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