contrib/llvm-project/llvm/lib/Target/AArch64/AArch64LoadStoreOptimizer.cpp

   1 //===- AArch64LoadStoreOptimizer.cpp - AArch64 load/store opt. pass -------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains a pass that performs load / store related peephole
  10 // optimizations. This pass should be run after register allocation.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "AArch64InstrInfo.h"
  15 #include "AArch64Subtarget.h"
  16 #include "MCTargetDesc/AArch64AddressingModes.h"
  17 #include "llvm/ADT/BitVector.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/ADT/iterator_range.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineFunctionPass.h"
  26 #include "llvm/CodeGen/MachineInstr.h"
  27 #include "llvm/CodeGen/MachineInstrBuilder.h"
  28 #include "llvm/CodeGen/MachineOperand.h"
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"
  30 #include "llvm/CodeGen/TargetRegisterInfo.h"
  31 #include "llvm/IR/DebugLoc.h"
  32 #include "llvm/MC/MCRegisterInfo.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/CommandLine.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/DebugCounter.h"
  37 #include "llvm/Support/ErrorHandling.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include <cassert>
  40 #include <cstdint>
  41 #include <functional>
  42 #include <iterator>
  43 #include <limits>
  44
  45 using namespace llvm;
  46
  47 #define DEBUG_TYPE "aarch64-ldst-opt"
  48
  49 STATISTIC(NumPairCreated, "Number of load/store pair instructions generated");
  50 STATISTIC(NumPostFolded, "Number of post-index updates folded");
  51 STATISTIC(NumPreFolded, "Number of pre-index updates folded");
  52 STATISTIC(NumUnscaledPairCreated,
  53           "Number of load/store from unscaled generated");
  54 STATISTIC(NumZeroStoresPromoted, "Number of narrow zero stores promoted");
  55 STATISTIC(NumLoadsFromStoresPromoted, "Number of loads from stores promoted");
  56
  57 DEBUG_COUNTER(RegRenamingCounter, DEBUG_TYPE "-reg-renaming",
  58               "Controls which pairs are considered for renaming");
  59
  60 // The LdStLimit limits how far we search for load/store pairs.
  61 static cl::opt<unsigned> LdStLimit("aarch64-load-store-scan-limit",
  62                                    cl::init(20), cl::Hidden);
  63
  64 // The UpdateLimit limits how far we search for update instructions when we form
  65 // pre-/post-index instructions.
  66 static cl::opt<unsigned> UpdateLimit("aarch64-update-scan-limit", cl::init(100),
  67                                      cl::Hidden);
  68
  69 #define AARCH64_LOAD_STORE_OPT_NAME "AArch64 load / store optimization pass"
  70
  71 namespace {
  72
  73 using LdStPairFlags = struct LdStPairFlags {
  74   // If a matching instruction is found, MergeForward is set to true if the
  75   // merge is to remove the first instruction and replace the second with
  76   // a pair-wise insn, and false if the reverse is true.
  77   bool MergeForward = false;
  78
  79   // SExtIdx gives the index of the result of the load pair that must be
  80   // extended. The value of SExtIdx assumes that the paired load produces the
  81   // value in this order: (I, returned iterator), i.e., -1 means no value has
  82   // to be extended, 0 means I, and 1 means the returned iterator.
  83   int SExtIdx = -1;
  84
  85   // If not none, RenameReg can be used to rename the result register of the
  86   // first store in a pair. Currently this only works when merging stores
  87   // forward.
  88   Optional<MCPhysReg> RenameReg = None;
  89
  90   LdStPairFlags() = default;
  91
  92   void setMergeForward(bool V = true) { MergeForward = V; }
  93   bool getMergeForward() const { return MergeForward; }
  94
  95   void setSExtIdx(int V) { SExtIdx = V; }
  96   int getSExtIdx() const { return SExtIdx; }
  97
  98   void setRenameReg(MCPhysReg R) { RenameReg = R; }
  99   void clearRenameReg() { RenameReg = None; }
 100   Optional<MCPhysReg> getRenameReg() const { return RenameReg; }
 101 };
 102
 103 struct AArch64LoadStoreOpt : public MachineFunctionPass {
 104   static char ID;
 105
 106   AArch64LoadStoreOpt() : MachineFunctionPass(ID) {
 107     initializeAArch64LoadStoreOptPass(*PassRegistry::getPassRegistry());
 108   }
 109
 110   AliasAnalysis *AA;
 111   const AArch64InstrInfo *TII;
 112   const TargetRegisterInfo *TRI;
 113   const AArch64Subtarget *Subtarget;
 114
 115   // Track which register units have been modified and used.
 116   LiveRegUnits ModifiedRegUnits, UsedRegUnits;
 117   LiveRegUnits DefinedInBB;
 118
 119   void getAnalysisUsage(AnalysisUsage &AU) const override {
 120     AU.addRequired<AAResultsWrapperPass>();
 121     MachineFunctionPass::getAnalysisUsage(AU);
 122   }
 123
 124   // Scan the instructions looking for a load/store that can be combined
 125   // with the current instruction into a load/store pair.
 126   // Return the matching instruction if one is found, else MBB->end().
 127   MachineBasicBlock::iterator findMatchingInsn(MachineBasicBlock::iterator I,
 128                                                LdStPairFlags &Flags,
 129                                                unsigned Limit,
 130                                                bool FindNarrowMerge);
 131
 132   // Scan the instructions looking for a store that writes to the address from
 133   // which the current load instruction reads. Return true if one is found.
 134   bool findMatchingStore(MachineBasicBlock::iterator I, unsigned Limit,
 135                          MachineBasicBlock::iterator &StoreI);
 136
 137   // Merge the two instructions indicated into a wider narrow store instruction.
 138   MachineBasicBlock::iterator
 139   mergeNarrowZeroStores(MachineBasicBlock::iterator I,
 140                         MachineBasicBlock::iterator MergeMI,
 141                         const LdStPairFlags &Flags);
 142
 143   // Merge the two instructions indicated into a single pair-wise instruction.
 144   MachineBasicBlock::iterator
 145   mergePairedInsns(MachineBasicBlock::iterator I,
 146                    MachineBasicBlock::iterator Paired,
 147                    const LdStPairFlags &Flags);
 148
 149   // Promote the load that reads directly from the address stored to.
 150   MachineBasicBlock::iterator
 151   promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
 152                        MachineBasicBlock::iterator StoreI);
 153
 154   // Scan the instruction list to find a base register update that can
 155   // be combined with the current instruction (a load or store) using
 156   // pre or post indexed addressing with writeback. Scan forwards.
 157   MachineBasicBlock::iterator
 158   findMatchingUpdateInsnForward(MachineBasicBlock::iterator I,
 159                                 int UnscaledOffset, unsigned Limit);
 160
 161   // Scan the instruction list to find a base register update that can
 162   // be combined with the current instruction (a load or store) using
 163   // pre or post indexed addressing with writeback. Scan backwards.
 164   MachineBasicBlock::iterator
 165   findMatchingUpdateInsnBackward(MachineBasicBlock::iterator I, unsigned Limit);
 166
 167   // Find an instruction that updates the base register of the ld/st
 168   // instruction.
 169   bool isMatchingUpdateInsn(MachineInstr &MemMI, MachineInstr &MI,
 170                             unsigned BaseReg, int Offset);
 171
 172   // Merge a pre- or post-index base register update into a ld/st instruction.
 173   MachineBasicBlock::iterator
 174   mergeUpdateInsn(MachineBasicBlock::iterator I,
 175                   MachineBasicBlock::iterator Update, bool IsPreIdx);
 176
 177   // Find and merge zero store instructions.
 178   bool tryToMergeZeroStInst(MachineBasicBlock::iterator &MBBI);
 179
 180   // Find and pair ldr/str instructions.
 181   bool tryToPairLdStInst(MachineBasicBlock::iterator &MBBI);
 182
 183   // Find and promote load instructions which read directly from store.
 184   bool tryToPromoteLoadFromStore(MachineBasicBlock::iterator &MBBI);
 185
 186   // Find and merge a base register updates before or after a ld/st instruction.
 187   bool tryToMergeLdStUpdate(MachineBasicBlock::iterator &MBBI);
 188
 189   bool optimizeBlock(MachineBasicBlock &MBB, bool EnableNarrowZeroStOpt);
 190
 191   bool runOnMachineFunction(MachineFunction &Fn) override;
 192
 193   MachineFunctionProperties getRequiredProperties() const override {
 194     return MachineFunctionProperties().set(
 195         MachineFunctionProperties::Property::NoVRegs);
 196   }
 197
 198   StringRef getPassName() const override { return AARCH64_LOAD_STORE_OPT_NAME; }
 199 };
 200
 201 char AArch64LoadStoreOpt::ID = 0;
 202
 203 } // end anonymous namespace
 204
 205 INITIALIZE_PASS(AArch64LoadStoreOpt, "aarch64-ldst-opt",
 206                 AARCH64_LOAD_STORE_OPT_NAME, false, false)
 207
 208 static bool isNarrowStore(unsigned Opc) {
 209   switch (Opc) {
 210   default:
 211     return false;
 212   case AArch64::STRBBui:
 213   case AArch64::STURBBi:
 214   case AArch64::STRHHui:
 215   case AArch64::STURHHi:
 216     return true;
 217   }
 218 }
 219
 220 // These instruction set memory tag and either keep memory contents unchanged or
 221 // set it to zero, ignoring the address part of the source register.
 222 static bool isTagStore(const MachineInstr &MI) {
 223   switch (MI.getOpcode()) {
 224   default:
 225     return false;
 226   case AArch64::STGOffset:
 227   case AArch64::STZGOffset:
 228   case AArch64::ST2GOffset:
 229   case AArch64::STZ2GOffset:
 230     return true;
 231   }
 232 }
 233
 234 static unsigned getMatchingNonSExtOpcode(unsigned Opc,
 235                                          bool *IsValidLdStrOpc = nullptr) {
 236   if (IsValidLdStrOpc)
 237     *IsValidLdStrOpc = true;
 238   switch (Opc) {
 239   default:
 240     if (IsValidLdStrOpc)
 241       *IsValidLdStrOpc = false;
 242     return std::numeric_limits<unsigned>::max();
 243   case AArch64::STRDui:
 244   case AArch64::STURDi:
 245   case AArch64::STRQui:
 246   case AArch64::STURQi:
 247   case AArch64::STRBBui:
 248   case AArch64::STURBBi:
 249   case AArch64::STRHHui:
 250   case AArch64::STURHHi:
 251   case AArch64::STRWui:
 252   case AArch64::STURWi:
 253   case AArch64::STRXui:
 254   case AArch64::STURXi:
 255   case AArch64::LDRDui:
 256   case AArch64::LDURDi:
 257   case AArch64::LDRQui:
 258   case AArch64::LDURQi:
 259   case AArch64::LDRWui:
 260   case AArch64::LDURWi:
 261   case AArch64::LDRXui:
 262   case AArch64::LDURXi:
 263   case AArch64::STRSui:
 264   case AArch64::STURSi:
 265   case AArch64::LDRSui:
 266   case AArch64::LDURSi:
 267     return Opc;
 268   case AArch64::LDRSWui:
 269     return AArch64::LDRWui;
 270   case AArch64::LDURSWi:
 271     return AArch64::LDURWi;
 272   }
 273 }
 274
 275 static unsigned getMatchingWideOpcode(unsigned Opc) {
 276   switch (Opc) {
 277   default:
 278     llvm_unreachable("Opcode has no wide equivalent!");
 279   case AArch64::STRBBui:
 280     return AArch64::STRHHui;
 281   case AArch64::STRHHui:
 282     return AArch64::STRWui;
 283   case AArch64::STURBBi:
 284     return AArch64::STURHHi;
 285   case AArch64::STURHHi:
 286     return AArch64::STURWi;
 287   case AArch64::STURWi:
 288     return AArch64::STURXi;
 289   case AArch64::STRWui:
 290     return AArch64::STRXui;
 291   }
 292 }
 293
 294 static unsigned getMatchingPairOpcode(unsigned Opc) {
 295   switch (Opc) {
 296   default:
 297     llvm_unreachable("Opcode has no pairwise equivalent!");
 298   case AArch64::STRSui:
 299   case AArch64::STURSi:
 300     return AArch64::STPSi;
 301   case AArch64::STRDui:
 302   case AArch64::STURDi:
 303     return AArch64::STPDi;
 304   case AArch64::STRQui:
 305   case AArch64::STURQi:
 306     return AArch64::STPQi;
 307   case AArch64::STRWui:
 308   case AArch64::STURWi:
 309     return AArch64::STPWi;
 310   case AArch64::STRXui:
 311   case AArch64::STURXi:
 312     return AArch64::STPXi;
 313   case AArch64::LDRSui:
 314   case AArch64::LDURSi:
 315     return AArch64::LDPSi;
 316   case AArch64::LDRDui:
 317   case AArch64::LDURDi:
 318     return AArch64::LDPDi;
 319   case AArch64::LDRQui:
 320   case AArch64::LDURQi:
 321     return AArch64::LDPQi;
 322   case AArch64::LDRWui:
 323   case AArch64::LDURWi:
 324     return AArch64::LDPWi;
 325   case AArch64::LDRXui:
 326   case AArch64::LDURXi:
 327     return AArch64::LDPXi;
 328   case AArch64::LDRSWui:
 329   case AArch64::LDURSWi:
 330     return AArch64::LDPSWi;
 331   }
 332 }
 333
 334 static unsigned isMatchingStore(MachineInstr &LoadInst,
 335                                 MachineInstr &StoreInst) {
 336   unsigned LdOpc = LoadInst.getOpcode();
 337   unsigned StOpc = StoreInst.getOpcode();
 338   switch (LdOpc) {
 339   default:
 340     llvm_unreachable("Unsupported load instruction!");
 341   case AArch64::LDRBBui:
 342     return StOpc == AArch64::STRBBui || StOpc == AArch64::STRHHui ||
 343            StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
 344   case AArch64::LDURBBi:
 345     return StOpc == AArch64::STURBBi || StOpc == AArch64::STURHHi ||
 346            StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
 347   case AArch64::LDRHHui:
 348     return StOpc == AArch64::STRHHui || StOpc == AArch64::STRWui ||
 349            StOpc == AArch64::STRXui;
 350   case AArch64::LDURHHi:
 351     return StOpc == AArch64::STURHHi || StOpc == AArch64::STURWi ||
 352            StOpc == AArch64::STURXi;
 353   case AArch64::LDRWui:
 354     return StOpc == AArch64::STRWui || StOpc == AArch64::STRXui;
 355   case AArch64::LDURWi:
 356     return StOpc == AArch64::STURWi || StOpc == AArch64::STURXi;
 357   case AArch64::LDRXui:
 358     return StOpc == AArch64::STRXui;
 359   case AArch64::LDURXi:
 360     return StOpc == AArch64::STURXi;
 361   }
 362 }
 363
 364 static unsigned getPreIndexedOpcode(unsigned Opc) {
 365   // FIXME: We don't currently support creating pre-indexed loads/stores when
 366   // the load or store is the unscaled version.  If we decide to perform such an
 367   // optimization in the future the cases for the unscaled loads/stores will
 368   // need to be added here.
 369   switch (Opc) {
 370   default:
 371     llvm_unreachable("Opcode has no pre-indexed equivalent!");
 372   case AArch64::STRSui:
 373     return AArch64::STRSpre;
 374   case AArch64::STRDui:
 375     return AArch64::STRDpre;
 376   case AArch64::STRQui:
 377     return AArch64::STRQpre;
 378   case AArch64::STRBBui:
 379     return AArch64::STRBBpre;
 380   case AArch64::STRHHui:
 381     return AArch64::STRHHpre;
 382   case AArch64::STRWui:
 383     return AArch64::STRWpre;
 384   case AArch64::STRXui:
 385     return AArch64::STRXpre;
 386   case AArch64::LDRSui:
 387     return AArch64::LDRSpre;
 388   case AArch64::LDRDui:
 389     return AArch64::LDRDpre;
 390   case AArch64::LDRQui:
 391     return AArch64::LDRQpre;
 392   case AArch64::LDRBBui:
 393     return AArch64::LDRBBpre;
 394   case AArch64::LDRHHui:
 395     return AArch64::LDRHHpre;
 396   case AArch64::LDRWui:
 397     return AArch64::LDRWpre;
 398   case AArch64::LDRXui:
 399     return AArch64::LDRXpre;
 400   case AArch64::LDRSWui:
 401     return AArch64::LDRSWpre;
 402   case AArch64::LDPSi:
 403     return AArch64::LDPSpre;
 404   case AArch64::LDPSWi:
 405     return AArch64::LDPSWpre;
 406   case AArch64::LDPDi:
 407     return AArch64::LDPDpre;
 408   case AArch64::LDPQi:
 409     return AArch64::LDPQpre;
 410   case AArch64::LDPWi:
 411     return AArch64::LDPWpre;
 412   case AArch64::LDPXi:
 413     return AArch64::LDPXpre;
 414   case AArch64::STPSi:
 415     return AArch64::STPSpre;
 416   case AArch64::STPDi:
 417     return AArch64::STPDpre;
 418   case AArch64::STPQi:
 419     return AArch64::STPQpre;
 420   case AArch64::STPWi:
 421     return AArch64::STPWpre;
 422   case AArch64::STPXi:
 423     return AArch64::STPXpre;
 424   case AArch64::STGOffset:
 425     return AArch64::STGPreIndex;
 426   case AArch64::STZGOffset:
 427     return AArch64::STZGPreIndex;
 428   case AArch64::ST2GOffset:
 429     return AArch64::ST2GPreIndex;
 430   case AArch64::STZ2GOffset:
 431     return AArch64::STZ2GPreIndex;
 432   case AArch64::STGPi:
 433     return AArch64::STGPpre;
 434   }
 435 }
 436
 437 static unsigned getPostIndexedOpcode(unsigned Opc) {
 438   switch (Opc) {
 439   default:
 440     llvm_unreachable("Opcode has no post-indexed wise equivalent!");
 441   case AArch64::STRSui:
 442   case AArch64::STURSi:
 443     return AArch64::STRSpost;
 444   case AArch64::STRDui:
 445   case AArch64::STURDi:
 446     return AArch64::STRDpost;
 447   case AArch64::STRQui:
 448   case AArch64::STURQi:
 449     return AArch64::STRQpost;
 450   case AArch64::STRBBui:
 451     return AArch64::STRBBpost;
 452   case AArch64::STRHHui:
 453     return AArch64::STRHHpost;
 454   case AArch64::STRWui:
 455   case AArch64::STURWi:
 456     return AArch64::STRWpost;
 457   case AArch64::STRXui:
 458   case AArch64::STURXi:
 459     return AArch64::STRXpost;
 460   case AArch64::LDRSui:
 461   case AArch64::LDURSi:
 462     return AArch64::LDRSpost;
 463   case AArch64::LDRDui:
 464   case AArch64::LDURDi:
 465     return AArch64::LDRDpost;
 466   case AArch64::LDRQui:
 467   case AArch64::LDURQi:
 468     return AArch64::LDRQpost;
 469   case AArch64::LDRBBui:
 470     return AArch64::LDRBBpost;
 471   case AArch64::LDRHHui:
 472     return AArch64::LDRHHpost;
 473   case AArch64::LDRWui:
 474   case AArch64::LDURWi:
 475     return AArch64::LDRWpost;
 476   case AArch64::LDRXui:
 477   case AArch64::LDURXi:
 478     return AArch64::LDRXpost;
 479   case AArch64::LDRSWui:
 480     return AArch64::LDRSWpost;
 481   case AArch64::LDPSi:
 482     return AArch64::LDPSpost;
 483   case AArch64::LDPSWi:
 484     return AArch64::LDPSWpost;
 485   case AArch64::LDPDi:
 486     return AArch64::LDPDpost;
 487   case AArch64::LDPQi:
 488     return AArch64::LDPQpost;
 489   case AArch64::LDPWi:
 490     return AArch64::LDPWpost;
 491   case AArch64::LDPXi:
 492     return AArch64::LDPXpost;
 493   case AArch64::STPSi:
 494     return AArch64::STPSpost;
 495   case AArch64::STPDi:
 496     return AArch64::STPDpost;
 497   case AArch64::STPQi:
 498     return AArch64::STPQpost;
 499   case AArch64::STPWi:
 500     return AArch64::STPWpost;
 501   case AArch64::STPXi:
 502     return AArch64::STPXpost;
 503   case AArch64::STGOffset:
 504     return AArch64::STGPostIndex;
 505   case AArch64::STZGOffset:
 506     return AArch64::STZGPostIndex;
 507   case AArch64::ST2GOffset:
 508     return AArch64::ST2GPostIndex;
 509   case AArch64::STZ2GOffset:
 510     return AArch64::STZ2GPostIndex;
 511   case AArch64::STGPi:
 512     return AArch64::STGPpost;
 513   }
 514 }
 515
 516 static bool isPairedLdSt(const MachineInstr &MI) {
 517   switch (MI.getOpcode()) {
 518   default:
 519     return false;
 520   case AArch64::LDPSi:
 521   case AArch64::LDPSWi:
 522   case AArch64::LDPDi:
 523   case AArch64::LDPQi:
 524   case AArch64::LDPWi:
 525   case AArch64::LDPXi:
 526   case AArch64::STPSi:
 527   case AArch64::STPDi:
 528   case AArch64::STPQi:
 529   case AArch64::STPWi:
 530   case AArch64::STPXi:
 531   case AArch64::STGPi:
 532     return true;
 533   }
 534 }
 535
 536 // Returns the scale and offset range of pre/post indexed variants of MI.
 537 static void getPrePostIndexedMemOpInfo(const MachineInstr &MI, int &Scale,
 538                                        int &MinOffset, int &MaxOffset) {
 539   bool IsPaired = isPairedLdSt(MI);
 540   bool IsTagStore = isTagStore(MI);
 541   // ST*G and all paired ldst have the same scale in pre/post-indexed variants
 542   // as in the "unsigned offset" variant.
 543   // All other pre/post indexed ldst instructions are unscaled.
 544   Scale = (IsTagStore || IsPaired) ? AArch64InstrInfo::getMemScale(MI) : 1;
 545
 546   if (IsPaired) {
 547     MinOffset = -64;
 548     MaxOffset = 63;
 549   } else {
 550     MinOffset = -256;
 551     MaxOffset = 255;
 552   }
 553 }
 554
 555 static MachineOperand &getLdStRegOp(MachineInstr &MI,
 556                                     unsigned PairedRegOp = 0) {
 557   assert(PairedRegOp < 2 && "Unexpected register operand idx.");
 558   unsigned Idx = isPairedLdSt(MI) ? PairedRegOp : 0;
 559   return MI.getOperand(Idx);
 560 }
 561
 562 static const MachineOperand &getLdStBaseOp(const MachineInstr &MI) {
 563   unsigned Idx = isPairedLdSt(MI) ? 2 : 1;
 564   return MI.getOperand(Idx);
 565 }
 566
 567 static const MachineOperand &getLdStOffsetOp(const MachineInstr &MI) {
 568   unsigned Idx = isPairedLdSt(MI) ? 3 : 2;
 569   return MI.getOperand(Idx);
 570 }
 571
 572 static bool isLdOffsetInRangeOfSt(MachineInstr &LoadInst,
 573                                   MachineInstr &StoreInst,
 574                                   const AArch64InstrInfo *TII) {
 575   assert(isMatchingStore(LoadInst, StoreInst) && "Expect only matched ld/st.");
 576   int LoadSize = TII->getMemScale(LoadInst);
 577   int StoreSize = TII->getMemScale(StoreInst);
 578   int UnscaledStOffset = TII->isUnscaledLdSt(StoreInst)
 579                              ? getLdStOffsetOp(StoreInst).getImm()
 580                              : getLdStOffsetOp(StoreInst).getImm() * StoreSize;
 581   int UnscaledLdOffset = TII->isUnscaledLdSt(LoadInst)
 582                              ? getLdStOffsetOp(LoadInst).getImm()
 583                              : getLdStOffsetOp(LoadInst).getImm() * LoadSize;
 584   return (UnscaledStOffset <= UnscaledLdOffset) &&
 585          (UnscaledLdOffset + LoadSize <= (UnscaledStOffset + StoreSize));
 586 }
 587
 588 static bool isPromotableZeroStoreInst(MachineInstr &MI) {
 589   unsigned Opc = MI.getOpcode();
 590   return (Opc == AArch64::STRWui || Opc == AArch64::STURWi ||
 591           isNarrowStore(Opc)) &&
 592          getLdStRegOp(MI).getReg() == AArch64::WZR;
 593 }
 594
 595 static bool isPromotableLoadFromStore(MachineInstr &MI) {
 596   switch (MI.getOpcode()) {
 597   default:
 598     return false;
 599   // Scaled instructions.
 600   case AArch64::LDRBBui:
 601   case AArch64::LDRHHui:
 602   case AArch64::LDRWui:
 603   case AArch64::LDRXui:
 604   // Unscaled instructions.
 605   case AArch64::LDURBBi:
 606   case AArch64::LDURHHi:
 607   case AArch64::LDURWi:
 608   case AArch64::LDURXi:
 609     return true;
 610   }
 611 }
 612
 613 static bool isMergeableLdStUpdate(MachineInstr &MI) {
 614   unsigned Opc = MI.getOpcode();
 615   switch (Opc) {
 616   default:
 617     return false;
 618   // Scaled instructions.
 619   case AArch64::STRSui:
 620   case AArch64::STRDui:
 621   case AArch64::STRQui:
 622   case AArch64::STRXui:
 623   case AArch64::STRWui:
 624   case AArch64::STRHHui:
 625   case AArch64::STRBBui:
 626   case AArch64::LDRSui:
 627   case AArch64::LDRDui:
 628   case AArch64::LDRQui:
 629   case AArch64::LDRXui:
 630   case AArch64::LDRWui:
 631   case AArch64::LDRHHui:
 632   case AArch64::LDRBBui:
 633   case AArch64::STGOffset:
 634   case AArch64::STZGOffset:
 635   case AArch64::ST2GOffset:
 636   case AArch64::STZ2GOffset:
 637   case AArch64::STGPi:
 638   // Unscaled instructions.
 639   case AArch64::STURSi:
 640   case AArch64::STURDi:
 641   case AArch64::STURQi:
 642   case AArch64::STURWi:
 643   case AArch64::STURXi:
 644   case AArch64::LDURSi:
 645   case AArch64::LDURDi:
 646   case AArch64::LDURQi:
 647   case AArch64::LDURWi:
 648   case AArch64::LDURXi:
 649   // Paired instructions.
 650   case AArch64::LDPSi:
 651   case AArch64::LDPSWi:
 652   case AArch64::LDPDi:
 653   case AArch64::LDPQi:
 654   case AArch64::LDPWi:
 655   case AArch64::LDPXi:
 656   case AArch64::STPSi:
 657   case AArch64::STPDi:
 658   case AArch64::STPQi:
 659   case AArch64::STPWi:
 660   case AArch64::STPXi:
 661     // Make sure this is a reg+imm (as opposed to an address reloc).
 662     if (!getLdStOffsetOp(MI).isImm())
 663       return false;
 664
 665     return true;
 666   }
 667 }
 668
 669 MachineBasicBlock::iterator
 670 AArch64LoadStoreOpt::mergeNarrowZeroStores(MachineBasicBlock::iterator I,
 671                                            MachineBasicBlock::iterator MergeMI,
 672                                            const LdStPairFlags &Flags) {
 673   assert(isPromotableZeroStoreInst(*I) && isPromotableZeroStoreInst(*MergeMI) &&
 674          "Expected promotable zero stores.");
 675
 676   MachineBasicBlock::iterator NextI = I;
 677   ++NextI;
 678   // If NextI is the second of the two instructions to be merged, we need
 679   // to skip one further. Either way we merge will invalidate the iterator,
 680   // and we don't need to scan the new instruction, as it's a pairwise
 681   // instruction, which we're not considering for further action anyway.
 682   if (NextI == MergeMI)
 683     ++NextI;
 684
 685   unsigned Opc = I->getOpcode();
 686   bool IsScaled = !TII->isUnscaledLdSt(Opc);
 687   int OffsetStride = IsScaled ? 1 : TII->getMemScale(*I);
 688
 689   bool MergeForward = Flags.getMergeForward();
 690   // Insert our new paired instruction after whichever of the paired
 691   // instructions MergeForward indicates.
 692   MachineBasicBlock::iterator InsertionPoint = MergeForward ? MergeMI : I;
 693   // Also based on MergeForward is from where we copy the base register operand
 694   // so we get the flags compatible with the input code.
 695   const MachineOperand &BaseRegOp =
 696       MergeForward ? getLdStBaseOp(*MergeMI) : getLdStBaseOp(*I);
 697
 698   // Which register is Rt and which is Rt2 depends on the offset order.
 699   MachineInstr *RtMI;
 700   if (getLdStOffsetOp(*I).getImm() ==
 701       getLdStOffsetOp(*MergeMI).getImm() + OffsetStride)
 702     RtMI = &*MergeMI;
 703   else
 704     RtMI = &*I;
 705
 706   int OffsetImm = getLdStOffsetOp(*RtMI).getImm();
 707   // Change the scaled offset from small to large type.
 708   if (IsScaled) {
 709     assert(((OffsetImm & 1) == 0) && "Unexpected offset to merge");
 710     OffsetImm /= 2;
 711   }
 712
 713   // Construct the new instruction.
 714   DebugLoc DL = I->getDebugLoc();
 715   MachineBasicBlock *MBB = I->getParent();
 716   MachineInstrBuilder MIB;
 717   MIB = BuildMI(*MBB, InsertionPoint, DL, TII->get(getMatchingWideOpcode(Opc)))
 718             .addReg(isNarrowStore(Opc) ? AArch64::WZR : AArch64::XZR)
 719             .add(BaseRegOp)
 720             .addImm(OffsetImm)
 721             .cloneMergedMemRefs({&*I, &*MergeMI})
 722             .setMIFlags(I->mergeFlagsWith(*MergeMI));
 723   (void)MIB;
 724
 725   LLVM_DEBUG(dbgs() << "Creating wider store. Replacing instructions:\n    ");
 726   LLVM_DEBUG(I->print(dbgs()));
 727   LLVM_DEBUG(dbgs() << "    ");
 728   LLVM_DEBUG(MergeMI->print(dbgs()));
 729   LLVM_DEBUG(dbgs() << "  with instruction:\n    ");
 730   LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 731   LLVM_DEBUG(dbgs() << "\n");
 732
 733   // Erase the old instructions.
 734   I->eraseFromParent();
 735   MergeMI->eraseFromParent();
 736   return NextI;
 737 }
 738
 739 // Apply Fn to all instructions between MI and the beginning of the block, until
 740 // a def for DefReg is reached. Returns true, iff Fn returns true for all
 741 // visited instructions. Stop after visiting Limit iterations.
 742 static bool forAllMIsUntilDef(MachineInstr &MI, MCPhysReg DefReg,
 743                               const TargetRegisterInfo *TRI, unsigned Limit,
 744                               std::function<bool(MachineInstr &, bool)> &Fn) {
 745   auto MBB = MI.getParent();
 746   for (MachineBasicBlock::reverse_iterator I = MI.getReverseIterator(),
 747                                            E = MBB->rend();
 748        I != E; I++) {
 749     if (!Limit)
 750       return false;
 751     --Limit;
 752
 753     bool isDef = any_of(I->operands(), [DefReg, TRI](MachineOperand &MOP) {
 754       return MOP.isReg() && MOP.isDef() && !MOP.isDebug() && MOP.getReg() &&
 755              TRI->regsOverlap(MOP.getReg(), DefReg);
 756     });
 757     if (!Fn(*I, isDef))
 758       return false;
 759     if (isDef)
 760       break;
 761   }
 762   return true;
 763 }
 764
 765 static void updateDefinedRegisters(MachineInstr &MI, LiveRegUnits &Units,
 766                                    const TargetRegisterInfo *TRI) {
 767
 768   for (const MachineOperand &MOP : phys_regs_and_masks(MI))
 769     if (MOP.isReg() && MOP.isKill())
 770       Units.removeReg(MOP.getReg());
 771
 772   for (const MachineOperand &MOP : phys_regs_and_masks(MI))
 773     if (MOP.isReg() && !MOP.isKill())
 774       Units.addReg(MOP.getReg());
 775 }
 776
 777 MachineBasicBlock::iterator
 778 AArch64LoadStoreOpt::mergePairedInsns(MachineBasicBlock::iterator I,
 779                                       MachineBasicBlock::iterator Paired,
 780                                       const LdStPairFlags &Flags) {
 781   MachineBasicBlock::iterator NextI = I;
 782   ++NextI;
 783   // If NextI is the second of the two instructions to be merged, we need
 784   // to skip one further. Either way we merge will invalidate the iterator,
 785   // and we don't need to scan the new instruction, as it's a pairwise
 786   // instruction, which we're not considering for further action anyway.
 787   if (NextI == Paired)
 788     ++NextI;
 789
 790   int SExtIdx = Flags.getSExtIdx();
 791   unsigned Opc =
 792       SExtIdx == -1 ? I->getOpcode() : getMatchingNonSExtOpcode(I->getOpcode());
 793   bool IsUnscaled = TII->isUnscaledLdSt(Opc);
 794   int OffsetStride = IsUnscaled ? TII->getMemScale(*I) : 1;
 795
 796   bool MergeForward = Flags.getMergeForward();
 797
 798   Optional<MCPhysReg> RenameReg = Flags.getRenameReg();
 799   if (MergeForward && RenameReg) {
 800     MCRegister RegToRename = getLdStRegOp(*I).getReg();
 801     DefinedInBB.addReg(*RenameReg);
 802
 803     // Return the sub/super register for RenameReg, matching the size of
 804     // OriginalReg.
 805     auto GetMatchingSubReg = [this,
 806                               RenameReg](MCPhysReg OriginalReg) -> MCPhysReg {
 807       for (MCPhysReg SubOrSuper : TRI->sub_and_superregs_inclusive(*RenameReg))
 808         if (TRI->getMinimalPhysRegClass(OriginalReg) ==
 809             TRI->getMinimalPhysRegClass(SubOrSuper))
 810           return SubOrSuper;
 811       llvm_unreachable("Should have found matching sub or super register!");
 812     };
 813
 814     std::function<bool(MachineInstr &, bool)> UpdateMIs =
 815         [this, RegToRename, GetMatchingSubReg](MachineInstr &MI, bool IsDef) {
 816           if (IsDef) {
 817             bool SeenDef = false;
 818             for (auto &MOP : MI.operands()) {
 819               // Rename the first explicit definition and all implicit
 820               // definitions matching RegToRename.
 821               if (MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
 822                   (!SeenDef || (MOP.isDef() && MOP.isImplicit())) &&
 823                   TRI->regsOverlap(MOP.getReg(), RegToRename)) {
 824                 assert((MOP.isImplicit() ||
 825                         (MOP.isRenamable() && !MOP.isEarlyClobber())) &&
 826                        "Need renamable operands");
 827                 MOP.setReg(GetMatchingSubReg(MOP.getReg()));
 828                 SeenDef = true;
 829               }
 830             }
 831           } else {
 832             for (auto &MOP : MI.operands()) {
 833               if (MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
 834                   TRI->regsOverlap(MOP.getReg(), RegToRename)) {
 835                 assert((MOP.isImplicit() ||
 836                         (MOP.isRenamable() && !MOP.isEarlyClobber())) &&
 837                            "Need renamable operands");
 838                 MOP.setReg(GetMatchingSubReg(MOP.getReg()));
 839               }
 840             }
 841           }
 842           LLVM_DEBUG(dbgs() << "Renamed " << MI << "\n");
 843           return true;
 844         };
 845     forAllMIsUntilDef(*I, RegToRename, TRI, LdStLimit, UpdateMIs);
 846
 847 #if !defined(NDEBUG)
 848     // Make sure the register used for renaming is not used between the paired
 849     // instructions. That would trash the content before the new paired
 850     // instruction.
 851     for (auto &MI :
 852          iterator_range<MachineInstrBundleIterator<llvm::MachineInstr>>(
 853              std::next(I), std::next(Paired)))
 854       assert(all_of(MI.operands(),
 855                     [this, &RenameReg](const MachineOperand &MOP) {
 856                       return !MOP.isReg() || MOP.isDebug() || !MOP.getReg() ||
 857                              !TRI->regsOverlap(MOP.getReg(), *RenameReg);
 858                     }) &&
 859              "Rename register used between paired instruction, trashing the "
 860              "content");
 861 #endif
 862   }
 863
 864   // Insert our new paired instruction after whichever of the paired
 865   // instructions MergeForward indicates.
 866   MachineBasicBlock::iterator InsertionPoint = MergeForward ? Paired : I;
 867   // Also based on MergeForward is from where we copy the base register operand
 868   // so we get the flags compatible with the input code.
 869   const MachineOperand &BaseRegOp =
 870       MergeForward ? getLdStBaseOp(*Paired) : getLdStBaseOp(*I);
 871
 872   int Offset = getLdStOffsetOp(*I).getImm();
 873   int PairedOffset = getLdStOffsetOp(*Paired).getImm();
 874   bool PairedIsUnscaled = TII->isUnscaledLdSt(Paired->getOpcode());
 875   if (IsUnscaled != PairedIsUnscaled) {
 876     // We're trying to pair instructions that differ in how they are scaled.  If
 877     // I is scaled then scale the offset of Paired accordingly.  Otherwise, do
 878     // the opposite (i.e., make Paired's offset unscaled).
 879     int MemSize = TII->getMemScale(*Paired);
 880     if (PairedIsUnscaled) {
 881       // If the unscaled offset isn't a multiple of the MemSize, we can't
 882       // pair the operations together.
 883       assert(!(PairedOffset % TII->getMemScale(*Paired)) &&
 884              "Offset should be a multiple of the stride!");
 885       PairedOffset /= MemSize;
 886     } else {
 887       PairedOffset *= MemSize;
 888     }
 889   }
 890
 891   // Which register is Rt and which is Rt2 depends on the offset order.
 892   MachineInstr *RtMI, *Rt2MI;
 893   if (Offset == PairedOffset + OffsetStride) {
 894     RtMI = &*Paired;
 895     Rt2MI = &*I;
 896     // Here we swapped the assumption made for SExtIdx.
 897     // I.e., we turn ldp I, Paired into ldp Paired, I.
 898     // Update the index accordingly.
 899     if (SExtIdx != -1)
 900       SExtIdx = (SExtIdx + 1) % 2;
 901   } else {
 902     RtMI = &*I;
 903     Rt2MI = &*Paired;
 904   }
 905   int OffsetImm = getLdStOffsetOp(*RtMI).getImm();
 906   // Scale the immediate offset, if necessary.
 907   if (TII->isUnscaledLdSt(RtMI->getOpcode())) {
 908     assert(!(OffsetImm % TII->getMemScale(*RtMI)) &&
 909            "Unscaled offset cannot be scaled.");
 910     OffsetImm /= TII->getMemScale(*RtMI);
 911   }
 912
 913   // Construct the new instruction.
 914   MachineInstrBuilder MIB;
 915   DebugLoc DL = I->getDebugLoc();
 916   MachineBasicBlock *MBB = I->getParent();
 917   MachineOperand RegOp0 = getLdStRegOp(*RtMI);
 918   MachineOperand RegOp1 = getLdStRegOp(*Rt2MI);
 919   // Kill flags may become invalid when moving stores for pairing.
 920   if (RegOp0.isUse()) {
 921     if (!MergeForward) {
 922       // Clear kill flags on store if moving upwards. Example:
 923       //   STRWui %w0, ...
 924       //   USE %w1
 925       //   STRWui kill %w1  ; need to clear kill flag when moving STRWui upwards
 926       RegOp0.setIsKill(false);
 927       RegOp1.setIsKill(false);
 928     } else {
 929       // Clear kill flags of the first stores register. Example:
 930       //   STRWui %w1, ...
 931       //   USE kill %w1   ; need to clear kill flag when moving STRWui downwards
 932       //   STRW %w0
 933       Register Reg = getLdStRegOp(*I).getReg();
 934       for (MachineInstr &MI : make_range(std::next(I), Paired))
 935         MI.clearRegisterKills(Reg, TRI);
 936     }
 937   }
 938   MIB = BuildMI(*MBB, InsertionPoint, DL, TII->get(getMatchingPairOpcode(Opc)))
 939             .add(RegOp0)
 940             .add(RegOp1)
 941             .add(BaseRegOp)
 942             .addImm(OffsetImm)
 943             .cloneMergedMemRefs({&*I, &*Paired})
 944             .setMIFlags(I->mergeFlagsWith(*Paired));
 945
 946   (void)MIB;
 947
 948   LLVM_DEBUG(
 949       dbgs() << "Creating pair load/store. Replacing instructions:\n    ");
 950   LLVM_DEBUG(I->print(dbgs()));
 951   LLVM_DEBUG(dbgs() << "    ");
 952   LLVM_DEBUG(Paired->print(dbgs()));
 953   LLVM_DEBUG(dbgs() << "  with instruction:\n    ");
 954   if (SExtIdx != -1) {
 955     // Generate the sign extension for the proper result of the ldp.
 956     // I.e., with X1, that would be:
 957     // %w1 = KILL %w1, implicit-def %x1
 958     // %x1 = SBFMXri killed %x1, 0, 31
 959     MachineOperand &DstMO = MIB->getOperand(SExtIdx);
 960     // Right now, DstMO has the extended register, since it comes from an
 961     // extended opcode.
 962     Register DstRegX = DstMO.getReg();
 963     // Get the W variant of that register.
 964     Register DstRegW = TRI->getSubReg(DstRegX, AArch64::sub_32);
 965     // Update the result of LDP to use the W instead of the X variant.
 966     DstMO.setReg(DstRegW);
 967     LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 968     LLVM_DEBUG(dbgs() << "\n");
 969     // Make the machine verifier happy by providing a definition for
 970     // the X register.
 971     // Insert this definition right after the generated LDP, i.e., before
 972     // InsertionPoint.
 973     MachineInstrBuilder MIBKill =
 974         BuildMI(*MBB, InsertionPoint, DL, TII->get(TargetOpcode::KILL), DstRegW)
 975             .addReg(DstRegW)
 976             .addReg(DstRegX, RegState::Define);
 977     MIBKill->getOperand(2).setImplicit();
 978     // Create the sign extension.
 979     MachineInstrBuilder MIBSXTW =
 980         BuildMI(*MBB, InsertionPoint, DL, TII->get(AArch64::SBFMXri), DstRegX)
 981             .addReg(DstRegX)
 982             .addImm(0)
 983             .addImm(31);
 984     (void)MIBSXTW;
 985     LLVM_DEBUG(dbgs() << "  Extend operand:\n    ");
 986     LLVM_DEBUG(((MachineInstr *)MIBSXTW)->print(dbgs()));
 987   } else {
 988     LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
 989   }
 990   LLVM_DEBUG(dbgs() << "\n");
 991
 992   if (MergeForward)
 993     for (const MachineOperand &MOP : phys_regs_and_masks(*I))
 994       if (MOP.isReg() && MOP.isKill())
 995         DefinedInBB.addReg(MOP.getReg());
 996
 997   // Erase the old instructions.
 998   I->eraseFromParent();
 999   Paired->eraseFromParent();
1000
1001   return NextI;
1002 }
1003
1004 MachineBasicBlock::iterator
1005 AArch64LoadStoreOpt::promoteLoadFromStore(MachineBasicBlock::iterator LoadI,
1006                                           MachineBasicBlock::iterator StoreI) {
1007   MachineBasicBlock::iterator NextI = LoadI;
1008   ++NextI;
1009
1010   int LoadSize = TII->getMemScale(*LoadI);
1011   int StoreSize = TII->getMemScale(*StoreI);
1012   Register LdRt = getLdStRegOp(*LoadI).getReg();
1013   const MachineOperand &StMO = getLdStRegOp(*StoreI);
1014   Register StRt = getLdStRegOp(*StoreI).getReg();
1015   bool IsStoreXReg = TRI->getRegClass(AArch64::GPR64RegClassID)->contains(StRt);
1016
1017   assert((IsStoreXReg ||
1018           TRI->getRegClass(AArch64::GPR32RegClassID)->contains(StRt)) &&
1019          "Unexpected RegClass");
1020
1021   MachineInstr *BitExtMI;
1022   if (LoadSize == StoreSize && (LoadSize == 4 || LoadSize == 8)) {
1023     // Remove the load, if the destination register of the loads is the same
1024     // register for stored value.
1025     if (StRt == LdRt && LoadSize == 8) {
1026       for (MachineInstr &MI : make_range(StoreI->getIterator(),
1027                                          LoadI->getIterator())) {
1028         if (MI.killsRegister(StRt, TRI)) {
1029           MI.clearRegisterKills(StRt, TRI);
1030           break;
1031         }
1032       }
1033       LLVM_DEBUG(dbgs() << "Remove load instruction:\n    ");
1034       LLVM_DEBUG(LoadI->print(dbgs()));
1035       LLVM_DEBUG(dbgs() << "\n");
1036       LoadI->eraseFromParent();
1037       return NextI;
1038     }
1039     // Replace the load with a mov if the load and store are in the same size.
1040     BitExtMI =
1041         BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
1042                 TII->get(IsStoreXReg ? AArch64::ORRXrs : AArch64::ORRWrs), LdRt)
1043             .addReg(IsStoreXReg ? AArch64::XZR : AArch64::WZR)
1044             .add(StMO)
1045             .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, 0))
1046             .setMIFlags(LoadI->getFlags());
1047   } else {
1048     // FIXME: Currently we disable this transformation in big-endian targets as
1049     // performance and correctness are verified only in little-endian.
1050     if (!Subtarget->isLittleEndian())
1051       return NextI;
1052     bool IsUnscaled = TII->isUnscaledLdSt(*LoadI);
1053     assert(IsUnscaled == TII->isUnscaledLdSt(*StoreI) &&
1054            "Unsupported ld/st match");
1055     assert(LoadSize <= StoreSize && "Invalid load size");
1056     int UnscaledLdOffset = IsUnscaled
1057                                ? getLdStOffsetOp(*LoadI).getImm()
1058                                : getLdStOffsetOp(*LoadI).getImm() * LoadSize;
1059     int UnscaledStOffset = IsUnscaled
1060                                ? getLdStOffsetOp(*StoreI).getImm()
1061                                : getLdStOffsetOp(*StoreI).getImm() * StoreSize;
1062     int Width = LoadSize * 8;
1063     unsigned DestReg =
1064         IsStoreXReg ? Register(TRI->getMatchingSuperReg(
1065                           LdRt, AArch64::sub_32, &AArch64::GPR64RegClass))
1066                     : LdRt;
1067
1068     assert((UnscaledLdOffset >= UnscaledStOffset &&
1069             (UnscaledLdOffset + LoadSize) <= UnscaledStOffset + StoreSize) &&
1070            "Invalid offset");
1071
1072     int Immr = 8 * (UnscaledLdOffset - UnscaledStOffset);
1073     int Imms = Immr + Width - 1;
1074     if (UnscaledLdOffset == UnscaledStOffset) {
1075       uint32_t AndMaskEncoded = ((IsStoreXReg ? 1 : 0) << 12) // N
1076                                 | ((Immr) << 6)               // immr
1077                                 | ((Imms) << 0)               // imms
1078           ;
1079
1080       BitExtMI =
1081           BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
1082                   TII->get(IsStoreXReg ? AArch64::ANDXri : AArch64::ANDWri),
1083                   DestReg)
1084               .add(StMO)
1085               .addImm(AndMaskEncoded)
1086               .setMIFlags(LoadI->getFlags());
1087     } else {
1088       BitExtMI =
1089           BuildMI(*LoadI->getParent(), LoadI, LoadI->getDebugLoc(),
1090                   TII->get(IsStoreXReg ? AArch64::UBFMXri : AArch64::UBFMWri),
1091                   DestReg)
1092               .add(StMO)
1093               .addImm(Immr)
1094               .addImm(Imms)
1095               .setMIFlags(LoadI->getFlags());
1096     }
1097   }
1098
1099   // Clear kill flags between store and load.
1100   for (MachineInstr &MI : make_range(StoreI->getIterator(),
1101                                      BitExtMI->getIterator()))
1102     if (MI.killsRegister(StRt, TRI)) {
1103       MI.clearRegisterKills(StRt, TRI);
1104       break;
1105     }
1106
1107   LLVM_DEBUG(dbgs() << "Promoting load by replacing :\n    ");
1108   LLVM_DEBUG(StoreI->print(dbgs()));
1109   LLVM_DEBUG(dbgs() << "    ");
1110   LLVM_DEBUG(LoadI->print(dbgs()));
1111   LLVM_DEBUG(dbgs() << "  with instructions:\n    ");
1112   LLVM_DEBUG(StoreI->print(dbgs()));
1113   LLVM_DEBUG(dbgs() << "    ");
1114   LLVM_DEBUG((BitExtMI)->print(dbgs()));
1115   LLVM_DEBUG(dbgs() << "\n");
1116
1117   // Erase the old instructions.
1118   LoadI->eraseFromParent();
1119   return NextI;
1120 }
1121
1122 static bool inBoundsForPair(bool IsUnscaled, int Offset, int OffsetStride) {
1123   // Convert the byte-offset used by unscaled into an "element" offset used
1124   // by the scaled pair load/store instructions.
1125   if (IsUnscaled) {
1126     // If the byte-offset isn't a multiple of the stride, there's no point
1127     // trying to match it.
1128     if (Offset % OffsetStride)
1129       return false;
1130     Offset /= OffsetStride;
1131   }
1132   return Offset <= 63 && Offset >= -64;
1133 }
1134
1135 // Do alignment, specialized to power of 2 and for signed ints,
1136 // avoiding having to do a C-style cast from uint_64t to int when
1137 // using alignTo from include/llvm/Support/MathExtras.h.
1138 // FIXME: Move this function to include/MathExtras.h?
1139 static int alignTo(int Num, int PowOf2) {
1140   return (Num + PowOf2 - 1) & ~(PowOf2 - 1);
1141 }
1142
1143 static bool mayAlias(MachineInstr &MIa, MachineInstr &MIb,
1144                      AliasAnalysis *AA) {
1145   // One of the instructions must modify memory.
1146   if (!MIa.mayStore() && !MIb.mayStore())
1147     return false;
1148
1149   // Both instructions must be memory operations.
1150   if (!MIa.mayLoadOrStore() && !MIb.mayLoadOrStore())
1151     return false;
1152
1153   return MIa.mayAlias(AA, MIb, /*UseTBAA*/false);
1154 }
1155
1156 static bool mayAlias(MachineInstr &MIa,
1157                      SmallVectorImpl<MachineInstr *> &MemInsns,
1158                      AliasAnalysis *AA) {
1159   for (MachineInstr *MIb : MemInsns)
1160     if (mayAlias(MIa, *MIb, AA))
1161       return true;
1162
1163   return false;
1164 }
1165
1166 bool AArch64LoadStoreOpt::findMatchingStore(
1167     MachineBasicBlock::iterator I, unsigned Limit,
1168     MachineBasicBlock::iterator &StoreI) {
1169   MachineBasicBlock::iterator B = I->getParent()->begin();
1170   MachineBasicBlock::iterator MBBI = I;
1171   MachineInstr &LoadMI = *I;
1172   Register BaseReg = getLdStBaseOp(LoadMI).getReg();
1173
1174   // If the load is the first instruction in the block, there's obviously
1175   // not any matching store.
1176   if (MBBI == B)
1177     return false;
1178
1179   // Track which register units have been modified and used between the first
1180   // insn and the second insn.
1181   ModifiedRegUnits.clear();
1182   UsedRegUnits.clear();
1183
1184   unsigned Count = 0;
1185   do {
1186     --MBBI;
1187     MachineInstr &MI = *MBBI;
1188
1189     // Don't count transient instructions towards the search limit since there
1190     // may be different numbers of them if e.g. debug information is present.
1191     if (!MI.isTransient())
1192       ++Count;
1193
1194     // If the load instruction reads directly from the address to which the
1195     // store instruction writes and the stored value is not modified, we can
1196     // promote the load. Since we do not handle stores with pre-/post-index,
1197     // it's unnecessary to check if BaseReg is modified by the store itself.
1198     if (MI.mayStore() && isMatchingStore(LoadMI, MI) &&
1199         BaseReg == getLdStBaseOp(MI).getReg() &&
1200         isLdOffsetInRangeOfSt(LoadMI, MI, TII) &&
1201         ModifiedRegUnits.available(getLdStRegOp(MI).getReg())) {
1202       StoreI = MBBI;
1203       return true;
1204     }
1205
1206     if (MI.isCall())
1207       return false;
1208
1209     // Update modified / uses register units.
1210     LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1211
1212     // Otherwise, if the base register is modified, we have no match, so
1213     // return early.
1214     if (!ModifiedRegUnits.available(BaseReg))
1215       return false;
1216
1217     // If we encounter a store aliased with the load, return early.
1218     if (MI.mayStore() && mayAlias(LoadMI, MI, AA))
1219       return false;
1220   } while (MBBI != B && Count < Limit);
1221   return false;
1222 }
1223
1224 // Returns true if FirstMI and MI are candidates for merging or pairing.
1225 // Otherwise, returns false.
1226 static bool areCandidatesToMergeOrPair(MachineInstr &FirstMI, MachineInstr &MI,
1227                                        LdStPairFlags &Flags,
1228                                        const AArch64InstrInfo *TII) {
1229   // If this is volatile or if pairing is suppressed, not a candidate.
1230   if (MI.hasOrderedMemoryRef() || TII->isLdStPairSuppressed(MI))
1231     return false;
1232
1233   // We should have already checked FirstMI for pair suppression and volatility.
1234   assert(!FirstMI.hasOrderedMemoryRef() &&
1235          !TII->isLdStPairSuppressed(FirstMI) &&
1236          "FirstMI shouldn't get here if either of these checks are true.");
1237
1238   unsigned OpcA = FirstMI.getOpcode();
1239   unsigned OpcB = MI.getOpcode();
1240
1241   // Opcodes match: nothing more to check.
1242   if (OpcA == OpcB)
1243     return true;
1244
1245   // Try to match a sign-extended load/store with a zero-extended load/store.
1246   bool IsValidLdStrOpc, PairIsValidLdStrOpc;
1247   unsigned NonSExtOpc = getMatchingNonSExtOpcode(OpcA, &IsValidLdStrOpc);
1248   assert(IsValidLdStrOpc &&
1249          "Given Opc should be a Load or Store with an immediate");
1250   // OpcA will be the first instruction in the pair.
1251   if (NonSExtOpc == getMatchingNonSExtOpcode(OpcB, &PairIsValidLdStrOpc)) {
1252     Flags.setSExtIdx(NonSExtOpc == (unsigned)OpcA ? 1 : 0);
1253     return true;
1254   }
1255
1256   // If the second instruction isn't even a mergable/pairable load/store, bail
1257   // out.
1258   if (!PairIsValidLdStrOpc)
1259     return false;
1260
1261   // FIXME: We don't support merging narrow stores with mixed scaled/unscaled
1262   // offsets.
1263   if (isNarrowStore(OpcA) || isNarrowStore(OpcB))
1264     return false;
1265
1266   // Try to match an unscaled load/store with a scaled load/store.
1267   return TII->isUnscaledLdSt(OpcA) != TII->isUnscaledLdSt(OpcB) &&
1268          getMatchingPairOpcode(OpcA) == getMatchingPairOpcode(OpcB);
1269
1270   // FIXME: Can we also match a mixed sext/zext unscaled/scaled pair?
1271 }
1272
1273 static bool
1274 canRenameUpToDef(MachineInstr &FirstMI, LiveRegUnits &UsedInBetween,
1275                  SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1276                  const TargetRegisterInfo *TRI) {
1277   if (!FirstMI.mayStore())
1278     return false;
1279
1280   // Check if we can find an unused register which we can use to rename
1281   // the register used by the first load/store.
1282   auto *RegClass = TRI->getMinimalPhysRegClass(getLdStRegOp(FirstMI).getReg());
1283   MachineFunction &MF = *FirstMI.getParent()->getParent();
1284   if (!RegClass || !MF.getRegInfo().tracksLiveness())
1285     return false;
1286
1287   auto RegToRename = getLdStRegOp(FirstMI).getReg();
1288   // For now, we only rename if the store operand gets killed at the store.
1289   if (!getLdStRegOp(FirstMI).isKill() &&
1290       !any_of(FirstMI.operands(),
1291               [TRI, RegToRename](const MachineOperand &MOP) {
1292                 return MOP.isReg() && !MOP.isDebug() && MOP.getReg() &&
1293                        MOP.isImplicit() && MOP.isKill() &&
1294                        TRI->regsOverlap(RegToRename, MOP.getReg());
1295               })) {
1296     LLVM_DEBUG(dbgs() << "  Operand not killed at " << FirstMI << "\n");
1297     return false;
1298   }
1299   auto canRenameMOP = [](const MachineOperand &MOP) {
1300     return MOP.isImplicit() ||
1301            (MOP.isRenamable() && !MOP.isEarlyClobber() && !MOP.isTied());
1302   };
1303
1304   bool FoundDef = false;
1305
1306   // For each instruction between FirstMI and the previous def for RegToRename,
1307   // we
1308   // * check if we can rename RegToRename in this instruction
1309   // * collect the registers used and required register classes for RegToRename.
1310   std::function<bool(MachineInstr &, bool)> CheckMIs = [&](MachineInstr &MI,
1311                                                            bool IsDef) {
1312     LLVM_DEBUG(dbgs() << "Checking " << MI << "\n");
1313     // Currently we do not try to rename across frame-setup instructions.
1314     if (MI.getFlag(MachineInstr::FrameSetup)) {
1315       LLVM_DEBUG(dbgs() << "  Cannot rename framesetup instructions currently ("
1316                         << MI << ")\n");
1317       return false;
1318     }
1319
1320     UsedInBetween.accumulate(MI);
1321
1322     // For a definition, check that we can rename the definition and exit the
1323     // loop.
1324     FoundDef = IsDef;
1325
1326     // For defs, check if we can rename the first def of RegToRename.
1327     if (FoundDef) {
1328       // For some pseudo instructions, we might not generate code in the end
1329       // (e.g. KILL) and we would end up without a correct def for the rename
1330       // register.
1331       // TODO: This might be overly conservative and we could handle those cases
1332       // in multiple ways:
1333       //       1. Insert an extra copy, to materialize the def.
1334       //       2. Skip pseudo-defs until we find an non-pseudo def.
1335       if (MI.isPseudo()) {
1336         LLVM_DEBUG(dbgs() << "  Cannot rename pseudo instruction " << MI
1337                           << "\n");
1338         return false;
1339       }
1340
1341       for (auto &MOP : MI.operands()) {
1342         if (!MOP.isReg() || !MOP.isDef() || MOP.isDebug() || !MOP.getReg() ||
1343             !TRI->regsOverlap(MOP.getReg(), RegToRename))
1344           continue;
1345         if (!canRenameMOP(MOP)) {
1346           LLVM_DEBUG(dbgs()
1347                      << "  Cannot rename " << MOP << " in " << MI << "\n");
1348           return false;
1349         }
1350         RequiredClasses.insert(TRI->getMinimalPhysRegClass(MOP.getReg()));
1351       }
1352       return true;
1353     } else {
1354       for (auto &MOP : MI.operands()) {
1355         if (!MOP.isReg() || MOP.isDebug() || !MOP.getReg() ||
1356             !TRI->regsOverlap(MOP.getReg(), RegToRename))
1357           continue;
1358
1359         if (!canRenameMOP(MOP)) {
1360           LLVM_DEBUG(dbgs()
1361                      << "  Cannot rename " << MOP << " in " << MI << "\n");
1362           return false;
1363         }
1364         RequiredClasses.insert(TRI->getMinimalPhysRegClass(MOP.getReg()));
1365       }
1366     }
1367     return true;
1368   };
1369
1370   if (!forAllMIsUntilDef(FirstMI, RegToRename, TRI, LdStLimit, CheckMIs))
1371     return false;
1372
1373   if (!FoundDef) {
1374     LLVM_DEBUG(dbgs() << "  Did not find definition for register in BB\n");
1375     return false;
1376   }
1377   return true;
1378 }
1379
1380 // Check if we can find a physical register for renaming. This register must:
1381 // * not be defined up to FirstMI (checking DefinedInBB)
1382 // * not used between the MI and the defining instruction of the register to
1383 //   rename (checked using UsedInBetween).
1384 // * is available in all used register classes (checked using RequiredClasses).
1385 static Optional<MCPhysReg> tryToFindRegisterToRename(
1386     MachineInstr &FirstMI, MachineInstr &MI, LiveRegUnits &DefinedInBB,
1387     LiveRegUnits &UsedInBetween,
1388     SmallPtrSetImpl<const TargetRegisterClass *> &RequiredClasses,
1389     const TargetRegisterInfo *TRI) {
1390   auto &MF = *FirstMI.getParent()->getParent();
1391   MachineRegisterInfo &RegInfo = MF.getRegInfo();
1392
1393   // Checks if any sub- or super-register of PR is callee saved.
1394   auto AnySubOrSuperRegCalleePreserved = [&MF, TRI](MCPhysReg PR) {
1395     return any_of(TRI->sub_and_superregs_inclusive(PR),
1396                   [&MF, TRI](MCPhysReg SubOrSuper) {
1397                     return TRI->isCalleeSavedPhysReg(SubOrSuper, MF);
1398                   });
1399   };
1400
1401   // Check if PR or one of its sub- or super-registers can be used for all
1402   // required register classes.
1403   auto CanBeUsedForAllClasses = [&RequiredClasses, TRI](MCPhysReg PR) {
1404     return all_of(RequiredClasses, [PR, TRI](const TargetRegisterClass *C) {
1405       return any_of(TRI->sub_and_superregs_inclusive(PR),
1406                     [C, TRI](MCPhysReg SubOrSuper) {
1407                       return C == TRI->getMinimalPhysRegClass(SubOrSuper);
1408                     });
1409     });
1410   };
1411
1412   auto *RegClass = TRI->getMinimalPhysRegClass(getLdStRegOp(FirstMI).getReg());
1413   for (const MCPhysReg &PR : *RegClass) {
1414     if (DefinedInBB.available(PR) && UsedInBetween.available(PR) &&
1415         !RegInfo.isReserved(PR) && !AnySubOrSuperRegCalleePreserved(PR) &&
1416         CanBeUsedForAllClasses(PR)) {
1417       DefinedInBB.addReg(PR);
1418       LLVM_DEBUG(dbgs() << "Found rename register " << printReg(PR, TRI)
1419                         << "\n");
1420       return {PR};
1421     }
1422   }
1423   LLVM_DEBUG(dbgs() << "No rename register found from "
1424                     << TRI->getRegClassName(RegClass) << "\n");
1425   return None;
1426 }
1427
1428 /// Scan the instructions looking for a load/store that can be combined with the
1429 /// current instruction into a wider equivalent or a load/store pair.
1430 MachineBasicBlock::iterator
1431 AArch64LoadStoreOpt::findMatchingInsn(MachineBasicBlock::iterator I,
1432                                       LdStPairFlags &Flags, unsigned Limit,
1433                                       bool FindNarrowMerge) {
1434   MachineBasicBlock::iterator E = I->getParent()->end();
1435   MachineBasicBlock::iterator MBBI = I;
1436   MachineBasicBlock::iterator MBBIWithRenameReg;
1437   MachineInstr &FirstMI = *I;
1438   ++MBBI;
1439
1440   bool MayLoad = FirstMI.mayLoad();
1441   bool IsUnscaled = TII->isUnscaledLdSt(FirstMI);
1442   Register Reg = getLdStRegOp(FirstMI).getReg();
1443   Register BaseReg = getLdStBaseOp(FirstMI).getReg();
1444   int Offset = getLdStOffsetOp(FirstMI).getImm();
1445   int OffsetStride = IsUnscaled ? TII->getMemScale(FirstMI) : 1;
1446   bool IsPromotableZeroStore = isPromotableZeroStoreInst(FirstMI);
1447
1448   Optional<bool> MaybeCanRename = None;
1449   SmallPtrSet<const TargetRegisterClass *, 5> RequiredClasses;
1450   LiveRegUnits UsedInBetween;
1451   UsedInBetween.init(*TRI);
1452
1453   Flags.clearRenameReg();
1454
1455   // Track which register units have been modified and used between the first
1456   // insn (inclusive) and the second insn.
1457   ModifiedRegUnits.clear();
1458   UsedRegUnits.clear();
1459
1460   // Remember any instructions that read/write memory between FirstMI and MI.
1461   SmallVector<MachineInstr *, 4> MemInsns;
1462
1463   for (unsigned Count = 0; MBBI != E && Count < Limit; ++MBBI) {
1464     MachineInstr &MI = *MBBI;
1465
1466     UsedInBetween.accumulate(MI);
1467
1468     // Don't count transient instructions towards the search limit since there
1469     // may be different numbers of them if e.g. debug information is present.
1470     if (!MI.isTransient())
1471       ++Count;
1472
1473     Flags.setSExtIdx(-1);
1474     if (areCandidatesToMergeOrPair(FirstMI, MI, Flags, TII) &&
1475         getLdStOffsetOp(MI).isImm()) {
1476       assert(MI.mayLoadOrStore() && "Expected memory operation.");
1477       // If we've found another instruction with the same opcode, check to see
1478       // if the base and offset are compatible with our starting instruction.
1479       // These instructions all have scaled immediate operands, so we just
1480       // check for +1/-1. Make sure to check the new instruction offset is
1481       // actually an immediate and not a symbolic reference destined for
1482       // a relocation.
1483       Register MIBaseReg = getLdStBaseOp(MI).getReg();
1484       int MIOffset = getLdStOffsetOp(MI).getImm();
1485       bool MIIsUnscaled = TII->isUnscaledLdSt(MI);
1486       if (IsUnscaled != MIIsUnscaled) {
1487         // We're trying to pair instructions that differ in how they are scaled.
1488         // If FirstMI is scaled then scale the offset of MI accordingly.
1489         // Otherwise, do the opposite (i.e., make MI's offset unscaled).
1490         int MemSize = TII->getMemScale(MI);
1491         if (MIIsUnscaled) {
1492           // If the unscaled offset isn't a multiple of the MemSize, we can't
1493           // pair the operations together: bail and keep looking.
1494           if (MIOffset % MemSize) {
1495             LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1496                                               UsedRegUnits, TRI);
1497             MemInsns.push_back(&MI);
1498             continue;
1499           }
1500           MIOffset /= MemSize;
1501         } else {
1502           MIOffset *= MemSize;
1503         }
1504       }
1505
1506       if (BaseReg == MIBaseReg && ((Offset == MIOffset + OffsetStride) ||
1507                                    (Offset + OffsetStride == MIOffset))) {
1508         int MinOffset = Offset < MIOffset ? Offset : MIOffset;
1509         if (FindNarrowMerge) {
1510           // If the alignment requirements of the scaled wide load/store
1511           // instruction can't express the offset of the scaled narrow input,
1512           // bail and keep looking. For promotable zero stores, allow only when
1513           // the stored value is the same (i.e., WZR).
1514           if ((!IsUnscaled && alignTo(MinOffset, 2) != MinOffset) ||
1515               (IsPromotableZeroStore && Reg != getLdStRegOp(MI).getReg())) {
1516             LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1517                                               UsedRegUnits, TRI);
1518             MemInsns.push_back(&MI);
1519             continue;
1520           }
1521         } else {
1522           // Pairwise instructions have a 7-bit signed offset field. Single
1523           // insns have a 12-bit unsigned offset field.  If the resultant
1524           // immediate offset of merging these instructions is out of range for
1525           // a pairwise instruction, bail and keep looking.
1526           if (!inBoundsForPair(IsUnscaled, MinOffset, OffsetStride)) {
1527             LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1528                                               UsedRegUnits, TRI);
1529             MemInsns.push_back(&MI);
1530             continue;
1531           }
1532           // If the alignment requirements of the paired (scaled) instruction
1533           // can't express the offset of the unscaled input, bail and keep
1534           // looking.
1535           if (IsUnscaled && (alignTo(MinOffset, OffsetStride) != MinOffset)) {
1536             LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits,
1537                                               UsedRegUnits, TRI);
1538             MemInsns.push_back(&MI);
1539             continue;
1540           }
1541         }
1542         // If the destination register of the loads is the same register, bail
1543         // and keep looking. A load-pair instruction with both destination
1544         // registers the same is UNPREDICTABLE and will result in an exception.
1545         if (MayLoad && Reg == getLdStRegOp(MI).getReg()) {
1546           LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits,
1547                                             TRI);
1548           MemInsns.push_back(&MI);
1549           continue;
1550         }
1551
1552         // If the Rt of the second instruction was not modified or used between
1553         // the two instructions and none of the instructions between the second
1554         // and first alias with the second, we can combine the second into the
1555         // first.
1556         if (ModifiedRegUnits.available(getLdStRegOp(MI).getReg()) &&
1557             !(MI.mayLoad() &&
1558               !UsedRegUnits.available(getLdStRegOp(MI).getReg())) &&
1559             !mayAlias(MI, MemInsns, AA)) {
1560
1561           Flags.setMergeForward(false);
1562           Flags.clearRenameReg();
1563           return MBBI;
1564         }
1565
1566         // Likewise, if the Rt of the first instruction is not modified or used
1567         // between the two instructions and none of the instructions between the
1568         // first and the second alias with the first, we can combine the first
1569         // into the second.
1570         if (!(MayLoad &&
1571               !UsedRegUnits.available(getLdStRegOp(FirstMI).getReg())) &&
1572             !mayAlias(FirstMI, MemInsns, AA)) {
1573
1574           if (ModifiedRegUnits.available(getLdStRegOp(FirstMI).getReg())) {
1575             Flags.setMergeForward(true);
1576             Flags.clearRenameReg();
1577             return MBBI;
1578           }
1579
1580           if (DebugCounter::shouldExecute(RegRenamingCounter)) {
1581             if (!MaybeCanRename)
1582               MaybeCanRename = {canRenameUpToDef(FirstMI, UsedInBetween,
1583                                                  RequiredClasses, TRI)};
1584
1585             if (*MaybeCanRename) {
1586               Optional<MCPhysReg> MaybeRenameReg = tryToFindRegisterToRename(
1587                   FirstMI, MI, DefinedInBB, UsedInBetween, RequiredClasses,
1588                   TRI);
1589               if (MaybeRenameReg) {
1590                 Flags.setRenameReg(*MaybeRenameReg);
1591                 Flags.setMergeForward(true);
1592                 MBBIWithRenameReg = MBBI;
1593               }
1594             }
1595           }
1596         }
1597         // Unable to combine these instructions due to interference in between.
1598         // Keep looking.
1599       }
1600     }
1601
1602     if (Flags.getRenameReg())
1603       return MBBIWithRenameReg;
1604
1605     // If the instruction wasn't a matching load or store.  Stop searching if we
1606     // encounter a call instruction that might modify memory.
1607     if (MI.isCall())
1608       return E;
1609
1610     // Update modified / uses register units.
1611     LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1612
1613     // Otherwise, if the base register is modified, we have no match, so
1614     // return early.
1615     if (!ModifiedRegUnits.available(BaseReg))
1616       return E;
1617
1618     // Update list of instructions that read/write memory.
1619     if (MI.mayLoadOrStore())
1620       MemInsns.push_back(&MI);
1621   }
1622   return E;
1623 }
1624
1625 MachineBasicBlock::iterator
1626 AArch64LoadStoreOpt::mergeUpdateInsn(MachineBasicBlock::iterator I,
1627                                      MachineBasicBlock::iterator Update,
1628                                      bool IsPreIdx) {
1629   assert((Update->getOpcode() == AArch64::ADDXri ||
1630           Update->getOpcode() == AArch64::SUBXri) &&
1631          "Unexpected base register update instruction to merge!");
1632   MachineBasicBlock::iterator NextI = I;
1633   // Return the instruction following the merged instruction, which is
1634   // the instruction following our unmerged load. Unless that's the add/sub
1635   // instruction we're merging, in which case it's the one after that.
1636   if (++NextI == Update)
1637     ++NextI;
1638
1639   int Value = Update->getOperand(2).getImm();
1640   assert(AArch64_AM::getShiftValue(Update->getOperand(3).getImm()) == 0 &&
1641          "Can't merge 1 << 12 offset into pre-/post-indexed load / store");
1642   if (Update->getOpcode() == AArch64::SUBXri)
1643     Value = -Value;
1644
1645   unsigned NewOpc = IsPreIdx ? getPreIndexedOpcode(I->getOpcode())
1646                              : getPostIndexedOpcode(I->getOpcode());
1647   MachineInstrBuilder MIB;
1648   int Scale, MinOffset, MaxOffset;
1649   getPrePostIndexedMemOpInfo(*I, Scale, MinOffset, MaxOffset);
1650   if (!isPairedLdSt(*I)) {
1651     // Non-paired instruction.
1652     MIB = BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
1653               .add(getLdStRegOp(*Update))
1654               .add(getLdStRegOp(*I))
1655               .add(getLdStBaseOp(*I))
1656               .addImm(Value / Scale)
1657               .setMemRefs(I->memoperands())
1658               .setMIFlags(I->mergeFlagsWith(*Update));
1659   } else {
1660     // Paired instruction.
1661     MIB = BuildMI(*I->getParent(), I, I->getDebugLoc(), TII->get(NewOpc))
1662               .add(getLdStRegOp(*Update))
1663               .add(getLdStRegOp(*I, 0))
1664               .add(getLdStRegOp(*I, 1))
1665               .add(getLdStBaseOp(*I))
1666               .addImm(Value / Scale)
1667               .setMemRefs(I->memoperands())
1668               .setMIFlags(I->mergeFlagsWith(*Update));
1669   }
1670   (void)MIB;
1671
1672   if (IsPreIdx) {
1673     ++NumPreFolded;
1674     LLVM_DEBUG(dbgs() << "Creating pre-indexed load/store.");
1675   } else {
1676     ++NumPostFolded;
1677     LLVM_DEBUG(dbgs() << "Creating post-indexed load/store.");
1678   }
1679   LLVM_DEBUG(dbgs() << "    Replacing instructions:\n    ");
1680   LLVM_DEBUG(I->print(dbgs()));
1681   LLVM_DEBUG(dbgs() << "    ");
1682   LLVM_DEBUG(Update->print(dbgs()));
1683   LLVM_DEBUG(dbgs() << "  with instruction:\n    ");
1684   LLVM_DEBUG(((MachineInstr *)MIB)->print(dbgs()));
1685   LLVM_DEBUG(dbgs() << "\n");
1686
1687   // Erase the old instructions for the block.
1688   I->eraseFromParent();
1689   Update->eraseFromParent();
1690
1691   return NextI;
1692 }
1693
1694 bool AArch64LoadStoreOpt::isMatchingUpdateInsn(MachineInstr &MemMI,
1695                                                MachineInstr &MI,
1696                                                unsigned BaseReg, int Offset) {
1697   switch (MI.getOpcode()) {
1698   default:
1699     break;
1700   case AArch64::SUBXri:
1701   case AArch64::ADDXri:
1702     // Make sure it's a vanilla immediate operand, not a relocation or
1703     // anything else we can't handle.
1704     if (!MI.getOperand(2).isImm())
1705       break;
1706     // Watch out for 1 << 12 shifted value.
1707     if (AArch64_AM::getShiftValue(MI.getOperand(3).getImm()))
1708       break;
1709
1710     // The update instruction source and destination register must be the
1711     // same as the load/store base register.
1712     if (MI.getOperand(0).getReg() != BaseReg ||
1713         MI.getOperand(1).getReg() != BaseReg)
1714       break;
1715
1716     int UpdateOffset = MI.getOperand(2).getImm();
1717     if (MI.getOpcode() == AArch64::SUBXri)
1718       UpdateOffset = -UpdateOffset;
1719
1720     // The immediate must be a multiple of the scaling factor of the pre/post
1721     // indexed instruction.
1722     int Scale, MinOffset, MaxOffset;
1723     getPrePostIndexedMemOpInfo(MemMI, Scale, MinOffset, MaxOffset);
1724     if (UpdateOffset % Scale != 0)
1725       break;
1726
1727     // Scaled offset must fit in the instruction immediate.
1728     int ScaledOffset = UpdateOffset / Scale;
1729     if (ScaledOffset > MaxOffset || ScaledOffset < MinOffset)
1730       break;
1731
1732     // If we have a non-zero Offset, we check that it matches the amount
1733     // we're adding to the register.
1734     if (!Offset || Offset == UpdateOffset)
1735       return true;
1736     break;
1737   }
1738   return false;
1739 }
1740
1741 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnForward(
1742     MachineBasicBlock::iterator I, int UnscaledOffset, unsigned Limit) {
1743   MachineBasicBlock::iterator E = I->getParent()->end();
1744   MachineInstr &MemMI = *I;
1745   MachineBasicBlock::iterator MBBI = I;
1746
1747   Register BaseReg = getLdStBaseOp(MemMI).getReg();
1748   int MIUnscaledOffset = getLdStOffsetOp(MemMI).getImm() * TII->getMemScale(MemMI);
1749
1750   // Scan forward looking for post-index opportunities.  Updating instructions
1751   // can't be formed if the memory instruction doesn't have the offset we're
1752   // looking for.
1753   if (MIUnscaledOffset != UnscaledOffset)
1754     return E;
1755
1756   // If the base register overlaps a source/destination register, we can't
1757   // merge the update. This does not apply to tag store instructions which
1758   // ignore the address part of the source register.
1759   // This does not apply to STGPi as well, which does not have unpredictable
1760   // behavior in this case unlike normal stores, and always performs writeback
1761   // after reading the source register value.
1762   if (!isTagStore(MemMI) && MemMI.getOpcode() != AArch64::STGPi) {
1763     bool IsPairedInsn = isPairedLdSt(MemMI);
1764     for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
1765       Register DestReg = getLdStRegOp(MemMI, i).getReg();
1766       if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
1767         return E;
1768     }
1769   }
1770
1771   // Track which register units have been modified and used between the first
1772   // insn (inclusive) and the second insn.
1773   ModifiedRegUnits.clear();
1774   UsedRegUnits.clear();
1775   ++MBBI;
1776   for (unsigned Count = 0; MBBI != E && Count < Limit; ++MBBI) {
1777     MachineInstr &MI = *MBBI;
1778
1779     // Don't count transient instructions towards the search limit since there
1780     // may be different numbers of them if e.g. debug information is present.
1781     if (!MI.isTransient())
1782       ++Count;
1783
1784     // If we found a match, return it.
1785     if (isMatchingUpdateInsn(*I, MI, BaseReg, UnscaledOffset))
1786       return MBBI;
1787
1788     // Update the status of what the instruction clobbered and used.
1789     LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1790
1791     // Otherwise, if the base register is used or modified, we have no match, so
1792     // return early.
1793     if (!ModifiedRegUnits.available(BaseReg) ||
1794         !UsedRegUnits.available(BaseReg))
1795       return E;
1796   }
1797   return E;
1798 }
1799
1800 MachineBasicBlock::iterator AArch64LoadStoreOpt::findMatchingUpdateInsnBackward(
1801     MachineBasicBlock::iterator I, unsigned Limit) {
1802   MachineBasicBlock::iterator B = I->getParent()->begin();
1803   MachineBasicBlock::iterator E = I->getParent()->end();
1804   MachineInstr &MemMI = *I;
1805   MachineBasicBlock::iterator MBBI = I;
1806
1807   Register BaseReg = getLdStBaseOp(MemMI).getReg();
1808   int Offset = getLdStOffsetOp(MemMI).getImm();
1809
1810   // If the load/store is the first instruction in the block, there's obviously
1811   // not any matching update. Ditto if the memory offset isn't zero.
1812   if (MBBI == B || Offset != 0)
1813     return E;
1814   // If the base register overlaps a destination register, we can't
1815   // merge the update.
1816   if (!isTagStore(MemMI)) {
1817     bool IsPairedInsn = isPairedLdSt(MemMI);
1818     for (unsigned i = 0, e = IsPairedInsn ? 2 : 1; i != e; ++i) {
1819       Register DestReg = getLdStRegOp(MemMI, i).getReg();
1820       if (DestReg == BaseReg || TRI->isSubRegister(BaseReg, DestReg))
1821         return E;
1822     }
1823   }
1824
1825   // Track which register units have been modified and used between the first
1826   // insn (inclusive) and the second insn.
1827   ModifiedRegUnits.clear();
1828   UsedRegUnits.clear();
1829   unsigned Count = 0;
1830   do {
1831     --MBBI;
1832     MachineInstr &MI = *MBBI;
1833
1834     // Don't count transient instructions towards the search limit since there
1835     // may be different numbers of them if e.g. debug information is present.
1836     if (!MI.isTransient())
1837       ++Count;
1838
1839     // If we found a match, return it.
1840     if (isMatchingUpdateInsn(*I, MI, BaseReg, Offset))
1841       return MBBI;
1842
1843     // Update the status of what the instruction clobbered and used.
1844     LiveRegUnits::accumulateUsedDefed(MI, ModifiedRegUnits, UsedRegUnits, TRI);
1845
1846     // Otherwise, if the base register is used or modified, we have no match, so
1847     // return early.
1848     if (!ModifiedRegUnits.available(BaseReg) ||
1849         !UsedRegUnits.available(BaseReg))
1850       return E;
1851   } while (MBBI != B && Count < Limit);
1852   return E;
1853 }
1854
1855 bool AArch64LoadStoreOpt::tryToPromoteLoadFromStore(
1856     MachineBasicBlock::iterator &MBBI) {
1857   MachineInstr &MI = *MBBI;
1858   // If this is a volatile load, don't mess with it.
1859   if (MI.hasOrderedMemoryRef())
1860     return false;
1861
1862   // Make sure this is a reg+imm.
1863   // FIXME: It is possible to extend it to handle reg+reg cases.
1864   if (!getLdStOffsetOp(MI).isImm())
1865     return false;
1866
1867   // Look backward up to LdStLimit instructions.
1868   MachineBasicBlock::iterator StoreI;
1869   if (findMatchingStore(MBBI, LdStLimit, StoreI)) {
1870     ++NumLoadsFromStoresPromoted;
1871     // Promote the load. Keeping the iterator straight is a
1872     // pain, so we let the merge routine tell us what the next instruction
1873     // is after it's done mucking about.
1874     MBBI = promoteLoadFromStore(MBBI, StoreI);
1875     return true;
1876   }
1877   return false;
1878 }
1879
1880 // Merge adjacent zero stores into a wider store.
1881 bool AArch64LoadStoreOpt::tryToMergeZeroStInst(
1882     MachineBasicBlock::iterator &MBBI) {
1883   assert(isPromotableZeroStoreInst(*MBBI) && "Expected narrow store.");
1884   MachineInstr &MI = *MBBI;
1885   MachineBasicBlock::iterator E = MI.getParent()->end();
1886
1887   if (!TII->isCandidateToMergeOrPair(MI))
1888     return false;
1889
1890   // Look ahead up to LdStLimit instructions for a mergable instruction.
1891   LdStPairFlags Flags;
1892   MachineBasicBlock::iterator MergeMI =
1893       findMatchingInsn(MBBI, Flags, LdStLimit, /* FindNarrowMerge = */ true);
1894   if (MergeMI != E) {
1895     ++NumZeroStoresPromoted;
1896
1897     // Keeping the iterator straight is a pain, so we let the merge routine tell
1898     // us what the next instruction is after it's done mucking about.
1899     MBBI = mergeNarrowZeroStores(MBBI, MergeMI, Flags);
1900     return true;
1901   }
1902   return false;
1903 }
1904
1905 // Find loads and stores that can be merged into a single load or store pair
1906 // instruction.
1907 bool AArch64LoadStoreOpt::tryToPairLdStInst(MachineBasicBlock::iterator &MBBI) {
1908   MachineInstr &MI = *MBBI;
1909   MachineBasicBlock::iterator E = MI.getParent()->end();
1910
1911   if (!TII->isCandidateToMergeOrPair(MI))
1912     return false;
1913
1914   // Early exit if the offset is not possible to match. (6 bits of positive
1915   // range, plus allow an extra one in case we find a later insn that matches
1916   // with Offset-1)
1917   bool IsUnscaled = TII->isUnscaledLdSt(MI);
1918   int Offset = getLdStOffsetOp(MI).getImm();
1919   int OffsetStride = IsUnscaled ? TII->getMemScale(MI) : 1;
1920   // Allow one more for offset.
1921   if (Offset > 0)
1922     Offset -= OffsetStride;
1923   if (!inBoundsForPair(IsUnscaled, Offset, OffsetStride))
1924     return false;
1925
1926   // Look ahead up to LdStLimit instructions for a pairable instruction.
1927   LdStPairFlags Flags;
1928   MachineBasicBlock::iterator Paired =
1929       findMatchingInsn(MBBI, Flags, LdStLimit, /* FindNarrowMerge = */ false);
1930   if (Paired != E) {
1931     ++NumPairCreated;
1932     if (TII->isUnscaledLdSt(MI))
1933       ++NumUnscaledPairCreated;
1934     // Keeping the iterator straight is a pain, so we let the merge routine tell
1935     // us what the next instruction is after it's done mucking about.
1936     auto Prev = std::prev(MBBI);
1937     MBBI = mergePairedInsns(MBBI, Paired, Flags);
1938     // Collect liveness info for instructions between Prev and the new position
1939     // MBBI.
1940     for (auto I = std::next(Prev); I != MBBI; I++)
1941       updateDefinedRegisters(*I, DefinedInBB, TRI);
1942
1943     return true;
1944   }
1945   return false;
1946 }
1947
1948 bool AArch64LoadStoreOpt::tryToMergeLdStUpdate
1949     (MachineBasicBlock::iterator &MBBI) {
1950   MachineInstr &MI = *MBBI;
1951   MachineBasicBlock::iterator E = MI.getParent()->end();
1952   MachineBasicBlock::iterator Update;
1953
1954   // Look forward to try to form a post-index instruction. For example,
1955   // ldr x0, [x20]
1956   // add x20, x20, #32
1957   //   merged into:
1958   // ldr x0, [x20], #32
1959   Update = findMatchingUpdateInsnForward(MBBI, 0, UpdateLimit);
1960   if (Update != E) {
1961     // Merge the update into the ld/st.
1962     MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/false);
1963     return true;
1964   }
1965
1966   // Don't know how to handle unscaled pre/post-index versions below, so bail.
1967   if (TII->isUnscaledLdSt(MI.getOpcode()))
1968     return false;
1969
1970   // Look back to try to find a pre-index instruction. For example,
1971   // add x0, x0, #8
1972   // ldr x1, [x0]
1973   //   merged into:
1974   // ldr x1, [x0, #8]!
1975   Update = findMatchingUpdateInsnBackward(MBBI, UpdateLimit);
1976   if (Update != E) {
1977     // Merge the update into the ld/st.
1978     MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/true);
1979     return true;
1980   }
1981
1982   // The immediate in the load/store is scaled by the size of the memory
1983   // operation. The immediate in the add we're looking for,
1984   // however, is not, so adjust here.
1985   int UnscaledOffset = getLdStOffsetOp(MI).getImm() * TII->getMemScale(MI);
1986
1987   // Look forward to try to find a pre-index instruction. For example,
1988   // ldr x1, [x0, #64]
1989   // add x0, x0, #64
1990   //   merged into:
1991   // ldr x1, [x0, #64]!
1992   Update = findMatchingUpdateInsnForward(MBBI, UnscaledOffset, UpdateLimit);
1993   if (Update != E) {
1994     // Merge the update into the ld/st.
1995     MBBI = mergeUpdateInsn(MBBI, Update, /*IsPreIdx=*/true);
1996     return true;
1997   }
1998
1999   return false;
2000 }
2001
2002 bool AArch64LoadStoreOpt::optimizeBlock(MachineBasicBlock &MBB,
2003                                         bool EnableNarrowZeroStOpt) {
2004
2005   bool Modified = false;
2006   // Four tranformations to do here:
2007   // 1) Find loads that directly read from stores and promote them by
2008   //    replacing with mov instructions. If the store is wider than the load,
2009   //    the load will be replaced with a bitfield extract.
2010   //      e.g.,
2011   //        str w1, [x0, #4]
2012   //        ldrh w2, [x0, #6]
2013   //        ; becomes
2014   //        str w1, [x0, #4]
2015   //        lsr w2, w1, #16
2016   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2017        MBBI != E;) {
2018     if (isPromotableLoadFromStore(*MBBI) && tryToPromoteLoadFromStore(MBBI))
2019       Modified = true;
2020     else
2021       ++MBBI;
2022   }
2023   // 2) Merge adjacent zero stores into a wider store.
2024   //      e.g.,
2025   //        strh wzr, [x0]
2026   //        strh wzr, [x0, #2]
2027   //        ; becomes
2028   //        str wzr, [x0]
2029   //      e.g.,
2030   //        str wzr, [x0]
2031   //        str wzr, [x0, #4]
2032   //        ; becomes
2033   //        str xzr, [x0]
2034   if (EnableNarrowZeroStOpt)
2035     for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2036          MBBI != E;) {
2037       if (isPromotableZeroStoreInst(*MBBI) && tryToMergeZeroStInst(MBBI))
2038         Modified = true;
2039       else
2040         ++MBBI;
2041     }
2042   // 3) Find loads and stores that can be merged into a single load or store
2043   //    pair instruction.
2044   //      e.g.,
2045   //        ldr x0, [x2]
2046   //        ldr x1, [x2, #8]
2047   //        ; becomes
2048   //        ldp x0, x1, [x2]
2049
2050   if (MBB.getParent()->getRegInfo().tracksLiveness()) {
2051     DefinedInBB.clear();
2052     DefinedInBB.addLiveIns(MBB);
2053   }
2054
2055   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2056        MBBI != E;) {
2057     // Track currently live registers up to this point, to help with
2058     // searching for a rename register on demand.
2059     updateDefinedRegisters(*MBBI, DefinedInBB, TRI);
2060     if (TII->isPairableLdStInst(*MBBI) && tryToPairLdStInst(MBBI))
2061       Modified = true;
2062     else
2063       ++MBBI;
2064   }
2065   // 4) Find base register updates that can be merged into the load or store
2066   //    as a base-reg writeback.
2067   //      e.g.,
2068   //        ldr x0, [x2]
2069   //        add x2, x2, #4
2070   //        ; becomes
2071   //        ldr x0, [x2], #4
2072   for (MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
2073        MBBI != E;) {
2074     if (isMergeableLdStUpdate(*MBBI) && tryToMergeLdStUpdate(MBBI))
2075       Modified = true;
2076     else
2077       ++MBBI;
2078   }
2079
2080   return Modified;
2081 }
2082
2083 bool AArch64LoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2084   if (skipFunction(Fn.getFunction()))
2085     return false;
2086
2087   Subtarget = &static_cast<const AArch64Subtarget &>(Fn.getSubtarget());
2088   TII = static_cast<const AArch64InstrInfo *>(Subtarget->getInstrInfo());
2089   TRI = Subtarget->getRegisterInfo();
2090   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2091
2092   // Resize the modified and used register unit trackers.  We do this once
2093   // per function and then clear the register units each time we optimize a load
2094   // or store.
2095   ModifiedRegUnits.init(*TRI);
2096   UsedRegUnits.init(*TRI);
2097   DefinedInBB.init(*TRI);
2098
2099   bool Modified = false;
2100   bool enableNarrowZeroStOpt = !Subtarget->requiresStrictAlign();
2101   for (auto &MBB : Fn) {
2102     auto M = optimizeBlock(MBB, enableNarrowZeroStOpt);
2103     Modified |= M;
2104   }
2105
2106   return Modified;
2107 }
2108
2109 // FIXME: Do we need/want a pre-alloc pass like ARM has to try to keep loads and
2110 // stores near one another?  Note: The pre-RA instruction scheduler already has
2111 // hooks to try and schedule pairable loads/stores together to improve pairing
2112 // opportunities.  Thus, pre-RA pairing pass may not be worth the effort.
2113
2114 // FIXME: When pairing store instructions it's very possible for this pass to
2115 // hoist a store with a KILL marker above another use (without a KILL marker).
2116 // The resulting IR is invalid, but nothing uses the KILL markers after this
2117 // pass, so it's never caused a problem in practice.
2118
2119 /// createAArch64LoadStoreOptimizationPass - returns an instance of the
2120 /// load / store optimization pass.
2121 FunctionPass *llvm::createAArch64LoadStoreOptimizationPass() {
2122   return new AArch64LoadStoreOpt();
2123 }