3 * File name: ir/ana/irextbb2.c
4 * Purpose: Alternate extended basic block computation
5 * Author: Matthias Braun
8 * Copyright: (c) 2002-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
15 * Alternative algorithm for computing extended basic blocks (using out edges
16 * and execution frequencies)
18 * @author Matthias Braun
20 #include "irextbb_t.h"
23 #include "irgraph_t.h"
24 #include "iredges_t.h"
31 struct obstack *obst; /**< the obstack where allocations took place */
32 ir_extblk *head; /**< head of the list of all extended blocks */
33 ir_exec_freq *execfreqs;
37 * allocate a new extended block header.
39 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
41 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
43 extblk->kind = k_ir_extblk;
45 extblk->blks = (ir_node **)env->head;
49 set_Block_extbb(block, extblk);
50 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 if (edges_activated(current_ir_graph)) {
75 const ir_edge_t *edge;
77 edge = get_block_succ_first(block);
81 edge = get_block_succ_next(block, edge);
85 edge = get_block_succ_next(block, edge);
89 return get_Block_n_cfg_outs(block);
92 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
94 static void create_extblk(ir_node *block, env_t *env)
98 if (irn_visited(block))
101 extblk = allocate_extblk(block, env);
102 mark_irn_visited(block);
104 pick_successor(block, extblk, env);
107 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
109 const ir_edge_t *edge;
110 ir_node *best_succ = NULL;
111 double best_execfreq = -1;
114 More than two successors means we have a jump table.
115 we cannot include a jump target into the current extended
116 basic block, so create a new one here.
118 if (get_block_n_succs(block) > 2) {
119 const ir_edge_t *edge;
121 foreach_block_succ(block, edge) {
122 ir_node *succ = get_edge_src_irn(edge);
123 create_extblk(succ, env);
129 foreach_block_succ(block, edge) {
130 ir_node *succ = get_edge_src_irn(edge);
133 if(irn_visited(succ))
136 if(get_Block_n_cfgpreds(succ) > 1) {
137 create_extblk(succ, env);
141 execfreq = get_block_execfreq(env->execfreqs, succ);
144 Remember best successor and make non best successor with only 1
145 pred block to new extbb leaders.
147 if (execfreq > best_execfreq) {
148 if (best_succ != NULL) {
149 create_extblk(best_succ, env);
152 best_execfreq = execfreq;
156 create_extblk(succ, env);
160 /* add best successor and recursively try to pick more */
161 if(best_succ != NULL) {
162 addto_extblk(extblk, best_succ);
163 mark_irn_visited(best_succ);
164 pick_successor(best_succ, extblk, env);
169 * Compute the extended basic blocks for a graph
171 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs) {
173 ir_extblk *extbb, *next;
176 if (irg->extbb_obst) {
177 obstack_free(irg->extbb_obst, NULL);
180 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
182 obstack_init(irg->extbb_obst);
184 env.obst = irg->extbb_obst;
186 env.execfreqs = execfreqs;
188 assure_irg_outs(irg);
190 /* we must mark nodes, so increase the visited flag */
191 inc_irg_visited(irg);
192 create_extblk(get_irg_start_block(irg), &env);
194 /* the end block needs a extbb assigned (even for endless loops) */
195 endblock = get_irg_end_block(irg);
196 if (! irn_visited(endblock)) {
197 create_extblk(endblock, &env);
201 Ok, we have now the list of all extended blocks starting with env.head
202 every extended block "knowns" the number of blocks in visited and
203 the blocks are linked in link.
204 Now we can create arrays that hold the blocks, some kind of "out" edges
205 for the extended block
207 for (extbb = env.head; extbb; extbb = next) {
208 int i, len = (int)extbb->visited;
211 next = (ir_extblk *)extbb->blks;
213 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
215 for (block = extbb->link, i = 0; i < len; ++i) {
216 ir_node *nblock = get_irn_link(block);
218 /* ensure that the leader is the first one */
219 extbb->blks[len - 1 - i] = block;
220 set_irn_link(block, NULL);
225 for(i = 0; i < len; ++i) {
228 ir_printf("%+F", extbb->blks[i]);
237 irg->extblk_state = extblk_valid;