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
222 if (tos == ARR_LEN (stack)) {
223 int nlen = ARR_LEN (stack) * 2;
224 ARR_RESIZE (ir_node *, stack, nlen);
227 mark_irn_in_stack(n);
231 * pop a node from the stack
233 * @return The topmost node
235 static INLINE ir_node *
238 ir_node *n = stack[--tos];
239 mark_irn_not_in_stack(n);
244 * The nodes up to n belong to the current loop.
245 * Removes them from the stack and adds them to the current loop.
248 pop_scc_to_loop (ir_node *n)
257 set_irn_dfn(m, loop_node_cnt);
258 add_loop_node(current_loop, m);
259 set_irn_loop(m, current_loop);
262 /* if (m==n) break;*/
265 /* i might be bigger than 1 for dead (and that's why bad) loops */
267 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
271 /* GL ??? my last son is my grandson??? Removes loops with no
272 ir_nodes in them. Such loops have only another loop as son. (Why
273 can't they have two loops as sons? Does it never get that far? ) */
274 static void close_loop (ir_loop *l)
276 int last = get_loop_n_elements(l) - 1;
277 loop_element lelement = get_loop_element(l, last);
278 ir_loop *last_son = lelement.son;
280 if (get_kind(last_son) == k_ir_loop &&
281 get_loop_n_elements(last_son) == 1) {
284 lelement = get_loop_element(last_son, 0);
287 if (get_kind(gson) == k_ir_loop) {
288 loop_element new_last_son;
290 gson->outer_loop = l;
291 new_last_son.son = gson;
292 l->children[last] = new_last_son;
299 /* Removes and unmarks all nodes up to n from the stack.
300 The nodes must be visited once more to assign them to a scc. */
302 pop_scc_unmark_visit (ir_node *n)
308 set_irn_visited(m, 0);
312 /**********************************************************************/
313 /* The loop datastructure. **/
314 /**********************************************************************/
316 /* Allocates a new loop as son of current_loop. Sets current_loop
317 to the new loop and returns the father. */
318 ir_loop *new_loop (void) {
319 ir_loop *father, *son;
321 father = current_loop;
323 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
324 memset (son, 0, sizeof (ir_loop));
325 son->kind = k_ir_loop;
326 son->children = NEW_ARR_F (loop_element, 0);
330 son->outer_loop = father;
331 add_loop_son(father, son);
332 son->depth = father->depth+1;
333 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
334 } else { /* The root loop */
335 son->outer_loop = son;
340 son->loop_nr = get_irp_new_node_nr();
349 /* Finishes the datastructures, copies the arrays to the obstack
351 A. Schoesser: Caution: loop -> sons is gone. */
352 static void mature_loop (ir_loop *loop) {
355 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
356 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
357 DEL_ARR_F(loop->sons);
358 loop->sons = new_sons;
362 /* Returns outer loop, itself if outermost. */
363 ir_loop *(get_loop_outer_loop)(const ir_loop *loop) {
364 return _get_loop_outer_loop(loop);
367 /* Returns nesting depth of this loop */
368 int (get_loop_depth)(const ir_loop *loop) {
369 return _get_loop_depth(loop);
372 /* Returns the number of inner loops */
373 int (get_loop_n_sons)(const ir_loop *loop) {
374 return _get_loop_n_sons(loop);
377 /* Returns the pos`th loop_node-child *
378 * TODO: This method isn`t very efficient ! *
379 * Returns NULL if there isn`t a pos`th loop_node */
380 ir_loop *get_loop_son (ir_loop *loop, int pos) {
381 int child_nr = 0, loop_nr = -1;
383 assert(loop && loop->kind == k_ir_loop);
384 while(child_nr < ARR_LEN(loop->children))
386 if(*(loop -> children[child_nr].kind) == k_ir_loop)
389 return(loop -> children[child_nr].son);
395 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
399 add_loop_son(ir_loop *loop, ir_loop *son) {
402 assert(loop && loop->kind == k_ir_loop);
403 assert(get_kind(son) == k_ir_loop);
404 ARR_APP1 (loop_element, loop->children, lson);
408 /* Returns the number of nodes in the loop */
409 int get_loop_n_nodes (ir_loop *loop) {
410 assert(loop); assert(loop->kind == k_ir_loop);
411 return loop -> n_nodes;
412 /* return ARR_LEN(loop->nodes); */
415 /* Returns the pos`th ir_node-child *
416 * TODO: This method isn`t very efficient ! *
417 * Returns NULL if there isn`t a pos`th ir_node */
418 ir_node *get_loop_node (ir_loop *loop, int pos) {
419 int child_nr, node_nr = -1;
421 assert(loop && loop->kind == k_ir_loop);
422 assert(pos < get_loop_n_nodes(loop));
424 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
425 if(*(loop -> children[child_nr].kind) == k_ir_node)
428 return(loop -> children[child_nr].node);
431 assert(0 && "no child at pos found");
435 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
439 add_loop_node(ir_loop *loop, ir_node *n) {
442 assert(loop && loop->kind == k_ir_loop);
443 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
444 ARR_APP1 (loop_element, loop->children, ln);
448 /* Returns the number of elements contained in loop. */
449 int get_loop_n_elements (const ir_loop *loop) {
450 assert(loop && loop->kind == k_ir_loop);
451 return(ARR_LEN(loop->children));
455 Returns the pos`th loop element.
456 This may be a loop_node or a ir_node. The caller of this function has
457 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
458 and then select the appropriate "loop_element.node" or "loop_element.son".
461 loop_element get_loop_element(const ir_loop *loop, int pos) {
462 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
463 return(loop -> children[pos]);
466 int get_loop_element_pos(const ir_loop *loop, void *le) {
468 assert(loop && loop->kind == k_ir_loop);
470 n = get_loop_n_elements(loop);
471 for (i = 0; i < n; i++)
472 if (get_loop_element(loop, i).node == le) return i;
476 int get_loop_loop_nr(const ir_loop *loop) {
477 assert(loop && loop->kind == k_ir_loop);
479 return loop->loop_nr;
486 /** A field to connect additional information to a loop. Only valid
487 if libfirm_debug is set. */
488 void set_loop_link (ir_loop *loop, void *link) {
489 assert(loop && loop->kind == k_ir_loop);
494 void *get_loop_link (const ir_loop *loop) {
495 assert(loop && loop->kind == k_ir_loop);
503 int (is_ir_loop)(const void *thing) {
504 return _is_ir_loop(thing);
507 /* The outermost loop is remarked in the surrounding graph. */
508 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
509 _set_irg_loop(irg, loop);
512 /* Returns the root loop info (if exists) for an irg. */
513 ir_loop *(get_irg_loop)(ir_graph *irg) {
514 return _get_irg_loop(irg);
518 /**********************************************************************/
519 /* Constructing and destructing the loop/backedge information. **/
520 /**********************************************************************/
522 /* Initialization steps. **********************************************/
525 init_node (ir_node *n, void *env) {
527 set_irn_link (n, new_scc_info());
532 init_scc_common (void) {
539 init_scc (ir_graph *irg) {
541 irg_walk_graph (irg, init_node, NULL, NULL);
543 irg_walk (irg, link_to_reg_end, NULL, NULL);
547 #ifdef INTERPROCEDURAL_VIEW
551 cg_walk (init_node, NULL, NULL);
553 #if EXPERIMENTAL_LOOP_TREE
554 cg_walk (link_to_reg_end, NULL, NULL);
559 /* Condition for breaking the recursion. */
560 static int is_outermost_Start(ir_node *n) {
561 /* Test whether this is the outermost Start node. If so
562 recursion must end. */
563 if ((get_irn_op(n) == op_Block) &&
564 (get_Block_n_cfgpreds(n) == 1) &&
565 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
566 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
570 /* @@@ Bad condition:
571 not possible in interprocedural view as outermost_graph is
572 not necessarily the only with a dead-end start block.
573 Besides current_ir_graph is not set properly. */
574 if ((get_irn_op(n) == op_Block) &&
575 (n == get_irg_start_block(current_ir_graph))) {
576 if ((!get_interprocedural_view()) ||
577 (current_ir_graph == outermost_ir_graph))
584 /* When to walk from nodes to blocks. Only for Control flow operations? */
586 get_start_index(ir_node *n) {
587 #undef BLOCK_BEFORE_NODE
588 #define BLOCK_BEFORE_NODE 1
590 #if BLOCK_BEFORE_NODE
592 /* This version assures, that all nodes are ordered absolutely. This allows
593 to undef all nodes in the heap analysis if the block is false, which means
595 I.e., with this code, the order on the loop tree is correct. But a (single)
596 test showed the loop tree is deeper. */
597 if (get_irn_op(n) == op_Phi ||
598 get_irn_op(n) == op_Block ||
599 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
600 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
601 get_irn_pinned(n) == op_pin_state_floats))
602 // Here we could test for backedge at -1 which is illegal
609 /* This version causes deeper loop trees (at least we verified this
611 But it guarantees that Blocks are analysed before nodes contained in the
612 block. If so, we can set the value to undef if the block is not \
614 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
622 /* Test for legal loop header: Block, Phi, ... */
623 static INLINE int is_possible_loop_head(ir_node *n) {
624 ir_op *op = get_irn_op(n);
625 return ((op == op_Block) ||
627 ((op == op_Filter) && get_interprocedural_view()));
630 /* Returns non-zero if n is a loop header, i.e., it is a Block, Phi
631 or Filter node and has predecessors within the loop and out
633 @arg root: only needed for assertion. */
635 is_head (ir_node *n, ir_node *root)
638 int some_outof_loop = 0, some_in_loop = 0;
640 /* Test for legal loop header: Block, Phi, ... */
641 if (!is_possible_loop_head(n))
644 if (!is_outermost_Start(n)) {
645 arity = get_irn_arity(n);
646 for (i = get_start_index(n); i < arity; i++) {
647 ir_node *pred = get_irn_n(n, i);
649 if (is_backedge(n, i)) continue;
650 if (!irn_is_in_stack(pred)) {
653 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
654 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
660 return some_outof_loop && some_in_loop;
664 * Returns non-zero if n is possible loop head of an endless loop.
665 * I.e., it is a Block, Phi or Filter node and has only predecessors
667 * @param root: only needed for assertion.
670 is_endless_head (ir_node *n, ir_node *root)
673 int some_outof_loop = 0, some_in_loop = 0;
675 /* Test for legal loop header: Block, Phi, ... */
676 if (!is_possible_loop_head(n))
679 if (!is_outermost_Start(n)) {
680 arity = get_irn_arity(n);
681 for (i = get_start_index(n); i < arity; i++) {
682 ir_node *pred = get_irn_n(n, i);
684 if (is_backedge(n, i)) { continue; }
685 if (!irn_is_in_stack(pred)) {
686 some_outof_loop = 1; //printf(" some out of loop ");
688 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
689 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
695 return !some_outof_loop && some_in_loop;
698 /* Returns index of the predecessor with the smallest dfn number
699 greater-equal than limit. */
701 smallest_dfn_pred (ir_node *n, int limit)
703 int i, index = -2, min = -1;
705 if (!is_outermost_Start(n)) {
706 int arity = get_irn_arity(n);
707 for (i = get_start_index(n); i < arity; i++) {
708 ir_node *pred = get_irn_n(n, i);
710 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
711 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
713 min = get_irn_dfn(pred);
720 /* Returns index of the predecessor with the largest dfn number. */
722 largest_dfn_pred (ir_node *n)
724 int i, index = -2, max = -1;
726 if (!is_outermost_Start(n)) {
727 int arity = get_irn_arity(n);
728 for (i = get_start_index(n); i < arity; i++) {
729 ir_node *pred = get_irn_n(n, i);
730 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
731 if (get_irn_dfn(pred) > max) {
733 max = get_irn_dfn(pred);
740 /** Searches the stack for possible loop heads. Tests these for backedges.
741 If it finds a head with an unmarked backedge it marks this edge and
742 returns the tail of the loop.
743 If it finds no backedge returns NULL.
744 ("disable_backedge" in fiasco)
746 * @param n A node where uplink == dfn.
750 find_tail (ir_node *n) {
752 int i, res_index = -2;
755 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
757 m = stack[tos-1]; /* tos = top of stack */
758 if (is_head (m, n)) {
759 res_index = smallest_dfn_pred(m, 0);
760 if ((res_index == -2) && /* no smallest dfn pred found. */
764 if (m == n) return NULL; // Is this to catch Phi - self loops?
765 for (i = tos-2; i >= 0; --i) {
768 if (is_head (m, n)) {
769 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
770 if (res_index == -2) /* no smallest dfn pred found. */
771 res_index = largest_dfn_pred (m);
773 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
779 /* We should not walk past our selves on the stack: The upcoming nodes
780 are not in this loop. We assume a loop not reachable from Start. */
789 /* A dead loop not reachable from Start. */
790 for (i = tos-2; i >= 0; --i) {
792 if (is_endless_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);
798 if (m == n) { break; } /* It's not an unreachable loop, either. */
800 //assert(0 && "no head found on stack");
804 if (res_index <= -2) {
805 /* It's a completely bad loop: without Phi/Block nodes that can
806 be a head. I.e., the code is "dying". We break the loop by
807 setting Bad nodes. */
808 int arity = get_irn_arity(n);
809 for (i = -1; i < arity; ++i) {
810 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
814 assert (res_index > -2);
816 set_backedge (m, res_index);
817 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
821 #if EXPERIMENTAL_LOOP_TREE
823 /* ----------------------------------------------------------------
824 AS: This is experimental code to build loop trees suitable for
825 the heap analysis. Does not work correctly right now... :-(
828 Search in stack for the corresponding first Call-End-ProjX that
829 corresponds to one of the control flow predecessors of the given
830 block, that is the possible callers.
831 returns: the control predecessor to chose\
832 or -1 if no corresponding Call-End-Node could be found
834 - -------------------------------------------------------------- */
836 int search_endproj_in_stack(ir_node *start_block)
839 assert(is_Block(start_block));
840 for(i = tos - 1; i >= 0; --i)
842 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
843 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
845 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
846 ir_node *end_projx = stack[i];
848 int arity = get_irn_arity(start_block);
849 for(j = 0; j < arity; j++)
851 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
852 get_Proj_proj(end_projx));
853 if(get_irn_n(start_block, j) == begin_projx)
855 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
865 static pmap *projx_link = NULL;
867 void link_to_reg_end (ir_node *n, void *env) {
868 if(get_irn_op(n) == op_Proj &&
869 get_irn_mode(n) == mode_X &&
870 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
871 /* Reg End Projx -> Find the CallBegin Projx and hash it */
872 ir_node *end_projx = n;
873 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
874 get_Proj_proj(end_projx));
875 set_projx_link(begin_projx, end_projx);
879 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
881 if(projx_link == NULL)
882 projx_link = pmap_create();
883 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
886 ir_node *get_projx_link(ir_node *cb_projx)
888 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
894 is_outermost_loop(ir_loop *l) {
895 return l == get_loop_outer_loop(l);
899 /*-----------------------------------------------------------*
900 * The core algorithm. *
901 *-----------------------------------------------------------*/
903 static void scc (ir_node *n) {
905 if (irn_visited(n)) return;
908 /* Initialize the node */
909 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
910 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
911 set_irn_loop(n, NULL);
915 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
916 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
917 so is_backedge does not access array[-1] but correctly returns false! */
919 if (!is_outermost_Start(n)) {
920 int arity = get_irn_arity(n);
922 for (i = get_start_index(n); i < arity; i++) {
924 if (is_backedge(n, i)) continue;
925 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
926 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
928 if (irn_is_in_stack(m)) {
929 /* Uplink of m is smaller if n->m is a backedge.
930 Propagate the uplink to mark the loop. */
931 if (get_irn_uplink(m) < get_irn_uplink(n))
932 set_irn_uplink(n, get_irn_uplink(m));
937 if (get_irn_dfn(n) == get_irn_uplink(n)) {
938 /* This condition holds for
939 1) the node with the incoming backedge.
940 That is: We found a loop!
941 2) Straight line code, because no uplink has been propagated, so the
942 uplink still is the same as the dfn.
944 But n might not be a proper loop head for the analysis. Proper loop
945 heads are Block and Phi nodes. find_tail searches the stack for
946 Block's and Phi's and takes those nodes as loop heads for the current
947 loop instead and marks the incoming edge as backedge. */
949 ir_node *tail = find_tail(n);
951 /* We have a loop, that is no straight line code,
952 because we found a loop head!
953 Next actions: Open a new loop on the loop tree and
954 try to find inner loops */
956 #if NO_LOOPS_WITHOUT_HEAD
957 /* This is an adaption of the algorithm from fiasco / optscc to
958 * avoid loops without Block or Phi as first node. This should
959 * severely reduce the number of evaluations of nodes to detect
960 * a fixpoint in the heap analysis.
961 * Further it avoids loops without firm nodes that cause errors
962 * in the heap analyses.
963 * But attention: don't do it for the outermost loop: This loop
964 * is not iterated. A first block can be a loop head in case of
965 * an endless recursion. */
969 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
977 ir_loop *l = new_loop();
980 /* Remove the loop from the stack ... */
981 pop_scc_unmark_visit (n);
983 /* The current backedge has been marked, that is temporarily eliminated,
984 by find tail. Start the scc algorithm
985 anew on the subgraph that is left (the current loop without the backedge)
986 in order to find more inner loops. */
989 assert (irn_visited(n));
990 #if NO_LOOPS_WITHOUT_HEAD
997 /* No loop head was found, that is we have straightline code.
998 Pop all nodes from the stack to the current loop. */
1004 static void my_scc (ir_node *n) {
1006 if (irn_visited(n)) return;
1007 mark_irn_visited(n);
1009 /* Initialize the node */
1010 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1011 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1012 set_irn_loop(n, NULL);
1016 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1017 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1018 so is_backedge does not access array[-1] but correctly returns false! */
1020 if (!is_outermost_Start(n)) {
1021 int arity = get_irn_arity(n);
1023 for (i = get_start_index(n); i < arity; i++) {
1025 if (is_backedge(n, i)) continue;
1026 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1027 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1029 if (irn_is_in_stack(m)) {
1030 /* Uplink of m is smaller if n->m is a backedge.
1031 Propagate the uplink to mark the loop. */
1032 if (get_irn_uplink(m) < get_irn_uplink(n))
1033 set_irn_uplink(n, get_irn_uplink(m));
1038 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1039 /* This condition holds for
1040 1) the node with the incoming backedge.
1041 That is: We found a loop!
1042 2) Straight line code, because no uplink has been propagated, so the
1043 uplink still is the same as the dfn.
1045 But n might not be a proper loop head for the analysis. Proper loop
1046 heads are Block and Phi nodes. find_tail searches the stack for
1047 Block's and Phi's and takes those nodes as loop heads for the current
1048 loop instead and marks the incoming edge as backedge. */
1050 ir_node *tail = find_tail(n);
1052 /* We have a loop, that is no straight line code,
1053 because we found a loop head!
1054 Next actions: Open a new loop on the loop tree and
1055 try to find inner loops */
1057 #if NO_LOOPS_WITHOUT_HEAD
1058 /* This is an adaption of the algorithm from fiasco / optscc to
1059 * avoid loops without Block or Phi as first node. This should
1060 * severely reduce the number of evaluations of nodes to detect
1061 * a fixpoint in the heap analysis.
1062 * Further it avoids loops without firm nodes that cause errors
1063 * in the heap analyses. */
1067 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1075 ir_loop *l = new_loop();
1078 /* Remove the loop from the stack ... */
1079 pop_scc_unmark_visit (n);
1081 /* The current backedge has been marked, that is temporarily eliminated,
1082 by find tail. Start the scc algorithm
1083 anew on the subgraph that is left (the current loop without the backedge)
1084 in order to find more inner loops. */
1087 assert (irn_visited(n));
1088 #if NO_LOOPS_WITHOUT_HEAD
1095 /* No loop head was found, that is we have straightline code.
1096 Pop all nodes from the stack to the current loop. */
1102 /* Constructs backedge information for irg. In interprocedural view constructs
1103 backedges for all methods called by irg, too. */
1104 int construct_backedges(ir_graph *irg) {
1105 ir_graph *rem = current_ir_graph;
1108 assert(!get_interprocedural_view() &&
1109 "not implemented, use construct_ip_backedges");
1112 current_ir_graph = irg;
1113 outermost_ir_graph = irg;
1115 init_scc(current_ir_graph);
1117 current_loop = NULL;
1118 new_loop(); /* sets current_loop */
1119 head_rem = current_loop; /* Just for assertion */
1121 inc_irg_visited(current_ir_graph);
1123 scc(get_irg_end(current_ir_graph));
1125 assert(head_rem == current_loop);
1126 set_irg_loop(current_ir_graph, current_loop);
1127 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1128 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1130 irg->loops = current_loop;
1134 count_loop (the_loop, &count, &depth);
1138 current_ir_graph = rem;
1140 return max_loop_depth;
1144 #ifdef INTERPROCEDURAL_VIEW
1145 int construct_ip_backedges (void) {
1146 ir_graph *rem = current_ir_graph;
1147 int rem_ipv = get_interprocedural_view();
1151 assert(get_irp_ip_view_state() == ip_view_valid);
1153 outermost_ir_graph = get_irp_main_irg();
1157 current_loop = NULL;
1158 new_loop(); /* sets current_loop */
1159 set_interprocedural_view(1);
1161 inc_max_irg_visited();
1162 for (i = 0; i < get_irp_n_irgs(); i++)
1163 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1165 /** We have to start the walk at the same nodes as cg_walk. **/
1166 /* Walk starting at unreachable procedures. Only these
1167 * have End blocks visible in interprocedural view. */
1168 for (i = 0; i < get_irp_n_irgs(); i++) {
1170 current_ir_graph = get_irp_irg(i);
1172 sb = get_irg_start_block(current_ir_graph);
1174 if ((get_Block_n_cfgpreds(sb) > 1) ||
1175 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1177 scc(get_irg_end(current_ir_graph));
1180 /* Check whether we walked all procedures: there could be procedures
1181 with cyclic calls but no call from the outside. */
1182 for (i = 0; i < get_irp_n_irgs(); i++) {
1184 current_ir_graph = get_irp_irg(i);
1186 /* Test start block: if inner procedure end and end block are not
1187 * visible and therefore not marked. */
1188 sb = get_irg_start_block(current_ir_graph);
1189 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1192 /* Walk all endless loops in inner procedures.
1193 * We recognize an inner procedure if the End node is not visited. */
1194 for (i = 0; i < get_irp_n_irgs(); i++) {
1196 current_ir_graph = get_irp_irg(i);
1198 e = get_irg_end(current_ir_graph);
1199 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1201 /* Don't visit the End node. */
1202 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1206 set_irg_loop(outermost_ir_graph, current_loop);
1207 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1208 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1210 current_ir_graph = rem;
1211 set_interprocedural_view(rem_ipv);
1212 return max_loop_depth;
1215 void my_construct_ip_backedges (void) {
1216 ir_graph *rem = current_ir_graph;
1217 int rem_ipv = get_interprocedural_view();
1220 assert(get_irp_ip_view_state() == ip_view_valid);
1222 outermost_ir_graph = get_irp_main_irg();
1226 current_loop = NULL;
1227 new_loop(); /* sets current_loop */
1228 set_interprocedural_view(1);
1230 inc_max_irg_visited();
1231 for (i = 0; i < get_irp_n_irgs(); i++)
1232 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1234 /** We have to start the walk at the same nodes as cg_walk. **/
1235 /* Walk starting at unreachable procedures. Only these
1236 * have End blocks visible in interprocedural view. */
1237 for (i = 0; i < get_irp_n_irgs(); i++) {
1239 current_ir_graph = get_irp_irg(i);
1241 sb = get_irg_start_block(current_ir_graph);
1243 if ((get_Block_n_cfgpreds(sb) > 1) ||
1244 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1246 my_scc(get_irg_end(current_ir_graph));
1249 /* Check whether we walked all procedures: there could be procedures
1250 with cyclic calls but no call from the outside. */
1251 for (i = 0; i < get_irp_n_irgs(); i++) {
1253 current_ir_graph = get_irp_irg(i);
1255 /* Test start block: if inner procedure end and end block are not
1256 * visible and therefore not marked. */
1257 sb = get_irg_start_block(current_ir_graph);
1258 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1261 /* Walk all endless loops in inner procedures.
1262 * We recognize an inner procedure if the End node is not visited. */
1263 for (i = 0; i < get_irp_n_irgs(); i++) {
1265 current_ir_graph = get_irp_irg(i);
1267 e = get_irg_end(current_ir_graph);
1268 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1270 /* Don't visit the End node. */
1271 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1275 set_irg_loop(outermost_ir_graph, current_loop);
1276 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1277 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1279 current_ir_graph = rem;
1280 set_interprocedural_view(rem_ipv);
1284 static void reset_backedges(ir_node *n) {
1285 if (is_possible_loop_head(n)) {
1286 #ifdef INTERPROCEDURAL_VIEW
1287 int rem = get_interprocedural_view();
1289 set_interprocedural_view(1);
1291 set_interprocedural_view(1);
1293 set_interprocedural_view(rem);
1302 static void loop_reset_backedges(ir_loop *l) {
1304 reset_backedges(get_loop_node(l, 0));
1305 for (i = 0; i < get_loop_n_nodes(l); ++i)
1306 set_irn_loop(get_loop_node(l, i), NULL);
1307 for (i = 0; i < get_loop_n_sons(l); ++i) {
1308 loop_reset_backedges(get_loop_son(l, i));
1313 static void loop_reset_node(ir_node *n, void *env) {
1315 set_irn_loop(n, NULL);
1320 /** Removes all loop information.
1321 Resets all backedges */
1322 void free_loop_information(ir_graph *irg) {
1323 /* We can not use this recursion, as the loop might contain
1324 illegal nodes by now. Why else would we throw away the
1326 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1328 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1329 set_irg_loop(irg, NULL);
1330 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1331 /* We cannot free the loop nodes, they are on the obstack. */
1335 void free_all_loop_information (void) {
1337 #ifdef INTERPROCEDURAL_VIEW
1338 int rem = get_interprocedural_view();
1339 set_interprocedural_view(1); /* To visit all filter nodes */
1341 for (i = 0; i < get_irp_n_irgs(); i++) {
1342 free_loop_information(get_irp_irg(i));
1344 #ifdef INTERPROCEDURAL_VIEW
1345 set_interprocedural_view(rem);
1353 /* Debug stuff *************************************************/
1355 static int test_loop_node(ir_loop *l) {
1356 int i, has_node = 0, found_problem = 0;
1359 assert(l && l->kind == k_ir_loop);
1361 if (get_loop_n_elements(l) == 0) {
1363 dump_loop(l, "-ha");
1366 le = get_loop_element(l, 0);
1367 if (*(le.kind) != k_ir_node) {
1368 assert(le.kind && *(le.kind) == k_ir_loop);
1371 dump_loop(l, "-ha");
1374 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1376 dump_loop(l, "-ha");
1379 if ((get_loop_depth(l) != 0) &&
1380 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1382 dump_loop(l, "-ha");
1387 for (i = 0; i < get_loop_n_elements(l); ++i) {
1388 le = get_loop_element(l, i);
1389 if (*(le.kind) == k_ir_node)
1392 if (test_loop_node(le.son)) found_problem = 1;
1395 if (has_node == 0) {
1397 dump_loop(l, "-ha");
1400 return found_problem;
1403 /** Prints all loop nodes that
1404 * - do not have any firm nodes, only loop sons
1405 * - the header is not a Phi, Block or Filter.
1407 void find_strange_loop_nodes(ir_loop *l) {
1408 int found_problem = 0;
1409 found_problem = test_loop_node(l);
1410 printf("Finished Test\n\n");
1411 if (found_problem) exit(0);
1415 /* ------------------------------------------------------------------- */
1416 /* Simple analyses based on the loop information */
1417 /* ------------------------------------------------------------------- */
1419 int is_loop_variant(ir_loop *l, ir_loop *b) {
1422 if (l == b) return 1;
1424 n_elems = get_loop_n_elements(l);
1425 for (i = 0; i < n_elems; ++i) {
1426 loop_element e = get_loop_element(l, i);
1427 if (is_ir_loop(e.kind))
1428 if (is_loop_variant(e.son, b))
1435 /* Test whether a value is loop invariant.
1437 * @param n The node to be tested.
1438 * @param block A block node. We pass the block, not the loop as we must
1439 * start off with a block loop to find all proper uses.
1441 * Returns non-zero, if the node n is not changed in the loop block
1442 * belongs to or in inner loops of this blocks loop. */
1443 int is_loop_invariant(ir_node *n, ir_node *block) {
1444 ir_loop *l = get_irn_loop(block);
1445 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1446 return !is_loop_variant(l, get_irn_loop(b));