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)
92 return OALLOCZ(obst, scc_info);
96 * Mark node n being on the SCC stack.
98 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)
110 scc_info *scc = get_irn_link(n);
116 * Checks if a node is on the SCC stack.
118 static inline int irn_is_in_stack(ir_node *n)
120 scc_info *scc = get_irn_link(n);
122 return scc->in_stack;
126 * Sets the uplink number for a node.
128 static inline void set_irn_uplink(ir_node *n, int uplink)
130 scc_info *scc = get_irn_link(n);
132 scc->uplink = uplink;
136 * Returns the uplink number for a node.
138 static int get_irn_uplink(ir_node *n)
140 scc_info *scc = get_irn_link(n);
146 * Sets the depth-first-search number for a node.
148 static inline void set_irn_dfn(ir_node *n, int dfn)
150 scc_info *scc = get_irn_link(n);
156 * Returns the depth-first-search number of a node.
158 static int get_irn_dfn(ir_node *n)
160 scc_info *scc = get_irn_link(n);
166 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l)
171 /* Test whether n is contained in this loop. */
172 for (i = 0; i < get_loop_n_nodes(l); i++)
173 if (n == get_loop_node(l, i)) return l;
175 /* Is this a leave in the loop tree? If so loop not found. */
176 if (get_loop_n_sons(l) == 0) return NULL;
178 /* Else descend in the loop tree. */
179 for (i = 0; i < get_loop_n_sons(l); i++) {
180 res = find_nodes_loop(n, get_loop_son(l, i));
186 /* @@@ temporary implementation, costly!!! */
187 ir_loop * get_irn_loop(ir_node *n)
189 ir_loop *l = get_irg_loop(current_ir_graph);
190 l = find_nodes_loop(n, l);
195 /**********************************************************************/
197 /**********************************************************************/
199 static ir_node **stack = NULL;
200 static int tos = 0; /* top of stack */
203 * initializes the stack
205 static inline void init_stack(void)
208 ARR_RESIZE(ir_node *, stack, 1000);
210 stack = NEW_ARR_F(ir_node *, 1000);
218 static void finish_stack(void)
225 * push a node onto the stack
227 * @param n The node to push
229 static inline void push(ir_node *n)
231 if (tos == ARR_LEN(stack)) {
232 int nlen = ARR_LEN(stack) * 2;
233 ARR_RESIZE(ir_node *, stack, nlen);
236 mark_irn_in_stack(n);
240 * pop a node from the stack
242 * @return The topmost node
244 static inline ir_node *pop(void)
246 ir_node *n = stack[--tos];
247 mark_irn_not_in_stack(n);
252 * The nodes up to n belong to the current loop.
253 * Removes them from the stack and adds them to the current loop.
255 static inline void pop_scc_to_loop(ir_node *n)
264 set_irn_dfn(m, loop_node_cnt);
265 add_loop_node(current_loop, m);
266 set_irn_loop(m, current_loop);
270 /* i might be bigger than 1 for dead (and that's why bad) loops */
272 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
276 /* GL ??? my last son is my grandson??? Removes loops with no
277 ir_nodes in them. Such loops have only another loop as son. (Why
278 can't they have two loops as sons? Does it never get that far? ) */
279 static void close_loop(ir_loop *l)
281 int last = get_loop_n_elements(l) - 1;
282 loop_element lelement = get_loop_element(l, last);
283 ir_loop *last_son = lelement.son;
285 if (get_kind(last_son) == k_ir_loop &&
286 get_loop_n_elements(last_son) == 1) {
289 lelement = get_loop_element(last_son, 0);
292 if (get_kind(gson) == k_ir_loop) {
293 loop_element new_last_son;
295 gson->outer_loop = l;
296 new_last_son.son = gson;
297 l->children[last] = new_last_son;
304 /* Removes and unmarks all nodes up to n from the stack.
305 The nodes must be visited once more to assign them to a scc. */
306 static inline void pop_scc_unmark_visit(ir_node *n)
312 set_irn_visited(m, 0);
316 /**********************************************************************/
317 /* The loop datastructure. **/
318 /**********************************************************************/
320 /* Allocates a new loop as son of current_loop. Sets current_loop
321 to the new loop and returns the father. */
322 static ir_loop *new_loop(void)
324 ir_loop *father = current_loop;
325 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
327 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
332 /**********************************************************************/
333 /* Constructing and destructing the loop/backedge information. **/
334 /**********************************************************************/
336 /* Initialization steps. **********************************************/
338 static inline void init_node(ir_node *n, void *env)
340 struct obstack *obst = env;
341 set_irn_link(n, new_scc_info(obst));
345 static inline void init_scc_common(void)
352 static inline void init_scc(ir_graph *irg, struct obstack *obst)
355 irg_walk_graph(irg, init_node, NULL, obst);
357 irg_walk (irg, link_to_reg_end, NULL, NULL);
361 static inline void finish_scc(void)
366 #ifdef INTERPROCEDURAL_VIEW
367 static inline void init_ip_scc(struct obstack *obst)
370 cg_walk(init_node, NULL, obst);
372 #if EXPERIMENTAL_LOOP_TREE
373 cg_walk(link_to_reg_end, NULL, NULL);
379 * Check weather a given node represents the outer most Start
380 * block. In intra-procedural view this is the start block of the
381 * current graph, in interprocedural view it is the start block
382 * of the outer most graph.
384 * @param n the node to check
386 * This is the condition for breaking the scc recursion.
388 static int is_outermost_Start(ir_node *n)
390 /* Test whether this is the outermost Start node. */
391 if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
392 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
393 if (is_Start(pred) && get_nodes_block(pred) == n)
399 /* When to walk from nodes to blocks. Only for Control flow operations? */
400 static inline int get_start_index(ir_node *n)
402 #undef BLOCK_BEFORE_NODE
403 #define BLOCK_BEFORE_NODE 1
405 #if BLOCK_BEFORE_NODE
407 /* This version assures, that all nodes are ordered absolutely. This allows
408 to undef all nodes in the heap analysis if the block is false, which means
410 I.e., with this code, the order on the loop tree is correct. But a (single)
411 test showed the loop tree is deeper. */
412 if (get_irn_op(n) == op_Phi ||
414 (is_Filter(n) && get_interprocedural_view()) || (
415 get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
416 get_irn_pinned(n) == op_pin_state_floats
418 // Here we could test for backedge at -1 which is illegal
425 /* This version causes deeper loop trees (at least we verified this
427 But it guarantees that Blocks are analysed before nodes contained in the
428 block. If so, we can set the value to undef if the block is not \
430 if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
439 * Return non-zero if the given node is a legal loop header:
440 * Block, Phi, Filter.
442 * @param n the node to check
444 static inline int is_possible_loop_head(ir_node *n)
446 ir_op *op = get_irn_op(n);
447 return ((op == op_Block) ||
449 ((op == op_Filter) && get_interprocedural_view()));
453 * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
454 * or Filter node and has predecessors within the loop and out
457 * @param n the node to check
458 * @param root only needed for assertion.
460 static int is_head(ir_node *n, ir_node *root)
463 int some_outof_loop = 0, some_in_loop = 0;
465 /* Test for legal loop header: Block, Phi, ... */
466 if (!is_possible_loop_head(n))
469 if (!is_outermost_Start(n)) {
471 int uplink = get_irn_uplink(root);
475 arity = get_irn_arity(n);
476 for (i = get_start_index(n); i < arity; i++) {
478 if (is_backedge(n, i))
480 pred = get_irn_n(n, i);
481 if (! irn_is_in_stack(pred)) {
484 assert(get_irn_uplink(pred) >= uplink);
489 return some_outof_loop & some_in_loop;
493 * Returns non-zero if n is possible loop head of an endless loop.
494 * I.e., it is a Block, Phi or Filter node and has only predecessors
497 * @param n the node to check
498 * @param root only needed for assertion.
500 static int is_endless_head(ir_node *n, ir_node *root)
503 int none_outof_loop = 1, some_in_loop = 0;
505 /* Test for legal loop header: Block, Phi, ... */
506 if (!is_possible_loop_head(n))
509 if (!is_outermost_Start(n)) {
511 int uplink = get_irn_uplink(root);
515 arity = get_irn_arity(n);
516 for (i = get_start_index(n); i < arity; i++) {
518 if (is_backedge(n, i))
520 pred = get_irn_n(n, i);
521 if (!irn_is_in_stack(pred)) {
524 assert(get_irn_uplink(pred) >= uplink);
529 return none_outof_loop & some_in_loop;
532 /** Returns index of the predecessor with the smallest dfn number
533 greater-equal than limit. */
534 static int smallest_dfn_pred(ir_node *n, int limit)
536 int i, index = -2, min = -1;
538 if (!is_outermost_Start(n)) {
539 int arity = get_irn_arity(n);
540 for (i = get_start_index(n); i < arity; i++) {
541 ir_node *pred = get_irn_n(n, i);
542 if (is_backedge(n, i) || !irn_is_in_stack(pred))
544 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
546 min = get_irn_dfn(pred);
554 * Returns index of the predecessor with the largest dfn number.
556 static int largest_dfn_pred(ir_node *n)
558 int i, index = -2, max = -1;
560 if (!is_outermost_Start(n)) {
561 int arity = get_irn_arity(n);
562 for (i = get_start_index(n); i < arity; i++) {
563 ir_node *pred = get_irn_n(n, i);
564 if (is_backedge (n, i) || !irn_is_in_stack(pred))
566 if (get_irn_dfn(pred) > max) {
568 max = get_irn_dfn(pred);
576 * Searches the stack for possible loop heads. Tests these for backedges.
577 * If it finds a head with an unmarked backedge it marks this edge and
578 * returns the tail of the loop.
579 * If it finds no backedge returns NULL.
580 * ("disable_backedge" in fiasco)
582 * @param n A node where uplink == dfn.
584 static ir_node *find_tail(ir_node *n)
587 int i, res_index = -2;
590 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
592 m = stack[tos-1]; /* tos = top of stack */
594 res_index = smallest_dfn_pred(m, 0);
595 if ((res_index == -2) && /* no smallest dfn pred found. */
599 if (m == n) return NULL; // Is this to catch Phi - self loops?
600 for (i = tos-2; i >= 0; --i) {
604 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
605 if (res_index == -2) /* no smallest dfn pred found. */
606 res_index = largest_dfn_pred(m);
608 if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
614 /* We should not walk past our selves on the stack: The upcoming nodes
615 are not in this loop. We assume a loop not reachable from Start. */
623 /* A dead loop not reachable from Start. */
624 for (i = tos-2; i >= 0; --i) {
626 if (is_endless_head(m, n)) {
627 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
628 if (res_index == -2) /* no smallest dfn pred found. */
629 res_index = largest_dfn_pred (m);
632 if (m == n) { break; } /* It's not an unreachable loop, either. */
634 //assert(0 && "no head found on stack");
638 if (res_index <= -2) {
639 /* It's a completely bad loop: without Phi/Block nodes that can
640 be a head. I.e., the code is "dying". We break the loop by
641 setting Bad nodes. */
642 int arity = get_irn_arity(n);
643 ir_node *bad = get_irg_bad(get_irn_irg(n));
644 for (i = -1; i < arity; ++i) {
645 set_irn_n(n, i, bad);
649 assert(res_index > -2);
651 set_backedge(m, res_index);
652 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
656 #if EXPERIMENTAL_LOOP_TREE
658 /* ----------------------------------------------------------------
659 AS: This is experimental code to build loop trees suitable for
660 the heap analysis. Does not work correctly right now... :-(
663 Search in stack for the corresponding first Call-End-ProjX that
664 corresponds to one of the control flow predecessors of the given
665 block, that is the possible callers.
666 returns: the control predecessor to chose\
667 or -1 if no corresponding Call-End-Node could be found
669 - -------------------------------------------------------------- */
671 int search_endproj_in_stack(ir_node *start_block)
674 assert(is_Block(start_block));
675 for (i = tos - 1; i >= 0; --i)
677 if (get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
678 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
680 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
681 ir_node *end_projx = stack[i];
683 int arity = get_irn_arity(start_block);
684 for (j = 0; j < arity; j++)
686 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
687 get_Proj_proj(end_projx));
688 if (get_irn_n(start_block, j) == begin_projx)
690 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
700 static pmap *projx_link = NULL;
702 void link_to_reg_end (ir_node *n, void *env)
704 if (get_irn_op(n) == op_Proj &&
705 get_irn_mode(n) == mode_X &&
706 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
707 /* Reg End Projx -> Find the CallBegin Projx and hash it */
708 ir_node *end_projx = n;
709 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
710 get_Proj_proj(end_projx));
711 set_projx_link(begin_projx, end_projx);
715 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
717 if (projx_link == NULL)
718 projx_link = pmap_create();
719 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
722 ir_node *get_projx_link(ir_node *cb_projx)
724 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
729 static inline int is_outermost_loop(ir_loop *l)
731 return l == get_loop_outer_loop(l);
735 /*-----------------------------------------------------------*
736 * The core algorithm. *
737 *-----------------------------------------------------------*/
740 * The core algorithm: Find strongly coupled components.
742 * @param n node to start
744 static void scc(ir_node *n)
746 if (irn_visited_else_mark(n))
749 /* Initialize the node */
750 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
751 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
752 set_irn_loop(n, NULL);
756 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
757 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
758 so is_backedge does not access array[-1] but correctly returns false! */
760 if (!is_outermost_Start(n)) {
761 int i, arity = get_irn_arity(n);
763 for (i = get_start_index(n); i < arity; ++i) {
765 if (is_backedge(n, i))
769 if (irn_is_in_stack(m)) {
770 /* Uplink of m is smaller if n->m is a backedge.
771 Propagate the uplink to mark the loop. */
772 if (get_irn_uplink(m) < get_irn_uplink(n))
773 set_irn_uplink(n, get_irn_uplink(m));
778 if (get_irn_dfn(n) == get_irn_uplink(n)) {
779 /* This condition holds for
780 1) the node with the incoming backedge.
781 That is: We found a loop!
782 2) Straight line code, because no uplink has been propagated, so the
783 uplink still is the same as the dfn.
785 But n might not be a proper loop head for the analysis. Proper loop
786 heads are Block and Phi nodes. find_tail() searches the stack for
787 Block's and Phi's and takes those nodes as loop heads for the current
788 loop instead and marks the incoming edge as backedge. */
790 ir_node *tail = find_tail(n);
792 /* We have a loop, that is no straight line code,
793 because we found a loop head!
794 Next actions: Open a new loop on the loop tree and
795 try to find inner loops */
797 #if NO_LOOPS_WITHOUT_HEAD
798 /* This is an adaption of the algorithm from fiasco / optscc to
799 * avoid loops without Block or Phi as first node. This should
800 * severely reduce the number of evaluations of nodes to detect
801 * a fixpoint in the heap analysis.
802 * Further it avoids loops without firm nodes that cause errors
803 * in the heap analyses.
804 * But attention: don't do it for the outermost loop: This loop
805 * is not iterated. A first block can be a loop head in case of
806 * an endless recursion. */
810 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
818 ir_loop *l = new_loop();
821 /* Remove the loop from the stack ... */
822 pop_scc_unmark_visit(n);
824 /* The current backedge has been marked, that is temporarily eliminated,
825 by find tail. Start the scc algorithm
826 again on the subgraph that is left (the current loop without the backedge)
827 in order to find more inner loops. */
830 assert(irn_visited(n));
831 #if NO_LOOPS_WITHOUT_HEAD
836 /* No loop head was found, that is we have straight line code.
837 Pop all nodes from the stack to the current loop. */
843 #ifdef INTERPROCEDURAL_VIEW
844 static void my_scc(ir_node *n)
847 if (irn_visited_else_mark(n))
850 /* Initialize the node */
851 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
852 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
853 set_irn_loop(n, NULL);
857 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
858 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
859 so is_backedge does not access array[-1] but correctly returns false! */
861 if (!is_outermost_Start(n)) {
862 int arity = get_irn_arity(n);
864 for (i = get_start_index(n); i < arity; i++) {
866 if (is_backedge(n, i)) continue;
867 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
868 /* if (!m || is_Unknown(m)) continue; */
870 if (irn_is_in_stack(m)) {
871 /* Uplink of m is smaller if n->m is a backedge.
872 Propagate the uplink to mark the loop. */
873 if (get_irn_uplink(m) < get_irn_uplink(n))
874 set_irn_uplink(n, get_irn_uplink(m));
879 if (get_irn_dfn(n) == get_irn_uplink(n)) {
880 /* This condition holds for
881 1) the node with the incoming backedge.
882 That is: We found a loop!
883 2) Straight line code, because no uplink has been propagated, so the
884 uplink still is the same as the dfn.
886 But n might not be a proper loop head for the analysis. Proper loop
887 heads are Block and Phi nodes. find_tail searches the stack for
888 Block's and Phi's and takes those nodes as loop heads for the current
889 loop instead and marks the incoming edge as backedge. */
891 ir_node *tail = find_tail(n);
893 /* We have a loop, that is no straight line code,
894 because we found a loop head!
895 Next actions: Open a new loop on the loop tree and
896 try to find inner loops */
898 #if NO_LOOPS_WITHOUT_HEAD
899 /* This is an adaption of the algorithm from fiasco / optscc to
900 * avoid loops without Block or Phi as first node. This should
901 * severely reduce the number of evaluations of nodes to detect
902 * a fixpoint in the heap analysis.
903 * Further it avoids loops without firm nodes that cause errors
904 * in the heap analyses. */
908 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
916 ir_loop *l = new_loop();
919 /* Remove the loop from the stack ... */
920 pop_scc_unmark_visit(n);
922 /* The current backedge has been marked, that is temporarily eliminated,
923 by find tail. Start the scc algorithm
924 anew on the subgraph that is left (the current loop without the backedge)
925 in order to find more inner loops. */
928 assert(irn_visited(n));
929 #if NO_LOOPS_WITHOUT_HEAD
934 /* No loop head was found, that is we have straightline code.
935 Pop all nodes from the stack to the current loop. */
940 #endif /* INTERPROCEDURAL_VIEW */
942 /* Constructs backedge information for irg. In interprocedural view constructs
943 backedges for all methods called by irg, too. */
944 int construct_backedges(ir_graph *irg)
946 ir_graph *rem = current_ir_graph;
950 assert(!get_interprocedural_view() &&
951 "not implemented, use construct_ip_backedges()");
954 current_ir_graph = irg;
955 outermost_ir_graph = irg;
958 init_scc(irg, &temp);
961 new_loop(); /* sets current_loop */
962 head_rem = current_loop; /* Just for assertion */
964 inc_irg_visited(irg);
966 scc(get_irg_end(irg));
969 obstack_free(&temp, NULL);
971 assert(head_rem == current_loop);
972 mature_loops(current_loop, irg->obst);
973 set_irg_loop(irg, current_loop);
974 set_irg_loopinfo_state(irg, loopinfo_consistent);
975 assert(get_irg_loop(irg)->kind == k_ir_loop);
976 current_ir_graph = rem;
977 return max_loop_depth;
981 #ifdef INTERPROCEDURAL_VIEW
982 int construct_ip_backedges(void)
984 ir_graph *rem = current_ir_graph;
985 int rem_ipv = get_interprocedural_view();
990 assert(get_irp_ip_view_state() == ip_view_valid);
992 outermost_ir_graph = get_irp_main_irg();
998 new_loop(); /* sets current_loop */
999 set_interprocedural_view(1);
1001 inc_max_irg_visited();
1002 for (i = 0; i < get_irp_n_irgs(); i++)
1003 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1005 /** We have to start the walk at the same nodes as cg_walk. **/
1006 /* Walk starting at unreachable procedures. Only these
1007 * have End blocks visible in interprocedural view. */
1008 for (i = 0; i < get_irp_n_irgs(); i++) {
1010 current_ir_graph = get_irp_irg(i);
1012 sb = get_irg_start_block(current_ir_graph);
1014 if ((get_Block_n_cfgpreds(sb) > 1) ||
1015 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
1018 scc(get_irg_end(current_ir_graph));
1021 /* Check whether we walked all procedures: there could be procedures
1022 with cyclic calls but no call from the outside. */
1023 for (i = 0; i < get_irp_n_irgs(); i++) {
1025 current_ir_graph = get_irp_irg(i);
1027 /* Test start block: if inner procedure end and end block are not
1028 * visible and therefore not marked. */
1029 sb = get_irg_start_block(current_ir_graph);
1030 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1033 /* Walk all endless loops in inner procedures.
1034 * We recognize an inner procedure if the End node is not visited. */
1035 for (i = 0; i < get_irp_n_irgs(); i++) {
1037 current_ir_graph = get_irp_irg(i);
1039 e = get_irg_end(current_ir_graph);
1040 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1042 /* Don't visit the End node. */
1043 for (j = 0; j < get_End_n_keepalives(e); j++)
1044 scc(get_End_keepalive(e, j));
1048 set_irg_loop(outermost_ir_graph, current_loop);
1049 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1050 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1052 obstack_free(&temp, NULL);
1053 current_ir_graph = rem;
1054 set_interprocedural_view(rem_ipv);
1055 return max_loop_depth;
1058 void my_construct_ip_backedges(void)
1060 ir_graph *rem = current_ir_graph;
1061 int rem_ipv = get_interprocedural_view();
1064 assert(get_irp_ip_view_state() == ip_view_valid);
1066 outermost_ir_graph = get_irp_main_irg();
1070 current_loop = NULL;
1071 new_loop(); /* sets current_loop */
1072 set_interprocedural_view(1);
1074 inc_max_irg_visited();
1075 for (i = 0; i < get_irp_n_irgs(); i++)
1076 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1078 /** We have to start the walk at the same nodes as cg_walk. **/
1079 /* Walk starting at unreachable procedures. Only these
1080 * have End blocks visible in interprocedural view. */
1081 for (i = 0; i < get_irp_n_irgs(); i++) {
1083 current_ir_graph = get_irp_irg(i);
1085 sb = get_irg_start_block(current_ir_graph);
1087 if ((get_Block_n_cfgpreds(sb) > 1) ||
1088 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1090 my_scc(get_irg_end(current_ir_graph));
1093 /* Check whether we walked all procedures: there could be procedures
1094 with cyclic calls but no call from the outside. */
1095 for (i = 0; i < get_irp_n_irgs(); i++) {
1097 current_ir_graph = get_irp_irg(i);
1099 /* Test start block: if inner procedure end and end block are not
1100 * visible and therefore not marked. */
1101 sb = get_irg_start_block(current_ir_graph);
1102 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1106 /* Walk all endless loops in inner procedures.
1107 * We recognize an inner procedure if the End node is not visited. */
1108 for (i = 0; i < get_irp_n_irgs(); i++) {
1110 current_ir_graph = get_irp_irg(i);
1112 e = get_irg_end(current_ir_graph);
1113 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1115 /* Don't visit the End node. */
1116 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1120 set_irg_loop(outermost_ir_graph, current_loop);
1121 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1122 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1124 current_ir_graph = rem;
1125 set_interprocedural_view(rem_ipv);
1129 static void reset_backedges(ir_node *n)
1131 if (is_possible_loop_head(n)) {
1132 #ifdef INTERPROCEDURAL_VIEW
1133 int rem = get_interprocedural_view();
1135 set_interprocedural_view(1);
1137 set_interprocedural_view(1);
1139 set_interprocedural_view(rem);
1148 static void loop_reset_backedges(ir_loop *l)
1151 reset_backedges(get_loop_node(l, 0));
1152 for (i = 0; i < get_loop_n_nodes(l); ++i)
1153 set_irn_loop(get_loop_node(l, i), NULL);
1154 for (i = 0; i < get_loop_n_sons(l); ++i) {
1155 loop_reset_backedges(get_loop_son(l, i));
1160 static void loop_reset_node(ir_node *n, void *env)
1163 set_irn_loop(n, NULL);
1168 /** Removes all loop information.
1169 Resets all backedges */
1170 void free_loop_information(ir_graph *irg)
1172 /* We can not use this recursion, as the loop might contain
1173 illegal nodes by now. Why else would we throw away the
1175 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1177 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1178 set_irg_loop(irg, NULL);
1179 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1180 /* We cannot free the loop nodes, they are on the obstack. */
1184 void free_all_loop_information(void)
1187 #ifdef INTERPROCEDURAL_VIEW
1188 int rem = get_interprocedural_view();
1189 set_interprocedural_view(1); /* To visit all filter nodes */
1191 for (i = 0; i < get_irp_n_irgs(); i++) {
1192 free_loop_information(get_irp_irg(i));
1194 #ifdef INTERPROCEDURAL_VIEW
1195 set_interprocedural_view(rem);
1199 /* ------------------------------------------------------------------- */
1200 /* Simple analyses based on the loop information */
1201 /* ------------------------------------------------------------------- */
1203 static int is_loop_variant(ir_loop *l, ir_loop *b)
1207 if (l == b) return 1;
1209 n_elems = get_loop_n_elements(l);
1210 for (i = 0; i < n_elems; ++i) {
1211 loop_element e = get_loop_element(l, i);
1212 if (is_ir_loop(e.kind))
1213 if (is_loop_variant(e.son, b))
1220 /* Test whether a value is loop invariant.
1222 * @param n The node to be tested.
1223 * @param block A block node. We pass the block, not the loop as we must
1224 * start off with a block loop to find all proper uses.
1226 * Returns non-zero, if the node n is not changed in the loop block
1227 * belongs to or in inner loops of this blocks loop. */
1228 int is_loop_invariant(const ir_node *n, const ir_node *block)
1230 ir_loop *l = get_irn_loop(block);
1231 const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1232 return !is_loop_variant(l, get_irn_loop(b));