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.
25 #include "irgraph_t.h"
33 /* A variant of the loop tree that avoids loops without head.
34 This reduces the depth of the loop tree. */
35 #define NO_LOOPS_WITHOUT_HEAD 1
38 INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
40 INLINE void add_loop_node(ir_loop *loop, ir_node *n);
42 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
44 static ir_loop *current_loop; /* Current loop construction is working
46 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
47 Each loop node gets a unique number.
48 What for? ev. remove. @@@ */
49 static int current_dfn = 1; /* Counter to generate depth first numbering
52 static int max_loop_depth = 0;
54 void link_to_reg_end (ir_node *n, void *env);
55 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
56 ir_node *get_projx_link(ir_node *cb_projx);
58 /**********************************************************************/
59 /* Node attributes **/
60 /**********************************************************************/
62 /**********************************************************************/
63 /* Node attributes needed for the construction. **/
64 /**********************************************************************/
66 typedef struct scc_info {
67 bool in_stack; /* Marks whether node is on the stack. */
68 int dfn; /* Depth first search number. */
69 int uplink; /* dfn number of ancestor. */
70 /* ir_loop *loop; *//* Refers to the containing loop. */
72 struct section *section;
78 static INLINE scc_info* new_scc_info(void) {
79 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
80 memset (info, 0, sizeof (scc_info));
85 mark_irn_in_stack (ir_node *n) {
86 assert(get_irn_link(n));
88 /* ((scc_info *)get_irn_link(n))->in_stack = true; */
89 ((scc_info *)n->link)->in_stack = true;
93 mark_irn_not_in_stack (ir_node *n) {
94 assert(get_irn_link(n));
96 /* ((scc_info *)get_irn_link(n))->in_stack = false; */
97 ((scc_info *)n->link)->in_stack = false;
101 irn_is_in_stack (ir_node *n) {
102 assert(get_irn_link(n));
104 /* return ((scc_info *)get_irn_link(n))->in_stack; */
105 return ((scc_info *)n->link)->in_stack;
109 set_irn_uplink (ir_node *n, int uplink) {
110 assert(get_irn_link(n));
112 /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
113 ((scc_info *)n->link)->uplink = uplink;
117 get_irn_uplink (ir_node *n) {
118 assert(get_irn_link(n));
119 /* from fast to slow */
120 /* return ((scc_info *)get_irn_link(n))->uplink; */
121 return ((scc_info *)n->link)->uplink;
125 set_irn_dfn (ir_node *n, int dfn) {
126 assert(get_irn_link(n));
128 /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
129 ((scc_info *)n->link)->dfn = dfn;
133 get_irn_dfn (ir_node *n) {
134 assert(get_irn_link(n));
136 /* return ((scc_info *)get_irn_link(n))->dfn; */
137 return ((scc_info *)n->link)->dfn;
142 set_irn_loop (ir_node *n, ir_loop* loop) {
146 /* Uses temporary information to get the loop */
148 get_irn_loop (ir_node *n) {
154 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
158 /* Test whether n is contained in this loop. */
159 for (i = 0; i < get_loop_n_nodes(l); i++)
160 if (n == get_loop_node(l, i)) return l;
162 /* Is this a leave in the loop tree? If so loop not found. */
163 if (get_loop_n_sons(l) == 0) return NULL;
165 /* Else descend in the loop tree. */
166 for (i = 0; i < get_loop_n_sons(l); i++) {
167 res = find_nodes_loop(n, get_loop_son(l, i));
173 /* @@@ temporary implementation, costly!!! */
174 ir_loop * get_irn_loop(ir_node *n) {
175 ir_loop *l = get_irg_loop(current_ir_graph);
176 l = find_nodes_loop(n, l);
181 /**********************************************************************/
183 /**********************************************************************/
185 static ir_node **stack = NULL;
186 static int tos = 0; /* top of stack */
188 static INLINE void init_stack(void) {
190 ARR_RESIZE (ir_node *, stack, 1000);
192 stack = NEW_ARR_F (ir_node *, 1000);
198 static INLINE void free_stack(void) {
210 if (tos == ARR_LEN (stack)) {
211 int nlen = ARR_LEN (stack) * 2;
212 ARR_RESIZE (ir_node *, stack, nlen);
215 mark_irn_in_stack(n);
218 static INLINE ir_node *
221 ir_node *n = stack[--tos];
222 mark_irn_not_in_stack(n);
226 /* The nodes up to n belong to the current loop.
227 Removes them from the stack and adds them to the current loop. */
229 pop_scc_to_loop (ir_node *n)
237 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
240 set_irn_dfn(m, loop_node_cnt);
241 add_loop_node(current_loop, m);
242 set_irn_loop(m, current_loop);
244 /* if (m==n) break;*/
247 /* i might be bigger than 1 for dead (and that's why bad) loops */
249 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
253 /* GL ??? my last son is my grandson??? Removes loops with no
254 ir_nodes in them. Such loops have only another loop as son. (Why
255 can't they have two loops as sons? Does it never get that far? ) */
256 static void close_loop (ir_loop *l)
258 int last = get_loop_n_elements(l) - 1;
259 loop_element lelement = get_loop_element(l, last);
260 ir_loop *last_son = lelement.son;
262 if (get_kind(last_son) == k_ir_loop &&
263 get_loop_n_elements(last_son) == 1)
267 lelement = get_loop_element(last_son, 0);
269 if(get_kind(gson) == k_ir_loop)
271 loop_element new_last_son;
273 gson -> outer_loop = l;
274 new_last_son.son = gson;
275 l -> children[last] = new_last_son;
282 /* Removes and unmarks all nodes up to n from the stack.
283 The nodes must be visited once more to assign them to a scc. */
285 pop_scc_unmark_visit (ir_node *n)
291 set_irn_visited(m, 0);
295 /**********************************************************************/
296 /* The loop datastructure. **/
297 /**********************************************************************/
299 /* Allocates a new loop as son of current_loop. Sets current_loop
300 to the new loop and returns the father. */
301 ir_loop *new_loop (void) {
302 ir_loop *father, *son;
304 father = current_loop;
306 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
307 memset (son, 0, sizeof (ir_loop));
308 son->kind = k_ir_loop;
309 son->children = NEW_ARR_F (loop_element, 0);
313 son->outer_loop = father;
314 add_loop_son(father, son);
315 son->depth = father->depth+1;
316 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
317 } else { /* The root loop */
318 son->outer_loop = son;
323 son->loop_nr = get_irp_new_node_nr();
332 /* Finishes the datastructures, copies the arrays to the obstack
334 A. Schoesser: Caution: loop -> sons is gone. */
335 static void mature_loop (ir_loop *loop) {
338 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
339 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
340 DEL_ARR_F(loop->sons);
341 loop->sons = new_sons;
345 /* Returns outer loop, itself if outermost. */
346 ir_loop *get_loop_outer_loop (ir_loop *loop) {
347 assert(loop && loop->kind == k_ir_loop);
348 return loop->outer_loop;
351 /* Returns nesting depth of this loop */
352 int get_loop_depth (ir_loop *loop) {
353 assert(loop); assert(loop->kind == k_ir_loop);
357 /* Returns the number of inner loops */
358 int get_loop_n_sons (ir_loop *loop) {
359 assert(loop && loop->kind == k_ir_loop);
360 return(loop -> n_sons);
363 /* Returns the pos`th loop_node-child *
364 * TODO: This method isn`t very efficient ! *
365 * Returns NULL if there isnt`t a pos`th loop_node */
366 ir_loop *get_loop_son (ir_loop *loop, int pos) {
367 int child_nr = 0, loop_nr = -1;
369 assert(loop && loop->kind == k_ir_loop);
370 while(child_nr < ARR_LEN(loop->children))
372 if(*(loop -> children[child_nr].kind) == k_ir_loop)
375 return(loop -> children[child_nr].son);
381 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
385 add_loop_son(ir_loop *loop, ir_loop *son) {
388 assert(loop && loop->kind == k_ir_loop);
389 assert(get_kind(son) == k_ir_loop);
390 ARR_APP1 (loop_element, loop->children, lson);
394 /* Returns the number of nodes in the loop */
395 int get_loop_n_nodes (ir_loop *loop) {
396 assert(loop); assert(loop->kind == k_ir_loop);
397 return loop -> n_nodes;
398 /* return ARR_LEN(loop->nodes); */
401 /* Returns the pos`th ir_node-child *
402 * TODO: This method isn`t very efficient ! *
403 * Returns NULL if there isnt`t a pos`th ir_node */
404 ir_node *get_loop_node (ir_loop *loop, int pos) {
405 int child_nr, node_nr = -1;
407 assert(loop && loop->kind == k_ir_loop);
408 assert(pos < get_loop_n_nodes(loop));
410 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
411 if(*(loop -> children[child_nr].kind) == k_ir_node)
414 return(loop -> children[child_nr].node);
417 printf("pos: %d\n", pos);
418 assert(0 && "no child at pos found");
422 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
426 add_loop_node(ir_loop *loop, ir_node *n) {
429 assert(loop && loop->kind == k_ir_loop);
430 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
431 ARR_APP1 (loop_element, loop->children, ln);
435 /** Returns the number of elements contained in loop. */
436 int get_loop_n_elements (ir_loop *loop) {
437 assert(loop && loop->kind == k_ir_loop);
438 return(ARR_LEN(loop->children));
442 Returns the pos`th loop element.
443 This may be a loop_node or a ir_node. The caller of this function has
444 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
445 and then select the apropriate "loop_element.node" or "loop_element.son".
448 loop_element get_loop_element (ir_loop *loop, int pos) {
449 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
451 return(loop -> children[pos]);
454 int get_loop_element_pos(ir_loop *loop, void *le) {
456 assert(loop && loop->kind == k_ir_loop);
458 for (i = 0; i < get_loop_n_elements(loop); i++)
459 if (get_loop_element(loop, i).node == le) return i;
463 int get_loop_loop_nr(ir_loop *loop) {
464 assert(loop && loop->kind == k_ir_loop);
466 return loop->loop_nr;
473 /** A field to connect additional information to a loop. Only valid
474 if libfirm_debug is set. */
475 void set_loop_link (ir_loop *loop, void *link) {
476 assert(loop && loop->kind == k_ir_loop);
481 void *get_loop_link (const ir_loop *loop) {
482 assert(loop && loop->kind == k_ir_loop);
490 /* The outermost loop is remarked in the surrounding graph. */
491 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
495 ir_loop *get_irg_loop(ir_graph *irg) {
501 /**********************************************************************/
502 /* Constructing and destructing the loop/backedge information. **/
503 /**********************************************************************/
505 /* Initialization steps. **********************************************/
508 init_node (ir_node *n, void *env) {
509 set_irn_link (n, new_scc_info());
512 /* Also init nodes not visible in intraproc_view. */
513 /* @@@ init_node is called for too many nodes -- this wastes memory!.
514 The mem is not lost as its on the obstack. */
515 if (get_irn_op(n) == op_Filter) {
516 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
517 init_node(get_Filter_cg_pred(n, i), NULL);
519 if (get_irn_op(n) == op_Block) {
520 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
521 init_node(get_Block_cg_cfgpred(n, i), NULL);
524 /* The following pattern matches only after a call from above pattern. */
525 if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
526 /* @@@ init_node is called for every proj -- this wastes memory!.
527 The mem is not lost as its on the obstack. */
528 ir_node *cb = get_Proj_pred(n);
529 if ((get_irn_op(cb) == op_CallBegin) ||
530 (get_irn_op(cb) == op_EndReg) ||
531 (get_irn_op(cb) == op_EndExcept)) {
533 init_node(get_nodes_block(cb), NULL);
540 init_scc_common (void) {
547 init_scc (ir_graph *irg) {
549 irg_walk_graph (irg, init_node, NULL, NULL);
551 irg_walk (irg, link_to_reg_end, NULL, NULL);
558 cg_walk (init_node, NULL, NULL);
560 #if EXPERIMENTAL_LOOP_TREE
561 cg_walk (link_to_reg_end, NULL, NULL);
565 /* Condition for breaking the recursion. */
566 static bool is_outermost_Start(ir_node *n) {
567 /* Test whether this is the outermost Start node. If so
568 recursion must end. */
569 if ((get_irn_op(n) == op_Block) &&
570 (get_Block_n_cfgpreds(n) == 1) &&
571 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
572 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
576 /* @@@ Bad condition:
577 not possible in interprocedural view as outermost_graph is
578 not necessarily the only with a dead-end start block.
579 Besides current_ir_graph is not set properly. */
580 if ((get_irn_op(n) == op_Block) &&
581 (n == get_irg_start_block(current_ir_graph))) {
582 if ((!interprocedural_view) ||
583 (current_ir_graph == outermost_ir_graph))
590 /* When to walk from nodes to blocks. Only for Control flow operations? */
592 get_start_index(ir_node *n) {
593 #undef BLOCK_BEFORE_NODE
594 #define BLOCK_BEFORE_NODE 1
596 #if BLOCK_BEFORE_NODE
598 /* This version assures, that all nodes are ordered absolutely. This allows
599 to undef all nodes in the heap analysis if the block is false, which means
601 I.e., with this code, the order on the loop tree is correct. But a (single)
602 test showed the loop tree is deeper. */
603 if (get_irn_op(n) == op_Phi ||
604 get_irn_op(n) == op_Block ||
605 (get_irn_op(n) == op_Filter && interprocedural_view) ||
606 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
607 get_irn_pinned(n) == op_pin_state_floats))
608 // Here we could test for backedge at -1 which is illegal
615 /* This version causes deeper loop trees (at least we verified this
617 But it guarantees that Blocks are analysed before nodes contained in the
618 block. If so, we can set the value to undef if the block is not \
620 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
630 static void test(ir_node *pred, ir_node *root, ir_node *this) {
632 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
634 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
635 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
636 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
638 printf("tos: %d\n", tos);
640 for (i = tos; i >= 0; i--) {
641 ir_node *n = stack[i];
643 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
648 /* Test for legal loop header: Block, Phi, ... */
649 INLINE static bool is_possible_loop_head(ir_node *n) {
650 ir_op *op = get_irn_op(n);
651 return ((op == op_Block) ||
653 ((op == op_Filter) && interprocedural_view));
656 /* Returns true if n is a loop header, i.e., it is a Block, Phi
657 or Filter node and has predecessors within the loop and out
659 @arg root: only needed for assertion. */
661 is_head (ir_node *n, ir_node *root)
664 int some_outof_loop = 0, some_in_loop = 0;
666 /* Test for legal loop header: Block, Phi, ... */
667 if (!is_possible_loop_head(n))
670 if (!is_outermost_Start(n)) {
671 arity = get_irn_arity(n);
672 for (i = get_start_index(n); i < arity; i++) {
673 ir_node *pred = get_irn_n(n, i);
675 if (is_backedge(n, i)) continue;
676 if (!irn_is_in_stack(pred)) {
679 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
680 DDMN(n); DDMN(pred); DDMN(root);
681 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
687 return some_outof_loop && some_in_loop;
690 /* Returns true if n is possible loop head of an endless loop.
691 I.e., it is a Block, Phi or Filter node and has only predecessors
693 @arg root: only needed for assertion. */
695 is_endless_head (ir_node *n, ir_node *root)
698 int some_outof_loop = 0, some_in_loop = 0;
700 /* Test for legal loop header: Block, Phi, ... */
701 if (!is_possible_loop_head(n))
704 if (!is_outermost_Start(n)) {
705 arity = get_irn_arity(n);
706 for (i = get_start_index(n); i < arity; i++) {
707 ir_node *pred = get_irn_n(n, i);
709 if (is_backedge(n, i)) { continue; }
710 if (!irn_is_in_stack(pred)) {
711 some_outof_loop = 1; //printf(" some out of loop ");
713 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
714 DDMN(pred); DDMN(root);
715 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
721 return !some_outof_loop && some_in_loop;
724 /* Returns index of the predecessor with the smallest dfn number
725 greater-equal than limit. */
727 smallest_dfn_pred (ir_node *n, int limit)
729 int i, index = -2, min = -1;
731 if (!is_outermost_Start(n)) {
732 int arity = get_irn_arity(n);
733 for (i = get_start_index(n); i < arity; i++) {
734 ir_node *pred = get_irn_n(n, i);
736 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
737 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
739 min = get_irn_dfn(pred);
746 /* Returns index of the predecessor with the largest dfn number. */
748 largest_dfn_pred (ir_node *n)
750 int i, index = -2, max = -1;
752 if (!is_outermost_Start(n)) {
753 int arity = get_irn_arity(n);
754 for (i = get_start_index(n); i < arity; i++) {
755 ir_node *pred = get_irn_n(n, i);
756 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
757 if (get_irn_dfn(pred) > max) {
759 max = get_irn_dfn(pred);
766 /** Searches the stack for possible loop heads. Tests these for backedges.
767 If it finds a head with an unmarked backedge it marks this edge and
768 returns the tail of the loop.
769 If it finds no backedge returns NULL.
770 ("disable_backedge" in fiasco)
772 * @param n A node where uplink == dfn.
776 find_tail (ir_node *n) {
778 int i, res_index = -2;
781 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
783 m = stack[tos-1]; /* tos = top of stack */
784 if (is_head (m, n)) {
785 res_index = smallest_dfn_pred(m, 0);
786 if ((res_index == -2) && /* no smallest dfn pred found. */
790 if (m == n) return NULL; // Is this to catch Phi - self loops?
791 for (i = tos-2; i >= 0; --i) {
794 if (is_head (m, n)) {
795 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
796 if (res_index == -2) /* no smallest dfn pred found. */
797 res_index = largest_dfn_pred (m);
799 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
805 /* We should not walk past our selves on the stack: The upcoming nodes
806 are not in this loop. We assume a loop not reachable from Start. */
815 /* A dead loop not reachable from Start. */
816 for (i = tos-2; i >= 0; --i) {
818 if (is_endless_head (m, n)) {
819 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
820 if (res_index == -2) /* no smallest dfn pred found. */
821 res_index = largest_dfn_pred (m);
824 if (m == n) { break; } /* It's not an unreachable loop, either. */
826 //assert(0 && "no head found on stack");
830 if (res_index <= -2) {
831 /* It's a completely bad loop: without Phi/Block nodes that can
832 be a head. I.e., the code is "dying". We break the loop by
833 setting Bad nodes. */
834 int arity = get_irn_arity(n);
835 for (i = -1; i < arity; ++i) {
836 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
840 assert (res_index > -2);
842 set_backedge (m, res_index);
843 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
847 #if EXPERIMENTAL_LOOP_TREE
849 /* ----------------------------------------------------------------
850 AS: This is experimantal code to build loop trees suitable for
851 the heap analysis. Does not work correctly right now... :-(
854 Search in stack for the corresponding first Call-End-ProjX that
855 corresponds to one of the control flow predecessors of the given
856 block, that is the possible callers.
857 returns: the control predecessor to chose\
858 or -1 if no corresponding Call-End-Node could be found
860 - -------------------------------------------------------------- */
862 int search_endproj_in_stack(ir_node *start_block)
865 assert(is_Block(start_block));
866 for(i = tos - 1; i >= 0; --i)
869 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
870 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
872 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
873 ir_node *end_projx = stack[i];
875 int arity = get_irn_arity(start_block);
876 for(j = 0; j < arity; j++)
878 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
879 get_Proj_proj(end_projx));
881 if(get_irn_n(start_block, j) == begin_projx)
883 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
893 static pmap *projx_link = NULL;
895 void link_to_reg_end (ir_node *n, void *env) {
896 if(get_irn_op(n) == op_Proj &&
897 get_irn_mode(n) == mode_X &&
898 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
899 /* Reg End Projx -> Find the CallBegin Projx and hash it */
900 ir_node *end_projx = n;
901 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
902 get_Proj_proj(end_projx));
903 printf("Linked the following ProjxNodes:\n");
906 set_projx_link(begin_projx, end_projx);
910 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
912 if(projx_link == NULL)
913 projx_link = pmap_create();
914 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
917 ir_node *get_projx_link(ir_node *cb_projx)
919 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
925 is_outermost_loop(ir_loop *l) {
926 return l == get_loop_outer_loop(l);
930 /*-----------------------------------------------------------*
931 * The core algorithm. *
932 *-----------------------------------------------------------*/
935 static void scc (ir_node *n) {
937 if (irn_visited(n)) return;
940 /* Initialize the node */
941 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
942 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
943 set_irn_loop(n, NULL);
947 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
948 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
949 so is_backedge does not access array[-1] but correctly returns false! */
951 if (!is_outermost_Start(n)) {
952 int arity = get_irn_arity(n);
954 for (i = get_start_index(n); i < arity; i++) {
956 if (is_backedge(n, i)) continue;
957 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
958 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
960 if (irn_is_in_stack(m)) {
961 /* Uplink of m is smaller if n->m is a backedge.
962 Propagate the uplink to mark the loop. */
963 if (get_irn_uplink(m) < get_irn_uplink(n))
964 set_irn_uplink(n, get_irn_uplink(m));
969 if (get_irn_dfn(n) == get_irn_uplink(n)) {
970 /* This condition holds for
971 1) the node with the incoming backedge.
972 That is: We found a loop!
973 2) Straight line code, because no uplink has been propagated, so the
974 uplink still is the same as the dfn.
976 But n might not be a proper loop head for the analysis. Proper loop
977 heads are Block and Phi nodes. find_tail searches the stack for
978 Block's and Phi's and takes those nodes as loop heads for the current
979 loop instead and marks the incoming edge as backedge. */
981 ir_node *tail = find_tail(n);
983 /* We have a loop, that is no straight line code,
984 because we found a loop head!
985 Next actions: Open a new loop on the loop tree and
986 try to find inner loops */
988 #if NO_LOOPS_WITHOUT_HEAD
989 /* This is an adaption of the algorithm from fiasco / optscc to
990 * avoid loops without Block or Phi as first node. This should
991 * severely reduce the number of evaluations of nodes to detect
992 * a fixpoint in the heap analysis.
993 * Further it avoids loops without firm nodes that cause errors
994 * in the heap analyses.
995 * But attention: don't do it for the outermost loop: This loop
996 * is not iterated. A first block can be a loop head in case of
997 * an endless recursion. */
1001 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1009 ir_loop *l = new_loop();
1012 /* Remove the loop from the stack ... */
1013 pop_scc_unmark_visit (n);
1015 /* The current backedge has been marked, that is temporarily eliminated,
1016 by find tail. Start the scc algorithm
1017 anew on the subgraph thats left (the current loop without the backedge)
1018 in order to find more inner loops. */
1021 assert (irn_visited(n));
1022 #if NO_LOOPS_WITHOUT_HEAD
1029 /* No loop head was found, that is we have straightline code.
1030 Pop all nodes from the stack to the current loop. */
1036 static void my_scc (ir_node *n) {
1038 if (irn_visited(n)) return;
1039 mark_irn_visited(n);
1041 /* Initialize the node */
1042 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1043 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1044 set_irn_loop(n, NULL);
1048 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1049 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1050 so is_backedge does not access array[-1] but correctly returns false! */
1052 if (!is_outermost_Start(n)) {
1053 int arity = get_irn_arity(n);
1055 for (i = get_start_index(n); i < arity; i++) {
1057 if (is_backedge(n, i)) continue;
1058 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1059 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1061 if (irn_is_in_stack(m)) {
1062 /* Uplink of m is smaller if n->m is a backedge.
1063 Propagate the uplink to mark the loop. */
1064 if (get_irn_uplink(m) < get_irn_uplink(n))
1065 set_irn_uplink(n, get_irn_uplink(m));
1070 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1071 /* This condition holds for
1072 1) the node with the incoming backedge.
1073 That is: We found a loop!
1074 2) Straight line code, because no uplink has been propagated, so the
1075 uplink still is the same as the dfn.
1077 But n might not be a proper loop head for the analysis. Proper loop
1078 heads are Block and Phi nodes. find_tail searches the stack for
1079 Block's and Phi's and takes those nodes as loop heads for the current
1080 loop instead and marks the incoming edge as backedge. */
1082 ir_node *tail = find_tail(n);
1084 /* We have a loop, that is no straight line code,
1085 because we found a loop head!
1086 Next actions: Open a new loop on the loop tree and
1087 try to find inner loops */
1089 #if NO_LOOPS_WITHOUT_HEAD
1090 /* This is an adaption of the algorithm from fiasco / optscc to
1091 * avoid loops without Block or Phi as first node. This should
1092 * severely reduce the number of evaluations of nodes to detect
1093 * a fixpoint in the heap analysis.
1094 * Further it avoids loops without firm nodes that cause errors
1095 * in the heap analyses. */
1099 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1107 ir_loop *l = new_loop();
1110 /* Remove the loop from the stack ... */
1111 pop_scc_unmark_visit (n);
1113 /* The current backedge has been marked, that is temporarily eliminated,
1114 by find tail. Start the scc algorithm
1115 anew on the subgraph thats left (the current loop without the backedge)
1116 in order to find more inner loops. */
1119 assert (irn_visited(n));
1120 #if NO_LOOPS_WITHOUT_HEAD
1127 /* No loop head was found, that is we have straightline code.
1128 Pop all nodes from the stack to the current loop. */
1134 /* Constructs backedge information for irg. In interprocedural view constructs
1135 backedges for all methods called by irg, too. */
1136 int construct_backedges(ir_graph *irg) {
1137 ir_graph *rem = current_ir_graph;
1140 assert(!interprocedural_view &&
1141 "not implemented, use construct_ip_backedges");
1144 current_ir_graph = irg;
1145 outermost_ir_graph = irg;
1147 init_scc(current_ir_graph);
1149 current_loop = NULL;
1150 new_loop(); /* sets current_loop */
1151 head_rem = current_loop; /* Just for assertion */
1153 inc_irg_visited(current_ir_graph);
1155 scc(get_irg_end(current_ir_graph));
1157 assert(head_rem == current_loop);
1158 set_irg_loop(current_ir_graph, current_loop);
1159 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1160 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1162 irg->loops = current_loop;
1166 count_loop (the_loop, &count, &depth);
1170 current_ir_graph = rem;
1172 return max_loop_depth;
1176 int construct_ip_backedges (void) {
1177 ir_graph *rem = current_ir_graph;
1178 int rem_ipv = interprocedural_view;
1182 assert(get_irp_ip_view_state() == ip_view_valid);
1184 outermost_ir_graph = get_irp_main_irg();
1188 current_loop = NULL;
1189 new_loop(); /* sets current_loop */
1190 interprocedural_view = 1;
1192 inc_max_irg_visited();
1193 for (i = 0; i < get_irp_n_irgs(); i++)
1194 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1196 /** We have to start the walk at the same nodes as cg_walk. **/
1197 /* Walk starting at unreachable procedures. Only these
1198 * have End blocks visible in interprocedural view. */
1199 for (i = 0; i < get_irp_n_irgs(); i++) {
1201 current_ir_graph = get_irp_irg(i);
1203 sb = get_irg_start_block(current_ir_graph);
1205 if ((get_Block_n_cfgpreds(sb) > 1) ||
1206 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1208 scc(get_irg_end(current_ir_graph));
1211 /* Check whether we walked all procedures: there could be procedures
1212 with cyclic calls but no call from the outside. */
1213 for (i = 0; i < get_irp_n_irgs(); i++) {
1215 current_ir_graph = get_irp_irg(i);
1217 /* Test start block: if inner procedure end and end block are not
1218 * visible and therefore not marked. */
1219 sb = get_irg_start_block(current_ir_graph);
1220 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1223 /* Walk all endless loops in inner procedures.
1224 * We recognize an inner procedure if the End node is not visited. */
1225 for (i = 0; i < get_irp_n_irgs(); i++) {
1227 current_ir_graph = get_irp_irg(i);
1229 e = get_irg_end(current_ir_graph);
1230 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1232 /* Don't visit the End node. */
1233 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1237 set_irg_loop(outermost_ir_graph, current_loop);
1238 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1239 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1241 current_ir_graph = rem;
1242 interprocedural_view = rem_ipv;
1243 return max_loop_depth;
1246 void my_construct_ip_backedges (void) {
1247 ir_graph *rem = current_ir_graph;
1248 int rem_ipv = interprocedural_view;
1251 assert(get_irp_ip_view_state() == ip_view_valid);
1253 outermost_ir_graph = get_irp_main_irg();
1257 current_loop = NULL;
1258 new_loop(); /* sets current_loop */
1259 interprocedural_view = 1;
1261 inc_max_irg_visited();
1262 for (i = 0; i < get_irp_n_irgs(); i++)
1263 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1265 /** We have to start the walk at the same nodes as cg_walk. **/
1266 /* Walk starting at unreachable procedures. Only these
1267 * have End blocks visible in interprocedural view. */
1268 for (i = 0; i < get_irp_n_irgs(); i++) {
1270 current_ir_graph = get_irp_irg(i);
1272 sb = get_irg_start_block(current_ir_graph);
1274 if ((get_Block_n_cfgpreds(sb) > 1) ||
1275 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1277 my_scc(get_irg_end(current_ir_graph));
1280 /* Check whether we walked all procedures: there could be procedures
1281 with cyclic calls but no call from the outside. */
1282 for (i = 0; i < get_irp_n_irgs(); i++) {
1284 current_ir_graph = get_irp_irg(i);
1286 /* Test start block: if inner procedure end and end block are not
1287 * visible and therefore not marked. */
1288 sb = get_irg_start_block(current_ir_graph);
1289 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1292 /* Walk all endless loops in inner procedures.
1293 * We recognize an inner procedure if the End node is not visited. */
1294 for (i = 0; i < get_irp_n_irgs(); i++) {
1296 current_ir_graph = get_irp_irg(i);
1298 e = get_irg_end(current_ir_graph);
1299 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1301 /* Don't visit the End node. */
1302 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1306 set_irg_loop(outermost_ir_graph, current_loop);
1307 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1308 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1310 current_ir_graph = rem;
1311 interprocedural_view = rem_ipv;
1314 static void reset_backedges(ir_node *n) {
1315 if (is_possible_loop_head(n)) {
1316 int rem = interprocedural_view;
1317 interprocedural_view = 1;
1319 interprocedural_view = 0;
1321 interprocedural_view = rem;
1327 static void loop_reset_backedges(ir_loop *l) {
1329 reset_backedges(get_loop_node(l, 0));
1330 for (i = 0; i < get_loop_n_nodes(l); ++i)
1331 set_irn_loop(get_loop_node(l, i), NULL);
1332 for (i = 0; i < get_loop_n_sons(l); ++i) {
1333 loop_reset_backedges(get_loop_son(l, i));
1338 static void loop_reset_node(ir_node *n, void *env) {
1339 set_irn_loop(n, NULL);
1344 /** Removes all loop information.
1345 Resets all backedges */
1346 void free_loop_information(ir_graph *irg) {
1347 /* We can not use this recursion, as the loop might contain
1348 illegal nodes by now. Why else would we throw away the
1350 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1352 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1353 set_irg_loop(irg, NULL);
1354 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1355 /* We cannot free the loop nodes, they are on the obstack. */
1359 void free_all_loop_information (void) {
1361 int rem = interprocedural_view;
1362 interprocedural_view = 1; /* To visit all filter nodes */
1363 for (i = 0; i < get_irp_n_irgs(); i++) {
1364 free_loop_information(get_irp_irg(i));
1366 interprocedural_view = rem;
1373 /* Debug stuff *************************************************/
1375 static int test_loop_node(ir_loop *l) {
1376 int i, has_node = 0, found_problem = 0;
1379 assert(l && l->kind == k_ir_loop);
1381 if (get_loop_n_elements(l) == 0) {
1382 printf(" Loop completely empty! "); DDML(l);
1384 dump_loop(l, "-ha");
1387 le = get_loop_element(l, 0);
1388 if (*(le.kind) != k_ir_node) {
1389 assert(le.kind && *(le.kind) == k_ir_loop);
1390 printf(" First loop element is not a node! "); DDML(l);
1391 printf(" "); DDML(le.son);
1394 dump_loop(l, "-ha");
1397 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1398 printf(" Wrong node as head! "); DDML(l);
1399 printf(" "); DDMN(le.node);
1401 dump_loop(l, "-ha");
1404 if ((get_loop_depth(l) != 0) &&
1405 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1406 printf(" Loop head has no backedges! "); DDML(l);
1407 printf(" "); DDMN(le.node);
1409 dump_loop(l, "-ha");
1414 for (i = 0; i < get_loop_n_elements(l); ++i) {
1415 le = get_loop_element(l, i);
1416 if (*(le.kind) == k_ir_node)
1419 if (test_loop_node(le.son)) found_problem = 1;
1422 if (has_node == 0) {
1423 printf(" Loop has no firm node! "); DDML(l);
1425 dump_loop(l, "-ha");
1428 if (get_loop_loop_nr(l) == 11819)
1429 dump_loop(l, "-ha-debug");
1431 return found_problem;
1434 /** Prints all loop nodes that
1435 * - do not have any firm nodes, only loop sons
1436 * - the header is not a Phi, Block or Filter.
1438 void find_strange_loop_nodes(ir_loop *l) {
1439 int found_problem = 0;
1440 printf("\nTesting loop "); DDML(l);
1441 found_problem = test_loop_node(l);
1442 printf("Finished Test\n\n");
1443 if (found_problem) exit(0);