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 "AArch64.h" 14 #include "AArch64ExpandImm.h" 15 #include "MCTargetDesc/AArch64AddressingModes.h" 16 17 namespace llvm { 18 19 namespace AArch64_IMM { 20 21 /// Helper function which extracts the specified 16-bit chunk from a 22 /// 64-bit value. 23 static 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. 31 static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding) { 32 Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk; 33 34 return AArch64_AM::processLogicalImmediate(Chunk, 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. 44 static 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(UImm, Idx)]; 53 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; 59 60 uint64_t Encoding = 0; 61 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)) 65 continue; 66 67 const bool CountThree = Count == 3; 68 69 Insn.push_back({ AArch64::ORRXri, 0, Encoding }); 70 71 unsigned ShiftAmt = 0; 72 uint64_t Imm16 = 0; 73 // Find the first chunk not materialized with the ORR instruction. 74 for (; ShiftAmt < 64; ShiftAmt += 16) { 75 Imm16 = (UImm >> ShiftAmt) & 0xFFFF; 76 77 if (Imm16 != ChunkVal) 78 break; 79 } 80 81 // Create the first MOVK instruction. 82 Insn.push_back({ AArch64::MOVKXi, Imm16, 83 AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) }); 84 85 // In case we have three instances the whole constant is now materialized 86 // and we can exit. 87 if (CountThree) 88 return true; 89 90 // Find the remaining chunk which needs to be materialized. 91 for (ShiftAmt += 16; ShiftAmt < 64; ShiftAmt += 16) { 92 Imm16 = (UImm >> ShiftAmt) & 0xFFFF; 93 94 if (Imm16 != ChunkVal) 95 break; 96 } 97 Insn.push_back({ AArch64::MOVKXi, Imm16, 98 AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt) }); 99 return true; 100 } 101 102 return false; 103 } 104 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 107 /// towards the MSB. 108 static bool isStartChunk(uint64_t Chunk) { 109 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max()) 110 return false; 111 112 return isMask_64(~Chunk); 113 } 114 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 117 /// towards the MSB. 118 static bool isEndChunk(uint64_t Chunk) { 119 if (Chunk == 0 || Chunk == std::numeric_limits<uint64_t>::max()) 120 return false; 121 122 return isMask_64(Chunk); 123 } 124 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; 128 129 if (Clear) 130 // Clear chunk in the immediate. 131 Imm &= ~(Mask << (Idx * 16)); 132 else 133 // Set all bits in the immediate for the particular chunk. 134 Imm |= Mask << (Idx * 16); 135 136 return Imm; 137 } 138 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. 144 /// 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|. 149 /// 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; 156 157 int StartIdx = NotSet; 158 int EndIdx = 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; 164 165 if (isStartChunk(Chunk)) 166 StartIdx = Idx; 167 else if (isEndChunk(Chunk)) 168 EndIdx = Idx; 169 } 170 171 // Early exit in case we can't find a start/end chunk. 172 if (StartIdx == NotSet || EndIdx == NotSet) 173 return false; 174 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; 179 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); 186 } 187 188 uint64_t OrrImm = UImm; 189 int FirstMovkIdx = NotSet; 190 int SecondMovkIdx = NotSet; 191 192 // Find out which chunks we need to patch up to obtain a contiguous sequence 193 // of ones. 194 for (int Idx = 0; Idx < 4; ++Idx) { 195 const uint64_t Chunk = getChunk(UImm, Idx); 196 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); 201 202 // Remember the index we need to patch. 203 if (FirstMovkIdx == NotSet) 204 FirstMovkIdx = Idx; 205 else 206 SecondMovkIdx = Idx; 207 208 // Check whether we are looking a chunk which is part of the contiguous 209 // sequence of ones. 210 } else if (Idx > StartIdx && Idx < EndIdx && Chunk != Inside) { 211 OrrImm = updateImm(OrrImm, Idx, Inside != Mask); 212 213 // Remember the index we need to patch. 214 if (FirstMovkIdx == NotSet) 215 FirstMovkIdx = Idx; 216 else 217 SecondMovkIdx = Idx; 218 } 219 } 220 assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!"); 221 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 }); 226 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) }); 231 232 // Early exit in case we only need to emit a single MOVK instruction. 233 if (SingleMovk) 234 return true; 235 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) }); 240 241 return true; 242 } 243 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; 250 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 253 // lower bits. 254 bool isNeg = false; 255 256 // Use MOVN to materialize the high bits if we have more all one chunks 257 // than all zero chunks. 258 if (OneChunks > ZeroChunks) { 259 isNeg = true; 260 Imm = ~Imm; 261 } 262 263 unsigned FirstOpc; 264 if (BitSize == 32) { 265 Imm &= (1LL << 32) - 1; 266 FirstOpc = (isNeg ? AArch64::MOVNWi : AArch64::MOVZWi); 267 } else { 268 FirstOpc = (isNeg ? AArch64::MOVNXi : AArch64::MOVZXi); 269 } 270 unsigned Shift = 0; // LSL amount for high bits with MOVZ/MOVN 271 unsigned LastShift = 0; // LSL amount for last MOVK 272 if (Imm != 0) { 273 unsigned LZ = countLeadingZeros(Imm); 274 unsigned TZ = countTrailingZeros(Imm); 275 Shift = (TZ / 16) * 16; 276 LastShift = ((63 - LZ) / 16) * 16; 277 } 278 unsigned Imm16 = (Imm >> Shift) & Mask; 279 280 Insn.push_back({ FirstOpc, Imm16, 281 AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) }); 282 283 if (Shift == LastShift) 284 return; 285 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. 288 if (isNeg) 289 Imm = ~Imm; 290 291 unsigned Opc = (BitSize == 32 ? AArch64::MOVKWi : AArch64::MOVKXi); 292 while (Shift < LastShift) { 293 Shift += 16; 294 Imm16 = (Imm >> Shift) & Mask; 295 if (Imm16 == (isNeg ? Mask : 0)) 296 continue; // This 16-bit portion is already set correctly. 297 298 Insn.push_back({ Opc, Imm16, 299 AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift) }); 300 } 301 } 302 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; 308 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; 315 if (Chunk == Mask) 316 OneChunks++; 317 else if (Chunk == 0) 318 ZeroChunks++; 319 } 320 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); 324 return; 325 } 326 327 // Try a single ORR. 328 uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize); 329 uint64_t Encoding; 330 if (AArch64_AM::processLogicalImmediate(UImm, BitSize, Encoding)) { 331 unsigned Opc = (BitSize == 32 ? AArch64::ORRWri : AArch64::ORRXri); 332 Insn.push_back({ Opc, 0, Encoding }); 333 return; 334 } 335 336 // One to up three instruction sequences. 337 // 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); 342 return; 343 } 344 345 assert(BitSize == 64 && "All 32-bit immediates can be expanded with a" 346 "MOVZ/MOVK pair"); 347 348 // Try other two-instruction sequences. 349 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, 365 Encoding)) { 366 // Create the ORR-immediate instruction. 367 Insn.push_back({ AArch64::ORRXri, 0, Encoding }); 368 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) }); 373 return; 374 } 375 } 376 377 // FIXME: Add more two-instruction sequences. 378 379 // Three instruction sequences. 380 // 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); 387 return; 388 } 389 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)) 394 return; 395 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 400 // MOVK instruction. 401 if (BitSize == 64 && trySequenceOfOnes(UImm, Insn)) 402 return; 403 404 // We found no possible two or three instruction sequence; use the general 405 // four-instruction sequence. 406 expandMOVImmSimple(Imm, BitSize, OneChunks, ZeroChunks, Insn); 407 } 408 409 } // end namespace AArch64_AM 410 411 } // end namespace llvm 412