3 * File name: ir/ana/irextbb.c
4 * Purpose: Extended basis block support.
9 * Copyright: (c) 2002-2005 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Computes extended basic blocks.
18 * @author Michael Beck
25 #include "irextbb_t.h"
28 #include "irgraph_t.h"
29 #include "iredges_t.h"
35 struct obstack *obst; /**< the obstack where allocations took place */
36 ir_extblk *head; /**< head of the list of all extended blocks */
37 ir_node *start_block; /**< the start block of the current graph */
40 int (is_ir_extbb)(const void *thing) {
41 return _is_ir_extbb(thing);
45 * allocate a new extended block header.
47 static void allocate_extblk(ir_node *block, env_t *env)
49 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
51 extblk->kind = k_ir_extblk;
53 extblk->blks = (ir_node **)env->head;
57 set_Block_extbb(block, extblk);
58 set_irn_link(block, NULL);
62 * Returns the number of block successors.
63 * we are interested only in 1, 2 and >2.
65 static int get_block_n_succs(ir_node *block) {
66 if (edges_activated(current_ir_graph)) {
67 const ir_edge_t *edge;
69 edge = get_block_succ_first(block);
72 edge = get_block_succ_next(block, edge);
75 edge = get_block_succ_next(block, edge);
78 return get_Block_n_cfg_outs(block);
82 * Pre block-walker. Calculates the extended block info.
84 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
86 int n = get_Block_n_cfgpreds(block);
89 if (n <= 0 || n > 1 || block == env->start_block) {
91 * block is a JOIN-node ie the control flow from
92 * many other blocks joins here. block is a leader.
93 * Note that we handle unreachable blocks (n <= 0) here too.
95 allocate_extblk(block, env);
97 else { /* we have only one control flow predecessor */
98 ir_node *add_to = get_Block_cfgpred_block(block, 0);
100 /* blocks with only one BAD predecessors are leaders too */
101 if (is_Bad(add_to)) {
102 allocate_extblk(block, env);
105 * Only one control flow predecessor. This block belongs
106 * to the same extended basic block as its predecessor.
108 ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));
110 if (irn_not_visited(cf_op)) {
111 ir_node *pred_bl = get_nodes_block(cf_op);
112 if (get_block_n_succs(pred_bl) > 2) {
113 /* More than two successors means we have a jump table.
114 * we cannot include a jump target into the current extended
115 * basic block, so create a new one here.
117 allocate_extblk(block, env);
119 /* either the previous block has only one successor or
120 * this is the first successor after an if, include it.
122 set_Block_extbb(block, NULL);
124 mark_irn_visited(cf_op);
126 /* already marked, so begin a new extended block here */
127 allocate_extblk(block, env);
133 /** A special extended block used as sentinel */
134 static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD };
137 * Post block-walker. Calculates the extended block info.
138 * During construction, we use the (free) block input of all basic blocks
139 * to point to there previous block.
141 static void post_walk_calc_extbb(ir_node *block, void *ctx)
143 ir_extblk *extbb = get_Block_extbb(block);
145 ir_extblk *sentinel = &_sentinel;
148 ir_node *curr, *prev, *list;
151 * Search the leader. It can happen, that we fall into an endless
152 * loop, because we enter an unreachable loop that is not yet detected.
153 * We break the loop using a sentinel.
155 for (curr = block; !extbb; curr = prev) {
156 prev = get_Block_cfgpred_block(curr, 0);
157 extbb = get_Block_extbb(prev);
158 set_Block_extbb(curr, sentinel);
161 if (extbb == sentinel) {
162 /* We detect a dead loop. We fix this by allocating a
163 * special Extended block
165 ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
167 allocate_extblk(block, env);
168 extbb = get_Block_extbb(block);
169 set_Block_extbb(block, sentinel);
172 /* replace all sentinels by the extbb info */
176 if (get_Block_extbb(prev) != sentinel)
178 set_irn_link(prev, list);
180 prev = get_Block_cfgpred_block(prev, 0);
182 /* arg, the list is in wrong order, turn around and add to the extbb list */
183 for (curr = list; curr; curr = prev) {
184 prev = get_irn_link(curr);
185 set_irn_link(curr, extbb->link);
187 set_Block_extbb(curr, extbb);
194 * Compute the extended basic blocks for a graph
196 void compute_extbb(ir_graph *irg) {
198 ir_extblk *extbb, *next;
201 obstack_free(irg->extbb_obst, NULL);
203 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
205 obstack_init(irg->extbb_obst);
207 env.obst = irg->extbb_obst;
209 env.start_block = get_irg_start_block(irg);
211 if (! edges_activated(irg)) {
212 /* we don't have edges */
213 assure_irg_outs(irg);
216 /* we must mark nodes, so increase the visited flag */
217 inc_irg_visited(irg);
218 irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
221 * Ok, we have now the list of all extended blocks starting with env.head
222 * every extended block "knowns" the number of blocks in visited and
223 * the blocks are linked in link.
224 * Now we can create arrays that hold the blocks, some kind of "out" edges
225 * for the extended block
227 for (extbb = env.head; extbb; extbb = next) {
228 int i, len = (int)extbb->visited;
231 next = (ir_extblk *)extbb->blks;
233 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
235 for (block = extbb->link, i = 0; i < len; ++i) {
236 ir_node *nblock = get_irn_link(block);
238 /* ensure that the leader is the first one */
239 extbb->blks[len - 1 - i] = block;
240 set_irn_link(block, NULL);
246 for (i = len - 1; i > 0; --i) {
247 ir_node *blk = extbb->blks[i];
249 if (get_Block_n_cfgpreds(blk) != 1) {
250 assert(!"Block for more than one predecessors is no leader");
251 } else if (get_Block_cfgpred_block(blk, 0) != extbb->blks[i - 1]) {
252 assert(!"extbb block order wrong");
261 irg->extblk_state = extblk_valid;
264 /* free all extended block info. */
265 void free_extbb(ir_graph *irg) {
266 if (irg->extbb_obst) {
267 obstack_free(irg->extbb_obst, NULL);
268 xfree(irg->extbb_obst);
269 irg->extbb_obst = NULL;
271 irg->extblk_state = extblk_none;
274 /* Return the extended block of a node. */
275 ir_extblk *get_nodes_extbb(ir_node *node) {
276 ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
277 return get_Block_extbb(block);
280 /* Gets the visited counter of an extended block. */
281 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
282 return _get_extbb_visited(blk);
285 /* Sets the visited counter of an extended block. */
286 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
287 _set_extbb_visited(blk, visited);
290 /* Mark an extended block as visited in a graph. */
291 void (mark_extbb_visited)(ir_extblk *blk) {
292 _mark_extbb_visited(blk);
295 /* Returns non-zero if an extended was visited. */
296 int (extbb_visited)(const ir_extblk *blk) {
297 return _extbb_visited(blk);
300 /* Returns non-zero if an extended block was NOT visited. */
301 int (extbb_not_visited)(const ir_extblk *blk) {
302 return _extbb_not_visited(blk);
305 /* Returns the link field of an extended block. */
306 void *(get_extbb_link)(const ir_extblk *blk) {
307 return _get_extbb_link(blk);
310 /* Sets the link field of an extended block. */
311 void (set_extbb_link)(ir_extblk *blk, void *link) {
312 _set_extbb_link(blk, link);
315 /* Return the number of basic blocks of an extended block */
316 int (get_extbb_n_blocks)(const ir_extblk *blk) {
317 return _get_extbb_n_blocks(blk);
320 /* Return the i'th basic block of an extended block */
321 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
322 return _get_extbb_block(blk, pos);
325 /* Return the leader basis block of an extended block. */
326 ir_node *(get_extbb_leader)(ir_extblk *blk) {
327 return _get_extbb_leader(blk);
330 /* Return the node number of an extended block. */
331 long get_extbb_node_nr(ir_extblk *blk) {
332 return get_irn_node_nr(get_extbb_leader(blk));
335 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
340 if (extbb_not_visited(blk)) {
341 mark_extbb_visited(blk);
343 if (pre) pre(blk, env);
345 node = get_extbb_leader(blk);
346 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
347 /* find the corresponding predecessor block. */
348 ir_node *pred = get_Block_cfgpred_block(node, i);
349 if (is_Block(pred)) {
351 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
354 assert(is_Bad(pred));
358 if (post) post(blk, env);
362 /* walks only over extended Block nodes in the graph. Has it's own visited
363 flag, so that it can be interleaved with the other walker. */
364 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
366 ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
367 ir_extblk *start_blk = get_Block_extbb(start_bl);
371 assert(!get_interprocedural_view()); /* interprocedural_view not implemented */
372 inc_irg_block_visited(current_ir_graph);
374 /* assure the start block is the first one */
375 mark_extbb_visited(start_blk);
377 post(start_blk, env);
378 irg_extblock_walk_2(blk, pre, post, env);
380 /* keepalive: the endless loops ... */
381 if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
382 ir_node *node = get_irg_end(current_ir_graph);
383 int arity = get_irn_arity(node);
384 for (i = 0; i < arity; i++) {
385 pred = get_irn_n(node, i);
387 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
388 else if (is_Phi(pred)) {
389 /* Sometimes the blocks died, but are still reachable through Phis.
390 * Make sure the algorithms that try to remove these reach them. */
391 ir_node *block = get_nodes_block(pred);
394 irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
403 /* Walks only over reachable Extended Basic Block nodes in the graph. */
404 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
406 ir_node *endbl = get_irg_end_block(irg);
407 ir_extblk *blk = get_Block_extbb(endbl);
408 ir_graph *rem = current_ir_graph;
409 current_ir_graph = irg;
410 irg_extblock_walk(blk, pre, post, env);
411 current_ir_graph = rem;