nsz Git - libfirm/blob - ir/be/belistsched.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       Primitive list scheduling with different node selectors.
  23  * @author      Sebastian Hack
  24  * @date        20.10.2004
  25  * @version     $Id$
  26  */
  27 #include "config.h"
  28
  29 #include <stdio.h>
  30 #include <stdarg.h>
  31 #include <string.h>
  32 #include <limits.h>
  33
  34 #include "benode.h"
  35 #include "be_t.h"
  36
  37 #include "obst.h"
  38 #include "list.h"
  39 #include "iterator.h"
  40
  41 #include "iredges_t.h"
  42 #include "irgwalk.h"
  43 #include "irnode_t.h"
  44 #include "irmode_t.h"
  45 #include "irdump.h"
  46 #include "irprintf_t.h"
  47 #include "array.h"
  48 #include "debug.h"
  49 #include "irtools.h"
  50
  51 #include "bemodule.h"
  52 #include "besched.h"
  53 #include "beutil.h"
  54 #include "belive_t.h"
  55 #include "belistsched.h"
  56 #include "beschedmris.h"
  57 #include "beschedrss.h"
  58 #include "bearch.h"
  59 #include "bestat.h"
  60 #include "beirg.h"
  61
  62 #include "lc_opts.h"
  63 #include "lc_opts_enum.h"
  64
  65 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
  66
  67 enum {
  68         BE_SCHED_SELECT_TRIVIAL,
  69         BE_SCHED_SELECT_REGPRESS,
  70         BE_SCHED_SELECT_MUCHNIK,
  71         BE_SCHED_SELECT_HEUR,
  72         BE_SCHED_SELECT_HMUCHNIK,
  73         BE_SCHED_SELECT_RANDOM,
  74         BE_SCHED_SELECT_NORMAL,
  75 };
  76
  77 enum {
  78         BE_SCHED_PREP_NONE = 0,
  79         BE_SCHED_PREP_MRIS = 2,
  80         BE_SCHED_PREP_RSS  = 3
  81 };
  82
  83 typedef struct list_sched_options_t {
  84         int select;  /**< the node selector */
  85         int prep;    /**< schedule preparation */
  86 } list_sched_options_t;
  87
  88 static list_sched_options_t list_sched_options = {
  89         BE_SCHED_SELECT_NORMAL,   /* mueller heuristic selector */
  90         BE_SCHED_PREP_NONE,       /* no scheduling preparation */
  91 };
  92
  93 /* schedule selector options. */
  94 static const lc_opt_enum_int_items_t sched_select_items[] = {
  95         { "trivial",  BE_SCHED_SELECT_TRIVIAL  },
  96         { "random",   BE_SCHED_SELECT_RANDOM   },
  97         { "regpress", BE_SCHED_SELECT_REGPRESS },
  98         { "normal",   BE_SCHED_SELECT_NORMAL   },
  99         { "muchnik",  BE_SCHED_SELECT_MUCHNIK  },
 100         { "heur",     BE_SCHED_SELECT_HEUR     },
 101         { "hmuchnik", BE_SCHED_SELECT_HMUCHNIK },
 102         { NULL,       0 }
 103 };
 104
 105 /* schedule preparation options. */
 106 static const lc_opt_enum_int_items_t sched_prep_items[] = {
 107         { "none", BE_SCHED_PREP_NONE },
 108         { "mris", BE_SCHED_PREP_MRIS },
 109         { "rss",  BE_SCHED_PREP_RSS  },
 110         { NULL,   0 }
 111 };
 112
 113 static lc_opt_enum_int_var_t sched_select_var = {
 114         &list_sched_options.select, sched_select_items
 115 };
 116
 117 static lc_opt_enum_int_var_t sched_prep_var = {
 118         &list_sched_options.prep, sched_prep_items
 119 };
 120
 121 static const lc_opt_table_entry_t list_sched_option_table[] = {
 122         LC_OPT_ENT_ENUM_PTR("prep",   "schedule preparation",   &sched_prep_var),
 123         LC_OPT_ENT_ENUM_PTR("select", "node selector",          &sched_select_var),
 124         LC_OPT_LAST
 125 };
 126
 127 /**
 128  * All scheduling info needed per node.
 129  */
 130 typedef struct sched_irn_t {
 131         unsigned num_not_sched_user; /**< The number of not yet scheduled users of this node */
 132         unsigned already_sched : 1;  /**< Set if this node is already scheduled */
 133 } sched_irn_t;
 134
 135 /**
 136  * Scheduling environment for the whole graph.
 137  */
 138 typedef struct sched_env_t {
 139         sched_irn_t *sched_info;                    /**< scheduling info per node */
 140         const list_sched_selector_t *selector;      /**< The node selector. */
 141         void *selector_env;                         /**< A pointer to give to the selector. */
 142 } sched_env_t;
 143
 144 /**
 145  * Environment for a block scheduler.
 146  */
 147 typedef struct block_sched_env_t {
 148         sched_irn_t *sched_info;                    /**< scheduling info per node, copied from the global scheduler object */
 149         ir_nodeset_t cands;                         /**< the set of candidates */
 150         ir_node *block;                             /**< the current block */
 151         sched_env_t *sched_env;                     /**< the scheduler environment */
 152         ir_nodeset_t live;                          /**< simple liveness during scheduling */
 153         const list_sched_selector_t *selector;
 154         void *selector_block_env;
 155 } block_sched_env_t;
 156
 157 /**
 158  * Returns non-zero if the node is already scheduled
 159  */
 160 static inline int is_already_scheduled(block_sched_env_t *env, ir_node *n)
 161 {
 162         unsigned const idx = get_irn_idx(n);
 163
 164         assert(idx < ARR_LEN(env->sched_info));
 165         return env->sched_info[idx].already_sched;
 166 }
 167
 168 /**
 169  * Mark a node as already scheduled
 170  */
 171 static inline void set_already_scheduled(block_sched_env_t *env, ir_node *n)
 172 {
 173         unsigned const idx = get_irn_idx(n);
 174
 175         assert(idx < ARR_LEN(env->sched_info));
 176         env->sched_info[idx].already_sched = 1;
 177 }
 178
 179 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
 180
 181 /**
 182  * Try to put a node in the ready set.
 183  * @param env   The block scheduler environment.
 184  * @param pred  The previous scheduled node.
 185  * @param irn   The node to make ready.
 186  * @return 1, if the node could be made ready, 0 else.
 187  */
 188 static inline int make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 189 {
 190         int i, n;
 191
 192         /* Blocks cannot be scheduled. */
 193         if (is_Block(irn) || get_irn_n_edges(irn) == 0)
 194                 return 0;
 195
 196         /*
 197          * Check, if the given ir node is in a different block as the
 198          * currently scheduled one. If that is so, don't make the node ready.
 199          */
 200         if (env->block != get_nodes_block(irn))
 201                 return 0;
 202
 203         for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 204                 ir_node *op = get_irn_in_or_dep(irn, i);
 205
 206                 /* if irn is an End we have keep-alives and op might be a block, skip that */
 207                 if (is_Block(op)) {
 208                         assert(is_End(irn));
 209                         continue;
 210                 }
 211
 212                 /* If the operand is local to the scheduled block and not yet
 213                  * scheduled, this nodes cannot be made ready, so exit. */
 214                 if (! is_already_scheduled(env, op) && get_nodes_block(op) == env->block)
 215                         return 0;
 216         }
 217
 218         if (! to_appear_in_schedule(irn)) {
 219                 add_to_sched(env, irn);
 220                 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
 221         } else {
 222                 ir_nodeset_insert(&env->cands, irn);
 223
 224                 /* Notify selector about the ready node. */
 225                 if (env->selector->node_ready)
 226                         env->selector->node_ready(env->selector_block_env, irn, pred);
 227
 228                 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 229         }
 230
 231     return 1;
 232 }
 233
 234 /**
 235  * Try, to make all users of a node ready.
 236  * In fact, a usage node can only be made ready, if all its operands
 237  * have already been scheduled yet. This is checked by make_ready().
 238  * @param env The block schedule environment.
 239  * @param irn The node, which usages (successors) are to be made ready.
 240  */
 241 static void make_users_ready(block_sched_env_t *env, ir_node *irn)
 242 {
 243         const ir_edge_t *edge;
 244
 245         /* make all data users ready */
 246         foreach_out_edge(irn, edge) {
 247                 ir_node *user = get_edge_src_irn(edge);
 248
 249                 if (! is_Phi(user))
 250                         make_ready(env, irn, user);
 251         }
 252
 253         /* and the dependent nodes as well */
 254         foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
 255                 ir_node *user = get_edge_src_irn(edge);
 256
 257                 if (! is_Phi(user))
 258                         make_ready(env, irn, user);
 259         }
 260 }
 261
 262 /**
 263  * Returns the number of not yet schedules users.
 264  */
 265 static inline int get_irn_not_sched_user(block_sched_env_t *env, ir_node *n)
 266 {
 267         unsigned const idx = get_irn_idx(n);
 268
 269         assert(idx < ARR_LEN(env->sched_info));
 270         return env->sched_info[idx].num_not_sched_user;
 271 }
 272
 273 /**
 274  * Sets the number of not yet schedules users.
 275  */
 276 static inline void set_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num)
 277 {
 278         unsigned const idx = get_irn_idx(n);
 279
 280         assert(idx < ARR_LEN(env->sched_info));
 281         env->sched_info[idx].num_not_sched_user = num;
 282 }
 283
 284 /**
 285  * Add @p num to the number of not yet schedules users and returns the result.
 286  */
 287 static inline int add_irn_not_sched_user(block_sched_env_t *env, ir_node *n, int num)
 288 {
 289         unsigned const idx = get_irn_idx(n);
 290
 291         assert(idx < ARR_LEN(env->sched_info));
 292         env->sched_info[idx].num_not_sched_user += num;
 293         return env->sched_info[idx].num_not_sched_user;
 294 }
 295
 296 /**
 297  * Returns the number of users of a node having mode datab.
 298  */
 299 static int get_num_successors(ir_node *irn)
 300 {
 301         int             sum = 0;
 302         const ir_edge_t *edge;
 303
 304         if (get_irn_mode(irn) == mode_T) {
 305                 /* for mode_T nodes: count the users of all Projs */
 306                 foreach_out_edge(irn, edge) {
 307                         ir_node *proj = get_edge_src_irn(edge);
 308                         ir_mode *mode = get_irn_mode(proj);
 309
 310                         if (mode == mode_T) {
 311                                 sum += get_num_successors(proj);
 312                         } else if (mode_is_datab(mode)) {
 313                                 sum += get_irn_n_edges(proj);
 314                         }
 315                 }
 316         }
 317         else {
 318                 /* do not count keep-alive edges */
 319                 foreach_out_edge(irn, edge) {
 320                         if (get_irn_opcode(get_edge_src_irn(edge)) != iro_End)
 321                                 sum++;
 322                 }
 323         }
 324
 325         return sum;
 326 }
 327
 328 /**
 329  * Adds irn to @p live, updates all inputs that this user is scheduled
 330  * and counts all of its non scheduled users.
 331  */
 332 static void update_sched_liveness(block_sched_env_t *env, ir_node *irn)
 333 {
 334         int i;
 335
 336         /* ignore Projs */
 337         if (is_Proj(irn))
 338                 return;
 339
 340         for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
 341                 ir_node *in = get_irn_in_or_dep(irn, i);
 342
 343                 /* if in is a proj: update predecessor */
 344                 in = skip_Proj(in);
 345
 346                 /* if in is still in the live set: reduce number of users by one */
 347                 if (ir_nodeset_contains(&env->live, in)) {
 348                         if (add_irn_not_sched_user(env, in, -1) <= 0)
 349                                 ir_nodeset_remove(&env->live, in);
 350                 }
 351         }
 352
 353         /*
 354                 get_num_successors returns the number of all users. This includes
 355                 users in different blocks as well. As the each block is scheduled separately
 356                 the liveness info of those users will not be updated and so these
 357                 users will keep up the register pressure as it is desired.
 358         */
 359         i = get_num_successors(irn);
 360         if (i > 0) {
 361                 set_irn_not_sched_user(env, irn, i);
 362                 ir_nodeset_insert(&env->live, irn);
 363         }
 364 }
 365
 366 /**
 367  * Append an instruction to a schedule.
 368  * @param env The block scheduling environment.
 369  * @param irn The node to add to the schedule.
 370  * @return    The given node.
 371  */
 372 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
 373 {
 374     /* If the node consumes/produces data, it is appended to the schedule
 375      * list, otherwise, it is not put into the list */
 376     if (to_appear_in_schedule(irn)) {
 377                 update_sched_liveness(env, irn);
 378                 sched_add_before(env->block, irn);
 379
 380                 DBG((dbg, LEVEL_2, "\tadding %+F\n", irn));
 381
 382                 /* Remove the node from the ready set */
 383                 ir_nodeset_remove(&env->cands, irn);
 384     }
 385
 386         /* notify the selector about the finally selected node. */
 387         if (env->selector->node_selected)
 388                 env->selector->node_selected(env->selector_block_env, irn);
 389
 390     /* Insert the node in the set of all available scheduled nodes. */
 391     set_already_scheduled(env, irn);
 392
 393         make_users_ready(env, irn);
 394 }
 395
 396 /**
 397  * Perform list scheduling on a block.
 398  *
 399  * Note, that the caller must compute a linked list of nodes in the block
 400  * using the link field before calling this function.
 401  *
 402  * Also the outs must have been computed.
 403  *
 404  * @param block The block node.
 405  * @param env Scheduling environment.
 406  */
 407 static void list_sched_block(ir_node *block, void *env_ptr)
 408 {
 409         sched_env_t *env                      = (sched_env_t*)env_ptr;
 410         const list_sched_selector_t *selector = env->selector;
 411
 412         block_sched_env_t be;
 413         const ir_edge_t *edge;
 414         ir_node *irn;
 415         int j, m;
 416
 417         /* Initialize the block's list head that will hold the schedule. */
 418         sched_init_block(block);
 419
 420         /* Initialize the block scheduling environment */
 421         be.sched_info = env->sched_info;
 422         be.block      = block;
 423         ir_nodeset_init_size(&be.cands, get_irn_n_edges(block));
 424         ir_nodeset_init_size(&be.live, get_irn_n_edges(block));
 425         be.selector   = selector;
 426         be.sched_env  = env;
 427
 428         DBG((dbg, LEVEL_1, "scheduling %+F\n", block));
 429
 430         if (selector->init_block)
 431                 be.selector_block_env = selector->init_block(env->selector_env, block);
 432
 433         /* Then one can add all nodes are ready to the set. */
 434         foreach_out_edge(block, edge) {
 435                 ir_node   *irn  = get_edge_src_irn(edge);
 436                 unsigned   code = get_irn_opcode(irn);
 437                 int users;
 438
 439                 if (code == iro_End) {
 440                         /* Skip the end node because of keep-alive edges. */
 441                         continue;
 442                 }
 443
 444                 users = get_irn_n_edges(irn);
 445                 if (users == 0)
 446                         continue;
 447                 else if (users == 1) { /* ignore nodes that are only hold by the anchor */
 448                         const ir_edge_t *edge = get_irn_out_edge_first_kind(irn, EDGE_KIND_NORMAL);
 449                         ir_node *user = get_edge_src_irn(edge);
 450                         if (is_Anchor(user))
 451                                 continue;
 452                 }
 453
 454                 if (is_Phi(irn)) {
 455                         /*
 456                            Phi functions are scheduled immediately, since they only
 457                            transfer data flow from the predecessors to this block.
 458                         */
 459                         add_to_sched(&be, irn);
 460                 } else if (be_is_Start(irn)) {
 461                         /* The start block will be scheduled as the first node */
 462                         add_to_sched(&be, irn);
 463                 } else {
 464                         /* Other nodes must have all operands in other blocks to be made
 465                          * ready */
 466                         int ready = 1;
 467
 468                         /* Check, if the operands of a node are not local to this block */
 469                         for (j = 0, m = get_irn_ins_or_deps(irn); j < m; ++j) {
 470                                 ir_node *operand = get_irn_in_or_dep(irn, j);
 471
 472                                 if (get_nodes_block(operand) == block) {
 473                                         ready = 0;
 474                                         break;
 475                                 } else {
 476                                         /* live in values increase register pressure */
 477                                         ir_nodeset_insert(&be.live, operand);
 478                                 }
 479                         }
 480
 481                         /* Make the node ready, if all operands live in a foreign block */
 482                         if (ready) {
 483                                 DBG((dbg, LEVEL_2, "\timmediately ready: %+F\n", irn));
 484                                 make_ready(&be, NULL, irn);
 485                         }
 486                 }
 487         }
 488
 489         /* Iterate over all remaining nodes */
 490         while (ir_nodeset_size(&be.cands) > 0) {
 491                 ir_nodeset_iterator_t iter;
 492
 493                 /* Keeps must be scheduled immediately */
 494                 foreach_ir_nodeset(&be.cands, irn, iter) {
 495                         if (be_is_Keep(irn) || be_is_CopyKeep(irn) || is_Sync(irn)) {
 496                                 break;
 497                         }
 498                 }
 499
 500                 if (! irn) {
 501                         /* Keeps must be immediately scheduled */
 502                         irn = be.selector->select(be.selector_block_env, &be.cands, &be.live);
 503                 }
 504
 505                 DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 506
 507                 /* Add the node to the schedule. */
 508                 add_to_sched(&be, irn);
 509
 510                 /* remove the scheduled node from the ready list. */
 511                 ir_nodeset_remove(&be.cands, irn);
 512         }
 513
 514         if (selector->finish_block)
 515                 selector->finish_block(be.selector_block_env);
 516
 517         ir_nodeset_destroy(&be.cands);
 518         ir_nodeset_destroy(&be.live);
 519 }
 520
 521 /* List schedule a graph. */
 522 void list_sched(ir_graph *irg)
 523 {
 524         int num_nodes;
 525         sched_env_t env;
 526         mris_env_t *mris = NULL;
 527         const list_sched_selector_t *selector;
 528
 529         /* Select a scheduler based on backend options */
 530         switch (list_sched_options.select) {
 531                 case BE_SCHED_SELECT_TRIVIAL:  selector = &trivial_selector;      break;
 532                 case BE_SCHED_SELECT_RANDOM:   selector = &random_selector;       break;
 533                 case BE_SCHED_SELECT_REGPRESS: selector = &reg_pressure_selector; break;
 534                 case BE_SCHED_SELECT_MUCHNIK:  selector = &muchnik_selector;      break;
 535                 case BE_SCHED_SELECT_HEUR:     selector = &heuristic_selector;    break;
 536                 case BE_SCHED_SELECT_NORMAL:   selector = &normal_selector;       break;
 537                 default:
 538                 case BE_SCHED_SELECT_HMUCHNIK: selector = &heuristic_selector;    break;
 539         }
 540
 541 #if 1
 542         /* Matze: This is very slow, we should avoid it to improve backend speed,
 543          * we just have to make sure that we have no dangling out-edges at this
 544          * point...
 545          */
 546
 547         /* Assure, that we have no dangling out-edges to deleted stuff */
 548         edges_deactivate(irg);
 549         edges_activate(irg);
 550 #endif
 551
 552         switch (list_sched_options.prep) {
 553                 case BE_SCHED_PREP_MRIS:
 554                         mris = be_sched_mris_preprocess(irg);
 555                         break;
 556                 case BE_SCHED_PREP_RSS:
 557                         rss_schedule_preparation(irg);
 558                         break;
 559                 default:
 560                         break;
 561         }
 562
 563         num_nodes = get_irg_last_idx(irg);
 564
 565         /* initialize environment for list scheduler */
 566         memset(&env, 0, sizeof(env));
 567         env.selector   = selector;
 568         env.sched_info = NEW_ARR_F(sched_irn_t, num_nodes);
 569
 570         memset(env.sched_info, 0, num_nodes * sizeof(env.sched_info[0]));
 571
 572         if (env.selector->init_graph)
 573                 env.selector_env = env.selector->init_graph(env.selector, irg);
 574
 575         /* Schedule each single block. */
 576         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 577
 578         if (env.selector->finish_graph)
 579                 env.selector->finish_graph(env.selector_env);
 580
 581         if (list_sched_options.prep == BE_SCHED_PREP_MRIS)
 582                 be_sched_mris_free(mris);
 583
 584         DEL_ARR_F(env.sched_info);
 585 }
 586
 587 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched);
 588 void be_init_listsched(void)
 589 {
 590         lc_opt_entry_t *be_grp    = lc_opt_get_grp(firm_opt_get_root(), "be");
 591         lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "listsched");
 592
 593         lc_opt_add_table(sched_grp, list_sched_option_table);
 594
 595         FIRM_DBG_REGISTER(dbg, "firm.be.sched");
 596 }