Re: [PATCH 1/2] Introduce gcc_sort_r

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Aug 1, 2019 at 5:54 PM Alexander Monakov <amonakov@ispras.ru> wrote:
>
> Hi,
>
> this patch adds gcc_sort_r, a function similar to Glibc qsort_r that takes an
> extra 'user data' pointer and passes it to comparators.  Richi asked about it
> in https://gcc.gnu.org/ml/gcc-patches/2019-07/msg01383.html , see followups in
> that thread for other approaches that were considered.
>
> Patch 2/2, unchanged from Richard's version, uses the new function in domwalk.
>
> Bootstrapped/regtested on x86-64.

OK.

Thanks!
Richard.

> Thanks.
> Alexander
>
>         * sort.cc (sort_r_ctx): New struct.
>         (reorder23): Make templated on context type.
>         (reorder45): Ditto.
>         (cmp1): Ditto.  Adjust signature.
>         (netsort): Ditto.
>         (mergesort): Ditto.
>         [CHECKING_P] (cmp2to3): New static function.  Use it...
>         (gcc_qsort) [CHECKING_P]: ...here.
>         (gcc_sort_r): New function.
>         * system.h (sort_r_cmp_fn): New function typedef.
>         (qsort_chk): Adjust signature.
>         (gcc_sort_r): Declare.
>         * vec.c (qsort_chk_error): Adjust.
>         (qsort_chk): Adjust.
>
> diff --git a/gcc/sort.cc b/gcc/sort.cc
> index 3e9c032c462..73a9f7ed7c5 100644
> --- a/gcc/sort.cc
> +++ b/gcc/sort.cc
> @@ -58,8 +58,25 @@ struct sort_ctx
>    size_t nlim; // limit for network sort
>  };
>
> +/* Like sort_ctx, but for use with qsort_r-style comparators.  Several
> +   functions in this file are templates that work with either context type.  */
> +struct sort_r_ctx
> +{
> +  void          *data;
> +  sort_r_cmp_fn *cmp_;
> +  char   *out;
> +  size_t n;
> +  size_t size;
> +  size_t nlim;
> +  int cmp (const void *a, const void *b)
> +  {
> +    return cmp_ (a, b, data);
> +  }
> +};
> +
>  /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
>     placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on.  */
> +template<typename sort_ctx>
>  static void
>  reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
>  {
> @@ -90,6 +107,7 @@ do {                                                     \
>  }
>
>  /* Like reorder23, but permute 4 or 5 elements.  */
> +template<typename sort_ctx>
>  static void
>  reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
>  {
> @@ -127,21 +145,23 @@ do {                                                     \
>     Return E0^E1 if E0 compares less than E1, zero otherwise.
>     This is noinline to avoid code growth and confine invocation
>     to a single call site, assisting indirect branch prediction.  */
> +template<typename sort_ctx>
>  noinline static intptr_t
> -cmp1 (char *e0, char *e1, cmp_fn *cmp)
> +cmp1 (char *e0, char *e1, sort_ctx *c)
>  {
>    intptr_t x = (intptr_t)e0 ^ (intptr_t)e1;
> -  return x & (cmp (e0, e1) >> 31);
> +  return x & (c->cmp (e0, e1) >> 31);
>  }
>
>  /* Execute network sort on 2 to 5 elements from IN, placing them into C->OUT.
>     IN may be equal to C->OUT, in which case elements are sorted in place.  */
> +template<typename sort_ctx>
>  static void
>  netsort (char *in, sort_ctx *c)
>  {
>  #define CMP(e0, e1)                   \
>  do {                                  \
> -  intptr_t x = cmp1 (e1, e0, c->cmp); \
> +  intptr_t x = cmp1 (e1, e0, c);      \
>    e0 = (char *)((intptr_t)e0 ^ x);    \
>    e1 = (char *)((intptr_t)e1 ^ x);    \
>  } while (0)
> @@ -176,6 +196,7 @@ do {                                  \
>  /* Execute merge sort on N elements from IN, placing them into OUT,
>     using TMP as temporary storage if IN is equal to OUT.
>     This is a stable sort if netsort is used only for 2 or 3 elements.  */
> +template<typename sort_ctx>
>  static void
>  mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp)
>  {
> @@ -217,6 +238,17 @@ do {                                            \
>    memcpy (out, l, r - out);
>  }
>
> +#if CHECKING_P
> +/* Adapter for using two-argument comparators in functions expecting the
> +   three-argument sort_r_cmp_fn type.  */
> +static int
> +cmp2to3 (const void *a, const void *b, void *c)
> +{
> +  return ((cmp_fn *)c) (a, b);
> +}
> +#endif
> +
> +/* Replacement for C qsort.  */
>  void
>  gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
>  {
> @@ -235,10 +267,30 @@ gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
>    if (buf != scratch)
>      free (buf);
>  #if CHECKING_P
> -  qsort_chk (vbase, n, size, cmp);
> +  qsort_chk (vbase, n, size, cmp2to3, (void*)cmp);
>  #endif
>  }
>
> +/* Substitute for Glibc qsort_r.  */
> +void
> +gcc_sort_r (void *vbase, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
> +{
> +  if (n < 2)
> +    return;
> +  char *base = (char *)vbase;
> +  sort_r_ctx c = {data, cmp, base, n, size, 5};
> +  long long scratch[32];
> +  size_t bufsz = (n / 2) * size;
> +  void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz);
> +  mergesort (base, &c, n, base, (char *)buf);
> +  if (buf != scratch)
> +    free (buf);
> +#if CHECKING_P
> +  qsort_chk (vbase, n, size, cmp, data);
> +#endif
> +}
> +
> +/* Stable sort, signature-compatible to C qsort.  */
>  void
>  gcc_stablesort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
>  {
> diff --git a/gcc/system.h b/gcc/system.h
> index d04f8fd3360..56af544b70b 100644
> --- a/gcc/system.h
> +++ b/gcc/system.h
> @@ -1197,13 +1197,14 @@ helper_const_non_const_cast (const char *p)
>  /* Get definitions of HOST_WIDE_INT.  */
>  #include "hwint.h"
>
> -/* GCC qsort API-compatible functions: except in release-checking compilers,
> -   redirect 4-argument qsort calls to gcc_qsort; keep 1-argument invocations
> -   corresponding to vec::qsort (cmp): they use C qsort internally anyway.  */
> -void qsort_chk (void *, size_t, size_t, int (*)(const void *, const void *));
> +typedef int sort_r_cmp_fn (const void *, const void *, void *);
> +void qsort_chk (void *, size_t, size_t, sort_r_cmp_fn *, void *);
> +void gcc_sort_r (void *, size_t, size_t, sort_r_cmp_fn *, void *);
>  void gcc_qsort (void *, size_t, size_t, int (*)(const void *, const void *));
>  void gcc_stablesort (void *, size_t, size_t,
>                      int (*)(const void *, const void *));
> +/* Redirect four-argument qsort calls to gcc_qsort; one-argument invocations
> +   correspond to vec::qsort, and use C qsort internally.  */
>  #define PP_5th(a1, a2, a3, a4, a5, ...) a5
>  #undef qsort
>  #define qsort(...) PP_5th (__VA_ARGS__, gcc_qsort, 3, 2, qsort, 0) (__VA_ARGS__)
> diff --git a/gcc/vec.c b/gcc/vec.c
> index cbd2db010f9..bac5eb753a3 100644
> --- a/gcc/vec.c
> +++ b/gcc/vec.c
> @@ -192,21 +192,23 @@ dump_vec_loc_statistics (void)
>  ATTRIBUTE_NORETURN ATTRIBUTE_COLD
>  static void
>  qsort_chk_error (const void *p1, const void *p2, const void *p3,
> -                int (*cmp) (const void *, const void *))
> +                sort_r_cmp_fn *cmp, void *data)
>  {
>    if (!p3)
>      {
> -      int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
> -      error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
> +      int r1 = cmp (p1, p2, data), r2 = cmp (p2, p1, data);
> +      error ("qsort comparator not anti-symmetric: %d, %d", r1, r2);
>      }
>    else if (p1 == p2)
>      {
> -      int r = cmp (p1, p3);
> +      int r = cmp (p1, p3, data);
>        error ("qsort comparator non-negative on sorted output: %d", r);
>      }
>    else
>      {
> -      int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
> +      int r1 = cmp (p1, p2, data);
> +      int r2 = cmp (p2, p3, data);
> +      int r3 = cmp (p1, p3, data);
>        error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
>      }
>    internal_error ("qsort checking failed");
> @@ -215,8 +217,7 @@ qsort_chk_error (const void *p1, const void *p2, const void *p3,
>  /* Verify anti-symmetry and transitivity for comparator CMP on sorted array
>     of N SIZE-sized elements pointed to by BASE.  */
>  void
> -qsort_chk (void *base, size_t n, size_t size,
> -          int (*cmp)(const void *, const void *))
> +qsort_chk (void *base, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
>  {
>  #if 0
>  #define LIM(n) (n)
> @@ -225,9 +226,9 @@ qsort_chk (void *base, size_t n, size_t size,
>  #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)
> +#define CMP(i, j) cmp (ELT (i), ELT (j), data)
> +#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp, data)
> +#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp, data)
>    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.  */