Re: [PATCH] tree-optimization/100499 - niter analysis and multiple_of_p

[Richard Biener <rguenther@suse.de>]

On Fri, 4 Feb 2022, Richard Sandiford wrote:

> Richard Biener <rguenther@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  <rguenther@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.cheng@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.