}
// If the range of either op1 or op2 is undefined, set the result to
-// undefined and return TRUE.
+// varying and return TRUE. If the caller truely cares about a result,
+// they should pass in a varying if it has an undefined that it wants
+// treated as a varying.
inline bool
-empty_range_check (value_range &r,
- const value_range &op1, const value_range & op2)
+empty_range_varying (irange &r, tree type,
+ const irange &op1, const irange & op2)
{
if (op1.undefined_p () || op2.undefined_p ())
{
- r.set_undefined ();
+ r.set_varying (type);
return true;
}
else
// the appropriate range.
static inline bool
-undefined_shift_range_check (value_range &r, tree type, const value_range op)
+undefined_shift_range_check (irange &r, tree type, const irange &op)
{
if (op.undefined_p ())
{
- r = value_range ();
+ r.set_undefined ();
return true;
}
|| wi::ge_p (op.upper_bound (),
TYPE_PRECISION (type), TYPE_SIGN (op.type ())))
{
- r = value_range (type);
+ r.set_varying (type);
return true;
}
return false;
// Default wide_int fold operation returns [MIN, MAX].
void
-range_operator::wi_fold (value_range &r, tree type,
+range_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb ATTRIBUTE_UNUSED,
const wide_int &lh_ub ATTRIBUTE_UNUSED,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
{
- gcc_checking_assert (value_range::supports_type_p (type));
- r = value_range (type);
+ gcc_checking_assert (irange::supports_type_p (type));
+ r.set_varying (type);
}
// The default for fold is to break all ranges into sub-ranges and
// invoke the wi_fold method on each sub-range pair.
bool
-range_operator::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+range_operator::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- gcc_checking_assert (value_range::supports_type_p (type));
- if (empty_range_check (r, lh, rh))
+ gcc_checking_assert (irange::supports_type_p (type));
+ if (empty_range_varying (r, type, lh, rh))
return true;
- value_range tmp;
+ unsigned num_lh = lh.num_pairs ();
+ unsigned num_rh = rh.num_pairs ();
+
+ // If both ranges are single pairs, fold directly into the result range.
+ if (num_lh == 1 && num_rh == 1)
+ {
+ wi_fold (r, type, lh.lower_bound (0), lh.upper_bound (0),
+ rh.lower_bound (0), rh.upper_bound (0));
+ return true;
+ }
+
+ widest_irange tmp;
r.set_undefined ();
- for (unsigned x = 0; x < lh.num_pairs (); ++x)
- for (unsigned y = 0; y < rh.num_pairs (); ++y)
+ for (unsigned x = 0; x < num_lh; ++x)
+ for (unsigned y = 0; y < num_rh; ++y)
{
wide_int lh_lb = lh.lower_bound (x);
wide_int lh_ub = lh.upper_bound (x);
// The default for op1_range is to return false.
bool
-range_operator::op1_range (value_range &r ATTRIBUTE_UNUSED,
+range_operator::op1_range (irange &r ATTRIBUTE_UNUSED,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs ATTRIBUTE_UNUSED,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+ const irange &lhs ATTRIBUTE_UNUSED,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
return false;
}
// The default for op2_range is to return false.
bool
-range_operator::op2_range (value_range &r ATTRIBUTE_UNUSED,
+range_operator::op2_range (irange &r ATTRIBUTE_UNUSED,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs ATTRIBUTE_UNUSED,
- const value_range &op1 ATTRIBUTE_UNUSED) const
+ const irange &lhs ATTRIBUTE_UNUSED,
+ const irange &op1 ATTRIBUTE_UNUSED) const
{
return false;
}
// to have overflowed (or underflowed).
static void
-value_range_from_overflowed_bounds (value_range &r, tree type,
+value_range_from_overflowed_bounds (irange &r, tree type,
const wide_int &wmin,
const wide_int &wmax)
{
// Likewise if the anti-range bounds are outside of the types
// values.
if (covers || wi::cmp (tmin, tmax, sgn) > 0)
- r = value_range (type);
+ r.set_varying (type);
else
- r = value_range (type, tmin, tmax, VR_ANTI_RANGE);
+ {
+ tree tree_min = wide_int_to_tree (type, tmin);
+ tree tree_max = wide_int_to_tree (type, tmax);
+ r.set (tree_min, tree_max, VR_ANTI_RANGE);
+ }
}
// Create and return a range from a pair of wide-ints. MIN_OVF and
// calculating WMIN and WMAX respectively.
static void
-value_range_with_overflow (value_range &r, tree type,
+value_range_with_overflow (irange &r, tree type,
const wide_int &wmin, const wide_int &wmax,
wi::overflow_type min_ovf = wi::OVF_NONE,
wi::overflow_type max_ovf = wi::OVF_NONE)
// values.
if (prec == 1 && wi::ne_p (wmax, wmin))
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
// If the limits are swapped, we wrapped around and cover
// the entire range.
if (wi::gt_p (tmin, tmax, sgn))
- r = value_range (type);
+ r.set_varying (type);
else
// No overflow or both overflow or underflow. The range
// kind stays normal.
- r = value_range (type, tmin, tmax);
+ r.set (wide_int_to_tree (type, tmin),
+ wide_int_to_tree (type, tmax));
return;
}
value_range_from_overflowed_bounds (r, type, wmin, wmax);
else
// Other underflow and/or overflow, drop to VR_VARYING.
- r = value_range (type);
+ r.set_varying (type);
}
else
{
else
new_ub = wmax;
- r = value_range (type, new_lb, new_ub);
+ r.set (wide_int_to_tree (type, new_lb),
+ wide_int_to_tree (type, new_ub));
}
}
// [10,5] into [MIN,5][10,MAX].
static inline void
-create_possibly_reversed_range (value_range &r, tree type,
+create_possibly_reversed_range (irange &r, tree type,
const wide_int &new_lb, const wide_int &new_ub)
{
signop s = TYPE_SIGN (type);
if (wi::gt_p (new_lb, new_ub, s))
value_range_from_overflowed_bounds (r, type, new_lb, new_ub);
else
- // Otherwise its just a normal range.
- r = value_range (type, new_lb, new_ub);
+ // Otherwise it's just a normal range.
+ r.set (wide_int_to_tree (type, new_lb), wide_int_to_tree (type, new_ub));
}
-// Return a value_range instance that is a boolean TRUE.
+// Return an irange instance that is a boolean TRUE.
-static inline value_range
+static inline int_range<1>
range_true (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::one (prec), wi::one (prec));
+ return int_range<1> (type, wi::one (prec), wi::one (prec));
}
-// Return a value_range instance that is a boolean FALSE.
+// Return an irange instance that is a boolean FALSE.
-static inline value_range
+static inline int_range<1>
range_false (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::zero (prec), wi::zero (prec));
+ return int_range<1> (type, wi::zero (prec), wi::zero (prec));
}
-// Return a value_range that covers both true and false.
+// Return an irange that covers both true and false.
-static inline value_range
+static inline int_range<1>
range_true_and_false (tree type)
{
unsigned prec = TYPE_PRECISION (type);
- return value_range (type, wi::zero (prec), wi::one (prec));
+ return int_range<1> (type, wi::zero (prec), wi::one (prec));
}
enum bool_range_state { BRS_FALSE, BRS_TRUE, BRS_EMPTY, BRS_FULL };
// the bool range.
static bool_range_state
-get_bool_state (value_range &r, const value_range &lhs, tree val_type)
+get_bool_state (irange &r, const irange &lhs, tree val_type)
{
// If there is no result, then this is unexecutable.
if (lhs.undefined_p ())
return BRS_EMPTY;
}
- // If the bounds aren't the same, then it's not a constant.
- if (!wi::eq_p (lhs.upper_bound (), lhs.lower_bound ()))
+ if (lhs.zero_p ())
+ return BRS_FALSE;
+
+ // For TRUE, we can't just test for [1,1] because Ada can have
+ // multi-bit booleans, and TRUE values can be: [1, MAX], ~[0], etc.
+ if (lhs.contains_p (build_zero_cst (lhs.type ())))
{
r.set_varying (val_type);
return BRS_FULL;
}
-
- if (lhs.zero_p ())
- return BRS_FALSE;
-
return BRS_TRUE;
}
class operator_equal : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &val) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &val) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &val) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &val) const;
} op_equal;
bool
-operator_equal::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_equal::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
// We can be sure the values are always equal or not if both ranges
}
bool
-operator_equal::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_equal::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_equal::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_equal::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_equal::op1_range (r, type, lhs, op1);
}
class operator_not_equal : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_not_equal;
bool
-operator_not_equal::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_not_equal::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
// We can be sure the values are always equal or not if both ranges
}
bool
-operator_not_equal::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_not_equal::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
bool
-operator_not_equal::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_not_equal::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_not_equal::op1_range (r, type, lhs, op1);
}
// (X < VAL) produces the range of [MIN, VAL - 1].
static void
-build_lt (value_range &r, tree type, const wide_int &val)
+build_lt (irange &r, tree type, const wide_int &val)
{
wi::overflow_type ov;
wide_int lim = wi::sub (val, 1, TYPE_SIGN (type), &ov);
if (ov)
r.set_undefined ();
else
- r = value_range (type, min_limit (type), lim);
+ r = int_range<1> (type, min_limit (type), lim);
}
// (X <= VAL) produces the range of [MIN, VAL].
static void
-build_le (value_range &r, tree type, const wide_int &val)
+build_le (irange &r, tree type, const wide_int &val)
{
- r = value_range (type, min_limit (type), val);
+ r = int_range<1> (type, min_limit (type), val);
}
// (X > VAL) produces the range of [VAL + 1, MAX].
static void
-build_gt (value_range &r, tree type, const wide_int &val)
+build_gt (irange &r, tree type, const wide_int &val)
{
wi::overflow_type ov;
wide_int lim = wi::add (val, 1, TYPE_SIGN (type), &ov);
if (ov)
r.set_undefined ();
else
- r = value_range (type, lim, max_limit (type));
+ r = int_range<1> (type, lim, max_limit (type));
}
// (X >= val) produces the range of [VAL, MAX].
static void
-build_ge (value_range &r, tree type, const wide_int &val)
+build_ge (irange &r, tree type, const wide_int &val)
{
- r = value_range (type, val, max_limit (type));
+ r = int_range<1> (type, val, max_limit (type));
}
class operator_lt : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_lt;
bool
-operator_lt::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_lt::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
}
bool
-operator_lt::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_lt::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_lt::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_lt::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
class operator_le : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_le;
bool
-operator_le::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_le::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
}
bool
-operator_le::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_le::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_le::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_le::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
class operator_gt : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_gt;
bool
-operator_gt::fold_range (value_range &r, tree type,
- const value_range &op1, const value_range &op2) const
+operator_gt::fold_range (irange &r, tree type,
+ const irange &op1, const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
}
bool
-operator_gt::op1_range (value_range &r, tree type,
- const value_range &lhs, const value_range &op2) const
+operator_gt::op1_range (irange &r, tree type,
+ const irange &lhs, const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_gt::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_gt::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
class operator_ge : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_ge;
bool
-operator_ge::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_ge::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
- if (empty_range_check (r, op1, op2))
+ if (empty_range_varying (r, type, op1, op2))
return true;
signop sign = TYPE_SIGN (op1.type ());
}
bool
-operator_ge::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_ge::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_ge::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_ge::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
switch (get_bool_state (r, lhs, type))
{
class operator_plus : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_plus;
void
-operator_plus::wi_fold (value_range &r, tree type,
+operator_plus::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
}
bool
-operator_plus::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_plus::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op2);
}
bool
-operator_plus::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_plus::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, lhs, op1);
}
class operator_minus : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_minus;
void
-operator_minus::wi_fold (value_range &r, tree type,
+operator_minus::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
}
bool
-operator_minus::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_minus::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return range_op_handler (PLUS_EXPR, type)->fold_range (r, type, lhs, op2);
}
bool
-operator_minus::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_minus::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return fold_range (r, type, op1, lhs);
}
class operator_min : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_min;
void
-operator_min::wi_fold (value_range &r, tree type,
+operator_min::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
class operator_max : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_max;
void
-operator_max::wi_fold (value_range &r, tree type,
+operator_max::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
const wide_int &) const = 0;
// Calculate the cross product of two sets of sub-ranges and return it.
- void wi_cross_product (value_range &r, tree type,
+ void wi_cross_product (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
// figure the smallest and largest values to form the new range.
void
-cross_product_operator::wi_cross_product (value_range &r, tree type,
+cross_product_operator::wi_cross_product (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
{
wide_int cp1, cp2, cp3, cp4;
// Default to varying.
- r = value_range (type);
+ r.set_varying (type);
// Compute the 4 cross operations, bailing if we get an overflow we
// can't handle.
class operator_mult : public cross_product_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
virtual bool wi_op_overflows (wide_int &res, tree type,
const wide_int &w0, const wide_int &w1) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_mult;
+bool
+operator_mult::op1_range (irange &r, tree type,
+ const irange &lhs, const irange &op2) const
+{
+ tree offset;
+
+ // We can't solve 0 = OP1 * N by dividing by N with a wrapping type.
+ // For example: For 0 = OP1 * 2, OP1 could be 0, or MAXINT, whereas
+ // for 4 = OP1 * 2, OP1 could be 2 or 130 (unsigned 8-bit)
+ if (TYPE_OVERFLOW_WRAPS (type))
+ return false;
+
+ if (op2.singleton_p (&offset) && !integer_zerop (offset))
+ return range_op_handler (TRUNC_DIV_EXPR, type)->fold_range (r, type,
+ lhs, op2);
+ return false;
+}
+
+bool
+operator_mult::op2_range (irange &r, tree type,
+ const irange &lhs, const irange &op1) const
+{
+ return operator_mult::op1_range (r, type, lhs, op1);
+}
+
bool
operator_mult::wi_op_overflows (wide_int &res, tree type,
const wide_int &w0, const wide_int &w1) const
}
void
-operator_mult::wi_fold (value_range &r, tree type,
+operator_mult::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
prod2 = prod3 - prod0;
if (wi::geu_p (prod2, sizem1))
// The range covers all values.
- r = value_range (type);
+ r.set_varying (type);
else
{
wide_int new_lb = wide_int::from (prod0, prec, sign);
{
public:
operator_div (enum tree_code c) { code = c; }
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
}
void
-operator_div::wi_fold (value_range &r, tree type,
+operator_div::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
// If we know we will divide by zero, return undefined.
if (rh_lb == 0 && rh_ub == 0)
{
- r = value_range ();
+ r.set_undefined ();
return;
}
// If flag_non_call_exceptions, we must not eliminate a division by zero.
if (cfun->can_throw_non_call_exceptions)
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
// If we're definitely dividing by zero, there's nothing to do.
if (wi_zero_p (type, divisor_min, divisor_max))
{
- r = value_range ();
+ r.set_undefined ();
return;
}
wi_cross_product (r, type, dividend_min, dividend_max,
divisor_min, wi::minus_one (prec));
else
- r = value_range ();
+ r.set_undefined ();
// Then divide by the non-zero positive numbers, if any.
if (wi::gt_p (divisor_max, wi::zero (prec), sign))
{
- value_range tmp;
+ widest_irange tmp;
wi_cross_product (tmp, type, dividend_min, dividend_max,
wi::one (prec), divisor_max);
r.union_ (tmp);
{
public:
operator_exact_divide () : operator_div (TRUNC_DIV_EXPR) { }
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_exact_div;
bool
-operator_exact_divide::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_exact_divide::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
tree offset;
// [2, 4] = op1 / [3,3] since its exact divide, no need to worry about
class operator_lshift : public cross_product_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
-
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
virtual bool wi_op_overflows (wide_int &res,
} op_lshift;
bool
-operator_lshift::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_lshift::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
if (undefined_shift_range_check (r, type, op2))
return true;
{
unsigned shift = op2.lower_bound ().to_uhwi ();
wide_int tmp = wi::set_bit_in_zero (shift, TYPE_PRECISION (type));
- value_range mult (type, tmp, tmp);
+ int_range<1> mult (type, tmp, tmp);
// Force wrapping multiplication.
bool saved_flag_wrapv = flag_wrapv;
bool saved_flag_wrapv_pointer = flag_wrapv_pointer;
flag_wrapv = 1;
flag_wrapv_pointer = 1;
- bool b = range_op_handler (MULT_EXPR, type)->fold_range (r, type, op1,
- mult);
+ bool b = op_mult.fold_range (r, type, op1, mult);
flag_wrapv = saved_flag_wrapv;
flag_wrapv_pointer = saved_flag_wrapv_pointer;
return b;
}
void
-operator_lshift::wi_fold (value_range &r, tree type,
+operator_lshift::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
if (in_bounds)
wi_cross_product (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
else
- r = value_range (type);
+ r.set_varying (type);
}
bool
return false;
}
+bool
+operator_lshift::op1_range (irange &r,
+ tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ tree shift_amount;
+ if (op2.singleton_p (&shift_amount))
+ {
+ int_range<1> shifted (shift_amount, shift_amount), ub, lb;
+ const range_operator *rshift_op = range_op_handler (RSHIFT_EXPR, type);
+ rshift_op->fold_range (ub, type, lhs, shifted);
+ if (TYPE_UNSIGNED (type))
+ {
+ r = ub;
+ return true;
+ }
+ // For signed types, we can't just do an arithmetic rshift,
+ // because that will propagate the sign bit.
+ //
+ // LHS
+ // 1110 = OP1 << 1
+ //
+ // Assuming a 4-bit signed integer, a right shift will result in
+ // OP1=1111, but OP1 could have also been 0111. What we want is
+ // a range from 0111 to 1111. That is, a range from the logical
+ // rshift (0111) to the arithmetic rshift (1111).
+ //
+ // Perform a logical rshift by doing the rshift as unsigned.
+ tree unsigned_type = unsigned_type_for (type);
+ widest_irange unsigned_lhs = lhs;
+ range_cast (unsigned_lhs, unsigned_type);
+ rshift_op = range_op_handler (RSHIFT_EXPR, unsigned_type);
+ rshift_op->fold_range (lb, unsigned_type, unsigned_lhs, shifted);
+ range_cast (lb, type);
+ r = lb;
+ r.union_ (ub);
+ return true;
+ }
+ return false;
+}
+
class operator_rshift : public cross_product_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
tree type,
const wide_int &w0,
const wide_int &w1) const;
+ virtual bool op1_range (irange &, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_rshift;
+bool
+operator_rshift::op1_range (irange &r,
+ tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ tree shift;
+ if (op2.singleton_p (&shift))
+ {
+ // Folding the original operation may discard some impossible
+ // ranges from the LHS.
+ widest_irange lhs_refined;
+ op_rshift.fold_range (lhs_refined, type, int_range<1> (type), op2);
+ lhs_refined.intersect (lhs);
+ if (lhs_refined.undefined_p ())
+ {
+ r.set_undefined ();
+ return true;
+ }
+ widest_irange shift_range (shift, shift);
+ widest_irange lb, ub;
+ op_lshift.fold_range (lb, type, lhs_refined, shift_range);
+ // LHS
+ // 0000 0111 = OP1 >> 3
+ //
+ // OP1 is anything from 0011 1000 to 0011 1111. That is, a
+ // range from LHS<<3 plus a mask of the 3 bits we shifted on the
+ // right hand side (0x07).
+ tree mask = fold_build1 (BIT_NOT_EXPR, type,
+ fold_build2 (LSHIFT_EXPR, type,
+ build_minus_one_cst (type),
+ shift));
+ widest_irange mask_range (build_zero_cst (type), mask);
+ op_plus.fold_range (ub, type, lb, mask_range);
+ r = lb;
+ r.union_ (ub);
+ if (!lhs_refined.contains_p (build_zero_cst (type)))
+ {
+ mask_range.invert ();
+ r.intersect (mask_range);
+ }
+ return true;
+ }
+ return false;
+}
+
bool
operator_rshift::wi_op_overflows (wide_int &res,
tree type,
}
bool
-operator_rshift::fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const
+operator_rshift::fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const
{
// Invoke the generic fold routine if not undefined..
if (undefined_shift_range_check (r, type, op2))
}
void
-operator_rshift::wi_fold (value_range &r, tree type,
+operator_rshift::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const
{
class operator_cast: public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
-
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+private:
+ bool truncating_cast_p (const irange &inner, const irange &outer) const;
+ bool inside_domain_p (const wide_int &min, const wide_int &max,
+ const irange &outer) const;
+ void fold_pair (irange &r, unsigned index, const irange &inner,
+ const irange &outer) const;
} op_convert;
+// Return TRUE if casting from INNER to OUTER is a truncating cast.
+
+inline bool
+operator_cast::truncating_cast_p (const irange &inner,
+ const irange &outer) const
+{
+ return TYPE_PRECISION (outer.type ()) < TYPE_PRECISION (inner.type ());
+}
+
+// Return TRUE if [MIN,MAX] is inside the domain of RANGE's type.
+
bool
-operator_cast::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh) const
+operator_cast::inside_domain_p (const wide_int &min,
+ const wide_int &max,
+ const irange &range) const
{
- if (empty_range_check (r, lh, rh))
- return true;
-
- tree inner = lh.type ();
- tree outer = rh.type ();
- gcc_checking_assert (rh.varying_p ());
- gcc_checking_assert (types_compatible_p (outer, type));
- signop inner_sign = TYPE_SIGN (inner);
- signop outer_sign = TYPE_SIGN (outer);
- unsigned inner_prec = TYPE_PRECISION (inner);
- unsigned outer_prec = TYPE_PRECISION (outer);
-
- // Start with an empty range and add subranges.
- r = value_range ();
- for (unsigned x = 0; x < lh.num_pairs (); ++x)
- {
- wide_int lh_lb = lh.lower_bound (x);
- wide_int lh_ub = lh.upper_bound (x);
-
- // If the conversion is not truncating we can convert the min
- // and max values and canonicalize the resulting range.
- // Otherwise, we can do the conversion if the size of the range
- // is less than what the precision of the target type can
- // represent.
- if (outer_prec >= inner_prec
- || wi::rshift (wi::sub (lh_ub, lh_lb),
- wi::uhwi (outer_prec, inner_prec),
- inner_sign) == 0)
+ wide_int domain_min = wi::to_wide (vrp_val_min (range.type ()));
+ wide_int domain_max = wi::to_wide (vrp_val_max (range.type ()));
+ signop domain_sign = TYPE_SIGN (range.type ());
+ return (wi::le_p (min, domain_max, domain_sign)
+ && wi::le_p (max, domain_max, domain_sign)
+ && wi::ge_p (min, domain_min, domain_sign)
+ && wi::ge_p (max, domain_min, domain_sign));
+}
+
+
+// Helper for fold_range which work on a pair at a time.
+
+void
+operator_cast::fold_pair (irange &r, unsigned index,
+ const irange &inner,
+ const irange &outer) const
+{
+ tree inner_type = inner.type ();
+ tree outer_type = outer.type ();
+ signop inner_sign = TYPE_SIGN (inner_type);
+ unsigned outer_prec = TYPE_PRECISION (outer_type);
+
+ // check to see if casting from INNER to OUTER is a conversion that
+ // fits in the resulting OUTER type.
+ wide_int inner_lb = inner.lower_bound (index);
+ wide_int inner_ub = inner.upper_bound (index);
+ if (truncating_cast_p (inner, outer))
+ {
+ // We may be able to accomodate a truncating cast if the
+ // resulting range can be represented in the target type...
+ if (wi::rshift (wi::sub (inner_ub, inner_lb),
+ wi::uhwi (outer_prec, TYPE_PRECISION (inner.type ())),
+ inner_sign) != 0)
{
- wide_int min = wide_int::from (lh_lb, outer_prec, inner_sign);
- wide_int max = wide_int::from (lh_ub, outer_prec, inner_sign);
- if (!wi::eq_p (min, wi::min_value (outer_prec, outer_sign))
- || !wi::eq_p (max, wi::max_value (outer_prec, outer_sign)))
- {
- value_range tmp;
- create_possibly_reversed_range (tmp, type, min, max);
- r.union_ (tmp);
- continue;
- }
+ r.set_varying (outer_type);
+ return;
}
- r = value_range (type);
- break;
+ }
+ // ...but we must still verify that the final range fits in the
+ // domain. This catches -fstrict-enum restrictions where the domain
+ // range is smaller than what fits in the underlying type.
+ wide_int min = wide_int::from (inner_lb, outer_prec, inner_sign);
+ wide_int max = wide_int::from (inner_ub, outer_prec, inner_sign);
+ if (inside_domain_p (min, max, outer))
+ create_possibly_reversed_range (r, outer_type, min, max);
+ else
+ r.set_varying (outer_type);
+}
+
+
+bool
+operator_cast::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &inner,
+ const irange &outer) const
+{
+ if (empty_range_varying (r, type, inner, outer))
+ return true;
+
+ gcc_checking_assert (outer.varying_p ());
+ gcc_checking_assert (inner.num_pairs () > 0);
+
+ // Avoid a temporary by folding the first pair directly into the result.
+ fold_pair (r, 0, inner, outer);
+
+ // Then process any additonal pairs by unioning with their results.
+ for (unsigned x = 1; x < inner.num_pairs (); ++x)
+ {
+ widest_irange tmp;
+ fold_pair (tmp, x, inner, outer);
+ r.union_ (tmp);
+ if (r.varying_p ())
+ return true;
}
return true;
}
bool
-operator_cast::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_cast::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
tree lhs_type = lhs.type ();
- value_range tmp;
gcc_checking_assert (types_compatible_p (op2.type(), type));
- // If the precision of the LHS is smaller than the precision of the
- // RHS, then there would be truncation of the value on the RHS, and
- // so we can tell nothing about it.
- if (TYPE_PRECISION (lhs_type) < TYPE_PRECISION (type))
- {
- // If we've been passed an actual value for the RHS rather than
- // the type, see if it fits the LHS, and if so, then we can allow
- // it.
- fold_range (r, lhs_type, op2, value_range (lhs_type));
- fold_range (tmp, type, r, value_range (type));
- if (tmp == op2)
+ if (truncating_cast_p (op2, lhs))
+ {
+ if (lhs.varying_p ())
+ r.set_varying (type);
+ else
{
- // We know the value of the RHS fits in the LHS type, so
- // convert the LHS and remove any values that arent in OP2.
- fold_range (r, type, lhs, value_range (type));
- r.intersect (op2);
- return true;
- }
- // Special case if the LHS is a boolean. A 0 means the RHS is
- // zero, and a 1 means the RHS is non-zero.
- if (TREE_CODE (lhs_type) == BOOLEAN_TYPE)
- {
- // If the LHS is unknown, the result is whatever op2 already is.
- if (!lhs.singleton_p ())
- {
- r = op2;
- return true;
- }
- // Boolean casts are weird in GCC. It's actually an implied
- // mask with 0x01, so all that is known is whether the
- // rightmost bit is 0 or 1, which implies the only value
- // *not* in the RHS is 0 or -1.
- unsigned prec = TYPE_PRECISION (type);
- if (lhs.zero_p ())
- r = value_range (type, wi::minus_one (prec), wi::minus_one (prec),
- VR_ANTI_RANGE);
- else
- r = value_range (type, wi::zero (prec), wi::zero (prec),
- VR_ANTI_RANGE);
- // And intersect it with what we know about op2.
- r.intersect (op2);
+ // We want to insert the LHS as an unsigned value since it
+ // would not trigger the signed bit of the larger type.
+ widest_irange converted_lhs = lhs;
+ range_cast (converted_lhs, unsigned_type_for (lhs_type));
+ range_cast (converted_lhs, type);
+ // Start by building the positive signed outer range for the type.
+ wide_int lim = wi::set_bit_in_zero (TYPE_PRECISION (lhs_type),
+ TYPE_PRECISION (type));
+ r = int_range<1> (type, lim, wi::max_value (TYPE_PRECISION (type),
+ SIGNED));
+ // For the signed part, we need to simply union the 2 ranges now.
+ r.union_ (converted_lhs);
+
+ // Create maximal negative number outside of LHS bits.
+ lim = wi::mask (TYPE_PRECISION (lhs_type), true,
+ TYPE_PRECISION (type));
+ // Add this to the unsigned LHS range(s).
+ widest_irange lim_range (type, lim, lim);
+ widest_irange lhs_neg;
+ range_op_handler (PLUS_EXPR, type)->fold_range (lhs_neg,
+ type,
+ converted_lhs,
+ lim_range);
+ // And union this with the entire outer types negative range.
+ widest_irange neg (type,
+ wi::min_value (TYPE_PRECISION (type),
+ SIGNED),
+ lim - 1);
+ neg.union_ (lhs_neg);
+ // And finally, munge the signed and unsigned portions.
+ r.union_ (neg);
}
- else
- // Otherwise we'll have to assume it's whatever we know about op2.
- r = op2;
+ // And intersect with any known value passed in the extra operand.
+ r.intersect (op2);
return true;
}
- // If the LHS precision is greater than the rhs precision, the LHS
- // range is restricted to the range of the RHS by this
- // assignment.
- if (TYPE_PRECISION (lhs_type) > TYPE_PRECISION (type))
+ widest_irange tmp;
+ if (TYPE_PRECISION (lhs_type) == TYPE_PRECISION (type))
+ tmp = lhs;
+ else
{
+ // The cast is not truncating, and the range is restricted to
+ // the range of the RHS by this assignment.
+ //
// Cast the range of the RHS to the type of the LHS.
- fold_range (tmp, lhs_type, value_range (type), value_range (lhs_type));
- // Intersect this with the LHS range will produce the range, which
- // will be cast to the RHS type before returning.
+ fold_range (tmp, lhs_type, int_range<1> (type), int_range<1> (lhs_type));
+ // Intersect this with the LHS range will produce the range,
+ // which will be cast to the RHS type before returning.
tmp.intersect (lhs);
}
- else
- tmp = lhs;
// Cast the calculated range to the type of the RHS.
- fold_range (r, type, tmp, value_range (type));
+ fold_range (r, type, tmp, int_range<1> (type));
return true;
}
class operator_logical_and : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_logical_and;
bool
-operator_logical_and::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_logical_and::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// 0 && anything is 0.
}
bool
-operator_logical_and::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_logical_and::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_logical_and::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_logical_and::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_logical_and::op1_range (r, type, lhs, op1);
}
class operator_bitwise_and : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
+private:
+ void simple_op1_range_solver (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ void remove_impossible_ranges (irange &r, const irange &rh) const;
} op_bitwise_and;
+static bool
+unsigned_singleton_p (const irange &op)
+{
+ tree mask;
+ if (op.singleton_p (&mask))
+ {
+ wide_int x = wi::to_wide (mask);
+ return wi::ge_p (x, 0, TYPE_SIGN (op.type ()));
+ }
+ return false;
+}
+
+// Remove any ranges from R that are known to be impossible when an
+// range is ANDed with MASK.
+
+void
+operator_bitwise_and::remove_impossible_ranges (irange &r,
+ const irange &rmask) const
+{
+ if (r.undefined_p () || !unsigned_singleton_p (rmask))
+ return;
+
+ wide_int mask = rmask.lower_bound ();
+ tree type = r.type ();
+ int prec = TYPE_PRECISION (type);
+ int leading_zeros = wi::clz (mask);
+ widest_irange impossible_ranges;
+
+ /* We know that starting at the most significant bit, any 0 in the
+ mask means the resulting range cannot contain a 1 in that same
+ position. This means the following ranges are impossible:
+
+ x & 0b1001 1010
+ IMPOSSIBLE RANGES
+ 01xx xxxx [0100 0000, 0111 1111]
+ 001x xxxx [0010 0000, 0011 1111]
+ 0000 01xx [0000 0100, 0000 0111]
+ 0000 0001 [0000 0001, 0000 0001]
+ */
+ wide_int one = wi::one (prec);
+ for (int i = 0; i < prec - leading_zeros - 1; ++i)
+ if (wi::bit_and (mask, wi::lshift (one, wi::uhwi (i, prec))) == 0)
+ {
+ tree lb = fold_build2 (LSHIFT_EXPR, type,
+ build_one_cst (type),
+ build_int_cst (type, i));
+ tree ub_left = fold_build1 (BIT_NOT_EXPR, type,
+ fold_build2 (LSHIFT_EXPR, type,
+ build_minus_one_cst (type),
+ build_int_cst (type, i)));
+ tree ub_right = fold_build2 (LSHIFT_EXPR, type,
+ build_one_cst (type),
+ build_int_cst (type, i));
+ tree ub = fold_build2 (BIT_IOR_EXPR, type, ub_left, ub_right);
+ impossible_ranges.union_ (int_range<1> (lb, ub));
+ }
+ if (!impossible_ranges.undefined_p ())
+ {
+ impossible_ranges.invert ();
+ r.intersect (impossible_ranges);
+ }
+}
+
+bool
+operator_bitwise_and::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
+{
+ if (range_operator::fold_range (r, type, lh, rh))
+ {
+ // FIXME: This is temporarily disabled because, though it
+ // generates better ranges, it's noticeably slower for evrp.
+ // remove_impossible_ranges (r, rh);
+ return true;
+ }
+ return false;
+}
+
+
// Optimize BIT_AND_EXPR and BIT_IOR_EXPR in terms of a mask if
// possible. Basically, see if we can optimize:
//
// return TRUE.
static bool
-wi_optimize_and_or (value_range &r,
+wi_optimize_and_or (irange &r,
enum tree_code code,
tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
}
void
-operator_bitwise_and::wi_fold (value_range &r, tree type,
+operator_bitwise_and::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
}
// If the limits got swapped around, return varying.
if (wi::gt_p (new_lb, new_ub,sign))
- r = value_range (type);
+ r.set_varying (type);
else
value_range_with_overflow (r, type, new_lb, new_ub);
}
+static void
+set_nonzero_range_from_mask (irange &r, tree type, const irange &lhs)
+{
+ if (!lhs.contains_p (build_zero_cst (type)))
+ r = range_nonzero (type);
+ else
+ r.set_varying (type);
+}
+
+// This was shamelessly stolen from register_edge_assert_for_2 and
+// adjusted to work with iranges.
+
+void
+operator_bitwise_and::simple_op1_range_solver (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ if (!op2.singleton_p ())
+ {
+ set_nonzero_range_from_mask (r, type, lhs);
+ return;
+ }
+ unsigned int nprec = TYPE_PRECISION (type);
+ wide_int cst2v = op2.lower_bound ();
+ bool cst2n = wi::neg_p (cst2v, TYPE_SIGN (type));
+ wide_int sgnbit;
+ if (cst2n)
+ sgnbit = wi::set_bit_in_zero (nprec - 1, nprec);
+ else
+ sgnbit = wi::zero (nprec);
+
+ // Solve [lhs.lower_bound (), +INF] = x & MASK.
+ //
+ // Minimum unsigned value for >= if (VAL & CST2) == VAL is VAL and
+ // maximum unsigned value is ~0. For signed comparison, if CST2
+ // doesn't have the most significant bit set, handle it similarly. If
+ // CST2 has MSB set, the minimum is the same, and maximum is ~0U/2.
+ wide_int valv = lhs.lower_bound ();
+ wide_int minv = valv & cst2v, maxv;
+ bool we_know_nothing = false;
+ if (minv != valv)
+ {
+ // If (VAL & CST2) != VAL, X & CST2 can't be equal to VAL.
+ minv = masked_increment (valv, cst2v, sgnbit, nprec);
+ if (minv == valv)
+ {
+ // If we can't determine anything on this bound, fall
+ // through and conservatively solve for the other end point.
+ we_know_nothing = true;
+ }
+ }
+ maxv = wi::mask (nprec - (cst2n ? 1 : 0), false, nprec);
+ if (we_know_nothing)
+ r.set_varying (type);
+ else
+ r = int_range<1> (type, minv, maxv);
+
+ // Solve [-INF, lhs.upper_bound ()] = x & MASK.
+ //
+ // 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.
+ valv = lhs.upper_bound ();
+ minv = valv & cst2v;
+ if (minv == valv)
+ maxv = valv;
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, nprec);
+ if (maxv == valv)
+ {
+ // If we couldn't determine anything on either bound, return
+ // undefined.
+ if (we_know_nothing)
+ r.set_undefined ();
+ return;
+ }
+ maxv -= 1;
+ }
+ maxv |= ~cst2v;
+ minv = sgnbit;
+ int_range<1> upper_bits (type, minv, maxv);
+ r.intersect (upper_bits);
+}
+
bool
-operator_bitwise_and::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_and::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
- // If this is really a logical wi_fold, call that.
if (types_compatible_p (type, boolean_type_node))
return op_logical_and.op1_range (r, type, lhs, op2);
- // For now do nothing with bitwise AND of value_range's.
- r.set_varying (type);
+ r.set_undefined ();
+ for (unsigned i = 0; i < lhs.num_pairs (); ++i)
+ {
+ widest_irange chunk (lhs.type (),
+ lhs.lower_bound (i),
+ lhs.upper_bound (i));
+ widest_irange res;
+ simple_op1_range_solver (res, type, chunk, op2);
+ r.union_ (res);
+ }
+ if (r.undefined_p ())
+ set_nonzero_range_from_mask (r, type, lhs);
return true;
}
bool
-operator_bitwise_and::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_bitwise_and::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_bitwise_and::op1_range (r, type, lhs, op1);
}
class operator_logical_or : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_logical_or;
bool
-operator_logical_or::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh) const
+operator_logical_or::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
r = lh;
}
bool
-operator_logical_or::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_logical_or::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
switch (get_bool_state (r, lhs, type))
{
}
bool
-operator_logical_or::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_logical_or::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_logical_or::op1_range (r, type, lhs, op1);
}
class operator_bitwise_or : public range_operator
{
public:
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
- virtual bool op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const;
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_bitwise_or;
void
-operator_bitwise_or::wi_fold (value_range &r, tree type,
+operator_bitwise_or::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
new_lb = wi::max (new_lb, rh_lb, sign);
// If the limits got swapped around, return varying.
if (wi::gt_p (new_lb, new_ub,sign))
- r = value_range (type);
+ r.set_varying (type);
else
value_range_with_overflow (r, type, new_lb, new_ub);
}
bool
-operator_bitwise_or::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_or::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// If this is really a logical wi_fold, call that.
if (types_compatible_p (type, boolean_type_node))
return op_logical_or.op1_range (r, type, lhs, op2);
- // For now do nothing with bitwise OR of value_range's.
+ if (lhs.zero_p ())
+ {
+ tree zero = build_zero_cst (type);
+ r = int_range<1> (zero, zero);
+ return true;
+ }
r.set_varying (type);
return true;
}
bool
-operator_bitwise_or::op2_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op1) const
+operator_bitwise_or::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
{
return operator_bitwise_or::op1_range (r, type, lhs, op1);
}
class operator_bitwise_xor : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
} op_bitwise_xor;
void
-operator_bitwise_xor::wi_fold (value_range &r, tree type,
+operator_bitwise_xor::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
if (wi::lt_p (new_lb, 0, sign) || wi::ge_p (new_ub, 0, sign))
value_range_with_overflow (r, type, new_lb, new_ub);
else
- r = value_range (type);
+ r.set_varying (type);
+}
+
+bool
+operator_bitwise_xor::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
+{
+ if (lhs.undefined_p () || lhs.varying_p ())
+ {
+ r = lhs;
+ return true;
+ }
+ if (types_compatible_p (type, boolean_type_node))
+ {
+ switch (get_bool_state (r, lhs, type))
+ {
+ case BRS_TRUE:
+ if (op2.varying_p ())
+ r.set_varying (type);
+ else if (op2.zero_p ())
+ r = range_true (type);
+ else
+ r = range_false (type);
+ break;
+ case BRS_FALSE:
+ r = op2;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ return true;
+ }
+ r.set_varying (type);
+ return true;
}
+bool
+operator_bitwise_xor::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
+{
+ return operator_bitwise_xor::op1_range (r, type, lhs, op1);
+}
class operator_trunc_mod : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_trunc_mod;
void
-operator_trunc_mod::wi_fold (value_range &r, tree type,
+operator_trunc_mod::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
// Mod 0 is undefined. Return undefined.
if (wi_zero_p (type, rh_lb, rh_ub))
{
- r = value_range ();
+ r.set_undefined ();
return;
}
class operator_logical_not : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_logical_not;
// Folding a logical NOT, oddly enough, involves doing nothing on the
// which is the result we are looking for.. so.. pass it through.
bool
-operator_logical_not::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_logical_not::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
if (lh.varying_p () || lh.undefined_p ())
}
bool
-operator_logical_not::op1_range (value_range &r,
+operator_logical_not::op1_range (irange &r,
tree type ATTRIBUTE_UNUSED,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
r = lhs;
if (!lhs.varying_p () && !lhs.undefined_p ())
class operator_bitwise_not : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_bitwise_not;
bool
-operator_bitwise_not::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_bitwise_not::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// ~X is simply -1 - X.
- value_range minusone (type, wi::minus_one (TYPE_PRECISION (type)),
- wi::minus_one (TYPE_PRECISION (type)));
+ int_range<1> minusone (type, wi::minus_one (TYPE_PRECISION (type)),
+ wi::minus_one (TYPE_PRECISION (type)));
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type, minusone,
lh);
}
bool
-operator_bitwise_not::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_bitwise_not::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// ~X is -1 - X and since bitwise NOT is involutary...do it again.
return fold_range (r, type, lhs, op2);
class operator_cst : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
} op_integer_cst;
bool
-operator_cst::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_cst::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
r = lh;
return true;
class operator_identity : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_identity;
bool
-operator_identity::fold_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lh,
- const value_range &rh ATTRIBUTE_UNUSED) const
+operator_identity::fold_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lh,
+ const irange &rh ATTRIBUTE_UNUSED) const
{
r = lh;
return true;
}
bool
-operator_identity::op1_range (value_range &r, tree type ATTRIBUTE_UNUSED,
- const value_range &lhs,
- const value_range &op2 ATTRIBUTE_UNUSED) const
+operator_identity::op1_range (irange &r, tree type ATTRIBUTE_UNUSED,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
{
r = lhs;
return true;
}
+class operator_unknown : public range_operator
+{
+public:
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+} op_unknown;
+
+bool
+operator_unknown::fold_range (irange &r, tree type,
+ const irange &lh ATTRIBUTE_UNUSED,
+ const irange &rh ATTRIBUTE_UNUSED) const
+{
+ r.set_varying (type);
+ return true;
+}
+
+
class operator_abs : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
const wide_int &rh_ub) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_abs;
void
-operator_abs::wi_fold (value_range &r, tree type,
+operator_abs::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
// Pass through LH for the easy cases.
if (sign == UNSIGNED || wi::ge_p (lh_lb, 0, sign))
{
- r = value_range (type, lh_lb, lh_ub);
+ r = int_range<1> (type, lh_lb, lh_ub);
return;
}
wide_int max_value = wi::max_value (prec, sign);
if (!TYPE_OVERFLOW_UNDEFINED (type) && wi::eq_p (lh_lb, min_value))
{
- r = value_range (type);
+ r.set_varying (type);
return;
}
min = wi::zero (prec);
max = max_value;
}
- r = value_range (type, min, max);
+ r = int_range<1> (type, min, max);
}
bool
-operator_abs::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_abs::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
- if (empty_range_check (r, lhs, op2))
+ if (empty_range_varying (r, type, lhs, op2))
return true;
if (TYPE_UNSIGNED (type))
{
return true;
}
// Start with the positives because negatives are an impossible result.
- value_range positives = range_positives (type);
+ widest_irange positives = range_positives (type);
positives.intersect (lhs);
r = positives;
// Then add the negative of each pair:
// ABS(op1) = [5,20] would yield op1 => [-20,-5][5,20].
for (unsigned i = 0; i < positives.num_pairs (); ++i)
- r.union_ (value_range (type,
- -positives.upper_bound (i),
- -positives.lower_bound (i)));
+ r.union_ (int_range<1> (type,
+ -positives.upper_bound (i),
+ -positives.lower_bound (i)));
return true;
}
class operator_absu : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_absu;
void
-operator_absu::wi_fold (value_range &r, tree type,
+operator_absu::wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
const wide_int &rh_ub ATTRIBUTE_UNUSED) const
}
gcc_checking_assert (TYPE_UNSIGNED (type));
- r = value_range (type, new_lb, new_ub);
+ r = int_range<1> (type, new_lb, new_ub);
}
class operator_negate : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_negate;
bool
-operator_negate::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_negate::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// -X is simply 0 - X.
return range_op_handler (MINUS_EXPR, type)->fold_range (r, type,
}
bool
-operator_negate::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_negate::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
// NEGATE is involutory.
return fold_range (r, type, lhs, op2);
class operator_addr_expr : public range_operator
{
public:
- virtual bool fold_range (value_range &r, tree type,
- const value_range &op1,
- const value_range &op2) const;
- virtual bool op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const;
+ virtual bool fold_range (irange &r, tree type,
+ const irange &op1,
+ const irange &op2) const;
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
} op_addr;
bool
-operator_addr_expr::fold_range (value_range &r, tree type,
- const value_range &lh,
- const value_range &rh) const
+operator_addr_expr::fold_range (irange &r, tree type,
+ const irange &lh,
+ const irange &rh) const
{
- if (empty_range_check (r, lh, rh))
+ if (empty_range_varying (r, type, lh, rh))
return true;
// Return a non-null pointer of the LHS type (passed in op2).
else if (!lh.contains_p (build_zero_cst (lh.type ())))
r = range_nonzero (type);
else
- r = value_range (type);
+ r.set_varying (type);
return true;
}
bool
-operator_addr_expr::op1_range (value_range &r, tree type,
- const value_range &lhs,
- const value_range &op2) const
+operator_addr_expr::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const
{
return operator_addr_expr::fold_range (r, type, lhs, op2);
}
class pointer_plus_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
} op_pointer_plus;
void
-pointer_plus_operator::wi_fold (value_range &r, tree type,
+pointer_plus_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
&& rh_lb == rh_ub && rh_lb == 0)
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_min_max_operator : public range_operator
{
public:
- virtual void wi_fold (value_range & r, tree type,
+ virtual void wi_fold (irange & r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_ptr_min_max;
void
-pointer_min_max_operator::wi_fold (value_range &r, tree type,
+pointer_min_max_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_and_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_and;
void
-pointer_and_operator::wi_fold (value_range &r, tree type,
+pointer_and_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb ATTRIBUTE_UNUSED,
if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
class pointer_or_operator : public range_operator
{
public:
- virtual void wi_fold (value_range &r, tree type,
+ virtual bool op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2) const;
+ virtual bool op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const;
+ virtual void wi_fold (irange &r, tree type,
const wide_int &lh_lb, const wide_int &lh_ub,
const wide_int &rh_lb, const wide_int &rh_ub) const;
} op_pointer_or;
+bool
+pointer_or_operator::op1_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op2 ATTRIBUTE_UNUSED) const
+{
+ if (lhs.zero_p ())
+ {
+ tree zero = build_zero_cst (type);
+ r = int_range<1> (zero, zero);
+ return true;
+ }
+ r.set_varying (type);
+ return true;
+}
+
+bool
+pointer_or_operator::op2_range (irange &r, tree type,
+ const irange &lhs,
+ const irange &op1) const
+{
+ return pointer_or_operator::op1_range (r, type, lhs, op1);
+}
+
void
-pointer_or_operator::wi_fold (value_range &r, tree type,
+pointer_or_operator::wi_fold (irange &r, tree type,
const wide_int &lh_lb,
const wide_int &lh_ub,
const wide_int &rh_lb,
else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
r = range_zero (type);
else
- r = value_range (type);
+ r.set_varying (type);
}
\f
// This implements the range operator tables as local objects in this file.
set (SSA_NAME, op_identity);
set (PAREN_EXPR, op_identity);
set (OBJ_TYPE_REF, op_identity);
+ set (IMAGPART_EXPR, op_unknown);
+ set (POINTER_DIFF_EXPR, op_unknown);
set (ABS_EXPR, op_abs);
set (ABSU_EXPR, op_absu);
set (NEGATE_EXPR, op_negate);
// Cast the range in R to TYPE.
void
-range_cast (value_range &r, tree type)
+range_cast (irange &r, tree type)
{
- value_range tmp = r;
+ widest_irange tmp = r;
range_operator *op = range_op_handler (CONVERT_EXPR, type);
// Call op_convert, if it fails, the result is varying.
- if (!op->fold_range (r, type, tmp, value_range (type)))
- r = value_range (type);
+ if (!op->fold_range (r, type, tmp, int_range<1> (type)))
+ r.set_varying (type);
}
#if CHECKING_P
#define UCHAR(N) build_int_cstu (unsigned_char_type_node, (N))
#define SCHAR(N) build_int_cst (signed_char_type_node, (N))
+static int_range<3>
+build_range3 (int a, int b, int c, int d, int e, int f)
+{
+ int_range<3> i1 (INT (a), INT (b));
+ int_range<3> i2 (INT (c), INT (d));
+ int_range<3> i3 (INT (e), INT (f));
+ i1.union_ (i2);
+ i1.union_ (i3);
+ return i1;
+}
+
+static void
+range3_tests ()
+{
+ typedef int_range<3> irange3;
+ irange3 r0, r1, r2;
+ irange3 i1, i2, i3;
+
+ // ([10,20] U [5,8]) U [1,3] ==> [1,3][5,8][10,20].
+ r0 = irange3 (INT (10), INT (20));
+ r1 = irange3 (INT (5), INT (8));
+ r0.union_ (r1);
+ r1 = irange3 (INT (1), INT (3));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (1, 3, 5, 8, 10, 20));
+
+ // [1,3][5,8][10,20] U [-5,0] => [-5,3][5,8][10,20].
+ r1 = irange3 (INT (-5), INT (0));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (-5, 3, 5, 8, 10, 20));
+
+ // [10,20][30,40] U [50,60] ==> [10,20][30,40][50,60].
+ r1 = irange3 (INT (50), INT (60));
+ r0 = irange3 (INT (10), INT (20));
+ r0.union_ (irange3 (INT (30), INT (40)));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
+ // [10,20][30,40][50,60] U [70, 80] ==> [10,20][30,40][50,60][70,80].
+ r1 = irange3 (INT (70), INT (80));
+ r0.union_ (r1);
+
+ r2 = build_range3 (10, 20, 30, 40, 50, 60);
+ r2.union_ (irange3 (INT (70), INT (80)));
+ ASSERT_TRUE (r0 == r2);
+
+ // [10,20][30,40][50,60] U [6,35] => [6,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (35));
+ r0.union_ (r1);
+ r1 = irange3 (INT (6), INT (40));
+ r1.union_ (irange3 (INT (50), INT (60)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [6,60] => [6,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (60));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange3 (INT (6), INT (60)));
+
+ // [10,20][30,40][50,60] U [6,70] => [6,70].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (6), INT (70));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == irange3 (INT (6), INT (70)));
+
+ // [10,20][30,40][50,60] U [35,70] => [10,20][30,70].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (35), INT (70));
+ r0.union_ (r1);
+ r1 = irange3 (INT (10), INT (20));
+ r1.union_ (irange3 (INT (30), INT (70)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [15,35] => [10,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (15), INT (35));
+ r0.union_ (r1);
+ r1 = irange3 (INT (10), INT (40));
+ r1.union_ (irange3 (INT (50), INT (60)));
+ ASSERT_TRUE (r0 == r1);
+
+ // [10,20][30,40][50,60] U [35,35] => [10,20][30,40][50,60].
+ r0 = build_range3 (10, 20, 30, 40, 50, 60);
+ r1 = irange3 (INT (35), INT (35));
+ r0.union_ (r1);
+ ASSERT_TRUE (r0 == build_range3 (10, 20, 30, 40, 50, 60));
+}
+
+static void
+widest_irange_tests ()
+{
+ widest_irange big;
+ unsigned int nrange;
+
+ // Build a huge multi-range range.
+ for (nrange = 0; nrange < 50; ++nrange)
+ {
+ int_range<1> tmp (INT (nrange*10), INT (nrange*10 + 5));
+ big.union_ (tmp);
+ }
+ ASSERT_TRUE (big.num_pairs () == nrange);
+
+ // Verify that we can copy it without loosing precision.
+ widest_irange copy (big);
+ ASSERT_TRUE (copy.num_pairs () == nrange);
+
+ // Inverting it should produce one more sub-range.
+ big.invert ();
+ ASSERT_TRUE (big.num_pairs () == nrange + 1);
+
+ int_range<1> tmp (INT (5), INT (37));
+ big.intersect (tmp);
+ ASSERT_TRUE (big.num_pairs () == 4);
+
+ // Test that [10,10][20,20] does NOT contain 15.
+ {
+ widest_irange i1 (build_int_cst (integer_type_node, 10),
+ build_int_cst (integer_type_node, 10));
+ widest_irange i2 (build_int_cst (integer_type_node, 20),
+ build_int_cst (integer_type_node, 20));
+ i1.union_ (i2);
+ ASSERT_FALSE (i1.contains_p (build_int_cst (integer_type_node, 15)));
+ }
+
+}
+
+static void
+multi_precision_range_tests ()
+{
+ // Test truncating copy to int_range<1>.
+ int_range<3> big = build_range3 (10, 20, 30, 40, 50, 60);
+ int_range<1> small = big;
+ ASSERT_TRUE (small == int_range<1> (INT (10), INT (60)));
+
+ // Test truncating copy to int_range<2>.
+ int_range<2> medium = big;
+ ASSERT_TRUE (!medium.undefined_p ());
+
+ // Test that a truncating copy of [MIN,20][22,40][80,MAX]
+ // ends up as a conservative anti-range of ~[21,21].
+ big = int_range<3> (vrp_val_min (integer_type_node), INT (20));
+ big.union_ (int_range<1> (INT (22), INT (40)));
+ big.union_ (int_range<1> (INT (80), vrp_val_max (integer_type_node)));
+ small = big;
+ ASSERT_TRUE (small == int_range<1> (INT (21), INT (21), VR_ANTI_RANGE));
+
+ range3_tests ();
+}
+
+static void
+operator_tests ()
+{
+ tree min = vrp_val_min (integer_type_node);
+ tree max = vrp_val_max (integer_type_node);
+ tree tiny = fold_build2 (PLUS_EXPR, integer_type_node, min,
+ build_one_cst (integer_type_node));
+ widest_irange res;
+ widest_irange i1 (tiny, max);
+ widest_irange i2 (build_int_cst (integer_type_node, 255),
+ build_int_cst (integer_type_node, 255));
+
+ // [MIN+1, MAX] = OP1 & 255: OP1 is VARYING
+ op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
+ ASSERT_TRUE (res == int_range<1> (integer_type_node));
+
+ // VARYING = OP1 & 255: OP1 is VARYING
+ i1 = int_range<1> (integer_type_node);
+ op_bitwise_and.op1_range (res, integer_type_node, i1, i2);
+ ASSERT_TRUE (res == int_range<1> (integer_type_node));
+
+ // Test that 0x808.... & 0x8.... still contains 0x8....
+ // for a large set of numbers.
+ {
+ tree big_type = long_long_unsigned_type_node;
+ // big_num = 0x808,0000,0000,0000
+ tree big_num = fold_build2 (LSHIFT_EXPR, big_type,
+ build_int_cst (big_type, 0x808),
+ build_int_cst (big_type, 48));
+ op_bitwise_and.fold_range (res, big_type,
+ int_range <1> (big_type),
+ int_range <1> (big_num, big_num));
+ // val = 0x8,0000,0000,0000
+ tree val = fold_build2 (LSHIFT_EXPR, big_type,
+ build_int_cst (big_type, 0x8),
+ build_int_cst (big_type, 48));
+ ASSERT_TRUE (res.contains_p (val));
+ }
+
+ // unsigned: [3, MAX] = OP1 >> 1
+ {
+ widest_irange lhs (build_int_cst (unsigned_type_node, 3),
+ TYPE_MAX_VALUE (unsigned_type_node));
+ widest_irange one (build_one_cst (unsigned_type_node),
+ build_one_cst (unsigned_type_node));
+ widest_irange op1;
+ op_rshift.op1_range (op1, unsigned_type_node, lhs, one);
+ ASSERT_FALSE (op1.contains_p (UINT (3)));
+ }
+
+ // signed: [3, MAX] = OP1 >> 1
+ {
+ widest_irange lhs (INT (3), TYPE_MAX_VALUE (integer_type_node));
+ widest_irange one (INT (1), INT (1));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, one);
+ ASSERT_FALSE (op1.contains_p (INT (-2)));
+ }
+
+ // This is impossible, so OP1 should be [].
+ // signed: [MIN, MIN] = OP1 >> 1
+ {
+ widest_irange lhs (TYPE_MIN_VALUE (integer_type_node),
+ TYPE_MIN_VALUE (integer_type_node));
+ widest_irange one (INT (1), INT (1));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, one);
+ ASSERT_TRUE (op1.undefined_p ());
+ }
+
+ // signed: ~[-1] = OP1 >> 31
+ {
+ widest_irange lhs (INT (-1), INT (-1), VR_ANTI_RANGE);
+ widest_irange shift (INT (31), INT (31));
+ widest_irange op1;
+ op_rshift.op1_range (op1, integer_type_node, lhs, shift);
+ widest_irange negatives = range_negatives (integer_type_node);
+ negatives.intersect (op1);
+ ASSERT_TRUE (negatives.undefined_p ());
+ }
+}
+
// Run all of the selftests within this file.
void
range_tests ()
{
tree u128_type = build_nonstandard_integer_type (128, /*unsigned=*/1);
- value_range i1, i2, i3;
- value_range r0, r1, rold;
+ int_range<1> i1, i2, i3;
+ int_range<1> r0, r1, rold;
+
+ // Test 1-bit signed integer union.
+ // [-1,-1] U [0,0] = VARYING.
+ tree one_bit_type = build_nonstandard_integer_type (1, 0);
+ {
+ tree one_bit_min = vrp_val_min (one_bit_type);
+ tree one_bit_max = vrp_val_max (one_bit_type);
+ int_range<2> min (one_bit_min, one_bit_min);
+ int_range<2> max (one_bit_max, one_bit_max);
+ max.union_ (min);
+ ASSERT_TRUE (max.varying_p ());
+ }
// Test that NOT(255) is [0..254] in 8-bit land.
- value_range not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
- ASSERT_TRUE (not_255 == value_range (UCHAR (0), UCHAR (254)));
+ int_range<1> not_255 (UCHAR (255), UCHAR (255), VR_ANTI_RANGE);
+ ASSERT_TRUE (not_255 == int_range<1> (UCHAR (0), UCHAR (254)));
// Test that NOT(0) is [1..255] in 8-bit land.
- value_range not_zero = range_nonzero (unsigned_char_type_node);
- ASSERT_TRUE (not_zero == value_range (UCHAR (1), UCHAR (255)));
+ int_range<1> not_zero = range_nonzero (unsigned_char_type_node);
+ ASSERT_TRUE (not_zero == int_range<1> (UCHAR (1), UCHAR (255)));
// Check that [0,127][0x..ffffff80,0x..ffffff]
// => ~[128, 0x..ffffff7f].
- r0 = value_range (UINT128 (0), UINT128 (127));
+ r0 = int_range<1> (UINT128 (0), UINT128 (127));
tree high = build_minus_one_cst (u128_type);
// low = -1 - 127 => 0x..ffffff80.
tree low = fold_build2 (MINUS_EXPR, u128_type, high, UINT128(127));
- r1 = value_range (low, high); // [0x..ffffff80, 0x..ffffffff]
+ r1 = int_range<1> (low, high); // [0x..ffffff80, 0x..ffffffff]
// r0 = [0,127][0x..ffffff80,0x..fffffff].
r0.union_ (r1);
// r1 = [128, 0x..ffffff7f].
- r1 = value_range (UINT128(128),
- fold_build2 (MINUS_EXPR, u128_type,
- build_minus_one_cst (u128_type),
- UINT128(128)));
+ r1 = int_range<1> (UINT128(128),
+ fold_build2 (MINUS_EXPR, u128_type,
+ build_minus_one_cst (u128_type),
+ UINT128(128)));
r0.invert ();
ASSERT_TRUE (r0 == r1);
tree maxuint = wide_int_to_tree (unsigned_type_node, r0.upper_bound ());
// Check that ~[0,5] => [6,MAX] for unsigned int.
- r0 = value_range (UINT (0), UINT (5));
+ r0 = int_range<1> (UINT (0), UINT (5));
r0.invert ();
- ASSERT_TRUE (r0 == value_range (UINT(6), maxuint));
+ ASSERT_TRUE (r0 == int_range<1> (UINT(6), maxuint));
// Check that ~[10,MAX] => [0,9] for unsigned int.
- r0 = value_range (UINT(10), maxuint);
+ r0 = int_range<1> (UINT(10), maxuint);
r0.invert ();
- ASSERT_TRUE (r0 == value_range (UINT (0), UINT (9)));
+ ASSERT_TRUE (r0 == int_range<1> (UINT (0), UINT (9)));
// Check that ~[0,5] => [6,MAX] for unsigned 128-bit numbers.
- r0 = value_range (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
- r1 = value_range (UINT128(6), build_minus_one_cst (u128_type));
+ r0 = int_range<1> (UINT128 (0), UINT128 (5), VR_ANTI_RANGE);
+ r1 = int_range<1> (UINT128(6), build_minus_one_cst (u128_type));
ASSERT_TRUE (r0 == r1);
// Check that [~5] is really [-MIN,4][6,MAX].
- r0 = value_range (INT (5), INT (5), VR_ANTI_RANGE);
- r1 = value_range (minint, INT (4));
- r1.union_ (value_range (INT (6), maxint));
+ r0 = int_range<1> (INT (5), INT (5), VR_ANTI_RANGE);
+ r1 = int_range<1> (minint, INT (4));
+ r1.union_ (int_range<1> (INT (6), maxint));
ASSERT_FALSE (r1.undefined_p ());
ASSERT_TRUE (r0 == r1);
- r1 = value_range (INT (5), INT (5));
- value_range r2 (r1);
+ r1 = int_range<1> (INT (5), INT (5));
+ int_range<1> r2 (r1);
ASSERT_TRUE (r1 == r2);
- r1 = value_range (INT (5), INT (10));
+ r1 = int_range<1> (INT (5), INT (10));
- r1 = value_range (integer_type_node,
- wi::to_wide (INT (5)), wi::to_wide (INT (10)));
+ r1 = int_range<1> (integer_type_node,
+ wi::to_wide (INT (5)), wi::to_wide (INT (10)));
ASSERT_TRUE (r1.contains_p (INT (7)));
- r1 = value_range (SCHAR (0), SCHAR (20));
+ r1 = int_range<1> (SCHAR (0), SCHAR (20));
ASSERT_TRUE (r1.contains_p (SCHAR(15)));
ASSERT_FALSE (r1.contains_p (SCHAR(300)));
if (TYPE_PRECISION (TREE_TYPE (maxint))
> TYPE_PRECISION (short_integer_type_node))
{
- r1 = value_range (integer_zero_node, maxint);
+ r1 = int_range<1> (integer_zero_node, maxint);
range_cast (r1, short_integer_type_node);
ASSERT_TRUE (r1.lower_bound () == wi::to_wide (minshort)
&& r1.upper_bound() == wi::to_wide (maxshort));
}
// (unsigned char)[-5,-1] => [251,255].
- r0 = rold = value_range (SCHAR (-5), SCHAR (-1));
+ r0 = rold = int_range<1> (SCHAR (-5), SCHAR (-1));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == value_range (UCHAR (251), UCHAR (255)));
+ ASSERT_TRUE (r0 == int_range<1> (UCHAR (251), UCHAR (255)));
range_cast (r0, signed_char_type_node);
ASSERT_TRUE (r0 == rold);
// (signed char)[15, 150] => [-128,-106][15,127].
- r0 = rold = value_range (UCHAR (15), UCHAR (150));
+ r0 = rold = int_range<1> (UCHAR (15), UCHAR (150));
range_cast (r0, signed_char_type_node);
- r1 = value_range (SCHAR (15), SCHAR (127));
- r2 = value_range (SCHAR (-128), SCHAR (-106));
+ r1 = int_range<1> (SCHAR (15), SCHAR (127));
+ r2 = int_range<1> (SCHAR (-128), SCHAR (-106));
r1.union_ (r2);
ASSERT_TRUE (r1 == r0);
range_cast (r0, unsigned_char_type_node);
ASSERT_TRUE (r0 == rold);
// (unsigned char)[-5, 5] => [0,5][251,255].
- r0 = rold = value_range (SCHAR (-5), SCHAR (5));
+ r0 = rold = int_range<1> (SCHAR (-5), SCHAR (5));
range_cast (r0, unsigned_char_type_node);
- r1 = value_range (UCHAR (251), UCHAR (255));
- r2 = value_range (UCHAR (0), UCHAR (5));
+ r1 = int_range<1> (UCHAR (251), UCHAR (255));
+ r2 = int_range<1> (UCHAR (0), UCHAR (5));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
range_cast (r0, signed_char_type_node);
ASSERT_TRUE (r0 == rold);
// (unsigned char)[-5,5] => [0,5][251,255].
- r0 = value_range (INT (-5), INT (5));
+ r0 = int_range<1> (INT (-5), INT (5));
range_cast (r0, unsigned_char_type_node);
- r1 = value_range (UCHAR (0), UCHAR (5));
- r1.union_ (value_range (UCHAR (251), UCHAR (255)));
+ r1 = int_range<1> (UCHAR (0), UCHAR (5));
+ r1.union_ (int_range<1> (UCHAR (251), UCHAR (255)));
ASSERT_TRUE (r0 == r1);
// (unsigned char)[5U,1974U] => [0,255].
- r0 = value_range (UINT (5), UINT (1974));
+ r0 = int_range<1> (UINT (5), UINT (1974));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == value_range (UCHAR (0), UCHAR (255)));
+ ASSERT_TRUE (r0 == int_range<1> (UCHAR (0), UCHAR (255)));
range_cast (r0, integer_type_node);
// Going to a wider range should not sign extend.
- ASSERT_TRUE (r0 == value_range (INT (0), INT (255)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (0), INT (255)));
// (unsigned char)[-350,15] => [0,255].
- r0 = value_range (INT (-350), INT (15));
+ r0 = int_range<1> (INT (-350), INT (15));
range_cast (r0, unsigned_char_type_node);
- ASSERT_TRUE (r0 == (value_range
+ ASSERT_TRUE (r0 == (int_range<1>
(TYPE_MIN_VALUE (unsigned_char_type_node),
TYPE_MAX_VALUE (unsigned_char_type_node))));
// Casting [-120,20] from signed char to unsigned short.
// => [0, 20][0xff88, 0xffff].
- r0 = value_range (SCHAR (-120), SCHAR (20));
+ r0 = int_range<1> (SCHAR (-120), SCHAR (20));
range_cast (r0, short_unsigned_type_node);
- r1 = value_range (UINT16 (0), UINT16 (20));
- r2 = value_range (UINT16 (0xff88), UINT16 (0xffff));
+ r1 = int_range<1> (UINT16 (0), UINT16 (20));
+ r2 = int_range<1> (UINT16 (0xff88), UINT16 (0xffff));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
// A truncating cast back to signed char will work because [-120, 20]
// is representable in signed char.
range_cast (r0, signed_char_type_node);
- ASSERT_TRUE (r0 == value_range (SCHAR (-120), SCHAR (20)));
+ ASSERT_TRUE (r0 == int_range<1> (SCHAR (-120), SCHAR (20)));
// unsigned char -> signed short
// (signed short)[(unsigned char)25, (unsigned char)250]
// => [(signed short)25, (signed short)250]
- r0 = rold = value_range (UCHAR (25), UCHAR (250));
+ r0 = rold = int_range<1> (UCHAR (25), UCHAR (250));
range_cast (r0, short_integer_type_node);
- r1 = value_range (INT16 (25), INT16 (250));
+ r1 = int_range<1> (INT16 (25), INT16 (250));
ASSERT_TRUE (r0 == r1);
range_cast (r0, unsigned_char_type_node);
ASSERT_TRUE (r0 == rold);
// Test casting a wider signed [-MIN,MAX] to a nar`rower unsigned.
- r0 = value_range (TYPE_MIN_VALUE (long_long_integer_type_node),
+ r0 = int_range<1> (TYPE_MIN_VALUE (long_long_integer_type_node),
TYPE_MAX_VALUE (long_long_integer_type_node));
range_cast (r0, short_unsigned_type_node);
- r1 = value_range (TYPE_MIN_VALUE (short_unsigned_type_node),
+ r1 = int_range<1> (TYPE_MIN_VALUE (short_unsigned_type_node),
TYPE_MAX_VALUE (short_unsigned_type_node));
ASSERT_TRUE (r0 == r1);
// NOT([10,20]) ==> [-MIN,9][21,MAX].
- r0 = r1 = value_range (INT (10), INT (20));
- r2 = value_range (minint, INT(9));
- r2.union_ (value_range (INT(21), maxint));
+ r0 = r1 = int_range<1> (INT (10), INT (20));
+ r2 = int_range<1> (minint, INT(9));
+ r2.union_ (int_range<1> (INT(21), maxint));
ASSERT_FALSE (r2.undefined_p ());
r1.invert ();
ASSERT_TRUE (r1 == r2);
// Test that booleans and their inverse work as expected.
r0 = range_zero (boolean_type_node);
- ASSERT_TRUE (r0 == value_range (build_zero_cst (boolean_type_node),
- build_zero_cst (boolean_type_node)));
+ ASSERT_TRUE (r0 == int_range<1> (build_zero_cst (boolean_type_node),
+ build_zero_cst (boolean_type_node)));
r0.invert ();
- ASSERT_TRUE (r0 == value_range (build_one_cst (boolean_type_node),
- build_one_cst (boolean_type_node)));
+ ASSERT_TRUE (r0 == int_range<1> (build_one_cst (boolean_type_node),
+ build_one_cst (boolean_type_node)));
// Casting NONZERO to a narrower type will wrap/overflow so
// it's just the entire range for the narrower type.
{
r0 = range_nonzero (integer_type_node);
range_cast (r0, short_integer_type_node);
- r1 = value_range (TYPE_MIN_VALUE (short_integer_type_node),
- TYPE_MAX_VALUE (short_integer_type_node));
+ r1 = int_range<1> (TYPE_MIN_VALUE (short_integer_type_node),
+ TYPE_MAX_VALUE (short_integer_type_node));
ASSERT_TRUE (r0 == r1);
}
// Converting this to 32-bits signed is [-MIN_16,-1][1, +MAX_16].
r0 = range_nonzero (short_integer_type_node);
range_cast (r0, integer_type_node);
- r1 = value_range (INT (-32768), INT (-1));
- r2 = value_range (INT (1), INT (32767));
+ r1 = int_range<1> (INT (-32768), INT (-1));
+ r2 = int_range<1> (INT (1), INT (32767));
r1.union_ (r2);
ASSERT_TRUE (r0 == r1);
ASSERT_TRUE (r0 == r1);
// [10,20] U [15, 30] => [10, 30].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (15), INT (30));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (15), INT (30));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (10), INT (30)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (30)));
// [15,40] U [] => [15,40].
- r0 = value_range (INT (15), INT (40));
+ r0 = int_range<1> (INT (15), INT (40));
r1.set_undefined ();
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (15), INT (40)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (40)));
// [10,20] U [10,10] => [10,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (10), INT (10));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (10), INT (10));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (10), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (10), INT (20)));
// [10,20] U [9,9] => [9,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (9), INT (9));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (9), INT (9));
r0.union_ (r1);
- ASSERT_TRUE (r0 == value_range (INT (9), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (9), INT (20)));
// [10,20] ^ [15,30] => [15,20].
- r0 = value_range (INT (10), INT (20));
- r1 = value_range (INT (15), INT (30));
+ r0 = int_range<1> (INT (10), INT (20));
+ r1 = int_range<1> (INT (15), INT (30));
r0.intersect (r1);
- ASSERT_TRUE (r0 == value_range (INT (15), INT (20)));
+ ASSERT_TRUE (r0 == int_range<1> (INT (15), INT (20)));
// Test the internal sanity of wide_int's wrt HWIs.
ASSERT_TRUE (wi::max_value (TYPE_PRECISION (boolean_type_node),
== wi::uhwi (1, TYPE_PRECISION (boolean_type_node)));
// Test zero_p().
- r0 = value_range (INT (0), INT (0));
+ r0 = int_range<1> (INT (0), INT (0));
ASSERT_TRUE (r0.zero_p ());
// Test nonzero_p().
- r0 = value_range (INT (0), INT (0));
+ r0 = int_range<1> (INT (0), INT (0));
r0.invert ();
ASSERT_TRUE (r0.nonzero_p ());
+
+ multi_precision_range_tests ();
+ widest_irange_tests ();
+ operator_tests ();
}
} // namespace selftest
/* Support routines for value ranges.
Copyright (C) 2019-2020 Free Software Foundation, Inc.
+ Major hacks by Aldy Hernandez <aldyh@redhat.com> and
+ Andrew MacLeod <amacleod@redhat.com>.
This file is part of GCC.
#include "tree-pretty-print.h"
#include "fold-const.h"
-value_range::value_range (tree min, tree max, value_range_kind kind)
+// Here we copy between any two irange's. The ranges can be legacy or
+// multi-ranges, and copying between any combination works correctly.
+
+irange &
+irange::operator= (const irange &src)
+{
+ if (legacy_mode_p () != src.legacy_mode_p ())
+ {
+ copy_legacy_range (src);
+ return *this;
+ }
+ if (legacy_mode_p ())
+ {
+ gcc_checking_assert (src.legacy_mode_p ());
+ m_num_ranges = src.m_num_ranges;
+ m_base[0] = src.m_base[0];
+ m_base[1] = src.m_base[1];
+ m_kind = src.m_kind;
+ return *this;
+ }
+
+ unsigned x;
+ unsigned lim = src.m_num_ranges;
+ if (lim > m_max_ranges)
+ lim = m_max_ranges;
+
+ for (x = 0; x < lim * 2; ++x)
+ m_base[x] = src.m_base[x];
+
+ // If the range didn't fit, the last range should cover the rest.
+ if (lim != src.m_num_ranges)
+ m_base[x - 1] = src.m_base[src.m_num_ranges * 2 - 1];
+
+ m_num_ranges = lim;
+ return *this;
+}
+
+// Return TRUE if range is a multi-range that can be represented as a
+// VR_ANTI_RANGE.
+
+bool
+irange::maybe_anti_range () const
{
- set (min, max, kind);
+ tree ttype = type ();
+ unsigned int precision = TYPE_PRECISION (ttype);
+ signop sign = TYPE_SIGN (ttype);
+ return (num_pairs () > 1
+ && precision > 1
+ && lower_bound () == wi::min_value (precision, sign)
+ && upper_bound () == wi::max_value (precision, sign));
}
-value_range::value_range (tree type)
+// Copy between a legacy and a multi-range, or vice-versa.
+
+void
+irange::copy_legacy_range (const irange &src)
{
- set_varying (type);
+ gcc_checking_assert (src.legacy_mode_p () != legacy_mode_p ());
+ if (src.undefined_p ())
+ set_undefined ();
+ else if (src.varying_p ())
+ set_varying (src.type ());
+ else if (src.kind () == VR_ANTI_RANGE)
+ set (src.min (), src.max (), VR_ANTI_RANGE);
+ else if (legacy_mode_p () && src.maybe_anti_range ())
+ {
+ int_range<3> tmp (src);
+ tmp.invert ();
+ set (tmp.min (), wide_int_to_tree (src.type (), tmp.upper_bound (0)),
+ VR_ANTI_RANGE);
+ }
+ else
+ set (src.min (), src.max (), VR_RANGE);
}
-value_range::value_range (tree type,
- const wide_int &wmin, const wide_int &wmax,
- enum value_range_kind kind)
+// Swap min/max if they are out of order. Return TRUE if further
+// processing of the range is necessary, FALSE otherwise.
+
+bool
+irange::swap_out_of_order_endpoints (tree &min, tree &max,
+ value_range_kind &kind)
{
- tree min = wide_int_to_tree (type, wmin);
- tree max = wide_int_to_tree (type, wmax);
- gcc_checking_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
- set (min, max, kind);
+ /* Wrong order for min and max, to swap them and the VR type we need
+ to adjust them. */
+ if (tree_int_cst_lt (max, min))
+ {
+ tree one, tmp;
+
+ /* For one bit precision if max < min, then the swapped
+ range covers all values, so for VR_RANGE it is varying and
+ for VR_ANTI_RANGE empty range, so drop to varying as well. */
+ if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
+ {
+ set_varying (TREE_TYPE (min));
+ return false;
+ }
+
+ one = build_int_cst (TREE_TYPE (min), 1);
+ tmp = int_const_binop (PLUS_EXPR, max, one);
+ max = int_const_binop (MINUS_EXPR, min, one);
+ min = tmp;
+
+ /* There's one corner case, if we had [C+1, C] before we now have
+ that again. But this represents an empty value range, so drop
+ to varying in this case. */
+ if (tree_int_cst_lt (max, min))
+ {
+ set_varying (TREE_TYPE (min));
+ return false;
+ }
+ kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ }
+ return true;
}
void
-value_range::set_undefined ()
+irange::irange_set (tree min, tree max)
{
- m_kind = VR_UNDEFINED;
- m_min = m_max = NULL;
+ gcc_checking_assert (!POLY_INT_CST_P (min));
+ gcc_checking_assert (!POLY_INT_CST_P (max));
+
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
+ if (flag_checking)
+ verify_range ();
}
void
-value_range::set_varying (tree type)
+irange::irange_set_anti_range (tree min, tree max)
{
- m_kind = VR_VARYING;
- if (supports_type_p (type))
+ gcc_checking_assert (!POLY_INT_CST_P (min));
+ gcc_checking_assert (!POLY_INT_CST_P (max));
+
+ // set an anti-range
+ tree type = TREE_TYPE (min);
+ signop sign = TYPE_SIGN (type);
+ int_range<2> type_range (type);
+ // Calculate INVERSE([I,J]) as [-MIN, I-1][J+1, +MAX].
+ m_num_ranges = 0;
+ wi::overflow_type ovf;
+
+ wide_int w_min = wi::to_wide (min);
+ if (wi::ne_p (w_min, type_range.lower_bound ()))
{
- m_min = vrp_val_min (type);
- m_max = vrp_val_max (type);
+ wide_int lim1 = wi::sub (w_min, 1, sign, &ovf);
+ gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
+ m_base[0] = type_range.tree_lower_bound (0);
+ m_base[1] = wide_int_to_tree (type, lim1);
+ m_num_ranges = 1;
}
- else
- /* We can't do anything range-wise with these types. */
- m_min = m_max = error_mark_node;
+ wide_int w_max = wi::to_wide (max);
+ if (wi::ne_p (w_max, type_range.upper_bound ()))
+ {
+ wide_int lim2 = wi::add (w_max, 1, sign, &ovf);
+ gcc_checking_assert (ovf != wi::OVF_OVERFLOW);
+ m_base[m_num_ranges * 2] = wide_int_to_tree (type, lim2);
+ m_base[m_num_ranges * 2 + 1] = type_range.tree_upper_bound (0);
+ ++m_num_ranges;
+ }
+ if (flag_checking)
+ verify_range ();
}
/* Set value range to the canonical form of {VRTYPE, MIN, MAX, EQUIV}.
extract ranges from var + CST op limit. */
void
-value_range::set (tree min, tree max, value_range_kind kind)
+irange::set (tree min, tree max, value_range_kind kind)
{
- /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (!legacy_mode_p ())
+ {
+ if (kind == VR_RANGE)
+ irange_set (min, max);
+ else
+ {
+ gcc_checking_assert (kind == VR_ANTI_RANGE);
+ irange_set_anti_range (min, max);
+ }
+ return;
+ }
if (kind == VR_UNDEFINED)
{
set_undefined ();
return;
}
-
if (kind == VR_RANGE)
{
/* Convert POLY_INT_CST bounds into worst-case INTEGER_CST bounds. */
}
else if (kind != VR_VARYING)
{
- if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
- kind = VR_VARYING;
+ if (POLY_INT_CST_P (min) || POLY_INT_CST_P (max))
+ kind = VR_VARYING;
}
-
if (kind == VR_VARYING)
{
- gcc_assert (TREE_TYPE (min) == TREE_TYPE (max));
- tree typ = TREE_TYPE (min);
- if (supports_type_p (typ))
- {
- gcc_assert (vrp_val_min (typ));
- gcc_assert (vrp_val_max (typ));
- }
- set_varying (typ);
+ set_varying (TREE_TYPE (min));
return;
}
- /* Nothing to canonicalize for symbolic ranges. */
+ tree type = TREE_TYPE (min);
+ // Nothing to canonicalize for symbolic ranges.
if (TREE_CODE (min) != INTEGER_CST
|| TREE_CODE (max) != INTEGER_CST)
{
m_kind = kind;
- m_min = min;
- m_max = max;
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
return;
}
+ if (!swap_out_of_order_endpoints (min, max, kind))
+ goto cleanup_set;
- /* Wrong order for min and max, to swap them and the VR type we need
- to adjust them. */
- if (tree_int_cst_lt (max, min))
- {
- tree one, tmp;
-
- /* For one bit precision if max < min, then the swapped
- range covers all values, so for VR_RANGE it is varying and
- for VR_ANTI_RANGE empty range, so drop to varying as well. */
- if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- one = build_int_cst (TREE_TYPE (min), 1);
- tmp = int_const_binop (PLUS_EXPR, max, one);
- max = int_const_binop (MINUS_EXPR, min, one);
- min = tmp;
-
- /* There's one corner case, if we had [C+1, C] before we now have
- that again. But this represents an empty value range, so drop
- to varying in this case. */
- if (tree_int_cst_lt (max, min))
- {
- set_varying (TREE_TYPE (min));
- return;
- }
-
- kind = kind == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
- }
-
- tree type = TREE_TYPE (min);
-
- /* Anti-ranges that can be represented as ranges should be so. */
+ // Anti-ranges that can be represented as ranges should be so.
if (kind == VR_ANTI_RANGE)
{
/* For -fstrict-enums we may receive out-of-range ranges so consider
kind = VR_RANGE;
}
}
+ else if (!swap_out_of_order_endpoints (min, max, kind))
+ goto cleanup_set;
- /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+ /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
+ to make sure VRP iteration terminates, otherwise we can get into
+ oscillations. */
+ if (!normalize_min_max (type, min, max, kind))
+ {
+ m_kind = kind;
+ m_base[0] = min;
+ m_base[1] = max;
+ m_num_ranges = 1;
+ if (flag_checking)
+ verify_range ();
+ }
- Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
- restrict those to a subset of what actually fits in the type.
- Instead use the extremes of the type precision which will allow
- compare_range_with_value() to check if a value is inside a range,
- whereas if we used TYPE_*_VAL, said function would just punt
- upon seeing a VARYING. */
+ cleanup_set:
+ // Avoid using TYPE_{MIN,MAX}_VALUE because -fstrict-enums can
+ // restrict those to a subset of what actually fits in the type.
+ // Instead use the extremes of the type precision
unsigned prec = TYPE_PRECISION (type);
signop sign = TYPE_SIGN (type);
if (wi::eq_p (wi::to_wide (min), wi::min_value (prec, sign))
&& wi::eq_p (wi::to_wide (max), wi::max_value (prec, sign)))
- {
- if (kind == VR_RANGE)
- set_varying (type);
- else if (kind == VR_ANTI_RANGE)
- set_undefined ();
- else
- gcc_unreachable ();
- return;
- }
-
- /* Do not drop [-INF(OVF), +INF(OVF)] to varying. (OVF) has to be sticky
- to make sure VRP iteration terminates, otherwise we can get into
- oscillations. */
-
- m_kind = kind;
- m_min = min;
- m_max = max;
+ m_kind = VR_VARYING;
+ else if (undefined_p ())
+ m_kind = VR_UNDEFINED;
if (flag_checking)
- check ();
-}
-
-void
-value_range::set (tree val)
-{
- gcc_assert (TREE_CODE (val) == SSA_NAME || is_gimple_min_invariant (val));
- if (TREE_OVERFLOW_P (val))
- val = drop_tree_overflow (val);
- set (val, val);
-}
-
-/* Set value range VR to a nonzero range of type TYPE. */
-
-void
-value_range::set_nonzero (tree type)
-{
- tree zero = build_int_cst (type, 0);
- set (zero, zero, VR_ANTI_RANGE);
-}
-
-/* Set value range VR to a ZERO range of type TYPE. */
-
-void
-value_range::set_zero (tree type)
-{
- set (build_int_cst (type, 0));
+ verify_range ();
}
/* Check the validity of the range. */
void
-value_range::check ()
+irange::verify_range ()
{
- switch (m_kind)
+ if (!legacy_mode_p ())
{
- case VR_RANGE:
- case VR_ANTI_RANGE:
- {
- gcc_assert (m_min && m_max);
- gcc_assert (!TREE_OVERFLOW_P (m_min) && !TREE_OVERFLOW_P (m_max));
-
- /* Creating ~[-MIN, +MAX] is stupid because that would be
- the empty set. */
- if (INTEGRAL_TYPE_P (TREE_TYPE (m_min)) && m_kind == VR_ANTI_RANGE)
- gcc_assert (!vrp_val_is_min (m_min) || !vrp_val_is_max (m_max));
+ gcc_checking_assert (m_kind == VR_RANGE);
+ for (unsigned i = 0; i < m_num_ranges; ++i)
+ {
+ tree lb = tree_lower_bound (i);
+ tree ub = tree_upper_bound (i);
+ int c = compare_values (lb, ub);
+ gcc_assert (c == 0 || c == -1);
+ }
+ return;
+ }
- int cmp = compare_values (m_min, m_max);
- gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
- break;
- }
+ switch (m_kind)
+ {
case VR_UNDEFINED:
- gcc_assert (!min () && !max ());
+ gcc_assert (m_num_ranges == 0);
break;
+
case VR_VARYING:
- gcc_assert (m_min && m_max);
+ gcc_assert (m_num_ranges == 1);
break;
+
+ case VR_ANTI_RANGE:
+ case VR_RANGE:
+ {
+ gcc_assert (m_num_ranges == 1);
+ int cmp = compare_values (tree_lower_bound (0), tree_upper_bound (0));
+ gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+ return;
+ }
+
default:
gcc_unreachable ();
}
}
-/* Return the number of sub-ranges in a range. */
-
unsigned
-value_range::num_pairs () const
+irange::legacy_num_pairs () const
{
+ gcc_checking_assert (legacy_mode_p ());
+
if (undefined_p ())
return 0;
if (varying_p ())
return 1;
- if (symbolic_p ())
+ // Inlined symbolic_p for performance:
+ if (!is_gimple_min_invariant (min ()) || !is_gimple_min_invariant (max ()))
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
{
// ~[MIN, X] has one sub-range of [X+1, MAX], and
// ~[X, MAX] has one sub-range of [MIN, X-1].
- if (vrp_val_is_min (m_min) || vrp_val_is_max (m_max))
+ if (vrp_val_is_min (min ()) || vrp_val_is_max (max ()))
return 1;
return 2;
}
+ gcc_checking_assert (m_num_ranges == 1);
return 1;
}
-/* Return the lower bound for a sub-range. PAIR is the sub-range in
- question. */
+// Return the lower bound for a sub-range. PAIR is the sub-range in
+// question.
wide_int
-value_range::lower_bound (unsigned pair) const
+irange::legacy_lower_bound (unsigned pair) const
{
+ gcc_checking_assert (legacy_mode_p ());
if (symbolic_p ())
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
- return numeric_range.lower_bound (pair);
+ return numeric_range.legacy_lower_bound (pair);
}
-
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
- tree t = NULL;
if (m_kind == VR_ANTI_RANGE)
{
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
- t = wide_int_to_tree (typ, wi::to_wide (m_max) + 1);
+ tree typ = type (), t;
+ if (pair == 1 || vrp_val_is_min (min ()))
+ t = wide_int_to_tree (typ, wi::to_wide (max ()) + 1);
else
t = vrp_val_min (typ);
+ return wi::to_wide (t);
}
- else
- t = m_min;
- return wi::to_wide (t);
+ return wi::to_wide (tree_lower_bound (pair));
}
-/* Return the upper bound for a sub-range. PAIR is the sub-range in
- question. */
+// Return the upper bound for a sub-range. PAIR is the sub-range in
+// question.
wide_int
-value_range::upper_bound (unsigned pair) const
+irange::legacy_upper_bound (unsigned pair) const
{
+ gcc_checking_assert (legacy_mode_p ());
if (symbolic_p ())
{
value_range numeric_range (*this);
numeric_range.normalize_symbolics ();
- return numeric_range.upper_bound (pair);
+ return numeric_range.legacy_upper_bound (pair);
}
-
gcc_checking_assert (!undefined_p ());
gcc_checking_assert (pair + 1 <= num_pairs ());
- tree t = NULL;
if (m_kind == VR_ANTI_RANGE)
{
- tree typ = type ();
- if (pair == 1 || vrp_val_is_min (m_min))
+ tree typ = type (), t;
+ if (pair == 1 || vrp_val_is_min (min ()))
t = vrp_val_max (typ);
else
- t = wide_int_to_tree (typ, wi::to_wide (m_min) - 1);
+ t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
+ return wi::to_wide (t);
}
- else
- t = m_max;
- return wi::to_wide (t);
-}
-
-/* Return the highest bound in a range. */
-
-wide_int
-value_range::upper_bound () const
-{
- unsigned pairs = num_pairs ();
- gcc_checking_assert (pairs > 0);
- return upper_bound (pairs - 1);
+ return wi::to_wide (tree_upper_bound (pair));
}
bool
-value_range::equal_p (const value_range &other) const
+irange::legacy_equal_p (const irange &other) const
{
- /* Ignore types for undefined. All undefines are equal. */
- if (undefined_p ())
- return m_kind == other.m_kind;
+ gcc_checking_assert (legacy_mode_p () && other.legacy_mode_p ());
- return (m_kind == other.m_kind
- && vrp_operand_equal_p (m_min, other.m_min)
- && vrp_operand_equal_p (m_max, other.m_max));
+ if (m_kind != other.m_kind)
+ return false;
+ if (m_kind == VR_UNDEFINED || m_kind == VR_VARYING)
+ return true;
+ return (vrp_operand_equal_p (tree_lower_bound (0),
+ other.tree_lower_bound (0))
+ && vrp_operand_equal_p (tree_upper_bound (0),
+ other.tree_upper_bound (0)));
}
bool
-value_range::operator== (const value_range &r) const
+irange::equal_p (const irange &other) const
{
- return equal_p (r);
+ if (legacy_mode_p ())
+ {
+ if (other.legacy_mode_p ())
+ return legacy_equal_p (other);
+ value_range tmp (other);
+ return legacy_equal_p (tmp);
+ }
+ if (other.legacy_mode_p ())
+ {
+ value_range tmp2 (*this);
+ return tmp2.legacy_equal_p (other);
+ }
+
+ if (m_num_ranges != other.m_num_ranges)
+ return false;
+
+ for (unsigned i = 0; i < m_num_ranges; ++i)
+ {
+ tree lb = tree_lower_bound (i);
+ tree ub = tree_upper_bound (i);
+ tree lb_other = other.tree_lower_bound (i);
+ tree ub_other = other.tree_upper_bound (i);
+ if (!operand_equal_p (lb, lb_other, 0)
+ || !operand_equal_p (ub, ub_other, 0))
+ return false;
+ }
+ return true;
}
-/* If range is a singleton, place it in RESULT and return TRUE.
- Note: A singleton can be any gimple invariant, not just constants.
- So, [&x, &x] counts as a singleton. */
/* Return TRUE if this is a symbolic range. */
bool
-value_range::symbolic_p () const
+irange::symbolic_p () const
{
return (!varying_p ()
&& !undefined_p ()
- && (!is_gimple_min_invariant (m_min)
- || !is_gimple_min_invariant (m_max)));
+ && (!is_gimple_min_invariant (min ())
+ || !is_gimple_min_invariant (max ())));
}
/* NOTE: This is not the inverse of symbolic_p because the range
constants would be represented as [-MIN, +MAX]. */
bool
-value_range::constant_p () const
+irange::constant_p () const
{
return (!varying_p ()
&& !undefined_p ()
- && TREE_CODE (m_min) == INTEGER_CST
- && TREE_CODE (m_max) == INTEGER_CST);
+ && TREE_CODE (min ()) == INTEGER_CST
+ && TREE_CODE (max ()) == INTEGER_CST);
}
+/* If range is a singleton, place it in RESULT and return TRUE.
+ Note: A singleton can be any gimple invariant, not just constants.
+ So, [&x, &x] counts as a singleton. */
+
bool
-value_range::singleton_p (tree *result) const
+irange::singleton_p (tree *result) const
{
+ if (!legacy_mode_p ())
+ {
+ if (num_pairs () == 1 && (wi::to_wide (tree_lower_bound ())
+ == wi::to_wide (tree_upper_bound ())))
+ {
+ if (result)
+ *result = tree_lower_bound ();
+ return true;
+ }
+ return false;
+ }
if (m_kind == VR_ANTI_RANGE)
{
if (nonzero_p ())
if (TYPE_PRECISION (type ()) == 1)
{
if (result)
- *result = m_max;
+ *result = max ();
return true;
}
return false;
if (num_pairs () == 1)
{
value_range vr0, vr1;
- ranges_from_anti_range (this, &vr0, &vr1);
+ ranges_from_anti_range ((const value_range *) this, &vr0, &vr1);
return vr0.singleton_p (result);
}
}
+ // Catches non-numeric extremes as well.
if (m_kind == VR_RANGE
&& vrp_operand_equal_p (min (), max ())
&& is_gimple_min_invariant (min ()))
}
/* Return 1 if VAL is inside value range.
- 0 if VAL is not inside value range.
+ 0 if VAL is not inside value range.
-2 if we cannot tell either way.
Benchmark compile/20001226-1.c compilation time after changing this
function. */
int
-value_range::value_inside_range (tree val) const
+irange::value_inside_range (tree val) const
{
- int cmp1, cmp2;
-
if (varying_p ())
return 1;
if (undefined_p ())
return 0;
- cmp1 = operand_less_p (val, m_min);
+ if (!legacy_mode_p () && TREE_CODE (val) == INTEGER_CST)
+ return contains_p (val);
+
+ int cmp1 = operand_less_p (val, min ());
if (cmp1 == -2)
return -2;
if (cmp1 == 1)
return m_kind != VR_RANGE;
- cmp2 = operand_less_p (m_max, val);
+ int cmp2 = operand_less_p (max (), val);
if (cmp2 == -2)
return -2;
/* Return TRUE if it is possible that range contains VAL. */
bool
-value_range::may_contain_p (tree val) const
+irange::may_contain_p (tree val) const
{
return value_inside_range (val) != 0;
}
/* Return TRUE if range contains INTEGER_CST. */
+/* Return 1 if VAL is inside value range.
+ 0 if VAL is not inside value range.
+
+ Benchmark compile/20001226-1.c compilation time after changing this
+ function. */
+
bool
-value_range::contains_p (tree cst) const
+irange::contains_p (tree cst) const
{
+ if (undefined_p ())
+ return false;
+
+ if (legacy_mode_p ())
+ {
+ gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
+ if (symbolic_p ())
+ {
+ value_range numeric_range (*this);
+ numeric_range.normalize_symbolics ();
+ return numeric_range.contains_p (cst);
+ }
+ return value_inside_range (cst) == 1;
+ }
+
gcc_checking_assert (TREE_CODE (cst) == INTEGER_CST);
- if (symbolic_p ())
+ signop sign = TYPE_SIGN (TREE_TYPE (cst));
+ wide_int v = wi::to_wide (cst);
+ for (unsigned r = 0; r < m_num_ranges; ++r)
{
- value_range numeric_range (*this);
- numeric_range.normalize_symbolics ();
- return numeric_range.contains_p (cst);
+ if (wi::lt_p (v, lower_bound (r), sign))
+ return false;
+ if (wi::le_p (v, upper_bound (r), sign))
+ return true;
}
- return value_inside_range (cst) == 1;
+
+ return false;
}
+
/* Normalize addresses into constants. */
void
-value_range::normalize_addresses ()
+irange::normalize_addresses ()
{
if (undefined_p ())
return;
if (!range_includes_zero_p (this))
{
- gcc_checking_assert (TREE_CODE (m_min) == ADDR_EXPR
- || TREE_CODE (m_max) == ADDR_EXPR);
+ gcc_checking_assert (TREE_CODE (min ()) == ADDR_EXPR
+ || TREE_CODE (max ()) == ADDR_EXPR);
set_nonzero (type ());
return;
}
/* Normalize symbolics and addresses into constants. */
void
-value_range::normalize_symbolics ()
+irange::normalize_symbolics ()
{
if (varying_p () || undefined_p ())
return;
}
/* Helper for the intersection operation for value ranges. Given two
- value ranges VR0 and VR1, return the intersection of the two
- ranges. This may not be the smallest possible such range. */
+ ranges VR0 and VR1, set VR0 to the intersection of both ranges.
+ This may not be the smallest possible such range. */
-value_range
-value_range::intersect_helper (const value_range *vr0, const value_range *vr1)
+void
+irange::legacy_intersect (irange *vr0, const irange *vr1)
{
/* If either range is VR_VARYING the other one wins. */
if (vr1->varying_p ())
- return *vr0;
+ return;
if (vr0->varying_p ())
- return *vr1;
+ {
+ /* Avoid the full copy if we already know both sides are simple
+ and can be trivially copied. */
+ if (vr1->legacy_mode_p ())
+ {
+ vr0->set (vr1->min (), vr1->max (), vr1->kind ());
+ return;
+ }
+ *vr0 = *vr1;
+ return;
+ }
/* When either range is VR_UNDEFINED the resulting range is
VR_UNDEFINED, too. */
if (vr0->undefined_p ())
- return *vr0;
+ return;
if (vr1->undefined_p ())
- return *vr1;
+ {
+ vr0->set_undefined ();
+ return;
+ }
value_range_kind vr0kind = vr0->kind ();
tree vr0min = vr0->min ();
tree vr0max = vr0->max ();
- intersect_ranges (&vr0kind, &vr0min, &vr0max,
- vr1->kind (), vr1->min (), vr1->max ());
+ /* Handle multi-ranges that can be represented as anti-ranges. */
+ if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ())
+ {
+ int_range<3> tmp (*vr1);
+ tmp.invert ();
+ intersect_ranges (&vr0kind, &vr0min, &vr0max,
+ VR_ANTI_RANGE, tmp.min (), tmp.max ());
+ }
+ else
+ intersect_ranges (&vr0kind, &vr0min, &vr0max,
+ vr1->kind (), vr1->min (), vr1->max ());
+
/* Make sure to canonicalize the result though as the inversion of a
- VR_RANGE can still be a VR_RANGE. Work on a temporary so we can
- fall back to vr0 when this turns things to varying. */
- value_range tem;
+ VR_RANGE can still be a VR_RANGE. */
if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
+ vr0->set_undefined ();
else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
+ {
+ /* If we failed, use the original VR0. */
+ return;
+ }
else
- tem.set (vr0min, vr0max, vr0kind);
- /* If that failed, use the saved original VR0. */
- if (tem.varying_p ())
- return *vr0;
-
- return tem;
+ vr0->set (vr0min, vr0max, vr0kind);
}
/* Union the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
*vr0max = NULL_TREE;
}
-/* Helper for meet operation for value ranges. Given two value ranges VR0 and
- VR1, return a range that contains both VR0 and VR1. This may not be the
+/* Helper for meet operation for value ranges. Given two ranges VR0
+ and VR1, set VR0 to the union of both ranges. This may not be the
smallest possible such range. */
-value_range
-value_range::union_helper (const value_range *vr0, const value_range *vr1)
+void
+irange::legacy_union (irange *vr0, const irange *vr1)
{
/* VR0 has the resulting range if VR1 is undefined or VR0 is varying. */
if (vr1->undefined_p ()
|| vr0->varying_p ())
- return *vr0;
+ return;
/* VR1 has the resulting range if VR0 is undefined or VR1 is varying. */
- if (vr0->undefined_p ()
- || vr1->varying_p ())
- return *vr1;
+ if (vr0->undefined_p ())
+ {
+ /* Avoid the full copy if we already know both sides are simple
+ and can be trivially copied. */
+ if (vr1->legacy_mode_p ())
+ {
+ vr0->set (vr1->min (), vr1->max (), vr1->kind ());
+ return;
+ }
+ *vr0 = *vr1;
+ return;
+ }
+ if (vr1->varying_p ())
+ {
+ vr0->set_varying (vr1->type ());
+ return;
+ }
value_range_kind vr0kind = vr0->kind ();
tree vr0min = vr0->min ();
tree vr0max = vr0->max ();
- union_ranges (&vr0kind, &vr0min, &vr0max,
- vr1->kind (), vr1->min (), vr1->max ());
+ /* Handle multi-ranges that can be represented as anti-ranges. */
+ if (!vr1->legacy_mode_p () && vr1->maybe_anti_range ())
+ {
+ int_range<3> tmp (*vr1);
+ tmp.invert ();
+ union_ranges (&vr0kind, &vr0min, &vr0max,
+ VR_ANTI_RANGE, tmp.min (), tmp.max ());
+ }
+ else
+ union_ranges (&vr0kind, &vr0min, &vr0max,
+ vr1->kind (), vr1->min (), vr1->max ());
- /* Work on a temporary so we can still use vr0 when union returns varying. */
- value_range tem;
if (vr0kind == VR_UNDEFINED)
- tem.set_undefined ();
+ vr0->set_undefined ();
else if (vr0kind == VR_VARYING)
- tem.set_varying (vr0->type ());
- else
- tem.set (vr0min, vr0max, vr0kind);
-
- /* Failed to find an efficient meet. Before giving up and setting
- the result to VARYING, see if we can at least derive a useful
- anti-range. */
- if (tem.varying_p ()
- && range_includes_zero_p (vr0) == 0
- && range_includes_zero_p (vr1) == 0)
{
- tem.set_nonzero (vr0->type ());
- return tem;
+ /* Failed to find an efficient meet. Before giving up and
+ setting the result to VARYING, see if we can at least derive
+ a non-zero range. */
+ if (range_includes_zero_p (vr0) == 0
+ && range_includes_zero_p (vr1) == 0)
+ vr0->set_nonzero (vr0->type ());
+ else
+ vr0->set_varying (vr0->type ());
}
-
- return tem;
+ else
+ vr0->set (vr0min, vr0max, vr0kind);
}
/* Meet operation for value ranges. Given two value ranges VR0 and
may not be the smallest possible such range. */
void
-value_range::union_ (const value_range *other)
+irange::union_ (const irange *other)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (legacy_mode_p ())
{
- fprintf (dump_file, "Meeting\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, other);
- fprintf (dump_file, "\n");
- }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Meeting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
- *this = union_helper (this, other);
+ legacy_union (this, other);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+ return;
+ }
+
+ if (other->legacy_mode_p ())
{
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
+ int_range<2> wider;
+ wider = *other;
+ irange_union (wider);
}
+ else
+ irange_union (*other);
}
-/* Range union, but for references. */
-
void
-value_range::union_ (const value_range &r)
+irange::intersect (const irange *other)
{
- /* Disable details for now, because it makes the ranger dump
- unnecessarily verbose. */
- bool details = dump_flags & TDF_DETAILS;
- if (details)
- dump_flags &= ~TDF_DETAILS;
- union_ (&r);
- if (details)
- dump_flags |= TDF_DETAILS;
+ if (legacy_mode_p ())
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Intersecting\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, other);
+ fprintf (dump_file, "\n");
+ }
+
+ legacy_intersect (this, other);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, this);
+ fprintf (dump_file, "\n");
+ }
+ return;
+ }
+
+ if (other->legacy_mode_p ())
+ {
+ int_range<2> wider;
+ wider = *other;
+ irange_intersect (wider);
+ }
+ else
+ irange_intersect (*other);
}
+// union_ for multi-ranges.
+
void
-value_range::intersect (const value_range *other)
+irange::irange_union (const irange &r)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
+
+ if (r.undefined_p () || varying_p ())
+ return;
+
+ if (undefined_p () || r.varying_p ())
{
- fprintf (dump_file, "Intersecting\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\nand\n ");
- dump_value_range (dump_file, other);
- fprintf (dump_file, "\n");
+ operator= (r);
+ return;
}
- *this = intersect_helper (this, other);
+ // Do not worry about merging and such by reserving twice as many
+ // pairs as needed, and then simply sort the 2 ranges into this
+ // intermediate form.
+ //
+ // The intermediate result will have the property that the beginning
+ // of each range is <= the beginning of the next range. There may
+ // be overlapping ranges at this point. I.e. this would be valid
+ // [-20, 10], [-10, 0], [0, 20], [40, 90] as it satisfies this
+ // contraint : -20 < -10 < 0 < 40. When the range is rebuilt into r,
+ // the merge is performed.
+ //
+ // [Xi,Yi]..[Xn,Yn] U [Xj,Yj]..[Xm,Ym] --> [Xk,Yk]..[Xp,Yp]
+ tree ttype = r.type ();
+ signop sign = TYPE_SIGN (ttype);
+
+ auto_vec<tree, 20> res;
+ wide_int u1 ;
+ wi::overflow_type ovf;
+ unsigned i = 0, j = 0, k = 0;
+
+ while (i < m_num_ranges * 2 && j < r.m_num_ranges * 2)
+ {
+ // lower of Xi and Xj is the lowest point.
+ if (wi::le_p (wi::to_wide (m_base[i]), wi::to_wide (r.m_base[j]), sign))
+ {
+ res.safe_push (m_base[i]);
+ res.safe_push (m_base[i + 1]);
+ k += 2;
+ i += 2;
+ }
+ else
+ {
+ res.safe_push (r.m_base[j]);
+ res.safe_push (r.m_base[j + 1]);
+ k += 2;
+ j += 2;
+ }
+ }
+ for ( ; i < m_num_ranges * 2; i += 2)
+ {
+ res.safe_push (m_base[i]);
+ res.safe_push (m_base[i + 1]);
+ k += 2;
+ }
+ for ( ; j < r.m_num_ranges * 2; j += 2)
+ {
+ res.safe_push (r.m_base[j]);
+ res.safe_push (r.m_base[j + 1]);
+ k += 2;
+ }
- if (dump_file && (dump_flags & TDF_DETAILS))
+ // Now normalize the vector removing any overlaps.
+ i = 2;
+ int prec = TYPE_PRECISION (ttype);
+ wide_int max_val = wi::max_value (prec, sign);
+ for (j = 2; j < k ; j += 2)
{
- fprintf (dump_file, "to\n ");
- dump_value_range (dump_file, this);
- fprintf (dump_file, "\n");
+ wide_int val_im1 = wi::to_wide (res[i - 1]);
+ if (val_im1 == max_val)
+ break;
+ u1 = wi::add (val_im1, 1, sign, &ovf);
+
+ // Overflow indicates we are at MAX already.
+ // A wide int bug requires the previous max_val check
+ // trigger: gcc.c-torture/compile/pr80443.c with -O3
+ if (ovf == wi::OVF_OVERFLOW)
+ break;
+
+ wide_int val_j = wi::to_wide (res[j]);
+ wide_int val_jp1 = wi::to_wide (res[j+1]);
+ // Current upper+1 is >= lower bound next pair, then we merge ranges.
+ if (wi::ge_p (u1, val_j, sign))
+ {
+ // New upper bounds is greater of current or the next one.
+ if (wi::gt_p (val_jp1, val_im1, sign))
+ res [i - 1] = res[j + 1];
+ }
+ else
+ {
+ // This is a new distinct range, but no point in copying it
+ // if it is already in the right place.
+ if (i != j)
+ {
+ res[i++] = res[j];
+ res[i++] = res[j + 1];
+ }
+ else
+ i += 2;
+ }
}
+
+ // At this point, the vector should have i ranges, none overlapping.
+ // Now it simply needs to be copied, and if there are too many
+ // ranges, merge some. We wont do any analysis as to what the
+ // "best" merges are, simply combine the final ranges into one.
+ if (i > m_max_ranges * 2)
+ {
+ res[m_max_ranges * 2 - 1] = res[i - 1];
+ i = m_max_ranges * 2;
+ }
+
+ for (j = 0; j < i ; j++)
+ m_base[j] = res [j];
+ m_num_ranges = i / 2;
+
+ if (flag_checking)
+ verify_range ();
}
-/* Range intersect, but for references. */
+// intersect for multi-ranges.
void
-value_range::intersect (const value_range &r)
+irange::irange_intersect (const irange &r)
+{
+ gcc_checking_assert (!legacy_mode_p () && !r.legacy_mode_p ());
+
+ if (undefined_p () || r.varying_p ())
+ return;
+ if (r.undefined_p ())
+ {
+ set_undefined ();
+ return;
+ }
+ if (varying_p ())
+ {
+ operator= (r);
+ return;
+ }
+
+ signop sign = TYPE_SIGN (TREE_TYPE(m_base[0]));
+ unsigned bld_pair = 0;
+ unsigned bld_lim = m_max_ranges;
+ widest_irange r2 (*this);
+ unsigned r2_lim = r2.num_pairs ();
+ unsigned i2 = 0;
+ for (unsigned i = 0; i < r.num_pairs (); )
+ {
+ // If r1's upper is < r2's lower, we can skip r1's pair.
+ tree ru = r.m_base[i * 2 + 1];
+ tree r2l = r2.m_base[i2 * 2];
+ if (wi::lt_p (wi::to_wide (ru), wi::to_wide (r2l), sign))
+ {
+ i++;
+ continue;
+ }
+ // Likewise, skip r2's pair if its excluded.
+ tree r2u = r2.m_base[i2 * 2 + 1];
+ tree rl = r.m_base[i * 2];
+ if (wi::lt_p (wi::to_wide (r2u), wi::to_wide (rl), sign))
+ {
+ i2++;
+ if (i2 < r2_lim)
+ continue;
+ // No more r2, break.
+ break;
+ }
+
+ // Must be some overlap. Find the highest of the lower bounds,
+ // and set it, unless the build limits lower bounds is already
+ // set.
+ if (bld_pair < bld_lim)
+ {
+ if (wi::ge_p (wi::to_wide (rl), wi::to_wide (r2l), sign))
+ m_base[bld_pair * 2] = rl;
+ else
+ m_base[bld_pair * 2] = r2l;
+ }
+ else
+ // Decrease and set a new upper.
+ bld_pair--;
+
+ // ...and choose the lower of the upper bounds.
+ if (wi::le_p (wi::to_wide (ru), wi::to_wide (r2u), sign))
+ {
+ m_base[bld_pair * 2 + 1] = ru;
+ bld_pair++;
+ // Move past the r1 pair and keep trying.
+ i++;
+ continue;
+ }
+ else
+ {
+ m_base[bld_pair * 2 + 1] = r2u;
+ bld_pair++;
+ i2++;
+ if (i2 < r2_lim)
+ continue;
+ // No more r2, break.
+ break;
+ }
+ // r2 has the higher lower bound.
+ }
+
+ // At the exit of this loop, it is one of 2 things:
+ // ran out of r1, or r2, but either means we are done.
+ m_num_ranges = bld_pair;
+ if (flag_checking)
+ verify_range ();
+}
+
+static wide_int inline
+subtract_one (const wide_int &x, tree type, wi::overflow_type &overflow)
{
- /* Disable details for now, because it makes the ranger dump
- unnecessarily verbose. */
- bool details = dump_flags & TDF_DETAILS;
- if (details)
- dump_flags &= ~TDF_DETAILS;
- intersect (&r);
- if (details)
- dump_flags |= TDF_DETAILS;
+ // A signed 1-bit bit-field, has a range of [-1,0] so subtracting +1
+ // overflows, since +1 is unrepresentable. This is why we have an
+ // addition of -1 here.
+ if (TYPE_SIGN (type) == SIGNED)
+ return wi::add (x, -1 , SIGNED, &overflow);
+ else
+ return wi::sub (x, 1, UNSIGNED, &overflow);
}
/* Return the inverse of a range. */
void
-value_range::invert ()
+irange::invert ()
{
- /* We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
- create non-canonical ranges. Use the constructors instead. */
- if (m_kind == VR_RANGE)
- *this = value_range (m_min, m_max, VR_ANTI_RANGE);
- else if (m_kind == VR_ANTI_RANGE)
- *this = value_range (m_min, m_max);
+ if (legacy_mode_p ())
+ {
+ // We can't just invert VR_RANGE and VR_ANTI_RANGE because we may
+ // create non-canonical ranges. Use the constructors instead.
+ if (m_kind == VR_RANGE)
+ *this = value_range (min (), max (), VR_ANTI_RANGE);
+ else if (m_kind == VR_ANTI_RANGE)
+ *this = value_range (min (), max ());
+ else
+ gcc_unreachable ();
+ return;
+ }
+
+ gcc_assert (!undefined_p () && !varying_p ());
+
+ // We always need one more set of bounds to represent an inverse, so
+ // if we're at the limit, we can't properly represent things.
+ //
+ // For instance, to represent the inverse of a 2 sub-range set
+ // [5, 10][20, 30], we would need a 3 sub-range set
+ // [-MIN, 4][11, 19][31, MAX].
+ //
+ // In this case, return the most conservative thing.
+ //
+ // However, if any of the extremes of the range are -MIN/+MAX, we
+ // know we will not need an extra bound. For example:
+ //
+ // INVERT([-MIN,20][30,40]) => [21,29][41,+MAX]
+ // INVERT([-MIN,20][30,MAX]) => [21,29]
+ tree ttype = type ();
+ unsigned prec = TYPE_PRECISION (ttype);
+ signop sign = TYPE_SIGN (ttype);
+ wide_int type_min = wi::min_value (prec, sign);
+ wide_int type_max = wi::max_value (prec, sign);
+ if (m_num_ranges == m_max_ranges
+ && lower_bound () != type_min
+ && upper_bound () != type_max)
+ {
+ m_base[1] = wide_int_to_tree (ttype, type_max);
+ m_num_ranges = 1;
+ return;
+ }
+ // The algorithm is as follows. To calculate INVERT ([a,b][c,d]), we
+ // generate [-MIN, a-1][b+1, c-1][d+1, MAX].
+ //
+ // If there is an over/underflow in the calculation for any
+ // sub-range, we eliminate that subrange. This allows us to easily
+ // calculate INVERT([-MIN, 5]) with: [-MIN, -MIN-1][6, MAX]. And since
+ // we eliminate the underflow, only [6, MAX] remains.
+ unsigned i = 0;
+ wi::overflow_type ovf;
+ // Construct leftmost range.
+ widest_irange orig_range (*this);
+ unsigned nitems = 0;
+ wide_int tmp;
+ // If this is going to underflow on the MINUS 1, don't even bother
+ // checking. This also handles subtracting one from an unsigned 0,
+ // which doesn't set the underflow bit.
+ if (type_min != orig_range.lower_bound ())
+ {
+ m_base[nitems++] = wide_int_to_tree (ttype, type_min);
+ tmp = subtract_one (orig_range.lower_bound (), ttype, ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ if (ovf)
+ nitems = 0;
+ }
+ i++;
+ // Construct middle ranges if applicable.
+ if (orig_range.num_pairs () > 1)
+ {
+ unsigned j = i;
+ for (; j < (orig_range.num_pairs () * 2) - 1; j += 2)
+ {
+ // The middle ranges cannot have MAX/MIN, so there's no need
+ // to check for unsigned overflow on the +1 and -1 here.
+ tmp = wi::add (wi::to_wide (orig_range.m_base[j]), 1, sign, &ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ tmp = subtract_one (wi::to_wide (orig_range.m_base[j + 1]),
+ ttype, ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ if (ovf)
+ nitems -= 2;
+ }
+ i = j;
+ }
+ // Construct rightmost range.
+ //
+ // However, if this will overflow on the PLUS 1, don't even bother.
+ // This also handles adding one to an unsigned MAX, which doesn't
+ // set the overflow bit.
+ if (type_max != wi::to_wide (orig_range.m_base[i]))
+ {
+ tmp = wi::add (wi::to_wide (orig_range.m_base[i]), 1, sign, &ovf);
+ m_base[nitems++] = wide_int_to_tree (ttype, tmp);
+ m_base[nitems++] = wide_int_to_tree (ttype, type_max);
+ if (ovf)
+ nitems -= 2;
+ }
+ m_num_ranges = nitems / 2;
+
+ if (flag_checking)
+ verify_range ();
+}
+
+static void
+dump_bound_with_infinite_markers (FILE *file, tree bound)
+{
+ tree type = TREE_TYPE (bound);
+ if (INTEGRAL_TYPE_P (type)
+ && !TYPE_UNSIGNED (type)
+ && vrp_val_is_min (bound)
+ && TYPE_PRECISION (type) != 1)
+ fprintf (file, "-INF");
+ else if (vrp_val_is_max (bound)
+ && TYPE_PRECISION (type) != 1)
+ fprintf (file, "+INF");
else
- gcc_unreachable ();
+ print_generic_expr (file, bound);
}
void
-value_range::dump (FILE *file) const
+irange::dump (FILE *file) const
{
if (undefined_p ())
- fprintf (file, "UNDEFINED");
- else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
{
- tree ttype = type ();
-
- print_generic_expr (file, ttype);
- fprintf (file, " ");
-
+ fprintf (file, "UNDEFINED");
+ return;
+ }
+ print_generic_expr (file, type ());
+ fprintf (file, " ");
+ if (varying_p ())
+ {
+ fprintf (file, "VARYING");
+ return;
+ }
+ if (legacy_mode_p ())
+ {
fprintf (file, "%s[", (m_kind == VR_ANTI_RANGE) ? "~" : "");
-
- if (INTEGRAL_TYPE_P (ttype)
- && !TYPE_UNSIGNED (ttype)
- && vrp_val_is_min (min ())
- && TYPE_PRECISION (ttype) != 1)
- fprintf (file, "-INF");
- else
- print_generic_expr (file, min ());
-
+ dump_bound_with_infinite_markers (file, min ());
fprintf (file, ", ");
-
- if (supports_type_p (ttype)
- && vrp_val_is_max (max ())
- && TYPE_PRECISION (ttype) != 1)
- fprintf (file, "+INF");
- else
- print_generic_expr (file, max ());
-
+ dump_bound_with_infinite_markers (file, max ());
fprintf (file, "]");
+ return;
}
- else if (varying_p ())
+ for (unsigned i = 0; i < m_num_ranges; ++i)
{
- print_generic_expr (file, type ());
- fprintf (file, " VARYING");
+ tree lb = m_base[i * 2];
+ tree ub = m_base[i * 2 + 1];
+ fprintf (file, "[");
+ dump_bound_with_infinite_markers (file, lb);
+ fprintf (file, ", ");
+ dump_bound_with_infinite_markers (file, ub);
+ fprintf (file, "]");
}
- else
- gcc_unreachable ();
}
void
-value_range::dump () const
+dump_value_range (FILE *file, const irange *vr)
{
- dump (stderr);
+ vr->dump (file);
}
-void
-dump_value_range (FILE *file, const value_range *vr)
+DEBUG_FUNCTION void
+debug (const irange *vr)
{
- if (!vr)
- fprintf (file, "[]");
- else
- vr->dump (file);
+ dump_value_range (stderr, vr);
+ fprintf (stderr, "\n");
+}
+
+DEBUG_FUNCTION void
+debug (const irange &vr)
+{
+ debug (&vr);
}
DEBUG_FUNCTION void
debug (const value_range *vr)
{
dump_value_range (stderr, vr);
+ fprintf (stderr, "\n");
}
DEBUG_FUNCTION void
debug (const value_range &vr)
{
dump_value_range (stderr, &vr);
+ fprintf (stderr, "\n");
}
/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
}
bool
-range_has_numeric_bounds_p (const value_range *vr)
+range_has_numeric_bounds_p (const irange *vr)
{
- return (vr->min ()
+ return (!vr->undefined_p ()
&& TREE_CODE (vr->min ()) == INTEGER_CST
&& TREE_CODE (vr->max ()) == INTEGER_CST);
}
-/* Return the maximum value for TYPE. */
-
-tree
-vrp_val_max (const_tree type)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MAX_VALUE (type);
- if (POINTER_TYPE_P (type))
- {
- wide_int max = wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type));
- return wide_int_to_tree (const_cast<tree> (type), max);
- }
- return NULL_TREE;
-}
-
-/* Return the minimum value for TYPE. */
-
-tree
-vrp_val_min (const_tree type)
-{
- if (INTEGRAL_TYPE_P (type))
- return TYPE_MIN_VALUE (type);
- if (POINTER_TYPE_P (type))
- return build_zero_cst (const_cast<tree> (type));
- return NULL_TREE;
-}
-
/* Return whether VAL is equal to the maximum value of its type.
We can't do a simple equality comparison with TYPE_MAX_VALUE because
C typedefs and Ada subtypes can produce types whose TYPE_MAX_VALUE
return false;
return true;
}
+
+#define DEFINE_INT_RANGE_GC_STUBS(N) \
+ void \
+ gt_pch_nx (int_range<N> *&x) \
+ { \
+ for (unsigned i = 0; i < N; ++i) \
+ { \
+ gt_pch_nx (x->m_ranges[i * 2]); \
+ gt_pch_nx (x->m_ranges[i * 2 + 1]); \
+ } \
+ } \
+ \
+ void \
+ gt_ggc_mx (int_range<N> *&x) \
+ { \
+ for (unsigned i = 0; i < N; ++i) \
+ { \
+ gt_ggc_mx (x->m_ranges[i * 2]); \
+ gt_ggc_mx (x->m_ranges[i * 2 + 1]); \
+ } \
+ }
+
+#define DEFINE_INT_RANGE_INSTANCE(N) \
+ template int_range<N>::int_range(tree, tree, value_range_kind); \
+ template int_range<N>::int_range(tree_node *, \
+ const wide_int &, \
+ const wide_int &, \
+ value_range_kind); \
+ template int_range<N>::int_range(tree); \
+ template int_range<N>::int_range(const irange &); \
+ template int_range<N>::int_range(const int_range &); \
+ template int_range<N>& int_range<N>::operator= (const int_range &);
+
+DEFINE_INT_RANGE_INSTANCE(1)
+DEFINE_INT_RANGE_INSTANCE(2)
+DEFINE_INT_RANGE_INSTANCE(3)
+DEFINE_INT_RANGE_INSTANCE(255)
+DEFINE_INT_RANGE_GC_STUBS(1)
projects / thirdparty / gcc.git / commitdiff
