[Bug middle-end/103120] New: [12 Regression] test miscompiled with -O2 on darwin since r12-4790

[Bug middle-end/103120] New: [12 Regression] test miscompiled with -O2 on darwin since r12-4790

[ibuclaw at gdcproject dot org]

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

            Bug ID: 103120
           Summary: [12 Regression] test miscompiled with -O2 on darwin
                    since r12-4790
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ibuclaw at gdcproject dot org
  Target Milestone: ---

Starting from r12-4790, one of the D library tests started failing on darwin.

Distilled it down to following C code.  Passes when compiled with -O1 and -O3,
but fails with -O2.
---
#define radix 10
__INT32_TYPE__ numDigits(__UINT64_TYPE__ value)
{
     __INT32_TYPE__ n = 1;
     while (value > __UINT32_MAX__)
     {
        n += 4;
        value /= radix * radix * radix * radix;
     }
     __UINT32_TYPE__ v = (__UINT32_TYPE__)value;
     while (1)
     {
         if (v < radix)
             return n;
         if (v < radix * radix)
             return n + 1;
         if (v < radix * radix * radix)
             return n + 2;
         if (v < radix * radix * radix * radix)
             return n + 3;
         n += 4;
         v /= radix * radix * radix * radix;
     }
}

int main()
{
    if (numDigits(__UINT64_MAX__) != 20)
        __builtin_abort();
}

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 on darwin since r12-4790

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.0
          Component|middle-end                  |tree-optimization
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-11-07
     Ever confirmed|0                           |1
             Target|                            |x86_64-lin ux-gnu

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, even on x86_64-linux-gnu.

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 on darwin since r12-4790

[ibuclaw at gdcproject dot org]

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

Iain Buclaw <ibuclaw at gdcproject dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|x86_64-lin ux-gnu           |x86_64-linux-gnu,
                   |                            |x86_64-apple-darwin20

--- Comment #2 from Iain Buclaw <ibuclaw at gdcproject dot org> ---
(In reply to Andrew Pinski from comment #1)
> Confirmed, even on x86_64-linux-gnu.
Thanks, I didn't see a failure for D on linux, so assumed that was fine.

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|x86_64-linux-gnu,           |
                   |x86_64-apple-darwin20       |

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Iain Buclaw from comment #2)
> (In reply to Andrew Pinski from comment #1)
> > Confirmed, even on x86_64-linux-gnu.
> Thanks, I didn't see a failure for D on linux, so assumed that was fine.

It fails even on aarch64-linux-gnu.  Let me double check if it passes after
r12-4971

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |blocker

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> It fails even on aarch64-linux-gnu.  Let me double check if it passes after
> r12-4971

Yes it still fails as of r12-4973 on x86_64-linux-gnu.

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|blocker                     |normal
           Priority|P3                          |P1

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[aldyh at gcc dot gnu.org]

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

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
This is an ordering issue in the path solver, and it's not even relation
related!  How interesting.

./xgcc -B./ a.c -O2 -fdisable-tree-ethread -fdisable-tree-thread1
-fdisable-tree-thread2 -fdisable-tree-threadfull1 -fno-tree-dominator-opts
-fdump-tree-threadfull2-details-threading -fdbg-cnt=back_threadfull2:1-1

The path is 19->3->??:

  <bb 3> [local count: 916928331]:
  # value_20 = PHI <value_17(19), value_7(D)(17)>
  # n_27 = PHI <n_16(19), 1(17)>
  n_16 = n_27 + 4;
  value_17 = value_20 / 10000;
  if (value_20 > 42949672959999)
    goto <bb 19>; [89.00%]
  else
    goto <bb 4>; [11.00%]

The path solver calculates:

*********** path_range_query ******************

path_range_query: compute_ranges for path: BB 19, BB 3
 Registering killing_def (path_oracle) value_17
range_defined_in_block (BB3) for value_20 is long unsigned int [4294967296,
1844674407370955]
range_defined_in_block (BB3) for value_17 is long unsigned int [429496,
184467440737]
range_defined_in_block (BB3) for value_20 is long unsigned int [429496,
184467440737]

So, it's calculating the range for value_20 as it tries to resolve value_17. 
The first 2 ranges are correct.

Then it tries to calculate the range for value_20 (again) because it's an
import.  However, when looking at the PHI, it ignores that there's already a
cache entry, so it tries the following...

  # value_20 = PHI <value_17(19), value_7(D)(17)>

...using the new value of value_17 which is incorrect.

It blows my mind that we haven't run into this before, especially with such a
simple test case.

I need to think about this, but my gut feeling says the following should do it:

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 9175651e896..7b5b2e5e55d 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -356,7 +356,8 @@ path_range_query::compute_ranges_in_block (basic_block bb)
     {
       tree name = ssa_name (i);

-      if (range_defined_in_block (r, name, bb))
+      if (!bitmap_bit_p (m_has_cache_entry, SSA_NAME_VERSION (name))
+         && range_defined_in_block (r, name, bb))
        set_cache (r, name);
     }

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:18546941ae4c56cd9240d2dc2ca2806e01eb6fb7

commit r12-5000-g18546941ae4c56cd9240d2dc2ca2806e01eb6fb7
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Mon Nov 8 12:13:33 2021 +0100

    path solver: Avoid recalculating ranges already in the cache.

    The problem here is an ordering issue with a path that starts
    with 19->3:

     <bb 3> [local count: 916928331]:
      # value_20 = PHI <value_17(19), value_7(D)(17)>
      # n_27 = PHI <n_16(19), 1(17)>
      n_16 = n_27 + 4;
      value_17 = value_20 / 10000;
      if (value_20 > 42949672959999)
        goto <bb 19>; [89.00%]
      else
        goto <bb 4>; [11.00%]

    The problem here is that both value_17 and value_20 are in the set of
    imports we must pre-calculate.  The value_17 name occurs first in the
    bitmap, so we try to resolve it first, which causes us to recursively
    solve the value_20 range.  We do so correctly and put them both in the
    cache.  However, when we try to solve value_20 from the bitmap, we
    ignore that it already has a cached entry and try to resolve the PHI
    with the wrong value of value_17:

      # value_20 = PHI <value_17(19), value_7(D)(17)>

    The right thing to do is to avoid recalculating definitions already
    solved.

    Regstrapped and checked for # threads before and after on x86-64 Linux.

    gcc/ChangeLog:

            PR tree-optimization/103120
            * gimple-range-path.cc (path_range_query::range_defined_in_block):
            Bail if there's a cache entry.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr103120.c: New test.

[Bug tree-optimization/103120] [12 Regression] test miscompiled with -O2 since r12-4790

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
fixed