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

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