1 //===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains a pass that performs load / store related peephole
11 // optimizations. This pass should be run after register allocation.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "arm-ldst-opt"
17 #include "ARMBaseInstrInfo.h"
18 #include "ARMMachineFunctionInfo.h"
19 #include "ARMRegisterInfo.h"
20 #include "MCTargetDesc/ARMAddressingModes.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/Function.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineFunctionPass.h"
25 #include "llvm/CodeGen/MachineInstr.h"
26 #include "llvm/CodeGen/MachineInstrBuilder.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/RegisterScavenging.h"
29 #include "llvm/CodeGen/SelectionDAGNodes.h"
30 #include "llvm/Target/TargetData.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 #include "llvm/Target/TargetMachine.h"
33 #include "llvm/Target/TargetRegisterInfo.h"
34 #include "llvm/Support/ErrorHandling.h"
35 #include "llvm/ADT/DenseMap.h"
36 #include "llvm/ADT/STLExtras.h"
37 #include "llvm/ADT/SmallPtrSet.h"
38 #include "llvm/ADT/SmallSet.h"
39 #include "llvm/ADT/SmallVector.h"
40 #include "llvm/ADT/Statistic.h"
43 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
44 STATISTIC(NumSTMGened , "Number of stm instructions generated");
45 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
46 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
47 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
48 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
49 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
50 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm");
51 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm");
52 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's");
53 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's");
55 /// ARMAllocLoadStoreOpt - Post- register allocation pass the combine
56 /// load / store instructions to form ldm / stm instructions.
59 struct ARMLoadStoreOpt : public MachineFunctionPass {
61 ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
63 const TargetInstrInfo *TII;
64 const TargetRegisterInfo *TRI;
69 virtual bool runOnMachineFunction(MachineFunction &Fn);
71 virtual const char *getPassName() const {
72 return "ARM load / store optimization pass";
76 struct MemOpQueueEntry {
81 MachineBasicBlock::iterator MBBI;
83 MemOpQueueEntry(int o, unsigned r, bool k, unsigned p,
84 MachineBasicBlock::iterator i)
85 : Offset(o), Reg(r), isKill(k), Position(p), MBBI(i), Merged(false) {}
87 typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
88 typedef MemOpQueue::iterator MemOpQueueIter;
90 bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
91 int Offset, unsigned Base, bool BaseKill, int Opcode,
92 ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
93 DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs);
94 void MergeOpsUpdate(MachineBasicBlock &MBB,
103 ARMCC::CondCodes Pred,
107 SmallVector<MachineBasicBlock::iterator, 4> &Merges);
108 void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
109 int Opcode, unsigned Size,
110 ARMCC::CondCodes Pred, unsigned PredReg,
111 unsigned Scratch, MemOpQueue &MemOps,
112 SmallVector<MachineBasicBlock::iterator, 4> &Merges);
114 void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
115 bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
116 MachineBasicBlock::iterator &MBBI);
117 bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
118 MachineBasicBlock::iterator MBBI,
119 const TargetInstrInfo *TII,
121 MachineBasicBlock::iterator &I);
122 bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
123 MachineBasicBlock::iterator MBBI,
125 MachineBasicBlock::iterator &I);
126 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
127 bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
129 char ARMLoadStoreOpt::ID = 0;
132 static int getLoadStoreMultipleOpcode(int Opcode, ARM_AM::AMSubMode Mode) {
134 default: llvm_unreachable("Unhandled opcode!");
138 default: llvm_unreachable("Unhandled submode!");
139 case ARM_AM::ia: return ARM::LDMIA;
140 case ARM_AM::da: return ARM::LDMDA;
141 case ARM_AM::db: return ARM::LDMDB;
142 case ARM_AM::ib: return ARM::LDMIB;
148 default: llvm_unreachable("Unhandled submode!");
149 case ARM_AM::ia: return ARM::STMIA;
150 case ARM_AM::da: return ARM::STMDA;
151 case ARM_AM::db: return ARM::STMDB;
152 case ARM_AM::ib: return ARM::STMIB;
159 default: llvm_unreachable("Unhandled submode!");
160 case ARM_AM::ia: return ARM::t2LDMIA;
161 case ARM_AM::db: return ARM::t2LDMDB;
168 default: llvm_unreachable("Unhandled submode!");
169 case ARM_AM::ia: return ARM::t2STMIA;
170 case ARM_AM::db: return ARM::t2STMDB;
176 default: llvm_unreachable("Unhandled submode!");
177 case ARM_AM::ia: return ARM::VLDMSIA;
178 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
184 default: llvm_unreachable("Unhandled submode!");
185 case ARM_AM::ia: return ARM::VSTMSIA;
186 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
192 default: llvm_unreachable("Unhandled submode!");
193 case ARM_AM::ia: return ARM::VLDMDIA;
194 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
200 default: llvm_unreachable("Unhandled submode!");
201 case ARM_AM::ia: return ARM::VSTMDIA;
202 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
213 AMSubMode getLoadStoreMultipleSubMode(int Opcode) {
215 default: llvm_unreachable("Unhandled opcode!");
221 case ARM::t2LDMIA_RET:
223 case ARM::t2LDMIA_UPD:
225 case ARM::t2STMIA_UPD:
227 case ARM::VLDMSIA_UPD:
229 case ARM::VSTMSIA_UPD:
231 case ARM::VLDMDIA_UPD:
233 case ARM::VSTMDIA_UPD:
247 case ARM::t2LDMDB_UPD:
249 case ARM::t2STMDB_UPD:
250 case ARM::VLDMSDB_UPD:
251 case ARM::VSTMSDB_UPD:
252 case ARM::VLDMDDB_UPD:
253 case ARM::VSTMDDB_UPD:
263 return ARM_AM::bad_am_submode;
266 } // end namespace ARM_AM
267 } // end namespace llvm
269 static bool isT2i32Load(unsigned Opc) {
270 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
273 static bool isi32Load(unsigned Opc) {
274 return Opc == ARM::LDRi12 || isT2i32Load(Opc);
277 static bool isT2i32Store(unsigned Opc) {
278 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
281 static bool isi32Store(unsigned Opc) {
282 return Opc == ARM::STRi12 || isT2i32Store(Opc);
285 /// MergeOps - Create and insert a LDM or STM with Base as base register and
286 /// registers in Regs as the register operands that would be loaded / stored.
287 /// It returns true if the transformation is done.
289 ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
290 MachineBasicBlock::iterator MBBI,
291 int Offset, unsigned Base, bool BaseKill,
292 int Opcode, ARMCC::CondCodes Pred,
293 unsigned PredReg, unsigned Scratch, DebugLoc dl,
294 SmallVector<std::pair<unsigned, bool>, 8> &Regs) {
295 // Only a single register to load / store. Don't bother.
296 unsigned NumRegs = Regs.size();
300 ARM_AM::AMSubMode Mode = ARM_AM::ia;
301 // VFP and Thumb2 do not support IB or DA modes.
302 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
303 bool haveIBAndDA = isNotVFP && !isThumb2;
304 if (Offset == 4 && haveIBAndDA)
306 else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA)
308 else if (Offset == -4 * (int)NumRegs && isNotVFP)
309 // VLDM/VSTM do not support DB mode without also updating the base reg.
311 else if (Offset != 0) {
312 // Check if this is a supported opcode before we insert instructions to
313 // calculate a new base register.
314 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return false;
316 // If starting offset isn't zero, insert a MI to materialize a new base.
317 // But only do so if it is cost effective, i.e. merging more than two
323 if (isi32Load(Opcode))
324 // If it is a load, then just use one of the destination register to
325 // use as the new base.
326 NewBase = Regs[NumRegs-1].first;
328 // Use the scratch register to use as a new base.
333 int BaseOpc = !isThumb2 ? ARM::ADDri : ARM::t2ADDri;
335 BaseOpc = !isThumb2 ? ARM::SUBri : ARM::t2SUBri;
338 int ImmedOffset = isThumb2
339 ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset);
340 if (ImmedOffset == -1)
341 // FIXME: Try t2ADDri12 or t2SUBri12?
342 return false; // Probably not worth it then.
344 BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase)
345 .addReg(Base, getKillRegState(BaseKill)).addImm(Offset)
346 .addImm(Pred).addReg(PredReg).addReg(0);
348 BaseKill = true; // New base is always killed right its use.
351 bool isDef = (isi32Load(Opcode) || Opcode == ARM::VLDRS ||
352 Opcode == ARM::VLDRD);
353 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
354 if (!Opcode) return false;
355 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(Opcode))
356 .addReg(Base, getKillRegState(BaseKill))
357 .addImm(Pred).addReg(PredReg);
358 for (unsigned i = 0; i != NumRegs; ++i)
359 MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef)
360 | getKillRegState(Regs[i].second));
365 // MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on
367 void ARMLoadStoreOpt::MergeOpsUpdate(MachineBasicBlock &MBB,
369 unsigned memOpsBegin, unsigned memOpsEnd,
370 unsigned insertAfter, int Offset,
371 unsigned Base, bool BaseKill,
373 ARMCC::CondCodes Pred, unsigned PredReg,
376 SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
377 // First calculate which of the registers should be killed by the merged
379 const unsigned insertPos = memOps[insertAfter].Position;
380 SmallSet<unsigned, 4> KilledRegs;
381 DenseMap<unsigned, unsigned> Killer;
382 for (unsigned i = 0, e = memOps.size(); i != e; ++i) {
383 if (i == memOpsBegin) {
388 if (memOps[i].Position < insertPos && memOps[i].isKill) {
389 unsigned Reg = memOps[i].Reg;
390 KilledRegs.insert(Reg);
395 SmallVector<std::pair<unsigned, bool>, 8> Regs;
396 for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
397 unsigned Reg = memOps[i].Reg;
398 // If we are inserting the merged operation after an operation that
399 // uses the same register, make sure to transfer any kill flag.
400 bool isKill = memOps[i].isKill || KilledRegs.count(Reg);
401 Regs.push_back(std::make_pair(Reg, isKill));
404 // Try to do the merge.
405 MachineBasicBlock::iterator Loc = memOps[insertAfter].MBBI;
407 if (!MergeOps(MBB, Loc, Offset, Base, BaseKill, Opcode,
408 Pred, PredReg, Scratch, dl, Regs))
411 // Merge succeeded, update records.
412 Merges.push_back(prior(Loc));
413 for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
414 // Remove kill flags from any memops that come before insertPos.
415 if (Regs[i-memOpsBegin].second) {
416 unsigned Reg = Regs[i-memOpsBegin].first;
417 if (KilledRegs.count(Reg)) {
418 unsigned j = Killer[Reg];
419 int Idx = memOps[j].MBBI->findRegisterUseOperandIdx(Reg, true);
420 assert(Idx >= 0 && "Cannot find killing operand");
421 memOps[j].MBBI->getOperand(Idx).setIsKill(false);
422 memOps[j].isKill = false;
424 memOps[i].isKill = true;
426 MBB.erase(memOps[i].MBBI);
427 // Update this memop to refer to the merged instruction.
428 // We may need to move kill flags again.
429 memOps[i].Merged = true;
430 memOps[i].MBBI = Merges.back();
431 memOps[i].Position = insertPos;
435 /// MergeLDR_STR - Merge a number of load / store instructions into one or more
436 /// load / store multiple instructions.
438 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
439 unsigned Base, int Opcode, unsigned Size,
440 ARMCC::CondCodes Pred, unsigned PredReg,
441 unsigned Scratch, MemOpQueue &MemOps,
442 SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
443 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
444 int Offset = MemOps[SIndex].Offset;
445 int SOffset = Offset;
446 unsigned insertAfter = SIndex;
447 MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
448 DebugLoc dl = Loc->getDebugLoc();
449 const MachineOperand &PMO = Loc->getOperand(0);
450 unsigned PReg = PMO.getReg();
451 unsigned PRegNum = PMO.isUndef() ? UINT_MAX
452 : getARMRegisterNumbering(PReg);
454 unsigned Limit = ~0U;
456 // vldm / vstm limit are 32 for S variants, 16 for D variants.
474 for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
475 int NewOffset = MemOps[i].Offset;
476 const MachineOperand &MO = MemOps[i].MBBI->getOperand(0);
477 unsigned Reg = MO.getReg();
478 unsigned RegNum = MO.isUndef() ? UINT_MAX
479 : getARMRegisterNumbering(Reg);
480 // Register numbers must be in ascending order. For VFP / NEON load and
481 // store multiples, the registers must also be consecutive and within the
482 // limit on the number of registers per instruction.
483 if (Reg != ARM::SP &&
484 NewOffset == Offset + (int)Size &&
485 ((isNotVFP && RegNum > PRegNum) ||
486 ((Count < Limit) && RegNum == PRegNum+1))) {
491 // Can't merge this in. Try merge the earlier ones first.
492 MergeOpsUpdate(MBB, MemOps, SIndex, i, insertAfter, SOffset,
493 Base, false, Opcode, Pred, PredReg, Scratch, dl, Merges);
494 MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch,
499 if (MemOps[i].Position > MemOps[insertAfter].Position)
503 bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1;
504 MergeOpsUpdate(MBB, MemOps, SIndex, MemOps.size(), insertAfter, SOffset,
505 Base, BaseKill, Opcode, Pred, PredReg, Scratch, dl, Merges);
509 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
510 unsigned Bytes, unsigned Limit,
511 ARMCC::CondCodes Pred, unsigned PredReg){
512 unsigned MyPredReg = 0;
515 if (MI->getOpcode() != ARM::t2SUBri &&
516 MI->getOpcode() != ARM::tSUBspi &&
517 MI->getOpcode() != ARM::SUBri)
520 // Make sure the offset fits in 8 bits.
521 if (Bytes == 0 || (Limit && Bytes >= Limit))
524 unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME
525 return (MI->getOperand(0).getReg() == Base &&
526 MI->getOperand(1).getReg() == Base &&
527 (MI->getOperand(2).getImm()*Scale) == Bytes &&
528 llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
529 MyPredReg == PredReg);
532 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
533 unsigned Bytes, unsigned Limit,
534 ARMCC::CondCodes Pred, unsigned PredReg){
535 unsigned MyPredReg = 0;
538 if (MI->getOpcode() != ARM::t2ADDri &&
539 MI->getOpcode() != ARM::tADDspi &&
540 MI->getOpcode() != ARM::ADDri)
543 if (Bytes == 0 || (Limit && Bytes >= Limit))
544 // Make sure the offset fits in 8 bits.
547 unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME
548 return (MI->getOperand(0).getReg() == Base &&
549 MI->getOperand(1).getReg() == Base &&
550 (MI->getOperand(2).getImm()*Scale) == Bytes &&
551 llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
552 MyPredReg == PredReg);
555 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
556 switch (MI->getOpcode()) {
584 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
587 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
591 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
592 ARM_AM::AMSubMode Mode) {
594 default: llvm_unreachable("Unhandled opcode!");
600 default: llvm_unreachable("Unhandled submode!");
601 case ARM_AM::ia: return ARM::LDMIA_UPD;
602 case ARM_AM::ib: return ARM::LDMIB_UPD;
603 case ARM_AM::da: return ARM::LDMDA_UPD;
604 case ARM_AM::db: return ARM::LDMDB_UPD;
612 default: llvm_unreachable("Unhandled submode!");
613 case ARM_AM::ia: return ARM::STMIA_UPD;
614 case ARM_AM::ib: return ARM::STMIB_UPD;
615 case ARM_AM::da: return ARM::STMDA_UPD;
616 case ARM_AM::db: return ARM::STMDB_UPD;
622 default: llvm_unreachable("Unhandled submode!");
623 case ARM_AM::ia: return ARM::t2LDMIA_UPD;
624 case ARM_AM::db: return ARM::t2LDMDB_UPD;
630 default: llvm_unreachable("Unhandled submode!");
631 case ARM_AM::ia: return ARM::t2STMIA_UPD;
632 case ARM_AM::db: return ARM::t2STMDB_UPD;
637 default: llvm_unreachable("Unhandled submode!");
638 case ARM_AM::ia: return ARM::VLDMSIA_UPD;
639 case ARM_AM::db: return ARM::VLDMSDB_UPD;
644 default: llvm_unreachable("Unhandled submode!");
645 case ARM_AM::ia: return ARM::VLDMDIA_UPD;
646 case ARM_AM::db: return ARM::VLDMDDB_UPD;
651 default: llvm_unreachable("Unhandled submode!");
652 case ARM_AM::ia: return ARM::VSTMSIA_UPD;
653 case ARM_AM::db: return ARM::VSTMSDB_UPD;
658 default: llvm_unreachable("Unhandled submode!");
659 case ARM_AM::ia: return ARM::VSTMDIA_UPD;
660 case ARM_AM::db: return ARM::VSTMDDB_UPD;
668 /// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
669 /// register into the LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
671 /// stmia rn, <ra, rb, rc>
672 /// rn := rn + 4 * 3;
674 /// stmia rn!, <ra, rb, rc>
676 /// rn := rn - 4 * 3;
677 /// ldmia rn, <ra, rb, rc>
679 /// ldmdb rn!, <ra, rb, rc>
680 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
681 MachineBasicBlock::iterator MBBI,
683 MachineBasicBlock::iterator &I) {
684 MachineInstr *MI = MBBI;
685 unsigned Base = MI->getOperand(0).getReg();
686 bool BaseKill = MI->getOperand(0).isKill();
687 unsigned Bytes = getLSMultipleTransferSize(MI);
688 unsigned PredReg = 0;
689 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
690 int Opcode = MI->getOpcode();
691 DebugLoc dl = MI->getDebugLoc();
693 // Can't use an updating ld/st if the base register is also a dest
694 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
695 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
696 if (MI->getOperand(i).getReg() == Base)
699 bool DoMerge = false;
700 ARM_AM::AMSubMode Mode = ARM_AM::getLoadStoreMultipleSubMode(Opcode);
702 // Try merging with the previous instruction.
703 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
704 if (MBBI != BeginMBBI) {
705 MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
706 while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
708 if (Mode == ARM_AM::ia &&
709 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
712 } else if (Mode == ARM_AM::ib &&
713 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
721 // Try merging with the next instruction.
722 MachineBasicBlock::iterator EndMBBI = MBB.end();
723 if (!DoMerge && MBBI != EndMBBI) {
724 MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
725 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
727 if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
728 isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
730 } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
731 isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
746 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
747 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
748 .addReg(Base, getDefRegState(true)) // WB base register
749 .addReg(Base, getKillRegState(BaseKill))
750 .addImm(Pred).addReg(PredReg);
752 // Transfer the rest of operands.
753 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
754 MIB.addOperand(MI->getOperand(OpNum));
756 // Transfer memoperands.
757 MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
763 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
764 ARM_AM::AddrOpc Mode) {
771 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
773 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
775 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
777 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
780 return ARM::t2LDR_PRE;
783 return ARM::t2STR_PRE;
784 default: llvm_unreachable("Unhandled opcode!");
789 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
790 ARM_AM::AddrOpc Mode) {
793 return ARM::LDR_POST;
795 return ARM::STR_POST;
797 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
799 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
801 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
803 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
806 return ARM::t2LDR_POST;
809 return ARM::t2STR_POST;
810 default: llvm_unreachable("Unhandled opcode!");
815 /// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
816 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
817 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
818 MachineBasicBlock::iterator MBBI,
819 const TargetInstrInfo *TII,
821 MachineBasicBlock::iterator &I) {
822 MachineInstr *MI = MBBI;
823 unsigned Base = MI->getOperand(1).getReg();
824 bool BaseKill = MI->getOperand(1).isKill();
825 unsigned Bytes = getLSMultipleTransferSize(MI);
826 int Opcode = MI->getOpcode();
827 DebugLoc dl = MI->getDebugLoc();
828 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
829 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
830 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
831 if (isi32Load(Opcode) || isi32Store(Opcode))
832 if (MI->getOperand(2).getImm() != 0)
834 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
837 bool isLd = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
838 // Can't do the merge if the destination register is the same as the would-be
839 // writeback register.
840 if (isLd && MI->getOperand(0).getReg() == Base)
843 unsigned PredReg = 0;
844 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
845 bool DoMerge = false;
846 ARM_AM::AddrOpc AddSub = ARM_AM::add;
848 // AM2 - 12 bits, thumb2 - 8 bits.
849 unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100);
851 // Try merging with the previous instruction.
852 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
853 if (MBBI != BeginMBBI) {
854 MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
855 while (PrevMBBI != BeginMBBI && PrevMBBI->isDebugValue())
857 if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) {
859 AddSub = ARM_AM::sub;
861 isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) {
865 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, AddSub);
870 // Try merging with the next instruction.
871 MachineBasicBlock::iterator EndMBBI = MBB.end();
872 if (!DoMerge && MBBI != EndMBBI) {
873 MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
874 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
877 isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) {
879 AddSub = ARM_AM::sub;
880 } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) {
884 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, AddSub);
898 Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
900 Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
903 // VLDM[SD}_UPD, VSTM[SD]_UPD
904 // (There are no base-updating versions of VLDR/VSTR instructions, but the
905 // updating load/store-multiple instructions can be used with only one
907 MachineOperand &MO = MI->getOperand(0);
908 BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
909 .addReg(Base, getDefRegState(true)) // WB base register
910 .addReg(Base, getKillRegState(isLd ? BaseKill : false))
911 .addImm(Pred).addReg(PredReg)
912 .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
913 getKillRegState(MO.isKill())));
916 // LDR_PRE, LDR_POST,
917 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
918 .addReg(Base, RegState::Define)
919 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
921 // t2LDR_PRE, t2LDR_POST
922 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
923 .addReg(Base, RegState::Define)
924 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
926 MachineOperand &MO = MI->getOperand(0);
929 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
930 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
931 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
933 // t2STR_PRE, t2STR_POST
934 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
935 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
936 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
943 /// isMemoryOp - Returns true if instruction is a memory operation that this
944 /// pass is capable of operating on.
945 static bool isMemoryOp(const MachineInstr *MI) {
946 // When no memory operands are present, conservatively assume unaligned,
947 // volatile, unfoldable.
948 if (!MI->hasOneMemOperand())
951 const MachineMemOperand *MMO = *MI->memoperands_begin();
953 // Don't touch volatile memory accesses - we may be changing their order.
954 if (MMO->isVolatile())
957 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
959 if (MMO->getAlignment() < 4)
962 // str <undef> could probably be eliminated entirely, but for now we just want
963 // to avoid making a mess of it.
964 // FIXME: Use str <undef> as a wildcard to enable better stm folding.
965 if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() &&
966 MI->getOperand(0).isUndef())
969 // Likewise don't mess with references to undefined addresses.
970 if (MI->getNumOperands() > 1 && MI->getOperand(1).isReg() &&
971 MI->getOperand(1).isUndef())
974 int Opcode = MI->getOpcode();
979 return MI->getOperand(1).isReg();
982 return MI->getOperand(1).isReg();
989 return MI->getOperand(1).isReg();
994 /// AdvanceRS - Advance register scavenger to just before the earliest memory
995 /// op that is being merged.
996 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) {
997 MachineBasicBlock::iterator Loc = MemOps[0].MBBI;
998 unsigned Position = MemOps[0].Position;
999 for (unsigned i = 1, e = MemOps.size(); i != e; ++i) {
1000 if (MemOps[i].Position < Position) {
1001 Position = MemOps[i].Position;
1002 Loc = MemOps[i].MBBI;
1006 if (Loc != MBB.begin())
1007 RS->forward(prior(Loc));
1010 static int getMemoryOpOffset(const MachineInstr *MI) {
1011 int Opcode = MI->getOpcode();
1012 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
1013 unsigned NumOperands = MI->getDesc().getNumOperands();
1014 unsigned OffField = MI->getOperand(NumOperands-3).getImm();
1016 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
1017 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
1018 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
1019 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12)
1022 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
1023 : ARM_AM::getAM5Offset(OffField) * 4;
1025 if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub)
1028 if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub)
1034 static void InsertLDR_STR(MachineBasicBlock &MBB,
1035 MachineBasicBlock::iterator &MBBI,
1036 int Offset, bool isDef,
1037 DebugLoc dl, unsigned NewOpc,
1038 unsigned Reg, bool RegDeadKill, bool RegUndef,
1039 unsigned BaseReg, bool BaseKill, bool BaseUndef,
1040 bool OffKill, bool OffUndef,
1041 ARMCC::CondCodes Pred, unsigned PredReg,
1042 const TargetInstrInfo *TII, bool isT2) {
1044 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1046 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1047 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1048 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1050 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1052 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1053 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1054 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1058 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1059 MachineBasicBlock::iterator &MBBI) {
1060 MachineInstr *MI = &*MBBI;
1061 unsigned Opcode = MI->getOpcode();
1062 if (Opcode == ARM::LDRD || Opcode == ARM::STRD ||
1063 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) {
1064 unsigned EvenReg = MI->getOperand(0).getReg();
1065 unsigned OddReg = MI->getOperand(1).getReg();
1066 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1067 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false);
1068 if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum)
1071 MachineBasicBlock::iterator NewBBI = MBBI;
1072 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1073 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1074 bool EvenDeadKill = isLd ?
1075 MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1076 bool EvenUndef = MI->getOperand(0).isUndef();
1077 bool OddDeadKill = isLd ?
1078 MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1079 bool OddUndef = MI->getOperand(1).isUndef();
1080 const MachineOperand &BaseOp = MI->getOperand(2);
1081 unsigned BaseReg = BaseOp.getReg();
1082 bool BaseKill = BaseOp.isKill();
1083 bool BaseUndef = BaseOp.isUndef();
1084 bool OffKill = isT2 ? false : MI->getOperand(3).isKill();
1085 bool OffUndef = isT2 ? false : MI->getOperand(3).isUndef();
1086 int OffImm = getMemoryOpOffset(MI);
1087 unsigned PredReg = 0;
1088 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
1090 if (OddRegNum > EvenRegNum && OffImm == 0) {
1091 // Ascending register numbers and no offset. It's safe to change it to a
1093 unsigned NewOpc = (isLd)
1094 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1095 : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1097 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1098 .addReg(BaseReg, getKillRegState(BaseKill))
1099 .addImm(Pred).addReg(PredReg)
1100 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1101 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill));
1104 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1105 .addReg(BaseReg, getKillRegState(BaseKill))
1106 .addImm(Pred).addReg(PredReg)
1108 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1110 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef));
1113 NewBBI = llvm::prior(MBBI);
1115 // Split into two instructions.
1116 unsigned NewOpc = (isLd)
1117 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1118 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1119 DebugLoc dl = MBBI->getDebugLoc();
1120 // If this is a load and base register is killed, it may have been
1121 // re-defed by the load, make sure the first load does not clobber it.
1123 (BaseKill || OffKill) &&
1124 (TRI->regsOverlap(EvenReg, BaseReg))) {
1125 assert(!TRI->regsOverlap(OddReg, BaseReg));
1126 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
1127 OddReg, OddDeadKill, false,
1128 BaseReg, false, BaseUndef, false, OffUndef,
1129 Pred, PredReg, TII, isT2);
1130 NewBBI = llvm::prior(MBBI);
1131 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1132 EvenReg, EvenDeadKill, false,
1133 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1134 Pred, PredReg, TII, isT2);
1136 if (OddReg == EvenReg && EvenDeadKill) {
1137 // If the two source operands are the same, the kill marker is
1138 // probably on the first one. e.g.
1139 // t2STRDi8 %R5<kill>, %R5, %R9<kill>, 0, 14, %reg0
1140 EvenDeadKill = false;
1143 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc,
1144 EvenReg, EvenDeadKill, EvenUndef,
1145 BaseReg, false, BaseUndef, false, OffUndef,
1146 Pred, PredReg, TII, isT2);
1147 NewBBI = llvm::prior(MBBI);
1148 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc,
1149 OddReg, OddDeadKill, OddUndef,
1150 BaseReg, BaseKill, BaseUndef, OffKill, OffUndef,
1151 Pred, PredReg, TII, isT2);
1166 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR
1167 /// ops of the same base and incrementing offset into LDM / STM ops.
1168 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1169 unsigned NumMerges = 0;
1170 unsigned NumMemOps = 0;
1172 unsigned CurrBase = 0;
1174 unsigned CurrSize = 0;
1175 ARMCC::CondCodes CurrPred = ARMCC::AL;
1176 unsigned CurrPredReg = 0;
1177 unsigned Position = 0;
1178 SmallVector<MachineBasicBlock::iterator,4> Merges;
1180 RS->enterBasicBlock(&MBB);
1181 MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
1183 if (FixInvalidRegPairOp(MBB, MBBI))
1186 bool Advance = false;
1187 bool TryMerge = false;
1188 bool Clobber = false;
1190 bool isMemOp = isMemoryOp(MBBI);
1192 int Opcode = MBBI->getOpcode();
1193 unsigned Size = getLSMultipleTransferSize(MBBI);
1194 const MachineOperand &MO = MBBI->getOperand(0);
1195 unsigned Reg = MO.getReg();
1196 bool isKill = MO.isDef() ? false : MO.isKill();
1197 unsigned Base = MBBI->getOperand(1).getReg();
1198 unsigned PredReg = 0;
1199 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MBBI, PredReg);
1200 int Offset = getMemoryOpOffset(MBBI);
1203 // r5 := ldr [r5, #4]
1204 // r6 := ldr [r5, #8]
1206 // The second ldr has effectively broken the chain even though it
1207 // looks like the later ldr(s) use the same base register. Try to
1208 // merge the ldr's so far, including this one. But don't try to
1209 // combine the following ldr(s).
1210 Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg());
1211 if (CurrBase == 0 && !Clobber) {
1212 // Start of a new chain.
1217 CurrPredReg = PredReg;
1218 MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill, Position, MBBI));
1227 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1228 // No need to match PredReg.
1229 // Continue adding to the queue.
1230 if (Offset > MemOps.back().Offset) {
1231 MemOps.push_back(MemOpQueueEntry(Offset, Reg, isKill,
1236 for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end();
1238 if (Offset < I->Offset) {
1239 MemOps.insert(I, MemOpQueueEntry(Offset, Reg, isKill,
1244 } else if (Offset == I->Offset) {
1245 // Collision! This can't be merged!
1254 if (MBBI->isDebugValue()) {
1257 // Reach the end of the block, try merging the memory instructions.
1259 } else if (Advance) {
1263 // Reach the end of the block, try merging the memory instructions.
1269 if (NumMemOps > 1) {
1270 // Try to find a free register to use as a new base in case it's needed.
1271 // First advance to the instruction just before the start of the chain.
1272 AdvanceRS(MBB, MemOps);
1273 // Find a scratch register.
1274 unsigned Scratch = RS->FindUnusedReg(ARM::GPRRegisterClass);
1275 // Process the load / store instructions.
1276 RS->forward(prior(MBBI));
1280 MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize,
1281 CurrPred, CurrPredReg, Scratch, MemOps, Merges);
1283 // Try folding preceding/trailing base inc/dec into the generated
1285 for (unsigned i = 0, e = Merges.size(); i < e; ++i)
1286 if (MergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI))
1288 NumMerges += Merges.size();
1290 // Try folding preceding/trailing base inc/dec into those load/store
1291 // that were not merged to form LDM/STM ops.
1292 for (unsigned i = 0; i != NumMemOps; ++i)
1293 if (!MemOps[i].Merged)
1294 if (MergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI))
1297 // RS may be pointing to an instruction that's deleted.
1298 RS->skipTo(prior(MBBI));
1299 } else if (NumMemOps == 1) {
1300 // Try folding preceding/trailing base inc/dec into the single
1302 if (MergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) {
1304 RS->forward(prior(MBBI));
1311 CurrPred = ARMCC::AL;
1318 // If iterator hasn't been advanced and this is not a memory op, skip it.
1319 // It can't start a new chain anyway.
1320 if (!Advance && !isMemOp && MBBI != E) {
1326 return NumMerges > 0;
1329 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return ops
1330 /// ("bx lr" and "mov pc, lr") into the preceding stack restore so it
1331 /// directly restore the value of LR into pc.
1332 /// ldmfd sp!, {..., lr}
1335 /// ldmfd sp!, {..., lr}
1338 /// ldmfd sp!, {..., pc}
1339 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1340 if (MBB.empty()) return false;
1342 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1343 if (MBBI != MBB.begin() &&
1344 (MBBI->getOpcode() == ARM::BX_RET ||
1345 MBBI->getOpcode() == ARM::tBX_RET ||
1346 MBBI->getOpcode() == ARM::MOVPCLR)) {
1347 MachineInstr *PrevMI = prior(MBBI);
1348 unsigned Opcode = PrevMI->getOpcode();
1349 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1350 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1351 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
1352 MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1);
1353 if (MO.getReg() != ARM::LR)
1355 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1356 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1357 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1358 PrevMI->setDesc(TII->get(NewOpc));
1360 PrevMI->copyImplicitOps(&*MBBI);
1368 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1369 const TargetMachine &TM = Fn.getTarget();
1370 AFI = Fn.getInfo<ARMFunctionInfo>();
1371 TII = TM.getInstrInfo();
1372 TRI = TM.getRegisterInfo();
1373 RS = new RegScavenger();
1374 isThumb2 = AFI->isThumb2Function();
1376 bool Modified = false;
1377 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1379 MachineBasicBlock &MBB = *MFI;
1380 Modified |= LoadStoreMultipleOpti(MBB);
1381 if (TM.getSubtarget<ARMSubtarget>().hasV5TOps())
1382 Modified |= MergeReturnIntoLDM(MBB);
1390 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move
1391 /// load / stores from consecutive locations close to make it more
1392 /// likely they will be combined later.
1395 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
1397 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
1399 const TargetData *TD;
1400 const TargetInstrInfo *TII;
1401 const TargetRegisterInfo *TRI;
1402 const ARMSubtarget *STI;
1403 MachineRegisterInfo *MRI;
1404 MachineFunction *MF;
1406 virtual bool runOnMachineFunction(MachineFunction &Fn);
1408 virtual const char *getPassName() const {
1409 return "ARM pre- register allocation load / store optimization pass";
1413 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
1414 unsigned &NewOpc, unsigned &EvenReg,
1415 unsigned &OddReg, unsigned &BaseReg,
1417 unsigned &PredReg, ARMCC::CondCodes &Pred,
1419 bool RescheduleOps(MachineBasicBlock *MBB,
1420 SmallVector<MachineInstr*, 4> &Ops,
1421 unsigned Base, bool isLd,
1422 DenseMap<MachineInstr*, unsigned> &MI2LocMap);
1423 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
1425 char ARMPreAllocLoadStoreOpt::ID = 0;
1428 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1429 TD = Fn.getTarget().getTargetData();
1430 TII = Fn.getTarget().getInstrInfo();
1431 TRI = Fn.getTarget().getRegisterInfo();
1432 STI = &Fn.getTarget().getSubtarget<ARMSubtarget>();
1433 MRI = &Fn.getRegInfo();
1436 bool Modified = false;
1437 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1439 Modified |= RescheduleLoadStoreInstrs(MFI);
1444 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
1445 MachineBasicBlock::iterator I,
1446 MachineBasicBlock::iterator E,
1447 SmallPtrSet<MachineInstr*, 4> &MemOps,
1448 SmallSet<unsigned, 4> &MemRegs,
1449 const TargetRegisterInfo *TRI) {
1450 // Are there stores / loads / calls between them?
1451 // FIXME: This is overly conservative. We should make use of alias information
1453 SmallSet<unsigned, 4> AddedRegPressure;
1455 if (I->isDebugValue() || MemOps.count(&*I))
1457 const MCInstrDesc &MCID = I->getDesc();
1458 if (MCID.isCall() || MCID.isTerminator() || I->hasUnmodeledSideEffects())
1460 if (isLd && MCID.mayStore())
1465 // It's not safe to move the first 'str' down.
1468 // str r4, [r0, #+4]
1469 if (MCID.mayStore())
1472 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
1473 MachineOperand &MO = I->getOperand(j);
1476 unsigned Reg = MO.getReg();
1477 if (MO.isDef() && TRI->regsOverlap(Reg, Base))
1479 if (Reg != Base && !MemRegs.count(Reg))
1480 AddedRegPressure.insert(Reg);
1484 // Estimate register pressure increase due to the transformation.
1485 if (MemRegs.size() <= 4)
1486 // Ok if we are moving small number of instructions.
1488 return AddedRegPressure.size() <= MemRegs.size() * 2;
1492 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
1494 unsigned &NewOpc, unsigned &EvenReg,
1495 unsigned &OddReg, unsigned &BaseReg,
1496 int &Offset, unsigned &PredReg,
1497 ARMCC::CondCodes &Pred,
1499 // Make sure we're allowed to generate LDRD/STRD.
1500 if (!STI->hasV5TEOps())
1503 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
1505 unsigned Opcode = Op0->getOpcode();
1506 if (Opcode == ARM::LDRi12)
1508 else if (Opcode == ARM::STRi12)
1510 else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
1511 NewOpc = ARM::t2LDRDi8;
1514 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
1515 NewOpc = ARM::t2STRDi8;
1521 // Make sure the base address satisfies i64 ld / st alignment requirement.
1522 if (!Op0->hasOneMemOperand() ||
1523 !(*Op0->memoperands_begin())->getValue() ||
1524 (*Op0->memoperands_begin())->isVolatile())
1527 unsigned Align = (*Op0->memoperands_begin())->getAlignment();
1528 const Function *Func = MF->getFunction();
1529 unsigned ReqAlign = STI->hasV6Ops()
1530 ? TD->getABITypeAlignment(Type::getInt64Ty(Func->getContext()))
1531 : 8; // Pre-v6 need 8-byte align
1532 if (Align < ReqAlign)
1535 // Then make sure the immediate offset fits.
1536 int OffImm = getMemoryOpOffset(Op0);
1538 int Limit = (1 << 8) * Scale;
1539 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
1543 ARM_AM::AddrOpc AddSub = ARM_AM::add;
1545 AddSub = ARM_AM::sub;
1548 int Limit = (1 << 8) * Scale;
1549 if (OffImm >= Limit || (OffImm & (Scale-1)))
1551 Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
1553 EvenReg = Op0->getOperand(0).getReg();
1554 OddReg = Op1->getOperand(0).getReg();
1555 if (EvenReg == OddReg)
1557 BaseReg = Op0->getOperand(1).getReg();
1558 Pred = llvm::getInstrPredicate(Op0, PredReg);
1559 dl = Op0->getDebugLoc();
1564 struct OffsetCompare {
1565 bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const {
1566 int LOffset = getMemoryOpOffset(LHS);
1567 int ROffset = getMemoryOpOffset(RHS);
1568 assert(LHS == RHS || LOffset != ROffset);
1569 return LOffset > ROffset;
1574 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
1575 SmallVector<MachineInstr*, 4> &Ops,
1576 unsigned Base, bool isLd,
1577 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
1578 bool RetVal = false;
1580 // Sort by offset (in reverse order).
1581 std::sort(Ops.begin(), Ops.end(), OffsetCompare());
1583 // The loads / stores of the same base are in order. Scan them from first to
1584 // last and check for the following:
1585 // 1. Any def of base.
1587 while (Ops.size() > 1) {
1588 unsigned FirstLoc = ~0U;
1589 unsigned LastLoc = 0;
1590 MachineInstr *FirstOp = 0;
1591 MachineInstr *LastOp = 0;
1593 unsigned LastOpcode = 0;
1594 unsigned LastBytes = 0;
1595 unsigned NumMove = 0;
1596 for (int i = Ops.size() - 1; i >= 0; --i) {
1597 MachineInstr *Op = Ops[i];
1598 unsigned Loc = MI2LocMap[Op];
1599 if (Loc <= FirstLoc) {
1603 if (Loc >= LastLoc) {
1608 unsigned Opcode = Op->getOpcode();
1609 if (LastOpcode && Opcode != LastOpcode)
1612 int Offset = getMemoryOpOffset(Op);
1613 unsigned Bytes = getLSMultipleTransferSize(Op);
1615 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
1618 LastOffset = Offset;
1620 LastOpcode = Opcode;
1621 if (++NumMove == 8) // FIXME: Tune this limit.
1628 SmallPtrSet<MachineInstr*, 4> MemOps;
1629 SmallSet<unsigned, 4> MemRegs;
1630 for (int i = NumMove-1; i >= 0; --i) {
1631 MemOps.insert(Ops[i]);
1632 MemRegs.insert(Ops[i]->getOperand(0).getReg());
1635 // Be conservative, if the instructions are too far apart, don't
1636 // move them. We want to limit the increase of register pressure.
1637 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
1639 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
1640 MemOps, MemRegs, TRI);
1642 for (unsigned i = 0; i != NumMove; ++i)
1645 // This is the new location for the loads / stores.
1646 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
1647 while (InsertPos != MBB->end()
1648 && (MemOps.count(InsertPos) || InsertPos->isDebugValue()))
1651 // If we are moving a pair of loads / stores, see if it makes sense
1652 // to try to allocate a pair of registers that can form register pairs.
1653 MachineInstr *Op0 = Ops.back();
1654 MachineInstr *Op1 = Ops[Ops.size()-2];
1655 unsigned EvenReg = 0, OddReg = 0;
1656 unsigned BaseReg = 0, PredReg = 0;
1657 ARMCC::CondCodes Pred = ARMCC::AL;
1659 unsigned NewOpc = 0;
1662 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
1663 EvenReg, OddReg, BaseReg,
1664 Offset, PredReg, Pred, isT2)) {
1668 const MCInstrDesc &MCID = TII->get(NewOpc);
1669 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI);
1670 MRI->constrainRegClass(EvenReg, TRC);
1671 MRI->constrainRegClass(OddReg, TRC);
1673 // Form the pair instruction.
1675 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
1676 .addReg(EvenReg, RegState::Define)
1677 .addReg(OddReg, RegState::Define)
1679 // FIXME: We're converting from LDRi12 to an insn that still
1680 // uses addrmode2, so we need an explicit offset reg. It should
1681 // always by reg0 since we're transforming LDRi12s.
1684 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1687 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
1691 // FIXME: We're converting from LDRi12 to an insn that still
1692 // uses addrmode2, so we need an explicit offset reg. It should
1693 // always by reg0 since we're transforming STRi12s.
1696 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1702 // Add register allocation hints to form register pairs.
1703 MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg);
1704 MRI->setRegAllocationHint(OddReg, ARMRI::RegPairOdd, EvenReg);
1706 for (unsigned i = 0; i != NumMove; ++i) {
1707 MachineInstr *Op = Ops.back();
1709 MBB->splice(InsertPos, MBB, Op);
1713 NumLdStMoved += NumMove;
1723 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
1724 bool RetVal = false;
1726 DenseMap<MachineInstr*, unsigned> MI2LocMap;
1727 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap;
1728 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap;
1729 SmallVector<unsigned, 4> LdBases;
1730 SmallVector<unsigned, 4> StBases;
1733 MachineBasicBlock::iterator MBBI = MBB->begin();
1734 MachineBasicBlock::iterator E = MBB->end();
1736 for (; MBBI != E; ++MBBI) {
1737 MachineInstr *MI = MBBI;
1738 const MCInstrDesc &MCID = MI->getDesc();
1739 if (MCID.isCall() || MCID.isTerminator()) {
1740 // Stop at barriers.
1745 if (!MI->isDebugValue())
1746 MI2LocMap[MI] = ++Loc;
1748 if (!isMemoryOp(MI))
1750 unsigned PredReg = 0;
1751 if (llvm::getInstrPredicate(MI, PredReg) != ARMCC::AL)
1754 int Opc = MI->getOpcode();
1755 bool isLd = isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
1756 unsigned Base = MI->getOperand(1).getReg();
1757 int Offset = getMemoryOpOffset(MI);
1759 bool StopHere = false;
1761 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1762 Base2LdsMap.find(Base);
1763 if (BI != Base2LdsMap.end()) {
1764 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1765 if (Offset == getMemoryOpOffset(BI->second[i])) {
1771 BI->second.push_back(MI);
1773 SmallVector<MachineInstr*, 4> MIs;
1775 Base2LdsMap[Base] = MIs;
1776 LdBases.push_back(Base);
1779 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI =
1780 Base2StsMap.find(Base);
1781 if (BI != Base2StsMap.end()) {
1782 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
1783 if (Offset == getMemoryOpOffset(BI->second[i])) {
1789 BI->second.push_back(MI);
1791 SmallVector<MachineInstr*, 4> MIs;
1793 Base2StsMap[Base] = MIs;
1794 StBases.push_back(Base);
1799 // Found a duplicate (a base+offset combination that's seen earlier).
1806 // Re-schedule loads.
1807 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
1808 unsigned Base = LdBases[i];
1809 SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base];
1811 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
1814 // Re-schedule stores.
1815 for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
1816 unsigned Base = StBases[i];
1817 SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base];
1819 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
1823 Base2LdsMap.clear();
1824 Base2StsMap.clear();
1834 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store
1835 /// optimization pass.
1836 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
1838 return new ARMPreAllocLoadStoreOpt();
1839 return new ARMLoadStoreOpt();