|
131
|
1 /* A class for building vector constant patterns.
|
|
|
2 Copyright (C) 2017-2018 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify it under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
14 for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #ifndef GCC_VECTOR_BUILDER_H
|
|
|
21 #define GCC_VECTOR_BUILDER_H
|
|
|
22
|
|
|
23 /* This class is a wrapper around auto_vec<T> for building vectors of T.
|
|
|
24 It aims to encode each vector as npatterns interleaved patterns,
|
|
|
25 where each pattern represents a sequence:
|
|
|
26
|
|
|
27 { BASE0, BASE1, BASE1 + STEP, BASE1 + STEP*2, BASE1 + STEP*3, ... }
|
|
|
28
|
|
|
29 The first three elements in each pattern provide enough information
|
|
|
30 to derive the other elements. If all patterns have a STEP of zero,
|
|
|
31 we only need to encode the first two elements in each pattern.
|
|
|
32 If BASE1 is also equal to BASE0 for all patterns, we only need to
|
|
|
33 encode the first element in each pattern. The number of encoded
|
|
|
34 elements per pattern is given by nelts_per_pattern.
|
|
|
35
|
|
|
36 The class can be used in two ways:
|
|
|
37
|
|
|
38 1. It can be used to build a full image of the vector, which is then
|
|
|
39 canonicalized by finalize (). In this case npatterns is initially
|
|
|
40 the number of elements in the vector and nelts_per_pattern is
|
|
|
41 initially 1.
|
|
|
42
|
|
|
43 2. It can be used to build a vector that already has a known encoding.
|
|
|
44 This is preferred since it is more efficient and copes with
|
|
|
45 variable-length vectors. finalize () then canonicalizes the encoding
|
|
|
46 to a simpler form if possible.
|
|
|
47
|
|
|
48 The derived class Derived provides this functionality for specific Ts.
|
|
|
49 Derived needs to provide the following interface:
|
|
|
50
|
|
|
51 bool equal_p (T elt1, T elt2) const;
|
|
|
52
|
|
|
53 Return true if elements ELT1 and ELT2 are equal.
|
|
|
54
|
|
|
55 bool allow_steps_p () const;
|
|
|
56
|
|
|
57 Return true if a stepped representation is OK. We don't allow
|
|
|
58 linear series for anything other than integers, to avoid problems
|
|
|
59 with rounding.
|
|
|
60
|
|
|
61 bool integral_p (T elt) const;
|
|
|
62
|
|
|
63 Return true if element ELT can be interpreted as an integer.
|
|
|
64
|
|
|
65 StepType step (T elt1, T elt2) const;
|
|
|
66
|
|
|
67 Return the value of element ELT2 minus the value of element ELT1,
|
|
|
68 given integral_p (ELT1) && integral_p (ELT2). There is no fixed
|
|
|
69 choice of StepType.
|
|
|
70
|
|
|
71 T apply_step (T base, unsigned int factor, StepType step) const;
|
|
|
72
|
|
|
73 Return a vector element with the value BASE + FACTOR * STEP.
|
|
|
74
|
|
|
75 bool can_elide_p (T elt) const;
|
|
|
76
|
|
|
77 Return true if we can drop element ELT, even if the retained
|
|
|
78 elements are different. This is provided for TREE_OVERFLOW
|
|
|
79 handling.
|
|
|
80
|
|
|
81 void note_representative (T *elt1_ptr, T elt2);
|
|
|
82
|
|
|
83 Record that ELT2 is being elided, given that ELT1_PTR points to
|
|
|
84 the last encoded element for the containing pattern. This is
|
|
|
85 again provided for TREE_OVERFLOW handling. */
|
|
|
86
|
|
|
87 template<typename T, typename Derived>
|
|
|
88 class vector_builder : public auto_vec<T, 32>
|
|
|
89 {
|
|
|
90 public:
|
|
|
91 vector_builder ();
|
|
|
92
|
|
|
93 poly_uint64 full_nelts () const { return m_full_nelts; }
|
|
|
94 unsigned int npatterns () const { return m_npatterns; }
|
|
|
95 unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
|
|
|
96 unsigned int encoded_nelts () const;
|
|
|
97 bool encoded_full_vector_p () const;
|
|
|
98 T elt (unsigned int) const;
|
|
|
99
|
|
|
100 bool operator == (const Derived &) const;
|
|
|
101 bool operator != (const Derived &x) const { return !operator == (x); }
|
|
|
102
|
|
|
103 void finalize ();
|
|
|
104
|
|
|
105 protected:
|
|
|
106 void new_vector (poly_uint64, unsigned int, unsigned int);
|
|
|
107 void reshape (unsigned int, unsigned int);
|
|
|
108 bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
|
|
|
109 bool stepped_sequence_p (unsigned int, unsigned int, unsigned int);
|
|
|
110 bool try_npatterns (unsigned int);
|
|
|
111
|
|
|
112 private:
|
|
|
113 vector_builder (const vector_builder &);
|
|
|
114 vector_builder &operator= (const vector_builder &);
|
|
|
115 Derived *derived () { return static_cast<Derived *> (this); }
|
|
|
116 const Derived *derived () const;
|
|
|
117
|
|
|
118 poly_uint64 m_full_nelts;
|
|
|
119 unsigned int m_npatterns;
|
|
|
120 unsigned int m_nelts_per_pattern;
|
|
|
121 };
|
|
|
122
|
|
|
123 template<typename T, typename Derived>
|
|
|
124 inline const Derived *
|
|
|
125 vector_builder<T, Derived>::derived () const
|
|
|
126 {
|
|
|
127 return static_cast<const Derived *> (this);
|
|
|
128 }
|
|
|
129
|
|
|
130 template<typename T, typename Derived>
|
|
|
131 inline
|
|
|
132 vector_builder<T, Derived>::vector_builder ()
|
|
|
133 : m_full_nelts (0),
|
|
|
134 m_npatterns (0),
|
|
|
135 m_nelts_per_pattern (0)
|
|
|
136 {}
|
|
|
137
|
|
|
138 /* Return the number of elements that are explicitly encoded. The vec
|
|
|
139 starts with these explicitly-encoded elements and may contain additional
|
|
|
140 elided elements. */
|
|
|
141
|
|
|
142 template<typename T, typename Derived>
|
|
|
143 inline unsigned int
|
|
|
144 vector_builder<T, Derived>::encoded_nelts () const
|
|
|
145 {
|
|
|
146 return m_npatterns * m_nelts_per_pattern;
|
|
|
147 }
|
|
|
148
|
|
|
149 /* Return true if every element of the vector is explicitly encoded. */
|
|
|
150
|
|
|
151 template<typename T, typename Derived>
|
|
|
152 inline bool
|
|
|
153 vector_builder<T, Derived>::encoded_full_vector_p () const
|
|
|
154 {
|
|
|
155 return known_eq (m_npatterns * m_nelts_per_pattern, m_full_nelts);
|
|
|
156 }
|
|
|
157
|
|
|
158 /* Start building a vector that has FULL_NELTS elements. Initially
|
|
|
159 encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */
|
|
|
160
|
|
|
161 template<typename T, typename Derived>
|
|
|
162 void
|
|
|
163 vector_builder<T, Derived>::new_vector (poly_uint64 full_nelts,
|
|
|
164 unsigned int npatterns,
|
|
|
165 unsigned int nelts_per_pattern)
|
|
|
166 {
|
|
|
167 m_full_nelts = full_nelts;
|
|
|
168 m_npatterns = npatterns;
|
|
|
169 m_nelts_per_pattern = nelts_per_pattern;
|
|
|
170 this->reserve (encoded_nelts ());
|
|
|
171 this->truncate (0);
|
|
|
172 }
|
|
|
173
|
|
|
174 /* Return true if this vector and OTHER have the same elements and
|
|
|
175 are encoded in the same way. */
|
|
|
176
|
|
|
177 template<typename T, typename Derived>
|
|
|
178 bool
|
|
|
179 vector_builder<T, Derived>::operator == (const Derived &other) const
|
|
|
180 {
|
|
|
181 if (maybe_ne (m_full_nelts, other.m_full_nelts)
|
|
|
182 || m_npatterns != other.m_npatterns
|
|
|
183 || m_nelts_per_pattern != other.m_nelts_per_pattern)
|
|
|
184 return false;
|
|
|
185
|
|
|
186 unsigned int nelts = encoded_nelts ();
|
|
|
187 for (unsigned int i = 0; i < nelts; ++i)
|
|
|
188 if (!derived ()->equal_p ((*this)[i], other[i]))
|
|
|
189 return false;
|
|
|
190
|
|
|
191 return true;
|
|
|
192 }
|
|
|
193
|
|
|
194 /* Return the value of vector element I, which might or might not be
|
|
|
195 encoded explicitly. */
|
|
|
196
|
|
|
197 template<typename T, typename Derived>
|
|
|
198 T
|
|
|
199 vector_builder<T, Derived>::elt (unsigned int i) const
|
|
|
200 {
|
|
|
201 /* This only makes sense if the encoding has been fully populated. */
|
|
|
202 gcc_checking_assert (encoded_nelts () <= this->length ());
|
|
|
203
|
|
|
204 /* First handle elements that are already present in the underlying
|
|
|
205 vector, regardless of whether they're part of the encoding or not. */
|
|
|
206 if (i < this->length ())
|
|
|
207 return (*this)[i];
|
|
|
208
|
|
|
209 /* Identify the pattern that contains element I and work out the index of
|
|
|
210 the last encoded element for that pattern. */
|
|
|
211 unsigned int pattern = i % m_npatterns;
|
|
|
212 unsigned int count = i / m_npatterns;
|
|
|
213 unsigned int final_i = encoded_nelts () - m_npatterns + pattern;
|
|
|
214 T final = (*this)[final_i];
|
|
|
215
|
|
|
216 /* If there are no steps, the final encoded value is the right one. */
|
|
|
217 if (m_nelts_per_pattern <= 2)
|
|
|
218 return final;
|
|
|
219
|
|
|
220 /* Otherwise work out the value from the last two encoded elements. */
|
|
|
221 T prev = (*this)[final_i - m_npatterns];
|
|
|
222 return derived ()->apply_step (final, count - 2,
|
|
|
223 derived ()->step (prev, final));
|
|
|
224 }
|
|
|
225
|
|
|
226 /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
|
|
|
227 but without changing the underlying vector. */
|
|
|
228
|
|
|
229 template<typename T, typename Derived>
|
|
|
230 void
|
|
|
231 vector_builder<T, Derived>::reshape (unsigned int npatterns,
|
|
|
232 unsigned int nelts_per_pattern)
|
|
|
233 {
|
|
|
234 unsigned int old_encoded_nelts = encoded_nelts ();
|
|
|
235 unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
|
|
|
236 gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
|
|
|
237 unsigned int next = new_encoded_nelts - npatterns;
|
|
|
238 for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
|
|
|
239 {
|
|
|
240 derived ()->note_representative (&(*this)[next], (*this)[i]);
|
|
|
241 next += 1;
|
|
|
242 if (next == new_encoded_nelts)
|
|
|
243 next -= npatterns;
|
|
|
244 }
|
|
|
245 m_npatterns = npatterns;
|
|
|
246 m_nelts_per_pattern = nelts_per_pattern;
|
|
|
247 }
|
|
|
248
|
|
|
249 /* Return true if elements [START, END) contain a repeating sequence of
|
|
|
250 STEP elements. */
|
|
|
251
|
|
|
252 template<typename T, typename Derived>
|
|
|
253 bool
|
|
|
254 vector_builder<T, Derived>::repeating_sequence_p (unsigned int start,
|
|
|
255 unsigned int end,
|
|
|
256 unsigned int step)
|
|
|
257 {
|
|
|
258 for (unsigned int i = start; i < end - step; ++i)
|
|
|
259 if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
|
|
|
260 return false;
|
|
|
261 return true;
|
|
|
262 }
|
|
|
263
|
|
|
264 /* Return true if elements [START, END) contain STEP interleaved linear
|
|
|
265 series. */
|
|
|
266
|
|
|
267 template<typename T, typename Derived>
|
|
|
268 bool
|
|
|
269 vector_builder<T, Derived>::stepped_sequence_p (unsigned int start,
|
|
|
270 unsigned int end,
|
|
|
271 unsigned int step)
|
|
|
272 {
|
|
|
273 if (!derived ()->allow_steps_p ())
|
|
|
274 return false;
|
|
|
275
|
|
|
276 for (unsigned int i = start + step * 2; i < end; ++i)
|
|
|
277 {
|
|
|
278 T elt1 = (*this)[i - step * 2];
|
|
|
279 T elt2 = (*this)[i - step];
|
|
|
280 T elt3 = (*this)[i];
|
|
|
281
|
|
|
282 if (!derived ()->integral_p (elt1)
|
|
|
283 || !derived ()->integral_p (elt2)
|
|
|
284 || !derived ()->integral_p (elt3))
|
|
|
285 return false;
|
|
|
286
|
|
|
287 if (maybe_ne (derived ()->step (elt1, elt2),
|
|
|
288 derived ()->step (elt2, elt3)))
|
|
|
289 return false;
|
|
|
290
|
|
|
291 if (!derived ()->can_elide_p (elt3))
|
|
|
292 return false;
|
|
|
293 }
|
|
|
294 return true;
|
|
|
295 }
|
|
|
296
|
|
|
297 /* Try to change the number of encoded patterns to NPATTERNS, returning
|
|
|
298 true on success. */
|
|
|
299
|
|
|
300 template<typename T, typename Derived>
|
|
|
301 bool
|
|
|
302 vector_builder<T, Derived>::try_npatterns (unsigned int npatterns)
|
|
|
303 {
|
|
|
304 if (m_nelts_per_pattern == 1)
|
|
|
305 {
|
|
|
306 /* See whether NPATTERNS is valid with the current 1-element-per-pattern
|
|
|
307 encoding. */
|
|
|
308 if (repeating_sequence_p (0, encoded_nelts (), npatterns))
|
|
|
309 {
|
|
|
310 reshape (npatterns, 1);
|
|
|
311 return true;
|
|
|
312 }
|
|
|
313
|
|
|
314 /* We can only increase the number of elements per pattern if all
|
|
|
315 elements are still encoded explicitly. */
|
|
|
316 if (!encoded_full_vector_p ())
|
|
|
317 return false;
|
|
|
318 }
|
|
|
319
|
|
|
320 if (m_nelts_per_pattern <= 2)
|
|
|
321 {
|
|
|
322 /* See whether NPATTERNS is valid with a 2-element-per-pattern
|
|
|
323 encoding. */
|
|
|
324 if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns))
|
|
|
325 {
|
|
|
326 reshape (npatterns, 2);
|
|
|
327 return true;
|
|
|
328 }
|
|
|
329
|
|
|
330 /* We can only increase the number of elements per pattern if all
|
|
|
331 elements are still encoded explicitly. */
|
|
|
332 if (!encoded_full_vector_p ())
|
|
|
333 return false;
|
|
|
334 }
|
|
|
335
|
|
|
336 if (m_nelts_per_pattern <= 3)
|
|
|
337 {
|
|
|
338 /* See whether we have NPATTERNS interleaved linear series,
|
|
|
339 giving a 3-element-per-pattern encoding. */
|
|
|
340 if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns))
|
|
|
341 {
|
|
|
342 reshape (npatterns, 3);
|
|
|
343 return true;
|
|
|
344 }
|
|
|
345 return false;
|
|
|
346 }
|
|
|
347
|
|
|
348 gcc_unreachable ();
|
|
|
349 }
|
|
|
350
|
|
|
351 /* Replace the current encoding with the canonical form. */
|
|
|
352
|
|
|
353 template<typename T, typename Derived>
|
|
|
354 void
|
|
|
355 vector_builder<T, Derived>::finalize ()
|
|
|
356 {
|
|
|
357 /* The encoding requires the same number of elements to come from each
|
|
|
358 pattern. */
|
|
|
359 gcc_assert (multiple_p (m_full_nelts, m_npatterns));
|
|
|
360
|
|
|
361 /* Allow the caller to build more elements than necessary. For example,
|
|
|
362 it's often convenient to build a stepped vector from the natural
|
|
|
363 encoding of three elements even if the vector itself only has two. */
|
|
|
364 unsigned HOST_WIDE_INT const_full_nelts;
|
|
|
365 if (m_full_nelts.is_constant (&const_full_nelts)
|
|
|
366 && const_full_nelts <= encoded_nelts ())
|
|
|
367 {
|
|
|
368 m_npatterns = const_full_nelts;
|
|
|
369 m_nelts_per_pattern = 1;
|
|
|
370 }
|
|
|
371
|
|
|
372 /* Try to whittle down the number of elements per pattern. That is:
|
|
|
373
|
|
|
374 1. If we have stepped patterns whose steps are all 0, reduce the
|
|
|
375 number of elements per pattern from 3 to 2.
|
|
|
376
|
|
|
377 2. If we have background fill values that are the same as the
|
|
|
378 foreground values, reduce the number of elements per pattern
|
|
|
379 from 2 to 1. */
|
|
|
380 while (m_nelts_per_pattern > 1
|
|
|
381 && repeating_sequence_p (encoded_nelts () - m_npatterns * 2,
|
|
|
382 encoded_nelts (), m_npatterns))
|
|
|
383 /* The last two sequences of M_NPATTERNS elements are equal,
|
|
|
384 so remove the last one. */
|
|
|
385 reshape (m_npatterns, m_nelts_per_pattern - 1);
|
|
|
386
|
|
|
387 if (pow2p_hwi (m_npatterns))
|
|
|
388 {
|
|
|
389 /* Try to halve the number of patterns while doing so gives a
|
|
|
390 valid pattern. This approach is linear in the number of
|
|
|
391 elements, whereas searcing from 1 up would be O(n*log(n)).
|
|
|
392
|
|
|
393 Each halving step tries to keep the number of elements per pattern
|
|
|
394 the same. If that isn't possible, and if all elements are still
|
|
|
395 explicitly encoded, the halving step can instead increase the number
|
|
|
396 of elements per pattern.
|
|
|
397
|
|
|
398 E.g. for:
|
|
|
399
|
|
|
400 { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8
|
|
|
401
|
|
|
402 we first realize that the second half of the sequence is not
|
|
|
403 equal to the first, so we cannot maintain 1 element per pattern
|
|
|
404 for npatterns == 4. Instead we halve the number of patterns
|
|
|
405 and double the number of elements per pattern, treating this
|
|
|
406 as a "foreground" { 0, 2, 3, 4 } against a "background" of
|
|
|
407 { 5, 6, 7, 8 | 5, 6, 7, 8 ... }:
|
|
|
408
|
|
|
409 { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4
|
|
|
410
|
|
|
411 Next we realize that this is *not* a foreround of { 0, 2 }
|
|
|
412 against a background of { 3, 4 | 3, 4 ... }, so the only
|
|
|
413 remaining option for reducing the number of patterns is
|
|
|
414 to use a foreground of { 0, 2 } against a stepped background
|
|
|
415 of { 1, 2 | 3, 4 | 5, 6 ... }. This is valid because we still
|
|
|
416 haven't elided any elements:
|
|
|
417
|
|
|
418 { 0, 2 | 3, 4 | 5, 6 } npatterns == 2
|
|
|
419
|
|
|
420 This in turn can be reduced to a foreground of { 0 } against a
|
|
|
421 stepped background of { 1 | 2 | 3 ... }:
|
|
|
422
|
|
|
423 { 0 | 2 | 3 } npatterns == 1
|
|
|
424
|
|
|
425 This last step would not have been possible for:
|
|
|
426
|
|
|
427 { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */
|
|
|
428 while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
|
|
|
429 continue;
|
|
|
430
|
|
|
431 /* Builders of arbitrary fixed-length vectors can use:
|
|
|
432
|
|
|
433 new_vector (x, x, 1)
|
|
|
434
|
|
|
435 so that every element is specified explicitly. Handle cases
|
|
|
436 that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 }
|
|
|
437 would be for 2-bit elements. We'll have treated them as
|
|
|
438 duplicates in the loop above. */
|
|
|
439 if (m_nelts_per_pattern == 1
|
|
|
440 && m_full_nelts.is_constant (&const_full_nelts)
|
|
|
441 && this->length () >= const_full_nelts
|
|
|
442 && (m_npatterns & 3) == 0
|
|
|
443 && stepped_sequence_p (m_npatterns / 4, const_full_nelts,
|
|
|
444 m_npatterns / 4))
|
|
|
445 {
|
|
|
446 reshape (m_npatterns / 4, 3);
|
|
|
447 while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
|
|
|
448 continue;
|
|
|
449 }
|
|
|
450 }
|
|
|
451 else
|
|
|
452 /* For the non-power-of-2 case, do a simple search up from 1. */
|
|
|
453 for (unsigned int i = 1; i <= m_npatterns / 2; ++i)
|
|
|
454 if (m_npatterns % i == 0 && try_npatterns (i))
|
|
|
455 break;
|
|
|
456 }
|
|
|
457
|
|
|
458 #endif
|
