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, t2WhileLoopStartLR 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/SetVector.h"
63 #include "llvm/ADT/SmallSet.h"
64 #include "llvm/CodeGen/LivePhysRegs.h"
65 #include "llvm/CodeGen/MachineFrameInfo.h"
66 #include "llvm/CodeGen/MachineFunctionPass.h"
67 #include "llvm/CodeGen/MachineLoopInfo.h"
68 #include "llvm/CodeGen/MachineLoopUtils.h"
69 #include "llvm/CodeGen/MachineRegisterInfo.h"
70 #include "llvm/CodeGen/Passes.h"
71 #include "llvm/CodeGen/ReachingDefAnalysis.h"
72 #include "llvm/MC/MCInstrDesc.h"
76 #define DEBUG_TYPE "arm-low-overhead-loops"
77 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
80 DisableTailPredication("arm-loloops-disable-tailpred", cl::Hidden,
81 cl::desc("Disable tail-predication in the ARM LowOverheadLoop pass"),
85 DisableOmitDLS("arm-disable-omit-dls", cl::Hidden,
86 cl::desc("Disable omitting 'dls lr, lr' instructions"),
89 static bool isVectorPredicated(MachineInstr *MI) {
90 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
91 return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
94 static bool isVectorPredicate(MachineInstr *MI) {
95 return MI->findRegisterDefOperandIdx(ARM::VPR) != -1;
98 static bool hasVPRUse(MachineInstr &MI) {
99 return MI.findRegisterUseOperandIdx(ARM::VPR) != -1;
102 static bool isDomainMVE(MachineInstr *MI) {
103 uint64_t Domain = MI->getDesc().TSFlags & ARMII::DomainMask;
104 return Domain == ARMII::DomainMVE;
107 static int getVecSize(const MachineInstr &MI) {
108 const MCInstrDesc &MCID = MI.getDesc();
109 uint64_t Flags = MCID.TSFlags;
110 return (Flags & ARMII::VecSize) >> ARMII::VecSizeShift;
113 static bool shouldInspect(MachineInstr &MI) {
114 if (MI.isDebugInstr())
116 return isDomainMVE(&MI) || isVectorPredicate(&MI) || hasVPRUse(MI);
121 using InstSet = SmallPtrSetImpl<MachineInstr *>;
123 class PostOrderLoopTraversal {
125 MachineLoopInfo &MLI;
126 SmallPtrSet<MachineBasicBlock*, 4> Visited;
127 SmallVector<MachineBasicBlock*, 4> Order;
130 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
131 : ML(ML), MLI(MLI) { }
133 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
137 // Visit all the blocks within the loop, as well as exit blocks and any
138 // blocks properly dominating the header.
140 std::function<void(MachineBasicBlock*)> Search = [this, &Search]
141 (MachineBasicBlock *MBB) -> void {
142 if (Visited.count(MBB))
146 for (auto *Succ : MBB->successors()) {
147 if (!ML.contains(Succ))
151 Order.push_back(MBB);
154 // Insert exit blocks.
155 SmallVector<MachineBasicBlock*, 2> ExitBlocks;
156 ML.getExitBlocks(ExitBlocks);
157 append_range(Order, ExitBlocks);
159 // Then add the loop body.
160 Search(ML.getHeader());
162 // Then try the preheader and its predecessors.
163 std::function<void(MachineBasicBlock*)> GetPredecessor =
164 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
165 Order.push_back(MBB);
166 if (MBB->pred_size() == 1)
167 GetPredecessor(*MBB->pred_begin());
170 if (auto *Preheader = ML.getLoopPreheader())
171 GetPredecessor(Preheader);
172 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true, true))
173 GetPredecessor(Preheader);
177 struct PredicatedMI {
178 MachineInstr *MI = nullptr;
179 SetVector<MachineInstr*> Predicates;
182 PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
183 assert(I && "Instruction must not be null!");
184 Predicates.insert(Preds.begin(), Preds.end());
188 // Represent the current state of the VPR and hold all instances which
189 // represent a VPT block, which is a list of instructions that begins with a
190 // VPT/VPST and has a maximum of four proceeding instructions. All
191 // instructions within the block are predicated upon the vpr and we allow
192 // instructions to define the vpr within in the block too.
194 friend struct LowOverheadLoop;
196 SmallVector<MachineInstr *, 4> Insts;
198 static SmallVector<VPTState, 4> Blocks;
199 static SetVector<MachineInstr *> CurrentPredicates;
200 static std::map<MachineInstr *,
201 std::unique_ptr<PredicatedMI>> PredicatedInsts;
203 static void CreateVPTBlock(MachineInstr *MI) {
204 assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))
205 && "Can't begin VPT without predicate");
206 Blocks.emplace_back(MI);
207 // The execution of MI is predicated upon the current set of instructions
208 // that are AND'ed together to form the VPR predicate value. In the case
209 // that MI is a VPT, CurrentPredicates will also just be MI.
210 PredicatedInsts.emplace(
211 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
214 static void reset() {
216 PredicatedInsts.clear();
217 CurrentPredicates.clear();
220 static void addInst(MachineInstr *MI) {
221 Blocks.back().insert(MI);
222 PredicatedInsts.emplace(
223 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
226 static void addPredicate(MachineInstr *MI) {
227 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);
228 CurrentPredicates.insert(MI);
231 static void resetPredicate(MachineInstr *MI) {
232 LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);
233 CurrentPredicates.clear();
234 CurrentPredicates.insert(MI);
238 // Have we found an instruction within the block which defines the vpr? If
239 // so, not all the instructions in the block will have the same predicate.
240 static bool hasUniformPredicate(VPTState &Block) {
241 return getDivergent(Block) == nullptr;
244 // If it exists, return the first internal instruction which modifies the
246 static MachineInstr *getDivergent(VPTState &Block) {
247 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
248 for (unsigned i = 1; i < Insts.size(); ++i) {
249 MachineInstr *Next = Insts[i];
250 if (isVectorPredicate(Next))
251 return Next; // Found an instruction altering the vpr.
256 // Return whether the given instruction is predicated upon a VCTP.
257 static bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {
258 SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI]->Predicates;
259 if (Exclusive && Predicates.size() != 1)
261 return llvm::any_of(Predicates, isVCTP);
264 // Is the VPST, controlling the block entry, predicated upon a VCTP.
265 static bool isEntryPredicatedOnVCTP(VPTState &Block,
266 bool Exclusive = false) {
267 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
268 return isPredicatedOnVCTP(Insts.front(), Exclusive);
271 // If this block begins with a VPT, we can check whether it's using
272 // at least one predicated input(s), as well as possible loop invariant
273 // which would result in it being implicitly predicated.
274 static bool hasImplicitlyValidVPT(VPTState &Block,
275 ReachingDefAnalysis &RDA) {
276 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
277 MachineInstr *VPT = Insts.front();
278 assert(isVPTOpcode(VPT->getOpcode()) &&
279 "Expected VPT block to begin with VPT/VPST");
281 if (VPT->getOpcode() == ARM::MVE_VPST)
284 auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
285 MachineInstr *Op = RDA.getMIOperand(MI, MI->getOperand(Idx));
286 return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);
289 auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
290 MachineOperand &MO = MI->getOperand(Idx);
291 if (!MO.isReg() || !MO.getReg())
294 SmallPtrSet<MachineInstr *, 2> Defs;
295 RDA.getGlobalReachingDefs(MI, MO.getReg(), Defs);
299 for (auto *Def : Defs)
300 if (Def->getParent() == VPT->getParent())
305 // Check that at least one of the operands is directly predicated on a
306 // vctp and allow an invariant value too.
307 return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
308 (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
309 (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
312 static bool isValid(ReachingDefAnalysis &RDA) {
313 // All predication within the loop should be based on vctp. If the block
314 // isn't predicated on entry, check whether the vctp is within the block
315 // and that all other instructions are then predicated on it.
316 for (auto &Block : Blocks) {
317 if (isEntryPredicatedOnVCTP(Block, false) ||
318 hasImplicitlyValidVPT(Block, RDA))
321 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
322 // We don't know how to convert a block with just a VPT;VCTP into
323 // anything valid once we remove the VCTP. For now just bail out.
324 assert(isVPTOpcode(Insts.front()->getOpcode()) &&
325 "Expected VPT block to start with a VPST or VPT!");
326 if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&
327 isVCTP(Insts.back()))
330 for (auto *MI : Insts) {
331 // Check that any internal VCTPs are 'Then' predicated.
332 if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)
334 // Skip other instructions that build up the predicate.
335 if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))
337 // Check that any other instructions are predicated upon a vctp.
338 // TODO: We could infer when VPTs are implicitly predicated on the
339 // vctp (when the operands are predicated).
340 if (!isPredicatedOnVCTP(MI)) {
341 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);
349 VPTState(MachineInstr *MI) { Insts.push_back(MI); }
351 void insert(MachineInstr *MI) {
353 // VPT/VPST + 4 predicated instructions.
354 assert(Insts.size() <= 5 && "Too many instructions in VPT block!");
357 bool containsVCTP() const {
358 return llvm::any_of(Insts, isVCTP);
361 unsigned size() const { return Insts.size(); }
362 SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }
365 struct LowOverheadLoop {
368 MachineBasicBlock *Preheader = nullptr;
369 MachineLoopInfo &MLI;
370 ReachingDefAnalysis &RDA;
371 const TargetRegisterInfo &TRI;
372 const ARMBaseInstrInfo &TII;
373 MachineFunction *MF = nullptr;
374 MachineBasicBlock::iterator StartInsertPt;
375 MachineBasicBlock *StartInsertBB = nullptr;
376 MachineInstr *Start = nullptr;
377 MachineInstr *Dec = nullptr;
378 MachineInstr *End = nullptr;
379 MachineOperand TPNumElements;
380 SmallVector<MachineInstr *, 4> VCTPs;
381 SmallPtrSet<MachineInstr *, 4> ToRemove;
382 SmallPtrSet<MachineInstr *, 4> BlockMasksToRecompute;
383 SmallPtrSet<MachineInstr *, 4> DoubleWidthResultInstrs;
384 SmallPtrSet<MachineInstr *, 4> VMOVCopies;
386 bool CannotTailPredicate = false;
388 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI,
389 ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI,
390 const ARMBaseInstrInfo &TII)
391 : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII),
392 TPNumElements(MachineOperand::CreateImm(0)) {
393 MF = ML.getHeader()->getParent();
394 if (auto *MBB = ML.getLoopPreheader())
396 else if (auto *MBB = MLI.findLoopPreheader(&ML, true, true))
401 // If this is an MVE instruction, check that we know how to use tail
402 // predication with it. Record VPT blocks and return whether the
403 // instruction is valid for tail predication.
404 bool ValidateMVEInst(MachineInstr *MI);
406 void AnalyseMVEInst(MachineInstr *MI) {
407 CannotTailPredicate = !ValidateMVEInst(MI);
410 bool IsTailPredicationLegal() const {
411 // For now, let's keep things really simple and only support a single
412 // block for tail predication.
413 return !Revert && FoundAllComponents() && !VCTPs.empty() &&
414 !CannotTailPredicate && ML.getNumBlocks() == 1;
417 // Given that MI is a VCTP, check that is equivalent to any other VCTPs
419 bool AddVCTP(MachineInstr *MI);
421 // Check that the predication in the loop will be equivalent once we
422 // perform the conversion. Also ensure that we can provide the number
423 // of elements to the loop start instruction.
424 bool ValidateTailPredicate();
426 // Check that any values available outside of the loop will be the same
427 // after tail predication conversion.
428 bool ValidateLiveOuts();
430 // Check the branch targets are within range and we satisfy our
432 void Validate(ARMBasicBlockUtils *BBUtils);
434 bool FoundAllComponents() const {
435 return Start && Dec && End;
438 SmallVectorImpl<VPTState> &getVPTBlocks() {
439 return VPTState::Blocks;
442 // Return the operand for the loop start instruction. This will be the loop
443 // iteration count, or the number of elements if we're tail predicating.
444 MachineOperand &getLoopStartOperand() {
445 if (IsTailPredicationLegal())
446 return TPNumElements;
447 return Start->getOperand(1);
450 unsigned getStartOpcode() const {
451 bool IsDo = isDoLoopStart(*Start);
452 if (!IsTailPredicationLegal())
453 return IsDo ? ARM::t2DLS : ARM::t2WLS;
455 return VCTPOpcodeToLSTP(VCTPs.back()->getOpcode(), IsDo);
459 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
460 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
461 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
462 if (!VCTPs.empty()) {
463 dbgs() << "ARM Loops: Found VCTP(s):\n";
464 for (auto *MI : VCTPs)
465 dbgs() << " - " << *MI;
467 if (!FoundAllComponents())
468 dbgs() << "ARM Loops: Not a low-overhead loop.\n";
469 else if (!(Start && Dec && End))
470 dbgs() << "ARM Loops: Failed to find all loop components.\n";
474 class ARMLowOverheadLoops : public MachineFunctionPass {
475 MachineFunction *MF = nullptr;
476 MachineLoopInfo *MLI = nullptr;
477 ReachingDefAnalysis *RDA = nullptr;
478 const ARMBaseInstrInfo *TII = nullptr;
479 MachineRegisterInfo *MRI = nullptr;
480 const TargetRegisterInfo *TRI = nullptr;
481 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
486 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
488 void getAnalysisUsage(AnalysisUsage &AU) const override {
489 AU.setPreservesCFG();
490 AU.addRequired<MachineLoopInfo>();
491 AU.addRequired<ReachingDefAnalysis>();
492 MachineFunctionPass::getAnalysisUsage(AU);
495 bool runOnMachineFunction(MachineFunction &MF) override;
497 MachineFunctionProperties getRequiredProperties() const override {
498 return MachineFunctionProperties().set(
499 MachineFunctionProperties::Property::NoVRegs).set(
500 MachineFunctionProperties::Property::TracksLiveness);
503 StringRef getPassName() const override {
504 return ARM_LOW_OVERHEAD_LOOPS_NAME;
508 bool ProcessLoop(MachineLoop *ML);
510 bool RevertNonLoops();
512 void RevertWhile(MachineInstr *MI) const;
513 void RevertDo(MachineInstr *MI) const;
515 bool RevertLoopDec(MachineInstr *MI) const;
517 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
519 void RevertLoopEndDec(MachineInstr *MI) const;
521 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
523 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
525 void Expand(LowOverheadLoop &LoLoop);
527 void IterationCountDCE(LowOverheadLoop &LoLoop);
531 char ARMLowOverheadLoops::ID = 0;
533 SmallVector<VPTState, 4> VPTState::Blocks;
534 SetVector<MachineInstr *> VPTState::CurrentPredicates;
535 std::map<MachineInstr *,
536 std::unique_ptr<PredicatedMI>> VPTState::PredicatedInsts;
538 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
541 static bool TryRemove(MachineInstr *MI, ReachingDefAnalysis &RDA,
542 InstSet &ToRemove, InstSet &Ignore) {
544 // Check that we can remove all of Killed without having to modify any IT
546 auto WontCorruptITs = [](InstSet &Killed, ReachingDefAnalysis &RDA) {
547 // Collect the dead code and the MBBs in which they reside.
548 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
549 for (auto *Dead : Killed)
550 BasicBlocks.insert(Dead->getParent());
552 // Collect IT blocks in all affected basic blocks.
553 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
554 for (auto *MBB : BasicBlocks) {
555 for (auto &IT : *MBB) {
556 if (IT.getOpcode() != ARM::t2IT)
558 RDA.getReachingLocalUses(&IT, MCRegister::from(ARM::ITSTATE),
563 // If we're removing all of the instructions within an IT block, then
564 // also remove the IT instruction.
565 SmallPtrSet<MachineInstr *, 2> ModifiedITs;
566 SmallPtrSet<MachineInstr *, 2> RemoveITs;
567 for (auto *Dead : Killed) {
568 if (MachineOperand *MO = Dead->findRegisterUseOperand(ARM::ITSTATE)) {
569 MachineInstr *IT = RDA.getMIOperand(Dead, *MO);
570 RemoveITs.insert(IT);
571 auto &CurrentBlock = ITBlocks[IT];
572 CurrentBlock.erase(Dead);
573 if (CurrentBlock.empty())
574 ModifiedITs.erase(IT);
576 ModifiedITs.insert(IT);
579 if (!ModifiedITs.empty())
581 Killed.insert(RemoveITs.begin(), RemoveITs.end());
585 SmallPtrSet<MachineInstr *, 2> Uses;
586 if (!RDA.isSafeToRemove(MI, Uses, Ignore))
589 if (WontCorruptITs(Uses, RDA)) {
590 ToRemove.insert(Uses.begin(), Uses.end());
591 LLVM_DEBUG(dbgs() << "ARM Loops: Able to remove: " << *MI
592 << " - can also remove:\n";
593 for (auto *Use : Uses)
594 dbgs() << " - " << *Use);
596 SmallPtrSet<MachineInstr*, 4> Killed;
597 RDA.collectKilledOperands(MI, Killed);
598 if (WontCorruptITs(Killed, RDA)) {
599 ToRemove.insert(Killed.begin(), Killed.end());
600 LLVM_DEBUG(for (auto *Dead : Killed)
601 dbgs() << " - " << *Dead);
608 bool LowOverheadLoop::ValidateTailPredicate() {
609 if (!IsTailPredicationLegal()) {
610 LLVM_DEBUG(if (VCTPs.empty())
611 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
612 dbgs() << "ARM Loops: Tail-predication is not valid.\n");
616 assert(!VCTPs.empty() && "VCTP instruction expected but is not set");
617 assert(ML.getBlocks().size() == 1 &&
618 "Shouldn't be processing a loop with more than one block");
620 if (DisableTailPredication) {
621 LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");
625 if (!VPTState::isValid(RDA)) {
626 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid VPT state.\n");
630 if (!ValidateLiveOuts()) {
631 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");
635 // For tail predication, we need to provide the number of elements, instead
636 // of the iteration count, to the loop start instruction. The number of
637 // elements is provided to the vctp instruction, so we need to check that
638 // we can use this register at InsertPt.
639 MachineInstr *VCTP = VCTPs.back();
640 if (Start->getOpcode() == ARM::t2DoLoopStartTP ||
641 Start->getOpcode() == ARM::t2WhileLoopStartTP) {
642 TPNumElements = Start->getOperand(2);
643 StartInsertPt = Start;
644 StartInsertBB = Start->getParent();
646 TPNumElements = VCTP->getOperand(1);
647 MCRegister NumElements = TPNumElements.getReg().asMCReg();
649 // If the register is defined within loop, then we can't perform TP.
650 // TODO: Check whether this is just a mov of a register that would be
652 if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
653 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
657 // The element count register maybe defined after InsertPt, in which case we
658 // need to try to move either InsertPt or the def so that the [w|d]lstp can
661 if (StartInsertPt != StartInsertBB->end() &&
662 !RDA.isReachingDefLiveOut(&*StartInsertPt, NumElements)) {
664 RDA.getLocalLiveOutMIDef(StartInsertBB, NumElements)) {
665 if (RDA.isSafeToMoveForwards(ElemDef, &*StartInsertPt)) {
666 ElemDef->removeFromParent();
667 StartInsertBB->insert(StartInsertPt, ElemDef);
669 << "ARM Loops: Moved element count def: " << *ElemDef);
670 } else if (RDA.isSafeToMoveBackwards(&*StartInsertPt, ElemDef)) {
671 StartInsertPt->removeFromParent();
672 StartInsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
674 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
676 // If we fail to move an instruction and the element count is provided
677 // by a mov, use the mov operand if it will have the same value at the
679 MachineOperand Operand = ElemDef->getOperand(1);
680 if (isMovRegOpcode(ElemDef->getOpcode()) &&
681 RDA.getUniqueReachingMIDef(ElemDef, Operand.getReg().asMCReg()) ==
682 RDA.getUniqueReachingMIDef(&*StartInsertPt,
683 Operand.getReg().asMCReg())) {
684 TPNumElements = Operand;
685 NumElements = TPNumElements.getReg();
688 << "ARM Loops: Unable to move element count to loop "
689 << "start instruction.\n");
696 // Especially in the case of while loops, InsertBB may not be the
697 // preheader, so we need to check that the register isn't redefined
698 // before entering the loop.
699 auto CannotProvideElements = [this](MachineBasicBlock *MBB,
700 MCRegister NumElements) {
703 // NumElements is redefined in this block.
704 if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
707 // Don't continue searching up through multiple predecessors.
708 if (MBB->pred_size() > 1)
714 // Search backwards for a def, until we get to InsertBB.
715 MachineBasicBlock *MBB = Preheader;
716 while (MBB && MBB != StartInsertBB) {
717 if (CannotProvideElements(MBB, NumElements)) {
718 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
721 MBB = *MBB->pred_begin();
725 // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect
726 // world the [w|d]lstp instruction would be last instruction in the preheader
727 // and so it would only affect instructions within the loop body. But due to
728 // scheduling, and/or the logic in this pass (above), the insertion point can
729 // be moved earlier. So if the Loop Start isn't the last instruction in the
730 // preheader, and if the initial element count is smaller than the vector
731 // width, the Loop Start instruction will immediately generate one or more
732 // false lane mask which can, incorrectly, affect the proceeding MVE
733 // instructions in the preheader.
734 if (std::any_of(StartInsertPt, StartInsertBB->end(), shouldInspect)) {
735 LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");
739 // For any DoubleWidthResultInstrs we found whilst scanning instructions, they
740 // need to compute an output size that is smaller than the VCTP mask operates
741 // on. The VecSize of the DoubleWidthResult is the larger vector size - the
742 // size it extends into, so any VCTP VecSize <= is valid.
743 unsigned VCTPVecSize = getVecSize(*VCTP);
744 for (MachineInstr *MI : DoubleWidthResultInstrs) {
745 unsigned InstrVecSize = getVecSize(*MI);
746 if (InstrVecSize > VCTPVecSize) {
747 LLVM_DEBUG(dbgs() << "ARM Loops: Double width result larger than VCTP "
748 << "VecSize:\n" << *MI);
753 // Check that the value change of the element count is what we expect and
754 // that the predication will be equivalent. For this we need:
755 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
756 // and we can also allow register copies within the chain too.
757 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
758 return -getAddSubImmediate(*MI) == ExpectedVecWidth;
761 MachineBasicBlock *MBB = VCTP->getParent();
762 // Remove modifications to the element count since they have no purpose in a
763 // tail predicated loop. Explicitly refer to the vctp operand no matter which
764 // register NumElements has been assigned to, since that is what the
765 // modifications will be using
766 if (auto *Def = RDA.getUniqueReachingMIDef(
767 &MBB->back(), VCTP->getOperand(1).getReg().asMCReg())) {
768 SmallPtrSet<MachineInstr*, 2> ElementChain;
769 SmallPtrSet<MachineInstr*, 2> Ignore;
770 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
772 Ignore.insert(VCTPs.begin(), VCTPs.end());
774 if (TryRemove(Def, RDA, ElementChain, Ignore)) {
775 bool FoundSub = false;
777 for (auto *MI : ElementChain) {
778 if (isMovRegOpcode(MI->getOpcode()))
781 if (isSubImmOpcode(MI->getOpcode())) {
782 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {
783 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
789 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
794 ToRemove.insert(ElementChain.begin(), ElementChain.end());
798 // If we converted the LoopStart to a t2DoLoopStartTP/t2WhileLoopStartTP, we
799 // can also remove any extra instructions in the preheader, which often
800 // includes a now unused MOV.
801 if ((Start->getOpcode() == ARM::t2DoLoopStartTP ||
802 Start->getOpcode() == ARM::t2WhileLoopStartTP) &&
803 Preheader && !Preheader->empty() &&
804 !RDA.hasLocalDefBefore(VCTP, VCTP->getOperand(1).getReg())) {
805 if (auto *Def = RDA.getUniqueReachingMIDef(
806 &Preheader->back(), VCTP->getOperand(1).getReg().asMCReg())) {
807 SmallPtrSet<MachineInstr*, 2> Ignore;
808 Ignore.insert(VCTPs.begin(), VCTPs.end());
809 TryRemove(Def, RDA, ToRemove, Ignore);
816 static bool isRegInClass(const MachineOperand &MO,
817 const TargetRegisterClass *Class) {
818 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
821 // MVE 'narrowing' operate on half a lane, reading from half and writing
822 // to half, which are referred to has the top and bottom half. The other
823 // half retains its previous value.
824 static bool retainsPreviousHalfElement(const MachineInstr &MI) {
825 const MCInstrDesc &MCID = MI.getDesc();
826 uint64_t Flags = MCID.TSFlags;
827 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
830 // Some MVE instructions read from the top/bottom halves of their operand(s)
831 // and generate a vector result with result elements that are double the
832 // width of the input.
833 static bool producesDoubleWidthResult(const MachineInstr &MI) {
834 const MCInstrDesc &MCID = MI.getDesc();
835 uint64_t Flags = MCID.TSFlags;
836 return (Flags & ARMII::DoubleWidthResult) != 0;
839 static bool isHorizontalReduction(const MachineInstr &MI) {
840 const MCInstrDesc &MCID = MI.getDesc();
841 uint64_t Flags = MCID.TSFlags;
842 return (Flags & ARMII::HorizontalReduction) != 0;
845 // Can this instruction generate a non-zero result when given only zeroed
846 // operands? This allows us to know that, given operands with false bytes
847 // zeroed by masked loads, that the result will also contain zeros in those
849 static bool canGenerateNonZeros(const MachineInstr &MI) {
851 // Check for instructions which can write into a larger element size,
852 // possibly writing into a previous zero'd lane.
853 if (producesDoubleWidthResult(MI))
856 switch (MI.getOpcode()) {
859 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
860 // fp16 -> fp32 vector conversions.
861 // Instructions that perform a NOT will generate 1s from 0s.
864 // Count leading zeros will do just that!
865 case ARM::MVE_VCLZs8:
866 case ARM::MVE_VCLZs16:
867 case ARM::MVE_VCLZs32:
873 // Look at its register uses to see if it only can only receive zeros
874 // into its false lanes which would then produce zeros. Also check that
875 // the output register is also defined by an FalseLanesZero instruction
876 // so that if tail-predication happens, the lanes that aren't updated will
878 static bool producesFalseLanesZero(MachineInstr &MI,
879 const TargetRegisterClass *QPRs,
880 const ReachingDefAnalysis &RDA,
881 InstSet &FalseLanesZero) {
882 if (canGenerateNonZeros(MI))
885 bool isPredicated = isVectorPredicated(&MI);
886 // Predicated loads will write zeros to the falsely predicated bytes of the
887 // destination register.
891 auto IsZeroInit = [](MachineInstr *Def) {
892 return !isVectorPredicated(Def) &&
893 Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
894 Def->getOperand(1).getImm() == 0;
897 bool AllowScalars = isHorizontalReduction(MI);
898 for (auto &MO : MI.operands()) {
899 if (!MO.isReg() || !MO.getReg())
901 if (!isRegInClass(MO, QPRs) && AllowScalars)
903 // Skip the lr predicate reg
904 int PIdx = llvm::findFirstVPTPredOperandIdx(MI);
905 if (PIdx != -1 && (int)MO.getOperandNo() == PIdx + 2)
908 // Check that this instruction will produce zeros in its false lanes:
909 // - If it only consumes false lanes zero or constant 0 (vmov #0)
910 // - If it's predicated, it only matters that it's def register already has
911 // false lane zeros, so we can ignore the uses.
912 SmallPtrSet<MachineInstr *, 2> Defs;
913 RDA.getGlobalReachingDefs(&MI, MO.getReg(), Defs);
916 for (auto *Def : Defs) {
917 if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))
919 if (MO.isUse() && isPredicated)
924 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
928 bool LowOverheadLoop::ValidateLiveOuts() {
929 // We want to find out if the tail-predicated version of this loop will
930 // produce the same values as the loop in its original form. For this to
931 // be true, the newly inserted implicit predication must not change the
932 // the (observable) results.
933 // We're doing this because many instructions in the loop will not be
934 // predicated and so the conversion from VPT predication to tail-predication
935 // can result in different values being produced; due to the tail-predication
936 // preventing many instructions from updating their falsely predicated
937 // lanes. This analysis assumes that all the instructions perform lane-wise
938 // operations and don't perform any exchanges.
939 // A masked load, whether through VPT or tail predication, will write zeros
940 // to any of the falsely predicated bytes. So, from the loads, we know that
941 // the false lanes are zeroed and here we're trying to track that those false
942 // lanes remain zero, or where they change, the differences are masked away
944 // All MVE stores have to be predicated, so we know that any predicate load
945 // operands, or stored results are equivalent already. Other explicitly
946 // predicated instructions will perform the same operation in the original
947 // loop and the tail-predicated form too. Because of this, we can insert
948 // loads, stores and other predicated instructions into our Predicated
949 // set and build from there.
950 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
951 SetVector<MachineInstr *> FalseLanesUnknown;
952 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
953 SmallPtrSet<MachineInstr *, 4> Predicated;
954 MachineBasicBlock *Header = ML.getHeader();
956 LLVM_DEBUG(dbgs() << "ARM Loops: Validating Live outs\n");
958 for (auto &MI : *Header) {
959 if (!shouldInspect(MI))
962 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
965 bool isPredicated = isVectorPredicated(&MI);
966 bool retainsOrReduces =
967 retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);
970 Predicated.insert(&MI);
971 if (producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero))
972 FalseLanesZero.insert(&MI);
973 else if (MI.getNumDefs() == 0)
975 else if (!isPredicated && retainsOrReduces) {
976 LLVM_DEBUG(dbgs() << " Unpredicated instruction that retainsOrReduces: " << MI);
978 } else if (!isPredicated && MI.getOpcode() != ARM::MQPRCopy)
979 FalseLanesUnknown.insert(&MI);
983 dbgs() << " Predicated:\n";
984 for (auto *I : Predicated)
986 dbgs() << " FalseLanesZero:\n";
987 for (auto *I : FalseLanesZero)
989 dbgs() << " FalseLanesUnknown:\n";
990 for (auto *I : FalseLanesUnknown)
994 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
995 SmallPtrSetImpl<MachineInstr *> &Predicated) {
996 SmallPtrSet<MachineInstr *, 2> Uses;
997 RDA.getGlobalUses(MI, MO.getReg().asMCReg(), Uses);
998 for (auto *Use : Uses) {
999 if (Use != MI && !Predicated.count(Use))
1005 // Visit the unknowns in reverse so that we can start at the values being
1006 // stored and then we can work towards the leaves, hopefully adding more
1007 // instructions to Predicated. Successfully terminating the loop means that
1008 // all the unknown values have to found to be masked by predicated user(s).
1009 // For any unpredicated values, we store them in NonPredicated so that we
1010 // can later check whether these form a reduction.
1011 SmallPtrSet<MachineInstr*, 2> NonPredicated;
1012 for (auto *MI : reverse(FalseLanesUnknown)) {
1013 for (auto &MO : MI->operands()) {
1014 if (!isRegInClass(MO, QPRs) || !MO.isDef())
1016 if (!HasPredicatedUsers(MI, MO, Predicated)) {
1017 LLVM_DEBUG(dbgs() << " Found an unknown def of : "
1018 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
1019 NonPredicated.insert(MI);
1023 // Any unknown false lanes have been masked away by the user(s).
1024 if (!NonPredicated.contains(MI))
1025 Predicated.insert(MI);
1028 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
1029 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
1030 ML.getExitBlocks(ExitBlocks);
1031 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
1032 assert(ExitBlocks.size() == 1 && "Expected a single exit block");
1033 MachineBasicBlock *ExitBB = ExitBlocks.front();
1034 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
1035 // TODO: Instead of blocking predication, we could move the vctp to the exit
1036 // block and calculate it's operand there in or the preheader.
1037 if (RegMask.PhysReg == ARM::VPR) {
1038 LLVM_DEBUG(dbgs() << " VPR is live in to the exit block.");
1041 // Check Q-regs that are live in the exit blocks. We don't collect scalars
1042 // because they won't be affected by lane predication.
1043 if (QPRs->contains(RegMask.PhysReg))
1044 if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
1045 LiveOutMIs.insert(MI);
1048 // We've already validated that any VPT predication within the loop will be
1049 // equivalent when we perform the predication transformation; so we know that
1050 // any VPT predicated instruction is predicated upon VCTP. Any live-out
1051 // instruction needs to be predicated, so check this here. The instructions
1052 // in NonPredicated have been found to be a reduction that we can ensure its
1053 // legality. Any MQPRCopy found will need to validate its input as if it was
1055 SmallVector<MachineInstr *> Worklist(LiveOutMIs.begin(), LiveOutMIs.end());
1056 while (!Worklist.empty()) {
1057 MachineInstr *MI = Worklist.pop_back_val();
1058 if (MI->getOpcode() == ARM::MQPRCopy) {
1059 VMOVCopies.insert(MI);
1060 MachineInstr *CopySrc =
1061 RDA.getUniqueReachingMIDef(MI, MI->getOperand(1).getReg());
1063 Worklist.push_back(CopySrc);
1064 } else if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {
1065 LLVM_DEBUG(dbgs() << " Unable to handle live out: " << *MI);
1074 void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {
1078 // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]
1079 // can only jump back.
1080 auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,
1081 ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {
1082 MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd
1083 ? End->getOperand(1).getMBB()
1084 : End->getOperand(2).getMBB();
1085 // TODO Maybe there's cases where the target doesn't have to be the header,
1086 // but for now be safe and revert.
1087 if (TgtBB != ML.getHeader()) {
1088 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");
1092 // The WLS and LE instructions have 12-bits for the label offset. WLS
1093 // requires a positive offset, while LE uses negative.
1094 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
1095 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
1096 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
1100 if (isWhileLoopStart(*Start)) {
1101 MachineBasicBlock *TargetBB = getWhileLoopStartTargetBB(*Start);
1102 if (BBUtils->getOffsetOf(Start) > BBUtils->getOffsetOf(TargetBB) ||
1103 !BBUtils->isBBInRange(Start, TargetBB, 4094)) {
1104 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
1111 StartInsertPt = MachineBasicBlock::iterator(Start);
1112 StartInsertBB = Start->getParent();
1113 LLVM_DEBUG(dbgs() << "ARM Loops: Will insert LoopStart at "
1116 Revert = !ValidateRanges(Start, End, BBUtils, ML);
1117 CannotTailPredicate = !ValidateTailPredicate();
1120 bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {
1121 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);
1122 if (VCTPs.empty()) {
1123 VCTPs.push_back(MI);
1127 // If we find another VCTP, check whether it uses the same value as the main VCTP.
1128 // If it does, store it in the VCTPs set, else refuse it.
1129 MachineInstr *Prev = VCTPs.back();
1130 if (!Prev->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
1131 !RDA.hasSameReachingDef(Prev, MI, MI->getOperand(1).getReg().asMCReg())) {
1132 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
1133 "definition from the main VCTP");
1136 VCTPs.push_back(MI);
1140 static bool ValidateMVEStore(MachineInstr *MI, MachineLoop *ML) {
1142 auto GetFrameIndex = [](MachineMemOperand *Operand) {
1143 const PseudoSourceValue *PseudoValue = Operand->getPseudoValue();
1144 if (PseudoValue && PseudoValue->kind() == PseudoSourceValue::FixedStack) {
1145 if (const auto *FS = dyn_cast<FixedStackPseudoSourceValue>(PseudoValue)) {
1146 return FS->getFrameIndex();
1152 auto IsStackOp = [GetFrameIndex](MachineInstr *I) {
1153 switch (I->getOpcode()) {
1154 case ARM::MVE_VSTRWU32:
1155 case ARM::MVE_VLDRWU32: {
1156 return I->getOperand(1).getReg() == ARM::SP &&
1157 I->memoperands().size() == 1 &&
1158 GetFrameIndex(I->memoperands().front()) >= 0;
1165 // An unpredicated vector register spill is allowed if all of the uses of the
1166 // stack slot are within the loop
1167 if (MI->getOpcode() != ARM::MVE_VSTRWU32 || !IsStackOp(MI))
1170 // Search all blocks after the loop for accesses to the same stack slot.
1171 // ReachingDefAnalysis doesn't work for sp as it relies on registers being
1172 // live-out (which sp never is) to know what blocks to look in
1173 if (MI->memoperands().size() == 0)
1175 int FI = GetFrameIndex(MI->memoperands().front());
1177 auto &FrameInfo = MI->getParent()->getParent()->getFrameInfo();
1178 if (FI == -1 || !FrameInfo.isSpillSlotObjectIndex(FI))
1181 SmallVector<MachineBasicBlock *> Frontier;
1182 ML->getExitBlocks(Frontier);
1183 SmallPtrSet<MachineBasicBlock *, 4> Visited{MI->getParent()};
1185 while (Idx < Frontier.size()) {
1186 MachineBasicBlock *BB = Frontier[Idx];
1187 bool LookAtSuccessors = true;
1188 for (auto &I : *BB) {
1189 if (!IsStackOp(&I) || I.memoperands().size() == 0)
1191 if (GetFrameIndex(I.memoperands().front()) != FI)
1193 // If this block has a store to the stack slot before any loads then we
1194 // can ignore the block
1195 if (I.getOpcode() == ARM::MVE_VSTRWU32) {
1196 LookAtSuccessors = false;
1199 // If the store and the load are using the same stack slot then the
1200 // store isn't valid for tail predication
1201 if (I.getOpcode() == ARM::MVE_VLDRWU32)
1205 if (LookAtSuccessors) {
1206 for (auto *Succ : BB->successors()) {
1207 if (!Visited.contains(Succ) && !is_contained(Frontier, Succ))
1208 Frontier.push_back(Succ);
1218 bool LowOverheadLoop::ValidateMVEInst(MachineInstr *MI) {
1219 if (CannotTailPredicate)
1222 if (!shouldInspect(*MI))
1225 if (MI->getOpcode() == ARM::MVE_VPSEL ||
1226 MI->getOpcode() == ARM::MVE_VPNOT) {
1227 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
1228 // 1) It will use the VPR as a predicate operand, but doesn't have to be
1229 // instead a VPT block, which means we can assert while building up
1230 // the VPT block because we don't find another VPT or VPST to being a new
1232 // 2) VPSEL still requires a VPR operand even after tail predicating,
1233 // which means we can't remove it unless there is another
1234 // instruction, such as vcmp, that can provide the VPR def.
1238 // Record all VCTPs and check that they're equivalent to one another.
1239 if (isVCTP(MI) && !AddVCTP(MI))
1242 // Inspect uses first so that any instructions that alter the VPR don't
1243 // alter the predicate upon themselves.
1244 const MCInstrDesc &MCID = MI->getDesc();
1246 unsigned LastOpIdx = MI->getNumOperands() - 1;
1247 for (const auto &Op : enumerate(reverse(MCID.operands()))) {
1248 const MachineOperand &MO = MI->getOperand(LastOpIdx - Op.index());
1249 if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)
1252 if (ARM::isVpred(Op.value().OperandType)) {
1253 VPTState::addInst(MI);
1255 } else if (MI->getOpcode() != ARM::MVE_VPST) {
1256 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
1261 // If we find an instruction that has been marked as not valid for tail
1262 // predication, only allow the instruction if it's contained within a valid
1264 bool RequiresExplicitPredication =
1265 (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;
1266 if (isDomainMVE(MI) && RequiresExplicitPredication) {
1267 if (MI->getOpcode() == ARM::MQPRCopy)
1269 if (!IsUse && producesDoubleWidthResult(*MI)) {
1270 DoubleWidthResultInstrs.insert(MI);
1274 LLVM_DEBUG(if (!IsUse) dbgs()
1275 << "ARM Loops: Can't tail predicate: " << *MI);
1279 // If the instruction is already explicitly predicated, then the conversion
1280 // will be fine, but ensure that all store operations are predicated.
1281 if (MI->mayStore() && !ValidateMVEStore(MI, &ML))
1284 // If this instruction defines the VPR, update the predicate for the
1285 // proceeding instructions.
1286 if (isVectorPredicate(MI)) {
1287 // Clear the existing predicate when we're not in VPT Active state,
1288 // otherwise we add to it.
1289 if (!isVectorPredicated(MI))
1290 VPTState::resetPredicate(MI);
1292 VPTState::addPredicate(MI);
1295 // Finally once the predicate has been modified, we can start a new VPT
1296 // block if necessary.
1297 if (isVPTOpcode(MI->getOpcode()))
1298 VPTState::CreateVPTBlock(MI);
1303 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
1304 const ARMSubtarget &ST = mf.getSubtarget<ARMSubtarget>();
1309 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
1311 MLI = &getAnalysis<MachineLoopInfo>();
1312 RDA = &getAnalysis<ReachingDefAnalysis>();
1313 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
1314 MRI = &MF->getRegInfo();
1315 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
1316 TRI = ST.getRegisterInfo();
1317 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
1318 BBUtils->computeAllBlockSizes();
1319 BBUtils->adjustBBOffsetsAfter(&MF->front());
1321 bool Changed = false;
1322 for (auto *ML : *MLI) {
1323 if (ML->isOutermost())
1324 Changed |= ProcessLoop(ML);
1326 Changed |= RevertNonLoops();
1330 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
1332 bool Changed = false;
1334 // Process inner loops first.
1335 for (MachineLoop *L : *ML)
1336 Changed |= ProcessLoop(L);
1339 dbgs() << "ARM Loops: Processing loop containing:\n";
1340 if (auto *Preheader = ML->getLoopPreheader())
1341 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1342 else if (auto *Preheader = MLI->findLoopPreheader(ML, true, true))
1343 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1344 for (auto *MBB : ML->getBlocks())
1345 dbgs() << " - Block: " << printMBBReference(*MBB) << "\n";
1348 // Search the given block for a loop start instruction. If one isn't found,
1349 // and there's only one predecessor block, search that one too.
1350 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
1351 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
1352 for (auto &MI : *MBB) {
1353 if (isLoopStart(MI))
1356 if (MBB->pred_size() == 1)
1357 return SearchForStart(*MBB->pred_begin());
1361 LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
1362 // Search the preheader for the start intrinsic.
1363 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
1364 // with potentially multiple set.loop.iterations, so we need to enable this.
1365 if (LoLoop.Preheader)
1366 LoLoop.Start = SearchForStart(LoLoop.Preheader);
1370 // Find the low-overhead loop components and decide whether or not to fall
1371 // back to a normal loop. Also look for a vctp instructions and decide
1372 // whether we can convert that predicate using tail predication.
1373 for (auto *MBB : reverse(ML->getBlocks())) {
1374 for (auto &MI : *MBB) {
1375 if (MI.isDebugValue())
1377 else if (MI.getOpcode() == ARM::t2LoopDec)
1379 else if (MI.getOpcode() == ARM::t2LoopEnd)
1381 else if (MI.getOpcode() == ARM::t2LoopEndDec)
1382 LoLoop.End = LoLoop.Dec = &MI;
1383 else if (isLoopStart(MI))
1385 else if (MI.getDesc().isCall()) {
1386 // TODO: Though the call will require LE to execute again, does this
1387 // mean we should revert? Always executing LE hopefully should be
1388 // faster than performing a sub,cmp,br or even subs,br.
1389 LoLoop.Revert = true;
1390 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
1392 // Record VPR defs and build up their corresponding vpt blocks.
1393 // Check we know how to tail predicate any mve instructions.
1394 LoLoop.AnalyseMVEInst(&MI);
1399 LLVM_DEBUG(LoLoop.dump());
1400 if (!LoLoop.FoundAllComponents()) {
1401 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
1405 assert(LoLoop.Start->getOpcode() != ARM::t2WhileLoopStart &&
1406 "Expected t2WhileLoopStart to be removed before regalloc!");
1408 // Check that the only instruction using LoopDec is LoopEnd. This can only
1409 // happen when the Dec and End are separate, not a single t2LoopEndDec.
1410 // TODO: Check for copy chains that really have no effect.
1411 if (LoLoop.Dec != LoLoop.End) {
1412 SmallPtrSet<MachineInstr *, 2> Uses;
1413 RDA->getReachingLocalUses(LoLoop.Dec, MCRegister::from(ARM::LR), Uses);
1414 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
1415 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
1416 LoLoop.Revert = true;
1419 LoLoop.Validate(BBUtils.get());
1424 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1425 // beq that branches to the exit branch.
1426 // TODO: We could also try to generate a cbz if the value in LR is also in
1427 // another low register.
1428 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
1429 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
1430 MachineBasicBlock *DestBB = getWhileLoopStartTargetBB(*MI);
1431 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1432 ARM::tBcc : ARM::t2Bcc;
1434 RevertWhileLoopStartLR(MI, TII, BrOpc);
1437 void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {
1438 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);
1439 RevertDoLoopStart(MI, TII);
1442 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
1443 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
1444 MachineBasicBlock *MBB = MI->getParent();
1445 SmallPtrSet<MachineInstr*, 1> Ignore;
1446 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
1447 if (I->getOpcode() == ARM::t2LoopEnd) {
1453 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
1455 RDA->isSafeToDefRegAt(MI, MCRegister::from(ARM::CPSR), Ignore);
1457 llvm::RevertLoopDec(MI, TII, SetFlags);
1461 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1462 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
1463 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
1465 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1466 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1467 ARM::tBcc : ARM::t2Bcc;
1469 llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);
1472 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1473 void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {
1474 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);
1475 assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");
1476 MachineBasicBlock *MBB = MI->getParent();
1478 MachineInstrBuilder MIB =
1479 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri));
1480 MIB.addDef(ARM::LR);
1481 MIB.add(MI->getOperand(1));
1483 MIB.addImm(ARMCC::AL);
1484 MIB.addReg(ARM::NoRegister);
1485 MIB.addReg(ARM::CPSR);
1486 MIB->getOperand(5).setIsDef(true);
1488 MachineBasicBlock *DestBB = MI->getOperand(2).getMBB();
1490 BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc;
1493 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
1494 MIB.add(MI->getOperand(2)); // branch target
1495 MIB.addImm(ARMCC::NE); // condition code
1496 MIB.addReg(ARM::CPSR);
1498 MI->eraseFromParent();
1501 // Perform dead code elimation on the loop iteration count setup expression.
1502 // If we are tail-predicating, the number of elements to be processed is the
1503 // operand of the VCTP instruction in the vector body, see getCount(), which is
1504 // register $r3 in this example:
1506 // $lr = big-itercount-expression
1508 // $lr = t2DoLoopStart renamable $lr
1511 // $vpr = MVE_VCTP32 renamable $r3
1512 // renamable $lr = t2LoopDec killed renamable $lr, 1
1513 // t2LoopEnd renamable $lr, %vector.body
1516 // What we would like achieve here is to replace the do-loop start pseudo
1517 // instruction t2DoLoopStart with:
1519 // $lr = MVE_DLSTP_32 killed renamable $r3
1521 // Thus, $r3 which defines the number of elements, is written to $lr,
1522 // and then we want to delete the whole chain that used to define $lr,
1523 // see the comment below how this chain could look like.
1525 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
1526 if (!LoLoop.IsTailPredicationLegal())
1529 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
1531 MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 1);
1533 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
1537 // Collect and remove the users of iteration count.
1538 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,
1540 if (!TryRemove(Def, *RDA, LoLoop.ToRemove, Killed))
1541 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
1544 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
1545 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
1546 // When using tail-predication, try to delete the dead code that was used to
1547 // calculate the number of loop iterations.
1548 IterationCountDCE(LoLoop);
1550 MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;
1551 MachineInstr *Start = LoLoop.Start;
1552 MachineBasicBlock *MBB = LoLoop.StartInsertBB;
1553 unsigned Opc = LoLoop.getStartOpcode();
1554 MachineOperand &Count = LoLoop.getLoopStartOperand();
1556 // A DLS lr, lr we needn't emit
1557 MachineInstr* NewStart;
1558 if (!DisableOmitDLS && Opc == ARM::t2DLS && Count.isReg() &&
1559 Count.getReg() == ARM::LR) {
1560 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't insert start: DLS lr, lr");
1563 MachineInstrBuilder MIB =
1564 BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));
1566 MIB.addDef(ARM::LR);
1568 if (isWhileLoopStart(*Start))
1569 MIB.addMBB(getWhileLoopStartTargetBB(*Start));
1571 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
1575 LoLoop.ToRemove.insert(Start);
1579 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
1580 auto RemovePredicate = [](MachineInstr *MI) {
1581 if (MI->isDebugInstr())
1583 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
1584 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
1585 assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");
1586 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
1587 "Expected Then predicate!");
1588 MI->getOperand(PIdx).setImm(ARMVCC::None);
1589 MI->getOperand(PIdx + 1).setReg(0);
1592 for (auto &Block : LoLoop.getVPTBlocks()) {
1593 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
1595 auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {
1596 assert(TheVCMP && "Replacing a removed or non-existent VCMP");
1597 // Replace the VCMP with a VPT
1598 MachineInstrBuilder MIB =
1599 BuildMI(*At->getParent(), At, At->getDebugLoc(),
1600 TII->get(VCMPOpcodeToVPT(TheVCMP->getOpcode())));
1601 MIB.addImm(ARMVCC::Then);
1603 MIB.add(TheVCMP->getOperand(1));
1605 MIB.add(TheVCMP->getOperand(2));
1606 // The comparison code, e.g. ge, eq, lt
1607 MIB.add(TheVCMP->getOperand(3));
1608 LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);
1609 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1610 LoLoop.ToRemove.insert(TheVCMP);
1614 if (VPTState::isEntryPredicatedOnVCTP(Block, /*exclusive*/ true)) {
1615 MachineInstr *VPST = Insts.front();
1616 if (VPTState::hasUniformPredicate(Block)) {
1617 // A vpt block starting with VPST, is only predicated upon vctp and has no
1618 // internal vpr defs:
1620 // - Unpredicate the remaining instructions.
1621 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1622 for (unsigned i = 1; i < Insts.size(); ++i)
1623 RemovePredicate(Insts[i]);
1625 // The VPT block has a non-uniform predicate but it uses a vpst and its
1626 // entry is guarded only by a vctp, which means we:
1627 // - Need to remove the original vpst.
1628 // - Then need to unpredicate any following instructions, until
1629 // we come across the divergent vpr def.
1630 // - Insert a new vpst to predicate the instruction(s) that following
1631 // the divergent vpr def.
1632 MachineInstr *Divergent = VPTState::getDivergent(Block);
1633 MachineBasicBlock *MBB = Divergent->getParent();
1634 auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);
1635 while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())
1638 bool DivergentNextIsPredicated =
1639 DivergentNext != MBB->end() &&
1640 getVPTInstrPredicate(*DivergentNext) != ARMVCC::None;
1642 for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;
1644 RemovePredicate(&*I);
1646 // Check if the instruction defining vpr is a vcmp so it can be combined
1647 // with the VPST This should be the divergent instruction
1648 MachineInstr *VCMP =
1649 VCMPOpcodeToVPT(Divergent->getOpcode()) != 0 ? Divergent : nullptr;
1651 if (DivergentNextIsPredicated) {
1652 // Insert a VPST at the divergent only if the next instruction
1653 // would actually use it. A VCMP following a VPST can be
1654 // merged into a VPT so do that instead if the VCMP exists.
1656 // Create a VPST (with a null mask for now, we'll recompute it
1658 MachineInstrBuilder MIB =
1659 BuildMI(*Divergent->getParent(), Divergent,
1660 Divergent->getDebugLoc(), TII->get(ARM::MVE_VPST));
1662 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
1663 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1665 // No RDA checks are necessary here since the VPST would have been
1666 // directly after the VCMP
1667 ReplaceVCMPWithVPT(VCMP, VCMP);
1671 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1672 LoLoop.ToRemove.insert(VPST);
1673 } else if (Block.containsVCTP()) {
1674 // The vctp will be removed, so either the entire block will be dead or
1675 // the block mask of the vp(s)t will need to be recomputed.
1676 MachineInstr *VPST = Insts.front();
1677 if (Block.size() == 2) {
1678 assert(VPST->getOpcode() == ARM::MVE_VPST &&
1679 "Found a VPST in an otherwise empty vpt block");
1680 LoLoop.ToRemove.insert(VPST);
1682 LoLoop.BlockMasksToRecompute.insert(VPST);
1683 } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {
1684 // If this block starts with a VPST then attempt to merge it with the
1685 // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT
1686 // block that no longer exists
1687 MachineInstr *VPST = Insts.front();
1688 auto Next = ++MachineBasicBlock::iterator(VPST);
1689 assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&
1690 "The instruction after a VPST must be predicated");
1692 MachineInstr *VprDef = RDA->getUniqueReachingMIDef(VPST, ARM::VPR);
1693 if (VprDef && VCMPOpcodeToVPT(VprDef->getOpcode()) &&
1694 !LoLoop.ToRemove.contains(VprDef)) {
1695 MachineInstr *VCMP = VprDef;
1696 // The VCMP and VPST can only be merged if the VCMP's operands will have
1697 // the same values at the VPST.
1698 // If any of the instructions between the VCMP and VPST are predicated
1699 // then a different code path is expected to have merged the VCMP and
1701 if (std::none_of(++MachineBasicBlock::iterator(VCMP),
1702 MachineBasicBlock::iterator(VPST), hasVPRUse) &&
1703 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(1).getReg()) &&
1704 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(2).getReg())) {
1705 ReplaceVCMPWithVPT(VCMP, VPST);
1706 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1707 LoLoop.ToRemove.insert(VPST);
1713 LoLoop.ToRemove.insert(LoLoop.VCTPs.begin(), LoLoop.VCTPs.end());
1716 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
1718 // Combine the LoopDec and LoopEnd instructions into LE(TP).
1719 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
1720 MachineInstr *End = LoLoop.End;
1721 MachineBasicBlock *MBB = End->getParent();
1722 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
1723 ARM::MVE_LETP : ARM::t2LEUpdate;
1724 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
1726 MIB.addDef(ARM::LR);
1727 unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;
1728 MIB.add(End->getOperand(Off + 0));
1729 MIB.add(End->getOperand(Off + 1));
1730 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
1731 LoLoop.ToRemove.insert(LoLoop.Dec);
1732 LoLoop.ToRemove.insert(End);
1736 // TODO: We should be able to automatically remove these branches before we
1737 // get here - probably by teaching analyzeBranch about the pseudo
1739 // If there is an unconditional branch, after I, that just branches to the
1740 // next block, remove it.
1741 auto RemoveDeadBranch = [](MachineInstr *I) {
1742 MachineBasicBlock *BB = I->getParent();
1743 MachineInstr *Terminator = &BB->instr_back();
1744 if (Terminator->isUnconditionalBranch() && I != Terminator) {
1745 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
1746 if (BB->isLayoutSuccessor(Succ)) {
1747 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
1748 Terminator->eraseFromParent();
1753 // And VMOVCopies need to become 2xVMOVD for tail predication to be valid.
1754 // Anything other MQPRCopy can be converted to MVE_VORR later on.
1755 auto ExpandVMOVCopies = [this](SmallPtrSet<MachineInstr *, 4> &VMOVCopies) {
1756 for (auto *MI : VMOVCopies) {
1757 LLVM_DEBUG(dbgs() << "Converting copy to VMOVD: " << *MI);
1758 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1759 MachineBasicBlock *MBB = MI->getParent();
1760 Register Dst = MI->getOperand(0).getReg();
1761 Register Src = MI->getOperand(1).getReg();
1762 auto MIB1 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),
1763 ARM::D0 + (Dst - ARM::Q0) * 2)
1764 .addReg(ARM::D0 + (Src - ARM::Q0) * 2)
1765 .add(predOps(ARMCC::AL));
1767 LLVM_DEBUG(dbgs() << " into " << *MIB1);
1768 auto MIB2 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),
1769 ARM::D0 + (Dst - ARM::Q0) * 2 + 1)
1770 .addReg(ARM::D0 + (Src - ARM::Q0) * 2 + 1)
1771 .add(predOps(ARMCC::AL));
1772 LLVM_DEBUG(dbgs() << " and " << *MIB2);
1774 MI->eraseFromParent();
1778 if (LoLoop.Revert) {
1779 if (isWhileLoopStart(*LoLoop.Start))
1780 RevertWhile(LoLoop.Start);
1782 RevertDo(LoLoop.Start);
1783 if (LoLoop.Dec == LoLoop.End)
1784 RevertLoopEndDec(LoLoop.End);
1786 RevertLoopEnd(LoLoop.End, RevertLoopDec(LoLoop.Dec));
1788 ExpandVMOVCopies(LoLoop.VMOVCopies);
1789 LoLoop.Start = ExpandLoopStart(LoLoop);
1791 RemoveDeadBranch(LoLoop.Start);
1792 LoLoop.End = ExpandLoopEnd(LoLoop);
1793 RemoveDeadBranch(LoLoop.End);
1794 if (LoLoop.IsTailPredicationLegal())
1795 ConvertVPTBlocks(LoLoop);
1796 for (auto *I : LoLoop.ToRemove) {
1797 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
1798 I->eraseFromParent();
1800 for (auto *I : LoLoop.BlockMasksToRecompute) {
1801 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
1802 recomputeVPTBlockMask(*I);
1803 LLVM_DEBUG(dbgs() << " ... done: " << *I);
1807 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
1809 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
1810 for (auto *MBB : PostOrder) {
1811 recomputeLiveIns(*MBB);
1812 // FIXME: For some reason, the live-in print order is non-deterministic for
1813 // our tests and I can't out why... So just sort them.
1814 MBB->sortUniqueLiveIns();
1817 for (auto *MBB : reverse(PostOrder))
1818 recomputeLivenessFlags(*MBB);
1820 // We've moved, removed and inserted new instructions, so update RDA.
1824 bool ARMLowOverheadLoops::RevertNonLoops() {
1825 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1826 bool Changed = false;
1828 for (auto &MBB : *MF) {
1829 SmallVector<MachineInstr*, 4> Starts;
1830 SmallVector<MachineInstr*, 4> Decs;
1831 SmallVector<MachineInstr*, 4> Ends;
1832 SmallVector<MachineInstr *, 4> EndDecs;
1833 SmallVector<MachineInstr *, 4> MQPRCopies;
1835 for (auto &I : MBB) {
1837 Starts.push_back(&I);
1838 else if (I.getOpcode() == ARM::t2LoopDec)
1840 else if (I.getOpcode() == ARM::t2LoopEnd)
1842 else if (I.getOpcode() == ARM::t2LoopEndDec)
1843 EndDecs.push_back(&I);
1844 else if (I.getOpcode() == ARM::MQPRCopy)
1845 MQPRCopies.push_back(&I);
1848 if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty() &&
1854 for (auto *Start : Starts) {
1855 if (isWhileLoopStart(*Start))
1860 for (auto *Dec : Decs)
1863 for (auto *End : Ends)
1865 for (auto *End : EndDecs)
1866 RevertLoopEndDec(End);
1867 for (auto *MI : MQPRCopies) {
1868 LLVM_DEBUG(dbgs() << "Converting copy to VORR: " << *MI);
1869 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1870 MachineBasicBlock *MBB = MI->getParent();
1871 auto MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::MVE_VORR),
1872 MI->getOperand(0).getReg())
1873 .add(MI->getOperand(1))
1874 .add(MI->getOperand(1));
1875 addUnpredicatedMveVpredROp(MIB, MI->getOperand(0).getReg());
1876 MI->eraseFromParent();
1882 FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1883 return new ARMLowOverheadLoops();