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

   1 /**
   2  * Scheduling algorithms.
   3  * Just a simple list scheduling algorithm is here.
   4  * @date   20.10.2004
   5  * @author Sebastian Hack
   6  * @cvs-id $Id$
   7  */
   8
   9 #ifdef HAVE_CONFIG_H
  10 #include "config.h"
  11 #endif
  12
  13 #include <stdio.h>
  14 #include <stdarg.h>
  15 #include <string.h>
  16 #include <limits.h>
  17
  18 #include "benode_t.h"
  19 #include "be_t.h"
  20
  21 #include "obst.h"
  22 #include "list.h"
  23 #include "iterator.h"
  24
  25 #include "iredges_t.h"
  26 #include "irgwalk.h"
  27 #include "irnode_t.h"
  28 #include "irmode_t.h"
  29 #include "irdump.h"
  30 #include "irprintf_t.h"
  31 #include "array.h"
  32 #include "debug.h"
  33 #include "irtools.h"
  34
  35 #include "besched_t.h"
  36 #include "beutil.h"
  37 #include "belive_t.h"
  38 #include "belistsched.h"
  39 #include "beschedmris.h"
  40 #include "bearch.h"
  41 #include "bestat.h"
  42
  43 /**
  44  * All scheduling info needed per node.
  45  */
  46 typedef struct _sched_irn_t {
  47         unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
  48         unsigned already_sched : 1;  /**< Set if this node is already scheduled */
  49 } sched_irn_t;
  50
  51 /**
  52  * Scheduling environment for the whole graph.
  53  */
  54 typedef struct _sched_env_t {
  55         sched_irn_t *sched_info;                    /**< scheduling info per node */
  56         const list_sched_selector_t *selector;      /**< The node selector. */
  57         const arch_env_t *arch_env;                 /**< The architecture environment. */
  58         const ir_graph *irg;                        /**< The graph to schedule. */
  59         void *selector_env;                         /**< A pointer to give to the selector. */
  60 } sched_env_t;
  61
  62 /**
  63  * Environment for a block scheduler.
  64  */
  65 typedef struct _block_sched_env_t {
  66         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
  67         nodeset *cands;                             /**< the set of candidates */
  68         ir_node *block;                             /**< the current block */
  69         sched_env_t *sched_env;                     /**< the scheduler environment */
  70         nodeset *live;                              /**< simple liveness during scheduling */
  71         const list_sched_selector_t *selector;
  72         void *selector_block_env;
  73         DEBUG_ONLY(firm_dbg_module_t *dbg;)
  74 } block_sched_env_t;
  75
  76 /**
  77  * Returns non-zero if the node is already scheduled
  78  */
  79 static INLINE int is_already_scheduled(block_sched_env_t *env, ir_node *n)
  80 {
  81         int idx = get_irn_idx(n);
  82
  83         assert(idx < ARR_LEN(env->sched_info));
  84         return env->sched_info[idx].already_sched;
  85 }
  86
  87 /**
  88  * Mark a node as already scheduled
  89  */
  90 static INLINE void mark_already_scheduled(block_sched_env_t *env, ir_node *n)
  91 {
  92         int idx = get_irn_idx(n);
  93
  94         assert(idx < ARR_LEN(env->sched_info));
  95         env->sched_info[idx].already_sched = 1;
  96 }
  97
  98 /**
  99  * Try to put a node in the ready set.
 100  * @param env   The block scheduler environment.
 101  * @param pred  The previous scheduled node.
 102  * @param irn   The node to make ready.
 103  * @return 1, if the node could be made ready, 0 else.
 104  */
 105 static INLINE int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 106 {
 107         int i, n;
 108
 109     /* Blocks cannot be scheduled. */
 110     if (is_Block(irn))
 111         return 0;
 112
 113     /*
 114      * Check, if the given ir node is in a different block as the
 115      * currently scheduled one. If that is so, don't make the node ready.
 116      */
 117     if (env->block != get_nodes_block(irn))
 118         return 0;
 119
 120         for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 121         ir_node *op = get_irn_in_or_dep(irn, i);
 122
 123         /* if irn is an End we have keep-alives and op might be a block, skip that */
 124         if (is_Block(op)) {
 125           assert(get_irn_op(irn) == op_End);
 126           continue;
 127         }
 128
 129         /* If the operand is local to the scheduled block and not yet
 130          * scheduled, this nodes cannot be made ready, so exit. */
 131         if (! is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 132             return 0;
 133     }
 134
 135         nodeset_insert(env->cands, irn);
 136
 137         /* Notify selector about the ready node. */
 138         if (env->selector->node_ready)
 139                 env->selector->node_ready(env->selector_block_env, irn, pred);
 140
 141     DB((env->dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 142
 143     return 1;
 144 }
 145
 146 /**
 147  * Try, to make all users of a node ready.
 148  * In fact, a usage node can only be made ready, if all its operands
 149  * have already been scheduled yet. This is checked my make_ready().
 150  * @param env The block schedule environment.
 151  * @param irn The node, which usages (successors) are to be made ready.
 152  */
 153 static INLINE void make_users_ready(block_sched_env_t *env, ir_node *irn)
 154 {
 155         const ir_edge_t *edge;
 156
 157         foreach_out_edge(irn, edge) {
 158                 ir_node *user = get_edge_src_irn(edge);
 159                 if (! is_Phi(user))
 160                         make_ready(env, irn, user);
 161         }
 162
 163         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 164                 ir_node *user = get_edge_src_irn(edge);
 165                 if (! is_Phi(user))
 166                         make_ready(env, irn, user);
 167         }
 168 }
 169
 170 /**
 171  * Returns the number of not yet schedules users.
 172  */
 173 static INLINE int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n) {
 174         int idx = get_irn_idx(n);
 175
 176         assert(idx < ARR_LEN(env->sched_info));
 177         return env->sched_info[idx].num_not_sched_user;
 178 }
 179
 180 /**
 181  * Sets the number of not yet schedules users.
 182  */
 183 static INLINE void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 184         int idx = get_irn_idx(n);
 185
 186         assert(idx < ARR_LEN(env->sched_info));
 187         env->sched_info[idx].num_not_sched_user = num;
 188 }
 189
 190 /**
 191  * Add @p num to the number of not yet schedules users and returns the result.
 192  */
 193 static INLINE int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num) {
 194         int idx = get_irn_idx(n);
 195
 196         assert(idx < ARR_LEN(env->sched_info));
 197         env->sched_info[idx].num_not_sched_user += num;
 198         return env->sched_info[idx].num_not_sched_user;
 199 }
 200
 201 /**
 202  * Returns the number of users of a node having mode datab.
 203  */
 204 static int get_num_successors(ir_node *irn) {
 205         int             sum = 0;
 206         const ir_edge_t *edge;
 207
 208         if (get_irn_mode(irn) == mode_T) {
 209                 /* for mode_T nodes: count the users of all Projs */
 210                 foreach_out_edge(irn, edge) {
 211                         ir_node *proj = get_edge_src_irn(edge);
 212                         ir_mode *mode = get_irn_mode(proj);
 213
 214                         if (mode == mode_T)
 215                                 sum += get_num_successors(proj);
 216                         else if (mode_is_datab(mode))
 217                                 sum += get_irn_n_edges(proj);
 218                 }
 219         }
 220         else {
 221                 /* do not count keep-alive edges */
 222                 foreach_out_edge(irn, edge) {
 223                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 224                                 sum++;
 225                 }
 226         }
 227
 228         return sum;
 229 }
 230
 231 /**
 232  * Adds irn to @p live, updates all inputs that this user is scheduled
 233  * and counts all of it's non scheduled users.
 234  */
 235 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn) {
 236         int i;
 237
 238         /* ignore Projs */
 239         if (is_Proj(irn))
 240                 return;
 241
 242         for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
 243                 ir_node *in = get_irn_in_or_dep(irn, i);
 244
 245                 /* if in is a proj: update predecessor */
 246                 while (is_Proj(in))
 247                         in = get_Proj_pred(in);
 248
 249                 /* if in is still in the live set: reduce number of users by one */
 250                 if (nodeset_find(env->live, in)) {
 251                         if (add_irn_not_sched_user(env, in, -1) <= 0)
 252                                 nodeset_remove(env->live, in);
 253                 }
 254         }
 255
 256         /*
 257                 get_num_successors returns the number of all users. This includes
 258                 users in different blocks as well. As the each block is scheduled separately
 259                 the liveness info of those users will not be updated and so these
 260                 users will keep up the register pressure as it is desired.
 261         */
 262         i = get_num_successors(irn);
 263         if (i > 0) {
 264                 set_irn_not_sched_user(env, irn, i);
 265                 nodeset_insert(env->live, irn);
 266         }
 267 }
 268
 269 static INLINE int must_appear_in_schedule(const list_sched_selector_t *sel, void *block_env, const ir_node *irn)
 270 {
 271         int res = -1;
 272
 273         if(sel->to_appear_in_schedule)
 274                 res = sel->to_appear_in_schedule(block_env, irn);
 275
 276         return res >= 0 ? res : (to_appear_in_schedule(irn) || be_is_Keep(irn) || be_is_CopyKeep(irn) || be_is_RegParams(irn));
 277 }
 278
 279 /**
 280  * Append an instruction to a schedule.
 281  * @param env The block scheduling environment.
 282  * @param irn The node to add to the schedule.
 283  * @return    The given node.
 284  */
 285 static ir_node *add_to_sched(block_sched_env_t *env, ir_node *irn)
 286 {
 287     /* If the node consumes/produces data, it is appended to the schedule
 288      * list, otherwise, it is not put into the list */
 289     if (must_appear_in_schedule(env->selector, env->selector_block_env, irn)) {
 290         sched_info_t *info = get_irn_sched_info(irn);
 291         INIT_LIST_HEAD(&info->list);
 292         info->scheduled = 1;
 293                 update_sched_liveness(env, irn);
 294         sched_add_before(env->block, irn);
 295
 296         DBG((env->dbg, LEVEL_2, "\tadding %+F\n", irn));
 297     }
 298
 299         /* notify the selector about the finally selected node. */
 300         if (env->selector->node_selected)
 301                 env->selector->node_selected(env->selector_block_env, irn);
 302
 303     /* Insert the node in the set of all already scheduled nodes. */
 304     mark_already_scheduled(env, irn);
 305
 306     /* Remove the node from the ready set */
 307     if(nodeset_find(env->cands, irn))
 308         nodeset_remove(env->cands, irn);
 309
 310     return irn;
 311 }
 312
 313 /**
 314  * Add the proj nodes of a tuple-mode irn to the schedule immediately
 315  * after the tuple-moded irn. By pinning the projs after the irn, no
 316  * other nodes can create a new lifetime between the tuple-moded irn and
 317  * one of its projs. This should render a realistic image of a
 318  * tuple-moded irn, which in fact models a node which defines multiple
 319  * values.
 320  *
 321  * @param irn The tuple-moded irn.
 322  */
 323 static void add_tuple_projs(block_sched_env_t *env, ir_node *irn)
 324 {
 325         const ir_edge_t *edge;
 326
 327         assert(get_irn_mode(irn) == mode_T && "Mode of node must be tuple");
 328
 329         if(is_Bad(irn))
 330                 return;
 331
 332
 333         /* non-proj nodes can have dependency edges to tuple nodes. */
 334         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 335                 ir_node *out = get_edge_src_irn(edge);
 336                 make_ready(env, irn, out);
 337         }
 338
 339         /* schedule the normal projs */
 340         foreach_out_edge(irn, edge) {
 341                 ir_node *out = get_edge_src_irn(edge);
 342
 343                 assert(is_Proj(out) && "successor of a modeT node must be a proj");
 344
 345                 if (get_irn_mode(out) == mode_T)
 346                         add_tuple_projs(env, out);
 347                 else {
 348                         add_to_sched(env, out);
 349                         make_users_ready(env, out);
 350                 }
 351         }
 352 }
 353
 354 /**
 355  * Perform list scheduling on a block.
 356  *
 357  * Note, that the caller must compute a linked list of nodes in the block
 358  * using the link field before calling this function.
 359  *
 360  * Also the outs must have been computed.
 361  *
 362  * @param block The block node.
 363  * @param env Scheduling environment.
 364  */
 365 static void list_sched_block(ir_node *block, void *env_ptr)
 366 {
 367         sched_env_t *env                      = env_ptr;
 368         const list_sched_selector_t *selector = env->selector;
 369         ir_node *start_node                   = get_irg_start(get_irn_irg(block));
 370         sched_info_t *info                    = get_irn_sched_info(block);
 371
 372         block_sched_env_t be;
 373         const ir_edge_t *edge;
 374         ir_node *irn;
 375         int j, m;
 376
 377         /* Initialize the block's list head that will hold the schedule. */
 378         INIT_LIST_HEAD(&info->list);
 379
 380         /* Initialize the block scheduling environment */
 381         be.sched_info        = env->sched_info;
 382         be.block             = block;
 383         be.cands             = new_nodeset(get_irn_n_edges(block));
 384         be.live              = new_nodeset(get_irn_n_edges(block));
 385         be.selector          = selector;
 386         be.sched_env         = env;
 387         FIRM_DBG_REGISTER(be.dbg, "firm.be.sched");
 388
 389         DBG((be.dbg, LEVEL_1, "scheduling %+F\n", block));
 390
 391         if (selector->init_block)
 392                 be.selector_block_env = selector->init_block(env->selector_env, block);
 393
 394         /* Then one can add all nodes are ready to the set. */
 395         foreach_out_edge(block, edge) {
 396                 ir_node *irn = get_edge_src_irn(edge);
 397
 398                 /* Skip the end node because of keepalive edges. */
 399                 if (get_irn_opcode(irn) == iro_End)
 400                         continue;
 401
 402                 if (is_Phi(irn)) {
 403                         /*
 404                                 Phi functions are scheduled immediately, since they     only
 405                                 transfer data flow from the predecessors to this block.
 406                         */
 407                         add_to_sched(&be, irn);
 408                         make_users_ready(&be, irn);
 409                 }
 410                 else if (irn == start_node) {
 411                         /* The start block will be scheduled as the first node */
 412                         add_to_sched(&be, irn);
 413                         add_tuple_projs(&be, irn);
 414                 }
 415                 else {
 416                         /* Other nodes must have all operands in other blocks to be made
 417                         * ready */
 418                         int ready = 1;
 419
 420                         /* Check, if the operands of a node are not local to this block */
 421                         for (j = 0, m = get_irn_ins_or_deps(irn); j < m; ++j) {
 422                                 ir_node *operand = get_irn_in_or_dep(irn, j);
 423
 424                                 if (get_nodes_block(operand) == block) {
 425                                         ready = 0;
 426                                         break;
 427                                 }
 428                                 else {
 429                                         /* live in values increase register pressure */
 430                                         update_sched_liveness(&be, operand);
 431                                 }
 432                         }
 433
 434                         /* Make the node ready, if all operands live in a foreign block */
 435                         if (ready) {
 436                                 DBG((be.dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
 437                                 make_ready(&be, NULL, irn);
 438                         }
 439                 }
 440         }
 441
 442         /* Iterate over all remaining nodes */
 443         while (nodeset_count(be.cands) > 0) {
 444                 /* collect statistics about amount of ready nodes */
 445                 be_do_stat_sched_ready(block, be.cands);
 446
 447                 /* Keeps must be scheduled immediatly */
 448                 foreach_nodeset(be.cands, irn) {
 449                         if (be_is_Keep(irn) || be_is_CopyKeep(irn)) {
 450                                 nodeset_break(be.cands);
 451                                 break;
 452                         }
 453                 }
 454
 455                 if (! irn) {
 456                         /* Keeps must be immediately scheduled */
 457                         irn = be.selector->select(be.selector_block_env, be.cands, be.live);
 458                 }
 459
 460                 DB((be.dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 461
 462                 /* Add the node to the schedule. */
 463                 add_to_sched(&be, irn);
 464
 465                 if (get_irn_mode(irn) == mode_T)
 466                         add_tuple_projs(&be, irn);
 467                 else
 468                         make_users_ready(&be, irn);
 469
 470                 /* remove the scheduled node from the ready list. */
 471                 if (nodeset_find(be.cands, irn))
 472                         nodeset_remove(be.cands, irn);
 473         }
 474
 475         if (selector->finish_block)
 476                 selector->finish_block(be.selector_block_env);
 477
 478         del_nodeset(be.cands);
 479         del_nodeset(be.live);
 480 }
 481
 482 /* List schedule a graph. */
 483 void list_sched(const be_irg_t *birg, be_options_t *be_opts)
 484 {
 485         const arch_env_t *arch_env  = birg->main_env->arch_env;
 486         ir_graph         *irg       = birg->irg;
 487
 488         int num_nodes;
 489         sched_env_t env;
 490         mris_env_t *mris = NULL;
 491         list_sched_selector_t sel;
 492
 493         /* Select a scheduler based on backend options */
 494         switch (be_opts->sched_select) {
 495                 case BE_SCHED_SELECT_TRIVIAL:
 496                         memcpy(&sel, trivial_selector, sizeof(sel));
 497                         break;
 498                 case BE_SCHED_SELECT_RANDOM:
 499                         memcpy(&sel, random_selector, sizeof(sel));
 500                         break;
 501                 case BE_SCHED_SELECT_REGPRESS:
 502                         memcpy(&sel, reg_pressure_selector, sizeof(sel));
 503                         break;
 504                 case BE_SCHED_SELECT_MUCHNIK:
 505                         memcpy(&sel, muchnik_selector, sizeof(sel));
 506                         break;
 507                 case BE_SCHED_SELECT_HEUR:
 508                         memcpy(&sel, heuristic_selector, sizeof(sel));
 509                         break;
 510                 case BE_SCHED_SELECT_HMUCHNIK:
 511                 default:
 512                         memcpy(&sel, trivial_selector, sizeof(sel));
 513         }
 514
 515         /* Assure, that the out edges are computed */
 516         edges_assure(irg);
 517
 518         if (be_opts->mris)
 519                 mris = be_sched_mris_preprocess(birg);
 520
 521         num_nodes = get_irg_last_idx(irg);
 522
 523         /* initialize environment for list scheduler */
 524         memset(&env, 0, sizeof(env));
 525         env.selector   = arch_env->isa->impl->get_list_sched_selector(arch_env->isa, &sel);
 526         env.arch_env   = arch_env;
 527         env.irg        = irg;
 528         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 529
 530         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 531
 532         if (env.selector->init_graph)
 533                 env.selector_env = env.selector->init_graph(env.selector, arch_env, irg);
 534
 535         /* Schedule each single block. */
 536         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 537
 538         if (env.selector->finish_graph)
 539                 env.selector->finish_graph(env.selector_env);
 540
 541         if (be_opts->mris)
 542                 be_sched_mris_free(mris);
 543
 544         DEL_ARR_F(env.sched_info);
 545 }