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"
31 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
33 static ir_loop *current_loop; /* Current loop construction is working
35 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
36 Each loop node gets a unique number.
37 What for? ev. remove. @@@ */
38 static int current_dfn = 1; /* Counter to generate depth first numbering
41 /**********************************************************************/
42 /* Node attributes **/
43 /**********************************************************************/
45 /* A map to get from irnodes to loop nodes. */
46 static pmap *node_loop_map = NULL;
48 /**********************************************************************/
49 /* Node attributes needed for the construction. **/
50 /**********************************************************************/
52 typedef struct scc_info {
53 bool in_stack; /* Marks whether node is on the stack. */
54 int dfn; /* Depth first search number. */
55 int uplink; /* dfn number of ancestor. */
56 /* ir_loop *loop; *//* Refers to the containing loop. */
58 struct section *section;
64 static INLINE scc_info* new_scc_info(void) {
65 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
66 memset (info, 0, sizeof (scc_info));
71 mark_irn_in_stack (ir_node *n) {
72 assert(get_irn_link(n));
74 /* ((scc_info *)get_irn_link(n))->in_stack = true; */
75 ((scc_info *)n->link)->in_stack = true;
79 mark_irn_not_in_stack (ir_node *n) {
80 assert(get_irn_link(n));
82 /* ((scc_info *)get_irn_link(n))->in_stack = false; */
83 ((scc_info *)n->link)->in_stack = false;
87 irn_is_in_stack (ir_node *n) {
88 assert(get_irn_link(n));
90 /* return ((scc_info *)get_irn_link(n))->in_stack; */
91 return ((scc_info *)n->link)->in_stack;
95 set_irn_uplink (ir_node *n, int uplink) {
96 assert(get_irn_link(n));
98 /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
99 ((scc_info *)n->link)->uplink = uplink;
103 get_irn_uplink (ir_node *n) {
104 assert(get_irn_link(n));
105 /* from fast to slow */
106 /* return ((scc_info *)get_irn_link(n))->uplink; */
107 return ((scc_info *)n->link)->uplink;
111 set_irn_dfn (ir_node *n, int dfn) {
112 assert(get_irn_link(n));
114 /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
115 ((scc_info *)n->link)->dfn = dfn;
119 get_irn_dfn (ir_node *n) {
120 assert(get_irn_link(n));
122 /* return ((scc_info *)get_irn_link(n))->dfn; */
123 return ((scc_info *)n->link)->dfn;
127 /* Replaced node loop map by real field as hash access dominates runtime
128 * of the algorithm. ! */
129 /* Uses temporary information to set the loop */
131 set_irn_loop (ir_node *n, ir_loop* loop) {
132 assert(node_loop_map && "not initialized!");
133 pmap_insert(node_loop_map, (void *)n, (void *)loop);
136 /* Uses temporary information to get the loop */
138 get_irn_loop (ir_node *n) {
140 if (!node_loop_map) return NULL;
142 if (pmap_contains(node_loop_map, (void *)n))
143 res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
149 set_irn_loop (ir_node *n, ir_loop* loop) {
153 /* Uses temporary information to get the loop */
155 get_irn_loop (ir_node *n) {
162 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
166 /* Test whether n is contained in this loop. */
167 for (i = 0; i < get_loop_n_nodes(l); i++)
168 if (n == get_loop_node(l, i)) return l;
170 /* Is this a leave in the loop tree? If so loop not found. */
171 if (get_loop_n_sons(l) == 0) return NULL;
173 /* Else descend in the loop tree. */
174 for (i = 0; i < get_loop_n_sons(l); i++) {
175 res = find_nodes_loop(n, get_loop_son(l, i));
181 /* @@@ temporary implementation, costly!!! */
182 ir_loop * get_irn_loop(ir_node *n) {
183 ir_loop *l = get_irg_loop(current_ir_graph);
184 l = find_nodes_loop(n, l);
189 /**********************************************************************/
191 /**********************************************************************/
193 static ir_node **stack = NULL;
194 static int tos = 0; /* top of stack */
196 static INLINE void init_stack(void) {
198 ARR_RESIZE (ir_node *, stack, 1000);
200 stack = NEW_ARR_F (ir_node *, 1000);
206 static INLINE void free_stack(void) {
218 if (tos == ARR_LEN (stack)) {
219 int nlen = ARR_LEN (stack) * 2;
220 ARR_RESIZE (ir_node *, stack, nlen);
223 mark_irn_in_stack(n);
226 static INLINE ir_node *
229 ir_node *n = stack[--tos];
230 mark_irn_not_in_stack(n);
234 /* The nodes up to n belong to the current loop.
235 Removes them from the stack and adds them to the current loop. */
237 pop_scc_to_loop (ir_node *n)
247 set_irn_dfn(m, loop_node_cnt);
248 add_loop_node(current_loop, m);
249 set_irn_loop(m, current_loop);
251 /* if (m==n) break;*/
255 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
258 /* GL ??? my last son is my grandson??? Removes loops with no
259 ir_nodes in them. Such loops have only another loop as son. (Why
260 can't they have two loops as sons? Does it never get that far? ) */
261 void close_loop (ir_loop *l)
263 int last = get_loop_n_elements(l) - 1;
264 loop_element lelement = get_loop_element(l, last);
265 ir_loop *last_son = lelement.son;
267 if (get_kind(last_son) == k_ir_loop &&
268 get_loop_n_elements(last_son) == 1)
272 lelement = get_loop_element(last_son, 0);
274 if(get_kind(gson) == k_ir_loop)
276 loop_element new_last_son;
278 gson -> outer_loop = l;
279 new_last_son.son = gson;
280 l -> children[last] = new_last_son;
287 /* Removes and unmarks all nodes up to n from the stack.
288 The nodes must be visited once more to assign them to a scc. */
290 pop_scc_unmark_visit (ir_node *n)
296 set_irn_visited(m, 0);
300 /**********************************************************************/
301 /* The loop datastructure. **/
302 /**********************************************************************/
304 /* Allocates a new loop as son of current_loop. Sets current_loop
305 to the new loop and returns the father. */
306 static ir_loop *new_loop (void) {
307 ir_loop *father, *son;
309 father = current_loop;
311 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
312 memset (son, 0, sizeof (ir_loop));
313 son->kind = k_ir_loop;
314 son->children = NEW_ARR_F (loop_element, 0);
318 son->outer_loop = father;
319 add_loop_son(father, son);
320 son->depth = father->depth+1;
321 } else { /* The root loop */
322 son->outer_loop = son;
327 son->loop_nr = get_irp_new_node_nr();
336 /* Finishes the datastructures, copies the arrays to the obstack
338 A. Schoesser: Caution: loop -> sons is gone. */
339 static void mature_loop (ir_loop *loop) {
342 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
343 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
344 DEL_ARR_F(loop->sons);
345 loop->sons = new_sons;
349 /* Returns outer loop, itself if outermost. */
350 ir_loop *get_loop_outer_loop (ir_loop *loop) {
351 assert(loop && loop->kind == k_ir_loop);
352 return loop->outer_loop;
355 /* Returns nesting depth of this loop */
356 int get_loop_depth (ir_loop *loop) {
357 assert(loop); assert(loop->kind == k_ir_loop);
361 /* Returns the number of inner loops */
362 int get_loop_n_sons (ir_loop *loop) {
363 assert(loop && loop->kind == k_ir_loop);
364 return(loop -> n_sons);
367 /* Returns the pos`th loop_node-child *
368 * TODO: This method isn`t very efficient ! *
369 * Returns NULL if there isnt`t a pos`th loop_node */
370 ir_loop *get_loop_son (ir_loop *loop, int pos) {
371 int child_nr = 0, loop_nr = -1;
373 assert(loop && loop->kind == k_ir_loop);
374 while(child_nr < ARR_LEN(loop->children))
376 if(*(loop -> children[child_nr].kind) == k_ir_loop)
379 return(loop -> children[child_nr].son);
385 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
389 add_loop_son(ir_loop *loop, ir_loop *son) {
392 assert(loop && loop->kind == k_ir_loop);
393 assert(get_kind(son) == k_ir_loop);
394 ARR_APP1 (loop_element, loop->children, lson);
398 /* Returns the number of nodes in the loop */
399 int get_loop_n_nodes (ir_loop *loop) {
400 assert(loop); assert(loop->kind == k_ir_loop);
401 return loop -> n_nodes;
402 /* return ARR_LEN(loop->nodes); */
405 /* Returns the pos`th ir_node-child *
406 * TODO: This method isn`t very efficient ! *
407 * Returns NULL if there isnt`t a pos`th ir_node */
408 ir_node *get_loop_node (ir_loop *loop, int pos) {
409 int child_nr, node_nr = -1;
411 assert(loop && loop->kind == k_ir_loop);
412 assert(pos < get_loop_n_nodes(loop));
414 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
415 if(*(loop -> children[child_nr].kind) == k_ir_node)
418 return(loop -> children[child_nr].node);
421 printf("pos: %d\n", pos);
422 assert(0 && "no child at pos found");
426 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
430 add_loop_node(ir_loop *loop, ir_node *n) {
433 assert(loop && loop->kind == k_ir_loop);
434 assert(get_kind(n) == k_ir_node);
435 ARR_APP1 (loop_element, loop->children, ln);
439 /** Returns the number of elements contained in loop. */
440 int get_loop_n_elements (ir_loop *loop) {
441 assert(loop && loop->kind == k_ir_loop);
442 return(ARR_LEN(loop->children));
446 Returns the pos`th loop element.
447 This may be a loop_node or a ir_node. The caller of this function has
448 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
449 and then select the apropriate "loop_element.node" or "loop_element.son".
452 loop_element get_loop_element (ir_loop *loop, int pos) {
453 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
455 return(loop -> children[pos]);
458 int get_loop_element_pos(ir_loop *loop, void *le) {
460 assert(loop && loop->kind == k_ir_loop);
462 for (i = 0; i < get_loop_n_elements(loop); i++)
463 if (get_loop_element(loop, i).node == le) return i;
467 int get_loop_loop_nr(ir_loop *loop) {
468 assert(loop && loop->kind == k_ir_loop);
470 return loop->loop_nr;
477 /** A field to connect additional information to a loop. Only valid
478 if libfirm_debug is set. */
479 void set_loop_link (ir_loop *loop, void *link) {
480 assert(loop && loop->kind == k_ir_loop);
485 void *get_loop_link (const ir_loop *loop) {
486 assert(loop && loop->kind == k_ir_loop);
494 /* The outermost loop is remarked in the surrounding graph. */
495 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
499 ir_loop *get_irg_loop(ir_graph *irg) {
505 /**********************************************************************/
506 /* Constructing and destructing the loop/backedge information. **/
507 /**********************************************************************/
509 /* Initialization steps. **********************************************/
512 init_node (ir_node *n, void *env) {
513 set_irn_link (n, new_scc_info());
516 /* Also init nodes not visible in intraproc_view. */
517 /* @@@ init_node is called for too many nodes -- this wastes memory!.
518 The mem is not lost as its on the obstack. */
519 if (intern_get_irn_op(n) == op_Filter) {
520 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
521 init_node(get_Filter_cg_pred(n, i), NULL);
523 if (intern_get_irn_op(n) == op_Block) {
524 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
525 init_node(get_Block_cg_cfgpred(n, i), NULL);
528 /* The following pattern matches only after a call from above pattern. */
529 if ((intern_get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
530 /* @@@ init_node is called for every proj -- this wastes memory!.
531 The mem is not lost as its on the obstack. */
532 ir_node *cb = get_Proj_pred(n);
533 if ((intern_get_irn_op(cb) == op_CallBegin) ||
534 (intern_get_irn_op(cb) == op_EndReg) ||
535 (intern_get_irn_op(cb) == op_EndExcept)) {
537 init_node(get_nodes_Block(cb), NULL);
544 init_scc_common (void) {
547 if (!node_loop_map) node_loop_map = pmap_create();
552 init_scc (ir_graph *irg) {
554 irg_walk_graph (irg, init_node, NULL, NULL);
556 irg_walk (irg, link_to_reg_end, NULL, NULL);
563 cg_walk (init_node, NULL, NULL);
566 /* Condition for breaking the recursion. */
567 static bool is_outermost_Start(ir_node *n) {
568 /* Test whether this is the outermost Start node. If so
569 recursion must end. */
570 if ((intern_get_irn_op(n) == op_Block) &&
571 (get_Block_n_cfgpreds(n) == 1) &&
572 (intern_get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
573 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
577 /* @@@ Bad condition:
578 not possible in interprocedural view as outermost_graph is
579 not necessarily the only with a dead-end start block.
580 Besides current_ir_graph is not set properly. */
581 if ((intern_get_irn_op(n) == op_Block) &&
582 (n == get_irg_start_block(current_ir_graph))) {
583 if ((!interprocedural_view) ||
584 (current_ir_graph == outermost_ir_graph))
591 /* Don't walk from nodes to blocks except for Control flow operations. */
593 get_start_index(ir_node *n) {
594 if (is_cfop(n) || is_fragile_op(n) || intern_get_irn_op(n) == op_Start)
600 /* Returns current_ir_graph and set it to the irg of predecessor index
602 static INLINE ir_graph *
603 switch_irg (ir_node *n, int index) {
604 ir_graph *old_current = current_ir_graph;
606 if (interprocedural_view) {
607 /* Only Filter and Block nodes can have predecessors in other graphs. */
608 if (intern_get_irn_op(n) == op_Filter)
609 n = get_nodes_Block(n);
610 if (intern_get_irn_op(n) == op_Block) {
611 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
612 if (is_ip_cfop(cfop)) {
613 current_ir_graph = get_irn_irg(cfop);
614 set_irg_visited(current_ir_graph, get_max_irg_visited());
622 /* Walks up the stack passing n and then finding the node
623 where we walked into the irg n is contained in.
624 Here we switch the irg. */
626 find_irg_on_stack (ir_node *n) {
628 ir_graph *old_current = current_ir_graph;
631 if (interprocedural_view) {
632 for (i = tos; i >= 0; i--) {
633 if (stack[i] == n) break;
638 for (; i >= 0; i--) {
640 /*printf(" Visiting %d ", i); DDMN(m);*/
642 current_ir_graph = get_irn_irg(m);
645 if (intern_get_irn_op(m) == op_Filter) {
646 /* Find the corresponding ip_cfop */
647 ir_node *pred = stack[i+1];
649 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
650 if (get_Filter_cg_pred(m, j) == pred) break;
651 if (j >= get_Filter_n_cg_preds(m))
652 /* It is a filter we didn't pass as the predecessors are marked. */
654 assert(get_Filter_cg_pred(m, j) == pred);
666 static void test(ir_node *pred, ir_node *root, ir_node *this) {
668 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
670 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
671 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
672 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
674 printf("tos: %d\n", tos);
676 for (i = tos; i >= 0; i--) {
677 ir_node *n = stack[i];
679 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
684 /* Test for legal loop header: Block, Phi, ... */
685 INLINE static bool is_possible_loop_head(ir_node *n) {
686 ir_op *op = intern_get_irn_op(n);
687 return ((op == op_Block) ||
689 ((op == op_Filter) && interprocedural_view));
692 /* Returns true if n is a loop header, i.e., it is a Block, Phi
693 or Filter node and has predecessors within the loop and out
695 @arg root: only needed for assertion. */
697 is_head (ir_node *n, ir_node *root)
700 int some_outof_loop = 0, some_in_loop = 0;
702 /* Test for legal loop header: Block, Phi, ... */
703 if (!is_possible_loop_head(n))
706 if (!is_outermost_Start(n)) {
707 arity = intern_get_irn_arity(n);
708 for (i = get_start_index(n); i < arity; i++) {
709 ir_node *pred = intern_get_irn_n(n, i);
711 if (is_backedge(n, i)) continue;
712 if (!irn_is_in_stack(pred)) {
715 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
720 return some_outof_loop && some_in_loop;
723 /* Returns index of the predecessor with the smallest dfn number
724 greater-equal than limit. */
726 smallest_dfn_pred (ir_node *n, int limit)
728 int i, index = -2, min = -1;
730 if (!is_outermost_Start(n)) {
731 int arity = intern_get_irn_arity(n);
732 for (i = get_start_index(n); i < arity; i++) {
733 ir_node *pred = intern_get_irn_n(n, i);
735 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
736 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
738 min = get_irn_dfn(pred);
745 /* Returns index of the predecessor with the largest dfn number. */
747 largest_dfn_pred (ir_node *n)
749 int i, index = -2, max = -1;
751 if (!is_outermost_Start(n)) {
752 int arity = intern_get_irn_arity(n);
753 for (i = get_start_index(n); i < arity; i++) {
754 ir_node *pred = intern_get_irn_n(n, i);
755 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
756 if (get_irn_dfn(pred) > max) {
758 max = get_irn_dfn(pred);
765 /* Searches the stack for possible loop heads. Tests these for backedges.
766 If it finds a head with an unmarked backedge it marks this edge and
767 returns the tail of the loop.
768 If it finds no backedge returns NULL.
769 ("disable_backedge" in fiasco) */
772 find_tail (ir_node *n) {
774 int i, res_index = -2;
777 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
780 m = stack[tos-1]; /* tos = top of stack */
781 if (is_head (m, n)) {
782 res_index = smallest_dfn_pred(m, 0);
783 if ((res_index == -2) && /* no smallest dfn pred found. */
787 if (m == n) return NULL;
788 for (i = tos-2; ; --i) {
790 if (is_head (m, n)) {
791 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
792 if (res_index == -2) /* no smallest dfn pred found. */
793 res_index = largest_dfn_pred (m);
798 assert (res_index > -2);
800 set_backedge (m, res_index);
801 return is_outermost_Start(n) ? NULL : intern_get_irn_n(m, res_index);
805 /* The core algorithm. *****************************************/
807 static void scc (ir_node *n) {
809 if (irn_visited(n)) return;
812 /* Initialize the node */
813 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
814 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
815 set_irn_loop(n, NULL);
819 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
820 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
821 so is_backedge does not access array[-1] but correctly returns false! */
823 if (!is_outermost_Start(n)) {
824 int arity = intern_get_irn_arity(n);
825 for (i = get_start_index(n); i < arity; i++) {
827 if (is_backedge(n, i)) continue;
829 m = intern_get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
830 /* if ((!m) || (intern_get_irn_op(m) == op_Unknown)) continue; */
832 if (irn_is_in_stack(m)) {
833 /* Uplink of m is smaller if n->m is a backedge.
834 Propagate the uplink to mark the loop. */
835 if (get_irn_uplink(m) < get_irn_uplink(n))
836 set_irn_uplink(n, get_irn_uplink(m));
841 if (get_irn_dfn(n) == get_irn_uplink(n)) {
842 /* This condition holds for the node with the incoming backedge.
843 AS: That is: For the loop head. */
844 ir_node *tail = find_tail(n);
846 /* We found a new inner loop! */
848 /* This is an adaption of the algorithm from fiasco / optscc to
849 * avoid loops without Block or Phi as first node. This should
850 * severely reduce the number of evaluations of nodes to detect
851 * a fixpoint in the heap analyses.
852 * Further it avoids loops without firm nodes that cause errors
853 * in the heap analyses. */
854 #define NO_LOOPS_WITHOUT_HEAD 1
855 #if NO_LOOPS_WITHOUT_HEAD
858 if (get_loop_n_elements(current_loop) > 0) {
866 ir_loop *l = new_loop();
869 /* Remove the loop from the stack ... */
870 pop_scc_unmark_visit (n);
871 /* and recompute it in a better order; and so that it goes into
873 /* GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
876 /* GL @@@ remove experimental stuff current_ir_graph = rem; */
878 assert (irn_visited(n));
879 #if NO_LOOPS_WITHOUT_HEAD
884 /* AS: No inner loop was found. Pop all nodes from the stack
885 to the current loop. */
891 /* Constructs backedge information for irg. In interprocedural view constructs
892 backedges for all methods called by irg, too. */
893 void construct_backedges(ir_graph *irg) {
894 ir_graph *rem = current_ir_graph;
897 assert(!interprocedural_view &&
898 "not implemented, use construct_ip_backedges");
900 current_ir_graph = irg;
901 outermost_ir_graph = irg;
903 init_scc(current_ir_graph);
906 new_loop(); /* sets current_loop */
907 head_rem = current_loop; /* Just for assertion */
909 if (interprocedural_view) {
910 set_irg_visited(current_ir_graph, inc_max_irg_visited());
913 inc_irg_visited(current_ir_graph);
916 scc(get_irg_end(current_ir_graph));
918 if (interprocedural_view) finish_ip_walk();
920 assert(head_rem == current_loop);
921 set_irg_loop(current_ir_graph, current_loop);
922 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
923 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
925 irg->loops = current_loop;
929 count_loop (the_loop, &count, &depth);
933 current_ir_graph = rem;
938 void construct_ip_backedges (void) {
939 ir_graph *rem = current_ir_graph;
940 int rem_ipv = interprocedural_view;
943 outermost_ir_graph = get_irp_main_irg();
948 new_loop(); /* sets current_loop */
949 interprocedural_view = 1;
951 inc_max_irg_visited();
952 for (i = 0; i < get_irp_n_irgs(); i++)
953 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
955 for (i = 0; i < get_irp_n_irgs(); i++) {
957 current_ir_graph = get_irp_irg(i);
958 /* Find real entry points */
959 sb = get_irg_start_block(current_ir_graph);
960 if ((get_Block_n_cfgpreds(sb) > 1) ||
961 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
962 /* Compute scc for this graph */
963 outermost_ir_graph = current_ir_graph;
964 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
965 scc(get_irg_end(current_ir_graph));
966 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
967 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
970 set_irg_loop(outermost_ir_graph, current_loop);
971 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
972 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
974 current_ir_graph = rem;
975 interprocedural_view = rem_ipv;
978 void construct_ip_backedges (void) {
979 ir_graph *rem = current_ir_graph;
980 int rem_ipv = interprocedural_view;
983 outermost_ir_graph = get_irp_main_irg();
988 new_loop(); /* sets current_loop */
989 interprocedural_view = 1;
991 inc_max_irg_visited();
992 for (i = 0; i < get_irp_n_irgs(); i++)
993 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
995 /** We have to start the walk at the same nodes as cg_walk. **/
996 /* Walk starting at unreachable procedures. Only these
997 * have End blocks visible in interprocedural view. */
998 for (i = 0; i < get_irp_n_irgs(); i++) {
1000 current_ir_graph = get_irp_irg(i);
1002 sb = get_irg_start_block(current_ir_graph);
1004 if ((get_Block_n_cfgpreds(sb) > 1) ||
1005 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1007 scc(get_irg_end(current_ir_graph));
1010 /* Check whether we walked all procedures: there could be procedures
1011 with cyclic calls but no call from the outside. */
1012 for (i = 0; i < get_irp_n_irgs(); i++) {
1014 current_ir_graph = get_irp_irg(i);
1016 /* Test start block: if inner procedure end and end block are not
1017 * visible and therefore not marked. */
1018 sb = get_irg_start_block(current_ir_graph);
1019 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1022 /* Walk all endless loops in inner procedures.
1023 * We recognize an inner procedure if the End node is not visited. */
1024 for (i = 0; i < get_irp_n_irgs(); i++) {
1026 current_ir_graph = get_irp_irg(i);
1028 e = get_irg_end(current_ir_graph);
1029 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1031 /* Don't visit the End node. */
1032 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1036 set_irg_loop(outermost_ir_graph, current_loop);
1037 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1038 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1040 current_ir_graph = rem;
1041 interprocedural_view = rem_ipv;
1045 static void reset_backedges(ir_node *n) {
1046 if (is_possible_loop_head(n)) {
1047 int rem = interprocedural_view;
1048 interprocedural_view = 1;
1050 interprocedural_view = 0;
1052 interprocedural_view = rem;
1056 static void loop_reset_backedges(ir_loop *l) {
1058 reset_backedges(get_loop_node(l, 0));
1059 for (i = 0; i < get_loop_n_nodes(l); ++i)
1060 set_irn_loop(get_loop_node(l, i), NULL);
1061 for (i = 0; i < get_loop_n_sons(l); ++i) {
1062 loop_reset_backedges(get_loop_son(l, i));
1066 /** Removes all loop information.
1067 Resets all backedges */
1068 void free_loop_information(ir_graph *irg) {
1069 if (get_irg_loop(irg))
1070 loop_reset_backedges(get_irg_loop(irg));
1071 set_irg_loop(irg, NULL);
1072 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1073 /* We cannot free the loop nodes, they are on the obstack. */
1077 void free_all_loop_information (void) {
1079 int rem = interprocedural_view;
1080 interprocedural_view = 1; /* To visit all filter nodes */
1081 for (i = 0; i < get_irp_n_irgs(); i++) {
1082 free_loop_information(get_irp_irg(i));
1084 pmap_destroy(node_loop_map);
1085 node_loop_map = NULL;
1086 interprocedural_view = rem;
1093 /* Debug stuff *************************************************/
1095 static int test_loop_node(ir_loop *l) {
1096 int i, has_node = 0, found_problem = 0;
1099 assert(l && l->kind == k_ir_loop);
1101 if (get_loop_n_elements(l) == 0) {
1102 printf(" Loop completely empty! "); DDML(l);
1104 dump_loop(l, "-ha");
1107 le = get_loop_element(l, 0);
1108 if (*(le.kind) != k_ir_node) {
1109 assert(le.kind && *(le.kind) == k_ir_loop);
1110 printf(" First loop element is not a node! "); DDML(l);
1111 printf(" "); DDML(le.son);
1114 dump_loop(l, "-ha");
1117 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1118 printf(" Wrong node as head! "); DDML(l);
1119 printf(" "); DDMN(le.node);
1121 dump_loop(l, "-ha");
1124 if ((get_loop_depth(l) != 0) &&
1125 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1126 printf(" Loop head has no backedges! "); DDML(l);
1127 printf(" "); DDMN(le.node);
1129 dump_loop(l, "-ha");
1134 for (i = 0; i < get_loop_n_elements(l); ++i) {
1135 le = get_loop_element(l, i);
1136 if (*(le.kind) == k_ir_node)
1139 if (test_loop_node(le.son)) found_problem = 1;
1142 if (has_node == 0) {
1143 printf(" Loop has no firm node! "); DDML(l);
1145 dump_loop(l, "-ha");
1148 if (get_loop_loop_nr(l) == 11819)
1149 dump_loop(l, "-ha-debug");
1151 return found_problem;
1154 /** Prints all loop nodes that
1155 * - do not have any firm nodes, only loop sons
1156 * - the header is not a Phi, Block or Filter.
1158 void find_strange_loop_nodes(ir_loop *l) {
1159 int found_problem = 0;
1160 printf("\nTesting loop "); DDML(l);
1161 found_problem = test_loop_node(l);
1162 printf("Finished Test\n\n");
1163 if (found_problem) exit(0);