1 //===- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass -------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 /// \file This file contains a pass that performs load / store related peephole
10 /// optimizations. This pass should be run after register allocation.
12 //===----------------------------------------------------------------------===//
15 #include "ARMBaseInstrInfo.h"
16 #include "ARMBaseRegisterInfo.h"
17 #include "ARMISelLowering.h"
18 #include "ARMMachineFunctionInfo.h"
19 #include "ARMSubtarget.h"
20 #include "MCTargetDesc/ARMAddressingModes.h"
21 #include "MCTargetDesc/ARMBaseInfo.h"
22 #include "Utils/ARMBaseInfo.h"
23 #include "llvm/ADT/ArrayRef.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/iterator_range.h"
32 #include "llvm/Analysis/AliasAnalysis.h"
33 #include "llvm/CodeGen/LivePhysRegs.h"
34 #include "llvm/CodeGen/MachineBasicBlock.h"
35 #include "llvm/CodeGen/MachineDominators.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/InitializePasses.h"
55 #include "llvm/MC/MCInstrDesc.h"
56 #include "llvm/Pass.h"
57 #include "llvm/Support/Allocator.h"
58 #include "llvm/Support/CommandLine.h"
59 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/ErrorHandling.h"
61 #include "llvm/Support/raw_ostream.h"
72 #define DEBUG_TYPE "arm-ldst-opt"
74 STATISTIC(NumLDMGened , "Number of ldm instructions generated");
75 STATISTIC(NumSTMGened , "Number of stm instructions generated");
76 STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
77 STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
78 STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
79 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
80 STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
81 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm");
82 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm");
83 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's");
84 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's");
86 /// This switch disables formation of double/multi instructions that could
87 /// potentially lead to (new) alignment traps even with CCR.UNALIGN_TRP
88 /// disabled. This can be used to create libraries that are robust even when
89 /// users provoke undefined behaviour by supplying misaligned pointers.
90 /// \see mayCombineMisaligned()
92 AssumeMisalignedLoadStores("arm-assume-misaligned-load-store", cl::Hidden,
93 cl::init(false), cl::desc("Be more conservative in ARM load/store opt"));
95 #define ARM_LOAD_STORE_OPT_NAME "ARM load / store optimization pass"
99 /// Post- register allocation pass the combine load / store instructions to
100 /// form ldm / stm instructions.
101 struct ARMLoadStoreOpt : public MachineFunctionPass {
104 const MachineFunction *MF;
105 const TargetInstrInfo *TII;
106 const TargetRegisterInfo *TRI;
107 const ARMSubtarget *STI;
108 const TargetLowering *TL;
109 ARMFunctionInfo *AFI;
110 LivePhysRegs LiveRegs;
111 RegisterClassInfo RegClassInfo;
112 MachineBasicBlock::const_iterator LiveRegPos;
114 bool RegClassInfoValid;
115 bool isThumb1, isThumb2;
117 ARMLoadStoreOpt() : MachineFunctionPass(ID) {}
119 bool runOnMachineFunction(MachineFunction &Fn) override;
121 MachineFunctionProperties getRequiredProperties() const override {
122 return MachineFunctionProperties().set(
123 MachineFunctionProperties::Property::NoVRegs);
126 StringRef getPassName() const override { return ARM_LOAD_STORE_OPT_NAME; }
129 /// A set of load/store MachineInstrs with same base register sorted by
131 struct MemOpQueueEntry {
133 int Offset; ///< Load/Store offset.
134 unsigned Position; ///< Position as counted from end of basic block.
136 MemOpQueueEntry(MachineInstr &MI, int Offset, unsigned Position)
137 : MI(&MI), Offset(Offset), Position(Position) {}
139 using MemOpQueue = SmallVector<MemOpQueueEntry, 8>;
141 /// A set of MachineInstrs that fulfill (nearly all) conditions to get
142 /// merged into a LDM/STM.
143 struct MergeCandidate {
144 /// List of instructions ordered by load/store offset.
145 SmallVector<MachineInstr*, 4> Instrs;
147 /// Index in Instrs of the instruction being latest in the schedule.
148 unsigned LatestMIIdx;
150 /// Index in Instrs of the instruction being earliest in the schedule.
151 unsigned EarliestMIIdx;
153 /// Index into the basic block where the merged instruction will be
154 /// inserted. (See MemOpQueueEntry.Position)
157 /// Whether the instructions can be merged into a ldm/stm instruction.
158 bool CanMergeToLSMulti;
160 /// Whether the instructions can be merged into a ldrd/strd instruction.
161 bool CanMergeToLSDouble;
163 SpecificBumpPtrAllocator<MergeCandidate> Allocator;
164 SmallVector<const MergeCandidate*,4> Candidates;
165 SmallVector<MachineInstr*,4> MergeBaseCandidates;
167 void moveLiveRegsBefore(const MachineBasicBlock &MBB,
168 MachineBasicBlock::const_iterator Before);
169 unsigned findFreeReg(const TargetRegisterClass &RegClass);
170 void UpdateBaseRegUses(MachineBasicBlock &MBB,
171 MachineBasicBlock::iterator MBBI, const DebugLoc &DL,
172 unsigned Base, unsigned WordOffset,
173 ARMCC::CondCodes Pred, unsigned PredReg);
174 MachineInstr *CreateLoadStoreMulti(
175 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
176 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
177 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
178 ArrayRef<std::pair<unsigned, bool>> Regs,
179 ArrayRef<MachineInstr*> Instrs);
180 MachineInstr *CreateLoadStoreDouble(
181 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
182 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
183 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
184 ArrayRef<std::pair<unsigned, bool>> Regs,
185 ArrayRef<MachineInstr*> Instrs) const;
186 void FormCandidates(const MemOpQueue &MemOps);
187 MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
188 bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
189 MachineBasicBlock::iterator &MBBI);
190 bool MergeBaseUpdateLoadStore(MachineInstr *MI);
191 bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
192 bool MergeBaseUpdateLSDouble(MachineInstr &MI) const;
193 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
194 bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
195 bool CombineMovBx(MachineBasicBlock &MBB);
198 } // end anonymous namespace
200 char ARMLoadStoreOpt::ID = 0;
202 INITIALIZE_PASS(ARMLoadStoreOpt, "arm-ldst-opt", ARM_LOAD_STORE_OPT_NAME, false,
205 static bool definesCPSR(const MachineInstr &MI) {
206 for (const auto &MO : MI.operands()) {
209 if (MO.isDef() && MO.getReg() == ARM::CPSR && !MO.isDead())
210 // If the instruction has live CPSR def, then it's not safe to fold it
211 // into load / store.
218 static int getMemoryOpOffset(const MachineInstr &MI) {
219 unsigned Opcode = MI.getOpcode();
220 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD;
221 unsigned NumOperands = MI.getDesc().getNumOperands();
222 unsigned OffField = MI.getOperand(NumOperands - 3).getImm();
224 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 ||
225 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 ||
226 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8 ||
227 Opcode == ARM::LDRi12 || Opcode == ARM::STRi12)
230 // Thumb1 immediate offsets are scaled by 4
231 if (Opcode == ARM::tLDRi || Opcode == ARM::tSTRi ||
232 Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi)
235 int Offset = isAM3 ? ARM_AM::getAM3Offset(OffField)
236 : ARM_AM::getAM5Offset(OffField) * 4;
237 ARM_AM::AddrOpc Op = isAM3 ? ARM_AM::getAM3Op(OffField)
238 : ARM_AM::getAM5Op(OffField);
240 if (Op == ARM_AM::sub)
246 static const MachineOperand &getLoadStoreBaseOp(const MachineInstr &MI) {
247 return MI.getOperand(1);
250 static const MachineOperand &getLoadStoreRegOp(const MachineInstr &MI) {
251 return MI.getOperand(0);
254 static int getLoadStoreMultipleOpcode(unsigned Opcode, ARM_AM::AMSubMode Mode) {
256 default: llvm_unreachable("Unhandled opcode!");
260 default: llvm_unreachable("Unhandled submode!");
261 case ARM_AM::ia: return ARM::LDMIA;
262 case ARM_AM::da: return ARM::LDMDA;
263 case ARM_AM::db: return ARM::LDMDB;
264 case ARM_AM::ib: return ARM::LDMIB;
269 default: llvm_unreachable("Unhandled submode!");
270 case ARM_AM::ia: return ARM::STMIA;
271 case ARM_AM::da: return ARM::STMDA;
272 case ARM_AM::db: return ARM::STMDB;
273 case ARM_AM::ib: return ARM::STMIB;
277 // tLDMIA is writeback-only - unless the base register is in the input
281 default: llvm_unreachable("Unhandled submode!");
282 case ARM_AM::ia: return ARM::tLDMIA;
286 // There is no non-writeback tSTMIA either.
289 default: llvm_unreachable("Unhandled submode!");
290 case ARM_AM::ia: return ARM::tSTMIA_UPD;
296 default: llvm_unreachable("Unhandled submode!");
297 case ARM_AM::ia: return ARM::t2LDMIA;
298 case ARM_AM::db: return ARM::t2LDMDB;
304 default: llvm_unreachable("Unhandled submode!");
305 case ARM_AM::ia: return ARM::t2STMIA;
306 case ARM_AM::db: return ARM::t2STMDB;
311 default: llvm_unreachable("Unhandled submode!");
312 case ARM_AM::ia: return ARM::VLDMSIA;
313 case ARM_AM::db: return 0; // Only VLDMSDB_UPD exists.
318 default: llvm_unreachable("Unhandled submode!");
319 case ARM_AM::ia: return ARM::VSTMSIA;
320 case ARM_AM::db: return 0; // Only VSTMSDB_UPD exists.
325 default: llvm_unreachable("Unhandled submode!");
326 case ARM_AM::ia: return ARM::VLDMDIA;
327 case ARM_AM::db: return 0; // Only VLDMDDB_UPD exists.
332 default: llvm_unreachable("Unhandled submode!");
333 case ARM_AM::ia: return ARM::VSTMDIA;
334 case ARM_AM::db: return 0; // Only VSTMDDB_UPD exists.
339 static ARM_AM::AMSubMode getLoadStoreMultipleSubMode(unsigned Opcode) {
341 default: llvm_unreachable("Unhandled opcode!");
348 case ARM::tLDMIA_UPD:
349 case ARM::tSTMIA_UPD:
350 case ARM::t2LDMIA_RET:
352 case ARM::t2LDMIA_UPD:
354 case ARM::t2STMIA_UPD:
356 case ARM::VLDMSIA_UPD:
358 case ARM::VSTMSIA_UPD:
360 case ARM::VLDMDIA_UPD:
362 case ARM::VSTMDIA_UPD:
376 case ARM::t2LDMDB_UPD:
378 case ARM::t2STMDB_UPD:
379 case ARM::VLDMSDB_UPD:
380 case ARM::VSTMSDB_UPD:
381 case ARM::VLDMDDB_UPD:
382 case ARM::VSTMDDB_UPD:
393 static bool isT1i32Load(unsigned Opc) {
394 return Opc == ARM::tLDRi || Opc == ARM::tLDRspi;
397 static bool isT2i32Load(unsigned Opc) {
398 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
401 static bool isi32Load(unsigned Opc) {
402 return Opc == ARM::LDRi12 || isT1i32Load(Opc) || isT2i32Load(Opc) ;
405 static bool isT1i32Store(unsigned Opc) {
406 return Opc == ARM::tSTRi || Opc == ARM::tSTRspi;
409 static bool isT2i32Store(unsigned Opc) {
410 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
413 static bool isi32Store(unsigned Opc) {
414 return Opc == ARM::STRi12 || isT1i32Store(Opc) || isT2i32Store(Opc);
417 static bool isLoadSingle(unsigned Opc) {
418 return isi32Load(Opc) || Opc == ARM::VLDRS || Opc == ARM::VLDRD;
421 static unsigned getImmScale(unsigned Opc) {
423 default: llvm_unreachable("Unhandled opcode!");
438 static unsigned getLSMultipleTransferSize(const MachineInstr *MI) {
439 switch (MI->getOpcode()) {
466 case ARM::tLDMIA_UPD:
467 case ARM::tSTMIA_UPD:
474 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 4;
477 return (MI->getNumOperands() - MI->getDesc().getNumOperands() + 1) * 8;
481 /// Update future uses of the base register with the offset introduced
482 /// due to writeback. This function only works on Thumb1.
483 void ARMLoadStoreOpt::UpdateBaseRegUses(MachineBasicBlock &MBB,
484 MachineBasicBlock::iterator MBBI,
485 const DebugLoc &DL, unsigned Base,
487 ARMCC::CondCodes Pred,
489 assert(isThumb1 && "Can only update base register uses for Thumb1!");
490 // Start updating any instructions with immediate offsets. Insert a SUB before
491 // the first non-updateable instruction (if any).
492 for (; MBBI != MBB.end(); ++MBBI) {
493 bool InsertSub = false;
494 unsigned Opc = MBBI->getOpcode();
496 if (MBBI->readsRegister(Base)) {
499 Opc == ARM::tLDRi || Opc == ARM::tLDRHi || Opc == ARM::tLDRBi;
501 Opc == ARM::tSTRi || Opc == ARM::tSTRHi || Opc == ARM::tSTRBi;
503 if (IsLoad || IsStore) {
504 // Loads and stores with immediate offsets can be updated, but only if
505 // the new offset isn't negative.
506 // The MachineOperand containing the offset immediate is the last one
507 // before predicates.
509 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
510 // The offsets are scaled by 1, 2 or 4 depending on the Opcode.
511 Offset = MO.getImm() - WordOffset * getImmScale(Opc);
513 // If storing the base register, it needs to be reset first.
514 Register InstrSrcReg = getLoadStoreRegOp(*MBBI).getReg();
516 if (Offset >= 0 && !(IsStore && InstrSrcReg == Base))
520 } else if ((Opc == ARM::tSUBi8 || Opc == ARM::tADDi8) &&
521 !definesCPSR(*MBBI)) {
522 // SUBS/ADDS using this register, with a dead def of the CPSR.
523 // Merge it with the update; if the merged offset is too large,
524 // insert a new sub instead.
526 MBBI->getOperand(MBBI->getDesc().getNumOperands() - 3);
527 Offset = (Opc == ARM::tSUBi8) ?
528 MO.getImm() + WordOffset * 4 :
529 MO.getImm() - WordOffset * 4 ;
530 if (Offset >= 0 && TL->isLegalAddImmediate(Offset)) {
531 // FIXME: Swap ADDS<->SUBS if Offset < 0, erase instruction if
534 // The base register has now been reset, so exit early.
540 // Can't update the instruction.
543 } else if (definesCPSR(*MBBI) || MBBI->isCall() || MBBI->isBranch()) {
544 // Since SUBS sets the condition flags, we can't place the base reset
545 // after an instruction that has a live CPSR def.
546 // The base register might also contain an argument for a function call.
551 // An instruction above couldn't be updated, so insert a sub.
552 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
553 .add(t1CondCodeOp(true))
555 .addImm(WordOffset * 4)
561 if (MBBI->killsRegister(Base) || MBBI->definesRegister(Base))
562 // Register got killed. Stop updating.
566 // End of block was reached.
567 if (MBB.succ_size() > 0) {
568 // FIXME: Because of a bug, live registers are sometimes missing from
569 // the successor blocks' live-in sets. This means we can't trust that
570 // information and *always* have to reset at the end of a block.
572 if (MBBI != MBB.end()) --MBBI;
573 BuildMI(MBB, MBBI, DL, TII->get(ARM::tSUBi8), Base)
574 .add(t1CondCodeOp(true))
576 .addImm(WordOffset * 4)
582 /// Return the first register of class \p RegClass that is not in \p Regs.
583 unsigned ARMLoadStoreOpt::findFreeReg(const TargetRegisterClass &RegClass) {
584 if (!RegClassInfoValid) {
585 RegClassInfo.runOnMachineFunction(*MF);
586 RegClassInfoValid = true;
589 for (unsigned Reg : RegClassInfo.getOrder(&RegClass))
590 if (!LiveRegs.contains(Reg))
595 /// Compute live registers just before instruction \p Before (in normal schedule
596 /// direction). Computes backwards so multiple queries in the same block must
597 /// come in reverse order.
598 void ARMLoadStoreOpt::moveLiveRegsBefore(const MachineBasicBlock &MBB,
599 MachineBasicBlock::const_iterator Before) {
600 // Initialize if we never queried in this block.
601 if (!LiveRegsValid) {
603 LiveRegs.addLiveOuts(MBB);
604 LiveRegPos = MBB.end();
605 LiveRegsValid = true;
607 // Move backward just before the "Before" position.
608 while (LiveRegPos != Before) {
610 LiveRegs.stepBackward(*LiveRegPos);
614 static bool ContainsReg(const ArrayRef<std::pair<unsigned, bool>> &Regs,
616 for (const std::pair<unsigned, bool> &R : Regs)
622 /// Create and insert a LDM or STM with Base as base register and registers in
623 /// Regs as the register operands that would be loaded / stored. It returns
624 /// true if the transformation is done.
625 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(
626 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
627 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
628 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
629 ArrayRef<std::pair<unsigned, bool>> Regs,
630 ArrayRef<MachineInstr*> Instrs) {
631 unsigned NumRegs = Regs.size();
634 // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
635 // Compute liveness information for that register to make the decision.
636 bool SafeToClobberCPSR = !isThumb1 ||
637 (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
638 MachineBasicBlock::LQR_Dead);
640 bool Writeback = isThumb1; // Thumb1 LDM/STM have base reg writeback.
642 // Exception: If the base register is in the input reglist, Thumb1 LDM is
644 // It's also not possible to merge an STR of the base register in Thumb1.
645 if (isThumb1 && ContainsReg(Regs, Base)) {
646 assert(Base != ARM::SP && "Thumb1 does not allow SP in register list");
647 if (Opcode == ARM::tLDRi)
649 else if (Opcode == ARM::tSTRi)
653 ARM_AM::AMSubMode Mode = ARM_AM::ia;
654 // VFP and Thumb2 do not support IB or DA modes. Thumb1 only supports IA.
655 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
656 bool haveIBAndDA = isNotVFP && !isThumb2 && !isThumb1;
658 if (Offset == 4 && haveIBAndDA) {
660 } else if (Offset == -4 * (int)NumRegs + 4 && haveIBAndDA) {
662 } else if (Offset == -4 * (int)NumRegs && isNotVFP && !isThumb1) {
663 // VLDM/VSTM do not support DB mode without also updating the base reg.
665 } else if (Offset != 0 || Opcode == ARM::tLDRspi || Opcode == ARM::tSTRspi) {
666 // Check if this is a supported opcode before inserting instructions to
667 // calculate a new base register.
668 if (!getLoadStoreMultipleOpcode(Opcode, Mode)) return nullptr;
670 // If starting offset isn't zero, insert a MI to materialize a new base.
671 // But only do so if it is cost effective, i.e. merging more than two
676 // On Thumb1, it's not worth materializing a new base register without
677 // clobbering the CPSR (i.e. not using ADDS/SUBS).
678 if (!SafeToClobberCPSR)
682 if (isi32Load(Opcode)) {
683 // If it is a load, then just use one of the destination registers
684 // as the new base. Will no longer be writeback in Thumb1.
685 NewBase = Regs[NumRegs-1].first;
688 // Find a free register that we can use as scratch register.
689 moveLiveRegsBefore(MBB, InsertBefore);
690 // The merged instruction does not exist yet but will use several Regs if
692 if (!isLoadSingle(Opcode))
693 for (const std::pair<unsigned, bool> &R : Regs)
694 LiveRegs.addReg(R.first);
696 NewBase = findFreeReg(isThumb1 ? ARM::tGPRRegClass : ARM::GPRRegClass);
701 int BaseOpc = isThumb2 ? (BaseKill && Base == ARM::SP ? ARM::t2ADDspImm
703 : (isThumb1 && Base == ARM::SP)
705 : (isThumb1 && Offset < 8)
707 : isThumb1 ? ARM::tADDi8 : ARM::ADDri;
710 // FIXME: There are no Thumb1 load/store instructions with negative
711 // offsets. So the Base != ARM::SP might be unnecessary.
713 BaseOpc = isThumb2 ? (BaseKill && Base == ARM::SP ? ARM::t2SUBspImm
715 : (isThumb1 && Offset < 8 && Base != ARM::SP)
717 : isThumb1 ? ARM::tSUBi8 : ARM::SUBri;
720 if (!TL->isLegalAddImmediate(Offset))
721 // FIXME: Try add with register operand?
722 return nullptr; // Probably not worth it then.
724 // We can only append a kill flag to the add/sub input if the value is not
725 // used in the register list of the stm as well.
726 bool KillOldBase = BaseKill &&
727 (!isi32Store(Opcode) || !ContainsReg(Regs, Base));
730 // Thumb1: depending on immediate size, use either
731 // ADDS NewBase, Base, #imm3
734 // ADDS NewBase, #imm8.
735 if (Base != NewBase &&
736 (BaseOpc == ARM::tADDi8 || BaseOpc == ARM::tSUBi8)) {
737 // Need to insert a MOV to the new base first.
738 if (isARMLowRegister(NewBase) && isARMLowRegister(Base) &&
740 // thumbv4t doesn't have lo->lo copies, and we can't predicate tMOVSr
741 if (Pred != ARMCC::AL)
743 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVSr), NewBase)
744 .addReg(Base, getKillRegState(KillOldBase));
746 BuildMI(MBB, InsertBefore, DL, TII->get(ARM::tMOVr), NewBase)
747 .addReg(Base, getKillRegState(KillOldBase))
748 .add(predOps(Pred, PredReg));
750 // The following ADDS/SUBS becomes an update.
754 if (BaseOpc == ARM::tADDrSPi) {
755 assert(Offset % 4 == 0 && "tADDrSPi offset is scaled by 4");
756 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
757 .addReg(Base, getKillRegState(KillOldBase))
759 .add(predOps(Pred, PredReg));
761 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
762 .add(t1CondCodeOp(true))
763 .addReg(Base, getKillRegState(KillOldBase))
765 .add(predOps(Pred, PredReg));
767 BuildMI(MBB, InsertBefore, DL, TII->get(BaseOpc), NewBase)
768 .addReg(Base, getKillRegState(KillOldBase))
770 .add(predOps(Pred, PredReg))
774 BaseKill = true; // New base is always killed straight away.
777 bool isDef = isLoadSingle(Opcode);
779 // Get LS multiple opcode. Note that for Thumb1 this might be an opcode with
780 // base register writeback.
781 Opcode = getLoadStoreMultipleOpcode(Opcode, Mode);
785 // Check if a Thumb1 LDM/STM merge is safe. This is the case if:
786 // - There is no writeback (LDM of base register),
787 // - the base register is killed by the merged instruction,
788 // - or it's safe to overwrite the condition flags, i.e. to insert a SUBS
789 // to reset the base register.
790 // Otherwise, don't merge.
791 // It's safe to return here since the code to materialize a new base register
792 // above is also conditional on SafeToClobberCPSR.
793 if (isThumb1 && !SafeToClobberCPSR && Writeback && !BaseKill)
796 MachineInstrBuilder MIB;
799 assert(isThumb1 && "expected Writeback only inThumb1");
800 if (Opcode == ARM::tLDMIA) {
801 assert(!(ContainsReg(Regs, Base)) && "Thumb1 can't LDM ! with Base in Regs");
802 // Update tLDMIA with writeback if necessary.
803 Opcode = ARM::tLDMIA_UPD;
806 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
808 // Thumb1: we might need to set base writeback when building the MI.
809 MIB.addReg(Base, getDefRegState(true))
810 .addReg(Base, getKillRegState(BaseKill));
812 // The base isn't dead after a merged instruction with writeback.
813 // Insert a sub instruction after the newly formed instruction to reset.
815 UpdateBaseRegUses(MBB, InsertBefore, DL, Base, NumRegs, Pred, PredReg);
817 // No writeback, simply build the MachineInstr.
818 MIB = BuildMI(MBB, InsertBefore, DL, TII->get(Opcode));
819 MIB.addReg(Base, getKillRegState(BaseKill));
822 MIB.addImm(Pred).addReg(PredReg);
824 for (const std::pair<unsigned, bool> &R : Regs)
825 MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
827 MIB.cloneMergedMemRefs(Instrs);
829 return MIB.getInstr();
832 MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(
833 MachineBasicBlock &MBB, MachineBasicBlock::iterator InsertBefore,
834 int Offset, unsigned Base, bool BaseKill, unsigned Opcode,
835 ARMCC::CondCodes Pred, unsigned PredReg, const DebugLoc &DL,
836 ArrayRef<std::pair<unsigned, bool>> Regs,
837 ArrayRef<MachineInstr*> Instrs) const {
838 bool IsLoad = isi32Load(Opcode);
839 assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
840 unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
842 assert(Regs.size() == 2);
843 MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
844 TII->get(LoadStoreOpcode));
846 MIB.addReg(Regs[0].first, RegState::Define)
847 .addReg(Regs[1].first, RegState::Define);
849 MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
850 .addReg(Regs[1].first, getKillRegState(Regs[1].second));
852 MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
853 MIB.cloneMergedMemRefs(Instrs);
854 return MIB.getInstr();
857 /// Call MergeOps and update MemOps and merges accordingly on success.
858 MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
859 const MachineInstr *First = Cand.Instrs.front();
860 unsigned Opcode = First->getOpcode();
861 bool IsLoad = isLoadSingle(Opcode);
862 SmallVector<std::pair<unsigned, bool>, 8> Regs;
863 SmallVector<unsigned, 4> ImpDefs;
864 DenseSet<unsigned> KilledRegs;
865 DenseSet<unsigned> UsedRegs;
866 // Determine list of registers and list of implicit super-register defs.
867 for (const MachineInstr *MI : Cand.Instrs) {
868 const MachineOperand &MO = getLoadStoreRegOp(*MI);
869 Register Reg = MO.getReg();
870 bool IsKill = MO.isKill();
872 KilledRegs.insert(Reg);
873 Regs.push_back(std::make_pair(Reg, IsKill));
874 UsedRegs.insert(Reg);
877 // Collect any implicit defs of super-registers, after merging we can't
878 // be sure anymore that we properly preserved these live ranges and must
879 // removed these implicit operands.
880 for (const MachineOperand &MO : MI->implicit_operands()) {
881 if (!MO.isReg() || !MO.isDef() || MO.isDead())
883 assert(MO.isImplicit());
884 Register DefReg = MO.getReg();
886 if (is_contained(ImpDefs, DefReg))
888 // We can ignore cases where the super-reg is read and written.
889 if (MI->readsRegister(DefReg))
891 ImpDefs.push_back(DefReg);
896 // Attempt the merge.
897 using iterator = MachineBasicBlock::iterator;
899 MachineInstr *LatestMI = Cand.Instrs[Cand.LatestMIIdx];
900 iterator InsertBefore = std::next(iterator(LatestMI));
901 MachineBasicBlock &MBB = *LatestMI->getParent();
902 unsigned Offset = getMemoryOpOffset(*First);
903 Register Base = getLoadStoreBaseOp(*First).getReg();
904 bool BaseKill = LatestMI->killsRegister(Base);
906 ARMCC::CondCodes Pred = getInstrPredicate(*First, PredReg);
907 DebugLoc DL = First->getDebugLoc();
908 MachineInstr *Merged = nullptr;
909 if (Cand.CanMergeToLSDouble)
910 Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
911 Opcode, Pred, PredReg, DL, Regs,
913 if (!Merged && Cand.CanMergeToLSMulti)
914 Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
915 Opcode, Pred, PredReg, DL, Regs, Cand.Instrs);
919 // Determine earliest instruction that will get removed. We then keep an
920 // iterator just above it so the following erases don't invalidated it.
921 iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
922 bool EarliestAtBegin = false;
923 if (EarliestI == MBB.begin()) {
924 EarliestAtBegin = true;
926 EarliestI = std::prev(EarliestI);
929 // Remove instructions which have been merged.
930 for (MachineInstr *MI : Cand.Instrs)
933 // Determine range between the earliest removed instruction and the new one.
935 EarliestI = MBB.begin();
937 EarliestI = std::next(EarliestI);
938 auto FixupRange = make_range(EarliestI, iterator(Merged));
940 if (isLoadSingle(Opcode)) {
941 // If the previous loads defined a super-reg, then we have to mark earlier
942 // operands undef; Replicate the super-reg def on the merged instruction.
943 for (MachineInstr &MI : FixupRange) {
944 for (unsigned &ImpDefReg : ImpDefs) {
945 for (MachineOperand &MO : MI.implicit_operands()) {
946 if (!MO.isReg() || MO.getReg() != ImpDefReg)
956 MachineInstrBuilder MIB(*Merged->getParent()->getParent(), Merged);
957 for (unsigned ImpDef : ImpDefs)
958 MIB.addReg(ImpDef, RegState::ImplicitDefine);
960 // Remove kill flags: We are possibly storing the values later now.
961 assert(isi32Store(Opcode) || Opcode == ARM::VSTRS || Opcode == ARM::VSTRD);
962 for (MachineInstr &MI : FixupRange) {
963 for (MachineOperand &MO : MI.uses()) {
964 if (!MO.isReg() || !MO.isKill())
966 if (UsedRegs.count(MO.getReg()))
970 assert(ImpDefs.empty());
976 static bool isValidLSDoubleOffset(int Offset) {
977 unsigned Value = abs(Offset);
978 // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
980 return (Value % 4) == 0 && Value < 1024;
983 /// Return true for loads/stores that can be combined to a double/multi
984 /// operation without increasing the requirements for alignment.
985 static bool mayCombineMisaligned(const TargetSubtargetInfo &STI,
986 const MachineInstr &MI) {
987 // vldr/vstr trap on misaligned pointers anyway, forming vldm makes no
989 unsigned Opcode = MI.getOpcode();
990 if (!isi32Load(Opcode) && !isi32Store(Opcode))
993 // Stack pointer alignment is out of the programmers control so we can trust
994 // SP-relative loads/stores.
995 if (getLoadStoreBaseOp(MI).getReg() == ARM::SP &&
996 STI.getFrameLowering()->getTransientStackAlign() >= Align(4))
1001 /// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
1002 void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
1003 const MachineInstr *FirstMI = MemOps[0].MI;
1004 unsigned Opcode = FirstMI->getOpcode();
1005 bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
1006 unsigned Size = getLSMultipleTransferSize(FirstMI);
1008 unsigned SIndex = 0;
1009 unsigned EIndex = MemOps.size();
1011 // Look at the first instruction.
1012 const MachineInstr *MI = MemOps[SIndex].MI;
1013 int Offset = MemOps[SIndex].Offset;
1014 const MachineOperand &PMO = getLoadStoreRegOp(*MI);
1015 Register PReg = PMO.getReg();
1016 unsigned PRegNum = PMO.isUndef() ? std::numeric_limits<unsigned>::max()
1017 : TRI->getEncodingValue(PReg);
1018 unsigned Latest = SIndex;
1019 unsigned Earliest = SIndex;
1021 bool CanMergeToLSDouble =
1022 STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
1023 // ARM errata 602117: LDRD with base in list may result in incorrect base
1024 // register when interrupted or faulted.
1025 if (STI->isCortexM3() && isi32Load(Opcode) &&
1026 PReg == getLoadStoreBaseOp(*MI).getReg())
1027 CanMergeToLSDouble = false;
1029 bool CanMergeToLSMulti = true;
1030 // On swift vldm/vstm starting with an odd register number as that needs
1031 // more uops than single vldrs.
1032 if (STI->hasSlowOddRegister() && !isNotVFP && (PRegNum % 2) == 1)
1033 CanMergeToLSMulti = false;
1035 // LDRD/STRD do not allow SP/PC. LDM/STM do not support it or have it
1036 // deprecated; LDM to PC is fine but cannot happen here.
1037 if (PReg == ARM::SP || PReg == ARM::PC)
1038 CanMergeToLSMulti = CanMergeToLSDouble = false;
1040 // Should we be conservative?
1041 if (AssumeMisalignedLoadStores && !mayCombineMisaligned(*STI, *MI))
1042 CanMergeToLSMulti = CanMergeToLSDouble = false;
1044 // vldm / vstm limit are 32 for S variants, 16 for D variants.
1056 // Merge following instructions where possible.
1057 for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
1058 int NewOffset = MemOps[I].Offset;
1059 if (NewOffset != Offset + (int)Size)
1061 const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
1062 Register Reg = MO.getReg();
1063 if (Reg == ARM::SP || Reg == ARM::PC)
1068 // See if the current load/store may be part of a multi load/store.
1069 unsigned RegNum = MO.isUndef() ? std::numeric_limits<unsigned>::max()
1070 : TRI->getEncodingValue(Reg);
1071 bool PartOfLSMulti = CanMergeToLSMulti;
1072 if (PartOfLSMulti) {
1073 // Register numbers must be in ascending order.
1074 if (RegNum <= PRegNum)
1075 PartOfLSMulti = false;
1076 // For VFP / NEON load/store multiples, the registers must be
1077 // consecutive and within the limit on the number of registers per
1079 else if (!isNotVFP && RegNum != PRegNum+1)
1080 PartOfLSMulti = false;
1082 // See if the current load/store may be part of a double load/store.
1083 bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
1085 if (!PartOfLSMulti && !PartOfLSDouble)
1087 CanMergeToLSMulti &= PartOfLSMulti;
1088 CanMergeToLSDouble &= PartOfLSDouble;
1089 // Track MemOp with latest and earliest position (Positions are
1090 // counted in reverse).
1091 unsigned Position = MemOps[I].Position;
1092 if (Position < MemOps[Latest].Position)
1094 else if (Position > MemOps[Earliest].Position)
1096 // Prepare for next MemOp.
1101 // Form a candidate from the Ops collected so far.
1102 MergeCandidate *Candidate = new(Allocator.Allocate()) MergeCandidate;
1103 for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
1104 Candidate->Instrs.push_back(MemOps[C].MI);
1105 Candidate->LatestMIIdx = Latest - SIndex;
1106 Candidate->EarliestMIIdx = Earliest - SIndex;
1107 Candidate->InsertPos = MemOps[Latest].Position;
1109 CanMergeToLSMulti = CanMergeToLSDouble = false;
1110 Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
1111 Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
1112 Candidates.push_back(Candidate);
1113 // Continue after the chain.
1115 } while (SIndex < EIndex);
1118 static unsigned getUpdatingLSMultipleOpcode(unsigned Opc,
1119 ARM_AM::AMSubMode Mode) {
1121 default: llvm_unreachable("Unhandled opcode!");
1127 default: llvm_unreachable("Unhandled submode!");
1128 case ARM_AM::ia: return ARM::LDMIA_UPD;
1129 case ARM_AM::ib: return ARM::LDMIB_UPD;
1130 case ARM_AM::da: return ARM::LDMDA_UPD;
1131 case ARM_AM::db: return ARM::LDMDB_UPD;
1138 default: llvm_unreachable("Unhandled submode!");
1139 case ARM_AM::ia: return ARM::STMIA_UPD;
1140 case ARM_AM::ib: return ARM::STMIB_UPD;
1141 case ARM_AM::da: return ARM::STMDA_UPD;
1142 case ARM_AM::db: return ARM::STMDB_UPD;
1147 default: llvm_unreachable("Unhandled submode!");
1148 case ARM_AM::ia: return ARM::t2LDMIA_UPD;
1149 case ARM_AM::db: return ARM::t2LDMDB_UPD;
1154 default: llvm_unreachable("Unhandled submode!");
1155 case ARM_AM::ia: return ARM::t2STMIA_UPD;
1156 case ARM_AM::db: return ARM::t2STMDB_UPD;
1160 default: llvm_unreachable("Unhandled submode!");
1161 case ARM_AM::ia: return ARM::VLDMSIA_UPD;
1162 case ARM_AM::db: return ARM::VLDMSDB_UPD;
1166 default: llvm_unreachable("Unhandled submode!");
1167 case ARM_AM::ia: return ARM::VLDMDIA_UPD;
1168 case ARM_AM::db: return ARM::VLDMDDB_UPD;
1172 default: llvm_unreachable("Unhandled submode!");
1173 case ARM_AM::ia: return ARM::VSTMSIA_UPD;
1174 case ARM_AM::db: return ARM::VSTMSDB_UPD;
1178 default: llvm_unreachable("Unhandled submode!");
1179 case ARM_AM::ia: return ARM::VSTMDIA_UPD;
1180 case ARM_AM::db: return ARM::VSTMDDB_UPD;
1185 /// Check if the given instruction increments or decrements a register and
1186 /// return the amount it is incremented/decremented. Returns 0 if the CPSR flags
1187 /// generated by the instruction are possibly read as well.
1188 static int isIncrementOrDecrement(const MachineInstr &MI, Register Reg,
1189 ARMCC::CondCodes Pred, Register PredReg) {
1192 switch (MI.getOpcode()) {
1193 case ARM::tADDi8: Scale = 4; CheckCPSRDef = true; break;
1194 case ARM::tSUBi8: Scale = -4; CheckCPSRDef = true; break;
1196 case ARM::t2SUBspImm:
1197 case ARM::SUBri: Scale = -1; CheckCPSRDef = true; break;
1199 case ARM::t2ADDspImm:
1200 case ARM::ADDri: Scale = 1; CheckCPSRDef = true; break;
1201 case ARM::tADDspi: Scale = 4; CheckCPSRDef = false; break;
1202 case ARM::tSUBspi: Scale = -4; CheckCPSRDef = false; break;
1207 if (MI.getOperand(0).getReg() != Reg ||
1208 MI.getOperand(1).getReg() != Reg ||
1209 getInstrPredicate(MI, MIPredReg) != Pred ||
1210 MIPredReg != PredReg)
1213 if (CheckCPSRDef && definesCPSR(MI))
1215 return MI.getOperand(2).getImm() * Scale;
1218 /// Searches for an increment or decrement of \p Reg before \p MBBI.
1219 static MachineBasicBlock::iterator
1220 findIncDecBefore(MachineBasicBlock::iterator MBBI, Register Reg,
1221 ARMCC::CondCodes Pred, Register PredReg, int &Offset) {
1223 MachineBasicBlock &MBB = *MBBI->getParent();
1224 MachineBasicBlock::iterator BeginMBBI = MBB.begin();
1225 MachineBasicBlock::iterator EndMBBI = MBB.end();
1226 if (MBBI == BeginMBBI)
1229 // Skip debug values.
1230 MachineBasicBlock::iterator PrevMBBI = std::prev(MBBI);
1231 while (PrevMBBI->isDebugInstr() && PrevMBBI != BeginMBBI)
1234 Offset = isIncrementOrDecrement(*PrevMBBI, Reg, Pred, PredReg);
1235 return Offset == 0 ? EndMBBI : PrevMBBI;
1238 /// Searches for a increment or decrement of \p Reg after \p MBBI.
1239 static MachineBasicBlock::iterator
1240 findIncDecAfter(MachineBasicBlock::iterator MBBI, Register Reg,
1241 ARMCC::CondCodes Pred, Register PredReg, int &Offset) {
1243 MachineBasicBlock &MBB = *MBBI->getParent();
1244 MachineBasicBlock::iterator EndMBBI = MBB.end();
1245 MachineBasicBlock::iterator NextMBBI = std::next(MBBI);
1246 // Skip debug values.
1247 while (NextMBBI != EndMBBI && NextMBBI->isDebugInstr())
1249 if (NextMBBI == EndMBBI)
1252 Offset = isIncrementOrDecrement(*NextMBBI, Reg, Pred, PredReg);
1253 return Offset == 0 ? EndMBBI : NextMBBI;
1256 /// Fold proceeding/trailing inc/dec of base register into the
1257 /// LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
1259 /// stmia rn, <ra, rb, rc>
1260 /// rn := rn + 4 * 3;
1262 /// stmia rn!, <ra, rb, rc>
1264 /// rn := rn - 4 * 3;
1265 /// ldmia rn, <ra, rb, rc>
1267 /// ldmdb rn!, <ra, rb, rc>
1268 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineInstr *MI) {
1269 // Thumb1 is already using updating loads/stores.
1270 if (isThumb1) return false;
1272 const MachineOperand &BaseOP = MI->getOperand(0);
1273 Register Base = BaseOP.getReg();
1274 bool BaseKill = BaseOP.isKill();
1276 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1277 unsigned Opcode = MI->getOpcode();
1278 DebugLoc DL = MI->getDebugLoc();
1280 // Can't use an updating ld/st if the base register is also a dest
1281 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
1282 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1283 if (MI->getOperand(i).getReg() == Base)
1286 int Bytes = getLSMultipleTransferSize(MI);
1287 MachineBasicBlock &MBB = *MI->getParent();
1288 MachineBasicBlock::iterator MBBI(MI);
1290 MachineBasicBlock::iterator MergeInstr
1291 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1292 ARM_AM::AMSubMode Mode = getLoadStoreMultipleSubMode(Opcode);
1293 if (Mode == ARM_AM::ia && Offset == -Bytes) {
1295 } else if (Mode == ARM_AM::ib && Offset == -Bytes) {
1298 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1299 if (((Mode != ARM_AM::ia && Mode != ARM_AM::ib) || Offset != Bytes) &&
1300 ((Mode != ARM_AM::da && Mode != ARM_AM::db) || Offset != -Bytes)) {
1302 // We couldn't find an inc/dec to merge. But if the base is dead, we
1303 // can still change to a writeback form as that will save us 2 bytes
1304 // of code size. It can create WAW hazards though, so only do it if
1305 // we're minimizing code size.
1306 if (!STI->hasMinSize() || !BaseKill)
1309 bool HighRegsUsed = false;
1310 for (unsigned i = 2, e = MI->getNumOperands(); i != e; ++i)
1311 if (MI->getOperand(i).getReg() >= ARM::R8) {
1312 HighRegsUsed = true;
1317 MergeInstr = MBB.end();
1322 if (MergeInstr != MBB.end())
1323 MBB.erase(MergeInstr);
1325 unsigned NewOpc = getUpdatingLSMultipleOpcode(Opcode, Mode);
1326 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1327 .addReg(Base, getDefRegState(true)) // WB base register
1328 .addReg(Base, getKillRegState(BaseKill))
1329 .addImm(Pred).addReg(PredReg);
1331 // Transfer the rest of operands.
1332 for (unsigned OpNum = 3, e = MI->getNumOperands(); OpNum != e; ++OpNum)
1333 MIB.add(MI->getOperand(OpNum));
1335 // Transfer memoperands.
1336 MIB.setMemRefs(MI->memoperands());
1342 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc,
1343 ARM_AM::AddrOpc Mode) {
1346 return ARM::LDR_PRE_IMM;
1348 return ARM::STR_PRE_IMM;
1350 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1352 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1354 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1356 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1359 return ARM::t2LDR_PRE;
1362 return ARM::t2STR_PRE;
1363 default: llvm_unreachable("Unhandled opcode!");
1367 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc,
1368 ARM_AM::AddrOpc Mode) {
1371 return ARM::LDR_POST_IMM;
1373 return ARM::STR_POST_IMM;
1375 return Mode == ARM_AM::add ? ARM::VLDMSIA_UPD : ARM::VLDMSDB_UPD;
1377 return Mode == ARM_AM::add ? ARM::VLDMDIA_UPD : ARM::VLDMDDB_UPD;
1379 return Mode == ARM_AM::add ? ARM::VSTMSIA_UPD : ARM::VSTMSDB_UPD;
1381 return Mode == ARM_AM::add ? ARM::VSTMDIA_UPD : ARM::VSTMDDB_UPD;
1384 return ARM::t2LDR_POST;
1387 return ARM::t2STR_POST;
1389 case ARM::MVE_VLDRBS16:
1390 return ARM::MVE_VLDRBS16_post;
1391 case ARM::MVE_VLDRBS32:
1392 return ARM::MVE_VLDRBS32_post;
1393 case ARM::MVE_VLDRBU16:
1394 return ARM::MVE_VLDRBU16_post;
1395 case ARM::MVE_VLDRBU32:
1396 return ARM::MVE_VLDRBU32_post;
1397 case ARM::MVE_VLDRHS32:
1398 return ARM::MVE_VLDRHS32_post;
1399 case ARM::MVE_VLDRHU32:
1400 return ARM::MVE_VLDRHU32_post;
1401 case ARM::MVE_VLDRBU8:
1402 return ARM::MVE_VLDRBU8_post;
1403 case ARM::MVE_VLDRHU16:
1404 return ARM::MVE_VLDRHU16_post;
1405 case ARM::MVE_VLDRWU32:
1406 return ARM::MVE_VLDRWU32_post;
1407 case ARM::MVE_VSTRB16:
1408 return ARM::MVE_VSTRB16_post;
1409 case ARM::MVE_VSTRB32:
1410 return ARM::MVE_VSTRB32_post;
1411 case ARM::MVE_VSTRH32:
1412 return ARM::MVE_VSTRH32_post;
1413 case ARM::MVE_VSTRBU8:
1414 return ARM::MVE_VSTRBU8_post;
1415 case ARM::MVE_VSTRHU16:
1416 return ARM::MVE_VSTRHU16_post;
1417 case ARM::MVE_VSTRWU32:
1418 return ARM::MVE_VSTRWU32_post;
1420 default: llvm_unreachable("Unhandled opcode!");
1424 /// Fold proceeding/trailing inc/dec of base register into the
1425 /// LDR/STR/FLD{D|S}/FST{D|S} op when possible:
1426 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineInstr *MI) {
1427 // Thumb1 doesn't have updating LDR/STR.
1428 // FIXME: Use LDM/STM with single register instead.
1429 if (isThumb1) return false;
1431 Register Base = getLoadStoreBaseOp(*MI).getReg();
1432 bool BaseKill = getLoadStoreBaseOp(*MI).isKill();
1433 unsigned Opcode = MI->getOpcode();
1434 DebugLoc DL = MI->getDebugLoc();
1435 bool isAM5 = (Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
1436 Opcode == ARM::VSTRD || Opcode == ARM::VSTRS);
1437 bool isAM2 = (Opcode == ARM::LDRi12 || Opcode == ARM::STRi12);
1438 if (isi32Load(Opcode) || isi32Store(Opcode))
1439 if (MI->getOperand(2).getImm() != 0)
1441 if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
1444 // Can't do the merge if the destination register is the same as the would-be
1445 // writeback register.
1446 if (MI->getOperand(0).getReg() == Base)
1450 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1451 int Bytes = getLSMultipleTransferSize(MI);
1452 MachineBasicBlock &MBB = *MI->getParent();
1453 MachineBasicBlock::iterator MBBI(MI);
1455 MachineBasicBlock::iterator MergeInstr
1456 = findIncDecBefore(MBBI, Base, Pred, PredReg, Offset);
1458 if (!isAM5 && Offset == Bytes) {
1459 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1460 } else if (Offset == -Bytes) {
1461 NewOpc = getPreIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1463 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1464 if (Offset == Bytes) {
1465 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::add);
1466 } else if (!isAM5 && Offset == -Bytes) {
1467 NewOpc = getPostIndexedLoadStoreOpcode(Opcode, ARM_AM::sub);
1471 MBB.erase(MergeInstr);
1473 ARM_AM::AddrOpc AddSub = Offset < 0 ? ARM_AM::sub : ARM_AM::add;
1475 bool isLd = isLoadSingle(Opcode);
1477 // VLDM[SD]_UPD, VSTM[SD]_UPD
1478 // (There are no base-updating versions of VLDR/VSTR instructions, but the
1479 // updating load/store-multiple instructions can be used with only one
1481 MachineOperand &MO = MI->getOperand(0);
1482 BuildMI(MBB, MBBI, DL, TII->get(NewOpc))
1483 .addReg(Base, getDefRegState(true)) // WB base register
1484 .addReg(Base, getKillRegState(isLd ? BaseKill : false))
1485 .addImm(Pred).addReg(PredReg)
1486 .addReg(MO.getReg(), (isLd ? getDefRegState(true) :
1487 getKillRegState(MO.isKill())))
1491 // LDR_PRE, LDR_POST
1492 if (NewOpc == ARM::LDR_PRE_IMM || NewOpc == ARM::LDRB_PRE_IMM) {
1493 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1494 .addReg(Base, RegState::Define)
1495 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg)
1498 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1499 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1500 .addReg(Base, RegState::Define)
1504 .add(predOps(Pred, PredReg))
1508 // t2LDR_PRE, t2LDR_POST
1509 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), MI->getOperand(0).getReg())
1510 .addReg(Base, RegState::Define)
1513 .add(predOps(Pred, PredReg))
1517 MachineOperand &MO = MI->getOperand(0);
1518 // FIXME: post-indexed stores use am2offset_imm, which still encodes
1519 // the vestigal zero-reg offset register. When that's fixed, this clause
1520 // can be removed entirely.
1521 if (isAM2 && NewOpc == ARM::STR_POST_IMM) {
1522 int Imm = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
1523 // STR_PRE, STR_POST
1524 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1525 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1529 .add(predOps(Pred, PredReg))
1532 // t2STR_PRE, t2STR_POST
1533 BuildMI(MBB, MBBI, DL, TII->get(NewOpc), Base)
1534 .addReg(MO.getReg(), getKillRegState(MO.isKill()))
1537 .add(predOps(Pred, PredReg))
1546 bool ARMLoadStoreOpt::MergeBaseUpdateLSDouble(MachineInstr &MI) const {
1547 unsigned Opcode = MI.getOpcode();
1548 assert((Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) &&
1549 "Must have t2STRDi8 or t2LDRDi8");
1550 if (MI.getOperand(3).getImm() != 0)
1553 // Behaviour for writeback is undefined if base register is the same as one
1555 const MachineOperand &BaseOp = MI.getOperand(2);
1556 Register Base = BaseOp.getReg();
1557 const MachineOperand &Reg0Op = MI.getOperand(0);
1558 const MachineOperand &Reg1Op = MI.getOperand(1);
1559 if (Reg0Op.getReg() == Base || Reg1Op.getReg() == Base)
1563 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
1564 MachineBasicBlock::iterator MBBI(MI);
1565 MachineBasicBlock &MBB = *MI.getParent();
1567 MachineBasicBlock::iterator MergeInstr = findIncDecBefore(MBBI, Base, Pred,
1570 if (Offset == 8 || Offset == -8) {
1571 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_PRE : ARM::t2STRD_PRE;
1573 MergeInstr = findIncDecAfter(MBBI, Base, Pred, PredReg, Offset);
1574 if (Offset == 8 || Offset == -8) {
1575 NewOpc = Opcode == ARM::t2LDRDi8 ? ARM::t2LDRD_POST : ARM::t2STRD_POST;
1579 MBB.erase(MergeInstr);
1581 DebugLoc DL = MI.getDebugLoc();
1582 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(NewOpc));
1583 if (NewOpc == ARM::t2LDRD_PRE || NewOpc == ARM::t2LDRD_POST) {
1584 MIB.add(Reg0Op).add(Reg1Op).addReg(BaseOp.getReg(), RegState::Define);
1586 assert(NewOpc == ARM::t2STRD_PRE || NewOpc == ARM::t2STRD_POST);
1587 MIB.addReg(BaseOp.getReg(), RegState::Define).add(Reg0Op).add(Reg1Op);
1589 MIB.addReg(BaseOp.getReg(), RegState::Kill)
1590 .addImm(Offset).addImm(Pred).addReg(PredReg);
1591 assert(TII->get(Opcode).getNumOperands() == 6 &&
1592 TII->get(NewOpc).getNumOperands() == 7 &&
1593 "Unexpected number of operands in Opcode specification.");
1595 // Transfer implicit operands.
1596 for (const MachineOperand &MO : MI.implicit_operands())
1598 MIB.cloneMemRefs(MI);
1604 /// Returns true if instruction is a memory operation that this pass is capable
1605 /// of operating on.
1606 static bool isMemoryOp(const MachineInstr &MI) {
1607 unsigned Opcode = MI.getOpcode();
1627 if (!MI.getOperand(1).isReg())
1630 // When no memory operands are present, conservatively assume unaligned,
1631 // volatile, unfoldable.
1632 if (!MI.hasOneMemOperand())
1635 const MachineMemOperand &MMO = **MI.memoperands_begin();
1637 // Don't touch volatile memory accesses - we may be changing their order.
1638 // TODO: We could allow unordered and monotonic atomics here, but we need to
1639 // make sure the resulting ldm/stm is correctly marked as atomic.
1640 if (MMO.isVolatile() || MMO.isAtomic())
1643 // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
1645 if (MMO.getAlign() < Align(4))
1648 // str <undef> could probably be eliminated entirely, but for now we just want
1649 // to avoid making a mess of it.
1650 // FIXME: Use str <undef> as a wildcard to enable better stm folding.
1651 if (MI.getOperand(0).isReg() && MI.getOperand(0).isUndef())
1654 // Likewise don't mess with references to undefined addresses.
1655 if (MI.getOperand(1).isUndef())
1661 static void InsertLDR_STR(MachineBasicBlock &MBB,
1662 MachineBasicBlock::iterator &MBBI, int Offset,
1663 bool isDef, unsigned NewOpc, unsigned Reg,
1664 bool RegDeadKill, bool RegUndef, unsigned BaseReg,
1665 bool BaseKill, bool BaseUndef, ARMCC::CondCodes Pred,
1666 unsigned PredReg, const TargetInstrInfo *TII,
1669 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1671 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill))
1672 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1673 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1674 // FIXME: This is overly conservative; the new instruction accesses 4
1676 MIB.cloneMemRefs(*MI);
1678 MachineInstrBuilder MIB = BuildMI(MBB, MBBI, MBBI->getDebugLoc(),
1680 .addReg(Reg, getKillRegState(RegDeadKill) | getUndefRegState(RegUndef))
1681 .addReg(BaseReg, getKillRegState(BaseKill)|getUndefRegState(BaseUndef));
1682 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
1683 // FIXME: This is overly conservative; the new instruction accesses 4
1685 MIB.cloneMemRefs(*MI);
1689 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB,
1690 MachineBasicBlock::iterator &MBBI) {
1691 MachineInstr *MI = &*MBBI;
1692 unsigned Opcode = MI->getOpcode();
1693 // FIXME: Code/comments below check Opcode == t2STRDi8, but this check returns
1694 // if we see this opcode.
1695 if (Opcode != ARM::LDRD && Opcode != ARM::STRD && Opcode != ARM::t2LDRDi8)
1698 const MachineOperand &BaseOp = MI->getOperand(2);
1699 Register BaseReg = BaseOp.getReg();
1700 Register EvenReg = MI->getOperand(0).getReg();
1701 Register OddReg = MI->getOperand(1).getReg();
1702 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false);
1703 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false);
1705 // ARM errata 602117: LDRD with base in list may result in incorrect base
1706 // register when interrupted or faulted.
1707 bool Errata602117 = EvenReg == BaseReg &&
1708 (Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8) && STI->isCortexM3();
1709 // ARM LDRD/STRD needs consecutive registers.
1710 bool NonConsecutiveRegs = (Opcode == ARM::LDRD || Opcode == ARM::STRD) &&
1711 (EvenRegNum % 2 != 0 || EvenRegNum + 1 != OddRegNum);
1713 if (!Errata602117 && !NonConsecutiveRegs)
1716 bool isT2 = Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8;
1717 bool isLd = Opcode == ARM::LDRD || Opcode == ARM::t2LDRDi8;
1718 bool EvenDeadKill = isLd ?
1719 MI->getOperand(0).isDead() : MI->getOperand(0).isKill();
1720 bool EvenUndef = MI->getOperand(0).isUndef();
1721 bool OddDeadKill = isLd ?
1722 MI->getOperand(1).isDead() : MI->getOperand(1).isKill();
1723 bool OddUndef = MI->getOperand(1).isUndef();
1724 bool BaseKill = BaseOp.isKill();
1725 bool BaseUndef = BaseOp.isUndef();
1726 assert((isT2 || MI->getOperand(3).getReg() == ARM::NoRegister) &&
1727 "register offset not handled below");
1728 int OffImm = getMemoryOpOffset(*MI);
1730 ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
1732 if (OddRegNum > EvenRegNum && OffImm == 0) {
1733 // Ascending register numbers and no offset. It's safe to change it to a
1735 unsigned NewOpc = (isLd)
1736 ? (isT2 ? ARM::t2LDMIA : ARM::LDMIA)
1737 : (isT2 ? ARM::t2STMIA : ARM::STMIA);
1739 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1740 .addReg(BaseReg, getKillRegState(BaseKill))
1741 .addImm(Pred).addReg(PredReg)
1742 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill))
1743 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill))
1747 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc))
1748 .addReg(BaseReg, getKillRegState(BaseKill))
1749 .addImm(Pred).addReg(PredReg)
1751 getKillRegState(EvenDeadKill) | getUndefRegState(EvenUndef))
1753 getKillRegState(OddDeadKill) | getUndefRegState(OddUndef))
1758 // Split into two instructions.
1759 unsigned NewOpc = (isLd)
1760 ? (isT2 ? (OffImm < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1761 : (isT2 ? (OffImm < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1762 // Be extra careful for thumb2. t2LDRi8 can't reference a zero offset,
1763 // so adjust and use t2LDRi12 here for that.
1764 unsigned NewOpc2 = (isLd)
1765 ? (isT2 ? (OffImm+4 < 0 ? ARM::t2LDRi8 : ARM::t2LDRi12) : ARM::LDRi12)
1766 : (isT2 ? (OffImm+4 < 0 ? ARM::t2STRi8 : ARM::t2STRi12) : ARM::STRi12);
1767 // If this is a load, make sure the first load does not clobber the base
1768 // register before the second load reads it.
1769 if (isLd && TRI->regsOverlap(EvenReg, BaseReg)) {
1770 assert(!TRI->regsOverlap(OddReg, BaseReg));
1771 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1772 false, BaseReg, false, BaseUndef, Pred, PredReg, TII, MI);
1773 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1774 false, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1777 if (OddReg == EvenReg && EvenDeadKill) {
1778 // If the two source operands are the same, the kill marker is
1779 // probably on the first one. e.g.
1780 // t2STRDi8 killed %r5, %r5, killed %r9, 0, 14, %reg0
1781 EvenDeadKill = false;
1784 // Never kill the base register in the first instruction.
1785 if (EvenReg == BaseReg)
1786 EvenDeadKill = false;
1787 InsertLDR_STR(MBB, MBBI, OffImm, isLd, NewOpc, EvenReg, EvenDeadKill,
1788 EvenUndef, BaseReg, false, BaseUndef, Pred, PredReg, TII,
1790 InsertLDR_STR(MBB, MBBI, OffImm + 4, isLd, NewOpc2, OddReg, OddDeadKill,
1791 OddUndef, BaseReg, BaseKill, BaseUndef, Pred, PredReg, TII,
1800 MBBI = MBB.erase(MBBI);
1804 /// An optimization pass to turn multiple LDR / STR ops of the same base and
1805 /// incrementing offset into LDM / STM ops.
1806 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
1808 unsigned CurrBase = 0;
1809 unsigned CurrOpc = ~0u;
1810 ARMCC::CondCodes CurrPred = ARMCC::AL;
1811 unsigned Position = 0;
1812 assert(Candidates.size() == 0);
1813 assert(MergeBaseCandidates.size() == 0);
1814 LiveRegsValid = false;
1816 for (MachineBasicBlock::iterator I = MBB.end(), MBBI; I != MBB.begin();
1818 // The instruction in front of the iterator is the one we look at.
1819 MBBI = std::prev(I);
1820 if (FixInvalidRegPairOp(MBB, MBBI))
1824 if (isMemoryOp(*MBBI)) {
1825 unsigned Opcode = MBBI->getOpcode();
1826 const MachineOperand &MO = MBBI->getOperand(0);
1827 Register Reg = MO.getReg();
1828 Register Base = getLoadStoreBaseOp(*MBBI).getReg();
1830 ARMCC::CondCodes Pred = getInstrPredicate(*MBBI, PredReg);
1831 int Offset = getMemoryOpOffset(*MBBI);
1832 if (CurrBase == 0) {
1833 // Start of a new chain.
1837 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1840 // Note: No need to match PredReg in the next if.
1841 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) {
1843 // r4 := ldr [r0, #8]
1844 // r4 := ldr [r0, #4]
1847 // If a load overrides the base register or a register loaded by
1848 // another load in our chain, we cannot take this instruction.
1849 bool Overlap = false;
1850 if (isLoadSingle(Opcode)) {
1851 Overlap = (Base == Reg);
1853 for (const MemOpQueueEntry &E : MemOps) {
1854 if (TRI->regsOverlap(Reg, E.MI->getOperand(0).getReg())) {
1863 // Check offset and sort memory operation into the current chain.
1864 if (Offset > MemOps.back().Offset) {
1865 MemOps.push_back(MemOpQueueEntry(*MBBI, Offset, Position));
1868 MemOpQueue::iterator MI, ME;
1869 for (MI = MemOps.begin(), ME = MemOps.end(); MI != ME; ++MI) {
1870 if (Offset < MI->Offset) {
1871 // Found a place to insert.
1874 if (Offset == MI->Offset) {
1875 // Collision, abort.
1880 if (MI != MemOps.end()) {
1881 MemOps.insert(MI, MemOpQueueEntry(*MBBI, Offset, Position));
1888 // Don't advance the iterator; The op will start a new chain next.
1891 // Fallthrough to look into existing chain.
1892 } else if (MBBI->isDebugInstr()) {
1894 } else if (MBBI->getOpcode() == ARM::t2LDRDi8 ||
1895 MBBI->getOpcode() == ARM::t2STRDi8) {
1896 // ARMPreAllocLoadStoreOpt has already formed some LDRD/STRD instructions
1897 // remember them because we may still be able to merge add/sub into them.
1898 MergeBaseCandidates.push_back(&*MBBI);
1901 // If we are here then the chain is broken; Extract candidates for a merge.
1902 if (MemOps.size() > 0) {
1903 FormCandidates(MemOps);
1904 // Reset for the next chain.
1907 CurrPred = ARMCC::AL;
1911 if (MemOps.size() > 0)
1912 FormCandidates(MemOps);
1914 // Sort candidates so they get processed from end to begin of the basic
1915 // block later; This is necessary for liveness calculation.
1916 auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
1917 return M0->InsertPos < M1->InsertPos;
1919 llvm::sort(Candidates, LessThan);
1921 // Go through list of candidates and merge.
1922 bool Changed = false;
1923 for (const MergeCandidate *Candidate : Candidates) {
1924 if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
1925 MachineInstr *Merged = MergeOpsUpdate(*Candidate);
1926 // Merge preceding/trailing base inc/dec into the merged op.
1929 unsigned Opcode = Merged->getOpcode();
1930 if (Opcode == ARM::t2STRDi8 || Opcode == ARM::t2LDRDi8)
1931 MergeBaseUpdateLSDouble(*Merged);
1933 MergeBaseUpdateLSMultiple(Merged);
1935 for (MachineInstr *MI : Candidate->Instrs) {
1936 if (MergeBaseUpdateLoadStore(MI))
1941 assert(Candidate->Instrs.size() == 1);
1942 if (MergeBaseUpdateLoadStore(Candidate->Instrs.front()))
1947 // Try to fold add/sub into the LDRD/STRD formed by ARMPreAllocLoadStoreOpt.
1948 for (MachineInstr *MI : MergeBaseCandidates)
1949 MergeBaseUpdateLSDouble(*MI);
1950 MergeBaseCandidates.clear();
1955 /// If this is a exit BB, try merging the return ops ("bx lr" and "mov pc, lr")
1956 /// into the preceding stack restore so it directly restore the value of LR
1958 /// ldmfd sp!, {..., lr}
1961 /// ldmfd sp!, {..., lr}
1964 /// ldmfd sp!, {..., pc}
1965 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) {
1966 // Thumb1 LDM doesn't allow high registers.
1967 if (isThumb1) return false;
1968 if (MBB.empty()) return false;
1970 MachineBasicBlock::iterator MBBI = MBB.getLastNonDebugInstr();
1971 if (MBBI != MBB.begin() && MBBI != MBB.end() &&
1972 (MBBI->getOpcode() == ARM::BX_RET ||
1973 MBBI->getOpcode() == ARM::tBX_RET ||
1974 MBBI->getOpcode() == ARM::MOVPCLR)) {
1975 MachineBasicBlock::iterator PrevI = std::prev(MBBI);
1976 // Ignore any debug instructions.
1977 while (PrevI->isDebugInstr() && PrevI != MBB.begin())
1979 MachineInstr &PrevMI = *PrevI;
1980 unsigned Opcode = PrevMI.getOpcode();
1981 if (Opcode == ARM::LDMIA_UPD || Opcode == ARM::LDMDA_UPD ||
1982 Opcode == ARM::LDMDB_UPD || Opcode == ARM::LDMIB_UPD ||
1983 Opcode == ARM::t2LDMIA_UPD || Opcode == ARM::t2LDMDB_UPD) {
1984 MachineOperand &MO = PrevMI.getOperand(PrevMI.getNumOperands() - 1);
1985 if (MO.getReg() != ARM::LR)
1987 unsigned NewOpc = (isThumb2 ? ARM::t2LDMIA_RET : ARM::LDMIA_RET);
1988 assert(((isThumb2 && Opcode == ARM::t2LDMIA_UPD) ||
1989 Opcode == ARM::LDMIA_UPD) && "Unsupported multiple load-return!");
1990 PrevMI.setDesc(TII->get(NewOpc));
1992 PrevMI.copyImplicitOps(*MBB.getParent(), *MBBI);
1994 // We now restore LR into PC so it is not live-out of the return block
1995 // anymore: Clear the CSI Restored bit.
1996 MachineFrameInfo &MFI = MBB.getParent()->getFrameInfo();
1997 // CSI should be fixed after PrologEpilog Insertion
1998 assert(MFI.isCalleeSavedInfoValid() && "CSI should be valid");
1999 for (CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
2000 if (Info.getReg() == ARM::LR) {
2001 Info.setRestored(false);
2011 bool ARMLoadStoreOpt::CombineMovBx(MachineBasicBlock &MBB) {
2012 MachineBasicBlock::iterator MBBI = MBB.getFirstTerminator();
2013 if (MBBI == MBB.begin() || MBBI == MBB.end() ||
2014 MBBI->getOpcode() != ARM::tBX_RET)
2017 MachineBasicBlock::iterator Prev = MBBI;
2019 if (Prev->getOpcode() != ARM::tMOVr || !Prev->definesRegister(ARM::LR))
2022 for (auto Use : Prev->uses())
2024 assert(STI->hasV4TOps());
2025 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(ARM::tBX))
2026 .addReg(Use.getReg(), RegState::Kill)
2027 .add(predOps(ARMCC::AL))
2028 .copyImplicitOps(*MBBI);
2034 llvm_unreachable("tMOVr doesn't kill a reg before tBX_RET?");
2037 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2038 if (skipFunction(Fn.getFunction()))
2042 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2043 TL = STI->getTargetLowering();
2044 AFI = Fn.getInfo<ARMFunctionInfo>();
2045 TII = STI->getInstrInfo();
2046 TRI = STI->getRegisterInfo();
2048 RegClassInfoValid = false;
2049 isThumb2 = AFI->isThumb2Function();
2050 isThumb1 = AFI->isThumbFunction() && !isThumb2;
2052 bool Modified = false;
2053 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E;
2055 MachineBasicBlock &MBB = *MFI;
2056 Modified |= LoadStoreMultipleOpti(MBB);
2057 if (STI->hasV5TOps())
2058 Modified |= MergeReturnIntoLDM(MBB);
2060 Modified |= CombineMovBx(MBB);
2063 Allocator.DestroyAll();
2067 #define ARM_PREALLOC_LOAD_STORE_OPT_NAME \
2068 "ARM pre- register allocation load / store optimization pass"
2072 /// Pre- register allocation pass that move load / stores from consecutive
2073 /// locations close to make it more likely they will be combined later.
2074 struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
2078 const DataLayout *TD;
2079 const TargetInstrInfo *TII;
2080 const TargetRegisterInfo *TRI;
2081 const ARMSubtarget *STI;
2082 MachineRegisterInfo *MRI;
2083 MachineDominatorTree *DT;
2084 MachineFunction *MF;
2086 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
2088 bool runOnMachineFunction(MachineFunction &Fn) override;
2090 StringRef getPassName() const override {
2091 return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
2094 void getAnalysisUsage(AnalysisUsage &AU) const override {
2095 AU.addRequired<AAResultsWrapperPass>();
2096 AU.addRequired<MachineDominatorTree>();
2097 AU.addPreserved<MachineDominatorTree>();
2098 MachineFunctionPass::getAnalysisUsage(AU);
2102 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
2103 unsigned &NewOpc, Register &EvenReg, Register &OddReg,
2104 Register &BaseReg, int &Offset, Register &PredReg,
2105 ARMCC::CondCodes &Pred, bool &isT2);
2106 bool RescheduleOps(MachineBasicBlock *MBB,
2107 SmallVectorImpl<MachineInstr *> &Ops,
2108 unsigned Base, bool isLd,
2109 DenseMap<MachineInstr*, unsigned> &MI2LocMap);
2110 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB);
2111 bool DistributeIncrements();
2112 bool DistributeIncrements(Register Base);
2115 } // end anonymous namespace
2117 char ARMPreAllocLoadStoreOpt::ID = 0;
2119 INITIALIZE_PASS_BEGIN(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2120 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2121 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
2122 INITIALIZE_PASS_END(ARMPreAllocLoadStoreOpt, "arm-prera-ldst-opt",
2123 ARM_PREALLOC_LOAD_STORE_OPT_NAME, false, false)
2125 // Limit the number of instructions to be rescheduled.
2126 // FIXME: tune this limit, and/or come up with some better heuristics.
2127 static cl::opt<unsigned> InstReorderLimit("arm-prera-ldst-opt-reorder-limit",
2128 cl::init(8), cl::Hidden);
2130 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) {
2131 if (AssumeMisalignedLoadStores || skipFunction(Fn.getFunction()))
2134 TD = &Fn.getDataLayout();
2135 STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
2136 TII = STI->getInstrInfo();
2137 TRI = STI->getRegisterInfo();
2138 MRI = &Fn.getRegInfo();
2139 DT = &getAnalysis<MachineDominatorTree>();
2141 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
2143 bool Modified = DistributeIncrements();
2144 for (MachineBasicBlock &MFI : Fn)
2145 Modified |= RescheduleLoadStoreInstrs(&MFI);
2150 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
2151 MachineBasicBlock::iterator I,
2152 MachineBasicBlock::iterator E,
2153 SmallPtrSetImpl<MachineInstr*> &MemOps,
2154 SmallSet<unsigned, 4> &MemRegs,
2155 const TargetRegisterInfo *TRI,
2156 AliasAnalysis *AA) {
2157 // Are there stores / loads / calls between them?
2158 SmallSet<unsigned, 4> AddedRegPressure;
2160 if (I->isDebugInstr() || MemOps.count(&*I))
2162 if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
2164 if (I->mayStore() || (!isLd && I->mayLoad()))
2165 for (MachineInstr *MemOp : MemOps)
2166 if (I->mayAlias(AA, *MemOp, /*UseTBAA*/ false))
2168 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
2169 MachineOperand &MO = I->getOperand(j);
2172 Register Reg = MO.getReg();
2173 if (MO.isDef() && TRI->regsOverlap(Reg, Base))
2175 if (Reg != Base && !MemRegs.count(Reg))
2176 AddedRegPressure.insert(Reg);
2180 // Estimate register pressure increase due to the transformation.
2181 if (MemRegs.size() <= 4)
2182 // Ok if we are moving small number of instructions.
2184 return AddedRegPressure.size() <= MemRegs.size() * 2;
2187 bool ARMPreAllocLoadStoreOpt::CanFormLdStDWord(
2188 MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl, unsigned &NewOpc,
2189 Register &FirstReg, Register &SecondReg, Register &BaseReg, int &Offset,
2190 Register &PredReg, ARMCC::CondCodes &Pred, bool &isT2) {
2191 // Make sure we're allowed to generate LDRD/STRD.
2192 if (!STI->hasV5TEOps())
2195 // FIXME: VLDRS / VSTRS -> VLDRD / VSTRD
2197 unsigned Opcode = Op0->getOpcode();
2198 if (Opcode == ARM::LDRi12) {
2200 } else if (Opcode == ARM::STRi12) {
2202 } else if (Opcode == ARM::t2LDRi8 || Opcode == ARM::t2LDRi12) {
2203 NewOpc = ARM::t2LDRDi8;
2206 } else if (Opcode == ARM::t2STRi8 || Opcode == ARM::t2STRi12) {
2207 NewOpc = ARM::t2STRDi8;
2214 // Make sure the base address satisfies i64 ld / st alignment requirement.
2215 // At the moment, we ignore the memoryoperand's value.
2216 // If we want to use AliasAnalysis, we should check it accordingly.
2217 if (!Op0->hasOneMemOperand() ||
2218 (*Op0->memoperands_begin())->isVolatile() ||
2219 (*Op0->memoperands_begin())->isAtomic())
2222 Align Alignment = (*Op0->memoperands_begin())->getAlign();
2223 const Function &Func = MF->getFunction();
2225 STI->hasV6Ops() ? TD->getABITypeAlign(Type::getInt64Ty(Func.getContext()))
2226 : Align(8); // Pre-v6 need 8-byte align
2227 if (Alignment < ReqAlign)
2230 // Then make sure the immediate offset fits.
2231 int OffImm = getMemoryOpOffset(*Op0);
2233 int Limit = (1 << 8) * Scale;
2234 if (OffImm >= Limit || (OffImm <= -Limit) || (OffImm & (Scale-1)))
2238 ARM_AM::AddrOpc AddSub = ARM_AM::add;
2240 AddSub = ARM_AM::sub;
2243 int Limit = (1 << 8) * Scale;
2244 if (OffImm >= Limit || (OffImm & (Scale-1)))
2246 Offset = ARM_AM::getAM3Opc(AddSub, OffImm);
2248 FirstReg = Op0->getOperand(0).getReg();
2249 SecondReg = Op1->getOperand(0).getReg();
2250 if (FirstReg == SecondReg)
2252 BaseReg = Op0->getOperand(1).getReg();
2253 Pred = getInstrPredicate(*Op0, PredReg);
2254 dl = Op0->getDebugLoc();
2258 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB,
2259 SmallVectorImpl<MachineInstr *> &Ops,
2260 unsigned Base, bool isLd,
2261 DenseMap<MachineInstr*, unsigned> &MI2LocMap) {
2262 bool RetVal = false;
2264 // Sort by offset (in reverse order).
2265 llvm::sort(Ops, [](const MachineInstr *LHS, const MachineInstr *RHS) {
2266 int LOffset = getMemoryOpOffset(*LHS);
2267 int ROffset = getMemoryOpOffset(*RHS);
2268 assert(LHS == RHS || LOffset != ROffset);
2269 return LOffset > ROffset;
2272 // The loads / stores of the same base are in order. Scan them from first to
2273 // last and check for the following:
2274 // 1. Any def of base.
2276 while (Ops.size() > 1) {
2277 unsigned FirstLoc = ~0U;
2278 unsigned LastLoc = 0;
2279 MachineInstr *FirstOp = nullptr;
2280 MachineInstr *LastOp = nullptr;
2282 unsigned LastOpcode = 0;
2283 unsigned LastBytes = 0;
2284 unsigned NumMove = 0;
2285 for (int i = Ops.size() - 1; i >= 0; --i) {
2286 // Make sure each operation has the same kind.
2287 MachineInstr *Op = Ops[i];
2289 = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
2290 if (LastOpcode && LSMOpcode != LastOpcode)
2293 // Check that we have a continuous set of offsets.
2294 int Offset = getMemoryOpOffset(*Op);
2295 unsigned Bytes = getLSMultipleTransferSize(Op);
2297 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
2301 // Don't try to reschedule too many instructions.
2302 if (NumMove == InstReorderLimit)
2305 // Found a mergable instruction; save information about it.
2307 LastOffset = Offset;
2309 LastOpcode = LSMOpcode;
2311 unsigned Loc = MI2LocMap[Op];
2312 if (Loc <= FirstLoc) {
2316 if (Loc >= LastLoc) {
2325 SmallPtrSet<MachineInstr*, 4> MemOps;
2326 SmallSet<unsigned, 4> MemRegs;
2327 for (size_t i = Ops.size() - NumMove, e = Ops.size(); i != e; ++i) {
2328 MemOps.insert(Ops[i]);
2329 MemRegs.insert(Ops[i]->getOperand(0).getReg());
2332 // Be conservative, if the instructions are too far apart, don't
2333 // move them. We want to limit the increase of register pressure.
2334 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
2336 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
2337 MemOps, MemRegs, TRI, AA);
2339 for (unsigned i = 0; i != NumMove; ++i)
2342 // This is the new location for the loads / stores.
2343 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
2344 while (InsertPos != MBB->end() &&
2345 (MemOps.count(&*InsertPos) || InsertPos->isDebugInstr()))
2348 // If we are moving a pair of loads / stores, see if it makes sense
2349 // to try to allocate a pair of registers that can form register pairs.
2350 MachineInstr *Op0 = Ops.back();
2351 MachineInstr *Op1 = Ops[Ops.size()-2];
2352 Register FirstReg, SecondReg;
2353 Register BaseReg, PredReg;
2354 ARMCC::CondCodes Pred = ARMCC::AL;
2356 unsigned NewOpc = 0;
2359 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc,
2360 FirstReg, SecondReg, BaseReg,
2361 Offset, PredReg, Pred, isT2)) {
2365 const MCInstrDesc &MCID = TII->get(NewOpc);
2366 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2367 MRI->constrainRegClass(FirstReg, TRC);
2368 MRI->constrainRegClass(SecondReg, TRC);
2370 // Form the pair instruction.
2372 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2373 .addReg(FirstReg, RegState::Define)
2374 .addReg(SecondReg, RegState::Define)
2376 // FIXME: We're converting from LDRi12 to an insn that still
2377 // uses addrmode2, so we need an explicit offset reg. It should
2378 // always by reg0 since we're transforming LDRi12s.
2381 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2382 MIB.cloneMergedMemRefs({Op0, Op1});
2383 LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2386 MachineInstrBuilder MIB = BuildMI(*MBB, InsertPos, dl, MCID)
2390 // FIXME: We're converting from LDRi12 to an insn that still
2391 // uses addrmode2, so we need an explicit offset reg. It should
2392 // always by reg0 since we're transforming STRi12s.
2395 MIB.addImm(Offset).addImm(Pred).addReg(PredReg);
2396 MIB.cloneMergedMemRefs({Op0, Op1});
2397 LLVM_DEBUG(dbgs() << "Formed " << *MIB << "\n");
2404 // Add register allocation hints to form register pairs.
2405 MRI->setRegAllocationHint(FirstReg, ARMRI::RegPairEven, SecondReg);
2406 MRI->setRegAllocationHint(SecondReg, ARMRI::RegPairOdd, FirstReg);
2409 for (unsigned i = 0; i != NumMove; ++i) {
2410 MachineInstr *Op = Ops.back();
2412 MBB->splice(InsertPos, MBB, Op);
2416 NumLdStMoved += NumMove;
2426 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) {
2427 bool RetVal = false;
2429 DenseMap<MachineInstr*, unsigned> MI2LocMap;
2430 using MapIt = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>::iterator;
2431 using Base2InstMap = DenseMap<unsigned, SmallVector<MachineInstr *, 4>>;
2432 using BaseVec = SmallVector<unsigned, 4>;
2433 Base2InstMap Base2LdsMap;
2434 Base2InstMap Base2StsMap;
2439 MachineBasicBlock::iterator MBBI = MBB->begin();
2440 MachineBasicBlock::iterator E = MBB->end();
2442 for (; MBBI != E; ++MBBI) {
2443 MachineInstr &MI = *MBBI;
2444 if (MI.isCall() || MI.isTerminator()) {
2445 // Stop at barriers.
2450 if (!MI.isDebugInstr())
2451 MI2LocMap[&MI] = ++Loc;
2453 if (!isMemoryOp(MI))
2456 if (getInstrPredicate(MI, PredReg) != ARMCC::AL)
2459 int Opc = MI.getOpcode();
2460 bool isLd = isLoadSingle(Opc);
2461 Register Base = MI.getOperand(1).getReg();
2462 int Offset = getMemoryOpOffset(MI);
2463 bool StopHere = false;
2464 auto FindBases = [&] (Base2InstMap &Base2Ops, BaseVec &Bases) {
2465 MapIt BI = Base2Ops.find(Base);
2466 if (BI == Base2Ops.end()) {
2467 Base2Ops[Base].push_back(&MI);
2468 Bases.push_back(Base);
2471 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) {
2472 if (Offset == getMemoryOpOffset(*BI->second[i])) {
2478 BI->second.push_back(&MI);
2482 FindBases(Base2LdsMap, LdBases);
2484 FindBases(Base2StsMap, StBases);
2487 // Found a duplicate (a base+offset combination that's seen earlier).
2494 // Re-schedule loads.
2495 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) {
2496 unsigned Base = LdBases[i];
2497 SmallVectorImpl<MachineInstr *> &Lds = Base2LdsMap[Base];
2499 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap);
2502 // Re-schedule stores.
2503 for (unsigned i = 0, e = StBases.size(); i != e; ++i) {
2504 unsigned Base = StBases[i];
2505 SmallVectorImpl<MachineInstr *> &Sts = Base2StsMap[Base];
2507 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap);
2511 Base2LdsMap.clear();
2512 Base2StsMap.clear();
2521 // Get the Base register operand index from the memory access MachineInst if we
2522 // should attempt to distribute postinc on it. Return -1 if not of a valid
2523 // instruction type. If it returns an index, it is assumed that instruction is a
2524 // r+i indexing mode, and getBaseOperandIndex() + 1 is the Offset index.
2525 static int getBaseOperandIndex(MachineInstr &MI) {
2526 switch (MI.getOpcode()) {
2527 case ARM::MVE_VLDRBS16:
2528 case ARM::MVE_VLDRBS32:
2529 case ARM::MVE_VLDRBU16:
2530 case ARM::MVE_VLDRBU32:
2531 case ARM::MVE_VLDRHS32:
2532 case ARM::MVE_VLDRHU32:
2533 case ARM::MVE_VLDRBU8:
2534 case ARM::MVE_VLDRHU16:
2535 case ARM::MVE_VLDRWU32:
2536 case ARM::MVE_VSTRB16:
2537 case ARM::MVE_VSTRB32:
2538 case ARM::MVE_VSTRH32:
2539 case ARM::MVE_VSTRBU8:
2540 case ARM::MVE_VSTRHU16:
2541 case ARM::MVE_VSTRWU32:
2547 static MachineInstr *createPostIncLoadStore(MachineInstr *MI, int Offset,
2549 const TargetInstrInfo *TII,
2550 const TargetRegisterInfo *TRI) {
2551 MachineFunction *MF = MI->getMF();
2552 MachineRegisterInfo &MRI = MF->getRegInfo();
2554 unsigned NewOpcode = getPostIndexedLoadStoreOpcode(
2555 MI->getOpcode(), Offset > 0 ? ARM_AM::add : ARM_AM::sub);
2557 const MCInstrDesc &MCID = TII->get(NewOpcode);
2558 // Constrain the def register class
2559 const TargetRegisterClass *TRC = TII->getRegClass(MCID, 0, TRI, *MF);
2560 MRI.constrainRegClass(NewReg, TRC);
2561 // And do the same for the base operand
2562 TRC = TII->getRegClass(MCID, 2, TRI, *MF);
2563 MRI.constrainRegClass(MI->getOperand(1).getReg(), TRC);
2565 return BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), MCID)
2566 .addReg(NewReg, RegState::Define)
2567 .add(MI->getOperand(0))
2568 .add(MI->getOperand(1))
2570 .add(MI->getOperand(3))
2571 .add(MI->getOperand(4))
2575 // Given a Base Register, optimise the load/store uses to attempt to create more
2576 // post-inc accesses. We do this by taking zero offset loads/stores with an add,
2577 // and convert them to a postinc load/store of the same type. Any subsequent
2578 // accesses will be adjusted to use and account for the post-inc value.
2580 // LDR #0 LDR_POSTINC #16
2585 bool ARMPreAllocLoadStoreOpt::DistributeIncrements(Register Base) {
2586 // We are looking for:
2587 // One zero offset load/store that can become postinc
2588 MachineInstr *BaseAccess = nullptr;
2589 // An increment that can be folded in
2590 MachineInstr *Increment = nullptr;
2591 // Other accesses after BaseAccess that will need to be updated to use the
2593 SmallPtrSet<MachineInstr *, 8> OtherAccesses;
2594 for (auto &Use : MRI->use_nodbg_instructions(Base)) {
2595 if (!Increment && getAddSubImmediate(Use) != 0) {
2600 int BaseOp = getBaseOperandIndex(Use);
2604 if (!Use.getOperand(BaseOp).isReg() ||
2605 Use.getOperand(BaseOp).getReg() != Base)
2607 if (Use.getOperand(BaseOp + 1).getImm() == 0)
2610 OtherAccesses.insert(&Use);
2613 if (!BaseAccess || !Increment ||
2614 BaseAccess->getParent() != Increment->getParent())
2617 if (Increment->definesRegister(ARM::CPSR) ||
2618 getInstrPredicate(*Increment, PredReg) != ARMCC::AL)
2621 LLVM_DEBUG(dbgs() << "\nAttempting to distribute increments on VirtualReg "
2622 << Base.virtRegIndex() << "\n");
2624 // Make sure that Increment has no uses before BaseAccess.
2625 for (MachineInstr &Use :
2626 MRI->use_nodbg_instructions(Increment->getOperand(0).getReg())) {
2627 if (!DT->dominates(BaseAccess, &Use) || &Use == BaseAccess) {
2628 LLVM_DEBUG(dbgs() << " BaseAccess doesn't dominate use of increment\n");
2633 // Make sure that Increment can be folded into Base
2634 int IncrementOffset = getAddSubImmediate(*Increment);
2635 unsigned NewPostIncOpcode = getPostIndexedLoadStoreOpcode(
2636 BaseAccess->getOpcode(), IncrementOffset > 0 ? ARM_AM::add : ARM_AM::sub);
2637 if (!isLegalAddressImm(NewPostIncOpcode, IncrementOffset, TII)) {
2638 LLVM_DEBUG(dbgs() << " Illegal addressing mode immediate on postinc\n");
2642 // And make sure that the negative value of increment can be added to all
2643 // other offsets after the BaseAccess. We rely on either
2644 // dominates(BaseAccess, OtherAccess) or dominates(OtherAccess, BaseAccess)
2645 // to keep things simple.
2646 SmallPtrSet<MachineInstr *, 4> SuccessorAccesses;
2647 for (auto *Use : OtherAccesses) {
2648 if (DT->dominates(BaseAccess, Use)) {
2649 SuccessorAccesses.insert(Use);
2650 unsigned BaseOp = getBaseOperandIndex(*Use);
2651 if (!isLegalAddressImm(
2653 Use->getOperand(BaseOp + 1).getImm() - IncrementOffset, TII)) {
2654 LLVM_DEBUG(dbgs() << " Illegal addressing mode immediate on use\n");
2657 } else if (!DT->dominates(Use, BaseAccess)) {
2659 dbgs() << " Unknown dominance relation between Base and Use\n");
2664 // Replace BaseAccess with a post inc
2665 LLVM_DEBUG(dbgs() << "Changing: "; BaseAccess->dump());
2666 LLVM_DEBUG(dbgs() << " And : "; Increment->dump());
2667 Register NewBaseReg = Increment->getOperand(0).getReg();
2668 MachineInstr *BaseAccessPost =
2669 createPostIncLoadStore(BaseAccess, IncrementOffset, NewBaseReg, TII, TRI);
2670 BaseAccess->eraseFromParent();
2671 Increment->eraseFromParent();
2672 (void)BaseAccessPost;
2673 LLVM_DEBUG(dbgs() << " To : "; BaseAccessPost->dump());
2675 for (auto *Use : SuccessorAccesses) {
2676 LLVM_DEBUG(dbgs() << "Changing: "; Use->dump());
2677 unsigned BaseOp = getBaseOperandIndex(*Use);
2678 Use->getOperand(BaseOp).setReg(NewBaseReg);
2679 int OldOffset = Use->getOperand(BaseOp + 1).getImm();
2680 Use->getOperand(BaseOp + 1).setImm(OldOffset - IncrementOffset);
2681 LLVM_DEBUG(dbgs() << " To : "; Use->dump());
2684 // Remove the kill flag from all uses of NewBaseReg, in case any old uses
2686 for (MachineOperand &Op : MRI->use_nodbg_operands(NewBaseReg))
2687 Op.setIsKill(false);
2691 bool ARMPreAllocLoadStoreOpt::DistributeIncrements() {
2692 bool Changed = false;
2693 SmallSetVector<Register, 4> Visited;
2694 for (auto &MBB : *MF) {
2695 for (auto &MI : MBB) {
2696 int BaseOp = getBaseOperandIndex(MI);
2697 if (BaseOp == -1 || !MI.getOperand(BaseOp).isReg())
2700 Register Base = MI.getOperand(BaseOp).getReg();
2701 if (!Base.isVirtual() || Visited.count(Base))
2704 Visited.insert(Base);
2708 for (auto Base : Visited)
2709 Changed |= DistributeIncrements(Base);
2714 /// Returns an instance of the load / store optimization pass.
2715 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) {
2717 return new ARMPreAllocLoadStoreOpt();
2718 return new ARMLoadStoreOpt();