3 * File name: ir/ana/irscc.c
4 * Purpose: Compute the strongly connected regions and build
5 * backedge/loop datastructures.
6 * A variation on the Tarjan algorithm. See also [Trapp:99],
8 * Author: Goetz Lindenmaier
12 * Copyright: (c) 2002-2003 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
24 #include "irgraph_t.h"
30 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
32 static ir_loop *current_loop; /* Current loop construction is working
34 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
35 Each loop node gets a unique number.
36 What for? ev. remove. @@@ */
37 static int current_dfn = 1; /* Counter to generate depth first numbering
40 /**********************************************************************/
41 /* Node attributes **/
42 /**********************************************************************/
44 /* A map to get from irnodes to loop nodes. */
45 static pmap *node_loop_map = NULL;
47 /**********************************************************************/
48 /* Node attributes needed for the construction. **/
49 /**********************************************************************/
51 typedef struct scc_info {
52 bool in_stack; /* Marks whether node is on the stack. */
53 int dfn; /* Depth first search number. */
54 int uplink; /* dfn number of ancestor. */
55 // ir_loop *loop; /* Refers to the containing loop. */
57 struct section *section;
63 static INLINE scc_info* new_scc_info(void) {
64 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
65 memset (info, 0, sizeof (scc_info));
70 mark_irn_in_stack (ir_node *n) {
71 assert(get_irn_link(n));
72 ((scc_info *)get_irn_link(n))->in_stack = true;
76 mark_irn_not_in_stack (ir_node *n) {
77 assert(get_irn_link(n));
78 ((scc_info *)get_irn_link(n))->in_stack = false;
82 irn_is_in_stack (ir_node *n) {
83 assert(get_irn_link(n));
84 return ((scc_info *)get_irn_link(n))->in_stack;
88 set_irn_uplink (ir_node *n, int uplink) {
89 assert(get_irn_link(n));
90 ((scc_info *)get_irn_link(n))->uplink = uplink;
94 get_irn_uplink (ir_node *n) {
95 assert(get_irn_link(n));
96 return ((scc_info *)get_irn_link(n))->uplink;
100 set_irn_dfn (ir_node *n, int dfn) {
101 if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
102 assert(get_irn_link(n));
103 ((scc_info *)get_irn_link(n))->dfn = dfn;
107 get_irn_dfn (ir_node *n) {
108 assert(get_irn_link(n));
109 return ((scc_info *)get_irn_link(n))->dfn;
112 /* Uses temporary information to set the loop */
114 set_irn_loop (ir_node *n, ir_loop* loop) {
115 //assert(get_irn_link(n));
116 //((scc_info *)get_irn_link(n))->loop = loop;
117 assert(node_loop_map && "not initialized!");
118 pmap_insert(node_loop_map, (void *)n, (void *)loop);
121 /* Uses temporary information to get the loop */
123 get_irn_loop (ir_node *n) {
125 //assert(get_irn_link(n));
126 //return ((scc_info *)get_irn_link(n))->loop;
127 assert(node_loop_map && "not initialized!");
129 if (pmap_contains(node_loop_map, (void *)n))
130 res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
136 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
140 /* Test whether n is contained in this loop. */
141 for (i = 0; i < get_loop_n_nodes(l); i++)
142 if (n == get_loop_node(l, i)) return l;
144 /* Is this a leave in the loop tree? If so loop not found. */
145 if (get_loop_n_sons(l) == 0) return NULL;
147 /* Else descend in the loop tree. */
148 for (i = 0; i < get_loop_n_sons(l); i++) {
149 res = find_nodes_loop(n, get_loop_son(l, i));
155 /* @@@ temporary implementation, costly!!! */
156 ir_loop * get_irn_loop(ir_node *n) {
157 ir_loop *l = get_irg_loop(current_ir_graph);
158 l = find_nodes_loop(n, l);
163 /**********************************************************************/
165 /**********************************************************************/
167 static ir_node **stack = NULL;
168 static int tos = 0; /* top of stack */
170 static INLINE void init_stack(void) {
172 ARR_RESIZE (ir_node *, stack, 1000);
174 stack = NEW_ARR_F (ir_node *, 1000);
180 static INLINE void free_stack(void) {
192 if (tos == ARR_LEN (stack)) {
193 int nlen = ARR_LEN (stack) * 2;
194 ARR_RESIZE (ir_node *, stack, nlen);
197 mark_irn_in_stack(n);
200 static INLINE ir_node *
203 ir_node *n = stack[--tos];
204 mark_irn_not_in_stack(n);
208 /* The nodes up to n belong to the current loop.
209 Removes them from the stack and adds them to the current loop. */
211 pop_scc_to_loop (ir_node *n)
221 set_irn_dfn(m, loop_node_cnt);
222 add_loop_node(current_loop, m);
223 set_irn_loop(m, current_loop);
225 /* if (m==n) break;*/
229 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
232 /* GL ??? my last son is my grandson??? Removes loops with no
233 ir_nodes in them. Such loops have only another loop as son. (Why
234 can't they have two loops as sons? Does it never get that far? ) */
235 void close_loop (ir_loop *l)
237 int last = get_loop_n_elements(l) - 1;
238 loop_element lelement = get_loop_element(l, last);
239 ir_loop *last_son = lelement.son;
241 if (get_kind(last_son) == k_ir_loop &&
242 get_loop_n_elements(last_son) == 1)
246 lelement = get_loop_element(last_son, 0);
248 if(get_kind(gson) == k_ir_loop)
250 loop_element new_last_son;
252 gson -> outer_loop = l;
253 new_last_son.son = gson;
254 l -> children[last] = new_last_son;
261 /* Removes and unmarks all nodes up to n from the stack.
262 The nodes must be visited once more to assign them to a scc. */
264 pop_scc_unmark_visit (ir_node *n)
270 set_irn_visited(m, 0);
274 /**********************************************************************/
275 /* The loop datastructure. **/
276 /**********************************************************************/
278 /* Allocates a new loop as son of current_loop. Sets current_loop
279 to the new loop and returns the father. */
280 static ir_loop *new_loop (void) {
281 ir_loop *father, *son;
283 father = current_loop;
285 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
286 memset (son, 0, sizeof (ir_loop));
287 son->kind = k_ir_loop;
288 son->children = NEW_ARR_F (loop_element, 0);
292 son->outer_loop = father;
293 add_loop_son(father, son);
294 son->depth = father->depth+1;
295 } else { /* The root loop */
296 son->outer_loop = son;
301 son->loop_nr = get_irp_new_node_nr();
309 /* Finishes the datastructures, copies the arrays to the obstack
311 A. Schoesser: Caution: loop -> sons is gone. */
312 static void mature_loop (ir_loop *loop) {
315 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
316 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
317 DEL_ARR_F(loop->sons);
318 loop->sons = new_sons;
322 /* Returns outer loop, itself if outermost. */
323 ir_loop *get_loop_outer_loop (ir_loop *loop) {
324 assert(loop && loop->kind == k_ir_loop);
325 return loop->outer_loop;
328 /* Returns nesting depth of this loop */
329 int get_loop_depth (ir_loop *loop) {
330 assert(loop); assert(loop->kind == k_ir_loop);
334 /* Returns the number of inner loops */
335 int get_loop_n_sons (ir_loop *loop) {
336 assert(loop && loop->kind == k_ir_loop);
337 return(loop -> n_sons);
340 /* Returns the pos`th loop_node-child *
341 * TODO: This method isn`t very efficient ! *
342 * Returns NULL if there isnt`t a pos`th loop_node */
343 ir_loop *get_loop_son (ir_loop *loop, int pos) {
344 int child_nr = 0, loop_nr = -1;
346 assert(loop && loop->kind == k_ir_loop);
347 while(child_nr < ARR_LEN(loop->children))
349 if(*(loop -> children[child_nr].kind) == k_ir_loop)
352 return(loop -> children[child_nr].son);
358 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
362 add_loop_son(ir_loop *loop, ir_loop *son) {
365 assert(loop && loop->kind == k_ir_loop);
366 assert(get_kind(son) == k_ir_loop);
367 ARR_APP1 (loop_element, loop->children, lson);
371 /* Returns the number of nodes in the loop */
372 int get_loop_n_nodes (ir_loop *loop) {
373 assert(loop); assert(loop->kind == k_ir_loop);
374 return loop -> n_nodes;
375 /* return ARR_LEN(loop->nodes); */
378 /* Returns the pos`th ir_node-child *
379 * TODO: This method isn`t very efficient ! *
380 * Returns NULL if there isnt`t a pos`th ir_node */
381 ir_node *get_loop_node (ir_loop *loop, int pos) {
382 int child_nr, node_nr = -1;
384 assert(loop && loop->kind == k_ir_loop);
385 assert(pos < get_loop_n_nodes(loop));
387 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
388 if(*(loop -> children[child_nr].kind) == k_ir_node)
391 return(loop -> children[child_nr].node);
393 assert(0 && "no child at pos found");
397 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
401 add_loop_node(ir_loop *loop, ir_node *n) {
404 assert(loop && loop->kind == k_ir_loop);
405 assert(get_kind(n) == k_ir_node);
406 ARR_APP1 (loop_element, loop->children, ln);
410 /** Returns the number of elements contained in loop. */
411 int get_loop_n_elements (ir_loop *loop) {
412 assert(loop && loop->kind == k_ir_loop);
413 return(ARR_LEN(loop->children));
417 Returns the pos`th loop element.
418 This may be a loop_node or a ir_node. The caller of this function has
419 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
420 and then select the apropriate "loop_element.node" or "loop_element.son".
423 loop_element get_loop_element (ir_loop *loop, int pos) {
424 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
426 return(loop -> children[pos]);
429 int get_loop_element_pos(ir_loop *loop, void *le) {
430 assert(loop && loop->kind == k_ir_loop);
433 for (i = 0; i < get_loop_n_elements(loop); i++)
434 if (get_loop_element(loop, i).node == le) return i;
438 int get_loop_loop_nr(ir_loop *loop) {
439 assert(loop && loop->kind == k_ir_loop);
441 return loop->loop_nr;
447 /* The outermost loop is remarked in the surrounding graph. */
448 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
452 ir_loop *get_irg_loop(ir_graph *irg) {
458 /**********************************************************************/
459 /* Constructing and destructing the loop/backedge information. **/
460 /**********************************************************************/
462 /* Initialization steps. **********************************************/
465 init_node (ir_node *n, void *env) {
466 set_irn_link (n, new_scc_info());
469 /* Also init nodes not visible in intraproc_view. */
470 /* @@@ init_node is called for too many nodes -- this wastes memory!.
471 The mem is not lost as its on the obstack. */
472 if (get_irn_op(n) == op_Filter) {
473 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
474 init_node(get_Filter_cg_pred(n, i), NULL);
476 if (get_irn_op(n) == op_Block) {
477 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
478 init_node(get_Block_cg_cfgpred(n, i), NULL);
481 /* The following pattern matches only after a call from above pattern. */
482 if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
483 /* @@@ init_node is called for every proj -- this wastes memory!.
484 The mem is not lost as its on the obstack. */
485 ir_node *cb = get_Proj_pred(n);
486 if ((get_irn_op(cb) == op_CallBegin) ||
487 (get_irn_op(cb) == op_EndReg) ||
488 (get_irn_op(cb) == op_EndExcept)) {
490 init_node(get_nodes_Block(cb), NULL);
497 init_scc_common (void) {
500 if (!node_loop_map) node_loop_map = pmap_create();
505 init_scc (ir_graph *irg) {
507 irg_walk_graph (irg, init_node, NULL, NULL);
509 irg_walk (irg, link_to_reg_end, NULL, NULL);
516 cg_walk (init_node, NULL, NULL);
519 /* Condition for breaking the recursion. */
520 static bool is_outermost_Start(ir_node *n) {
521 /* Test whether this is the outermost Start node. If so
522 recursion must end. */
523 if ((get_irn_op(n) == op_Block) &&
524 (get_Block_n_cfgpreds(n) == 1) &&
525 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
526 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
530 /* @@@ Bad condition:
531 not possible in interprocedural view as outermost_graph is
532 not necessarily the only with a dead-end start block.
533 Besides current_ir_graph is not set properly. */
534 if ((get_irn_op(n) == op_Block) &&
535 (n == get_irg_start_block(current_ir_graph))) {
536 if ((!interprocedural_view) ||
537 (current_ir_graph == outermost_ir_graph))
544 /* Don't walk from nodes to blocks except for Control flow operations. */
546 get_start_index(ir_node *n) {
547 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
553 /* Returns current_ir_graph and set it to the irg of predecessor index
555 static INLINE ir_graph *
556 switch_irg (ir_node *n, int index) {
557 ir_graph *old_current = current_ir_graph;
559 if (interprocedural_view) {
560 /* Only Filter and Block nodes can have predecessors in other graphs. */
561 if (get_irn_op(n) == op_Filter)
562 n = get_nodes_Block(n);
563 if (get_irn_op(n) == op_Block) {
564 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
565 if (is_ip_cfop(cfop)) {
566 current_ir_graph = get_irn_irg(cfop);
567 set_irg_visited(current_ir_graph, get_max_irg_visited());
575 /* Walks up the stack passing n and then finding the node
576 where we walked into the irg n is contained in.
577 Here we switch the irg. */
579 find_irg_on_stack (ir_node *n) {
581 ir_graph *old_current = current_ir_graph;
584 if (interprocedural_view) {
585 for (i = tos; i >= 0; i--) {
586 if (stack[i] == n) break;
591 for (; i >= 0; i--) {
593 /*printf(" Visiting %d ", i); DDMN(m);*/
595 current_ir_graph = get_irn_irg(m);
598 if (get_irn_op(m) == op_Filter) {
599 /* Find the corresponding ip_cfop */
600 ir_node *pred = stack[i+1];
602 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
603 if (get_Filter_cg_pred(m, j) == pred) break;
604 if (j >= get_Filter_n_cg_preds(m))
605 /* It is a filter we didn't pass as the predecessors are marked. */
607 assert(get_Filter_cg_pred(m, j) == pred);
618 static void test(ir_node *pred, ir_node *root, ir_node *this) {
620 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
622 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
623 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
624 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
626 printf("tos: %d\n", tos);
628 for (i = tos; i >= 0; i--) {
629 ir_node *n = stack[i];
631 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
636 /* Test for legal loop header: Block, Phi, ... */
637 INLINE static bool is_possible_loop_head(ir_node *n) {
638 return ((get_irn_op(n) == op_Block) ||
639 (get_irn_op(n) == op_Phi) ||
640 ((get_irn_op(n) == op_Filter) && interprocedural_view));
643 /* Returns true if n is a loop header, i.e., it is a Block, Phi
644 or Filter node and has predecessors within the loop and out
646 @arg root: only needed for assertion. */
648 is_head (ir_node *n, ir_node *root)
651 int some_outof_loop = 0, some_in_loop = 0;
653 /* Test for legal loop header: Block, Phi, ... */
654 if (!is_possible_loop_head(n))
657 if (!is_outermost_Start(n)) {
658 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
659 ir_node *pred = get_irn_n(n, i);
661 if (is_backedge(n, i)) continue;
662 if (!irn_is_in_stack(pred)) {
665 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
670 return some_outof_loop && some_in_loop;
673 /* Returns index of the predecessor with the smallest dfn number
674 greater-equal than limit. */
676 smallest_dfn_pred (ir_node *n, int limit)
678 int i, index = -2, min = -1;
680 if (!is_outermost_Start(n)) {
681 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
682 ir_node *pred = get_irn_n(n, i);
684 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
685 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
687 min = get_irn_dfn(pred);
694 /* Returns index of the predecessor with the largest dfn number. */
696 largest_dfn_pred (ir_node *n)
698 int i, index = -2, max = -1;
700 if (!is_outermost_Start(n)) {
701 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
702 ir_node *pred = get_irn_n(n, i);
703 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
704 if (get_irn_dfn(pred) > max) {
706 max = get_irn_dfn(pred);
713 /* Searches the stack for possible loop heads. Tests these for backedges.
714 If it finds a head with an unmarked backedge it marks this edge and
715 returns the tail of the loop.
716 If it finds no backedge returns NULL.
717 ("disable_backedge" in fiasco) */
720 find_tail (ir_node *n) {
722 int i, res_index = -2;
725 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
728 m = stack[tos-1]; /* tos = top of stack */
729 if (is_head (m, n)) {
730 res_index = smallest_dfn_pred(m, 0);
731 if ((res_index == -2) && /* no smallest dfn pred found. */
735 if (m == n) return NULL;
736 for (i = tos-2; ; --i) {
738 if (is_head (m, n)) {
739 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
740 if (res_index == -2) /* no smallest dfn pred found. */
741 res_index = largest_dfn_pred (m);
746 assert (res_index > -2);
748 set_backedge (m, res_index);
749 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
753 /* The core algorithm. *****************************************/
755 static void scc (ir_node *n) {
757 // GL @@@ remove experimental stuff ir_graph *rem;
759 if (irn_visited(n)) return;
762 /* Initialize the node */
763 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
764 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
765 set_irn_loop(n, NULL);
768 /* What's this good for?
769 n->ana.scc.section = NULL;
774 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
775 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
776 so is_backedge does not access array[-1] but correctly returns false! */
778 if (!is_outermost_Start(n)) {
779 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
781 if (is_backedge(n, i)) continue;
783 m = get_irn_n(n, i); /*get_irn_ip_pred(n, i);*/
784 if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
786 // GL @@@ remove experimental stuff /*return_recur(n, i);*/
788 if (irn_is_in_stack(m)) {
789 /* Uplink of m is smaller if n->m is a backedge.
790 Propagate the uplink to mark the loop. */
791 if (get_irn_uplink(m) < get_irn_uplink(n))
792 set_irn_uplink(n, get_irn_uplink(m));
797 if (get_irn_dfn(n) == get_irn_uplink(n)) {
798 /* This condition holds for the node with the incoming backedge.
799 AS: That is: For the loop head. */
800 ir_node *tail = find_tail(n);
802 /* We found a new inner loop! */
804 /* This is an adaption of the algorithm from fiasco / optscc to
805 * avoid loops without Block or Phi as first node. This should
806 * severely reduce the number of evaluations of nodes to detect
807 * a fixpoint in the heap analyses.
808 * Firther it avoids loops without firm nodes that cause errors
809 * in the heap analyses. */
810 #define NO_LOOPS_WITHOUT_HEAD 1
811 #if NO_LOOPS_WITHOUT_HEAD
814 if (get_loop_n_elements(current_loop) > 0) {
822 ir_loop *l = new_loop();
825 /* Remove the loop from the stack ... */
826 pop_scc_unmark_visit (n);
827 /* and recompute it in a better order; and so that it goes into
829 // GL @@@ remove experimental stuff rem = find_irg_on_stack(tail);
832 // GL @@@ remove experimental stuff current_ir_graph = rem;
834 assert (irn_visited(n));
835 #if NO_LOOPS_WITHOUT_HEAD
840 /* AS: No inner loop was found. Pop all nodes from the stack
841 to the current loop. */
847 /* Constructs backedge information for irg. In interprocedural view constructs
848 backedges for all methods called by irg, too. */
849 void construct_backedges(ir_graph *irg) {
850 ir_graph *rem = current_ir_graph;
853 assert(!interprocedural_view &&
854 "not implemented, use construct_ip_backedges");
856 current_ir_graph = irg;
857 outermost_ir_graph = irg;
859 init_scc(current_ir_graph);
862 new_loop(); /* sets current_loop */
863 head_rem = current_loop; /* Just for assertion */
865 if (interprocedural_view) {
866 set_irg_visited(current_ir_graph, inc_max_irg_visited());
869 inc_irg_visited(current_ir_graph);
872 scc(get_irg_end(current_ir_graph));
874 if (interprocedural_view) finish_ip_walk();
876 assert(head_rem == current_loop);
877 set_irg_loop(current_ir_graph, current_loop);
878 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
880 irg->loops = current_loop;
884 count_loop (the_loop, &count, &depth);
888 current_ir_graph = rem;
893 void construct_ip_backedges (void) {
894 ir_graph *rem = current_ir_graph;
895 int rem_ipv = interprocedural_view;
898 outermost_ir_graph = get_irp_main_irg();
903 new_loop(); /* sets current_loop */
904 interprocedural_view = 1;
906 inc_max_irg_visited();
907 for (i = 0; i < get_irp_n_irgs(); i++)
908 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
910 for (i = 0; i < get_irp_n_irgs(); i++) {
912 current_ir_graph = get_irp_irg(i);
913 /* Find real entry points */
914 sb = get_irg_start_block(current_ir_graph);
915 if ((get_Block_n_cfgpreds(sb) > 1) ||
916 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
917 /* Compute scc for this graph */
918 outermost_ir_graph = current_ir_graph;
919 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
920 scc(get_irg_end(current_ir_graph));
921 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
922 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
925 set_irg_loop(outermost_ir_graph, current_loop);
926 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
928 current_ir_graph = rem;
929 interprocedural_view = rem_ipv;
932 void construct_ip_backedges (void) {
933 ir_graph *rem = current_ir_graph;
934 int rem_ipv = interprocedural_view;
937 outermost_ir_graph = get_irp_main_irg();
942 new_loop(); /* sets current_loop */
943 interprocedural_view = 1;
945 inc_max_irg_visited();
946 for (i = 0; i < get_irp_n_irgs(); i++)
947 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
949 /** We have to start the walk at the same nodes as cg_walk. **/
950 /* Walk starting at unreachable procedures. Only these
951 * have End blocks visible in interprocedural view. */
952 for (i = 0; i < get_irp_n_irgs(); i++) {
954 current_ir_graph = get_irp_irg(i);
956 sb = get_irg_start_block(current_ir_graph);
958 if ((get_Block_n_cfgpreds(sb) > 1) ||
959 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
961 scc(get_irg_end(current_ir_graph));
964 /* Check whether we walked all procedures: there could be procedures
965 with cyclic calls but no call from the outside. */
966 for (i = 0; i < get_irp_n_irgs(); i++) {
968 current_ir_graph = get_irp_irg(i);
970 /* Test start block: if inner procedure end and end block are not
971 * visible and therefore not marked. */
972 sb = get_irg_start_block(current_ir_graph);
973 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
976 /* Walk all endless loops in inner procedures.
977 * We recognize an inner procedure if the End node is not visited. */
978 for (i = 0; i < get_irp_n_irgs(); i++) {
980 current_ir_graph = get_irp_irg(i);
982 e = get_irg_end(current_ir_graph);
983 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
985 /* Don't visit the End node. */
986 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
990 set_irg_loop(outermost_ir_graph, current_loop);
991 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
993 current_ir_graph = rem;
994 interprocedural_view = rem_ipv;
998 static void reset_backedges(ir_node *n, void *env) {
999 if (is_possible_loop_head(n))
1003 /** Removes all loop information.
1004 Resets all backedges */
1005 void free_loop_information(ir_graph *irg) {
1006 set_irg_loop(irg, NULL);
1007 /* We cannot free the loop nodes, they are on the obstack. */
1008 irg_walk_graph(irg, NULL, reset_backedges, NULL);
1012 void free_all_loop_information (void) {
1014 int rem = interprocedural_view;
1015 interprocedural_view = 1; /* To visit all filter nodes */
1016 for (i = 0; i < get_irp_n_irgs(); i++) {
1017 free_loop_information(get_irp_irg(i));
1019 pmap_destroy(node_loop_map);
1020 node_loop_map = NULL;
1021 interprocedural_view = rem;
1028 /* Debug stuff *************************************************/
1030 static int test_loop_node(ir_loop *l) {
1031 int i, has_node = 0, found_problem = 0;
1033 assert(l && l->kind == k_ir_loop);
1035 if (get_loop_n_elements(l) == 0) {
1036 printf(" Loop completely empty! "); DDML(l);
1038 dump_loop(l, "-ha");
1041 le = get_loop_element(l, 0);
1042 if (*(le.kind) != k_ir_node) {
1043 assert(le.kind && *(le.kind) == k_ir_loop);
1044 printf(" First loop element is not a node! "); DDML(l);
1045 printf(" "); DDML(le.son);
1048 dump_loop(l, "-ha");
1051 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1052 printf(" Wrong node as head! "); DDML(l);
1053 printf(" "); DDMN(le.node);
1055 dump_loop(l, "-ha");
1059 for (i = 0; i < get_loop_n_elements(l); ++i) {
1060 le = get_loop_element(l, i);
1061 if (*(le.kind) == k_ir_node)
1064 if (test_loop_node(le.son)) found_problem = 1;
1068 printf(" Loop has no firm node! "); DDML(l);
1070 dump_loop(l, "-ha");
1073 return found_problem;
1076 /** Prints all loop nodes that
1077 * - do not have any firm nodes, only loop sons
1078 * - the header is not a Phi, Block or Filter.
1080 void find_strange_loop_nodes(ir_loop *l) {
1081 int found_problem = 0;
1082 printf("\nTesting loop "); DDML(l);
1083 found_problem = test_loop_node(l);
1084 printf("Finished Test\n\n");
1085 if (found_problem) exit(0);