3 * File name: ir/ana/irscc.c
4 * Purpose: Compute the strongly connected regions and build
5 * backedge/loop datastructures.
6 * A variation on the Tarjan algorithm. See also [Trapp:99],
8 * Author: Goetz Lindenmaier
12 * Copyright: (c) 2002-2003 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
24 #include "irgraph_t.h"
31 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
33 static ir_loop *current_loop; /* Current loop construction is working
35 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
36 Each loop node gets a unique number.
37 What for? ev. remove. @@@ */
38 static int current_dfn = 1; /* Counter to generate depth first numbering
41 void link_to_reg_end (ir_node *n, void *env);
42 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
43 ir_node *get_projx_link(ir_node *cb_projx);
45 /**********************************************************************/
46 /* Node attributes **/
47 /**********************************************************************/
49 /* A map to get from irnodes to loop nodes. */
50 static pmap *node_loop_map = NULL;
52 /**********************************************************************/
53 /* Node attributes needed for the construction. **/
54 /**********************************************************************/
56 typedef struct scc_info {
57 bool in_stack; /* Marks whether node is on the stack. */
58 int dfn; /* Depth first search number. */
59 int uplink; /* dfn number of ancestor. */
60 /* ir_loop *loop; *//* Refers to the containing loop. */
62 struct section *section;
68 static INLINE scc_info* new_scc_info(void) {
69 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
70 memset (info, 0, sizeof (scc_info));
75 mark_irn_in_stack (ir_node *n) {
76 assert(get_irn_link(n));
78 /* ((scc_info *)get_irn_link(n))->in_stack = true; */
79 ((scc_info *)n->link)->in_stack = true;
83 mark_irn_not_in_stack (ir_node *n) {
84 assert(get_irn_link(n));
86 /* ((scc_info *)get_irn_link(n))->in_stack = false; */
87 ((scc_info *)n->link)->in_stack = false;
91 irn_is_in_stack (ir_node *n) {
92 assert(get_irn_link(n));
94 /* return ((scc_info *)get_irn_link(n))->in_stack; */
95 return ((scc_info *)n->link)->in_stack;
99 set_irn_uplink (ir_node *n, int uplink) {
100 assert(get_irn_link(n));
102 /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
103 ((scc_info *)n->link)->uplink = uplink;
107 get_irn_uplink (ir_node *n) {
108 assert(get_irn_link(n));
109 /* from fast to slow */
110 /* return ((scc_info *)get_irn_link(n))->uplink; */
111 return ((scc_info *)n->link)->uplink;
115 set_irn_dfn (ir_node *n, int dfn) {
116 assert(get_irn_link(n));
118 /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
119 ((scc_info *)n->link)->dfn = dfn;
123 get_irn_dfn (ir_node *n) {
124 assert(get_irn_link(n));
126 /* return ((scc_info *)get_irn_link(n))->dfn; */
127 return ((scc_info *)n->link)->dfn;
131 /* Replaced node loop map by real field as hash access dominates runtime
132 * of the algorithm. ! */
133 /* Uses temporary information to set the loop */
135 set_irn_loop (ir_node *n, ir_loop* loop) {
136 assert(node_loop_map && "not initialized!");
137 pmap_insert(node_loop_map, (void *)n, (void *)loop);
140 /* Uses temporary information to get the loop */
142 get_irn_loop (ir_node *n) {
144 if (!node_loop_map) return NULL;
146 if (pmap_contains(node_loop_map, (void *)n))
147 res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
153 set_irn_loop (ir_node *n, ir_loop* loop) {
157 /* Uses temporary information to get the loop */
159 get_irn_loop (ir_node *n) {
166 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
170 /* Test whether n is contained in this loop. */
171 for (i = 0; i < get_loop_n_nodes(l); i++)
172 if (n == get_loop_node(l, i)) return l;
174 /* Is this a leave in the loop tree? If so loop not found. */
175 if (get_loop_n_sons(l) == 0) return NULL;
177 /* Else descend in the loop tree. */
178 for (i = 0; i < get_loop_n_sons(l); i++) {
179 res = find_nodes_loop(n, get_loop_son(l, i));
185 /* @@@ temporary implementation, costly!!! */
186 ir_loop * get_irn_loop(ir_node *n) {
187 ir_loop *l = get_irg_loop(current_ir_graph);
188 l = find_nodes_loop(n, l);
193 /**********************************************************************/
195 /**********************************************************************/
197 static ir_node **stack = NULL;
198 static int tos = 0; /* top of stack */
200 static INLINE void init_stack(void) {
202 ARR_RESIZE (ir_node *, stack, 1000);
204 stack = NEW_ARR_F (ir_node *, 1000);
210 static INLINE void free_stack(void) {
222 if (tos == ARR_LEN (stack)) {
223 int nlen = ARR_LEN (stack) * 2;
224 ARR_RESIZE (ir_node *, stack, nlen);
227 mark_irn_in_stack(n);
230 static INLINE ir_node *
233 ir_node *n = stack[--tos];
234 mark_irn_not_in_stack(n);
238 /* The nodes up to n belong to the current loop.
239 Removes them from the stack and adds them to the current loop. */
241 pop_scc_to_loop (ir_node *n)
251 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
254 set_irn_dfn(m, loop_node_cnt);
255 add_loop_node(current_loop, m);
256 set_irn_loop(m, current_loop);
258 /* if (m==n) break;*/
262 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
265 /* GL ??? my last son is my grandson??? Removes loops with no
266 ir_nodes in them. Such loops have only another loop as son. (Why
267 can't they have two loops as sons? Does it never get that far? ) */
268 static void close_loop (ir_loop *l)
270 int last = get_loop_n_elements(l) - 1;
271 loop_element lelement = get_loop_element(l, last);
272 ir_loop *last_son = lelement.son;
274 if (get_kind(last_son) == k_ir_loop &&
275 get_loop_n_elements(last_son) == 1)
279 lelement = get_loop_element(last_son, 0);
281 if(get_kind(gson) == k_ir_loop)
283 loop_element new_last_son;
285 gson -> outer_loop = l;
286 new_last_son.son = gson;
287 l -> children[last] = new_last_son;
294 /* Removes and unmarks all nodes up to n from the stack.
295 The nodes must be visited once more to assign them to a scc. */
297 pop_scc_unmark_visit (ir_node *n)
303 set_irn_visited(m, 0);
307 /**********************************************************************/
308 /* The loop datastructure. **/
309 /**********************************************************************/
311 /* Allocates a new loop as son of current_loop. Sets current_loop
312 to the new loop and returns the father. */
313 ir_loop *new_loop (void) {
314 ir_loop *father, *son;
316 father = current_loop;
318 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
319 memset (son, 0, sizeof (ir_loop));
320 son->kind = k_ir_loop;
321 son->children = NEW_ARR_F (loop_element, 0);
325 son->outer_loop = father;
326 add_loop_son(father, son);
327 son->depth = father->depth+1;
328 } else { /* The root loop */
329 son->outer_loop = son;
334 son->loop_nr = get_irp_new_node_nr();
343 /* Finishes the datastructures, copies the arrays to the obstack
345 A. Schoesser: Caution: loop -> sons is gone. */
346 static void mature_loop (ir_loop *loop) {
349 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
350 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
351 DEL_ARR_F(loop->sons);
352 loop->sons = new_sons;
356 /* Returns outer loop, itself if outermost. */
357 ir_loop *get_loop_outer_loop (ir_loop *loop) {
358 assert(loop && loop->kind == k_ir_loop);
359 return loop->outer_loop;
362 /* Returns nesting depth of this loop */
363 int get_loop_depth (ir_loop *loop) {
364 assert(loop); assert(loop->kind == k_ir_loop);
368 /* Returns the number of inner loops */
369 int get_loop_n_sons (ir_loop *loop) {
370 assert(loop && loop->kind == k_ir_loop);
371 return(loop -> n_sons);
374 /* Returns the pos`th loop_node-child *
375 * TODO: This method isn`t very efficient ! *
376 * Returns NULL if there isnt`t a pos`th loop_node */
377 ir_loop *get_loop_son (ir_loop *loop, int pos) {
378 int child_nr = 0, loop_nr = -1;
380 assert(loop && loop->kind == k_ir_loop);
381 while(child_nr < ARR_LEN(loop->children))
383 if(*(loop -> children[child_nr].kind) == k_ir_loop)
386 return(loop -> children[child_nr].son);
392 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
396 add_loop_son(ir_loop *loop, ir_loop *son) {
399 assert(loop && loop->kind == k_ir_loop);
400 assert(get_kind(son) == k_ir_loop);
401 ARR_APP1 (loop_element, loop->children, lson);
405 /* Returns the number of nodes in the loop */
406 int get_loop_n_nodes (ir_loop *loop) {
407 assert(loop); assert(loop->kind == k_ir_loop);
408 return loop -> n_nodes;
409 /* return ARR_LEN(loop->nodes); */
412 /* Returns the pos`th ir_node-child *
413 * TODO: This method isn`t very efficient ! *
414 * Returns NULL if there isnt`t a pos`th ir_node */
415 ir_node *get_loop_node (ir_loop *loop, int pos) {
416 int child_nr, node_nr = -1;
418 assert(loop && loop->kind == k_ir_loop);
419 assert(pos < get_loop_n_nodes(loop));
421 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
422 if(*(loop -> children[child_nr].kind) == k_ir_node)
425 return(loop -> children[child_nr].node);
428 printf("pos: %d\n", pos);
429 assert(0 && "no child at pos found");
433 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
437 add_loop_node(ir_loop *loop, ir_node *n) {
440 assert(loop && loop->kind == k_ir_loop);
441 assert(get_kind(n) == k_ir_node);
442 ARR_APP1 (loop_element, loop->children, ln);
446 /** Returns the number of elements contained in loop. */
447 int get_loop_n_elements (ir_loop *loop) {
448 assert(loop && loop->kind == k_ir_loop);
449 return(ARR_LEN(loop->children));
453 Returns the pos`th loop element.
454 This may be a loop_node or a ir_node. The caller of this function has
455 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
456 and then select the apropriate "loop_element.node" or "loop_element.son".
459 loop_element get_loop_element (ir_loop *loop, int pos) {
460 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
462 return(loop -> children[pos]);
465 int get_loop_element_pos(ir_loop *loop, void *le) {
467 assert(loop && loop->kind == k_ir_loop);
469 for (i = 0; i < get_loop_n_elements(loop); i++)
470 if (get_loop_element(loop, i).node == le) return i;
474 int get_loop_loop_nr(ir_loop *loop) {
475 assert(loop && loop->kind == k_ir_loop);
477 return loop->loop_nr;
484 /** A field to connect additional information to a loop. Only valid
485 if libfirm_debug is set. */
486 void set_loop_link (ir_loop *loop, void *link) {
487 assert(loop && loop->kind == k_ir_loop);
492 void *get_loop_link (const ir_loop *loop) {
493 assert(loop && loop->kind == k_ir_loop);
501 /* The outermost loop is remarked in the surrounding graph. */
502 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
506 ir_loop *get_irg_loop(ir_graph *irg) {
512 /**********************************************************************/
513 /* Constructing and destructing the loop/backedge information. **/
514 /**********************************************************************/
516 /* Initialization steps. **********************************************/
519 init_node (ir_node *n, void *env) {
520 set_irn_link (n, new_scc_info());
523 /* Also init nodes not visible in intraproc_view. */
524 /* @@@ init_node is called for too many nodes -- this wastes memory!.
525 The mem is not lost as its on the obstack. */
526 if (get_irn_op(n) == op_Filter) {
527 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
528 init_node(get_Filter_cg_pred(n, i), NULL);
530 if (get_irn_op(n) == op_Block) {
531 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
532 init_node(get_Block_cg_cfgpred(n, i), NULL);
535 /* The following pattern matches only after a call from above pattern. */
536 if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
537 /* @@@ init_node is called for every proj -- this wastes memory!.
538 The mem is not lost as its on the obstack. */
539 ir_node *cb = get_Proj_pred(n);
540 if ((get_irn_op(cb) == op_CallBegin) ||
541 (get_irn_op(cb) == op_EndReg) ||
542 (get_irn_op(cb) == op_EndExcept)) {
544 init_node(get_nodes_Block(cb), NULL);
551 init_scc_common (void) {
554 if (!node_loop_map) node_loop_map = pmap_create();
559 init_scc (ir_graph *irg) {
561 irg_walk_graph (irg, init_node, NULL, NULL);
563 irg_walk (irg, link_to_reg_end, NULL, NULL);
570 cg_walk (init_node, NULL, NULL);
572 #if EXPERIMENTAL_LOOP_TREE
573 cg_walk (link_to_reg_end, NULL, NULL);
577 /* Condition for breaking the recursion. */
578 static bool is_outermost_Start(ir_node *n) {
579 /* Test whether this is the outermost Start node. If so
580 recursion must end. */
581 if ((get_irn_op(n) == op_Block) &&
582 (get_Block_n_cfgpreds(n) == 1) &&
583 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
584 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
588 /* @@@ Bad condition:
589 not possible in interprocedural view as outermost_graph is
590 not necessarily the only with a dead-end start block.
591 Besides current_ir_graph is not set properly. */
592 if ((get_irn_op(n) == op_Block) &&
593 (n == get_irg_start_block(current_ir_graph))) {
594 if ((!interprocedural_view) ||
595 (current_ir_graph == outermost_ir_graph))
602 /* When to walk from nodes to blocks. Only for Control flow operations? */
604 get_start_index(ir_node *n) {
605 #undef BLOCK_BEFORE_NODE
606 #define BLOCK_BEFORE_NODE 1
608 #if BLOCK_BEFORE_NODE
610 /* This version assures, that all nodes are ordered absolutely. This allows
611 to undef all nodes in the heap analysis if the block is false, which means
613 I.e., with this code, the order on the loop tree is correct. But a (single)
614 test showed the loop tree is deeper. */
615 if (get_irn_op(n) == op_Phi ||
616 get_irn_op(n) == op_Block ||
617 (get_irn_op(n) == op_Filter && interprocedural_view) ||
618 (get_irg_pinned(get_irn_irg(n)) == floats &&
619 get_op_pinned(get_irn_op(n)) == floats))
620 // Here we could test for backedge at -1 which is illegal
627 /* This version causes deeper loop trees (at least we verified this
629 But it guarantees that Blocks are analysed before nodes contained in the
630 block. If so, we can set the value to undef if the block is not \
632 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
642 static void test(ir_node *pred, ir_node *root, ir_node *this) {
644 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
646 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
647 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
648 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
650 printf("tos: %d\n", tos);
652 for (i = tos; i >= 0; i--) {
653 ir_node *n = stack[i];
655 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
660 /* Test for legal loop header: Block, Phi, ... */
661 INLINE static bool is_possible_loop_head(ir_node *n) {
662 ir_op *op = get_irn_op(n);
663 return ((op == op_Block) ||
665 ((op == op_Filter) && interprocedural_view));
668 /* Returns true if n is a loop header, i.e., it is a Block, Phi
669 or Filter node and has predecessors within the loop and out
671 @arg root: only needed for assertion. */
673 is_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)) {
691 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
692 DDMN(n); DDMN(pred); DDMN(root);
693 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
699 return some_outof_loop && some_in_loop;
702 /* Returns true if n is possible loop head of an endless loop.
703 I.e., it is a Block, Phi or Filter node and has only predecessors
705 @arg root: only needed for assertion. */
707 is_endless_head (ir_node *n, ir_node *root)
710 int some_outof_loop = 0, some_in_loop = 0;
712 /* Test for legal loop header: Block, Phi, ... */
713 if (!is_possible_loop_head(n))
716 if (!is_outermost_Start(n)) {
717 arity = get_irn_arity(n);
718 for (i = get_start_index(n); i < arity; i++) {
719 ir_node *pred = get_irn_n(n, i);
721 if (is_backedge(n, i)) { continue; }
722 if (!irn_is_in_stack(pred)) {
723 some_outof_loop = 1; //printf(" some out of loop ");
725 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
726 DDMN(pred); DDMN(root);
727 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
733 return !some_outof_loop && some_in_loop;
736 /* Returns index of the predecessor with the smallest dfn number
737 greater-equal than limit. */
739 smallest_dfn_pred (ir_node *n, int limit)
741 int i, index = -2, min = -1;
743 if (!is_outermost_Start(n)) {
744 int arity = get_irn_arity(n);
745 for (i = get_start_index(n); i < arity; i++) {
746 ir_node *pred = get_irn_n(n, i);
748 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
749 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
751 min = get_irn_dfn(pred);
758 /* Returns index of the predecessor with the largest dfn number. */
760 largest_dfn_pred (ir_node *n)
762 int i, index = -2, max = -1;
764 if (!is_outermost_Start(n)) {
765 int arity = get_irn_arity(n);
766 for (i = get_start_index(n); i < arity; i++) {
767 ir_node *pred = get_irn_n(n, i);
768 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
769 if (get_irn_dfn(pred) > max) {
771 max = get_irn_dfn(pred);
778 /** Searches the stack for possible loop heads. Tests these for backedges.
779 If it finds a head with an unmarked backedge it marks this edge and
780 returns the tail of the loop.
781 If it finds no backedge returns NULL.
782 ("disable_backedge" in fiasco)
784 * @param n A node where uplink == dfn.
788 find_tail (ir_node *n) {
790 int i, res_index = -2;
793 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
795 m = stack[tos-1]; /* tos = top of stack */
796 if (is_head (m, n)) {
797 res_index = smallest_dfn_pred(m, 0);
798 if ((res_index == -2) && /* no smallest dfn pred found. */
802 if (m == n) return NULL; // Is this to catch Phi - self loops?
803 for (i = tos-2; i >= 0; --i) {
806 if (is_head (m, n)) {
807 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
808 if (res_index == -2) /* no smallest dfn pred found. */
809 res_index = largest_dfn_pred (m);
811 if ((m == n) && (res_index == -2)) {
817 /* We should not walk past our selves on the stack: The upcoming nodes
818 are not in this loop. We assume a loop not reachable from Start. */
827 /* A dead loop not reachable from Start. */
828 for (i = tos-2; i >= 0; --i) {
830 if (is_endless_head (m, n)) {
831 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
832 if (res_index == -2) /* no smallest dfn pred found. */
833 res_index = largest_dfn_pred (m);
836 if (m == n) { break; } /* It's not an unreachable loop, either. */
838 //assert(0 && "no head found on stack");
842 assert (res_index > -2);
844 set_backedge (m, res_index);
845 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
849 #if EXPERIMENTAL_LOOP_TREE
851 /* ----------------------------------------------------------------
852 AS: This is experimantal code to build loop trees suitable for
853 the heap analysis. Does not work correctly right now... :-(
856 Search in stack for the corresponding first Call-End-ProjX that
857 corresponds to one of the control flow predecessors of the given
858 block, that is the possible callers.
859 returns: the control predecessor to chose\
860 or -1 if no corresponding Call-End-Node could be found
862 - -------------------------------------------------------------- */
864 int search_endproj_in_stack(ir_node *start_block)
867 assert(is_Block(start_block));
868 for(i = tos - 1; i >= 0; --i)
871 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
872 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
874 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
875 ir_node *end_projx = stack[i];
877 for(j = 0; j < get_irn_arity(start_block); j++)
879 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), 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 && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
898 /* Reg End Projx -> Find the CallBegin Projx and hash it */
899 ir_node *end_projx = n;
900 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
901 printf("Linked the following ProjxNodes:\n");
904 set_projx_link(begin_projx, end_projx);
908 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
910 if(projx_link == NULL)
911 projx_link = pmap_create();
912 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
915 ir_node *get_projx_link(ir_node *cb_projx)
917 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
924 /*-----------------------------------------------------------*
925 * The core algorithm. *
926 *-----------------------------------------------------------*/
929 static void scc (ir_node *n) {
931 if (irn_visited(n)) return;
934 /* Initialize the node */
935 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
936 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
937 set_irn_loop(n, NULL);
941 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
942 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
943 so is_backedge does not access array[-1] but correctly returns false! */
945 if (!is_outermost_Start(n)) {
946 int arity = get_irn_arity(n);
948 #if EXPERIMENTAL_LOOP_TREE
950 /* This is meant to be used with the experimenatl code above.
951 If the above code is not used any more, this can be deleted, too.... */
953 if(interprocedural_view &&
955 get_irn_op(get_irn_n(n, 0)) == op_Proj &&
956 get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
958 /* We are at the start node of a function:
959 Walk to the callers in the correct order! */
961 DDMN(get_irn_n(get_irn_n(n, 0), 0));
962 for(i = 0; i < arity; i++)
967 pred_nr = search_endproj_in_stack(n);
968 assert(pred_nr >= 0);
969 if(is_backedge(n, pred_nr))
971 m = get_irn_n(n, pred_nr);
974 if (irn_is_in_stack(m)) {
975 /* Uplink of m is smaller if n->m is a backedge.
976 Propagate the uplink to mark the loop. */
977 if (get_irn_uplink(m) < get_irn_uplink(n))
978 set_irn_uplink(n, get_irn_uplink(m));
987 for (i = get_start_index(n); i < arity; i++) {
989 if (is_backedge(n, i)) continue;
990 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
991 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
993 if (irn_is_in_stack(m)) {
994 /* Uplink of m is smaller if n->m is a backedge.
995 Propagate the uplink to mark the loop. */
996 if (get_irn_uplink(m) < get_irn_uplink(n))
997 set_irn_uplink(n, get_irn_uplink(m));
1003 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1004 /* This condition holds for
1005 1) the node with the incoming backedge.
1006 That is: We found a loop!
1007 2) Straight line code, because no uplink has been propagated, so the
1008 uplink still is the same as the dfn.
1010 But n might not be a proper loop head for the analysis. Proper loop
1011 heads are Block and Phi nodes. find_tail searches the stack for
1012 Block's and Phi's and takes those nodes as loop heads for the current
1013 loop instead and marks the incoming edge as backedge. */
1015 ir_node *tail = find_tail(n);
1017 /* We have a loop, that is no straight line code,
1018 because we found a loop head!
1019 Next actions: Open a new loop on the loop tree and
1020 try to find inner loops */
1023 #define NO_LOOPS_WITHOUT_HEAD 1
1024 #if NO_LOOPS_WITHOUT_HEAD
1026 /* This is an adaption of the algorithm from fiasco / optscc to
1027 * avoid loops without Block or Phi as first node. This should
1028 * severely reduce the number of evaluations of nodes to detect
1029 * a fixpoint in the heap analysis.
1030 * Further it avoids loops without firm nodes that cause errors
1031 * in the heap analyses. */
1035 if (get_loop_n_elements(current_loop) > 0) {
1045 ir_loop *l = new_loop();
1049 /* Remove the loop from the stack ... */
1050 pop_scc_unmark_visit (n);
1052 /* GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1054 /* The current backedge has been marked, that is temporarily eliminated,
1055 by find tail. Start the scc algorithm
1056 anew on the subgraph thats left (the current loop without the backedge)
1057 in order to find more inner loops. */
1061 /* GL @@@ remove experimental stuff current_ir_graph = rem; */
1063 assert (irn_visited(n));
1064 #if NO_LOOPS_WITHOUT_HEAD
1071 /* AS: No loop head was found, that is we have straightline code.
1072 Pop all nodes from the stack to the current loop. */
1078 /* Constructs backedge information for irg. In interprocedural view constructs
1079 backedges for all methods called by irg, too. */
1080 void construct_backedges(ir_graph *irg) {
1081 ir_graph *rem = current_ir_graph;
1084 assert(!interprocedural_view &&
1085 "not implemented, use construct_ip_backedges");
1087 current_ir_graph = irg;
1088 outermost_ir_graph = irg;
1090 init_scc(current_ir_graph);
1092 current_loop = NULL;
1093 new_loop(); /* sets current_loop */
1094 head_rem = current_loop; /* Just for assertion */
1096 if (interprocedural_view) {
1097 set_irg_visited(current_ir_graph, inc_max_irg_visited());
1100 inc_irg_visited(current_ir_graph);
1103 scc(get_irg_end(current_ir_graph));
1105 if (interprocedural_view) finish_ip_walk();
1107 assert(head_rem == current_loop);
1108 set_irg_loop(current_ir_graph, current_loop);
1109 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1110 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1112 irg->loops = current_loop;
1116 count_loop (the_loop, &count, &depth);
1120 current_ir_graph = rem;
1125 void construct_ip_backedges (void) {
1126 ir_graph *rem = current_ir_graph;
1127 int rem_ipv = interprocedural_view;
1130 outermost_ir_graph = get_irp_main_irg();
1134 current_loop = NULL;
1135 new_loop(); /* sets current_loop */
1136 interprocedural_view = 1;
1138 inc_max_irg_visited();
1139 for (i = 0; i < get_irp_n_irgs(); i++)
1140 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1142 for (i = 0; i < get_irp_n_irgs(); i++) {
1144 current_ir_graph = get_irp_irg(i);
1145 /* Find real entry points */
1146 sb = get_irg_start_block(current_ir_graph);
1147 if ((get_Block_n_cfgpreds(sb) > 1) ||
1148 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1149 /* Compute scc for this graph */
1150 outermost_ir_graph = current_ir_graph;
1151 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1152 scc(get_irg_end(current_ir_graph));
1153 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1154 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1157 set_irg_loop(outermost_ir_graph, current_loop);
1158 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1159 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1161 current_ir_graph = rem;
1162 interprocedural_view = rem_ipv;
1165 void construct_ip_backedges (void) {
1166 ir_graph *rem = current_ir_graph;
1167 int rem_ipv = interprocedural_view;
1170 assert(get_irp_ip_view_state() == ip_view_valid);
1172 outermost_ir_graph = get_irp_main_irg();
1176 current_loop = NULL;
1177 new_loop(); /* sets current_loop */
1178 interprocedural_view = 1;
1180 inc_max_irg_visited();
1181 for (i = 0; i < get_irp_n_irgs(); i++)
1182 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1184 /** We have to start the walk at the same nodes as cg_walk. **/
1185 /* Walk starting at unreachable procedures. Only these
1186 * have End blocks visible in interprocedural view. */
1187 for (i = 0; i < get_irp_n_irgs(); i++) {
1189 current_ir_graph = get_irp_irg(i);
1191 sb = get_irg_start_block(current_ir_graph);
1193 if ((get_Block_n_cfgpreds(sb) > 1) ||
1194 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1196 scc(get_irg_end(current_ir_graph));
1199 /* Check whether we walked all procedures: there could be procedures
1200 with cyclic calls but no call from the outside. */
1201 for (i = 0; i < get_irp_n_irgs(); i++) {
1203 current_ir_graph = get_irp_irg(i);
1205 /* Test start block: if inner procedure end and end block are not
1206 * visible and therefore not marked. */
1207 sb = get_irg_start_block(current_ir_graph);
1208 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1211 /* Walk all endless loops in inner procedures.
1212 * We recognize an inner procedure if the End node is not visited. */
1213 for (i = 0; i < get_irp_n_irgs(); i++) {
1215 current_ir_graph = get_irp_irg(i);
1217 e = get_irg_end(current_ir_graph);
1218 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1220 /* Don't visit the End node. */
1221 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1225 set_irg_loop(outermost_ir_graph, current_loop);
1226 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1227 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1229 current_ir_graph = rem;
1230 interprocedural_view = rem_ipv;
1234 static void reset_backedges(ir_node *n) {
1235 if (is_possible_loop_head(n)) {
1236 int rem = interprocedural_view;
1237 interprocedural_view = 1;
1239 interprocedural_view = 0;
1241 interprocedural_view = rem;
1247 static void loop_reset_backedges(ir_loop *l) {
1249 reset_backedges(get_loop_node(l, 0));
1250 for (i = 0; i < get_loop_n_nodes(l); ++i)
1251 set_irn_loop(get_loop_node(l, i), NULL);
1252 for (i = 0; i < get_loop_n_sons(l); ++i) {
1253 loop_reset_backedges(get_loop_son(l, i));
1258 static void loop_reset_node(ir_node *n, void *env) {
1259 set_irn_loop(n, NULL);
1264 /** Removes all loop information.
1265 Resets all backedges */
1266 void free_loop_information(ir_graph *irg) {
1267 /* We can not use this recursion, as the loop might contain
1268 illegal nodes by now. Why else would we throw away the
1270 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1272 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1273 set_irg_loop(irg, NULL);
1274 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1275 /* We cannot free the loop nodes, they are on the obstack. */
1279 void free_all_loop_information (void) {
1281 int rem = interprocedural_view;
1282 interprocedural_view = 1; /* To visit all filter nodes */
1283 for (i = 0; i < get_irp_n_irgs(); i++) {
1284 free_loop_information(get_irp_irg(i));
1286 pmap_destroy(node_loop_map);
1287 node_loop_map = NULL;
1288 interprocedural_view = rem;
1295 /* Debug stuff *************************************************/
1297 static int test_loop_node(ir_loop *l) {
1298 int i, has_node = 0, found_problem = 0;
1301 assert(l && l->kind == k_ir_loop);
1303 if (get_loop_n_elements(l) == 0) {
1304 printf(" Loop completely empty! "); DDML(l);
1306 dump_loop(l, "-ha");
1309 le = get_loop_element(l, 0);
1310 if (*(le.kind) != k_ir_node) {
1311 assert(le.kind && *(le.kind) == k_ir_loop);
1312 printf(" First loop element is not a node! "); DDML(l);
1313 printf(" "); DDML(le.son);
1316 dump_loop(l, "-ha");
1319 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1320 printf(" Wrong node as head! "); DDML(l);
1321 printf(" "); DDMN(le.node);
1323 dump_loop(l, "-ha");
1326 if ((get_loop_depth(l) != 0) &&
1327 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1328 printf(" Loop head has no backedges! "); DDML(l);
1329 printf(" "); DDMN(le.node);
1331 dump_loop(l, "-ha");
1336 for (i = 0; i < get_loop_n_elements(l); ++i) {
1337 le = get_loop_element(l, i);
1338 if (*(le.kind) == k_ir_node)
1341 if (test_loop_node(le.son)) found_problem = 1;
1344 if (has_node == 0) {
1345 printf(" Loop has no firm node! "); DDML(l);
1347 dump_loop(l, "-ha");
1350 if (get_loop_loop_nr(l) == 11819)
1351 dump_loop(l, "-ha-debug");
1353 return found_problem;
1356 /** Prints all loop nodes that
1357 * - do not have any firm nodes, only loop sons
1358 * - the header is not a Phi, Block or Filter.
1360 void find_strange_loop_nodes(ir_loop *l) {
1361 int found_problem = 0;
1362 printf("\nTesting loop "); DDML(l);
1363 found_problem = test_loop_node(l);
1364 printf("Finished Test\n\n");
1365 if (found_problem) exit(0);