2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Compute the strongly connected regions and build
23 * backedge/loop datastructures.
24 * A variation on the Tarjan algorithm. See also [Trapp:99],
26 * @author Goetz Lindenmaier
38 #include "irgraph_t.h"
45 /* A variant of the loop tree that avoids loops without head.
46 This reduces the depth of the loop tree. */
47 #define NO_LOOPS_WITHOUT_HEAD 1
49 /** The outermost graph the scc is computed for. */
50 static ir_graph *outermost_ir_graph;
51 /** Current loop construction is working on. */
52 static ir_loop *current_loop;
53 /** Counts the number of allocated loop nodes.
54 * Each loop node gets a unique number.
55 * @todo What for? ev. remove.
57 static int loop_node_cnt = 0;
58 /** Counter to generate depth first numbering of visited nodes. */
59 static int current_dfn = 1;
61 static int max_loop_depth = 0;
63 void link_to_reg_end(ir_node *n, void *env);
64 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
65 ir_node *get_projx_link(ir_node *cb_projx);
67 /**********************************************************************/
68 /* Node attributes **/
69 /**********************************************************************/
71 /**********************************************************************/
72 /* Node attributes needed for the construction. **/
73 /**********************************************************************/
75 typedef struct scc_info {
76 int in_stack; /**< Marks whether node is on the stack. */
77 int dfn; /**< Depth first search number. */
78 int uplink; /**< dfn number of ancestor. */
79 /* ir_loop *loop; *//* Refers to the containing loop. */
81 struct section *section;
88 * Allocates a new SCC info on the given obstack.
90 static inline scc_info *new_scc_info(struct obstack *obst) {
91 scc_info *info = obstack_alloc(obst, sizeof(*info));
92 memset(info, 0, sizeof(*info));
97 * Mark node n being on the SCC stack.
99 static inline void mark_irn_in_stack(ir_node *n) {
100 scc_info *scc = get_irn_link(n);
106 * Mark node n NOT being on the SCC stack.
108 static inline void mark_irn_not_in_stack(ir_node *n) {
109 scc_info *scc = get_irn_link(n);
115 * Checks if a node is on the SCC stack.
117 static inline int irn_is_in_stack(ir_node *n) {
118 scc_info *scc = get_irn_link(n);
120 return scc->in_stack;
124 * Sets the uplink number for a node.
126 static inline void set_irn_uplink(ir_node *n, int uplink) {
127 scc_info *scc = get_irn_link(n);
129 scc->uplink = uplink;
133 * Returns the uplink number for a node.
135 static int get_irn_uplink(ir_node *n) {
136 scc_info *scc = get_irn_link(n);
142 * Sets the depth-first-search number for a node.
144 static inline void set_irn_dfn(ir_node *n, int dfn) {
145 scc_info *scc = get_irn_link(n);
151 * Returns the depth-first-search number of a node.
153 static int get_irn_dfn(ir_node *n) {
154 scc_info *scc = get_irn_link(n);
160 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l) {
164 /* Test whether n is contained in this loop. */
165 for (i = 0; i < get_loop_n_nodes(l); i++)
166 if (n == get_loop_node(l, i)) return l;
168 /* Is this a leave in the loop tree? If so loop not found. */
169 if (get_loop_n_sons(l) == 0) return NULL;
171 /* Else descend in the loop tree. */
172 for (i = 0; i < get_loop_n_sons(l); i++) {
173 res = find_nodes_loop(n, get_loop_son(l, i));
179 /* @@@ temporary implementation, costly!!! */
180 ir_loop * get_irn_loop(ir_node *n) {
181 ir_loop *l = get_irg_loop(current_ir_graph);
182 l = find_nodes_loop(n, l);
187 /**********************************************************************/
189 /**********************************************************************/
191 static ir_node **stack = NULL;
192 static int tos = 0; /* top of stack */
195 * initializes the stack
197 static inline void init_stack(void) {
199 ARR_RESIZE(ir_node *, stack, 1000);
201 stack = NEW_ARR_F(ir_node *, 1000);
209 static void finish_stack(void) {
215 * push a node onto the stack
217 * @param n The node to push
219 static inline void push(ir_node *n) {
220 if (tos == ARR_LEN(stack)) {
221 int nlen = ARR_LEN(stack) * 2;
222 ARR_RESIZE(ir_node *, stack, nlen);
225 mark_irn_in_stack(n);
229 * pop a node from the stack
231 * @return The topmost node
233 static inline ir_node *pop(void) {
234 ir_node *n = stack[--tos];
235 mark_irn_not_in_stack(n);
240 * The nodes up to n belong to the current loop.
241 * Removes them from the stack and adds them to the current loop.
243 static inline void pop_scc_to_loop(ir_node *n) {
251 set_irn_dfn(m, loop_node_cnt);
252 add_loop_node(current_loop, m);
253 set_irn_loop(m, current_loop);
257 /* i might be bigger than 1 for dead (and that's why bad) loops */
259 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
263 /* GL ??? my last son is my grandson??? Removes loops with no
264 ir_nodes in them. Such loops have only another loop as son. (Why
265 can't they have two loops as sons? Does it never get that far? ) */
266 static void close_loop(ir_loop *l) {
267 int last = get_loop_n_elements(l) - 1;
268 loop_element lelement = get_loop_element(l, last);
269 ir_loop *last_son = lelement.son;
271 if (get_kind(last_son) == k_ir_loop &&
272 get_loop_n_elements(last_son) == 1) {
275 lelement = get_loop_element(last_son, 0);
278 if (get_kind(gson) == k_ir_loop) {
279 loop_element new_last_son;
281 gson->outer_loop = l;
282 new_last_son.son = gson;
283 l->children[last] = new_last_son;
290 /* Removes and unmarks all nodes up to n from the stack.
291 The nodes must be visited once more to assign them to a scc. */
292 static inline void pop_scc_unmark_visit(ir_node *n) {
297 set_irn_visited(m, 0);
301 /**********************************************************************/
302 /* The loop datastructure. **/
303 /**********************************************************************/
305 /* Allocates a new loop as son of current_loop. Sets current_loop
306 to the new loop and returns the father. */
307 static ir_loop *new_loop(void) {
308 ir_loop *father = current_loop;
309 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
311 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
316 /**********************************************************************/
317 /* Constructing and destructing the loop/backedge information. **/
318 /**********************************************************************/
320 /* Initialization steps. **********************************************/
322 static inline void init_node(ir_node *n, void *env) {
323 struct obstack *obst = env;
324 set_irn_link(n, new_scc_info(obst));
328 static inline void init_scc_common(void) {
334 static inline void init_scc(ir_graph *irg, struct obstack *obst) {
336 irg_walk_graph(irg, init_node, NULL, obst);
338 irg_walk (irg, link_to_reg_end, NULL, NULL);
342 static inline void finish_scc(void)
347 #ifdef INTERPROCEDURAL_VIEW
348 static inline void init_ip_scc(struct obstack *obst) {
350 cg_walk(init_node, NULL, obst);
352 #if EXPERIMENTAL_LOOP_TREE
353 cg_walk(link_to_reg_end, NULL, NULL);
359 * Check weather a given node represents the outer most Start
360 * block. In intra-procedural view this is the start block of the
361 * current graph, in interprocedural view it is the start block
362 * of the outer most graph.
364 * @param n the node to check
366 * This is the condition for breaking the scc recursion.
368 static int is_outermost_Start(ir_node *n) {
369 /* Test whether this is the outermost Start node. */
370 if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
371 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
372 if (is_Start(pred) && get_nodes_block(pred) == n)
378 /* When to walk from nodes to blocks. Only for Control flow operations? */
379 static inline int get_start_index(ir_node *n) {
380 #undef BLOCK_BEFORE_NODE
381 #define BLOCK_BEFORE_NODE 1
383 #if BLOCK_BEFORE_NODE
385 /* This version assures, that all nodes are ordered absolutely. This allows
386 to undef all nodes in the heap analysis if the block is false, which means
388 I.e., with this code, the order on the loop tree is correct. But a (single)
389 test showed the loop tree is deeper. */
390 if (get_irn_op(n) == op_Phi ||
392 (is_Filter(n) && get_interprocedural_view()) || (
393 get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
394 get_irn_pinned(n) == op_pin_state_floats
396 // Here we could test for backedge at -1 which is illegal
403 /* This version causes deeper loop trees (at least we verified this
405 But it guarantees that Blocks are analysed before nodes contained in the
406 block. If so, we can set the value to undef if the block is not \
408 if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
417 * Return non-zero if the given node is a legal loop header:
418 * Block, Phi, Filter.
420 * @param n the node to check
422 static inline int is_possible_loop_head(ir_node *n) {
423 ir_op *op = get_irn_op(n);
424 return ((op == op_Block) ||
426 ((op == op_Filter) && get_interprocedural_view()));
430 * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
431 * or Filter node and has predecessors within the loop and out
434 * @param n the node to check
435 * @param root only needed for assertion.
437 static int is_head(ir_node *n, ir_node *root) {
439 int some_outof_loop = 0, some_in_loop = 0;
441 /* Test for legal loop header: Block, Phi, ... */
442 if (!is_possible_loop_head(n))
445 if (!is_outermost_Start(n)) {
447 int uplink = get_irn_uplink(root);
451 arity = get_irn_arity(n);
452 for (i = get_start_index(n); i < arity; i++) {
454 if (is_backedge(n, i))
456 pred = get_irn_n(n, i);
457 if (! irn_is_in_stack(pred)) {
460 assert(get_irn_uplink(pred) >= uplink);
465 return some_outof_loop & some_in_loop;
469 * Returns non-zero if n is possible loop head of an endless loop.
470 * I.e., it is a Block, Phi or Filter node and has only predecessors
473 * @param n the node to check
474 * @param root only needed for assertion.
476 static int is_endless_head(ir_node *n, ir_node *root) {
478 int none_outof_loop = 1, some_in_loop = 0;
480 /* Test for legal loop header: Block, Phi, ... */
481 if (!is_possible_loop_head(n))
484 if (!is_outermost_Start(n)) {
486 int uplink = get_irn_uplink(root);
490 arity = get_irn_arity(n);
491 for (i = get_start_index(n); i < arity; i++) {
493 if (is_backedge(n, i))
495 pred = get_irn_n(n, i);
496 if (!irn_is_in_stack(pred)) {
499 assert(get_irn_uplink(pred) >= uplink);
504 return none_outof_loop & some_in_loop;
507 /** Returns index of the predecessor with the smallest dfn number
508 greater-equal than limit. */
509 static int smallest_dfn_pred(ir_node *n, int limit) {
510 int i, index = -2, min = -1;
512 if (!is_outermost_Start(n)) {
513 int arity = get_irn_arity(n);
514 for (i = get_start_index(n); i < arity; i++) {
515 ir_node *pred = get_irn_n(n, i);
516 if (is_backedge(n, i) || !irn_is_in_stack(pred))
518 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
520 min = get_irn_dfn(pred);
528 * Returns index of the predecessor with the largest dfn number.
530 static int largest_dfn_pred(ir_node *n) {
531 int i, index = -2, max = -1;
533 if (!is_outermost_Start(n)) {
534 int arity = get_irn_arity(n);
535 for (i = get_start_index(n); i < arity; i++) {
536 ir_node *pred = get_irn_n(n, i);
537 if (is_backedge (n, i) || !irn_is_in_stack(pred))
539 if (get_irn_dfn(pred) > max) {
541 max = get_irn_dfn(pred);
549 * Searches the stack for possible loop heads. Tests these for backedges.
550 * If it finds a head with an unmarked backedge it marks this edge and
551 * returns the tail of the loop.
552 * If it finds no backedge returns NULL.
553 * ("disable_backedge" in fiasco)
555 * @param n A node where uplink == dfn.
557 static ir_node *find_tail(ir_node *n) {
559 int i, res_index = -2;
562 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
564 m = stack[tos-1]; /* tos = top of stack */
566 res_index = smallest_dfn_pred(m, 0);
567 if ((res_index == -2) && /* no smallest dfn pred found. */
571 if (m == n) return NULL; // Is this to catch Phi - self loops?
572 for (i = tos-2; i >= 0; --i) {
576 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
577 if (res_index == -2) /* no smallest dfn pred found. */
578 res_index = largest_dfn_pred(m);
580 if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
586 /* We should not walk past our selves on the stack: The upcoming nodes
587 are not in this loop. We assume a loop not reachable from Start. */
595 /* A dead loop not reachable from Start. */
596 for (i = tos-2; i >= 0; --i) {
598 if (is_endless_head(m, n)) {
599 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
600 if (res_index == -2) /* no smallest dfn pred found. */
601 res_index = largest_dfn_pred (m);
604 if (m == n) { break; } /* It's not an unreachable loop, either. */
606 //assert(0 && "no head found on stack");
610 if (res_index <= -2) {
611 /* It's a completely bad loop: without Phi/Block nodes that can
612 be a head. I.e., the code is "dying". We break the loop by
613 setting Bad nodes. */
614 int arity = get_irn_arity(n);
615 ir_node *bad = get_irg_bad(get_irn_irg(n));
616 for (i = -1; i < arity; ++i) {
617 set_irn_n(n, i, bad);
621 assert(res_index > -2);
623 set_backedge(m, res_index);
624 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
628 #if EXPERIMENTAL_LOOP_TREE
630 /* ----------------------------------------------------------------
631 AS: This is experimental code to build loop trees suitable for
632 the heap analysis. Does not work correctly right now... :-(
635 Search in stack for the corresponding first Call-End-ProjX that
636 corresponds to one of the control flow predecessors of the given
637 block, that is the possible callers.
638 returns: the control predecessor to chose\
639 or -1 if no corresponding Call-End-Node could be found
641 - -------------------------------------------------------------- */
643 int search_endproj_in_stack(ir_node *start_block) {
645 assert(is_Block(start_block));
646 for(i = tos - 1; i >= 0; --i)
648 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
649 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
651 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
652 ir_node *end_projx = stack[i];
654 int arity = get_irn_arity(start_block);
655 for(j = 0; j < arity; j++)
657 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
658 get_Proj_proj(end_projx));
659 if(get_irn_n(start_block, j) == begin_projx)
661 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
671 static pmap *projx_link = NULL;
673 void link_to_reg_end (ir_node *n, void *env) {
674 if(get_irn_op(n) == op_Proj &&
675 get_irn_mode(n) == mode_X &&
676 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
677 /* Reg End Projx -> Find the CallBegin Projx and hash it */
678 ir_node *end_projx = n;
679 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
680 get_Proj_proj(end_projx));
681 set_projx_link(begin_projx, end_projx);
685 void set_projx_link(ir_node *cb_projx, ir_node *end_projx) {
686 if(projx_link == NULL)
687 projx_link = pmap_create();
688 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
691 ir_node *get_projx_link(ir_node *cb_projx) {
692 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
697 static inline int is_outermost_loop(ir_loop *l) {
698 return l == get_loop_outer_loop(l);
702 /*-----------------------------------------------------------*
703 * The core algorithm. *
704 *-----------------------------------------------------------*/
707 * The core algorithm: Find strongly coupled components.
709 * @param n node to start
711 static void scc(ir_node *n) {
712 if (irn_visited_else_mark(n))
715 /* Initialize the node */
716 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
717 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
718 set_irn_loop(n, NULL);
722 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
723 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
724 so is_backedge does not access array[-1] but correctly returns false! */
726 if (!is_outermost_Start(n)) {
727 int i, arity = get_irn_arity(n);
729 for (i = get_start_index(n); i < arity; ++i) {
731 if (is_backedge(n, i))
735 if (irn_is_in_stack(m)) {
736 /* Uplink of m is smaller if n->m is a backedge.
737 Propagate the uplink to mark the loop. */
738 if (get_irn_uplink(m) < get_irn_uplink(n))
739 set_irn_uplink(n, get_irn_uplink(m));
744 if (get_irn_dfn(n) == get_irn_uplink(n)) {
745 /* This condition holds for
746 1) the node with the incoming backedge.
747 That is: We found a loop!
748 2) Straight line code, because no uplink has been propagated, so the
749 uplink still is the same as the dfn.
751 But n might not be a proper loop head for the analysis. Proper loop
752 heads are Block and Phi nodes. find_tail() searches the stack for
753 Block's and Phi's and takes those nodes as loop heads for the current
754 loop instead and marks the incoming edge as backedge. */
756 ir_node *tail = find_tail(n);
758 /* We have a loop, that is no straight line code,
759 because we found a loop head!
760 Next actions: Open a new loop on the loop tree and
761 try to find inner loops */
763 #if NO_LOOPS_WITHOUT_HEAD
764 /* This is an adaption of the algorithm from fiasco / optscc to
765 * avoid loops without Block or Phi as first node. This should
766 * severely reduce the number of evaluations of nodes to detect
767 * a fixpoint in the heap analysis.
768 * Further it avoids loops without firm nodes that cause errors
769 * in the heap analyses.
770 * But attention: don't do it for the outermost loop: This loop
771 * is not iterated. A first block can be a loop head in case of
772 * an endless recursion. */
776 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
784 ir_loop *l = new_loop();
787 /* Remove the loop from the stack ... */
788 pop_scc_unmark_visit(n);
790 /* The current backedge has been marked, that is temporarily eliminated,
791 by find tail. Start the scc algorithm
792 again on the subgraph that is left (the current loop without the backedge)
793 in order to find more inner loops. */
796 assert(irn_visited(n));
797 #if NO_LOOPS_WITHOUT_HEAD
802 /* No loop head was found, that is we have straight line code.
803 Pop all nodes from the stack to the current loop. */
809 #ifdef INTERPROCEDURAL_VIEW
810 static void my_scc(ir_node *n) {
812 if (irn_visited_else_mark(n))
815 /* Initialize the node */
816 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
817 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
818 set_irn_loop(n, NULL);
822 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
823 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
824 so is_backedge does not access array[-1] but correctly returns false! */
826 if (!is_outermost_Start(n)) {
827 int arity = get_irn_arity(n);
829 for (i = get_start_index(n); i < arity; i++) {
831 if (is_backedge(n, i)) continue;
832 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
833 /* if (!m || is_Unknown(m)) continue; */
835 if (irn_is_in_stack(m)) {
836 /* Uplink of m is smaller if n->m is a backedge.
837 Propagate the uplink to mark the loop. */
838 if (get_irn_uplink(m) < get_irn_uplink(n))
839 set_irn_uplink(n, get_irn_uplink(m));
844 if (get_irn_dfn(n) == get_irn_uplink(n)) {
845 /* This condition holds for
846 1) the node with the incoming backedge.
847 That is: We found a loop!
848 2) Straight line code, because no uplink has been propagated, so the
849 uplink still is the same as the dfn.
851 But n might not be a proper loop head for the analysis. Proper loop
852 heads are Block and Phi nodes. find_tail searches the stack for
853 Block's and Phi's and takes those nodes as loop heads for the current
854 loop instead and marks the incoming edge as backedge. */
856 ir_node *tail = find_tail(n);
858 /* We have a loop, that is no straight line code,
859 because we found a loop head!
860 Next actions: Open a new loop on the loop tree and
861 try to find inner loops */
863 #if NO_LOOPS_WITHOUT_HEAD
864 /* This is an adaption of the algorithm from fiasco / optscc to
865 * avoid loops without Block or Phi as first node. This should
866 * severely reduce the number of evaluations of nodes to detect
867 * a fixpoint in the heap analysis.
868 * Further it avoids loops without firm nodes that cause errors
869 * in the heap analyses. */
873 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
881 ir_loop *l = new_loop();
884 /* Remove the loop from the stack ... */
885 pop_scc_unmark_visit(n);
887 /* The current backedge has been marked, that is temporarily eliminated,
888 by find tail. Start the scc algorithm
889 anew on the subgraph that is left (the current loop without the backedge)
890 in order to find more inner loops. */
893 assert(irn_visited(n));
894 #if NO_LOOPS_WITHOUT_HEAD
899 /* No loop head was found, that is we have straightline code.
900 Pop all nodes from the stack to the current loop. */
905 #endif /* INTERPROCEDURAL_VIEW */
907 /* Constructs backedge information for irg. In interprocedural view constructs
908 backedges for all methods called by irg, too. */
909 int construct_backedges(ir_graph *irg) {
910 ir_graph *rem = current_ir_graph;
914 assert(!get_interprocedural_view() &&
915 "not implemented, use construct_ip_backedges()");
918 current_ir_graph = irg;
919 outermost_ir_graph = irg;
922 init_scc(irg, &temp);
925 new_loop(); /* sets current_loop */
926 head_rem = current_loop; /* Just for assertion */
928 inc_irg_visited(irg);
930 scc(get_irg_end(irg));
933 obstack_free(&temp, NULL);
935 assert(head_rem == current_loop);
936 mature_loops(current_loop, irg->obst);
937 set_irg_loop(irg, current_loop);
938 set_irg_loopinfo_state(irg, loopinfo_consistent);
939 assert(get_irg_loop(irg)->kind == k_ir_loop);
940 current_ir_graph = rem;
941 return max_loop_depth;
945 #ifdef INTERPROCEDURAL_VIEW
946 int construct_ip_backedges(void) {
947 ir_graph *rem = current_ir_graph;
948 int rem_ipv = get_interprocedural_view();
953 assert(get_irp_ip_view_state() == ip_view_valid);
955 outermost_ir_graph = get_irp_main_irg();
961 new_loop(); /* sets current_loop */
962 set_interprocedural_view(1);
964 inc_max_irg_visited();
965 for (i = 0; i < get_irp_n_irgs(); i++)
966 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
968 /** We have to start the walk at the same nodes as cg_walk. **/
969 /* Walk starting at unreachable procedures. Only these
970 * have End blocks visible in interprocedural view. */
971 for (i = 0; i < get_irp_n_irgs(); i++) {
973 current_ir_graph = get_irp_irg(i);
975 sb = get_irg_start_block(current_ir_graph);
977 if ((get_Block_n_cfgpreds(sb) > 1) ||
978 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
981 scc(get_irg_end(current_ir_graph));
984 /* Check whether we walked all procedures: there could be procedures
985 with cyclic calls but no call from the outside. */
986 for (i = 0; i < get_irp_n_irgs(); i++) {
988 current_ir_graph = get_irp_irg(i);
990 /* Test start block: if inner procedure end and end block are not
991 * visible and therefore not marked. */
992 sb = get_irg_start_block(current_ir_graph);
993 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
996 /* Walk all endless loops in inner procedures.
997 * We recognize an inner procedure if the End node is not visited. */
998 for (i = 0; i < get_irp_n_irgs(); i++) {
1000 current_ir_graph = get_irp_irg(i);
1002 e = get_irg_end(current_ir_graph);
1003 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1005 /* Don't visit the End node. */
1006 for (j = 0; j < get_End_n_keepalives(e); j++)
1007 scc(get_End_keepalive(e, j));
1011 set_irg_loop(outermost_ir_graph, current_loop);
1012 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1013 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1015 obstack_free(&temp, NULL);
1016 current_ir_graph = rem;
1017 set_interprocedural_view(rem_ipv);
1018 return max_loop_depth;
1021 void my_construct_ip_backedges(void) {
1022 ir_graph *rem = current_ir_graph;
1023 int rem_ipv = get_interprocedural_view();
1026 assert(get_irp_ip_view_state() == ip_view_valid);
1028 outermost_ir_graph = get_irp_main_irg();
1032 current_loop = NULL;
1033 new_loop(); /* sets current_loop */
1034 set_interprocedural_view(1);
1036 inc_max_irg_visited();
1037 for (i = 0; i < get_irp_n_irgs(); i++)
1038 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1040 /** We have to start the walk at the same nodes as cg_walk. **/
1041 /* Walk starting at unreachable procedures. Only these
1042 * have End blocks visible in interprocedural view. */
1043 for (i = 0; i < get_irp_n_irgs(); i++) {
1045 current_ir_graph = get_irp_irg(i);
1047 sb = get_irg_start_block(current_ir_graph);
1049 if ((get_Block_n_cfgpreds(sb) > 1) ||
1050 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1052 my_scc(get_irg_end(current_ir_graph));
1055 /* Check whether we walked all procedures: there could be procedures
1056 with cyclic calls but no call from the outside. */
1057 for (i = 0; i < get_irp_n_irgs(); i++) {
1059 current_ir_graph = get_irp_irg(i);
1061 /* Test start block: if inner procedure end and end block are not
1062 * visible and therefore not marked. */
1063 sb = get_irg_start_block(current_ir_graph);
1064 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1068 /* Walk all endless loops in inner procedures.
1069 * We recognize an inner procedure if the End node is not visited. */
1070 for (i = 0; i < get_irp_n_irgs(); i++) {
1072 current_ir_graph = get_irp_irg(i);
1074 e = get_irg_end(current_ir_graph);
1075 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1077 /* Don't visit the End node. */
1078 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1082 set_irg_loop(outermost_ir_graph, current_loop);
1083 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1084 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1086 current_ir_graph = rem;
1087 set_interprocedural_view(rem_ipv);
1091 static void reset_backedges(ir_node *n) {
1092 if (is_possible_loop_head(n)) {
1093 #ifdef INTERPROCEDURAL_VIEW
1094 int rem = get_interprocedural_view();
1096 set_interprocedural_view(1);
1098 set_interprocedural_view(1);
1100 set_interprocedural_view(rem);
1109 static void loop_reset_backedges(ir_loop *l) {
1111 reset_backedges(get_loop_node(l, 0));
1112 for (i = 0; i < get_loop_n_nodes(l); ++i)
1113 set_irn_loop(get_loop_node(l, i), NULL);
1114 for (i = 0; i < get_loop_n_sons(l); ++i) {
1115 loop_reset_backedges(get_loop_son(l, i));
1120 static void loop_reset_node(ir_node *n, void *env) {
1122 set_irn_loop(n, NULL);
1127 /** Removes all loop information.
1128 Resets all backedges */
1129 void free_loop_information(ir_graph *irg) {
1130 /* We can not use this recursion, as the loop might contain
1131 illegal nodes by now. Why else would we throw away the
1133 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1135 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1136 set_irg_loop(irg, NULL);
1137 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1138 /* We cannot free the loop nodes, they are on the obstack. */
1142 void free_all_loop_information(void) {
1144 #ifdef INTERPROCEDURAL_VIEW
1145 int rem = get_interprocedural_view();
1146 set_interprocedural_view(1); /* To visit all filter nodes */
1148 for (i = 0; i < get_irp_n_irgs(); i++) {
1149 free_loop_information(get_irp_irg(i));
1151 #ifdef INTERPROCEDURAL_VIEW
1152 set_interprocedural_view(rem);
1160 /* Debug stuff *************************************************/
1162 static int test_loop_node(ir_loop *l) {
1163 int i, has_node = 0, found_problem = 0;
1166 assert(l && l->kind == k_ir_loop);
1168 if (get_loop_n_elements(l) == 0) {
1170 dump_loop(l, "-ha");
1173 le = get_loop_element(l, 0);
1174 if (*(le.kind) != k_ir_node) {
1175 assert(le.kind && *(le.kind) == k_ir_loop);
1178 dump_loop(l, "-ha");
1181 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1183 dump_loop(l, "-ha");
1186 if ((get_loop_depth(l) != 0) &&
1187 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1189 dump_loop(l, "-ha");
1194 for (i = 0; i < get_loop_n_elements(l); ++i) {
1195 le = get_loop_element(l, i);
1196 if (*(le.kind) == k_ir_node)
1199 if (test_loop_node(le.son)) found_problem = 1;
1202 if (has_node == 0) {
1204 dump_loop(l, "-ha");
1207 return found_problem;
1210 /** Prints all loop nodes that
1211 * - do not have any firm nodes, only loop sons
1212 * - the header is not a Phi, Block or Filter.
1214 void find_strange_loop_nodes(ir_loop *l) {
1215 int found_problem = 0;
1216 found_problem = test_loop_node(l);
1217 printf("Finished Test\n\n");
1218 if (found_problem) exit(0);
1222 /* ------------------------------------------------------------------- */
1223 /* Simple analyses based on the loop information */
1224 /* ------------------------------------------------------------------- */
1226 int is_loop_variant(ir_loop *l, ir_loop *b) {
1229 if (l == b) return 1;
1231 n_elems = get_loop_n_elements(l);
1232 for (i = 0; i < n_elems; ++i) {
1233 loop_element e = get_loop_element(l, i);
1234 if (is_ir_loop(e.kind))
1235 if (is_loop_variant(e.son, b))
1242 /* Test whether a value is loop invariant.
1244 * @param n The node to be tested.
1245 * @param block A block node. We pass the block, not the loop as we must
1246 * start off with a block loop to find all proper uses.
1248 * Returns non-zero, if the node n is not changed in the loop block
1249 * belongs to or in inner loops of this blocks loop. */
1250 int is_loop_invariant(const ir_node *n, const ir_node *block) {
1251 ir_loop *l = get_irn_loop(block);
1252 const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1253 return !is_loop_variant(l, get_irn_loop(b));