[reviewed] qsort comparator consistency checking

[reviewed] qsort comparator consistency checking

[Alexander Monakov]

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.

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
 

Re: [reviewed] qsort comparator consistency checking

[Christophe Lyon]

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
>

Re: [reviewed] qsort comparator consistency checking

[Andrew Pinski]

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
>>

Re: [reviewed] qsort comparator consistency checking

[Alexander Monakov]

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;
     }

Re: [reviewed] qsort comparator consistency checking

[Steve Ellcey]

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

Re: [reviewed] qsort comparator consistency checking

[Christophe Lyon]

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

Re: [reviewed] qsort comparator consistency checking

[Steve Ellcey]

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