1 /* A representation of vector permutation indices.
2 Copyright (C) 2017-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
23 #include "vec-perm-indices.h"
25 #include "fold-const.h"
26 #include "tree-vector-builder.h"
32 #include "rtx-vector-builder.h"
34 /* Switch to a new permutation vector that selects between NINPUTS vector
35 inputs that have NELTS_PER_INPUT elements each. Take the elements of the
36 new permutation vector from ELEMENTS, clamping each one to be in range. */
39 vec_perm_indices::new_vector (const vec_perm_builder
&elements
,
41 poly_uint64 nelts_per_input
)
44 m_nelts_per_input
= nelts_per_input
;
45 /* If the vector has a constant number of elements, expand the
46 encoding and clamp each element. E.g. { 0, 2, 4, ... } might
47 wrap halfway if there is only one vector input, and we want
48 the wrapped form to be the canonical one.
50 If the vector has a variable number of elements, just copy
51 the encoding. In that case the unwrapped form is canonical
52 and there is no way of representing the wrapped form. */
53 poly_uint64 full_nelts
= elements
.full_nelts ();
54 unsigned HOST_WIDE_INT copy_nelts
;
55 if (full_nelts
.is_constant (©_nelts
))
56 m_encoding
.new_vector (full_nelts
, copy_nelts
, 1);
59 copy_nelts
= elements
.encoded_nelts ();
60 m_encoding
.new_vector (full_nelts
, elements
.npatterns (),
61 elements
.nelts_per_pattern ());
63 unsigned int npatterns
= m_encoding
.npatterns ();
64 for (unsigned int i
= 0; i
< npatterns
; ++i
)
65 m_encoding
.quick_push (clamp (elements
.elt (i
)));
68 (a + b) % c == ((a % c) + (b % c)) % c
70 to simplify the clamping of variable-length vectors. */
71 for (unsigned int i
= npatterns
; i
< copy_nelts
; ++i
)
73 element_type step
= clamp (elements
.elt (i
)
74 - elements
.elt (i
- npatterns
));
75 m_encoding
.quick_push (clamp (m_encoding
[i
- npatterns
] + step
));
77 m_encoding
.finalize ();
80 /* Switch to a new permutation vector that selects the same input elements
81 as ORIG, but with each element split into FACTOR pieces. For example,
82 if ORIG is { 1, 2, 0, 3 } and FACTOR is 2, the new permutation is
83 { 2, 3, 4, 5, 0, 1, 6, 7 }. */
86 vec_perm_indices::new_expanded_vector (const vec_perm_indices
&orig
,
89 m_ninputs
= orig
.m_ninputs
;
90 m_nelts_per_input
= orig
.m_nelts_per_input
* factor
;
91 m_encoding
.new_vector (orig
.m_encoding
.full_nelts () * factor
,
92 orig
.m_encoding
.npatterns () * factor
,
93 orig
.m_encoding
.nelts_per_pattern ());
94 unsigned int encoded_nelts
= orig
.m_encoding
.encoded_nelts ();
95 for (unsigned int i
= 0; i
< encoded_nelts
; ++i
)
97 element_type base
= orig
.m_encoding
[i
] * factor
;
98 for (unsigned int j
= 0; j
< factor
; ++j
)
99 m_encoding
.quick_push (base
+ j
);
101 m_encoding
.finalize ();
104 /* Rotate the inputs of the permutation right by DELTA inputs. This changes
105 the values of the permutation vector but it doesn't change the way that
106 the elements are encoded. */
109 vec_perm_indices::rotate_inputs (int delta
)
111 element_type element_delta
= delta
* m_nelts_per_input
;
112 for (unsigned int i
= 0; i
< m_encoding
.length (); ++i
)
113 m_encoding
[i
] = clamp (m_encoding
[i
] + element_delta
);
116 /* Return true if index OUT_BASE + I * OUT_STEP selects input
117 element IN_BASE + I * IN_STEP. */
120 vec_perm_indices::series_p (unsigned int out_base
, unsigned int out_step
,
121 element_type in_base
, element_type in_step
) const
123 /* Check the base value. */
124 if (maybe_ne (clamp (m_encoding
.elt (out_base
)), clamp (in_base
)))
127 element_type full_nelts
= m_encoding
.full_nelts ();
128 unsigned int npatterns
= m_encoding
.npatterns ();
130 /* Calculate which multiple of OUT_STEP elements we need to get
131 back to the same pattern. */
132 unsigned int cycle_length
= least_common_multiple (out_step
, npatterns
);
134 /* Check the steps. */
135 in_step
= clamp (in_step
);
136 out_base
+= out_step
;
137 unsigned int limit
= 0;
140 /* Succeed if we've checked all the elements in the vector. */
141 if (known_ge (out_base
, full_nelts
))
144 if (out_base
>= npatterns
)
146 /* We've got to the end of the "foreground" values. Check
147 2 elements from each pattern in the "background" values. */
149 limit
= out_base
+ cycle_length
* 2;
150 else if (out_base
>= limit
)
154 element_type v0
= m_encoding
.elt (out_base
- out_step
);
155 element_type v1
= m_encoding
.elt (out_base
);
156 if (maybe_ne (clamp (v1
- v0
), in_step
))
159 out_base
+= out_step
;
164 /* Return true if all elements of the permutation vector are in the range
165 [START, START + SIZE). */
168 vec_perm_indices::all_in_range_p (element_type start
, element_type size
) const
170 /* Check the first two elements of each pattern. */
171 unsigned int npatterns
= m_encoding
.npatterns ();
172 unsigned int nelts_per_pattern
= m_encoding
.nelts_per_pattern ();
173 unsigned int base_nelts
= npatterns
* MIN (nelts_per_pattern
, 2);
174 for (unsigned int i
= 0; i
< base_nelts
; ++i
)
175 if (!known_in_range_p (m_encoding
[i
], start
, size
))
178 /* For stepped encodings, check the full range of the series. */
179 if (nelts_per_pattern
== 3)
181 element_type limit
= input_nelts ();
183 /* The number of elements in each pattern beyond the first two
184 that we checked above. */
185 poly_int64 step_nelts
= exact_div (m_encoding
.full_nelts (),
187 for (unsigned int i
= 0; i
< npatterns
; ++i
)
189 /* BASE1 has been checked but BASE2 hasn't. */
190 element_type base1
= m_encoding
[i
+ npatterns
];
191 element_type base2
= m_encoding
[i
+ base_nelts
];
193 /* The step to add to get from BASE1 to each subsequent value. */
194 element_type step
= clamp (base2
- base1
);
196 /* STEP has no inherent sign, so a value near LIMIT can
197 act as a negative step. The series is in range if it
198 is in range according to one of the two interpretations.
200 Since we're dealing with clamped values, ELEMENT_TYPE is
201 wide enough for overflow not to be a problem. */
202 element_type headroom_down
= base1
- start
;
203 element_type headroom_up
= size
- headroom_down
- 1;
205 if ((!step
.is_constant (&diff
)
206 || maybe_lt (headroom_up
, diff
* step_nelts
))
207 && (!(limit
- step
).is_constant (&diff
)
208 || maybe_lt (headroom_down
, diff
* step_nelts
)))
215 /* Try to read the contents of VECTOR_CST CST as a constant permutation
216 vector. Return true and add the elements to BUILDER on success,
217 otherwise return false without modifying BUILDER. */
220 tree_to_vec_perm_builder (vec_perm_builder
*builder
, tree cst
)
222 unsigned int encoded_nelts
= vector_cst_encoded_nelts (cst
);
223 for (unsigned int i
= 0; i
< encoded_nelts
; ++i
)
224 if (!tree_fits_poly_int64_p (VECTOR_CST_ENCODED_ELT (cst
, i
)))
227 builder
->new_vector (TYPE_VECTOR_SUBPARTS (TREE_TYPE (cst
)),
228 VECTOR_CST_NPATTERNS (cst
),
229 VECTOR_CST_NELTS_PER_PATTERN (cst
));
230 for (unsigned int i
= 0; i
< encoded_nelts
; ++i
)
231 builder
->quick_push (tree_to_poly_int64 (VECTOR_CST_ENCODED_ELT (cst
, i
)));
235 /* Return a VECTOR_CST of type TYPE for the permutation vector in INDICES. */
238 vec_perm_indices_to_tree (tree type
, const vec_perm_indices
&indices
)
240 gcc_assert (known_eq (TYPE_VECTOR_SUBPARTS (type
), indices
.length ()));
241 tree_vector_builder
sel (type
, indices
.encoding ().npatterns (),
242 indices
.encoding ().nelts_per_pattern ());
243 unsigned int encoded_nelts
= sel
.encoded_nelts ();
244 for (unsigned int i
= 0; i
< encoded_nelts
; i
++)
245 sel
.quick_push (build_int_cst (TREE_TYPE (type
), indices
[i
]));
249 /* Return a CONST_VECTOR of mode MODE that contains the elements of
253 vec_perm_indices_to_rtx (machine_mode mode
, const vec_perm_indices
&indices
)
255 gcc_assert (GET_MODE_CLASS (mode
) == MODE_VECTOR_INT
256 && known_eq (GET_MODE_NUNITS (mode
), indices
.length ()));
257 rtx_vector_builder
sel (mode
, indices
.encoding ().npatterns (),
258 indices
.encoding ().nelts_per_pattern ());
259 unsigned int encoded_nelts
= sel
.encoded_nelts ();
260 for (unsigned int i
= 0; i
< encoded_nelts
; i
++)
261 sel
.quick_push (gen_int_mode (indices
[i
], GET_MODE_INNER (mode
)));
269 /* Test a 12-element vector. */
272 test_vec_perm_12 (void)
274 vec_perm_builder
builder (12, 12, 1);
275 for (unsigned int i
= 0; i
< 4; ++i
)
277 builder
.quick_push (i
* 5);
278 builder
.quick_push (3 + i
);
279 builder
.quick_push (2 + 3 * i
);
281 vec_perm_indices
indices (builder
, 1, 12);
282 ASSERT_TRUE (indices
.series_p (0, 3, 0, 5));
283 ASSERT_FALSE (indices
.series_p (0, 3, 3, 5));
284 ASSERT_FALSE (indices
.series_p (0, 3, 0, 8));
285 ASSERT_TRUE (indices
.series_p (1, 3, 3, 1));
286 ASSERT_TRUE (indices
.series_p (2, 3, 2, 3));
288 ASSERT_TRUE (indices
.series_p (0, 4, 0, 4));
289 ASSERT_FALSE (indices
.series_p (1, 4, 3, 4));
291 ASSERT_TRUE (indices
.series_p (0, 6, 0, 10));
292 ASSERT_FALSE (indices
.series_p (0, 6, 0, 100));
294 ASSERT_FALSE (indices
.series_p (1, 10, 3, 7));
295 ASSERT_TRUE (indices
.series_p (1, 10, 3, 8));
297 ASSERT_TRUE (indices
.series_p (0, 12, 0, 10));
298 ASSERT_TRUE (indices
.series_p (0, 12, 0, 11));
299 ASSERT_TRUE (indices
.series_p (0, 12, 0, 100));
302 /* Run selftests for this file. */
305 vec_perm_indices_c_tests ()
310 } // namespace selftest