[Bug rtl-optimization/115565] New: [4.0/4.1/4.2/4.3/4.4/4.5/4.6/4.7/4.8/4.9/5/6/7/8/9/10/11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[Bug rtl-optimization/115565] New: [4.0/4.1/4.2/4.3/4.4/4.5/4.6/4.7/4.8/4.9/5/6/7/8/9/10/11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[macro at orcam dot me.uk]

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

            Bug ID: 115565
           Summary: [4.0/4.1/4.2/4.3/4.4/4.5/4.6/4.7/4.8/4.9/5/6/7/8/9/10/
                    11/12/13/14/15 Regression] CSE: Comparison incorrectly
                    evaluated as constant causing optimization to produce
                    wrong code
           Product: gcc
           Version: 15.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: macro at orcam dot me.uk
  Target Milestone: ---

Created attachment 58473
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58473&action=edit
Proposed fix

I've had an emergency case where I chose to revive my old Alpha/Linux
userland based on glibc 2.4 + LinuxThreads built with GCC 4.1.2 release,
which I built decades ago, but never came to verifing.  Now that I came
back to it I found out that numerous key programs hang, making the system
mostly unusable.  Oddly enough bash and GDB worked, which let me debug
this issue over a serial console line in a single-user environment.

Eventually I figured out that a key piece of code has been optimised away
from `pthread_rwlock_unlock' in libpthread.so, causing a write lock never
to be released and consequently the caller to lock up on the next attempt
to reacquire the lock.

Then I have narrowed the problem down to CSE and bisected to commit
08a692679fb8 ("Undefined cse.c behaviour causes 3.4 regression on HPUX"),
<https://gcc.gnu.org/ml/gcc-patches/2004-10/msg02027.html>, staring at
which however and wading through cse.c yielded nothing.

So I went ahead and debugged GCC compiling the problematic piece of code
and finally arrived at this condition:

REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty

incorrectly evaluating to true for `ent' being a memory reference.
Needless to say the left-hand side referred to register 0, so both `qty'
values were -1, for this source code:

rwlock->__rw_writer != thread_self ()

where `thread_self' expanded to a PALcode call to retrieve the thread
pointer and return it in $0.  Evidently an update to the handling of
`comparison_qty' was missed with said commit and -1 now means either
a non-register reference or a register 0 reference that has not been
assigned a quantity.  I have attached an obvious fix for this issue and
will follow with a proper patch submission right away.

Interestingly enough the bug has been covered for my reproducer later on
and as from commit 932ad4d9b550 ("Make CSE path following use the CFG"),
<https://gcc.gnu.org/ml/gcc-patches/2006-12/msg00431.html>, it does not
trigger anymore with the original reproducer (and LinuxThreads have
since been decommissioned anyway, so nobody else might have stumbled
across this issue), however in principle the bug is still there waiting
to bite and the fix proposed cleanly applies unchanged from the version
I originally made for GCC 4.1.2 except for the .c to .cc file rename.

As there can only be a single attachment added per submission, I'll be
following up with tarballs including the reproducer, Alpha assembly code
produced and associated RTL dumps for the last good and first bad commit
respectively, so that this has been recorded for posterity, even though
not directly usable with GCC 15.  See the .cmd files within for the
compilation options used, although just `-O1' should do.

[Bug rtl-optimization/115565] [4.0/4.1/4.2/4.3/4.4/4.5/4.6/4.7/4.8/4.9/5/6/7/8/9/10/11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[macro at orcam dot me.uk]

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

--- Comment #1 from Maciej W. Rozycki <macro at orcam dot me.uk> ---
Created attachment 58474
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58474&action=edit
Reduced reproducer and correct code + RTL dumps produced with commit
4cd26879f758

[Bug rtl-optimization/115565] [4.0/4.1/4.2/4.3/4.4/4.5/4.6/4.7/4.8/4.9/5/6/7/8/9/10/11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[macro at orcam dot me.uk]

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

--- Comment #2 from Maciej W. Rozycki <macro at orcam dot me.uk> ---
Created attachment 58475
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58475&action=edit
Reduced reproducer and incorrect code + RTL dumps produced with commit
08a692679fb8

[Bug rtl-optimization/115565] [11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[roger at nextmovesoftware dot com]

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

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-06-20
             Status|UNCONFIRMED                 |NEW
                 CC|                            |roger at nextmovesoftware dot com
     Ever confirmed|0                           |1

--- Comment #3 from Roger Sayle <roger at nextmovesoftware dot com> ---
Doh!  I hadn't noticed (twenty years ago) that -1 was used to represent an
invalid quantity number in CSE's comparison_qty field.  There was no mention of
this in my post or patch. Using INT_MIN looks like a reasonable (good) fix. 
Presumably backends that constrain values in hard register zero (before reload)
are rare, which is why no-one has noticed/been affected by this.

Thanks for the fix, and my apologies for the inconvenience.

[Bug rtl-optimization/115565] [11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.5
           Priority|P3                          |P2

[Bug rtl-optimization/115565] [11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Maciej W. Rozycki <macro@gcc.gnu.org>:

https://gcc.gnu.org/g:69bc5fb97dc3fada81869e00fa65d39f7def6acf

commit r15-1724-g69bc5fb97dc3fada81869e00fa65d39f7def6acf
Author: Maciej W. Rozycki <macro@orcam.me.uk>
Date:   Sat Jun 29 23:26:55 2024 +0100

    [PR115565] cse: Don't use a valid regno for non-register in comparison_qty

    Use INT_MIN rather than -1 in `comparison_qty' where a comparison is not
    with a register, because the value of -1 is actually a valid reference
    to register 0 in the case where it has not been assigned a quantity.

    Using -1 makes `REG_QTY (REGNO (folded_arg1)) == ent->comparison_qty'
    comparison in `fold_rtx' to incorrectly trigger in rare circumstances
    and return true for a memory reference, making CSE consider a comparison
    operation to evaluate to a constant expression and consequently make the
    resulting code incorrectly execute or fail to execute conditional
    blocks.

    This has caused a miscompilation of rwlock.c from LinuxThreads for the
    `alpha-linux-gnu' target, where `rwlock->__rw_writer != thread_self ()'
    expression (where `thread_self' returns the thread pointer via a PALcode
    call) has been decided to be always true (with `ent->comparison_qty'
    using -1 for a reference to to `rwlock->__rw_writer', while register 0
    holding the thread pointer retrieved by `thread_self') and code for the
    false case has been optimized away where it mustn't have, causing
    program lockups.

    The issue has been observed as a regression from commit 08a692679fb8
    ("Undefined cse.c behaviour causes 3.4 regression on HPUX"),
    <https://gcc.gnu.org/ml/gcc-patches/2004-10/msg02027.html>, and up to
    commit 932ad4d9b550 ("Make CSE path following use the CFG"),
    <https://gcc.gnu.org/ml/gcc-patches/2006-12/msg00431.html>, where CSE
    has been restructured sufficiently for the issue not to trigger with the
    original reproducer anymore.  However the original bug remains and can
    trigger, because `comparison_qty' will still be assigned -1 for a memory
    reference and the `reg_qty' member of a `cse_reg_info_table' entry will
    still be assigned -1 for register 0 where the entry has not been
    assigned a quantity, e.g. at initialization.

    Use INT_MIN then as noted above, so that the value remains negative, for
    consistency with the REGNO_QTY_VALID_P macro (even though not used on
    `comparison_qty'), and then so that it should not ever match a valid
    negated register number, fixing the regression with commit 08a692679fb8.

            gcc/
            PR rtl-optimization/115565
            * cse.cc (record_jump_cond): Use INT_MIN rather than -1 for
            `comparison_qty' if !REG_P.

[Bug rtl-optimization/115565] [11/12/13/14/15 Regression] CSE: Comparison incorrectly evaluated as constant causing optimization to produce wrong code

[macro at orcam dot me.uk]

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

Maciej W. Rozycki <macro at orcam dot me.uk> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |macro at orcam dot me.uk
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #5 from Maciej W. Rozycki <macro at orcam dot me.uk> ---
Fix committed, closing bug.