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