-/* Returns true if n is a loop header, i.e., it is a Block, Phi
- or Filter node and has predecessors within the loop and out
- of the loop. */
-static bool
-is_head (ir_node *n, ir_node *root)
-{
- int i;
- int some_outof_loop = 0, some_in_loop = 0;
-
- /* Test for legal loop header: Block, Phi, ... */
- if (!is_possible_loop_head(n))
- return false;
-
- if (!is_outermost_Start(n)) {
- for (i = get_start_index(n); i < get_irn_arity(n); i++) {
- ir_node *pred = get_irn_n(n, i);
- assert(pred);
- if (is_backedge(n, i)) continue;
- if (!irn_is_in_stack(pred)) {
- some_outof_loop = 1;
- } else {
- assert(get_irn_uplink(pred) >= get_irn_uplink(root));
- some_in_loop = 1;
- }
- }
- }
- return some_outof_loop && some_in_loop;
-}
-
-/* Returns index of the predecessor with the smallest dfn number
- greater-equal than limit. */
-static int
-smallest_dfn_pred (ir_node *n, int limit)
-{
- int i, index = -2, min = -1;
-
- if (!is_outermost_Start(n)) {
- for (i = get_start_index(n); i < get_irn_arity(n); i++) {
- ir_node *pred = get_irn_n(n, i);
- assert(pred);
- if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
- if (get_irn_dfn(pred) >= limit
- && (min == -1 || get_irn_dfn(pred) < min)) {
- index = i;
- min = get_irn_dfn(pred);
- }
- }
- }
- return index;
-}
-
-/* Returns index of the predecessor with the largest dfn number. */
-static int
-largest_dfn_pred (ir_node *n)
-{
- int i, index = -2, max = -1;
-
- if (!is_outermost_Start(n)) {
- for (i = get_start_index(n); i < get_irn_arity(n); i++) {
- ir_node *pred = get_irn_n(n, i);
- if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
- if (get_irn_dfn(pred) > max) {
- index = i;
- max = get_irn_dfn(pred);
- }
- }
- }
- return index;
-}
-
-/* Searches the stack for possible loop heads. Tests these for backedges.
- If it finds a head with an unmarked backedge it marks this edge and
- returns the tail of the loop.
- If it finds no backedge returns NULL.
- ("disable_backedge" in fiasco) */
-
-static ir_node *
-find_tail (ir_node *n) {
- ir_node *m;
- int i, res_index = -2;
-
- /*
- if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
- */
-
- m = stack[tos-1]; /* tos = top of stack */
- if (is_head (m, n)) {
- res_index = smallest_dfn_pred(m, 0);
- if ((res_index == -2) && /* no smallest dfn pred found. */
- (n == m))
- return NULL;
- } else {
- if (m == n) return NULL;
- for (i = tos-2; ; --i) {
- m = stack[i];
- if (is_head (m, n)) {
- res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
- if (res_index == -2) /* no smallest dfn pred found. */
- res_index = largest_dfn_pred (m);
- break;
- }
- }
- }
- assert (res_index > -2);
-
- set_backedge (m, res_index);
- return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
-}
-
-
-/* The core algorithm. *****************************************/
-
-static void scc (ir_node *n) {
- int i;
- ir_graph *rem;
-
- if (irn_visited(n)) return;
- mark_irn_visited(n);
- /*printf("mark: %d ", get_irn_visited(n)); DDMN(n);
- DDME(get_irg_ent(current_ir_graph));*/
-
- /* Initialize the node */
- set_irn_dfn(n, current_dfn); /* Depth first number for this node */
- set_irn_uplink(n, current_dfn); /* ... is default uplink. */
- set_irn_loop(n, NULL);
- current_dfn ++;
-
- /* What's this good for?
- n->ana.scc.section = NULL;
- */
-
- push(n);
-
- if (!is_outermost_Start(n)) {
- for (i = get_start_index(n); i < get_irn_arity(n); i++) {
- ir_node *m;
- if (is_backedge(n, i)) continue;
-
- m = get_irn_n(n, i); /*get_irn_ip_pred(n, i);*/
- if ((!m) || (get_irn_op(m) == op_Unknown)) continue;
- scc (m);
- /*return_recur(n, i);*/
-
- if (irn_is_in_stack(m)) {
- /* Uplink of m is smaller if n->m is a backedge.
- Propagate the uplink to mark the loop. */
- if (get_irn_uplink(m) < get_irn_uplink(n))
- set_irn_uplink(n, get_irn_uplink(m));
- }
- }
- }
- if (get_irn_dfn(n) == get_irn_uplink(n)) {
- /* This condition holds for the node with the incoming backedge. */
- ir_node *tail = find_tail(n);
- if (tail) {
- /* We found a new loop! */
- ir_loop *l = new_loop();
-
- /* Remove the loop from the stack ... */
- pop_scc_unmark_visit (n);
- /* and recompute it in a better order; and so that it goes into
- the new loop. */
- rem = find_irg_on_stack(tail);
-
- scc (tail);
- current_ir_graph = rem;
-
- assert (irn_visited(n));
- close_loop(l);
-
- /* current_loop = l; AS: This is done close_loop */
- } else {
- pop_scc_to_loop(n);
- }
- }
+#ifdef INTERPROCEDURAL_VIEW
+static void my_scc(ir_node *n) {
+ int i;
+ if (irn_visited(n))
+ return;
+ mark_irn_visited(n);
+
+ /* Initialize the node */
+ set_irn_dfn(n, current_dfn); /* Depth first number for this node */
+ set_irn_uplink(n, current_dfn); /* ... is default uplink. */
+ set_irn_loop(n, NULL);
+ current_dfn ++;
+ push(n);
+
+ /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
+ array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
+ so is_backedge does not access array[-1] but correctly returns false! */
+
+ if (!is_outermost_Start(n)) {
+ int arity = get_irn_arity(n);
+
+ for (i = get_start_index(n); i < arity; i++) {
+ ir_node *m;
+ if (is_backedge(n, i)) continue;
+ m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
+ /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
+ my_scc(m);
+ if (irn_is_in_stack(m)) {
+ /* Uplink of m is smaller if n->m is a backedge.
+ Propagate the uplink to mark the loop. */
+ if (get_irn_uplink(m) < get_irn_uplink(n))
+ set_irn_uplink(n, get_irn_uplink(m));
+ }
+ }
+ }
+
+ if (get_irn_dfn(n) == get_irn_uplink(n)) {
+ /* This condition holds for
+ 1) the node with the incoming backedge.
+ That is: We found a loop!
+ 2) Straight line code, because no uplink has been propagated, so the
+ uplink still is the same as the dfn.
+
+ But n might not be a proper loop head for the analysis. Proper loop
+ heads are Block and Phi nodes. find_tail searches the stack for
+ Block's and Phi's and takes those nodes as loop heads for the current
+ loop instead and marks the incoming edge as backedge. */
+
+ ir_node *tail = find_tail(n);
+ if (tail) {
+ /* We have a loop, that is no straight line code,
+ because we found a loop head!
+ Next actions: Open a new loop on the loop tree and
+ try to find inner loops */
+
+#if NO_LOOPS_WITHOUT_HEAD
+ /* This is an adaption of the algorithm from fiasco / optscc to
+ * avoid loops without Block or Phi as first node. This should
+ * severely reduce the number of evaluations of nodes to detect
+ * a fixpoint in the heap analysis.
+ * Further it avoids loops without firm nodes that cause errors
+ * in the heap analyses. */
+
+ ir_loop *l;
+ int close;
+ if ((get_loop_n_elements(current_loop) > 0) || (is_outermost_loop(current_loop))) {
+ l = new_loop();
+ close = 1;
+ } else {
+ l = current_loop;
+ close = 0;
+ }
+#else
+ ir_loop *l = new_loop();
+#endif
+
+ /* Remove the loop from the stack ... */
+ pop_scc_unmark_visit(n);
+
+ /* The current backedge has been marked, that is temporarily eliminated,
+ by find tail. Start the scc algorithm
+ anew on the subgraph that is left (the current loop without the backedge)
+ in order to find more inner loops. */
+ my_scc(tail);
+
+ assert(irn_visited(n));
+#if NO_LOOPS_WITHOUT_HEAD
+ if (close)
+#endif
+ close_loop(l);
+ } else {
+ /* No loop head was found, that is we have straightline code.
+ Pop all nodes from the stack to the current loop. */
+ pop_scc_to_loop(n);
+ }
+ }