#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "regs.h"
#include "timevar.h"
#include "output.h"
#include "insn-config.h"
#include "flags.h"
#include "recog.h"
#include "toplev.h"
#include "cselib.h"
#include "params.h"
#include "tm_p.h"
#include "target.h"
#include "cfglayout.h"
#include "emit-rtl.h"
enum bb_flags
{
BB_FORWARDER_BLOCK = 1,
BB_NONTHREADABLE_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 FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
static bool first_pass;
static bool try_crossjump_to_edge (int, edge, edge);
static bool try_crossjump_bb (int, basic_block);
static bool outgoing_edges_match (int, basic_block, basic_block);
static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
static bool insns_match_p (int, rtx, rtx);
static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
static bool try_optimize_cfg (int);
static bool try_simplify_condjump (basic_block);
static bool try_forward_edges (int, basic_block);
static edge thread_jump (int, edge, basic_block);
static bool mark_effect (rtx, bitmap);
static void notice_new_block (basic_block);
static void update_forwarder_flag (basic_block);
static int mentions_nonequal_regs (rtx *, void *);
static void merge_memattrs (rtx, rtx);
static void
notice_new_block (basic_block bb)
{
if (!bb)
return;
if (forwarder_block_p (bb))
BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
}
static void
update_forwarder_flag (basic_block bb)
{
if (forwarder_block_p (bb))
BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
else
BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
}
static bool
try_simplify_condjump (basic_block cbranch_block)
{
basic_block jump_block, jump_dest_block, cbranch_dest_block;
edge cbranch_jump_edge, cbranch_fallthru_edge;
rtx cbranch_insn;
if (EDGE_COUNT (cbranch_block->succs) != 2)
return false;
cbranch_insn = BB_END (cbranch_block);
if (!any_condjump_p (cbranch_insn))
return false;
cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
jump_block = cbranch_fallthru_edge->dest;
if (EDGE_COUNT (jump_block->preds) >= 2
|| jump_block->next_bb == EXIT_BLOCK_PTR
|| !FORWARDER_BLOCK_P (jump_block))
return false;
jump_dest_block = EDGE_SUCC (jump_block, 0)->dest;
if (flag_reorder_blocks_and_partition
&& (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
|| (cbranch_jump_edge->flags & EDGE_CROSSING)))
return false;
cbranch_dest_block = cbranch_jump_edge->dest;
if (cbranch_dest_block == EXIT_BLOCK_PTR
|| !can_fallthru (jump_block, cbranch_dest_block))
return false;
if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
return false;
if (dump_file)
fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
cbranch_dest_block);
cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
jump_dest_block);
cbranch_jump_edge->flags |= EDGE_FALLTHRU;
cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
update_br_prob_note (cbranch_block);
delete_basic_block (jump_block);
tidy_fallthru_edge (cbranch_jump_edge);
update_forwarder_flag (cbranch_block);
return true;
}
static bool
mark_effect (rtx exp, regset nonequal)
{
int regno;
rtx dest;
switch (GET_CODE (exp))
{
case CLOBBER:
if (REG_P (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;
dest = SET_DEST (exp);
if (dest == pc_rtx)
return false;
if (!REG_P (dest))
return true;
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;
}
}
static int
mentions_nonequal_regs (rtx *x, void *data)
{
regset nonequal = (regset) data;
if (REG_P (*x))
{
int regno;
regno = REGNO (*x);
if (REGNO_REG_SET_P (nonequal, regno))
return 1;
if (regno < FIRST_PSEUDO_REGISTER)
{
int n = hard_regno_nregs[regno][GET_MODE (*x)];
while (--n > 0)
if (REGNO_REG_SET_P (nonequal, regno + n))
return 1;
}
}
return 0;
}
static edge
thread_jump (int mode, edge e, basic_block b)
{
rtx set1, set2, cond1, cond2, insn;
enum rtx_code code1, code2, reversed_code2;
bool reverse1 = false;
unsigned i;
regset nonequal;
bool failed = false;
reg_set_iterator rsi;
if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
return NULL;
if (EDGE_COUNT (e->src->succs) != 2)
return NULL;
if (EDGE_COUNT (b->succs) != 2)
{
BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
return NULL;
}
if (!any_condjump_p (BB_END (e->src)))
return NULL;
if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
{
BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
return NULL;
}
set1 = pc_set (BB_END (e->src));
set2 = pc_set (BB_END (b));
if (((e->flags & EDGE_FALLTHRU) != 0)
!= (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, BB_END (e->src));
else
code1 = GET_CODE (cond1);
code2 = GET_CODE (cond2);
reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
if (!comparison_dominates_p (code1, code2)
&& !comparison_dominates_p (code1, reversed_code2))
return NULL;
if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
|| !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
return NULL;
for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
insn = NEXT_INSN (insn))
if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
{
BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
return NULL;
}
cselib_init (false);
for (insn = NEXT_INSN (BB_HEAD (e->src));
insn != NEXT_INSN (BB_END (e->src));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
cselib_process_insn (insn);
nonequal = BITMAP_ALLOC (NULL);
CLEAR_REG_SET (nonequal);
for (insn = NEXT_INSN (BB_HEAD (b));
insn != NEXT_INSN (BB_END (b)) && !failed;
insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
rtx pat = PATTERN (insn);
if (GET_CODE (pat) == PARALLEL)
{
for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
}
else
failed |= mark_effect (pat, nonequal);
}
cselib_process_insn (insn);
}
if (failed)
{
BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
goto failed_exit;
}
if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
goto failed_exit;
if (mode & CLEANUP_UPDATE_LIFE)
AND_REG_SET (nonequal, b->global_live_at_end);
EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi)
goto failed_exit;
BITMAP_FREE (nonequal);
cselib_finish ();
if ((comparison_dominates_p (code1, code2) != 0)
!= (XEXP (SET_SRC (set2), 1) == pc_rtx))
return BRANCH_EDGE (b);
else
return FALLTHRU_EDGE (b);
failed_exit:
BITMAP_FREE (nonequal);
cselib_finish ();
return NULL;
}
static bool
try_forward_edges (int mode, basic_block b)
{
bool changed = false;
edge_iterator ei;
edge e, *threaded_edges = NULL;
if (flag_reorder_blocks_and_partition
&& find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
return false;
for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
{
basic_block target, first;
int counter;
bool threaded = false;
int nthreaded_edges = 0;
bool may_thread = first_pass | (b->flags & BB_DIRTY);
if (e->flags & EDGE_COMPLEX)
{
ei_next (&ei);
continue;
}
target = first = e->dest;
counter = 0;
if (flag_reorder_blocks_and_partition
&& first != EXIT_BLOCK_PTR
&& find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
return false;
while (counter < n_basic_blocks)
{
basic_block new_target = NULL;
bool new_target_threaded = false;
may_thread |= target->flags & BB_DIRTY;
if (FORWARDER_BLOCK_P (target)
&& !(EDGE_SUCC (target, 0)->flags & EDGE_CROSSING)
&& EDGE_SUCC (target, 0)->dest != EXIT_BLOCK_PTR)
{
if (target == EDGE_SUCC (target, 0)->dest)
counter = n_basic_blocks;
new_target = EDGE_SUCC (target, 0)->dest;
}
else if ((mode & CLEANUP_THREADING) && may_thread)
{
edge t = thread_jump (mode, e, target);
if (t)
{
if (!threaded_edges)
threaded_edges = xmalloc (sizeof (*threaded_edges)
* n_basic_blocks);
else
{
int i;
for (i = 0; i < nthreaded_edges; ++i)
if (threaded_edges[i] == t)
break;
if (i < nthreaded_edges)
{
counter = n_basic_blocks;
break;
}
}
if (t->dest == b)
break;
gcc_assert (nthreaded_edges < n_basic_blocks);
threaded_edges[nthreaded_edges++] = t;
new_target = t->dest;
new_target_threaded = true;
}
}
if (!new_target)
break;
if ((mode & CLEANUP_PRE_LOOP) && optimize)
{
rtx insn = (EDGE_SUCC (target, 0)->flags & EDGE_FALLTHRU
? BB_HEAD (target) : prev_nonnote_insn (BB_END (target)));
if (!NOTE_P (insn))
insn = NEXT_INSN (insn);
for (; insn && !LABEL_P (insn) && !INSN_P (insn);
insn = NEXT_INSN (insn))
if (NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
break;
if (NOTE_P (insn))
break;
insn = PREV_INSN (BB_HEAD (target));
if (insn && NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
break;
}
counter++;
target = new_target;
threaded |= new_target_threaded;
}
if (counter >= n_basic_blocks)
{
if (dump_file)
fprintf (dump_file, "Infinite loop in BB %i.\n",
target->index);
}
else if (target == first)
;
else
{
gcov_type edge_count = e->count;
int edge_probability = e->probability;
int edge_frequency;
int n = 0;
if (threaded && target != EXIT_BLOCK_PTR)
{
notice_new_block (redirect_edge_and_branch_force (e, target));
if (dump_file)
fprintf (dump_file, "Conditionals threaded.\n");
}
else if (!redirect_edge_and_branch (e, target))
{
if (dump_file)
fprintf (dump_file,
"Forwarding edge %i->%i to %i failed.\n",
b->index, e->dest->index, target->index);
ei_next (&ei);
continue;
}
edge_frequency = ((edge_probability * b->frequency
+ REG_BR_PROB_BASE / 2)
/ REG_BR_PROB_BASE);
if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
do
{
edge t;
if (EDGE_COUNT (first->succs) > 1)
{
gcc_assert (n < nthreaded_edges);
t = threaded_edges [n++];
gcc_assert (t->src == first);
update_bb_profile_for_threading (first, edge_frequency,
edge_count, t);
update_br_prob_note (first);
}
else
{
first->count -= edge_count;
if (first->count < 0)
first->count = 0;
first->frequency -= edge_frequency;
if (first->frequency < 0)
first->frequency = 0;
if (n < nthreaded_edges
&& first == threaded_edges [n]->src)
n++;
t = EDGE_SUCC (first, 0);
}
t->count -= edge_count;
if (t->count < 0)
t->count = 0;
first = t->dest;
}
while (first != target);
changed = true;
continue;
}
ei_next (&ei);
}
if (threaded_edges)
free (threaded_edges);
return changed;
}
static void
merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
{
rtx barrier;
bool only_notes;
if (flag_reorder_blocks_and_partition
&& (BB_PARTITION (a) != BB_PARTITION (b)
|| find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)))
return;
barrier = next_nonnote_insn (BB_END (a));
gcc_assert (BARRIER_P (barrier));
delete_insn (barrier);
only_notes = squeeze_notes (&BB_HEAD (a), &BB_END (a));
gcc_assert (!only_notes);
if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
a->flags |= BB_DIRTY;
if (dump_file)
fprintf (dump_file, "Moved block %d before %d and merged.\n",
a->index, b->index);
unlink_block (a);
link_block (a, b->prev_bb);
merge_blocks (a, b);
}
static void
merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
{
rtx barrier, real_b_end;
rtx label, table;
bool only_notes;
if (flag_reorder_blocks_and_partition
&& (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
|| BB_PARTITION (a) != BB_PARTITION (b)))
return;
real_b_end = BB_END (b);
if (tablejump_p (BB_END (b), &label, &table)
&& prev_active_insn (label) == BB_END (b))
{
BB_END (b) = table;
}
barrier = NEXT_INSN (BB_END (b));
if (barrier && BARRIER_P (barrier))
delete_insn (barrier);
only_notes = squeeze_notes (&BB_HEAD (b), &BB_END (b));
gcc_assert (!only_notes);
reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
BB_END (b) = real_b_end;
if (dump_file)
fprintf (dump_file, "Moved block %d after %d and merged.\n",
b->index, a->index);
merge_blocks (a, b);
}
static basic_block
merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
{
basic_block next;
if (flag_reorder_blocks_and_partition
&& (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
|| find_reg_note (BB_END (c), REG_CROSSING_JUMP, NULL_RTX)
|| BB_PARTITION (b) != BB_PARTITION (c)))
return NULL;
if (e->flags & EDGE_FALLTHRU)
{
int b_index = b->index, c_index = c->index;
merge_blocks (b, c);
update_forwarder_flag (b);
if (dump_file)
fprintf (dump_file, "Merged %d and %d without moving.\n",
b_index, c_index);
return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
}
else if (mode & CLEANUP_EXPENSIVE)
{
edge tmp_edge, b_fallthru_edge;
bool c_has_outgoing_fallthru;
bool b_has_incoming_fallthru;
edge_iterator ei;
if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
return NULL;
FOR_EACH_EDGE (tmp_edge, ei, c->succs)
if (tmp_edge->flags & EDGE_FALLTHRU)
break;
c_has_outgoing_fallthru = (tmp_edge != NULL);
FOR_EACH_EDGE (tmp_edge, ei, b->preds)
if (tmp_edge->flags & EDGE_FALLTHRU)
break;
b_has_incoming_fallthru = (tmp_edge != NULL);
b_fallthru_edge = tmp_edge;
next = b->prev_bb;
if (next == c)
next = next->prev_bb;
if (! c_has_outgoing_fallthru)
{
merge_blocks_move_successor_nojumps (b, c);
return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
}
if (b_has_incoming_fallthru)
{
basic_block bb;
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
return NULL;
bb = force_nonfallthru (b_fallthru_edge);
if (bb)
notice_new_block (bb);
}
merge_blocks_move_predecessor_nojumps (b, c);
return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
}
return NULL;
}
void
merge_memattrs (rtx x, rtx y)
{
int i;
int j;
enum rtx_code code;
const char *fmt;
if (x == y)
return;
if (x == 0 || y == 0)
return;
code = GET_CODE (x);
if (code != GET_CODE (y))
return;
if (GET_MODE (x) != GET_MODE (y))
return;
if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
{
if (! MEM_ATTRS (x))
MEM_ATTRS (y) = 0;
else if (! MEM_ATTRS (y))
MEM_ATTRS (x) = 0;
else
{
rtx mem_size;
if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
{
set_mem_alias_set (x, 0);
set_mem_alias_set (y, 0);
}
if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
{
set_mem_expr (x, 0);
set_mem_expr (y, 0);
set_mem_offset (x, 0);
set_mem_offset (y, 0);
}
else if (MEM_OFFSET (x) != MEM_OFFSET (y))
{
set_mem_offset (x, 0);
set_mem_offset (y, 0);
}
if (!MEM_SIZE (x))
mem_size = NULL_RTX;
else if (!MEM_SIZE (y))
mem_size = NULL_RTX;
else
mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
INTVAL (MEM_SIZE (y))));
set_mem_size (x, mem_size);
set_mem_size (y, mem_size);
set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
set_mem_align (y, MEM_ALIGN (x));
}
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
switch (fmt[i])
{
case 'E':
if (XVECLEN (x, i) != XVECLEN (y, i))
return;
for (j = 0; j < XVECLEN (x, i); j++)
merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
break;
case 'e':
merge_memattrs (XEXP (x, i), XEXP (y, i));
}
}
return;
}
static bool
insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
{
rtx p1, p2;
if (GET_CODE (i1) != GET_CODE (i2))
return false;
p1 = PATTERN (i1);
p2 = PATTERN (i2);
if (GET_CODE (p1) != GET_CODE (p2))
return false;
if (CALL_P (i1)
&& (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
CALL_INSN_FUNCTION_USAGE (i2))
|| SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
return false;
#ifdef STACK_REGS
if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
{
rtx note;
HARD_REG_SET i1_regset, i2_regset;
CLEAR_HARD_REG_SET (i1_regset);
CLEAR_HARD_REG_SET (i2_regset);
for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
return false;
done:
;
}
#endif
if (reload_completed
? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
return true;
if (!reload_completed)
{
rtx equiv1 = find_reg_equal_equiv_note (i1);
rtx equiv2 = find_reg_equal_equiv_note (i2);
if (equiv1 && equiv2
&& (! reload_completed
|| (CONSTANT_P (XEXP (equiv1, 0))
&& rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
{
rtx s1 = single_set (i1);
rtx s2 = single_set (i2);
if (s1 != 0 && s2 != 0
&& rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
{
validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
if (! rtx_renumbered_equal_p (p1, p2))
cancel_changes (0);
else if (apply_change_group ())
return true;
}
}
}
return false;
}
static int
flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
basic_block bb2, rtx *f1, rtx *f2)
{
rtx i1, i2, last1, last2, afterlast1, afterlast2;
int ninsns = 0;
i1 = BB_END (bb1);
last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
if (onlyjump_p (i1)
|| (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
{
last1 = i1;
i1 = PREV_INSN (i1);
}
i2 = BB_END (bb2);
if (onlyjump_p (i2)
|| (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
{
last2 = i2;
if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
ninsns++;
i2 = PREV_INSN (i2);
}
while (true)
{
while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
i1 = PREV_INSN (i1);
while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
i2 = PREV_INSN (i2);
if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
break;
if (!insns_match_p (mode, i1, i2))
break;
merge_memattrs (i1, i2);
if (INSN_P (i1))
{
rtx equiv1 = find_reg_equal_equiv_note (i1);
rtx equiv2 = find_reg_equal_equiv_note (i2);
if (equiv1 && !equiv2)
remove_note (i1, equiv1);
else if (!equiv1 && equiv2)
remove_note (i2, equiv2);
else if (equiv1 && equiv2
&& !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
{
remove_note (i1, equiv1);
remove_note (i2, equiv2);
}
afterlast1 = last1, afterlast2 = last2;
last1 = i1, last2 = i2;
ninsns++;
}
i1 = PREV_INSN (i1);
i2 = PREV_INSN (i2);
}
#ifdef HAVE_cc0
if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
last1 = afterlast1, last2 = afterlast2, ninsns--;
#endif
if (ninsns)
{
while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
last1 = PREV_INSN (last1);
if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
last1 = PREV_INSN (last1);
while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
last2 = PREV_INSN (last2);
if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
last2 = PREV_INSN (last2);
*f1 = last1;
*f2 = last2;
}
return ninsns;
}
static bool
outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
{
int nehedges1 = 0, nehedges2 = 0;
edge fallthru1 = 0, fallthru2 = 0;
edge e1, e2;
edge_iterator ei;
if (EDGE_COUNT (bb1->succs) == 1
&& (EDGE_SUCC (bb1, 0)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
&& (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
return (EDGE_COUNT (bb2->succs) == 1
&& (EDGE_SUCC (bb2, 0)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
&& (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
if (EDGE_COUNT (bb1->succs) == 2
&& any_condjump_p (BB_END (bb1))
&& onlyjump_p (BB_END (bb1)))
{
edge b1, f1, b2, f2;
bool reverse, match;
rtx set1, set2, cond1, cond2;
enum rtx_code code1, code2;
if (EDGE_COUNT (bb2->succs) != 2
|| !any_condjump_p (BB_END (bb2))
|| !onlyjump_p (BB_END (bb2)))
return false;
b1 = BRANCH_EDGE (bb1);
b2 = BRANCH_EDGE (bb2);
f1 = FALLTHRU_EDGE (bb1);
f2 = FALLTHRU_EDGE (bb2);
if (FORWARDER_BLOCK_P (f1->dest))
f1 = EDGE_SUCC (f1->dest, 0);
if (FORWARDER_BLOCK_P (f2->dest))
f2 = EDGE_SUCC (f2->dest, 0);
if (FORWARDER_BLOCK_P (f1->dest)
|| FORWARDER_BLOCK_P (f2->dest)
|| FORWARDER_BLOCK_P (b1->dest)
|| FORWARDER_BLOCK_P (b2->dest))
return false;
if (f1->dest == f2->dest && b1->dest == b2->dest)
reverse = false;
else if (f1->dest == b2->dest && b1->dest == f2->dest)
reverse = true;
else
return false;
set1 = pc_set (BB_END (bb1));
set2 = pc_set (BB_END (bb2));
if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
!= (XEXP (SET_SRC (set2), 1) == pc_rtx))
reverse = !reverse;
cond1 = XEXP (SET_SRC (set1), 0);
cond2 = XEXP (SET_SRC (set2), 0);
code1 = GET_CODE (cond1);
if (reverse)
code2 = reversed_comparison_code (cond2, BB_END (bb2));
else
code2 = GET_CODE (cond2);
if (code2 == UNKNOWN)
return false;
match = ((code1 == code2
&& rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
&& rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
|| (code1 == swap_condition (code2)
&& rtx_renumbered_equal_p (XEXP (cond1, 1),
XEXP (cond2, 0))
&& rtx_renumbered_equal_p (XEXP (cond1, 0),
XEXP (cond2, 1))));
if (match
&& !optimize_size
&& maybe_hot_bb_p (bb1)
&& maybe_hot_bb_p (bb2))
{
int prob2;
if (b1->dest == b2->dest)
prob2 = b2->probability;
else
prob2 = REG_BR_PROB_BASE - b2->probability;
if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
{
if (dump_file)
fprintf (dump_file,
"Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
bb1->index, bb2->index, b1->probability, prob2);
return false;
}
}
if (dump_file && match)
fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
bb1->index, bb2->index);
return match;
}
{
rtx label1, label2;
rtx table1, table2;
if (tablejump_p (BB_END (bb1), &label1, &table1)
&& tablejump_p (BB_END (bb2), &label2, &table2)
&& GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
{
if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
{
bool identical = false;
rtx p1, p2;
p1 = PATTERN (table1);
p2 = PATTERN (table2);
if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
{
identical = true;
}
else if (GET_CODE (p1) == ADDR_DIFF_VEC
&& (XVECLEN (p1, 1) == XVECLEN (p2, 1))
&& rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
&& rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
{
int i;
identical = true;
for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
identical = false;
}
if (identical)
{
replace_label_data rr;
bool match;
rr.r1 = label1;
rr.r2 = label2;
rr.update_label_nuses = false;
for_each_rtx (&BB_END (bb1), replace_label, &rr);
match = insns_match_p (mode, BB_END (bb1), BB_END (bb2));
if (dump_file && match)
fprintf (dump_file,
"Tablejumps in bb %i and %i match.\n",
bb1->index, bb2->index);
rr.r1 = label2;
rr.r2 = label1;
for_each_rtx (&BB_END (bb1), replace_label, &rr);
return match;
}
}
return false;
}
}
if (!insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
return false;
if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
return false;
FOR_EACH_EDGE (e1, ei, bb1->succs)
{
e2 = EDGE_SUCC (bb2, ei.index);
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 (nehedges1 != nehedges2
|| (fallthru1 != 0) != (fallthru2 != 0))
return false;
if (fallthru1)
{
basic_block d1 = (forwarder_block_p (fallthru1->dest)
? EDGE_SUCC (fallthru1->dest, 0)->dest: fallthru1->dest);
basic_block d2 = (forwarder_block_p (fallthru2->dest)
? EDGE_SUCC (fallthru2->dest, 0)->dest: fallthru2->dest);
if (d1 != d2)
return false;
}
{
rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
if (!n1 && n2)
return false;
if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
return false;
}
return true;
}
static bool
try_crossjump_to_edge (int mode, edge e1, edge e2)
{
int nmatch;
basic_block src1 = e1->src, src2 = e2->src;
basic_block redirect_to, redirect_from, to_remove;
rtx newpos1, newpos2;
edge s;
edge_iterator ei;
newpos1 = newpos2 = NULL_RTX;
if (flag_reorder_blocks_and_partition && no_new_pseudos)
return false;
if (EDGE_COUNT (src1->preds) == 1
&& FORWARDER_BLOCK_P (src1))
e1 = EDGE_PRED (src1, 0), src1 = e1->src;
if (EDGE_COUNT (src2->preds) == 1
&& FORWARDER_BLOCK_P (src2))
e2 = EDGE_PRED (src2, 0), src2 = e2->src;
if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
return false;
if (src1 == src2)
return false;
if (FORWARDER_BLOCK_P (e1->dest)
&& FORWARDER_BLOCK_P (EDGE_SUCC (e1->dest, 0)->dest))
return false;
if (FORWARDER_BLOCK_P (e2->dest)
&& FORWARDER_BLOCK_P (EDGE_SUCC (e2->dest, 0)->dest))
return false;
if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
return false;
if (!outgoing_edges_match (mode, src1, src2))
return false;
nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
&& (newpos1 != BB_HEAD (src1)))
return false;
{
rtx label1, label2;
rtx table1, table2;
if (tablejump_p (BB_END (src1), &label1, &table1)
&& tablejump_p (BB_END (src2), &label2, &table2)
&& label1 != label2)
{
replace_label_data rr;
rtx insn;
rr.r1 = label1;
rr.r2 = label2;
rr.update_label_nuses = true;
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
{
if (insn != BB_END (src1))
for_each_rtx (&insn, replace_label, &rr);
}
}
}
if (newpos2 == BB_HEAD (src2))
redirect_to = src2;
else
{
if (dump_file)
fprintf (dump_file, "Splitting bb %i before %i insns\n",
src2->index, nmatch);
redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
}
if (dump_file)
fprintf (dump_file,
"Cross jumping from bb %i to bb %i; %i common insns\n",
src1->index, src2->index, nmatch);
redirect_to->count += src1->count;
redirect_to->frequency += src1->frequency;
redirect_to->flags |= BB_DIRTY;
FOR_EACH_EDGE (s, ei, redirect_to->succs)
{
edge s2;
edge_iterator ei;
basic_block d = s->dest;
if (FORWARDER_BLOCK_P (d))
d = EDGE_SUCC (d, 0)->dest;
FOR_EACH_EDGE (s2, ei, src1->succs)
{
basic_block d2 = s2->dest;
if (FORWARDER_BLOCK_P (d2))
d2 = EDGE_SUCC (d2, 0)->dest;
if (d == d2)
break;
}
s->count += s2->count;
if (FORWARDER_BLOCK_P (s->dest))
{
EDGE_SUCC (s->dest, 0)->count += s2->count;
s->dest->count += s2->count;
s->dest->frequency += EDGE_FREQUENCY (s);
}
if (FORWARDER_BLOCK_P (s2->dest))
{
EDGE_SUCC (s2->dest, 0)->count -= s2->count;
if (EDGE_SUCC (s2->dest, 0)->count < 0)
EDGE_SUCC (s2->dest, 0)->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));
}
update_br_prob_note (redirect_to);
if (LABEL_P (newpos1))
newpos1 = NEXT_INSN (newpos1);
if (NOTE_P (newpos1))
newpos1 = NEXT_INSN (newpos1);
redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
to_remove = EDGE_SUCC (redirect_from, 0)->dest;
redirect_edge_and_branch_force (EDGE_SUCC (redirect_from, 0), redirect_to);
delete_basic_block (to_remove);
update_forwarder_flag (redirect_from);
if (redirect_to != src2)
update_forwarder_flag (src2);
return true;
}
static bool
try_crossjump_bb (int mode, basic_block bb)
{
edge e, e2, fallthru;
bool changed;
unsigned max, ix, ix2;
basic_block ev, ev2;
edge_iterator ei;
if (EDGE_COUNT (bb->preds) < 2)
return false;
if (!optimize_size
&& bb != EXIT_BLOCK_PTR
&& computed_jump_p (BB_END (bb)))
return false;
if (flag_reorder_blocks_and_partition
&& (BB_PARTITION (EDGE_PRED (bb, 0)->src) != BB_PARTITION (EDGE_PRED (bb, 1)->src)
|| (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING)))
return false;
fallthru = NULL;
max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
if (EDGE_COUNT (bb->preds) > max)
return false;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->flags & EDGE_FALLTHRU)
fallthru = e;
}
changed = false;
for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
{
e = EDGE_PRED (ev, ix);
ix++;
if (fallthru)
{
if (e == fallthru)
continue;
if (!first_pass
&& (!(e->src->flags & BB_DIRTY)
&& !(fallthru->src->flags & BB_DIRTY)))
continue;
if (try_crossjump_to_edge (mode, e, fallthru))
{
changed = true;
ix = 0;
ev = bb;
continue;
}
}
if (EDGE_SUCC (e->src, 0) != e)
continue;
for (ix2 = 0, ev2 = bb; ix2 < EDGE_COUNT (ev2->preds); )
{
e2 = EDGE_PRED (ev2, ix2);
ix2++;
if (e2 == e)
continue;
if (e2 == fallthru)
continue;
if (e->src->index > e2->src->index)
continue;
if (!first_pass
&& (!(e->src->flags & BB_DIRTY)
&& !(e2->src->flags & BB_DIRTY)))
continue;
if (try_crossjump_to_edge (mode, e, e2))
{
changed = true;
ev2 = bb;
ix = 0;
break;
}
}
}
return changed;
}
static bool
try_optimize_cfg (int mode)
{
bool changed_overall = false;
bool changed;
int iterations = 0;
basic_block bb, b, next;
if (mode & CLEANUP_CROSSJUMP)
add_noreturn_fake_exit_edges ();
FOR_EACH_BB (bb)
update_forwarder_flag (bb);
if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
clear_bb_flags ();
if (! targetm.cannot_modify_jumps_p ())
{
first_pass = true;
do
{
changed = false;
iterations++;
if (dump_file)
fprintf (dump_file,
"\n\ntry_optimize_cfg iteration %i\n\n",
iterations);
for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
{
basic_block c;
edge s;
bool changed_here = false;
while (EDGE_COUNT (b->preds) == 0)
{
c = b->prev_bb;
if (dump_file)
fprintf (dump_file, "Deleting block %i.\n",
b->index);
delete_basic_block (b);
if (!(mode & CLEANUP_CFGLAYOUT))
changed = true;
b = c;
}
if (EDGE_COUNT (b->preds) == 1
&& (EDGE_PRED (b, 0)->flags & EDGE_FALLTHRU)
&& !(EDGE_PRED (b, 0)->flags & EDGE_COMPLEX)
&& LABEL_P (BB_HEAD (b))
&& (EDGE_PRED (b, 0)->src == ENTRY_BLOCK_PTR
|| !JUMP_P (BB_END (EDGE_PRED (b, 0)->src))
|| ! label_is_jump_target_p (BB_HEAD (b),
BB_END (EDGE_PRED (b, 0)->src))))
{
rtx label = BB_HEAD (b);
delete_insn_chain (label, label);
if (NOTE_LINE_NUMBER (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
{
rtx bb_note = NEXT_INSN (BB_HEAD (b));
reorder_insns_nobb (label, label, bb_note);
BB_HEAD (b) = bb_note;
}
if (dump_file)
fprintf (dump_file, "Deleted label in block %i.\n",
b->index);
}
if (!(mode & CLEANUP_CFGLAYOUT)
&& EDGE_COUNT (b->preds) == 1
&& (EDGE_PRED (b, 0)->flags & EDGE_FALLTHRU)
&& !LABEL_P (BB_HEAD (b))
&& FORWARDER_BLOCK_P (b)
&& (EDGE_SUCC (b, 0)->flags & EDGE_FALLTHRU)
&& n_basic_blocks > 1)
{
if (dump_file)
fprintf (dump_file,
"Deleting fallthru block %i.\n",
b->index);
c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
redirect_edge_succ_nodup (EDGE_PRED (b, 0), EDGE_SUCC (b, 0)->dest);
delete_basic_block (b);
changed = true;
b = c;
}
if (EDGE_COUNT (b->succs) == 1
&& (s = EDGE_SUCC (b, 0))
&& !(s->flags & EDGE_COMPLEX)
&& (c = s->dest) != EXIT_BLOCK_PTR
&& EDGE_COUNT (c->preds) == 1
&& b != c)
{
if ((mode & CLEANUP_CFGLAYOUT)
&& can_merge_blocks_p (b, c))
{
merge_blocks (b, c);
update_forwarder_flag (b);
changed_here = true;
}
else if (!(mode & CLEANUP_CFGLAYOUT)
&& (!JUMP_P (BB_END (b))
|| (reload_completed
? simplejump_p (BB_END (b))
: (onlyjump_p (BB_END (b))
&& !tablejump_p (BB_END (b),
NULL, NULL))))
&& (next = merge_blocks_move (s, b, c, mode)))
{
b = next;
changed_here = true;
}
}
if ((mode & CLEANUP_EXPENSIVE)
&& !(mode & CLEANUP_CFGLAYOUT)
&& try_simplify_condjump (b))
changed_here = true;
if (EDGE_COUNT (b->succs) == 1
&& EDGE_SUCC (b, 0)->dest != EXIT_BLOCK_PTR
&& onlyjump_p (BB_END (b))
&& !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
&& try_redirect_by_replacing_jump (EDGE_SUCC (b, 0), EDGE_SUCC (b, 0)->dest,
(mode & CLEANUP_CFGLAYOUT) != 0))
{
update_forwarder_flag (b);
changed_here = true;
}
if (try_forward_edges (mode, b))
changed_here = true;
if ((mode & CLEANUP_CROSSJUMP)
&& try_crossjump_bb (mode, b))
changed_here = true;
if (!changed_here)
b = b->next_bb;
else
changed = true;
}
if ((mode & CLEANUP_CROSSJUMP)
&& try_crossjump_bb (mode, EXIT_BLOCK_PTR))
changed = true;
#ifdef ENABLE_CHECKING
if (changed)
verify_flow_info ();
#endif
changed_overall |= changed;
first_pass = false;
}
while (changed);
}
if (mode & CLEANUP_CROSSJUMP)
remove_fake_exit_edges ();
clear_aux_for_blocks ();
return changed_overall;
}
bool
delete_unreachable_blocks (void)
{
bool changed = false;
basic_block b, next_bb;
find_unreachable_blocks ();
for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
{
next_bb = b->next_bb;
if (!(b->flags & BB_REACHABLE))
{
delete_basic_block (b);
changed = true;
}
}
if (changed)
tidy_fallthru_edges ();
return changed;
}
bool
merge_seq_blocks (void)
{
basic_block bb;
bool changed = false;
for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; )
{
if (EDGE_COUNT (bb->succs) == 1
&& can_merge_blocks_p (bb, EDGE_SUCC (bb, 0)->dest))
{
merge_blocks (bb, EDGE_SUCC (bb, 0)->dest);
changed = true;
continue;
}
bb = bb->next_bb;
}
return changed;
}
bool
cleanup_cfg (int mode)
{
bool changed = false;
timevar_push (TV_CLEANUP_CFG);
if (delete_unreachable_blocks ())
{
changed = true;
if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_UPDATE_LIFE))
&& !reload_completed)
delete_trivially_dead_insns (get_insns(), max_reg_num ());
}
compact_blocks ();
while (try_optimize_cfg (mode))
{
delete_unreachable_blocks (), changed = true;
if (mode & CLEANUP_UPDATE_LIFE)
{
if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
| PROP_KILL_DEAD_CODE
| ((mode & CLEANUP_LOG_LINKS)
? PROP_LOG_LINKS : 0)))
break;
}
else if (!(mode & CLEANUP_NO_INSN_DEL)
&& (mode & CLEANUP_EXPENSIVE)
&& !reload_completed)
{
if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
break;
}
else
break;
delete_dead_jumptables ();
}
free_EXPR_LIST_list (&label_value_list);
timevar_pop (TV_CLEANUP_CFG);
return changed;
}