3 * File name: ir/ana/irscc.c
4 * Purpose: Compute the strongly connected regions and build
5 * backedge/cfloop 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 #define NO_CFLOOPS_WITHOUT_HEAD 1
33 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
35 static ir_loop *current_loop; /* Current cfloop construction is working
37 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
38 Each cfloop node gets a unique number.
39 What for? ev. remove. @@@ */
40 static int current_dfn = 1; /* Counter to generate depth first numbering
43 static int max_loop_depth = 0;
45 void link_to_reg_end (ir_node *n, void *env);
47 /**********************************************************************/
48 /* Node attributes **/
49 /**********************************************************************/
51 /**********************************************************************/
52 /* Node attributes needed for the construction. **/
53 /**********************************************************************/
55 typedef struct scc_info {
56 bool in_stack; /* Marks whether node is on the stack. */
57 int dfn; /* Depth first search number. */
58 int uplink; /* dfn number of ancestor. */
61 static INLINE scc_info* new_scc_info(void) {
62 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
63 memset (info, 0, sizeof (scc_info));
68 mark_irn_in_stack (ir_node *n) {
69 assert(get_irn_link(n));
70 ((scc_info *)n->link)->in_stack = true;
74 mark_irn_not_in_stack (ir_node *n) {
75 assert(get_irn_link(n));
76 ((scc_info *)n->link)->in_stack = false;
80 irn_is_in_stack (ir_node *n) {
81 assert(get_irn_link(n));
82 return ((scc_info *)n->link)->in_stack;
86 set_irn_uplink (ir_node *n, int uplink) {
87 assert(get_irn_link(n));
88 ((scc_info *)n->link)->uplink = uplink;
92 get_irn_uplink (ir_node *n) {
93 assert(get_irn_link(n));
94 return ((scc_info *)n->link)->uplink;
98 set_irn_dfn (ir_node *n, int dfn) {
99 assert(get_irn_link(n));
100 ((scc_info *)n->link)->dfn = dfn;
104 get_irn_dfn (ir_node *n) {
105 assert(get_irn_link(n));
106 return ((scc_info *)n->link)->dfn;
109 /**********************************************************************/
111 /**********************************************************************/
113 static ir_node **stack = NULL;
114 static int tos = 0; /* top of stack */
116 static INLINE void init_stack(void) {
118 ARR_RESIZE (ir_node *, stack, 1000);
120 stack = NEW_ARR_F (ir_node *, 1000);
129 if (tos == ARR_LEN (stack)) {
130 int nlen = ARR_LEN (stack) * 2;
131 ARR_RESIZE (ir_node *, stack, nlen);
134 mark_irn_in_stack(n);
137 static INLINE ir_node *
140 ir_node *n = stack[--tos];
141 mark_irn_not_in_stack(n);
145 /* The nodes up to n belong to the current loop.
146 Removes them from the stack and adds them to the current loop. */
148 pop_scc_to_loop (ir_node *n)
156 set_irn_dfn(m, loop_node_cnt);
157 add_loop_node(current_loop, m);
158 set_irn_loop(m, current_loop);
159 /* if (m==n) break;*/
163 /* GL ??? my last son is my grandson??? Removes cfloops with no
164 ir_nodes in them. Such loops have only another loop as son. (Why
165 can't they have two loops as sons? Does it never get that far? ) */
166 static void close_loop (ir_loop *l)
168 int last = get_loop_n_elements(l) - 1;
169 loop_element lelement = get_loop_element(l, last);
170 ir_loop *last_son = lelement.son;
172 if (get_kind(last_son) == k_ir_loop &&
173 get_loop_n_elements(last_son) == 1) {
176 lelement = get_loop_element(last_son, 0);
178 if(get_kind(gson) == k_ir_loop) {
179 loop_element new_last_son;
181 gson -> outer_loop = l;
182 new_last_son.son = gson;
183 l -> children[last] = new_last_son;
190 /* Removes and unmarks all nodes up to n from the stack.
191 The nodes must be visited once more to assign them to a scc. */
193 pop_scc_unmark_visit (ir_node *n)
199 set_irn_visited(m, 0);
203 /**********************************************************************/
204 /* The loop datastructure. **/
205 /**********************************************************************/
207 /* Allocates a new loop as son of current_loop. Sets current_loop
208 to the new loop and returns the father. */
209 static ir_loop *new_loop (void) {
210 ir_loop *father, *son;
212 father = current_loop;
214 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
215 memset (son, 0, sizeof (ir_loop));
216 son->kind = k_ir_loop;
217 son->children = NEW_ARR_F (loop_element, 0);
221 son->outer_loop = father;
222 add_loop_son(father, son);
223 son->depth = father->depth+1;
224 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
225 } else { /* The root loop */
226 son->outer_loop = son;
231 son->loop_nr = get_irp_new_node_nr();
239 /**********************************************************************/
240 /* Constructing and destructing the loop/backedge information. **/
241 /**********************************************************************/
243 /* Initialization steps. **********************************************/
246 init_node (ir_node *n, void *env) {
248 set_irn_link (n, new_scc_info());
253 init_scc_common (void) {
260 init_scc (ir_graph *irg) {
262 irg_walk_graph (irg, init_node, NULL, NULL);
268 cg_walk (init_node, NULL, NULL);
270 #if EXPERIMENTAL_CFLOOP_TREE
271 cg_walk (link_to_reg_end, NULL, NULL);
275 /* Condition for breaking the recursion. */
276 static bool is_outermost_StartBlock(ir_node *n) {
277 /* Test whether this is the outermost Start node. If so
278 recursion must end. */
280 if ((get_Block_n_cfgpreds(n) == 1) &&
281 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
282 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
288 /** Returns true if n is a loop header, i.e., it is a Block node
289 * and has predecessors within the cfloop and out of the cfloop.
291 * @param root: only needed for assertion.
294 is_head (ir_node *n, ir_node *root)
297 int some_outof_loop = 0, some_in_loop = 0;
301 if (!is_outermost_StartBlock(n)) {
302 arity = get_irn_arity(n);
303 for (i = 0; i < arity; i++) {
304 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
305 if (is_backedge(n, i)) continue;
306 if (!irn_is_in_stack(pred)) {
309 if (get_irn_uplink(pred) < get_irn_uplink(root)) {
310 DDMN(pred); DDMN(root);
311 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
317 return some_outof_loop && some_in_loop;
321 /* Returns true if n is possible loop head of an endless loop.
322 I.e., it is a Block, Phi or Filter node and has only predecessors
324 @arg root: only needed for assertion. */
326 is_endless_head (ir_node *n, ir_node *root)
329 int some_outof_loop = 0, some_in_loop = 0;
332 /* Test for legal loop header: Block, Phi, ... */
333 if (!is_outermost_StartBlock(n)) {
334 arity = get_irn_arity(n);
335 for (i = 0; i < arity; i++) {
336 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
338 if (is_backedge(n, i)) { continue; }
339 if (!irn_is_in_stack(pred)) {
340 some_outof_loop = 1; //printf(" some out of loop ");
342 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
343 DDMN(pred); DDMN(root);
344 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
350 return !some_outof_loop && some_in_loop;
353 /* Returns index of the predecessor with the smallest dfn number
354 greater-equal than limit. */
356 smallest_dfn_pred (ir_node *n, int limit)
358 int i, index = -2, min = -1;
360 if (!is_outermost_StartBlock(n)) {
361 int arity = get_irn_arity(n);
362 for (i = 0; i < arity; i++) {
363 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
364 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
365 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
367 min = get_irn_dfn(pred);
374 /* Returns index of the predecessor with the largest dfn number. */
376 largest_dfn_pred (ir_node *n)
378 int i, index = -2, max = -1;
380 if (!is_outermost_StartBlock(n)) {
381 int arity = get_irn_arity(n);
382 for (i = 0; i < arity; i++) {
383 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
384 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
385 if (get_irn_dfn(pred) > max) {
387 max = get_irn_dfn(pred);
394 /* Searches the stack for possible loop heads. Tests these for backedges.
395 If it finds a head with an unmarked backedge it marks this edge and
396 returns the tail of the loop.
397 If it finds no backedge returns NULL. */
399 find_tail (ir_node *n) {
401 int i, res_index = -2;
403 m = stack[tos-1]; /* tos = top of stack */
404 if (is_head (m, n)) {
405 res_index = smallest_dfn_pred(m, 0);
406 if ((res_index == -2) && /* no smallest dfn pred found. */
410 if (m == n) return NULL;
411 for (i = tos-2; i >= 0; --i) {
414 if (is_head (m, n)) {
415 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
416 if (res_index == -2) /* no smallest dfn pred found. */
417 res_index = largest_dfn_pred (m);
419 if ((m == n) && (res_index == -2)) {
426 /* We should not walk past our selves on the stack: The upcoming nodes
427 are not in this loop. We assume a loop not reachable from Start. */
437 /* A dead loop not reachable from Start. */
438 for (i = tos-2; i >= 0; --i) {
440 if (is_endless_head (m, n)) {
441 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
442 if (res_index == -2) /* no smallest dfn pred found. */
443 res_index = largest_dfn_pred (m);
446 if (m == n) { break; } /* It's not an unreachable loop, either. */
448 //assert(0 && "no head found on stack");
452 assert (res_index > -2);
454 set_backedge (m, res_index);
455 return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
459 is_outermost_loop(ir_loop *l) {
460 return l == get_loop_outer_loop(l);
463 /*-----------------------------------------------------------*
464 * The core algorithm. *
465 *-----------------------------------------------------------*/
468 static void cfscc (ir_node *n) {
473 if (irn_visited(n)) return;
476 /* Initialize the node */
477 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
478 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
479 set_irn_loop(n, NULL);
483 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
484 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
485 so is_backedge does not access array[-1] but correctly returns false! */
487 if (!is_outermost_StartBlock(n)) {
488 int arity = get_irn_arity(n);
490 for (i = 0; i < arity; i++) {
492 if (is_backedge(n, i)) continue;
493 m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
496 if (irn_is_in_stack(m)) {
497 /* Uplink of m is smaller if n->m is a backedge.
498 Propagate the uplink to mark the cfloop. */
499 if (get_irn_uplink(m) < get_irn_uplink(n))
500 set_irn_uplink(n, get_irn_uplink(m));
505 if (get_irn_dfn(n) == get_irn_uplink(n)) {
506 /* This condition holds for
507 1) the node with the incoming backedge.
508 That is: We found a cfloop!
509 2) Straight line code, because no uplink has been propagated, so the
510 uplink still is the same as the dfn.
512 But n might not be a proper cfloop head for the analysis. Proper cfloop
513 heads are Block and Phi nodes. find_tail searches the stack for
514 Block's and Phi's and takes those nodes as cfloop heads for the current
515 cfloop instead and marks the incoming edge as backedge. */
517 ir_node *tail = find_tail(n);
519 /* We have a cfloop, that is no straight line code,
520 because we found a cfloop head!
521 Next actions: Open a new cfloop on the cfloop tree and
522 try to find inner cfloops */
524 #if NO_CFLOOPS_WITHOUT_HEAD
526 /* This is an adaption of the algorithm from fiasco / optscc to
527 * avoid cfloops without Block or Phi as first node. This should
528 * severely reduce the number of evaluations of nodes to detect
529 * a fixpoint in the heap analysis.
530 * Further it avoids cfloops without firm nodes that cause errors
531 * in the heap analyses. */
535 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
545 ir_loop *l = new_loop();
549 /* Remove the cfloop from the stack ... */
550 pop_scc_unmark_visit (n);
552 /* The current backedge has been marked, that is temporarily eliminated,
553 by find tail. Start the scc algorithm
554 anew on the subgraph thats left (the current cfloop without the backedge)
555 in order to find more inner cfloops. */
559 assert (irn_visited(n));
560 #if NO_CFLOOPS_WITHOUT_HEAD
567 /* AS: No cfloop head was found, that is we have straightline code.
568 Pop all nodes from the stack to the current cfloop. */
574 /* Constructs backedge information for irg. */
575 int construct_cf_backedges(ir_graph *irg) {
576 ir_graph *rem = current_ir_graph;
578 ir_node *end = get_irg_end(irg);
581 assert(!get_interprocedural_view() &&
582 "use construct_ip_backedges");
585 current_ir_graph = irg;
586 outermost_ir_graph = irg;
588 init_scc(current_ir_graph);
591 new_loop(); /* sets current_loop */
592 head_rem = current_loop; /* Just for assertion */
594 inc_irg_visited(current_ir_graph);
596 cfscc(get_irg_end_block(current_ir_graph));
597 for (i = 0; i < get_End_n_keepalives(end); i++) {
598 ir_node *el = get_End_keepalive(end, i);
599 if (is_Block(el)) cfscc(el);
602 assert(head_rem == current_loop);
603 set_irg_loop(current_ir_graph, current_loop);
604 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
605 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
607 current_ir_graph = rem;
608 return max_loop_depth;
612 int construct_ip_cf_backedges (void) {
613 ir_graph *rem = current_ir_graph;
614 int rem_ipv = get_interprocedural_view();
617 assert(get_irp_ip_view_state() == ip_view_valid);
619 outermost_ir_graph = get_irp_main_irg();
624 new_loop(); /* sets current_loop */
625 set_interprocedural_view(true);
627 inc_max_irg_visited();
628 for (i = 0; i < get_irp_n_irgs(); i++)
629 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
631 /** We have to start the walk at the same nodes as cg_walk. **/
632 /* Walk starting at unreachable procedures. Only these
633 * have End blocks visible in interprocedural view. */
634 for (i = 0; i < get_irp_n_irgs(); i++) {
636 current_ir_graph = get_irp_irg(i);
638 sb = get_irg_start_block(current_ir_graph);
640 if ((get_Block_n_cfgpreds(sb) > 1) ||
641 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
643 cfscc(get_irg_end_block(current_ir_graph));
646 /* Check whether we walked all procedures: there could be procedures
647 with cyclic calls but no call from the outside. */
648 for (i = 0; i < get_irp_n_irgs(); i++) {
650 current_ir_graph = get_irp_irg(i);
652 /* Test start block: if inner procedure end and end block are not
653 * visible and therefore not marked. */
654 sb = get_irg_start_block(current_ir_graph);
655 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
658 /* Walk all endless cfloops in inner procedures.
659 * We recognize an inner procedure if the End node is not visited. */
660 for (i = 0; i < get_irp_n_irgs(); i++) {
662 current_ir_graph = get_irp_irg(i);
664 e = get_irg_end(current_ir_graph);
665 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
667 /* Don't visit the End node. */
668 for (j = 0; j < get_End_n_keepalives(e); j++) {
669 ir_node *el = get_End_keepalive(e, j);
670 if (is_Block(el)) cfscc(el);
675 set_irg_loop(outermost_ir_graph, current_loop);
676 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
677 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
679 current_ir_graph = rem;
680 set_interprocedural_view(rem_ipv);
681 return max_loop_depth;
685 static void reset_backedges(ir_node *n) {
687 int rem = get_interprocedural_view();
688 set_interprocedural_view(true);
690 set_interprocedural_view(false);
692 set_interprocedural_view(rem);
695 static void loop_reset_backedges(ir_loop *l) {
697 reset_backedges(get_loop_node(l, 0));
698 for (i = 0; i < get_loop_n_nodes(l); ++i)
699 set_irn_loop(get_loop_node(l, i), NULL);
700 for (i = 0; i < get_loop_n_sons(l); ++i) {
701 loop_reset_backedges(get_loop_son(l, i));
705 /* Removes all cfloop information.
706 Resets all backedges */
707 void free_cfloop_information(ir_graph *irg) {
708 if (get_irg_loop(irg))
709 loop_reset_backedges(get_irg_loop(irg));
710 set_irg_loop(irg, NULL);
711 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
712 /* We cannot free the cfloop nodes, they are on the obstack. */
716 void free_all_cfloop_information (void) {
718 int rem = get_interprocedural_view();
719 set_interprocedural_view(true); /* To visit all filter nodes */
720 for (i = 0; i < get_irp_n_irgs(); i++) {
721 free_cfloop_information(get_irp_irg(i));
723 set_interprocedural_view(rem);