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
full_nelts()93 poly_uint64 full_nelts () const { return m_full_nelts; }
npatterns()94 unsigned int npatterns () const { return m_npatterns; }
nelts_per_pattern()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 &);
derived()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 *
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
vector_builder()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
encoded_nelts()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
encoded_full_vector_p()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
new_vector(poly_uint64 full_nelts,unsigned int npatterns,unsigned int nelts_per_pattern)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
elt(unsigned int i)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
reshape(unsigned int npatterns,unsigned int nelts_per_pattern)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
repeating_sequence_p(unsigned int start,unsigned int end,unsigned int step)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
stepped_sequence_p(unsigned int start,unsigned int end,unsigned int step)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
try_npatterns(unsigned int npatterns)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
finalize()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
459