[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  changed:

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED
   Target Milestone|--- |8.0

--- Comment #24 from Richard Biener  ---
Fixed for GCC 8, not suitable for backporting.

[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
Bug 66313 depends on bug 81082, which changed state.

Bug 81082 Summary: [8 Regression] Failure to vectorise after reassociating 
index computation
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81082

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

[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
Bug 66313 depends on bug 81554, which changed state.

Bug 81554 Summary: [8 Regression] 25% performance regression in Himeno benchmark
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81554

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |DUPLICATE

[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
Bug 66313 depends on bug 81203, which changed state.

Bug 81203 Summary: [8 Regression] tail recursion: internal compiler error: 
verify_ssa failed
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81203

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

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

[seurer at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66313
Bug 66313 depends on bug 80948, which changed state.

Bug 80948 Summary: [8 regression] test case gcc.dg/torture/pr68017.c fails with 
ICE starting with r248771
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80948

   What|Removed |Added

 Status|ASSIGNED|RESOLVED
 Resolution|--- |FIXED

[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  changed:

   What|Removed |Added

  Known to work||8.0
  Known to fail||7.1.0

--- Comment #23 from Richard Biener  ---
Fixed on trunk sofar.

[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 #22 from Richard Biener  ---
Author: rguenth
Date: Thu Jun  1 08:05:24 2017
New Revision: 248771

URL: https://gcc.gnu.org/viewcvs?rev=248771=gcc=rev
Log:
2017-06-01  Richard Biener  

PR middle-end/66313
* fold-const.c (fold_plusminus_mult_expr): If the factored
factor may be zero use a wrapping type for the inner operation.
* tree-tailcall.c (independent_of_stmt_p): Pass in to_move bitmap
and handle moved defs.
(process_assignment): Properly guard the unary op case.  Return a
tri-state indicating that moving the stmt before the call may allow
to continue.  Pass through to_move.
(find_tail_calls): Handle moving unrelated defs before
the call.

* c-c++-common/ubsan/pr66313.c: New testcase.
* gcc.dg/tree-ssa/loop-15.c: Adjust.

Added:
trunk/gcc/testsuite/c-c++-common/ubsan/pr66313.c
Modified:
trunk/gcc/ChangeLog
trunk/gcc/fold-const.c
trunk/gcc/testsuite/ChangeLog
trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-15.c
trunk/gcc/tree-tailcall.c

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

[babokin at gmail dot com]

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

--- Comment #20 from Dmitry Babokin  ---
I've created #80932 for c1*(c2*v1-c3*v2)=>c1*c2*v1-c1*c3*v2 issue.

--- Comment #21 from Dmitry Babokin  ---
I've created #80932 for c1*(c2*v1-c3*v2)=>c1*c2*v1-c1*c3*v2 issue.

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

[babokin at gmail dot com]

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

--- Comment #20 from Dmitry Babokin  ---
I've created #80932 for c1*(c2*v1-c3*v2)=>c1*c2*v1-c1*c3*v2 issue.

--- Comment #21 from Dmitry Babokin  ---
I've created #80932 for c1*(c2*v1-c3*v2)=>c1*c2*v1-c1*c3*v2 issue.

[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 #19 from Richard Biener  ---
Created attachment 41441
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=41441=edit
patch

Patch I am testing, I finally managed to convince tailrecursion optimization to
handle the case in gcc.dg/tree-ssa/tailrecursion-6.c after the fix to the
folding.

If testing goes well I'll commit this to trunk.

[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 #18 from Richard Biener  ---
(In reply to Dmitry Babokin from comment #16)
> Here's another test case with a contrary example, where a variable gets
> pulled into the braces and it also causes false positive. Transformation is:
> const1 * (const2 * var1 - const3 * var2) => const1*const2*var1 - const3*var2;
> 
> > cat f.cpp
> #include 
> signed char var_10 = 77;
> long long int var_13 = 1547580415367384384LL;
> 
> long foo() {
>   long a = -6 *
> // 0xbf8a6c24aa342bc0 = -4644781160949077056
>(long(16636733186465668563ULL * var_13 ) -
> // 0xd4cdd0f8c2df13cf = -3112602000603278385
> long(678280911954875019ULL * var_10));
>   return a;
> }
> 
> int main () {
> long a = foo ();
> std::cout << a << std::endl;
> return 0;
> }
> 
> > g++ -fsanitize=undefined -O0 f.cpp; ./a.out
> f.cpp:6:8: runtime error: signed integer overflow: -9024801181724640896 -
> 228867929910118694 cannot be represented in type 'long int'
> 9193074962074792026
> 
> If it's unrelated issue, let me know and I'll file a separate bug for it.

Yes, that's an unrelated issue -- extract_muldiv likely.

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

[babokin at gmail dot com]

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

--- Comment #17 from Dmitry Babokin  ---
Any chances for the fix for this bug?

Looks like this one stands as a last obstacle to claim UBSAN in GCC fully
functional.

I still see quite a few errors, but looks like all of them are attributed to
this problem. Anyway, I have no way to verify this before this bug is fixed.

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

[babokin at gmail dot com]

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

--- Comment #16 from Dmitry Babokin  ---
Here's another test case with a contrary example, where a variable gets pulled
into the braces and it also causes false positive. Transformation is: const1 *
(const2 * var1 - const3 * var2) => const1*const2*var1 - const3*var2;

> cat f.cpp
#include 
signed char var_10 = 77;
long long int var_13 = 1547580415367384384LL;

long foo() {
  long a = -6 *
// 0xbf8a6c24aa342bc0 = -4644781160949077056
   (long(16636733186465668563ULL * var_13 ) -
// 0xd4cdd0f8c2df13cf = -3112602000603278385
long(678280911954875019ULL * var_10));
  return a;
}

int main () {
long a = foo ();
std::cout << a << std::endl;
return 0;
}

> g++ -fsanitize=undefined -O0 f.cpp; ./a.out
f.cpp:6:8: runtime error: signed integer overflow: -9024801181724640896 -
228867929910118694 cannot be represented in type 'long int'
9193074962074792026

If it's unrelated issue, let me know and I'll file a separate bug for it.

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

[babokin at gmail dot com]

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

--- Comment #15 from Dmitry Babokin  ---
The bug is almost 2 years old. I consider it's quite important, as false
positives make UBSAN not usable on any large codebases.

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

[glisse at gcc dot gnu.org]

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

Marc Glisse  changed:

   What|Removed |Added

 CC||babokin at gmail dot com

--- Comment #14 from Marc Glisse  ---
*** Bug 80847 has been marked as a duplicate of this bug. ***

[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  changed:

   What|Removed |Added

 CC||ishiura-compiler at ml dot 
kwansei
   ||.ac.jp

--- Comment #13 from Richard Biener  ---
*** Bug 80541 has been marked as a duplicate of this bug. ***

[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  changed:

   What|Removed |Added

URL||https://gcc.gnu.org/ml/gcc-
   ||patches/2015-10/msg02907.ht
   ||ml

--- Comment #12 from Richard Biener  ---
See patch at https://gcc.gnu.org/ml/gcc-patches/2015-10/msg02907.html, yes I
think
even the latest variant regressed at least the tail-recursion testcase and I
didn't have time to review Josephs last comment and change the exceptions
accordingly.

That said, I believe the transform would be best done in the reassoc pass
but that has to be enhanced to handle types with non-wrapping overflow
characteristics first.

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

[glisse at gcc dot gnu.org]

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

--- Comment #11 from Marc Glisse  ---
Does the patch still exist? Did it fail testing?

[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  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  ---
Testing a patch.

[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 #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

[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 #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

[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

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

[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...