1//===-- AArch64PerfectShuffle.h - AdvSIMD Perfect Shuffle Table -----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file declares data for the optimal way to build a perfect shuffle using
10// AdvSIMD instructions. The data is generated by llvm-PerfectShuffle.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_AARCH64_AARCH64PERFECTSHUFFLE_H
15#define LLVM_LIB_TARGET_AARCH64_AARCH64PERFECTSHUFFLE_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/STLExtras.h"
19
20namespace llvm {
21
22extern const unsigned PerfectShuffleTable[6561 + 1];
23
24inline unsigned getPerfectShuffleCost(llvm::ArrayRef<int> M) {
25 assert(M.size() == 4 && "Expected a 4 entry perfect shuffle");
26
27 // Special case zero-cost nop copies, from either LHS or RHS.
28 if (llvm::all_of(Range: llvm::enumerate(First&: M), P: [](const auto &E) {
29 return E.value() < 0 || E.value() == (int)E.index();
30 }))
31 return 0;
32 if (llvm::all_of(Range: llvm::enumerate(First&: M), P: [](const auto &E) {
33 return E.value() < 0 || E.value() == (int)E.index() + 4;
34 }))
35 return 0;
36
37 // Get the four mask elementd from the 2 inputs. Perfect shuffles encode undef
38 // elements with value 8.
39 unsigned PFIndexes[4];
40 for (unsigned i = 0; i != 4; ++i) {
41 assert(M[i] < 8 && "Expected a maximum entry of 8 for shuffle mask");
42 if (M[i] < 0)
43 PFIndexes[i] = 8;
44 else
45 PFIndexes[i] = M[i];
46 }
47
48 // Compute the index in the perfect shuffle table.
49 unsigned PFTableIndex = PFIndexes[0] * 9 * 9 * 9 + PFIndexes[1] * 9 * 9 +
50 PFIndexes[2] * 9 + PFIndexes[3];
51 unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
52 // And extract the cost from the upper bits. The cost is encoded as Cost-1.
53 return (PFEntry >> 30) + 1;
54}
55
56/// Return true for zip1 or zip2 masks of the form:
57/// <0, 8, 1, 9, 2, 10, 3, 11> (WhichResultOut = 0, OperandOrderOut = 0) or
58/// <4, 12, 5, 13, 6, 14, 7, 15> (WhichResultOut = 1, OperandOrderOut = 0) or
59/// <8, 0, 9, 1, 10, 2, 11, 3> (WhichResultOut = 0, OperandOrderOut = 1) or
60/// <12, 4, 13, 5, 14, 6, 15, 7> (WhichResultOut = 1, OperandOrderOut = 1)
61inline bool isZIPMask(ArrayRef<int> M, unsigned NumElts,
62 unsigned &WhichResultOut, unsigned &OperandOrderOut) {
63 if (NumElts % 2 != 0)
64 return false;
65
66 // "Result" corresponds to "WhichResultOut", selecting between zip1 and zip2.
67 // "Order" corresponds to "OperandOrderOut", selecting the order of operands
68 // for the instruction (flipped or not).
69 bool Result0Order0 = true; // WhichResultOut = 0, OperandOrderOut = 0
70 bool Result1Order0 = true; // WhichResultOut = 1, OperandOrderOut = 0
71 bool Result0Order1 = true; // WhichResultOut = 0, OperandOrderOut = 1
72 bool Result1Order1 = true; // WhichResultOut = 1, OperandOrderOut = 1
73 // Check all elements match.
74 for (unsigned i = 0; i != NumElts; i += 2) {
75 if (M[i] >= 0) {
76 unsigned EvenElt = (unsigned)M[i];
77 if (EvenElt != i / 2)
78 Result0Order0 = false;
79 if (EvenElt != NumElts / 2 + i / 2)
80 Result1Order0 = false;
81 if (EvenElt != NumElts + i / 2)
82 Result0Order1 = false;
83 if (EvenElt != NumElts + NumElts / 2 + i / 2)
84 Result1Order1 = false;
85 }
86 if (M[i + 1] >= 0) {
87 unsigned OddElt = (unsigned)M[i + 1];
88 if (OddElt != NumElts + i / 2)
89 Result0Order0 = false;
90 if (OddElt != NumElts + NumElts / 2 + i / 2)
91 Result1Order0 = false;
92 if (OddElt != i / 2)
93 Result0Order1 = false;
94 if (OddElt != NumElts / 2 + i / 2)
95 Result1Order1 = false;
96 }
97 }
98
99 if (Result0Order0 + Result1Order0 + Result0Order1 + Result1Order1 != 1)
100 return false;
101
102 WhichResultOut = (Result0Order0 || Result0Order1) ? 0 : 1;
103 OperandOrderOut = (Result0Order0 || Result1Order0) ? 0 : 1;
104 return true;
105}
106
107/// isZIP_v_undef_Mask - Special case of isZIPMask for canonical form of
108/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
109/// Mask is e.g., <0, 0, 1, 1> instead of <0, 4, 1, 5>.
110inline bool isZIP_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
111 unsigned &WhichResult) {
112 if (NumElts % 2 != 0)
113 return false;
114 WhichResult = (M[0] == 0 ? 0 : 1);
115 unsigned Idx = WhichResult * NumElts / 2;
116 for (unsigned i = 0; i != NumElts; i += 2) {
117 if ((M[i] >= 0 && (unsigned)M[i] != Idx) ||
118 (M[i + 1] >= 0 && (unsigned)M[i + 1] != Idx))
119 return false;
120 Idx += 1;
121 }
122
123 return true;
124}
125
126/// Return true for uzp1 or uzp2 masks of the form:
127/// <0, 2, 4, 6, 8, 10, 12, 14> or
128/// <1, 3, 5, 7, 9, 11, 13, 15>
129inline bool isUZPMask(ArrayRef<int> M, unsigned NumElts,
130 unsigned &WhichResultOut) {
131 // Check the first non-undef element for which half to use.
132 unsigned WhichResult = 2;
133 for (unsigned i = 0; i != NumElts; i++) {
134 if (M[i] >= 0) {
135 WhichResult = ((unsigned)M[i] == i * 2 ? 0 : 1);
136 break;
137 }
138 }
139 if (WhichResult == 2)
140 return false;
141
142 // Check all elements match.
143 for (unsigned i = 0; i != NumElts; ++i) {
144 if (M[i] < 0)
145 continue; // ignore UNDEF indices
146 if ((unsigned)M[i] != 2 * i + WhichResult)
147 return false;
148 }
149 WhichResultOut = WhichResult;
150 return true;
151}
152
153/// isUZP_v_undef_Mask - Special case of isUZPMask for canonical form of
154/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
155/// Mask is e.g., <0, 2, 0, 2> instead of <0, 2, 4, 6>,
156inline bool isUZP_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
157 unsigned &WhichResult) {
158 unsigned Half = NumElts / 2;
159 WhichResult = (M[0] == 0 ? 0 : 1);
160 for (unsigned j = 0; j != 2; ++j) {
161 unsigned Idx = WhichResult;
162 for (unsigned i = 0; i != Half; ++i) {
163 int MIdx = M[i + j * Half];
164 if (MIdx >= 0 && (unsigned)MIdx != Idx)
165 return false;
166 Idx += 2;
167 }
168 }
169
170 return true;
171}
172
173/// Return true for trn1 or trn2 masks of the form:
174/// <0, 8, 2, 10, 4, 12, 6, 14> (WhichResultOut = 0, OperandOrderOut = 0) or
175/// <1, 9, 3, 11, 5, 13, 7, 15> (WhichResultOut = 1, OperandOrderOut = 0) or
176/// <8, 0, 10, 2, 12, 4, 14, 6> (WhichResultOut = 0, OperandOrderOut = 1) or
177/// <9, 1, 11, 3, 13, 5, 15, 7> (WhichResultOut = 1, OperandOrderOut = 1) or
178inline bool isTRNMask(ArrayRef<int> M, unsigned NumElts,
179 unsigned &WhichResultOut, unsigned &OperandOrderOut) {
180 if (NumElts % 2 != 0)
181 return false;
182
183 // "Result" corresponds to "WhichResultOut", selecting between trn1 and trn2.
184 // "Order" corresponds to "OperandOrderOut", selecting the order of operands
185 // for the instruction (flipped or not).
186 bool Result0Order0 = true; // WhichResultOut = 0, OperandOrderOut = 0
187 bool Result1Order0 = true; // WhichResultOut = 1, OperandOrderOut = 0
188 bool Result0Order1 = true; // WhichResultOut = 0, OperandOrderOut = 1
189 bool Result1Order1 = true; // WhichResultOut = 1, OperandOrderOut = 1
190 // Check all elements match.
191 for (unsigned i = 0; i != NumElts; i += 2) {
192 if (M[i] >= 0) {
193 unsigned EvenElt = (unsigned)M[i];
194 if (EvenElt != i)
195 Result0Order0 = false;
196 if (EvenElt != i + 1)
197 Result1Order0 = false;
198 if (EvenElt != NumElts + i)
199 Result0Order1 = false;
200 if (EvenElt != NumElts + i + 1)
201 Result1Order1 = false;
202 }
203 if (M[i + 1] >= 0) {
204 unsigned OddElt = (unsigned)M[i + 1];
205 if (OddElt != NumElts + i)
206 Result0Order0 = false;
207 if (OddElt != NumElts + i + 1)
208 Result1Order0 = false;
209 if (OddElt != i)
210 Result0Order1 = false;
211 if (OddElt != i + 1)
212 Result1Order1 = false;
213 }
214 }
215
216 if (Result0Order0 + Result1Order0 + Result0Order1 + Result1Order1 != 1)
217 return false;
218
219 WhichResultOut = (Result0Order0 || Result0Order1) ? 0 : 1;
220 OperandOrderOut = (Result0Order0 || Result1Order0) ? 0 : 1;
221 return true;
222}
223
224/// isTRN_v_undef_Mask - Special case of isTRNMask for canonical form of
225/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
226/// Mask is e.g., <0, 0, 2, 2> instead of <0, 4, 2, 6>.
227inline bool isTRN_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
228 unsigned &WhichResult) {
229 if (NumElts % 2 != 0)
230 return false;
231 WhichResult = (M[0] == 0 ? 0 : 1);
232 for (unsigned i = 0; i < NumElts; i += 2) {
233 if ((M[i] >= 0 && (unsigned)M[i] != i + WhichResult) ||
234 (M[i + 1] >= 0 && (unsigned)M[i + 1] != i + WhichResult))
235 return false;
236 }
237 return true;
238}
239
240/// isREVMask - Check if a vector shuffle corresponds to a REV
241/// instruction with the specified blocksize. (The order of the elements
242/// within each block of the vector is reversed.)
243inline bool isREVMask(ArrayRef<int> M, unsigned EltSize, unsigned NumElts,
244 unsigned BlockSize) {
245 assert((BlockSize == 16 || BlockSize == 32 || BlockSize == 64 ||
246 BlockSize == 128) &&
247 "Only possible block sizes for REV are: 16, 32, 64, 128");
248
249 unsigned BlockElts = M[0] + 1;
250 // If the first shuffle index is UNDEF, be optimistic.
251 if (M[0] < 0)
252 BlockElts = BlockSize / EltSize;
253
254 if (BlockSize <= EltSize || BlockSize != BlockElts * EltSize)
255 return false;
256
257 for (unsigned i = 0; i < NumElts; ++i) {
258 if (M[i] < 0)
259 continue; // ignore UNDEF indices
260 if ((unsigned)M[i] != (i - i % BlockElts) + (BlockElts - 1 - i % BlockElts))
261 return false;
262 }
263
264 return true;
265}
266
267/// isDUPQMask - matches a splat of equivalent lanes within segments of a given
268/// number of elements.
269inline std::optional<unsigned> isDUPQMask(ArrayRef<int> Mask, unsigned Segments,
270 unsigned SegmentSize) {
271 unsigned Lane = unsigned(Mask[0]);
272
273 // Make sure there's no size changes.
274 if (SegmentSize * Segments != Mask.size())
275 return std::nullopt;
276
277 // Check the first index corresponds to one of the lanes in the first segment.
278 if (Lane >= SegmentSize)
279 return std::nullopt;
280
281 // Check that all lanes match the first, adjusted for segment.
282 // Undef/poison lanes (<0) are also accepted.
283 if (all_of(Range: enumerate(First&: Mask), P: [&](auto P) {
284 const unsigned SegmentIndex = P.index() / SegmentSize;
285 return P.value() < 0 ||
286 unsigned(P.value()) == Lane + SegmentIndex * SegmentSize;
287 }))
288 return Lane;
289
290 return std::nullopt;
291}
292
293/// isDUPFirstSegmentMask - matches a splat of the first 128b segment.
294inline bool isDUPFirstSegmentMask(ArrayRef<int> Mask, unsigned Segments,
295 unsigned SegmentSize) {
296 // Make sure there's no size changes.
297 if (SegmentSize * Segments != Mask.size())
298 return false;
299
300 // Check that all lanes refer to the equivalent lane in the first segment.
301 // Undef/poison lanes (<0) are also accepted.
302 return all_of(Range: enumerate(First&: Mask), P: [&](auto P) {
303 const unsigned IndexWithinSegment = P.index() % SegmentSize;
304 return P.value() < 0 || unsigned(P.value()) == IndexWithinSegment;
305 });
306}
307
308} // namespace llvm
309
310#endif
311