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 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);
42 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
43 ir_node *get_projx_link(ir_node *cb_projx);
45 /**********************************************************************/
46 /* Node attributes **/
47 /**********************************************************************/
49 /* A map to get from irnodes to loop nodes. */
50 static pmap *node_loop_map = NULL;
52 /**********************************************************************/
53 /* Node attributes needed for the construction. **/
54 /**********************************************************************/
56 typedef struct scc_info {
57 bool in_stack; /* Marks whether node is on the stack. */
58 int dfn; /* Depth first search number. */
59 int uplink; /* dfn number of ancestor. */
62 static INLINE scc_info* new_scc_info(void) {
63 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
64 memset (info, 0, sizeof (scc_info));
69 mark_irn_in_stack (ir_node *n) {
70 assert(get_irn_link(n));
71 ((scc_info *)n->link)->in_stack = true;
75 mark_irn_not_in_stack (ir_node *n) {
76 assert(get_irn_link(n));
77 ((scc_info *)n->link)->in_stack = false;
81 irn_is_in_stack (ir_node *n) {
82 assert(get_irn_link(n));
83 return ((scc_info *)n->link)->in_stack;
87 set_irn_uplink (ir_node *n, int uplink) {
88 assert(get_irn_link(n));
89 ((scc_info *)n->link)->uplink = uplink;
93 get_irn_uplink (ir_node *n) {
94 assert(get_irn_link(n));
95 return ((scc_info *)n->link)->uplink;
99 set_irn_dfn (ir_node *n, int dfn) {
100 assert(get_irn_link(n));
101 ((scc_info *)n->link)->dfn = dfn;
105 get_irn_dfn (ir_node *n) {
106 assert(get_irn_link(n));
107 return ((scc_info *)n->link)->dfn;
110 /**********************************************************************/
112 /**********************************************************************/
114 static ir_node **stack = NULL;
115 static int tos = 0; /* top of stack */
117 static INLINE void init_stack(void) {
119 ARR_RESIZE (ir_node *, stack, 1000);
121 stack = NEW_ARR_F (ir_node *, 1000);
130 if (tos == ARR_LEN (stack)) {
131 int nlen = ARR_LEN (stack) * 2;
132 ARR_RESIZE (ir_node *, stack, nlen);
135 mark_irn_in_stack(n);
138 static INLINE ir_node *
141 ir_node *n = stack[--tos];
142 mark_irn_not_in_stack(n);
146 /* The nodes up to n belong to the current loop.
147 Removes them from the stack and adds them to the current loop. */
149 pop_scc_to_loop (ir_node *n)
157 set_irn_dfn(m, loop_node_cnt);
158 add_loop_node(current_loop, m);
159 set_irn_loop(m, current_loop);
160 /* if (m==n) break;*/
164 /* GL ??? my last son is my grandson??? Removes cfloops with no
165 ir_nodes in them. Such loops have only another loop as son. (Why
166 can't they have two loops as sons? Does it never get that far? ) */
167 static void close_loop (ir_loop *l)
169 int last = get_loop_n_elements(l) - 1;
170 loop_element lelement = get_loop_element(l, last);
171 ir_loop *last_son = lelement.son;
173 if (get_kind(last_son) == k_ir_loop &&
174 get_loop_n_elements(last_son) == 1) {
177 lelement = get_loop_element(last_son, 0);
179 if(get_kind(gson) == k_ir_loop) {
180 loop_element new_last_son;
182 gson -> outer_loop = l;
183 new_last_son.son = gson;
184 l -> children[last] = new_last_son;
191 /* Removes and unmarks all nodes up to n from the stack.
192 The nodes must be visited once more to assign them to a scc. */
194 pop_scc_unmark_visit (ir_node *n)
200 set_irn_visited(m, 0);
204 /**********************************************************************/
205 /* The loop datastructure. **/
206 /**********************************************************************/
208 /* Allocates a new loop as son of current_loop. Sets current_loop
209 to the new loop and returns the father. */
210 static ir_loop *new_loop (void) {
211 ir_loop *father, *son;
213 father = current_loop;
215 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
216 memset (son, 0, sizeof (ir_loop));
217 son->kind = k_ir_loop;
218 son->children = NEW_ARR_F (loop_element, 0);
222 son->outer_loop = father;
223 add_loop_son(father, son);
224 son->depth = father->depth+1;
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) {
256 if (!node_loop_map) node_loop_map = pmap_create();
261 init_scc (ir_graph *irg) {
263 irg_walk_graph (irg, init_node, NULL, NULL);
269 cg_walk (init_node, NULL, NULL);
271 #if EXPERIMENTAL_CFLOOP_TREE
272 cg_walk (link_to_reg_end, NULL, NULL);
276 /* Condition for breaking the recursion. */
277 static bool is_outermost_StartBlock(ir_node *n) {
278 /* Test whether this is the outermost Start node. If so
279 recursion must end. */
281 if ((get_Block_n_cfgpreds(n) == 1) &&
282 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
283 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
289 /** Returns true if n is a loop header, i.e., it is a Block node
290 * and has predecessors within the cfloop and out of the cfloop.
292 * @param root: only needed for assertion.
295 is_head (ir_node *n, ir_node *root)
298 int some_outof_loop = 0, some_in_loop = 0;
302 if (!is_outermost_StartBlock(n)) {
303 arity = get_irn_arity(n);
304 for (i = 0; i < arity; i++) {
305 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
306 if (is_backedge(n, i)) continue;
307 if (!irn_is_in_stack(pred)) {
310 if (get_irn_uplink(pred) < get_irn_uplink(root)) {
311 DDMN(pred); DDMN(root);
312 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
318 return some_outof_loop && some_in_loop;
321 /* Returns index of the predecessor with the smallest dfn number
322 greater-equal than limit. */
324 smallest_dfn_pred (ir_node *n, int limit)
326 int i, index = -2, min = -1;
328 if (!is_outermost_StartBlock(n)) {
329 int arity = get_irn_arity(n);
330 for (i = 0; i < arity; i++) {
331 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
332 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
333 if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
335 min = get_irn_dfn(pred);
342 /* Returns index of the predecessor with the largest dfn number. */
344 largest_dfn_pred (ir_node *n)
346 int i, index = -2, max = -1;
348 if (!is_outermost_StartBlock(n)) {
349 int arity = get_irn_arity(n);
350 for (i = 0; i < arity; i++) {
351 ir_node *pred = get_nodes_block(skip_Proj(get_irn_n(n, i)));
352 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
353 if (get_irn_dfn(pred) > max) {
355 max = get_irn_dfn(pred);
362 /* Searches the stack for possible loop heads. Tests these for backedges.
363 If it finds a head with an unmarked backedge it marks this edge and
364 returns the tail of the loop.
365 If it finds no backedge returns NULL.
366 ("disable_backedge" in fiasco) */
368 find_tail (ir_node *n) {
370 int i, res_index = -2;
372 m = stack[tos-1]; /* tos = top of stack */
373 if (is_head (m, n)) {
374 res_index = smallest_dfn_pred(m, 0);
375 if ((res_index == -2) && /* no smallest dfn pred found. */
379 if (m == n) return NULL;
380 for (i = tos-2; ; --i) {
382 if (is_head (m, n)) {
383 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
384 if (res_index == -2) /* no smallest dfn pred found. */
385 res_index = largest_dfn_pred (m);
390 assert (res_index > -2);
392 set_backedge (m, res_index);
393 return is_outermost_StartBlock(n) ? NULL : get_nodes_block(skip_Proj(get_irn_n(m, res_index)));
396 /*-----------------------------------------------------------*
397 * The core algorithm. *
398 *-----------------------------------------------------------*/
401 static void cfscc (ir_node *n) {
406 if (irn_visited(n)) return;
409 /* Initialize the node */
410 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
411 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
412 set_irn_loop(n, NULL);
416 /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
417 array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
418 so is_backedge does not access array[-1] but correctly returns false! */
420 if (!is_outermost_StartBlock(n)) {
421 int arity = get_irn_arity(n);
423 for (i = 0; i < arity; i++) {
425 if (is_backedge(n, i)) continue;
426 m = get_nodes_block(skip_Proj(get_irn_n(n, i)));
429 if (irn_is_in_stack(m)) {
430 /* Uplink of m is smaller if n->m is a backedge.
431 Propagate the uplink to mark the cfloop. */
432 if (get_irn_uplink(m) < get_irn_uplink(n))
433 set_irn_uplink(n, get_irn_uplink(m));
438 if (get_irn_dfn(n) == get_irn_uplink(n)) {
439 /* This condition holds for
440 1) the node with the incoming backedge.
441 That is: We found a cfloop!
442 2) Straight line code, because no uplink has been propagated, so the
443 uplink still is the same as the dfn.
445 But n might not be a proper cfloop head for the analysis. Proper cfloop
446 heads are Block and Phi nodes. find_tail searches the stack for
447 Block's and Phi's and takes those nodes as cfloop heads for the current
448 cfloop instead and marks the incoming edge as backedge. */
450 ir_node *tail = find_tail(n);
452 /* We have a cfloop, that is no straight line code,
453 because we found a cfloop head!
454 Next actions: Open a new cfloop on the cfloop tree and
455 try to find inner cfloops */
458 #define NO_CFLOOPS_WITHOUT_HEAD 1
459 #if NO_CFLOOPS_WITHOUT_HEAD
461 /* This is an adaption of the algorithm from fiasco / optscc to
462 * avoid cfloops without Block or Phi as first node. This should
463 * severely reduce the number of evaluations of nodes to detect
464 * a fixpoint in the heap analysis.
465 * Further it avoids cfloops without firm nodes that cause errors
466 * in the heap analyses. */
470 if (get_loop_n_elements(current_loop) > 0) {
480 ir_loop *l = new_loop();
484 /* Remove the cfloop from the stack ... */
485 pop_scc_unmark_visit (n);
487 /* The current backedge has been marked, that is temporarily eliminated,
488 by find tail. Start the scc algorithm
489 anew on the subgraph thats left (the current cfloop without the backedge)
490 in order to find more inner cfloops. */
494 assert (irn_visited(n));
495 #if NO_CFLOOPS_WITHOUT_HEAD
502 /* AS: No cfloop head was found, that is we have straightline code.
503 Pop all nodes from the stack to the current cfloop. */
509 /* Constructs backedge information for irg. */
510 void construct_cf_backedges(ir_graph *irg) {
511 ir_graph *rem = current_ir_graph;
513 ir_node *end = get_irg_end(irg);
516 assert(!interprocedural_view &&
517 "use construct_ip_backedges");
519 current_ir_graph = irg;
520 outermost_ir_graph = irg;
522 init_scc(current_ir_graph);
525 new_loop(); /* sets current_loop */
526 head_rem = current_loop; /* Just for assertion */
528 inc_irg_visited(current_ir_graph);
530 cfscc(get_irg_end_block(current_ir_graph));
531 for (i = 0; i < get_End_n_keepalives(end); i++) {
532 ir_node *el = get_End_keepalive(end, i);
533 if (is_Block(el)) cfscc(el);
536 assert(head_rem == current_loop);
537 set_irg_loop(current_ir_graph, current_loop);
538 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_consistent);
539 assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
541 current_ir_graph = rem;
545 void construct_ip_cf_backedges (void) {
546 ir_graph *rem = current_ir_graph;
547 int rem_ipv = interprocedural_view;
550 assert(get_irp_ip_view_state() == ip_view_valid);
552 outermost_ir_graph = get_irp_main_irg();
557 new_loop(); /* sets current_loop */
558 interprocedural_view = 1;
560 inc_max_irg_visited();
561 for (i = 0; i < get_irp_n_irgs(); i++)
562 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
564 /** We have to start the walk at the same nodes as cg_walk. **/
565 /* Walk starting at unreachable procedures. Only these
566 * have End blocks visible in interprocedural view. */
567 for (i = 0; i < get_irp_n_irgs(); i++) {
569 current_ir_graph = get_irp_irg(i);
571 sb = get_irg_start_block(current_ir_graph);
573 if ((get_Block_n_cfgpreds(sb) > 1) ||
574 (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
576 cfscc(get_irg_end_block(current_ir_graph));
579 /* Check whether we walked all procedures: there could be procedures
580 with cyclic calls but no call from the outside. */
581 for (i = 0; i < get_irp_n_irgs(); i++) {
583 current_ir_graph = get_irp_irg(i);
585 /* Test start block: if inner procedure end and end block are not
586 * visible and therefore not marked. */
587 sb = get_irg_start_block(current_ir_graph);
588 if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) cfscc(sb);
591 /* Walk all endless cfloops in inner procedures.
592 * We recognize an inner procedure if the End node is not visited. */
593 for (i = 0; i < get_irp_n_irgs(); i++) {
595 current_ir_graph = get_irp_irg(i);
597 e = get_irg_end(current_ir_graph);
598 if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
600 /* Don't visit the End node. */
601 for (j = 0; j < get_End_n_keepalives(e); j++) {
602 ir_node *el = get_End_keepalive(e, j);
603 if (is_Block(el)) cfscc(el);
608 set_irg_loop(outermost_ir_graph, current_loop);
609 set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_ip_consistent);
610 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
612 current_ir_graph = rem;
613 interprocedural_view = rem_ipv;
617 static void reset_backedges(ir_node *n) {
619 int rem = interprocedural_view;
620 interprocedural_view = 1;
622 interprocedural_view = 0;
624 interprocedural_view = rem;
627 static void loop_reset_backedges(ir_loop *l) {
629 reset_backedges(get_loop_node(l, 0));
630 for (i = 0; i < get_loop_n_nodes(l); ++i)
631 set_irn_loop(get_loop_node(l, i), NULL);
632 for (i = 0; i < get_loop_n_sons(l); ++i) {
633 loop_reset_backedges(get_loop_son(l, i));
637 /* Removes all cfloop information.
638 Resets all backedges */
639 void free_cfloop_information(ir_graph *irg) {
640 if (get_irg_loop(irg))
641 loop_reset_backedges(get_irg_loop(irg));
642 set_irg_loop(irg, NULL);
643 set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
644 /* We cannot free the cfloop nodes, they are on the obstack. */
648 void free_all_cfloop_information (void) {
650 int rem = interprocedural_view;
651 interprocedural_view = 1; /* To visit all filter nodes */
652 for (i = 0; i < get_irp_n_irgs(); i++) {
653 free_cfloop_information(get_irp_irg(i));
655 pmap_destroy(node_loop_map);
656 node_loop_map = NULL;
657 interprocedural_view = rem;