Bug 82381 - [8 Regression] internal compiler error: qsort checking failed
Summary: [8 Regression] internal compiler error: qsort checking failed
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 8.0
: P3 normal
Target Milestone: 8.0
Assignee: Jakub Jelinek
Keywords: ice-checking
Depends on:
Blocks: qsort_chk yarpgen
  Show dependency treegraph
Reported: 2017-10-01 07:15 UTC by Dmitry Babokin
Modified: 2021-11-01 23:07 UTC (History)
4 users (show)

See Also:
Known to work:
Known to fail:
Last reconfirmed:

gcc8-pr82381.patch (891 bytes, patch)
2017-10-02 15:31 UTC, Jakub Jelinek
Details | Diff
gcc8-pr82381.patch (1.07 KB, patch)
2017-10-02 16:51 UTC, Jakub Jelinek
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Dmitry Babokin 2017-10-01 07:15:07 UTC
GCC trunk rev 253307, x86_64.

This looks like a fresh regression. I see quite many fails like this one.

> cat f.cpp
char b, h;
unsigned short c, e;
short d, f, g;
void i() {
  if (h) {
    short a(-(d + c - b));
    f = e - a - -d;
  if (c)
    g = 0;

> g++ -O2 -c f.cpp
f.cpp: In function ‘void i()’:
f.cpp:4:6: error: qsort comparator non-negative on sorted output: 1
 void i() {
during GIMPLE pass: reassoc
f.cpp:4:6: internal compiler error: qsort checking failed
0x8fbc82 qsort_chk_error
0x8fbcfb qsort_chk(void*, unsigned long, unsigned long, int (*)(void const*, void const*))
0x7d9118 vec<operand_entry*, va_heap, vl_embed>::qsort(int (*)(void const*, void const*))
0x7d9118 vec<operand_entry*, va_heap, vl_ptr>::qsort(int (*)(void const*, void const*))
0x7d9118 reassociate_bb
0x7d755b reassociate_bb
0x7d755b reassociate_bb
0x7d755b reassociate_bb
0x109673c do_reassoc
0x109673c execute_reassoc
0x109673c execute
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.
Comment 1 David Binderman 2017-10-01 17:40:33 UTC
Problem seems to have appeared between revisions 253276 and 253315.
Comment 2 Martin Liška 2017-10-02 08:39:23 UTC
Confirmed, started with added qsort checking in r253295. I'll fix that.
Comment 3 Richard Biener 2017-10-02 08:45:57 UTC
Probably simply

2017-09-29  Alexander Monakov  <amonakov@ispras.ru>

        * genmodes.c (calc_wider_mode): Suppress qsort macro.
        * system.h [CHECKING_P] (qsort): Redirect to qsort_chk.
        (qsort_chk): Declare.
        * vec.c [CHECKING_P] (qsort_chk_error): New static function.
        (qsort_chk): New function.

we now check validity of qsort compare functions.

#2  0x0000000001dc91d2 in qsort_chk (base=0x2c2e438, n=4, size=8, cmp=
    0x14074c6 <sort_by_operand_rank(void const*, void const*)>)
    at /tmp/trunk2/gcc/vec.c:274
274                 return ERR3 (i, i1, j);
(gdb) l
269           /* Verify that elements within this span compare less than
270              elements beyond the span.  */
271           for (i = i1; i < i2; i++)
272             for (j = i2; j < i2 + lim2; j++)
273               if (CMP (i, j) >= 0)
274                 return ERR3 (i, i1, j);
275               else if (CMP (j, i) <= 0)
276                 return ERR2 (i, j);

I'm quite sure that

      /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
         versions of removed SSA_NAMEs, so if possible, prefer to sort
         based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
         See PR60418.  */
      if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
          && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
          && !oea->stmt_to_insert
          && !oeb->stmt_to_insert
          && SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
          gimple *stmta = SSA_NAME_DEF_STMT (oea->op);
          gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
          basic_block bba = gimple_bb (stmta);
          basic_block bbb = gimple_bb (stmtb);
          if (bbb != bba)
              if (bb_rank[bbb->index] != bb_rank[bba->index])
                return bb_rank[bbb->index] - bb_rank[bba->index];
              bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
              bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
              if (da != db)
                return da ? 1 : -1;

breaks transitivity because of the ->stmt_to_insert check.  Here we have
[1] !stmt_to_insert [2] !stmt_to_insert [3] stmt_to_insert

This kind of ordering isn't going to work :/

First introduced by Jakub but then broke with the stmt_to_insert addition
by Kugan...

I guess we need some approximate insert location here.
Comment 4 Jakub Jelinek 2017-10-02 14:56:43 UTC
Richard, this is something you've suggested in:
To answer my question from:
the bb_rank can be the same for different bbs, if we have more than 65536 basic blocks on 32-bit hosts.

So, I think we should go for reversion of msg01871.html and instead apply the other patch.
Comment 5 Jakub Jelinek 2017-10-02 15:31:41 UTC
Created attachment 42286 [details]

Something like this.
Comment 6 Jakub Jelinek 2017-10-02 16:51:00 UTC
Created attachment 42290 [details]

Actually better like this.  The case when one SSA_NAME is (D) and the other is not still could result in transitivity problems.
Comment 7 Jakub Jelinek 2017-10-03 11:25:10 UTC
Author: jakub
Date: Tue Oct  3 11:24:39 2017
New Revision: 253379

URL: https://gcc.gnu.org/viewcvs?rev=253379&root=gcc&view=rev
	PR tree-optimization/82381
	* tree-ssa-reassoc.c (sort_by_operand_rank): Don't check
	stmt_to_insert nor wheather SSA_NAMEs are default defs.
	Return 1 or -1 if one of bba and bbb is NULL. If bb_rank is equal,
	fallthrough into reassoc_stmt_dominates_stmt_p.

	* gcc.c-torture/compile/pr82381.c: New test.

Comment 8 Christophe Lyon 2017-10-03 12:15:52 UTC
FWIW, Jakub's patch (in comment #7) doesn't fix the build failure I reported at https://gcc.gnu.org/ml/gcc-patches/2017-09/msg01980.html
Comment 9 Steve Ellcey 2017-10-03 16:13:43 UTC
(In reply to Christophe Lyon from comment #8)
> FWIW, Jakub's patch (in comment #7) doesn't fix the build failure I reported
> at https://gcc.gnu.org/ml/gcc-patches/2017-09/msg01980.html

Presumably, that problem is PR 82396.
Comment 10 Jakub Jelinek 2017-10-04 07:53:29 UTC
Author: jakub
Date: Wed Oct  4 07:52:26 2017
New Revision: 253396

URL: https://gcc.gnu.org/viewcvs?rev=253396&root=gcc&view=rev
	PR tree-optimization/82381
	* tree-ssa-reassoc.c (sort_by_operand_rank): Check for different
	oeN->rank first.  Return 1 or -1 if one op is SSA_NAME and the other
	is not.

Comment 11 Andrey Guskov 2017-10-04 09:15:35 UTC
Also having that on half the SPEC CPU2017. Glad that it`s already fixed.

Likely duplicates: pr82395, pr82396, pr82397, pr82398, pr82401
Comment 12 Jakub Jelinek 2017-10-11 10:34:50 UTC