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

   1 /**
   2  * Scheduling algorithms.
   3  * An ILP scheduler based on
   4  * "ILP-based Instruction Scheduling for IA-64"
   5  * by Daniel Kaestner and Sebastian Winkel
   6  *
   7  * @date   22.10.2005
   8  * @author Christian Wuerdig
   9  * @cvs-id $Id$
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #include "irnode_t.h"
  16 #include "irgwalk.h"
  17 #include "irbitset.h"
  18 #include "irphase_t.h"
  19 #include "iredges.h"
  20 #include "debug.h"
  21 #include "pdeq.h"
  22
  23 #include "be.h"
  24 #include "benode_t.h"
  25
  26 typedef struct _ilpsched_node_attr_t {
  27         unsigned asap;
  28         unsigned alap;
  29         unsigned visit_idx : 31;
  30         unsigned enqueued  : 1;
  31         bitset_t *transitive_block_nodes;
  32 } ilpsched_node_attr_t;
  33
  34 typedef struct _ilpsched_block_attr_t {
  35         unsigned n_interesting_nodes;
  36         ir_node  *head_root_nodes;
  37 } ilpsched_block_attr_t;
  38
  39 typedef union _ilpsched_attr_ {
  40         ilpsched_node_attr_t  node_attr;
  41         ilpsched_block_attr_t block_attr;
  42 } ilpsched_attr_t;
  43
  44 typedef struct {
  45         ir_node         *irn;
  46         ilpsched_attr_t attr;
  47 } be_ilpsched_irn_t;
  48
  49 typedef struct {
  50         phase_t  ph;
  51         ir_graph *irg;
  52         waitq    *alap_queue;
  53         DEBUG_ONLY(firm_dbg_module_t *dbg);
  54 } be_ilpsched_env_t;
  55
  56 #define get_ilpsched_irn(ilpsched_env, irn) (phase_get_or_set_irn_data(&(ilpsched_env)->ph, (irn)))
  57 #define is_ilpsched_block(node)             (is_Block((node)->irn))
  58 #define get_ilpsched_block_attr(block)      (&(block)->attr.block_attr)
  59 #define get_ilpsched_node_attr(node)        (&(node)->attr.node_attr)
  60
  61 #define foreach_linked_irns(head, iter) for ((iter) = (head); (iter); (iter) = get_irn_link((iter)))
  62
  63 #define consider_for_sched(irn) \
  64         (! (is_Block(irn) || is_Proj(irn) || is_Phi(irn) || be_is_Keep(irn) || is_NoMem(irn) || is_Jmp(irn)))
  65
  66 /**
  67  * In case there is no phase information for irn, initialize it.
  68  */
  69 static void *init_ilpsched_irn(phase_t *ph, ir_node *irn, void *old) {
  70         be_ilpsched_irn_t *res = old ? old : phase_alloc(ph, sizeof(res[0]));
  71
  72         if (res == old) {
  73                 /* if node has phase data and it's not a block: clear the bitset */
  74                 if (! is_Block(res->irn)) {
  75                         ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
  76                         bitset_clear_all(na->transitive_block_nodes);
  77                         na->visit_idx = 0;
  78                 }
  79                 return old;
  80         }
  81
  82         res->irn = irn;
  83
  84         if (is_Block(irn)) {
  85                 ilpsched_block_attr_t *ba = get_ilpsched_block_attr(res);
  86
  87                 ba->n_interesting_nodes = 0;
  88                 ba->head_root_nodes     = NULL;
  89         }
  90         else {
  91                 ilpsched_node_attr_t *na = get_ilpsched_node_attr(res);
  92
  93                 na->asap      = 0;
  94                 na->alap      = 0;
  95                 na->visit_idx = 0;
  96                 na->enqueued  = 0;
  97                 na->transitive_block_nodes = bitset_irg_obstack_alloc(phase_obst(ph), phase_get_irg(ph));
  98         }
  99
 100         return res;
 101 }
 102
 103 /**
 104  * Add all nodes having no user in current block to last_nodes list.
 105  */
 106 static void collect_alap_root_nodes(ir_node *irn, void *walk_env) {
 107         ir_node               *block;
 108         const ir_edge_t       *edge;
 109         be_ilpsched_env_t     *env;
 110         be_ilpsched_irn_t     *block_node;
 111         ilpsched_block_attr_t *ba;
 112         int                   has_block_user = 0;
 113
 114         if (! consider_for_sched(irn))
 115                 return;
 116
 117         block = get_nodes_block(irn);
 118
 119         foreach_out_edge(irn, edge) {
 120                 ir_node *user = get_edge_src_irn(edge);
 121
 122                 if (is_Proj(user)) {
 123                         const ir_edge_t *user_edge;
 124
 125                         if (get_irn_mode(user) == mode_X)
 126                                 continue;
 127
 128                         /* The ABI ensures, that there will be no ProjT nodes in the graph. */
 129                         foreach_out_edge(user, user_edge) {
 130                                 ir_node *real_user = get_edge_src_irn(user_edge);
 131
 132                                 if (! is_Phi(real_user) && get_nodes_block(real_user) == block) {
 133                                         has_block_user = 1;
 134                                         break;
 135                                 }
 136                         }
 137
 138                         if (has_block_user)
 139                                 break;
 140                 }
 141                 else if (is_Block(user)) {
 142                         continue;
 143                 }
 144                 else if (! is_Phi(user) && get_nodes_block(user) == block) {
 145                         has_block_user = 1;
 146                         break;
 147                 }
 148         }
 149
 150         env        = walk_env;
 151         block_node = get_ilpsched_irn(env, block);
 152         ba         = get_ilpsched_block_attr(block_node);
 153
 154         ba->n_interesting_nodes++;
 155
 156         /* current irn has no user inside this block */
 157         if (! has_block_user) {
 158                 set_irn_link(irn, ba->head_root_nodes);
 159                 ba->head_root_nodes = irn;
 160         }
 161 }
 162
 163 /**
 164  * Calculate the ASAP scheduling step for current irn.
 165  */
 166 static void calculate_irn_asap(ir_node *irn, void *walk_env) {
 167         be_ilpsched_irn_t *node;
 168         be_ilpsched_env_t *env = walk_env;
 169         int      i;
 170         unsigned idx;
 171         ir_node  *block;
 172         ilpsched_node_attr_t *na;
 173
 174         /* These nodes are handled separate */
 175         if (! consider_for_sched(irn))
 176                 return;
 177
 178         DBG((env->dbg, LEVEL_1, "Calculating ASAP of node %+F\n", irn));
 179
 180         node  = get_ilpsched_irn(env, irn);
 181         block = get_nodes_block(irn);
 182         idx   = get_irn_idx(irn);
 183         na    = get_ilpsched_node_attr(node);
 184
 185         /* accumulate all transitive predecessors of current node */
 186         for (i = get_irn_ins_or_deps(irn) - 1; i >= 0; --i) {
 187                 ir_node              *pred = skip_Proj(get_irn_in_or_dep(irn, i));
 188                 be_ilpsched_irn_t    *pred_node;
 189                 ilpsched_node_attr_t *pna;
 190
 191                 if (be_is_Keep(pred))
 192                         pred = skip_Proj(get_irn_n(pred, 0));
 193
 194                 if (is_Phi(pred) || block != get_nodes_block(pred) || is_NoMem(pred))
 195                         continue;
 196
 197                 pred_node = get_ilpsched_irn(env, pred);
 198                 pna       = get_ilpsched_node_attr(pred_node);
 199
 200                 assert(pna->asap && "missing ASAP of predecessor");
 201
 202                 /*
 203                         We have not already visited this predecessor
 204                         -> accumulate it's predecessors
 205                 */
 206                 if (pna->visit_idx != idx) {
 207                         pna->visit_idx = idx;
 208                         na->transitive_block_nodes = bitset_or(na->transitive_block_nodes, pna->transitive_block_nodes);
 209                         DBG((env->dbg, LEVEL_1, "\taccumulating preds of %+F\n", pred));
 210                 }
 211         }
 212
 213         /* every node is it's own transitive predecessor in block */
 214         bitset_set(na->transitive_block_nodes, idx);
 215
 216         /* asap = number of transitive predecessors in this block */
 217         na->asap = bitset_popcnt(na->transitive_block_nodes);
 218
 219         DBG((env->dbg, LEVEL_1, "\tcalculated ASAP is %u\n", na->asap));
 220 }
 221
 222 /**
 223  * Accumulate the successors of all nodes from irn on upwards.
 224  */
 225 static void accumulate_succs(be_ilpsched_env_t *env, ir_node *irn) {
 226         unsigned             i, n;
 227         unsigned             idx    = get_irn_idx(irn);
 228         be_ilpsched_irn_t    *node  = get_ilpsched_irn(env, irn);
 229         ilpsched_node_attr_t *na    = get_ilpsched_node_attr(node);
 230         ir_node              *block = get_nodes_block(irn);
 231         waitq                *wq    = new_waitq();
 232
 233         DBG((env->dbg, LEVEL_1, "\taccumulating succs of %+F\n", irn));
 234
 235         /* enqueue node for final alap calculation */
 236         if (! na->enqueued) {
 237                 be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
 238                 ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
 239
 240                 na->enqueued = 1;
 241                 na->alap     = ba->n_interesting_nodes;
 242                 waitq_put(env->alap_queue, node);
 243                 DBG((env->dbg, LEVEL_2, "\t\tenqueueing %+F for final ALAP calculation\n", irn));
 244         }
 245
 246         for (i = 0, n = get_irn_ins_or_deps(irn); i < n; ++i) {
 247                 ir_node              *pred = skip_Proj(get_irn_in_or_dep(irn, i));
 248                 be_ilpsched_irn_t    *pred_node;
 249                 ilpsched_node_attr_t *pna;
 250
 251                 if (be_is_Keep(pred))
 252                         pred = skip_Proj(get_irn_n(pred, 0));
 253
 254                 if (is_Phi(pred) || block != get_nodes_block(pred) || is_NoMem(pred))
 255                         continue;
 256
 257                 pred_node = get_ilpsched_irn(env, pred);
 258                 pna       = get_ilpsched_node_attr(pred_node);
 259
 260                 /* accumulate the successors */
 261                 if (pna->visit_idx != idx) {
 262                         pna->visit_idx = idx;
 263                         pna->transitive_block_nodes = bitset_or(pna->transitive_block_nodes, na->transitive_block_nodes);
 264
 265                         /* set current node as successor */
 266                         bitset_set(pna->transitive_block_nodes, idx);
 267                         waitq_put(wq, pred);
 268
 269                         DBG((env->dbg, LEVEL_1, "\taccumulating succs of %+F to %+F\n", irn, pred));
 270                 }
 271         }
 272
 273         /* process all predecessors */
 274         while (! waitq_empty(wq)) {
 275                 accumulate_succs(env, waitq_get(wq));
 276         }
 277 }
 278
 279 /**
 280  * Calculate the ALAP scheduling step of all irns in current block.
 281  * Depends on ASAP beeing calculated.
 282  */
 283 static void calculate_block_alap(ir_node *block, void *walk_env) {
 284         be_ilpsched_env_t     *env        = walk_env;
 285         be_ilpsched_irn_t     *block_node = get_ilpsched_irn(env, block);
 286         ilpsched_block_attr_t *ba         = get_ilpsched_block_attr(block_node);
 287         bitset_t              *alap_bs    = bitset_irg_alloca(env->irg);
 288         ir_node *root;
 289
 290         assert(is_Block(block));
 291
 292         DBG((env->dbg, LEVEL_1, "Calculating ALAP for nodes in %+F (%u nodes)\n", block, ba->n_interesting_nodes));
 293
 294         phase_reinit_block_irn_data(&env->ph, block);
 295
 296         /* calculate the alap of all nodes, starting at collected roots upwards */
 297         foreach_linked_irns(ba->head_root_nodes, root) {
 298                 accumulate_succs(env, root);
 299         }
 300
 301         /* all interesting nodes should have their successors accumulated now */
 302         while (! waitq_empty(env->alap_queue)) {
 303                 be_ilpsched_irn_t    *node = waitq_get(env->alap_queue);
 304                 ilpsched_node_attr_t *na   = get_ilpsched_node_attr(node);
 305
 306                 na->alap -= bitset_popcnt(na->transitive_block_nodes);
 307                 DBG((env->dbg, LEVEL_1, "\tALAP of %+F is %u (%u succs)\n", node->irn, na->alap, bitset_popcnt(na->transitive_block_nodes)));
 308         }
 309 }
 310
 311 void be_ilp_sched(const be_irg_t *birg) {
 312         be_ilpsched_env_t env;
 313
 314         FIRM_DBG_REGISTER(env.dbg, "firm.be.sched.ilp");
 315
 316         //firm_dbg_set_mask(env.dbg, 31);
 317
 318         env.irg        = birg->irg;
 319         env.alap_queue = new_waitq();
 320         phase_init(&env.ph, "be ilp scheduling", env.irg, PHASE_DEFAULT_GROWTH, init_ilpsched_irn);
 321
 322         irg_walk_graph(env.irg, collect_alap_root_nodes, calculate_irn_asap, &env);
 323         irg_block_walk_graph(env.irg, NULL, calculate_block_alap, &env);
 324
 325         del_waitq(env.alap_queue);
 326         phase_free(&env.ph);
 327 }