/* Loop manipulation code for GNU compiler.
- Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
static int find_path (edge, basic_block **);
static bool alp_enum_p (basic_block, void *);
static void add_loop (struct loops *, struct loop *);
-static void fix_loop_placements (struct loop *);
+static void fix_loop_placements (struct loops *, struct loop *);
static bool fix_bb_placement (struct loops *, basic_block);
static void fix_bb_placements (struct loops *, basic_block);
static void place_new_loop (struct loops *, struct loop *);
static basic_block create_preheader (struct loop *, int);
static void fix_irreducible_loops (basic_block);
+#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
/* Fix placements of basic blocks inside loops and the placement of
loops in the loop tree. */
fix_bb_placements (loops, from);
- fix_loop_placements (from->loop_father);
+ fix_loop_placements (loops, from->loop_father);
return true;
}
for (i = 0; i < nbbs; i++)
{
bbs[i]->frequency = (bbs[i]->frequency * num) / den;
- bbs[i]->count = (bbs[i]->count * num) / den;
+ bbs[i]->count = RDIV (bbs[i]->count * num, den);
for (e = bbs[i]->succ; e; e = e->succ_next)
e->count = (e->count * num) /den;
}
accordingly. Everything between them plus LATCH_EDGE destination must
be dominated by HEADER_EDGE destination, and back-reachable from
LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
- SWITCH_BB->succ to original destination of LATCH_EDGE and
- SWITCH_BB->succ->succ_next to original destination of HEADER_EDGE.
+ FALLTHRU_EDGE (SWITCH_BB) to original destination of HEADER_EDGE and
+ BRANCH_EDGE (SWITCH_BB) to original destination of LATCH_EDGE.
Returns newly created loop. */
+
struct loop *
-loopify (struct loops *loops, edge latch_edge, edge header_edge, basic_block switch_bb)
+loopify (struct loops *loops, edge latch_edge, edge header_edge,
+ basic_block switch_bb)
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
/* Redirect edges. */
loop_redirect_edge (latch_edge, loop->header);
+ loop_redirect_edge (BRANCH_EDGE (switch_bb), succ_bb);
+
loop_redirect_edge (header_edge, switch_bb);
- loop_redirect_edge (switch_bb->succ->succ_next, loop->header);
- loop_redirect_edge (switch_bb->succ, succ_bb);
+ loop_redirect_edge (FALLTHRU_EDGE (switch_bb), loop->header);
/* Update dominators. */
set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
+
set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
/* Compute new loop. */
It is used in case when we removed some edges coming out of LOOP, which
may cause the right placement of LOOP inside loop tree to change. */
static void
-fix_loop_placements (struct loop *loop)
+fix_loop_placements (struct loops *loops, struct loop *loop)
{
struct loop *outer;
outer = loop->outer;
if (!fix_loop_placement (loop))
break;
+
+ /* Changing the placement of a loop in the loop tree may alter the
+ validity of condition 2) of the description of fix_bb_placement
+ for its preheader, because the successor is the header and belongs
+ to the loop. So call fix_bb_placements to fix up the placement
+ of the preheader and (possibly) of its predecessors. */
+ fix_bb_placements (loops, loop_preheader_edge (loop)->src);
loop = outer;
}
}
return ret;
}
-#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+/* The NBBS blocks in BBS will get duplicated and the copies will be placed
+ to LOOP. Update the single_exit information in superloops of LOOP. */
+
+static void
+update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
+ struct loop *loop)
+{
+ unsigned i;
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 1;
+
+ for (; loop->outer; loop = loop->outer)
+ {
+ if (!loop->single_exit)
+ continue;
+
+ if (loop->single_exit->src->rbi->duplicated)
+ loop->single_exit = NULL;
+ }
+
+ for (i = 0; i < nbbs; i++)
+ bbs[i]->rbi->duplicated = 0;
+}
+
/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
LOOPS structure and dominators. E's destination must be LOOP header for
first_active_latch = latch;
}
+ /* Update the information about single exits. */
+ if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
+ update_single_exits_after_duplication (bbs, n, target);
+
/* Record exit edge in original loop body. */
if (orig && TEST_BIT (wont_exit, 0))
to_remove[(*n_to_remove)++] = orig;
dummy->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
}
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
+ if (dump_file)
+ fprintf (dump_file, "Created preheader block for loop %i\n",
loop->num);
return dummy;
return new_bb;
}
+
+/* Uses the natural loop discovery to recreate loop notes. */
+void
+create_loop_notes (void)
+{
+ rtx insn, head, end;
+ struct loops loops;
+ struct loop *loop;
+ basic_block *first, *last, bb, pbb;
+ struct loop **stack, **top;
+
+#ifdef ENABLE_CHECKING
+ /* Verify that there really are no loop notes. */
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ if (NOTE_P (insn)
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ abort ();
+#endif
+
+ flow_loops_find (&loops, LOOP_TREE);
+ free_dominance_info (CDI_DOMINATORS);
+ if (loops.num > 1)
+ {
+ last = xcalloc (loops.num, sizeof (basic_block));
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ last[loop->num] = bb;
+ }
+
+ first = xcalloc (loops.num, sizeof (basic_block));
+ stack = xcalloc (loops.num, sizeof (struct loop *));
+ top = stack;
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ {
+ if (!first[loop->num])
+ {
+ *top++ = loop;
+ first[loop->num] = bb;
+ }
+
+ if (bb == last[loop->num])
+ {
+ /* Prevent loops from overlapping. */
+ while (*--top != loop)
+ last[(*top)->num] = EXIT_BLOCK_PTR;
+
+ /* If loop starts with jump into it, place the note in
+ front of the jump. */
+ insn = PREV_INSN (BB_HEAD (first[loop->num]));
+ if (insn
+ && BARRIER_P (insn))
+ insn = PREV_INSN (insn);
+
+ if (insn
+ && JUMP_P (insn)
+ && any_uncondjump_p (insn)
+ && onlyjump_p (insn))
+ {
+ pbb = BLOCK_FOR_INSN (insn);
+ if (!pbb || !pbb->succ || pbb->succ->succ_next)
+ abort ();
+
+ if (!flow_bb_inside_loop_p (loop, pbb->succ->dest))
+ insn = BB_HEAD (first[loop->num]);
+ }
+ else
+ insn = BB_HEAD (first[loop->num]);
+
+ head = BB_HEAD (first[loop->num]);
+ emit_note_before (NOTE_INSN_LOOP_BEG, insn);
+ BB_HEAD (first[loop->num]) = head;
+
+ /* Position the note correctly wrto barrier. */
+ insn = BB_END (last[loop->num]);
+ if (NEXT_INSN (insn)
+ && BARRIER_P (NEXT_INSN (insn)))
+ insn = NEXT_INSN (insn);
+
+ end = BB_END (last[loop->num]);
+ emit_note_after (NOTE_INSN_LOOP_END, insn);
+ BB_END (last[loop->num]) = end;
+ }
+ }
+ }
+
+ free (first);
+ free (last);
+ free (stack);
+ }
+ flow_loops_free (&loops);
+}