lib/Target/ARM/ARMLoadStoreOptimizer.cpp

   1 //===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng and is distributed under the
   6 // University of Illinois Open Source 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 "ARMRegisterInfo.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/CodeGen/MachineBasicBlock.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/MachineInstr.h"
  25 #include "llvm/CodeGen/MachineInstrBuilder.h"
  26 #include "llvm/CodeGen/RegisterScavenging.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Target/MRegisterInfo.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 #include "llvm/Target/TargetMachine.h"
  31 using namespace llvm;
  32
  33 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
  34 STATISTIC(NumSTMGened , "Number of stm instructions generated");
  35 STATISTIC(NumFLDMGened, "Number of fldm instructions generated");
  36 STATISTIC(NumFSTMGened, "Number of fstm instructions generated");
  37
  38 namespace {
  39   struct VISIBILITY_HIDDEN ARMLoadStoreOpt : public MachineFunctionPass {
  40     const TargetInstrInfo *TII;
  41     const MRegisterInfo *MRI;
  42     RegScavenger *RS;
  43
  44     virtual bool runOnMachineFunction(MachineFunction &Fn);
  45
  46     virtual const char *getPassName() const {
  47       return "ARM load / store optimization pass";
  48     }
  49
  50   private:
  51     struct MemOpQueueEntry {
  52       int Offset;
  53       unsigned Position;
  54       MachineBasicBlock::iterator MBBI;
  55       bool Merged;
  56       MemOpQueueEntry(int o, int p, MachineBasicBlock::iterator i)
  57         : Offset(o), Position(p), MBBI(i), Merged(false) {};
  58     };
  59     typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
  60     typedef MemOpQueue::iterator MemOpQueueIter;
  61
  62     SmallVector<MachineBasicBlock::iterator, 4>
  63     MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
  64                  int Opcode, unsigned Size, MemOpQueue &MemOps);
  65
  66     bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
  67     bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
  68   };
  69 }
  70
  71 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
  72 /// optimization pass.
  73 FunctionPass *llvm::createARMLoadStoreOptimizationPass() {
  74   return new ARMLoadStoreOpt();
  75 }
  76
  77 static int getLoadStoreMultipleOpcode(int Opcode) {
  78   switch (Opcode) {
  79   case ARM::LDR:
  80     NumLDMGened++;
  81     return ARM::LDM;
  82   case ARM::STR:
  83     NumSTMGened++;
  84     return ARM::STM;
  85   case ARM::FLDS:
  86     NumFLDMGened++;
  87     return ARM::FLDMS;
  88   case ARM::FSTS:
  89     NumFSTMGened++;
  90     return ARM::FSTMS;
  91   case ARM::FLDD:
  92     NumFLDMGened++;
  93     return ARM::FLDMD;
  94   case ARM::FSTD:
  95     NumFSTMGened++;
  96     return ARM::FSTMD;
  97   default: abort();
  98   }
  99   return 0;
 100 }
 101
 102 /// mergeOps - Create and insert a LDM or STM with Base as base register and
 103 /// registers in Regs as the register operands that would be loaded / stored.
 104 /// It returns true if the transformation is done.
 105 static bool mergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
 106                      int Offset, unsigned Base, int Opcode,
 107                      SmallVector<unsigned, 8> &Regs,
 108                      const TargetInstrInfo *TII) {
 109   // Only a single register to load / store. Don't bother.
 110   unsigned NumRegs = Regs.size();
 111   if (NumRegs <= 1)
 112     return false;
 113
 114   ARM_AM::AMSubMode Mode = ARM_AM::ia;
 115   bool isAM4 = Opcode == ARM::LDR || Opcode == ARM::STR;
 116   if (isAM4 && Offset == 4)
 117     Mode = ARM_AM::ib;
 118   else if (isAM4 && Offset == -4 * (int)NumRegs + 4)
 119     Mode = ARM_AM::da;
 120   else if (isAM4 && Offset == -4 * (int)NumRegs)
 121     Mode = ARM_AM::db;
 122   else if (Offset != 0) {
 123     // If starting offset isn't zero, insert a MI to materialize a new base.
 124     // But only do so if it is cost effective, i.e. merging more than two
 125     // loads / stores.
 126     if (NumRegs <= 2)
 127       return false;
 128
 129     unsigned NewBase;
 130     if (Opcode == ARM::LDR)
 131       // If it is a load, then just use one of the destination register to
 132       // use as the new base.
 133       NewBase = Regs[NumRegs-1];
 134     else {
 135       // FIXME: Try scavenging a register to use as a new base.
 136       NewBase = ARM::R12;
 137     }
 138     int BaseOpc = ARM::ADDri;
 139     if (Offset < 0) {
 140       BaseOpc = ARM::SUBri;
 141       Offset = - Offset;
 142     }
 143     int ImmedOffset = ARM_AM::getSOImmVal(Offset);
 144     if (ImmedOffset == -1)
 145       return false;  // Probably not worth it then.
 146     BuildMI(MBB, MBBI, TII->get(BaseOpc), NewBase).addReg(Base).addImm(ImmedOffset);
 147     Base = NewBase;
 148   }
 149
 150   bool isDPR = Opcode == ARM::FLDD || Opcode == ARM::FSTD;
 151   bool isDef = Opcode == ARM::LDR || Opcode == ARM::FLDS || Opcode == ARM::FLDD;
 152   Opcode = getLoadStoreMultipleOpcode(Opcode);
 153   MachineInstrBuilder MIB = (isAM4)
 154     ? BuildMI(MBB, MBBI, TII->get(Opcode)).addReg(Base)
 155         .addImm(ARM_AM::getAM4ModeImm(Mode))
 156     : BuildMI(MBB, MBBI, TII->get(Opcode)).addReg(Base)
 157         .addImm(ARM_AM::getAM5Opc(Mode, false, isDPR ? NumRegs<<1 : NumRegs));
 158   for (unsigned i = 0; i != NumRegs; ++i)
 159     MIB = MIB.addReg(Regs[i], Opcode == isDef);
 160
 161   return true;
 162 }
 163
 164 SmallVector<MachineBasicBlock::iterator, 4>
 165 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB,
 166                               unsigned SIndex, unsigned Base, int Opcode,
 167                               unsigned Size, MemOpQueue &MemOps) {
 168   bool isAM4 = Opcode == ARM::LDR || Opcode == ARM::STR;
 169   SmallVector<MachineBasicBlock::iterator, 4> Merges;
 170   int Offset = MemOps[SIndex].Offset;
 171   int SOffset = Offset;
 172   unsigned Pos = MemOps[SIndex].Position;
 173   MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
 174   SmallVector<unsigned, 8> Regs;
 175   unsigned PReg = MemOps[SIndex].MBBI->getOperand(0).getReg();
 176   unsigned PRegNum = ARMRegisterInfo::getRegisterNumbering(PReg);
 177   Regs.push_back(PReg);
 178   for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
 179     int NewOffset = MemOps[i].Offset;
 180     unsigned Reg = MemOps[i].MBBI->getOperand(0).getReg();
 181     unsigned RegNum = ARMRegisterInfo::getRegisterNumbering(Reg);
 182     // AM4 - register numbers in ascending order.
 183     // AM5 - consecutive register numbers in ascending order.
 184     if (NewOffset == Offset + (int)Size &&
 185         ((isAM4 && RegNum > PRegNum) || RegNum == PRegNum+1)) {
 186       Offset += Size;
 187       Regs.push_back(Reg);
 188       PRegNum = RegNum;
 189     } else {
 190       // Can't merge this in. Try merge the earlier ones first.
 191       if (mergeOps(MBB, ++Loc, SOffset, Base, Opcode, Regs, TII)) {
 192         Merges.push_back(prior(Loc));
 193         for (unsigned j = SIndex; j < i; ++j) {
 194           MBB.erase(MemOps[j].MBBI);
 195           MemOps[j].Merged = true;
 196         }
 197       }
 198       SmallVector<MachineBasicBlock::iterator, 4> Merges2 =
 199         MergeLDR_STR(MBB, i, Base, Opcode, Size, MemOps);
 200       Merges.append(Merges2.begin(), Merges2.end());
 201       return Merges;
 202     }
 203
 204     if (MemOps[i].Position > Pos) {
 205       Pos = MemOps[i].Position;
 206       Loc = MemOps[i].MBBI;
 207     }
 208   }
 209
 210   if (mergeOps(MBB, ++Loc, SOffset, Base, Opcode, Regs, TII)) {
 211     Merges.push_back(prior(Loc));
 212     for (unsigned i = SIndex, e = MemOps.size(); i != e; ++i) {
 213       MBB.erase(MemOps[i].MBBI);
 214       MemOps[i].Merged = true;
 215     }
 216   }
 217
 218   return Merges;
 219 }
 220
 221 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
 222                                        unsigned Bytes) {
 223   return (MI && MI->getOpcode() == ARM::SUBri &&
 224           MI->getOperand(0).getReg() == Base &&
 225           MI->getOperand(1).getReg() == Base &&
 226           ARM_AM::getAM2Offset(MI->getOperand(2).getImm()) == Bytes);
 227 }
 228
 229 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
 230                                        unsigned Bytes) {
 231   return (MI && MI->getOpcode() == ARM::ADDri &&
 232           MI->getOperand(0).getReg() == Base &&
 233           MI->getOperand(1).getReg() == Base &&
 234           ARM_AM::getAM2Offset(MI->getOperand(2).getImm()) == Bytes);
 235 }
 236
 237 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
 238   switch (MI->getOpcode()) {
 239   default: return 0;
 240   case ARM::LDR:
 241   case ARM::STR:
 242   case ARM::FLDS:
 243   case ARM::FSTS:
 244     return 4;
 245   case ARM::FLDD:
 246   case ARM::FSTD:
 247     return 8;
 248   case ARM::LDM:
 249   case ARM::STM:
 250     return (MI->getNumOperands() - 2) * 4;
 251   case ARM::FLDMS:
 252   case ARM::FSTMS:
 253   case ARM::FLDMD:
 254   case ARM::FSTMD:
 255     return ARM_AM::getAM5Offset(MI->getOperand(1).getImm()) * 4;
 256   }
 257 }
 258
 259 /// mergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
 260 /// register into the LDM/STM/FLDM{D|S}/FSTM{D|S} op when possible:
 261 ///
 262 /// stmia rn, <ra, rb, rc>
 263 /// rn := rn + 4 * 3;
 264 /// =>
 265 /// stmia rn!, <ra, rb, rc>
 266 ///
 267 /// rn := rn - 4 * 3;
 268 /// ldmia rn, <ra, rb, rc>
 269 /// =>
 270 /// ldmdb rn!, <ra, rb, rc>
 271 static bool mergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
 272                                       MachineBasicBlock::iterator MBBI) {
 273   MachineInstr *MI = MBBI;
 274   unsigned Base = MI->getOperand(0).getReg();
 275   unsigned Bytes = getLSMultipleTransferSize(MI);
 276   int Opcode = MI->getOpcode();
 277   bool isAM4 = Opcode == ARM::LDM || Opcode == ARM::STM;
 278
 279   if (isAM4) {
 280     if (ARM_AM::getAM4WBFlag(MI->getOperand(1).getImm()))
 281       return false;
 282
 283     // Can't use the updating AM4 sub-mode if the base register is also a dest
 284     // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
 285     for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i) {
 286       if (MI->getOperand(i).getReg() == Base)
 287         return false;
 288     }
 289
 290     ARM_AM::AMSubMode Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm());
 291     if (MBBI != MBB.begin()) {
 292       MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 293       if (Mode == ARM_AM::ia &&
 294           isMatchingDecrement(PrevMBBI, Base, Bytes)) {
 295         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::db, true));
 296         MBB.erase(PrevMBBI);
 297         return true;
 298       } else if (Mode == ARM_AM::ib &&
 299                  isMatchingDecrement(PrevMBBI, Base, Bytes)) {
 300         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::da, true));
 301         MBB.erase(PrevMBBI);
 302         return true;
 303       }
 304     }
 305
 306     if (MBBI != MBB.end()) {
 307       MachineBasicBlock::iterator NextMBBI = next(MBBI);
 308       if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
 309           isMatchingIncrement(NextMBBI, Base, Bytes)) {
 310         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
 311         MBB.erase(NextMBBI);
 312         return true;
 313       } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
 314                  isMatchingDecrement(NextMBBI, Base, Bytes)) {
 315         MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
 316         MBB.erase(NextMBBI);
 317         return true;
 318       }
 319     }
 320   } else {
 321     // FLDM{D|S}, FSTM{D|S} addressing mode 5 ops.
 322     if (ARM_AM::getAM5WBFlag(MI->getOperand(1).getImm()))
 323       return false;
 324
 325     ARM_AM::AMSubMode Mode = ARM_AM::getAM5SubMode(MI->getOperand(1).getImm());
 326     unsigned Offset = ARM_AM::getAM5Offset(MI->getOperand(1).getImm());
 327     if (MBBI != MBB.begin()) {
 328       MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 329       if (Mode == ARM_AM::ia &&
 330           isMatchingDecrement(PrevMBBI, Base, Bytes)) {
 331         MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::db, true, Offset));
 332         MBB.erase(PrevMBBI);
 333         return true;
 334       }
 335     }
 336
 337     if (MBBI != MBB.end()) {
 338       MachineBasicBlock::iterator NextMBBI = next(MBBI);
 339       if (Mode == ARM_AM::ia &&
 340           isMatchingIncrement(NextMBBI, Base, Bytes)) {
 341         MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::ia, true, Offset));
 342         MBB.erase(NextMBBI);
 343       }
 344       return true;
 345     }
 346   }
 347
 348   return false;
 349 }
 350
 351 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) {
 352   switch (Opc) {
 353   case ARM::LDR: return ARM::LDR_PRE;
 354   case ARM::STR: return ARM::STR_PRE;
 355   case ARM::FLDS: return ARM::FLDMS;
 356   case ARM::FLDD: return ARM::FLDMD;
 357   case ARM::FSTS: return ARM::FSTMS;
 358   case ARM::FSTD: return ARM::FSTMD;
 359   default: abort();
 360   }
 361   return 0;
 362 }
 363
 364 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) {
 365   switch (Opc) {
 366   case ARM::LDR: return ARM::LDR_POST;
 367   case ARM::STR: return ARM::STR_POST;
 368   case ARM::FLDS: return ARM::FLDMS;
 369   case ARM::FLDD: return ARM::FLDMD;
 370   case ARM::FSTS: return ARM::FSTMS;
 371   case ARM::FSTD: return ARM::FSTMD;
 372   default: abort();
 373   }
 374   return 0;
 375 }
 376
 377 /// mergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
 378 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
 379 static bool mergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
 380                                      MachineBasicBlock::iterator MBBI,
 381                                      const TargetInstrInfo *TII) {
 382   MachineInstr *MI = MBBI;
 383   unsigned Base = MI->getOperand(1).getReg();
 384   unsigned Bytes = getLSMultipleTransferSize(MI);
 385   int Opcode = MI->getOpcode();
 386   bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
 387   if ((isAM2 && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0) ||
 388       (!isAM2 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0))
 389     return false;
 390
 391   bool isLd = Opcode == ARM::LDR || Opcode == ARM::FLDS || Opcode == ARM::FLDD;
 392   // Can't do the merge if the destination register is the same as the would-be
 393   // writeback register.
 394   if (isLd && MI->getOperand(0).getReg() == Base)
 395     return false;
 396
 397   bool DoMerge = false;
 398   ARM_AM::AddrOpc AddSub = ARM_AM::add;
 399   unsigned NewOpc = 0;
 400   if (MBBI != MBB.begin()) {
 401     MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
 402     if (isMatchingDecrement(PrevMBBI, Base, Bytes)) {
 403       DoMerge = true;
 404       AddSub = ARM_AM::sub;
 405       NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
 406     } else if (isAM2 && isMatchingIncrement(PrevMBBI, Base, Bytes)) {
 407       DoMerge = true;
 408       NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
 409     }
 410     if (DoMerge)
 411       MBB.erase(PrevMBBI);
 412   }
 413
 414   if (!DoMerge && MBBI != MBB.end()) {
 415     MachineBasicBlock::iterator NextMBBI = next(MBBI);
 416     if (isAM2 && isMatchingDecrement(NextMBBI, Base, Bytes)) {
 417       DoMerge = true;
 418       AddSub = ARM_AM::sub;
 419       NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
 420     } else if (isMatchingIncrement(NextMBBI, Base, Bytes)) {
 421       DoMerge = true;
 422       NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
 423     }
 424     if (DoMerge)
 425       MBB.erase(NextMBBI);
 426   }
 427
 428   if (!DoMerge)
 429     return false;
 430
 431   bool isDPR = NewOpc == ARM::FLDMD || NewOpc == ARM::FSTMD;
 432   unsigned Offset = isAM2 ? ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift)
 433     : ARM_AM::getAM5Opc((AddSub == ARM_AM::sub) ? ARM_AM::db : ARM_AM::ia,
 434                         true, isDPR ? 2 : 1);
 435   if (isLd) {
 436     if (isAM2)
 437       BuildMI(MBB, MBBI, TII->get(NewOpc), MI->getOperand(0).getReg())
 438         .addReg(Base, true).addReg(Base).addReg(0).addImm(Offset);
 439     else
 440       BuildMI(MBB, MBBI, TII->get(NewOpc)).addReg(Base)
 441         .addImm(Offset).addReg(MI->getOperand(0).getReg(), true);
 442   } else {
 443     if (isAM2)
 444       BuildMI(MBB, MBBI, TII->get(NewOpc), Base).addReg(MI->getOperand(0).getReg())
 445         .addReg(Base).addReg(0).addImm(Offset);
 446     else
 447       BuildMI(MBB, MBBI, TII->get(NewOpc)).addReg(Base)
 448         .addImm(Offset).addReg(MI->getOperand(0).getReg(), false);
 449   }
 450   MBB.erase(MBBI);
 451
 452   return true;
 453 }
 454
 455 /// isMemoryOp - Returns true if instruction is a memory operations (that this
 456 /// pass is capable of operating on).
 457 static bool isMemoryOp(MachineInstr *MI) {
 458   int Opcode = MI->getOpcode();
 459   switch (Opcode) {
 460   default: break;
 461   case ARM::LDR:
 462   case ARM::STR:
 463     return MI->getOperand(1).isRegister() && MI->getOperand(2).getReg() == 0;
 464   case ARM::FLDS:
 465   case ARM::FSTS:
 466     return MI->getOperand(1).isRegister();
 467   case ARM::FLDD:
 468   case ARM::FSTD:
 469     return MI->getOperand(1).isRegister();
 470   }
 471   return false;
 472 }
 473
 474 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
 475 /// ops of the same base and incrementing offset into LDM / STM ops.
 476 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
 477   unsigned NumMerges = 0;
 478   unsigned NumMemOps = 0;
 479   MemOpQueue MemOps;
 480   unsigned CurrBase = 0;
 481   int CurrOpc = -1;
 482   unsigned CurrSize = 0;
 483   unsigned Position = 0;
 484
 485   if (RS) RS->enterBasicBlock(&MBB);
 486   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
 487   while (MBBI != E) {
 488     bool Advance  = false;
 489     bool TryMerge = false;
 490     bool Clobber  = false;
 491
 492     bool isMemOp = isMemoryOp(MBBI);
 493     if (isMemOp) {
 494       int Opcode = MBBI->getOpcode();
 495       bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
 496       unsigned Size = getLSMultipleTransferSize(MBBI);
 497
 498       unsigned Base = MBBI->getOperand(1).getReg();
 499       unsigned OffIdx = MBBI->getNumOperands()-1;
 500       unsigned OffField = MBBI->getOperand(OffIdx).getImm();
 501       int Offset = isAM2
 502         ? ARM_AM::getAM2Offset(OffField) : ARM_AM::getAM5Offset(OffField) * 4;
 503       if (isAM2) {
 504         if (ARM_AM::getAM2Op(OffField) == ARM_AM::sub)
 505           Offset = -Offset;
 506       } else {
 507         if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub)
 508           Offset = -Offset;
 509       }
 510       // Watch out for:
 511       // r4 := ldr [r5]
 512       // r5 := ldr [r5, #4]
 513       // r6 := ldr [r5, #8]
 514       //
 515       // The second ldr has effectively broken the chain even though it
 516       // looks like the later ldr(s) use the same base register. Try to
 517       // merge the ldr's so far, including this one. But don't try to
 518       // combine the following ldr(s).
 519       Clobber = (Opcode == ARM::LDR && Base == MBBI->getOperand(0).getReg());
 520       if (CurrBase == 0 && !Clobber) {
 521         // Start of a new chain.
 522         CurrBase = Base;
 523         CurrOpc  = Opcode;
 524         CurrSize = Size;
 525         MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI));
 526         NumMemOps++;
 527         Advance = true;
 528       } else {
 529         if (Clobber) {
 530           TryMerge = true;
 531           Advance = true;
 532         }
 533
 534         if (CurrOpc == Opcode && CurrBase == Base) {
 535           // Continue adding to the queue.
 536           if (Offset > MemOps.back().Offset) {
 537             MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI));
 538             NumMemOps++;
 539             Advance = true;
 540           } else {
 541             for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
 542                  I != E; ++I) {
 543               if (Offset < I->Offset) {
 544                 MemOps.insert(I, MemOpQueueEntry(Offset, Position, MBBI));
 545                 NumMemOps++;
 546                 Advance = true;
 547                 break;
 548               } else if (Offset == I->Offset) {
 549                 // Collision! This can't be merged!
 550                 break;
 551               }
 552             }
 553           }
 554         }
 555       }
 556     }
 557
 558     if (Advance) {
 559       ++Position;
 560       ++MBBI;
 561     } else
 562       TryMerge = true;
 563
 564     if (TryMerge) {
 565       if (NumMemOps > 1) {
 566         SmallVector<MachineBasicBlock::iterator,4> MBBII =
 567           MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize,MemOps);
 568         // Try folding preceeding/trailing base inc/dec into the generated
 569         // LDM/STM ops.
 570         for (unsigned i = 0, e = MBBII.size(); i < e; ++i)
 571           if (mergeBaseUpdateLSMultiple(MBB, MBBII[i]))
 572             NumMerges++;
 573         NumMerges += MBBII.size();
 574       }
 575
 576       // Try folding preceeding/trailing base inc/dec into those load/store
 577       // that were not merged to form LDM/STM ops.
 578       for (unsigned i = 0; i != NumMemOps; ++i)
 579         if (!MemOps[i].Merged)
 580           if (mergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII))
 581             NumMerges++;
 582
 583       CurrBase = 0;
 584       CurrOpc = -1;
 585       if (NumMemOps) {
 586         MemOps.clear();
 587         NumMemOps = 0;
 588       }
 589
 590       // If iterator hasn't been advanced and this is not a memory op, skip it.
 591       // It can't start a new chain anyway.
 592       if (!Advance && !isMemOp && MBBI != E) {
 593         ++Position;
 594         ++MBBI;
 595       }
 596     }
 597   }
 598   return NumMerges > 0;
 599 }
 600
 601 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return op
 602 /// (bx lr) into the preceeding stack restore so it directly restore the value
 603 /// of LR into pc.
 604 ///   ldmfd sp!, {r7, lr}
 605 ///   bx lr
 606 /// =>
 607 ///   ldmfd sp!, {r7, pc}
 608 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
 609   if (MBB.empty()) return false;
 610
 611   MachineBasicBlock::iterator MBBI = prior(MBB.end());
 612   if (MBBI->getOpcode() == ARM::BX_RET && MBBI != MBB.begin()) {
 613     MachineInstr *PrevMI = prior(MBBI);
 614     if (PrevMI->getOpcode() == ARM::LDM) {
 615       MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
 616       if (MO.getReg() == ARM::LR) {
 617         PrevMI->setInstrDescriptor(TII->get(ARM::LDM_RET));
 618         MO.setReg(ARM::PC);
 619         MBB.erase(MBBI);
 620         return true;
 621       }
 622     }
 623   }
 624   return false;
 625 }
 626
 627 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
 628   const TargetMachine &TM = Fn.getTarget();
 629   TII = TM.getInstrInfo();
 630   MRI = TM.getRegisterInfo();
 631   RS = MRI->requiresRegisterScavenging(Fn) ? new RegScavenger() : NULL;
 632
 633   bool Modified = false;
 634   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
 635        ++MFI) {
 636     MachineBasicBlock &MBB = *MFI;
 637     Modified |= LoadStoreMultipleOpti(MBB);
 638     Modified |= MergeReturnIntoLDM(MBB);
 639   }
 640
 641   delete RS;
 642   return Modified;
 643 }