2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Extended basis block support.
23 * @author Michael Beck
28 #include "irextbb_t.h"
31 #include "irgraph_t.h"
32 #include "iredges_t.h"
38 * Environment for extbb construction.
41 struct obstack *obst; /**< the obstack where allocations took place */
42 ir_extblk *head; /**< head of the list of all extended blocks */
43 ir_node *start_block; /**< the start block of the current graph */
46 int (is_ir_extbb)(const void *thing)
48 return _is_ir_extbb(thing);
52 * allocate a new extended block header.
54 static void allocate_extblk(ir_node *block, env_t *env)
56 ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
58 extblk->kind = k_ir_extblk;
60 extblk->blks = (ir_node **)env->head;
64 set_Block_extbb(block, extblk);
65 set_irn_link(block, NULL);
69 * Returns the number of block successors.
70 * we are interested only in 1, 2 and >2.
72 static int get_block_n_succs(ir_node *block)
74 if (edges_activated(current_ir_graph)) {
75 const ir_edge_t *edge;
77 edge = get_block_succ_first(block);
80 edge = get_block_succ_next(block, edge);
83 edge = get_block_succ_next(block, edge);
86 return get_Block_n_cfg_outs(block);
90 * Pre block-walker. Calculates the extended block info.
92 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
94 int n = get_Block_n_cfgpreds(block);
95 env_t *env = (env_t*) ctx;
97 if (n <= 0 || n > 1 || block == env->start_block) {
99 * block is a JOIN-node ie the control flow from
100 * many other blocks joins here. block is a leader.
101 * Note that we handle unreachable blocks (n <= 0) here too.
103 allocate_extblk(block, env);
105 else { /* we have only one control flow predecessor */
106 ir_node *add_to = get_Block_cfgpred_block(block, 0);
108 /* blocks with only one BAD predecessors are leaders too */
109 if (is_Bad(add_to)) {
110 allocate_extblk(block, env);
113 * Only one control flow predecessor. This block belongs
114 * to the same extended basic block as its predecessor.
116 ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));
118 if (!irn_visited_else_mark(cf_op)) {
119 ir_node *pred_bl = get_nodes_block(cf_op);
120 if (get_block_n_succs(pred_bl) > 2) {
121 /* More than two successors means we have a jump table.
122 * we cannot include a jump target into the current extended
123 * basic block, so create a new one here.
125 allocate_extblk(block, env);
127 /* either the previous block has only one successor or
128 * this is the first successor after an if, include it.
130 set_Block_extbb(block, NULL);
133 /* already marked, so begin a new extended block here */
134 allocate_extblk(block, env);
140 /** A special extended block used as sentinel */
141 static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD, NULL, NULL };
144 * Post block-walker. Calculates the extended block info.
145 * During construction, we use the (free) block input of all basic blocks
146 * to point to there previous block.
148 static void post_walk_calc_extbb(ir_node *block, void *ctx)
150 ir_extblk *extbb = get_Block_extbb(block);
151 env_t *env = (env_t*) ctx;
152 ir_extblk *sentinel = &_sentinel;
155 ir_node *curr, *prev, *list;
158 * Search the leader. It can happen, that we fall into an endless
159 * loop, because we enter an unreachable loop that is not yet detected.
160 * We break the loop using a sentinel.
162 for (curr = block; !extbb; curr = prev) {
163 prev = get_Block_cfgpred_block(curr, 0);
164 extbb = get_Block_extbb(prev);
165 set_Block_extbb(curr, sentinel);
168 if (extbb == sentinel) {
169 /* We detect a dead loop. We fix this by allocating a
170 * special Extended block
172 ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
174 allocate_extblk(block, env);
175 extbb = get_Block_extbb(block);
176 set_Block_extbb(block, sentinel);
179 /* replace all sentinels by the extbb info */
183 if (get_Block_extbb(prev) != sentinel)
185 set_irn_link(prev, list);
187 prev = get_Block_cfgpred_block(prev, 0);
189 /* arg, the list is in wrong order, turn around and add to the extbb list */
190 for (curr = list; curr; curr = prev) {
191 prev = (ir_node*) get_irn_link(curr);
192 set_irn_link(curr, extbb->link);
194 set_Block_extbb(curr, extbb);
201 * Compute the extended basic blocks for a graph
203 void compute_extbb(ir_graph *irg)
206 ir_extblk *extbb, *next;
209 obstack_free(irg->extbb_obst, NULL);
211 irg->extbb_obst = XMALLOC(struct obstack);
212 obstack_init(irg->extbb_obst);
214 env.obst = irg->extbb_obst;
216 env.start_block = get_irg_start_block(irg);
218 if (! edges_activated(irg)) {
219 /* we don't have edges */
220 assure_irg_outs(irg);
223 /* we must mark nodes, so increase the visited flag */
224 inc_irg_visited(irg);
225 irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
228 * Ok, we have now the list of all extended blocks starting with env.head
229 * every extended block "knowns" the number of blocks in visited and
230 * the blocks are linked in link.
231 * Now we can create arrays that hold the blocks, some kind of "out" edges
232 * for the extended block
234 for (extbb = env.head; extbb; extbb = next) {
235 int i, len = (int)extbb->visited;
238 next = (ir_extblk *)extbb->blks;
240 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
242 for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
243 ir_node *nblock = (ir_node*) get_irn_link(block);
245 /* ensure that the leader is the first one */
246 extbb->blks[len - 1 - i] = block;
247 set_irn_link(block, NULL);
253 for (i = len - 1; i > 0; --i) {
254 ir_node *blk = extbb->blks[i];
256 if (get_Block_n_cfgpreds(blk) != 1) {
257 assert(!"Block for more than one predecessors is no leader");
258 } else if (get_Block_cfgpred_block(blk, 0) != extbb->blks[i - 1]) {
259 assert(!"extbb block order wrong");
268 set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
271 /* free all extended block info. */
272 void free_extbb(ir_graph *irg)
274 if (irg->extbb_obst) {
275 obstack_free(irg->extbb_obst, NULL);
276 xfree(irg->extbb_obst);
277 irg->extbb_obst = NULL;
279 clear_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
282 /* Return the extended block of a node. */
283 ir_extblk *get_nodes_extbb(const ir_node *node)
285 const ir_node *block = is_Block(node) ? node : get_nodes_block(node);
286 return get_Block_extbb(block);
289 /* Gets the visited counter of an extended block. */
290 ir_visited_t (get_extbb_visited)(const ir_extblk *blk)
292 return _get_extbb_visited(blk);
295 /* Sets the visited counter of an extended block. */
296 void (set_extbb_visited)(ir_extblk *blk, ir_visited_t visited)
298 _set_extbb_visited(blk, visited);
301 /* Mark an extended block as visited in a graph. */
302 void (mark_extbb_visited)(ir_extblk *blk)
304 _mark_extbb_visited(blk);
307 /* Returns non-zero if an extended was visited. */
308 int (extbb_visited)(const ir_extblk *blk)
310 return _extbb_visited(blk);
313 /* Returns non-zero if an extended block was NOT visited. */
314 int (extbb_not_visited)(const ir_extblk *blk)
316 return _extbb_not_visited(blk);
319 /* Returns the link field of an extended block. */
320 void *(get_extbb_link)(const ir_extblk *blk)
322 return _get_extbb_link(blk);
325 /* Sets the link field of an extended block. */
326 void (set_extbb_link)(ir_extblk *blk, void *link)
328 _set_extbb_link(blk, link);
331 /* Return the number of basic blocks of an extended block */
332 int (get_extbb_n_blocks)(const ir_extblk *blk)
334 return _get_extbb_n_blocks(blk);
337 /* Return the i'th basic block of an extended block */
338 ir_node *(get_extbb_block)(const ir_extblk *blk, int pos)
340 return _get_extbb_block(blk, pos);
343 /* Return the leader basis block of an extended block. */
344 ir_node *(get_extbb_leader)(const ir_extblk *blk)
346 return _get_extbb_leader(blk);
349 /* Return the node number of an extended block. */
350 long get_extbb_node_nr(const ir_extblk *blk)
352 return get_irn_node_nr(get_extbb_leader(blk));
355 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
360 if (extbb_not_visited(blk)) {
361 mark_extbb_visited(blk);
363 if (pre) pre(blk, env);
365 node = get_extbb_leader(blk);
366 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
367 /* find the corresponding predecessor block. */
368 ir_node *pred = get_Block_cfgpred_block(node, i);
369 if (is_Block(pred)) {
371 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
374 assert(is_Bad(pred));
378 if (post) post(blk, env);
382 /* walks only over extended Block nodes in the graph. Has its own visited
383 flag, so that it can be interleaved with the other walker. */
384 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
386 ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
387 ir_extblk *start_blk = get_Block_extbb(start_bl);
391 inc_irg_block_visited(current_ir_graph);
393 /* assure the start block is the first one */
394 mark_extbb_visited(start_blk);
396 post(start_blk, env);
397 irg_extblock_walk_2(blk, pre, post, env);
399 /* keepalive: the endless loops ... */
400 if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
401 ir_node *node = get_irg_end(current_ir_graph);
402 int arity = get_irn_arity(node);
403 for (i = 0; i < arity; i++) {
404 pred = get_irn_n(node, i);
406 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
407 else if (is_Phi(pred)) {
408 /* Sometimes the blocks died, but are still reachable through Phis.
409 * Make sure the algorithms that try to remove these reach them. */
410 ir_node *block = get_nodes_block(pred);
413 irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
422 /* Walks only over reachable Extended Basic Block nodes in the graph. */
423 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
425 ir_node *endbl = get_irg_end_block(irg);
426 ir_extblk *blk = get_Block_extbb(endbl);
427 ir_graph *rem = current_ir_graph;
428 current_ir_graph = irg;
429 irg_extblock_walk(blk, pre, post, env);
430 current_ir_graph = rem;