[Bug middle-end/66313] New: Unsafe factorization of a*b+a*c

[Bug middle-end/66313] New: Unsafe factorization of a*b+a*c

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

            Bug ID: 66313
           Summary: Unsafe factorization of a*b+a*c
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

int f(int a, int b, int c){
  return a * b + a * c;
}
int main(){
  return f(0, __INT_MAX__, __INT_MAX__);
}

$ gcc -fsanitize=undefined e.c
$ ./a.out
e.c:2:16: runtime error: signed integer overflow: 2147483647 + 2147483647
cannot be represented in type 'int'

But I thought I was only computing 0+0?

f(-1, __INT_MAX__, 1) yields:
e.c:2:16: runtime error: signed integer overflow: 2147483647 + 1 cannot be
represented in type 'int'
e.c:2:10: runtime error: signed integer overflow: -2147483648 * -1 cannot be
represented in type 'int'

I am not very excited about restricting this transformation to
TYPE_OVERFLOW_WRAPS, but the alternative is to cast to unsigned (and back after
the operations), which isn't so nice either.

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-05-28
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Well, generating a testcase that generates wrong-code via VRP should be
possible.
Yes, the general "solution" is to compute the whole expression in unsigned
and cast it back...

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Done in this patch.  I don't claim it's beautiful, but oh well.

diff --git gcc/fold-const.c gcc/fold-const.c
index 61eee4a..ce4e989 100644
--- gcc/fold-const.c
+++ gcc/fold-const.c
@@ -7050,11 +7050,18 @@ fold_plusminus_mult_expr (location_t loc, enum
tree_code code, tree type,
     }

   if (same)
-    return fold_build2_loc (loc, MULT_EXPR, type,
-                       fold_build2_loc (loc, code, type,
-                                    fold_convert_loc (loc, type, alt0),
-                                    fold_convert_loc (loc, type, alt1)),
-                       fold_convert_loc (loc, type, same));
+    {
+      /* Perform the expression in unsigned type to avoid introducing
+        undefined behavior, then convert it back to the original type.  */
+      tree utype = unsigned_type_for (type);
+      utype = utype ? utype : type;
+      tree op0 = fold_build2_loc (loc, code, utype,
+                                 fold_convert_loc (loc, utype, alt0),
+                                 fold_convert_loc (loc, utype, alt1));
+      tree op1 = fold_convert_loc (loc, utype, same);
+      return fold_convert_loc (loc, type, fold_build2_loc (loc, MULT_EXPR,
+                                                          utype, op0, op1));
+    }

   return NULL_TREE;
 }
diff --git gcc/testsuite/gcc.dg/fold-plusmult-2.c
gcc/testsuite/gcc.dg/fold-plusmult-2.c
index 82f9898..c74688b 100644
--- gcc/testsuite/gcc.dg/fold-plusmult-2.c
+++ gcc/testsuite/gcc.dg/fold-plusmult-2.c
@@ -16,4 +16,4 @@ int bar (int i)
 /* But eventually this to be canonicalized to (i + 2) * 2.  */

 /* { dg-final { scan-tree-dump "i \\\* 4 \\\+ 2" "original" } } */
-/* { dg-final { scan-tree-dump "\\\(i \\\+ 2\\\) \\\* 2" "original" } } */
+/* { dg-final { scan-tree-dump "i \\\+ 2\\\) \\\* 2" "original" } } */
diff --git gcc/testsuite/gcc.dg/fold-plusmult.c
gcc/testsuite/gcc.dg/fold-plusmult.c
index 1781552..f30fcbf 100644
--- gcc/testsuite/gcc.dg/fold-plusmult.c
+++ gcc/testsuite/gcc.dg/fold-plusmult.c
@@ -11,4 +11,4 @@ int test2 (int a)
   return (a + a)*2;
 }

-/* { dg-final { scan-tree-dump-times "<a> \\\* 4" 2 "original" } } */
+/* { dg-final { scan-tree-dump-times "a.? \\\* 4" 2 "original" } } */

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'm actually testing a patch that moves all of this to match.pd .... (without
fixing this, that said)

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #4 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Ok, then I'll try to fix it up there.

A testcase:
/* PR middle-end/66313 */
/* { dg-do run } */
/* { dg-options "-fsanitize=undefined -fsanitize-undefined-trap-on-error" } */

int __attribute__ ((__noinline__))
f (int a, int b, int c)
{
  return a * b + a * c;
}

int
main ()
{
  int a = f (0, __INT_MAX__, __INT_MAX__);
  asm ("" : : "r" (a));
  a = f (-1, __INT_MAX__, 1);
  asm ("" : : "r" (a));
}

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
I think I'll restrict the computation in unsigned only for
TYPE_OVERFLOW_SANITIZED, otherwise we fail to optimize important stuff :/ (e.g.
tree-ssa/pr23294.c).

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
No, that's not a good approach either.

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
gcc.dg/tree-ssa/pr23294.c should be still optimized, no?  there is not a single
case with a possibly overflowing addition in there.

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #8 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Right now .optimized looks like this:

f6 (int a, int b)
{
  int _2; 
  int _4; 
  int _5; 

  <bb 2>: 
  _2 = a_1(D) * 3;
  _4 = _2 - b_3(D);
  _5 = _4 * 2;
  return _5; 

}

whereas if we compute the expression in unsigned, we generate this:

f6 (int a, int b)
{
  int _2; 
  unsigned int _3; 
  unsigned int b.5_5;
  unsigned int _6; 
  unsigned int _7; 
  int _8; 

  <bb 2>: 
  _2 = a_1(D) * -3; 
  _3 = (unsigned int) _2; 
  b.5_5 = (unsigned int) b_4(D);
  _6 = _3 + b.5_5;
  _7 = _6 * 4294967294;
  _8 = (int) _7; 
  return _8; 

}

But I see no other way ;(.

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

--- Comment #9 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
With the conversion to unsigned we're also no longer able to optimize
tree-ssa/tailrecursion-6.c.

[Bug middle-end/66313] Unsafe factorization of a*b+a*c

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
Testing a patch.