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/APInt.h"
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/STLExtras.h"
20
21namespace llvm {
22
23extern const unsigned PerfectShuffleTable[6561 + 1];
24
25inline unsigned getPerfectShuffleCost(llvm::ArrayRef<int> M) {
26 assert(M.size() == 4 && "Expected a 4 entry perfect shuffle");
27
28 // Special case zero-cost nop copies, from either LHS or RHS.
29 if (llvm::all_of(Range: llvm::enumerate(First&: M), P: [](const auto &E) {
30 return E.value() < 0 || E.value() == (int)E.index();
31 }))
32 return 0;
33 if (llvm::all_of(Range: llvm::enumerate(First&: M), P: [](const auto &E) {
34 return E.value() < 0 || E.value() == (int)E.index() + 4;
35 }))
36 return 0;
37
38 // Get the four mask elementd from the 2 inputs. Perfect shuffles encode undef
39 // elements with value 8.
40 unsigned PFIndexes[4];
41 for (unsigned i = 0; i != 4; ++i) {
42 assert(M[i] < 8 && "Expected a maximum entry of 8 for shuffle mask");
43 if (M[i] < 0)
44 PFIndexes[i] = 8;
45 else
46 PFIndexes[i] = M[i];
47 }
48
49 // Compute the index in the perfect shuffle table.
50 unsigned PFTableIndex = PFIndexes[0] * 9 * 9 * 9 + PFIndexes[1] * 9 * 9 +
51 PFIndexes[2] * 9 + PFIndexes[3];
52 unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
53 // And extract the cost from the upper bits. The cost is encoded as Cost-1.
54 return (PFEntry >> 30) + 1;
55}
56
57/// Return true for zip1 or zip2 masks of the form:
58/// <0, 8, 1, 9, 2, 10, 3, 11> (WhichResultOut = 0, OperandOrderOut = 0) or
59/// <4, 12, 5, 13, 6, 14, 7, 15> (WhichResultOut = 1, OperandOrderOut = 0) or
60/// <8, 0, 9, 1, 10, 2, 11, 3> (WhichResultOut = 0, OperandOrderOut = 1) or
61/// <12, 4, 13, 5, 14, 6, 15, 7> (WhichResultOut = 1, OperandOrderOut = 1)
62inline bool isZIPMask(ArrayRef<int> M, unsigned NumElts,
63 unsigned &WhichResultOut, unsigned &OperandOrderOut) {
64 if (NumElts % 2 != 0)
65 return false;
66
67 // "Result" corresponds to "WhichResultOut", selecting between zip1 and zip2.
68 // "Order" corresponds to "OperandOrderOut", selecting the order of operands
69 // for the instruction (flipped or not).
70 bool Result0Order0 = true; // WhichResultOut = 0, OperandOrderOut = 0
71 bool Result1Order0 = true; // WhichResultOut = 1, OperandOrderOut = 0
72 bool Result0Order1 = true; // WhichResultOut = 0, OperandOrderOut = 1
73 bool Result1Order1 = true; // WhichResultOut = 1, OperandOrderOut = 1
74 // Check all elements match.
75 for (unsigned i = 0; i != NumElts; i += 2) {
76 if (M[i] >= 0) {
77 unsigned EvenElt = (unsigned)M[i];
78 if (EvenElt != i / 2)
79 Result0Order0 = false;
80 if (EvenElt != NumElts / 2 + i / 2)
81 Result1Order0 = false;
82 if (EvenElt != NumElts + i / 2)
83 Result0Order1 = false;
84 if (EvenElt != NumElts + NumElts / 2 + i / 2)
85 Result1Order1 = false;
86 }
87 if (M[i + 1] >= 0) {
88 unsigned OddElt = (unsigned)M[i + 1];
89 if (OddElt != NumElts + i / 2)
90 Result0Order0 = false;
91 if (OddElt != NumElts + NumElts / 2 + i / 2)
92 Result1Order0 = false;
93 if (OddElt != i / 2)
94 Result0Order1 = false;
95 if (OddElt != NumElts / 2 + i / 2)
96 Result1Order1 = false;
97 }
98 }
99
100 if (Result0Order0 + Result1Order0 + Result0Order1 + Result1Order1 != 1)
101 return false;
102
103 WhichResultOut = (Result0Order0 || Result0Order1) ? 0 : 1;
104 OperandOrderOut = (Result0Order0 || Result1Order0) ? 0 : 1;
105 return true;
106}
107
108/// isZIP_v_undef_Mask - Special case of isZIPMask for canonical form of
109/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
110/// Mask is e.g., <0, 0, 1, 1> instead of <0, 4, 1, 5>.
111inline bool isZIP_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
112 unsigned &WhichResult) {
113 if (NumElts % 2 != 0)
114 return false;
115 WhichResult = (M[0] == 0 ? 0 : 1);
116 unsigned Idx = WhichResult * NumElts / 2;
117 for (unsigned i = 0; i != NumElts; i += 2) {
118 if ((M[i] >= 0 && (unsigned)M[i] != Idx) ||
119 (M[i + 1] >= 0 && (unsigned)M[i + 1] != Idx))
120 return false;
121 Idx += 1;
122 }
123
124 return true;
125}
126
127/// Return true for uzp1 or uzp2 masks of the form:
128/// <0, 2, 4, 6, 8, 10, 12, 14> or
129/// <1, 3, 5, 7, 9, 11, 13, 15>
130inline bool isUZPMask(ArrayRef<int> M, unsigned NumElts,
131 unsigned &WhichResultOut) {
132 // Check the first non-undef element for which half to use.
133 unsigned WhichResult = 2;
134 for (unsigned i = 0; i != NumElts; i++) {
135 if (M[i] >= 0) {
136 WhichResult = ((unsigned)M[i] == i * 2 ? 0 : 1);
137 break;
138 }
139 }
140 if (WhichResult == 2)
141 return false;
142
143 // Check all elements match.
144 for (unsigned i = 0; i != NumElts; ++i) {
145 if (M[i] < 0)
146 continue; // ignore UNDEF indices
147 if ((unsigned)M[i] != 2 * i + WhichResult)
148 return false;
149 }
150 WhichResultOut = WhichResult;
151 return true;
152}
153
154/// isUZP_v_undef_Mask - Special case of isUZPMask for canonical form of
155/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
156/// Mask is e.g., <0, 2, 0, 2> instead of <0, 2, 4, 6>,
157inline bool isUZP_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
158 unsigned &WhichResult) {
159 unsigned Half = NumElts / 2;
160 WhichResult = (M[0] == 0 ? 0 : 1);
161 for (unsigned j = 0; j != 2; ++j) {
162 unsigned Idx = WhichResult;
163 for (unsigned i = 0; i != Half; ++i) {
164 int MIdx = M[i + j * Half];
165 if (MIdx >= 0 && (unsigned)MIdx != Idx)
166 return false;
167 Idx += 2;
168 }
169 }
170
171 return true;
172}
173
174/// Return true for trn1 or trn2 masks of the form:
175/// <0, 8, 2, 10, 4, 12, 6, 14> (WhichResultOut = 0, OperandOrderOut = 0) or
176/// <1, 9, 3, 11, 5, 13, 7, 15> (WhichResultOut = 1, OperandOrderOut = 0) or
177/// <8, 0, 10, 2, 12, 4, 14, 6> (WhichResultOut = 0, OperandOrderOut = 1) or
178/// <9, 1, 11, 3, 13, 5, 15, 7> (WhichResultOut = 1, OperandOrderOut = 1) or
179inline bool isTRNMask(ArrayRef<int> M, unsigned NumElts,
180 unsigned &WhichResultOut, unsigned &OperandOrderOut) {
181 if (NumElts % 2 != 0)
182 return false;
183
184 // "Result" corresponds to "WhichResultOut", selecting between trn1 and trn2.
185 // "Order" corresponds to "OperandOrderOut", selecting the order of operands
186 // for the instruction (flipped or not).
187 bool Result0Order0 = true; // WhichResultOut = 0, OperandOrderOut = 0
188 bool Result1Order0 = true; // WhichResultOut = 1, OperandOrderOut = 0
189 bool Result0Order1 = true; // WhichResultOut = 0, OperandOrderOut = 1
190 bool Result1Order1 = true; // WhichResultOut = 1, OperandOrderOut = 1
191 // Check all elements match.
192 for (unsigned i = 0; i != NumElts; i += 2) {
193 if (M[i] >= 0) {
194 unsigned EvenElt = (unsigned)M[i];
195 if (EvenElt != i)
196 Result0Order0 = false;
197 if (EvenElt != i + 1)
198 Result1Order0 = false;
199 if (EvenElt != NumElts + i)
200 Result0Order1 = false;
201 if (EvenElt != NumElts + i + 1)
202 Result1Order1 = false;
203 }
204 if (M[i + 1] >= 0) {
205 unsigned OddElt = (unsigned)M[i + 1];
206 if (OddElt != NumElts + i)
207 Result0Order0 = false;
208 if (OddElt != NumElts + i + 1)
209 Result1Order0 = false;
210 if (OddElt != i)
211 Result0Order1 = false;
212 if (OddElt != i + 1)
213 Result1Order1 = false;
214 }
215 }
216
217 if (Result0Order0 + Result1Order0 + Result0Order1 + Result1Order1 != 1)
218 return false;
219
220 WhichResultOut = (Result0Order0 || Result0Order1) ? 0 : 1;
221 OperandOrderOut = (Result0Order0 || Result1Order0) ? 0 : 1;
222 return true;
223}
224
225/// isTRN_v_undef_Mask - Special case of isTRNMask for canonical form of
226/// "vector_shuffle v, v", i.e., "vector_shuffle v, undef".
227/// Mask is e.g., <0, 0, 2, 2> instead of <0, 4, 2, 6>.
228inline bool isTRN_v_undef_Mask(ArrayRef<int> M, unsigned NumElts,
229 unsigned &WhichResult) {
230 if (NumElts % 2 != 0)
231 return false;
232 WhichResult = (M[0] == 0 ? 0 : 1);
233 for (unsigned i = 0; i < NumElts; i += 2) {
234 if ((M[i] >= 0 && (unsigned)M[i] != i + WhichResult) ||
235 (M[i + 1] >= 0 && (unsigned)M[i + 1] != i + WhichResult))
236 return false;
237 }
238 return true;
239}
240
241/// isREVMask - Check if a vector shuffle corresponds to a REV
242/// instruction with the specified blocksize. (The order of the elements
243/// within each block of the vector is reversed.)
244inline bool isREVMask(ArrayRef<int> M, unsigned EltSize, unsigned NumElts,
245 unsigned BlockSize) {
246 assert((BlockSize == 16 || BlockSize == 32 || BlockSize == 64 ||
247 BlockSize == 128) &&
248 "Only possible block sizes for REV are: 16, 32, 64, 128");
249
250 unsigned BlockElts = M[0] + 1;
251 // If the first shuffle index is UNDEF, be optimistic.
252 if (M[0] < 0)
253 BlockElts = BlockSize / EltSize;
254
255 if (BlockSize <= EltSize || BlockSize != BlockElts * EltSize)
256 return false;
257
258 for (unsigned i = 0; i < NumElts; ++i) {
259 if (M[i] < 0)
260 continue; // ignore UNDEF indices
261 if ((unsigned)M[i] != (i - i % BlockElts) + (BlockElts - 1 - i % BlockElts))
262 return false;
263 }
264
265 return true;
266}
267
268/// Check if an EXT instruction can handle the shuffle mask when the
269/// vector sources of the shuffle are different.
270inline bool isEXTMask(ArrayRef<int> M, unsigned NumElts, bool &ReverseEXT,
271 unsigned &Imm) {
272 // Look for the first non-undef element.
273 const int *FirstRealElt = find_if(Range&: M, P: [](int Elt) { return Elt >= 0; });
274 if (FirstRealElt == M.end())
275 return false;
276
277 // Benefit from APInt to handle overflow when calculating expected element.
278 unsigned MaskBits = APInt(32, NumElts * 2).logBase2();
279 APInt ExpectedElt = APInt(MaskBits, *FirstRealElt + 1, /*isSigned=*/false,
280 /*implicitTrunc=*/true);
281 // The following shuffle indices must be the successive elements after the
282 // first real element.
283 if (std::any_of(first: FirstRealElt + 1, last: M.end(),
284 pred: [&](int Elt) { return Elt != ExpectedElt++ && Elt >= 0; }))
285 return false;
286
287 // The index of an EXT is the first element if it is not UNDEF.
288 // Watch out for the beginning UNDEFs. The EXT index should be the expected
289 // value of the first element. E.g.
290 // <-1, -1, 3, ...> is treated as <1, 2, 3, ...>.
291 // <-1, -1, 0, 1, ...> is treated as <2*NumElts-2, 2*NumElts-1, 0, 1, ...>.
292 // ExpectedElt is the last mask index plus 1.
293 Imm = ExpectedElt.getZExtValue();
294
295 // There are two difference cases requiring to reverse input vectors.
296 // For example, for vector <4 x i32> we have the following cases,
297 // Case 1: shufflevector(<4 x i32>, <4 x i32>, <-1, -1, -1, 0>)
298 // Case 2: shufflevector(<4 x i32>, <4 x i32>, <-1, -1, 7, 0>)
299 // For both cases, we finally use mask <5, 6, 7, 0>, which requires
300 // to reverse two input vectors.
301 ReverseEXT = false;
302 if (Imm < NumElts)
303 ReverseEXT = true;
304 else
305 Imm -= NumElts;
306
307 return true;
308}
309
310/// check if an EXT instruction can handle the shuffle mask when the
311/// vector sources of the shuffle are the same. i.e <2,3,0,1>
312inline bool isSingletonEXTMask(ArrayRef<int> M, unsigned NumElts,
313 unsigned &Imm) {
314 // Assume that the first shuffle index is not UNDEF. Fail if it is.
315 if (M[0] < 0)
316 return false;
317
318 Imm = M[0];
319
320 // If this is a VEXT shuffle, the immediate value is the index of the first
321 // element. The other shuffle indices must be the successive elements after
322 // the first one.
323 unsigned ExpectedElt = Imm;
324 for (unsigned I = 1; I < NumElts; ++I) {
325 // Increment the expected index. If it wraps around, just follow it
326 // back to index zero and keep going.
327 ++ExpectedElt;
328 if (ExpectedElt == NumElts)
329 ExpectedElt = 0;
330
331 if (M[I] < 0)
332 continue; // Ignore UNDEF indices.
333 if (ExpectedElt != static_cast<unsigned>(M[I]))
334 return false;
335 }
336
337 return true;
338}
339
340/// isDUPQMask - matches a splat of equivalent lanes within segments of a given
341/// number of elements.
342inline std::optional<unsigned> isDUPQMask(ArrayRef<int> Mask, unsigned Segments,
343 unsigned SegmentSize) {
344 unsigned Lane = unsigned(Mask[0]);
345
346 // Make sure there's no size changes.
347 if (SegmentSize * Segments != Mask.size())
348 return std::nullopt;
349
350 // Check the first index corresponds to one of the lanes in the first segment.
351 if (Lane >= SegmentSize)
352 return std::nullopt;
353
354 // Check that all lanes match the first, adjusted for segment.
355 // Undef/poison lanes (<0) are also accepted.
356 if (all_of(Range: enumerate(First&: Mask), P: [&](auto P) {
357 const unsigned SegmentIndex = P.index() / SegmentSize;
358 return P.value() < 0 ||
359 unsigned(P.value()) == Lane + SegmentIndex * SegmentSize;
360 }))
361 return Lane;
362
363 return std::nullopt;
364}
365
366/// isDUPFirstSegmentMask - matches a splat of the first 128b segment.
367inline bool isDUPFirstSegmentMask(ArrayRef<int> Mask, unsigned Segments,
368 unsigned SegmentSize) {
369 // Make sure there's no size changes.
370 if (SegmentSize * Segments != Mask.size())
371 return false;
372
373 // Check that all lanes refer to the equivalent lane in the first segment.
374 // Undef/poison lanes (<0) are also accepted.
375 return all_of(Range: enumerate(First&: Mask), P: [&](auto P) {
376 const unsigned IndexWithinSegment = P.index() % SegmentSize;
377 return P.value() < 0 || unsigned(P.value()) == IndexWithinSegment;
378 });
379}
380
381/// ShuffleEntry - Represent a shuffle entry in the decomposion of a vector
382/// shuffle. i.e. a vector shuffle LHS, RHS, Mask can be built using a list of
383/// ShuffleEntry, by performing Op to either LHS, RHS or one of the previous
384/// ShuffleEntrys in the lists.
385struct ShuffleEntry {
386 // The supported operations. The first 16 match those generated by
387 // PerfectShuffle.cpp.
388 enum Operation {
389 OP_COPY = 0, // Copy, used for things like <u,u,u,3> to say it is <0,1,2,3>
390 OP_VREV,
391 OP_VDUP0,
392 OP_VDUP1,
393 OP_VDUP2,
394 OP_VDUP3,
395 OP_VEXT1,
396 OP_VEXT2,
397 OP_VEXT3,
398 OP_VUZPL, // VUZP, left result
399 OP_VUZPR, // VUZP, right result
400 OP_VZIPL, // VZIP, left result
401 OP_VZIPR, // VZIP, right result
402 OP_VTRNL, // VTRN, left result
403 OP_VTRNR, // VTRN, right result
404 OP_MOVLANE, // Move lane. RHSID is the lane to move into
405
406 OP_MOVLANE32,
407 OP_MOVLANE64,
408 };
409
410 /// Special IDs for the LHS and RHS values.
411 enum IDs {
412 LHS = 0xfe,
413 RHS = 0xff,
414 };
415
416 Operation Op;
417 unsigned LHSID;
418 unsigned RHSID;
419};
420
421inline unsigned
422generatePerfectShuffleFromTable(unsigned PFTableIndex,
423 SmallVector<ShuffleEntry> &Entries) {
424 unsigned PFEntry = PerfectShuffleTable[PFTableIndex];
425 ShuffleEntry::Operation OpNum =
426 (ShuffleEntry::Operation)((PFEntry >> 26) & 0x0F);
427 unsigned LHSID = (PFEntry >> 13) & ((1 << 13) - 1);
428 unsigned RHSID = (PFEntry >> 0) & ((1 << 13) - 1);
429
430 if (OpNum == ShuffleEntry::OP_COPY) {
431 if (LHSID == (1 * 9 + 2) * 9 + 3)
432 return ShuffleEntry::LHS;
433 assert(LHSID == ((4 * 9 + 5) * 9 + 6) * 9 + 7 && "Illegal OP_COPY!");
434 return ShuffleEntry::RHS;
435 }
436
437 unsigned OpLHS = generatePerfectShuffleFromTable(PFTableIndex: LHSID, Entries);
438
439 if (OpNum == ShuffleEntry::OP_MOVLANE) {
440 // Decompose a PerfectShuffle ID to get the Mask for lane Elt
441 auto getPFIDLane = [](unsigned ID, int Elt) -> int {
442 assert(Elt < 4 && "Expected Perfect Lanes to be less than 4");
443 Elt = 3 - Elt;
444 while (Elt > 0) {
445 ID /= 9;
446 Elt--;
447 }
448 return (ID % 9 == 8) ? -1 : ID % 9;
449 };
450
451 // OP_MOVLANE are either D movs (if bit 0x4 is set) or S movs. D movs
452 // convert into a higher type.
453 if (RHSID & 0x4) {
454 int MaskElt = getPFIDLane(PFTableIndex, (RHSID & 0x01) << 1) >> 1;
455 if (MaskElt == -1)
456 MaskElt =
457 (getPFIDLane(PFTableIndex, ((RHSID & 0x01) << 1) + 1) - 1) >> 1;
458 assert(MaskElt >= 0 && "Didn't expect an undef movlane index!");
459 unsigned ExtLane = MaskElt < 2 ? MaskElt : (MaskElt - 2);
460 Entries.push_back(Elt: {.Op: ShuffleEntry::OP_MOVLANE64, .LHSID: OpLHS,
461 .RHSID: (MaskElt >= 2) << 16 | ExtLane << 8 | (RHSID & 0x3)});
462 } else {
463 int MaskElt = getPFIDLane(PFTableIndex, RHSID);
464 assert(MaskElt >= 0 && "Didn't expect an undef movlane index!");
465 unsigned ExtLane = MaskElt < 4 ? MaskElt : (MaskElt - 4);
466 Entries.push_back(Elt: {.Op: ShuffleEntry::OP_MOVLANE32, .LHSID: OpLHS,
467 .RHSID: (MaskElt >= 4) << 16 | ExtLane << 8 | (RHSID & 0x3)});
468 }
469 return Entries.size() - 1;
470 }
471
472 unsigned OpRHS = generatePerfectShuffleFromTable(PFTableIndex: RHSID, Entries);
473
474 Entries.push_back(Elt: {.Op: OpNum, .LHSID: OpLHS, .RHSID: OpRHS});
475 return Entries.size() - 1;
476}
477
478/// generatePerfectShuffle - Given a Mask, attempt to generate the optimal
479/// sequence of instructions using zip/uzp/trn/dup/etc. Currently uses the
480/// perfect shuffle tables.
481inline bool generatePerfectShuffle(ArrayRef<int> Mask, unsigned NumElts,
482 SmallVector<ShuffleEntry> &Entries) {
483 assert(NumElts == 4 && "Only 4 element masks supported at the moment");
484
485 // Compute the index in the perfect shuffle table.
486 unsigned PFIndexes[4];
487 for (unsigned i = 0; i != 4; ++i) {
488 if (Mask[i] < 0)
489 PFIndexes[i] = 8;
490 else
491 PFIndexes[i] = Mask[i];
492 }
493
494 unsigned PFTableIndex = PFIndexes[0] * 9 * 9 * 9 + PFIndexes[1] * 9 * 9 +
495 PFIndexes[2] * 9 + PFIndexes[3];
496 unsigned Idx = generatePerfectShuffleFromTable(PFTableIndex, Entries);
497 return Idx == Entries.size() - 1;
498}
499
500} // namespace llvm
501
502#endif
503