[Bug c/65307] New: Incorrect optimization breaks basic arithmetic

[Bug c/65307] New: Incorrect optimization breaks basic arithmetic

[madars+gccbug at gmail dot com]

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

            Bug ID: 65307
           Summary: Incorrect optimization breaks basic arithmetic
           Product: gcc
           Version: 4.9.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: madars+gccbug at gmail dot com

The following code sample exhibits a bug in a gcc -O2 optimization pass.
Namely, having defined two() and six() with the obvious return values, the
value of two() * 2 + six() * 5 gets an assembly of 1 shl 5 (i.e. 32, instead of
the correct 34).

Code: http://web.mit.edu/madars/Public/gcc-basic-arithmetic-bug.c

gcc 4.9.1 and 4.9.2 with -O2 are both buggy, -O1 makes the bug go away; the bug
does not seem to be present in gcc 4.8 and earlier.

[Bug c/65307] Incorrect optimization breaks basic arithmetic

[madars+gccbug at gmail dot com]

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

--- Comment #1 from madars+gccbug at gmail dot com ---
I should clarify that the same behavior can be observed on Debian, Ubuntu and
Fedora:

gcc (Ubuntu 4.9.1-16ubuntu6) 4.9.1
gcc (Debian 4.9.1-19) 4.9.1
gcc (GCC) 4.9.2 20141101 (Red Hat 4.9.2-1)

Moreover, Alex Chernyakhovsky reports that switching two() * 2 to two() + two()
or two() << 1 produces correct results, so this seems to have to do with the
handling of multiplication.

[Bug c/65307] Incorrect optimization breaks basic arithmetic

[andersk at mit dot edu]

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

Anders Kaseorg <andersk at mit dot edu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andersk at mit dot edu

--- Comment #2 from Anders Kaseorg <andersk at mit dot edu> ---
Confirmed, except that changing two() * 2 to two() + two() or two() << 1 does
not make a difference for me.  This looks more related to inlining:

-O1: works
-O2: fails
-O1 -finline-small-functions: fails
-O2 -fno-inline-small-functions: works

And if I mark two() and six() as inline, then it fails even at -O1.

(GCC 4.9.2-10ubuntu7 on Ubuntu vivid amd64)

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[mpolacek at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-03-04
                 CC|                            |mpolacek at gcc dot gnu.org
          Component|c                           |tree-optimization
   Target Milestone|---                         |4.9.3
            Summary|Incorrect optimization      |[4.9 Regression] Incorrect
                   |breaks basic arithmetic     |optimization breaks basic
                   |                            |arithmetic
     Ever confirmed|0                           |1

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Confirmed for 4.9.  It's been fixed on trunk with r216728.

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[ktietz at gcc dot gnu.org]

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

Kai Tietz <ktietz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |ktietz at gcc dot gnu.org
         Resolution|---                         |DUPLICATE

--- Comment #4 from Kai Tietz <ktietz at gcc dot gnu.org> ---
This is a duplicate of PR/65216.  Underlying issue is in reassoc1-pass.  This
issue is fixed for 5.0

*** This bug has been marked as a duplicate of bug 65216 ***

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[mpolacek at gcc dot gnu.org]

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

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Why do you think it is a duplicate?  PR65216 was a 5 Regression, something that
worked in 4.9; this one is an issue with 4.9 and not 5.  PR65216 was also about
-O3 only, this one fails even with -O2.  PR65216 started after this one got
fixed.

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[manu at gcc dot gnu.org]

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

Manuel López-Ibáñez <manu at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |manu at gcc dot gnu.org
         Resolution|DUPLICATE                   |---

--- Comment #6 from Manuel López-Ibáñez <manu at gcc dot gnu.org> ---
(In reply to Kai Tietz from comment #4)
> This is a duplicate of PR/65216.  Underlying issue is in reassoc1-pass. 
> This issue is fixed for 5.0
> 
> *** This bug has been marked as a duplicate of bug 65216 ***

Is it fixed in 4.9.x? Because that PR 65216 is marked as fixed and does not
mention 4.9.x, only 5.0.
>From gcc-bugs-return-479339-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Wed Mar 04 12:53:26 2015
Return-Path: <gcc-bugs-return-479339-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 119861 invoked by alias); 4 Mar 2015 12:53:26 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 119824 invoked by uid 48); 4 Mar 2015 12:53:22 -0000
From: "redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug c++/65312] Implicitly-declared default constructor must be defined as deleted
Date: Wed, 04 Mar 2015 12:53:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: c++
X-Bugzilla-Version: 4.9.2
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: redi at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-65312-4-WbAC7cxRJx@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-65312-4@http.gcc.gnu.org/bugzilla/>
References: <bug-65312-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-03/txt/msg00483.txt.bz2
Content-length: 445

https://gcc.gnu.org/bugzilla/show_bug.cgi?ide312

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The {} means value-initialization as opposed to default-initialization.

I think value-init requires the compiler to zero out all the members first,
even though they will be given another value anyway.

I haven't checked the generated code, but that would be my guess (and I would
hope the dead stores can be optimized away).

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[ktietz at gcc dot gnu.org]

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

--- Comment #7 from Kai Tietz <ktietz at gcc dot gnu.org> ---
Well, it looked like the same issue by inspection dumps, as folding issue
happens in reassoc-pass.  Of course it might be that forward-prop patch is the
actual issue.

I noticed for -O3 on 4.9.x that valid computation (dse1):

...
g (const unsigned int from_f)
{
  const unsigned int thirty_four;
  unsigned int _3;
  unsigned int _4;
  unsigned int global.0_8;
  unsigned int _9;
  unsigned int _10;

  <bb 2>:
  global.0_8 = global;
  _9 = global.0_8 * 2;
  _3 = _9 * 2;
  _10 = _9 * 3;
  _4 = _10 * 5;
  thirty_four_5 = _3 + _4;
...

Shows after reassoc1 pass:
...
g (const unsigned int from_f)
{
  const unsigned int thirty_four;
  unsigned int _3;
  unsigned int _4;
  unsigned int global.0_8;
  unsigned int _9;
  unsigned int _10;

  <bb 2>:
  global.0_8 = global;
  _9 = global.0_8 * 2;
  _4 = 15;
  _3 = _4 + 2;
  _10 = _9 * _3;
  thirty_four_5 = _10;
...

so it seems to be the forward-propagate patch.

Sorry for the noise

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
           Priority|P3                          |P2
      Known to work|                            |4.8.3, 5.0
      Known to fail|                            |4.9.2

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[maltsevm at gmail dot com]

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

Mikhail Maltsev <maltsevm at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |maltsevm at gmail dot com

--- Comment #8 from Mikhail Maltsev <maltsevm at gmail dot com> ---
A simpler testcase:

static inline unsigned cp(unsigned x)                                           
{                                                                               
    return x;                                                                   
}                                                                               

unsigned f(unsigned x)                                                          
{
    return cp(x * 2) * 2 + cp(cp(x * 2) * 3) * 5;
}

$ cat ./test1.c.085t.phiopt2

;; Function f (f, funcdef_no=1, decl_uid=1393, symbol_order=1)

f (unsigned int x)
{
  unsigned int _2;
  unsigned int _3;
  unsigned int _4;
  unsigned int _5;
  unsigned int _6;

  <bb 2>:
  _2 = x_1(D) * 2;
  _5 = 15;
  _3 = _5 + 2;
  _4 = _2 * _3;
  _6 = _4;
  return _6;

}

$ cat ./test1.c.087t.ccp3

;; Function f (f, funcdef_no=1, decl_uid=1393, symbol_order=1)


Pass statistics:
----------------

Immediate_uses: 

x_1(D) : --> single use.
_2 = x_1(D) * 2;

_2 : --> single use.
_4 = _2 * _3;

_3 : --> single use.
_4 = _2 * _3;

_4 : --> single use.
_6 = _4;

_5 : --> single use.
_3 = _5 + 2;

_6 : --> single use.
return _6;

.MEM_7(D) : --> single use.
# VUSE <.MEM_7(D)>
return _6;

Adding Destination of edge (0 -> 2) to worklist


Simulating block 2

Visiting statement:
# RANGE [0, 4294967295] NONZERO 0x000000000fffffffe
_2 = x_1(D) * 2;
which is likely CONSTANT
Lattice value changed to CONSTANT 0x00000000000000000 (0x000000000fffffffe). 
Adding SSA edges to worklist.

Visiting statement:
# RANGE [0, 4294967295] NONZERO 0x000000000fffffffe
_5 = 15;
which is likely CONSTANT
Lattice value changed to CONSTANT 14.  Adding SSA edges to worklist.

Visiting statement:
_3 = _5 + 2;
which is likely CONSTANT
Lattice value changed to CONSTANT 16.  Adding SSA edges to worklist.

Visiting statement:
_4 = _2 * _3;
which is likely CONSTANT
Lattice value changed to CONSTANT 0x00000000000000000 (0x000000000ffffffe0). 
Adding SSA edges to worklist.

Visiting statement:
# RANGE [0, 4294967295] NONZERO 0x000000000fffffffe
_6 = _4;
Lattice value changed to CONSTANT 0x00000000000000000 (0x000000000ffffffe0). 
Adding SSA edges to worklist.

Visiting statement:
# VUSE <.MEM_7(D)>
return _6;
No interesting values produced.  Marked VARYING.

Substituting values and folding statements

Folding statement: return _6;
Not folded
Folding statement: _6 = _4;
Not folded
Folding statement: _4 = _2 * _3;
Folded into: _4 = _2 * 16;

Removing dead stmt _3 = 16;

Removing dead stmt _5 = 14;

Folding statement: _2 = x_1(D) * 2;
Not folded

Pass statistics:
----------------
Constants propagated: 1
Statements deleted: 2

f (unsigned intD.4 xD.1392)
{
  unsigned intD.4 _2;
  unsigned intD.4 _4;
  unsigned intD.4 _6;

;;   basic block 2, loop depth 0, count 0, freq 10000, maybe hot
;;    prev block 0, next block 1, flags: (NEW, REACHABLE)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
  # RANGE [0, 4294967295] NONZERO 0x000000000fffffffe
  _2 = x_1(D) * 2;
  # RANGE [0, 4294967295] NONZERO 0x000000000ffffffe0
  _4 = _2 * 16;
  # RANGE [0, 4294967295] NONZERO 0x000000000ffffffe0
  _6 = _4;
  # VUSE <.MEM_7(D)>
  return _6;
;;    succ:       EXIT [100.0%] 

}

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |NEW

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
Visiting statement:
# RANGE [0, 4294967295] NONZERO 0x000000000fffffffe
_5 = 15;
which is likely CONSTANT
Lattice value changed to CONSTANT 14.  Adding SSA edges to worklist.

is of course overly optimistic ;)  (but yes, nonzero bits info is bogus)

I'd say we should eventually assert instead of miscompiling things.

That is,

static prop_value_t
evaluate_stmt (gimple stmt)
{
...
  if (flag_tree_bit_ccp
      && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
          || (!is_constant && likelyvalue != UNDEFINED))
      && gimple_get_lhs (stmt)
      && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
    {
          if (!is_constant)
            {
...
            }
          else
            {
              double_int valv = tree_to_double_int (val.value);

here assert

     gcc_assert ((valv & ~val.mask & ~nonzero_bits).is_zero ());

that is, known bits in valv should be consistent with nonzero_bits info.

              if (!(valv & ~nonzero_bits & mask).is_zero ())
                val.value = double_int_to_tree (TREE_TYPE (lhs),
                                                valv & nonzero_bits);
              if (nonzero_bits.is_zero ())
                val.mask = double_int_zero;
              else
                val.mask = val.mask & (nonzero_bits | ~mask);
            }

[Bug tree-optimization/65307] [4.9/5 Regression] Incorrect optimization breaks basic arithmetic

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|5.0                         |
            Summary|[4.9 Regression] Incorrect  |[4.9/5 Regression]
                   |optimization breaks basic   |Incorrect optimization
                   |arithmetic                  |breaks basic arithmetic
      Known to fail|                            |5.0

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
The simpler testcase reproduces on trunk for me.  Trunk assert:

Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c  (revision 221174)
+++ gcc/tree-ssa-ccp.c  (working copy)
@@ -1901,9 +1922,13 @@ evaluate_stmt (gimple stmt)
            }
          else
            {
-             if (wi::bit_and_not (val.value, nonzero_bits) != 0)
-               val.value = wide_int_to_tree (TREE_TYPE (lhs),
-                                             nonzero_bits & val.value);
+             wide_int tem = wi::bit_and_not (val.value, nonzero_bits);
+             if (tem != 0)
+               {
+                 gcc_assert (extend_mask (tem).and_not (val.mask) == 0);
+                 val.value = wide_int_to_tree (TREE_TYPE (lhs),
+                                               nonzero_bits & val.value);
+               }
              if (nonzero_bits == 0)
                val.mask = 0;
              else

[Bug tree-optimization/65307] [4.9/5 Regression] Incorrect optimization breaks basic arithmetic

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed 4.9 assert:

              gcc_assert ((valv & ~val.mask 
                           & ~nonzero_bits & mask).is_zero ());

fixed trunk assert:

@@ -1901,9 +1922,14 @@ evaluate_stmt (gimple stmt)
            }
          else
            {
-             if (wi::bit_and_not (val.value, nonzero_bits) != 0)
-               val.value = wide_int_to_tree (TREE_TYPE (lhs),
-                                             nonzero_bits & val.value);
+             widest_int tem = wi::bit_and_not (wi::to_widest (val.value),
+                                               extend_mask (nonzero_bits));
+             if (tem != 0)
+               {
+                 gcc_assert (tem.and_not (val.mask) == 0);
+                 val.value = wide_int_to_tree (TREE_TYPE (lhs),
+                                               nonzero_bits & val.value);
+               }
              if (nonzero_bits == 0)
                val.mask = 0;
              else


That is, when CCP computes a constant it verifies that nonzero bits info
is consistent with that.

Such assert might not be ready for prime-time as for example in unreachable
code-regions any inconsistency can happen, like in

  if ((i & 1) == 0) { if (i == 3) { .... } }

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[madars+gccbug at gmail dot com]

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

--- Comment #12 from madars+gccbug at gmail dot com ---
By the way, in g++ the bug can be triggered even with -O1 and without marking
any functions inline (implicitly or explicitly):

http://web.mit.edu/madars/Public/gcc-basic-arithmetic-bug-O1.cpp

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug tree-optimization/65307] [4.9 Regression] Incorrect optimization breaks basic arithmetic

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4