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

   1 /**
   2  * Implements a trace scheduler as presented in Muchnik[TM].
   3  * Originally implemented by Michael Beck.
   4  * @author Christian Wuerdig
   5  * @date   28.08.2006
   6  * @cvs-id $Id$
   7  */
   8 #ifdef HAVE_CONFIG_H
   9 #include "config.h"
  10 #endif
  11
  12 #include <stdlib.h>
  13
  14 #include "iredges_t.h"
  15
  16 #include "besched_t.h"
  17 #include "belistsched.h"
  18 #include "benode_t.h"
  19
  20 /* we need a special mark */
  21 static char _mark;
  22 #define MARK &_mark
  23
  24 typedef struct _trace_irn {
  25         sched_timestep_t delay;      /**< The delay for this node if already calculated, else 0. */
  26         sched_timestep_t etime;      /**< The earliest time of this node. */
  27         unsigned num_user;           /**< The number real users (mode datab) of this node */
  28         int      reg_diff;           /**< The difference of num(out registers) - num(in registers) */
  29         int      preorder;           /**< The pre-order position */
  30         unsigned critical_path_len;  /**< The weighted length of the longest critical path */
  31         unsigned is_root       : 1;  /**< is a root node of a block */
  32 } trace_irn_t;
  33
  34 typedef struct _trace_env {
  35         trace_irn_t      *sched_info;               /**< trace scheduling information about the nodes */
  36         const arch_env_t *arch_env;                 /**< the arch environment */
  37         sched_timestep_t curr_time;                 /**< current time of the scheduler */
  38         void             *selector_env;             /**< the backend selector environment */
  39         const list_sched_selector_t *selector;      /**< the actual backend selector */
  40         be_lv_t          *liveness;                 /**< The liveness for the irg */
  41         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  42 } trace_env_t;
  43
  44 /**
  45  * Returns a random node from a nodeset
  46  */
  47 static ir_node *get_nodeset_node(const ir_nodeset_t *nodeset)
  48 {
  49         ir_nodeset_iterator_t iter;
  50
  51         ir_nodeset_iterator_init(&iter, nodeset);
  52         return ir_nodeset_iterator_next(&iter);
  53 }
  54
  55 /**
  56  * Returns non-zero if the node is a root node
  57  */
  58 static INLINE unsigned is_root_node(trace_env_t *env, ir_node *n)
  59 {
  60         int idx = get_irn_idx(n);
  61
  62         assert(idx < ARR_LEN(env->sched_info));
  63         return env->sched_info[idx].is_root;
  64 }
  65
  66 /**
  67  * Mark a node as root node
  68  */
  69 static INLINE void mark_root_node(trace_env_t *env, ir_node *n)
  70 {
  71         int idx = get_irn_idx(n);
  72
  73         assert(idx < ARR_LEN(env->sched_info));
  74         env->sched_info[idx].is_root = 1;
  75 }
  76
  77 /**
  78  * Get the current delay.
  79  */
  80 static INLINE sched_timestep_t get_irn_delay(trace_env_t *env, ir_node *n) {
  81         int idx = get_irn_idx(n);
  82
  83         assert(idx < ARR_LEN(env->sched_info));
  84         return env->sched_info[idx].delay;
  85 }
  86
  87 /**
  88  * Set the current delay.
  89  */
  90 static INLINE void set_irn_delay(trace_env_t *env, ir_node *n, sched_timestep_t delay) {
  91         int idx = get_irn_idx(n);
  92
  93         assert(idx < ARR_LEN(env->sched_info));
  94         env->sched_info[idx].delay = delay;
  95 }
  96
  97 /**
  98  * Get the current etime.
  99  */
 100 static INLINE sched_timestep_t get_irn_etime(trace_env_t *env, ir_node *n) {
 101         int idx = get_irn_idx(n);
 102
 103         assert(idx < ARR_LEN(env->sched_info));
 104         return env->sched_info[idx].etime;
 105 }
 106
 107 /**
 108  * Set the current etime.
 109  */
 110 static INLINE void set_irn_etime(trace_env_t *env, ir_node *n, sched_timestep_t etime) {
 111         int idx = get_irn_idx(n);
 112
 113         assert(idx < ARR_LEN(env->sched_info));
 114         env->sched_info[idx].etime = etime;
 115 }
 116
 117 /**
 118  * Get the number of users.
 119  */
 120 static INLINE unsigned get_irn_num_user(trace_env_t *env, ir_node *n) {
 121         int idx = get_irn_idx(n);
 122
 123         assert(idx < ARR_LEN(env->sched_info));
 124         return env->sched_info[idx].num_user;
 125 }
 126
 127 /**
 128  * Set the number of users.
 129  */
 130 static INLINE void set_irn_num_user(trace_env_t *env, ir_node *n, unsigned num_user) {
 131         int idx = get_irn_idx(n);
 132
 133         assert(idx < ARR_LEN(env->sched_info));
 134         env->sched_info[idx].num_user = num_user;
 135 }
 136
 137 /**
 138  * Get the register difference.
 139  */
 140 static INLINE int get_irn_reg_diff(trace_env_t *env, ir_node *n) {
 141         int idx = get_irn_idx(n);
 142
 143         assert(idx < ARR_LEN(env->sched_info));
 144         return env->sched_info[idx].reg_diff;
 145 }
 146
 147 /**
 148  * Set the register difference.
 149  */
 150 static INLINE void set_irn_reg_diff(trace_env_t *env, ir_node *n, int reg_diff) {
 151         int idx = get_irn_idx(n);
 152
 153         assert(idx < ARR_LEN(env->sched_info));
 154         env->sched_info[idx].reg_diff = reg_diff;
 155 }
 156
 157 /**
 158  * Get the pre-order position.
 159  */
 160 static INLINE int get_irn_preorder(trace_env_t *env, ir_node *n) {
 161         int idx = get_irn_idx(n);
 162
 163         assert(idx < ARR_LEN(env->sched_info));
 164         return env->sched_info[idx].preorder;
 165 }
 166
 167 /**
 168  * Set the pre-order position.
 169  */
 170 static INLINE void set_irn_preorder(trace_env_t *env, ir_node *n, int pos) {
 171         int idx = get_irn_idx(n);
 172
 173         assert(idx < ARR_LEN(env->sched_info));
 174         env->sched_info[idx].preorder = pos;
 175 }
 176
 177 /**
 178  * Get the pre-order position.
 179  */
 180 static INLINE unsigned get_irn_critical_path_len(trace_env_t *env, ir_node *n) {
 181         int idx = get_irn_idx(n);
 182
 183         assert(idx < ARR_LEN(env->sched_info));
 184         return env->sched_info[idx].critical_path_len;
 185 }
 186
 187 /**
 188  * Set the pre-order position.
 189  */
 190 static INLINE void set_irn_critical_path_len(trace_env_t *env, ir_node *n, unsigned len) {
 191         int idx = get_irn_idx(n);
 192
 193         assert(idx < ARR_LEN(env->sched_info));
 194         env->sched_info[idx].critical_path_len = len;
 195 }
 196
 197 /**
 198  * returns the exec-time for node n.
 199  */
 200 static sched_timestep_t exectime(trace_env_t *env, ir_node *n) {
 201         if (be_is_Keep(n) || is_Proj(n))
 202                 return 0;
 203         if (env->selector->exectime)
 204                 return env->selector->exectime(env->selector_env, n);
 205         return 1;
 206 }
 207
 208 /**
 209  * Calculates the latency for between two ops
 210  */
 211 static sched_timestep_t latency(trace_env_t *env, ir_node *pred, int pred_cycle, ir_node *curr, int curr_cycle) {
 212         /* a Keep hides a root */
 213         if (be_is_Keep(curr))
 214                 return exectime(env, pred);
 215
 216         /* Proj's are executed immediately */
 217         if (is_Proj(curr))
 218                 return 0;
 219
 220         /* predecessors Proj's must be skipped */
 221         if (is_Proj(pred))
 222                 pred = get_Proj_pred(pred);
 223
 224         if (env->selector->latency)
 225                 return env->selector->latency(env->selector_env, pred, pred_cycle, curr, curr_cycle);
 226         return 1;
 227 }
 228
 229 /**
 230  * Returns the number of users of a node having mode datab.
 231  */
 232 static int get_num_successors(ir_node *irn) {
 233         int sum = 0;
 234         const ir_edge_t *edge;
 235
 236         if (get_irn_mode(irn) == mode_T) {
 237                 /* for mode_T nodes: count the users of all Projs */
 238                 foreach_out_edge(irn, edge) {
 239                         ir_node *proj = get_edge_src_irn(edge);
 240                         ir_mode *mode = get_irn_mode(proj);
 241
 242                         if (mode == mode_T)
 243                                 sum += get_num_successors(proj);
 244                         else if (mode_is_datab(mode))
 245                                 sum += get_irn_n_edges(proj);
 246                 }
 247         }
 248         else {
 249                 /* do not count keep-alive edges */
 250                 foreach_out_edge(irn, edge) {
 251                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 252                                 sum++;
 253                 }
 254         }
 255
 256         return sum;
 257 }
 258
 259 /**
 260  * Returns the difference of regs_output - regs_input;
 261  */
 262 static int get_reg_difference(trace_env_t *env, ir_node *irn) {
 263         int num_out = 0;
 264         int num_in  = 0;
 265         int i;
 266         ir_node *block = get_nodes_block(irn);
 267
 268         if (be_is_Call(irn)) {
 269                 /* we want calls prefered */
 270                 return -5;
 271         }
 272
 273         if (get_irn_mode(irn) == mode_T) {
 274                 /* mode_T nodes: num out regs == num Projs with mode datab */
 275                 const ir_edge_t *edge;
 276                 foreach_out_edge(irn, edge) {
 277                         ir_node *proj = get_edge_src_irn(edge);
 278                         if (mode_is_datab(get_irn_mode(proj)))
 279                                 num_out++;
 280                 }
 281         }
 282         else
 283                 num_out = 1;
 284
 285         /* num in regs: number of ins with mode datab and not ignore */
 286         for (i = get_irn_arity(irn) - 1; i >= 0; i--) {
 287                 ir_node *in = get_irn_n(irn, i);
 288
 289                 if (! be_is_live_end(env->liveness, block, in) &&  /* if the value lives outside of block: do not count */
 290                         mode_is_datab(get_irn_mode(in))             &&  /* must be data node */
 291                         ! arch_irn_is(env->arch_env, in, ignore))       /* ignore "ignore" nodes :) */
 292                         num_in++;
 293         }
 294
 295         return num_out - num_in;
 296 }
 297
 298 /**
 299  * descent into a dag and create a pre-order list.
 300  */
 301 static void descent(ir_node *root, ir_node *block, ir_node **list, trace_env_t *env, unsigned path_len) {
 302         int i;
 303
 304         if (! is_Phi(root)) {
 305                 path_len += exectime(env, root);
 306                 if (get_irn_critical_path_len(env, root) < path_len) {
 307                         set_irn_critical_path_len(env, root, path_len);
 308                 }
 309                 /* calculate number of users (needed for heuristic) */
 310                 set_irn_num_user(env, root, get_num_successors(root));
 311
 312                 /* calculate register difference (needed for heuristic) */
 313                 set_irn_reg_diff(env, root, get_reg_difference(env, root));
 314
 315                 /* Phi nodes always leave the block */
 316                 for (i = get_irn_arity(root) - 1; i >= 0; --i) {
 317                         ir_node *pred = get_irn_n(root, i);
 318
 319                         DBG((env->dbg, LEVEL_3, "   node %+F\n", pred));
 320
 321                         /* Blocks may happen as predecessors of End nodes */
 322                         if (is_Block(pred))
 323                                 continue;
 324
 325                         /* already seen nodes are not marked */
 326                         if (get_irn_link(pred) != MARK)
 327                                 continue;
 328
 329                         /* don't leave our block */
 330                         if (get_nodes_block(pred) != block)
 331                                 continue;
 332
 333                         set_irn_link(pred, NULL);
 334
 335                         descent(pred, block, list, env, path_len);
 336                 }
 337         }
 338         set_irn_link(root, *list);
 339         *list = root;
 340 }
 341
 342 /**
 343  * Returns non-zero if root is a root in the block block.
 344  */
 345 static int is_root(ir_node *root, ir_node *block) {
 346         const ir_edge_t *edge;
 347
 348         foreach_out_edge(root, edge) {
 349                 ir_node *succ = get_edge_src_irn(edge);
 350
 351                 if (is_Block(succ))
 352                         continue;
 353                 /* Phi nodes are always in "another block */
 354                 if (is_Phi(succ))
 355                         continue;
 356                 if (get_nodes_block(succ) == block)
 357                         return 0;
 358         }
 359         return 1;
 360 }
 361
 362 /**
 363  * Performs initial block calculations for trace scheduling.
 364  */
 365 static void trace_preprocess_block(trace_env_t *env, ir_node *block) {
 366         ir_node *root = NULL, *preord = NULL;
 367         ir_node *curr, *irn;
 368         int cur_pos;
 369         const ir_edge_t *edge;
 370
 371         /* First step: Find the root set. */
 372         foreach_out_edge(block, edge) {
 373                 ir_node *succ = get_edge_src_irn(edge);
 374
 375                 if (is_root(succ, block)) {
 376                         mark_root_node(env, succ);
 377                         set_irn_link(succ, root);
 378                         root = succ;
 379                 }
 380                 else
 381                         set_irn_link(succ, MARK);
 382         }
 383
 384         /* Second step: calculate the pre-order list. */
 385         preord = NULL;
 386         for (curr = root; curr; curr = irn) {
 387                 irn = get_irn_link(curr);
 388                 DBG((env->dbg, LEVEL_2, "   DAG root %+F\n", curr));
 389                 descent(curr, block, &preord, env, 0);
 390         }
 391         root = preord;
 392
 393         /* Third step: calculate the Delay. Note that our
 394         * list is now in pre-order, starting at root
 395         */
 396         for (cur_pos = 0, curr = root; curr; curr = get_irn_link(curr), cur_pos++) {
 397                 sched_timestep_t d;
 398
 399                 if (arch_irn_class_is(env->arch_env, curr, branch)) {
 400                         /* assure, that branches can be executed last */
 401                         d = 0;
 402                 }
 403                 else {
 404                         if (is_root_node(env, curr))
 405                                 d = exectime(env, curr);
 406                         else {
 407                                 d = 0;
 408                                 foreach_out_edge(curr, edge) {
 409                                         ir_node *n = get_edge_src_irn(edge);
 410
 411                                         if (get_nodes_block(n) == block) {
 412                                                 sched_timestep_t ld;
 413
 414                                                 ld = latency(env, curr, 1, n, 0) + get_irn_delay(env, n);
 415                                                 d = ld > d ? ld : d;
 416                                         }
 417                                 }
 418                         }
 419                 }
 420                 set_irn_delay(env, curr, d);
 421                 DB((env->dbg, LEVEL_2, "\t%+F delay %u\n", curr, d));
 422
 423                 /* set the etime of all nodes to 0 */
 424                 set_irn_etime(env, curr, 0);
 425
 426                 set_irn_preorder(env, curr, cur_pos);
 427         }
 428 }
 429
 430 /**
 431  * This functions gets called after a node finally has been made ready.
 432  */
 433 static void trace_node_ready(void *data, ir_node *irn, ir_node *pred) {
 434         trace_env_t *env = data;
 435         sched_timestep_t etime_p, etime;
 436
 437         etime = env->curr_time;
 438         if (pred) {
 439                 etime_p = get_irn_etime(env, pred);
 440                 etime  += latency(env, pred, 1, irn, 0);
 441                 etime   = etime_p > etime ? etime_p : etime;
 442         }
 443
 444         set_irn_etime(env, irn, etime);
 445         DB((env->dbg, LEVEL_2, "\tset etime of %+F to %u\n", irn, etime));
 446 }
 447
 448 /**
 449  * Update the current time after irn has been selected.
 450  */
 451 static void trace_update_time(void *data, ir_node *irn) {
 452         trace_env_t *env = data;
 453         if (is_Phi(irn) || get_irn_opcode(irn) == iro_Start) {
 454                 env->curr_time += get_irn_etime(env, irn);
 455         }
 456         else {
 457                 env->curr_time += exectime(env, irn);
 458         }
 459 }
 460
 461 /**
 462  * Allocates memory and initializes trace scheduling environment.
 463  * @param birg   The backend irg object
 464  * @return The environment
 465  */
 466 static trace_env_t *trace_init(const arch_env_t *arch_env, ir_graph *irg) {
 467         trace_env_t *env = xcalloc(1, sizeof(*env));
 468         int         nn   = get_irg_last_idx(irg);
 469
 470         env->arch_env   = arch_env;
 471         env->curr_time  = 0;
 472         env->sched_info = NEW_ARR_F(trace_irn_t, nn);
 473         env->liveness   = be_liveness(irg);
 474         FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.trace");
 475
 476         memset(env->sched_info, 0, nn * sizeof(*(env->sched_info)));
 477
 478         return env;
 479 }
 480
 481 /**
 482  * Frees all memory allocated for trace scheduling environment.
 483  * @param env  The environment
 484  */
 485 static void trace_free(void *data) {
 486         trace_env_t *env = data;
 487         be_liveness_free(env->liveness);
 488         DEL_ARR_F(env->sched_info);
 489         free(env);
 490 }
 491
 492 /**
 493  * Simple selector. Just assure that jumps are scheduled last.
 494  */
 495 static ir_node *basic_selection(const arch_env_t *arch_env, ir_nodeset_t *ready_set) {
 496         ir_node *irn = NULL;
 497         ir_nodeset_iterator_t iter;
 498
 499         /* assure that branches and constants are executed last */
 500         foreach_ir_nodeset(ready_set, irn, iter) {
 501                 if (! arch_irn_class_is(arch_env, irn, branch)) {
 502                         return irn;
 503                 }
 504         }
 505
 506         /* at last: schedule branches */
 507         irn = get_nodeset_node(ready_set);
 508
 509         return irn;
 510 }
 511
 512 /**
 513 * The muchnik selector.
 514 */
 515 static ir_node *muchnik_select(void *block_env, ir_nodeset_t *ready_set, ir_nodeset_t *live_set)
 516 {
 517         trace_env_t *env = block_env;
 518         ir_nodeset_t mcands, ecands;
 519         ir_nodeset_iterator_t iter;
 520         sched_timestep_t max_delay = 0;
 521         ir_node *irn;
 522
 523         /* calculate the max delay of all candidates */
 524         foreach_ir_nodeset(ready_set, irn, iter) {
 525                 sched_timestep_t d = get_irn_delay(env, irn);
 526
 527                 max_delay = d > max_delay ? d : max_delay;
 528         }
 529
 530         ir_nodeset_init_size(&mcands, 8);
 531         ir_nodeset_init_size(&ecands, 8);
 532
 533         /* build mcands and ecands */
 534         foreach_ir_nodeset(ready_set, irn, iter) {
 535                 if (get_irn_delay(env, irn) == max_delay) {
 536                         ir_nodeset_insert(&mcands, irn);
 537                         if (get_irn_etime(env, irn) <= env->curr_time)
 538                                 ir_nodeset_insert(&ecands, irn);
 539                 }
 540         }
 541
 542         /* select a node */
 543         if (ir_nodeset_size(&mcands) == 1) {
 544                 irn = get_nodeset_node(&mcands);
 545                 DB((env->dbg, LEVEL_3, "\tirn = %+F, mcand = 1, max_delay = %u\n", irn, max_delay));
 546         }
 547         else {
 548                 int cnt = ir_nodeset_size(&ecands);
 549                 if (cnt == 1) {
 550                         irn = get_nodeset_node(&ecands);
 551
 552                         if (arch_irn_class_is(env->arch_env, irn, branch)) {
 553                                 /* BEWARE: don't select a JUMP if others are still possible */
 554                                 goto force_mcands;
 555                         }
 556                         DB((env->dbg, LEVEL_3, "\tirn = %+F, ecand = 1, max_delay = %u\n", irn, max_delay));
 557                 }
 558                 else if (cnt > 1) {
 559                         DB((env->dbg, LEVEL_3, "\tecand = %d, max_delay = %u\n", cnt, max_delay));
 560                         irn = basic_selection(env->arch_env, &ecands);
 561                 }
 562                 else {
 563 force_mcands:
 564                         DB((env->dbg, LEVEL_3, "\tmcand = %d\n", ir_nodeset_size(&mcands)));
 565                         irn = basic_selection(env->arch_env, &mcands);
 566                 }
 567         }
 568
 569         return irn;
 570 }
 571
 572 static void *muchnik_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
 573 {
 574         trace_env_t *env  = trace_init(arch_env, irg);
 575         env->selector     = vtab;
 576         env->selector_env = (void*) arch_env;
 577         return (void *)env;
 578 }
 579
 580 static void *muchnik_init_block(void *graph_env, ir_node *bl)
 581 {
 582         trace_preprocess_block(graph_env, bl);
 583         return graph_env;
 584 }
 585
 586 static const list_sched_selector_t muchnik_selector_struct = {
 587         muchnik_init_graph,
 588         muchnik_init_block,
 589         muchnik_select,
 590         NULL,                /* to_appear_in_schedule */
 591         trace_node_ready,    /* node_ready */
 592         trace_update_time,   /* node_selected */
 593         NULL,                /* exectime */
 594         NULL,                /* latency */
 595         NULL,                /* finish_block */
 596         trace_free           /* finish_graph */
 597 };
 598
 599 const list_sched_selector_t *muchnik_selector = &muchnik_selector_struct;
 600
 601 /**
 602  * Execute the heuristic function.
 603  */
 604 static ir_node *heuristic_select(void *block_env, ir_nodeset_t *ns, ir_nodeset_t *lv)
 605 {
 606         trace_env_t *trace_env   = block_env;
 607         ir_node     *irn, *cand  = NULL;
 608         int         max_prio     = INT_MIN;
 609         int         cur_prio     = INT_MIN;
 610         int         cur_pressure = ir_nodeset_size(lv);
 611         int         reg_fact, cand_reg_fact;
 612         ir_nodeset_iterator_t iter;
 613
 614         /* prefer instructions which can be scheduled early */
 615 #define PRIO_TIME        3
 616         /* prefer instructions with lots of successors */
 617 #define PRIO_NUMSUCCS    8
 618         /* prefer instructions with long critical path */
 619 #define PRIO_LEVEL      12
 620         /* prefer instructions coming early in preorder */
 621 #define PRIO_PREORD      8
 622         /* weight of current register pressure */
 623 #define PRIO_CUR_PRESS  20
 624         /* weight of register pressure difference */
 625 #define PRIO_CHG_PRESS   8
 626
 627         /* priority based selection, heuristic inspired by mueller diss */
 628         foreach_ir_nodeset(ns, irn, iter) {
 629                 /* make sure that branches are scheduled last */
 630                 if (! arch_irn_class_is(trace_env->arch_env, irn, branch)) {
 631                         int rdiff = get_irn_reg_diff(trace_env, irn);
 632                         int sign  = rdiff < 0;
 633                         int chg   = (rdiff < 0 ? -rdiff : rdiff) << PRIO_CHG_PRESS;
 634
 635                         //reg_fact = chg << cur_pressure;
 636                         reg_fact = chg * cur_pressure;
 637                         if (reg_fact < chg)
 638                                 reg_fact = INT_MAX - 2;
 639                         reg_fact = sign ? -reg_fact : reg_fact;
 640
 641                         cur_prio = (get_irn_critical_path_len(trace_env, irn) << PRIO_LEVEL)
 642                                 //- (get_irn_delay(trace_env, irn) << PRIO_LEVEL)
 643                                 + (get_irn_num_user(trace_env, irn) << PRIO_NUMSUCCS)
 644                                 - (get_irn_etime(trace_env, irn) << PRIO_TIME)
 645                                 //- ((get_irn_reg_diff(trace_env, irn) >> PRIO_CHG_PRESS) << ((cur_pressure >> PRIO_CUR_PRESS) - 3))
 646                                 - reg_fact
 647                                 + (get_irn_preorder(trace_env, irn) << PRIO_PREORD); /* high preorder means early schedule */
 648                         if (cur_prio > max_prio) {
 649                                 cand          = irn;
 650                                 max_prio      = cur_prio;
 651                                 cand_reg_fact = reg_fact;
 652                         }
 653
 654                         DBG((trace_env->dbg, LEVEL_4, "checked NODE %+F\n", irn));
 655                         DBG((trace_env->dbg, LEVEL_4, "\tpriority: %d\n", cur_prio));
 656                         DBG((trace_env->dbg, LEVEL_4, "\tpath len: %d (%d)\n", get_irn_critical_path_len(trace_env, irn), get_irn_critical_path_len(trace_env, irn) << PRIO_LEVEL));
 657                         DBG((trace_env->dbg, LEVEL_4, "\tdelay:    %d (%d)\n", get_irn_delay(trace_env, irn), get_irn_delay(trace_env, irn) << PRIO_LEVEL));
 658                         DBG((trace_env->dbg, LEVEL_4, "\t#user:    %d (%d)\n", get_irn_num_user(trace_env, irn), get_irn_num_user(trace_env, irn) << PRIO_NUMSUCCS));
 659                         DBG((trace_env->dbg, LEVEL_4, "\tetime:    %d (%d)\n", get_irn_etime(trace_env, irn), 0 - (get_irn_etime(trace_env, irn) << PRIO_TIME)));
 660                         DBG((trace_env->dbg, LEVEL_4, "\tpreorder: %d (%d)\n", get_irn_preorder(trace_env, irn), get_irn_preorder(trace_env, irn) << PRIO_PREORD));
 661                         DBG((trace_env->dbg, LEVEL_4, "\treg diff: %d (%d)\n", get_irn_reg_diff(trace_env, irn), 0 - reg_fact));
 662                         DBG((trace_env->dbg, LEVEL_4, "\tpressure: %d\n", cur_pressure));
 663                 }
 664         }
 665
 666         if (cand) {
 667                 DBG((trace_env->dbg, LEVEL_4, "heuristic selected %+F:\n", cand));
 668         }
 669         else {
 670                 cand = basic_selection(trace_env->arch_env, ns);
 671         }
 672
 673         return cand;
 674 }
 675
 676 static const list_sched_selector_t heuristic_selector_struct = {
 677         muchnik_init_graph,
 678         muchnik_init_block,
 679         heuristic_select,
 680         NULL,                /* to_appear_in_schedule */
 681         trace_node_ready,    /* node_ready */
 682         trace_update_time,   /* node_selected */
 683         NULL,                /* exectime */
 684         NULL,                /* latency */
 685         NULL,                /* finish_block */
 686         trace_free           /* finish_graph */
 687 };
 688
 689 const list_sched_selector_t *heuristic_selector = &heuristic_selector_struct;