lib/Target/ARM/ARMLoadStoreOptimizer.cpp

   1 //===-- ARMLoadStoreOptimizer.cpp - ARM 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 #define DEBUG_TYPE "arm-ldst-opt"
  16 #include "ARM.h"
  17 #include "ARMAddressingModes.h"
  18 #include "ARMBaseInstrInfo.h"
  19 #include "ARMMachineFunctionInfo.h"
  20 #include "ARMRegisterInfo.h"
  21 #include "llvm/DerivedTypes.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/MachineFunctionPass.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/MachineRegisterInfo.h"
  28 #include "llvm/CodeGen/RegisterScavenging.h"
  29 #include "llvm/Target/TargetData.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetMachine.h"
  32 #include "llvm/Target/TargetRegisterInfo.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include "llvm/ADT/DenseMap.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include "llvm/ADT/SmallPtrSet.h"
  37 #include "llvm/ADT/SmallSet.h"
  38 #include "llvm/ADT/SmallVector.h"
  39 #include "llvm/ADT/Statistic.h"
  40 using namespace llvm;
  41
  42 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
  43 STATISTIC(NumSTMGened , "Number of stm instructions generated");
  44 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
  45 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
  46 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
  47 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
  48 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
  49 STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
  50 STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
  51 STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
  52 STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");
  53
  54 /// ARMAllocLoadStoreOpt - Post- register allocation pass the combine
  55 /// load / store instructions to form ldm / stm instructions.
  56
  57 namespace {
  58   struct ARMLoadStoreOpt : public MachineFunctionPass {
  59     static char ID;
  60     ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
  61
  62     const TargetInstrInfo *TII;
  63     const TargetRegisterInfo *TRI;
  64     ARMFunctionInfo *AFI;
  65     RegScavenger *RS;
  66     bool isThumb2;
  67
  68     virtual bool runOnMachineFunction(MachineFunction &Fn);
  69
  70     virtual const char *getPassName() const {
  71       return "ARM load / store optimization pass";
  72     }
  73
  74   private:
  75     struct MemOpQueueEntry {
  76       int Offset;
  77       unsigned Reg;
  78       bool isKill;
  79       unsigned Position;
  80       MachineBasicBlock::iterator MBBI;
  81       bool Merged;
  82       MemOpQueueEntry(int o, unsigned r, bool k, unsigned p,
  83                       MachineBasicBlock::iterator i)
  84         : Offset(o), Reg(r), isKill(k), Position(p), MBBI(i), Merged(false) {}
  85     };
  86     typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
  87     typedef MemOpQueue::iterator MemOpQueueIter;
  88
  89     bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
  90                   int Offset, unsigned Base, bool BaseKill, int Opcode,
  91                   ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
  92                   DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs);
  93     void MergeOpsUpdate(MachineBasicBlock &MBB,
  94                         MemOpQueue &MemOps,
  95                         unsigned memOpsBegin,
  96                         unsigned memOpsEnd,
  97                         unsigned insertAfter,
  98                         int Offset,
  99                         unsigned Base,
 100                         bool BaseKill,
 101                         int Opcode,
 102                         ARMCC::CondCodes Pred,
 103                         unsigned PredReg,
 104                         unsigned Scratch,
 105                         DebugLoc dl,
 106                         SmallVector<MachineBasicBlock::iterator, 4> &Merges);
 107     void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
 108                       int Opcode, unsigned Size,
 109                       ARMCC::CondCodes Pred, unsigned PredReg,
 110                       unsigned Scratch, MemOpQueue &MemOps,
 111                       SmallVector<MachineBasicBlock::iterator, 4> &Merges);
 112
 113     void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
 114     bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
 115                              MachineBasicBlock::iterator &MBBI);
 116     bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
 117                                   MachineBasicBlock::iterator MBBI,
 118                                   const TargetInstrInfo *TII,
 119                                   bool &Advance,
 120                                   MachineBasicBlock::iterator &I);
 121     bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
 122                                    MachineBasicBlock::iterator MBBI,
 123                                    bool &Advance,
 124                                    MachineBasicBlock::iterator &I);
 125     bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
 126     bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
 127   };
 128   char ARMLoadStoreOpt::ID = 0;
 129 }
 130
 131 static int getLoadStoreMultipleOpcode(int Opcode) {
 132   switch (Opcode) {
 133   case ARM::LDRi12:
 134     ++NumLDMGened;
 135     return ARM::LDM;
 136   case ARM::STR:
 137     ++NumSTMGened;
 138     return ARM::STM;
 139   case ARM::t2LDRi8:
 140   case ARM::t2LDRi12:
 141     ++NumLDMGened;
 142     return ARM::t2LDM;
 143   case ARM::t2STRi8:
 144   case ARM::t2STRi12:
 145     ++NumSTMGened;
 146     return ARM::t2STM;
 147   case ARM::VLDRS:
 148     ++NumVLDMGened;
 149     return ARM::VLDMS;
 150   case ARM::VSTRS:
 151     ++NumVSTMGened;
 152     return ARM::VSTMS;
 153   case ARM::VLDRD:
 154     ++NumVLDMGened;
 155     return ARM::VLDMD;
 156   case ARM::VSTRD:
 157     ++NumVSTMGened;
 158     return ARM::VSTMD;
 159   default: llvm_unreachable("Unhandled opcode!");
 160   }
 161   return 0;
 162 }
 163
 164 static bool isT2i32Load(unsigned Opc) {
 165   return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
 166 }
 167
 168 static bool isi32Load(unsigned Opc) {
 169   return Opc == ARM::LDRi12 || isT2i32Load(Opc);
 170 }
 171
 172 static bool isT2i32Store(unsigned Opc) {
 173   return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
 174 }
 175
 176 static bool isi32Store(unsigned Opc) {
 177   return Opc == ARM::STR || isT2i32Store(Opc);
 178 }
 179
 180 /// MergeOps - Create and insert a LDM or STM with Base as base register and
 181 /// registers in Regs as the register operands that would be loaded / stored.
 182 /// It returns true if the transformation is done.
 183 bool
 184 ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
 185                           MachineBasicBlock::iterator MBBI,
 186                           int Offset, unsigned Base, bool BaseKill,
 187                           int Opcode, ARMCC::CondCodes Pred,
 188                           unsigned PredReg, unsigned Scratch, DebugLoc dl,
 189                           SmallVector<std::pair<unsigned, bool>, 8> &Regs) {
 190   // Only a single register to load / store. Don't bother.
 191   unsigned NumRegs = Regs.size();
 192   if (NumRegs <= 1)
 193     return false;
 194
 195   ARM_AM::AMSubMode Mode = ARM_AM::ia;
 196   // VFP and Thumb2 do not support IB or DA modes.
 197   bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
 198   bool haveIBAndDA = isNotVFP && !isThumb2;
 199   if (Offset == 4 && haveIBAndDA)
 200     Mode = ARM_AM::ib;
 201   else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA)
 202     Mode = ARM_AM::da;
 203   else if (Offset == -4 * (int)NumRegs && isNotVFP)
 204     // VLDM/VSTM do not support DB mode without also updating the base reg.
 205     Mode = ARM_AM::db;
 206   else if (Offset != 0) {
 207     // If starting offset isn't zero, insert a MI to materialize a new base.
 208     // But only do so if it is cost effective, i.e. merging more than two
 209     // loads / stores.
 210     if (NumRegs <= 2)
 211       return false;
 212
 213     unsigned NewBase;
 214     if (isi32Load(Opcode))
 215       // If it is a load, then just use one of the destination register to
 216       // use as the new base.
 217       NewBase = Regs[NumRegs-1].first;
 218     else {
 219       // Use the scratch register to use as a new base.
 220       NewBase = Scratch;
 221       if (NewBase == 0)
 222         return false;
 223     }
 224     int BaseOpc = !isThumb2
 225       ? ARM::ADDri
 226       : ((Base == ARM::SP) ? ARM::t2ADDrSPi : ARM::t2ADDri);
 227     if (Offset < 0) {
 228       BaseOpc = !isThumb2
 229         ? ARM::SUBri
 230         : ((Base == ARM::SP) ? ARM::t2SUBrSPi : ARM::t2SUBri);
 231       Offset = - Offset;
 232     }
 233     int ImmedOffset = isThumb2
 234       ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset);
 235     if (ImmedOffset == -1)
 236       // FIXME: Try t2ADDri12 or t2SUBri12?
 237       return false;  // Probably not worth it then.
 238
 239     BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase)
 240       .addReg(Base, getKillRegState(BaseKill)).addImm(Offset)
 241       .addImm(Pred).addReg(PredReg).addReg(0);
 242     Base = NewBase;
 243     BaseKill = true;  // New base is always killed right its use.
 244   }
 245
 246   bool isDef = (isi32Load(Opcode) || Opcode == ARM::VLDRS ||
 247                 Opcode == ARM::VLDRD);
 248   Opcode = getLoadStoreMultipleOpcode(Opcode);
 249   MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(Opcode))
 250     .addReg(Base, getKillRegState(BaseKill))
 251     .addImm(ARM_AM::getAM4ModeImm(Mode)).addImm(Pred).addReg(PredReg);
 252   for (unsigned i = 0; i != NumRegs; ++i)
 253     MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef)
 254                      | getKillRegState(Regs[i].second));
 255
 256   return true;
 257 }
 258
 259 // MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on
 260 // success.
 261 void ARMLoadStoreOpt::MergeOpsUpdate(MachineBasicBlock &MBB,
 262                                      MemOpQueue &memOps,
 263                                      unsigned memOpsBegin, unsigned memOpsEnd,
 264                                      unsigned insertAfter, int Offset,
 265                                      unsigned Base, bool BaseKill,
 266                                      int Opcode,
 267                                      ARMCC::CondCodes Pred, unsigned PredReg,
 268                                      unsigned Scratch,
 269                                      DebugLoc dl,
 270                           SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
 271   // First calculate which of the registers should be killed by the merged
 272   // instruction.
 273   const unsigned insertPos = memOps[insertAfter].Position;
 274
 275   SmallSet<unsigned, 4> UnavailRegs;
 276   SmallSet<unsigned, 4> KilledRegs;
 277   DenseMap<unsigned, unsigned> Killer;
 278   for (unsigned i = 0; i < memOpsBegin; ++i) {
 279     if (memOps[i].Position < insertPos && memOps[i].isKill) {
 280       unsigned Reg = memOps[i].Reg;
 281       if (memOps[i].Merged)
 282         UnavailRegs.insert(Reg);
 283       else {
 284         KilledRegs.insert(Reg);
 285         Killer[Reg] = i;
 286       }
 287     }
 288   }
 289   for (unsigned i = memOpsEnd, e = memOps.size(); i != e; ++i) {
 290     if (memOps[i].Position < insertPos && memOps[i].isKill) {
 291       unsigned Reg = memOps[i].Reg;
 292       KilledRegs.insert(Reg);
 293       Killer[Reg] = i;
 294     }
 295   }
 296
 297   SmallVector<std::pair<unsigned, bool>, 8> Regs;
 298   for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
 299     unsigned Reg = memOps[i].Reg;
 300     if (UnavailRegs.count(Reg))
 301       // Register is killed before and it's not easy / possible to update the
 302       // kill marker on already merged instructions. Abort.
 303       return;
 304
 305     // If we are inserting the merged operation after an unmerged operation that
 306     // uses the same register, make sure to transfer any kill flag.
 307     bool isKill = memOps[i].isKill || KilledRegs.count(Reg);
 308     Regs.push_back(std::make_pair(Reg, isKill));
 309   }
 310
 311   // Try to do the merge.
 312   MachineBasicBlock::iterator Loc = memOps[insertAfter].MBBI;
 313   ++Loc;
 314   if (!MergeOps(MBB, Loc, Offset, Base, BaseKill, Opcode,
 315                 Pred, PredReg, Scratch, dl, Regs))
 316     return;
 317
 318   // Merge succeeded, update records.
 319   Merges.push_back(prior(Loc));
 320   for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
 321     // Remove kill flags from any unmerged memops that come before insertPos.
 322     if (Regs[i-memOpsBegin].second) {
 323       unsigned Reg = Regs[i-memOpsBegin].first;
 324       if (KilledRegs.count(Reg)) {
 325         unsigned j = Killer[Reg];
 326         memOps[j].MBBI->getOperand(0).setIsKill(false);
 327         memOps[j].isKill = false;
 328       }
 329     }
 330     MBB.erase(memOps[i].MBBI);
 331     memOps[i].Merged = true;
 332   }
 333 }
 334
 335 /// MergeLDR_STR - Merge a number of load / store instructions into one or more
 336 /// load / store multiple instructions.
 337 void
 338 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
 339                           unsigned Base, int Opcode, unsigned Size,
 340                           ARMCC::CondCodes Pred, unsigned PredReg,
 341                           unsigned Scratch, MemOpQueue &MemOps,
 342                           SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
 343   bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
 344   int Offset = MemOps[SIndex].Offset;
 345   int SOffset = Offset;
 346   unsigned insertAfter = SIndex;
 347   MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
 348   DebugLoc dl = Loc->getDebugLoc();
 349   const MachineOperand &PMO = Loc->getOperand(0);
 350   unsigned PReg = PMO.getReg();
 351   unsigned PRegNum = PMO.isUndef() ? UINT_MAX
 352     : getARMRegisterNumbering(PReg);
 353   unsigned Count = 1;
 354
 355   for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
 356     int NewOffset = MemOps[i].Offset;
 357     const MachineOperand &MO = MemOps[i].MBBI->getOperand(0);
 358     unsigned Reg = MO.getReg();
 359     unsigned RegNum = MO.isUndef() ? UINT_MAX
 360       : getARMRegisterNumbering(Reg);
 361     // Register numbers must be in ascending order.  For VFP, the registers
 362     // must also be consecutive and there is a limit of 16 double-word
 363     // registers per instruction.
 364     if (Reg != ARM::SP &&
 365         NewOffset == Offset + (int)Size &&
 366         ((isNotVFP && RegNum > PRegNum)
 367          || ((Size < 8 || Count < 16) && RegNum == PRegNum+1))) {
 368       Offset += Size;
 369       PRegNum = RegNum;
 370       ++Count;
 371     } else {
 372       // Can't merge this in. Try merge the earlier ones first.
 373       MergeOpsUpdate(MBB, MemOps, SIndex, i, insertAfter, SOffset,
 374                      Base, false, Opcode, Pred, PredReg, Scratch, dl, Merges);
 375       MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch,
 376                    MemOps, Merges);
 377       return;
 378     }
 379
 380     if (MemOps[i].Position > MemOps[insertAfter].Position)
 381       insertAfter = i;
 382   }
 383
 384   bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1;
 385   MergeOpsUpdate(MBB, MemOps, SIndex, MemOps.size(), insertAfter, SOffset,
 386                  Base, BaseKill, Opcode, Pred, PredReg, Scratch, dl, Merges);
 387   return;
 388 }
 389
 390 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
 391                                        unsigned Bytes, unsigned Limit,
 392                                        ARMCC::CondCodes Pred, unsigned PredReg){
 393   unsigned MyPredReg = 0;
 394   if (!MI)
 395     return false;
 396   if (MI->getOpcode() != ARM::t2SUBri &&
 397       MI->getOpcode() != ARM::t2SUBrSPi &&
 398       MI->getOpcode() != ARM::t2SUBrSPi12 &&
 399       MI->getOpcode() != ARM::tSUBspi &&
 400       MI->getOpcode() != ARM::SUBri)
 401     return false;
 402
 403   // Make sure the offset fits in 8 bits.
 404   if (Bytes == 0 || (Limit && Bytes >= Limit))
 405     return false;
 406
 407   unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME
 408   return (MI->getOperand(0).getReg() == Base &&
 409           MI->getOperand(1).getReg() == Base &&
 410           (MI->getOperand(2).getImm()*Scale) == Bytes &&
 411           llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
 412           MyPredReg == PredReg);
 413 }
 414
 415 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
 416                                        unsigned Bytes, unsigned Limit,
 417                                        ARMCC::CondCodes Pred, unsigned PredReg){
 418   unsigned MyPredReg = 0;
 419   if (!MI)
 420     return false;
 421   if (MI->getOpcode() != ARM::t2ADDri &&
 422       MI->getOpcode() != ARM::t2ADDrSPi &&
 423       MI->getOpcode() != ARM::t2ADDrSPi12 &&
 424       MI->getOpcode() != ARM::tADDspi &&
 425       MI->getOpcode() != ARM::ADDri)
 426     return false;
 427
 428   if (Bytes == 0 || (Limit && Bytes >= Limit))
 429     // Make sure the offset fits in 8 bits.
 430     return false;
 431
 432   unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME
 433   return (MI->getOperand(0).getReg() == Base &&
 434           MI->getOperand(1).getReg() == Base &&
 435           (MI->getOperand(2).getImm()*Scale) == Bytes &&
 436           llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
 437           MyPredReg == PredReg);
 438 }
 439
 440 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
 441   switch (MI->getOpcode()) {
 442   default: return 0;
 443   case ARM::LDRi12:
 444   case ARM::STR:
 445   case ARM::t2LDRi8:
 446   case ARM::t2LDRi12:
 447   case ARM::t2STRi8:
 448   case ARM::t2STRi12:
 449   case ARM::VLDRS:
 450   case ARM::VSTRS:
 451     return 4;
 452   case ARM::VLDRD:
 453   case ARM::VSTRD:
 454     return 8;
 455   case ARM::LDM:
 456   case ARM::STM:
 457   case ARM::t2LDM:
 458   case ARM::t2STM:
 459   case ARM::VLDMS:
 460   case ARM::VSTMS:
 461     return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
 462   case ARM::VLDMD:
 463   case ARM::VSTMD:
 464     return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
 465   }
 466 }
 467
 468 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc) {
 469   switch (Opc) {
 470   case ARM::LDM: return ARM::LDM_UPD;
 471   case ARM::STM: return ARM::STM_UPD;
 472   case ARM::t2LDM: return ARM::t2LDM_UPD;
 473   case ARM::t2STM: return ARM::t2STM_UPD;
 474   case ARM::VLDMS: return ARM::VLDMS_UPD;
 475   case ARM::VLDMD: return ARM::VLDMD_UPD;
 476   case ARM::VSTMS: return ARM::VSTMS_UPD;
 477   case ARM::VSTMD: return ARM::VSTMD_UPD;
 478   default: llvm_unreachable("Unhandled opcode!");
 479   }
 480   return 0;
 481 }
 482
 483 /// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
 484 /// register into the LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
 485 ///
 486 /// stmia rn, <ra, rb, rc>
 487 /// rn := rn + 4 * 3;
 488 /// =>
 489 /// stmia rn!, <ra, rb, rc>
 490 ///
 491 /// rn := rn - 4 * 3;
 492 /// ldmia rn, <ra, rb, rc>
 493 /// =>
 494 /// ldmdb rn!, <ra, rb, rc>
 495 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
 496                                                MachineBasicBlock::iterator MBBI,
 497                                                bool &Advance,
 498                                                MachineBasicBlock::iterator &I) {
 499   MachineInstr *MI = MBBI;
 500   unsigned Base = MI->getOperand(0).getReg();
 501   bool BaseKill = MI->getOperand(0).isKill();
 502   unsigned Bytes = getLSMultipleTransferSize(MI);
 503   unsigned PredReg = 0;
 504   ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
 505   int Opcode = MI->getOpcode();
 506   DebugLoc dl = MI->getDebugLoc();
 507
 508   bool DoMerge = false;
 509   ARM_AM::AMSubMode Mode = ARM_AM::ia;
 510
 511   // Can't use an updating ld/st if the base register is also a dest
 512   // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
 513   for (unsigned i = 3, e = MI->getNumOperands(); i != e; ++i) {
 514     if (MI->getOperand(i).getReg() == Base)
 515       return false;
 516   }
 517   Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm());
 518
 519   // Try merging with the previous instruction.
 520   MachineBasicBlock::iterator BeginMBBI = MBB.begin();
 521   if (MBBI != BeginMBBI) {
 522     MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 523     while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
 524       --PrevMBBI;
 525     if (Mode == ARM_AM::ia &&
 526         isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
 527       Mode = ARM_AM::db;
 528       DoMerge = true;
 529     } else if (Mode == ARM_AM::ib &&
 530                isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
 531       Mode = ARM_AM::da;
 532       DoMerge = true;
 533     }
 534     if (DoMerge)
 535       MBB.erase(PrevMBBI);
 536   }
 537
 538   // Try merging with the next instruction.
 539   MachineBasicBlock::iterator EndMBBI = MBB.end();
 540   if (!DoMerge && MBBI != EndMBBI) {
 541     MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
 542     while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
 543       ++NextMBBI;
 544     if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
 545         isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
 546       DoMerge = true;
 547     } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
 548                isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
 549       DoMerge = true;
 550     }
 551     if (DoMerge) {
 552       if (NextMBBI == I) {
 553         Advance = true;
 554         ++I;
 555       }
 556       MBB.erase(NextMBBI);
 557     }
 558   }
 559
 560   if (!DoMerge)
 561     return false;
 562
 563   unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode);
 564   MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
 565     .addReg(Base, getDefRegState(true)) // WB base register
 566     .addReg(Base, getKillRegState(BaseKill))
 567     .addImm(ARM_AM::getAM4ModeImm(Mode))
 568     .addImm(Pred).addReg(PredReg);
 569   // Transfer the rest of operands.
 570   for (unsigned OpNum = 4, e = MI->getNumOperands(); OpNum != e; ++OpNum)
 571     MIB.addOperand(MI->getOperand(OpNum));
 572   // Transfer memoperands.
 573   (*MIB).setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
 574
 575   MBB.erase(MBBI);
 576   return true;
 577 }
 578
 579 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) {
 580   switch (Opc) {
 581   case ARM::LDRi12: return ARM::LDR_PRE;
 582   case ARM::STR: return ARM::STR_PRE;
 583   case ARM::VLDRS: return ARM::VLDMS_UPD;
 584   case ARM::VLDRD: return ARM::VLDMD_UPD;
 585   case ARM::VSTRS: return ARM::VSTMS_UPD;
 586   case ARM::VSTRD: return ARM::VSTMD_UPD;
 587   case ARM::t2LDRi8:
 588   case ARM::t2LDRi12:
 589     return ARM::t2LDR_PRE;
 590   case ARM::t2STRi8:
 591   case ARM::t2STRi12:
 592     return ARM::t2STR_PRE;
 593   default: llvm_unreachable("Unhandled opcode!");
 594   }
 595   return 0;
 596 }
 597
 598 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) {
 599   switch (Opc) {
 600   case ARM::LDRi12: return ARM::LDR_POST;
 601   case ARM::STR: return ARM::STR_POST;
 602   case ARM::VLDRS: return ARM::VLDMS_UPD;
 603   case ARM::VLDRD: return ARM::VLDMD_UPD;
 604   case ARM::VSTRS: return ARM::VSTMS_UPD;
 605   case ARM::VSTRD: return ARM::VSTMD_UPD;
 606   case ARM::t2LDRi8:
 607   case ARM::t2LDRi12:
 608     return ARM::t2LDR_POST;
 609   case ARM::t2STRi8:
 610   case ARM::t2STRi12:
 611     return ARM::t2STR_POST;
 612   default: llvm_unreachable("Unhandled opcode!");
 613   }
 614   return 0;
 615 }
 616
 617 /// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
 618 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
 619 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
 620                                                MachineBasicBlock::iterator MBBI,
 621                                                const TargetInstrInfo *TII,
 622                                                bool &Advance,
 623                                                MachineBasicBlock::iterator &I) {
 624   MachineInstr *MI = MBBI;
 625   unsigned Base = MI->getOperand(1).getReg();
 626   bool BaseKill = MI->getOperand(1).isKill();
 627   unsigned Bytes = getLSMultipleTransferSize(MI);
 628   int Opcode = MI->getOpcode();
 629   DebugLoc dl = MI->getDebugLoc();
 630   bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
 631                 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
 632   bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STR);
 633   // FIXME: This special handling of LDRi12 is hackery until all of the ARM
 634   // LDR/STR insns are moved away from the addrmode2 mega-instruction to
 635   // the split (LDRi12/LDRrs) style instructions.
 636   if (Opcode == ARM::LDRi12 || isT2i32Load(Opcode) || isT2i32Store(Opcode))
 637     if (MI->getOperand(2).getImm() != 0)
 638       return false;
 639   if (isAM2 && Opcode != ARM::LDRi12
 640       && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0)
 641     return false;
 642   if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
 643     return false;
 644
 645   bool isLd = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
 646   // Can't do the merge if the destination register is the same as the would-be
 647   // writeback register.
 648   if (isLd && MI->getOperand(0).getReg() == Base)
 649     return false;
 650
 651   unsigned PredReg = 0;
 652   ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
 653   bool DoMerge = false;
 654   ARM_AM::AddrOpc AddSub = ARM_AM::add;
 655   unsigned NewOpc = 0;
 656   // AM2 - 12 bits, thumb2 - 8 bits.
 657   unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100);
 658
 659   // Try merging with the previous instruction.
 660   MachineBasicBlock::iterator BeginMBBI = MBB.begin();
 661   if (MBBI != BeginMBBI) {
 662     MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 663     while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
 664       --PrevMBBI;
 665     if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) {
 666       DoMerge = true;
 667       AddSub = ARM_AM::sub;
 668     } else if (!isAM5 &&
 669                isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) {
 670       DoMerge = true;
 671     }
 672     if (DoMerge) {
 673       NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
 674       MBB.erase(PrevMBBI);
 675     }
 676   }
 677
 678   // Try merging with the next instruction.
 679   MachineBasicBlock::iterator EndMBBI = MBB.end();
 680   if (!DoMerge && MBBI != EndMBBI) {
 681     MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
 682     while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
 683       ++NextMBBI;
 684     if (!isAM5 &&
 685         isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) {
 686       DoMerge = true;
 687       AddSub = ARM_AM::sub;
 688     } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) {
 689       DoMerge = true;
 690     }
 691     if (DoMerge) {
 692       NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
 693       if (NextMBBI == I) {
 694         Advance = true;
 695         ++I;
 696       }
 697       MBB.erase(NextMBBI);
 698     }
 699   }
 700
 701   if (!DoMerge)
 702     return false;
 703
 704   unsigned Offset = 0;
 705   if (isAM5)
 706     Offset = ARM_AM::getAM4ModeImm(AddSub == ARM_AM::sub ?
 707                                    ARM_AM::db : ARM_AM::ia);
 708   else if (isAM2)
 709     Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
 710   else
 711     Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
 712
 713   if (isAM5) {
 714     // VLDM[SD}_UPD, VSTM[SD]_UPD
 715     // (There are no base-updating versions of VLDR/VSTR instructions, but the
 716     // updating load/store-multiple instructions can be used with only one
 717     // register.)
 718     MachineOperand &MO = MI->getOperand(0);
 719     BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
 720       .addReg(Base, getDefRegState(true)) // WB base register
 721       .addReg(Base, getKillRegState(isLd ? BaseKill : false))
 722       .addImm(Offset)
 723       .addImm(Pred).addReg(PredReg)
 724       .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
 725                             getKillRegState(MO.isKill())));
 726   } else if (isLd) {
 727     if (isAM2)
 728       // LDR_PRE, LDR_POST,
 729       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
 730         .addReg(Base, RegState::Define)
 731         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
 732     else
 733       // t2LDR_PRE, t2LDR_POST
 734       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
 735         .addReg(Base, RegState::Define)
 736         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 737   } else {
 738     MachineOperand &MO = MI->getOperand(0);
 739     if (isAM2)
 740       // STR_PRE, STR_POST
 741       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
 742         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
 743         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
 744     else
 745       // t2STR_PRE, t2STR_POST
 746       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
 747         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
 748         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 749   }
 750   MBB.erase(MBBI);
 751
 752   return true;
 753 }
 754
 755 /// isMemoryOp - Returns true if instruction is a memory operations (that this
 756 /// pass is capable of operating on).
 757 static bool isMemoryOp(const MachineInstr *MI) {
 758   // When no memory operands are present, conservatively assume unaligned,
 759   // volatile, unfoldable.
 760   if (!MI->hasOneMemOperand())
 761     return false;
 762
 763   const MachineMemOperand *MMO = *MI->memoperands_begin();
 764
 765   // Don't touch volatile memory accesses - we may be changing their order.
 766   if (MMO->isVolatile())
 767     return false;
 768
 769   // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
 770   // not.
 771   if (MMO->getAlignment() < 4)
 772     return false;
 773
 774   // str <undef> could probably be eliminated entirely, but for now we just want
 775   // to avoid making a mess of it.
 776   // FIXME: Use str <undef> as a wildcard to enable better stm folding.
 777   if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() &&
 778       MI->getOperand(0).isUndef())
 779     return false;
 780
 781   // Likewise don't mess with references to undefined addresses.
 782   if (MI->getNumOperands() > 1 && MI->getOperand(1).isReg() &&
 783       MI->getOperand(1).isUndef())
 784     return false;
 785
 786   int Opcode = MI->getOpcode();
 787   switch (Opcode) {
 788   default: break;
 789   case ARM::STR:
 790     return MI->getOperand(1).isReg() && MI->getOperand(2).getReg() == 0;
 791   case ARM::VLDRS:
 792   case ARM::VSTRS:
 793     return MI->getOperand(1).isReg();
 794   case ARM::VLDRD:
 795   case ARM::VSTRD:
 796     return MI->getOperand(1).isReg();
 797   case ARM::LDRi12:
 798   case ARM::t2LDRi8:
 799   case ARM::t2LDRi12:
 800   case ARM::t2STRi8:
 801   case ARM::t2STRi12:
 802     return MI->getOperand(1).isReg();
 803   }
 804   return false;
 805 }
 806
 807 /// AdvanceRS - Advance register scavenger to just before the earliest memory
 808 /// op that is being merged.
 809 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) {
 810   MachineBasicBlock::iterator Loc = MemOps[0].MBBI;
 811   unsigned Position = MemOps[0].Position;
 812   for (unsigned i = 1, e = MemOps.size(); i != e; ++i) {
 813     if (MemOps[i].Position < Position) {
 814       Position = MemOps[i].Position;
 815       Loc = MemOps[i].MBBI;
 816     }
 817   }
 818
 819   if (Loc != MBB.begin())
 820     RS->forward(prior(Loc));
 821 }
 822
 823 static int getMemoryOpOffset(const MachineInstr *MI) {
 824   int Opcode = MI->getOpcode();
 825   bool isAM2 = Opcode == ARM::STR;
 826   bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
 827   unsigned NumOperands = MI->getDesc().getNumOperands();
 828   unsigned OffField = MI->getOperand(NumOperands-3).getImm();
 829
 830   if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
 831       Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
 832       Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
 833       Opcode == ARM::LDRi12)
 834     return OffField;
 835
 836   int Offset = isAM2
 837     ? ARM_AM::getAM2Offset(OffField)
 838     : (isAM3 ? ARM_AM::getAM3Offset(OffField)
 839              : ARM_AM::getAM5Offset(OffField) * 4);
 840   if (isAM2) {
 841     if (ARM_AM::getAM2Op(OffField) == ARM_AM::sub)
 842       Offset = -Offset;
 843   } else if (isAM3) {
 844     if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub)
 845       Offset = -Offset;
 846   } else {
 847     if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub)
 848       Offset = -Offset;
 849   }
 850   return Offset;
 851 }
 852
 853 static void InsertLDR_STR(MachineBasicBlock &MBB,
 854                           MachineBasicBlock::iterator &MBBI,
 855                           int OffImm, bool isDef,
 856                           DebugLoc dl, unsigned NewOpc,
 857                           unsigned Reg, bool RegDeadKill, bool RegUndef,
 858                           unsigned BaseReg, bool BaseKill, bool BaseUndef,
 859                           unsigned OffReg, bool OffKill, bool OffUndef,
 860                           ARMCC::CondCodes Pred, unsigned PredReg,
 861                           const TargetInstrInfo *TII, bool isT2) {
 862   int Offset = OffImm;
 863   // FIXME: This fancy offset encoding stuff goes away when we're done
 864   // removing addrmode2.
 865   if (!isT2 && !isDef) {
 866     if (OffImm < 0)
 867       Offset = ARM_AM::getAM2Opc(ARM_AM::sub, -OffImm, ARM_AM::no_shift);
 868     else
 869       Offset = ARM_AM::getAM2Opc(ARM_AM::add, OffImm, ARM_AM::no_shift);
 870   }
 871   if (isDef) {
 872     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
 873                                       TII->get(NewOpc))
 874       .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
 875       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
 876     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
 877   } else {
 878     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
 879                                       TII->get(NewOpc))
 880       .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
 881       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
 882     if (!isT2)
 883       MIB.addReg(OffReg,  getKillRegState(OffKill)|getUndefRegState(OffUndef));
 884     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
 885   }
 886 }
 887
 888 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
 889                                           MachineBasicBlock::iterator &MBBI) {
 890   MachineInstr *MI = &*MBBI;
 891   unsigned Opcode = MI->getOpcode();
 892   if (Opcode == ARM::LDRD || Opcode == ARM::STRD ||
 893       Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) {
 894     unsigned EvenReg = MI->getOperand(0).getReg();
 895     unsigned OddReg  = MI->getOperand(1).getReg();
 896     unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
 897     unsigned OddRegNum  = TRI->getDwarfRegNum(OddReg, false);
 898     if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum)
 899       return false;
 900
 901     MachineBasicBlock::iterator NewBBI = MBBI;
 902     bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
 903     bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
 904     bool EvenDeadKill = isLd ?
 905       MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
 906     bool EvenUndef = MI->getOperand(0).isUndef();
 907     bool OddDeadKill  = isLd ?
 908       MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
 909     bool OddUndef = MI->getOperand(1).isUndef();
 910     const MachineOperand &BaseOp = MI->getOperand(2);
 911     unsigned BaseReg = BaseOp.getReg();
 912     bool BaseKill = BaseOp.isKill();
 913     bool BaseUndef = BaseOp.isUndef();
 914     unsigned OffReg = isT2 ? 0 : MI->getOperand(3).getReg();
 915     bool OffKill = isT2 ? false : MI->getOperand(3).isKill();
 916     bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef();
 917     int OffImm = getMemoryOpOffset(MI);
 918     unsigned PredReg = 0;
 919     ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
 920
 921     if (OddRegNum > EvenRegNum && OffReg == 0 && OffImm == 0) {
 922       // Ascending register numbers and no offset. It's safe to change it to a
 923       // ldm or stm.
 924       unsigned NewOpc = (isLd)
 925         ? (isT2 ? ARM::t2LDM : ARM::LDM)
 926         : (isT2 ? ARM::t2STM : ARM::STM);
 927       if (isLd) {
 928         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 929           .addReg(BaseReg, getKillRegState(BaseKill))
 930           .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia))
 931           .addImm(Pred).addReg(PredReg)
 932           .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
 933           .addReg(OddReg,  getDefRegState(isLd) | getDeadRegState(OddDeadKill));
 934         ++NumLDRD2LDM;
 935       } else {
 936         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 937           .addReg(BaseReg, getKillRegState(BaseKill))
 938           .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia))
 939           .addImm(Pred).addReg(PredReg)
 940           .addReg(EvenReg,
 941                   getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
 942           .addReg(OddReg,
 943                   getKillRegState(OddDeadKill)  | getUndefRegState(OddUndef));
 944         ++NumSTRD2STM;
 945       }
 946       NewBBI = llvm::prior(MBBI);
 947     } else {
 948       // Split into two instructions.
 949       assert((!isT2 || !OffReg) &&
 950              "Thumb2 ldrd / strd does not encode offset register!");
 951       unsigned NewOpc = (isLd)
 952         ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
 953         : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STR);
 954       DebugLoc dl = MBBI->getDebugLoc();
 955       // If this is a load and base register is killed, it may have been
 956       // re-defed by the load, make sure the first load does not clobber it.
 957       if (isLd &&
 958           (BaseKill || OffKill) &&
 959           (TRI->regsOverlap(EvenReg, BaseReg) ||
 960            (OffReg && TRI->regsOverlap(EvenReg, OffReg)))) {
 961         assert(!TRI->regsOverlap(OddReg, BaseReg) &&
 962                (!OffReg || !TRI->regsOverlap(OddReg, OffReg)));
 963         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
 964                       OddReg, OddDeadKill, false,
 965                       BaseReg, false, BaseUndef, OffReg, false, OffUndef,
 966                       Pred, PredReg, TII, isT2);
 967         NewBBI = llvm::prior(MBBI);
 968         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
 969                       EvenReg, EvenDeadKill, false,
 970                       BaseReg, BaseKill, BaseUndef, OffReg, OffKill, OffUndef,
 971                       Pred, PredReg, TII, isT2);
 972       } else {
 973         if (OddReg == EvenReg && EvenDeadKill) {
 974           // If the two source operands are the same, the kill marker is
 975           // probably on the first one. e.g.
 976           // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0
 977           EvenDeadKill = false;
 978           OddDeadKill = true;
 979         }
 980         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
 981                       EvenReg, EvenDeadKill, EvenUndef,
 982                       BaseReg, false, BaseUndef, OffReg, false, OffUndef,
 983                       Pred, PredReg, TII, isT2);
 984         NewBBI = llvm::prior(MBBI);
 985         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
 986                       OddReg, OddDeadKill, OddUndef,
 987                       BaseReg, BaseKill, BaseUndef, OffReg, OffKill, OffUndef,
 988                       Pred, PredReg, TII, isT2);
 989       }
 990       if (isLd)
 991         ++NumLDRD2LDR;
 992       else
 993         ++NumSTRD2STR;
 994     }
 995
 996     MBB.erase(MI);
 997     MBBI = NewBBI;
 998     return true;
 999   }
1000   return false;
1001 }
1002
1003 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
1004 /// ops of the same base and incrementing offset into LDM / STM ops.
1005 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1006   unsigned NumMerges = 0;
1007   unsigned NumMemOps = 0;
1008   MemOpQueue MemOps;
1009   unsigned CurrBase = 0;
1010   int CurrOpc = -1;
1011   unsigned CurrSize = 0;
1012   ARMCC::CondCodes CurrPred = ARMCC::AL;
1013   unsigned CurrPredReg = 0;
1014   unsigned Position = 0;
1015   SmallVector<MachineBasicBlock::iterator,4> Merges;
1016
1017   RS->enterBasicBlock(&MBB);
1018   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1019   while (MBBI != E) {
1020     if (FixInvalidRegPairOp(MBB, MBBI))
1021       continue;
1022
1023     bool Advance  = false;
1024     bool TryMerge = false;
1025     bool Clobber  = false;
1026
1027     bool isMemOp = isMemoryOp(MBBI);
1028     if (isMemOp) {
1029       int Opcode = MBBI->getOpcode();
1030       unsigned Size = getLSMultipleTransferSize(MBBI);
1031       const MachineOperand &MO = MBBI->getOperand(0);
1032       unsigned Reg = MO.getReg();
1033       bool isKill = MO.isDef() ? false : MO.isKill();
1034       unsigned Base = MBBI->getOperand(1).getReg();
1035       unsigned PredReg = 0;
1036       ARMCC::CondCodes Pred = llvm::getInstrPredicate(MBBI, PredReg);
1037       int Offset = getMemoryOpOffset(MBBI);
1038       // Watch out for:
1039       // r4 := ldr [r5]
1040       // r5 := ldr [r5, #4]
1041       // r6 := ldr [r5, #8]
1042       //
1043       // The second ldr has effectively broken the chain even though it
1044       // looks like the later ldr(s) use the same base register. Try to
1045       // merge the ldr's so far, including this one. But don't try to
1046       // combine the following ldr(s).
1047       Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg());
1048       if (CurrBase == 0 && !Clobber) {
1049         // Start of a new chain.
1050         CurrBase = Base;
1051         CurrOpc  = Opcode;
1052         CurrSize = Size;
1053         CurrPred = Pred;
1054         CurrPredReg = PredReg;
1055         MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI));
1056         ++NumMemOps;
1057         Advance = true;
1058       } else {
1059         if (Clobber) {
1060           TryMerge = true;
1061           Advance = true;
1062         }
1063
1064         if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1065           // No need to match PredReg.
1066           // Continue adding to the queue.
1067           if (Offset > MemOps.back().Offset) {
1068             MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill,
1069                                              Position, MBBI));
1070             ++NumMemOps;
1071             Advance = true;
1072           } else {
1073             for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
1074                  I != E; ++I) {
1075               if (Offset < I->Offset) {
1076                 MemOps.insert(I, MemOpQueueEntry(Offset, Reg, isKill,
1077                                                  Position, MBBI));
1078                 ++NumMemOps;
1079                 Advance = true;
1080                 break;
1081               } else if (Offset == I->Offset) {
1082                 // Collision! This can't be merged!
1083                 break;
1084               }
1085             }
1086           }
1087         }
1088       }
1089     }
1090
1091     if (MBBI->isDebugValue()) {
1092       ++MBBI;
1093       if (MBBI == E)
1094         // Reach the end of the block, try merging the memory instructions.
1095         TryMerge = true;
1096     } else if (Advance) {
1097       ++Position;
1098       ++MBBI;
1099       if (MBBI == E)
1100         // Reach the end of the block, try merging the memory instructions.
1101         TryMerge = true;
1102     } else
1103       TryMerge = true;
1104
1105     if (TryMerge) {
1106       if (NumMemOps > 1) {
1107         // Try to find a free register to use as a new base in case it's needed.
1108         // First advance to the instruction just before the start of the chain.
1109         AdvanceRS(MBB, MemOps);
1110         // Find a scratch register.
1111         unsigned Scratch = RS->FindUnusedReg(ARM::GPRRegisterClass);
1112         // Process the load / store instructions.
1113         RS->forward(prior(MBBI));
1114
1115         // Merge ops.
1116         Merges.clear();
1117         MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize,
1118                      CurrPred, CurrPredReg, Scratch, MemOps, Merges);
1119
1120         // Try folding preceeding/trailing base inc/dec into the generated
1121         // LDM/STM ops.
1122         for (unsigned i = 0, e = Merges.size(); i < e; ++i)
1123           if (MergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI))
1124             ++NumMerges;
1125         NumMerges += Merges.size();
1126
1127         // Try folding preceeding/trailing base inc/dec into those load/store
1128         // that were not merged to form LDM/STM ops.
1129         for (unsigned i = 0; i != NumMemOps; ++i)
1130           if (!MemOps[i].Merged)
1131             if (MergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI))
1132               ++NumMerges;
1133
1134         // RS may be pointing to an instruction that's deleted.
1135         RS->skipTo(prior(MBBI));
1136       } else if (NumMemOps == 1) {
1137         // Try folding preceeding/trailing base inc/dec into the single
1138         // load/store.
1139         if (MergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) {
1140           ++NumMerges;
1141           RS->forward(prior(MBBI));
1142         }
1143       }
1144
1145       CurrBase = 0;
1146       CurrOpc = -1;
1147       CurrSize = 0;
1148       CurrPred = ARMCC::AL;
1149       CurrPredReg = 0;
1150       if (NumMemOps) {
1151         MemOps.clear();
1152         NumMemOps = 0;
1153       }
1154
1155       // If iterator hasn't been advanced and this is not a memory op, skip it.
1156       // It can't start a new chain anyway.
1157       if (!Advance && !isMemOp && MBBI != E) {
1158         ++Position;
1159         ++MBBI;
1160       }
1161     }
1162   }
1163   return NumMerges > 0;
1164 }
1165
1166 namespace {
1167   struct OffsetCompare {
1168     bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
1169       int LOffset = getMemoryOpOffset(LHS);
1170       int ROffset = getMemoryOpOffset(RHS);
1171       assert(LHS == RHS || LOffset != ROffset);
1172       return LOffset > ROffset;
1173     }
1174   };
1175 }
1176
1177 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return ops
1178 /// ("bx lr" and "mov pc, lr") into the preceeding stack restore so it
1179 /// directly restore the value of LR into pc.
1180 ///   ldmfd sp!, {..., lr}
1181 ///   bx lr
1182 /// or
1183 ///   ldmfd sp!, {..., lr}
1184 ///   mov pc, lr
1185 /// =>
1186 ///   ldmfd sp!, {..., pc}
1187 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1188   if (MBB.empty()) return false;
1189
1190   MachineBasicBlock::iterator MBBI = prior(MBB.end());
1191   if (MBBI != MBB.begin() &&
1192       (MBBI->getOpcode() == ARM::BX_RET ||
1193        MBBI->getOpcode() == ARM::tBX_RET ||
1194        MBBI->getOpcode() == ARM::MOVPCLR)) {
1195     MachineInstr *PrevMI = prior(MBBI);
1196     if (PrevMI->getOpcode() == ARM::LDM_UPD ||
1197         PrevMI->getOpcode() == ARM::t2LDM_UPD) {
1198       MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
1199       if (MO.getReg() != ARM::LR)
1200         return false;
1201       unsigned NewOpc = isThumb2 ? ARM::t2LDM_RET : ARM::LDM_RET;
1202       PrevMI->setDesc(TII->get(NewOpc));
1203       MO.setReg(ARM::PC);
1204       PrevMI->copyImplicitOps(&*MBBI);
1205       MBB.erase(MBBI);
1206       return true;
1207     }
1208   }
1209   return false;
1210 }
1211
1212 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1213   const TargetMachine &TM = Fn.getTarget();
1214   AFI = Fn.getInfo<ARMFunctionInfo>();
1215   TII = TM.getInstrInfo();
1216   TRI = TM.getRegisterInfo();
1217   RS = new RegScavenger();
1218   isThumb2 = AFI->isThumb2Function();
1219
1220   bool Modified = false;
1221   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1222        ++MFI) {
1223     MachineBasicBlock &MBB = *MFI;
1224     Modified |= LoadStoreMultipleOpti(MBB);
1225     Modified |= MergeReturnIntoLDM(MBB);
1226   }
1227
1228   delete RS;
1229   return Modified;
1230 }
1231
1232
1233 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move
1234 /// load / stores from consecutive locations close to make it more
1235 /// likely they will be combined later.
1236
1237 namespace {
1238   struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
1239     static char ID;
1240     ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
1241
1242     const TargetData *TD;
1243     const TargetInstrInfo *TII;
1244     const TargetRegisterInfo *TRI;
1245     const ARMSubtarget *STI;
1246     MachineRegisterInfo *MRI;
1247     MachineFunction *MF;
1248
1249     virtual bool runOnMachineFunction(MachineFunction &Fn);
1250
1251     virtual const char *getPassName() const {
1252       return "ARM pre- register allocation load / store optimization pass";
1253     }
1254
1255   private:
1256     bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
1257                           unsigned &NewOpc, unsigned &EvenReg,
1258                           unsigned &OddReg, unsigned &BaseReg,
1259                           unsigned &OffReg, int &Offset,
1260                           unsigned &PredReg, ARMCC::CondCodes &Pred,
1261                           bool &isT2);
1262     bool RescheduleOps(MachineBasicBlock *MBB,
1263                        SmallVector<MachineInstr*, 4> &Ops,
1264                        unsigned Base, bool isLd,
1265                        DenseMap<MachineInstr*, unsigned> &MI2LocMap);
1266     bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
1267   };
1268   char ARMPreAllocLoadStoreOpt::ID = 0;
1269 }
1270
1271 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1272   TD  = Fn.getTarget().getTargetData();
1273   TII = Fn.getTarget().getInstrInfo();
1274   TRI = Fn.getTarget().getRegisterInfo();
1275   STI = &Fn.getTarget().getSubtarget<ARMSubtarget>();
1276   MRI = &Fn.getRegInfo();
1277   MF  = &Fn;
1278
1279   bool Modified = false;
1280   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1281        ++MFI)
1282     Modified |= RescheduleLoadStoreInstrs(MFI);
1283
1284   return Modified;
1285 }
1286
1287 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
1288                                       MachineBasicBlock::iterator I,
1289                                       MachineBasicBlock::iterator E,
1290                                       SmallPtrSet<MachineInstr*, 4> &MemOps,
1291                                       SmallSet<unsigned, 4> &MemRegs,
1292                                       const TargetRegisterInfo *TRI) {
1293   // Are there stores / loads / calls between them?
1294   // FIXME: This is overly conservative. We should make use of alias information
1295   // some day.
1296   SmallSet<unsigned, 4> AddedRegPressure;
1297   while (++I != E) {
1298     if (I->isDebugValue() || MemOps.count(&*I))
1299       continue;
1300     const TargetInstrDesc &TID = I->getDesc();
1301     if (TID.isCall() || TID.isTerminator() || TID.hasUnmodeledSideEffects())
1302       return false;
1303     if (isLd && TID.mayStore())
1304       return false;
1305     if (!isLd) {
1306       if (TID.mayLoad())
1307         return false;
1308       // It's not safe to move the first 'str' down.
1309       // str r1, [r0]
1310       // strh r5, [r0]
1311       // str r4, [r0, #+4]
1312       if (TID.mayStore())
1313         return false;
1314     }
1315     for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
1316       MachineOperand &MO = I->getOperand(j);
1317       if (!MO.isReg())
1318         continue;
1319       unsigned Reg = MO.getReg();
1320       if (MO.isDef() && TRI->regsOverlap(Reg, Base))
1321         return false;
1322       if (Reg != Base && !MemRegs.count(Reg))
1323         AddedRegPressure.insert(Reg);
1324     }
1325   }
1326
1327   // Estimate register pressure increase due to the transformation.
1328   if (MemRegs.size() <= 4)
1329     // Ok if we are moving small number of instructions.
1330     return true;
1331   return AddedRegPressure.size() <= MemRegs.size() * 2;
1332 }
1333
1334 bool
1335 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
1336                                           DebugLoc &dl,
1337                                           unsigned &NewOpc, unsigned &EvenReg,
1338                                           unsigned &OddReg, unsigned &BaseReg,
1339                                           unsigned &OffReg, int &Offset,
1340                                           unsigned &PredReg,
1341                                           ARMCC::CondCodes &Pred,
1342                                           bool &isT2) {
1343   // Make sure we're allowed to generate LDRD/STRD.
1344   if (!STI->hasV5TEOps())
1345     return false;
1346
1347   // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
1348   unsigned Scale = 1;
1349   unsigned Opcode = Op0->getOpcode();
1350   if (Opcode == ARM::LDRi12)
1351     NewOpc = ARM::LDRD;
1352   else if (Opcode == ARM::STR)
1353     NewOpc = ARM::STRD;
1354   else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
1355     NewOpc = ARM::t2LDRDi8;
1356     Scale = 4;
1357     isT2 = true;
1358   } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
1359     NewOpc = ARM::t2STRDi8;
1360     Scale = 4;
1361     isT2 = true;
1362   } else
1363     return false;
1364
1365   // Make sure the offset registers match.
1366   if (!isT2 && Opcode != ARM::LDRi12 &&
1367       (Op0->getOperand(2).getReg() != Op1->getOperand(2).getReg()))
1368       return false;
1369
1370   // Make sure the base address satisfies i64 ld / st alignment requirement.
1371   if (!Op0->hasOneMemOperand() ||
1372       !(*Op0->memoperands_begin())->getValue() ||
1373       (*Op0->memoperands_begin())->isVolatile())
1374     return false;
1375
1376   unsigned Align = (*Op0->memoperands_begin())->getAlignment();
1377   const Function *Func = MF->getFunction();
1378   unsigned ReqAlign = STI->hasV6Ops()
1379     ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext()))
1380     : 8;  // Pre-v6 need 8-byte align
1381   if (Align < ReqAlign)
1382     return false;
1383
1384   // Then make sure the immediate offset fits.
1385   int OffImm = getMemoryOpOffset(Op0);
1386   if (isT2) {
1387     if (OffImm < 0) {
1388       if (OffImm < -255)
1389         // Can't fall back to t2LDRi8 / t2STRi8.
1390         return false;
1391     } else {
1392       int Limit = (1 << 8) * Scale;
1393       if (OffImm >= Limit || (OffImm & (Scale-1)))
1394         return false;
1395     }
1396     Offset = OffImm;
1397   } else {
1398     ARM_AM::AddrOpc AddSub = ARM_AM::add;
1399     if (OffImm < 0) {
1400       AddSub = ARM_AM::sub;
1401       OffImm = - OffImm;
1402     }
1403     int Limit = (1 << 8) * Scale;
1404     if (OffImm >= Limit || (OffImm & (Scale-1)))
1405       return false;
1406     Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
1407   }
1408   EvenReg = Op0->getOperand(0).getReg();
1409   OddReg  = Op1->getOperand(0).getReg();
1410   if (EvenReg == OddReg)
1411     return false;
1412   BaseReg = Op0->getOperand(1).getReg();
1413   if (!isT2 && Opcode != ARM::LDRi12)
1414     OffReg = Op0->getOperand(2).getReg();
1415   Pred = llvm::getInstrPredicate(Op0, PredReg);
1416   dl = Op0->getDebugLoc();
1417   return true;
1418 }
1419
1420 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
1421                                  SmallVector<MachineInstr*, 4> &Ops,
1422                                  unsigned Base, bool isLd,
1423                                  DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
1424   bool RetVal = false;
1425
1426   // Sort by offset (in reverse order).
1427   std::sort(Ops.begin(), Ops.end(), OffsetCompare());
1428
1429   // The loads / stores of the same base are in order. Scan them from first to
1430   // last and check for the following:
1431   // 1. Any def of base.
1432   // 2. Any gaps.
1433   while (Ops.size() > 1) {
1434     unsigned FirstLoc = ~0U;
1435     unsigned LastLoc = 0;
1436     MachineInstr *FirstOp = 0;
1437     MachineInstr *LastOp = 0;
1438     int LastOffset = 0;
1439     unsigned LastOpcode = 0;
1440     unsigned LastBytes = 0;
1441     unsigned NumMove = 0;
1442     for (int i = Ops.size() - 1; i >= 0; --i) {
1443       MachineInstr *Op = Ops[i];
1444       unsigned Loc = MI2LocMap[Op];
1445       if (Loc <= FirstLoc) {
1446         FirstLoc = Loc;
1447         FirstOp = Op;
1448       }
1449       if (Loc >= LastLoc) {
1450         LastLoc = Loc;
1451         LastOp = Op;
1452       }
1453
1454       unsigned Opcode = Op->getOpcode();
1455       if (LastOpcode && Opcode != LastOpcode)
1456         break;
1457
1458       int Offset = getMemoryOpOffset(Op);
1459       unsigned Bytes = getLSMultipleTransferSize(Op);
1460       if (LastBytes) {
1461         if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
1462           break;
1463       }
1464       LastOffset = Offset;
1465       LastBytes = Bytes;
1466       LastOpcode = Opcode;
1467       if (++NumMove == 8) // FIXME: Tune this limit.
1468         break;
1469     }
1470
1471     if (NumMove <= 1)
1472       Ops.pop_back();
1473     else {
1474       SmallPtrSet<MachineInstr*, 4> MemOps;
1475       SmallSet<unsigned, 4> MemRegs;
1476       for (int i = NumMove-1; i >= 0; --i) {
1477         MemOps.insert(Ops[i]);
1478         MemRegs.insert(Ops[i]->getOperand(0).getReg());
1479       }
1480
1481       // Be conservative, if the instructions are too far apart, don't
1482       // move them. We want to limit the increase of register pressure.
1483       bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
1484       if (DoMove)
1485         DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
1486                                            MemOps, MemRegs, TRI);
1487       if (!DoMove) {
1488         for (unsigned i = 0; i != NumMove; ++i)
1489           Ops.pop_back();
1490       } else {
1491         // This is the new location for the loads / stores.
1492         MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
1493         while (InsertPos != MBB->end()
1494                && (MemOps.count(InsertPos) || InsertPos->isDebugValue()))
1495           ++InsertPos;
1496
1497         // If we are moving a pair of loads / stores, see if it makes sense
1498         // to try to allocate a pair of registers that can form register pairs.
1499         MachineInstr *Op0 = Ops.back();
1500         MachineInstr *Op1 = Ops[Ops.size()-2];
1501         unsigned EvenReg = 0, OddReg = 0;
1502         unsigned BaseReg = 0, OffReg = 0, PredReg = 0;
1503         ARMCC::CondCodes Pred = ARMCC::AL;
1504         bool isT2 = false;
1505         unsigned NewOpc = 0;
1506         int Offset = 0;
1507         DebugLoc dl;
1508         if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
1509                                              EvenReg, OddReg, BaseReg, OffReg,
1510                                              Offset, PredReg, Pred, isT2)) {
1511           Ops.pop_back();
1512           Ops.pop_back();
1513
1514           // Form the pair instruction.
1515           if (isLd) {
1516             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos,
1517                                               dl, TII->get(NewOpc))
1518               .addReg(EvenReg, RegState::Define)
1519               .addReg(OddReg, RegState::Define)
1520               .addReg(BaseReg);
1521             // For now, we're converting from LDRi12 to an insn that still
1522             // uses addrmode2, so we need an explicit offset reg. It should
1523             // always by reg0 since we're transforming LDRi12s. The old
1524             // was just being paranoid in allowing for anything else.
1525             if (!isT2)
1526               MIB.addReg(0);
1527             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1528             ++NumLDRDFormed;
1529           } else {
1530             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos,
1531                                               dl, TII->get(NewOpc))
1532               .addReg(EvenReg)
1533               .addReg(OddReg)
1534               .addReg(BaseReg);
1535             if (!isT2)
1536               MIB.addReg(OffReg);
1537             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1538             ++NumSTRDFormed;
1539           }
1540           MBB->erase(Op0);
1541           MBB->erase(Op1);
1542
1543           // Add register allocation hints to form register pairs.
1544           MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg);
1545           MRI->setRegAllocationHint(OddReg,  ARMRI::RegPairOdd, EvenReg);
1546         } else {
1547           for (unsigned i = 0; i != NumMove; ++i) {
1548             MachineInstr *Op = Ops.back();
1549             Ops.pop_back();
1550             MBB->splice(InsertPos, MBB, Op);
1551           }
1552         }
1553
1554         NumLdStMoved += NumMove;
1555         RetVal = true;
1556       }
1557     }
1558   }
1559
1560   return RetVal;
1561 }
1562
1563 bool
1564 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
1565   bool RetVal = false;
1566
1567   DenseMap<MachineInstr*, unsigned> MI2LocMap;
1568   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
1569   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
1570   SmallVector<unsigned, 4> LdBases;
1571   SmallVector<unsigned, 4> StBases;
1572
1573   unsigned Loc = 0;
1574   MachineBasicBlock::iterator MBBI = MBB->begin();
1575   MachineBasicBlock::iterator E = MBB->end();
1576   while (MBBI != E) {
1577     for (; MBBI != E; ++MBBI) {
1578       MachineInstr *MI = MBBI;
1579       const TargetInstrDesc &TID = MI->getDesc();
1580       if (TID.isCall() || TID.isTerminator()) {
1581         // Stop at barriers.
1582         ++MBBI;
1583         break;
1584       }
1585
1586       if (!MI->isDebugValue())
1587         MI2LocMap[MI] = ++Loc;
1588
1589       if (!isMemoryOp(MI))
1590         continue;
1591       unsigned PredReg = 0;
1592       if (llvm::getInstrPredicate(MI, PredReg) != ARMCC::AL)
1593         continue;
1594
1595       int Opc = MI->getOpcode();
1596       bool isLd = isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
1597       unsigned Base = MI->getOperand(1).getReg();
1598       int Offset = getMemoryOpOffset(MI);
1599
1600       bool StopHere = false;
1601       if (isLd) {
1602         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1603           Base2LdsMap.find(Base);
1604         if (BI != Base2LdsMap.end()) {
1605           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1606             if (Offset == getMemoryOpOffset(BI->second[i])) {
1607               StopHere = true;
1608               break;
1609             }
1610           }
1611           if (!StopHere)
1612             BI->second.push_back(MI);
1613         } else {
1614           SmallVector<MachineInstr*, 4> MIs;
1615           MIs.push_back(MI);
1616           Base2LdsMap[Base] = MIs;
1617           LdBases.push_back(Base);
1618         }
1619       } else {
1620         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1621           Base2StsMap.find(Base);
1622         if (BI != Base2StsMap.end()) {
1623           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1624             if (Offset == getMemoryOpOffset(BI->second[i])) {
1625               StopHere = true;
1626               break;
1627             }
1628           }
1629           if (!StopHere)
1630             BI->second.push_back(MI);
1631         } else {
1632           SmallVector<MachineInstr*, 4> MIs;
1633           MIs.push_back(MI);
1634           Base2StsMap[Base] = MIs;
1635           StBases.push_back(Base);
1636         }
1637       }
1638
1639       if (StopHere) {
1640         // Found a duplicate (a base+offset combination that's seen earlier).
1641         // Backtrack.
1642         --Loc;
1643         break;
1644       }
1645     }
1646
1647     // Re-schedule loads.
1648     for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
1649       unsigned Base = LdBases[i];
1650       SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base];
1651       if (Lds.size() > 1)
1652         RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
1653     }
1654
1655     // Re-schedule stores.
1656     for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
1657       unsigned Base = StBases[i];
1658       SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base];
1659       if (Sts.size() > 1)
1660         RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
1661     }
1662
1663     if (MBBI != E) {
1664       Base2LdsMap.clear();
1665       Base2StsMap.clear();
1666       LdBases.clear();
1667       StBases.clear();
1668     }
1669   }
1670
1671   return RetVal;
1672 }
1673
1674
1675 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
1676 /// optimization pass.
1677 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
1678   if (PreAlloc)
1679     return new ARMPreAllocLoadStoreOpt();
1680   return new ARMLoadStoreOpt();
1681 }