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…
Thanks,
Richard
