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-2006 Universität Karlsruhe
13 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
30 #include "irgraph_t.h"
38 /* A variant of the loop tree that avoids loops without head.
39 This reduces the depth of the loop tree. */
40 #define NO_LOOPS_WITHOUT_HEAD 1
42 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
44 static ir_loop *current_loop; /* Current loop construction is working
46 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
47 Each loop node gets a unique number.
48 What for? ev. remove. @@@ */
49 static int current_dfn = 1; /* Counter to generate depth first numbering
52 static int max_loop_depth = 0;
54 void link_to_reg_end (ir_node *n, void *env);
55 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
56 ir_node *get_projx_link(ir_node *cb_projx);
58 /**********************************************************************/
59 /* Node attributes **/
60 /**********************************************************************/
62 /**********************************************************************/
63 /* Node attributes needed for the construction. **/
64 /**********************************************************************/
66 typedef struct scc_info {
67 int in_stack; /**< Marks whether node is on the stack. */
68 int dfn; /**< Depth first search number. */
69 int uplink; /**< dfn number of ancestor. */
70 /* ir_loop *loop; *//* Refers to the containing loop. */
72 struct section *section;
78 static INLINE scc_info* new_scc_info(void) {
79 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
80 memset (info, 0, sizeof (scc_info));
85 mark_irn_in_stack (ir_node *n) {
86 scc_info *scc = get_irn_link(n);
92 mark_irn_not_in_stack (ir_node *n) {
93 scc_info *scc = get_irn_link(n);
99 irn_is_in_stack (ir_node *n) {
100 scc_info *scc = get_irn_link(n);
102 return scc->in_stack;
106 set_irn_uplink (ir_node *n, int uplink) {
107 scc_info *scc = get_irn_link(n);
109 scc->uplink = uplink;
113 get_irn_uplink (ir_node *n) {
114 scc_info *scc = get_irn_link(n);
120 set_irn_dfn (ir_node *n, int dfn) {
121 scc_info *scc = get_irn_link(n);
127 get_irn_dfn (ir_node *n) {
128 scc_info *scc = get_irn_link(n);
135 set_irn_loop (ir_node *n, ir_loop *loop) {
139 /* Uses temporary information to get the loop */
140 ir_loop *(get_irn_loop)(const ir_node *n) {
141 return _get_irn_loop(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)(const ir_loop *loop) {
354 return _get_loop_outer_loop(loop);
357 /* Returns nesting depth of this loop */
358 int (get_loop_depth)(const ir_loop *loop) {
359 return _get_loop_depth(loop);
362 /* Returns the number of inner loops */
363 int (get_loop_n_sons)(const ir_loop *loop) {
364 return _get_loop_n_sons(loop);
367 /* Returns the pos`th loop_node-child *
368 * TODO: This method isn`t very efficient ! *
369 * Returns NULL if there isn`t a pos`th loop_node */
370 ir_loop *get_loop_son (ir_loop *loop, int pos) {
371 int child_nr = 0, loop_nr = -1;
373 assert(loop && loop->kind == k_ir_loop);
374 while(child_nr < ARR_LEN(loop->children))
376 if(*(loop -> children[child_nr].kind) == k_ir_loop)
379 return(loop -> children[child_nr].son);
385 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
389 add_loop_son(ir_loop *loop, ir_loop *son) {
392 assert(loop && loop->kind == k_ir_loop);
393 assert(get_kind(son) == k_ir_loop);
394 ARR_APP1 (loop_element, loop->children, lson);
398 /* Returns the number of nodes in the loop */
399 int get_loop_n_nodes (ir_loop *loop) {
400 assert(loop); assert(loop->kind == k_ir_loop);
401 return loop -> n_nodes;
402 /* return ARR_LEN(loop->nodes); */
405 /* Returns the pos`th ir_node-child *
406 * TODO: This method isn`t very efficient ! *
407 * Returns NULL if there isn`t a pos`th ir_node */
408 ir_node *get_loop_node (ir_loop *loop, int pos) {
409 int child_nr, node_nr = -1;
411 assert(loop && loop->kind == k_ir_loop);
412 assert(pos < get_loop_n_nodes(loop));
414 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
415 if(*(loop -> children[child_nr].kind) == k_ir_node)
418 return(loop -> children[child_nr].node);
421 printf("pos: %d\n", pos);
422 assert(0 && "no child at pos found");
426 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
430 add_loop_node(ir_loop *loop, ir_node *n) {
433 assert(loop && loop->kind == k_ir_loop);
434 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
435 ARR_APP1 (loop_element, loop->children, ln);
439 /* Returns the number of elements contained in loop. */
440 int get_loop_n_elements (const ir_loop *loop) {
441 assert(loop && loop->kind == k_ir_loop);
442 return(ARR_LEN(loop->children));
446 Returns the pos`th loop element.
447 This may be a loop_node or a ir_node. The caller of this function has
448 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
449 and then select the appropriate "loop_element.node" or "loop_element.son".
452 loop_element get_loop_element(const ir_loop *loop, int pos) {
453 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
454 return(loop -> children[pos]);
457 int get_loop_element_pos(const ir_loop *loop, void *le) {
459 assert(loop && loop->kind == k_ir_loop);
461 n = get_loop_n_elements(loop);
462 for (i = 0; i < n; i++)
463 if (get_loop_element(loop, i).node == le) return i;
467 int get_loop_loop_nr(const ir_loop *loop) {
468 assert(loop && loop->kind == k_ir_loop);
470 return loop->loop_nr;
477 /** A field to connect additional information to a loop. Only valid
478 if libfirm_debug is set. */
479 void set_loop_link (ir_loop *loop, void *link) {
480 assert(loop && loop->kind == k_ir_loop);
485 void *get_loop_link (const ir_loop *loop) {
486 assert(loop && loop->kind == k_ir_loop);
494 int (is_ir_loop)(const void *thing) {
495 return _is_ir_loop(thing);
498 /* The outermost loop is remarked in the surrounding graph. */
499 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
500 _set_irg_loop(irg, loop);
503 /* Returns the root loop info (if exists) for an irg. */
504 ir_loop *(get_irg_loop)(ir_graph *irg) {
505 return _get_irg_loop(irg);
509 /**********************************************************************/
510 /* Constructing and destructing the loop/backedge information. **/
511 /**********************************************************************/
513 /* Initialization steps. **********************************************/
516 init_node (ir_node *n, void *env) {
517 set_irn_link (n, new_scc_info());
522 init_scc_common (void) {
529 init_scc (ir_graph *irg) {
531 irg_walk_graph (irg, init_node, NULL, NULL);
533 irg_walk (irg, link_to_reg_end, NULL, NULL);
540 cg_walk (init_node, NULL, NULL);
542 #if EXPERIMENTAL_LOOP_TREE
543 cg_walk (link_to_reg_end, NULL, NULL);
547 /* Condition for breaking the recursion. */
548 static int is_outermost_Start(ir_node *n) {
549 /* Test whether this is the outermost Start node. If so
550 recursion must end. */
551 if ((get_irn_op(n) == op_Block) &&
552 (get_Block_n_cfgpreds(n) == 1) &&
553 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
554 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
558 /* @@@ Bad condition:
559 not possible in interprocedural view as outermost_graph is
560 not necessarily the only with a dead-end start block.
561 Besides current_ir_graph is not set properly. */
562 if ((get_irn_op(n) == op_Block) &&
563 (n == get_irg_start_block(current_ir_graph))) {
564 if ((!get_interprocedural_view()) ||
565 (current_ir_graph == outermost_ir_graph))
572 /* When to walk from nodes to blocks. Only for Control flow operations? */
574 get_start_index(ir_node *n) {
575 #undef BLOCK_BEFORE_NODE
576 #define BLOCK_BEFORE_NODE 1
578 #if BLOCK_BEFORE_NODE
580 /* This version assures, that all nodes are ordered absolutely. This allows
581 to undef all nodes in the heap analysis if the block is false, which means
583 I.e., with this code, the order on the loop tree is correct. But a (single)
584 test showed the loop tree is deeper. */
585 if (get_irn_op(n) == op_Phi ||
586 get_irn_op(n) == op_Block ||
587 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
588 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
589 get_irn_pinned(n) == op_pin_state_floats))
590 // Here we could test for backedge at -1 which is illegal
597 /* This version causes deeper loop trees (at least we verified this
599 But it guarantees that Blocks are analysed before nodes contained in the
600 block. If so, we can set the value to undef if the block is not \
602 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
612 static void test(ir_node *pred, ir_node *root, ir_node *this) {
614 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
616 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
617 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
618 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
620 printf("tos: %d\n", tos);
622 for (i = tos; i >= 0; i--) {
623 ir_node *n = stack[i];
625 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
630 /* Test for legal loop header: Block, Phi, ... */
631 static INLINE int is_possible_loop_head(ir_node *n) {
632 ir_op *op = get_irn_op(n);
633 return ((op == op_Block) ||
635 ((op == op_Filter) && get_interprocedural_view()));
638 /* Returns non-zero if n is a loop header, i.e., it is a Block, Phi
639 or Filter node and has predecessors within the loop and out
641 @arg root: only needed for assertion. */
643 is_head (ir_node *n, ir_node *root)
646 int some_outof_loop = 0, some_in_loop = 0;
648 /* Test for legal loop header: Block, Phi, ... */
649 if (!is_possible_loop_head(n))
652 if (!is_outermost_Start(n)) {
653 arity = get_irn_arity(n);
654 for (i = get_start_index(n); i < arity; i++) {
655 ir_node *pred = get_irn_n(n, i);
657 if (is_backedge(n, i)) continue;
658 if (!irn_is_in_stack(pred)) {
661 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
662 DDMN(n); DDMN(pred); DDMN(root);
663 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
669 return some_outof_loop && some_in_loop;
673 * Returns non-zero if n is possible loop head of an endless loop.
674 * I.e., it is a Block, Phi or Filter node and has only predecessors
676 * @param root: only needed for assertion.
679 is_endless_head (ir_node *n, ir_node *root)
682 int some_outof_loop = 0, some_in_loop = 0;
684 /* Test for legal loop header: Block, Phi, ... */
685 if (!is_possible_loop_head(n))
688 if (!is_outermost_Start(n)) {
689 arity = get_irn_arity(n);
690 for (i = get_start_index(n); i < arity; i++) {
691 ir_node *pred = get_irn_n(n, i);
693 if (is_backedge(n, i)) { continue; }
694 if (!irn_is_in_stack(pred)) {
695 some_outof_loop = 1; //printf(" some out of loop ");
697 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
698 DDMN(pred); DDMN(root);
699 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
705 return !some_outof_loop && some_in_loop;
708 /* Returns index of the predecessor with the smallest dfn number
709 greater-equal than limit. */
711 smallest_dfn_pred (ir_node *n, int limit)
713 int i, index = -2, min = -1;
715 if (!is_outermost_Start(n)) {
716 int arity = get_irn_arity(n);
717 for (i = get_start_index(n); i < arity; i++) {
718 ir_node *pred = get_irn_n(n, i);
720 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
721 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
723 min = get_irn_dfn(pred);
730 /* Returns index of the predecessor with the largest dfn number. */
732 largest_dfn_pred (ir_node *n)
734 int i, index = -2, max = -1;
736 if (!is_outermost_Start(n)) {
737 int arity = get_irn_arity(n);
738 for (i = get_start_index(n); i < arity; i++) {
739 ir_node *pred = get_irn_n(n, i);
740 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
741 if (get_irn_dfn(pred) > max) {
743 max = get_irn_dfn(pred);
750 /** Searches the stack for possible loop heads. Tests these for backedges.
751 If it finds a head with an unmarked backedge it marks this edge and
752 returns the tail of the loop.
753 If it finds no backedge returns NULL.
754 ("disable_backedge" in fiasco)
756 * @param n A node where uplink == dfn.
760 find_tail (ir_node *n) {
762 int i, res_index = -2;
765 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
767 m = stack[tos-1]; /* tos = top of stack */
768 if (is_head (m, n)) {
769 res_index = smallest_dfn_pred(m, 0);
770 if ((res_index == -2) && /* no smallest dfn pred found. */
774 if (m == n) return NULL; // Is this to catch Phi - self loops?
775 for (i = tos-2; i >= 0; --i) {
778 if (is_head (m, n)) {
779 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
780 if (res_index == -2) /* no smallest dfn pred found. */
781 res_index = largest_dfn_pred (m);
783 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
789 /* We should not walk past our selves on the stack: The upcoming nodes
790 are not in this loop. We assume a loop not reachable from Start. */
799 /* A dead loop not reachable from Start. */
800 for (i = tos-2; i >= 0; --i) {
802 if (is_endless_head (m, n)) {
803 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
804 if (res_index == -2) /* no smallest dfn pred found. */
805 res_index = largest_dfn_pred (m);
808 if (m == n) { break; } /* It's not an unreachable loop, either. */
810 //assert(0 && "no head found on stack");
814 if (res_index <= -2) {
815 /* It's a completely bad loop: without Phi/Block nodes that can
816 be a head. I.e., the code is "dying". We break the loop by
817 setting Bad nodes. */
818 int arity = get_irn_arity(n);
819 for (i = -1; i < arity; ++i) {
820 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
824 assert (res_index > -2);
826 set_backedge (m, res_index);
827 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
831 #if EXPERIMENTAL_LOOP_TREE
833 /* ----------------------------------------------------------------
834 AS: This is experimental code to build loop trees suitable for
835 the heap analysis. Does not work correctly right now... :-(
838 Search in stack for the corresponding first Call-End-ProjX that
839 corresponds to one of the control flow predecessors of the given
840 block, that is the possible callers.
841 returns: the control predecessor to chose\
842 or -1 if no corresponding Call-End-Node could be found
844 - -------------------------------------------------------------- */
846 int search_endproj_in_stack(ir_node *start_block)
849 assert(is_Block(start_block));
850 for(i = tos - 1; i >= 0; --i)
853 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
854 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
856 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
857 ir_node *end_projx = stack[i];
859 int arity = get_irn_arity(start_block);
860 for(j = 0; j < arity; j++)
862 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
863 get_Proj_proj(end_projx));
865 if(get_irn_n(start_block, j) == begin_projx)
867 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
877 static pmap *projx_link = NULL;
879 void link_to_reg_end (ir_node *n, void *env) {
880 if(get_irn_op(n) == op_Proj &&
881 get_irn_mode(n) == mode_X &&
882 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
883 /* Reg End Projx -> Find the CallBegin Projx and hash it */
884 ir_node *end_projx = n;
885 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
886 get_Proj_proj(end_projx));
887 printf("Linked the following ProjxNodes:\n");
890 set_projx_link(begin_projx, end_projx);
894 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
896 if(projx_link == NULL)
897 projx_link = pmap_create();
898 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
901 ir_node *get_projx_link(ir_node *cb_projx)
903 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
909 is_outermost_loop(ir_loop *l) {
910 return l == get_loop_outer_loop(l);
914 /*-----------------------------------------------------------*
915 * The core algorithm. *
916 *-----------------------------------------------------------*/
918 static void scc (ir_node *n) {
920 if (irn_visited(n)) return;
923 /* Initialize the node */
924 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
925 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
926 set_irn_loop(n, NULL);
930 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
931 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
932 so is_backedge does not access array[-1] but correctly returns false! */
934 if (!is_outermost_Start(n)) {
935 int arity = get_irn_arity(n);
937 for (i = get_start_index(n); i < arity; i++) {
939 if (is_backedge(n, i)) continue;
940 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
941 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
943 if (irn_is_in_stack(m)) {
944 /* Uplink of m is smaller if n->m is a backedge.
945 Propagate the uplink to mark the loop. */
946 if (get_irn_uplink(m) < get_irn_uplink(n))
947 set_irn_uplink(n, get_irn_uplink(m));
952 if (get_irn_dfn(n) == get_irn_uplink(n)) {
953 /* This condition holds for
954 1) the node with the incoming backedge.
955 That is: We found a loop!
956 2) Straight line code, because no uplink has been propagated, so the
957 uplink still is the same as the dfn.
959 But n might not be a proper loop head for the analysis. Proper loop
960 heads are Block and Phi nodes. find_tail searches the stack for
961 Block's and Phi's and takes those nodes as loop heads for the current
962 loop instead and marks the incoming edge as backedge. */
964 ir_node *tail = find_tail(n);
966 /* We have a loop, that is no straight line code,
967 because we found a loop head!
968 Next actions: Open a new loop on the loop tree and
969 try to find inner loops */
971 #if NO_LOOPS_WITHOUT_HEAD
972 /* This is an adaption of the algorithm from fiasco / optscc to
973 * avoid loops without Block or Phi as first node. This should
974 * severely reduce the number of evaluations of nodes to detect
975 * a fixpoint in the heap analysis.
976 * Further it avoids loops without firm nodes that cause errors
977 * in the heap analyses.
978 * But attention: don't do it for the outermost loop: This loop
979 * is not iterated. A first block can be a loop head in case of
980 * an endless recursion. */
984 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
992 ir_loop *l = new_loop();
995 /* Remove the loop from the stack ... */
996 pop_scc_unmark_visit (n);
998 /* The current backedge has been marked, that is temporarily eliminated,
999 by find tail. Start the scc algorithm
1000 anew on the subgraph that is left (the current loop without the backedge)
1001 in order to find more inner loops. */
1004 assert (irn_visited(n));
1005 #if NO_LOOPS_WITHOUT_HEAD
1012 /* No loop head was found, that is we have straightline code.
1013 Pop all nodes from the stack to the current loop. */
1019 static void my_scc (ir_node *n) {
1021 if (irn_visited(n)) return;
1022 mark_irn_visited(n);
1024 /* Initialize the node */
1025 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1026 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1027 set_irn_loop(n, NULL);
1031 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1032 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1033 so is_backedge does not access array[-1] but correctly returns false! */
1035 if (!is_outermost_Start(n)) {
1036 int arity = get_irn_arity(n);
1038 for (i = get_start_index(n); i < arity; i++) {
1040 if (is_backedge(n, i)) continue;
1041 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1042 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1044 if (irn_is_in_stack(m)) {
1045 /* Uplink of m is smaller if n->m is a backedge.
1046 Propagate the uplink to mark the loop. */
1047 if (get_irn_uplink(m) < get_irn_uplink(n))
1048 set_irn_uplink(n, get_irn_uplink(m));
1053 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1054 /* This condition holds for
1055 1) the node with the incoming backedge.
1056 That is: We found a loop!
1057 2) Straight line code, because no uplink has been propagated, so the
1058 uplink still is the same as the dfn.
1060 But n might not be a proper loop head for the analysis. Proper loop
1061 heads are Block and Phi nodes. find_tail searches the stack for
1062 Block's and Phi's and takes those nodes as loop heads for the current
1063 loop instead and marks the incoming edge as backedge. */
1065 ir_node *tail = find_tail(n);
1067 /* We have a loop, that is no straight line code,
1068 because we found a loop head!
1069 Next actions: Open a new loop on the loop tree and
1070 try to find inner loops */
1072 #if NO_LOOPS_WITHOUT_HEAD
1073 /* This is an adaption of the algorithm from fiasco / optscc to
1074 * avoid loops without Block or Phi as first node. This should
1075 * severely reduce the number of evaluations of nodes to detect
1076 * a fixpoint in the heap analysis.
1077 * Further it avoids loops without firm nodes that cause errors
1078 * in the heap analyses. */
1082 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1090 ir_loop *l = new_loop();
1093 /* Remove the loop from the stack ... */
1094 pop_scc_unmark_visit (n);
1096 /* The current backedge has been marked, that is temporarily eliminated,
1097 by find tail. Start the scc algorithm
1098 anew on the subgraph that is left (the current loop without the backedge)
1099 in order to find more inner loops. */
1102 assert (irn_visited(n));
1103 #if NO_LOOPS_WITHOUT_HEAD
1110 /* No loop head was found, that is we have straightline code.
1111 Pop all nodes from the stack to the current loop. */
1117 /* Constructs backedge information for irg. In interprocedural view constructs
1118 backedges for all methods called by irg, too. */
1119 int construct_backedges(ir_graph *irg) {
1120 ir_graph *rem = current_ir_graph;
1123 assert(!get_interprocedural_view() &&
1124 "not implemented, use construct_ip_backedges");
1127 current_ir_graph = irg;
1128 outermost_ir_graph = irg;
1130 init_scc(current_ir_graph);
1132 current_loop = NULL;
1133 new_loop(); /* sets current_loop */
1134 head_rem = current_loop; /* Just for assertion */
1136 inc_irg_visited(current_ir_graph);
1138 scc(get_irg_end(current_ir_graph));
1140 assert(head_rem == current_loop);
1141 set_irg_loop(current_ir_graph, current_loop);
1142 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1143 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1145 irg->loops = current_loop;
1149 count_loop (the_loop, &count, &depth);
1153 current_ir_graph = rem;
1155 return max_loop_depth;
1159 int construct_ip_backedges (void) {
1160 ir_graph *rem = current_ir_graph;
1161 int rem_ipv = get_interprocedural_view();
1165 assert(get_irp_ip_view_state() == ip_view_valid);
1167 outermost_ir_graph = get_irp_main_irg();
1171 current_loop = NULL;
1172 new_loop(); /* sets current_loop */
1173 set_interprocedural_view(1);
1175 inc_max_irg_visited();
1176 for (i = 0; i < get_irp_n_irgs(); i++)
1177 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1179 /** We have to start the walk at the same nodes as cg_walk. **/
1180 /* Walk starting at unreachable procedures. Only these
1181 * have End blocks visible in interprocedural view. */
1182 for (i = 0; i < get_irp_n_irgs(); i++) {
1184 current_ir_graph = get_irp_irg(i);
1186 sb = get_irg_start_block(current_ir_graph);
1188 if ((get_Block_n_cfgpreds(sb) > 1) ||
1189 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1191 scc(get_irg_end(current_ir_graph));
1194 /* Check whether we walked all procedures: there could be procedures
1195 with cyclic calls but no call from the outside. */
1196 for (i = 0; i < get_irp_n_irgs(); i++) {
1198 current_ir_graph = get_irp_irg(i);
1200 /* Test start block: if inner procedure end and end block are not
1201 * visible and therefore not marked. */
1202 sb = get_irg_start_block(current_ir_graph);
1203 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1206 /* Walk all endless loops in inner procedures.
1207 * We recognize an inner procedure if the End node is not visited. */
1208 for (i = 0; i < get_irp_n_irgs(); i++) {
1210 current_ir_graph = get_irp_irg(i);
1212 e = get_irg_end(current_ir_graph);
1213 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1215 /* Don't visit the End node. */
1216 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1220 set_irg_loop(outermost_ir_graph, current_loop);
1221 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1222 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1224 current_ir_graph = rem;
1225 set_interprocedural_view(rem_ipv);
1226 return max_loop_depth;
1229 void my_construct_ip_backedges (void) {
1230 ir_graph *rem = current_ir_graph;
1231 int rem_ipv = get_interprocedural_view();
1234 assert(get_irp_ip_view_state() == ip_view_valid);
1236 outermost_ir_graph = get_irp_main_irg();
1240 current_loop = NULL;
1241 new_loop(); /* sets current_loop */
1242 set_interprocedural_view(1);
1244 inc_max_irg_visited();
1245 for (i = 0; i < get_irp_n_irgs(); i++)
1246 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1248 /** We have to start the walk at the same nodes as cg_walk. **/
1249 /* Walk starting at unreachable procedures. Only these
1250 * have End blocks visible in interprocedural view. */
1251 for (i = 0; i < get_irp_n_irgs(); i++) {
1253 current_ir_graph = get_irp_irg(i);
1255 sb = get_irg_start_block(current_ir_graph);
1257 if ((get_Block_n_cfgpreds(sb) > 1) ||
1258 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1260 my_scc(get_irg_end(current_ir_graph));
1263 /* Check whether we walked all procedures: there could be procedures
1264 with cyclic calls but no call from the outside. */
1265 for (i = 0; i < get_irp_n_irgs(); i++) {
1267 current_ir_graph = get_irp_irg(i);
1269 /* Test start block: if inner procedure end and end block are not
1270 * visible and therefore not marked. */
1271 sb = get_irg_start_block(current_ir_graph);
1272 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1275 /* Walk all endless loops in inner procedures.
1276 * We recognize an inner procedure if the End node is not visited. */
1277 for (i = 0; i < get_irp_n_irgs(); i++) {
1279 current_ir_graph = get_irp_irg(i);
1281 e = get_irg_end(current_ir_graph);
1282 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1284 /* Don't visit the End node. */
1285 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1289 set_irg_loop(outermost_ir_graph, current_loop);
1290 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1291 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1293 current_ir_graph = rem;
1294 set_interprocedural_view(rem_ipv);
1297 static void reset_backedges(ir_node *n) {
1298 if (is_possible_loop_head(n)) {
1299 int rem = get_interprocedural_view();
1301 set_interprocedural_view(1);
1303 set_interprocedural_view(1);
1305 set_interprocedural_view(rem);
1311 static void loop_reset_backedges(ir_loop *l) {
1313 reset_backedges(get_loop_node(l, 0));
1314 for (i = 0; i < get_loop_n_nodes(l); ++i)
1315 set_irn_loop(get_loop_node(l, i), NULL);
1316 for (i = 0; i < get_loop_n_sons(l); ++i) {
1317 loop_reset_backedges(get_loop_son(l, i));
1322 static void loop_reset_node(ir_node *n, void *env) {
1323 set_irn_loop(n, NULL);
1328 /** Removes all loop information.
1329 Resets all backedges */
1330 void free_loop_information(ir_graph *irg) {
1331 /* We can not use this recursion, as the loop might contain
1332 illegal nodes by now. Why else would we throw away the
1334 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1336 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1337 set_irg_loop(irg, NULL);
1338 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1339 /* We cannot free the loop nodes, they are on the obstack. */
1343 void free_all_loop_information (void) {
1345 int rem = get_interprocedural_view();
1346 set_interprocedural_view(1); /* To visit all filter nodes */
1347 for (i = 0; i < get_irp_n_irgs(); i++) {
1348 free_loop_information(get_irp_irg(i));
1350 set_interprocedural_view(rem);
1357 /* Debug stuff *************************************************/
1359 static int test_loop_node(ir_loop *l) {
1360 int i, has_node = 0, found_problem = 0;
1363 assert(l && l->kind == k_ir_loop);
1365 if (get_loop_n_elements(l) == 0) {
1366 printf(" Loop completely empty! "); DDML(l);
1368 dump_loop(l, "-ha");
1371 le = get_loop_element(l, 0);
1372 if (*(le.kind) != k_ir_node) {
1373 assert(le.kind && *(le.kind) == k_ir_loop);
1374 printf(" First loop element is not a node! "); DDML(l);
1375 printf(" "); DDML(le.son);
1378 dump_loop(l, "-ha");
1381 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1382 printf(" Wrong node as head! "); DDML(l);
1383 printf(" "); DDMN(le.node);
1385 dump_loop(l, "-ha");
1388 if ((get_loop_depth(l) != 0) &&
1389 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1390 printf(" Loop head has no backedges! "); DDML(l);
1391 printf(" "); DDMN(le.node);
1393 dump_loop(l, "-ha");
1398 for (i = 0; i < get_loop_n_elements(l); ++i) {
1399 le = get_loop_element(l, i);
1400 if (*(le.kind) == k_ir_node)
1403 if (test_loop_node(le.son)) found_problem = 1;
1406 if (has_node == 0) {
1407 printf(" Loop has no firm node! "); DDML(l);
1409 dump_loop(l, "-ha");
1412 return found_problem;
1415 /** Prints all loop nodes that
1416 * - do not have any firm nodes, only loop sons
1417 * - the header is not a Phi, Block or Filter.
1419 void find_strange_loop_nodes(ir_loop *l) {
1420 int found_problem = 0;
1421 printf("\nTesting loop "); DDML(l);
1422 found_problem = test_loop_node(l);
1423 printf("Finished Test\n\n");
1424 if (found_problem) exit(0);
1428 /* ------------------------------------------------------------------- */
1429 /* Simple analyses based on the loop information */
1430 /* ------------------------------------------------------------------- */
1432 int is_loop_variant(ir_loop *l, ir_loop *b) {
1435 if (l == b) return 1;
1437 n_elems = get_loop_n_elements(l);
1438 for (i = 0; i < n_elems; ++i) {
1439 loop_element e = get_loop_element(l, i);
1440 if (is_ir_loop(e.kind))
1441 if (is_loop_variant(e.son, b))
1448 /* Test whether a value is loop invariant.
1450 * @param n The node to be tested.
1451 * @param block A block node. We pass the block, not the loop as we must
1452 * start off with a block loop to find all proper uses.
1454 * Returns non-zero, if the node n is not changed in the loop block
1455 * belongs to or in inner loops of this blocks loop. */
1456 int is_loop_invariant(ir_node *n, ir_node *block) {
1457 ir_loop *l = get_irn_loop(block);
1458 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1459 return !is_loop_variant(l, get_irn_loop(b));