[Bug rtl-optimization/109187] New: [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2

[Bug rtl-optimization/109187] New: [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2

[zsojka at seznam dot cz]

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

            Bug ID: 109187
           Summary: [13 Regression] ICE: qsort checking failed: qsort
                    comparator non-negative on sorted output: 1736258160
                    at -O2
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zsojka at seznam dot cz
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu
            Target: aarch64-unknown-linux-gnu

Created attachment 54703
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54703&action=edit
reduced testcase

Compiler output:
$ aarch64-unknown-linux-gnu-gcc testcase.c -O2
testcase.c: In function 'foo':
testcase.c:15:1: error: qsort comparator non-negative on sorted output:
1736258160
   15 | }
      | ^
during RTL pass: sched1
testcase.c:15:1: internal compiler error: qsort checking failed
0xad2af3 qsort_chk_error
        /repo/gcc-trunk/gcc/vec.cc:204
0xad2c3c qsort_chk(void*, unsigned long, unsigned long, int (*)(void const*,
void const*, void*), void*)
        /repo/gcc-trunk/gcc/vec.cc:246
0x20ccab5 gcc_qsort(void*, unsigned long, unsigned long, int (*)(void const*,
void const*))
        /repo/gcc-trunk/gcc/sort.cc:272
0x1ec3882 ready_sort_real
        /repo/gcc-trunk/gcc/haifa-sched.cc:3095
0x1ecc05c ready_sort
        /repo/gcc-trunk/gcc/haifa-sched.cc:3111
0x1ecc05c schedule_block(basic_block_def**, void*)
        /repo/gcc-trunk/gcc/haifa-sched.cc:6718
0x1125b1a schedule_region
        /repo/gcc-trunk/gcc/sched-rgn.cc:3200
0x1125b1a schedule_insns()
        /repo/gcc-trunk/gcc/sched-rgn.cc:3527
0x1125dec schedule_insns()
        /repo/gcc-trunk/gcc/sched-rgn.cc:3513
0x1125dec rest_of_handle_sched
        /repo/gcc-trunk/gcc/sched-rgn.cc:3731
0x1125dec execute
        /repo/gcc-trunk/gcc/sched-rgn.cc:3841
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
           Keywords|                            |needs-bisection

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-03-20
     Ever confirmed|0                           |1
            Summary|[13 Regression] ICE: qsort  |[13 Regression] ICE: qsort
                   |checking failed: qsort      |checking failed: qsort
                   |comparator non-negative on  |comparator non-negative on
                   |sorted output: 1736258160   |sorted output: 1736258160
                   |at -O2                      |at -O2 since
                   |                            |r13-5154-g733a1b777f16cd
                 CC|                            |amonakov at gcc dot gnu.org,
                   |                            |marxin at gcc dot gnu.org
           Keywords|needs-bisection             |
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Martin Liška <marxin at gcc dot gnu.org> ---
Started with r13-5154-g733a1b777f16cd.

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[amonakov at gcc dot gnu.org]

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

--- Comment #2 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
This is caused by overflowing subtraction in autopref_rank_for_schedule:

      if (!irrel1 && !irrel2)
        /* Sort memory references from lowest offset to the largest.  */
        r = data1->offset - data2->offset;

When offsets are arbitrary this pattern (anti-pattern?) is inappropriate for
producing a less/equal/greater comparison result. The following (or variants)
is safe:

diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc
index 4efaa9445..11bf10645 100644
--- a/gcc/haifa-sched.cc
+++ b/gcc/haifa-sched.cc
@@ -5686,7 +5686,7 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const
rtx_insn *insn2)

       if (!irrel1 && !irrel2)
        /* Sort memory references from lowest offset to the largest.  */
-       r = data1->offset - data2->offset;
+       r = (data1->offset > data2->offset) - (data1->offset < data2->offset);
       else if (write)
        /* Schedule "irrelevant" insns before memory stores to resolve
           as many producer dependencies of stores as possible.  */

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[amonakov at gcc dot gnu.org]

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

--- Comment #3 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
The reduced case is offsetting stack variables in a manner that seems too
invalid for my taste, so I plan to send a patch with a following testcase
instead (needs -O2 --param sched-autopref-queue-depth=1, ICEs on amd64):

void f(int *a)
{
  for (;;)
    asm("" :: "r"(a[-0x10000000]), "r"(a[0x10000000]), "r"(a[0]) : "memory");
}

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |amonakov at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks Alex.

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Alexander Monakov <amonakov@gcc.gnu.org>:

https://gcc.gnu.org/g:fb046e69f0ed2d637ea715ae71ad50131f30cb2d

commit r13-6907-gfb046e69f0ed2d637ea715ae71ad50131f30cb2d
Author: Alexander Monakov <amonakov@ispras.ru>
Date:   Tue Mar 28 16:00:37 2023 +0300

    haifa-sched: fix autopref_rank_for_schedule comparator [PR109187]

    Do not attempt to use a plain subtraction for generating a three-way
    comparison result in autopref_rank_for_schedule qsort comparator, as
    offsets are not restricted and subtraction may overflow.  Open-code
    a safe three-way comparison instead.

    gcc/ChangeLog:

            PR rtl-optimization/109187
            * haifa-sched.cc (autopref_rank_for_schedule): Avoid use of
overflowing
            subtraction in three-way comparison.

    gcc/testsuite/ChangeLog:

            PR rtl-optimization/109187
            * gcc.dg/pr109187.c: New test.

[Bug rtl-optimization/109187] [13 Regression] ICE: qsort checking failed: qsort comparator non-negative on sorted output: 1736258160 at -O2 since r13-5154-g733a1b777f16cd

[amonakov at gcc dot gnu.org]

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

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

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

--- Comment #6 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
Fixed on the trunk, thanks for the report.