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