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.
29 #include "irgraph_t.h"
37 /* A variant of the loop tree that avoids loops without head.
38 This reduces the depth of the loop tree. */
39 #define NO_LOOPS_WITHOUT_HEAD 1
42 INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
44 INLINE void add_loop_node(ir_loop *loop, ir_node *n);
46 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
48 static ir_loop *current_loop; /* Current loop construction is working
50 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
51 Each loop node gets a unique number.
52 What for? ev. remove. @@@ */
53 static int current_dfn = 1; /* Counter to generate depth first numbering
56 static int max_loop_depth = 0;
58 void link_to_reg_end (ir_node *n, void *env);
59 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
60 ir_node *get_projx_link(ir_node *cb_projx);
62 /**********************************************************************/
63 /* Node attributes **/
64 /**********************************************************************/
66 /**********************************************************************/
67 /* Node attributes needed for the construction. **/
68 /**********************************************************************/
70 typedef struct scc_info {
71 bool in_stack; /* Marks whether node is on the stack. */
72 int dfn; /* Depth first search number. */
73 int uplink; /* dfn number of ancestor. */
74 /* ir_loop *loop; *//* Refers to the containing loop. */
76 struct section *section;
82 static INLINE scc_info* new_scc_info(void) {
83 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
84 memset (info, 0, sizeof (scc_info));
89 mark_irn_in_stack (ir_node *n) {
90 assert(get_irn_link(n));
92 /* ((scc_info *)get_irn_link(n))->in_stack = true; */
93 ((scc_info *)n->link)->in_stack = true;
97 mark_irn_not_in_stack (ir_node *n) {
98 assert(get_irn_link(n));
100 /* ((scc_info *)get_irn_link(n))->in_stack = false; */
101 ((scc_info *)n->link)->in_stack = false;
105 irn_is_in_stack (ir_node *n) {
106 assert(get_irn_link(n));
108 /* return ((scc_info *)get_irn_link(n))->in_stack; */
109 return ((scc_info *)n->link)->in_stack;
113 set_irn_uplink (ir_node *n, int uplink) {
114 assert(get_irn_link(n));
116 /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
117 ((scc_info *)n->link)->uplink = uplink;
121 get_irn_uplink (ir_node *n) {
122 assert(get_irn_link(n));
123 /* from fast to slow */
124 /* return ((scc_info *)get_irn_link(n))->uplink; */
125 return ((scc_info *)n->link)->uplink;
129 set_irn_dfn (ir_node *n, int dfn) {
130 assert(get_irn_link(n));
132 /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
133 ((scc_info *)n->link)->dfn = dfn;
137 get_irn_dfn (ir_node *n) {
138 assert(get_irn_link(n));
140 /* return ((scc_info *)get_irn_link(n))->dfn; */
141 return ((scc_info *)n->link)->dfn;
146 set_irn_loop (ir_node *n, ir_loop* loop) {
150 /* Uses temporary information to get the loop */
152 get_irn_loop (ir_node *n) {
158 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
162 /* Test whether n is contained in this loop. */
163 for (i = 0; i < get_loop_n_nodes(l); i++)
164 if (n == get_loop_node(l, i)) return l;
166 /* Is this a leave in the loop tree? If so loop not found. */
167 if (get_loop_n_sons(l) == 0) return NULL;
169 /* Else descend in the loop tree. */
170 for (i = 0; i < get_loop_n_sons(l); i++) {
171 res = find_nodes_loop(n, get_loop_son(l, i));
177 /* @@@ temporary implementation, costly!!! */
178 ir_loop * get_irn_loop(ir_node *n) {
179 ir_loop *l = get_irg_loop(current_ir_graph);
180 l = find_nodes_loop(n, l);
185 /**********************************************************************/
187 /**********************************************************************/
189 static ir_node **stack = NULL;
190 static int tos = 0; /* top of stack */
192 static INLINE void init_stack(void) {
194 ARR_RESIZE (ir_node *, stack, 1000);
196 stack = NEW_ARR_F (ir_node *, 1000);
202 static INLINE void free_stack(void) {
214 if (tos == ARR_LEN (stack)) {
215 int nlen = ARR_LEN (stack) * 2;
216 ARR_RESIZE (ir_node *, stack, nlen);
219 mark_irn_in_stack(n);
222 static INLINE ir_node *
225 ir_node *n = stack[--tos];
226 mark_irn_not_in_stack(n);
230 /* The nodes up to n belong to the current loop.
231 Removes them from the stack and adds them to the current loop. */
233 pop_scc_to_loop (ir_node *n)
241 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
244 set_irn_dfn(m, loop_node_cnt);
245 add_loop_node(current_loop, m);
246 set_irn_loop(m, current_loop);
248 /* if (m==n) break;*/
251 /* i might be bigger than 1 for dead (and that's why bad) loops */
253 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
257 /* GL ??? my last son is my grandson??? Removes loops with no
258 ir_nodes in them. Such loops have only another loop as son. (Why
259 can't they have two loops as sons? Does it never get that far? ) */
260 static void close_loop (ir_loop *l)
262 int last = get_loop_n_elements(l) - 1;
263 loop_element lelement = get_loop_element(l, last);
264 ir_loop *last_son = lelement.son;
266 if (get_kind(last_son) == k_ir_loop &&
267 get_loop_n_elements(last_son) == 1)
271 lelement = get_loop_element(last_son, 0);
273 if(get_kind(gson) == k_ir_loop)
275 loop_element new_last_son;
277 gson -> outer_loop = l;
278 new_last_son.son = gson;
279 l -> children[last] = new_last_son;
286 /* Removes and unmarks all nodes up to n from the stack.
287 The nodes must be visited once more to assign them to a scc. */
289 pop_scc_unmark_visit (ir_node *n)
295 set_irn_visited(m, 0);
299 /**********************************************************************/
300 /* The loop datastructure. **/
301 /**********************************************************************/
303 /* Allocates a new loop as son of current_loop. Sets current_loop
304 to the new loop and returns the father. */
305 ir_loop *new_loop (void) {
306 ir_loop *father, *son;
308 father = current_loop;
310 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
311 memset (son, 0, sizeof (ir_loop));
312 son->kind = k_ir_loop;
313 son->children = NEW_ARR_F (loop_element, 0);
317 son->outer_loop = father;
318 add_loop_son(father, son);
319 son->depth = father->depth+1;
320 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
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 || get_kind(n) == k_ir_graph); /* used in callgraph.c */
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 int is_ir_loop(const void *thing) {
495 return (get_kind(thing) == k_ir_loop);
498 /* The outermost loop is remarked in the surrounding graph. */
499 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
503 ir_loop *get_irg_loop(ir_graph *irg) {
509 /**********************************************************************/
510 /* Constructing and destructing the loop/backedge information. **/
511 /**********************************************************************/
513 /* Initialization steps. **********************************************/
516 init_node (ir_node *n, void *env) {
517 set_irn_link (n, new_scc_info());
522 init_scc_common (void) {
529 init_scc (ir_graph *irg) {
531 irg_walk_graph (irg, init_node, NULL, NULL);
533 irg_walk (irg, link_to_reg_end, NULL, NULL);
540 cg_walk (init_node, NULL, NULL);
542 #if EXPERIMENTAL_LOOP_TREE
543 cg_walk (link_to_reg_end, NULL, NULL);
547 /* Condition for breaking the recursion. */
548 static bool is_outermost_Start(ir_node *n) {
549 /* Test whether this is the outermost Start node. If so
550 recursion must end. */
551 if ((get_irn_op(n) == op_Block) &&
552 (get_Block_n_cfgpreds(n) == 1) &&
553 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
554 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
558 /* @@@ Bad condition:
559 not possible in interprocedural view as outermost_graph is
560 not necessarily the only with a dead-end start block.
561 Besides current_ir_graph is not set properly. */
562 if ((get_irn_op(n) == op_Block) &&
563 (n == get_irg_start_block(current_ir_graph))) {
564 if ((!get_interprocedural_view()) ||
565 (current_ir_graph == outermost_ir_graph))
572 /* When to walk from nodes to blocks. Only for Control flow operations? */
574 get_start_index(ir_node *n) {
575 #undef BLOCK_BEFORE_NODE
576 #define BLOCK_BEFORE_NODE 1
578 #if BLOCK_BEFORE_NODE
580 /* This version assures, that all nodes are ordered absolutely. This allows
581 to undef all nodes in the heap analysis if the block is false, which means
583 I.e., with this code, the order on the loop tree is correct. But a (single)
584 test showed the loop tree is deeper. */
585 if (get_irn_op(n) == op_Phi ||
586 get_irn_op(n) == op_Block ||
587 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
588 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
589 get_irn_pinned(n) == op_pin_state_floats))
590 // Here we could test for backedge at -1 which is illegal
597 /* This version causes deeper loop trees (at least we verified this
599 But it guarantees that Blocks are analysed before nodes contained in the
600 block. If so, we can set the value to undef if the block is not \
602 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
612 static void test(ir_node *pred, ir_node *root, ir_node *this) {
614 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
616 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
617 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
618 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
620 printf("tos: %d\n", tos);
622 for (i = tos; i >= 0; i--) {
623 ir_node *n = stack[i];
625 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
630 /* Test for legal loop header: Block, Phi, ... */
631 INLINE static bool is_possible_loop_head(ir_node *n) {
632 ir_op *op = get_irn_op(n);
633 return ((op == op_Block) ||
635 ((op == op_Filter) && get_interprocedural_view()));
638 /* Returns true if n is a loop header, i.e., it is a Block, Phi
639 or Filter node and has predecessors within the loop and out
641 @arg root: only needed for assertion. */
643 is_head (ir_node *n, ir_node *root)
646 int some_outof_loop = 0, some_in_loop = 0;
648 /* Test for legal loop header: Block, Phi, ... */
649 if (!is_possible_loop_head(n))
652 if (!is_outermost_Start(n)) {
653 arity = get_irn_arity(n);
654 for (i = get_start_index(n); i < arity; i++) {
655 ir_node *pred = get_irn_n(n, i);
657 if (is_backedge(n, i)) continue;
658 if (!irn_is_in_stack(pred)) {
661 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
662 DDMN(n); DDMN(pred); DDMN(root);
663 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
669 return some_outof_loop && some_in_loop;
672 /* Returns true if n is possible loop head of an endless loop.
673 I.e., it is a Block, Phi or Filter node and has only predecessors
675 @arg root: only needed for assertion. */
677 is_endless_head (ir_node *n, ir_node *root)
680 int some_outof_loop = 0, some_in_loop = 0;
682 /* Test for legal loop header: Block, Phi, ... */
683 if (!is_possible_loop_head(n))
686 if (!is_outermost_Start(n)) {
687 arity = get_irn_arity(n);
688 for (i = get_start_index(n); i < arity; i++) {
689 ir_node *pred = get_irn_n(n, i);
691 if (is_backedge(n, i)) { continue; }
692 if (!irn_is_in_stack(pred)) {
693 some_outof_loop = 1; //printf(" some out of loop ");
695 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
696 DDMN(pred); DDMN(root);
697 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
703 return !some_outof_loop && some_in_loop;
706 /* Returns index of the predecessor with the smallest dfn number
707 greater-equal than limit. */
709 smallest_dfn_pred (ir_node *n, int limit)
711 int i, index = -2, min = -1;
713 if (!is_outermost_Start(n)) {
714 int arity = get_irn_arity(n);
715 for (i = get_start_index(n); i < arity; i++) {
716 ir_node *pred = get_irn_n(n, i);
718 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
719 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
721 min = get_irn_dfn(pred);
728 /* Returns index of the predecessor with the largest dfn number. */
730 largest_dfn_pred (ir_node *n)
732 int i, index = -2, max = -1;
734 if (!is_outermost_Start(n)) {
735 int arity = get_irn_arity(n);
736 for (i = get_start_index(n); i < arity; i++) {
737 ir_node *pred = get_irn_n(n, i);
738 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
739 if (get_irn_dfn(pred) > max) {
741 max = get_irn_dfn(pred);
748 /** Searches the stack for possible loop heads. Tests these for backedges.
749 If it finds a head with an unmarked backedge it marks this edge and
750 returns the tail of the loop.
751 If it finds no backedge returns NULL.
752 ("disable_backedge" in fiasco)
754 * @param n A node where uplink == dfn.
758 find_tail (ir_node *n) {
760 int i, res_index = -2;
763 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
765 m = stack[tos-1]; /* tos = top of stack */
766 if (is_head (m, n)) {
767 res_index = smallest_dfn_pred(m, 0);
768 if ((res_index == -2) && /* no smallest dfn pred found. */
772 if (m == n) return NULL; // Is this to catch Phi - self loops?
773 for (i = tos-2; i >= 0; --i) {
776 if (is_head (m, n)) {
777 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
778 if (res_index == -2) /* no smallest dfn pred found. */
779 res_index = largest_dfn_pred (m);
781 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
787 /* We should not walk past our selves on the stack: The upcoming nodes
788 are not in this loop. We assume a loop not reachable from Start. */
797 /* A dead loop not reachable from Start. */
798 for (i = tos-2; i >= 0; --i) {
800 if (is_endless_head (m, n)) {
801 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
802 if (res_index == -2) /* no smallest dfn pred found. */
803 res_index = largest_dfn_pred (m);
806 if (m == n) { break; } /* It's not an unreachable loop, either. */
808 //assert(0 && "no head found on stack");
812 if (res_index <= -2) {
813 /* It's a completely bad loop: without Phi/Block nodes that can
814 be a head. I.e., the code is "dying". We break the loop by
815 setting Bad nodes. */
816 int arity = get_irn_arity(n);
817 for (i = -1; i < arity; ++i) {
818 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
822 assert (res_index > -2);
824 set_backedge (m, res_index);
825 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
829 #if EXPERIMENTAL_LOOP_TREE
831 /* ----------------------------------------------------------------
832 AS: This is experimantal code to build loop trees suitable for
833 the heap analysis. Does not work correctly right now... :-(
836 Search in stack for the corresponding first Call-End-ProjX that
837 corresponds to one of the control flow predecessors of the given
838 block, that is the possible callers.
839 returns: the control predecessor to chose\
840 or -1 if no corresponding Call-End-Node could be found
842 - -------------------------------------------------------------- */
844 int search_endproj_in_stack(ir_node *start_block)
847 assert(is_Block(start_block));
848 for(i = tos - 1; i >= 0; --i)
851 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
852 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
854 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
855 ir_node *end_projx = stack[i];
857 int arity = get_irn_arity(start_block);
858 for(j = 0; j < arity; j++)
860 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
861 get_Proj_proj(end_projx));
863 if(get_irn_n(start_block, j) == begin_projx)
865 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
875 static pmap *projx_link = NULL;
877 void link_to_reg_end (ir_node *n, void *env) {
878 if(get_irn_op(n) == op_Proj &&
879 get_irn_mode(n) == mode_X &&
880 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
881 /* Reg End Projx -> Find the CallBegin Projx and hash it */
882 ir_node *end_projx = n;
883 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
884 get_Proj_proj(end_projx));
885 printf("Linked the following ProjxNodes:\n");
888 set_projx_link(begin_projx, end_projx);
892 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
894 if(projx_link == NULL)
895 projx_link = pmap_create();
896 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
899 ir_node *get_projx_link(ir_node *cb_projx)
901 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
907 is_outermost_loop(ir_loop *l) {
908 return l == get_loop_outer_loop(l);
912 /*-----------------------------------------------------------*
913 * The core algorithm. *
914 *-----------------------------------------------------------*/
917 static void scc (ir_node *n) {
919 if (irn_visited(n)) return;
922 /* Initialize the node */
923 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
924 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
925 set_irn_loop(n, NULL);
929 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
930 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
931 so is_backedge does not access array[-1] but correctly returns false! */
933 if (!is_outermost_Start(n)) {
934 int arity = get_irn_arity(n);
936 for (i = get_start_index(n); i < arity; i++) {
938 if (is_backedge(n, i)) continue;
939 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
940 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
942 if (irn_is_in_stack(m)) {
943 /* Uplink of m is smaller if n->m is a backedge.
944 Propagate the uplink to mark the loop. */
945 if (get_irn_uplink(m) < get_irn_uplink(n))
946 set_irn_uplink(n, get_irn_uplink(m));
951 if (get_irn_dfn(n) == get_irn_uplink(n)) {
952 /* This condition holds for
953 1) the node with the incoming backedge.
954 That is: We found a loop!
955 2) Straight line code, because no uplink has been propagated, so the
956 uplink still is the same as the dfn.
958 But n might not be a proper loop head for the analysis. Proper loop
959 heads are Block and Phi nodes. find_tail searches the stack for
960 Block's and Phi's and takes those nodes as loop heads for the current
961 loop instead and marks the incoming edge as backedge. */
963 ir_node *tail = find_tail(n);
965 /* We have a loop, that is no straight line code,
966 because we found a loop head!
967 Next actions: Open a new loop on the loop tree and
968 try to find inner loops */
970 #if NO_LOOPS_WITHOUT_HEAD
971 /* This is an adaption of the algorithm from fiasco / optscc to
972 * avoid loops without Block or Phi as first node. This should
973 * severely reduce the number of evaluations of nodes to detect
974 * a fixpoint in the heap analysis.
975 * Further it avoids loops without firm nodes that cause errors
976 * in the heap analyses.
977 * But attention: don't do it for the outermost loop: This loop
978 * is not iterated. A first block can be a loop head in case of
979 * an endless recursion. */
983 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
991 ir_loop *l = new_loop();
994 /* Remove the loop from the stack ... */
995 pop_scc_unmark_visit (n);
997 /* The current backedge has been marked, that is temporarily eliminated,
998 by find tail. Start the scc algorithm
999 anew on the subgraph thats left (the current loop without the backedge)
1000 in order to find more inner loops. */
1003 assert (irn_visited(n));
1004 #if NO_LOOPS_WITHOUT_HEAD
1011 /* No loop head was found, that is we have straightline code.
1012 Pop all nodes from the stack to the current loop. */
1018 static void my_scc (ir_node *n) {
1020 if (irn_visited(n)) return;
1021 mark_irn_visited(n);
1023 /* Initialize the node */
1024 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1025 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1026 set_irn_loop(n, NULL);
1030 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1031 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1032 so is_backedge does not access array[-1] but correctly returns false! */
1034 if (!is_outermost_Start(n)) {
1035 int arity = get_irn_arity(n);
1037 for (i = get_start_index(n); i < arity; i++) {
1039 if (is_backedge(n, i)) continue;
1040 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1041 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1043 if (irn_is_in_stack(m)) {
1044 /* Uplink of m is smaller if n->m is a backedge.
1045 Propagate the uplink to mark the loop. */
1046 if (get_irn_uplink(m) < get_irn_uplink(n))
1047 set_irn_uplink(n, get_irn_uplink(m));
1052 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1053 /* This condition holds for
1054 1) the node with the incoming backedge.
1055 That is: We found a loop!
1056 2) Straight line code, because no uplink has been propagated, so the
1057 uplink still is the same as the dfn.
1059 But n might not be a proper loop head for the analysis. Proper loop
1060 heads are Block and Phi nodes. find_tail searches the stack for
1061 Block's and Phi's and takes those nodes as loop heads for the current
1062 loop instead and marks the incoming edge as backedge. */
1064 ir_node *tail = find_tail(n);
1066 /* We have a loop, that is no straight line code,
1067 because we found a loop head!
1068 Next actions: Open a new loop on the loop tree and
1069 try to find inner loops */
1071 #if NO_LOOPS_WITHOUT_HEAD
1072 /* This is an adaption of the algorithm from fiasco / optscc to
1073 * avoid loops without Block or Phi as first node. This should
1074 * severely reduce the number of evaluations of nodes to detect
1075 * a fixpoint in the heap analysis.
1076 * Further it avoids loops without firm nodes that cause errors
1077 * in the heap analyses. */
1081 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1089 ir_loop *l = new_loop();
1092 /* Remove the loop from the stack ... */
1093 pop_scc_unmark_visit (n);
1095 /* The current backedge has been marked, that is temporarily eliminated,
1096 by find tail. Start the scc algorithm
1097 anew on the subgraph thats left (the current loop without the backedge)
1098 in order to find more inner loops. */
1101 assert (irn_visited(n));
1102 #if NO_LOOPS_WITHOUT_HEAD
1109 /* No loop head was found, that is we have straightline code.
1110 Pop all nodes from the stack to the current loop. */
1116 /* Constructs backedge information for irg. In interprocedural view constructs
1117 backedges for all methods called by irg, too. */
1118 int construct_backedges(ir_graph *irg) {
1119 ir_graph *rem = current_ir_graph;
1122 assert(!get_interprocedural_view() &&
1123 "not implemented, use construct_ip_backedges");
1126 current_ir_graph = irg;
1127 outermost_ir_graph = irg;
1129 init_scc(current_ir_graph);
1131 current_loop = NULL;
1132 new_loop(); /* sets current_loop */
1133 head_rem = current_loop; /* Just for assertion */
1135 inc_irg_visited(current_ir_graph);
1137 scc(get_irg_end(current_ir_graph));
1139 assert(head_rem == current_loop);
1140 set_irg_loop(current_ir_graph, current_loop);
1141 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1142 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1144 irg->loops = current_loop;
1148 count_loop (the_loop, &count, &depth);
1152 current_ir_graph = rem;
1154 return max_loop_depth;
1158 int construct_ip_backedges (void) {
1159 ir_graph *rem = current_ir_graph;
1160 int rem_ipv = get_interprocedural_view();
1164 assert(get_irp_ip_view_state() == ip_view_valid);
1166 outermost_ir_graph = get_irp_main_irg();
1170 current_loop = NULL;
1171 new_loop(); /* sets current_loop */
1172 set_interprocedural_view(true);
1174 inc_max_irg_visited();
1175 for (i = 0; i < get_irp_n_irgs(); i++)
1176 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1178 /** We have to start the walk at the same nodes as cg_walk. **/
1179 /* Walk starting at unreachable procedures. Only these
1180 * have End blocks visible in interprocedural view. */
1181 for (i = 0; i < get_irp_n_irgs(); i++) {
1183 current_ir_graph = get_irp_irg(i);
1185 sb = get_irg_start_block(current_ir_graph);
1187 if ((get_Block_n_cfgpreds(sb) > 1) ||
1188 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1190 scc(get_irg_end(current_ir_graph));
1193 /* Check whether we walked all procedures: there could be procedures
1194 with cyclic calls but no call from the outside. */
1195 for (i = 0; i < get_irp_n_irgs(); i++) {
1197 current_ir_graph = get_irp_irg(i);
1199 /* Test start block: if inner procedure end and end block are not
1200 * visible and therefore not marked. */
1201 sb = get_irg_start_block(current_ir_graph);
1202 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1205 /* Walk all endless loops in inner procedures.
1206 * We recognize an inner procedure if the End node is not visited. */
1207 for (i = 0; i < get_irp_n_irgs(); i++) {
1209 current_ir_graph = get_irp_irg(i);
1211 e = get_irg_end(current_ir_graph);
1212 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1214 /* Don't visit the End node. */
1215 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1219 set_irg_loop(outermost_ir_graph, current_loop);
1220 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1221 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1223 current_ir_graph = rem;
1224 set_interprocedural_view(rem_ipv);
1225 return max_loop_depth;
1228 void my_construct_ip_backedges (void) {
1229 ir_graph *rem = current_ir_graph;
1230 int rem_ipv = get_interprocedural_view();
1233 assert(get_irp_ip_view_state() == ip_view_valid);
1235 outermost_ir_graph = get_irp_main_irg();
1239 current_loop = NULL;
1240 new_loop(); /* sets current_loop */
1241 set_interprocedural_view(true);
1243 inc_max_irg_visited();
1244 for (i = 0; i < get_irp_n_irgs(); i++)
1245 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1247 /** We have to start the walk at the same nodes as cg_walk. **/
1248 /* Walk starting at unreachable procedures. Only these
1249 * have End blocks visible in interprocedural view. */
1250 for (i = 0; i < get_irp_n_irgs(); i++) {
1252 current_ir_graph = get_irp_irg(i);
1254 sb = get_irg_start_block(current_ir_graph);
1256 if ((get_Block_n_cfgpreds(sb) > 1) ||
1257 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1259 my_scc(get_irg_end(current_ir_graph));
1262 /* Check whether we walked all procedures: there could be procedures
1263 with cyclic calls but no call from the outside. */
1264 for (i = 0; i < get_irp_n_irgs(); i++) {
1266 current_ir_graph = get_irp_irg(i);
1268 /* Test start block: if inner procedure end and end block are not
1269 * visible and therefore not marked. */
1270 sb = get_irg_start_block(current_ir_graph);
1271 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1274 /* Walk all endless loops in inner procedures.
1275 * We recognize an inner procedure if the End node is not visited. */
1276 for (i = 0; i < get_irp_n_irgs(); i++) {
1278 current_ir_graph = get_irp_irg(i);
1280 e = get_irg_end(current_ir_graph);
1281 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1283 /* Don't visit the End node. */
1284 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1288 set_irg_loop(outermost_ir_graph, current_loop);
1289 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1290 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1292 current_ir_graph = rem;
1293 set_interprocedural_view(rem_ipv);
1296 static void reset_backedges(ir_node *n) {
1297 if (is_possible_loop_head(n)) {
1298 int rem = get_interprocedural_view();
1300 set_interprocedural_view(true);
1302 set_interprocedural_view(true);
1304 set_interprocedural_view(rem);
1310 static void loop_reset_backedges(ir_loop *l) {
1312 reset_backedges(get_loop_node(l, 0));
1313 for (i = 0; i < get_loop_n_nodes(l); ++i)
1314 set_irn_loop(get_loop_node(l, i), NULL);
1315 for (i = 0; i < get_loop_n_sons(l); ++i) {
1316 loop_reset_backedges(get_loop_son(l, i));
1321 static void loop_reset_node(ir_node *n, void *env) {
1322 set_irn_loop(n, NULL);
1327 /** Removes all loop information.
1328 Resets all backedges */
1329 void free_loop_information(ir_graph *irg) {
1330 /* We can not use this recursion, as the loop might contain
1331 illegal nodes by now. Why else would we throw away the
1333 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1335 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1336 set_irg_loop(irg, NULL);
1337 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1338 /* We cannot free the loop nodes, they are on the obstack. */
1342 void free_all_loop_information (void) {
1344 int rem = get_interprocedural_view();
1345 set_interprocedural_view(true); /* To visit all filter nodes */
1346 for (i = 0; i < get_irp_n_irgs(); i++) {
1347 free_loop_information(get_irp_irg(i));
1349 set_interprocedural_view(rem);
1356 /* Debug stuff *************************************************/
1358 static int test_loop_node(ir_loop *l) {
1359 int i, has_node = 0, found_problem = 0;
1362 assert(l && l->kind == k_ir_loop);
1364 if (get_loop_n_elements(l) == 0) {
1365 printf(" Loop completely empty! "); DDML(l);
1367 dump_loop(l, "-ha");
1370 le = get_loop_element(l, 0);
1371 if (*(le.kind) != k_ir_node) {
1372 assert(le.kind && *(le.kind) == k_ir_loop);
1373 printf(" First loop element is not a node! "); DDML(l);
1374 printf(" "); DDML(le.son);
1377 dump_loop(l, "-ha");
1380 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1381 printf(" Wrong node as head! "); DDML(l);
1382 printf(" "); DDMN(le.node);
1384 dump_loop(l, "-ha");
1387 if ((get_loop_depth(l) != 0) &&
1388 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1389 printf(" Loop head has no backedges! "); DDML(l);
1390 printf(" "); DDMN(le.node);
1392 dump_loop(l, "-ha");
1397 for (i = 0; i < get_loop_n_elements(l); ++i) {
1398 le = get_loop_element(l, i);
1399 if (*(le.kind) == k_ir_node)
1402 if (test_loop_node(le.son)) found_problem = 1;
1405 if (has_node == 0) {
1406 printf(" Loop has no firm node! "); DDML(l);
1408 dump_loop(l, "-ha");
1411 if (get_loop_loop_nr(l) == 11819)
1412 dump_loop(l, "-ha-debug");
1414 return found_problem;
1417 /** Prints all loop nodes that
1418 * - do not have any firm nodes, only loop sons
1419 * - the header is not a Phi, Block or Filter.
1421 void find_strange_loop_nodes(ir_loop *l) {
1422 int found_problem = 0;
1423 printf("\nTesting loop "); DDML(l);
1424 found_problem = test_loop_node(l);
1425 printf("Finished Test\n\n");
1426 if (found_problem) exit(0);
1430 /* ------------------------------------------------------------------- */
1431 /* Simple analyses based on the loop information */
1432 /* ------------------------------------------------------------------- */
1434 int is_loop_variant(ir_loop *l, ir_loop *b) {
1437 if (l == b) return true;
1439 n_elems = get_loop_n_elements(l);
1440 for (i = 0; i < n_elems; ++i) {
1441 loop_element e = get_loop_element(l, i);
1442 if (is_ir_loop(e.kind))
1443 if (is_loop_variant(e.son, b))
1450 /* Test whether a value is loop invariant.
1452 * @param n The node to be tested.
1453 * @param block A block node. We pass the block, not the loop as we must
1454 * start off with a block loop to find all proper uses.
1456 * Returns true, if the node n is not changed in the loop block
1457 * belongs to or in inner loops of this block. */
1458 int is_loop_invariant(ir_node *n, ir_node *block) {
1459 ir_loop *l = get_irn_loop(block);
1460 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1461 return !is_loop_variant(l, get_irn_loop(b));