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 static ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
33 static ir_loop *current_loop; /* Current cfloop construction is working
35 static int loop_node_cnt = 0; /* Counts the number of allocated cfloop nodes.
36 Each cfloop node gets a unique number.
37 What for? ev. remove. @@@ */
38 static int current_dfn = 1; /* Counter to generate depth first numbering
41 void link_to_reg_end (ir_node *n, void *env);
43 /**********************************************************************/
44 /* Node attributes **/
45 /**********************************************************************/
47 /**********************************************************************/
48 /* Node attributes needed for the construction. **/
49 /**********************************************************************/
51 typedef struct scc_info {
52 bool in_stack; /* Marks whether node is on the stack. */
53 int dfn; /* Depth first search number. */
54 int uplink; /* dfn number of ancestor. */
57 static INLINE scc_info* new_scc_info(void) {
58 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
59 memset (info, 0, sizeof (scc_info));
64 mark_irn_in_stack (ir_node *n) {
65 assert(get_irn_link(n));
66 ((scc_info *)n->link)->in_stack = true;
70 mark_irn_not_in_stack (ir_node *n) {
71 assert(get_irn_link(n));
72 ((scc_info *)n->link)->in_stack = false;
76 irn_is_in_stack (ir_node *n) {
77 assert(get_irn_link(n));
78 return ((scc_info *)n->link)->in_stack;
82 set_irn_uplink (ir_node *n, int uplink) {
83 assert(get_irn_link(n));
84 ((scc_info *)n->link)->uplink = uplink;
88 get_irn_uplink (ir_node *n) {
89 assert(get_irn_link(n));
90 return ((scc_info *)n->link)->uplink;
94 set_irn_dfn (ir_node *n, int dfn) {
95 assert(get_irn_link(n));
96 ((scc_info *)n->link)->dfn = dfn;
100 get_irn_dfn (ir_node *n) {
101 assert(get_irn_link(n));
102 return ((scc_info *)n->link)->dfn;
105 /**********************************************************************/
107 /**********************************************************************/
109 static ir_node **stack = NULL;
110 static int tos = 0; /* top of stack */
112 static INLINE void init_stack(void) {
114 ARR_RESIZE (ir_node *, stack, 1000);
116 stack = NEW_ARR_F (ir_node *, 1000);
125 if (tos == ARR_LEN (stack)) {
126 int nlen = ARR_LEN (stack) * 2;
127 ARR_RESIZE (ir_node *, stack, nlen);
130 mark_irn_in_stack(n);
133 static INLINE ir_node *
136 ir_node *n = stack[--tos];
137 mark_irn_not_in_stack(n);
141 /* The nodes up to n belong to the current loop.
142 Removes them from the stack and adds them to the current loop. */
144 pop_scc_to_loop (ir_node *n)
152 set_irn_dfn(m, loop_node_cnt);
153 add_loop_node(current_loop, m);
154 set_irn_loop(m, current_loop);
155 /* if (m==n) break;*/
159 /* GL ??? my last son is my grandson??? Removes cfloops with no
160 ir_nodes in them. Such loops have only another loop as son. (Why
161 can't they have two loops as sons? Does it never get that far? ) */
162 static void close_loop (ir_loop *l)
164 int last = get_loop_n_elements(l) - 1;
165 loop_element lelement = get_loop_element(l, last);
166 ir_loop *last_son = lelement.son;
168 if (get_kind(last_son) == k_ir_loop &&
169 get_loop_n_elements(last_son) == 1) {
172 lelement = get_loop_element(last_son, 0);
174 if(get_kind(gson) == k_ir_loop) {
175 loop_element new_last_son;
177 gson -> outer_loop = l;
178 new_last_son.son = gson;
179 l -> children[last] = new_last_son;
186 /* Removes and unmarks all nodes up to n from the stack.
187 The nodes must be visited once more to assign them to a scc. */
189 pop_scc_unmark_visit (ir_node *n)
195 set_irn_visited(m, 0);
199 /**********************************************************************/
200 /* The loop datastructure. **/
201 /**********************************************************************/
203 /* Allocates a new loop as son of current_loop. Sets current_loop
204 to the new loop and returns the father. */
205 static ir_loop *new_loop (void) {
206 ir_loop *father, *son;
208 father = current_loop;
210 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
211 memset (son, 0, sizeof (ir_loop));
212 son->kind = k_ir_loop;
213 son->children = NEW_ARR_F (loop_element, 0);
217 son->outer_loop = father;
218 add_loop_son(father, son);
219 son->depth = father->depth+1;
220 } else { /* The root loop */
221 son->outer_loop = son;
226 son->loop_nr = get_irp_new_node_nr();
234 /**********************************************************************/
235 /* Constructing and destructing the loop/backedge information. **/
236 /**********************************************************************/
238 /* Initialization steps. **********************************************/
241 init_node (ir_node *n, void *env) {
243 set_irn_link (n, new_scc_info());
248 init_scc_common (void) {
255 init_scc (ir_graph *irg) {
257 irg_walk_graph (irg, init_node, NULL, NULL);
263 cg_walk (init_node, NULL, NULL);
265 #if EXPERIMENTAL_CFLOOP_TREE
266 cg_walk (link_to_reg_end, NULL, NULL);
270 /* Condition for breaking the recursion. */
271 static bool is_outermost_StartBlock(ir_node *n) {
272 /* Test whether this is the outermost Start node. If so
273 recursion must end. */
275 if ((get_Block_n_cfgpreds(n) == 1) &&
276 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
277 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
283 /** Returns true if n is a loop header, i.e., it is a Block node
284 * and has predecessors within the cfloop and out of the cfloop.
286 * @param root: only needed for assertion.
289 is_head (ir_node *n, ir_node *root)
292 int some_outof_loop = 0, some_in_loop = 0;
296 if (!is_outermost_StartBlock(n)) {
297 arity = get_irn_arity(n);
298 for (i = 0; i < arity; i++) {
299 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
300 if (is_backedge(n, i)) continue;
301 if (!irn_is_in_stack(pred)) {
304 if (get_irn_uplink(pred) < get_irn_uplink(root)) {
305 DDMN(pred); DDMN(root);
306 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
312 return some_outof_loop && some_in_loop;
315 /* Returns index of the predecessor with the smallest dfn number
316 greater-equal than limit. */
318 smallest_dfn_pred (ir_node *n, int limit)
320 int i, index = -2, min = -1;
322 if (!is_outermost_StartBlock(n)) {
323 int arity = get_irn_arity(n);
324 for (i = 0; i < arity; i++) {
325 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
326 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
327 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
329 min = get_irn_dfn(pred);
336 /* Returns index of the predecessor with the largest dfn number. */
338 largest_dfn_pred (ir_node *n)
340 int i, index = -2, max = -1;
342 if (!is_outermost_StartBlock(n)) {
343 int arity = get_irn_arity(n);
344 for (i = 0; i < arity; i++) {
345 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
346 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
347 if (get_irn_dfn(pred) > max) {
349 max = get_irn_dfn(pred);
356 /* Searches the stack for possible loop heads. Tests these for backedges.
357 If it finds a head with an unmarked backedge it marks this edge and
358 returns the tail of the loop.
359 If it finds no backedge returns NULL.
360 ("disable_backedge" in fiasco) */
362 find_tail (ir_node *n) {
364 int i, res_index = -2;
366 m = stack[tos-1]; /* tos = top of stack */
367 if (is_head (m, n)) {
368 res_index = smallest_dfn_pred(m, 0);
369 if ((res_index == -2) && /* no smallest dfn pred found. */
373 if (m == n) return NULL;
374 for (i = tos-2; ; --i) {
376 if (is_head (m, n)) {
377 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
378 if (res_index == -2) /* no smallest dfn pred found. */
379 res_index = largest_dfn_pred (m);
384 assert (res_index > -2);
386 set_backedge (m, res_index);
387 return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
390 /*-----------------------------------------------------------*
391 * The core algorithm. *
392 *-----------------------------------------------------------*/
395 static void cfscc (ir_node *n) {
400 if (irn_visited(n)) return;
403 /* Initialize the node */
404 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
405 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
406 set_irn_loop(n, NULL);
410 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
411 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
412 so is_backedge does not access array[-1] but correctly returns false! */
414 if (!is_outermost_StartBlock(n)) {
415 int arity = get_irn_arity(n);
417 for (i = 0; i < arity; i++) {
419 if (is_backedge(n, i)) continue;
420 m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
423 if (irn_is_in_stack(m)) {
424 /* Uplink of m is smaller if n->m is a backedge.
425 Propagate the uplink to mark the cfloop. */
426 if (get_irn_uplink(m) < get_irn_uplink(n))
427 set_irn_uplink(n, get_irn_uplink(m));
432 if (get_irn_dfn(n) == get_irn_uplink(n)) {
433 /* This condition holds for
434 1) the node with the incoming backedge.
435 That is: We found a cfloop!
436 2) Straight line code, because no uplink has been propagated, so the
437 uplink still is the same as the dfn.
439 But n might not be a proper cfloop head for the analysis. Proper cfloop
440 heads are Block and Phi nodes. find_tail searches the stack for
441 Block's and Phi's and takes those nodes as cfloop heads for the current
442 cfloop instead and marks the incoming edge as backedge. */
444 ir_node *tail = find_tail(n);
446 /* We have a cfloop, that is no straight line code,
447 because we found a cfloop head!
448 Next actions: Open a new cfloop on the cfloop tree and
449 try to find inner cfloops */
452 #define NO_CFLOOPS_WITHOUT_HEAD 1
453 #if NO_CFLOOPS_WITHOUT_HEAD
455 /* This is an adaption of the algorithm from fiasco / optscc to
456 * avoid cfloops without Block or Phi as first node. This should
457 * severely reduce the number of evaluations of nodes to detect
458 * a fixpoint in the heap analysis.
459 * Further it avoids cfloops without firm nodes that cause errors
460 * in the heap analyses. */
464 if (get_loop_n_elements(current_loop) > 0) {
474 ir_loop *l = new_loop();
478 /* Remove the cfloop from the stack ... */
479 pop_scc_unmark_visit (n);
481 /* The current backedge has been marked, that is temporarily eliminated,
482 by find tail. Start the scc algorithm
483 anew on the subgraph thats left (the current cfloop without the backedge)
484 in order to find more inner cfloops. */
488 assert (irn_visited(n));
489 #if NO_CFLOOPS_WITHOUT_HEAD
496 /* AS: No cfloop head was found, that is we have straightline code.
497 Pop all nodes from the stack to the current cfloop. */
503 /* Constructs backedge information for irg. */
504 void construct_cf_backedges(ir_graph *irg) {
505 ir_graph *rem = current_ir_graph;
507 ir_node *end = get_irg_end(irg);
510 assert(!interprocedural_view &&
511 "use construct_ip_backedges");
513 current_ir_graph = irg;
514 outermost_ir_graph = irg;
516 init_scc(current_ir_graph);
519 new_loop(); /* sets current_loop */
520 head_rem = current_loop; /* Just for assertion */
522 inc_irg_visited(current_ir_graph);
524 cfscc(get_irg_end_block(current_ir_graph));
525 for (i = 0; i < get_End_n_keepalives(end); i++) {
526 ir_node *el = get_End_keepalive(end, i);
527 if (is_Block(el)) cfscc(el);
530 assert(head_rem == current_loop);
531 set_irg_loop(current_ir_graph, current_loop);
532 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
533 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
535 current_ir_graph = rem;
539 void construct_ip_cf_backedges (void) {
540 ir_graph *rem = current_ir_graph;
541 int rem_ipv = interprocedural_view;
544 assert(get_irp_ip_view_state() == ip_view_valid);
546 outermost_ir_graph = get_irp_main_irg();
551 new_loop(); /* sets current_loop */
552 interprocedural_view = 1;
554 inc_max_irg_visited();
555 for (i = 0; i < get_irp_n_irgs(); i++)
556 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
558 /** We have to start the walk at the same nodes as cg_walk. **/
559 /* Walk starting at unreachable procedures. Only these
560 * have End blocks visible in interprocedural view. */
561 for (i = 0; i < get_irp_n_irgs(); i++) {
563 current_ir_graph = get_irp_irg(i);
565 sb = get_irg_start_block(current_ir_graph);
567 if ((get_Block_n_cfgpreds(sb) > 1) ||
568 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
570 cfscc(get_irg_end_block(current_ir_graph));
573 /* Check whether we walked all procedures: there could be procedures
574 with cyclic calls but no call from the outside. */
575 for (i = 0; i < get_irp_n_irgs(); i++) {
577 current_ir_graph = get_irp_irg(i);
579 /* Test start block: if inner procedure end and end block are not
580 * visible and therefore not marked. */
581 sb = get_irg_start_block(current_ir_graph);
582 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
585 /* Walk all endless cfloops in inner procedures.
586 * We recognize an inner procedure if the End node is not visited. */
587 for (i = 0; i < get_irp_n_irgs(); i++) {
589 current_ir_graph = get_irp_irg(i);
591 e = get_irg_end(current_ir_graph);
592 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
594 /* Don't visit the End node. */
595 for (j = 0; j < get_End_n_keepalives(e); j++) {
596 ir_node *el = get_End_keepalive(e, j);
597 if (is_Block(el)) cfscc(el);
602 set_irg_loop(outermost_ir_graph, current_loop);
603 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
604 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
606 current_ir_graph = rem;
607 interprocedural_view = rem_ipv;
611 static void reset_backedges(ir_node *n) {
613 int rem = interprocedural_view;
614 interprocedural_view = 1;
616 interprocedural_view = 0;
618 interprocedural_view = rem;
621 static void loop_reset_backedges(ir_loop *l) {
623 reset_backedges(get_loop_node(l, 0));
624 for (i = 0; i < get_loop_n_nodes(l); ++i)
625 set_irn_loop(get_loop_node(l, i), NULL);
626 for (i = 0; i < get_loop_n_sons(l); ++i) {
627 loop_reset_backedges(get_loop_son(l, i));
631 /* Removes all cfloop information.
632 Resets all backedges */
633 void free_cfloop_information(ir_graph *irg) {
634 if (get_irg_loop(irg))
635 loop_reset_backedges(get_irg_loop(irg));
636 set_irg_loop(irg, NULL);
637 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
638 /* We cannot free the cfloop nodes, they are on the obstack. */
642 void free_all_cfloop_information (void) {
644 int rem = interprocedural_view;
645 interprocedural_view = 1; /* To visit all filter nodes */
646 for (i = 0; i < get_irp_n_irgs(); i++) {
647 free_cfloop_information(get_irp_irg(i));
649 interprocedural_view = rem;