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"
27 struct obstack *obst; /**< the obstack where allocations took place */
28 ir_extblk *head; /**< head of the list of all extended blocks */
32 * allocate a new extended block header.
34 static void allocate_extblk(ir_node *block, env_t *env)
36 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
38 extblk->kind = k_ir_extblk;
40 extblk->blks = (ir_node **)env->head;
44 set_Block_extbb(block, extblk);
45 set_irn_link(block, NULL);
49 * add a block to an extended block
51 static void addto_extblk(ir_extblk *extblk, ir_node *block)
53 /* link all blocks belonging to this extended block */
54 set_irn_link(block, extblk->link);
59 set_Block_extbb(block, extblk);
64 * Pre block-walker. Calculates the extended block info.
66 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
68 int n = get_Block_n_cfgpreds(block);
71 if (n <= 0 || n > 1 || block == get_irg_start_block(current_ir_graph)) {
73 * block is a JOIN-node ie the control flow from
74 * many other blocks joins here. block is a leader.
75 * Note that we handle unreachable blocks (n <= 0) here too.
77 allocate_extblk(block, env);
79 else { /* we have only one control flow predecessor */
80 ir_node *add_to = get_Block_cfgpred_block(block, 0);
82 /* blocks with only one BAD predecessors are leaders too */
84 allocate_extblk(block, env);
88 * Only one control flow predecessor. This block belongs
89 * to the same extended basic block as its predecessor.
91 set_Block_extbb(block, NULL);
99 * Post block-walker. Calculates the extended block info.
100 * During construction, we use the (free) block input of all basic blocks
101 * to point to there previous block.
103 static void post_walk_calc_extbb(ir_node *block, void *ctx)
105 ir_extblk *extbb = get_Block_extbb(block);
107 ir_extblk *sentinel = (ir_extblk *)&_sentinel;
110 ir_node *curr, *prev;
113 * Search the leader. It can happen, that we fall into an endless
114 * loop, because we enter an unreachable loop that is not yet detected.
115 * We break the loop using a sentinel.
117 for (curr = block; !extbb; curr = prev) {
118 prev = get_Block_cfgpred_block(curr, 0);
119 extbb = get_Block_extbb(prev);
120 set_Block_extbb(curr, sentinel);
123 if (extbb == sentinel) {
124 /* We detect a dead loop. We fix this by allocating an
125 * special Extended block
127 ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
129 allocate_extblk(block, env);
130 extbb = get_Block_extbb(block);
131 set_Block_extbb(block, sentinel);
134 /* replace all sentinels by the extbb info */
137 if (get_Block_extbb(prev) != sentinel)
139 set_Block_extbb(prev, extbb);
140 prev = get_Block_cfgpred_block(prev, 0);
146 * Compute the extended basic blocks for a graph
148 void compute_extbb(ir_graph *irg) {
150 ir_extblk *extbb, *next;
153 obstack_free(irg->extbb_obst, NULL);
155 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
157 obstack_init(irg->extbb_obst);
159 env.obst = irg->extbb_obst;
162 irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
165 * Ok, we have now the list of all extended blocks starting with env.head
166 * every extended block "knowns" the number of blocks in visited and
167 * the blocks are linked in link.
168 * Now we can create arrays that hold the blocks, some kind of "out" edges
169 * for the extended block
171 for (extbb = env.head; extbb; extbb = next) {
172 int i, len = (int)extbb->visited;
175 next = (ir_extblk *)extbb->blks;
177 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
179 for (block = extbb->link, i = 0; i < len; ++i) {
180 ir_node *nblock = get_irn_link(block);
182 /* ensure that the leader is the first one */
183 extbb->blks[len - 1 - i] = block;
184 set_irn_link(block, NULL);
192 irg->extblk_state = ir_extblk_info_valid;
195 /* free all extended block info. */
196 void free_extbb(ir_graph *irg) {
197 if (irg->extbb_obst) {
198 obstack_free(irg->extbb_obst, NULL);
199 xfree(irg->extbb_obst);
200 irg->extbb_obst = NULL;
202 irg->extblk_state = ir_extblk_info_none;
205 /* Return the extended block of a node. */
206 ir_extblk *get_nodes_extbb(ir_node *node) {
207 ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
208 return get_Block_extbb(block);
211 /* Gets the visited counter of an extended block. */
212 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
213 return _get_extbb_visited(blk);
216 /* Sets the visited counter of an extended block. */
217 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
218 _set_extbb_visited(blk, visited);
221 /* Mark an extended block as visited in a graph. */
222 void (mark_extbb_visited)(ir_extblk *blk) {
223 _mark_extbb_visited(blk);
226 /* Returns non-zero if an extended was visited. */
227 int (extbb_visited)(const ir_extblk *blk) {
228 return _extbb_visited(blk);
231 /* Returns non-zero if an extended block was NOT visited. */
232 int (extbb_not_visited)(const ir_extblk *blk) {
233 return _extbb_not_visited(blk);
236 /* Returns the link field of an extended block. */
237 void *(get_extbb_link)(const ir_extblk *blk) {
238 return _get_extbb_link(blk);
241 /* Sets the link field of an extended block. */
242 void (set_extbb_link)(ir_extblk *blk, void *link) {
243 _set_extbb_link(blk, link);
246 /* Return the number of basic blocks of an extended block */
247 int (get_extbb_n_blocks)(const ir_extblk *blk) {
248 return _get_extbb_n_blocks(blk);
251 /* Return the i'th basic block of an extended block */
252 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
253 return _get_extbb_block(blk, pos);
256 /* Return the leader basis block of an extended block. */
257 ir_node *(get_extbb_leader)(ir_extblk *blk) {
258 return _get_extbb_leader(blk);
261 /* Return the node number of an extended block. */
262 long get_extbb_node_nr(ir_extblk *blk) {
263 return get_irn_node_nr(get_extbb_leader(blk));