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
26 * Alternative algorithm for computing extended basic blocks (using out edges
27 * and execution frequencies)
31 #include "irextbb_t.h"
34 #include "irgraph_t.h"
35 #include "iredges_t.h"
42 struct obstack *obst; /**< the obstack where allocations took place */
43 ir_extblk *head; /**< head of the list of all extended blocks */
44 ir_exec_freq *execfreqs;
48 * allocate a new extended block header.
50 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
52 ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
54 extblk->kind = k_ir_extblk;
56 extblk->blks = (ir_node **)env->head;
60 set_Block_extbb(block, extblk);
61 set_irn_link(block, NULL);
67 * add a block to an extended block
69 static void addto_extblk(ir_extblk *extblk, ir_node *block)
71 /* link all blocks belonging to this extended block */
72 set_irn_link(block, extblk->link);
77 set_Block_extbb(block, extblk);
81 * Returns the number of block successors.
82 * we are interested only in 1, 2 and >2.
84 static int get_block_n_succs(ir_node *block)
86 if (edges_activated(current_ir_graph)) {
87 const ir_edge_t *edge;
89 edge = get_block_succ_first(block);
93 edge = get_block_succ_next(block, edge);
97 edge = get_block_succ_next(block, edge);
101 return get_Block_n_cfg_outs(block);
104 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
106 static void create_extblk(ir_node *block, env_t *env)
110 if (irn_visited_else_mark(block))
113 extblk = allocate_extblk(block, env);
115 pick_successor(block, extblk, env);
118 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
120 const ir_edge_t *edge;
121 ir_node *best_succ = NULL;
122 double best_execfreq = -1;
125 More than two successors means we have a jump table.
126 we cannot include a jump target into the current extended
127 basic block, so create a new one here.
129 if (get_block_n_succs(block) > 2) {
130 foreach_block_succ(block, edge) {
131 ir_node *succ = get_edge_src_irn(edge);
132 create_extblk(succ, env);
138 foreach_block_succ(block, edge) {
139 ir_node *succ = get_edge_src_irn(edge);
142 if (irn_visited(succ))
145 if (get_Block_n_cfgpreds(succ) > 1) {
146 create_extblk(succ, env);
150 execfreq = get_block_execfreq(env->execfreqs, succ);
153 Remember best successor and make non best successor with only 1
154 pred block to new extbb leaders.
156 if (execfreq > best_execfreq) {
157 if (best_succ != NULL) {
158 create_extblk(best_succ, env);
161 best_execfreq = execfreq;
165 create_extblk(succ, env);
169 /* add best successor and recursively try to pick more */
170 if (best_succ != NULL) {
171 addto_extblk(extblk, best_succ);
172 mark_irn_visited(best_succ);
173 pick_successor(best_succ, extblk, env);
177 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs)
180 ir_extblk *extbb, *next;
183 if (irg->extbb_obst) {
184 obstack_free(irg->extbb_obst, NULL);
187 irg->extbb_obst = XMALLOC(struct obstack);
189 obstack_init(irg->extbb_obst);
191 env.obst = irg->extbb_obst;
193 env.execfreqs = execfreqs;
195 assure_irg_outs(irg);
197 /* we must mark nodes, so increase the visited flag */
198 inc_irg_visited(irg);
199 create_extblk(get_irg_start_block(irg), &env);
201 /* the end block needs a extbb assigned (even for endless loops) */
202 endblock = get_irg_end_block(irg);
203 create_extblk(endblock, &env);
206 Ok, we have now the list of all extended blocks starting with env.head
207 every extended block "knowns" the number of blocks in visited and
208 the blocks are linked in link.
209 Now we can create arrays that hold the blocks, some kind of "out" edges
210 for the extended block
212 for (extbb = env.head; extbb; extbb = next) {
213 int i, len = (int)extbb->visited;
216 next = (ir_extblk *)extbb->blks;
218 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
220 for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
221 ir_node *nblock = (ir_node*) get_irn_link(block);
223 /* ensure that the leader is the first one */
224 extbb->blks[len - 1 - i] = block;
225 set_irn_link(block, NULL);
230 for (i = 0; i < len; ++i) {
233 ir_printf("%+F", extbb->blks[i]);
242 set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);