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  * @cvs-id $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.h"
  42 #include "bestat.h"
  43
  44 #include <libcore/lc_opts.h>
  45 #include <libcore/lc_opts_enum.h>
  46
  47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
  48
  49 #define BE_SCHED_NODE(irn) (be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn))
  50
  51 enum {
  52         BE_SCHED_SELECT_TRIVIAL  = 0,
  53         BE_SCHED_SELECT_REGPRESS = 1,
  54         BE_SCHED_SELECT_MUCHNIK  = 2,
  55         BE_SCHED_SELECT_HEUR     = 3,
  56         BE_SCHED_SELECT_HMUCHNIK = 4,
  57         BE_SCHED_SELECT_RANDOM   = 5
  58 };
  59
  60 enum {
  61         BE_SCHED_PREP_NONE = 0,
  62         BE_SCHED_PREP_MRIS = 2,
  63         BE_SCHED_PREP_RSS  = 3
  64 };
  65
  66 typedef struct _list_sched_options_t {
  67         int select;  /**< the node selector */
  68         int prep;    /**< schedule preparation */
  69 } list_sched_options_t;
  70
  71 static list_sched_options_t list_sched_options = {
  72         BE_SCHED_SELECT_HEUR,     /* mueller heuristic selector */
  73         BE_SCHED_PREP_NONE,       /* no scheduling preparation */
  74 };
  75
  76 /* schedule selector options. */
  77 static const lc_opt_enum_int_items_t sched_select_items[] = {
  78         { "trivial",  BE_SCHED_SELECT_TRIVIAL  },
  79         { "random",   BE_SCHED_SELECT_RANDOM },
  80         { "regpress", BE_SCHED_SELECT_REGPRESS },
  81         { "muchnik",  BE_SCHED_SELECT_MUCHNIK  },
  82         { "heur",     BE_SCHED_SELECT_HEUR     },
  83         { "hmuchnik", BE_SCHED_SELECT_HMUCHNIK },
  84         { NULL,       0 }
  85 };
  86
  87 /* schedule preparation options. */
  88 static const lc_opt_enum_int_items_t sched_prep_items[] = {
  89         { "none", BE_SCHED_PREP_NONE },
  90         { "mris", BE_SCHED_PREP_MRIS },
  91         { "rss",  BE_SCHED_PREP_RSS  },
  92         { NULL,   0 }
  93 };
  94
  95 static lc_opt_enum_int_var_t sched_select_var = {
  96         &list_sched_options.select, sched_select_items
  97 };
  98
  99 static lc_opt_enum_int_var_t sched_prep_var = {
 100         &list_sched_options.prep, sched_prep_items
 101 };
 102
 103 static const lc_opt_table_entry_t list_sched_option_table[] = {
 104         LC_OPT_ENT_ENUM_PTR("prep",   "schedule preparation",   &sched_prep_var),
 105         LC_OPT_ENT_ENUM_PTR("select", "node selector",          &sched_select_var),
 106         { NULL }
 107 };
 108
 109 /**
 110  * All scheduling info needed per node.
 111  */
 112 typedef struct _sched_irn_t {
 113         unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
 114         unsigned already_sched : 1;  /**< Set if this node is already scheduled */
 115 } sched_irn_t;
 116
 117 /**
 118  * Scheduling environment for the whole graph.
 119  */
 120 typedef struct _sched_env_t {
 121         sched_irn_t *sched_info;                    /**< scheduling info per node */
 122         const list_sched_selector_t *selector;      /**< The node selector. */
 123         const arch_env_t *arch_env;                 /**< The architecture environment. */
 124         const ir_graph *irg;                        /**< The graph to schedule. */
 125         void *selector_env;                         /**< A pointer to give to the selector. */
 126 } sched_env_t;
 127
 128 /**
 129  * Environment for a block scheduler.
 130  */
 131 typedef struct _block_sched_env_t {
 132         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
 133         nodeset *cands;                             /**< the set of candidates */
 134         ir_node *block;                             /**< the current block */
 135         sched_env_t *sched_env;                     /**< the scheduler environment */
 136         nodeset *live;                              /**< simple liveness during scheduling */
 137         const list_sched_selector_t *selector;
 138         void *selector_block_env;
 139 } block_sched_env_t;
 140
 141 /**
 142  * Returns non-zero if the node is already scheduled
 143  */
 144 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
 145 {
 146         int idx = get_irn_idx(n);
 147
 148         assert(idx < ARR_LEN(env->sched_info));
 149         return env->sched_info[idx].already_sched;
 150 }
 151
 152 /**
 153  * Mark a node as already scheduled
 154  */
 155 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
 156 {
 157         int idx = get_irn_idx(n);
 158
 159         assert(idx < ARR_LEN(env->sched_info));
 160         env->sched_info[idx].already_sched = 1;
 161 }
 162
 163 /**
 164  * Try to put a node in the ready set.
 165  * @param env   The block scheduler environment.
 166  * @param pred  The previous scheduled node.
 167  * @param irn   The node to make ready.
 168  * @return 1, if the node could be made ready, 0 else.
 169  */
 170 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 171 {
 172         int i, n;
 173
 174         /* Blocks cannot be scheduled. */
 175         if (is_Block(irn) || get_irn_n_edges(irn) == 0)
 176                 return 0;
 177
 178         /*
 179          * Check, if the given ir node is in a different block as the
 180          * currently scheduled one. If that is so, don't make the node ready.
 181          */
 182         if (env->block != get_nodes_block(irn))
 183                 return 0;
 184
 185         for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 186                 ir_node *op = get_irn_in_or_dep(irn, i);
 187
 188                 /* if irn is an End we have keep-alives and op might be a block, skip that */
 189                 if (is_Block(op)) {
 190                         assert(get_irn_op(irn) == op_End);
 191                         continue;
 192                 }
 193
 194                 /* If the operand is local to the scheduled block and not yet
 195                  * scheduled, this nodes cannot be made ready, so exit. */
 196                 if (! is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 197                         return 0;
 198         }
 199
 200         nodeset_insert(env->cands, irn);
 201
 202         /* Notify selector about the ready node. */
 203         if (env->selector->node_ready)
 204                 env->selector->node_ready(env->selector_block_env, irn, pred);
 205
 206     DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 207
 208     return 1;
 209 }
 210
 211 /**
 212  * Try, to make all users of a node ready.
 213  * In fact, a usage node can only be made ready, if all its operands
 214  * have already been scheduled yet. This is checked by make_ready().
 215  * @param env The block schedule environment.
 216  * @param irn The node, which usages (successors) are to be made ready.
 217  */
 218 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
 219 {
 220         const ir_edge_t *edge;
 221
 222         foreach_out_edge(irn, edge) {
 223                 ir_node *user = get_edge_src_irn(edge);
 224                 if (! is_Phi(user))
 225                         make_ready(env, irn, user);
 226         }
 227
 228         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 229                 ir_node *user = get_edge_src_irn(edge);
 230                 if (! is_Phi(user))
 231                         make_ready(env, irn, user);
 232         }
 233 }
 234
 235 /**
 236  * Returns the number of not yet schedules users.
 237  */
 238 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
 239         int idx = get_irn_idx(n);
 240
 241         assert(idx < ARR_LEN(env->sched_info));
 242         return env->sched_info[idx].num_not_sched_user;
 243 }
 244
 245 /**
 246  * Sets the number of not yet schedules users.
 247  */
 248 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 249         int idx = get_irn_idx(n);
 250
 251         assert(idx < ARR_LEN(env->sched_info));
 252         env->sched_info[idx].num_not_sched_user = num;
 253 }
 254
 255 /**
 256  * Add @p num to the number of not yet schedules users and returns the result.
 257  */
 258 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 259         int idx = get_irn_idx(n);
 260
 261         assert(idx < ARR_LEN(env->sched_info));
 262         env->sched_info[idx].num_not_sched_user += num;
 263         return env->sched_info[idx].num_not_sched_user;
 264 }
 265
 266 /**
 267  * Returns the number of users of a node having mode datab.
 268  */
 269 static int get_num_successors(ir_node *irn) {
 270         int             sum = 0;
 271         const ir_edge_t *edge;
 272
 273         if (get_irn_mode(irn) == mode_T) {
 274                 /* for mode_T nodes: count the users of all Projs */
 275                 foreach_out_edge(irn, edge) {
 276                         ir_node *proj = get_edge_src_irn(edge);
 277                         ir_mode *mode = get_irn_mode(proj);
 278
 279                         if (mode == mode_T)
 280                                 sum += get_num_successors(proj);
 281                         else if (mode_is_datab(mode))
 282                                 sum += get_irn_n_edges(proj);
 283                 }
 284         }
 285         else {
 286                 /* do not count keep-alive edges */
 287                 foreach_out_edge(irn, edge) {
 288                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 289                                 sum++;
 290                 }
 291         }
 292
 293         return sum;
 294 }
 295
 296 /**
 297  * Adds irn to @p live, updates all inputs that this user is scheduled
 298  * and counts all of it's non scheduled users.
 299  */
 300 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
 301         int i;
 302
 303         /* ignore Projs */
 304         if (is_Proj(irn))
 305                 return;
 306
 307         for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
 308                 ir_node *in = get_irn_in_or_dep(irn, i);
 309
 310                 /* if in is a proj: update predecessor */
 311                 while (is_Proj(in))
 312                         in = get_Proj_pred(in);
 313
 314                 /* if in is still in the live set: reduce number of users by one */
 315                 if (nodeset_find(env->live, in)) {
 316                         if (add_irn_not_sched_user(env, in, -1) <= 0)
 317                                 nodeset_remove(env->live, in);
 318                 }
 319         }
 320
 321         /*
 322                 get_num_successors returns the number of all users. This includes
 323                 users in different blocks as well. As the each block is scheduled separately
 324                 the liveness info of those users will not be updated and so these
 325                 users will keep up the register pressure as it is desired.
 326         */
 327         i = get_num_successors(irn);
 328         if (i > 0) {
 329                 set_irn_not_sched_user(env, irn, i);
 330                 nodeset_insert(env->live, irn);
 331         }
 332 }
 333
 334 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
 335 {
 336         int res = -1;
 337
 338         if (get_irn_n_edges(irn) < 1)
 339                 return 0;
 340
 341         if (sel->to_appear_in_schedule)
 342                 res = sel->to_appear_in_schedule(block_env, irn);
 343
 344         return res >= 0 ? res : ((to_appear_in_schedule(irn) || BE_SCHED_NODE(irn)) && ! is_Unknown(irn));
 345 }
 346
 347 /**
 348  * Append an instruction to a schedule.
 349  * @param env The block scheduling environment.
 350  * @param irn The node to add to the schedule.
 351  * @return    The given node.
 352  */
 353 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
 354 {
 355     /* If the node consumes/produces data, it is appended to the schedule
 356      * list, otherwise, it is not put into the list */
 357     if (must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
 358                 update_sched_liveness(env, irn);
 359         sched_add_before(env->block, irn);
 360
 361         DBG((dbg, LEVEL_2, "\tadding %+F\n", irn));
 362     }
 363
 364         /* notify the selector about the finally selected node. */
 365         if (env->selector->node_selected)
 366                 env->selector->node_selected(env->selector_block_env, irn);
 367
 368     /* Insert the node in the set of all already scheduled nodes. */
 369     mark_already_scheduled(env, irn);
 370
 371     /* Remove the node from the ready set */
 372     if(nodeset_find(env->cands, irn))
 373         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         be.cands      = new_nodeset(get_irn_n_edges(block));
 448         be.live       = new_nodeset(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 (nodeset_count(be.cands) > 0) {
 510                 /* collect statistics about amount of ready nodes */
 511                 be_do_stat_sched_ready(block, be.cands);
 512
 513                 /* Keeps must be scheduled immediatly */
 514                 foreach_nodeset(be.cands, irn) {
 515                         if (be_is_Keep(irn) || be_is_CopyKeep(irn) || is_Sync(irn)) {
 516                                 nodeset_break(be.cands);
 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                 if (nodeset_find(be.cands, irn))
 538                         nodeset_remove(be.cands, irn);
 539         }
 540
 541         if (selector->finish_block)
 542                 selector->finish_block(be.selector_block_env);
 543
 544         del_nodeset(be.cands);
 545         del_nodeset(be.live);
 546 }
 547
 548 /* List schedule a graph. */
 549 void list_sched(const be_irg_t *birg, be_options_t *be_opts)
 550 {
 551         const arch_env_t *arch_env = birg->main_env->arch_env;
 552         ir_graph         *irg      = birg->irg;
 553
 554         int num_nodes;
 555         sched_env_t env;
 556         mris_env_t *mris = NULL;
 557         list_sched_selector_t sel;
 558
 559         /* Select a scheduler based on backend options */
 560         switch (list_sched_options.select) {
 561                 case BE_SCHED_SELECT_TRIVIAL:
 562                         memcpy(&sel, trivial_selector, sizeof(sel));
 563                         break;
 564                 case BE_SCHED_SELECT_RANDOM:
 565                         memcpy(&sel, random_selector, sizeof(sel));
 566                         break;
 567                 case BE_SCHED_SELECT_REGPRESS:
 568                         memcpy(&sel, reg_pressure_selector, sizeof(sel));
 569                         break;
 570                 case BE_SCHED_SELECT_MUCHNIK:
 571                         memcpy(&sel, muchnik_selector, sizeof(sel));
 572                         break;
 573                 case BE_SCHED_SELECT_HEUR:
 574                         memcpy(&sel, heuristic_selector, sizeof(sel));
 575                         break;
 576                 case BE_SCHED_SELECT_HMUCHNIK:
 577                 default:
 578                         memcpy(&sel, trivial_selector, sizeof(sel));
 579         }
 580
 581 #if 1
 582         /* Matze: This is very slow, we should avoid it to improve backend speed,
 583          * we just have to make sure that we have no dangling out-edges at this
 584          * point...
 585          */
 586
 587         /* Assure, that we have no dangling out-edges to deleted stuff */
 588         edges_deactivate(birg->irg);
 589         edges_activate(birg->irg);
 590 #endif
 591
 592         switch (list_sched_options.prep) {
 593                 case BE_SCHED_PREP_MRIS:
 594                         mris = be_sched_mris_preprocess(birg);
 595                         break;
 596                 case BE_SCHED_PREP_RSS:
 597                         rss_schedule_preparation(birg);
 598                         break;
 599                 default:
 600                         break;
 601         }
 602
 603         num_nodes = get_irg_last_idx(irg);
 604
 605         /* initialize environment for list scheduler */
 606         memset(&env, 0, sizeof(env));
 607         env.selector   = arch_env->isa->impl->get_list_sched_selector(arch_env->isa, &sel);
 608         env.arch_env   = arch_env;
 609         env.irg        = irg;
 610         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 611
 612         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 613
 614         if (env.selector->init_graph)
 615                 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
 616
 617         /* Schedule each single block. */
 618         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 619
 620         if (env.selector->finish_graph)
 621                 env.selector->finish_graph(env.selector_env);
 622
 623         if (list_sched_options.prep == BE_SCHED_PREP_MRIS)
 624                 be_sched_mris_free(mris);
 625
 626         DEL_ARR_F(env.sched_info);
 627 }
 628
 629 /* List schedule a block. */
 630 void list_sched_single_block(const be_irg_t *birg, ir_node *block, be_options_t *be_opts)
 631 {
 632         const arch_env_t *arch_env = birg->main_env->arch_env;
 633         ir_graph         *irg      = birg->irg;
 634
 635         int num_nodes;
 636         sched_env_t env;
 637         list_sched_selector_t sel;
 638
 639         /* Select a scheduler based on backend options */
 640         switch (list_sched_options.select) {
 641                 case BE_SCHED_SELECT_TRIVIAL:
 642                         memcpy(&sel, trivial_selector, sizeof(sel));
 643                         break;
 644                 case BE_SCHED_SELECT_RANDOM:
 645                         memcpy(&sel, random_selector, sizeof(sel));
 646                         break;
 647                 case BE_SCHED_SELECT_REGPRESS:
 648                         memcpy(&sel, reg_pressure_selector, sizeof(sel));
 649                         break;
 650                 case BE_SCHED_SELECT_MUCHNIK:
 651                         memcpy(&sel, muchnik_selector, sizeof(sel));
 652                         break;
 653                 case BE_SCHED_SELECT_HEUR:
 654                         memcpy(&sel, heuristic_selector, sizeof(sel));
 655                         break;
 656                 case BE_SCHED_SELECT_HMUCHNIK:
 657                 default:
 658                         memcpy(&sel, trivial_selector, sizeof(sel));
 659         }
 660
 661         /* Assure, that the out edges are computed */
 662         edges_deactivate(birg->irg);
 663         edges_activate(birg->irg);
 664
 665         num_nodes = get_irg_last_idx(irg);
 666
 667         /* initialize environment for list scheduler */
 668         memset(&env, 0, sizeof(env));
 669         env.selector   = arch_env->isa->impl->get_list_sched_selector(arch_env->isa, &sel);
 670         env.arch_env   = arch_env;
 671         env.irg        = irg;
 672         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 673
 674         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 675
 676         if (env.selector->init_graph)
 677                 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
 678
 679         /* Schedule block. */
 680         list_sched_block(block, &env);
 681
 682         if (env.selector->finish_graph)
 683                 env.selector->finish_graph(env.selector_env);
 684
 685         DEL_ARR_F(env.sched_info);
 686 }
 687
 688 /**
 689  * Register list scheduler options.
 690  */
 691 void be_init_listsched(void) {
 692         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 693         lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "listsched");
 694
 695         lc_opt_add_table(sched_grp, list_sched_option_table);
 696
 697         FIRM_DBG_REGISTER(dbg, "firm.be.sched");
 698 }
 699
 700 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched);