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));
80 * Post-walker: collect nodes and put them on the right list
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 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
97 pdeq_putl(ctx->blk_list, node);
101 block = get_nodes_block(node);
102 entry = block_find_entry(block, ctx);
104 if (get_irn_mode(node) == mode_X) {
106 * put all mode_X nodes to the start, later we can
107 * move them to the end.
109 pdeq_putr(entry->list, node);
112 pdeq_putl(entry->list, node);
116 * move mode_X nodes to the end of the schedule
118 static void move_X_nodes_to_end(pdeq *list)
122 /* move mode_X nodes to the end */
123 for (j = pdeq_len(list); j > 0; --j) {
124 ir_node *node = pdeq_getr(list);
126 if (get_irn_mode(node) == mode_X) {
127 pdeq_putl(list, node);
130 pdeq_putr(list, node);
137 * traverse the pre order only, from End to Start
139 static void traverse_pre(blk_collect_data_t* blks, irg_walk_func *pre, void *env)
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);
147 /* move mode_X nodes to the end */
148 move_X_nodes_to_end(entry->list);
150 for (j = pdeq_len(entry->list); j > 0; --j) {
151 ir_node *node = pdeq_getl(entry->list);
159 * traverse the post order only, from Start to End
161 static void traverse_post(blk_collect_data_t* blks, irg_walk_func *post, void *env)
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);
171 /* move mode_X nodes to the end */
172 move_X_nodes_to_end(entry->list);
174 for (j = pdeq_len(entry->list); j > 0; --j) {
175 ir_node *node = pdeq_getr(entry->list);
184 static void traverse_both(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
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);
193 pdeq_putr(blks->blk_list, block);
195 /* move mode_X nodes to the end */
196 move_X_nodes_to_end(entry->list);
198 for (j = pdeq_len(entry->list); j > 0; --j) {
199 ir_node *node = pdeq_getl(entry->list);
201 pdeq_putr(entry->list, node);
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);
214 for (j = pdeq_len(entry->list); j > 0; --j) {
215 ir_node *node = pdeq_getr(entry->list);
225 static void traverse(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
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);
233 * Intraprozedural graph walker over blocks.
236 do_irg_walk_blk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
238 blk_collect_data_t blks;
239 int old_view = get_interprocedural_view();
241 /* switch off interprocedural view */
242 set_interprocedural_view(false);
244 obstack_init(&blks.obst);
245 blks.blk_map = new_pset(addr_cmp, 1);
246 blks.blk_list = new_pdeq();
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));
254 /* second step: traverse the list */
255 traverse(&blks, pre, post, env);
258 del_pdeq(blks.blk_list);
259 del_pset(blks.blk_map);
260 obstack_free(&blks.obst, NULL);
262 set_interprocedural_view(old_view);
265 void irg_walk_blkwise(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
267 inc_irg_visited(current_ir_graph);
268 do_irg_walk_blk(node, pre, post, env);
271 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
273 ir_graph * rem = current_ir_graph;
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;