3 * File name: ir/ir/irgwalk_blk.c
9 * Copyright: (c) 1999-2004 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 #include "irgraph_t.h" /* visited flag */
24 * Metadata for block walker
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 */
33 * An entry for a block in the blk_map
35 typedef struct _block_entry_t {
36 ir_node *block; /**< the block */
37 pdeq *list; /**< the instruction list */
41 * compare two block_entries
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;
47 return e1->block != e2->block;
51 * calculates a hash value for an block address
52 * Addresses are typically aligned at 32bit, so we ignore the lowest bits
54 static INLINE unsigned block_hash(const ir_node *node) {
55 return (unsigned)node >> 3;
59 * Returns the associates block_entry_t for an block
61 static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx)
67 elem = pset_find(ctx->blk_map, &key, block_hash(block));
71 elem = obstack_alloc(&ctx->obst, sizeof(*elem));
74 elem->list = new_pdeq();
76 return pset_insert(ctx->blk_map, elem, block_hash(block));
82 static void collect_nodes(ir_node *node, void *env)
84 blk_collect_data_t *ctx = env;
89 /* it's a block, put it into the block list */
90 pdeq_putr(ctx->blk_list, node);
94 block = get_nodes_block(node);
95 entry = block_find_entry(block, ctx);
97 if (get_irn_mode(node) == mode_X)
98 pdeq_putl(entry->list, node);
100 pdeq_putr(entry->list, node);
104 * traverse the pre order only, from End to Start
106 static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env)
110 for (i = pdeq_len(blks->blk_list); i > 0; --i) {
111 ir_node *block = pdeq_getl(blks->blk_list);
112 block_entry_t *entry = block_find_entry(block, blks);
114 for (j = pdeq_len(entry->list); j > 0; --j) {
115 ir_node *node = pdeq_getl(entry->list);
123 * traverse the post order only, from Start to End
125 static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env)
129 for (i = pdeq_len(blks->blk_list); i > 0; --i) {
130 ir_node *block = pdeq_getr(blks->blk_list);
131 block_entry_t *entry = block_find_entry(block, blks);
134 for (j = pdeq_len(entry->list); j > 0; --j) {
135 ir_node *node = pdeq_getr(entry->list);
144 static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
148 /* pre walk, rotate all lists */
149 for (i = pdeq_len(blks->blk_list); i > 0; --i) {
150 ir_node *block = pdeq_getl(blks->blk_list);
151 block_entry_t *entry = block_find_entry(block, blks);
153 pdeq_putr(blks->blk_list, block);
155 for (j = pdeq_len(entry->list); j > 0; --j) {
156 ir_node *node = pdeq_getl(entry->list);
158 pdeq_putr(entry->list, node);
165 traverse_post(blks, post, env);
172 static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
174 if (!post) traverse_pre (blks, pre, env);
175 else if (!pre) traverse_post(blks, post, env);
176 else traverse_both(blks, pre, post, env);
180 * Intraprozedural graph walker over blocks.
183 do_irg_walk_blk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
185 blk_collect_data_t blks;
186 int old_view = interprocedural_view;
188 /* switch off interprocedural view */
189 interprocedural_view = 0;
191 obstack_init(&blks.obst);
192 blks.blk_map = new_pset(addr_cmp, 1);
193 blks.blk_list = new_pdeq();
195 if (node->visited < current_ir_graph->visited) {
196 /* first step: traverse the graph and fill the lists */
197 irg_walk(node, collect_nodes, NULL, &blks);
199 /* second step: traverse the list */
200 traverse(&blks, pre, post, env);
203 del_pdeq(blks.blk_list);
204 del_pset(blks.blk_map);
205 obstack_free(&blks.obst, NULL);
207 interprocedural_view = old_view;
210 void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
212 inc_irg_visited(current_ir_graph);
213 do_irg_walk_blk(node, pre, post, env);
216 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
218 ir_graph * rem = current_ir_graph;
220 stat_irg_walk_blkwise(irg, (void *)pre, (void *)post);
221 current_ir_graph = irg;
222 irg_walk_blkwise(get_irg_end(irg), pre, post, env);
223 current_ir_graph = rem;