Use gather loads for strided accesses
[official-gcc.git] / gcc / vec.c
blob695cd1eba5ad436d02fe7f29ab923907b6e482d7
1 /* Vector API for GNU compiler.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file is compiled twice: once for the generator programs
23 once for the compiler. */
24 #ifdef GENERATOR_FILE
25 #include "bconfig.h"
26 #else
27 #include "config.h"
28 #endif
30 #include "system.h"
31 #include "coretypes.h"
32 #include "hash-table.h"
33 #include "selftest.h"
34 #ifdef GENERATOR_FILE
35 #include "errors.h"
36 #else
37 #include "input.h"
38 #include "diagnostic-core.h"
39 #endif
41 /* vNULL is an empty type with a template cast operation that returns
42 a zero-initialized vec<T, A, L> instance. Use this when you want
43 to assign nil values to new vec instances or pass a nil vector as
44 a function call argument.
46 We use this technique because vec<T, A, L> must be PODs (they are
47 stored in unions and passed in vararg functions), this means that
48 they cannot have ctors/dtors. */
49 vnull vNULL;
51 /* Vector memory usage. */
52 struct vec_usage: public mem_usage
54 /* Default constructor. */
55 vec_usage (): m_items (0), m_items_peak (0) {}
57 /* Constructor. */
58 vec_usage (size_t allocated, size_t times, size_t peak,
59 size_t items, size_t items_peak)
60 : mem_usage (allocated, times, peak),
61 m_items (items), m_items_peak (items_peak) {}
63 /* Sum the usage with SECOND usage. */
64 vec_usage
65 operator+ (const vec_usage &second)
67 return vec_usage (m_allocated + second.m_allocated,
68 m_times + second.m_times,
69 m_peak + second.m_peak,
70 m_items + second.m_items,
71 m_items_peak + second.m_items_peak);
74 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
75 inline void
76 dump (mem_location *loc, mem_usage &total) const
78 char s[4096];
79 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
80 loc->m_line, loc->m_function);
82 s[48] = '\0';
84 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
85 (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
86 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
87 (long)m_items, (long)m_items_peak);
90 /* Dump footer. */
91 inline void
92 dump_footer ()
94 print_dash_line ();
95 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
96 (long)m_times, (long)m_items);
97 print_dash_line ();
100 /* Dump header with NAME. */
101 static inline void
102 dump_header (const char *name)
104 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
105 "Times", "Leak items", "Peak items");
106 print_dash_line ();
109 /* Current number of items allocated. */
110 size_t m_items;
111 /* Peak value of number of allocated items. */
112 size_t m_items_peak;
115 /* Vector memory description. */
116 static mem_alloc_description <vec_usage> vec_mem_desc;
118 /* Account the overhead. */
120 void
121 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
122 MEM_STAT_DECL)
124 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
125 FINAL_PASS_MEM_STAT);
126 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
127 usage->m_items += elements;
128 if (usage->m_items_peak < usage->m_items)
129 usage->m_items_peak = usage->m_items;
132 /* Notice that the memory allocated for the vector has been freed. */
134 void
135 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
136 MEM_STAT_DECL)
138 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
139 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
140 false FINAL_PASS_MEM_STAT);
141 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
145 /* Calculate the number of slots to reserve a vector, making sure that
146 it is of at least DESIRED size by growing ALLOC exponentially. */
148 unsigned
149 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
151 /* We must have run out of room. */
152 gcc_assert (alloc < desired);
154 /* Exponential growth. */
155 if (!alloc)
156 alloc = 4;
157 else if (alloc < 16)
158 /* Double when small. */
159 alloc = alloc * 2;
160 else
161 /* Grow slower when large. */
162 alloc = (alloc * 3 / 2);
164 /* If this is still too small, set it to the right size. */
165 if (alloc < desired)
166 alloc = desired;
167 return alloc;
170 /* Dump per-site memory statistics. */
172 void
173 dump_vec_loc_statistics (void)
175 vec_mem_desc.dump (VEC_ORIGIN);
178 #if CHECKING_P
179 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
180 witness elements. */
181 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
182 static void
183 qsort_chk_error (const void *p1, const void *p2, const void *p3,
184 int (*cmp) (const void *, const void *))
186 if (!p3)
188 int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
189 error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
191 else if (p1 == p2)
193 int r = cmp (p1, p3);
194 error ("qsort comparator non-negative on sorted output: %d", r);
196 else
198 int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
199 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
201 internal_error ("qsort checking failed");
204 /* Wrapper around qsort with checking that CMP is consistent on given input.
206 Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
207 comparators to libc qsort can result in undefined behavior. Therefore we
208 should ideally perform consistency checks prior to invoking qsort, but in
209 order to do that optimally we'd need to sort the array ourselves beforehand
210 with a sorting routine known to be "safe". Instead, we expect that most
211 implementations in practice will still produce some permutation of input
212 array even for invalid comparators, which enables us to perform checks on
213 the output array. */
214 void
215 qsort_chk (void *base, size_t n, size_t size,
216 int (*cmp)(const void *, const void *))
218 (qsort) (base, n, size, cmp);
219 #if 0
220 #define LIM(n) (n)
221 #else
222 /* Limit overall time complexity to O(n log n). */
223 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
224 #endif
225 #define ELT(i) ((const char *) base + (i) * size)
226 #define CMP(i, j) cmp (ELT (i), ELT (j))
227 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
228 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
229 size_t i1, i2, i, j;
230 /* This outer loop iterates over maximum spans [i1, i2) such that
231 elements within each span compare equal to each other. */
232 for (i1 = 0; i1 < n; i1 = i2)
234 /* Position i2 one past last element that compares equal to i1'th. */
235 for (i2 = i1 + 1; i2 < n; i2++)
236 if (CMP (i1, i2))
237 break;
238 else if (CMP (i2, i1))
239 return ERR2 (i1, i2);
240 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
241 /* Verify that other pairs within current span compare equal. */
242 for (i = i1 + 1; i + 1 < i2; i++)
243 for (j = i + 1; j < i1 + lim1; j++)
244 if (CMP (i, j))
245 return ERR3 (i, i1, j);
246 else if (CMP (j, i))
247 return ERR2 (i, j);
248 /* Verify that elements within this span compare less than
249 elements beyond the span. */
250 for (i = i1; i < i2; i++)
251 for (j = i2; j < i2 + lim2; j++)
252 if (CMP (i, j) >= 0)
253 return ERR3 (i, i1, j);
254 else if (CMP (j, i) <= 0)
255 return ERR2 (i, j);
257 #undef ERR3
258 #undef ERR2
259 #undef CMP
260 #undef ELT
261 #undef LIM
263 #endif /* #if CHECKING_P */
265 #ifndef GENERATOR_FILE
266 #if CHECKING_P
268 namespace selftest {
270 /* Selftests. */
272 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
273 Helper function for selftests. */
275 static void
276 safe_push_range (vec <int>&v, int start, int limit)
278 for (int i = start; i < limit; i++)
279 v.safe_push (i);
282 /* Verify that vec::quick_push works correctly. */
284 static void
285 test_quick_push ()
287 auto_vec <int> v;
288 ASSERT_EQ (0, v.length ());
289 v.reserve (3);
290 ASSERT_EQ (0, v.length ());
291 ASSERT_TRUE (v.space (3));
292 v.quick_push (5);
293 v.quick_push (6);
294 v.quick_push (7);
295 ASSERT_EQ (3, v.length ());
296 ASSERT_EQ (5, v[0]);
297 ASSERT_EQ (6, v[1]);
298 ASSERT_EQ (7, v[2]);
301 /* Verify that vec::safe_push works correctly. */
303 static void
304 test_safe_push ()
306 auto_vec <int> v;
307 ASSERT_EQ (0, v.length ());
308 v.safe_push (5);
309 v.safe_push (6);
310 v.safe_push (7);
311 ASSERT_EQ (3, v.length ());
312 ASSERT_EQ (5, v[0]);
313 ASSERT_EQ (6, v[1]);
314 ASSERT_EQ (7, v[2]);
317 /* Verify that vec::truncate works correctly. */
319 static void
320 test_truncate ()
322 auto_vec <int> v;
323 ASSERT_EQ (0, v.length ());
324 safe_push_range (v, 0, 10);
325 ASSERT_EQ (10, v.length ());
327 v.truncate (5);
328 ASSERT_EQ (5, v.length ());
331 /* Verify that vec::safe_grow_cleared works correctly. */
333 static void
334 test_safe_grow_cleared ()
336 auto_vec <int> v;
337 ASSERT_EQ (0, v.length ());
338 v.safe_grow_cleared (50);
339 ASSERT_EQ (50, v.length ());
340 ASSERT_EQ (0, v[0]);
341 ASSERT_EQ (0, v[49]);
344 /* Verify that vec::pop works correctly. */
346 static void
347 test_pop ()
349 auto_vec <int> v;
350 safe_push_range (v, 5, 20);
351 ASSERT_EQ (15, v.length ());
353 int last = v.pop ();
354 ASSERT_EQ (19, last);
355 ASSERT_EQ (14, v.length ());
358 /* Verify that vec::safe_insert works correctly. */
360 static void
361 test_safe_insert ()
363 auto_vec <int> v;
364 safe_push_range (v, 0, 10);
365 v.safe_insert (5, 42);
366 ASSERT_EQ (4, v[4]);
367 ASSERT_EQ (42, v[5]);
368 ASSERT_EQ (5, v[6]);
369 ASSERT_EQ (11, v.length ());
372 /* Verify that vec::ordered_remove works correctly. */
374 static void
375 test_ordered_remove ()
377 auto_vec <int> v;
378 safe_push_range (v, 0, 10);
379 v.ordered_remove (5);
380 ASSERT_EQ (4, v[4]);
381 ASSERT_EQ (6, v[5]);
382 ASSERT_EQ (9, v.length ());
385 /* Verify that vec::unordered_remove works correctly. */
387 static void
388 test_unordered_remove ()
390 auto_vec <int> v;
391 safe_push_range (v, 0, 10);
392 v.unordered_remove (5);
393 ASSERT_EQ (9, v.length ());
396 /* Verify that vec::block_remove works correctly. */
398 static void
399 test_block_remove ()
401 auto_vec <int> v;
402 safe_push_range (v, 0, 10);
403 v.block_remove (5, 3);
404 ASSERT_EQ (3, v[3]);
405 ASSERT_EQ (4, v[4]);
406 ASSERT_EQ (8, v[5]);
407 ASSERT_EQ (9, v[6]);
408 ASSERT_EQ (7, v.length ());
411 /* Comparator for use by test_qsort. */
413 static int
414 reverse_cmp (const void *p_i, const void *p_j)
416 return *(const int *)p_j - *(const int *)p_i;
419 /* Verify that vec::qsort works correctly. */
421 static void
422 test_qsort ()
424 auto_vec <int> v;
425 safe_push_range (v, 0, 10);
426 v.qsort (reverse_cmp);
427 ASSERT_EQ (9, v[0]);
428 ASSERT_EQ (8, v[1]);
429 ASSERT_EQ (1, v[8]);
430 ASSERT_EQ (0, v[9]);
431 ASSERT_EQ (10, v.length ());
434 /* Run all of the selftests within this file. */
436 void
437 vec_c_tests ()
439 test_quick_push ();
440 test_safe_push ();
441 test_truncate ();
442 test_safe_grow_cleared ();
443 test_pop ();
444 test_safe_insert ();
445 test_ordered_remove ();
446 test_unordered_remove ();
447 test_block_remove ();
448 test_qsort ();
451 } // namespace selftest
453 #endif /* #if CHECKING_P */
454 #endif /* #ifndef GENERATOR_FILE */