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