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