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 #include <stdbool.h>
  34
  35 #include "benode.h"
  36 #include "be_t.h"
  37
  38 #include "obst.h"
  39 #include "list.h"
  40 #include "iterator.h"
  41
  42 #include "iredges_t.h"
  43 #include "irgwalk.h"
  44 #include "irnode_t.h"
  45 #include "irmode_t.h"
  46 #include "irdump.h"
  47 #include "irprintf_t.h"
  48 #include "array.h"
  49 #include "debug.h"
  50 #include "irtools.h"
  51
  52 #include "bemodule.h"
  53 #include "besched.h"
  54 #include "beutil.h"
  55 #include "belive_t.h"
  56 #include "belistsched.h"
  57 #include "bearch.h"
  58 #include "bestat.h"
  59 #include "beirg.h"
  60
  61 #include "lc_opts.h"
  62 #include "lc_opts_enum.h"
  63
  64 /* we have prolog, "normal" and epilog */
  65 #define N_PRIORITY_CLASSES  3
  66
  67 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL);
  68
  69 /**
  70  * Scheduling environment for the whole graph.
  71  */
  72 typedef struct sched_env_t {
  73         unsigned *scheduled;                   /**< bitset of already scheduled nodes */
  74         const list_sched_selector_t *selector; /**< The node selector. */
  75         void *selector_env;                    /**< A pointer to give to the selector. */
  76 } sched_env_t;
  77
  78 /**
  79  * Environment for a block scheduler.
  80  */
  81 typedef struct block_sched_env_t {
  82         /** scheduling info per node, copied from the global scheduler object */
  83         unsigned                    *scheduled;
  84         /** the set of candidates */
  85         ir_nodeset_t                 cands[N_PRIORITY_CLASSES];
  86         ir_node                     *block;     /**< the current block */
  87         sched_env_t                 *sched_env; /**< the scheduler environment */
  88         const list_sched_selector_t *selector;
  89         void                        *selector_block_env;
  90 } block_sched_env_t;
  91
  92 /**
  93  * map prolog/normal/epilog into 3 priority levels
  94  */
  95 static unsigned get_priority(const ir_node *node)
  96 {
  97         arch_irn_flags_t flags = arch_irn_get_flags(node);
  98         if (flags & arch_irn_flags_prolog) {
  99                 assert(! (flags & arch_irn_flags_epilog));
 100                 return 0;
 101         } else if (flags & arch_irn_flags_epilog) {
 102                 return 2;
 103         }
 104         return 1;
 105 }
 106
 107 /**
 108  * Returns non-zero if the node is already scheduled
 109  */
 110 static bool is_already_scheduled(const sched_env_t *env, ir_node *n)
 111 {
 112         unsigned idx = get_irn_idx(n);
 113         return rbitset_is_set(env->scheduled, idx);
 114 }
 115
 116 /**
 117  * Mark a node as already scheduled
 118  */
 119 static void set_already_scheduled(sched_env_t *env, ir_node *n)
 120 {
 121         unsigned idx = get_irn_idx(n);
 122         rbitset_set(env->scheduled, idx);
 123 }
 124
 125 static void selected(block_sched_env_t *env, ir_node *irn);
 126 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
 127
 128 /**
 129  * Put a node in the ready set, or make it available immediately if it doesn't
 130  * need to be scheduled
 131  */
 132 static void node_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 133 {
 134         if (is_Proj(irn)
 135             || (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled)) {
 136                 selected(env, irn);
 137                 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
 138         } else if (be_is_Keep(irn) || be_is_CopyKeep(irn)) {
 139                 /* Keeps must be scheduled immediately */
 140                 add_to_sched(env, irn);
 141         } else {
 142                 unsigned priority = get_priority(irn);
 143                 ir_nodeset_insert(&env->cands[priority], irn);
 144
 145                 /* Notify selector about the ready node. */
 146                 if (env->selector->node_ready)
 147                         env->selector->node_ready(env->selector_block_env, irn, pred);
 148
 149                 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 150         }
 151 }
 152
 153 /**
 154  * Try to put a node in the ready set.
 155  * @param env   The block scheduler environment.
 156  * @param pred  The previous scheduled node.
 157  * @param irn   The node to make ready.
 158  * @return 1, if the node could be made ready, 0 else.
 159  */
 160 static void try_make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 161 {
 162         int i, n;
 163
 164         /* we schedule one block at a time, so no need to consider users in other
 165          * blocks */
 166         if (is_Block(irn) || get_nodes_block(irn) != env->block)
 167                 return;
 168         if (is_Phi(irn) || is_End(irn))
 169                 return;
 170         /* check if all operands are already available */
 171         n = get_irn_ins_or_deps(irn);
 172         for (i = 0; i < n; ++i) {
 173                 ir_node *op = get_irn_in_or_dep(irn, i);
 174
 175                 /* If the operand is local to the scheduled block and not yet
 176                  * scheduled, this nodes cannot be made ready, so exit. */
 177                 if (get_nodes_block(op) == env->block
 178                                 && !is_already_scheduled(env->sched_env, op))
 179                         return;
 180         }
 181
 182         node_ready(env, pred, irn);
 183 }
 184
 185 static void selected(block_sched_env_t *env, ir_node *node)
 186 {
 187         const ir_edge_t *edge;
 188
 189         /* notify the selector about the finally selected node. */
 190         if (env->selector->node_selected)
 191                 env->selector->node_selected(env->selector_block_env, node);
 192
 193     /* Insert the node in the set of all available scheduled nodes. */
 194     set_already_scheduled(env->sched_env, node);
 195
 196     /* check users, they might be ready now */
 197         foreach_out_edge(node, edge) {
 198                 ir_node *user = get_edge_src_irn(edge);
 199                 try_make_ready(env, node, user);
 200         }
 201         foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) {
 202                 ir_node *user = get_edge_src_irn(edge);
 203                 try_make_ready(env, node, user);
 204         }
 205 }
 206
 207 /**
 208  * Append an instruction to a schedule.
 209  * @param env The block scheduling environment.
 210  * @param irn The node to add to the schedule.
 211  * @return    The given node.
 212  */
 213 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
 214 {
 215         unsigned priority = get_priority(irn);
 216
 217         assert(! (arch_irn_get_flags(irn) & arch_irn_flags_not_scheduled));
 218
 219         sched_add_before(env->block, irn);
 220
 221         DB((dbg, LEVEL_2, "\tschedule %+F\n", irn));
 222
 223         /* Remove the node from the ready set */
 224         ir_nodeset_remove(&env->cands[priority], irn);
 225
 226         selected(env, irn);
 227 }
 228
 229 /**
 230  * Perform list scheduling on a block.
 231  *
 232  * Note, that the caller must compute a linked list of nodes in the block
 233  * using the link field before calling this function.
 234  *
 235  * Also the outs must have been computed.
 236  *
 237  * @param block The block node.
 238  * @param env Scheduling environment.
 239  */
 240 static void list_sched_block(ir_node *block, void *env_ptr)
 241 {
 242         sched_env_t *env                      = (sched_env_t*)env_ptr;
 243         const list_sched_selector_t *selector = env->selector;
 244
 245         block_sched_env_t be;
 246         const ir_edge_t *edge;
 247         unsigned p;
 248
 249         /* Initialize the block's list head that will hold the schedule. */
 250         sched_init_block(block);
 251
 252         /* Initialize the block scheduling environment */
 253         be.block     = block;
 254         be.selector  = selector;
 255         be.sched_env = env;
 256         for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
 257                 ir_nodeset_init_size(&be.cands[p], get_irn_n_edges(block));
 258         }
 259
 260         DB((dbg, LEVEL_1, "scheduling %+F\n", block));
 261
 262         if (selector->init_block)
 263                 be.selector_block_env = selector->init_block(env->selector_env, block);
 264
 265         /* Then one can add all nodes are ready to the set. */
 266         foreach_out_edge(block, edge) {
 267                 ir_node *irn = get_edge_src_irn(edge);
 268
 269                 if (is_Phi(irn)) {
 270                         /* Phi functions are scheduled immediately, since they only
 271                          * transfer data flow from the predecessors to this block. */
 272                         add_to_sched(&be, irn);
 273                 } else if (be_is_Start(irn)) {
 274                         /* The start block will be scheduled as the first node */
 275                         add_to_sched(&be, irn);
 276                 } else {
 277                         try_make_ready(&be, NULL, irn);
 278                 }
 279         }
 280
 281         /* Iterate over all remaining nodes */
 282         for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
 283                 ir_nodeset_t *p_cands = &be.cands[p];
 284                 while (ir_nodeset_size(p_cands) > 0) {
 285                         ir_node *irn = be.selector->select(be.selector_block_env, p_cands);
 286                         DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 287
 288                         /* remove the scheduled node from the ready list. */
 289                         ir_nodeset_remove(p_cands, irn);
 290                         /* Add the node to the schedule. */
 291                         add_to_sched(&be, irn);
 292                 }
 293         }
 294
 295         if (selector->finish_block)
 296                 selector->finish_block(be.selector_block_env);
 297
 298         for (p = 0; p < N_PRIORITY_CLASSES; ++p) {
 299                 /** all cand lists should be empty. Otherwise there was some invalid
 300                  * dependencies between priority classes (ie. priority 0 value depending
 301                  * on a priority 1 value) */
 302                 assert(ir_nodeset_size(&be.cands[p]) == 0);
 303                 ir_nodeset_init_size(&be.cands[p], get_irn_n_edges(block));
 304         }
 305 }
 306
 307 /* List schedule a graph. */
 308 void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector)
 309 {
 310         int num_nodes;
 311         sched_env_t env;
 312
 313         /* Matze: This is very slow, we should avoid it to improve backend speed,
 314          * we just have to make sure that we have no dangling out-edges at this
 315          * point...
 316          */
 317         edges_deactivate(irg);
 318         edges_activate(irg);
 319
 320         num_nodes = get_irg_last_idx(irg);
 321
 322         /* initialize environment for list scheduler */
 323         memset(&env, 0, sizeof(env));
 324         env.selector  = selector;
 325         env.scheduled = rbitset_malloc(num_nodes);
 326
 327         if (selector->init_graph != NULL)
 328                 env.selector_env = selector->init_graph(irg);
 329
 330         /* Schedule each single block. */
 331         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 332
 333         if (selector->finish_graph != NULL)
 334                 selector->finish_graph(env.selector_env);
 335
 336         free(env.scheduled);
 337 }
 338
 339 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched);
 340 void be_init_listsched(void)
 341 {
 342         FIRM_DBG_REGISTER(dbg, "firm.be.sched");
 343 }