3 * File name: ir/ana/irextbb2.c
4 * Purpose: Alternate extended basic block computation
5 * Author: Matthias Braun
9 * Copyright: (c) 2002-2005 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
16 * Alternative algorithm for computing extended basic blocks (using out edges
17 * and execution frequencies)
19 * @author Matthias Braun
21 #include "irextbb_t.h"
24 #include "irgraph_t.h"
25 #include "iredges_t.h"
32 struct obstack *obst; /**< the obstack where allocations took place */
33 ir_extblk *head; /**< head of the list of all extended blocks */
34 exec_freq_t *execfreqs;
38 * allocate a new extended block header.
40 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
42 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
44 extblk->kind = k_ir_extblk;
46 extblk->blks = (ir_node **)env->head;
50 set_Block_extbb(block, extblk);
51 set_irn_link(block, NULL);
57 * add a block to an extended block
59 static void addto_extblk(ir_extblk *extblk, ir_node *block)
61 /* link all blocks belonging to this extended block */
62 set_irn_link(block, extblk->link);
67 set_Block_extbb(block, extblk);
71 * Returns the number of block successors.
72 * we are interested only in 1, 2 and >2.
74 static int get_block_n_succs(ir_node *block) {
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);
91 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
93 static void create_extblk(ir_node *block, env_t *env)
95 if(irn_visited(block))
98 ir_extblk *extblk = allocate_extblk(block, env);
99 mark_irn_visited(block);
101 pick_successor(block, extblk, env);
104 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
106 const ir_edge_t *edge;
107 ir_node *best_succ = NULL;
108 double best_execfreq = -1;
110 /* More than two successors means we have a jump table.
111 * we cannot include a jump target into the current extended
112 * basic block, so create a new one here.
114 if(get_block_n_succs(block) > 2) {
115 const ir_edge_t *edge;
117 foreach_block_succ(block, edge) {
118 ir_node *succ = get_edge_src_irn(edge);
119 create_extblk(succ, env);
125 foreach_block_succ(block, edge) {
126 ir_node *succ = get_edge_src_irn(edge);
129 if(get_Block_n_cfgpreds(succ) > 1) {
130 create_extblk(succ, env);
134 execfreq = get_block_execfreq(env->execfreqs, succ);
136 // remember best sucessor and make non best successor with only 1
137 // pred block to new extbb leaders
138 if(execfreq > best_execfreq) {
139 if(best_succ != NULL) {
140 create_extblk(best_succ, env);
143 best_execfreq = execfreq;
146 create_extblk(succ, env);
150 // add best successor and recursively try to pick more
151 if(best_succ != NULL) {
152 addto_extblk(extblk, best_succ);
153 mark_irn_visited(best_succ);
154 pick_successor(best_succ, extblk, env);
159 * Compute the extended basic blocks for a graph
161 void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) {
163 ir_extblk *extbb, *next;
166 if (irg->extbb_obst) {
167 obstack_free(irg->extbb_obst, NULL);
169 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
171 obstack_init(irg->extbb_obst);
173 env.obst = irg->extbb_obst;
175 env.execfreqs = execfreqs;
177 assure_irg_outs(irg);
179 /* we must mark nodes, so increase the visited flag */
180 inc_irg_visited(irg);
181 create_extblk(get_irg_start_block(irg), &env);
183 // the end block needs a extbb assigned (even for endless loops)
184 endblock = get_irg_end_block(irg);
185 if(!irn_visited(endblock)) {
186 create_extblk(endblock, &env);
190 * Ok, we have now the list of all extended blocks starting with env.head
191 * every extended block "knowns" the number of blocks in visited and
192 * the blocks are linked in link.
193 * Now we can create arrays that hold the blocks, some kind of "out" edges
194 * for the extended block
196 for (extbb = env.head; extbb; extbb = next) {
197 int i, len = (int)extbb->visited;
200 next = (ir_extblk *)extbb->blks;
202 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
204 for (block = extbb->link, i = 0; i < len; ++i) {
205 ir_node *nblock = get_irn_link(block);
207 /* ensure that the leader is the first one */
208 extbb->blks[len - 1 - i] = block;
209 set_irn_link(block, NULL);
214 for(i = 0; i < len; ++i) {
217 ir_printf("%+F", extbb->blks[i]);
226 irg->extblk_state = extblk_valid;