On 10/1/19 11:11 AM, Aldy Hernandez wrote:
> Hi folks.
>
> Here is my official submission of the range-ops part of the ranger to
> mainline.
>
> I realize that I could have split this patch up into 2-3 separate ones,
> but I don't want to run into the chicken-and-egg scenario of last time,
> where I had 4 inter-connected patches that were hard to review
> independently.
It might have helped a bit, but it was pretty easy to find the mapping
from bits in wide-int-range.cc into range-op.cc -- the comments were
copied :-)
>
> A few notes that may help in reviewing.
>
> The range-ops proper is in range-op.*.
>
> The range.* files are separate files containing some simple auxiliary
> functions that will have irange and value_range_base counterparts. Our
> development branch will have #define value_range_base irange, and some
> auxiliary glue, but none of that will be in trunk. As promised, trunk
> is all value_range_base.
>
> * The changes to tree-vrp.* are:
>
> 1. New constructors to align the irange and value_range_base APIs. We
> discussed this a few months ago, and these were the agreed upon changes
> to the API.
Right.
>
> 2. Extracting the symbolic handling of PLUS/MINUS and POINTER_PLUS_EXPR
> into separate functions (extract_range_from_plus_minus_expr and
> extract_range_from_pointer_plus_expr).
In retrospect we should have broken down that function in the old vrp
code. I suspect that function started out relatively small and just
kept expanding over time into the horrid mess that became.
THere were a number of places where you ended up pulling code from two
existing locations into a single point in range-ops. But again, it was
just a matter of finding the multiple original source points and mapping
then into their new location in range-ops.cc, using the copied comments
as a guide.
>
> 3. New range_fold_unary_expr and range_fold_binary_expr functions. These
> are the VRP entry point into range-ops. They normalize symbolics and do
> some minor pre-shuffling before calling range-ops to do the actual range
> operation.
Right. I see these as primarily an adapter between existing code and
the new range ops.
>
> (I have some minor shuffling of these two functions that I'd like to
> post as separate clean-ups, but I didn't want to pollute this patchset
> with them: Fedora taking forever to test and all.)
Works for me.
> 5. Removing the wide-int-range.* files. Most of the code is now
> in-lined into range-op.cc with the exception of
> wide_int_range_set_zero_nonzero_bits which has been moved into tree-vrp.c.
Right. Largely follows from #2 above.
>
> I think that's all!
>
> For testing this patchset, I left the old extract_*ary_expr_code in, and
> added comparison code that trapped if there were any differences between
> what VRP was getting and what range-ops calculated. I found no
> regressions in either a full bootstrap/tests (all languages), or with a
> full Fedora build. As a bonus, we found quite a few cases where
> range-ops was getting better results.
So to provide a bit more info here. We ran tests back in the spring
which resulted in various bugfixes/improvements. Aldy asked me to
re-run with their more recent branch. That run exposed one very clear
ranger bug which Aldy fixed prior to submitting this patch as well as
several cases where the results differed. We verified each and every
one of them was a case where Ranger was getting better results.
> (Note: At the last minute, Jeff found one regression in the multi-day
> Fedora build. I will fix this as a follow-up. BTW, it does not cause
> any regressions in a bootstrap or GCC test-run, just a discrepancy on
> one specific corner case between VRP and range-ops.)
Right. WHat happened was there was a package that failed to build due
to the Fortran front-end getting tighter in its handling of argument
checking. Once that (and various other issues related to using a gcc-10
snapshot) was worked around I rebuilt the failing packages. That in
turn exposed another case where ranger and vrp differed in their results
(it's a MULT+overflow case IIRC) ANyway, I'm leaving it to you to
analyze :-)
[ ... ]
>
> The attached patch is based off of trunk from a few weeks ago. If
> approved, I will merge and re-test again with latest trunk. I won't
> however, test all of Fedora :-P.
Agreed, I don't think that's necessary. FWIW, using a month-old branch
for testing was amazingly helpful in other respects. We found ~100
packages that need updating for gcc-10 as well as a few bugs unrelated
to Ranger. I've actually got Sunday's snapshot spinning now and fully
expect to be spinning Fedora builds with snapshots for the next several
months. So I don't expect a Fedora build just to test after ranger
integration, but instead that it'll "just happen" on a subsequent snapshot.
>
> May I be so bold as to suggest that if there are minor suggestions that
> arise from this review, that they be done as follow-ups? I'd like to
> get as much testing as possible in this stage1.
There's a variety of small, obvious things that should be fixed.
Comment typos and the like. There's one question on inversion that may
require some discussion.
See inline comments...
>
> Thanks.
> Aldy
>
>
> range-ops.patch
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 65f9db966d0..9aa46c087b8 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,68 @@
> +2019-09-25 Aldy Hernandez <al...@redhat.com>
> +
> + * Makefile.in (OBJS): Add range.o and range-op.o.
> + Remove wide-int-range.o.
> + (GTFILES): Add range.h.
> + * function-tests.c (test_ranges): New.
> + (function_tests_c_tests): Call test_ranges.
> + * ipa-cp.c (ipa_vr_operation_and_type_effects): Call
> + range_fold_unary_expr instead of extract_range_from_unary_expr.
> + * ipa-prop.c (ipa_compute_jump_functions_for_edge): Same.
> + * range-op.cc: New file.
> + * range-op.h: New file.
> + * range.cc: New file.
> + * range.h: New file.
> + * selftest.h (range_tests): New prototype.
> + * ssa.h: Include range.h.
> + * tree-vrp.c (value_range_base::value_range_base): New
> + constructors.
> + (value_range_base::singleton_p): Do not call
> + ranges_from_anti_range until sure we will need to.
> + (value_range_base::type): Rename gcc_assert to
> + gcc_checking_assert.
> + (vrp_val_is_max): New argument.
> + (vrp_val_is_min): Same.
> + (wide_int_range_set_zero_nonzero_bits): Move from
> + wide-int-range.cc.
> + (extract_range_into_wide_ints): Remove.
> + (extract_range_from_multiplicative_op): Remove.
> + (extract_range_from_pointer_plus_expr): Abstract POINTER_PLUS code
> + from extract_range_from_binary_expr.
> + (extract_range_from_plus_minus_expr): Abstract PLUS/MINUS code
> + from extract_range_from_binary_expr.
> + (extract_range_from_binary_expr): Remove.
> + (normalize_for_range_ops): New.
> + (range_fold_binary_expr): New.
> + (range_fold_unary_expr): New.
> + (value_range_base::num_pairs): New.
> + (value_range_base::lower_bound): New.
> + (value_range_base::upper_bound): New.
> + (value_range_base::upper_bound): New.
> + (value_range_base::contains_p): New.
> + (value_range_base::invert): New.
> + (value_range_base::union_): New.
> + (value_range_base::intersect): New.
> + (range_compatible_p): New.
> + (value_range_base::operator==): New.
> + (determine_value_range_1): Call range_fold_*expr instead of
> + extract_range_from_*expr.
> + * tree-vrp.h (class value_range_base): Add new constructors.
> + Add methods for union_, intersect, operator==, contains_p,
> + num_pairs, lower_bound, upper_bound, invert.
> + (vrp_val_is_min): Add handle_pointers argument.
> + (vrp_val_is_max): Same.
> + (extract_range_from_unary_expr): Remove.
> + (extract_range_from_binary_expr): Remove.
> + (range_fold_unary_expr): New.
> + (range_fold_binary_expr): New.
> + * vr-values.c (vr_values::extract_range_from_binary_expr): Call
> + range_fold_binary_expr instead of extract_range_from_binary_expr.
> + (vr_values::extract_range_basic): Same.
> + (vr_values::extract_range_from_unary_expr): Call
> + range_fold_unary_expr instead of extract_range_from_unary_expr.
> + * wide-int-range.cc: Remove.
> + * wide-int-range.h: Remove.
> +
> 2019-08-27 Richard Biener <rguent...@suse.de>
>
> * config/i386/i386-features.h
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 597dc01328b..d9549710d8e 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
[ ... ]
> @@ -2548,6 +2549,7 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h
> $(srcdir)/coretypes.h \
> $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
> $(srcdir)/gimple.h \
> $(srcdir)/gimple-ssa.h \
> + $(srcdir)/range.h $(srcdir)/range.cc \
> $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c $(srcdir)/tree-ssa-address.c
> \
> $(srcdir)/tree-cfg.c $(srcdir)/tree-ssa-loop-ivopts.c \
> $(srcdir)/tree-dfa.c \
I didn't see any GTY thingies in range.h/range.cc, so I don't think this
is strictly necessary. BUt I'm not going to stress if you leave it in.
> diff --git a/gcc/range-op.cc b/gcc/range-op.cc
> new file mode 100644
> index 00000000000..a21520df355
> --- /dev/null
> +++ b/gcc/range-op.cc
[ ... ]
> +
> +// Return a value_range_base instance that is a boolean FALSE.
> +
> +static inline value_range_base
> +range_true_and_false (tree type)
> +{
> + unsigned prec = TYPE_PRECISION (type);
> + return value_range_base (type, wi::zero (prec), wi::one (prec));
> +}
I think the function comment is wrong. We're creating a range with both
true and false values. Effectively a BRS_FULL range I believe.
> +// Return the summary information about boolean range LHS. Return an
> +// "interesting" range in R. For EMPTY or FULL, return the equivilent
> +// range for TYPE, for BRS_TRUE and BRS false, return the negation of
> +// the bool range.
s/equivilent/equivalent/
> +
> +static bool_range_state
> +get_bool_state (value_range_base &r,
> + const value_range_base &lhs, tree val_type)
> +{
> + // If there is no result, then this is unexectuable.
s/unexectuable/unexecutable/
[ ... ]
> +bool
> +operator_equal::op1_range (value_range_base &r, tree type,
> + const value_range_base &lhs,
> + const value_range_base &op2) const
> +{
> + switch (get_bool_state (r, lhs, type))
> + {
> + case BRS_FALSE:
> + // If the result is false, the only time we know anything is
> + // if OP2 is a constant.
> + if (wi::eq_p (op2.lower_bound(), op2.upper_bound()))
> + r = range_invert (op2);
> + else
> + r.set_varying (type);
> + break;
Looks like you've got spaces vs tabs wrong above. It repeats in other
BRS_FALSE cases. I suspect some global search/replace is the right
thing to do here.
[ ... ]
+
> +value_range_base
> +operator_lt::fold_range (tree type,
> + const value_range_base &op1,
> + const value_range_base &op2) const
> +{
> + value_range_base r;
> + if (empty_range_check (r, op1, op2))
> + return r;
> +
> + signop sign = TYPE_SIGN (op1.type ());
> + gcc_checking_assert (sign == TYPE_SIGN (op2.type ()));
> +
> + if (wi::lt_p (op1.upper_bound (), op2.lower_bound (), sign))
> + r = range_true (type);
> + else
> + if (!wi::lt_p (op1.lower_bound (), op2.upper_bound (), sign))
> + r = range_false (type);
> + else
> + r = range_true_and_false (type);
> + return r;
> +}
So formatting goof here. It should be
if (...)
blah
else if (...)
blah2
else
blah3
This repeats in other operator_XX member functions.
[ ... ]
> +
> +value_range_base
> +operator_lshift::wi_fold (tree type,
> + const wide_int &lh_lb, const wide_int &lh_ub,
> + const wide_int &rh_lb, const wide_int &rh_ub) const
> +{
[ ... ]
> + {
> + // For non-negative numbers, we're shifting out only zeroes,
> + // the value increases monotonically. For negative numbers,
> + // we're shifting out only ones, the value decreases
> + // monotomically.
s/monotomically/monotonically/
> +
> +bool
> +operator_cast::op1_range (value_range_base &r, tree type,
> + const value_range_base &lhs,
> + const value_range_base &op2) const
> +{
[ ... ]
> + // If the LHS precision is greater than the rhs precision, the LHS
> + // range is resticted to the range of the RHS by this
> + // assignment.
s/resticted/restricted/
> diff --git a/gcc/range.cc b/gcc/range.cc
> new file mode 100644
> index 00000000000..5e4d90436f2
> --- /dev/null
> +++ b/gcc/range.cc
[ ... ]
> +
> +value_range_base
> +range_intersect (const value_range_base &r1, const value_range_base &r2)
> +{
> + value_range_base tmp (r1);
> + tmp.intersect (r2);
> + return tmp;
> +}
So low level question here. This code looks particularly well suited
for the NRV optimization. Can you check if NVR (named-value-return) is
triggering here, and if not why. ISTM these are likely used heavily and
NVR would be a win.
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 5ec4d17f23b..269a3cb090e 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
[ ... ]
> @@ -67,7 +67,7 @@ along with GCC; see the file COPYING3. If not see
> +
> +/* Return the inverse of a range. */
> +
> +void
> +value_range_base::invert ()
> +{
> + if (undefined_p ())
> + return;
> + if (varying_p ())
> + set_undefined ();
> + 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 ();
> +}
I don't think this is right for varying_p. ISTM that if something is
VR_VARYING that inverting it is still VR_VARYING. VR_UNDEFINED seems
particularly bad given its optimistic treatment elsewhere.
So there's a handful of nits in there. The only functional concern I
have is value_range_base::invert.
jeff
