2 #include "interval_analysis.h"
4 #include "firm_common_t.h"
14 /*------------------------------------------------------------------*/
15 /* A new in array via a hashmap. */
16 /* The in array refers to the loop the block is contained in if the */
17 /* block is not in blocks loop. */
18 /*------------------------------------------------------------------*/
28 static set *region_attr_set = NULL;
30 int region_attr_cmp(const void *e1, const void *e2, size_t size) {
31 region_attr *ra1 = (region_attr *)e1;
32 region_attr *ra2 = (region_attr *)e2;
33 return (ra1->reg != ra2->reg);
36 static INLINE int attr_set_hash (region_attr *a) {
37 unsigned int v = (unsigned int) a->reg;
41 static INLINE region_attr *get_region_attr(void *region) {
42 region_attr r_attr, *res;
45 res = set_find(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
48 r_attr.in_array = NEW_ARR_F(void *, 0);
49 if (is_ir_loop(region))
50 r_attr.op_array = NEW_ARR_F(void *, 0);
52 r_attr.op_array = NULL;
54 r_attr.n_exc_outs = 0;
55 res = set_insert(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
61 int get_region_n_ins(void *region) {
62 return ARR_LEN(get_region_attr(region)->in_array);
65 void *get_region_in(void *region, int pos) {
66 assert(0 <= pos && pos < get_region_n_ins(region));
67 return (get_region_attr(region)->in_array)[pos];
70 void add_region_in (void *region, void *in) {
71 ARR_APP1(void *, get_region_attr(region)->in_array, in);
72 get_region_attr(in)->n_outs++;
75 int get_region_n_outs(void *region) {
76 return get_region_attr(region)->n_outs;
79 int get_region_n_exc_outs(void *region) {
80 return get_region_attr(region)->n_exc_outs;
83 void inc_region_n_exc_outs(void *region) {
84 (get_region_attr(region)->n_exc_outs)++;
87 void *get_loop_cfop(void *region, int pos) {
88 assert(0 <= pos && pos < get_region_n_ins(region));
89 return (get_region_attr(region)->op_array)[pos];
92 void add_loop_cfop (void *region, void *cfop) {
94 ARR_APP1(void *, get_region_attr(region)->op_array, cfop);
97 static INLINE void exc_outs(void *reg, ir_node *cfop) {
98 if (is_fragile_op(cfop)) inc_region_n_exc_outs(reg);
101 /*------------------------------------------------------------------*/
102 /* Algorithm to construct the interval edges based on a loop tree. */
103 /* Walk a loop and add all edges. Walk inner loops by recursion. */
104 /*------------------------------------------------------------------*/
106 /* return true if outer can be reached from inner via the outer loop relation */
107 static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *cfop) {
108 if (get_loop_outer_loop(inner) == outer) {
109 add_region_in(inner, b);
110 add_loop_cfop(inner, cfop);
117 static int test_loop_nest(ir_node *pred_b, ir_loop *nest) {
118 int i, n_elems = get_loop_n_elements(nest);
120 for (i = 0; (i < n_elems); ++i) {
121 loop_element e = get_loop_element(nest, i);
124 if (e.node == pred_b) return true;
127 if (test_loop_nest(pred_b, e.son)) return true;
135 static int find_inner_loop(ir_node *b, ir_loop *l, ir_node *pred, ir_node *cfop) {
136 int i, n_elems = get_loop_n_elements(l);
139 for (i = 0; (i < n_elems) && !found; ++i) {
140 loop_element e = get_loop_element(l, i);
143 if (e.node == b) return false;
146 found = test_loop_nest(pred, e.son);
148 add_region_in(b, e.son);
149 exc_outs(e.son, cfop);
150 //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
161 static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, ir_node *pred_b, ir_node *cfop) {
162 ir_loop *outer = get_loop_outer_loop(l);
164 int l_pos = get_loop_element_pos(outer, l);
166 assert(l_pos > 0 && "Is this a necessary condition? There could be a perfect nest ...");
168 for (i = l_pos -1, found = false; i > -1 && !found; --i) {
169 ir_loop *k = get_loop_element(outer, i).son;
171 found = test_loop_nest(pred_b, k);
174 //if (is_fragile_op(cfop)) inc_region_n_exc_outs(k);
176 add_loop_cfop(l, cfop);
177 add_region_in(b, NULL);
183 DDMG(current_ir_graph);
194 /* Compute the edges for the interval graph.
196 * @param b The block for which to constuct the edges.
197 * @param l The loop of b.
199 * There are four cases:
200 * - The pred block is in the same loop. Add a normal block-block edge.
201 * - The pred block is in a loop contained in this loop, somewhere down in
202 * the nesting. The predecessor of this block is the outermost loop of the nest
203 * directly contained in l.
204 * - The pred block is in the outer loop of l. l gets an edge to the pred block.
205 * - The outer loop of l contains another loop k just before l. The control flow
206 * branches directly from loop k to loop l. Add an edge l->k. Watch it: k must
207 * not be a direct predecessor of l in the loop tree!
209 static void construct_interval_block(ir_node *b, ir_loop *l) {
210 int i, n_cfgpreds = get_Block_n_cfgpreds(b);
212 if (b == get_irg_start_block(current_ir_graph)) return;
213 /* We want nice blocks. */
214 assert(n_cfgpreds > 0);
216 for (i = 0; i < n_cfgpreds; ++i) {
217 if (is_backedge(b, i)) {
218 if (b != get_loop_element(l, 0).node) {
219 if (get_firm_verbosity()) {
220 printf("Loophead not at loop position 0. "); DDMN(b);
223 /* There are no backedges in the interval decomposition. */
224 add_region_in(b, NULL);
228 ir_node *cfop = skip_Proj(get_Block_cfgpred(b, i));
229 ir_node *pred = get_nodes_block(cfop);
230 /* We want nice blocks. */
231 assert( get_irn_op(pred) != op_Bad
232 && get_irn_op(skip_Proj(get_Block_cfgpred(b, i))) != op_Bad);
233 ir_loop *pred_l = get_irn_loop(pred);
235 add_region_in(b, pred);
236 //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
237 exc_outs(pred, cfop);
239 int found = find_inner_loop(b, l, pred, cfop);
241 if (b != get_loop_element(l, 0).node) {
242 if (get_firm_verbosity()) {
243 printf("Loop entry not at loop position 0. "); DDMN(b);
246 found = find_outer_loop(l, pred_l, pred, cfop);
247 if (found) add_region_in(b, NULL); /* placeholder */
250 found = find_previous_loop(l, pred_l, b, pred, cfop);
253 DDMG(current_ir_graph);
256 assert(is_backedge(b, i));
257 assert(found && "backedge from inner loop");
261 if (b != get_loop_element(l, 0).node) {
262 /* Check for improper region */
263 if (has_backedges(b)) {
264 printf("Improper Region!!!!!!\n");
265 DDMG(current_ir_graph);
273 static void construct_interval_edges(ir_loop *l) {
274 int i, n_elems = get_loop_n_elements(l);
275 for (i = 0; i < n_elems; ++i) {
276 loop_element e = get_loop_element(l, i);
279 construct_interval_block(e.node, l);
282 construct_interval_edges(e.son);
289 void construct_intervals(ir_graph *irg) {
291 ir_graph *rem = current_ir_graph;
292 current_ir_graph = irg;
294 if (!region_attr_set)
295 region_attr_set = new_set(region_attr_cmp, 256);
297 construct_cf_backedges(current_ir_graph);
300 l = get_irg_loop(current_ir_graph);
302 construct_interval_edges(l);
304 current_ir_graph = rem;
307 void free_intervals(void) {
309 if (!region_attr_set) return;
311 for (ins = (void **)pmap_first(region_in_map);
313 ins = (void **)pmap_next(region_in_map)) {
317 del_set(region_attr_set);
318 region_attr_set = NULL;
321 /*------------------------------------------------------------------*/
322 /* A vcg dumper showing an interval decomposition of a cfg. */
324 /*------------------------------------------------------------------*/
326 void dump_region_edges(FILE *F, void *reg) {
327 int i, n_ins = get_region_n_ins(reg);
329 if (is_ir_node(reg) && get_Block_n_cfgpreds((ir_node *)reg) > get_region_n_ins(reg)) {
330 for (i = n_ins; i < get_Block_n_cfgpreds((ir_node *)reg); ++i) {
331 if (is_backedge((ir_node *)reg, i))
332 fprintf (F, "backedge: { sourcename: \"");
334 fprintf (F, "edge: { sourcename: \"");
335 PRINT_NODEID(((ir_node *)reg));
336 fprintf (F, "\" targetname: \"");
337 PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
338 fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
342 for (i = 0; i < n_ins; ++i) {
343 void *target = get_region_in(reg, i);
345 if (is_ir_node(reg)) {
346 if (get_Block_n_cfgpreds((ir_node *)reg) != get_region_n_ins(reg)) {
347 printf("n_cfgpreds = %d, n_ins = %d\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg));
348 DDMN((ir_node *)reg);
352 if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
353 assert(is_ir_node(reg));
354 if (is_backedge((ir_node *)reg, i))
355 fprintf (F, "backedge: { sourcename: \"");
357 fprintf (F, "edge: { sourcename: \"");
358 PRINT_NODEID(((ir_node *)reg));
359 fprintf (F, "\" targetname: \"");
360 PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
361 fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
363 if (!target) continue;
366 fprintf (F, "edge: { sourcename: \"");
367 if (is_ir_node(reg)) {
368 PRINT_NODEID(((ir_node *)reg));
370 PRINT_LOOPID(((ir_loop *)reg));
372 fprintf (F, "\" targetname: \"");
373 if (is_ir_node(target)) {
374 PRINT_NODEID(((ir_node *)target));
376 PRINT_LOOPID(((ir_loop *)target));
379 if (is_ir_node(reg) && is_fragile_op(skip_Proj(get_Block_cfgpred(reg, i))))
380 fprintf(F, EXC_CF_EDGE_ATTR);
385 #include "execution_frequency.h"
387 void dump_interval_block(FILE *F, ir_node *block) {
389 /* This is a block. Dump a node for the block. */
390 fprintf (F, "node: {title: \""); PRINT_NODEID(block);
391 fprintf (F, "\" label: \"");
392 if (block == get_irg_start_block(get_irn_irg(block)))
393 fprintf(F, "Start ");
394 if (block == get_irg_end_block(get_irn_irg(block)))
397 fprintf (F, "%s ", get_op_name(get_irn_op(block)));
399 fprintf(F, " freq: %9.4lf", get_region_exec_freq(block));
400 fprintf(F, " n_outs: %d", get_region_n_outs(block));
401 fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(block));
403 fprintf(F, "info1:\"");
404 if (dump_dominator_information_flag)
405 fprintf(F, "dom depth %d\n", get_Block_dom_depth(block));
407 /* show arity and possible Bad predecessors of the block */
408 fprintf(F, "arity: %d\n", get_Block_n_cfgpreds(block));
409 for (fl = i = 0; i < get_Block_n_cfgpreds(block); ++i) {
410 ir_node *pred = get_Block_cfgpred(block, i);
413 fprintf(F, "Bad pred at pos: ");
414 fprintf(F, "%d ", i);
421 fprintf (F, "\""); /* closing quote of info */
423 if ((block == get_irg_start_block(get_irn_irg(block))) ||
424 (block == get_irg_end_block(get_irn_irg(block))) )
425 fprintf(F, " color:blue ");
427 fprintf(F, " color:yellow ");
432 void dump_interval_loop(FILE *F, ir_loop *l) {
433 int i, n_elems = get_loop_n_elements(l);
435 fprintf(F, "graph: { title: \"");
437 fprintf(F, "\" label: \"loop %d", get_loop_loop_nr(l));
438 fprintf(F, " freq: %9.4lf", get_region_exec_freq(l));
439 fprintf(F, " n_outs: %d", get_region_n_outs(l));
440 fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(l));
441 fprintf(F, "\" status:clustered color:white \n");
443 for (i = 0; i < n_elems; ++i) {
444 loop_element e = get_loop_element(l, i);
445 dump_region_edges(F, e.node);
448 dump_interval_block(F, e.node);
451 dump_interval_loop(F, e.son);
461 void dump_interval_graph(ir_graph *irg, const char *suffix) {
464 if (strncmp(get_entity_name(get_irg_entity(irg)), dump_file_filter, strlen(dump_file_filter)) != 0)
467 f = vcg_open(irg, suffix, "-intervals");
468 dump_vcg_header(f, get_irg_dump_name(irg), NULL);
470 current_ir_graph = irg;
472 dump_interval_loop(f, get_irg_loop(current_ir_graph));