[Bug tree-optimization/71702] New: dr_group_sort_cmp violates transitivity required for qsort

["amonakov at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

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

            Bug ID: 71702
           Summary: dr_group_sort_cmp violates transitivity required for
                    qsort
           Product: gcc
           Version: 5.3.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amonakov at gcc dot gnu.org
  Target Milestone: ---

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

On the attached testcase, with gcc-4.9.3 or gcc-5.3, with '-O3
-fno-strict-overflow', invocation of qsort with comparator dr_group_sort_cmp
from vect_analyze_data_ref_accesses during SLP pass demonstrates that this
comparator can lack transitivity: there is a triple of data references such
that comparator indicates dr1 > dr2 && dr2 > dr3 && dr3 > dr1.

I couldn't reproduce this with gcc-6 or trunk (but I don't know if it's
actually fixed there).

On musl-hosted GCC, this leads to an ICE on gcc_assert further below in
vect_analyze_data_ref_accesses.  On Glibc-hosted GCC the resulting sort order
is different, so the assert doesn't trigger on this testcase.

It's possible to stop in gdb on the faulty invocation using a simple LD_PRELOAD
validator (to be attached):

gcc -std=c99 -g -fPIC -shared qsortchk.so qsortchk.c
gdb -ex "set env LD_PRELOAD=`pwd`/qsortchk.so" --args \
  .../5.3.0/cc1 -O3 -fno-strict-overflow ssmin.c

On 5.3 the problematic dataref triple seems to be:

Creating dr for *_27
analyze_innermost: success.
        base_address: Lx_26(D) + _24 * 8
        offset from base address: 0
        constant offset from base address: 0
        step: 0
        aligned to: 128
        base_object: *_27

Creating dr for *_40
analyze_innermost: Applying pattern match.pd:49, generic-match.c:3223
success.
        base_address: Lx_26(D) + (sizetype) _34 * 8
        offset from base address: 0
        constant offset from base address: 8
        step: 0
        aligned to: 128
        base_object: *_40

Creating dr for *_31
analyze_innermost: Applying pattern match.pd:49, generic-match.c:3223
success.
        base_address: Lx_26(D) + (sizetype) _24 * 8
        offset from base address: 0
        constant offset from base address: 8
        step: 0
        aligned to: 128
        base_object: *_31