| Message ID | alpine.LNX.2.20.13.1709291604420.18755@monopod.intra.ispras.ru |
|---|---|
| State | New |
| Headers | show |
| Series | [reviewed] qsort comparator consistency checking | expand |
Hi, On 29 September 2017 at 15:29, Alexander Monakov <amonakov@ispras.ru> wrote: > Hello, > > I'm going to install the following patch on trunk in the next few hours. > This revision doesn't offer per-callsite opt-out anymore as suggested by > Richi on the Cauldron (made possible by fixing all known issues on trunk). > Thus this patch has a few minor differences compared to the previous > revision that was ack'ed by Jeff. > > Tested on x86_64-linux, i686-linux and ppc64le-linux. > > Alexander > > * 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. > This patch (r253295) breaks the gcc build for aarch64-linux-gnu: libtool: compile: /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc/xgcc -shared-libgcc -B/tmp/3041688_6.t mpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc -nostdinc++ -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj -aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-g nu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src/.libs -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64 -none-linux-gnu/libstdc++-v3/libsupc++/.libs -B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/bin/ -B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/lib/ -isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/include -isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/sys-include -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/../libgcc -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/aarch64-none-linux-gnu -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/libsupc++ -D_GLIBCXX_SHARED -std=gnu++14 -Wall -Wextra -Wwrite-strings -Wcast-qual -Wabi -fdiagnostics-show-location=once -ffunction-sections -fdata-sections -frandom-seed=ops.lo -g -O2 -D_GNU_SOURCE -c /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc -fPIC -DPIC -D_GLIBCXX_SHARED -o ops.o In file included from /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/deque:66:0, from /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/stack:60, from /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc:32: /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc: In member function 'void std::deque<_Tp, _Alloc>::_M_range_insert_aux(std::deque<_Tp, _Alloc>::iterator, _ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with _ForwardIterator = std::experimental::filesystem::v1::__cxx11::path::iterator; _Tp = std::experimental::filesystem::v1::__cxx11::path; _Alloc = std::allocator<std::experimental::filesystem::v1::__cxx11::path>]': /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7: error: qsort comparator non-negative on sorted output: 8 } ^ during RTL pass: sched2 /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7: internal compiler error: qsort checking failed 0x55f7a1 qsort_chk_error /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:222 0x15337d8 qsort_chk(void*, unsigned long, unsigned long, int (*)(void const*, void const*)) /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:274 0x14360e0 ready_sort_real /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:3087 0x143de85 schedule_block(basic_block_def**, void*) /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:6749 0xd42132 schedule_region /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3174 0xd42132 schedule_insns() /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3513 0xd424ee rest_of_handle_sched2 /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3737 0xd424ee execute /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3873 Christophe > diff --git a/gcc/genmodes.c b/gcc/genmodes.c > index 97ed949c255..4eb8ee56d88 100644 > --- a/gcc/genmodes.c > +++ b/gcc/genmodes.c > @@ -880,7 +880,7 @@ calc_wider_mode (void) > for (i = 0, m = modes[c]; m; i++, m = m->next) > sortbuf[i] = m; > > - qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes); > + (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes); > > sortbuf[i] = 0; > for (j = 0; j < i; j++) > diff --git a/gcc/system.h b/gcc/system.h > index 59449f1942b..f0664e93fc8 100644 > --- a/gcc/system.h > +++ b/gcc/system.h > @@ -1181,4 +1181,14 @@ helper_const_non_const_cast (const char *p) > /* Get definitions of HOST_WIDE_INT. */ > #include "hwint.h" > > +/* qsort comparator consistency checking: except in release-checking compilers, > + redirect 4-argument qsort calls to qsort_chk; keep 1-argument invocations > + corresponding to vec::qsort (cmp): they use C qsort internally anyway. */ > +#if CHECKING_P > +#define PP_5th(a1, a2, a3, a4, a5, ...) a5 > +#undef qsort > +#define qsort(...) PP_5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__) > +void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *)); > +#endif > + > #endif /* ! GCC_SYSTEM_H */ > diff --git a/gcc/vec.c b/gcc/vec.c > index d612703184b..9a80f3421db 100644 > --- a/gcc/vec.c > +++ b/gcc/vec.c > @@ -31,6 +31,12 @@ along with GCC; see the file COPYING3. If not see > #include "coretypes.h" > #include "hash-table.h" > #include "selftest.h" > +#ifdef GENERATOR_FILE > +#include "errors.h" > +#else > +#include "input.h" > +#include "diagnostic-core.h" > +#endif > > /* vNULL is an empty type with a template cast operation that returns > a zero-initialized vec<T, A, L> instance. Use this when you want > @@ -190,6 +196,93 @@ dump_vec_loc_statistics (void) > vec_mem_desc.dump (VEC_ORIGIN); > } > > +#if CHECKING_P > +/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as > + witness elements. */ > +ATTRIBUTE_NORETURN ATTRIBUTE_COLD > +static void > +qsort_chk_error (const void *p1, const void *p2, const void *p3, > + int (*cmp) (const void *, const void *)) > +{ > + if (!p3) > + { > + int r1 = cmp (p1, p2), r2 = cmp (p2, p1); > + error ("qsort comparator not anti-commutative: %d, %d", r1, r2); > + } > + else if (p1 == p2) > + { > + int r = cmp (p1, p3); > + error ("qsort comparator non-negative on sorted output: %d", r); > + } > + else > + { > + int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); > + error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); > + } > + internal_error ("qsort checking failed"); > +} > + > +/* Wrapper around qsort with checking that CMP is consistent on given input. > + > + Strictly speaking, passing invalid (non-transitive, non-anti-commutative) > + comparators to libc qsort can result in undefined behavior. Therefore we > + should ideally perform consistency checks prior to invoking qsort, but in > + order to do that optimally we'd need to sort the array ourselves beforehand > + with a sorting routine known to be "safe". Instead, we expect that most > + implementations in practice will still produce some permutation of input > + array even for invalid comparators, which enables us to perform checks on > + the output array. */ > +void > +qsort_chk (void *base, size_t n, size_t size, > + int (*cmp)(const void *, const void *)) > +{ > + (qsort) (base, n, size, cmp); > +#if 0 > +#define LIM(n) (n) > +#else > + /* Limit overall time complexity to O(n log n). */ > +#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) > +#endif > +#define ELT(i) ((const char *) base + (i) * size) > +#define CMP(i, j) cmp (ELT (i), ELT (j)) > +#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) > +#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) > + size_t i1, i2, i, j; > + /* This outer loop iterates over maximum spans [i1, i2) such that > + elements within each span compare equal to each other. */ > + for (i1 = 0; i1 < n; i1 = i2) > + { > + /* Position i2 one past last element that compares equal to i1'th. */ > + for (i2 = i1 + 1; i2 < n; i2++) > + if (CMP (i1, i2)) > + break; > + else if (CMP (i2, i1)) > + return ERR2 (i1, i2); > + size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); > + /* Verify that other pairs within current span compare equal. */ > + for (i = i1 + 1; i + 1 < i2; i++) > + for (j = i + 1; j < i1 + lim1; j++) > + if (CMP (i, j)) > + return ERR3 (i, i1, j); > + else if (CMP (j, i)) > + return ERR2 (i, j); > + /* Verify that elements within this span compare less than > + elements beyond the span. */ > + for (i = i1; i < i2; i++) > + for (j = i2; j < i2 + lim2; j++) > + if (CMP (i, j) >= 0) > + return ERR3 (i, i1, j); > + else if (CMP (j, i) <= 0) > + return ERR2 (i, j); > + } > +#undef ERR3 > +#undef ERR2 > +#undef CMP > +#undef ELT > +#undef LIM > +} > +#endif /* #if CHECKING_P */ > + > #ifndef GENERATOR_FILE > #if CHECKING_P >
On Fri, Sep 29, 2017 at 10:46 AM, Christophe Lyon <christophe.lyon@linaro.org> wrote: > Hi, > > > On 29 September 2017 at 15:29, Alexander Monakov <amonakov@ispras.ru> wrote: >> Hello, >> >> I'm going to install the following patch on trunk in the next few hours. >> This revision doesn't offer per-callsite opt-out anymore as suggested by >> Richi on the Cauldron (made possible by fixing all known issues on trunk). >> Thus this patch has a few minor differences compared to the previous >> revision that was ack'ed by Jeff. >> >> Tested on x86_64-linux, i686-linux and ppc64le-linux. >> >> Alexander >> >> * 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. >> > > This patch (r253295) breaks the gcc build for aarch64-linux-gnu: I was just about to report the same thing. Thanks, Andrew > libtool: compile: > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc/xgcc > -shared-libgcc -B/tmp/3041688_6.t > mpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/./gcc > -nostdinc++ -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj > -aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src > -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-g > nu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/src/.libs > -L/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64 > -none-linux-gnu/libstdc++-v3/libsupc++/.libs > -B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/bin/ > -B/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/lib/ > -isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/include > -isystem /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/tools/aarch64-none-linux-gnu/sys-include > -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/../libgcc > -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/aarch64-none-linux-gnu > -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include > -I/tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/libsupc++ > -D_GLIBCXX_SHARED -std=gnu++14 -Wall -Wextra -Wwrite-strings > -Wcast-qual -Wabi -fdiagnostics-show-location=once -ffunction-sections > -fdata-sections -frandom-seed=ops.lo -g -O2 -D_GNU_SOURCE -c > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc > -fPIC -DPIC -D_GLIBCXX_SHARED -o ops.o > In file included from > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/deque:66:0, > from > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/stack:60, > from > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/libstdc++-v3/src/filesystem/ops.cc:32: > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc: > In member function 'void std::deque<_Tp, > _Alloc>::_M_range_insert_aux(std::deque<_Tp, _Alloc>::iterator, > _ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with > _ForwardIterator = > std::experimental::filesystem::v1::__cxx11::path::iterator; _Tp = > std::experimental::filesystem::v1::__cxx11::path; _Alloc = > std::allocator<std::experimental::filesystem::v1::__cxx11::path>]': > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7: > error: qsort comparator non-negative on sorted output: 8 > } > ^ > during RTL pass: sched2 > /tmp/3041688_6.tmpdir/aci-gcc-fsf/builds/gcc-fsf-gccsrc/obj-aarch64-none-linux-gnu/gcc3/aarch64-none-linux-gnu/libstdc++-v3/include/bits/deque.tcc:626:7: > internal compiler error: qsort checking failed > 0x55f7a1 qsort_chk_error > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:222 > 0x15337d8 qsort_chk(void*, unsigned long, unsigned long, int (*)(void > const*, void const*)) > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/vec.c:274 > 0x14360e0 ready_sort_real > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:3087 > 0x143de85 schedule_block(basic_block_def**, void*) > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/haifa-sched.c:6749 > 0xd42132 schedule_region > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3174 > 0xd42132 schedule_insns() > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3513 > 0xd424ee rest_of_handle_sched2 > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3737 > 0xd424ee execute > /tmp/3041688_6.tmpdir/aci-gcc-fsf/sources/gcc-fsf/gccsrc/gcc/sched-rgn.c:3873 > > Christophe > >> diff --git a/gcc/genmodes.c b/gcc/genmodes.c >> index 97ed949c255..4eb8ee56d88 100644 >> --- a/gcc/genmodes.c >> +++ b/gcc/genmodes.c >> @@ -880,7 +880,7 @@ calc_wider_mode (void) >> for (i = 0, m = modes[c]; m; i++, m = m->next) >> sortbuf[i] = m; >> >> - qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes); >> + (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes); >> >> sortbuf[i] = 0; >> for (j = 0; j < i; j++) >> diff --git a/gcc/system.h b/gcc/system.h >> index 59449f1942b..f0664e93fc8 100644 >> --- a/gcc/system.h >> +++ b/gcc/system.h >> @@ -1181,4 +1181,14 @@ helper_const_non_const_cast (const char *p) >> /* Get definitions of HOST_WIDE_INT. */ >> #include "hwint.h" >> >> +/* qsort comparator consistency checking: except in release-checking compilers, >> + redirect 4-argument qsort calls to qsort_chk; keep 1-argument invocations >> + corresponding to vec::qsort (cmp): they use C qsort internally anyway. */ >> +#if CHECKING_P >> +#define PP_5th(a1, a2, a3, a4, a5, ...) a5 >> +#undef qsort >> +#define qsort(...) PP_5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__) >> +void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *)); >> +#endif >> + >> #endif /* ! GCC_SYSTEM_H */ >> diff --git a/gcc/vec.c b/gcc/vec.c >> index d612703184b..9a80f3421db 100644 >> --- a/gcc/vec.c >> +++ b/gcc/vec.c >> @@ -31,6 +31,12 @@ along with GCC; see the file COPYING3. If not see >> #include "coretypes.h" >> #include "hash-table.h" >> #include "selftest.h" >> +#ifdef GENERATOR_FILE >> +#include "errors.h" >> +#else >> +#include "input.h" >> +#include "diagnostic-core.h" >> +#endif >> >> /* vNULL is an empty type with a template cast operation that returns >> a zero-initialized vec<T, A, L> instance. Use this when you want >> @@ -190,6 +196,93 @@ dump_vec_loc_statistics (void) >> vec_mem_desc.dump (VEC_ORIGIN); >> } >> >> +#if CHECKING_P >> +/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as >> + witness elements. */ >> +ATTRIBUTE_NORETURN ATTRIBUTE_COLD >> +static void >> +qsort_chk_error (const void *p1, const void *p2, const void *p3, >> + int (*cmp) (const void *, const void *)) >> +{ >> + if (!p3) >> + { >> + int r1 = cmp (p1, p2), r2 = cmp (p2, p1); >> + error ("qsort comparator not anti-commutative: %d, %d", r1, r2); >> + } >> + else if (p1 == p2) >> + { >> + int r = cmp (p1, p3); >> + error ("qsort comparator non-negative on sorted output: %d", r); >> + } >> + else >> + { >> + int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); >> + error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); >> + } >> + internal_error ("qsort checking failed"); >> +} >> + >> +/* Wrapper around qsort with checking that CMP is consistent on given input. >> + >> + Strictly speaking, passing invalid (non-transitive, non-anti-commutative) >> + comparators to libc qsort can result in undefined behavior. Therefore we >> + should ideally perform consistency checks prior to invoking qsort, but in >> + order to do that optimally we'd need to sort the array ourselves beforehand >> + with a sorting routine known to be "safe". Instead, we expect that most >> + implementations in practice will still produce some permutation of input >> + array even for invalid comparators, which enables us to perform checks on >> + the output array. */ >> +void >> +qsort_chk (void *base, size_t n, size_t size, >> + int (*cmp)(const void *, const void *)) >> +{ >> + (qsort) (base, n, size, cmp); >> +#if 0 >> +#define LIM(n) (n) >> +#else >> + /* Limit overall time complexity to O(n log n). */ >> +#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) >> +#endif >> +#define ELT(i) ((const char *) base + (i) * size) >> +#define CMP(i, j) cmp (ELT (i), ELT (j)) >> +#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) >> +#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) >> + size_t i1, i2, i, j; >> + /* This outer loop iterates over maximum spans [i1, i2) such that >> + elements within each span compare equal to each other. */ >> + for (i1 = 0; i1 < n; i1 = i2) >> + { >> + /* Position i2 one past last element that compares equal to i1'th. */ >> + for (i2 = i1 + 1; i2 < n; i2++) >> + if (CMP (i1, i2)) >> + break; >> + else if (CMP (i2, i1)) >> + return ERR2 (i1, i2); >> + size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); >> + /* Verify that other pairs within current span compare equal. */ >> + for (i = i1 + 1; i + 1 < i2; i++) >> + for (j = i + 1; j < i1 + lim1; j++) >> + if (CMP (i, j)) >> + return ERR3 (i, i1, j); >> + else if (CMP (j, i)) >> + return ERR2 (i, j); >> + /* Verify that elements within this span compare less than >> + elements beyond the span. */ >> + for (i = i1; i < i2; i++) >> + for (j = i2; j < i2 + lim2; j++) >> + if (CMP (i, j) >= 0) >> + return ERR3 (i, i1, j); >> + else if (CMP (j, i) <= 0) >> + return ERR2 (i, j); >> + } >> +#undef ERR3 >> +#undef ERR2 >> +#undef CMP >> +#undef ELT >> +#undef LIM >> +} >> +#endif /* #if CHECKING_P */ >> + >> #ifndef GENERATOR_FILE >> #if CHECKING_P >>
On Fri, 29 Sep 2017, Andrew Pinski wrote: > > This patch (r253295) breaks the gcc build for aarch64-linux-gnu: > > I was just about to report the same thing. I think autoprefetch ranking heuristic is still wrong if multi_mem_insn_p may be true; please try this patch. * haifa-sched.c (autopref_rank_data): Remove. (autopref_rank_for_schedule): Only use min_offset difference. diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 549e8961411..cea1242e1f1 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -5647,62 +5647,6 @@ autopref_multipass_init (const rtx_insn *insn, int write) } -/* Helper for autopref_rank_for_schedule. Given the data of two - insns relevant to the auto-prefetcher modelling code DATA1 and DATA2 - return their comparison result. Return 0 if there is no sensible - ranking order for the two insns. */ - -static int -autopref_rank_data (autopref_multipass_data_t data1, - autopref_multipass_data_t data2) -{ - /* Simple case when both insns are simple single memory ops. */ - if (!data1->multi_mem_insn_p && !data2->multi_mem_insn_p) - return data1->min_offset - data2->min_offset; - - /* Two load/store multiple insns. Return 0 if the offset ranges - overlap and the difference between the minimum offsets otherwise. */ - else if (data1->multi_mem_insn_p && data2->multi_mem_insn_p) - { - int min1 = data1->min_offset; - int max1 = data1->max_offset; - int min2 = data2->min_offset; - int max2 = data2->max_offset; - - if (max1 < min2 || min1 > max2) - return min1 - min2; - else - return 0; - } - - /* The other two cases is a pair of a load/store multiple and - a simple memory op. Return 0 if the single op's offset is within the - range of the multi-op insn and the difference between the single offset - and the minimum offset of the multi-set insn otherwise. */ - else if (data1->multi_mem_insn_p && !data2->multi_mem_insn_p) - { - int max1 = data1->max_offset; - int min1 = data1->min_offset; - - if (data2->min_offset >= min1 - && data2->min_offset <= max1) - return 0; - else - return min1 - data2->min_offset; - } - else - { - int max2 = data2->max_offset; - int min2 = data2->min_offset; - - if (data1->min_offset >= min2 - && data1->min_offset <= max2) - return 0; - else - return data1->min_offset - min2; - } -} - /* Helper function for rank_for_schedule sorting. */ static int autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2) @@ -5725,7 +5669,7 @@ autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2) int irrel2 = data2->status == AUTOPREF_MULTIPASS_DATA_IRRELEVANT; if (!irrel1 && !irrel2) - r = autopref_rank_data (data1, data2); + r = data1->min_offset - data2->min_offset; else r = irrel2 - irrel1; }
On Fri, 2017-09-29 at 21:14 +0300, Alexander Monakov wrote: > On Fri, 29 Sep 2017, Andrew Pinski wrote: > > > > > > > > This patch (r253295) breaks the gcc build for aarch64-linux-gnu: > > I was just about to report the same thing. > I think autoprefetch ranking heuristic is still wrong if > multi_mem_insn_p > may be true; please try this patch. > > * haifa-sched.c (autopref_rank_data): Remove. > (autopref_rank_for_schedule): Only use min_offset difference. This fixed the build for me on aarch64. I am still running the testsuite. Steve Ellcey sellcey@cavium.com
On 29 September 2017 at 21:39, Steve Ellcey <sellcey@cavium.com> wrote: > On Fri, 2017-09-29 at 21:14 +0300, Alexander Monakov wrote: >> On Fri, 29 Sep 2017, Andrew Pinski wrote: >> > >> > > >> > > This patch (r253295) breaks the gcc build for aarch64-linux-gnu: >> > I was just about to report the same thing. >> I think autoprefetch ranking heuristic is still wrong if >> multi_mem_insn_p >> may be true; please try this patch. >> >> * haifa-sched.c (autopref_rank_data): Remove. >> (autopref_rank_for_schedule): Only use min_offset difference. > > This fixed the build for me on aarch64. I am still running the > testsuite. > It doesn't for me. I'm getting another build error: /home/christophe.lyon/src/GCC/sources/gcc-fsf/aarch64-build/gcc/haifa-sched.c: In function ‘int autopref_multipass_dfa_lookahead_guard_1(const rtx_insn*, const rtx_insn*, int)’: /home/christophe.lyon/src/GCC/sources/gcc-fsf/aarch64-build/gcc/haifa-sched.c:5700:42: error: ‘autopref_rank_data’ was not declared in this scope The removed autopref_rank_data function is still called by autopref_multipass_dfa_lookahead_guard_1. Christophe > Steve Ellcey > sellcey@cavium.com
On Fri, 2017-09-29 at 21:43 +0200, Christophe Lyon wrote: > On 29 September 2017 at 21:39, Steve Ellcey <sellcey@cavium.com> > wrote: > > > > On Fri, 2017-09-29 at 21:14 +0300, Alexander Monakov wrote: > > > > > > On Fri, 29 Sep 2017, Andrew Pinski wrote: > > > > > > > > > > > > > > > > > > > > > > > This patch (r253295) breaks the gcc build for aarch64-linux- > > > > > gnu: > > > > I was just about to report the same thing. > > > I think autoprefetch ranking heuristic is still wrong if > > > multi_mem_insn_p > > > may be true; please try this patch. > > > > > > * haifa-sched.c (autopref_rank_data): Remove. > > > (autopref_rank_for_schedule): Only use min_offset > > > difference. > > This fixed the build for me on aarch64. I am still running the > > testsuite. > > > It doesn't for me. I'm getting another build error: > /home/christophe.lyon/src/GCC/sources/gcc-fsf/aarch64- > build/gcc/haifa-sched.c: > In function ‘int autopref_multipass_dfa_lookahead_guard_1(const > rtx_insn*, const rtx_insn*, int)’: > /home/christophe.lyon/src/GCC/sources/gcc-fsf/aarch64- > build/gcc/haifa-sched.c:5700:42: > error: ‘autopref_rank_data’ was not declared in this scope > > The removed autopref_rank_data function is still called by > autopref_multipass_dfa_lookahead_guard_1. OK, I actually cheated and removed the call but not the function itself because 'it couldn't possible matter, could it'? :-) Steve Ellcey
diff --git a/gcc/genmodes.c b/gcc/genmodes.c index 97ed949c255..4eb8ee56d88 100644 --- a/gcc/genmodes.c +++ b/gcc/genmodes.c @@ -880,7 +880,7 @@ calc_wider_mode (void) for (i = 0, m = modes[c]; m; i++, m = m->next) sortbuf[i] = m; - qsort (sortbuf, i, sizeof (struct mode_data *), cmp_modes); + (qsort) (sortbuf, i, sizeof (struct mode_data *), cmp_modes); sortbuf[i] = 0; for (j = 0; j < i; j++) diff --git a/gcc/system.h b/gcc/system.h index 59449f1942b..f0664e93fc8 100644 --- a/gcc/system.h +++ b/gcc/system.h @@ -1181,4 +1181,14 @@ helper_const_non_const_cast (const char *p) /* Get definitions of HOST_WIDE_INT. */ #include "hwint.h" +/* qsort comparator consistency checking: except in release-checking compilers, + redirect 4-argument qsort calls to qsort_chk; keep 1-argument invocations + corresponding to vec::qsort (cmp): they use C qsort internally anyway. */ +#if CHECKING_P +#define PP_5th(a1, a2, a3, a4, a5, ...) a5 +#undef qsort +#define qsort(...) PP_5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__) +void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *)); +#endif + #endif /* ! GCC_SYSTEM_H */ diff --git a/gcc/vec.c b/gcc/vec.c index d612703184b..9a80f3421db 100644 --- a/gcc/vec.c +++ b/gcc/vec.c @@ -31,6 +31,12 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "hash-table.h" #include "selftest.h" +#ifdef GENERATOR_FILE +#include "errors.h" +#else +#include "input.h" +#include "diagnostic-core.h" +#endif /* vNULL is an empty type with a template cast operation that returns a zero-initialized vec<T, A, L> instance. Use this when you want @@ -190,6 +196,93 @@ dump_vec_loc_statistics (void) vec_mem_desc.dump (VEC_ORIGIN); } +#if CHECKING_P +/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as + witness elements. */ +ATTRIBUTE_NORETURN ATTRIBUTE_COLD +static void +qsort_chk_error (const void *p1, const void *p2, const void *p3, + int (*cmp) (const void *, const void *)) +{ + if (!p3) + { + int r1 = cmp (p1, p2), r2 = cmp (p2, p1); + error ("qsort comparator not anti-commutative: %d, %d", r1, r2); + } + else if (p1 == p2) + { + int r = cmp (p1, p3); + error ("qsort comparator non-negative on sorted output: %d", r); + } + else + { + int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3); + error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3); + } + internal_error ("qsort checking failed"); +} + +/* Wrapper around qsort with checking that CMP is consistent on given input. + + Strictly speaking, passing invalid (non-transitive, non-anti-commutative) + comparators to libc qsort can result in undefined behavior. Therefore we + should ideally perform consistency checks prior to invoking qsort, but in + order to do that optimally we'd need to sort the array ourselves beforehand + with a sorting routine known to be "safe". Instead, we expect that most + implementations in practice will still produce some permutation of input + array even for invalid comparators, which enables us to perform checks on + the output array. */ +void +qsort_chk (void *base, size_t n, size_t size, + int (*cmp)(const void *, const void *)) +{ + (qsort) (base, n, size, cmp); +#if 0 +#define LIM(n) (n) +#else + /* Limit overall time complexity to O(n log n). */ +#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n)) +#endif +#define ELT(i) ((const char *) base + (i) * size) +#define CMP(i, j) cmp (ELT (i), ELT (j)) +#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp) +#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp) + size_t i1, i2, i, j; + /* This outer loop iterates over maximum spans [i1, i2) such that + elements within each span compare equal to each other. */ + for (i1 = 0; i1 < n; i1 = i2) + { + /* Position i2 one past last element that compares equal to i1'th. */ + for (i2 = i1 + 1; i2 < n; i2++) + if (CMP (i1, i2)) + break; + else if (CMP (i2, i1)) + return ERR2 (i1, i2); + size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2); + /* Verify that other pairs within current span compare equal. */ + for (i = i1 + 1; i + 1 < i2; i++) + for (j = i + 1; j < i1 + lim1; j++) + if (CMP (i, j)) + return ERR3 (i, i1, j); + else if (CMP (j, i)) + return ERR2 (i, j); + /* Verify that elements within this span compare less than + elements beyond the span. */ + for (i = i1; i < i2; i++) + for (j = i2; j < i2 + lim2; j++) + if (CMP (i, j) >= 0) + return ERR3 (i, i1, j); + else if (CMP (j, i) <= 0) + return ERR2 (i, j); + } +#undef ERR3 +#undef ERR2 +#undef CMP +#undef ELT +#undef LIM +} +#endif /* #if CHECKING_P */ + #ifndef GENERATOR_FILE #if CHECKING_P
Hello, I'm going to install the following patch on trunk in the next few hours. This revision doesn't offer per-callsite opt-out anymore as suggested by Richi on the Cauldron (made possible by fixing all known issues on trunk). Thus this patch has a few minor differences compared to the previous revision that was ack'ed by Jeff. Tested on x86_64-linux, i686-linux and ppc64le-linux. Alexander * 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.