1 //===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
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 /// Finalize v8.1-m low-overhead loops by converting the associated pseudo
10 /// instructions into machine operations.
11 /// The expectation is that the loop contains three pseudo instructions:
12 /// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
13 /// form should be in the preheader, whereas the while form should be in the
14 /// preheaders only predecessor.
15 /// - t2LoopDec - placed within in the loop body.
16 /// - t2LoopEnd - the loop latch terminator.
18 /// In addition to this, we also look for the presence of the VCTP instruction,
19 /// which determines whether we can generated the tail-predicated low-overhead
22 /// Assumptions and Dependencies:
23 /// Low-overhead loops are constructed and executed using a setup instruction:
24 /// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
25 /// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
26 /// but fixed polarity: WLS can only branch forwards and LE can only branch
27 /// backwards. These restrictions mean that this pass is dependent upon block
28 /// layout and block sizes, which is why it's the last pass to run. The same is
29 /// true for ConstantIslands, but this pass does not increase the size of the
30 /// basic blocks, nor does it change the CFG. Instructions are mainly removed
31 /// during the transform and pseudo instructions are replaced by real ones. In
32 /// some cases, when we have to revert to a 'normal' loop, we have to introduce
33 /// multiple instructions for a single pseudo (see RevertWhile and
34 /// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
35 /// are defined to be as large as this maximum sequence of replacement
38 /// A note on VPR.P0 (the lane mask):
39 /// VPT, VCMP, VPNOT and VCTP won't overwrite VPR.P0 when they update it in a
40 /// "VPT Active" context (which includes low-overhead loops and vpt blocks).
41 /// They will simply "and" the result of their calculation with the current
42 /// value of VPR.P0. You can think of it like this:
44 /// if VPT active: ; Between a DLSTP/LETP, or for predicated instrs
49 /// When we're inside the low-overhead loop (between DLSTP and LETP), we always
50 /// fall in the "VPT active" case, so we can consider that all VPR writes by
51 /// one of those instruction is actually a "and".
52 //===----------------------------------------------------------------------===//
55 #include "ARMBaseInstrInfo.h"
56 #include "ARMBaseRegisterInfo.h"
57 #include "ARMBasicBlockInfo.h"
58 #include "ARMSubtarget.h"
59 #include "MVETailPredUtils.h"
60 #include "Thumb2InstrInfo.h"
61 #include "llvm/ADT/SetOperations.h"
62 #include "llvm/ADT/SmallSet.h"
63 #include "llvm/CodeGen/LivePhysRegs.h"
64 #include "llvm/CodeGen/MachineFunctionPass.h"
65 #include "llvm/CodeGen/MachineLoopInfo.h"
66 #include "llvm/CodeGen/MachineLoopUtils.h"
67 #include "llvm/CodeGen/MachineRegisterInfo.h"
68 #include "llvm/CodeGen/Passes.h"
69 #include "llvm/CodeGen/ReachingDefAnalysis.h"
70 #include "llvm/MC/MCInstrDesc.h"
74 #define DEBUG_TYPE "arm-low-overhead-loops"
75 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
78 DisableTailPredication("arm-loloops-disable-tailpred", cl::Hidden,
79 cl::desc("Disable tail-predication in the ARM LowOverheadLoop pass"),
82 static bool isVectorPredicated(MachineInstr *MI) {
83 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
84 return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
87 static bool isVectorPredicate(MachineInstr *MI) {
88 return MI->findRegisterDefOperandIdx(ARM::VPR) != -1;
91 static bool hasVPRUse(MachineInstr &MI) {
92 return MI.findRegisterUseOperandIdx(ARM::VPR) != -1;
95 static bool isDomainMVE(MachineInstr *MI) {
96 uint64_t Domain = MI->getDesc().TSFlags & ARMII::DomainMask;
97 return Domain == ARMII::DomainMVE;
100 static bool shouldInspect(MachineInstr &MI) {
101 return isDomainMVE(&MI) || isVectorPredicate(&MI) || hasVPRUse(MI);
104 static bool isDo(MachineInstr *MI) {
105 return MI->getOpcode() != ARM::t2WhileLoopStart;
110 using InstSet = SmallPtrSetImpl<MachineInstr *>;
112 class PostOrderLoopTraversal {
114 MachineLoopInfo &MLI;
115 SmallPtrSet<MachineBasicBlock*, 4> Visited;
116 SmallVector<MachineBasicBlock*, 4> Order;
119 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
120 : ML(ML), MLI(MLI) { }
122 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
126 // Visit all the blocks within the loop, as well as exit blocks and any
127 // blocks properly dominating the header.
129 std::function<void(MachineBasicBlock*)> Search = [this, &Search]
130 (MachineBasicBlock *MBB) -> void {
131 if (Visited.count(MBB))
135 for (auto *Succ : MBB->successors()) {
136 if (!ML.contains(Succ))
140 Order.push_back(MBB);
143 // Insert exit blocks.
144 SmallVector<MachineBasicBlock*, 2> ExitBlocks;
145 ML.getExitBlocks(ExitBlocks);
146 append_range(Order, ExitBlocks);
148 // Then add the loop body.
149 Search(ML.getHeader());
151 // Then try the preheader and its predecessors.
152 std::function<void(MachineBasicBlock*)> GetPredecessor =
153 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
154 Order.push_back(MBB);
155 if (MBB->pred_size() == 1)
156 GetPredecessor(*MBB->pred_begin());
159 if (auto *Preheader = ML.getLoopPreheader())
160 GetPredecessor(Preheader);
161 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true))
162 GetPredecessor(Preheader);
166 struct PredicatedMI {
167 MachineInstr *MI = nullptr;
168 SetVector<MachineInstr*> Predicates;
171 PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
172 assert(I && "Instruction must not be null!");
173 Predicates.insert(Preds.begin(), Preds.end());
177 // Represent the current state of the VPR and hold all instances which
178 // represent a VPT block, which is a list of instructions that begins with a
179 // VPT/VPST and has a maximum of four proceeding instructions. All
180 // instructions within the block are predicated upon the vpr and we allow
181 // instructions to define the vpr within in the block too.
183 friend struct LowOverheadLoop;
185 SmallVector<MachineInstr *, 4> Insts;
187 static SmallVector<VPTState, 4> Blocks;
188 static SetVector<MachineInstr *> CurrentPredicates;
189 static std::map<MachineInstr *,
190 std::unique_ptr<PredicatedMI>> PredicatedInsts;
192 static void CreateVPTBlock(MachineInstr *MI) {
193 assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))
194 && "Can't begin VPT without predicate");
195 Blocks.emplace_back(MI);
196 // The execution of MI is predicated upon the current set of instructions
197 // that are AND'ed together to form the VPR predicate value. In the case
198 // that MI is a VPT, CurrentPredicates will also just be MI.
199 PredicatedInsts.emplace(
200 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
203 static void reset() {
205 PredicatedInsts.clear();
206 CurrentPredicates.clear();
209 static void addInst(MachineInstr *MI) {
210 Blocks.back().insert(MI);
211 PredicatedInsts.emplace(
212 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
215 static void addPredicate(MachineInstr *MI) {
216 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);
217 CurrentPredicates.insert(MI);
220 static void resetPredicate(MachineInstr *MI) {
221 LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);
222 CurrentPredicates.clear();
223 CurrentPredicates.insert(MI);
227 // Have we found an instruction within the block which defines the vpr? If
228 // so, not all the instructions in the block will have the same predicate.
229 static bool hasUniformPredicate(VPTState &Block) {
230 return getDivergent(Block) == nullptr;
233 // If it exists, return the first internal instruction which modifies the
235 static MachineInstr *getDivergent(VPTState &Block) {
236 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
237 for (unsigned i = 1; i < Insts.size(); ++i) {
238 MachineInstr *Next = Insts[i];
239 if (isVectorPredicate(Next))
240 return Next; // Found an instruction altering the vpr.
245 // Return whether the given instruction is predicated upon a VCTP.
246 static bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {
247 SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI]->Predicates;
248 if (Exclusive && Predicates.size() != 1)
250 for (auto *PredMI : Predicates)
256 // Is the VPST, controlling the block entry, predicated upon a VCTP.
257 static bool isEntryPredicatedOnVCTP(VPTState &Block,
258 bool Exclusive = false) {
259 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
260 return isPredicatedOnVCTP(Insts.front(), Exclusive);
263 // If this block begins with a VPT, we can check whether it's using
264 // at least one predicated input(s), as well as possible loop invariant
265 // which would result in it being implicitly predicated.
266 static bool hasImplicitlyValidVPT(VPTState &Block,
267 ReachingDefAnalysis &RDA) {
268 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
269 MachineInstr *VPT = Insts.front();
270 assert(isVPTOpcode(VPT->getOpcode()) &&
271 "Expected VPT block to begin with VPT/VPST");
273 if (VPT->getOpcode() == ARM::MVE_VPST)
276 auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
277 MachineInstr *Op = RDA.getMIOperand(MI, MI->getOperand(Idx));
278 return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);
281 auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
282 MachineOperand &MO = MI->getOperand(Idx);
283 if (!MO.isReg() || !MO.getReg())
286 SmallPtrSet<MachineInstr *, 2> Defs;
287 RDA.getGlobalReachingDefs(MI, MO.getReg(), Defs);
291 for (auto *Def : Defs)
292 if (Def->getParent() == VPT->getParent())
297 // Check that at least one of the operands is directly predicated on a
298 // vctp and allow an invariant value too.
299 return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
300 (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
301 (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
304 static bool isValid(ReachingDefAnalysis &RDA) {
305 // All predication within the loop should be based on vctp. If the block
306 // isn't predicated on entry, check whether the vctp is within the block
307 // and that all other instructions are then predicated on it.
308 for (auto &Block : Blocks) {
309 if (isEntryPredicatedOnVCTP(Block, false) ||
310 hasImplicitlyValidVPT(Block, RDA))
313 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
314 // We don't know how to convert a block with just a VPT;VCTP into
315 // anything valid once we remove the VCTP. For now just bail out.
316 assert(isVPTOpcode(Insts.front()->getOpcode()) &&
317 "Expected VPT block to start with a VPST or VPT!");
318 if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&
319 isVCTP(Insts.back()))
322 for (auto *MI : Insts) {
323 // Check that any internal VCTPs are 'Then' predicated.
324 if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)
326 // Skip other instructions that build up the predicate.
327 if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))
329 // Check that any other instructions are predicated upon a vctp.
330 // TODO: We could infer when VPTs are implicitly predicated on the
331 // vctp (when the operands are predicated).
332 if (!isPredicatedOnVCTP(MI)) {
333 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);
341 VPTState(MachineInstr *MI) { Insts.push_back(MI); }
343 void insert(MachineInstr *MI) {
345 // VPT/VPST + 4 predicated instructions.
346 assert(Insts.size() <= 5 && "Too many instructions in VPT block!");
349 bool containsVCTP() const {
350 for (auto *MI : Insts)
356 unsigned size() const { return Insts.size(); }
357 SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }
360 struct LowOverheadLoop {
363 MachineBasicBlock *Preheader = nullptr;
364 MachineLoopInfo &MLI;
365 ReachingDefAnalysis &RDA;
366 const TargetRegisterInfo &TRI;
367 const ARMBaseInstrInfo &TII;
368 MachineFunction *MF = nullptr;
369 MachineBasicBlock::iterator StartInsertPt;
370 MachineBasicBlock *StartInsertBB = nullptr;
371 MachineInstr *Start = nullptr;
372 MachineInstr *Dec = nullptr;
373 MachineInstr *End = nullptr;
374 MachineOperand TPNumElements;
375 SmallVector<MachineInstr*, 4> VCTPs;
376 SmallPtrSet<MachineInstr*, 4> ToRemove;
377 SmallPtrSet<MachineInstr*, 4> BlockMasksToRecompute;
379 bool CannotTailPredicate = false;
381 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI,
382 ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI,
383 const ARMBaseInstrInfo &TII)
384 : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII),
385 TPNumElements(MachineOperand::CreateImm(0)) {
386 MF = ML.getHeader()->getParent();
387 if (auto *MBB = ML.getLoopPreheader())
389 else if (auto *MBB = MLI.findLoopPreheader(&ML, true))
394 // If this is an MVE instruction, check that we know how to use tail
395 // predication with it. Record VPT blocks and return whether the
396 // instruction is valid for tail predication.
397 bool ValidateMVEInst(MachineInstr *MI);
399 void AnalyseMVEInst(MachineInstr *MI) {
400 CannotTailPredicate = !ValidateMVEInst(MI);
403 bool IsTailPredicationLegal() const {
404 // For now, let's keep things really simple and only support a single
405 // block for tail predication.
406 return !Revert && FoundAllComponents() && !VCTPs.empty() &&
407 !CannotTailPredicate && ML.getNumBlocks() == 1;
410 // Given that MI is a VCTP, check that is equivalent to any other VCTPs
412 bool AddVCTP(MachineInstr *MI);
414 // Check that the predication in the loop will be equivalent once we
415 // perform the conversion. Also ensure that we can provide the number
416 // of elements to the loop start instruction.
417 bool ValidateTailPredicate();
419 // Check that any values available outside of the loop will be the same
420 // after tail predication conversion.
421 bool ValidateLiveOuts();
423 // Is it safe to define LR with DLS/WLS?
424 // LR can be defined if it is the operand to start, because it's the same
425 // value, or if it's going to be equivalent to the operand to Start.
426 MachineInstr *isSafeToDefineLR();
428 // Check the branch targets are within range and we satisfy our
430 void Validate(ARMBasicBlockUtils *BBUtils);
432 bool FoundAllComponents() const {
433 return Start && Dec && End;
436 SmallVectorImpl<VPTState> &getVPTBlocks() {
437 return VPTState::Blocks;
440 // Return the operand for the loop start instruction. This will be the loop
441 // iteration count, or the number of elements if we're tail predicating.
442 MachineOperand &getLoopStartOperand() {
443 if (IsTailPredicationLegal())
444 return TPNumElements;
445 return isDo(Start) ? Start->getOperand(1) : Start->getOperand(0);
448 unsigned getStartOpcode() const {
449 bool IsDo = isDo(Start);
450 if (!IsTailPredicationLegal())
451 return IsDo ? ARM::t2DLS : ARM::t2WLS;
453 return VCTPOpcodeToLSTP(VCTPs.back()->getOpcode(), IsDo);
457 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
458 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
459 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
460 if (!VCTPs.empty()) {
461 dbgs() << "ARM Loops: Found VCTP(s):\n";
462 for (auto *MI : VCTPs)
463 dbgs() << " - " << *MI;
465 if (!FoundAllComponents())
466 dbgs() << "ARM Loops: Not a low-overhead loop.\n";
467 else if (!(Start && Dec && End))
468 dbgs() << "ARM Loops: Failed to find all loop components.\n";
472 class ARMLowOverheadLoops : public MachineFunctionPass {
473 MachineFunction *MF = nullptr;
474 MachineLoopInfo *MLI = nullptr;
475 ReachingDefAnalysis *RDA = nullptr;
476 const ARMBaseInstrInfo *TII = nullptr;
477 MachineRegisterInfo *MRI = nullptr;
478 const TargetRegisterInfo *TRI = nullptr;
479 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
484 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
486 void getAnalysisUsage(AnalysisUsage &AU) const override {
487 AU.setPreservesCFG();
488 AU.addRequired<MachineLoopInfo>();
489 AU.addRequired<ReachingDefAnalysis>();
490 MachineFunctionPass::getAnalysisUsage(AU);
493 bool runOnMachineFunction(MachineFunction &MF) override;
495 MachineFunctionProperties getRequiredProperties() const override {
496 return MachineFunctionProperties().set(
497 MachineFunctionProperties::Property::NoVRegs).set(
498 MachineFunctionProperties::Property::TracksLiveness);
501 StringRef getPassName() const override {
502 return ARM_LOW_OVERHEAD_LOOPS_NAME;
506 bool ProcessLoop(MachineLoop *ML);
508 bool RevertNonLoops();
510 void RevertWhile(MachineInstr *MI) const;
511 void RevertDo(MachineInstr *MI) const;
513 bool RevertLoopDec(MachineInstr *MI) const;
515 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
517 void RevertLoopEndDec(MachineInstr *MI) const;
519 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
521 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
523 void Expand(LowOverheadLoop &LoLoop);
525 void IterationCountDCE(LowOverheadLoop &LoLoop);
529 char ARMLowOverheadLoops::ID = 0;
531 SmallVector<VPTState, 4> VPTState::Blocks;
532 SetVector<MachineInstr *> VPTState::CurrentPredicates;
533 std::map<MachineInstr *,
534 std::unique_ptr<PredicatedMI>> VPTState::PredicatedInsts;
536 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
539 static bool TryRemove(MachineInstr *MI, ReachingDefAnalysis &RDA,
540 InstSet &ToRemove, InstSet &Ignore) {
542 // Check that we can remove all of Killed without having to modify any IT
544 auto WontCorruptITs = [](InstSet &Killed, ReachingDefAnalysis &RDA) {
545 // Collect the dead code and the MBBs in which they reside.
546 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
547 for (auto *Dead : Killed)
548 BasicBlocks.insert(Dead->getParent());
550 // Collect IT blocks in all affected basic blocks.
551 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
552 for (auto *MBB : BasicBlocks) {
553 for (auto &IT : *MBB) {
554 if (IT.getOpcode() != ARM::t2IT)
556 RDA.getReachingLocalUses(&IT, MCRegister::from(ARM::ITSTATE),
561 // If we're removing all of the instructions within an IT block, then
562 // also remove the IT instruction.
563 SmallPtrSet<MachineInstr *, 2> ModifiedITs;
564 SmallPtrSet<MachineInstr *, 2> RemoveITs;
565 for (auto *Dead : Killed) {
566 if (MachineOperand *MO = Dead->findRegisterUseOperand(ARM::ITSTATE)) {
567 MachineInstr *IT = RDA.getMIOperand(Dead, *MO);
568 RemoveITs.insert(IT);
569 auto &CurrentBlock = ITBlocks[IT];
570 CurrentBlock.erase(Dead);
571 if (CurrentBlock.empty())
572 ModifiedITs.erase(IT);
574 ModifiedITs.insert(IT);
577 if (!ModifiedITs.empty())
579 Killed.insert(RemoveITs.begin(), RemoveITs.end());
583 SmallPtrSet<MachineInstr *, 2> Uses;
584 if (!RDA.isSafeToRemove(MI, Uses, Ignore))
587 if (WontCorruptITs(Uses, RDA)) {
588 ToRemove.insert(Uses.begin(), Uses.end());
589 LLVM_DEBUG(dbgs() << "ARM Loops: Able to remove: " << *MI
590 << " - can also remove:\n";
591 for (auto *Use : Uses)
592 dbgs() << " - " << *Use);
594 SmallPtrSet<MachineInstr*, 4> Killed;
595 RDA.collectKilledOperands(MI, Killed);
596 if (WontCorruptITs(Killed, RDA)) {
597 ToRemove.insert(Killed.begin(), Killed.end());
598 LLVM_DEBUG(for (auto *Dead : Killed)
599 dbgs() << " - " << *Dead);
606 bool LowOverheadLoop::ValidateTailPredicate() {
607 if (!IsTailPredicationLegal()) {
608 LLVM_DEBUG(if (VCTPs.empty())
609 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
610 dbgs() << "ARM Loops: Tail-predication is not valid.\n");
614 assert(!VCTPs.empty() && "VCTP instruction expected but is not set");
615 assert(ML.getBlocks().size() == 1 &&
616 "Shouldn't be processing a loop with more than one block");
618 if (DisableTailPredication) {
619 LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");
623 if (!VPTState::isValid(RDA)) {
624 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid VPT state.\n");
628 if (!ValidateLiveOuts()) {
629 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");
633 // Check that creating a [W|D]LSTP, which will define LR with an element
634 // count instead of iteration count, won't affect any other instructions
635 // than the LoopStart and LoopDec.
636 // TODO: We should try to insert the [W|D]LSTP after any of the other uses.
637 Register StartReg = isDo(Start) ? Start->getOperand(1).getReg()
638 : Start->getOperand(0).getReg();
639 if (StartInsertPt == Start && StartReg == ARM::LR) {
640 if (auto *IterCount = RDA.getMIOperand(Start, isDo(Start) ? 1 : 0)) {
641 SmallPtrSet<MachineInstr *, 2> Uses;
642 RDA.getGlobalUses(IterCount, MCRegister::from(ARM::LR), Uses);
643 for (auto *Use : Uses) {
644 if (Use != Start && Use != Dec) {
645 LLVM_DEBUG(dbgs() << " ARM Loops: Found LR use: " << *Use);
652 // For tail predication, we need to provide the number of elements, instead
653 // of the iteration count, to the loop start instruction. The number of
654 // elements is provided to the vctp instruction, so we need to check that
655 // we can use this register at InsertPt.
656 MachineInstr *VCTP = VCTPs.back();
657 if (Start->getOpcode() == ARM::t2DoLoopStartTP) {
658 TPNumElements = Start->getOperand(2);
659 StartInsertPt = Start;
660 StartInsertBB = Start->getParent();
662 TPNumElements = VCTP->getOperand(1);
663 MCRegister NumElements = TPNumElements.getReg().asMCReg();
665 // If the register is defined within loop, then we can't perform TP.
666 // TODO: Check whether this is just a mov of a register that would be
668 if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
669 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
673 // The element count register maybe defined after InsertPt, in which case we
674 // need to try to move either InsertPt or the def so that the [w|d]lstp can
677 if (StartInsertPt != StartInsertBB->end() &&
678 !RDA.isReachingDefLiveOut(&*StartInsertPt, NumElements)) {
680 RDA.getLocalLiveOutMIDef(StartInsertBB, NumElements)) {
681 if (RDA.isSafeToMoveForwards(ElemDef, &*StartInsertPt)) {
682 ElemDef->removeFromParent();
683 StartInsertBB->insert(StartInsertPt, ElemDef);
685 << "ARM Loops: Moved element count def: " << *ElemDef);
686 } else if (RDA.isSafeToMoveBackwards(&*StartInsertPt, ElemDef)) {
687 StartInsertPt->removeFromParent();
688 StartInsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
690 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
692 // If we fail to move an instruction and the element count is provided
693 // by a mov, use the mov operand if it will have the same value at the
695 MachineOperand Operand = ElemDef->getOperand(1);
696 if (isMovRegOpcode(ElemDef->getOpcode()) &&
697 RDA.getUniqueReachingMIDef(ElemDef, Operand.getReg().asMCReg()) ==
698 RDA.getUniqueReachingMIDef(&*StartInsertPt,
699 Operand.getReg().asMCReg())) {
700 TPNumElements = Operand;
701 NumElements = TPNumElements.getReg();
704 << "ARM Loops: Unable to move element count to loop "
705 << "start instruction.\n");
712 // Especially in the case of while loops, InsertBB may not be the
713 // preheader, so we need to check that the register isn't redefined
714 // before entering the loop.
715 auto CannotProvideElements = [this](MachineBasicBlock *MBB,
716 MCRegister NumElements) {
719 // NumElements is redefined in this block.
720 if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
723 // Don't continue searching up through multiple predecessors.
724 if (MBB->pred_size() > 1)
730 // Search backwards for a def, until we get to InsertBB.
731 MachineBasicBlock *MBB = Preheader;
732 while (MBB && MBB != StartInsertBB) {
733 if (CannotProvideElements(MBB, NumElements)) {
734 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
737 MBB = *MBB->pred_begin();
741 // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect
742 // world the [w|d]lstp instruction would be last instruction in the preheader
743 // and so it would only affect instructions within the loop body. But due to
744 // scheduling, and/or the logic in this pass (above), the insertion point can
745 // be moved earlier. So if the Loop Start isn't the last instruction in the
746 // preheader, and if the initial element count is smaller than the vector
747 // width, the Loop Start instruction will immediately generate one or more
748 // false lane mask which can, incorrectly, affect the proceeding MVE
749 // instructions in the preheader.
750 if (std::any_of(StartInsertPt, StartInsertBB->end(), shouldInspect)) {
751 LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");
755 // Check that the value change of the element count is what we expect and
756 // that the predication will be equivalent. For this we need:
757 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
758 // and we can also allow register copies within the chain too.
759 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
760 return -getAddSubImmediate(*MI) == ExpectedVecWidth;
763 MachineBasicBlock *MBB = VCTP->getParent();
764 // Remove modifications to the element count since they have no purpose in a
765 // tail predicated loop. Explicitly refer to the vctp operand no matter which
766 // register NumElements has been assigned to, since that is what the
767 // modifications will be using
768 if (auto *Def = RDA.getUniqueReachingMIDef(
769 &MBB->back(), VCTP->getOperand(1).getReg().asMCReg())) {
770 SmallPtrSet<MachineInstr*, 2> ElementChain;
771 SmallPtrSet<MachineInstr*, 2> Ignore;
772 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
774 Ignore.insert(VCTPs.begin(), VCTPs.end());
776 if (TryRemove(Def, RDA, ElementChain, Ignore)) {
777 bool FoundSub = false;
779 for (auto *MI : ElementChain) {
780 if (isMovRegOpcode(MI->getOpcode()))
783 if (isSubImmOpcode(MI->getOpcode())) {
784 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {
785 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
791 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
796 ToRemove.insert(ElementChain.begin(), ElementChain.end());
802 static bool isRegInClass(const MachineOperand &MO,
803 const TargetRegisterClass *Class) {
804 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
807 // MVE 'narrowing' operate on half a lane, reading from half and writing
808 // to half, which are referred to has the top and bottom half. The other
809 // half retains its previous value.
810 static bool retainsPreviousHalfElement(const MachineInstr &MI) {
811 const MCInstrDesc &MCID = MI.getDesc();
812 uint64_t Flags = MCID.TSFlags;
813 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
816 // Some MVE instructions read from the top/bottom halves of their operand(s)
817 // and generate a vector result with result elements that are double the
818 // width of the input.
819 static bool producesDoubleWidthResult(const MachineInstr &MI) {
820 const MCInstrDesc &MCID = MI.getDesc();
821 uint64_t Flags = MCID.TSFlags;
822 return (Flags & ARMII::DoubleWidthResult) != 0;
825 static bool isHorizontalReduction(const MachineInstr &MI) {
826 const MCInstrDesc &MCID = MI.getDesc();
827 uint64_t Flags = MCID.TSFlags;
828 return (Flags & ARMII::HorizontalReduction) != 0;
831 // Can this instruction generate a non-zero result when given only zeroed
832 // operands? This allows us to know that, given operands with false bytes
833 // zeroed by masked loads, that the result will also contain zeros in those
835 static bool canGenerateNonZeros(const MachineInstr &MI) {
837 // Check for instructions which can write into a larger element size,
838 // possibly writing into a previous zero'd lane.
839 if (producesDoubleWidthResult(MI))
842 switch (MI.getOpcode()) {
845 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
846 // fp16 -> fp32 vector conversions.
847 // Instructions that perform a NOT will generate 1s from 0s.
850 // Count leading zeros will do just that!
851 case ARM::MVE_VCLZs8:
852 case ARM::MVE_VCLZs16:
853 case ARM::MVE_VCLZs32:
859 // Look at its register uses to see if it only can only receive zeros
860 // into its false lanes which would then produce zeros. Also check that
861 // the output register is also defined by an FalseLanesZero instruction
862 // so that if tail-predication happens, the lanes that aren't updated will
864 static bool producesFalseLanesZero(MachineInstr &MI,
865 const TargetRegisterClass *QPRs,
866 const ReachingDefAnalysis &RDA,
867 InstSet &FalseLanesZero) {
868 if (canGenerateNonZeros(MI))
871 bool isPredicated = isVectorPredicated(&MI);
872 // Predicated loads will write zeros to the falsely predicated bytes of the
873 // destination register.
877 auto IsZeroInit = [](MachineInstr *Def) {
878 return !isVectorPredicated(Def) &&
879 Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
880 Def->getOperand(1).getImm() == 0;
883 bool AllowScalars = isHorizontalReduction(MI);
884 for (auto &MO : MI.operands()) {
885 if (!MO.isReg() || !MO.getReg())
887 if (!isRegInClass(MO, QPRs) && AllowScalars)
890 // Check that this instruction will produce zeros in its false lanes:
891 // - If it only consumes false lanes zero or constant 0 (vmov #0)
892 // - If it's predicated, it only matters that it's def register already has
893 // false lane zeros, so we can ignore the uses.
894 SmallPtrSet<MachineInstr *, 2> Defs;
895 RDA.getGlobalReachingDefs(&MI, MO.getReg(), Defs);
896 for (auto *Def : Defs) {
897 if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))
899 if (MO.isUse() && isPredicated)
904 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
908 bool LowOverheadLoop::ValidateLiveOuts() {
909 // We want to find out if the tail-predicated version of this loop will
910 // produce the same values as the loop in its original form. For this to
911 // be true, the newly inserted implicit predication must not change the
912 // the (observable) results.
913 // We're doing this because many instructions in the loop will not be
914 // predicated and so the conversion from VPT predication to tail-predication
915 // can result in different values being produced; due to the tail-predication
916 // preventing many instructions from updating their falsely predicated
917 // lanes. This analysis assumes that all the instructions perform lane-wise
918 // operations and don't perform any exchanges.
919 // A masked load, whether through VPT or tail predication, will write zeros
920 // to any of the falsely predicated bytes. So, from the loads, we know that
921 // the false lanes are zeroed and here we're trying to track that those false
922 // lanes remain zero, or where they change, the differences are masked away
924 // All MVE stores have to be predicated, so we know that any predicate load
925 // operands, or stored results are equivalent already. Other explicitly
926 // predicated instructions will perform the same operation in the original
927 // loop and the tail-predicated form too. Because of this, we can insert
928 // loads, stores and other predicated instructions into our Predicated
929 // set and build from there.
930 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
931 SetVector<MachineInstr *> FalseLanesUnknown;
932 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
933 SmallPtrSet<MachineInstr *, 4> Predicated;
934 MachineBasicBlock *Header = ML.getHeader();
936 for (auto &MI : *Header) {
937 if (!shouldInspect(MI))
940 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
943 bool isPredicated = isVectorPredicated(&MI);
944 bool retainsOrReduces =
945 retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);
948 Predicated.insert(&MI);
949 if (producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero))
950 FalseLanesZero.insert(&MI);
951 else if (MI.getNumDefs() == 0)
953 else if (!isPredicated && retainsOrReduces)
955 else if (!isPredicated)
956 FalseLanesUnknown.insert(&MI);
959 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
960 SmallPtrSetImpl<MachineInstr *> &Predicated) {
961 SmallPtrSet<MachineInstr *, 2> Uses;
962 RDA.getGlobalUses(MI, MO.getReg().asMCReg(), Uses);
963 for (auto *Use : Uses) {
964 if (Use != MI && !Predicated.count(Use))
970 // Visit the unknowns in reverse so that we can start at the values being
971 // stored and then we can work towards the leaves, hopefully adding more
972 // instructions to Predicated. Successfully terminating the loop means that
973 // all the unknown values have to found to be masked by predicated user(s).
974 // For any unpredicated values, we store them in NonPredicated so that we
975 // can later check whether these form a reduction.
976 SmallPtrSet<MachineInstr*, 2> NonPredicated;
977 for (auto *MI : reverse(FalseLanesUnknown)) {
978 for (auto &MO : MI->operands()) {
979 if (!isRegInClass(MO, QPRs) || !MO.isDef())
981 if (!HasPredicatedUsers(MI, MO, Predicated)) {
982 LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : "
983 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
984 NonPredicated.insert(MI);
988 // Any unknown false lanes have been masked away by the user(s).
989 if (!NonPredicated.contains(MI))
990 Predicated.insert(MI);
993 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
994 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
995 ML.getExitBlocks(ExitBlocks);
996 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
997 assert(ExitBlocks.size() == 1 && "Expected a single exit block");
998 MachineBasicBlock *ExitBB = ExitBlocks.front();
999 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
1000 // TODO: Instead of blocking predication, we could move the vctp to the exit
1001 // block and calculate it's operand there in or the preheader.
1002 if (RegMask.PhysReg == ARM::VPR)
1004 // Check Q-regs that are live in the exit blocks. We don't collect scalars
1005 // because they won't be affected by lane predication.
1006 if (QPRs->contains(RegMask.PhysReg))
1007 if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
1008 LiveOutMIs.insert(MI);
1011 // We've already validated that any VPT predication within the loop will be
1012 // equivalent when we perform the predication transformation; so we know that
1013 // any VPT predicated instruction is predicated upon VCTP. Any live-out
1014 // instruction needs to be predicated, so check this here. The instructions
1015 // in NonPredicated have been found to be a reduction that we can ensure its
1017 for (auto *MI : LiveOutMIs) {
1018 if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {
1019 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to handle live out: " << *MI);
1027 void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {
1031 // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]
1032 // can only jump back.
1033 auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,
1034 ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {
1035 MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd
1036 ? End->getOperand(1).getMBB()
1037 : End->getOperand(2).getMBB();
1038 // TODO Maybe there's cases where the target doesn't have to be the header,
1039 // but for now be safe and revert.
1040 if (TgtBB != ML.getHeader()) {
1041 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");
1045 // The WLS and LE instructions have 12-bits for the label offset. WLS
1046 // requires a positive offset, while LE uses negative.
1047 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
1048 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
1049 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
1053 if (Start->getOpcode() == ARM::t2WhileLoopStart &&
1054 (BBUtils->getOffsetOf(Start) >
1055 BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
1056 !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
1057 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
1063 // Find a suitable position to insert the loop start instruction. It needs to
1064 // be able to safely define LR.
1065 auto FindStartInsertionPoint = [](MachineInstr *Start, MachineInstr *Dec,
1066 MachineBasicBlock::iterator &InsertPt,
1067 MachineBasicBlock *&InsertBB,
1068 ReachingDefAnalysis &RDA,
1069 InstSet &ToRemove) {
1070 // For a t2DoLoopStart it is always valid to use the start insertion point.
1071 // For WLS we can define LR if LR already contains the same value.
1072 if (isDo(Start) || Start->getOperand(0).getReg() == ARM::LR) {
1073 InsertPt = MachineBasicBlock::iterator(Start);
1074 InsertBB = Start->getParent();
1078 // We've found no suitable LR def and Start doesn't use LR directly. Can we
1079 // just define LR anyway?
1080 if (!RDA.isSafeToDefRegAt(Start, MCRegister::from(ARM::LR)))
1083 InsertPt = MachineBasicBlock::iterator(Start);
1084 InsertBB = Start->getParent();
1088 if (!FindStartInsertionPoint(Start, Dec, StartInsertPt, StartInsertBB, RDA,
1090 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
1094 LLVM_DEBUG(if (StartInsertPt == StartInsertBB->end())
1095 dbgs() << "ARM Loops: Will insert LoopStart at end of block\n";
1097 dbgs() << "ARM Loops: Will insert LoopStart at "
1101 Revert = !ValidateRanges(Start, End, BBUtils, ML);
1102 CannotTailPredicate = !ValidateTailPredicate();
1105 bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {
1106 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);
1107 if (VCTPs.empty()) {
1108 VCTPs.push_back(MI);
1112 // If we find another VCTP, check whether it uses the same value as the main VCTP.
1113 // If it does, store it in the VCTPs set, else refuse it.
1114 MachineInstr *Prev = VCTPs.back();
1115 if (!Prev->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
1116 !RDA.hasSameReachingDef(Prev, MI, MI->getOperand(1).getReg().asMCReg())) {
1117 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
1118 "definition from the main VCTP");
1121 VCTPs.push_back(MI);
1125 bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
1126 if (CannotTailPredicate)
1129 if (!shouldInspect(*MI))
1132 if (MI->getOpcode() == ARM::MVE_VPSEL ||
1133 MI->getOpcode() == ARM::MVE_VPNOT) {
1134 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
1135 // 1) It will use the VPR as a predicate operand, but doesn't have to be
1136 // instead a VPT block, which means we can assert while building up
1137 // the VPT block because we don't find another VPT or VPST to being a new
1139 // 2) VPSEL still requires a VPR operand even after tail predicating,
1140 // which means we can't remove it unless there is another
1141 // instruction, such as vcmp, that can provide the VPR def.
1145 // Record all VCTPs and check that they're equivalent to one another.
1146 if (isVCTP(MI) && !AddVCTP(MI))
1149 // Inspect uses first so that any instructions that alter the VPR don't
1150 // alter the predicate upon themselves.
1151 const MCInstrDesc &MCID = MI->getDesc();
1153 unsigned LastOpIdx = MI->getNumOperands() - 1;
1154 for (auto &Op : enumerate(reverse(MCID.operands()))) {
1155 const MachineOperand &MO = MI->getOperand(LastOpIdx - Op.index());
1156 if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)
1159 if (ARM::isVpred(Op.value().OperandType)) {
1160 VPTState::addInst(MI);
1162 } else if (MI->getOpcode() != ARM::MVE_VPST) {
1163 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
1168 // If we find an instruction that has been marked as not valid for tail
1169 // predication, only allow the instruction if it's contained within a valid
1171 bool RequiresExplicitPredication =
1172 (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;
1173 if (isDomainMVE(MI) && RequiresExplicitPredication) {
1174 LLVM_DEBUG(if (!IsUse)
1175 dbgs() << "ARM Loops: Can't tail predicate: " << *MI);
1179 // If the instruction is already explicitly predicated, then the conversion
1180 // will be fine, but ensure that all store operations are predicated.
1184 // If this instruction defines the VPR, update the predicate for the
1185 // proceeding instructions.
1186 if (isVectorPredicate(MI)) {
1187 // Clear the existing predicate when we're not in VPT Active state,
1188 // otherwise we add to it.
1189 if (!isVectorPredicated(MI))
1190 VPTState::resetPredicate(MI);
1192 VPTState::addPredicate(MI);
1195 // Finally once the predicate has been modified, we can start a new VPT
1196 // block if necessary.
1197 if (isVPTOpcode(MI->getOpcode()))
1198 VPTState::CreateVPTBlock(MI);
1203 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
1204 const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
1209 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
1211 MLI = &getAnalysis<MachineLoopInfo>();
1212 RDA = &getAnalysis<ReachingDefAnalysis>();
1213 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
1214 MRI = &MF->getRegInfo();
1215 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
1216 TRI = ST.getRegisterInfo();
1217 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
1218 BBUtils->computeAllBlockSizes();
1219 BBUtils->adjustBBOffsetsAfter(&MF->front());
1221 bool Changed = false;
1222 for (auto ML : *MLI) {
1223 if (ML->isOutermost())
1224 Changed |= ProcessLoop(ML);
1226 Changed |= RevertNonLoops();
1230 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
1232 bool Changed = false;
1234 // Process inner loops first.
1235 for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
1236 Changed |= ProcessLoop(*I);
1238 LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";
1239 if (auto *Preheader = ML->getLoopPreheader())
1240 dbgs() << " - " << Preheader->getName() << "\n";
1241 else if (auto *Preheader = MLI->findLoopPreheader(ML))
1242 dbgs() << " - " << Preheader->getName() << "\n";
1243 else if (auto *Preheader = MLI->findLoopPreheader(ML, true))
1244 dbgs() << " - " << Preheader->getName() << "\n";
1245 for (auto *MBB : ML->getBlocks())
1246 dbgs() << " - " << MBB->getName() << "\n";
1249 // Search the given block for a loop start instruction. If one isn't found,
1250 // and there's only one predecessor block, search that one too.
1251 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
1252 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
1253 for (auto &MI : *MBB) {
1254 if (isLoopStart(MI))
1257 if (MBB->pred_size() == 1)
1258 return SearchForStart(*MBB->pred_begin());
1262 LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
1263 // Search the preheader for the start intrinsic.
1264 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
1265 // with potentially multiple set.loop.iterations, so we need to enable this.
1266 if (LoLoop.Preheader)
1267 LoLoop.Start = SearchForStart(LoLoop.Preheader);
1271 // Find the low-overhead loop components and decide whether or not to fall
1272 // back to a normal loop. Also look for a vctp instructions and decide
1273 // whether we can convert that predicate using tail predication.
1274 for (auto *MBB : reverse(ML->getBlocks())) {
1275 for (auto &MI : *MBB) {
1276 if (MI.isDebugValue())
1278 else if (MI.getOpcode() == ARM::t2LoopDec)
1280 else if (MI.getOpcode() == ARM::t2LoopEnd)
1282 else if (MI.getOpcode() == ARM::t2LoopEndDec)
1283 LoLoop.End = LoLoop.Dec = &MI;
1284 else if (isLoopStart(MI))
1286 else if (MI.getDesc().isCall()) {
1287 // TODO: Though the call will require LE to execute again, does this
1288 // mean we should revert? Always executing LE hopefully should be
1289 // faster than performing a sub,cmp,br or even subs,br.
1290 LoLoop.Revert = true;
1291 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
1293 // Record VPR defs and build up their corresponding vpt blocks.
1294 // Check we know how to tail predicate any mve instructions.
1295 LoLoop.AnalyseMVEInst(&MI);
1300 LLVM_DEBUG(LoLoop.dump());
1301 if (!LoLoop.FoundAllComponents()) {
1302 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
1306 // Check that the only instruction using LoopDec is LoopEnd. This can only
1307 // happen when the Dec and End are separate, not a single t2LoopEndDec.
1308 // TODO: Check for copy chains that really have no effect.
1309 if (LoLoop.Dec != LoLoop.End) {
1310 SmallPtrSet<MachineInstr *, 2> Uses;
1311 RDA->getReachingLocalUses(LoLoop.Dec, MCRegister::from(ARM::LR), Uses);
1312 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
1313 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
1314 LoLoop.Revert = true;
1317 LoLoop.Validate(BBUtils.get());
1322 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1323 // beq that branches to the exit branch.
1324 // TODO: We could also try to generate a cbz if the value in LR is also in
1325 // another low register.
1326 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
1327 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
1328 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1329 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1330 ARM::tBcc : ARM::t2Bcc;
1332 RevertWhileLoopStart(MI, TII, BrOpc);
1335 void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {
1336 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);
1337 RevertDoLoopStart(MI, TII);
1340 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
1341 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
1342 MachineBasicBlock *MBB = MI->getParent();
1343 SmallPtrSet<MachineInstr*, 1> Ignore;
1344 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
1345 if (I->getOpcode() == ARM::t2LoopEnd) {
1351 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
1353 RDA->isSafeToDefRegAt(MI, MCRegister::from(ARM::CPSR), Ignore);
1355 llvm::RevertLoopDec(MI, TII, SetFlags);
1359 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1360 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
1361 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
1363 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1364 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1365 ARM::tBcc : ARM::t2Bcc;
1367 llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);
1370 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1371 void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {
1372 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);
1373 assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");
1374 MachineBasicBlock *MBB = MI->getParent();
1376 MachineInstrBuilder MIB =
1377 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri));
1378 MIB.addDef(ARM::LR);
1379 MIB.add(MI->getOperand(1));
1381 MIB.addImm(ARMCC::AL);
1382 MIB.addReg(ARM::NoRegister);
1383 MIB.addReg(ARM::CPSR);
1384 MIB->getOperand(5).setIsDef(true);
1386 MachineBasicBlock *DestBB = MI->getOperand(2).getMBB();
1388 BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc;
1391 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
1392 MIB.add(MI->getOperand(2)); // branch target
1393 MIB.addImm(ARMCC::NE); // condition code
1394 MIB.addReg(ARM::CPSR);
1396 MI->eraseFromParent();
1399 // Perform dead code elimation on the loop iteration count setup expression.
1400 // If we are tail-predicating, the number of elements to be processed is the
1401 // operand of the VCTP instruction in the vector body, see getCount(), which is
1402 // register $r3 in this example:
1404 // $lr = big-itercount-expression
1406 // $lr = t2DoLoopStart renamable $lr
1409 // $vpr = MVE_VCTP32 renamable $r3
1410 // renamable $lr = t2LoopDec killed renamable $lr, 1
1411 // t2LoopEnd renamable $lr, %vector.body
1414 // What we would like achieve here is to replace the do-loop start pseudo
1415 // instruction t2DoLoopStart with:
1417 // $lr = MVE_DLSTP_32 killed renamable $r3
1419 // Thus, $r3 which defines the number of elements, is written to $lr,
1420 // and then we want to delete the whole chain that used to define $lr,
1421 // see the comment below how this chain could look like.
1423 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
1424 if (!LoLoop.IsTailPredicationLegal())
1427 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
1430 RDA->getMIOperand(LoLoop.Start, isDo(LoLoop.Start) ? 1 : 0);
1432 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
1436 // Collect and remove the users of iteration count.
1437 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,
1439 if (!TryRemove(Def, *RDA, LoLoop.ToRemove, Killed))
1440 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
1443 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
1444 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
1445 // When using tail-predication, try to delete the dead code that was used to
1446 // calculate the number of loop iterations.
1447 IterationCountDCE(LoLoop);
1449 MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;
1450 MachineInstr *Start = LoLoop.Start;
1451 MachineBasicBlock *MBB = LoLoop.StartInsertBB;
1452 unsigned Opc = LoLoop.getStartOpcode();
1453 MachineOperand &Count = LoLoop.getLoopStartOperand();
1455 MachineInstrBuilder MIB =
1456 BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));
1458 MIB.addDef(ARM::LR);
1461 MIB.add(Start->getOperand(1));
1463 LoLoop.ToRemove.insert(Start);
1464 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
1468 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
1469 auto RemovePredicate = [](MachineInstr *MI) {
1470 if (MI->isDebugInstr())
1472 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
1473 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
1474 assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");
1475 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
1476 "Expected Then predicate!");
1477 MI->getOperand(PIdx).setImm(ARMVCC::None);
1478 MI->getOperand(PIdx + 1).setReg(0);
1481 for (auto &Block : LoLoop.getVPTBlocks()) {
1482 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
1484 auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {
1485 assert(TheVCMP && "Replacing a removed or non-existent VCMP");
1486 // Replace the VCMP with a VPT
1487 MachineInstrBuilder MIB =
1488 BuildMI(*At->getParent(), At, At->getDebugLoc(),
1489 TII->get(VCMPOpcodeToVPT(TheVCMP->getOpcode())));
1490 MIB.addImm(ARMVCC::Then);
1492 MIB.add(TheVCMP->getOperand(1));
1494 MIB.add(TheVCMP->getOperand(2));
1495 // The comparison code, e.g. ge, eq, lt
1496 MIB.add(TheVCMP->getOperand(3));
1497 LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);
1498 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1499 LoLoop.ToRemove.insert(TheVCMP);
1503 if (VPTState::isEntryPredicatedOnVCTP(Block, /*exclusive*/ true)) {
1504 MachineInstr *VPST = Insts.front();
1505 if (VPTState::hasUniformPredicate(Block)) {
1506 // A vpt block starting with VPST, is only predicated upon vctp and has no
1507 // internal vpr defs:
1509 // - Unpredicate the remaining instructions.
1510 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1511 for (unsigned i = 1; i < Insts.size(); ++i)
1512 RemovePredicate(Insts[i]);
1514 // The VPT block has a non-uniform predicate but it uses a vpst and its
1515 // entry is guarded only by a vctp, which means we:
1516 // - Need to remove the original vpst.
1517 // - Then need to unpredicate any following instructions, until
1518 // we come across the divergent vpr def.
1519 // - Insert a new vpst to predicate the instruction(s) that following
1520 // the divergent vpr def.
1521 MachineInstr *Divergent = VPTState::getDivergent(Block);
1522 MachineBasicBlock *MBB = Divergent->getParent();
1523 auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);
1524 while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())
1527 bool DivergentNextIsPredicated =
1528 DivergentNext != MBB->end() &&
1529 getVPTInstrPredicate(*DivergentNext) != ARMVCC::None;
1531 for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;
1533 RemovePredicate(&*I);
1535 // Check if the instruction defining vpr is a vcmp so it can be combined
1536 // with the VPST This should be the divergent instruction
1537 MachineInstr *VCMP =
1538 VCMPOpcodeToVPT(Divergent->getOpcode()) != 0 ? Divergent : nullptr;
1540 if (DivergentNextIsPredicated) {
1541 // Insert a VPST at the divergent only if the next instruction
1542 // would actually use it. A VCMP following a VPST can be
1543 // merged into a VPT so do that instead if the VCMP exists.
1545 // Create a VPST (with a null mask for now, we'll recompute it
1547 MachineInstrBuilder MIB =
1548 BuildMI(*Divergent->getParent(), Divergent,
1549 Divergent->getDebugLoc(), TII->get(ARM::MVE_VPST));
1551 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
1552 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1554 // No RDA checks are necessary here since the VPST would have been
1555 // directly after the VCMP
1556 ReplaceVCMPWithVPT(VCMP, VCMP);
1560 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1561 LoLoop.ToRemove.insert(VPST);
1562 } else if (Block.containsVCTP()) {
1563 // The vctp will be removed, so either the entire block will be dead or
1564 // the block mask of the vp(s)t will need to be recomputed.
1565 MachineInstr *VPST = Insts.front();
1566 if (Block.size() == 2) {
1567 assert(VPST->getOpcode() == ARM::MVE_VPST &&
1568 "Found a VPST in an otherwise empty vpt block");
1569 LoLoop.ToRemove.insert(VPST);
1571 LoLoop.BlockMasksToRecompute.insert(VPST);
1572 } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {
1573 // If this block starts with a VPST then attempt to merge it with the
1574 // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT
1575 // block that no longer exists
1576 MachineInstr *VPST = Insts.front();
1577 auto Next = ++MachineBasicBlock::iterator(VPST);
1578 assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&
1579 "The instruction after a VPST must be predicated");
1581 MachineInstr *VprDef = RDA->getUniqueReachingMIDef(VPST, ARM::VPR);
1582 if (VprDef && VCMPOpcodeToVPT(VprDef->getOpcode()) &&
1583 !LoLoop.ToRemove.contains(VprDef)) {
1584 MachineInstr *VCMP = VprDef;
1585 // The VCMP and VPST can only be merged if the VCMP's operands will have
1586 // the same values at the VPST.
1587 // If any of the instructions between the VCMP and VPST are predicated
1588 // then a different code path is expected to have merged the VCMP and
1590 if (!std::any_of(++MachineBasicBlock::iterator(VCMP),
1591 MachineBasicBlock::iterator(VPST), hasVPRUse) &&
1592 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(1).getReg()) &&
1593 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(2).getReg())) {
1594 ReplaceVCMPWithVPT(VCMP, VPST);
1595 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1596 LoLoop.ToRemove.insert(VPST);
1602 LoLoop.ToRemove.insert(LoLoop.VCTPs.begin(), LoLoop.VCTPs.end());
1605 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
1607 // Combine the LoopDec and LoopEnd instructions into LE(TP).
1608 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
1609 MachineInstr *End = LoLoop.End;
1610 MachineBasicBlock *MBB = End->getParent();
1611 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
1612 ARM::MVE_LETP : ARM::t2LEUpdate;
1613 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
1615 MIB.addDef(ARM::LR);
1616 unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;
1617 MIB.add(End->getOperand(Off + 0));
1618 MIB.add(End->getOperand(Off + 1));
1619 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
1620 LoLoop.ToRemove.insert(LoLoop.Dec);
1621 LoLoop.ToRemove.insert(End);
1625 // TODO: We should be able to automatically remove these branches before we
1626 // get here - probably by teaching analyzeBranch about the pseudo
1628 // If there is an unconditional branch, after I, that just branches to the
1629 // next block, remove it.
1630 auto RemoveDeadBranch = [](MachineInstr *I) {
1631 MachineBasicBlock *BB = I->getParent();
1632 MachineInstr *Terminator = &BB->instr_back();
1633 if (Terminator->isUnconditionalBranch() && I != Terminator) {
1634 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
1635 if (BB->isLayoutSuccessor(Succ)) {
1636 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
1637 Terminator->eraseFromParent();
1642 if (LoLoop.Revert) {
1643 if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
1644 RevertWhile(LoLoop.Start);
1646 RevertDo(LoLoop.Start);
1647 if (LoLoop.Dec == LoLoop.End)
1648 RevertLoopEndDec(LoLoop.End);
1650 RevertLoopEnd(LoLoop.End, RevertLoopDec(LoLoop.Dec));
1652 LoLoop.Start = ExpandLoopStart(LoLoop);
1653 RemoveDeadBranch(LoLoop.Start);
1654 LoLoop.End = ExpandLoopEnd(LoLoop);
1655 RemoveDeadBranch(LoLoop.End);
1656 if (LoLoop.IsTailPredicationLegal())
1657 ConvertVPTBlocks(LoLoop);
1658 for (auto *I : LoLoop.ToRemove) {
1659 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
1660 I->eraseFromParent();
1662 for (auto *I : LoLoop.BlockMasksToRecompute) {
1663 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
1664 recomputeVPTBlockMask(*I);
1665 LLVM_DEBUG(dbgs() << " ... done: " << *I);
1669 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
1671 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
1672 for (auto *MBB : PostOrder) {
1673 recomputeLiveIns(*MBB);
1674 // FIXME: For some reason, the live-in print order is non-deterministic for
1675 // our tests and I can't out why... So just sort them.
1676 MBB->sortUniqueLiveIns();
1679 for (auto *MBB : reverse(PostOrder))
1680 recomputeLivenessFlags(*MBB);
1682 // We've moved, removed and inserted new instructions, so update RDA.
1686 bool ARMLowOverheadLoops::RevertNonLoops() {
1687 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1688 bool Changed = false;
1690 for (auto &MBB : *MF) {
1691 SmallVector<MachineInstr*, 4> Starts;
1692 SmallVector<MachineInstr*, 4> Decs;
1693 SmallVector<MachineInstr*, 4> Ends;
1694 SmallVector<MachineInstr *, 4> EndDecs;
1696 for (auto &I : MBB) {
1698 Starts.push_back(&I);
1699 else if (I.getOpcode() == ARM::t2LoopDec)
1701 else if (I.getOpcode() == ARM::t2LoopEnd)
1703 else if (I.getOpcode() == ARM::t2LoopEndDec)
1704 EndDecs.push_back(&I);
1707 if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty())
1712 for (auto *Start : Starts) {
1713 if (Start->getOpcode() == ARM::t2WhileLoopStart)
1718 for (auto *Dec : Decs)
1721 for (auto *End : Ends)
1723 for (auto *End : EndDecs)
1724 RevertLoopEndDec(End);
1729 FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1730 return new ARMLowOverheadLoops();