Ive been working on adding points to information to prange. There are 2
primary things this aims to replace.
1 - VRP currently manages a side table of pointer equivalences in
value-pointer-equiv.{h,cc}. Only VRP ever sees this and it is used in a
dominator based walk to attempt to identify is_gimple_min_invariant_p ()
expressions that can replace SSA names in gimple.
2 - pointer_query from pointer-query.{h,cc} is used by some of the
warning code to attempt to track which object SSA names point to, and
also track ranges for where within the referenced object a pointer may
as well as the possible size of that referenced objectfor object-size
and bounds analysis. When the author wrote the code, ranger was not
advanced enough to be of use, so this class was created in an attempt to
find the information. It has maintenance issues as well as incomplete
information.
This first patch set will introduce points-to information and implement
only the first of the 2 stages. The points to information will be only
the invariant values (is_gimple-min_invariant_p) , with the full version
which replaces pointer_query coming later. This will make all the
information in the VRP side table available to any consumer of prange,
and I see its effects in IPA immediately. It also does a better job
within VRP than the side table did as ranger is a more capable flow
analysis engine than a simple DOM walk.
This RFC is mostly to ask about the API interface in prange, and the
naming conventions. I've reworked it a couple of times and this is what
I have evolved to, but perhaps others have better ideas.
points-to information is embedded in the prange class. It was
originally a class of its own, but I found using it a bit awkward, and
once I simplified the API, it didn't seem as necessary as I first thought.
-------
"unknown" terminology is used to match irange_bitmask, indicating we
have no idea what it points to and there is no info.
// unknown_p () is true if no object is pointed to.
* void set_pt_unknown ();
bool pt_unknown_p () const;*
---------
I used the concept of points to and points_away to represent opposite
side of a branch . ie
if (ptr == &foo)
On the true side, ptr will point_to &foo, and on the false side, ptr
will point_away from &foo.
This allows for easy equality and inequality checks. Internally the
points-to field will both refer to &foo, and there is a flag indicating
whether the pointer points to it or away from it.
I also use the term "invariant", as all points to fields being referred
to by these routines are is_gimple_min_invariant_p ().
* // Invariant points-to are is_gimple_min_invariant_p ().
// Return expression or NULL_TREE for points-to or away
tree pt_invariant () const;
tree pt_invariant_away () const;
// Return true if present and identical for THIS and R.
bool pt_invariant_p (const prange &r) const;
bool pt_invariant_away_p (const prange &r) const;
*
* // Invert flips the flag and returns true, if THIS p;olints to
something.
bool pt_invert ();
// Return true if THIS and R point to and away from the same object.
bool pt_inverted_p (const prange &r) const;*
So for instance operator_equal () checks the points to info between op1
and op2 to see if they are known to point to or away from the same
invariant value:
// Check for points to equality and inequality first.
if (op1.pt_invariant_p (op2))
r = range_true (type);
else if (op1.pt_inverted_p (op2))
r = range_false (type);
And tree-vrp simply checks to see if there is a points-to value and uses it:
if (is_a <prange> (r))
{
prange &p = as_a <prange> (r);
ret = p.pt_invariant ();
}
return ret;
-----------
You can set or copy points-to info,:
*void set_pt (tree ptr, bool points_to_p = true);
void copy_pt (const prange &r);*
Although there isn't a lot of need in most cases. The gimple_range_fold
machinery takes care of setting it on expressions, and the range-op
operators will adjust and propagate the information automatically.
-------
These 3 functions are added for the upcoming pointer_query changes. The
provide the same information that pointer-query tracks. They are
available for use for the invariant code as well, with the values picked
up from tree-affine and are therefore currently always constant.
* // pt_base () - object/allocation the pointer refers into.
tree pt_base () const;
// pt_offset () - possible byte offset range from BASE.
void pt_offset (irange &) const;
// pt_size () - possible size range of the referenced object.
void pt_size (irange &) const;*
--------------------
Once the variant code is added to support pointer_query, the only added
routines currently tagged to be added (and not included in this patch) are:
* void set (tree base, const irange& size, const irange &offset);
void update_size (irange &size);
void update_offset (irange &offset);*
To allow adjustments to size and offset as they are discovered., again,
mostly handled by range-ops and the gimple-range-fold machinery.
----------------------
Clearly as this gets used, I can make adjustments, but I wanted to get a
feel if anyone had any comments or suggestions that can be incorporated
from the start, or something else i missed. Or just general quesitons
One other note, IPA requires unshared expressions, so I added a facility
to allocating a prange which allocated an unshared points-to field for
this use case. The default is shared.
------------------------
Oh, there are some testcase adjustments that need to be made thanks to
the increase in information already being seen.:
A series of the mem/str-chk testcases ave failures because they encode
assumptions about previous imprecision: either expecting an object to
remain unknown, expecting a _chk call to remain, or expecting one to be
folded only under older object-size behaviour. The enhanced PTA
information causes these tests to be checking for something whcih is now
better optimized.
I opened PR123160 because these PTA changes expose a bug in gimple-fold
with the object size calculation. When pointer_plus is used in an
expression, it can return incorrect results and this results ina test
case failure.
And finally, IPA is automatically passing the points to around, and its
caused me numerous issues. mostly resolved now. :-) The biggest
remaining issue is that if a function returns a constant points to
value, TREE_VRP will happily make the replacementand this gives the
appearance of inlining something when its marked no inline.
An example (without pointers) is
int __attribute__ ((noinline)) Bar ()
{ return 10; }
int main ()
{ return Bar () != 0; }
IPA provides "10" as the return value of Bar which is assigned to an SSA
name. VRP sees [10,10] as the range for that SSA name and this
effectively replaces Bar() with 10. So it looks lie inlining, even
though it is simple value propagation. I talked to mjambor about this,
and he indicates this is expected, and ((noipa) should also be added to
avoid this. The points-to code triggers a failure in the testsuite
(gcc.misc-tests/gcov-14.c) where something similar has happened with the
points-to info.
And finally, gcc.dg/Wreturn-local-addr-9.c use to fail with a bogus
"may return address of local variable" at -Os.. and that now goes away
with this :-)
Ive attached the current WIP patch which applies to trunk and bootstraps
on x86_64
Please, feel free to comment and ask questions. I intend to commit
it wthin a few days assuming i get all remaining wrinkles worked out.
And then proceed to continue working on the pointer_query replacement
effort. And of course handling any fallout :-) We can certainly make
adjustments in trunk.
Andrew
PS
If an pointer does point to an object, I have elected to have
singleton_p () NOT return true and the item that it points to. I found
there were too many places which were not expecting pointer invariant
expressions that at least for now, one has to specifically ask for the
invariant pointer, as the new tree-vrp changes do:
if (r.singleton_p (&ret))
return ret;
else
ret = NULL_TREE;
if (is_a <prange> (r))
{
prange &p = as_a <prange> (r);
ret = p.pt_invariant ();
}
return ret;
<...>
What would you think the expected behavior to be? should
singleton_p() return any invariant points to value? I'm tempted to say
yes... If so I can attempt to revisit that in a followup patch and
see what problems I encounter.
From 247718ee3110954a534c1e09df2717c70f04bf66 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Wed, 10 Jun 2026 13:42:27 -0400
Subject: [PATCH 05/12] Points-to functionality for prange.
Add basic invariant points-to functionality to prange.
Use tree affine for base and offset info
Adjust various range-ops to support points-to.
* gimple-range-fold.cc (x_fold_context): New.
(pta_valueize): New.
(fold_using_range::fold_stmt): Set PTA fields.
(fold_using_range::range_of_phi): Ditto.
* ipa-prop.cc (ipa_vr::ipa_vr): Allocate unshared range.
* range-op-ptr.cc (pointer_plus_operator::fold_range): Handle PTA.
(pointer_plus_operator::op2_range): Ditto.
(operator_pointer_diff::fold_range): Ditto.
(operator_cast::fold_range): Ditto.
(operator_cast::lhs_op1_relation): Ditto.
(operator_equal::fold_range): Ditto.
(operator_not_equal::fold_range): Ditto.
* value-query.cc (range_query::get_tree_range): Ditto.
* value-range-pretty-print.cc (vrange_printer::print_pt): New.
(vrange_printer::visit): Add print support.
* value-range-pretty-print.h (vrange_printer::print_pt): New prototype.
* value-range-storage.cc (vrange_allocator::clone): Allow unshared
expression allocation.
(vrange_storage::alloc): Likewise.
(prange_storage::alloc): Likewise.
(prange_storage::prange_format): Copy PTA.
(prange_storage::set_prange): Ditto.
(prange_storage::get_prange): Ditto.
(prange_storage::equal_p): Compare points-to data.
(ggc_alloc_vrange_storage): Allow unshared expression.
* value-range-storage.h (clone): Adjust param list.
(prange_storage::m_pt, m_points_to_p): New.
* value-range.cc (inchash::add_vrange): Add points-to to hash value.
(prange::set_pt): New.
(prange::pt_base): New.
(prange::pt_offset): New.
(prange::pt_size): New.
(prange::set): Initialize PTA field.
(prange::union_): Handle PTA cases.
(prange::intersect): Ditto.
(prange::operator=): Ditto.
(prange::operator==): Ditto.
(prange::invert): Handle PTA cases.
(prange::verify_range): Ditto.
* value-range.h (set_pt, set_pt_unknown, pt_unknown_p,
pt_invariant, pt_invariant_away, pt_invariant_p, pt_invariant_away_p,
pt_invert, pt_inverted_p, pt_base, pt_offset, pt_size,
pt_equal_p): New prange prototypes.
(prange::m_pt, prange::m_points_to_p): New members.
(prange::set_undefined): Clear PTA fields.
(prange::set_varying): Ditto.
(prange::set_nonzero): Ditto.
(prange::set_zero): Ditto.
(prange::zero_p): Check PTA fields.
(varying_compatible_p): Ditto.
(prange::set_pt): New.
(prange::set_pt_unknown): New.
(prange::pt_unknown_p): New.
(prange::pt_equal_p): New prange prototypes.
(prange::pt_inverted_p): New.
(prange::pt_invert): New.
(prange::pt_invariant): New.
(prange::pt_invariant_away): New.
(prange::pt_invariant_p): New.
(prange::pt_invariant_away_p): New.
---
gcc/gimple-range-fold.cc | 70 +++++++++++++--
gcc/ipa-prop.cc | 2 +-
gcc/range-op-ptr.cc | 43 ++++++++--
gcc/value-query.cc | 15 ++--
gcc/value-range-pretty-print.cc | 45 ++++++++++
gcc/value-range-pretty-print.h | 1 +
gcc/value-range-storage.cc | 33 ++++++--
gcc/value-range-storage.h | 13 ++-
gcc/value-range.cc | 144 ++++++++++++++++++++++++++++++-
gcc/value-range.h | 145 +++++++++++++++++++++++++++++++-
10 files changed, 477 insertions(+), 34 deletions(-)
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index c3f720a786f..4f4827bb46f 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -651,6 +651,25 @@ gimple_range_adjustment (vrange &res, const gimple *stmt)
}
}
+// Provide context to the gimple fold callback.
+
+static struct
+{
+ gimple *m_stmt;
+ range_query *m_query;
+} x_fold_context;
+
+// Gimple fold callback.
+
+static tree
+pta_valueize (tree name)
+{
+ tree ret
+ = x_fold_context.m_query->value_of_expr (name, x_fold_context.m_stmt);
+
+ return ret ? ret : name;
+}
+
// Calculate a range for statement S and return it in R. If NAME is provided it
// represents the SSA_NAME on the LHS of the statement. It is only required
// if there is more than one lhs/output. If a range cannot
@@ -721,6 +740,34 @@ fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name)
gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name)));
range_cast (r, TREE_TYPE (name));
}
+
+ // IF this is not a prange, we are done.
+ if (!is_a <prange> (r))
+ return true;
+
+ prange &p = as_a <prange> (r);
+ // Check to see if points_to should be set.
+ if (p.pt_unknown_p () && name && gimple_code (s) == GIMPLE_ASSIGN)
+ {
+ tree rhs = gimple_assign_rhs1 (s);
+ tree_code code = gimple_assign_rhs_code (s);
+ // If code is SSA_NAME, any points to would already be copied.
+ if (code != SSA_NAME && get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && TREE_CODE (rhs) == ADDR_EXPR)
+ {
+ p.set_pt (rhs, true);
+ }
+ else
+ {
+ // If we couldn't find anything, try fold.
+ x_fold_context = { s, src.query () };
+ rhs = gimple_fold_stmt_to_constant_1 (s, pta_valueize, pta_valueize);
+ if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
+ {
+ p.set_pt (rhs, true);
+ }
+ }
+ }
return true;
}
@@ -1172,7 +1219,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
seen_arg = true;
single_arg = arg;
}
- else if (single_arg != arg)
+ else if (!vrp_operand_equal_p (single_arg, arg))
single_arg = NULL_TREE;
// Once the value reaches varying, stop looking.
@@ -1210,14 +1257,27 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
if (single_arg)
src.register_relation (phi, VREL_EQ, phi_def, single_arg);
}
- else if (src.get_operand (arg_range, single_arg)
- && arg_range.singleton_p ())
+ else if (src.get_operand (arg_range, single_arg))
{
+ // Check if the single argument points to a specific object.
+ if (is_a <prange> (arg_range))
+ {
+ prange &ptr = as_a <prange> (arg_range);
+ // If it doesn't already point at something, set points to.
+ if (!ptr.pt_unknown_p ()
+ && TREE_CODE (single_arg) == ADDR_EXPR)
+ ptr.set_pt (single_arg, true);
+ r = ptr;
+ return true;
+ }
// Numerical arguments that are a constant can be returned as
// the constant. This can help fold later cases where even this
// constant might have been UNDEFINED via an unreachable edge.
- r = arg_range;
- return true;
+ if (arg_range.singleton_p ())
+ {
+ r = arg_range;
+ return true;
+ }
}
}
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index 330c8a39e5b..79b59a6a76f 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -148,7 +148,7 @@ ipa_vr::ipa_vr ()
}
ipa_vr::ipa_vr (const vrange &r)
- : m_storage (ggc_alloc_vrange_storage (r)),
+ : m_storage (ggc_alloc_vrange_storage (r, false /* shared_p */)),
m_type (r.type ())
{
}
diff --git a/gcc/range-op-ptr.cc b/gcc/range-op-ptr.cc
index 6461530a9a3..a96e53bf141 100644
--- a/gcc/range-op-ptr.cc
+++ b/gcc/range-op-ptr.cc
@@ -370,24 +370,29 @@ pointer_plus_operator::fold_range (prange &r, tree type,
else
r.set_varying (type);
+ // If op1 refers to an object, op1 + 0 will also refer to the object.
+ if (rh_lb == rh_ub && rh_lb == 0)
+ r.set_pt (op1);
+
update_known_bitmask (r, POINTER_PLUS_EXPR, op1, op2);
return true;
}
bool
pointer_plus_operator::op2_range (irange &r, tree type,
- const prange &lhs ATTRIBUTE_UNUSED,
- const prange &op1 ATTRIBUTE_UNUSED,
+ const prange &lhs,
+ const prange &op1,
relation_trio trio) const
{
relation_kind rel = trio.lhs_op1 ();
r.set_varying (type);
// If the LHS and OP1 are equal, the op2 must be zero.
- if (rel == VREL_EQ)
+ if (rel == VREL_EQ || lhs.pt_invariant_p (op1))
r.set_zero (type);
// If the LHS and OP1 are not equal, the offset must be non-zero.
- else if (rel == VREL_NE)
+ // AWM: Check if aliasing may mean we can't do the not_equal check.
+ else if (rel == VREL_NE || lhs.pt_inverted_p (op1))
r.set_nonzero (type);
else
return false;
@@ -490,6 +495,9 @@ operator_pointer_diff::fold_range (irange &r, tree type,
r.set_varying (type);
relation_kind rel = trio.op1_op2 ();
op1_op2_relation_effect (r, type, op1, op2, rel);
+ // if op1 and op2 point to the same object, the diff is 0.
+ if (op1.pt_invariant_p (op2))
+ r.set_zero (type);
update_bitmask (r, op1, op2);
return true;
}
@@ -564,6 +572,10 @@ operator_cast::fold_range (prange &r, tree type,
return true;
r.set (type, inner.lower_bound (), inner.upper_bound ());
+
+ // The resulting pointer still points to the same object.
+ r.set_pt (inner);
+
r.update_bitmask (inner.get_bitmask ());
return true;
}
@@ -725,6 +737,15 @@ operator_cast::lhs_op1_relation (const prange &lhs,
return VREL_VARYING;
}
+ // If the pointer precisions are the same, check for equality and
+ // inequality in the points to fields.
+ if (lhs_prec == op1_prec)
+ {
+ if (lhs.pt_invariant_p (op1))
+ return VREL_EQ;
+ if (lhs.pt_inverted_p (op1))
+ return VREL_NE;
+ }
unsigned prec = MIN (lhs_prec, op1_prec);
return bits_to_pe (prec);
}
@@ -878,7 +899,12 @@ operator_equal::fold_range (irange &r, tree type,
// consist of a single value, and then compare them.
bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
- if (op1_const && op2_const)
+ // Check for points to equality and inequality first.
+ if (op1.pt_invariant_p (op2))
+ r = range_true (type);
+ else if (op1.pt_inverted_p (op2))
+ r = range_false (type);
+ else if (op1_const && op2_const)
{
if (wi::eq_p (op1.lower_bound (), op2.upper_bound()))
r = range_true (type);
@@ -977,7 +1003,12 @@ operator_not_equal::fold_range (irange &r, tree type,
// consist of a single value, and then compare them.
bool op1_const = wi::eq_p (op1.lower_bound (), op1.upper_bound ());
bool op2_const = wi::eq_p (op2.lower_bound (), op2.upper_bound ());
- if (op1_const && op2_const)
+ // Check for points to equality and inequality first.
+ if (op1.pt_inverted_p (op2))
+ r = range_true (type);
+ else if (op1.pt_invariant_p (op2))
+ r = range_false (type);
+ else if (op1_const && op2_const)
{
if (wi::ne_p (op1.lower_bound (), op2.upper_bound()))
r = range_true (type);
diff --git a/gcc/value-query.cc b/gcc/value-query.cc
index e7a75832cb4..decf4e4d0ac 100644
--- a/gcc/value-query.cc
+++ b/gcc/value-query.cc
@@ -388,13 +388,16 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt,
case ADDR_EXPR:
{
- // Handle &var which can show up in phi arguments.
+ // Handle &expr, and set points to.
if (tree_single_nonzero_p (expr))
- {
- r.set_nonzero (type);
- return true;
- }
- break;
+ r.set_nonzero (type);
+ else
+ r.set_varying (type);
+ // Set points to field.
+ gcc_checking_assert (is_a <prange> (r));
+ prange &ptr = as_a <prange> (r);
+ ptr.set_pt (expr, true);
+ return true;
}
default:
diff --git a/gcc/value-range-pretty-print.cc b/gcc/value-range-pretty-print.cc
index cd9a57d54cb..c3e62b0d73a 100644
--- a/gcc/value-range-pretty-print.cc
+++ b/gcc/value-range-pretty-print.cc
@@ -112,6 +112,49 @@ vrange_printer::visit (const irange &r) const
print_irange_bitmasks (pp, r.m_bitmask);
}
+void
+vrange_printer::print_pt (const prange &r) const
+{
+ bool points_to_p = false;
+ tree pt = r.pt_invariant ();
+ if (pt)
+ points_to_p = true;
+ else
+ pt = r.pt_invariant_away ();
+
+ if (pt)
+ {
+ if (points_to_p)
+ pp_string (pp, " -> ");
+ else
+ pp_string (pp, " ! -> ");
+ dump_generic_node (pp, pt, 0, TDF_NONE | TDF_NOUID, false);
+ if (points_to_p)
+ {
+ int_range_max sz;
+ int_range_max off;
+ tree b;
+ b = r.pt_base ();
+ r.pt_offset(off);
+ r.pt_size (sz);
+ pp_string (pp, " { Base: ");
+ dump_generic_node (pp, b, 0, TDF_NONE | TDF_NOUID, false);
+ if (!off.varying_p () && !off.undefined_p () && !off.zero_p ())
+ {
+ pp_string (pp, " ; Off: ");
+ visit (off);
+ }
+ if (!sz.varying_p () && !sz.undefined_p ())
+ {
+ pp_string (pp, " ; Size: ");
+ visit (sz);
+ }
+ pp_string (pp, " }");
+ }
+
+ }
+}
+
void
vrange_printer::visit (const prange &r) const
{
@@ -135,6 +178,8 @@ vrange_printer::visit (const prange &r) const
print_int_bound (pp, r.upper_bound (), r.type ());
pp_character (pp, ']');
print_irange_bitmasks (pp, r.m_bitmask);
+ // Dump the points to field if there is one.
+ print_pt (r);
}
void
diff --git a/gcc/value-range-pretty-print.h b/gcc/value-range-pretty-print.h
index e5156b2e654..b6e6a488782 100644
--- a/gcc/value-range-pretty-print.h
+++ b/gcc/value-range-pretty-print.h
@@ -30,6 +30,7 @@ public:
void visit (const prange &) const override;
void visit (const frange &) const override;
private:
+ void print_pt (const prange &) const;
void print_frange_nan (const frange &) const;
void print_real_value (tree type, const REAL_VALUE_TYPE &r) const;
diff --git a/gcc/value-range-storage.cc b/gcc/value-range-storage.cc
index b2b3e445590..6a7ce4ceed3 100644
--- a/gcc/value-range-storage.cc
+++ b/gcc/value-range-storage.cc
@@ -24,6 +24,7 @@ along with GCC; see the file COPYING3. If not see
#include "backend.h"
#include "tree.h"
#include "gimple.h"
+#include "gimplify.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "fold-const.h"
@@ -108,9 +109,9 @@ vrange_allocator::free (void *p)
// it.
vrange_storage *
-vrange_allocator::clone (const vrange &r)
+vrange_allocator::clone (const vrange &r, bool shared_p)
{
- return vrange_storage::alloc (*m_alloc, r);
+ return vrange_storage::alloc (*m_alloc, r, shared_p);
}
vrange_storage *
@@ -141,12 +142,13 @@ vrange_allocator::clone_undefined (tree type)
// it. Return NULL if R is unsupported.
vrange_storage *
-vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r)
+vrange_storage::alloc (vrange_internal_alloc &allocator, const vrange &r,
+ bool shared_p)
{
if (is_a <irange> (r))
return irange_storage::alloc (allocator, as_a <irange> (r));
if (is_a <prange> (r))
- return prange_storage::alloc (allocator, as_a <prange> (r));
+ return prange_storage::alloc (allocator, as_a <prange> (r), shared_p);
if (is_a <frange> (r))
return frange_storage::alloc (allocator, as_a <frange> (r));
return NULL;
@@ -591,7 +593,8 @@ frange_storage::fits_p (const frange &) const
//============================================================================
prange_storage *
-prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r)
+prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r,
+ bool shared_p)
{
unsigned num_words;
prange_format (r, num_words);
@@ -606,6 +609,9 @@ prange_storage::alloc (vrange_internal_alloc &allocator, const prange &r)
size_t size = sizeof (prange_storage) + extra_size;
prange_storage *p = static_cast <prange_storage *> (allocator.alloc (size));
new (p) prange_storage (r);
+ if (p->m_pt && !shared_p)
+ p->m_pt = unshare_expr_without_location (p->m_pt);
+
return p;
}
@@ -657,7 +663,8 @@ prange_storage::prange_format (const prange &r, unsigned &num_words)
num_words += 2;
// PR_FULL must have a bitmask or points to, or it should be PR_VARYING.
- gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ());
+ gcc_checking_assert (kind != PR_FULL || !r.get_bitmask ().unknown_p ()
+ || r.m_pt != NULL_TREE);
return kind;
}
@@ -667,6 +674,8 @@ prange_storage::set_prange (const prange &r)
unsigned num_words;
m_kind = prange_format (r, num_words);
m_has_bitmask = !r.get_bitmask ().unknown_p ();
+ m_pt = r.m_pt;
+ m_points_to_p = r.m_points_to_p;
unsigned index = 0;
@@ -751,6 +760,9 @@ prange_storage::get_prange (prange &r, tree type) const
else
r.m_bitmask.set_unknown (TYPE_PRECISION (type));
+ r.m_points_to_p = m_points_to_p;
+ r.m_pt = m_pt;
+
if (flag_checking)
r.verify_range ();
}
@@ -803,6 +815,11 @@ prange_storage::equal_p (const prange &r) const
if (!r.m_bitmask.unknown_p ())
return false;
+ if (m_pt != r.m_pt)
+ return false;
+ if (m_points_to_p != r.m_points_to_p)
+ return false;
+
return true;
}
@@ -827,7 +844,7 @@ vrange_storage *ggc_alloc_vrange_storage (tree type)
return ggc_vrange_allocator.clone_varying (type);
}
-vrange_storage *ggc_alloc_vrange_storage (const vrange &r)
+vrange_storage *ggc_alloc_vrange_storage (const vrange &r, bool shared_p)
{
- return ggc_vrange_allocator.clone (r);
+ return ggc_vrange_allocator.clone (r, shared_p);
}
diff --git a/gcc/value-range-storage.h b/gcc/value-range-storage.h
index 280aa65fe2d..13d097666d6 100644
--- a/gcc/value-range-storage.h
+++ b/gcc/value-range-storage.h
@@ -30,7 +30,7 @@ public:
// Use GC memory when GC is true, otherwise use obstacks.
vrange_allocator (bool gc = false);
~vrange_allocator ();
- class vrange_storage *clone (const vrange &r);
+ class vrange_storage *clone (const vrange &r, bool shared_p = true);
vrange_storage *clone_varying (tree type);
vrange_storage *clone_undefined (tree type);
void *alloc (size_t size);
@@ -49,7 +49,8 @@ private:
class GTY((desc ("%h.m_discriminator"), tag("VR_UNKNOWN"))) vrange_storage
{
public:
- static vrange_storage *alloc (vrange_internal_alloc &, const vrange &);
+ static vrange_storage *alloc (vrange_internal_alloc &, const vrange &,
+ bool shared_p = true);
void get_vrange (vrange &r, tree type) const;
void set_vrange (const vrange &r);
bool fits_p (const vrange &r) const;
@@ -121,7 +122,8 @@ public:
friend void gt_pch_nx_vrange_storage(void *);
friend void gt_pch_p_14vrange_storage(void *, void *, gt_pointer_operator,
void *);
- static prange_storage *alloc (vrange_internal_alloc &, const prange &);
+ static prange_storage *alloc (vrange_internal_alloc &, const prange &,
+ bool shared_p = true);
void set_prange (const prange &r);
void get_prange (prange &r, tree type) const;
bool equal_p (const prange &r) const;
@@ -135,6 +137,8 @@ private:
enum prange_kind m_kind;
bool m_has_bitmask;
+ bool m_points_to_p;
+ tree m_pt;
// We don't use TRAILING_WIDE_INT_ACCESSOR because the getters here
// must be const. Perhaps TRAILING_WIDE_INT_ACCESSOR could be made
@@ -170,6 +174,7 @@ class GTY((tag ("VR_FRANGE"))) frange_storage : public vrange_storage
};
extern vrange_storage *ggc_alloc_vrange_storage (tree type);
-extern vrange_storage *ggc_alloc_vrange_storage (const vrange &);
+extern vrange_storage *ggc_alloc_vrange_storage (const vrange &,
+ bool shared_p = true);
#endif // GCC_VALUE_RANGE_STORAGE_H
diff --git a/gcc/value-range.cc b/gcc/value-range.cc
index fa17dd276af..488feb5ca0f 100644
--- a/gcc/value-range.cc
+++ b/gcc/value-range.cc
@@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see
#include "value-range-pretty-print.h"
#include "fold-const.h"
#include "gimple-range.h"
+#include "tree-dfa.h"
+#include "tree-affine.h"
// Return the bitmask inherent in a range : TYPE [MIN, MAX].
// This used to be get_bitmask_from_range ().
@@ -458,6 +460,14 @@ add_vrange (const vrange &v, inchash::hash &hstate,
irange_bitmask bm = r.get_bitmask ();
hstate.add_wide_int (bm.value ());
hstate.add_wide_int (bm.mask ());
+ bool flag = false;
+ tree tmp = r.pt_invariant ();
+ if (tmp)
+ flag = true;
+ else
+ tmp = r.pt_invariant_away ();
+ hstate.add_ptr (tmp);
+ hstate.add_flag (flag);
}
return;
}
@@ -516,6 +526,101 @@ irange::set_nonnegative (tree type)
wi::to_wide (TYPE_MAX_VALUE (type)));
}
+
+// Set the points to info for EXPR if possible. POINTS_TO_P is true if it
+// points to EXPR, and FALSE if it points away.
+
+void
+prange::set_pt (tree expr, bool points_to_p)
+{
+ gcc_checking_assert (m_kind != VR_UNDEFINED);
+ gcc_checking_assert (!expr || TREE_CODE (expr) != SSA_NAME);
+
+ m_pt = NULL_TREE;
+ m_points_to_p = false;
+
+ // No points to initially may make this VARYING.
+ if (varying_compatible_p ())
+ set_varying (type ());
+ else
+ m_kind = VR_RANGE;
+
+ if (!expr)
+ return;
+
+ gcc_checking_assert (TREE_CODE (expr) == ADDR_EXPR);
+
+ // Ensure only constants get through for now.
+ if (!is_gimple_min_invariant (expr))
+ return;
+
+ aff_tree offset;
+ poly_widest_int size;
+ tree obj = TREE_OPERAND (expr, 0);
+ tree base = get_inner_reference_aff (obj, &offset, &size);
+
+ if (!base)
+ return;
+ if (!offset.offset.is_constant ())
+ return;
+ if (!size.is_constant ())
+ return;
+
+ m_pt = expr;
+ m_points_to_p = points_to_p;
+ m_kind = VR_RANGE;
+}
+
+// Return object/allocation the pointer refers into, otherwise NULL_TREE.
+
+tree
+prange::pt_base () const
+{
+ if (!m_pt)
+ return NULL_TREE;
+
+ aff_tree off;
+ poly_widest_int sz;
+
+ gcc_checking_assert (m_pt);
+ return get_inner_reference_aff (m_pt, &off, &sz);
+}
+
+// Return possible byte offset range from BASE.
+
+void
+prange::pt_offset (irange &r) const
+{
+ aff_tree off;
+ poly_widest_int sz;
+
+ gcc_checking_assert (m_pt);
+
+ get_inner_reference_aff (m_pt, &off, &sz);
+ gcc_checking_assert (off.offset.is_constant ());
+
+ widest_int w = off.offset.coeffs[0];
+ wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
+ r.set (sizetype, w2, w2);
+}
+
+// Return possible size range of the referenced object.
+
+void
+prange::pt_size (irange &r) const
+{
+ aff_tree off;
+ poly_widest_int sz;
+
+ gcc_checking_assert (m_pt);
+
+ get_inner_reference_aff (m_pt, &off, &sz);
+ gcc_checking_assert (sz.is_constant ());
+
+ widest_int w = sz.coeffs[0];
+ wide_int w2 = wi::to_wide (wide_int_to_tree (sizetype, w));
+ r.set (sizetype, w2, w2);
+}
// Prange implementation.
void
@@ -561,6 +666,8 @@ prange::set (tree type, const wide_int &min, const wide_int &max,
m_type = type;
m_min = min;
m_max = max;
+ set_pt_unknown ();
+
if (m_min == 0 && m_max == -1)
{
m_kind = VR_VARYING;
@@ -640,6 +747,12 @@ prange::union_ (const vrange &v)
prange new_range (type (), new_lb, new_ub);
new_range.m_bitmask.union_ (m_bitmask);
new_range.m_bitmask.union_ (r.m_bitmask);
+
+ // Keep it simple, either both point to the same thing or both
+ // do not point to the same thing, or we drop the points to info.
+ if (pt_equal_p (r))
+ new_range.set_pt (*this);
+
if (new_range.varying_compatible_p ())
{
set_varying (type ());
@@ -690,6 +803,21 @@ prange::intersect (const vrange &v)
set_undefined ();
else if (!m_bitmask.intersect (r.m_bitmask))
set_undefined ();
+ // If only one object points to something, that is the intersection.
+ else if (pt_unknown_p () && !r.pt_unknown_p ())
+ set_pt (r);
+ else if (!pt_unknown_p () && !r.pt_unknown_p ())
+ {
+ // If both point to something, we want to be careful. Without aliasing
+ // 2 different values can point to the same thing, so UNDEFINED is
+ // not appropriate, but we want to keep the rule that intersection
+ // never becomes larger.
+ // If the other object points to something specific, and this one does
+ // not, use the specific one. Otherwise leave the range as is.
+ if (pt_invariant_away () && r.pt_invariant ())
+ set_pt (r);
+ }
+
if (varying_compatible_p ())
{
set_varying (type ());
@@ -711,6 +839,7 @@ prange::operator= (const prange &src)
m_min = src.m_min;
m_max = src.m_max;
m_bitmask = src.m_bitmask;
+ set_pt (src);
if (flag_checking)
verify_range ();
return *this;
@@ -727,17 +856,27 @@ prange::operator== (const prange &src) const
if (varying_p ())
return types_compatible_p (type (), src.type ());
+ if (!pt_equal_p (src))
+ return false;
+
return (m_min == src.m_min && m_max == src.m_max
&& m_bitmask == src.m_bitmask);
}
return false;
}
+
void
prange::invert ()
{
gcc_checking_assert (!undefined_p () && !varying_p ());
+ // Invert the points_to object. If that worked, this is done.
+ if (pt_invert ())
+ return;
+ else
+ set_pt_unknown ();
+
wide_int new_lb, new_ub;
unsigned prec = TYPE_PRECISION (type ());
wide_int type_min = wi::zero (prec);
@@ -771,7 +910,10 @@ prange::verify_range () const
gcc_checking_assert (m_discriminator == VR_PRANGE);
if (m_kind == VR_UNDEFINED)
- return;
+ {
+ gcc_checking_assert (pt_unknown_p ());
+ return;
+ }
gcc_checking_assert (supports_p (type ()));
diff --git a/gcc/value-range.h b/gcc/value-range.h
index 35421914a71..0ab67303009 100644
--- a/gcc/value-range.h
+++ b/gcc/value-range.h
@@ -440,6 +440,41 @@ public:
virtual void verify_range () const final override;
irange_bitmask get_bitmask () const final override;
void update_bitmask (const irange_bitmask &) final override;
+
+ // prange interface to points to information.
+ // It can point_to or point_away from an object. This represents both
+ // sides of a conditional. ie:
+ // if (p == &foo)
+ // // p points to foo.
+ // else
+ // // p points away from foo.
+ // pt_invariant () and pt_invariant_away () - Return pt if this is invariant.
+ void set_pt (const prange &r);
+ void set_pt (tree ptr, bool points_to_p = true);
+
+ // unknown_p () is true if no object is pointed to.
+ void set_pt_unknown ();
+ bool pt_unknown_p () const;
+
+ // Invariant points-to are is_gimple_min_invariant_p ().
+ // Return expression or NULL_TREE for points-to or away
+ tree pt_invariant () const;
+ tree pt_invariant_away () const;
+
+ // Return true if present and identical for THIS and R.
+ bool pt_invariant_p (const prange &r) const;
+ bool pt_invariant_away_p (const prange &r) const;
+
+ bool pt_invert ();
+ bool pt_inverted_p (const prange &r) const;
+
+ // pt_base () - object/allocation the pointer refers into.
+ tree pt_base () const;
+ // pt_offset () - possible byte offset range from BASE.
+ void pt_offset (irange &) const;
+ // pt_size () - possible size range of the referenced object.
+ void pt_size (irange &) const;
+
protected:
bool varying_compatible_p () const;
@@ -447,6 +482,12 @@ protected:
wide_int m_min;
wide_int m_max;
irange_bitmask m_bitmask;
+
+ // A prange can point to an object, or NOT point to an object.
+ tree m_pt; // object points-to refers to.
+ bool m_points_to_p; // Does it point to it (TRUE), or not (FALSE).
+ // If P has the same points to fields as THIS.
+ bool pt_equal_p (const class prange &p) const;
};
// Unsupported temporaries may be created by ranger before it's known
@@ -1329,6 +1370,7 @@ inline void
prange::set_undefined ()
{
m_kind = VR_UNDEFINED;
+ set_pt_unknown ();
}
inline void
@@ -1339,6 +1381,7 @@ prange::set_varying (tree type)
m_min = wi::zero (TYPE_PRECISION (type));
m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
m_bitmask.set_unknown (TYPE_PRECISION (type));
+ set_pt_unknown ();
if (flag_checking)
verify_range ();
@@ -1352,6 +1395,7 @@ prange::set_nonzero (tree type)
m_min = wi::one (TYPE_PRECISION (type));
m_max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
m_bitmask.set_unknown (TYPE_PRECISION (type));
+ set_pt_unknown ();
if (flag_checking)
verify_range ();
@@ -1365,6 +1409,7 @@ prange::set_zero (tree type)
wide_int zero = wi::zero (TYPE_PRECISION (type));
m_min = m_max = zero;
m_bitmask = irange_bitmask (zero, zero);
+ set_pt_unknown ();
if (flag_checking)
verify_range ();
@@ -1379,7 +1424,7 @@ prange::contains_p (tree cst) const
inline bool
prange::zero_p () const
{
- return m_kind == VR_RANGE && m_min == 0 && m_max == 0;
+ return m_kind == VR_RANGE && m_min == 0 && m_max == 0 && pt_unknown_p ();
}
inline bool
@@ -1412,8 +1457,8 @@ prange::upper_bound () const
inline bool
prange::varying_compatible_p () const
{
- return (!undefined_p ()
- && m_min == 0 && m_max == -1 && get_bitmask ().unknown_p ());
+ return (!undefined_p () && m_min == 0 && m_max == -1
+ && get_bitmask ().unknown_p () && pt_unknown_p ());
}
inline irange_bitmask
@@ -1428,6 +1473,100 @@ prange::fits_p (const vrange &) const
return true;
}
+// Set this range's point-to object to PTR, and POINTS_TO_P is TRUE if it
+// does point to it, and FALSE if it does not point to it.
+
+inline void
+prange::set_pt (const prange &r)
+{
+ m_pt = r.m_pt;
+ m_points_to_p = r.m_points_to_p;
+
+ if (r.undefined_p ())
+ return;
+ // Check whether this is now VARYING or not.
+ if (varying_compatible_p ())
+ set_varying (type ());
+ else
+ m_kind = VR_RANGE;
+}
+
+// prange_pt methods.
+// ------------------------------------------------------------------
+
+inline void
+prange::set_pt_unknown ()
+{
+ m_pt = NULL_TREE;
+ m_points_to_p = false;
+}
+
+inline bool
+prange::pt_unknown_p () const
+{
+ return (m_pt == NULL_TREE);
+}
+
+inline bool
+prange::pt_equal_p (const prange &p) const
+{
+ return (m_points_to_p == p.m_points_to_p && m_pt == p.m_pt);
+}
+
+inline bool
+prange::pt_inverted_p (const prange &r) const
+{
+ return m_pt && vrp_operand_equal_p (m_pt, r.m_pt)
+ && m_points_to_p != r.m_points_to_p;
+}
+
+inline bool
+prange::pt_invert ()
+{
+ if (m_pt)
+ {
+ m_points_to_p = !m_points_to_p;
+ return true;
+ }
+ return false;
+}
+
+inline tree
+prange::pt_invariant () const
+{
+ if (m_pt && m_points_to_p)
+ return m_pt;
+ return NULL_TREE;
+}
+
+inline tree
+prange::pt_invariant_away () const
+{
+ if (m_pt && !m_points_to_p)
+ return m_pt;
+ return NULL_TREE;
+}
+
+inline bool
+prange::pt_invariant_p (const prange &r) const
+{
+ if (m_pt && m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
+ && m_points_to_p == r.m_points_to_p)
+ return m_pt;
+ return NULL_TREE;
+}
+
+inline bool
+prange::pt_invariant_away_p (const prange &r) const
+{
+ if (m_pt && !m_points_to_p && vrp_operand_equal_p (r.m_pt, m_pt)
+ && m_points_to_p == r.m_points_to_p)
+ return m_pt;
+ return NULL_TREE;
+}
+
+
+// -----------------------------------------------------------------------
inline
frange::frange ()
--
2.45.0
