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