typedef struct value_range_d value_range_t;
+#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
static int compare_values (tree val1, tree val2);
static int compare_values_warnv (tree val1, tree val2, bool *);
static void vrp_meet (value_range_t *, value_range_t *);
+static void vrp_intersect_ranges (value_range_t *, value_range_t *);
static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
tree, tree, bool, bool *,
bool *);
}
+/* Set value range VR to VR_UNDEFINED. */
+
+static inline void
+set_value_range_to_undefined (value_range_t *vr)
+{
+ vr->type = VR_UNDEFINED;
+ vr->min = vr->max = NULL_TREE;
+ if (vr->equiv)
+ bitmap_clear (vr->equiv);
+}
+
+
/* Set value range VR to VR_VARYING. */
static inline void
set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
tree min, tree max, bitmap equiv)
{
- /* Nothing to canonicalize for symbolic or unknown or varying ranges. */
- if ((t != VR_RANGE
- && t != VR_ANTI_RANGE)
- || TREE_CODE (min) != INTEGER_CST
+ /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (t == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr);
+ return;
+ }
+ else if (t == VR_VARYING)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* Nothing to canonicalize for symbolic ranges. */
+ if (TREE_CODE (min) != INTEGER_CST
|| TREE_CODE (max) != INTEGER_CST)
{
set_value_range (vr, t, min, max, equiv);
if (is_min && is_max)
{
- /* We cannot deal with empty ranges, drop to varying. */
+ /* We cannot deal with empty ranges, drop to varying.
+ ??? This could be VR_UNDEFINED instead. */
set_value_range_to_varying (vr);
return;
}
}
}
+ /* Drop [-INF(OVF), +INF(OVF)] to varying. */
+ if (needs_overflow_infinity (TREE_TYPE (min))
+ && is_overflow_infinity (min)
+ && is_overflow_infinity (max))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
set_value_range (vr, t, min, max, equiv);
}
}
-/* Set value range VR to VR_UNDEFINED. */
-
-static inline void
-set_value_range_to_undefined (value_range_t *vr)
-{
- vr->type = VR_UNDEFINED;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
-}
-
-
/* If abs (min) < abs (max), set VR to [-max, max], if
abs (min) >= abs (max), set VR to [-min, min]. */
/* If VAR is a default definition of a parameter, the variable can
take any value in VAR's type. */
sym = SSA_NAME_VAR (var);
- if (SSA_NAME_IS_DEFAULT_DEF (var)
- && TREE_CODE (sym) == PARM_DECL)
- {
- /* Try to use the "nonnull" attribute to create ~[0, 0]
- anti-ranges for pointers. Note that this is only valid with
- default definitions of PARM_DECLs. */
- if (POINTER_TYPE_P (TREE_TYPE (sym))
- && nonnull_arg_p (sym))
+ if (SSA_NAME_IS_DEFAULT_DEF (var))
+ {
+ if (TREE_CODE (sym) == PARM_DECL)
+ {
+ /* Try to use the "nonnull" attribute to create ~[0, 0]
+ anti-ranges for pointers. Note that this is only valid with
+ default definitions of PARM_DECLs. */
+ if (POINTER_TYPE_P (TREE_TYPE (sym))
+ && nonnull_arg_p (sym))
+ set_value_range_to_nonnull (vr, TREE_TYPE (sym));
+ else
+ set_value_range_to_varying (vr);
+ }
+ else if (TREE_CODE (sym) == RESULT_DECL
+ && DECL_BY_REFERENCE (sym))
set_value_range_to_nonnull (vr, TREE_TYPE (sym));
- else
- set_value_range_to_varying (vr);
}
return vr;
extract_range_from_assert (value_range_t *vr_p, tree expr)
{
tree var, cond, limit, min, max, type;
- value_range_t *var_vr, *limit_vr;
+ value_range_t *limit_vr;
enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
else
gcc_unreachable ();
- /* If VAR already had a known range, it may happen that the new
- range we have computed and VAR's range are not compatible. For
- instance,
-
- if (p_5 == NULL)
- p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
- x_7 = p_6->fld;
- p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
-
- While the above comes from a faulty program, it will cause an ICE
- later because p_8 and p_6 will have incompatible ranges and at
- the same time will be considered equivalent. A similar situation
- would arise from
-
- if (i_5 > 10)
- i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
- if (i_5 < 5)
- i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
-
- Again i_6 and i_7 will have incompatible ranges. It would be
- pointless to try and do anything with i_7's range because
- anything dominated by 'if (i_5 < 5)' will be optimized away.
- Note, due to the wa in which simulation proceeds, the statement
- i_7 = ASSERT_EXPR <...> we would never be visited because the
- conditional 'if (i_5 < 5)' always evaluates to false. However,
- this extra check does not hurt and may protect against future
- changes to VRP that may get into a situation similar to the
- NULL pointer dereference example.
-
- Note that these compatibility tests are only needed when dealing
- with ranges or a mix of range and anti-range. If VAR_VR and VR_P
- are both anti-ranges, they will always be compatible, because two
- anti-ranges will always have a non-empty intersection. */
-
- var_vr = get_value_range (var);
-
- /* We may need to make adjustments when VR_P and VAR_VR are numeric
- ranges or anti-ranges. */
- if (vr_p->type == VR_VARYING
- || vr_p->type == VR_UNDEFINED
- || var_vr->type == VR_VARYING
- || var_vr->type == VR_UNDEFINED
- || symbolic_range_p (vr_p)
- || symbolic_range_p (var_vr))
- return;
-
- if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
- {
- /* If the two ranges have a non-empty intersection, we can
- refine the resulting range. Since the assert expression
- creates an equivalency and at the same time it asserts a
- predicate, we can take the intersection of the two ranges to
- get better precision. */
- if (value_ranges_intersect_p (var_vr, vr_p))
- {
- /* Use the larger of the two minimums. */
- if (compare_values (vr_p->min, var_vr->min) == -1)
- min = var_vr->min;
- else
- min = vr_p->min;
-
- /* Use the smaller of the two maximums. */
- if (compare_values (vr_p->max, var_vr->max) == 1)
- max = var_vr->max;
- else
- max = vr_p->max;
-
- set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
- }
- else
- {
- /* The two ranges do not intersect, set the new range to
- VARYING, because we will not be able to do anything
- meaningful with it. */
- set_value_range_to_varying (vr_p);
- }
- }
- else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
- || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
- {
- /* A range and an anti-range will cancel each other only if
- their ends are the same. For instance, in the example above,
- p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
- so VR_P should be set to VR_VARYING. */
- if (compare_values (var_vr->min, vr_p->min) == 0
- && compare_values (var_vr->max, vr_p->max) == 0)
- set_value_range_to_varying (vr_p);
- else
- {
- tree min, max, anti_min, anti_max, real_min, real_max;
- int cmp;
-
- /* We want to compute the logical AND of the two ranges;
- there are three cases to consider.
-
-
- 1. The VR_ANTI_RANGE range is completely within the
- VR_RANGE and the endpoints of the ranges are
- different. In that case the resulting range
- should be whichever range is more precise.
- Typically that will be the VR_RANGE.
-
- 2. The VR_ANTI_RANGE is completely disjoint from
- the VR_RANGE. In this case the resulting range
- should be the VR_RANGE.
-
- 3. There is some overlap between the VR_ANTI_RANGE
- and the VR_RANGE.
-
- 3a. If the high limit of the VR_ANTI_RANGE resides
- within the VR_RANGE, then the result is a new
- VR_RANGE starting at the high limit of the
- VR_ANTI_RANGE + 1 and extending to the
- high limit of the original VR_RANGE.
-
- 3b. If the low limit of the VR_ANTI_RANGE resides
- within the VR_RANGE, then the result is a new
- VR_RANGE starting at the low limit of the original
- VR_RANGE and extending to the low limit of the
- VR_ANTI_RANGE - 1. */
- if (vr_p->type == VR_ANTI_RANGE)
- {
- anti_min = vr_p->min;
- anti_max = vr_p->max;
- real_min = var_vr->min;
- real_max = var_vr->max;
- }
- else
- {
- anti_min = var_vr->min;
- anti_max = var_vr->max;
- real_min = vr_p->min;
- real_max = vr_p->max;
- }
-
-
- /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
- not including any endpoints. */
- if (compare_values (anti_max, real_max) == -1
- && compare_values (anti_min, real_min) == 1)
- {
- /* If the range is covering the whole valid range of
- the type keep the anti-range. */
- if (!vrp_val_is_min (real_min)
- || !vrp_val_is_max (real_max))
- set_value_range (vr_p, VR_RANGE, real_min,
- real_max, vr_p->equiv);
- }
- /* Case 2, VR_ANTI_RANGE completely disjoint from
- VR_RANGE. */
- else if (compare_values (anti_min, real_max) == 1
- || compare_values (anti_max, real_min) == -1)
- {
- set_value_range (vr_p, VR_RANGE, real_min,
- real_max, vr_p->equiv);
- }
- /* Case 3a, the anti-range extends into the low
- part of the real range. Thus creating a new
- low for the real range. */
- else if (((cmp = compare_values (anti_max, real_min)) == 1
- || cmp == 0)
- && compare_values (anti_max, real_max) == -1)
- {
- gcc_assert (!is_positive_overflow_infinity (anti_max));
- if (needs_overflow_infinity (TREE_TYPE (anti_max))
- && vrp_val_is_max (anti_max))
- {
- if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
- {
- set_value_range_to_varying (vr_p);
- return;
- }
- min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
- }
- else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
- {
- if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
- min = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
- anti_max,
- build_int_cst (TREE_TYPE (var_vr->min),
- -1));
- else
- min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
- anti_max,
- build_int_cst (TREE_TYPE (var_vr->min),
- 1));
- }
- else
- min = fold_build_pointer_plus_hwi (anti_max, 1);
- max = real_max;
- set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
- }
- /* Case 3b, the anti-range extends into the high
- part of the real range. Thus creating a new
- higher for the real range. */
- else if (compare_values (anti_min, real_min) == 1
- && ((cmp = compare_values (anti_min, real_max)) == -1
- || cmp == 0))
- {
- gcc_assert (!is_negative_overflow_infinity (anti_min));
- if (needs_overflow_infinity (TREE_TYPE (anti_min))
- && vrp_val_is_min (anti_min))
- {
- if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
- {
- set_value_range_to_varying (vr_p);
- return;
- }
- max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
- }
- else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
- {
- if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
- && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
- max = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
- anti_min,
- build_int_cst (TREE_TYPE (var_vr->min),
- -1));
- else
- max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
- anti_min,
- build_int_cst (TREE_TYPE (var_vr->min),
- 1));
- }
- else
- max = fold_build_pointer_plus_hwi (anti_min, -1);
- min = real_min;
- set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
- }
- }
- }
+ /* Finally intersect the new range with what we already know about var. */
+ vrp_intersect_ranges (vr_p, get_value_range (var));
}
return true;
}
+/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
+ so that *VR0 U *VR1 == *AR. Returns true if that is possible,
+ false otherwise. If *AR can be represented with a single range
+ *VR1 will be VR_UNDEFINED. */
+
+static bool
+ranges_from_anti_range (value_range_t *ar,
+ value_range_t *vr0, value_range_t *vr1)
+{
+ tree type = TREE_TYPE (ar->min);
+
+ vr0->type = VR_UNDEFINED;
+ vr1->type = VR_UNDEFINED;
+
+ if (ar->type != VR_ANTI_RANGE
+ || TREE_CODE (ar->min) != INTEGER_CST
+ || TREE_CODE (ar->max) != INTEGER_CST
+ || !vrp_val_min (type)
+ || !vrp_val_max (type))
+ return false;
+
+ if (!vrp_val_is_min (ar->min))
+ {
+ vr0->type = VR_RANGE;
+ vr0->min = vrp_val_min (type);
+ vr0->max
+ = double_int_to_tree (type,
+ double_int_sub (tree_to_double_int (ar->min),
+ double_int_one));
+ }
+ if (!vrp_val_is_max (ar->max))
+ {
+ vr1->type = VR_RANGE;
+ vr1->min
+ = double_int_to_tree (type,
+ double_int_add (tree_to_double_int (ar->max),
+ double_int_one));
+ vr1->max = vrp_val_max (type);
+ }
+ if (vr0->type == VR_UNDEFINED)
+ {
+ *vr0 = *vr1;
+ vr1->type = VR_UNDEFINED;
+ }
+
+ return vr0->type != VR_UNDEFINED;
+}
+
/* Helper to extract a value-range *VR for a multiplicative operation
*VR0 CODE *VR1. */
value_range_t *vr0_, value_range_t *vr1_)
{
value_range_t vr0 = *vr0_, vr1 = *vr1_;
+ value_range_t vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
enum value_range_type type;
tree min = NULL_TREE, max = NULL_TREE;
int cmp;
&& code != ROUND_DIV_EXPR
&& code != TRUNC_MOD_EXPR
&& code != RSHIFT_EXPR
+ && code != LSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
else if (vr1.type == VR_UNDEFINED)
set_value_range_to_varying (&vr1);
+ /* Now canonicalize anti-ranges to ranges when they are not symbolic
+ and express ~[] op X as ([]' op X) U ([]'' op X). */
+ if (vr0.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
+ {
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+ &vrtem1, vr1_);
+ vrp_meet (vr, &vrres);
+ }
+ return;
+ }
+ /* Likewise for X op ~[]. */
+ if (vr1.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
+ {
+ extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+ vr0_, &vrtem1);
+ vrp_meet (vr, &vrres);
+ }
+ return;
+ }
+
/* The type of the resulting value range defaults to VR0.TYPE. */
type = vr0.type;
extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
return;
}
+ else if (code == LSHIFT_EXPR)
+ {
+ /* If we have a LSHIFT_EXPR with any shift values outside [0..prec-1],
+ then drop to VR_VARYING. Outside of this range we get undefined
+ behavior from the shift operation. We cannot even trust
+ SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
+ shifts, and the operation at the tree level may be widened. */
+ if (vr1.type != VR_RANGE
+ || !value_range_nonnegative_p (&vr1)
+ || TREE_CODE (vr1.max) != INTEGER_CST
+ || compare_tree_int (vr1.max, TYPE_PRECISION (expr_type) - 1) == 1)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* We can map shifts by constants to MULT_EXPR handling. */
+ if (range_int_cst_singleton_p (&vr1))
+ {
+ value_range_t vr1p = VR_INITIALIZER;
+ vr1p.type = VR_RANGE;
+ vr1p.min
+ = double_int_to_tree (expr_type,
+ double_int_lshift (double_int_one,
+ TREE_INT_CST_LOW (vr1.min),
+ TYPE_PRECISION (expr_type),
+ false));
+ vr1p.max = vr1p.min;
+ extract_range_from_multiplicative_op_1 (vr, MULT_EXPR, &vr0, &vr1p);
+ return;
+ }
+
+ set_value_range_to_varying (vr);
+ return;
+ }
else if (code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
enum tree_code code,
tree expr_type, tree op0, tree op1)
{
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
enum tree_code code, tree type,
value_range_t *vr0_, tree op0_type)
{
- value_range_t vr0 = *vr0_;
+ value_range_t vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
/* VRP only operates on integral and pointer types. */
if (!(INTEGRAL_TYPE_P (op0_type)
return;
}
+ /* Handle operations that we express in terms of others. */
+ if (code == PAREN_EXPR)
+ {
+ /* PAREN_EXPR is a simple copy. */
+ copy_value_range (vr, &vr0);
+ return;
+ }
+ else if (code == NEGATE_EXPR)
+ {
+ /* -X is simply 0 - X, so re-use existing code that also handles
+ anti-ranges fine. */
+ value_range_t zero = VR_INITIALIZER;
+ set_value_range_to_value (&zero, build_int_cst (type, 0), NULL);
+ extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0);
+ return;
+ }
+ else if (code == BIT_NOT_EXPR)
+ {
+ /* ~X is simply -1 - X, so re-use existing code that also handles
+ anti-ranges fine. */
+ value_range_t minusone = VR_INITIALIZER;
+ set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL);
+ extract_range_from_binary_expr_1 (vr, MINUS_EXPR,
+ type, &minusone, &vr0);
+ return;
+ }
+
+ /* Now canonicalize anti-ranges to ranges when they are not symbolic
+ and express op ~[] as (op []') U (op []''). */
+ if (vr0.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
+ {
+ extract_range_from_unary_expr_1 (vr, code, type, &vrtem0, op0_type);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_unary_expr_1 (&vrres, code, type,
+ &vrtem1, op0_type);
+ vrp_meet (vr, &vrres);
+ }
+ return;
+ }
+
if (CONVERT_EXPR_CODE_P (code))
{
tree inner_type = op0_type;
set_value_range_to_varying (vr);
return;
}
- else if (code == NEGATE_EXPR)
- {
- /* -X is simply 0 - X, so re-use existing code that also handles
- anti-ranges fine. */
- value_range_t zero = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- set_value_range_to_value (&zero, build_int_cst (type, 0), NULL);
- extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0);
- return;
- }
else if (code == ABS_EXPR)
{
tree min, max;
set_value_range (vr, vr0.type, min, max, NULL);
return;
}
- else if (code == BIT_NOT_EXPR)
- {
- /* ~X is simply -1 - X, so re-use existing code that also handles
- anti-ranges fine. */
- value_range_t minusone = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL);
- extract_range_from_binary_expr_1 (vr, MINUS_EXPR,
- type, &minusone, &vr0);
- return;
- }
- else if (code == PAREN_EXPR)
- {
- copy_value_range (vr, &vr0);
- return;
- }
/* For unhandled operations fall back to varying. */
set_value_range_to_varying (vr);
extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
tree type, tree op0)
{
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr0 = VR_INITIALIZER;
/* Get value ranges for the operand. For constant operands, create
a new value range with the operand to simplify processing. */
extract_range_from_cond_expr (value_range_t *vr, gimple stmt)
{
tree op0, op1;
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
set_value_range_to_varying (&vr1);
/* The resulting value range is the union of the operand ranges */
- vrp_meet (&vr0, &vr1);
copy_value_range (vr, &vr0);
+ vrp_meet (vr, &vr1);
}
{
double_int nit;
- if (estimated_loop_iterations (loop, true, &nit))
+ /* We are only entering here for loop header PHI nodes, so using
+ the number of latch executions is the correct thing to use. */
+ if (max_loop_iterations (loop, &nit))
{
- value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t maxvr = VR_INITIALIZER;
double_int dtmp;
bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
int overflow = 0;
return true;
}
+/* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
+ (otherwise return VAL). VAL and MASK must be zero-extended for
+ precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
+ (to transform signed values into unsigned) and at the end xor
+ SGNBIT back. */
+
+static double_int
+masked_increment (double_int val, double_int mask, double_int sgnbit,
+ unsigned int prec)
+{
+ double_int bit = double_int_one, res;
+ unsigned int i;
+
+ val = double_int_xor (val, sgnbit);
+ for (i = 0; i < prec; i++, bit = double_int_add (bit, bit))
+ {
+ res = mask;
+ if (double_int_zero_p (double_int_and (res, bit)))
+ continue;
+ res = double_int_sub (bit, double_int_one);
+ res = double_int_and_not (double_int_add (val, bit), res);
+ res = double_int_and (res, mask);
+ if (double_int_ucmp (res, val) > 0)
+ return double_int_xor (res, sgnbit);
+ }
+ return double_int_xor (val, sgnbit);
+}
+
/* Try to register an edge assertion for SSA name NAME on edge E for
the condition COND contributing to the conditional jump pointed to by BSI.
Invert the condition COND if INVERT is true.
}
}
- /* Similarly add asserts for NAME == CST and NAME being defined as
- NAME = NAME2 >> CST2. */
if (TREE_CODE_CLASS (comp_code) == tcc_comparison
&& TREE_CODE (val) == INTEGER_CST)
{
gimple def_stmt = SSA_NAME_DEF_STMT (name);
- tree name2 = NULL_TREE, cst2 = NULL_TREE;
+ tree name2 = NULL_TREE, names[2], cst2 = NULL_TREE;
tree val2 = NULL_TREE;
- unsigned HOST_WIDE_INT mask[2] = { 0, 0 };
+ double_int mask = double_int_zero;
+ unsigned int prec = TYPE_PRECISION (TREE_TYPE (val));
+
+ /* Add asserts for NAME cmp CST and NAME being defined
+ as NAME = (int) NAME2. */
+ if (!TYPE_UNSIGNED (TREE_TYPE (val))
+ && (comp_code == LE_EXPR || comp_code == LT_EXPR
+ || comp_code == GT_EXPR || comp_code == GE_EXPR)
+ && gimple_assign_cast_p (def_stmt))
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && TYPE_UNSIGNED (TREE_TYPE (name2))
+ && prec == TYPE_PRECISION (TREE_TYPE (name2))
+ && (comp_code == LE_EXPR || comp_code == GT_EXPR
+ || !tree_int_cst_equal (val,
+ TYPE_MIN_VALUE (TREE_TYPE (val))))
+ && live_on_edge (e, name2)
+ && !has_single_use (name2))
+ {
+ tree tmp, cst;
+ enum tree_code new_comp_code = comp_code;
+
+ cst = fold_convert (TREE_TYPE (name2),
+ TYPE_MIN_VALUE (TREE_TYPE (val)));
+ /* Build an expression for the range test. */
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name2), name2, cst);
+ cst = fold_build2 (PLUS_EXPR, TREE_TYPE (name2), cst,
+ fold_convert (TREE_TYPE (name2), val));
+ if (comp_code == LT_EXPR || comp_code == GE_EXPR)
+ {
+ new_comp_code = comp_code == LT_EXPR ? LE_EXPR : GT_EXPR;
+ cst = fold_build2 (MINUS_EXPR, TREE_TYPE (name2), cst,
+ build_int_cst (TREE_TYPE (name2), 1));
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name2, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name2, tmp, new_comp_code, cst, NULL,
+ e, bsi);
+
+ retval = true;
+ }
+ }
- /* Extract CST2 from the right shift. */
+ /* Add asserts for NAME cmp CST and NAME being defined as
+ NAME = NAME2 >> CST2.
+
+ Extract CST2 from the right shift. */
if (is_gimple_assign (def_stmt)
&& gimple_assign_rhs_code (def_stmt) == RSHIFT_EXPR)
{
cst2 = gimple_assign_rhs2 (def_stmt);
if (TREE_CODE (name2) == SSA_NAME
&& host_integerp (cst2, 1)
- && (unsigned HOST_WIDE_INT) tree_low_cst (cst2, 1)
- < 2 * HOST_BITS_PER_WIDE_INT
&& INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && IN_RANGE (tree_low_cst (cst2, 1), 1, prec - 1)
+ && prec <= HOST_BITS_PER_DOUBLE_INT
+ && prec == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (val)))
&& live_on_edge (e, name2)
&& !has_single_use (name2))
{
- if ((unsigned HOST_WIDE_INT) tree_low_cst (cst2, 1)
- < HOST_BITS_PER_WIDE_INT)
- mask[0] = ((unsigned HOST_WIDE_INT) 1
- << tree_low_cst (cst2, 1)) - 1;
- else
- {
- mask[1] = ((unsigned HOST_WIDE_INT) 1
- << (tree_low_cst (cst2, 1)
- - HOST_BITS_PER_WIDE_INT)) - 1;
- mask[0] = -1;
- }
+ mask = double_int_mask (tree_low_cst (cst2, 1));
val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2);
}
}
-
if (val2 != NULL_TREE
&& TREE_CODE (val2) == INTEGER_CST
&& simple_cst_equal (fold_build2 (RSHIFT_EXPR,
{
if (!TYPE_UNSIGNED (TREE_TYPE (val)))
{
- unsigned int prec = TYPE_PRECISION (TREE_TYPE (val));
tree type = build_nonstandard_integer_type (prec, 1);
tmp = build1 (NOP_EXPR, type, name2);
val2 = fold_convert (type, val2);
}
tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), tmp, val2);
- new_val = build_int_cst_wide (TREE_TYPE (tmp), mask[0], mask[1]);
+ new_val = double_int_to_tree (TREE_TYPE (tmp), mask);
new_comp_code = comp_code == EQ_EXPR ? LE_EXPR : GT_EXPR;
}
else if (comp_code == LT_EXPR || comp_code == GE_EXPR)
new_val = val2;
else
{
- new_val = build_int_cst_wide (TREE_TYPE (val2),
- mask[0], mask[1]);
- new_val = fold_binary (BIT_IOR_EXPR, TREE_TYPE (val2),
- val2, new_val);
+ double_int maxval
+ = double_int_max_value (prec, TYPE_UNSIGNED (TREE_TYPE (val)));
+ mask = double_int_ior (tree_to_double_int (val2), mask);
+ if (double_int_equal_p (mask, maxval))
+ new_val = NULL_TREE;
+ else
+ new_val = double_int_to_tree (TREE_TYPE (val2), mask);
}
- if (dump_file)
+ if (new_val)
{
- fprintf (dump_file, "Adding assert for ");
- print_generic_expr (dump_file, name2, 0);
- fprintf (dump_file, " from ");
- print_generic_expr (dump_file, tmp, 0);
- fprintf (dump_file, "\n");
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name2, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name2, tmp, new_comp_code, new_val,
+ NULL, e, bsi);
+ retval = true;
}
+ }
- register_new_assert_for (name2, tmp, new_comp_code, new_val,
- NULL, e, bsi);
- retval = true;
+ /* Add asserts for NAME cmp CST and NAME being defined as
+ NAME = NAME2 & CST2.
+
+ Extract CST2 from the and. */
+ names[0] = NULL_TREE;
+ names[1] = NULL_TREE;
+ cst2 = NULL_TREE;
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ cst2 = gimple_assign_rhs2 (def_stmt);
+ if (TREE_CODE (name2) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && TREE_CODE (cst2) == INTEGER_CST
+ && !integer_zerop (cst2)
+ && prec <= HOST_BITS_PER_DOUBLE_INT
+ && (prec > 1
+ || TYPE_UNSIGNED (TREE_TYPE (val))))
+ {
+ gimple def_stmt2 = SSA_NAME_DEF_STMT (name2);
+ if (gimple_assign_cast_p (def_stmt2))
+ {
+ names[1] = gimple_assign_rhs1 (def_stmt2);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2))
+ || !INTEGRAL_TYPE_P (TREE_TYPE (names[1]))
+ || (TYPE_PRECISION (TREE_TYPE (name2))
+ != TYPE_PRECISION (TREE_TYPE (names[1])))
+ || !live_on_edge (e, names[1])
+ || has_single_use (names[1]))
+ names[1] = NULL_TREE;
+ }
+ if (live_on_edge (e, name2)
+ && !has_single_use (name2))
+ names[0] = name2;
+ }
+ }
+ if (names[0] || names[1])
+ {
+ double_int minv, maxv = double_int_zero, valv, cst2v;
+ double_int tem, sgnbit;
+ bool valid_p = false, valn = false, cst2n = false;
+ enum tree_code ccode = comp_code;
+
+ valv = double_int_zext (tree_to_double_int (val), prec);
+ cst2v = double_int_zext (tree_to_double_int (cst2), prec);
+ if (!TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ valn = double_int_negative_p (double_int_sext (valv, prec));
+ cst2n = double_int_negative_p (double_int_sext (cst2v, prec));
+ }
+ /* If CST2 doesn't have most significant bit set,
+ but VAL is negative, we have comparison like
+ if ((x & 0x123) > -4) (always true). Just give up. */
+ if (!cst2n && valn)
+ ccode = ERROR_MARK;
+ if (cst2n)
+ sgnbit = double_int_zext (double_int_lshift (double_int_one,
+ prec - 1, prec,
+ false), prec);
+ else
+ sgnbit = double_int_zero;
+ minv = double_int_and (valv, cst2v);
+ switch (ccode)
+ {
+ case EQ_EXPR:
+ /* Minimum unsigned value for equality is VAL & CST2
+ (should be equal to VAL, otherwise we probably should
+ have folded the comparison into false) and
+ maximum unsigned value is VAL | ~CST2. */
+ maxv = double_int_ior (valv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ valid_p = true;
+ break;
+ case NE_EXPR:
+ tem = double_int_ior (valv, double_int_not (cst2v));
+ tem = double_int_zext (tem, prec);
+ /* If VAL is 0, handle (X & CST2) != 0 as (X & CST2) > 0U. */
+ if (double_int_zero_p (valv))
+ {
+ cst2n = false;
+ sgnbit = double_int_zero;
+ goto gt_expr;
+ }
+ /* If (VAL | ~CST2) is all ones, handle it as
+ (X & CST2) < VAL. */
+ if (double_int_equal_p (tem, double_int_mask (prec)))
+ {
+ cst2n = false;
+ valn = false;
+ sgnbit = double_int_zero;
+ goto lt_expr;
+ }
+ if (!cst2n
+ && double_int_negative_p (double_int_sext (cst2v, prec)))
+ sgnbit = double_int_zext (double_int_lshift (double_int_one,
+ prec - 1, prec,
+ false), prec);
+ if (!double_int_zero_p (sgnbit))
+ {
+ if (double_int_equal_p (valv, sgnbit))
+ {
+ cst2n = true;
+ valn = true;
+ goto gt_expr;
+ }
+ if (double_int_equal_p (tem, double_int_mask (prec - 1)))
+ {
+ cst2n = true;
+ goto lt_expr;
+ }
+ if (!cst2n)
+ sgnbit = double_int_zero;
+ }
+ break;
+ case GE_EXPR:
+ /* Minimum unsigned value for >= if (VAL & CST2) == VAL
+ is VAL and maximum unsigned value is ~0. For signed
+ comparison, if CST2 doesn't have most significant bit
+ set, handle it similarly. If CST2 has MSB set,
+ the minimum is the same, and maximum is ~0U/2. */
+ if (!double_int_equal_p (minv, valv))
+ {
+ /* If (VAL & CST2) != VAL, X & CST2 can't be equal to
+ VAL. */
+ minv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (minv, valv))
+ break;
+ }
+ maxv = double_int_mask (prec - (cst2n ? 1 : 0));
+ valid_p = true;
+ break;
+ case GT_EXPR:
+ gt_expr:
+ /* Find out smallest MINV where MINV > VAL
+ && (MINV & CST2) == MINV, if any. If VAL is signed and
+ CST2 has MSB set, compute it biased by 1 << (prec - 1). */
+ minv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (minv, valv))
+ break;
+ maxv = double_int_mask (prec - (cst2n ? 1 : 0));
+ valid_p = true;
+ break;
+ case LE_EXPR:
+ /* Minimum unsigned value for <= is 0 and maximum
+ unsigned value is VAL | ~CST2 if (VAL & CST2) == VAL.
+ Otherwise, find smallest VAL2 where VAL2 > VAL
+ && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
+ as maximum.
+ For signed comparison, if CST2 doesn't have most
+ significant bit set, handle it similarly. If CST2 has
+ MSB set, the maximum is the same and minimum is INT_MIN. */
+ if (double_int_equal_p (minv, valv))
+ maxv = valv;
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (maxv, valv))
+ break;
+ maxv = double_int_sub (maxv, double_int_one);
+ }
+ maxv = double_int_ior (maxv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ minv = sgnbit;
+ valid_p = true;
+ break;
+ case LT_EXPR:
+ lt_expr:
+ /* Minimum unsigned value for < is 0 and maximum
+ unsigned value is (VAL-1) | ~CST2 if (VAL & CST2) == VAL.
+ Otherwise, find smallest VAL2 where VAL2 > VAL
+ && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
+ as maximum.
+ For signed comparison, if CST2 doesn't have most
+ significant bit set, handle it similarly. If CST2 has
+ MSB set, the maximum is the same and minimum is INT_MIN. */
+ if (double_int_equal_p (minv, valv))
+ {
+ if (double_int_equal_p (valv, sgnbit))
+ break;
+ maxv = valv;
+ }
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (maxv, valv))
+ break;
+ }
+ maxv = double_int_sub (maxv, double_int_one);
+ maxv = double_int_ior (maxv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ minv = sgnbit;
+ valid_p = true;
+ break;
+ default:
+ break;
+ }
+ if (valid_p
+ && !double_int_equal_p (double_int_zext (double_int_sub (maxv,
+ minv),
+ prec),
+ double_int_mask (prec)))
+ {
+ tree tmp, new_val, type;
+ int i;
+
+ for (i = 0; i < 2; i++)
+ if (names[i])
+ {
+ double_int maxv2 = maxv;
+ tmp = names[i];
+ type = TREE_TYPE (names[i]);
+ if (!TYPE_UNSIGNED (type))
+ {
+ type = build_nonstandard_integer_type (prec, 1);
+ tmp = build1 (NOP_EXPR, type, names[i]);
+ }
+ if (!double_int_zero_p (minv))
+ {
+ tmp = build2 (PLUS_EXPR, type, tmp,
+ double_int_to_tree (type,
+ double_int_neg (minv)));
+ maxv2 = double_int_sub (maxv, minv);
+ }
+ new_val = double_int_to_tree (type, maxv2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, names[i], 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (names[i], tmp, LE_EXPR,
+ new_val, NULL, e, bsi);
+ retval = true;
+ }
+ }
}
}
&& TYPE_MAX_VALUE (TREE_TYPE (lhs)))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
- value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ 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);
return SSA_PROP_VARYING;
}
+/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
+ { VR1TYPE, VR0MIN, VR0MAX } and store the result
+ in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
+ possible such range. The resulting range is not canonicalized. */
+
+static void
+intersect_ranges (enum value_range_type *vr0type,
+ tree *vr0min, tree *vr0max,
+ enum value_range_type vr1type,
+ tree vr1min, tree vr1max)
+{
+ bool mineq = operand_equal_p (*vr0min, vr1min, 0);
+ bool maxeq = operand_equal_p (*vr0max, vr1max, 0);
+
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (mineq && maxeq)
+ {
+ /* [( )] */
+ if (*vr0type == vr1type)
+ /* Nothing to do for equal ranges. */
+ ;
+ else if ((*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ || (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE))
+ {
+ /* For anti-range with range intersection the result is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (operand_less_p (*vr0max, vr1min) == 1
+ || operand_less_p (vr1max, *vr0min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, the result of the
+ intersect operation is the range for intersecting an
+ anti-range with a range or empty when intersecting two ranges.
+ For intersecting two anti-ranges simply choose vr0. */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Take VR0. */
+ }
+ }
+ else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
+ && (mineq || operand_less_p (*vr0min, vr1min) == 1))
+ {
+ /* [ ( ) ] or [( ) ] or [ ( )] */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* If both are ranges the result is the inner one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Choose the right gap if the left one is empty. */
+ if (mineq)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max, integer_one_node);
+ else
+ *vr0min = vr1max;
+ }
+ /* Choose the left gap if the right one is empty. */
+ else if (maxeq)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ integer_one_node);
+ else
+ *vr0max = vr1min;
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (*vr0min)
+ && vrp_val_is_max (*vr0max))
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ /* Else choose the range. */
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ /* If both are anti-ranges the result is the outer one. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
+ && (mineq || operand_less_p (vr1min, *vr0min) == 1))
+ {
+ /* ( [ ] ) or ([ ] ) or ( [ ]) */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ /* Choose the inner range. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* Choose the right gap if the left is empty. */
+ if (mineq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ integer_one_node);
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ /* Choose the left gap if the right is empty. */
+ else if (maxeq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ integer_one_node);
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (vr1min)
+ && vrp_val_is_max (vr1max))
+ ;
+ /* Else choose the range. */
+ else
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* If both are anti-ranges the result is the outer one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (vr1type == VR_ANTI_RANGE
+ && *vr0type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0))
+ && operand_less_p (*vr0min, vr1min) == 1)
+ {
+ /* [ ( ] ) or [ ]( ) */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ integer_one_node);
+ else
+ *vr0max = vr1min;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ integer_one_node);
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0))
+ && operand_less_p (vr1min, *vr0min) == 1)
+ {
+ /* ( [ ) ] or ( )[ ] */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ integer_one_node);
+ else
+ *vr0min = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ integer_one_node);
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ else
+ gcc_unreachable ();
+ }
+
+ /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
+ result for the intersection. That's always a conservative
+ correct estimate. */
+
+ return;
+}
+
+
+/* Intersect the two value-ranges *VR0 and *VR1 and store the result
+ in *VR0. This may not be the smallest possible such range. */
+
+static void
+vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1)
+{
+ value_range_t saved;
+
+ /* If either range is VR_VARYING the other one wins. */
+ if (vr1->type == VR_VARYING)
+ return;
+ if (vr0->type == VR_VARYING)
+ {
+ copy_value_range (vr0, vr1);
+ return;
+ }
+
+ /* When either range is VR_UNDEFINED the resulting range is
+ VR_UNDEFINED, too. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
+ if (vr1->type == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr0);
+ return;
+ }
+
+ /* Save the original vr0 so we can return it as conservative intersection
+ result when our worker turns things to varying. */
+ saved = *vr0;
+ intersect_ranges (&vr0->type, &vr0->min, &vr0->max,
+ vr1->type, vr1->min, vr1->max);
+ /* Make sure to canonicalize the result though as the inversion of a
+ VR_RANGE can still be a VR_RANGE. */
+ set_and_canonicalize_value_range (vr0, vr0->type,
+ vr0->min, vr0->max, vr0->equiv);
+ /* If that failed, use the saved original VR0. */
+ if (vr0->type == VR_VARYING)
+ {
+ *vr0 = saved;
+ return;
+ }
+ /* If the result is VR_UNDEFINED there is no need to mess with
+ the equivalencies. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
+
+ /* The resulting set of equivalences for range intersection is the union of
+ the two sets. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_ior_into (vr0->equiv, vr1->equiv);
+ else if (vr1->equiv && !vr0->equiv)
+ bitmap_copy (vr0->equiv, vr1->equiv);
+}
+
+static void
+vrp_intersect_ranges (value_range_t *vr0, value_range_t *vr1)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Intersecting\n ");
+ dump_value_range (dump_file, vr0);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, vr1);
+ fprintf (dump_file, "\n");
+ }
+ vrp_intersect_ranges_1 (vr0, vr1);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, vr0);
+ fprintf (dump_file, "\n");
+ }
+}
/* Meet operation for value ranges. Given two value ranges VR0 and
VR1, store in VR0 a range that contains both VR0 and VR1. This
{
if (vr0->type == VR_UNDEFINED)
{
- copy_value_range (vr0, vr1);
+ /* Drop equivalences. See PR53465. */
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, NULL);
return;
}
if (vr1->type == VR_UNDEFINED)
{
- /* Nothing to do. VR0 already has the resulting range. */
+ /* VR0 already has the resulting range, just drop equivalences.
+ See PR53465. */
+ if (vr0->equiv)
+ bitmap_clear (vr0->equiv);
return;
}
return;
}
- if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
+ if (vr0->type == vr1->type
+ && compare_values (vr0->min, vr1->min) == 0
+ && compare_values (vr0->max, vr1->max) == 0)
+ {
+ /* If the value-ranges are identical just insersect
+ their equivalencies. */
+ }
+ else if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
{
int cmp;
tree min, max;
- /* Compute the convex hull of the ranges. The lower limit of
- the new range is the minimum of the two ranges. If they
+ /* If the two ranges represent an anti-range produce a
+ VR_RANGE with swapped min/max and let the range canonicalization
+ fix things up. */
+ if (vrp_val_is_min (vr0->min) && !is_overflow_infinity (vr0->min)
+ && vrp_val_is_max (vr1->max) && !is_overflow_infinity (vr1->max)
+ && TREE_CODE (vr1->min) == INTEGER_CST
+ && TREE_CODE (vr0->max) == INTEGER_CST
+ && compare_values (vr0->max, vr1->min) == -1)
+ {
+ min = vr1->min;
+ max = vr0->max;
+ }
+ else if (vrp_val_is_min (vr1->min) && !is_overflow_infinity (vr1->min)
+ && vrp_val_is_max (vr0->max) && !is_overflow_infinity (vr0->max)
+ && TREE_CODE (vr1->max) == INTEGER_CST
+ && TREE_CODE (vr0->min) == INTEGER_CST
+ && compare_values (vr1->max, vr0->min) == -1)
+ {
+ max = vr1->max;
+ min = vr0->min;
+ }
+ /* Otherwise compute the convex hull of the ranges. The lower limit of
+ the new range is the minimum of the two ranges. If they
cannot be compared, then give up. */
- cmp = compare_values (vr0->min, vr1->min);
- if (cmp == 0 || cmp == 1)
- min = vr1->min;
- else if (cmp == -1)
- min = vr0->min;
- else
- goto give_up;
-
- /* Similarly, the upper limit of the new range is the maximum
- of the two ranges. If they cannot be compared, then
- give up. */
- cmp = compare_values (vr0->max, vr1->max);
- if (cmp == 0 || cmp == -1)
- max = vr1->max;
- else if (cmp == 1)
- max = vr0->max;
else
- goto give_up;
-
- /* Check for useless ranges. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (min))
- && ((vrp_val_is_min (min) || is_overflow_infinity (min))
- && (vrp_val_is_max (max) || is_overflow_infinity (max))))
- goto give_up;
-
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
-
- set_value_range (vr0, vr0->type, min, max, vr0->equiv);
- }
- else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
- {
- /* Two anti-ranges meet only if their complements intersect.
- Only handle the case of identical ranges. */
- if (compare_values (vr0->min, vr1->min) == 0
- && compare_values (vr0->max, vr1->max) == 0
- && compare_values (vr0->min, vr0->max) == 0)
{
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+ cmp = compare_values (vr0->min, vr1->min);
+ if (cmp == 0 || cmp == 1)
+ min = vr1->min;
+ else if (cmp == -1)
+ min = vr0->min;
+ else
+ goto give_up;
+
+ /* Similarly, the upper limit of the new range is the maximum
+ of the two ranges. If they cannot be compared, then
+ give up. */
+ cmp = compare_values (vr0->max, vr1->max);
+ if (cmp == 0 || cmp == -1)
+ max = vr1->max;
+ else if (cmp == 1)
+ max = vr0->max;
+ else
+ goto give_up;
+
+ /* Check for useless ranges. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (min))
+ && ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max))))
+ goto give_up;
}
- else
- goto give_up;
+
+ set_and_canonicalize_value_range (vr0, vr0->type, min, max, vr0->equiv);
}
else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
- /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
- only handle the case where the ranges have an empty intersection.
- The result of the meet operation is the anti-range. */
- if (!symbolic_range_p (vr0)
- && !symbolic_range_p (vr1)
- && !value_ranges_intersect_p (vr0, vr1))
- {
- /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
- set. We need to compute the intersection of the two
- equivalence sets. */
- if (vr1->type == VR_ANTI_RANGE)
- set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ if (symbolic_range_p (vr0)
+ || symbolic_range_p (vr1))
+ goto give_up;
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (operand_less_p (vr0->max, vr1->min) == 1
+ || operand_less_p (vr1->max, vr0->min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, result of the meet
+ operation is the anti-range or if both are anti-ranges
+ it covers all. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ goto give_up;
+ else if (vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ }
+ else if (operand_less_p (vr1->max, vr0->max) == 1
+ && operand_less_p (vr0->min, vr1->min) == 1)
+ {
+ /* [ ( ) ]
+ Arbitrarily choose the left or inner gap. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type, vr0->min,
+ int_const_binop (MINUS_EXPR, vr1->min, integer_one_node),
+ vr0->equiv);
+ else
+ goto give_up;
+ }
+ else if (operand_less_p (vr0->max, vr1->max) == 1
+ && operand_less_p (vr1->min, vr0->min) == 1)
+ {
+ /* ( [ ] )
+ Arbitrarily choose the left or inner gap. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ /* Nothing to do. */;
+ else if (vr1->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr1->type, vr1->min,
+ int_const_binop (MINUS_EXPR, vr0->min, integer_one_node),
+ vr0->equiv);
+ else
+ goto give_up;
+ }
+ else if (operand_less_p (vr1->min, vr0->max) == 1
+ && operand_less_p (vr0->max, vr1->max) == 1)
+ {
+ /* [ ( ] ) */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr0->type, vr1->min, vr0->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type, vr0->min,
+ int_const_binop (MINUS_EXPR, vr1->min, integer_one_node),
+ vr0->equiv);
+ else
+ set_and_canonicalize_value_range (vr0, vr1->type,
+ int_const_binop (PLUS_EXPR, vr0->max, integer_one_node),
+ vr1->max, vr0->equiv);
+ }
+ else if (operand_less_p (vr0->min, vr1->max) == 1
+ && operand_less_p (vr1->max, vr0->max) == 1)
+ {
+ /* ( [ ) ] */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr0->min, vr1->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type,
+ int_const_binop (PLUS_EXPR, vr1->max, integer_one_node),
+ vr0->max, vr0->equiv);
+ else
+ set_and_canonicalize_value_range (vr0, vr1->type, vr1->min,
+ int_const_binop (MINUS_EXPR, vr0->min, integer_one_node),
+ vr0->equiv);
}
else
goto give_up;
else
gcc_unreachable ();
+ /* The resulting set of equivalences is always the intersection of
+ the two sets. Above we always left the equivalency set of vr0 as-is. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_and_into (vr0->equiv, vr1->equiv);
+ else if (vr0->equiv && !vr1->equiv)
+ bitmap_clear (vr0->equiv);
+
return;
give_up:
size_t i;
tree lhs = PHI_RESULT (phi);
value_range_t *lhs_vr = get_value_range (lhs);
- value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr_result = VR_INITIALIZER;
+ bool first = true;
int edges, old_edges;
struct loop *l;
fprintf (dump_file, "\n");
}
- vrp_meet (&vr_result, &vr_arg);
+ if (first)
+ copy_value_range (&vr_result, &vr_arg);
+ else
+ vrp_meet (&vr_result, &vr_arg);
+ first = false;
if (vr_result.type == VR_VARYING)
break;
tree op0 = gimple_assign_rhs1 (stmt);
tree op1 = gimple_assign_rhs2 (stmt);
tree op = NULL_TREE;
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
double_int may_be_nonzero0, may_be_nonzero1;
double_int must_be_nonzero0, must_be_nonzero1;
double_int mask;
insert_range_assertions ();
- /* Estimate number of iterations - but do not use undefined behavior
- for this. We can't do this lazily as other functions may compute
- this using undefined behavior. */
- free_numbers_of_iterations_estimates ();
- estimate_numbers_of_iterations (false);
-
to_remove_edges = VEC_alloc (edge, heap, 10);
to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
threadedge_initialize_values ();
projects / gcc.git / blobdiff