Line data Source code
1 : /* A representation of vector permutation indices.
2 : Copyright (C) 2017-2026 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 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "vec-perm-indices.h"
24 : #include "tree.h"
25 : #include "fold-const.h"
26 : #include "tree-vector-builder.h"
27 : #include "backend.h"
28 : #include "rtl.h"
29 : #include "memmodel.h"
30 : #include "emit-rtl.h"
31 : #include "selftest.h"
32 : #include "rtx-vector-builder.h"
33 :
34 :
35 : /* Switch to a new permutation vector that selects between NINPUTS vector
36 : inputs that have NELTS_PER_INPUT elements each. Take the elements of the
37 : new permutation vector from ELEMENTS, clamping each one to be in range. */
38 :
39 : void
40 4001214 : vec_perm_indices::new_vector (const vec_perm_builder &elements,
41 : unsigned int ninputs,
42 : bool input0_bitwise_zero_p,
43 : bool input1_bitwise_zero_p,
44 : poly_uint64 nelts_per_input)
45 : {
46 4001214 : m_ninputs = ninputs;
47 4001214 : m_nelts_per_input = nelts_per_input;
48 4001214 : m_input0_bitwise_zero_p = input0_bitwise_zero_p;
49 4001214 : m_input1_bitwise_zero_p = input1_bitwise_zero_p;
50 : /* If the vector has a constant number of elements, expand the
51 : encoding and clamp each element. E.g. { 0, 2, 4, ... } might
52 : wrap halfway if there is only one vector input, and we want
53 : the wrapped form to be the canonical one.
54 :
55 : If the vector has a variable number of elements, just copy
56 : the encoding. In that case the unwrapped form is canonical
57 : and there is no way of representing the wrapped form. */
58 4001214 : poly_uint64 full_nelts = elements.full_nelts ();
59 4001214 : unsigned HOST_WIDE_INT copy_nelts;
60 4001214 : if (full_nelts.is_constant (©_nelts))
61 4001214 : m_encoding.new_vector (full_nelts, copy_nelts, 1);
62 : else
63 : {
64 : copy_nelts = elements.encoded_nelts ();
65 : m_encoding.new_vector (full_nelts, elements.npatterns (),
66 : elements.nelts_per_pattern ());
67 : }
68 4001214 : unsigned int npatterns = m_encoding.npatterns ();
69 32224727 : for (unsigned int i = 0; i < npatterns; ++i)
70 28223759 : m_encoding.quick_push (clamp (elements.elt (i)));
71 : /* Use the fact that:
72 :
73 : (a + b) % c == ((a % c) + (b % c)) % c
74 :
75 : to simplify the clamping of variable-length vectors. */
76 4001214 : for (unsigned int i = npatterns; i < copy_nelts; ++i)
77 : {
78 0 : element_type step = clamp (elements.elt (i)
79 0 : - elements.elt (i - npatterns));
80 0 : m_encoding.quick_push (clamp (m_encoding[i - npatterns] + step));
81 : }
82 4001214 : m_encoding.finalize ();
83 4001214 : }
84 :
85 : /* Switch to a new permutation vector that selects the same input elements
86 : as ORIG, but with each element split into FACTOR pieces. For example,
87 : if ORIG is { 1, 2, 0, 3 } and FACTOR is 2, the new permutation is
88 : { 2, 3, 4, 5, 0, 1, 6, 7 }. */
89 :
90 : void
91 663401 : vec_perm_indices::new_expanded_vector (const vec_perm_indices &orig,
92 : unsigned int factor)
93 : {
94 663401 : m_ninputs = orig.m_ninputs;
95 663401 : m_input0_bitwise_zero_p = orig.m_input0_bitwise_zero_p;
96 663401 : m_input1_bitwise_zero_p = orig.m_input1_bitwise_zero_p;
97 663401 : m_nelts_per_input = orig.m_nelts_per_input * factor;
98 663401 : m_encoding.new_vector (orig.m_encoding.full_nelts () * factor,
99 663401 : orig.m_encoding.npatterns () * factor,
100 : orig.m_encoding.nelts_per_pattern ());
101 663401 : unsigned int encoded_nelts = orig.m_encoding.encoded_nelts ();
102 2199900 : for (unsigned int i = 0; i < encoded_nelts; ++i)
103 : {
104 1536499 : element_type base = orig.m_encoding[i] * factor;
105 9877159 : for (unsigned int j = 0; j < factor; ++j)
106 8340660 : m_encoding.quick_push (base + j);
107 : }
108 663401 : m_encoding.finalize ();
109 663401 : }
110 :
111 : /* Check whether we can switch to a new permutation vector that
112 : selects the same input elements as ORIG, but with each element
113 : built up from FACTOR pieces. Return true if yes, otherwise
114 : return false. Every FACTOR permutation indexes should be
115 : continuous separately and the first one of each batch should
116 : be able to exactly modulo FACTOR. For example, if ORIG is
117 : { 2, 3, 4, 5, 0, 1, 6, 7 } and FACTOR is 2, the new permutation
118 : is { 1, 2, 0, 3 }. */
119 :
120 : bool
121 24 : vec_perm_indices::new_shrunk_vector (const vec_perm_indices &orig,
122 : unsigned int factor)
123 : {
124 24 : gcc_assert (factor > 0);
125 :
126 24 : if (maybe_lt (orig.m_nelts_per_input, factor))
127 : return false;
128 :
129 24 : poly_uint64 nelts;
130 : /* Invalid if vector units number isn't multiple of factor. */
131 48 : if (!multiple_p (orig.m_nelts_per_input, factor, &nelts))
132 : return false;
133 :
134 : /* Only handle the case that npatterns is multiple of factor.
135 : FIXME: Try to see whether we can reshape it by factor npatterns. */
136 24 : if (orig.m_encoding.npatterns () % factor != 0)
137 : return false;
138 :
139 11 : unsigned int encoded_nelts = orig.m_encoding.encoded_nelts ();
140 11 : auto_vec<element_type, 32> encoding (encoded_nelts);
141 : /* Separate all encoded elements into batches by size factor,
142 : then ensure the first element of each batch is multiple of
143 : factor and all elements in each batch is consecutive from
144 : the first one. */
145 12 : for (unsigned int i = 0; i < encoded_nelts; i += factor)
146 : {
147 11 : element_type first = orig.m_encoding[i];
148 11 : element_type new_index;
149 11 : if (!multiple_p (first, factor, &new_index))
150 10 : return false;
151 25 : for (unsigned int j = 1; j < factor; ++j)
152 24 : if (maybe_ne (first + j, orig.m_encoding[i + j]))
153 10 : return false;
154 1 : encoding.quick_push (new_index);
155 : }
156 :
157 1 : m_ninputs = orig.m_ninputs;
158 1 : m_nelts_per_input = nelts;
159 1 : poly_uint64 full_nelts = exact_div (orig.m_encoding.full_nelts (), factor);
160 1 : unsigned int npatterns = orig.m_encoding.npatterns () / factor;
161 :
162 1 : m_encoding.new_vector (full_nelts, npatterns,
163 : orig.m_encoding.nelts_per_pattern ());
164 1 : m_encoding.splice (encoding);
165 1 : m_encoding.finalize ();
166 :
167 1 : return true;
168 11 : }
169 :
170 : /* Rotate the inputs of the permutation right by DELTA inputs. This changes
171 : the values of the permutation vector but it doesn't change the way that
172 : the elements are encoded. */
173 :
174 : void
175 15102 : vec_perm_indices::rotate_inputs (int delta)
176 : {
177 15102 : element_type element_delta = delta * m_nelts_per_input;
178 78192 : for (unsigned int i = 0; i < m_encoding.length (); ++i)
179 63090 : m_encoding[i] = clamp (m_encoding[i] + element_delta);
180 15102 : }
181 :
182 : /* Return true if index OUT_BASE + I * OUT_STEP selects input
183 : element IN_BASE + I * IN_STEP. For example, the call to test
184 : whether a permute reverses a vector of N elements would be:
185 :
186 : series_p (0, 1, N - 1, -1)
187 :
188 : which would return true for { N - 1, N - 2, N - 3, ... }.
189 : The calls to test for an interleaving of elements starting
190 : at N1 and N2 would be:
191 :
192 : series_p (0, 2, N1, 1) && series_p (1, 2, N2, 1).
193 :
194 : which would return true for { N1, N2, N1 + 1, N2 + 1, ... }. */
195 :
196 : bool
197 4151106 : vec_perm_indices::series_p (unsigned int out_base, unsigned int out_step,
198 : element_type in_base, element_type in_step) const
199 : {
200 : /* Check the base value. */
201 4151106 : if (maybe_ne (clamp (m_encoding.elt (out_base)), clamp (in_base)))
202 : return false;
203 :
204 1340848 : element_type full_nelts = m_encoding.full_nelts ();
205 1340848 : unsigned int npatterns = m_encoding.npatterns ();
206 :
207 : /* Calculate which multiple of OUT_STEP elements we need to get
208 : back to the same pattern. */
209 1340848 : unsigned int cycle_length = least_common_multiple (out_step, npatterns);
210 :
211 : /* Check the steps. */
212 1340848 : in_step = clamp (in_step);
213 1340848 : out_base += out_step;
214 1340848 : unsigned int limit = 0;
215 2438380 : for (;;)
216 : {
217 : /* Succeed if we've checked all the elements in the vector. */
218 1889614 : if (known_ge (out_base, full_nelts))
219 1340848 : return true;
220 :
221 1586189 : if (out_base >= npatterns)
222 : {
223 : /* We've got to the end of the "foreground" values. Check
224 : 2 elements from each pattern in the "background" values. */
225 949622 : if (limit == 0)
226 872712 : limit = out_base + cycle_length * 2;
227 76910 : else if (out_base >= limit)
228 : return true;
229 : }
230 :
231 1558512 : element_type v0 = m_encoding.elt (out_base - out_step);
232 1558512 : element_type v1 = m_encoding.elt (out_base);
233 1880058 : if (maybe_ne (clamp (v1 - v0), in_step))
234 : return false;
235 :
236 548766 : out_base += out_step;
237 548766 : }
238 : }
239 :
240 : /* Return true if all elements of the permutation vector are in the range
241 : [START, START + SIZE). */
242 :
243 : bool
244 3515103 : vec_perm_indices::all_in_range_p (element_type start, element_type size) const
245 : {
246 : /* Check the first two elements of each pattern. */
247 3515103 : unsigned int npatterns = m_encoding.npatterns ();
248 3515103 : unsigned int nelts_per_pattern = m_encoding.nelts_per_pattern ();
249 3515103 : unsigned int base_nelts = npatterns * MIN (nelts_per_pattern, 2);
250 14916262 : for (unsigned int i = 0; i < base_nelts; ++i)
251 24974896 : if (!known_in_range_p (m_encoding[i], start, size))
252 : return false;
253 :
254 : /* For stepped encodings, check the full range of the series. */
255 1342525 : if (nelts_per_pattern == 3)
256 : {
257 402163 : element_type limit = input_nelts ();
258 :
259 : /* The number of elements in each pattern beyond the first two
260 : that we checked above. */
261 402163 : poly_int64 step_nelts = exact_div (m_encoding.full_nelts (),
262 402163 : npatterns) - 2;
263 843184 : for (unsigned int i = 0; i < npatterns; ++i)
264 : {
265 : /* BASE1 has been checked but BASE2 hasn't. */
266 637852 : element_type base1 = m_encoding[i + npatterns];
267 637852 : element_type base2 = m_encoding[i + base_nelts];
268 :
269 : /* The step to add to get from BASE1 to each subsequent value. */
270 637852 : element_type step = clamp (base2 - base1);
271 :
272 : /* STEP has no inherent sign, so a value near LIMIT can
273 : act as a negative step. The series is in range if it
274 : is in range according to one of the two interpretations.
275 :
276 : Since we're dealing with clamped values, ELEMENT_TYPE is
277 : wide enough for overflow not to be a problem. */
278 637852 : element_type headroom_down = base1 - start;
279 637852 : element_type headroom_up = size - headroom_down - 1;
280 637852 : HOST_WIDE_INT diff;
281 637852 : if ((!step.is_constant (&diff)
282 637852 : || maybe_lt (headroom_up, diff * step_nelts))
283 197056 : && (!(limit - step).is_constant (&diff)
284 197056 : || maybe_lt (headroom_down, diff * step_nelts)))
285 2369409 : return false;
286 : }
287 : }
288 : return true;
289 : }
290 :
291 : /* Try to read the contents of VECTOR_CST CST as a constant permutation
292 : vector. Return true and add the elements to BUILDER on success,
293 : otherwise return false without modifying BUILDER. */
294 :
295 : bool
296 2072941 : tree_to_vec_perm_builder (vec_perm_builder *builder, tree cst)
297 : {
298 2072941 : unsigned int encoded_nelts = vector_cst_encoded_nelts (cst);
299 10543309 : for (unsigned int i = 0; i < encoded_nelts; ++i)
300 8470393 : if (!tree_fits_poly_int64_p (VECTOR_CST_ENCODED_ELT (cst, i)))
301 : return false;
302 :
303 4145832 : builder->new_vector (TYPE_VECTOR_SUBPARTS (TREE_TYPE (cst)),
304 2072916 : VECTOR_CST_NPATTERNS (cst),
305 2072916 : VECTOR_CST_NELTS_PER_PATTERN (cst));
306 10543284 : for (unsigned int i = 0; i < encoded_nelts; ++i)
307 8470368 : builder->quick_push (tree_to_poly_int64 (VECTOR_CST_ENCODED_ELT (cst, i)));
308 : return true;
309 : }
310 :
311 : /* Try to read the contents of VECTOR_CST PERM_CST as a constant permutation
312 : vector permuting OP0 and OP1. Return true and populate INDICES on success,
313 : otherwise return false without modifying INDICES. */
314 :
315 : bool
316 322558 : tree_to_vec_perm_indices (vec_perm_indices *indices, tree op0, tree op1,
317 : tree perm_cst)
318 : {
319 322558 : vec_perm_builder builder;
320 322558 : if (!tree_to_vec_perm_builder (&builder, perm_cst))
321 : return false;
322 322557 : indices->new_vector (builder, op0 == op1 ? 1 : 2,
323 322557 : initializer_zerop (op0), initializer_zerop (op1),
324 322557 : TYPE_VECTOR_SUBPARTS (TREE_TYPE (op0)));
325 322557 : return true;
326 322558 : }
327 :
328 :
329 : /* Return a VECTOR_CST of type TYPE for the permutation vector in INDICES. */
330 :
331 : tree
332 1235107 : vec_perm_indices_to_tree (tree type, const vec_perm_indices &indices)
333 : {
334 1235107 : gcc_assert (known_eq (TYPE_VECTOR_SUBPARTS (type), indices.length ()));
335 1235107 : tree_vector_builder sel (type, indices.encoding ().npatterns (),
336 1235107 : indices.encoding ().nelts_per_pattern ());
337 1235107 : unsigned int encoded_nelts = sel.encoded_nelts ();
338 8376415 : for (unsigned int i = 0; i < encoded_nelts; i++)
339 7141308 : sel.quick_push (build_int_cst (TREE_TYPE (type), indices[i]));
340 1235107 : return sel.build ();
341 1235107 : }
342 :
343 : /* Return a CONST_VECTOR of mode MODE that contains the elements of
344 : INDICES. */
345 :
346 : rtx
347 0 : vec_perm_indices_to_rtx (machine_mode mode, const vec_perm_indices &indices)
348 : {
349 0 : gcc_assert (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
350 : && known_eq (GET_MODE_NUNITS (mode), indices.length ()));
351 0 : rtx_vector_builder sel (mode, indices.encoding ().npatterns (),
352 0 : indices.encoding ().nelts_per_pattern ());
353 0 : unsigned int encoded_nelts = sel.encoded_nelts ();
354 0 : for (unsigned int i = 0; i < encoded_nelts; i++)
355 0 : sel.quick_push (gen_int_mode (indices[i], GET_MODE_INNER (mode)));
356 0 : return sel.build ();
357 0 : }
358 :
359 : #if CHECKING_P
360 :
361 : namespace selftest {
362 :
363 : /* Test a 12-element vector. */
364 :
365 : static void
366 4 : test_vec_perm_12 (void)
367 : {
368 4 : vec_perm_builder builder (12, 12, 1);
369 20 : for (unsigned int i = 0; i < 4; ++i)
370 : {
371 16 : builder.quick_push (i * 5);
372 16 : builder.quick_push (3 + i);
373 16 : builder.quick_push (2 + 3 * i);
374 : }
375 4 : vec_perm_indices indices (builder, 1, 12);
376 4 : ASSERT_TRUE (indices.series_p (0, 3, 0, 5));
377 4 : ASSERT_FALSE (indices.series_p (0, 3, 3, 5));
378 4 : ASSERT_FALSE (indices.series_p (0, 3, 0, 8));
379 4 : ASSERT_TRUE (indices.series_p (1, 3, 3, 1));
380 4 : ASSERT_TRUE (indices.series_p (2, 3, 2, 3));
381 :
382 4 : ASSERT_TRUE (indices.series_p (0, 4, 0, 4));
383 4 : ASSERT_FALSE (indices.series_p (1, 4, 3, 4));
384 :
385 4 : ASSERT_TRUE (indices.series_p (0, 6, 0, 10));
386 4 : ASSERT_FALSE (indices.series_p (0, 6, 0, 100));
387 :
388 4 : ASSERT_FALSE (indices.series_p (1, 10, 3, 7));
389 4 : ASSERT_TRUE (indices.series_p (1, 10, 3, 8));
390 :
391 4 : ASSERT_TRUE (indices.series_p (0, 12, 0, 10));
392 4 : ASSERT_TRUE (indices.series_p (0, 12, 0, 11));
393 4 : ASSERT_TRUE (indices.series_p (0, 12, 0, 100));
394 4 : }
395 :
396 : /* Run selftests for this file. */
397 :
398 : void
399 4 : vec_perm_indices_cc_tests ()
400 : {
401 4 : test_vec_perm_12 ();
402 4 : }
403 :
404 : } // namespace selftest
405 :
406 : #endif
|
