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 exec_freq_t *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(get_Block_n_cfgpreds(succ) > 1) {
134 create_extblk(succ, env);
138 execfreq = get_block_execfreq(env->execfreqs, succ);
141 Remember best successor and make non best successor with only 1
142 pred block to new extbb leaders.
144 if (execfreq > best_execfreq) {
145 if (best_succ != NULL) {
146 create_extblk(best_succ, env);
149 best_execfreq = execfreq;
153 create_extblk(succ, env);
157 /* add best successor and recursively try to pick more */
158 if(best_succ != NULL) {
159 addto_extblk(extblk, best_succ);
160 mark_irn_visited(best_succ);
161 pick_successor(best_succ, extblk, env);
166 * Compute the extended basic blocks for a graph
168 void compute_extbb_execfreqs(ir_graph *irg, exec_freq_t *execfreqs) {
170 ir_extblk *extbb, *next;
173 if (irg->extbb_obst) {
174 obstack_free(irg->extbb_obst, NULL);
177 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
179 obstack_init(irg->extbb_obst);
181 env.obst = irg->extbb_obst;
183 env.execfreqs = execfreqs;
185 assure_irg_outs(irg);
187 /* we must mark nodes, so increase the visited flag */
188 inc_irg_visited(irg);
189 create_extblk(get_irg_start_block(irg), &env);
191 /* the end block needs a extbb assigned (even for endless loops) */
192 endblock = get_irg_end_block(irg);
193 if (! irn_visited(endblock)) {
194 create_extblk(endblock, &env);
198 Ok, we have now the list of all extended blocks starting with env.head
199 every extended block "knowns" the number of blocks in visited and
200 the blocks are linked in link.
201 Now we can create arrays that hold the blocks, some kind of "out" edges
202 for the extended block
204 for (extbb = env.head; extbb; extbb = next) {
205 int i, len = (int)extbb->visited;
208 next = (ir_extblk *)extbb->blks;
210 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
212 for (block = extbb->link, i = 0; i < len; ++i) {
213 ir_node *nblock = get_irn_link(block);
215 /* ensure that the leader is the first one */
216 extbb->blks[len - 1 - i] = block;
217 set_irn_link(block, NULL);
222 for(i = 0; i < len; ++i) {
225 ir_printf("%+F", extbb->blks[i]);
234 irg->extblk_state = extblk_valid;