1 //===- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass -------------===//
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 /// \file This file contains a pass that performs load / store related peephole
11 /// optimizations. This pass should be run after register allocation.
13 //===----------------------------------------------------------------------===//
16 #include "ARMBaseInstrInfo.h"
17 #include "ARMBaseRegisterInfo.h"
18 #include "ARMISelLowering.h"
19 #include "ARMMachineFunctionInfo.h"
20 #include "ARMSubtarget.h"
21 #include "MCTargetDesc/ARMAddressingModes.h"
22 #include "MCTargetDesc/ARMBaseInfo.h"
23 #include "Utils/ARMBaseInfo.h"
24 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/ADT/DenseMap.h"
26 #include "llvm/ADT/DenseSet.h"
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/SmallSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/ADT/iterator_range.h"
33 #include "llvm/Analysis/AliasAnalysis.h"
34 #include "llvm/CodeGen/LivePhysRegs.h"
35 #include "llvm/CodeGen/MachineBasicBlock.h"
36 #include "llvm/CodeGen/MachineFunction.h"
37 #include "llvm/CodeGen/MachineFunctionPass.h"
38 #include "llvm/CodeGen/MachineInstr.h"
39 #include "llvm/CodeGen/MachineInstrBuilder.h"
40 #include "llvm/CodeGen/MachineMemOperand.h"
41 #include "llvm/CodeGen/MachineOperand.h"
42 #include "llvm/CodeGen/MachineRegisterInfo.h"
43 #include "llvm/CodeGen/RegisterClassInfo.h"
44 #include "llvm/CodeGen/TargetFrameLowering.h"
45 #include "llvm/CodeGen/TargetInstrInfo.h"
46 #include "llvm/CodeGen/TargetLowering.h"
47 #include "llvm/CodeGen/TargetRegisterInfo.h"
48 #include "llvm/CodeGen/TargetSubtargetInfo.h"
49 #include "llvm/IR/DataLayout.h"
50 #include "llvm/IR/DebugLoc.h"
51 #include "llvm/IR/DerivedTypes.h"
52 #include "llvm/IR/Function.h"
53 #include "llvm/IR/Type.h"
54 #include "llvm/MC/MCInstrDesc.h"
55 #include "llvm/Pass.h"
56 #include "llvm/Support/Allocator.h"
57 #include "llvm/Support/CommandLine.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/ErrorHandling.h"
60 #include "llvm/Support/raw_ostream.h"
71 #define DEBUG_TYPE "arm-ldst-opt"
73 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
74 STATISTIC(NumSTMGened , "Number of stm instructions generated");
75 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
76 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
77 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
78 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
79 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
80 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm");
81 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm");
82 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's");
83 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's");
85 /// This switch disables formation of double/multi instructions that could
86 /// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP
87 /// disabled. This can be used to create libraries that are robust even when
88 /// users provoke undefined behaviour by supplying misaligned pointers.
89 /// \see mayCombineMisaligned()
91 AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden,
92 cl::init(false), cl::desc("Be more conservative in ARM load/store opt"));
94 #define ARM_LOAD_STORE_OPT_NAME "ARM load / store optimization pass"
98 /// Post- register allocation pass the combine load / store instructions to
99 /// form ldm / stm instructions.
100 struct ARMLoadStoreOpt : public MachineFunctionPass {
103 const MachineFunction *MF;
104 const TargetInstrInfo *TII;
105 const TargetRegisterInfo *TRI;
106 const ARMSubtarget *STI;
107 const TargetLowering *TL;
108 ARMFunctionInfo *AFI;
109 LivePhysRegs LiveRegs;
110 RegisterClassInfo RegClassInfo;
111 MachineBasicBlock::const_iterator LiveRegPos;
113 bool RegClassInfoValid;
114 bool isThumb1, isThumb2;
116 ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
118 bool runOnMachineFunction(MachineFunction &Fn) override;
120 MachineFunctionProperties getRequiredProperties() const override {
121 return MachineFunctionProperties().set(
122 MachineFunctionProperties::Property::NoVRegs);
125 StringRef getPassName() const override { return ARM_LOAD_STORE_OPT_NAME; }
128 /// A set of load/store MachineInstrs with same base register sorted by
130 struct MemOpQueueEntry {
132 int Offset; ///< Load/Store offset.
133 unsigned Position; ///< Position as counted from end of basic block.
135 MemOpQueueEntry(MachineInstr &MI, int Offset, unsigned Position)
136 : MI(&MI), Offset(Offset), Position(Position) {}
138 using MemOpQueue = SmallVector<MemOpQueueEntry, 8>;
140 /// A set of MachineInstrs that fulfill (nearly all) conditions to get
141 /// merged into a LDM/STM.
142 struct MergeCandidate {
143 /// List of instructions ordered by load/store offset.
144 SmallVector<MachineInstr*, 4> Instrs;
146 /// Index in Instrs of the instruction being latest in the schedule.
147 unsigned LatestMIIdx;
149 /// Index in Instrs of the instruction being earliest in the schedule.
150 unsigned EarliestMIIdx;
152 /// Index into the basic block where the merged instruction will be
153 /// inserted. (See MemOpQueueEntry.Position)
156 /// Whether the instructions can be merged into a ldm/stm instruction.
157 bool CanMergeToLSMulti;
159 /// Whether the instructions can be merged into a ldrd/strd instruction.
160 bool CanMergeToLSDouble;
162 SpecificBumpPtrAllocator<MergeCandidate> Allocator;
163 SmallVector<const MergeCandidate*,4> Candidates;
164 SmallVector<MachineInstr*,4> MergeBaseCandidates;
166 void moveLiveRegsBefore(const MachineBasicBlock &MBB,
167 MachineBasicBlock::const_iterator Before);
168 unsigned findFreeReg(const TargetRegisterClass &RegClass);
169 void UpdateBaseRegUses(MachineBasicBlock &MBB,
170 MachineBasicBlock::iterator MBBI, const DebugLoc &DL,
171 unsigned Base, unsigned WordOffset,
172 ARMCC::CondCodes Pred, unsigned PredReg);
173 MachineInstr *CreateLoadStoreMulti(
174 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
175 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
176 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
177 ArrayRef<std::pair<unsigned, bool>> Regs);
178 MachineInstr *CreateLoadStoreDouble(
179 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
180 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
181 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
182 ArrayRef<std::pair<unsigned, bool>> Regs) const;
183 void FormCandidates(const MemOpQueue &MemOps);
184 MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
185 bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
186 MachineBasicBlock::iterator &MBBI);
187 bool MergeBaseUpdateLoadStore(MachineInstr *MI);
188 bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
189 bool MergeBaseUpdateLSDouble(MachineInstr &MI) const;
190 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
191 bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
192 bool CombineMovBx(MachineBasicBlock &MBB);
195 } // end anonymous namespace
197 char ARMLoadStoreOpt::ID = 0;
199 INITIALIZE_PASS(ARMLoadStoreOpt, "arm-ldst-opt", ARM_LOAD_STORE_OPT_NAME, false,
202 static bool definesCPSR(const MachineInstr &MI) {
203 for (const auto &MO : MI.operands()) {
206 if (MO.isDef() && MO.getReg() == ARM::CPSR && !MO.isDead())
207 // If the instruction has live CPSR def, then it's not safe to fold it
208 // into load / store.
215 static int getMemoryOpOffset(const MachineInstr &MI) {
216 unsigned Opcode = MI.getOpcode();
217 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
218 unsigned NumOperands = MI.getDesc().getNumOperands();
219 unsigned OffField = MI.getOperand(NumOperands - 3).getImm();
221 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
222 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
223 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
224 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12)
227 // Thumb1 immediate offsets are scaled by 4
228 if (Opcode == ARM::tLDRi || Opcode == ARM::tSTRi ||
229 Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi)
232 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
233 : ARM_AM::getAM5Offset(OffField) * 4;
234 ARM_AM::AddrOpc Op = isAM3 ? ARM_AM::getAM3Op(OffField)
235 : ARM_AM::getAM5Op(OffField);
237 if (Op == ARM_AM::sub)
243 static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
244 return MI.getOperand(1);
247 static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
248 return MI.getOperand(0);
251 static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
253 default: llvm_unreachable("Unhandled opcode!");
257 default: llvm_unreachable("Unhandled submode!");
258 case ARM_AM::ia: return ARM::LDMIA;
259 case ARM_AM::da: return ARM::LDMDA;
260 case ARM_AM::db: return ARM::LDMDB;
261 case ARM_AM::ib: return ARM::LDMIB;
266 default: llvm_unreachable("Unhandled submode!");
267 case ARM_AM::ia: return ARM::STMIA;
268 case ARM_AM::da: return ARM::STMDA;
269 case ARM_AM::db: return ARM::STMDB;
270 case ARM_AM::ib: return ARM::STMIB;
274 // tLDMIA is writeback-only - unless the base register is in the input
278 default: llvm_unreachable("Unhandled submode!");
279 case ARM_AM::ia: return ARM::tLDMIA;
283 // There is no non-writeback tSTMIA either.
286 default: llvm_unreachable("Unhandled submode!");
287 case ARM_AM::ia: return ARM::tSTMIA_UPD;
293 default: llvm_unreachable("Unhandled submode!");
294 case ARM_AM::ia: return ARM::t2LDMIA;
295 case ARM_AM::db: return ARM::t2LDMDB;
301 default: llvm_unreachable("Unhandled submode!");
302 case ARM_AM::ia: return ARM::t2STMIA;
303 case ARM_AM::db: return ARM::t2STMDB;
308 default: llvm_unreachable("Unhandled submode!");
309 case ARM_AM::ia: return ARM::VLDMSIA;
310 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
315 default: llvm_unreachable("Unhandled submode!");
316 case ARM_AM::ia: return ARM::VSTMSIA;
317 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
322 default: llvm_unreachable("Unhandled submode!");
323 case ARM_AM::ia: return ARM::VLDMDIA;
324 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
329 default: llvm_unreachable("Unhandled submode!");
330 case ARM_AM::ia: return ARM::VSTMDIA;
331 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
336 static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
338 default: llvm_unreachable("Unhandled opcode!");
345 case ARM::tLDMIA_UPD:
346 case ARM::tSTMIA_UPD:
347 case ARM::t2LDMIA_RET:
349 case ARM::t2LDMIA_UPD:
351 case ARM::t2STMIA_UPD:
353 case ARM::VLDMSIA_UPD:
355 case ARM::VSTMSIA_UPD:
357 case ARM::VLDMDIA_UPD:
359 case ARM::VSTMDIA_UPD:
373 case ARM::t2LDMDB_UPD:
375 case ARM::t2STMDB_UPD:
376 case ARM::VLDMSDB_UPD:
377 case ARM::VSTMSDB_UPD:
378 case ARM::VLDMDDB_UPD:
379 case ARM::VSTMDDB_UPD:
390 static bool isT1i32Load(unsigned Opc) {
391 return Opc == ARM::tLDRi || Opc == ARM::tLDRspi;
394 static bool isT2i32Load(unsigned Opc) {
395 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
398 static bool isi32Load(unsigned Opc) {
399 return Opc == ARM::LDRi12 || isT1i32Load(Opc) || isT2i32Load(Opc) ;
402 static bool isT1i32Store(unsigned Opc) {
403 return Opc == ARM::tSTRi || Opc == ARM::tSTRspi;
406 static bool isT2i32Store(unsigned Opc) {
407 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
410 static bool isi32Store(unsigned Opc) {
411 return Opc == ARM::STRi12 || isT1i32Store(Opc) || isT2i32Store(Opc);
414 static bool isLoadSingle(unsigned Opc) {
415 return isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
418 static unsigned getImmScale(unsigned Opc) {
420 default: llvm_unreachable("Unhandled opcode!");
435 static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
436 switch (MI->getOpcode()) {
463 case ARM::tLDMIA_UPD:
464 case ARM::tSTMIA_UPD:
471 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
474 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
478 /// Update future uses of the base register with the offset introduced
479 /// due to writeback. This function only works on Thumb1.
480 void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
481 MachineBasicBlock::iterator MBBI,
482 const DebugLoc &DL, unsigned Base,
484 ARMCC::CondCodes Pred,
486 assert(isThumb1 && "Can only update base register uses for Thumb1!");
487 // Start updating any instructions with immediate offsets. Insert a SUB before
488 // the first non-updateable instruction (if any).
489 for (; MBBI != MBB.end(); ++MBBI) {
490 bool InsertSub = false;
491 unsigned Opc = MBBI->getOpcode();
493 if (MBBI->readsRegister(Base)) {
496 Opc == ARM::tLDRi || Opc == ARM::tLDRHi || Opc == ARM::tLDRBi;
498 Opc == ARM::tSTRi || Opc == ARM::tSTRHi || Opc == ARM::tSTRBi;
500 if (IsLoad || IsStore) {
501 // Loads and stores with immediate offsets can be updated, but only if
502 // the new offset isn't negative.
503 // The MachineOperand containing the offset immediate is the last one
504 // before predicates.
506 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
507 // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
508 Offset = MO.getImm() - WordOffset * getImmScale(Opc);
510 // If storing the base register, it needs to be reset first.
511 unsigned InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
513 if (Offset >= 0 && !(IsStore && InstrSrcReg == Base))
517 } else if ((Opc == ARM::tSUBi8 || Opc == ARM::tADDi8) &&
518 !definesCPSR(*MBBI)) {
519 // SUBS/ADDS using this register, with a dead def of the CPSR.
520 // Merge it with the update; if the merged offset is too large,
521 // insert a new sub instead.
523 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
524 Offset = (Opc == ARM::tSUBi8) ?
525 MO.getImm() + WordOffset * 4 :
526 MO.getImm() - WordOffset * 4 ;
527 if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
528 // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
531 // The base register has now been reset, so exit early.
537 // Can't update the instruction.
540 } else if (definesCPSR(*MBBI) || MBBI->isCall() || MBBI->isBranch()) {
541 // Since SUBS sets the condition flags, we can't place the base reset
542 // after an instruction that has a live CPSR def.
543 // The base register might also contain an argument for a function call.
548 // An instruction above couldn't be updated, so insert a sub.
549 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
550 .add(t1CondCodeOp(true))
552 .addImm(WordOffset * 4)
558 if (MBBI->killsRegister(Base) || MBBI->definesRegister(Base))
559 // Register got killed. Stop updating.
563 // End of block was reached.
564 if (MBB.succ_size() > 0) {
565 // FIXME: Because of a bug, live registers are sometimes missing from
566 // the successor blocks' live-in sets. This means we can't trust that
567 // information and *always* have to reset at the end of a block.
569 if (MBBI != MBB.end()) --MBBI;
570 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
571 .add(t1CondCodeOp(true))
573 .addImm(WordOffset * 4)
579 /// Return the first register of class \p RegClass that is not in \p Regs.
580 unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
581 if (!RegClassInfoValid) {
582 RegClassInfo.runOnMachineFunction(*MF);
583 RegClassInfoValid = true;
586 for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
587 if (!LiveRegs.contains(Reg))
592 /// Compute live registers just before instruction \p Before (in normal schedule
593 /// direction). Computes backwards so multiple queries in the same block must
594 /// come in reverse order.
595 void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
596 MachineBasicBlock::const_iterator Before) {
597 // Initialize if we never queried in this block.
598 if (!LiveRegsValid) {
600 LiveRegs.addLiveOuts(MBB);
601 LiveRegPos = MBB.end();
602 LiveRegsValid = true;
604 // Move backward just before the "Before" position.
605 while (LiveRegPos != Before) {
607 LiveRegs.stepBackward(*LiveRegPos);
611 static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
613 for (const std::pair<unsigned, bool> &R : Regs)
619 /// Create and insert a LDM or STM with Base as base register and registers in
620 /// Regs as the register operands that would be loaded / stored. It returns
621 /// true if the transformation is done.
622 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(
623 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
624 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
625 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
626 ArrayRef<std::pair<unsigned, bool>> Regs) {
627 unsigned NumRegs = Regs.size();
630 // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
631 // Compute liveness information for that register to make the decision.
632 bool SafeToClobberCPSR = !isThumb1 ||
633 (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
634 MachineBasicBlock::LQR_Dead);
636 bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
638 // Exception: If the base register is in the input reglist, Thumb1 LDM is
640 // It's also not possible to merge an STR of the base register in Thumb1.
641 if (isThumb1 && ContainsReg(Regs, Base)) {
642 assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
643 if (Opcode == ARM::tLDRi)
645 else if (Opcode == ARM::tSTRi)
649 ARM_AM::AMSubMode Mode = ARM_AM::ia;
650 // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
651 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
652 bool haveIBAndDA = isNotVFP && !isThumb2 && !isThumb1;
654 if (Offset == 4 && haveIBAndDA) {
656 } else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) {
658 } else if (Offset == -4 * (int)NumRegs && isNotVFP && !isThumb1) {
659 // VLDM/VSTM do not support DB mode without also updating the base reg.
661 } else if (Offset != 0 || Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi) {
662 // Check if this is a supported opcode before inserting instructions to
663 // calculate a new base register.
664 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return nullptr;
666 // If starting offset isn't zero, insert a MI to materialize a new base.
667 // But only do so if it is cost effective, i.e. merging more than two
672 // On Thumb1, it's not worth materializing a new base register without
673 // clobbering the CPSR (i.e. not using ADDS/SUBS).
674 if (!SafeToClobberCPSR)
678 if (isi32Load(Opcode)) {
679 // If it is a load, then just use one of the destination registers
680 // as the new base. Will no longer be writeback in Thumb1.
681 NewBase = Regs[NumRegs-1].first;
684 // Find a free register that we can use as scratch register.
685 moveLiveRegsBefore(MBB, InsertBefore);
686 // The merged instruction does not exist yet but will use several Regs if
688 if (!isLoadSingle(Opcode))
689 for (const std::pair<unsigned, bool> &R : Regs)
690 LiveRegs.addReg(R.first);
692 NewBase = findFreeReg(isThumb1 ? ARM::tGPRRegClass : ARM::GPRRegClass);
698 isThumb2 ? ARM::t2ADDri :
699 (isThumb1 && Base == ARM::SP) ? ARM::tADDrSPi :
700 (isThumb1 && Offset < 8) ? ARM::tADDi3 :
701 isThumb1 ? ARM::tADDi8 : ARM::ADDri;
706 isThumb2 ? ARM::t2SUBri :
707 (isThumb1 && Offset < 8 && Base != ARM::SP) ? ARM::tSUBi3 :
708 isThumb1 ? ARM::tSUBi8 : ARM::SUBri;
711 if (!TL->isLegalAddImmediate(Offset))
712 // FIXME: Try add with register operand?
713 return nullptr; // Probably not worth it then.
715 // We can only append a kill flag to the add/sub input if the value is not
716 // used in the register list of the stm as well.
717 bool KillOldBase = BaseKill &&
718 (!isi32Store(Opcode) || !ContainsReg(Regs, Base));
721 // Thumb1: depending on immediate size, use either
722 // ADDS NewBase, Base, #imm3
725 // ADDS NewBase, #imm8.
726 if (Base != NewBase &&
727 (BaseOpc == ARM::tADDi8 || BaseOpc == ARM::tSUBi8)) {
728 // Need to insert a MOV to the new base first.
729 if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
731 // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
732 if (Pred != ARMCC::AL)
734 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
735 .addReg(Base, getKillRegState(KillOldBase));
737 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
738 .addReg(Base, getKillRegState(KillOldBase))
739 .add(predOps(Pred, PredReg));
741 // The following ADDS/SUBS becomes an update.
745 if (BaseOpc == ARM::tADDrSPi) {
746 assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
747 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
748 .addReg(Base, getKillRegState(KillOldBase))
750 .add(predOps(Pred, PredReg));
752 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
753 .add(t1CondCodeOp(true))
754 .addReg(Base, getKillRegState(KillOldBase))
756 .add(predOps(Pred, PredReg));
758 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
759 .addReg(Base, getKillRegState(KillOldBase))
761 .add(predOps(Pred, PredReg))
765 BaseKill = true; // New base is always killed straight away.
768 bool isDef = isLoadSingle(Opcode);
770 // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
771 // base register writeback.
772 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
776 // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
777 // - There is no writeback (LDM of base register),
778 // - the base register is killed by the merged instruction,
779 // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
780 // to reset the base register.
781 // Otherwise, don't merge.
782 // It's safe to return here since the code to materialize a new base register
783 // above is also conditional on SafeToClobberCPSR.
784 if (isThumb1 && !SafeToClobberCPSR && Writeback && !BaseKill)
787 MachineInstrBuilder MIB;
790 assert(isThumb1 && "expected Writeback only inThumb1");
791 if (Opcode == ARM::tLDMIA) {
792 assert(!(ContainsReg(Regs, Base)) && "Thumb1 can't LDM ! with Base in Regs");
793 // Update tLDMIA with writeback if necessary.
794 Opcode = ARM::tLDMIA_UPD;
797 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
799 // Thumb1: we might need to set base writeback when building the MI.
800 MIB.addReg(Base, getDefRegState(true))
801 .addReg(Base, getKillRegState(BaseKill));
803 // The base isn't dead after a merged instruction with writeback.
804 // Insert a sub instruction after the newly formed instruction to reset.
806 UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
808 // No writeback, simply build the MachineInstr.
809 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
810 MIB.addReg(Base, getKillRegState(BaseKill));
813 MIB.addImm(Pred).addReg(PredReg);
815 for (const std::pair<unsigned, bool> &R : Regs)
816 MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
818 return MIB.getInstr();
821 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(
822 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
823 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
824 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
825 ArrayRef<std::pair<unsigned, bool>> Regs) const {
826 bool IsLoad = isi32Load(Opcode);
827 assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
828 unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
830 assert(Regs.size() == 2);
831 MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
832 TII->get(LoadStoreOpcode));
834 MIB.addReg(Regs[0].first, RegState::Define)
835 .addReg(Regs[1].first, RegState::Define);
837 MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
838 .addReg(Regs[1].first, getKillRegState(Regs[1].second));
840 MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
841 return MIB.getInstr();
844 /// Call MergeOps and update MemOps and merges accordingly on success.
845 MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
846 const MachineInstr *First = Cand.Instrs.front();
847 unsigned Opcode = First->getOpcode();
848 bool IsLoad = isLoadSingle(Opcode);
849 SmallVector<std::pair<unsigned, bool>, 8> Regs;
850 SmallVector<unsigned, 4> ImpDefs;
851 DenseSet<unsigned> KilledRegs;
852 DenseSet<unsigned> UsedRegs;
853 // Determine list of registers and list of implicit super-register defs.
854 for (const MachineInstr *MI : Cand.Instrs) {
855 const MachineOperand &MO = getLoadStoreRegOp(*MI);
856 unsigned Reg = MO.getReg();
857 bool IsKill = MO.isKill();
859 KilledRegs.insert(Reg);
860 Regs.push_back(std::make_pair(Reg, IsKill));
861 UsedRegs.insert(Reg);
864 // Collect any implicit defs of super-registers, after merging we can't
865 // be sure anymore that we properly preserved these live ranges and must
866 // removed these implicit operands.
867 for (const MachineOperand &MO : MI->implicit_operands()) {
868 if (!MO.isReg() || !MO.isDef() || MO.isDead())
870 assert(MO.isImplicit());
871 unsigned DefReg = MO.getReg();
873 if (is_contained(ImpDefs, DefReg))
875 // We can ignore cases where the super-reg is read and written.
876 if (MI->readsRegister(DefReg))
878 ImpDefs.push_back(DefReg);
883 // Attempt the merge.
884 using iterator = MachineBasicBlock::iterator;
886 MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
887 iterator InsertBefore = std::next(iterator(LatestMI));
888 MachineBasicBlock &MBB = *LatestMI->getParent();
889 unsigned Offset = getMemoryOpOffset(*First);
890 unsigned Base = getLoadStoreBaseOp(*First).getReg();
891 bool BaseKill = LatestMI->killsRegister(Base);
892 unsigned PredReg = 0;
893 ARMCC::CondCodes Pred = getInstrPredicate(*First, PredReg);
894 DebugLoc DL = First->getDebugLoc();
895 MachineInstr *Merged = nullptr;
896 if (Cand.CanMergeToLSDouble)
897 Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
898 Opcode, Pred, PredReg, DL, Regs);
899 if (!Merged && Cand.CanMergeToLSMulti)
900 Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
901 Opcode, Pred, PredReg, DL, Regs);
905 // Determine earliest instruction that will get removed. We then keep an
906 // iterator just above it so the following erases don't invalidated it.
907 iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
908 bool EarliestAtBegin = false;
909 if (EarliestI == MBB.begin()) {
910 EarliestAtBegin = true;
912 EarliestI = std::prev(EarliestI);
915 // Remove instructions which have been merged.
916 for (MachineInstr *MI : Cand.Instrs)
919 // Determine range between the earliest removed instruction and the new one.
921 EarliestI = MBB.begin();
923 EarliestI = std::next(EarliestI);
924 auto FixupRange = make_range(EarliestI, iterator(Merged));
926 if (isLoadSingle(Opcode)) {
927 // If the previous loads defined a super-reg, then we have to mark earlier
928 // operands undef; Replicate the super-reg def on the merged instruction.
929 for (MachineInstr &MI : FixupRange) {
930 for (unsigned &ImpDefReg : ImpDefs) {
931 for (MachineOperand &MO : MI.implicit_operands()) {
932 if (!MO.isReg() || MO.getReg() != ImpDefReg)
942 MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
943 for (unsigned ImpDef : ImpDefs)
944 MIB.addReg(ImpDef, RegState::ImplicitDefine);
946 // Remove kill flags: We are possibly storing the values later now.
947 assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
948 for (MachineInstr &MI : FixupRange) {
949 for (MachineOperand &MO : MI.uses()) {
950 if (!MO.isReg() || !MO.isKill())
952 if (UsedRegs.count(MO.getReg()))
956 assert(ImpDefs.empty());
962 static bool isValidLSDoubleOffset(int Offset) {
963 unsigned Value = abs(Offset);
964 // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
966 return (Value % 4) == 0 && Value < 1024;
969 /// Return true for loads/stores that can be combined to a double/multi
970 /// operation without increasing the requirements for alignment.
971 static bool mayCombineMisaligned(const TargetSubtargetInfo &STI,
972 const MachineInstr &MI) {
973 // vldr/vstr trap on misaligned pointers anyway, forming vldm makes no
975 unsigned Opcode = MI.getOpcode();
976 if (!isi32Load(Opcode) && !isi32Store(Opcode))
979 // Stack pointer alignment is out of the programmers control so we can trust
980 // SP-relative loads/stores.
981 if (getLoadStoreBaseOp(MI).getReg() == ARM::SP &&
982 STI.getFrameLowering()->getTransientStackAlignment() >= 4)
987 /// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
988 void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
989 const MachineInstr *FirstMI = MemOps[0].MI;
990 unsigned Opcode = FirstMI->getOpcode();
991 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
992 unsigned Size = getLSMultipleTransferSize(FirstMI);
995 unsigned EIndex = MemOps.size();
997 // Look at the first instruction.
998 const MachineInstr *MI = MemOps[SIndex].MI;
999 int Offset = MemOps[SIndex].Offset;
1000 const MachineOperand &PMO = getLoadStoreRegOp(*MI);
1001 unsigned PReg = PMO.getReg();
1002 unsigned PRegNum = PMO.isUndef() ? std::numeric_limits<unsigned>::max()
1003 : TRI->getEncodingValue(PReg);
1004 unsigned Latest = SIndex;
1005 unsigned Earliest = SIndex;
1007 bool CanMergeToLSDouble =
1008 STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
1009 // ARM errata 602117: LDRD with base in list may result in incorrect base
1010 // register when interrupted or faulted.
1011 if (STI->isCortexM3() && isi32Load(Opcode) &&
1012 PReg == getLoadStoreBaseOp(*MI).getReg())
1013 CanMergeToLSDouble = false;
1015 bool CanMergeToLSMulti = true;
1016 // On swift vldm/vstm starting with an odd register number as that needs
1017 // more uops than single vldrs.
1018 if (STI->hasSlowOddRegister() && !isNotVFP && (PRegNum % 2) == 1)
1019 CanMergeToLSMulti = false;
1021 // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
1022 // deprecated; LDM to PC is fine but cannot happen here.
1023 if (PReg == ARM::SP || PReg == ARM::PC)
1024 CanMergeToLSMulti = CanMergeToLSDouble = false;
1026 // Should we be conservative?
1027 if (AssumeMisalignedLoadStores && !mayCombineMisaligned(*STI, *MI))
1028 CanMergeToLSMulti = CanMergeToLSDouble = false;
1030 // Merge following instructions where possible.
1031 for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
1032 int NewOffset = MemOps[I].Offset;
1033 if (NewOffset != Offset + (int)Size)
1035 const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
1036 unsigned Reg = MO.getReg();
1037 if (Reg == ARM::SP || Reg == ARM::PC)
1040 // See if the current load/store may be part of a multi load/store.
1041 unsigned RegNum = MO.isUndef() ? std::numeric_limits<unsigned>::max()
1042 : TRI->getEncodingValue(Reg);
1043 bool PartOfLSMulti = CanMergeToLSMulti;
1044 if (PartOfLSMulti) {
1045 // Register numbers must be in ascending order.
1046 if (RegNum <= PRegNum)
1047 PartOfLSMulti = false;
1048 // For VFP / NEON load/store multiples, the registers must be
1049 // consecutive and within the limit on the number of registers per
1051 else if (!isNotVFP && RegNum != PRegNum+1)
1052 PartOfLSMulti = false;
1054 // See if the current load/store may be part of a double load/store.
1055 bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
1057 if (!PartOfLSMulti && !PartOfLSDouble)
1059 CanMergeToLSMulti &= PartOfLSMulti;
1060 CanMergeToLSDouble &= PartOfLSDouble;
1061 // Track MemOp with latest and earliest position (Positions are
1062 // counted in reverse).
1063 unsigned Position = MemOps[I].Position;
1064 if (Position < MemOps[Latest].Position)
1066 else if (Position > MemOps[Earliest].Position)
1068 // Prepare for next MemOp.
1073 // Form a candidate from the Ops collected so far.
1074 MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
1075 for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
1076 Candidate->Instrs.push_back(MemOps[C].MI);
1077 Candidate->LatestMIIdx = Latest - SIndex;
1078 Candidate->EarliestMIIdx = Earliest - SIndex;
1079 Candidate->InsertPos = MemOps[Latest].Position;
1081 CanMergeToLSMulti = CanMergeToLSDouble = false;
1082 Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
1083 Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
1084 Candidates.push_back(Candidate);
1085 // Continue after the chain.
1087 } while (SIndex < EIndex);
1090 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1091 ARM_AM::AMSubMode Mode) {
1093 default: llvm_unreachable("Unhandled opcode!");
1099 default: llvm_unreachable("Unhandled submode!");
1100 case ARM_AM::ia: return ARM::LDMIA_UPD;
1101 case ARM_AM::ib: return ARM::LDMIB_UPD;
1102 case ARM_AM::da: return ARM::LDMDA_UPD;
1103 case ARM_AM::db: return ARM::LDMDB_UPD;
1110 default: llvm_unreachable("Unhandled submode!");
1111 case ARM_AM::ia: return ARM::STMIA_UPD;
1112 case ARM_AM::ib: return ARM::STMIB_UPD;
1113 case ARM_AM::da: return ARM::STMDA_UPD;
1114 case ARM_AM::db: return ARM::STMDB_UPD;
1119 default: llvm_unreachable("Unhandled submode!");
1120 case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1121 case ARM_AM::db: return ARM::t2LDMDB_UPD;
1126 default: llvm_unreachable("Unhandled submode!");
1127 case ARM_AM::ia: return ARM::t2STMIA_UPD;
1128 case ARM_AM::db: return ARM::t2STMDB_UPD;
1132 default: llvm_unreachable("Unhandled submode!");
1133 case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1134 case ARM_AM::db: return ARM::VLDMSDB_UPD;
1138 default: llvm_unreachable("Unhandled submode!");
1139 case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1140 case ARM_AM::db: return ARM::VLDMDDB_UPD;
1144 default: llvm_unreachable("Unhandled submode!");
1145 case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1146 case ARM_AM::db: return ARM::VSTMSDB_UPD;
1150 default: llvm_unreachable("Unhandled submode!");
1151 case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1152 case ARM_AM::db: return ARM::VSTMDDB_UPD;
1157 /// Check if the given instruction increments or decrements a register and
1158 /// return the amount it is incremented/decremented. Returns 0 if the CPSR flags
1159 /// generated by the instruction are possibly read as well.
1160 static int isIncrementOrDecrement(const MachineInstr &MI, unsigned Reg,
1161 ARMCC::CondCodes Pred, unsigned PredReg) {
1164 switch (MI.getOpcode()) {
1165 case ARM::tADDi8: Scale = 4; CheckCPSRDef = true; break;
1166 case ARM::tSUBi8: Scale = -4; CheckCPSRDef = true; break;
1168 case ARM::SUBri: Scale = -1; CheckCPSRDef = true; break;
1170 case ARM::ADDri: Scale = 1; CheckCPSRDef = true; break;
1171 case ARM::tADDspi: Scale = 4; CheckCPSRDef = false; break;
1172 case ARM::tSUBspi: Scale = -4; CheckCPSRDef = false; break;
1177 if (MI.getOperand(0).getReg() != Reg ||
1178 MI.getOperand(1).getReg() != Reg ||
1179 getInstrPredicate(MI, MIPredReg) != Pred ||
1180 MIPredReg != PredReg)
1183 if (CheckCPSRDef && definesCPSR(MI))
1185 return MI.getOperand(2).getImm() * Scale;
1188 /// Searches for an increment or decrement of \p Reg before \p MBBI.
1189 static MachineBasicBlock::iterator
1190 findIncDecBefore(MachineBasicBlock::iterator MBBI, unsigned Reg,
1191 ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1193 MachineBasicBlock &MBB = *MBBI->getParent();
1194 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1195 MachineBasicBlock::iterator EndMBBI = MBB.end();
1196 if (MBBI == BeginMBBI)
1199 // Skip debug values.
1200 MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1201 while (PrevMBBI->isDebugValue() && PrevMBBI != BeginMBBI)
1204 Offset = isIncrementOrDecrement(*PrevMBBI, Reg, Pred, PredReg);
1205 return Offset == 0 ? EndMBBI : PrevMBBI;
1208 /// Searches for a increment or decrement of \p Reg after \p MBBI.
1209 static MachineBasicBlock::iterator
1210 findIncDecAfter(MachineBasicBlock::iterator MBBI, unsigned Reg,
1211 ARMCC::CondCodes Pred, unsigned PredReg, int &Offset) {
1213 MachineBasicBlock &MBB = *MBBI->getParent();
1214 MachineBasicBlock::iterator EndMBBI = MBB.end();
1215 MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1216 // Skip debug values.
1217 while (NextMBBI != EndMBBI && NextMBBI->isDebugValue())
1219 if (NextMBBI == EndMBBI)
1222 Offset = isIncrementOrDecrement(*NextMBBI, Reg, Pred, PredReg);
1223 return Offset == 0 ? EndMBBI : NextMBBI;
1226 /// Fold proceeding/trailing inc/dec of base register into the
1227 /// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
1229 /// stmia rn, <ra, rb, rc>
1230 /// rn := rn + 4 * 3;
1232 /// stmia rn!, <ra, rb, rc>
1234 /// rn := rn - 4 * 3;
1235 /// ldmia rn, <ra, rb, rc>
1237 /// ldmdb rn!, <ra, rb, rc>
1238 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
1239 // Thumb1 is already using updating loads/stores.
1240 if (isThumb1) return false;
1242 const MachineOperand &BaseOP = MI->getOperand(0);
1243 unsigned Base = BaseOP.getReg();
1244 bool BaseKill = BaseOP.isKill();
1245 unsigned PredReg = 0;
1246 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1247 unsigned Opcode = MI->getOpcode();
1248 DebugLoc DL = MI->getDebugLoc();
1250 // Can't use an updating ld/st if the base register is also a dest
1251 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
1252 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1253 if (MI->getOperand(i).getReg() == Base)
1256 int Bytes = getLSMultipleTransferSize(MI);
1257 MachineBasicBlock &MBB = *MI->getParent();
1258 MachineBasicBlock::iterator MBBI(MI);
1260 MachineBasicBlock::iterator MergeInstr
1261 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1262 ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1263 if (Mode == ARM_AM::ia && Offset == -Bytes) {
1265 } else if (Mode == ARM_AM::ib && Offset == -Bytes) {
1268 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1269 if (((Mode != ARM_AM::ia && Mode != ARM_AM::ib) || Offset != Bytes) &&
1270 ((Mode != ARM_AM::da && Mode != ARM_AM::db) || Offset != -Bytes)) {
1272 // We couldn't find an inc/dec to merge. But if the base is dead, we
1273 // can still change to a writeback form as that will save us 2 bytes
1274 // of code size. It can create WAW hazards though, so only do it if
1275 // we're minimizing code size.
1276 if (!MBB.getParent()->getFunction().optForMinSize() || !BaseKill)
1279 bool HighRegsUsed = false;
1280 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1281 if (MI->getOperand(i).getReg() >= ARM::R8) {
1282 HighRegsUsed = true;
1287 MergeInstr = MBB.end();
1292 if (MergeInstr != MBB.end())
1293 MBB.erase(MergeInstr);
1295 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
1296 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1297 .addReg(Base, getDefRegState(true)) // WB base register
1298 .addReg(Base, getKillRegState(BaseKill))
1299 .addImm(Pred).addReg(PredReg);
1301 // Transfer the rest of operands.
1302 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
1303 MIB.add(MI->getOperand(OpNum));
1305 // Transfer memoperands.
1306 MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
1312 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1313 ARM_AM::AddrOpc Mode) {
1316 return ARM::LDR_PRE_IMM;
1318 return ARM::STR_PRE_IMM;
1320 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1322 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1324 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1326 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1329 return ARM::t2LDR_PRE;
1332 return ARM::t2STR_PRE;
1333 default: llvm_unreachable("Unhandled opcode!");
1337 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1338 ARM_AM::AddrOpc Mode) {
1341 return ARM::LDR_POST_IMM;
1343 return ARM::STR_POST_IMM;
1345 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1347 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1349 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1351 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1354 return ARM::t2LDR_POST;
1357 return ARM::t2STR_POST;
1358 default: llvm_unreachable("Unhandled opcode!");
1362 /// Fold proceeding/trailing inc/dec of base register into the
1363 /// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
1364 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
1365 // Thumb1 doesn't have updating LDR/STR.
1366 // FIXME: Use LDM/STM with single register instead.
1367 if (isThumb1) return false;
1369 unsigned Base = getLoadStoreBaseOp(*MI).getReg();
1370 bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
1371 unsigned Opcode = MI->getOpcode();
1372 DebugLoc DL = MI->getDebugLoc();
1373 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
1374 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
1375 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
1376 if (isi32Load(Opcode) || isi32Store(Opcode))
1377 if (MI->getOperand(2).getImm() != 0)
1379 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
1382 // Can't do the merge if the destination register is the same as the would-be
1383 // writeback register.
1384 if (MI->getOperand(0).getReg() == Base)
1387 unsigned PredReg = 0;
1388 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1389 int Bytes = getLSMultipleTransferSize(MI);
1390 MachineBasicBlock &MBB = *MI->getParent();
1391 MachineBasicBlock::iterator MBBI(MI);
1393 MachineBasicBlock::iterator MergeInstr
1394 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1396 if (!isAM5 && Offset == Bytes) {
1397 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1398 } else if (Offset == -Bytes) {
1399 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1401 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1402 if (Offset == Bytes) {
1403 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1404 } else if (!isAM5 && Offset == -Bytes) {
1405 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1409 MBB.erase(MergeInstr);
1411 ARM_AM::AddrOpc AddSub = Offset < 0 ? ARM_AM::sub : ARM_AM::add;
1413 bool isLd = isLoadSingle(Opcode);
1415 // VLDM[SD]_UPD, VSTM[SD]_UPD
1416 // (There are no base-updating versions of VLDR/VSTR instructions, but the
1417 // updating load/store-multiple instructions can be used with only one
1419 MachineOperand &MO = MI->getOperand(0);
1420 BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1421 .addReg(Base, getDefRegState(true)) // WB base register
1422 .addReg(Base, getKillRegState(isLd ? BaseKill : false))
1423 .addImm(Pred).addReg(PredReg)
1424 .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
1425 getKillRegState(MO.isKill())));
1428 // LDR_PRE, LDR_POST
1429 if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
1430 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1431 .addReg(Base, RegState::Define)
1432 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
1434 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1435 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1436 .addReg(Base, RegState::Define)
1440 .add(predOps(Pred, PredReg));
1443 // t2LDR_PRE, t2LDR_POST
1444 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1445 .addReg(Base, RegState::Define)
1448 .add(predOps(Pred, PredReg));
1451 MachineOperand &MO = MI->getOperand(0);
1452 // FIXME: post-indexed stores use am2offset_imm, which still encodes
1453 // the vestigal zero-reg offset register. When that's fixed, this clause
1454 // can be removed entirely.
1455 if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
1456 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1457 // STR_PRE, STR_POST
1458 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1459 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1463 .add(predOps(Pred, PredReg));
1465 // t2STR_PRE, t2STR_POST
1466 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1467 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1470 .add(predOps(Pred, PredReg));
1478 bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const {
1479 unsigned Opcode = MI.getOpcode();
1480 assert((Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) &&
1481 "Must have t2STRDi8 or t2LDRDi8");
1482 if (MI.getOperand(3).getImm() != 0)
1485 // Behaviour for writeback is undefined if base register is the same as one
1487 const MachineOperand &BaseOp = MI.getOperand(2);
1488 unsigned Base = BaseOp.getReg();
1489 const MachineOperand &Reg0Op = MI.getOperand(0);
1490 const MachineOperand &Reg1Op = MI.getOperand(1);
1491 if (Reg0Op.getReg() == Base || Reg1Op.getReg() == Base)
1495 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1496 MachineBasicBlock::iterator MBBI(MI);
1497 MachineBasicBlock &MBB = *MI.getParent();
1499 MachineBasicBlock::iterator MergeInstr = findIncDecBefore(MBBI, Base, Pred,
1502 if (Offset == 8 || Offset == -8) {
1503 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_PRE : ARM::t2STRD_PRE;
1505 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1506 if (Offset == 8 || Offset == -8) {
1507 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_POST : ARM::t2STRD_POST;
1511 MBB.erase(MergeInstr);
1513 DebugLoc DL = MI.getDebugLoc();
1514 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc));
1515 if (NewOpc == ARM::t2LDRD_PRE || NewOpc == ARM::t2LDRD_POST) {
1516 MIB.add(Reg0Op).add(Reg1Op).addReg(BaseOp.getReg(), RegState::Define);
1518 assert(NewOpc == ARM::t2STRD_PRE || NewOpc == ARM::t2STRD_POST);
1519 MIB.addReg(BaseOp.getReg(), RegState::Define).add(Reg0Op).add(Reg1Op);
1521 MIB.addReg(BaseOp.getReg(), RegState::Kill)
1522 .addImm(Offset).addImm(Pred).addReg(PredReg);
1523 assert(TII->get(Opcode).getNumOperands() == 6 &&
1524 TII->get(NewOpc).getNumOperands() == 7 &&
1525 "Unexpected number of operands in Opcode specification.");
1527 // Transfer implicit operands.
1528 for (const MachineOperand &MO : MI.implicit_operands())
1530 MIB->setMemRefs(MI.memoperands_begin(), MI.memoperands_end());
1536 /// Returns true if instruction is a memory operation that this pass is capable
1537 /// of operating on.
1538 static bool isMemoryOp(const MachineInstr &MI) {
1539 unsigned Opcode = MI.getOpcode();
1559 if (!MI.getOperand(1).isReg())
1562 // When no memory operands are present, conservatively assume unaligned,
1563 // volatile, unfoldable.
1564 if (!MI.hasOneMemOperand())
1567 const MachineMemOperand &MMO = **MI.memoperands_begin();
1569 // Don't touch volatile memory accesses - we may be changing their order.
1570 if (MMO.isVolatile())
1573 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1575 if (MMO.getAlignment() < 4)
1578 // str <undef> could probably be eliminated entirely, but for now we just want
1579 // to avoid making a mess of it.
1580 // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1581 if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())
1584 // Likewise don't mess with references to undefined addresses.
1585 if (MI.getOperand(1).isUndef())
1591 static void InsertLDR_STR(MachineBasicBlock &MBB,
1592 MachineBasicBlock::iterator &MBBI, int Offset,
1593 bool isDef, unsigned NewOpc, unsigned Reg,
1594 bool RegDeadKill, bool RegUndef, unsigned BaseReg,
1595 bool BaseKill, bool BaseUndef, ARMCC::CondCodes Pred,
1596 unsigned PredReg, const TargetInstrInfo *TII) {
1598 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1600 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1601 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1602 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1604 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1606 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1607 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1608 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1612 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1613 MachineBasicBlock::iterator &MBBI) {
1614 MachineInstr *MI = &*MBBI;
1615 unsigned Opcode = MI->getOpcode();
1616 // FIXME: Code/comments below check Opcode == t2STRDi8, but this check returns
1617 // if we see this opcode.
1618 if (Opcode != ARM::LDRD && Opcode != ARM::STRD && Opcode != ARM::t2LDRDi8)
1621 const MachineOperand &BaseOp = MI->getOperand(2);
1622 unsigned BaseReg = BaseOp.getReg();
1623 unsigned EvenReg = MI->getOperand(0).getReg();
1624 unsigned OddReg = MI->getOperand(1).getReg();
1625 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1626 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false);
1628 // ARM errata 602117: LDRD with base in list may result in incorrect base
1629 // register when interrupted or faulted.
1630 bool Errata602117 = EvenReg == BaseReg &&
1631 (Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8) && STI->isCortexM3();
1632 // ARM LDRD/STRD needs consecutive registers.
1633 bool NonConsecutiveRegs = (Opcode == ARM::LDRD || Opcode == ARM::STRD) &&
1634 (EvenRegNum % 2 != 0 || EvenRegNum + 1 != OddRegNum);
1636 if (!Errata602117 && !NonConsecutiveRegs)
1639 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1640 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1641 bool EvenDeadKill = isLd ?
1642 MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1643 bool EvenUndef = MI->getOperand(0).isUndef();
1644 bool OddDeadKill = isLd ?
1645 MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1646 bool OddUndef = MI->getOperand(1).isUndef();
1647 bool BaseKill = BaseOp.isKill();
1648 bool BaseUndef = BaseOp.isUndef();
1649 assert((isT2 || MI->getOperand(3).getReg() == ARM::NoRegister) &&
1650 "register offset not handled below");
1651 int OffImm = getMemoryOpOffset(*MI);
1652 unsigned PredReg = 0;
1653 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1655 if (OddRegNum > EvenRegNum && OffImm == 0) {
1656 // Ascending register numbers and no offset. It's safe to change it to a
1658 unsigned NewOpc = (isLd)
1659 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1660 : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1662 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1663 .addReg(BaseReg, getKillRegState(BaseKill))
1664 .addImm(Pred).addReg(PredReg)
1665 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1666 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill));
1669 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1670 .addReg(BaseReg, getKillRegState(BaseKill))
1671 .addImm(Pred).addReg(PredReg)
1673 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1675 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef));
1679 // Split into two instructions.
1680 unsigned NewOpc = (isLd)
1681 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1682 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1683 // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1684 // so adjust and use t2LDRi12 here for that.
1685 unsigned NewOpc2 = (isLd)
1686 ? (isT2 ? (OffImm+4 < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1687 : (isT2 ? (OffImm+4 < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1688 // If this is a load, make sure the first load does not clobber the base
1689 // register before the second load reads it.
1690 if (isLd && TRI->regsOverlap(EvenReg, BaseReg)) {
1691 assert(!TRI->regsOverlap(OddReg, BaseReg));
1692 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1693 false, BaseReg, false, BaseUndef, Pred, PredReg, TII);
1694 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1695 false, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII);
1697 if (OddReg == EvenReg && EvenDeadKill) {
1698 // If the two source operands are the same, the kill marker is
1699 // probably on the first one. e.g.
1700 // t2STRDi8 killed %r5, %r5, killed %r9, 0, 14, %reg0
1701 EvenDeadKill = false;
1704 // Never kill the base register in the first instruction.
1705 if (EvenReg == BaseReg)
1706 EvenDeadKill = false;
1707 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1708 EvenUndef, BaseReg, false, BaseUndef, Pred, PredReg, TII);
1709 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1710 OddUndef, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII);
1718 MBBI = MBB.erase(MBBI);
1722 /// An optimization pass to turn multiple LDR / STR ops of the same base and
1723 /// incrementing offset into LDM / STM ops.
1724 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1726 unsigned CurrBase = 0;
1727 unsigned CurrOpc = ~0u;
1728 ARMCC::CondCodes CurrPred = ARMCC::AL;
1729 unsigned Position = 0;
1730 assert(Candidates.size() == 0);
1731 assert(MergeBaseCandidates.size() == 0);
1732 LiveRegsValid = false;
1734 for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1736 // The instruction in front of the iterator is the one we look at.
1737 MBBI = std::prev(I);
1738 if (FixInvalidRegPairOp(MBB, MBBI))
1742 if (isMemoryOp(*MBBI)) {
1743 unsigned Opcode = MBBI->getOpcode();
1744 const MachineOperand &MO = MBBI->getOperand(0);
1745 unsigned Reg = MO.getReg();
1746 unsigned Base = getLoadStoreBaseOp(*MBBI).getReg();
1747 unsigned PredReg = 0;
1748 ARMCC::CondCodes Pred = getInstrPredicate(*MBBI, PredReg);
1749 int Offset = getMemoryOpOffset(*MBBI);
1750 if (CurrBase == 0) {
1751 // Start of a new chain.
1755 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1758 // Note: No need to match PredReg in the next if.
1759 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1761 // r4 := ldr [r0, #8]
1762 // r4 := ldr [r0, #4]
1765 // If a load overrides the base register or a register loaded by
1766 // another load in our chain, we cannot take this instruction.
1767 bool Overlap = false;
1768 if (isLoadSingle(Opcode)) {
1769 Overlap = (Base == Reg);
1771 for (const MemOpQueueEntry &E : MemOps) {
1772 if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1781 // Check offset and sort memory operation into the current chain.
1782 if (Offset > MemOps.back().Offset) {
1783 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1786 MemOpQueue::iterator MI, ME;
1787 for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; ++MI) {
1788 if (Offset < MI->Offset) {
1789 // Found a place to insert.
1792 if (Offset == MI->Offset) {
1793 // Collision, abort.
1798 if (MI != MemOps.end()) {
1799 MemOps.insert(MI, MemOpQueueEntry(*MBBI, Offset, Position));
1806 // Don't advance the iterator; The op will start a new chain next.
1809 // Fallthrough to look into existing chain.
1810 } else if (MBBI->isDebugValue()) {
1812 } else if (MBBI->getOpcode() == ARM::t2LDRDi8 ||
1813 MBBI->getOpcode() == ARM::t2STRDi8) {
1814 // ARMPreAllocLoadStoreOpt has already formed some LDRD/STRD instructions
1815 // remember them because we may still be able to merge add/sub into them.
1816 MergeBaseCandidates.push_back(&*MBBI);
1819 // If we are here then the chain is broken; Extract candidates for a merge.
1820 if (MemOps.size() > 0) {
1821 FormCandidates(MemOps);
1822 // Reset for the next chain.
1825 CurrPred = ARMCC::AL;
1829 if (MemOps.size() > 0)
1830 FormCandidates(MemOps);
1832 // Sort candidates so they get processed from end to begin of the basic
1833 // block later; This is necessary for liveness calculation.
1834 auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1835 return M0->InsertPos < M1->InsertPos;
1837 std::sort(Candidates.begin(), Candidates.end(), LessThan);
1839 // Go through list of candidates and merge.
1840 bool Changed = false;
1841 for (const MergeCandidate *Candidate : Candidates) {
1842 if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
1843 MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1844 // Merge preceding/trailing base inc/dec into the merged op.
1847 unsigned Opcode = Merged->getOpcode();
1848 if (Opcode == ARM::t2STRDi8 || Opcode == ARM::t2LDRDi8)
1849 MergeBaseUpdateLSDouble(*Merged);
1851 MergeBaseUpdateLSMultiple(Merged);
1853 for (MachineInstr *MI : Candidate->Instrs) {
1854 if (MergeBaseUpdateLoadStore(MI))
1859 assert(Candidate->Instrs.size() == 1);
1860 if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1865 // Try to fold add/sub into the LDRD/STRD formed by ARMPreAllocLoadStoreOpt.
1866 for (MachineInstr *MI : MergeBaseCandidates)
1867 MergeBaseUpdateLSDouble(*MI);
1868 MergeBaseCandidates.clear();
1873 /// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
1874 /// into the preceding stack restore so it directly restore the value of LR
1876 /// ldmfd sp!, {..., lr}
1879 /// ldmfd sp!, {..., lr}
1882 /// ldmfd sp!, {..., pc}
1883 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1884 // Thumb1 LDM doesn't allow high registers.
1885 if (isThumb1) return false;
1886 if (MBB.empty()) return false;
1888 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1889 if (MBBI != MBB.begin() && MBBI != MBB.end() &&
1890 (MBBI->getOpcode() == ARM::BX_RET ||
1891 MBBI->getOpcode() == ARM::tBX_RET ||
1892 MBBI->getOpcode() == ARM::MOVPCLR)) {
1893 MachineBasicBlock::iterator PrevI = std::prev(MBBI);
1894 // Ignore any DBG_VALUE instructions.
1895 while (PrevI->isDebugValue() && PrevI != MBB.begin())
1897 MachineInstr &PrevMI = *PrevI;
1898 unsigned Opcode = PrevMI.getOpcode();
1899 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1900 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1901 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
1902 MachineOperand &MO = PrevMI.getOperand(PrevMI.getNumOperands() - 1);
1903 if (MO.getReg() != ARM::LR)
1905 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1906 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1907 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1908 PrevMI.setDesc(TII->get(NewOpc));
1910 PrevMI.copyImplicitOps(*MBB.getParent(), *MBBI);
1912 // We now restore LR into PC so it is not live-out of the return block
1913 // anymore: Clear the CSI Restored bit.
1914 MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
1915 // CSI should be fixed after PrologEpilog Insertion
1916 assert(MFI.isCalleeSavedInfoValid() && "CSI should be valid");
1917 for (CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
1918 if (Info.getReg() == ARM::LR) {
1919 Info.setRestored(false);
1929 bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) {
1930 MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
1931 if (MBBI == MBB.begin() || MBBI == MBB.end() ||
1932 MBBI->getOpcode() != ARM::tBX_RET)
1935 MachineBasicBlock::iterator Prev = MBBI;
1937 if (Prev->getOpcode() != ARM::tMOVr || !Prev->definesRegister(ARM::LR))
1940 for (auto Use : Prev->uses())
1942 assert(STI->hasV4TOps());
1943 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(ARM::tBX))
1944 .addReg(Use.getReg(), RegState::Kill)
1945 .add(predOps(ARMCC::AL))
1946 .copyImplicitOps(*MBBI);
1952 llvm_unreachable("tMOVr doesn't kill a reg before tBX_RET?");
1955 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
1956 if (skipFunction(Fn.getFunction()))
1960 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
1961 TL = STI->getTargetLowering();
1962 AFI = Fn.getInfo<ARMFunctionInfo>();
1963 TII = STI->getInstrInfo();
1964 TRI = STI->getRegisterInfo();
1966 RegClassInfoValid = false;
1967 isThumb2 = AFI->isThumb2Function();
1968 isThumb1 = AFI->isThumbFunction() && !isThumb2;
1970 bool Modified = false;
1971 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
1973 MachineBasicBlock &MBB = *MFI;
1974 Modified |= LoadStoreMultipleOpti(MBB);
1975 if (STI->hasV5TOps())
1976 Modified |= MergeReturnIntoLDM(MBB);
1978 Modified |= CombineMovBx(MBB);
1981 Allocator.DestroyAll();
1985 #define ARM_PREALLOC_LOAD_STORE_OPT_NAME \
1986 "ARM pre- register allocation load / store optimization pass"
1990 /// Pre- register allocation pass that move load / stores from consecutive
1991 /// locations close to make it more likely they will be combined later.
1992 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
1996 const DataLayout *TD;
1997 const TargetInstrInfo *TII;
1998 const TargetRegisterInfo *TRI;
1999 const ARMSubtarget *STI;
2000 MachineRegisterInfo *MRI;
2001 MachineFunction *MF;
2003 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
2005 bool runOnMachineFunction(MachineFunction &Fn) override;
2007 StringRef getPassName() const override {
2008 return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
2011 void getAnalysisUsage(AnalysisUsage &AU) const override {
2012 AU.addRequired<AAResultsWrapperPass>();
2013 MachineFunctionPass::getAnalysisUsage(AU);
2017 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
2018 unsigned &NewOpc, unsigned &EvenReg,
2019 unsigned &OddReg, unsigned &BaseReg,
2021 unsigned &PredReg, ARMCC::CondCodes &Pred,
2023 bool RescheduleOps(MachineBasicBlock *MBB,
2024 SmallVectorImpl<MachineInstr *> &Ops,
2025 unsigned Base, bool isLd,
2026 DenseMap<MachineInstr*, unsigned> &MI2LocMap);
2027 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
2030 } // end anonymous namespace
2032 char ARMPreAllocLoadStoreOpt::ID = 0;
2034 INITIALIZE_PASS(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2035 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2037 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2038 if (AssumeMisalignedLoadStores || skipFunction(Fn.getFunction()))
2041 TD = &Fn.getDataLayout();
2042 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2043 TII = STI->getInstrInfo();
2044 TRI = STI->getRegisterInfo();
2045 MRI = &Fn.getRegInfo();
2047 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2049 bool Modified = false;
2050 for (MachineBasicBlock &MFI : Fn)
2051 Modified |= RescheduleLoadStoreInstrs(&MFI);
2056 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
2057 MachineBasicBlock::iterator I,
2058 MachineBasicBlock::iterator E,
2059 SmallPtrSetImpl<MachineInstr*> &MemOps,
2060 SmallSet<unsigned, 4> &MemRegs,
2061 const TargetRegisterInfo *TRI,
2062 AliasAnalysis *AA) {
2063 // Are there stores / loads / calls between them?
2064 SmallSet<unsigned, 4> AddedRegPressure;
2066 if (I->isDebugValue() || MemOps.count(&*I))
2068 if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
2070 if (I->mayStore() || (!isLd && I->mayLoad()))
2071 for (MachineInstr *MemOp : MemOps)
2072 if (I->mayAlias(AA, *MemOp, /*UseTBAA*/ false))
2074 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
2075 MachineOperand &MO = I->getOperand(j);
2078 unsigned Reg = MO.getReg();
2079 if (MO.isDef() && TRI->regsOverlap(Reg, Base))
2081 if (Reg != Base && !MemRegs.count(Reg))
2082 AddedRegPressure.insert(Reg);
2086 // Estimate register pressure increase due to the transformation.
2087 if (MemRegs.size() <= 4)
2088 // Ok if we are moving small number of instructions.
2090 return AddedRegPressure.size() <= MemRegs.size() * 2;
2094 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1,
2095 DebugLoc &dl, unsigned &NewOpc,
2097 unsigned &SecondReg,
2098 unsigned &BaseReg, int &Offset,
2100 ARMCC::CondCodes &Pred,
2102 // Make sure we're allowed to generate LDRD/STRD.
2103 if (!STI->hasV5TEOps())
2106 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
2108 unsigned Opcode = Op0->getOpcode();
2109 if (Opcode == ARM::LDRi12) {
2111 } else if (Opcode == ARM::STRi12) {
2113 } else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
2114 NewOpc = ARM::t2LDRDi8;
2117 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
2118 NewOpc = ARM::t2STRDi8;
2125 // Make sure the base address satisfies i64 ld / st alignment requirement.
2126 // At the moment, we ignore the memoryoperand's value.
2127 // If we want to use AliasAnalysis, we should check it accordingly.
2128 if (!Op0->hasOneMemOperand() ||
2129 (*Op0->memoperands_begin())->isVolatile())
2132 unsigned Align = (*Op0->memoperands_begin())->getAlignment();
2133 const Function &Func = MF->getFunction();
2134 unsigned ReqAlign = STI->hasV6Ops()
2135 ? TD->getABITypeAlignment(Type::getInt64Ty(Func.getContext()))
2136 : 8; // Pre-v6 need 8-byte align
2137 if (Align < ReqAlign)
2140 // Then make sure the immediate offset fits.
2141 int OffImm = getMemoryOpOffset(*Op0);
2143 int Limit = (1 << 8) * Scale;
2144 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
2148 ARM_AM::AddrOpc AddSub = ARM_AM::add;
2150 AddSub = ARM_AM::sub;
2153 int Limit = (1 << 8) * Scale;
2154 if (OffImm >= Limit || (OffImm & (Scale-1)))
2156 Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
2158 FirstReg = Op0->getOperand(0).getReg();
2159 SecondReg = Op1->getOperand(0).getReg();
2160 if (FirstReg == SecondReg)
2162 BaseReg = Op0->getOperand(1).getReg();
2163 Pred = getInstrPredicate(*Op0, PredReg);
2164 dl = Op0->getDebugLoc();
2168 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
2169 SmallVectorImpl<MachineInstr *> &Ops,
2170 unsigned Base, bool isLd,
2171 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2172 bool RetVal = false;
2174 // Sort by offset (in reverse order).
2175 std::sort(Ops.begin(), Ops.end(),
2176 [](const MachineInstr *LHS, const MachineInstr *RHS) {
2177 int LOffset = getMemoryOpOffset(*LHS);
2178 int ROffset = getMemoryOpOffset(*RHS);
2179 assert(LHS == RHS || LOffset != ROffset);
2180 return LOffset > ROffset;
2183 // The loads / stores of the same base are in order. Scan them from first to
2184 // last and check for the following:
2185 // 1. Any def of base.
2187 while (Ops.size() > 1) {
2188 unsigned FirstLoc = ~0U;
2189 unsigned LastLoc = 0;
2190 MachineInstr *FirstOp = nullptr;
2191 MachineInstr *LastOp = nullptr;
2193 unsigned LastOpcode = 0;
2194 unsigned LastBytes = 0;
2195 unsigned NumMove = 0;
2196 for (int i = Ops.size() - 1; i >= 0; --i) {
2197 // Make sure each operation has the same kind.
2198 MachineInstr *Op = Ops[i];
2200 = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2201 if (LastOpcode && LSMOpcode != LastOpcode)
2204 // Check that we have a continuous set of offsets.
2205 int Offset = getMemoryOpOffset(*Op);
2206 unsigned Bytes = getLSMultipleTransferSize(Op);
2208 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2212 // Don't try to reschedule too many instructions.
2213 if (NumMove == 8) // FIXME: Tune this limit.
2216 // Found a mergable instruction; save information about it.
2218 LastOffset = Offset;
2220 LastOpcode = LSMOpcode;
2222 unsigned Loc = MI2LocMap[Op];
2223 if (Loc <= FirstLoc) {
2227 if (Loc >= LastLoc) {
2236 SmallPtrSet<MachineInstr*, 4> MemOps;
2237 SmallSet<unsigned, 4> MemRegs;
2238 for (size_t i = Ops.size() - NumMove, e = Ops.size(); i != e; ++i) {
2239 MemOps.insert(Ops[i]);
2240 MemRegs.insert(Ops[i]->getOperand(0).getReg());
2243 // Be conservative, if the instructions are too far apart, don't
2244 // move them. We want to limit the increase of register pressure.
2245 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
2247 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2248 MemOps, MemRegs, TRI, AA);
2250 for (unsigned i = 0; i != NumMove; ++i)
2253 // This is the new location for the loads / stores.
2254 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
2255 while (InsertPos != MBB->end() &&
2256 (MemOps.count(&*InsertPos) || InsertPos->isDebugValue()))
2259 // If we are moving a pair of loads / stores, see if it makes sense
2260 // to try to allocate a pair of registers that can form register pairs.
2261 MachineInstr *Op0 = Ops.back();
2262 MachineInstr *Op1 = Ops[Ops.size()-2];
2263 unsigned FirstReg = 0, SecondReg = 0;
2264 unsigned BaseReg = 0, PredReg = 0;
2265 ARMCC::CondCodes Pred = ARMCC::AL;
2267 unsigned NewOpc = 0;
2270 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
2271 FirstReg, SecondReg, BaseReg,
2272 Offset, PredReg, Pred, isT2)) {
2276 const MCInstrDesc &MCID = TII->get(NewOpc);
2277 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2278 MRI->constrainRegClass(FirstReg, TRC);
2279 MRI->constrainRegClass(SecondReg, TRC);
2281 // Form the pair instruction.
2283 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2284 .addReg(FirstReg, RegState::Define)
2285 .addReg(SecondReg, RegState::Define)
2287 // FIXME: We're converting from LDRi12 to an insn that still
2288 // uses addrmode2, so we need an explicit offset reg. It should
2289 // always by reg0 since we're transforming LDRi12s.
2292 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2293 MIB.setMemRefs(Op0->mergeMemRefsWith(*Op1));
2294 DEBUG(dbgs() << "Formed " << *MIB << "\n");
2297 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2301 // FIXME: We're converting from LDRi12 to an insn that still
2302 // uses addrmode2, so we need an explicit offset reg. It should
2303 // always by reg0 since we're transforming STRi12s.
2306 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2307 MIB.setMemRefs(Op0->mergeMemRefsWith(*Op1));
2308 DEBUG(dbgs() << "Formed " << *MIB << "\n");
2315 // Add register allocation hints to form register pairs.
2316 MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2317 MRI->setRegAllocationHint(SecondReg, ARMRI::RegPairOdd, FirstReg);
2320 for (unsigned i = 0; i != NumMove; ++i) {
2321 MachineInstr *Op = Ops.back();
2323 MBB->splice(InsertPos, MBB, Op);
2327 NumLdStMoved += NumMove;
2337 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2338 bool RetVal = false;
2340 DenseMap<MachineInstr*, unsigned> MI2LocMap;
2341 DenseMap<unsigned, SmallVector<MachineInstr *, 4>> Base2LdsMap;
2342 DenseMap<unsigned, SmallVector<MachineInstr *, 4>> Base2StsMap;
2343 SmallVector<unsigned, 4> LdBases;
2344 SmallVector<unsigned, 4> StBases;
2347 MachineBasicBlock::iterator MBBI = MBB->begin();
2348 MachineBasicBlock::iterator E = MBB->end();
2350 for (; MBBI != E; ++MBBI) {
2351 MachineInstr &MI = *MBBI;
2352 if (MI.isCall() || MI.isTerminator()) {
2353 // Stop at barriers.
2358 if (!MI.isDebugValue())
2359 MI2LocMap[&MI] = ++Loc;
2361 if (!isMemoryOp(MI))
2363 unsigned PredReg = 0;
2364 if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
2367 int Opc = MI.getOpcode();
2368 bool isLd = isLoadSingle(Opc);
2369 unsigned Base = MI.getOperand(1).getReg();
2370 int Offset = getMemoryOpOffset(MI);
2372 bool StopHere = false;
2374 DenseMap<unsigned, SmallVector<MachineInstr *, 4>>::iterator BI =
2375 Base2LdsMap.find(Base);
2376 if (BI != Base2LdsMap.end()) {
2377 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2378 if (Offset == getMemoryOpOffset(*BI->second[i])) {
2384 BI->second.push_back(&MI);
2386 Base2LdsMap[Base].push_back(&MI);
2387 LdBases.push_back(Base);
2390 DenseMap<unsigned, SmallVector<MachineInstr *, 4>>::iterator BI =
2391 Base2StsMap.find(Base);
2392 if (BI != Base2StsMap.end()) {
2393 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2394 if (Offset == getMemoryOpOffset(*BI->second[i])) {
2400 BI->second.push_back(&MI);
2402 Base2StsMap[Base].push_back(&MI);
2403 StBases.push_back(Base);
2408 // Found a duplicate (a base+offset combination that's seen earlier).
2415 // Re-schedule loads.
2416 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
2417 unsigned Base = LdBases[i];
2418 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
2420 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2423 // Re-schedule stores.
2424 for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
2425 unsigned Base = StBases[i];
2426 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
2428 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2432 Base2LdsMap.clear();
2433 Base2StsMap.clear();
2442 /// Returns an instance of the load / store optimization pass.
2443 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2445 return new ARMPreAllocLoadStoreOpt();
2446 return new ARMLoadStoreOpt();