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.
26 #include "irgraph_t.h"
33 #define NO_CFLOOPS_WITHOUT_HEAD 1
35 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
37 static ir_loop *current_loop; /* Current cfloop construction is working
39 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
40 Each cfloop node gets a unique number.
41 What for? ev. remove. @@@ */
42 static int current_dfn = 1; /* Counter to generate depth first numbering
45 static int max_loop_depth = 0;
47 void link_to_reg_end (ir_node *n, void *env);
49 /**********************************************************************/
50 /* Node attributes **/
51 /**********************************************************************/
53 /**********************************************************************/
54 /* Node attributes needed for the construction. **/
55 /**********************************************************************/
57 typedef struct scc_info {
58 bool in_stack; /* Marks whether node is on the stack. */
59 int dfn; /* Depth first search number. */
60 int uplink; /* dfn number of ancestor. */
63 static INLINE scc_info* new_scc_info(void) {
64 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
65 memset (info, 0, sizeof (scc_info));
70 mark_irn_in_stack (ir_node *n) {
71 assert(get_irn_link(n));
72 ((scc_info *)n->link)->in_stack = true;
76 mark_irn_not_in_stack (ir_node *n) {
77 assert(get_irn_link(n));
78 ((scc_info *)n->link)->in_stack = false;
82 irn_is_in_stack (ir_node *n) {
83 assert(get_irn_link(n));
84 return ((scc_info *)n->link)->in_stack;
88 set_irn_uplink (ir_node *n, int uplink) {
89 assert(get_irn_link(n));
90 ((scc_info *)n->link)->uplink = uplink;
94 get_irn_uplink (ir_node *n) {
95 assert(get_irn_link(n));
96 return ((scc_info *)n->link)->uplink;
100 set_irn_dfn (ir_node *n, int dfn) {
101 assert(get_irn_link(n));
102 ((scc_info *)n->link)->dfn = dfn;
106 get_irn_dfn (ir_node *n) {
107 assert(get_irn_link(n));
108 return ((scc_info *)n->link)->dfn;
111 /**********************************************************************/
113 /**********************************************************************/
115 static ir_node **stack = NULL;
116 static int tos = 0; /* top of stack */
118 static INLINE void init_stack(void) {
120 ARR_RESIZE (ir_node *, stack, 1000);
122 stack = NEW_ARR_F (ir_node *, 1000);
131 if (tos == ARR_LEN (stack)) {
132 int nlen = ARR_LEN (stack) * 2;
133 ARR_RESIZE (ir_node *, stack, nlen);
136 mark_irn_in_stack(n);
139 static INLINE ir_node *
142 ir_node *n = stack[--tos];
143 mark_irn_not_in_stack(n);
147 /* The nodes up to n belong to the current loop.
148 Removes them from the stack and adds them to the current loop. */
150 pop_scc_to_loop (ir_node *n)
158 set_irn_dfn(m, loop_node_cnt);
159 add_loop_node(current_loop, m);
160 set_irn_loop(m, current_loop);
161 /* if (m==n) break;*/
165 /* GL ??? my last son is my grandson??? Removes cfloops with no
166 ir_nodes in them. Such loops have only another loop as son. (Why
167 can't they have two loops as sons? Does it never get that far? ) */
168 static void close_loop (ir_loop *l)
170 int last = get_loop_n_elements(l) - 1;
171 loop_element lelement = get_loop_element(l, last);
172 ir_loop *last_son = lelement.son;
174 if (get_kind(last_son) == k_ir_loop &&
175 get_loop_n_elements(last_son) == 1) {
178 lelement = get_loop_element(last_son, 0);
180 if(get_kind(gson) == k_ir_loop) {
181 loop_element new_last_son;
183 gson -> outer_loop = l;
184 new_last_son.son = gson;
185 l -> children[last] = new_last_son;
192 /* Removes and unmarks all nodes up to n from the stack.
193 The nodes must be visited once more to assign them to a scc. */
195 pop_scc_unmark_visit (ir_node *n)
201 set_irn_visited(m, 0);
205 /**********************************************************************/
206 /* The loop datastructure. **/
207 /**********************************************************************/
209 /* Allocates a new loop as son of current_loop. Sets current_loop
210 to the new loop and returns the father. */
211 static ir_loop *new_loop (void) {
212 ir_loop *father, *son;
214 father = current_loop;
216 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
217 memset (son, 0, sizeof (ir_loop));
218 son->kind = k_ir_loop;
219 son->children = NEW_ARR_F (loop_element, 0);
223 son->outer_loop = father;
224 add_loop_son(father, son);
225 son->depth = father->depth+1;
226 if (son->depth > max_loop_depth) max_loop_depth = son->depth;
227 } else { /* The root loop */
228 son->outer_loop = son;
233 son->loop_nr = get_irp_new_node_nr();
241 /**********************************************************************/
242 /* Constructing and destructing the loop/backedge information. **/
243 /**********************************************************************/
245 /* Initialization steps. **********************************************/
248 init_node (ir_node *n, void *env) {
250 set_irn_link (n, new_scc_info());
255 init_scc_common (void) {
262 init_scc (ir_graph *irg) {
264 irg_walk_graph (irg, init_node, NULL, NULL);
270 cg_walk (init_node, NULL, NULL);
272 #if EXPERIMENTAL_CFLOOP_TREE
273 cg_walk (link_to_reg_end, NULL, NULL);
277 /* Condition for breaking the recursion. */
278 static bool is_outermost_StartBlock(ir_node *n) {
279 /* Test whether this is the outermost Start node. If so
280 recursion must end. */
282 if ((get_Block_n_cfgpreds(n) == 1) &&
283 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
284 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
290 /** Returns true if n is a loop header, i.e., it is a Block node
291 * and has predecessors within the cfloop and out of the cfloop.
293 * @param root: only needed for assertion.
296 is_head (ir_node *n, ir_node *root)
299 int some_outof_loop = 0, some_in_loop = 0;
303 if (!is_outermost_StartBlock(n)) {
304 arity = get_irn_arity(n);
305 for (i = 0; i < arity; i++) {
306 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
307 if (is_backedge(n, i)) continue;
308 if (!irn_is_in_stack(pred)) {
311 if (get_irn_uplink(pred) < get_irn_uplink(root)) {
312 DDMN(pred); DDMN(root);
313 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
319 return some_outof_loop && some_in_loop;
323 /* Returns true if n is possible loop head of an endless loop.
324 I.e., it is a Block, Phi or Filter node and has only predecessors
326 @arg root: only needed for assertion. */
328 is_endless_head (ir_node *n, ir_node *root)
331 int some_outof_loop = 0, some_in_loop = 0;
334 /* Test for legal loop header: Block, Phi, ... */
335 if (!is_outermost_StartBlock(n)) {
336 arity = get_irn_arity(n);
337 for (i = 0; i < arity; i++) {
338 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
340 if (is_backedge(n, i)) { continue; }
341 if (!irn_is_in_stack(pred)) {
342 some_outof_loop = 1; //printf(" some out of loop ");
344 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
345 DDMN(pred); DDMN(root);
346 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
352 return !some_outof_loop && some_in_loop;
355 /* Returns index of the predecessor with the smallest dfn number
356 greater-equal than limit. */
358 smallest_dfn_pred (ir_node *n, int limit)
360 int i, index = -2, min = -1;
362 if (!is_outermost_StartBlock(n)) {
363 int arity = get_irn_arity(n);
364 for (i = 0; i < arity; i++) {
365 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
366 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
367 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
369 min = get_irn_dfn(pred);
376 /* Returns index of the predecessor with the largest dfn number. */
378 largest_dfn_pred (ir_node *n)
380 int i, index = -2, max = -1;
382 if (!is_outermost_StartBlock(n)) {
383 int arity = get_irn_arity(n);
384 for (i = 0; i < arity; i++) {
385 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
386 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
387 if (get_irn_dfn(pred) > max) {
389 max = get_irn_dfn(pred);
396 /* Searches the stack for possible loop heads. Tests these for backedges.
397 If it finds a head with an unmarked backedge it marks this edge and
398 returns the tail of the loop.
399 If it finds no backedge returns NULL. */
401 find_tail (ir_node *n) {
403 int i, res_index = -2;
405 m = stack[tos-1]; /* tos = top of stack */
406 if (is_head (m, n)) {
407 res_index = smallest_dfn_pred(m, 0);
408 if ((res_index == -2) && /* no smallest dfn pred found. */
412 if (m == n) return NULL;
413 for (i = tos-2; i >= 0; --i) {
416 if (is_head (m, n)) {
417 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
418 if (res_index == -2) /* no smallest dfn pred found. */
419 res_index = largest_dfn_pred (m);
421 if ((m == n) && (res_index == -2)) {
428 /* We should not walk past our selves on the stack: The upcoming nodes
429 are not in this loop. We assume a loop not reachable from Start. */
439 /* A dead loop not reachable from Start. */
440 for (i = tos-2; i >= 0; --i) {
442 if (is_endless_head (m, n)) {
443 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
444 if (res_index == -2) /* no smallest dfn pred found. */
445 res_index = largest_dfn_pred (m);
448 if (m == n) { break; } /* It's not an unreachable loop, either. */
450 //assert(0 && "no head found on stack");
454 assert (res_index > -2);
456 set_backedge (m, res_index);
457 return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
461 is_outermost_loop(ir_loop *l) {
462 return l == get_loop_outer_loop(l);
465 /*-----------------------------------------------------------*
466 * The core algorithm. *
467 *-----------------------------------------------------------*/
470 static void cfscc (ir_node *n) {
475 if (irn_visited(n)) return;
478 /* Initialize the node */
479 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
480 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
481 set_irn_loop(n, NULL);
485 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
486 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
487 so is_backedge does not access array[-1] but correctly returns false! */
489 if (!is_outermost_StartBlock(n)) {
490 int arity = get_irn_arity(n);
492 for (i = 0; i < arity; i++) {
494 if (is_backedge(n, i)) continue;
495 m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
498 if (irn_is_in_stack(m)) {
499 /* Uplink of m is smaller if n->m is a backedge.
500 Propagate the uplink to mark the cfloop. */
501 if (get_irn_uplink(m) < get_irn_uplink(n))
502 set_irn_uplink(n, get_irn_uplink(m));
507 if (get_irn_dfn(n) == get_irn_uplink(n)) {
508 /* This condition holds for
509 1) the node with the incoming backedge.
510 That is: We found a cfloop!
511 2) Straight line code, because no uplink has been propagated, so the
512 uplink still is the same as the dfn.
514 But n might not be a proper cfloop head for the analysis. Proper cfloop
515 heads are Block and Phi nodes. find_tail searches the stack for
516 Block's and Phi's and takes those nodes as cfloop heads for the current
517 cfloop instead and marks the incoming edge as backedge. */
519 ir_node *tail = find_tail(n);
521 /* We have a cfloop, that is no straight line code,
522 because we found a cfloop head!
523 Next actions: Open a new cfloop on the cfloop tree and
524 try to find inner cfloops */
526 #if NO_CFLOOPS_WITHOUT_HEAD
528 /* This is an adaption of the algorithm from fiasco / optscc to
529 * avoid cfloops without Block or Phi as first node. This should
530 * severely reduce the number of evaluations of nodes to detect
531 * a fixpoint in the heap analysis.
532 * Further it avoids cfloops without firm nodes that cause errors
533 * in the heap analyses. */
537 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
547 ir_loop *l = new_loop();
551 /* Remove the cfloop from the stack ... */
552 pop_scc_unmark_visit (n);
554 /* The current backedge has been marked, that is temporarily eliminated,
555 by find tail. Start the scc algorithm
556 anew on the subgraph thats left (the current cfloop without the backedge)
557 in order to find more inner cfloops. */
561 assert (irn_visited(n));
562 #if NO_CFLOOPS_WITHOUT_HEAD
569 /* AS: No cfloop head was found, that is we have straightline code.
570 Pop all nodes from the stack to the current cfloop. */
576 /* Constructs backedge information for irg. */
577 int construct_cf_backedges(ir_graph *irg) {
578 ir_graph *rem = current_ir_graph;
580 ir_node *end = get_irg_end(irg);
583 assert(!get_interprocedural_view() &&
584 "use construct_ip_backedges");
587 current_ir_graph = irg;
588 outermost_ir_graph = irg;
590 init_scc(current_ir_graph);
593 new_loop(); /* sets current_loop */
594 head_rem = current_loop; /* Just for assertion */
596 inc_irg_visited(current_ir_graph);
598 cfscc(get_irg_end_block(current_ir_graph));
599 for (i = 0; i < get_End_n_keepalives(end); i++) {
600 ir_node *el = get_End_keepalive(end, i);
601 if (is_Block(el)) cfscc(el);
604 assert(head_rem == current_loop);
605 set_irg_loop(current_ir_graph, current_loop);
606 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
607 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
609 current_ir_graph = rem;
610 return max_loop_depth;
614 int construct_ip_cf_backedges (void) {
615 ir_graph *rem = current_ir_graph;
616 int rem_ipv = get_interprocedural_view();
619 assert(get_irp_ip_view_state() == ip_view_valid);
621 outermost_ir_graph = get_irp_main_irg();
626 new_loop(); /* sets current_loop */
627 set_interprocedural_view(true);
629 inc_max_irg_visited();
630 for (i = 0; i < get_irp_n_irgs(); i++)
631 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
633 /** We have to start the walk at the same nodes as cg_walk. **/
634 /* Walk starting at unreachable procedures. Only these
635 * have End blocks visible in interprocedural view. */
636 for (i = 0; i < get_irp_n_irgs(); i++) {
638 current_ir_graph = get_irp_irg(i);
640 sb = get_irg_start_block(current_ir_graph);
642 if ((get_Block_n_cfgpreds(sb) > 1) ||
643 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
645 cfscc(get_irg_end_block(current_ir_graph));
648 /* Check whether we walked all procedures: there could be procedures
649 with cyclic calls but no call from the outside. */
650 for (i = 0; i < get_irp_n_irgs(); i++) {
652 current_ir_graph = get_irp_irg(i);
654 /* Test start block: if inner procedure end and end block are not
655 * visible and therefore not marked. */
656 sb = get_irg_start_block(current_ir_graph);
657 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
660 /* Walk all endless cfloops in inner procedures.
661 * We recognize an inner procedure if the End node is not visited. */
662 for (i = 0; i < get_irp_n_irgs(); i++) {
664 current_ir_graph = get_irp_irg(i);
666 e = get_irg_end(current_ir_graph);
667 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
669 /* Don't visit the End node. */
670 for (j = 0; j < get_End_n_keepalives(e); j++) {
671 ir_node *el = get_End_keepalive(e, j);
672 if (is_Block(el)) cfscc(el);
677 set_irg_loop(outermost_ir_graph, current_loop);
678 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
679 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
681 current_ir_graph = rem;
682 set_interprocedural_view(rem_ipv);
683 return max_loop_depth;
687 static void reset_backedges(ir_node *n) {
688 int rem = get_interprocedural_view();
691 set_interprocedural_view(true);
693 set_interprocedural_view(false);
695 set_interprocedural_view(rem);
698 static void loop_reset_backedges(ir_loop *l) {
700 reset_backedges(get_loop_node(l, 0));
701 for (i = 0; i < get_loop_n_nodes(l); ++i)
702 set_irn_loop(get_loop_node(l, i), NULL);
703 for (i = 0; i < get_loop_n_sons(l); ++i) {
704 loop_reset_backedges(get_loop_son(l, i));
708 /* Removes all cfloop information.
709 Resets all backedges */
710 void free_cfloop_information(ir_graph *irg) {
711 if (get_irg_loop(irg))
712 loop_reset_backedges(get_irg_loop(irg));
713 set_irg_loop(irg, NULL);
714 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
715 /* We cannot free the cfloop nodes, they are on the obstack. */
719 void free_all_cfloop_information (void) {
721 int rem = get_interprocedural_view();
722 set_interprocedural_view(true); /* To visit all filter nodes */
723 for (i = 0; i < get_irp_n_irgs(); i++) {
724 free_cfloop_information(get_irp_irg(i));
726 set_interprocedural_view(rem);