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 int is_ir_loop(const void *thing) {
491 return (get_kind(thing) == 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());
518 init_scc_common (void) {
525 init_scc (ir_graph *irg) {
527 irg_walk_graph (irg, init_node, NULL, NULL);
529 irg_walk (irg, link_to_reg_end, NULL, NULL);
536 cg_walk (init_node, NULL, NULL);
538 #if EXPERIMENTAL_LOOP_TREE
539 cg_walk (link_to_reg_end, NULL, NULL);
543 /* Condition for breaking the recursion. */
544 static bool is_outermost_Start(ir_node *n) {
545 /* Test whether this is the outermost Start node. If so
546 recursion must end. */
547 if ((get_irn_op(n) == op_Block) &&
548 (get_Block_n_cfgpreds(n) == 1) &&
549 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
550 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
554 /* @@@ Bad condition:
555 not possible in interprocedural view as outermost_graph is
556 not necessarily the only with a dead-end start block.
557 Besides current_ir_graph is not set properly. */
558 if ((get_irn_op(n) == op_Block) &&
559 (n == get_irg_start_block(current_ir_graph))) {
560 if ((!get_interprocedural_view()) ||
561 (current_ir_graph == outermost_ir_graph))
568 /* When to walk from nodes to blocks. Only for Control flow operations? */
570 get_start_index(ir_node *n) {
571 #undef BLOCK_BEFORE_NODE
572 #define BLOCK_BEFORE_NODE 1
574 #if BLOCK_BEFORE_NODE
576 /* This version assures, that all nodes are ordered absolutely. This allows
577 to undef all nodes in the heap analysis if the block is false, which means
579 I.e., with this code, the order on the loop tree is correct. But a (single)
580 test showed the loop tree is deeper. */
581 if (get_irn_op(n) == op_Phi ||
582 get_irn_op(n) == op_Block ||
583 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
584 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
585 get_irn_pinned(n) == op_pin_state_floats))
586 // Here we could test for backedge at -1 which is illegal
593 /* This version causes deeper loop trees (at least we verified this
595 But it guarantees that Blocks are analysed before nodes contained in the
596 block. If so, we can set the value to undef if the block is not \
598 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
608 static void test(ir_node *pred, ir_node *root, ir_node *this) {
610 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
612 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
613 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
614 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
616 printf("tos: %d\n", tos);
618 for (i = tos; i >= 0; i--) {
619 ir_node *n = stack[i];
621 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
626 /* Test for legal loop header: Block, Phi, ... */
627 INLINE static bool is_possible_loop_head(ir_node *n) {
628 ir_op *op = get_irn_op(n);
629 return ((op == op_Block) ||
631 ((op == op_Filter) && get_interprocedural_view()));
634 /* Returns true if n is a loop header, i.e., it is a Block, Phi
635 or Filter node and has predecessors within the loop and out
637 @arg root: only needed for assertion. */
639 is_head (ir_node *n, ir_node *root)
642 int some_outof_loop = 0, some_in_loop = 0;
644 /* Test for legal loop header: Block, Phi, ... */
645 if (!is_possible_loop_head(n))
648 if (!is_outermost_Start(n)) {
649 arity = get_irn_arity(n);
650 for (i = get_start_index(n); i < arity; i++) {
651 ir_node *pred = get_irn_n(n, i);
653 if (is_backedge(n, i)) continue;
654 if (!irn_is_in_stack(pred)) {
657 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
658 DDMN(n); DDMN(pred); DDMN(root);
659 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
665 return some_outof_loop && some_in_loop;
668 /* Returns true if n is possible loop head of an endless loop.
669 I.e., it is a Block, Phi or Filter node and has only predecessors
671 @arg root: only needed for assertion. */
673 is_endless_head (ir_node *n, ir_node *root)
676 int some_outof_loop = 0, some_in_loop = 0;
678 /* Test for legal loop header: Block, Phi, ... */
679 if (!is_possible_loop_head(n))
682 if (!is_outermost_Start(n)) {
683 arity = get_irn_arity(n);
684 for (i = get_start_index(n); i < arity; i++) {
685 ir_node *pred = get_irn_n(n, i);
687 if (is_backedge(n, i)) { continue; }
688 if (!irn_is_in_stack(pred)) {
689 some_outof_loop = 1; //printf(" some out of loop ");
691 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
692 DDMN(pred); DDMN(root);
693 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
699 return !some_outof_loop && some_in_loop;
702 /* Returns index of the predecessor with the smallest dfn number
703 greater-equal than limit. */
705 smallest_dfn_pred (ir_node *n, int limit)
707 int i, index = -2, min = -1;
709 if (!is_outermost_Start(n)) {
710 int arity = get_irn_arity(n);
711 for (i = get_start_index(n); i < arity; i++) {
712 ir_node *pred = get_irn_n(n, i);
714 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
715 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
717 min = get_irn_dfn(pred);
724 /* Returns index of the predecessor with the largest dfn number. */
726 largest_dfn_pred (ir_node *n)
728 int i, index = -2, max = -1;
730 if (!is_outermost_Start(n)) {
731 int arity = get_irn_arity(n);
732 for (i = get_start_index(n); i < arity; i++) {
733 ir_node *pred = get_irn_n(n, i);
734 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
735 if (get_irn_dfn(pred) > max) {
737 max = get_irn_dfn(pred);
744 /** Searches the stack for possible loop heads. Tests these for backedges.
745 If it finds a head with an unmarked backedge it marks this edge and
746 returns the tail of the loop.
747 If it finds no backedge returns NULL.
748 ("disable_backedge" in fiasco)
750 * @param n A node where uplink == dfn.
754 find_tail (ir_node *n) {
756 int i, res_index = -2;
759 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
761 m = stack[tos-1]; /* tos = top of stack */
762 if (is_head (m, n)) {
763 res_index = smallest_dfn_pred(m, 0);
764 if ((res_index == -2) && /* no smallest dfn pred found. */
768 if (m == n) return NULL; // Is this to catch Phi - self loops?
769 for (i = tos-2; i >= 0; --i) {
772 if (is_head (m, n)) {
773 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
774 if (res_index == -2) /* no smallest dfn pred found. */
775 res_index = largest_dfn_pred (m);
777 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
783 /* We should not walk past our selves on the stack: The upcoming nodes
784 are not in this loop. We assume a loop not reachable from Start. */
793 /* A dead loop not reachable from Start. */
794 for (i = tos-2; i >= 0; --i) {
796 if (is_endless_head (m, n)) {
797 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
798 if (res_index == -2) /* no smallest dfn pred found. */
799 res_index = largest_dfn_pred (m);
802 if (m == n) { break; } /* It's not an unreachable loop, either. */
804 //assert(0 && "no head found on stack");
808 if (res_index <= -2) {
809 /* It's a completely bad loop: without Phi/Block nodes that can
810 be a head. I.e., the code is "dying". We break the loop by
811 setting Bad nodes. */
812 int arity = get_irn_arity(n);
813 for (i = -1; i < arity; ++i) {
814 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
818 assert (res_index > -2);
820 set_backedge (m, res_index);
821 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
825 #if EXPERIMENTAL_LOOP_TREE
827 /* ----------------------------------------------------------------
828 AS: This is experimantal code to build loop trees suitable for
829 the heap analysis. Does not work correctly right now... :-(
832 Search in stack for the corresponding first Call-End-ProjX that
833 corresponds to one of the control flow predecessors of the given
834 block, that is the possible callers.
835 returns: the control predecessor to chose\
836 or -1 if no corresponding Call-End-Node could be found
838 - -------------------------------------------------------------- */
840 int search_endproj_in_stack(ir_node *start_block)
843 assert(is_Block(start_block));
844 for(i = tos - 1; i >= 0; --i)
847 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
848 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
850 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
851 ir_node *end_projx = stack[i];
853 int arity = get_irn_arity(start_block);
854 for(j = 0; j < arity; j++)
856 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
857 get_Proj_proj(end_projx));
859 if(get_irn_n(start_block, j) == begin_projx)
861 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
871 static pmap *projx_link = NULL;
873 void link_to_reg_end (ir_node *n, void *env) {
874 if(get_irn_op(n) == op_Proj &&
875 get_irn_mode(n) == mode_X &&
876 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
877 /* Reg End Projx -> Find the CallBegin Projx and hash it */
878 ir_node *end_projx = n;
879 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
880 get_Proj_proj(end_projx));
881 printf("Linked the following ProjxNodes:\n");
884 set_projx_link(begin_projx, end_projx);
888 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
890 if(projx_link == NULL)
891 projx_link = pmap_create();
892 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
895 ir_node *get_projx_link(ir_node *cb_projx)
897 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
903 is_outermost_loop(ir_loop *l) {
904 return l == get_loop_outer_loop(l);
908 /*-----------------------------------------------------------*
909 * The core algorithm. *
910 *-----------------------------------------------------------*/
913 static void scc (ir_node *n) {
915 if (irn_visited(n)) return;
918 /* Initialize the node */
919 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
920 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
921 set_irn_loop(n, NULL);
925 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
926 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
927 so is_backedge does not access array[-1] but correctly returns false! */
929 if (!is_outermost_Start(n)) {
930 int arity = get_irn_arity(n);
932 for (i = get_start_index(n); i < arity; i++) {
934 if (is_backedge(n, i)) continue;
935 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
936 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
938 if (irn_is_in_stack(m)) {
939 /* Uplink of m is smaller if n->m is a backedge.
940 Propagate the uplink to mark the loop. */
941 if (get_irn_uplink(m) < get_irn_uplink(n))
942 set_irn_uplink(n, get_irn_uplink(m));
947 if (get_irn_dfn(n) == get_irn_uplink(n)) {
948 /* This condition holds for
949 1) the node with the incoming backedge.
950 That is: We found a loop!
951 2) Straight line code, because no uplink has been propagated, so the
952 uplink still is the same as the dfn.
954 But n might not be a proper loop head for the analysis. Proper loop
955 heads are Block and Phi nodes. find_tail searches the stack for
956 Block's and Phi's and takes those nodes as loop heads for the current
957 loop instead and marks the incoming edge as backedge. */
959 ir_node *tail = find_tail(n);
961 /* We have a loop, that is no straight line code,
962 because we found a loop head!
963 Next actions: Open a new loop on the loop tree and
964 try to find inner loops */
966 #if NO_LOOPS_WITHOUT_HEAD
967 /* This is an adaption of the algorithm from fiasco / optscc to
968 * avoid loops without Block or Phi as first node. This should
969 * severely reduce the number of evaluations of nodes to detect
970 * a fixpoint in the heap analysis.
971 * Further it avoids loops without firm nodes that cause errors
972 * in the heap analyses.
973 * But attention: don't do it for the outermost loop: This loop
974 * is not iterated. A first block can be a loop head in case of
975 * an endless recursion. */
979 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
987 ir_loop *l = new_loop();
990 /* Remove the loop from the stack ... */
991 pop_scc_unmark_visit (n);
993 /* The current backedge has been marked, that is temporarily eliminated,
994 by find tail. Start the scc algorithm
995 anew on the subgraph thats left (the current loop without the backedge)
996 in order to find more inner loops. */
999 assert (irn_visited(n));
1000 #if NO_LOOPS_WITHOUT_HEAD
1007 /* No loop head was found, that is we have straightline code.
1008 Pop all nodes from the stack to the current loop. */
1014 static void my_scc (ir_node *n) {
1016 if (irn_visited(n)) return;
1017 mark_irn_visited(n);
1019 /* Initialize the node */
1020 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1021 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1022 set_irn_loop(n, NULL);
1026 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1027 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1028 so is_backedge does not access array[-1] but correctly returns false! */
1030 if (!is_outermost_Start(n)) {
1031 int arity = get_irn_arity(n);
1033 for (i = get_start_index(n); i < arity; i++) {
1035 if (is_backedge(n, i)) continue;
1036 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1037 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1039 if (irn_is_in_stack(m)) {
1040 /* Uplink of m is smaller if n->m is a backedge.
1041 Propagate the uplink to mark the loop. */
1042 if (get_irn_uplink(m) < get_irn_uplink(n))
1043 set_irn_uplink(n, get_irn_uplink(m));
1048 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1049 /* This condition holds for
1050 1) the node with the incoming backedge.
1051 That is: We found a loop!
1052 2) Straight line code, because no uplink has been propagated, so the
1053 uplink still is the same as the dfn.
1055 But n might not be a proper loop head for the analysis. Proper loop
1056 heads are Block and Phi nodes. find_tail searches the stack for
1057 Block's and Phi's and takes those nodes as loop heads for the current
1058 loop instead and marks the incoming edge as backedge. */
1060 ir_node *tail = find_tail(n);
1062 /* We have a loop, that is no straight line code,
1063 because we found a loop head!
1064 Next actions: Open a new loop on the loop tree and
1065 try to find inner loops */
1067 #if NO_LOOPS_WITHOUT_HEAD
1068 /* This is an adaption of the algorithm from fiasco / optscc to
1069 * avoid loops without Block or Phi as first node. This should
1070 * severely reduce the number of evaluations of nodes to detect
1071 * a fixpoint in the heap analysis.
1072 * Further it avoids loops without firm nodes that cause errors
1073 * in the heap analyses. */
1077 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1085 ir_loop *l = new_loop();
1088 /* Remove the loop from the stack ... */
1089 pop_scc_unmark_visit (n);
1091 /* The current backedge has been marked, that is temporarily eliminated,
1092 by find tail. Start the scc algorithm
1093 anew on the subgraph thats left (the current loop without the backedge)
1094 in order to find more inner loops. */
1097 assert (irn_visited(n));
1098 #if NO_LOOPS_WITHOUT_HEAD
1105 /* No loop head was found, that is we have straightline code.
1106 Pop all nodes from the stack to the current loop. */
1112 /* Constructs backedge information for irg. In interprocedural view constructs
1113 backedges for all methods called by irg, too. */
1114 int construct_backedges(ir_graph *irg) {
1115 ir_graph *rem = current_ir_graph;
1118 assert(!get_interprocedural_view() &&
1119 "not implemented, use construct_ip_backedges");
1122 current_ir_graph = irg;
1123 outermost_ir_graph = irg;
1125 init_scc(current_ir_graph);
1127 current_loop = NULL;
1128 new_loop(); /* sets current_loop */
1129 head_rem = current_loop; /* Just for assertion */
1131 inc_irg_visited(current_ir_graph);
1133 scc(get_irg_end(current_ir_graph));
1135 assert(head_rem == current_loop);
1136 set_irg_loop(current_ir_graph, current_loop);
1137 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1138 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1140 irg->loops = current_loop;
1144 count_loop (the_loop, &count, &depth);
1148 current_ir_graph = rem;
1150 return max_loop_depth;
1154 int construct_ip_backedges (void) {
1155 ir_graph *rem = current_ir_graph;
1156 int rem_ipv = get_interprocedural_view();
1160 assert(get_irp_ip_view_state() == ip_view_valid);
1162 outermost_ir_graph = get_irp_main_irg();
1166 current_loop = NULL;
1167 new_loop(); /* sets current_loop */
1168 set_interprocedural_view(true);
1170 inc_max_irg_visited();
1171 for (i = 0; i < get_irp_n_irgs(); i++)
1172 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1174 /** We have to start the walk at the same nodes as cg_walk. **/
1175 /* Walk starting at unreachable procedures. Only these
1176 * have End blocks visible in interprocedural view. */
1177 for (i = 0; i < get_irp_n_irgs(); i++) {
1179 current_ir_graph = get_irp_irg(i);
1181 sb = get_irg_start_block(current_ir_graph);
1183 if ((get_Block_n_cfgpreds(sb) > 1) ||
1184 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1186 scc(get_irg_end(current_ir_graph));
1189 /* Check whether we walked all procedures: there could be procedures
1190 with cyclic calls but no call from the outside. */
1191 for (i = 0; i < get_irp_n_irgs(); i++) {
1193 current_ir_graph = get_irp_irg(i);
1195 /* Test start block: if inner procedure end and end block are not
1196 * visible and therefore not marked. */
1197 sb = get_irg_start_block(current_ir_graph);
1198 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1201 /* Walk all endless loops in inner procedures.
1202 * We recognize an inner procedure if the End node is not visited. */
1203 for (i = 0; i < get_irp_n_irgs(); i++) {
1205 current_ir_graph = get_irp_irg(i);
1207 e = get_irg_end(current_ir_graph);
1208 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1210 /* Don't visit the End node. */
1211 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1215 set_irg_loop(outermost_ir_graph, current_loop);
1216 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1217 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1219 current_ir_graph = rem;
1220 set_interprocedural_view(rem_ipv);
1221 return max_loop_depth;
1224 void my_construct_ip_backedges (void) {
1225 ir_graph *rem = current_ir_graph;
1226 int rem_ipv = get_interprocedural_view();
1229 assert(get_irp_ip_view_state() == ip_view_valid);
1231 outermost_ir_graph = get_irp_main_irg();
1235 current_loop = NULL;
1236 new_loop(); /* sets current_loop */
1237 set_interprocedural_view(true);
1239 inc_max_irg_visited();
1240 for (i = 0; i < get_irp_n_irgs(); i++)
1241 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1243 /** We have to start the walk at the same nodes as cg_walk. **/
1244 /* Walk starting at unreachable procedures. Only these
1245 * have End blocks visible in interprocedural view. */
1246 for (i = 0; i < get_irp_n_irgs(); i++) {
1248 current_ir_graph = get_irp_irg(i);
1250 sb = get_irg_start_block(current_ir_graph);
1252 if ((get_Block_n_cfgpreds(sb) > 1) ||
1253 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1255 my_scc(get_irg_end(current_ir_graph));
1258 /* Check whether we walked all procedures: there could be procedures
1259 with cyclic calls but no call from the outside. */
1260 for (i = 0; i < get_irp_n_irgs(); i++) {
1262 current_ir_graph = get_irp_irg(i);
1264 /* Test start block: if inner procedure end and end block are not
1265 * visible and therefore not marked. */
1266 sb = get_irg_start_block(current_ir_graph);
1267 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1270 /* Walk all endless loops in inner procedures.
1271 * We recognize an inner procedure if the End node is not visited. */
1272 for (i = 0; i < get_irp_n_irgs(); i++) {
1274 current_ir_graph = get_irp_irg(i);
1276 e = get_irg_end(current_ir_graph);
1277 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1279 /* Don't visit the End node. */
1280 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1284 set_irg_loop(outermost_ir_graph, current_loop);
1285 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1286 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1288 current_ir_graph = rem;
1289 set_interprocedural_view(rem_ipv);
1292 static void reset_backedges(ir_node *n) {
1293 if (is_possible_loop_head(n)) {
1294 int rem = get_interprocedural_view();
1296 set_interprocedural_view(true);
1298 set_interprocedural_view(true);
1300 set_interprocedural_view(rem);
1306 static void loop_reset_backedges(ir_loop *l) {
1308 reset_backedges(get_loop_node(l, 0));
1309 for (i = 0; i < get_loop_n_nodes(l); ++i)
1310 set_irn_loop(get_loop_node(l, i), NULL);
1311 for (i = 0; i < get_loop_n_sons(l); ++i) {
1312 loop_reset_backedges(get_loop_son(l, i));
1317 static void loop_reset_node(ir_node *n, void *env) {
1318 set_irn_loop(n, NULL);
1323 /** Removes all loop information.
1324 Resets all backedges */
1325 void free_loop_information(ir_graph *irg) {
1326 /* We can not use this recursion, as the loop might contain
1327 illegal nodes by now. Why else would we throw away the
1329 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1331 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1332 set_irg_loop(irg, NULL);
1333 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1334 /* We cannot free the loop nodes, they are on the obstack. */
1338 void free_all_loop_information (void) {
1340 int rem = get_interprocedural_view();
1341 set_interprocedural_view(true); /* To visit all filter nodes */
1342 for (i = 0; i < get_irp_n_irgs(); i++) {
1343 free_loop_information(get_irp_irg(i));
1345 set_interprocedural_view(rem);
1352 /* Debug stuff *************************************************/
1354 static int test_loop_node(ir_loop *l) {
1355 int i, has_node = 0, found_problem = 0;
1358 assert(l && l->kind == k_ir_loop);
1360 if (get_loop_n_elements(l) == 0) {
1361 printf(" Loop completely empty! "); DDML(l);
1363 dump_loop(l, "-ha");
1366 le = get_loop_element(l, 0);
1367 if (*(le.kind) != k_ir_node) {
1368 assert(le.kind && *(le.kind) == k_ir_loop);
1369 printf(" First loop element is not a node! "); DDML(l);
1370 printf(" "); DDML(le.son);
1373 dump_loop(l, "-ha");
1376 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1377 printf(" Wrong node as head! "); DDML(l);
1378 printf(" "); DDMN(le.node);
1380 dump_loop(l, "-ha");
1383 if ((get_loop_depth(l) != 0) &&
1384 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1385 printf(" Loop head has no backedges! "); DDML(l);
1386 printf(" "); DDMN(le.node);
1388 dump_loop(l, "-ha");
1393 for (i = 0; i < get_loop_n_elements(l); ++i) {
1394 le = get_loop_element(l, i);
1395 if (*(le.kind) == k_ir_node)
1398 if (test_loop_node(le.son)) found_problem = 1;
1401 if (has_node == 0) {
1402 printf(" Loop has no firm node! "); DDML(l);
1404 dump_loop(l, "-ha");
1407 if (get_loop_loop_nr(l) == 11819)
1408 dump_loop(l, "-ha-debug");
1410 return found_problem;
1413 /** Prints all loop nodes that
1414 * - do not have any firm nodes, only loop sons
1415 * - the header is not a Phi, Block or Filter.
1417 void find_strange_loop_nodes(ir_loop *l) {
1418 int found_problem = 0;
1419 printf("\nTesting loop "); DDML(l);
1420 found_problem = test_loop_node(l);
1421 printf("Finished Test\n\n");
1422 if (found_problem) exit(0);
1426 /* ------------------------------------------------------------------- */
1427 /* Simple analyses based on the loop information */
1428 /* ------------------------------------------------------------------- */
1430 int is_loop_variant(ir_loop *l, ir_loop *b) {
1433 if (l == b) return true;
1435 n_elems = get_loop_n_elements(l);
1436 for (i = 0; i < n_elems; ++i) {
1437 loop_element e = get_loop_element(l, i);
1438 if (is_ir_loop(e.kind))
1439 if (is_loop_variant(e.son, b))
1446 /* Test whether a value is loop invariant.
1448 * @param n The node to be tested.
1449 * @param block A block node. We pass the block, not the loop as we must
1450 * start off with a block loop to find all proper uses.
1452 * Returns true, if the node n is not changed in the loop block
1453 * belongs to or in inner loops of this block. */
1454 int is_loop_invariant(ir_node *n, ir_node *block) {
1455 ir_loop *l = get_irn_loop(block);
1456 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1457 return !is_loop_variant(l, get_irn_loop(b));