2 * Copyright (C) 1995-2007 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
44 #include "irgraph_t.h"
52 /* A variant of the loop tree that avoids loops without head.
53 This reduces the depth of the loop tree. */
54 #define NO_LOOPS_WITHOUT_HEAD 1
56 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
58 static ir_loop *current_loop; /* Current loop construction is working
60 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
61 Each loop node gets a unique number.
62 What for? ev. remove. @@@ */
63 static int current_dfn = 1; /* Counter to generate depth first numbering
66 static int max_loop_depth = 0;
68 void link_to_reg_end (ir_node *n, void *env);
69 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
70 ir_node *get_projx_link(ir_node *cb_projx);
72 /**********************************************************************/
73 /* Node attributes **/
74 /**********************************************************************/
76 /**********************************************************************/
77 /* Node attributes needed for the construction. **/
78 /**********************************************************************/
80 typedef struct scc_info {
81 int in_stack; /**< Marks whether node is on the stack. */
82 int dfn; /**< Depth first search number. */
83 int uplink; /**< dfn number of ancestor. */
84 /* ir_loop *loop; *//* Refers to the containing loop. */
86 struct section *section;
92 static INLINE scc_info* new_scc_info(void) {
93 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
94 memset (info, 0, sizeof (scc_info));
99 mark_irn_in_stack (ir_node *n) {
100 scc_info *scc = get_irn_link(n);
106 mark_irn_not_in_stack (ir_node *n) {
107 scc_info *scc = get_irn_link(n);
113 irn_is_in_stack (ir_node *n) {
114 scc_info *scc = get_irn_link(n);
116 return scc->in_stack;
120 set_irn_uplink (ir_node *n, int uplink) {
121 scc_info *scc = get_irn_link(n);
123 scc->uplink = uplink;
127 get_irn_uplink (ir_node *n) {
128 scc_info *scc = get_irn_link(n);
134 set_irn_dfn (ir_node *n, int dfn) {
135 scc_info *scc = get_irn_link(n);
141 get_irn_dfn (ir_node *n) {
142 scc_info *scc = get_irn_link(n);
149 set_irn_loop (ir_node *n, ir_loop *loop) {
153 /* Uses temporary information to get the loop */
154 ir_loop *(get_irn_loop)(const ir_node *n) {
155 return _get_irn_loop(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);
207 static INLINE void free_stack(void) {
215 * push a node onto the stack
217 * @param n The node to push
224 if (tos == ARR_LEN (stack)) {
225 int nlen = ARR_LEN (stack) * 2;
226 ARR_RESIZE (ir_node *, stack, nlen);
229 mark_irn_in_stack(n);
233 * pop a node from the stack
235 * @return The topmost node
237 static INLINE ir_node *
240 ir_node *n = stack[--tos];
241 mark_irn_not_in_stack(n);
246 * The nodes up to n belong to the current loop.
247 * Removes them from the stack and adds them to the current loop.
250 pop_scc_to_loop (ir_node *n)
258 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
261 set_irn_dfn(m, loop_node_cnt);
262 add_loop_node(current_loop, m);
263 set_irn_loop(m, current_loop);
266 /* if (m==n) break;*/
269 /* i might be bigger than 1 for dead (and that's why bad) loops */
271 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
275 /* GL ??? my last son is my grandson??? Removes loops with no
276 ir_nodes in them. Such loops have only another loop as son. (Why
277 can't they have two loops as sons? Does it never get that far? ) */
278 static void close_loop (ir_loop *l)
280 int last = get_loop_n_elements(l) - 1;
281 loop_element lelement = get_loop_element(l, last);
282 ir_loop *last_son = lelement.son;
284 if (get_kind(last_son) == k_ir_loop &&
285 get_loop_n_elements(last_son) == 1) {
288 lelement = get_loop_element(last_son, 0);
291 if (get_kind(gson) == k_ir_loop) {
292 loop_element new_last_son;
294 gson->outer_loop = l;
295 new_last_son.son = gson;
296 l->children[last] = new_last_son;
303 /* Removes and unmarks all nodes up to n from the stack.
304 The nodes must be visited once more to assign them to a scc. */
306 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 ir_loop *new_loop (void) {
323 ir_loop *father, *son;
325 father = current_loop;
327 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
328 memset (son, 0, sizeof (ir_loop));
329 son->kind = k_ir_loop;
330 son->children = NEW_ARR_F (loop_element, 0);
334 son->outer_loop = father;
335 add_loop_son(father, son);
336 son->depth = father->depth+1;
337 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
338 } else { /* The root loop */
339 son->outer_loop = son;
344 son->loop_nr = get_irp_new_node_nr();
353 /* Finishes the datastructures, copies the arrays to the obstack
355 A. Schoesser: Caution: loop -> sons is gone. */
356 static void mature_loop (ir_loop *loop) {
359 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
360 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
361 DEL_ARR_F(loop->sons);
362 loop->sons = new_sons;
366 /* Returns outer loop, itself if outermost. */
367 ir_loop *(get_loop_outer_loop)(const ir_loop *loop) {
368 return _get_loop_outer_loop(loop);
371 /* Returns nesting depth of this loop */
372 int (get_loop_depth)(const ir_loop *loop) {
373 return _get_loop_depth(loop);
376 /* Returns the number of inner loops */
377 int (get_loop_n_sons)(const ir_loop *loop) {
378 return _get_loop_n_sons(loop);
381 /* Returns the pos`th loop_node-child *
382 * TODO: This method isn`t very efficient ! *
383 * Returns NULL if there isn`t a pos`th loop_node */
384 ir_loop *get_loop_son (ir_loop *loop, int pos) {
385 int child_nr = 0, loop_nr = -1;
387 assert(loop && loop->kind == k_ir_loop);
388 while(child_nr < ARR_LEN(loop->children))
390 if(*(loop -> children[child_nr].kind) == k_ir_loop)
393 return(loop -> children[child_nr].son);
399 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
403 add_loop_son(ir_loop *loop, ir_loop *son) {
406 assert(loop && loop->kind == k_ir_loop);
407 assert(get_kind(son) == k_ir_loop);
408 ARR_APP1 (loop_element, loop->children, lson);
412 /* Returns the number of nodes in the loop */
413 int get_loop_n_nodes (ir_loop *loop) {
414 assert(loop); assert(loop->kind == k_ir_loop);
415 return loop -> n_nodes;
416 /* return ARR_LEN(loop->nodes); */
419 /* Returns the pos`th ir_node-child *
420 * TODO: This method isn`t very efficient ! *
421 * Returns NULL if there isn`t a pos`th ir_node */
422 ir_node *get_loop_node (ir_loop *loop, int pos) {
423 int child_nr, node_nr = -1;
425 assert(loop && loop->kind == k_ir_loop);
426 assert(pos < get_loop_n_nodes(loop));
428 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
429 if(*(loop -> children[child_nr].kind) == k_ir_node)
432 return(loop -> children[child_nr].node);
435 printf("pos: %d\n", pos);
436 assert(0 && "no child at pos found");
440 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
444 add_loop_node(ir_loop *loop, ir_node *n) {
447 assert(loop && loop->kind == k_ir_loop);
448 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
449 ARR_APP1 (loop_element, loop->children, ln);
453 /* Returns the number of elements contained in loop. */
454 int get_loop_n_elements (const ir_loop *loop) {
455 assert(loop && loop->kind == k_ir_loop);
456 return(ARR_LEN(loop->children));
460 Returns the pos`th loop element.
461 This may be a loop_node or a ir_node. The caller of this function has
462 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
463 and then select the appropriate "loop_element.node" or "loop_element.son".
466 loop_element get_loop_element(const ir_loop *loop, int pos) {
467 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
468 return(loop -> children[pos]);
471 int get_loop_element_pos(const ir_loop *loop, void *le) {
473 assert(loop && loop->kind == k_ir_loop);
475 n = get_loop_n_elements(loop);
476 for (i = 0; i < n; i++)
477 if (get_loop_element(loop, i).node == le) return i;
481 int get_loop_loop_nr(const ir_loop *loop) {
482 assert(loop && loop->kind == k_ir_loop);
484 return loop->loop_nr;
491 /** A field to connect additional information to a loop. Only valid
492 if libfirm_debug is set. */
493 void set_loop_link (ir_loop *loop, void *link) {
494 assert(loop && loop->kind == k_ir_loop);
499 void *get_loop_link (const ir_loop *loop) {
500 assert(loop && loop->kind == k_ir_loop);
508 int (is_ir_loop)(const void *thing) {
509 return _is_ir_loop(thing);
512 /* The outermost loop is remarked in the surrounding graph. */
513 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
514 _set_irg_loop(irg, loop);
517 /* Returns the root loop info (if exists) for an irg. */
518 ir_loop *(get_irg_loop)(ir_graph *irg) {
519 return _get_irg_loop(irg);
523 /**********************************************************************/
524 /* Constructing and destructing the loop/backedge information. **/
525 /**********************************************************************/
527 /* Initialization steps. **********************************************/
530 init_node (ir_node *n, void *env) {
531 set_irn_link (n, new_scc_info());
536 init_scc_common (void) {
543 init_scc (ir_graph *irg) {
545 irg_walk_graph (irg, init_node, NULL, NULL);
547 irg_walk (irg, link_to_reg_end, NULL, NULL);
554 cg_walk (init_node, NULL, NULL);
556 #if EXPERIMENTAL_LOOP_TREE
557 cg_walk (link_to_reg_end, NULL, NULL);
561 /* Condition for breaking the recursion. */
562 static int is_outermost_Start(ir_node *n) {
563 /* Test whether this is the outermost Start node. If so
564 recursion must end. */
565 if ((get_irn_op(n) == op_Block) &&
566 (get_Block_n_cfgpreds(n) == 1) &&
567 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
568 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
572 /* @@@ Bad condition:
573 not possible in interprocedural view as outermost_graph is
574 not necessarily the only with a dead-end start block.
575 Besides current_ir_graph is not set properly. */
576 if ((get_irn_op(n) == op_Block) &&
577 (n == get_irg_start_block(current_ir_graph))) {
578 if ((!get_interprocedural_view()) ||
579 (current_ir_graph == outermost_ir_graph))
586 /* When to walk from nodes to blocks. Only for Control flow operations? */
588 get_start_index(ir_node *n) {
589 #undef BLOCK_BEFORE_NODE
590 #define BLOCK_BEFORE_NODE 1
592 #if BLOCK_BEFORE_NODE
594 /* This version assures, that all nodes are ordered absolutely. This allows
595 to undef all nodes in the heap analysis if the block is false, which means
597 I.e., with this code, the order on the loop tree is correct. But a (single)
598 test showed the loop tree is deeper. */
599 if (get_irn_op(n) == op_Phi ||
600 get_irn_op(n) == op_Block ||
601 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
602 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
603 get_irn_pinned(n) == op_pin_state_floats))
604 // Here we could test for backedge at -1 which is illegal
611 /* This version causes deeper loop trees (at least we verified this
613 But it guarantees that Blocks are analysed before nodes contained in the
614 block. If so, we can set the value to undef if the block is not \
616 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
626 static void test(ir_node *pred, ir_node *root, ir_node *this) {
628 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
630 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
631 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
632 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
634 printf("tos: %d\n", tos);
636 for (i = tos; i >= 0; i--) {
637 ir_node *n = stack[i];
639 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
644 /* Test for legal loop header: Block, Phi, ... */
645 static INLINE int is_possible_loop_head(ir_node *n) {
646 ir_op *op = get_irn_op(n);
647 return ((op == op_Block) ||
649 ((op == op_Filter) && get_interprocedural_view()));
652 /* Returns non-zero if n is a loop header, i.e., it is a Block, Phi
653 or Filter node and has predecessors within the loop and out
655 @arg root: only needed for assertion. */
657 is_head (ir_node *n, ir_node *root)
660 int some_outof_loop = 0, some_in_loop = 0;
662 /* Test for legal loop header: Block, Phi, ... */
663 if (!is_possible_loop_head(n))
666 if (!is_outermost_Start(n)) {
667 arity = get_irn_arity(n);
668 for (i = get_start_index(n); i < arity; i++) {
669 ir_node *pred = get_irn_n(n, i);
671 if (is_backedge(n, i)) continue;
672 if (!irn_is_in_stack(pred)) {
675 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
676 DDMN(n); DDMN(pred); DDMN(root);
677 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
683 return some_outof_loop && some_in_loop;
687 * Returns non-zero if n is possible loop head of an endless loop.
688 * I.e., it is a Block, Phi or Filter node and has only predecessors
690 * @param root: only needed for assertion.
693 is_endless_head (ir_node *n, ir_node *root)
696 int some_outof_loop = 0, some_in_loop = 0;
698 /* Test for legal loop header: Block, Phi, ... */
699 if (!is_possible_loop_head(n))
702 if (!is_outermost_Start(n)) {
703 arity = get_irn_arity(n);
704 for (i = get_start_index(n); i < arity; i++) {
705 ir_node *pred = get_irn_n(n, i);
707 if (is_backedge(n, i)) { continue; }
708 if (!irn_is_in_stack(pred)) {
709 some_outof_loop = 1; //printf(" some out of loop ");
711 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
712 DDMN(pred); DDMN(root);
713 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
719 return !some_outof_loop && some_in_loop;
722 /* Returns index of the predecessor with the smallest dfn number
723 greater-equal than limit. */
725 smallest_dfn_pred (ir_node *n, int limit)
727 int i, index = -2, min = -1;
729 if (!is_outermost_Start(n)) {
730 int arity = get_irn_arity(n);
731 for (i = get_start_index(n); i < arity; i++) {
732 ir_node *pred = get_irn_n(n, i);
734 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
735 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
737 min = get_irn_dfn(pred);
744 /* Returns index of the predecessor with the largest dfn number. */
746 largest_dfn_pred (ir_node *n)
748 int i, index = -2, max = -1;
750 if (!is_outermost_Start(n)) {
751 int arity = get_irn_arity(n);
752 for (i = get_start_index(n); i < arity; i++) {
753 ir_node *pred = get_irn_n(n, i);
754 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
755 if (get_irn_dfn(pred) > max) {
757 max = get_irn_dfn(pred);
764 /** Searches the stack for possible loop heads. Tests these for backedges.
765 If it finds a head with an unmarked backedge it marks this edge and
766 returns the tail of the loop.
767 If it finds no backedge returns NULL.
768 ("disable_backedge" in fiasco)
770 * @param n A node where uplink == dfn.
774 find_tail (ir_node *n) {
776 int i, res_index = -2;
779 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
781 m = stack[tos-1]; /* tos = top of stack */
782 if (is_head (m, n)) {
783 res_index = smallest_dfn_pred(m, 0);
784 if ((res_index == -2) && /* no smallest dfn pred found. */
788 if (m == n) return NULL; // Is this to catch Phi - self loops?
789 for (i = tos-2; i >= 0; --i) {
792 if (is_head (m, n)) {
793 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
794 if (res_index == -2) /* no smallest dfn pred found. */
795 res_index = largest_dfn_pred (m);
797 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
803 /* We should not walk past our selves on the stack: The upcoming nodes
804 are not in this loop. We assume a loop not reachable from Start. */
813 /* A dead loop not reachable from Start. */
814 for (i = tos-2; i >= 0; --i) {
816 if (is_endless_head (m, n)) {
817 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
818 if (res_index == -2) /* no smallest dfn pred found. */
819 res_index = largest_dfn_pred (m);
822 if (m == n) { break; } /* It's not an unreachable loop, either. */
824 //assert(0 && "no head found on stack");
828 if (res_index <= -2) {
829 /* It's a completely bad loop: without Phi/Block nodes that can
830 be a head. I.e., the code is "dying". We break the loop by
831 setting Bad nodes. */
832 int arity = get_irn_arity(n);
833 for (i = -1; i < arity; ++i) {
834 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
838 assert (res_index > -2);
840 set_backedge (m, res_index);
841 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
845 #if EXPERIMENTAL_LOOP_TREE
847 /* ----------------------------------------------------------------
848 AS: This is experimental code to build loop trees suitable for
849 the heap analysis. Does not work correctly right now... :-(
852 Search in stack for the corresponding first Call-End-ProjX that
853 corresponds to one of the control flow predecessors of the given
854 block, that is the possible callers.
855 returns: the control predecessor to chose\
856 or -1 if no corresponding Call-End-Node could be found
858 - -------------------------------------------------------------- */
860 int search_endproj_in_stack(ir_node *start_block)
863 assert(is_Block(start_block));
864 for(i = tos - 1; i >= 0; --i)
867 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
868 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
870 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
871 ir_node *end_projx = stack[i];
873 int arity = get_irn_arity(start_block);
874 for(j = 0; j < arity; j++)
876 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
877 get_Proj_proj(end_projx));
879 if(get_irn_n(start_block, j) == begin_projx)
881 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
891 static pmap *projx_link = NULL;
893 void link_to_reg_end (ir_node *n, void *env) {
894 if(get_irn_op(n) == op_Proj &&
895 get_irn_mode(n) == mode_X &&
896 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
897 /* Reg End Projx -> Find the CallBegin Projx and hash it */
898 ir_node *end_projx = n;
899 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
900 get_Proj_proj(end_projx));
901 printf("Linked the following ProjxNodes:\n");
904 set_projx_link(begin_projx, end_projx);
908 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
910 if(projx_link == NULL)
911 projx_link = pmap_create();
912 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
915 ir_node *get_projx_link(ir_node *cb_projx)
917 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
923 is_outermost_loop(ir_loop *l) {
924 return l == get_loop_outer_loop(l);
928 /*-----------------------------------------------------------*
929 * The core algorithm. *
930 *-----------------------------------------------------------*/
932 static void scc (ir_node *n) {
934 if (irn_visited(n)) return;
937 /* Initialize the node */
938 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
939 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
940 set_irn_loop(n, NULL);
944 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
945 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
946 so is_backedge does not access array[-1] but correctly returns false! */
948 if (!is_outermost_Start(n)) {
949 int arity = get_irn_arity(n);
951 for (i = get_start_index(n); i < arity; i++) {
953 if (is_backedge(n, i)) continue;
954 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
955 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
957 if (irn_is_in_stack(m)) {
958 /* Uplink of m is smaller if n->m is a backedge.
959 Propagate the uplink to mark the loop. */
960 if (get_irn_uplink(m) < get_irn_uplink(n))
961 set_irn_uplink(n, get_irn_uplink(m));
966 if (get_irn_dfn(n) == get_irn_uplink(n)) {
967 /* This condition holds for
968 1) the node with the incoming backedge.
969 That is: We found a loop!
970 2) Straight line code, because no uplink has been propagated, so the
971 uplink still is the same as the dfn.
973 But n might not be a proper loop head for the analysis. Proper loop
974 heads are Block and Phi nodes. find_tail searches the stack for
975 Block's and Phi's and takes those nodes as loop heads for the current
976 loop instead and marks the incoming edge as backedge. */
978 ir_node *tail = find_tail(n);
980 /* We have a loop, that is no straight line code,
981 because we found a loop head!
982 Next actions: Open a new loop on the loop tree and
983 try to find inner loops */
985 #if NO_LOOPS_WITHOUT_HEAD
986 /* This is an adaption of the algorithm from fiasco / optscc to
987 * avoid loops without Block or Phi as first node. This should
988 * severely reduce the number of evaluations of nodes to detect
989 * a fixpoint in the heap analysis.
990 * Further it avoids loops without firm nodes that cause errors
991 * in the heap analyses.
992 * But attention: don't do it for the outermost loop: This loop
993 * is not iterated. A first block can be a loop head in case of
994 * an endless recursion. */
998 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1006 ir_loop *l = new_loop();
1009 /* Remove the loop from the stack ... */
1010 pop_scc_unmark_visit (n);
1012 /* The current backedge has been marked, that is temporarily eliminated,
1013 by find tail. Start the scc algorithm
1014 anew on the subgraph that is left (the current loop without the backedge)
1015 in order to find more inner loops. */
1018 assert (irn_visited(n));
1019 #if NO_LOOPS_WITHOUT_HEAD
1026 /* No loop head was found, that is we have straightline code.
1027 Pop all nodes from the stack to the current loop. */
1033 static void my_scc (ir_node *n) {
1035 if (irn_visited(n)) return;
1036 mark_irn_visited(n);
1038 /* Initialize the node */
1039 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1040 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1041 set_irn_loop(n, NULL);
1045 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1046 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1047 so is_backedge does not access array[-1] but correctly returns false! */
1049 if (!is_outermost_Start(n)) {
1050 int arity = get_irn_arity(n);
1052 for (i = get_start_index(n); i < arity; i++) {
1054 if (is_backedge(n, i)) continue;
1055 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1056 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1058 if (irn_is_in_stack(m)) {
1059 /* Uplink of m is smaller if n->m is a backedge.
1060 Propagate the uplink to mark the loop. */
1061 if (get_irn_uplink(m) < get_irn_uplink(n))
1062 set_irn_uplink(n, get_irn_uplink(m));
1067 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1068 /* This condition holds for
1069 1) the node with the incoming backedge.
1070 That is: We found a loop!
1071 2) Straight line code, because no uplink has been propagated, so the
1072 uplink still is the same as the dfn.
1074 But n might not be a proper loop head for the analysis. Proper loop
1075 heads are Block and Phi nodes. find_tail searches the stack for
1076 Block's and Phi's and takes those nodes as loop heads for the current
1077 loop instead and marks the incoming edge as backedge. */
1079 ir_node *tail = find_tail(n);
1081 /* We have a loop, that is no straight line code,
1082 because we found a loop head!
1083 Next actions: Open a new loop on the loop tree and
1084 try to find inner loops */
1086 #if NO_LOOPS_WITHOUT_HEAD
1087 /* This is an adaption of the algorithm from fiasco / optscc to
1088 * avoid loops without Block or Phi as first node. This should
1089 * severely reduce the number of evaluations of nodes to detect
1090 * a fixpoint in the heap analysis.
1091 * Further it avoids loops without firm nodes that cause errors
1092 * in the heap analyses. */
1096 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1104 ir_loop *l = new_loop();
1107 /* Remove the loop from the stack ... */
1108 pop_scc_unmark_visit (n);
1110 /* The current backedge has been marked, that is temporarily eliminated,
1111 by find tail. Start the scc algorithm
1112 anew on the subgraph that is left (the current loop without the backedge)
1113 in order to find more inner loops. */
1116 assert (irn_visited(n));
1117 #if NO_LOOPS_WITHOUT_HEAD
1124 /* No loop head was found, that is we have straightline code.
1125 Pop all nodes from the stack to the current loop. */
1131 /* Constructs backedge information for irg. In interprocedural view constructs
1132 backedges for all methods called by irg, too. */
1133 int construct_backedges(ir_graph *irg) {
1134 ir_graph *rem = current_ir_graph;
1137 assert(!get_interprocedural_view() &&
1138 "not implemented, use construct_ip_backedges");
1141 current_ir_graph = irg;
1142 outermost_ir_graph = irg;
1144 init_scc(current_ir_graph);
1146 current_loop = NULL;
1147 new_loop(); /* sets current_loop */
1148 head_rem = current_loop; /* Just for assertion */
1150 inc_irg_visited(current_ir_graph);
1152 scc(get_irg_end(current_ir_graph));
1154 assert(head_rem == current_loop);
1155 set_irg_loop(current_ir_graph, current_loop);
1156 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1157 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1159 irg->loops = current_loop;
1163 count_loop (the_loop, &count, &depth);
1167 current_ir_graph = rem;
1169 return max_loop_depth;
1173 int construct_ip_backedges (void) {
1174 ir_graph *rem = current_ir_graph;
1175 int rem_ipv = get_interprocedural_view();
1179 assert(get_irp_ip_view_state() == ip_view_valid);
1181 outermost_ir_graph = get_irp_main_irg();
1185 current_loop = NULL;
1186 new_loop(); /* sets current_loop */
1187 set_interprocedural_view(1);
1189 inc_max_irg_visited();
1190 for (i = 0; i < get_irp_n_irgs(); i++)
1191 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1193 /** We have to start the walk at the same nodes as cg_walk. **/
1194 /* Walk starting at unreachable procedures. Only these
1195 * have End blocks visible in interprocedural view. */
1196 for (i = 0; i < get_irp_n_irgs(); i++) {
1198 current_ir_graph = get_irp_irg(i);
1200 sb = get_irg_start_block(current_ir_graph);
1202 if ((get_Block_n_cfgpreds(sb) > 1) ||
1203 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1205 scc(get_irg_end(current_ir_graph));
1208 /* Check whether we walked all procedures: there could be procedures
1209 with cyclic calls but no call from the outside. */
1210 for (i = 0; i < get_irp_n_irgs(); i++) {
1212 current_ir_graph = get_irp_irg(i);
1214 /* Test start block: if inner procedure end and end block are not
1215 * visible and therefore not marked. */
1216 sb = get_irg_start_block(current_ir_graph);
1217 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1220 /* Walk all endless loops in inner procedures.
1221 * We recognize an inner procedure if the End node is not visited. */
1222 for (i = 0; i < get_irp_n_irgs(); i++) {
1224 current_ir_graph = get_irp_irg(i);
1226 e = get_irg_end(current_ir_graph);
1227 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1229 /* Don't visit the End node. */
1230 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1234 set_irg_loop(outermost_ir_graph, current_loop);
1235 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1236 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1238 current_ir_graph = rem;
1239 set_interprocedural_view(rem_ipv);
1240 return max_loop_depth;
1243 void my_construct_ip_backedges (void) {
1244 ir_graph *rem = current_ir_graph;
1245 int rem_ipv = get_interprocedural_view();
1248 assert(get_irp_ip_view_state() == ip_view_valid);
1250 outermost_ir_graph = get_irp_main_irg();
1254 current_loop = NULL;
1255 new_loop(); /* sets current_loop */
1256 set_interprocedural_view(1);
1258 inc_max_irg_visited();
1259 for (i = 0; i < get_irp_n_irgs(); i++)
1260 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1262 /** We have to start the walk at the same nodes as cg_walk. **/
1263 /* Walk starting at unreachable procedures. Only these
1264 * have End blocks visible in interprocedural view. */
1265 for (i = 0; i < get_irp_n_irgs(); i++) {
1267 current_ir_graph = get_irp_irg(i);
1269 sb = get_irg_start_block(current_ir_graph);
1271 if ((get_Block_n_cfgpreds(sb) > 1) ||
1272 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1274 my_scc(get_irg_end(current_ir_graph));
1277 /* Check whether we walked all procedures: there could be procedures
1278 with cyclic calls but no call from the outside. */
1279 for (i = 0; i < get_irp_n_irgs(); i++) {
1281 current_ir_graph = get_irp_irg(i);
1283 /* Test start block: if inner procedure end and end block are not
1284 * visible and therefore not marked. */
1285 sb = get_irg_start_block(current_ir_graph);
1286 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1289 /* Walk all endless loops in inner procedures.
1290 * We recognize an inner procedure if the End node is not visited. */
1291 for (i = 0; i < get_irp_n_irgs(); i++) {
1293 current_ir_graph = get_irp_irg(i);
1295 e = get_irg_end(current_ir_graph);
1296 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1298 /* Don't visit the End node. */
1299 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1303 set_irg_loop(outermost_ir_graph, current_loop);
1304 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1305 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1307 current_ir_graph = rem;
1308 set_interprocedural_view(rem_ipv);
1311 static void reset_backedges(ir_node *n) {
1312 if (is_possible_loop_head(n)) {
1313 int rem = get_interprocedural_view();
1315 set_interprocedural_view(1);
1317 set_interprocedural_view(1);
1319 set_interprocedural_view(rem);
1325 static void loop_reset_backedges(ir_loop *l) {
1327 reset_backedges(get_loop_node(l, 0));
1328 for (i = 0; i < get_loop_n_nodes(l); ++i)
1329 set_irn_loop(get_loop_node(l, i), NULL);
1330 for (i = 0; i < get_loop_n_sons(l); ++i) {
1331 loop_reset_backedges(get_loop_son(l, i));
1336 static void loop_reset_node(ir_node *n, void *env) {
1337 set_irn_loop(n, NULL);
1342 /** Removes all loop information.
1343 Resets all backedges */
1344 void free_loop_information(ir_graph *irg) {
1345 /* We can not use this recursion, as the loop might contain
1346 illegal nodes by now. Why else would we throw away the
1348 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1350 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1351 set_irg_loop(irg, NULL);
1352 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1353 /* We cannot free the loop nodes, they are on the obstack. */
1357 void free_all_loop_information (void) {
1359 int rem = get_interprocedural_view();
1360 set_interprocedural_view(1); /* To visit all filter nodes */
1361 for (i = 0; i < get_irp_n_irgs(); i++) {
1362 free_loop_information(get_irp_irg(i));
1364 set_interprocedural_view(rem);
1371 /* Debug stuff *************************************************/
1373 static int test_loop_node(ir_loop *l) {
1374 int i, has_node = 0, found_problem = 0;
1377 assert(l && l->kind == k_ir_loop);
1379 if (get_loop_n_elements(l) == 0) {
1380 printf(" Loop completely empty! "); DDML(l);
1382 dump_loop(l, "-ha");
1385 le = get_loop_element(l, 0);
1386 if (*(le.kind) != k_ir_node) {
1387 assert(le.kind && *(le.kind) == k_ir_loop);
1388 printf(" First loop element is not a node! "); DDML(l);
1389 printf(" "); DDML(le.son);
1392 dump_loop(l, "-ha");
1395 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1396 printf(" Wrong node as head! "); DDML(l);
1397 printf(" "); DDMN(le.node);
1399 dump_loop(l, "-ha");
1402 if ((get_loop_depth(l) != 0) &&
1403 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1404 printf(" Loop head has no backedges! "); DDML(l);
1405 printf(" "); DDMN(le.node);
1407 dump_loop(l, "-ha");
1412 for (i = 0; i < get_loop_n_elements(l); ++i) {
1413 le = get_loop_element(l, i);
1414 if (*(le.kind) == k_ir_node)
1417 if (test_loop_node(le.son)) found_problem = 1;
1420 if (has_node == 0) {
1421 printf(" Loop has no firm node! "); DDML(l);
1423 dump_loop(l, "-ha");
1426 return found_problem;
1429 /** Prints all loop nodes that
1430 * - do not have any firm nodes, only loop sons
1431 * - the header is not a Phi, Block or Filter.
1433 void find_strange_loop_nodes(ir_loop *l) {
1434 int found_problem = 0;
1435 printf("\nTesting loop "); DDML(l);
1436 found_problem = test_loop_node(l);
1437 printf("Finished Test\n\n");
1438 if (found_problem) exit(0);
1442 /* ------------------------------------------------------------------- */
1443 /* Simple analyses based on the loop information */
1444 /* ------------------------------------------------------------------- */
1446 int is_loop_variant(ir_loop *l, ir_loop *b) {
1449 if (l == b) return 1;
1451 n_elems = get_loop_n_elements(l);
1452 for (i = 0; i < n_elems; ++i) {
1453 loop_element e = get_loop_element(l, i);
1454 if (is_ir_loop(e.kind))
1455 if (is_loop_variant(e.son, b))
1462 /* Test whether a value is loop invariant.
1464 * @param n The node to be tested.
1465 * @param block A block node. We pass the block, not the loop as we must
1466 * start off with a block loop to find all proper uses.
1468 * Returns non-zero, if the node n is not changed in the loop block
1469 * belongs to or in inner loops of this blocks loop. */
1470 int is_loop_invariant(ir_node *n, ir_node *block) {
1471 ir_loop *l = get_irn_loop(block);
1472 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1473 return !is_loop_variant(l, get_irn_loop(b));