lib/Target/ARM/ARMLoadStoreOptimizer.cpp

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