1 /* Copyright (C) 2002 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Goetz Lindenmaier
6 ** irscc.c Computing the strongly connected regions and building
7 ** backedge/loop datastructures.
17 #include "irgraph_t.h"
23 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
25 static ir_loop *current_loop; /* Current loop construction is working
27 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
28 Each loop node gets a unique number.
29 What for? ev. remove. @@@ */
30 static int current_dfn = 1; /* Counter to generate depth first numbering
33 /**********************************************************************/
34 /* Node attributes needed for the construction. **/
35 /**********************************************************************/
37 typedef struct scc_info {
38 bool in_stack; /* Marks whether node is on the stack. */
39 int dfn; /* Depth first search number. */
40 int uplink; /* dfn number of ancestor. */
41 ir_loop *loop; /* Refers to the containing loop. */
43 struct section *section;
49 static INLINE scc_info* new_scc_info() {
50 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
51 memset (info, 0, sizeof (scc_info));
56 mark_irn_in_stack (ir_node *n) {
57 assert(get_irn_link(n));
58 ((scc_info *)get_irn_link(n))->in_stack = true;
62 mark_irn_not_in_stack (ir_node *n) {
63 assert(get_irn_link(n));
64 ((scc_info *)get_irn_link(n))->in_stack = false;
68 irn_is_in_stack (ir_node *n) {
69 assert(get_irn_link(n));
70 return ((scc_info *)get_irn_link(n))->in_stack;
74 set_irn_uplink (ir_node *n, int uplink) {
75 assert(get_irn_link(n));
76 ((scc_info *)get_irn_link(n))->uplink = uplink;
80 get_irn_uplink (ir_node *n) {
81 assert(get_irn_link(n));
82 return ((scc_info *)get_irn_link(n))->uplink;
86 set_irn_dfn (ir_node *n, int dfn) {
87 if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
88 assert(get_irn_link(n));
89 ((scc_info *)get_irn_link(n))->dfn = dfn;
93 get_irn_dfn (ir_node *n) {
94 assert(get_irn_link(n));
95 return ((scc_info *)get_irn_link(n))->dfn;
98 /* Uses temporary information to set the loop */
100 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
101 assert(get_irn_link(n));
102 ((scc_info *)get_irn_link(n))->loop = loop;
105 /* Uses temporary information to get the loop */
106 static INLINE ir_loop *
107 get_irn_loop_tmp (ir_node *n) {
108 assert(get_irn_link(n));
109 return ((scc_info *)get_irn_link(n))->loop;
112 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
116 /* Test whether n is contained in this loop. */
117 for (i = 0; i < get_loop_n_nodes(l); i++)
118 if (n == get_loop_node(l, i)) return l;
120 /* Is this a leave in the loop tree? If so loop not found. */
121 if (get_loop_n_sons(l) == 0) return NULL;
123 /* Else descend in the loop tree. */
124 for (i = 0; i < get_loop_n_sons(l); i++) {
125 res = find_nodes_loop(n, get_loop_son(l, i));
131 /* @@@ temporary implementation, costly!!! */
132 ir_loop * get_irn_loop(ir_node *n) {
133 ir_loop *l = get_irg_loop(current_ir_graph);
134 l = find_nodes_loop(n, l);
138 /**********************************************************************/
140 /**********************************************************************/
142 static ir_node **stack = NULL;
143 static int tos = 0; /* top of stack */
145 static INLINE void init_stack() {
147 ARR_RESIZE (ir_node *, stack, 1000);
149 stack = NEW_ARR_F (ir_node *, 1000);
154 static INLINE void free_stack() {
165 if (tos == ARR_LEN (stack)) {
166 int nlen = ARR_LEN (stack) * 2;
167 ARR_RESIZE (ir_node *, stack, nlen);
170 mark_irn_in_stack(n);
173 static INLINE ir_node *
176 ir_node *n = stack[--tos];
177 mark_irn_not_in_stack(n);
181 /* The nodes up to n belong to the current loop.
182 Removes them from the stack and adds them to the current loop. */
184 pop_scc_to_loop (ir_node *n)
190 set_irn_dfn(m, loop_node_cnt);
192 add_loop_node(current_loop, m);
193 set_irn_loop_tmp(m, current_loop);
198 /* Removes and unmarks all nodes up to n from the stack.
199 The nodes must be visited once more to assign them to a scc. */
201 pop_scc_unmark_visit (ir_node *n)
207 set_irn_visited(m, 0);
211 /**********************************************************************/
212 /* The loop datastructure. **/
213 /**********************************************************************/
215 /* Allocates a new loop as son of current_loop. Sets current_loop
216 to the new loop and returns the father. */
217 static ir_loop *new_loop (void) {
218 ir_loop *father, *son;
220 father = current_loop;
222 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
223 memset (son, 0, sizeof (ir_loop));
224 son->kind = k_ir_loop;
225 son->sons = NEW_ARR_F (ir_loop *, 0);
226 son->nodes = NEW_ARR_F (ir_node *, 0);
228 son->outer_loop = father;
229 add_loop_son(father, son);
230 son->depth = father->depth+1;
231 } else { /* The root loop */
232 son->outer_loop = son;
240 /* Finishes the datastructures, copies the arrays to the obstack
241 of current_ir_graph. */
242 static void mature_loop (ir_loop *loop) {
246 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
247 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
248 DEL_ARR_F(loop->sons);
249 loop->sons = new_sons;
252 /* Returns outer loop, itself if outermost. */
253 ir_loop *get_loop_outer_loop (ir_loop *loop) {
254 assert(loop && loop->kind == k_ir_loop);
255 return loop->outer_loop;
258 /* Returns nesting depth of this loop */
259 int get_loop_depth (ir_loop *loop) {
260 assert(loop); assert(loop->kind == k_ir_loop);
264 /* Returns the number of inner loops */
265 int get_loop_n_sons (ir_loop *loop) {
266 assert(loop && loop->kind == k_ir_loop);
267 return ARR_LEN(loop->sons);
269 ir_loop *get_loop_son (ir_loop *loop, int pos) {
270 assert(loop && loop->kind == k_ir_loop);
271 return loop->sons[pos];
274 add_loop_son(ir_loop *loop, ir_loop *son) {
275 assert(loop && loop->kind == k_ir_loop);
276 ARR_APP1 (ir_loop *, loop->sons, son);
279 /* Returns the number of nodes in the loop */
280 int get_loop_n_nodes (ir_loop *loop) {
281 assert(loop); assert(loop->kind == k_ir_loop);
282 return ARR_LEN(loop->nodes);
284 ir_node *get_loop_node (ir_loop *loop, int pos) {
285 assert(loop && loop->kind == k_ir_loop);
286 return loop->nodes[pos];
289 add_loop_node(ir_loop *loop, ir_node *n) {
290 assert(loop && loop->kind == k_ir_loop);
291 ARR_APP1 (ir_node *, loop->nodes, n);
294 /* The outermost loop is remarked in the surrounding graph. */
295 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
299 ir_loop *get_irg_loop(ir_graph *irg) {
304 /**********************************************************************/
305 /* Constructing and destructing the loop/backedge information. **/
306 /**********************************************************************/
308 /* Initialization steps. **********************************************/
311 init_node (ir_node *n, void *env) {
313 set_irn_link (n, new_scc_info());
316 /* Also init nodes not visible in intraproc_view. */
317 /* @@@ init_node is called for too many nodes -- this wastes memory!.
318 The mem is not lost as its on the obstack. */
319 if (get_irn_op(n) == op_Filter) {
320 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
321 init_node(get_Filter_cg_pred(n, i), NULL);
323 if (get_irn_op(n) == op_Block) {
324 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
325 init_node(get_Block_cg_cfgpred(n, i), NULL);
328 /* The following pattern matches only after a call from above pattern. */
329 if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
330 /* @@@ init_node is called for every proj -- this wastes memory!.
331 The mem is not lost as its on the obstack. */
332 ir_node *cb = get_Proj_pred(n);
333 if ((get_irn_op(cb) == op_CallBegin) ||
334 (get_irn_op(cb) == op_EndReg) ||
335 (get_irn_op(cb) == op_EndExcept)) {
337 init_node(get_nodes_Block(cb), NULL);
343 init_scc (ir_graph *irg) {
347 irg_walk_graph (irg, init_node, NULL, NULL);
349 irg_walk (irg, link_to_reg_end, NULL, NULL);
358 cg_walk (init_node, NULL, NULL);
362 Works, but is inefficient.
366 interprocedural_view = 1;
370 for (i = 0; i < get_irp_n_irgs(); i++) {
371 current_ir_graph = get_irp_irg(i);
372 irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
373 /* @@@ decrease max_visited to avoide double walks */
378 /* Condition for breaking the recursion. */
379 static bool is_outermost_Start(ir_node *n) {
380 /* Test whether this is the outermost Start node. If so
381 recursion must end. */
382 if ((get_irn_op(n) == op_Block) &&
383 (get_Block_n_cfgpreds(n) == 1) &&
384 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
385 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
389 /* @@@ Bad condition:
390 not possible in interprocedural view as outermost_graph is
391 not necessarily the only with a dead-end start block.
392 Besides current_ir_graph is not set properly. */
393 if ((get_irn_op(n) == op_Block) &&
394 (n == get_irg_start_block(current_ir_graph))) {
395 if ((!interprocedural_view) ||
396 (current_ir_graph == outermost_ir_graph))
403 /* Don't walk from nodes to blocks except for Control flow operations. */
405 get_start_index(ir_node *n) {
406 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
412 /* Returns current_ir_graph and set it to the irg of predecessor index
414 static INLINE ir_graph *
415 switch_irg (ir_node *n, int index) {
416 ir_graph *old_current = current_ir_graph;
418 if (interprocedural_view) {
419 /* Only Filter and Block nodes can have predecessors in other graphs. */
420 if (get_irn_op(n) == op_Filter)
421 n = get_nodes_Block(n);
422 if (get_irn_op(n) == op_Block) {
423 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
424 if (is_ip_cfop(cfop)) {
425 current_ir_graph = get_irn_irg(cfop);
426 set_irg_visited(current_ir_graph, get_max_irg_visited());
434 /* Walks up the stack passing n and then finding the node
435 where we walked into the irg n is contained in.
436 Here we switch the irg. */
438 find_irg_on_stack (ir_node *n) {
440 ir_graph *old_current = current_ir_graph;
443 if (interprocedural_view) {
444 for (i = tos; i >= 0; i--) {
445 if (stack[i] == n) break;
452 for (; i >= 0; i--) {
454 //printf(" Visiting %d ", i); DDMN(m);
456 current_ir_graph = get_irn_irg(m);
459 if (get_irn_op(m) == op_Filter) {
460 /* Find the corresponding ip_cfop */
461 ir_node *pred = stack[i+1];
463 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
464 if (get_Filter_cg_pred(m, j) == pred) break;
465 if (j >= get_Filter_n_cg_preds(m))
466 /* It is a filter we didn't pass as the predecessors are marked. */
468 assert(get_Filter_cg_pred(m, j) == pred);
478 static void test(ir_node *pred, ir_node *root, ir_node *this) {
480 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
482 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
483 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
484 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
486 printf("tos: %d\n", tos);
488 for (i = tos; i >= 0; i--) {
489 ir_node *n = stack[i];
491 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
495 /* Returns true if n is a loop header, i.e., it is a Block, Phi
496 or Filter node and has predecessors within the loop and out
499 is_head (ir_node *n, ir_node *root)
502 int some_outof_loop = 0, some_in_loop = 0;
504 /* Test for legal loop header */
505 if (!((get_irn_op(n) == op_Block) ||
506 (get_irn_op(n) == op_Phi) ||
507 ((get_irn_op(n) == op_Filter) && interprocedural_view)))
510 if (!is_outermost_Start(n)) {
511 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
512 ir_node *pred = get_irn_n(n, i);
514 if (is_backedge(n, i)) continue;
515 if (!irn_is_in_stack(pred)) {
518 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
523 return some_outof_loop && some_in_loop;
526 /* Returns index of the predecessor with the smallest dfn number
527 greater-equal than limit. */
529 smallest_dfn_pred (ir_node *n, int limit)
531 int i, index = -2, min = -1;
533 if (!is_outermost_Start(n)) {
534 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
535 ir_node *pred = get_irn_n(n, i);
537 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
538 if (get_irn_dfn(pred) >= limit
539 && (min == -1 || get_irn_dfn(pred) < min)) {
541 min = get_irn_dfn(pred);
548 /* Returns index of the predecessor with the largest dfn number. */
550 largest_dfn_pred (ir_node *n)
552 int i, index = -2, max = -1;
554 if (!is_outermost_Start(n)) {
555 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
556 ir_node *pred = get_irn_n(n, i);
557 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
558 if (get_irn_dfn(pred) > max) {
560 max = get_irn_dfn(pred);
567 /* Searches the stack for possible loop heads. Tests these for backedges.
568 If it finds a head with an unmarked backedge it marks this edge and
569 returns the tail of the loop.
570 If it finds no backedge returns NULL. */
572 find_tail (ir_node *n) {
574 int i, res_index = -2;
577 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
581 if (is_head (m, n)) {
582 res_index = smallest_dfn_pred(m, 0);
583 if ((res_index == -2) && /* no smallest dfn pred found. */
587 if (m == n) return NULL;
588 for (i = tos-2; ; --i) {
590 if (is_head (m, n)) {
591 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
592 if (res_index == -2) /* no smallest dfn pred found. */
593 res_index = largest_dfn_pred (m);
598 assert (res_index > -2);
600 set_backedge (m, res_index);
601 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
605 /* The core algorithm. *****************************************/
607 static void scc (ir_node *n) {
611 if (irn_visited(n)) return;
613 //printf("mark: %d ", get_irn_visited(n)); DDMN(n);
614 //DDME(get_irg_ent(current_ir_graph));
616 /* Initialize the node */
617 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
618 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
619 set_irn_loop_tmp(n, NULL);
622 /* What's this good for?
623 n->ana.scc.section = NULL;
628 if (!is_outermost_Start(n)) {
629 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
631 if (is_backedge(n, i)) continue;
633 m = get_irn_n(n, i); //get_irn_ip_pred(n, i);
634 if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
636 //return_recur(n, i);
638 if (irn_is_in_stack(m)) {
639 /* Uplink of m is smaller if n->m is a backedge.
640 Propagate the uplink to mark the loop. */
641 if (get_irn_uplink(m) < get_irn_uplink(n))
642 set_irn_uplink(n, get_irn_uplink(m));
646 if (get_irn_dfn(n) == get_irn_uplink(n)) {
647 /* This condition holds for the node with the incoming backedge. */
648 ir_node *tail = find_tail(n);
650 /* We found a new loop! */
651 ir_loop *l = new_loop();
652 /* Remove the loop from the stack ... */
653 pop_scc_unmark_visit (n);
654 /* and recompute it in a better order; and so that it goes into
656 rem = find_irg_on_stack(tail);
658 current_ir_graph = rem;
660 assert (irn_visited(n));
669 /* Constructs backedge information for irg. In interprocedural view constructs
670 backedges for all methods called by irg, too. */
671 void construct_backedges(ir_graph *irg) {
672 ir_graph *rem = current_ir_graph;
676 assert(!interprocedural_view &&
677 "not implemented, use construct_ip_backedges");
679 current_ir_graph = irg;
680 outermost_ir_graph = irg;
685 new_loop(); /* sets current_loop */
686 head_rem = current_loop; /* Just for assertion */
688 if (interprocedural_view) {
689 set_irg_visited(irg, inc_max_irg_visited());
692 inc_irg_visited(irg);
695 scc(get_irg_end(irg));
696 for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
697 scc(get_End_keepalive(get_irg_end(irg), i));
699 if (interprocedural_view) finish_ip_walk();
701 assert(head_rem == current_loop);
702 set_irg_loop(irg, current_loop);
703 assert(get_irg_loop(irg)->kind == k_ir_loop);
705 irg->loops = current_loop;
709 count_loop (the_loop, &count, &depth);
713 current_ir_graph = rem;
718 void construct_ip_backedges () {
719 ir_graph *rem = current_ir_graph;
720 int rem_ipv = interprocedural_view;
723 outermost_ir_graph = get_irp_main_irg();
728 new_loop(); /* sets current_loop */
729 interprocedural_view = 1;
731 inc_max_irg_visited();
732 for (i = 0; i < get_irp_n_irgs(); i++)
733 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
735 for (i = 0; i < get_irp_n_irgs(); i++) {
737 current_ir_graph = get_irp_irg(i);
738 //DDME(get_irg_ent(current_ir_graph));
739 /* Find real entry points */
740 sb = get_irg_start_block(current_ir_graph);
741 if ((get_Block_n_cfgpreds(sb) > 1) ||
742 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
743 // printf("running scc for "); DDME(get_irg_ent(current_ir_graph));
744 /* Compute scc for this graph */
745 outermost_ir_graph = current_ir_graph;
746 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
747 scc(get_irg_end(current_ir_graph));
748 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
749 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
752 set_irg_loop(outermost_ir_graph, current_loop);
753 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
755 current_ir_graph = rem;
756 interprocedural_view = rem_ipv;