lib/Target/ARM/ARMLoadStoreOptimizer.cpp

   1 //===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ------------===//
   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 /// \file 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 "ARM.h"
  16 #include "ARMBaseInstrInfo.h"
  17 #include "ARMBaseRegisterInfo.h"
  18 #include "ARMISelLowering.h"
  19 #include "ARMMachineFunctionInfo.h"
  20 #include "ARMSubtarget.h"
  21 #include "MCTargetDesc/ARMAddressingModes.h"
  22 #include "ThumbRegisterInfo.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SmallSet.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/CodeGen/MachineBasicBlock.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31 #include "llvm/CodeGen/MachineInstr.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineRegisterInfo.h"
  34 #include "llvm/CodeGen/RegisterClassInfo.h"
  35 #include "llvm/CodeGen/SelectionDAGNodes.h"
  36 #include "llvm/CodeGen/LivePhysRegs.h"
  37 #include "llvm/IR/DataLayout.h"
  38 #include "llvm/IR/DerivedTypes.h"
  39 #include "llvm/IR/Function.h"
  40 #include "llvm/Support/Allocator.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/ErrorHandling.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Target/TargetInstrInfo.h"
  45 #include "llvm/Target/TargetMachine.h"
  46 #include "llvm/Target/TargetRegisterInfo.h"
  47 using namespace llvm;
  48
  49 #define DEBUG_TYPE "arm-ldst-opt"
  50
  51 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
  52 STATISTIC(NumSTMGened , "Number of stm instructions generated");
  53 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
  54 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
  55 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
  56 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
  57 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
  58 STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
  59 STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
  60 STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
  61 STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");
  62
  63 namespace {
  64   /// Post- register allocation pass the combine load / store instructions to
  65   /// form ldm / stm instructions.
  66   struct ARMLoadStoreOpt : public MachineFunctionPass {
  67     static char ID;
  68     ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
  69
  70     const MachineFunction *MF;
  71     const TargetInstrInfo *TII;
  72     const TargetRegisterInfo *TRI;
  73     const MachineRegisterInfo *MRI;
  74     const ARMSubtarget *STI;
  75     const TargetLowering *TL;
  76     ARMFunctionInfo *AFI;
  77     LivePhysRegs LiveRegs;
  78     RegisterClassInfo RegClassInfo;
  79     MachineBasicBlock::const_iterator LiveRegPos;
  80     bool LiveRegsValid;
  81     bool RegClassInfoValid;
  82     bool isThumb1, isThumb2;
  83
  84     bool runOnMachineFunction(MachineFunction &Fn) override;
  85
  86     const char *getPassName() const override {
  87       return "ARM load / store optimization pass";
  88     }
  89
  90   private:
  91     /// A set of load/store MachineInstrs with same base register sorted by
  92     /// offset.
  93     struct MemOpQueueEntry {
  94       MachineInstr *MI;
  95       int Offset;        ///< Load/Store offset.
  96       unsigned Position; ///< Position as counted from end of basic block.
  97       MemOpQueueEntry(MachineInstr *MI, int Offset, unsigned Position)
  98         : MI(MI), Offset(Offset), Position(Position) {}
  99     };
 100     typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
 101
 102     /// A set of MachineInstrs that fulfill (nearly all) conditions to get
 103     /// merged into a LDM/STM.
 104     struct MergeCandidate {
 105       /// List of instructions ordered by load/store offset.
 106       SmallVector<MachineInstr*, 4> Instrs;
 107       /// Index in Instrs of the instruction being latest in the schedule.
 108       unsigned LatestMIIdx;
 109       /// Index in Instrs of the instruction being earliest in the schedule.
 110       unsigned EarliestMIIdx;
 111       /// Index into the basic block where the merged instruction will be
 112       /// inserted. (See MemOpQueueEntry.Position)
 113       unsigned InsertPos;
 114       /// Whether the instructions can be merged into a ldm/stm instruction.
 115       bool CanMergeToLSMulti;
 116       /// Whether the instructions can be merged into a ldrd/strd instruction.
 117       bool CanMergeToLSDouble;
 118     };
 119     SpecificBumpPtrAllocator<MergeCandidate> Allocator;
 120     SmallVector<const MergeCandidate*,4> Candidates;
 121
 122     void moveLiveRegsBefore(const MachineBasicBlock &MBB,
 123                             MachineBasicBlock::const_iterator Before);
 124     unsigned findFreeReg(const TargetRegisterClass &RegClass);
 125     void UpdateBaseRegUses(MachineBasicBlock &MBB,
 126                            MachineBasicBlock::iterator MBBI,
 127                            DebugLoc DL, unsigned Base, unsigned WordOffset,
 128                            ARMCC::CondCodes Pred, unsigned PredReg);
 129     MachineInstr *CreateLoadStoreMulti(MachineBasicBlock &MBB,
 130         MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
 131         bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
 132         DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs);
 133     MachineInstr *CreateLoadStoreDouble(MachineBasicBlock &MBB,
 134         MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
 135         bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
 136         DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) const;
 137     void FormCandidates(const MemOpQueue &MemOps);
 138     MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
 139     bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
 140                              MachineBasicBlock::iterator &MBBI);
 141     bool MergeBaseUpdateLoadStore(MachineInstr *MI);
 142     bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
 143     bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
 144     bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
 145   };
 146   char ARMLoadStoreOpt::ID = 0;
 147 }
 148
 149 static bool definesCPSR(const MachineInstr *MI) {
 150   for (const auto &MO : MI->operands()) {
 151     if (!MO.isReg())
 152       continue;
 153     if (MO.isDef() && MO.getReg() == ARM::CPSR && !MO.isDead())
 154       // If the instruction has live CPSR def, then it's not safe to fold it
 155       // into load / store.
 156       return true;
 157   }
 158
 159   return false;
 160 }
 161
 162 static int getMemoryOpOffset(const MachineInstr *MI) {
 163   unsigned Opcode = MI->getOpcode();
 164   bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
 165   unsigned NumOperands = MI->getDesc().getNumOperands();
 166   unsigned OffField = MI->getOperand(NumOperands-3).getImm();
 167
 168   if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
 169       Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
 170       Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
 171       Opcode == ARM::LDRi12   || Opcode == ARM::STRi12)
 172     return OffField;
 173
 174   // Thumb1 immediate offsets are scaled by 4
 175   if (Opcode == ARM::tLDRi || Opcode == ARM::tSTRi ||
 176       Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi)
 177     return OffField * 4;
 178
 179   int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
 180     : ARM_AM::getAM5Offset(OffField) * 4;
 181   ARM_AM::AddrOpc Op = isAM3 ? ARM_AM::getAM3Op(OffField)
 182     : ARM_AM::getAM5Op(OffField);
 183
 184   if (Op == ARM_AM::sub)
 185     return -Offset;
 186
 187   return Offset;
 188 }
 189
 190 static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
 191   return MI.getOperand(1);
 192 }
 193
 194 static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
 195   return MI.getOperand(0);
 196 }
 197
 198 static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
 199   switch (Opcode) {
 200   default: llvm_unreachable("Unhandled opcode!");
 201   case ARM::LDRi12:
 202     ++NumLDMGened;
 203     switch (Mode) {
 204     default: llvm_unreachable("Unhandled submode!");
 205     case ARM_AM::ia: return ARM::LDMIA;
 206     case ARM_AM::da: return ARM::LDMDA;
 207     case ARM_AM::db: return ARM::LDMDB;
 208     case ARM_AM::ib: return ARM::LDMIB;
 209     }
 210   case ARM::STRi12:
 211     ++NumSTMGened;
 212     switch (Mode) {
 213     default: llvm_unreachable("Unhandled submode!");
 214     case ARM_AM::ia: return ARM::STMIA;
 215     case ARM_AM::da: return ARM::STMDA;
 216     case ARM_AM::db: return ARM::STMDB;
 217     case ARM_AM::ib: return ARM::STMIB;
 218     }
 219   case ARM::tLDRi:
 220   case ARM::tLDRspi:
 221     // tLDMIA is writeback-only - unless the base register is in the input
 222     // reglist.
 223     ++NumLDMGened;
 224     switch (Mode) {
 225     default: llvm_unreachable("Unhandled submode!");
 226     case ARM_AM::ia: return ARM::tLDMIA;
 227     }
 228   case ARM::tSTRi:
 229   case ARM::tSTRspi:
 230     // There is no non-writeback tSTMIA either.
 231     ++NumSTMGened;
 232     switch (Mode) {
 233     default: llvm_unreachable("Unhandled submode!");
 234     case ARM_AM::ia: return ARM::tSTMIA_UPD;
 235     }
 236   case ARM::t2LDRi8:
 237   case ARM::t2LDRi12:
 238     ++NumLDMGened;
 239     switch (Mode) {
 240     default: llvm_unreachable("Unhandled submode!");
 241     case ARM_AM::ia: return ARM::t2LDMIA;
 242     case ARM_AM::db: return ARM::t2LDMDB;
 243     }
 244   case ARM::t2STRi8:
 245   case ARM::t2STRi12:
 246     ++NumSTMGened;
 247     switch (Mode) {
 248     default: llvm_unreachable("Unhandled submode!");
 249     case ARM_AM::ia: return ARM::t2STMIA;
 250     case ARM_AM::db: return ARM::t2STMDB;
 251     }
 252   case ARM::VLDRS:
 253     ++NumVLDMGened;
 254     switch (Mode) {
 255     default: llvm_unreachable("Unhandled submode!");
 256     case ARM_AM::ia: return ARM::VLDMSIA;
 257     case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
 258     }
 259   case ARM::VSTRS:
 260     ++NumVSTMGened;
 261     switch (Mode) {
 262     default: llvm_unreachable("Unhandled submode!");
 263     case ARM_AM::ia: return ARM::VSTMSIA;
 264     case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
 265     }
 266   case ARM::VLDRD:
 267     ++NumVLDMGened;
 268     switch (Mode) {
 269     default: llvm_unreachable("Unhandled submode!");
 270     case ARM_AM::ia: return ARM::VLDMDIA;
 271     case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
 272     }
 273   case ARM::VSTRD:
 274     ++NumVSTMGened;
 275     switch (Mode) {
 276     default: llvm_unreachable("Unhandled submode!");
 277     case ARM_AM::ia: return ARM::VSTMDIA;
 278     case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
 279     }
 280   }
 281 }
 282
 283 static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
 284   switch (Opcode) {
 285   default: llvm_unreachable("Unhandled opcode!");
 286   case ARM::LDMIA_RET:
 287   case ARM::LDMIA:
 288   case ARM::LDMIA_UPD:
 289   case ARM::STMIA:
 290   case ARM::STMIA_UPD:
 291   case ARM::tLDMIA:
 292   case ARM::tLDMIA_UPD:
 293   case ARM::tSTMIA_UPD:
 294   case ARM::t2LDMIA_RET:
 295   case ARM::t2LDMIA:
 296   case ARM::t2LDMIA_UPD:
 297   case ARM::t2STMIA:
 298   case ARM::t2STMIA_UPD:
 299   case ARM::VLDMSIA:
 300   case ARM::VLDMSIA_UPD:
 301   case ARM::VSTMSIA:
 302   case ARM::VSTMSIA_UPD:
 303   case ARM::VLDMDIA:
 304   case ARM::VLDMDIA_UPD:
 305   case ARM::VSTMDIA:
 306   case ARM::VSTMDIA_UPD:
 307     return ARM_AM::ia;
 308
 309   case ARM::LDMDA:
 310   case ARM::LDMDA_UPD:
 311   case ARM::STMDA:
 312   case ARM::STMDA_UPD:
 313     return ARM_AM::da;
 314
 315   case ARM::LDMDB:
 316   case ARM::LDMDB_UPD:
 317   case ARM::STMDB:
 318   case ARM::STMDB_UPD:
 319   case ARM::t2LDMDB:
 320   case ARM::t2LDMDB_UPD:
 321   case ARM::t2STMDB:
 322   case ARM::t2STMDB_UPD:
 323   case ARM::VLDMSDB_UPD:
 324   case ARM::VSTMSDB_UPD:
 325   case ARM::VLDMDDB_UPD:
 326   case ARM::VSTMDDB_UPD:
 327     return ARM_AM::db;
 328
 329   case ARM::LDMIB:
 330   case ARM::LDMIB_UPD:
 331   case ARM::STMIB:
 332   case ARM::STMIB_UPD:
 333     return ARM_AM::ib;
 334   }
 335 }
 336
 337 static bool isT1i32Load(unsigned Opc) {
 338   return Opc == ARM::tLDRi || Opc == ARM::tLDRspi;
 339 }
 340
 341 static bool isT2i32Load(unsigned Opc) {
 342   return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
 343 }
 344
 345 static bool isi32Load(unsigned Opc) {
 346   return Opc == ARM::LDRi12 || isT1i32Load(Opc) || isT2i32Load(Opc) ;
 347 }
 348
 349 static bool isT1i32Store(unsigned Opc) {
 350   return Opc == ARM::tSTRi || Opc == ARM::tSTRspi;
 351 }
 352
 353 static bool isT2i32Store(unsigned Opc) {
 354   return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
 355 }
 356
 357 static bool isi32Store(unsigned Opc) {
 358   return Opc == ARM::STRi12 || isT1i32Store(Opc) || isT2i32Store(Opc);
 359 }
 360
 361 static bool isLoadSingle(unsigned Opc) {
 362   return isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
 363 }
 364
 365 static unsigned getImmScale(unsigned Opc) {
 366   switch (Opc) {
 367   default: llvm_unreachable("Unhandled opcode!");
 368   case ARM::tLDRi:
 369   case ARM::tSTRi:
 370   case ARM::tLDRspi:
 371   case ARM::tSTRspi:
 372     return 1;
 373   case ARM::tLDRHi:
 374   case ARM::tSTRHi:
 375     return 2;
 376   case ARM::tLDRBi:
 377   case ARM::tSTRBi:
 378     return 4;
 379   }
 380 }
 381
 382 static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
 383   switch (MI->getOpcode()) {
 384   default: return 0;
 385   case ARM::LDRi12:
 386   case ARM::STRi12:
 387   case ARM::tLDRi:
 388   case ARM::tSTRi:
 389   case ARM::tLDRspi:
 390   case ARM::tSTRspi:
 391   case ARM::t2LDRi8:
 392   case ARM::t2LDRi12:
 393   case ARM::t2STRi8:
 394   case ARM::t2STRi12:
 395   case ARM::VLDRS:
 396   case ARM::VSTRS:
 397     return 4;
 398   case ARM::VLDRD:
 399   case ARM::VSTRD:
 400     return 8;
 401   case ARM::LDMIA:
 402   case ARM::LDMDA:
 403   case ARM::LDMDB:
 404   case ARM::LDMIB:
 405   case ARM::STMIA:
 406   case ARM::STMDA:
 407   case ARM::STMDB:
 408   case ARM::STMIB:
 409   case ARM::tLDMIA:
 410   case ARM::tLDMIA_UPD:
 411   case ARM::tSTMIA_UPD:
 412   case ARM::t2LDMIA:
 413   case ARM::t2LDMDB:
 414   case ARM::t2STMIA:
 415   case ARM::t2STMDB:
 416   case ARM::VLDMSIA:
 417   case ARM::VSTMSIA:
 418     return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
 419   case ARM::VLDMDIA:
 420   case ARM::VSTMDIA:
 421     return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
 422   }
 423 }
 424
 425 /// Update future uses of the base register with the offset introduced
 426 /// due to writeback. This function only works on Thumb1.
 427 void
 428 ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
 429                                    MachineBasicBlock::iterator MBBI,
 430                                    DebugLoc DL, unsigned Base,
 431                                    unsigned WordOffset,
 432                                    ARMCC::CondCodes Pred, unsigned PredReg) {
 433   assert(isThumb1 && "Can only update base register uses for Thumb1!");
 434   // Start updating any instructions with immediate offsets. Insert a SUB before
 435   // the first non-updateable instruction (if any).
 436   for (; MBBI != MBB.end(); ++MBBI) {
 437     bool InsertSub = false;
 438     unsigned Opc = MBBI->getOpcode();
 439
 440     if (MBBI->readsRegister(Base)) {
 441       int Offset;
 442       bool IsLoad =
 443         Opc == ARM::tLDRi || Opc == ARM::tLDRHi || Opc == ARM::tLDRBi;
 444       bool IsStore =
 445         Opc == ARM::tSTRi || Opc == ARM::tSTRHi || Opc == ARM::tSTRBi;
 446
 447       if (IsLoad || IsStore) {
 448         // Loads and stores with immediate offsets can be updated, but only if
 449         // the new offset isn't negative.
 450         // The MachineOperand containing the offset immediate is the last one
 451         // before predicates.
 452         MachineOperand &MO =
 453           MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
 454         // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
 455         Offset = MO.getImm() - WordOffset * getImmScale(Opc);
 456
 457         // If storing the base register, it needs to be reset first.
 458         unsigned InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
 459
 460         if (Offset >= 0 && !(IsStore && InstrSrcReg == Base))
 461           MO.setImm(Offset);
 462         else
 463           InsertSub = true;
 464
 465       } else if ((Opc == ARM::tSUBi8 || Opc == ARM::tADDi8) &&
 466                  !definesCPSR(MBBI)) {
 467         // SUBS/ADDS using this register, with a dead def of the CPSR.
 468         // Merge it with the update; if the merged offset is too large,
 469         // insert a new sub instead.
 470         MachineOperand &MO =
 471           MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
 472         Offset = (Opc == ARM::tSUBi8) ?
 473           MO.getImm() + WordOffset * 4 :
 474           MO.getImm() - WordOffset * 4 ;
 475         if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
 476           // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
 477           // Offset == 0.
 478           MO.setImm(Offset);
 479           // The base register has now been reset, so exit early.
 480           return;
 481         } else {
 482           InsertSub = true;
 483         }
 484
 485       } else {
 486         // Can't update the instruction.
 487         InsertSub = true;
 488       }
 489
 490     } else if (definesCPSR(MBBI) || MBBI->isCall() || MBBI->isBranch()) {
 491       // Since SUBS sets the condition flags, we can't place the base reset
 492       // after an instruction that has a live CPSR def.
 493       // The base register might also contain an argument for a function call.
 494       InsertSub = true;
 495     }
 496
 497     if (InsertSub) {
 498       // An instruction above couldn't be updated, so insert a sub.
 499       AddDefaultT1CC(BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base), true)
 500         .addReg(Base).addImm(WordOffset * 4).addImm(Pred).addReg(PredReg);
 501       return;
 502     }
 503
 504     if (MBBI->killsRegister(Base) || MBBI->definesRegister(Base))
 505       // Register got killed. Stop updating.
 506       return;
 507   }
 508
 509   // End of block was reached.
 510   if (MBB.succ_size() > 0) {
 511     // FIXME: Because of a bug, live registers are sometimes missing from
 512     // the successor blocks' live-in sets. This means we can't trust that
 513     // information and *always* have to reset at the end of a block.
 514     // See PR21029.
 515     if (MBBI != MBB.end()) --MBBI;
 516     AddDefaultT1CC(
 517       BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base), true)
 518       .addReg(Base).addImm(WordOffset * 4).addImm(Pred).addReg(PredReg);
 519   }
 520 }
 521
 522 /// Return the first register of class \p RegClass that is not in \p Regs.
 523 unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
 524   if (!RegClassInfoValid) {
 525     RegClassInfo.runOnMachineFunction(*MF);
 526     RegClassInfoValid = true;
 527   }
 528
 529   for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
 530     if (!LiveRegs.contains(Reg))
 531       return Reg;
 532   return 0;
 533 }
 534
 535 /// Compute live registers just before instruction \p Before (in normal schedule
 536 /// direction). Computes backwards so multiple queries in the same block must
 537 /// come in reverse order.
 538 void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
 539     MachineBasicBlock::const_iterator Before) {
 540   // Initialize if we never queried in this block.
 541   if (!LiveRegsValid) {
 542     LiveRegs.init(TRI);
 543     LiveRegs.addLiveOuts(&MBB, true);
 544     LiveRegPos = MBB.end();
 545     LiveRegsValid = true;
 546   }
 547   // Move backward just before the "Before" position.
 548   while (LiveRegPos != Before) {
 549     --LiveRegPos;
 550     LiveRegs.stepBackward(*LiveRegPos);
 551   }
 552 }
 553
 554 static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
 555                         unsigned Reg) {
 556   for (const std::pair<unsigned, bool> &R : Regs)
 557     if (R.first == Reg)
 558       return true;
 559   return false;
 560 }
 561
 562 /// Create and insert a LDM or STM with Base as base register and registers in
 563 /// Regs as the register operands that would be loaded / stored.  It returns
 564 /// true if the transformation is done.
 565 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(MachineBasicBlock &MBB,
 566     MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
 567     bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
 568     DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) {
 569   unsigned NumRegs = Regs.size();
 570   assert(NumRegs > 1);
 571
 572   // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
 573   // Compute liveness information for that register to make the decision.
 574   bool SafeToClobberCPSR = !isThumb1 ||
 575     (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
 576      MachineBasicBlock::LQR_Dead);
 577
 578   bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
 579
 580   // Exception: If the base register is in the input reglist, Thumb1 LDM is
 581   // non-writeback.
 582   // It's also not possible to merge an STR of the base register in Thumb1.
 583   if (isThumb1 && isi32Load(Opcode) && ContainsReg(Regs, Base)) {
 584     assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
 585     if (Opcode == ARM::tLDRi) {
 586       Writeback = false;
 587     } else if (Opcode == ARM::tSTRi) {
 588       return nullptr;
 589     }
 590   }
 591
 592   ARM_AM::AMSubMode Mode = ARM_AM::ia;
 593   // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
 594   bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
 595   bool haveIBAndDA = isNotVFP && !isThumb2 && !isThumb1;
 596
 597   if (Offset == 4 && haveIBAndDA) {
 598     Mode = ARM_AM::ib;
 599   } else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) {
 600     Mode = ARM_AM::da;
 601   } else if (Offset == -4 * (int)NumRegs && isNotVFP && !isThumb1) {
 602     // VLDM/VSTM do not support DB mode without also updating the base reg.
 603     Mode = ARM_AM::db;
 604   } else if (Offset != 0 || Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi) {
 605     // Check if this is a supported opcode before inserting instructions to
 606     // calculate a new base register.
 607     if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return nullptr;
 608
 609     // If starting offset isn't zero, insert a MI to materialize a new base.
 610     // But only do so if it is cost effective, i.e. merging more than two
 611     // loads / stores.
 612     if (NumRegs <= 2)
 613       return nullptr;
 614
 615     // On Thumb1, it's not worth materializing a new base register without
 616     // clobbering the CPSR (i.e. not using ADDS/SUBS).
 617     if (!SafeToClobberCPSR)
 618       return nullptr;
 619
 620     unsigned NewBase;
 621     if (isi32Load(Opcode)) {
 622       // If it is a load, then just use one of the destination register to
 623       // use as the new base.
 624       NewBase = Regs[NumRegs-1].first;
 625     } else {
 626       // Find a free register that we can use as scratch register.
 627       moveLiveRegsBefore(MBB, InsertBefore);
 628       // The merged instruction does not exist yet but will use several Regs if
 629       // it is a Store.
 630       if (!isLoadSingle(Opcode))
 631         for (const std::pair<unsigned, bool> &R : Regs)
 632           LiveRegs.addReg(R.first);
 633
 634       NewBase = findFreeReg(isThumb1 ? ARM::tGPRRegClass : ARM::GPRRegClass);
 635       if (NewBase == 0)
 636         return nullptr;
 637     }
 638
 639     int BaseOpc =
 640       isThumb2 ? ARM::t2ADDri :
 641       (isThumb1 && Base == ARM::SP) ? ARM::tADDrSPi :
 642       (isThumb1 && Offset < 8) ? ARM::tADDi3 :
 643       isThumb1 ? ARM::tADDi8  : ARM::ADDri;
 644
 645     if (Offset < 0) {
 646       Offset = - Offset;
 647       BaseOpc =
 648         isThumb2 ? ARM::t2SUBri :
 649         (isThumb1 && Offset < 8 && Base != ARM::SP) ? ARM::tSUBi3 :
 650         isThumb1 ? ARM::tSUBi8  : ARM::SUBri;
 651     }
 652
 653     if (!TL->isLegalAddImmediate(Offset))
 654       // FIXME: Try add with register operand?
 655       return nullptr; // Probably not worth it then.
 656
 657     // We can only append a kill flag to the add/sub input if the value is not
 658     // used in the register list of the stm as well.
 659     bool KillOldBase = BaseKill &&
 660       (!isi32Store(Opcode) || !ContainsReg(Regs, Base));
 661
 662     if (isThumb1) {
 663       // Thumb1: depending on immediate size, use either
 664       //   ADDS NewBase, Base, #imm3
 665       // or
 666       //   MOV  NewBase, Base
 667       //   ADDS NewBase, #imm8.
 668       if (Base != NewBase &&
 669           (BaseOpc == ARM::tADDi8 || BaseOpc == ARM::tSUBi8)) {
 670         // Need to insert a MOV to the new base first.
 671         if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
 672             !STI->hasV6Ops()) {
 673           // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
 674           if (Pred != ARMCC::AL)
 675             return nullptr;
 676           BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
 677             .addReg(Base, getKillRegState(KillOldBase));
 678         } else
 679           BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
 680             .addReg(Base, getKillRegState(KillOldBase))
 681             .addImm(Pred).addReg(PredReg);
 682
 683         // The following ADDS/SUBS becomes an update.
 684         Base = NewBase;
 685         KillOldBase = true;
 686       }
 687       if (BaseOpc == ARM::tADDrSPi) {
 688         assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
 689         BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
 690           .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset/4)
 691           .addImm(Pred).addReg(PredReg);
 692       } else
 693         AddDefaultT1CC(
 694           BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase), true)
 695           .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset)
 696           .addImm(Pred).addReg(PredReg);
 697     } else {
 698       BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
 699         .addReg(Base, getKillRegState(KillOldBase)).addImm(Offset)
 700         .addImm(Pred).addReg(PredReg).addReg(0);
 701     }
 702     Base = NewBase;
 703     BaseKill = true; // New base is always killed straight away.
 704   }
 705
 706   bool isDef = isLoadSingle(Opcode);
 707
 708   // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
 709   // base register writeback.
 710   Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
 711   if (!Opcode)
 712     return nullptr;
 713
 714   // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
 715   // - There is no writeback (LDM of base register),
 716   // - the base register is killed by the merged instruction,
 717   // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
 718   //   to reset the base register.
 719   // Otherwise, don't merge.
 720   // It's safe to return here since the code to materialize a new base register
 721   // above is also conditional on SafeToClobberCPSR.
 722   if (isThumb1 && !SafeToClobberCPSR && Writeback && !BaseKill)
 723     return nullptr;
 724
 725   MachineInstrBuilder MIB;
 726
 727   if (Writeback) {
 728     if (Opcode == ARM::tLDMIA)
 729       // Update tLDMIA with writeback if necessary.
 730       Opcode = ARM::tLDMIA_UPD;
 731
 732     MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
 733
 734     // Thumb1: we might need to set base writeback when building the MI.
 735     MIB.addReg(Base, getDefRegState(true))
 736        .addReg(Base, getKillRegState(BaseKill));
 737
 738     // The base isn't dead after a merged instruction with writeback.
 739     // Insert a sub instruction after the newly formed instruction to reset.
 740     if (!BaseKill)
 741       UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
 742
 743   } else {
 744     // No writeback, simply build the MachineInstr.
 745     MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
 746     MIB.addReg(Base, getKillRegState(BaseKill));
 747   }
 748
 749   MIB.addImm(Pred).addReg(PredReg);
 750
 751   for (const std::pair<unsigned, bool> &R : Regs)
 752     MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
 753
 754   return MIB.getInstr();
 755 }
 756
 757 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(MachineBasicBlock &MBB,
 758     MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
 759     bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
 760     DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) const {
 761   bool IsLoad = isi32Load(Opcode);
 762   assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
 763   unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
 764
 765   assert(Regs.size() == 2);
 766   MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
 767                                     TII->get(LoadStoreOpcode));
 768   if (IsLoad) {
 769     MIB.addReg(Regs[0].first, RegState::Define)
 770        .addReg(Regs[1].first, RegState::Define);
 771   } else {
 772     MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
 773        .addReg(Regs[1].first, getKillRegState(Regs[1].second));
 774   }
 775   MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 776   return MIB.getInstr();
 777 }
 778
 779 /// Call MergeOps and update MemOps and merges accordingly on success.
 780 MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
 781   const MachineInstr *First = Cand.Instrs.front();
 782   unsigned Opcode = First->getOpcode();
 783   bool IsLoad = isLoadSingle(Opcode);
 784   SmallVector<std::pair<unsigned, bool>, 8> Regs;
 785   SmallVector<unsigned, 4> ImpDefs;
 786   DenseSet<unsigned> KilledRegs;
 787   DenseSet<unsigned> UsedRegs;
 788   // Determine list of registers and list of implicit super-register defs.
 789   for (const MachineInstr *MI : Cand.Instrs) {
 790     const MachineOperand &MO = getLoadStoreRegOp(*MI);
 791     unsigned Reg = MO.getReg();
 792     bool IsKill = MO.isKill();
 793     if (IsKill)
 794       KilledRegs.insert(Reg);
 795     Regs.push_back(std::make_pair(Reg, IsKill));
 796     UsedRegs.insert(Reg);
 797
 798     if (IsLoad) {
 799       // Collect any implicit defs of super-registers, after merging we can't
 800       // be sure anymore that we properly preserved these live ranges and must
 801       // removed these implicit operands.
 802       for (const MachineOperand &MO : MI->implicit_operands()) {
 803         if (!MO.isReg() || !MO.isDef() || MO.isDead())
 804           continue;
 805         assert(MO.isImplicit());
 806         unsigned DefReg = MO.getReg();
 807
 808         if (std::find(ImpDefs.begin(), ImpDefs.end(), DefReg) != ImpDefs.end())
 809           continue;
 810         // We can ignore cases where the super-reg is read and written.
 811         if (MI->readsRegister(DefReg))
 812           continue;
 813         ImpDefs.push_back(DefReg);
 814       }
 815     }
 816   }
 817
 818   // Attempt the merge.
 819   typedef MachineBasicBlock::iterator iterator;
 820   MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
 821   iterator InsertBefore = std::next(iterator(LatestMI));
 822   MachineBasicBlock &MBB = *LatestMI->getParent();
 823   unsigned Offset = getMemoryOpOffset(First);
 824   unsigned Base = getLoadStoreBaseOp(*First).getReg();
 825   bool BaseKill = LatestMI->killsRegister(Base);
 826   unsigned PredReg = 0;
 827   ARMCC::CondCodes Pred = getInstrPredicate(First, PredReg);
 828   DebugLoc DL = First->getDebugLoc();
 829   MachineInstr *Merged = nullptr;
 830   if (Cand.CanMergeToLSDouble)
 831     Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
 832                                    Opcode, Pred, PredReg, DL, Regs);
 833   if (!Merged && Cand.CanMergeToLSMulti)
 834     Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
 835                                   Opcode, Pred, PredReg, DL, Regs);
 836   if (!Merged)
 837     return nullptr;
 838
 839   // Determine earliest instruction that will get removed. We then keep an
 840   // iterator just above it so the following erases don't invalidated it.
 841   iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
 842   bool EarliestAtBegin = false;
 843   if (EarliestI == MBB.begin()) {
 844     EarliestAtBegin = true;
 845   } else {
 846     EarliestI = std::prev(EarliestI);
 847   }
 848
 849   // Remove instructions which have been merged.
 850   for (MachineInstr *MI : Cand.Instrs)
 851     MBB.erase(MI);
 852
 853   // Determine range between the earliest removed instruction and the new one.
 854   if (EarliestAtBegin)
 855     EarliestI = MBB.begin();
 856   else
 857     EarliestI = std::next(EarliestI);
 858   auto FixupRange = make_range(EarliestI, iterator(Merged));
 859
 860   if (isLoadSingle(Opcode)) {
 861     // If the previous loads defined a super-reg, then we have to mark earlier
 862     // operands undef; Replicate the super-reg def on the merged instruction.
 863     for (MachineInstr &MI : FixupRange) {
 864       for (unsigned &ImpDefReg : ImpDefs) {
 865         for (MachineOperand &MO : MI.implicit_operands()) {
 866           if (!MO.isReg() || MO.getReg() != ImpDefReg)
 867             continue;
 868           if (MO.readsReg())
 869             MO.setIsUndef();
 870           else if (MO.isDef())
 871             ImpDefReg = 0;
 872         }
 873       }
 874     }
 875
 876     MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
 877     for (unsigned ImpDef : ImpDefs)
 878       MIB.addReg(ImpDef, RegState::ImplicitDefine);
 879   } else {
 880     // Remove kill flags: We are possibly storing the values later now.
 881     assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
 882     for (MachineInstr &MI : FixupRange) {
 883       for (MachineOperand &MO : MI.uses()) {
 884         if (!MO.isReg() || !MO.isKill())
 885           continue;
 886         if (UsedRegs.count(MO.getReg()))
 887           MO.setIsKill(false);
 888       }
 889     }
 890     assert(ImpDefs.empty());
 891   }
 892
 893   return Merged;
 894 }
 895
 896 static bool isValidLSDoubleOffset(int Offset) {
 897   unsigned Value = abs(Offset);
 898   // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
 899   // multiplied by 4.
 900   return (Value % 4) == 0 && Value < 1024;
 901 }
 902
 903 /// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
 904 void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
 905   const MachineInstr *FirstMI = MemOps[0].MI;
 906   unsigned Opcode = FirstMI->getOpcode();
 907   bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
 908   unsigned Size = getLSMultipleTransferSize(FirstMI);
 909
 910   unsigned SIndex = 0;
 911   unsigned EIndex = MemOps.size();
 912   do {
 913     // Look at the first instruction.
 914     const MachineInstr *MI = MemOps[SIndex].MI;
 915     int Offset = MemOps[SIndex].Offset;
 916     const MachineOperand &PMO = getLoadStoreRegOp(*MI);
 917     unsigned PReg = PMO.getReg();
 918     unsigned PRegNum = PMO.isUndef() ? UINT_MAX : TRI->getEncodingValue(PReg);
 919     unsigned Latest = SIndex;
 920     unsigned Earliest = SIndex;
 921     unsigned Count = 1;
 922     bool CanMergeToLSDouble =
 923       STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
 924     // ARM errata 602117: LDRD with base in list may result in incorrect base
 925     // register when interrupted or faulted.
 926     if (STI->isCortexM3() && isi32Load(Opcode) &&
 927         PReg == getLoadStoreBaseOp(*MI).getReg())
 928       CanMergeToLSDouble = false;
 929
 930     bool CanMergeToLSMulti = true;
 931     // On swift vldm/vstm starting with an odd register number as that needs
 932     // more uops than single vldrs.
 933     if (STI->isSwift() && !isNotVFP && (PRegNum % 2) == 1)
 934       CanMergeToLSMulti = false;
 935
 936     // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
 937     // deprecated; LDM to PC is fine but cannot happen here.
 938     if (PReg == ARM::SP || PReg == ARM::PC)
 939       CanMergeToLSMulti = CanMergeToLSDouble = false;
 940
 941     // Merge following instructions where possible.
 942     for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
 943       int NewOffset = MemOps[I].Offset;
 944       if (NewOffset != Offset + (int)Size)
 945         break;
 946       const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
 947       unsigned Reg = MO.getReg();
 948       if (Reg == ARM::SP || Reg == ARM::PC)
 949         break;
 950
 951       // See if the current load/store may be part of a multi load/store.
 952       unsigned RegNum = MO.isUndef() ? UINT_MAX : TRI->getEncodingValue(Reg);
 953       bool PartOfLSMulti = CanMergeToLSMulti;
 954       if (PartOfLSMulti) {
 955         // Register numbers must be in ascending order.
 956         if (RegNum <= PRegNum)
 957           PartOfLSMulti = false;
 958         // For VFP / NEON load/store multiples, the registers must be
 959         // consecutive and within the limit on the number of registers per
 960         // instruction.
 961         else if (!isNotVFP && RegNum != PRegNum+1)
 962           PartOfLSMulti = false;
 963       }
 964       // See if the current load/store may be part of a double load/store.
 965       bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
 966
 967       if (!PartOfLSMulti && !PartOfLSDouble)
 968         break;
 969       CanMergeToLSMulti &= PartOfLSMulti;
 970       CanMergeToLSDouble &= PartOfLSDouble;
 971       // Track MemOp with latest and earliest position (Positions are
 972       // counted in reverse).
 973       unsigned Position = MemOps[I].Position;
 974       if (Position < MemOps[Latest].Position)
 975         Latest = I;
 976       else if (Position > MemOps[Earliest].Position)
 977         Earliest = I;
 978       // Prepare for next MemOp.
 979       Offset += Size;
 980       PRegNum = RegNum;
 981     }
 982
 983     // Form a candidate from the Ops collected so far.
 984     MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
 985     for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
 986       Candidate->Instrs.push_back(MemOps[C].MI);
 987     Candidate->LatestMIIdx = Latest - SIndex;
 988     Candidate->EarliestMIIdx = Earliest - SIndex;
 989     Candidate->InsertPos = MemOps[Latest].Position;
 990     if (Count == 1)
 991       CanMergeToLSMulti = CanMergeToLSDouble = false;
 992     Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
 993     Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
 994     Candidates.push_back(Candidate);
 995     // Continue after the chain.
 996     SIndex += Count;
 997   } while (SIndex < EIndex);
 998 }
 999
1000 static bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
1001                                 unsigned Bytes, unsigned Limit,
1002                                 ARMCC::CondCodes Pred, unsigned PredReg) {
1003   unsigned MyPredReg = 0;
1004   if (!MI)
1005     return false;
1006
1007   bool CheckCPSRDef = false;
1008   switch (MI->getOpcode()) {
1009   default: return false;
1010   case ARM::tSUBi8:
1011   case ARM::t2SUBri:
1012   case ARM::SUBri:
1013     CheckCPSRDef = true;
1014     break;
1015   case ARM::tSUBspi:
1016     break;
1017   }
1018
1019   // Make sure the offset fits in 8 bits.
1020   if (Bytes == 0 || (Limit && Bytes >= Limit))
1021     return false;
1022
1023   unsigned Scale = (MI->getOpcode() == ARM::tSUBspi ||
1024                     MI->getOpcode() == ARM::tSUBi8) ? 4 : 1; // FIXME
1025   if (!(MI->getOperand(0).getReg() == Base &&
1026         MI->getOperand(1).getReg() == Base &&
1027         (MI->getOperand(2).getImm() * Scale) == Bytes &&
1028         getInstrPredicate(MI, MyPredReg) == Pred &&
1029         MyPredReg == PredReg))
1030     return false;
1031
1032   return CheckCPSRDef ? !definesCPSR(MI) : true;
1033 }
1034
1035 static bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
1036                                 unsigned Bytes, unsigned Limit,
1037                                 ARMCC::CondCodes Pred, unsigned PredReg) {
1038   unsigned MyPredReg = 0;
1039   if (!MI)
1040     return false;
1041
1042   bool CheckCPSRDef = false;
1043   switch (MI->getOpcode()) {
1044   default: return false;
1045   case ARM::tADDi8:
1046   case ARM::t2ADDri:
1047   case ARM::ADDri:
1048     CheckCPSRDef = true;
1049     break;
1050   case ARM::tADDspi:
1051     break;
1052   }
1053
1054   if (Bytes == 0 || (Limit && Bytes >= Limit))
1055     // Make sure the offset fits in 8 bits.
1056     return false;
1057
1058   unsigned Scale = (MI->getOpcode() == ARM::tADDspi ||
1059                     MI->getOpcode() == ARM::tADDi8) ? 4 : 1; // FIXME
1060   if (!(MI->getOperand(0).getReg() == Base &&
1061         MI->getOperand(1).getReg() == Base &&
1062         (MI->getOperand(2).getImm() * Scale) == Bytes &&
1063         getInstrPredicate(MI, MyPredReg) == Pred &&
1064         MyPredReg == PredReg))
1065     return false;
1066
1067   return CheckCPSRDef ? !definesCPSR(MI) : true;
1068 }
1069
1070 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1071                                             ARM_AM::AMSubMode Mode) {
1072   switch (Opc) {
1073   default: llvm_unreachable("Unhandled opcode!");
1074   case ARM::LDMIA:
1075   case ARM::LDMDA:
1076   case ARM::LDMDB:
1077   case ARM::LDMIB:
1078     switch (Mode) {
1079     default: llvm_unreachable("Unhandled submode!");
1080     case ARM_AM::ia: return ARM::LDMIA_UPD;
1081     case ARM_AM::ib: return ARM::LDMIB_UPD;
1082     case ARM_AM::da: return ARM::LDMDA_UPD;
1083     case ARM_AM::db: return ARM::LDMDB_UPD;
1084     }
1085   case ARM::STMIA:
1086   case ARM::STMDA:
1087   case ARM::STMDB:
1088   case ARM::STMIB:
1089     switch (Mode) {
1090     default: llvm_unreachable("Unhandled submode!");
1091     case ARM_AM::ia: return ARM::STMIA_UPD;
1092     case ARM_AM::ib: return ARM::STMIB_UPD;
1093     case ARM_AM::da: return ARM::STMDA_UPD;
1094     case ARM_AM::db: return ARM::STMDB_UPD;
1095     }
1096   case ARM::t2LDMIA:
1097   case ARM::t2LDMDB:
1098     switch (Mode) {
1099     default: llvm_unreachable("Unhandled submode!");
1100     case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1101     case ARM_AM::db: return ARM::t2LDMDB_UPD;
1102     }
1103   case ARM::t2STMIA:
1104   case ARM::t2STMDB:
1105     switch (Mode) {
1106     default: llvm_unreachable("Unhandled submode!");
1107     case ARM_AM::ia: return ARM::t2STMIA_UPD;
1108     case ARM_AM::db: return ARM::t2STMDB_UPD;
1109     }
1110   case ARM::VLDMSIA:
1111     switch (Mode) {
1112     default: llvm_unreachable("Unhandled submode!");
1113     case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1114     case ARM_AM::db: return ARM::VLDMSDB_UPD;
1115     }
1116   case ARM::VLDMDIA:
1117     switch (Mode) {
1118     default: llvm_unreachable("Unhandled submode!");
1119     case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1120     case ARM_AM::db: return ARM::VLDMDDB_UPD;
1121     }
1122   case ARM::VSTMSIA:
1123     switch (Mode) {
1124     default: llvm_unreachable("Unhandled submode!");
1125     case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1126     case ARM_AM::db: return ARM::VSTMSDB_UPD;
1127     }
1128   case ARM::VSTMDIA:
1129     switch (Mode) {
1130     default: llvm_unreachable("Unhandled submode!");
1131     case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1132     case ARM_AM::db: return ARM::VSTMDDB_UPD;
1133     }
1134   }
1135 }
1136
1137 /// Fold proceeding/trailing inc/dec of base register into the
1138 /// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
1139 ///
1140 /// stmia rn, <ra, rb, rc>
1141 /// rn := rn + 4 * 3;
1142 /// =>
1143 /// stmia rn!, <ra, rb, rc>
1144 ///
1145 /// rn := rn - 4 * 3;
1146 /// ldmia rn, <ra, rb, rc>
1147 /// =>
1148 /// ldmdb rn!, <ra, rb, rc>
1149 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
1150   // Thumb1 is already using updating loads/stores.
1151   if (isThumb1) return false;
1152
1153   const MachineOperand &BaseOP = MI->getOperand(0);
1154   unsigned Base = BaseOP.getReg();
1155   bool BaseKill = BaseOP.isKill();
1156   unsigned Bytes = getLSMultipleTransferSize(MI);
1157   unsigned PredReg = 0;
1158   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1159   unsigned Opcode = MI->getOpcode();
1160   DebugLoc DL = MI->getDebugLoc();
1161
1162   // Can't use an updating ld/st if the base register is also a dest
1163   // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
1164   for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1165     if (MI->getOperand(i).getReg() == Base)
1166       return false;
1167
1168   bool DoMerge = false;
1169   ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1170
1171   // Try merging with the previous instruction.
1172   MachineBasicBlock &MBB = *MI->getParent();
1173   MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1174   MachineBasicBlock::iterator MBBI(MI);
1175   if (MBBI != BeginMBBI) {
1176     MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1177     while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
1178       --PrevMBBI;
1179     if (Mode == ARM_AM::ia &&
1180         isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
1181       Mode = ARM_AM::db;
1182       DoMerge = true;
1183     } else if (Mode == ARM_AM::ib &&
1184                isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
1185       Mode = ARM_AM::da;
1186       DoMerge = true;
1187     }
1188     if (DoMerge)
1189       MBB.erase(PrevMBBI);
1190   }
1191
1192   // Try merging with the next instruction.
1193   MachineBasicBlock::iterator EndMBBI = MBB.end();
1194   if (!DoMerge && MBBI != EndMBBI) {
1195     MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1196     while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
1197       ++NextMBBI;
1198     if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
1199         isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
1200       DoMerge = true;
1201     } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
1202                isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
1203       DoMerge = true;
1204     }
1205     if (DoMerge)
1206       MBB.erase(NextMBBI);
1207   }
1208
1209   if (!DoMerge)
1210     return false;
1211
1212   unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
1213   MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1214     .addReg(Base, getDefRegState(true)) // WB base register
1215     .addReg(Base, getKillRegState(BaseKill))
1216     .addImm(Pred).addReg(PredReg);
1217
1218   // Transfer the rest of operands.
1219   for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
1220     MIB.addOperand(MI->getOperand(OpNum));
1221
1222   // Transfer memoperands.
1223   MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
1224
1225   MBB.erase(MBBI);
1226   return true;
1227 }
1228
1229 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1230                                              ARM_AM::AddrOpc Mode) {
1231   switch (Opc) {
1232   case ARM::LDRi12:
1233     return ARM::LDR_PRE_IMM;
1234   case ARM::STRi12:
1235     return ARM::STR_PRE_IMM;
1236   case ARM::VLDRS:
1237     return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1238   case ARM::VLDRD:
1239     return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1240   case ARM::VSTRS:
1241     return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1242   case ARM::VSTRD:
1243     return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1244   case ARM::t2LDRi8:
1245   case ARM::t2LDRi12:
1246     return ARM::t2LDR_PRE;
1247   case ARM::t2STRi8:
1248   case ARM::t2STRi12:
1249     return ARM::t2STR_PRE;
1250   default: llvm_unreachable("Unhandled opcode!");
1251   }
1252 }
1253
1254 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1255                                               ARM_AM::AddrOpc Mode) {
1256   switch (Opc) {
1257   case ARM::LDRi12:
1258     return ARM::LDR_POST_IMM;
1259   case ARM::STRi12:
1260     return ARM::STR_POST_IMM;
1261   case ARM::VLDRS:
1262     return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1263   case ARM::VLDRD:
1264     return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1265   case ARM::VSTRS:
1266     return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1267   case ARM::VSTRD:
1268     return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1269   case ARM::t2LDRi8:
1270   case ARM::t2LDRi12:
1271     return ARM::t2LDR_POST;
1272   case ARM::t2STRi8:
1273   case ARM::t2STRi12:
1274     return ARM::t2STR_POST;
1275   default: llvm_unreachable("Unhandled opcode!");
1276   }
1277 }
1278
1279 /// Fold proceeding/trailing inc/dec of base register into the
1280 /// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
1281 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
1282   // Thumb1 doesn't have updating LDR/STR.
1283   // FIXME: Use LDM/STM with single register instead.
1284   if (isThumb1) return false;
1285
1286   unsigned Base = getLoadStoreBaseOp(*MI).getReg();
1287   bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
1288   unsigned Bytes = getLSMultipleTransferSize(MI);
1289   unsigned Opcode = MI->getOpcode();
1290   DebugLoc DL = MI->getDebugLoc();
1291   bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
1292                 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
1293   bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
1294   if (isi32Load(Opcode) || isi32Store(Opcode))
1295     if (MI->getOperand(2).getImm() != 0)
1296       return false;
1297   if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
1298     return false;
1299
1300   bool isLd = isLoadSingle(Opcode);
1301   // Can't do the merge if the destination register is the same as the would-be
1302   // writeback register.
1303   if (MI->getOperand(0).getReg() == Base)
1304     return false;
1305
1306   unsigned PredReg = 0;
1307   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1308   bool DoMerge = false;
1309   ARM_AM::AddrOpc AddSub = ARM_AM::add;
1310   unsigned NewOpc = 0;
1311   // AM2 - 12 bits, thumb2 - 8 bits.
1312   unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100);
1313
1314   // Try merging with the previous instruction.
1315   MachineBasicBlock &MBB = *MI->getParent();
1316   MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1317   MachineBasicBlock::iterator MBBI(MI);
1318   if (MBBI != BeginMBBI) {
1319     MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1320     while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
1321       --PrevMBBI;
1322     if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) {
1323       DoMerge = true;
1324       AddSub = ARM_AM::sub;
1325     } else if (!isAM5 &&
1326                isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) {
1327       DoMerge = true;
1328     }
1329     if (DoMerge) {
1330       NewOpc = getPreIndexedLoadStoreOpcode(Opcode, AddSub);
1331       MBB.erase(PrevMBBI);
1332     }
1333   }
1334
1335   // Try merging with the next instruction.
1336   MachineBasicBlock::iterator EndMBBI = MBB.end();
1337   if (!DoMerge && MBBI != EndMBBI) {
1338     MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1339     while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
1340       ++NextMBBI;
1341     if (!isAM5 &&
1342         isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) {
1343       DoMerge = true;
1344       AddSub = ARM_AM::sub;
1345     } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) {
1346       DoMerge = true;
1347     }
1348     if (DoMerge) {
1349       NewOpc = getPostIndexedLoadStoreOpcode(Opcode, AddSub);
1350       MBB.erase(NextMBBI);
1351     }
1352   }
1353
1354   if (!DoMerge)
1355     return false;
1356
1357   if (isAM5) {
1358     // VLDM[SD]_UPD, VSTM[SD]_UPD
1359     // (There are no base-updating versions of VLDR/VSTR instructions, but the
1360     // updating load/store-multiple instructions can be used with only one
1361     // register.)
1362     MachineOperand &MO = MI->getOperand(0);
1363     BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1364       .addReg(Base, getDefRegState(true)) // WB base register
1365       .addReg(Base, getKillRegState(isLd ? BaseKill : false))
1366       .addImm(Pred).addReg(PredReg)
1367       .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
1368                             getKillRegState(MO.isKill())));
1369   } else if (isLd) {
1370     if (isAM2) {
1371       // LDR_PRE, LDR_POST
1372       if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
1373         int Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
1374         BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1375           .addReg(Base, RegState::Define)
1376           .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
1377       } else {
1378         int Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1379         BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1380           .addReg(Base, RegState::Define)
1381           .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
1382       }
1383     } else {
1384       int Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
1385       // t2LDR_PRE, t2LDR_POST
1386       BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1387         .addReg(Base, RegState::Define)
1388         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
1389     }
1390   } else {
1391     MachineOperand &MO = MI->getOperand(0);
1392     // FIXME: post-indexed stores use am2offset_imm, which still encodes
1393     // the vestigal zero-reg offset register. When that's fixed, this clause
1394     // can be removed entirely.
1395     if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
1396       int Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1397       // STR_PRE, STR_POST
1398       BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1399         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1400         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
1401     } else {
1402       int Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
1403       // t2STR_PRE, t2STR_POST
1404       BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1405         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1406         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
1407     }
1408   }
1409   MBB.erase(MBBI);
1410
1411   return true;
1412 }
1413
1414 /// Returns true if instruction is a memory operation that this pass is capable
1415 /// of operating on.
1416 static bool isMemoryOp(const MachineInstr *MI) {
1417   // When no memory operands are present, conservatively assume unaligned,
1418   // volatile, unfoldable.
1419   if (!MI->hasOneMemOperand())
1420     return false;
1421
1422   const MachineMemOperand *MMO = *MI->memoperands_begin();
1423
1424   // Don't touch volatile memory accesses - we may be changing their order.
1425   if (MMO->isVolatile())
1426     return false;
1427
1428   // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1429   // not.
1430   if (MMO->getAlignment() < 4)
1431     return false;
1432
1433   // str <undef> could probably be eliminated entirely, but for now we just want
1434   // to avoid making a mess of it.
1435   // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1436   if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() &&
1437       MI->getOperand(0).isUndef())
1438     return false;
1439
1440   // Likewise don't mess with references to undefined addresses.
1441   if (MI->getNumOperands() > 1 && MI->getOperand(1).isReg() &&
1442       MI->getOperand(1).isUndef())
1443     return false;
1444
1445   unsigned Opcode = MI->getOpcode();
1446   switch (Opcode) {
1447   default: break;
1448   case ARM::VLDRS:
1449   case ARM::VSTRS:
1450     return MI->getOperand(1).isReg();
1451   case ARM::VLDRD:
1452   case ARM::VSTRD:
1453     return MI->getOperand(1).isReg();
1454   case ARM::LDRi12:
1455   case ARM::STRi12:
1456   case ARM::tLDRi:
1457   case ARM::tSTRi:
1458   case ARM::tLDRspi:
1459   case ARM::tSTRspi:
1460   case ARM::t2LDRi8:
1461   case ARM::t2LDRi12:
1462   case ARM::t2STRi8:
1463   case ARM::t2STRi12:
1464     return MI->getOperand(1).isReg();
1465   }
1466   return false;
1467 }
1468
1469 static void InsertLDR_STR(MachineBasicBlock &MBB,
1470                           MachineBasicBlock::iterator &MBBI,
1471                           int Offset, bool isDef,
1472                           DebugLoc DL, unsigned NewOpc,
1473                           unsigned Reg, bool RegDeadKill, bool RegUndef,
1474                           unsigned BaseReg, bool BaseKill, bool BaseUndef,
1475                           bool OffKill, bool OffUndef,
1476                           ARMCC::CondCodes Pred, unsigned PredReg,
1477                           const TargetInstrInfo *TII, bool isT2) {
1478   if (isDef) {
1479     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1480                                       TII->get(NewOpc))
1481       .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1482       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1483     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1484   } else {
1485     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1486                                       TII->get(NewOpc))
1487       .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1488       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1489     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1490   }
1491 }
1492
1493 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1494                                           MachineBasicBlock::iterator &MBBI) {
1495   MachineInstr *MI = &*MBBI;
1496   unsigned Opcode = MI->getOpcode();
1497   if (Opcode != ARM::LDRD && Opcode != ARM::STRD && Opcode != ARM::t2LDRDi8)
1498     return false;
1499
1500   const MachineOperand &BaseOp = MI->getOperand(2);
1501   unsigned BaseReg = BaseOp.getReg();
1502   unsigned EvenReg = MI->getOperand(0).getReg();
1503   unsigned OddReg  = MI->getOperand(1).getReg();
1504   unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1505   unsigned OddRegNum  = TRI->getDwarfRegNum(OddReg, false);
1506
1507   // ARM errata 602117: LDRD with base in list may result in incorrect base
1508   // register when interrupted or faulted.
1509   bool Errata602117 = EvenReg == BaseReg &&
1510     (Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8) && STI->isCortexM3();
1511   // ARM LDRD/STRD needs consecutive registers.
1512   bool NonConsecutiveRegs = (Opcode == ARM::LDRD || Opcode == ARM::STRD) &&
1513     (EvenRegNum % 2 != 0 || EvenRegNum + 1 != OddRegNum);
1514
1515   if (!Errata602117 && !NonConsecutiveRegs)
1516     return false;
1517
1518   bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1519   bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1520   bool EvenDeadKill = isLd ?
1521     MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1522   bool EvenUndef = MI->getOperand(0).isUndef();
1523   bool OddDeadKill  = isLd ?
1524     MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1525   bool OddUndef = MI->getOperand(1).isUndef();
1526   bool BaseKill = BaseOp.isKill();
1527   bool BaseUndef = BaseOp.isUndef();
1528   bool OffKill = isT2 ? false : MI->getOperand(3).isKill();
1529   bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef();
1530   int OffImm = getMemoryOpOffset(MI);
1531   unsigned PredReg = 0;
1532   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1533
1534   if (OddRegNum > EvenRegNum && OffImm == 0) {
1535     // Ascending register numbers and no offset. It's safe to change it to a
1536     // ldm or stm.
1537     unsigned NewOpc = (isLd)
1538       ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1539       : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1540     if (isLd) {
1541       BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1542         .addReg(BaseReg, getKillRegState(BaseKill))
1543         .addImm(Pred).addReg(PredReg)
1544         .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1545         .addReg(OddReg,  getDefRegState(isLd) | getDeadRegState(OddDeadKill));
1546       ++NumLDRD2LDM;
1547     } else {
1548       BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1549         .addReg(BaseReg, getKillRegState(BaseKill))
1550         .addImm(Pred).addReg(PredReg)
1551         .addReg(EvenReg,
1552                 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1553         .addReg(OddReg,
1554                 getKillRegState(OddDeadKill)  | getUndefRegState(OddUndef));
1555       ++NumSTRD2STM;
1556     }
1557   } else {
1558     // Split into two instructions.
1559     unsigned NewOpc = (isLd)
1560       ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1561       : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1562     // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1563     // so adjust and use t2LDRi12 here for that.
1564     unsigned NewOpc2 = (isLd)
1565       ? (isT2 ? (OffImm+4 < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1566       : (isT2 ? (OffImm+4 < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1567     DebugLoc dl = MBBI->getDebugLoc();
1568     // If this is a load and base register is killed, it may have been
1569     // re-defed by the load, make sure the first load does not clobber it.
1570     if (isLd &&
1571         (BaseKill || OffKill) &&
1572         (TRI->regsOverlap(EvenReg, BaseReg))) {
1573       assert(!TRI->regsOverlap(OddReg, BaseReg));
1574       InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc2,
1575                     OddReg, OddDeadKill, false,
1576                     BaseReg, false, BaseUndef, false, OffUndef,
1577                     Pred, PredReg, TII, isT2);
1578       InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1579                     EvenReg, EvenDeadKill, false,
1580                     BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1581                     Pred, PredReg, TII, isT2);
1582     } else {
1583       if (OddReg == EvenReg && EvenDeadKill) {
1584         // If the two source operands are the same, the kill marker is
1585         // probably on the first one. e.g.
1586         // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0
1587         EvenDeadKill = false;
1588         OddDeadKill = true;
1589       }
1590       // Never kill the base register in the first instruction.
1591       if (EvenReg == BaseReg)
1592         EvenDeadKill = false;
1593       InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1594                     EvenReg, EvenDeadKill, EvenUndef,
1595                     BaseReg, false, BaseUndef, false, OffUndef,
1596                     Pred, PredReg, TII, isT2);
1597       InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc2,
1598                     OddReg, OddDeadKill, OddUndef,
1599                     BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1600                     Pred, PredReg, TII, isT2);
1601     }
1602     if (isLd)
1603       ++NumLDRD2LDR;
1604     else
1605       ++NumSTRD2STR;
1606   }
1607
1608   MBBI = MBB.erase(MBBI);
1609   return true;
1610 }
1611
1612 /// An optimization pass to turn multiple LDR / STR ops of the same base and
1613 /// incrementing offset into LDM / STM ops.
1614 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1615   MemOpQueue MemOps;
1616   unsigned CurrBase = 0;
1617   unsigned CurrOpc = ~0u;
1618   ARMCC::CondCodes CurrPred = ARMCC::AL;
1619   unsigned Position = 0;
1620   assert(Candidates.size() == 0);
1621   LiveRegsValid = false;
1622
1623   for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1624        I = MBBI) {
1625     // The instruction in front of the iterator is the one we look at.
1626     MBBI = std::prev(I);
1627     if (FixInvalidRegPairOp(MBB, MBBI))
1628       continue;
1629     ++Position;
1630
1631     if (isMemoryOp(MBBI)) {
1632       unsigned Opcode = MBBI->getOpcode();
1633       const MachineOperand &MO = MBBI->getOperand(0);
1634       unsigned Reg = MO.getReg();
1635       unsigned Base = getLoadStoreBaseOp(*MBBI).getReg();
1636       unsigned PredReg = 0;
1637       ARMCC::CondCodes Pred = getInstrPredicate(MBBI, PredReg);
1638       int Offset = getMemoryOpOffset(MBBI);
1639       if (CurrBase == 0) {
1640         // Start of a new chain.
1641         CurrBase = Base;
1642         CurrOpc  = Opcode;
1643         CurrPred = Pred;
1644         MemOps.push_back(MemOpQueueEntry(MBBI, Offset, Position));
1645         continue;
1646       }
1647       // Note: No need to match PredReg in the next if.
1648       if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1649         // Watch out for:
1650         //   r4 := ldr [r0, #8]
1651         //   r4 := ldr [r0, #4]
1652         // or
1653         //   r0 := ldr [r0]
1654         // If a load overrides the base register or a register loaded by
1655         // another load in our chain, we cannot take this instruction.
1656         bool Overlap = false;
1657         if (isLoadSingle(Opcode)) {
1658           Overlap = (Base == Reg);
1659           if (!Overlap) {
1660             for (const MemOpQueueEntry &E : MemOps) {
1661               if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1662                 Overlap = true;
1663                 break;
1664               }
1665             }
1666           }
1667         }
1668
1669         if (!Overlap) {
1670           // Check offset and sort memory operation into the current chain.
1671           if (Offset > MemOps.back().Offset) {
1672             MemOps.push_back(MemOpQueueEntry(MBBI, Offset, Position));
1673             continue;
1674           } else {
1675             MemOpQueue::iterator MI, ME;
1676             for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; ++MI) {
1677               if (Offset < MI->Offset) {
1678                 // Found a place to insert.
1679                 break;
1680               }
1681               if (Offset == MI->Offset) {
1682                 // Collision, abort.
1683                 MI = ME;
1684                 break;
1685               }
1686             }
1687             if (MI != MemOps.end()) {
1688               MemOps.insert(MI, MemOpQueueEntry(MBBI, Offset, Position));
1689               continue;
1690             }
1691           }
1692         }
1693       }
1694
1695       // Don't advance the iterator; The op will start a new chain next.
1696       MBBI = I;
1697       --Position;
1698       // Fallthrough to look into existing chain.
1699     } else if (MBBI->isDebugValue())
1700       continue;
1701
1702     // If we are here then the chain is broken; Extract candidates for a merge.
1703     if (MemOps.size() > 0) {
1704       FormCandidates(MemOps);
1705       // Reset for the next chain.
1706       CurrBase = 0;
1707       CurrOpc = ~0u;
1708       CurrPred = ARMCC::AL;
1709       MemOps.clear();
1710     }
1711   }
1712   if (MemOps.size() > 0)
1713     FormCandidates(MemOps);
1714
1715   // Sort candidates so they get processed from end to begin of the basic
1716   // block later; This is necessary for liveness calculation.
1717   auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1718     return M0->InsertPos < M1->InsertPos;
1719   };
1720   std::sort(Candidates.begin(), Candidates.end(), LessThan);
1721
1722   // Go through list of candidates and merge.
1723   bool Changed = false;
1724   for (const MergeCandidate *Candidate : Candidates) {
1725     if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
1726       MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1727       // Merge preceding/trailing base inc/dec into the merged op.
1728       if (Merged) {
1729         Changed = true;
1730         unsigned Opcode = Merged->getOpcode();
1731         if (Opcode != ARM::t2STRDi8 && Opcode != ARM::t2LDRDi8)
1732           MergeBaseUpdateLSMultiple(Merged);
1733       } else {
1734         for (MachineInstr *MI : Candidate->Instrs) {
1735           if (MergeBaseUpdateLoadStore(MI))
1736             Changed = true;
1737         }
1738       }
1739     } else {
1740       assert(Candidate->Instrs.size() == 1);
1741       if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1742         Changed = true;
1743     }
1744   }
1745   Candidates.clear();
1746
1747   return Changed;
1748 }
1749
1750 /// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
1751 /// into the preceding stack restore so it directly restore the value of LR
1752 /// into pc.
1753 ///   ldmfd sp!, {..., lr}
1754 ///   bx lr
1755 /// or
1756 ///   ldmfd sp!, {..., lr}
1757 ///   mov pc, lr
1758 /// =>
1759 ///   ldmfd sp!, {..., pc}
1760 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1761   // Thumb1 LDM doesn't allow high registers.
1762   if (isThumb1) return false;
1763   if (MBB.empty()) return false;
1764
1765   MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1766   if (MBBI != MBB.begin() &&
1767       (MBBI->getOpcode() == ARM::BX_RET ||
1768        MBBI->getOpcode() == ARM::tBX_RET ||
1769        MBBI->getOpcode() == ARM::MOVPCLR)) {
1770     MachineInstr *PrevMI = std::prev(MBBI);
1771     unsigned Opcode = PrevMI->getOpcode();
1772     if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1773         Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1774         Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
1775       MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
1776       if (MO.getReg() != ARM::LR)
1777         return false;
1778       unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1779       assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1780               Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1781       PrevMI->setDesc(TII->get(NewOpc));
1782       MO.setReg(ARM::PC);
1783       PrevMI->copyImplicitOps(*MBB.getParent(), &*MBBI);
1784       MBB.erase(MBBI);
1785       return true;
1786     }
1787   }
1788   return false;
1789 }
1790
1791 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1792   MF = &Fn;
1793   STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
1794   TL = STI->getTargetLowering();
1795   AFI = Fn.getInfo<ARMFunctionInfo>();
1796   TII = STI->getInstrInfo();
1797   TRI = STI->getRegisterInfo();
1798   MRI = &Fn.getRegInfo();
1799   RegClassInfoValid = false;
1800   isThumb2 = AFI->isThumb2Function();
1801   isThumb1 = AFI->isThumbFunction() && !isThumb2;
1802
1803   bool Modified = false;
1804   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1805        ++MFI) {
1806     MachineBasicBlock &MBB = *MFI;
1807     Modified |= LoadStoreMultipleOpti(MBB);
1808     if (STI->hasV5TOps())
1809       Modified |= MergeReturnIntoLDM(MBB);
1810   }
1811
1812   Allocator.DestroyAll();
1813   return Modified;
1814 }
1815
1816 namespace {
1817   /// Pre- register allocation pass that move load / stores from consecutive
1818   /// locations close to make it more likely they will be combined later.
1819   struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
1820     static char ID;
1821     ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
1822
1823     const DataLayout *TD;
1824     const TargetInstrInfo *TII;
1825     const TargetRegisterInfo *TRI;
1826     const ARMSubtarget *STI;
1827     MachineRegisterInfo *MRI;
1828     MachineFunction *MF;
1829
1830     bool runOnMachineFunction(MachineFunction &Fn) override;
1831
1832     const char *getPassName() const override {
1833       return "ARM pre- register allocation load / store optimization pass";
1834     }
1835
1836   private:
1837     bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
1838                           unsigned &NewOpc, unsigned &EvenReg,
1839                           unsigned &OddReg, unsigned &BaseReg,
1840                           int &Offset,
1841                           unsigned &PredReg, ARMCC::CondCodes &Pred,
1842                           bool &isT2);
1843     bool RescheduleOps(MachineBasicBlock *MBB,
1844                        SmallVectorImpl<MachineInstr *> &Ops,
1845                        unsigned Base, bool isLd,
1846                        DenseMap<MachineInstr*, unsigned> &MI2LocMap);
1847     bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
1848   };
1849   char ARMPreAllocLoadStoreOpt::ID = 0;
1850 }
1851
1852 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1853   TD = &Fn.getDataLayout();
1854   STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
1855   TII = STI->getInstrInfo();
1856   TRI = STI->getRegisterInfo();
1857   MRI = &Fn.getRegInfo();
1858   MF  = &Fn;
1859
1860   bool Modified = false;
1861   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1862        ++MFI)
1863     Modified |= RescheduleLoadStoreInstrs(MFI);
1864
1865   return Modified;
1866 }
1867
1868 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
1869                                       MachineBasicBlock::iterator I,
1870                                       MachineBasicBlock::iterator E,
1871                                       SmallPtrSetImpl<MachineInstr*> &MemOps,
1872                                       SmallSet<unsigned, 4> &MemRegs,
1873                                       const TargetRegisterInfo *TRI) {
1874   // Are there stores / loads / calls between them?
1875   // FIXME: This is overly conservative. We should make use of alias information
1876   // some day.
1877   SmallSet<unsigned, 4> AddedRegPressure;
1878   while (++I != E) {
1879     if (I->isDebugValue() || MemOps.count(&*I))
1880       continue;
1881     if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
1882       return false;
1883     if (isLd && I->mayStore())
1884       return false;
1885     if (!isLd) {
1886       if (I->mayLoad())
1887         return false;
1888       // It's not safe to move the first 'str' down.
1889       // str r1, [r0]
1890       // strh r5, [r0]
1891       // str r4, [r0, #+4]
1892       if (I->mayStore())
1893         return false;
1894     }
1895     for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
1896       MachineOperand &MO = I->getOperand(j);
1897       if (!MO.isReg())
1898         continue;
1899       unsigned Reg = MO.getReg();
1900       if (MO.isDef() && TRI->regsOverlap(Reg, Base))
1901         return false;
1902       if (Reg != Base && !MemRegs.count(Reg))
1903         AddedRegPressure.insert(Reg);
1904     }
1905   }
1906
1907   // Estimate register pressure increase due to the transformation.
1908   if (MemRegs.size() <= 4)
1909     // Ok if we are moving small number of instructions.
1910     return true;
1911   return AddedRegPressure.size() <= MemRegs.size() * 2;
1912 }
1913
1914
1915 /// Copy \p Op0 and \p Op1 operands into a new array assigned to MI.
1916 static void concatenateMemOperands(MachineInstr *MI, MachineInstr *Op0,
1917                                    MachineInstr *Op1) {
1918   assert(MI->memoperands_empty() && "expected a new machineinstr");
1919   size_t numMemRefs = (Op0->memoperands_end() - Op0->memoperands_begin())
1920     + (Op1->memoperands_end() - Op1->memoperands_begin());
1921
1922   MachineFunction *MF = MI->getParent()->getParent();
1923   MachineSDNode::mmo_iterator MemBegin = MF->allocateMemRefsArray(numMemRefs);
1924   MachineSDNode::mmo_iterator MemEnd =
1925     std::copy(Op0->memoperands_begin(), Op0->memoperands_end(), MemBegin);
1926   MemEnd =
1927     std::copy(Op1->memoperands_begin(), Op1->memoperands_end(), MemEnd);
1928   MI->setMemRefs(MemBegin, MemEnd);
1929 }
1930
1931 bool
1932 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
1933                                           DebugLoc &dl, unsigned &NewOpc,
1934                                           unsigned &FirstReg,
1935                                           unsigned &SecondReg,
1936                                           unsigned &BaseReg, int &Offset,
1937                                           unsigned &PredReg,
1938                                           ARMCC::CondCodes &Pred,
1939                                           bool &isT2) {
1940   // Make sure we're allowed to generate LDRD/STRD.
1941   if (!STI->hasV5TEOps())
1942     return false;
1943
1944   // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
1945   unsigned Scale = 1;
1946   unsigned Opcode = Op0->getOpcode();
1947   if (Opcode == ARM::LDRi12) {
1948     NewOpc = ARM::LDRD;
1949   } else if (Opcode == ARM::STRi12) {
1950     NewOpc = ARM::STRD;
1951   } else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
1952     NewOpc = ARM::t2LDRDi8;
1953     Scale = 4;
1954     isT2 = true;
1955   } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
1956     NewOpc = ARM::t2STRDi8;
1957     Scale = 4;
1958     isT2 = true;
1959   } else {
1960     return false;
1961   }
1962
1963   // Make sure the base address satisfies i64 ld / st alignment requirement.
1964   // At the moment, we ignore the memoryoperand's value.
1965   // If we want to use AliasAnalysis, we should check it accordingly.
1966   if (!Op0->hasOneMemOperand() ||
1967       (*Op0->memoperands_begin())->isVolatile())
1968     return false;
1969
1970   unsigned Align = (*Op0->memoperands_begin())->getAlignment();
1971   const Function *Func = MF->getFunction();
1972   unsigned ReqAlign = STI->hasV6Ops()
1973     ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext()))
1974     : 8;  // Pre-v6 need 8-byte align
1975   if (Align < ReqAlign)
1976     return false;
1977
1978   // Then make sure the immediate offset fits.
1979   int OffImm = getMemoryOpOffset(Op0);
1980   if (isT2) {
1981     int Limit = (1 << 8) * Scale;
1982     if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
1983       return false;
1984     Offset = OffImm;
1985   } else {
1986     ARM_AM::AddrOpc AddSub = ARM_AM::add;
1987     if (OffImm < 0) {
1988       AddSub = ARM_AM::sub;
1989       OffImm = - OffImm;
1990     }
1991     int Limit = (1 << 8) * Scale;
1992     if (OffImm >= Limit || (OffImm & (Scale-1)))
1993       return false;
1994     Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
1995   }
1996   FirstReg = Op0->getOperand(0).getReg();
1997   SecondReg = Op1->getOperand(0).getReg();
1998   if (FirstReg == SecondReg)
1999     return false;
2000   BaseReg = Op0->getOperand(1).getReg();
2001   Pred = getInstrPredicate(Op0, PredReg);
2002   dl = Op0->getDebugLoc();
2003   return true;
2004 }
2005
2006 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
2007                                  SmallVectorImpl<MachineInstr *> &Ops,
2008                                  unsigned Base, bool isLd,
2009                                  DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2010   bool RetVal = false;
2011
2012   // Sort by offset (in reverse order).
2013   std::sort(Ops.begin(), Ops.end(),
2014             [](const MachineInstr *LHS, const MachineInstr *RHS) {
2015     int LOffset = getMemoryOpOffset(LHS);
2016     int ROffset = getMemoryOpOffset(RHS);
2017     assert(LHS == RHS || LOffset != ROffset);
2018     return LOffset > ROffset;
2019   });
2020
2021   // The loads / stores of the same base are in order. Scan them from first to
2022   // last and check for the following:
2023   // 1. Any def of base.
2024   // 2. Any gaps.
2025   while (Ops.size() > 1) {
2026     unsigned FirstLoc = ~0U;
2027     unsigned LastLoc = 0;
2028     MachineInstr *FirstOp = nullptr;
2029     MachineInstr *LastOp = nullptr;
2030     int LastOffset = 0;
2031     unsigned LastOpcode = 0;
2032     unsigned LastBytes = 0;
2033     unsigned NumMove = 0;
2034     for (int i = Ops.size() - 1; i >= 0; --i) {
2035       MachineInstr *Op = Ops[i];
2036       unsigned Loc = MI2LocMap[Op];
2037       if (Loc <= FirstLoc) {
2038         FirstLoc = Loc;
2039         FirstOp = Op;
2040       }
2041       if (Loc >= LastLoc) {
2042         LastLoc = Loc;
2043         LastOp = Op;
2044       }
2045
2046       unsigned LSMOpcode
2047         = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2048       if (LastOpcode && LSMOpcode != LastOpcode)
2049         break;
2050
2051       int Offset = getMemoryOpOffset(Op);
2052       unsigned Bytes = getLSMultipleTransferSize(Op);
2053       if (LastBytes) {
2054         if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2055           break;
2056       }
2057       LastOffset = Offset;
2058       LastBytes = Bytes;
2059       LastOpcode = LSMOpcode;
2060       if (++NumMove == 8) // FIXME: Tune this limit.
2061         break;
2062     }
2063
2064     if (NumMove <= 1)
2065       Ops.pop_back();
2066     else {
2067       SmallPtrSet<MachineInstr*, 4> MemOps;
2068       SmallSet<unsigned, 4> MemRegs;
2069       for (int i = NumMove-1; i >= 0; --i) {
2070         MemOps.insert(Ops[i]);
2071         MemRegs.insert(Ops[i]->getOperand(0).getReg());
2072       }
2073
2074       // Be conservative, if the instructions are too far apart, don't
2075       // move them. We want to limit the increase of register pressure.
2076       bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
2077       if (DoMove)
2078         DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2079                                            MemOps, MemRegs, TRI);
2080       if (!DoMove) {
2081         for (unsigned i = 0; i != NumMove; ++i)
2082           Ops.pop_back();
2083       } else {
2084         // This is the new location for the loads / stores.
2085         MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
2086         while (InsertPos != MBB->end()
2087                && (MemOps.count(InsertPos) || InsertPos->isDebugValue()))
2088           ++InsertPos;
2089
2090         // If we are moving a pair of loads / stores, see if it makes sense
2091         // to try to allocate a pair of registers that can form register pairs.
2092         MachineInstr *Op0 = Ops.back();
2093         MachineInstr *Op1 = Ops[Ops.size()-2];
2094         unsigned FirstReg = 0, SecondReg = 0;
2095         unsigned BaseReg = 0, PredReg = 0;
2096         ARMCC::CondCodes Pred = ARMCC::AL;
2097         bool isT2 = false;
2098         unsigned NewOpc = 0;
2099         int Offset = 0;
2100         DebugLoc dl;
2101         if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
2102                                              FirstReg, SecondReg, BaseReg,
2103                                              Offset, PredReg, Pred, isT2)) {
2104           Ops.pop_back();
2105           Ops.pop_back();
2106
2107           const MCInstrDesc &MCID = TII->get(NewOpc);
2108           const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2109           MRI->constrainRegClass(FirstReg, TRC);
2110           MRI->constrainRegClass(SecondReg, TRC);
2111
2112           // Form the pair instruction.
2113           if (isLd) {
2114             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2115               .addReg(FirstReg, RegState::Define)
2116               .addReg(SecondReg, RegState::Define)
2117               .addReg(BaseReg);
2118             // FIXME: We're converting from LDRi12 to an insn that still
2119             // uses addrmode2, so we need an explicit offset reg. It should
2120             // always by reg0 since we're transforming LDRi12s.
2121             if (!isT2)
2122               MIB.addReg(0);
2123             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2124             concatenateMemOperands(MIB, Op0, Op1);
2125             DEBUG(dbgs() << "Formed " << *MIB << "\n");
2126             ++NumLDRDFormed;
2127           } else {
2128             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2129               .addReg(FirstReg)
2130               .addReg(SecondReg)
2131               .addReg(BaseReg);
2132             // FIXME: We're converting from LDRi12 to an insn that still
2133             // uses addrmode2, so we need an explicit offset reg. It should
2134             // always by reg0 since we're transforming STRi12s.
2135             if (!isT2)
2136               MIB.addReg(0);
2137             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2138             concatenateMemOperands(MIB, Op0, Op1);
2139             DEBUG(dbgs() << "Formed " << *MIB << "\n");
2140             ++NumSTRDFormed;
2141           }
2142           MBB->erase(Op0);
2143           MBB->erase(Op1);
2144
2145           if (!isT2) {
2146             // Add register allocation hints to form register pairs.
2147             MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2148             MRI->setRegAllocationHint(SecondReg,  ARMRI::RegPairOdd, FirstReg);
2149           }
2150         } else {
2151           for (unsigned i = 0; i != NumMove; ++i) {
2152             MachineInstr *Op = Ops.back();
2153             Ops.pop_back();
2154             MBB->splice(InsertPos, MBB, Op);
2155           }
2156         }
2157
2158         NumLdStMoved += NumMove;
2159         RetVal = true;
2160       }
2161     }
2162   }
2163
2164   return RetVal;
2165 }
2166
2167 bool
2168 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2169   bool RetVal = false;
2170
2171   DenseMap<MachineInstr*, unsigned> MI2LocMap;
2172   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
2173   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
2174   SmallVector<unsigned, 4> LdBases;
2175   SmallVector<unsigned, 4> StBases;
2176
2177   unsigned Loc = 0;
2178   MachineBasicBlock::iterator MBBI = MBB->begin();
2179   MachineBasicBlock::iterator E = MBB->end();
2180   while (MBBI != E) {
2181     for (; MBBI != E; ++MBBI) {
2182       MachineInstr *MI = MBBI;
2183       if (MI->isCall() || MI->isTerminator()) {
2184         // Stop at barriers.
2185         ++MBBI;
2186         break;
2187       }
2188
2189       if (!MI->isDebugValue())
2190         MI2LocMap[MI] = ++Loc;
2191
2192       if (!isMemoryOp(MI))
2193         continue;
2194       unsigned PredReg = 0;
2195       if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
2196         continue;
2197
2198       int Opc = MI->getOpcode();
2199       bool isLd = isLoadSingle(Opc);
2200       unsigned Base = MI->getOperand(1).getReg();
2201       int Offset = getMemoryOpOffset(MI);
2202
2203       bool StopHere = false;
2204       if (isLd) {
2205         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
2206           Base2LdsMap.find(Base);
2207         if (BI != Base2LdsMap.end()) {
2208           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2209             if (Offset == getMemoryOpOffset(BI->second[i])) {
2210               StopHere = true;
2211               break;
2212             }
2213           }
2214           if (!StopHere)
2215             BI->second.push_back(MI);
2216         } else {
2217           Base2LdsMap[Base].push_back(MI);
2218           LdBases.push_back(Base);
2219         }
2220       } else {
2221         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
2222           Base2StsMap.find(Base);
2223         if (BI != Base2StsMap.end()) {
2224           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2225             if (Offset == getMemoryOpOffset(BI->second[i])) {
2226               StopHere = true;
2227               break;
2228             }
2229           }
2230           if (!StopHere)
2231             BI->second.push_back(MI);
2232         } else {
2233           Base2StsMap[Base].push_back(MI);
2234           StBases.push_back(Base);
2235         }
2236       }
2237
2238       if (StopHere) {
2239         // Found a duplicate (a base+offset combination that's seen earlier).
2240         // Backtrack.
2241         --Loc;
2242         break;
2243       }
2244     }
2245
2246     // Re-schedule loads.
2247     for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
2248       unsigned Base = LdBases[i];
2249       SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
2250       if (Lds.size() > 1)
2251         RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2252     }
2253
2254     // Re-schedule stores.
2255     for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
2256       unsigned Base = StBases[i];
2257       SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
2258       if (Sts.size() > 1)
2259         RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2260     }
2261
2262     if (MBBI != E) {
2263       Base2LdsMap.clear();
2264       Base2StsMap.clear();
2265       LdBases.clear();
2266       StBases.clear();
2267     }
2268   }
2269
2270   return RetVal;
2271 }
2272
2273
2274 /// Returns an instance of the load / store optimization pass.
2275 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2276   if (PreAlloc)
2277     return new ARMPreAllocLoadStoreOpt();
2278   return new ARMLoadStoreOpt();
2279 }