lib/Target/ARM64/ARM64LoadStoreOptimizer.cpp

   1 //===-- ARM64LoadStoreOptimizer.cpp - ARM64 load/store opt. pass --*- 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 performs load / store related peephole
  11 // optimizations. This pass should be run after register allocation.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "arm64-ldst-opt"
  16 #include "ARM64InstrInfo.h"
  17 #include "MCTargetDesc/ARM64AddressingModes.h"
  18 #include "llvm/ADT/BitVector.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/ErrorHandling.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/ADT/Statistic.h"
  31 using namespace llvm;
  32
  33 /// ARM64AllocLoadStoreOpt - Post-register allocation pass to combine
  34 /// load / store instructions to form ldp / stp instructions.
  35
  36 STATISTIC(NumPairCreated, "Number of load/store pair instructions generated");
  37 STATISTIC(NumPostFolded, "Number of post-index updates folded");
  38 STATISTIC(NumPreFolded, "Number of pre-index updates folded");
  39 STATISTIC(NumUnscaledPairCreated,
  40           "Number of load/store from unscaled generated");
  41
  42 static cl::opt<bool> DoLoadStoreOpt("arm64-load-store-opt", cl::init(true),
  43                                     cl::Hidden);
  44 static cl::opt<unsigned> ScanLimit("arm64-load-store-scan-limit", cl::init(20),
  45                                    cl::Hidden);
  46
  47 // Place holder while testing unscaled load/store combining
  48 static cl::opt<bool>
  49 EnableARM64UnscaledMemOp("arm64-unscaled-mem-op", cl::Hidden,
  50                          cl::desc("Allow ARM64 unscaled load/store combining"),
  51                          cl::init(true));
  52
  53 namespace {
  54 struct ARM64LoadStoreOpt : public MachineFunctionPass {
  55   static char ID;
  56   ARM64LoadStoreOpt() : MachineFunctionPass(ID) {}
  57
  58   const ARM64InstrInfo *TII;
  59   const TargetRegisterInfo *TRI;
  60
  61   // Scan the instructions looking for a load/store that can be combined
  62   // with the current instruction into a load/store pair.
  63   // Return the matching instruction if one is found, else MBB->end().
  64   // If a matching instruction is found, mergeForward is set to true if the
  65   // merge is to remove the first instruction and replace the second with
  66   // a pair-wise insn, and false if the reverse is true.
  67   MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,
  68                                                bool &mergeForward,
  69                                                unsigned Limit);
  70   // Merge the two instructions indicated into a single pair-wise instruction.
  71   // If mergeForward is true, erase the first instruction and fold its
  72   // operation into the second. If false, the reverse. Return the instruction
  73   // following the first instruction (which may change during proecessing).
  74   MachineBasicBlock::iterator
  75   mergePairedInsns(MachineBasicBlock::iterator I,
  76                    MachineBasicBlock::iterator Paired, bool mergeForward);
  77
  78   // Scan the instruction list to find a base register update that can
  79   // be combined with the current instruction (a load or store) using
  80   // pre or post indexed addressing with writeback. Scan forwards.
  81   MachineBasicBlock::iterator
  82   findMatchingUpdateInsnForward(MachineBasicBlock::iterator I, unsigned Limit,
  83                                 int Value);
  84
  85   // Scan the instruction list to find a base register update that can
  86   // be combined with the current instruction (a load or store) using
  87   // pre or post indexed addressing with writeback. Scan backwards.
  88   MachineBasicBlock::iterator
  89   findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I, unsigned Limit);
  90
  91   // Merge a pre-index base register update into a ld/st instruction.
  92   MachineBasicBlock::iterator
  93   mergePreIdxUpdateInsn(MachineBasicBlock::iterator I,
  94                         MachineBasicBlock::iterator Update);
  95
  96   // Merge a post-index base register update into a ld/st instruction.
  97   MachineBasicBlock::iterator
  98   mergePostIdxUpdateInsn(MachineBasicBlock::iterator I,
  99                          MachineBasicBlock::iterator Update);
 100
 101   bool optimizeBlock(MachineBasicBlock &MBB);
 102
 103   virtual bool runOnMachineFunction(MachineFunction &Fn);
 104
 105   virtual const char *getPassName() const {
 106     return "ARM64 load / store optimization pass";
 107   }
 108
 109 private:
 110   int getMemSize(MachineInstr *MemMI);
 111 };
 112 char ARM64LoadStoreOpt::ID = 0;
 113 }
 114
 115 static bool isUnscaledLdst(unsigned Opc) {
 116   switch (Opc) {
 117   default:
 118     return false;
 119   case ARM64::STURSi:
 120     return true;
 121   case ARM64::STURDi:
 122     return true;
 123   case ARM64::STURQi:
 124     return true;
 125   case ARM64::STURWi:
 126     return true;
 127   case ARM64::STURXi:
 128     return true;
 129   case ARM64::LDURSi:
 130     return true;
 131   case ARM64::LDURDi:
 132     return true;
 133   case ARM64::LDURQi:
 134     return true;
 135   case ARM64::LDURWi:
 136     return true;
 137   case ARM64::LDURXi:
 138     return true;
 139   }
 140 }
 141
 142 // Size in bytes of the data moved by an unscaled load or store
 143 int ARM64LoadStoreOpt::getMemSize(MachineInstr *MemMI) {
 144   switch (MemMI->getOpcode()) {
 145   default:
 146     llvm_unreachable("Opcode has has unknown size!");
 147   case ARM64::STRSui:
 148   case ARM64::STURSi:
 149     return 4;
 150   case ARM64::STRDui:
 151   case ARM64::STURDi:
 152     return 8;
 153   case ARM64::STRQui:
 154   case ARM64::STURQi:
 155     return 16;
 156   case ARM64::STRWui:
 157   case ARM64::STURWi:
 158     return 4;
 159   case ARM64::STRXui:
 160   case ARM64::STURXi:
 161     return 8;
 162   case ARM64::LDRSui:
 163   case ARM64::LDURSi:
 164     return 4;
 165   case ARM64::LDRDui:
 166   case ARM64::LDURDi:
 167     return 8;
 168   case ARM64::LDRQui:
 169   case ARM64::LDURQi:
 170     return 16;
 171   case ARM64::LDRWui:
 172   case ARM64::LDURWi:
 173     return 4;
 174   case ARM64::LDRXui:
 175   case ARM64::LDURXi:
 176     return 8;
 177   }
 178 }
 179
 180 static unsigned getMatchingPairOpcode(unsigned Opc) {
 181   switch (Opc) {
 182   default:
 183     llvm_unreachable("Opcode has no pairwise equivalent!");
 184   case ARM64::STRSui:
 185   case ARM64::STURSi:
 186     return ARM64::STPSi;
 187   case ARM64::STRDui:
 188   case ARM64::STURDi:
 189     return ARM64::STPDi;
 190   case ARM64::STRQui:
 191   case ARM64::STURQi:
 192     return ARM64::STPQi;
 193   case ARM64::STRWui:
 194   case ARM64::STURWi:
 195     return ARM64::STPWi;
 196   case ARM64::STRXui:
 197   case ARM64::STURXi:
 198     return ARM64::STPXi;
 199   case ARM64::LDRSui:
 200   case ARM64::LDURSi:
 201     return ARM64::LDPSi;
 202   case ARM64::LDRDui:
 203   case ARM64::LDURDi:
 204     return ARM64::LDPDi;
 205   case ARM64::LDRQui:
 206   case ARM64::LDURQi:
 207     return ARM64::LDPQi;
 208   case ARM64::LDRWui:
 209   case ARM64::LDURWi:
 210     return ARM64::LDPWi;
 211   case ARM64::LDRXui:
 212   case ARM64::LDURXi:
 213     return ARM64::LDPXi;
 214   }
 215 }
 216
 217 static unsigned getPreIndexedOpcode(unsigned Opc) {
 218   switch (Opc) {
 219   default:
 220     llvm_unreachable("Opcode has no pre-indexed equivalent!");
 221   case ARM64::STRSui:    return ARM64::STRSpre;
 222   case ARM64::STRDui:    return ARM64::STRDpre;
 223   case ARM64::STRQui:    return ARM64::STRQpre;
 224   case ARM64::STRWui:    return ARM64::STRWpre;
 225   case ARM64::STRXui:    return ARM64::STRXpre;
 226   case ARM64::LDRSui:    return ARM64::LDRSpre;
 227   case ARM64::LDRDui:    return ARM64::LDRDpre;
 228   case ARM64::LDRQui:    return ARM64::LDRQpre;
 229   case ARM64::LDRWui:    return ARM64::LDRWpre;
 230   case ARM64::LDRXui:    return ARM64::LDRXpre;
 231   }
 232 }
 233
 234 static unsigned getPostIndexedOpcode(unsigned Opc) {
 235   switch (Opc) {
 236   default:
 237     llvm_unreachable("Opcode has no post-indexed wise equivalent!");
 238   case ARM64::STRSui:
 239     return ARM64::STRSpost;
 240   case ARM64::STRDui:
 241     return ARM64::STRDpost;
 242   case ARM64::STRQui:
 243     return ARM64::STRQpost;
 244   case ARM64::STRWui:
 245     return ARM64::STRWpost;
 246   case ARM64::STRXui:
 247     return ARM64::STRXpost;
 248   case ARM64::LDRSui:
 249     return ARM64::LDRSpost;
 250   case ARM64::LDRDui:
 251     return ARM64::LDRDpost;
 252   case ARM64::LDRQui:
 253     return ARM64::LDRQpost;
 254   case ARM64::LDRWui:
 255     return ARM64::LDRWpost;
 256   case ARM64::LDRXui:
 257     return ARM64::LDRXpost;
 258   }
 259 }
 260
 261 MachineBasicBlock::iterator
 262 ARM64LoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,
 263                                     MachineBasicBlock::iterator Paired,
 264                                     bool mergeForward) {
 265   MachineBasicBlock::iterator NextI = I;
 266   ++NextI;
 267   // If NextI is the second of the two instructions to be merged, we need
 268   // to skip one further. Either way we merge will invalidate the iterator,
 269   // and we don't need to scan the new instruction, as it's a pairwise
 270   // instruction, which we're not considering for further action anyway.
 271   if (NextI == Paired)
 272     ++NextI;
 273
 274   bool IsUnscaled = isUnscaledLdst(I->getOpcode());
 275   int OffsetStride = IsUnscaled && EnableARM64UnscaledMemOp ? getMemSize(I) : 1;
 276
 277   unsigned NewOpc = getMatchingPairOpcode(I->getOpcode());
 278   // Insert our new paired instruction after whichever of the paired
 279   // instructions mergeForward indicates.
 280   MachineBasicBlock::iterator InsertionPoint = mergeForward ? Paired : I;
 281   // Also based on mergeForward is from where we copy the base register operand
 282   // so we get the flags compatible with the input code.
 283   MachineOperand &BaseRegOp =
 284       mergeForward ? Paired->getOperand(1) : I->getOperand(1);
 285
 286   // Which register is Rt and which is Rt2 depends on the offset order.
 287   MachineInstr *RtMI, *Rt2MI;
 288   if (I->getOperand(2).getImm() ==
 289       Paired->getOperand(2).getImm() + OffsetStride) {
 290     RtMI = Paired;
 291     Rt2MI = I;
 292   } else {
 293     RtMI = I;
 294     Rt2MI = Paired;
 295   }
 296   // Handle Unscaled
 297   int OffsetImm = RtMI->getOperand(2).getImm();
 298   if (IsUnscaled && EnableARM64UnscaledMemOp)
 299     OffsetImm /= OffsetStride;
 300
 301   // Construct the new instruction.
 302   MachineInstrBuilder MIB = BuildMI(*I->getParent(), InsertionPoint,
 303                                     I->getDebugLoc(), TII->get(NewOpc))
 304                                 .addOperand(RtMI->getOperand(0))
 305                                 .addOperand(Rt2MI->getOperand(0))
 306                                 .addOperand(BaseRegOp)
 307                                 .addImm(OffsetImm);
 308   (void)MIB;
 309
 310   // FIXME: Do we need/want to copy the mem operands from the source
 311   //        instructions? Probably. What uses them after this?
 312
 313   DEBUG(dbgs() << "Creating pair load/store. Replacing instructions:\n    ");
 314   DEBUG(I->print(dbgs()));
 315   DEBUG(dbgs() << "    ");
 316   DEBUG(Paired->print(dbgs()));
 317   DEBUG(dbgs() << "  with instruction:\n    ");
 318   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 319   DEBUG(dbgs() << "\n");
 320
 321   // Erase the old instructions.
 322   I->eraseFromParent();
 323   Paired->eraseFromParent();
 324
 325   return NextI;
 326 }
 327
 328 /// trackRegDefsUses - Remember what registers the specified instruction uses
 329 /// and modifies.
 330 static void trackRegDefsUses(MachineInstr *MI, BitVector &ModifiedRegs,
 331                              BitVector &UsedRegs,
 332                              const TargetRegisterInfo *TRI) {
 333   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 334     MachineOperand &MO = MI->getOperand(i);
 335     if (MO.isRegMask())
 336       ModifiedRegs.setBitsNotInMask(MO.getRegMask());
 337
 338     if (!MO.isReg())
 339       continue;
 340     unsigned Reg = MO.getReg();
 341     if (MO.isDef()) {
 342       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 343         ModifiedRegs.set(*AI);
 344     } else {
 345       assert(MO.isUse() && "Reg operand not a def and not a use?!?");
 346       for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
 347         UsedRegs.set(*AI);
 348     }
 349   }
 350 }
 351
 352 static bool inBoundsForPair(bool IsUnscaled, int Offset, int OffsetStride) {
 353   if (!IsUnscaled && (Offset > 63 || Offset < -64))
 354     return false;
 355   if (IsUnscaled) {
 356     // Convert the byte-offset used by unscaled into an "element" offset used
 357     // by the scaled pair load/store instructions.
 358     int elemOffset = Offset / OffsetStride;
 359     if (elemOffset > 63 || elemOffset < -64)
 360       return false;
 361   }
 362   return true;
 363 }
 364
 365 // Do alignment, specialized to power of 2 and for signed ints,
 366 // avoiding having to do a C-style cast from uint_64t to int when
 367 // using RoundUpToAlignment from include/llvm/Support/MathExtras.h.
 368 // FIXME: Move this function to include/MathExtras.h?
 369 static int alignTo(int Num, int PowOf2) {
 370   return (Num + PowOf2 - 1) & ~(PowOf2 - 1);
 371 }
 372
 373 /// findMatchingInsn - Scan the instructions looking for a load/store that can
 374 /// be combined with the current instruction into a load/store pair.
 375 MachineBasicBlock::iterator
 376 ARM64LoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,
 377                                     bool &mergeForward, unsigned Limit) {
 378   MachineBasicBlock::iterator E = I->getParent()->end();
 379   MachineBasicBlock::iterator MBBI = I;
 380   MachineInstr *FirstMI = I;
 381   ++MBBI;
 382
 383   int Opc = FirstMI->getOpcode();
 384   bool mayLoad = FirstMI->mayLoad();
 385   bool IsUnscaled = isUnscaledLdst(Opc);
 386   unsigned Reg = FirstMI->getOperand(0).getReg();
 387   unsigned BaseReg = FirstMI->getOperand(1).getReg();
 388   int Offset = FirstMI->getOperand(2).getImm();
 389
 390   // Early exit if the first instruction modifies the base register.
 391   // e.g., ldr x0, [x0]
 392   // Early exit if the offset if not possible to match. (6 bits of positive
 393   // range, plus allow an extra one in case we find a later insn that matches
 394   // with Offset-1
 395   if (FirstMI->modifiesRegister(BaseReg, TRI))
 396     return E;
 397   int OffsetStride =
 398       IsUnscaled && EnableARM64UnscaledMemOp ? getMemSize(FirstMI) : 1;
 399   if (!inBoundsForPair(IsUnscaled, Offset, OffsetStride))
 400     return E;
 401
 402   // Track which registers have been modified and used between the first insn
 403   // (inclusive) and the second insn.
 404   BitVector ModifiedRegs, UsedRegs;
 405   ModifiedRegs.resize(TRI->getNumRegs());
 406   UsedRegs.resize(TRI->getNumRegs());
 407   for (unsigned Count = 0; MBBI != E && Count < Limit; ++MBBI) {
 408     MachineInstr *MI = MBBI;
 409     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
 410     // optimization by changing how far we scan.
 411     if (MI->isDebugValue())
 412       continue;
 413
 414     // Now that we know this is a real instruction, count it.
 415     ++Count;
 416
 417     if (Opc == MI->getOpcode() && MI->getOperand(2).isImm()) {
 418       // If we've found another instruction with the same opcode, check to see
 419       // if the base and offset are compatible with our starting instruction.
 420       // These instructions all have scaled immediate operands, so we just
 421       // check for +1/-1. Make sure to check the new instruction offset is
 422       // actually an immediate and not a symbolic reference destined for
 423       // a relocation.
 424       //
 425       // Pairwise instructions have a 7-bit signed offset field. Single insns
 426       // have a 12-bit unsigned offset field. To be a valid combine, the
 427       // final offset must be in range.
 428       unsigned MIBaseReg = MI->getOperand(1).getReg();
 429       int MIOffset = MI->getOperand(2).getImm();
 430       if (BaseReg == MIBaseReg && ((Offset == MIOffset + OffsetStride) ||
 431                                    (Offset + OffsetStride == MIOffset))) {
 432         int MinOffset = Offset < MIOffset ? Offset : MIOffset;
 433         // If this is a volatile load/store that otherwise matched, stop looking
 434         // as something is going on that we don't have enough information to
 435         // safely transform. Similarly, stop if we see a hint to avoid pairs.
 436         if (MI->hasOrderedMemoryRef() || TII->isLdStPairSuppressed(MI))
 437           return E;
 438         // If the resultant immediate offset of merging these instructions
 439         // is out of range for a pairwise instruction, bail and keep looking.
 440         bool MIIsUnscaled = isUnscaledLdst(MI->getOpcode());
 441         if (!inBoundsForPair(MIIsUnscaled, MinOffset, OffsetStride)) {
 442           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 443           continue;
 444         }
 445         // If the alignment requirements of the paired (scaled) instruction
 446         // can't express the offset of the unscaled input, bail and keep
 447         // looking.
 448         if (IsUnscaled && EnableARM64UnscaledMemOp &&
 449             (alignTo(MinOffset, OffsetStride) != MinOffset)) {
 450           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 451           continue;
 452         }
 453         // If the destination register of the loads is the same register, bail
 454         // and keep looking. A load-pair instruction with both destination
 455         // registers the same is UNPREDICTABLE and will result in an exception.
 456         if (mayLoad && Reg == MI->getOperand(0).getReg()) {
 457           trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 458           continue;
 459         }
 460
 461         // If the Rt of the second instruction was not modified or used between
 462         // the two instructions, we can combine the second into the first.
 463         if (!ModifiedRegs[MI->getOperand(0).getReg()] &&
 464             !UsedRegs[MI->getOperand(0).getReg()]) {
 465           mergeForward = false;
 466           return MBBI;
 467         }
 468
 469         // Likewise, if the Rt of the first instruction is not modified or used
 470         // between the two instructions, we can combine the first into the
 471         // second.
 472         if (!ModifiedRegs[FirstMI->getOperand(0).getReg()] &&
 473             !UsedRegs[FirstMI->getOperand(0).getReg()]) {
 474           mergeForward = true;
 475           return MBBI;
 476         }
 477         // Unable to combine these instructions due to interference in between.
 478         // Keep looking.
 479       }
 480     }
 481
 482     // If the instruction wasn't a matching load or store, but does (or can)
 483     // modify memory, stop searching, as we don't have alias analysis or
 484     // anything like that to tell us whether the access is tromping on the
 485     // locations we care about. The big one we want to catch is calls.
 486     //
 487     // FIXME: Theoretically, we can do better than that for SP and FP based
 488     // references since we can effectively know where those are touching. It's
 489     // unclear if it's worth the extra code, though. Most paired instructions
 490     // will be sequential, perhaps with a few intervening non-memory related
 491     // instructions.
 492     if (MI->mayStore() || MI->isCall())
 493       return E;
 494     // Likewise, if we're matching a store instruction, we don't want to
 495     // move across a load, as it may be reading the same location.
 496     if (FirstMI->mayStore() && MI->mayLoad())
 497       return E;
 498
 499     // Update modified / uses register lists.
 500     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 501
 502     // Otherwise, if the base register is modified, we have no match, so
 503     // return early.
 504     if (ModifiedRegs[BaseReg])
 505       return E;
 506   }
 507   return E;
 508 }
 509
 510 MachineBasicBlock::iterator
 511 ARM64LoadStoreOpt::mergePreIdxUpdateInsn(MachineBasicBlock::iterator I,
 512                                          MachineBasicBlock::iterator Update) {
 513   assert((Update->getOpcode() == ARM64::ADDXri ||
 514           Update->getOpcode() == ARM64::SUBXri) &&
 515          "Unexpected base register update instruction to merge!");
 516   MachineBasicBlock::iterator NextI = I;
 517   // Return the instruction following the merged instruction, which is
 518   // the instruction following our unmerged load. Unless that's the add/sub
 519   // instruction we're merging, in which case it's the one after that.
 520   if (++NextI == Update)
 521     ++NextI;
 522
 523   int Value = Update->getOperand(2).getImm();
 524   assert(ARM64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
 525          "Can't merge 1 << 12 offset into pre-indexed load / store");
 526   if (Update->getOpcode() == ARM64::SUBXri)
 527     Value = -Value;
 528
 529   unsigned NewOpc = getPreIndexedOpcode(I->getOpcode());
 530   MachineInstrBuilder MIB =
 531       BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
 532           .addOperand(I->getOperand(0))
 533           .addOperand(I->getOperand(1))
 534           .addImm(Value);
 535   (void)MIB;
 536
 537   DEBUG(dbgs() << "Creating pre-indexed load/store.");
 538   DEBUG(dbgs() << "    Replacing instructions:\n    ");
 539   DEBUG(I->print(dbgs()));
 540   DEBUG(dbgs() << "    ");
 541   DEBUG(Update->print(dbgs()));
 542   DEBUG(dbgs() << "  with instruction:\n    ");
 543   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 544   DEBUG(dbgs() << "\n");
 545
 546   // Erase the old instructions for the block.
 547   I->eraseFromParent();
 548   Update->eraseFromParent();
 549
 550   return NextI;
 551 }
 552
 553 MachineBasicBlock::iterator
 554 ARM64LoadStoreOpt::mergePostIdxUpdateInsn(MachineBasicBlock::iterator I,
 555                                           MachineBasicBlock::iterator Update) {
 556   assert((Update->getOpcode() == ARM64::ADDXri ||
 557           Update->getOpcode() == ARM64::SUBXri) &&
 558          "Unexpected base register update instruction to merge!");
 559   MachineBasicBlock::iterator NextI = I;
 560   // Return the instruction following the merged instruction, which is
 561   // the instruction following our unmerged load. Unless that's the add/sub
 562   // instruction we're merging, in which case it's the one after that.
 563   if (++NextI == Update)
 564     ++NextI;
 565
 566   int Value = Update->getOperand(2).getImm();
 567   assert(ARM64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
 568          "Can't merge 1 << 12 offset into post-indexed load / store");
 569   if (Update->getOpcode() == ARM64::SUBXri)
 570     Value = -Value;
 571
 572   unsigned NewOpc = getPostIndexedOpcode(I->getOpcode());
 573   MachineInstrBuilder MIB =
 574       BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
 575           .addOperand(I->getOperand(0))
 576           .addOperand(I->getOperand(1))
 577           .addImm(Value);
 578   (void)MIB;
 579
 580   DEBUG(dbgs() << "Creating post-indexed load/store.");
 581   DEBUG(dbgs() << "    Replacing instructions:\n    ");
 582   DEBUG(I->print(dbgs()));
 583   DEBUG(dbgs() << "    ");
 584   DEBUG(Update->print(dbgs()));
 585   DEBUG(dbgs() << "  with instruction:\n    ");
 586   DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 587   DEBUG(dbgs() << "\n");
 588
 589   // Erase the old instructions for the block.
 590   I->eraseFromParent();
 591   Update->eraseFromParent();
 592
 593   return NextI;
 594 }
 595
 596 static bool isMatchingUpdateInsn(MachineInstr *MI, unsigned BaseReg,
 597                                  int Offset) {
 598   switch (MI->getOpcode()) {
 599   default:
 600     break;
 601   case ARM64::SUBXri:
 602     // Negate the offset for a SUB instruction.
 603     Offset *= -1;
 604   // FALLTHROUGH
 605   case ARM64::ADDXri:
 606     // Make sure it's a vanilla immediate operand, not a relocation or
 607     // anything else we can't handle.
 608     if (!MI->getOperand(2).isImm())
 609       break;
 610     // Watch out for 1 << 12 shifted value.
 611     if (ARM64_AM::getShiftValue(MI->getOperand(3).getImm()))
 612       break;
 613     // If the instruction has the base register as source and dest and the
 614     // immediate will fit in a signed 9-bit integer, then we have a match.
 615     if (MI->getOperand(0).getReg() == BaseReg &&
 616         MI->getOperand(1).getReg() == BaseReg &&
 617         MI->getOperand(2).getImm() <= 255 &&
 618         MI->getOperand(2).getImm() >= -256) {
 619       // If we have a non-zero Offset, we check that it matches the amount
 620       // we're adding to the register.
 621       if (!Offset || Offset == MI->getOperand(2).getImm())
 622         return true;
 623     }
 624     break;
 625   }
 626   return false;
 627 }
 628
 629 MachineBasicBlock::iterator
 630 ARM64LoadStoreOpt::findMatchingUpdateInsnForward(MachineBasicBlock::iterator I,
 631                                                  unsigned Limit, int Value) {
 632   MachineBasicBlock::iterator E = I->getParent()->end();
 633   MachineInstr *MemMI = I;
 634   MachineBasicBlock::iterator MBBI = I;
 635   const MachineFunction &MF = *MemMI->getParent()->getParent();
 636
 637   unsigned DestReg = MemMI->getOperand(0).getReg();
 638   unsigned BaseReg = MemMI->getOperand(1).getReg();
 639   int Offset = MemMI->getOperand(2).getImm() *
 640                TII->getRegClass(MemMI->getDesc(), 0, TRI, MF)->getSize();
 641
 642   // If the base register overlaps the destination register, we can't
 643   // merge the update.
 644   if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
 645     return E;
 646
 647   // Scan forward looking for post-index opportunities.
 648   // Updating instructions can't be formed if the memory insn already
 649   // has an offset other than the value we're looking for.
 650   if (Offset != Value)
 651     return E;
 652
 653   // Track which registers have been modified and used between the first insn
 654   // (inclusive) and the second insn.
 655   BitVector ModifiedRegs, UsedRegs;
 656   ModifiedRegs.resize(TRI->getNumRegs());
 657   UsedRegs.resize(TRI->getNumRegs());
 658   ++MBBI;
 659   for (unsigned Count = 0; MBBI != E; ++MBBI) {
 660     MachineInstr *MI = MBBI;
 661     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
 662     // optimization by changing how far we scan.
 663     if (MI->isDebugValue())
 664       continue;
 665
 666     // Now that we know this is a real instruction, count it.
 667     ++Count;
 668
 669     // If we found a match, return it.
 670     if (isMatchingUpdateInsn(MI, BaseReg, Value))
 671       return MBBI;
 672
 673     // Update the status of what the instruction clobbered and used.
 674     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 675
 676     // Otherwise, if the base register is used or modified, we have no match, so
 677     // return early.
 678     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
 679       return E;
 680   }
 681   return E;
 682 }
 683
 684 MachineBasicBlock::iterator
 685 ARM64LoadStoreOpt::findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I,
 686                                                   unsigned Limit) {
 687   MachineBasicBlock::iterator B = I->getParent()->begin();
 688   MachineBasicBlock::iterator E = I->getParent()->end();
 689   MachineInstr *MemMI = I;
 690   MachineBasicBlock::iterator MBBI = I;
 691   const MachineFunction &MF = *MemMI->getParent()->getParent();
 692
 693   unsigned DestReg = MemMI->getOperand(0).getReg();
 694   unsigned BaseReg = MemMI->getOperand(1).getReg();
 695   int Offset = MemMI->getOperand(2).getImm();
 696   unsigned RegSize = TII->getRegClass(MemMI->getDesc(), 0, TRI, MF)->getSize();
 697
 698   // If the load/store is the first instruction in the block, there's obviously
 699   // not any matching update. Ditto if the memory offset isn't zero.
 700   if (MBBI == B || Offset != 0)
 701     return E;
 702   // If the base register overlaps the destination register, we can't
 703   // merge the update.
 704   if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
 705     return E;
 706
 707   // Track which registers have been modified and used between the first insn
 708   // (inclusive) and the second insn.
 709   BitVector ModifiedRegs, UsedRegs;
 710   ModifiedRegs.resize(TRI->getNumRegs());
 711   UsedRegs.resize(TRI->getNumRegs());
 712   --MBBI;
 713   for (unsigned Count = 0; MBBI != B; --MBBI) {
 714     MachineInstr *MI = MBBI;
 715     // Skip DBG_VALUE instructions. Otherwise debug info can affect the
 716     // optimization by changing how far we scan.
 717     if (MI->isDebugValue())
 718       continue;
 719
 720     // Now that we know this is a real instruction, count it.
 721     ++Count;
 722
 723     // If we found a match, return it.
 724     if (isMatchingUpdateInsn(MI, BaseReg, RegSize))
 725       return MBBI;
 726
 727     // Update the status of what the instruction clobbered and used.
 728     trackRegDefsUses(MI, ModifiedRegs, UsedRegs, TRI);
 729
 730     // Otherwise, if the base register is used or modified, we have no match, so
 731     // return early.
 732     if (ModifiedRegs[BaseReg] || UsedRegs[BaseReg])
 733       return E;
 734   }
 735   return E;
 736 }
 737
 738 bool ARM64LoadStoreOpt::optimizeBlock(MachineBasicBlock &MBB) {
 739   bool Modified = false;
 740   // Two tranformations to do here:
 741   // 1) Find loads and stores that can be merged into a single load or store
 742   //    pair instruction.
 743   //      e.g.,
 744   //        ldr x0, [x2]
 745   //        ldr x1, [x2, #8]
 746   //        ; becomes
 747   //        ldp x0, x1, [x2]
 748   // 2) Find base register updates that can be merged into the load or store
 749   //    as a base-reg writeback.
 750   //      e.g.,
 751   //        ldr x0, [x2]
 752   //        add x2, x2, #4
 753   //        ; becomes
 754   //        ldr x0, [x2], #4
 755
 756   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 757        MBBI != E;) {
 758     MachineInstr *MI = MBBI;
 759     switch (MI->getOpcode()) {
 760     default:
 761       // Just move on to the next instruction.
 762       ++MBBI;
 763       break;
 764     case ARM64::STRSui:
 765     case ARM64::STRDui:
 766     case ARM64::STRQui:
 767     case ARM64::STRXui:
 768     case ARM64::STRWui:
 769     case ARM64::LDRSui:
 770     case ARM64::LDRDui:
 771     case ARM64::LDRQui:
 772     case ARM64::LDRXui:
 773     case ARM64::LDRWui:
 774     // do the unscaled versions as well
 775     case ARM64::STURSi:
 776     case ARM64::STURDi:
 777     case ARM64::STURQi:
 778     case ARM64::STURWi:
 779     case ARM64::STURXi:
 780     case ARM64::LDURSi:
 781     case ARM64::LDURDi:
 782     case ARM64::LDURQi:
 783     case ARM64::LDURWi:
 784     case ARM64::LDURXi: {
 785       // If this is a volatile load/store, don't mess with it.
 786       if (MI->hasOrderedMemoryRef()) {
 787         ++MBBI;
 788         break;
 789       }
 790       // Make sure this is a reg+imm (as opposed to an address reloc).
 791       if (!MI->getOperand(2).isImm()) {
 792         ++MBBI;
 793         break;
 794       }
 795       // Check if this load/store has a hint to avoid pair formation.
 796       // MachineMemOperands hints are set by the ARM64StorePairSuppress pass.
 797       if (TII->isLdStPairSuppressed(MI)) {
 798         ++MBBI;
 799         break;
 800       }
 801       // Look ahead up to ScanLimit instructions for a pairable instruction.
 802       bool mergeForward = false;
 803       MachineBasicBlock::iterator Paired =
 804           findMatchingInsn(MBBI, mergeForward, ScanLimit);
 805       if (Paired != E) {
 806         // Merge the loads into a pair. Keeping the iterator straight is a
 807         // pain, so we let the merge routine tell us what the next instruction
 808         // is after it's done mucking about.
 809         MBBI = mergePairedInsns(MBBI, Paired, mergeForward);
 810
 811         Modified = true;
 812         ++NumPairCreated;
 813         if (isUnscaledLdst(MI->getOpcode()))
 814           ++NumUnscaledPairCreated;
 815         break;
 816       }
 817       ++MBBI;
 818       break;
 819     }
 820       // FIXME: Do the other instructions.
 821     }
 822   }
 823
 824   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 825        MBBI != E;) {
 826     MachineInstr *MI = MBBI;
 827     // Do update merging. It's simpler to keep this separate from the above
 828     // switch, though not strictly necessary.
 829     int Opc = MI->getOpcode();
 830     switch (Opc) {
 831     default:
 832       // Just move on to the next instruction.
 833       ++MBBI;
 834       break;
 835     case ARM64::STRSui:
 836     case ARM64::STRDui:
 837     case ARM64::STRQui:
 838     case ARM64::STRXui:
 839     case ARM64::STRWui:
 840     case ARM64::LDRSui:
 841     case ARM64::LDRDui:
 842     case ARM64::LDRQui:
 843     case ARM64::LDRXui:
 844     case ARM64::LDRWui:
 845     // do the unscaled versions as well
 846     case ARM64::STURSi:
 847     case ARM64::STURDi:
 848     case ARM64::STURQi:
 849     case ARM64::STURWi:
 850     case ARM64::STURXi:
 851     case ARM64::LDURSi:
 852     case ARM64::LDURDi:
 853     case ARM64::LDURQi:
 854     case ARM64::LDURWi:
 855     case ARM64::LDURXi: {
 856       // Make sure this is a reg+imm (as opposed to an address reloc).
 857       if (!MI->getOperand(2).isImm()) {
 858         ++MBBI;
 859         break;
 860       }
 861       // Look ahead up to ScanLimit instructions for a mergable instruction.
 862       MachineBasicBlock::iterator Update =
 863           findMatchingUpdateInsnForward(MBBI, ScanLimit, 0);
 864       if (Update != E) {
 865         // Merge the update into the ld/st.
 866         MBBI = mergePostIdxUpdateInsn(MBBI, Update);
 867         Modified = true;
 868         ++NumPostFolded;
 869         break;
 870       }
 871       // Don't know how to handle pre/post-index versions, so move to the next
 872       // instruction.
 873       if (isUnscaledLdst(Opc)) {
 874         ++MBBI;
 875         break;
 876       }
 877
 878       // Look back to try to find a pre-index instruction. For example,
 879       // add x0, x0, #8
 880       // ldr x1, [x0]
 881       //   merged into:
 882       // ldr x1, [x0, #8]!
 883       Update = findMatchingUpdateInsnBackward(MBBI, ScanLimit);
 884       if (Update != E) {
 885         // Merge the update into the ld/st.
 886         MBBI = mergePreIdxUpdateInsn(MBBI, Update);
 887         Modified = true;
 888         ++NumPreFolded;
 889         break;
 890       }
 891
 892       // Look forward to try to find a post-index instruction. For example,
 893       // ldr x1, [x0, #64]
 894       // add x0, x0, #64
 895       //   merged into:
 896       // ldr x1, [x0], #64
 897
 898       // The immediate in the load/store is scaled by the size of the register
 899       // being loaded. The immediate in the add we're looking for,
 900       // however, is not, so adjust here.
 901       int Value = MI->getOperand(2).getImm() *
 902                   TII->getRegClass(MI->getDesc(), 0, TRI, *(MBB.getParent()))
 903                       ->getSize();
 904       Update = findMatchingUpdateInsnForward(MBBI, ScanLimit, Value);
 905       if (Update != E) {
 906         // Merge the update into the ld/st.
 907         MBBI = mergePreIdxUpdateInsn(MBBI, Update);
 908         Modified = true;
 909         ++NumPreFolded;
 910         break;
 911       }
 912
 913       // Nothing found. Just move to the next instruction.
 914       ++MBBI;
 915       break;
 916     }
 917       // FIXME: Do the other instructions.
 918     }
 919   }
 920
 921   return Modified;
 922 }
 923
 924 bool ARM64LoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
 925   // Early exit if pass disabled.
 926   if (!DoLoadStoreOpt)
 927     return false;
 928
 929   const TargetMachine &TM = Fn.getTarget();
 930   TII = static_cast<const ARM64InstrInfo *>(TM.getInstrInfo());
 931   TRI = TM.getRegisterInfo();
 932
 933   bool Modified = false;
 934   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
 935        ++MFI) {
 936     MachineBasicBlock &MBB = *MFI;
 937     Modified |= optimizeBlock(MBB);
 938   }
 939
 940   return Modified;
 941 }
 942
 943 // FIXME: Do we need/want a pre-alloc pass like ARM has to try to keep
 944 // loads and stores near one another?
 945
 946 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
 947 /// optimization pass.
 948 FunctionPass *llvm::createARM64LoadStoreOptimizationPass() {
 949   return new ARM64LoadStoreOpt();
 950 }