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

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