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  */
   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
  19 #include "obst.h"
  20 #include "list.h"
  21 #include "iterator.h"
  22
  23 #include "iredges_t.h"
  24 #include "irgwalk.h"
  25 #include "irnode_t.h"
  26 #include "irmode_t.h"
  27 #include "irdump.h"
  28 #include "irprintf_t.h"
  29 #include "array.h"
  30 #include "debug.h"
  31 #include "irtools.h"
  32
  33 #include "besched_t.h"
  34 #include "beutil.h"
  35 #include "belive_t.h"
  36 #include "belistsched.h"
  37 #include "beschedmris.h"
  38 #include "bearch.h"
  39 #include "bestat.h"
  40
  41 /**
  42  * All scheduling info needed per node.
  43  */
  44 typedef struct _sched_irn_t {
  45         sched_timestep_t delay;     /**< The delay for this node if already calculated, else 0. */
  46         sched_timestep_t etime;     /**< The earliest time of this node. */
  47         unsigned already_sched : 1; /**< Set if this node is already scheduled */
  48         unsigned is_root       : 1; /**< is a root node of a block */
  49 } sched_irn_t;
  50
  51 /**
  52  * Scheduling environment for the whole graph.
  53  */
  54 typedef struct _sched_env_t {
  55         sched_irn_t *sched_info;                    /**< scheduling info per node */
  56         const list_sched_selector_t *selector;      /**< The node selector. */
  57         const arch_env_t *arch_env;                 /**< The architecture environment. */
  58         const ir_graph *irg;                        /**< The graph to schedule. */
  59         void *selector_env;                         /**< A pointer to give to the selector. */
  60 } sched_env_t;
  61
  62 #if 0
  63 /*
  64  * Ugly global variable for the compare function
  65  * since qsort(3) does not pass an extra pointer.
  66  */
  67 static ir_node *curr_bl = NULL;
  68
  69 static int cmp_usage(const void *a, const void *b)
  70 {
  71         struct trivial_sched_env *env;
  72         const ir_node *p = a;
  73         const ir_node *q = b;
  74         int res = 0;
  75
  76         res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
  77
  78         /*
  79          * One of them is live at the end of the block.
  80          * Then, that one shall be scheduled at after the other
  81          */
  82         if(res != 0)
  83                 return res;
  84
  85
  86         return res;
  87 }
  88 #endif
  89
  90 /**
  91  * The trivial selector:
  92  * Just assure that branches are executed last, otherwise select
  93  * the first node ready.
  94  */
  95 static ir_node *trivial_select(void *block_env, nodeset *ready_set)
  96 {
  97         const arch_env_t *arch_env = block_env;
  98         ir_node *irn = NULL;
  99         int const_last = 0;
 100
 101         /* assure that branches and constants are executed last */
 102         for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
 103                 arch_irn_class_t irn_class = arch_irn_classify(arch_env, irn);
 104
 105                 if (irn_class != arch_irn_class_branch && (const_last ? (irn_class != arch_irn_class_const) : 1)) {
 106                         nodeset_break(ready_set);
 107                         return irn;
 108                 }
 109         }
 110
 111         /* assure that constants are executed before branches */
 112         if (const_last) {
 113                 for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
 114                         if (arch_irn_classify(arch_env, irn) != arch_irn_class_branch) {
 115                                 nodeset_break(ready_set);
 116                                 return irn;
 117                         }
 118                 }
 119         }
 120
 121
 122         /* at last: schedule branches */
 123         irn = nodeset_first(ready_set);
 124         nodeset_break(ready_set);
 125
 126         return irn;
 127 }
 128
 129 static void *trivial_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 130 {
 131         return (void *) arch_env;
 132 }
 133
 134 static void *trivial_init_block(void *graph_env, ir_node *bl)
 135 {
 136         return graph_env;
 137 }
 138
 139 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
 140 {
 141         int res = -1;
 142
 143         if(sel->to_appear_in_schedule)
 144                 res = sel->to_appear_in_schedule(block_env, irn);
 145
 146         return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_RegParams(irn));
 147 }
 148
 149 static const list_sched_selector_t trivial_selector_struct = {
 150         trivial_init_graph,
 151         trivial_init_block,
 152         trivial_select,
 153         NULL,                /* to_appear_in_schedule */
 154         NULL,                /* exectime */
 155         NULL,                /* latency */
 156         NULL,                /* finish_block */
 157         NULL                 /* finish_graph */
 158 };
 159
 160 const list_sched_selector_t *trivial_selector = &trivial_selector_struct;
 161
 162 typedef struct _usage_stats_t {
 163         ir_node *irn;
 164         struct _usage_stats_t *next;
 165         int max_hops;
 166         int uses_in_block;      /**< Number of uses inside the current block. */
 167         int already_consumed;   /**< Number of insns using this value already
 168                                                           scheduled. */
 169 } usage_stats_t;
 170
 171 typedef struct {
 172         const list_sched_selector_t *vtab;
 173         const arch_env_t *arch_env;
 174 } reg_pressure_main_env_t;
 175
 176 typedef struct {
 177         struct obstack obst;
 178         const reg_pressure_main_env_t *main_env;
 179         usage_stats_t *root;
 180         nodeset *already_scheduled;
 181 } reg_pressure_selector_env_t;
 182
 183 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
 184 {
 185         usage_stats_t *us = get_irn_link(irn);
 186
 187         if(!us) {
 188                 us                   = obstack_alloc(&env->obst, sizeof(us[0]));
 189                 us->irn              = irn;
 190                 us->already_consumed = 0;
 191                 us->max_hops         = INT_MAX;
 192                 us->next             = env->root;
 193                 env->root            = us;
 194                 set_irn_link(irn, us);
 195         }
 196
 197         return us;
 198 }
 199
 200 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
 201 {
 202         usage_stats_t *us = get_irn_link(irn);
 203         assert(us && "This node must have usage stats");
 204         return us;
 205 }
 206
 207 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
 208 {
 209         ir_node *bl = get_nodes_block(irn);
 210         /*
 211          * If the reached node is not in the block desired,
 212          * return the value passed for this situation.
 213          */
 214         if(get_nodes_block(irn) != bl)
 215                 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
 216
 217         /*
 218          * If the node is in the current block but not
 219          * yet scheduled, we keep on searching from that node.
 220          */
 221         if(!nodeset_find(env->already_scheduled, irn)) {
 222                 int i, n;
 223                 int res = 0;
 224                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 225                         ir_node *operand = get_irn_n(irn, i);
 226
 227                         if(get_irn_visited(operand) < visited_nr) {
 228                                 int tmp;
 229
 230                                 set_irn_visited(operand, visited_nr);
 231                                 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
 232                                 res = MAX(tmp, res);
 233                         }
 234                 }
 235
 236                 return res;
 237         }
 238
 239         /*
 240          * If the node is in the current block and scheduled, return
 241          * the depth which indicates the number of steps to the
 242          * region of scheduled nodes.
 243          */
 244         return depth;
 245 }
 246
 247 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
 248 {
 249         ir_node *bl   = get_nodes_block(irn);
 250         ir_graph *irg = get_irn_irg(bl);
 251         int res       = 0;
 252
 253         const ir_edge_t *edge;
 254
 255         foreach_out_edge(irn, edge) {
 256                 ir_node *user       = get_edge_src_irn(edge);
 257                 unsigned visited_nr = get_irg_visited(irg) + 1;
 258                 int max_hops;
 259
 260                 set_irg_visited(irg, visited_nr);
 261                 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
 262                 res      = MAX(res, max_hops);
 263         }
 264
 265         return res;
 266 }
 267
 268 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 269 {
 270         reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
 271
 272         main_env->arch_env = arch_env;
 273         main_env->vtab     = vtab;
 274         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 275
 276         return main_env;
 277 }
 278
 279 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
 280 {
 281         ir_node *irn;
 282         reg_pressure_selector_env_t *env  = xmalloc(sizeof(env[0]));
 283
 284         obstack_init(&env->obst);
 285         env->already_scheduled = new_nodeset(32);
 286         env->root              = NULL;
 287         env->main_env          = graph_env;
 288
 289         /*
 290          * Collect usage statistics.
 291          */
 292         sched_foreach(bl, irn) {
 293                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 294                         int i, n;
 295
 296                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 297                                 ir_node *op = get_irn_n(irn, i);
 298                                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 299                                         usage_stats_t *us = get_or_set_usage_stats(env, irn);
 300                                         if(is_live_end(bl, op))
 301                                                 us->uses_in_block = 99999;
 302                                         else
 303                                                 us->uses_in_block++;
 304                                 }
 305                         }
 306                 }
 307         }
 308
 309         return env;
 310 }
 311
 312 static void reg_pressure_block_free(void *block_env)
 313 {
 314         reg_pressure_selector_env_t *env = block_env;
 315         usage_stats_t *us;
 316
 317         for(us = env->root; us; us = us->next)
 318                 set_irn_link(us->irn, NULL);
 319
 320         obstack_free(&env->obst, NULL);
 321         del_nodeset(env->already_scheduled);
 322         free(env);
 323 }
 324
 325 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
 326 {
 327         int res = 0;
 328         if(get_irn_mode(irn) == mode_T) {
 329                 const ir_edge_t *edge;
 330
 331                 foreach_out_edge(irn, edge)
 332                         res += get_result_hops_sum(env, get_edge_src_irn(edge));
 333         }
 334
 335         else if(mode_is_data(get_irn_mode(irn)))
 336                 res = compute_max_hops(env, irn);
 337
 338
 339         return res;
 340 }
 341
 342 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
 343 {
 344         int i, n;
 345         int sum = 0;
 346
 347         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 348                 ir_node *op = get_irn_n(irn, i);
 349
 350                 if(must_appear_in_schedule(env->main_env->vtab, env, op))
 351                         sum += compute_max_hops(env, op);
 352         }
 353
 354         sum += get_result_hops_sum(env, irn);
 355
 356         return sum;
 357 }
 358
 359 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set)
 360 {
 361         reg_pressure_selector_env_t *env = block_env;
 362         ir_node *irn, *res     = NULL;
 363         int curr_cost          = INT_MAX;
 364
 365         assert(nodeset_count(ready_set) > 0);
 366
 367         for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
 368                 /*
 369                         Ignore branch instructions for the time being.
 370                         They should only be scheduled if there is nothing else.
 371                 */
 372                 if (arch_irn_classify(env->main_env->arch_env, irn) != arch_irn_class_branch) {
 373                         int costs = reg_pr_costs(env, irn);
 374                         if (costs <= curr_cost) {
 375                                 res       = irn;
 376                                 curr_cost = costs;
 377                         }
 378                 }
 379         }
 380
 381         /*
 382                 There was no result so we only saw a branch.
 383                 Take it and finish.
 384         */
 385
 386         if(!res) {
 387                 res = nodeset_first(ready_set);
 388                 nodeset_break(ready_set);
 389
 390                 assert(res && "There must be a node scheduled.");
 391         }
 392
 393         nodeset_insert(env->already_scheduled, res);
 394         return res;
 395 }
 396
 397 /**
 398  * Environment for a block scheduler.
 399  */
 400 typedef struct _block_sched_env_t {
 401         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
 402         sched_timestep_t curr_time;                 /**< current time of the scheduler */
 403         nodeset *cands;                             /**< the set of candidates */
 404         ir_node *block;                             /**< the current block */
 405         sched_env_t *sched_env;                     /**< the scheduler environment */
 406         const list_sched_selector_t *selector;
 407         void *selector_block_env;
 408         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 409 } block_sched_env_t;
 410
 411 /**
 412  * Returns non-zero if the node is already scheduled
 413  */
 414 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
 415 {
 416         int idx = get_irn_idx(n);
 417
 418         assert(idx < ARR_LEN(env->sched_info));
 419         return env->sched_info[idx].already_sched;
 420 }
 421
 422 /**
 423  * Mark a node as already scheduled
 424  */
 425 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
 426 {
 427         int idx = get_irn_idx(n);
 428
 429         assert(idx < ARR_LEN(env->sched_info));
 430         env->sched_info[idx].already_sched = 1;
 431 }
 432
 433 /**
 434  * Returns non-zero if the node is a root node
 435  */
 436 static INLINE unsigned is_root_node(block_sched_env_t *env, ir_node *n)
 437 {
 438         int idx = get_irn_idx(n);
 439
 440         assert(idx < ARR_LEN(env->sched_info));
 441         return env->sched_info[idx].is_root;
 442 }
 443
 444 /**
 445  * Mark a node as roto node
 446  */
 447 static INLINE void mark_root_node(block_sched_env_t *env, ir_node *n)
 448 {
 449         int idx = get_irn_idx(n);
 450
 451         assert(idx < ARR_LEN(env->sched_info));
 452         env->sched_info[idx].is_root = 1;
 453 }
 454
 455 /**
 456  * Get the current delay.
 457  */
 458 static sched_timestep_t get_irn_delay(block_sched_env_t *env, ir_node *n) {
 459         int idx = get_irn_idx(n);
 460
 461         assert(idx < ARR_LEN(env->sched_info));
 462         return env->sched_info[idx].delay;
 463 }
 464
 465 /**
 466  * Set the current delay.
 467  */
 468 static void set_irn_delay(block_sched_env_t *env, ir_node *n, sched_timestep_t delay) {
 469         int idx = get_irn_idx(n);
 470
 471         assert(idx < ARR_LEN(env->sched_info));
 472         env->sched_info[idx].delay = delay;
 473 }
 474
 475 /**
 476  * Get the current etime.
 477  */
 478 static sched_timestep_t get_irn_etime(block_sched_env_t *env, ir_node *n) {
 479         int idx = get_irn_idx(n);
 480
 481         assert(idx < ARR_LEN(env->sched_info));
 482         return env->sched_info[idx].etime;
 483 }
 484
 485 /**
 486  * Set the current etime.
 487  */
 488 static void set_irn_etime(block_sched_env_t *env, ir_node *n, sched_timestep_t etime) {
 489         int idx = get_irn_idx(n);
 490
 491         assert(idx < ARR_LEN(env->sched_info));
 492         env->sched_info[idx].etime = etime;
 493 }
 494
 495 /**
 496  * returns the exec-time for node n.
 497  */
 498 static sched_timestep_t exectime(sched_env_t *env, ir_node *n) {
 499   if (be_is_Keep(n) || is_Proj(n))
 500     return 0;
 501         if (env->selector->exectime)
 502                 return env->selector->exectime(env->selector_env, n);
 503         return 1;
 504 }
 505
 506 /**
 507  * Calculates the latency for between two ops
 508  */
 509 static sched_timestep_t latency(sched_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
 510         /* a Keep hides a root */
 511   if (be_is_Keep(curr))
 512                 return exectime(env, pred);
 513
 514         /* Proj's are executed immediately */
 515         if (is_Proj(curr))
 516     return 0;
 517
 518         /* predecessors Proj's must be skipped */
 519   if (is_Proj(pred))
 520     pred = get_Proj_pred(pred);
 521
 522         if (env->selector->latency)
 523                 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
 524         return 1;
 525 }
 526
 527 /**
 528  * Try to put a node in the ready set.
 529  * @param env   The block scheduler environment.
 530  * @param pred  The previous scheduled node.
 531  * @param irn   The node to make ready.
 532  * @return 1, if the node could be made ready, 0 else.
 533  */
 534 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 535 {
 536     int i, n;
 537                 sched_timestep_t etime_p, etime;
 538
 539     /* Blocks cannot be scheduled. */
 540     if (is_Block(irn))
 541         return 0;
 542
 543     /*
 544      * Check, if the given ir node is in a different block as the
 545      * currently scheduled one. If that is so, don't make the node ready.
 546      */
 547     if (env->block != get_nodes_block(irn))
 548         return 0;
 549
 550     for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 551         ir_node *op = get_irn_n(irn, i);
 552
 553         /* if irn is an End we have keep-alives and op might be a block, skip that */
 554         if (is_Block(op)) {
 555           assert(get_irn_op(irn) == op_End);
 556           continue;
 557         }
 558
 559         /* If the operand is local to the scheduled block and not yet
 560          * scheduled, this nodes cannot be made ready, so exit. */
 561         if (!is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 562             return 0;
 563     }
 564
 565     nodeset_insert(env->cands, irn);
 566
 567                 /* calculate the etime of this node */
 568                 etime = env->curr_time;
 569                 if (pred) {
 570                         etime_p  = get_irn_etime(env, pred);
 571                         etime   += latency(env->sched_env, pred, 1, irn, 0);
 572
 573                         etime = etime_p > etime ? etime_p : etime;
 574                 }
 575
 576                 set_irn_etime(env, irn, etime);
 577
 578     DB((env->dbg, LEVEL_2, "\tmaking ready: %+F etime %u\n", irn, etime));
 579
 580     return 1;
 581 }
 582
 583 /**
 584  * Try, to make all users of a node ready.
 585  * In fact, a usage node can only be made ready, if all its operands
 586  * have already been scheduled yet. This is checked my make_ready().
 587  * @param env The block schedule environment.
 588  * @param irn The node, which usages (successors) are to be made ready.
 589  */
 590 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
 591 {
 592         const ir_edge_t *edge;
 593
 594         foreach_out_edge(irn, edge) {
 595                 ir_node *user = edge->src;
 596                 if(!is_Phi(user))
 597                         make_ready(env, irn, user);
 598         }
 599 }
 600
 601 /**
 602  * Compare to nodes using pointer equality.
 603  * @param p1 Node one.
 604  * @param p2 Node two.
 605  * @return 0 if they are identical.
 606  */
 607 static int node_cmp_func(const void *p1, const void *p2)
 608 {
 609     return p1 != p2;
 610 }
 611
 612 /**
 613  * Append an instruction to a schedule.
 614  * @param env The block scheduling environment.
 615  * @param irn The node to add to the schedule.
 616  * @return    The given node.
 617  */
 618 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
 619 {
 620     /* If the node consumes/produces data, it is appended to the schedule
 621      * list, otherwise, it is not put into the list */
 622     if(must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
 623         sched_info_t *info = get_irn_sched_info(irn);
 624         INIT_LIST_HEAD(&info->list);
 625         info->scheduled = 1;
 626         sched_add_before(env->block, irn);
 627
 628         DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
 629     }
 630
 631     /* Insert the node in the set of all already scheduled nodes. */
 632     mark_already_scheduled(env, irn);
 633
 634     /* Remove the node from the ready set */
 635     if(nodeset_find(env->cands, irn))
 636         nodeset_remove(env->cands, irn);
 637
 638     return irn;
 639 }
 640
 641 /**
 642  * Add the proj nodes of a tuple-mode irn to the schedule immediately
 643  * after the tuple-moded irn. By pinning the projs after the irn, no
 644  * other nodes can create a new lifetime between the tuple-moded irn and
 645  * one of its projs. This should render a realistic image of a
 646  * tuple-moded irn, which in fact models a node which defines multiple
 647  * values.
 648  *
 649  * @param irn The tuple-moded irn.
 650  */
 651 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
 652 {
 653         const ir_edge_t *edge;
 654
 655         assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
 656
 657         if(is_Bad(irn))
 658                 return;
 659
 660         foreach_out_edge(irn, edge) {
 661                 ir_node *out = edge->src;
 662
 663                 assert(is_Proj(out) && "successor of a modeT node must be a proj");
 664
 665                 if (get_irn_mode(out) == mode_T)
 666                         add_tuple_projs(env, out);
 667                 else {
 668                         add_to_sched(env, out);
 669                         make_users_ready(env, out);
 670                 }
 671         }
 672 }
 673
 674 /**
 675  * Execute the heuristic function,
 676  */
 677 static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
 678 {
 679         ir_node *irn;
 680
 681         for (irn = nodeset_first(ns); irn; irn = nodeset_next(ns)) {
 682                 if (be_is_Keep(irn)) {
 683                         nodeset_break(ns);
 684                         return irn;
 685                 }
 686         }
 687
 688         return be->selector->select(be->selector_block_env, ns);
 689 }
 690
 691 /**
 692  * Returns non-zero if root is a root in the block block.
 693  */
 694 static int is_root(ir_node *root, ir_node *block) {
 695         const ir_edge_t *edge;
 696
 697         foreach_out_edge(root, edge) {
 698                 ir_node *succ = get_edge_src_irn(edge);
 699
 700                 if (is_Block(succ))
 701                         continue;
 702                 /* Phi nodes are always in "another block */
 703                 if (is_Phi(succ))
 704                         continue;
 705                 if (get_nodes_block(succ) == block)
 706                         return 0;
 707         }
 708         return 1;
 709 }
 710
 711 /* we need a special mark */
 712 static char _mark;
 713 #define MARK    &_mark
 714
 715 /**
 716  * descent into a dag and create a pre-order list.
 717  */
 718 static void descent(ir_node *root, ir_node *block, ir_node **list) {
 719         int i;
 720
 721         if (! is_Phi(root)) {
 722                 /* Phi nodes always leave the block */
 723                 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
 724                         ir_node *pred = get_irn_n(root, i);
 725
 726                         /* Blocks may happen as predecessors of End nodes */
 727                         if (is_Block(pred))
 728                                 continue;
 729
 730                         /* already seen nodes are not marked */
 731                         if (get_irn_link(pred) != MARK)
 732                                 continue;
 733
 734                         /* don't leave our block */
 735                         if (get_nodes_block(pred) != block)
 736                                 continue;
 737
 738                         descent(pred, block, list);
 739                 }
 740         }
 741         set_irn_link(root, *list);
 742         *list = root;
 743 }
 744
 745 /**
 746  * Perform list scheduling on a block.
 747  *
 748  * Note, that the caller must compute a linked list of nodes in the block
 749  * using the link field before calling this function.
 750  *
 751  * Also the outs must have been computed.
 752  *
 753  * @param block The block node.
 754  * @param env Scheduling environment.
 755  */
 756 static void list_sched_block(ir_node *block, void *env_ptr)
 757 {
 758         sched_env_t *env                      = env_ptr;
 759         const list_sched_selector_t *selector = env->selector;
 760         ir_node *start_node                   = get_irg_start(get_irn_irg(block));
 761         sched_info_t *info                    = get_irn_sched_info(block);
 762
 763         block_sched_env_t be;
 764         const ir_edge_t *edge;
 765         ir_node *irn;
 766         int j, m;
 767
 768         ir_node *root = NULL, *preord = NULL;
 769         ir_node *curr;
 770
 771         /* Initialize the block's list head that will hold the schedule. */
 772         INIT_LIST_HEAD(&info->list);
 773
 774         /* Initialize the block scheduling environment */
 775         be.sched_info        = env->sched_info;
 776         be.block             = block;
 777         be.curr_time         = 0;
 778         be.cands             = new_nodeset(get_irn_n_edges(block));
 779         be.selector          = selector;
 780         be.sched_env         = env;
 781         FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
 782
 783 //      firm_dbg_set_mask(be.dbg, SET_LEVEL_3);
 784
 785         if (selector->init_block)
 786                 be.selector_block_env = selector->init_block(env->selector_env, block);
 787
 788         DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
 789
 790         /* First step: Find the root set. */
 791         foreach_out_edge(block, edge) {
 792                 ir_node *succ = get_edge_src_irn(edge);
 793
 794                 if (is_root(succ, block)) {
 795                         mark_root_node(&be, succ);
 796                         set_irn_link(succ, root);
 797                         root = succ;
 798                 }
 799                 else
 800                         set_irn_link(succ, MARK);
 801         }
 802
 803         /* Second step: calculate the pre-order list. */
 804         preord = NULL;
 805         for (curr = root; curr; curr = irn) {
 806                 irn = get_irn_link(curr);
 807                 descent(curr, block, &preord);
 808         }
 809         root = preord;
 810
 811         /* Third step: calculate the Delay. Note that our
 812          * list is now in pre-order, starting at root
 813          */
 814         for (curr = root; curr; curr = get_irn_link(curr)) {
 815                 sched_timestep_t d;
 816
 817                 if (arch_irn_classify(env->arch_env, curr) == arch_irn_class_branch) {
 818                         /* assure, that branches can be executed last */
 819                         d = 0;
 820                 }
 821                 else {
 822                         if (is_root_node(&be, curr))
 823                                 d = exectime(env, curr);
 824                         else {
 825                                 d = 0;
 826                                 foreach_out_edge(curr, edge) {
 827                                         ir_node *n = get_edge_src_irn(edge);
 828
 829                                         if (get_nodes_block(n) == block) {
 830                                                 sched_timestep_t ld;
 831
 832                                                 ld = latency(env, curr, 1, n, 0) + get_irn_delay(&be, n);
 833                                                 d = ld > d ? ld : d;
 834                                         }
 835                                 }
 836                         }
 837                 }
 838                 set_irn_delay(&be, curr, d);
 839                 DB((be.dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
 840
 841                 /* set the etime of all nodes to 0 */
 842                 set_irn_etime(&be, curr, 0);
 843         }
 844
 845
 846         /* Then one can add all nodes are ready to the set. */
 847         foreach_out_edge(block, edge) {
 848                 ir_node *irn = get_edge_src_irn(edge);
 849
 850                 /* Skip the end node because of keepalive edges. */
 851                 if (get_irn_opcode(irn) == iro_End)
 852                         continue;
 853
 854                 if (is_Phi(irn)) {
 855                         /* Phi functions are scheduled immediately, since they only transfer
 856                          * data flow from the predecessors to this block. */
 857
 858                         /* Increase the time step. */
 859                         be.curr_time += get_irn_etime(&be, irn);
 860                         add_to_sched(&be, irn);
 861                         make_users_ready(&be, irn);
 862                 }
 863                 else if (irn == start_node) {
 864                         /* The start block will be scheduled as the first node */
 865                         be.curr_time += get_irn_etime(&be, irn);
 866
 867                         add_to_sched(&be, irn);
 868                         add_tuple_projs(&be, irn);
 869                 }
 870                 else {
 871                         /* Other nodes must have all operands in other blocks to be made
 872                          * ready */
 873                         int ready = 1;
 874
 875                         /* Check, if the operands of a node are not local to this block */
 876                         for (j = 0, m = get_irn_arity(irn); j < m; ++j) {
 877                                 ir_node *operand = get_irn_n(irn, j);
 878
 879                                 if (get_nodes_block(operand) == block) {
 880                                         ready = 0;
 881                                         break;
 882                                 }
 883                         }
 884
 885                         /* Make the node ready, if all operands live in a foreign block */
 886                         if (ready) {
 887                                 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
 888                                 make_ready(&be, NULL, irn);
 889                         }
 890                 }
 891         }
 892
 893         while (nodeset_count(be.cands) > 0) {
 894                 nodeset *mcands;                            /**< the set of candidates with maximum delay time */
 895                 nodeset *ecands;                            /**< the set of nodes in mcands whose etime <= curr_time  */
 896                 sched_timestep_t max_delay = 0;
 897
 898                 /* collect statistics about amount of ready nodes */
 899                 be_do_stat_sched_ready(block, be.cands);
 900
 901                 /* calculate the max delay of all candidates */
 902                 foreach_nodeset(be.cands, irn) {
 903                         sched_timestep_t d = get_irn_delay(&be, irn);
 904
 905                         max_delay = d > max_delay ? d : max_delay;
 906                 }
 907                 mcands = new_nodeset(8);
 908                 ecands = new_nodeset(8);
 909
 910                 /* calculate mcands and ecands */
 911                 foreach_nodeset(be.cands, irn) {
 912       if (be_is_Keep(irn)) {
 913         nodeset_break(be.cands);
 914         break;
 915       }
 916                         if (get_irn_delay(&be, irn) == max_delay) {
 917                                 nodeset_insert(mcands, irn);
 918                                 if (get_irn_etime(&be, irn) <= be.curr_time)
 919                                         nodeset_insert(ecands, irn);
 920                         }
 921                 }
 922
 923     if (irn) {
 924       /* Keeps must be immediately scheduled */
 925     }
 926     else {
 927                   DB((be.dbg, LEVEL_2, "\tbe.curr_time = %u\n", be.curr_time));
 928
 929                   /* select a node to be scheduled and check if it was ready */
 930                   if (nodeset_count(mcands) == 1) {
 931                           DB((be.dbg, LEVEL_3, "\tmcand = 1, max_delay = %u\n", max_delay));
 932                           irn = nodeset_first(mcands);
 933                   }
 934                   else {
 935                           int cnt = nodeset_count(ecands);
 936                           if (cnt == 1) {
 937                                         arch_irn_class_t irn_class;
 938
 939                                   irn = nodeset_first(ecands);
 940                                         irn_class = arch_irn_classify(env->arch_env, irn);
 941
 942                                         if (irn_class == arch_irn_class_branch) {
 943                                                 /* BEWARE: don't select a JUMP if others are still possible */
 944                                                 goto force_mcands;
 945                                         }
 946                                   DB((be.dbg, LEVEL_3, "\tecand = 1, max_delay = %u\n", max_delay));
 947                           }
 948                           else if (cnt > 1) {
 949                                   DB((be.dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
 950                                   irn = select_node_heuristic(&be, ecands);
 951                           }
 952                           else {
 953 force_mcands:
 954                                   DB((be.dbg, LEVEL_3, "\tmcand = %d\n", nodeset_count(mcands)));
 955                                   irn = select_node_heuristic(&be, mcands);
 956                           }
 957                   }
 958     }
 959                 del_nodeset(mcands);
 960                 del_nodeset(ecands);
 961
 962                 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 963
 964                 /* Increase the time step. */
 965                 be.curr_time += exectime(env, irn);
 966
 967                 /* Add the node to the schedule. */
 968                 add_to_sched(&be, irn);
 969
 970                 if (get_irn_mode(irn) == mode_T)
 971                         add_tuple_projs(&be, irn);
 972                 else
 973                         make_users_ready(&be, irn);
 974
 975                 /* remove the scheduled node from the ready list. */
 976                 if (nodeset_find(be.cands, irn))
 977                         nodeset_remove(be.cands, irn);
 978         }
 979
 980         if (selector->finish_block)
 981                 selector->finish_block(be.selector_block_env);
 982
 983         del_nodeset(be.cands);
 984 }
 985
 986 static const list_sched_selector_t reg_pressure_selector_struct = {
 987         reg_pressure_graph_init,
 988         reg_pressure_block_init,
 989         reg_pressure_select,
 990         NULL,                    /* to_appear_in_schedule */
 991         NULL,                    /* exectime */
 992         NULL,                    /* latency */
 993         reg_pressure_block_free,
 994         free
 995 };
 996
 997 const list_sched_selector_t *reg_pressure_selector = &reg_pressure_selector_struct;
 998
 999 /* List schedule a graph. */
1000 void list_sched(const be_irg_t *birg, int enable_mris)
1001 {
1002         const arch_env_t *arch_env = birg->main_env->arch_env;
1003         ir_graph *irg              = birg->irg;
1004
1005         int num_nodes;
1006         sched_env_t env;
1007         mris_env_t *mris;
1008
1009         /* Assure, that the out edges are computed */
1010         edges_assure(irg);
1011
1012         if(enable_mris)
1013                 mris = be_sched_mris_preprocess(birg);
1014
1015         num_nodes = get_irg_last_idx(irg);
1016
1017         memset(&env, 0, sizeof(env));
1018         env.selector   = arch_env->isa->impl->get_list_sched_selector(arch_env->isa);
1019         env.arch_env   = arch_env;
1020         env.irg        = irg;
1021         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
1022
1023         memset(env.sched_info, 0, num_nodes * sizeof(*env.sched_info));
1024
1025         if (env.selector->init_graph)
1026                 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
1027
1028         /* Schedule each single block. */
1029         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
1030
1031         if (env.selector->finish_graph)
1032                 env.selector->finish_graph(env.selector_env);
1033
1034         if(enable_mris)
1035                 be_sched_mris_free(mris);
1036
1037         DEL_ARR_F(env.sched_info);
1038 }