+/**
+ * Returns non-zero if n is a loop header, i.e., it is a Block or Phi
+ * node and has predecessors within the loop and out of the loop.
+ *
+ * @param n the node to check
+ * @param root only needed for assertion.
+ */
+static int is_head(ir_node *n, ir_node *root)
+{
+ int i, arity;
+ int some_outof_loop = 0, some_in_loop = 0;
+
+ /* Test for legal loop header: Block, Phi, ... */
+ if (!is_possible_loop_head(n))
+ return 0;
+
+ if (!is_outermost_Start(n)) {
+#ifndef NDEBUG
+ int uplink = get_irn_uplink(root);
+#else
+ (void) root;
+#endif
+ arity = get_irn_arity(n);
+ for (i = get_start_index(n); i < arity; i++) {
+ ir_node *pred;
+ if (is_backedge(n, i))
+ continue;
+ pred = get_irn_n(n, i);
+ if (! irn_is_in_stack(pred)) {
+ some_outof_loop = 1;
+ } else {
+ assert(get_irn_uplink(pred) >= uplink);
+ some_in_loop = 1;
+ }
+ }
+ }
+ return some_outof_loop & some_in_loop;
+}
+
+/**
+ * Returns non-zero if n is possible loop head of an endless loop.
+ * I.e., it is a Block or Phi node and has only predecessors
+ * within the loop.
+ *
+ * @param n the node to check
+ * @param root only needed for assertion.
+ */
+static int is_endless_head(ir_node *n, ir_node *root)
+{
+ int i, arity;
+ int none_outof_loop = 1, some_in_loop = 0;
+
+ /* Test for legal loop header: Block, Phi, ... */
+ if (!is_possible_loop_head(n))
+ return 0;
+
+ if (!is_outermost_Start(n)) {
+#ifndef NDEBUG
+ int uplink = get_irn_uplink(root);
+#else
+ (void) root;
+#endif
+ arity = get_irn_arity(n);
+ for (i = get_start_index(n); i < arity; i++) {
+ ir_node *pred;
+ if (is_backedge(n, i))
+ continue;
+ pred = get_irn_n(n, i);
+ if (!irn_is_in_stack(pred)) {
+ none_outof_loop = 0;
+ } else {
+ assert(get_irn_uplink(pred) >= uplink);
+ some_in_loop = 1;
+ }
+ }
+ }
+ return none_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)) {
+ int arity = get_irn_arity(n);
+ for (i = get_start_index(n); i < arity; 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) >= 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)) {
+ int arity = get_irn_arity(n);
+ for (i = get_start_index(n); i < arity; 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)
+ *
+ * @param n A node where uplink == dfn.
+ */
+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; // Is this to catch Phi - self loops?
+ for (i = tos-2; i >= 0; --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);
+
+ if ((m == n) && (res_index == -2)) { /* don't walk past loop head. */
+ i = -1;
+ }
+ break;
+ }
+
+ /* We should not walk past our selves on the stack: The upcoming nodes
+ are not in this loop. We assume a loop not reachable from Start. */
+ if (m == n) {
+ i = -1;
+ break;
+ }
+ }
+
+ if (i < 0) {
+ /* A dead loop not reachable from Start. */
+ for (i = tos-2; i >= 0; --i) {
+ m = stack[i];
+ if (is_endless_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;
+ }
+ if (m == n) { break; } /* It's not an unreachable loop, either. */
+ }
+ //assert(0 && "no head found on stack");
+ }
+
+ }
+ if (res_index <= -2) {
+ /* It's a completely bad loop: without Phi/Block nodes that can
+ be a head. I.e., the code is "dying". We break the loop by
+ setting Bad nodes. */
+ int arity = get_irn_arity(n);
+ ir_node *bad = get_irg_bad(get_irn_irg(n));
+ for (i = -1; i < arity; ++i) {
+ set_irn_n(n, i, bad);
+ }
+ return NULL;
+ }
+ assert(res_index > -2);
+
+ set_backedge(m, res_index);
+ return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
+}
+
+static inline int is_outermost_loop(ir_loop *l)
+{
+ return l == get_loop_outer_loop(l);
+}