lib/Target/AArch64/AArch64LoadStoreOptimizer.cpp

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