Fixed typo --flo
[libfirm] / ir / ana / irscc.c
1 /*
2  * Project:     libFIRM
3  * File name:   ir/ana/irscc.c
4  * Purpose:     Compute the strongly connected regions and build
5  *              backedge/loop datastructures.
6  *              A variation on the Tarjan algorithm. See also [Trapp:99],
7  *              Chapter 5.2.1.2.
8  * Author:      Goetz Lindenmaier
9  * Modified by:
10  * Created:     7.2002
11  * CVS-ID:      $Id$
12  * Copyright:   (c) 2002-2003 Universität Karlsruhe
13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
14  */
15
16 #ifdef HAVE_CONFIG_H
17 #include "config.h"
18 #endif
19
20 #include <string.h>
21
22 #include "irloop_t.h"
23 #include "irnode_t.h"
24 #include "irgraph_t.h"
25 #include "array.h"
26 #include "pmap.h"
27 #include "irgwalk.h"
28 #include "irprog_t.h"
29 #include "irdump.h"
30
31 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
32                       for */
33 static ir_loop *current_loop;      /* Current loop construction is working
34                       on. */
35 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
36                       Each loop node gets a unique number.
37                       What for? ev. remove. @@@ */
38 static int current_dfn = 1;        /* Counter to generate depth first numbering
39                       of visited nodes.  */
40
41 /**********************************************************************/
42 /* Node attributes                                                   **/
43 /**********************************************************************/
44
45 /* A map to get from irnodes to loop nodes. */
46 static pmap *node_loop_map = NULL;
47
48 /**********************************************************************/
49 /* Node attributes needed for the construction.                      **/
50 /**********************************************************************/
51
52 typedef struct scc_info {
53   bool in_stack;         /* Marks whether node is on the stack. */
54   int dfn;               /* Depth first search number. */
55   int uplink;            /* dfn number of ancestor. */
56   //  ir_loop *loop;         /* Refers to the containing loop. */
57   /*
58       struct section *section;
59       xset def;
60       xset use;
61   */
62 } scc_info;
63
64 static INLINE scc_info* new_scc_info(void) {
65   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
66   memset (info, 0, sizeof (scc_info));
67   return info;
68 }
69
70 static INLINE void
71 mark_irn_in_stack (ir_node *n) {
72   assert(get_irn_link(n));
73   // to slow
74   //((scc_info *)get_irn_link(n))->in_stack = true;
75   ((scc_info *)n->link)->in_stack = true;
76 }
77
78 static INLINE void
79 mark_irn_not_in_stack (ir_node *n) {
80   assert(get_irn_link(n));
81   // to slow
82   //((scc_info *)get_irn_link(n))->in_stack = false;
83   ((scc_info *)n->link)->in_stack = false;
84 }
85
86 static INLINE bool
87 irn_is_in_stack (ir_node *n) {
88   assert(get_irn_link(n));
89   // to slow
90   //return ((scc_info *)get_irn_link(n))->in_stack;
91   return ((scc_info *)n->link)->in_stack;
92 }
93
94 static INLINE void
95 set_irn_uplink (ir_node *n, int uplink) {
96   assert(get_irn_link(n));
97   // to slow
98   //((scc_info *)get_irn_link(n))->uplink = uplink;
99   ((scc_info *)n->link)->uplink = uplink;
100 }
101
102 static INLINE int
103 get_irn_uplink (ir_node *n) {
104   assert(get_irn_link(n));
105   // to slow
106   //return ((scc_info *)get_irn_link(n))->uplink;
107   return ((scc_info *)n->link)->uplink;
108 }
109
110 static INLINE void
111 set_irn_dfn (ir_node *n, int dfn) {
112   assert(get_irn_link(n));
113   // to slow
114   //((scc_info *)get_irn_link(n))->dfn = dfn;
115   ((scc_info *)n->link)->dfn = dfn;
116 }
117
118 static INLINE int
119 get_irn_dfn (ir_node *n) {
120   assert(get_irn_link(n));
121   // to slow
122   //return ((scc_info *)get_irn_link(n))->dfn;
123   return ((scc_info *)n->link)->dfn;
124 }
125
126 #if 0
127 /* Replaced node loop map by real field as hash access dominates runtime
128  * of the algorithm. ! */
129 /* Uses temporary information to set the loop */
130 static INLINE void
131 set_irn_loop (ir_node *n, ir_loop* loop) {
132   assert(node_loop_map && "not initialized!");
133   pmap_insert(node_loop_map, (void *)n, (void *)loop);
134 }
135
136 /* Uses temporary information to get the loop */
137 INLINE ir_loop *
138 get_irn_loop (ir_node *n) {
139   ir_loop *res = NULL;
140   if (!node_loop_map) return NULL;
141
142   if (pmap_contains(node_loop_map, (void *)n))
143     res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
144
145   return res;
146 }
147 #else
148 static INLINE void
149 set_irn_loop (ir_node *n, ir_loop* loop) {
150   n->loop = loop;
151 }
152
153 /* Uses temporary information to get the loop */
154 INLINE ir_loop *
155 get_irn_loop (ir_node *n) {
156   return n->loop;
157 }
158 #endif
159
160
161 #if 0
162 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
163   int i;
164   ir_loop *res = NULL;
165
166   /* Test whether n is contained in this loop. */
167   for (i = 0; i < get_loop_n_nodes(l); i++)
168     if (n == get_loop_node(l, i)) return l;
169
170   /* Is this a leave in the loop tree? If so loop not found. */
171   if (get_loop_n_sons(l) == 0) return NULL;
172
173   /* Else descend in the loop tree. */
174   for (i = 0; i < get_loop_n_sons(l); i++) {
175     res = find_nodes_loop(n, get_loop_son(l, i));
176     if (res) break;
177   }
178   return res;
179 }
180
181 /* @@@ temporary implementation, costly!!! */
182 ir_loop * get_irn_loop(ir_node *n) {
183   ir_loop *l = get_irg_loop(current_ir_graph);
184   l = find_nodes_loop(n, l);
185   return l;
186 }
187 #endif
188
189 /**********************************************************************/
190 /* A stack.                                                          **/
191 /**********************************************************************/
192
193 static ir_node **stack = NULL;
194 static int tos = 0;                /* top of stack */
195
196 static INLINE void init_stack(void) {
197   if (stack) {
198     ARR_RESIZE (ir_node *, stack, 1000);
199   } else {
200     stack = NEW_ARR_F (ir_node *, 1000);
201   }
202   tos = 0;
203 }
204
205 #if 0
206 static INLINE void free_stack(void) {
207   DEL_ARR_F(stack);
208   stack = NULL;
209   tos = 0;
210 }
211 #endif
212
213 static INLINE void
214 push (ir_node *n)
215 {
216   /*DDMN(n);*/
217
218   if (tos == ARR_LEN (stack)) {
219     int nlen = ARR_LEN (stack) * 2;
220     ARR_RESIZE (ir_node *, stack, nlen);
221   }
222   stack [tos++] = n;
223   mark_irn_in_stack(n);
224 }
225
226 static INLINE ir_node *
227 pop (void)
228 {
229   ir_node *n = stack[--tos];
230   mark_irn_not_in_stack(n);
231   return n;
232 }
233
234 /* The nodes up to n belong to the current loop.
235    Removes them from the stack and adds them to the current loop. */
236 static INLINE void
237 pop_scc_to_loop (ir_node *n)
238 {
239   ir_node *m;
240   int i = 0;
241
242   /*for (;;) {*/
243   do
244     {
245     m = pop();
246     loop_node_cnt++;
247     set_irn_dfn(m, loop_node_cnt);
248     add_loop_node(current_loop, m);
249     set_irn_loop(m, current_loop);
250     i++;
251     /*    if (m==n) break;*/
252     } while(m != n);
253
254   if(i > 1)
255     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
256 }
257
258 /* GL ??? my last son is my grandson???  Removes loops with no
259    ir_nodes in them.  Such loops have only another loop as son. (Why
260    can't they have two loops as sons? Does it never get that far? ) */
261 void close_loop (ir_loop *l)
262 {
263   int last = get_loop_n_elements(l) - 1;
264   loop_element lelement = get_loop_element(l, last);
265   ir_loop *last_son = lelement.son;
266
267   if (get_kind(last_son) == k_ir_loop &&
268       get_loop_n_elements(last_son) == 1)
269     {
270       ir_loop *gson;
271
272       lelement = get_loop_element(last_son, 0);
273       gson = lelement.son;
274       if(get_kind(gson) == k_ir_loop)
275     {
276           loop_element new_last_son;
277
278       gson -> outer_loop = l;
279           new_last_son.son = gson;
280       l -> children[last] = new_last_son;
281     }
282     }
283
284   current_loop = l;
285 }
286
287 /* Removes and unmarks all nodes up to n from the stack.
288    The nodes must be visited once more to assign them to a scc. */
289 static INLINE void
290 pop_scc_unmark_visit (ir_node *n)
291 {
292   ir_node *m = NULL;
293
294   while (m != n) {
295     m = pop();
296     set_irn_visited(m, 0);
297   }
298 }
299
300 /**********************************************************************/
301 /* The loop datastructure.                                           **/
302 /**********************************************************************/
303
304 /* Allocates a new loop as son of current_loop.  Sets current_loop
305    to the new loop and returns the father. */
306 static ir_loop *new_loop (void) {
307   ir_loop *father, *son;
308
309   father = current_loop;
310
311   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
312   memset (son, 0, sizeof (ir_loop));
313   son->kind = k_ir_loop;
314   son->children = NEW_ARR_F (loop_element, 0);
315   son->n_nodes = 0;
316   son->n_sons=0;
317   if (father) {
318     son->outer_loop = father;
319     add_loop_son(father, son);
320     son->depth = father->depth+1;
321   } else {  /* The root loop */
322     son->outer_loop = son;
323     son->depth = 0;
324   }
325
326 #ifdef DEBUG_libfirm
327   son->loop_nr = get_irp_new_node_nr();
328   son->link = NULL;
329 #endif
330
331   current_loop = son;
332   return father;
333 }
334
335 #if 0
336 /* Finishes the datastructures, copies the arrays to the obstack
337    of current_ir_graph.
338    A. Schoesser: Caution: loop -> sons is gone. */
339 static void mature_loop (ir_loop *loop) {
340   ir_loop **new_sons;
341
342   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
343   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
344   DEL_ARR_F(loop->sons);
345   loop->sons = new_sons;
346 }
347 #endif
348
349 /* Returns outer loop, itself if outermost. */
350 ir_loop *get_loop_outer_loop (ir_loop *loop) {
351   assert(loop && loop->kind == k_ir_loop);
352   return loop->outer_loop;
353 }
354
355 /* Returns nesting depth of this loop */
356 int get_loop_depth (ir_loop *loop) {
357   assert(loop); assert(loop->kind == k_ir_loop);
358   return loop->depth;
359 }
360
361 /* Returns the number of inner loops */
362 int      get_loop_n_sons (ir_loop *loop) {
363   assert(loop && loop->kind == k_ir_loop);
364   return(loop -> n_sons);
365 }
366
367 /* Returns the pos`th loop_node-child              *
368  * TODO: This method isn`t very efficient !        *
369  * Returns NULL if there isnt`t a pos`th loop_node */
370 ir_loop *get_loop_son (ir_loop *loop, int pos) {
371   int child_nr = 0, loop_nr = -1;
372
373   assert(loop && loop->kind == k_ir_loop);
374   while(child_nr < ARR_LEN(loop->children))
375    {
376     if(*(loop -> children[child_nr].kind) == k_ir_loop)
377       loop_nr++;
378     if(loop_nr == pos)
379       return(loop -> children[child_nr].son);
380     child_nr++;
381    }
382   return NULL;
383 }
384
385 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
386    is invalid! */
387
388 static INLINE void
389 add_loop_son(ir_loop *loop, ir_loop *son) {
390   loop_element lson;
391   lson.son = son;
392   assert(loop && loop->kind == k_ir_loop);
393   assert(get_kind(son) == k_ir_loop);
394   ARR_APP1 (loop_element, loop->children, lson);
395   loop -> n_sons++;
396 }
397
398 /* Returns the number of nodes in the loop */
399 int      get_loop_n_nodes (ir_loop *loop) {
400   assert(loop); assert(loop->kind == k_ir_loop);
401   return loop -> n_nodes;
402 /*  return ARR_LEN(loop->nodes); */
403 }
404
405 /* Returns the pos`th ir_node-child                *
406  * TODO: This method isn`t very efficient !        *
407  * Returns NULL if there isnt`t a pos`th ir_node   */
408 ir_node *get_loop_node (ir_loop *loop, int pos) {
409   int child_nr, node_nr = -1;
410
411   assert(loop && loop->kind == k_ir_loop);
412   assert(pos < get_loop_n_nodes(loop));
413
414   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
415     if(*(loop -> children[child_nr].kind) == k_ir_node)
416       node_nr++;
417     if(node_nr == pos)
418       return(loop -> children[child_nr].node);
419   }
420   assert(0 && "no child at pos found");
421   return NULL;
422 }
423
424 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
425    is invalid! */
426
427 static INLINE void
428 add_loop_node(ir_loop *loop, ir_node *n) {
429   loop_element ln;
430   ln.node = n;
431   assert(loop && loop->kind == k_ir_loop);
432   assert(get_kind(n) == k_ir_node);
433   ARR_APP1 (loop_element, loop->children, ln);
434   loop->n_nodes++;
435 }
436
437 /** Returns the number of elements contained in loop.  */
438 int get_loop_n_elements (ir_loop *loop) {
439   assert(loop && loop->kind == k_ir_loop);
440   return(ARR_LEN(loop->children));
441 }
442
443 /*
444  Returns the pos`th loop element.
445  This may be a loop_node or a ir_node. The caller of this function has
446  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
447  and then select the apropriate "loop_element.node" or "loop_element.son".
448 */
449
450 loop_element get_loop_element (ir_loop *loop, int pos) {
451   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
452
453   return(loop -> children[pos]);
454 }
455
456 int get_loop_element_pos(ir_loop *loop, void *le) {
457   int i;
458   assert(loop && loop->kind == k_ir_loop);
459
460   for (i = 0; i < get_loop_n_elements(loop); i++)
461     if (get_loop_element(loop, i).node == le) return i;
462   return -1;
463 }
464
465 int get_loop_loop_nr(ir_loop *loop) {
466   assert(loop && loop->kind == k_ir_loop);
467 #ifdef DEBUG_libfirm
468   return loop->loop_nr;
469 #else
470   return (int)loop;
471 #endif
472 }
473
474
475 /** A field to connect additional information to a loop.  Only valid
476     if libfirm_debug is set. */
477 void  set_loop_link (ir_loop *loop, void *link) {
478   assert(loop && loop->kind == k_ir_loop);
479 #ifdef DEBUG_libfirm
480   loop->link = link;
481 #endif
482 }
483 void *get_loop_link (const ir_loop *loop) {
484   assert(loop && loop->kind == k_ir_loop);
485 #ifdef DEBUG_libfirm
486   return loop->link;
487 #else
488   return NULL;
489 #endif
490 }
491
492 /* The outermost loop is remarked in the surrounding graph. */
493 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
494   assert(irg);
495   irg->loop = loop;
496 }
497 ir_loop *get_irg_loop(ir_graph *irg) {
498   assert(irg);
499   return irg->loop;
500 }
501
502
503 /**********************************************************************/
504 /* Constructing and destructing the loop/backedge information.       **/
505 /**********************************************************************/
506
507 /* Initialization steps. **********************************************/
508
509 static INLINE void
510 init_node (ir_node *n, void *env) {
511   set_irn_link (n, new_scc_info());
512   clear_backedges(n);
513 #if 0
514   /* Also init nodes not visible in intraproc_view. */
515     /* @@@ init_node is called for too many nodes -- this wastes memory!.
516        The mem is not lost as its on the obstack. */
517   if (get_irn_op(n) == op_Filter) {
518     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
519       init_node(get_Filter_cg_pred(n, i), NULL);
520   }
521   if (get_irn_op(n) == op_Block) {
522     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
523       init_node(get_Block_cg_cfgpred(n, i), NULL);
524     }
525   }
526   /* The following pattern matches only after a call from above pattern. */
527   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
528     /* @@@ init_node is called for every proj -- this wastes memory!.
529        The mem is not lost as its on the obstack. */
530     ir_node *cb = get_Proj_pred(n);
531     if ((get_irn_op(cb) == op_CallBegin) ||
532     (get_irn_op(cb) == op_EndReg) ||
533     (get_irn_op(cb) == op_EndExcept)) {
534       init_node(cb, NULL);
535       init_node(get_nodes_Block(cb), NULL);
536     }
537   }
538 #endif
539 }
540
541 static INLINE void
542 init_scc_common (void) {
543   current_dfn = 1;
544   loop_node_cnt = 0;
545   if (!node_loop_map) node_loop_map = pmap_create();
546   init_stack();
547 }
548
549 static INLINE void
550 init_scc (ir_graph *irg) {
551   init_scc_common();
552   irg_walk_graph (irg, init_node, NULL, NULL);
553   /*
554   irg_walk (irg, link_to_reg_end, NULL, NULL);
555   */
556 }
557
558 static INLINE void
559 init_ip_scc (void) {
560   init_scc_common();
561   cg_walk (init_node, NULL, NULL);
562 }
563
564 /* Condition for breaking the recursion. */
565 static bool is_outermost_Start(ir_node *n) {
566   /* Test whether this is the outermost Start node.  If so
567      recursion must end. */
568   if ((get_irn_op(n) == op_Block)     &&
569       (get_Block_n_cfgpreds(n) == 1)  &&
570       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
571       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
572     return true;
573   }
574 #if 0
575   /*  @@@ Bad condition:
576       not possible in interprocedural view as outermost_graph is
577       not necessarily the only with a dead-end start block.
578       Besides current_ir_graph is not set properly. */
579   if ((get_irn_op(n) == op_Block) &&
580       (n == get_irg_start_block(current_ir_graph))) {
581     if ((!interprocedural_view)  ||
582     (current_ir_graph == outermost_ir_graph))
583       return true;
584   }
585 #endif
586   return false;
587 }
588
589 /* Don't walk from nodes to blocks except for Control flow operations. */
590 static INLINE int
591 get_start_index(ir_node *n) {
592   if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
593     return -1;
594   else
595     return 0;
596 }
597 #if 0
598 /* Returns current_ir_graph and set it to the irg of predecessor index
599    of node n. */
600 static INLINE ir_graph *
601 switch_irg (ir_node *n, int index) {
602   ir_graph *old_current = current_ir_graph;
603
604   if (interprocedural_view) {
605     /* Only Filter and Block nodes can have predecessors in other graphs. */
606     if (get_irn_op(n) == op_Filter)
607       n = get_nodes_Block(n);
608     if (get_irn_op(n) == op_Block) {
609       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
610       if (is_ip_cfop(cfop)) {
611     current_ir_graph = get_irn_irg(cfop);
612     set_irg_visited(current_ir_graph, get_max_irg_visited());
613       }
614     }
615   }
616
617   return old_current;
618 }
619
620 /* Walks up the stack passing n and then finding the node
621    where we walked into the irg n is contained in.
622    Here we switch the irg. */
623 static ir_graph *
624 find_irg_on_stack (ir_node *n) {
625   ir_node *m;
626   ir_graph *old_current = current_ir_graph;
627   int i;
628
629   if (interprocedural_view) {
630     for (i = tos; i >= 0; i--) {
631       if (stack[i] == n) break;
632     }
633     if (i < 0) i = tos;
634
635     assert (i >= 0);
636     for (; i >= 0; i--) {
637       m = stack[i];
638       /*printf(" Visiting %d ", i); DDMN(m);*/
639       if (is_ip_cfop(m)) {
640     current_ir_graph = get_irn_irg(m);
641     break;
642       }
643       if (get_irn_op(m) == op_Filter) {
644     /* Find the corresponding ip_cfop */
645     ir_node *pred = stack[i+1];
646     int j;
647     for (j = 0; j < get_Filter_n_cg_preds(m); j++)
648       if (get_Filter_cg_pred(m, j) == pred) break;
649     if (j >= get_Filter_n_cg_preds(m))
650       /* It is a filter we didn't pass as the predecessors are marked. */
651       continue;
652     assert(get_Filter_cg_pred(m, j) == pred);
653     switch_irg(m, j);
654     break;
655       }
656     }
657   }
658
659   return old_current;
660 }
661 #endif
662
663 #if 0
664 static void test(ir_node *pred, ir_node *root, ir_node *this) {
665   int i;
666   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
667
668   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
669   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
670   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
671
672   printf("tos: %d\n", tos);
673
674   for (i = tos; i >= 0; i--) {
675     ir_node *n = stack[i];
676     if (!n) continue;
677     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
678   }
679 }
680 #endif
681
682 /* Test for legal loop header: Block, Phi, ... */
683 INLINE static bool is_possible_loop_head(ir_node *n) {
684   ir_op *op = get_irn_op(n);
685   return ((op == op_Block) ||
686       (op == op_Phi) ||
687       ((op == op_Filter) && interprocedural_view));
688 }
689
690 /* Returns true if n is a loop header, i.e., it is a Block, Phi
691    or Filter node and has predecessors within the loop and out
692    of the loop.
693    @arg root: only needed for assertion. */
694 static bool
695 is_head (ir_node *n, ir_node *root)
696 {
697   int i, arity;
698   int some_outof_loop = 0, some_in_loop = 0;
699
700   /* Test for legal loop header: Block, Phi, ... */
701   if (!is_possible_loop_head(n))
702     return false;
703   if (!is_outermost_Start(n)) {
704     arity = get_irn_arity(n);
705     for (i = get_start_index(n); i < arity; i++) {
706       ir_node *pred = get_irn_n(n, i);
707       assert(pred);
708       if (is_backedge(n, i)) continue;
709       if (!irn_is_in_stack(pred)) {
710     some_outof_loop = 1;
711       } else {
712     assert(get_irn_uplink(pred) >= get_irn_uplink(root));
713     some_in_loop = 1;
714       }
715     }
716   }
717   return some_outof_loop && some_in_loop;
718 }
719
720 /* Returns index of the predecessor with the smallest dfn number
721    greater-equal than limit. */
722 static int
723 smallest_dfn_pred (ir_node *n, int limit)
724 {
725   int i, index = -2, min = -1;
726
727   if (!is_outermost_Start(n)) {
728     int arity = get_irn_arity(n);
729     for (i = get_start_index(n); i < arity; i++) {
730       ir_node *pred = get_irn_n(n, i);
731       assert(pred);
732       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
733       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
734     index = i;
735     min = get_irn_dfn(pred);
736       }
737     }
738   }
739   return index;
740 }
741
742 /* Returns index of the predecessor with the largest dfn number. */
743 static int
744 largest_dfn_pred (ir_node *n)
745 {
746   int i, index = -2, max = -1;
747
748   if (!is_outermost_Start(n)) {
749     int arity = get_irn_arity(n);
750     for (i = get_start_index(n); i < arity; i++) {
751       ir_node *pred = get_irn_n(n, i);
752       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
753       if (get_irn_dfn(pred) > max) {
754     index = i;
755     max = get_irn_dfn(pred);
756       }
757     }
758   }
759   return index;
760 }
761
762 /* Searches the stack for possible loop heads.  Tests these for backedges.
763    If it finds a head with an unmarked backedge it marks this edge and
764    returns the tail of the loop.
765    If it finds no backedge returns NULL.
766    ("disable_backedge" in fiasco) */
767
768 static ir_node *
769 find_tail (ir_node *n) {
770   ir_node *m;
771   int i, res_index = -2;
772
773   /*
774     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
775   */
776
777   m = stack[tos-1];  /* tos = top of stack */
778   if (is_head (m, n)) {
779     res_index = smallest_dfn_pred(m, 0);
780     if ((res_index == -2) &&  /* no smallest dfn pred found. */
781     (n == m))
782       return NULL;
783   } else {
784     if (m == n) return NULL;
785     for (i = tos-2; ; --i) {
786       m = stack[i];
787       if (is_head (m, n)) {
788     res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
789     if (res_index == -2)  /* no smallest dfn pred found. */
790       res_index = largest_dfn_pred (m);
791     break;
792       }
793     }
794   }
795   assert (res_index > -2);
796
797   set_backedge (m, res_index);
798   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
799 }
800
801
802 /* The core algorithm. *****************************************/
803
804 static void scc (ir_node *n) {
805   int i;
806   if (irn_visited(n)) return;
807   mark_irn_visited(n);
808
809   /* Initialize the node */
810   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
811   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
812   set_irn_loop(n, NULL);
813   current_dfn ++;
814   push(n);
815
816   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
817      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
818      so is_backedge does not access array[-1] but correctly returns false! */
819
820   if (!is_outermost_Start(n)) {
821     int arity = get_irn_arity(n);
822     for (i = get_start_index(n); i < arity; i++) {
823       ir_node *m;
824       if (is_backedge(n, i)) continue;
825
826       m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
827       //if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
828       scc (m);
829       if (irn_is_in_stack(m)) {
830     /* Uplink of m is smaller if n->m is a backedge.
831        Propagate the uplink to mark the loop. */
832     if (get_irn_uplink(m) < get_irn_uplink(n))
833       set_irn_uplink(n, get_irn_uplink(m));
834       }
835     }
836   }
837
838   if (get_irn_dfn(n) == get_irn_uplink(n)) {
839     /* This condition holds for the node with the incoming backedge.
840        AS: That is: For the loop head. */
841     ir_node *tail = find_tail(n);
842     if (tail) {
843       /* We found a new inner loop! */
844
845       /* This is an adaption of the algorithm from fiasco / optscc to
846        * avoid loops without Block or Phi as first node.  This should
847        * severely reduce the number of evaluations of nodes to detect
848        * a fixpoint in the heap analyses.
849        * Further it avoids loops without firm nodes that cause errors
850        * in the heap analyses. */
851 #define NO_LOOPS_WITHOUT_HEAD 1
852 #if NO_LOOPS_WITHOUT_HEAD
853       ir_loop *l;
854       int close;
855       if (get_loop_n_elements(current_loop) > 0) {
856     l = new_loop();
857     close = 1;
858       } else {
859     l = current_loop;
860     close = 0;
861       }
862 #else
863       ir_loop *l = new_loop();
864 #endif
865
866       /* Remove the loop from the stack ... */
867       pop_scc_unmark_visit (n);
868       /* and recompute it in a better order; and so that it goes into
869      the new loop. */
870       // GL @@@ remove experimental stuff rem = find_irg_on_stack(tail);
871
872       scc (tail);
873       // GL @@@ remove experimental stuff current_ir_graph = rem;
874
875       assert (irn_visited(n));
876 #if NO_LOOPS_WITHOUT_HEAD
877       if (close)
878 #endif
879       close_loop(l);
880     } else {
881       /* AS: No inner loop was found. Pop all nodes from the stack
882      to the current loop. */
883       pop_scc_to_loop(n);
884     }
885   }
886 }
887
888 /* Constructs backedge information for irg. In interprocedural view constructs
889    backedges for all methods called by irg, too. */
890 void construct_backedges(ir_graph *irg) {
891   ir_graph *rem = current_ir_graph;
892   ir_loop *head_rem;
893
894   assert(!interprocedural_view &&
895      "not implemented, use construct_ip_backedges");
896
897   current_ir_graph = irg;
898   outermost_ir_graph = irg;
899
900   init_scc(current_ir_graph);
901
902   current_loop = NULL;
903   new_loop();  /* sets current_loop */
904   head_rem = current_loop; /* Just for assertion */
905
906   if (interprocedural_view) {
907     set_irg_visited(current_ir_graph, inc_max_irg_visited());
908     init_ip_walk ();
909   } else {
910     inc_irg_visited(current_ir_graph);
911   }
912
913   scc(get_irg_end(current_ir_graph));
914
915   if (interprocedural_view) finish_ip_walk();
916
917   assert(head_rem == current_loop);
918   set_irg_loop(current_ir_graph, current_loop);
919   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
920   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
921   /*
922   irg->loops = current_loop;
923   if (icfg == 1) {
924     int count = 0;
925     int depth = 0;
926     count_loop (the_loop, &count, &depth);
927     }
928   }
929   */
930   current_ir_graph = rem;
931 }
932
933
934 #if 0
935 void construct_ip_backedges (void) {
936   ir_graph *rem = current_ir_graph;
937   int rem_ipv = interprocedural_view;
938   int i, j;
939
940   outermost_ir_graph = get_irp_main_irg();
941
942   init_ip_scc();
943
944   current_loop = NULL;
945   new_loop();  /* sets current_loop */
946   interprocedural_view = 1;
947
948   inc_max_irg_visited();
949   for (i = 0; i < get_irp_n_irgs(); i++)
950     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
951
952   for (i = 0; i < get_irp_n_irgs(); i++) {
953     ir_node *sb;
954     current_ir_graph = get_irp_irg(i);
955     /* Find real entry points */
956     sb = get_irg_start_block(current_ir_graph);
957     if ((get_Block_n_cfgpreds(sb) > 1) ||
958     (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
959     /* Compute scc for this graph */
960     outermost_ir_graph = current_ir_graph;
961     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
962     scc(get_irg_end(current_ir_graph));
963     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
964       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
965   }
966
967   set_irg_loop(outermost_ir_graph, current_loop);
968   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
969   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
970
971   current_ir_graph = rem;
972   interprocedural_view = rem_ipv;
973 }
974 #else
975 void construct_ip_backedges (void) {
976   ir_graph *rem = current_ir_graph;
977   int rem_ipv = interprocedural_view;
978   int i;
979
980   outermost_ir_graph = get_irp_main_irg();
981
982   init_ip_scc();
983
984   current_loop = NULL;
985   new_loop();  /* sets current_loop */
986   interprocedural_view = 1;
987
988   inc_max_irg_visited();
989   for (i = 0; i < get_irp_n_irgs(); i++)
990     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
991
992   /** We have to start the walk at the same nodes as cg_walk. **/
993   /* Walk starting at unreachable procedures. Only these
994    * have End blocks visible in interprocedural view. */
995   for (i = 0; i < get_irp_n_irgs(); i++) {
996     ir_node *sb;
997     current_ir_graph = get_irp_irg(i);
998
999     sb = get_irg_start_block(current_ir_graph);
1000
1001     if ((get_Block_n_cfgpreds(sb) > 1) ||
1002     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1003
1004     scc(get_irg_end(current_ir_graph));
1005   }
1006
1007   /* Check whether we walked all procedures: there could be procedures
1008      with cyclic calls but no call from the outside. */
1009   for (i = 0; i < get_irp_n_irgs(); i++) {
1010     ir_node *sb;
1011     current_ir_graph = get_irp_irg(i);
1012
1013     /* Test start block: if inner procedure end and end block are not
1014      * visible and therefore not marked. */
1015     sb = get_irg_start_block(current_ir_graph);
1016     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1017   }
1018
1019   /* Walk all endless loops in inner procedures.
1020    * We recognize an inner procedure if the End node is not visited. */
1021   for (i = 0; i < get_irp_n_irgs(); i++) {
1022     ir_node *e;
1023     current_ir_graph = get_irp_irg(i);
1024
1025     e = get_irg_end(current_ir_graph);
1026     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1027       int j;
1028       /* Don't visit the End node. */
1029       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1030     }
1031   }
1032
1033   set_irg_loop(outermost_ir_graph, current_loop);
1034   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1035   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1036
1037   current_ir_graph = rem;
1038   interprocedural_view = rem_ipv;
1039 }
1040 #endif
1041
1042 static void reset_backedges(ir_node *n) {
1043   if (is_possible_loop_head(n)) {
1044     int rem = interprocedural_view;
1045     interprocedural_view = 1;
1046     clear_backedges(n);
1047     interprocedural_view = 0;
1048     clear_backedges(n);
1049     interprocedural_view = rem;
1050   }
1051 }
1052
1053 static void loop_reset_backedges(ir_loop *l) {
1054   int i;
1055   reset_backedges(get_loop_node(l, 0));
1056   for (i = 0; i < get_loop_n_nodes(l); ++i)
1057     set_irn_loop(get_loop_node(l, i), NULL);
1058   for (i = 0; i < get_loop_n_sons(l); ++i) {
1059     loop_reset_backedges(get_loop_son(l, i));
1060   }
1061 }
1062
1063 /** Removes all loop information.
1064     Resets all backedges */
1065 void free_loop_information(ir_graph *irg) {
1066   if (get_irg_loop(irg))
1067     loop_reset_backedges(get_irg_loop(irg));
1068   set_irg_loop(irg, NULL);
1069   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1070   /* We cannot free the loop nodes, they are on the obstack. */
1071 }
1072
1073
1074 void free_all_loop_information (void) {
1075   int i;
1076   int rem = interprocedural_view;
1077   interprocedural_view = 1;  /* To visit all filter nodes */
1078   for (i = 0; i < get_irp_n_irgs(); i++) {
1079     free_loop_information(get_irp_irg(i));
1080   }
1081   pmap_destroy(node_loop_map);
1082   node_loop_map = NULL;
1083   interprocedural_view = rem;
1084 }
1085
1086
1087
1088
1089
1090 /* Debug stuff *************************************************/
1091
1092 static int test_loop_node(ir_loop *l) {
1093   int i, has_node = 0, found_problem = 0;
1094   loop_element le;
1095
1096   assert(l && l->kind == k_ir_loop);
1097
1098   if (get_loop_n_elements(l) == 0) {
1099     printf(" Loop completely empty! "); DDML(l);
1100     found_problem = 1;
1101     dump_loop(l, "-ha");
1102   }
1103
1104   le = get_loop_element(l, 0);
1105   if (*(le.kind) != k_ir_node) {
1106     assert(le.kind && *(le.kind) == k_ir_loop);
1107     printf(" First loop element is not a node! "); DDML(l);
1108     printf("                                   "); DDML(le.son);
1109
1110     found_problem = 1;
1111     dump_loop(l, "-ha");
1112   }
1113
1114   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1115     printf(" Wrong node as head! "); DDML(l);
1116     printf("                     "); DDMN(le.node);
1117     found_problem = 1;
1118     dump_loop(l, "-ha");
1119   }
1120
1121   if ((get_loop_depth(l) != 0) &&
1122       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1123     printf(" Loop head has no backedges! "); DDML(l);
1124     printf("                             "); DDMN(le.node);
1125     found_problem = 1;
1126     dump_loop(l, "-ha");
1127   }
1128
1129   /* Recur */
1130   has_node = 0;
1131   for (i = 0; i < get_loop_n_elements(l); ++i) {
1132     le = get_loop_element(l, i);
1133     if (*(le.kind) == k_ir_node)
1134       has_node++;
1135     else
1136       if (test_loop_node(le.son)) found_problem = 1;
1137   }
1138
1139   if (has_node == 0) {
1140     printf(" Loop has no firm node! "); DDML(l);
1141     found_problem = 1;
1142     dump_loop(l, "-ha");
1143   }
1144
1145   if (get_loop_loop_nr(l) == 11819)
1146     dump_loop(l, "-ha-debug");
1147
1148   return found_problem;
1149 }
1150
1151 /** Prints all loop nodes that
1152  *  - do not have any firm nodes, only loop sons
1153  *  - the header is not a Phi, Block or Filter.
1154  */
1155 void find_strange_loop_nodes(ir_loop *l) {
1156   int found_problem = 0;
1157   printf("\nTesting loop "); DDML(l);
1158   found_problem = test_loop_node(l);
1159   printf("Finished Test\n\n");
1160   if (found_problem) exit(0);
1161
1162 }