[Bug tree-optimization/60930] New: Wrong constant folding

[Bug tree-optimization/60930] New: Wrong constant folding

[ishiura-compiler at ml dot kwansei.ac.jp]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

            Bug ID: 60930
           Summary: Wrong constant folding
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ishiura-compiler at ml dot kwansei.ac.jp

GCC 4.7 - 4.10 for i686 and x86_64 miscompiles the following code.

    $ cat error.c

    #include <stdio.h>
    int x = 1;
    main ()
    {
        unsigned long long t = 0xffffffffffffffffLLU * (0xffffffffLU * x);
        if (t != 0xffffffff00000001LLU) {
            printf ("Error (t == %llu)\n", t);
        }
        return 0;
    }

    $ x86_64-unknown-linux-gnu-gcc-4.10.0 error.c -O1
    $ ./a.out
    Error 1

    $ x86_64-unknown-linux-gnu-gcc-4.10.0 -v
    Using built-in specs.
    COLLECT_GCC=x86_64-unknown-linux-gnu-gcc-4.10.0
   
COLLECT_LTO_WRAPPER=/usr/local/x86_64-tools/gcc-4.10.0/libexec/gcc/x86_64-unknown-linux-gnu/4.10.0/lto-wrapper
    Target: x86_64-unknown-linux-gnu
    Configured with: /home/hassy/gcc-master/configure
    --prefix=/usr/local/x86_64-tools/gcc-4.10.0/
    --with-gmp=/usr/local/gmp-5.1.1/ --with-mpfr=/usr/local/mpfr-3.1.2/
    --with-mpc=/usr/local/mpc-1.0.2/ --disable-multilib
    --disable-nls --enable-languages=c
    Thread model: posix
    gcc version 4.10.0 20140422 (experimental) (GCC)

The status of the other versions are as follows:

    (x86_64)
    GCC-4.7.3 OK
    GCC-4.8.3 (prerelease) Error
    GCC-4.9.1 (prerelease) Error
    GCC-4.10.0 (experimental) Error

    (i686)
    GCC-4.7.3 Error
    GCC-4.8.3 (prerelease) Error
    GCC-4.9.1 (prerelease) Error
    GCC-4.10.0 (experimental) Error

[Bug tree-optimization/60930] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Wrong constant folding      |Wrong folding of -
                   |                            |((unsigned long long) a *
                   |                            |(unsigned long long)
                   |                            |(unsigned int)-1)

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, slsr is causing the problem.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-04-23
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |wschmidt at gcc dot gnu.org
   Target Milestone|---                         |4.8.3
            Summary|Wrong folding of -          |[4.8/4.9/4.10 Regression]
                   |((unsigned long long) a *   |Wrong folding of -
                   |(unsigned long long)        |((unsigned long long) a *
                   |(unsigned int)-1)           |(unsigned long long)
                   |                            |(unsigned int)-1)
     Ever confirmed|0                           |1

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Indeed, started with r188989.

int x = 1;

__attribute__((noinline, noclone)) void
foo (unsigned long long t)
{
  asm volatile ("" : : "r" (&t));
  if (x == 1)
    __builtin_abort ();
}

int
main ()
{
  unsigned long long t = 0xffffffffffffffffULL * (0xffffffffUL * x);
  if (t != 0xffffffff00000001ULL)
    foo (t);;
  return 0;
}

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Target|                            |x86_64-*-*, i?86-*-*
           Priority|P3                          |P2

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

Bill Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #3 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Also reproduces on powerpc64le-linux-gnu for 4.10.  I'll investigate.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #4 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Created attachment 32664
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32664&action=edit
Proposed patch

Here's a patch (for trunk) that solves the problem for powerpc64le without
regression.  If you have time, can you please try this on the ports for which
the bug was reported?  Meantime I'll work on the backport versions.

Thanks,
Bill

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Bill Schmidt from comment #4)
> Created attachment 32664 [details]
> Proposed patch
> 
> Here's a patch (for trunk) that solves the problem for powerpc64le without
> regression.  If you have time, can you please try this on the ports for
> which the bug was reported?  Meantime I'll work on the backport versions.
> 
> Thanks,
> Bill

That is a weird check for overflow.  If you are looking for multiplication
overflow and want to perform the computation in signed double_int, then
supposedly one would use
bool overflow_p = false;
temp = tree_to_double_int (base_cand->stride).mul_with_sign (tree_to_double_int
(stride_in), false, &overflow_p);
if (!overflow_p)
Not sure about the false, if e.g. both the base_cand->stride and stride_in are
TYPE_UNSIGNED, shouldn't it be true then?  What if one of them is signed and
one unsigned?
Alternatively, you could just fold_binary (MULT_EXPR, type, base_cand->stride,
stride_in); and check for TREE_OVERFLOW_P on the result.

Richard, your thoughts on this?

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #6 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Perhaps I confused matters a little with the commentary.  What's happening with
the bug is that the multiplication succeeds in the double-int but the product
is then truncated to the size of the stride type on the double_int_to_tree
call.  If the sign changes during the truncation, then we have an effective
overflow when the target is that particular type.  This seemed like a simple
way to detect the problem with minimal changes to the code.  But I'm happy to
use whatever methods are preferred.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think the problem is that we look at expressions in 'long unsigned int'
but a base_cand of type 'int'.  That is, the bug in the computation is
that ctype is unsigned long but stride is int.  If that is really desired
and required then you want to do sth more like

Index: gcc/gimple-ssa-strength-reduction.c
===================================================================
--- gcc/gimple-ssa-strength-reduction.c (revision 209677)
+++ gcc/gimple-ssa-strength-reduction.c (working copy)
@@ -1114,15 +1114,20 @@ create_mul_imm_cand (gimple gs, tree bas
             X = Y * c
             ============================
             X = (B + i') * (S * c)  */
-         base = base_cand->base_expr;
-         index = base_cand->index;
          temp = tree_to_double_int (base_cand->stride)
                 * tree_to_double_int (stride_in);
-         stride = double_int_to_tree (TREE_TYPE (stride_in), temp);
-         ctype = base_cand->cand_type;
-         if (has_single_use (base_in))
-           savings = (base_cand->dead_savings 
-                      + stmt_cost (base_cand->cand_stmt, speed));
+         temp = temp.ext (TYPE_PRECISION (base_cand->cand_type),
+                          TYPE_UNSIGNED (base_cand->cand_type));
+         if (double_int_fits_to_tree_p (TREE_TYPE (stride_in), temp))
+           {
+             base = base_cand->base_expr;
+             index = base_cand->index;
+             stride = double_int_to_tree (TREE_TYPE (stride_in), temp);
+             ctype = base_cand->cand_type;
+             if (has_single_use (base_in))
+               savings = (base_cand->dead_savings 
+                          + stmt_cost (base_cand->cand_stmt, speed));
+           }
        }
       else if (base_cand->kind == CAND_ADD && integer_onep
(base_cand->stride))
        {

as I suppose a truncation to ctype will happen anyway (and is ok).

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #8 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Hi Richi,

What you suggest won't quite work, as the ctype just represents the type of the
base expression and not necessarily the type of the result.  (We're doing a
pure-forward analysis and don't know how the result will be used downstream.) 
It's common for the code we deal with here to multiply an unsigned value by a
negative number and then cast it to a sizetype as part of array addressing. 
The temp.ext () call would preclude optimizing that case.  So I think the
correct way to do this is as you specified but without that call to change the
value of temp.  I'll test that today.

An example test case where ctype is unsigned but negative address calculations 
are effectively used is gcc.dg/tree-ssa/slsr-8.c.  Prior to SLSR the code looks
like below:

;; Function f (f, funcdef_no=0, decl_uid=2213, symbol_order=0)

;; 1 loops found
;;
;; Loop 0
;;  header 0, latch 1
;;  depth 0, outer -1
;;  nodes: 0 1 2 3 4
;; 2 succs { 4 3 }
;; 3 succs { 4 }
;; 4 succs { 1 }
f (int s, int * c)
{
  int * x3;
  int * x2;
  int * x1;
  int a3;
  int a2;
  int a1;
  int * iftmp.0_1;
  long unsigned int _4;
  long unsigned int _5;
  sizetype _6;
  long unsigned int _10;
  long unsigned int _11;
  sizetype _12;
  long unsigned int _15;
  long unsigned int _16;
  sizetype _17;

  <bb 2>:
  a1_3 = s_2(D) * 2;
  _4 = (long unsigned int) a1_3;
  _5 = _4 * 4;
  _6 = -_5;
  x1_8 = c_7(D) + _6;
  a2_9 = s_2(D) * 4;
  _10 = (long unsigned int) a2_9;
  _11 = _10 * 4;
  _12 = -_11;
  x2_13 = c_7(D) + _12;
  if (x1_8 != 0B)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  a3_14 = s_2(D) * 6;
  _15 = (long unsigned int) a3_14;
  _16 = _15 * 4;
  _17 = -_16;
  x3_18 = c_7(D) + _17;

  <bb 4>:
  # iftmp.0_1 = PHI <x2_13(2), x3_18(3)>
  return iftmp.0_1;

}

With SLSR, we can get rid of some of the multiply/negate sequences and produce:

;; Function f (f, funcdef_no=0, decl_uid=2213, symbol_order=0)

Removing basic block 5
f (int s, int * c)
{
  int * x3;
  int * x2;
  int * x1;
  int a1;
  int * iftmp.0_1;
  long unsigned int _4;
  long unsigned int _5;
  sizetype _6;

  <bb 2>:
  a1_3 = s_2(D) * 2;
  _4 = (long unsigned int) a1_3;
  _5 = _4 * 4;
  _6 = -_5;
  x1_8 = c_7(D) + _6;
  x2_13 = x1_8 + _6;
  if (x1_8 != 0B)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  x3_18 = x2_13 + _6;

  <bb 4>:
  # iftmp.0_1 = PHI <x2_13(2), x3_18(3)>
  return iftmp.0_1;

}

Restricting the folded multiplicand to an unsigned type causes us to miss this
opportunity.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

Bill Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #32664|0                           |1
        is obsolete|                            |

--- Comment #9 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Created attachment 32677
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32677&action=edit
Revised proposed patch

Current proposed patch.  Again it would be nice to have verification on the
reported platforms as well, but this should work on 4.8, 4.9, 4.10.  Need to
check 4.7 to see if the same patch works there.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #10 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Er, guess there was no SLSR in 4.7, so if this test is failing on 4.7 that must
be something else.  I will assume that's a typo, though.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #12 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
I will let the trunk fix burn in for a week before patching 4.8 and 4.9.

Note that this patch will NOT fix whatever is wrong with this test case on
4.7.3 for i686.  I suggest that you open a separate bug report for that case if
you are concerned about 4.7.  The SLSR phase didn't exist in 4.7 so something
else is wrong there.

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #13 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Author: wschmidt
Date: Fri May  2 21:49:26 2014
New Revision: 210020

URL: http://gcc.gnu.org/viewcvs?rev=210020&root=gcc&view=rev
Log:
[gcc]

2014-05-02  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/60930
    * gimple-ssa-strength-reduction.c (create_mul_imm_cand):  Reject
    creating a multiply candidate by folding two constant
    multiplicands when the result overflows.

[gcc/testsuite]

2014-05-02  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/60930
    * gcc.dg/torture/pr60930.c:  New test.



Added:
    branches/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr60930.c
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/gimple-ssa-strength-reduction.c
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

--- Comment #14 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Author: wschmidt
Date: Fri May  2 21:51:09 2014
New Revision: 210021

URL: http://gcc.gnu.org/viewcvs?rev=210021&root=gcc&view=rev
Log:
[gcc]

2014-05-02  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/60930
    * gimple-ssa-strength-reduction.c (create_mul_imm_cand):  Reject
    creating a multiply candidate by folding two constant
    multiplicands when the result overflows.

[gcc/testsuite]

2014-05-02  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/60930
    * gcc.dg/torture/pr60930.c:  New test.



Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr60930.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/gimple-ssa-strength-reduction.c
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog

[Bug tree-optimization/60930] [4.8/4.9/4.10 Regression] Wrong folding of - ((unsigned long long) a * (unsigned long long) (unsigned int)-1)

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60930

Bill Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #15 from Bill Schmidt <wschmidt at gcc dot gnu.org> ---
Work is complete.