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