[PATCH] tree-optimization/114074 - CHREC multiplication and undefined overflow

[Richard Biener <rguenther@suse.de>]

When folding a multiply CHRECs are handled like {a, +, b} * c
is {a*c, +, b*c} but that isn't generally correct when overflow
invokes undefined behavior.  The following uses unsigned arithmetic
unless either a is zero or a and b have the same sign.

I've used simple early outs for INTEGER_CSTs and otherwise use
a range-query since we lack a tree_expr_nonpositive_p.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

I'm not sure it's worth using ranger, there might be also more
cases where the integer multiply is OK, say when abs (A) > abs (B).
But also {-2, +, 2}, but not for {1, +, -1} for example.

OK?

Thanks,
Richard.

	PR tree-optimization/114074
	* tree-chrec.h (chrec_convert_rhs): Default at_stmt arg to NULL.
	* tree-chrec.cc (chrec_fold_multiply): Canonicalize inputs.
	Handle poly vs. non-poly multiplication correctly with respect
	to undefined behavior on overflow.

	* gcc.dg/torture/pr114074.c: New testcase.
	* gcc.dg/pr68317.c: Adjust expected location of diagnostic.
---
 gcc/testsuite/gcc.dg/pr68317.c          |  4 +-
 gcc/testsuite/gcc.dg/torture/pr114074.c | 27 +++++++++++++
 gcc/tree-chrec.cc                       | 53 ++++++++++++++++++++-----
 gcc/tree-chrec.h                        |  2 +-
 4 files changed, 72 insertions(+), 14 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/torture/pr114074.c

diff --git a/gcc/testsuite/gcc.dg/pr68317.c b/gcc/testsuite/gcc.dg/pr68317.c
index bd053a7522b..06cd2e1da9c 100644
--- a/gcc/testsuite/gcc.dg/pr68317.c
+++ b/gcc/testsuite/gcc.dg/pr68317.c
@@ -12,8 +12,8 @@ foo ()
 {
  int32_t index = 0;
 
- for (index; index <= 10; index--) // expected warning here
+ for (index; index <= 10; index--) /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */
    /* Result of the following multiply will overflow
       when converted to signed int32_t.  */
-   bar ((0xcafe + index) * 0xdead);  /* { dg-warning "iteration \[0-9\]+ invokes undefined behavior" } */
+   bar ((0xcafe + index) * 0xdead);
 }
diff --git a/gcc/testsuite/gcc.dg/torture/pr114074.c b/gcc/testsuite/gcc.dg/torture/pr114074.c
new file mode 100644
index 00000000000..336e97673c3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr114074.c
@@ -0,0 +1,27 @@
+/* { dg-do run } */
+
+int a, b, d;
+
+__attribute__((noipa)) void
+foo (void)
+{
+  ++d;
+}
+
+int
+main ()
+{
+  for (a = 0; a > -3; a -= 2)
+    {
+      int c = a;
+      b = __INT_MAX__ - 3000;
+      a = ~c * b;
+      foo ();
+      if (!a)
+        break;
+      a = c;
+    }
+  if (d != 2)
+    __builtin_abort ();
+  return 0;
+}
diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
index 61456fe1141..1b1023f68af 100644
--- a/gcc/tree-chrec.cc
+++ b/gcc/tree-chrec.cc
@@ -38,6 +38,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "gimple.h"
 #include "tree-ssa-loop.h"
 #include "dumpfile.h"
+#include "value-range.h"
+#include "value-query.h"
 #include "tree-scalar-evolution.h"
 
 /* Extended folder for chrecs.  */
@@ -404,6 +406,10 @@ chrec_fold_multiply (tree type,
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);
 
+  if (TREE_CODE (op0) != POLYNOMIAL_CHREC
+      && TREE_CODE (op1) == POLYNOMIAL_CHREC)
+    std::swap (op0, op1);
+
   switch (TREE_CODE (op0))
     {
     case POLYNOMIAL_CHREC:
@@ -428,10 +434,41 @@ chrec_fold_multiply (tree type,
 	  if (integer_zerop (op1))
 	    return build_int_cst (type, 0);
 
-	  return build_polynomial_chrec
-	    (CHREC_VARIABLE (op0),
-	     chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
-	     chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
+	  /* When overflow is undefined and CHREC_LEFT/RIGHT do not have the
+	     same sign or CHREC_LEFT is zero then folding the multiply into
+	     the addition does not have the same behavior on overflow.  Use
+	     unsigned arithmetic in that case.  */
+	  value_range rl, rr;
+	  if (!ANY_INTEGRAL_TYPE_P (type)
+	      || TYPE_OVERFLOW_WRAPS (type)
+	      || integer_zerop (CHREC_LEFT (op0))
+	      || (TREE_CODE (CHREC_LEFT (op0)) == INTEGER_CST
+		  && TREE_CODE (CHREC_RIGHT (op0)) == INTEGER_CST
+		  && (tree_int_cst_sgn (CHREC_LEFT (op0))
+		      == tree_int_cst_sgn (CHREC_RIGHT (op0))))
+	      || (get_range_query (cfun)->range_of_expr (rl, CHREC_LEFT (op0))
+		  && !rl.undefined_p ()
+		  && (rl.nonpositive_p () || rl.nonnegative_p ())
+		  && get_range_query (cfun)->range_of_expr (rr, CHREC_RIGHT (op0))
+		  && !rr.undefined_p ()
+		  && ((rl.nonpositive_p () && rr.nonpositive_p ())
+		      || (rl.nonnegative_p () && rr.nonnegative_p ()))))
+	    return build_polynomial_chrec
+		     (CHREC_VARIABLE (op0),
+		      chrec_fold_multiply (type, CHREC_LEFT (op0), op1),
+		      chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
+	  else
+	    {
+	      tree utype = unsigned_type_for (type);
+	      op1 = chrec_convert_rhs (utype, op1);
+	      tree tem = build_polynomial_chrec
+		(CHREC_VARIABLE (op0),
+		 chrec_fold_multiply
+		   (utype, chrec_convert_rhs (utype, CHREC_LEFT (op0)), op1),
+		 chrec_fold_multiply
+		   (utype, chrec_convert_rhs (utype, CHREC_RIGHT (op0)), op1));
+	      return chrec_convert_rhs (type, tem);
+	    }
 	}
 
     CASE_CONVERT:
@@ -449,13 +486,7 @@ chrec_fold_multiply (tree type,
       switch (TREE_CODE (op1))
 	{
 	case POLYNOMIAL_CHREC:
-	  gcc_checking_assert
-	    (!chrec_contains_symbols_defined_in_loop (op1,
-						      CHREC_VARIABLE (op1)));
-	  return build_polynomial_chrec
-	    (CHREC_VARIABLE (op1),
-	     chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
-	     chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
+	  gcc_unreachable ();
 
 	CASE_CONVERT:
 	  if (tree_contains_chrecs (op1, NULL))
diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index e3a5ba55885..8003eb53a39 100644
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -63,7 +63,7 @@ extern tree chrec_fold_plus (tree, tree, tree);
 extern tree chrec_fold_minus (tree, tree, tree);
 extern tree chrec_fold_multiply (tree, tree, tree);
 extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL);
-extern tree chrec_convert_rhs (tree, tree, gimple *);
+extern tree chrec_convert_rhs (tree, tree, gimple * = NULL);
 extern tree chrec_convert_aggressive (tree, tree, bool *);
 
 /* Operations.  */
-- 
2.35.3