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