[PATCH PR100499]Fix wrong niter info caused by overflow behavior

[PATCH PR100499]Fix wrong niter info caused by overflow behavior

[bin.cheng]

[-- Attachment #1: Type: text/plain, Size: 1227 bytes --]

Hi,
As described in PR100499, loop niters analysis for "!=" now relies on multiple_of_p which
so far is mostly implemented for no-overflow scenarios.  This patch fixes the issue by:
1. add new parameter to multiple_of_p indicating no-wrapping behavior in top expression.
2. pass new argument to help multiple_of_p, for example, the case in stor-layout.c.
3. adjust calls in number_of_iterations_ne by checking multiple_of_p without dependence
    on wrapping/no-wrapping behavior.  It also corrects one issue in PR72817.

Noticed there are some improvements in ranger to help analysis of multiple_of_p.  For
TOP expression like "left op right", we would like to check if this specific op wraps or not.
For example:
1. left (unsigned, multiple of 3) + 0xfffffffd: the result is multiple of 3 if "+" wraps even if
    right operand is not multiple of 3.
2. left (unsigned, multiple of 3) + 6: the result is not multiple of 3 if "+" wraps even if the
    right operand is multiple of 3.
So in the end, we might need ranger to tell if such operator wraps or not, i.e, must_overflow,
must_not_overflow, may_overflow.  Of course, we need to be conservative in the last case.

Bootstrap and test on x86_64.  Any comments?

Thanks,
bin

[-- Attachment #2: pr100499-20210520.txt --]
[-- Type: application/octet-stream, Size: 11656 bytes --]

commit 65e4c9ed1bcfd3259f639052ceabf144b67ac646
Author: Bin Cheng <bin.cheng@linux.alibaba.com>
Date:   Thu May 20 15:26:07 2021 +0800

    Make function multiple_of_p aware of wrap behavior.
    
    The function was designed mostly for use if TOP doesn't wrap, this
    patch relaxed the restriction by introducing new parameter NO_WRAP.
    It also changes two callers accordingly.
    
    gcc:
    
            PR tree-optimization/100499
            * fold-const.c (multiple_of_p): New parameter.  Check may wrap
            behavior.
            * fold-const.h (multiple_of_p): New parameter.
            * stor-layout.c (handle_warn_if_not_align): Pass new argument
            indicating no wrap would happen.
            * tree-ssa-loop-niter.c (number_of_iterations_ne): Adjust
            checking on multiple_of_p by handling properly.
    
    gcc/testsuite:
    
            PR tree-optimization/100499
            * gcc.c-torture/execute/pr100499.c: New test.

diff --git a/gcc/fold-const.c b/gcc/fold-const.c
index 5a41524702b..41ba07014ed 100644
--- a/gcc/fold-const.c
+++ b/gcc/fold-const.c
@@ -13967,10 +13967,15 @@ fold_build_call_array_initializer_loc (location_t loc, tree type, tree fn,
      SAVE_EXPR (I) * SAVE_EXPR (J)
 
    (where the same SAVE_EXPR (J) is used in the original and the
-   transformed version).  */
+   transformed version).
+
+   Before introducing NO_WRAP, this function didn't check if TOP could wrap
+   because of overflow or not, and it was mostly for use in case that TOP
+   doesn't overflow/wrap.  Now it only assumes TOP doesn't overflow/wrap if
+   NO_WRAP is true.  */
 
 int
-multiple_of_p (tree type, const_tree top, const_tree bottom)
+multiple_of_p (tree type, const_tree top, const_tree bottom, bool no_wrap)
 {
   gimple *stmt;
   tree t1, op1, op2;
@@ -13988,10 +13993,15 @@ 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, no_wrap)
+	      || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap));
 
     case MULT_EXPR:
+      if (!no_wrap && TYPE_OVERFLOW_WRAPS (type)
+	  /* Overflow/wrap doesn't matter if the 2nd operand is power of 2. */
+	  && !integer_pow2p (TREE_OPERAND (top, 1)))
+	return false;
+
       if (TREE_CODE (bottom) == INTEGER_CST)
 	{
 	  op1 = TREE_OPERAND (top, 0);
@@ -14000,7 +14010,7 @@ 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, no_wrap))
 		return 1;
 	      /* Handle multiple_of_p ((x * 2 + 2) * 4, 8).  */
 	      if (multiple_of_p (type, bottom, op2))
@@ -14010,33 +14020,28 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
 		  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, no_wrap);
 		    }
 		}
-	      return multiple_of_p (type, op1, bottom);
+	      return multiple_of_p (type, op1, bottom, no_wrap);
 	    }
 	}
-      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, no_wrap)
+	      || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap));
 
     case MINUS_EXPR:
-      /* It is impossible to prove if op0 - op1 is multiple of bottom
+    case PLUS_EXPR:
+      if (!no_wrap && TYPE_OVERFLOW_WRAPS (type)
+	  /* Overflow/wrap doesn't matter if the 2nd operand is power of 2. */
+	  && !integer_pow2p (TREE_OPERAND (top, 1)))
+	return false;
+
+      /* 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.  */
-      op1 = TREE_OPERAND (top, 1);
-      if (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));
+      return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, no_wrap)
+	      && multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap));
 
     case LSHIFT_EXPR:
       if (TREE_CODE (TREE_OPERAND (top, 1)) == INTEGER_CST)
@@ -14050,7 +14055,7 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
 				     const_binop (LSHIFT_EXPR, size_one_node,
 						  op1))) != 0
 	      && !TREE_OVERFLOW (t1))
-	    return multiple_of_p (type, t1, bottom);
+	    return multiple_of_p (type, t1, bottom, no_wrap);
 	}
       return 0;
 
@@ -14064,11 +14069,11 @@ multiple_of_p (tree type, const_tree top, const_tree bottom)
       /* fall through */
 
     case SAVE_EXPR:
-      return multiple_of_p (type, TREE_OPERAND (top, 0), bottom);
+      return multiple_of_p (type, TREE_OPERAND (top, 0), bottom, no_wrap);
 
     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, no_wrap)
+	      && multiple_of_p (type, TREE_OPERAND (top, 2), bottom, no_wrap));
 
     case INTEGER_CST:
       if (TREE_CODE (bottom) != INTEGER_CST
diff --git a/gcc/fold-const.h b/gcc/fold-const.h
index 2a74287c131..1e0937b75fe 100644
--- a/gcc/fold-const.h
+++ b/gcc/fold-const.h
@@ -94,7 +94,7 @@ extern void fold_overflow_warning (const char*, enum warn_strict_overflow_code);
 extern enum tree_code fold_div_compare (enum tree_code, tree, tree,
 					tree *, tree *, bool *);
 extern bool operand_equal_p (const_tree, const_tree, unsigned int flags = 0);
-extern int multiple_of_p (tree, const_tree, const_tree);
+extern int multiple_of_p (tree, const_tree, const_tree, bool = false);
 #define omit_one_operand(T1,T2,T3)\
    omit_one_operand_loc (UNKNOWN_LOCATION, T1, T2, T3)
 extern tree omit_one_operand_loc (location_t, tree, tree, tree);
diff --git a/gcc/stor-layout.c b/gcc/stor-layout.c
index 94b8b21c7a8..50fccc71984 100644
--- a/gcc/stor-layout.c
+++ b/gcc/stor-layout.c
@@ -1184,7 +1184,8 @@ handle_warn_if_not_align (tree field, unsigned int record_align)
 	     record_align, context, warn_if_not_align);
 
   tree off = byte_position (field);
-  if (!multiple_of_p (TREE_TYPE (off), off, size_int (warn_if_not_align)))
+  if (!multiple_of_p (TREE_TYPE (off), off, size_int (warn_if_not_align),
+		      /* bool no_wrap = */true))
     {
       if (TREE_CODE (off) == INTEGER_CST)
 	warning (opt_w, "%q+D offset %E in %qT isn%'t aligned to %u",
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100499.c b/gcc/testsuite/gcc.c-torture/execute/pr100499.c
new file mode 100644
index 00000000000..555c9d3dd92
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr100499.c
@@ -0,0 +1,32 @@
+/* { dg-options "-O1 -fpeel-loops -ftree-loop-vectorize" } */
+
+#include<assert.h>
+typedef unsigned short uint16_t;
+typedef signed int int32_t;
+static uint16_t g_2823 = 0xEC75L;
+static uint16_t g_116 = 0xBC07L;
+
+static uint16_t
+(safe_mul_func_uint16_t_u_u)(uint16_t ui1, uint16_t ui2 )
+{
+
+  return ((unsigned int)ui1) * ((unsigned int)ui2);
+}
+
+int main (int argc, char* argv[])
+{
+    uint16_t l_2815 = 65535UL;
+    uint16_t *l_2821 = &g_116;
+    uint16_t *l_2822 = &g_2823;
+
+    assert (g_2823 == 60533);
+lbl_2826:
+    l_2815 &= 0x9DEF1EAEL;
+    if (+(safe_mul_func_uint16_t_u_u(((*l_2821) = l_2815), (--(*l_2822)))))
+    {
+      goto lbl_2826;
+    }
+    assert (g_2823 == 32768);
+
+    return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 3817ec423e7..325bd978609 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1024,17 +1024,19 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
 	    new_base = base - step > FINAL ; step < 0
 					     && base - step doesn't overflow
 
-       2') |FINAL - new_base| is an exact multiple of step.
-
-     Please refer to PR34114 as an example of loop-ch's impact, also refer
-     to PR72817 as an example why condition 2') is necessary.
+     Please refer to PR34114 as an example of loop-ch's impact.
 
      Note, for NE_EXPR, base equals to FINAL is a special case, in
-     which the loop exits immediately, and the iv does not overflow.  */
+     which the loop exits immediately, and the iv does not overflow.
+
+     Also note, we prove condition 2) by checking base and final seperately
+     along with condition 1) or 1').  */
   if (!niter->control.no_overflow
-      && (integer_onep (s) || multiple_of_p (type, c, s)))
+      && (integer_onep (s)
+	  || (multiple_of_p (type, fold_convert (niter_type, iv->base), s)
+	      && multiple_of_p (type, fold_convert (niter_type, final), s))))
     {
-      tree t, cond, new_c, relaxed_cond = boolean_false_node;
+      tree t, cond, relaxed_cond = boolean_false_node;
 
       if (tree_int_cst_sign_bit (iv->step))
 	{
@@ -1048,12 +1050,8 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
 	      if (integer_nonzerop (t))
 		{
 		  t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
-		  new_c = fold_build2 (MINUS_EXPR, niter_type,
-				       fold_convert (niter_type, t),
-				       fold_convert (niter_type, final));
-		  if (multiple_of_p (type, new_c, s))
-		    relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node,
-						t, final);
+		  relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, t,
+					      final);
 		}
 	    }
 	}
@@ -1069,12 +1067,8 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
 	      if (integer_nonzerop (t))
 		{
 		  t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
-		  new_c = fold_build2 (MINUS_EXPR, niter_type,
-				       fold_convert (niter_type, final),
-				       fold_convert (niter_type, t));
-		  if (multiple_of_p (type, new_c, s))
-		    relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node,
-						t, final);
+		  relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, t,
+					      final);
 		}
 	    }
 	}
@@ -1084,19 +1078,11 @@ number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
 	t = simplify_using_initial_conditions (loop, relaxed_cond);
 
       if (t && integer_onep (t))
-	niter->control.no_overflow = true;
-    }
-
-  /* First the trivial cases -- when the step is 1.  */
-  if (integer_onep (s))
-    {
-      niter->niter = c;
-      return true;
-    }
-  if (niter->control.no_overflow && multiple_of_p (type, c, s))
-    {
-      niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s);
-      return true;
+	{
+	  niter->control.no_overflow = true;
+	  niter->niter = fold_build2 (EXACT_DIV_EXPR, niter_type, c, s);
+	  return true;
+	}
     }
 
   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop

Re: [PATCH PR100499]Fix wrong niter info caused by overflow behavior

[Richard Biener]

On Thu, May 27, 2021 at 5:38 AM bin.cheng via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Hi,
> As described in PR100499, loop niters analysis for "!=" now relies on multiple_of_p which
> so far is mostly implemented for no-overflow scenarios.  This patch fixes the issue by:
> 1. add new parameter to multiple_of_p indicating no-wrapping behavior in top expression.
> 2. pass new argument to help multiple_of_p, for example, the case in stor-layout.c.
> 3. adjust calls in number_of_iterations_ne by checking multiple_of_p without dependence
>     on wrapping/no-wrapping behavior.  It also corrects one issue in PR72817.
>
> Noticed there are some improvements in ranger to help analysis of multiple_of_p.  For
> TOP expression like "left op right", we would like to check if this specific op wraps or not.
> For example:
> 1. left (unsigned, multiple of 3) + 0xfffffffd: the result is multiple of 3 if "+" wraps even if
>     right operand is not multiple of 3.
> 2. left (unsigned, multiple of 3) + 6: the result is not multiple of 3 if "+" wraps even if the
>     right operand is multiple of 3.
> So in the end, we might need ranger to tell if such operator wraps or not, i.e, must_overflow,
> must_not_overflow, may_overflow.  Of course, we need to be conservative in the last case.
>
> Bootstrap and test on x86_64.  Any comments?

The multiple_of_p changes could have ABI impact on the 2nd occurance in
stor-layout.c, so a conservative fix would leave that one with
/*no_wrap = */true
as well.

In fact most of the scattered uses elsewhere should possibly converted to
wi::multiple_of_p.

Now,

+      if (!no_wrap && TYPE_OVERFLOW_WRAPS (type)
+         /* Overflow/wrap doesn't matter if the 2nd operand is power of 2. */
+         && !integer_pow2p (TREE_OPERAND (top, 1)))
+       return false;

are integer_pow2_p the only cases we can handle with ignoring overflow?
Isn't the other case when bottom is integer_pow2_p?
I wonder if it makes sense to wrap the core worker of multiple_of_p, using
tree_ctz for integer_pow2_p (bottom), that also already uses range/nonzero
bits info on SSA names.

That said - please factor out the niter analysis changes, they should be
valid on their own and it will be interesting to be able to bisect their
effect separately.

Thanks,
Richard.

> Thanks,
> bin