On Fri, Jul 15, 2016 at 6:00 PM, Alexander Monakov <amona...@ispras.ru> wrote:
> Hi,
>
> this patch adds internal checking for comparator functions that GCC passes to
> qsort. PR71702 describes an ICE that happens because comparator
> 'dr_group_sort_cmp' used to be non-transitive in some cases until GCC 6. This
> patch would uncover that issue on a number of small testcases in GCC's
> testsuite, so it should be useful to catch similar issues in the future as
> well.
>
> Although the meat of the implementation is not tied to vec<>, this patch adds
> verification only to vec::qsort. I see there's a number of other ::qsort uses
> in GCC; it should be useful to have such checking there as well. I'd
> appreciate
> input on that (I'd go with '#define qsort(b, n, s, c) qsort_chk (b, n, s, c)'
> in system.h and implement qsort_chk as a checking wrapper around libc qsort).
>
> Bootstrapped and regtested on x86_64, OK to apply?
Ugh. What impact does this have on stage2 compile-time?
Richard.
> Alexander
>
> * vec.c (vec_check_sort_cmp): New. Use it...
> * vec.h (vec<T, A, vl_embed>::qsort): ...here to verify comparator
> consistency when checking is enabled.
>
> diff --git a/gcc/vec.c b/gcc/vec.c
> index fd200ea..b4ac0b4 100644
> --- a/gcc/vec.c
> +++ b/gcc/vec.c
> @@ -190,6 +190,44 @@ dump_vec_loc_statistics (void)
> vec_mem_desc.dump (VEC_ORIGIN);
> }
>
> +/* Verify consistency of comparator CMP on array BASE of N SIZE-sized
> elements.
> + Assuming the array should be sorted according to CMP, any assertion
> failure
> + here implies that CMP is not transitive, or is not anti-commutative. */
> +
> +void
> +vec_check_sort_cmp (const void *base, size_t n, size_t size,
> + int (*cmp) (const void *, const void *))
> +{
> + const char *cbase = (const char *) base;
> + size_t i1, i2, i, j;
> + /* The following loop nest has O(n^2) time complexity. Limit n to avoid
> + slowness on artificial testcases. */
> + if (n > 100)
> + n = 100;
> +#define CMP(i, j) cmp (cbase + (i) * size, cbase + (j) * size)
> + /* The outer loop iterates over maximum spans [i1, i2) such that elements
> + within each span compare equal. */
> + for (i1 = 0; i1 < n; i1 = i2)
> + {
> + /* Position i2 past the last element that compares equal to i1'th. */
> + for (i2 = i1 + 1; i2 < n; i2++)
> + if (CMP (i1, i2))
> + break;
> + else
> + gcc_assert (!CMP (i2, i1));
> + /* Verify that all remaining pairs within current span compare equal.
> */
> + for (i = i1 + 1; i + 1 < i2; i++)
> + for (j = i + 1; j < i2; j++)
> + gcc_assert (!CMP (i, j) && !CMP (j, i));
> + /* Verify that all elements within current span compare less than any
> + element beyond the span. */
> + for (i = i1; i < i2; i++)
> + for (j = i2; j < n; j++)
> + gcc_assert (CMP (i, j) < 0 && CMP (j, i) > 0);
> + }
> +#undef CMP
> +}
> +
> #ifndef GENERATOR_FILE
> #if CHECKING_P
>
> diff --git a/gcc/vec.h b/gcc/vec.h
> index eb8c270..ff1e37e 100644
> --- a/gcc/vec.h
> +++ b/gcc/vec.h
> @@ -182,6 +182,9 @@ extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
> /* Support function for statistics. */
> extern void dump_vec_loc_statistics (void);
>
> +extern void vec_check_sort_cmp (const void *, size_t, size_t,
> + int (*) (const void *, const void *));
> +
> /* Hashtable mapping vec addresses to descriptors. */
> extern htab_t vec_mem_usage_hash;
>
> @@ -947,8 +950,11 @@ template<typename T, typename A>
> inline void
> vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
> {
> - if (length () > 1)
> - ::qsort (address (), length (), sizeof (T), cmp);
> + if (length () <= 1)
> + return;
> + ::qsort (address (), length (), sizeof (T), cmp);
> + if (CHECKING_P)
> + vec_check_sort_cmp (address (), length (), sizeof (T), cmp);
> }
>
>
