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.
15 #include "irgraph_t.h"
18 ir_graph *outermost_ir_graph; /* The outermost graph the scc is computed
20 static ir_loop *current_loop; /* Current loop construction is working
22 static int loop_node_cnt = 0; /* Counts the number of allocated loop nodes.
23 Each loop node gets a unique number.
24 What for? ev. remove. @@@ */
25 static int current_dfn = 1; /* Counter to generate depth first numbering
28 /**********************************************************************/
29 /* Node attributes needed for the construction. **/
30 /**********************************************************************/
32 typedef struct scc_info {
33 bool in_stack; /* Marks whether node is on the stack. */
34 int dfn; /* Depth first search number. */
35 int uplink; /* dfn number of ancestor. */
36 ir_loop *loop; /* Refers to the containing loop. */
38 struct section *section;
44 static INLINE scc_info* new_scc_info() {
45 scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
46 memset (info, 0, sizeof (scc_info));
51 mark_irn_in_stack (ir_node *n) {
52 assert(get_irn_link(n));
53 ((scc_info *)get_irn_link(n))->in_stack = true;
57 mark_irn_not_in_stack (ir_node *n) {
58 assert(get_irn_link(n));
59 ((scc_info *)get_irn_link(n))->in_stack = false;
63 irn_is_in_stack (ir_node *n) {
64 assert(get_irn_link(n));
65 return ((scc_info *)get_irn_link(n))->in_stack;
69 set_irn_uplink (ir_node *n, int uplink) {
70 assert(get_irn_link(n));
71 ((scc_info *)get_irn_link(n))->uplink = uplink;
75 get_irn_uplink (ir_node *n) {
76 assert(get_irn_link(n));
77 return ((scc_info *)get_irn_link(n))->uplink;
81 set_irn_dfn (ir_node *n, int dfn) {
82 if (! get_irn_link(n)) { DDMN(n); DDME(get_irg_ent(current_ir_graph));}
83 assert(get_irn_link(n));
84 ((scc_info *)get_irn_link(n))->dfn = dfn;
88 get_irn_dfn (ir_node *n) {
89 assert(get_irn_link(n));
90 return ((scc_info *)get_irn_link(n))->dfn;
93 /* Uses temporary information to set the loop */
95 set_irn_loop_tmp (ir_node *n, ir_loop* loop) {
96 assert(get_irn_link(n));
97 ((scc_info *)get_irn_link(n))->loop = loop;
100 /* Uses temporary information to get the loop */
101 static INLINE ir_loop *
102 get_irn_loop_tmp (ir_node *n) {
103 assert(get_irn_link(n));
104 return ((scc_info *)get_irn_link(n))->loop;
107 ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
111 /* Test whether n is contained in this loop. */
112 for (i = 0; i < get_loop_n_nodes(l); i++)
113 if (n == get_loop_node(l, i)) return l;
115 /* Is this a leave in the loop tree? If so loop not found. */
116 if (get_loop_n_sons(l) == 0) return NULL;
118 /* Else descend in the loop tree. */
119 for (i = 0; i < get_loop_n_sons(l); i++) {
120 res = find_nodes_loop(n, get_loop_son(l, i));
126 /* @@@ temporary implementation, costly!!! */
127 ir_loop * get_irn_loop(ir_node *n) {
128 ir_loop *l = get_irg_loop(current_ir_graph);
129 l = find_nodes_loop(n, l);
133 /**********************************************************************/
135 /**********************************************************************/
137 static ir_node **stack = NULL;
138 static int tos = 0; /* top of stack */
140 static INLINE void init_stack() {
142 ARR_RESIZE (ir_node *, stack, 1000);
144 stack = NEW_ARR_F (ir_node *, 1000);
149 static INLINE void free_stack() {
160 if (tos == ARR_LEN (stack)) {
161 int nlen = ARR_LEN (stack) * 2;
162 ARR_RESIZE (ir_node *, stack, nlen);
165 mark_irn_in_stack(n);
168 static INLINE ir_node *
171 ir_node *n = stack[--tos];
172 mark_irn_not_in_stack(n);
176 /* The nodes up to n belong to the current loop.
177 Removes them from the stack and adds them to the current loop. */
179 pop_scc_to_loop (ir_node *n)
185 set_irn_dfn(m, loop_node_cnt);
187 add_loop_node(current_loop, m);
188 set_irn_loop_tmp(m, current_loop);
193 /* Removes and unmarks all nodes up to n from the stack.
194 The nodes must be visited once more to assign them to a scc. */
196 pop_scc_unmark_visit (ir_node *n)
202 set_irn_visited(m, 0);
206 /**********************************************************************/
207 /* The loop datastructure. **/
208 /**********************************************************************/
210 /* Allocates a new loop as son of current_loop. Sets current_loop
211 to the new loop and returns the father. */
212 ir_loop *new_loop (void) {
213 ir_loop *father, *son;
215 father = current_loop;
217 son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
218 memset (son, 0, sizeof (ir_loop));
219 son->kind = k_ir_loop;
220 son->sons = NEW_ARR_F (ir_loop *, 0);
221 son->nodes = NEW_ARR_F (ir_node *, 0);
223 son->outer_loop = father;
224 add_loop_son(father, son);
225 son->depth = father->depth+1;
226 } else { /* The root loop */
227 son->outer_loop = son;
235 /* Finishes the datastructures, copies the arrays to the obstack
236 of current_ir_graph. */
237 void mature_loop (ir_loop *loop) {
241 new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
242 memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
243 DEL_ARR_F(loop->sons);
244 loop->sons = new_sons;
247 /* Returns outer loop, itself if outermost. */
248 ir_loop *get_loop_outer_loop (ir_loop *loop) {
249 assert(loop && loop->kind == k_ir_loop);
250 return loop->outer_loop;
253 /* Returns nesting depth of this loop */
254 int get_loop_depth (ir_loop *loop) {
255 assert(loop); assert(loop->kind == k_ir_loop);
259 /* @@@ sons are the inner loops _and_ all nodes within them. */
260 /* Returns the number of inner loops */
261 int get_loop_n_sons (ir_loop *loop) {
262 assert(loop && loop->kind == k_ir_loop);
263 return ARR_LEN(loop->sons);
265 ir_loop *get_loop_son (ir_loop *loop, int pos) {
266 assert(loop && loop->kind == k_ir_loop);
267 return loop->sons[pos];
270 add_loop_son(ir_loop *loop, ir_loop *son) {
271 assert(loop && loop->kind == k_ir_loop);
272 ARR_APP1 (ir_loop *, loop->sons, son);
275 /* Returns the number of nodes in the loop */
276 int get_loop_n_nodes (ir_loop *loop) {
277 assert(loop); assert(loop->kind == k_ir_loop);
278 return ARR_LEN(loop->nodes);
280 ir_node *get_loop_node (ir_loop *loop, int pos) {
281 assert(loop && loop->kind == k_ir_loop);
282 return loop->nodes[pos];
285 add_loop_node(ir_loop *loop, ir_node *n) {
286 assert(loop && loop->kind == k_ir_loop);
287 ARR_APP1 (ir_node *, loop->nodes, n);
290 /* The outermost loop is remarked in the surrounding graph. */
291 void set_irg_loop(ir_graph *irg, ir_loop *loop) {
295 ir_loop *get_irg_loop(ir_graph *irg) {
300 /**********************************************************************/
301 /* Constructing and destructing the loop/backedge information. **/
302 /**********************************************************************/
304 /* Initialization steps. **********************************************/
307 init_node (ir_node *n, void *env) {
308 set_irn_link (n, new_scc_info());
313 init_scc (ir_graph *irg) {
317 irg_walk_graph (irg, init_node, NULL, NULL);
319 irg_walk (irg, link_to_reg_end, NULL, NULL);
323 /* Condition for breaking the recursion. */
324 bool is_outermost_Start(ir_node *n) {
325 /* Test whether this is the outermost Start node. If so
326 recursion must end. */
327 if ((get_irn_op(n) == op_Block) &&
328 (n == get_irg_start_block(current_ir_graph))) {
329 if ((!interprocedural_view) ||
330 (current_ir_graph == outermost_ir_graph))
336 /* Don't walk from nodes to blocks except for Control flow operations. */
338 get_start_index(ir_node *n) {
339 if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
345 /* Returns current_ir_graph and set it to the irg of predecessor index
347 static INLINE ir_graph *
348 switch_irg (ir_node *n, int index) {
349 ir_graph *old_current = current_ir_graph;
351 if (interprocedural_view) {
352 /* Only Filter and Block nodes can have predecessors in other graphs. */
353 if (get_irn_op(n) == op_Filter)
354 n = get_nodes_Block(n);
355 if (get_irn_op(n) == op_Block) {
356 ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
357 if (is_ip_cfop(cfop)) {
358 current_ir_graph = get_irn_irg(cfop);
359 set_irg_visited(current_ir_graph, get_max_irg_visited());
367 /* Walks up the stack passing n and then finding the node
368 where we walked into the irg n is contained in.
369 Here we switch the irg. */
371 find_irg_on_stack (ir_node *n) {
373 ir_graph *old_current = current_ir_graph;
376 if (interprocedural_view) {
377 for (i = tos; i >= 0; i--) {
378 if (stack[i] == n) break;
385 for (; i >= 0; i--) {
387 //printf(" Visiting %d ", i); DDMN(m);
389 current_ir_graph = get_irn_irg(m);
392 if (get_irn_op(m) == op_Filter) {
393 /* Find the corresponding ip_cfop */
394 ir_node *pred = stack[i+1];
396 for (j = 0; j < get_Filter_n_cg_preds(m); j++)
397 if (get_Filter_cg_pred(m, j) == pred) break;
398 if (j >= get_Filter_n_cg_preds(m))
399 /* It is a filter we didn't pass as the predecessors are marked. */
401 assert(get_Filter_cg_pred(m, j) == pred);
411 /* Returns true if n is a loop header, i.e., it is a Block, Phi
412 or Filter node and has predecessors within the loop and out
415 is_head (ir_node *n, ir_node *root)
418 int some_outof_loop = 0, some_in_loop = 0;
420 /* Test for legal loop header */
421 if (!((get_irn_op(n) == op_Block) ||
422 (get_irn_op(n) == op_Phi) ||
423 ((get_irn_op(n) == op_Filter) && interprocedural_view)))
426 if (!is_outermost_Start(n)) {
427 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
428 ir_node *pred = get_irn_n(n, i);
430 if (is_backedge(n, i)) continue;
431 if (!irn_is_in_stack(pred)) {
434 assert(get_irn_uplink(pred) >= get_irn_uplink(root));
439 return some_outof_loop && some_in_loop;
442 /* Returns index of the predecessor with the smallest dfn number
443 greater-equal than limit. */
445 smallest_dfn_pred (ir_node *n, int limit)
447 int i, index = -2, min = -1;
449 if (!is_outermost_Start(n)) {
450 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
451 ir_node *pred = get_irn_n(n, i);
453 if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
454 if (get_irn_dfn(pred) >= limit
455 && (min == -1 || get_irn_dfn(pred) < min)) {
457 min = get_irn_dfn(pred);
464 /* Returns index of the predecessor with the largest dfn number. */
466 largest_dfn_pred (ir_node *n)
468 int i, index = -2, max = -1;
470 if (!is_outermost_Start(n)) {
471 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
472 ir_node *pred = get_irn_n(n, i);
473 if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
474 if (get_irn_dfn(pred) > max) {
476 max = get_irn_dfn(pred);
483 /* Searches the stack for possible loop heads. Tests these for backedges.
484 If it finds a head with an unmarked backedge it marks this edge and
485 returns the tail of the loop.
486 If it finds no backedge returns NULL. */
488 find_tail (ir_node *n) {
490 int i, res_index = -2;
493 if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
497 if (is_head (m, n)) {
498 res_index = smallest_dfn_pred(m, 0);
499 if ((res_index == -2) && /* no smallest dfn pred found. */
503 if (m == n) return NULL;
504 for (i = tos-2; ; --i) {
506 if (is_head (m, n)) {
507 res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
508 if (res_index == -2) /* no smallest dfn pred found. */
509 res_index = largest_dfn_pred (m);
514 assert (res_index > -2);
516 set_backedge (m, res_index);
517 return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
521 /* The core algorithm. *****************************************/
523 void scc (ir_node *n) {
527 if (irn_visited(n)) return;
530 /* Initialize the node */
531 set_irn_dfn(n, current_dfn); /* Depth first number for this node */
532 set_irn_uplink(n, current_dfn); /* ... is default uplink. */
533 set_irn_loop_tmp(n, NULL);
536 /* What's this good for?
537 n->ana.scc.section = NULL;
542 if (!is_outermost_Start(n)) {
543 for (i = get_start_index(n); i < get_irn_arity(n); i++) {
545 if (is_backedge(n, i)) continue;
547 m = get_irn_ip_pred(n, i);
552 if (irn_is_in_stack(m)) {
553 /* Uplink of m is smaller if n->m is a backedge.
554 Propagate the uplink to mark the loop. */
555 if (get_irn_uplink(m) < get_irn_uplink(n))
556 set_irn_uplink(n, get_irn_uplink(m));
560 if (get_irn_dfn(n) == get_irn_uplink(n)) {
561 /* This condition holds for the node with the incoming backedge. */
562 ir_node *tail = find_tail(n);
564 /* We found a new loop! */
565 ir_loop *l = new_loop();
566 /* Remove the loop from the stack ... */
567 pop_scc_unmark_visit (n);
568 /* and recompute it in a better order; and so that it goes into
570 rem = find_irg_on_stack(tail);
572 current_ir_graph = rem;
574 assert (irn_visited(n));
583 /* Constructs backedge information for irg. In interprocedural view constructs
584 backedges for all methods called by irg, too. */
585 void construct_backedges(ir_graph *irg) {
586 ir_graph *rem = current_ir_graph;
590 current_ir_graph = irg;
591 outermost_ir_graph = irg;
596 new_loop(); /* sets current_loop */
597 head_rem = current_loop; /* Just for assertion */
599 if (interprocedural_view) {
600 set_irg_visited(irg, inc_max_irg_visited());
603 inc_irg_visited(irg);
606 scc(get_irg_end(irg));
607 for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
608 scc(get_End_keepalive(get_irg_end(irg), i));
610 if (interprocedural_view) finish_ip_walk();
612 assert(head_rem == current_loop);
613 set_irg_loop(irg, current_loop);
614 assert(get_irg_loop(irg)->kind == k_ir_loop);
616 irg->loops = current_loop;
620 count_loop (the_loop, &count, &depth);
624 current_ir_graph = rem;