1 /* Copyright (C) 2002 by Universitaet Karlsruhe
4 * Authors: Goetz Lindenmaier
6 * irscc.c Computing the strongly connected regions and building
7 * backedge/loop datastructures.
17 #include "irgraph_t.h"
22 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
24 static ir_loop *current_loop; /* Current loop construction is working
26 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
27 Each loop node gets a unique number.
28 What for? ev. remove. @@@ */
29 static int current_dfn = 1; /* Counter to generate depth first numbering
32 /**********************************************************************/
33 /* Node attributes needed for the construction. **/
34 /**********************************************************************/
36 typedef struct scc_info {
37 bool in_stack; /* Marks whether node is on the stack. */
38 int dfn; /* Depth first search number. */
39 int uplink; /* dfn number of ancestor. */
40 ir_loop *loop; /* Refers to the containing loop. */
42 struct section *section;
48 static INLINE scc_info* new_scc_info(void) {
49 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
50 memset (info, 0, sizeof (scc_info));
55 mark_irn_in_stack (ir_node *n) {
56 assert(get_irn_link(n));
57 ((scc_info *)get_irn_link(n))->in_stack = true;
61 mark_irn_not_in_stack (ir_node *n) {
62 assert(get_irn_link(n));
63 ((scc_info *)get_irn_link(n))->in_stack = false;
67 irn_is_in_stack (ir_node *n) {
68 assert(get_irn_link(n));
69 return ((scc_info *)get_irn_link(n))->in_stack;
73 set_irn_uplink (ir_node *n, int uplink) {
74 assert(get_irn_link(n));
75 ((scc_info *)get_irn_link(n))->uplink = uplink;
79 get_irn_uplink (ir_node *n) {
80 assert(get_irn_link(n));
81 return ((scc_info *)get_irn_link(n))->uplink;
85 set_irn_dfn (ir_node *n, int dfn) {
86 if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
87 assert(get_irn_link(n));
88 ((scc_info *)get_irn_link(n))->dfn = dfn;
92 get_irn_dfn (ir_node *n) {
93 assert(get_irn_link(n));
94 return ((scc_info *)get_irn_link(n))->dfn;
97 /* Uses temporary information to set the loop */
99 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
100 assert(get_irn_link(n));
101 ((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;
113 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
117 /* Test whether n is contained in this loop. */
118 for (i = 0; i < get_loop_n_nodes(l); i++)
119 if (n == get_loop_node(l, i)) return l;
121 /* Is this a leave in the loop tree? If so loop not found. */
122 if (get_loop_n_sons(l) == 0) return NULL;
124 /* Else descend in the loop tree. */
125 for (i = 0; i < get_loop_n_sons(l); i++) {
126 res = find_nodes_loop(n, get_loop_son(l, i));
132 /* @@@ temporary implementation, costly!!! */
133 ir_loop * get_irn_loop(ir_node *n) {
134 ir_loop *l = get_irg_loop(current_ir_graph);
135 l = find_nodes_loop(n, l);
139 /**********************************************************************/
141 /**********************************************************************/
143 static ir_node **stack = NULL;
144 static int tos = 0; /* top of stack */
146 static INLINE void init_stack(void) {
148 ARR_RESIZE (ir_node *, stack, 1000);
150 stack = NEW_ARR_F (ir_node *, 1000);
156 static INLINE void free_stack(void) {
168 if (tos == ARR_LEN (stack)) {
169 int nlen = ARR_LEN (stack) * 2;
170 ARR_RESIZE (ir_node *, stack, nlen);
173 mark_irn_in_stack(n);
176 static INLINE ir_node *
179 ir_node *n = stack[--tos];
180 mark_irn_not_in_stack(n);
184 /* The nodes up to n belong to the current loop.
185 Removes them from the stack and adds them to the current loop. */
187 pop_scc_to_loop (ir_node *n)
193 set_irn_dfn(m, loop_node_cnt);
195 add_loop_node(current_loop, m);
196 set_irn_loop_tmp(m, current_loop);
201 /* Removes and unmarks all nodes up to n from the stack.
202 The nodes must be visited once more to assign them to a scc. */
204 pop_scc_unmark_visit (ir_node *n)
210 set_irn_visited(m, 0);
214 /**********************************************************************/
215 /* The loop datastructure. **/
216 /**********************************************************************/
218 /* Allocates a new loop as son of current_loop. Sets current_loop
219 to the new loop and returns the father. */
220 static ir_loop *new_loop (void) {
221 ir_loop *father, *son;
223 father = current_loop;
225 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
226 memset (son, 0, sizeof (ir_loop));
227 son->kind = k_ir_loop;
228 /* son->sons = NEW_ARR_F (ir_loop *, 0);
229 son->nodes = NEW_ARR_F (ir_node *, 0);
230 A. Schoesser: Removed, because array children was introduced,
231 which contains both, nodes AND sons.
232 This comment may be removed after beeing read by all important persons :) */
233 son->children = NEW_ARR_F (loop_element, 0);
237 son->outer_loop = father;
238 add_loop_son(father, son);
239 son->depth = father->depth+1;
240 } else { /* The root loop */
241 son->outer_loop = son;
250 /* Finishes the datastructures, copies the arrays to the obstack
252 A. Schoesser: Caution: loop -> sons is gone. */
253 static void mature_loop (ir_loop *loop) {
256 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
257 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
258 DEL_ARR_F(loop->sons);
259 loop->sons = new_sons;
263 /* Returns outer loop, itself if outermost. */
264 ir_loop *get_loop_outer_loop (ir_loop *loop) {
265 assert(loop && loop->kind == k_ir_loop);
266 return loop->outer_loop;
269 /* Returns nesting depth of this loop */
270 int get_loop_depth (ir_loop *loop) {
271 assert(loop); assert(loop->kind == k_ir_loop);
275 /* Returns the number of inner loops */
276 int get_loop_n_sons (ir_loop *loop) {
277 assert(loop && loop->kind == k_ir_loop);
278 return(loop -> n_sons);
281 /* Returns the pos`th loop_node-child *
282 * TODO: This method isn`t very efficient ! *
283 * Returns NULL if there isnt`t a pos`th loop_node */
284 ir_loop *get_loop_son (ir_loop *loop, int pos) {
285 int child_nr = 0, loop_nr = -1;
287 assert(loop && loop->kind == k_ir_loop);
288 while(child_nr < ARR_LEN(loop->children))
290 if(*(loop -> children[child_nr].kind) == k_ir_loop)
293 return(loop -> children[child_nr].son);
299 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
303 add_loop_son(ir_loop *loop, ir_loop *son) {
304 assert(loop && loop->kind == k_ir_loop);
305 assert(get_kind(son) == k_ir_loop);
306 ARR_APP1 (loop_element, loop->children, (loop_element) son);
310 /* Returns the number of nodes in the loop */
311 int get_loop_n_nodes (ir_loop *loop) {
312 assert(loop); assert(loop->kind == k_ir_loop);
313 return loop -> n_nodes;
314 /* return ARR_LEN(loop->nodes); */
317 /* Returns the pos`th ir_node-child *
318 * TODO: This method isn`t very efficient ! *
319 * Returns NULL if there isnt`t a pos`th ir_node */
320 ir_node *get_loop_node (ir_loop *loop, int pos) {
321 int child_nr, node_nr = -1;
323 assert(loop && loop->kind == k_ir_loop);
324 assert(pos < get_loop_n_nodes(loop));
326 for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
327 if(*(loop -> children[child_nr].kind) == k_ir_node)
330 return(loop -> children[child_nr].node);
332 assert(0 && "no child at pos found");
336 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
340 add_loop_node(ir_loop *loop, ir_node *n) {
341 assert(loop && loop->kind == k_ir_loop);
342 assert(get_kind(n) == k_ir_node);
343 ARR_APP1 (loop_element, loop->children, (loop_element) n);
347 /** Returns the number of elements contained in loop. */
348 int get_loop_n_elements (ir_loop *loop) {
349 assert(loop && loop->kind == k_ir_loop);
350 return(ARR_LEN(loop->children));
354 Returns the pos`th loop element.
355 This may be a loop_node or a ir_node. The caller of this function has
356 to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
357 and then select the apropriate "loop_element.node" or "loop_element.son".
360 loop_element get_loop_element (ir_loop *loop, int pos) {
361 assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
363 return(loop -> children[pos]);
366 /* The outermost loop is remarked in the surrounding graph. */
367 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
371 ir_loop *get_irg_loop(ir_graph *irg) {
376 /**********************************************************************/
377 /* Constructing and destructing the loop/backedge information. **/
378 /**********************************************************************/
380 /* Initialization steps. **********************************************/
383 init_node (ir_node *n, void *env) {
384 set_irn_link (n, new_scc_info());
387 /* Also init nodes not visible in intraproc_view. */
388 /* @@@ init_node is called for too many nodes -- this wastes memory!.
389 The mem is not lost as its on the obstack. */
390 if (get_irn_op(n) == op_Filter) {
391 for (i = 0; i < get_Filter_n_cg_preds(n); i++)
392 init_node(get_Filter_cg_pred(n, i), NULL);
394 if (get_irn_op(n) == op_Block) {
395 for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
396 init_node(get_Block_cg_cfgpred(n, i), NULL);
399 /* The following pattern matches only after a call from above pattern. */
400 if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
401 /* @@@ init_node is called for every proj -- this wastes memory!.
402 The mem is not lost as its on the obstack. */
403 ir_node *cb = get_Proj_pred(n);
404 if ((get_irn_op(cb) == op_CallBegin) ||
405 (get_irn_op(cb) == op_EndReg) ||
406 (get_irn_op(cb) == op_EndExcept)) {
408 init_node(get_nodes_Block(cb), NULL);
414 init_scc (ir_graph *irg) {
418 irg_walk_graph (irg, init_node, NULL, NULL);
420 irg_walk (irg, link_to_reg_end, NULL, NULL);
429 cg_walk (init_node, NULL, NULL);
433 Works, but is inefficient.
437 interprocedural_view = 1;
441 for (i = 0; i < get_irp_n_irgs(); i++) {
442 current_ir_graph = get_irp_irg(i);
443 irg_walk_graph (current_ir_graph, init_node, NULL, NULL);
444 /* @@@ decrease max_visited to avoide double walks */
449 /* Condition for breaking the recursion. */
450 static bool is_outermost_Start(ir_node *n) {
451 /* Test whether this is the outermost Start node. If so
452 recursion must end. */
453 if ((get_irn_op(n) == op_Block) &&
454 (get_Block_n_cfgpreds(n) == 1) &&
455 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
456 (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
460 /* @@@ Bad condition:
461 not possible in interprocedural view as outermost_graph is
462 not necessarily the only with a dead-end start block.
463 Besides current_ir_graph is not set properly. */
464 if ((get_irn_op(n) == op_Block) &&
465 (n == get_irg_start_block(current_ir_graph))) {
466 if ((!interprocedural_view) ||
467 (current_ir_graph == outermost_ir_graph))
474 /* Don't walk from nodes to blocks except for Control flow operations. */
476 get_start_index(ir_node *n) {
477 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
483 /* Returns current_ir_graph and set it to the irg of predecessor index
485 static INLINE ir_graph *
486 switch_irg (ir_node *n, int index) {
487 ir_graph *old_current = current_ir_graph;
489 if (interprocedural_view) {
490 /* Only Filter and Block nodes can have predecessors in other graphs. */
491 if (get_irn_op(n) == op_Filter)
492 n = get_nodes_Block(n);
493 if (get_irn_op(n) == op_Block) {
494 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
495 if (is_ip_cfop(cfop)) {
496 current_ir_graph = get_irn_irg(cfop);
497 set_irg_visited(current_ir_graph, get_max_irg_visited());
505 /* Walks up the stack passing n and then finding the node
506 where we walked into the irg n is contained in.
507 Here we switch the irg. */
509 find_irg_on_stack (ir_node *n) {
511 ir_graph *old_current = current_ir_graph;
514 if (interprocedural_view) {
515 for (i = tos; i >= 0; i--) {
516 if (stack[i] == n) break;
523 for (; i >= 0; i--) {
525 //printf(" Visiting %d ", i); DDMN(m);
527 current_ir_graph = get_irn_irg(m);
530 if (get_irn_op(m) == op_Filter) {
531 /* Find the corresponding ip_cfop */
532 ir_node *pred = stack[i+1];
534 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
535 if (get_Filter_cg_pred(m, j) == pred) break;
536 if (j >= get_Filter_n_cg_preds(m))
537 /* It is a filter we didn't pass as the predecessors are marked. */
539 assert(get_Filter_cg_pred(m, j) == pred);
550 static void test(ir_node *pred, ir_node *root, ir_node *this) {
552 if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
554 printf("this: %d ", get_irn_uplink(this)); DDMN(this);
555 printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
556 printf("root: %d ", get_irn_uplink(root)); DDMN(root);
558 printf("tos: %d\n", tos);
560 for (i = tos; i >= 0; i--) {
561 ir_node *n = stack[i];
563 printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
568 /* Returns true if n is a loop header, i.e., it is a Block, Phi
569 or Filter node and has predecessors within the loop and out
572 is_head (ir_node *n, ir_node *root)
575 int some_outof_loop = 0, some_in_loop = 0;
577 /* Test for legal loop header */
578 if (!((get_irn_op(n) == op_Block) ||
579 (get_irn_op(n) == op_Phi) ||
580 ((get_irn_op(n) == op_Filter) && interprocedural_view)))
583 if (!is_outermost_Start(n)) {
584 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
585 ir_node *pred = get_irn_n(n, i);
587 if (is_backedge(n, i)) continue;
588 if (!irn_is_in_stack(pred)) {
591 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
596 return some_outof_loop && some_in_loop;
599 /* Returns index of the predecessor with the smallest dfn number
600 greater-equal than limit. */
602 smallest_dfn_pred (ir_node *n, int limit)
604 int i, index = -2, min = -1;
606 if (!is_outermost_Start(n)) {
607 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
608 ir_node *pred = get_irn_n(n, i);
610 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
611 if (get_irn_dfn(pred) >= limit
612 && (min == -1 || get_irn_dfn(pred) < min)) {
614 min = get_irn_dfn(pred);
621 /* Returns index of the predecessor with the largest dfn number. */
623 largest_dfn_pred (ir_node *n)
625 int i, index = -2, max = -1;
627 if (!is_outermost_Start(n)) {
628 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
629 ir_node *pred = get_irn_n(n, i);
630 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
631 if (get_irn_dfn(pred) > max) {
633 max = get_irn_dfn(pred);
640 /* Searches the stack for possible loop heads. Tests these for backedges.
641 If it finds a head with an unmarked backedge it marks this edge and
642 returns the tail of the loop.
643 If it finds no backedge returns NULL. */
645 find_tail (ir_node *n) {
647 int i, res_index = -2;
650 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
654 if (is_head (m, n)) {
655 res_index = smallest_dfn_pred(m, 0);
656 if ((res_index == -2) && /* no smallest dfn pred found. */
660 if (m == n) return NULL;
661 for (i = tos-2; ; --i) {
663 if (is_head (m, n)) {
664 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
665 if (res_index == -2) /* no smallest dfn pred found. */
666 res_index = largest_dfn_pred (m);
671 assert (res_index > -2);
673 set_backedge (m, res_index);
674 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
678 /* The core algorithm. *****************************************/
680 static void scc (ir_node *n) {
684 if (irn_visited(n)) return;
686 //printf("mark: %d ", get_irn_visited(n)); DDMN(n);
687 //DDME(get_irg_ent(current_ir_graph));
689 /* Initialize the node */
690 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
691 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
692 set_irn_loop_tmp(n, NULL);
695 /* What's this good for?
696 n->ana.scc.section = NULL;
701 if (!is_outermost_Start(n)) {
702 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
704 if (is_backedge(n, i)) continue;
706 m = get_irn_n(n, i); //get_irn_ip_pred(n, i);
707 if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
709 //return_recur(n, i);
711 if (irn_is_in_stack(m)) {
712 /* Uplink of m is smaller if n->m is a backedge.
713 Propagate the uplink to mark the loop. */
714 if (get_irn_uplink(m) < get_irn_uplink(n))
715 set_irn_uplink(n, get_irn_uplink(m));
719 if (get_irn_dfn(n) == get_irn_uplink(n)) {
720 /* This condition holds for the node with the incoming backedge. */
721 ir_node *tail = find_tail(n);
723 /* We found a new loop! */
724 ir_loop *l = new_loop();
725 /* Remove the loop from the stack ... */
726 pop_scc_unmark_visit (n);
727 /* and recompute it in a better order; and so that it goes into
729 rem = find_irg_on_stack(tail);
731 current_ir_graph = rem;
733 assert (irn_visited(n));
742 /* Constructs backedge information for irg. In interprocedural view constructs
743 backedges for all methods called by irg, too. */
744 void construct_backedges(ir_graph *irg) {
745 ir_graph *rem = current_ir_graph;
749 assert(!interprocedural_view &&
750 "not implemented, use construct_ip_backedges");
752 current_ir_graph = irg;
753 outermost_ir_graph = irg;
758 new_loop(); /* sets current_loop */
759 head_rem = current_loop; /* Just for assertion */
761 if (interprocedural_view) {
762 set_irg_visited(irg, inc_max_irg_visited());
765 inc_irg_visited(irg);
768 scc(get_irg_end(irg));
769 for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
770 scc(get_End_keepalive(get_irg_end(irg), i));
772 if (interprocedural_view) finish_ip_walk();
774 assert(head_rem == current_loop);
775 set_irg_loop(irg, current_loop);
776 assert(get_irg_loop(irg)->kind == k_ir_loop);
778 irg->loops = current_loop;
782 count_loop (the_loop, &count, &depth);
786 current_ir_graph = rem;
791 void construct_ip_backedges (void) {
792 ir_graph *rem = current_ir_graph;
793 int rem_ipv = interprocedural_view;
796 outermost_ir_graph = get_irp_main_irg();
801 new_loop(); /* sets current_loop */
802 interprocedural_view = 1;
804 inc_max_irg_visited();
805 for (i = 0; i < get_irp_n_irgs(); i++)
806 set_irg_visited(get_irp_irg(i), get_max_irg_visited());
808 for (i = 0; i < get_irp_n_irgs(); i++) {
810 current_ir_graph = get_irp_irg(i);
811 //DDME(get_irg_ent(current_ir_graph));
812 /* Find real entry points */
813 sb = get_irg_start_block(current_ir_graph);
814 if ((get_Block_n_cfgpreds(sb) > 1) ||
815 (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
816 // printf("running scc for "); DDME(get_irg_ent(current_ir_graph));
817 /* Compute scc for this graph */
818 outermost_ir_graph = current_ir_graph;
819 set_irg_visited(outermost_ir_graph, get_max_irg_visited());
820 scc(get_irg_end(current_ir_graph));
821 for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
822 scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
825 set_irg_loop(outermost_ir_graph, current_loop);
826 assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
828 current_ir_graph = rem;
829 interprocedural_view = rem_ipv;