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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Primitive list scheduling with different node selectors.
   9  * @author      Sebastian Hack
  10  * @date        20.10.2004
  11  */
  12 #include "config.h"
  13
  14 #include <stdio.h>
  15 #include <stdarg.h>
  16 #include <string.h>
  17 #include <limits.h>
  18 #include <stdbool.h>
  19
  20 #include "benode.h"
  21 #include "be_t.h"
  22
  23 #include "obst.h"
  24 #include "list.h"
  25
  26 #include "iredges_t.h"
  27 #include "irgwalk.h"
  28 #include "irnode_t.h"
  29 #include "irmode_t.h"
  30 #include "irdump.h"
  31 #include "irprintf.h"
  32 #include "array.h"
  33 #include "debug.h"
  34 #include "irtools.h"
  35
  36 #include "bemodule.h"
  37 #include "besched.h"
  38 #include "beutil.h"
  39 #include "belive_t.h"
  40 #include "belistsched.h"
  41 #include "bearch.h"
  42 #include "bestat.h"
  43
  44 #include "lc_opts.h"
  45 #include "lc_opts_enum.h"
  46
  47 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  48
  49 /**
  50  * Scheduling environment for the whole graph.
  51  */
  52 typedef struct sched_env_t {
  53         unsigned *scheduled;                   /**< bitset of already scheduled nodes */
  54         const list_sched_selector_t *selector; /**< The node selector. */
  55         void *selector_env;                    /**< A pointer to give to the selector. */
  56 } sched_env_t;
  57
  58 /**
  59  * Environment for a block scheduler.
  60  */
  61 typedef struct block_sched_env_t {
  62         /** scheduling info per node, copied from the global scheduler object */
  63         unsigned                    *scheduled;
  64         /** the set of candidates */
  65         ir_nodeset_t                 cands;
  66         ir_node                     *block;     /**< the current block */
  67         sched_env_t                 *sched_env; /**< the scheduler environment */
  68         const list_sched_selector_t *selector;
  69         void                        *selector_block_env;
  70 } block_sched_env_t;
  71
  72 /**
  73  * Returns non-zero if the node is already scheduled
  74  */
  75 static bool is_already_scheduled(const sched_env_t *env, ir_node *n)
  76 {
  77         unsigned idx = get_irn_idx(n);
  78         return rbitset_is_set(env->scheduled, idx);
  79 }
  80
  81 /**
  82  * Mark a node as already scheduled
  83  */
  84 static void set_already_scheduled(sched_env_t *env, ir_node *n)
  85 {
  86         unsigned idx = get_irn_idx(n);
  87         rbitset_set(env->scheduled, idx);
  88 }
  89
  90 static void selected(block_sched_env_t *env, ir_node *irn);
  91 static void add_to_sched(block_sched_env_t *env, ir_node *irn);
  92
  93 /**
  94  * Put a node in the ready set, or make it available immediately if it doesn't
  95  * need to be scheduled
  96  */
  97 static void node_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
  98 {
  99         if (is_Proj(irn)
 100             || (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled)) {
 101                 selected(env, irn);
 102                 DB((dbg, LEVEL_3, "\tmaking immediately available: %+F\n", irn));
 103         } else if (be_is_Keep(irn) || be_is_CopyKeep(irn)) {
 104                 /* Keeps must be scheduled immediately */
 105                 add_to_sched(env, irn);
 106         } else {
 107                 ir_nodeset_insert(&env->cands, irn);
 108
 109                 /* Notify selector about the ready node. */
 110                 if (env->selector->node_ready)
 111                         env->selector->node_ready(env->selector_block_env, irn, pred);
 112
 113                 DB((dbg, LEVEL_2, "\tmaking ready: %+F\n", irn));
 114         }
 115 }
 116
 117 /**
 118  * Try to put a node in the ready set.
 119  * @param env   The block scheduler environment.
 120  * @param pred  The previous scheduled node.
 121  * @param irn   The node to make ready.
 122  * @return 1, if the node could be made ready, 0 else.
 123  */
 124 static void try_make_ready(block_sched_env_t *env, ir_node *pred, ir_node *irn)
 125 {
 126         int i, n;
 127
 128         /* we schedule one block at a time, so no need to consider users in other
 129          * blocks */
 130         if (is_Block(irn) || get_nodes_block(irn) != env->block)
 131                 return;
 132         if (is_Phi(irn) || is_End(irn))
 133                 return;
 134         /* check if all operands are already available */
 135         n = get_irn_ins_or_deps(irn);
 136         for (i = 0; i < n; ++i) {
 137                 ir_node *op = get_irn_in_or_dep(irn, i);
 138
 139                 /* If the operand is local to the scheduled block and not yet
 140                  * scheduled, this nodes cannot be made ready, so exit. */
 141                 if (get_nodes_block(op) == env->block
 142                                 && !is_already_scheduled(env->sched_env, op))
 143                         return;
 144         }
 145
 146         node_ready(env, pred, irn);
 147 }
 148
 149 static void selected(block_sched_env_t *env, ir_node *node)
 150 {
 151         /* notify the selector about the finally selected node. */
 152         if (env->selector->node_selected)
 153                 env->selector->node_selected(env->selector_block_env, node);
 154
 155     /* Insert the node in the set of all available scheduled nodes. */
 156     set_already_scheduled(env->sched_env, node);
 157
 158     /* check users, they might be ready now */
 159         foreach_out_edge(node, edge) {
 160                 ir_node *user = get_edge_src_irn(edge);
 161                 try_make_ready(env, node, user);
 162         }
 163         foreach_out_edge_kind(node, edge, EDGE_KIND_DEP) {
 164                 ir_node *user = get_edge_src_irn(edge);
 165                 try_make_ready(env, node, user);
 166         }
 167 }
 168
 169 /**
 170  * Append an instruction to a schedule.
 171  * @param env The block scheduling environment.
 172  * @param irn The node to add to the schedule.
 173  * @return    The given node.
 174  */
 175 static void add_to_sched(block_sched_env_t *env, ir_node *irn)
 176 {
 177         assert(! (arch_get_irn_flags(irn) & arch_irn_flags_not_scheduled));
 178
 179         sched_add_before(env->block, irn);
 180
 181         DB((dbg, LEVEL_2, "\tschedule %+F\n", irn));
 182
 183         /* Remove the node from the ready set */
 184         ir_nodeset_remove(&env->cands, irn);
 185
 186         selected(env, irn);
 187 }
 188
 189 /**
 190  * Perform list scheduling on a block.
 191  *
 192  * Note, that the caller must compute a linked list of nodes in the block
 193  * using the link field before calling this function.
 194  *
 195  * Also the outs must have been computed.
 196  *
 197  * @param block The block node.
 198  * @param env Scheduling environment.
 199  */
 200 static void list_sched_block(ir_node *block, void *env_ptr)
 201 {
 202         sched_env_t *env                      = (sched_env_t*)env_ptr;
 203         const list_sched_selector_t *selector = env->selector;
 204
 205         block_sched_env_t be;
 206         ir_nodeset_t *cands = &be.cands;
 207
 208         /* Initialize the block's list head that will hold the schedule. */
 209         sched_init_block(block);
 210
 211         /* Initialize the block scheduling environment */
 212         be.block     = block;
 213         be.selector  = selector;
 214         be.sched_env = env;
 215         ir_nodeset_init_size(cands, get_irn_n_edges(block));
 216
 217         DB((dbg, LEVEL_1, "scheduling %+F\n", block));
 218
 219         if (selector->init_block)
 220                 be.selector_block_env = selector->init_block(env->selector_env, block);
 221
 222         /* Then one can add all nodes are ready to the set. */
 223         foreach_out_edge(block, edge) {
 224                 ir_node *irn = get_edge_src_irn(edge);
 225
 226                 if (is_Phi(irn)) {
 227                         /* Phi functions are scheduled immediately, since they only
 228                          * transfer data flow from the predecessors to this block. */
 229                         add_to_sched(&be, irn);
 230                 } else if (be_is_Start(irn)) {
 231                         /* The start block will be scheduled as the first node */
 232                         add_to_sched(&be, irn);
 233                 } else {
 234                         try_make_ready(&be, NULL, irn);
 235                 }
 236         }
 237
 238         /* Iterate over all remaining nodes */
 239         while (ir_nodeset_size(cands) > 0) {
 240                 ir_node *irn = be.selector->select(be.selector_block_env, cands);
 241                 DB((dbg, LEVEL_2, "\tpicked node %+F\n", irn));
 242
 243                 /* remove the scheduled node from the ready list. */
 244                 ir_nodeset_remove(cands, irn);
 245                 /* Add the node to the schedule. */
 246                 add_to_sched(&be, irn);
 247         }
 248
 249         ir_nodeset_destroy(cands);
 250
 251         if (selector->finish_block)
 252                 selector->finish_block(be.selector_block_env);
 253 }
 254
 255 /* List schedule a graph. */
 256 void be_list_sched_graph(ir_graph *irg, const list_sched_selector_t *selector)
 257 {
 258         int num_nodes;
 259         sched_env_t env;
 260
 261         /* Matze: This is very slow, we should avoid it to improve backend speed,
 262          * we just have to make sure that we have no dangling out-edges at this
 263          * point...
 264          */
 265         edges_deactivate(irg);
 266         edges_activate(irg);
 267
 268         num_nodes = get_irg_last_idx(irg);
 269
 270         /* initialize environment for list scheduler */
 271         memset(&env, 0, sizeof(env));
 272         env.selector  = selector;
 273         env.scheduled = rbitset_malloc(num_nodes);
 274
 275         if (selector->init_graph != NULL)
 276                 env.selector_env = selector->init_graph(irg);
 277
 278         /* Schedule each single block. */
 279         irg_block_walk_graph(irg, list_sched_block, NULL, &env);
 280
 281         if (selector->finish_graph != NULL)
 282                 selector->finish_graph(env.selector_env);
 283
 284         free(env.scheduled);
 285 }
 286
 287 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_listsched)
 288 void be_init_listsched(void)
 289 {
 290         FIRM_DBG_REGISTER(dbg, "firm.be.sched");
 291 }