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 "ARMAddressingModes.h"
  18 #include "ARMMachineFunctionInfo.h"
  19 #include "ARMRegisterInfo.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/RegisterScavenging.h"
  27 #include "llvm/Target/TargetData.h"
  28 #include "llvm/Target/TargetInstrInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/Target/TargetRegisterInfo.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/ADT/DenseMap.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include "llvm/ADT/SmallPtrSet.h"
  35 #include "llvm/ADT/SmallSet.h"
  36 #include "llvm/ADT/SmallVector.h"
  37 #include "llvm/ADT/Statistic.h"
  38 using namespace llvm;
  39
  40 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
  41 STATISTIC(NumSTMGened , "Number of stm instructions generated");
  42 STATISTIC(NumFLDMGened, "Number of fldm instructions generated");
  43 STATISTIC(NumFSTMGened, "Number of fstm instructions generated");
  44 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
  45 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
  46 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
  47 STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
  48 STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
  49 STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
  50 STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");
  51
  52 /// ARMAllocLoadStoreOpt - Post- register allocation pass the combine
  53 /// load / store instructions to form ldm / stm instructions.
  54
  55 namespace {
  56   struct VISIBILITY_HIDDEN ARMLoadStoreOpt : public MachineFunctionPass {
  57     static char ID;
  58     ARMLoadStoreOpt() : MachineFunctionPass(&ID) {}
  59
  60     const TargetInstrInfo *TII;
  61     const TargetRegisterInfo *TRI;
  62     ARMFunctionInfo *AFI;
  63     RegScavenger *RS;
  64
  65     virtual bool runOnMachineFunction(MachineFunction &Fn);
  66
  67     virtual const char *getPassName() const {
  68       return "ARM load / store optimization pass";
  69     }
  70
  71   private:
  72     struct MemOpQueueEntry {
  73       int Offset;
  74       unsigned Position;
  75       MachineBasicBlock::iterator MBBI;
  76       bool Merged;
  77       MemOpQueueEntry(int o, int p, MachineBasicBlock::iterator i)
  78         : Offset(o), Position(p), MBBI(i), Merged(false) {};
  79     };
  80     typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
  81     typedef MemOpQueue::iterator MemOpQueueIter;
  82
  83     bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
  84                   int Offset, unsigned Base, bool BaseKill, int Opcode,
  85                   ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
  86                   DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs);
  87     void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
  88                       int Opcode, unsigned Size,
  89                       ARMCC::CondCodes Pred, unsigned PredReg,
  90                       unsigned Scratch, MemOpQueue &MemOps,
  91                       SmallVector<MachineBasicBlock::iterator, 4> &Merges);
  92
  93     void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
  94     bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
  95                              MachineBasicBlock::iterator &MBBI);
  96     bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
  97     bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
  98   };
  99   char ARMLoadStoreOpt::ID = 0;
 100 }
 101
 102 static int getLoadStoreMultipleOpcode(int Opcode) {
 103   switch (Opcode) {
 104   case ARM::LDR:
 105     NumLDMGened++;
 106     return ARM::LDM;
 107   case ARM::STR:
 108     NumSTMGened++;
 109     return ARM::STM;
 110   case ARM::FLDS:
 111     NumFLDMGened++;
 112     return ARM::FLDMS;
 113   case ARM::FSTS:
 114     NumFSTMGened++;
 115     return ARM::FSTMS;
 116   case ARM::FLDD:
 117     NumFLDMGened++;
 118     return ARM::FLDMD;
 119   case ARM::FSTD:
 120     NumFSTMGened++;
 121     return ARM::FSTMD;
 122   default: abort();
 123   }
 124   return 0;
 125 }
 126
 127 /// MergeOps - Create and insert a LDM or STM with Base as base register and
 128 /// registers in Regs as the register operands that would be loaded / stored.
 129 /// It returns true if the transformation is done.
 130 bool
 131 ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
 132                           MachineBasicBlock::iterator MBBI,
 133                           int Offset, unsigned Base, bool BaseKill,
 134                           int Opcode, ARMCC::CondCodes Pred,
 135                           unsigned PredReg, unsigned Scratch, DebugLoc dl,
 136                           SmallVector<std::pair<unsigned, bool>, 8> &Regs) {
 137   // Only a single register to load / store. Don't bother.
 138   unsigned NumRegs = Regs.size();
 139   if (NumRegs <= 1)
 140     return false;
 141
 142   ARM_AM::AMSubMode Mode = ARM_AM::ia;
 143   bool isAM4 = Opcode == ARM::LDR || Opcode == ARM::STR;
 144   if (isAM4 && Offset == 4)
 145     Mode = ARM_AM::ib;
 146   else if (isAM4 && Offset == -4 * (int)NumRegs + 4)
 147     Mode = ARM_AM::da;
 148   else if (isAM4 && Offset == -4 * (int)NumRegs)
 149     Mode = ARM_AM::db;
 150   else if (Offset != 0) {
 151     // If starting offset isn't zero, insert a MI to materialize a new base.
 152     // But only do so if it is cost effective, i.e. merging more than two
 153     // loads / stores.
 154     if (NumRegs <= 2)
 155       return false;
 156
 157     unsigned NewBase;
 158     if (Opcode == ARM::LDR)
 159       // If it is a load, then just use one of the destination register to
 160       // use as the new base.
 161       NewBase = Regs[NumRegs-1].first;
 162     else {
 163       // Use the scratch register to use as a new base.
 164       NewBase = Scratch;
 165       if (NewBase == 0)
 166         return false;
 167     }
 168     int BaseOpc = ARM::ADDri;
 169     if (Offset < 0) {
 170       BaseOpc = ARM::SUBri;
 171       Offset = - Offset;
 172     }
 173     int ImmedOffset = ARM_AM::getSOImmVal(Offset);
 174     if (ImmedOffset == -1)
 175       return false;  // Probably not worth it then.
 176
 177     BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase)
 178       .addReg(Base, getKillRegState(BaseKill)).addImm(ImmedOffset)
 179       .addImm(Pred).addReg(PredReg).addReg(0);
 180     Base = NewBase;
 181     BaseKill = true;  // New base is always killed right its use.
 182   }
 183
 184   bool isDPR = Opcode == ARM::FLDD || Opcode == ARM::FSTD;
 185   bool isDef = Opcode == ARM::LDR || Opcode == ARM::FLDS || Opcode == ARM::FLDD;
 186   Opcode = getLoadStoreMultipleOpcode(Opcode);
 187   MachineInstrBuilder MIB = (isAM4)
 188     ? BuildMI(MBB, MBBI, dl, TII->get(Opcode))
 189         .addReg(Base, getKillRegState(BaseKill))
 190         .addImm(ARM_AM::getAM4ModeImm(Mode)).addImm(Pred).addReg(PredReg)
 191     : BuildMI(MBB, MBBI, dl, TII->get(Opcode))
 192         .addReg(Base, getKillRegState(BaseKill))
 193         .addImm(ARM_AM::getAM5Opc(Mode, false, isDPR ? NumRegs<<1 : NumRegs))
 194         .addImm(Pred).addReg(PredReg);
 195   for (unsigned i = 0; i != NumRegs; ++i)
 196     MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef)
 197                      | getKillRegState(Regs[i].second));
 198
 199   return true;
 200 }
 201
 202 /// MergeLDR_STR - Merge a number of load / store instructions into one or more
 203 /// load / store multiple instructions.
 204 void
 205 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
 206                           unsigned Base, int Opcode, unsigned Size,
 207                           ARMCC::CondCodes Pred, unsigned PredReg,
 208                           unsigned Scratch, MemOpQueue &MemOps,
 209                           SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
 210   bool isAM4 = Opcode == ARM::LDR || Opcode == ARM::STR;
 211   int Offset = MemOps[SIndex].Offset;
 212   int SOffset = Offset;
 213   unsigned Pos = MemOps[SIndex].Position;
 214   MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
 215   DebugLoc dl = Loc->getDebugLoc();
 216   unsigned PReg = Loc->getOperand(0).getReg();
 217   unsigned PRegNum = ARMRegisterInfo::getRegisterNumbering(PReg);
 218   bool isKill = Loc->getOperand(0).isKill();
 219
 220   SmallVector<std::pair<unsigned,bool>, 8> Regs;
 221   Regs.push_back(std::make_pair(PReg, isKill));
 222   for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
 223     int NewOffset = MemOps[i].Offset;
 224     unsigned Reg = MemOps[i].MBBI->getOperand(0).getReg();
 225     unsigned RegNum = ARMRegisterInfo::getRegisterNumbering(Reg);
 226     isKill = MemOps[i].MBBI->getOperand(0).isKill();
 227     // AM4 - register numbers in ascending order.
 228     // AM5 - consecutive register numbers in ascending order.
 229     if (NewOffset == Offset + (int)Size &&
 230         ((isAM4 && RegNum > PRegNum) || RegNum == PRegNum+1)) {
 231       Offset += Size;
 232       Regs.push_back(std::make_pair(Reg, isKill));
 233       PRegNum = RegNum;
 234     } else {
 235       // Can't merge this in. Try merge the earlier ones first.
 236       if (MergeOps(MBB, ++Loc, SOffset, Base, false, Opcode, Pred, PredReg,
 237                    Scratch, dl, Regs)) {
 238         Merges.push_back(prior(Loc));
 239         for (unsigned j = SIndex; j < i; ++j) {
 240           MBB.erase(MemOps[j].MBBI);
 241           MemOps[j].Merged = true;
 242         }
 243       }
 244       MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch,
 245                    MemOps, Merges);
 246       return;
 247     }
 248
 249     if (MemOps[i].Position > Pos) {
 250       Pos = MemOps[i].Position;
 251       Loc = MemOps[i].MBBI;
 252     }
 253   }
 254
 255   bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1;
 256   if (MergeOps(MBB, ++Loc, SOffset, Base, BaseKill, Opcode, Pred, PredReg,
 257                Scratch, dl, Regs)) {
 258     Merges.push_back(prior(Loc));
 259     for (unsigned i = SIndex, e = MemOps.size(); i != e; ++i) {
 260       MBB.erase(MemOps[i].MBBI);
 261       MemOps[i].Merged = true;
 262     }
 263   }
 264
 265   return;
 266 }
 267
 268 /// getInstrPredicate - If instruction is predicated, returns its predicate
 269 /// condition, otherwise returns AL. It also returns the condition code
 270 /// register by reference.
 271 static ARMCC::CondCodes getInstrPredicate(MachineInstr *MI, unsigned &PredReg) {
 272   int PIdx = MI->findFirstPredOperandIdx();
 273   if (PIdx == -1) {
 274     PredReg = 0;
 275     return ARMCC::AL;
 276   }
 277
 278   PredReg = MI->getOperand(PIdx+1).getReg();
 279   return (ARMCC::CondCodes)MI->getOperand(PIdx).getImm();
 280 }
 281
 282 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
 283                                        unsigned Bytes, ARMCC::CondCodes Pred,
 284                                        unsigned PredReg) {
 285   unsigned MyPredReg = 0;
 286   return (MI && MI->getOpcode() == ARM::SUBri &&
 287           MI->getOperand(0).getReg() == Base &&
 288           MI->getOperand(1).getReg() == Base &&
 289           ARM_AM::getAM2Offset(MI->getOperand(2).getImm()) == Bytes &&
 290           getInstrPredicate(MI, MyPredReg) == Pred &&
 291           MyPredReg == PredReg);
 292 }
 293
 294 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
 295                                        unsigned Bytes, ARMCC::CondCodes Pred,
 296                                        unsigned PredReg) {
 297   unsigned MyPredReg = 0;
 298   return (MI && MI->getOpcode() == ARM::ADDri &&
 299           MI->getOperand(0).getReg() == Base &&
 300           MI->getOperand(1).getReg() == Base &&
 301           ARM_AM::getAM2Offset(MI->getOperand(2).getImm()) == Bytes &&
 302           getInstrPredicate(MI, MyPredReg) == Pred &&
 303           MyPredReg == PredReg);
 304 }
 305
 306 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
 307   switch (MI->getOpcode()) {
 308   default: return 0;
 309   case ARM::LDR:
 310   case ARM::STR:
 311   case ARM::FLDS:
 312   case ARM::FSTS:
 313     return 4;
 314   case ARM::FLDD:
 315   case ARM::FSTD:
 316     return 8;
 317   case ARM::LDM:
 318   case ARM::STM:
 319     return (MI->getNumOperands() - 4) * 4;
 320   case ARM::FLDMS:
 321   case ARM::FSTMS:
 322   case ARM::FLDMD:
 323   case ARM::FSTMD:
 324     return ARM_AM::getAM5Offset(MI->getOperand(1).getImm()) * 4;
 325   }
 326 }
 327
 328 /// mergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
 329 /// register into the LDM/STM/FLDM{D|S}/FSTM{D|S} op when possible:
 330 ///
 331 /// stmia rn, <ra, rb, rc>
 332 /// rn := rn + 4 * 3;
 333 /// =>
 334 /// stmia rn!, <ra, rb, rc>
 335 ///
 336 /// rn := rn - 4 * 3;
 337 /// ldmia rn, <ra, rb, rc>
 338 /// =>
 339 /// ldmdb rn!, <ra, rb, rc>
 340 static bool mergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
 341                                       MachineBasicBlock::iterator MBBI,
 342                                       bool &Advance,
 343                                       MachineBasicBlock::iterator &I) {
 344   MachineInstr *MI = MBBI;
 345   unsigned Base = MI->getOperand(0).getReg();
 346   unsigned Bytes = getLSMultipleTransferSize(MI);
 347   unsigned PredReg = 0;
 348   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
 349   int Opcode = MI->getOpcode();
 350   bool isAM4 = Opcode == ARM::LDM || Opcode == ARM::STM;
 351
 352   if (isAM4) {
 353     if (ARM_AM::getAM4WBFlag(MI->getOperand(1).getImm()))
 354       return false;
 355
 356     // Can't use the updating AM4 sub-mode if the base register is also a dest
 357     // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
 358     for (unsigned i = 3, e = MI->getNumOperands(); i != e; ++i) {
 359       if (MI->getOperand(i).getReg() == Base)
 360         return false;
 361     }
 362
 363     ARM_AM::AMSubMode Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm());
 364     if (MBBI != MBB.begin()) {
 365       MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 366       if (Mode == ARM_AM::ia &&
 367           isMatchingDecrement(PrevMBBI, Base, Bytes, Pred, PredReg)) {
 368         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::db, true));
 369         MBB.erase(PrevMBBI);
 370         return true;
 371       } else if (Mode == ARM_AM::ib &&
 372                  isMatchingDecrement(PrevMBBI, Base, Bytes, Pred, PredReg)) {
 373         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::da, true));
 374         MBB.erase(PrevMBBI);
 375         return true;
 376       }
 377     }
 378
 379     if (MBBI != MBB.end()) {
 380       MachineBasicBlock::iterator NextMBBI = next(MBBI);
 381       if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
 382           isMatchingIncrement(NextMBBI, Base, Bytes, Pred, PredReg)) {
 383         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
 384         if (NextMBBI == I) {
 385           Advance = true;
 386           ++I;
 387         }
 388         MBB.erase(NextMBBI);
 389         return true;
 390       } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
 391                  isMatchingDecrement(NextMBBI, Base, Bytes, Pred, PredReg)) {
 392         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
 393         if (NextMBBI == I) {
 394           Advance = true;
 395           ++I;
 396         }
 397         MBB.erase(NextMBBI);
 398         return true;
 399       }
 400     }
 401   } else {
 402     // FLDM{D|S}, FSTM{D|S} addressing mode 5 ops.
 403     if (ARM_AM::getAM5WBFlag(MI->getOperand(1).getImm()))
 404       return false;
 405
 406     ARM_AM::AMSubMode Mode = ARM_AM::getAM5SubMode(MI->getOperand(1).getImm());
 407     unsigned Offset = ARM_AM::getAM5Offset(MI->getOperand(1).getImm());
 408     if (MBBI != MBB.begin()) {
 409       MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 410       if (Mode == ARM_AM::ia &&
 411           isMatchingDecrement(PrevMBBI, Base, Bytes, Pred, PredReg)) {
 412         MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::db, true, Offset));
 413         MBB.erase(PrevMBBI);
 414         return true;
 415       }
 416     }
 417
 418     if (MBBI != MBB.end()) {
 419       MachineBasicBlock::iterator NextMBBI = next(MBBI);
 420       if (Mode == ARM_AM::ia &&
 421           isMatchingIncrement(NextMBBI, Base, Bytes, Pred, PredReg)) {
 422         MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::ia, true, Offset));
 423         if (NextMBBI == I) {
 424           Advance = true;
 425           ++I;
 426         }
 427         MBB.erase(NextMBBI);
 428       }
 429       return true;
 430     }
 431   }
 432
 433   return false;
 434 }
 435
 436 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) {
 437   switch (Opc) {
 438   case ARM::LDR: return ARM::LDR_PRE;
 439   case ARM::STR: return ARM::STR_PRE;
 440   case ARM::FLDS: return ARM::FLDMS;
 441   case ARM::FLDD: return ARM::FLDMD;
 442   case ARM::FSTS: return ARM::FSTMS;
 443   case ARM::FSTD: return ARM::FSTMD;
 444   default: abort();
 445   }
 446   return 0;
 447 }
 448
 449 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) {
 450   switch (Opc) {
 451   case ARM::LDR: return ARM::LDR_POST;
 452   case ARM::STR: return ARM::STR_POST;
 453   case ARM::FLDS: return ARM::FLDMS;
 454   case ARM::FLDD: return ARM::FLDMD;
 455   case ARM::FSTS: return ARM::FSTMS;
 456   case ARM::FSTD: return ARM::FSTMD;
 457   default: abort();
 458   }
 459   return 0;
 460 }
 461
 462 /// mergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
 463 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
 464 static bool mergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
 465                                      MachineBasicBlock::iterator MBBI,
 466                                      const TargetInstrInfo *TII,
 467                                      bool &Advance,
 468                                      MachineBasicBlock::iterator &I) {
 469   MachineInstr *MI = MBBI;
 470   unsigned Base = MI->getOperand(1).getReg();
 471   bool BaseKill = MI->getOperand(1).isKill();
 472   unsigned Bytes = getLSMultipleTransferSize(MI);
 473   int Opcode = MI->getOpcode();
 474   DebugLoc dl = MI->getDebugLoc();
 475   bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
 476   if ((isAM2 && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0) ||
 477       (!isAM2 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0))
 478     return false;
 479
 480   bool isLd = Opcode == ARM::LDR || Opcode == ARM::FLDS || Opcode == ARM::FLDD;
 481   // Can't do the merge if the destination register is the same as the would-be
 482   // writeback register.
 483   if (isLd && MI->getOperand(0).getReg() == Base)
 484     return false;
 485
 486   unsigned PredReg = 0;
 487   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
 488   bool DoMerge = false;
 489   ARM_AM::AddrOpc AddSub = ARM_AM::add;
 490   unsigned NewOpc = 0;
 491   if (MBBI != MBB.begin()) {
 492     MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 493     if (isMatchingDecrement(PrevMBBI, Base, Bytes, Pred, PredReg)) {
 494       DoMerge = true;
 495       AddSub = ARM_AM::sub;
 496       NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
 497     } else if (isAM2 && isMatchingIncrement(PrevMBBI, Base, Bytes,
 498                                             Pred, PredReg)) {
 499       DoMerge = true;
 500       NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
 501     }
 502     if (DoMerge)
 503       MBB.erase(PrevMBBI);
 504   }
 505
 506   if (!DoMerge && MBBI != MBB.end()) {
 507     MachineBasicBlock::iterator NextMBBI = next(MBBI);
 508     if (isAM2 && isMatchingDecrement(NextMBBI, Base, Bytes, Pred, PredReg)) {
 509       DoMerge = true;
 510       AddSub = ARM_AM::sub;
 511       NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
 512     } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Pred, PredReg)) {
 513       DoMerge = true;
 514       NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
 515     }
 516     if (DoMerge) {
 517       if (NextMBBI == I) {
 518         Advance = true;
 519         ++I;
 520       }
 521       MBB.erase(NextMBBI);
 522     }
 523   }
 524
 525   if (!DoMerge)
 526     return false;
 527
 528   bool isDPR = NewOpc == ARM::FLDMD || NewOpc == ARM::FSTMD;
 529   unsigned Offset = isAM2 ? ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift)
 530     : ARM_AM::getAM5Opc((AddSub == ARM_AM::sub) ? ARM_AM::db : ARM_AM::ia,
 531                         true, isDPR ? 2 : 1);
 532   if (isLd) {
 533     if (isAM2)
 534       // LDR_PRE, LDR_POST;
 535       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
 536         .addReg(Base, RegState::Define)
 537         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
 538     else
 539       // FLDMS, FLDMD
 540       BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
 541         .addReg(Base, getKillRegState(BaseKill))
 542         .addImm(Offset).addImm(Pred).addReg(PredReg)
 543         .addReg(MI->getOperand(0).getReg(), RegState::Define);
 544   } else {
 545     MachineOperand &MO = MI->getOperand(0);
 546     if (isAM2)
 547       // STR_PRE, STR_POST;
 548       BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
 549         .addReg(MO.getReg(), getKillRegState(MO.isKill()))
 550         .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
 551     else
 552       // FSTMS, FSTMD
 553       BuildMI(MBB, MBBI, dl, TII->get(NewOpc)).addReg(Base).addImm(Offset)
 554         .addImm(Pred).addReg(PredReg)
 555         .addReg(MO.getReg(), getKillRegState(MO.isKill()));
 556   }
 557   MBB.erase(MBBI);
 558
 559   return true;
 560 }
 561
 562 /// isMemoryOp - Returns true if instruction is a memory operations (that this
 563 /// pass is capable of operating on).
 564 static bool isMemoryOp(MachineInstr *MI) {
 565   int Opcode = MI->getOpcode();
 566   switch (Opcode) {
 567   default: break;
 568   case ARM::LDR:
 569   case ARM::STR:
 570     return MI->getOperand(1).isReg() && MI->getOperand(2).getReg() == 0;
 571   case ARM::FLDS:
 572   case ARM::FSTS:
 573     return MI->getOperand(1).isReg();
 574   case ARM::FLDD:
 575   case ARM::FSTD:
 576     return MI->getOperand(1).isReg();
 577   }
 578   return false;
 579 }
 580
 581 /// AdvanceRS - Advance register scavenger to just before the earliest memory
 582 /// op that is being merged.
 583 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) {
 584   MachineBasicBlock::iterator Loc = MemOps[0].MBBI;
 585   unsigned Position = MemOps[0].Position;
 586   for (unsigned i = 1, e = MemOps.size(); i != e; ++i) {
 587     if (MemOps[i].Position < Position) {
 588       Position = MemOps[i].Position;
 589       Loc = MemOps[i].MBBI;
 590     }
 591   }
 592
 593   if (Loc != MBB.begin())
 594     RS->forward(prior(Loc));
 595 }
 596
 597 static int getMemoryOpOffset(const MachineInstr *MI) {
 598   int Opcode = MI->getOpcode();
 599   bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
 600   bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
 601   unsigned NumOperands = MI->getDesc().getNumOperands();
 602   unsigned OffField = MI->getOperand(NumOperands-3).getImm();
 603   int Offset = isAM2
 604     ? ARM_AM::getAM2Offset(OffField)
 605     : (isAM3 ? ARM_AM::getAM3Offset(OffField)
 606              : ARM_AM::getAM5Offset(OffField) * 4);
 607   if (isAM2) {
 608     if (ARM_AM::getAM2Op(OffField) == ARM_AM::sub)
 609       Offset = -Offset;
 610   } else if (isAM3) {
 611     if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub)
 612       Offset = -Offset;
 613   } else {
 614     if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub)
 615       Offset = -Offset;
 616   }
 617   return Offset;
 618 }
 619
 620 static void InsertLDR_STR(MachineBasicBlock &MBB,
 621                           MachineBasicBlock::iterator &MBBI,
 622                           int OffImm, bool isDef,
 623                           DebugLoc dl, unsigned NewOpc,
 624                           unsigned Reg, bool RegDeadKill,
 625                           unsigned BaseReg, bool BaseKill,
 626                           unsigned OffReg, bool OffKill,
 627                           ARMCC::CondCodes Pred, unsigned PredReg,
 628                           const TargetInstrInfo *TII) {
 629   unsigned Offset;
 630   if (OffImm < 0)
 631     Offset = ARM_AM::getAM2Opc(ARM_AM::sub, -OffImm, ARM_AM::no_shift);
 632   else
 633     Offset = ARM_AM::getAM2Opc(ARM_AM::add, OffImm, ARM_AM::no_shift);
 634   if (isDef)
 635     BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 636       .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
 637       .addReg(BaseReg, getKillRegState(BaseKill))
 638       .addReg(OffReg,  getKillRegState(OffKill))
 639       .addImm(Offset)
 640       .addImm(Pred).addReg(PredReg);
 641   else
 642     BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 643       .addReg(Reg, getKillRegState(RegDeadKill))
 644       .addReg(BaseReg, getKillRegState(BaseKill))
 645       .addReg(OffReg,  getKillRegState(OffKill))
 646       .addImm(Offset)
 647       .addImm(Pred).addReg(PredReg);
 648 }
 649
 650 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
 651                                           MachineBasicBlock::iterator &MBBI) {
 652   MachineInstr *MI = &*MBBI;
 653   unsigned Opcode = MI->getOpcode();
 654   if (Opcode == ARM::LDRD || Opcode == ARM::STRD) {
 655     unsigned EvenReg = MI->getOperand(0).getReg();
 656     unsigned OddReg  = MI->getOperand(1).getReg();
 657     unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
 658     unsigned OddRegNum  = TRI->getDwarfRegNum(OddReg, false);
 659     if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum)
 660       return false;
 661
 662     bool isLd = Opcode == ARM::LDRD;
 663     bool EvenDeadKill = isLd ?
 664       MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
 665     bool OddDeadKill  = isLd ?
 666       MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
 667     const MachineOperand &BaseOp = MI->getOperand(2);
 668     unsigned BaseReg = BaseOp.getReg();
 669     bool BaseKill = BaseOp.isKill();
 670     const MachineOperand &OffOp = MI->getOperand(3);
 671     unsigned OffReg = OffOp.getReg();
 672     bool OffKill = OffOp.isKill();
 673     int OffImm = getMemoryOpOffset(MI);
 674     unsigned PredReg = 0;
 675     ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
 676
 677     if (OddRegNum > EvenRegNum && OffReg == 0 && OffImm == 0) {
 678       // Ascending register numbers and no offset. It's safe to change it to a
 679       // ldm or stm.
 680       unsigned NewOpc = (Opcode == ARM::LDRD) ? ARM::LDM : ARM::STM;
 681       if (isLd) {
 682         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 683           .addReg(BaseReg, getKillRegState(BaseKill))
 684           .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia))
 685           .addImm(Pred).addReg(PredReg)
 686           .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
 687           .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill));
 688         ++NumLDRD2LDM;
 689       } else {
 690         BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
 691           .addReg(BaseReg, getKillRegState(BaseKill))
 692           .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia))
 693           .addImm(Pred).addReg(PredReg)
 694           .addReg(EvenReg, getKillRegState(EvenDeadKill))
 695           .addReg(OddReg, getKillRegState(OddDeadKill));
 696         ++NumSTRD2STM;
 697       }
 698     } else {
 699       // Split into two instructions.
 700       unsigned NewOpc = (Opcode == ARM::LDRD) ? ARM::LDR : ARM::STR;
 701       DebugLoc dl = MBBI->getDebugLoc();
 702       // If this is a load and base register is killed, it may have been
 703       // re-defed by the load, make sure the first load does not clobber it.
 704       if (isLd &&
 705           (BaseKill || OffKill) &&
 706           (TRI->regsOverlap(EvenReg, BaseReg) ||
 707            (OffReg && TRI->regsOverlap(EvenReg, OffReg)))) {
 708         assert(!TRI->regsOverlap(OddReg, BaseReg) &&
 709                (!OffReg || !TRI->regsOverlap(OddReg, OffReg)));
 710         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc, OddReg, OddDeadKill,
 711                       BaseReg, false, OffReg, false, Pred, PredReg, TII);
 712         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc, EvenReg, EvenDeadKill,
 713                       BaseReg, BaseKill, OffReg, OffKill, Pred, PredReg, TII);
 714       } else {
 715         InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
 716                       EvenReg, EvenDeadKill, BaseReg, false, OffReg, false,
 717                       Pred, PredReg, TII);
 718         InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
 719                       OddReg, OddDeadKill, BaseReg, BaseKill, OffReg, OffKill,
 720                       Pred, PredReg, TII);
 721       }
 722       if (isLd)
 723         ++NumLDRD2LDR;
 724       else
 725         ++NumSTRD2STR;
 726     }
 727
 728     MBBI = prior(MBBI);
 729     MBB.erase(MI);
 730   }
 731   return false;
 732 }
 733
 734 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
 735 /// ops of the same base and incrementing offset into LDM / STM ops.
 736 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
 737   unsigned NumMerges = 0;
 738   unsigned NumMemOps = 0;
 739   MemOpQueue MemOps;
 740   unsigned CurrBase = 0;
 741   int CurrOpc = -1;
 742   unsigned CurrSize = 0;
 743   ARMCC::CondCodes CurrPred = ARMCC::AL;
 744   unsigned CurrPredReg = 0;
 745   unsigned Position = 0;
 746   SmallVector<MachineBasicBlock::iterator,4> Merges;
 747
 748   RS->enterBasicBlock(&MBB);
 749   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 750   while (MBBI != E) {
 751     if (FixInvalidRegPairOp(MBB, MBBI))
 752       continue;
 753
 754     bool Advance  = false;
 755     bool TryMerge = false;
 756     bool Clobber  = false;
 757
 758     bool isMemOp = isMemoryOp(MBBI);
 759     if (isMemOp) {
 760       int Opcode = MBBI->getOpcode();
 761       unsigned Size = getLSMultipleTransferSize(MBBI);
 762       unsigned Base = MBBI->getOperand(1).getReg();
 763       unsigned PredReg = 0;
 764       ARMCC::CondCodes Pred = getInstrPredicate(MBBI, PredReg);
 765       int Offset = getMemoryOpOffset(MBBI);
 766       // Watch out for:
 767       // r4 := ldr [r5]
 768       // r5 := ldr [r5, #4]
 769       // r6 := ldr [r5, #8]
 770       //
 771       // The second ldr has effectively broken the chain even though it
 772       // looks like the later ldr(s) use the same base register. Try to
 773       // merge the ldr's so far, including this one. But don't try to
 774       // combine the following ldr(s).
 775       Clobber = (Opcode == ARM::LDR && Base == MBBI->getOperand(0).getReg());
 776       if (CurrBase == 0 && !Clobber) {
 777         // Start of a new chain.
 778         CurrBase = Base;
 779         CurrOpc  = Opcode;
 780         CurrSize = Size;
 781         CurrPred = Pred;
 782         CurrPredReg = PredReg;
 783         MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI));
 784         NumMemOps++;
 785         Advance = true;
 786       } else {
 787         if (Clobber) {
 788           TryMerge = true;
 789           Advance = true;
 790         }
 791
 792         if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
 793           // No need to match PredReg.
 794           // Continue adding to the queue.
 795           if (Offset > MemOps.back().Offset) {
 796             MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI));
 797             NumMemOps++;
 798             Advance = true;
 799           } else {
 800             for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
 801                  I != E; ++I) {
 802               if (Offset < I->Offset) {
 803                 MemOps.insert(I, MemOpQueueEntry(Offset, Position, MBBI));
 804                 NumMemOps++;
 805                 Advance = true;
 806                 break;
 807               } else if (Offset == I->Offset) {
 808                 // Collision! This can't be merged!
 809                 break;
 810               }
 811             }
 812           }
 813         }
 814       }
 815     }
 816
 817     if (Advance) {
 818       ++Position;
 819       ++MBBI;
 820     } else
 821       TryMerge = true;
 822
 823     if (TryMerge) {
 824       if (NumMemOps > 1) {
 825         // Try to find a free register to use as a new base in case it's needed.
 826         // First advance to the instruction just before the start of the chain.
 827         AdvanceRS(MBB, MemOps);
 828         // Find a scratch register. Make sure it's a call clobbered register or
 829         // a spilled callee-saved register.
 830         unsigned Scratch = RS->FindUnusedReg(&ARM::GPRRegClass, true);
 831         if (!Scratch)
 832           Scratch = RS->FindUnusedReg(&ARM::GPRRegClass,
 833                                       AFI->getSpilledCSRegisters());
 834         // Process the load / store instructions.
 835         RS->forward(prior(MBBI));
 836
 837         // Merge ops.
 838         Merges.clear();
 839         MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize,
 840                      CurrPred, CurrPredReg, Scratch, MemOps, Merges);
 841
 842         // Try folding preceeding/trailing base inc/dec into the generated
 843         // LDM/STM ops.
 844         for (unsigned i = 0, e = Merges.size(); i < e; ++i)
 845           if (mergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI))
 846             ++NumMerges;
 847         NumMerges += Merges.size();
 848
 849         // Try folding preceeding/trailing base inc/dec into those load/store
 850         // that were not merged to form LDM/STM ops.
 851         for (unsigned i = 0; i != NumMemOps; ++i)
 852           if (!MemOps[i].Merged)
 853             if (mergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI))
 854               ++NumMerges;
 855
 856         // RS may be pointing to an instruction that's deleted.
 857         RS->skipTo(prior(MBBI));
 858       } else if (NumMemOps == 1) {
 859         // Try folding preceeding/trailing base inc/dec into the single
 860         // load/store.
 861         if (mergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) {
 862           ++NumMerges;
 863           RS->forward(prior(MBBI));
 864         }
 865       }
 866
 867       CurrBase = 0;
 868       CurrOpc = -1;
 869       CurrSize = 0;
 870       CurrPred = ARMCC::AL;
 871       CurrPredReg = 0;
 872       if (NumMemOps) {
 873         MemOps.clear();
 874         NumMemOps = 0;
 875       }
 876
 877       // If iterator hasn't been advanced and this is not a memory op, skip it.
 878       // It can't start a new chain anyway.
 879       if (!Advance && !isMemOp && MBBI != E) {
 880         ++Position;
 881         ++MBBI;
 882       }
 883     }
 884   }
 885   return NumMerges > 0;
 886 }
 887
 888 namespace {
 889   struct OffsetCompare {
 890     bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
 891       int LOffset = getMemoryOpOffset(LHS);
 892       int ROffset = getMemoryOpOffset(RHS);
 893       assert(LHS == RHS || LOffset != ROffset);
 894       return LOffset > ROffset;
 895     }
 896   };
 897 }
 898
 899 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return op
 900 /// (bx lr) into the preceeding stack restore so it directly restore the value
 901 /// of LR into pc.
 902 ///   ldmfd sp!, {r7, lr}
 903 ///   bx lr
 904 /// =>
 905 ///   ldmfd sp!, {r7, pc}
 906 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
 907   if (MBB.empty()) return false;
 908
 909   MachineBasicBlock::iterator MBBI = prior(MBB.end());
 910   if (MBBI->getOpcode() == ARM::BX_RET && MBBI != MBB.begin()) {
 911     MachineInstr *PrevMI = prior(MBBI);
 912     if (PrevMI->getOpcode() == ARM::LDM) {
 913       MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
 914       if (MO.getReg() == ARM::LR) {
 915         PrevMI->setDesc(TII->get(ARM::LDM_RET));
 916         MO.setReg(ARM::PC);
 917         MBB.erase(MBBI);
 918         return true;
 919       }
 920     }
 921   }
 922   return false;
 923 }
 924
 925 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
 926   const TargetMachine &TM = Fn.getTarget();
 927   AFI = Fn.getInfo<ARMFunctionInfo>();
 928   TII = TM.getInstrInfo();
 929   TRI = TM.getRegisterInfo();
 930   RS = new RegScavenger();
 931
 932   bool Modified = false;
 933   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
 934        ++MFI) {
 935     MachineBasicBlock &MBB = *MFI;
 936     Modified |= LoadStoreMultipleOpti(MBB);
 937     Modified |= MergeReturnIntoLDM(MBB);
 938   }
 939
 940   delete RS;
 941   return Modified;
 942 }
 943
 944
 945 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move
 946 /// load / stores from consecutive locations close to make it more
 947 /// likely they will be combined later.
 948
 949 namespace {
 950   struct VISIBILITY_HIDDEN ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
 951     static char ID;
 952     ARMPreAllocLoadStoreOpt() : MachineFunctionPass(&ID) {}
 953
 954     const TargetData *TD;
 955     const TargetInstrInfo *TII;
 956     const TargetRegisterInfo *TRI;
 957     const ARMSubtarget *STI;
 958     MachineRegisterInfo *MRI;
 959
 960     virtual bool runOnMachineFunction(MachineFunction &Fn);
 961
 962     virtual const char *getPassName() const {
 963       return "ARM pre- register allocation load / store optimization pass";
 964     }
 965
 966   private:
 967     bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
 968                           unsigned &NewOpc, unsigned &EvenReg,
 969                           unsigned &OddReg, unsigned &BaseReg,
 970                           unsigned &OffReg, unsigned &Offset,
 971                           unsigned &PredReg, ARMCC::CondCodes &Pred);
 972     bool RescheduleOps(MachineBasicBlock *MBB,
 973                        SmallVector<MachineInstr*, 4> &Ops,
 974                        unsigned Base, bool isLd,
 975                        DenseMap<MachineInstr*, unsigned> &MI2LocMap);
 976     bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
 977   };
 978   char ARMPreAllocLoadStoreOpt::ID = 0;
 979 }
 980
 981 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
 982   TD  = Fn.getTarget().getTargetData();
 983   TII = Fn.getTarget().getInstrInfo();
 984   TRI = Fn.getTarget().getRegisterInfo();
 985   STI = &Fn.getTarget().getSubtarget<ARMSubtarget>();
 986   MRI = &Fn.getRegInfo();
 987
 988   bool Modified = false;
 989   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
 990        ++MFI)
 991     Modified |= RescheduleLoadStoreInstrs(MFI);
 992
 993   return Modified;
 994 }
 995
 996 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
 997                                       MachineBasicBlock::iterator I,
 998                                       MachineBasicBlock::iterator E,
 999                                       SmallPtrSet<MachineInstr*, 4> &MemOps,
1000                                       SmallSet<unsigned, 4> &MemRegs,
1001                                       const TargetRegisterInfo *TRI) {
1002   // Are there stores / loads / calls between them?
1003   // FIXME: This is overly conservative. We should make use of alias information
1004   // some day.
1005   SmallSet<unsigned, 4> AddedRegPressure;
1006   while (++I != E) {
1007     if (MemOps.count(&*I))
1008       continue;
1009     const TargetInstrDesc &TID = I->getDesc();
1010     if (TID.isCall() || TID.isTerminator() || TID.hasUnmodeledSideEffects())
1011       return false;
1012     if (isLd && TID.mayStore())
1013       return false;
1014     if (!isLd) {
1015       if (TID.mayLoad())
1016         return false;
1017       // It's not safe to move the first 'str' down.
1018       // str r1, [r0]
1019       // strh r5, [r0]
1020       // str r4, [r0, #+4]
1021       if (TID.mayStore())
1022         return false;
1023     }
1024     for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
1025       MachineOperand &MO = I->getOperand(j);
1026       if (!MO.isReg())
1027         continue;
1028       unsigned Reg = MO.getReg();
1029       if (MO.isDef() && TRI->regsOverlap(Reg, Base))
1030         return false;
1031       if (Reg != Base && !MemRegs.count(Reg))
1032         AddedRegPressure.insert(Reg);
1033     }
1034   }
1035
1036   // Estimate register pressure increase due to the transformation.
1037   if (MemRegs.size() <= 4)
1038     // Ok if we are moving small number of instructions.
1039     return true;
1040   return AddedRegPressure.size() <= MemRegs.size() * 2;
1041 }
1042
1043 bool
1044 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
1045                                           DebugLoc &dl,
1046                                           unsigned &NewOpc, unsigned &EvenReg,
1047                                           unsigned &OddReg, unsigned &BaseReg,
1048                                           unsigned &OffReg, unsigned &Offset,
1049                                           unsigned &PredReg,
1050                                           ARMCC::CondCodes &Pred) {
1051   // FIXME: FLDS / FSTS -> FLDD / FSTD
1052   unsigned Opcode = Op0->getOpcode();
1053   if (Opcode == ARM::LDR)
1054     NewOpc = ARM::LDRD;
1055   else if (Opcode == ARM::STR)
1056     NewOpc = ARM::STRD;
1057   else
1058     return 0;
1059
1060   // Must sure the base address satisfies i64 ld / st alignment requirement.
1061   if (!Op0->hasOneMemOperand() ||
1062       !Op0->memoperands_begin()->getValue() ||
1063       Op0->memoperands_begin()->isVolatile())
1064     return false;
1065
1066   unsigned Align = Op0->memoperands_begin()->getAlignment();
1067   unsigned ReqAlign = STI->hasV6Ops()
1068     ? TD->getPrefTypeAlignment(Type::Int64Ty) : 8; // Pre-v6 need 8-byte align
1069   if (Align < ReqAlign)
1070     return false;
1071
1072   // Then make sure the immediate offset fits.
1073   int OffImm = getMemoryOpOffset(Op0);
1074   ARM_AM::AddrOpc AddSub = ARM_AM::add;
1075   if (OffImm < 0) {
1076     AddSub = ARM_AM::sub;
1077     OffImm = - OffImm;
1078   }
1079   if (OffImm >= 256) // 8 bits
1080     return false;
1081   Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
1082
1083   EvenReg = Op0->getOperand(0).getReg();
1084   OddReg  = Op1->getOperand(0).getReg();
1085   if (EvenReg == OddReg)
1086     return false;
1087   BaseReg = Op0->getOperand(1).getReg();
1088   OffReg = Op0->getOperand(2).getReg();
1089   Pred = getInstrPredicate(Op0, PredReg);
1090   dl = Op0->getDebugLoc();
1091   return true;
1092 }
1093
1094 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
1095                                  SmallVector<MachineInstr*, 4> &Ops,
1096                                  unsigned Base, bool isLd,
1097                                  DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
1098   bool RetVal = false;
1099
1100   // Sort by offset (in reverse order).
1101   std::sort(Ops.begin(), Ops.end(), OffsetCompare());
1102
1103   // The loads / stores of the same base are in order. Scan them from first to
1104   // last and check for the followins:
1105   // 1. Any def of base.
1106   // 2. Any gaps.
1107   while (Ops.size() > 1) {
1108     unsigned FirstLoc = ~0U;
1109     unsigned LastLoc = 0;
1110     MachineInstr *FirstOp = 0;
1111     MachineInstr *LastOp = 0;
1112     int LastOffset = 0;
1113     unsigned LastOpcode = 0;
1114     unsigned LastBytes = 0;
1115     unsigned NumMove = 0;
1116     for (int i = Ops.size() - 1; i >= 0; --i) {
1117       MachineInstr *Op = Ops[i];
1118       unsigned Loc = MI2LocMap[Op];
1119       if (Loc <= FirstLoc) {
1120         FirstLoc = Loc;
1121         FirstOp = Op;
1122       }
1123       if (Loc >= LastLoc) {
1124         LastLoc = Loc;
1125         LastOp = Op;
1126       }
1127
1128       unsigned Opcode = Op->getOpcode();
1129       if (LastOpcode && Opcode != LastOpcode)
1130         break;
1131
1132       int Offset = getMemoryOpOffset(Op);
1133       unsigned Bytes = getLSMultipleTransferSize(Op);
1134       if (LastBytes) {
1135         if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
1136           break;
1137       }
1138       LastOffset = Offset;
1139       LastBytes = Bytes;
1140       LastOpcode = Opcode;
1141       if (++NumMove == 8) // FIXME: Tune
1142         break;
1143     }
1144
1145     if (NumMove <= 1)
1146       Ops.pop_back();
1147     else {
1148       SmallPtrSet<MachineInstr*, 4> MemOps;
1149       SmallSet<unsigned, 4> MemRegs;
1150       for (int i = NumMove-1; i >= 0; --i) {
1151         MemOps.insert(Ops[i]);
1152         MemRegs.insert(Ops[i]->getOperand(0).getReg());
1153       }
1154
1155       // Be conservative, if the instructions are too far apart, don't
1156       // move them. We want to limit the increase of register pressure.
1157       bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
1158       if (DoMove)
1159         DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
1160                                            MemOps, MemRegs, TRI);
1161       if (!DoMove) {
1162         for (unsigned i = 0; i != NumMove; ++i)
1163           Ops.pop_back();
1164       } else {
1165         // This is the new location for the loads / stores.
1166         MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
1167         while (InsertPos != MBB->end() && MemOps.count(InsertPos))
1168           ++InsertPos;
1169
1170         // If we are moving a pair of loads / stores, see if it makes sense
1171         // to try to allocate a pair of registers that can form register pairs.
1172         MachineInstr *Op0 = Ops.back();
1173         MachineInstr *Op1 = Ops[Ops.size()-2];
1174         unsigned EvenReg = 0, OddReg = 0;
1175         unsigned BaseReg = 0, OffReg = 0, PredReg = 0;
1176         ARMCC::CondCodes Pred = ARMCC::AL;
1177         unsigned NewOpc = 0;
1178         unsigned Offset = 0;
1179         DebugLoc dl;
1180         if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
1181                                              EvenReg, OddReg, BaseReg, OffReg,
1182                                              Offset, PredReg, Pred)) {
1183           Ops.pop_back();
1184           Ops.pop_back();
1185
1186           // Form the pair instruction.
1187           if (isLd) {
1188             BuildMI(*MBB, InsertPos, dl, TII->get(NewOpc))
1189               .addReg(EvenReg, RegState::Define)
1190               .addReg(OddReg, RegState::Define)
1191               .addReg(BaseReg).addReg(0).addImm(Offset)
1192               .addImm(Pred).addReg(PredReg);
1193             ++NumLDRDFormed;
1194           } else {
1195             BuildMI(*MBB, InsertPos, dl, TII->get(NewOpc))
1196               .addReg(EvenReg)
1197               .addReg(OddReg)
1198               .addReg(BaseReg).addReg(0).addImm(Offset)
1199               .addImm(Pred).addReg(PredReg);
1200             ++NumSTRDFormed;
1201           }
1202           MBB->erase(Op0);
1203           MBB->erase(Op1);
1204
1205           // Add register allocation hints to form register pairs.
1206           MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg);
1207           MRI->setRegAllocationHint(OddReg,  ARMRI::RegPairOdd, EvenReg);
1208         } else {
1209           for (unsigned i = 0; i != NumMove; ++i) {
1210             MachineInstr *Op = Ops.back();
1211             Ops.pop_back();
1212             MBB->splice(InsertPos, MBB, Op);
1213           }
1214         }
1215
1216         NumLdStMoved += NumMove;
1217         RetVal = true;
1218       }
1219     }
1220   }
1221
1222   return RetVal;
1223 }
1224
1225 bool
1226 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
1227   bool RetVal = false;
1228
1229   DenseMap<MachineInstr*, unsigned> MI2LocMap;
1230   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
1231   DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
1232   SmallVector<unsigned, 4> LdBases;
1233   SmallVector<unsigned, 4> StBases;
1234
1235   unsigned Loc = 0;
1236   MachineBasicBlock::iterator MBBI = MBB->begin();
1237   MachineBasicBlock::iterator E = MBB->end();
1238   while (MBBI != E) {
1239     for (; MBBI != E; ++MBBI) {
1240       MachineInstr *MI = MBBI;
1241       const TargetInstrDesc &TID = MI->getDesc();
1242       if (TID.isCall() || TID.isTerminator()) {
1243         // Stop at barriers.
1244         ++MBBI;
1245         break;
1246       }
1247
1248       MI2LocMap[MI] = Loc++;
1249       if (!isMemoryOp(MI))
1250         continue;
1251       unsigned PredReg = 0;
1252       if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
1253         continue;
1254
1255       int Opcode = MI->getOpcode();
1256       bool isLd = Opcode == ARM::LDR ||
1257         Opcode == ARM::FLDS || Opcode == ARM::FLDD;
1258       unsigned Base = MI->getOperand(1).getReg();
1259       int Offset = getMemoryOpOffset(MI);
1260
1261       bool StopHere = false;
1262       if (isLd) {
1263         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1264           Base2LdsMap.find(Base);
1265         if (BI != Base2LdsMap.end()) {
1266           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1267             if (Offset == getMemoryOpOffset(BI->second[i])) {
1268               StopHere = true;
1269               break;
1270             }
1271           }
1272           if (!StopHere)
1273             BI->second.push_back(MI);
1274         } else {
1275           SmallVector<MachineInstr*, 4> MIs;
1276           MIs.push_back(MI);
1277           Base2LdsMap[Base] = MIs;
1278           LdBases.push_back(Base);
1279         }
1280       } else {
1281         DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1282           Base2StsMap.find(Base);
1283         if (BI != Base2StsMap.end()) {
1284           for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1285             if (Offset == getMemoryOpOffset(BI->second[i])) {
1286               StopHere = true;
1287               break;
1288             }
1289           }
1290           if (!StopHere)
1291             BI->second.push_back(MI);
1292         } else {
1293           SmallVector<MachineInstr*, 4> MIs;
1294           MIs.push_back(MI);
1295           Base2StsMap[Base] = MIs;
1296           StBases.push_back(Base);
1297         }
1298       }
1299
1300       if (StopHere) {
1301         // Found a duplicate (a base+offset combination that's seen earlier).
1302         // Backtrack.
1303         --Loc;
1304         break;
1305       }
1306     }
1307
1308     // Re-schedule loads.
1309     for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
1310       unsigned Base = LdBases[i];
1311       SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base];
1312       if (Lds.size() > 1)
1313         RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
1314     }
1315
1316     // Re-schedule stores.
1317     for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
1318       unsigned Base = StBases[i];
1319       SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base];
1320       if (Sts.size() > 1)
1321         RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
1322     }
1323
1324     if (MBBI != E) {
1325       Base2LdsMap.clear();
1326       Base2StsMap.clear();
1327       LdBases.clear();
1328       StBases.clear();
1329     }
1330   }
1331
1332   return RetVal;
1333 }
1334
1335
1336 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
1337 /// optimization pass.
1338 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
1339   if (PreAlloc)
1340     return new ARMPreAllocLoadStoreOpt();
1341   return new ARMLoadStoreOpt();
1342 }