[Bug tree-optimization/97567] New: wrong code at -Os and above on x86_64-pc-linux-gnu

[Bug tree-optimization/97567] New: wrong code at -Os and above on x86_64-pc-linux-gnu

[su at cs dot ucdavis.edu]

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

            Bug ID: 97567
           Summary: wrong code at -Os and above on x86_64-pc-linux-gnu
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: su at cs dot ucdavis.edu
  Target Milestone: ---

[550] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/11.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--prefix=/local/suz-local/software/local/gcc-trunk --enable-languages=c,c++
--disable-werror --enable-multilib --with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 11.0.0 20201025 (experimental) [master revision
1aeb7d7d67d:7a48d67add1:d7ddd287ca76e87f431f43687de6d8cc48e52543] (GCC)
[551] %
[551] % gcctk -O1 small.c; ./a.out
[552] %
[552] % gcctk -Os small.c
[553] % ./a.out
Illegal instruction
[554] %
[554] % cat small.c
int a, b, c, d;
void k() {
  unsigned f = 1;
  long g = 4073709551615;
  for (; a; a++)
    for (;;) {
      d = 0;
    L1:
      break;
    }
  if (f)
    for (; a; a++)
      ;
  g || f;
  int i = 0 - f || g;
  long j = g - f;
  if (j || f) {
    if (g < 4073709551615)
      for (;;)
        ;
    int e = ~f, h = b / ~e;
    if (c)
      goto L2;
    g = f = h;
  }
  g || d;
L2:
  if (c)
    goto L1;
}
int main() { k(); return 0; }

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-10-25
   Target Milestone|---                         |11.0
           Priority|P3                          |P1
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org
            Summary|wrong code at -Os and above |[11 Regression] wrong code
                   |on x86_64-pc-linux-gnu      |at -Os and above on
                   |                            |x86_64-pc-linux-gnu

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r11-3685-gfcae5121154d1c3382b056bcc2c563cedac28e74

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 49441
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49441&action=edit
combine OR operands with union, not intersect

Fundamentally, this boils down to a bug in logical-combine.

calculating the range for f_21 on edge 11->17  


  <bb 11> :
  # iftmp.4_28 = PHI <1(9), 0(10), 1(8)>
  _10 = (long int) f_21;
  j_40 = g_25 - _10;
  _11 = _10 != g_25;
  _13 = _8 | _11;
  if (_13 != 0)
    goto <bb 12>; [INV]
  else
    goto <bb 17>; [INV]


this is the FALSE edge, so we want to deal with _13 = [0,0]

Unseen in this block is the definition of _8, which comes from a elsewhere
  _8 = f_21 != 0;

Notice f_21 can be calculated on both sides of the OR.

logical_combine figures out the ranges on each side and combines them.  it
correctly identifies that in order to take the false side, we need to only look
at  the values for f_21 where
 _8  [0,0] = f_21 != 0      in which case f_21 is [0,0]
and on the _11 side we cant really figure anything out, so we get VARYING when
_11 is [0,0]

logical combine then combines these values, and as this is an OR operation, it
can be any value from either op1 or op2... so it can be [0,0] or VARYING
which should be varying.

The code had a carry over from the AND, and was intersecting these values.. and
producing [0,0], which was then triggering new folds in substitute and fold
because it resolved to a constant.   incorrectly. 

As you can see in the patch, the comments were a little conflicting, but the
conclusion was the UNION of 2 values...   but then the code did an
intersection.

currently testing

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:48722d158cbf692c24025e345ecbbbb570f66aa5

commit r11-4393-g48722d158cbf692c24025e345ecbbbb570f66aa5
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Oct 26 14:55:00 2020 -0400

    Combine logical OR ranges properly.

    When combining logical OR operands with a FALSE result, union the false
    ranges for operand1 and operand2... not intersection.

            gcc/
            PR tree-optimization/97567
            * gimple-range-gori.cc (gori_compute::logical_combine): Union the
            ranges of operand1 and operand2, not intersect.
            gcc/testsuite/
            * gcc.dg/pr97567.c: New.

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[hjl.tools at gmail dot com]

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

--- Comment #4 from H.J. Lu <hjl.tools at gmail dot com> ---
(In reply to CVS Commits from comment #3)
> The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:
> 
> https://gcc.gnu.org/g:48722d158cbf692c24025e345ecbbbb570f66aa5
> 
> commit r11-4393-g48722d158cbf692c24025e345ecbbbb570f66aa5
> Author: Andrew MacLeod <amacleod@redhat.com>
> Date:   Mon Oct 26 14:55:00 2020 -0400
> 
>     Combine logical OR ranges properly.
>     
>     When combining logical OR operands with a FALSE result, union the false
>     ranges for operand1 and operand2... not intersection.
>     
>             gcc/
>             PR tree-optimization/97567
>             * gimple-range-gori.cc (gori_compute::logical_combine): Union the
>             ranges of operand1 and operand2, not intersect.
>             gcc/testsuite/
>             * gcc.dg/pr97567.c: New.

This commit compiled gcc.dg/pr97567.c into an finite loop on Linux/x86.

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 49448
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49448&action=edit
Adjust test case for 32 bit

change the testcase type to long long to avoid issues on 32 bit targets.

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
fixed

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
The original fix was incorrect.  It papered over a problem by reducing
opportunities it could find. Given

  if (c_2 || c_3) 

If the FALSE edge is taken, this is ! (c_2 || c_3) which is equivalent to !c_2
&& !c_3.. so performing the intersection as combine_logical was originally
doing was correct.

I found this by examining cases  we were missing because this was no longer
being combined properly.  which sent be back to this PR to figure out what the
real reason for the failure was.

The GORI design specification calculates outgoing ranges using dependency
chains, but as soon as the chain goes outside the current block, we are suppose
to revert to using the on-entry range since control flow could dictate further
range changes.

I had noticed that on certain occasions we'd peek into other blocks, and each
time I saw it, it was beneficial and seemed like a harmless recalculation, So I
let it go.

In this particular case, during the on-entry cache propagation we were peeking
into another block to pick up a value used in the logical OR operation.
Unfortunately, the on-entry cache hadn't finished propagating and the
incomplete range was picked up from that other block instead of the current
one, and we ended up calculating a [0,0] range on an outgoing edge that should
have been VARYING.  And bad things happened.

The fix is to patch the logical evaluation code to do the same thing as the
non-logical code, follow the spec, and simply use the range-on-entry value for
the block if the def chain  leads out of the current block

[Bug tree-optimization/97567] [11 Regression] wrong code at -Os and above on x86_64-pc-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Andrew Macleod <amacleod@gcc.gnu.org>:

https://gcc.gnu.org/g:7d26a337bfa1135d95caa3c213e82f2a97f18a01

commit r11-4862-g7d26a337bfa1135d95caa3c213e82f2a97f18a01
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Nov 9 19:38:22 2020 -0500

    Fix logical_combine OR operation. Again.

    The original fix was incorrect and results in loss of opportunities.
    Revert the original fix. When processing logical chains, do not
    follow chains outside of the current basic block.  Use the import
    value instead.

            gcc/
            PR tree-optimization/97567
            * gimple-range-gori.cc: (gori_compute::logical_combine): False
            OR operations should intersect the 2 results.
            (gori_compute::compute_logical_operands_in_chain): If def chains
            are outside the current basic block, don't follow them.
            gcc/testsuite/
            * gcc.dg/pr97567-2.c: New.