Branch data Line data Source code
1 : : /* A class for building vector constant patterns.
2 : : Copyright (C) 2017-2025 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 : : Shape is the type that specifies the number of elements in the vector
49 : : and (where relevant) the type of each element.
50 : :
51 : : The derived class Derived provides the functionality of this class
52 : : for specific Ts. Derived needs to provide the following interface:
53 : :
54 : : bool equal_p (T elt1, T elt2) const;
55 : :
56 : : Return true if elements ELT1 and ELT2 are equal.
57 : :
58 : : bool allow_steps_p () const;
59 : :
60 : : Return true if a stepped representation is OK. We don't allow
61 : : linear series for anything other than integers, to avoid problems
62 : : with rounding.
63 : :
64 : : bool integral_p (T elt) const;
65 : :
66 : : Return true if element ELT can be interpreted as an integer.
67 : :
68 : : StepType step (T elt1, T elt2) const;
69 : :
70 : : Return the value of element ELT2 minus the value of element ELT1,
71 : : given integral_p (ELT1) && integral_p (ELT2). There is no fixed
72 : : choice of StepType.
73 : :
74 : : T apply_step (T base, unsigned int factor, StepType step) const;
75 : :
76 : : Return a vector element with the value BASE + FACTOR * STEP.
77 : :
78 : : bool can_elide_p (T elt) const;
79 : :
80 : : Return true if we can drop element ELT, even if the retained
81 : : elements are different. This is provided for TREE_OVERFLOW
82 : : handling.
83 : :
84 : : void note_representative (T *elt1_ptr, T elt2);
85 : :
86 : : Record that ELT2 is being elided, given that ELT1_PTR points to
87 : : the last encoded element for the containing pattern. This is
88 : : again provided for TREE_OVERFLOW handling.
89 : :
90 : : static poly_uint64 shape_nelts (Shape shape);
91 : :
92 : : Return the number of elements in SHAPE.
93 : :
94 : : The class provides additional functionality for the case in which
95 : : T can describe a vector constant as well as an individual element.
96 : : This functionality requires:
97 : :
98 : : static poly_uint64 nelts_of (T x);
99 : :
100 : : Return the number of elements in vector constant X.
101 : :
102 : : static unsigned int npatterns_of (T x);
103 : :
104 : : Return the number of patterns used to encode vector constant X.
105 : :
106 : : static unsigned int nelts_per_pattern_of (T x);
107 : :
108 : : Return the number of elements used to encode each pattern
109 : : in vector constant X. */
110 : :
111 : : template<typename T, typename Shape, typename Derived>
112 : 55763804 : class vector_builder : public auto_vec<T, 32>
113 : : {
114 : : public:
115 : : vector_builder ();
116 : :
117 : 7035849 : poly_uint64 full_nelts () const { return m_full_nelts; }
118 : 56084844 : unsigned int npatterns () const { return m_npatterns; }
119 : 52973296 : unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
120 : : unsigned int encoded_nelts () const;
121 : : bool encoded_full_vector_p () const;
122 : : T elt (unsigned int) const;
123 : : unsigned int count_dups (int, int, int) const;
124 : :
125 : : bool operator == (const Derived &) const;
126 : 1365775 : bool operator != (const Derived &x) const { return !operator == (x); }
127 : :
128 : : bool new_unary_operation (Shape, T, bool);
129 : : bool new_binary_operation (Shape, T, T, bool);
130 : :
131 : : void finalize ();
132 : :
133 : : static unsigned int binary_encoded_nelts (T, T);
134 : :
135 : : protected:
136 : : void new_vector (poly_uint64, unsigned int, unsigned int);
137 : : void reshape (unsigned int, unsigned int);
138 : : bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
139 : : bool stepped_sequence_p (unsigned int, unsigned int, unsigned int);
140 : : bool try_npatterns (unsigned int);
141 : :
142 : : private:
143 : : vector_builder (const vector_builder &);
144 : : vector_builder &operator= (const vector_builder &);
145 : : Derived *derived () { return static_cast<Derived *> (this); }
146 : : const Derived *derived () const;
147 : :
148 : : poly_uint64 m_full_nelts;
149 : : unsigned int m_npatterns;
150 : : unsigned int m_nelts_per_pattern;
151 : : };
152 : :
153 : : template<typename T, typename Shape, typename Derived>
154 : : inline const Derived *
155 : : vector_builder<T, Shape, Derived>::derived () const
156 : : {
157 : : return static_cast<const Derived *> (this);
158 : : }
159 : :
160 : : template<typename T, typename Shape, typename Derived>
161 : : inline
162 : 59215846 : vector_builder<T, Shape, Derived>::vector_builder ()
163 : 59215846 : : m_full_nelts (0),
164 : 59215846 : m_npatterns (0),
165 : 59215846 : m_nelts_per_pattern (0)
166 : : {}
167 : :
168 : : /* Return the number of elements that are explicitly encoded. The vec
169 : : starts with these explicitly-encoded elements and may contain additional
170 : : elided elements. */
171 : :
172 : : template<typename T, typename Shape, typename Derived>
173 : : inline unsigned int
174 : 1047574312 : vector_builder<T, Shape, Derived>::encoded_nelts () const
175 : : {
176 : 105015619 : return m_npatterns * m_nelts_per_pattern;
177 : : }
178 : :
179 : : /* Return true if every element of the vector is explicitly encoded. */
180 : :
181 : : template<typename T, typename Shape, typename Derived>
182 : : inline bool
183 : 8954508 : vector_builder<T, Shape, Derived>::encoded_full_vector_p () const
184 : : {
185 : 8954508 : return known_eq (m_npatterns * m_nelts_per_pattern, m_full_nelts);
186 : : }
187 : :
188 : : /* Start building a vector that has FULL_NELTS elements. Initially
189 : : encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */
190 : :
191 : : template<typename T, typename Shape, typename Derived>
192 : : void
193 : 57400252 : vector_builder<T, Shape, Derived>::new_vector (poly_uint64 full_nelts,
194 : : unsigned int npatterns,
195 : : unsigned int nelts_per_pattern)
196 : : {
197 : 57400252 : m_full_nelts = full_nelts;
198 : 57400252 : m_npatterns = npatterns;
199 : 57400252 : m_nelts_per_pattern = nelts_per_pattern;
200 : 57400252 : this->reserve (encoded_nelts ());
201 : 57400252 : this->truncate (0);
202 : 57400252 : }
203 : :
204 : : /* Return true if this vector and OTHER have the same elements and
205 : : are encoded in the same way. */
206 : :
207 : : template<typename T, typename Shape, typename Derived>
208 : : bool
209 : 1365775 : vector_builder<T, Shape, Derived>::operator == (const Derived &other) const
210 : : {
211 : 1365775 : if (maybe_ne (m_full_nelts, other.m_full_nelts)
212 : : || m_npatterns != other.m_npatterns
213 : 1365775 : || m_nelts_per_pattern != other.m_nelts_per_pattern)
214 : : return false;
215 : :
216 : 1364621 : unsigned int nelts = encoded_nelts ();
217 : 6852953 : for (unsigned int i = 0; i < nelts; ++i)
218 : 5505040 : if (!derived ()->equal_p ((*this)[i], other[i]))
219 : : return false;
220 : :
221 : : return true;
222 : : }
223 : :
224 : : /* Return the value of vector element I, which might or might not be
225 : : encoded explicitly. */
226 : :
227 : : template<typename T, typename Shape, typename Derived>
228 : : T
229 : 938977687 : vector_builder<T, Shape, Derived>::elt (unsigned int i) const
230 : : {
231 : : /* First handle elements that are already present in the underlying
232 : : vector, regardless of whether they're part of the encoding or not. */
233 : 938977687 : if (i < this->length ())
234 : 86037311 : return (*this)[i];
235 : :
236 : : /* Extrapolation is only possible if the encoding has been fully
237 : : populated. */
238 : 1705880752 : gcc_checking_assert (encoded_nelts () <= this->length ());
239 : :
240 : : /* Identify the pattern that contains element I and work out the index of
241 : : the last encoded element for that pattern. */
242 : 852940376 : unsigned int pattern = i % m_npatterns;
243 : 852940376 : unsigned int count = i / m_npatterns;
244 : 852940376 : unsigned int final_i = encoded_nelts () - m_npatterns + pattern;
245 : 852940376 : T final = (*this)[final_i];
246 : :
247 : : /* If there are no steps, the final encoded value is the right one. */
248 : 852940376 : if (m_nelts_per_pattern <= 2)
249 : 376277 : return final;
250 : :
251 : : /* Otherwise work out the value from the last two encoded elements. */
252 : 2493572 : T prev = (*this)[final_i - m_npatterns];
253 : 2493572 : return derived ()->apply_step (final, count - 2,
254 : 2628878 : derived ()->step (prev, final));
255 : : }
256 : :
257 : : /* Try to start building a new vector of shape SHAPE that holds the result of
258 : : a unary operation on vector constant VEC. ALLOW_STEPPED_P is true if the
259 : : operation can handle stepped encodings directly, without having to expand
260 : : the full sequence.
261 : :
262 : : Return true if the operation is possible, which it always is when
263 : : ALLOW_STEPPED_P is true. Leave the builder unchanged otherwise. */
264 : :
265 : : template<typename T, typename Shape, typename Derived>
266 : : bool
267 : 112858 : vector_builder<T, Shape, Derived>::new_unary_operation (Shape shape, T vec,
268 : : bool allow_stepped_p)
269 : : {
270 : 112858 : poly_uint64 full_nelts = Derived::shape_nelts (shape);
271 : 112858 : gcc_assert (known_eq (full_nelts, Derived::nelts_of (vec)));
272 : 112858 : unsigned int npatterns = Derived::npatterns_of (vec);
273 : 112858 : unsigned int nelts_per_pattern = Derived::nelts_per_pattern_of (vec);
274 : 112858 : if (!allow_stepped_p && nelts_per_pattern > 2)
275 : : {
276 : : if (!full_nelts.is_constant ())
277 : : return false;
278 : 7852 : npatterns = full_nelts.to_constant ();
279 : 7852 : nelts_per_pattern = 1;
280 : : }
281 : 112858 : derived ()->new_vector (shape, npatterns, nelts_per_pattern);
282 : : return true;
283 : : }
284 : :
285 : : /* Try to start building a new vector of shape SHAPE that holds the result of
286 : : a binary operation on vector constants VEC1 and VEC2. ALLOW_STEPPED_P is
287 : : true if the operation can handle stepped encodings directly, without
288 : : having to expand the full sequence.
289 : :
290 : : Return true if the operation is possible. Leave the builder unchanged
291 : : otherwise. */
292 : :
293 : : template<typename T, typename Shape, typename Derived>
294 : : bool
295 : 197693 : vector_builder<T, Shape, Derived>::new_binary_operation (Shape shape,
296 : : T vec1, T vec2,
297 : : bool allow_stepped_p)
298 : : {
299 : 197693 : poly_uint64 full_nelts = Derived::shape_nelts (shape);
300 : 197693 : gcc_assert (known_eq (full_nelts, Derived::nelts_of (vec1))
301 : : && known_eq (full_nelts, Derived::nelts_of (vec2)));
302 : : /* Conceptually we split the patterns in VEC1 and VEC2 until we have
303 : : an equal number for both. Each split pattern requires the same
304 : : number of elements per pattern as the original. E.g. splitting:
305 : :
306 : : { 1, 2, 3, ... }
307 : :
308 : : into two gives:
309 : :
310 : : { 1, 3, 5, ... }
311 : : { 2, 4, 6, ... }
312 : :
313 : : while splitting:
314 : :
315 : : { 1, 0, ... }
316 : :
317 : : into two gives:
318 : :
319 : : { 1, 0, ... }
320 : : { 0, 0, ... }. */
321 : 197693 : unsigned int npatterns
322 : 197693 : = least_common_multiple (Derived::npatterns_of (vec1),
323 : 197693 : Derived::npatterns_of (vec2));
324 : 197693 : unsigned int nelts_per_pattern
325 : 197693 : = MAX (Derived::nelts_per_pattern_of (vec1),
326 : : Derived::nelts_per_pattern_of (vec2));
327 : 197693 : if (!allow_stepped_p && nelts_per_pattern > 2)
328 : : {
329 : : if (!full_nelts.is_constant ())
330 : : return false;
331 : 6622 : npatterns = full_nelts.to_constant ();
332 : 6622 : nelts_per_pattern = 1;
333 : : }
334 : 197693 : derived ()->new_vector (shape, npatterns, nelts_per_pattern);
335 : : return true;
336 : : }
337 : :
338 : : /* Return the number of elements that the caller needs to operate on in
339 : : order to handle a binary operation on vector constants VEC1 and VEC2.
340 : : This static function is used instead of new_binary_operation if the
341 : : result of the operation is not a constant vector. */
342 : :
343 : : template<typename T, typename Shape, typename Derived>
344 : : unsigned int
345 : 0 : vector_builder<T, Shape, Derived>::binary_encoded_nelts (T vec1, T vec2)
346 : : {
347 : 0 : poly_uint64 nelts = Derived::nelts_of (vec1);
348 : 0 : gcc_assert (known_eq (nelts, Derived::nelts_of (vec2)));
349 : : /* See new_binary_operation for details. */
350 : 0 : unsigned int npatterns
351 : 0 : = least_common_multiple (Derived::npatterns_of (vec1),
352 : 0 : Derived::npatterns_of (vec2));
353 : 0 : unsigned int nelts_per_pattern
354 : 0 : = MAX (Derived::nelts_per_pattern_of (vec1),
355 : : Derived::nelts_per_pattern_of (vec2));
356 : : unsigned HOST_WIDE_INT const_nelts;
357 : 0 : if (nelts.is_constant (&const_nelts))
358 : 0 : return MIN (npatterns * nelts_per_pattern, const_nelts);
359 : : return npatterns * nelts_per_pattern;
360 : : }
361 : :
362 : : /* Return the number of leading duplicate elements in the range
363 : : [START:END:STEP]. The value is always at least 1. */
364 : :
365 : : template<typename T, typename Shape, typename Derived>
366 : : unsigned int
367 : : vector_builder<T, Shape, Derived>::count_dups (int start, int end,
368 : : int step) const
369 : : {
370 : : gcc_assert ((end - start) % step == 0);
371 : :
372 : : unsigned int ndups = 1;
373 : : for (int i = start + step;
374 : : i != end && derived ()->equal_p (elt (i), elt (start));
375 : : i += step)
376 : : ndups++;
377 : : return ndups;
378 : : }
379 : :
380 : : /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
381 : : but without changing the underlying vector. */
382 : :
383 : : template<typename T, typename Shape, typename Derived>
384 : : void
385 : 8528106 : vector_builder<T, Shape, Derived>::reshape (unsigned int npatterns,
386 : : unsigned int nelts_per_pattern)
387 : : {
388 : 8528106 : unsigned int old_encoded_nelts = encoded_nelts ();
389 : 8528106 : unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
390 : 8528106 : gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
391 : 8528106 : unsigned int next = new_encoded_nelts - npatterns;
392 : 21596483 : for (unsigned int i = new_encoded_nelts; i < old_encoded_nelts; ++i)
393 : : {
394 : 13068377 : derived ()->note_representative (&(*this)[next], (*this)[i]);
395 : 13068377 : next += 1;
396 : 13068377 : if (next == new_encoded_nelts)
397 : 6074178 : next -= npatterns;
398 : : }
399 : 8528106 : m_npatterns = npatterns;
400 : 8528106 : m_nelts_per_pattern = nelts_per_pattern;
401 : 8528106 : }
402 : :
403 : : /* Return true if elements [START, END) contain a repeating sequence of
404 : : STEP elements. */
405 : :
406 : : template<typename T, typename Shape, typename Derived>
407 : : bool
408 : 16044787 : vector_builder<T, Shape, Derived>::repeating_sequence_p (unsigned int start,
409 : : unsigned int end,
410 : : unsigned int step)
411 : : {
412 : 20868409 : for (unsigned int i = start; i < end - step; ++i)
413 : 14790864 : if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
414 : : return false;
415 : : return true;
416 : : }
417 : :
418 : : /* Return true if elements [START, END) contain STEP interleaved linear
419 : : series. */
420 : :
421 : : template<typename T, typename Shape, typename Derived>
422 : : bool
423 : 5997328 : vector_builder<T, Shape, Derived>::stepped_sequence_p (unsigned int start,
424 : : unsigned int end,
425 : : unsigned int step)
426 : : {
427 : 1118719 : if (!derived ()->allow_steps_p ())
428 : : return false;
429 : :
430 : 14956258 : for (unsigned int i = start + step * 2; i < end; ++i)
431 : : {
432 : 12505697 : T elt1 = (*this)[i - step * 2];
433 : 12505697 : T elt2 = (*this)[i - step];
434 : 12505697 : T elt3 = (*this)[i];
435 : :
436 : 12505697 : if (!derived ()->integral_p (elt1)
437 : 12505697 : || !derived ()->integral_p (elt2)
438 : 13840255 : || !derived ()->integral_p (elt3))
439 : 4878609 : return false;
440 : :
441 : 12505697 : if (maybe_ne (derived ()->step (elt1, elt2),
442 : 13840255 : derived ()->step (elt2, elt3)))
443 : : return false;
444 : :
445 : 8898491 : if (!derived ()->can_elide_p (elt3))
446 : : return false;
447 : : }
448 : : return true;
449 : : }
450 : :
451 : : /* Try to change the number of encoded patterns to NPATTERNS, returning
452 : : true on success. */
453 : :
454 : : template<typename T, typename Shape, typename Derived>
455 : : bool
456 : 12591233 : vector_builder<T, Shape, Derived>::try_npatterns (unsigned int npatterns)
457 : : {
458 : 12591233 : if (m_nelts_per_pattern == 1)
459 : : {
460 : : /* See whether NPATTERNS is valid with the current 1-element-per-pattern
461 : : encoding. */
462 : 6699502 : if (repeating_sequence_p (0, encoded_nelts (), npatterns))
463 : : {
464 : 1257409 : reshape (npatterns, 1);
465 : 1257409 : return true;
466 : : }
467 : :
468 : : /* We can only increase the number of elements per pattern if all
469 : : elements are still encoded explicitly. */
470 : 5442093 : if (!encoded_full_vector_p ())
471 : : return false;
472 : : }
473 : :
474 : 10506455 : if (m_nelts_per_pattern <= 2)
475 : : {
476 : : /* See whether NPATTERNS is valid with a 2-element-per-pattern
477 : : encoding. */
478 : 8329020 : if (repeating_sequence_p (npatterns, encoded_nelts (), npatterns))
479 : : {
480 : 4816940 : reshape (npatterns, 2);
481 : 4816940 : return true;
482 : : }
483 : :
484 : : /* We can only increase the number of elements per pattern if all
485 : : elements are still encoded explicitly. */
486 : 3512080 : if (!encoded_full_vector_p ())
487 : : return false;
488 : : }
489 : :
490 : 5654570 : if (m_nelts_per_pattern <= 3)
491 : : {
492 : : /* See whether we have NPATTERNS interleaved linear series,
493 : : giving a 3-element-per-pattern encoding. */
494 : 5654570 : if (stepped_sequence_p (npatterns, encoded_nelts (), npatterns))
495 : : {
496 : 2450510 : reshape (npatterns, 3);
497 : 2450510 : return true;
498 : : }
499 : : return false;
500 : : }
501 : :
502 : 0 : gcc_unreachable ();
503 : : }
504 : :
505 : : /* Replace the current encoding with the canonical form. */
506 : :
507 : : template<typename T, typename Shape, typename Derived>
508 : : void
509 : 52617481 : vector_builder<T, Shape, Derived>::finalize ()
510 : : {
511 : : /* The encoding requires the same number of elements to come from each
512 : : pattern. */
513 : 105234962 : gcc_assert (multiple_p (m_full_nelts, m_npatterns));
514 : :
515 : : /* Allow the caller to build more elements than necessary. For example,
516 : : it's often convenient to build a stepped vector from the natural
517 : : encoding of three elements even if the vector itself only has two. */
518 : : unsigned HOST_WIDE_INT const_full_nelts;
519 : 52617481 : if (m_full_nelts.is_constant (&const_full_nelts)
520 : 52617481 : && const_full_nelts <= encoded_nelts ())
521 : : {
522 : 8064510 : m_npatterns = const_full_nelts;
523 : 8064510 : m_nelts_per_pattern = 1;
524 : : }
525 : :
526 : : /* Try to whittle down the number of elements per pattern. That is:
527 : :
528 : : 1. If we have stepped patterns whose steps are all 0, reduce the
529 : : number of elements per pattern from 3 to 2.
530 : :
531 : : 2. If we have background fill values that are the same as the
532 : : foreground values, reduce the number of elements per pattern
533 : : from 2 to 1. */
534 : 52620677 : while (m_nelts_per_pattern > 1
535 : 52620677 : && repeating_sequence_p (encoded_nelts () - m_npatterns * 2,
536 : : encoded_nelts (), m_npatterns))
537 : : /* The last two sequences of M_NPATTERNS elements are equal,
538 : : so remove the last one. */
539 : 3196 : reshape (m_npatterns, m_nelts_per_pattern - 1);
540 : :
541 : 105234962 : if (pow2p_hwi (m_npatterns))
542 : : {
543 : : /* Try to halve the number of patterns while doing so gives a
544 : : valid pattern. This approach is linear in the number of
545 : : elements, whereas searcing from 1 up would be O(n*log(n)).
546 : :
547 : : Each halving step tries to keep the number of elements per pattern
548 : : the same. If that isn't possible, and if all elements are still
549 : : explicitly encoded, the halving step can instead increase the number
550 : : of elements per pattern.
551 : :
552 : : E.g. for:
553 : :
554 : : { 0, 2, 3, 4, 5, 6, 7, 8 } npatterns == 8 full_nelts == 8
555 : :
556 : : we first realize that the second half of the sequence is not
557 : : equal to the first, so we cannot maintain 1 element per pattern
558 : : for npatterns == 4. Instead we halve the number of patterns
559 : : and double the number of elements per pattern, treating this
560 : : as a "foreground" { 0, 2, 3, 4 } against a "background" of
561 : : { 5, 6, 7, 8 | 5, 6, 7, 8 ... }:
562 : :
563 : : { 0, 2, 3, 4 | 5, 6, 7, 8 } npatterns == 4
564 : :
565 : : Next we realize that this is *not* a foreround of { 0, 2 }
566 : : against a background of { 3, 4 | 3, 4 ... }, so the only
567 : : remaining option for reducing the number of patterns is
568 : : to use a foreground of { 0, 2 } against a stepped background
569 : : of { 1, 2 | 3, 4 | 5, 6 ... }. This is valid because we still
570 : : haven't elided any elements:
571 : :
572 : : { 0, 2 | 3, 4 | 5, 6 } npatterns == 2
573 : :
574 : : This in turn can be reduced to a foreground of { 0 } against a
575 : : stepped background of { 1 | 2 | 3 ... }:
576 : :
577 : : { 0 | 2 | 3 } npatterns == 1
578 : :
579 : : This last step would not have been possible for:
580 : :
581 : : { 0, 0 | 3, 4 | 5, 6 } npatterns == 2. */
582 : 61142064 : while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
583 : 8524679 : continue;
584 : :
585 : : /* Builders of arbitrary fixed-length vectors can use:
586 : :
587 : : new_vector (x, x, 1)
588 : :
589 : : so that every element is specified explicitly. Handle cases
590 : : that are actually wrapping series, like { 0, 1, 2, 3, 0, 1, 2, 3 }
591 : : would be for 2-bit elements. We'll have treated them as
592 : : duplicates in the loop above. */
593 : 52617469 : if (m_nelts_per_pattern == 1
594 : 46989748 : && m_full_nelts.is_constant (&const_full_nelts)
595 : 93979496 : && this->length () >= const_full_nelts
596 : 3449846 : && (m_npatterns & 3) == 0
597 : 52960143 : && stepped_sequence_p (m_npatterns / 4, const_full_nelts,
598 : : m_npatterns / 4))
599 : : {
600 : 51 : reshape (m_npatterns / 4, 3);
601 : 135 : while ((m_npatterns & 1) == 0 && try_npatterns (m_npatterns / 2))
602 : 84 : continue;
603 : : }
604 : : }
605 : : else
606 : : /* For the non-power-of-2 case, do a simple search up from 1. */
607 : 168 : for (unsigned int i = 1; i <= m_npatterns / 2; ++i)
608 : 168 : if (m_npatterns % i == 0 && try_npatterns (i))
609 : : break;
610 : 52617481 : }
611 : :
612 : : #endif
|
