1//===- AArch64ExpandImm.h - AArch64 Immediate Expansion -------------------===//
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 implements the AArch64ExpandImm stuff.
10//
11//===----------------------------------------------------------------------===//
12
13#include "AArch64ExpandImm.h"
14#include "AArch64.h"
15#include "AArch64Subtarget.h"
16#include "MCTargetDesc/AArch64AddressingModes.h"
17
18using namespace llvm;
19using namespace llvm::AArch64_IMM;
20
21/// Helper function which extracts the specified 16-bit chunk from a
22/// 64-bit value.
23static uint64_t getChunk(uint64_t Imm, unsigned ChunkIdx) {
24 assert(ChunkIdx < 4 && "Out of range chunk index specified!");
25
26 return (Imm >> (ChunkIdx * 16)) & 0xFFFF;
27}
28
29/// Check whether the given 16-bit chunk replicated to full 64-bit width
30/// can be materialized with an ORR instruction.
31static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding) {
32 Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk;
33
34 return AArch64_AM::processLogicalImmediate(Imm: Chunk, RegSize: 64, Encoding);
35}
36
37/// Check for identical 16-bit chunks within the constant and if so
38/// materialize them with a single ORR instruction. The remaining one or two
39/// 16-bit chunks will be materialized with MOVK instructions.
40///
41/// This allows us to materialize constants like |A|B|A|A| or |A|B|C|A| (order
42/// of the chunks doesn't matter), assuming |A|A|A|A| can be materialized with
43/// an ORR instruction.
44static bool tryToreplicateChunks(uint64_t UImm,
45 SmallVectorImpl<ImmInsnModel> &Insn) {
46 using CountMap = DenseMap<uint64_t, unsigned>;
47
48 CountMap Counts;
49
50 // Scan the constant and count how often every chunk occurs.
51 for (unsigned Idx = 0; Idx < 4; ++Idx)
52 ++Counts[getChunk(Imm: UImm, ChunkIdx: Idx)];
53
54 // Traverse the chunks to find one which occurs more than once.
55 for (const auto &Chunk : Counts) {
56 const uint64_t ChunkVal = Chunk.first;
57 const unsigned Count = Chunk.second;
58
59 uint64_t Encoding = 0;
60
61 // We are looking for chunks which have two or three instances and can be
62 // materialized with an ORR instruction.
63 if ((Count != 2 && Count != 3) || !canUseOrr(Chunk: ChunkVal, Encoding))
64 continue;
65
66 const bool CountThree = Count == 3;
67
68 Insn.push_back(Elt: { .Opcode: AArch64::ORRXri, .Op1: 0, .Op2: Encoding });
69
70 unsigned ShiftAmt = 0;
71 uint64_t Imm16 = 0;
72 // Find the first chunk not materialized with the ORR instruction.
73 for (; ShiftAmt < 64; ShiftAmt += 16) {
74 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
75
76 if (Imm16 != ChunkVal)
77 break;
78 }
79
80 // Create the first MOVK instruction.
81 Insn.push_back(Elt: { .Opcode: AArch64::MOVKXi, .Op1: Imm16,
82 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: ShiftAmt) });
83
84 // In case we have three instances the whole constant is now materialized
85 // and we can exit.
86 if (CountThree)
87 return true;
88
89 // Find the remaining chunk which needs to be materialized.
90 for (ShiftAmt += 16; ShiftAmt < 64; ShiftAmt += 16) {
91 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
92
93 if (Imm16 != ChunkVal)
94 break;
95 }
96 Insn.push_back(Elt: { .Opcode: AArch64::MOVKXi, .Op1: Imm16,
97 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: ShiftAmt) });
98 return true;
99 }
100
101 return false;
102}
103
104/// Check whether this chunk matches the pattern '1...0...'. This pattern
105/// starts a contiguous sequence of ones if we look at the bits from the LSB
106/// towards the MSB.
107static bool isStartChunk(uint64_t Chunk) {
108 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
109 return false;
110
111 return isMask_64(Value: ~Chunk);
112}
113
114/// Check whether this chunk matches the pattern '0...1...' This pattern
115/// ends a contiguous sequence of ones if we look at the bits from the LSB
116/// towards the MSB.
117static bool isEndChunk(uint64_t Chunk) {
118 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
119 return false;
120
121 return isMask_64(Value: Chunk);
122}
123
124/// Clear or set all bits in the chunk at the given index.
125static uint64_t updateImm(uint64_t Imm, unsigned Idx, bool Clear) {
126 const uint64_t Mask = 0xFFFF;
127
128 if (Clear)
129 // Clear chunk in the immediate.
130 Imm &= ~(Mask << (Idx * 16));
131 else
132 // Set all bits in the immediate for the particular chunk.
133 Imm |= Mask << (Idx * 16);
134
135 return Imm;
136}
137
138/// Check whether the constant contains a sequence of contiguous ones,
139/// which might be interrupted by one or two chunks. If so, materialize the
140/// sequence of contiguous ones with an ORR instruction.
141/// Materialize the chunks which are either interrupting the sequence or outside
142/// of the sequence with a MOVK instruction.
143///
144/// Assuming S is a chunk which starts the sequence (1...0...), E is a chunk
145/// which ends the sequence (0...1...). Then we are looking for constants which
146/// contain at least one S and E chunk.
147/// E.g. |E|A|B|S|, |A|E|B|S| or |A|B|E|S|.
148///
149/// We are also looking for constants like |S|A|B|E| where the contiguous
150/// sequence of ones wraps around the MSB into the LSB.
151static bool trySequenceOfOnes(uint64_t UImm,
152 SmallVectorImpl<ImmInsnModel> &Insn) {
153 const int NotSet = -1;
154 const uint64_t Mask = 0xFFFF;
155
156 int StartIdx = NotSet;
157 int EndIdx = NotSet;
158 // Try to find the chunks which start/end a contiguous sequence of ones.
159 for (int Idx = 0; Idx < 4; ++Idx) {
160 int64_t Chunk = getChunk(Imm: UImm, ChunkIdx: Idx);
161 // Sign extend the 16-bit chunk to 64-bit.
162 Chunk = (Chunk << 48) >> 48;
163
164 if (isStartChunk(Chunk))
165 StartIdx = Idx;
166 else if (isEndChunk(Chunk))
167 EndIdx = Idx;
168 }
169
170 // Early exit in case we can't find a start/end chunk.
171 if (StartIdx == NotSet || EndIdx == NotSet)
172 return false;
173
174 // Outside of the contiguous sequence of ones everything needs to be zero.
175 uint64_t Outside = 0;
176 // Chunks between the start and end chunk need to have all their bits set.
177 uint64_t Inside = Mask;
178
179 // If our contiguous sequence of ones wraps around from the MSB into the LSB,
180 // just swap indices and pretend we are materializing a contiguous sequence
181 // of zeros surrounded by a contiguous sequence of ones.
182 if (StartIdx > EndIdx) {
183 std::swap(a&: StartIdx, b&: EndIdx);
184 std::swap(a&: Outside, b&: Inside);
185 }
186
187 uint64_t OrrImm = UImm;
188 int FirstMovkIdx = NotSet;
189 int SecondMovkIdx = NotSet;
190
191 // Find out which chunks we need to patch up to obtain a contiguous sequence
192 // of ones.
193 for (int Idx = 0; Idx < 4; ++Idx) {
194 const uint64_t Chunk = getChunk(Imm: UImm, ChunkIdx: Idx);
195
196 // Check whether we are looking at a chunk which is not part of the
197 // contiguous sequence of ones.
198 if ((Idx < StartIdx || EndIdx < Idx) && Chunk != Outside) {
199 OrrImm = updateImm(Imm: OrrImm, Idx, Clear: Outside == 0);
200
201 // Remember the index we need to patch.
202 if (FirstMovkIdx == NotSet)
203 FirstMovkIdx = Idx;
204 else
205 SecondMovkIdx = Idx;
206
207 // Check whether we are looking a chunk which is part of the contiguous
208 // sequence of ones.
209 } else if (Idx > StartIdx && Idx < EndIdx && Chunk != Inside) {
210 OrrImm = updateImm(Imm: OrrImm, Idx, Clear: Inside != Mask);
211
212 // Remember the index we need to patch.
213 if (FirstMovkIdx == NotSet)
214 FirstMovkIdx = Idx;
215 else
216 SecondMovkIdx = Idx;
217 }
218 }
219 assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!");
220
221 // Create the ORR-immediate instruction.
222 uint64_t Encoding = 0;
223 AArch64_AM::processLogicalImmediate(Imm: OrrImm, RegSize: 64, Encoding);
224 Insn.push_back(Elt: { .Opcode: AArch64::ORRXri, .Op1: 0, .Op2: Encoding });
225
226 const bool SingleMovk = SecondMovkIdx == NotSet;
227 Insn.push_back(Elt: { .Opcode: AArch64::MOVKXi, .Op1: getChunk(Imm: UImm, ChunkIdx: FirstMovkIdx),
228 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL,
229 Imm: FirstMovkIdx * 16) });
230
231 // Early exit in case we only need to emit a single MOVK instruction.
232 if (SingleMovk)
233 return true;
234
235 // Create the second MOVK instruction.
236 Insn.push_back(
237 Elt: {.Opcode: AArch64::MOVKXi, .Op1: getChunk(Imm: UImm, ChunkIdx: SecondMovkIdx),
238 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: SecondMovkIdx * 16)});
239
240 return true;
241}
242
243// Attempt to expand 64-bit immediate values that consist of shifted negated
244// components such as 0x1234'5678'edcb'a987, where the upper half is the
245// negation of the lower half. Immediates of this form can generally be
246// expanded via a sequence of MOVN+MOVK to expand the lower half, followed by
247// an EOR or EON to shift and negate the result to the upper half, for example:
248// mov x0, #-22137 // =0xffffffffffffa987
249// movk x0, #60875, lsl #16 // =0xffffffffedcba987
250// eor x0, x0, x0, lsl #32 // =0xffffffffedcba987 ^ 0xedcba98700000000
251// =0x12345678edcba987.
252// The logic extends to other shift amounts in the range [17, 48) (outside that
253// range we get runs of ones/zeros that are optimised separately).
254//
255// When the lower half contains a 16-bit chunk of ones, such as
256// 0x0000'5678'ffff'a987, the intermediate MOVK is redundant.
257// Similarly, when it contains a 16-bit chunk of zeros, such as
258// 0xffff'5678'0000'a987, the expansion can instead be effected by expanding
259// the negation of the lower half and negating the result with an EON, e.g.:
260// mov x0, #-43400 // =0xffffffffffff5678
261// eon x0, x0, x0, lsl #32 // =0xffffffffffff5678 ^ ~0xffff567800000000
262// =0xffffffffffff5678 ^ 0x0000a987ffffffff
263// =0xffff56780000a987.
264// In any of these cases, the expansion with EOR/EON saves an instruction
265// compared to the default expansion based on MOV and MOVKs.
266static bool tryCopyWithNegation(uint64_t Imm, bool AllowThreeSequence,
267 SmallVectorImpl<ImmInsnModel> &Insn) {
268 // Degenerate cases where Imm is a run of ones should be handled separately.
269 if (!Imm || llvm::isShiftedMask_64(Value: Imm))
270 return false;
271
272 const unsigned Mask = 0xffff;
273
274 auto tryExpansion = [&](unsigned Opc, uint64_t C, unsigned N) {
275 assert((C >> 32) == 0xffffffffULL && "Invalid immediate");
276 const unsigned Imm0 = C & Mask;
277 const unsigned Imm16 = (C >> 16) & Mask;
278 if (Imm0 != Mask && Imm16 != Mask && !AllowThreeSequence)
279 return false;
280
281 if (Imm0 != Mask) {
282 Insn.push_back(Elt: {.Opcode: AArch64::MOVNXi, .Op1: Imm0 ^ Mask, .Op2: 0});
283 if (Imm16 != Mask)
284 Insn.push_back(Elt: {.Opcode: AArch64::MOVKXi, .Op1: Imm16, .Op2: 16});
285 } else {
286 Insn.push_back(Elt: {.Opcode: AArch64::MOVNXi, .Op1: Imm16 ^ Mask, .Op2: 16});
287 }
288
289 Insn.push_back(Elt: {.Opcode: Opc, .Op1: std::nullopt, .Op2: N});
290 return true;
291 };
292
293 for (unsigned N = 17; N < 48; ++N) {
294 // Attempt EOR.
295 uint64_t C = 0xffffffff00000000ULL | (Imm ^ (Imm << N));
296 if ((C ^ (C << N)) == Imm && tryExpansion(AArch64::EORXrs, C, N))
297 return true;
298
299 // Attempt EON.
300 C = 0xffffffff00000000ULL | (Imm ^ ~(~Imm << N));
301 if ((C ^ ~(C << N)) == Imm && tryExpansion(AArch64::EONXrs, C, N))
302 return true;
303 }
304
305 return false;
306}
307
308static uint64_t GetRunOfOnesStartingAt(uint64_t V, uint64_t StartPosition) {
309 uint64_t NumOnes = llvm::countr_one(Value: V >> StartPosition);
310
311 uint64_t UnshiftedOnes;
312 if (NumOnes == 64) {
313 UnshiftedOnes = ~0ULL;
314 } else {
315 UnshiftedOnes = (1ULL << NumOnes) - 1;
316 }
317 return UnshiftedOnes << StartPosition;
318}
319
320static uint64_t MaximallyReplicateSubImmediate(uint64_t V, uint64_t Subset) {
321 uint64_t Result = Subset;
322
323 // 64, 32, 16, 8, 4, 2
324 for (uint64_t i = 0; i < 6; ++i) {
325 uint64_t Rotation = 1ULL << (6 - i);
326 uint64_t Closure = Result | llvm::rotl<uint64_t>(V: Result, R: Rotation);
327 if (Closure != (Closure & V)) {
328 break;
329 }
330 Result = Closure;
331 }
332
333 return Result;
334}
335
336// Find the logical immediate that covers the most bits in RemainingBits,
337// allowing for additional bits to be set that were set in OriginalBits.
338static uint64_t maximalLogicalImmWithin(uint64_t RemainingBits,
339 uint64_t OriginalBits) {
340 // Find the first set bit.
341 uint32_t Position = llvm::countr_zero(Val: RemainingBits);
342
343 // Get the first run of set bits.
344 uint64_t FirstRun = GetRunOfOnesStartingAt(V: OriginalBits, StartPosition: Position);
345
346 // Replicate the run as many times as possible, as long as the bits are set in
347 // RemainingBits.
348 uint64_t MaximalImm = MaximallyReplicateSubImmediate(V: OriginalBits, Subset: FirstRun);
349
350 return MaximalImm;
351}
352
353static std::optional<std::pair<uint64_t, uint64_t>>
354decomposeIntoOrrOfLogicalImmediates(uint64_t UImm) {
355 if (UImm == 0 || ~UImm == 0)
356 return std::nullopt;
357
358 // Make sure we don't have a run of ones split around the rotation boundary.
359 uint32_t InitialTrailingOnes = llvm::countr_one(Value: UImm);
360 uint64_t RotatedBits = llvm::rotr<uint64_t>(V: UImm, R: InitialTrailingOnes);
361
362 // Find the largest logical immediate that fits within the full immediate.
363 uint64_t MaximalImm1 = maximalLogicalImmWithin(RemainingBits: RotatedBits, OriginalBits: RotatedBits);
364
365 // Remove all bits that are set by this mask.
366 uint64_t RemainingBits = RotatedBits & ~MaximalImm1;
367
368 // Find the largest logical immediate covering the remaining bits, allowing
369 // for additional bits to be set that were also set in the original immediate.
370 uint64_t MaximalImm2 = maximalLogicalImmWithin(RemainingBits, OriginalBits: RotatedBits);
371
372 // If any bits still haven't been covered, then give up.
373 if (RemainingBits & ~MaximalImm2)
374 return std::nullopt;
375
376 // Make sure to un-rotate the immediates.
377 return std::make_pair(x: rotl(V: MaximalImm1, R: InitialTrailingOnes),
378 y: rotl(V: MaximalImm2, R: InitialTrailingOnes));
379}
380
381// Attempt to expand an immediate as the ORR of a pair of logical immediates.
382static bool tryOrrOfLogicalImmediates(uint64_t UImm,
383 SmallVectorImpl<ImmInsnModel> &Insn) {
384 auto MaybeDecomposition = decomposeIntoOrrOfLogicalImmediates(UImm);
385 if (MaybeDecomposition == std::nullopt)
386 return false;
387 uint64_t Imm1 = MaybeDecomposition->first;
388 uint64_t Imm2 = MaybeDecomposition->second;
389
390 uint64_t Encoding1, Encoding2;
391 bool Imm1Success = AArch64_AM::processLogicalImmediate(Imm: Imm1, RegSize: 64, Encoding&: Encoding1);
392 bool Imm2Success = AArch64_AM::processLogicalImmediate(Imm: Imm2, RegSize: 64, Encoding&: Encoding2);
393
394 if (Imm1Success && Imm2Success) {
395 // Create the ORR-immediate instructions.
396 Insn.push_back(Elt: {.Opcode: AArch64::ORRXri, .Op1: 0, .Op2: Encoding1});
397 Insn.push_back(Elt: {.Opcode: AArch64::ORRXri, .Op1: 1, .Op2: Encoding2});
398 return true;
399 }
400
401 return false;
402}
403
404// Attempt to expand an immediate as the AND of a pair of logical immediates.
405// This is done by applying DeMorgan's law, under which logical immediates
406// are closed.
407static bool tryAndOfLogicalImmediates(uint64_t UImm,
408 SmallVectorImpl<ImmInsnModel> &Insn) {
409 // Apply DeMorgan's law to turn this into an ORR problem.
410 auto MaybeDecomposition = decomposeIntoOrrOfLogicalImmediates(UImm: ~UImm);
411 if (MaybeDecomposition == std::nullopt)
412 return false;
413 uint64_t Imm1 = MaybeDecomposition->first;
414 uint64_t Imm2 = MaybeDecomposition->second;
415
416 uint64_t Encoding1, Encoding2;
417 bool Imm1Success = AArch64_AM::processLogicalImmediate(Imm: ~Imm1, RegSize: 64, Encoding&: Encoding1);
418 bool Imm2Success = AArch64_AM::processLogicalImmediate(Imm: ~Imm2, RegSize: 64, Encoding&: Encoding2);
419
420 if (Imm1Success && Imm2Success) {
421 // Materialize Imm1, the LHS of the AND
422 Insn.push_back(Elt: {.Opcode: AArch64::ORRXri, .Op1: 0, .Op2: Encoding1});
423 // AND Imm1 with Imm2
424 Insn.push_back(Elt: {.Opcode: AArch64::ANDXri, .Op1: 1, .Op2: Encoding2});
425 return true;
426 }
427
428 return false;
429}
430
431// Check whether the constant can be represented by exclusive-or of two 64-bit
432// logical immediates. If so, materialize it with an ORR instruction followed
433// by an EOR instruction.
434//
435// This encoding allows all remaining repeated byte patterns, and many repeated
436// 16-bit values, to be encoded without needing four instructions. It can also
437// represent some irregular bitmasks (although those would mostly only need
438// three instructions otherwise).
439static bool tryEorOfLogicalImmediates(uint64_t Imm,
440 SmallVectorImpl<ImmInsnModel> &Insn) {
441 // Determine the larger repetition size of the two possible logical
442 // immediates, by finding the repetition size of Imm.
443 unsigned BigSize = 64;
444
445 do {
446 BigSize /= 2;
447 uint64_t Mask = (1ULL << BigSize) - 1;
448
449 if ((Imm & Mask) != ((Imm >> BigSize) & Mask)) {
450 BigSize *= 2;
451 break;
452 }
453 } while (BigSize > 2);
454
455 uint64_t BigMask = ((uint64_t)-1LL) >> (64 - BigSize);
456
457 // Find the last bit of each run of ones, circularly. For runs which wrap
458 // around from bit 0 to bit 63, this is the bit before the most-significant
459 // zero, otherwise it is the least-significant bit in the run of ones.
460 uint64_t RunStarts = Imm & ~rotl<uint64_t>(V: Imm, R: 1);
461
462 // Find the smaller repetition size of the two possible logical immediates by
463 // counting the number of runs of one-bits within the BigSize-bit value. Both
464 // sizes may be the same. The EOR may add one or subtract one from the
465 // power-of-two count that can be represented by a logical immediate, or it
466 // may be left unchanged.
467 int RunsPerBigChunk = popcount(Value: RunStarts & BigMask);
468
469 static const int8_t BigToSmallSizeTable[32] = {
470 -1, -1, 0, 1, 2, 2, -1, 3, 3, 3, -1, -1, -1, -1, -1, 4,
471 4, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5,
472 };
473
474 int BigToSmallShift = BigToSmallSizeTable[RunsPerBigChunk];
475
476 // Early-exit if the big chunk couldn't be a power-of-two number of runs
477 // EORed with another single run.
478 if (BigToSmallShift == -1)
479 return false;
480
481 unsigned SmallSize = BigSize >> BigToSmallShift;
482
483 // 64-bit values with a bit set every (1 << index) bits.
484 static const uint64_t RepeatedOnesTable[] = {
485 0xffffffffffffffff, 0x5555555555555555, 0x1111111111111111,
486 0x0101010101010101, 0x0001000100010001, 0x0000000100000001,
487 0x0000000000000001,
488 };
489
490 // This RepeatedOnesTable lookup is a faster implementation of the division
491 // 0xffffffffffffffff / ((1 << SmallSize) - 1), and can be thought of as
492 // dividing the 64-bit value into fields of width SmallSize, and placing a
493 // one in the least significant bit of each field.
494 uint64_t SmallOnes = RepeatedOnesTable[countr_zero(Val: SmallSize)];
495
496 // Now we try to find the number of ones in each of the smaller repetitions,
497 // by looking at runs of ones in Imm. This can take three attempts, as the
498 // EOR may have changed the length of the first two runs we find.
499
500 // Rotate a run of ones so we can count the number of trailing set bits.
501 int Rotation = countr_zero(Val: RunStarts);
502 uint64_t RotatedImm = rotr<uint64_t>(V: Imm, R: Rotation);
503 for (int Attempt = 0; Attempt < 3; ++Attempt) {
504 unsigned RunLength = countr_one(Value: RotatedImm);
505
506 // Construct candidate values BigImm and SmallImm, such that if these two
507 // values are encodable, we have a solution. (SmallImm is constructed to be
508 // encodable, but this isn't guaranteed when RunLength >= SmallSize)
509 uint64_t SmallImm =
510 rotl<uint64_t>(V: (SmallOnes << RunLength) - SmallOnes, R: Rotation);
511 uint64_t BigImm = Imm ^ SmallImm;
512
513 uint64_t BigEncoding = 0;
514 uint64_t SmallEncoding = 0;
515 if (AArch64_AM::processLogicalImmediate(Imm: BigImm, RegSize: 64, Encoding&: BigEncoding) &&
516 AArch64_AM::processLogicalImmediate(Imm: SmallImm, RegSize: 64, Encoding&: SmallEncoding)) {
517 Insn.push_back(Elt: {.Opcode: AArch64::ORRXri, .Op1: 0, .Op2: SmallEncoding});
518 Insn.push_back(Elt: {.Opcode: AArch64::EORXri, .Op1: 1, .Op2: BigEncoding});
519 return true;
520 }
521
522 // Rotate to the next run of ones
523 Rotation += countr_zero(Val: rotr<uint64_t>(V: RunStarts, R: Rotation) & ~1);
524 RotatedImm = rotr<uint64_t>(V: Imm, R: Rotation);
525 }
526
527 return false;
528}
529
530/// \brief Expand a MOVi32imm or MOVi64imm pseudo instruction to a
531/// MOVZ or MOVN of width BitSize followed by up to 3 MOVK instructions.
532static inline void expandMOVImmSimple(uint64_t Imm, unsigned BitSize,
533 unsigned OneChunks, unsigned ZeroChunks,
534 SmallVectorImpl<ImmInsnModel> &Insn) {
535 const unsigned Mask = 0xFFFF;
536
537 // Use a MOVZ or MOVN instruction to set the high bits, followed by one or
538 // more MOVK instructions to insert additional 16-bit portions into the
539 // lower bits.
540 bool isNeg = false;
541
542 // Use MOVN to materialize the high bits if we have more all one chunks
543 // than all zero chunks.
544 if (OneChunks > ZeroChunks) {
545 isNeg = true;
546 Imm = ~Imm;
547 }
548
549 unsigned FirstOpc;
550 if (BitSize == 32) {
551 Imm &= (1LL << 32) - 1;
552 FirstOpc = (isNeg ? AArch64::MOVNWi : AArch64::MOVZWi);
553 } else {
554 FirstOpc = (isNeg ? AArch64::MOVNXi : AArch64::MOVZXi);
555 }
556 unsigned Shift = 0; // LSL amount for high bits with MOVZ/MOVN
557 unsigned LastShift = 0; // LSL amount for last MOVK
558 if (Imm != 0) {
559 unsigned LZ = llvm::countl_zero(Val: Imm);
560 unsigned TZ = llvm::countr_zero(Val: Imm);
561 Shift = (TZ / 16) * 16;
562 LastShift = ((63 - LZ) / 16) * 16;
563 }
564 unsigned Imm16 = (Imm >> Shift) & Mask;
565
566 Insn.push_back(Elt: { .Opcode: FirstOpc, .Op1: Imm16,
567 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: Shift) });
568
569 if (Shift == LastShift)
570 return;
571
572 // If a MOVN was used for the high bits of a negative value, flip the rest
573 // of the bits back for use with MOVK.
574 if (isNeg)
575 Imm = ~Imm;
576
577 unsigned Opc = (BitSize == 32 ? AArch64::MOVKWi : AArch64::MOVKXi);
578 while (Shift < LastShift) {
579 Shift += 16;
580 Imm16 = (Imm >> Shift) & Mask;
581 if (Imm16 == (isNeg ? Mask : 0))
582 continue; // This 16-bit portion is already set correctly.
583
584 Insn.push_back(Elt: { .Opcode: Opc, .Op1: Imm16,
585 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: Shift) });
586 }
587
588 // Now, we get 16-bit divided Imm. If high and low bits are same in
589 // 32-bit, there is an opportunity to reduce instruction.
590 if (Insn.size() > 2 && (Imm >> 32) == (Imm & 0xffffffffULL)) {
591 for (int Size = Insn.size(); Size > 2; Size--)
592 Insn.pop_back();
593 Insn.push_back(Elt: {.Opcode: AArch64::ORRXrs, .Op1: 0, .Op2: 32});
594 }
595}
596
597/// Expand a MOVi32imm or MOVi64imm pseudo instruction to one or more
598/// real move-immediate instructions to synthesize the immediate.
599void AArch64_IMM::expandMOVImm(uint64_t Imm, unsigned BitSize,
600 SmallVectorImpl<ImmInsnModel> &Insn) {
601 const unsigned Mask = 0xFFFF;
602
603 // Scan the immediate and count the number of 16-bit chunks which are either
604 // all ones or all zeros.
605 unsigned OneChunks = 0;
606 unsigned ZeroChunks = 0;
607 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {
608 const unsigned Chunk = (Imm >> Shift) & Mask;
609 if (Chunk == Mask)
610 OneChunks++;
611 else if (Chunk == 0)
612 ZeroChunks++;
613 }
614
615 // Prefer MOVZ/MOVN over ORR because of the rules for the "mov" alias.
616 if ((BitSize / 16) - OneChunks <= 1 || (BitSize / 16) - ZeroChunks <= 1) {
617 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
618 assert(Insn.size() == 1 &&
619 "Move of immediate should have expanded to a single MOVZ/MOVN");
620 return;
621 }
622
623 // Try a single ORR.
624 uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize);
625 uint64_t Encoding;
626 if (AArch64_AM::processLogicalImmediate(Imm: UImm, RegSize: BitSize, Encoding)) {
627 unsigned Opc = (BitSize == 32 ? AArch64::ORRWri : AArch64::ORRXri);
628 Insn.push_back(Elt: { .Opcode: Opc, .Op1: 0, .Op2: Encoding });
629 return;
630 }
631
632 // One to up three instruction sequences.
633 //
634 // Prefer MOVZ/MOVN followed by MOVK; it's more readable, and possibly the
635 // fastest sequence with fast literal generation.
636 if (OneChunks >= (BitSize / 16) - 2 || ZeroChunks >= (BitSize / 16) - 2) {
637 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
638 return;
639 }
640
641 assert(BitSize == 64 && "All 32-bit immediates can be expanded with a"
642 "MOVZ/MOVK pair");
643
644 // Try other two-instruction sequences.
645
646 // 64-bit ORR followed by MOVK.
647 // We try to construct the ORR immediate in three different ways: either we
648 // zero out the chunk which will be replaced, we fill the chunk which will
649 // be replaced with ones, or we take the bit pattern from the other half of
650 // the 64-bit immediate. This is comprehensive because of the way ORR
651 // immediates are constructed.
652 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {
653 uint64_t ShiftedMask = (0xFFFFULL << Shift);
654 uint64_t ZeroChunk = UImm & ~ShiftedMask;
655 uint64_t OneChunk = UImm | ShiftedMask;
656 uint64_t RotatedImm = llvm::rotl(V: UImm, R: 32);
657 uint64_t ReplicateChunk = ZeroChunk | (RotatedImm & ShiftedMask);
658 if (AArch64_AM::processLogicalImmediate(Imm: ZeroChunk, RegSize: BitSize, Encoding) ||
659 AArch64_AM::processLogicalImmediate(Imm: OneChunk, RegSize: BitSize, Encoding) ||
660 AArch64_AM::processLogicalImmediate(Imm: ReplicateChunk, RegSize: BitSize,
661 Encoding)) {
662 // Create the ORR-immediate instruction.
663 Insn.push_back(Elt: { .Opcode: AArch64::ORRXri, .Op1: 0, .Op2: Encoding });
664
665 // Create the MOVK instruction.
666 const unsigned Imm16 = getChunk(Imm: UImm, ChunkIdx: Shift / 16);
667 Insn.push_back(Elt: { .Opcode: AArch64::MOVKXi, .Op1: Imm16,
668 .Op2: AArch64_AM::getShifterImm(ST: AArch64_AM::LSL, Imm: Shift) });
669 return;
670 }
671 }
672
673 // Attempt to use a sequence of two ORR-immediate instructions.
674 if (tryOrrOfLogicalImmediates(UImm: Imm, Insn))
675 return;
676
677 // Attempt to use a sequence of ORR-immediate followed by AND-immediate.
678 if (tryAndOfLogicalImmediates(UImm: Imm, Insn))
679 return;
680
681 // Attempt to use a sequence of ORR-immediate followed by EOR-immediate.
682 if (tryEorOfLogicalImmediates(Imm: UImm, Insn))
683 return;
684
685 // Attempt to use a sequence of MOVN+EOR/EON (shifted register).
686 if (tryCopyWithNegation(Imm, /*AllowThreeSequence=*/false, Insn))
687 return;
688
689 // FIXME: Add more two-instruction sequences.
690
691 // Three instruction sequences.
692 //
693 // Prefer MOVZ/MOVN followed by two MOVK; it's more readable, and possibly
694 // the fastest sequence with fast literal generation. (If neither MOVK is
695 // part of a fast literal generation pair, it could be slower than the
696 // four-instruction sequence, but we won't worry about that for now.)
697 if (OneChunks || ZeroChunks) {
698 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
699 return;
700 }
701
702 // Check for identical 16-bit chunks within the constant and if so materialize
703 // them with a single ORR instruction. The remaining one or two 16-bit chunks
704 // will be materialized with MOVK instructions.
705 if (BitSize == 64 && tryToreplicateChunks(UImm, Insn))
706 return;
707
708 // Check whether the constant contains a sequence of contiguous ones, which
709 // might be interrupted by one or two chunks. If so, materialize the sequence
710 // of contiguous ones with an ORR instruction. Materialize the chunks which
711 // are either interrupting the sequence or outside of the sequence with a
712 // MOVK instruction.
713 if (BitSize == 64 && trySequenceOfOnes(UImm, Insn))
714 return;
715
716 // Attempt to use a sequence of MOVN+MOVK+EOR/EON (shifted register).
717 if (tryCopyWithNegation(Imm, /*AllowThreeSequence=*/true, Insn))
718 return;
719
720 // We found no possible two or three instruction sequence; use the general
721 // four-instruction sequence.
722 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
723}
724
725void AArch64_IMM::expandMOVAddr(unsigned Opcode, unsigned TargetFlags,
726 bool IsTargetMachO,
727 SmallVectorImpl<AddrInsnModel> &Insn) {
728 if (Opcode == AArch64::MOVaddrBA && IsTargetMachO) {
729 // Block address on Mach-O goes through a constant pool.
730 Insn.push_back(Elt: {.Opcode: AArch64::ADRP});
731 Insn.push_back(Elt: {.Opcode: AArch64::LDRXui});
732 return;
733 }
734 Insn.push_back(Elt: {.Opcode: AArch64::ADRP});
735 if (TargetFlags & AArch64II::MO_TAGGED)
736 Insn.push_back(Elt: {.Opcode: AArch64::MOVKXi});
737 Insn.push_back(Elt: {.Opcode: AArch64::ADDXri});
738}
739
740bool AArch64_IMM::expandVectorMOVImm(
741 APInt Imm, SmallVectorImpl<AArch64_IMM::ImmInsnModel> &Insns,
742 const AArch64Subtarget &ST) {
743 assert((Imm.getBitWidth() == 64 || Imm.getBitWidth() == 128) &&
744 "Expected vector sized constant");
745 bool Is64Bit = Imm.getBitWidth() == 64;
746
747 if (ST.isNeonAvailable() && Imm.getHiBits(numBits: 64) == Imm.getLoBits(numBits: 64)) {
748 uint64_t Value = Imm.trunc(width: 64).getZExtValue();
749 if (Value == 0) {
750 Insns.push_back(Elt: {.Opcode: AArch64::FMOVD0, .Op1: std::nullopt, .Op2: std::nullopt});
751 return true;
752 }
753 if (AArch64_AM::isAdvSIMDModImmType10(Imm: Value)) {
754 unsigned Opc = Is64Bit ? AArch64::MOVID : AArch64::MOVIv2d_ns;
755 Insns.push_back(
756 Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType10(Imm: Value), .Op2: std::nullopt});
757 return true;
758 }
759 if (AArch64_AM::isAdvSIMDModImmType1(Imm: Value)) {
760 unsigned Opc = Is64Bit ? AArch64::MOVIv2i32 : AArch64::MOVIv4i32;
761 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType1(Imm: Value), .Op2: 0});
762 return true;
763 }
764 if (AArch64_AM::isAdvSIMDModImmType2(Imm: Value)) {
765 unsigned Opc = Is64Bit ? AArch64::MOVIv2i32 : AArch64::MOVIv4i32;
766 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType2(Imm: Value), .Op2: 8});
767 return true;
768 }
769 if (AArch64_AM::isAdvSIMDModImmType3(Imm: Value)) {
770 unsigned Opc = Is64Bit ? AArch64::MOVIv2i32 : AArch64::MOVIv4i32;
771 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType3(Imm: Value), .Op2: 16});
772 return true;
773 }
774 if (AArch64_AM::isAdvSIMDModImmType4(Imm: Value)) {
775 unsigned Opc = Is64Bit ? AArch64::MOVIv2i32 : AArch64::MOVIv4i32;
776 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType4(Imm: Value), .Op2: 24});
777 return true;
778 }
779 if (AArch64_AM::isAdvSIMDModImmType5(Imm: Value)) {
780 unsigned Opc = Is64Bit ? AArch64::MOVIv4i16 : AArch64::MOVIv8i16;
781 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType5(Imm: Value), .Op2: 0});
782 return true;
783 }
784 if (AArch64_AM::isAdvSIMDModImmType6(Imm: Value)) {
785 unsigned Opc = Is64Bit ? AArch64::MOVIv4i16 : AArch64::MOVIv8i16;
786 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType6(Imm: Value), .Op2: 8});
787 return true;
788 }
789 if (AArch64_AM::isAdvSIMDModImmType7(Imm: Value)) {
790 unsigned Opc = Is64Bit ? AArch64::MOVIv2s_msl : AArch64::MOVIv4s_msl;
791 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType7(Imm: Value), .Op2: 264});
792 return true;
793 }
794 if (AArch64_AM::isAdvSIMDModImmType8(Imm: Value)) {
795 unsigned Opc = Is64Bit ? AArch64::MOVIv2s_msl : AArch64::MOVIv4s_msl;
796 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType8(Imm: Value), .Op2: 272});
797 return true;
798 }
799 if (AArch64_AM::isAdvSIMDModImmType9(Imm: Value)) {
800 unsigned Opc = Is64Bit ? AArch64::MOVIv8b_ns : AArch64::MOVIv16b_ns;
801 Insns.push_back(
802 Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType9(Imm: Value), .Op2: std::nullopt});
803 return true;
804 }
805 if (AArch64_AM::isAdvSIMDModImmType11(Imm: Value)) {
806 unsigned Opc = Is64Bit ? AArch64::FMOVv2f32_ns : AArch64::FMOVv4f32_ns;
807 Insns.push_back(
808 Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType11(Imm: Value), .Op2: std::nullopt});
809 return true;
810 }
811 if (AArch64_AM::isAdvSIMDModImmType12(Imm: Value)) {
812 unsigned Opc = Is64Bit ? AArch64::FMOVDi : AArch64::FMOVv2f64_ns;
813 Insns.push_back(
814 Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType12(Imm: Value), .Op2: std::nullopt});
815 return true;
816 }
817
818 APInt NotImm = ~Imm;
819 Value = NotImm.trunc(width: 64).getZExtValue();
820 if (AArch64_AM::isAdvSIMDModImmType1(Imm: Value)) {
821 unsigned Opc = Is64Bit ? AArch64::MVNIv2i32 : AArch64::MVNIv4i32;
822 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType1(Imm: Value), .Op2: 0});
823 return true;
824 }
825 if (AArch64_AM::isAdvSIMDModImmType2(Imm: Value)) {
826 unsigned Opc = Is64Bit ? AArch64::MVNIv2i32 : AArch64::MVNIv4i32;
827 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType2(Imm: Value), .Op2: 8});
828 return true;
829 }
830 if (AArch64_AM::isAdvSIMDModImmType3(Imm: Value)) {
831 unsigned Opc = Is64Bit ? AArch64::MVNIv2i32 : AArch64::MVNIv4i32;
832 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType3(Imm: Value), .Op2: 16});
833 return true;
834 }
835 if (AArch64_AM::isAdvSIMDModImmType4(Imm: Value)) {
836 unsigned Opc = Is64Bit ? AArch64::MVNIv2i32 : AArch64::MVNIv4i32;
837 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType4(Imm: Value), .Op2: 24});
838 return true;
839 }
840 if (AArch64_AM::isAdvSIMDModImmType5(Imm: Value)) {
841 unsigned Opc = Is64Bit ? AArch64::MVNIv4i16 : AArch64::MVNIv8i16;
842 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType5(Imm: Value), .Op2: 0});
843 return true;
844 }
845 if (AArch64_AM::isAdvSIMDModImmType6(Imm: Value)) {
846 unsigned Opc = Is64Bit ? AArch64::MVNIv4i16 : AArch64::MVNIv8i16;
847 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType6(Imm: Value), .Op2: 8});
848 return true;
849 }
850 if (AArch64_AM::isAdvSIMDModImmType7(Imm: Value)) {
851 unsigned Opc = Is64Bit ? AArch64::MVNIv2s_msl : AArch64::MVNIv4s_msl;
852 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType7(Imm: Value), .Op2: 264});
853 return true;
854 }
855 if (AArch64_AM::isAdvSIMDModImmType8(Imm: Value)) {
856 unsigned Opc = Is64Bit ? AArch64::MVNIv2s_msl : AArch64::MVNIv4s_msl;
857 Insns.push_back(Elt: {.Opcode: Opc, .Op1: AArch64_AM::encodeAdvSIMDModImmType8(Imm: Value), .Op2: 272});
858 return true;
859 }
860 }
861
862 if (ST.isNeonAvailable() && ST.hasFullFP16() && Imm.isSplat(SplatSizeInBits: 16)) {
863 int Enc = AArch64_AM::getFP16Imm(Imm: Imm.trunc(width: 16));
864 if (Enc != -1) {
865 unsigned Opc = Is64Bit ? AArch64::FMOVv4f16_ns : AArch64::FMOVv8f16_ns;
866 Insns.push_back(Elt: {.Opcode: Opc, .Op1: Enc, .Op2: std::nullopt});
867 return true;
868 }
869 }
870
871 // TODO: We should be able to support 64-bit destinations too
872 if (ST.hasSVE() && !Is64Bit && Imm.getHiBits(numBits: 64) == Imm.getLoBits(numBits: 64)) {
873 // See if we can make use of the SVE dup instruction.
874 APInt Val64 = Imm.trunc(width: 64);
875 int32_t ImmVal, ShiftVal;
876 if (AArch64_AM::isSVECpyDupImm(SizeInBits: 64, Val: Val64.getSExtValue(), Imm&: ImmVal,
877 Shift&: ShiftVal)) {
878 Insns.push_back(
879 Elt: {.Opcode: AArch64::DUP_ZI_D, .Op1: (uint64_t)ImmVal, .Op2: (uint64_t)ShiftVal});
880 return true;
881 }
882 uint64_t Encoding;
883 if (AArch64_AM::isSVELogicalImm(SizeInBits: 64, ImmVal: Val64.getZExtValue(), Encoding)) {
884 Insns.push_back(Elt: {.Opcode: AArch64::DUPM_ZI, .Op1: Encoding, .Op2: std::nullopt});
885 return true;
886 }
887 }
888
889 return false;
890}
891