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