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 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 printf(" here!!! \n");
848 for (i = -1; i < get_irn_arity(n); ++i) {
849 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
854 assert (res_index > -2);
856 set_backedge (m, res_index);
857 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
861 #if EXPERIMENTAL_LOOP_TREE
863 /* ----------------------------------------------------------------
864 AS: This is experimantal code to build loop trees suitable for
865 the heap analysis. Does not work correctly right now... :-(
868 Search in stack for the corresponding first Call-End-ProjX that
869 corresponds to one of the control flow predecessors of the given
870 block, that is the possible callers.
871 returns: the control predecessor to chose\
872 or -1 if no corresponding Call-End-Node could be found
874 - -------------------------------------------------------------- */
876 int search_endproj_in_stack(ir_node *start_block)
879 assert(is_Block(start_block));
880 for(i = tos - 1; i >= 0; --i)
883 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
884 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
886 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
887 ir_node *end_projx = stack[i];
889 for(j = 0; j < get_irn_arity(start_block); j++)
891 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
893 if(get_irn_n(start_block, j) == begin_projx)
895 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
905 static pmap *projx_link = NULL;
907 void link_to_reg_end (ir_node *n, void *env) {
908 if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
910 /* Reg End Projx -> Find the CallBegin Projx and hash it */
911 ir_node *end_projx = n;
912 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
913 printf("Linked the following ProjxNodes:\n");
916 set_projx_link(begin_projx, end_projx);
920 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
922 if(projx_link == NULL)
923 projx_link = pmap_create();
924 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
927 ir_node *get_projx_link(ir_node *cb_projx)
929 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
936 /*-----------------------------------------------------------*
937 * The core algorithm. *
938 *-----------------------------------------------------------*/
941 static void scc (ir_node *n) {
943 if (irn_visited(n)) return;
946 /* Initialize the node */
947 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
948 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
949 set_irn_loop(n, NULL);
953 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
954 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
955 so is_backedge does not access array[-1] but correctly returns false! */
957 if (!is_outermost_Start(n)) {
958 int arity = get_irn_arity(n);
960 #if EXPERIMENTAL_LOOP_TREE
962 /* This is meant to be used with the experimenatl code above.
963 If the above code is not used any more, this can be deleted, too.... */
965 if(interprocedural_view &&
967 get_irn_op(get_irn_n(n, 0)) == op_Proj &&
968 get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
970 /* We are at the start node of a function:
971 Walk to the callers in the correct order! */
973 DDMN(get_irn_n(get_irn_n(n, 0), 0));
974 for(i = 0; i < arity; i++)
979 pred_nr = search_endproj_in_stack(n);
980 assert(pred_nr >= 0);
981 if(is_backedge(n, pred_nr))
983 m = get_irn_n(n, pred_nr);
986 if (irn_is_in_stack(m)) {
987 /* Uplink of m is smaller if n->m is a backedge.
988 Propagate the uplink to mark the loop. */
989 if (get_irn_uplink(m) < get_irn_uplink(n))
990 set_irn_uplink(n, get_irn_uplink(m));
999 for (i = get_start_index(n); i < arity; i++) {
1001 if (is_backedge(n, i)) continue;
1002 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1003 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1005 if (irn_is_in_stack(m)) {
1006 /* Uplink of m is smaller if n->m is a backedge.
1007 Propagate the uplink to mark the loop. */
1008 if (get_irn_uplink(m) < get_irn_uplink(n))
1009 set_irn_uplink(n, get_irn_uplink(m));
1015 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1016 /* This condition holds for
1017 1) the node with the incoming backedge.
1018 That is: We found a loop!
1019 2) Straight line code, because no uplink has been propagated, so the
1020 uplink still is the same as the dfn.
1022 But n might not be a proper loop head for the analysis. Proper loop
1023 heads are Block and Phi nodes. find_tail searches the stack for
1024 Block's and Phi's and takes those nodes as loop heads for the current
1025 loop instead and marks the incoming edge as backedge. */
1027 ir_node *tail = find_tail(n);
1029 /* We have a loop, that is no straight line code,
1030 because we found a loop head!
1031 Next actions: Open a new loop on the loop tree and
1032 try to find inner loops */
1035 #define NO_LOOPS_WITHOUT_HEAD 1
1036 #if NO_LOOPS_WITHOUT_HEAD
1038 /* This is an adaption of the algorithm from fiasco / optscc to
1039 * avoid loops without Block or Phi as first node. This should
1040 * severely reduce the number of evaluations of nodes to detect
1041 * a fixpoint in the heap analysis.
1042 * Further it avoids loops without firm nodes that cause errors
1043 * in the heap analyses. */
1047 if (get_loop_n_elements(current_loop) > 0) {
1057 ir_loop *l = new_loop();
1061 /* Remove the loop from the stack ... */
1062 pop_scc_unmark_visit (n);
1064 /* GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1066 /* The current backedge has been marked, that is temporarily eliminated,
1067 by find tail. Start the scc algorithm
1068 anew on the subgraph thats left (the current loop without the backedge)
1069 in order to find more inner loops. */
1073 /* GL @@@ remove experimental stuff current_ir_graph = rem; */
1075 assert (irn_visited(n));
1076 #if NO_LOOPS_WITHOUT_HEAD
1083 /* AS: No loop head was found, that is we have straightline code.
1084 Pop all nodes from the stack to the current loop. */
1090 /* Constructs backedge information for irg. In interprocedural view constructs
1091 backedges for all methods called by irg, too. */
1092 void construct_backedges(ir_graph *irg) {
1093 ir_graph *rem = current_ir_graph;
1096 assert(!interprocedural_view &&
1097 "not implemented, use construct_ip_backedges");
1099 current_ir_graph = irg;
1100 outermost_ir_graph = irg;
1102 init_scc(current_ir_graph);
1104 current_loop = NULL;
1105 new_loop(); /* sets current_loop */
1106 head_rem = current_loop; /* Just for assertion */
1108 if (interprocedural_view) {
1109 set_irg_visited(current_ir_graph, inc_max_irg_visited());
1112 inc_irg_visited(current_ir_graph);
1115 scc(get_irg_end(current_ir_graph));
1117 if (interprocedural_view) finish_ip_walk();
1119 assert(head_rem == current_loop);
1120 set_irg_loop(current_ir_graph, current_loop);
1121 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1122 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1124 irg->loops = current_loop;
1128 count_loop (the_loop, &count, &depth);
1132 current_ir_graph = rem;
1137 void construct_ip_backedges (void) {
1138 ir_graph *rem = current_ir_graph;
1139 int rem_ipv = interprocedural_view;
1142 outermost_ir_graph = get_irp_main_irg();
1146 current_loop = NULL;
1147 new_loop(); /* sets current_loop */
1148 interprocedural_view = 1;
1150 inc_max_irg_visited();
1151 for (i = 0; i < get_irp_n_irgs(); i++)
1152 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1154 for (i = 0; i < get_irp_n_irgs(); i++) {
1156 current_ir_graph = get_irp_irg(i);
1157 /* Find real entry points */
1158 sb = get_irg_start_block(current_ir_graph);
1159 if ((get_Block_n_cfgpreds(sb) > 1) ||
1160 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1161 /* Compute scc for this graph */
1162 outermost_ir_graph = current_ir_graph;
1163 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1164 scc(get_irg_end(current_ir_graph));
1165 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1166 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1169 set_irg_loop(outermost_ir_graph, current_loop);
1170 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1171 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1173 current_ir_graph = rem;
1174 interprocedural_view = rem_ipv;
1177 void construct_ip_backedges (void) {
1178 ir_graph *rem = current_ir_graph;
1179 int rem_ipv = interprocedural_view;
1182 assert(get_irp_ip_view_state() == ip_view_valid);
1184 outermost_ir_graph = get_irp_main_irg();
1188 current_loop = NULL;
1189 new_loop(); /* sets current_loop */
1190 interprocedural_view = 1;
1192 inc_max_irg_visited();
1193 for (i = 0; i < get_irp_n_irgs(); i++)
1194 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1196 /** We have to start the walk at the same nodes as cg_walk. **/
1197 /* Walk starting at unreachable procedures. Only these
1198 * have End blocks visible in interprocedural view. */
1199 for (i = 0; i < get_irp_n_irgs(); i++) {
1201 current_ir_graph = get_irp_irg(i);
1203 sb = get_irg_start_block(current_ir_graph);
1205 if ((get_Block_n_cfgpreds(sb) > 1) ||
1206 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1208 scc(get_irg_end(current_ir_graph));
1211 /* Check whether we walked all procedures: there could be procedures
1212 with cyclic calls but no call from the outside. */
1213 for (i = 0; i < get_irp_n_irgs(); i++) {
1215 current_ir_graph = get_irp_irg(i);
1217 /* Test start block: if inner procedure end and end block are not
1218 * visible and therefore not marked. */
1219 sb = get_irg_start_block(current_ir_graph);
1220 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1223 /* Walk all endless loops in inner procedures.
1224 * We recognize an inner procedure if the End node is not visited. */
1225 for (i = 0; i < get_irp_n_irgs(); i++) {
1227 current_ir_graph = get_irp_irg(i);
1229 e = get_irg_end(current_ir_graph);
1230 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1232 /* Don't visit the End node. */
1233 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1237 set_irg_loop(outermost_ir_graph, current_loop);
1238 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1239 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1241 current_ir_graph = rem;
1242 interprocedural_view = rem_ipv;
1246 static void reset_backedges(ir_node *n) {
1247 if (is_possible_loop_head(n)) {
1248 int rem = interprocedural_view;
1249 interprocedural_view = 1;
1251 interprocedural_view = 0;
1253 interprocedural_view = rem;
1259 static void loop_reset_backedges(ir_loop *l) {
1261 reset_backedges(get_loop_node(l, 0));
1262 for (i = 0; i < get_loop_n_nodes(l); ++i)
1263 set_irn_loop(get_loop_node(l, i), NULL);
1264 for (i = 0; i < get_loop_n_sons(l); ++i) {
1265 loop_reset_backedges(get_loop_son(l, i));
1270 static void loop_reset_node(ir_node *n, void *env) {
1271 set_irn_loop(n, NULL);
1276 /** Removes all loop information.
1277 Resets all backedges */
1278 void free_loop_information(ir_graph *irg) {
1279 /* We can not use this recursion, as the loop might contain
1280 illegal nodes by now. Why else would we throw away the
1282 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1284 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1285 set_irg_loop(irg, NULL);
1286 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1287 /* We cannot free the loop nodes, they are on the obstack. */
1291 void free_all_loop_information (void) {
1293 int rem = interprocedural_view;
1294 interprocedural_view = 1; /* To visit all filter nodes */
1295 for (i = 0; i < get_irp_n_irgs(); i++) {
1296 free_loop_information(get_irp_irg(i));
1298 pmap_destroy(node_loop_map);
1299 node_loop_map = NULL;
1300 interprocedural_view = rem;
1307 /* Debug stuff *************************************************/
1309 static int test_loop_node(ir_loop *l) {
1310 int i, has_node = 0, found_problem = 0;
1313 assert(l && l->kind == k_ir_loop);
1315 if (get_loop_n_elements(l) == 0) {
1316 printf(" Loop completely empty! "); DDML(l);
1318 dump_loop(l, "-ha");
1321 le = get_loop_element(l, 0);
1322 if (*(le.kind) != k_ir_node) {
1323 assert(le.kind && *(le.kind) == k_ir_loop);
1324 printf(" First loop element is not a node! "); DDML(l);
1325 printf(" "); DDML(le.son);
1328 dump_loop(l, "-ha");
1331 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1332 printf(" Wrong node as head! "); DDML(l);
1333 printf(" "); DDMN(le.node);
1335 dump_loop(l, "-ha");
1338 if ((get_loop_depth(l) != 0) &&
1339 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1340 printf(" Loop head has no backedges! "); DDML(l);
1341 printf(" "); DDMN(le.node);
1343 dump_loop(l, "-ha");
1348 for (i = 0; i < get_loop_n_elements(l); ++i) {
1349 le = get_loop_element(l, i);
1350 if (*(le.kind) == k_ir_node)
1353 if (test_loop_node(le.son)) found_problem = 1;
1356 if (has_node == 0) {
1357 printf(" Loop has no firm node! "); DDML(l);
1359 dump_loop(l, "-ha");
1362 if (get_loop_loop_nr(l) == 11819)
1363 dump_loop(l, "-ha-debug");
1365 return found_problem;
1368 /** Prints all loop nodes that
1369 * - do not have any firm nodes, only loop sons
1370 * - the header is not a Phi, Block or Filter.
1372 void find_strange_loop_nodes(ir_loop *l) {
1373 int found_problem = 0;
1374 printf("\nTesting loop "); DDML(l);
1375 found_problem = test_loop_node(l);
1376 printf("Finished Test\n\n");
1377 if (found_problem) exit(0);