This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
value_range and irange unification
- From: Aldy Hernandez <aldyh at redhat dot com>
- To: Richard Biener <richard dot guenther at gmail dot com>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Cc: Andrew MacLeod <amacleod at redhat dot com>
- Date: Fri, 21 Jun 2019 07:41:26 -0400
- Subject: value_range and irange unification
Hi Richard. Hi folks.
In order to unify the APIs for value_range and irange, we'd like to make
some minor changes to value_range. We believe most of these changes
could go in now, and would prefer so, to get broader testing and
minimize the plethora of changes we drag around on our branch.
First, introduce a type for VR_VARYING and VR_UNDEFINED.
--------------------------------------------------------
irange utilizes 0 or more sub-ranges to represent a range, and VARYING
is simply one subrange [MIN, MAX]. value_range represents this with
VR_VARYING, and since there is no type associated with it, we cannot
calculate the lower and upper bounds for the range. There is also a
lack of canonicalness in value range in that VR_VARYING and [MIN, MAX]
are two different representations of the same value.
We tried to adjust irange to not associate a type with the empty range
[] (representing undefined), but found we were unable to perform all
operations properly. In particular, we cannot invert an empty range.
i.e. invert ( [] ) should produce [MIN, MAX]. Again, we need to have a
type associated with this empty range.
We'd like to tweak value_range so that set_varying() and set_undefined()
both take a type, and then always set the min/max fields based on that
type. This takes no additional memory in the structure, and is
virtually transparent to all the existing uses of value_range.
This allows:
1) invert to be implemented properly for both VARYING and UNDEFINED
by simply changing one to the other.
2) the type() method to always work without any special casing by
simply returning TREE_TYPE(min)
3) the new incoming bounds() routines to work trivially for these
cases as well (lbound/ubound, num_pairs(), etc).
This functionality is provided in the first attached patch.
Note, the current implementation sets min/max to TREE_TYPE, not to
TYPE_MIN/MAX_VALUE. We can fix this if preferred.
Second, enforce canonicalization at value_range build time.
-----------------------------------------------------------
As discussed above, value_range has multiple representations for the
same range. For instance, ~[0,0] is the same as [1,MAX] in unsigned and
[MIN, MAX] is really varying, among others. We found it quite difficult
to make things work, with multiple representations for a given range.
Canonicalizing at build time solves this, as well as removing explicit
set_and_canonicalize() calls throughout. Furthermore, it avoids some
special casing in VRP.
Along with canonicalizing, we also enforce the existing value_range API
more strongly. For instance, we don't allow setting equivalences for
either VR_VARYING or VR_UNDEFINED.
This functionality is provided in the second patch.
Third, irange on value_range implementation.
---------------------------------------------
The third attached patch shows how we use the above two to implement
irange using value_ranges. value_range would be a drop-in replacement
for irange, by just doing the following in range.h:
+// Enable this to implement irange piggybacking on value_range.
+#define IRANGE_WITH_VALUE_RANGE 1
+
+#if IRANGE_WITH_VALUE_RANGE
+#include "tree-vrp.h"
+typedef value_range_base irange;
+typedef value_range_storage irange_storage;
+#define IRANGE_PLAIN VR_RANGE
+#define IRANGE_INVERSE VR_ANTI_RANGE
+#else
...
The additions to the value_range API would be mostly the following (full
details in the third attached patch):
+ value_range_base (tree, tree);
+ value_range_base (value_range_kind,
+ tree type, const wide_int &, const wide_int &);
+ value_range_base (tree type, const wide_int &, const wide_int &);
+ value_range_base (tree type, const value_range_storage *);
+ value_range_base (tree type);
void set (value_range_kind, tree, tree);
void set (tree);
@@ -77,7 +86,25 @@ public:
bool singleton_p (tree *result = NULL) const;
void dump (FILE *) const;
+ /* Support machinery for irange. */
+ static const unsigned int m_max_pairs = 2;
+ static bool supports_type_p (tree type);
+ static bool supports_ssa_p (tree ssa);
+ static bool supports_p (tree expr);
+ void cast (tree);
+ bool contains_p (tree) const;
+ unsigned num_pairs () const;
+ wide_int lower_bound (unsigned = 0) const;
+ wide_int upper_bound (unsigned) const;
+ wide_int upper_bound () const;
+ void invert ();
+ void dump () const { dump (stderr); }
+ // FIXME: Perhaps rewrite the irange versions to use pointers instead.
+ void union_ (const value_range_base &);
+ void intersect (const value_range_base &);
+
protected:
+ value_range_base normalize_symbolics () const;
There are no regressions from mainline, and we are catching every one of
our internal ranger tests, with the exception of two that require more
than 2 sub-ranges to work. i.e. Not a regression from mainline-- just
new functionality we can't get with the limited sub-ranges in value_range.
Note: Please ignore the value_range_base::normalize_symbolics stuff.
It's likely to go through multiple revisions as Andrew gets the ranger
to deal with symbolics.
Finally
-------
All these patches are already in our branch, and irange with value_range
can be enabled by #define IRANGE_WITH_VALUE_RANGE 1.
With these changes, we can successfully build and run the ranger branch
using value_range in place of irange, which indicates a successful API
merge.
After some minor cleanups, I would like to contribute at least the first
two patches to trunk (VARYING types and the enforced canonicalization).
This will enable us to move forward with trying to integrate the
range-ops code which makes heavy use of the subrange interface, and
allows for broader testing instead of dropping everything in one-go.
These two patches stand on their own independently, and IMO provide
useful functionality right now.
I would ideally like to contribute the third patch to mainline, but I do
understand that it currently has no users... although I could rewrite
bits of tree-vrp to use these new functions (lower_bound, upper_bound,
etc), thus providing a use case ??. However, I do understand if you'd
prefer to keep this last patch on the branch.
Thoughts?
Aldy (and Andrew)
commit c79b8dde9ca9f1f33515c434cc48f4248a952bd9
Author: aldyh <aldyh@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Tue Jun 18 22:44:37 2019 +0000
VR_VARYING and VR_UNDEFINED now must now have a type associated with it.
Type is stored in the MIN/MAX fields which were previously unused when
varying or undefined.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/ssa-range@272456 138bc75d-0d04-0410-961f-82ee72b054a4
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index 09aa0c484c4..6f8293720ae 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -258,7 +258,7 @@ evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
vr_values->extract_range_from_phi_node (phi, &vr_result);
else
{
- vr_result.set_varying ();
+ vr_result.set_varying (TREE_TYPE (lhs));
/* When we have an unvisited executable predecessor we can't
use PHI arg ranges which may be still UNDEFINED but have
to use VARYING for them. But we can still resort to
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 59b15fa7362..c99f4e70497 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -314,7 +314,7 @@ public:
inline bool set_to_bottom ();
bool meet_with (const value_range_base *p_vr);
bool meet_with (const ipcp_vr_lattice &other);
- void init () { gcc_assert (m_vr.undefined_p ()); }
+ void init (tree type) { m_vr.set_undefined (type); }
void print (FILE * f);
private:
@@ -962,7 +962,7 @@ ipcp_vr_lattice::set_to_bottom ()
{
if (m_vr.varying_p ())
return false;
- m_vr.set_varying ();
+ m_vr.set_varying (m_vr.type ());
return true;
}
@@ -1190,7 +1190,8 @@ initialize_node_lattices (struct cgraph_node *node)
for (i = 0; i < ipa_get_param_count (info); i++)
{
struct ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
- plats->m_value_range.init ();
+ tree type = ipa_get_type (info, i);
+ plats->m_value_range.init (type);
}
if (disable || variable)
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 7ab72e5ee81..65d018eb292 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -184,7 +184,7 @@ record_temporary_equivalences_from_phis (edge e,
else if (TREE_CODE (src) == INTEGER_CST)
new_vr->set (src);
else
- new_vr->set_varying ();
+ new_vr->set_varying (TREE_TYPE (src));
/* This is a temporary range for DST, so push it. */
evrp_range_analyzer->push_value_range (dst, new_vr);
diff --git a/gcc/tree-ssanames.c b/gcc/tree-ssanames.c
index 5bac799e9a3..1199f64e575 100644
--- a/gcc/tree-ssanames.c
+++ b/gcc/tree-ssanames.c
@@ -441,7 +441,7 @@ get_range_info (const_tree name, value_range_base &vr)
enum value_range_kind kind = get_range_info (name, &wmin, &wmax);
if (kind == VR_VARYING || kind == VR_UNDEFINED)
- min = max = NULL;
+ min = max = TREE_TYPE (name);
else
{
min = wide_int_to_tree (TREE_TYPE (name), wmin);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 8dca15e0e59..8a3bd2599a5 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -192,7 +192,6 @@ value_range_base::check ()
}
case VR_UNDEFINED:
case VR_VARYING:
- gcc_assert (!min () && !max ());
break;
default:
gcc_unreachable ();
@@ -219,6 +218,13 @@ value_range::check ()
bool
value_range_base::equal_p (const value_range_base &other) const
{
+ /* Ignore types for undefined. All undefines are equal. */
+ if (undefined_p ())
+ return m_kind == other.m_kind;
+
+ if (varying_p ())
+ return m_kind == other.m_kind && types_compatible_p (m_min, other.m_min);
+
return (m_kind == other.m_kind
&& vrp_operand_equal_p (m_min, other.m_min)
&& vrp_operand_equal_p (m_max, other.m_max));
@@ -261,27 +267,29 @@ value_range_base::constant_p () const
}
void
-value_range_base::set_undefined ()
+value_range_base::set_undefined (tree type)
{
- set (VR_UNDEFINED, NULL, NULL);
+ set (VR_UNDEFINED, type, type);
}
void
-value_range::set_undefined ()
+value_range::set_undefined (tree type)
{
- set (VR_UNDEFINED, NULL, NULL, NULL);
+ value_range_base::set_undefined (type);
+ equiv_clear ();
}
void
-value_range_base::set_varying ()
+value_range_base::set_varying (tree type)
{
- set (VR_VARYING, NULL, NULL);
+ set (VR_VARYING, type, type);
}
void
-value_range::set_varying ()
+value_range::set_varying (tree type)
{
- set (VR_VARYING, NULL, NULL, NULL);
+ value_range_base::set_varying (type);
+ equiv_clear ();
}
/* Return TRUE if it is possible that range contains VAL. */
@@ -340,21 +348,29 @@ value_range_base::singleton_p (tree *result) const
tree
value_range_base::type () const
{
- /* Types are only valid for VR_RANGE and VR_ANTI_RANGE, which are
- known to have non-zero min/max. */
- gcc_assert (min ());
+ if (undefined_p () || varying_p ())
+ {
+ gcc_assert (min () != NULL);
+ return min ();
+ }
return TREE_TYPE (min ());
}
void
value_range_base::dump (FILE *file) const
{
+ tree ttype;
+ if (undefined_p () || varying_p ())
+ ttype = m_min;
+ else ttype = TREE_TYPE (m_min);
+
if (undefined_p ())
- fprintf (file, "UNDEFINED");
+ {
+ print_generic_expr (file, ttype);
+ fprintf (file, " UNDEFINED");
+ }
else if (m_kind == VR_RANGE || m_kind == VR_ANTI_RANGE)
{
- tree ttype = type ();
-
print_generic_expr (file, ttype);
fprintf (file, " ");
@@ -380,7 +396,10 @@ value_range_base::dump (FILE *file) const
fprintf (file, "]");
}
else if (varying_p ())
- fprintf (file, "VARYING");
+ {
+ print_generic_expr (file, ttype);
+ fprintf (file, " VARYING");
+ }
else
gcc_unreachable ();
}
@@ -631,15 +650,16 @@ void
value_range_base::set_and_canonicalize (enum value_range_kind kind,
tree min, tree max)
{
- /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
if (kind == VR_UNDEFINED)
{
- set_undefined ();
+ gcc_assert (TYPE_P (min));
+ set_undefined (min);
return;
}
else if (kind == VR_VARYING)
{
- set_varying ();
+ gcc_assert (TYPE_P (min));
+ set_varying (min);
return;
}
@@ -662,7 +682,7 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
for VR_ANTI_RANGE empty range, so drop to varying as well. */
if (TYPE_PRECISION (TREE_TYPE (min)) == 1)
{
- set_varying ();
+ set_varying (TREE_TYPE (min));
return;
}
@@ -676,7 +696,7 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
to varying in this case. */
if (tree_int_cst_lt (max, min))
{
- set_varying ();
+ set_varying (TREE_TYPE (min));
return;
}
@@ -698,7 +718,7 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
{
/* We cannot deal with empty ranges, drop to varying.
??? This could be VR_UNDEFINED instead. */
- set_varying ();
+ set_varying (type);
return;
}
else if (TYPE_PRECISION (TREE_TYPE (min)) == 1
@@ -1193,8 +1213,8 @@ ranges_from_anti_range (const value_range_base *ar,
{
tree type = ar->type ();
- vr0->set_undefined ();
- vr1->set_undefined ();
+ vr0->set_undefined (type);
+ vr1->set_undefined (type);
/* As a future improvement, we could handle ~[0, A] as: [-INF, -1] U
[A+1, +INF]. Not sure if this helps in practice, though. */
@@ -1217,7 +1237,7 @@ ranges_from_anti_range (const value_range_base *ar,
if (vr0->undefined_p ())
{
*vr0 = *vr1;
- vr1->set_undefined ();
+ vr1->set_undefined (type);
}
return !vr0->undefined_p ();
@@ -1285,7 +1305,7 @@ extract_range_from_multiplicative_op (value_range_base *vr,
wide_int_to_tree (type, res_lb),
wide_int_to_tree (type, res_ub));
else
- vr->set_varying ();
+ vr->set_varying (type);
}
/* If BOUND will include a symbolic bound, adjust it accordingly,
@@ -1498,7 +1518,7 @@ canonicalize_value_range (value_range_base *vr, tree expr_type)
&& operand_equal_p (TYPE_MIN_VALUE (expr_type), vr->min (), 0)
&& operand_equal_p (TYPE_MAX_VALUE (expr_type), vr->max (), 0))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
// The canonicalizations below are only needed when comparing with VRP.
@@ -1627,22 +1647,23 @@ ranger_fold (value_range_base *vr, enum tree_code code,
{
range_operator *op = range_op_handler (code);
irange res;
+ tree type = ir0.type ();
if (!op)
{
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
if (!op->fold_range (res, ir0, ir1))
{
if (res.undefined_p ())
- vr->set_undefined ();
+ vr->set_undefined (type);
else
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
if (res.undefined_p ())
{
- vr->set_undefined ();
+ vr->set_undefined (type);
return;
}
// MAX/MIN of pointers in VRP dumbs everything down to
@@ -1655,7 +1676,7 @@ ranger_fold (value_range_base *vr, enum tree_code code,
&& !res.zero_p ()
&& !res.nonzero_p ())
{
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
*vr = irange_to_value_range (res);
@@ -1690,7 +1711,7 @@ ranger_fold_unary (value_range_base *vr, enum tree_code code, tree expr_type,
else if (vr0->zero_p ())
vr->set_zero (expr_type);
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
irange res, vr0_irange, vr1_irange;
@@ -1720,7 +1741,7 @@ extract_range_from_binary_expr (value_range_base *vr,
if (!INTEGRAL_TYPE_P (expr_type)
&& !POINTER_TYPE_P (expr_type))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -1744,14 +1765,14 @@ extract_range_from_binary_expr (value_range_base *vr,
&& code != BIT_IOR_EXPR
&& code != BIT_XOR_EXPR)
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
/* If both ranges are UNDEFINED, so is the result. */
if (vr0.undefined_p () && vr1.undefined_p ())
{
- vr->set_undefined ();
+ vr->set_undefined (expr_type);
return;
}
/* If one of the ranges is UNDEFINED drop it to VARYING for the following
@@ -1759,9 +1780,9 @@ extract_range_from_binary_expr (value_range_base *vr,
have UNDEFINED result for all or some value-ranges of the not UNDEFINED
operand. */
else if (vr0.undefined_p ())
- vr0.set_varying ();
+ vr0.set_varying (expr_type);
else if (vr1.undefined_p ())
- vr1.set_varying ();
+ vr1.set_varying (expr_type);
/* We get imprecise results from ranges_from_anti_range when
code is EXACT_DIV_EXPR. We could mask out bits in the resulting
@@ -1833,7 +1854,7 @@ extract_range_from_binary_expr (value_range_base *vr,
|| vr0.symbolic_p ()
|| vr1.symbolic_p ()))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -1881,7 +1902,7 @@ extract_range_from_binary_expr (value_range_base *vr,
else if (vr0.zero_p () && vr1.zero_p ())
vr->set_zero (expr_type);
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
}
else if (code == POINTER_PLUS_EXPR)
{
@@ -1912,7 +1933,7 @@ extract_range_from_binary_expr (value_range_base *vr,
else if (vr0.zero_p () && vr1.zero_p ())
vr->set_zero (expr_type);
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
}
else if (code == BIT_AND_EXPR)
{
@@ -1923,10 +1944,10 @@ extract_range_from_binary_expr (value_range_base *vr,
else if (vr0.zero_p () || vr1.zero_p ())
vr->set_zero (expr_type);
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
}
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -1993,7 +2014,7 @@ extract_range_from_binary_expr (value_range_base *vr,
if (((bool)min_ovf && sym_min_op0 != sym_min_op1)
|| ((bool)max_ovf && sym_max_op0 != sym_max_op1))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -2004,7 +2025,7 @@ extract_range_from_binary_expr (value_range_base *vr,
wmin, wmax, min_ovf, max_ovf);
if (type == VR_VARYING)
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -2030,7 +2051,7 @@ extract_range_from_binary_expr (value_range_base *vr,
a single range or anti-range as the above is
[-INF+1, +INF(OVF)] intersected with ~[5, 5]
but one could use a scheme similar to equivalences for this. */
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
}
@@ -2047,7 +2068,7 @@ extract_range_from_binary_expr (value_range_base *vr,
vr->set (VR_RANGE, wide_int_to_tree (expr_type, wmin),
wide_int_to_tree (expr_type, wmax));
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
else if (code == MULT_EXPR)
@@ -2055,7 +2076,7 @@ extract_range_from_binary_expr (value_range_base *vr,
if (!range_int_cst_p (&vr0)
|| !range_int_cst_p (&vr1))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
@@ -2100,7 +2121,7 @@ extract_range_from_binary_expr (value_range_base *vr,
}
}
}
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
else if (code == TRUNC_DIV_EXPR
@@ -2116,7 +2137,7 @@ extract_range_from_binary_expr (value_range_base *vr,
/* Special case explicit division by zero as undefined. */
if (vr1.zero_p ())
{
- vr->set_undefined ();
+ vr->set_undefined (expr_type);
return;
}
@@ -2137,7 +2158,7 @@ extract_range_from_binary_expr (value_range_base *vr,
TYPE_OVERFLOW_UNDEFINED (expr_type),
extra_range_p, extra_min, extra_max))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
vr->set (VR_RANGE, wide_int_to_tree (expr_type, wmin),
@@ -2155,7 +2176,7 @@ extract_range_from_binary_expr (value_range_base *vr,
{
if (vr1.zero_p ())
{
- vr->set_undefined ();
+ vr->set_undefined (expr_type);
return;
}
wide_int wmin, wmax, tmp;
@@ -2196,7 +2217,7 @@ extract_range_from_binary_expr (value_range_base *vr,
vr->set (VR_RANGE, min, max);
}
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
else if (code == BIT_IOR_EXPR)
@@ -2214,7 +2235,7 @@ extract_range_from_binary_expr (value_range_base *vr,
vr->set (VR_RANGE, min, max);
}
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
else if (code == BIT_XOR_EXPR)
@@ -2230,7 +2251,7 @@ extract_range_from_binary_expr (value_range_base *vr,
vr->set (VR_RANGE, min, max);
}
else
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
}
@@ -2244,7 +2265,7 @@ extract_range_from_binary_expr (value_range_base *vr,
|| max == NULL_TREE
|| TREE_OVERFLOW_P (max))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -2253,7 +2274,7 @@ extract_range_from_binary_expr (value_range_base *vr,
Note that we do accept [-INF, -INF] and [+INF, +INF]. */
if (vrp_val_is_min (min) && vrp_val_is_max (max))
{
- vr->set_varying ();
+ vr->set_varying (expr_type);
return;
}
@@ -2263,7 +2284,7 @@ extract_range_from_binary_expr (value_range_base *vr,
/* If the new range has its limits swapped around (MIN > MAX),
then the operation caused one of them to wrap around, mark
the new range VARYING. */
- vr->set_varying ();
+ vr->set_varying (expr_type);
}
else
vr->set (type, min, max);
@@ -2289,14 +2310,14 @@ extract_range_from_unary_expr (value_range_base *vr,
|| !(INTEGRAL_TYPE_P (type)
|| POINTER_TYPE_P (type)))
{
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
/* If VR0 is UNDEFINED, so is the result. */
if (vr0.undefined_p ())
{
- vr->set_undefined ();
+ vr->set_undefined (type);
return;
}
@@ -2322,7 +2343,7 @@ extract_range_from_unary_expr (value_range_base *vr,
flag_ranges_mode = save;
canonicalize_value_range (&old_vr, type);
- vr1.set_varying ();
+ vr1.set_varying (type);
compare_value_ranges (code, &vr0, &vr1, &old_vr, vr, type);
}
return;
@@ -2389,7 +2410,7 @@ extract_range_from_unary_expr (value_range_base *vr,
else if (vr0.zero_p ())
vr->set_zero (type);
else
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
@@ -2424,7 +2445,7 @@ extract_range_from_unary_expr (value_range_base *vr,
vr->set_and_canonicalize (VR_RANGE, min, max);
}
else
- vr->set_varying ();
+ vr->set_varying (outer_type);
return;
}
else if (code == ABS_EXPR)
@@ -2437,7 +2458,7 @@ extract_range_from_unary_expr (value_range_base *vr,
vr->set (VR_RANGE, wide_int_to_tree (type, wmin),
wide_int_to_tree (type, wmax));
else
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
else if (code == ABSU_EXPR)
@@ -2452,7 +2473,7 @@ extract_range_from_unary_expr (value_range_base *vr,
}
/* For unhandled operations fall back to varying. */
- vr->set_varying ();
+ vr->set_varying (type);
return;
}
@@ -5448,7 +5469,7 @@ vrp_prop::vrp_initialize ()
if (!stmt_interesting_for_vrp (phi))
{
tree lhs = PHI_RESULT (phi);
- get_value_range (lhs)->set_varying ();
+ get_value_range (lhs)->set_varying (TREE_TYPE (lhs));
prop_set_simulate_again (phi, false);
}
else
@@ -5643,7 +5664,7 @@ vrp_prop::visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
use_operand_p use_p;
enum ssa_prop_result res = SSA_PROP_VARYING;
- get_value_range (lhs)->set_varying ();
+ get_value_range (lhs)->set_varying (TREE_TYPE (lhs));
FOR_EACH_IMM_USE_FAST (use_p, iter, lhs)
{
@@ -6331,6 +6352,11 @@ value_range_base::intersect_helper (const value_range_base *vr0,
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_base tem;
+ if (vr0type == VR_UNDEFINED || vr0type == VR_VARYING)
+ {
+ vr0min = TREE_TYPE (vr0->min ());
+ vr0max = TREE_TYPE (vr0->min ());
+ }
tem.set_and_canonicalize (vr0type, vr0min, vr0max);
/* If that failed, use the saved original VR0. */
if (tem.varying_p ())
@@ -6436,6 +6462,11 @@ value_range_base::union_helper (const value_range_base *vr0,
/* Work on a temporary so we can still use vr0 when union returns varying. */
value_range_base tem;
+ if (vr0type == VR_UNDEFINED || vr0type == VR_VARYING)
+ {
+ vr0min = TREE_TYPE (vr0->min ());
+ vr0max = TREE_TYPE (vr0->min ());
+ }
tem.set_and_canonicalize (vr0type, vr0min, vr0max);
/* Failed to find an efficient meet. Before giving up and setting
@@ -7189,7 +7220,7 @@ determine_value_range_1 (value_range_base *vr, tree expr)
vr->set (kind, wide_int_to_tree (TREE_TYPE (expr), min),
wide_int_to_tree (TREE_TYPE (expr), max));
else
- vr->set_varying ();
+ vr->set_varying (TREE_TYPE (expr));
}
}
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 4ec974f5fdb..4af1bc99da9 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -58,8 +58,8 @@ public:
bool constant_p () const;
bool undefined_p () const;
bool varying_p () const;
- void set_varying ();
- void set_undefined ();
+ void set_varying (tree);
+ void set_undefined (tree = NULL);
void union_ (const value_range_base *);
void intersect (const value_range_base *);
@@ -133,8 +133,8 @@ class GTY((user)) value_range : public value_range_base
bool equal_p (const value_range &, bool ignore_equivs) const;
/* Types of value ranges. */
- void set_undefined ();
- void set_varying ();
+ void set_undefined (tree = NULL);
+ void set_varying (tree);
/* Equivalence bitmap methods. */
bitmap equiv () const;
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 9ffd20f7bce..6bc62f46d2a 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -91,7 +91,7 @@ static inline void
set_value_range_to_truthvalue (value_range *vr, tree type)
{
if (TYPE_PRECISION (type) == 1)
- vr->set_varying ();
+ vr->set_varying (type);
else
vr->update (VR_RANGE, build_int_cst (type, 0), build_int_cst (type, 1));
}
@@ -153,10 +153,10 @@ vr_values::get_value_range (const_tree var)
{
get_range_info (var, *vr);
if (vr->undefined_p ())
- vr->set_varying ();
+ vr->set_varying (TREE_TYPE (sym));
}
else
- vr->set_varying ();
+ vr->set_varying (TREE_TYPE (sym));
}
else if (TREE_CODE (sym) == RESULT_DECL
&& DECL_BY_REFERENCE (sym))
@@ -181,7 +181,7 @@ vr_values::set_defs_to_varying (gimple *stmt)
value_range *vr = get_value_range (def);
/* Avoid writing to vr_const_varying get_value_range may return. */
if (!vr->varying_p ())
- vr->set_varying ();
+ vr->set_varying (TREE_TYPE (def));
}
}
@@ -225,13 +225,13 @@ vr_values::update_value_range (const_tree var, value_range *new_vr)
called, if we are anyway, keep it VARYING. */
if (old_vr->varying_p ())
{
- new_vr->set_varying ();
+ new_vr->set_varying (new_vr->type ());
is_new = false;
}
else if (new_vr->undefined_p ())
{
- old_vr->set_varying ();
- new_vr->set_varying ();
+ old_vr->set_varying (TREE_TYPE (var));
+ new_vr->set_varying (TREE_TYPE (var));
return true;
}
else
@@ -460,7 +460,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
if ((POINTER_TYPE_P (type) && cond_code != NE_EXPR && cond_code != EQ_EXPR)
|| limit == var)
{
- vr_p->set_varying ();
+ vr_p->set_varying (type);
return;
}
@@ -620,7 +620,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
all should be optimized away above us. */
if (cond_code == LT_EXPR
&& compare_values (max, min) == 0)
- vr_p->set_varying ();
+ vr_p->set_varying (TREE_TYPE (min));
else
{
/* For LT_EXPR, we create the range [MIN, MAX - 1]. */
@@ -660,7 +660,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
all should be optimized away above us. */
if (cond_code == GT_EXPR
&& compare_values (min, max) == 0)
- vr_p->set_varying ();
+ vr_p->set_varying (TREE_TYPE (min));
else
{
/* For GT_EXPR, we create the range [MIN + 1, MAX]. */
@@ -767,14 +767,14 @@ vr_values::extract_range_from_binary_expr (value_range *vr,
else if (is_gimple_min_invariant (op0))
vr0.set (op0);
else
- vr0.set_varying ();
+ vr0.set_varying (TREE_TYPE (op0));
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
vr1.set (op1);
else
- vr1.set_varying ();
+ vr1.set_varying (TREE_TYPE (op1));
/* If one argument is varying, we can sometimes still deduce a
range for the output: any + [3, +INF] is in [MIN+3, +INF]. */
@@ -915,7 +915,7 @@ vr_values::extract_range_from_unary_expr (value_range *vr, enum tree_code code,
else if (is_gimple_min_invariant (op0))
vr0.set (op0);
else
- vr0.set_varying ();
+ vr0.set_varying (type);
::extract_range_from_unary_expr (vr, code, type, &vr0, TREE_TYPE (op0));
}
@@ -937,7 +937,7 @@ vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt)
else if (is_gimple_min_invariant (op0))
tem0.set (op0);
else
- tem0.set_varying ();
+ tem0.set_varying (TREE_TYPE (op0));
tree op1 = gimple_assign_rhs3 (stmt);
value_range tem1;
@@ -947,7 +947,7 @@ vr_values::extract_range_from_cond_expr (value_range *vr, gassign *stmt)
else if (is_gimple_min_invariant (op1))
tem1.set (op1);
else
- tem1.set_varying ();
+ tem1.set_varying (TREE_TYPE (op1));
/* The resulting value range is the union of the operand ranges */
vr->deep_copy (vr0);
@@ -1309,7 +1309,7 @@ vr_values::extract_range_basic (value_range *vr, gimple *stmt)
if (vr->kind () == VR_RANGE
&& (vr->min () == vr->max ()
|| operand_equal_p (vr->min (), vr->max (), 0)))
- vr->set_varying ();
+ vr->set_varying (vr->type ());
return;
}
}
@@ -1368,7 +1368,7 @@ vr_values::extract_range_basic (value_range *vr, gimple *stmt)
vr->set (build_int_cst (type, ovf));
else if (TYPE_PRECISION (type) == 1
&& !TYPE_UNSIGNED (type))
- vr->set_varying ();
+ vr->set_varying (type);
else
vr->set (VR_RANGE, build_int_cst (type, 0),
build_int_cst (type, 1));
@@ -1413,7 +1413,7 @@ vr_values::extract_range_basic (value_range *vr, gimple *stmt)
vr->equiv_clear ();
}
else
- vr->set_varying ();
+ vr->set_varying (type);
}
@@ -1449,7 +1449,7 @@ vr_values::extract_range_from_assignment (value_range *vr, gassign *stmt)
&& is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
vr->set (gimple_assign_rhs1 (stmt));
else
- vr->set_varying ();
+ vr->set_varying (TREE_TYPE (gimple_assign_lhs (stmt)));
if (vr->varying_p ())
extract_range_basic (vr, stmt);
@@ -2888,7 +2888,7 @@ vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result)
vr_arg_tem.set (vr_arg_->kind (), vr_arg_->min (),
vr_arg_->max (), NULL);
if (vr_arg_tem.symbolic_p ())
- vr_arg_tem.set_varying ();
+ vr_arg_tem.set_varying (vr_arg_->type ());
}
else
vr_arg = vr_arg_;
@@ -3010,7 +3010,7 @@ vr_values::extract_range_from_phi_node (gphi *phi, value_range *vr_result)
goto update_range;
varying:
- vr_result->set_varying ();
+ vr_result->set_varying (TREE_TYPE (lhs));
scev_check:
/* If this is a loop PHI node SCEV may known more about its value-range.
@@ -3031,7 +3031,7 @@ infinite_check:
|| compare_values (vr_result->min (), vr_result->max ()) > 0))
;
else
- vr_result->set_varying ();
+ vr_result->set_varying (TREE_TYPE (lhs));
/* If the new range is different than the previous value, keep
iterating. */
commit 1c363d12a2f0a33fba758c87165c96f4a4d6e706
Author: aldyh <aldyh@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Thu Jun 20 17:54:34 2019 +0000
Enforce value_range canonicalization.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/ssa-range@272516 138bc75d-0d04-0410-961f-82ee72b054a4
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b4d5698823e..cf5daf31cd0 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -80,19 +80,11 @@ ranges_from_anti_range (const value_range_base *ar,
for still active basic-blocks. */
static sbitmap *live;
-void
-value_range_base::set (enum value_range_kind kind, tree min, tree max)
-{
- m_kind = kind;
- m_min = min;
- m_max = max;
- if (flag_checking)
- check ();
-}
-
void
value_range::set_equiv (bitmap equiv)
{
+ if (undefined_p () || varying_p ())
+ equiv = NULL;
/* Since updating the equivalence set involves deep copying the
bitmaps, only do it if absolutely necessary.
@@ -154,7 +146,7 @@ value_range_base::value_range_base (enum value_range_kind kind,
tree min = wide_int_to_tree (type, wmin);
tree max = wide_int_to_tree (type, wmax);
gcc_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
- set_and_canonicalize (kind, min, max);
+ set (kind, min, max);
}
value_range_base::value_range_base (tree type,
@@ -163,7 +155,7 @@ value_range_base::value_range_base (tree type,
{
tree min = wide_int_to_tree (type, wmin);
tree max = wide_int_to_tree (type, wmax);
- set_and_canonicalize (VR_RANGE, min, max);
+ set (VR_RANGE, min, max);
}
value_range_base::value_range_base (tree min, tree max)
@@ -310,7 +302,8 @@ value_range_base::constant_p () const
void
value_range_base::set_undefined (tree type)
{
- set (VR_UNDEFINED, type, type);
+ m_kind = VR_UNDEFINED;
+ m_min = m_max = type;
}
void
@@ -323,7 +316,8 @@ value_range::set_undefined (tree type)
void
value_range_base::set_varying (tree type)
{
- set (VR_VARYING, type, type);
+ m_kind = VR_VARYING;
+ m_min = m_max = type;
}
void
@@ -707,8 +701,7 @@ intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
extract ranges from var + CST op limit. */
void
-value_range_base::set_and_canonicalize (enum value_range_kind kind,
- tree min, tree max)
+value_range_base::set (enum value_range_kind kind, tree min, tree max)
{
if (kind == VR_UNDEFINED)
{
@@ -727,7 +720,9 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
if (TREE_CODE (min) != INTEGER_CST
|| TREE_CODE (max) != INTEGER_CST)
{
- set (kind, min, max);
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
return;
}
@@ -811,3 +806,23 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
}
}
+ /* Normalize [MIN, MAX] into VARYING and ~[MIN, MAX] into UNDEFINED.
+ 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. */
+ 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 (type);
+ else
+ gcc_unreachable ();
+ return;
+ }
@@ -838,18 +832,11 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
to make sure VRP iteration terminates, otherwise we can get into
oscillations. */
- set (kind, min, max);
-}
-
-void
-value_range::set_and_canonicalize (enum value_range_kind kind,
- tree min, tree max, bitmap equiv)
-{
- value_range_base::set_and_canonicalize (kind, min, max);
- if (this->kind () == VR_RANGE || this->kind () == VR_ANTI_RANGE)
- set_equiv (equiv);
- else
- equiv_clear ();
+ m_kind = kind;
+ m_min = min;
+ m_max = max;
+ if (flag_checking)
+ check ();
}
void
@@ -1351,7 +1338,8 @@ static void
extract_range_from_multiplicative_op (value_range_base *vr,
enum tree_code code,
const value_range_base *vr0,
- const value_range_base *vr1)
+ const value_range_base *vr1,
+ tree type)
{
gcc_assert (code == MULT_EXPR
|| code == TRUNC_DIV_EXPR
@@ -1361,13 +1349,25 @@ extract_range_from_multiplicative_op (value_range_base *vr,
|| code == ROUND_DIV_EXPR
|| code == RSHIFT_EXPR
|| code == LSHIFT_EXPR);
- gcc_assert (vr0->kind () == VR_RANGE
- && vr0->kind () == vr1->kind ());
+ if (!range_int_cst_p (vr1))
+ {
+ vr->set_varying (type);
+ return;
+ }
+
+ /* Even if vr0 is VARYING or otherwise not usable, we can derive
+ useful ranges just from the shift count. E.g.
+ x >> 63 for signed 64-bit x is always [-1, 0]. */
+ tree vr0_min = vr0->min (), vr0_max = vr0->max ();
+ if (vr0->kind () != VR_RANGE || vr0->symbolic_p ())
+ {
+ vr0_min = vrp_val_min (type);
+ vr0_max = vrp_val_max (type);
+ }
- tree type = vr0->type ();
wide_int res_lb, res_ub;
- wide_int vr0_lb = wi::to_wide (vr0->min ());
- wide_int vr0_ub = wi::to_wide (vr0->max ());
+ wide_int vr0_lb = wi::to_wide (vr0_min);
+ wide_int vr0_ub = wi::to_wide (vr0_max);
wide_int vr1_lb = wi::to_wide (vr1->min ());
wide_int vr1_ub = wi::to_wide (vr1->max ());
bool overflow_undefined = TYPE_OVERFLOW_UNDEFINED (type);
@@ -1377,9 +1377,8 @@ extract_range_from_multiplicative_op (value_range_base *vr,
code, TYPE_SIGN (type), prec,
vr0_lb, vr0_ub, vr1_lb, vr1_ub,
overflow_undefined))
- vr->set_and_canonicalize (VR_RANGE,
- wide_int_to_tree (type, res_lb),
- wide_int_to_tree (type, res_ub));
+ vr->set (VR_RANGE, wide_int_to_tree (type, res_lb),
+ wide_int_to_tree (type, res_ub));
else
vr->set_varying (type);
}
@@ -2032,19 +2031,30 @@ extract_range_from_binary_expr (value_range_base *vr,
range and see what we end up with. */
if (code == PLUS_EXPR || code == MINUS_EXPR)
{
+ value_range_kind vr0_kind = vr0.kind (), vr1_kind = vr1.kind ();
+ tree vr0_min = vr0.min (), vr0_max = vr0.max ();
+ tree vr1_min = vr1.min (), vr1_max = vr1.max ();
/* This will normalize things such that calculating
[0,0] - VR_VARYING is not dropped to varying, but is
calculated as [MIN+1, MAX]. */
if (vr0.varying_p ())
- vr0.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+ {
+ vr0_kind = VR_RANGE;
+ vr0_min = vrp_val_min (expr_type);
+ vr0_max = vrp_val_max (expr_type);
+ }
if (vr1.varying_p ())
- vr1.set (VR_RANGE, vrp_val_min (expr_type), vrp_val_max (expr_type));
+ {
+ vr1_kind = VR_RANGE;
+ vr1_min = vrp_val_min (expr_type);
+ vr1_max = vrp_val_max (expr_type);
+ }
const bool minus_p = (code == MINUS_EXPR);
- tree min_op0 = vr0.min ();
- tree min_op1 = minus_p ? vr1.max () : vr1.min ();
- tree max_op0 = vr0.max ();
- tree max_op1 = minus_p ? vr1.min () : vr1.max ();
+ tree min_op0 = vr0_min;
+ tree min_op1 = minus_p ? vr1_max : vr1_min;
+ tree max_op0 = vr0_max;
+ tree max_op1 = minus_p ? vr1_min : vr1_max;
tree sym_min_op0 = NULL_TREE;
tree sym_min_op1 = NULL_TREE;
tree sym_max_op0 = NULL_TREE;
@@ -2057,7 +2067,7 @@ extract_range_from_binary_expr (value_range_base *vr,
single-symbolic ranges, try to compute the precise resulting range,
but only if we know that this resulting range will also be constant
or single-symbolic. */
- if (vr0.kind () == VR_RANGE && vr1.kind () == VR_RANGE
+ if (vr0_kind == VR_RANGE && vr1_kind == VR_RANGE
&& (TREE_CODE (min_op0) == INTEGER_CST
|| (sym_min_op0
= get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
@@ -2155,7 +2165,7 @@ extract_range_from_binary_expr (value_range_base *vr,
vr->set_varying (expr_type);
return;
}
- extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
+ extract_range_from_multiplicative_op (vr, code, &vr0, &vr1, expr_type);
return;
}
else if (code == RSHIFT_EXPR
@@ -2170,13 +2180,8 @@ extract_range_from_binary_expr (value_range_base *vr,
{
if (code == RSHIFT_EXPR)
{
- /* Even if vr0 is VARYING or otherwise not usable, we can derive
- useful ranges just from the shift count. E.g.
- x >> 63 for signed 64-bit x is always [-1, 0]. */
- if (vr0.kind () != VR_RANGE || vr0.symbolic_p ())
- vr0.set (VR_RANGE, vrp_val_min (expr_type),
- vrp_val_max (expr_type));
- extract_range_from_multiplicative_op (vr, code, &vr0, &vr1);
+ extract_range_from_multiplicative_op (vr, code, &vr0, &vr1,
+ expr_type);
return;
}
else if (code == LSHIFT_EXPR
@@ -2192,7 +2197,7 @@ extract_range_from_binary_expr (value_range_base *vr,
{
min = wide_int_to_tree (expr_type, res_lb);
max = wide_int_to_tree (expr_type, res_ub);
- vr->set_and_canonicalize (VR_RANGE, min, max);
+ vr->set (VR_RANGE, min, max);
return;
}
}
@@ -2518,7 +2523,7 @@ extract_range_from_unary_expr (value_range_base *vr,
{
tree min = wide_int_to_tree (outer_type, wmin);
tree max = wide_int_to_tree (outer_type, wmax);
- vr->set_and_canonicalize (VR_RANGE, min, max);
+ vr->set (VR_RANGE, min, max);
}
else
vr->set_varying (outer_type);
@@ -6433,7 +6438,7 @@ value_range_base::intersect_helper (const value_range_base *vr0,
vr0min = TREE_TYPE (vr0->min ());
vr0max = TREE_TYPE (vr0->min ());
}
- tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+ tem.set (vr0type, vr0min, vr0max);
/* If that failed, use the saved original VR0. */
if (tem.varying_p ())
return *vr0;
@@ -6543,7 +6548,7 @@ value_range_base::union_helper (const value_range_base *vr0,
vr0min = TREE_TYPE (vr0->min ());
vr0max = TREE_TYPE (vr0->min ());
}
- tem.set_and_canonicalize (vr0type, vr0min, vr0max);
+ tem.set (vr0type, vr0min, vr0max);
/* Failed to find an efficient meet. Before giving up and setting
the result to VARYING, see if we can at least derive a useful
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 80fcc4aee26..41fa3efc40a 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -80,7 +80,6 @@ public:
/* Misc methods. */
tree type () const;
bool may_contain_p (tree) const;
- void set_and_canonicalize (enum value_range_kind, tree, tree);
bool zero_p () const;
bool nonzero_p () const;
bool singleton_p (tree *result = NULL) const;
@@ -170,7 +169,6 @@ class GTY((user)) value_range : public value_range_base
/* Misc methods. */
void deep_copy (const value_range *);
- void set_and_canonicalize (enum value_range_kind, tree, tree, bitmap = NULL);
void dump (FILE *) const;
private:
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index def5a163e90..c0477da458b 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -534,9 +534,9 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
vice-versa. Use set_and_canonicalize which does this for
us. */
if (cond_code == LE_EXPR)
- vr_p->set_and_canonicalize (VR_RANGE, min, max, vr_p->equiv ());
+ vr_p->set (VR_RANGE, min, max, vr_p->equiv ());
else if (cond_code == GT_EXPR)
- vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+ vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
else
gcc_unreachable ();
}
@@ -608,7 +608,7 @@ vr_values::extract_range_for_var_from_comparison_expr (tree var,
&& vrp_val_is_max (max))
min = max = limit;
- vr_p->set_and_canonicalize (VR_ANTI_RANGE, min, max, vr_p->equiv ());
+ vr_p->set (VR_ANTI_RANGE, min, max, vr_p->equiv ());
}
else if (cond_code == LE_EXPR || cond_code == LT_EXPR)
{
commit 1d7d379b3f8b23e5b378488f5dc1e8cc3225d350
Author: aldyh <aldyh@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Tue Jun 18 22:44:57 2019 +0000
irange on value_range implementation.
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 4af1bc99da9..80fcc4aee26 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -35,14 +35,23 @@ enum value_range_kind
VR_LAST
};
+class value_range_storage;
/* Range of values that can be associated with an SSA_NAME after VRP
has executed. */
class GTY((for_user)) value_range_base
{
+ friend value_range_storage;
+ friend void irange_tests ();
public:
value_range_base ();
value_range_base (value_range_kind, tree, tree);
+ value_range_base (tree, tree);
+ value_range_base (value_range_kind,
+ tree type, const wide_int &, const wide_int &);
+ value_range_base (tree type, const wide_int &, const wide_int &);
+ value_range_base (tree type, const value_range_storage *);
+ value_range_base (tree type);
void set (value_range_kind, tree, tree);
void set (tree);
@@ -77,7 +86,25 @@ public:
bool singleton_p (tree *result = NULL) const;
void dump (FILE *) const;
+ /* Support machinery for irange. */
+ static const unsigned int m_max_pairs = 2;
+ static bool supports_type_p (tree type);
+ static bool supports_ssa_p (tree ssa);
+ static bool supports_p (tree expr);
+ void cast (tree);
+ bool contains_p (tree) const;
+ unsigned num_pairs () const;
+ wide_int lower_bound (unsigned = 0) const;
+ wide_int upper_bound (unsigned) const;
+ wide_int upper_bound () const;
+ void invert ();
+ void dump () const { dump (stderr); }
+ // FIXME: Perhaps rewrite the irange versions to use pointers instead.
+ void union_ (const value_range_base &);
+ void intersect (const value_range_base &);
+
protected:
+ value_range_base normalize_symbolics () const;
void check ();
static value_range_base union_helper (const value_range_base *,
const value_range_base *);
@@ -156,6 +183,29 @@ class GTY((user)) value_range : public value_range_base
bitmap m_equiv;
};
+class value_range_storage
+{
+ friend class value_range_base;
+public:
+ static value_range_storage *alloc (const value_range_base &r)
+ {
+ value_range_storage *p = ggc_alloc<value_range_storage> ();
+ p->set (r);
+ return p;
+ }
+ bool update (const value_range_base &r)
+ {
+ set (r);
+ return true;
+ }
+private:
+ void set (const value_range_base &r)
+ {
+ m_vr = r;
+ }
+ value_range_base m_vr;
+};
+
inline
value_range_base::value_range_base ()
{
@@ -267,11 +317,11 @@ extern bool range_int_cst_singleton_p (const value_range_base *);
extern int compare_values (tree, tree);
extern int compare_values_warnv (tree, tree, bool *);
extern int operand_less_p (tree, tree);
-extern bool vrp_val_is_min (const_tree);
-extern bool vrp_val_is_max (const_tree);
+extern bool vrp_val_is_min (const_tree, bool handle_pointers = false);
+extern bool vrp_val_is_max (const_tree, bool handle_pointers = false);
-extern tree vrp_val_min (const_tree);
-extern tree vrp_val_max (const_tree);
+extern tree vrp_val_min (const_tree, bool handle_pointers = false);
+extern tree vrp_val_max (const_tree, bool handle_pointers = false);
extern void extract_range_from_unary_expr (value_range_base *vr,
enum tree_code code,
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 8a3bd2599a5..b4d5698823e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -71,6 +71,11 @@ along with GCC; see the file COPYING3. If not see
#include "wide-int-range.h"
#include "grange.h"
+static bool
+ranges_from_anti_range (const value_range_base *ar,
+ value_range_base *vr0, value_range_base *vr1,
+ bool handle_pointers = false);
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
@@ -136,6 +141,42 @@ value_range::value_range (const value_range_base &other)
set (other.kind (), other.min(), other.max (), NULL);
}
+value_range_base::value_range_base (tree type)
+{
+ set_varying (type);
+}
+
+value_range_base::value_range_base (enum value_range_kind kind,
+ tree type,
+ const wide_int &wmin,
+ const wide_int &wmax)
+{
+ tree min = wide_int_to_tree (type, wmin);
+ tree max = wide_int_to_tree (type, wmax);
+ gcc_assert (kind == VR_RANGE || kind == VR_ANTI_RANGE);
+ set_and_canonicalize (kind, min, max);
+}
+
+value_range_base::value_range_base (tree type,
+ const wide_int &wmin,
+ const wide_int &wmax)
+{
+ tree min = wide_int_to_tree (type, wmin);
+ tree max = wide_int_to_tree (type, wmax);
+ set_and_canonicalize (VR_RANGE, min, max);
+}
+
+value_range_base::value_range_base (tree min, tree max)
+{
+ set (VR_RANGE, min, max);
+}
+
+value_range_base::value_range_base (tree type ATTRIBUTE_UNUSED,
+ const value_range_storage *stow)
+{
+ *this = stow->m_vr;
+}
+
/* Like set, but keep the equivalences in place. */
void
@@ -334,6 +375,13 @@ value_range::equiv_add (const_tree var,
bool
value_range_base::singleton_p (tree *result) const
{
+ if (m_kind == VR_ANTI_RANGE)
+ {
+ value_range_base vr0, vr1;
+ return (ranges_from_anti_range (this, &vr0, &vr1, true)
+ && vr1.undefined_p ()
+ && vr0.singleton_p (result));
+ }
if (m_kind == VR_RANGE
&& vrp_operand_equal_p (min (), max ())
&& is_gimple_min_invariant (min ()))
@@ -520,10 +568,18 @@ static assert_locus **asserts_for;
/* Return the maximum value for TYPE. */
tree
-vrp_val_max (const_tree type)
+vrp_val_max (const_tree type, bool handle_pointers)
{
if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
+ {
+ if (POINTER_TYPE_P (type) && handle_pointers)
+ {
+ 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 TYPE_MAX_VALUE (type);
}
@@ -531,10 +587,14 @@ vrp_val_max (const_tree type)
/* Return the minimum value for TYPE. */
tree
-vrp_val_min (const_tree type)
+vrp_val_min (const_tree type, bool handle_pointers)
{
if (!INTEGRAL_TYPE_P (type))
- return NULL_TREE;
+ {
+ if (POINTER_TYPE_P (type) && handle_pointers)
+ return build_zero_cst (const_cast<tree> (type));
+ return NULL_TREE;
+ }
return TYPE_MIN_VALUE (type);
}
@@ -545,9 +605,9 @@ vrp_val_min (const_tree type)
is not == to the integer constant with the same value in the type. */
bool
-vrp_val_is_max (const_tree val)
+vrp_val_is_max (const_tree val, bool handle_pointers)
{
- tree type_max = vrp_val_max (TREE_TYPE (val));
+ tree type_max = vrp_val_max (TREE_TYPE (val), handle_pointers);
return (val == type_max
|| (type_max != NULL_TREE
&& operand_equal_p (val, type_max, 0)));
@@ -556,9 +616,9 @@ vrp_val_is_max (const_tree val)
/* Return whether VAL is equal to the minimum value of its type. */
bool
-vrp_val_is_min (const_tree val)
+vrp_val_is_min (const_tree val, bool handle_pointers)
{
- tree type_min = vrp_val_min (TREE_TYPE (val));
+ tree type_min = vrp_val_min (TREE_TYPE (val), handle_pointers);
return (val == type_min
|| (type_min != NULL_TREE
&& operand_equal_p (val, type_min, 0)));
@@ -652,7 +712,7 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
{
if (kind == VR_UNDEFINED)
{
- gcc_assert (TYPE_P (min));
+ gcc_assert (!min || TYPE_P (min));
set_undefined (min);
return;
}
@@ -704,11 +764,11 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
}
/* Anti-ranges that can be represented as ranges should be so. */
+ tree type = TREE_TYPE (min);
if (kind == VR_ANTI_RANGE)
{
/* For -fstrict-enums we may receive out-of-range ranges so consider
values < -INF and values > INF as -INF/INF as well. */
- tree type = TREE_TYPE (min);
bool is_min = (INTEGRAL_TYPE_P (type)
&& tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0);
bool is_max = (INTEGRAL_TYPE_P (type)
@@ -754,7 +814,6 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind,
/* FIXME: The ranger chops off out-of-bound ranges for
-fstrict-enums. Do the same here. This is only here to make
sure the ranger and VRP compare correctly. */
- tree type = TREE_TYPE (min);
if (TREE_CODE (type) == ENUMERAL_TYPE
&& kind == VR_RANGE)
{
@@ -1209,8 +1279,14 @@ vrp_set_zero_nonzero_bits (const tree expr_type,
static bool
ranges_from_anti_range (const value_range_base *ar,
- value_range_base *vr0, value_range_base *vr1)
+ value_range_base *vr0, value_range_base *vr1,
+ bool handle_pointers)
{
+ /* ?? This function is called multiple times from num_pairs,
+ lower_bound, and upper_bound. We should either memoize this, or
+ rewrite the callers in such a way that we're not re-calculating
+ this constantly. */
+
tree type = ar->type ();
vr0->set_undefined (type);
@@ -1222,18 +1298,18 @@ ranges_from_anti_range (const value_range_base *ar,
if (ar->kind () != VR_ANTI_RANGE
|| TREE_CODE (ar->min ()) != INTEGER_CST
|| TREE_CODE (ar->max ()) != INTEGER_CST
- || !vrp_val_min (type)
- || !vrp_val_max (type))
+ || !vrp_val_min (type, handle_pointers)
+ || !vrp_val_max (type, handle_pointers))
return false;
- if (tree_int_cst_lt (vrp_val_min (type), ar->min ()))
+ if (tree_int_cst_lt (vrp_val_min (type, handle_pointers), ar->min ()))
vr0->set (VR_RANGE,
- vrp_val_min (type),
+ vrp_val_min (type, handle_pointers),
wide_int_to_tree (type, wi::to_wide (ar->min ()) - 1));
- if (tree_int_cst_lt (ar->max (), vrp_val_max (type)))
+ if (tree_int_cst_lt (ar->max (), vrp_val_max (type, handle_pointers)))
vr1->set (VR_RANGE,
wide_int_to_tree (type, wi::to_wide (ar->max ()) + 1),
- vrp_val_max (type));
+ vrp_val_max (type, handle_pointers));
if (vr0->undefined_p ())
{
*vr0 = *vr1;
@@ -6547,6 +6623,197 @@ value_range::union_ (const value_range *other)
}
}
+value_range_base
+value_range_base::normalize_symbolics () const
+{
+ tree ttype = type ();
+ bool min_symbolic = is_gimple_min_invariant (min ());
+ bool max_symbolic = is_gimple_min_invariant (max ());
+ if (varying_p () || undefined_p () || (!min_symbolic && !max_symbolic))
+ return *this;
+
+ // [SYM, SYM] -> VARYING
+ if (min_symbolic && max_symbolic)
+ goto varying;
+ if (kind () == VR_RANGE)
+ {
+ // [SYM, NUM] -> [-MIN, NUM]
+ if (min_symbolic)
+ return value_range_base (VR_RANGE, vrp_val_min (ttype), max ());
+ // [NUM, SYM] -> [NUM, +MAX]
+ return value_range_base (VR_RANGE, min (), vrp_val_max (ttype));
+ }
+ gcc_assert (kind () == VR_ANTI_RANGE);
+ // ~[SYM, NUM] -> [NUM + 1, +MAX]
+ if (min_symbolic)
+ {
+ if (!vrp_val_is_max (max ()))
+ {
+ tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1);
+ return value_range_base (VR_RANGE, n, vrp_val_max (ttype));
+ }
+ goto varying;
+ }
+ // ~[NUM, SYM] -> [-MIN, NUM - 1]
+ if (!vrp_val_is_min (min ()))
+ {
+ tree n = wide_int_to_tree (ttype, wi::to_wide (min ()) - 1);
+ return value_range_base (VR_RANGE, vrp_val_min (ttype), n);
+ }
+ varying:
+ value_range_base tmp;
+ tmp.set_varying (ttype);
+ return tmp;
+}
+
+unsigned
+value_range_base::num_pairs () const
+{
+ if (undefined_p ())
+ return 0;
+ if (varying_p ())
+ return 1;
+ if (symbolic_p ())
+ return normalize_symbolics ().num_pairs ();
+ if (m_kind == VR_ANTI_RANGE)
+ {
+ value_range_base vr0, vr1;
+ gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true));
+ if (vr1.undefined_p ())
+ return 1;
+ return 2;
+ }
+ return 1;
+}
+
+wide_int
+value_range_base::lower_bound (unsigned pair) const
+{
+ if (symbolic_p ())
+ return normalize_symbolics ().lower_bound (pair);
+
+ gcc_assert (!undefined_p ());
+ gcc_assert (pair + 1 <= num_pairs ());
+ tree t = NULL;
+ if (varying_p ())
+ t = vrp_val_min (type (), true);
+ else if (m_kind == VR_RANGE)
+ t = m_min;
+ else if (m_kind == VR_ANTI_RANGE)
+ {
+ value_range_base vr0, vr1;
+ gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true));
+ if (pair == 0)
+ t = vr0.min ();
+ else if (pair == 1)
+ t = vr1.min ();
+ else
+ gcc_unreachable ();
+ }
+ return wi::to_wide (t);
+}
+
+wide_int
+value_range_base::upper_bound (unsigned pair) const
+{
+ if (symbolic_p ())
+ return normalize_symbolics ().upper_bound (pair);
+
+ gcc_assert (!undefined_p ());
+ gcc_assert (pair + 1 <= num_pairs ());
+ tree t = NULL;
+ if (varying_p ())
+ t = vrp_val_max (type (), true);
+ else if (m_kind == VR_RANGE)
+ t = m_max;
+ else if (m_kind == VR_ANTI_RANGE)
+ {
+ value_range_base vr0, vr1;
+ gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true));
+ if (pair == 0)
+ t = vr0.max ();
+ else if (pair == 1)
+ t = vr1.max ();
+ else
+ gcc_unreachable ();
+ }
+ return wi::to_wide (t);
+}
+
+wide_int
+value_range_base::upper_bound () const
+{
+ unsigned pairs = num_pairs ();
+ gcc_assert (pairs > 0);
+ return upper_bound (pairs - 1);
+}
+
+void
+value_range_base::cast (tree typ)
+{
+ value_range_base tem;
+ enum ranges_mode save = flag_ranges_mode;
+ /* Avoid infinite recursion in the ranger vs vrp checking code. */
+ flag_ranges_mode = RANGES_VRP;
+ /* At some point we should inline all of the CONVERT_EXPR code from
+ extract_range_from_unary_expr here. */
+ extract_range_from_unary_expr (&tem, CONVERT_EXPR, typ, this, type ());
+ flag_ranges_mode = save;
+ *this = tem;
+}
+
+/* Return TRUE if range contains INTEGER_CST. */
+
+bool
+value_range_base::contains_p (tree cst) const
+{
+ gcc_assert (TREE_CODE (cst) == INTEGER_CST);
+ if (symbolic_p ())
+ return normalize_symbolics ().contains_p (cst);
+ return value_inside_range (cst) == 1;
+}
+
+void
+value_range_base::invert ()
+{
+ if (undefined_p ())
+ set_varying (type ());
+ else if (varying_p ())
+ set_undefined (type ());
+ else if (m_kind == VR_RANGE)
+ m_kind = VR_ANTI_RANGE;
+ else if (m_kind == VR_ANTI_RANGE)
+ m_kind = VR_RANGE;
+ else
+ gcc_unreachable ();
+}
+
+void
+value_range_base::union_ (const value_range_base &r)
+{
+ /* 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;
+}
+
+void
+value_range_base::intersect (const value_range_base &r)
+{
+ /* 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;
+}
+
/* Visit all arguments for PHI node PHI that flow through executable
edges. If a valid value range can be derived from all the incoming
value ranges, set a new range for the LHS of PHI. */
@@ -7241,3 +7512,24 @@ determine_value_range (tree expr, wide_int *min, wide_int *max)
return VR_VARYING;
}
+
+#if IRANGE_WITH_VALUE_RANGE
+irange
+value_range_to_irange (tree type ATTRIBUTE_UNUSED, const value_range_base &vr)
+{
+ return vr;
+}
+
+irange
+value_range_to_irange (tree type, enum value_range_kind kind,
+ const wide_int &min, const wide_int &max)
+{
+ return irange (kind, type, min, max);
+}
+
+value_range_base
+irange_to_value_range (const irange &ir)
+{
+ return ir;
+}
+#endif // IRANGE_TO_VALUE_RANGE
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 6bc62f46d2a..def5a163e90 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -105,7 +105,7 @@ set_value_range_to_truthvalue (value_range *vr, tree type)
value_range *
vr_values::get_value_range (const_tree var)
{
- static const value_range vr_const_varying (VR_VARYING, NULL, NULL);
+ tree type = TREE_TYPE (var);
value_range *vr;
tree sym;
unsigned ver = SSA_NAME_VERSION (var);
@@ -118,7 +118,13 @@ vr_values::get_value_range (const_tree var)
We should get here at most from the substitute-and-fold stage which
will never try to change values. */
if (ver >= num_vr_values)
- return CONST_CAST (value_range *, &vr_const_varying);
+ {
+ /* ?? At some point we should find a way to cache varying ranges
+ by type. In the tree type itself? */
+ vr = vrp_value_range_pool.allocate ();
+ vr->set_varying (type);
+ return vr;
+ }
vr = vr_value[ver];
if (vr)
@@ -126,11 +132,16 @@ vr_values::get_value_range (const_tree var)
/* After propagation finished do not allocate new value-ranges. */
if (values_propagated)
- return CONST_CAST (value_range *, &vr_const_varying);
+ {
+ /* See note about caching varying above. */
+ vr = vrp_value_range_pool.allocate ();
+ vr->set_varying (type);
+ return vr;
+ }
/* Create a default value range. */
vr_value[ver] = vr = vrp_value_range_pool.allocate ();
- vr->set_undefined ();
+ vr->set_undefined (type);
/* If VAR is a default definition of a parameter, the variable can
take any value in VAR's type. */
@@ -179,9 +190,7 @@ vr_values::set_defs_to_varying (gimple *stmt)
FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
{
value_range *vr = get_value_range (def);
- /* Avoid writing to vr_const_varying get_value_range may return. */
- if (!vr->varying_p ())
- vr->set_varying (TREE_TYPE (def));
+ vr->set_varying (TREE_TYPE (def));
}
}
@@ -995,6 +1004,9 @@ check_for_binary_op_overflow (enum tree_code subcode, tree type,
tree op1, irange &ir1,
bool *ovf)
{
+ if (ir0.undefined_p () || ir1.undefined_p ())
+ return false;
+
tree vr0min = wide_int_to_tree (TREE_TYPE (op0), ir0.lower_bound ());
tree vr0max = wide_int_to_tree (TREE_TYPE (op0), ir0.upper_bound ());
tree vr1min = wide_int_to_tree (TREE_TYPE (op1), ir1.lower_bound ());
@@ -3948,6 +3960,12 @@ range_misc::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi,
tree tem;
gassign *conv;
+ /* An undefined means this statement is unreachable. Bail to avoid
+ calculating anything in range_fits_type_p below. Perhaps we
+ should generically bail from simplify_stmt_using_ranges. */
+ if (ir.undefined_p ())
+ return false;
+
/* First check if we can use a signed type in place of an unsigned. */
scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
if (TYPE_UNSIGNED (TREE_TYPE (rhs1))