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
41 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
43 static ir_loop *current_loop; /* Current loop construction is working
45 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
46 Each loop node gets a unique number.
47 What for? ev. remove. @@@ */
48 static int current_dfn = 1; /* Counter to generate depth first numbering
51 static int max_loop_depth = 0;
53 void link_to_reg_end (ir_node *n, void *env);
54 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
55 ir_node *get_projx_link(ir_node *cb_projx);
57 /**********************************************************************/
58 /* Node attributes **/
59 /**********************************************************************/
61 /**********************************************************************/
62 /* Node attributes needed for the construction. **/
63 /**********************************************************************/
65 typedef struct scc_info {
66 bool in_stack; /* Marks whether node is on the stack. */
67 int dfn; /* Depth first search number. */
68 int uplink; /* dfn number of ancestor. */
69 /* ir_loop *loop; *//* Refers to the containing loop. */
71 struct section *section;
77 static INLINE scc_info* new_scc_info(void) {
78 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
79 memset (info, 0, sizeof (scc_info));
84 mark_irn_in_stack (ir_node *n) {
85 scc_info *scc = get_irn_link(n);
91 mark_irn_not_in_stack (ir_node *n) {
92 scc_info *scc = get_irn_link(n);
94 scc->in_stack = false;
98 irn_is_in_stack (ir_node *n) {
99 scc_info *scc = get_irn_link(n);
101 return scc->in_stack;
105 set_irn_uplink (ir_node *n, int uplink) {
106 scc_info *scc = get_irn_link(n);
108 scc->uplink = uplink;
112 get_irn_uplink (ir_node *n) {
113 scc_info *scc = get_irn_link(n);
119 set_irn_dfn (ir_node *n, int dfn) {
120 scc_info *scc = get_irn_link(n);
126 get_irn_dfn (ir_node *n) {
127 scc_info *scc = get_irn_link(n);
134 set_irn_loop (ir_node *n, ir_loop *loop) {
138 /* Uses temporary information to get the loop */
140 get_irn_loop (ir_node *n) {
146 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
150 /* Test whether n is contained in this loop. */
151 for (i = 0; i < get_loop_n_nodes(l); i++)
152 if (n == get_loop_node(l, i)) return l;
154 /* Is this a leave in the loop tree? If so loop not found. */
155 if (get_loop_n_sons(l) == 0) return NULL;
157 /* Else descend in the loop tree. */
158 for (i = 0; i < get_loop_n_sons(l); i++) {
159 res = find_nodes_loop(n, get_loop_son(l, i));
165 /* @@@ temporary implementation, costly!!! */
166 ir_loop * get_irn_loop(ir_node *n) {
167 ir_loop *l = get_irg_loop(current_ir_graph);
168 l = find_nodes_loop(n, l);
173 /**********************************************************************/
175 /**********************************************************************/
177 static ir_node **stack = NULL;
178 static int tos = 0; /* top of stack */
181 * initializes the stack
183 static INLINE void init_stack(void) {
185 ARR_RESIZE (ir_node *, stack, 1000);
187 stack = NEW_ARR_F (ir_node *, 1000);
193 static INLINE void free_stack(void) {
201 * push a node onto the stack
203 * @param n The node to push
210 if (tos == ARR_LEN (stack)) {
211 int nlen = ARR_LEN (stack) * 2;
212 ARR_RESIZE (ir_node *, stack, nlen);
215 mark_irn_in_stack(n);
219 * pop a node from the stack
221 * @return The topmost node
223 static INLINE ir_node *
226 ir_node *n = stack[--tos];
227 mark_irn_not_in_stack(n);
232 * The nodes up to n belong to the current loop.
233 * Removes them from the stack and adds them to the current loop.
236 pop_scc_to_loop (ir_node *n)
244 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
247 set_irn_dfn(m, loop_node_cnt);
248 add_loop_node(current_loop, m);
249 set_irn_loop(m, current_loop);
252 /* if (m==n) break;*/
255 /* i might be bigger than 1 for dead (and that's why bad) loops */
257 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
261 /* GL ??? my last son is my grandson??? Removes loops with no
262 ir_nodes in them. Such loops have only another loop as son. (Why
263 can't they have two loops as sons? Does it never get that far? ) */
264 static void close_loop (ir_loop *l)
266 int last = get_loop_n_elements(l) - 1;
267 loop_element lelement = get_loop_element(l, last);
268 ir_loop *last_son = lelement.son;
270 if (get_kind(last_son) == k_ir_loop &&
271 get_loop_n_elements(last_son) == 1) {
274 lelement = get_loop_element(last_son, 0);
277 if (get_kind(gson) == k_ir_loop) {
278 loop_element new_last_son;
280 gson->outer_loop = l;
281 new_last_son.son = gson;
282 l->children[last] = new_last_son;
289 /* Removes and unmarks all nodes up to n from the stack.
290 The nodes must be visited once more to assign them to a scc. */
292 pop_scc_unmark_visit (ir_node *n)
298 set_irn_visited(m, 0);
302 /**********************************************************************/
303 /* The loop datastructure. **/
304 /**********************************************************************/
306 /* Allocates a new loop as son of current_loop. Sets current_loop
307 to the new loop and returns the father. */
308 ir_loop *new_loop (void) {
309 ir_loop *father, *son;
311 father = current_loop;
313 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
314 memset (son, 0, sizeof (ir_loop));
315 son->kind = k_ir_loop;
316 son->children = NEW_ARR_F (loop_element, 0);
320 son->outer_loop = father;
321 add_loop_son(father, son);
322 son->depth = father->depth+1;
323 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
324 } else { /* The root loop */
325 son->outer_loop = son;
330 son->loop_nr = get_irp_new_node_nr();
339 /* Finishes the datastructures, copies the arrays to the obstack
341 A. Schoesser: Caution: loop -> sons is gone. */
342 static void mature_loop (ir_loop *loop) {
345 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
346 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
347 DEL_ARR_F(loop->sons);
348 loop->sons = new_sons;
352 /* Returns outer loop, itself if outermost. */
353 ir_loop *get_loop_outer_loop (ir_loop *loop) {
354 assert(loop && loop->kind == k_ir_loop);
355 return loop->outer_loop;
358 /* Returns nesting depth of this loop */
359 int get_loop_depth (ir_loop *loop) {
360 assert(loop); assert(loop->kind == k_ir_loop);
364 /* Returns the number of inner loops */
365 int get_loop_n_sons (ir_loop *loop) {
366 assert(loop && loop->kind == k_ir_loop);
367 return(loop -> n_sons);
370 /* Returns the pos`th loop_node-child *
371 * TODO: This method isn`t very efficient ! *
372 * Returns NULL if there isnt`t a pos`th loop_node */
373 ir_loop *get_loop_son (ir_loop *loop, int pos) {
374 int child_nr = 0, loop_nr = -1;
376 assert(loop && loop->kind == k_ir_loop);
377 while(child_nr < ARR_LEN(loop->children))
379 if(*(loop -> children[child_nr].kind) == k_ir_loop)
382 return(loop -> children[child_nr].son);
388 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
392 add_loop_son(ir_loop *loop, ir_loop *son) {
395 assert(loop && loop->kind == k_ir_loop);
396 assert(get_kind(son) == k_ir_loop);
397 ARR_APP1 (loop_element, loop->children, lson);
401 /* Returns the number of nodes in the loop */
402 int get_loop_n_nodes (ir_loop *loop) {
403 assert(loop); assert(loop->kind == k_ir_loop);
404 return loop -> n_nodes;
405 /* return ARR_LEN(loop->nodes); */
408 /* Returns the pos`th ir_node-child *
409 * TODO: This method isn`t very efficient ! *
410 * Returns NULL if there isnt`t a pos`th ir_node */
411 ir_node *get_loop_node (ir_loop *loop, int pos) {
412 int child_nr, node_nr = -1;
414 assert(loop && loop->kind == k_ir_loop);
415 assert(pos < get_loop_n_nodes(loop));
417 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
418 if(*(loop -> children[child_nr].kind) == k_ir_node)
421 return(loop -> children[child_nr].node);
424 printf("pos: %d\n", pos);
425 assert(0 && "no child at pos found");
429 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
433 add_loop_node(ir_loop *loop, ir_node *n) {
436 assert(loop && loop->kind == k_ir_loop);
437 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
438 ARR_APP1 (loop_element, loop->children, ln);
442 /** Returns the number of elements contained in loop. */
443 int get_loop_n_elements (ir_loop *loop) {
444 assert(loop && loop->kind == k_ir_loop);
445 return(ARR_LEN(loop->children));
449 Returns the pos`th loop element.
450 This may be a loop_node or a ir_node. The caller of this function has
451 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
452 and then select the apropriate "loop_element.node" or "loop_element.son".
455 loop_element get_loop_element (ir_loop *loop, int pos) {
456 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
458 return(loop -> children[pos]);
461 int get_loop_element_pos(ir_loop *loop, void *le) {
463 assert(loop && loop->kind == k_ir_loop);
465 for (i = 0; i < get_loop_n_elements(loop); i++)
466 if (get_loop_element(loop, i).node == le) return i;
470 int get_loop_loop_nr(ir_loop *loop) {
471 assert(loop && loop->kind == k_ir_loop);
473 return loop->loop_nr;
480 /** A field to connect additional information to a loop. Only valid
481 if libfirm_debug is set. */
482 void set_loop_link (ir_loop *loop, void *link) {
483 assert(loop && loop->kind == k_ir_loop);
488 void *get_loop_link (const ir_loop *loop) {
489 assert(loop && loop->kind == k_ir_loop);
497 int is_ir_loop(const void *thing) {
498 return (get_kind(thing) == 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());
525 init_scc_common (void) {
532 init_scc (ir_graph *irg) {
534 irg_walk_graph (irg, init_node, NULL, NULL);
536 irg_walk (irg, link_to_reg_end, NULL, NULL);
543 cg_walk (init_node, NULL, NULL);
545 #if EXPERIMENTAL_LOOP_TREE
546 cg_walk (link_to_reg_end, NULL, NULL);
550 /* Condition for breaking the recursion. */
551 static bool is_outermost_Start(ir_node *n) {
552 /* Test whether this is the outermost Start node. If so
553 recursion must end. */
554 if ((get_irn_op(n) == op_Block) &&
555 (get_Block_n_cfgpreds(n) == 1) &&
556 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
557 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
561 /* @@@ Bad condition:
562 not possible in interprocedural view as outermost_graph is
563 not necessarily the only with a dead-end start block.
564 Besides current_ir_graph is not set properly. */
565 if ((get_irn_op(n) == op_Block) &&
566 (n == get_irg_start_block(current_ir_graph))) {
567 if ((!get_interprocedural_view()) ||
568 (current_ir_graph == outermost_ir_graph))
575 /* When to walk from nodes to blocks. Only for Control flow operations? */
577 get_start_index(ir_node *n) {
578 #undef BLOCK_BEFORE_NODE
579 #define BLOCK_BEFORE_NODE 1
581 #if BLOCK_BEFORE_NODE
583 /* This version assures, that all nodes are ordered absolutely. This allows
584 to undef all nodes in the heap analysis if the block is false, which means
586 I.e., with this code, the order on the loop tree is correct. But a (single)
587 test showed the loop tree is deeper. */
588 if (get_irn_op(n) == op_Phi ||
589 get_irn_op(n) == op_Block ||
590 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
591 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
592 get_irn_pinned(n) == op_pin_state_floats))
593 // Here we could test for backedge at -1 which is illegal
600 /* This version causes deeper loop trees (at least we verified this
602 But it guarantees that Blocks are analysed before nodes contained in the
603 block. If so, we can set the value to undef if the block is not \
605 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
615 static void test(ir_node *pred, ir_node *root, ir_node *this) {
617 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
619 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
620 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
621 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
623 printf("tos: %d\n", tos);
625 for (i = tos; i >= 0; i--) {
626 ir_node *n = stack[i];
628 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
633 /* Test for legal loop header: Block, Phi, ... */
634 static INLINE bool is_possible_loop_head(ir_node *n) {
635 ir_op *op = get_irn_op(n);
636 return ((op == op_Block) ||
638 ((op == op_Filter) && get_interprocedural_view()));
641 /* Returns true if n is a loop header, i.e., it is a Block, Phi
642 or Filter node and has predecessors within the loop and out
644 @arg root: only needed for assertion. */
646 is_head (ir_node *n, ir_node *root)
649 int some_outof_loop = 0, some_in_loop = 0;
651 /* Test for legal loop header: Block, Phi, ... */
652 if (!is_possible_loop_head(n))
655 if (!is_outermost_Start(n)) {
656 arity = get_irn_arity(n);
657 for (i = get_start_index(n); i < arity; i++) {
658 ir_node *pred = get_irn_n(n, i);
660 if (is_backedge(n, i)) continue;
661 if (!irn_is_in_stack(pred)) {
664 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
665 DDMN(n); DDMN(pred); DDMN(root);
666 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
672 return some_outof_loop && some_in_loop;
675 /* Returns true if n is possible loop head of an endless loop.
676 I.e., it is a Block, Phi or Filter node and has only predecessors
678 @arg root: only needed for assertion. */
680 is_endless_head (ir_node *n, ir_node *root)
683 int some_outof_loop = 0, some_in_loop = 0;
685 /* Test for legal loop header: Block, Phi, ... */
686 if (!is_possible_loop_head(n))
689 if (!is_outermost_Start(n)) {
690 arity = get_irn_arity(n);
691 for (i = get_start_index(n); i < arity; i++) {
692 ir_node *pred = get_irn_n(n, i);
694 if (is_backedge(n, i)) { continue; }
695 if (!irn_is_in_stack(pred)) {
696 some_outof_loop = 1; //printf(" some out of loop ");
698 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
699 DDMN(pred); DDMN(root);
700 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
706 return !some_outof_loop && some_in_loop;
709 /* Returns index of the predecessor with the smallest dfn number
710 greater-equal than limit. */
712 smallest_dfn_pred (ir_node *n, int limit)
714 int i, index = -2, min = -1;
716 if (!is_outermost_Start(n)) {
717 int 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) || !irn_is_in_stack(pred)) continue;
722 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
724 min = get_irn_dfn(pred);
731 /* Returns index of the predecessor with the largest dfn number. */
733 largest_dfn_pred (ir_node *n)
735 int i, index = -2, max = -1;
737 if (!is_outermost_Start(n)) {
738 int arity = get_irn_arity(n);
739 for (i = get_start_index(n); i < arity; i++) {
740 ir_node *pred = get_irn_n(n, i);
741 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
742 if (get_irn_dfn(pred) > max) {
744 max = get_irn_dfn(pred);
751 /** Searches the stack for possible loop heads. Tests these for backedges.
752 If it finds a head with an unmarked backedge it marks this edge and
753 returns the tail of the loop.
754 If it finds no backedge returns NULL.
755 ("disable_backedge" in fiasco)
757 * @param n A node where uplink == dfn.
761 find_tail (ir_node *n) {
763 int i, res_index = -2;
766 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
768 m = stack[tos-1]; /* tos = top of stack */
769 if (is_head (m, n)) {
770 res_index = smallest_dfn_pred(m, 0);
771 if ((res_index == -2) && /* no smallest dfn pred found. */
775 if (m == n) return NULL; // Is this to catch Phi - self loops?
776 for (i = tos-2; i >= 0; --i) {
779 if (is_head (m, n)) {
780 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
781 if (res_index == -2) /* no smallest dfn pred found. */
782 res_index = largest_dfn_pred (m);
784 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
790 /* We should not walk past our selves on the stack: The upcoming nodes
791 are not in this loop. We assume a loop not reachable from Start. */
800 /* A dead loop not reachable from Start. */
801 for (i = tos-2; i >= 0; --i) {
803 if (is_endless_head (m, n)) {
804 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
805 if (res_index == -2) /* no smallest dfn pred found. */
806 res_index = largest_dfn_pred (m);
809 if (m == n) { break; } /* It's not an unreachable loop, either. */
811 //assert(0 && "no head found on stack");
815 if (res_index <= -2) {
816 /* It's a completely bad loop: without Phi/Block nodes that can
817 be a head. I.e., the code is "dying". We break the loop by
818 setting Bad nodes. */
819 int arity = get_irn_arity(n);
820 for (i = -1; i < arity; ++i) {
821 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
825 assert (res_index > -2);
827 set_backedge (m, res_index);
828 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
832 #if EXPERIMENTAL_LOOP_TREE
834 /* ----------------------------------------------------------------
835 AS: This is experimantal code to build loop trees suitable for
836 the heap analysis. Does not work correctly right now... :-(
839 Search in stack for the corresponding first Call-End-ProjX that
840 corresponds to one of the control flow predecessors of the given
841 block, that is the possible callers.
842 returns: the control predecessor to chose\
843 or -1 if no corresponding Call-End-Node could be found
845 - -------------------------------------------------------------- */
847 int search_endproj_in_stack(ir_node *start_block)
850 assert(is_Block(start_block));
851 for(i = tos - 1; i >= 0; --i)
854 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
855 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
857 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
858 ir_node *end_projx = stack[i];
860 int arity = get_irn_arity(start_block);
861 for(j = 0; j < arity; j++)
863 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
864 get_Proj_proj(end_projx));
866 if(get_irn_n(start_block, j) == begin_projx)
868 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
878 static pmap *projx_link = NULL;
880 void link_to_reg_end (ir_node *n, void *env) {
881 if(get_irn_op(n) == op_Proj &&
882 get_irn_mode(n) == mode_X &&
883 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
884 /* Reg End Projx -> Find the CallBegin Projx and hash it */
885 ir_node *end_projx = n;
886 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
887 get_Proj_proj(end_projx));
888 printf("Linked the following ProjxNodes:\n");
891 set_projx_link(begin_projx, end_projx);
895 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
897 if(projx_link == NULL)
898 projx_link = pmap_create();
899 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
902 ir_node *get_projx_link(ir_node *cb_projx)
904 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
910 is_outermost_loop(ir_loop *l) {
911 return l == get_loop_outer_loop(l);
915 /*-----------------------------------------------------------*
916 * The core algorithm. *
917 *-----------------------------------------------------------*/
920 static void scc (ir_node *n) {
922 if (irn_visited(n)) return;
925 /* Initialize the node */
926 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
927 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
928 set_irn_loop(n, NULL);
932 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
933 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
934 so is_backedge does not access array[-1] but correctly returns false! */
936 if (!is_outermost_Start(n)) {
937 int arity = get_irn_arity(n);
939 for (i = get_start_index(n); i < arity; i++) {
941 if (is_backedge(n, i)) continue;
942 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
943 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
945 if (irn_is_in_stack(m)) {
946 /* Uplink of m is smaller if n->m is a backedge.
947 Propagate the uplink to mark the loop. */
948 if (get_irn_uplink(m) < get_irn_uplink(n))
949 set_irn_uplink(n, get_irn_uplink(m));
954 if (get_irn_dfn(n) == get_irn_uplink(n)) {
955 /* This condition holds for
956 1) the node with the incoming backedge.
957 That is: We found a loop!
958 2) Straight line code, because no uplink has been propagated, so the
959 uplink still is the same as the dfn.
961 But n might not be a proper loop head for the analysis. Proper loop
962 heads are Block and Phi nodes. find_tail searches the stack for
963 Block's and Phi's and takes those nodes as loop heads for the current
964 loop instead and marks the incoming edge as backedge. */
966 ir_node *tail = find_tail(n);
968 /* We have a loop, that is no straight line code,
969 because we found a loop head!
970 Next actions: Open a new loop on the loop tree and
971 try to find inner loops */
973 #if NO_LOOPS_WITHOUT_HEAD
974 /* This is an adaption of the algorithm from fiasco / optscc to
975 * avoid loops without Block or Phi as first node. This should
976 * severely reduce the number of evaluations of nodes to detect
977 * a fixpoint in the heap analysis.
978 * Further it avoids loops without firm nodes that cause errors
979 * in the heap analyses.
980 * But attention: don't do it for the outermost loop: This loop
981 * is not iterated. A first block can be a loop head in case of
982 * an endless recursion. */
986 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
994 ir_loop *l = new_loop();
997 /* Remove the loop from the stack ... */
998 pop_scc_unmark_visit (n);
1000 /* The current backedge has been marked, that is temporarily eliminated,
1001 by find tail. Start the scc algorithm
1002 anew on the subgraph that is left (the current loop without the backedge)
1003 in order to find more inner loops. */
1006 assert (irn_visited(n));
1007 #if NO_LOOPS_WITHOUT_HEAD
1014 /* No loop head was found, that is we have straightline code.
1015 Pop all nodes from the stack to the current loop. */
1021 static void my_scc (ir_node *n) {
1023 if (irn_visited(n)) return;
1024 mark_irn_visited(n);
1026 /* Initialize the node */
1027 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1028 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1029 set_irn_loop(n, NULL);
1033 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1034 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1035 so is_backedge does not access array[-1] but correctly returns false! */
1037 if (!is_outermost_Start(n)) {
1038 int arity = get_irn_arity(n);
1040 for (i = get_start_index(n); i < arity; i++) {
1042 if (is_backedge(n, i)) continue;
1043 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1044 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1046 if (irn_is_in_stack(m)) {
1047 /* Uplink of m is smaller if n->m is a backedge.
1048 Propagate the uplink to mark the loop. */
1049 if (get_irn_uplink(m) < get_irn_uplink(n))
1050 set_irn_uplink(n, get_irn_uplink(m));
1055 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1056 /* This condition holds for
1057 1) the node with the incoming backedge.
1058 That is: We found a loop!
1059 2) Straight line code, because no uplink has been propagated, so the
1060 uplink still is the same as the dfn.
1062 But n might not be a proper loop head for the analysis. Proper loop
1063 heads are Block and Phi nodes. find_tail searches the stack for
1064 Block's and Phi's and takes those nodes as loop heads for the current
1065 loop instead and marks the incoming edge as backedge. */
1067 ir_node *tail = find_tail(n);
1069 /* We have a loop, that is no straight line code,
1070 because we found a loop head!
1071 Next actions: Open a new loop on the loop tree and
1072 try to find inner loops */
1074 #if NO_LOOPS_WITHOUT_HEAD
1075 /* This is an adaption of the algorithm from fiasco / optscc to
1076 * avoid loops without Block or Phi as first node. This should
1077 * severely reduce the number of evaluations of nodes to detect
1078 * a fixpoint in the heap analysis.
1079 * Further it avoids loops without firm nodes that cause errors
1080 * in the heap analyses. */
1084 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1092 ir_loop *l = new_loop();
1095 /* Remove the loop from the stack ... */
1096 pop_scc_unmark_visit (n);
1098 /* The current backedge has been marked, that is temporarily eliminated,
1099 by find tail. Start the scc algorithm
1100 anew on the subgraph that is left (the current loop without the backedge)
1101 in order to find more inner loops. */
1104 assert (irn_visited(n));
1105 #if NO_LOOPS_WITHOUT_HEAD
1112 /* No loop head was found, that is we have straightline code.
1113 Pop all nodes from the stack to the current loop. */
1119 /* Constructs backedge information for irg. In interprocedural view constructs
1120 backedges for all methods called by irg, too. */
1121 int construct_backedges(ir_graph *irg) {
1122 ir_graph *rem = current_ir_graph;
1125 assert(!get_interprocedural_view() &&
1126 "not implemented, use construct_ip_backedges");
1129 current_ir_graph = irg;
1130 outermost_ir_graph = irg;
1132 init_scc(current_ir_graph);
1134 current_loop = NULL;
1135 new_loop(); /* sets current_loop */
1136 head_rem = current_loop; /* Just for assertion */
1138 inc_irg_visited(current_ir_graph);
1140 scc(get_irg_end(current_ir_graph));
1142 assert(head_rem == current_loop);
1143 set_irg_loop(current_ir_graph, current_loop);
1144 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1145 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1147 irg->loops = current_loop;
1151 count_loop (the_loop, &count, &depth);
1155 current_ir_graph = rem;
1157 return max_loop_depth;
1161 int construct_ip_backedges (void) {
1162 ir_graph *rem = current_ir_graph;
1163 int rem_ipv = get_interprocedural_view();
1167 assert(get_irp_ip_view_state() == ip_view_valid);
1169 outermost_ir_graph = get_irp_main_irg();
1173 current_loop = NULL;
1174 new_loop(); /* sets current_loop */
1175 set_interprocedural_view(true);
1177 inc_max_irg_visited();
1178 for (i = 0; i < get_irp_n_irgs(); i++)
1179 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1181 /** We have to start the walk at the same nodes as cg_walk. **/
1182 /* Walk starting at unreachable procedures. Only these
1183 * have End blocks visible in interprocedural view. */
1184 for (i = 0; i < get_irp_n_irgs(); i++) {
1186 current_ir_graph = get_irp_irg(i);
1188 sb = get_irg_start_block(current_ir_graph);
1190 if ((get_Block_n_cfgpreds(sb) > 1) ||
1191 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1193 scc(get_irg_end(current_ir_graph));
1196 /* Check whether we walked all procedures: there could be procedures
1197 with cyclic calls but no call from the outside. */
1198 for (i = 0; i < get_irp_n_irgs(); i++) {
1200 current_ir_graph = get_irp_irg(i);
1202 /* Test start block: if inner procedure end and end block are not
1203 * visible and therefore not marked. */
1204 sb = get_irg_start_block(current_ir_graph);
1205 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1208 /* Walk all endless loops in inner procedures.
1209 * We recognize an inner procedure if the End node is not visited. */
1210 for (i = 0; i < get_irp_n_irgs(); i++) {
1212 current_ir_graph = get_irp_irg(i);
1214 e = get_irg_end(current_ir_graph);
1215 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1217 /* Don't visit the End node. */
1218 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1222 set_irg_loop(outermost_ir_graph, current_loop);
1223 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1224 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1226 current_ir_graph = rem;
1227 set_interprocedural_view(rem_ipv);
1228 return max_loop_depth;
1231 void my_construct_ip_backedges (void) {
1232 ir_graph *rem = current_ir_graph;
1233 int rem_ipv = get_interprocedural_view();
1236 assert(get_irp_ip_view_state() == ip_view_valid);
1238 outermost_ir_graph = get_irp_main_irg();
1242 current_loop = NULL;
1243 new_loop(); /* sets current_loop */
1244 set_interprocedural_view(true);
1246 inc_max_irg_visited();
1247 for (i = 0; i < get_irp_n_irgs(); i++)
1248 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1250 /** We have to start the walk at the same nodes as cg_walk. **/
1251 /* Walk starting at unreachable procedures. Only these
1252 * have End blocks visible in interprocedural view. */
1253 for (i = 0; i < get_irp_n_irgs(); i++) {
1255 current_ir_graph = get_irp_irg(i);
1257 sb = get_irg_start_block(current_ir_graph);
1259 if ((get_Block_n_cfgpreds(sb) > 1) ||
1260 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1262 my_scc(get_irg_end(current_ir_graph));
1265 /* Check whether we walked all procedures: there could be procedures
1266 with cyclic calls but no call from the outside. */
1267 for (i = 0; i < get_irp_n_irgs(); i++) {
1269 current_ir_graph = get_irp_irg(i);
1271 /* Test start block: if inner procedure end and end block are not
1272 * visible and therefore not marked. */
1273 sb = get_irg_start_block(current_ir_graph);
1274 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1277 /* Walk all endless loops in inner procedures.
1278 * We recognize an inner procedure if the End node is not visited. */
1279 for (i = 0; i < get_irp_n_irgs(); i++) {
1281 current_ir_graph = get_irp_irg(i);
1283 e = get_irg_end(current_ir_graph);
1284 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1286 /* Don't visit the End node. */
1287 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1291 set_irg_loop(outermost_ir_graph, current_loop);
1292 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1293 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1295 current_ir_graph = rem;
1296 set_interprocedural_view(rem_ipv);
1299 static void reset_backedges(ir_node *n) {
1300 if (is_possible_loop_head(n)) {
1301 int rem = get_interprocedural_view();
1303 set_interprocedural_view(true);
1305 set_interprocedural_view(true);
1307 set_interprocedural_view(rem);
1313 static void loop_reset_backedges(ir_loop *l) {
1315 reset_backedges(get_loop_node(l, 0));
1316 for (i = 0; i < get_loop_n_nodes(l); ++i)
1317 set_irn_loop(get_loop_node(l, i), NULL);
1318 for (i = 0; i < get_loop_n_sons(l); ++i) {
1319 loop_reset_backedges(get_loop_son(l, i));
1324 static void loop_reset_node(ir_node *n, void *env) {
1325 set_irn_loop(n, NULL);
1330 /** Removes all loop information.
1331 Resets all backedges */
1332 void free_loop_information(ir_graph *irg) {
1333 /* We can not use this recursion, as the loop might contain
1334 illegal nodes by now. Why else would we throw away the
1336 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1338 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1339 set_irg_loop(irg, NULL);
1340 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1341 /* We cannot free the loop nodes, they are on the obstack. */
1345 void free_all_loop_information (void) {
1347 int rem = get_interprocedural_view();
1348 set_interprocedural_view(true); /* To visit all filter nodes */
1349 for (i = 0; i < get_irp_n_irgs(); i++) {
1350 free_loop_information(get_irp_irg(i));
1352 set_interprocedural_view(rem);
1359 /* Debug stuff *************************************************/
1361 static int test_loop_node(ir_loop *l) {
1362 int i, has_node = 0, found_problem = 0;
1365 assert(l && l->kind == k_ir_loop);
1367 if (get_loop_n_elements(l) == 0) {
1368 printf(" Loop completely empty! "); DDML(l);
1370 dump_loop(l, "-ha");
1373 le = get_loop_element(l, 0);
1374 if (*(le.kind) != k_ir_node) {
1375 assert(le.kind && *(le.kind) == k_ir_loop);
1376 printf(" First loop element is not a node! "); DDML(l);
1377 printf(" "); DDML(le.son);
1380 dump_loop(l, "-ha");
1383 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1384 printf(" Wrong node as head! "); DDML(l);
1385 printf(" "); DDMN(le.node);
1387 dump_loop(l, "-ha");
1390 if ((get_loop_depth(l) != 0) &&
1391 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1392 printf(" Loop head has no backedges! "); DDML(l);
1393 printf(" "); DDMN(le.node);
1395 dump_loop(l, "-ha");
1400 for (i = 0; i < get_loop_n_elements(l); ++i) {
1401 le = get_loop_element(l, i);
1402 if (*(le.kind) == k_ir_node)
1405 if (test_loop_node(le.son)) found_problem = 1;
1408 if (has_node == 0) {
1409 printf(" Loop has no firm node! "); DDML(l);
1411 dump_loop(l, "-ha");
1414 return found_problem;
1417 /** Prints all loop nodes that
1418 * - do not have any firm nodes, only loop sons
1419 * - the header is not a Phi, Block or Filter.
1421 void find_strange_loop_nodes(ir_loop *l) {
1422 int found_problem = 0;
1423 printf("\nTesting loop "); DDML(l);
1424 found_problem = test_loop_node(l);
1425 printf("Finished Test\n\n");
1426 if (found_problem) exit(0);
1430 /* ------------------------------------------------------------------- */
1431 /* Simple analyses based on the loop information */
1432 /* ------------------------------------------------------------------- */
1434 int is_loop_variant(ir_loop *l, ir_loop *b) {
1437 if (l == b) return true;
1439 n_elems = get_loop_n_elements(l);
1440 for (i = 0; i < n_elems; ++i) {
1441 loop_element e = get_loop_element(l, i);
1442 if (is_ir_loop(e.kind))
1443 if (is_loop_variant(e.son, b))
1450 /* Test whether a value is loop invariant.
1452 * @param n The node to be tested.
1453 * @param block A block node. We pass the block, not the loop as we must
1454 * start off with a block loop to find all proper uses.
1456 * Returns true, if the node n is not changed in the loop block
1457 * belongs to or in inner loops of this blocks loop. */
1458 int is_loop_invariant(ir_node *n, ir_node *block) {
1459 ir_loop *l = get_irn_loop(block);
1460 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1461 return !is_loop_variant(l, get_irn_loop(b));