Warning: That file was not part of the compilation database. It may have many parsing errors.

1/* A class for building vector constant patterns.
2 Copyright (C) 2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
87template<typename T, typename Derived>
88class vector_builder : public auto_vec<T, 32>
89{
90public:
91 vector_builder ();
92
93 unsigned int 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 void finalize ();
101
102protected:
103 void new_vector (unsigned int, unsigned int, unsigned int);
104 void reshape (unsigned int, unsigned int);
105 bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
106 bool stepped_sequence_p (unsigned int, unsigned int, unsigned int);
107 bool try_npatterns (unsigned int);
108
109private:
110 vector_builder (const vector_builder &);
111 vector_builder &operator= (const vector_builder &);
112 Derived *derived () { return static_cast<Derived *> (this); }
113 const Derived *derived () const;
114
115 unsigned int m_full_nelts;
116 unsigned int m_npatterns;
117 unsigned int m_nelts_per_pattern;
118};
119
120template<typename T, typename Derived>
121inline const Derived *
122vector_builder<T, Derived>::derived () const
123{
124 return static_cast<const Derived *> (this);
125}
126
127template<typename T, typename Derived>
128inline
129vector_builder<T, Derived>::vector_builder ()
130 : m_full_nelts (0),
131 m_npatterns (0),
132 m_nelts_per_pattern (0)
133{}
134
135/* Return the number of elements that are explicitly encoded. The vec
136 starts with these explicitly-encoded elements and may contain additional
137 elided elements. */
138
139template<typename T, typename Derived>
140inline unsigned int
141vector_builder<T, Derived>::encoded_nelts () const
142{
143 return m_npatterns * m_nelts_per_pattern;
144}
145
146/* Return true if every element of the vector is explicitly encoded. */
147
148template<typename T, typename Derived>
149inline bool
150vector_builder<T, Derived>::encoded_full_vector_p () const
151{
152 return m_npatterns * m_nelts_per_pattern == m_full_nelts;
153}
154
155/* Start building a vector that has FULL_NELTS elements. Initially
156 encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */
157
158template<typename T, typename Derived>
159void
160vector_builder<T, Derived>::new_vector (unsigned int full_nelts,
161 unsigned int npatterns,
162 unsigned int nelts_per_pattern)
163{
164 m_full_nelts = full_nelts;
165 m_npatterns = npatterns;
166 m_nelts_per_pattern = nelts_per_pattern;
167 this->reserve (encoded_nelts ());
168 this->truncate (0);
169}
170
171/* Return the value of vector element I, which might or might not be
172 encoded explicitly. */
173
174template<typename T, typename Derived>
175T
176vector_builder<T, Derived>::elt (unsigned int i) const
177{
178 /* This only makes sense if the encoding has been fully populated. */
179 gcc_checking_assert (encoded_nelts () <= this->length ());
180
181 /* First handle elements that are already present in the underlying
182 vector, regardless of whether they're part of the encoding or not. */
183 if (i < this->length ())
184 return (*this)[i];
185
186 /* Identify the pattern that contains element I and work out the index of
187 the last encoded element for that pattern. */
188 unsigned int pattern = i % m_npatterns;
189 unsigned int count = i / m_npatterns;
190 unsigned int final_i = encoded_nelts () - m_npatterns + pattern;
191 T final = (*this)[final_i];
192
193 /* If there are no steps, the final encoded value is the right one. */
194 if (m_nelts_per_pattern <= 2)
195 return final;
196
197 /* Otherwise work out the value from the last two encoded elements. */
198 T prev = (*this)[final_i - m_npatterns];
199 return derived ()->apply_step (final, count - 2,
200 derived ()->step (prev, final));
201}
202
203/* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
204 but without changing the underlying vector. */
205
206template<typename T, typename Derived>
207void
208vector_builder<T, Derived>::reshape (unsigned int npatterns,
209 unsigned int nelts_per_pattern)
210{
211 unsigned int old_encoded_nelts = encoded_nelts ();
212 unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
213 gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
214 unsigned int next = new_encoded_nelts - npatterns;
215 for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
216 {
217 derived ()->note_representative (&(*this)[next], (*this)[i]);
218 next += 1;
219 if (next == new_encoded_nelts)
220 next -= npatterns;
221 }
222 m_npatterns = npatterns;
223 m_nelts_per_pattern = nelts_per_pattern;
224}
225
226/* Return true if elements [START, END) contain a repeating sequence of
227 STEP elements. */
228
229template<typename T, typename Derived>
230bool
231vector_builder<T, Derived>::repeating_sequence_p (unsigned int start,
232 unsigned int end,
233 unsigned int step)
234{
235 for (unsigned int i = start; i < end - step; ++i)
236 if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
237 return false;
238 return true;
239}
240
241/* Return true if elements [START, END) contain STEP interleaved linear
242 series. */
243
244template<typename T, typename Derived>
245bool
246vector_builder<T, Derived>::stepped_sequence_p (unsigned int start,
247 unsigned int end,
248 unsigned int step)
249{
250 if (!derived ()->allow_steps_p ())
251 return false;
252
253 for (unsigned int i = start + step * 2; i < end; ++i)
254 {
255 T elt1 = (*this)[i - step * 2];
256 T elt2 = (*this)[i - step];
257 T elt3 = (*this)[i];
258
259 if (!derived ()->integral_p (elt1)
260 || !derived ()->integral_p (elt2)
261 || !derived ()->integral_p (elt3))
262 return false;
263
264 if (derived ()->step (elt1, elt2) != derived ()->step (elt2, elt3))
265 return false;
266
267 if (!derived ()->can_elide_p (elt3))
268 return false;
269 }
270 return true;
271}
272
273/* Try to change the number of encoded patterns to NPATTERNS, returning
274 true on success. */
275
276template<typename T, typename Derived>
277bool
278vector_builder<T, Derived>::try_npatterns (unsigned int npatterns)
279{
280 if (m_nelts_per_pattern == 1)
281 {
282 /* See whether NPATTERNS is valid with the current 1-element-per-pattern
283 encoding. */
284 if (repeating_sequence_p (0, encoded_nelts (), npatterns))
285 {
286 reshape (npatterns, 1);
287 return true;
288 }
289
290 /* We can only increase the number of elements per pattern if all
291 elements are still encoded explicitly. */
292 if (!encoded_full_vector_p ())
293 return false;
294 }
295
296 if (m_nelts_per_pattern <= 2)
297 {
298 /* See whether NPATTERNS is valid with a 2-element-per-pattern
299 encoding. */
300 if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns))
301 {
302 reshape (npatterns, 2);
303 return true;
304 }
305
306 /* We can only increase the number of elements per pattern if all
307 elements are still encoded explicitly. */
308 if (!encoded_full_vector_p ())
309 return false;
310 }
311
312 if (m_nelts_per_pattern <= 3)
313 {
314 /* See whether we have NPATTERNS interleaved linear series,
315 giving a 3-element-per-pattern encoding. */
316 if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns))
317 {
318 reshape (npatterns, 3);
319 return true;
320 }
321 return false;
322 }
323
324 gcc_unreachable ();
325}
326
327/* Replace the current encoding with the canonical form. */
328
329template<typename T, typename Derived>
330void
331vector_builder<T, Derived>::finalize ()
332{
333 /* The encoding requires the same number of elements to come from each
334 pattern. */
335 gcc_assert (m_full_nelts % m_npatterns == 0);
336
337 /* Allow the caller to build more elements than necessary. For example,
338 it's often convenient to build a stepped vector from the natural
339 encoding of three elements even if the vector itself only has two. */
340 if (m_full_nelts <= encoded_nelts ())
341 {
342 m_npatterns = m_full_nelts;
343 m_nelts_per_pattern = 1;
344 }
345
346 /* Try to whittle down the number of elements per pattern. That is:
347
348 1. If we have stepped patterns whose steps are all 0, reduce the
349 number of elements per pattern from 3 to 2.
350
351 2. If we have background fill values that are the same as the
352 foreground values, reduce the number of elements per pattern
353 from 2 to 1. */
354 while (m_nelts_per_pattern > 1
355 && repeating_sequence_p (encoded_nelts () - m_npatterns * 2,
356 encoded_nelts (), m_npatterns))
357 /* The last two sequences of M_NPATTERNS elements are equal,
358 so remove the last one. */
359 reshape (m_npatterns, m_nelts_per_pattern - 1);
360
361 if (pow2p_hwi (m_npatterns))
362 {
363 /* Try to halve the number of patterns while doing so gives a
364 valid pattern. This approach is linear in the number of
365 elements, whereas searcing from 1 up would be O(n*log(n)).
366
367 Each halving step tries to keep the number of elements per pattern
368 the same. If that isn't possible, and if all elements are still
369 explicitly encoded, the halving step can instead increase the number
370 of elements per pattern.
371
372 E.g. for:
373
374 { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8
375
376 we first realize that the second half of the sequence is not
377 equal to the first, so we cannot maintain 1 element per pattern
378 for npatterns == 4. Instead we halve the number of patterns
379 and double the number of elements per pattern, treating this
380 as a "foreground" { 0, 2, 3, 4 } against a "background" of
381 { 5, 6, 7, 8 | 5, 6, 7, 8 ... }:
382
383 { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4
384
385 Next we realize that this is *not* a foreround of { 0, 2 }
386 against a background of { 3, 4 | 3, 4 ... }, so the only
387 remaining option for reducing the number of patterns is
388 to use a foreground of { 0, 2 } against a stepped background
389 of { 1, 2 | 3, 4 | 5, 6 ... }. This is valid because we still
390 haven't elided any elements:
391
392 { 0, 2 | 3, 4 | 5, 6 } npatterns == 2
393
394 This in turn can be reduced to a foreground of { 0 } against a
395 stepped background of { 1 | 2 | 3 ... }:
396
397 { 0 | 2 | 3 } npatterns == 1
398
399 This last step would not have been possible for:
400
401 { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */
402 while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
403 continue;
404
405 /* Builders of arbitrary fixed-length vectors can use:
406
407 new_vector (x, x, 1)
408
409 so that every element is specified explicitly. Handle cases
410 that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 }
411 would be for 2-bit elements. We'll have treated them as
412 duplicates in the loop above. */
413 if (m_nelts_per_pattern == 1
414 && this->length () >= m_full_nelts
415 && (m_npatterns & 3) == 0
416 && stepped_sequence_p (m_npatterns / 4, m_full_nelts,
417 m_npatterns / 4))
418 {
419 reshape (m_npatterns / 4, 3);
420 while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
421 continue;
422 }
423 }
424 else
425 /* For the non-power-of-2 case, do a simple search up from 1. */
426 for (unsigned int i = 1; i <= m_npatterns / 2; ++i)
427 if (m_npatterns % i == 0 && try_npatterns (i))
428 break;
429}
430
431#endif
432

Warning: That file was not part of the compilation database. It may have many parsing errors.