nsz Git - libfirm/blob - ir/be/belistsched.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Primitive list scheduling with different node selectors.
  23  * @author      Sebastian Hack
  24  * @date        20.10.2004
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include <stdio.h>
  30 #include <stdarg.h>
  31 #include <string.h>
  32 #include <limits.h>
  33
  34 #include "benode.h"
  35 #include "be_t.h"
  36
  37 #include "obst.h"
  38 #include "list.h"
  39 #include "iterator.h"
  40
  41 #include "iredges_t.h"
  42 #include "irgwalk.h"
  43 #include "irnode_t.h"
  44 #include "irmode_t.h"
  45 #include "irdump.h"
  46 #include "irprintf_t.h"
  47 #include "array.h"
  48 #include "debug.h"
  49 #include "irtools.h"
  50
  51 #include "bemodule.h"
  52 #include "besched.h"
  53 #include "beutil.h"
  54 #include "belive_t.h"
  55 #include "belistsched.h"
  56 #include "beschedmris.h"
  57 #include "beschedrss.h"
  58 #include "bearch.h"
  59 #include "bestat.h"
  60 #include "beirg.h"
  61
  62 #include "lc_opts.h"
  63 #include "lc_opts_enum.h"
  64
  65 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
  66
  67 enum {
  68         BE_SCHED_SELECT_TRIVIAL,
  69         BE_SCHED_SELECT_REGPRESS,
  70         BE_SCHED_SELECT_MUCHNIK,
  71         BE_SCHED_SELECT_HEUR,
  72         BE_SCHED_SELECT_HMUCHNIK,
  73         BE_SCHED_SELECT_RANDOM,
  74         BE_SCHED_SELECT_NORMAL,
  75 };
  76
  77 enum {
  78         BE_SCHED_PREP_NONE = 0,
  79         BE_SCHED_PREP_MRIS = 2,
  80         BE_SCHED_PREP_RSS  = 3
  81 };
  82
  83 typedef struct list_sched_options_t {
  84         int select;  /**< the node selector */
  85         int prep;    /**< schedule preparation */
  86 } list_sched_options_t;
  87
  88 static list_sched_options_t list_sched_options = {
  89         BE_SCHED_SELECT_NORMAL,   /* mueller heuristic selector */
  90         BE_SCHED_PREP_NONE,       /* no scheduling preparation */
  91 };
  92
  93 /* schedule selector options. */
  94 static const lc_opt_enum_int_items_t sched_select_items[] = {
  95         { "trivial",  BE_SCHED_SELECT_TRIVIAL  },
  96         { "random",   BE_SCHED_SELECT_RANDOM   },
  97         { "regpress", BE_SCHED_SELECT_REGPRESS },
  98         { "normal",   BE_SCHED_SELECT_NORMAL   },
  99         { "muchnik",  BE_SCHED_SELECT_MUCHNIK  },
 100         { "heur",     BE_SCHED_SELECT_HEUR     },
 101         { "hmuchnik", BE_SCHED_SELECT_HMUCHNIK },
 102         { NULL,       0 }
 103 };
 104
 105 /* schedule preparation options. */
 106 static const lc_opt_enum_int_items_t sched_prep_items[] = {
 107         { "none", BE_SCHED_PREP_NONE },
 108         { "mris", BE_SCHED_PREP_MRIS },
 109         { "rss",  BE_SCHED_PREP_RSS  },
 110         { NULL,   0 }
 111 };
 112
 113 static lc_opt_enum_int_var_t sched_select_var = {
 114         &list_sched_options.select, sched_select_items
 115 };
 116
 117 static lc_opt_enum_int_var_t sched_prep_var = {
 118         &list_sched_options.prep, sched_prep_items
 119 };
 120
 121 static const lc_opt_table_entry_t list_sched_option_table[] = {
 122         LC_OPT_ENT_ENUM_PTR("prep",   "schedule preparation",   &sched_prep_var),
 123         LC_OPT_ENT_ENUM_PTR("select", "node selector",          &sched_select_var),
 124         LC_OPT_LAST
 125 };
 126
 127 /**
 128  * All scheduling info needed per node.
 129  */
 130 typedef struct sched_irn_t {
 131         unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
 132         unsigned already_sched : 1;  /**< Set if this node is already scheduled */
 133 } sched_irn_t;
 134
 135 /**
 136  * Scheduling environment for the whole graph.
 137  */
 138 typedef struct sched_env_t {
 139         sched_irn_t *sched_info;                    /**< scheduling info per node */
 140         const list_sched_selector_t *selector;      /**< The node selector. */
 141         void *selector_env;                         /**< A pointer to give to the selector. */
 142 } sched_env_t;
 143
 144 /**
 145  * Environment for a block scheduler.
 146  */
 147 typedef struct block_sched_env_t {
 148         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
 149         ir_nodeset_t cands;                         /**< the set of candidates */
 150         ir_node *block;                             /**< the current block */
 151         sched_env_t *sched_env;                     /**< the scheduler environment */
 152         ir_nodeset_t live;                          /**< simple liveness during scheduling */
 153         const list_sched_selector_t *selector;
 154         void *selector_block_env;
 155 } block_sched_env_t;
 156
 157 /**
 158  * Returns non-zero if the node is already scheduled
 159  */
 160 static inline int is_already_scheduled(block_sched_env_t *env, ir_node *n)
 161 {
 162         int idx = get_irn_idx(n);
 163
 164         assert(idx < ARR_LEN(env->sched_info));
 165         return env->sched_info[idx].already_sched;
 166 }
 167
 168 /**
 169  * Mark a node as already scheduled
 170  */
 171 static inline void set_already_scheduled(block_sched_env_t *env, ir_node *n)
 172 {
 173         int idx = get_irn_idx(n);
 174
 175         assert(idx < ARR_LEN(env->sched_info));
 176         env->sched_info[idx].already_sched = 1;
 177 }
 178
 179 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
 180
 181 /**
 182  * Try to put a node in the ready set.
 183  * @param env   The block scheduler environment.
 184  * @param pred  The previous scheduled node.
 185  * @param irn   The node to make ready.
 186  * @return 1, if the node could be made ready, 0 else.
 187  */
 188 static inline int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 189 {
 190         int i, n;
 191
 192         /* Blocks cannot be scheduled. */
 193         if (is_Block(irn) || get_irn_n_edges(irn) == 0)
 194                 return 0;
 195
 196         /*
 197          * Check, if the given ir node is in a different block as the
 198          * currently scheduled one. If that is so, don't make the node ready.
 199          */
 200         if (env->block != get_nodes_block(irn))
 201                 return 0;
 202
 203         for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 204                 ir_node *op = get_irn_in_or_dep(irn, i);
 205
 206                 /* if irn is an End we have keep-alives and op might be a block, skip that */
 207                 if (is_Block(op)) {
 208                         assert(is_End(irn));
 209                         continue;
 210                 }
 211
 212                 /* If the operand is local to the scheduled block and not yet
 213                  * scheduled, this nodes cannot be made ready, so exit. */
 214                 if (! is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 215                         return 0;
 216         }
 217
 218         if (! to_appear_in_schedule(irn)) {
 219                 add_to_sched(env, irn);
 220                 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
 221         } else {
 222                 ir_nodeset_insert(&env->cands, irn);
 223
 224                 /* Notify selector about the ready node. */
 225                 if (env->selector->node_ready)
 226                         env->selector->node_ready(env->selector_block_env, irn, pred);
 227
 228                 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 229         }
 230
 231     return 1;
 232 }
 233
 234 /**
 235  * Try, to make all users of a node ready.
 236  * In fact, a usage node can only be made ready, if all its operands
 237  * have already been scheduled yet. This is checked by make_ready().
 238  * @param env The block schedule environment.
 239  * @param irn The node, which usages (successors) are to be made ready.
 240  */
 241 static void make_users_ready(block_sched_env_t *env, ir_node *irn)
 242 {
 243         const ir_edge_t *edge;
 244
 245         /* make all data users ready */
 246         foreach_out_edge(irn, edge) {
 247                 ir_node *user = get_edge_src_irn(edge);
 248
 249                 if (! is_Phi(user))
 250                         make_ready(env, irn, user);
 251         }
 252
 253         /* and the dependent nodes as well */
 254         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 255                 ir_node *user = get_edge_src_irn(edge);
 256
 257                 if (! is_Phi(user))
 258                         make_ready(env, irn, user);
 259         }
 260 }
 261
 262 /**
 263  * Returns the number of not yet schedules users.
 264  */
 265 static inline int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n)
 266 {
 267         int idx = get_irn_idx(n);
 268
 269         assert(idx < ARR_LEN(env->sched_info));
 270         return env->sched_info[idx].num_not_sched_user;
 271 }
 272
 273 /**
 274  * Sets the number of not yet schedules users.
 275  */
 276 static inline void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num)
 277 {
 278         int idx = get_irn_idx(n);
 279
 280         assert(idx < ARR_LEN(env->sched_info));
 281         env->sched_info[idx].num_not_sched_user = num;
 282 }
 283
 284 /**
 285  * Add @p num to the number of not yet schedules users and returns the result.
 286  */
 287 static inline int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num)
 288 {
 289         int idx = get_irn_idx(n);
 290
 291         assert(idx < ARR_LEN(env->sched_info));
 292         env->sched_info[idx].num_not_sched_user += num;
 293         return env->sched_info[idx].num_not_sched_user;
 294 }
 295
 296 /**
 297  * Returns the number of users of a node having mode datab.
 298  */
 299 static int get_num_successors(ir_node *irn)
 300 {
 301         int             sum = 0;
 302         const ir_edge_t *edge;
 303
 304         if (get_irn_mode(irn) == mode_T) {
 305                 /* for mode_T nodes: count the users of all Projs */
 306                 foreach_out_edge(irn, edge) {
 307                         ir_node *proj = get_edge_src_irn(edge);
 308                         ir_mode *mode = get_irn_mode(proj);
 309
 310                         if (mode == mode_T) {
 311                                 sum += get_num_successors(proj);
 312                         } else if (mode_is_datab(mode)) {
 313                                 sum += get_irn_n_edges(proj);
 314                         }
 315                 }
 316         }
 317         else {
 318                 /* do not count keep-alive edges */
 319                 foreach_out_edge(irn, edge) {
 320                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 321                                 sum++;
 322                 }
 323         }
 324
 325         return sum;
 326 }
 327
 328 /**
 329  * Adds irn to @p live, updates all inputs that this user is scheduled
 330  * and counts all of its non scheduled users.
 331  */
 332 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn)
 333 {
 334         int i;
 335
 336         /* ignore Projs */
 337         if (is_Proj(irn))
 338                 return;
 339
 340         for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
 341                 ir_node *in = get_irn_in_or_dep(irn, i);
 342
 343                 /* if in is a proj: update predecessor */
 344                 in = skip_Proj(in);
 345
 346                 /* if in is still in the live set: reduce number of users by one */
 347                 if (ir_nodeset_contains(&env->live, in)) {
 348                         if (add_irn_not_sched_user(env, in, -1) <= 0)
 349                                 ir_nodeset_remove(&env->live, in);
 350                 }
 351         }
 352
 353         /*
 354                 get_num_successors returns the number of all users. This includes
 355                 users in different blocks as well. As the each block is scheduled separately
 356                 the liveness info of those users will not be updated and so these
 357                 users will keep up the register pressure as it is desired.
 358         */
 359         i = get_num_successors(irn);
 360         if (i > 0) {
 361                 set_irn_not_sched_user(env, irn, i);
 362                 ir_nodeset_insert(&env->live, irn);
 363         }
 364 }
 365
 366 /**
 367  * Append an instruction to a schedule.
 368  * @param env The block scheduling environment.
 369  * @param irn The node to add to the schedule.
 370  * @return    The given node.
 371  */
 372 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
 373 {
 374     /* If the node consumes/produces data, it is appended to the schedule
 375      * list, otherwise, it is not put into the list */
 376     if (to_appear_in_schedule(irn)) {
 377                 update_sched_liveness(env, irn);
 378                 sched_add_before(env->block, irn);
 379
 380                 DBG((dbg, LEVEL_2, "\tadding %+F\n", irn));
 381
 382                 /* Remove the node from the ready set */
 383                 ir_nodeset_remove(&env->cands, irn);
 384     }
 385
 386         /* notify the selector about the finally selected node. */
 387         if (env->selector->node_selected)
 388                 env->selector->node_selected(env->selector_block_env, irn);
 389
 390     /* Insert the node in the set of all available scheduled nodes. */
 391     set_already_scheduled(env, irn);
 392
 393         make_users_ready(env, irn);
 394 }
 395
 396 /**
 397  * Perform list scheduling on a block.
 398  *
 399  * Note, that the caller must compute a linked list of nodes in the block
 400  * using the link field before calling this function.
 401  *
 402  * Also the outs must have been computed.
 403  *
 404  * @param block The block node.
 405  * @param env Scheduling environment.
 406  */
 407 static void list_sched_block(ir_node *block, void *env_ptr)
 408 {
 409         sched_env_t *env                      = env_ptr;
 410         const list_sched_selector_t *selector = env->selector;
 411
 412         block_sched_env_t be;
 413         const ir_edge_t *edge;
 414         ir_node *irn;
 415         int j, m;
 416
 417         /* Initialize the block's list head that will hold the schedule. */
 418         sched_init_block(block);
 419
 420         /* Initialize the block scheduling environment */
 421         be.sched_info = env->sched_info;
 422         be.block      = block;
 423         ir_nodeset_init_size(&be.cands, get_irn_n_edges(block));
 424         ir_nodeset_init_size(&be.live, get_irn_n_edges(block));
 425         be.selector   = selector;
 426         be.sched_env  = env;
 427
 428         DBG((dbg, LEVEL_1, "scheduling %+F\n", block));
 429
 430         if (selector->init_block)
 431                 be.selector_block_env = selector->init_block(env->selector_env, block);
 432
 433         /* Then one can add all nodes are ready to the set. */
 434         foreach_out_edge(block, edge) {
 435                 ir_node   *irn = get_edge_src_irn(edge);
 436                 ir_opcode code = get_irn_opcode(irn);
 437                 int users;
 438
 439                 if (code == iro_End) {
 440                         /* Skip the end node because of keep-alive edges. */
 441                         continue;
 442                 } else if (code == iro_Block) {
 443                         /* A Block-Block edge. This should be the MacroBlock
 444                          * edge, ignore it. */
 445                         assert(get_Block_MacroBlock(irn) == block && "Block-Block edge found");
 446                         continue;
 447                 }
 448
 449                 users = get_irn_n_edges(irn);
 450                 if (users == 0)
 451                         continue;
 452                 else if (users == 1) { /* ignore nodes that are only hold by the anchor */
 453                         const ir_edge_t *edge = get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL);
 454                         ir_node *user = get_edge_src_irn(edge);
 455                         if (is_Anchor(user))
 456                                 continue;
 457                 }
 458
 459                 if (is_Phi(irn)) {
 460                         /*
 461                                 Phi functions are scheduled immediately, since they     only
 462                                 transfer data flow from the predecessors to this block.
 463                         */
 464                         add_to_sched(&be, irn);
 465                 } else if (be_is_Start(irn)) {
 466                         /* The start block will be scheduled as the first node */
 467                         add_to_sched(&be, irn);
 468                 } else {
 469                         /* Other nodes must have all operands in other blocks to be made
 470                          * ready */
 471                         int ready = 1;
 472
 473                         /* Check, if the operands of a node are not local to this block */
 474                         for (j = 0, m = get_irn_ins_or_deps(irn); j < m; ++j) {
 475                                 ir_node *operand = get_irn_in_or_dep(irn, j);
 476
 477                                 if (get_nodes_block(operand) == block) {
 478                                         ready = 0;
 479                                         break;
 480                                 } else {
 481                                         /* live in values increase register pressure */
 482                                         ir_nodeset_insert(&be.live, operand);
 483                                 }
 484                         }
 485
 486                         /* Make the node ready, if all operands live in a foreign block */
 487                         if (ready) {
 488                                 DBG((dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
 489                                 make_ready(&be, NULL, irn);
 490                         }
 491                 }
 492         }
 493
 494         /* Iterate over all remaining nodes */
 495         while (ir_nodeset_size(&be.cands) > 0) {
 496                 ir_nodeset_iterator_t iter;
 497
 498                 /* Keeps must be scheduled immediately */
 499                 foreach_ir_nodeset(&be.cands, irn, iter) {
 500                         if (be_is_Keep(irn) || be_is_CopyKeep(irn) || is_Sync(irn)) {
 501                                 break;
 502                         }
 503                 }
 504
 505                 if (! irn) {
 506                         /* Keeps must be immediately scheduled */
 507                         irn = be.selector->select(be.selector_block_env, &be.cands, &be.live);
 508                 }
 509
 510                 DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 511
 512                 /* Add the node to the schedule. */
 513                 add_to_sched(&be, irn);
 514
 515                 /* remove the scheduled node from the ready list. */
 516                 ir_nodeset_remove(&be.cands, irn);
 517         }
 518
 519         if (selector->finish_block)
 520                 selector->finish_block(be.selector_block_env);
 521
 522         ir_nodeset_destroy(&be.cands);
 523         ir_nodeset_destroy(&be.live);
 524 }
 525
 526 /* List schedule a graph. */
 527 void list_sched(ir_graph *irg)
 528 {
 529         int num_nodes;
 530         sched_env_t env;
 531         mris_env_t *mris = NULL;
 532         const list_sched_selector_t *selector;
 533
 534         /* Select a scheduler based on backend options */
 535         switch (list_sched_options.select) {
 536                 case BE_SCHED_SELECT_TRIVIAL:  selector = &trivial_selector;      break;
 537                 case BE_SCHED_SELECT_RANDOM:   selector = &random_selector;       break;
 538                 case BE_SCHED_SELECT_REGPRESS: selector = &reg_pressure_selector; break;
 539                 case BE_SCHED_SELECT_MUCHNIK:  selector = &muchnik_selector;      break;
 540                 case BE_SCHED_SELECT_HEUR:     selector = &heuristic_selector;    break;
 541                 case BE_SCHED_SELECT_NORMAL:   selector = &normal_selector;       break;
 542                 default:
 543                 case BE_SCHED_SELECT_HMUCHNIK: selector = &heuristic_selector;    break;
 544         }
 545
 546 #if 1
 547         /* Matze: This is very slow, we should avoid it to improve backend speed,
 548          * we just have to make sure that we have no dangling out-edges at this
 549          * point...
 550          */
 551
 552         /* Assure, that we have no dangling out-edges to deleted stuff */
 553         edges_deactivate(irg);
 554         edges_activate(irg);
 555 #endif
 556
 557         switch (list_sched_options.prep) {
 558                 case BE_SCHED_PREP_MRIS:
 559                         mris = be_sched_mris_preprocess(irg);
 560                         break;
 561                 case BE_SCHED_PREP_RSS:
 562                         rss_schedule_preparation(irg);
 563                         break;
 564                 default:
 565                         break;
 566         }
 567
 568         num_nodes = get_irg_last_idx(irg);
 569
 570         /* initialize environment for list scheduler */
 571         memset(&env, 0, sizeof(env));
 572         env.selector   = selector;
 573         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 574
 575         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 576
 577         if (env.selector->init_graph)
 578                 env.selector_env = env.selector->init_graph(env.selector, irg);
 579
 580         /* Schedule each single block. */
 581         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 582
 583         if (env.selector->finish_graph)
 584                 env.selector->finish_graph(env.selector_env);
 585
 586         if (list_sched_options.prep == BE_SCHED_PREP_MRIS)
 587                 be_sched_mris_free(mris);
 588
 589         DEL_ARR_F(env.sched_info);
 590 }
 591
 592 /* List schedule a block. */
 593 void list_sched_single_block(ir_graph *irg, ir_node *block)
 594 {
 595         int num_nodes;
 596         sched_env_t env;
 597         const list_sched_selector_t *selector;
 598
 599         /* Select a scheduler based on backend options */
 600         switch (list_sched_options.select) {
 601                 case BE_SCHED_SELECT_TRIVIAL:  selector = &trivial_selector;      break;
 602                 case BE_SCHED_SELECT_RANDOM:   selector = &random_selector;       break;
 603                 case BE_SCHED_SELECT_REGPRESS: selector = &reg_pressure_selector; break;
 604                 case BE_SCHED_SELECT_MUCHNIK:  selector = &muchnik_selector;      break;
 605                 case BE_SCHED_SELECT_HEUR:     selector = &heuristic_selector;    break;
 606                 case BE_SCHED_SELECT_NORMAL:   selector = &normal_selector;       break;
 607                 default:
 608                 case BE_SCHED_SELECT_HMUCHNIK: selector = &trivial_selector;      break;
 609         }
 610
 611         /* Assure, that the out edges are computed */
 612         edges_deactivate(irg);
 613         edges_activate(irg);
 614
 615         num_nodes = get_irg_last_idx(irg);
 616
 617         /* initialize environment for list scheduler */
 618         memset(&env, 0, sizeof(env));
 619         env.selector   = selector;
 620         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 621
 622         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 623
 624         if (env.selector->init_graph)
 625                 env.selector_env = env.selector->init_graph(env.selector, irg);
 626
 627         /* Schedule block. */
 628         list_sched_block(block, &env);
 629
 630         if (env.selector->finish_graph)
 631                 env.selector->finish_graph(env.selector_env);
 632
 633         DEL_ARR_F(env.sched_info);
 634 }
 635
 636 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched);
 637 void be_init_listsched(void)
 638 {
 639         lc_opt_entry_t *be_grp    = lc_opt_get_grp(firm_opt_get_root(), "be");
 640         lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "listsched");
 641
 642         lc_opt_add_table(sched_grp, list_sched_option_table);
 643
 644         FIRM_DBG_REGISTER(dbg, "firm.be.sched");
 645 }