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"
51 /* A variant of the loop tree that avoids loops without head.
52 This reduces the depth of the loop tree. */
53 #define NO_LOOPS_WITHOUT_HEAD 1
55 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
57 static ir_loop *current_loop; /* Current loop construction is working
59 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
60 Each loop node gets a unique number.
61 What for? ev. remove. @@@ */
62 static int current_dfn = 1; /* Counter to generate depth first numbering
65 static int max_loop_depth = 0;
67 void link_to_reg_end (ir_node *n, void *env);
68 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
69 ir_node *get_projx_link(ir_node *cb_projx);
71 /**********************************************************************/
72 /* Node attributes **/
73 /**********************************************************************/
75 /**********************************************************************/
76 /* Node attributes needed for the construction. **/
77 /**********************************************************************/
79 typedef struct scc_info {
80 int in_stack; /**< Marks whether node is on the stack. */
81 int dfn; /**< Depth first search number. */
82 int uplink; /**< dfn number of ancestor. */
83 /* ir_loop *loop; *//* Refers to the containing loop. */
85 struct section *section;
91 static INLINE scc_info* new_scc_info(void) {
92 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
93 memset (info, 0, sizeof (scc_info));
98 mark_irn_in_stack (ir_node *n) {
99 scc_info *scc = get_irn_link(n);
105 mark_irn_not_in_stack (ir_node *n) {
106 scc_info *scc = get_irn_link(n);
112 irn_is_in_stack (ir_node *n) {
113 scc_info *scc = get_irn_link(n);
115 return scc->in_stack;
119 set_irn_uplink (ir_node *n, int uplink) {
120 scc_info *scc = get_irn_link(n);
122 scc->uplink = uplink;
126 get_irn_uplink (ir_node *n) {
127 scc_info *scc = get_irn_link(n);
133 set_irn_dfn (ir_node *n, int dfn) {
134 scc_info *scc = get_irn_link(n);
140 get_irn_dfn (ir_node *n) {
141 scc_info *scc = get_irn_link(n);
148 set_irn_loop (ir_node *n, ir_loop *loop) {
152 /* Uses temporary information to get the loop */
153 ir_loop *(get_irn_loop)(const ir_node *n) {
154 return _get_irn_loop(n);
159 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
163 /* Test whether n is contained in this loop. */
164 for (i = 0; i < get_loop_n_nodes(l); i++)
165 if (n == get_loop_node(l, i)) return l;
167 /* Is this a leave in the loop tree? If so loop not found. */
168 if (get_loop_n_sons(l) == 0) return NULL;
170 /* Else descend in the loop tree. */
171 for (i = 0; i < get_loop_n_sons(l); i++) {
172 res = find_nodes_loop(n, get_loop_son(l, i));
178 /* @@@ temporary implementation, costly!!! */
179 ir_loop * get_irn_loop(ir_node *n) {
180 ir_loop *l = get_irg_loop(current_ir_graph);
181 l = find_nodes_loop(n, l);
186 /**********************************************************************/
188 /**********************************************************************/
190 static ir_node **stack = NULL;
191 static int tos = 0; /* top of stack */
194 * initializes the stack
196 static INLINE void init_stack(void) {
198 ARR_RESIZE (ir_node *, stack, 1000);
200 stack = NEW_ARR_F (ir_node *, 1000);
206 static INLINE void free_stack(void) {
214 * push a node onto the stack
216 * @param n The node to push
221 if (tos == ARR_LEN (stack)) {
222 int nlen = ARR_LEN (stack) * 2;
223 ARR_RESIZE (ir_node *, stack, nlen);
226 mark_irn_in_stack(n);
230 * pop a node from the stack
232 * @return The topmost node
234 static INLINE ir_node *
237 ir_node *n = stack[--tos];
238 mark_irn_not_in_stack(n);
243 * The nodes up to n belong to the current loop.
244 * Removes them from the stack and adds them to the current loop.
247 pop_scc_to_loop (ir_node *n)
256 set_irn_dfn(m, loop_node_cnt);
257 add_loop_node(current_loop, m);
258 set_irn_loop(m, current_loop);
261 /* if (m==n) break;*/
264 /* i might be bigger than 1 for dead (and that's why bad) loops */
266 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
270 /* GL ??? my last son is my grandson??? Removes loops with no
271 ir_nodes in them. Such loops have only another loop as son. (Why
272 can't they have two loops as sons? Does it never get that far? ) */
273 static void close_loop (ir_loop *l)
275 int last = get_loop_n_elements(l) - 1;
276 loop_element lelement = get_loop_element(l, last);
277 ir_loop *last_son = lelement.son;
279 if (get_kind(last_son) == k_ir_loop &&
280 get_loop_n_elements(last_son) == 1) {
283 lelement = get_loop_element(last_son, 0);
286 if (get_kind(gson) == k_ir_loop) {
287 loop_element new_last_son;
289 gson->outer_loop = l;
290 new_last_son.son = gson;
291 l->children[last] = new_last_son;
298 /* Removes and unmarks all nodes up to n from the stack.
299 The nodes must be visited once more to assign them to a scc. */
301 pop_scc_unmark_visit (ir_node *n)
307 set_irn_visited(m, 0);
311 /**********************************************************************/
312 /* The loop datastructure. **/
313 /**********************************************************************/
315 /* Allocates a new loop as son of current_loop. Sets current_loop
316 to the new loop and returns the father. */
317 ir_loop *new_loop (void) {
318 ir_loop *father, *son;
320 father = current_loop;
322 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
323 memset (son, 0, sizeof (ir_loop));
324 son->kind = k_ir_loop;
325 son->children = NEW_ARR_F (loop_element, 0);
329 son->outer_loop = father;
330 add_loop_son(father, son);
331 son->depth = father->depth+1;
332 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
333 } else { /* The root loop */
334 son->outer_loop = son;
339 son->loop_nr = get_irp_new_node_nr();
348 /* Finishes the datastructures, copies the arrays to the obstack
350 A. Schoesser: Caution: loop -> sons is gone. */
351 static void mature_loop (ir_loop *loop) {
354 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
355 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
356 DEL_ARR_F(loop->sons);
357 loop->sons = new_sons;
361 /* Returns outer loop, itself if outermost. */
362 ir_loop *(get_loop_outer_loop)(const ir_loop *loop) {
363 return _get_loop_outer_loop(loop);
366 /* Returns nesting depth of this loop */
367 int (get_loop_depth)(const ir_loop *loop) {
368 return _get_loop_depth(loop);
371 /* Returns the number of inner loops */
372 int (get_loop_n_sons)(const ir_loop *loop) {
373 return _get_loop_n_sons(loop);
376 /* Returns the pos`th loop_node-child *
377 * TODO: This method isn`t very efficient ! *
378 * Returns NULL if there isn`t a pos`th loop_node */
379 ir_loop *get_loop_son (ir_loop *loop, int pos) {
380 int child_nr = 0, loop_nr = -1;
382 assert(loop && loop->kind == k_ir_loop);
383 while(child_nr < ARR_LEN(loop->children))
385 if(*(loop -> children[child_nr].kind) == k_ir_loop)
388 return(loop -> children[child_nr].son);
394 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
398 add_loop_son(ir_loop *loop, ir_loop *son) {
401 assert(loop && loop->kind == k_ir_loop);
402 assert(get_kind(son) == k_ir_loop);
403 ARR_APP1 (loop_element, loop->children, lson);
407 /* Returns the number of nodes in the loop */
408 int get_loop_n_nodes (ir_loop *loop) {
409 assert(loop); assert(loop->kind == k_ir_loop);
410 return loop -> n_nodes;
411 /* return ARR_LEN(loop->nodes); */
414 /* Returns the pos`th ir_node-child *
415 * TODO: This method isn`t very efficient ! *
416 * Returns NULL if there isn`t a pos`th ir_node */
417 ir_node *get_loop_node (ir_loop *loop, int pos) {
418 int child_nr, node_nr = -1;
420 assert(loop && loop->kind == k_ir_loop);
421 assert(pos < get_loop_n_nodes(loop));
423 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
424 if(*(loop -> children[child_nr].kind) == k_ir_node)
427 return(loop -> children[child_nr].node);
430 assert(0 && "no child at pos found");
434 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
438 add_loop_node(ir_loop *loop, ir_node *n) {
441 assert(loop && loop->kind == k_ir_loop);
442 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
443 ARR_APP1 (loop_element, loop->children, ln);
447 /* Returns the number of elements contained in loop. */
448 int get_loop_n_elements (const ir_loop *loop) {
449 assert(loop && loop->kind == k_ir_loop);
450 return(ARR_LEN(loop->children));
454 Returns the pos`th loop element.
455 This may be a loop_node or a ir_node. The caller of this function has
456 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
457 and then select the appropriate "loop_element.node" or "loop_element.son".
460 loop_element get_loop_element(const ir_loop *loop, int pos) {
461 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
462 return(loop -> children[pos]);
465 int get_loop_element_pos(const ir_loop *loop, void *le) {
467 assert(loop && loop->kind == k_ir_loop);
469 n = get_loop_n_elements(loop);
470 for (i = 0; i < n; i++)
471 if (get_loop_element(loop, i).node == le) return i;
475 int get_loop_loop_nr(const ir_loop *loop) {
476 assert(loop && loop->kind == k_ir_loop);
478 return loop->loop_nr;
485 /** A field to connect additional information to a loop. Only valid
486 if libfirm_debug is set. */
487 void set_loop_link (ir_loop *loop, void *link) {
488 assert(loop && loop->kind == k_ir_loop);
491 void *get_loop_link (const ir_loop *loop) {
492 assert(loop && loop->kind == k_ir_loop);
496 int (is_ir_loop)(const void *thing) {
497 return _is_ir_loop(thing);
500 /* The outermost loop is remarked in the surrounding graph. */
501 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
502 _set_irg_loop(irg, loop);
505 /* Returns the root loop info (if exists) for an irg. */
506 ir_loop *(get_irg_loop)(ir_graph *irg) {
507 return _get_irg_loop(irg);
511 /**********************************************************************/
512 /* Constructing and destructing the loop/backedge information. **/
513 /**********************************************************************/
515 /* Initialization steps. **********************************************/
518 init_node (ir_node *n, void *env) {
520 set_irn_link (n, new_scc_info());
525 init_scc_common (void) {
532 init_scc (ir_graph *irg) {
534 irg_walk_graph (irg, init_node, NULL, NULL);
536 irg_walk (irg, link_to_reg_end, NULL, NULL);
540 #ifdef INTERPROCEDURAL_VIEW
544 cg_walk (init_node, NULL, NULL);
546 #if EXPERIMENTAL_LOOP_TREE
547 cg_walk (link_to_reg_end, NULL, NULL);
552 /* Condition for breaking the recursion. */
553 static int is_outermost_Start(ir_node *n) {
554 /* Test whether this is the outermost Start node. If so
555 recursion must end. */
556 if ((get_irn_op(n) == op_Block) &&
557 (get_Block_n_cfgpreds(n) == 1) &&
558 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
559 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
563 /* @@@ Bad condition:
564 not possible in interprocedural view as outermost_graph is
565 not necessarily the only with a dead-end start block.
566 Besides current_ir_graph is not set properly. */
567 if ((get_irn_op(n) == op_Block) &&
568 (n == get_irg_start_block(current_ir_graph))) {
569 if ((!get_interprocedural_view()) ||
570 (current_ir_graph == outermost_ir_graph))
577 /* When to walk from nodes to blocks. Only for Control flow operations? */
579 get_start_index(ir_node *n) {
580 #undef BLOCK_BEFORE_NODE
581 #define BLOCK_BEFORE_NODE 1
583 #if BLOCK_BEFORE_NODE
585 /* This version assures, that all nodes are ordered absolutely. This allows
586 to undef all nodes in the heap analysis if the block is false, which means
588 I.e., with this code, the order on the loop tree is correct. But a (single)
589 test showed the loop tree is deeper. */
590 if (get_irn_op(n) == op_Phi ||
591 get_irn_op(n) == op_Block ||
592 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
593 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
594 get_irn_pinned(n) == op_pin_state_floats))
595 // Here we could test for backedge at -1 which is illegal
602 /* This version causes deeper loop trees (at least we verified this
604 But it guarantees that Blocks are analysed before nodes contained in the
605 block. If so, we can set the value to undef if the block is not \
607 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
615 /* Test for legal loop header: Block, Phi, ... */
616 static INLINE int is_possible_loop_head(ir_node *n) {
617 ir_op *op = get_irn_op(n);
618 return ((op == op_Block) ||
620 ((op == op_Filter) && get_interprocedural_view()));
623 /* Returns non-zero if n is a loop header, i.e., it is a Block, Phi
624 or Filter node and has predecessors within the loop and out
626 @arg root: only needed for assertion. */
628 is_head (ir_node *n, ir_node *root)
631 int some_outof_loop = 0, some_in_loop = 0;
633 /* Test for legal loop header: Block, Phi, ... */
634 if (!is_possible_loop_head(n))
637 if (!is_outermost_Start(n)) {
638 arity = get_irn_arity(n);
639 for (i = get_start_index(n); i < arity; i++) {
640 ir_node *pred = get_irn_n(n, i);
642 if (is_backedge(n, i)) continue;
643 if (!irn_is_in_stack(pred)) {
646 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
647 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
653 return some_outof_loop && some_in_loop;
657 * Returns non-zero if n is possible loop head of an endless loop.
658 * I.e., it is a Block, Phi or Filter node and has only predecessors
660 * @param root: only needed for assertion.
663 is_endless_head (ir_node *n, ir_node *root)
666 int some_outof_loop = 0, some_in_loop = 0;
668 /* Test for legal loop header: Block, Phi, ... */
669 if (!is_possible_loop_head(n))
672 if (!is_outermost_Start(n)) {
673 arity = get_irn_arity(n);
674 for (i = get_start_index(n); i < arity; i++) {
675 ir_node *pred = get_irn_n(n, i);
677 if (is_backedge(n, i)) { continue; }
678 if (!irn_is_in_stack(pred)) {
679 some_outof_loop = 1; //printf(" some out of loop ");
681 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
682 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
688 return !some_outof_loop && some_in_loop;
691 /* Returns index of the predecessor with the smallest dfn number
692 greater-equal than limit. */
694 smallest_dfn_pred (ir_node *n, int limit)
696 int i, index = -2, min = -1;
698 if (!is_outermost_Start(n)) {
699 int arity = get_irn_arity(n);
700 for (i = get_start_index(n); i < arity; i++) {
701 ir_node *pred = get_irn_n(n, i);
703 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
704 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
706 min = get_irn_dfn(pred);
713 /* Returns index of the predecessor with the largest dfn number. */
715 largest_dfn_pred (ir_node *n)
717 int i, index = -2, max = -1;
719 if (!is_outermost_Start(n)) {
720 int arity = get_irn_arity(n);
721 for (i = get_start_index(n); i < arity; i++) {
722 ir_node *pred = get_irn_n(n, i);
723 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
724 if (get_irn_dfn(pred) > max) {
726 max = get_irn_dfn(pred);
733 /** Searches the stack for possible loop heads. Tests these for backedges.
734 If it finds a head with an unmarked backedge it marks this edge and
735 returns the tail of the loop.
736 If it finds no backedge returns NULL.
737 ("disable_backedge" in fiasco)
739 * @param n A node where uplink == dfn.
743 find_tail (ir_node *n) {
745 int i, res_index = -2;
748 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
750 m = stack[tos-1]; /* tos = top of stack */
751 if (is_head (m, n)) {
752 res_index = smallest_dfn_pred(m, 0);
753 if ((res_index == -2) && /* no smallest dfn pred found. */
757 if (m == n) return NULL; // Is this to catch Phi - self loops?
758 for (i = tos-2; i >= 0; --i) {
761 if (is_head (m, n)) {
762 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
763 if (res_index == -2) /* no smallest dfn pred found. */
764 res_index = largest_dfn_pred (m);
766 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
772 /* We should not walk past our selves on the stack: The upcoming nodes
773 are not in this loop. We assume a loop not reachable from Start. */
782 /* A dead loop not reachable from Start. */
783 for (i = tos-2; i >= 0; --i) {
785 if (is_endless_head (m, n)) {
786 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
787 if (res_index == -2) /* no smallest dfn pred found. */
788 res_index = largest_dfn_pred (m);
791 if (m == n) { break; } /* It's not an unreachable loop, either. */
793 //assert(0 && "no head found on stack");
797 if (res_index <= -2) {
798 /* It's a completely bad loop: without Phi/Block nodes that can
799 be a head. I.e., the code is "dying". We break the loop by
800 setting Bad nodes. */
801 int arity = get_irn_arity(n);
802 for (i = -1; i < arity; ++i) {
803 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
807 assert (res_index > -2);
809 set_backedge (m, res_index);
810 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
814 #if EXPERIMENTAL_LOOP_TREE
816 /* ----------------------------------------------------------------
817 AS: This is experimental code to build loop trees suitable for
818 the heap analysis. Does not work correctly right now... :-(
821 Search in stack for the corresponding first Call-End-ProjX that
822 corresponds to one of the control flow predecessors of the given
823 block, that is the possible callers.
824 returns: the control predecessor to chose\
825 or -1 if no corresponding Call-End-Node could be found
827 - -------------------------------------------------------------- */
829 int search_endproj_in_stack(ir_node *start_block)
832 assert(is_Block(start_block));
833 for(i = tos - 1; i >= 0; --i)
835 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
836 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
838 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
839 ir_node *end_projx = stack[i];
841 int arity = get_irn_arity(start_block);
842 for(j = 0; j < arity; j++)
844 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
845 get_Proj_proj(end_projx));
846 if(get_irn_n(start_block, j) == begin_projx)
848 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
858 static pmap *projx_link = NULL;
860 void link_to_reg_end (ir_node *n, void *env) {
861 if(get_irn_op(n) == op_Proj &&
862 get_irn_mode(n) == mode_X &&
863 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
864 /* Reg End Projx -> Find the CallBegin Projx and hash it */
865 ir_node *end_projx = n;
866 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
867 get_Proj_proj(end_projx));
868 set_projx_link(begin_projx, end_projx);
872 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
874 if(projx_link == NULL)
875 projx_link = pmap_create();
876 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
879 ir_node *get_projx_link(ir_node *cb_projx)
881 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
887 is_outermost_loop(ir_loop *l) {
888 return l == get_loop_outer_loop(l);
892 /*-----------------------------------------------------------*
893 * The core algorithm. *
894 *-----------------------------------------------------------*/
896 static void scc (ir_node *n) {
898 if (irn_visited(n)) return;
901 /* Initialize the node */
902 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
903 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
904 set_irn_loop(n, NULL);
908 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
909 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
910 so is_backedge does not access array[-1] but correctly returns false! */
912 if (!is_outermost_Start(n)) {
913 int arity = get_irn_arity(n);
915 for (i = get_start_index(n); i < arity; i++) {
917 if (is_backedge(n, i)) continue;
918 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
919 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
921 if (irn_is_in_stack(m)) {
922 /* Uplink of m is smaller if n->m is a backedge.
923 Propagate the uplink to mark the loop. */
924 if (get_irn_uplink(m) < get_irn_uplink(n))
925 set_irn_uplink(n, get_irn_uplink(m));
930 if (get_irn_dfn(n) == get_irn_uplink(n)) {
931 /* This condition holds for
932 1) the node with the incoming backedge.
933 That is: We found a loop!
934 2) Straight line code, because no uplink has been propagated, so the
935 uplink still is the same as the dfn.
937 But n might not be a proper loop head for the analysis. Proper loop
938 heads are Block and Phi nodes. find_tail searches the stack for
939 Block's and Phi's and takes those nodes as loop heads for the current
940 loop instead and marks the incoming edge as backedge. */
942 ir_node *tail = find_tail(n);
944 /* We have a loop, that is no straight line code,
945 because we found a loop head!
946 Next actions: Open a new loop on the loop tree and
947 try to find inner loops */
949 #if NO_LOOPS_WITHOUT_HEAD
950 /* This is an adaption of the algorithm from fiasco / optscc to
951 * avoid loops without Block or Phi as first node. This should
952 * severely reduce the number of evaluations of nodes to detect
953 * a fixpoint in the heap analysis.
954 * Further it avoids loops without firm nodes that cause errors
955 * in the heap analyses.
956 * But attention: don't do it for the outermost loop: This loop
957 * is not iterated. A first block can be a loop head in case of
958 * an endless recursion. */
962 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
970 ir_loop *l = new_loop();
973 /* Remove the loop from the stack ... */
974 pop_scc_unmark_visit (n);
976 /* The current backedge has been marked, that is temporarily eliminated,
977 by find tail. Start the scc algorithm
978 anew on the subgraph that is left (the current loop without the backedge)
979 in order to find more inner loops. */
982 assert (irn_visited(n));
983 #if NO_LOOPS_WITHOUT_HEAD
990 /* No loop head was found, that is we have straightline code.
991 Pop all nodes from the stack to the current loop. */
997 static void my_scc (ir_node *n) {
999 if (irn_visited(n)) return;
1000 mark_irn_visited(n);
1002 /* Initialize the node */
1003 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1004 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1005 set_irn_loop(n, NULL);
1009 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1010 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1011 so is_backedge does not access array[-1] but correctly returns false! */
1013 if (!is_outermost_Start(n)) {
1014 int arity = get_irn_arity(n);
1016 for (i = get_start_index(n); i < arity; i++) {
1018 if (is_backedge(n, i)) continue;
1019 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1020 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1022 if (irn_is_in_stack(m)) {
1023 /* Uplink of m is smaller if n->m is a backedge.
1024 Propagate the uplink to mark the loop. */
1025 if (get_irn_uplink(m) < get_irn_uplink(n))
1026 set_irn_uplink(n, get_irn_uplink(m));
1031 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1032 /* This condition holds for
1033 1) the node with the incoming backedge.
1034 That is: We found a loop!
1035 2) Straight line code, because no uplink has been propagated, so the
1036 uplink still is the same as the dfn.
1038 But n might not be a proper loop head for the analysis. Proper loop
1039 heads are Block and Phi nodes. find_tail searches the stack for
1040 Block's and Phi's and takes those nodes as loop heads for the current
1041 loop instead and marks the incoming edge as backedge. */
1043 ir_node *tail = find_tail(n);
1045 /* We have a loop, that is no straight line code,
1046 because we found a loop head!
1047 Next actions: Open a new loop on the loop tree and
1048 try to find inner loops */
1050 #if NO_LOOPS_WITHOUT_HEAD
1051 /* This is an adaption of the algorithm from fiasco / optscc to
1052 * avoid loops without Block or Phi as first node. This should
1053 * severely reduce the number of evaluations of nodes to detect
1054 * a fixpoint in the heap analysis.
1055 * Further it avoids loops without firm nodes that cause errors
1056 * in the heap analyses. */
1060 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1068 ir_loop *l = new_loop();
1071 /* Remove the loop from the stack ... */
1072 pop_scc_unmark_visit (n);
1074 /* The current backedge has been marked, that is temporarily eliminated,
1075 by find tail. Start the scc algorithm
1076 anew on the subgraph that is left (the current loop without the backedge)
1077 in order to find more inner loops. */
1080 assert (irn_visited(n));
1081 #if NO_LOOPS_WITHOUT_HEAD
1088 /* No loop head was found, that is we have straightline code.
1089 Pop all nodes from the stack to the current loop. */
1095 /* Constructs backedge information for irg. In interprocedural view constructs
1096 backedges for all methods called by irg, too. */
1097 int construct_backedges(ir_graph *irg) {
1098 ir_graph *rem = current_ir_graph;
1101 assert(!get_interprocedural_view() &&
1102 "not implemented, use construct_ip_backedges");
1105 current_ir_graph = irg;
1106 outermost_ir_graph = irg;
1108 init_scc(current_ir_graph);
1110 current_loop = NULL;
1111 new_loop(); /* sets current_loop */
1112 head_rem = current_loop; /* Just for assertion */
1114 inc_irg_visited(current_ir_graph);
1116 scc(get_irg_end(current_ir_graph));
1118 assert(head_rem == current_loop);
1119 set_irg_loop(current_ir_graph, current_loop);
1120 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1121 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1123 irg->loops = current_loop;
1127 count_loop (the_loop, &count, &depth);
1131 current_ir_graph = rem;
1133 return max_loop_depth;
1137 #ifdef INTERPROCEDURAL_VIEW
1138 int construct_ip_backedges (void) {
1139 ir_graph *rem = current_ir_graph;
1140 int rem_ipv = get_interprocedural_view();
1144 assert(get_irp_ip_view_state() == ip_view_valid);
1146 outermost_ir_graph = get_irp_main_irg();
1150 current_loop = NULL;
1151 new_loop(); /* sets current_loop */
1152 set_interprocedural_view(1);
1154 inc_max_irg_visited();
1155 for (i = 0; i < get_irp_n_irgs(); i++)
1156 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1158 /** We have to start the walk at the same nodes as cg_walk. **/
1159 /* Walk starting at unreachable procedures. Only these
1160 * have End blocks visible in interprocedural view. */
1161 for (i = 0; i < get_irp_n_irgs(); i++) {
1163 current_ir_graph = get_irp_irg(i);
1165 sb = get_irg_start_block(current_ir_graph);
1167 if ((get_Block_n_cfgpreds(sb) > 1) ||
1168 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1170 scc(get_irg_end(current_ir_graph));
1173 /* Check whether we walked all procedures: there could be procedures
1174 with cyclic calls but no call from the outside. */
1175 for (i = 0; i < get_irp_n_irgs(); i++) {
1177 current_ir_graph = get_irp_irg(i);
1179 /* Test start block: if inner procedure end and end block are not
1180 * visible and therefore not marked. */
1181 sb = get_irg_start_block(current_ir_graph);
1182 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1185 /* Walk all endless loops in inner procedures.
1186 * We recognize an inner procedure if the End node is not visited. */
1187 for (i = 0; i < get_irp_n_irgs(); i++) {
1189 current_ir_graph = get_irp_irg(i);
1191 e = get_irg_end(current_ir_graph);
1192 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1194 /* Don't visit the End node. */
1195 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1199 set_irg_loop(outermost_ir_graph, current_loop);
1200 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1201 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1203 current_ir_graph = rem;
1204 set_interprocedural_view(rem_ipv);
1205 return max_loop_depth;
1208 void my_construct_ip_backedges (void) {
1209 ir_graph *rem = current_ir_graph;
1210 int rem_ipv = get_interprocedural_view();
1213 assert(get_irp_ip_view_state() == ip_view_valid);
1215 outermost_ir_graph = get_irp_main_irg();
1219 current_loop = NULL;
1220 new_loop(); /* sets current_loop */
1221 set_interprocedural_view(1);
1223 inc_max_irg_visited();
1224 for (i = 0; i < get_irp_n_irgs(); i++)
1225 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1227 /** We have to start the walk at the same nodes as cg_walk. **/
1228 /* Walk starting at unreachable procedures. Only these
1229 * have End blocks visible in interprocedural view. */
1230 for (i = 0; i < get_irp_n_irgs(); i++) {
1232 current_ir_graph = get_irp_irg(i);
1234 sb = get_irg_start_block(current_ir_graph);
1236 if ((get_Block_n_cfgpreds(sb) > 1) ||
1237 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1239 my_scc(get_irg_end(current_ir_graph));
1242 /* Check whether we walked all procedures: there could be procedures
1243 with cyclic calls but no call from the outside. */
1244 for (i = 0; i < get_irp_n_irgs(); i++) {
1246 current_ir_graph = get_irp_irg(i);
1248 /* Test start block: if inner procedure end and end block are not
1249 * visible and therefore not marked. */
1250 sb = get_irg_start_block(current_ir_graph);
1251 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1254 /* Walk all endless loops in inner procedures.
1255 * We recognize an inner procedure if the End node is not visited. */
1256 for (i = 0; i < get_irp_n_irgs(); i++) {
1258 current_ir_graph = get_irp_irg(i);
1260 e = get_irg_end(current_ir_graph);
1261 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1263 /* Don't visit the End node. */
1264 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1268 set_irg_loop(outermost_ir_graph, current_loop);
1269 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1270 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1272 current_ir_graph = rem;
1273 set_interprocedural_view(rem_ipv);
1277 static void reset_backedges(ir_node *n) {
1278 if (is_possible_loop_head(n)) {
1279 #ifdef INTERPROCEDURAL_VIEW
1280 int rem = get_interprocedural_view();
1282 set_interprocedural_view(1);
1284 set_interprocedural_view(1);
1286 set_interprocedural_view(rem);
1295 static void loop_reset_backedges(ir_loop *l) {
1297 reset_backedges(get_loop_node(l, 0));
1298 for (i = 0; i < get_loop_n_nodes(l); ++i)
1299 set_irn_loop(get_loop_node(l, i), NULL);
1300 for (i = 0; i < get_loop_n_sons(l); ++i) {
1301 loop_reset_backedges(get_loop_son(l, i));
1306 static void loop_reset_node(ir_node *n, void *env) {
1308 set_irn_loop(n, NULL);
1313 /** Removes all loop information.
1314 Resets all backedges */
1315 void free_loop_information(ir_graph *irg) {
1316 /* We can not use this recursion, as the loop might contain
1317 illegal nodes by now. Why else would we throw away the
1319 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1321 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1322 set_irg_loop(irg, NULL);
1323 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1324 /* We cannot free the loop nodes, they are on the obstack. */
1328 void free_all_loop_information (void) {
1330 #ifdef INTERPROCEDURAL_VIEW
1331 int rem = get_interprocedural_view();
1332 set_interprocedural_view(1); /* To visit all filter nodes */
1334 for (i = 0; i < get_irp_n_irgs(); i++) {
1335 free_loop_information(get_irp_irg(i));
1337 #ifdef INTERPROCEDURAL_VIEW
1338 set_interprocedural_view(rem);
1346 /* Debug stuff *************************************************/
1348 static int test_loop_node(ir_loop *l) {
1349 int i, has_node = 0, found_problem = 0;
1352 assert(l && l->kind == k_ir_loop);
1354 if (get_loop_n_elements(l) == 0) {
1356 dump_loop(l, "-ha");
1359 le = get_loop_element(l, 0);
1360 if (*(le.kind) != k_ir_node) {
1361 assert(le.kind && *(le.kind) == k_ir_loop);
1364 dump_loop(l, "-ha");
1367 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1369 dump_loop(l, "-ha");
1372 if ((get_loop_depth(l) != 0) &&
1373 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1375 dump_loop(l, "-ha");
1380 for (i = 0; i < get_loop_n_elements(l); ++i) {
1381 le = get_loop_element(l, i);
1382 if (*(le.kind) == k_ir_node)
1385 if (test_loop_node(le.son)) found_problem = 1;
1388 if (has_node == 0) {
1390 dump_loop(l, "-ha");
1393 return found_problem;
1396 /** Prints all loop nodes that
1397 * - do not have any firm nodes, only loop sons
1398 * - the header is not a Phi, Block or Filter.
1400 void find_strange_loop_nodes(ir_loop *l) {
1401 int found_problem = 0;
1402 found_problem = test_loop_node(l);
1403 printf("Finished Test\n\n");
1404 if (found_problem) exit(0);
1408 /* ------------------------------------------------------------------- */
1409 /* Simple analyses based on the loop information */
1410 /* ------------------------------------------------------------------- */
1412 int is_loop_variant(ir_loop *l, ir_loop *b) {
1415 if (l == b) return 1;
1417 n_elems = get_loop_n_elements(l);
1418 for (i = 0; i < n_elems; ++i) {
1419 loop_element e = get_loop_element(l, i);
1420 if (is_ir_loop(e.kind))
1421 if (is_loop_variant(e.son, b))
1428 /* Test whether a value is loop invariant.
1430 * @param n The node to be tested.
1431 * @param block A block node. We pass the block, not the loop as we must
1432 * start off with a block loop to find all proper uses.
1434 * Returns non-zero, if the node n is not changed in the loop block
1435 * belongs to or in inner loops of this blocks loop. */
1436 int is_loop_invariant(ir_node *n, ir_node *block) {
1437 ir_loop *l = get_irn_loop(block);
1438 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1439 return !is_loop_variant(l, get_irn_loop(b));