2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Compute the strongly connected regions and build backedge/cfloop
9 * datastructures. A variation on the Tarjan algorithm. See also
10 * [Trapp:99], Chapter 5.2.1.2.
11 * @author Goetz Lindenmaier
20 #include "irgraph_t.h"
28 /** The outermost graph the scc is computed for */
29 static ir_graph *outermost_ir_graph;
30 /** Current cfloop construction is working on. */
31 static ir_loop *current_loop;
32 /** Counts the number of allocated cfloop nodes.
33 * Each cfloop node gets a unique number.
34 * @todo What for? ev. remove.
36 static int loop_node_cnt = 0;
37 /** Counter to generate depth first numbering of visited nodes. */
38 static int current_dfn = 1;
40 /**********************************************************************/
41 /* Node attributes needed for the construction. **/
42 /**********************************************************************/
45 * The SCC info. Additional fields for an ir-node needed for the
48 typedef struct scc_info {
49 int in_stack; /**< Marks whether node is on the stack. */
50 int dfn; /**< Depth first search number. */
51 int uplink; /**< dfn number of ancestor. */
54 /** Allocate a new scc_info on the given obstack */
55 static inline scc_info *new_scc_info(struct obstack *obst)
57 return OALLOCZ(obst, scc_info);
61 * Marks the node n to be on the stack.
63 static inline void mark_irn_in_stack(ir_node *n)
65 scc_info *info = (scc_info*) get_irn_link(n);
70 * Marks the node n to be not on the stack.
72 static inline void mark_irn_not_in_stack(ir_node *n)
74 scc_info *info = (scc_info*) get_irn_link(n);
79 * Returns whether node n is on the stack.
81 static inline int irn_is_in_stack(ir_node *n)
83 scc_info *info = (scc_info*) get_irn_link(n);
84 return info->in_stack;
88 * Sets node n uplink value.
90 static inline void set_irn_uplink(ir_node *n, int uplink)
92 scc_info *info = (scc_info*) get_irn_link(n);
93 info->uplink = uplink;
97 * Return node n uplink value.
99 static inline int get_irn_uplink(ir_node *n)
101 scc_info *info = (scc_info*) get_irn_link(n);
106 * Sets node n dfn value.
108 static inline void set_irn_dfn(ir_node *n, int dfn)
110 scc_info *info = (scc_info*) get_irn_link(n);
115 * Returns node n dfn value.
117 static inline int get_irn_dfn(ir_node *n)
119 scc_info *info = (scc_info*) get_irn_link(n);
123 /**********************************************************************/
125 /**********************************************************************/
127 /** An IR-node stack */
128 static ir_node **stack = NULL;
129 /** The top (index) of the IR-node stack */
130 static size_t tos = 0;
133 * Initializes the IR-node stack
135 static inline void init_stack(void)
138 ARR_RESIZE(ir_node *, stack, 1000);
140 stack = NEW_ARR_F(ir_node *, 1000);
145 static void finish_stack(void)
152 * Push a node n onto the IR-node stack.
154 static inline void push(ir_node *n)
156 if (tos == ARR_LEN(stack)) {
157 size_t nlen = ARR_LEN(stack) * 2;
158 ARR_RESIZE(ir_node *, stack, nlen);
161 mark_irn_in_stack(n);
165 * Pop a node from the IR-node stack and return it.
167 static inline ir_node *pop(void)
169 ir_node *n = stack[--tos];
170 mark_irn_not_in_stack(n);
175 * The nodes from tos up to n belong to the current loop.
176 * Removes them from the stack and adds them to the current loop.
178 static inline void pop_scc_to_loop(ir_node *n)
185 set_irn_dfn(m, loop_node_cnt);
186 add_loop_node(current_loop, m);
187 set_irn_loop(m, current_loop);
191 /* GL ??? my last son is my grandson??? Removes cfloops with no
192 ir_nodes in them. Such loops have only another loop as son. (Why
193 can't they have two loops as sons? Does it never get that far? ) */
194 static void close_loop(ir_loop *l)
196 size_t last = get_loop_n_elements(l) - 1;
197 loop_element lelement = get_loop_element(l, last);
198 ir_loop *last_son = lelement.son;
200 if (get_kind(last_son) == k_ir_loop &&
201 get_loop_n_elements(last_son) == 1) {
204 lelement = get_loop_element(last_son, 0);
206 if (get_kind(gson) == k_ir_loop) {
207 loop_element new_last_son;
209 gson->outer_loop = l;
210 new_last_son.son = gson;
211 l->children[last] = new_last_son;
213 /* the loop last_son is dead now, recover at least some memory */
214 DEL_ARR_F(last_son->children);
222 * Removes and unmarks all nodes up to n from the stack.
223 * The nodes must be visited once more to assign them to a scc.
225 static inline void pop_scc_unmark_visit(ir_node *n)
231 set_irn_visited(m, 0);
235 /**********************************************************************/
236 /* The loop datastructure. **/
237 /**********************************************************************/
240 * Allocates a new loop as son of current_loop. Sets current_loop
241 * to the new loop and returns its father.
242 * The loop is allocated on the outermost_ir_graphs's obstack.
244 static ir_loop *new_loop(void)
246 ir_loop *father = current_loop;
247 ir_loop *son = alloc_loop(father, get_irg_obstack(outermost_ir_graph));
253 /**********************************************************************/
254 /* Constructing and destructing the loop/backedge information. **/
255 /**********************************************************************/
257 /* Initialization steps. **********************************************/
260 * Allocates a scc_info for every Block node n.
261 * Clear the backedges for all nodes.
262 * Called from a walker.
264 static inline void init_node(ir_node *n, void *env)
266 struct obstack *obst = (struct obstack*) env;
268 set_irn_link(n, new_scc_info(obst));
273 * Initializes the common global settings for the scc algorithm
275 static inline void init_scc_common(void)
283 * Initializes the scc algorithm for the intraprocedural case.
284 * Add scc info to every block node.
286 static inline void init_scc(ir_graph *irg, struct obstack *obst)
289 irg_walk_graph(irg, init_node, NULL, obst);
292 static inline void finish_scc(void)
297 /** Returns non-zero if n is a loop header, i.e., it is a Block node
298 * and has predecessors within the cfloop and out of the cfloop.
300 * @param n the block node to check
301 * @param root only needed for assertion.
303 static int is_head(ir_node *n, ir_node *root)
305 int some_outof_loop = 0, some_in_loop = 0;
308 int const arity = get_Block_n_cfgpreds(n);
309 for (int i = 0; i < arity; i++) {
310 ir_node *pred = get_Block_cfgpred_block(n, i);
311 /* ignore Bad control flow: it cannot happen */
314 if (is_backedge(n, i))
316 if (!irn_is_in_stack(pred)) {
319 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
323 return some_outof_loop & some_in_loop;
328 * Returns non-zero if n is possible loop head of an endless loop.
329 * I.e., it is a Block node and has only predecessors
332 * @param n the block node to check
333 * @param root only needed for assertion.
335 static int is_endless_head(ir_node *n, ir_node *root)
337 int none_outof_loop = 1, some_in_loop = 0;
340 /* Test for legal loop header: Block, Phi, ... */
341 int const arity = get_Block_n_cfgpreds(n);
342 for (int i = 0; i < arity; i++) {
343 ir_node *pred = get_Block_cfgpred_block(n, i);
344 /* ignore Bad control flow: it cannot happen */
347 if (is_backedge(n, i))
349 if (!irn_is_in_stack(pred)) {
352 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
356 return none_outof_loop && some_in_loop;
360 * Returns index of the predecessor with the smallest dfn number
361 * greater-equal than limit.
363 static int smallest_dfn_pred(ir_node *n, int limit)
365 int i, index = -2, min = -1;
367 int arity = get_Block_n_cfgpreds(n);
368 for (i = 0; i < arity; i++) {
369 ir_node *pred = get_Block_cfgpred_block(n, i);
370 /* ignore Bad control flow: it cannot happen */
373 if (is_backedge(n, i) || !irn_is_in_stack(pred))
375 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
377 min = get_irn_dfn(pred);
384 * Returns index of the predecessor with the largest dfn number.
386 static int largest_dfn_pred(ir_node *n)
388 int i, index = -2, max = -1;
390 int arity = get_Block_n_cfgpreds(n);
391 for (i = 0; i < arity; i++) {
392 ir_node *pred = get_Block_cfgpred_block(n, i);
393 /* ignore Bad control flow: it cannot happen */
396 if (is_backedge(n, i) || !irn_is_in_stack(pred))
398 if (get_irn_dfn(pred) > max) {
400 max = get_irn_dfn(pred);
407 * Searches the stack for possible loop heads. Tests these for backedges.
408 * If it finds a head with an unmarked backedge it marks this edge and
409 * returns the tail of the loop.
410 * If it finds no backedge returns NULL.
412 static ir_node *find_tail(ir_node *n)
418 m = stack[tos - 1]; /* tos = top of stack */
420 res_index = smallest_dfn_pred(m, 0);
421 if ((res_index == -2) && /* no smallest dfn pred found. */
427 for (i = tos - 1; i != 0;) {
430 res_index = smallest_dfn_pred(m, get_irn_dfn(m) + 1);
431 if (res_index == -2) /* no smallest dfn pred found. */
432 res_index = largest_dfn_pred(m);
434 if ((m == n) && (res_index == -2)) {
441 /* We should not walk past our selves on the stack: The upcoming nodes
442 are not in this loop. We assume a loop not reachable from Start. */
449 if (i == (size_t)-1) {
450 /* A dead loop not reachable from Start. */
451 for (i = tos - 1; i != 0;) {
453 if (is_endless_head(m, n)) {
454 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
455 if (res_index == -2) /* no smallest dfn pred found. */
456 res_index = largest_dfn_pred(m);
459 if (m == n) break; /* It's not an unreachable loop, either. */
461 //assert(0 && "no head found on stack");
464 assert(res_index > -2);
466 set_backedge(m, res_index);
467 return get_Block_cfgpred_block(m, res_index);
471 * returns non.zero if l is the outermost loop.
473 inline static int is_outermost_loop(ir_loop *l)
475 return l == get_loop_outer_loop(l);
478 /*-----------------------------------------------------------*
479 * The core algorithm. *
480 *-----------------------------------------------------------*/
483 * Walks over all blocks of a graph
485 static void cfscc(ir_node *n)
492 if (irn_visited_else_mark(n)) return;
494 /* Initialize the node */
495 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
496 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
497 set_irn_loop(n, NULL);
501 arity = get_Block_n_cfgpreds(n);
503 for (i = 0; i < arity; i++) {
506 if (is_backedge(n, i))
508 m = get_Block_cfgpred_block(n, i);
509 /* ignore Bad control flow: it cannot happen */
514 if (irn_is_in_stack(m)) {
515 /* Uplink of m is smaller if n->m is a backedge.
516 Propagate the uplink to mark the cfloop. */
517 if (get_irn_uplink(m) < get_irn_uplink(n))
518 set_irn_uplink(n, get_irn_uplink(m));
522 if (get_irn_dfn(n) == get_irn_uplink(n)) {
523 /* This condition holds for
524 1) the node with the incoming backedge.
525 That is: We found a cfloop!
526 2) Straight line code, because no uplink has been propagated, so the
527 uplink still is the same as the dfn.
529 But n might not be a proper cfloop head for the analysis. Proper cfloop
530 heads are Block and Phi nodes. find_tail searches the stack for
531 Block's and Phi's and takes those nodes as cfloop heads for the current
532 cfloop instead and marks the incoming edge as backedge. */
534 ir_node *tail = find_tail(n);
536 /* We have a cfloop, that is no straight line code,
537 because we found a cfloop head!
538 Next actions: Open a new cfloop on the cfloop tree and
539 try to find inner cfloops */
541 /* This is an adaption of the algorithm from fiasco / optscc to
542 * avoid cfloops without Block or Phi as first node. This should
543 * severely reduce the number of evaluations of nodes to detect
544 * a fixpoint in the heap analysis.
545 * Further it avoids cfloops without firm nodes that cause errors
546 * in the heap analyses. */
550 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
558 /* Remove the cfloop from the stack ... */
559 pop_scc_unmark_visit(n);
561 /* The current backedge has been marked, that is temporarily eliminated,
562 by find tail. Start the scc algorithm
563 anew on the subgraph thats left (the current cfloop without the backedge)
564 in order to find more inner cfloops. */
568 assert(irn_visited(n));
572 /* AS: No cfloop head was found, that is we have straight line code.
573 Pop all nodes from the stack to the current cfloop. */
579 void construct_cf_backedges(ir_graph *irg)
582 ir_node *end = get_irg_end(irg);
586 outermost_ir_graph = irg;
589 init_scc(irg, &temp);
592 new_loop(); /* sets current_loop */
593 head_rem = current_loop; /* Just for assertion */
595 inc_irg_visited(irg);
597 /* walk over all blocks of the graph, including keep alives */
598 cfscc(get_irg_end_block(irg));
599 for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
600 ir_node *el = get_End_keepalive(end, i);
605 obstack_free(&temp, NULL);
607 assert(head_rem == current_loop);
608 mature_loops(current_loop, get_irg_obstack(irg));
609 set_irg_loop(irg, current_loop);
610 add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
613 void assure_loopinfo(ir_graph *irg)
615 if (irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO))
617 construct_cf_backedges(irg);