gcc/sort.cc

   1 /* Platform-independent deterministic sort function.
   2    Copyright (C) 2018 Free Software Foundation, Inc.
   3    Contributed by Alexander Monakov.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This implements a sort function suitable for GCC use cases:
  22    - signature-compatible to C qsort, but relaxed contract:
  23      - may apply the comparator to elements in a temporary buffer
  24      - may abort on allocation failure
  25    - deterministic (but not necessarily stable)
  26    - fast, especially for common cases (0-5 elements of size 8 or 4)
  27
  28    The implementation uses a network sort for up to 5 elements and
  29    a merge sort on top of that.  Neither stage has branches depending on
  30    comparator result, trading extra arithmetic for branch mispredictions.  */
  31
  32 #ifdef GENERATOR_FILE
  33 #include "bconfig.h"
  34 #else
  35 #include "config.h"
  36 #endif
  37
  38 #include "system.h"
  39
  40 #define likely(cond) __builtin_expect ((cond), 1)
  41
  42 #ifdef __GNUC__
  43 #define noinline __attribute__ ((__noinline__))
  44 #else
  45 #define noinline
  46 #endif
  47
  48 /* C-style qsort comparator function type.  */
  49 typedef int cmp_fn (const void *, const void *);
  50
  51 /* Structure holding read-mostly (read-only in netsort) context.  */
  52 struct sort_ctx
  53 {
  54   cmp_fn *cmp; // pointer to comparator
  55   char   *out; // output buffer
  56   size_t n;    // number of elements
  57   size_t size; // element size
  58 };
  59
  60 /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
  61    placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on.  */
  62 static void
  63 reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
  64 {
  65 #define REORDER_23(TYPE, STRIDE, OFFSET)                 \
  66 do {                                                     \
  67   TYPE t0, t1;                                           \
  68   memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
  69   memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
  70   char *out = c->out + OFFSET;                           \
  71   if (likely (c->n == 3))                                \
  72     memcpy (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE)); \
  73   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
  74   memcpy (out, &t1, sizeof (TYPE));                      \
  75 } while (0)
  76
  77   if (likely (c->size == sizeof (size_t)))
  78     REORDER_23 (size_t, sizeof (size_t), 0);
  79   else if (likely (c->size == sizeof (int)))
  80     REORDER_23 (int, sizeof (int), 0);
  81   else
  82     {
  83       size_t offset = 0, step = sizeof (size_t);
  84       for (; offset + step <= c->size; offset += step)
  85         REORDER_23 (size_t, c->size, offset);
  86       for (; offset < c->size; offset++)
  87         REORDER_23 (char, c->size, offset);
  88     }
  89 }
  90
  91 /* Like reorder23, but permute 4 or 5 elements.  */
  92 static void
  93 reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
  94 {
  95 #define REORDER_45(TYPE, STRIDE, OFFSET)                 \
  96 do {                                                     \
  97   TYPE t0, t1, t2, t3;                                   \
  98   memcpy (&t0, e0 + OFFSET, sizeof (TYPE));              \
  99   memcpy (&t1, e1 + OFFSET, sizeof (TYPE));              \
 100   memcpy (&t2, e2 + OFFSET, sizeof (TYPE));              \
 101   memcpy (&t3, e3 + OFFSET, sizeof (TYPE));              \
 102   char *out = c->out + OFFSET;                           \
 103   if (likely (c->n == 5))                                \
 104     memcpy (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE)); \
 105   memcpy (out, &t0, sizeof (TYPE)); out += STRIDE;       \
 106   memcpy (out, &t1, sizeof (TYPE)); out += STRIDE;       \
 107   memcpy (out, &t2, sizeof (TYPE)); out += STRIDE;       \
 108   memcpy (out, &t3, sizeof (TYPE));                      \
 109 } while (0)
 110
 111   if (likely (c->size == sizeof (size_t)))
 112     REORDER_45 (size_t, sizeof (size_t), 0);
 113   else if (likely(c->size == sizeof (int)))
 114     REORDER_45 (int,  sizeof (int), 0);
 115   else
 116     {
 117       size_t offset = 0, step = sizeof (size_t);
 118       for (; offset + step <= c->size; offset += step)
 119         REORDER_45 (size_t, c->size, offset);
 120       for (; offset < c->size; offset++)
 121         REORDER_45 (char, c->size, offset);
 122     }
 123 }
 124
 125 /* Helper for netsort. Invoke comparator CMP on E0 and E1.
 126    Return E0^E1 if E0 compares less than E1, zero otherwise.
 127    This is noinline to avoid code growth and confine invocation
 128    to a single call site, assisting indirect branch prediction.  */
 129 noinline static intptr_t
 130 cmp1 (char *e0, char *e1, cmp_fn *cmp)
 131 {
 132   intptr_t x = (intptr_t)e0 ^ (intptr_t)e1;
 133   return x & (cmp (e0, e1) >> 31);
 134 }
 135
 136 /* Execute network sort on 2 to 5 elements from IN, placing them into C->OUT.
 137    IN may be equal to C->OUT, in which case elements are sorted in place.  */
 138 static void
 139 netsort (char *in, sort_ctx *c)
 140 {
 141 #define CMP(e0, e1)                   \
 142 do {                                  \
 143   intptr_t x = cmp1 (e1, e0, c->cmp); \
 144   e0 = (char *)((intptr_t)e0 ^ x);    \
 145   e1 = (char *)((intptr_t)e1 ^ x);    \
 146 } while (0)
 147
 148   char *e0 = in, *e1 = e0 + c->size, *e2 = e1 + c->size;
 149   CMP (e0, e1);
 150   if (likely (c->n == 3))
 151     {
 152       CMP (e1, e2);
 153       CMP (e0, e1);
 154     }
 155   if (c->n <= 3)
 156     return reorder23 (c, e0, e1, e2);
 157   char *e3 = e2 + c->size, *e4 = e3 + c->size;
 158   if (likely (c->n == 5))
 159     {
 160       CMP (e3, e4);
 161       CMP (e2, e4);
 162     }
 163   CMP (e2, e3);
 164   if (likely (c->n == 5))
 165     {
 166       CMP (e0, e3);
 167       CMP (e1, e4);
 168     }
 169   CMP (e0, e2);
 170   CMP (e1, e3);
 171   CMP (e1, e2);
 172   reorder45 (c, e0, e1, e2, e3, e4);
 173 }
 174
 175 /* Execute merge sort on N elements from IN, placing them into OUT,
 176    using TMP as temporary storage if IN is equal to OUT.
 177    This is a stable sort if netsort is used only for 2 or 3 elements.  */
 178 static void
 179 mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp)
 180 {
 181   if (likely (n <= 5))
 182     {
 183       c->out = out;
 184       c->n = n;
 185       return netsort (in, c);
 186     }
 187   size_t nl = n / 2, nr = n - nl, sz = nl * c->size;
 188   char *mid = in + sz, *r = out + sz, *l = in == out ? tmp : in;
 189   /* Sort the right half, outputting to right half of OUT.  */
 190   mergesort (mid, c, nr, r, tmp);
 191   /* Sort the left half, leaving left half of OUT free.  */
 192   mergesort (in, c, nl, l, mid);
 193   /* Merge sorted halves given by L, R to [OUT, END).  */
 194 #define MERGE_ELTSIZE(SIZE)                     \
 195 do {                                            \
 196   intptr_t mr = c->cmp (r, l) >> 31;            \
 197   intptr_t lr = (intptr_t)l ^ (intptr_t)r;      \
 198   lr = (intptr_t)l ^ (lr & mr);                 \
 199   out = (char *)memcpy (out, (char *)lr, SIZE); \
 200   out += SIZE;                                  \
 201   r += mr & SIZE;                               \
 202   if (r == out) return;                         \
 203   l += ~mr & SIZE;                              \
 204 } while (r != end)
 205
 206   if (likely (c->cmp(r, l + (r - out) - c->size) < 0))
 207     {
 208       char *end = out + n * c->size;
 209       if (sizeof (size_t) == 8 && likely (c->size == 8))
 210         MERGE_ELTSIZE (8);
 211       else if (likely (c->size == 4))
 212         MERGE_ELTSIZE (4);
 213       else
 214         MERGE_ELTSIZE (c->size);
 215     }
 216   memcpy (out, l, r - out);
 217 }
 218
 219 void
 220 gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
 221 {
 222   if (n < 2)
 223     return;
 224   char *base = (char *)vbase;
 225   sort_ctx c = {cmp, base, n, size};
 226   long long scratch[32];
 227   size_t bufsz = (n / 2) * size;
 228   void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz);
 229   mergesort (base, &c, n, base, (char *)buf);
 230   if (buf != scratch)
 231     free (buf);
 232 }