- for (i = tos; i >= 0; i--) {
- ir_node *n = stack[i];
- if (!n) continue;
- printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
- }
-}
-#endif
-
-/* Test for legal loop header: Block, Phi, ... */
-INLINE static bool is_possible_loop_head(ir_node *n) {
- return ((get_irn_op(n) == op_Block) ||
- (get_irn_op(n) == op_Phi) ||
- ((get_irn_op(n) == op_Filter) && interprocedural_view));
-}
-
-/* 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.
- @arg root: only needed for assertion. */
-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);
-
- /* 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)) {
- 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.
- AS: That is: For the loop head. */
- ir_node *tail = find_tail(n);
- if (tail) {
- /* We found a new inner 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);
- } else {
- /* AS: No inner loop was found. Pop all nodes from the stack
- to the current loop. */
- pop_scc_to_loop(n);
- }
- }
-}
-
-/* Constructs backedge information for irg. In interprocedural view constructs
- backedges for all methods called by irg, too. */
-void construct_backedges(ir_graph *irg) {
- ir_graph *rem = current_ir_graph;
- ir_loop *head_rem;
- int i;
-
- assert(!interprocedural_view &&
- "not implemented, use construct_ip_backedges");
-
- current_ir_graph = irg;
- outermost_ir_graph = irg;
-
- init_scc(irg);
-
- current_loop = NULL;
- new_loop(); /* sets current_loop */
- head_rem = current_loop; /* Just for assertion */
-
- if (interprocedural_view) {
- set_irg_visited(irg, inc_max_irg_visited());
- init_ip_walk ();
- } else {
- inc_irg_visited(irg);
- }
-
- scc(get_irg_end(irg));
- for (i = 0; i < get_End_n_keepalives(get_irg_end(irg)); i++)
- scc(get_End_keepalive(get_irg_end(irg), i));
-
- if (interprocedural_view) finish_ip_walk();
-
- assert(head_rem == current_loop);
- set_irg_loop(irg, current_loop);
- assert(get_irg_loop(irg)->kind == k_ir_loop);
- /*
- irg->loops = current_loop;
- if (icfg == 1) {
- int count = 0;
- int depth = 0;
- count_loop (the_loop, &count, &depth);
- }
- }
- */
- current_ir_graph = rem;
-}
-
-
-
-void construct_ip_backedges (void) {
- ir_graph *rem = current_ir_graph;
- int rem_ipv = interprocedural_view;
- int i, j;
-
- outermost_ir_graph = get_irp_main_irg();
-
- init_ip_scc();
-
- current_loop = NULL;
- new_loop(); /* sets current_loop */
- interprocedural_view = 1;
-
- inc_max_irg_visited();
- for (i = 0; i < get_irp_n_irgs(); i++)
- set_irg_visited(get_irp_irg(i), get_max_irg_visited());
-
- for (i = 0; i < get_irp_n_irgs(); i++) {
- ir_node *sb;
- current_ir_graph = get_irp_irg(i);
- /*DDME(get_irg_ent(current_ir_graph));*/
- /* Find real entry points */
- sb = get_irg_start_block(current_ir_graph);
- if ((get_Block_n_cfgpreds(sb) > 1) ||
- (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
- /* printf("running scc for "); DDME(get_irg_ent(current_ir_graph)); */
- /* Compute scc for this graph */
- outermost_ir_graph = current_ir_graph;
- set_irg_visited(outermost_ir_graph, get_max_irg_visited());
- scc(get_irg_end(current_ir_graph));
- for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
- scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
- }
-
- set_irg_loop(outermost_ir_graph, current_loop);
- assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
-
- current_ir_graph = rem;
- interprocedural_view = rem_ipv;
-}
-
-
-static void reset_backedges(ir_node *n, void *env) {
- if (is_possible_loop_head(n))
- clear_backedges(n);
-}
-
-/** Removes all loop information.
- Resets all backedges */
-void free_loop_information(ir_graph *irg) {
- set_irg_loop(irg, NULL);
- /* We cannot free the loop nodes, they are on the obstack. */
- irg_walk_graph(irg, NULL, reset_backedges, NULL);
-}