nsz Git - libfirm/blob - ir/ir/irgwalk_blk.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/irgwalk_blk.c
   4  * Purpose:
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 # include "config.h"
  14 #endif
  15
  16 #include "irnode_t.h"
  17 #include "irgraph_t.h" /* visited flag */
  18 #include "irgwalk.h"
  19 #include "pset.h"
  20 #include "irhooks.h"
  21 #include "array.h"
  22
  23 /**
  24  * Metadata for block walker
  25  */
  26 typedef struct _blk_collect_data_t {
  27   struct obstack obst;        /**< obstack to allocate objects on */
  28   pset           *blk_map;    /**< Hash map: Block -> List */
  29   ir_node        **blk_list;  /**< the Block list */
  30 } blk_collect_data_t;
  31
  32 /**
  33  * An entry for a block in the blk_map
  34  */
  35 typedef struct _block_entry_t {
  36   ir_node *block;       /**< the block */
  37   ir_node **phi_list;   /**< the list of Phi instruction */
  38   ir_node **df_list;    /**< the list of data flow instruction */
  39   ir_node **cf_list;    /**< the list of control flow instructions */
  40   ir_node **entry_list; /**< list of all block entries */
  41 } block_entry_t;
  42
  43 /**
  44  * compare two block_entries
  45  */
  46 static int addr_cmp(const void *elt, const void *key) {
  47   const block_entry_t *e1 = elt;
  48   const block_entry_t *e2 = key;
  49
  50   return e1->block != e2->block;
  51 }
  52
  53 /**
  54  * calculates a hash value for an block address
  55  * Addresses are typically aligned at 32bit, so we ignore the lowest bits
  56  */
  57 static INLINE unsigned block_hash(const ir_node *node) {
  58   return (unsigned)node >> 3;
  59 }
  60
  61 /**
  62  * Returns the associates block_entry_t for an block
  63  */
  64 static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx)
  65 {
  66   block_entry_t key;
  67   block_entry_t *elem;
  68
  69   key.block = block;
  70   elem = pset_find(ctx->blk_map, &key, block_hash(block));
  71   if (elem)
  72     return elem;
  73
  74   elem = obstack_alloc(&ctx->obst, sizeof(*elem));
  75
  76   elem->block      = block;
  77   elem->phi_list   = NEW_ARR_F(ir_node *, 0);
  78   elem->df_list    = NEW_ARR_F(ir_node *, 0);
  79   elem->cf_list    = NEW_ARR_F(ir_node *, 0);
  80   elem->entry_list = NEW_ARR_F(ir_node *, 0);
  81
  82   return pset_insert(ctx->blk_map, elem, block_hash(block));
  83 }
  84
  85 /**
  86  * traverse the pre order only, from End to Start
  87  */
  88 static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env)
  89 {
  90   int i, j;
  91
  92   for (i = ARR_LEN(blks->blk_list) - 1; i >= 0; --i) {
  93     ir_node       *block = blks->blk_list[i];
  94     block_entry_t *entry = block_find_entry(block, blks);
  95
  96     for (j = ARR_LEN(entry->cf_list) - 1; j >= 0; --j) {
  97       ir_node *node = entry->cf_list[j];
  98       pre(node, env);
  99     }
 100
 101     for (j = ARR_LEN(entry->df_list) - 1; j >= 0; --j) {
 102       ir_node *node = entry->df_list[j];
 103       pre(node, env);
 104     }
 105
 106     for (j = ARR_LEN(entry->phi_list) - 1; j >= 0; --j) {
 107       ir_node *node = entry->phi_list[j];
 108       pre(node, env);
 109     }
 110
 111     pre(block, env);
 112
 113     DEL_ARR_F(entry->entry_list);
 114     DEL_ARR_F(entry->phi_list);
 115     DEL_ARR_F(entry->df_list);
 116     DEL_ARR_F(entry->cf_list);
 117   }
 118 }
 119
 120 /**
 121  * traverse the post order only, from Start to End
 122  */
 123 static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env)
 124 {
 125   int i, j;
 126
 127   for (i = 0; i < ARR_LEN(blks->blk_list); ++i) {
 128     ir_node       *block = blks->blk_list[i];
 129     block_entry_t *entry = block_find_entry(block, blks);
 130
 131     post(block, env);
 132
 133     for (j = 0; j < ARR_LEN(entry->phi_list); ++j) {
 134       ir_node *node = entry->phi_list[j];
 135       post(node, env);
 136     }
 137
 138     for (j = 0; j < ARR_LEN(entry->df_list); ++j) {
 139       ir_node *node = entry->df_list[j];
 140       post(node, env);
 141     }
 142
 143     for (j = 0; j < ARR_LEN(entry->cf_list); ++j) {
 144       ir_node *node = entry->cf_list[j];
 145       post(node, env);
 146     }
 147
 148     DEL_ARR_F(entry->entry_list);
 149     DEL_ARR_F(entry->phi_list);
 150     DEL_ARR_F(entry->df_list);
 151     DEL_ARR_F(entry->cf_list);
 152   }
 153 }
 154
 155 /**
 156  * traverse both
 157  */
 158 static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 159 {
 160   int i, j;
 161
 162   for (i = ARR_LEN(blks->blk_list) - 1; i >= 0; --i) {
 163     ir_node       *block = blks->blk_list[i];
 164     block_entry_t *entry = block_find_entry(block, blks);
 165
 166     for (j = ARR_LEN(entry->cf_list) - 1; j >= 0; --j) {
 167       ir_node *node = entry->cf_list[j];
 168       pre(node, env);
 169     }
 170
 171     for (j = ARR_LEN(entry->df_list) - 1; j >= 0; --j) {
 172       ir_node *node = entry->df_list[j];
 173       pre(node, env);
 174     }
 175
 176     for (j = ARR_LEN(entry->phi_list) - 1; j >= 0; --j) {
 177       ir_node *node = entry->phi_list[j];
 178       pre(node, env);
 179     }
 180
 181     pre(block, env);
 182   }
 183
 184   /* second step */
 185   traverse_post(blks, post, env);
 186 }
 187
 188
 189 /**
 190  * Do the traversal
 191  */
 192 static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 193 {
 194   if      (!post) traverse_pre (blks, pre, env);
 195   else if (!pre)  traverse_post(blks, post, env);
 196   else            traverse_both(blks, pre, post, env);
 197 }
 198
 199
 200 /**
 201  * walks over the graph and collects all blocks and all block entries
 202  */
 203 static void collect_walk(ir_node *node, blk_collect_data_t *env)
 204 {
 205   int           i, is_phi;
 206   block_entry_t *entry;
 207   ir_node       *block;
 208
 209   mark_irn_visited(node);
 210
 211   if (node->op == op_Block) {
 212     /* predecessors of a block are control flow nodes */
 213     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 214       ir_node *pred = get_irn_n(node, i);
 215       ir_node *blk  = get_nodes_block(pred);
 216
 217       if (irn_not_visited(pred)) {
 218         collect_walk(pred, env);
 219
 220         /* control flow predecessors are always block inputs */
 221         entry = block_find_entry(blk, env);
 222         ARR_APP1(ir_node *, entry->entry_list, pred);
 223       }
 224     }
 225
 226     /* it's a block, put it into the block list */
 227     if (node == get_irg_end_block(current_ir_graph)) {
 228       /* Put the end block always last. If we don't do it here,
 229        * it might be placed elsewhere if the graph contains
 230        * endless loops.
 231        */
 232     }
 233     else {
 234       ARR_APP1(ir_node *, env->blk_list, node);
 235     }
 236   }
 237   else {
 238     block = get_nodes_block(node);
 239
 240     if (irn_not_visited(block))
 241       collect_walk(block, env);
 242
 243     is_phi = is_Phi(node);
 244     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 245       ir_node *pred = get_irn_n(node, i);
 246
 247       if (irn_not_visited(pred)) {
 248         collect_walk(pred, env);
 249
 250       /* BEWARE: predecessors of End nodes might be blocks */
 251       if (is_no_Block(pred)) {
 252         ir_node *blk  = get_nodes_block(pred);
 253
 254           /*
 255            * Note that Phi predecessors are always block entries
 256            * because Phi edges are always "outside" a block
 257            */
 258           if (block != blk || is_phi) {
 259             entry = block_find_entry(blk, env);
 260             ARR_APP1(ir_node *, entry->entry_list, pred);
 261           }
 262         }
 263       }
 264     }
 265   }
 266 }
 267
 268 /**
 269  * walks over the nodes of a block
 270  * and collects them into the right list
 271  */
 272 static void collect_blks_lists(ir_node *node, ir_node *block,
 273                                block_entry_t *entry, blk_collect_data_t *env)
 274 {
 275   int i;
 276
 277   mark_irn_visited(node);
 278
 279   /*
 280    * Do not descent into Phi predecessors, these are always
 281    * outside the current block because Phi edges are always
 282    * "outside".
 283    */
 284   if (! is_Phi(node)) {
 285     for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 286       ir_node *pred = get_irn_n(node, i);
 287
 288       /* BEWARE: predecessors of End nodes might be blocks */
 289       if (is_no_Block(pred)) {
 290         ir_node *blk  = get_nodes_block(pred);
 291
 292         if (irn_not_visited(pred)) {
 293           if (block != blk)
 294             continue;
 295           collect_blks_lists(pred, block, entry, env);
 296         }
 297       }
 298     }
 299   }
 300   else {
 301     ARR_APP1(ir_node *, entry->phi_list, node);
 302     return;
 303   }
 304
 305   if (get_irn_mode(node) == mode_X) {
 306     ARR_APP1(ir_node *, entry->cf_list, node);
 307   }
 308   else {
 309     ARR_APP1(ir_node *, entry->df_list, node);
 310   }
 311 }
 312
 313 /**
 314  * walk over the graph and collect all lists
 315  */
 316 static void collect_lists(blk_collect_data_t *env)
 317 {
 318   int             i, j;
 319   ir_node         *block, *node;
 320   block_entry_t   *entry;
 321
 322   inc_irg_visited(current_ir_graph);
 323
 324   for (i = ARR_LEN(env->blk_list) - 1; i >= 0; --i) {
 325     block = env->blk_list[i];
 326     entry = block_find_entry(block, env);
 327
 328     for (j = ARR_LEN(entry->entry_list) - 1; j >= 0; --j) {
 329       node = entry->entry_list[j];
 330
 331       /* a entry might already be visited due to Phi loops */
 332       if (node->visited < current_ir_graph->visited)
 333         collect_blks_lists(node, block, entry, env);
 334     }
 335   }
 336 }
 337
 338 /**
 339  * Intraprozedural graph walker over blocks.
 340  */
 341 static void
 342 do_irg_walk_blk(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 343 {
 344   ir_node            *end_node = get_irg_end(irg);
 345   ir_node            *end_blk = get_irg_end_block(irg);
 346   blk_collect_data_t blks;
 347   int old_view       = get_interprocedural_view();
 348   block_entry_t      *entry;
 349
 350   /* switch off interprocedural view */
 351   set_interprocedural_view(false);
 352
 353   obstack_init(&blks.obst);
 354   blks.blk_map  = new_pset(addr_cmp, 1);
 355   blks.blk_list = NEW_ARR_F(ir_node *, 0);
 356
 357   /* first step: traverse the graph and fill the lists */
 358   inc_irg_visited(irg);
 359   collect_walk(end_node, &blks);
 360
 361   /* add the end block */
 362   ARR_APP1(ir_node *, blks.blk_list, end_blk);
 363
 364   /* and the end node */
 365   entry = block_find_entry(end_blk, &blks);
 366   ARR_APP1(ir_node *, entry->entry_list, end_node);
 367
 368   collect_lists(&blks);
 369
 370   /* second step: traverse the list */
 371   traverse(&blks, pre, post, env);
 372
 373   DEL_ARR_F(blks.blk_list);
 374   del_pset(blks.blk_map);
 375   obstack_free(&blks.obst, NULL);
 376
 377   set_interprocedural_view(old_view);
 378 }
 379
 380 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 381 {
 382   ir_graph * rem = current_ir_graph;
 383
 384   hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post);
 385   current_ir_graph = irg;
 386   do_irg_walk_blk(irg, pre, post, env);
 387   current_ir_graph = rem;
 388 }