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