/* If-conversion support.
- Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
+ Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
- Software Foundation, 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA. */
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "tm_p.h"
#include "cfgloop.h"
#include "target.h"
+#include "timevar.h"
+#include "tree-pass.h"
+#include "vec.h"
+#include "vecprim.h"
#ifndef HAVE_conditional_execution
/* If this instruction is the load or set of a "stack" register,
such as a floating point register on x87, then the cost of
- speculatively executing this instruction needs to include
- the additional cost of popping this register off of the
- register stack. */
+ speculatively executing this insn may need to include
+ the additional cost of popping its result off of the
+ register stack. Unfortunately, correctly recognizing and
+ accounting for this additional overhead is tricky, so for
+ now we simply prohibit such speculative execution. */
#ifdef STACK_REGS
{
rtx set = single_set (insn);
if (set && STACK_REG_P (SET_DEST (set)))
- cost += COSTS_N_INSNS (1);
+ return false;
}
#endif
}
else if (CALL_P (insn))
return false;
-
+
if (insn == BB_END (bb))
break;
insn = NEXT_INSN (insn);
struct noce_if_info
{
+ /* A basic block that ends in a simple conditional jump. */
basic_block test_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);
optab ot;
start_sequence ();
- insn = emit_move_insn (x, y);
+ /* Check that the SET_SRC is reasonable before calling emit_move_insn,
+ otherwise construct a suitable SET pattern ourselves. */
+ insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
+ ? 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)
- switch (GET_RTX_CLASS (GET_CODE (y)))
- {
- case RTX_UNARY:
- ot = code_to_optab[GET_CODE (y)];
- if (ot)
- {
- start_sequence ();
- target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
- if (target != NULL_RTX)
- {
- if (target != x)
- emit_move_insn (x, target);
- seq = get_insns ();
- }
- end_sequence ();
- }
- break;
+ {
+ if (GET_CODE (x) == ZERO_EXTRACT)
+ {
+ rtx op = XEXP (x, 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
+ invoke store_bit_field again it is necessary to have the START
+ value from the first call. */
+ if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
+ {
+ if (MEM_P (op))
+ start = BITS_PER_UNIT - start - size;
+ else
+ {
+ gcc_assert (REG_P (op));
+ start = BITS_PER_WORD - start - size;
+ }
+ }
- case RTX_BIN_ARITH:
- case RTX_COMM_ARITH:
- ot = code_to_optab[GET_CODE (y)];
- if (ot)
- {
- start_sequence ();
- target = expand_binop (GET_MODE (y), ot,
- XEXP (y, 0), XEXP (y, 1),
- x, 0, OPTAB_DIRECT);
- if (target != NULL_RTX)
- {
- if (target != x)
- emit_move_insn (x, target);
- seq = get_insns ();
- }
- end_sequence ();
- }
- break;
+ gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
+ store_bit_field (op, size, start, GET_MODE (x), y);
+ return;
+ }
- default:
- break;
- }
+ switch (GET_RTX_CLASS (GET_CODE (y)))
+ {
+ case RTX_UNARY:
+ ot = code_to_optab[GET_CODE (y)];
+ if (ot)
+ {
+ start_sequence ();
+ target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
+ if (target != NULL_RTX)
+ {
+ if (target != x)
+ emit_move_insn (x, target);
+ seq = get_insns ();
+ }
+ end_sequence ();
+ }
+ break;
+
+ case RTX_BIN_ARITH:
+ case RTX_COMM_ARITH:
+ ot = code_to_optab[GET_CODE (y)];
+ if (ot)
+ {
+ start_sequence ();
+ target = expand_binop (GET_MODE (y), ot,
+ XEXP (y, 0), XEXP (y, 1),
+ x, 0, OPTAB_DIRECT);
+ if (target != NULL_RTX)
+ {
+ if (target != x)
+ emit_move_insn (x, target);
+ seq = get_insns ();
+ }
+ end_sequence ();
+ }
+ break;
+
+ default:
+ break;
+ }
+ }
emit_insn (seq);
return;
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 prev_insn;
/* First, look to see if we put a constant in a register. */
- prev_insn = PREV_INSN (if_info->cond_earliest);
+ prev_insn = prev_nonnote_insn (if_info->cond_earliest);
if (prev_insn
&& INSN_P (prev_insn)
&& GET_CODE (PATTERN (prev_insn)) == SET)
if (no_new_pseudos)
return FALSE;
- /* Recognize A and B as constituting an ABS or NABS. */
+ /* 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. */
a = if_info->a;
b = if_info->b;
if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
if (rtx_equal_p (XEXP (cond, 0), b))
c = XEXP (cond, 1);
else if (rtx_equal_p (XEXP (cond, 1), b))
- c = XEXP (cond, 0);
+ {
+ c = XEXP (cond, 0);
+ negate = !negate;
+ }
else
return FALSE;
- /* Verify that C is zero. Search backward through the block for
- a REG_EQUAL note if necessary. */
+ /* Verify that C is zero. Search one step backward for a
+ REG_EQUAL note or a simple source if necessary. */
if (REG_P (c))
{
- rtx insn, note = NULL;
- for (insn = earliest;
- insn != BB_HEAD (if_info->test_bb);
- insn = PREV_INSN (insn))
- if (INSN_P (insn)
- && ((note = find_reg_note (insn, REG_EQUAL, c))
- || (note = find_reg_note (insn, REG_EQUIV, c))))
- break;
- if (! note)
+ rtx set, insn = prev_nonnote_insn (earliest);
+ if (insn
+ && (set = single_set (insn))
+ && rtx_equal_p (SET_DEST (set), c))
+ {
+ rtx note = find_reg_equal_equiv_note (insn);
+ if (note)
+ c = XEXP (note, 0);
+ else
+ c = SET_SRC (set);
+ }
+ else
return FALSE;
- c = XEXP (note, 0);
}
if (MEM_P (c)
&& GET_CODE (XEXP (c, 0)) == SYMBOL_REF
rtx cond, t, m, c, seq;
enum machine_mode mode;
enum rtx_code code;
+ bool b_unconditional;
if (no_new_pseudos)
return FALSE;
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
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 ! may_trap_p (op);
}
+/* Return true if a write into MEM may trap or fault. */
+
+static bool
+noce_mem_write_may_trap_or_fault_p (rtx mem)
+{
+ rtx addr;
+
+ if (MEM_READONLY_P (mem))
+ return true;
+
+ if (may_trap_or_fault_p (mem))
+ return true;
+
+ addr = XEXP (mem, 0);
+
+ /* Call target hook to avoid the effects of -fpic etc.... */
+ addr = targetm.delegitimize_address (addr);
+
+ while (addr)
+ switch (GET_CODE (addr))
+ {
+ case CONST:
+ case PRE_DEC:
+ case PRE_INC:
+ case POST_DEC:
+ case POST_INC:
+ case POST_MODIFY:
+ addr = XEXP (addr, 0);
+ break;
+ case LO_SUM:
+ case PRE_MODIFY:
+ addr = XEXP (addr, 1);
+ break;
+ case PLUS:
+ if (GET_CODE (XEXP (addr, 1)) == CONST_INT)
+ addr = XEXP (addr, 0);
+ else
+ return false;
+ break;
+ case LABEL_REF:
+ return true;
+ case SYMBOL_REF:
+ if (SYMBOL_REF_DECL (addr)
+ && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
+ return true;
+ return false;
+ default:
+ return false;
+ }
+
+ 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. */
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 */
+ basic_block join_bb;
struct noce_if_info if_info;
rtx insn_a, insn_b;
rtx set_a, set_b;
??? For future expansion, look for multiple X in such patterns. */
- /* 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 (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)
+ if (!noce_init_if_info (ce_info, &if_info))
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;
+ cond = if_info.cond;
+ jump = if_info.jump;
/* Look for one of the potential sets. */
insn_a = first_active_insn (then_bb);
if (side_effects_p (x))
return FALSE;
- /* If x is a read-only memory, then the program is valid only if we
- avoid the store into it. If there are stores on both the THEN and
- ELSE arms, then we can go ahead with the conversion; either the
- program is broken, or the condition is always false such that the
- other memory is selected. */
- if (!set_b && MEM_P (x) && MEM_READONLY_P (x))
- return FALSE;
-
b = (set_b ? SET_SRC (set_b) : x);
/* Only operate on register destinations, and even then avoid extending
{
if (no_new_pseudos || GET_MODE (x) == BLKmode)
return FALSE;
+
+ 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.test_bb = test_bb;
- if_info.cond = cond;
- if_info.jump = jump;
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;
/* Try optimizations in some approximation of a useful order. */
/* ??? Should first look to see if X is live incoming at all. If it
}
/* Disallow the "if (...) x = a;" form (with an implicit "else x = x;")
- for most optimizations if writing to x may trap, i.e. it's a memory
- other than a static var or a stack slot. */
- if (! set_b
- && MEM_P (orig_x)
- && ! MEM_NOTRAP_P (orig_x)
- && rtx_addr_can_trap_p (XEXP (orig_x, 0)))
- {
- if (HAVE_conditional_move)
- {
- if (noce_try_cmove (&if_info))
- goto success;
- if (! HAVE_conditional_execution
- && noce_try_cmove_arith (&if_info))
- goto success;
- }
- return FALSE;
- }
+ for optimizations if writing to x may trap or fault, i.e. it's a memory
+ other than a static var or a stack slot, is misaligned on strict
+ aligned machines or is read-only.
+ If x is a read-only memory, then the program is valid only if we
+ avoid the store into it. If there are stores on both the THEN and
+ ELSE arms, then we can go ahead with the conversion; either the
+ program is broken, or the condition is always false such that the
+ other memory is selected. */
+ 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))
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. */
+
+ join_bb = single_succ (then_bb);
+ 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, 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, 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;
+
+ if (!INSN_P (insn) || JUMP_P (insn))
+ continue;
+ set = single_set (insn);
+ if (!set)
+ return FALSE;
+
+ dest = SET_DEST (set);
+ src = SET_SRC (set);
+ if (!REG_P (dest)
+ || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
+ return FALSE;
+
+ if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
+ return FALSE;
+
+ if (side_effects_p (src) || side_effects_p (dest))
+ 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)
+ return FALSE;
+
+ /* Don't try to handle this if the condition uses the
+ destination register. */
+ if (reg_overlap_mentioned_p (dest, cond))
+ return FALSE;
+
+ /* 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 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 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)
+{
+ enum rtx_code code;
+ rtx insn, cond_arg0, cond_arg1;
+
+ code = GET_CODE (cond);
+ cond_arg0 = XEXP (cond, 0);
+ cond_arg1 = XEXP (cond, 1);
+
+ FOR_BB_INSNS (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];
+
+ 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 or IF-THEN-ELSE 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 ce_if_block *ce_info)
+{
+ basic_block test_bb = ce_info->test_bb;
+ basic_block then_bb = ce_info->then_bb;
+ basic_block else_bb = ce_info->else_bb;
+ basic_block join_bb;
+ struct noce_if_info if_info;
+ rtx jump, cond, 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;
+
+ if (!HAVE_conditional_move || no_new_pseudos)
+ return FALSE;
+
+ memset (&if_info, 0, sizeof if_info);
+
+ if (!noce_init_if_info (ce_info, &if_info))
+ return FALSE;
+
+ cond = if_info.cond;
+ jump = if_info.jump;
+
+ /* Build a mapping for each block to the value used for each
+ register. */
+ max_reg = max_reg_num ();
+ size = (max_reg + 1) * sizeof (rtx);
+ then_vals = (rtx *) alloca (size);
+ else_vals = (rtx *) alloca (size);
+ memset (then_vals, 0, size);
+ memset (else_vals, 0, size);
+
+ /* 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)))
+ return FALSE;
+
+ /* Make sure the blocks can be used together. If the same register
+ is set in both blocks, and is not set to a constant in both
+ cases, then both blocks must set it to the same register. We
+ have already verified that if it is set to a register, that the
+ 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++)
+ {
+ if (!then_vals[reg] && !else_vals[reg])
+ continue;
+
+ if (!else_vals[reg])
+ ++c;
+ else
+ {
+ 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
+ them. */
+ if (c > MAX_CONDITIONAL_EXECUTE)
+ return FALSE;
+
+ /* Try to emit the conditional moves. First do the then block,
+ then do anything left in the else blocks. */
+ start_sequence ();
+ 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)))
+ {
+ end_sequence ();
+ return FALSE;
+ }
+ seq = end_ifcvt_sequence (&if_info);
+ if (!seq)
+ return FALSE;
+
+ loc_insn = first_active_insn (then_bb);
+ if (!loc_insn)
+ {
+ loc_insn = first_active_insn (else_bb);
+ gcc_assert (loc_insn);
+ }
+ emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
+
+ join_bb = single_succ (then_bb);
+ 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++;
+
+ 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. */
static int
process_if_block (struct ce_if_block * ce_info)
{
- if (! reload_completed
- && noce_process_if_block (ce_info))
- return TRUE;
+ /* Only perform the noce transformations before register allocation.
+ They could be made to run later, but this would require a lot of
+ work, and it doesn't seem to be worth it. */
+ if (! reload_completed)
+ {
+ if (noce_process_if_block (ce_info))
+ return TRUE;
+
+ if (HAVE_conditional_move
+ && cond_move_process_if_block (ce_info))
+ return TRUE;
+ }
if (HAVE_conditional_execution && reload_completed)
{
if (then_bb)
{
- if (combo_bb->global_live_at_end)
- COPY_REG_SET (combo_bb->global_live_at_end,
- then_bb->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->global_live_at_end)
- COPY_REG_SET (combo_bb->global_live_at_end,
- join_bb->global_live_at_end);
-
merge_blocks (combo_bb, join_bb);
num_true_changes++;
}
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)
{
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;
/* Conversion went ok, including moving the insns and fixing up the
jump. Adjust the CFG to match. */
- bitmap_ior (test_bb->global_live_at_end,
- else_bb->global_live_at_start,
- then_bb->global_live_at_end);
+ bitmap_ior (test_bb->il.rtl->global_live_at_end,
+ else_bb->il.rtl->global_live_at_start,
+ then_bb->il.rtl->global_live_at_end);
/* We can avoid creating a new basic block if then_bb is immediately
if (new_bb)
{
new_bb->index = then_bb_index;
- BASIC_BLOCK (then_bb_index) = new_bb;
+ SET_BASIC_BLOCK (then_bb_index, new_bb);
/* Since the fallthru edge was redirected from test_bb to new_bb,
we need to ensure that new_bb is in the same partition as
test bb (you can not fall through across section boundaries). */
/* 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;
return FALSE;
/* THEN is not EXIT. */
- if (then_bb->index < 0)
+ if (then_bb->index < NUM_FIXED_BLOCKS)
return FALSE;
/* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
;
- else if (else_succ->dest->index < 0
+ else if (else_succ->dest->index < NUM_FIXED_BLOCKS
|| dominated_by_p (CDI_POST_DOMINATORS, then_bb,
else_succ->dest))
;
/* Conversion went ok, including moving the insns and fixing up the
jump. Adjust the CFG to match. */
- bitmap_ior (test_bb->global_live_at_end,
- then_bb->global_live_at_start,
- else_bb->global_live_at_end);
+ bitmap_ior (test_bb->il.rtl->global_live_at_end,
+ then_bb->il.rtl->global_live_at_start,
+ else_bb->il.rtl->global_live_at_end);
delete_basic_block (else_bb);
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))
/* ??? 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 (max_regno < max_reg_num ())
+ {
+ max_regno = max_reg_num ();
+ allocate_reg_info (max_regno, FALSE, FALSE);
+ }
propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
/* For small register class machines, don't lengthen lifetimes of
/* 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. */
- COPY_REG_SET (test_live, other_bb->global_live_at_start);
+ COPY_REG_SET (test_live, other_bb->il.rtl->global_live_at_start);
pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
0);
/* We can perform the transformation if
MERGE_SET & (TEST_SET | TEST_LIVE)
and
- TEST_SET & merge_bb->global_live_at_start
+ TEST_SET & merge_bb->il.rtl->global_live_at_start
are empty. */
if (bitmap_intersect_p (test_set, merge_set)
|| bitmap_intersect_p (test_live, merge_set)
- || bitmap_intersect_p (test_set, merge_bb->global_live_at_start))
+ || bitmap_intersect_p (test_set,
+ merge_bb->il.rtl->global_live_at_start))
fail = 1;
FREE_REG_SET (tmp);
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)
/* Move the insns out of MERGE_BB to before the branch. */
if (head != NULL)
{
+ rtx insn;
+
if (end == BB_END (merge_bb))
BB_END (merge_bb) = PREV_INSN (head);
if (squeeze_notes (&head, &end))
return TRUE;
+ /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
+ notes might become invalid. */
+ insn = head;
+ do
+ {
+ rtx note, set;
+
+ if (! INSN_P (insn))
+ continue;
+ note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+ if (! note)
+ continue;
+ set = single_set (insn);
+ if (!set || !function_invariant_p (SET_SRC (set)))
+ remove_note (insn, note);
+ } while (insn != end && (insn = NEXT_INSN (insn)));
+
reorder_insns (head, end, PREV_INSN (earliest));
}
\f
/* Main entry point for all if-conversion. */
-void
+static void
if_convert (int x_life_data_ok)
{
basic_block bb;
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))
+ loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
+ if (current_loops)
{
- struct loops loops;
-
- flow_loops_find (&loops);
- mark_loop_exit_edges (&loops);
- flow_loops_free (&loops);
- free_dominance_info (CDI_DOMINATORS);
+ 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)
verify_flow_info ();
#endif
}
+\f
+static bool
+gate_handle_if_conversion (void)
+{
+ return (optimize > 0);
+}
+
+/* If-conversion and CFG cleanup. */
+static unsigned int
+rest_of_handle_if_conversion (void)
+{
+ if (flag_if_conversion)
+ {
+ if (dump_file)
+ dump_flow_info (dump_file, dump_flags);
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+ reg_scan (get_insns (), max_reg_num ());
+ if_convert (0);
+ }
+
+ timevar_push (TV_JUMP);
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+ reg_scan (get_insns (), max_reg_num ());
+ timevar_pop (TV_JUMP);
+ return 0;
+}
+
+struct tree_opt_pass pass_rtl_ifcvt =
+{
+ "ce1", /* name */
+ gate_handle_if_conversion, /* gate */
+ rest_of_handle_if_conversion, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_IFCVT, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'C' /* letter */
+};
+
+static bool
+gate_handle_if_after_combine (void)
+{
+ return (optimize > 0 && flag_if_conversion);
+}
+
+
+/* Rerun if-conversion, as combine may have simplified things enough
+ to now meet sequence length restrictions. */
+static unsigned int
+rest_of_handle_if_after_combine (void)
+{
+ no_new_pseudos = 0;
+ if_convert (1);
+ no_new_pseudos = 1;
+ return 0;
+}
+
+struct tree_opt_pass pass_if_after_combine =
+{
+ "ce2", /* name */
+ gate_handle_if_after_combine, /* gate */
+ rest_of_handle_if_after_combine, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_IFCVT, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'C' /* letter */
+};
+
+
+static bool
+gate_handle_if_after_reload (void)
+{
+ return (optimize > 0);
+}
+
+static unsigned int
+rest_of_handle_if_after_reload (void)
+{
+ /* Last attempt to optimize CFG, as scheduling, peepholing and insn
+ splitting possibly introduced more crossjumping opportunities. */
+ cleanup_cfg (CLEANUP_EXPENSIVE
+ | CLEANUP_UPDATE_LIFE
+ | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
+ if (flag_if_conversion2)
+ if_convert (1);
+ return 0;
+}
+
+
+struct tree_opt_pass pass_if_after_reload =
+{
+ "ce3", /* name */
+ gate_handle_if_after_reload, /* gate */
+ rest_of_handle_if_after_reload, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_IFCVT2, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func |
+ TODO_ggc_collect, /* todo_flags_finish */
+ 'E' /* letter */
+};