/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005-2014 Free Software Foundation, Inc.
+ Copyright (C) 2005-2015 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "flags.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
#include "stor-layout.h"
#include "calls.h"
#include "predict.h"
-#include "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
#include "hard-reg-set.h"
-#include "input.h"
#include "function.h"
#include "dominance.h"
#include "cfg.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "gimple-walk.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
#include "tree-ssa-threadupdate.h"
+#include "rtl.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "insn-codes.h"
#include "optabs.h"
+#include "tree-ssa-scopedtables.h"
#include "tree-ssa-threadedge.h"
-#include "wide-int.h"
static int *vr_phi_edge_counts;
typedef struct {
- gimple stmt;
+ gswitch *stmt;
tree vec;
} switch_update;
if (arg == cfun->static_chain_decl)
return true;
+ /* THIS argument of method is always non-NULL. */
+ if (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
+ && arg == DECL_ARGUMENTS (current_function_decl)
+ && flag_delete_null_pointer_checks)
+ return true;
+
+ /* Values passed by reference are always non-NULL. */
+ if (TREE_CODE (TREE_TYPE (arg)) == REFERENCE_TYPE
+ && flag_delete_null_pointer_checks)
+ return true;
+
fntype = TREE_TYPE (current_function_decl);
for (attrs = TYPE_ATTRIBUTES (fntype); attrs; attrs = TREE_CHAIN (attrs))
{
value_range_t *old_vr;
bool is_new;
+ /* If there is a value-range on the SSA name from earlier analysis
+ factor that in. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (var)))
+ {
+ wide_int min, max;
+ value_range_type rtype = get_range_info (var, &min, &max);
+ if (rtype == VR_RANGE || rtype == VR_ANTI_RANGE)
+ {
+ value_range_d nr;
+ nr.type = rtype;
+ nr.min = wide_int_to_tree (TREE_TYPE (var), min);
+ nr.max = wide_int_to_tree (TREE_TYPE (var), max);
+ nr.equiv = NULL;
+ vrp_intersect_ranges (new_vr, &nr);
+ }
+ }
+
/* Update the value range, if necessary. */
old_vr = get_value_range (var);
is_new = old_vr->type != new_vr->type
if (is_new)
{
/* Do not allow transitions up the lattice. The following
- is slightly more awkward than just new_vr->type < old_vr->type
+ is slightly more awkward than just new_vr->type < old_vr->type
because VR_RANGE and VR_ANTI_RANGE need to be considered
the same. We may not have is_new when transitioning to
- UNDEFINED or from VARYING. */
- if (new_vr->type == VR_UNDEFINED
- || old_vr->type == VR_VARYING)
- set_value_range_to_varying (old_vr);
+ UNDEFINED. If old_vr->type is VARYING, we shouldn't be
+ called. */
+ if (new_vr->type == VR_UNDEFINED)
+ {
+ BITMAP_FREE (new_vr->equiv);
+ set_value_range_to_varying (old_vr);
+ set_value_range_to_varying (new_vr);
+ return true;
+ }
else
set_value_range (old_vr, new_vr->type, new_vr->min, new_vr->max,
new_vr->equiv);
&& DECL_IS_OPERATOR_NEW (fndecl)
&& !TREE_NOTHROW (fndecl))
return true;
+ /* References are always non-NULL. */
+ if (flag_delete_null_pointer_checks
+ && TREE_CODE (TREE_TYPE (fndecl)) == REFERENCE_TYPE)
+ return true;
if (flag_delete_null_pointer_checks &&
lookup_attribute ("returns_nonnull",
TYPE_ATTRIBUTES (gimple_call_fntype (stmt))))
&& code != MAX_EXPR
&& code != PLUS_EXPR
&& code != MINUS_EXPR
+ && code != RSHIFT_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
prod3. */
/* min0min1 > max0max1 */
if (wi::gts_p (prod0, prod3))
- {
- vrp_int tmp = prod3;
- prod3 = prod0;
- prod0 = tmp;
- }
+ std::swap (prod0, prod3);
/* min0max1 > max0min1 */
if (wi::gts_p (prod1, prod2))
- {
- vrp_int tmp = prod2;
- prod2 = prod1;
- prod1 = tmp;
- }
+ std::swap (prod1, prod2);
if (wi::gts_p (prod0, prod1))
- {
- vrp_int tmp = prod1;
- prod1 = prod0;
- prod0 = tmp;
- }
+ std::swap (prod0, prod1);
if (wi::gts_p (prod2, prod3))
- {
- vrp_int tmp = prod3;
- prod3 = prod2;
- prod2 = tmp;
- }
+ std::swap (prod2, prod3);
/* diff = max - min. */
prod2 = prod3 - prod0;
{
if (code == RSHIFT_EXPR)
{
+ /* Even if vr0 is VARYING or otherwise not usable, we can derive
+ useful ranges just from the shift count. E.g.
+ x >> 63 for signed 64-bit x is always [-1, 0]. */
+ if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
+ {
+ vr0.type = type = VR_RANGE;
+ vr0.min = vrp_val_min (expr_type);
+ vr0.max = vrp_val_max (expr_type);
+ }
extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
return;
}
and all numbers from min to 0 for negative min. */
cmp = compare_values (vr0.max, zero);
if (cmp == -1)
- max = zero;
+ {
+ /* When vr0.max < 0, vr1.min != 0 and value
+ ranges for dividend and divisor are available. */
+ if (vr1.type == VR_RANGE
+ && !symbolic_range_p (&vr0)
+ && !symbolic_range_p (&vr1)
+ && !compare_values (vr1.min, zero))
+ max = int_const_binop (code, vr0.max, vr1.min);
+ else
+ max = zero;
+ }
else if (cmp == 0 || cmp == 1)
max = vr0.max;
else
type = VR_VARYING;
cmp = compare_values (vr0.min, zero);
if (cmp == 1)
- min = zero;
+ {
+ /* For unsigned division when value ranges for dividend
+ and divisor are available. */
+ if (vr1.type == VR_RANGE
+ && !symbolic_range_p (&vr0)
+ && !symbolic_range_p (&vr1))
+ min = int_const_binop (code, vr0.min, vr1.max);
+ else
+ min = zero;
+ }
else if (cmp == 0 || cmp == -1)
min = vr0.min;
else
}
else if (code == TRUNC_MOD_EXPR)
{
- if (vr1.type != VR_RANGE
- || range_includes_zero_p (vr1.min, vr1.max) != 0
- || vrp_val_is_min (vr1.min))
+ if (range_is_null (&vr1))
{
- set_value_range_to_varying (vr);
+ set_value_range_to_undefined (vr);
return;
}
+ /* ABS (A % B) < ABS (B) and either
+ 0 <= A % B <= A or A <= A % B <= 0. */
type = VR_RANGE;
- /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */
- max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
- if (tree_int_cst_lt (max, vr1.max))
- max = vr1.max;
- max = int_const_binop (MINUS_EXPR, max, build_int_cst (TREE_TYPE (max), 1));
- /* If the dividend is non-negative the modulus will be
- non-negative as well. */
- if (TYPE_UNSIGNED (expr_type)
- || value_range_nonnegative_p (&vr0))
- min = build_int_cst (TREE_TYPE (max), 0);
+ signop sgn = TYPE_SIGN (expr_type);
+ unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int wmin, wmax, tmp;
+ wide_int zero = wi::zero (prec);
+ wide_int one = wi::one (prec);
+ if (vr1.type == VR_RANGE && !symbolic_range_p (&vr1))
+ {
+ wmax = wi::sub (vr1.max, one);
+ if (sgn == SIGNED)
+ {
+ tmp = wi::sub (wi::minus_one (prec), vr1.min);
+ wmax = wi::smax (wmax, tmp);
+ }
+ }
else
- min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
+ {
+ wmax = wi::max_value (prec, sgn);
+ /* X % INT_MIN may be INT_MAX. */
+ if (sgn == UNSIGNED)
+ wmax = wmax - one;
+ }
+
+ if (sgn == UNSIGNED)
+ wmin = zero;
+ else
+ {
+ wmin = -wmax;
+ if (vr0.type == VR_RANGE && TREE_CODE (vr0.min) == INTEGER_CST)
+ {
+ tmp = vr0.min;
+ if (wi::gts_p (tmp, zero))
+ tmp = zero;
+ wmin = wi::smax (wmin, tmp);
+ }
+ }
+
+ if (vr0.type == VR_RANGE && TREE_CODE (vr0.max) == INTEGER_CST)
+ {
+ tmp = vr0.max;
+ if (sgn == SIGNED && wi::neg_p (tmp))
+ tmp = zero;
+ wmax = wi::min (wmax, tmp, sgn);
+ }
+
+ min = wide_int_to_tree (expr_type, wmin);
+ max = wide_int_to_tree (expr_type, wmax);
}
else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
{
{
/* If the range was reversed, swap MIN and MAX. */
if (cmp == 1)
- {
- tree t = min;
- min = max;
- max = t;
- }
+ std::swap (min, max);
}
cmp = compare_values (min, max);
the ranges of each of its operands and the expression code. */
static void
-extract_range_from_cond_expr (value_range_t *vr, gimple stmt)
+extract_range_from_cond_expr (value_range_t *vr, gassign *stmt)
{
tree op0, op1;
value_range_t vr0 = VR_INITIALIZER;
in *VR. */
static void
-extract_range_from_assignment (value_range_t *vr, gimple stmt)
+extract_range_from_assignment (value_range_t *vr, gassign *stmt)
{
enum tree_code code = gimple_assign_rhs_code (stmt);
operands around and change the comparison code. */
if (comp == GT_EXPR || comp == GE_EXPR)
{
- value_range_t *tmp;
comp = (comp == GT_EXPR) ? LT_EXPR : LE_EXPR;
- tmp = vr0;
- vr0 = vr1;
- vr1 = tmp;
+ std::swap (vr0, vr1);
}
if (comp == EQ_EXPR)
build_assert_expr_for (tree cond, tree v)
{
tree a;
- gimple assertion;
+ gassign *assertion;
gcc_assert (TREE_CODE (v) == SSA_NAME
&& COMPARISON_CLASS_P (cond));
list of assertions for the corresponding operands. */
static void
-find_conditional_asserts (basic_block bb, gimple last)
+find_conditional_asserts (basic_block bb, gcond *last)
{
gimple_stmt_iterator bsi;
tree op;
list of assertions for the corresponding operands. */
static void
-find_switch_asserts (basic_block bb, gimple last)
+find_switch_asserts (basic_block bb, gswitch *last)
{
gimple_stmt_iterator bsi;
tree op;
static void
find_assert_locations_1 (basic_block bb, sbitmap live)
{
- gimple_stmt_iterator si;
gimple last;
last = last_stmt (bb);
&& gimple_code (last) == GIMPLE_COND
&& !fp_predicate (last)
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
- find_conditional_asserts (bb, last);
+ find_conditional_asserts (bb, as_a <gcond *> (last));
/* If BB's last statement is a switch statement involving integer
operands, determine if we need to add ASSERT_EXPRs. */
if (last
&& gimple_code (last) == GIMPLE_SWITCH
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
- find_switch_asserts (bb, last);
+ find_switch_asserts (bb, as_a <gswitch *> (last));
/* Traverse all the statements in BB marking used names and looking
for statements that may infer assertions for their used operands. */
- for (si = gsi_last_bb (bb); !gsi_end_p (si); gsi_prev (&si))
+ for (gimple_stmt_iterator si = gsi_last_bb (bb); !gsi_end_p (si);
+ gsi_prev (&si))
{
gimple stmt;
tree op;
}
/* Traverse all PHI nodes in BB, updating live. */
- for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
+ gsi_next (&si))
{
use_operand_p arg_p;
ssa_op_iter i;
- gimple phi = gsi_stmt (si);
+ gphi *phi = si.phi ();
tree res = gimple_phi_result (phi);
if (virtual_operand_p (res))
{
i = loop->latch->index;
unsigned int j = single_succ_edge (loop->latch)->dest_idx;
- for (gimple_stmt_iterator gsi = gsi_start_phis (loop->header);
+ for (gphi_iterator gsi = gsi_start_phis (loop->header);
!gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
if (virtual_operand_p (gimple_phi_result (phi)))
continue;
tree arg = gimple_phi_arg_def (phi, j);
/* Accesses to trailing arrays via pointers may access storage
beyond the types array bounds. */
base = get_base_address (ref);
- if (base && TREE_CODE (base) == MEM_REF)
+ if ((warn_array_bounds < 2)
+ && base && TREE_CODE (base) == MEM_REF)
{
tree cref, next = NULL_TREE;
up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound,
build_int_cst (TREE_TYPE (up_bound), 1));
+ /* Empty array. */
+ if (tree_int_cst_equal (low_bound, up_bound_p1))
+ {
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is above array bounds");
+ TREE_NO_WARNING (ref) = 1;
+ }
+
if (TREE_CODE (low_sub) == SSA_NAME)
{
vr = get_value_range (low_sub);
if (vr && vr->type == VR_ANTI_RANGE)
{
if (TREE_CODE (up_sub) == INTEGER_CST
- && tree_int_cst_lt (up_bound, up_sub)
+ && (ignore_off_by_one
+ ? tree_int_cst_lt (up_bound, up_sub)
+ : tree_int_cst_le (up_bound, up_sub))
&& TREE_CODE (low_sub) == INTEGER_CST
- && tree_int_cst_lt (low_sub, low_bound))
+ && tree_int_cst_le (low_sub, low_bound))
{
warning_at (location, OPT_Warray_bounds,
"array subscript is outside array bounds");
}
else if (TREE_CODE (up_sub) == INTEGER_CST
&& (ignore_off_by_one
- ? (tree_int_cst_lt (up_bound, up_sub)
- && !tree_int_cst_equal (up_bound_p1, up_sub))
- : (tree_int_cst_lt (up_bound, up_sub)
- || tree_int_cst_equal (up_bound_p1, up_sub))))
+ ? !tree_int_cst_le (up_sub, up_bound_p1)
+ : !tree_int_cst_le (up_sub, up_bound)))
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
static void
search_for_addr_array (tree t, location_t location)
{
- while (TREE_CODE (t) == SSA_NAME)
- {
- gimple g = SSA_NAME_DEF_STMT (t);
-
- if (gimple_code (g) != GIMPLE_ASSIGN)
- return;
-
- if (get_gimple_rhs_class (gimple_assign_rhs_code (g))
- != GIMPLE_SINGLE_RHS)
- return;
-
- t = gimple_assign_rhs1 (g);
- }
-
-
- /* We are only interested in addresses of ARRAY_REF's. */
- if (TREE_CODE (t) != ADDR_EXPR)
- return;
-
/* Check each ARRAY_REFs in the reference chain. */
do
{
if (TREE_CODE (t) == ARRAY_REF)
check_array_ref (location, t, false /*ignore_off_by_one*/);
- if (TREE_CODE (t) == MEM_REF
- || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
- search_for_addr_array (TREE_OPERAND (t, 0), location);
-
- if (TREE_CODE (t) == ADDR_EXPR)
- *walk_subtree = FALSE;
+ else if (TREE_CODE (t) == ADDR_EXPR)
+ {
+ search_for_addr_array (t, location);
+ *walk_subtree = FALSE;
+ }
return NULL_TREE;
}
{
gimple stmt = gsi_stmt (si);
struct walk_stmt_info wi;
- if (!gimple_has_location (stmt))
+ if (!gimple_has_location (stmt)
+ || is_gimple_debug (stmt))
continue;
- if (is_gimple_call (stmt))
- {
- size_t i;
- size_t n = gimple_call_num_args (stmt);
- for (i = 0; i < n; i++)
- {
- tree arg = gimple_call_arg (stmt, i);
- search_for_addr_array (arg, gimple_location (stmt));
- }
- }
- else
- {
- memset (&wi, 0, sizeof (wi));
- wi.info = CONST_CAST (void *, (const void *)
- gimple_location_ptr (stmt));
+ memset (&wi, 0, sizeof (wi));
+ wi.info = CONST_CAST (void *, (const void *)
+ gimple_location_ptr (stmt));
- walk_gimple_op (gsi_stmt (si),
- check_array_bounds,
- &wi);
- }
+ walk_gimple_op (gsi_stmt (si),
+ check_array_bounds,
+ &wi);
}
}
}
&& (is_gimple_call (stmt)
|| !gimple_vuse (stmt)))
return true;
+ else if (is_gimple_call (stmt) && gimple_call_internal_p (stmt))
+ switch (gimple_call_internal_fn (stmt))
+ {
+ case IFN_ADD_OVERFLOW:
+ case IFN_SUB_OVERFLOW:
+ case IFN_MUL_OVERFLOW:
+ /* These internal calls return _Complex integer type,
+ but are interesting to VRP nevertheless. */
+ if (lhs && TREE_CODE (lhs) == SSA_NAME)
+ return true;
+ break;
+ default:
+ break;
+ }
}
else if (gimple_code (stmt) == GIMPLE_COND
|| gimple_code (stmt) == GIMPLE_SWITCH)
FOR_EACH_BB_FN (bb, cfun)
{
- gimple_stmt_iterator si;
-
- for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+ for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
+ gsi_next (&si))
{
- gimple phi = gsi_stmt (si);
+ gphi *phi = si.phi ();
if (!stmt_interesting_for_vrp (phi))
{
tree lhs = PHI_RESULT (phi);
prop_set_simulate_again (phi, true);
}
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
+ gsi_next (&si))
{
gimple stmt = gsi_stmt (si);
return name;
}
+/* Return the singleton value-range for NAME if that is a constant
+ but signal to not follow SSA edges. */
+
+static inline tree
+vrp_valueize_1 (tree name)
+{
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ /* If the definition may be simulated again we cannot follow
+ this SSA edge as the SSA propagator does not necessarily
+ re-visit the use. */
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ if (!gimple_nop_p (def_stmt)
+ && prop_simulate_again_p (def_stmt))
+ return NULL_TREE;
+ value_range_t *vr = get_value_range (name);
+ if (range_int_cst_singleton_p (vr))
+ return vr->min;
+ }
+ return name;
+}
+
/* Visit assignment STMT. If it produces an interesting range, record
the SSA name in *OUTPUT_P. */
value_range_t new_vr = VR_INITIALIZER;
/* Try folding the statement to a constant first. */
- tree tem = gimple_fold_stmt_to_constant (stmt, vrp_valueize);
- if (tem)
+ tree tem = gimple_fold_stmt_to_constant_1 (stmt, vrp_valueize,
+ vrp_valueize_1);
+ if (tem && is_gimple_min_invariant (tem))
set_value_range_to_value (&new_vr, tem, NULL);
/* Then dispatch to value-range extracting functions. */
else if (code == GIMPLE_CALL)
extract_range_basic (&new_vr, stmt);
else
- extract_range_from_assignment (&new_vr, stmt);
+ extract_range_from_assignment (&new_vr, as_a <gassign *> (stmt));
if (update_value_range (lhs, &new_vr))
{
return SSA_PROP_NOT_INTERESTING;
}
+ else if (is_gimple_call (stmt) && gimple_call_internal_p (stmt))
+ switch (gimple_call_internal_fn (stmt))
+ {
+ case IFN_ADD_OVERFLOW:
+ case IFN_SUB_OVERFLOW:
+ case IFN_MUL_OVERFLOW:
+ /* These internal calls return _Complex integer type,
+ which VRP does not track, but the immediate uses
+ thereof might be interesting. */
+ if (lhs && TREE_CODE (lhs) == SSA_NAME)
+ {
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ enum ssa_prop_result res = SSA_PROP_VARYING;
+
+ set_value_range_to_varying (get_value_range (lhs));
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
+ {
+ gimple use_stmt = USE_STMT (use_p);
+ if (!is_gimple_assign (use_stmt))
+ continue;
+ enum tree_code rhs_code = gimple_assign_rhs_code (use_stmt);
+ if (rhs_code != REALPART_EXPR && rhs_code != IMAGPART_EXPR)
+ continue;
+ tree rhs1 = gimple_assign_rhs1 (use_stmt);
+ tree use_lhs = gimple_assign_lhs (use_stmt);
+ if (TREE_CODE (rhs1) != rhs_code
+ || TREE_OPERAND (rhs1, 0) != lhs
+ || TREE_CODE (use_lhs) != SSA_NAME
+ || !stmt_interesting_for_vrp (use_stmt)
+ || (!INTEGRAL_TYPE_P (TREE_TYPE (use_lhs))
+ || !TYPE_MIN_VALUE (TREE_TYPE (use_lhs))
+ || !TYPE_MAX_VALUE (TREE_TYPE (use_lhs))))
+ continue;
+
+ /* If there is a change in the value range for any of the
+ REALPART_EXPR/IMAGPART_EXPR immediate uses, return
+ SSA_PROP_INTERESTING. If there are any REALPART_EXPR
+ or IMAGPART_EXPR immediate uses, but none of them have
+ a change in their value ranges, return
+ SSA_PROP_NOT_INTERESTING. If there are no
+ {REAL,IMAG}PART_EXPR uses at all,
+ return SSA_PROP_VARYING. */
+ value_range_t new_vr = VR_INITIALIZER;
+ extract_range_basic (&new_vr, use_stmt);
+ value_range_t *old_vr = get_value_range (use_lhs);
+ if (old_vr->type != new_vr.type
+ || !vrp_operand_equal_p (old_vr->min, new_vr.min)
+ || !vrp_operand_equal_p (old_vr->max, new_vr.max)
+ || !vrp_bitmap_equal_p (old_vr->equiv, new_vr.equiv))
+ res = SSA_PROP_INTERESTING;
+ else
+ res = SSA_PROP_NOT_INTERESTING;
+ BITMAP_FREE (new_vr.equiv);
+ if (res == SSA_PROP_INTERESTING)
+ {
+ *output_p = lhs;
+ return res;
+ }
+ }
+
+ return res;
+ }
+ break;
+ default:
+ break;
+ }
/* Every other statement produces no useful ranges. */
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
tree type = TREE_TYPE (op0);
value_range_t *vr0 = get_value_range (op0);
- if (vr0->type != VR_VARYING
+ if (vr0->type == VR_RANGE
&& INTEGRAL_TYPE_P (type)
&& vrp_val_is_min (vr0->min)
&& vrp_val_is_max (vr0->max)
SSA_PROP_VARYING. */
static enum ssa_prop_result
-vrp_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
+vrp_visit_cond_stmt (gcond *stmt, edge *taken_edge_p)
{
tree val;
bool sop;
returned. */
static bool
-find_case_label_index (gimple stmt, size_t start_idx, tree val, size_t *idx)
+find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx)
{
size_t n = gimple_switch_num_labels (stmt);
size_t low, high;
Returns true if the default label is not needed. */
static bool
-find_case_label_range (gimple stmt, tree min, tree max, size_t *min_idx,
+find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx,
size_t *max_idx)
{
size_t i, j;
Returns true if the default label is not needed. */
static bool
-find_case_label_ranges (gimple stmt, value_range_t *vr, size_t *min_idx1,
+find_case_label_ranges (gswitch *stmt, value_range_t *vr, size_t *min_idx1,
size_t *max_idx1, size_t *min_idx2,
size_t *max_idx2)
{
SSA_PROP_VARYING. */
static enum ssa_prop_result
-vrp_visit_switch_stmt (gimple stmt, edge *taken_edge_p)
+vrp_visit_switch_stmt (gswitch *stmt, edge *taken_edge_p)
{
tree op, val;
value_range_t *vr;
else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
return vrp_visit_assignment_or_call (stmt, output_p);
else if (gimple_code (stmt) == GIMPLE_COND)
- return vrp_visit_cond_stmt (stmt, taken_edge_p);
+ return vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p);
else if (gimple_code (stmt) == GIMPLE_SWITCH)
- return vrp_visit_switch_stmt (stmt, taken_edge_p);
+ return vrp_visit_switch_stmt (as_a <gswitch *> (stmt), taken_edge_p);
/* All other statements produce nothing of interest for VRP, so mark
their outputs varying and prevent further simulation. */
value ranges, set a new range for the LHS of PHI. */
static enum ssa_prop_result
-vrp_visit_phi_node (gimple phi)
+vrp_visit_phi_node (gphi *phi)
{
size_t i;
tree lhs = PHI_RESULT (phi);
fprintf (dump_file, "\n");
}
+ if (vr_result.type == VR_VARYING)
+ return SSA_PROP_VARYING;
+
return SSA_PROP_INTERESTING;
}
if (integer_zerop (op1))
gimple_assign_set_rhs_with_ops (gsi,
need_conversion
- ? NOP_EXPR : TREE_CODE (op0),
- op0, NULL_TREE);
+ ? NOP_EXPR : TREE_CODE (op0), op0);
/* For A != B we substitute A ^ B. Either with conversion. */
else if (need_conversion)
{
- tree tem = make_ssa_name (TREE_TYPE (op0), NULL);
- gimple newop = gimple_build_assign_with_ops (BIT_XOR_EXPR, tem, op0, op1);
+ tree tem = make_ssa_name (TREE_TYPE (op0));
+ gassign *newop
+ = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
gsi_insert_before (gsi, newop, GSI_SAME_STMT);
- gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem, NULL_TREE);
+ gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
}
/* Or without. */
else
/* Simplify a division or modulo operator to a right shift or
bitwise and if the first operand is unsigned or is greater
- than zero and the second operand is an exact power of two. */
+ than zero and the second operand is an exact power of two.
+ For TRUNC_MOD_EXPR op0 % op1 with constant op1, optimize it
+ into just op0 if op0's range is known to be a subset of
+ [-op1 + 1, op1 - 1] for signed and [0, op1 - 1] for unsigned
+ modulo. */
static bool
simplify_div_or_mod_using_ranges (gimple stmt)
tree val = NULL;
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
- value_range_t *vr = get_value_range (gimple_assign_rhs1 (stmt));
+ value_range_t *vr = get_value_range (op0);
+
+ if (rhs_code == TRUNC_MOD_EXPR
+ && TREE_CODE (op1) == INTEGER_CST
+ && tree_int_cst_sgn (op1) == 1
+ && range_int_cst_p (vr)
+ && tree_int_cst_lt (vr->max, op1))
+ {
+ if (TYPE_UNSIGNED (TREE_TYPE (op0))
+ || tree_int_cst_sgn (vr->min) >= 0
+ || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1),
+ vr->min))
+ {
+ /* If op0 already has the range op0 % op1 has,
+ then TRUNC_MOD_EXPR won't change anything. */
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ gimple_assign_set_rhs_from_tree (&gsi, op0);
+ update_stmt (stmt);
+ return true;
+ }
+ }
+
+ if (!integer_pow2p (op1))
+ return false;
if (TYPE_UNSIGNED (TREE_TYPE (op0)))
{
if (op == NULL_TREE)
return false;
- gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op, NULL);
+ gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
update_stmt (gsi_stmt (*gsi));
return true;
}
a known value range VR.
If there is one and only one value which will satisfy the
- conditional, then return that value. Else return NULL. */
+ conditional, then return that value. Else return NULL.
+
+ If signed overflow must be undefined for the value to satisfy
+ the conditional, then set *STRICT_OVERFLOW_P to true. */
static tree
test_for_singularity (enum tree_code cond_code, tree op0,
- tree op1, value_range_t *vr)
+ tree op1, value_range_t *vr,
+ bool *strict_overflow_p)
{
tree min = NULL;
tree max = NULL;
then there is only one value which can satisfy the condition,
return that value. */
if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
- return min;
+ {
+ if ((cond_code == LE_EXPR || cond_code == LT_EXPR)
+ && is_overflow_infinity (vr->max))
+ *strict_overflow_p = true;
+ if ((cond_code == GE_EXPR || cond_code == GT_EXPR)
+ && is_overflow_infinity (vr->min))
+ *strict_overflow_p = true;
+
+ return min;
+ }
}
return NULL;
}
the original conditional. */
static bool
-simplify_cond_using_ranges (gimple stmt)
+simplify_cond_using_ranges (gcond *stmt)
{
tree op0 = gimple_cond_lhs (stmt);
tree op1 = gimple_cond_rhs (stmt);
able to simplify this conditional. */
if (vr->type == VR_RANGE)
{
- tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
+ enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
+ bool sop = false;
+ tree new_tree = test_for_singularity (cond_code, op0, op1, vr, &sop);
- if (new_tree)
+ if (new_tree
+ && (!sop || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))))
{
if (dump_file)
{
fprintf (dump_file, "\n");
}
+ if (sop && issue_strict_overflow_warning (wc))
+ {
+ location_t location = input_location;
+ if (gimple_has_location (stmt))
+ location = gimple_location (stmt);
+
+ warning_at (location, OPT_Wstrict_overflow,
+ "assuming signed overflow does not occur when "
+ "simplifying conditional");
+ }
+
return true;
}
/* Try again after inverting the condition. We only deal
with integral types here, so no need to worry about
issues with inverting FP comparisons. */
- cond_code = invert_tree_comparison (cond_code, false);
- new_tree = test_for_singularity (cond_code, op0, op1, vr);
+ sop = false;
+ new_tree = test_for_singularity
+ (invert_tree_comparison (cond_code, false),
+ op0, op1, vr, &sop);
- if (new_tree)
+ if (new_tree
+ && (!sop || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0))))
{
if (dump_file)
{
fprintf (dump_file, "\n");
}
+ if (sop && issue_strict_overflow_warning (wc))
+ {
+ location_t location = input_location;
+ if (gimple_has_location (stmt))
+ location = gimple_location (stmt);
+
+ warning_at (location, OPT_Wstrict_overflow,
+ "assuming signed overflow does not occur when "
+ "simplifying conditional");
+ }
+
return true;
}
}
argument. */
static bool
-simplify_switch_using_ranges (gimple stmt)
+simplify_switch_using_ranges (gswitch *stmt)
{
tree op = gimple_switch_index (stmt);
value_range_t *vr;
machine_mode fltmode = TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
machine_mode mode;
tree tem;
- gimple conv;
+ gassign *conv;
/* We can only handle constant ranges. */
if (vr->type != VR_RANGE
/* It works, insert a truncation or sign-change before the
float conversion. */
tem = make_ssa_name (build_nonstandard_integer_type
- (GET_MODE_PRECISION (mode), 0), NULL);
- conv = gimple_build_assign_with_ops (NOP_EXPR, tem, rhs1, NULL_TREE);
+ (GET_MODE_PRECISION (mode), 0));
+ conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
gsi_insert_before (gsi, conv, GSI_SAME_STMT);
gimple_assign_set_rhs1 (stmt, tem);
update_stmt (stmt);
gimple g;
location_t loc = gimple_location (stmt);
if (is_ubsan)
- g = gimple_build_assign_with_ops (subcode, gimple_call_lhs (stmt),
- op0, op1);
+ g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
else
{
int prec = TYPE_PRECISION (type);
op0 = fold_convert (utype, op0);
else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
{
- g = gimple_build_assign_with_ops (NOP_EXPR,
- make_ssa_name (utype, NULL),
- op0, NULL_TREE);
+ g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
gimple_set_location (g, loc);
gsi_insert_before (gsi, g, GSI_SAME_STMT);
op0 = gimple_assign_lhs (g);
op1 = fold_convert (utype, op1);
else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
{
- g = gimple_build_assign_with_ops (NOP_EXPR,
- make_ssa_name (utype, NULL),
- op1, NULL_TREE);
+ g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
gimple_set_location (g, loc);
gsi_insert_before (gsi, g, GSI_SAME_STMT);
op1 = gimple_assign_lhs (g);
}
- g = gimple_build_assign_with_ops (subcode, make_ssa_name (utype, NULL),
- op0, op1);
+ g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
gimple_set_location (g, loc);
gsi_insert_before (gsi, g, GSI_SAME_STMT);
if (utype != type)
{
- g = gimple_build_assign_with_ops (NOP_EXPR,
- make_ssa_name (type, NULL),
- gimple_assign_lhs (g), NULL_TREE);
+ g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
+ gimple_assign_lhs (g));
gimple_set_location (g, loc);
gsi_insert_before (gsi, g, GSI_SAME_STMT);
}
- g = gimple_build_assign_with_ops (COMPLEX_EXPR, gimple_call_lhs (stmt),
- gimple_assign_lhs (g),
- build_int_cst (type, ovf));
+ g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
+ gimple_assign_lhs (g),
+ build_int_cst (type, ovf));
}
gimple_set_location (g, loc);
gsi_replace (gsi, g, false);
/* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
and BIT_AND_EXPR respectively if the first operand is greater
- than zero and the second operand is an exact power of two. */
+ than zero and the second operand is an exact power of two.
+ Also optimize TRUNC_MOD_EXPR away if the second operand is
+ constant and the first operand already has the right value
+ range. */
case TRUNC_DIV_EXPR:
case TRUNC_MOD_EXPR:
- if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
- && integer_pow2p (gimple_assign_rhs2 (stmt)))
+ if (TREE_CODE (rhs1) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
return simplify_div_or_mod_using_ranges (stmt);
break;
}
}
else if (gimple_code (stmt) == GIMPLE_COND)
- return simplify_cond_using_ranges (stmt);
+ return simplify_cond_using_ranges (as_a <gcond *> (stmt));
else if (gimple_code (stmt) == GIMPLE_SWITCH)
- return simplify_switch_using_ranges (stmt);
+ return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
else if (is_gimple_call (stmt)
&& gimple_call_internal_p (stmt))
return simplify_internal_call_using_ranges (gsi, stmt);
gimple_assign_rhs2 (stmt),
stmt);
}
- else if (gimple_code (stmt) == GIMPLE_COND)
- val = vrp_evaluate_conditional (gimple_cond_code (stmt),
- gimple_cond_lhs (stmt),
- gimple_cond_rhs (stmt),
+ else if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+ val = vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+ gimple_cond_lhs (cond_stmt),
+ gimple_cond_rhs (cond_stmt),
stmt);
else
return false;
else
{
gcc_assert (gimple_code (stmt) == GIMPLE_COND);
+ gcond *cond_stmt = as_a <gcond *> (stmt);
if (integer_zerop (val))
- gimple_cond_make_false (stmt);
+ gimple_cond_make_false (cond_stmt);
else if (integer_onep (val))
- gimple_cond_make_true (stmt);
+ gimple_cond_make_true (cond_stmt);
else
gcc_unreachable ();
}
return simplify_stmt_using_ranges (si);
}
-/* Stack of dest,src equivalency pairs that need to be restored after
- each attempt to thread a block's incoming edge to an outgoing edge.
-
- A NULL entry is used to mark the end of pairs which need to be
- restored. */
-static vec<tree> equiv_stack;
+/* Unwindable const/copy equivalences. */
+const_and_copies *equiv_stack;
/* A trivial wrapper so that we can present the generic jump threading
code with a simple API for simplifying statements. STMT is the
static tree
simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
{
- if (gimple_code (stmt) == GIMPLE_COND)
- return vrp_evaluate_conditional (gimple_cond_code (stmt),
- gimple_cond_lhs (stmt),
- gimple_cond_rhs (stmt), within_stmt);
+ if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+ return vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+ gimple_cond_lhs (cond_stmt),
+ gimple_cond_rhs (cond_stmt),
+ within_stmt);
- if (gimple_code (stmt) == GIMPLE_ASSIGN)
+ if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
{
value_range_t new_vr = VR_INITIALIZER;
- tree lhs = gimple_assign_lhs (stmt);
+ tree lhs = gimple_assign_lhs (assign_stmt);
if (TREE_CODE (lhs) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
- extract_range_from_assignment (&new_vr, stmt);
+ extract_range_from_assignment (&new_vr, assign_stmt);
if (range_int_cst_singleton_p (&new_vr))
return new_vr.min;
}
identify_jump_threads (void)
{
basic_block bb;
- gimple dummy;
+ gcond *dummy;
int i;
edge e;
/* Allocate our unwinder stack to unwind any temporary equivalences
that might be recorded. */
- equiv_stack.create (20);
+ equiv_stack = new const_and_copies (dump_file, dump_flags);
/* To avoid lots of silly node creation, we create a single
conditional and just modify it in-place when attempting to
if (! potentially_threadable_block (bb))
continue;
- /* We only care about blocks ending in a COND_EXPR. While there
- may be some value in handling SWITCH_EXPR here, I doubt it's
- terribly important. */
- last = gsi_stmt (gsi_last_bb (bb));
+ last = last_stmt (bb);
/* We're basically looking for a switch or any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
- check it explicitly. */
- if (gimple_code (last) == GIMPLE_SWITCH
+ check it explicitly.
+
+ We also handle the case where there are no statements in the
+ block. This come up with forwarder blocks that are not
+ optimized away because they lead to a loop header. But we do
+ want to thread through them as we can sometimes thread to the
+ loop exit which is obviously profitable. */
+ if (!last
+ || gimple_code (last) == GIMPLE_SWITCH
|| (gimple_code (last) == GIMPLE_COND
&& TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
continue;
- thread_across_edge (dummy, e, true, &equiv_stack,
+ thread_across_edge (dummy, e, true, equiv_stack,
simplify_stmt_for_jump_threading);
}
}
finalize_jump_threads (void)
{
thread_through_all_blocks (false);
- equiv_stack.release ();
+ delete equiv_stack;
}
substitute_and_fold (op_with_constant_singleton_value_range,
vrp_fold_stmt, false);
- if (warn_array_bounds)
+ if (warn_array_bounds && first_pass_instance)
check_all_array_refs ();
/* We must identify jump threading opportunities before we release
|| (vr_value[i]->type == VR_UNDEFINED))
continue;
- if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
- && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
- && (vr_value[i]->type == VR_RANGE
- || vr_value[i]->type == VR_ANTI_RANGE))
- set_range_info (name, vr_value[i]->type, vr_value[i]->min,
- vr_value[i]->max);
+ if ((TREE_CODE (vr_value[i]->min) == INTEGER_CST)
+ && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
+ && (vr_value[i]->type == VR_RANGE
+ || vr_value[i]->type == VR_ANTI_RANGE))
+ set_range_info (name, vr_value[i]->type, vr_value[i]->min,
+ vr_value[i]->max);
}
/* Free allocated memory. */
projects / gcc.git / blobdiff