2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Compute the strongly connected regions and build
23 * backedge/loop datastructures.
24 * A variation on the Tarjan algorithm. See also [Trapp:99],
26 * @author Goetz Lindenmaier
37 #include "irgraph_t.h"
45 /** The outermost graph the scc is computed for. */
46 static ir_graph *outermost_ir_graph;
47 /** Current loop construction is working on. */
48 static ir_loop *current_loop;
49 /** Counts the number of allocated loop nodes.
50 * Each loop node gets a unique number.
51 * @todo What for? ev. remove.
53 static int loop_node_cnt = 0;
54 /** Counter to generate depth first numbering of visited nodes. */
55 static int current_dfn = 1;
57 static unsigned max_loop_depth = 0;
59 void link_to_reg_end(ir_node *n, void *env);
60 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
61 ir_node *get_projx_link(ir_node *cb_projx);
63 /**********************************************************************/
64 /* Node attributes **/
65 /**********************************************************************/
67 /**********************************************************************/
68 /* Node attributes needed for the construction. **/
69 /**********************************************************************/
71 typedef struct scc_info {
72 int in_stack; /**< Marks whether node is on the stack. */
73 int dfn; /**< Depth first search number. */
74 int uplink; /**< dfn number of ancestor. */
75 /* ir_loop *loop; *//* Refers to the containing loop. */
77 struct section *section;
84 * Allocates a new SCC info on the given obstack.
86 static inline scc_info *new_scc_info(struct obstack *obst)
88 return OALLOCZ(obst, scc_info);
92 * Mark node n being on the SCC stack.
94 static inline void mark_irn_in_stack(ir_node *n)
96 scc_info *scc = (scc_info*) get_irn_link(n);
102 * Mark node n NOT being on the SCC stack.
104 static inline void mark_irn_not_in_stack(ir_node *n)
106 scc_info *scc = (scc_info*) get_irn_link(n);
112 * Checks if a node is on the SCC stack.
114 static inline int irn_is_in_stack(ir_node *n)
116 scc_info *scc = (scc_info*) get_irn_link(n);
118 return scc->in_stack;
122 * Sets the uplink number for a node.
124 static inline void set_irn_uplink(ir_node *n, int uplink)
126 scc_info *scc = (scc_info*) get_irn_link(n);
128 scc->uplink = uplink;
132 * Returns the uplink number for a node.
134 static int get_irn_uplink(ir_node *n)
136 scc_info *scc = (scc_info*) get_irn_link(n);
142 * Sets the depth-first-search number for a node.
144 static inline void set_irn_dfn(ir_node *n, int dfn)
146 scc_info *scc = (scc_info*) get_irn_link(n);
152 * Returns the depth-first-search number of a node.
154 static int get_irn_dfn(ir_node *n)
156 scc_info *scc = (scc_info*) get_irn_link(n);
162 static ir_loop *find_nodes_loop(ir_node *n, ir_loop *l)
167 /* Test whether n is contained in this loop. */
168 for (i = 0; i < get_loop_n_nodes(l); i++)
169 if (n == get_loop_node(l, i)) return l;
171 /* Is this a leave in the loop tree? If so loop not found. */
172 if (get_loop_n_sons(l) == 0) return NULL;
174 /* Else descend in the loop tree. */
175 for (i = 0; i < get_loop_n_sons(l); i++) {
176 res = find_nodes_loop(n, get_loop_son(l, i));
182 /* @@@ temporary implementation, costly!!! */
183 ir_loop * get_irn_loop(ir_node *n)
185 ir_loop *l = get_irg_loop(current_ir_graph);
186 l = find_nodes_loop(n, l);
191 /**********************************************************************/
193 /**********************************************************************/
195 static ir_node **stack = NULL;
196 static size_t tos = 0; /* top of stack */
199 * initializes the stack
201 static inline void init_stack(void)
204 ARR_RESIZE(ir_node *, stack, 1000);
206 stack = NEW_ARR_F(ir_node *, 1000);
214 static void finish_stack(void)
221 * push a node onto the stack
223 * @param n The node to push
225 static inline void push(ir_node *n)
227 if (tos == ARR_LEN(stack)) {
228 size_t nlen = ARR_LEN(stack) * 2;
229 ARR_RESIZE(ir_node *, stack, nlen);
232 mark_irn_in_stack(n);
236 * pop a node from the stack
238 * @return The topmost node
240 static inline ir_node *pop(void)
246 mark_irn_not_in_stack(n);
251 * The nodes up to n belong to the current loop.
252 * Removes them from the stack and adds them to the current loop.
254 static inline void pop_scc_to_loop(ir_node *n)
262 set_irn_dfn(m, loop_node_cnt);
263 add_loop_node(current_loop, m);
264 set_irn_loop(m, current_loop);
268 /* GL ??? my last son is my grandson??? Removes loops with no
269 ir_nodes in them. Such loops have only another loop as son. (Why
270 can't they have two loops as sons? Does it never get that far? ) */
271 static void close_loop(ir_loop *l)
273 size_t last = get_loop_n_elements(l) - 1;
274 loop_element lelement = get_loop_element(l, last);
275 ir_loop *last_son = lelement.son;
277 if (get_kind(last_son) == k_ir_loop &&
278 get_loop_n_elements(last_son) == 1) {
281 lelement = get_loop_element(last_son, 0);
284 if (get_kind(gson) == k_ir_loop) {
285 loop_element new_last_son;
287 gson->outer_loop = l;
288 new_last_son.son = gson;
289 l->children[last] = new_last_son;
296 /* Removes and unmarks all nodes up to n from the stack.
297 The nodes must be visited once more to assign them to a scc. */
298 static inline void pop_scc_unmark_visit(ir_node *n)
304 set_irn_visited(m, 0);
308 /**********************************************************************/
309 /* The loop datastructure. **/
310 /**********************************************************************/
312 /* Allocates a new loop as son of current_loop. Sets current_loop
313 to the new loop and returns the father. */
314 static ir_loop *new_loop(void)
316 ir_loop *father = current_loop;
317 ir_loop *son = alloc_loop(father, get_irg_obstack(outermost_ir_graph));
319 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
324 /**********************************************************************/
325 /* Constructing and destructing the loop/backedge information. **/
326 /**********************************************************************/
328 /* Initialization steps. **********************************************/
330 static inline void init_node(ir_node *n, void *env)
332 struct obstack *obst = (struct obstack*) env;
333 set_irn_link(n, new_scc_info(obst));
337 static inline void init_scc_common(void)
344 static inline void init_scc(ir_graph *irg, struct obstack *obst)
347 irg_walk_graph(irg, init_node, NULL, obst);
349 irg_walk (irg, link_to_reg_end, NULL, NULL);
353 static inline void finish_scc(void)
359 * Check whether a given node represents the outermost Start
360 * block. In intra-procedural view this is the start block of the
361 * current graph, in interprocedural view it is the start block
362 * of the outer most graph.
364 * @param n the node to check
366 * This is the condition for breaking the scc recursion.
368 static int is_outermost_Start(ir_node *n)
370 /* Test whether this is the outermost Start node. */
371 if (is_Block(n) && get_Block_n_cfgpreds(n) == 1) {
372 ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));
373 if (is_Start(pred) && get_nodes_block(pred) == n)
379 /* When to walk from nodes to blocks. Only for Control flow operations? */
380 static inline int get_start_index(ir_node *n)
382 #undef BLOCK_BEFORE_NODE
383 #define BLOCK_BEFORE_NODE 1
385 #if BLOCK_BEFORE_NODE
387 /* This version assures, that all nodes are ordered absolutely. This allows
388 to undef all nodes in the heap analysis if the block is false, which
390 I.e., with this code, the order on the loop tree is correct. But a
391 (single) test showed the loop tree is deeper. */
394 (get_irg_pinned(get_irn_irg(n)) == op_pin_state_floats &&
395 get_irn_pinned(n) == op_pin_state_floats))
396 // Here we could test for backedge at -1 which is illegal
403 /* This version causes deeper loop trees (at least we verified this
405 But it guarantees that Blocks are analysed before nodes contained in the
406 block. If so, we can set the value to undef if the block is not \
408 if (is_cfop(n) || is_fragile_op(n) || is_Start(n))
417 * Return non-zero if the given node is a legal loop header:
420 * @param n the node to check
422 static inline int is_possible_loop_head(ir_node *n)
424 return is_Block(n) || is_Phi(n);
428 * Returns non-zero if n is a loop header, i.e., it is a Block or Phi
429 * node and has predecessors within the loop and out of the loop.
431 * @param n the node to check
432 * @param root only needed for assertion.
434 static int is_head(ir_node *n, ir_node *root)
437 int some_outof_loop = 0, some_in_loop = 0;
439 /* Test for legal loop header: Block, Phi, ... */
440 if (!is_possible_loop_head(n))
443 if (!is_outermost_Start(n)) {
445 int uplink = get_irn_uplink(root);
449 arity = get_irn_arity(n);
450 for (i = get_start_index(n); i < arity; i++) {
452 if (is_backedge(n, i))
454 pred = get_irn_n(n, i);
455 if (! irn_is_in_stack(pred)) {
458 assert(get_irn_uplink(pred) >= uplink);
463 return some_outof_loop & some_in_loop;
467 * Returns non-zero if n is possible loop head of an endless loop.
468 * I.e., it is a Block or Phi node and has only predecessors
471 * @param n the node to check
472 * @param root only needed for assertion.
474 static int is_endless_head(ir_node *n, ir_node *root)
477 int none_outof_loop = 1, some_in_loop = 0;
479 /* Test for legal loop header: Block, Phi, ... */
480 if (!is_possible_loop_head(n))
483 if (!is_outermost_Start(n)) {
485 int uplink = get_irn_uplink(root);
489 arity = get_irn_arity(n);
490 for (i = get_start_index(n); i < arity; i++) {
492 if (is_backedge(n, i))
494 pred = get_irn_n(n, i);
495 if (!irn_is_in_stack(pred)) {
498 assert(get_irn_uplink(pred) >= uplink);
503 return none_outof_loop & some_in_loop;
506 /** Returns index of the predecessor with the smallest dfn number
507 greater-equal than limit. */
508 static int smallest_dfn_pred(ir_node *n, int limit)
510 int i, index = -2, min = -1;
512 if (!is_outermost_Start(n)) {
513 int arity = get_irn_arity(n);
514 for (i = get_start_index(n); i < arity; i++) {
515 ir_node *pred = get_irn_n(n, i);
516 if (is_backedge(n, i) || !irn_is_in_stack(pred))
518 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
520 min = get_irn_dfn(pred);
528 * Returns index of the predecessor with the largest dfn number.
530 static int largest_dfn_pred(ir_node *n)
532 int i, index = -2, max = -1;
534 if (!is_outermost_Start(n)) {
535 int arity = get_irn_arity(n);
536 for (i = get_start_index(n); i < arity; i++) {
537 ir_node *pred = get_irn_n(n, i);
538 if (is_backedge (n, i) || !irn_is_in_stack(pred))
540 if (get_irn_dfn(pred) > max) {
542 max = get_irn_dfn(pred);
550 * Searches the stack for possible loop heads. Tests these for backedges.
551 * If it finds a head with an unmarked backedge it marks this edge and
552 * returns the tail of the loop.
553 * If it finds no backedge returns NULL.
554 * ("disable_backedge" in fiasco)
556 * @param n A node where uplink == dfn.
558 static ir_node *find_tail(ir_node *n)
561 int i, res_index = -2;
564 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
566 m = stack[tos-1]; /* tos = top of stack */
568 res_index = smallest_dfn_pred(m, 0);
569 if ((res_index == -2) && /* no smallest dfn pred found. */
573 if (m == n) return NULL; // Is this to catch Phi - self loops?
574 for (i = tos-2; i >= 0; --i) {
578 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
579 if (res_index == -2) /* no smallest dfn pred found. */
580 res_index = largest_dfn_pred(m);
582 if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
588 /* We should not walk past our selves on the stack: The upcoming nodes
589 are not in this loop. We assume a loop not reachable from Start. */
597 /* A dead loop not reachable from Start. */
598 for (i = tos-2; i >= 0; --i) {
600 if (is_endless_head(m, n)) {
601 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
602 if (res_index == -2) /* no smallest dfn pred found. */
603 res_index = largest_dfn_pred (m);
606 /* It's not an unreachable loop, either. */
610 //assert(0 && "no head found on stack");
614 if (res_index <= -2) {
615 /* It's a completely bad loop: without Phi/Block nodes that can
616 be a head. I.e., the code is "dying". We break the loop by
617 setting Bad nodes. */
618 ir_graph *irg = get_irn_irg(n);
619 ir_mode *mode = get_irn_mode(n);
620 ir_node *bad = new_r_Bad(irg, mode);
621 int arity = get_irn_arity(n);
622 for (i = -1; i < arity; ++i) {
623 set_irn_n(n, i, bad);
627 assert(res_index > -2);
629 set_backedge(m, res_index);
630 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
633 static inline int is_outermost_loop(ir_loop *l)
635 return l == get_loop_outer_loop(l);
638 /*-----------------------------------------------------------*
639 * The core algorithm. *
640 *-----------------------------------------------------------*/
643 * The core algorithm: Find strongly coupled components.
645 * @param n node to start
647 static void scc(ir_node *n)
649 if (irn_visited_else_mark(n))
652 /* Initialize the node */
653 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
654 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
655 set_irn_loop(n, NULL);
659 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
660 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
661 so is_backedge does not access array[-1] but correctly returns false! */
663 if (!is_outermost_Start(n)) {
664 int i, arity = get_irn_arity(n);
666 for (i = get_start_index(n); i < arity; ++i) {
668 if (is_backedge(n, i))
672 if (irn_is_in_stack(m)) {
673 /* Uplink of m is smaller if n->m is a backedge.
674 Propagate the uplink to mark the loop. */
675 if (get_irn_uplink(m) < get_irn_uplink(n))
676 set_irn_uplink(n, get_irn_uplink(m));
681 if (get_irn_dfn(n) == get_irn_uplink(n)) {
682 /* This condition holds for
683 1) the node with the incoming backedge.
684 That is: We found a loop!
685 2) Straight line code, because no uplink has been propagated, so the
686 uplink still is the same as the dfn.
688 But n might not be a proper loop head for the analysis. Proper loop
689 heads are Block and Phi nodes. find_tail() searches the stack for
690 Block's and Phi's and takes those nodes as loop heads for the current
691 loop instead and marks the incoming edge as backedge. */
693 ir_node *tail = find_tail(n);
695 /* We have a loop, that is no straight line code,
696 because we found a loop head!
697 Next actions: Open a new loop on the loop tree and
698 try to find inner loops */
700 /* This is an adaption of the algorithm from fiasco / optscc to
701 * avoid loops without Block or Phi as first node. This should
702 * severely reduce the number of evaluations of nodes to detect
703 * a fixpoint in the heap analysis.
704 * Further it avoids loops without firm nodes that cause errors
705 * in the heap analyses.
706 * But attention: don't do it for the outermost loop: This loop
707 * is not iterated. A first block can be a loop head in case of
708 * an endless recursion. */
712 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
720 /* Remove the loop from the stack ... */
721 pop_scc_unmark_visit(n);
723 /* The current backedge has been marked, that is temporarily eliminated,
724 by find tail. Start the scc algorithm
725 again on the subgraph that is left (the current loop without the backedge)
726 in order to find more inner loops. */
729 assert(irn_visited(n));
733 /* No loop head was found, that is we have straight line code.
734 Pop all nodes from the stack to the current loop. */
740 int construct_backedges(ir_graph *irg)
742 ir_graph *rem = current_ir_graph;
747 current_ir_graph = irg;
748 outermost_ir_graph = irg;
751 init_scc(irg, &temp);
754 new_loop(); /* sets current_loop */
755 head_rem = current_loop; /* Just for assertion */
757 inc_irg_visited(irg);
759 scc(get_irg_end(irg));
762 obstack_free(&temp, NULL);
764 assert(head_rem == current_loop);
765 mature_loops(current_loop, get_irg_obstack(irg));
766 set_irg_loop(irg, current_loop);
767 add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
768 assert(get_irg_loop(irg)->kind == k_ir_loop);
769 current_ir_graph = rem;
770 return max_loop_depth;
773 static void reset_backedges(ir_node *n)
775 if (is_possible_loop_head(n)) {
781 static void loop_reset_backedges(ir_loop *l)
784 reset_backedges(get_loop_node(l, 0));
785 for (i = 0; i < get_loop_n_nodes(l); ++i)
786 set_irn_loop(get_loop_node(l, i), NULL);
787 for (i = 0; i < get_loop_n_sons(l); ++i) {
788 loop_reset_backedges(get_loop_son(l, i));
793 static void loop_reset_node(ir_node *n, void *env)
796 set_irn_loop(n, NULL);
800 void free_loop_information(ir_graph *irg)
802 /* We can not use this recursion, as the loop might contain
803 illegal nodes by now. Why else would we throw away the
805 if (get_irg_loop(irg)) loop_reset_backedges(get_irg_loop(irg));
807 irg_walk_graph(irg, loop_reset_node, NULL, NULL);
808 set_irg_loop(irg, NULL);
809 clear_irg_properties(current_ir_graph, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
810 /* We cannot free the loop nodes, they are on the obstack. */
813 void free_all_loop_information(void)
816 for (i = 0; i < get_irp_n_irgs(); i++) {
817 free_loop_information(get_irp_irg(i));
821 /* ------------------------------------------------------------------- */
822 /* Simple analyses based on the loop information */
823 /* ------------------------------------------------------------------- */
825 static int is_loop_variant(ir_loop *l, ir_loop *b)
829 if (l == b) return 1;
831 n_elems = get_loop_n_elements(l);
832 for (i = 0; i < n_elems; ++i) {
833 loop_element e = get_loop_element(l, i);
834 if (is_ir_loop(e.kind))
835 if (is_loop_variant(e.son, b))
842 int is_loop_invariant(const ir_node *n, const ir_node *block)
844 ir_loop *l = get_irn_loop(block);
845 const ir_node *b = is_Block(n) ? n : get_nodes_block(n);
846 return !is_loop_variant(l, get_irn_loop(b));