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)
34 #include "irextbb_t.h"
37 #include "irgraph_t.h"
38 #include "iredges_t.h"
45 struct obstack *obst; /**< the obstack where allocations took place */
46 ir_extblk *head; /**< head of the list of all extended blocks */
47 ir_exec_freq *execfreqs;
51 * allocate a new extended block header.
53 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
55 ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
57 extblk->kind = k_ir_extblk;
59 extblk->blks = (ir_node **)env->head;
63 set_Block_extbb(block, extblk);
64 set_irn_link(block, NULL);
70 * add a block to an extended block
72 static void addto_extblk(ir_extblk *extblk, ir_node *block)
74 /* link all blocks belonging to this extended block */
75 set_irn_link(block, extblk->link);
80 set_Block_extbb(block, extblk);
84 * Returns the number of block successors.
85 * we are interested only in 1, 2 and >2.
87 static int get_block_n_succs(ir_node *block) {
88 if (edges_activated(current_ir_graph)) {
89 const ir_edge_t *edge;
91 edge = get_block_succ_first(block);
95 edge = get_block_succ_next(block, edge);
99 edge = get_block_succ_next(block, edge);
103 return get_Block_n_cfg_outs(block);
106 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
108 static void create_extblk(ir_node *block, env_t *env)
112 if (irn_visited(block))
115 extblk = allocate_extblk(block, env);
116 mark_irn_visited(block);
118 pick_successor(block, extblk, env);
121 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
123 const ir_edge_t *edge;
124 ir_node *best_succ = NULL;
125 double best_execfreq = -1;
128 More than two successors means we have a jump table.
129 we cannot include a jump target into the current extended
130 basic block, so create a new one here.
132 if (get_block_n_succs(block) > 2) {
133 const ir_edge_t *edge;
135 foreach_block_succ(block, edge) {
136 ir_node *succ = get_edge_src_irn(edge);
137 create_extblk(succ, env);
143 foreach_block_succ(block, edge) {
144 ir_node *succ = get_edge_src_irn(edge);
147 if(irn_visited(succ))
150 if(get_Block_n_cfgpreds(succ) > 1) {
151 create_extblk(succ, env);
155 execfreq = get_block_execfreq(env->execfreqs, succ);
158 Remember best successor and make non best successor with only 1
159 pred block to new extbb leaders.
161 if (execfreq > best_execfreq) {
162 if (best_succ != NULL) {
163 create_extblk(best_succ, env);
166 best_execfreq = execfreq;
170 create_extblk(succ, env);
174 /* add best successor and recursively try to pick more */
175 if(best_succ != NULL) {
176 addto_extblk(extblk, best_succ);
177 mark_irn_visited(best_succ);
178 pick_successor(best_succ, extblk, env);
183 * Compute the extended basic blocks for a graph
185 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs) {
187 ir_extblk *extbb, *next;
190 if (irg->extbb_obst) {
191 obstack_free(irg->extbb_obst, NULL);
194 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
196 obstack_init(irg->extbb_obst);
198 env.obst = irg->extbb_obst;
200 env.execfreqs = execfreqs;
202 assure_irg_outs(irg);
204 /* we must mark nodes, so increase the visited flag */
205 inc_irg_visited(irg);
206 create_extblk(get_irg_start_block(irg), &env);
208 /* the end block needs a extbb assigned (even for endless loops) */
209 endblock = get_irg_end_block(irg);
210 if (! irn_visited(endblock)) {
211 create_extblk(endblock, &env);
215 Ok, we have now the list of all extended blocks starting with env.head
216 every extended block "knowns" the number of blocks in visited and
217 the blocks are linked in link.
218 Now we can create arrays that hold the blocks, some kind of "out" edges
219 for the extended block
221 for (extbb = env.head; extbb; extbb = next) {
222 int i, len = (int)extbb->visited;
225 next = (ir_extblk *)extbb->blks;
227 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
229 for (block = extbb->link, i = 0; i < len; ++i) {
230 ir_node *nblock = get_irn_link(block);
232 /* ensure that the leader is the first one */
233 extbb->blks[len - 1 - i] = block;
234 set_irn_link(block, NULL);
239 for(i = 0; i < len; ++i) {
242 ir_printf("%+F", extbb->blks[i]);
251 irg->extblk_state = extblk_valid;