3 * File name: ir/ana/irscc.c
4 * Purpose: Compute the strongly connected regions and build
5 * backedge/loop datastructures.
6 * A variation on the Tarjan algorithm. See also [Trapp:99],
8 * Author: Goetz Lindenmaier
12 * Copyright: (c) 2002-2003 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
29 #include "irgraph_t.h"
37 /* A variant of the loop tree that avoids loops without head.
38 This reduces the depth of the loop tree. */
39 #define NO_LOOPS_WITHOUT_HEAD 1
42 INLINE void add_loop_son(ir_loop *loop, ir_loop *son);
44 INLINE void add_loop_node(ir_loop *loop, ir_node *n);
46 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
48 static ir_loop *current_loop; /* Current loop construction is working
50 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
51 Each loop node gets a unique number.
52 What for? ev. remove. @@@ */
53 static int current_dfn = 1; /* Counter to generate depth first numbering
56 static int max_loop_depth = 0;
58 void link_to_reg_end (ir_node *n, void *env);
59 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
60 ir_node *get_projx_link(ir_node *cb_projx);
62 /**********************************************************************/
63 /* Node attributes **/
64 /**********************************************************************/
66 /**********************************************************************/
67 /* Node attributes needed for the construction. **/
68 /**********************************************************************/
70 typedef struct scc_info {
71 bool in_stack; /* Marks whether node is on the stack. */
72 int dfn; /* Depth first search number. */
73 int uplink; /* dfn number of ancestor. */
74 /* ir_loop *loop; *//* Refers to the containing loop. */
76 struct section *section;
82 static INLINE scc_info* new_scc_info(void) {
83 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
84 memset (info, 0, sizeof (scc_info));
89 mark_irn_in_stack (ir_node *n) {
90 scc_info *scc = get_irn_link(n);
96 mark_irn_not_in_stack (ir_node *n) {
97 scc_info *scc = get_irn_link(n);
99 scc->in_stack = false;
103 irn_is_in_stack (ir_node *n) {
104 scc_info *scc = get_irn_link(n);
106 return scc->in_stack;
110 set_irn_uplink (ir_node *n, int uplink) {
111 scc_info *scc = get_irn_link(n);
113 scc->uplink = uplink;
117 get_irn_uplink (ir_node *n) {
118 scc_info *scc = get_irn_link(n);
124 set_irn_dfn (ir_node *n, int dfn) {
125 scc_info *scc = get_irn_link(n);
131 get_irn_dfn (ir_node *n) {
132 scc_info *scc = get_irn_link(n);
139 set_irn_loop (ir_node *n, ir_loop *loop) {
143 /* Uses temporary information to get the loop */
145 get_irn_loop (ir_node *n) {
151 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
155 /* Test whether n is contained in this loop. */
156 for (i = 0; i < get_loop_n_nodes(l); i++)
157 if (n == get_loop_node(l, i)) return l;
159 /* Is this a leave in the loop tree? If so loop not found. */
160 if (get_loop_n_sons(l) == 0) return NULL;
162 /* Else descend in the loop tree. */
163 for (i = 0; i < get_loop_n_sons(l); i++) {
164 res = find_nodes_loop(n, get_loop_son(l, i));
170 /* @@@ temporary implementation, costly!!! */
171 ir_loop * get_irn_loop(ir_node *n) {
172 ir_loop *l = get_irg_loop(current_ir_graph);
173 l = find_nodes_loop(n, l);
178 /**********************************************************************/
180 /**********************************************************************/
182 static ir_node **stack = NULL;
183 static int tos = 0; /* top of stack */
186 * initializes the stack
188 static INLINE void init_stack(void) {
190 ARR_RESIZE (ir_node *, stack, 1000);
192 stack = NEW_ARR_F (ir_node *, 1000);
198 static INLINE void free_stack(void) {
206 * push a node onto the stack
208 * @param n The node to push
215 if (tos == ARR_LEN (stack)) {
216 int nlen = ARR_LEN (stack) * 2;
217 ARR_RESIZE (ir_node *, stack, nlen);
220 mark_irn_in_stack(n);
224 * pop a node from the stack
226 * @return The topmost node
228 static INLINE ir_node *
231 ir_node *n = stack[--tos];
232 mark_irn_not_in_stack(n);
237 * The nodes up to n belong to the current loop.
238 * 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);
257 /* if (m==n) break;*/
260 /* i might be bigger than 1 for dead (and that's why bad) loops */
262 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
266 /* GL ??? my last son is my grandson??? Removes loops with no
267 ir_nodes in them. Such loops have only another loop as son. (Why
268 can't they have two loops as sons? Does it never get that far? ) */
269 static void close_loop (ir_loop *l)
271 int last = get_loop_n_elements(l) - 1;
272 loop_element lelement = get_loop_element(l, last);
273 ir_loop *last_son = lelement.son;
275 if (get_kind(last_son) == k_ir_loop &&
276 get_loop_n_elements(last_son) == 1) {
279 lelement = get_loop_element(last_son, 0);
282 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 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
329 } else { /* The root loop */
330 son->outer_loop = son;
335 son->loop_nr = get_irp_new_node_nr();
344 /* Finishes the datastructures, copies the arrays to the obstack
346 A. Schoesser: Caution: loop -> sons is gone. */
347 static void mature_loop (ir_loop *loop) {
350 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
351 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
352 DEL_ARR_F(loop->sons);
353 loop->sons = new_sons;
357 /* Returns outer loop, itself if outermost. */
358 ir_loop *get_loop_outer_loop (ir_loop *loop) {
359 assert(loop && loop->kind == k_ir_loop);
360 return loop->outer_loop;
363 /* Returns nesting depth of this loop */
364 int get_loop_depth (ir_loop *loop) {
365 assert(loop); assert(loop->kind == k_ir_loop);
369 /* Returns the number of inner loops */
370 int get_loop_n_sons (ir_loop *loop) {
371 assert(loop && loop->kind == k_ir_loop);
372 return(loop -> n_sons);
375 /* Returns the pos`th loop_node-child *
376 * TODO: This method isn`t very efficient ! *
377 * Returns NULL if there isnt`t a pos`th loop_node */
378 ir_loop *get_loop_son (ir_loop *loop, int pos) {
379 int child_nr = 0, loop_nr = -1;
381 assert(loop && loop->kind == k_ir_loop);
382 while(child_nr < ARR_LEN(loop->children))
384 if(*(loop -> children[child_nr].kind) == k_ir_loop)
387 return(loop -> children[child_nr].son);
393 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
397 add_loop_son(ir_loop *loop, ir_loop *son) {
400 assert(loop && loop->kind == k_ir_loop);
401 assert(get_kind(son) == k_ir_loop);
402 ARR_APP1 (loop_element, loop->children, lson);
406 /* Returns the number of nodes in the loop */
407 int get_loop_n_nodes (ir_loop *loop) {
408 assert(loop); assert(loop->kind == k_ir_loop);
409 return loop -> n_nodes;
410 /* return ARR_LEN(loop->nodes); */
413 /* Returns the pos`th ir_node-child *
414 * TODO: This method isn`t very efficient ! *
415 * Returns NULL if there isnt`t a pos`th ir_node */
416 ir_node *get_loop_node (ir_loop *loop, int pos) {
417 int child_nr, node_nr = -1;
419 assert(loop && loop->kind == k_ir_loop);
420 assert(pos < get_loop_n_nodes(loop));
422 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
423 if(*(loop -> children[child_nr].kind) == k_ir_node)
426 return(loop -> children[child_nr].node);
429 printf("pos: %d\n", pos);
430 assert(0 && "no child at pos found");
434 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
438 add_loop_node(ir_loop *loop, ir_node *n) {
441 assert(loop && loop->kind == k_ir_loop);
442 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
443 ARR_APP1 (loop_element, loop->children, ln);
447 /** Returns the number of elements contained in loop. */
448 int get_loop_n_elements (ir_loop *loop) {
449 assert(loop && loop->kind == k_ir_loop);
450 return(ARR_LEN(loop->children));
454 Returns the pos`th loop element.
455 This may be a loop_node or a ir_node. The caller of this function has
456 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
457 and then select the apropriate "loop_element.node" or "loop_element.son".
460 loop_element get_loop_element (ir_loop *loop, int pos) {
461 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
463 return(loop -> children[pos]);
466 int get_loop_element_pos(ir_loop *loop, void *le) {
468 assert(loop && loop->kind == k_ir_loop);
470 for (i = 0; i < get_loop_n_elements(loop); i++)
471 if (get_loop_element(loop, i).node == le) return i;
475 int get_loop_loop_nr(ir_loop *loop) {
476 assert(loop && loop->kind == k_ir_loop);
478 return loop->loop_nr;
485 /** A field to connect additional information to a loop. Only valid
486 if libfirm_debug is set. */
487 void set_loop_link (ir_loop *loop, void *link) {
488 assert(loop && loop->kind == k_ir_loop);
493 void *get_loop_link (const ir_loop *loop) {
494 assert(loop && loop->kind == k_ir_loop);
502 int is_ir_loop(const void *thing) {
503 return (get_kind(thing) == k_ir_loop);
506 /* The outermost loop is remarked in the surrounding graph. */
507 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
511 ir_loop *get_irg_loop(ir_graph *irg) {
517 /**********************************************************************/
518 /* Constructing and destructing the loop/backedge information. **/
519 /**********************************************************************/
521 /* Initialization steps. **********************************************/
524 init_node (ir_node *n, void *env) {
525 set_irn_link (n, new_scc_info());
530 init_scc_common (void) {
537 init_scc (ir_graph *irg) {
539 irg_walk_graph (irg, init_node, NULL, NULL);
541 irg_walk (irg, link_to_reg_end, NULL, NULL);
548 cg_walk (init_node, NULL, NULL);
550 #if EXPERIMENTAL_LOOP_TREE
551 cg_walk (link_to_reg_end, NULL, NULL);
555 /* Condition for breaking the recursion. */
556 static bool is_outermost_Start(ir_node *n) {
557 /* Test whether this is the outermost Start node. If so
558 recursion must end. */
559 if ((get_irn_op(n) == op_Block) &&
560 (get_Block_n_cfgpreds(n) == 1) &&
561 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
562 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
566 /* @@@ Bad condition:
567 not possible in interprocedural view as outermost_graph is
568 not necessarily the only with a dead-end start block.
569 Besides current_ir_graph is not set properly. */
570 if ((get_irn_op(n) == op_Block) &&
571 (n == get_irg_start_block(current_ir_graph))) {
572 if ((!get_interprocedural_view()) ||
573 (current_ir_graph == outermost_ir_graph))
580 /* When to walk from nodes to blocks. Only for Control flow operations? */
582 get_start_index(ir_node *n) {
583 #undef BLOCK_BEFORE_NODE
584 #define BLOCK_BEFORE_NODE 1
586 #if BLOCK_BEFORE_NODE
588 /* This version assures, that all nodes are ordered absolutely. This allows
589 to undef all nodes in the heap analysis if the block is false, which means
591 I.e., with this code, the order on the loop tree is correct. But a (single)
592 test showed the loop tree is deeper. */
593 if (get_irn_op(n) == op_Phi ||
594 get_irn_op(n) == op_Block ||
595 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
596 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
597 get_irn_pinned(n) == op_pin_state_floats))
598 // Here we could test for backedge at -1 which is illegal
605 /* This version causes deeper loop trees (at least we verified this
607 But it guarantees that Blocks are analysed before nodes contained in the
608 block. If so, we can set the value to undef if the block is not \
610 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
620 static void test(ir_node *pred, ir_node *root, ir_node *this) {
622 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
624 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
625 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
626 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
628 printf("tos: %d\n", tos);
630 for (i = tos; i >= 0; i--) {
631 ir_node *n = stack[i];
633 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
638 /* Test for legal loop header: Block, Phi, ... */
639 INLINE static bool is_possible_loop_head(ir_node *n) {
640 ir_op *op = get_irn_op(n);
641 return ((op == op_Block) ||
643 ((op == op_Filter) && get_interprocedural_view()));
646 /* Returns true if n is a loop header, i.e., it is a Block, Phi
647 or Filter node and has predecessors within the loop and out
649 @arg root: only needed for assertion. */
651 is_head (ir_node *n, ir_node *root)
654 int some_outof_loop = 0, some_in_loop = 0;
656 /* Test for legal loop header: Block, Phi, ... */
657 if (!is_possible_loop_head(n))
660 if (!is_outermost_Start(n)) {
661 arity = get_irn_arity(n);
662 for (i = get_start_index(n); i < arity; i++) {
663 ir_node *pred = get_irn_n(n, i);
665 if (is_backedge(n, i)) continue;
666 if (!irn_is_in_stack(pred)) {
669 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
670 DDMN(n); DDMN(pred); DDMN(root);
671 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
677 return some_outof_loop && some_in_loop;
680 /* Returns true if n is possible loop head of an endless loop.
681 I.e., it is a Block, Phi or Filter node and has only predecessors
683 @arg root: only needed for assertion. */
685 is_endless_head (ir_node *n, ir_node *root)
688 int some_outof_loop = 0, some_in_loop = 0;
690 /* Test for legal loop header: Block, Phi, ... */
691 if (!is_possible_loop_head(n))
694 if (!is_outermost_Start(n)) {
695 arity = get_irn_arity(n);
696 for (i = get_start_index(n); i < arity; i++) {
697 ir_node *pred = get_irn_n(n, i);
699 if (is_backedge(n, i)) { continue; }
700 if (!irn_is_in_stack(pred)) {
701 some_outof_loop = 1; //printf(" some out of loop ");
703 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
704 DDMN(pred); DDMN(root);
705 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
711 return !some_outof_loop && some_in_loop;
714 /* Returns index of the predecessor with the smallest dfn number
715 greater-equal than limit. */
717 smallest_dfn_pred (ir_node *n, int limit)
719 int i, index = -2, min = -1;
721 if (!is_outermost_Start(n)) {
722 int arity = get_irn_arity(n);
723 for (i = get_start_index(n); i < arity; i++) {
724 ir_node *pred = get_irn_n(n, i);
726 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
727 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
729 min = get_irn_dfn(pred);
736 /* Returns index of the predecessor with the largest dfn number. */
738 largest_dfn_pred (ir_node *n)
740 int i, index = -2, max = -1;
742 if (!is_outermost_Start(n)) {
743 int arity = get_irn_arity(n);
744 for (i = get_start_index(n); i < arity; i++) {
745 ir_node *pred = get_irn_n(n, i);
746 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
747 if (get_irn_dfn(pred) > max) {
749 max = get_irn_dfn(pred);
756 /** Searches the stack for possible loop heads. Tests these for backedges.
757 If it finds a head with an unmarked backedge it marks this edge and
758 returns the tail of the loop.
759 If it finds no backedge returns NULL.
760 ("disable_backedge" in fiasco)
762 * @param n A node where uplink == dfn.
766 find_tail (ir_node *n) {
768 int i, res_index = -2;
771 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
773 m = stack[tos-1]; /* tos = top of stack */
774 if (is_head (m, n)) {
775 res_index = smallest_dfn_pred(m, 0);
776 if ((res_index == -2) && /* no smallest dfn pred found. */
780 if (m == n) return NULL; // Is this to catch Phi - self loops?
781 for (i = tos-2; i >= 0; --i) {
784 if (is_head (m, n)) {
785 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
786 if (res_index == -2) /* no smallest dfn pred found. */
787 res_index = largest_dfn_pred (m);
789 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
795 /* We should not walk past our selves on the stack: The upcoming nodes
796 are not in this loop. We assume a loop not reachable from Start. */
805 /* A dead loop not reachable from Start. */
806 for (i = tos-2; i >= 0; --i) {
808 if (is_endless_head (m, n)) {
809 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
810 if (res_index == -2) /* no smallest dfn pred found. */
811 res_index = largest_dfn_pred (m);
814 if (m == n) { break; } /* It's not an unreachable loop, either. */
816 //assert(0 && "no head found on stack");
820 if (res_index <= -2) {
821 /* It's a completely bad loop: without Phi/Block nodes that can
822 be a head. I.e., the code is "dying". We break the loop by
823 setting Bad nodes. */
824 int arity = get_irn_arity(n);
825 for (i = -1; i < arity; ++i) {
826 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
830 assert (res_index > -2);
832 set_backedge (m, res_index);
833 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
837 #if EXPERIMENTAL_LOOP_TREE
839 /* ----------------------------------------------------------------
840 AS: This is experimantal code to build loop trees suitable for
841 the heap analysis. Does not work correctly right now... :-(
844 Search in stack for the corresponding first Call-End-ProjX that
845 corresponds to one of the control flow predecessors of the given
846 block, that is the possible callers.
847 returns: the control predecessor to chose\
848 or -1 if no corresponding Call-End-Node could be found
850 - -------------------------------------------------------------- */
852 int search_endproj_in_stack(ir_node *start_block)
855 assert(is_Block(start_block));
856 for(i = tos - 1; i >= 0; --i)
859 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
860 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
862 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
863 ir_node *end_projx = stack[i];
865 int arity = get_irn_arity(start_block);
866 for(j = 0; j < arity; j++)
868 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
869 get_Proj_proj(end_projx));
871 if(get_irn_n(start_block, j) == begin_projx)
873 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
883 static pmap *projx_link = NULL;
885 void link_to_reg_end (ir_node *n, void *env) {
886 if(get_irn_op(n) == op_Proj &&
887 get_irn_mode(n) == mode_X &&
888 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
889 /* Reg End Projx -> Find the CallBegin Projx and hash it */
890 ir_node *end_projx = n;
891 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
892 get_Proj_proj(end_projx));
893 printf("Linked the following ProjxNodes:\n");
896 set_projx_link(begin_projx, end_projx);
900 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
902 if(projx_link == NULL)
903 projx_link = pmap_create();
904 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
907 ir_node *get_projx_link(ir_node *cb_projx)
909 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
915 is_outermost_loop(ir_loop *l) {
916 return l == get_loop_outer_loop(l);
920 /*-----------------------------------------------------------*
921 * The core algorithm. *
922 *-----------------------------------------------------------*/
925 static void scc (ir_node *n) {
927 if (irn_visited(n)) return;
930 /* Initialize the node */
931 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
932 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
933 set_irn_loop(n, NULL);
937 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
938 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
939 so is_backedge does not access array[-1] but correctly returns false! */
941 if (!is_outermost_Start(n)) {
942 int arity = get_irn_arity(n);
944 for (i = get_start_index(n); i < arity; i++) {
946 if (is_backedge(n, i)) continue;
947 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
948 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
950 if (irn_is_in_stack(m)) {
951 /* Uplink of m is smaller if n->m is a backedge.
952 Propagate the uplink to mark the loop. */
953 if (get_irn_uplink(m) < get_irn_uplink(n))
954 set_irn_uplink(n, get_irn_uplink(m));
959 if (get_irn_dfn(n) == get_irn_uplink(n)) {
960 /* This condition holds for
961 1) the node with the incoming backedge.
962 That is: We found a loop!
963 2) Straight line code, because no uplink has been propagated, so the
964 uplink still is the same as the dfn.
966 But n might not be a proper loop head for the analysis. Proper loop
967 heads are Block and Phi nodes. find_tail searches the stack for
968 Block's and Phi's and takes those nodes as loop heads for the current
969 loop instead and marks the incoming edge as backedge. */
971 ir_node *tail = find_tail(n);
973 /* We have a loop, that is no straight line code,
974 because we found a loop head!
975 Next actions: Open a new loop on the loop tree and
976 try to find inner loops */
978 #if NO_LOOPS_WITHOUT_HEAD
979 /* This is an adaption of the algorithm from fiasco / optscc to
980 * avoid loops without Block or Phi as first node. This should
981 * severely reduce the number of evaluations of nodes to detect
982 * a fixpoint in the heap analysis.
983 * Further it avoids loops without firm nodes that cause errors
984 * in the heap analyses.
985 * But attention: don't do it for the outermost loop: This loop
986 * is not iterated. A first block can be a loop head in case of
987 * an endless recursion. */
991 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
999 ir_loop *l = new_loop();
1002 /* Remove the loop from the stack ... */
1003 pop_scc_unmark_visit (n);
1005 /* The current backedge has been marked, that is temporarily eliminated,
1006 by find tail. Start the scc algorithm
1007 anew on the subgraph thats left (the current loop without the backedge)
1008 in order to find more inner loops. */
1011 assert (irn_visited(n));
1012 #if NO_LOOPS_WITHOUT_HEAD
1019 /* No loop head was found, that is we have straightline code.
1020 Pop all nodes from the stack to the current loop. */
1026 static void my_scc (ir_node *n) {
1028 if (irn_visited(n)) return;
1029 mark_irn_visited(n);
1031 /* Initialize the node */
1032 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1033 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1034 set_irn_loop(n, NULL);
1038 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1039 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1040 so is_backedge does not access array[-1] but correctly returns false! */
1042 if (!is_outermost_Start(n)) {
1043 int arity = get_irn_arity(n);
1045 for (i = get_start_index(n); i < arity; i++) {
1047 if (is_backedge(n, i)) continue;
1048 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1049 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1051 if (irn_is_in_stack(m)) {
1052 /* Uplink of m is smaller if n->m is a backedge.
1053 Propagate the uplink to mark the loop. */
1054 if (get_irn_uplink(m) < get_irn_uplink(n))
1055 set_irn_uplink(n, get_irn_uplink(m));
1060 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1061 /* This condition holds for
1062 1) the node with the incoming backedge.
1063 That is: We found a loop!
1064 2) Straight line code, because no uplink has been propagated, so the
1065 uplink still is the same as the dfn.
1067 But n might not be a proper loop head for the analysis. Proper loop
1068 heads are Block and Phi nodes. find_tail searches the stack for
1069 Block's and Phi's and takes those nodes as loop heads for the current
1070 loop instead and marks the incoming edge as backedge. */
1072 ir_node *tail = find_tail(n);
1074 /* We have a loop, that is no straight line code,
1075 because we found a loop head!
1076 Next actions: Open a new loop on the loop tree and
1077 try to find inner loops */
1079 #if NO_LOOPS_WITHOUT_HEAD
1080 /* This is an adaption of the algorithm from fiasco / optscc to
1081 * avoid loops without Block or Phi as first node. This should
1082 * severely reduce the number of evaluations of nodes to detect
1083 * a fixpoint in the heap analysis.
1084 * Further it avoids loops without firm nodes that cause errors
1085 * in the heap analyses. */
1089 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1097 ir_loop *l = new_loop();
1100 /* Remove the loop from the stack ... */
1101 pop_scc_unmark_visit (n);
1103 /* The current backedge has been marked, that is temporarily eliminated,
1104 by find tail. Start the scc algorithm
1105 anew on the subgraph thats left (the current loop without the backedge)
1106 in order to find more inner loops. */
1109 assert (irn_visited(n));
1110 #if NO_LOOPS_WITHOUT_HEAD
1117 /* No loop head was found, that is we have straightline code.
1118 Pop all nodes from the stack to the current loop. */
1124 /* Constructs backedge information for irg. In interprocedural view constructs
1125 backedges for all methods called by irg, too. */
1126 int construct_backedges(ir_graph *irg) {
1127 ir_graph *rem = current_ir_graph;
1130 assert(!get_interprocedural_view() &&
1131 "not implemented, use construct_ip_backedges");
1134 current_ir_graph = irg;
1135 outermost_ir_graph = irg;
1137 init_scc(current_ir_graph);
1139 current_loop = NULL;
1140 new_loop(); /* sets current_loop */
1141 head_rem = current_loop; /* Just for assertion */
1143 inc_irg_visited(current_ir_graph);
1145 scc(get_irg_end(current_ir_graph));
1147 assert(head_rem == current_loop);
1148 set_irg_loop(current_ir_graph, current_loop);
1149 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1150 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1152 irg->loops = current_loop;
1156 count_loop (the_loop, &count, &depth);
1160 current_ir_graph = rem;
1162 return max_loop_depth;
1166 int construct_ip_backedges (void) {
1167 ir_graph *rem = current_ir_graph;
1168 int rem_ipv = get_interprocedural_view();
1172 assert(get_irp_ip_view_state() == ip_view_valid);
1174 outermost_ir_graph = get_irp_main_irg();
1178 current_loop = NULL;
1179 new_loop(); /* sets current_loop */
1180 set_interprocedural_view(true);
1182 inc_max_irg_visited();
1183 for (i = 0; i < get_irp_n_irgs(); i++)
1184 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1186 /** We have to start the walk at the same nodes as cg_walk. **/
1187 /* Walk starting at unreachable procedures. Only these
1188 * have End blocks visible in interprocedural view. */
1189 for (i = 0; i < get_irp_n_irgs(); i++) {
1191 current_ir_graph = get_irp_irg(i);
1193 sb = get_irg_start_block(current_ir_graph);
1195 if ((get_Block_n_cfgpreds(sb) > 1) ||
1196 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1198 scc(get_irg_end(current_ir_graph));
1201 /* Check whether we walked all procedures: there could be procedures
1202 with cyclic calls but no call from the outside. */
1203 for (i = 0; i < get_irp_n_irgs(); i++) {
1205 current_ir_graph = get_irp_irg(i);
1207 /* Test start block: if inner procedure end and end block are not
1208 * visible and therefore not marked. */
1209 sb = get_irg_start_block(current_ir_graph);
1210 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1213 /* Walk all endless loops in inner procedures.
1214 * We recognize an inner procedure if the End node is not visited. */
1215 for (i = 0; i < get_irp_n_irgs(); i++) {
1217 current_ir_graph = get_irp_irg(i);
1219 e = get_irg_end(current_ir_graph);
1220 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1222 /* Don't visit the End node. */
1223 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1227 set_irg_loop(outermost_ir_graph, current_loop);
1228 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1229 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1231 current_ir_graph = rem;
1232 set_interprocedural_view(rem_ipv);
1233 return max_loop_depth;
1236 void my_construct_ip_backedges (void) {
1237 ir_graph *rem = current_ir_graph;
1238 int rem_ipv = get_interprocedural_view();
1241 assert(get_irp_ip_view_state() == ip_view_valid);
1243 outermost_ir_graph = get_irp_main_irg();
1247 current_loop = NULL;
1248 new_loop(); /* sets current_loop */
1249 set_interprocedural_view(true);
1251 inc_max_irg_visited();
1252 for (i = 0; i < get_irp_n_irgs(); i++)
1253 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1255 /** We have to start the walk at the same nodes as cg_walk. **/
1256 /* Walk starting at unreachable procedures. Only these
1257 * have End blocks visible in interprocedural view. */
1258 for (i = 0; i < get_irp_n_irgs(); i++) {
1260 current_ir_graph = get_irp_irg(i);
1262 sb = get_irg_start_block(current_ir_graph);
1264 if ((get_Block_n_cfgpreds(sb) > 1) ||
1265 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1267 my_scc(get_irg_end(current_ir_graph));
1270 /* Check whether we walked all procedures: there could be procedures
1271 with cyclic calls but no call from the outside. */
1272 for (i = 0; i < get_irp_n_irgs(); i++) {
1274 current_ir_graph = get_irp_irg(i);
1276 /* Test start block: if inner procedure end and end block are not
1277 * visible and therefore not marked. */
1278 sb = get_irg_start_block(current_ir_graph);
1279 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1282 /* Walk all endless loops in inner procedures.
1283 * We recognize an inner procedure if the End node is not visited. */
1284 for (i = 0; i < get_irp_n_irgs(); i++) {
1286 current_ir_graph = get_irp_irg(i);
1288 e = get_irg_end(current_ir_graph);
1289 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1291 /* Don't visit the End node. */
1292 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1296 set_irg_loop(outermost_ir_graph, current_loop);
1297 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1298 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1300 current_ir_graph = rem;
1301 set_interprocedural_view(rem_ipv);
1304 static void reset_backedges(ir_node *n) {
1305 if (is_possible_loop_head(n)) {
1306 int rem = get_interprocedural_view();
1308 set_interprocedural_view(true);
1310 set_interprocedural_view(true);
1312 set_interprocedural_view(rem);
1318 static void loop_reset_backedges(ir_loop *l) {
1320 reset_backedges(get_loop_node(l, 0));
1321 for (i = 0; i < get_loop_n_nodes(l); ++i)
1322 set_irn_loop(get_loop_node(l, i), NULL);
1323 for (i = 0; i < get_loop_n_sons(l); ++i) {
1324 loop_reset_backedges(get_loop_son(l, i));
1329 static void loop_reset_node(ir_node *n, void *env) {
1330 set_irn_loop(n, NULL);
1335 /** Removes all loop information.
1336 Resets all backedges */
1337 void free_loop_information(ir_graph *irg) {
1338 /* We can not use this recursion, as the loop might contain
1339 illegal nodes by now. Why else would we throw away the
1341 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1343 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1344 set_irg_loop(irg, NULL);
1345 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1346 /* We cannot free the loop nodes, they are on the obstack. */
1350 void free_all_loop_information (void) {
1352 int rem = get_interprocedural_view();
1353 set_interprocedural_view(true); /* To visit all filter nodes */
1354 for (i = 0; i < get_irp_n_irgs(); i++) {
1355 free_loop_information(get_irp_irg(i));
1357 set_interprocedural_view(rem);
1364 /* Debug stuff *************************************************/
1366 static int test_loop_node(ir_loop *l) {
1367 int i, has_node = 0, found_problem = 0;
1370 assert(l && l->kind == k_ir_loop);
1372 if (get_loop_n_elements(l) == 0) {
1373 printf(" Loop completely empty! "); DDML(l);
1375 dump_loop(l, "-ha");
1378 le = get_loop_element(l, 0);
1379 if (*(le.kind) != k_ir_node) {
1380 assert(le.kind && *(le.kind) == k_ir_loop);
1381 printf(" First loop element is not a node! "); DDML(l);
1382 printf(" "); DDML(le.son);
1385 dump_loop(l, "-ha");
1388 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1389 printf(" Wrong node as head! "); DDML(l);
1390 printf(" "); DDMN(le.node);
1392 dump_loop(l, "-ha");
1395 if ((get_loop_depth(l) != 0) &&
1396 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1397 printf(" Loop head has no backedges! "); DDML(l);
1398 printf(" "); DDMN(le.node);
1400 dump_loop(l, "-ha");
1405 for (i = 0; i < get_loop_n_elements(l); ++i) {
1406 le = get_loop_element(l, i);
1407 if (*(le.kind) == k_ir_node)
1410 if (test_loop_node(le.son)) found_problem = 1;
1413 if (has_node == 0) {
1414 printf(" Loop has no firm node! "); DDML(l);
1416 dump_loop(l, "-ha");
1419 return found_problem;
1422 /** Prints all loop nodes that
1423 * - do not have any firm nodes, only loop sons
1424 * - the header is not a Phi, Block or Filter.
1426 void find_strange_loop_nodes(ir_loop *l) {
1427 int found_problem = 0;
1428 printf("\nTesting loop "); DDML(l);
1429 found_problem = test_loop_node(l);
1430 printf("Finished Test\n\n");
1431 if (found_problem) exit(0);
1435 /* ------------------------------------------------------------------- */
1436 /* Simple analyses based on the loop information */
1437 /* ------------------------------------------------------------------- */
1439 int is_loop_variant(ir_loop *l, ir_loop *b) {
1442 if (l == b) return true;
1444 n_elems = get_loop_n_elements(l);
1445 for (i = 0; i < n_elems; ++i) {
1446 loop_element e = get_loop_element(l, i);
1447 if (is_ir_loop(e.kind))
1448 if (is_loop_variant(e.son, b))
1455 /* Test whether a value is loop invariant.
1457 * @param n The node to be tested.
1458 * @param block A block node. We pass the block, not the loop as we must
1459 * start off with a block loop to find all proper uses.
1461 * Returns true, if the node n is not changed in the loop block
1462 * belongs to or in inner loops of this block. */
1463 int is_loop_invariant(ir_node *n, ir_node *block) {
1464 ir_loop *l = get_irn_loop(block);
1465 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1466 return !is_loop_variant(l, get_irn_loop(b));