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)
249 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
252 set_irn_dfn(m, loop_node_cnt);
253 add_loop_node(current_loop, m);
254 set_irn_loop(m, current_loop);
256 /* if (m==n) break;*/
259 /* i might be bigger than 1 for dead (and that's why bad) loops */
261 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 if (res_index <= -2) {
843 /* It's a completely bad loop: without Phi/Block nodes that can
844 be a head. I.e., the code is "dying". We break the loop by
845 setting Bad nodes. */
846 for (i = -1; i < get_irn_arity(n); ++i) {
847 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
851 assert (res_index > -2);
853 set_backedge (m, res_index);
854 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
858 #if EXPERIMENTAL_LOOP_TREE
860 /* ----------------------------------------------------------------
861 AS: This is experimantal code to build loop trees suitable for
862 the heap analysis. Does not work correctly right now... :-(
865 Search in stack for the corresponding first Call-End-ProjX that
866 corresponds to one of the control flow predecessors of the given
867 block, that is the possible callers.
868 returns: the control predecessor to chose\
869 or -1 if no corresponding Call-End-Node could be found
871 - -------------------------------------------------------------- */
873 int search_endproj_in_stack(ir_node *start_block)
876 assert(is_Block(start_block));
877 for(i = tos - 1; i >= 0; --i)
880 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
881 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
883 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
884 ir_node *end_projx = stack[i];
886 for(j = 0; j < get_irn_arity(start_block); j++)
888 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
890 if(get_irn_n(start_block, j) == begin_projx)
892 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
902 static pmap *projx_link = NULL;
904 void link_to_reg_end (ir_node *n, void *env) {
905 if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
907 /* Reg End Projx -> Find the CallBegin Projx and hash it */
908 ir_node *end_projx = n;
909 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
910 printf("Linked the following ProjxNodes:\n");
913 set_projx_link(begin_projx, end_projx);
917 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
919 if(projx_link == NULL)
920 projx_link = pmap_create();
921 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
924 ir_node *get_projx_link(ir_node *cb_projx)
926 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
933 /*-----------------------------------------------------------*
934 * The core algorithm. *
935 *-----------------------------------------------------------*/
938 static void scc (ir_node *n) {
940 if (irn_visited(n)) return;
943 /* Initialize the node */
944 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
945 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
946 set_irn_loop(n, NULL);
950 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
951 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
952 so is_backedge does not access array[-1] but correctly returns false! */
954 if (!is_outermost_Start(n)) {
955 int arity = get_irn_arity(n);
957 #if EXPERIMENTAL_LOOP_TREE
959 /* This is meant to be used with the experimenatl code above.
960 If the above code is not used any more, this can be deleted, too.... */
962 if(interprocedural_view &&
964 get_irn_op(get_irn_n(n, 0)) == op_Proj &&
965 get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
967 /* We are at the start node of a function:
968 Walk to the callers in the correct order! */
970 DDMN(get_irn_n(get_irn_n(n, 0), 0));
971 for(i = 0; i < arity; i++)
976 pred_nr = search_endproj_in_stack(n);
977 assert(pred_nr >= 0);
978 if(is_backedge(n, pred_nr))
980 m = get_irn_n(n, pred_nr);
983 if (irn_is_in_stack(m)) {
984 /* Uplink of m is smaller if n->m is a backedge.
985 Propagate the uplink to mark the loop. */
986 if (get_irn_uplink(m) < get_irn_uplink(n))
987 set_irn_uplink(n, get_irn_uplink(m));
996 for (i = get_start_index(n); i < arity; i++) {
998 if (is_backedge(n, i)) continue;
999 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1000 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1002 if (irn_is_in_stack(m)) {
1003 /* Uplink of m is smaller if n->m is a backedge.
1004 Propagate the uplink to mark the loop. */
1005 if (get_irn_uplink(m) < get_irn_uplink(n))
1006 set_irn_uplink(n, get_irn_uplink(m));
1012 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1013 /* This condition holds for
1014 1) the node with the incoming backedge.
1015 That is: We found a loop!
1016 2) Straight line code, because no uplink has been propagated, so the
1017 uplink still is the same as the dfn.
1019 But n might not be a proper loop head for the analysis. Proper loop
1020 heads are Block and Phi nodes. find_tail searches the stack for
1021 Block's and Phi's and takes those nodes as loop heads for the current
1022 loop instead and marks the incoming edge as backedge. */
1024 ir_node *tail = find_tail(n);
1026 /* We have a loop, that is no straight line code,
1027 because we found a loop head!
1028 Next actions: Open a new loop on the loop tree and
1029 try to find inner loops */
1032 #define NO_LOOPS_WITHOUT_HEAD 1
1033 #if NO_LOOPS_WITHOUT_HEAD
1035 /* This is an adaption of the algorithm from fiasco / optscc to
1036 * avoid loops without Block or Phi as first node. This should
1037 * severely reduce the number of evaluations of nodes to detect
1038 * a fixpoint in the heap analysis.
1039 * Further it avoids loops without firm nodes that cause errors
1040 * in the heap analyses. */
1044 if (get_loop_n_elements(current_loop) > 0) {
1054 ir_loop *l = new_loop();
1058 /* Remove the loop from the stack ... */
1059 pop_scc_unmark_visit (n);
1061 /* GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1063 /* The current backedge has been marked, that is temporarily eliminated,
1064 by find tail. Start the scc algorithm
1065 anew on the subgraph thats left (the current loop without the backedge)
1066 in order to find more inner loops. */
1070 /* GL @@@ remove experimental stuff current_ir_graph = rem; */
1072 assert (irn_visited(n));
1073 #if NO_LOOPS_WITHOUT_HEAD
1080 /* AS: No loop head was found, that is we have straightline code.
1081 Pop all nodes from the stack to the current loop. */
1087 /* Constructs backedge information for irg. In interprocedural view constructs
1088 backedges for all methods called by irg, too. */
1089 void construct_backedges(ir_graph *irg) {
1090 ir_graph *rem = current_ir_graph;
1093 assert(!interprocedural_view &&
1094 "not implemented, use construct_ip_backedges");
1096 current_ir_graph = irg;
1097 outermost_ir_graph = irg;
1099 init_scc(current_ir_graph);
1101 current_loop = NULL;
1102 new_loop(); /* sets current_loop */
1103 head_rem = current_loop; /* Just for assertion */
1105 if (interprocedural_view) {
1106 set_irg_visited(current_ir_graph, inc_max_irg_visited());
1109 inc_irg_visited(current_ir_graph);
1112 scc(get_irg_end(current_ir_graph));
1114 if (interprocedural_view) finish_ip_walk();
1116 assert(head_rem == current_loop);
1117 set_irg_loop(current_ir_graph, current_loop);
1118 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1119 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1121 irg->loops = current_loop;
1125 count_loop (the_loop, &count, &depth);
1129 current_ir_graph = rem;
1134 void construct_ip_backedges (void) {
1135 ir_graph *rem = current_ir_graph;
1136 int rem_ipv = interprocedural_view;
1139 outermost_ir_graph = get_irp_main_irg();
1143 current_loop = NULL;
1144 new_loop(); /* sets current_loop */
1145 interprocedural_view = 1;
1147 inc_max_irg_visited();
1148 for (i = 0; i < get_irp_n_irgs(); i++)
1149 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1151 for (i = 0; i < get_irp_n_irgs(); i++) {
1153 current_ir_graph = get_irp_irg(i);
1154 /* Find real entry points */
1155 sb = get_irg_start_block(current_ir_graph);
1156 if ((get_Block_n_cfgpreds(sb) > 1) ||
1157 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1158 /* Compute scc for this graph */
1159 outermost_ir_graph = current_ir_graph;
1160 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1161 scc(get_irg_end(current_ir_graph));
1162 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1163 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1166 set_irg_loop(outermost_ir_graph, current_loop);
1167 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1168 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1170 current_ir_graph = rem;
1171 interprocedural_view = rem_ipv;
1174 void construct_ip_backedges (void) {
1175 ir_graph *rem = current_ir_graph;
1176 int rem_ipv = interprocedural_view;
1179 assert(get_irp_ip_view_state() == ip_view_valid);
1181 outermost_ir_graph = get_irp_main_irg();
1185 current_loop = NULL;
1186 new_loop(); /* sets current_loop */
1187 interprocedural_view = 1;
1189 inc_max_irg_visited();
1190 for (i = 0; i < get_irp_n_irgs(); i++)
1191 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1193 /** We have to start the walk at the same nodes as cg_walk. **/
1194 /* Walk starting at unreachable procedures. Only these
1195 * have End blocks visible in interprocedural view. */
1196 for (i = 0; i < get_irp_n_irgs(); i++) {
1198 current_ir_graph = get_irp_irg(i);
1200 sb = get_irg_start_block(current_ir_graph);
1202 if ((get_Block_n_cfgpreds(sb) > 1) ||
1203 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1205 scc(get_irg_end(current_ir_graph));
1208 /* Check whether we walked all procedures: there could be procedures
1209 with cyclic calls but no call from the outside. */
1210 for (i = 0; i < get_irp_n_irgs(); i++) {
1212 current_ir_graph = get_irp_irg(i);
1214 /* Test start block: if inner procedure end and end block are not
1215 * visible and therefore not marked. */
1216 sb = get_irg_start_block(current_ir_graph);
1217 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1220 /* Walk all endless loops in inner procedures.
1221 * We recognize an inner procedure if the End node is not visited. */
1222 for (i = 0; i < get_irp_n_irgs(); i++) {
1224 current_ir_graph = get_irp_irg(i);
1226 e = get_irg_end(current_ir_graph);
1227 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1229 /* Don't visit the End node. */
1230 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1234 set_irg_loop(outermost_ir_graph, current_loop);
1235 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1236 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1238 current_ir_graph = rem;
1239 interprocedural_view = rem_ipv;
1243 static void reset_backedges(ir_node *n) {
1244 if (is_possible_loop_head(n)) {
1245 int rem = interprocedural_view;
1246 interprocedural_view = 1;
1248 interprocedural_view = 0;
1250 interprocedural_view = rem;
1256 static void loop_reset_backedges(ir_loop *l) {
1258 reset_backedges(get_loop_node(l, 0));
1259 for (i = 0; i < get_loop_n_nodes(l); ++i)
1260 set_irn_loop(get_loop_node(l, i), NULL);
1261 for (i = 0; i < get_loop_n_sons(l); ++i) {
1262 loop_reset_backedges(get_loop_son(l, i));
1267 static void loop_reset_node(ir_node *n, void *env) {
1268 set_irn_loop(n, NULL);
1273 /** Removes all loop information.
1274 Resets all backedges */
1275 void free_loop_information(ir_graph *irg) {
1276 /* We can not use this recursion, as the loop might contain
1277 illegal nodes by now. Why else would we throw away the
1279 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1281 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1282 set_irg_loop(irg, NULL);
1283 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1284 /* We cannot free the loop nodes, they are on the obstack. */
1288 void free_all_loop_information (void) {
1290 int rem = interprocedural_view;
1291 interprocedural_view = 1; /* To visit all filter nodes */
1292 for (i = 0; i < get_irp_n_irgs(); i++) {
1293 free_loop_information(get_irp_irg(i));
1295 pmap_destroy(node_loop_map);
1296 node_loop_map = NULL;
1297 interprocedural_view = rem;
1304 /* Debug stuff *************************************************/
1306 static int test_loop_node(ir_loop *l) {
1307 int i, has_node = 0, found_problem = 0;
1310 assert(l && l->kind == k_ir_loop);
1312 if (get_loop_n_elements(l) == 0) {
1313 printf(" Loop completely empty! "); DDML(l);
1315 dump_loop(l, "-ha");
1318 le = get_loop_element(l, 0);
1319 if (*(le.kind) != k_ir_node) {
1320 assert(le.kind && *(le.kind) == k_ir_loop);
1321 printf(" First loop element is not a node! "); DDML(l);
1322 printf(" "); DDML(le.son);
1325 dump_loop(l, "-ha");
1328 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1329 printf(" Wrong node as head! "); DDML(l);
1330 printf(" "); DDMN(le.node);
1332 dump_loop(l, "-ha");
1335 if ((get_loop_depth(l) != 0) &&
1336 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1337 printf(" Loop head has no backedges! "); DDML(l);
1338 printf(" "); DDMN(le.node);
1340 dump_loop(l, "-ha");
1345 for (i = 0; i < get_loop_n_elements(l); ++i) {
1346 le = get_loop_element(l, i);
1347 if (*(le.kind) == k_ir_node)
1350 if (test_loop_node(le.son)) found_problem = 1;
1353 if (has_node == 0) {
1354 printf(" Loop has no firm node! "); DDML(l);
1356 dump_loop(l, "-ha");
1359 if (get_loop_loop_nr(l) == 11819)
1360 dump_loop(l, "-ha-debug");
1362 return found_problem;
1365 /** Prints all loop nodes that
1366 * - do not have any firm nodes, only loop sons
1367 * - the header is not a Phi, Block or Filter.
1369 void find_strange_loop_nodes(ir_loop *l) {
1370 int found_problem = 0;
1371 printf("\nTesting loop "); DDML(l);
1372 found_problem = test_loop_node(l);
1373 printf("Finished Test\n\n");
1374 if (found_problem) exit(0);