-/* 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 */
- if (!((get_irn_op(n) == op_Block) ||
- (get_irn_op(n) == op_Phi) ||
- ((get_irn_op(n) == op_Filter) && interprocedural_view)))
- 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_tmp(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);
- }
- }