lib/Target/ARM/ARMLoadStoreOptimizer.cpp

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