2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Alternative extended basic block computation
23 * @author Matthias Braun
27 * Alternative algorithm for computing extended basic blocks (using out edges
28 * and execution frequencies)
32 #include "irextbb_t.h"
35 #include "irgraph_t.h"
36 #include "iredges_t.h"
43 struct obstack *obst; /**< the obstack where allocations took place */
44 ir_extblk *head; /**< head of the list of all extended blocks */
45 ir_exec_freq *execfreqs;
49 * allocate a new extended block header.
51 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
53 ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
55 extblk->kind = k_ir_extblk;
57 extblk->blks = (ir_node **)env->head;
61 set_Block_extbb(block, extblk);
62 set_irn_link(block, NULL);
68 * add a block to an extended block
70 static void addto_extblk(ir_extblk *extblk, ir_node *block)
72 /* link all blocks belonging to this extended block */
73 set_irn_link(block, extblk->link);
78 set_Block_extbb(block, extblk);
82 * Returns the number of block successors.
83 * we are interested only in 1, 2 and >2.
85 static int get_block_n_succs(ir_node *block)
87 if (edges_activated(current_ir_graph)) {
88 const ir_edge_t *edge;
90 edge = get_block_succ_first(block);
94 edge = get_block_succ_next(block, edge);
98 edge = get_block_succ_next(block, edge);
102 return get_Block_n_cfg_outs(block);
105 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
107 static void create_extblk(ir_node *block, env_t *env)
111 if (irn_visited_else_mark(block))
114 extblk = allocate_extblk(block, env);
116 pick_successor(block, extblk, env);
119 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
121 const ir_edge_t *edge;
122 ir_node *best_succ = NULL;
123 double best_execfreq = -1;
126 More than two successors means we have a jump table.
127 we cannot include a jump target into the current extended
128 basic block, so create a new one here.
130 if (get_block_n_succs(block) > 2) {
131 foreach_block_succ(block, edge) {
132 ir_node *succ = get_edge_src_irn(edge);
133 create_extblk(succ, env);
139 foreach_block_succ(block, edge) {
140 ir_node *succ = get_edge_src_irn(edge);
143 if (irn_visited(succ))
146 if (get_Block_n_cfgpreds(succ) > 1) {
147 create_extblk(succ, env);
151 execfreq = get_block_execfreq(env->execfreqs, succ);
154 Remember best successor and make non best successor with only 1
155 pred block to new extbb leaders.
157 if (execfreq > best_execfreq) {
158 if (best_succ != NULL) {
159 create_extblk(best_succ, env);
162 best_execfreq = execfreq;
166 create_extblk(succ, env);
170 /* add best successor and recursively try to pick more */
171 if (best_succ != NULL) {
172 addto_extblk(extblk, best_succ);
173 mark_irn_visited(best_succ);
174 pick_successor(best_succ, extblk, env);
179 * Compute the extended basic blocks for a graph
181 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs)
184 ir_extblk *extbb, *next;
187 if (irg->extbb_obst) {
188 obstack_free(irg->extbb_obst, NULL);
191 irg->extbb_obst = XMALLOC(struct obstack);
193 obstack_init(irg->extbb_obst);
195 env.obst = irg->extbb_obst;
197 env.execfreqs = execfreqs;
199 assure_irg_outs(irg);
201 /* we must mark nodes, so increase the visited flag */
202 inc_irg_visited(irg);
203 create_extblk(get_irg_start_block(irg), &env);
205 /* the end block needs a extbb assigned (even for endless loops) */
206 endblock = get_irg_end_block(irg);
207 create_extblk(endblock, &env);
210 Ok, we have now the list of all extended blocks starting with env.head
211 every extended block "knowns" the number of blocks in visited and
212 the blocks are linked in link.
213 Now we can create arrays that hold the blocks, some kind of "out" edges
214 for the extended block
216 for (extbb = env.head; extbb; extbb = next) {
217 int i, len = (int)extbb->visited;
220 next = (ir_extblk *)extbb->blks;
222 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
224 for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
225 ir_node *nblock = (ir_node*) get_irn_link(block);
227 /* ensure that the leader is the first one */
228 extbb->blks[len - 1 - i] = block;
229 set_irn_link(block, NULL);
234 for (i = 0; i < len; ++i) {
237 ir_printf("%+F", extbb->blks[i]);
246 set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);