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
20 #include "irextbb_t.h"
23 #include "irgraph_t.h"
24 #include "iredges_t.h"
30 struct obstack *obst; /**< the obstack where allocations took place */
31 ir_extblk *head; /**< head of the list of all extended blocks */
34 int (is_ir_extbb)(const void *thing) {
35 return _is_ir_extbb(thing);
39 * allocate a new extended block header.
41 static void allocate_extblk(ir_node *block, env_t *env)
43 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
45 extblk->kind = k_ir_extblk;
47 extblk->blks = (ir_node **)env->head;
51 set_Block_extbb(block, extblk);
52 set_irn_link(block, NULL);
56 * add a block to an extended block
58 static void addto_extblk(ir_extblk *extblk, ir_node *block)
60 /* link all blocks belonging to this extended block */
61 set_irn_link(block, extblk->link);
66 set_Block_extbb(block, extblk);
70 * Returns the number of block successors.
71 * we are interested only in 1, 2 and >2.
73 static int get_block_n_succs(ir_node *block) {
74 #ifdef FIRM_EDGES_INPLACE
75 if (edges_activated(current_ir_graph)) {
76 const ir_edge_t *edge;
78 edge = get_block_succ_first(block);
81 edge = get_block_succ_next(block, edge);
84 edge = get_block_succ_next(block, edge);
88 return get_Block_n_cfg_outs(block);
92 * Pre block-walker. Calculates the extended block info.
94 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
96 int n = get_Block_n_cfgpreds(block);
99 if (n <= 0 || n > 1 ||
100 block == get_irg_start_block(current_ir_graph)) {
102 * block is a JOIN-node ie the control flow from
103 * many other blocks joins here. block is a leader.
104 * Note that we handle unreachable blocks (n <= 0) here too.
106 allocate_extblk(block, env);
108 else { /* we have only one control flow predecessor */
109 ir_node *add_to = get_Block_cfgpred_block(block, 0);
111 /* blocks with only one BAD predecessors are leaders too */
112 if (is_Bad(add_to)) {
113 allocate_extblk(block, env);
117 * Only one control flow predecessor. This block belongs
118 * to the same extended basic block as its predecessor.
120 ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));
122 if (irn_not_visited(cf_op)) {
123 ir_node *pred_bl = get_nodes_block(cf_op);
124 if (get_block_n_succs(pred_bl) > 2) {
125 /* More than two successors means we have a jump table.
126 * we cannot include a jump target into the current extended
127 * basic block, so create a new one here.
129 allocate_extblk(block, env);
132 /* either the previous block has only one successor or
133 * this is the first successor after an if, include it.
135 set_Block_extbb(block, NULL);
137 mark_irn_visited(cf_op);
140 /* already marked, so begin a new extended block here */
141 allocate_extblk(block, env);
147 /** A special extended block used as sentinel */
148 static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD };
151 * Post block-walker. Calculates the extended block info.
152 * During construction, we use the (free) block input of all basic blocks
153 * to point to there previous block.
155 static void post_walk_calc_extbb(ir_node *block, void *ctx)
157 ir_extblk *extbb = get_Block_extbb(block);
159 ir_extblk *sentinel = &_sentinel;
162 ir_node *curr, *prev;
165 * Search the leader. It can happen, that we fall into an endless
166 * loop, because we enter an unreachable loop that is not yet detected.
167 * We break the loop using a sentinel.
169 for (curr = block; !extbb; curr = prev) {
170 prev = get_Block_cfgpred_block(curr, 0);
171 extbb = get_Block_extbb(prev);
172 set_Block_extbb(curr, sentinel);
175 if (extbb == sentinel) {
176 /* We detect a dead loop. We fix this by allocating an
177 * special Extended block
179 ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
181 allocate_extblk(block, env);
182 extbb = get_Block_extbb(block);
183 set_Block_extbb(block, sentinel);
186 /* replace all sentinels by the extbb info */
189 if (get_Block_extbb(prev) != sentinel)
191 set_Block_extbb(prev, extbb);
193 set_irn_link(prev, extbb->link);
195 prev = get_Block_cfgpred_block(prev, 0);
202 * Walker for cf_dependent_on().
203 * This function searches a node tgt recursively from a given node
204 * but is restricted to the given extended basic block.
206 * @return 1 if tgt was reachable from curr, 0 if not.
208 static int check_cf_dependence(ir_node *curr, ir_node *tgt, ir_extblk *extbb)
212 /* Note: we did not include the leader in our serach, so
213 there could not be any loops here. */
214 if (get_Block_extbb(curr) != extbb)
220 for (i = 0, n = get_Block_n_cfgpreds(curr); i < n; ++i) {
221 if (check_cf_dependence(get_Block_cfgpred_block(curr, i), tgt, extbb))
228 * Check if a block is control dependent on another one.
229 * Both blocks must be in the same extended basic block.
230 * @param blk1 The first block.
231 * @param blk2 The second block.
232 * @return 1, if blk1 is control dependent (transitively) on blk2, 0 if not.
234 static int cf_dependent_on(ir_node *blk1, ir_node *blk2)
236 ir_extblk *extbb = get_Block_extbb(blk1);
237 ir_graph *irg = get_irn_irg(blk1);
239 assert(extbb == get_Block_extbb(blk2));
240 return check_cf_dependence(blk1, blk2, extbb);
244 * Compare two blocks for dependency.
247 * 0 if both blocks nodes are equal
248 * 1 block b1 depends on block b2
249 * -1 block b2 depends on block d2
251 static int block_order(const void *b1, const void *b2)
253 ir_node *n1 = *(ir_node **)b1;
254 ir_node *n2 = *(ir_node **)b2;
256 return n1 == n2 ? 0 : (cf_dependent_on(n1, n2) ? -1 : 1);
258 #endif /* NEED_SORT */
261 * Compute the extended basic blocks for a graph
263 void compute_extbb(ir_graph *irg) {
265 ir_extblk *extbb, *next;
268 obstack_free(irg->extbb_obst, NULL);
270 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
272 obstack_init(irg->extbb_obst);
274 env.obst = irg->extbb_obst;
277 #ifdef FIRM_EDGES_INPLACE
278 if (edges_activated(irg)) {
283 if (get_irg_outs_state(irg) != outs_consistent)
284 compute_irg_outs(irg);
286 /* we must mark nodes, so increase the visited flag */
287 inc_irg_visited(irg);
288 irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
291 * Ok, we have now the list of all extended blocks starting with env.head
292 * every extended block "knowns" the number of blocks in visited and
293 * the blocks are linked in link.
294 * Now we can create arrays that hold the blocks, some kind of "out" edges
295 * for the extended block
297 for (extbb = env.head; extbb; extbb = next) {
298 int i, len = (int)extbb->visited;
301 next = (ir_extblk *)extbb->blks;
303 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
305 for (block = extbb->link, i = 0; i < len; ++i) {
306 ir_node *nblock = get_irn_link(block);
308 /* ensure that the leader is the first one */
309 extbb->blks[len - 1 - i] = block;
310 set_irn_link(block, NULL);
318 /* we want the blocks in scheduled order, so sort them */
319 /* FIXME: is this really needed? Or generates the algorithm automagically ordered ones? */
321 /* temporary remove the leader from the extended block to break loops */
322 set_Block_extbb(extbb->blks[0], NULL);
323 qsort(&extbb->blks[1], len-1, sizeof(extbb->blks[0]), block_order);
324 set_Block_extbb(extbb->blks[0], extbb);
329 irg->extblk_state = extblk_valid;
332 /* free all extended block info. */
333 void free_extbb(ir_graph *irg) {
334 if (irg->extbb_obst) {
335 obstack_free(irg->extbb_obst, NULL);
336 xfree(irg->extbb_obst);
337 irg->extbb_obst = NULL;
339 irg->extblk_state = extblk_none;
342 /* Return the extended block of a node. */
343 ir_extblk *get_nodes_extbb(ir_node *node) {
344 ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
345 return get_Block_extbb(block);
348 /* Gets the visited counter of an extended block. */
349 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
350 return _get_extbb_visited(blk);
353 /* Sets the visited counter of an extended block. */
354 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
355 _set_extbb_visited(blk, visited);
358 /* Mark an extended block as visited in a graph. */
359 void (mark_extbb_visited)(ir_extblk *blk) {
360 _mark_extbb_visited(blk);
363 /* Returns non-zero if an extended was visited. */
364 int (extbb_visited)(const ir_extblk *blk) {
365 return _extbb_visited(blk);
368 /* Returns non-zero if an extended block was NOT visited. */
369 int (extbb_not_visited)(const ir_extblk *blk) {
370 return _extbb_not_visited(blk);
373 /* Returns the link field of an extended block. */
374 void *(get_extbb_link)(const ir_extblk *blk) {
375 return _get_extbb_link(blk);
378 /* Sets the link field of an extended block. */
379 void (set_extbb_link)(ir_extblk *blk, void *link) {
380 _set_extbb_link(blk, link);
383 /* Return the number of basic blocks of an extended block */
384 int (get_extbb_n_blocks)(const ir_extblk *blk) {
385 return _get_extbb_n_blocks(blk);
388 /* Return the i'th basic block of an extended block */
389 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
390 return _get_extbb_block(blk, pos);
393 /* Return the leader basis block of an extended block. */
394 ir_node *(get_extbb_leader)(ir_extblk *blk) {
395 return _get_extbb_leader(blk);
398 /* Return the node number of an extended block. */
399 long get_extbb_node_nr(ir_extblk *blk) {
400 return get_irn_node_nr(get_extbb_leader(blk));
403 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
408 if (extbb_not_visited(blk)) {
409 mark_extbb_visited(blk);
411 if (pre) pre(blk, env);
413 node = get_extbb_leader(blk);
414 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
415 /* find the corresponding predecessor block. */
416 ir_node *pred = get_Block_cfgpred_block(node, i);
417 if (is_Block(pred)) {
419 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
422 assert(is_Bad(pred));
426 if (post) post(blk, env);
430 /* walks only over extended Block nodes in the graph. Has it's own visited
431 flag, so that it can be interleaved with the other walker. */
432 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
434 ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
435 ir_extblk *start_blk = get_Block_extbb(start_bl);
439 assert(!get_interprocedural_view()); /* interprocedural_view not implemented */
440 inc_irg_block_visited(current_ir_graph);
442 /* assure the start block is the first one */
443 mark_extbb_visited(start_blk);
445 post(start_blk, env);
446 irg_extblock_walk_2(blk, pre, post, env);
448 /* keepalive: the endless loops ... */
449 if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
450 ir_node *node = get_irg_end(current_ir_graph);
451 int arity = get_irn_arity(node);
452 for (i = 0; i < arity; i++) {
453 pred = get_irn_n(node, i);
455 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
456 else if (is_Phi(pred)) {
457 /* Sometimes the blocks died, but are still reachable through Phis.
458 * Make sure the algorithms that try to remove these reach them. */
459 ir_node *block = get_nodes_block(pred);
462 irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
471 /* Walks only over reachable Extended Basic Block nodes in the graph. */
472 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
474 ir_node *endbl = get_irg_end_block(irg);
475 ir_extblk *blk = get_Block_extbb(endbl);
476 ir_graph *rem = current_ir_graph;
477 current_ir_graph = irg;
478 irg_extblock_walk(blk, pre, post, env);
479 current_ir_graph = rem;