2 * Copyright (C) 1995-2008 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 backedge/cfloop
23 * datastructures. A variation on the Tarjan algorithm. See also
24 * [Trapp:99], Chapter 5.2.1.2.
25 * @author Goetz Lindenmaier
35 #include "irgraph_t.h"
42 #define NO_CFLOOPS_WITHOUT_HEAD 1
44 /** The outermost graph the scc is computed for */
45 static ir_graph *outermost_ir_graph;
46 /** Current cfloop construction is working on. */
47 static ir_loop *current_loop;
48 /** Counts the number of allocated cfloop nodes.
49 * Each cfloop node gets a unique number.
50 * @todo What for? ev. remove.
52 static int loop_node_cnt = 0;
53 /** Counter to generate depth first numbering of visited nodes. */
54 static int current_dfn = 1;
56 static int max_loop_depth = 0;
58 void link_to_reg_end(ir_node *n, void *env);
60 /**********************************************************************/
61 /* Node attributes **/
62 /**********************************************************************/
64 /**********************************************************************/
65 /* Node attributes needed for the construction. **/
66 /**********************************************************************/
69 * The SCC info. Additional fields for an ir-node needed for the
72 typedef struct scc_info {
73 int in_stack; /**< Marks whether node is on the stack. */
74 int dfn; /**< Depth first search number. */
75 int uplink; /**< dfn number of ancestor. */
78 /** Allocate a new scc_info on the given obstack */
79 static inline scc_info *new_scc_info(struct obstack *obst) {
80 scc_info *info = obstack_alloc(obst, sizeof(*info));
81 memset(info, 0, sizeof(*info));
86 * Marks the node n to be on the stack.
88 static inline void mark_irn_in_stack(ir_node *n) {
89 scc_info *info = get_irn_link(n);
94 * Marks the node n to be not on the stack.
96 static inline void mark_irn_not_in_stack(ir_node *n) {
97 scc_info *info = get_irn_link(n);
102 * Returns whether node n is on the stack.
104 static inline int irn_is_in_stack(ir_node *n) {
105 scc_info *info = get_irn_link(n);
106 return info->in_stack;
110 * Sets node n uplink value.
112 static inline void set_irn_uplink(ir_node *n, int uplink) {
113 scc_info *info = get_irn_link(n);
114 info->uplink = uplink;
118 * Return node n uplink value.
120 static inline int get_irn_uplink(ir_node *n) {
121 scc_info *info = get_irn_link(n);
126 * Sets node n dfn value.
128 static inline void set_irn_dfn(ir_node *n, int dfn) {
129 scc_info *info = get_irn_link(n);
134 * Returns node n dfn value.
136 static inline int get_irn_dfn(ir_node *n) {
137 scc_info *info = get_irn_link(n);
141 /**********************************************************************/
143 /**********************************************************************/
145 /** An IR-node stack */
146 static ir_node **stack = NULL;
147 /** The top (index) of the IR-node stack */
151 * Initializes the IR-node stack
153 static inline void init_stack(void) {
155 ARR_RESIZE(ir_node *, stack, 1000);
157 stack = NEW_ARR_F(ir_node *, 1000);
162 static void finish_stack(void)
169 * Push a node n onto the IR-node stack.
171 static inline void push(ir_node *n) {
172 if (tos == ARR_LEN(stack)) {
173 int nlen = ARR_LEN(stack) * 2;
174 ARR_RESIZE(ir_node *, stack, nlen);
177 mark_irn_in_stack(n);
181 * Pop a node from the IR-node stack and return it.
183 static inline ir_node *pop(void) {
184 ir_node *n = stack[--tos];
185 mark_irn_not_in_stack(n);
190 * The nodes from tos up to n belong to the current loop.
191 * Removes them from the stack and adds them to the current loop.
193 static inline void pop_scc_to_loop(ir_node *n) {
199 set_irn_dfn(m, loop_node_cnt);
200 add_loop_node(current_loop, m);
201 set_irn_loop(m, current_loop);
205 /* GL ??? my last son is my grandson??? Removes cfloops with no
206 ir_nodes in them. Such loops have only another loop as son. (Why
207 can't they have two loops as sons? Does it never get that far? ) */
208 static void close_loop(ir_loop *l) {
209 int last = get_loop_n_elements(l) - 1;
210 loop_element lelement = get_loop_element(l, last);
211 ir_loop *last_son = lelement.son;
213 if (get_kind(last_son) == k_ir_loop &&
214 get_loop_n_elements(last_son) == 1) {
217 lelement = get_loop_element(last_son, 0);
219 if (get_kind(gson) == k_ir_loop) {
220 loop_element new_last_son;
222 gson->outer_loop = l;
223 new_last_son.son = gson;
224 l->children[last] = new_last_son;
226 /* the loop last_son is dead now, recover at least some memory */
227 DEL_ARR_F(last_son->children);
235 * Removes and unmarks all nodes up to n from the stack.
236 * The nodes must be visited once more to assign them to a scc.
238 static inline void pop_scc_unmark_visit(ir_node *n) {
243 set_irn_visited(m, 0);
247 /**********************************************************************/
248 /* The loop datastructure. **/
249 /**********************************************************************/
252 * Allocates a new loop as son of current_loop. Sets current_loop
253 * to the new loop and returns its father.
254 * The loop is allocated on the outermost_ir_graphs's obstack.
256 static ir_loop *new_loop(void) {
257 ir_loop *father = current_loop;
258 ir_loop *son = alloc_loop(father, outermost_ir_graph->obst);
260 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
265 /**********************************************************************/
266 /* Constructing and destructing the loop/backedge information. **/
267 /**********************************************************************/
269 /* Initialization steps. **********************************************/
272 * Allocates a scc_info for every Block node n.
273 * Clear the backedges for all nodes.
274 * Called from a walker.
276 static inline void init_node(ir_node *n, void *env) {
277 struct obstack *obst = env;
279 set_irn_link(n, new_scc_info(obst));
284 * Initializes the common global settings for the scc algorithm
286 static inline void init_scc_common(void) {
293 * Initializes the scc algorithm for the intraprocedural case.
294 * Add scc info to every block node.
296 static inline void init_scc(ir_graph *irg, struct obstack *obst) {
298 irg_walk_graph(irg, init_node, NULL, obst);
301 static inline void finish_scc(void)
306 #ifdef INTERPROCEDURAL_VIEW
308 * Initializes the scc algorithm for the interprocedural case.
310 static inline void init_ip_scc(struct obstack *obst) {
312 cg_walk(init_node, NULL, obst);
314 #if EXPERIMENTAL_CFLOOP_TREE
315 cg_walk(link_to_reg_end, NULL, NULL);
321 * Condition for breaking the recursion: n is the block
322 * that gets the initial control flow from the Start node.
324 static int is_outermost_StartBlock(ir_node *n) {
325 /* Test whether this is the outermost Start node. If so
326 recursion must end. */
328 if (get_Block_n_cfgpreds(n) == 1 &&
329 is_Start(skip_Proj(get_Block_cfgpred(n, 0))) &&
330 get_Block_cfgpred_block(n, 0) == n) {
336 /** Returns non-zero if n is a loop header, i.e., it is a Block node
337 * and has predecessors within the cfloop and out of the cfloop.
339 * @param n the block node to check
340 * @param root only needed for assertion.
342 static int is_head(ir_node *n, ir_node *root) {
344 int some_outof_loop = 0, some_in_loop = 0;
349 if (!is_outermost_StartBlock(n)) {
350 arity = get_Block_n_cfgpreds(n);
351 for (i = 0; i < arity; i++) {
352 ir_node *pred = get_Block_cfgpred_block(n, i);
353 /* ignore Bad control flow: it cannot happen */
356 if (is_backedge(n, i))
358 if (!irn_is_in_stack(pred)) {
361 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
366 return some_outof_loop & some_in_loop;
371 * Returns non-zero if n is possible loop head of an endless loop.
372 * I.e., it is a Block node and has only predecessors
375 * @param n the block node to check
376 * @param root only needed for assertion.
378 static int is_endless_head(ir_node *n, ir_node *root) {
380 int none_outof_loop = 1, some_in_loop = 0;
384 /* Test for legal loop header: Block, Phi, ... */
385 if (!is_outermost_StartBlock(n)) {
386 arity = get_Block_n_cfgpreds(n);
387 for (i = 0; i < arity; i++) {
388 ir_node *pred = get_Block_cfgpred_block(n, i);
389 /* ignore Bad control flow: it cannot happen */
392 if (is_backedge(n, i))
394 if (!irn_is_in_stack(pred)) {
397 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
402 return none_outof_loop && some_in_loop;
406 * Returns index of the predecessor with the smallest dfn number
407 * greater-equal than limit.
409 static int smallest_dfn_pred(ir_node *n, int limit) {
410 int i, index = -2, min = -1;
412 if (!is_outermost_StartBlock(n)) {
413 int arity = get_Block_n_cfgpreds(n);
414 for (i = 0; i < arity; i++) {
415 ir_node *pred = get_Block_cfgpred_block(n, i);
416 /* ignore Bad control flow: it cannot happen */
419 if (is_backedge(n, i) || !irn_is_in_stack(pred))
421 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
423 min = get_irn_dfn(pred);
431 * Returns index of the predecessor with the largest dfn number.
433 static int largest_dfn_pred(ir_node *n) {
434 int i, index = -2, max = -1;
436 if (!is_outermost_StartBlock(n)) {
437 int arity = get_Block_n_cfgpreds(n);
438 for (i = 0; i < arity; i++) {
439 ir_node *pred = get_Block_cfgpred_block(n, i);
440 /* ignore Bad control flow: it cannot happen */
443 if (is_backedge(n, i) || !irn_is_in_stack(pred))
445 if (get_irn_dfn(pred) > max) {
447 max = get_irn_dfn(pred);
455 * Searches the stack for possible loop heads. Tests these for backedges.
456 * If it finds a head with an unmarked backedge it marks this edge and
457 * returns the tail of the loop.
458 * If it finds no backedge returns NULL.
460 static ir_node *find_tail(ir_node *n) {
462 int i, res_index = -2;
464 m = stack[tos-1]; /* tos = top of stack */
466 res_index = smallest_dfn_pred(m, 0);
467 if ((res_index == -2) && /* no smallest dfn pred found. */
473 for (i = tos-2; i >= 0; --i) {
477 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
478 if (res_index == -2) /* no smallest dfn pred found. */
479 res_index = largest_dfn_pred(m);
481 if ((m == n) && (res_index == -2)) {
488 /* We should not walk past our selves on the stack: The upcoming nodes
489 are not in this loop. We assume a loop not reachable from Start. */
497 /* A dead loop not reachable from Start. */
498 for (i = tos-2; i >= 0; --i) {
500 if (is_endless_head(m, n)) {
501 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
502 if (res_index == -2) /* no smallest dfn pred found. */
503 res_index = largest_dfn_pred(m);
506 if (m == n) break; /* It's not an unreachable loop, either. */
508 //assert(0 && "no head found on stack");
511 assert(res_index > -2);
513 set_backedge(m, res_index);
514 return is_outermost_StartBlock(n) ? NULL : get_Block_cfgpred_block(m, res_index);
518 * returns non.zero if l is the outermost loop.
520 inline static int is_outermost_loop(ir_loop *l) {
521 return l == get_loop_outer_loop(l);
524 /*-----------------------------------------------------------*
525 * The core algorithm. *
526 *-----------------------------------------------------------*/
529 * Walks over all blocks of a graph
531 static void cfscc(ir_node *n) {
536 if (irn_visited_else_mark(n)) return;
538 /* Initialize the node */
539 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
540 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
541 set_irn_loop(n, NULL);
545 if (!is_outermost_StartBlock(n)) {
546 int arity = get_Block_n_cfgpreds(n);
548 for (i = 0; i < arity; i++) {
551 if (is_backedge(n, i))
553 m = get_Block_cfgpred_block(n, i);
554 /* ignore Bad control flow: it cannot happen */
559 if (irn_is_in_stack(m)) {
560 /* Uplink of m is smaller if n->m is a backedge.
561 Propagate the uplink to mark the cfloop. */
562 if (get_irn_uplink(m) < get_irn_uplink(n))
563 set_irn_uplink(n, get_irn_uplink(m));
568 if (get_irn_dfn(n) == get_irn_uplink(n)) {
569 /* This condition holds for
570 1) the node with the incoming backedge.
571 That is: We found a cfloop!
572 2) Straight line code, because no uplink has been propagated, so the
573 uplink still is the same as the dfn.
575 But n might not be a proper cfloop head for the analysis. Proper cfloop
576 heads are Block and Phi nodes. find_tail searches the stack for
577 Block's and Phi's and takes those nodes as cfloop heads for the current
578 cfloop instead and marks the incoming edge as backedge. */
580 ir_node *tail = find_tail(n);
582 /* We have a cfloop, that is no straight line code,
583 because we found a cfloop head!
584 Next actions: Open a new cfloop on the cfloop tree and
585 try to find inner cfloops */
587 #if NO_CFLOOPS_WITHOUT_HEAD
589 /* This is an adaption of the algorithm from fiasco / optscc to
590 * avoid cfloops without Block or Phi as first node. This should
591 * severely reduce the number of evaluations of nodes to detect
592 * a fixpoint in the heap analysis.
593 * Further it avoids cfloops without firm nodes that cause errors
594 * in the heap analyses. */
598 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
608 ir_loop *l = new_loop();
612 /* Remove the cfloop from the stack ... */
613 pop_scc_unmark_visit(n);
615 /* The current backedge has been marked, that is temporarily eliminated,
616 by find tail. Start the scc algorithm
617 anew on the subgraph thats left (the current cfloop without the backedge)
618 in order to find more inner cfloops. */
622 assert(irn_visited(n));
623 #if NO_CFLOOPS_WITHOUT_HEAD
628 /* AS: No cfloop head was found, that is we have straight line code.
629 Pop all nodes from the stack to the current cfloop. */
635 /* Constructs control flow backedge information for irg. */
636 int construct_cf_backedges(ir_graph *irg) {
637 ir_graph *rem = current_ir_graph;
639 ir_node *end = get_irg_end(irg);
643 assert(!get_interprocedural_view() &&
644 "use construct_ip_cf_backedges()");
647 current_ir_graph = irg;
648 outermost_ir_graph = irg;
651 init_scc(irg, &temp);
654 new_loop(); /* sets current_loop */
655 head_rem = current_loop; /* Just for assertion */
657 inc_irg_visited(irg);
659 /* walk over all blocks of the graph, including keep alives */
660 cfscc(get_irg_end_block(irg));
661 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
662 ir_node *el = get_End_keepalive(end, i);
667 obstack_free(&temp, NULL);
669 assert(head_rem == current_loop);
670 mature_loops(current_loop, irg->obst);
671 set_irg_loop(irg, current_loop);
672 set_irg_loopinfo_state(irg, loopinfo_cf_consistent);
673 assert(get_irg_loop(irg)->kind == k_ir_loop);
675 current_ir_graph = rem;
676 return max_loop_depth;
679 void assure_cf_loop(ir_graph *irg) {
680 irg_loopinfo_state state = get_irg_loopinfo_state(irg);
682 if (state != loopinfo_cf_consistent)
683 construct_cf_backedges(irg);
686 #ifdef INTERPROCEDURAL_VIEW
687 int construct_ip_cf_backedges (void) {
688 ir_graph *rem = current_ir_graph;
689 int rem_ipv = get_interprocedural_view();
693 assert(get_irp_ip_view_state() == ip_view_valid);
695 outermost_ir_graph = get_irp_main_irg();
701 new_loop(); /* sets current_loop */
702 set_interprocedural_view(1);
704 inc_max_irg_visited();
705 for (i = 0; i < get_irp_n_irgs(); i++)
706 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
708 /** We have to start the walk at the same nodes as cg_walk. **/
709 /* Walk starting at unreachable procedures. Only these
710 * have End blocks visible in interprocedural view. */
711 for (i = 0; i < get_irp_n_irgs(); i++) {
713 current_ir_graph = get_irp_irg(i);
715 sb = get_irg_start_block(current_ir_graph);
717 if ((get_Block_n_cfgpreds(sb) > 1) ||
718 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
720 cfscc(get_irg_end_block(current_ir_graph));
723 /* Check whether we walked all procedures: there could be procedures
724 with cyclic calls but no call from the outside. */
725 for (i = 0; i < get_irp_n_irgs(); i++) {
727 current_ir_graph = get_irp_irg(i);
729 /* Test start block: if inner procedure end and end block are not
730 * visible and therefore not marked. */
731 sb = get_irg_start_block(current_ir_graph);
732 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
735 /* Walk all endless cfloops in inner procedures.
736 * We recognize an inner procedure if the End node is not visited. */
737 for (i = 0; i < get_irp_n_irgs(); i++) {
739 current_ir_graph = get_irp_irg(i);
741 e = get_irg_end(current_ir_graph);
742 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
744 /* Don't visit the End node. */
745 for (j = 0; j < get_End_n_keepalives(e); j++) {
746 ir_node *el = get_End_keepalive(e, j);
747 if (is_Block(el)) cfscc(el);
752 set_irg_loop(outermost_ir_graph, current_loop);
753 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
754 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
756 obstack_free(&temp, NULL);
757 current_ir_graph = rem;
758 set_interprocedural_view(rem_ipv);
759 return max_loop_depth;
764 * Clear the intra- and the interprocedural
765 * backedge information pf a block.
767 static void reset_backedges(ir_node *block) {
770 assert(is_Block(block));
771 #ifdef INTERPROCEDURAL_VIEW
772 rem = get_interprocedural_view();
773 set_interprocedural_view(1);
774 clear_backedges(block);
775 set_interprocedural_view(0);
776 clear_backedges(block);
777 set_interprocedural_view(rem);
780 clear_backedges(block);
785 * Reset all backedges of the first block of
786 * a loop as well as all loop info for all nodes of this loop.
787 * Recurse into all nested loops.
789 static void loop_reset_backedges(ir_loop *l) {
791 reset_backedges(get_loop_node(l, 0));
792 for (i = 0; i < get_loop_n_nodes(l); ++i)
793 set_irn_loop(get_loop_node(l, i), NULL);
794 for (i = 0; i < get_loop_n_sons(l); ++i) {
795 loop_reset_backedges(get_loop_son(l, i));
799 /* Removes all cfloop information.
800 Resets all backedges */
801 void free_cfloop_information(ir_graph *irg) {
802 ir_loop *loop = get_irg_loop(irg);
804 loop_reset_backedges(loop);
805 set_irg_loop(irg, NULL);
807 set_irg_loopinfo_state(irg, loopinfo_none);
808 /* We cannot free the cfloop nodes, they are on the obstack. */
812 void free_all_cfloop_information(void) {
814 #ifdef INTERPROCEDURAL_VIEW
815 int rem = get_interprocedural_view();
816 set_interprocedural_view(1); /* To visit all filter nodes */
818 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
819 free_cfloop_information(get_irp_irg(i));
821 #ifdef INTERPROCEDURAL_VIEW
822 set_interprocedural_view(rem);