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/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 int getVecSize(const MachineInstr &MI) {
101 const MCInstrDesc &MCID = MI.getDesc();
102 uint64_t Flags = MCID.TSFlags;
103 return (Flags & ARMII::VecSize) >> ARMII::VecSizeShift;
106 static bool shouldInspect(MachineInstr &MI) {
107 if (MI.isDebugInstr())
109 return isDomainMVE(&MI) || isVectorPredicate(&MI) || hasVPRUse(MI);
114 using InstSet = SmallPtrSetImpl<MachineInstr *>;
116 class PostOrderLoopTraversal {
118 MachineLoopInfo &MLI;
119 SmallPtrSet<MachineBasicBlock*, 4> Visited;
120 SmallVector<MachineBasicBlock*, 4> Order;
123 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
124 : ML(ML), MLI(MLI) { }
126 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
130 // Visit all the blocks within the loop, as well as exit blocks and any
131 // blocks properly dominating the header.
133 std::function<void(MachineBasicBlock*)> Search = [this, &Search]
134 (MachineBasicBlock *MBB) -> void {
135 if (Visited.count(MBB))
139 for (auto *Succ : MBB->successors()) {
140 if (!ML.contains(Succ))
144 Order.push_back(MBB);
147 // Insert exit blocks.
148 SmallVector<MachineBasicBlock*, 2> ExitBlocks;
149 ML.getExitBlocks(ExitBlocks);
150 append_range(Order, ExitBlocks);
152 // Then add the loop body.
153 Search(ML.getHeader());
155 // Then try the preheader and its predecessors.
156 std::function<void(MachineBasicBlock*)> GetPredecessor =
157 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
158 Order.push_back(MBB);
159 if (MBB->pred_size() == 1)
160 GetPredecessor(*MBB->pred_begin());
163 if (auto *Preheader = ML.getLoopPreheader())
164 GetPredecessor(Preheader);
165 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true, true))
166 GetPredecessor(Preheader);
170 struct PredicatedMI {
171 MachineInstr *MI = nullptr;
172 SetVector<MachineInstr*> Predicates;
175 PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
176 assert(I && "Instruction must not be null!");
177 Predicates.insert(Preds.begin(), Preds.end());
181 // Represent the current state of the VPR and hold all instances which
182 // represent a VPT block, which is a list of instructions that begins with a
183 // VPT/VPST and has a maximum of four proceeding instructions. All
184 // instructions within the block are predicated upon the vpr and we allow
185 // instructions to define the vpr within in the block too.
187 friend struct LowOverheadLoop;
189 SmallVector<MachineInstr *, 4> Insts;
191 static SmallVector<VPTState, 4> Blocks;
192 static SetVector<MachineInstr *> CurrentPredicates;
193 static std::map<MachineInstr *,
194 std::unique_ptr<PredicatedMI>> PredicatedInsts;
196 static void CreateVPTBlock(MachineInstr *MI) {
197 assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))
198 && "Can't begin VPT without predicate");
199 Blocks.emplace_back(MI);
200 // The execution of MI is predicated upon the current set of instructions
201 // that are AND'ed together to form the VPR predicate value. In the case
202 // that MI is a VPT, CurrentPredicates will also just be MI.
203 PredicatedInsts.emplace(
204 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
207 static void reset() {
209 PredicatedInsts.clear();
210 CurrentPredicates.clear();
213 static void addInst(MachineInstr *MI) {
214 Blocks.back().insert(MI);
215 PredicatedInsts.emplace(
216 MI, std::make_unique<PredicatedMI>(MI, CurrentPredicates));
219 static void addPredicate(MachineInstr *MI) {
220 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);
221 CurrentPredicates.insert(MI);
224 static void resetPredicate(MachineInstr *MI) {
225 LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);
226 CurrentPredicates.clear();
227 CurrentPredicates.insert(MI);
231 // Have we found an instruction within the block which defines the vpr? If
232 // so, not all the instructions in the block will have the same predicate.
233 static bool hasUniformPredicate(VPTState &Block) {
234 return getDivergent(Block) == nullptr;
237 // If it exists, return the first internal instruction which modifies the
239 static MachineInstr *getDivergent(VPTState &Block) {
240 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
241 for (unsigned i = 1; i < Insts.size(); ++i) {
242 MachineInstr *Next = Insts[i];
243 if (isVectorPredicate(Next))
244 return Next; // Found an instruction altering the vpr.
249 // Return whether the given instruction is predicated upon a VCTP.
250 static bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {
251 SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI]->Predicates;
252 if (Exclusive && Predicates.size() != 1)
254 return llvm::any_of(Predicates, isVCTP);
257 // Is the VPST, controlling the block entry, predicated upon a VCTP.
258 static bool isEntryPredicatedOnVCTP(VPTState &Block,
259 bool Exclusive = false) {
260 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
261 return isPredicatedOnVCTP(Insts.front(), Exclusive);
264 // If this block begins with a VPT, we can check whether it's using
265 // at least one predicated input(s), as well as possible loop invariant
266 // which would result in it being implicitly predicated.
267 static bool hasImplicitlyValidVPT(VPTState &Block,
268 ReachingDefAnalysis &RDA) {
269 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
270 MachineInstr *VPT = Insts.front();
271 assert(isVPTOpcode(VPT->getOpcode()) &&
272 "Expected VPT block to begin with VPT/VPST");
274 if (VPT->getOpcode() == ARM::MVE_VPST)
277 auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
278 MachineInstr *Op = RDA.getMIOperand(MI, MI->getOperand(Idx));
279 return Op && PredicatedInsts.count(Op) && isPredicatedOnVCTP(Op);
282 auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
283 MachineOperand &MO = MI->getOperand(Idx);
284 if (!MO.isReg() || !MO.getReg())
287 SmallPtrSet<MachineInstr *, 2> Defs;
288 RDA.getGlobalReachingDefs(MI, MO.getReg(), Defs);
292 for (auto *Def : Defs)
293 if (Def->getParent() == VPT->getParent())
298 // Check that at least one of the operands is directly predicated on a
299 // vctp and allow an invariant value too.
300 return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
301 (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
302 (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
305 static bool isValid(ReachingDefAnalysis &RDA) {
306 // All predication within the loop should be based on vctp. If the block
307 // isn't predicated on entry, check whether the vctp is within the block
308 // and that all other instructions are then predicated on it.
309 for (auto &Block : Blocks) {
310 if (isEntryPredicatedOnVCTP(Block, false) ||
311 hasImplicitlyValidVPT(Block, RDA))
314 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
315 // We don't know how to convert a block with just a VPT;VCTP into
316 // anything valid once we remove the VCTP. For now just bail out.
317 assert(isVPTOpcode(Insts.front()->getOpcode()) &&
318 "Expected VPT block to start with a VPST or VPT!");
319 if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&
320 isVCTP(Insts.back()))
323 for (auto *MI : Insts) {
324 // Check that any internal VCTPs are 'Then' predicated.
325 if (isVCTP(MI) && getVPTInstrPredicate(*MI) != ARMVCC::Then)
327 // Skip other instructions that build up the predicate.
328 if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))
330 // Check that any other instructions are predicated upon a vctp.
331 // TODO: We could infer when VPTs are implicitly predicated on the
332 // vctp (when the operands are predicated).
333 if (!isPredicatedOnVCTP(MI)) {
334 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);
342 VPTState(MachineInstr *MI) { Insts.push_back(MI); }
344 void insert(MachineInstr *MI) {
346 // VPT/VPST + 4 predicated instructions.
347 assert(Insts.size() <= 5 && "Too many instructions in VPT block!");
350 bool containsVCTP() const {
351 return llvm::any_of(Insts, isVCTP);
354 unsigned size() const { return Insts.size(); }
355 SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }
358 struct LowOverheadLoop {
361 MachineBasicBlock *Preheader = nullptr;
362 MachineLoopInfo &MLI;
363 ReachingDefAnalysis &RDA;
364 const TargetRegisterInfo &TRI;
365 const ARMBaseInstrInfo &TII;
366 MachineFunction *MF = nullptr;
367 MachineBasicBlock::iterator StartInsertPt;
368 MachineBasicBlock *StartInsertBB = nullptr;
369 MachineInstr *Start = nullptr;
370 MachineInstr *Dec = nullptr;
371 MachineInstr *End = nullptr;
372 MachineOperand TPNumElements;
373 SmallVector<MachineInstr *, 4> VCTPs;
374 SmallPtrSet<MachineInstr *, 4> ToRemove;
375 SmallPtrSet<MachineInstr *, 4> BlockMasksToRecompute;
376 SmallPtrSet<MachineInstr *, 4> DoubleWidthResultInstrs;
377 SmallPtrSet<MachineInstr *, 4> VMOVCopies;
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, 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 Start->getOperand(1);
448 unsigned getStartOpcode() const {
449 bool IsDo = isDoLoopStart(*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 // For tail predication, we need to provide the number of elements, instead
634 // of the iteration count, to the loop start instruction. The number of
635 // elements is provided to the vctp instruction, so we need to check that
636 // we can use this register at InsertPt.
637 MachineInstr *VCTP = VCTPs.back();
638 if (Start->getOpcode() == ARM::t2DoLoopStartTP ||
639 Start->getOpcode() == ARM::t2WhileLoopStartTP) {
640 TPNumElements = Start->getOperand(2);
641 StartInsertPt = Start;
642 StartInsertBB = Start->getParent();
644 TPNumElements = VCTP->getOperand(1);
645 MCRegister NumElements = TPNumElements.getReg().asMCReg();
647 // If the register is defined within loop, then we can't perform TP.
648 // TODO: Check whether this is just a mov of a register that would be
650 if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
651 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
655 // The element count register maybe defined after InsertPt, in which case we
656 // need to try to move either InsertPt or the def so that the [w|d]lstp can
659 if (StartInsertPt != StartInsertBB->end() &&
660 !RDA.isReachingDefLiveOut(&*StartInsertPt, NumElements)) {
662 RDA.getLocalLiveOutMIDef(StartInsertBB, NumElements)) {
663 if (RDA.isSafeToMoveForwards(ElemDef, &*StartInsertPt)) {
664 ElemDef->removeFromParent();
665 StartInsertBB->insert(StartInsertPt, ElemDef);
667 << "ARM Loops: Moved element count def: " << *ElemDef);
668 } else if (RDA.isSafeToMoveBackwards(&*StartInsertPt, ElemDef)) {
669 StartInsertPt->removeFromParent();
670 StartInsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
672 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
674 // If we fail to move an instruction and the element count is provided
675 // by a mov, use the mov operand if it will have the same value at the
677 MachineOperand Operand = ElemDef->getOperand(1);
678 if (isMovRegOpcode(ElemDef->getOpcode()) &&
679 RDA.getUniqueReachingMIDef(ElemDef, Operand.getReg().asMCReg()) ==
680 RDA.getUniqueReachingMIDef(&*StartInsertPt,
681 Operand.getReg().asMCReg())) {
682 TPNumElements = Operand;
683 NumElements = TPNumElements.getReg();
686 << "ARM Loops: Unable to move element count to loop "
687 << "start instruction.\n");
694 // Especially in the case of while loops, InsertBB may not be the
695 // preheader, so we need to check that the register isn't redefined
696 // before entering the loop.
697 auto CannotProvideElements = [this](MachineBasicBlock *MBB,
698 MCRegister NumElements) {
701 // NumElements is redefined in this block.
702 if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
705 // Don't continue searching up through multiple predecessors.
706 if (MBB->pred_size() > 1)
712 // Search backwards for a def, until we get to InsertBB.
713 MachineBasicBlock *MBB = Preheader;
714 while (MBB && MBB != StartInsertBB) {
715 if (CannotProvideElements(MBB, NumElements)) {
716 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
719 MBB = *MBB->pred_begin();
723 // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect
724 // world the [w|d]lstp instruction would be last instruction in the preheader
725 // and so it would only affect instructions within the loop body. But due to
726 // scheduling, and/or the logic in this pass (above), the insertion point can
727 // be moved earlier. So if the Loop Start isn't the last instruction in the
728 // preheader, and if the initial element count is smaller than the vector
729 // width, the Loop Start instruction will immediately generate one or more
730 // false lane mask which can, incorrectly, affect the proceeding MVE
731 // instructions in the preheader.
732 if (std::any_of(StartInsertPt, StartInsertBB->end(), shouldInspect)) {
733 LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");
737 // For any DoubleWidthResultInstrs we found whilst scanning instructions, they
738 // need to compute an output size that is smaller than the VCTP mask operates
739 // on. The VecSize of the DoubleWidthResult is the larger vector size - the
740 // size it extends into, so any VCTP VecSize <= is valid.
741 unsigned VCTPVecSize = getVecSize(*VCTP);
742 for (MachineInstr *MI : DoubleWidthResultInstrs) {
743 unsigned InstrVecSize = getVecSize(*MI);
744 if (InstrVecSize > VCTPVecSize) {
745 LLVM_DEBUG(dbgs() << "ARM Loops: Double width result larger than VCTP "
746 << "VecSize:\n" << *MI);
751 // Check that the value change of the element count is what we expect and
752 // that the predication will be equivalent. For this we need:
753 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
754 // and we can also allow register copies within the chain too.
755 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
756 return -getAddSubImmediate(*MI) == ExpectedVecWidth;
759 MachineBasicBlock *MBB = VCTP->getParent();
760 // Remove modifications to the element count since they have no purpose in a
761 // tail predicated loop. Explicitly refer to the vctp operand no matter which
762 // register NumElements has been assigned to, since that is what the
763 // modifications will be using
764 if (auto *Def = RDA.getUniqueReachingMIDef(
765 &MBB->back(), VCTP->getOperand(1).getReg().asMCReg())) {
766 SmallPtrSet<MachineInstr*, 2> ElementChain;
767 SmallPtrSet<MachineInstr*, 2> Ignore;
768 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
770 Ignore.insert(VCTPs.begin(), VCTPs.end());
772 if (TryRemove(Def, RDA, ElementChain, Ignore)) {
773 bool FoundSub = false;
775 for (auto *MI : ElementChain) {
776 if (isMovRegOpcode(MI->getOpcode()))
779 if (isSubImmOpcode(MI->getOpcode())) {
780 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {
781 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
787 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
792 ToRemove.insert(ElementChain.begin(), ElementChain.end());
796 // If we converted the LoopStart to a t2DoLoopStartTP/t2WhileLoopStartTP, we
797 // can also remove any extra instructions in the preheader, which often
798 // includes a now unused MOV.
799 if ((Start->getOpcode() == ARM::t2DoLoopStartTP ||
800 Start->getOpcode() == ARM::t2WhileLoopStartTP) &&
801 Preheader && !Preheader->empty() &&
802 !RDA.hasLocalDefBefore(VCTP, VCTP->getOperand(1).getReg())) {
803 if (auto *Def = RDA.getUniqueReachingMIDef(
804 &Preheader->back(), VCTP->getOperand(1).getReg().asMCReg())) {
805 SmallPtrSet<MachineInstr*, 2> Ignore;
806 Ignore.insert(VCTPs.begin(), VCTPs.end());
807 TryRemove(Def, RDA, ToRemove, Ignore);
814 static bool isRegInClass(const MachineOperand &MO,
815 const TargetRegisterClass *Class) {
816 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
819 // MVE 'narrowing' operate on half a lane, reading from half and writing
820 // to half, which are referred to has the top and bottom half. The other
821 // half retains its previous value.
822 static bool retainsPreviousHalfElement(const MachineInstr &MI) {
823 const MCInstrDesc &MCID = MI.getDesc();
824 uint64_t Flags = MCID.TSFlags;
825 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
828 // Some MVE instructions read from the top/bottom halves of their operand(s)
829 // and generate a vector result with result elements that are double the
830 // width of the input.
831 static bool producesDoubleWidthResult(const MachineInstr &MI) {
832 const MCInstrDesc &MCID = MI.getDesc();
833 uint64_t Flags = MCID.TSFlags;
834 return (Flags & ARMII::DoubleWidthResult) != 0;
837 static bool isHorizontalReduction(const MachineInstr &MI) {
838 const MCInstrDesc &MCID = MI.getDesc();
839 uint64_t Flags = MCID.TSFlags;
840 return (Flags & ARMII::HorizontalReduction) != 0;
843 // Can this instruction generate a non-zero result when given only zeroed
844 // operands? This allows us to know that, given operands with false bytes
845 // zeroed by masked loads, that the result will also contain zeros in those
847 static bool canGenerateNonZeros(const MachineInstr &MI) {
849 // Check for instructions which can write into a larger element size,
850 // possibly writing into a previous zero'd lane.
851 if (producesDoubleWidthResult(MI))
854 switch (MI.getOpcode()) {
857 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
858 // fp16 -> fp32 vector conversions.
859 // Instructions that perform a NOT will generate 1s from 0s.
862 // Count leading zeros will do just that!
863 case ARM::MVE_VCLZs8:
864 case ARM::MVE_VCLZs16:
865 case ARM::MVE_VCLZs32:
871 // Look at its register uses to see if it only can only receive zeros
872 // into its false lanes which would then produce zeros. Also check that
873 // the output register is also defined by an FalseLanesZero instruction
874 // so that if tail-predication happens, the lanes that aren't updated will
876 static bool producesFalseLanesZero(MachineInstr &MI,
877 const TargetRegisterClass *QPRs,
878 const ReachingDefAnalysis &RDA,
879 InstSet &FalseLanesZero) {
880 if (canGenerateNonZeros(MI))
883 bool isPredicated = isVectorPredicated(&MI);
884 // Predicated loads will write zeros to the falsely predicated bytes of the
885 // destination register.
889 auto IsZeroInit = [](MachineInstr *Def) {
890 return !isVectorPredicated(Def) &&
891 Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
892 Def->getOperand(1).getImm() == 0;
895 bool AllowScalars = isHorizontalReduction(MI);
896 for (auto &MO : MI.operands()) {
897 if (!MO.isReg() || !MO.getReg())
899 if (!isRegInClass(MO, QPRs) && AllowScalars)
901 // Skip the lr predicate reg
902 int PIdx = llvm::findFirstVPTPredOperandIdx(MI);
903 if (PIdx != -1 && (int)MI.getOperandNo(&MO) == PIdx + 2)
906 // Check that this instruction will produce zeros in its false lanes:
907 // - If it only consumes false lanes zero or constant 0 (vmov #0)
908 // - If it's predicated, it only matters that it's def register already has
909 // false lane zeros, so we can ignore the uses.
910 SmallPtrSet<MachineInstr *, 2> Defs;
911 RDA.getGlobalReachingDefs(&MI, MO.getReg(), Defs);
912 for (auto *Def : Defs) {
913 if (Def == &MI || FalseLanesZero.count(Def) || IsZeroInit(Def))
915 if (MO.isUse() && isPredicated)
920 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
924 bool LowOverheadLoop::ValidateLiveOuts() {
925 // We want to find out if the tail-predicated version of this loop will
926 // produce the same values as the loop in its original form. For this to
927 // be true, the newly inserted implicit predication must not change the
928 // the (observable) results.
929 // We're doing this because many instructions in the loop will not be
930 // predicated and so the conversion from VPT predication to tail-predication
931 // can result in different values being produced; due to the tail-predication
932 // preventing many instructions from updating their falsely predicated
933 // lanes. This analysis assumes that all the instructions perform lane-wise
934 // operations and don't perform any exchanges.
935 // A masked load, whether through VPT or tail predication, will write zeros
936 // to any of the falsely predicated bytes. So, from the loads, we know that
937 // the false lanes are zeroed and here we're trying to track that those false
938 // lanes remain zero, or where they change, the differences are masked away
940 // All MVE stores have to be predicated, so we know that any predicate load
941 // operands, or stored results are equivalent already. Other explicitly
942 // predicated instructions will perform the same operation in the original
943 // loop and the tail-predicated form too. Because of this, we can insert
944 // loads, stores and other predicated instructions into our Predicated
945 // set and build from there.
946 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
947 SetVector<MachineInstr *> FalseLanesUnknown;
948 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
949 SmallPtrSet<MachineInstr *, 4> Predicated;
950 MachineBasicBlock *Header = ML.getHeader();
952 LLVM_DEBUG(dbgs() << "ARM Loops: Validating Live outs\n");
954 for (auto &MI : *Header) {
955 if (!shouldInspect(MI))
958 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
961 bool isPredicated = isVectorPredicated(&MI);
962 bool retainsOrReduces =
963 retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);
966 Predicated.insert(&MI);
967 if (producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero))
968 FalseLanesZero.insert(&MI);
969 else if (MI.getNumDefs() == 0)
971 else if (!isPredicated && retainsOrReduces) {
972 LLVM_DEBUG(dbgs() << " Unpredicated instruction that retainsOrReduces: " << MI);
974 } else if (!isPredicated && MI.getOpcode() != ARM::MQPRCopy)
975 FalseLanesUnknown.insert(&MI);
979 dbgs() << " Predicated:\n";
980 for (auto *I : Predicated)
982 dbgs() << " FalseLanesZero:\n";
983 for (auto *I : FalseLanesZero)
985 dbgs() << " FalseLanesUnknown:\n";
986 for (auto *I : FalseLanesUnknown)
990 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
991 SmallPtrSetImpl<MachineInstr *> &Predicated) {
992 SmallPtrSet<MachineInstr *, 2> Uses;
993 RDA.getGlobalUses(MI, MO.getReg().asMCReg(), Uses);
994 for (auto *Use : Uses) {
995 if (Use != MI && !Predicated.count(Use))
1001 // Visit the unknowns in reverse so that we can start at the values being
1002 // stored and then we can work towards the leaves, hopefully adding more
1003 // instructions to Predicated. Successfully terminating the loop means that
1004 // all the unknown values have to found to be masked by predicated user(s).
1005 // For any unpredicated values, we store them in NonPredicated so that we
1006 // can later check whether these form a reduction.
1007 SmallPtrSet<MachineInstr*, 2> NonPredicated;
1008 for (auto *MI : reverse(FalseLanesUnknown)) {
1009 for (auto &MO : MI->operands()) {
1010 if (!isRegInClass(MO, QPRs) || !MO.isDef())
1012 if (!HasPredicatedUsers(MI, MO, Predicated)) {
1013 LLVM_DEBUG(dbgs() << " Found an unknown def of : "
1014 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
1015 NonPredicated.insert(MI);
1019 // Any unknown false lanes have been masked away by the user(s).
1020 if (!NonPredicated.contains(MI))
1021 Predicated.insert(MI);
1024 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
1025 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
1026 ML.getExitBlocks(ExitBlocks);
1027 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
1028 assert(ExitBlocks.size() == 1 && "Expected a single exit block");
1029 MachineBasicBlock *ExitBB = ExitBlocks.front();
1030 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
1031 // TODO: Instead of blocking predication, we could move the vctp to the exit
1032 // block and calculate it's operand there in or the preheader.
1033 if (RegMask.PhysReg == ARM::VPR) {
1034 LLVM_DEBUG(dbgs() << " VPR is live in to the exit block.");
1037 // Check Q-regs that are live in the exit blocks. We don't collect scalars
1038 // because they won't be affected by lane predication.
1039 if (QPRs->contains(RegMask.PhysReg))
1040 if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
1041 LiveOutMIs.insert(MI);
1044 // We've already validated that any VPT predication within the loop will be
1045 // equivalent when we perform the predication transformation; so we know that
1046 // any VPT predicated instruction is predicated upon VCTP. Any live-out
1047 // instruction needs to be predicated, so check this here. The instructions
1048 // in NonPredicated have been found to be a reduction that we can ensure its
1049 // legality. Any MQPRCopy found will need to validate its input as if it was
1051 SmallVector<MachineInstr *> Worklist(LiveOutMIs.begin(), LiveOutMIs.end());
1052 while (!Worklist.empty()) {
1053 MachineInstr *MI = Worklist.pop_back_val();
1054 if (MI->getOpcode() == ARM::MQPRCopy) {
1055 VMOVCopies.insert(MI);
1056 MachineInstr *CopySrc =
1057 RDA.getUniqueReachingMIDef(MI, MI->getOperand(1).getReg());
1059 Worklist.push_back(CopySrc);
1060 } else if (NonPredicated.count(MI) && FalseLanesUnknown.contains(MI)) {
1061 LLVM_DEBUG(dbgs() << " Unable to handle live out: " << *MI);
1070 void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {
1074 // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]
1075 // can only jump back.
1076 auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,
1077 ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {
1078 MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd
1079 ? End->getOperand(1).getMBB()
1080 : End->getOperand(2).getMBB();
1081 // TODO Maybe there's cases where the target doesn't have to be the header,
1082 // but for now be safe and revert.
1083 if (TgtBB != ML.getHeader()) {
1084 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");
1088 // The WLS and LE instructions have 12-bits for the label offset. WLS
1089 // requires a positive offset, while LE uses negative.
1090 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
1091 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
1092 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
1096 if (isWhileLoopStart(*Start)) {
1097 MachineBasicBlock *TargetBB = getWhileLoopStartTargetBB(*Start);
1098 if (BBUtils->getOffsetOf(Start) > BBUtils->getOffsetOf(TargetBB) ||
1099 !BBUtils->isBBInRange(Start, TargetBB, 4094)) {
1100 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
1107 StartInsertPt = MachineBasicBlock::iterator(Start);
1108 StartInsertBB = Start->getParent();
1109 LLVM_DEBUG(dbgs() << "ARM Loops: Will insert LoopStart at "
1112 Revert = !ValidateRanges(Start, End, BBUtils, ML);
1113 CannotTailPredicate = !ValidateTailPredicate();
1116 bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {
1117 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);
1118 if (VCTPs.empty()) {
1119 VCTPs.push_back(MI);
1123 // If we find another VCTP, check whether it uses the same value as the main VCTP.
1124 // If it does, store it in the VCTPs set, else refuse it.
1125 MachineInstr *Prev = VCTPs.back();
1126 if (!Prev->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
1127 !RDA.hasSameReachingDef(Prev, MI, MI->getOperand(1).getReg().asMCReg())) {
1128 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
1129 "definition from the main VCTP");
1132 VCTPs.push_back(MI);
1136 static bool ValidateMVEStore(MachineInstr *MI, MachineLoop *ML) {
1138 auto GetFrameIndex = [](MachineMemOperand *Operand) {
1139 const PseudoSourceValue *PseudoValue = Operand->getPseudoValue();
1140 if (PseudoValue && PseudoValue->kind() == PseudoSourceValue::FixedStack) {
1141 if (const auto *FS = dyn_cast<FixedStackPseudoSourceValue>(PseudoValue)) {
1142 return FS->getFrameIndex();
1148 auto IsStackOp = [GetFrameIndex](MachineInstr *I) {
1149 switch (I->getOpcode()) {
1150 case ARM::MVE_VSTRWU32:
1151 case ARM::MVE_VLDRWU32: {
1152 return I->getOperand(1).getReg() == ARM::SP &&
1153 I->memoperands().size() == 1 &&
1154 GetFrameIndex(I->memoperands().front()) >= 0;
1161 // An unpredicated vector register spill is allowed if all of the uses of the
1162 // stack slot are within the loop
1163 if (MI->getOpcode() != ARM::MVE_VSTRWU32 || !IsStackOp(MI))
1166 // Search all blocks after the loop for accesses to the same stack slot.
1167 // ReachingDefAnalysis doesn't work for sp as it relies on registers being
1168 // live-out (which sp never is) to know what blocks to look in
1169 if (MI->memoperands().size() == 0)
1171 int FI = GetFrameIndex(MI->memoperands().front());
1173 auto &FrameInfo = MI->getParent()->getParent()->getFrameInfo();
1174 if (FI == -1 || !FrameInfo.isSpillSlotObjectIndex(FI))
1177 SmallVector<MachineBasicBlock *> Frontier;
1178 ML->getExitBlocks(Frontier);
1179 SmallPtrSet<MachineBasicBlock *, 4> Visited{MI->getParent()};
1181 while (Idx < Frontier.size()) {
1182 MachineBasicBlock *BB = Frontier[Idx];
1183 bool LookAtSuccessors = true;
1184 for (auto &I : *BB) {
1185 if (!IsStackOp(&I) || I.memoperands().size() == 0)
1187 if (GetFrameIndex(I.memoperands().front()) != FI)
1189 // If this block has a store to the stack slot before any loads then we
1190 // can ignore the block
1191 if (I.getOpcode() == ARM::MVE_VSTRWU32) {
1192 LookAtSuccessors = false;
1195 // If the store and the load are using the same stack slot then the
1196 // store isn't valid for tail predication
1197 if (I.getOpcode() == ARM::MVE_VLDRWU32)
1201 if (LookAtSuccessors) {
1202 for (auto Succ : BB->successors()) {
1203 if (!Visited.contains(Succ) && !is_contained(Frontier, Succ))
1204 Frontier.push_back(Succ);
1214 bool LowOverheadLoop::ValidateMVEInst(MachineInstr *MI) {
1215 if (CannotTailPredicate)
1218 if (!shouldInspect(*MI))
1221 if (MI->getOpcode() == ARM::MVE_VPSEL ||
1222 MI->getOpcode() == ARM::MVE_VPNOT) {
1223 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
1224 // 1) It will use the VPR as a predicate operand, but doesn't have to be
1225 // instead a VPT block, which means we can assert while building up
1226 // the VPT block because we don't find another VPT or VPST to being a new
1228 // 2) VPSEL still requires a VPR operand even after tail predicating,
1229 // which means we can't remove it unless there is another
1230 // instruction, such as vcmp, that can provide the VPR def.
1234 // Record all VCTPs and check that they're equivalent to one another.
1235 if (isVCTP(MI) && !AddVCTP(MI))
1238 // Inspect uses first so that any instructions that alter the VPR don't
1239 // alter the predicate upon themselves.
1240 const MCInstrDesc &MCID = MI->getDesc();
1242 unsigned LastOpIdx = MI->getNumOperands() - 1;
1243 for (auto &Op : enumerate(reverse(MCID.operands()))) {
1244 const MachineOperand &MO = MI->getOperand(LastOpIdx - Op.index());
1245 if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)
1248 if (ARM::isVpred(Op.value().OperandType)) {
1249 VPTState::addInst(MI);
1251 } else if (MI->getOpcode() != ARM::MVE_VPST) {
1252 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
1257 // If we find an instruction that has been marked as not valid for tail
1258 // predication, only allow the instruction if it's contained within a valid
1260 bool RequiresExplicitPredication =
1261 (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;
1262 if (isDomainMVE(MI) && RequiresExplicitPredication) {
1263 if (MI->getOpcode() == ARM::MQPRCopy)
1265 if (!IsUse && producesDoubleWidthResult(*MI)) {
1266 DoubleWidthResultInstrs.insert(MI);
1270 LLVM_DEBUG(if (!IsUse) dbgs()
1271 << "ARM Loops: Can't tail predicate: " << *MI);
1275 // If the instruction is already explicitly predicated, then the conversion
1276 // will be fine, but ensure that all store operations are predicated.
1277 if (MI->mayStore() && !ValidateMVEStore(MI, &ML))
1280 // If this instruction defines the VPR, update the predicate for the
1281 // proceeding instructions.
1282 if (isVectorPredicate(MI)) {
1283 // Clear the existing predicate when we're not in VPT Active state,
1284 // otherwise we add to it.
1285 if (!isVectorPredicated(MI))
1286 VPTState::resetPredicate(MI);
1288 VPTState::addPredicate(MI);
1291 // Finally once the predicate has been modified, we can start a new VPT
1292 // block if necessary.
1293 if (isVPTOpcode(MI->getOpcode()))
1294 VPTState::CreateVPTBlock(MI);
1299 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
1300 const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
1305 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
1307 MLI = &getAnalysis<MachineLoopInfo>();
1308 RDA = &getAnalysis<ReachingDefAnalysis>();
1309 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
1310 MRI = &MF->getRegInfo();
1311 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
1312 TRI = ST.getRegisterInfo();
1313 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
1314 BBUtils->computeAllBlockSizes();
1315 BBUtils->adjustBBOffsetsAfter(&MF->front());
1317 bool Changed = false;
1318 for (auto ML : *MLI) {
1319 if (ML->isOutermost())
1320 Changed |= ProcessLoop(ML);
1322 Changed |= RevertNonLoops();
1326 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
1328 bool Changed = false;
1330 // Process inner loops first.
1331 for (MachineLoop *L : *ML)
1332 Changed |= ProcessLoop(L);
1335 dbgs() << "ARM Loops: Processing loop containing:\n";
1336 if (auto *Preheader = ML->getLoopPreheader())
1337 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1338 else if (auto *Preheader = MLI->findLoopPreheader(ML, true, true))
1339 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1340 for (auto *MBB : ML->getBlocks())
1341 dbgs() << " - Block: " << printMBBReference(*MBB) << "\n";
1344 // Search the given block for a loop start instruction. If one isn't found,
1345 // and there's only one predecessor block, search that one too.
1346 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
1347 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
1348 for (auto &MI : *MBB) {
1349 if (isLoopStart(MI))
1352 if (MBB->pred_size() == 1)
1353 return SearchForStart(*MBB->pred_begin());
1357 LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
1358 // Search the preheader for the start intrinsic.
1359 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
1360 // with potentially multiple set.loop.iterations, so we need to enable this.
1361 if (LoLoop.Preheader)
1362 LoLoop.Start = SearchForStart(LoLoop.Preheader);
1366 // Find the low-overhead loop components and decide whether or not to fall
1367 // back to a normal loop. Also look for a vctp instructions and decide
1368 // whether we can convert that predicate using tail predication.
1369 for (auto *MBB : reverse(ML->getBlocks())) {
1370 for (auto &MI : *MBB) {
1371 if (MI.isDebugValue())
1373 else if (MI.getOpcode() == ARM::t2LoopDec)
1375 else if (MI.getOpcode() == ARM::t2LoopEnd)
1377 else if (MI.getOpcode() == ARM::t2LoopEndDec)
1378 LoLoop.End = LoLoop.Dec = &MI;
1379 else if (isLoopStart(MI))
1381 else if (MI.getDesc().isCall()) {
1382 // TODO: Though the call will require LE to execute again, does this
1383 // mean we should revert? Always executing LE hopefully should be
1384 // faster than performing a sub,cmp,br or even subs,br.
1385 LoLoop.Revert = true;
1386 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
1388 // Record VPR defs and build up their corresponding vpt blocks.
1389 // Check we know how to tail predicate any mve instructions.
1390 LoLoop.AnalyseMVEInst(&MI);
1395 LLVM_DEBUG(LoLoop.dump());
1396 if (!LoLoop.FoundAllComponents()) {
1397 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
1401 assert(LoLoop.Start->getOpcode() != ARM::t2WhileLoopStart &&
1402 "Expected t2WhileLoopStart to be removed before regalloc!");
1404 // Check that the only instruction using LoopDec is LoopEnd. This can only
1405 // happen when the Dec and End are separate, not a single t2LoopEndDec.
1406 // TODO: Check for copy chains that really have no effect.
1407 if (LoLoop.Dec != LoLoop.End) {
1408 SmallPtrSet<MachineInstr *, 2> Uses;
1409 RDA->getReachingLocalUses(LoLoop.Dec, MCRegister::from(ARM::LR), Uses);
1410 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
1411 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
1412 LoLoop.Revert = true;
1415 LoLoop.Validate(BBUtils.get());
1420 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1421 // beq that branches to the exit branch.
1422 // TODO: We could also try to generate a cbz if the value in LR is also in
1423 // another low register.
1424 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
1425 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
1426 MachineBasicBlock *DestBB = getWhileLoopStartTargetBB(*MI);
1427 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1428 ARM::tBcc : ARM::t2Bcc;
1430 RevertWhileLoopStartLR(MI, TII, BrOpc);
1433 void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {
1434 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);
1435 RevertDoLoopStart(MI, TII);
1438 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
1439 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
1440 MachineBasicBlock *MBB = MI->getParent();
1441 SmallPtrSet<MachineInstr*, 1> Ignore;
1442 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
1443 if (I->getOpcode() == ARM::t2LoopEnd) {
1449 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
1451 RDA->isSafeToDefRegAt(MI, MCRegister::from(ARM::CPSR), Ignore);
1453 llvm::RevertLoopDec(MI, TII, SetFlags);
1457 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1458 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
1459 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
1461 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1462 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1463 ARM::tBcc : ARM::t2Bcc;
1465 llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);
1468 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1469 void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {
1470 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);
1471 assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");
1472 MachineBasicBlock *MBB = MI->getParent();
1474 MachineInstrBuilder MIB =
1475 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::t2SUBri));
1476 MIB.addDef(ARM::LR);
1477 MIB.add(MI->getOperand(1));
1479 MIB.addImm(ARMCC::AL);
1480 MIB.addReg(ARM::NoRegister);
1481 MIB.addReg(ARM::CPSR);
1482 MIB->getOperand(5).setIsDef(true);
1484 MachineBasicBlock *DestBB = MI->getOperand(2).getMBB();
1486 BBUtils->isBBInRange(MI, DestBB, 254) ? ARM::tBcc : ARM::t2Bcc;
1489 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
1490 MIB.add(MI->getOperand(2)); // branch target
1491 MIB.addImm(ARMCC::NE); // condition code
1492 MIB.addReg(ARM::CPSR);
1494 MI->eraseFromParent();
1497 // Perform dead code elimation on the loop iteration count setup expression.
1498 // If we are tail-predicating, the number of elements to be processed is the
1499 // operand of the VCTP instruction in the vector body, see getCount(), which is
1500 // register $r3 in this example:
1502 // $lr = big-itercount-expression
1504 // $lr = t2DoLoopStart renamable $lr
1507 // $vpr = MVE_VCTP32 renamable $r3
1508 // renamable $lr = t2LoopDec killed renamable $lr, 1
1509 // t2LoopEnd renamable $lr, %vector.body
1512 // What we would like achieve here is to replace the do-loop start pseudo
1513 // instruction t2DoLoopStart with:
1515 // $lr = MVE_DLSTP_32 killed renamable $r3
1517 // Thus, $r3 which defines the number of elements, is written to $lr,
1518 // and then we want to delete the whole chain that used to define $lr,
1519 // see the comment below how this chain could look like.
1521 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
1522 if (!LoLoop.IsTailPredicationLegal())
1525 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
1527 MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 1);
1529 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
1533 // Collect and remove the users of iteration count.
1534 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,
1536 if (!TryRemove(Def, *RDA, LoLoop.ToRemove, Killed))
1537 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
1540 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
1541 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
1542 // When using tail-predication, try to delete the dead code that was used to
1543 // calculate the number of loop iterations.
1544 IterationCountDCE(LoLoop);
1546 MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;
1547 MachineInstr *Start = LoLoop.Start;
1548 MachineBasicBlock *MBB = LoLoop.StartInsertBB;
1549 unsigned Opc = LoLoop.getStartOpcode();
1550 MachineOperand &Count = LoLoop.getLoopStartOperand();
1552 // A DLS lr, lr we needn't emit
1553 MachineInstr* NewStart;
1554 if (Opc == ARM::t2DLS && Count.isReg() && Count.getReg() == ARM::LR) {
1555 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't insert start: DLS lr, lr");
1558 MachineInstrBuilder MIB =
1559 BuildMI(*MBB, InsertPt, Start->getDebugLoc(), TII->get(Opc));
1561 MIB.addDef(ARM::LR);
1563 if (isWhileLoopStart(*Start))
1564 MIB.addMBB(getWhileLoopStartTargetBB(*Start));
1566 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
1570 LoLoop.ToRemove.insert(Start);
1574 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
1575 auto RemovePredicate = [](MachineInstr *MI) {
1576 if (MI->isDebugInstr())
1578 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
1579 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
1580 assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");
1581 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
1582 "Expected Then predicate!");
1583 MI->getOperand(PIdx).setImm(ARMVCC::None);
1584 MI->getOperand(PIdx + 1).setReg(0);
1587 for (auto &Block : LoLoop.getVPTBlocks()) {
1588 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
1590 auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {
1591 assert(TheVCMP && "Replacing a removed or non-existent VCMP");
1592 // Replace the VCMP with a VPT
1593 MachineInstrBuilder MIB =
1594 BuildMI(*At->getParent(), At, At->getDebugLoc(),
1595 TII->get(VCMPOpcodeToVPT(TheVCMP->getOpcode())));
1596 MIB.addImm(ARMVCC::Then);
1598 MIB.add(TheVCMP->getOperand(1));
1600 MIB.add(TheVCMP->getOperand(2));
1601 // The comparison code, e.g. ge, eq, lt
1602 MIB.add(TheVCMP->getOperand(3));
1603 LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);
1604 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1605 LoLoop.ToRemove.insert(TheVCMP);
1609 if (VPTState::isEntryPredicatedOnVCTP(Block, /*exclusive*/ true)) {
1610 MachineInstr *VPST = Insts.front();
1611 if (VPTState::hasUniformPredicate(Block)) {
1612 // A vpt block starting with VPST, is only predicated upon vctp and has no
1613 // internal vpr defs:
1615 // - Unpredicate the remaining instructions.
1616 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1617 for (unsigned i = 1; i < Insts.size(); ++i)
1618 RemovePredicate(Insts[i]);
1620 // The VPT block has a non-uniform predicate but it uses a vpst and its
1621 // entry is guarded only by a vctp, which means we:
1622 // - Need to remove the original vpst.
1623 // - Then need to unpredicate any following instructions, until
1624 // we come across the divergent vpr def.
1625 // - Insert a new vpst to predicate the instruction(s) that following
1626 // the divergent vpr def.
1627 MachineInstr *Divergent = VPTState::getDivergent(Block);
1628 MachineBasicBlock *MBB = Divergent->getParent();
1629 auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);
1630 while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())
1633 bool DivergentNextIsPredicated =
1634 DivergentNext != MBB->end() &&
1635 getVPTInstrPredicate(*DivergentNext) != ARMVCC::None;
1637 for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;
1639 RemovePredicate(&*I);
1641 // Check if the instruction defining vpr is a vcmp so it can be combined
1642 // with the VPST This should be the divergent instruction
1643 MachineInstr *VCMP =
1644 VCMPOpcodeToVPT(Divergent->getOpcode()) != 0 ? Divergent : nullptr;
1646 if (DivergentNextIsPredicated) {
1647 // Insert a VPST at the divergent only if the next instruction
1648 // would actually use it. A VCMP following a VPST can be
1649 // merged into a VPT so do that instead if the VCMP exists.
1651 // Create a VPST (with a null mask for now, we'll recompute it
1653 MachineInstrBuilder MIB =
1654 BuildMI(*Divergent->getParent(), Divergent,
1655 Divergent->getDebugLoc(), TII->get(ARM::MVE_VPST));
1657 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
1658 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1660 // No RDA checks are necessary here since the VPST would have been
1661 // directly after the VCMP
1662 ReplaceVCMPWithVPT(VCMP, VCMP);
1666 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1667 LoLoop.ToRemove.insert(VPST);
1668 } else if (Block.containsVCTP()) {
1669 // The vctp will be removed, so either the entire block will be dead or
1670 // the block mask of the vp(s)t will need to be recomputed.
1671 MachineInstr *VPST = Insts.front();
1672 if (Block.size() == 2) {
1673 assert(VPST->getOpcode() == ARM::MVE_VPST &&
1674 "Found a VPST in an otherwise empty vpt block");
1675 LoLoop.ToRemove.insert(VPST);
1677 LoLoop.BlockMasksToRecompute.insert(VPST);
1678 } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {
1679 // If this block starts with a VPST then attempt to merge it with the
1680 // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT
1681 // block that no longer exists
1682 MachineInstr *VPST = Insts.front();
1683 auto Next = ++MachineBasicBlock::iterator(VPST);
1684 assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&
1685 "The instruction after a VPST must be predicated");
1687 MachineInstr *VprDef = RDA->getUniqueReachingMIDef(VPST, ARM::VPR);
1688 if (VprDef && VCMPOpcodeToVPT(VprDef->getOpcode()) &&
1689 !LoLoop.ToRemove.contains(VprDef)) {
1690 MachineInstr *VCMP = VprDef;
1691 // The VCMP and VPST can only be merged if the VCMP's operands will have
1692 // the same values at the VPST.
1693 // If any of the instructions between the VCMP and VPST are predicated
1694 // then a different code path is expected to have merged the VCMP and
1696 if (std::none_of(++MachineBasicBlock::iterator(VCMP),
1697 MachineBasicBlock::iterator(VPST), hasVPRUse) &&
1698 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(1).getReg()) &&
1699 RDA->hasSameReachingDef(VCMP, VPST, VCMP->getOperand(2).getReg())) {
1700 ReplaceVCMPWithVPT(VCMP, VPST);
1701 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1702 LoLoop.ToRemove.insert(VPST);
1708 LoLoop.ToRemove.insert(LoLoop.VCTPs.begin(), LoLoop.VCTPs.end());
1711 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
1713 // Combine the LoopDec and LoopEnd instructions into LE(TP).
1714 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
1715 MachineInstr *End = LoLoop.End;
1716 MachineBasicBlock *MBB = End->getParent();
1717 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
1718 ARM::MVE_LETP : ARM::t2LEUpdate;
1719 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
1721 MIB.addDef(ARM::LR);
1722 unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;
1723 MIB.add(End->getOperand(Off + 0));
1724 MIB.add(End->getOperand(Off + 1));
1725 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
1726 LoLoop.ToRemove.insert(LoLoop.Dec);
1727 LoLoop.ToRemove.insert(End);
1731 // TODO: We should be able to automatically remove these branches before we
1732 // get here - probably by teaching analyzeBranch about the pseudo
1734 // If there is an unconditional branch, after I, that just branches to the
1735 // next block, remove it.
1736 auto RemoveDeadBranch = [](MachineInstr *I) {
1737 MachineBasicBlock *BB = I->getParent();
1738 MachineInstr *Terminator = &BB->instr_back();
1739 if (Terminator->isUnconditionalBranch() && I != Terminator) {
1740 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
1741 if (BB->isLayoutSuccessor(Succ)) {
1742 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
1743 Terminator->eraseFromParent();
1748 // And VMOVCopies need to become 2xVMOVD for tail predication to be valid.
1749 // Anything other MQPRCopy can be converted to MVE_VORR later on.
1750 auto ExpandVMOVCopies = [this](SmallPtrSet<MachineInstr *, 4> &VMOVCopies) {
1751 for (auto *MI : VMOVCopies) {
1752 LLVM_DEBUG(dbgs() << "Converting copy to VMOVD: " << *MI);
1753 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1754 MachineBasicBlock *MBB = MI->getParent();
1755 Register Dst = MI->getOperand(0).getReg();
1756 Register Src = MI->getOperand(1).getReg();
1757 auto MIB1 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),
1758 ARM::D0 + (Dst - ARM::Q0) * 2)
1759 .addReg(ARM::D0 + (Src - ARM::Q0) * 2)
1760 .add(predOps(ARMCC::AL));
1762 LLVM_DEBUG(dbgs() << " into " << *MIB1);
1763 auto MIB2 = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::VMOVD),
1764 ARM::D0 + (Dst - ARM::Q0) * 2 + 1)
1765 .addReg(ARM::D0 + (Src - ARM::Q0) * 2 + 1)
1766 .add(predOps(ARMCC::AL));
1767 LLVM_DEBUG(dbgs() << " and " << *MIB2);
1769 MI->eraseFromParent();
1773 if (LoLoop.Revert) {
1774 if (isWhileLoopStart(*LoLoop.Start))
1775 RevertWhile(LoLoop.Start);
1777 RevertDo(LoLoop.Start);
1778 if (LoLoop.Dec == LoLoop.End)
1779 RevertLoopEndDec(LoLoop.End);
1781 RevertLoopEnd(LoLoop.End, RevertLoopDec(LoLoop.Dec));
1783 ExpandVMOVCopies(LoLoop.VMOVCopies);
1784 LoLoop.Start = ExpandLoopStart(LoLoop);
1786 RemoveDeadBranch(LoLoop.Start);
1787 LoLoop.End = ExpandLoopEnd(LoLoop);
1788 RemoveDeadBranch(LoLoop.End);
1789 if (LoLoop.IsTailPredicationLegal())
1790 ConvertVPTBlocks(LoLoop);
1791 for (auto *I : LoLoop.ToRemove) {
1792 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
1793 I->eraseFromParent();
1795 for (auto *I : LoLoop.BlockMasksToRecompute) {
1796 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
1797 recomputeVPTBlockMask(*I);
1798 LLVM_DEBUG(dbgs() << " ... done: " << *I);
1802 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
1804 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
1805 for (auto *MBB : PostOrder) {
1806 recomputeLiveIns(*MBB);
1807 // FIXME: For some reason, the live-in print order is non-deterministic for
1808 // our tests and I can't out why... So just sort them.
1809 MBB->sortUniqueLiveIns();
1812 for (auto *MBB : reverse(PostOrder))
1813 recomputeLivenessFlags(*MBB);
1815 // We've moved, removed and inserted new instructions, so update RDA.
1819 bool ARMLowOverheadLoops::RevertNonLoops() {
1820 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1821 bool Changed = false;
1823 for (auto &MBB : *MF) {
1824 SmallVector<MachineInstr*, 4> Starts;
1825 SmallVector<MachineInstr*, 4> Decs;
1826 SmallVector<MachineInstr*, 4> Ends;
1827 SmallVector<MachineInstr *, 4> EndDecs;
1828 SmallVector<MachineInstr *, 4> MQPRCopies;
1830 for (auto &I : MBB) {
1832 Starts.push_back(&I);
1833 else if (I.getOpcode() == ARM::t2LoopDec)
1835 else if (I.getOpcode() == ARM::t2LoopEnd)
1837 else if (I.getOpcode() == ARM::t2LoopEndDec)
1838 EndDecs.push_back(&I);
1839 else if (I.getOpcode() == ARM::MQPRCopy)
1840 MQPRCopies.push_back(&I);
1843 if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty() &&
1849 for (auto *Start : Starts) {
1850 if (isWhileLoopStart(*Start))
1855 for (auto *Dec : Decs)
1858 for (auto *End : Ends)
1860 for (auto *End : EndDecs)
1861 RevertLoopEndDec(End);
1862 for (auto *MI : MQPRCopies) {
1863 LLVM_DEBUG(dbgs() << "Converting copy to VORR: " << *MI);
1864 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1865 MachineBasicBlock *MBB = MI->getParent();
1866 auto MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(ARM::MVE_VORR),
1867 MI->getOperand(0).getReg())
1868 .add(MI->getOperand(1))
1869 .add(MI->getOperand(1));
1870 addUnpredicatedMveVpredROp(MIB, MI->getOperand(0).getReg());
1871 MI->eraseFromParent();
1877 FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1878 return new ARMLowOverheadLoops();