Mercurial > hg > CbC > CbC_gcc

comparison gcc/vector-builder.h @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* A class for building vector constant patterns. 1 /* A class for building vector constant patterns.
2 Copyright (C) 2017-2018 Free Software Foundation, Inc. 2 Copyright (C) 2017-2020 Free Software Foundation, Inc.
3 3
4 This file is part of GCC. 4 This file is part of GCC.
5 5
6 GCC is free software; you can redistribute it and/or modify it under 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 7 the terms of the GNU General Public License as published by the Free
43 2. It can be used to build a vector that already has a known encoding. 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 44 This is preferred since it is more efficient and copes with
45 variable-length vectors. finalize () then canonicalizes the encoding 45 variable-length vectors. finalize () then canonicalizes the encoding
46 to a simpler form if possible. 46 to a simpler form if possible.
47 47
48 The derived class Derived provides this functionality for specific Ts. 48 Shape is the type that specifies the number of elements in the vector
49 Derived needs to provide the following interface: 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:
50 53
51 bool equal_p (T elt1, T elt2) const; 54 bool equal_p (T elt1, T elt2) const;
52 55
53 Return true if elements ELT1 and ELT2 are equal. 56 Return true if elements ELT1 and ELT2 are equal.
54 57
80 83
81 void note_representative (T *elt1_ptr, T elt2); 84 void note_representative (T *elt1_ptr, T elt2);
82 85
83 Record that ELT2 is being elided, given that ELT1_PTR points to 86 Record that ELT2 is being elided, given that ELT1_PTR points to
84 the last encoded element for the containing pattern. This is 87 the last encoded element for the containing pattern. This is
85 again provided for TREE_OVERFLOW handling. */ 88 again provided for TREE_OVERFLOW handling.
86 89
87 template<typename T, typename Derived> 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>
88 class vector_builder : public auto_vec<T, 32> 112 class vector_builder : public auto_vec<T, 32>
89 { 113 {
90 public: 114 public:
91 vector_builder (); 115 vector_builder ();
92 116
94 unsigned int npatterns () const { return m_npatterns; } 118 unsigned int npatterns () const { return m_npatterns; }
95 unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; } 119 unsigned int nelts_per_pattern () const { return m_nelts_per_pattern; }
96 unsigned int encoded_nelts () const; 120 unsigned int encoded_nelts () const;
97 bool encoded_full_vector_p () const; 121 bool encoded_full_vector_p () const;
98 T elt (unsigned int) const; 122 T elt (unsigned int) const;
123 unsigned int count_dups (int, int, int) const;
99 124
100 bool operator == (const Derived &) const; 125 bool operator == (const Derived &) const;
101 bool operator != (const Derived &x) const { return !operator == (x); } 126 bool operator != (const Derived &x) const { return !operator == (x); }
102 127
128 bool new_unary_operation (Shape, T, bool);
129 bool new_binary_operation (Shape, T, T, bool);
130
103 void finalize (); 131 void finalize ();
132
133 static unsigned int binary_encoded_nelts (T, T);
104 134
105 protected: 135 protected:
106 void new_vector (poly_uint64, unsigned int, unsigned int); 136 void new_vector (poly_uint64, unsigned int, unsigned int);
107 void reshape (unsigned int, unsigned int); 137 void reshape (unsigned int, unsigned int);
108 bool repeating_sequence_p (unsigned int, unsigned int, unsigned int); 138 bool repeating_sequence_p (unsigned int, unsigned int, unsigned int);
118 poly_uint64 m_full_nelts; 148 poly_uint64 m_full_nelts;
119 unsigned int m_npatterns; 149 unsigned int m_npatterns;
120 unsigned int m_nelts_per_pattern; 150 unsigned int m_nelts_per_pattern;
121 }; 151 };
122 152
123 template<typename T, typename Derived> 153 template<typename T, typename Shape, typename Derived>
124 inline const Derived * 154 inline const Derived *
125 vector_builder<T, Derived>::derived () const 155 vector_builder<T, Shape, Derived>::derived () const
126 { 156 {
127 return static_cast<const Derived *> (this); 157 return static_cast<const Derived *> (this);
128 } 158 }
129 159
130 template<typename T, typename Derived> 160 template<typename T, typename Shape, typename Derived>
131 inline 161 inline
132 vector_builder<T, Derived>::vector_builder () 162 vector_builder<T, Shape, Derived>::vector_builder ()
133 : m_full_nelts (0), 163 : m_full_nelts (0),
134 m_npatterns (0), 164 m_npatterns (0),
135 m_nelts_per_pattern (0) 165 m_nelts_per_pattern (0)
136 {} 166 {}
137 167
138 /* Return the number of elements that are explicitly encoded. The vec 168 /* Return the number of elements that are explicitly encoded. The vec
139 starts with these explicitly-encoded elements and may contain additional 169 starts with these explicitly-encoded elements and may contain additional
140 elided elements. */ 170 elided elements. */
141 171
142 template<typename T, typename Derived> 172 template<typename T, typename Shape, typename Derived>
143 inline unsigned int 173 inline unsigned int
144 vector_builder<T, Derived>::encoded_nelts () const 174 vector_builder<T, Shape, Derived>::encoded_nelts () const
145 { 175 {
146 return m_npatterns * m_nelts_per_pattern; 176 return m_npatterns * m_nelts_per_pattern;
147 } 177 }
148 178
149 /* Return true if every element of the vector is explicitly encoded. */ 179 /* Return true if every element of the vector is explicitly encoded. */
150 180
151 template<typename T, typename Derived> 181 template<typename T, typename Shape, typename Derived>
152 inline bool 182 inline bool
153 vector_builder<T, Derived>::encoded_full_vector_p () const 183 vector_builder<T, Shape, Derived>::encoded_full_vector_p () const
154 { 184 {
155 return known_eq (m_npatterns * m_nelts_per_pattern, m_full_nelts); 185 return known_eq (m_npatterns * m_nelts_per_pattern, m_full_nelts);
156 } 186 }
157 187
158 /* Start building a vector that has FULL_NELTS elements. Initially 188 /* Start building a vector that has FULL_NELTS elements. Initially
159 encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */ 189 encode it using NPATTERNS patterns with NELTS_PER_PATTERN each. */
160 190
161 template<typename T, typename Derived> 191 template<typename T, typename Shape, typename Derived>
162 void 192 void
163 vector_builder<T, Derived>::new_vector (poly_uint64 full_nelts, 193 vector_builder<T, Shape, Derived>::new_vector (poly_uint64 full_nelts,
164 unsigned int npatterns, 194 unsigned int npatterns,
165 unsigned int nelts_per_pattern) 195 unsigned int nelts_per_pattern)
166 { 196 {
167 m_full_nelts = full_nelts; 197 m_full_nelts = full_nelts;
168 m_npatterns = npatterns; 198 m_npatterns = npatterns;
169 m_nelts_per_pattern = nelts_per_pattern; 199 m_nelts_per_pattern = nelts_per_pattern;
170 this->reserve (encoded_nelts ()); 200 this->reserve (encoded_nelts ());
172 } 202 }
173 203
174 /* Return true if this vector and OTHER have the same elements and 204 /* Return true if this vector and OTHER have the same elements and
175 are encoded in the same way. */ 205 are encoded in the same way. */
176 206
177 template<typename T, typename Derived> 207 template<typename T, typename Shape, typename Derived>
178 bool 208 bool
179 vector_builder<T, Derived>::operator == (const Derived &other) const 209 vector_builder<T, Shape, Derived>::operator == (const Derived &other) const
180 { 210 {
181 if (maybe_ne (m_full_nelts, other.m_full_nelts) 211 if (maybe_ne (m_full_nelts, other.m_full_nelts)
182 || m_npatterns != other.m_npatterns 212 || m_npatterns != other.m_npatterns
183 || m_nelts_per_pattern != other.m_nelts_per_pattern) 213 || m_nelts_per_pattern != other.m_nelts_per_pattern)
184 return false; 214 return false;
192 } 222 }
193 223
194 /* Return the value of vector element I, which might or might not be 224 /* Return the value of vector element I, which might or might not be
195 encoded explicitly. */ 225 encoded explicitly. */
196 226
197 template<typename T, typename Derived> 227 template<typename T, typename Shape, typename Derived>
198 T 228 T
199 vector_builder<T, Derived>::elt (unsigned int i) const 229 vector_builder<T, Shape, Derived>::elt (unsigned int i) const
200 { 230 {
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 231 /* First handle elements that are already present in the underlying
205 vector, regardless of whether they're part of the encoding or not. */ 232 vector, regardless of whether they're part of the encoding or not. */
206 if (i < this->length ()) 233 if (i < this->length ())
207 return (*this)[i]; 234 return (*this)[i];
235
236 /* Extrapolation is only possible if the encoding has been fully
237 populated. */
238 gcc_checking_assert (encoded_nelts () <= this->length ());
208 239
209 /* Identify the pattern that contains element I and work out the index of 240 /* Identify the pattern that contains element I and work out the index of
210 the last encoded element for that pattern. */ 241 the last encoded element for that pattern. */
211 unsigned int pattern = i % m_npatterns; 242 unsigned int pattern = i % m_npatterns;
212 unsigned int count = i / m_npatterns; 243 unsigned int count = i / m_npatterns;
221 T prev = (*this)[final_i - m_npatterns]; 252 T prev = (*this)[final_i - m_npatterns];
222 return derived ()->apply_step (final, count - 2, 253 return derived ()->apply_step (final, count - 2,
223 derived ()->step (prev, final)); 254 derived ()->step (prev, final));
224 } 255 }
225 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 vector_builder<T, Shape, Derived>::new_unary_operation (Shape shape, T vec,
268 bool allow_stepped_p)
269 {
270 poly_uint64 full_nelts = Derived::shape_nelts (shape);
271 gcc_assert (known_eq (full_nelts, Derived::nelts_of (vec)));
272 unsigned int npatterns = Derived::npatterns_of (vec);
273 unsigned int nelts_per_pattern = Derived::nelts_per_pattern_of (vec);
274 if (!allow_stepped_p && nelts_per_pattern > 2)
275 {
276 if (!full_nelts.is_constant ())
277 return false;
278 npatterns = full_nelts.to_constant ();
279 nelts_per_pattern = 1;
280 }
281 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 vector_builder<T, Shape, Derived>::new_binary_operation (Shape shape,
296 T vec1, T vec2,
297 bool allow_stepped_p)
298 {
299 poly_uint64 full_nelts = Derived::shape_nelts (shape);
300 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 unsigned int npatterns
322 = least_common_multiple (Derived::npatterns_of (vec1),
323 Derived::npatterns_of (vec2));
324 unsigned int nelts_per_pattern
325 = MAX (Derived::nelts_per_pattern_of (vec1),
326 Derived::nelts_per_pattern_of (vec2));
327 if (!allow_stepped_p && nelts_per_pattern > 2)
328 {
329 if (!full_nelts.is_constant ())
330 return false;
331 npatterns = full_nelts.to_constant ();
332 nelts_per_pattern = 1;
333 }
334 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 vector_builder<T, Shape, Derived>::binary_encoded_nelts (T vec1, T vec2)
346 {
347 poly_uint64 nelts = Derived::nelts_of (vec1);
348 gcc_assert (known_eq (nelts, Derived::nelts_of (vec2)));
349 /* See new_binary_operation for details. */
350 unsigned int npatterns
351 = least_common_multiple (Derived::npatterns_of (vec1),
352 Derived::npatterns_of (vec2));
353 unsigned int nelts_per_pattern
354 = MAX (Derived::nelts_per_pattern_of (vec1),
355 Derived::nelts_per_pattern_of (vec2));
356 unsigned HOST_WIDE_INT const_nelts;
357 if (nelts.is_constant (&const_nelts))
358 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
226 /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each, 380 /* Change the encoding to NPATTERNS patterns of NELTS_PER_PATTERN each,
227 but without changing the underlying vector. */ 381 but without changing the underlying vector. */
228 382
229 template<typename T, typename Derived> 383 template<typename T, typename Shape, typename Derived>
230 void 384 void
231 vector_builder<T, Derived>::reshape (unsigned int npatterns, 385 vector_builder<T, Shape, Derived>::reshape (unsigned int npatterns,
232 unsigned int nelts_per_pattern) 386 unsigned int nelts_per_pattern)
233 { 387 {
234 unsigned int old_encoded_nelts = encoded_nelts (); 388 unsigned int old_encoded_nelts = encoded_nelts ();
235 unsigned int new_encoded_nelts = npatterns * nelts_per_pattern; 389 unsigned int new_encoded_nelts = npatterns * nelts_per_pattern;
236 gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts); 390 gcc_checking_assert (new_encoded_nelts <= old_encoded_nelts);
237 unsigned int next = new_encoded_nelts - npatterns; 391 unsigned int next = new_encoded_nelts - npatterns;
247 } 401 }
248 402
249 /* Return true if elements [START, END) contain a repeating sequence of 403 /* Return true if elements [START, END) contain a repeating sequence of
250 STEP elements. */ 404 STEP elements. */
251 405
252 template<typename T, typename Derived> 406 template<typename T, typename Shape, typename Derived>
253 bool 407 bool
254 vector_builder<T, Derived>::repeating_sequence_p (unsigned int start, 408 vector_builder<T, Shape, Derived>::repeating_sequence_p (unsigned int start,
255 unsigned int end, 409 unsigned int end,
256 unsigned int step) 410 unsigned int step)
257 { 411 {
258 for (unsigned int i = start; i < end - step; ++i) 412 for (unsigned int i = start; i < end - step; ++i)
259 if (!derived ()->equal_p ((*this)[i], (*this)[i + step])) 413 if (!derived ()->equal_p ((*this)[i], (*this)[i + step]))
260 return false; 414 return false;
261 return true; 415 return true;
262 } 416 }
263 417
264 /* Return true if elements [START, END) contain STEP interleaved linear 418 /* Return true if elements [START, END) contain STEP interleaved linear
265 series. */ 419 series. */
266 420
267 template<typename T, typename Derived> 421 template<typename T, typename Shape, typename Derived>
268 bool 422 bool
269 vector_builder<T, Derived>::stepped_sequence_p (unsigned int start, 423 vector_builder<T, Shape, Derived>::stepped_sequence_p (unsigned int start,
270 unsigned int end, 424 unsigned int end,
271 unsigned int step) 425 unsigned int step)
272 { 426 {
273 if (!derived ()->allow_steps_p ()) 427 if (!derived ()->allow_steps_p ())
274 return false; 428 return false;
275 429
276 for (unsigned int i = start + step * 2; i < end; ++i) 430 for (unsigned int i = start + step * 2; i < end; ++i)
295 } 449 }
296 450
297 /* Try to change the number of encoded patterns to NPATTERNS, returning 451 /* Try to change the number of encoded patterns to NPATTERNS, returning
298 true on success. */ 452 true on success. */
299 453
300 template<typename T, typename Derived> 454 template<typename T, typename Shape, typename Derived>
301 bool 455 bool
302 vector_builder<T, Derived>::try_npatterns (unsigned int npatterns) 456 vector_builder<T, Shape, Derived>::try_npatterns (unsigned int npatterns)
303 { 457 {
304 if (m_nelts_per_pattern == 1) 458 if (m_nelts_per_pattern == 1)
305 { 459 {
306 /* See whether NPATTERNS is valid with the current 1-element-per-pattern 460 /* See whether NPATTERNS is valid with the current 1-element-per-pattern
307 encoding. */ 461 encoding. */
348 gcc_unreachable (); 502 gcc_unreachable ();
349 } 503 }
350 504
351 /* Replace the current encoding with the canonical form. */ 505 /* Replace the current encoding with the canonical form. */
352 506
353 template<typename T, typename Derived> 507 template<typename T, typename Shape, typename Derived>
354 void 508 void
355 vector_builder<T, Derived>::finalize () 509 vector_builder<T, Shape, Derived>::finalize ()
356 { 510 {
357 /* The encoding requires the same number of elements to come from each 511 /* The encoding requires the same number of elements to come from each
358 pattern. */ 512 pattern. */
359 gcc_assert (multiple_p (m_full_nelts, m_npatterns)); 513 gcc_assert (multiple_p (m_full_nelts, m_npatterns));
360 514