3 * File name: ir/ana/irscc.c
4 * Purpose: Compute the strongly connected regions and build
5 * backedge/loop datastructures.
6 * A variation on the Tarjan algorithm. See also [Trapp:99],
8 * Author: Goetz Lindenmaier
12 * Copyright: (c) 2002-2003 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
29 #include "irgraph_t.h"
37 /* A variant of the loop tree that avoids loops without head.
38 This reduces the depth of the loop tree. */
39 #define NO_LOOPS_WITHOUT_HEAD 1
41 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
43 static ir_loop *current_loop; /* Current loop construction is working
45 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
46 Each loop node gets a unique number.
47 What for? ev. remove. @@@ */
48 static int current_dfn = 1; /* Counter to generate depth first numbering
51 static int max_loop_depth = 0;
53 void link_to_reg_end (ir_node *n, void *env);
54 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
55 ir_node *get_projx_link(ir_node *cb_projx);
57 /**********************************************************************/
58 /* Node attributes **/
59 /**********************************************************************/
61 /**********************************************************************/
62 /* Node attributes needed for the construction. **/
63 /**********************************************************************/
65 typedef struct scc_info {
66 bool in_stack; /* Marks whether node is on the stack. */
67 int dfn; /* Depth first search number. */
68 int uplink; /* dfn number of ancestor. */
69 /* ir_loop *loop; *//* Refers to the containing loop. */
71 struct section *section;
77 static INLINE scc_info* new_scc_info(void) {
78 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
79 memset (info, 0, sizeof (scc_info));
84 mark_irn_in_stack (ir_node *n) {
85 scc_info *scc = get_irn_link(n);
91 mark_irn_not_in_stack (ir_node *n) {
92 scc_info *scc = get_irn_link(n);
94 scc->in_stack = false;
98 irn_is_in_stack (ir_node *n) {
99 scc_info *scc = get_irn_link(n);
101 return scc->in_stack;
105 set_irn_uplink (ir_node *n, int uplink) {
106 scc_info *scc = get_irn_link(n);
108 scc->uplink = uplink;
112 get_irn_uplink (ir_node *n) {
113 scc_info *scc = get_irn_link(n);
119 set_irn_dfn (ir_node *n, int dfn) {
120 scc_info *scc = get_irn_link(n);
126 get_irn_dfn (ir_node *n) {
127 scc_info *scc = get_irn_link(n);
134 set_irn_loop (ir_node *n, ir_loop *loop) {
138 /* Uses temporary information to get the loop */
140 get_irn_loop (ir_node *n) {
146 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
150 /* Test whether n is contained in this loop. */
151 for (i = 0; i < get_loop_n_nodes(l); i++)
152 if (n == get_loop_node(l, i)) return l;
154 /* Is this a leave in the loop tree? If so loop not found. */
155 if (get_loop_n_sons(l) == 0) return NULL;
157 /* Else descend in the loop tree. */
158 for (i = 0; i < get_loop_n_sons(l); i++) {
159 res = find_nodes_loop(n, get_loop_son(l, i));
165 /* @@@ temporary implementation, costly!!! */
166 ir_loop * get_irn_loop(ir_node *n) {
167 ir_loop *l = get_irg_loop(current_ir_graph);
168 l = find_nodes_loop(n, l);
173 /**********************************************************************/
175 /**********************************************************************/
177 static ir_node **stack = NULL;
178 static int tos = 0; /* top of stack */
181 * initializes the stack
183 static INLINE void init_stack(void) {
185 ARR_RESIZE (ir_node *, stack, 1000);
187 stack = NEW_ARR_F (ir_node *, 1000);
193 static INLINE void free_stack(void) {
201 * push a node onto the stack
203 * @param n The node to push
210 if (tos == ARR_LEN (stack)) {
211 int nlen = ARR_LEN (stack) * 2;
212 ARR_RESIZE (ir_node *, stack, nlen);
215 mark_irn_in_stack(n);
219 * pop a node from the stack
221 * @return The topmost node
223 static INLINE ir_node *
226 ir_node *n = stack[--tos];
227 mark_irn_not_in_stack(n);
232 * The nodes up to n belong to the current loop.
233 * Removes them from the stack and adds them to the current loop.
236 pop_scc_to_loop (ir_node *n)
244 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
247 set_irn_dfn(m, loop_node_cnt);
248 add_loop_node(current_loop, m);
249 set_irn_loop(m, current_loop);
252 /* if (m==n) break;*/
255 /* i might be bigger than 1 for dead (and that's why bad) loops */
257 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
261 /* GL ??? my last son is my grandson??? Removes loops with no
262 ir_nodes in them. Such loops have only another loop as son. (Why
263 can't they have two loops as sons? Does it never get that far? ) */
264 static void close_loop (ir_loop *l)
266 int last = get_loop_n_elements(l) - 1;
267 loop_element lelement = get_loop_element(l, last);
268 ir_loop *last_son = lelement.son;
270 if (get_kind(last_son) == k_ir_loop &&
271 get_loop_n_elements(last_son) == 1) {
274 lelement = get_loop_element(last_son, 0);
277 if (get_kind(gson) == k_ir_loop) {
278 loop_element new_last_son;
280 gson->outer_loop = l;
281 new_last_son.son = gson;
282 l->children[last] = new_last_son;
289 /* Removes and unmarks all nodes up to n from the stack.
290 The nodes must be visited once more to assign them to a scc. */
292 pop_scc_unmark_visit (ir_node *n)
298 set_irn_visited(m, 0);
302 /**********************************************************************/
303 /* The loop datastructure. **/
304 /**********************************************************************/
306 /* Allocates a new loop as son of current_loop. Sets current_loop
307 to the new loop and returns the father. */
308 ir_loop *new_loop (void) {
309 ir_loop *father, *son;
311 father = current_loop;
313 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
314 memset (son, 0, sizeof (ir_loop));
315 son->kind = k_ir_loop;
316 son->children = NEW_ARR_F (loop_element, 0);
320 son->outer_loop = father;
321 add_loop_son(father, son);
322 son->depth = father->depth+1;
323 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
324 } else { /* The root loop */
325 son->outer_loop = son;
330 son->loop_nr = get_irp_new_node_nr();
339 /* Finishes the datastructures, copies the arrays to the obstack
341 A. Schoesser: Caution: loop -> sons is gone. */
342 static void mature_loop (ir_loop *loop) {
345 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
346 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
347 DEL_ARR_F(loop->sons);
348 loop->sons = new_sons;
352 /* Returns outer loop, itself if outermost. */
353 ir_loop *get_loop_outer_loop (ir_loop *loop) {
354 assert(loop && loop->kind == k_ir_loop);
355 return loop->outer_loop;
358 /* Returns nesting depth of this loop */
359 int get_loop_depth (ir_loop *loop) {
360 assert(loop); assert(loop->kind == k_ir_loop);
364 /* Returns the number of inner loops */
365 int get_loop_n_sons (ir_loop *loop) {
366 assert(loop && loop->kind == k_ir_loop);
367 return(loop -> n_sons);
370 /* Returns the pos`th loop_node-child *
371 * TODO: This method isn`t very efficient ! *
372 * Returns NULL if there isn`t a pos`th loop_node */
373 ir_loop *get_loop_son (ir_loop *loop, int pos) {
374 int child_nr = 0, loop_nr = -1;
376 assert(loop && loop->kind == k_ir_loop);
377 while(child_nr < ARR_LEN(loop->children))
379 if(*(loop -> children[child_nr].kind) == k_ir_loop)
382 return(loop -> children[child_nr].son);
388 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
392 add_loop_son(ir_loop *loop, ir_loop *son) {
395 assert(loop && loop->kind == k_ir_loop);
396 assert(get_kind(son) == k_ir_loop);
397 ARR_APP1 (loop_element, loop->children, lson);
401 /* Returns the number of nodes in the loop */
402 int get_loop_n_nodes (ir_loop *loop) {
403 assert(loop); assert(loop->kind == k_ir_loop);
404 return loop -> n_nodes;
405 /* return ARR_LEN(loop->nodes); */
408 /* Returns the pos`th ir_node-child *
409 * TODO: This method isn`t very efficient ! *
410 * Returns NULL if there isn`t a pos`th ir_node */
411 ir_node *get_loop_node (ir_loop *loop, int pos) {
412 int child_nr, node_nr = -1;
414 assert(loop && loop->kind == k_ir_loop);
415 assert(pos < get_loop_n_nodes(loop));
417 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
418 if(*(loop -> children[child_nr].kind) == k_ir_node)
421 return(loop -> children[child_nr].node);
424 printf("pos: %d\n", pos);
425 assert(0 && "no child at pos found");
429 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
433 add_loop_node(ir_loop *loop, ir_node *n) {
436 assert(loop && loop->kind == k_ir_loop);
437 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
438 ARR_APP1 (loop_element, loop->children, ln);
442 /** Returns the number of elements contained in loop. */
443 int get_loop_n_elements (ir_loop *loop) {
444 assert(loop && loop->kind == k_ir_loop);
445 return(ARR_LEN(loop->children));
449 Returns the pos`th loop element.
450 This may be a loop_node or a ir_node. The caller of this function has
451 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
452 and then select the appropriate "loop_element.node" or "loop_element.son".
455 loop_element get_loop_element (ir_loop *loop, int pos) {
456 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
458 return(loop -> children[pos]);
461 int get_loop_element_pos(ir_loop *loop, void *le) {
463 assert(loop && loop->kind == k_ir_loop);
465 for (i = 0; i < get_loop_n_elements(loop); i++)
466 if (get_loop_element(loop, i).node == le) return i;
470 int get_loop_loop_nr(ir_loop *loop) {
471 assert(loop && loop->kind == k_ir_loop);
473 return loop->loop_nr;
480 /** A field to connect additional information to a loop. Only valid
481 if libfirm_debug is set. */
482 void set_loop_link (ir_loop *loop, void *link) {
483 assert(loop && loop->kind == k_ir_loop);
488 void *get_loop_link (const ir_loop *loop) {
489 assert(loop && loop->kind == k_ir_loop);
497 int (is_ir_loop)(const void *thing) {
498 return _is_ir_loop(thing);
501 /* The outermost loop is remarked in the surrounding graph. */
502 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
503 _set_irg_loop(irg, loop);
506 /* Returns the root loop info (if exists) for an irg. */
507 ir_loop *(get_irg_loop)(ir_graph *irg) {
508 return _get_irg_loop(irg);
512 /**********************************************************************/
513 /* Constructing and destructing the loop/backedge information. **/
514 /**********************************************************************/
516 /* Initialization steps. **********************************************/
519 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);
543 cg_walk (init_node, NULL, NULL);
545 #if EXPERIMENTAL_LOOP_TREE
546 cg_walk (link_to_reg_end, NULL, NULL);
550 /* Condition for breaking the recursion. */
551 static bool is_outermost_Start(ir_node *n) {
552 /* Test whether this is the outermost Start node. If so
553 recursion must end. */
554 if ((get_irn_op(n) == op_Block) &&
555 (get_Block_n_cfgpreds(n) == 1) &&
556 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
557 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
561 /* @@@ Bad condition:
562 not possible in interprocedural view as outermost_graph is
563 not necessarily the only with a dead-end start block.
564 Besides current_ir_graph is not set properly. */
565 if ((get_irn_op(n) == op_Block) &&
566 (n == get_irg_start_block(current_ir_graph))) {
567 if ((!get_interprocedural_view()) ||
568 (current_ir_graph == outermost_ir_graph))
575 /* When to walk from nodes to blocks. Only for Control flow operations? */
577 get_start_index(ir_node *n) {
578 #undef BLOCK_BEFORE_NODE
579 #define BLOCK_BEFORE_NODE 1
581 #if BLOCK_BEFORE_NODE
583 /* This version assures, that all nodes are ordered absolutely. This allows
584 to undef all nodes in the heap analysis if the block is false, which means
586 I.e., with this code, the order on the loop tree is correct. But a (single)
587 test showed the loop tree is deeper. */
588 if (get_irn_op(n) == op_Phi ||
589 get_irn_op(n) == op_Block ||
590 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
591 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
592 get_irn_pinned(n) == op_pin_state_floats))
593 // Here we could test for backedge at -1 which is illegal
600 /* This version causes deeper loop trees (at least we verified this
602 But it guarantees that Blocks are analysed before nodes contained in the
603 block. If so, we can set the value to undef if the block is not \
605 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
615 static void test(ir_node *pred, ir_node *root, ir_node *this) {
617 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
619 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
620 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
621 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
623 printf("tos: %d\n", tos);
625 for (i = tos; i >= 0; i--) {
626 ir_node *n = stack[i];
628 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
633 /* Test for legal loop header: Block, Phi, ... */
634 static INLINE bool is_possible_loop_head(ir_node *n) {
635 ir_op *op = get_irn_op(n);
636 return ((op == op_Block) ||
638 ((op == op_Filter) && get_interprocedural_view()));
641 /* Returns true if n is a loop header, i.e., it is a Block, Phi
642 or Filter node and has predecessors within the loop and out
644 @arg root: only needed for assertion. */
646 is_head (ir_node *n, ir_node *root)
649 int some_outof_loop = 0, some_in_loop = 0;
651 /* Test for legal loop header: Block, Phi, ... */
652 if (!is_possible_loop_head(n))
655 if (!is_outermost_Start(n)) {
656 arity = get_irn_arity(n);
657 for (i = get_start_index(n); i < arity; i++) {
658 ir_node *pred = get_irn_n(n, i);
660 if (is_backedge(n, i)) continue;
661 if (!irn_is_in_stack(pred)) {
664 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
665 DDMN(n); DDMN(pred); DDMN(root);
666 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
672 return some_outof_loop && some_in_loop;
675 /* Returns true if n is possible loop head of an endless loop.
676 I.e., it is a Block, Phi or Filter node and has only predecessors
678 @arg root: only needed for assertion. */
680 is_endless_head (ir_node *n, ir_node *root)
683 int some_outof_loop = 0, some_in_loop = 0;
685 /* Test for legal loop header: Block, Phi, ... */
686 if (!is_possible_loop_head(n))
689 if (!is_outermost_Start(n)) {
690 arity = get_irn_arity(n);
691 for (i = get_start_index(n); i < arity; i++) {
692 ir_node *pred = get_irn_n(n, i);
694 if (is_backedge(n, i)) { continue; }
695 if (!irn_is_in_stack(pred)) {
696 some_outof_loop = 1; //printf(" some out of loop ");
698 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
699 DDMN(pred); DDMN(root);
700 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
706 return !some_outof_loop && some_in_loop;
709 /* Returns index of the predecessor with the smallest dfn number
710 greater-equal than limit. */
712 smallest_dfn_pred (ir_node *n, int limit)
714 int i, index = -2, min = -1;
716 if (!is_outermost_Start(n)) {
717 int arity = get_irn_arity(n);
718 for (i = get_start_index(n); i < arity; i++) {
719 ir_node *pred = get_irn_n(n, i);
721 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
722 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
724 min = get_irn_dfn(pred);
731 /* Returns index of the predecessor with the largest dfn number. */
733 largest_dfn_pred (ir_node *n)
735 int i, index = -2, max = -1;
737 if (!is_outermost_Start(n)) {
738 int arity = get_irn_arity(n);
739 for (i = get_start_index(n); i < arity; i++) {
740 ir_node *pred = get_irn_n(n, i);
741 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
742 if (get_irn_dfn(pred) > max) {
744 max = get_irn_dfn(pred);
751 /** Searches the stack for possible loop heads. Tests these for backedges.
752 If it finds a head with an unmarked backedge it marks this edge and
753 returns the tail of the loop.
754 If it finds no backedge returns NULL.
755 ("disable_backedge" in fiasco)
757 * @param n A node where uplink == dfn.
761 find_tail (ir_node *n) {
763 int i, res_index = -2;
766 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
768 m = stack[tos-1]; /* tos = top of stack */
769 if (is_head (m, n)) {
770 res_index = smallest_dfn_pred(m, 0);
771 if ((res_index == -2) && /* no smallest dfn pred found. */
775 if (m == n) return NULL; // Is this to catch Phi - self loops?
776 for (i = tos-2; i >= 0; --i) {
779 if (is_head (m, n)) {
780 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
781 if (res_index == -2) /* no smallest dfn pred found. */
782 res_index = largest_dfn_pred (m);
784 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
790 /* We should not walk past our selves on the stack: The upcoming nodes
791 are not in this loop. We assume a loop not reachable from Start. */
800 /* A dead loop not reachable from Start. */
801 for (i = tos-2; i >= 0; --i) {
803 if (is_endless_head (m, n)) {
804 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
805 if (res_index == -2) /* no smallest dfn pred found. */
806 res_index = largest_dfn_pred (m);
809 if (m == n) { break; } /* It's not an unreachable loop, either. */
811 //assert(0 && "no head found on stack");
815 if (res_index <= -2) {
816 /* It's a completely bad loop: without Phi/Block nodes that can
817 be a head. I.e., the code is "dying". We break the loop by
818 setting Bad nodes. */
819 int arity = get_irn_arity(n);
820 for (i = -1; i < arity; ++i) {
821 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
825 assert (res_index > -2);
827 set_backedge (m, res_index);
828 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
832 #if EXPERIMENTAL_LOOP_TREE
834 /* ----------------------------------------------------------------
835 AS: This is experimental code to build loop trees suitable for
836 the heap analysis. Does not work correctly right now... :-(
839 Search in stack for the corresponding first Call-End-ProjX that
840 corresponds to one of the control flow predecessors of the given
841 block, that is the possible callers.
842 returns: the control predecessor to chose\
843 or -1 if no corresponding Call-End-Node could be found
845 - -------------------------------------------------------------- */
847 int search_endproj_in_stack(ir_node *start_block)
850 assert(is_Block(start_block));
851 for(i = tos - 1; i >= 0; --i)
854 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
855 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
857 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
858 ir_node *end_projx = stack[i];
860 int arity = get_irn_arity(start_block);
861 for(j = 0; j < arity; j++)
863 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
864 get_Proj_proj(end_projx));
866 if(get_irn_n(start_block, j) == begin_projx)
868 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
878 static pmap *projx_link = NULL;
880 void link_to_reg_end (ir_node *n, void *env) {
881 if(get_irn_op(n) == op_Proj &&
882 get_irn_mode(n) == mode_X &&
883 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
884 /* Reg End Projx -> Find the CallBegin Projx and hash it */
885 ir_node *end_projx = n;
886 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
887 get_Proj_proj(end_projx));
888 printf("Linked the following ProjxNodes:\n");
891 set_projx_link(begin_projx, end_projx);
895 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
897 if(projx_link == NULL)
898 projx_link = pmap_create();
899 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
902 ir_node *get_projx_link(ir_node *cb_projx)
904 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
910 is_outermost_loop(ir_loop *l) {
911 return l == get_loop_outer_loop(l);
915 /*-----------------------------------------------------------*
916 * The core algorithm. *
917 *-----------------------------------------------------------*/
919 static void scc (ir_node *n) {
921 if (irn_visited(n)) return;
924 /* Initialize the node */
925 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
926 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
927 set_irn_loop(n, NULL);
931 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
932 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
933 so is_backedge does not access array[-1] but correctly returns false! */
935 if (!is_outermost_Start(n)) {
936 int arity = get_irn_arity(n);
938 for (i = get_start_index(n); i < arity; i++) {
940 if (is_backedge(n, i)) continue;
941 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
942 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
944 if (irn_is_in_stack(m)) {
945 /* Uplink of m is smaller if n->m is a backedge.
946 Propagate the uplink to mark the loop. */
947 if (get_irn_uplink(m) < get_irn_uplink(n))
948 set_irn_uplink(n, get_irn_uplink(m));
953 if (get_irn_dfn(n) == get_irn_uplink(n)) {
954 /* This condition holds for
955 1) the node with the incoming backedge.
956 That is: We found a loop!
957 2) Straight line code, because no uplink has been propagated, so the
958 uplink still is the same as the dfn.
960 But n might not be a proper loop head for the analysis. Proper loop
961 heads are Block and Phi nodes. find_tail searches the stack for
962 Block's and Phi's and takes those nodes as loop heads for the current
963 loop instead and marks the incoming edge as backedge. */
965 ir_node *tail = find_tail(n);
967 /* We have a loop, that is no straight line code,
968 because we found a loop head!
969 Next actions: Open a new loop on the loop tree and
970 try to find inner loops */
972 #if NO_LOOPS_WITHOUT_HEAD
973 /* This is an adaption of the algorithm from fiasco / optscc to
974 * avoid loops without Block or Phi as first node. This should
975 * severely reduce the number of evaluations of nodes to detect
976 * a fixpoint in the heap analysis.
977 * Further it avoids loops without firm nodes that cause errors
978 * in the heap analyses.
979 * But attention: don't do it for the outermost loop: This loop
980 * is not iterated. A first block can be a loop head in case of
981 * an endless recursion. */
985 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
993 ir_loop *l = new_loop();
996 /* Remove the loop from the stack ... */
997 pop_scc_unmark_visit (n);
999 /* The current backedge has been marked, that is temporarily eliminated,
1000 by find tail. Start the scc algorithm
1001 anew on the subgraph that is left (the current loop without the backedge)
1002 in order to find more inner loops. */
1005 assert (irn_visited(n));
1006 #if NO_LOOPS_WITHOUT_HEAD
1013 /* No loop head was found, that is we have straightline code.
1014 Pop all nodes from the stack to the current loop. */
1020 static void my_scc (ir_node *n) {
1022 if (irn_visited(n)) return;
1023 mark_irn_visited(n);
1025 /* Initialize the node */
1026 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1027 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1028 set_irn_loop(n, NULL);
1032 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1033 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1034 so is_backedge does not access array[-1] but correctly returns false! */
1036 if (!is_outermost_Start(n)) {
1037 int arity = get_irn_arity(n);
1039 for (i = get_start_index(n); i < arity; i++) {
1041 if (is_backedge(n, i)) continue;
1042 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1043 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1045 if (irn_is_in_stack(m)) {
1046 /* Uplink of m is smaller if n->m is a backedge.
1047 Propagate the uplink to mark the loop. */
1048 if (get_irn_uplink(m) < get_irn_uplink(n))
1049 set_irn_uplink(n, get_irn_uplink(m));
1054 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1055 /* This condition holds for
1056 1) the node with the incoming backedge.
1057 That is: We found a loop!
1058 2) Straight line code, because no uplink has been propagated, so the
1059 uplink still is the same as the dfn.
1061 But n might not be a proper loop head for the analysis. Proper loop
1062 heads are Block and Phi nodes. find_tail searches the stack for
1063 Block's and Phi's and takes those nodes as loop heads for the current
1064 loop instead and marks the incoming edge as backedge. */
1066 ir_node *tail = find_tail(n);
1068 /* We have a loop, that is no straight line code,
1069 because we found a loop head!
1070 Next actions: Open a new loop on the loop tree and
1071 try to find inner loops */
1073 #if NO_LOOPS_WITHOUT_HEAD
1074 /* This is an adaption of the algorithm from fiasco / optscc to
1075 * avoid loops without Block or Phi as first node. This should
1076 * severely reduce the number of evaluations of nodes to detect
1077 * a fixpoint in the heap analysis.
1078 * Further it avoids loops without firm nodes that cause errors
1079 * in the heap analyses. */
1083 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1091 ir_loop *l = new_loop();
1094 /* Remove the loop from the stack ... */
1095 pop_scc_unmark_visit (n);
1097 /* The current backedge has been marked, that is temporarily eliminated,
1098 by find tail. Start the scc algorithm
1099 anew on the subgraph that is left (the current loop without the backedge)
1100 in order to find more inner loops. */
1103 assert (irn_visited(n));
1104 #if NO_LOOPS_WITHOUT_HEAD
1111 /* No loop head was found, that is we have straightline code.
1112 Pop all nodes from the stack to the current loop. */
1118 /* Constructs backedge information for irg. In interprocedural view constructs
1119 backedges for all methods called by irg, too. */
1120 int construct_backedges(ir_graph *irg) {
1121 ir_graph *rem = current_ir_graph;
1124 assert(!get_interprocedural_view() &&
1125 "not implemented, use construct_ip_backedges");
1128 current_ir_graph = irg;
1129 outermost_ir_graph = irg;
1131 init_scc(current_ir_graph);
1133 current_loop = NULL;
1134 new_loop(); /* sets current_loop */
1135 head_rem = current_loop; /* Just for assertion */
1137 inc_irg_visited(current_ir_graph);
1139 scc(get_irg_end(current_ir_graph));
1141 assert(head_rem == current_loop);
1142 set_irg_loop(current_ir_graph, current_loop);
1143 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1144 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1146 irg->loops = current_loop;
1150 count_loop (the_loop, &count, &depth);
1154 current_ir_graph = rem;
1156 return max_loop_depth;
1160 int construct_ip_backedges (void) {
1161 ir_graph *rem = current_ir_graph;
1162 int rem_ipv = get_interprocedural_view();
1166 assert(get_irp_ip_view_state() == ip_view_valid);
1168 outermost_ir_graph = get_irp_main_irg();
1172 current_loop = NULL;
1173 new_loop(); /* sets current_loop */
1174 set_interprocedural_view(true);
1176 inc_max_irg_visited();
1177 for (i = 0; i < get_irp_n_irgs(); i++)
1178 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1180 /** We have to start the walk at the same nodes as cg_walk. **/
1181 /* Walk starting at unreachable procedures. Only these
1182 * have End blocks visible in interprocedural view. */
1183 for (i = 0; i < get_irp_n_irgs(); i++) {
1185 current_ir_graph = get_irp_irg(i);
1187 sb = get_irg_start_block(current_ir_graph);
1189 if ((get_Block_n_cfgpreds(sb) > 1) ||
1190 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1192 scc(get_irg_end(current_ir_graph));
1195 /* Check whether we walked all procedures: there could be procedures
1196 with cyclic calls but no call from the outside. */
1197 for (i = 0; i < get_irp_n_irgs(); i++) {
1199 current_ir_graph = get_irp_irg(i);
1201 /* Test start block: if inner procedure end and end block are not
1202 * visible and therefore not marked. */
1203 sb = get_irg_start_block(current_ir_graph);
1204 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1207 /* Walk all endless loops in inner procedures.
1208 * We recognize an inner procedure if the End node is not visited. */
1209 for (i = 0; i < get_irp_n_irgs(); i++) {
1211 current_ir_graph = get_irp_irg(i);
1213 e = get_irg_end(current_ir_graph);
1214 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1216 /* Don't visit the End node. */
1217 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1221 set_irg_loop(outermost_ir_graph, current_loop);
1222 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1223 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1225 current_ir_graph = rem;
1226 set_interprocedural_view(rem_ipv);
1227 return max_loop_depth;
1230 void my_construct_ip_backedges (void) {
1231 ir_graph *rem = current_ir_graph;
1232 int rem_ipv = get_interprocedural_view();
1235 assert(get_irp_ip_view_state() == ip_view_valid);
1237 outermost_ir_graph = get_irp_main_irg();
1241 current_loop = NULL;
1242 new_loop(); /* sets current_loop */
1243 set_interprocedural_view(true);
1245 inc_max_irg_visited();
1246 for (i = 0; i < get_irp_n_irgs(); i++)
1247 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1249 /** We have to start the walk at the same nodes as cg_walk. **/
1250 /* Walk starting at unreachable procedures. Only these
1251 * have End blocks visible in interprocedural view. */
1252 for (i = 0; i < get_irp_n_irgs(); i++) {
1254 current_ir_graph = get_irp_irg(i);
1256 sb = get_irg_start_block(current_ir_graph);
1258 if ((get_Block_n_cfgpreds(sb) > 1) ||
1259 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1261 my_scc(get_irg_end(current_ir_graph));
1264 /* Check whether we walked all procedures: there could be procedures
1265 with cyclic calls but no call from the outside. */
1266 for (i = 0; i < get_irp_n_irgs(); i++) {
1268 current_ir_graph = get_irp_irg(i);
1270 /* Test start block: if inner procedure end and end block are not
1271 * visible and therefore not marked. */
1272 sb = get_irg_start_block(current_ir_graph);
1273 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1276 /* Walk all endless loops in inner procedures.
1277 * We recognize an inner procedure if the End node is not visited. */
1278 for (i = 0; i < get_irp_n_irgs(); i++) {
1280 current_ir_graph = get_irp_irg(i);
1282 e = get_irg_end(current_ir_graph);
1283 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1285 /* Don't visit the End node. */
1286 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1290 set_irg_loop(outermost_ir_graph, current_loop);
1291 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1292 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1294 current_ir_graph = rem;
1295 set_interprocedural_view(rem_ipv);
1298 static void reset_backedges(ir_node *n) {
1299 if (is_possible_loop_head(n)) {
1300 int rem = get_interprocedural_view();
1302 set_interprocedural_view(true);
1304 set_interprocedural_view(true);
1306 set_interprocedural_view(rem);
1312 static void loop_reset_backedges(ir_loop *l) {
1314 reset_backedges(get_loop_node(l, 0));
1315 for (i = 0; i < get_loop_n_nodes(l); ++i)
1316 set_irn_loop(get_loop_node(l, i), NULL);
1317 for (i = 0; i < get_loop_n_sons(l); ++i) {
1318 loop_reset_backedges(get_loop_son(l, i));
1323 static void loop_reset_node(ir_node *n, void *env) {
1324 set_irn_loop(n, NULL);
1329 /** Removes all loop information.
1330 Resets all backedges */
1331 void free_loop_information(ir_graph *irg) {
1332 /* We can not use this recursion, as the loop might contain
1333 illegal nodes by now. Why else would we throw away the
1335 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1337 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1338 set_irg_loop(irg, NULL);
1339 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1340 /* We cannot free the loop nodes, they are on the obstack. */
1344 void free_all_loop_information (void) {
1346 int rem = get_interprocedural_view();
1347 set_interprocedural_view(true); /* To visit all filter nodes */
1348 for (i = 0; i < get_irp_n_irgs(); i++) {
1349 free_loop_information(get_irp_irg(i));
1351 set_interprocedural_view(rem);
1358 /* Debug stuff *************************************************/
1360 static int test_loop_node(ir_loop *l) {
1361 int i, has_node = 0, found_problem = 0;
1364 assert(l && l->kind == k_ir_loop);
1366 if (get_loop_n_elements(l) == 0) {
1367 printf(" Loop completely empty! "); DDML(l);
1369 dump_loop(l, "-ha");
1372 le = get_loop_element(l, 0);
1373 if (*(le.kind) != k_ir_node) {
1374 assert(le.kind && *(le.kind) == k_ir_loop);
1375 printf(" First loop element is not a node! "); DDML(l);
1376 printf(" "); DDML(le.son);
1379 dump_loop(l, "-ha");
1382 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1383 printf(" Wrong node as head! "); DDML(l);
1384 printf(" "); DDMN(le.node);
1386 dump_loop(l, "-ha");
1389 if ((get_loop_depth(l) != 0) &&
1390 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1391 printf(" Loop head has no backedges! "); DDML(l);
1392 printf(" "); DDMN(le.node);
1394 dump_loop(l, "-ha");
1399 for (i = 0; i < get_loop_n_elements(l); ++i) {
1400 le = get_loop_element(l, i);
1401 if (*(le.kind) == k_ir_node)
1404 if (test_loop_node(le.son)) found_problem = 1;
1407 if (has_node == 0) {
1408 printf(" Loop has no firm node! "); DDML(l);
1410 dump_loop(l, "-ha");
1413 return found_problem;
1416 /** Prints all loop nodes that
1417 * - do not have any firm nodes, only loop sons
1418 * - the header is not a Phi, Block or Filter.
1420 void find_strange_loop_nodes(ir_loop *l) {
1421 int found_problem = 0;
1422 printf("\nTesting loop "); DDML(l);
1423 found_problem = test_loop_node(l);
1424 printf("Finished Test\n\n");
1425 if (found_problem) exit(0);
1429 /* ------------------------------------------------------------------- */
1430 /* Simple analyses based on the loop information */
1431 /* ------------------------------------------------------------------- */
1433 int is_loop_variant(ir_loop *l, ir_loop *b) {
1436 if (l == b) return true;
1438 n_elems = get_loop_n_elements(l);
1439 for (i = 0; i < n_elems; ++i) {
1440 loop_element e = get_loop_element(l, i);
1441 if (is_ir_loop(e.kind))
1442 if (is_loop_variant(e.son, b))
1449 /* Test whether a value is loop invariant.
1451 * @param n The node to be tested.
1452 * @param block A block node. We pass the block, not the loop as we must
1453 * start off with a block loop to find all proper uses.
1455 * Returns true, if the node n is not changed in the loop block
1456 * belongs to or in inner loops of this blocks loop. */
1457 int is_loop_invariant(ir_node *n, ir_node *block) {
1458 ir_loop *l = get_irn_loop(block);
1459 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1460 return !is_loop_variant(l, get_irn_loop(b));