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.
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 bool 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);
95 scc->in_stack = false;
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 */
141 get_irn_loop (ir_node *n) {
147 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
151 /* Test whether n is contained in this loop. */
152 for (i = 0; i < get_loop_n_nodes(l); i++)
153 if (n == get_loop_node(l, i)) return l;
155 /* Is this a leave in the loop tree? If so loop not found. */
156 if (get_loop_n_sons(l) == 0) return NULL;
158 /* Else descend in the loop tree. */
159 for (i = 0; i < get_loop_n_sons(l); i++) {
160 res = find_nodes_loop(n, get_loop_son(l, i));
166 /* @@@ temporary implementation, costly!!! */
167 ir_loop * get_irn_loop(ir_node *n) {
168 ir_loop *l = get_irg_loop(current_ir_graph);
169 l = find_nodes_loop(n, l);
174 /**********************************************************************/
176 /**********************************************************************/
178 static ir_node **stack = NULL;
179 static int tos = 0; /* top of stack */
182 * initializes the stack
184 static INLINE void init_stack(void) {
186 ARR_RESIZE (ir_node *, stack, 1000);
188 stack = NEW_ARR_F (ir_node *, 1000);
194 static INLINE void free_stack(void) {
202 * push a node onto the stack
204 * @param n The node to push
211 if (tos == ARR_LEN (stack)) {
212 int nlen = ARR_LEN (stack) * 2;
213 ARR_RESIZE (ir_node *, stack, nlen);
216 mark_irn_in_stack(n);
220 * pop a node from the stack
222 * @return The topmost node
224 static INLINE ir_node *
227 ir_node *n = stack[--tos];
228 mark_irn_not_in_stack(n);
233 * The nodes up to n belong to the current loop.
234 * Removes them from the stack and adds them to the current loop.
237 pop_scc_to_loop (ir_node *n)
245 //printf(" dfn: %d, upl %d upl-new %d ", get_irn_dfn(m), get_irn_uplink(m), loop_node_cnt+1); DDMN(m);
248 set_irn_dfn(m, loop_node_cnt);
249 add_loop_node(current_loop, m);
250 set_irn_loop(m, current_loop);
253 /* if (m==n) break;*/
256 /* i might be bigger than 1 for dead (and that's why bad) loops */
258 printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
262 /* GL ??? my last son is my grandson??? Removes loops with no
263 ir_nodes in them. Such loops have only another loop as son. (Why
264 can't they have two loops as sons? Does it never get that far? ) */
265 static void close_loop (ir_loop *l)
267 int last = get_loop_n_elements(l) - 1;
268 loop_element lelement = get_loop_element(l, last);
269 ir_loop *last_son = lelement.son;
271 if (get_kind(last_son) == k_ir_loop &&
272 get_loop_n_elements(last_son) == 1) {
275 lelement = get_loop_element(last_son, 0);
278 if (get_kind(gson) == k_ir_loop) {
279 loop_element new_last_son;
281 gson->outer_loop = l;
282 new_last_son.son = gson;
283 l->children[last] = new_last_son;
290 /* Removes and unmarks all nodes up to n from the stack.
291 The nodes must be visited once more to assign them to a scc. */
293 pop_scc_unmark_visit (ir_node *n)
299 set_irn_visited(m, 0);
303 /**********************************************************************/
304 /* The loop datastructure. **/
305 /**********************************************************************/
307 /* Allocates a new loop as son of current_loop. Sets current_loop
308 to the new loop and returns the father. */
309 ir_loop *new_loop (void) {
310 ir_loop *father, *son;
312 father = current_loop;
314 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
315 memset (son, 0, sizeof (ir_loop));
316 son->kind = k_ir_loop;
317 son->children = NEW_ARR_F (loop_element, 0);
321 son->outer_loop = father;
322 add_loop_son(father, son);
323 son->depth = father->depth+1;
324 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
325 } else { /* The root loop */
326 son->outer_loop = son;
331 son->loop_nr = get_irp_new_node_nr();
340 /* Finishes the datastructures, copies the arrays to the obstack
342 A. Schoesser: Caution: loop -> sons is gone. */
343 static void mature_loop (ir_loop *loop) {
346 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
347 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
348 DEL_ARR_F(loop->sons);
349 loop->sons = new_sons;
353 /* Returns outer loop, itself if outermost. */
354 ir_loop *get_loop_outer_loop (ir_loop *loop) {
355 assert(loop && loop->kind == k_ir_loop);
356 return loop->outer_loop;
359 /* Returns nesting depth of this loop */
360 int get_loop_depth (ir_loop *loop) {
361 assert(loop); assert(loop->kind == k_ir_loop);
365 /* Returns the number of inner loops */
366 int get_loop_n_sons (ir_loop *loop) {
367 assert(loop && loop->kind == k_ir_loop);
368 return(loop -> n_sons);
371 /* Returns the pos`th loop_node-child *
372 * TODO: This method isn`t very efficient ! *
373 * Returns NULL if there isn`t a pos`th loop_node */
374 ir_loop *get_loop_son (ir_loop *loop, int pos) {
375 int child_nr = 0, loop_nr = -1;
377 assert(loop && loop->kind == k_ir_loop);
378 while(child_nr < ARR_LEN(loop->children))
380 if(*(loop -> children[child_nr].kind) == k_ir_loop)
383 return(loop -> children[child_nr].son);
389 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
393 add_loop_son(ir_loop *loop, ir_loop *son) {
396 assert(loop && loop->kind == k_ir_loop);
397 assert(get_kind(son) == k_ir_loop);
398 ARR_APP1 (loop_element, loop->children, lson);
402 /* Returns the number of nodes in the loop */
403 int get_loop_n_nodes (ir_loop *loop) {
404 assert(loop); assert(loop->kind == k_ir_loop);
405 return loop -> n_nodes;
406 /* return ARR_LEN(loop->nodes); */
409 /* Returns the pos`th ir_node-child *
410 * TODO: This method isn`t very efficient ! *
411 * Returns NULL if there isn`t a pos`th ir_node */
412 ir_node *get_loop_node (ir_loop *loop, int pos) {
413 int child_nr, node_nr = -1;
415 assert(loop && loop->kind == k_ir_loop);
416 assert(pos < get_loop_n_nodes(loop));
418 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
419 if(*(loop -> children[child_nr].kind) == k_ir_node)
422 return(loop -> children[child_nr].node);
425 printf("pos: %d\n", pos);
426 assert(0 && "no child at pos found");
430 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
434 add_loop_node(ir_loop *loop, ir_node *n) {
437 assert(loop && loop->kind == k_ir_loop);
438 assert(get_kind(n) == k_ir_node || get_kind(n) == k_ir_graph); /* used in callgraph.c */
439 ARR_APP1 (loop_element, loop->children, ln);
443 /** Returns the number of elements contained in loop. */
444 int get_loop_n_elements (ir_loop *loop) {
445 assert(loop && loop->kind == k_ir_loop);
446 return(ARR_LEN(loop->children));
450 Returns the pos`th loop element.
451 This may be a loop_node or a ir_node. The caller of this function has
452 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
453 and then select the appropriate "loop_element.node" or "loop_element.son".
456 loop_element get_loop_element (ir_loop *loop, int pos) {
457 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
459 return(loop -> children[pos]);
462 int get_loop_element_pos(ir_loop *loop, void *le) {
464 assert(loop && loop->kind == k_ir_loop);
466 for (i = 0; i < get_loop_n_elements(loop); i++)
467 if (get_loop_element(loop, i).node == le) return i;
471 int get_loop_loop_nr(ir_loop *loop) {
472 assert(loop && loop->kind == k_ir_loop);
474 return loop->loop_nr;
481 /** A field to connect additional information to a loop. Only valid
482 if libfirm_debug is set. */
483 void set_loop_link (ir_loop *loop, void *link) {
484 assert(loop && loop->kind == k_ir_loop);
489 void *get_loop_link (const ir_loop *loop) {
490 assert(loop && loop->kind == k_ir_loop);
498 int (is_ir_loop)(const void *thing) {
499 return _is_ir_loop(thing);
502 /* The outermost loop is remarked in the surrounding graph. */
503 void (set_irg_loop)(ir_graph *irg, ir_loop *loop) {
504 _set_irg_loop(irg, loop);
507 /* Returns the root loop info (if exists) for an irg. */
508 ir_loop *(get_irg_loop)(ir_graph *irg) {
509 return _get_irg_loop(irg);
513 /**********************************************************************/
514 /* Constructing and destructing the loop/backedge information. **/
515 /**********************************************************************/
517 /* Initialization steps. **********************************************/
520 init_node (ir_node *n, void *env) {
521 set_irn_link (n, new_scc_info());
526 init_scc_common (void) {
533 init_scc (ir_graph *irg) {
535 irg_walk_graph (irg, init_node, NULL, NULL);
537 irg_walk (irg, link_to_reg_end, NULL, NULL);
544 cg_walk (init_node, NULL, NULL);
546 #if EXPERIMENTAL_LOOP_TREE
547 cg_walk (link_to_reg_end, NULL, NULL);
551 /* Condition for breaking the recursion. */
552 static bool is_outermost_Start(ir_node *n) {
553 /* Test whether this is the outermost Start node. If so
554 recursion must end. */
555 if ((get_irn_op(n) == op_Block) &&
556 (get_Block_n_cfgpreds(n) == 1) &&
557 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
558 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
562 /* @@@ Bad condition:
563 not possible in interprocedural view as outermost_graph is
564 not necessarily the only with a dead-end start block.
565 Besides current_ir_graph is not set properly. */
566 if ((get_irn_op(n) == op_Block) &&
567 (n == get_irg_start_block(current_ir_graph))) {
568 if ((!get_interprocedural_view()) ||
569 (current_ir_graph == outermost_ir_graph))
576 /* When to walk from nodes to blocks. Only for Control flow operations? */
578 get_start_index(ir_node *n) {
579 #undef BLOCK_BEFORE_NODE
580 #define BLOCK_BEFORE_NODE 1
582 #if BLOCK_BEFORE_NODE
584 /* This version assures, that all nodes are ordered absolutely. This allows
585 to undef all nodes in the heap analysis if the block is false, which means
587 I.e., with this code, the order on the loop tree is correct. But a (single)
588 test showed the loop tree is deeper. */
589 if (get_irn_op(n) == op_Phi ||
590 get_irn_op(n) == op_Block ||
591 (get_irn_op(n) == op_Filter && get_interprocedural_view()) ||
592 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
593 get_irn_pinned(n) == op_pin_state_floats))
594 // Here we could test for backedge at -1 which is illegal
601 /* This version causes deeper loop trees (at least we verified this
603 But it guarantees that Blocks are analysed before nodes contained in the
604 block. If so, we can set the value to undef if the block is not \
606 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
616 static void test(ir_node *pred, ir_node *root, ir_node *this) {
618 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
620 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
621 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
622 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
624 printf("tos: %d\n", tos);
626 for (i = tos; i >= 0; i--) {
627 ir_node *n = stack[i];
629 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
634 /* Test for legal loop header: Block, Phi, ... */
635 static INLINE bool is_possible_loop_head(ir_node *n) {
636 ir_op *op = get_irn_op(n);
637 return ((op == op_Block) ||
639 ((op == op_Filter) && get_interprocedural_view()));
642 /* Returns true if n is a loop header, i.e., it is a Block, Phi
643 or Filter node and has predecessors within the loop and out
645 @arg root: only needed for assertion. */
647 is_head (ir_node *n, ir_node *root)
650 int some_outof_loop = 0, some_in_loop = 0;
652 /* Test for legal loop header: Block, Phi, ... */
653 if (!is_possible_loop_head(n))
656 if (!is_outermost_Start(n)) {
657 arity = get_irn_arity(n);
658 for (i = get_start_index(n); i < arity; i++) {
659 ir_node *pred = get_irn_n(n, i);
661 if (is_backedge(n, i)) continue;
662 if (!irn_is_in_stack(pred)) {
665 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
666 DDMN(n); DDMN(pred); DDMN(root);
667 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
673 return some_outof_loop && some_in_loop;
676 /* Returns true if n is possible loop head of an endless loop.
677 I.e., it is a Block, Phi or Filter node and has only predecessors
679 @arg root: only needed for assertion. */
681 is_endless_head (ir_node *n, ir_node *root)
684 int some_outof_loop = 0, some_in_loop = 0;
686 /* Test for legal loop header: Block, Phi, ... */
687 if (!is_possible_loop_head(n))
690 if (!is_outermost_Start(n)) {
691 arity = get_irn_arity(n);
692 for (i = get_start_index(n); i < arity; i++) {
693 ir_node *pred = get_irn_n(n, i);
695 if (is_backedge(n, i)) { continue; }
696 if (!irn_is_in_stack(pred)) {
697 some_outof_loop = 1; //printf(" some out of loop ");
699 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
700 DDMN(pred); DDMN(root);
701 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
707 return !some_outof_loop && some_in_loop;
710 /* Returns index of the predecessor with the smallest dfn number
711 greater-equal than limit. */
713 smallest_dfn_pred (ir_node *n, int limit)
715 int i, index = -2, min = -1;
717 if (!is_outermost_Start(n)) {
718 int arity = get_irn_arity(n);
719 for (i = get_start_index(n); i < arity; i++) {
720 ir_node *pred = get_irn_n(n, i);
722 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
723 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
725 min = get_irn_dfn(pred);
732 /* Returns index of the predecessor with the largest dfn number. */
734 largest_dfn_pred (ir_node *n)
736 int i, index = -2, max = -1;
738 if (!is_outermost_Start(n)) {
739 int arity = get_irn_arity(n);
740 for (i = get_start_index(n); i < arity; i++) {
741 ir_node *pred = get_irn_n(n, i);
742 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
743 if (get_irn_dfn(pred) > max) {
745 max = get_irn_dfn(pred);
752 /** Searches the stack for possible loop heads. Tests these for backedges.
753 If it finds a head with an unmarked backedge it marks this edge and
754 returns the tail of the loop.
755 If it finds no backedge returns NULL.
756 ("disable_backedge" in fiasco)
758 * @param n A node where uplink == dfn.
762 find_tail (ir_node *n) {
764 int i, res_index = -2;
767 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
769 m = stack[tos-1]; /* tos = top of stack */
770 if (is_head (m, n)) {
771 res_index = smallest_dfn_pred(m, 0);
772 if ((res_index == -2) && /* no smallest dfn pred found. */
776 if (m == n) return NULL; // Is this to catch Phi - self loops?
777 for (i = tos-2; i >= 0; --i) {
780 if (is_head (m, n)) {
781 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
782 if (res_index == -2) /* no smallest dfn pred found. */
783 res_index = largest_dfn_pred (m);
785 if ((m == n) && (res_index == -2)) { /* dont walk past loop head. */
791 /* We should not walk past our selves on the stack: The upcoming nodes
792 are not in this loop. We assume a loop not reachable from Start. */
801 /* A dead loop not reachable from Start. */
802 for (i = tos-2; i >= 0; --i) {
804 if (is_endless_head (m, n)) {
805 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
806 if (res_index == -2) /* no smallest dfn pred found. */
807 res_index = largest_dfn_pred (m);
810 if (m == n) { break; } /* It's not an unreachable loop, either. */
812 //assert(0 && "no head found on stack");
816 if (res_index <= -2) {
817 /* It's a completely bad loop: without Phi/Block nodes that can
818 be a head. I.e., the code is "dying". We break the loop by
819 setting Bad nodes. */
820 int arity = get_irn_arity(n);
821 for (i = -1; i < arity; ++i) {
822 set_irn_n(n, i, get_irg_bad(get_irn_irg(n)));
826 assert (res_index > -2);
828 set_backedge (m, res_index);
829 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
833 #if EXPERIMENTAL_LOOP_TREE
835 /* ----------------------------------------------------------------
836 AS: This is experimental code to build loop trees suitable for
837 the heap analysis. Does not work correctly right now... :-(
840 Search in stack for the corresponding first Call-End-ProjX that
841 corresponds to one of the control flow predecessors of the given
842 block, that is the possible callers.
843 returns: the control predecessor to chose\
844 or -1 if no corresponding Call-End-Node could be found
846 - -------------------------------------------------------------- */
848 int search_endproj_in_stack(ir_node *start_block)
851 assert(is_Block(start_block));
852 for(i = tos - 1; i >= 0; --i)
855 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
856 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
858 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
859 ir_node *end_projx = stack[i];
861 int arity = get_irn_arity(start_block);
862 for(j = 0; j < arity; j++)
864 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
865 get_Proj_proj(end_projx));
867 if(get_irn_n(start_block, j) == begin_projx)
869 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
879 static pmap *projx_link = NULL;
881 void link_to_reg_end (ir_node *n, void *env) {
882 if(get_irn_op(n) == op_Proj &&
883 get_irn_mode(n) == mode_X &&
884 get_irn_op(get_irn_n(n, 0)) == op_EndReg) {
885 /* Reg End Projx -> Find the CallBegin Projx and hash it */
886 ir_node *end_projx = n;
887 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)),
888 get_Proj_proj(end_projx));
889 printf("Linked the following ProjxNodes:\n");
892 set_projx_link(begin_projx, end_projx);
896 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
898 if(projx_link == NULL)
899 projx_link = pmap_create();
900 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
903 ir_node *get_projx_link(ir_node *cb_projx)
905 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
911 is_outermost_loop(ir_loop *l) {
912 return l == get_loop_outer_loop(l);
916 /*-----------------------------------------------------------*
917 * The core algorithm. *
918 *-----------------------------------------------------------*/
920 static void scc (ir_node *n) {
922 if (irn_visited(n)) return;
925 /* Initialize the node */
926 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
927 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
928 set_irn_loop(n, NULL);
932 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
933 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
934 so is_backedge does not access array[-1] but correctly returns false! */
936 if (!is_outermost_Start(n)) {
937 int arity = get_irn_arity(n);
939 for (i = get_start_index(n); i < arity; i++) {
941 if (is_backedge(n, i)) continue;
942 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
943 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
945 if (irn_is_in_stack(m)) {
946 /* Uplink of m is smaller if n->m is a backedge.
947 Propagate the uplink to mark the loop. */
948 if (get_irn_uplink(m) < get_irn_uplink(n))
949 set_irn_uplink(n, get_irn_uplink(m));
954 if (get_irn_dfn(n) == get_irn_uplink(n)) {
955 /* This condition holds for
956 1) the node with the incoming backedge.
957 That is: We found a loop!
958 2) Straight line code, because no uplink has been propagated, so the
959 uplink still is the same as the dfn.
961 But n might not be a proper loop head for the analysis. Proper loop
962 heads are Block and Phi nodes. find_tail searches the stack for
963 Block's and Phi's and takes those nodes as loop heads for the current
964 loop instead and marks the incoming edge as backedge. */
966 ir_node *tail = find_tail(n);
968 /* We have a loop, that is no straight line code,
969 because we found a loop head!
970 Next actions: Open a new loop on the loop tree and
971 try to find inner loops */
973 #if NO_LOOPS_WITHOUT_HEAD
974 /* This is an adaption of the algorithm from fiasco / optscc to
975 * avoid loops without Block or Phi as first node. This should
976 * severely reduce the number of evaluations of nodes to detect
977 * a fixpoint in the heap analysis.
978 * Further it avoids loops without firm nodes that cause errors
979 * in the heap analyses.
980 * But attention: don't do it for the outermost loop: This loop
981 * is not iterated. A first block can be a loop head in case of
982 * an endless recursion. */
986 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
994 ir_loop *l = new_loop();
997 /* Remove the loop from the stack ... */
998 pop_scc_unmark_visit (n);
1000 /* The current backedge has been marked, that is temporarily eliminated,
1001 by find tail. Start the scc algorithm
1002 anew on the subgraph that is left (the current loop without the backedge)
1003 in order to find more inner loops. */
1006 assert (irn_visited(n));
1007 #if NO_LOOPS_WITHOUT_HEAD
1014 /* No loop head was found, that is we have straightline code.
1015 Pop all nodes from the stack to the current loop. */
1021 static void my_scc (ir_node *n) {
1023 if (irn_visited(n)) return;
1024 mark_irn_visited(n);
1026 /* Initialize the node */
1027 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
1028 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
1029 set_irn_loop(n, NULL);
1033 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
1034 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
1035 so is_backedge does not access array[-1] but correctly returns false! */
1037 if (!is_outermost_Start(n)) {
1038 int arity = get_irn_arity(n);
1040 for (i = get_start_index(n); i < arity; i++) {
1042 if (is_backedge(n, i)) continue;
1043 m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
1044 /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
1046 if (irn_is_in_stack(m)) {
1047 /* Uplink of m is smaller if n->m is a backedge.
1048 Propagate the uplink to mark the loop. */
1049 if (get_irn_uplink(m) < get_irn_uplink(n))
1050 set_irn_uplink(n, get_irn_uplink(m));
1055 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1056 /* This condition holds for
1057 1) the node with the incoming backedge.
1058 That is: We found a loop!
1059 2) Straight line code, because no uplink has been propagated, so the
1060 uplink still is the same as the dfn.
1062 But n might not be a proper loop head for the analysis. Proper loop
1063 heads are Block and Phi nodes. find_tail searches the stack for
1064 Block's and Phi's and takes those nodes as loop heads for the current
1065 loop instead and marks the incoming edge as backedge. */
1067 ir_node *tail = find_tail(n);
1069 /* We have a loop, that is no straight line code,
1070 because we found a loop head!
1071 Next actions: Open a new loop on the loop tree and
1072 try to find inner loops */
1074 #if NO_LOOPS_WITHOUT_HEAD
1075 /* This is an adaption of the algorithm from fiasco / optscc to
1076 * avoid loops without Block or Phi as first node. This should
1077 * severely reduce the number of evaluations of nodes to detect
1078 * a fixpoint in the heap analysis.
1079 * Further it avoids loops without firm nodes that cause errors
1080 * in the heap analyses. */
1084 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
1092 ir_loop *l = new_loop();
1095 /* Remove the loop from the stack ... */
1096 pop_scc_unmark_visit (n);
1098 /* The current backedge has been marked, that is temporarily eliminated,
1099 by find tail. Start the scc algorithm
1100 anew on the subgraph that is left (the current loop without the backedge)
1101 in order to find more inner loops. */
1104 assert (irn_visited(n));
1105 #if NO_LOOPS_WITHOUT_HEAD
1112 /* No loop head was found, that is we have straightline code.
1113 Pop all nodes from the stack to the current loop. */
1119 /* Constructs backedge information for irg. In interprocedural view constructs
1120 backedges for all methods called by irg, too. */
1121 int construct_backedges(ir_graph *irg) {
1122 ir_graph *rem = current_ir_graph;
1125 assert(!get_interprocedural_view() &&
1126 "not implemented, use construct_ip_backedges");
1129 current_ir_graph = irg;
1130 outermost_ir_graph = irg;
1132 init_scc(current_ir_graph);
1134 current_loop = NULL;
1135 new_loop(); /* sets current_loop */
1136 head_rem = current_loop; /* Just for assertion */
1138 inc_irg_visited(current_ir_graph);
1140 scc(get_irg_end(current_ir_graph));
1142 assert(head_rem == current_loop);
1143 set_irg_loop(current_ir_graph, current_loop);
1144 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1145 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1147 irg->loops = current_loop;
1151 count_loop (the_loop, &count, &depth);
1155 current_ir_graph = rem;
1157 return max_loop_depth;
1161 int construct_ip_backedges (void) {
1162 ir_graph *rem = current_ir_graph;
1163 int rem_ipv = get_interprocedural_view();
1167 assert(get_irp_ip_view_state() == ip_view_valid);
1169 outermost_ir_graph = get_irp_main_irg();
1173 current_loop = NULL;
1174 new_loop(); /* sets current_loop */
1175 set_interprocedural_view(true);
1177 inc_max_irg_visited();
1178 for (i = 0; i < get_irp_n_irgs(); i++)
1179 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1181 /** We have to start the walk at the same nodes as cg_walk. **/
1182 /* Walk starting at unreachable procedures. Only these
1183 * have End blocks visible in interprocedural view. */
1184 for (i = 0; i < get_irp_n_irgs(); i++) {
1186 current_ir_graph = get_irp_irg(i);
1188 sb = get_irg_start_block(current_ir_graph);
1190 if ((get_Block_n_cfgpreds(sb) > 1) ||
1191 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1193 scc(get_irg_end(current_ir_graph));
1196 /* Check whether we walked all procedures: there could be procedures
1197 with cyclic calls but no call from the outside. */
1198 for (i = 0; i < get_irp_n_irgs(); i++) {
1200 current_ir_graph = get_irp_irg(i);
1202 /* Test start block: if inner procedure end and end block are not
1203 * visible and therefore not marked. */
1204 sb = get_irg_start_block(current_ir_graph);
1205 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1208 /* Walk all endless loops in inner procedures.
1209 * We recognize an inner procedure if the End node is not visited. */
1210 for (i = 0; i < get_irp_n_irgs(); i++) {
1212 current_ir_graph = get_irp_irg(i);
1214 e = get_irg_end(current_ir_graph);
1215 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1217 /* Don't visit the End node. */
1218 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1222 set_irg_loop(outermost_ir_graph, current_loop);
1223 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1224 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1226 current_ir_graph = rem;
1227 set_interprocedural_view(rem_ipv);
1228 return max_loop_depth;
1231 void my_construct_ip_backedges (void) {
1232 ir_graph *rem = current_ir_graph;
1233 int rem_ipv = get_interprocedural_view();
1236 assert(get_irp_ip_view_state() == ip_view_valid);
1238 outermost_ir_graph = get_irp_main_irg();
1242 current_loop = NULL;
1243 new_loop(); /* sets current_loop */
1244 set_interprocedural_view(true);
1246 inc_max_irg_visited();
1247 for (i = 0; i < get_irp_n_irgs(); i++)
1248 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1250 /** We have to start the walk at the same nodes as cg_walk. **/
1251 /* Walk starting at unreachable procedures. Only these
1252 * have End blocks visible in interprocedural view. */
1253 for (i = 0; i < get_irp_n_irgs(); i++) {
1255 current_ir_graph = get_irp_irg(i);
1257 sb = get_irg_start_block(current_ir_graph);
1259 if ((get_Block_n_cfgpreds(sb) > 1) ||
1260 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1262 my_scc(get_irg_end(current_ir_graph));
1265 /* Check whether we walked all procedures: there could be procedures
1266 with cyclic calls but no call from the outside. */
1267 for (i = 0; i < get_irp_n_irgs(); i++) {
1269 current_ir_graph = get_irp_irg(i);
1271 /* Test start block: if inner procedure end and end block are not
1272 * visible and therefore not marked. */
1273 sb = get_irg_start_block(current_ir_graph);
1274 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1277 /* Walk all endless loops in inner procedures.
1278 * We recognize an inner procedure if the End node is not visited. */
1279 for (i = 0; i < get_irp_n_irgs(); i++) {
1281 current_ir_graph = get_irp_irg(i);
1283 e = get_irg_end(current_ir_graph);
1284 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1286 /* Don't visit the End node. */
1287 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1291 set_irg_loop(outermost_ir_graph, current_loop);
1292 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1293 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1295 current_ir_graph = rem;
1296 set_interprocedural_view(rem_ipv);
1299 static void reset_backedges(ir_node *n) {
1300 if (is_possible_loop_head(n)) {
1301 int rem = get_interprocedural_view();
1303 set_interprocedural_view(true);
1305 set_interprocedural_view(true);
1307 set_interprocedural_view(rem);
1313 static void loop_reset_backedges(ir_loop *l) {
1315 reset_backedges(get_loop_node(l, 0));
1316 for (i = 0; i < get_loop_n_nodes(l); ++i)
1317 set_irn_loop(get_loop_node(l, i), NULL);
1318 for (i = 0; i < get_loop_n_sons(l); ++i) {
1319 loop_reset_backedges(get_loop_son(l, i));
1324 static void loop_reset_node(ir_node *n, void *env) {
1325 set_irn_loop(n, NULL);
1330 /** Removes all loop information.
1331 Resets all backedges */
1332 void free_loop_information(ir_graph *irg) {
1333 /* We can not use this recursion, as the loop might contain
1334 illegal nodes by now. Why else would we throw away the
1336 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
1338 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
1339 set_irg_loop(irg, NULL);
1340 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1341 /* We cannot free the loop nodes, they are on the obstack. */
1345 void free_all_loop_information (void) {
1347 int rem = get_interprocedural_view();
1348 set_interprocedural_view(true); /* To visit all filter nodes */
1349 for (i = 0; i < get_irp_n_irgs(); i++) {
1350 free_loop_information(get_irp_irg(i));
1352 set_interprocedural_view(rem);
1359 /* Debug stuff *************************************************/
1361 static int test_loop_node(ir_loop *l) {
1362 int i, has_node = 0, found_problem = 0;
1365 assert(l && l->kind == k_ir_loop);
1367 if (get_loop_n_elements(l) == 0) {
1368 printf(" Loop completely empty! "); DDML(l);
1370 dump_loop(l, "-ha");
1373 le = get_loop_element(l, 0);
1374 if (*(le.kind) != k_ir_node) {
1375 assert(le.kind && *(le.kind) == k_ir_loop);
1376 printf(" First loop element is not a node! "); DDML(l);
1377 printf(" "); DDML(le.son);
1380 dump_loop(l, "-ha");
1383 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1384 printf(" Wrong node as head! "); DDML(l);
1385 printf(" "); DDMN(le.node);
1387 dump_loop(l, "-ha");
1390 if ((get_loop_depth(l) != 0) &&
1391 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1392 printf(" Loop head has no backedges! "); DDML(l);
1393 printf(" "); DDMN(le.node);
1395 dump_loop(l, "-ha");
1400 for (i = 0; i < get_loop_n_elements(l); ++i) {
1401 le = get_loop_element(l, i);
1402 if (*(le.kind) == k_ir_node)
1405 if (test_loop_node(le.son)) found_problem = 1;
1408 if (has_node == 0) {
1409 printf(" Loop has no firm node! "); DDML(l);
1411 dump_loop(l, "-ha");
1414 return found_problem;
1417 /** Prints all loop nodes that
1418 * - do not have any firm nodes, only loop sons
1419 * - the header is not a Phi, Block or Filter.
1421 void find_strange_loop_nodes(ir_loop *l) {
1422 int found_problem = 0;
1423 printf("\nTesting loop "); DDML(l);
1424 found_problem = test_loop_node(l);
1425 printf("Finished Test\n\n");
1426 if (found_problem) exit(0);
1430 /* ------------------------------------------------------------------- */
1431 /* Simple analyses based on the loop information */
1432 /* ------------------------------------------------------------------- */
1434 int is_loop_variant(ir_loop *l, ir_loop *b) {
1437 if (l == b) return true;
1439 n_elems = get_loop_n_elements(l);
1440 for (i = 0; i < n_elems; ++i) {
1441 loop_element e = get_loop_element(l, i);
1442 if (is_ir_loop(e.kind))
1443 if (is_loop_variant(e.son, b))
1450 /* Test whether a value is loop invariant.
1452 * @param n The node to be tested.
1453 * @param block A block node. We pass the block, not the loop as we must
1454 * start off with a block loop to find all proper uses.
1456 * Returns true, if the node n is not changed in the loop block
1457 * belongs to or in inner loops of this blocks loop. */
1458 int is_loop_invariant(ir_node *n, ir_node *block) {
1459 ir_loop *l = get_irn_loop(block);
1460 ir_node *b = (is_Block(n)) ? n : get_nodes_block(n);
1461 return !is_loop_variant(l, get_irn_loop(b));