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