#include "recog.h"
#include "toplev.h"
#include "cselib.h"
+#include "tm_p.h"
#include "obstack.h"
/* cleanup_cfg maintains following flags for each basic block. */
-enum bb_flags {
+
+enum bb_flags
+{
/* Set if life info needs to be recomputed for given BB. */
BB_UPDATE_LIFE = 1,
/* Set if BB is the forwarder block to avoid too many
forwarder_block_p calls. */
BB_FORWARDER_BLOCK = 2
- };
+};
-#define BB_FLAGS(bb) (enum bb_flags)(bb)->aux
-#define BB_SET_FLAG(bb,flag) \
- (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux | (flag))
-#define BB_CLEAR_FLAG(bb,flag) \
- (bb)->aux = (void *) (long) ((enum bb_flags)(bb)->aux & ~(flag))
+#define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
+#define BB_SET_FLAG(BB, FLAG) \
+ (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
+#define BB_CLEAR_FLAG(BB, FLAG) \
+ (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
-#define FORWARDER_BLOCK_P(bb) (BB_FLAGS(bb) & BB_FORWARDER_BLOCK)
+#define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
static bool try_crossjump_bb PARAMS ((int, basic_block));
{
if (!bb)
return;
+
BB_SET_FLAG (bb, BB_UPDATE_LIFE);
if (forwarder_block_p (bb))
BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
jump_dest_block);
cbranch_jump_edge->flags |= EDGE_FALLTHRU;
cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
+ update_br_prob_note (cbranch_block);
/* Delete the block with the unconditional jump, and clean up the mess. */
flow_delete_block (jump_block);
\f
/* Attempt to prove that operation is NOOP using CSElib or mark the effect
on register. Used by jump threading. */
+
static bool
mark_effect (exp, nonequal)
rtx exp;
regset nonequal;
{
+ int regno;
+ rtx dest;
switch (GET_CODE (exp))
{
/* In case we do clobber the register, mark it as equal, as we know the
value is dead so it don't have to match. */
case CLOBBER:
if (REG_P (XEXP (exp, 0)))
- CLEAR_REGNO_REG_SET (nonequal, REGNO (XEXP (exp, 0)));
+ {
+ dest = XEXP (exp, 0);
+ regno = REGNO (dest);
+ CLEAR_REGNO_REG_SET (nonequal, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
+ while (--n > 0)
+ CLEAR_REGNO_REG_SET (nonequal, regno + n);
+ }
+ }
return false;
+
case SET:
if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
return false;
- if (GET_CODE (SET_SRC (exp)) != REG)
+ dest = SET_DEST (exp);
+ if (dest == pc_rtx)
+ return false;
+ if (!REG_P (dest))
return true;
- SET_REGNO_REG_SET (nonequal, REGNO (SET_SRC (exp)));
+ regno = REGNO (dest);
+ SET_REGNO_REG_SET (nonequal, regno);
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
+ while (--n > 0)
+ SET_REGNO_REG_SET (nonequal, regno + n);
+ }
return false;
+
default:
return false;
}
set1 = pc_set (e->src->end);
set2 = pc_set (b->end);
if (((e->flags & EDGE_FALLTHRU) != 0)
- != (XEXP (SET_SRC (set1), 0) == pc_rtx))
+ != (XEXP (SET_SRC (set1), 1) == pc_rtx))
reverse1 = true;
cond1 = XEXP (SET_SRC (set1), 0);
cond2 = XEXP (SET_SRC (set2), 0);
if (reverse1)
- code1 = reversed_comparison_code (cond1, b->end);
+ code1 = reversed_comparison_code (cond1, e->src->end);
else
code1 = GET_CODE (cond1);
nonequal = BITMAP_XMALLOC();
CLEAR_REG_SET (nonequal);
+
/* Now assume that we've continued by the edge E to B and continue
processing as if it were same basic block.
-
Our goal is to prove that whole block is an NOOP. */
- for (insn = NEXT_INSN (b->head); insn != b->end && !failed;
+
+ for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed;
insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
else
failed |= mark_effect (pat, nonequal);
}
+
cselib_process_insn (insn);
}
BITMAP_XFREE (nonequal);
cselib_finish ();
if ((comparison_dominates_p (code1, code2) != 0)
- != (XEXP (SET_SRC (set2), 0) == pc_rtx))
+ != (XEXP (SET_SRC (set2), 1) == pc_rtx))
return BRANCH_EDGE (b);
else
return FALLTHRU_EDGE (b);
int mode;
{
bool changed = false;
- edge e, next, threaded_edge;
+ edge e, next, *threaded_edges = NULL;
- for (e = b->succ; e ; e = next)
+ for (e = b->succ; e; e = next)
{
basic_block target, first;
int counter;
bool threaded = false;
+ int nthreaded_edges = 0;
next = e->succ_next;
counter = n_basic_blocks;
new_target = target->succ->dest;
}
+
/* Allow to thread only over one edge at time to simplify updating
of probabilities. */
- else if ((mode & CLEANUP_THREADING) && !threaded)
+ else if (mode & CLEANUP_THREADING)
{
- threaded_edge = thread_jump (mode, e, target);
- if (threaded_edge)
+ edge t = thread_jump (mode, e, target);
+ if (t)
{
- new_target = threaded_edge->dest;
+ if (!threaded_edges)
+ threaded_edges = xmalloc (sizeof (*threaded_edges)
+ * n_basic_blocks);
+ else
+ {
+ int i;
+
+ /* Detect an infinite loop across blocks not
+ including the start block. */
+ for (i = 0; i < nthreaded_edges; ++i)
+ if (threaded_edges[i] == t)
+ break;
+ if (i < nthreaded_edges)
+ {
+ counter = n_basic_blocks;
+ break;
+ }
+ }
+
+ /* Detect an infinite loop across the start block. */
+ if (t->dest == b)
+ break;
+
+ if (nthreaded_edges >= n_basic_blocks)
+ abort ();
+ threaded_edges[nthreaded_edges++] = t;
+
+ new_target = t->dest;
new_target_threaded = true;
}
}
+
if (!new_target)
break;
if (GET_CODE (insn) != NOTE)
insn = NEXT_INSN (insn);
- for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
+ for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
if (GET_CODE (insn) == NOTE)
break;
}
+
counter++;
target = new_target;
threaded |= new_target_threaded;
gcov_type edge_count = e->count;
int edge_probability = e->probability;
int edge_frequency;
+ int n = 0;
- if (threaded)
+ /* Don't force if target is exit block. */
+ if (threaded && target != EXIT_BLOCK_PTR)
{
notice_new_block (redirect_edge_and_branch_force (e, target));
if (rtl_dump_file)
else if (!redirect_edge_and_branch (e, target))
{
if (rtl_dump_file)
- fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
+ fprintf (rtl_dump_file,
+ "Forwarding edge %i->%i to %i failed.\n",
b->index, e->dest->index, target->index);
continue;
}
+
/* We successfully forwarded the edge. Now update profile
data: for each edge we traversed in the chain, remove
the original edge's execution count. */
do
{
edge t;
+
first->count -= edge_count;
- first->succ->count -= edge_count;
+ if (first->count < 0)
+ first->count = 0;
first->frequency -= edge_frequency;
+ if (first->frequency < 0)
+ first->frequency = 0;
if (first->succ->succ_next)
- t = threaded_edge;
+ {
+ edge e;
+ int prob;
+ if (n >= nthreaded_edges)
+ abort ();
+ t = threaded_edges [n++];
+ if (t->src != first)
+ abort ();
+ if (first->frequency)
+ prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
+ else
+ prob = 0;
+ if (prob > t->probability)
+ prob = t->probability;
+ t->probability -= prob;
+ prob = REG_BR_PROB_BASE - prob;
+ if (prob <= 0)
+ {
+ first->succ->probability = REG_BR_PROB_BASE;
+ first->succ->succ_next->probability = 0;
+ }
+ else
+ for (e = first->succ; e; e = e->succ_next)
+ e->probability = ((e->probability * REG_BR_PROB_BASE)
+ / (double) prob);
+ update_br_prob_note (first);
+ }
else
- t = first->succ;
+ {
+ /* It is possible that as the result of
+ threading we've removed edge as it is
+ threaded to the fallthru edge. Avoid
+ getting out of sync. */
+ if (n < nthreaded_edges
+ && first == threaded_edges [n]->src)
+ n++;
+ t = first->succ;
+ }
+
+ t->count -= edge_count;
+ if (t->count < 0)
+ t->count = 0;
first = t->dest;
}
while (first != target);
}
}
+ if (threaded_edges)
+ free (threaded_edges);
return changed;
}
\f
BB_SET_FLAG (a, BB_UPDATE_LIFE);
if (rtl_dump_file)
- {
- fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
- a->index, b->index);
- }
+ fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
+ a->index, b->index);
/* Swap the records for the two blocks around. Although we are deleting B,
A is now where B was and we want to compact the BB array from where
BB_SET_FLAG (a, BB_UPDATE_LIFE);
if (rtl_dump_file)
- {
- fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
- b->index, a->index);
- }
+ fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
+ b->index, a->index);
}
/* Attempt to merge basic blocks that are potentially non-adjacent.
/* If B has a fallthru edge to C, no need to move anything. */
if (e->flags & EDGE_FALLTHRU)
{
+ int b_index = b->index, c_index = c->index;
/* We need to update liveness in case C already has broken liveness
or B ends by conditional jump to next instructions that will be
removed. */
update_forwarder_flag (b);
if (rtl_dump_file)
- {
- fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
- b->index, c->index);
- }
+ fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
+ b_index, c_index);
return true;
}
+
/* Otherwise we will need to move code around. Do that only if expensive
transformations are allowed. */
else if (mode & CLEANUP_EXPENSIVE)
for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
if (tmp_edge->flags & EDGE_FALLTHRU)
break;
+
c_has_outgoing_fallthru = (tmp_edge != NULL);
for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
if (tmp_edge->flags & EDGE_FALLTHRU)
break;
+
b_has_incoming_fallthru = (tmp_edge != NULL);
b_fallthru_edge = tmp_edge;
if (b_has_incoming_fallthru)
{
basic_block bb;
+
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
return false;
bb = force_nonfallthru (b_fallthru_edge);
else
BB_SET_FLAG (b_fallthru_edge->src, BB_UPDATE_LIFE);
}
+
merge_blocks_move_predecessor_nojumps (b, c);
return true;
}
+
return false;
}
\f
return true;
}
}
+
return false;
}
+
return true;
}
\f
|| (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
{
last1 = i1;
- /* Count everything except for unconditional jump as insn. */
- if (!simplejump_p (i1) && !returnjump_p (i1))
- ninsns++;
i1 = PREV_INSN (i1);
}
+
i2 = bb2->end;
if (onlyjump_p (i2)
|| (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
{
last2 = i2;
+ /* Count everything except for unconditional jump as insn. */
+ if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
+ ninsns++;
i2 = PREV_INSN (i2);
}
/* Ignore notes. */
while (!active_insn_p (i1) && i1 != bb1->head)
i1 = PREV_INSN (i1);
+
while (!active_insn_p (i2) && i2 != bb2->head)
i2 = PREV_INSN (i2);
last1 = i1, last2 = i2;
ninsns++;
}
+
i1 = PREV_INSN (i1);
i2 = PREV_INSN (i2);
}
#ifdef HAVE_cc0
- if (ninsns)
- {
- /* Don't allow the insn after a compare to be shared by
- cross-jumping unless the compare is also shared. */
- if (reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
- last1 = afterlast1, last2 = afterlast2, ninsns--;
- }
+ /* Don't allow the insn after a compare to be shared by
+ cross-jumping unless the compare is also shared. */
+ if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
+ last1 = afterlast1, last2 = afterlast2, ninsns--;
#endif
/* Include preceding notes and labels in the cross-jump. One,
{
while (last1 != bb1->head && !active_insn_p (PREV_INSN (last1)))
last1 = PREV_INSN (last1);
+
if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
last1 = PREV_INSN (last1);
+
while (last2 != bb2->head && !active_insn_p (PREV_INSN (last2)))
last2 = PREV_INSN (last2);
+
if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
last2 = PREV_INSN (last2);
/* If BB1 has only one successor, we may be looking at either an
unconditional jump, or a fake edge to exit. */
- if (bb1->succ && !bb1->succ->succ_next)
- {
- if (! bb2->succ || bb2->succ->succ_next)
- return false;
- return insns_match_p (mode, bb1->end, bb2->end);
- }
+ if (bb1->succ && !bb1->succ->succ_next
+ && !(bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+ return (bb2->succ && !bb2->succ->succ_next
+ && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0);
/* Match conditional jumps - this may get tricky when fallthru and branch
edges are crossed. */
if (bb1->succ
&& bb1->succ->succ_next
&& !bb1->succ->succ_next->succ_next
- && any_condjump_p (bb1->end))
+ && any_condjump_p (bb1->end)
+ && onlyjump_p (bb1->end))
{
edge b1, f1, b2, f2;
bool reverse, match;
if (!bb2->succ
|| !bb2->succ->succ_next
|| bb1->succ->succ_next->succ_next
- || !any_condjump_p (bb2->end))
+ || !any_condjump_p (bb2->end)
+ || !onlyjump_p (bb1->end))
return false;
b1 = BRANCH_EDGE (bb1);
should be optimized out already. */
if (FORWARDER_BLOCK_P (f1->dest))
f1 = f1->dest->succ;
+
if (FORWARDER_BLOCK_P (f2->dest))
f2 = f2->dest->succ;
code2 = reversed_comparison_code (cond2, bb2->end);
else
code2 = GET_CODE (cond2);
+
if (code2 == UNKNOWN)
return false;
we will only have one branch prediction bit to work with. Thus
we require the existing branches to have probabilities that are
roughly similar. */
- /* ??? We should use bb->frequency to allow merging in infrequently
- executed blocks, but at the moment it is not available when
- cleanup_cfg is run. */
- if (match && !optimize_size)
+ if (match
+ && !optimize_size
+ && bb1->frequency > BB_FREQ_MAX / 1000
+ && bb2->frequency > BB_FREQ_MAX / 1000)
{
- rtx note1, note2;
- int prob1, prob2;
- note1 = find_reg_note (bb1->end, REG_BR_PROB, 0);
- note2 = find_reg_note (bb2->end, REG_BR_PROB, 0);
+ int prob2;
- if (note1 && note2)
+ if (b1->dest == b2->dest)
+ prob2 = b2->probability;
+ else
+ /* Do not use f2 probability as f2 may be forwarded. */
+ prob2 = REG_BR_PROB_BASE - b2->probability;
+
+ /* Fail if the difference in probabilities is
+ greater than 5%. */
+ if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 20)
{
- prob1 = INTVAL (XEXP (note1, 0));
- prob2 = INTVAL (XEXP (note2, 0));
- if (reverse)
- prob2 = REG_BR_PROB_BASE - prob2;
-
- /* Fail if the difference in probabilities is
- greater than 5%. */
- if (abs (prob1 - prob2) > REG_BR_PROB_BASE / 20)
- return false;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
+ bb1->index, bb2->index, b1->probability, prob2);
+
+ return false;
}
- else if (note1 || note2)
- return false;
}
if (rtl_dump_file && match)
{
if (e1->flags & EDGE_EH)
nehedges1++;
+
if (e2->flags & EDGE_EH)
nehedges2++;
+
if (e1->flags & EDGE_FALLTHRU)
fallthru1 = e1;
if (e2->flags & EDGE_FALLTHRU)
fallthru2 = e2;
}
+
/* If number of edges of various types does not match, fail. */
- if (e1 || e2)
- return false;
- if (nehedges1 != nehedges2)
- return false;
- if ((fallthru1 != 0) != (fallthru2 != 0))
+ if (e1 || e2
+ || nehedges1 != nehedges2
+ || (fallthru1 != 0) != (fallthru2 != 0))
return false;
/* fallthru edges must be forwarded to the same destination. */
? fallthru1->dest->succ->dest: fallthru1->dest);
basic_block d2 = (forwarder_block_p (fallthru2->dest)
? fallthru2->dest->succ->dest: fallthru2->dest);
+
if (d1 != d2)
return false;
}
+
/* In case we do have EH edges, ensure we are in the same region. */
if (nehedges1)
{
rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
+
if (XEXP (n1, 0) != XEXP (n2, 0))
return false;
}
+
/* We don't need to match the rest of edges as above checks should be enought
to ensure that they are equivalent. */
return true;
edge s;
rtx last;
rtx label;
- rtx note;
/* Search backward through forwarder blocks. We don't need to worry
about multiple entry or chained forwarders, as they will be optimized
if (src1->pred
&& !src1->pred->pred_next
&& FORWARDER_BLOCK_P (src1))
- {
- e1 = src1->pred;
- src1 = e1->src;
- }
+ e1 = src1->pred, src1 = e1->src;
+
if (src2->pred
&& !src2->pred->pred_next
&& FORWARDER_BLOCK_P (src2))
- {
- e2 = src2->pred;
- src2 = e2->src;
- }
+ e2 = src2->pred, src2 = e2->src;
/* Nothing to do if we reach ENTRY, or a common source block. */
if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
if (FORWARDER_BLOCK_P (e1->dest)
&& FORWARDER_BLOCK_P (e1->dest->succ->dest))
return false;
+
if (FORWARDER_BLOCK_P (e2->dest)
&& FORWARDER_BLOCK_P (e2->dest->succ->dest))
return false;
if (FORWARDER_BLOCK_P (d))
d = d->succ->dest;
+
for (s2 = src1->succ; ; s2 = s2->succ_next)
{
basic_block d2 = s2->dest;
if (d == d2)
break;
}
+
s->count += s2->count;
/* Take care to update possible forwarder blocks. We verified
s->dest->count += s2->count;
s->dest->frequency += EDGE_FREQUENCY (s);
}
+
if (FORWARDER_BLOCK_P (s2->dest))
{
s2->dest->succ->count -= s2->count;
+ if (s2->dest->succ->count < 0)
+ s2->dest->succ->count = 0;
s2->dest->count -= s2->count;
s2->dest->frequency -= EDGE_FREQUENCY (s);
+ if (s2->dest->frequency < 0)
+ s2->dest->frequency = 0;
+ if (s2->dest->count < 0)
+ s2->dest->count = 0;
}
+
if (!redirect_to->frequency && !src1->frequency)
s->probability = (s->probability + s2->probability) / 2;
else
- s->probability =
- ((s->probability * redirect_to->frequency +
- s2->probability * src1->frequency)
- / (redirect_to->frequency + src1->frequency));
+ s->probability
+ = ((s->probability * redirect_to->frequency +
+ s2->probability * src1->frequency)
+ / (redirect_to->frequency + src1->frequency));
}
- note = find_reg_note (redirect_to->end, REG_BR_PROB, 0);
- if (note)
- XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability);
+ update_br_prob_note (redirect_to);
/* Edit SRC1 to go to REDIRECT_TO at NEWPOS1. */
/* Skip possible basic block header. */
if (GET_CODE (newpos1) == CODE_LABEL)
newpos1 = NEXT_INSN (newpos1);
+
if (GET_CODE (newpos1) == NOTE)
newpos1 = NEXT_INSN (newpos1);
last = src1->end;
/* Attempt to merge blocks as made possible by edge removal. If a block
has only one successor, and the successor has only one predecessor,
they may be combined. */
-
do
{
changed = false;
c = BASIC_BLOCK (b->index - 1);
if (rtl_dump_file)
fprintf (rtl_dump_file, "Deleting block %i.\n", b->index);
+
flow_delete_block (b);
changed = true;
b = c;
|| ! label_is_jump_target_p (b->head, b->pred->src->end)))
{
rtx label = b->head;
+
b->head = NEXT_INSN (b->head);
delete_insn_chain (label, label);
if (rtl_dump_file)
if (rtl_dump_file)
fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
b->index);
+
c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
redirect_edge_succ_nodup (b->pred, b->succ->dest);
flow_delete_block (b);
if ((mode & CLEANUP_UPDATE_LIFE) && changed_overall)
{
bool found = 0;
+
blocks = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (blocks);
for (i = 0; i < n_basic_blocks; i++)
found = 1;
SET_BIT (blocks, i);
}
+
if (found)
update_life_info (blocks, UPDATE_LIFE_GLOBAL,
PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
| PROP_KILL_DEAD_CODE);
sbitmap_free (blocks);
}
+
for (i = 0; i < n_basic_blocks; i++)
BASIC_BLOCK (i)->aux = NULL;
OSDN Git Service
