1 //===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 /// Finalize v8.1-m low-overhead loops by converting the associated pseudo
10 /// instructions into machine operations.
11 /// The expectation is that the loop contains three pseudo instructions:
12 /// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
13 /// form should be in the preheader, whereas the while form should be in the
14 /// preheaders only predecessor.
15 /// - t2LoopDec - placed within in the loop body.
16 /// - t2LoopEnd - the loop latch terminator.
18 /// In addition to this, we also look for the presence of the VCTP instruction,
19 /// which determines whether we can generated the tail-predicated low-overhead
22 /// Assumptions and Dependencies:
23 /// Low-overhead loops are constructed and executed using a setup instruction:
24 /// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
25 /// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
26 /// but fixed polarity: WLS can only branch forwards and LE can only branch
27 /// backwards. These restrictions mean that this pass is dependent upon block
28 /// layout and block sizes, which is why it's the last pass to run. The same is
29 /// true for ConstantIslands, but this pass does not increase the size of the
30 /// basic blocks, nor does it change the CFG. Instructions are mainly removed
31 /// during the transform and pseudo instructions are replaced by real ones. In
32 /// some cases, when we have to revert to a 'normal' loop, we have to introduce
33 /// multiple instructions for a single pseudo (see RevertWhile and
34 /// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
35 /// are defined to be as large as this maximum sequence of replacement
38 //===----------------------------------------------------------------------===//
41 #include "ARMBaseInstrInfo.h"
42 #include "ARMBaseRegisterInfo.h"
43 #include "ARMBasicBlockInfo.h"
44 #include "ARMSubtarget.h"
45 #include "Thumb2InstrInfo.h"
46 #include "llvm/ADT/SetOperations.h"
47 #include "llvm/ADT/SmallSet.h"
48 #include "llvm/CodeGen/MachineFunctionPass.h"
49 #include "llvm/CodeGen/MachineLoopInfo.h"
50 #include "llvm/CodeGen/MachineLoopUtils.h"
51 #include "llvm/CodeGen/MachineRegisterInfo.h"
52 #include "llvm/CodeGen/Passes.h"
53 #include "llvm/CodeGen/ReachingDefAnalysis.h"
54 #include "llvm/MC/MCInstrDesc.h"
58 #define DEBUG_TYPE "arm-low-overhead-loops"
59 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
64 MachineInstr *MI = nullptr;
65 SetVector<MachineInstr*> Predicates;
68 PredicatedMI(MachineInstr *I, SetVector<MachineInstr*> &Preds) :
70 Predicates.insert(Preds.begin(), Preds.end());
74 // Represent a VPT block, a list of instructions that begins with a VPST and
75 // has a maximum of four proceeding instructions. All instructions within the
76 // block are predicated upon the vpr and we allow instructions to define the
77 // vpr within in the block too.
79 std::unique_ptr<PredicatedMI> VPST;
80 PredicatedMI *Divergent = nullptr;
81 SmallVector<PredicatedMI, 4> Insts;
84 VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
85 VPST = std::make_unique<PredicatedMI>(MI, Preds);
88 void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
89 LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI);
90 if (!Divergent && !set_difference(Preds, VPST->Predicates).empty()) {
91 Divergent = &Insts.back();
92 LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI);
94 Insts.emplace_back(MI, Preds);
95 assert(Insts.size() <= 4 && "Too many instructions in VPT block!");
98 // Have we found an instruction within the block which defines the vpr? If
99 // so, not all the instructions in the block will have the same predicate.
100 bool HasNonUniformPredicate() const {
101 return Divergent != nullptr;
104 // Is the given instruction part of the predicate set controlling the entry
106 bool IsPredicatedOn(MachineInstr *MI) const {
107 return VPST->Predicates.count(MI);
110 // Is the given instruction the only predicate which controls the entry to
112 bool IsOnlyPredicatedOn(MachineInstr *MI) const {
113 return IsPredicatedOn(MI) && VPST->Predicates.size() == 1;
116 unsigned size() const { return Insts.size(); }
117 SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; }
118 MachineInstr *getVPST() const { return VPST->MI; }
119 PredicatedMI *getDivergent() const { return Divergent; }
122 struct LowOverheadLoop {
124 MachineLoop *ML = nullptr;
125 MachineFunction *MF = nullptr;
126 MachineInstr *InsertPt = nullptr;
127 MachineInstr *Start = nullptr;
128 MachineInstr *Dec = nullptr;
129 MachineInstr *End = nullptr;
130 MachineInstr *VCTP = nullptr;
131 VPTBlock *CurrentBlock = nullptr;
132 SetVector<MachineInstr*> CurrentPredicate;
133 SmallVector<VPTBlock, 4> VPTBlocks;
135 bool CannotTailPredicate = false;
137 LowOverheadLoop(MachineLoop *ML) : ML(ML) {
138 MF = ML->getHeader()->getParent();
141 // If this is an MVE instruction, check that we know how to use tail
142 // predication with it. Record VPT blocks and return whether the
143 // instruction is valid for tail predication.
144 bool ValidateMVEInst(MachineInstr *MI);
146 void AnalyseMVEInst(MachineInstr *MI) {
147 CannotTailPredicate = !ValidateMVEInst(MI);
150 bool IsTailPredicationLegal() const {
151 // For now, let's keep things really simple and only support a single
152 // block for tail predication.
153 return !Revert && FoundAllComponents() && VCTP &&
154 !CannotTailPredicate && ML->getNumBlocks() == 1;
157 bool ValidateTailPredicate(MachineInstr *StartInsertPt,
158 ReachingDefAnalysis *RDA,
159 MachineLoopInfo *MLI);
161 // Is it safe to define LR with DLS/WLS?
162 // LR can be defined if it is the operand to start, because it's the same
163 // value, or if it's going to be equivalent to the operand to Start.
164 MachineInstr *IsSafeToDefineLR(ReachingDefAnalysis *RDA);
166 // Check the branch targets are within range and we satisfy our
168 void CheckLegality(ARMBasicBlockUtils *BBUtils, ReachingDefAnalysis *RDA,
169 MachineLoopInfo *MLI);
171 bool FoundAllComponents() const {
172 return Start && Dec && End;
175 SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; }
177 // Return the loop iteration count, or the number of elements if we're tail
179 MachineOperand &getCount() {
180 return IsTailPredicationLegal() ?
181 VCTP->getOperand(1) : Start->getOperand(0);
184 unsigned getStartOpcode() const {
185 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
186 if (!IsTailPredicationLegal())
187 return IsDo ? ARM::t2DLS : ARM::t2WLS;
189 return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo);
193 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
194 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
195 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
196 if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP;
197 if (!FoundAllComponents())
198 dbgs() << "ARM Loops: Not a low-overhead loop.\n";
199 else if (!(Start && Dec && End))
200 dbgs() << "ARM Loops: Failed to find all loop components.\n";
204 class ARMLowOverheadLoops : public MachineFunctionPass {
205 MachineFunction *MF = nullptr;
206 MachineLoopInfo *MLI = nullptr;
207 ReachingDefAnalysis *RDA = nullptr;
208 const ARMBaseInstrInfo *TII = nullptr;
209 MachineRegisterInfo *MRI = nullptr;
210 const TargetRegisterInfo *TRI = nullptr;
211 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
216 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
218 void getAnalysisUsage(AnalysisUsage &AU) const override {
219 AU.setPreservesCFG();
220 AU.addRequired<MachineLoopInfo>();
221 AU.addRequired<ReachingDefAnalysis>();
222 MachineFunctionPass::getAnalysisUsage(AU);
225 bool runOnMachineFunction(MachineFunction &MF) override;
227 MachineFunctionProperties getRequiredProperties() const override {
228 return MachineFunctionProperties().set(
229 MachineFunctionProperties::Property::NoVRegs).set(
230 MachineFunctionProperties::Property::TracksLiveness);
233 StringRef getPassName() const override {
234 return ARM_LOW_OVERHEAD_LOOPS_NAME;
238 bool ProcessLoop(MachineLoop *ML);
240 bool RevertNonLoops();
242 void RevertWhile(MachineInstr *MI) const;
244 bool RevertLoopDec(MachineInstr *MI, bool AllowFlags = false) const;
246 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
248 void RemoveLoopUpdate(LowOverheadLoop &LoLoop);
250 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
252 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
254 void Expand(LowOverheadLoop &LoLoop);
259 char ARMLowOverheadLoops::ID = 0;
261 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
264 MachineInstr *LowOverheadLoop::IsSafeToDefineLR(ReachingDefAnalysis *RDA) {
265 // We can define LR because LR already contains the same value.
266 if (Start->getOperand(0).getReg() == ARM::LR)
269 unsigned CountReg = Start->getOperand(0).getReg();
270 auto IsMoveLR = [&CountReg](MachineInstr *MI) {
271 return MI->getOpcode() == ARM::tMOVr &&
272 MI->getOperand(0).getReg() == ARM::LR &&
273 MI->getOperand(1).getReg() == CountReg &&
274 MI->getOperand(2).getImm() == ARMCC::AL;
277 MachineBasicBlock *MBB = Start->getParent();
279 // Find an insertion point:
280 // - Is there a (mov lr, Count) before Start? If so, and nothing else writes
281 // to Count before Start, we can insert at that mov.
282 if (auto *LRDef = RDA->getReachingMIDef(Start, ARM::LR))
283 if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
286 // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
287 // to Count after Start, we can insert at that mov.
288 if (auto *LRDef = RDA->getLocalLiveOutMIDef(MBB, ARM::LR))
289 if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
292 // We've found no suitable LR def and Start doesn't use LR directly. Can we
293 // just define LR anyway?
294 if (!RDA->isRegUsedAfter(Start, ARM::LR))
300 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
301 // not define a register that is used by any instructions, after and including,
302 // 'To'. These instructions also must not redefine any of Froms operands.
303 template<typename Iterator>
304 static bool IsSafeToMove(MachineInstr *From, MachineInstr *To, ReachingDefAnalysis *RDA) {
305 SmallSet<int, 2> Defs;
306 // First check that From would compute the same value if moved.
307 for (auto &MO : From->operands()) {
308 if (!MO.isReg() || MO.isUndef() || !MO.getReg())
311 Defs.insert(MO.getReg());
312 else if (!RDA->hasSameReachingDef(From, To, MO.getReg()))
316 // Now walk checking that the rest of the instructions will compute the same
318 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
319 for (auto &MO : I->operands())
320 if (MO.isReg() && MO.getReg() && MO.isUse() && Defs.count(MO.getReg()))
326 bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt,
327 ReachingDefAnalysis *RDA, MachineLoopInfo *MLI) {
328 assert(VCTP && "VCTP instruction expected but is not set");
329 // All predication within the loop should be based on vctp. If the block
330 // isn't predicated on entry, check whether the vctp is within the block
331 // and that all other instructions are then predicated on it.
332 for (auto &Block : VPTBlocks) {
333 if (Block.IsPredicatedOn(VCTP))
335 if (!Block.HasNonUniformPredicate() || !isVCTP(Block.getDivergent()->MI)) {
336 LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: "
337 << *Block.getDivergent()->MI);
340 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
341 for (auto &PredMI : Insts) {
342 if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI))
344 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MI
345 << " - which is predicated on:\n";
346 for (auto *MI : PredMI.Predicates)
347 dbgs() << " - " << *MI;
353 // For tail predication, we need to provide the number of elements, instead
354 // of the iteration count, to the loop start instruction. The number of
355 // elements is provided to the vctp instruction, so we need to check that
356 // we can use this register at InsertPt.
357 Register NumElements = VCTP->getOperand(1).getReg();
359 // If the register is defined within loop, then we can't perform TP.
360 // TODO: Check whether this is just a mov of a register that would be
362 if (RDA->getReachingDef(VCTP, NumElements) >= 0) {
363 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
367 // The element count register maybe defined after InsertPt, in which case we
368 // need to try to move either InsertPt or the def so that the [w|d]lstp can
370 MachineBasicBlock *InsertBB = InsertPt->getParent();
371 if (!RDA->isReachingDefLiveOut(InsertPt, NumElements)) {
372 if (auto *ElemDef = RDA->getLocalLiveOutMIDef(InsertBB, NumElements)) {
373 if (IsSafeToMove<MachineBasicBlock::reverse_iterator>(ElemDef, InsertPt, RDA)) {
374 ElemDef->removeFromParent();
375 InsertBB->insert(MachineBasicBlock::iterator(InsertPt), ElemDef);
376 LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: "
378 } else if (IsSafeToMove<MachineBasicBlock::iterator>(InsertPt, ElemDef, RDA)) {
379 InsertPt->removeFromParent();
380 InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef), InsertPt);
381 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
383 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to move element count to loop "
384 << "start instruction.\n");
390 // Especially in the case of while loops, InsertBB may not be the
391 // preheader, so we need to check that the register isn't redefined
392 // before entering the loop.
393 auto CannotProvideElements = [&RDA](MachineBasicBlock *MBB,
394 Register NumElements) {
395 // NumElements is redefined in this block.
396 if (RDA->getReachingDef(&MBB->back(), NumElements) >= 0)
399 // Don't continue searching up through multiple predecessors.
400 if (MBB->pred_size() > 1)
406 // First, find the block that looks like the preheader.
407 MachineBasicBlock *MBB = MLI->findLoopPreheader(ML, true);
409 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n");
413 // Then search backwards for a def, until we get to InsertBB.
414 while (MBB != InsertBB) {
415 if (CannotProvideElements(MBB, NumElements)) {
416 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
419 MBB = *MBB->pred_begin();
422 LLVM_DEBUG(dbgs() << "ARM Loops: Will use tail predication.\n");
426 void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils,
427 ReachingDefAnalysis *RDA,
428 MachineLoopInfo *MLI) {
432 if (!End->getOperand(1).isMBB())
433 report_fatal_error("Expected LoopEnd to target basic block");
435 // TODO Maybe there's cases where the target doesn't have to be the header,
436 // but for now be safe and revert.
437 if (End->getOperand(1).getMBB() != ML->getHeader()) {
438 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n");
443 // The WLS and LE instructions have 12-bits for the label offset. WLS
444 // requires a positive offset, while LE uses negative.
445 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) ||
446 !BBUtils->isBBInRange(End, ML->getHeader(), 4094)) {
447 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
452 if (Start->getOpcode() == ARM::t2WhileLoopStart &&
453 (BBUtils->getOffsetOf(Start) >
454 BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
455 !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
456 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
461 InsertPt = Revert ? nullptr : IsSafeToDefineLR(RDA);
463 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
467 LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
469 if (!IsTailPredicationLegal()) {
470 LLVM_DEBUG(if (!VCTP)
471 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
472 dbgs() << "ARM Loops: Tail-predication is not valid.\n");
476 assert(ML->getBlocks().size() == 1 &&
477 "Shouldn't be processing a loop with more than one block");
478 CannotTailPredicate = !ValidateTailPredicate(InsertPt, RDA, MLI);
479 LLVM_DEBUG(if (CannotTailPredicate)
480 dbgs() << "ARM Loops: Couldn't validate tail predicate.\n");
483 bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
484 if (CannotTailPredicate)
487 // Only support a single vctp.
488 if (isVCTP(MI) && VCTP)
491 // Start a new vpt block when we discover a vpt.
492 if (MI->getOpcode() == ARM::MVE_VPST) {
493 VPTBlocks.emplace_back(MI, CurrentPredicate);
494 CurrentBlock = &VPTBlocks.back();
496 } else if (isVCTP(MI))
498 else if (MI->getOpcode() == ARM::MVE_VPSEL ||
499 MI->getOpcode() == ARM::MVE_VPNOT)
502 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
503 // 1) It will use the VPR as a predicate operand, but doesn't have to be
504 // instead a VPT block, which means we can assert while building up
505 // the VPT block because we don't find another VPST to being a new
507 // 2) VPSEL still requires a VPR operand even after tail predicating,
508 // which means we can't remove it unless there is another
509 // instruction, such as vcmp, that can provide the VPR def.
513 const MCInstrDesc &MCID = MI->getDesc();
514 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
515 const MachineOperand &MO = MI->getOperand(i);
516 if (!MO.isReg() || MO.getReg() != ARM::VPR)
520 CurrentPredicate.insert(MI);
522 } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) {
523 CurrentBlock->addInst(MI, CurrentPredicate);
526 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
531 // If we find a vpr def that is not already predicated on the vctp, we've
532 // got disjoint predicates that may not be equivalent when we do the
534 if (IsDef && !IsUse && VCTP && !isVCTP(MI)) {
535 LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI);
539 uint64_t Flags = MCID.TSFlags;
540 if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
543 // If we find an instruction that has been marked as not valid for tail
544 // predication, only allow the instruction if it's contained within a valid
546 if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) {
547 LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI);
554 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
555 const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
560 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
562 MLI = &getAnalysis<MachineLoopInfo>();
563 RDA = &getAnalysis<ReachingDefAnalysis>();
564 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
565 MRI = &MF->getRegInfo();
566 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
567 TRI = ST.getRegisterInfo();
568 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
569 BBUtils->computeAllBlockSizes();
570 BBUtils->adjustBBOffsetsAfter(&MF->front());
572 bool Changed = false;
573 for (auto ML : *MLI) {
574 if (!ML->getParentLoop())
575 Changed |= ProcessLoop(ML);
577 Changed |= RevertNonLoops();
581 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
583 bool Changed = false;
585 // Process inner loops first.
586 for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
587 Changed |= ProcessLoop(*I);
589 LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";
590 if (auto *Preheader = ML->getLoopPreheader())
591 dbgs() << " - " << Preheader->getName() << "\n";
592 else if (auto *Preheader = MLI->findLoopPreheader(ML))
593 dbgs() << " - " << Preheader->getName() << "\n";
594 for (auto *MBB : ML->getBlocks())
595 dbgs() << " - " << MBB->getName() << "\n";
598 // Search the given block for a loop start instruction. If one isn't found,
599 // and there's only one predecessor block, search that one too.
600 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
601 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
602 for (auto &MI : *MBB) {
606 if (MBB->pred_size() == 1)
607 return SearchForStart(*MBB->pred_begin());
611 LowOverheadLoop LoLoop(ML);
612 // Search the preheader for the start intrinsic.
613 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
614 // with potentially multiple set.loop.iterations, so we need to enable this.
615 if (auto *Preheader = ML->getLoopPreheader())
616 LoLoop.Start = SearchForStart(Preheader);
617 else if (auto *Preheader = MLI->findLoopPreheader(ML, true))
618 LoLoop.Start = SearchForStart(Preheader);
622 // Find the low-overhead loop components and decide whether or not to fall
623 // back to a normal loop. Also look for a vctp instructions and decide
624 // whether we can convert that predicate using tail predication.
625 for (auto *MBB : reverse(ML->getBlocks())) {
626 for (auto &MI : *MBB) {
627 if (MI.getOpcode() == ARM::t2LoopDec)
629 else if (MI.getOpcode() == ARM::t2LoopEnd)
631 else if (isLoopStart(MI))
633 else if (MI.getDesc().isCall()) {
634 // TODO: Though the call will require LE to execute again, does this
635 // mean we should revert? Always executing LE hopefully should be
636 // faster than performing a sub,cmp,br or even subs,br.
637 LoLoop.Revert = true;
638 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
640 // Record VPR defs and build up their corresponding vpt blocks.
641 // Check we know how to tail predicate any mve instructions.
642 LoLoop.AnalyseMVEInst(&MI);
645 // We need to ensure that LR is not used or defined inbetween LoopDec and
647 if (!LoLoop.Dec || LoLoop.End || LoLoop.Revert)
650 // If we find that LR has been written or read between LoopDec and
651 // LoopEnd, expect that the decremented value is being used else where.
652 // Because this value isn't actually going to be produced until the
653 // latch, by LE, we would need to generate a real sub. The value is also
654 // likely to be copied/reloaded for use of LoopEnd - in which in case
655 // we'd need to perform an add because it gets subtracted again by LE!
656 // The other option is to then generate the other form of LE which doesn't
658 for (auto &MO : MI.operands()) {
659 if (MI.getOpcode() != ARM::t2LoopDec && MO.isReg() &&
660 MO.getReg() == ARM::LR) {
661 LLVM_DEBUG(dbgs() << "ARM Loops: Found LR Use/Def: " << MI);
662 LoLoop.Revert = true;
669 LLVM_DEBUG(LoLoop.dump());
670 if (!LoLoop.FoundAllComponents()) {
671 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
675 LoLoop.CheckLegality(BBUtils.get(), RDA, MLI);
680 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
681 // beq that branches to the exit branch.
682 // TODO: We could also try to generate a cbz if the value in LR is also in
683 // another low register.
684 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
685 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
686 MachineBasicBlock *MBB = MI->getParent();
687 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
688 TII->get(ARM::t2CMPri));
689 MIB.add(MI->getOperand(0));
691 MIB.addImm(ARMCC::AL);
692 MIB.addReg(ARM::NoRegister);
694 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
695 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
696 ARM::tBcc : ARM::t2Bcc;
698 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
699 MIB.add(MI->getOperand(1)); // branch target
700 MIB.addImm(ARMCC::EQ); // condition code
701 MIB.addReg(ARM::CPSR);
702 MI->eraseFromParent();
705 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI,
706 bool SetFlags) const {
707 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
708 MachineBasicBlock *MBB = MI->getParent();
710 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
712 (RDA->isRegUsedAfter(MI, ARM::CPSR) ||
713 !RDA->hasSameReachingDef(MI, &MBB->back(), ARM::CPSR)))
716 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
717 TII->get(ARM::t2SUBri));
719 MIB.add(MI->getOperand(1));
720 MIB.add(MI->getOperand(2));
721 MIB.addImm(ARMCC::AL);
725 MIB.addReg(ARM::CPSR);
726 MIB->getOperand(5).setIsDef(true);
730 MI->eraseFromParent();
734 // Generate a subs, or sub and cmp, and a branch instead of an LE.
735 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
736 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
738 MachineBasicBlock *MBB = MI->getParent();
741 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
742 TII->get(ARM::t2CMPri));
745 MIB.addImm(ARMCC::AL);
746 MIB.addReg(ARM::NoRegister);
749 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
750 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
751 ARM::tBcc : ARM::t2Bcc;
754 MachineInstrBuilder MIB =
755 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
756 MIB.add(MI->getOperand(1)); // branch target
757 MIB.addImm(ARMCC::NE); // condition code
758 MIB.addReg(ARM::CPSR);
759 MI->eraseFromParent();
762 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
763 MachineInstr *InsertPt = LoLoop.InsertPt;
764 MachineInstr *Start = LoLoop.Start;
765 MachineBasicBlock *MBB = InsertPt->getParent();
766 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
767 unsigned Opc = LoLoop.getStartOpcode();
768 MachineOperand &Count = LoLoop.getCount();
770 MachineInstrBuilder MIB =
771 BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));
776 MIB.add(Start->getOperand(1));
778 // When using tail-predication, try to delete the dead code that was used to
779 // calculate the number of loop iterations.
780 if (LoLoop.IsTailPredicationLegal()) {
781 SmallVector<MachineInstr*, 4> Killed;
782 SmallVector<MachineInstr*, 4> Dead;
783 if (auto *Def = RDA->getReachingMIDef(Start,
784 Start->getOperand(0).getReg())) {
785 Killed.push_back(Def);
787 while (!Killed.empty()) {
788 MachineInstr *Def = Killed.back();
791 for (auto &MO : Def->operands()) {
792 if (!MO.isReg() || !MO.isKill())
795 MachineInstr *Kill = RDA->getReachingMIDef(Def, MO.getReg());
796 if (Kill && RDA->getNumUses(Kill, MO.getReg()) == 1)
797 Killed.push_back(Kill);
800 for (auto *MI : Dead)
801 MI->eraseFromParent();
805 // If we're inserting at a mov lr, then remove it as it's redundant.
806 if (InsertPt != Start)
807 InsertPt->eraseFromParent();
808 Start->eraseFromParent();
809 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
813 // Goal is to optimise and clean-up these loops:
816 // renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg
817 // renamable $r3, dead $cpsr = tSUBi8 killed renamable $r3(tied-def 0), 4
819 // $lr = MVE_DLSTP_32 renamable $r3
821 // The SUB is the old update of the loop iteration count expression, which
822 // is no longer needed. This sub is removed when the element count, which is in
823 // r3 in this example, is defined by an instruction in the loop, and it has
826 void ARMLowOverheadLoops::RemoveLoopUpdate(LowOverheadLoop &LoLoop) {
827 Register ElemCount = LoLoop.VCTP->getOperand(1).getReg();
828 MachineInstr *LastInstrInBlock = &LoLoop.VCTP->getParent()->back();
830 LLVM_DEBUG(dbgs() << "ARM Loops: Trying to remove loop update stmt\n");
832 if (LoLoop.ML->getNumBlocks() != 1) {
833 LLVM_DEBUG(dbgs() << "ARM Loops: Single block loop expected\n");
837 LLVM_DEBUG(dbgs() << "ARM Loops: Analyzing elemcount in operand: ";
838 LoLoop.VCTP->getOperand(1).dump());
840 // Find the definition we are interested in removing, if there is one.
841 MachineInstr *Def = RDA->getReachingMIDef(LastInstrInBlock, ElemCount);
843 LLVM_DEBUG(dbgs() << "ARM Loops: Can't find a def, nothing to do.\n");
847 // Bail if we define CPSR and it is not dead
848 if (!Def->registerDefIsDead(ARM::CPSR, TRI)) {
849 LLVM_DEBUG(dbgs() << "ARM Loops: CPSR is not dead\n");
853 // Bail if elemcount is used in exit blocks, i.e. if it is live-in.
854 if (isRegLiveInExitBlocks(LoLoop.ML, ElemCount)) {
855 LLVM_DEBUG(dbgs() << "ARM Loops: Elemcount is live-out, can't remove stmt\n");
859 // Bail if there are uses after this Def in the block.
860 SmallVector<MachineInstr*, 4> Uses;
861 RDA->getReachingLocalUses(Def, ElemCount, Uses);
863 LLVM_DEBUG(dbgs() << "ARM Loops: Local uses in block, can't remove stmt\n");
868 RDA->getAllInstWithUseBefore(Def, ElemCount, Uses);
870 // Remove Def if there are no uses, or if the only use is the VCTP
872 if (!Uses.size() || (Uses.size() == 1 && Uses[0] == LoLoop.VCTP)) {
873 LLVM_DEBUG(dbgs() << "ARM Loops: Removing loop update instruction: ";
875 Def->eraseFromParent();
879 LLVM_DEBUG(dbgs() << "ARM Loops: Can't remove loop update, it's used by:\n";
880 for (auto U : Uses) U->dump());
883 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
884 auto RemovePredicate = [](MachineInstr *MI) {
885 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
886 if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) {
887 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
888 "Expected Then predicate!");
889 MI->getOperand(PIdx).setImm(ARMVCC::None);
890 MI->getOperand(PIdx+1).setReg(0);
892 llvm_unreachable("trying to unpredicate a non-predicated instruction");
895 // There are a few scenarios which we have to fix up:
896 // 1) A VPT block with is only predicated by the vctp and has no internal vpr
898 // 2) A VPT block which is only predicated by the vctp but has an internal
900 // 3) A VPT block which is predicated upon the vctp as well as another vpr
902 // 4) A VPT block which is not predicated upon a vctp, but contains it and
903 // all instructions within the block are predicated upon in.
905 for (auto &Block : LoLoop.getVPTBlocks()) {
906 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
907 if (Block.HasNonUniformPredicate()) {
908 PredicatedMI *Divergent = Block.getDivergent();
909 if (isVCTP(Divergent->MI)) {
910 // The vctp will be removed, so the size of the vpt block needs to be
912 uint64_t Size = getARMVPTBlockMask(Block.size() - 1);
913 Block.getVPST()->getOperand(0).setImm(Size);
914 LLVM_DEBUG(dbgs() << "ARM Loops: Modified VPT block mask.\n");
915 } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
916 // The VPT block has a non-uniform predicate but it's entry is guarded
917 // only by a vctp, which means we:
918 // - Need to remove the original vpst.
919 // - Then need to unpredicate any following instructions, until
920 // we come across the divergent vpr def.
921 // - Insert a new vpst to predicate the instruction(s) that following
922 // the divergent vpr def.
923 // TODO: We could be producing more VPT blocks than necessary and could
924 // fold the newly created one into a proceeding one.
925 for (auto I = ++MachineBasicBlock::iterator(Block.getVPST()),
926 E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I)
927 RemovePredicate(&*I);
930 auto E = MachineBasicBlock::reverse_iterator(Divergent->MI);
931 auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI);
932 MachineInstr *InsertAt = nullptr;
938 MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt,
939 InsertAt->getDebugLoc(),
940 TII->get(ARM::MVE_VPST));
941 MIB.addImm(getARMVPTBlockMask(Size));
942 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST());
943 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
944 Block.getVPST()->eraseFromParent();
946 } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
947 // A vpt block which is only predicated upon vctp and has no internal vpr
950 // - Unpredicate the remaining instructions.
951 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST());
952 Block.getVPST()->eraseFromParent();
953 for (auto &PredMI : Insts)
954 RemovePredicate(PredMI.MI);
958 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *LoLoop.VCTP);
959 LoLoop.VCTP->eraseFromParent();
962 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
964 // Combine the LoopDec and LoopEnd instructions into LE(TP).
965 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
966 MachineInstr *End = LoLoop.End;
967 MachineBasicBlock *MBB = End->getParent();
968 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
969 ARM::MVE_LETP : ARM::t2LEUpdate;
970 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
973 MIB.add(End->getOperand(0));
974 MIB.add(End->getOperand(1));
975 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
977 LoLoop.End->eraseFromParent();
978 LoLoop.Dec->eraseFromParent();
982 // TODO: We should be able to automatically remove these branches before we
983 // get here - probably by teaching analyzeBranch about the pseudo
985 // If there is an unconditional branch, after I, that just branches to the
986 // next block, remove it.
987 auto RemoveDeadBranch = [](MachineInstr *I) {
988 MachineBasicBlock *BB = I->getParent();
989 MachineInstr *Terminator = &BB->instr_back();
990 if (Terminator->isUnconditionalBranch() && I != Terminator) {
991 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
992 if (BB->isLayoutSuccessor(Succ)) {
993 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
994 Terminator->eraseFromParent();
1000 if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
1001 RevertWhile(LoLoop.Start);
1003 LoLoop.Start->eraseFromParent();
1004 bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec, true);
1005 RevertLoopEnd(LoLoop.End, FlagsAlreadySet);
1007 LoLoop.Start = ExpandLoopStart(LoLoop);
1008 RemoveDeadBranch(LoLoop.Start);
1009 LoLoop.End = ExpandLoopEnd(LoLoop);
1010 RemoveDeadBranch(LoLoop.End);
1011 if (LoLoop.IsTailPredicationLegal()) {
1012 RemoveLoopUpdate(LoLoop);
1013 ConvertVPTBlocks(LoLoop);
1018 bool ARMLowOverheadLoops::RevertNonLoops() {
1019 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1020 bool Changed = false;
1022 for (auto &MBB : *MF) {
1023 SmallVector<MachineInstr*, 4> Starts;
1024 SmallVector<MachineInstr*, 4> Decs;
1025 SmallVector<MachineInstr*, 4> Ends;
1027 for (auto &I : MBB) {
1029 Starts.push_back(&I);
1030 else if (I.getOpcode() == ARM::t2LoopDec)
1032 else if (I.getOpcode() == ARM::t2LoopEnd)
1036 if (Starts.empty() && Decs.empty() && Ends.empty())
1041 for (auto *Start : Starts) {
1042 if (Start->getOpcode() == ARM::t2WhileLoopStart)
1045 Start->eraseFromParent();
1047 for (auto *Dec : Decs)
1050 for (auto *End : Ends)
1056 FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1057 return new ARMLowOverheadLoops();