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