On Fri, 4 Feb 2022, Richard Sandiford wrote:
> Richard Biener <rguent...@suse.de> writes:
> > On Fri, 4 Feb 2022, Richard Sandiford wrote:
> >> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
> >> > niter analysis uses multiple_of_p which currently assumes
> >> > operations like MULT_EXPR do not wrap. We've got to rely on this
> >> > for optimizing size expressions like those in DECL_SIZE and those
> >> > generally use unsigned arithmetic with no indication that they
> >> > are not expected to wrap. To preserve that the following adds
> >> > a parameter to multiple_of_p, defaulted to true, indicating that
> >> > the TOP expression is not expected to wrap for outer computations
> >> > in TYPE. This mostly follows a patch proposed by Bin last year
> >> > with the conversion behavior added.
> >> >
> >> > Applying to all users the new effect is that upon type conversions
> >> > in the TOP expression the behavior will switch to honor
> >> > TYPE_OVERFLOW_UNDEFINED for the converted sub-expressions.
> >> >
> >> > The patch also changes the occurance in niter analysis that we
> >> > know is problematic and we have testcases for to pass false
> >> > to multiple_of_p. The patch also contains a change to the
> >> > PR72817 fix from Bin to avoid regressing gcc.dg/tree-ssa/loop-42.c.
> >> >
> >> > The intent for stage1 is to introduce a size_multiple_of_p and
> >> > internalize the added parameter so all multiple_of_p users will
> >> > honor TYPE_OVERFLOW_UNDEFINED and users dealing with size expressions
> >> > need to be switched to size_multiple_of_p.
> >> >
> >> > Bootstrapped and tested on x86_64-unknown-linux-gnu with all languages
> >> > and {,-m32} testing.
> >> >
> >> > The patch applies ontop of the three earlier posted ones that touch
> >> > multiple_of_p but have not yet been reviewed/pushed.
> >> >
> >> > OK?
> >> >
> >> > Thanks,
> >> > Richard.
> >> >
> >> > 2022-01-26 Richard Biener <rguent...@suse.de>
> >> >
> >> > PR tree-optimization/100499
> >> > * fold-const.h (multiple_of_p): Add nowrap parameter, defaulted
> >> > to true.
> >> > * fold-const.cc (multiple_of_p): Likewise. Honor it for
> >> > MULT_EXPR, PLUS_EXPR and MINUS_EXPR and pass it along,
> >> > switching to false for conversions.
> >> > * tree-ssa-loop-niter.cc (number_of_iterations_ne): Do not
> >> > claim the outermost expression does not wrap when calling
> >> > multiple_of_p. Refactor the check done to check the
> >> > original IV, avoiding a bias that might wrap.
> >> >
> >> > * gcc.dg/torture/pr100499-1.c: New testcase.
> >> > * gcc.dg/torture/pr100499-2.c: Likewise.
> >> > * gcc.dg/torture/pr100499-3.c: Likewise.
> >> >
> >> > Co-authored-by: Bin Cheng <bin.ch...@linux.alibaba.com>
> >> > ---
> >> > gcc/fold-const.cc | 81 +++++++++++++++--------
> >> > gcc/fold-const.h | 2 +-
> >> > gcc/testsuite/gcc.dg/torture/pr100499-1.c | 27 ++++++++
> >> > gcc/testsuite/gcc.dg/torture/pr100499-2.c | 16 +++++
> >> > gcc/testsuite/gcc.dg/torture/pr100499-3.c | 14 ++++
> >> > gcc/tree-ssa-loop-niter.cc | 52 ++++++---------
> >> > 6 files changed, 131 insertions(+), 61 deletions(-)
> >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-1.c
> >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-2.c
> >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-3.c
> >> >
> >> > diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
> >> > index a0a4913c45e..7c204fb6265 100644
> >> > --- a/gcc/fold-const.cc
> >> > +++ b/gcc/fold-const.cc
> >> > @@ -14062,10 +14062,16 @@ fold_binary_initializer_loc (location_t loc,
> >> > tree_code code, tree type,
> >> > SAVE_EXPR (I) * SAVE_EXPR (J)
> >> >
> >> > (where the same SAVE_EXPR (J) is used in the original and the
> >> > - transformed version). */
> >> > + transformed version).
> >> > +
> >> > + NOWRAP specifies whether all outer operations in TYPE should
> >> > + be considered not wrapping. Any type conversion within TOP acts
> >> > + as a barrier and we will fall back to NOWRAP being false.
> >> > + NOWRAP is mostly used to treat expressions in TYPE_SIZE and friends
> >> > + as not wrapping even though they are generally using unsigned
> >> > arithmetic. */
> >> >
> >> > int
> >> > -multiple_of_p (tree type, const_tree top, const_tree bottom)
> >> > +multiple_of_p (tree type, const_tree top, const_tree bottom, bool
> >> > nowrap)
> >> > {
> >> > gimple *stmt;
> >> > tree op1, op2;
> >> > @@ -14083,10 +14089,17 @@ multiple_of_p (tree type, const_tree top,
> >> > const_tree bottom)
> >> > a multiple of BOTTOM then TOP is a multiple of BOTTOM. */
> >> > if (!integer_pow2p (bottom))
> >> > return 0;
> >> > - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom)
> >> > - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom));
> >> > + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom,
> >> > nowrap)
> >> > + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom,
> >> > nowrap));
> >> >
> >> > case MULT_EXPR:
> >> > + /* If the multiplication can wrap we cannot recurse further unless
> >> > + the second operand is a power of two which is where wrapping
> >> > + does not matter. */
> >> > + if (!nowrap
> >> > + && !TYPE_OVERFLOW_UNDEFINED (type)
> >> > + && !integer_pow2p (TREE_OPERAND (top, 1)))
> >> > + return 0;
> >>
> >> I think I'm missing something, but isn't the key thing whether bottom
> >> is a power of 2? E.g. as it stands it looks like we'd still say that a
> >> wrapping x * 2 is a multiple of 3 based purely on x being a multiple of 3,
> >> thanks to…
> >
> > I had to think about this as well but the logic is that (as you noted),
> > we below test ...
> >
> >> > if (TREE_CODE (bottom) == INTEGER_CST)
> >> > {
> >> > op1 = TREE_OPERAND (top, 0);
> >> > @@ -14095,24 +14108,24 @@ multiple_of_p (tree type, const_tree top,
> >> > const_tree bottom)
> >> > std::swap (op1, op2);
> >> > if (TREE_CODE (op2) == INTEGER_CST)
> >> > {
> >> > - if (multiple_of_p (type, op2, bottom))
> >> > + if (multiple_of_p (type, op2, bottom, nowrap))
> >> > return 1;
> >> > /* Handle multiple_of_p ((x * 2 + 2) * 4, 8). */
> >> > - if (multiple_of_p (type, bottom, op2))
> >> > + if (multiple_of_p (type, bottom, op2, nowrap))
> >> > {
> >> > widest_int w = wi::sdiv_trunc (wi::to_widest (bottom),
> >> > wi::to_widest (op2));
> >> > if (wi::fits_to_tree_p (w, TREE_TYPE (bottom)))
> >> > {
> >> > op2 = wide_int_to_tree (TREE_TYPE (bottom), w);
> >> > - return multiple_of_p (type, op1, op2);
> >> > + return multiple_of_p (type, op1, op2, nowrap);
> >> > }
> >> > }
> >> > - return multiple_of_p (type, op1, bottom);
> >> > + return multiple_of_p (type, op1, bottom, nowrap);
> >> > }
> >> > }
> >> > - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom)
> >> > - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom));
> >> > + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom,
> >> > nowrap)
> >> > + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom,
> >> > nowrap));
> >>
> >> …the second arm of the || here.
> >
> > .. oh, we use ||, I thought about this again for the plus case
> > and there we use && which means we'll have bottom a power of two.
> >
> > I think back last year when we discussed this Bin said having
> > bottom a power of two is unnecessarily restrictive.
> >
> >> On the other hand, a wrapping x * 6 is a multiple of 2 even though 6
> >> isn't a power of 2.
> >
> > Yes, for bottom being a power of two the logic would definitely apply.
> >
> > So, changing it to
> >
> > if (!nowrap
> > && !TYPE_OVERFLOW_UNDEFINED (type)
> > && !integer_pow2p (bottom))
> > return 0;
> >
> > would work.
> >
> > I suppose for consistency we should change the condition on the
> > plus/minus case in the same way.
>
> Yeah, agreed.
>
> Like you were discussing in the PR trail, it would be great if ranger
> could help to cut down the false negatives here…
Yes. Note that the patch leaves nowrap = true on all but one caller
so we have something to backport to fix the case we have a testcase for.
For GCC 13 I plan to drop the defaulting as indicated and then we
can also look to either just honor global ranges or do even more
fancy things. I intentionally tried to come up with the most
simplistic and obviously correct patch at this point.
I'm re-testing currently and will post the updated patch.
Richard.
