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
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #include <stdio.h>
  14 #include <stdarg.h>
  15 #include <string.h>
  16 #include <limits.h>
  17
  18 #include "benode_t.h"
  19 #include "be_t.h"
  20
  21 #include "obst.h"
  22 #include "list.h"
  23 #include "iterator.h"
  24
  25 #include "iredges_t.h"
  26 #include "irgwalk.h"
  27 #include "irnode_t.h"
  28 #include "irmode_t.h"
  29 #include "irdump.h"
  30 #include "irprintf_t.h"
  31 #include "array.h"
  32 #include "debug.h"
  33 #include "irtools.h"
  34
  35 #include "besched_t.h"
  36 #include "beutil.h"
  37 #include "belive_t.h"
  38 #include "belistsched.h"
  39 #include "beschedmris.h"
  40 #include "bearch.h"
  41 #include "bestat.h"
  42
  43 /**
  44  * All scheduling info needed per node.
  45  */
  46 typedef struct _sched_irn_t {
  47         sched_timestep_t delay;      /**< The delay for this node if already calculated, else 0. */
  48         sched_timestep_t etime;      /**< The earliest time of this node. */
  49         unsigned num_user;           /**< The number real users (mode datab) of this node */
  50         unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
  51         int      reg_diff;           /**< The difference of num(out registers) - num(in registers) */
  52         int      preorder;           /**< The pre-order position */
  53         unsigned already_sched : 1;  /**< Set if this node is already scheduled */
  54         unsigned is_root       : 1;  /**< is a root node of a block */
  55 } sched_irn_t;
  56
  57 /**
  58  * Scheduling environment for the whole graph.
  59  */
  60 typedef struct _sched_env_t {
  61         sched_irn_t *sched_info;                    /**< scheduling info per node */
  62         const list_sched_selector_t *selector;      /**< The node selector. */
  63         const arch_env_t *arch_env;                 /**< The architecture environment. */
  64         const ir_graph *irg;                        /**< The graph to schedule. */
  65         void *selector_env;                         /**< A pointer to give to the selector. */
  66         unsigned use_heuristic : 1;                 /**< Use internal heuristic or backend selector */
  67 } sched_env_t;
  68
  69 #if 0
  70 /*
  71  * Ugly global variable for the compare function
  72  * since qsort(3) does not pass an extra pointer.
  73  */
  74 static ir_node *curr_bl = NULL;
  75
  76 static int cmp_usage(const void *a, const void *b)
  77 {
  78         struct trivial_sched_env *env;
  79         const ir_node *p = a;
  80         const ir_node *q = b;
  81         int res = 0;
  82
  83         res = is_live_end(env->curr_bl, a) - is_live_end(env->curr_bl, b);
  84
  85         /*
  86          * One of them is live at the end of the block.
  87          * Then, that one shall be scheduled at after the other
  88          */
  89         if(res != 0)
  90                 return res;
  91
  92
  93         return res;
  94 }
  95 #endif
  96
  97 /**
  98  * The trivial selector:
  99  * Just assure that branches are executed last, otherwise select
 100  * the first node ready.
 101  */
 102 static ir_node *trivial_select(void *block_env, nodeset *ready_set)
 103 {
 104         const arch_env_t *arch_env = block_env;
 105         ir_node *irn = NULL;
 106
 107         /* assure that branches and constants are executed last */
 108         for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
 109                 if (! arch_irn_class_is(arch_env, irn, branch)) {
 110                         nodeset_break(ready_set);
 111                         return irn;
 112                 }
 113         }
 114
 115
 116         /* at last: schedule branches */
 117         irn = nodeset_first(ready_set);
 118         nodeset_break(ready_set);
 119
 120         return irn;
 121 }
 122
 123 static void *trivial_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 124 {
 125         return (void *) arch_env;
 126 }
 127
 128 static void *trivial_init_block(void *graph_env, ir_node *bl)
 129 {
 130         return graph_env;
 131 }
 132
 133 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
 134 {
 135         int res = -1;
 136
 137         if(sel->to_appear_in_schedule)
 138                 res = sel->to_appear_in_schedule(block_env, irn);
 139
 140         return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_RegParams(irn));
 141 }
 142
 143 static const list_sched_selector_t trivial_selector_struct = {
 144         trivial_init_graph,
 145         trivial_init_block,
 146         trivial_select,
 147         NULL,                /* to_appear_in_schedule */
 148         NULL,                /* exectime */
 149         NULL,                /* latency */
 150         NULL,                /* finish_block */
 151         NULL                 /* finish_graph */
 152 };
 153
 154 const list_sched_selector_t *trivial_selector = &trivial_selector_struct;
 155
 156 typedef struct _usage_stats_t {
 157         ir_node *irn;
 158         struct _usage_stats_t *next;
 159         int max_hops;
 160         int uses_in_block;      /**< Number of uses inside the current block. */
 161         int already_consumed;   /**< Number of insns using this value already
 162                                                           scheduled. */
 163 } usage_stats_t;
 164
 165 typedef struct {
 166         const list_sched_selector_t *vtab;
 167         const arch_env_t *arch_env;
 168 } reg_pressure_main_env_t;
 169
 170 typedef struct {
 171         struct obstack obst;
 172         const reg_pressure_main_env_t *main_env;
 173         usage_stats_t *root;
 174         nodeset *already_scheduled;
 175 } reg_pressure_selector_env_t;
 176
 177 static INLINE usage_stats_t *get_or_set_usage_stats(reg_pressure_selector_env_t *env, ir_node *irn)
 178 {
 179         usage_stats_t *us = get_irn_link(irn);
 180
 181         if(!us) {
 182                 us                   = obstack_alloc(&env->obst, sizeof(us[0]));
 183                 us->irn              = irn;
 184                 us->already_consumed = 0;
 185                 us->max_hops         = INT_MAX;
 186                 us->next             = env->root;
 187                 env->root            = us;
 188                 set_irn_link(irn, us);
 189         }
 190
 191         return us;
 192 }
 193
 194 static INLINE usage_stats_t *get_usage_stats(ir_node *irn)
 195 {
 196         usage_stats_t *us = get_irn_link(irn);
 197         assert(us && "This node must have usage stats");
 198         return us;
 199 }
 200
 201 static int max_hops_walker(reg_pressure_selector_env_t *env, ir_node *irn, ir_node *curr_bl, int depth, unsigned visited_nr)
 202 {
 203         ir_node *bl = get_nodes_block(irn);
 204         /*
 205          * If the reached node is not in the block desired,
 206          * return the value passed for this situation.
 207          */
 208         if(get_nodes_block(irn) != bl)
 209                 return block_dominates(bl, curr_bl) ? 0 : INT_MAX;
 210
 211         /*
 212          * If the node is in the current block but not
 213          * yet scheduled, we keep on searching from that node.
 214          */
 215         if(!nodeset_find(env->already_scheduled, irn)) {
 216                 int i, n;
 217                 int res = 0;
 218                 for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 219                         ir_node *operand = get_irn_n(irn, i);
 220
 221                         if(get_irn_visited(operand) < visited_nr) {
 222                                 int tmp;
 223
 224                                 set_irn_visited(operand, visited_nr);
 225                                 tmp = max_hops_walker(env, operand, bl, depth + 1, visited_nr);
 226                                 res = MAX(tmp, res);
 227                         }
 228                 }
 229
 230                 return res;
 231         }
 232
 233         /*
 234          * If the node is in the current block and scheduled, return
 235          * the depth which indicates the number of steps to the
 236          * region of scheduled nodes.
 237          */
 238         return depth;
 239 }
 240
 241 static int compute_max_hops(reg_pressure_selector_env_t *env, ir_node *irn)
 242 {
 243         ir_node *bl   = get_nodes_block(irn);
 244         ir_graph *irg = get_irn_irg(bl);
 245         int res       = 0;
 246
 247         const ir_edge_t *edge;
 248
 249         foreach_out_edge(irn, edge) {
 250                 ir_node *user       = get_edge_src_irn(edge);
 251                 unsigned visited_nr = get_irg_visited(irg) + 1;
 252                 int max_hops;
 253
 254                 set_irg_visited(irg, visited_nr);
 255                 max_hops = max_hops_walker(env, user, irn, 0, visited_nr);
 256                 res      = MAX(res, max_hops);
 257         }
 258
 259         return res;
 260 }
 261
 262 static void *reg_pressure_graph_init(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 263 {
 264         reg_pressure_main_env_t *main_env = xmalloc(sizeof(main_env[0]));
 265
 266         main_env->arch_env = arch_env;
 267         main_env->vtab     = vtab;
 268         irg_walk_graph(irg, firm_clear_link, NULL, NULL);
 269
 270         return main_env;
 271 }
 272
 273 static void *reg_pressure_block_init(void *graph_env, ir_node *bl)
 274 {
 275         ir_node *irn;
 276         reg_pressure_selector_env_t *env  = xmalloc(sizeof(env[0]));
 277
 278         obstack_init(&env->obst);
 279         env->already_scheduled = new_nodeset(32);
 280         env->root              = NULL;
 281         env->main_env          = graph_env;
 282
 283         /*
 284          * Collect usage statistics.
 285          */
 286         sched_foreach(bl, irn) {
 287                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 288                         int i, n;
 289
 290                         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 291                                 //ir_node *op = get_irn_n(irn, i);
 292                                 if(must_appear_in_schedule(env->main_env->vtab, env, irn)) {
 293                                         usage_stats_t *us = get_or_set_usage_stats(env, irn);
 294 #if 0 /* Liveness is not computed here! */
 295                                         if(is_live_end(bl, op))
 296                                                 us->uses_in_block = 99999;
 297                                         else
 298 #endif
 299                                                 us->uses_in_block++;
 300                                 }
 301                         }
 302                 }
 303         }
 304
 305         return env;
 306 }
 307
 308 static void reg_pressure_block_free(void *block_env)
 309 {
 310         reg_pressure_selector_env_t *env = block_env;
 311         usage_stats_t *us;
 312
 313         for(us = env->root; us; us = us->next)
 314                 set_irn_link(us->irn, NULL);
 315
 316         obstack_free(&env->obst, NULL);
 317         del_nodeset(env->already_scheduled);
 318         free(env);
 319 }
 320
 321 static int get_result_hops_sum(reg_pressure_selector_env_t *env, ir_node *irn)
 322 {
 323         int res = 0;
 324         if(get_irn_mode(irn) == mode_T) {
 325                 const ir_edge_t *edge;
 326
 327                 foreach_out_edge(irn, edge)
 328                         res += get_result_hops_sum(env, get_edge_src_irn(edge));
 329         }
 330
 331         else if(mode_is_data(get_irn_mode(irn)))
 332                 res = compute_max_hops(env, irn);
 333
 334
 335         return res;
 336 }
 337
 338 static INLINE int reg_pr_costs(reg_pressure_selector_env_t *env, ir_node *irn)
 339 {
 340         int i, n;
 341         int sum = 0;
 342
 343         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 344                 ir_node *op = get_irn_n(irn, i);
 345
 346                 if(must_appear_in_schedule(env->main_env->vtab, env, op))
 347                         sum += compute_max_hops(env, op);
 348         }
 349
 350         sum += get_result_hops_sum(env, irn);
 351
 352         return sum;
 353 }
 354
 355 static ir_node *reg_pressure_select(void *block_env, nodeset *ready_set)
 356 {
 357         reg_pressure_selector_env_t *env = block_env;
 358         ir_node *irn, *res     = NULL;
 359         int curr_cost          = INT_MAX;
 360
 361         assert(nodeset_count(ready_set) > 0);
 362
 363         for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
 364                 /*
 365                         Ignore branch instructions for the time being.
 366                         They should only be scheduled if there is nothing else.
 367                 */
 368                 if (! arch_irn_class_is(env->main_env->arch_env, irn, branch)) {
 369                         int costs = reg_pr_costs(env, irn);
 370                         if (costs <= curr_cost) {
 371                                 res       = irn;
 372                                 curr_cost = costs;
 373                         }
 374                 }
 375         }
 376
 377         /*
 378                 There was no result so we only saw a branch.
 379                 Take it and finish.
 380         */
 381
 382         if(!res) {
 383                 res = nodeset_first(ready_set);
 384                 nodeset_break(ready_set);
 385
 386                 assert(res && "There must be a node scheduled.");
 387         }
 388
 389         nodeset_insert(env->already_scheduled, res);
 390         return res;
 391 }
 392
 393 /**
 394  * Environment for a block scheduler.
 395  */
 396 typedef struct _block_sched_env_t {
 397         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
 398         sched_timestep_t curr_time;                 /**< current time of the scheduler */
 399         nodeset *cands;                             /**< the set of candidates */
 400         ir_node *block;                             /**< the current block */
 401         sched_env_t *sched_env;                     /**< the scheduler environment */
 402         nodeset *live;                              /**< simple liveness during scheduling */
 403         const list_sched_selector_t *selector;
 404         void *selector_block_env;
 405         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 406 } block_sched_env_t;
 407
 408 /**
 409  * Returns non-zero if the node is already scheduled
 410  */
 411 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
 412 {
 413         int idx = get_irn_idx(n);
 414
 415         assert(idx < ARR_LEN(env->sched_info));
 416         return env->sched_info[idx].already_sched;
 417 }
 418
 419 /**
 420  * Mark a node as already scheduled
 421  */
 422 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
 423 {
 424         int idx = get_irn_idx(n);
 425
 426         assert(idx < ARR_LEN(env->sched_info));
 427         env->sched_info[idx].already_sched = 1;
 428 }
 429
 430 /**
 431  * Returns non-zero if the node is a root node
 432  */
 433 static INLINE unsigned is_root_node(block_sched_env_t *env, ir_node *n)
 434 {
 435         int idx = get_irn_idx(n);
 436
 437         assert(idx < ARR_LEN(env->sched_info));
 438         return env->sched_info[idx].is_root;
 439 }
 440
 441 /**
 442  * Mark a node as roto node
 443  */
 444 static INLINE void mark_root_node(block_sched_env_t *env, ir_node *n)
 445 {
 446         int idx = get_irn_idx(n);
 447
 448         assert(idx < ARR_LEN(env->sched_info));
 449         env->sched_info[idx].is_root = 1;
 450 }
 451
 452 /**
 453  * Get the current delay.
 454  */
 455 static INLINE sched_timestep_t get_irn_delay(block_sched_env_t *env, ir_node *n) {
 456         int idx = get_irn_idx(n);
 457
 458         assert(idx < ARR_LEN(env->sched_info));
 459         return env->sched_info[idx].delay;
 460 }
 461
 462 /**
 463  * Set the current delay.
 464  */
 465 static INLINE void set_irn_delay(block_sched_env_t *env, ir_node *n, sched_timestep_t delay) {
 466         int idx = get_irn_idx(n);
 467
 468         assert(idx < ARR_LEN(env->sched_info));
 469         env->sched_info[idx].delay = delay;
 470 }
 471
 472 /**
 473  * Get the current etime.
 474  */
 475 static INLINE sched_timestep_t get_irn_etime(block_sched_env_t *env, ir_node *n) {
 476         int idx = get_irn_idx(n);
 477
 478         assert(idx < ARR_LEN(env->sched_info));
 479         return env->sched_info[idx].etime;
 480 }
 481
 482 /**
 483  * Set the current etime.
 484  */
 485 static INLINE void set_irn_etime(block_sched_env_t *env, ir_node *n, sched_timestep_t etime) {
 486         int idx = get_irn_idx(n);
 487
 488         assert(idx < ARR_LEN(env->sched_info));
 489         env->sched_info[idx].etime = etime;
 490 }
 491
 492 /**
 493  * Get the number of users.
 494  */
 495 static INLINE unsigned get_irn_num_user(block_sched_env_t *env, ir_node *n) {
 496         int idx = get_irn_idx(n);
 497
 498         assert(idx < ARR_LEN(env->sched_info));
 499         return env->sched_info[idx].num_user;
 500 }
 501
 502 /**
 503  * Set the number of users.
 504  */
 505 static INLINE void set_irn_num_user(block_sched_env_t *env, ir_node *n, unsigned num_user) {
 506         int idx = get_irn_idx(n);
 507
 508         assert(idx < ARR_LEN(env->sched_info));
 509         env->sched_info[idx].num_user = num_user;
 510 }
 511
 512 /**
 513  * Get the register difference.
 514  */
 515 static INLINE int get_irn_reg_diff(block_sched_env_t *env, ir_node *n) {
 516         int idx = get_irn_idx(n);
 517
 518         assert(idx < ARR_LEN(env->sched_info));
 519         return env->sched_info[idx].reg_diff;
 520 }
 521
 522 /**
 523  * Set the register difference.
 524  */
 525 static INLINE void set_irn_reg_diff(block_sched_env_t *env, ir_node *n, int reg_diff) {
 526         int idx = get_irn_idx(n);
 527
 528         assert(idx < ARR_LEN(env->sched_info));
 529         env->sched_info[idx].reg_diff = reg_diff;
 530 }
 531
 532 /**
 533  * Get the pre-order position.
 534  */
 535 static INLINE int get_irn_preorder(block_sched_env_t *env, ir_node *n) {
 536         int idx = get_irn_idx(n);
 537
 538         assert(idx < ARR_LEN(env->sched_info));
 539         return env->sched_info[idx].preorder;
 540 }
 541
 542 /**
 543  * Set the pre-order position.
 544  */
 545 static INLINE void set_irn_preorder(block_sched_env_t *env, ir_node *n, int pos) {
 546         int idx = get_irn_idx(n);
 547
 548         assert(idx < ARR_LEN(env->sched_info));
 549         env->sched_info[idx].preorder = pos;
 550 }
 551
 552 /**
 553  * returns the exec-time for node n.
 554  */
 555 static sched_timestep_t exectime(sched_env_t *env, ir_node *n) {
 556   if (be_is_Keep(n) || is_Proj(n))
 557     return 0;
 558         if (env->selector->exectime)
 559                 return env->selector->exectime(env->selector_env, n);
 560         return 1;
 561 }
 562
 563 /**
 564  * Calculates the latency for between two ops
 565  */
 566 static sched_timestep_t latency(sched_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
 567         /* a Keep hides a root */
 568         if (be_is_Keep(curr))
 569                 return exectime(env, pred);
 570
 571         /* Proj's are executed immediately */
 572         if (is_Proj(curr))
 573                 return 0;
 574
 575         /* predecessors Proj's must be skipped */
 576         if (is_Proj(pred))
 577                 pred = get_Proj_pred(pred);
 578
 579         if (env->selector->latency)
 580                 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
 581         return 1;
 582 }
 583
 584 /**
 585  * Try to put a node in the ready set.
 586  * @param env   The block scheduler environment.
 587  * @param pred  The previous scheduled node.
 588  * @param irn   The node to make ready.
 589  * @return 1, if the node could be made ready, 0 else.
 590  */
 591 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 592 {
 593         int i, n;
 594         sched_timestep_t etime_p, etime;
 595
 596     /* Blocks cannot be scheduled. */
 597     if (is_Block(irn))
 598         return 0;
 599
 600     /*
 601      * Check, if the given ir node is in a different block as the
 602      * currently scheduled one. If that is so, don't make the node ready.
 603      */
 604     if (env->block != get_nodes_block(irn))
 605         return 0;
 606
 607     for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 608         ir_node *op = get_irn_n(irn, i);
 609
 610         /* if irn is an End we have keep-alives and op might be a block, skip that */
 611         if (is_Block(op)) {
 612           assert(get_irn_op(irn) == op_End);
 613           continue;
 614         }
 615
 616         /* If the operand is local to the scheduled block and not yet
 617          * scheduled, this nodes cannot be made ready, so exit. */
 618         if (!is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 619             return 0;
 620     }
 621
 622     nodeset_insert(env->cands, irn);
 623
 624         /* calculate the etime of this node */
 625         etime = env->curr_time;
 626         if (pred) {
 627                 etime_p  = get_irn_etime(env, pred);
 628                 etime   += latency(env->sched_env, pred, 1, irn, 0);
 629
 630                 etime = etime_p > etime ? etime_p : etime;
 631         }
 632
 633         set_irn_etime(env, irn, etime);
 634
 635     DB((env->dbg, LEVEL_2, "\tmaking ready: %+F etime %u\n", irn, etime));
 636
 637     return 1;
 638 }
 639
 640 /**
 641  * Try, to make all users of a node ready.
 642  * In fact, a usage node can only be made ready, if all its operands
 643  * have already been scheduled yet. This is checked my make_ready().
 644  * @param env The block schedule environment.
 645  * @param irn The node, which usages (successors) are to be made ready.
 646  */
 647 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
 648 {
 649         const ir_edge_t *edge;
 650
 651         foreach_out_edge(irn, edge) {
 652                 ir_node *user = edge->src;
 653                 if(!is_Phi(user))
 654                         make_ready(env, irn, user);
 655         }
 656 }
 657
 658 /**
 659  * Returns the number of not yet schedules users.
 660  */
 661 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
 662         int idx = get_irn_idx(n);
 663
 664         assert(idx < ARR_LEN(env->sched_info));
 665         return env->sched_info[idx].num_not_sched_user;
 666 }
 667
 668 /**
 669  * Sets the number of not yet schedules users.
 670  */
 671 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 672         int idx = get_irn_idx(n);
 673
 674         assert(idx < ARR_LEN(env->sched_info));
 675         env->sched_info[idx].num_not_sched_user = num;
 676 }
 677
 678 /**
 679  * Add @p num to the number of not yet schedules users and returns the result.
 680  */
 681 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 682         int idx = get_irn_idx(n);
 683
 684         assert(idx < ARR_LEN(env->sched_info));
 685         env->sched_info[idx].num_not_sched_user += num;
 686         return env->sched_info[idx].num_not_sched_user;
 687 }
 688
 689 /**
 690  * Returns the number of users of a node having mode datab.
 691  */
 692 static int get_num_successors(ir_node *irn) {
 693         int sum = 0;
 694         const ir_edge_t *edge;
 695
 696         if (get_irn_mode(irn) == mode_T) {
 697                 /* for mode_T nodes: count the users of all Projs */
 698                 foreach_out_edge(irn, edge) {
 699                         ir_node *proj = get_edge_src_irn(edge);
 700                         ir_mode *mode = get_irn_mode(proj);
 701
 702                         if (mode == mode_T)
 703                                 sum += get_num_successors(proj);
 704                         else if (mode_is_datab(mode))
 705                                 sum += get_irn_n_edges(proj);
 706                 }
 707         }
 708         else {
 709                 /* do not count keep-alive edges */
 710                 foreach_out_edge(irn, edge) {
 711                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 712                                 sum++;
 713                 }
 714         }
 715
 716         return sum;
 717 }
 718
 719 /**
 720  * Adds irn to @p live, updates all inputs that this user is scheduled
 721  * and counts all of it's non scheduled users.
 722  */
 723 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
 724         int i;
 725
 726         /* ignore Projs */
 727         if (is_Proj(irn))
 728                 return;
 729
 730         for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
 731                 ir_node *in = get_irn_n(irn, i);
 732
 733                 /* if in is a proj: update predecessor */
 734                 while (is_Proj(in))
 735                         in = get_Proj_pred(in);
 736
 737                 /* if in is still in the live set: reduce number of users by one */
 738                 if (nodeset_find(env->live, in)) {
 739                         if (add_irn_not_sched_user(env, in, -1) <= 0)
 740                                 nodeset_remove(env->live, in);
 741                 }
 742         }
 743
 744         /*
 745                 get_num_successors returns the number of all users. This includes
 746                 users in different blocks as well. As the each block is scheduled separately
 747                 the liveness info of those users will not be updated and so these
 748                 users will keep up the register pressure as it is desired.
 749         */
 750         i = get_num_successors(irn);
 751         if (i > 0) {
 752                 set_irn_not_sched_user(env, irn, i);
 753                 nodeset_insert(env->live, irn);
 754         }
 755 }
 756
 757 /**
 758  * Returns the current register pressure for the current block
 759  * while scheduling.
 760  * This is the number of already scheduled nodes having not yet
 761  * scheduled users.
 762  */
 763 static INLINE int get_cur_reg_pressure(block_sched_env_t *env) {
 764         /*
 765                 Nodes with all users scheduled are removed from live set,
 766                 so the number of nodes in this set represent the current
 767                 register pressure in this block.
 768         */
 769         return nodeset_count(env->live);
 770 }
 771
 772 /**
 773  * Append an instruction to a schedule.
 774  * @param env The block scheduling environment.
 775  * @param irn The node to add to the schedule.
 776  * @return    The given node.
 777  */
 778 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
 779 {
 780     /* If the node consumes/produces data, it is appended to the schedule
 781      * list, otherwise, it is not put into the list */
 782     if(must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
 783         sched_info_t *info = get_irn_sched_info(irn);
 784         INIT_LIST_HEAD(&info->list);
 785         info->scheduled = 1;
 786                 update_sched_liveness(env, irn);
 787         sched_add_before(env->block, irn);
 788
 789         DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
 790     }
 791
 792     /* Insert the node in the set of all already scheduled nodes. */
 793     mark_already_scheduled(env, irn);
 794
 795     /* Remove the node from the ready set */
 796     if(nodeset_find(env->cands, irn))
 797         nodeset_remove(env->cands, irn);
 798
 799     return irn;
 800 }
 801
 802 /**
 803  * Add the proj nodes of a tuple-mode irn to the schedule immediately
 804  * after the tuple-moded irn. By pinning the projs after the irn, no
 805  * other nodes can create a new lifetime between the tuple-moded irn and
 806  * one of its projs. This should render a realistic image of a
 807  * tuple-moded irn, which in fact models a node which defines multiple
 808  * values.
 809  *
 810  * @param irn The tuple-moded irn.
 811  */
 812 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
 813 {
 814         const ir_edge_t *edge;
 815
 816         assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
 817
 818         if(is_Bad(irn))
 819                 return;
 820
 821         foreach_out_edge(irn, edge) {
 822                 ir_node *out = edge->src;
 823
 824                 assert(is_Proj(out) && "successor of a modeT node must be a proj");
 825
 826                 if (get_irn_mode(out) == mode_T)
 827                         add_tuple_projs(env, out);
 828                 else {
 829                         add_to_sched(env, out);
 830                         make_users_ready(env, out);
 831                 }
 832         }
 833 }
 834
 835 /**
 836  * Returns the difference of regs_output - regs_input;
 837  */
 838 static int get_reg_difference(block_sched_env_t *be, ir_node *irn) {
 839         int num_out = 0;
 840         int num_in  = 0;
 841         int i;
 842
 843         if (get_irn_mode(irn) == mode_T) {
 844                 /* mode_T nodes: num out regs == num Projs with mode datab */
 845                 const ir_edge_t *edge;
 846                 foreach_out_edge(irn, edge) {
 847                         ir_node *proj = get_edge_src_irn(edge);
 848                         if (mode_is_datab(get_irn_mode(proj)))
 849                                 num_out++;
 850                 }
 851         }
 852         else
 853                 num_out = 1;
 854
 855         /* num in regs: number of ins with mode datab and not ignore */
 856         for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
 857                 ir_node *in = get_irn_n(irn, i);
 858                 if (mode_is_datab(get_irn_mode(in)) && ! arch_irn_is(be->sched_env->arch_env, irn, ignore))
 859                         num_in++;
 860         }
 861
 862         return num_out - num_in;
 863 }
 864
 865 /**
 866  * Execute the heuristic function,
 867  */
 868 static ir_node *select_node_heuristic(block_sched_env_t *be, nodeset *ns)
 869 {
 870         ir_node *irn, *cand = NULL;
 871
 872 /* prefer instructions which can be scheduled early */
 873 #define PRIO_TIME       16
 874 /* prefer instructions with lots of successors */
 875 #define PRIO_NUMSUCCS    4
 876 /* prefer instructions with long critical path */
 877 #define PRIO_LEVEL      12
 878 /* prefer instructions coming early in preorder */
 879 #define PRIO_PREORD      8
 880 /* weight of current register pressure */
 881 #define PRIO_CUR_PRESS  20
 882 /* weight of register pressure difference */
 883 #define PRIO_CHG_PRESS  14
 884
 885         /* schedule keeps as early as possible */
 886         foreach_nodeset(ns, irn) {
 887                 if (be_is_Keep(irn)) {
 888                         nodeset_break(ns);
 889                         return irn;
 890                 }
 891         }
 892
 893         if (be->sched_env->use_heuristic) {
 894                 int max_prio     = INT_MIN;
 895                 int cur_prio     = INT_MIN;
 896                 int cur_pressure = get_cur_reg_pressure(be);
 897
 898                 /* priority based selection, heuristic inspired by mueller diss */
 899                 foreach_nodeset(ns, irn) {
 900                         /* make sure that branches are scheduled last */
 901                         if (! arch_irn_class_is(be->sched_env->arch_env, irn, branch)) {
 902                                 cur_prio = (get_irn_delay(be, irn) << PRIO_LEVEL)
 903                                         + (get_irn_num_user(be, irn) << PRIO_NUMSUCCS)
 904                                         - (get_irn_etime(be, irn) << PRIO_TIME)
 905                                         - ((get_irn_reg_diff(be, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
 906                                         + (get_irn_preorder(be, irn) << PRIO_PREORD); /* high preorder means: early scheduled in pre-order list */
 907                                 if (cur_prio > max_prio) {
 908                                         cand     = irn;
 909                                         max_prio = cur_prio;
 910                                 }
 911                         }
 912                 }
 913
 914                 if (cand) {
 915                         DBG((be->dbg, LEVEL_4, "heuristic selected %+F:\n", cand));
 916                         DBG((be->dbg, LEVEL_4, "\tpriority: %d\n", cand));
 917                         DBG((be->dbg, LEVEL_4, "\tdelay:    %d (%d)\n", get_irn_delay(be, cand), get_irn_delay(be, cand) << PRIO_LEVEL));
 918                         DBG((be->dbg, LEVEL_4, "\t#user:    %d (%d)\n", get_irn_num_user(be, cand), get_irn_num_user(be, cand) << PRIO_NUMSUCCS));
 919                         DBG((be->dbg, LEVEL_4, "\tetime:    %d (%d)\n", get_irn_etime(be, cand), -(get_irn_etime(be, cand) << PRIO_TIME)));
 920                         DBG((be->dbg, LEVEL_4, "\tpreorder: %d (%d)\n", get_irn_preorder(be, cand), get_irn_preorder(be, cand) << PRIO_PREORD));
 921                         DBG((be->dbg, LEVEL_4, "\treg diff: %d (%d)\n", get_irn_reg_diff(be, cand), -(((get_irn_reg_diff(be, cand) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3)))));
 922                         DBG((be->dbg, LEVEL_4, "\tpressure: %d\n", cur_pressure));
 923                 }
 924                 else {
 925                         cand = nodeset_first(ns);
 926                 }
 927         }
 928         else {
 929                 /* use backend selector */
 930                 cand = be->selector->select(be->selector_block_env, ns);
 931         }
 932
 933         return cand;
 934 }
 935
 936 /**
 937  * Returns non-zero if root is a root in the block block.
 938  */
 939 static int is_root(ir_node *root, ir_node *block) {
 940         const ir_edge_t *edge;
 941
 942         foreach_out_edge(root, edge) {
 943                 ir_node *succ = get_edge_src_irn(edge);
 944
 945                 if (is_Block(succ))
 946                         continue;
 947                 /* Phi nodes are always in "another block */
 948                 if (is_Phi(succ))
 949                         continue;
 950                 if (get_nodes_block(succ) == block)
 951                         return 0;
 952         }
 953         return 1;
 954 }
 955
 956 /* we need a special mark */
 957 static char _mark;
 958 #define MARK    &_mark
 959
 960 static firm_dbg_module_t *xxxdbg;
 961
 962 /**
 963  * descent into a dag and create a pre-order list.
 964  */
 965 static void descent(ir_node *root, ir_node *block, ir_node **list, block_sched_env_t *env, int cur_depth) {
 966         int i;
 967
 968         cur_depth++;
 969
 970         if (! is_Phi(root)) {
 971                 /* Phi nodes always leave the block */
 972                 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
 973                         ir_node *pred = get_irn_n(root, i);
 974
 975                         DBG((xxxdbg, LEVEL_3, "   node %+F\n", pred));
 976                         /* Blocks may happen as predecessors of End nodes */
 977                         if (is_Block(pred))
 978                                 continue;
 979
 980                         /* already seen nodes are not marked */
 981                         if (get_irn_link(pred) != MARK)
 982                                 continue;
 983
 984                         /* don't leave our block */
 985                         if (get_nodes_block(pred) != block)
 986                                 continue;
 987
 988                         set_irn_link(pred, NULL);
 989                         set_irn_preorder(env, pred, cur_depth);
 990
 991                         descent(pred, block, list, env, cur_depth);
 992                 }
 993         }
 994         set_irn_link(root, *list);
 995         *list = root;
 996
 997         cur_depth--;
 998 }
 999
1000 /**
1001  * Perform list scheduling on a block.
1002  *
1003  * Note, that the caller must compute a linked list of nodes in the block
1004  * using the link field before calling this function.
1005  *
1006  * Also the outs must have been computed.
1007  *
1008  * @param block The block node.
1009  * @param env Scheduling environment.
1010  */
1011 static void list_sched_block(ir_node *block, void *env_ptr)
1012 {
1013         sched_env_t *env                      = env_ptr;
1014         const list_sched_selector_t *selector = env->selector;
1015         ir_node *start_node                   = get_irg_start(get_irn_irg(block));
1016         sched_info_t *info                    = get_irn_sched_info(block);
1017
1018         block_sched_env_t be;
1019         const ir_edge_t *edge;
1020         ir_node *irn;
1021         int j, m;
1022
1023         ir_node *root = NULL, *preord = NULL;
1024         ir_node *curr;
1025
1026         /* Initialize the block's list head that will hold the schedule. */
1027         INIT_LIST_HEAD(&info->list);
1028
1029         /* Initialize the block scheduling environment */
1030         be.sched_info        = env->sched_info;
1031         be.block             = block;
1032         be.curr_time         = 0;
1033         be.cands             = new_nodeset(get_irn_n_edges(block));
1034         be.live              = new_nodeset(get_irn_n_edges(block));
1035         be.selector          = selector;
1036         be.sched_env         = env;
1037         FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
1038         FIRM_DBG_REGISTER(xxxdbg, "firm.be.sched");
1039
1040         //      firm_dbg_set_mask(be.dbg, SET_LEVEL_3);
1041
1042         if (selector->init_block)
1043                 be.selector_block_env = selector->init_block(env->selector_env, block);
1044
1045         DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
1046
1047         /* First step: Find the root set. */
1048         foreach_out_edge(block, edge) {
1049                 ir_node *succ = get_edge_src_irn(edge);
1050
1051                 if (is_root(succ, block)) {
1052                         mark_root_node(&be, succ);
1053                         set_irn_link(succ, root);
1054                         root = succ;
1055                 }
1056                 else
1057                         set_irn_link(succ, MARK);
1058         }
1059
1060         /* Second step: calculate the pre-order list. */
1061         preord = NULL;
1062         for (curr = root; curr; curr = irn) {
1063                 irn = get_irn_link(curr);
1064                 DBG((be.dbg, LEVEL_2, "   DAG root %+F\n", curr));
1065                 descent(curr, block, &preord, &be, 0);
1066         }
1067         root = preord;
1068
1069         /* Third step: calculate the Delay. Note that our
1070         * list is now in pre-order, starting at root
1071         */
1072         for (curr = root; curr; curr = get_irn_link(curr)) {
1073                 sched_timestep_t d;
1074
1075                 if (arch_irn_class_is(env->arch_env, curr, branch)) {
1076                         /* assure, that branches can be executed last */
1077                         d = 0;
1078                 }
1079                 else {
1080                         if (is_root_node(&be, curr))
1081                                 d = exectime(env, curr);
1082                         else {
1083                                 d = 0;
1084                                 foreach_out_edge(curr, edge) {
1085                                         ir_node *n = get_edge_src_irn(edge);
1086
1087                                         if (get_nodes_block(n) == block) {
1088                                                 sched_timestep_t ld;
1089
1090                                                 ld = latency(env, curr, 1, n, 0) + get_irn_delay(&be, n);
1091                                                 d = ld > d ? ld : d;
1092                                         }
1093                                 }
1094                         }
1095                 }
1096                 set_irn_delay(&be, curr, d);
1097                 DB((be.dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
1098
1099                 /* set the etime of all nodes to 0 */
1100                 set_irn_etime(&be, curr, 0);
1101         }
1102
1103
1104         /* Then one can add all nodes are ready to the set. */
1105         foreach_out_edge(block, edge) {
1106                 ir_node *irn = get_edge_src_irn(edge);
1107
1108                 /* Skip the end node because of keepalive edges. */
1109                 if (get_irn_opcode(irn) == iro_End)
1110                         continue;
1111
1112                 if (is_Phi(irn)) {
1113                         /* Phi functions are scheduled immediately, since they only transfer
1114                         * data flow from the predecessors to this block. */
1115
1116                         /* Increase the time step. */
1117                         be.curr_time += get_irn_etime(&be, irn);
1118                         add_to_sched(&be, irn);
1119                         make_users_ready(&be, irn);
1120                 }
1121                 else if (irn == start_node) {
1122                         /* The start block will be scheduled as the first node */
1123                         be.curr_time += get_irn_etime(&be, irn);
1124
1125                         add_to_sched(&be, irn);
1126                         add_tuple_projs(&be, irn);
1127                 }
1128                 else {
1129                         /* Other nodes must have all operands in other blocks to be made
1130                         * ready */
1131                         int ready = 1;
1132
1133                         /* Check, if the operands of a node are not local to this block */
1134                         for (j = 0, m = get_irn_arity(irn); j < m; ++j) {
1135                                 ir_node *operand = get_irn_n(irn, j);
1136
1137                                 if (get_nodes_block(operand) == block) {
1138                                         ready = 0;
1139                                         break;
1140                                 }
1141                                 else {
1142                                         /* live in values increase register pressure */
1143                                         update_sched_liveness(&be, operand);
1144                                 }
1145                         }
1146
1147                         /* Make the node ready, if all operands live in a foreign block */
1148                         if (ready) {
1149                                 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
1150                                 make_ready(&be, NULL, irn);
1151                         }
1152
1153                         /* calculate number of users (needed for heuristic) */
1154                         set_irn_num_user(&be, irn, get_num_successors(irn));
1155
1156                         /* calculate register difference (needed for heuristic) */
1157                         set_irn_reg_diff(&be, irn, get_reg_difference(&be, irn));
1158                 }
1159         }
1160
1161         while (nodeset_count(be.cands) > 0) {
1162                 nodeset *mcands;                            /**< the set of candidates with maximum delay time */
1163                 nodeset *ecands;                            /**< the set of nodes in mcands whose etime <= curr_time  */
1164                 sched_timestep_t max_delay = 0;
1165
1166                 /* collect statistics about amount of ready nodes */
1167                 be_do_stat_sched_ready(block, be.cands);
1168
1169                 /* calculate the max delay of all candidates */
1170                 foreach_nodeset(be.cands, irn) {
1171                         sched_timestep_t d = get_irn_delay(&be, irn);
1172
1173                         max_delay = d > max_delay ? d : max_delay;
1174                 }
1175                 mcands = new_nodeset(8);
1176                 ecands = new_nodeset(8);
1177
1178                 /* calculate mcands and ecands */
1179                 foreach_nodeset(be.cands, irn) {
1180                         if (be_is_Keep(irn)) {
1181                                 nodeset_break(be.cands);
1182                                 break;
1183                         }
1184                         if (get_irn_delay(&be, irn) == max_delay) {
1185                                 nodeset_insert(mcands, irn);
1186                                 if (get_irn_etime(&be, irn) <= be.curr_time)
1187                                         nodeset_insert(ecands, irn);
1188                         }
1189                 }
1190
1191                 if (irn) {
1192                         /* Keeps must be immediately scheduled */
1193                 }
1194                 else {
1195                         DB((be.dbg, LEVEL_2, "\tbe.curr_time = %u\n", be.curr_time));
1196
1197                         /* select a node to be scheduled and check if it was ready */
1198                         if (nodeset_count(mcands) == 1) {
1199                                 irn = nodeset_first(mcands);
1200                                 DB((be.dbg, LEVEL_3, "\tirn = %+F, mcand = 1, max_delay = %u\n", irn, max_delay));
1201                         }
1202                         else {
1203                                 int cnt = nodeset_count(ecands);
1204                                 if (cnt == 1) {
1205                                         irn = nodeset_first(ecands);
1206
1207                                         if (arch_irn_class_is(env->arch_env, irn, branch)) {
1208                                                 /* BEWARE: don't select a JUMP if others are still possible */
1209                                                 goto force_mcands;
1210                                         }
1211                                         DB((be.dbg, LEVEL_3, "\tirn = %+F, ecand = 1, max_delay = %u\n", irn, max_delay));
1212                                 }
1213                                 else if (cnt > 1) {
1214                                         DB((be.dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
1215                                         irn = select_node_heuristic(&be, ecands);
1216                                 }
1217                                 else {
1218 force_mcands:
1219                                         DB((be.dbg, LEVEL_3, "\tmcand = %d\n", nodeset_count(mcands)));
1220                                         irn = select_node_heuristic(&be, mcands);
1221                                 }
1222                         }
1223                 }
1224                 del_nodeset(mcands);
1225                 del_nodeset(ecands);
1226
1227                 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
1228
1229                 /* Increase the time step. */
1230                 be.curr_time += exectime(env, irn);
1231
1232                 /* Add the node to the schedule. */
1233                 add_to_sched(&be, irn);
1234
1235                 if (get_irn_mode(irn) == mode_T)
1236                         add_tuple_projs(&be, irn);
1237                 else
1238                         make_users_ready(&be, irn);
1239
1240                 /* remove the scheduled node from the ready list. */
1241                 if (nodeset_find(be.cands, irn))
1242                         nodeset_remove(be.cands, irn);
1243         }
1244
1245         if (selector->finish_block)
1246                 selector->finish_block(be.selector_block_env);
1247
1248         del_nodeset(be.cands);
1249         del_nodeset(be.live);
1250 }
1251
1252 static const list_sched_selector_t reg_pressure_selector_struct = {
1253         reg_pressure_graph_init,
1254         reg_pressure_block_init,
1255         reg_pressure_select,
1256         NULL,                    /* to_appear_in_schedule */
1257         NULL,                    /* exectime */
1258         NULL,                    /* latency */
1259         reg_pressure_block_free,
1260         free
1261 };
1262
1263 const list_sched_selector_t *reg_pressure_selector = &reg_pressure_selector_struct;
1264
1265 /* List schedule a graph. */
1266 void list_sched(const be_irg_t *birg, be_options_t *be_opts)
1267 {
1268         const arch_env_t *arch_env = birg->main_env->arch_env;
1269         ir_graph *irg              = birg->irg;
1270
1271         int num_nodes;
1272         sched_env_t env;
1273         mris_env_t *mris;
1274
1275         /* Assure, that the out edges are computed */
1276         edges_assure(irg);
1277
1278         if(be_opts->mris)
1279                 mris = be_sched_mris_preprocess(birg);
1280
1281         num_nodes = get_irg_last_idx(irg);
1282
1283         memset(&env, 0, sizeof(env));
1284         env.selector      = arch_env->isa->impl->get_list_sched_selector(arch_env->isa);
1285         env.arch_env      = arch_env;
1286         env.irg           = irg;
1287         env.use_heuristic = be_opts->sched_select == BE_SCHED_SELECT_HEUR ? 1 : 0;
1288         env.sched_info    = NEW_ARR_F(sched_irn_t, num_nodes);
1289
1290         memset(env.sched_info, 0, num_nodes * sizeof(*env.sched_info));
1291
1292         if (env.selector->init_graph)
1293                 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
1294
1295         /* Schedule each single block. */
1296         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
1297
1298         if (env.selector->finish_graph)
1299                 env.selector->finish_graph(env.selector_env);
1300
1301         if(be_opts->mris)
1302                 be_sched_mris_free(mris);
1303
1304         DEL_ARR_F(env.sched_info);
1305 }