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 return OALLOCZ(obst, scc_info);
95 * Mark node n being on the SCC stack.
97 static inline void mark_irn_in_stack(ir_node *n) {
98 scc_info *scc = get_irn_link(n);
104 * Mark node n NOT being on the SCC stack.
106 static inline void mark_irn_not_in_stack(ir_node *n) {
107 scc_info *scc = get_irn_link(n);
113 * Checks if a node is on the SCC stack.
115 static inline int irn_is_in_stack(ir_node *n) {
116 scc_info *scc = get_irn_link(n);
118 return scc->in_stack;
122 * Sets the uplink number for a node.
124 static inline void set_irn_uplink(ir_node *n, int uplink) {
125 scc_info *scc = get_irn_link(n);
127 scc->uplink = uplink;
131 * Returns the uplink number for a node.
133 static int get_irn_uplink(ir_node *n) {
134 scc_info *scc = get_irn_link(n);
140 * Sets the depth-first-search number for a node.
142 static inline void set_irn_dfn(ir_node *n, int dfn) {
143 scc_info *scc = get_irn_link(n);
149 * Returns the depth-first-search number of a node.
151 static int get_irn_dfn(ir_node *n) {
152 scc_info *scc = get_irn_link(n);
158 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l) {
162 /* Test whether n is contained in this loop. */
163 for (i = 0; i < get_loop_n_nodes(l); i++)
164 if (n == get_loop_node(l, i)) return l;
166 /* Is this a leave in the loop tree? If so loop not found. */
167 if (get_loop_n_sons(l) == 0) return NULL;
169 /* Else descend in the loop tree. */
170 for (i = 0; i < get_loop_n_sons(l); i++) {
171 res = find_nodes_loop(n, get_loop_son(l, i));
177 /* @@@ temporary implementation, costly!!! */
178 ir_loop * get_irn_loop(ir_node *n) {
179 ir_loop *l = get_irg_loop(current_ir_graph);
180 l = find_nodes_loop(n, l);
185 /**********************************************************************/
187 /**********************************************************************/
189 static ir_node **stack = NULL;
190 static int tos = 0; /* top of stack */
193 * initializes the stack
195 static inline void init_stack(void) {
197 ARR_RESIZE(ir_node *, stack, 1000);
199 stack = NEW_ARR_F(ir_node *, 1000);
207 static void finish_stack(void) {
213 * push a node onto the stack
215 * @param n The node to push
217 static inline void push(ir_node *n) {
218 if (tos == ARR_LEN(stack)) {
219 int nlen = ARR_LEN(stack) * 2;
220 ARR_RESIZE(ir_node *, stack, nlen);
223 mark_irn_in_stack(n);
227 * pop a node from the stack
229 * @return The topmost node
231 static inline ir_node *pop(void) {
232 ir_node *n = stack[--tos];
233 mark_irn_not_in_stack(n);
238 * The nodes up to n belong to the current loop.
239 * Removes them from the stack and adds them to the current loop.
241 static inline void pop_scc_to_loop(ir_node *n) {
249 set_irn_dfn(m, loop_node_cnt);
250 add_loop_node(current_loop, m);
251 set_irn_loop(m, current_loop);
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) {
265 int last = get_loop_n_elements(l) - 1;
266 loop_element lelement = get_loop_element(l, last);
267 ir_loop *last_son = lelement.son;
269 if (get_kind(last_son) == k_ir_loop &&
270 get_loop_n_elements(last_son) == 1) {
273 lelement = get_loop_element(last_son, 0);
276 if (get_kind(gson) == k_ir_loop) {
277 loop_element new_last_son;
279 gson->outer_loop = l;
280 new_last_son.son = gson;
281 l->children[last] = new_last_son;
288 /* Removes and unmarks all nodes up to n from the stack.
289 The nodes must be visited once more to assign them to a scc. */
290 static inline void pop_scc_unmark_visit(ir_node *n) {
295 set_irn_visited(m, 0);
299 /**********************************************************************/
300 /* The loop datastructure. **/
301 /**********************************************************************/
303 /* Allocates a new loop as son of current_loop. Sets current_loop
304 to the new loop and returns the father. */
305 static ir_loop *new_loop(void) {
306 ir_loop *father = current_loop;
307 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
309 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
314 /**********************************************************************/
315 /* Constructing and destructing the loop/backedge information. **/
316 /**********************************************************************/
318 /* Initialization steps. **********************************************/
320 static inline void init_node(ir_node *n, void *env) {
321 struct obstack *obst = env;
322 set_irn_link(n, new_scc_info(obst));
326 static inline void init_scc_common(void) {
332 static inline void init_scc(ir_graph *irg, struct obstack *obst) {
334 irg_walk_graph(irg, init_node, NULL, obst);
336 irg_walk (irg, link_to_reg_end, NULL, NULL);
340 static inline void finish_scc(void)
345 #ifdef INTERPROCEDURAL_VIEW
346 static inline void init_ip_scc(struct obstack *obst) {
348 cg_walk(init_node, NULL, obst);
350 #if EXPERIMENTAL_LOOP_TREE
351 cg_walk(link_to_reg_end, NULL, NULL);
357 * Check weather a given node represents the outer most Start
358 * block. In intra-procedural view this is the start block of the
359 * current graph, in interprocedural view it is the start block
360 * of the outer most graph.
362 * @param n the node to check
364 * This is the condition for breaking the scc recursion.
366 static int is_outermost_Start(ir_node *n) {
367 /* Test whether this is the outermost Start node. */
368 if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
369 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
370 if (is_Start(pred) && get_nodes_block(pred) == n)
376 /* When to walk from nodes to blocks. Only for Control flow operations? */
377 static inline int get_start_index(ir_node *n) {
378 #undef BLOCK_BEFORE_NODE
379 #define BLOCK_BEFORE_NODE 1
381 #if BLOCK_BEFORE_NODE
383 /* This version assures, that all nodes are ordered absolutely. This allows
384 to undef all nodes in the heap analysis if the block is false, which means
386 I.e., with this code, the order on the loop tree is correct. But a (single)
387 test showed the loop tree is deeper. */
388 if (get_irn_op(n) == op_Phi ||
390 (is_Filter(n) && get_interprocedural_view()) || (
391 get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
392 get_irn_pinned(n) == op_pin_state_floats
394 // Here we could test for backedge at -1 which is illegal
401 /* This version causes deeper loop trees (at least we verified this
403 But it guarantees that Blocks are analysed before nodes contained in the
404 block. If so, we can set the value to undef if the block is not \
406 if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
415 * Return non-zero if the given node is a legal loop header:
416 * Block, Phi, Filter.
418 * @param n the node to check
420 static inline int is_possible_loop_head(ir_node *n) {
421 ir_op *op = get_irn_op(n);
422 return ((op == op_Block) ||
424 ((op == op_Filter) && get_interprocedural_view()));
428 * Returns non-zero if n is a loop header, i.e., it is a Block, Phi
429 * or Filter node and has predecessors within the loop and out
432 * @param n the node to check
433 * @param root only needed for assertion.
435 static int is_head(ir_node *n, ir_node *root) {
437 int some_outof_loop = 0, some_in_loop = 0;
439 /* Test for legal loop header: Block, Phi, ... */
440 if (!is_possible_loop_head(n))
443 if (!is_outermost_Start(n)) {
445 int uplink = get_irn_uplink(root);
449 arity = get_irn_arity(n);
450 for (i = get_start_index(n); i < arity; i++) {
452 if (is_backedge(n, i))
454 pred = get_irn_n(n, i);
455 if (! irn_is_in_stack(pred)) {
458 assert(get_irn_uplink(pred) >= uplink);
463 return some_outof_loop & some_in_loop;
467 * Returns non-zero if n is possible loop head of an endless loop.
468 * I.e., it is a Block, Phi or Filter node and has only predecessors
471 * @param n the node to check
472 * @param root only needed for assertion.
474 static int is_endless_head(ir_node *n, ir_node *root) {
476 int none_outof_loop = 1, some_in_loop = 0;
478 /* Test for legal loop header: Block, Phi, ... */
479 if (!is_possible_loop_head(n))
482 if (!is_outermost_Start(n)) {
484 int uplink = get_irn_uplink(root);
488 arity = get_irn_arity(n);
489 for (i = get_start_index(n); i < arity; i++) {
491 if (is_backedge(n, i))
493 pred = get_irn_n(n, i);
494 if (!irn_is_in_stack(pred)) {
497 assert(get_irn_uplink(pred) >= uplink);
502 return none_outof_loop & some_in_loop;
505 /** Returns index of the predecessor with the smallest dfn number
506 greater-equal than limit. */
507 static int smallest_dfn_pred(ir_node *n, int limit) {
508 int i, index = -2, min = -1;
510 if (!is_outermost_Start(n)) {
511 int arity = get_irn_arity(n);
512 for (i = get_start_index(n); i < arity; i++) {
513 ir_node *pred = get_irn_n(n, i);
514 if (is_backedge(n, i) || !irn_is_in_stack(pred))
516 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
518 min = get_irn_dfn(pred);
526 * Returns index of the predecessor with the largest dfn number.
528 static int largest_dfn_pred(ir_node *n) {
529 int i, index = -2, max = -1;
531 if (!is_outermost_Start(n)) {
532 int arity = get_irn_arity(n);
533 for (i = get_start_index(n); i < arity; i++) {
534 ir_node *pred = get_irn_n(n, i);
535 if (is_backedge (n, i) || !irn_is_in_stack(pred))
537 if (get_irn_dfn(pred) > max) {
539 max = get_irn_dfn(pred);
547 * Searches the stack for possible loop heads. Tests these for backedges.
548 * If it finds a head with an unmarked backedge it marks this edge and
549 * returns the tail of the loop.
550 * If it finds no backedge returns NULL.
551 * ("disable_backedge" in fiasco)
553 * @param n A node where uplink == dfn.
555 static ir_node *find_tail(ir_node *n) {
557 int i, res_index = -2;
560 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
562 m = stack[tos-1]; /* tos = top of stack */
564 res_index = smallest_dfn_pred(m, 0);
565 if ((res_index == -2) && /* no smallest dfn pred found. */
569 if (m == n) return NULL; // Is this to catch Phi - self loops?
570 for (i = tos-2; i >= 0; --i) {
574 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
575 if (res_index == -2) /* no smallest dfn pred found. */
576 res_index = largest_dfn_pred(m);
578 if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
584 /* We should not walk past our selves on the stack: The upcoming nodes
585 are not in this loop. We assume a loop not reachable from Start. */
593 /* A dead loop not reachable from Start. */
594 for (i = tos-2; i >= 0; --i) {
596 if (is_endless_head(m, n)) {
597 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
598 if (res_index == -2) /* no smallest dfn pred found. */
599 res_index = largest_dfn_pred (m);
602 if (m == n) { break; } /* It's not an unreachable loop, either. */
604 //assert(0 && "no head found on stack");
608 if (res_index <= -2) {
609 /* It's a completely bad loop: without Phi/Block nodes that can
610 be a head. I.e., the code is "dying". We break the loop by
611 setting Bad nodes. */
612 int arity = get_irn_arity(n);
613 ir_node *bad = get_irg_bad(get_irn_irg(n));
614 for (i = -1; i < arity; ++i) {
615 set_irn_n(n, i, bad);
619 assert(res_index > -2);
621 set_backedge(m, res_index);
622 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
626 #if EXPERIMENTAL_LOOP_TREE
628 /* ----------------------------------------------------------------
629 AS: This is experimental code to build loop trees suitable for
630 the heap analysis. Does not work correctly right now... :-(
633 Search in stack for the corresponding first Call-End-ProjX that
634 corresponds to one of the control flow predecessors of the given
635 block, that is the possible callers.
636 returns: the control predecessor to chose\
637 or -1 if no corresponding Call-End-Node could be found
639 - -------------------------------------------------------------- */
641 int search_endproj_in_stack(ir_node *start_block) {
643 assert(is_Block(start_block));
644 for(i = tos - 1; i >= 0; --i)
646 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
647 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
649 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
650 ir_node *end_projx = stack[i];
652 int arity = get_irn_arity(start_block);
653 for(j = 0; j < arity; j++)
655 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
656 get_Proj_proj(end_projx));
657 if(get_irn_n(start_block, j) == begin_projx)
659 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
669 static pmap *projx_link = NULL;
671 void link_to_reg_end (ir_node *n, void *env) {
672 if(get_irn_op(n) == op_Proj &&
673 get_irn_mode(n) == mode_X &&
674 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
675 /* Reg End Projx -> Find the CallBegin Projx and hash it */
676 ir_node *end_projx = n;
677 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
678 get_Proj_proj(end_projx));
679 set_projx_link(begin_projx, end_projx);
683 void set_projx_link(ir_node *cb_projx, ir_node *end_projx) {
684 if(projx_link == NULL)
685 projx_link = pmap_create();
686 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
689 ir_node *get_projx_link(ir_node *cb_projx) {
690 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
695 static inline int is_outermost_loop(ir_loop *l) {
696 return l == get_loop_outer_loop(l);
700 /*-----------------------------------------------------------*
701 * The core algorithm. *
702 *-----------------------------------------------------------*/
705 * The core algorithm: Find strongly coupled components.
707 * @param n node to start
709 static void scc(ir_node *n) {
710 if (irn_visited_else_mark(n))
713 /* Initialize the node */
714 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
715 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
716 set_irn_loop(n, NULL);
720 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
721 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
722 so is_backedge does not access array[-1] but correctly returns false! */
724 if (!is_outermost_Start(n)) {
725 int i, arity = get_irn_arity(n);
727 for (i = get_start_index(n); i < arity; ++i) {
729 if (is_backedge(n, i))
733 if (irn_is_in_stack(m)) {
734 /* Uplink of m is smaller if n->m is a backedge.
735 Propagate the uplink to mark the loop. */
736 if (get_irn_uplink(m) < get_irn_uplink(n))
737 set_irn_uplink(n, get_irn_uplink(m));
742 if (get_irn_dfn(n) == get_irn_uplink(n)) {
743 /* This condition holds for
744 1) the node with the incoming backedge.
745 That is: We found a loop!
746 2) Straight line code, because no uplink has been propagated, so the
747 uplink still is the same as the dfn.
749 But n might not be a proper loop head for the analysis. Proper loop
750 heads are Block and Phi nodes. find_tail() searches the stack for
751 Block's and Phi's and takes those nodes as loop heads for the current
752 loop instead and marks the incoming edge as backedge. */
754 ir_node *tail = find_tail(n);
756 /* We have a loop, that is no straight line code,
757 because we found a loop head!
758 Next actions: Open a new loop on the loop tree and
759 try to find inner loops */
761 #if NO_LOOPS_WITHOUT_HEAD
762 /* This is an adaption of the algorithm from fiasco / optscc to
763 * avoid loops without Block or Phi as first node. This should
764 * severely reduce the number of evaluations of nodes to detect
765 * a fixpoint in the heap analysis.
766 * Further it avoids loops without firm nodes that cause errors
767 * in the heap analyses.
768 * But attention: don't do it for the outermost loop: This loop
769 * is not iterated. A first block can be a loop head in case of
770 * an endless recursion. */
774 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
782 ir_loop *l = new_loop();
785 /* Remove the loop from the stack ... */
786 pop_scc_unmark_visit(n);
788 /* The current backedge has been marked, that is temporarily eliminated,
789 by find tail. Start the scc algorithm
790 again on the subgraph that is left (the current loop without the backedge)
791 in order to find more inner loops. */
794 assert(irn_visited(n));
795 #if NO_LOOPS_WITHOUT_HEAD
800 /* No loop head was found, that is we have straight line code.
801 Pop all nodes from the stack to the current loop. */
807 #ifdef INTERPROCEDURAL_VIEW
808 static void my_scc(ir_node *n) {
810 if (irn_visited_else_mark(n))
813 /* Initialize the node */
814 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
815 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
816 set_irn_loop(n, NULL);
820 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
821 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
822 so is_backedge does not access array[-1] but correctly returns false! */
824 if (!is_outermost_Start(n)) {
825 int arity = get_irn_arity(n);
827 for (i = get_start_index(n); i < arity; i++) {
829 if (is_backedge(n, i)) continue;
830 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
831 /* if (!m || is_Unknown(m)) continue; */
833 if (irn_is_in_stack(m)) {
834 /* Uplink of m is smaller if n->m is a backedge.
835 Propagate the uplink to mark the loop. */
836 if (get_irn_uplink(m) < get_irn_uplink(n))
837 set_irn_uplink(n, get_irn_uplink(m));
842 if (get_irn_dfn(n) == get_irn_uplink(n)) {
843 /* This condition holds for
844 1) the node with the incoming backedge.
845 That is: We found a loop!
846 2) Straight line code, because no uplink has been propagated, so the
847 uplink still is the same as the dfn.
849 But n might not be a proper loop head for the analysis. Proper loop
850 heads are Block and Phi nodes. find_tail searches the stack for
851 Block's and Phi's and takes those nodes as loop heads for the current
852 loop instead and marks the incoming edge as backedge. */
854 ir_node *tail = find_tail(n);
856 /* We have a loop, that is no straight line code,
857 because we found a loop head!
858 Next actions: Open a new loop on the loop tree and
859 try to find inner loops */
861 #if NO_LOOPS_WITHOUT_HEAD
862 /* This is an adaption of the algorithm from fiasco / optscc to
863 * avoid loops without Block or Phi as first node. This should
864 * severely reduce the number of evaluations of nodes to detect
865 * a fixpoint in the heap analysis.
866 * Further it avoids loops without firm nodes that cause errors
867 * in the heap analyses. */
871 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
879 ir_loop *l = new_loop();
882 /* Remove the loop from the stack ... */
883 pop_scc_unmark_visit(n);
885 /* The current backedge has been marked, that is temporarily eliminated,
886 by find tail. Start the scc algorithm
887 anew on the subgraph that is left (the current loop without the backedge)
888 in order to find more inner loops. */
891 assert(irn_visited(n));
892 #if NO_LOOPS_WITHOUT_HEAD
897 /* No loop head was found, that is we have straightline code.
898 Pop all nodes from the stack to the current loop. */
903 #endif /* INTERPROCEDURAL_VIEW */
905 /* Constructs backedge information for irg. In interprocedural view constructs
906 backedges for all methods called by irg, too. */
907 int construct_backedges(ir_graph *irg) {
908 ir_graph *rem = current_ir_graph;
912 assert(!get_interprocedural_view() &&
913 "not implemented, use construct_ip_backedges()");
916 current_ir_graph = irg;
917 outermost_ir_graph = irg;
920 init_scc(irg, &temp);
923 new_loop(); /* sets current_loop */
924 head_rem = current_loop; /* Just for assertion */
926 inc_irg_visited(irg);
928 scc(get_irg_end(irg));
931 obstack_free(&temp, NULL);
933 assert(head_rem == current_loop);
934 mature_loops(current_loop, irg->obst);
935 set_irg_loop(irg, current_loop);
936 set_irg_loopinfo_state(irg, loopinfo_consistent);
937 assert(get_irg_loop(irg)->kind == k_ir_loop);
938 current_ir_graph = rem;
939 return max_loop_depth;
943 #ifdef INTERPROCEDURAL_VIEW
944 int construct_ip_backedges(void) {
945 ir_graph *rem = current_ir_graph;
946 int rem_ipv = get_interprocedural_view();
951 assert(get_irp_ip_view_state() == ip_view_valid);
953 outermost_ir_graph = get_irp_main_irg();
959 new_loop(); /* sets current_loop */
960 set_interprocedural_view(1);
962 inc_max_irg_visited();
963 for (i = 0; i < get_irp_n_irgs(); i++)
964 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
966 /** We have to start the walk at the same nodes as cg_walk. **/
967 /* Walk starting at unreachable procedures. Only these
968 * have End blocks visible in interprocedural view. */
969 for (i = 0; i < get_irp_n_irgs(); i++) {
971 current_ir_graph = get_irp_irg(i);
973 sb = get_irg_start_block(current_ir_graph);
975 if ((get_Block_n_cfgpreds(sb) > 1) ||
976 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb))
979 scc(get_irg_end(current_ir_graph));
982 /* Check whether we walked all procedures: there could be procedures
983 with cyclic calls but no call from the outside. */
984 for (i = 0; i < get_irp_n_irgs(); i++) {
986 current_ir_graph = get_irp_irg(i);
988 /* Test start block: if inner procedure end and end block are not
989 * visible and therefore not marked. */
990 sb = get_irg_start_block(current_ir_graph);
991 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
994 /* Walk all endless loops in inner procedures.
995 * We recognize an inner procedure if the End node is not visited. */
996 for (i = 0; i < get_irp_n_irgs(); i++) {
998 current_ir_graph = get_irp_irg(i);
1000 e = get_irg_end(current_ir_graph);
1001 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1003 /* Don't visit the End node. */
1004 for (j = 0; j < get_End_n_keepalives(e); j++)
1005 scc(get_End_keepalive(e, j));
1009 set_irg_loop(outermost_ir_graph, current_loop);
1010 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1011 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1013 obstack_free(&temp, NULL);
1014 current_ir_graph = rem;
1015 set_interprocedural_view(rem_ipv);
1016 return max_loop_depth;
1019 void my_construct_ip_backedges(void) {
1020 ir_graph *rem = current_ir_graph;
1021 int rem_ipv = get_interprocedural_view();
1024 assert(get_irp_ip_view_state() == ip_view_valid);
1026 outermost_ir_graph = get_irp_main_irg();
1030 current_loop = NULL;
1031 new_loop(); /* sets current_loop */
1032 set_interprocedural_view(1);
1034 inc_max_irg_visited();
1035 for (i = 0; i < get_irp_n_irgs(); i++)
1036 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1038 /** We have to start the walk at the same nodes as cg_walk. **/
1039 /* Walk starting at unreachable procedures. Only these
1040 * have End blocks visible in interprocedural view. */
1041 for (i = 0; i < get_irp_n_irgs(); i++) {
1043 current_ir_graph = get_irp_irg(i);
1045 sb = get_irg_start_block(current_ir_graph);
1047 if ((get_Block_n_cfgpreds(sb) > 1) ||
1048 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1050 my_scc(get_irg_end(current_ir_graph));
1053 /* Check whether we walked all procedures: there could be procedures
1054 with cyclic calls but no call from the outside. */
1055 for (i = 0; i < get_irp_n_irgs(); i++) {
1057 current_ir_graph = get_irp_irg(i);
1059 /* Test start block: if inner procedure end and end block are not
1060 * visible and therefore not marked. */
1061 sb = get_irg_start_block(current_ir_graph);
1062 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph))
1066 /* Walk all endless loops in inner procedures.
1067 * We recognize an inner procedure if the End node is not visited. */
1068 for (i = 0; i < get_irp_n_irgs(); i++) {
1070 current_ir_graph = get_irp_irg(i);
1072 e = get_irg_end(current_ir_graph);
1073 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1075 /* Don't visit the End node. */
1076 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1080 set_irg_loop(outermost_ir_graph, current_loop);
1081 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1082 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1084 current_ir_graph = rem;
1085 set_interprocedural_view(rem_ipv);
1089 static void reset_backedges(ir_node *n) {
1090 if (is_possible_loop_head(n)) {
1091 #ifdef INTERPROCEDURAL_VIEW
1092 int rem = get_interprocedural_view();
1094 set_interprocedural_view(1);
1096 set_interprocedural_view(1);
1098 set_interprocedural_view(rem);
1107 static void loop_reset_backedges(ir_loop *l) {
1109 reset_backedges(get_loop_node(l, 0));
1110 for (i = 0; i < get_loop_n_nodes(l); ++i)
1111 set_irn_loop(get_loop_node(l, i), NULL);
1112 for (i = 0; i < get_loop_n_sons(l); ++i) {
1113 loop_reset_backedges(get_loop_son(l, i));
1118 static void loop_reset_node(ir_node *n, void *env) {
1120 set_irn_loop(n, NULL);
1125 /** Removes all loop information.
1126 Resets all backedges */
1127 void free_loop_information(ir_graph *irg) {
1128 /* We can not use this recursion, as the loop might contain
1129 illegal nodes by now. Why else would we throw away the
1131 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1133 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1134 set_irg_loop(irg, NULL);
1135 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1136 /* We cannot free the loop nodes, they are on the obstack. */
1140 void free_all_loop_information(void) {
1142 #ifdef INTERPROCEDURAL_VIEW
1143 int rem = get_interprocedural_view();
1144 set_interprocedural_view(1); /* To visit all filter nodes */
1146 for (i = 0; i < get_irp_n_irgs(); i++) {
1147 free_loop_information(get_irp_irg(i));
1149 #ifdef INTERPROCEDURAL_VIEW
1150 set_interprocedural_view(rem);
1158 /* Debug stuff *************************************************/
1160 static int test_loop_node(ir_loop *l) {
1161 int i, has_node = 0, found_problem = 0;
1164 assert(l && l->kind == k_ir_loop);
1166 if (get_loop_n_elements(l) == 0) {
1168 dump_loop(l, "-ha");
1171 le = get_loop_element(l, 0);
1172 if (*(le.kind) != k_ir_node) {
1173 assert(le.kind && *(le.kind) == k_ir_loop);
1176 dump_loop(l, "-ha");
1179 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1181 dump_loop(l, "-ha");
1184 if ((get_loop_depth(l) != 0) &&
1185 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1187 dump_loop(l, "-ha");
1192 for (i = 0; i < get_loop_n_elements(l); ++i) {
1193 le = get_loop_element(l, i);
1194 if (*(le.kind) == k_ir_node)
1197 if (test_loop_node(le.son)) found_problem = 1;
1200 if (has_node == 0) {
1202 dump_loop(l, "-ha");
1205 return found_problem;
1208 /** Prints all loop nodes that
1209 * - do not have any firm nodes, only loop sons
1210 * - the header is not a Phi, Block or Filter.
1212 void find_strange_loop_nodes(ir_loop *l) {
1213 int found_problem = 0;
1214 found_problem = test_loop_node(l);
1215 printf("Finished Test\n\n");
1216 if (found_problem) exit(0);
1220 /* ------------------------------------------------------------------- */
1221 /* Simple analyses based on the loop information */
1222 /* ------------------------------------------------------------------- */
1224 int is_loop_variant(ir_loop *l, ir_loop *b) {
1227 if (l == b) return 1;
1229 n_elems = get_loop_n_elements(l);
1230 for (i = 0; i < n_elems; ++i) {
1231 loop_element e = get_loop_element(l, i);
1232 if (is_ir_loop(e.kind))
1233 if (is_loop_variant(e.son, b))
1240 /* Test whether a value is loop invariant.
1242 * @param n The node to be tested.
1243 * @param block A block node. We pass the block, not the loop as we must
1244 * start off with a block loop to find all proper uses.
1246 * Returns non-zero, if the node n is not changed in the loop block
1247 * belongs to or in inner loops of this blocks loop. */
1248 int is_loop_invariant(const ir_node *n, const ir_node *block) {
1249 ir_loop *l = get_irn_loop(block);
1250 const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
1251 return !is_loop_variant(l, get_irn_loop(b));