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 "pdeq.h"
  20 #include "pset.h"
  21 #include "irhooks.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   pdeq           *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   pdeq    *list;     /**< the instruction list */
  38 } block_entry_t;
  39
  40 /**
  41  * compare two block_entries
  42  */
  43 static int addr_cmp(const void *elt, const void *key) {
  44   const block_entry_t *e1 = elt;
  45   const block_entry_t *e2 = key;
  46
  47   return e1->block != e2->block;
  48 }
  49
  50 /**
  51  * calculates a hash value for an block address
  52  * Addresses are typically aligned at 32bit, so we ignore the lowest bits
  53  */
  54 static INLINE unsigned block_hash(const ir_node *node) {
  55   return (unsigned)node >> 3;
  56 }
  57
  58 /**
  59  * Returns the associates block_entry_t for an block
  60  */
  61 static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx)
  62 {
  63   block_entry_t key;
  64   block_entry_t *elem;
  65
  66   key.block = block;
  67   elem = pset_find(ctx->blk_map, &key, block_hash(block));
  68   if (elem)
  69     return elem;
  70
  71   elem = obstack_alloc(&ctx->obst, sizeof(*elem));
  72
  73   elem->block = block;
  74   elem->list  = new_pdeq();
  75
  76   return pset_insert(ctx->blk_map, elem, block_hash(block));
  77 }
  78
  79 /**
  80  * Post-walker: collect nodes and put them on the right list
  81  */
  82 static void collect_nodes(ir_node *node, void *env)
  83 {
  84    blk_collect_data_t *ctx = env;
  85    ir_node            *block;
  86    block_entry_t      *entry;
  87
  88    if (is_Block(node))  {
  89      /* it's a block, put it into the block list */
  90      pdeq_putl(ctx->blk_list, node);
  91      return;
  92    }
  93
  94    block = get_nodes_block(node);
  95    entry = block_find_entry(block, ctx);
  96
  97    if (get_irn_mode(node) == mode_X) {
  98      /*
  99       * put all mode_X nodes to the start, later we can
 100       * move them to the end.
 101       */
 102      pdeq_putr(entry->list, node);
 103    }
 104    else
 105      pdeq_putl(entry->list, node);
 106 }
 107
 108 /**
 109  * move mode_X nodes to the end of the schedule
 110  */
 111 static void move_X_nodes_to_end(pdeq *list)
 112 {
 113   int j;
 114
 115   /* move mode_X nodes to the end */
 116   for (j = pdeq_len(list); j > 0; --j) {
 117     ir_node *node = pdeq_getr(list);
 118
 119     if (get_irn_mode(node) == mode_X) {
 120       pdeq_putl(list, node);
 121     }
 122     else {
 123       pdeq_putr(list, node);
 124       break;
 125     }
 126   }
 127 }
 128
 129 /**
 130  * traverse the pre order only, from End to Start
 131  */
 132 static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env)
 133 {
 134   int i, j;
 135
 136   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 137     ir_node       *block = pdeq_getl(blks->blk_list);
 138     block_entry_t *entry = block_find_entry(block, blks);
 139
 140     /* move mode_X nodes to the end */
 141     move_X_nodes_to_end(entry->list);
 142
 143     for (j = pdeq_len(entry->list); j > 0; --j) {
 144       ir_node *node = pdeq_getl(entry->list);
 145       pre(node, env);
 146     }
 147     pre(block, env);
 148   }
 149 }
 150
 151 /**
 152  * traverse the post order only, from Start to End
 153  */
 154 static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env)
 155 {
 156   int i, j;
 157
 158   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 159     ir_node       *block = pdeq_getr(blks->blk_list);
 160     block_entry_t *entry = block_find_entry(block, blks);
 161
 162     post(block, env);
 163
 164     /* move mode_X nodes to the end */
 165     move_X_nodes_to_end(entry->list);
 166
 167     for (j = pdeq_len(entry->list); j > 0; --j) {
 168       ir_node *node = pdeq_getr(entry->list);
 169       post(node, env);
 170     }
 171   }
 172 }
 173
 174 /**
 175  * traverse both
 176  */
 177 static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 178 {
 179   int i, j;
 180
 181   /* pre walk, rotate all lists */
 182   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 183     ir_node       *block = pdeq_getl(blks->blk_list);
 184     block_entry_t *entry = block_find_entry(block, blks);
 185
 186     pdeq_putr(blks->blk_list, block);
 187
 188     /* move mode_X nodes to the end */
 189     move_X_nodes_to_end(entry->list);
 190
 191     for (j = pdeq_len(entry->list); j > 0; --j) {
 192       ir_node *node = pdeq_getl(entry->list);
 193
 194       pdeq_putr(entry->list, node);
 195       pre(node, env);
 196     }
 197     pre(block, env);
 198   }
 199
 200   /* second step */
 201   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 202     ir_node       *block = pdeq_getr(blks->blk_list);
 203     block_entry_t *entry = block_find_entry(block, blks);
 204
 205     post(block, env);
 206
 207     for (j = pdeq_len(entry->list); j > 0; --j) {
 208       ir_node *node = pdeq_getr(entry->list);
 209       post(node, env);
 210     }
 211   }
 212 }
 213
 214
 215 /**
 216  * Do the traversal
 217  */
 218 static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 219 {
 220   if      (!post) traverse_pre (blks, pre, env);
 221   else if (!pre)  traverse_post(blks, post, env);
 222   else            traverse_both(blks, pre, post, env);
 223 }
 224
 225 /**
 226  * Intraprozedural graph walker over blocks.
 227  */
 228 static void
 229 do_irg_walk_blk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 230 {
 231   blk_collect_data_t blks;
 232   int old_view = get_interprocedural_view();
 233
 234   /* switch off interprocedural view */
 235   set_interprocedural_view(false);
 236
 237   obstack_init(&blks.obst);
 238   blks.blk_map  = new_pset(addr_cmp, 1);
 239   blks.blk_list = new_pdeq();
 240
 241   if (node->visited < current_ir_graph->visited) {
 242     /* first step: traverse the graph and fill the lists */
 243     irg_walk(node, NULL, collect_nodes, &blks);
 244
 245     /* second step: traverse the list */
 246     traverse(&blks, pre, post, env);
 247   }
 248
 249   del_pdeq(blks.blk_list);
 250   del_pset(blks.blk_map);
 251   obstack_free(&blks.obst, NULL);
 252
 253   set_interprocedural_view(old_view);
 254 }
 255
 256 void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 257 {
 258   inc_irg_visited(current_ir_graph);
 259   do_irg_walk_blk(node, pre, post, env);
 260 }
 261
 262 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 263 {
 264   ir_graph * rem = current_ir_graph;
 265
 266   hook_irg_walk_blkwise(irg, (void *)pre, (void *)post);
 267   current_ir_graph = irg;
 268   irg_walk_blkwise(get_irg_end(irg), pre, post, env);
 269   current_ir_graph = rem;
 270 }