tree-optimization/100499 - niter analysis and multiple_of_p

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.

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>

1 files changed, 52 insertions, 28 deletions

diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc
index 12732d3..2578a86 100644
--- a/gcc/fold-const.cc
+++ b/gcc/fold-const.cc
@@ -14073,10 +14073,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;
@@ -14094,10 +14100,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 bottom is a power of two which is where wrapping does not
+	 matter.  */
+      if (!nowrap
+	  && !TYPE_OVERFLOW_UNDEFINED (type)
+	  && !integer_pow2p (bottom))
+	return 0;
       if (TREE_CODE (bottom) == INTEGER_CST)
 	{
 	  op1 = TREE_OPERAND (top, 0);
@@ -14106,24 +14119,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));
 
     case LSHIFT_EXPR:
       /* Handle X << CST as X * (1 << CST) and only process the constant.  */
@@ -14135,29 +14148,38 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
 	      wide_int mul_op
 		= wi::one (TYPE_PRECISION (type)) << wi::to_wide (op1);
 	      return multiple_of_p (type,
-				    wide_int_to_tree (type, mul_op), bottom);
+				    wide_int_to_tree (type, mul_op), bottom,
+				    nowrap);
 	    }
 	}
       return 0;
 
     case MINUS_EXPR:
-      /* It is impossible to prove if op0 - op1 is multiple of bottom
-	 precisely, so be conservative here checking if both op0 and op1
-	 are multiple of bottom.  Note we check the second operand first
-	 since it's usually simpler.  */
-      return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom)
-	      && multiple_of_p (type, TREE_OPERAND (top, 0), bottom));
-
     case PLUS_EXPR:
-      /* The same as MINUS_EXPR, but handle cases like op0 + 0xfffffffd
-	 as op0 - 3 if the expression has unsigned type.  For example,
-	 (X / 3) + 0xfffffffd is multiple of 3, but 0xfffffffd is not.  */
+      /* If the addition or subtraction can wrap we cannot recurse further
+	 unless bottom is a power of two which is where wrapping does not
+	 matter.  */
+      if (!nowrap
+	  && !TYPE_OVERFLOW_UNDEFINED (type)
+	  && !integer_pow2p (bottom))
+	return 0;
+
+      /* Handle cases like op0 + 0xfffffffd as op0 - 3 if the expression has
+	 unsigned type.  For example, (X / 3) + 0xfffffffd is multiple of 3,
+	 but 0xfffffffd is not.  */
       op1 = TREE_OPERAND (top, 1);
-      if (TYPE_UNSIGNED (type)
+      if (TREE_CODE (top) == PLUS_EXPR
+	  && nowrap
+	  && TYPE_UNSIGNED (type)
 	  && TREE_CODE (op1) == INTEGER_CST && tree_int_cst_sign_bit (op1))
 	op1 = fold_build1 (NEGATE_EXPR, type, op1);
-      return (multiple_of_p (type, op1, bottom)
-	      && multiple_of_p (type, TREE_OPERAND (top, 0), bottom));
+
+      /* It is impossible to prove if op0 +- op1 is multiple of bottom
+	 precisely, so be conservative here checking if both op0 and op1
+	 are multiple of bottom.  Note we check the second operand first
+	 since it's usually simpler.  */
+      return (multiple_of_p (type, op1, bottom, nowrap)
+	      && multiple_of_p (type, TREE_OPERAND (top, 0), bottom, nowrap));
 
     CASE_CONVERT:
       /* Can't handle conversions from non-integral or wider integral type.  */
@@ -14165,15 +14187,17 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
 	  || (TYPE_PRECISION (type)
 	      < TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (top, 0)))))
 	return 0;
+      /* NOWRAP only extends to operations in the outermost type so
+	 make sure to strip it off here.  */
       return multiple_of_p (TREE_TYPE (TREE_OPERAND (top, 0)),
-			    TREE_OPERAND (top, 0), bottom);
+			    TREE_OPERAND (top, 0), bottom, false);
 
     case SAVE_EXPR:
-      return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
+      return multiple_of_p (type, TREE_OPERAND (top, 0), bottom, nowrap);
 
     case COND_EXPR:
-      return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom)
-	      && multiple_of_p (type, TREE_OPERAND (top, 2), bottom));
+      return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, nowrap)
+	      && multiple_of_p (type, TREE_OPERAND (top, 2), bottom, nowrap));
 
     case INTEGER_CST:
       if (TREE_CODE (bottom) != INTEGER_CST