/* If-conversion support.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
Free Software Foundation, Inc.
This file is part of GCC.
#include "hard-reg-set.h"
#include "basic-block.h"
#include "expr.h"
-#include "real.h"
#include "output.h"
#include "optabs.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "tm_p.h"
#include "cfgloop.h"
static bool cheap_bb_rtx_cost_p (const_basic_block, int);
static rtx first_active_insn (basic_block);
static rtx last_active_insn (basic_block, int);
+static rtx find_active_insn_before (basic_block, rtx);
+static rtx find_active_insn_after (basic_block, rtx);
static basic_block block_fallthru (basic_block);
static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int);
static rtx cond_exec_get_condition (rtx);
return insn;
}
+/* Return the active insn before INSN inside basic block CURR_BB. */
+
+static rtx
+find_active_insn_before (basic_block curr_bb, rtx insn)
+{
+ if (!insn || insn == BB_HEAD (curr_bb))
+ return NULL_RTX;
+
+ while ((insn = PREV_INSN (insn)) != NULL_RTX)
+ {
+ if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
+ break;
+
+ /* No other active insn all the way to the start of the basic block. */
+ if (insn == BB_HEAD (curr_bb))
+ return NULL_RTX;
+ }
+
+ return insn;
+}
+
+/* Return the active insn after INSN inside basic block CURR_BB. */
+
+static rtx
+find_active_insn_after (basic_block curr_bb, rtx insn)
+{
+ if (!insn || insn == BB_END (curr_bb))
+ return NULL_RTX;
+
+ while ((insn = NEXT_INSN (insn)) != NULL_RTX)
+ {
+ if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
+ break;
+
+ /* No other active insn all the way to the end of the basic block. */
+ if (insn == BB_END (curr_bb))
+ return NULL_RTX;
+ }
+
+ return insn;
+}
+
/* Return the basic block reached by falling though the basic block BB. */
static basic_block
block_fallthru (basic_block bb)
{
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, bb->succs)
- if (e->flags & EDGE_FALLTHRU)
- break;
+ edge e = find_fallthru_edge (bb->succs);
return (e) ? e->dest : NULL_BLOCK;
}
rtx false_expr; /* test for then block insns */
rtx true_prob_val; /* probability of else block */
rtx false_prob_val; /* probability of then block */
- int n_insns;
+ rtx then_last_head = NULL_RTX; /* Last match at the head of THEN */
+ rtx else_last_head = NULL_RTX; /* Last match at the head of ELSE */
+ rtx then_first_tail = NULL_RTX; /* First match at the tail of THEN */
+ rtx else_first_tail = NULL_RTX; /* First match at the tail of ELSE */
+ int then_n_insns, else_n_insns, n_insns;
enum rtx_code false_code;
/* If test is comprised of && or || elements, and we've failed at handling
number of insns and see if it is small enough to convert. */
then_start = first_active_insn (then_bb);
then_end = last_active_insn (then_bb, TRUE);
- n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
+ then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
+ n_insns = then_n_insns;
max = MAX_CONDITIONAL_EXECUTE;
if (else_bb)
{
+ int n_matching;
+
max *= 2;
else_start = first_active_insn (else_bb);
else_end = last_active_insn (else_bb, TRUE);
- n_insns += ce_info->num_else_insns = count_bb_insns (else_bb);
+ else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb);
+ n_insns += else_n_insns;
+
+ /* Look for matching sequences at the head and tail of the two blocks,
+ and limit the range of insns to be converted if possible. */
+ n_matching = flow_find_cross_jump (then_bb, else_bb,
+ &then_first_tail, &else_first_tail);
+ if (then_first_tail == BB_HEAD (then_bb))
+ then_start = then_end = NULL_RTX;
+ if (else_first_tail == BB_HEAD (else_bb))
+ else_start = else_end = NULL_RTX;
+
+ if (n_matching > 0)
+ {
+ if (then_end)
+ then_end = find_active_insn_before (then_bb, then_first_tail);
+ if (else_end)
+ else_end = find_active_insn_before (else_bb, else_first_tail);
+ n_insns -= 2 * n_matching;
+ }
+
+ if (then_start && else_start)
+ {
+ int longest_match = MIN (then_n_insns - n_matching,
+ else_n_insns - n_matching);
+ n_matching
+ = flow_find_head_matching_sequence (then_bb, else_bb,
+ &then_last_head,
+ &else_last_head,
+ longest_match);
+
+ if (n_matching > 0)
+ {
+ rtx insn;
+
+ /* We won't pass the insns in the head sequence to
+ cond_exec_process_insns, so we need to test them here
+ to make sure that they don't clobber the condition. */
+ for (insn = BB_HEAD (then_bb);
+ insn != NEXT_INSN (then_last_head);
+ insn = NEXT_INSN (insn))
+ if (!LABEL_P (insn) && !NOTE_P (insn)
+ && !DEBUG_INSN_P (insn)
+ && modified_in_p (test_expr, insn))
+ return FALSE;
+ }
+
+ if (then_last_head == then_end)
+ then_start = then_end = NULL_RTX;
+ if (else_last_head == else_end)
+ else_start = else_end = NULL_RTX;
+
+ if (n_matching > 0)
+ {
+ if (then_start)
+ then_start = find_active_insn_after (then_bb, then_last_head);
+ if (else_start)
+ else_start = find_active_insn_after (else_bb, else_last_head);
+ n_insns -= 2 * n_matching;
+ }
+ }
}
if (n_insns > max)
fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
n_insns, (n_insns == 1) ? " was" : "s were");
- /* Merge the blocks! */
+ /* Merge the blocks! If we had matching sequences, make sure to delete one
+ copy at the appropriate location first: delete the copy in the THEN branch
+ for a tail sequence so that the remaining one is executed last for both
+ branches, and delete the copy in the ELSE branch for a head sequence so
+ that the remaining one is executed first for both branches. */
+ if (then_first_tail)
+ {
+ rtx from = then_first_tail;
+ if (!INSN_P (from))
+ from = find_active_insn_after (then_bb, from);
+ delete_insn_chain (from, BB_END (then_bb), false);
+ }
+ if (else_last_head)
+ delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
+
merge_if_block (ce_info);
cond_exec_changed_p = TRUE;
return TRUE;
noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
{
+ rtx target ATTRIBUTE_UNUSED;
+ int unsignedp ATTRIBUTE_UNUSED;
+
/* If earliest == jump, try to build the cmove insn directly.
This is helpful when combine has created some complex condition
(like for alpha's cmovlbs) that we can't hope to regenerate
return NULL_RTX;
#if HAVE_conditional_move
- return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
- vtrue, vfalse, GET_MODE (x),
- (code == LTU || code == GEU
- || code == LEU || code == GTU));
+ unsignedp = (code == LTU || code == GEU
+ || code == LEU || code == GTU);
+
+ target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
+ vtrue, vfalse, GET_MODE (x),
+ unsignedp);
+ if (target)
+ return target;
+
+ /* We might be faced with a situation like:
+
+ x = (reg:M TARGET)
+ vtrue = (subreg:M (reg:N VTRUE) BYTE)
+ vfalse = (subreg:M (reg:N VFALSE) BYTE)
+
+ We can't do a conditional move in mode M, but it's possible that we
+ could do a conditional move in mode N instead and take a subreg of
+ the result.
+
+ If we can't create new pseudos, though, don't bother. */
+ if (reload_completed)
+ return NULL_RTX;
+
+ if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
+ {
+ rtx reg_vtrue = SUBREG_REG (vtrue);
+ rtx reg_vfalse = SUBREG_REG (vfalse);
+ unsigned int byte_vtrue = SUBREG_BYTE (vtrue);
+ unsigned int byte_vfalse = SUBREG_BYTE (vfalse);
+ rtx promoted_target;
+
+ if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
+ || byte_vtrue != byte_vfalse
+ || (SUBREG_PROMOTED_VAR_P (vtrue)
+ != SUBREG_PROMOTED_VAR_P (vfalse))
+ || (SUBREG_PROMOTED_UNSIGNED_P (vtrue)
+ != SUBREG_PROMOTED_UNSIGNED_P (vfalse)))
+ return NULL_RTX;
+
+ promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
+
+ target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b,
+ VOIDmode, reg_vtrue, reg_vfalse,
+ GET_MODE (reg_vtrue), unsignedp);
+ /* Nope, couldn't do it in that mode either. */
+ if (!target)
+ return NULL_RTX;
+
+ target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
+ SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
+ SUBREG_PROMOTED_UNSIGNED_SET (target, SUBREG_PROMOTED_UNSIGNED_P (vtrue));
+ emit_move_insn (x, target);
+ return x;
+ }
+ else
+ return NULL_RTX;
#else
/* We'll never get here, as noce_process_if_block doesn't call the
functions involved. Ifdef code, however, should be discouraged
if insn_rtx_cost can't be estimated. */
if (insn_a)
{
- insn_cost = insn_rtx_cost (PATTERN (insn_a),
- optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a)));
+ insn_cost
+ = insn_rtx_cost (PATTERN (insn_a),
+ optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a)));
if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost))
return FALSE;
}
if (insn_b)
{
- insn_cost += insn_rtx_cost (PATTERN (insn_b),
- optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b)));
+ insn_cost
+ += insn_rtx_cost (PATTERN (insn_b),
+ optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b)));
if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost))
return FALSE;
}
/* Otherwise, fall back on canonicalize_condition to do the dirty
work of manipulating MODE_CC values and COMPARE rtx codes. */
- return canonicalize_condition (jump, cond, reverse, earliest,
- NULL_RTX, false, true);
+ tmp = canonicalize_condition (jump, cond, reverse, earliest,
+ NULL_RTX, false, true);
+
+ /* We don't handle side-effects in the condition, like handling
+ REG_INC notes and making sure no duplicate conditions are emitted. */
+ if (tmp != NULL_RTX && side_effects_p (tmp))
+ return NULL_RTX;
+
+ return tmp;
}
/* Return true if OP is ok for if-then-else processing. */
}
else
{
- insn_b = prev_nonnote_insn (if_info->cond_earliest);
- while (insn_b && DEBUG_INSN_P (insn_b))
- insn_b = prev_nonnote_insn (insn_b);
+ insn_b = prev_nonnote_nondebug_insn (if_info->cond_earliest);
/* We're going to be moving the evaluation of B down from above
COND_EARLIEST to JUMP. Make sure the relevant data is still
intact. */
the lifetime of hard registers on small register class machines. */
orig_x = x;
if (!REG_P (x)
- || (SMALL_REGISTER_CLASSES
- && REGNO (x) < FIRST_PSEUDO_REGISTER))
+ || (HARD_REGISTER_P (x)
+ && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
{
if (GET_MODE (x) == BLKmode)
return FALSE;
REGS. COND is the condition we will test. */
static int
-check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) **regs, rtx cond)
+check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) **regs,
+ rtx cond)
{
rtx insn;
dest = SET_DEST (set);
src = SET_SRC (set);
if (!REG_P (dest)
- || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
+ || (HARD_REGISTER_P (dest)
+ && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
return FALSE;
if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
/* Make sure the blocks are suitable. */
if (!check_cond_move_block (then_bb, then_vals, &then_regs, cond)
- || (else_bb && !check_cond_move_block (else_bb, else_vals, &else_regs, cond)))
+ || (else_bb
+ && !check_cond_move_block (else_bb, else_vals, &else_regs, cond)))
{
VEC_free (int, heap, then_regs);
VEC_free (int, heap, else_regs);
source register does not change after the assignment. Also count
the number of registers set in only one of the blocks. */
c = 0;
- for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
+ FOR_EACH_VEC_ELT (int, then_regs, i, reg)
{
if (!then_vals[reg] && !else_vals[reg])
continue;
}
/* Finish off c for MAX_CONDITIONAL_EXECUTE. */
- for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
+ FOR_EACH_VEC_ELT (int, else_regs, i, reg)
if (!then_vals[reg])
++c;
Return TRUE if we were successful at converting the block. */
static int
-noce_find_if_block (basic_block test_bb,
- edge then_edge, edge else_edge,
+noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
int pass)
{
basic_block then_bb, else_bb, join_bb;
return FALSE;
/* If this is not a standard conditional jump, we can't parse it. */
- cond = noce_get_condition (jump,
- &cond_earliest,
- then_else_reversed);
+ cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
if (!cond)
return FALSE;
/* Otherwise this must be a multiway branch of some sort. */
return NULL;
- memset (&ce_info, '\0', sizeof (ce_info));
+ memset (&ce_info, 0, sizeof (ce_info));
ce_info.test_bb = test_bb;
ce_info.then_bb = then_edge->dest;
ce_info.else_bb = else_edge->dest;
IFCVT_INIT_EXTRA_FIELDS (&ce_info);
#endif
- if (! reload_completed
+ if (!reload_completed
&& noce_find_if_block (test_bb, then_edge, else_edge, pass))
goto success;
- if (targetm.have_conditional_execution () && reload_completed
+ if (reload_completed
+ && targetm.have_conditional_execution ()
&& cond_exec_find_if_block (&ce_info))
goto success;
if (HAVE_trap
- && optab_handler (ctrap_optab, word_mode)->insn_code != CODE_FOR_nothing
+ && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
&& find_cond_trap (test_bb, then_edge, else_edge))
goto success;
if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
- && (! targetm.have_conditional_execution () || reload_completed))
+ && (reload_completed || !targetm.have_conditional_execution ()))
{
if (find_if_case_1 (test_bb, then_edge, else_edge))
goto success;
ce_info->last_test_bb = test_bb;
/* We only ever should get here after reload,
- and only if we have conditional execution. */
- gcc_assert (targetm.have_conditional_execution () && reload_completed);
+ and if we have conditional execution. */
+ gcc_assert (reload_completed && targetm.have_conditional_execution ());
/* Discover if any fall through predecessors of the current test basic block
were && tests (which jump to the else block) or || tests (which jump to
if (EDGE_COUNT (then_bb->succs) > 0
&& (!single_succ_p (then_bb)
|| (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
- || (epilogue_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
+ || (epilogue_completed
+ && tablejump_p (BB_END (then_bb), NULL, NULL))))
return FALSE;
/* If the THEN block has no successors, conditional execution can still
else if (single_succ_p (else_bb)
&& single_succ (then_bb) == single_succ (else_bb)
&& single_pred_p (else_bb)
- && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
- && ! (epilogue_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
+ && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
+ && !(epilogue_completed
+ && tablejump_p (BB_END (else_bb), NULL, NULL)))
join_bb = single_succ (else_bb);
/* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
basic_block other_bb, basic_block new_dest, int reversep)
{
rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
+ bitmap merge_set = NULL, merge_set_noclobber = NULL;
/* Number of pending changes. */
int n_validated_changes = 0;
earliest = jump;
}
#endif
+
/* Try the NCE path if the CE path did not result in any changes. */
if (n_validated_changes == 0)
{
that any registers modified are dead at the branch site. */
rtx insn, cond, prev;
- bitmap merge_set, test_live, test_set;
- unsigned i, fail = 0;
- bitmap_iterator bi;
+ bitmap test_live, test_set;
+ bool intersect = false;
/* Check for no calls or trapping operations. */
for (insn = head; ; insn = NEXT_INSN (insn))
/* Collect:
MERGE_SET = set of registers set in MERGE_BB
+ MERGE_SET_NOCLOBBER = like MERGE_SET, but only includes registers
+ that are really set, not just clobbered.
TEST_LIVE = set of registers live at EARLIEST
- TEST_SET = set of registers set between EARLIEST and the
- end of the block. */
+ TEST_SET = set of registers set between EARLIEST and the
+ end of the block. */
merge_set = BITMAP_ALLOC (®_obstack);
- test_live = BITMAP_ALLOC (®_obstack);
- test_set = BITMAP_ALLOC (®_obstack);
+ merge_set_noclobber = BITMAP_ALLOC (®_obstack);
- /* ??? bb->local_set is only valid during calculate_global_regs_live,
- so we must recompute usage for MERGE_BB. Not so bad, I suppose,
- since we've already asserted that MERGE_BB is small. */
/* If we allocated new pseudos (e.g. in the conditional move
expander called from noce_emit_cmove), we must resize the
array first. */
{
if (NONDEBUG_INSN_P (insn))
{
- unsigned int uid = INSN_UID (insn);
- df_ref *def_rec;
- for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
- {
- df_ref def = *def_rec;
- bitmap_set_bit (merge_set, DF_REF_REGNO (def));
- }
+ df_simulate_find_defs (insn, merge_set);
+ df_simulate_find_noclobber_defs (insn, merge_set_noclobber);
}
}
/* For small register class machines, don't lengthen lifetimes of
hard registers before reload. */
- if (SMALL_REGISTER_CLASSES && ! reload_completed)
+ if (! reload_completed
+ && targetm.small_register_classes_for_mode_p (VOIDmode))
{
- EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
+ unsigned i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (merge_set_noclobber, 0, i, bi)
{
if (i < FIRST_PSEUDO_REGISTER
&& ! fixed_regs[i]
&& ! global_regs[i])
- fail = 1;
+ goto fail;
}
}
/* For TEST, we're interested in a range of insns, not a whole block.
Moreover, we're interested in the insns live from OTHER_BB. */
+ test_live = BITMAP_ALLOC (®_obstack);
+ test_set = BITMAP_ALLOC (®_obstack);
/* The loop below takes the set of live registers
after JUMP, and calculates the live set before EARLIEST. */
}
/* We can perform the transformation if
- MERGE_SET & (TEST_SET | TEST_LIVE)
+ MERGE_SET_NOCLOBBER & TEST_SET
+ and
+ MERGE_SET & TEST_LIVE
and
TEST_SET & DF_LIVE_IN (merge_bb)
are empty. */
- if (bitmap_intersect_p (test_set, merge_set)
- || bitmap_intersect_p (test_live, merge_set)
+ if (bitmap_intersect_p (merge_set_noclobber, test_set)
+ || bitmap_intersect_p (merge_set, test_live)
|| bitmap_intersect_p (test_set, df_get_live_in (merge_bb)))
- fail = 1;
+ intersect = true;
- BITMAP_FREE (merge_set);
BITMAP_FREE (test_live);
BITMAP_FREE (test_set);
- if (fail)
- return FALSE;
+ if (intersect)
+ goto fail;
}
no_body:
if (end == BB_END (merge_bb))
BB_END (merge_bb) = PREV_INSN (head);
- /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
- notes might become invalid. */
+ /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
+ notes being moved might become invalid. */
insn = head;
do
{
remove_note (insn, note);
} while (insn != end && (insn = NEXT_INSN (insn)));
+ /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
+ notes referring to the registers being set might become invalid. */
+ if (merge_set)
+ {
+ unsigned i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
+ remove_reg_equal_equiv_notes_for_regno (i);
+
+ BITMAP_FREE (merge_set);
+ BITMAP_FREE (merge_set_noclobber);
+ }
+
reorder_insns (head, end, PREV_INSN (earliest));
}
cancel:
cancel_changes (0);
+ fail:
+ if (merge_set)
+ {
+ BITMAP_FREE (merge_set);
+ BITMAP_FREE (merge_set_noclobber);
+ }
return FALSE;
}
\f