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/// ShuffleEntry - Represent a shuffle entry in the decomposion of a vector
309/// shuffle. i.e. a vector shuffle LHS, RHS, Mask can be built using a list of
310/// ShuffleEntry, by performing Op to either LHS, RHS or one of the previous
311/// ShuffleEntrys in the lists.
312struct ShuffleEntry {
313 // The supported operations. The first 16 match those generated by
314 // PerfectShuffle.cpp.
315 enum Operation {
316 OP_COPY = 0, // Copy, used for things like <u,u,u,3> to say it is <0,1,2,3>
317 OP_VREV,
318 OP_VDUP0,
319 OP_VDUP1,
320 OP_VDUP2,
321 OP_VDUP3,
322 OP_VEXT1,
323 OP_VEXT2,
324 OP_VEXT3,
325 OP_VUZPL, // VUZP, left result
326 OP_VUZPR, // VUZP, right result
327 OP_VZIPL, // VZIP, left result
328 OP_VZIPR, // VZIP, right result
329 OP_VTRNL, // VTRN, left result
330 OP_VTRNR, // VTRN, right result
331 OP_MOVLANE, // Move lane. RHSID is the lane to move into
332
333 OP_MOVLANE32,
334 OP_MOVLANE64,
335 };
336
337 /// Special IDs for the LHS and RHS values.
338 enum IDs {
339 LHS = 0xfe,
340 RHS = 0xff,
341 };
342
343 Operation Op;
344 unsigned LHSID;
345 unsigned RHSID;
346};
347
348inline unsigned
349generatePerfectShuffleFromTable(unsigned PFTableIndex,
350 SmallVector<ShuffleEntry> &Entries) {
351 unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
352 ShuffleEntry::Operation OpNum =
353 (ShuffleEntry::Operation)((PFEntry >> 26) & 0x0F);
354 unsigned LHSID = (PFEntry >> 13) & ((1 << 13) - 1);
355 unsigned RHSID = (PFEntry >> 0) & ((1 << 13) - 1);
356
357 if (OpNum == ShuffleEntry::OP_COPY) {
358 if (LHSID == (1 * 9 + 2) * 9 + 3)
359 return ShuffleEntry::LHS;
360 assert(LHSID == ((4 * 9 + 5) * 9 + 6) * 9 + 7 && "Illegal OP_COPY!");
361 return ShuffleEntry::RHS;
362 }
363
364 unsigned OpLHS = generatePerfectShuffleFromTable(PFTableIndex: LHSID, Entries);
365
366 if (OpNum == ShuffleEntry::OP_MOVLANE) {
367 // Decompose a PerfectShuffle ID to get the Mask for lane Elt
368 auto getPFIDLane = [](unsigned ID, int Elt) -> int {
369 assert(Elt < 4 && "Expected Perfect Lanes to be less than 4");
370 Elt = 3 - Elt;
371 while (Elt > 0) {
372 ID /= 9;
373 Elt--;
374 }
375 return (ID % 9 == 8) ? -1 : ID % 9;
376 };
377
378 // OP_MOVLANE are either D movs (if bit 0x4 is set) or S movs. D movs
379 // convert into a higher type.
380 if (RHSID & 0x4) {
381 int MaskElt = getPFIDLane(PFTableIndex, (RHSID & 0x01) << 1) >> 1;
382 if (MaskElt == -1)
383 MaskElt =
384 (getPFIDLane(PFTableIndex, ((RHSID & 0x01) << 1) + 1) - 1) >> 1;
385 assert(MaskElt >= 0 && "Didn't expect an undef movlane index!");
386 unsigned ExtLane = MaskElt < 2 ? MaskElt : (MaskElt - 2);
387 Entries.push_back(Elt: {.Op: ShuffleEntry::OP_MOVLANE64, .LHSID: OpLHS,
388 .RHSID: (MaskElt >= 2) << 16 | ExtLane << 8 | (RHSID & 0x3)});
389 } else {
390 int MaskElt = getPFIDLane(PFTableIndex, RHSID);
391 assert(MaskElt >= 0 && "Didn't expect an undef movlane index!");
392 unsigned ExtLane = MaskElt < 4 ? MaskElt : (MaskElt - 4);
393 Entries.push_back(Elt: {.Op: ShuffleEntry::OP_MOVLANE32, .LHSID: OpLHS,
394 .RHSID: (MaskElt >= 4) << 16 | ExtLane << 8 | (RHSID & 0x3)});
395 }
396 return Entries.size() - 1;
397 }
398
399 unsigned OpRHS = generatePerfectShuffleFromTable(PFTableIndex: RHSID, Entries);
400
401 Entries.push_back(Elt: {.Op: OpNum, .LHSID: OpLHS, .RHSID: OpRHS});
402 return Entries.size() - 1;
403}
404
405/// generatePerfectShuffle - Given a Mask, attempt to generate the optimal
406/// sequence of instructions using zip/uzp/trn/dup/etc. Currently uses the
407/// perfect shuffle tables.
408inline bool generatePerfectShuffle(ArrayRef<int> Mask, unsigned NumElts,
409 SmallVector<ShuffleEntry> &Entries) {
410 assert(NumElts == 4 && "Only 4 element masks supported at the moment");
411
412 // Compute the index in the perfect shuffle table.
413 unsigned PFIndexes[4];
414 for (unsigned i = 0; i != 4; ++i) {
415 if (Mask[i] < 0)
416 PFIndexes[i] = 8;
417 else
418 PFIndexes[i] = Mask[i];
419 }
420
421 unsigned PFTableIndex = PFIndexes[0] * 9 * 9 * 9 + PFIndexes[1] * 9 * 9 +
422 PFIndexes[2] * 9 + PFIndexes[3];
423 unsigned Idx = generatePerfectShuffleFromTable(PFTableIndex, Entries);
424 return Idx == Entries.size() - 1;
425}
426
427} // namespace llvm
428
429#endif
430