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