/* If-conversion support.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
This file is part of GCC.
#include "target.h"
#include "timevar.h"
#include "tree-pass.h"
+#include "vec.h"
+#include "vecprim.h"
#ifndef HAVE_conditional_execution
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);
-static int cond_exec_process_if_block (ce_if_block_t *, int);
-static rtx noce_get_condition (rtx, rtx *);
+static rtx noce_get_condition (rtx, rtx *, bool);
static int noce_operand_ok (rtx);
-static int noce_process_if_block (ce_if_block_t *);
-static int process_if_block (ce_if_block_t *);
static void merge_if_block (ce_if_block_t *);
static int find_cond_trap (basic_block, edge, edge);
static basic_block find_if_header (basic_block, int);
static int block_jumps_and_fallthru_p (basic_block, basic_block);
-static int find_if_block (ce_if_block_t *);
+static int noce_find_if_block (basic_block, edge, edge, int);
+static int cond_exec_find_if_block (ce_if_block_t *);
static int find_if_case_1 (basic_block, edge, edge);
static int find_if_case_2 (basic_block, edge, edge);
static int find_memory (rtx *, void *);
}
else if (CALL_P (insn))
return false;
-
+
if (insn == BB_END (bb))
break;
insn = NEXT_INSN (insn);
struct noce_if_info
{
- basic_block test_bb;
+ /* The basic blocks that make up the IF-THEN-{ELSE-,}JOIN block. */
+ basic_block test_bb, then_bb, else_bb, join_bb;
+
+ /* The jump that ends TEST_BB. */
+ rtx jump;
+
+ /* The jump condition. */
+ rtx cond;
+
+ /* New insns should be inserted before this one. */
+ rtx cond_earliest;
+
+ /* Insns in the THEN and ELSE block. There is always just this
+ one insns in those blocks. The insns are single_set insns.
+ If there was no ELSE block, INSN_B is the last insn before
+ COND_EARLIEST, or NULL_RTX. In the former case, the insn
+ operands are still valid, as if INSN_B was moved down below
+ the jump. */
rtx insn_a, insn_b;
- rtx x, a, b;
- rtx jump, cond, cond_earliest;
- /* True if "b" was originally evaluated unconditionally. */
- bool b_unconditional;
+
+ /* The SET_SRC of INSN_A and INSN_B. */
+ rtx a, b;
+
+ /* The SET_DEST of INSN_A. */
+ rtx x;
};
static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
? emit_move_insn (x, y)
: emit_insn (gen_rtx_SET (VOIDmode, x, y));
seq = get_insns ();
- end_sequence();
+ end_sequence ();
if (recog_memoized (insn) <= 0)
{
unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
- /* store_bit_field expects START to be relative to
- BYTES_BIG_ENDIAN and adjusts this value for machines with
- BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
+ /* store_bit_field expects START to be relative to
+ BYTES_BIG_ENDIAN and adjusts this value for machines with
+ BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
invoke store_bit_field again it is necessary to have the START
value from the first call. */
if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
end_sequence ();
}
break;
-
+
case RTX_BIN_ARITH:
case RTX_COMM_ARITH:
ot = code_to_optab[GET_CODE (y)];
end_sequence ();
}
break;
-
+
default:
break;
}
}
-
+
emit_insn (seq);
return;
}
int normalize, can_reverse;
enum machine_mode mode;
- if (! no_new_pseudos
- && GET_CODE (if_info->a) == CONST_INT
+ if (GET_CODE (if_info->a) == CONST_INT
&& GET_CODE (if_info->b) == CONST_INT)
{
mode = GET_MODE (if_info->x);
rtx target, seq;
int subtract, normalize;
- if (! no_new_pseudos
- && GET_CODE (if_info->a) == PLUS
+ if (GET_CODE (if_info->a) == PLUS
&& rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
&& (reversed_comparison_code (if_info->cond, if_info->jump)
!= UNKNOWN))
int reversep;
reversep = 0;
- if (! no_new_pseudos
- && (BRANCH_COST >= 2
- || STORE_FLAG_VALUE == -1)
+ if ((BRANCH_COST >= 2
+ || STORE_FLAG_VALUE == -1)
&& ((if_info->a == const0_rtx
&& rtx_equal_p (if_info->b, if_info->x))
|| ((reversep = (reversed_comparison_code (if_info->cond,
conditional on their addresses followed by a load. Don't do this
early because it'll screw alias analysis. Note that we've
already checked for no side effects. */
- if (! no_new_pseudos && cse_not_expected
+ /* ??? FIXME: Magic number 5. */
+ if (cse_not_expected
&& MEM_P (a) && MEM_P (b)
&& BRANCH_COST >= 5)
{
return FALSE;
}
else
+ insn_cost = 0;
+
+ if (insn_b)
{
- insn_cost = 0;
+ insn_cost += insn_rtx_cost (PATTERN (insn_b));
+ if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST))
+ return FALSE;
}
- if (insn_b) {
- insn_cost += insn_rtx_cost (PATTERN (insn_b));
- if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST))
- return FALSE;
- }
-
/* Possibly rearrange operands to make things come out more natural. */
if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
{
{
rtx set;
- if (no_new_pseudos)
- goto end_seq_and_fail;
-
if (is_mem)
{
tmp = gen_reg_rtx (GET_MODE (a));
{
rtx set, last;
- if (no_new_pseudos)
- goto end_seq_and_fail;
-
if (is_mem)
{
tmp = gen_reg_rtx (GET_MODE (b));
enum rtx_code code, op;
int unsignedp;
- /* ??? Can't guarantee that expand_binop won't create pseudos. */
- if (no_new_pseudos)
- return FALSE;
-
/* ??? Reject modes with NaNs or signed zeros since we don't know how
they will be resolved with an SMIN/SMAX. It wouldn't be too hard
to get the target to tell us... */
rtx cond, earliest, target, seq, a, b, c;
int negate;
- /* ??? Can't guarantee that expand_binop won't create pseudos. */
- if (no_new_pseudos)
- return FALSE;
-
/* Recognize A and B as constituting an ABS or NABS. The canonical
form is a branch around the negation, taken when the object is the
first operand of a comparison against 0 that evaluates to true. */
rtx cond, t, m, c, seq;
enum machine_mode mode;
enum rtx_code code;
-
- if (no_new_pseudos)
- return FALSE;
+ bool b_unconditional;
cond = if_info->cond;
code = GET_CODE (cond);
return FALSE;
/* This is only profitable if T is cheap, or T is unconditionally
- executed/evaluated in the original insn sequence. */
+ executed/evaluated in the original insn sequence. The latter
+ happens if INSN_B was taken from TEST_BB, or if there was no
+ INSN_B which can happen for e.g. conditional stores to memory. */
+ b_unconditional = (if_info->insn_b == NULL_RTX
+ || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb);
if (rtx_cost (t, SET) >= COSTS_N_INSNS (2)
- && (!if_info->b_unconditional
+ && (!b_unconditional
|| t != if_info->b))
return FALSE;
return FALSE;
bitnum = INTVAL (XEXP (cond, 2));
mode = GET_MODE (x);
- if (bitnum >= HOST_BITS_PER_WIDE_INT)
+ if (BITS_BIG_ENDIAN)
+ bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
+ if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
return FALSE;
}
else
/* Similar to get_condition, only the resulting condition must be
- valid at JUMP, instead of at EARLIEST. */
+ valid at JUMP, instead of at EARLIEST.
+
+ If THEN_ELSE_REVERSED is true, the fallthrough goes to the THEN
+ block of the caller, and we have to reverse the condition. */
static rtx
-noce_get_condition (rtx jump, rtx *earliest)
+noce_get_condition (rtx jump, rtx *earliest, bool then_else_reversed)
{
rtx cond, set, tmp;
bool reverse;
reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
&& XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
+ /* We may have to reverse because the caller's if block is not canonical
+ (i.e. the ELSE block isn't the fallthrough block for the TEST block). */
+ if (then_else_reversed)
+ reverse = !reverse;
+
/* If the condition variable is a register and is MODE_INT, accept it. */
cond = XEXP (SET_SRC (set), 0);
NULL_RTX, false, true);
}
-/* Initialize for a simple IF-THEN or IF-THEN-ELSE block. We will not
- be using conditional execution. Set some fields of IF_INFO based
- on CE_INFO: test_bb, cond, jump, cond_earliest. Return TRUE if
- things look OK. */
-
-static int
-noce_init_if_info (struct ce_if_block *ce_info, struct noce_if_info *if_info)
-{
- basic_block test_bb = ce_info->test_bb;
- rtx cond, jump;
-
- /* If test is comprised of && or || elements, don't handle it unless
- it is the special case of && elements without an ELSE block. */
- if (ce_info->num_multiple_test_blocks)
- {
- if (ce_info->else_bb || !ce_info->and_and_p)
- return FALSE;
-
- ce_info->test_bb = test_bb = ce_info->last_test_bb;
- ce_info->num_multiple_test_blocks = 0;
- ce_info->num_and_and_blocks = 0;
- ce_info->num_or_or_blocks = 0;
- }
-
- /* If this is not a standard conditional jump, we can't parse it. */
- jump = BB_END (test_bb);
- cond = noce_get_condition (jump, &if_info->cond_earliest);
- if (!cond)
- return FALSE;
-
- /* If the conditional jump is more than just a conditional
- jump, then we can not do if-conversion on this block. */
- if (! onlyjump_p (jump))
- return FALSE;
-
- /* We must be comparing objects whose modes imply the size. */
- if (GET_MODE (XEXP (cond, 0)) == BLKmode)
- return FALSE;
-
- if_info->test_bb = test_bb;
- if_info->cond = cond;
- if_info->jump = jump;
-
- return TRUE;
-}
-
/* Return true if OP is ok for if-then-else processing. */
static int
return false;
}
-/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
- without using conditional execution. Return TRUE if we were
- successful at converting the block. */
+/* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
+ it without using conditional execution. Return TRUE if we were successful
+ at converting the block. */
static int
-noce_process_if_block (struct ce_if_block * ce_info)
+noce_process_if_block (struct noce_if_info *if_info)
{
- basic_block test_bb = ce_info->test_bb; /* test block */
- basic_block then_bb = ce_info->then_bb; /* THEN */
- basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
- struct noce_if_info if_info;
+ basic_block test_bb = if_info->test_bb; /* test block */
+ basic_block then_bb = if_info->then_bb; /* THEN */
+ basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
+ basic_block join_bb = if_info->join_bb; /* JOIN */
+ rtx jump = if_info->jump;
+ rtx cond = if_info->cond;
rtx insn_a, insn_b;
rtx set_a, set_b;
rtx orig_x, x, a, b;
- rtx jump, cond;
/* We're looking for patterns of the form
??? For future expansion, look for multiple X in such patterns. */
- if (!noce_init_if_info (ce_info, &if_info))
- return FALSE;
-
- cond = if_info.cond;
- jump = if_info.jump;
-
/* Look for one of the potential sets. */
insn_a = first_active_insn (then_bb);
if (! insn_a
}
else
{
- insn_b = prev_nonnote_insn (if_info.cond_earliest);
+ insn_b = prev_nonnote_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. */
|| ! rtx_equal_p (x, SET_DEST (set_b))
|| reg_overlap_mentioned_p (x, SET_SRC (set_b))
|| modified_between_p (SET_SRC (set_b),
- PREV_INSN (if_info.cond_earliest), jump)
+ PREV_INSN (if_info->cond_earliest), jump)
/* Likewise with X. In particular this can happen when
noce_get_condition looks farther back in the instruction
stream than one might expect. */
|| reg_overlap_mentioned_p (x, cond)
|| reg_overlap_mentioned_p (x, a)
- || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump))
+ || modified_between_p (x, PREV_INSN (if_info->cond_earliest), jump))
insn_b = set_b = NULL_RTX;
}
|| (SMALL_REGISTER_CLASSES
&& REGNO (x) < FIRST_PSEUDO_REGISTER))
{
- if (no_new_pseudos || GET_MODE (x) == BLKmode)
+ if (GET_MODE (x) == BLKmode)
return FALSE;
- if (GET_MODE (x) == ZERO_EXTRACT
- && (GET_CODE (XEXP (x, 1)) != CONST_INT
+ if (GET_MODE (x) == ZERO_EXTRACT
+ && (GET_CODE (XEXP (x, 1)) != CONST_INT
|| GET_CODE (XEXP (x, 2)) != CONST_INT))
return FALSE;
-
+
x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
? XEXP (x, 0) : x));
}
return FALSE;
/* Set up the info block for our subroutines. */
- if_info.insn_a = insn_a;
- if_info.insn_b = insn_b;
- if_info.x = x;
- if_info.a = a;
- if_info.b = b;
- if_info.b_unconditional = else_bb == 0;
+ if_info->insn_a = insn_a;
+ if_info->insn_b = insn_b;
+ if_info->x = x;
+ if_info->a = a;
+ if_info->b = b;
/* Try optimizations in some approximation of a useful order. */
/* ??? Should first look to see if X is live incoming at all. If it
if (!set_b && MEM_P (orig_x) && noce_mem_write_may_trap_or_fault_p (orig_x))
return FALSE;
- if (noce_try_move (&if_info))
+ if (noce_try_move (if_info))
goto success;
- if (noce_try_store_flag (&if_info))
+ if (noce_try_store_flag (if_info))
goto success;
- if (noce_try_bitop (&if_info))
+ if (noce_try_bitop (if_info))
goto success;
- if (noce_try_minmax (&if_info))
+ if (noce_try_minmax (if_info))
goto success;
- if (noce_try_abs (&if_info))
+ if (noce_try_abs (if_info))
goto success;
if (HAVE_conditional_move
- && noce_try_cmove (&if_info))
+ && noce_try_cmove (if_info))
goto success;
if (! HAVE_conditional_execution)
{
- if (noce_try_store_flag_constants (&if_info))
+ if (noce_try_store_flag_constants (if_info))
goto success;
- if (noce_try_addcc (&if_info))
+ if (noce_try_addcc (if_info))
goto success;
- if (noce_try_store_flag_mask (&if_info))
+ if (noce_try_store_flag_mask (if_info))
goto success;
if (HAVE_conditional_move
- && noce_try_cmove_arith (&if_info))
+ && noce_try_cmove_arith (if_info))
goto success;
- if (noce_try_sign_mask (&if_info))
+ if (noce_try_sign_mask (if_info))
goto success;
}
return FALSE;
success:
- /* The original sets may now be killed. */
- delete_insn (insn_a);
-
- /* Several special cases here: First, we may have reused insn_b above,
- in which case insn_b is now NULL. Second, we want to delete insn_b
- if it came from the ELSE block, because follows the now correct
- write that appears in the TEST block. However, if we got insn_b from
- the TEST block, it may in fact be loading data needed for the comparison.
- We'll let life_analysis remove the insn if it's really dead. */
- if (insn_b && else_bb)
- delete_insn (insn_b);
-
- /* The new insns will have been inserted immediately before the jump. We
- should be able to remove the jump with impunity, but the condition itself
- may have been modified by gcse to be shared across basic blocks. */
- delete_insn (jump);
/* If we used a temporary, fix it up now. */
if (orig_x != x)
{
+ rtx seq;
+
start_sequence ();
noce_emit_move_insn (orig_x, x);
- insn_b = get_insns ();
+ seq = get_insns ();
set_used_flags (orig_x);
- unshare_all_rtl_in_chain (insn_b);
+ unshare_all_rtl_in_chain (seq);
end_sequence ();
- emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a));
+ emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a));
}
- /* Merge the blocks! */
- merge_if_block (ce_info);
+ /* The original THEN and ELSE blocks may now be removed. The test block
+ must now jump to the join block. If the test block and the join block
+ can be merged, do so. */
+ if (else_bb)
+ {
+ delete_basic_block (else_bb);
+ num_true_changes++;
+ }
+ else
+ remove_edge (find_edge (test_bb, join_bb));
+
+ remove_edge (find_edge (then_bb, join_bb));
+ redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
+ delete_basic_block (then_bb);
+ num_true_changes++;
+
+ if (can_merge_blocks_p (test_bb, join_bb))
+ {
+ merge_blocks (test_bb, join_bb);
+ num_true_changes++;
+ }
+ num_updated_if_blocks++;
return TRUE;
}
/* Check whether a block is suitable for conditional move conversion.
Every insn must be a simple set of a register to a constant or a
register. For each assignment, store the value in the array VALS,
- indexed by register number. COND is the condition we will
- test. */
+ indexed by register number, then store the register number in
+ REGS. COND is the condition we will test. */
static int
-check_cond_move_block (basic_block bb, rtx *vals, rtx cond)
+check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) *regs, rtx cond)
{
rtx insn;
+ /* We can only handle simple jumps at the end of the basic block.
+ It is almost impossible to update the CFG otherwise. */
+ insn = BB_END (bb);
+ if (JUMP_P (insn) && !onlyjump_p (insn))
+ return FALSE;
+
FOR_BB_INSNS (bb, insn)
{
rtx set, dest, src;
src = SET_SRC (set);
if (!REG_P (dest)
|| (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
- return false;
+ return FALSE;
if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
return FALSE;
if (may_trap_p (src) || may_trap_p (dest))
return FALSE;
+ /* Don't try to handle this if the source register was
+ modified earlier in the block. */
+ if ((REG_P (src)
+ && vals[REGNO (src)] != NULL)
+ || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
+ && vals[REGNO (SUBREG_REG (src))] != NULL))
+ return FALSE;
+
/* Don't try to handle this if the destination register was
modified earlier in the block. */
if (vals[REGNO (dest)] != NULL)
if (reg_overlap_mentioned_p (dest, cond))
return FALSE;
- vals[REGNO (dest)] = src;
-
/* Don't try to handle this if the source register is modified
later in the block. */
if (!CONSTANT_P (src)
&& modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
return FALSE;
+
+ vals[REGNO (dest)] = src;
+
+ VEC_safe_push (int, heap, regs, REGNO (dest));
}
return TRUE;
}
-/* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
- using only conditional moves. Return TRUE if we were successful at
- converting the block. */
+/* Given a basic block BB suitable for conditional move conversion,
+ a condition COND, and arrays THEN_VALS and ELSE_VALS containing the
+ register values depending on COND, emit the insns in the block as
+ conditional moves. If ELSE_BLOCK is true, THEN_BB was already
+ processed. The caller has started a sequence for the conversion.
+ Return true if successful, false if something goes wrong. */
-static int
-cond_move_process_if_block (struct ce_if_block *ce_info)
+static bool
+cond_move_convert_if_block (struct noce_if_info *if_infop,
+ basic_block bb, rtx cond,
+ rtx *then_vals, rtx *else_vals,
+ bool else_block_p)
{
- basic_block then_bb = ce_info->then_bb;
- basic_block else_bb = ce_info->else_bb;
- struct noce_if_info if_info;
- rtx jump, cond, insn, seq, cond_arg0, cond_arg1, loc_insn;
- int max_reg, size, c, i;
- rtx *then_vals;
- rtx *else_vals;
enum rtx_code code;
+ rtx insn, cond_arg0, cond_arg1;
- if (!HAVE_conditional_move || no_new_pseudos)
- return FALSE;
+ code = GET_CODE (cond);
+ cond_arg0 = XEXP (cond, 0);
+ cond_arg1 = XEXP (cond, 1);
- memset (&if_info, 0, sizeof if_info);
+ FOR_BB_INSNS (bb, insn)
+ {
+ rtx set, target, dest, t, e;
+ unsigned int regno;
- if (!noce_init_if_info (ce_info, &if_info))
- return FALSE;
+ if (!INSN_P (insn) || JUMP_P (insn))
+ continue;
+ set = single_set (insn);
+ gcc_assert (set && REG_P (SET_DEST (set)));
+
+ dest = SET_DEST (set);
+ regno = REGNO (dest);
- cond = if_info.cond;
- jump = if_info.jump;
+ t = then_vals[regno];
+ e = else_vals[regno];
+
+ if (else_block_p)
+ {
+ /* If this register was set in the then block, we already
+ handled this case there. */
+ if (t)
+ continue;
+ t = dest;
+ gcc_assert (e);
+ }
+ else
+ {
+ gcc_assert (t);
+ if (!e)
+ e = dest;
+ }
+
+ target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
+ t, e);
+ if (!target)
+ return false;
+
+ if (target != dest)
+ noce_emit_move_insn (dest, target);
+ }
+
+ return true;
+}
+
+/* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
+ it using only conditional moves. Return TRUE if we were successful at
+ converting the block. */
+
+static int
+cond_move_process_if_block (struct noce_if_info *if_info)
+{
+ basic_block test_bb = if_info->test_bb;
+ basic_block then_bb = if_info->then_bb;
+ basic_block else_bb = if_info->else_bb;
+ basic_block join_bb = if_info->join_bb;
+ rtx jump = if_info->jump;
+ rtx cond = if_info->cond;
+ rtx seq, loc_insn;
+ int max_reg, size, c, reg;
+ rtx *then_vals;
+ rtx *else_vals;
+ VEC (int, heap) *then_regs = NULL;
+ VEC (int, heap) *else_regs = NULL;
+ unsigned int i;
/* Build a mapping for each block to the value used for each
register. */
memset (else_vals, 0, size);
/* Make sure the blocks are suitable. */
- if (!check_cond_move_block (then_bb, then_vals, cond)
- || (else_bb && !check_cond_move_block (else_bb, else_vals, cond)))
+ 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)))
return FALSE;
/* Make sure the blocks can be used together. If the same register
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; i <= max_reg; ++i)
+ for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
{
- if (!then_vals[i] && !else_vals[i])
+ if (!then_vals[reg] && !else_vals[reg])
continue;
- if (!then_vals[i] || !else_vals[i])
+ if (!else_vals[reg])
++c;
else
{
- if (!CONSTANT_P (then_vals[i])
- && !CONSTANT_P (else_vals[i])
- && !rtx_equal_p (then_vals[i], else_vals[i]))
+ if (!CONSTANT_P (then_vals[reg])
+ && !CONSTANT_P (else_vals[reg])
+ && !rtx_equal_p (then_vals[reg], else_vals[reg]))
return FALSE;
}
}
+ /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
+ for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
+ if (!then_vals[reg])
+ ++c;
+
/* Make sure it is reasonable to convert this block. What matters
is the number of assignments currently made in only one of the
branches, since if we convert we are going to always execute
if (c > MAX_CONDITIONAL_EXECUTE)
return FALSE;
- /* Emit the conditional moves. First do the then block, then do
- anything left in the else blocks. */
-
- code = GET_CODE (cond);
- cond_arg0 = XEXP (cond, 0);
- cond_arg1 = XEXP (cond, 1);
-
+ /* Try to emit the conditional moves. First do the then block,
+ then do anything left in the else blocks. */
start_sequence ();
-
- FOR_BB_INSNS (then_bb, insn)
- {
- rtx set, target, dest, t, e;
- unsigned int regno;
-
- if (!INSN_P (insn) || JUMP_P (insn))
- continue;
- set = single_set (insn);
- gcc_assert (set && REG_P (SET_DEST (set)));
-
- dest = SET_DEST (set);
- regno = REGNO (dest);
- t = then_vals[regno];
- e = else_vals[regno];
- gcc_assert (t);
- if (!e)
- e = dest;
- target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1,
- t, e);
- if (!target)
- {
- end_sequence ();
- return FALSE;
- }
-
- if (target != dest)
- noce_emit_move_insn (dest, target);
- }
-
- if (else_bb)
+ if (!cond_move_convert_if_block (if_info, then_bb, cond,
+ then_vals, else_vals, false)
+ || (else_bb
+ && !cond_move_convert_if_block (if_info, else_bb, cond,
+ then_vals, else_vals, true)))
{
- FOR_BB_INSNS (else_bb, insn)
- {
- rtx set, target, dest;
- unsigned int regno;
-
- if (!INSN_P (insn) || JUMP_P (insn))
- continue;
- set = single_set (insn);
- gcc_assert (set && REG_P (SET_DEST (set)));
-
- dest = SET_DEST (set);
- regno = REGNO (dest);
-
- /* If this register was set in the then block, we already
- handled this case above. */
- if (then_vals[regno])
- continue;
- gcc_assert (else_vals[regno]);
-
- target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1,
- dest, else_vals[regno]);
- if (!target)
- {
- end_sequence ();
- return FALSE;
- }
-
- if (target != dest)
- noce_emit_move_insn (dest, target);
- }
+ end_sequence ();
+ return FALSE;
}
-
- seq = end_ifcvt_sequence (&if_info);
+ seq = end_ifcvt_sequence (if_info);
if (!seq)
return FALSE;
}
emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
- FOR_BB_INSNS (then_bb, insn)
- if (INSN_P (insn) && !JUMP_P (insn))
- delete_insn (insn);
if (else_bb)
{
- FOR_BB_INSNS (else_bb, insn)
- if (INSN_P (insn) && !JUMP_P (insn))
- delete_insn (insn);
+ delete_basic_block (else_bb);
+ num_true_changes++;
}
- delete_insn (jump);
+ else
+ remove_edge (find_edge (test_bb, join_bb));
- merge_if_block (ce_info);
+ remove_edge (find_edge (then_bb, join_bb));
+ redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
+ delete_basic_block (then_bb);
+ num_true_changes++;
+
+ if (can_merge_blocks_p (test_bb, join_bb))
+ {
+ merge_blocks (test_bb, join_bb);
+ num_true_changes++;
+ }
+
+ num_updated_if_blocks++;
+
+ VEC_free (int, heap, then_regs);
+ VEC_free (int, heap, else_regs);
return TRUE;
}
+
\f
-/* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
- straight line code. Return true if successful. */
+/* Determine if a given basic block heads a simple IF-THEN-JOIN or an
+ IF-THEN-ELSE-JOIN block.
+
+ If so, we'll try to convert the insns to not require the branch,
+ using only transformations that do not require conditional execution.
+
+ Return TRUE if we were successful at converting the block. */
static int
-process_if_block (struct ce_if_block * ce_info)
+noce_find_if_block (basic_block test_bb,
+ edge then_edge, edge else_edge,
+ int pass)
{
- if (! reload_completed
- && noce_process_if_block (ce_info))
- return TRUE;
+ basic_block then_bb, else_bb, join_bb;
+ bool then_else_reversed = false;
+ rtx jump, cond;
+ struct noce_if_info if_info;
- if (HAVE_conditional_move
- && cond_move_process_if_block (ce_info))
- return TRUE;
+ /* We only ever should get here before reload. */
+ gcc_assert (!reload_completed);
- if (HAVE_conditional_execution && reload_completed)
+ /* Recognize an IF-THEN-ELSE-JOIN block. */
+ if (single_pred_p (then_edge->dest)
+ && single_succ_p (then_edge->dest)
+ && single_pred_p (else_edge->dest)
+ && single_succ_p (else_edge->dest)
+ && single_succ (then_edge->dest) == single_succ (else_edge->dest))
{
- /* If we have && and || tests, try to first handle combining the && and
- || tests into the conditional code, and if that fails, go back and
- handle it without the && and ||, which at present handles the && case
- if there was no ELSE block. */
- if (cond_exec_process_if_block (ce_info, TRUE))
- return TRUE;
+ then_bb = then_edge->dest;
+ else_bb = else_edge->dest;
+ join_bb = single_succ (then_bb);
+ }
+ /* Recognize an IF-THEN-JOIN block. */
+ else if (single_pred_p (then_edge->dest)
+ && single_succ_p (then_edge->dest)
+ && single_succ (then_edge->dest) == else_edge->dest)
+ {
+ then_bb = then_edge->dest;
+ else_bb = NULL_BLOCK;
+ join_bb = else_edge->dest;
+ }
+ /* Recognize an IF-ELSE-JOIN block. We can have those because the order
+ of basic blocks in cfglayout mode does not matter, so the fallthrough
+ edge can go to any basic block (and not just to bb->next_bb, like in
+ cfgrtl mode). */
+ else if (single_pred_p (else_edge->dest)
+ && single_succ_p (else_edge->dest)
+ && single_succ (else_edge->dest) == then_edge->dest)
+ {
+ /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
+ To make this work, we have to invert the THEN and ELSE blocks
+ and reverse the jump condition. */
+ then_bb = else_edge->dest;
+ else_bb = NULL_BLOCK;
+ join_bb = single_succ (then_bb);
+ then_else_reversed = true;
+ }
+ else
+ /* Not a form we can handle. */
+ return FALSE;
+
+ /* The edges of the THEN and ELSE blocks cannot have complex edges. */
+ if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
+ return FALSE;
+ if (else_bb
+ && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
+ return FALSE;
- if (ce_info->num_multiple_test_blocks)
- {
- cancel_changes (0);
+ num_possible_if_blocks++;
- if (cond_exec_process_if_block (ce_info, FALSE))
- return TRUE;
- }
+ if (dump_file)
+ {
+ fprintf (dump_file,
+ "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
+ (else_bb) ? "-ELSE" : "",
+ pass, test_bb->index, then_bb->index);
+
+ if (else_bb)
+ fprintf (dump_file, ", else %d", else_bb->index);
+
+ fprintf (dump_file, ", join %d\n", join_bb->index);
}
+ /* If the conditional jump is more than just a conditional
+ jump, then we can not do if-conversion on this block. */
+ jump = BB_END (test_bb);
+ if (! onlyjump_p (jump))
+ return FALSE;
+
+ /* If this is not a standard conditional jump, we can't parse it. */
+ cond = noce_get_condition (jump,
+ &if_info.cond_earliest,
+ then_else_reversed);
+ if (!cond)
+ return FALSE;
+
+ /* We must be comparing objects whose modes imply the size. */
+ if (GET_MODE (XEXP (cond, 0)) == BLKmode)
+ return FALSE;
+
+ /* Initialize an IF_INFO struct to pass around. */
+ memset (&if_info, 0, sizeof if_info);
+ if_info.test_bb = test_bb;
+ if_info.then_bb = then_bb;
+ if_info.else_bb = else_bb;
+ if_info.join_bb = join_bb;
+ if_info.cond = cond;
+ if_info.jump = jump;
+
+ /* Do the real work. */
+
+ if (noce_process_if_block (&if_info))
+ return TRUE;
+
+ if (HAVE_conditional_move
+ && cond_move_process_if_block (&if_info))
+ return TRUE;
+
return FALSE;
}
+\f
/* Merge the blocks and mark for local life update. */
if (then_bb)
{
- if (combo_bb->il.rtl->global_live_at_end)
- COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
- then_bb->il.rtl->global_live_at_end);
merge_blocks (combo_bb, then_bb);
num_true_changes++;
}
&& join_bb != EXIT_BLOCK_PTR)
{
/* We can merge the JOIN. */
- if (combo_bb->il.rtl->global_live_at_end)
- COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
- join_bb->il.rtl->global_live_at_end);
-
merge_blocks (combo_bb, join_bb);
num_true_changes++;
}
IFCVT_INIT_EXTRA_FIELDS (&ce_info);
#endif
- if (find_if_block (&ce_info))
+ if (! reload_completed
+ && noce_find_if_block (test_bb, then_edge, else_edge, pass))
+ goto success;
+
+ if (HAVE_conditional_execution && reload_completed
+ && cond_exec_find_if_block (&ce_info))
goto success;
if (HAVE_trap && HAVE_conditional_trap
Return TRUE if we were successful at converting the block. */
static int
-find_if_block (struct ce_if_block * ce_info)
+cond_exec_find_if_block (struct ce_if_block * ce_info)
{
basic_block test_bb = ce_info->test_bb;
basic_block then_bb = ce_info->then_bb;
ce_info->last_test_bb = test_bb;
+ /* We only ever should get here after reload,
+ and only if we have conditional execution. */
+ gcc_assert (HAVE_conditional_execution && reload_completed);
+
/* 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
the then block). */
- if (HAVE_conditional_execution && reload_completed
- && single_pred_p (test_bb)
+ if (single_pred_p (test_bb)
&& single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
{
basic_block bb = single_pred (test_bb);
other than any || blocks which jump to the THEN block. */
if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
return FALSE;
-
+
/* The edges of the THEN and ELSE blocks cannot have complex edges. */
FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
{
}
/* Do the real work. */
+
ce_info->else_bb = else_bb;
ce_info->join_bb = join_bb;
- return process_if_block (ce_info);
+ /* If we have && and || tests, try to first handle combining the && and ||
+ tests into the conditional code, and if that fails, go back and handle
+ it without the && and ||, which at present handles the && case if there
+ was no ELSE block. */
+ if (cond_exec_process_if_block (ce_info, TRUE))
+ return TRUE;
+
+ if (ce_info->num_multiple_test_blocks)
+ {
+ cancel_changes (0);
+
+ if (cond_exec_process_if_block (ce_info, FALSE))
+ return TRUE;
+ }
}
/* Convert a branch over a trap, or a branch
/* If this is not a standard conditional jump, we can't parse it. */
jump = BB_END (test_bb);
- cond = noce_get_condition (jump, &cond_earliest);
+ cond = noce_get_condition (jump, &cond_earliest, false);
if (! cond)
return FALSE;
if (seq == NULL)
return FALSE;
- num_true_changes++;
-
/* Emit the new insns before cond_earliest. */
emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
/* Delete the trap block if possible. */
remove_edge (trap_bb == then_bb ? then_edge : else_edge);
if (EDGE_COUNT (trap_bb->preds) == 0)
- delete_basic_block (trap_bb);
-
- /* If the non-trap block and the test are now adjacent, merge them.
- Otherwise we must insert a direct branch. */
- if (test_bb->next_bb == other_bb)
{
- struct ce_if_block new_ce_info;
- delete_insn (jump);
- memset (&new_ce_info, '\0', sizeof (new_ce_info));
- new_ce_info.test_bb = test_bb;
- new_ce_info.then_bb = NULL;
- new_ce_info.else_bb = NULL;
- new_ce_info.join_bb = other_bb;
- merge_if_block (&new_ce_info);
+ delete_basic_block (trap_bb);
+ num_true_changes++;
}
+
+ /* Wire together the blocks again. */
+ if (current_ir_type () == IR_RTL_CFGLAYOUT)
+ single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
else
{
rtx lab, newjump;
LABEL_NUSES (lab) += 1;
JUMP_LABEL (newjump) = lab;
emit_barrier_after (newjump);
+ }
+ delete_insn (jump);
- delete_insn (jump);
+ if (can_merge_blocks_p (test_bb, other_bb))
+ {
+ merge_blocks (test_bb, other_bb);
+ num_true_changes++;
}
+ num_updated_if_blocks++;
return TRUE;
}
/* If we are partitioning hot/cold basic blocks, we don't want to
mess up unconditional or indirect jumps that cross between hot
and cold sections.
-
+
Basic block partitioning may result in some jumps that appear to
- be optimizable (or blocks that appear to be mergeable), but which really
- must be left untouched (they are required to make it safely across
- partition boundaries). See the comments at the top of
+ be optimizable (or blocks that appear to be mergeable), but which really
+ must be left untouched (they are required to make it safely across
+ partition boundaries). See the comments at the top of
bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
- if ((BB_END (then_bb)
+ if ((BB_END (then_bb)
&& find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
|| (BB_END (test_bb)
&& find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
|| (BB_END (else_bb)
- && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
+ && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
NULL_RTX)))
return FALSE;
/* If we are partitioning hot/cold basic blocks, we don't want to
mess up unconditional or indirect jumps that cross between hot
and cold sections.
-
+
Basic block partitioning may result in some jumps that appear to
- be optimizable (or blocks that appear to be mergeable), but which really
- must be left untouched (they are required to make it safely across
- partition boundaries). See the comments at the top of
+ be optimizable (or blocks that appear to be mergeable), but which really
+ must be left untouched (they are required to make it safely across
+ partition boundaries). See the comments at the top of
bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
if ((BB_END (then_bb)
&& find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
|| (BB_END (test_bb)
&& find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
- || (BB_END (else_bb)
- && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
+ || (BB_END (else_bb)
+ && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
NULL_RTX)))
return FALSE;
head = BB_HEAD (merge_bb);
end = BB_END (merge_bb);
+ /* If merge_bb ends with a tablejump, predicating/moving insn's
+ into test_bb and then deleting merge_bb will result in the jumptable
+ that follows merge_bb being removed along with merge_bb and then we
+ get an unresolved reference to the jumptable. */
+ if (tablejump_p (end, NULL, NULL))
+ return FALSE;
+
if (LABEL_P (head))
head = NEXT_INSN (head);
if (NOTE_P (head))
return FALSE;
/* Find the extent of the conditional. */
- cond = noce_get_condition (jump, &earliest);
+ cond = noce_get_condition (jump, &earliest, false);
if (! cond)
return FALSE;
if (other_bb != new_dest)
{
- redirect_jump_2 (jump, old_dest, new_label, -1, reversep);
+ redirect_jump_2 (jump, old_dest, new_label, 0, reversep);
redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
if (reversep)
num_true_changes = 0;
life_data_ok = (x_life_data_ok != 0);
- if ((! targetm.cannot_modify_jumps_p ())
- && (!flag_reorder_blocks_and_partition || !no_new_pseudos
- || !targetm.have_named_sections))
- {
- struct loops loops;
+ /* Some transformations in this pass can create new pseudos,
+ if the pass runs before reload. Make sure we can do so. */
+ gcc_assert (! no_new_pseudos || reload_completed);
- flow_loops_find (&loops);
- mark_loop_exit_edges (&loops);
- flow_loops_free (&loops);
- free_dominance_info (CDI_DOMINATORS);
+ loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+ if (current_loops)
+ {
+ mark_loop_exit_edges ();
+ loop_optimizer_finalize ();
}
+ free_dominance_info (CDI_DOMINATORS);
/* Compute postdominators if we think we'll use them. */
if (HAVE_conditional_execution || life_data_ok)
TODO_ggc_collect, /* todo_flags_finish */
'E' /* letter */
};
-
-
OSDN Git Service
