1 //===- AArch64ExpandImm.h - AArch64 Immediate Expansion -------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements the AArch64ExpandImm stuff.
11 //===----------------------------------------------------------------------===//
14 #include "AArch64ExpandImm.h"
15 #include "MCTargetDesc/AArch64AddressingModes.h"
19 namespace AArch64_IMM {
21 /// Helper function which extracts the specified 16-bit chunk from a
23 static uint64_t getChunk(uint64_t Imm, unsigned ChunkIdx) {
24 assert(ChunkIdx < 4 && "Out of range chunk index specified!");
26 return (Imm >> (ChunkIdx * 16)) & 0xFFFF;
29 /// Check whether the given 16-bit chunk replicated to full 64-bit width
30 /// can be materialized with an ORR instruction.
31 static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding) {
32 Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk;
34 return AArch64_AM::processLogicalImmediate(Chunk, 64, Encoding);
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.
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.
44 static bool tryToreplicateChunks(uint64_t UImm,
45 SmallVectorImpl<ImmInsnModel> &Insn) {
46 using CountMap = DenseMap<uint64_t, unsigned>;
50 // Scan the constant and count how often every chunk occurs.
51 for (unsigned Idx = 0; Idx < 4; ++Idx)
52 ++Counts[getChunk(UImm, Idx)];
54 // Traverse the chunks to find one which occurs more than once.
55 for (CountMap::const_iterator Chunk = Counts.begin(), End = Counts.end();
56 Chunk != End; ++Chunk) {
57 const uint64_t ChunkVal = Chunk->first;
58 const unsigned Count = Chunk->second;
60 uint64_t Encoding = 0;
62 // We are looking for chunks which have two or three instances and can be
63 // materialized with an ORR instruction.
64 if ((Count != 2 && Count != 3) || !canUseOrr(ChunkVal, Encoding))
67 const bool CountThree = Count == 3;
69 Insn.push_back({ AArch64::ORRXri, 0, Encoding });
71 unsigned ShiftAmt = 0;
73 // Find the first chunk not materialized with the ORR instruction.
74 for (; ShiftAmt < 64; ShiftAmt += 16) {
75 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
77 if (Imm16 != ChunkVal)
81 // Create the first MOVK instruction.
82 Insn.push_back({ AArch64::MOVKXi, Imm16,
83 AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) });
85 // In case we have three instances the whole constant is now materialized
90 // Find the remaining chunk which needs to be materialized.
91 for (ShiftAmt += 16; ShiftAmt < 64; ShiftAmt += 16) {
92 Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
94 if (Imm16 != ChunkVal)
97 Insn.push_back({ AArch64::MOVKXi, Imm16,
98 AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) });
105 /// Check whether this chunk matches the pattern '1...0...'. This pattern
106 /// starts a contiguous sequence of ones if we look at the bits from the LSB
108 static bool isStartChunk(uint64_t Chunk) {
109 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
112 return isMask_64(~Chunk);
115 /// Check whether this chunk matches the pattern '0...1...' This pattern
116 /// ends a contiguous sequence of ones if we look at the bits from the LSB
118 static bool isEndChunk(uint64_t Chunk) {
119 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max())
122 return isMask_64(Chunk);
125 /// Clear or set all bits in the chunk at the given index.
126 static uint64_t updateImm(uint64_t Imm, unsigned Idx, bool Clear) {
127 const uint64_t Mask = 0xFFFF;
130 // Clear chunk in the immediate.
131 Imm &= ~(Mask << (Idx * 16));
133 // Set all bits in the immediate for the particular chunk.
134 Imm |= Mask << (Idx * 16);
139 /// Check whether the constant contains a sequence of contiguous ones,
140 /// which might be interrupted by one or two chunks. If so, materialize the
141 /// sequence of contiguous ones with an ORR instruction.
142 /// Materialize the chunks which are either interrupting the sequence or outside
143 /// of the sequence with a MOVK instruction.
145 /// Assuming S is a chunk which starts the sequence (1...0...), E is a chunk
146 /// which ends the sequence (0...1...). Then we are looking for constants which
147 /// contain at least one S and E chunk.
148 /// E.g. |E|A|B|S|, |A|E|B|S| or |A|B|E|S|.
150 /// We are also looking for constants like |S|A|B|E| where the contiguous
151 /// sequence of ones wraps around the MSB into the LSB.
152 static bool trySequenceOfOnes(uint64_t UImm,
153 SmallVectorImpl<ImmInsnModel> &Insn) {
154 const int NotSet = -1;
155 const uint64_t Mask = 0xFFFF;
157 int StartIdx = NotSet;
159 // Try to find the chunks which start/end a contiguous sequence of ones.
160 for (int Idx = 0; Idx < 4; ++Idx) {
161 int64_t Chunk = getChunk(UImm, Idx);
162 // Sign extend the 16-bit chunk to 64-bit.
163 Chunk = (Chunk << 48) >> 48;
165 if (isStartChunk(Chunk))
167 else if (isEndChunk(Chunk))
171 // Early exit in case we can't find a start/end chunk.
172 if (StartIdx == NotSet || EndIdx == NotSet)
175 // Outside of the contiguous sequence of ones everything needs to be zero.
176 uint64_t Outside = 0;
177 // Chunks between the start and end chunk need to have all their bits set.
178 uint64_t Inside = Mask;
180 // If our contiguous sequence of ones wraps around from the MSB into the LSB,
181 // just swap indices and pretend we are materializing a contiguous sequence
182 // of zeros surrounded by a contiguous sequence of ones.
183 if (StartIdx > EndIdx) {
184 std::swap(StartIdx, EndIdx);
185 std::swap(Outside, Inside);
188 uint64_t OrrImm = UImm;
189 int FirstMovkIdx = NotSet;
190 int SecondMovkIdx = NotSet;
192 // Find out which chunks we need to patch up to obtain a contiguous sequence
194 for (int Idx = 0; Idx < 4; ++Idx) {
195 const uint64_t Chunk = getChunk(UImm, Idx);
197 // Check whether we are looking at a chunk which is not part of the
198 // contiguous sequence of ones.
199 if ((Idx < StartIdx || EndIdx < Idx) && Chunk != Outside) {
200 OrrImm = updateImm(OrrImm, Idx, Outside == 0);
202 // Remember the index we need to patch.
203 if (FirstMovkIdx == NotSet)
208 // Check whether we are looking a chunk which is part of the contiguous
210 } else if (Idx > StartIdx && Idx < EndIdx && Chunk != Inside) {
211 OrrImm = updateImm(OrrImm, Idx, Inside != Mask);
213 // Remember the index we need to patch.
214 if (FirstMovkIdx == NotSet)
220 assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!");
222 // Create the ORR-immediate instruction.
223 uint64_t Encoding = 0;
224 AArch64_AM::processLogicalImmediate(OrrImm, 64, Encoding);
225 Insn.push_back({ AArch64::ORRXri, 0, Encoding });
227 const bool SingleMovk = SecondMovkIdx == NotSet;
228 Insn.push_back({ AArch64::MOVKXi, getChunk(UImm, FirstMovkIdx),
229 AArch64_AM::getShifterImm(AArch64_AM::LSL,
230 FirstMovkIdx * 16) });
232 // Early exit in case we only need to emit a single MOVK instruction.
236 // Create the second MOVK instruction.
237 Insn.push_back({ AArch64::MOVKXi, getChunk(UImm, SecondMovkIdx),
238 AArch64_AM::getShifterImm(AArch64_AM::LSL,
239 SecondMovkIdx * 16) });
244 /// \brief Expand a MOVi32imm or MOVi64imm pseudo instruction to a
245 /// MOVZ or MOVN of width BitSize followed by up to 3 MOVK instructions.
246 static inline void expandMOVImmSimple(uint64_t Imm, unsigned BitSize,
247 unsigned OneChunks, unsigned ZeroChunks,
248 SmallVectorImpl<ImmInsnModel> &Insn) {
249 const unsigned Mask = 0xFFFF;
251 // Use a MOVZ or MOVN instruction to set the high bits, followed by one or
252 // more MOVK instructions to insert additional 16-bit portions into the
256 // Use MOVN to materialize the high bits if we have more all one chunks
257 // than all zero chunks.
258 if (OneChunks > ZeroChunks) {
265 Imm &= (1LL << 32) - 1;
266 FirstOpc = (isNeg ? AArch64::MOVNWi : AArch64::MOVZWi);
268 FirstOpc = (isNeg ? AArch64::MOVNXi : AArch64::MOVZXi);
270 unsigned Shift = 0; // LSL amount for high bits with MOVZ/MOVN
271 unsigned LastShift = 0; // LSL amount for last MOVK
273 unsigned LZ = countLeadingZeros(Imm);
274 unsigned TZ = countTrailingZeros(Imm);
275 Shift = (TZ / 16) * 16;
276 LastShift = ((63 - LZ) / 16) * 16;
278 unsigned Imm16 = (Imm >> Shift) & Mask;
280 Insn.push_back({ FirstOpc, Imm16,
281 AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
283 if (Shift == LastShift)
286 // If a MOVN was used for the high bits of a negative value, flip the rest
287 // of the bits back for use with MOVK.
291 unsigned Opc = (BitSize == 32 ? AArch64::MOVKWi : AArch64::MOVKXi);
292 while (Shift < LastShift) {
294 Imm16 = (Imm >> Shift) & Mask;
295 if (Imm16 == (isNeg ? Mask : 0))
296 continue; // This 16-bit portion is already set correctly.
298 Insn.push_back({ Opc, Imm16,
299 AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
303 /// Expand a MOVi32imm or MOVi64imm pseudo instruction to one or more
304 /// real move-immediate instructions to synthesize the immediate.
305 void expandMOVImm(uint64_t Imm, unsigned BitSize,
306 SmallVectorImpl<ImmInsnModel> &Insn) {
307 const unsigned Mask = 0xFFFF;
309 // Scan the immediate and count the number of 16-bit chunks which are either
310 // all ones or all zeros.
311 unsigned OneChunks = 0;
312 unsigned ZeroChunks = 0;
313 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {
314 const unsigned Chunk = (Imm >> Shift) & Mask;
321 // Prefer MOVZ/MOVN over ORR because of the rules for the "mov" alias.
322 if ((BitSize / 16) - OneChunks <= 1 || (BitSize / 16) - ZeroChunks <= 1) {
323 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
328 uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize);
330 if (AArch64_AM::processLogicalImmediate(UImm, BitSize, Encoding)) {
331 unsigned Opc = (BitSize == 32 ? AArch64::ORRWri : AArch64::ORRXri);
332 Insn.push_back({ Opc, 0, Encoding });
336 // One to up three instruction sequences.
338 // Prefer MOVZ/MOVN followed by MOVK; it's more readable, and possibly the
339 // fastest sequence with fast literal generation.
340 if (OneChunks >= (BitSize / 16) - 2 || ZeroChunks >= (BitSize / 16) - 2) {
341 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
345 assert(BitSize == 64 && "All 32-bit immediates can be expanded with a"
348 // Try other two-instruction sequences.
350 // 64-bit ORR followed by MOVK.
351 // We try to construct the ORR immediate in three different ways: either we
352 // zero out the chunk which will be replaced, we fill the chunk which will
353 // be replaced with ones, or we take the bit pattern from the other half of
354 // the 64-bit immediate. This is comprehensive because of the way ORR
355 // immediates are constructed.
356 for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {
357 uint64_t ShiftedMask = (0xFFFFULL << Shift);
358 uint64_t ZeroChunk = UImm & ~ShiftedMask;
359 uint64_t OneChunk = UImm | ShiftedMask;
360 uint64_t RotatedImm = (UImm << 32) | (UImm >> 32);
361 uint64_t ReplicateChunk = ZeroChunk | (RotatedImm & ShiftedMask);
362 if (AArch64_AM::processLogicalImmediate(ZeroChunk, BitSize, Encoding) ||
363 AArch64_AM::processLogicalImmediate(OneChunk, BitSize, Encoding) ||
364 AArch64_AM::processLogicalImmediate(ReplicateChunk, BitSize,
366 // Create the ORR-immediate instruction.
367 Insn.push_back({ AArch64::ORRXri, 0, Encoding });
369 // Create the MOVK instruction.
370 const unsigned Imm16 = getChunk(UImm, Shift / 16);
371 Insn.push_back({ AArch64::MOVKXi, Imm16,
372 AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) });
377 // FIXME: Add more two-instruction sequences.
379 // Three instruction sequences.
381 // Prefer MOVZ/MOVN followed by two MOVK; it's more readable, and possibly
382 // the fastest sequence with fast literal generation. (If neither MOVK is
383 // part of a fast literal generation pair, it could be slower than the
384 // four-instruction sequence, but we won't worry about that for now.)
385 if (OneChunks || ZeroChunks) {
386 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
390 // Check for identical 16-bit chunks within the constant and if so materialize
391 // them with a single ORR instruction. The remaining one or two 16-bit chunks
392 // will be materialized with MOVK instructions.
393 if (BitSize == 64 && tryToreplicateChunks(UImm, Insn))
396 // Check whether the constant contains a sequence of contiguous ones, which
397 // might be interrupted by one or two chunks. If so, materialize the sequence
398 // of contiguous ones with an ORR instruction. Materialize the chunks which
399 // are either interrupting the sequence or outside of the sequence with a
401 if (BitSize == 64 && trySequenceOfOnes(UImm, Insn))
404 // We found no possible two or three instruction sequence; use the general
405 // four-instruction sequence.
406 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn);
409 } // end namespace AArch64_AM
411 } // end namespace llvm