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 void link_to_reg_end (ir_node *n, void *env);
45 /**********************************************************************/
46 /* Node attributes **/
47 /**********************************************************************/
49 /**********************************************************************/
50 /* Node attributes needed for the construction. **/
51 /**********************************************************************/
53 typedef struct scc_info {
54 bool in_stack; /* Marks whether node is on the stack. */
55 int dfn; /* Depth first search number. */
56 int uplink; /* dfn number of ancestor. */
59 static INLINE scc_info* new_scc_info(void) {
60 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
61 memset (info, 0, sizeof (scc_info));
66 mark_irn_in_stack (ir_node *n) {
67 assert(get_irn_link(n));
68 ((scc_info *)n->link)->in_stack = true;
72 mark_irn_not_in_stack (ir_node *n) {
73 assert(get_irn_link(n));
74 ((scc_info *)n->link)->in_stack = false;
78 irn_is_in_stack (ir_node *n) {
79 assert(get_irn_link(n));
80 return ((scc_info *)n->link)->in_stack;
84 set_irn_uplink (ir_node *n, int uplink) {
85 assert(get_irn_link(n));
86 ((scc_info *)n->link)->uplink = uplink;
90 get_irn_uplink (ir_node *n) {
91 assert(get_irn_link(n));
92 return ((scc_info *)n->link)->uplink;
96 set_irn_dfn (ir_node *n, int dfn) {
97 assert(get_irn_link(n));
98 ((scc_info *)n->link)->dfn = dfn;
102 get_irn_dfn (ir_node *n) {
103 assert(get_irn_link(n));
104 return ((scc_info *)n->link)->dfn;
107 /**********************************************************************/
109 /**********************************************************************/
111 static ir_node **stack = NULL;
112 static int tos = 0; /* top of stack */
114 static INLINE void init_stack(void) {
116 ARR_RESIZE (ir_node *, stack, 1000);
118 stack = NEW_ARR_F (ir_node *, 1000);
127 if (tos == ARR_LEN (stack)) {
128 int nlen = ARR_LEN (stack) * 2;
129 ARR_RESIZE (ir_node *, stack, nlen);
132 mark_irn_in_stack(n);
135 static INLINE ir_node *
138 ir_node *n = stack[--tos];
139 mark_irn_not_in_stack(n);
143 /* The nodes up to n belong to the current loop.
144 Removes them from the stack and adds them to the current loop. */
146 pop_scc_to_loop (ir_node *n)
154 set_irn_dfn(m, loop_node_cnt);
155 add_loop_node(current_loop, m);
156 set_irn_loop(m, current_loop);
157 /* if (m==n) break;*/
161 /* GL ??? my last son is my grandson??? Removes cfloops with no
162 ir_nodes in them. Such loops have only another loop as son. (Why
163 can't they have two loops as sons? Does it never get that far? ) */
164 static void close_loop (ir_loop *l)
166 int last = get_loop_n_elements(l) - 1;
167 loop_element lelement = get_loop_element(l, last);
168 ir_loop *last_son = lelement.son;
170 if (get_kind(last_son) == k_ir_loop &&
171 get_loop_n_elements(last_son) == 1) {
174 lelement = get_loop_element(last_son, 0);
176 if(get_kind(gson) == k_ir_loop) {
177 loop_element new_last_son;
179 gson -> outer_loop = l;
180 new_last_son.son = gson;
181 l -> children[last] = new_last_son;
188 /* Removes and unmarks all nodes up to n from the stack.
189 The nodes must be visited once more to assign them to a scc. */
191 pop_scc_unmark_visit (ir_node *n)
197 set_irn_visited(m, 0);
201 /**********************************************************************/
202 /* The loop datastructure. **/
203 /**********************************************************************/
205 /* Allocates a new loop as son of current_loop. Sets current_loop
206 to the new loop and returns the father. */
207 static ir_loop *new_loop (void) {
208 ir_loop *father, *son;
210 father = current_loop;
212 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
213 memset (son, 0, sizeof (ir_loop));
214 son->kind = k_ir_loop;
215 son->children = NEW_ARR_F (loop_element, 0);
219 son->outer_loop = father;
220 add_loop_son(father, son);
221 son->depth = father->depth+1;
222 } else { /* The root loop */
223 son->outer_loop = son;
228 son->loop_nr = get_irp_new_node_nr();
236 /**********************************************************************/
237 /* Constructing and destructing the loop/backedge information. **/
238 /**********************************************************************/
240 /* Initialization steps. **********************************************/
243 init_node (ir_node *n, void *env) {
245 set_irn_link (n, new_scc_info());
250 init_scc_common (void) {
257 init_scc (ir_graph *irg) {
259 irg_walk_graph (irg, init_node, NULL, NULL);
265 cg_walk (init_node, NULL, NULL);
267 #if EXPERIMENTAL_CFLOOP_TREE
268 cg_walk (link_to_reg_end, NULL, NULL);
272 /* Condition for breaking the recursion. */
273 static bool is_outermost_StartBlock(ir_node *n) {
274 /* Test whether this is the outermost Start node. If so
275 recursion must end. */
277 if ((get_Block_n_cfgpreds(n) == 1) &&
278 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
279 (get_nodes_block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
285 /** Returns true if n is a loop header, i.e., it is a Block node
286 * and has predecessors within the cfloop and out of the cfloop.
288 * @param root: only needed for assertion.
291 is_head (ir_node *n, ir_node *root)
294 int some_outof_loop = 0, some_in_loop = 0;
298 if (!is_outermost_StartBlock(n)) {
299 arity = get_irn_arity(n);
300 for (i = 0; i < arity; i++) {
301 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
302 if (is_backedge(n, i)) continue;
303 if (!irn_is_in_stack(pred)) {
306 if (get_irn_uplink(pred) < get_irn_uplink(root)) {
307 DDMN(pred); DDMN(root);
308 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
314 return some_outof_loop && some_in_loop;
318 /* Returns true if n is possible loop head of an endless loop.
319 I.e., it is a Block, Phi or Filter node and has only predecessors
321 @arg root: only needed for assertion. */
323 is_endless_head (ir_node *n, ir_node *root)
326 int some_outof_loop = 0, some_in_loop = 0;
329 /* Test for legal loop header: Block, Phi, ... */
330 if (!is_outermost_StartBlock(n)) {
331 arity = get_irn_arity(n);
332 for (i = 0; i < arity; i++) {
333 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
335 if (is_backedge(n, i)) { continue; }
336 if (!irn_is_in_stack(pred)) {
337 some_outof_loop = 1; //printf(" some out of loop ");
339 if(get_irn_uplink(pred) < get_irn_uplink(root)) {
340 DDMN(pred); DDMN(root);
341 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
347 return !some_outof_loop && some_in_loop;
350 /* Returns index of the predecessor with the smallest dfn number
351 greater-equal than limit. */
353 smallest_dfn_pred (ir_node *n, int limit)
355 int i, index = -2, min = -1;
357 if (!is_outermost_StartBlock(n)) {
358 int arity = get_irn_arity(n);
359 for (i = 0; i < arity; i++) {
360 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
361 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
362 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
364 min = get_irn_dfn(pred);
371 /* Returns index of the predecessor with the largest dfn number. */
373 largest_dfn_pred (ir_node *n)
375 int i, index = -2, max = -1;
377 if (!is_outermost_StartBlock(n)) {
378 int arity = get_irn_arity(n);
379 for (i = 0; i < arity; i++) {
380 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
381 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
382 if (get_irn_dfn(pred) > max) {
384 max = get_irn_dfn(pred);
391 /* Searches the stack for possible loop heads. Tests these for backedges.
392 If it finds a head with an unmarked backedge it marks this edge and
393 returns the tail of the loop.
394 If it finds no backedge returns NULL. */
396 find_tail (ir_node *n) {
398 int i, res_index = -2;
400 m = stack[tos-1]; /* tos = top of stack */
401 if (is_head (m, n)) {
402 res_index = smallest_dfn_pred(m, 0);
403 if ((res_index == -2) && /* no smallest dfn pred found. */
407 if (m == n) return NULL;
408 for (i = tos-2; i >= 0; --i) {
411 if (is_head (m, n)) {
412 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
413 if (res_index == -2) /* no smallest dfn pred found. */
414 res_index = largest_dfn_pred (m);
416 if ((m == n) && (res_index == -2)) {
423 /* We should not walk past our selves on the stack: The upcoming nodes
424 are not in this loop. We assume a loop not reachable from Start. */
434 /* A dead loop not reachable from Start. */
435 for (i = tos-2; i >= 0; --i) {
437 if (is_endless_head (m, n)) {
438 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
439 if (res_index == -2) /* no smallest dfn pred found. */
440 res_index = largest_dfn_pred (m);
443 if (m == n) { break; } /* It's not an unreachable loop, either. */
445 //assert(0 && "no head found on stack");
449 assert (res_index > -2);
451 set_backedge (m, res_index);
452 return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
456 is_outermost_loop(ir_loop *l) {
457 return l == get_loop_outer_loop(l);
460 /*-----------------------------------------------------------*
461 * The core algorithm. *
462 *-----------------------------------------------------------*/
465 static void cfscc (ir_node *n) {
470 if (irn_visited(n)) return;
473 /* Initialize the node */
474 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
475 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
476 set_irn_loop(n, NULL);
480 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
481 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
482 so is_backedge does not access array[-1] but correctly returns false! */
484 if (!is_outermost_StartBlock(n)) {
485 int arity = get_irn_arity(n);
487 for (i = 0; i < arity; i++) {
489 if (is_backedge(n, i)) continue;
490 m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
493 if (irn_is_in_stack(m)) {
494 /* Uplink of m is smaller if n->m is a backedge.
495 Propagate the uplink to mark the cfloop. */
496 if (get_irn_uplink(m) < get_irn_uplink(n))
497 set_irn_uplink(n, get_irn_uplink(m));
502 if (get_irn_dfn(n) == get_irn_uplink(n)) {
503 /* This condition holds for
504 1) the node with the incoming backedge.
505 That is: We found a cfloop!
506 2) Straight line code, because no uplink has been propagated, so the
507 uplink still is the same as the dfn.
509 But n might not be a proper cfloop head for the analysis. Proper cfloop
510 heads are Block and Phi nodes. find_tail searches the stack for
511 Block's and Phi's and takes those nodes as cfloop heads for the current
512 cfloop instead and marks the incoming edge as backedge. */
514 ir_node *tail = find_tail(n);
516 /* We have a cfloop, that is no straight line code,
517 because we found a cfloop head!
518 Next actions: Open a new cfloop on the cfloop tree and
519 try to find inner cfloops */
521 #if NO_CFLOOPS_WITHOUT_HEAD
523 /* This is an adaption of the algorithm from fiasco / optscc to
524 * avoid cfloops without Block or Phi as first node. This should
525 * severely reduce the number of evaluations of nodes to detect
526 * a fixpoint in the heap analysis.
527 * Further it avoids cfloops without firm nodes that cause errors
528 * in the heap analyses. */
532 if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
542 ir_loop *l = new_loop();
546 /* Remove the cfloop from the stack ... */
547 pop_scc_unmark_visit (n);
549 /* The current backedge has been marked, that is temporarily eliminated,
550 by find tail. Start the scc algorithm
551 anew on the subgraph thats left (the current cfloop without the backedge)
552 in order to find more inner cfloops. */
556 assert (irn_visited(n));
557 #if NO_CFLOOPS_WITHOUT_HEAD
564 /* AS: No cfloop head was found, that is we have straightline code.
565 Pop all nodes from the stack to the current cfloop. */
571 /* Constructs backedge information for irg. */
572 void construct_cf_backedges(ir_graph *irg) {
573 ir_graph *rem = current_ir_graph;
575 ir_node *end = get_irg_end(irg);
578 assert(!interprocedural_view &&
579 "use construct_ip_backedges");
581 current_ir_graph = irg;
582 outermost_ir_graph = irg;
584 init_scc(current_ir_graph);
587 new_loop(); /* sets current_loop */
588 head_rem = current_loop; /* Just for assertion */
590 inc_irg_visited(current_ir_graph);
592 cfscc(get_irg_end_block(current_ir_graph));
593 for (i = 0; i < get_End_n_keepalives(end); i++) {
594 ir_node *el = get_End_keepalive(end, i);
595 if (is_Block(el)) cfscc(el);
598 assert(head_rem == current_loop);
599 set_irg_loop(current_ir_graph, current_loop);
600 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
601 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
603 current_ir_graph = rem;
607 void construct_ip_cf_backedges (void) {
608 ir_graph *rem = current_ir_graph;
609 int rem_ipv = interprocedural_view;
612 assert(get_irp_ip_view_state() == ip_view_valid);
614 outermost_ir_graph = get_irp_main_irg();
619 new_loop(); /* sets current_loop */
620 interprocedural_view = 1;
622 inc_max_irg_visited();
623 for (i = 0; i < get_irp_n_irgs(); i++)
624 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
626 /** We have to start the walk at the same nodes as cg_walk. **/
627 /* Walk starting at unreachable procedures. Only these
628 * have End blocks visible in interprocedural view. */
629 for (i = 0; i < get_irp_n_irgs(); i++) {
631 current_ir_graph = get_irp_irg(i);
633 sb = get_irg_start_block(current_ir_graph);
635 if ((get_Block_n_cfgpreds(sb) > 1) ||
636 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
638 cfscc(get_irg_end_block(current_ir_graph));
641 /* Check whether we walked all procedures: there could be procedures
642 with cyclic calls but no call from the outside. */
643 for (i = 0; i < get_irp_n_irgs(); i++) {
645 current_ir_graph = get_irp_irg(i);
647 /* Test start block: if inner procedure end and end block are not
648 * visible and therefore not marked. */
649 sb = get_irg_start_block(current_ir_graph);
650 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
653 /* Walk all endless cfloops in inner procedures.
654 * We recognize an inner procedure if the End node is not visited. */
655 for (i = 0; i < get_irp_n_irgs(); i++) {
657 current_ir_graph = get_irp_irg(i);
659 e = get_irg_end(current_ir_graph);
660 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
662 /* Don't visit the End node. */
663 for (j = 0; j < get_End_n_keepalives(e); j++) {
664 ir_node *el = get_End_keepalive(e, j);
665 if (is_Block(el)) cfscc(el);
670 set_irg_loop(outermost_ir_graph, current_loop);
671 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
672 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
674 current_ir_graph = rem;
675 interprocedural_view = rem_ipv;
679 static void reset_backedges(ir_node *n) {
681 int rem = interprocedural_view;
682 interprocedural_view = 1;
684 interprocedural_view = 0;
686 interprocedural_view = rem;
689 static void loop_reset_backedges(ir_loop *l) {
691 reset_backedges(get_loop_node(l, 0));
692 for (i = 0; i < get_loop_n_nodes(l); ++i)
693 set_irn_loop(get_loop_node(l, i), NULL);
694 for (i = 0; i < get_loop_n_sons(l); ++i) {
695 loop_reset_backedges(get_loop_son(l, i));
699 /* Removes all cfloop information.
700 Resets all backedges */
701 void free_cfloop_information(ir_graph *irg) {
702 if (get_irg_loop(irg))
703 loop_reset_backedges(get_irg_loop(irg));
704 set_irg_loop(irg, NULL);
705 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
706 /* We cannot free the cfloop nodes, they are on the obstack. */
710 void free_all_cfloop_information (void) {
712 int rem = interprocedural_view;
713 interprocedural_view = 1; /* To visit all filter nodes */
714 for (i = 0; i < get_irp_n_irgs(); i++) {
715 free_cfloop_information(get_irp_irg(i));
717 interprocedural_view = rem;