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