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     if (node == get_irg_end_block(current_ir_graph)) {
  91       /* Put the end block always last. If we don't do it here,
  92        * it might be placed elsewhere if the graph contains
  93        * endless loops.
  94        */
  95     }
  96     else
  97       pdeq_putl(ctx->blk_list, node);
  98     return;
  99   }
 100
 101   block = get_nodes_block(node);
 102   entry = block_find_entry(block, ctx);
 103
 104   if (get_irn_mode(node) == mode_X) {
 105     /*
 106      * put all mode_X nodes to the start, later we can
 107      * move them to the end.
 108      */
 109     pdeq_putr(entry->list, node);
 110   }
 111   else
 112     pdeq_putl(entry->list, node);
 113 }
 114
 115 /**
 116  * move mode_X nodes to the end of the schedule
 117  */
 118 static void move_X_nodes_to_end(pdeq *list)
 119 {
 120   int j;
 121
 122   /* move mode_X nodes to the end */
 123   for (j = pdeq_len(list); j > 0; --j) {
 124     ir_node *node = pdeq_getr(list);
 125
 126     if (get_irn_mode(node) == mode_X) {
 127       pdeq_putl(list, node);
 128     }
 129     else {
 130       pdeq_putr(list, node);
 131       break;
 132     }
 133   }
 134 }
 135
 136 /**
 137  * traverse the pre order only, from End to Start
 138  */
 139 static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env)
 140 {
 141   int i, j;
 142
 143   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 144     ir_node       *block = pdeq_getl(blks->blk_list);
 145     block_entry_t *entry = block_find_entry(block, blks);
 146
 147     /* move mode_X nodes to the end */
 148     move_X_nodes_to_end(entry->list);
 149
 150     for (j = pdeq_len(entry->list); j > 0; --j) {
 151       ir_node *node = pdeq_getl(entry->list);
 152       pre(node, env);
 153     }
 154     pre(block, env);
 155   }
 156 }
 157
 158 /**
 159  * traverse the post order only, from Start to End
 160  */
 161 static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env)
 162 {
 163   int i, j;
 164
 165   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 166     ir_node       *block = pdeq_getr(blks->blk_list);
 167     block_entry_t *entry = block_find_entry(block, blks);
 168
 169     post(block, env);
 170
 171     /* move mode_X nodes to the end */
 172     move_X_nodes_to_end(entry->list);
 173
 174     for (j = pdeq_len(entry->list); j > 0; --j) {
 175       ir_node *node = pdeq_getr(entry->list);
 176       post(node, env);
 177     }
 178   }
 179 }
 180
 181 /**
 182  * traverse both
 183  */
 184 static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 185 {
 186   int i, j;
 187
 188   /* pre walk, rotate all lists */
 189   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 190     ir_node       *block = pdeq_getl(blks->blk_list);
 191     block_entry_t *entry = block_find_entry(block, blks);
 192
 193     pdeq_putr(blks->blk_list, block);
 194
 195     /* move mode_X nodes to the end */
 196     move_X_nodes_to_end(entry->list);
 197
 198     for (j = pdeq_len(entry->list); j > 0; --j) {
 199       ir_node *node = pdeq_getl(entry->list);
 200
 201       pdeq_putr(entry->list, node);
 202       pre(node, env);
 203     }
 204     pre(block, env);
 205   }
 206
 207   /* second step */
 208   for (i = pdeq_len(blks->blk_list); i > 0; --i) {
 209     ir_node       *block = pdeq_getr(blks->blk_list);
 210     block_entry_t *entry = block_find_entry(block, blks);
 211
 212     post(block, env);
 213
 214     for (j = pdeq_len(entry->list); j > 0; --j) {
 215       ir_node *node = pdeq_getr(entry->list);
 216       post(node, env);
 217     }
 218   }
 219 }
 220
 221
 222 /**
 223  * Do the traversal
 224  */
 225 static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 226 {
 227   if      (!post) traverse_pre (blks, pre, env);
 228   else if (!pre)  traverse_post(blks, post, env);
 229   else            traverse_both(blks, pre, post, env);
 230 }
 231
 232 /**
 233  * Intraprozedural graph walker over blocks.
 234  */
 235 static void
 236 do_irg_walk_blk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 237 {
 238   blk_collect_data_t blks;
 239   int old_view = get_interprocedural_view();
 240
 241   /* switch off interprocedural view */
 242   set_interprocedural_view(false);
 243
 244   obstack_init(&blks.obst);
 245   blks.blk_map  = new_pset(addr_cmp, 1);
 246   blks.blk_list = new_pdeq();
 247
 248   if (node->visited < current_ir_graph->visited) {
 249     /* first step: traverse the graph and fill the lists */
 250     irg_walk(node, NULL, collect_nodes, &blks);
 251     /* add the end block */
 252     pdeq_putl(blks.blk_list, get_irg_end_block(current_ir_graph));
 253
 254     /* second step: traverse the list */
 255     traverse(&blks, pre, post, env);
 256   }
 257
 258   del_pdeq(blks.blk_list);
 259   del_pset(blks.blk_map);
 260   obstack_free(&blks.obst, NULL);
 261
 262   set_interprocedural_view(old_view);
 263 }
 264
 265 void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 266 {
 267   inc_irg_visited(current_ir_graph);
 268   do_irg_walk_blk(node, pre, post, env);
 269 }
 270
 271 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 272 {
 273   ir_graph * rem = current_ir_graph;
 274
 275   hook_irg_walk_blkwise(irg, (void *)pre, (void *)post);
 276   current_ir_graph = irg;
 277   irg_walk_blkwise(get_irg_end(irg), pre, post, env);
 278   current_ir_graph = rem;
 279 }