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.
24 #include "irgraph_t.h"
31 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
33 static ir_loop *current_loop; /* Current loop construction is working
35 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
36 Each loop node gets a unique number.
37 What for? ev. remove. @@@ */
38 static int current_dfn = 1; /* Counter to generate depth first numbering
41 void link_to_reg_end (ir_node *n, void *env);
42 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
43 ir_node *get_projx_link(ir_node *cb_projx);
45 /**********************************************************************/
46 /* Node attributes **/
47 /**********************************************************************/
49 /* A map to get from irnodes to loop nodes. */
50 static pmap *node_loop_map = NULL;
52 /**********************************************************************/
53 /* Node attributes needed for the construction. **/
54 /**********************************************************************/
56 typedef struct scc_info {
57 bool in_stack; /* Marks whether node is on the stack. */
58 int dfn; /* Depth first search number. */
59 int uplink; /* dfn number of ancestor. */
60 /* ir_loop *loop; *//* Refers to the containing loop. */
62 struct section *section;
68 static INLINE scc_info* new_scc_info(void) {
69 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
70 memset (info, 0, sizeof (scc_info));
75 mark_irn_in_stack (ir_node *n) {
76 assert(get_irn_link(n));
78 /* ((scc_info *)get_irn_link(n))->in_stack = true; */
79 ((scc_info *)n->link)->in_stack = true;
83 mark_irn_not_in_stack (ir_node *n) {
84 assert(get_irn_link(n));
86 /* ((scc_info *)get_irn_link(n))->in_stack = false; */
87 ((scc_info *)n->link)->in_stack = false;
91 irn_is_in_stack (ir_node *n) {
92 assert(get_irn_link(n));
94 /* return ((scc_info *)get_irn_link(n))->in_stack; */
95 return ((scc_info *)n->link)->in_stack;
99 set_irn_uplink (ir_node *n, int uplink) {
100 assert(get_irn_link(n));
102 /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
103 ((scc_info *)n->link)->uplink = uplink;
107 get_irn_uplink (ir_node *n) {
108 assert(get_irn_link(n));
109 /* from fast to slow */
110 /* return ((scc_info *)get_irn_link(n))->uplink; */
111 return ((scc_info *)n->link)->uplink;
115 set_irn_dfn (ir_node *n, int dfn) {
116 assert(get_irn_link(n));
118 /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
119 ((scc_info *)n->link)->dfn = dfn;
123 get_irn_dfn (ir_node *n) {
124 assert(get_irn_link(n));
126 /* return ((scc_info *)get_irn_link(n))->dfn; */
127 return ((scc_info *)n->link)->dfn;
131 /* Replaced node loop map by real field as hash access dominates runtime
132 * of the algorithm. ! */
133 /* Uses temporary information to set the loop */
135 set_irn_loop (ir_node *n, ir_loop* loop) {
136 assert(node_loop_map && "not initialized!");
137 pmap_insert(node_loop_map, (void *)n, (void *)loop);
140 /* Uses temporary information to get the loop */
142 get_irn_loop (ir_node *n) {
144 if (!node_loop_map) return NULL;
146 if (pmap_contains(node_loop_map, (void *)n))
147 res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
153 set_irn_loop (ir_node *n, ir_loop* loop) {
157 /* Uses temporary information to get the loop */
159 get_irn_loop (ir_node *n) {
166 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
170 /* Test whether n is contained in this loop. */
171 for (i = 0; i < get_loop_n_nodes(l); i++)
172 if (n == get_loop_node(l, i)) return l;
174 /* Is this a leave in the loop tree? If so loop not found. */
175 if (get_loop_n_sons(l) == 0) return NULL;
177 /* Else descend in the loop tree. */
178 for (i = 0; i < get_loop_n_sons(l); i++) {
179 res = find_nodes_loop(n, get_loop_son(l, i));
185 /* @@@ temporary implementation, costly!!! */
186 ir_loop * get_irn_loop(ir_node *n) {
187 ir_loop *l = get_irg_loop(current_ir_graph);
188 l = find_nodes_loop(n, l);
193 /**********************************************************************/
195 /**********************************************************************/
197 static ir_node **stack = NULL;
198 static int tos = 0; /* top of stack */
200 static INLINE void init_stack(void) {
202 ARR_RESIZE (ir_node *, stack, 1000);
204 stack = NEW_ARR_F (ir_node *, 1000);
210 static INLINE void free_stack(void) {
222 if (tos == ARR_LEN (stack)) {
223 int nlen = ARR_LEN (stack) * 2;
224 ARR_RESIZE (ir_node *, stack, nlen);
227 mark_irn_in_stack(n);
230 static INLINE ir_node *
233 ir_node *n = stack[--tos];
234 mark_irn_not_in_stack(n);
238 /* The nodes up to n belong to the current loop.
239 Removes them from the stack and adds them to the current loop. */
241 pop_scc_to_loop (ir_node *n)
251 set_irn_dfn(m, loop_node_cnt);
252 add_loop_node(current_loop, m);
253 set_irn_loop(m, current_loop);
255 /* if (m==n) break;*/
259 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 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)
276 lelement = get_loop_element(last_son, 0);
278 if(get_kind(gson) == k_ir_loop)
280 loop_element new_last_son;
282 gson -> outer_loop = l;
283 new_last_son.son = gson;
284 l -> children[last] = new_last_son;
291 /* Removes and unmarks all nodes up to n from the stack.
292 The nodes must be visited once more to assign them to a scc. */
294 pop_scc_unmark_visit (ir_node *n)
300 set_irn_visited(m, 0);
304 /**********************************************************************/
305 /* The loop datastructure. **/
306 /**********************************************************************/
308 /* Allocates a new loop as son of current_loop. Sets current_loop
309 to the new loop and returns the father. */
310 static ir_loop *new_loop (void) {
311 ir_loop *father, *son;
313 father = current_loop;
315 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
316 memset (son, 0, sizeof (ir_loop));
317 son->kind = k_ir_loop;
318 son->children = NEW_ARR_F (loop_element, 0);
322 son->outer_loop = father;
323 add_loop_son(father, son);
324 son->depth = father->depth+1;
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 isnt`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 isnt`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);
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 apropriate "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 /* The outermost loop is remarked in the surrounding graph. */
499 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
503 ir_loop *get_irg_loop(ir_graph *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());
520 /* Also init nodes not visible in intraproc_view. */
521 /* @@@ init_node is called for too many nodes -- this wastes memory!.
522 The mem is not lost as its on the obstack. */
523 if (intern_get_irn_op(n) == op_Filter) {
524 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
525 init_node(get_Filter_cg_pred(n, i), NULL);
527 if (intern_get_irn_op(n) == op_Block) {
528 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
529 init_node(get_Block_cg_cfgpred(n, i), NULL);
532 /* The following pattern matches only after a call from above pattern. */
533 if ((intern_get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
534 /* @@@ init_node is called for every proj -- this wastes memory!.
535 The mem is not lost as its on the obstack. */
536 ir_node *cb = get_Proj_pred(n);
537 if ((intern_get_irn_op(cb) == op_CallBegin) ||
538 (intern_get_irn_op(cb) == op_EndReg) ||
539 (intern_get_irn_op(cb) == op_EndExcept)) {
541 init_node(get_nodes_Block(cb), NULL);
548 init_scc_common (void) {
551 if (!node_loop_map) node_loop_map = pmap_create();
556 init_scc (ir_graph *irg) {
558 irg_walk_graph (irg, init_node, NULL, NULL);
560 irg_walk (irg, link_to_reg_end, NULL, NULL);
567 cg_walk (init_node, NULL, NULL);
569 #if EXPERIMENTAL_LOOP_TREE
570 cg_walk (link_to_reg_end, NULL, NULL);
574 /* Condition for breaking the recursion. */
575 static bool is_outermost_Start(ir_node *n) {
576 /* Test whether this is the outermost Start node. If so
577 recursion must end. */
578 if ((intern_get_irn_op(n) == op_Block) &&
579 (get_Block_n_cfgpreds(n) == 1) &&
580 (intern_get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
581 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
585 /* @@@ Bad condition:
586 not possible in interprocedural view as outermost_graph is
587 not necessarily the only with a dead-end start block.
588 Besides current_ir_graph is not set properly. */
589 if ((intern_get_irn_op(n) == op_Block) &&
590 (n == get_irg_start_block(current_ir_graph))) {
591 if ((!interprocedural_view) ||
592 (current_ir_graph == outermost_ir_graph))
599 /* When to walk from nodes to blocks. Only for Control flow operations? */
601 get_start_index(ir_node *n) {
602 #undef BLOCK_BEFORE_NODE
603 #define BLOCK_BEFORE_NODE 1
605 #if BLOCK_BEFORE_NODE
607 /* This version assures, that all nodes are ordered absolutely. This allows
608 to undef all nodes in the heap analysis if the block is false, which means
610 I.e., with this code, the order on the loop tree is correct. But a (single)
611 test showed the loop tree is deeper. */
612 if (intern_get_irn_op(n) == op_Phi ||
613 intern_get_irn_op(n) == op_Block ||
614 (intern_get_irn_op(n) == op_Filter && interprocedural_view) ||
615 (get_irg_pinned(get_irn_irg(n)) == floats &&
616 get_op_pinned(get_irn_op(n)) == floats))
617 // Here we could test for backedge at -1 which is illegal
624 /* This version causes deeper loop trees (at least we verified this
626 But it guarantees that Blocks are analysed before nodes contained in the
627 block. If so, we can set the value to undef if the block is not \
629 if (is_cfop(n) || is_fragile_op(n) || intern_get_irn_op(n) == op_Start)
639 /* Returns current_ir_graph and set it to the irg of predecessor index
641 static INLINE ir_graph *
642 switch_irg (ir_node *n, int index) {
643 ir_graph *old_current = current_ir_graph;
645 if (interprocedural_view) {
646 /* Only Filter and Block nodes can have predecessors in other graphs. */
647 if (intern_get_irn_op(n) == op_Filter)
648 n = get_nodes_Block(n);
649 if (intern_get_irn_op(n) == op_Block) {
650 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
651 if (is_ip_cfop(cfop)) {
652 current_ir_graph = get_irn_irg(cfop);
653 set_irg_visited(current_ir_graph, get_max_irg_visited());
661 /* Walks up the stack passing n and then finding the node
662 where we walked into the irg n is contained in.
663 Here we switch the irg. */
665 find_irg_on_stack (ir_node *n) {
667 ir_graph *old_current = current_ir_graph;
670 if (interprocedural_view) {
671 for (i = tos; i >= 0; i--) {
672 if (stack[i] == n) break;
677 for (; i >= 0; i--) {
679 /*printf(" Visiting %d ", i); DDMN(m);*/
681 current_ir_graph = get_irn_irg(m);
684 if (intern_get_irn_op(m) == op_Filter) {
685 /* Find the corresponding ip_cfop */
686 ir_node *pred = stack[i+1];
688 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
689 if (get_Filter_cg_pred(m, j) == pred) break;
690 if (j >= get_Filter_n_cg_preds(m))
691 /* It is a filter we didn't pass as the predecessors are marked. */
693 assert(get_Filter_cg_pred(m, j) == pred);
705 static void test(ir_node *pred, ir_node *root, ir_node *this) {
707 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
709 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
710 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
711 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
713 printf("tos: %d\n", tos);
715 for (i = tos; i >= 0; i--) {
716 ir_node *n = stack[i];
718 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
723 /* Test for legal loop header: Block, Phi, ... */
724 INLINE static bool is_possible_loop_head(ir_node *n) {
725 ir_op *op = intern_get_irn_op(n);
726 return ((op == op_Block) ||
728 ((op == op_Filter) && interprocedural_view));
731 /* Returns true if n is a loop header, i.e., it is a Block, Phi
732 or Filter node and has predecessors within the loop and out
734 @arg root: only needed for assertion. */
736 is_head (ir_node *n, ir_node *root)
739 int some_outof_loop = 0, some_in_loop = 0;
741 /* Test for legal loop header: Block, Phi, ... */
742 if (!is_possible_loop_head(n))
745 if (!is_outermost_Start(n)) {
746 arity = intern_get_irn_arity(n);
747 for (i = get_start_index(n); i < arity; i++) {
748 ir_node *pred = intern_get_irn_n(n, i);
750 if (is_backedge(n, i)) continue;
751 if (!irn_is_in_stack(pred)) {
754 if(get_irn_uplink(pred) < get_irn_uplink(root))
756 DDMN(pred); DDMN(root);
758 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
763 return some_outof_loop && some_in_loop;
766 /* Returns index of the predecessor with the smallest dfn number
767 greater-equal than limit. */
769 smallest_dfn_pred (ir_node *n, int limit)
771 int i, index = -2, min = -1;
773 if (!is_outermost_Start(n)) {
774 int arity = intern_get_irn_arity(n);
775 for (i = get_start_index(n); i < arity; i++) {
776 ir_node *pred = intern_get_irn_n(n, i);
778 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
779 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
781 min = get_irn_dfn(pred);
788 /* Returns index of the predecessor with the largest dfn number. */
790 largest_dfn_pred (ir_node *n)
792 int i, index = -2, max = -1;
794 if (!is_outermost_Start(n)) {
795 int arity = intern_get_irn_arity(n);
796 for (i = get_start_index(n); i < arity; i++) {
797 ir_node *pred = intern_get_irn_n(n, i);
798 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
799 if (get_irn_dfn(pred) > max) {
801 max = get_irn_dfn(pred);
808 /* Searches the stack for possible loop heads. Tests these for backedges.
809 If it finds a head with an unmarked backedge it marks this edge and
810 returns the tail of the loop.
811 If it finds no backedge returns NULL.
812 ("disable_backedge" in fiasco) */
815 find_tail (ir_node *n) {
817 int i, res_index = -2;
820 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
823 m = stack[tos-1]; /* tos = top of stack */
824 if (is_head (m, n)) {
825 res_index = smallest_dfn_pred(m, 0);
826 if ((res_index == -2) && /* no smallest dfn pred found. */
830 if (m == n) return NULL;
831 for (i = tos-2; ; --i) {
833 if (is_head (m, n)) {
834 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
835 if (res_index == -2) /* no smallest dfn pred found. */
836 res_index = largest_dfn_pred (m);
841 assert (res_index > -2);
843 set_backedge (m, res_index);
844 return is_outermost_Start(n) ? NULL : intern_get_irn_n(m, res_index);
848 #if EXPERIMENTAL_LOOP_TREE
850 /* ----------------------------------------------------------------
851 AS: This is experimantal code to build loop trees suitable for
852 the heap analysis. Does not work correctly right now... :-(
855 Search in stack for the corresponding first Call-End-ProjX that
856 corresponds to one of the control flow predecessors of the given
857 block, that is the possible callers.
858 returns: the control predecessor to chose\
859 or -1 if no corresponding Call-End-Node could be found
861 - -------------------------------------------------------------- */
863 int search_endproj_in_stack(ir_node *start_block)
866 assert(is_Block(start_block));
867 for(i = tos - 1; i >= 0; --i)
870 if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
871 get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
873 printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
874 ir_node *end_projx = stack[i];
876 for(j = 0; j < get_irn_arity(start_block); j++)
878 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
880 if(get_irn_n(start_block, j) == begin_projx)
882 printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
892 static pmap *projx_link = NULL;
894 void link_to_reg_end (ir_node *n, void *env) {
895 if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
897 /* Reg End Projx -> Find the CallBegin Projx and hash it */
898 ir_node *end_projx = n;
899 ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
900 printf("Linked the following ProjxNodes:\n");
903 set_projx_link(begin_projx, end_projx);
907 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
909 if(projx_link == NULL)
910 projx_link = pmap_create();
911 pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
914 ir_node *get_projx_link(ir_node *cb_projx)
916 return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
923 /*************************************************************
924 * The core algorithm. *
925 *************************************************************/
928 static void scc (ir_node *n) {
930 if (irn_visited(n)) return;
933 /* Initialize the node */
934 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
935 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
936 set_irn_loop(n, NULL);
940 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
941 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
942 so is_backedge does not access array[-1] but correctly returns false! */
944 if (!is_outermost_Start(n)) {
945 int arity = intern_get_irn_arity(n);
947 #if EXPERIMENTAL_LOOP_TREE
949 /* This is meant to be used with the experimenatl code above.
950 If the above code is not used any more, this can be deleted, too.... */
952 if(interprocedural_view &&
954 get_irn_op(get_irn_n(n, 0)) == op_Proj &&
955 get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
957 /* We are at the start node of a function:
958 Walk to the callers in the correct order! */
960 DDMN(get_irn_n(get_irn_n(n, 0), 0));
961 for(i = 0; i < arity; i++)
966 pred_nr = search_endproj_in_stack(n);
967 assert(pred_nr >= 0);
968 if(is_backedge(n, pred_nr))
970 m = get_irn_n(n, pred_nr);
973 if (irn_is_in_stack(m)) {
974 /* Uplink of m is smaller if n->m is a backedge.
975 Propagate the uplink to mark the loop. */
976 if (get_irn_uplink(m) < get_irn_uplink(n))
977 set_irn_uplink(n, get_irn_uplink(m));
986 for (i = get_start_index(n); i < arity; i++) {
988 if (is_backedge(n, i)) continue;
989 /* printf("i: %d\n", i); */
990 m = intern_get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
991 /* if ((!m) || (intern_get_irn_op(m) == op_Unknown)) continue; */
993 if (irn_is_in_stack(m)) {
994 /* Uplink of m is smaller if n->m is a backedge.
995 Propagate the uplink to mark the loop. */
996 if (get_irn_uplink(m) < get_irn_uplink(n))
997 set_irn_uplink(n, get_irn_uplink(m));
1003 if (get_irn_dfn(n) == get_irn_uplink(n)) {
1004 /* This condition holds for
1005 1) the node with the incoming backedge.
1006 That is: We found a loop!
1007 2) Straight line code, because no uplink has been propagated, so the
1008 uplink still is the same as the dfn.
1010 But n might not be a proper loop head for the analysis. Proper loop
1011 heads are Block and Phi nodes. find_tail searches the stack for
1012 Block's and Phi's and takes those nodes as loop heads for the current
1013 loop instead and marks the incoming edge as backedge. */
1015 ir_node *tail = find_tail(n);
1017 /* We have a loop, that is no straight line code,
1018 because we found a loop head!
1019 Next actions: Open a new loop on the loop tree and
1020 try to find inner loops */
1023 #define NO_LOOPS_WITHOUT_HEAD 1
1024 #if NO_LOOPS_WITHOUT_HEAD
1026 /* This is an adaption of the algorithm from fiasco / optscc to
1027 * avoid loops without Block or Phi as first node. This should
1028 * severely reduce the number of evaluations of nodes to detect
1029 * a fixpoint in the heap analysis.
1030 * Further it avoids loops without firm nodes that cause errors
1031 * in the heap analyses. */
1035 if (get_loop_n_elements(current_loop) > 0) {
1045 ir_loop *l = new_loop();
1049 /* Remove the loop from the stack ... */
1050 pop_scc_unmark_visit (n);
1052 /* GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1054 /* The current backedge has been marked, that is temporarily eliminated,
1055 by find tail. Start the scc algorithm
1056 anew on the subgraph thats left (the current loop without the backedge)
1057 in order to find more inner loops. */
1061 /* GL @@@ remove experimental stuff current_ir_graph = rem; */
1063 assert (irn_visited(n));
1064 #if NO_LOOPS_WITHOUT_HEAD
1071 /* AS: No loop head was found, that is we have straightline code.
1072 Pop all nodes from the stack to the current loop. */
1078 /* Constructs backedge information for irg. In interprocedural view constructs
1079 backedges for all methods called by irg, too. */
1080 void construct_backedges(ir_graph *irg) {
1081 ir_graph *rem = current_ir_graph;
1084 assert(!interprocedural_view &&
1085 "not implemented, use construct_ip_backedges");
1087 current_ir_graph = irg;
1088 outermost_ir_graph = irg;
1090 init_scc(current_ir_graph);
1092 current_loop = NULL;
1093 new_loop(); /* sets current_loop */
1094 head_rem = current_loop; /* Just for assertion */
1096 if (interprocedural_view) {
1097 set_irg_visited(current_ir_graph, inc_max_irg_visited());
1100 inc_irg_visited(current_ir_graph);
1103 scc(get_irg_end(current_ir_graph));
1105 if (interprocedural_view) finish_ip_walk();
1107 assert(head_rem == current_loop);
1108 set_irg_loop(current_ir_graph, current_loop);
1109 set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1110 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1112 irg->loops = current_loop;
1116 count_loop (the_loop, &count, &depth);
1120 current_ir_graph = rem;
1125 void construct_ip_backedges (void) {
1126 ir_graph *rem = current_ir_graph;
1127 int rem_ipv = interprocedural_view;
1130 outermost_ir_graph = get_irp_main_irg();
1134 current_loop = NULL;
1135 new_loop(); /* sets current_loop */
1136 interprocedural_view = 1;
1138 inc_max_irg_visited();
1139 for (i = 0; i < get_irp_n_irgs(); i++)
1140 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1142 for (i = 0; i < get_irp_n_irgs(); i++) {
1144 current_ir_graph = get_irp_irg(i);
1145 /* Find real entry points */
1146 sb = get_irg_start_block(current_ir_graph);
1147 if ((get_Block_n_cfgpreds(sb) > 1) ||
1148 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1149 /* Compute scc for this graph */
1150 outermost_ir_graph = current_ir_graph;
1151 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1152 scc(get_irg_end(current_ir_graph));
1153 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1154 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1157 set_irg_loop(outermost_ir_graph, current_loop);
1158 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1159 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1161 current_ir_graph = rem;
1162 interprocedural_view = rem_ipv;
1165 void construct_ip_backedges (void) {
1166 ir_graph *rem = current_ir_graph;
1167 int rem_ipv = interprocedural_view;
1170 outermost_ir_graph = get_irp_main_irg();
1174 current_loop = NULL;
1175 new_loop(); /* sets current_loop */
1176 interprocedural_view = 1;
1178 inc_max_irg_visited();
1179 for (i = 0; i < get_irp_n_irgs(); i++)
1180 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1182 /** We have to start the walk at the same nodes as cg_walk. **/
1183 /* Walk starting at unreachable procedures. Only these
1184 * have End blocks visible in interprocedural view. */
1185 for (i = 0; i < get_irp_n_irgs(); i++) {
1187 current_ir_graph = get_irp_irg(i);
1189 sb = get_irg_start_block(current_ir_graph);
1191 if ((get_Block_n_cfgpreds(sb) > 1) ||
1192 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1194 scc(get_irg_end(current_ir_graph));
1197 /* Check whether we walked all procedures: there could be procedures
1198 with cyclic calls but no call from the outside. */
1199 for (i = 0; i < get_irp_n_irgs(); i++) {
1201 current_ir_graph = get_irp_irg(i);
1203 /* Test start block: if inner procedure end and end block are not
1204 * visible and therefore not marked. */
1205 sb = get_irg_start_block(current_ir_graph);
1206 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1209 /* Walk all endless loops in inner procedures.
1210 * We recognize an inner procedure if the End node is not visited. */
1211 for (i = 0; i < get_irp_n_irgs(); i++) {
1213 current_ir_graph = get_irp_irg(i);
1215 e = get_irg_end(current_ir_graph);
1216 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1218 /* Don't visit the End node. */
1219 for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1223 set_irg_loop(outermost_ir_graph, current_loop);
1224 set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1225 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1227 current_ir_graph = rem;
1228 interprocedural_view = rem_ipv;
1232 static void reset_backedges(ir_node *n) {
1233 if (is_possible_loop_head(n)) {
1234 int rem = interprocedural_view;
1235 interprocedural_view = 1;
1237 interprocedural_view = 0;
1239 interprocedural_view = rem;
1243 static void loop_reset_backedges(ir_loop *l) {
1245 reset_backedges(get_loop_node(l, 0));
1246 for (i = 0; i < get_loop_n_nodes(l); ++i)
1247 set_irn_loop(get_loop_node(l, i), NULL);
1248 for (i = 0; i < get_loop_n_sons(l); ++i) {
1249 loop_reset_backedges(get_loop_son(l, i));
1253 /** Removes all loop information.
1254 Resets all backedges */
1255 void free_loop_information(ir_graph *irg) {
1256 if (get_irg_loop(irg))
1257 loop_reset_backedges(get_irg_loop(irg));
1258 set_irg_loop(irg, NULL);
1259 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1260 /* We cannot free the loop nodes, they are on the obstack. */
1264 void free_all_loop_information (void) {
1266 int rem = interprocedural_view;
1267 interprocedural_view = 1; /* To visit all filter nodes */
1268 for (i = 0; i < get_irp_n_irgs(); i++) {
1269 free_loop_information(get_irp_irg(i));
1271 pmap_destroy(node_loop_map);
1272 node_loop_map = NULL;
1273 interprocedural_view = rem;
1280 /* Debug stuff *************************************************/
1282 static int test_loop_node(ir_loop *l) {
1283 int i, has_node = 0, found_problem = 0;
1286 assert(l && l->kind == k_ir_loop);
1288 if (get_loop_n_elements(l) == 0) {
1289 printf(" Loop completely empty! "); DDML(l);
1291 dump_loop(l, "-ha");
1294 le = get_loop_element(l, 0);
1295 if (*(le.kind) != k_ir_node) {
1296 assert(le.kind && *(le.kind) == k_ir_loop);
1297 printf(" First loop element is not a node! "); DDML(l);
1298 printf(" "); DDML(le.son);
1301 dump_loop(l, "-ha");
1304 if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1305 printf(" Wrong node as head! "); DDML(l);
1306 printf(" "); DDMN(le.node);
1308 dump_loop(l, "-ha");
1311 if ((get_loop_depth(l) != 0) &&
1312 (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1313 printf(" Loop head has no backedges! "); DDML(l);
1314 printf(" "); DDMN(le.node);
1316 dump_loop(l, "-ha");
1321 for (i = 0; i < get_loop_n_elements(l); ++i) {
1322 le = get_loop_element(l, i);
1323 if (*(le.kind) == k_ir_node)
1326 if (test_loop_node(le.son)) found_problem = 1;
1329 if (has_node == 0) {
1330 printf(" Loop has no firm node! "); DDML(l);
1332 dump_loop(l, "-ha");
1335 if (get_loop_loop_nr(l) == 11819)
1336 dump_loop(l, "-ha-debug");
1338 return found_problem;
1341 /** Prints all loop nodes that
1342 * - do not have any firm nodes, only loop sons
1343 * - the header is not a Phi, Block or Filter.
1345 void find_strange_loop_nodes(ir_loop *l) {
1346 int found_problem = 0;
1347 printf("\nTesting loop "); DDML(l);
1348 found_problem = test_loop_node(l);
1349 printf("Finished Test\n\n");
1350 if (found_problem) exit(0);