lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

   1 //==-- AArch64ExpandPseudoInsts.cpp - Expand pseudo instructions --*- C++ -*-=//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains a pass that expands pseudo instructions into target
  11 // instructions to allow proper scheduling and other late optimizations.  This
  12 // pass should be run after register allocation but before the post-regalloc
  13 // scheduling pass.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "MCTargetDesc/AArch64AddressingModes.h"
  18 #include "AArch64InstrInfo.h"
  19 #include "AArch64Subtarget.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstrBuilder.h"
  22 #include "llvm/Support/MathExtras.h"
  23 using namespace llvm;
  24
  25 namespace llvm {
  26 void initializeAArch64ExpandPseudoPass(PassRegistry &);
  27 }
  28
  29 #define AARCH64_EXPAND_PSEUDO_NAME "AArch64 pseudo instruction expansion pass"
  30
  31 namespace {
  32 class AArch64ExpandPseudo : public MachineFunctionPass {
  33 public:
  34   static char ID;
  35   AArch64ExpandPseudo() : MachineFunctionPass(ID) {
  36     initializeAArch64ExpandPseudoPass(*PassRegistry::getPassRegistry());
  37   }
  38
  39   const AArch64InstrInfo *TII;
  40
  41   bool runOnMachineFunction(MachineFunction &Fn) override;
  42
  43   const char *getPassName() const override {
  44     return AARCH64_EXPAND_PSEUDO_NAME;
  45   }
  46
  47 private:
  48   bool expandMBB(MachineBasicBlock &MBB);
  49   bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI);
  50   bool expandMOVImm(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
  51                     unsigned BitSize);
  52 };
  53 char AArch64ExpandPseudo::ID = 0;
  54 }
  55
  56 INITIALIZE_PASS(AArch64ExpandPseudo, "aarch64-expand-pseudo",
  57                 AARCH64_EXPAND_PSEUDO_NAME, false, false)
  58
  59 /// \brief Transfer implicit operands on the pseudo instruction to the
  60 /// instructions created from the expansion.
  61 static void transferImpOps(MachineInstr &OldMI, MachineInstrBuilder &UseMI,
  62                            MachineInstrBuilder &DefMI) {
  63   const MCInstrDesc &Desc = OldMI.getDesc();
  64   for (unsigned i = Desc.getNumOperands(), e = OldMI.getNumOperands(); i != e;
  65        ++i) {
  66     const MachineOperand &MO = OldMI.getOperand(i);
  67     assert(MO.isReg() && MO.getReg());
  68     if (MO.isUse())
  69       UseMI.addOperand(MO);
  70     else
  71       DefMI.addOperand(MO);
  72   }
  73 }
  74
  75 /// \brief Helper function which extracts the specified 16-bit chunk from a
  76 /// 64-bit value.
  77 static uint64_t getChunk(uint64_t Imm, unsigned ChunkIdx) {
  78   assert(ChunkIdx < 4 && "Out of range chunk index specified!");
  79
  80   return (Imm >> (ChunkIdx * 16)) & 0xFFFF;
  81 }
  82
  83 /// \brief Helper function which replicates a 16-bit chunk within a 64-bit
  84 /// value. Indices correspond to element numbers in a v4i16.
  85 static uint64_t replicateChunk(uint64_t Imm, unsigned FromIdx, unsigned ToIdx) {
  86   assert((FromIdx < 4) && (ToIdx < 4) && "Out of range chunk index specified!");
  87   const unsigned ShiftAmt = ToIdx * 16;
  88
  89   // Replicate the source chunk to the destination position.
  90   const uint64_t Chunk = getChunk(Imm, FromIdx) << ShiftAmt;
  91   // Clear the destination chunk.
  92   Imm &= ~(0xFFFFLL << ShiftAmt);
  93   // Insert the replicated chunk.
  94   return Imm | Chunk;
  95 }
  96
  97 /// \brief Helper function which tries to materialize a 64-bit value with an
  98 /// ORR + MOVK instruction sequence.
  99 static bool tryOrrMovk(uint64_t UImm, uint64_t OrrImm, MachineInstr &MI,
 100                        MachineBasicBlock &MBB,
 101                        MachineBasicBlock::iterator &MBBI,
 102                        const AArch64InstrInfo *TII, unsigned ChunkIdx) {
 103   assert(ChunkIdx < 4 && "Out of range chunk index specified!");
 104   const unsigned ShiftAmt = ChunkIdx * 16;
 105
 106   uint64_t Encoding;
 107   if (AArch64_AM::processLogicalImmediate(OrrImm, 64, Encoding)) {
 108     // Create the ORR-immediate instruction.
 109     MachineInstrBuilder MIB =
 110         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ORRXri))
 111             .addOperand(MI.getOperand(0))
 112             .addReg(AArch64::XZR)
 113             .addImm(Encoding);
 114
 115     // Create the MOVK instruction.
 116     const unsigned Imm16 = getChunk(UImm, ChunkIdx);
 117     const unsigned DstReg = MI.getOperand(0).getReg();
 118     const bool DstIsDead = MI.getOperand(0).isDead();
 119     MachineInstrBuilder MIB1 =
 120         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::MOVKXi))
 121             .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
 122             .addReg(DstReg)
 123             .addImm(Imm16)
 124             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt));
 125
 126     transferImpOps(MI, MIB, MIB1);
 127     MI.eraseFromParent();
 128     return true;
 129   }
 130
 131   return false;
 132 }
 133
 134 /// \brief Check whether the given 16-bit chunk replicated to full 64-bit width
 135 /// can be materialized with an ORR instruction.
 136 static bool canUseOrr(uint64_t Chunk, uint64_t &Encoding) {
 137   Chunk = (Chunk << 48) | (Chunk << 32) | (Chunk << 16) | Chunk;
 138
 139   return AArch64_AM::processLogicalImmediate(Chunk, 64, Encoding);
 140 }
 141
 142 /// \brief Check for identical 16-bit chunks within the constant and if so
 143 /// materialize them with a single ORR instruction. The remaining one or two
 144 /// 16-bit chunks will be materialized with MOVK instructions.
 145 ///
 146 /// This allows us to materialize constants like |A|B|A|A| or |A|B|C|A| (order
 147 /// of the chunks doesn't matter), assuming |A|A|A|A| can be materialized with
 148 /// an ORR instruction.
 149 ///
 150 static bool tryToreplicateChunks(uint64_t UImm, MachineInstr &MI,
 151                                  MachineBasicBlock &MBB,
 152                                  MachineBasicBlock::iterator &MBBI,
 153                                  const AArch64InstrInfo *TII) {
 154   typedef DenseMap<uint64_t, unsigned> CountMap;
 155   CountMap Counts;
 156
 157   // Scan the constant and count how often every chunk occurs.
 158   for (unsigned Idx = 0; Idx < 4; ++Idx)
 159     ++Counts[getChunk(UImm, Idx)];
 160
 161   // Traverse the chunks to find one which occurs more than once.
 162   for (CountMap::const_iterator Chunk = Counts.begin(), End = Counts.end();
 163        Chunk != End; ++Chunk) {
 164     const uint64_t ChunkVal = Chunk->first;
 165     const unsigned Count = Chunk->second;
 166
 167     uint64_t Encoding = 0;
 168
 169     // We are looking for chunks which have two or three instances and can be
 170     // materialized with an ORR instruction.
 171     if ((Count != 2 && Count != 3) || !canUseOrr(ChunkVal, Encoding))
 172       continue;
 173
 174     const bool CountThree = Count == 3;
 175     // Create the ORR-immediate instruction.
 176     MachineInstrBuilder MIB =
 177         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ORRXri))
 178             .addOperand(MI.getOperand(0))
 179             .addReg(AArch64::XZR)
 180             .addImm(Encoding);
 181
 182     const unsigned DstReg = MI.getOperand(0).getReg();
 183     const bool DstIsDead = MI.getOperand(0).isDead();
 184
 185     unsigned ShiftAmt = 0;
 186     uint64_t Imm16 = 0;
 187     // Find the first chunk not materialized with the ORR instruction.
 188     for (; ShiftAmt < 64; ShiftAmt += 16) {
 189       Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
 190
 191       if (Imm16 != ChunkVal)
 192         break;
 193     }
 194
 195     // Create the first MOVK instruction.
 196     MachineInstrBuilder MIB1 =
 197         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::MOVKXi))
 198             .addReg(DstReg,
 199                     RegState::Define | getDeadRegState(DstIsDead && CountThree))
 200             .addReg(DstReg)
 201             .addImm(Imm16)
 202             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt));
 203
 204     // In case we have three instances the whole constant is now materialized
 205     // and we can exit.
 206     if (CountThree) {
 207       transferImpOps(MI, MIB, MIB1);
 208       MI.eraseFromParent();
 209       return true;
 210     }
 211
 212     // Find the remaining chunk which needs to be materialized.
 213     for (ShiftAmt += 16; ShiftAmt < 64; ShiftAmt += 16) {
 214       Imm16 = (UImm >> ShiftAmt) & 0xFFFF;
 215
 216       if (Imm16 != ChunkVal)
 217         break;
 218     }
 219
 220     // Create the second MOVK instruction.
 221     MachineInstrBuilder MIB2 =
 222         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::MOVKXi))
 223             .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
 224             .addReg(DstReg)
 225             .addImm(Imm16)
 226             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, ShiftAmt));
 227
 228     transferImpOps(MI, MIB, MIB2);
 229     MI.eraseFromParent();
 230     return true;
 231   }
 232
 233   return false;
 234 }
 235
 236 /// \brief Check whether this chunk matches the pattern '1...0...'. This pattern
 237 /// starts a contiguous sequence of ones if we look at the bits from the LSB
 238 /// towards the MSB.
 239 static bool isStartChunk(uint64_t Chunk) {
 240   if (Chunk == 0 || Chunk == UINT64_MAX)
 241     return false;
 242
 243   return isMask_64(~Chunk);
 244 }
 245
 246 /// \brief Check whether this chunk matches the pattern '0...1...' This pattern
 247 /// ends a contiguous sequence of ones if we look at the bits from the LSB
 248 /// towards the MSB.
 249 static bool isEndChunk(uint64_t Chunk) {
 250   if (Chunk == 0 || Chunk == UINT64_MAX)
 251     return false;
 252
 253   return isMask_64(Chunk);
 254 }
 255
 256 /// \brief Clear or set all bits in the chunk at the given index.
 257 static uint64_t updateImm(uint64_t Imm, unsigned Idx, bool Clear) {
 258   const uint64_t Mask = 0xFFFF;
 259
 260   if (Clear)
 261     // Clear chunk in the immediate.
 262     Imm &= ~(Mask << (Idx * 16));
 263   else
 264     // Set all bits in the immediate for the particular chunk.
 265     Imm |= Mask << (Idx * 16);
 266
 267   return Imm;
 268 }
 269
 270 /// \brief Check whether the constant contains a sequence of contiguous ones,
 271 /// which might be interrupted by one or two chunks. If so, materialize the
 272 /// sequence of contiguous ones with an ORR instruction.
 273 /// Materialize the chunks which are either interrupting the sequence or outside
 274 /// of the sequence with a MOVK instruction.
 275 ///
 276 /// Assuming S is a chunk which starts the sequence (1...0...), E is a chunk
 277 /// which ends the sequence (0...1...). Then we are looking for constants which
 278 /// contain at least one S and E chunk.
 279 /// E.g. |E|A|B|S|, |A|E|B|S| or |A|B|E|S|.
 280 ///
 281 /// We are also looking for constants like |S|A|B|E| where the contiguous
 282 /// sequence of ones wraps around the MSB into the LSB.
 283 ///
 284 static bool trySequenceOfOnes(uint64_t UImm, MachineInstr &MI,
 285                               MachineBasicBlock &MBB,
 286                               MachineBasicBlock::iterator &MBBI,
 287                               const AArch64InstrInfo *TII) {
 288   const int NotSet = -1;
 289   const uint64_t Mask = 0xFFFF;
 290
 291   int StartIdx = NotSet;
 292   int EndIdx = NotSet;
 293   // Try to find the chunks which start/end a contiguous sequence of ones.
 294   for (int Idx = 0; Idx < 4; ++Idx) {
 295     int64_t Chunk = getChunk(UImm, Idx);
 296     // Sign extend the 16-bit chunk to 64-bit.
 297     Chunk = (Chunk << 48) >> 48;
 298
 299     if (isStartChunk(Chunk))
 300       StartIdx = Idx;
 301     else if (isEndChunk(Chunk))
 302       EndIdx = Idx;
 303   }
 304
 305   // Early exit in case we can't find a start/end chunk.
 306   if (StartIdx == NotSet || EndIdx == NotSet)
 307     return false;
 308
 309   // Outside of the contiguous sequence of ones everything needs to be zero.
 310   uint64_t Outside = 0;
 311   // Chunks between the start and end chunk need to have all their bits set.
 312   uint64_t Inside = Mask;
 313
 314   // If our contiguous sequence of ones wraps around from the MSB into the LSB,
 315   // just swap indices and pretend we are materializing a contiguous sequence
 316   // of zeros surrounded by a contiguous sequence of ones.
 317   if (StartIdx > EndIdx) {
 318     std::swap(StartIdx, EndIdx);
 319     std::swap(Outside, Inside);
 320   }
 321
 322   uint64_t OrrImm = UImm;
 323   int FirstMovkIdx = NotSet;
 324   int SecondMovkIdx = NotSet;
 325
 326   // Find out which chunks we need to patch up to obtain a contiguous sequence
 327   // of ones.
 328   for (int Idx = 0; Idx < 4; ++Idx) {
 329     const uint64_t Chunk = getChunk(UImm, Idx);
 330
 331     // Check whether we are looking at a chunk which is not part of the
 332     // contiguous sequence of ones.
 333     if ((Idx < StartIdx || EndIdx < Idx) && Chunk != Outside) {
 334       OrrImm = updateImm(OrrImm, Idx, Outside == 0);
 335
 336       // Remember the index we need to patch.
 337       if (FirstMovkIdx == NotSet)
 338         FirstMovkIdx = Idx;
 339       else
 340         SecondMovkIdx = Idx;
 341
 342       // Check whether we are looking a chunk which is part of the contiguous
 343       // sequence of ones.
 344     } else if (Idx > StartIdx && Idx < EndIdx && Chunk != Inside) {
 345       OrrImm = updateImm(OrrImm, Idx, Inside != Mask);
 346
 347       // Remember the index we need to patch.
 348       if (FirstMovkIdx == NotSet)
 349         FirstMovkIdx = Idx;
 350       else
 351         SecondMovkIdx = Idx;
 352     }
 353   }
 354   assert(FirstMovkIdx != NotSet && "Constant materializable with single ORR!");
 355
 356   // Create the ORR-immediate instruction.
 357   uint64_t Encoding = 0;
 358   AArch64_AM::processLogicalImmediate(OrrImm, 64, Encoding);
 359   MachineInstrBuilder MIB =
 360       BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ORRXri))
 361           .addOperand(MI.getOperand(0))
 362           .addReg(AArch64::XZR)
 363           .addImm(Encoding);
 364
 365   const unsigned DstReg = MI.getOperand(0).getReg();
 366   const bool DstIsDead = MI.getOperand(0).isDead();
 367
 368   const bool SingleMovk = SecondMovkIdx == NotSet;
 369   // Create the first MOVK instruction.
 370   MachineInstrBuilder MIB1 =
 371       BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::MOVKXi))
 372           .addReg(DstReg,
 373                   RegState::Define | getDeadRegState(DstIsDead && SingleMovk))
 374           .addReg(DstReg)
 375           .addImm(getChunk(UImm, FirstMovkIdx))
 376           .addImm(
 377               AArch64_AM::getShifterImm(AArch64_AM::LSL, FirstMovkIdx * 16));
 378
 379   // Early exit in case we only need to emit a single MOVK instruction.
 380   if (SingleMovk) {
 381     transferImpOps(MI, MIB, MIB1);
 382     MI.eraseFromParent();
 383     return true;
 384   }
 385
 386   // Create the second MOVK instruction.
 387   MachineInstrBuilder MIB2 =
 388       BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::MOVKXi))
 389           .addReg(DstReg, RegState::Define | getDeadRegState(DstIsDead))
 390           .addReg(DstReg)
 391           .addImm(getChunk(UImm, SecondMovkIdx))
 392           .addImm(
 393               AArch64_AM::getShifterImm(AArch64_AM::LSL, SecondMovkIdx * 16));
 394
 395   transferImpOps(MI, MIB, MIB2);
 396   MI.eraseFromParent();
 397   return true;
 398 }
 399
 400 /// \brief Expand a MOVi32imm or MOVi64imm pseudo instruction to one or more
 401 /// real move-immediate instructions to synthesize the immediate.
 402 bool AArch64ExpandPseudo::expandMOVImm(MachineBasicBlock &MBB,
 403                                        MachineBasicBlock::iterator MBBI,
 404                                        unsigned BitSize) {
 405   MachineInstr &MI = *MBBI;
 406   uint64_t Imm = MI.getOperand(1).getImm();
 407   const unsigned Mask = 0xFFFF;
 408
 409   // Try a MOVI instruction (aka ORR-immediate with the zero register).
 410   uint64_t UImm = Imm << (64 - BitSize) >> (64 - BitSize);
 411   uint64_t Encoding;
 412   if (AArch64_AM::processLogicalImmediate(UImm, BitSize, Encoding)) {
 413     unsigned Opc = (BitSize == 32 ? AArch64::ORRWri : AArch64::ORRXri);
 414     MachineInstrBuilder MIB =
 415         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(Opc))
 416             .addOperand(MI.getOperand(0))
 417             .addReg(BitSize == 32 ? AArch64::WZR : AArch64::XZR)
 418             .addImm(Encoding);
 419     transferImpOps(MI, MIB, MIB);
 420     MI.eraseFromParent();
 421     return true;
 422   }
 423
 424   // Scan the immediate and count the number of 16-bit chunks which are either
 425   // all ones or all zeros.
 426   unsigned OneChunks = 0;
 427   unsigned ZeroChunks = 0;
 428   for (unsigned Shift = 0; Shift < BitSize; Shift += 16) {
 429     const unsigned Chunk = (Imm >> Shift) & Mask;
 430     if (Chunk == Mask)
 431       OneChunks++;
 432     else if (Chunk == 0)
 433       ZeroChunks++;
 434   }
 435
 436   // Since we can't materialize the constant with a single ORR instruction,
 437   // let's see whether we can materialize 3/4 of the constant with an ORR
 438   // instruction and use an additional MOVK instruction to materialize the
 439   // remaining 1/4.
 440   //
 441   // We are looking for constants with a pattern like: |A|X|B|X| or |X|A|X|B|.
 442   //
 443   // E.g. assuming |A|X|A|X| is a pattern which can be materialized with ORR,
 444   // we would create the following instruction sequence:
 445   //
 446   // ORR x0, xzr, |A|X|A|X|
 447   // MOVK x0, |B|, LSL #16
 448   //
 449   // Only look at 64-bit constants which can't be materialized with a single
 450   // instruction e.g. which have less than either three all zero or all one
 451   // chunks.
 452   //
 453   // Ignore 32-bit constants here, they always can be materialized with a
 454   // MOVZ/MOVN + MOVK pair. Since the 32-bit constant can't be materialized
 455   // with a single ORR, the best sequence we can achieve is a ORR + MOVK pair.
 456   // Thus we fall back to the default code below which in the best case creates
 457   // a single MOVZ/MOVN instruction (in case one chunk is all zero or all one).
 458   //
 459   if (BitSize == 64 && OneChunks < 3 && ZeroChunks < 3) {
 460     // If we interpret the 64-bit constant as a v4i16, are elements 0 and 2
 461     // identical?
 462     if (getChunk(UImm, 0) == getChunk(UImm, 2)) {
 463       // See if we can come up with a constant which can be materialized with
 464       // ORR-immediate by replicating element 3 into element 1.
 465       uint64_t OrrImm = replicateChunk(UImm, 3, 1);
 466       if (tryOrrMovk(UImm, OrrImm, MI, MBB, MBBI, TII, 1))
 467         return true;
 468
 469       // See if we can come up with a constant which can be materialized with
 470       // ORR-immediate by replicating element 1 into element 3.
 471       OrrImm = replicateChunk(UImm, 1, 3);
 472       if (tryOrrMovk(UImm, OrrImm, MI, MBB, MBBI, TII, 3))
 473         return true;
 474
 475       // If we interpret the 64-bit constant as a v4i16, are elements 1 and 3
 476       // identical?
 477     } else if (getChunk(UImm, 1) == getChunk(UImm, 3)) {
 478       // See if we can come up with a constant which can be materialized with
 479       // ORR-immediate by replicating element 2 into element 0.
 480       uint64_t OrrImm = replicateChunk(UImm, 2, 0);
 481       if (tryOrrMovk(UImm, OrrImm, MI, MBB, MBBI, TII, 0))
 482         return true;
 483
 484       // See if we can come up with a constant which can be materialized with
 485       // ORR-immediate by replicating element 1 into element 3.
 486       OrrImm = replicateChunk(UImm, 0, 2);
 487       if (tryOrrMovk(UImm, OrrImm, MI, MBB, MBBI, TII, 2))
 488         return true;
 489     }
 490   }
 491
 492   // Check for identical 16-bit chunks within the constant and if so materialize
 493   // them with a single ORR instruction. The remaining one or two 16-bit chunks
 494   // will be materialized with MOVK instructions.
 495   if (BitSize == 64 && tryToreplicateChunks(UImm, MI, MBB, MBBI, TII))
 496     return true;
 497
 498   // Check whether the constant contains a sequence of contiguous ones, which
 499   // might be interrupted by one or two chunks. If so, materialize the sequence
 500   // of contiguous ones with an ORR instruction. Materialize the chunks which
 501   // are either interrupting the sequence or outside of the sequence with a
 502   // MOVK instruction.
 503   if (BitSize == 64 && trySequenceOfOnes(UImm, MI, MBB, MBBI, TII))
 504     return true;
 505
 506   // Use a MOVZ or MOVN instruction to set the high bits, followed by one or
 507   // more MOVK instructions to insert additional 16-bit portions into the
 508   // lower bits.
 509   bool isNeg = false;
 510
 511   // Use MOVN to materialize the high bits if we have more all one chunks
 512   // than all zero chunks.
 513   if (OneChunks > ZeroChunks) {
 514     isNeg = true;
 515     Imm = ~Imm;
 516   }
 517
 518   unsigned FirstOpc;
 519   if (BitSize == 32) {
 520     Imm &= (1LL << 32) - 1;
 521     FirstOpc = (isNeg ? AArch64::MOVNWi : AArch64::MOVZWi);
 522   } else {
 523     FirstOpc = (isNeg ? AArch64::MOVNXi : AArch64::MOVZXi);
 524   }
 525   unsigned Shift = 0;     // LSL amount for high bits with MOVZ/MOVN
 526   unsigned LastShift = 0; // LSL amount for last MOVK
 527   if (Imm != 0) {
 528     unsigned LZ = countLeadingZeros(Imm);
 529     unsigned TZ = countTrailingZeros(Imm);
 530     Shift = ((63 - LZ) / 16) * 16;
 531     LastShift = (TZ / 16) * 16;
 532   }
 533   unsigned Imm16 = (Imm >> Shift) & Mask;
 534   unsigned DstReg = MI.getOperand(0).getReg();
 535   bool DstIsDead = MI.getOperand(0).isDead();
 536   MachineInstrBuilder MIB1 =
 537       BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(FirstOpc))
 538           .addReg(DstReg, RegState::Define |
 539                               getDeadRegState(DstIsDead && Shift == LastShift))
 540           .addImm(Imm16)
 541           .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift));
 542
 543   // If a MOVN was used for the high bits of a negative value, flip the rest
 544   // of the bits back for use with MOVK.
 545   if (isNeg)
 546     Imm = ~Imm;
 547
 548   if (Shift == LastShift) {
 549     transferImpOps(MI, MIB1, MIB1);
 550     MI.eraseFromParent();
 551     return true;
 552   }
 553
 554   MachineInstrBuilder MIB2;
 555   unsigned Opc = (BitSize == 32 ? AArch64::MOVKWi : AArch64::MOVKXi);
 556   while (Shift != LastShift) {
 557     Shift -= 16;
 558     Imm16 = (Imm >> Shift) & Mask;
 559     if (Imm16 == (isNeg ? Mask : 0))
 560       continue; // This 16-bit portion is already set correctly.
 561     MIB2 = BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(Opc))
 562                .addReg(DstReg,
 563                        RegState::Define |
 564                            getDeadRegState(DstIsDead && Shift == LastShift))
 565                .addReg(DstReg)
 566                .addImm(Imm16)
 567                .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift));
 568   }
 569
 570   transferImpOps(MI, MIB1, MIB2);
 571   MI.eraseFromParent();
 572   return true;
 573 }
 574
 575 /// \brief If MBBI references a pseudo instruction that should be expanded here,
 576 /// do the expansion and return true.  Otherwise return false.
 577 bool AArch64ExpandPseudo::expandMI(MachineBasicBlock &MBB,
 578                                  MachineBasicBlock::iterator MBBI) {
 579   MachineInstr &MI = *MBBI;
 580   unsigned Opcode = MI.getOpcode();
 581   switch (Opcode) {
 582   default:
 583     break;
 584
 585   case AArch64::ADDWrr:
 586   case AArch64::SUBWrr:
 587   case AArch64::ADDXrr:
 588   case AArch64::SUBXrr:
 589   case AArch64::ADDSWrr:
 590   case AArch64::SUBSWrr:
 591   case AArch64::ADDSXrr:
 592   case AArch64::SUBSXrr:
 593   case AArch64::ANDWrr:
 594   case AArch64::ANDXrr:
 595   case AArch64::BICWrr:
 596   case AArch64::BICXrr:
 597   case AArch64::ANDSWrr:
 598   case AArch64::ANDSXrr:
 599   case AArch64::BICSWrr:
 600   case AArch64::BICSXrr:
 601   case AArch64::EONWrr:
 602   case AArch64::EONXrr:
 603   case AArch64::EORWrr:
 604   case AArch64::EORXrr:
 605   case AArch64::ORNWrr:
 606   case AArch64::ORNXrr:
 607   case AArch64::ORRWrr:
 608   case AArch64::ORRXrr: {
 609     unsigned Opcode;
 610     switch (MI.getOpcode()) {
 611     default:
 612       return false;
 613     case AArch64::ADDWrr:      Opcode = AArch64::ADDWrs; break;
 614     case AArch64::SUBWrr:      Opcode = AArch64::SUBWrs; break;
 615     case AArch64::ADDXrr:      Opcode = AArch64::ADDXrs; break;
 616     case AArch64::SUBXrr:      Opcode = AArch64::SUBXrs; break;
 617     case AArch64::ADDSWrr:     Opcode = AArch64::ADDSWrs; break;
 618     case AArch64::SUBSWrr:     Opcode = AArch64::SUBSWrs; break;
 619     case AArch64::ADDSXrr:     Opcode = AArch64::ADDSXrs; break;
 620     case AArch64::SUBSXrr:     Opcode = AArch64::SUBSXrs; break;
 621     case AArch64::ANDWrr:      Opcode = AArch64::ANDWrs; break;
 622     case AArch64::ANDXrr:      Opcode = AArch64::ANDXrs; break;
 623     case AArch64::BICWrr:      Opcode = AArch64::BICWrs; break;
 624     case AArch64::BICXrr:      Opcode = AArch64::BICXrs; break;
 625     case AArch64::ANDSWrr:     Opcode = AArch64::ANDSWrs; break;
 626     case AArch64::ANDSXrr:     Opcode = AArch64::ANDSXrs; break;
 627     case AArch64::BICSWrr:     Opcode = AArch64::BICSWrs; break;
 628     case AArch64::BICSXrr:     Opcode = AArch64::BICSXrs; break;
 629     case AArch64::EONWrr:      Opcode = AArch64::EONWrs; break;
 630     case AArch64::EONXrr:      Opcode = AArch64::EONXrs; break;
 631     case AArch64::EORWrr:      Opcode = AArch64::EORWrs; break;
 632     case AArch64::EORXrr:      Opcode = AArch64::EORXrs; break;
 633     case AArch64::ORNWrr:      Opcode = AArch64::ORNWrs; break;
 634     case AArch64::ORNXrr:      Opcode = AArch64::ORNXrs; break;
 635     case AArch64::ORRWrr:      Opcode = AArch64::ORRWrs; break;
 636     case AArch64::ORRXrr:      Opcode = AArch64::ORRXrs; break;
 637     }
 638     MachineInstrBuilder MIB1 =
 639         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(Opcode),
 640                 MI.getOperand(0).getReg())
 641             .addOperand(MI.getOperand(1))
 642             .addOperand(MI.getOperand(2))
 643             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, 0));
 644     transferImpOps(MI, MIB1, MIB1);
 645     MI.eraseFromParent();
 646     return true;
 647   }
 648
 649   case AArch64::LOADgot: {
 650     // Expand into ADRP + LDR.
 651     unsigned DstReg = MI.getOperand(0).getReg();
 652     const MachineOperand &MO1 = MI.getOperand(1);
 653     unsigned Flags = MO1.getTargetFlags();
 654     MachineInstrBuilder MIB1 =
 655         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ADRP), DstReg);
 656     MachineInstrBuilder MIB2 =
 657         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::LDRXui))
 658             .addOperand(MI.getOperand(0))
 659             .addReg(DstReg);
 660
 661     if (MO1.isGlobal()) {
 662       MIB1.addGlobalAddress(MO1.getGlobal(), 0, Flags | AArch64II::MO_PAGE);
 663       MIB2.addGlobalAddress(MO1.getGlobal(), 0,
 664                             Flags | AArch64II::MO_PAGEOFF | AArch64II::MO_NC);
 665     } else if (MO1.isSymbol()) {
 666       MIB1.addExternalSymbol(MO1.getSymbolName(), Flags | AArch64II::MO_PAGE);
 667       MIB2.addExternalSymbol(MO1.getSymbolName(),
 668                              Flags | AArch64II::MO_PAGEOFF | AArch64II::MO_NC);
 669     } else {
 670       assert(MO1.isCPI() &&
 671              "Only expect globals, externalsymbols, or constant pools");
 672       MIB1.addConstantPoolIndex(MO1.getIndex(), MO1.getOffset(),
 673                                 Flags | AArch64II::MO_PAGE);
 674       MIB2.addConstantPoolIndex(MO1.getIndex(), MO1.getOffset(),
 675                                 Flags | AArch64II::MO_PAGEOFF |
 676                                     AArch64II::MO_NC);
 677     }
 678
 679     transferImpOps(MI, MIB1, MIB2);
 680     MI.eraseFromParent();
 681     return true;
 682   }
 683
 684   case AArch64::MOVaddr:
 685   case AArch64::MOVaddrJT:
 686   case AArch64::MOVaddrCP:
 687   case AArch64::MOVaddrBA:
 688   case AArch64::MOVaddrTLS:
 689   case AArch64::MOVaddrEXT: {
 690     // Expand into ADRP + ADD.
 691     unsigned DstReg = MI.getOperand(0).getReg();
 692     MachineInstrBuilder MIB1 =
 693         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ADRP), DstReg)
 694             .addOperand(MI.getOperand(1));
 695
 696     MachineInstrBuilder MIB2 =
 697         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::ADDXri))
 698             .addOperand(MI.getOperand(0))
 699             .addReg(DstReg)
 700             .addOperand(MI.getOperand(2))
 701             .addImm(0);
 702
 703     transferImpOps(MI, MIB1, MIB2);
 704     MI.eraseFromParent();
 705     return true;
 706   }
 707
 708   case AArch64::MOVi32imm:
 709     return expandMOVImm(MBB, MBBI, 32);
 710   case AArch64::MOVi64imm:
 711     return expandMOVImm(MBB, MBBI, 64);
 712   case AArch64::RET_ReallyLR: {
 713     MachineInstrBuilder MIB =
 714         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::RET))
 715           .addReg(AArch64::LR);
 716     transferImpOps(MI, MIB, MIB);
 717     MI.eraseFromParent();
 718     return true;
 719   }
 720   }
 721   return false;
 722 }
 723
 724 /// \brief Iterate over the instructions in basic block MBB and expand any
 725 /// pseudo instructions.  Return true if anything was modified.
 726 bool AArch64ExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
 727   bool Modified = false;
 728
 729   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 730   while (MBBI != E) {
 731     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
 732     Modified |= expandMI(MBB, MBBI);
 733     MBBI = NMBBI;
 734   }
 735
 736   return Modified;
 737 }
 738
 739 bool AArch64ExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
 740   TII = static_cast<const AArch64InstrInfo *>(MF.getSubtarget().getInstrInfo());
 741
 742   bool Modified = false;
 743   for (auto &MBB : MF)
 744     Modified |= expandMBB(MBB);
 745   return Modified;
 746 }
 747
 748 /// \brief Returns an instance of the pseudo instruction expansion pass.
 749 FunctionPass *llvm::createAArch64ExpandPseudoPass() {
 750   return new AArch64ExpandPseudo();
 751 }