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 Implementation of interval analysis
30 #include "interval_analysis.h"
31 #include "execution_frequency.h"
32 #include "firm_common_t.h"
44 DEBUG_ONLY(static firm_dbg_module_t *dbg);
46 /*------------------------------------------------------------------*/
47 /* A new in array via a hashmap. */
48 /* The in array refers to the loop the block is contained in if the */
49 /* block is not in blocks loop. */
50 /*------------------------------------------------------------------*/
52 /** The attributes of a region. */
54 void *reg; /**< The region: A block or a loop. */
55 void **in_array; /**< New in-array for this region, may contain NULL (to be synchronized with block inputs). */
56 void **op_array; /**< If reg is a loop, the control flow operations leading to this loop. */
57 int n_outs; /**< The number of out edges of this region. */
58 int n_exc_outs; /**< The number of exception out edges of this region. */
61 /** A Hashset containing the region attributes. */
62 static set *region_attr_set = NULL;
65 * Compare two region attributes for identical regions.
67 static int region_attr_cmp(const void *e1, const void *e2, size_t size) {
68 region_attr *ra1 = (region_attr *)e1;
69 region_attr *ra2 = (region_attr *)e2;
71 return (ra1->reg != ra2->reg);
74 /** Hash a region attribute (the region only). */
75 static inline int attr_set_hash(region_attr *a) {
76 return HASH_PTR(a->reg);
80 * Return the region attribute for a given region.
81 * Allocate one if not exists.
83 * @param region the region
85 static inline region_attr *get_region_attr(void *region) {
86 region_attr r_attr, *res;
89 res = set_find(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
92 r_attr.in_array = NEW_ARR_F(void *, 0);
93 if (is_ir_loop(region))
94 r_attr.op_array = NEW_ARR_F(void *, 0);
96 r_attr.op_array = NULL;
98 r_attr.n_exc_outs = 0;
99 res = set_insert(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
105 int get_region_n_ins(void *region) {
106 return ARR_LEN(get_region_attr(region)->in_array);
109 void *get_region_in(void *region, int pos) {
110 assert(0 <= pos && pos < get_region_n_ins(region));
111 return ((get_region_attr(region)->in_array)[pos]);
114 void add_region_in(void *region, void *in) {
115 ARR_APP1(void *, get_region_attr(region)->in_array, in);
116 get_region_attr(in)->n_outs++;
119 int get_region_n_outs(void *region) {
120 return get_region_attr(region)->n_outs;
123 int get_region_n_exc_outs(void *region) {
124 return get_region_attr(region)->n_exc_outs;
127 void inc_region_n_exc_outs(void *region) {
128 (get_region_attr(region)->n_exc_outs)++;
131 void *get_loop_cfop(void *region, int pos) {
132 assert(0 <= pos && pos < get_region_n_ins(region));
133 return ((get_region_attr(region)->op_array)[pos]);
136 /** Add a control flow op to a loop region. */
137 static inline void add_loop_cfop(void *region, void *cfop) {
139 ARR_APP1(void *, get_region_attr(region)->op_array, cfop);
143 * Increase the number of exception outputs if a control flow
144 * operation (that is inside the given region) is a fragile operation.
146 * @param reg a region
147 * @param cfop a control flow operation leaving this region
149 static inline void exc_outs(void *reg, ir_node *cfop) {
150 if (is_fragile_op(cfop) || is_fragile_Proj(cfop))
151 inc_region_n_exc_outs(reg);
154 /*------------------------------------------------------------------*/
155 /* Algorithm to construct the interval edges based on a loop tree. */
156 /* Walk a loop and add all edges. Walk inner loops by recursion. */
157 /*------------------------------------------------------------------*/
160 * Check if the loop of a given block is the outer loop of the current one.
161 * If yes, add an edge from the block to the region of the current loop.
163 * @param inner the current (possible inner) loop
164 * @param outer the loop of blk
166 * @param cfop the control flow op leaving blk
168 * @return non-zero if outer can be reached from inner via the outer loop relation
170 static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *blk, ir_node *cfop) {
171 if (get_loop_outer_loop(inner) == outer) {
172 add_region_in(inner, blk);
173 add_loop_cfop(inner, cfop);
181 * Check if a given block can be found in a given loop
182 * or its nesting loops.
187 static int test_loop_nest(ir_node *blk, ir_loop *loop) {
188 int i, n_elems = get_loop_n_elements(loop);
190 for (i = 0; i < n_elems; ++i) {
191 loop_element e = get_loop_element(loop, i);
198 if (test_loop_nest(blk, e.son))
209 * Check if pred is a block from an inner loop jumping via cfop to the block blk.
210 * If yes, add an edge from pred's loop to the region blk.
213 * @param l the loop of blk
214 * @param pred a predecessor block of blk
215 * @param cfop the control flow op from pred to blk
217 * @return non-zero if pred is from an inner loop
219 static int find_inner_loop(ir_node *blk, ir_loop *l, ir_node *pred, ir_node *cfop) {
220 int i, n_elems = get_loop_n_elements(l);
223 for (i = 0; i < n_elems; ++i) {
224 loop_element e = get_loop_element(l, i);
228 /* stop the search if we reach blk, pred cannot be found
234 found = test_loop_nest(pred, e.son);
236 add_region_in(blk, e.son);
237 exc_outs(e.son, cfop);
249 * Check if a predecessor block pred_b is from a previous loop of the
252 * @param l the loop of the block b
253 * @param pred_l the loop of the block pred_b
255 * @param pred_b the predecessor block
256 * @param cfop the control flow node leaving pred_b for b
258 * @return non-zero if pred is from an previous loop
260 static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b,
261 ir_node *pred_b, ir_node *cfop)
263 ir_loop *outer = get_loop_outer_loop(l);
265 int l_pos = get_loop_element_pos(outer, l);
268 assert(l_pos > 0 && "Is this a necessary condition? There could be a perfect nest ...");
270 for (i = l_pos -1, found = 0; i > -1 && !found; --i) {
271 ir_loop *k = get_loop_element(outer, i).son;
273 found = test_loop_nest(pred_b, k);
277 add_loop_cfop(l, cfop);
278 /* placeholder: the edge is in the loop region */
279 add_region_in(b, NULL);
289 * Compute the edges for the interval graph.
291 * @param blk The block for which to construct the edges.
292 * @param l The loop of blk.
294 * There are four cases:
295 * - A predecessor block is in the same loop. Add a normal block-block edge.
296 * - A predecessor block is in a loop contained in this loop, somewhere down in
297 * the nesting. The predecessor of this block is the outermost loop of the nest
298 * directly contained in l.
299 * - A predecessor block is in the outer loop of l. l gets an edge to the predecessor block.
300 * - The outer loop of l contains another loop k just before l. The control flow
301 * branches directly from loop k to loop l. Add an edge l->k. Watch it: k must
302 * not be a direct predecessor of l in the loop tree!
304 static void construct_interval_block(ir_node *blk, ir_loop *l) {
307 if (blk == get_irg_start_block(current_ir_graph))
310 n_cfgpreds = get_Block_n_cfgpreds(blk);
311 /* We want nice blocks. */
312 assert(n_cfgpreds > 0);
314 for (i = 0; i < n_cfgpreds; ++i) {
315 ir_node *cfop, *pred;
318 if (is_backedge(blk, i)) {
319 if (blk != get_loop_element(l, 0).node) {
320 DB((dbg, LEVEL_1, "Loophead not at loop position 0. %+F\n", blk));
322 /* There are no backedges in the interval decomposition. */
323 add_region_in(blk, NULL);
327 cfop = get_Block_cfgpred(blk, i);
329 ir_node *op = skip_Proj(cfop);
330 if (is_fragile_op(op) && get_Proj_proj(cfop) == pn_Generic_X_except) {
332 * Skip the Proj for the exception flow only, leave the
333 * not exception flow Proj's intact.
334 * If the old semantic is used (only one exception Proj) this
335 * should lead to the same representation as before.
339 assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop)));
343 pred = skip_Proj(get_nodes_block(cfop));
344 /* We want nice blocks. */
345 assert(!is_Bad(pred) && !is_Bad(skip_Proj(get_Block_cfgpred(blk, i))));
346 pred_l = get_irn_loop(pred);
348 /* first case: both blocks are in the same loop */
349 add_region_in(blk, pred);
350 exc_outs(pred, cfop);
352 /* check for the second case: pred is from an inner loop */
353 int found = find_inner_loop(blk, l, pred, cfop);
355 if (blk != get_loop_element(l, 0).node) {
356 DB((dbg, LEVEL_1, "Loop entry not at loop position 0. %+F\n", blk));
358 /* check for the third case: pred is in an outer loop */
359 found = find_outer_loop(l, pred_l, pred, cfop);
361 /* placeholder: the edge is added to the loop region */
362 add_region_in(blk, NULL);
364 /* fourth case: pred is from the previous loop */
365 found = find_previous_loop(l, pred_l, blk, pred, cfop);
367 assert(found && "decomposition failed");
373 if (blk != get_loop_element(l, 0).node) {
374 /* Check for improper region. But these can happen, so what? */
375 if (has_backedges(blk)) {
376 DB((dbg, LEVEL_1, "Improper Region %+F\n", blk));
384 * Construct interval edges for a given (control flow) loop.
386 * @param l the cf loop
388 static void construct_interval_edges(ir_loop *l) {
389 int i, n_elems = get_loop_n_elements(l);
390 for (i = 0; i < n_elems; ++i) {
391 loop_element e = get_loop_element(l, i);
394 construct_interval_block(e.node, l);
397 construct_interval_edges(e.son);
405 void construct_intervals(ir_graph *irg) {
407 ir_graph *rem = current_ir_graph;
409 current_ir_graph = irg;
411 FIRM_DBG_REGISTER(dbg, "firm.ana.interval");
413 if (region_attr_set == NULL)
414 region_attr_set = new_set(region_attr_cmp, 256);
416 construct_cf_backedges(current_ir_graph);
418 l = get_irg_loop(current_ir_graph);
420 construct_interval_edges(l);
422 current_ir_graph = rem;
425 void free_intervals(void) {
428 if (region_attr_set == NULL)
431 for (res = set_first(region_attr_set);
433 res = set_next(region_attr_set)) {
434 DEL_ARR_F(res->in_array);
435 if (res->op_array != NULL)
436 DEL_ARR_F(res->op_array);
439 del_set(region_attr_set);
440 region_attr_set = NULL;
443 /*------------------------------------------------------------------*/
444 /* A vcg dumper showing an interval decomposition of a cfg. */
446 /*------------------------------------------------------------------*/
448 void dump_region_edges(FILE *F, void *reg) {
449 int i, n_ins = get_region_n_ins(reg);
451 if (is_ir_node(reg)) {
453 if (get_Block_n_cfgpreds(irn) > get_region_n_ins(reg)) {
454 for (i = n_ins; i < get_Block_n_cfgpreds(irn); ++i) {
455 if (is_backedge(irn, i))
456 fprintf(F, "backedge: { sourcename: \"");
458 fprintf(F, "edge: { sourcename: \"");
460 fprintf(F, "\" targetname: \"");
461 PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred(irn, i))));
462 fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
467 for (i = 0; i < n_ins; ++i) {
468 void *target = get_region_in(reg, i);
470 if (is_ir_node(reg)) {
472 if (get_Block_n_cfgpreds(irn) != get_region_n_ins(reg)) {
473 ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds(irn), get_region_n_ins(reg), irn);
477 if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
478 assert(is_ir_node(reg));
479 if (is_backedge((ir_node *)reg, i))
480 fprintf(F, "backedge: { sourcename: \"");
482 fprintf(F, "edge: { sourcename: \"");
483 PRINT_NODEID(((ir_node *)reg));
484 fprintf(F, "\" targetname: \"");
485 PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
486 fprintf(F, "\" " BLOCK_EDGE_ATTR "}\n");
488 if (!target) continue;
491 fprintf(F, "edge: { sourcename: \"");
492 if (is_ir_node(reg)) {
493 PRINT_NODEID(((ir_node *)reg));
495 PRINT_LOOPID(((ir_loop *)reg));
497 fprintf(F, "\" targetname: \"");
498 if (is_ir_node(target)) {
499 PRINT_NODEID(((ir_node *)target));
501 PRINT_LOOPID(((ir_loop *)target));
504 if (is_ir_node(reg) && is_fragile_op(skip_Proj(get_Block_cfgpred(reg, i))))
505 fprintf(F, EXC_CF_EDGE_ATTR);
510 #include "execution_frequency.h"
512 static void dump_interval_block(FILE *F, ir_node *block) {
514 /* This is a block. Dump a node for the block. */
515 fprintf(F, "node: {title: \""); PRINT_NODEID(block);
516 fprintf(F, "\" label: \"");
517 if (block == get_irg_start_block(get_irn_irg(block)))
518 fprintf(F, "Start ");
519 if (block == get_irg_end_block(get_irn_irg(block)))
522 fprintf(F, "%s ", get_op_name(get_irn_op(block)));
524 fprintf(F, " freq: %9.4lf", get_region_exec_freq(block));
525 fprintf(F, " n_outs: %d", get_region_n_outs(block));
526 fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(block));
528 fprintf(F, "info1:\"");
529 if (dump_dominator_information_flag)
530 fprintf(F, "dom depth %d\n", get_Block_dom_depth(block));
532 /* show arity and possible Bad predecessors of the block */
533 fprintf(F, "arity: %d\n", get_Block_n_cfgpreds(block));
534 for (fl = i = 0; i < get_Block_n_cfgpreds(block); ++i) {
535 ir_node *pred = get_Block_cfgpred(block, i);
538 fprintf(F, "Bad pred at pos: ");
539 fprintf(F, "%d ", i);
546 fprintf(F, "\""); /* closing quote of info */
548 if ((block == get_irg_start_block(get_irn_irg(block))) ||
549 (block == get_irg_end_block(get_irn_irg(block))) )
550 fprintf(F, " color:blue ");
552 fprintf(F, " color:yellow ");
557 static void dump_interval_loop(FILE *F, ir_loop *l) {
558 int i, n_elems = get_loop_n_elements(l);
560 fprintf(F, "graph: { title: \"");
562 fprintf(F, "\" label: \"loop %d", get_loop_loop_nr(l));
563 fprintf(F, " freq: %9.4lf", get_region_exec_freq(l));
564 fprintf(F, " n_outs: %d", get_region_n_outs(l));
565 fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(l));
566 fprintf(F, "\" status:clustered color:white \n");
568 for (i = 0; i < n_elems; ++i) {
569 loop_element e = get_loop_element(l, i);
570 dump_region_edges(F, e.node);
573 dump_interval_block(F, e.node);
576 dump_interval_loop(F, e.son);
587 void dump_interval_graph(ir_graph *irg, const char *suffix) {
591 if (!is_filtered_dump_name(get_entity_ident(get_irg_entity(irg))))
594 f = vcg_open(irg, suffix, "-intervals");
595 dump_vcg_header(f, get_irg_dump_name(irg), NULL, NULL);
597 rem = current_ir_graph;
598 current_ir_graph = irg;
600 dump_interval_loop(f, get_irg_loop(irg));
605 current_ir_graph = rem;