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

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