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_IMM;
 768   case ARM::STRi12:
 769     return ARM::STR_PRE_IMM;
 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_IMM;
 794   case ARM::STRi12:
 795     return ARM::STR_POST_IMM;
 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   if (isAM5) {
 897     // VLDM[SD}_UPD, VSTM[SD]_UPD
 898     // (There are no base-updating versions of VLDR/VSTR instructions, but the
 899     // updating load/store-multiple instructions can be used with only one
 900     // register.)
 901     MachineOperand &MO = MI->getOperand(0);
 902     BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
 903       .addReg(Base, getDefRegState(true)) // WB base register
 904       .addReg(Base, getKillRegState(isLd ? BaseKill : false))
 905       .addImm(Pred).addReg(PredReg)
 906       .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
 907                             getKillRegState(MO.isKill())));
 908   } else if (isLd) {
 909     if (isAM2) {
 910       int Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
 911       // LDR_PRE, LDR_POST
 912       if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
 913         BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
 914           .addReg(Base, RegState::Define)
 915           .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 916       } else {
 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       }
 921     } else {
 922       int Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
 923       // t2LDR_PRE, t2LDR_POST
 924       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
 925         .addReg(Base, RegState::Define)
 926         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 927     }
 928   } else {
 929     MachineOperand &MO = MI->getOperand(0);
 930     // FIXME: post-indexed stores use am2offset_imm, which still encodes
 931     // the vestigal zero-reg offset register. When that's fixed, this clause
 932     // can be removed entirely.
 933     if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
 934       int Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
 935       // STR_PRE, STR_POST
 936       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
 937         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
 938         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
 939     } else {
 940       int Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
 941       // t2STR_PRE, t2STR_POST
 942       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
 943         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
 944         .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
 945     }
 946   }
 947   MBB.erase(MBBI);
 948
 949   return true;
 950 }
 951
 952 /// isMemoryOp - Returns true if instruction is a memory operation that this
 953 /// pass is capable of operating on.
 954 static bool isMemoryOp(const MachineInstr *MI) {
 955   // When no memory operands are present, conservatively assume unaligned,
 956   // volatile, unfoldable.
 957   if (!MI->hasOneMemOperand())
 958     return false;
 959
 960   const MachineMemOperand *MMO = *MI->memoperands_begin();
 961
 962   // Don't touch volatile memory accesses - we may be changing their order.
 963   if (MMO->isVolatile())
 964     return false;
 965
 966   // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
 967   // not.
 968   if (MMO->getAlignment() < 4)
 969     return false;
 970
 971   // str <undef> could probably be eliminated entirely, but for now we just want
 972   // to avoid making a mess of it.
 973   // FIXME: Use str <undef> as a wildcard to enable better stm folding.
 974   if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() &&
 975       MI->getOperand(0).isUndef())
 976     return false;
 977
 978   // Likewise don't mess with references to undefined addresses.
 979   if (MI->getNumOperands() > 1 && MI->getOperand(1).isReg() &&
 980       MI->getOperand(1).isUndef())
 981     return false;
 982
 983   int Opcode = MI->getOpcode();
 984   switch (Opcode) {
 985   default: break;
 986   case ARM::VLDRS:
 987   case ARM::VSTRS:
 988     return MI->getOperand(1).isReg();
 989   case ARM::VLDRD:
 990   case ARM::VSTRD:
 991     return MI->getOperand(1).isReg();
 992   case ARM::LDRi12:
 993   case ARM::STRi12:
 994   case ARM::t2LDRi8:
 995   case ARM::t2LDRi12:
 996   case ARM::t2STRi8:
 997   case ARM::t2STRi12:
 998     return MI->getOperand(1).isReg();
 999   }
1000   return false;
1001 }
1002
1003 /// AdvanceRS - Advance register scavenger to just before the earliest memory
1004 /// op that is being merged.
1005 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) {
1006   MachineBasicBlock::iterator Loc = MemOps[0].MBBI;
1007   unsigned Position = MemOps[0].Position;
1008   for (unsigned i = 1, e = MemOps.size(); i != e; ++i) {
1009     if (MemOps[i].Position < Position) {
1010       Position = MemOps[i].Position;
1011       Loc = MemOps[i].MBBI;
1012     }
1013   }
1014
1015   if (Loc != MBB.begin())
1016     RS->forward(prior(Loc));
1017 }
1018
1019 static int getMemoryOpOffset(const MachineInstr *MI) {
1020   int Opcode = MI->getOpcode();
1021   bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
1022   unsigned NumOperands = MI->getDesc().getNumOperands();
1023   unsigned OffField = MI->getOperand(NumOperands-3).getImm();
1024
1025   if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
1026       Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
1027       Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
1028       Opcode == ARM::LDRi12   || Opcode == ARM::STRi12)
1029     return OffField;
1030
1031   int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
1032     : ARM_AM::getAM5Offset(OffField) * 4;
1033   if (isAM3) {
1034     if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub)
1035       Offset = -Offset;
1036   } else {
1037     if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub)
1038       Offset = -Offset;
1039   }
1040   return Offset;
1041 }
1042
1043 static void InsertLDR_STR(MachineBasicBlock &MBB,
1044                           MachineBasicBlock::iterator &MBBI,
1045                           int Offset, bool isDef,
1046                           DebugLoc dl, unsigned NewOpc,
1047                           unsigned Reg, bool RegDeadKill, bool RegUndef,
1048                           unsigned BaseReg, bool BaseKill, bool BaseUndef,
1049                           bool OffKill, bool OffUndef,
1050                           ARMCC::CondCodes Pred, unsigned PredReg,
1051                           const TargetInstrInfo *TII, bool isT2) {
1052   if (isDef) {
1053     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1054                                       TII->get(NewOpc))
1055       .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1056       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1057     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1058   } else {
1059     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1060                                       TII->get(NewOpc))
1061       .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1062       .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1063     MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1064   }
1065 }
1066
1067 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1068                                           MachineBasicBlock::iterator &MBBI) {
1069   MachineInstr *MI = &*MBBI;
1070   unsigned Opcode = MI->getOpcode();
1071   if (Opcode == ARM::LDRD || Opcode == ARM::STRD ||
1072       Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) {
1073     unsigned EvenReg = MI->getOperand(0).getReg();
1074     unsigned OddReg  = MI->getOperand(1).getReg();
1075     unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1076     unsigned OddRegNum  = TRI->getDwarfRegNum(OddReg, false);
1077     if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum)
1078       return false;
1079
1080     MachineBasicBlock::iterator NewBBI = MBBI;
1081     bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1082     bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1083     bool EvenDeadKill = isLd ?
1084       MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1085     bool EvenUndef = MI->getOperand(0).isUndef();
1086     bool OddDeadKill  = isLd ?
1087       MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1088     bool OddUndef = MI->getOperand(1).isUndef();
1089     const MachineOperand &BaseOp = MI->getOperand(2);
1090     unsigned BaseReg = BaseOp.getReg();
1091     bool BaseKill = BaseOp.isKill();
1092     bool BaseUndef = BaseOp.isUndef();
1093     bool OffKill = isT2 ? false : MI->getOperand(3).isKill();
1094     bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef();
1095     int OffImm = getMemoryOpOffset(MI);
1096     unsigned PredReg = 0;
1097     ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
1098
1099     if (OddRegNum > EvenRegNum && OffImm == 0) {
1100       // Ascending register numbers and no offset. It's safe to change it to a
1101       // ldm or stm.
1102       unsigned NewOpc = (isLd)
1103         ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1104         : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1105       if (isLd) {
1106         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1107           .addReg(BaseReg, getKillRegState(BaseKill))
1108           .addImm(Pred).addReg(PredReg)
1109           .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1110           .addReg(OddReg,  getDefRegState(isLd) | getDeadRegState(OddDeadKill));
1111         ++NumLDRD2LDM;
1112       } else {
1113         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1114           .addReg(BaseReg, getKillRegState(BaseKill))
1115           .addImm(Pred).addReg(PredReg)
1116           .addReg(EvenReg,
1117                   getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1118           .addReg(OddReg,
1119                   getKillRegState(OddDeadKill)  | getUndefRegState(OddUndef));
1120         ++NumSTRD2STM;
1121       }
1122       NewBBI = llvm::prior(MBBI);
1123     } else {
1124       // Split into two instructions.
1125       unsigned NewOpc = (isLd)
1126         ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1127         : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1128       DebugLoc dl = MBBI->getDebugLoc();
1129       // If this is a load and base register is killed, it may have been
1130       // re-defed by the load, make sure the first load does not clobber it.
1131       if (isLd &&
1132           (BaseKill || OffKill) &&
1133           (TRI->regsOverlap(EvenReg, BaseReg))) {
1134         assert(!TRI->regsOverlap(OddReg, BaseReg));
1135         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
1136                       OddReg, OddDeadKill, false,
1137                       BaseReg, false, BaseUndef, false, OffUndef,
1138                       Pred, PredReg, TII, isT2);
1139         NewBBI = llvm::prior(MBBI);
1140         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1141                       EvenReg, EvenDeadKill, false,
1142                       BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1143                       Pred, PredReg, TII, isT2);
1144       } else {
1145         if (OddReg == EvenReg && EvenDeadKill) {
1146           // If the two source operands are the same, the kill marker is
1147           // probably on the first one. e.g.
1148           // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0
1149           EvenDeadKill = false;
1150           OddDeadKill = true;
1151         }
1152         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1153                       EvenReg, EvenDeadKill, EvenUndef,
1154                       BaseReg, false, BaseUndef, false, OffUndef,
1155                       Pred, PredReg, TII, isT2);
1156         NewBBI = llvm::prior(MBBI);
1157         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
1158                       OddReg, OddDeadKill, OddUndef,
1159                       BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1160                       Pred, PredReg, TII, isT2);
1161       }
1162       if (isLd)
1163         ++NumLDRD2LDR;
1164       else
1165         ++NumSTRD2STR;
1166     }
1167
1168     MBB.erase(MI);
1169     MBBI = NewBBI;
1170     return true;
1171   }
1172   return false;
1173 }
1174
1175 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
1176 /// ops of the same base and incrementing offset into LDM / STM ops.
1177 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1178   unsigned NumMerges = 0;
1179   unsigned NumMemOps = 0;
1180   MemOpQueue MemOps;
1181   unsigned CurrBase = 0;
1182   int CurrOpc = -1;
1183   unsigned CurrSize = 0;
1184   ARMCC::CondCodes CurrPred = ARMCC::AL;
1185   unsigned CurrPredReg = 0;
1186   unsigned Position = 0;
1187   SmallVector<MachineBasicBlock::iterator,4> Merges;
1188
1189   RS->enterBasicBlock(&MBB);
1190   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1191   while (MBBI != E) {
1192     if (FixInvalidRegPairOp(MBB, MBBI))
1193       continue;
1194
1195     bool Advance  = false;
1196     bool TryMerge = false;
1197     bool Clobber  = false;
1198
1199     bool isMemOp = isMemoryOp(MBBI);
1200     if (isMemOp) {
1201       int Opcode = MBBI->getOpcode();
1202       unsigned Size = getLSMultipleTransferSize(MBBI);
1203       const MachineOperand &MO = MBBI->getOperand(0);
1204       unsigned Reg = MO.getReg();
1205       bool isKill = MO.isDef() ? false : MO.isKill();
1206       unsigned Base = MBBI->getOperand(1).getReg();
1207       unsigned PredReg = 0;
1208       ARMCC::CondCodes Pred = llvm::getInstrPredicate(MBBI, PredReg);
1209       int Offset = getMemoryOpOffset(MBBI);
1210       // Watch out for:
1211       // r4 := ldr [r5]
1212       // r5 := ldr [r5, #4]
1213       // r6 := ldr [r5, #8]
1214       //
1215       // The second ldr has effectively broken the chain even though it
1216       // looks like the later ldr(s) use the same base register. Try to
1217       // merge the ldr's so far, including this one. But don't try to
1218       // combine the following ldr(s).
1219       Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg());
1220       if (CurrBase == 0 && !Clobber) {
1221         // Start of a new chain.
1222         CurrBase = Base;
1223         CurrOpc  = Opcode;
1224         CurrSize = Size;
1225         CurrPred = Pred;
1226         CurrPredReg = PredReg;
1227         MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI));
1228         ++NumMemOps;
1229         Advance = true;
1230       } else {
1231         if (Clobber) {
1232           TryMerge = true;
1233           Advance = true;
1234         }
1235
1236         if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1237           // No need to match PredReg.
1238           // Continue adding to the queue.
1239           if (Offset > MemOps.back().Offset) {
1240             MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill,
1241                                              Position, MBBI));
1242             ++NumMemOps;
1243             Advance = true;
1244           } else {
1245             for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
1246                  I != E; ++I) {
1247               if (Offset < I->Offset) {
1248                 MemOps.insert(I, MemOpQueueEntry(Offset, Reg, isKill,
1249                                                  Position, MBBI));
1250                 ++NumMemOps;
1251                 Advance = true;
1252                 break;
1253               } else if (Offset == I->Offset) {
1254                 // Collision! This can't be merged!
1255                 break;
1256               }
1257             }
1258           }
1259         }
1260       }
1261     }
1262
1263     if (MBBI->isDebugValue()) {
1264       ++MBBI;
1265       if (MBBI == E)
1266         // Reach the end of the block, try merging the memory instructions.
1267         TryMerge = true;
1268     } else if (Advance) {
1269       ++Position;
1270       ++MBBI;
1271       if (MBBI == E)
1272         // Reach the end of the block, try merging the memory instructions.
1273         TryMerge = true;
1274     } else
1275       TryMerge = true;
1276
1277     if (TryMerge) {
1278       if (NumMemOps > 1) {
1279         // Try to find a free register to use as a new base in case it's needed.
1280         // First advance to the instruction just before the start of the chain.
1281         AdvanceRS(MBB, MemOps);
1282         // Find a scratch register.
1283         unsigned Scratch = RS->FindUnusedReg(ARM::GPRRegisterClass);
1284         // Process the load / store instructions.
1285         RS->forward(prior(MBBI));
1286
1287         // Merge ops.
1288         Merges.clear();
1289         MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize,
1290                      CurrPred, CurrPredReg, Scratch, MemOps, Merges);
1291
1292         // Try folding preceding/trailing base inc/dec into the generated
1293         // LDM/STM ops.
1294         for (unsigned i = 0, e = Merges.size(); i < e; ++i)
1295           if (MergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI))
1296             ++NumMerges;
1297         NumMerges += Merges.size();
1298
1299         // Try folding preceding/trailing base inc/dec into those load/store
1300         // that were not merged to form LDM/STM ops.
1301         for (unsigned i = 0; i != NumMemOps; ++i)
1302           if (!MemOps[i].Merged)
1303             if (MergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI))
1304               ++NumMerges;
1305
1306         // RS may be pointing to an instruction that's deleted.
1307         RS->skipTo(prior(MBBI));
1308       } else if (NumMemOps == 1) {
1309         // Try folding preceding/trailing base inc/dec into the single
1310         // load/store.
1311         if (MergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) {
1312           ++NumMerges;
1313           RS->forward(prior(MBBI));
1314         }
1315       }
1316
1317       CurrBase = 0;
1318       CurrOpc = -1;
1319       CurrSize = 0;
1320       CurrPred = ARMCC::AL;
1321       CurrPredReg = 0;
1322       if (NumMemOps) {
1323         MemOps.clear();
1324         NumMemOps = 0;
1325       }
1326
1327       // If iterator hasn't been advanced and this is not a memory op, skip it.
1328       // It can't start a new chain anyway.
1329       if (!Advance && !isMemOp && MBBI != E) {
1330         ++Position;
1331         ++MBBI;
1332       }
1333     }
1334   }
1335   return NumMerges > 0;
1336 }
1337
1338 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return ops
1339 /// ("bx lr" and "mov pc, lr") into the preceding stack restore so it
1340 /// directly restore the value of LR into pc.
1341 ///   ldmfd sp!, {..., lr}
1342 ///   bx lr
1343 /// or
1344 ///   ldmfd sp!, {..., lr}
1345 ///   mov pc, lr
1346 /// =>
1347 ///   ldmfd sp!, {..., pc}
1348 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1349   if (MBB.empty()) return false;
1350
1351   MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1352   if (MBBI != MBB.begin() &&
1353       (MBBI->getOpcode() == ARM::BX_RET ||
1354        MBBI->getOpcode() == ARM::tBX_RET ||
1355        MBBI->getOpcode() == ARM::MOVPCLR)) {
1356     MachineInstr *PrevMI = prior(MBBI);
1357     unsigned Opcode = PrevMI->getOpcode();
1358     if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1359         Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1360         Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
1361       MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
1362       if (MO.getReg() != ARM::LR)
1363         return false;
1364       unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1365       assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1366               Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1367       PrevMI->setDesc(TII->get(NewOpc));
1368       MO.setReg(ARM::PC);
1369       PrevMI->copyImplicitOps(&*MBBI);
1370       MBB.erase(MBBI);
1371       return true;
1372     }
1373   }
1374   return false;
1375 }
1376
1377 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1378   const TargetMachine &TM = Fn.getTarget();
1379   AFI = Fn.getInfo<ARMFunctionInfo>();
1380   TII = TM.getInstrInfo();
1381   TRI = TM.getRegisterInfo();
1382   RS = new RegScavenger();
1383   isThumb2 = AFI->isThumb2Function();
1384
1385   bool Modified = false;
1386   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1387        ++MFI) {
1388     MachineBasicBlock &MBB = *MFI;
1389     Modified |= LoadStoreMultipleOpti(MBB);
1390     if (TM.getSubtarget<ARMSubtarget>().hasV5TOps())
1391       Modified |= MergeReturnIntoLDM(MBB);
1392   }
1393
1394   delete RS;
1395   return Modified;
1396 }
1397
1398
1399 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move
1400 /// load / stores from consecutive locations close to make it more
1401 /// likely they will be combined later.
1402
1403 namespace {
1404   struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
1405     static char ID;
1406     ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
1407
1408     const TargetData *TD;
1409     const TargetInstrInfo *TII;
1410     const TargetRegisterInfo *TRI;
1411     const ARMSubtarget *STI;
1412     MachineRegisterInfo *MRI;
1413     MachineFunction *MF;
1414
1415     virtual bool runOnMachineFunction(MachineFunction &Fn);
1416
1417     virtual const char *getPassName() const {
1418       return "ARM pre- register allocation load / store optimization pass";
1419     }
1420
1421   private:
1422     bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
1423                           unsigned &NewOpc, unsigned &EvenReg,
1424                           unsigned &OddReg, unsigned &BaseReg,
1425                           int &Offset,
1426                           unsigned &PredReg, ARMCC::CondCodes &Pred,
1427                           bool &isT2);
1428     bool RescheduleOps(MachineBasicBlock *MBB,
1429                        SmallVector<MachineInstr*, 4> &Ops,
1430                        unsigned Base, bool isLd,
1431                        DenseMap<MachineInstr*, unsigned> &MI2LocMap);
1432     bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
1433   };
1434   char ARMPreAllocLoadStoreOpt::ID = 0;
1435 }
1436
1437 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1438   TD  = Fn.getTarget().getTargetData();
1439   TII = Fn.getTarget().getInstrInfo();
1440   TRI = Fn.getTarget().getRegisterInfo();
1441   STI = &Fn.getTarget().getSubtarget<ARMSubtarget>();
1442   MRI = &Fn.getRegInfo();
1443   MF  = &Fn;
1444
1445   bool Modified = false;
1446   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1447        ++MFI)
1448     Modified |= RescheduleLoadStoreInstrs(MFI);
1449
1450   return Modified;
1451 }
1452
1453 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
1454                                       MachineBasicBlock::iterator I,
1455                                       MachineBasicBlock::iterator E,
1456                                       SmallPtrSet<MachineInstr*, 4> &MemOps,
1457                                       SmallSet<unsigned, 4> &MemRegs,
1458                                       const TargetRegisterInfo *TRI) {
1459   // Are there stores / loads / calls between them?
1460   // FIXME: This is overly conservative. We should make use of alias information
1461   // some day.
1462   SmallSet<unsigned, 4> AddedRegPressure;
1463   while (++I != E) {
1464     if (I->isDebugValue() || MemOps.count(&*I))
1465       continue;
1466     const MCInstrDesc &MCID = I->getDesc();
1467     if (MCID.isCall() || MCID.isTerminator() || I->hasUnmodeledSideEffects())
1468       return false;
1469     if (isLd && MCID.mayStore())
1470       return false;
1471     if (!isLd) {
1472       if (MCID.mayLoad())
1473         return false;
1474       // It's not safe to move the first 'str' down.
1475       // str r1, [r0]
1476       // strh r5, [r0]
1477       // str r4, [r0, #+4]
1478       if (MCID.mayStore())
1479         return false;
1480     }
1481     for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
1482       MachineOperand &MO = I->getOperand(j);
1483       if (!MO.isReg())
1484         continue;
1485       unsigned Reg = MO.getReg();
1486       if (MO.isDef() && TRI->regsOverlap(Reg, Base))
1487         return false;
1488       if (Reg != Base && !MemRegs.count(Reg))
1489         AddedRegPressure.insert(Reg);
1490     }
1491   }
1492
1493   // Estimate register pressure increase due to the transformation.
1494   if (MemRegs.size() <= 4)
1495     // Ok if we are moving small number of instructions.
1496     return true;
1497   return AddedRegPressure.size() <= MemRegs.size() * 2;
1498 }
1499
1500 bool
1501 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
1502                                           DebugLoc &dl,
1503                                           unsigned &NewOpc, unsigned &EvenReg,
1504                                           unsigned &OddReg, unsigned &BaseReg,
1505                                           int &Offset, unsigned &PredReg,
1506                                           ARMCC::CondCodes &Pred,
1507                                           bool &isT2) {
1508   // Make sure we're allowed to generate LDRD/STRD.
1509   if (!STI->hasV5TEOps())
1510     return false;
1511
1512   // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
1513   unsigned Scale = 1;
1514   unsigned Opcode = Op0->getOpcode();
1515   if (Opcode == ARM::LDRi12)
1516     NewOpc = ARM::LDRD;
1517   else if (Opcode == ARM::STRi12)
1518     NewOpc = ARM::STRD;
1519   else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
1520     NewOpc = ARM::t2LDRDi8;
1521     Scale = 4;
1522     isT2 = true;
1523   } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
1524     NewOpc = ARM::t2STRDi8;
1525     Scale = 4;
1526     isT2 = true;
1527   } else
1528     return false;
1529
1530   // Make sure the base address satisfies i64 ld / st alignment requirement.
1531   if (!Op0->hasOneMemOperand() ||
1532       !(*Op0->memoperands_begin())->getValue() ||
1533       (*Op0->memoperands_begin())->isVolatile())
1534     return false;
1535
1536   unsigned Align = (*Op0->memoperands_begin())->getAlignment();
1537   const Function *Func = MF->getFunction();
1538   unsigned ReqAlign = STI->hasV6Ops()
1539     ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext()))
1540     : 8;  // Pre-v6 need 8-byte align
1541   if (Align < ReqAlign)
1542     return false;
1543
1544   // Then make sure the immediate offset fits.
1545   int OffImm = getMemoryOpOffset(Op0);
1546   if (isT2) {
1547     int Limit = (1 << 8) * Scale;
1548     if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
1549       return false;
1550     Offset = OffImm;
1551   } else {
1552     ARM_AM::AddrOpc AddSub = ARM_AM::add;
1553     if (OffImm < 0) {
1554       AddSub = ARM_AM::sub;
1555       OffImm = - OffImm;
1556     }
1557     int Limit = (1 << 8) * Scale;
1558     if (OffImm >= Limit || (OffImm & (Scale-1)))
1559       return false;
1560     Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
1561   }
1562   EvenReg = Op0->getOperand(0).getReg();
1563   OddReg  = Op1->getOperand(0).getReg();
1564   if (EvenReg == OddReg)
1565     return false;
1566   BaseReg = Op0->getOperand(1).getReg();
1567   Pred = llvm::getInstrPredicate(Op0, PredReg);
1568   dl = Op0->getDebugLoc();
1569   return true;
1570 }
1571
1572 namespace {
1573   struct OffsetCompare {
1574     bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
1575       int LOffset = getMemoryOpOffset(LHS);
1576       int ROffset = getMemoryOpOffset(RHS);
1577       assert(LHS == RHS || LOffset != ROffset);
1578       return LOffset > ROffset;
1579     }
1580   };
1581 }
1582
1583 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
1584                                  SmallVector<MachineInstr*, 4> &Ops,
1585                                  unsigned Base, bool isLd,
1586                                  DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
1587   bool RetVal = false;
1588
1589   // Sort by offset (in reverse order).
1590   std::sort(Ops.begin(), Ops.end(), OffsetCompare());
1591
1592   // The loads / stores of the same base are in order. Scan them from first to
1593   // last and check for the following:
1594   // 1. Any def of base.
1595   // 2. Any gaps.
1596   while (Ops.size() > 1) {
1597     unsigned FirstLoc = ~0U;
1598     unsigned LastLoc = 0;
1599     MachineInstr *FirstOp = 0;
1600     MachineInstr *LastOp = 0;
1601     int LastOffset = 0;
1602     unsigned LastOpcode = 0;
1603     unsigned LastBytes = 0;
1604     unsigned NumMove = 0;
1605     for (int i = Ops.size() - 1; i >= 0; --i) {
1606       MachineInstr *Op = Ops[i];
1607       unsigned Loc = MI2LocMap[Op];
1608       if (Loc <= FirstLoc) {
1609         FirstLoc = Loc;
1610         FirstOp = Op;
1611       }
1612       if (Loc >= LastLoc) {
1613         LastLoc = Loc;
1614         LastOp = Op;
1615       }
1616
1617       unsigned Opcode = Op->getOpcode();
1618       if (LastOpcode && Opcode != LastOpcode)
1619         break;
1620
1621       int Offset = getMemoryOpOffset(Op);
1622       unsigned Bytes = getLSMultipleTransferSize(Op);
1623       if (LastBytes) {
1624         if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
1625           break;
1626       }
1627       LastOffset = Offset;
1628       LastBytes = Bytes;
1629       LastOpcode = Opcode;
1630       if (++NumMove == 8) // FIXME: Tune this limit.
1631         break;
1632     }
1633
1634     if (NumMove <= 1)
1635       Ops.pop_back();
1636     else {
1637       SmallPtrSet<MachineInstr*, 4> MemOps;
1638       SmallSet<unsigned, 4> MemRegs;
1639       for (int i = NumMove-1; i >= 0; --i) {
1640         MemOps.insert(Ops[i]);
1641         MemRegs.insert(Ops[i]->getOperand(0).getReg());
1642       }
1643
1644       // Be conservative, if the instructions are too far apart, don't
1645       // move them. We want to limit the increase of register pressure.
1646       bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
1647       if (DoMove)
1648         DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
1649                                            MemOps, MemRegs, TRI);
1650       if (!DoMove) {
1651         for (unsigned i = 0; i != NumMove; ++i)
1652           Ops.pop_back();
1653       } else {
1654         // This is the new location for the loads / stores.
1655         MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
1656         while (InsertPos != MBB->end()
1657                && (MemOps.count(InsertPos) || InsertPos->isDebugValue()))
1658           ++InsertPos;
1659
1660         // If we are moving a pair of loads / stores, see if it makes sense
1661         // to try to allocate a pair of registers that can form register pairs.
1662         MachineInstr *Op0 = Ops.back();
1663         MachineInstr *Op1 = Ops[Ops.size()-2];
1664         unsigned EvenReg = 0, OddReg = 0;
1665         unsigned BaseReg = 0, PredReg = 0;
1666         ARMCC::CondCodes Pred = ARMCC::AL;
1667         bool isT2 = false;
1668         unsigned NewOpc = 0;
1669         int Offset = 0;
1670         DebugLoc dl;
1671         if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
1672                                              EvenReg, OddReg, BaseReg,
1673                                              Offset, PredReg, Pred, isT2)) {
1674           Ops.pop_back();
1675           Ops.pop_back();
1676
1677           const MCInstrDesc &MCID = TII->get(NewOpc);
1678           const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI);
1679           MRI->constrainRegClass(EvenReg, TRC);
1680           MRI->constrainRegClass(OddReg, TRC);
1681
1682           // Form the pair instruction.
1683           if (isLd) {
1684             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
1685               .addReg(EvenReg, RegState::Define)
1686               .addReg(OddReg, RegState::Define)
1687               .addReg(BaseReg);
1688             // FIXME: We're converting from LDRi12 to an insn that still
1689             // uses addrmode2, so we need an explicit offset reg. It should
1690             // always by reg0 since we're transforming LDRi12s.
1691             if (!isT2)
1692               MIB.addReg(0);
1693             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1694             ++NumLDRDFormed;
1695           } else {
1696             MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
1697               .addReg(EvenReg)
1698               .addReg(OddReg)
1699               .addReg(BaseReg);
1700             // FIXME: We're converting from LDRi12 to an insn that still
1701             // uses addrmode2, so we need an explicit offset reg. It should
1702             // always by reg0 since we're transforming STRi12s.
1703             if (!isT2)
1704               MIB.addReg(0);
1705             MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1706             ++NumSTRDFormed;
1707           }
1708           MBB->erase(Op0);
1709           MBB->erase(Op1);
1710
1711           // Add register allocation hints to form register pairs.
1712           MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg);
1713           MRI->setRegAllocationHint(OddReg,  ARMRI::RegPairOdd, EvenReg);
1714         } else {
1715           for (unsigned i = 0; i != NumMove; ++i) {
1716             MachineInstr *Op = Ops.back();
1717             Ops.pop_back();
1718             MBB->splice(InsertPos, MBB, Op);
1719           }
1720         }
1721
1722         NumLdStMoved += NumMove;
1723         RetVal = true;
1724       }
1725     }
1726   }
1727
1728   return RetVal;
1729 }
1730
1731 bool
1732 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
1733   bool RetVal = false;
1734
1735   DenseMap<MachineInstr*, unsigned> MI2LocMap;
1736   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
1737   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
1738   SmallVector<unsigned, 4> LdBases;
1739   SmallVector<unsigned, 4> StBases;
1740
1741   unsigned Loc = 0;
1742   MachineBasicBlock::iterator MBBI = MBB->begin();
1743   MachineBasicBlock::iterator E = MBB->end();
1744   while (MBBI != E) {
1745     for (; MBBI != E; ++MBBI) {
1746       MachineInstr *MI = MBBI;
1747       const MCInstrDesc &MCID = MI->getDesc();
1748       if (MCID.isCall() || MCID.isTerminator()) {
1749         // Stop at barriers.
1750         ++MBBI;
1751         break;
1752       }
1753
1754       if (!MI->isDebugValue())
1755         MI2LocMap[MI] = ++Loc;
1756
1757       if (!isMemoryOp(MI))
1758         continue;
1759       unsigned PredReg = 0;
1760       if (llvm::getInstrPredicate(MI, PredReg) != ARMCC::AL)
1761         continue;
1762
1763       int Opc = MI->getOpcode();
1764       bool isLd = isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
1765       unsigned Base = MI->getOperand(1).getReg();
1766       int Offset = getMemoryOpOffset(MI);
1767
1768       bool StopHere = false;
1769       if (isLd) {
1770         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1771           Base2LdsMap.find(Base);
1772         if (BI != Base2LdsMap.end()) {
1773           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1774             if (Offset == getMemoryOpOffset(BI->second[i])) {
1775               StopHere = true;
1776               break;
1777             }
1778           }
1779           if (!StopHere)
1780             BI->second.push_back(MI);
1781         } else {
1782           SmallVector<MachineInstr*, 4> MIs;
1783           MIs.push_back(MI);
1784           Base2LdsMap[Base] = MIs;
1785           LdBases.push_back(Base);
1786         }
1787       } else {
1788         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1789           Base2StsMap.find(Base);
1790         if (BI != Base2StsMap.end()) {
1791           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1792             if (Offset == getMemoryOpOffset(BI->second[i])) {
1793               StopHere = true;
1794               break;
1795             }
1796           }
1797           if (!StopHere)
1798             BI->second.push_back(MI);
1799         } else {
1800           SmallVector<MachineInstr*, 4> MIs;
1801           MIs.push_back(MI);
1802           Base2StsMap[Base] = MIs;
1803           StBases.push_back(Base);
1804         }
1805       }
1806
1807       if (StopHere) {
1808         // Found a duplicate (a base+offset combination that's seen earlier).
1809         // Backtrack.
1810         --Loc;
1811         break;
1812       }
1813     }
1814
1815     // Re-schedule loads.
1816     for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
1817       unsigned Base = LdBases[i];
1818       SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base];
1819       if (Lds.size() > 1)
1820         RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
1821     }
1822
1823     // Re-schedule stores.
1824     for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
1825       unsigned Base = StBases[i];
1826       SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base];
1827       if (Sts.size() > 1)
1828         RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
1829     }
1830
1831     if (MBBI != E) {
1832       Base2LdsMap.clear();
1833       Base2StsMap.clear();
1834       LdBases.clear();
1835       StBases.clear();
1836     }
1837   }
1838
1839   return RetVal;
1840 }
1841
1842
1843 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
1844 /// optimization pass.
1845 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
1846   if (PreAlloc)
1847     return new ARMPreAllocLoadStoreOpt();
1848   return new ARMLoadStoreOpt();
1849 }