* [PATCH 0/6] qsort comparator consistency fixes @ 2017-07-15 20:49 Alexander Monakov 2017-07-15 20:48 ` [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func Alexander Monakov ` (6 more replies) 0 siblings, 7 replies; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches 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 ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov @ 2017-07-15 20:48 ` Alexander Monakov 2017-07-19 6:50 ` Jeff Law 2017-07-15 20:49 ` [PATCH 6/6] qsort comparator consistency checking Alexander Monakov ` (5 subsequent siblings) 6 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:48 UTC (permalink / raw) To: gcc-patches This comparator lacks anti-commutativity and can indicate A < B < A if both A and B satisfy non_spilled_static_chain_regno_p. Proceed to following tie-breakers in that case. (it looks like the code incorrectly assumes that at most one register in the array will satisfy non_spilled_static_chain_regno_p) * lra-assigns.c (pseudo_compare_func): Fix comparison step based on non_spilled_static_chain_regno_p. --- gcc/lra-assigns.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c index 42556d3..2aadeef 100644 --- a/gcc/lra-assigns.c +++ b/gcc/lra-assigns.c @@ -253,10 +253,9 @@ pseudo_compare_func (const void *v1p, const void *v2p) /* Assign hard reg to static chain pointer first pseudo when non-local goto is used. */ - if (non_spilled_static_chain_regno_p (r1)) - return -1; - else if (non_spilled_static_chain_regno_p (r2)) - return 1; + if ((diff = (non_spilled_static_chain_regno_p (r2) + - non_spilled_static_chain_regno_p (r1))) != 0) + return diff; /* Prefer to assign more frequently used registers first. */ if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0) -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func 2017-07-15 20:48 ` [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func Alexander Monakov @ 2017-07-19 6:50 ` Jeff Law 0 siblings, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-07-19 6:50 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > This comparator lacks anti-commutativity and can indicate > A < B < A if both A and B satisfy non_spilled_static_chain_regno_p. > Proceed to following tie-breakers in that case. > > (it looks like the code incorrectly assumes that at most one register > in the array will satisfy non_spilled_static_chain_regno_p) > > * lra-assigns.c (pseudo_compare_func): Fix comparison step based on > non_spilled_static_chain_regno_p. OK. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 6/6] qsort comparator consistency checking 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov 2017-07-15 20:48 ` [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func Alexander Monakov @ 2017-07-15 20:49 ` Alexander Monakov 2017-07-31 18:06 ` Jeff Law 2017-08-02 17:29 ` Jeff Law 2017-07-15 20:49 ` [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator Alexander Monakov ` (4 subsequent siblings) 6 siblings, 2 replies; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches This is the updated qsort comparator verifier. Since we have vec::qsort(cmp), the patch uses the macro argument counting trick to redirect only the four-argument invocations of qsort to qsort_chk. I realize that won't win much sympathies, but a patch doing mass-renaming of qsort in the whole GCC codebase would win even fewer, I suspect. The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2) checking, but there's no accompanying configure.ac change. I'm not sure that would be useful in practice, so I'd rather turn it into #if 0. The suppression in genmodes was needed because it's not linked with vec.o. * genmodes.c (calc_wider_mode): Suppress qsort macro. * system.h [CHECKING_P] (qsort): Redirect to qsort_chk. (qsort_nochk): New macro. (qsort_chk): Declare. (qsort_disable_checking): Declare. * vec.c (qsort_chk_error): New static function. (qsort_disable_checking): Define. (qsort_chk): New function. --- gcc/genmodes.c | 2 +- gcc/system.h | 11 +++++++ gcc/vec.c | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 107 insertions(+), 1 deletion(-) diff --git a/gcc/genmodes.c b/gcc/genmodes.c index f7eaeef..01a0e65 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 b091794..0f44942 100644 --- a/gcc/system.h +++ b/gcc/system.h @@ -1170,4 +1170,15 @@ helper_const_non_const_cast (const char *p) /* Get definitions of HOST_WIDE_INT. */ #include "hwint.h" +/* qsort comparator consistency checking machinery. */ +#if CHECKING_P +/* Except in release-checking compilers, redirect 4-argument qsort calls. */ +#undef qsort +#define _5th(_1, _2, _3, _4, _5, ...) _5 +#define qsort(...) _5th (__VA_ARGS__, qsort_chk, 3, 2, qsort, 0) (__VA_ARGS__) +#endif +#define qsort_nochk (qsort) +void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *)); +extern unsigned qsort_disable_checking; + #endif /* ! GCC_SYSTEM_H */ diff --git a/gcc/vec.c b/gcc/vec.c index d612703..5d9f1e9 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 @@ -42,6 +48,95 @@ along with GCC; see the file COPYING3. If not see they cannot have ctors/dtors. */ vnull vNULL; +/* 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"); +} + +unsigned qsort_disable_checking; + +/* 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 *)) +{ + if (!CHECKING_P || qsort_disable_checking) + return (qsort) (base, n, size, cmp); + (qsort) (base, n, size, cmp); +#ifdef ENABLE_FULL_QSORT_CHECKING +#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 +} + /* Vector memory usage. */ struct vec_usage: public mem_usage { -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-07-15 20:49 ` [PATCH 6/6] qsort comparator consistency checking Alexander Monakov @ 2017-07-31 18:06 ` Jeff Law 2017-07-31 18:28 ` Alexander Monakov 2017-08-02 17:29 ` Jeff Law 1 sibling, 1 reply; 39+ messages in thread From: Jeff Law @ 2017-07-31 18:06 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > This is the updated qsort comparator verifier. > > Since we have vec::qsort(cmp), the patch uses the macro argument counting > trick to redirect only the four-argument invocations of qsort to qsort_chk. > I realize that won't win much sympathies, but a patch doing mass-renaming > of qsort in the whole GCC codebase would win even fewer, I suspect. > > The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2) > checking, but there's no accompanying configure.ac change. I'm not sure > that would be useful in practice, so I'd rather turn it into #if 0. > > The suppression in genmodes was needed because it's not linked with vec.o. > > * genmodes.c (calc_wider_mode): Suppress qsort macro. > * system.h [CHECKING_P] (qsort): Redirect to qsort_chk. > (qsort_nochk): New macro. > (qsort_chk): Declare. > (qsort_disable_checking): Declare. > * vec.c (qsort_chk_error): New static function. > (qsort_disable_checking): Define. > (qsort_chk): New function. I must have missed something. Can't you just define qsort (BASE, NMEMB, SIZE, COMPARE) into qsort_chk (BASE, NMEMB, SIZE, COMPARE) That shouldn't affect the qsort from vec? Right? Or am I missing something Jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-07-31 18:06 ` Jeff Law @ 2017-07-31 18:28 ` Alexander Monakov 2017-08-02 17:16 ` Jeff Law 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-31 18:28 UTC (permalink / raw) To: Jeff Law; +Cc: gcc-patches On Mon, 31 Jul 2017, Jeff Law wrote: > I must have missed something. Can't you just define > > qsort (BASE, NMEMB, SIZE, COMPARE) into > > qsort_chk (BASE, NMEMB, SIZE, COMPARE) > > That shouldn't affect the qsort from vec? Right? Or am I missing something If you do #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp) then all invocations of vec::qsort, i.e. myvec.qsort (mycmp); will yield a preprocessing error due to wrong number of arguments supplied to the qsort macro (one instead of four). Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-07-31 18:28 ` Alexander Monakov @ 2017-08-02 17:16 ` Jeff Law 0 siblings, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-08-02 17:16 UTC (permalink / raw) To: Alexander Monakov; +Cc: gcc-patches On 07/31/2017 12:27 PM, Alexander Monakov wrote: > On Mon, 31 Jul 2017, Jeff Law wrote: >> I must have missed something. Can't you just define >> >> qsort (BASE, NMEMB, SIZE, COMPARE) into >> >> qsort_chk (BASE, NMEMB, SIZE, COMPARE) >> >> That shouldn't affect the qsort from vec? Right? Or am I missing something > > If you do > > #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp) > > then all invocations of vec::qsort, i.e. > > myvec.qsort (mycmp); > > will yield a preprocessing error due to wrong number of arguments supplied > to the qsort macro (one instead of four). Duh. Hit me with a clue stick. I guess I have to get familiar with the macro argument counting trick :-) jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-07-15 20:49 ` [PATCH 6/6] qsort comparator consistency checking Alexander Monakov 2017-07-31 18:06 ` Jeff Law @ 2017-08-02 17:29 ` Jeff Law 2017-08-02 18:00 ` Alexander Monakov 1 sibling, 1 reply; 39+ messages in thread From: Jeff Law @ 2017-08-02 17:29 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > This is the updated qsort comparator verifier. > > Since we have vec::qsort(cmp), the patch uses the macro argument counting > trick to redirect only the four-argument invocations of qsort to qsort_chk. > I realize that won't win much sympathies, but a patch doing mass-renaming > of qsort in the whole GCC codebase would win even fewer, I suspect. > > The macro ENABLE_FULL_QSORT_CHECKING could be used to enable full O(n^2) > checking, but there's no accompanying configure.ac change. I'm not sure > that would be useful in practice, so I'd rather turn it into #if 0. > > The suppression in genmodes was needed because it's not linked with vec.o. > > * genmodes.c (calc_wider_mode): Suppress qsort macro. > * system.h [CHECKING_P] (qsort): Redirect to qsort_chk. > (qsort_nochk): New macro. > (qsort_chk): Declare. > (qsort_disable_checking): Declare. > * vec.c (qsort_chk_error): New static function. > (qsort_disable_checking): Define. > (qsort_chk): New function. Well, there's not *that* many qsort calls. My quick grep shows 94 and its a very mechanical change. Then a poison in system.h to ensure raw calls to qsort don't return. The counting trick is, well, ugly. There's also issues in that some compilers don't properly implement the C99 pre-processor standard properly (MSVC) and what happens when there's no arguments? While not likely an issue here, I think it highlights that this kind of preprocessor hackery is just a bad idea. I'd prefer to just bite the bullet and do the mechanical qsort change. Jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-02 17:29 ` Jeff Law @ 2017-08-02 18:00 ` Alexander Monakov 2017-08-02 18:08 ` Jeff Law 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-08-02 18:00 UTC (permalink / raw) To: Jeff Law; +Cc: gcc-patches On Wed, 2 Aug 2017, Jeff Law wrote: > Well, there's not *that* many qsort calls. My quick grep shows 94 and > its a very mechanical change. Then a poison in system.h to ensure raw > calls to qsort don't return. Any suggestion for the non-poisoned replacement? xqsort? gcc_qsort? Can you review the rest (the substantial functionality) of the patch without waiting for the mass-renaming change? Thanks. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-02 18:00 ` Alexander Monakov @ 2017-08-02 18:08 ` Jeff Law 2017-08-03 14:25 ` Alexander Monakov 0 siblings, 1 reply; 39+ messages in thread From: Jeff Law @ 2017-08-02 18:08 UTC (permalink / raw) To: Alexander Monakov; +Cc: gcc-patches On 08/02/2017 12:00 PM, Alexander Monakov wrote: > On Wed, 2 Aug 2017, Jeff Law wrote: >> Well, there's not *that* many qsort calls. My quick grep shows 94 and >> its a very mechanical change. Then a poison in system.h to ensure raw >> calls to qsort don't return. > > Any suggestion for the non-poisoned replacement? xqsort? gcc_qsort? qsort_chk/qsort_nochk for checked and non-checked? > > Can you review the rest (the substantial functionality) of the patch > without waiting for the mass-renaming change? I think the rest is good as-is. If we find a need to adjust the checking intervals, then we can do that as a follow-up. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-02 18:08 ` Jeff Law @ 2017-08-03 14:25 ` Alexander Monakov 2017-08-03 15:33 ` Jeff Law 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-08-03 14:25 UTC (permalink / raw) To: Jeff Law; +Cc: gcc-patches On Wed, 2 Aug 2017, Jeff Law wrote: > >> Well, there's not *that* many qsort calls. My quick grep shows 94 and > >> its a very mechanical change. Then a poison in system.h to ensure raw > >> calls to qsort don't return. Note that poisoning qsort outlaws vec::qsort too; it would need to be mass- renamed as well (to vec::sort, presumably). It seems there are 83 or more calls to vec::qsort. > > Any suggestion for the non-poisoned replacement? xqsort? gcc_qsort? > qsort_chk/qsort_nochk for checked and non-checked? I believe qsort_chk isn't appropriate, checking is not explicitly a part of interface, and we never use _chk in potentially-checking tree and RTL accessors either. Thanks. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 14:25 ` Alexander Monakov @ 2017-08-03 15:33 ` Jeff Law 2017-08-03 15:53 ` Jakub Jelinek 0 siblings, 1 reply; 39+ messages in thread From: Jeff Law @ 2017-08-03 15:33 UTC (permalink / raw) To: Alexander Monakov; +Cc: gcc-patches On 08/03/2017 08:24 AM, Alexander Monakov wrote: > On Wed, 2 Aug 2017, Jeff Law wrote: >>>> Well, there's not *that* many qsort calls. My quick grep shows 94 and >>>> its a very mechanical change. Then a poison in system.h to ensure raw >>>> calls to qsort don't return. > > Note that poisoning qsort outlaws vec::qsort too; it would need to be mass- > renamed as well (to vec::sort, presumably). It seems there are 83 or more > calls to vec::qsort. Ugh :( That's an unfortunate implementation of poisoning :( Consider a patch to rename those too pre-approved. > >>> Any suggestion for the non-poisoned replacement? xqsort? gcc_qsort? >> qsort_chk/qsort_nochk for checked and non-checked? > > I believe qsort_chk isn't appropriate, checking is not explicitly a part > of interface, and we never use _chk in potentially-checking tree and RTL > accessors either. How about just "sort"? Jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 15:33 ` Jeff Law @ 2017-08-03 15:53 ` Jakub Jelinek 2017-08-03 16:23 ` Alexander Monakov 2017-08-09 16:31 ` Jeff Law 0 siblings, 2 replies; 39+ messages in thread From: Jakub Jelinek @ 2017-08-03 15:53 UTC (permalink / raw) To: Jeff Law; +Cc: Alexander Monakov, gcc-patches On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote: > On 08/03/2017 08:24 AM, Alexander Monakov wrote: > > On Wed, 2 Aug 2017, Jeff Law wrote: > >>>> Well, there's not *that* many qsort calls. My quick grep shows 94 and > >>>> its a very mechanical change. Then a poison in system.h to ensure raw > >>>> calls to qsort don't return. > > > > Note that poisoning qsort outlaws vec::qsort too; it would need to be mass- > > renamed as well (to vec::sort, presumably). It seems there are 83 or more > > calls to vec::qsort. > Ugh :( That's an unfortunate implementation of poisoning :( Consider a > patch to rename those too pre-approved. Do we really need to rename and poison anything? qsort () in the source is something that is most obvious to developers, so trying to force them to use something different will just mean extra thing to learn. I mean, isn't it better to just add a static inline qsort that in the checking case calls qsort_chk, or do the redirection using GNU asm redirection: typeof (qsort) __asm ("qsort_chk"); and define extern "C" qsort_chk somewhere? configure could test whether it works on the target (it wouldn't perhaps on targets which already use some inline for qsort in their headers or use qsort as a macro (but the latter wouldn't work anyway with GCC already)). The _5th macro isn't that bad either, appart from using reserved namespace identifiers (it really should be something like qsort_5th and the arguments shouldn't start with underscores). Jakub ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 15:53 ` Jakub Jelinek @ 2017-08-03 16:23 ` Alexander Monakov 2017-08-03 16:27 ` Oleg Endo ` (3 more replies) 2017-08-09 16:31 ` Jeff Law 1 sibling, 4 replies; 39+ messages in thread From: Alexander Monakov @ 2017-08-03 16:23 UTC (permalink / raw) To: Jakub Jelinek; +Cc: Jeff Law, gcc-patches On Thu, 3 Aug 2017, Jakub Jelinek wrote: > Do we really need to rename and poison anything? qsort () in the source is > something that is most obvious to developers, so trying to force them to use > something different will just mean extra thing to learn. Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is. Note that with vec::qsort -> vec::sort renaming (which should be less controversial, STL also has std::vector<T>::sort), the argument counting trick won't be needed, the redirection will simply be: #undef qsort #define qsort(base, n, sz, cmp) qsort_chk (base, n, sz, cmp) > I mean, isn't it better to just add a static inline qsort that in the > checking case calls qsort_chk, (redefining qsort like that is formally UB, I'd like to avoid it) > or do the redirection using GNU asm redirection: > typeof (qsort) __asm ("qsort_chk"); > and define extern "C" qsort_chk somewhere? > configure could test whether it works on the target (it wouldn't perhaps > on targets which already use some inline for qsort in their headers or use > qsort as a macro (but the latter wouldn't work anyway with GCC already)). I'd rather not go this way. > The _5th macro isn't that bad either, appart from using reserved namespace > identifiers (it really should be something like qsort_5th and the arguments > shouldn't start with underscores). I didn't understand what Jeff found "ugly" about it; I wonder what epithets would be applied then to more, ahem, unusual parts of GCC. Thanks. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:23 ` Alexander Monakov @ 2017-08-03 16:27 ` Oleg Endo 2017-08-03 16:31 ` Alexander Monakov 2017-08-03 16:28 ` Jakub Jelinek ` (2 subsequent siblings) 3 siblings, 1 reply; 39+ messages in thread From: Oleg Endo @ 2017-08-03 16:27 UTC (permalink / raw) To: Alexander Monakov, Jakub Jelinek; +Cc: Jeff Law, gcc-patches On Thu, 2017-08-03 at 19:23 +0300, Alexander Monakov wrote: >Â > Note that with vec::qsort -> vec::sort renaming (which should be less > controversial, STL also has std::vector<T>::sort) No it doesn't? Â One uses std::sort from <algorithm> on a pair of random access iterators to sort a std::vector. Cheers, Oleg ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:27 ` Oleg Endo @ 2017-08-03 16:31 ` Alexander Monakov 2017-08-03 16:35 ` Oleg Endo 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-08-03 16:31 UTC (permalink / raw) To: Oleg Endo; +Cc: Jakub Jelinek, Jeff Law, gcc-patches [-- Attachment #1: Type: text/plain, Size: 379 bytes --] On Fri, 4 Aug 2017, Oleg Endo wrote: > > Note that with vec::qsort -> vec::sort renaming (which should be less > > controversial, STL also has std::vector<T>::sort) > > No it doesn't? Â One uses std::sort from <algorithm> on a pair of random > access iterators to sort a std::vector. My mistake, but the main point remains: STL uses 'sort' without the 'q'. Thanks. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:31 ` Alexander Monakov @ 2017-08-03 16:35 ` Oleg Endo 0 siblings, 0 replies; 39+ messages in thread From: Oleg Endo @ 2017-08-03 16:35 UTC (permalink / raw) To: Alexander Monakov; +Cc: Jakub Jelinek, Jeff Law, gcc-patches On Thu, 2017-08-03 at 19:31 +0300, Alexander Monakov wrote: >Â > My mistake, but the main point remains: STL uses 'sort' without the > 'q'. I think it'd be better if GCC's custom containers somewhat tried to follow C++ standard container idioms. Â Chopping off the 'q' is one step towards it. Cheers, Oleg ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:23 ` Alexander Monakov 2017-08-03 16:27 ` Oleg Endo @ 2017-08-03 16:28 ` Jakub Jelinek 2017-08-07 14:07 ` Pedro Alves 2017-08-09 16:35 ` Jeff Law 3 siblings, 0 replies; 39+ messages in thread From: Jakub Jelinek @ 2017-08-03 16:28 UTC (permalink / raw) To: Alexander Monakov; +Cc: Jeff Law, gcc-patches On Thu, Aug 03, 2017 at 07:23:31PM +0300, Alexander Monakov wrote: > On Thu, 3 Aug 2017, Jakub Jelinek wrote: > > Do we really need to rename and poison anything? qsort () in the source is > > something that is most obvious to developers, so trying to force them to use > > something different will just mean extra thing to learn. > > Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is. > > Note that with vec::qsort -> vec::sort renaming (which should be less > controversial, STL also has std::vector<T>::sort), the argument counting vec::qsort -> vec::sort renaming is fine with me. Jakub ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:23 ` Alexander Monakov 2017-08-03 16:27 ` Oleg Endo 2017-08-03 16:28 ` Jakub Jelinek @ 2017-08-07 14:07 ` Pedro Alves 2017-08-09 16:35 ` Jeff Law 3 siblings, 0 replies; 39+ messages in thread From: Pedro Alves @ 2017-08-07 14:07 UTC (permalink / raw) To: Alexander Monakov, Jakub Jelinek; +Cc: Jeff Law, gcc-patches On 08/03/2017 05:23 PM, Alexander Monakov wrote: > Note that with vec::qsort -> vec::sort renaming (which should be less > controversial, STL also has std::vector<T>::sort), the argument counting > trick won't be needed, the redirection will simply be: OTOH, std::sort's comparison function callback has a different interface from qsort's. std::sort wants less-than true/false, while qsort wants -1/0/1. Might be less confusing to leave "sort" for a method that follows std::sort's interface. You could also consider using std::sort, btw. I don't think there's a reason it can't work with vec. Since std::sort is a template, the inlining + indirection avoidance often results in faster sorts (potentially at the expense of compile time). Consistency checking could be implemented by adding a a gcc::sort wrapper around std::sort (and calling the former throughout). Thanks, Pedro Alves ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 16:23 ` Alexander Monakov ` (2 preceding siblings ...) 2017-08-07 14:07 ` Pedro Alves @ 2017-08-09 16:35 ` Jeff Law 2017-08-10 13:35 ` Alexander Monakov 3 siblings, 1 reply; 39+ messages in thread From: Jeff Law @ 2017-08-09 16:35 UTC (permalink / raw) To: Alexander Monakov, Jakub Jelinek; +Cc: gcc-patches On 08/03/2017 10:23 AM, Alexander Monakov wrote: > On Thu, 3 Aug 2017, Jakub Jelinek wrote: >> Do we really need to rename and poison anything? qsort () in the source is >> something that is most obvious to developers, so trying to force them to use >> something different will just mean extra thing to learn. > > Yep, I'd prefer to have a solution that keeps C-style qsort invocations as-is. Revisiting, I'm in agreement with you. > >> The _5th macro isn't that bad either, appart from using reserved namespace >> identifiers (it really should be something like qsort_5th and the arguments >> shouldn't start with underscores). > > I didn't understand what Jeff found "ugly" about it; I wonder what epithets > would be applied then to more, ahem, unusual parts of GCC. I doubt anyone would want to hear what I might say about other code. I'm sure I wouldn't want my kids reading how I might refer to certain parts of GCC. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-09 16:35 ` Jeff Law @ 2017-08-10 13:35 ` Alexander Monakov 2017-08-24 6:27 ` Jeff Law 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-08-10 13:35 UTC (permalink / raw) To: Jeff Law; +Cc: Jakub Jelinek, gcc-patches On Wed, 9 Aug 2017, Jeff Law wrote: > >> The _5th macro isn't that bad either, appart from using reserved namespace > >> identifiers (it really should be something like qsort_5th and the arguments > >> shouldn't start with underscores). > > > > I didn't understand what Jeff found "ugly" about it; I wonder what epithets > > would be applied then to more, ahem, unusual parts of GCC. > I doubt anyone would want to hear what I might say about other code. > I'm sure I wouldn't want my kids reading how I might refer to certain > parts of GCC. Imho it's no good to just say "ugly" in patch review without any further elaboration, it only serves to provide a minor chilling effect, telling the contributor they haven't done good enough (for your personal taste) without informing them where/how they could have improved. More importantly, am I correct in understanding that at this point all remaining changes are reviewed and approved, and I can go ahead with preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the others on top of it? Or is the original approach with argument-counting trick still under consideration? Thanks. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-10 13:35 ` Alexander Monakov @ 2017-08-24 6:27 ` Jeff Law 0 siblings, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-08-24 6:27 UTC (permalink / raw) To: Alexander Monakov; +Cc: Jakub Jelinek, gcc-patches On 08/10/2017 05:24 AM, Alexander Monakov wrote: > On Wed, 9 Aug 2017, Jeff Law wrote: >>>> The _5th macro isn't that bad either, appart from using reserved namespace >>>> identifiers (it really should be something like qsort_5th and the arguments >>>> shouldn't start with underscores). >>> >>> I didn't understand what Jeff found "ugly" about it; I wonder what epithets >>> would be applied then to more, ahem, unusual parts of GCC. >> I doubt anyone would want to hear what I might say about other code. >> I'm sure I wouldn't want my kids reading how I might refer to certain >> parts of GCC. > > Imho it's no good to just say "ugly" in patch review without any further > elaboration, it only serves to provide a minor chilling effect, telling > the contributor they haven't done good enough (for your personal taste) > without informing them where/how they could have improved. > > More importantly, am I correct in understanding that at this point all > remaining changes are reviewed and approved, and I can go ahead with > preparing vec::qsort -> vec::sort mass-renaming patch and rebasing the > others on top of it? Or is the original approach with argument-counting > trick still under consideration? I still don't like the argument-counting trick. But avoiding it seems even more painful. So let's go with your original approach with the argument-counting trick. At least it's buried and folks likely won't have to look at it with any regularity. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 6/6] qsort comparator consistency checking 2017-08-03 15:53 ` Jakub Jelinek 2017-08-03 16:23 ` Alexander Monakov @ 2017-08-09 16:31 ` Jeff Law 1 sibling, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-08-09 16:31 UTC (permalink / raw) To: Jakub Jelinek; +Cc: Alexander Monakov, gcc-patches On 08/03/2017 09:52 AM, Jakub Jelinek wrote: > On Thu, Aug 03, 2017 at 09:33:13AM -0600, Jeff Law wrote: >> On 08/03/2017 08:24 AM, Alexander Monakov wrote: >>> On Wed, 2 Aug 2017, Jeff Law wrote: >>>>>> Well, there's not *that* many qsort calls. My quick grep shows 94 and >>>>>> its a very mechanical change. Then a poison in system.h to ensure raw >>>>>> calls to qsort don't return. >>> >>> Note that poisoning qsort outlaws vec::qsort too; it would need to be mass- >>> renamed as well (to vec::sort, presumably). It seems there are 83 or more >>> calls to vec::qsort. >> Ugh :( That's an unfortunate implementation of poisoning :( Consider a >> patch to rename those too pre-approved. > > Do we really need to rename and poison anything? qsort () in the source is > something that is most obvious to developers, so trying to force them to use > something different will just mean extra thing to learn. Thinking about this again, you're probably right. I failed to distinguish between this case and something like malloc. For qsort, if we're using the numbering hack, introduction of a new qsort call will result in a qsort call that is properly checked. In contrast we simply don't want folks calling malloc & friends directly under any circumstances. Sorry for taking everyone down a bogus path here. Jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov 2017-07-15 20:48 ` [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func Alexander Monakov 2017-07-15 20:49 ` [PATCH 6/6] qsort comparator consistency checking Alexander Monakov @ 2017-07-15 20:49 ` Alexander Monakov 2017-07-19 6:51 ` Jeff Law 2017-07-15 20:49 ` [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills Alexander Monakov ` (3 subsequent siblings) 6 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches Subtracting values to produce a -/0/+ comparison value only works when original values have limited range. Otherwise it leads to broken comparator that indicates 0 < 0x40000000 < 0x80000000 < 0. Yuri posted an equivalent patch just a few hours ago: https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00882.html * tree-vrp.c (compare_assert_loc): Properly compare hash values. --- gcc/tree-vrp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 28205f1..d1888f6 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -6459,7 +6459,7 @@ compare_assert_loc (const void *pa, const void *pb) return (a->e != NULL ? a->e->src->index - b->e->src->index : a->bb->index - b->bb->index); - return ha - hb; + return ha < hb ? -1 : 1; } /* Process all the insertions registered for every name N_i registered -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator 2017-07-15 20:49 ` [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator Alexander Monakov @ 2017-07-19 6:51 ` Jeff Law 0 siblings, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-07-19 6:51 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > Subtracting values to produce a -/0/+ comparison value only works when > original values have limited range. Otherwise it leads to broken > comparator that indicates 0 < 0x40000000 < 0x80000000 < 0. > > Yuri posted an equivalent patch just a few hours ago: > https://gcc.gnu.org/ml/gcc-patches/2017-07/msg00882.html > > * tree-vrp.c (compare_assert_loc): Properly compare hash values. Richi already ack'd Yuri's version, so let's stick with that. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov ` (2 preceding siblings ...) 2017-07-15 20:49 ` [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator Alexander Monakov @ 2017-07-15 20:49 ` Alexander Monakov 2017-07-18 19:51 ` Yuri Gribov 2017-07-31 17:42 ` Jeff Law 2017-07-15 20:49 ` [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos Alexander Monakov ` (2 subsequent siblings) 6 siblings, 2 replies; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches The reload_pseudo_compare_func comparator, when used from assign_by_spills, can be non-transitive, indicating A < B < C < A if both A and C satisfy !bitmap_bit_p (&non_reload_pseudos, rAC), but B does not. This function was originally a proper comparator, and the problematic clause was added to fix PR 57878: https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html That the comparator is invalid implies that that PR, if it still exists, can reappear (but probably under more complicated circumstances). This looks like a sensitive area, so disabling checking is the only obvious approach. * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME. (assign_by_spills): Use non-checking qsort. --- gcc/lra-assigns.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c index 2aadeef..a67d1a6 100644 --- a/gcc/lra-assigns.c +++ b/gcc/lra-assigns.c @@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void *v2p) /* The code below executes rarely as nregs == 1 in most cases. So we should not worry about using faster data structures to check reload pseudos. */ + /* FIXME this makes comparator non-transitive and thus invalid. */ && ! bitmap_bit_p (&non_reload_pseudos, r1) && ! bitmap_bit_p (&non_reload_pseudos, r2)) return diff; @@ -1384,7 +1385,7 @@ assign_by_spills (void) bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos); for (iter = 0; iter <= 1; iter++) { - qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); + qsort_nochk (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); nfails = 0; for (i = 0; i < n; i++) { -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills 2017-07-15 20:49 ` [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills Alexander Monakov @ 2017-07-18 19:51 ` Yuri Gribov 2017-07-31 17:42 ` Jeff Law 1 sibling, 0 replies; 39+ messages in thread From: Yuri Gribov @ 2017-07-18 19:51 UTC (permalink / raw) To: Alexander Monakov; +Cc: GCC Patches On Sat, Jul 15, 2017 at 9:47 PM, Alexander Monakov <amonakov@ispras.ru> wrote: > The reload_pseudo_compare_func comparator, when used from assign_by_spills, > can be non-transitive, indicating A < B < C < A if both A and C satisfy > !bitmap_bit_p (&non_reload_pseudos, rAC), but B does not. > > This function was originally a proper comparator, and the problematic > clause was added to fix PR 57878: > https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html > > That the comparator is invalid implies that that PR, if it still exists, > can reappear (but probably under more complicated circumstances). > > This looks like a sensitive area, so disabling checking is the only > obvious approach. May make sense to add PR rtl-optimization/68988 annotation to changelog. > * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME. > (assign_by_spills): Use non-checking qsort. > --- > gcc/lra-assigns.c | 3 ++- > 1 file changed, 2 insertions(+), 1 deletion(-) > > diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c > index 2aadeef..a67d1a6 100644 > --- a/gcc/lra-assigns.c > +++ b/gcc/lra-assigns.c > @@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void *v2p) > /* The code below executes rarely as nregs == 1 in most cases. > So we should not worry about using faster data structures to > check reload pseudos. */ > + /* FIXME this makes comparator non-transitive and thus invalid. */ > && ! bitmap_bit_p (&non_reload_pseudos, r1) > && ! bitmap_bit_p (&non_reload_pseudos, r2)) > return diff; > @@ -1384,7 +1385,7 @@ assign_by_spills (void) > bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos); > for (iter = 0; iter <= 1; iter++) > { > - qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); > + qsort_nochk (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func); > nfails = 0; > for (i = 0; i < n; i++) > { > -- > 1.8.3.1 > ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills 2017-07-15 20:49 ` [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills Alexander Monakov 2017-07-18 19:51 ` Yuri Gribov @ 2017-07-31 17:42 ` Jeff Law 1 sibling, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-07-31 17:42 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > The reload_pseudo_compare_func comparator, when used from assign_by_spills, > can be non-transitive, indicating A < B < C < A if both A and C satisfy > !bitmap_bit_p (&non_reload_pseudos, rAC), but B does not. > > This function was originally a proper comparator, and the problematic > clause was added to fix PR 57878: > https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html > > That the comparator is invalid implies that that PR, if it still exists, > can reappear (but probably under more complicated circumstances). > > This looks like a sensitive area, so disabling checking is the only > obvious approach. > > * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME. > (assign_by_spills): Use non-checking qsort. This is OK once the final comparator consistency checking patch is approved. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov ` (3 preceding siblings ...) 2017-07-15 20:49 ` [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills Alexander Monakov @ 2017-07-15 20:49 ` Alexander Monakov 2017-07-19 6:50 ` Jeff Law 2017-07-22 11:15 ` Segher Boessenkool 2017-07-15 20:49 ` [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use Alexander Monakov 2017-07-21 14:30 ` [PATCH 7/6] fortran: fix pair_cmp qsort comparator Alexander Monakov 6 siblings, 2 replies; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches This qsort comparator lacks anti-commutativity and can indicate A < B < A if A and B have the same bitpos. Return 0 in that case. * gimple-ssa-store-merging.c (sort_by_bitpos): Return 0 on equal bitpos. --- gcc/gimple-ssa-store-merging.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/gcc/gimple-ssa-store-merging.c b/gcc/gimple-ssa-store-merging.c index 64b8351..c99960b 100644 --- a/gcc/gimple-ssa-store-merging.c +++ b/gcc/gimple-ssa-store-merging.c @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) store_immediate_info *const *tmp = (store_immediate_info * const *) x; store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; - if ((*tmp)->bitpos <= (*tmp2)->bitpos) + if ((*tmp)->bitpos < (*tmp2)->bitpos) return -1; else if ((*tmp)->bitpos > (*tmp2)->bitpos) return 1; - - gcc_unreachable (); + else + return 0; } /* Sorting function for store_immediate_info objects. -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-15 20:49 ` [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos Alexander Monakov @ 2017-07-19 6:50 ` Jeff Law 2017-07-22 11:15 ` Segher Boessenkool 1 sibling, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-07-19 6:50 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > This qsort comparator lacks anti-commutativity and can indicate > A < B < A if A and B have the same bitpos. Return 0 in that case. > > * gimple-ssa-store-merging.c (sort_by_bitpos): Return 0 on equal bitpos. OK. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-15 20:49 ` [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos Alexander Monakov 2017-07-19 6:50 ` Jeff Law @ 2017-07-22 11:15 ` Segher Boessenkool 2017-07-24 20:49 ` Alexander Monakov 1 sibling, 1 reply; 39+ messages in thread From: Segher Boessenkool @ 2017-07-22 11:15 UTC (permalink / raw) To: Alexander Monakov; +Cc: gcc-patches On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: > --- a/gcc/gimple-ssa-store-merging.c > +++ b/gcc/gimple-ssa-store-merging.c > @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) > store_immediate_info *const *tmp = (store_immediate_info * const *) x; > store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; > > - if ((*tmp)->bitpos <= (*tmp2)->bitpos) > + if ((*tmp)->bitpos < (*tmp2)->bitpos) > return -1; > else if ((*tmp)->bitpos > (*tmp2)->bitpos) > return 1; > - > - gcc_unreachable (); > + else > + return 0; > } Does any sort using this comparison function require the sort to be stable? It looks like the <= was simply a typo and should have been <, but the gcc_unreachable was as intended? (With <= it is trivially unreachable there). Segher ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-22 11:15 ` Segher Boessenkool @ 2017-07-24 20:49 ` Alexander Monakov 2017-07-25 8:34 ` Kyrill Tkachov 0 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-24 20:49 UTC (permalink / raw) To: Segher Boessenkool; +Cc: gcc-patches, Kyrill Tkachov On Sat, 22 Jul 2017, Segher Boessenkool wrote: > On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: > > --- a/gcc/gimple-ssa-store-merging.c > > +++ b/gcc/gimple-ssa-store-merging.c > > @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) > > store_immediate_info *const *tmp = (store_immediate_info * const *) x; > > store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; > > > > - if ((*tmp)->bitpos <= (*tmp2)->bitpos) > > + if ((*tmp)->bitpos < (*tmp2)->bitpos) > > return -1; > > else if ((*tmp)->bitpos > (*tmp2)->bitpos) > > return 1; > > - > > - gcc_unreachable (); > > + else > > + return 0; > > } > > Does any sort using this comparison function require the sort to be > stable? > > It looks like the <= was simply a typo and should have been <, but > the gcc_unreachable was as intended? (With <= it is trivially > unreachable there). I think it's best if the original author can chime in - adding Kyrill. (to be clear, equal bitpos is possible, this issue causes qsort checker errors) Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-24 20:49 ` Alexander Monakov @ 2017-07-25 8:34 ` Kyrill Tkachov 2017-07-25 8:47 ` Richard Biener 2017-07-25 16:03 ` Alexander Monakov 0 siblings, 2 replies; 39+ messages in thread From: Kyrill Tkachov @ 2017-07-25 8:34 UTC (permalink / raw) To: Alexander Monakov, Segher Boessenkool; +Cc: gcc-patches Hi, On 24/07/17 21:48, Alexander Monakov wrote: > On Sat, 22 Jul 2017, Segher Boessenkool wrote: > >> On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: >>> --- a/gcc/gimple-ssa-store-merging.c >>> +++ b/gcc/gimple-ssa-store-merging.c >>> @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) >>> store_immediate_info *const *tmp = (store_immediate_info * const *) x; >>> store_immediate_info *const *tmp2 = (store_immediate_info * const *) y; >>> >>> - if ((*tmp)->bitpos <= (*tmp2)->bitpos) >>> + if ((*tmp)->bitpos < (*tmp2)->bitpos) >>> return -1; >>> else if ((*tmp)->bitpos > (*tmp2)->bitpos) >>> return 1; >>> - >>> - gcc_unreachable (); >>> + else >>> + return 0; >>> } >> Does any sort using this comparison function require the sort to be >> stable? >> >> It looks like the <= was simply a typo and should have been <, but >> the gcc_unreachable was as intended? (With <= it is trivially >> unreachable there). > I think it's best if the original author can chime in - adding Kyrill. > > (to be clear, equal bitpos is possible, this issue causes qsort checker errors) For the uses of this function the order when the bitpos is the same does not matter, I just wanted to avoid returning zero to avoid perturbations due to qsort. IMO the right thing to do here to avoid the qsort checker errors is to break the tie between store_immediate_info objects with equal bitpos by using the sort_by_order heuristic i.e. something like "return (*tmp)->order - (*tmp2)->order;". That should give well-behaved results as the order of two store_immediate_info objects is guaranteed not to be the same (otherwise something has gone wrong elsewhere). Thanks, Kyrill > Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-25 8:34 ` Kyrill Tkachov @ 2017-07-25 8:47 ` Richard Biener 2017-07-25 16:03 ` Alexander Monakov 1 sibling, 0 replies; 39+ messages in thread From: Richard Biener @ 2017-07-25 8:47 UTC (permalink / raw) To: Kyrill Tkachov; +Cc: Alexander Monakov, Segher Boessenkool, GCC Patches On Tue, Jul 25, 2017 at 10:34 AM, Kyrill Tkachov <kyrylo.tkachov@foss.arm.com> wrote: > Hi, > > On 24/07/17 21:48, Alexander Monakov wrote: >> >> On Sat, 22 Jul 2017, Segher Boessenkool wrote: >> >>> On Sat, Jul 15, 2017 at 11:47:45PM +0300, Alexander Monakov wrote: >>>> >>>> --- a/gcc/gimple-ssa-store-merging.c >>>> +++ b/gcc/gimple-ssa-store-merging.c >>>> @@ -516,12 +516,12 @@ sort_by_bitpos (const void *x, const void *y) >>>> store_immediate_info *const *tmp = (store_immediate_info * const *) >>>> x; >>>> store_immediate_info *const *tmp2 = (store_immediate_info * const *) >>>> y; >>>> - if ((*tmp)->bitpos <= (*tmp2)->bitpos) >>>> + if ((*tmp)->bitpos < (*tmp2)->bitpos) >>>> return -1; >>>> else if ((*tmp)->bitpos > (*tmp2)->bitpos) >>>> return 1; >>>> - >>>> - gcc_unreachable (); >>>> + else >>>> + return 0; >>>> } >>> >>> Does any sort using this comparison function require the sort to be >>> stable? >>> >>> It looks like the <= was simply a typo and should have been <, but >>> the gcc_unreachable was as intended? (With <= it is trivially >>> unreachable there). >> >> I think it's best if the original author can chime in - adding Kyrill. >> >> (to be clear, equal bitpos is possible, this issue causes qsort checker >> errors) > > > For the uses of this function the order when the bitpos is the same > does not matter, I just wanted to avoid returning zero to avoid > perturbations > due to qsort. > IMO the right thing to do here to avoid the qsort checker errors is to break > the tie between > store_immediate_info objects with equal bitpos by using the sort_by_order > heuristic > i.e. something like "return (*tmp)->order - (*tmp2)->order;". > That should give well-behaved results as the order of two > store_immediate_info objects > is guaranteed not to be the same (otherwise something has gone wrong > elsewhere). Agreed. Richard. > Thanks, > Kyrill > >> Alexander > > ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos 2017-07-25 8:34 ` Kyrill Tkachov 2017-07-25 8:47 ` Richard Biener @ 2017-07-25 16:03 ` Alexander Monakov 1 sibling, 0 replies; 39+ messages in thread From: Alexander Monakov @ 2017-07-25 16:03 UTC (permalink / raw) To: Kyrill Tkachov; +Cc: Segher Boessenkool, gcc-patches On Tue, 25 Jul 2017, Kyrill Tkachov wrote: > For the uses of this function the order when the bitpos is the same > does not matter, I just wanted to avoid returning zero to avoid perturbations > due to qsort. But you can't stabilize qsort in that manner, in fact by making the comparator invalid you achieve the opposite: making the output unpredictable, even with respect to elements with different bitpos. > IMO the right thing to do here to avoid the qsort checker errors is to break > the tie between store_immediate_info objects with equal bitpos by using the > sort_by_order heuristic i.e. something like "return (*tmp)->order - > (*tmp2)->order;". That should give well-behaved results as the order of two > store_immediate_info objects is guaranteed not to be the same (otherwise > something has gone wrong elsewhere). Note that my patch in this subthread has been applied already, please submit a separate patch if you want to add this stabilizing clause. Alexander ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov ` (4 preceding siblings ...) 2017-07-15 20:49 ` [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos Alexander Monakov @ 2017-07-15 20:49 ` Alexander Monakov 2017-07-31 17:44 ` Jeff Law 2017-07-21 14:30 ` [PATCH 7/6] fortran: fix pair_cmp qsort comparator Alexander Monakov 6 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-15 20:49 UTC (permalink / raw) To: gcc-patches The autopref_rank_for_schedule sub-comparator and its subroutine autopref_rank_data lack transitivity. Skip checking if they are in use. This heuristic is disabled by default everywhere except ARM and AArch64, so on other targets this does not suppress checking all the time. * haifa-sched.c (ready_sort_real): Disable qsort checking if autoprefetch heuristic will be used. (autopref_rank_for_schedule): Add FIXME. --- gcc/haifa-sched.c | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index af0ed27..71ad3c4 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -3081,11 +3081,18 @@ ready_sort_real (struct ready_list *ready) if (sched_verbose >= 4) stats1 = rank_for_schedule_stats; + /* autopref_rank_for_schedule lacks transitivity. */ + if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0) + qsort_disable_checking |= 1; + if (n_ready_real == 2) swap_sort (first, n_ready_real); else if (n_ready_real > 2) qsort (first, n_ready_real, sizeof (rtx), rank_for_schedule); + if (PARAM_VALUE (PARAM_SCHED_AUTOPREF_QUEUE_DEPTH) >= 0) + qsort_disable_checking &= ~1; + if (sched_verbose >= 4) { rank_for_schedule_stats_diff (&stats1, &rank_for_schedule_stats); @@ -5704,6 +5711,7 @@ autopref_rank_data (autopref_multipass_data_t data1, } /* Helper function for rank_for_schedule sorting. */ +/* FIXME: this comparator lacks transitivity and is thus invalid for qsort. */ static int autopref_rank_for_schedule (const rtx_insn *insn1, const rtx_insn *insn2) { -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use 2017-07-15 20:49 ` [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use Alexander Monakov @ 2017-07-31 17:44 ` Jeff Law 0 siblings, 0 replies; 39+ messages in thread From: Jeff Law @ 2017-07-31 17:44 UTC (permalink / raw) To: Alexander Monakov, gcc-patches On 07/15/2017 02:47 PM, Alexander Monakov wrote: > The autopref_rank_for_schedule sub-comparator and its subroutine > autopref_rank_data lack transitivity. Skip checking if they are in use. > > This heuristic is disabled by default everywhere except ARM and AArch64, > so on other targets this does not suppress checking all the time. > > * haifa-sched.c (ready_sort_real): Disable qsort checking if > autoprefetch heuristic will be used. > (autopref_rank_for_schedule): Add FIXME. This is also OK once the final patch for consistency checking is approved. jeff ^ permalink raw reply [flat|nested] 39+ messages in thread
* [PATCH 7/6] fortran: fix pair_cmp qsort comparator 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov ` (5 preceding siblings ...) 2017-07-15 20:49 ` [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use Alexander Monakov @ 2017-07-21 14:30 ` Alexander Monakov 2017-07-23 11:39 ` Thomas Koenig 6 siblings, 1 reply; 39+ messages in thread From: Alexander Monakov @ 2017-07-21 14:30 UTC (permalink / raw) To: fortran, gcc-patches Hello, The final tie-breaker in pair_cmp comparator looks strange, it correctly yields zero for equal expr->symtree-n.sym values, but for unequal values it produces 0 or 1. This would be correct for C++ STL-style comparators that require "less-than" predicate to be computed, but not for C qsort. The comment before the function seems to confirm that the intent was to indeed sort in ascending gfc_symbol order, but the code is doing mostly the opposite. Make the comparator properly anti-commutative by returning -1 in the last tie-breaker when appropriate. Bootstrapped and regtested on x86-64, OK for trunk? * interface.c (pair_cmp): Fix gfc_symbol comparison. Adjust comment. --- gcc/fortran/interface.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/gcc/fortran/interface.c b/gcc/fortran/interface.c index 6fe0647..13e2bdd 100644 --- a/gcc/fortran/interface.c +++ b/gcc/fortran/interface.c @@ -3294,7 +3294,7 @@ argpair; order: - p->a->expr == NULL - p->a->expr->expr_type != EXPR_VARIABLE - - growing p->a->expr->symbol. */ + - by gfc_symbol pointer value (larger first). */ static int pair_cmp (const void *p1, const void *p2) @@ -3320,6 +3320,8 @@ pair_cmp (const void *p1, const void *p2) } if (a2->expr->expr_type != EXPR_VARIABLE) return 1; + if (a1->expr->symtree->n.sym > a2->expr->symtree->n.sym) + return -1; return a1->expr->symtree->n.sym < a2->expr->symtree->n.sym; } -- 1.8.3.1 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [PATCH 7/6] fortran: fix pair_cmp qsort comparator 2017-07-21 14:30 ` [PATCH 7/6] fortran: fix pair_cmp qsort comparator Alexander Monakov @ 2017-07-23 11:39 ` Thomas Koenig 0 siblings, 0 replies; 39+ messages in thread From: Thomas Koenig @ 2017-07-23 11:39 UTC (permalink / raw) To: Alexander Monakov, fortran, gcc-patches Am 21.07.2017 um 16:29 schrieb Alexander Monakov: > Bootstrapped and regtested on x86-64, OK for trunk? > > * interface.c (pair_cmp): Fix gfc_symbol comparison. Adjust comment. OK. Thanks for the patch! Regards Thomas ^ permalink raw reply [flat|nested] 39+ messages in thread
end of thread, other threads:[~2017-08-24 6:15 UTC | newest] Thread overview: 39+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-07-15 20:49 [PATCH 0/6] qsort comparator consistency fixes Alexander Monakov 2017-07-15 20:48 ` [PATCH 3/6] lra-assigns.c: fix pseudo_compare_func Alexander Monakov 2017-07-19 6:50 ` Jeff Law 2017-07-15 20:49 ` [PATCH 6/6] qsort comparator consistency checking Alexander Monakov 2017-07-31 18:06 ` Jeff Law 2017-07-31 18:28 ` Alexander Monakov 2017-08-02 17:16 ` Jeff Law 2017-08-02 17:29 ` Jeff Law 2017-08-02 18:00 ` Alexander Monakov 2017-08-02 18:08 ` Jeff Law 2017-08-03 14:25 ` Alexander Monakov 2017-08-03 15:33 ` Jeff Law 2017-08-03 15:53 ` Jakub Jelinek 2017-08-03 16:23 ` Alexander Monakov 2017-08-03 16:27 ` Oleg Endo 2017-08-03 16:31 ` Alexander Monakov 2017-08-03 16:35 ` Oleg Endo 2017-08-03 16:28 ` Jakub Jelinek 2017-08-07 14:07 ` Pedro Alves 2017-08-09 16:35 ` Jeff Law 2017-08-10 13:35 ` Alexander Monakov 2017-08-24 6:27 ` Jeff Law 2017-08-09 16:31 ` Jeff Law 2017-07-15 20:49 ` [PATCH 1/6] tree-vrp: fix compare_assert_loc qsort comparator Alexander Monakov 2017-07-19 6:51 ` Jeff Law 2017-07-15 20:49 ` [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills Alexander Monakov 2017-07-18 19:51 ` Yuri Gribov 2017-07-31 17:42 ` Jeff Law 2017-07-15 20:49 ` [PATCH 2/6] gimple-ssa-store-merging.c: fix sort_by_bitpos Alexander Monakov 2017-07-19 6:50 ` Jeff Law 2017-07-22 11:15 ` Segher Boessenkool 2017-07-24 20:49 ` Alexander Monakov 2017-07-25 8:34 ` Kyrill Tkachov 2017-07-25 8:47 ` Richard Biener 2017-07-25 16:03 ` Alexander Monakov 2017-07-15 20:49 ` [PATCH 5/6] haifa-sched.c: give up qsort checking when autoprefetch heuristic is in use Alexander Monakov 2017-07-31 17:44 ` Jeff Law 2017-07-21 14:30 ` [PATCH 7/6] fortran: fix pair_cmp qsort comparator Alexander Monakov 2017-07-23 11:39 ` Thomas Koenig
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).