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