On Tue, Oct 1, 2019 at 8:07 PM Jeff Law <l...@redhat.com> wrote:
>
> 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.
VR_VARYING isn't a range, it's a lattice state (likewise for VR_UNDEFINED).
It doesn't make sense to invert a lattice state. How you treat
VR_VARYING/VR_UNDEFINED
depends on context and so depends what 'invert' would do. I suggest to assert
that varying/undefined is never inverted.
Richard.
>
> So there's a handful of nits in there. The only functional concern I
> have is value_range_base::invert.
>
> jeff
