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
24 #include "irextbb_t.h"
27 #include "irgraph_t.h"
28 #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_exec_freq *execfreqs;
41 * allocate a new extended block header.
43 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
45 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
47 extblk->kind = k_ir_extblk;
49 extblk->blks = (ir_node **)env->head;
53 set_Block_extbb(block, extblk);
54 set_irn_link(block, NULL);
60 * add a block to an extended block
62 static void addto_extblk(ir_extblk *extblk, ir_node *block)
64 /* link all blocks belonging to this extended block */
65 set_irn_link(block, extblk->link);
70 set_Block_extbb(block, extblk);
74 * Returns the number of block successors.
75 * we are interested only in 1, 2 and >2.
77 static int get_block_n_succs(ir_node *block) {
78 if (edges_activated(current_ir_graph)) {
79 const ir_edge_t *edge;
81 edge = get_block_succ_first(block);
85 edge = get_block_succ_next(block, edge);
89 edge = get_block_succ_next(block, edge);
93 return get_Block_n_cfg_outs(block);
96 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
98 static void create_extblk(ir_node *block, env_t *env)
102 if (irn_visited(block))
105 extblk = allocate_extblk(block, env);
106 mark_irn_visited(block);
108 pick_successor(block, extblk, env);
111 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
113 const ir_edge_t *edge;
114 ir_node *best_succ = NULL;
115 double best_execfreq = -1;
118 More than two successors means we have a jump table.
119 we cannot include a jump target into the current extended
120 basic block, so create a new one here.
122 if (get_block_n_succs(block) > 2) {
123 const ir_edge_t *edge;
125 foreach_block_succ(block, edge) {
126 ir_node *succ = get_edge_src_irn(edge);
127 create_extblk(succ, env);
133 foreach_block_succ(block, edge) {
134 ir_node *succ = get_edge_src_irn(edge);
137 if(irn_visited(succ))
140 if(get_Block_n_cfgpreds(succ) > 1) {
141 create_extblk(succ, env);
145 execfreq = get_block_execfreq(env->execfreqs, succ);
148 Remember best successor and make non best successor with only 1
149 pred block to new extbb leaders.
151 if (execfreq > best_execfreq) {
152 if (best_succ != NULL) {
153 create_extblk(best_succ, env);
156 best_execfreq = execfreq;
160 create_extblk(succ, env);
164 /* add best successor and recursively try to pick more */
165 if(best_succ != NULL) {
166 addto_extblk(extblk, best_succ);
167 mark_irn_visited(best_succ);
168 pick_successor(best_succ, extblk, env);
173 * Compute the extended basic blocks for a graph
175 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs) {
177 ir_extblk *extbb, *next;
180 if (irg->extbb_obst) {
181 obstack_free(irg->extbb_obst, NULL);
184 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
186 obstack_init(irg->extbb_obst);
188 env.obst = irg->extbb_obst;
190 env.execfreqs = execfreqs;
192 assure_irg_outs(irg);
194 /* we must mark nodes, so increase the visited flag */
195 inc_irg_visited(irg);
196 create_extblk(get_irg_start_block(irg), &env);
198 /* the end block needs a extbb assigned (even for endless loops) */
199 endblock = get_irg_end_block(irg);
200 if (! irn_visited(endblock)) {
201 create_extblk(endblock, &env);
205 Ok, we have now the list of all extended blocks starting with env.head
206 every extended block "knowns" the number of blocks in visited and
207 the blocks are linked in link.
208 Now we can create arrays that hold the blocks, some kind of "out" edges
209 for the extended block
211 for (extbb = env.head; extbb; extbb = next) {
212 int i, len = (int)extbb->visited;
215 next = (ir_extblk *)extbb->blks;
217 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
219 for (block = extbb->link, i = 0; i < len; ++i) {
220 ir_node *nblock = get_irn_link(block);
222 /* ensure that the leader is the first one */
223 extbb->blks[len - 1 - i] = block;
224 set_irn_link(block, NULL);
229 for(i = 0; i < len; ++i) {
232 ir_printf("%+F", extbb->blks[i]);
241 irg->extblk_state = extblk_valid;