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

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