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