[PATCH 0/6] qsort comparator consistency fixes

[Alexander Monakov <amonakov at ispras dot ru>]

Hello,

(previous thread here:
https://gcc.gnu.org/ml/gcc-patches/2016-07/msg00944.html )

we still have a few places in GCC where the comparator function passed to qsort
is not actually a proper sorting predicate.  Most commonly it fails to impose
total ordering by lacking transitivity.  It's useful to fix such instances,
because:

- such comparators don't work as intended;
- they lead to issues that can only be reproduced with a specific libc;
- failure usually happens not in qsort, but quite some time later.

(PR 71702 and its duplicates is a good highlight for the latter two, it
could only be observed with qsort from musl libc and manifested as assert
failure in the vectorizer, which was not trivial to diagnose)

The goal of this patchset is to introduce automatic comparator consistency
verification in GCC, with zero impact on release-checking compilers and
minimal workflow disturbance (it should be possible to easily suppress
checking to e.g. unblock bootstrap when there's no obvious fix).

Changes from the last year's patch:

+ both vec::qsort and libc ::qsort are checked (previously only vec::)
+ individual callers can opt out of checking
+ a bit more sensible cutoff for avoiding O(n^2) time complexity
+ unlike a year ago, now this needs 5 accompanying patches for broken
  comparators, meaning new issues have crept in

The first question last year from Richard was about bootstrap time impact.
Last year it appeared to be in the noise, I can do it again if there's
interest.

Patches 1-3 fix broken comparators where the fix is evident, patches 4-5
avoid qsort checking where comparators needs nontrivial fixes, and patch
6 is the actual checking implementation.

  tree-vrp: fix compare_assert_loc qsort comparator
  gimple-ssa-store-merging.c: fix sort_by_bitpos
  lra-assigns.c: fix pseudo_compare_func
  lra-assigns.c: give up on qsort checking in assign_by_spills
  haifa-sched.c: give up qsort checking when autoprefetch heuristic is
    in use
  qsort comparator consistency checking

 gcc/genmodes.c                 |  2 +-
 gcc/gimple-ssa-store-merging.c |  6 +--
 gcc/haifa-sched.c              |  8 ++++
 gcc/lra-assigns.c              | 10 ++---
 gcc/system.h                   | 11 +++++
 gcc/tree-vrp.c                 |  2 +-
 gcc/vec.c                      | 95 ++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 124 insertions(+), 10 deletions(-)

-- 
1.8.3.1