Mercurial > hg > CbC > CbC_gcc

comparison gcc/sort.cc @ 132:d34655255c78

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc-8.2
author mir3636
date Thu, 25 Oct 2018 10:21:07 +0900
parents 84e7813d76e9
children 1830386684a0
comparison
equal deleted inserted replaced
130:e108057fa461 132:d34655255c78
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 size_t nlim; // limit for network sort
59 };
60
61 /* Helper for netsort. Permute, possibly in-place, 2 or 3 elements,
62 placing E0 to C->OUT, E1 to C->OUT + C->SIZE, and so on. */
63 static void
64 reorder23 (sort_ctx *c, char *e0, char *e1, char *e2)
65 {
66 #define REORDER_23(TYPE, STRIDE, OFFSET) \
67 do { \
68 TYPE t0, t1; \
69 memcpy (&t0, e0 + OFFSET, sizeof (TYPE)); \
70 memcpy (&t1, e1 + OFFSET, sizeof (TYPE)); \
71 char *out = c->out + OFFSET; \
72 if (likely (c->n == 3)) \
73 memmove (out + 2*STRIDE, e2 + OFFSET, sizeof (TYPE));\
74 memcpy (out, &t0, sizeof (TYPE)); out += STRIDE; \
75 memcpy (out, &t1, sizeof (TYPE)); \
76 } while (0)
77
78 if (likely (c->size == sizeof (size_t)))
79 REORDER_23 (size_t, sizeof (size_t), 0);
80 else if (likely (c->size == sizeof (int)))
81 REORDER_23 (int, sizeof (int), 0);
82 else
83 {
84 size_t offset = 0, step = sizeof (size_t);
85 for (; offset + step <= c->size; offset += step)
86 REORDER_23 (size_t, c->size, offset);
87 for (; offset < c->size; offset++)
88 REORDER_23 (char, c->size, offset);
89 }
90 }
91
92 /* Like reorder23, but permute 4 or 5 elements. */
93 static void
94 reorder45 (sort_ctx *c, char *e0, char *e1, char *e2, char *e3, char *e4)
95 {
96 #define REORDER_45(TYPE, STRIDE, OFFSET) \
97 do { \
98 TYPE t0, t1, t2, t3; \
99 memcpy (&t0, e0 + OFFSET, sizeof (TYPE)); \
100 memcpy (&t1, e1 + OFFSET, sizeof (TYPE)); \
101 memcpy (&t2, e2 + OFFSET, sizeof (TYPE)); \
102 memcpy (&t3, e3 + OFFSET, sizeof (TYPE)); \
103 char *out = c->out + OFFSET; \
104 if (likely (c->n == 5)) \
105 memmove (out + 4*STRIDE, e4 + OFFSET, sizeof (TYPE));\
106 memcpy (out, &t0, sizeof (TYPE)); out += STRIDE; \
107 memcpy (out, &t1, sizeof (TYPE)); out += STRIDE; \
108 memcpy (out, &t2, sizeof (TYPE)); out += STRIDE; \
109 memcpy (out, &t3, sizeof (TYPE)); \
110 } while (0)
111
112 if (likely (c->size == sizeof (size_t)))
113 REORDER_45 (size_t, sizeof (size_t), 0);
114 else if (likely(c->size == sizeof (int)))
115 REORDER_45 (int, sizeof (int), 0);
116 else
117 {
118 size_t offset = 0, step = sizeof (size_t);
119 for (; offset + step <= c->size; offset += step)
120 REORDER_45 (size_t, c->size, offset);
121 for (; offset < c->size; offset++)
122 REORDER_45 (char, c->size, offset);
123 }
124 }
125
126 /* Helper for netsort. Invoke comparator CMP on E0 and E1.
127 Return E0^E1 if E0 compares less than E1, zero otherwise.
128 This is noinline to avoid code growth and confine invocation
129 to a single call site, assisting indirect branch prediction. */
130 noinline static intptr_t
131 cmp1 (char *e0, char *e1, cmp_fn *cmp)
132 {
133 intptr_t x = (intptr_t)e0 ^ (intptr_t)e1;
134 return x & (cmp (e0, e1) >> 31);
135 }
136
137 /* Execute network sort on 2 to 5 elements from IN, placing them into C->OUT.
138 IN may be equal to C->OUT, in which case elements are sorted in place. */
139 static void
140 netsort (char *in, sort_ctx *c)
141 {
142 #define CMP(e0, e1) \
143 do { \
144 intptr_t x = cmp1 (e1, e0, c->cmp); \
145 e0 = (char *)((intptr_t)e0 ^ x); \
146 e1 = (char *)((intptr_t)e1 ^ x); \
147 } while (0)
148
149 char *e0 = in, *e1 = e0 + c->size, *e2 = e1 + c->size;
150 CMP (e0, e1);
151 if (likely (c->n == 3))
152 {
153 CMP (e1, e2);
154 CMP (e0, e1);
155 }
156 if (c->n <= 3)
157 return reorder23 (c, e0, e1, e2);
158 char *e3 = e2 + c->size, *e4 = e3 + c->size;
159 if (likely (c->n == 5))
160 {
161 CMP (e3, e4);
162 CMP (e2, e4);
163 }
164 CMP (e2, e3);
165 if (likely (c->n == 5))
166 {
167 CMP (e0, e3);
168 CMP (e1, e4);
169 }
170 CMP (e0, e2);
171 CMP (e1, e3);
172 CMP (e1, e2);
173 reorder45 (c, e0, e1, e2, e3, e4);
174 }
175
176 /* Execute merge sort on N elements from IN, placing them into OUT,
177 using TMP as temporary storage if IN is equal to OUT.
178 This is a stable sort if netsort is used only for 2 or 3 elements. */
179 static void
180 mergesort (char *in, sort_ctx *c, size_t n, char *out, char *tmp)
181 {
182 if (likely (n <= c->nlim))
183 {
184 c->out = out;
185 c->n = n;
186 return netsort (in, c);
187 }
188 size_t nl = n / 2, nr = n - nl, sz = nl * c->size;
189 char *mid = in + sz, *r = out + sz, *l = in == out ? tmp : in;
190 /* Sort the right half, outputting to right half of OUT. */
191 mergesort (mid, c, nr, r, tmp);
192 /* Sort the left half, leaving left half of OUT free. */
193 mergesort (in, c, nl, l, mid);
194 /* Merge sorted halves given by L, R to [OUT, END). */
195 #define MERGE_ELTSIZE(SIZE) \
196 do { \
197 intptr_t mr = c->cmp (r, l) >> 31; \
198 intptr_t lr = (intptr_t)l ^ (intptr_t)r; \
199 lr = (intptr_t)l ^ (lr & mr); \
200 out = (char *)memcpy (out, (char *)lr, SIZE); \
201 out += SIZE; \
202 r += mr & SIZE; \
203 if (r == out) return; \
204 l += ~mr & SIZE; \
205 } while (r != end)
206
207 if (likely (c->cmp(r, l + (r - out) - c->size) < 0))
208 {
209 char *end = out + n * c->size;
210 if (sizeof (size_t) == 8 && likely (c->size == 8))
211 MERGE_ELTSIZE (8);
212 else if (likely (c->size == 4))
213 MERGE_ELTSIZE (4);
214 else
215 MERGE_ELTSIZE (c->size);
216 }
217 memcpy (out, l, r - out);
218 }
219
220 void
221 gcc_qsort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
222 {
223 if (n < 2)
224 return;
225 size_t nlim = 5;
226 bool stable = (ssize_t) size < 0;
227 if (stable)
228 nlim = 3, size = ~size;
229 char *base = (char *)vbase;
230 sort_ctx c = {cmp, base, n, size, nlim};
231 long long scratch[32];
232 size_t bufsz = (n / 2) * size;
233 void *buf = bufsz <= sizeof scratch ? scratch : xmalloc (bufsz);
234 mergesort (base, &c, n, base, (char *)buf);
235 if (buf != scratch)
236 free (buf);
237 #if CHECKING_P
238 qsort_chk (vbase, n, size, cmp);
239 #endif
240 }
241
242 void
243 gcc_stablesort (void *vbase, size_t n, size_t size, cmp_fn *cmp)
244 {
245 gcc_qsort (vbase, n, ~size, cmp);
246 }