1 //===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 /// Finalize v8.1-m low-overhead loops by converting the associated pseudo
10 /// instructions into machine operations.
11 /// The expectation is that the loop contains three pseudo instructions:
12 /// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
13 /// form should be in the preheader, whereas the while form should be in the
14 /// preheaders only predecessor.
15 /// - t2LoopDec - placed within in the loop body.
16 /// - t2LoopEnd - the loop latch terminator.
18 /// In addition to this, we also look for the presence of the VCTP instruction,
19 /// which determines whether we can generated the tail-predicated low-overhead
22 /// Assumptions and Dependencies:
23 /// Low-overhead loops are constructed and executed using a setup instruction:
24 /// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
25 /// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
26 /// but fixed polarity: WLS can only branch forwards and LE can only branch
27 /// backwards. These restrictions mean that this pass is dependent upon block
28 /// layout and block sizes, which is why it's the last pass to run. The same is
29 /// true for ConstantIslands, but this pass does not increase the size of the
30 /// basic blocks, nor does it change the CFG. Instructions are mainly removed
31 /// during the transform and pseudo instructions are replaced by real ones. In
32 /// some cases, when we have to revert to a 'normal' loop, we have to introduce
33 /// multiple instructions for a single pseudo (see RevertWhile and
34 /// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
35 /// are defined to be as large as this maximum sequence of replacement
38 /// A note on VPR.P0 (the lane mask):
39 /// VPT, VCMP, VPNOT and VCTP won't overwrite VPR.P0 when they update it in a
40 /// "VPT Active" context (which includes low-overhead loops and vpt blocks).
41 /// They will simply "and" the result of their calculation with the current
42 /// value of VPR.P0. You can think of it like this:
44 /// if VPT active: ; Between a DLSTP/LETP, or for predicated instrs
49 /// When we're inside the low-overhead loop (between DLSTP and LETP), we always
50 /// fall in the "VPT active" case, so we can consider that all VPR writes by
51 /// one of those instruction is actually a "and".
52 //===----------------------------------------------------------------------===//
55 #include "ARMBaseInstrInfo.h"
56 #include "ARMBaseRegisterInfo.h"
57 #include "ARMBasicBlockInfo.h"
58 #include "ARMSubtarget.h"
59 #include "Thumb2InstrInfo.h"
60 #include "llvm/ADT/SetOperations.h"
61 #include "llvm/ADT/SmallSet.h"
62 #include "llvm/CodeGen/LivePhysRegs.h"
63 #include "llvm/CodeGen/MachineFunctionPass.h"
64 #include "llvm/CodeGen/MachineLoopInfo.h"
65 #include "llvm/CodeGen/MachineLoopUtils.h"
66 #include "llvm/CodeGen/MachineRegisterInfo.h"
67 #include "llvm/CodeGen/Passes.h"
68 #include "llvm/CodeGen/ReachingDefAnalysis.h"
69 #include "llvm/MC/MCInstrDesc.h"
73 #define DEBUG_TYPE "arm-low-overhead-loops"
74 #define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
78 using InstSet = SmallPtrSetImpl<MachineInstr *>;
80 class PostOrderLoopTraversal {
83 SmallPtrSet<MachineBasicBlock*, 4> Visited;
84 SmallVector<MachineBasicBlock*, 4> Order;
87 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
88 : ML(ML), MLI(MLI) { }
90 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
94 // Visit all the blocks within the loop, as well as exit blocks and any
95 // blocks properly dominating the header.
97 std::function<void(MachineBasicBlock*)> Search = [this, &Search]
98 (MachineBasicBlock *MBB) -> void {
99 if (Visited.count(MBB))
103 for (auto *Succ : MBB->successors()) {
104 if (!ML.contains(Succ))
108 Order.push_back(MBB);
111 // Insert exit blocks.
112 SmallVector<MachineBasicBlock*, 2> ExitBlocks;
113 ML.getExitBlocks(ExitBlocks);
114 for (auto *MBB : ExitBlocks)
115 Order.push_back(MBB);
117 // Then add the loop body.
118 Search(ML.getHeader());
120 // Then try the preheader and its predecessors.
121 std::function<void(MachineBasicBlock*)> GetPredecessor =
122 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
123 Order.push_back(MBB);
124 if (MBB->pred_size() == 1)
125 GetPredecessor(*MBB->pred_begin());
128 if (auto *Preheader = ML.getLoopPreheader())
129 GetPredecessor(Preheader);
130 else if (auto *Preheader = MLI.findLoopPreheader(&ML, true))
131 GetPredecessor(Preheader);
135 struct PredicatedMI {
136 MachineInstr *MI = nullptr;
137 SetVector<MachineInstr*> Predicates;
140 PredicatedMI(MachineInstr *I, SetVector<MachineInstr *> &Preds) : MI(I) {
141 assert(I && "Instruction must not be null!");
142 Predicates.insert(Preds.begin(), Preds.end());
146 // Represent a VPT block, a list of instructions that begins with a VPT/VPST
147 // and has a maximum of four proceeding instructions. All instructions within
148 // the block are predicated upon the vpr and we allow instructions to define
149 // the vpr within in the block too.
151 // The predicate then instruction, which is either a VPT, or a VPST
153 std::unique_ptr<PredicatedMI> PredicateThen;
154 PredicatedMI *Divergent = nullptr;
155 SmallVector<PredicatedMI, 4> Insts;
158 VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
159 PredicateThen = std::make_unique<PredicatedMI>(MI, Preds);
162 void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
163 LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI);
164 if (!Divergent && !set_difference(Preds, PredicateThen->Predicates).empty()) {
165 Divergent = &Insts.back();
166 LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI);
168 Insts.emplace_back(MI, Preds);
169 assert(Insts.size() <= 4 && "Too many instructions in VPT block!");
172 // Have we found an instruction within the block which defines the vpr? If
173 // so, not all the instructions in the block will have the same predicate.
174 bool HasNonUniformPredicate() const {
175 return Divergent != nullptr;
178 // Is the given instruction part of the predicate set controlling the entry
180 bool IsPredicatedOn(MachineInstr *MI) const {
181 return PredicateThen->Predicates.count(MI);
184 // Returns true if this is a VPT instruction.
185 bool isVPT() const { return !isVPST(); }
187 // Returns true if this is a VPST instruction.
188 bool isVPST() const {
189 return PredicateThen->MI->getOpcode() == ARM::MVE_VPST;
192 // Is the given instruction the only predicate which controls the entry to
194 bool IsOnlyPredicatedOn(MachineInstr *MI) const {
195 return IsPredicatedOn(MI) && PredicateThen->Predicates.size() == 1;
198 unsigned size() const { return Insts.size(); }
199 SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; }
200 MachineInstr *getPredicateThen() const { return PredicateThen->MI; }
201 PredicatedMI *getDivergent() const { return Divergent; }
207 MachineInstr &Reduce;
210 Reduction(MachineInstr *Init, MachineInstr *Mov, MachineInstr *Add,
212 : Init(Init), Copy(*Mov), Reduce(*Add), VPSEL(*Sel) { }
215 struct LowOverheadLoop {
218 MachineBasicBlock *Preheader = nullptr;
219 MachineLoopInfo &MLI;
220 ReachingDefAnalysis &RDA;
221 const TargetRegisterInfo &TRI;
222 const ARMBaseInstrInfo &TII;
223 MachineFunction *MF = nullptr;
224 MachineInstr *InsertPt = nullptr;
225 MachineInstr *Start = nullptr;
226 MachineInstr *Dec = nullptr;
227 MachineInstr *End = nullptr;
228 MachineInstr *VCTP = nullptr;
229 SmallPtrSet<MachineInstr*, 4> SecondaryVCTPs;
230 VPTBlock *CurrentBlock = nullptr;
231 SetVector<MachineInstr*> CurrentPredicate;
232 SmallVector<VPTBlock, 4> VPTBlocks;
233 SmallPtrSet<MachineInstr*, 4> ToRemove;
234 SmallVector<std::unique_ptr<Reduction>, 1> Reductions;
235 SmallPtrSet<MachineInstr*, 4> BlockMasksToRecompute;
237 bool CannotTailPredicate = false;
239 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI,
240 ReachingDefAnalysis &RDA, const TargetRegisterInfo &TRI,
241 const ARMBaseInstrInfo &TII)
242 : ML(ML), MLI(MLI), RDA(RDA), TRI(TRI), TII(TII) {
243 MF = ML.getHeader()->getParent();
244 if (auto *MBB = ML.getLoopPreheader())
246 else if (auto *MBB = MLI.findLoopPreheader(&ML, true))
250 // If this is an MVE instruction, check that we know how to use tail
251 // predication with it. Record VPT blocks and return whether the
252 // instruction is valid for tail predication.
253 bool ValidateMVEInst(MachineInstr *MI);
255 void AnalyseMVEInst(MachineInstr *MI) {
256 CannotTailPredicate = !ValidateMVEInst(MI);
259 bool IsTailPredicationLegal() const {
260 // For now, let's keep things really simple and only support a single
261 // block for tail predication.
262 return !Revert && FoundAllComponents() && VCTP &&
263 !CannotTailPredicate && ML.getNumBlocks() == 1;
266 // Check that the predication in the loop will be equivalent once we
267 // perform the conversion. Also ensure that we can provide the number
268 // of elements to the loop start instruction.
269 bool ValidateTailPredicate(MachineInstr *StartInsertPt);
271 // See whether the live-out instructions are a reduction that we can fixup
273 bool FindValidReduction(InstSet &LiveMIs, InstSet &LiveOutUsers);
275 // Check that any values available outside of the loop will be the same
276 // after tail predication conversion.
277 bool ValidateLiveOuts();
279 // Is it safe to define LR with DLS/WLS?
280 // LR can be defined if it is the operand to start, because it's the same
281 // value, or if it's going to be equivalent to the operand to Start.
282 MachineInstr *isSafeToDefineLR();
284 // Check the branch targets are within range and we satisfy our
286 void CheckLegality(ARMBasicBlockUtils *BBUtils);
288 bool FoundAllComponents() const {
289 return Start && Dec && End;
292 SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; }
294 // Return the loop iteration count, or the number of elements if we're tail
296 MachineOperand &getCount() {
297 return IsTailPredicationLegal() ?
298 VCTP->getOperand(1) : Start->getOperand(0);
301 unsigned getStartOpcode() const {
302 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
303 if (!IsTailPredicationLegal())
304 return IsDo ? ARM::t2DLS : ARM::t2WLS;
306 return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo);
310 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
311 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
312 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
313 if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP;
314 if (!FoundAllComponents())
315 dbgs() << "ARM Loops: Not a low-overhead loop.\n";
316 else if (!(Start && Dec && End))
317 dbgs() << "ARM Loops: Failed to find all loop components.\n";
321 class ARMLowOverheadLoops : public MachineFunctionPass {
322 MachineFunction *MF = nullptr;
323 MachineLoopInfo *MLI = nullptr;
324 ReachingDefAnalysis *RDA = nullptr;
325 const ARMBaseInstrInfo *TII = nullptr;
326 MachineRegisterInfo *MRI = nullptr;
327 const TargetRegisterInfo *TRI = nullptr;
328 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
333 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
335 void getAnalysisUsage(AnalysisUsage &AU) const override {
336 AU.setPreservesCFG();
337 AU.addRequired<MachineLoopInfo>();
338 AU.addRequired<ReachingDefAnalysis>();
339 MachineFunctionPass::getAnalysisUsage(AU);
342 bool runOnMachineFunction(MachineFunction &MF) override;
344 MachineFunctionProperties getRequiredProperties() const override {
345 return MachineFunctionProperties().set(
346 MachineFunctionProperties::Property::NoVRegs).set(
347 MachineFunctionProperties::Property::TracksLiveness);
350 StringRef getPassName() const override {
351 return ARM_LOW_OVERHEAD_LOOPS_NAME;
355 bool ProcessLoop(MachineLoop *ML);
357 bool RevertNonLoops();
359 void RevertWhile(MachineInstr *MI) const;
361 bool RevertLoopDec(MachineInstr *MI) const;
363 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
365 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
367 void FixupReductions(LowOverheadLoop &LoLoop) const;
369 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
371 void Expand(LowOverheadLoop &LoLoop);
373 void IterationCountDCE(LowOverheadLoop &LoLoop);
377 char ARMLowOverheadLoops::ID = 0;
379 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
382 MachineInstr *LowOverheadLoop::isSafeToDefineLR() {
383 // We can define LR because LR already contains the same value.
384 if (Start->getOperand(0).getReg() == ARM::LR)
387 unsigned CountReg = Start->getOperand(0).getReg();
388 auto IsMoveLR = [&CountReg](MachineInstr *MI) {
389 return MI->getOpcode() == ARM::tMOVr &&
390 MI->getOperand(0).getReg() == ARM::LR &&
391 MI->getOperand(1).getReg() == CountReg &&
392 MI->getOperand(2).getImm() == ARMCC::AL;
395 MachineBasicBlock *MBB = Start->getParent();
397 // Find an insertion point:
398 // - Is there a (mov lr, Count) before Start? If so, and nothing else writes
399 // to Count before Start, we can insert at that mov.
400 if (auto *LRDef = RDA.getUniqueReachingMIDef(Start, ARM::LR))
401 if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg))
404 // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
405 // to Count after Start, we can insert at that mov.
406 if (auto *LRDef = RDA.getLocalLiveOutMIDef(MBB, ARM::LR))
407 if (IsMoveLR(LRDef) && RDA.hasSameReachingDef(Start, LRDef, CountReg))
410 // We've found no suitable LR def and Start doesn't use LR directly. Can we
411 // just define LR anyway?
412 return RDA.isSafeToDefRegAt(Start, ARM::LR) ? Start : nullptr;
415 bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt) {
416 assert(VCTP && "VCTP instruction expected but is not set");
417 // All predication within the loop should be based on vctp. If the block
418 // isn't predicated on entry, check whether the vctp is within the block
419 // and that all other instructions are then predicated on it.
420 for (auto &Block : VPTBlocks) {
421 if (Block.IsPredicatedOn(VCTP))
423 if (Block.HasNonUniformPredicate() && !isVCTP(Block.getDivergent()->MI)) {
424 LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: "
425 << *Block.getDivergent()->MI);
428 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
429 for (auto &PredMI : Insts) {
430 // Check the instructions in the block and only allow:
432 // - Instructions predicated on the main VCTP
434 // - VCMPs just "and" their result with VPR.P0. Whether they are
435 // located before/after the VCTP is irrelevant - the end result will
436 // be the same in both cases, so there's no point in requiring them
437 // to be located after the VCTP!
438 if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI) ||
439 VCMPOpcodeToVPT(PredMI.MI->getOpcode()) != 0)
441 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MI
442 << " - which is predicated on:\n";
443 for (auto *MI : PredMI.Predicates)
444 dbgs() << " - " << *MI);
449 if (!ValidateLiveOuts())
452 // For tail predication, we need to provide the number of elements, instead
453 // of the iteration count, to the loop start instruction. The number of
454 // elements is provided to the vctp instruction, so we need to check that
455 // we can use this register at InsertPt.
456 Register NumElements = VCTP->getOperand(1).getReg();
458 // If the register is defined within loop, then we can't perform TP.
459 // TODO: Check whether this is just a mov of a register that would be
461 if (RDA.hasLocalDefBefore(VCTP, NumElements)) {
462 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
466 // The element count register maybe defined after InsertPt, in which case we
467 // need to try to move either InsertPt or the def so that the [w|d]lstp can
469 // TODO: On failing to move an instruction, check if the count is provided by
470 // a mov and whether we can use the mov operand directly.
471 MachineBasicBlock *InsertBB = StartInsertPt->getParent();
472 if (!RDA.isReachingDefLiveOut(StartInsertPt, NumElements)) {
473 if (auto *ElemDef = RDA.getLocalLiveOutMIDef(InsertBB, NumElements)) {
474 if (RDA.isSafeToMoveForwards(ElemDef, StartInsertPt)) {
475 ElemDef->removeFromParent();
476 InsertBB->insert(MachineBasicBlock::iterator(StartInsertPt), ElemDef);
477 LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: "
479 } else if (RDA.isSafeToMoveBackwards(StartInsertPt, ElemDef)) {
480 StartInsertPt->removeFromParent();
481 InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef),
483 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
485 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to move element count to loop "
486 << "start instruction.\n");
492 // Especially in the case of while loops, InsertBB may not be the
493 // preheader, so we need to check that the register isn't redefined
494 // before entering the loop.
495 auto CannotProvideElements = [this](MachineBasicBlock *MBB,
496 Register NumElements) {
497 // NumElements is redefined in this block.
498 if (RDA.hasLocalDefBefore(&MBB->back(), NumElements))
501 // Don't continue searching up through multiple predecessors.
502 if (MBB->pred_size() > 1)
508 // First, find the block that looks like the preheader.
509 MachineBasicBlock *MBB = Preheader;
511 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n");
515 // Then search backwards for a def, until we get to InsertBB.
516 while (MBB != InsertBB) {
517 if (CannotProvideElements(MBB, NumElements)) {
518 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
521 MBB = *MBB->pred_begin();
524 // Check that the value change of the element count is what we expect and
525 // that the predication will be equivalent. For this we need:
526 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
527 // and we can also allow register copies within the chain too.
528 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
529 return -getAddSubImmediate(*MI) == ExpectedVecWidth;
532 MBB = VCTP->getParent();
533 if (auto *Def = RDA.getUniqueReachingMIDef(&MBB->back(), NumElements)) {
534 SmallPtrSet<MachineInstr*, 2> ElementChain;
535 SmallPtrSet<MachineInstr*, 2> Ignore = { VCTP };
536 unsigned ExpectedVectorWidth = getTailPredVectorWidth(VCTP->getOpcode());
538 Ignore.insert(SecondaryVCTPs.begin(), SecondaryVCTPs.end());
540 if (RDA.isSafeToRemove(Def, ElementChain, Ignore)) {
541 bool FoundSub = false;
543 for (auto *MI : ElementChain) {
544 if (isMovRegOpcode(MI->getOpcode()))
547 if (isSubImmOpcode(MI->getOpcode())) {
548 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth))
555 LLVM_DEBUG(dbgs() << "ARM Loops: Will remove element count chain:\n";
556 for (auto *MI : ElementChain)
557 dbgs() << " - " << *MI);
558 ToRemove.insert(ElementChain.begin(), ElementChain.end());
564 static bool isVectorPredicated(MachineInstr *MI) {
565 int PIdx = llvm::findFirstVPTPredOperandIdx(*MI);
566 return PIdx != -1 && MI->getOperand(PIdx + 1).getReg() == ARM::VPR;
569 static bool isRegInClass(const MachineOperand &MO,
570 const TargetRegisterClass *Class) {
571 return MO.isReg() && MO.getReg() && Class->contains(MO.getReg());
574 // MVE 'narrowing' operate on half a lane, reading from half and writing
575 // to half, which are referred to has the top and bottom half. The other
576 // half retains its previous value.
577 static bool retainsPreviousHalfElement(const MachineInstr &MI) {
578 const MCInstrDesc &MCID = MI.getDesc();
579 uint64_t Flags = MCID.TSFlags;
580 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
583 // Some MVE instructions read from the top/bottom halves of their operand(s)
584 // and generate a vector result with result elements that are double the
585 // width of the input.
586 static bool producesDoubleWidthResult(const MachineInstr &MI) {
587 const MCInstrDesc &MCID = MI.getDesc();
588 uint64_t Flags = MCID.TSFlags;
589 return (Flags & ARMII::DoubleWidthResult) != 0;
592 static bool isHorizontalReduction(const MachineInstr &MI) {
593 const MCInstrDesc &MCID = MI.getDesc();
594 uint64_t Flags = MCID.TSFlags;
595 return (Flags & ARMII::HorizontalReduction) != 0;
598 // Can this instruction generate a non-zero result when given only zeroed
599 // operands? This allows us to know that, given operands with false bytes
600 // zeroed by masked loads, that the result will also contain zeros in those
602 static bool canGenerateNonZeros(const MachineInstr &MI) {
604 // Check for instructions which can write into a larger element size,
605 // possibly writing into a previous zero'd lane.
606 if (producesDoubleWidthResult(MI))
609 switch (MI.getOpcode()) {
612 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
613 // fp16 -> fp32 vector conversions.
614 // Instructions that perform a NOT will generate 1s from 0s.
617 // Count leading zeros will do just that!
618 case ARM::MVE_VCLZs8:
619 case ARM::MVE_VCLZs16:
620 case ARM::MVE_VCLZs32:
627 // Look at its register uses to see if it only can only receive zeros
628 // into its false lanes which would then produce zeros. Also check that
629 // the output register is also defined by an FalseLanesZero instruction
630 // so that if tail-predication happens, the lanes that aren't updated will
632 static bool producesFalseLanesZero(MachineInstr &MI,
633 const TargetRegisterClass *QPRs,
634 const ReachingDefAnalysis &RDA,
635 InstSet &FalseLanesZero) {
636 if (canGenerateNonZeros(MI))
639 bool AllowScalars = isHorizontalReduction(MI);
640 for (auto &MO : MI.operands()) {
641 if (!MO.isReg() || !MO.getReg())
643 if (!isRegInClass(MO, QPRs) && AllowScalars)
645 if (auto *OpDef = RDA.getMIOperand(&MI, MO))
646 if (FalseLanesZero.count(OpDef))
650 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
655 LowOverheadLoop::FindValidReduction(InstSet &LiveMIs, InstSet &LiveOutUsers) {
656 // Also check for reductions where the operation needs to be merging values
657 // from the last and previous loop iterations. This means an instruction
658 // producing a value and a vmov storing the value calculated in the previous
659 // iteration. So we can have two live-out regs, one produced by a vmov and
660 // both being consumed by a vpsel.
661 LLVM_DEBUG(dbgs() << "ARM Loops: Looking for reduction live-outs:\n";
662 for (auto *MI : LiveMIs)
663 dbgs() << " - " << *MI);
668 // Expect a vmov, a vadd and a single vpsel user.
669 // TODO: This means we can't currently support multiple reductions in the
671 if (LiveMIs.size() != 2 || LiveOutUsers.size() != 1)
674 MachineInstr *VPSEL = *LiveOutUsers.begin();
675 if (VPSEL->getOpcode() != ARM::MVE_VPSEL)
678 unsigned VPRIdx = llvm::findFirstVPTPredOperandIdx(*VPSEL) + 1;
679 MachineInstr *Pred = RDA.getMIOperand(VPSEL, VPRIdx);
680 if (!Pred || Pred != VCTP) {
681 LLVM_DEBUG(dbgs() << "ARM Loops: Not using equivalent predicate.\n");
685 MachineInstr *Reduce = RDA.getMIOperand(VPSEL, 1);
689 assert(LiveMIs.count(Reduce) && "Expected MI to be live-out");
691 // TODO: Support more operations than VADD.
692 switch (VCTP->getOpcode()) {
696 if (Reduce->getOpcode() != ARM::MVE_VADDi8)
699 case ARM::MVE_VCTP16:
700 if (Reduce->getOpcode() != ARM::MVE_VADDi16)
703 case ARM::MVE_VCTP32:
704 if (Reduce->getOpcode() != ARM::MVE_VADDi32)
709 // Test that the reduce op is overwriting ones of its operands.
710 if (Reduce->getOperand(0).getReg() != Reduce->getOperand(1).getReg() &&
711 Reduce->getOperand(0).getReg() != Reduce->getOperand(2).getReg()) {
712 LLVM_DEBUG(dbgs() << "ARM Loops: Reducing op isn't overwriting itself.\n");
716 // Check that the VORR is actually a VMOV.
717 MachineInstr *Copy = RDA.getMIOperand(VPSEL, 2);
718 if (!Copy || Copy->getOpcode() != ARM::MVE_VORR ||
719 !Copy->getOperand(1).isReg() || !Copy->getOperand(2).isReg() ||
720 Copy->getOperand(1).getReg() != Copy->getOperand(2).getReg())
723 assert(LiveMIs.count(Copy) && "Expected MI to be live-out");
725 // Check that the vadd and vmov are only used by each other and the vpsel.
726 SmallPtrSet<MachineInstr*, 2> CopyUsers;
727 RDA.getGlobalUses(Copy, Copy->getOperand(0).getReg(), CopyUsers);
728 if (CopyUsers.size() > 2 || !CopyUsers.count(Reduce)) {
729 LLVM_DEBUG(dbgs() << "ARM Loops: Copy users unsupported.\n");
733 SmallPtrSet<MachineInstr*, 2> ReduceUsers;
734 RDA.getGlobalUses(Reduce, Reduce->getOperand(0).getReg(), ReduceUsers);
735 if (ReduceUsers.size() > 2 || !ReduceUsers.count(Copy)) {
736 LLVM_DEBUG(dbgs() << "ARM Loops: Reduce users unsupported.\n");
740 // Then find whether there's an instruction initialising the register that
741 // is storing the reduction.
742 SmallPtrSet<MachineInstr*, 2> Incoming;
743 RDA.getLiveOuts(Preheader, Copy->getOperand(1).getReg(), Incoming);
744 if (Incoming.size() > 1)
747 MachineInstr *Init = Incoming.empty() ? nullptr : *Incoming.begin();
748 LLVM_DEBUG(dbgs() << "ARM Loops: Found a reduction:\n"
752 Reductions.push_back(std::make_unique<Reduction>(Init, Copy, Reduce, VPSEL));
756 bool LowOverheadLoop::ValidateLiveOuts() {
757 // We want to find out if the tail-predicated version of this loop will
758 // produce the same values as the loop in its original form. For this to
759 // be true, the newly inserted implicit predication must not change the
760 // the (observable) results.
761 // We're doing this because many instructions in the loop will not be
762 // predicated and so the conversion from VPT predication to tail-predication
763 // can result in different values being produced; due to the tail-predication
764 // preventing many instructions from updating their falsely predicated
765 // lanes. This analysis assumes that all the instructions perform lane-wise
766 // operations and don't perform any exchanges.
767 // A masked load, whether through VPT or tail predication, will write zeros
768 // to any of the falsely predicated bytes. So, from the loads, we know that
769 // the false lanes are zeroed and here we're trying to track that those false
770 // lanes remain zero, or where they change, the differences are masked away
772 // All MVE loads and stores have to be predicated, so we know that any load
773 // operands, or stored results are equivalent already. Other explicitly
774 // predicated instructions will perform the same operation in the original
775 // loop and the tail-predicated form too. Because of this, we can insert
776 // loads, stores and other predicated instructions into our Predicated
777 // set and build from there.
778 const TargetRegisterClass *QPRs = TRI.getRegClass(ARM::MQPRRegClassID);
779 SetVector<MachineInstr *> FalseLanesUnknown;
780 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
781 SmallPtrSet<MachineInstr *, 4> Predicated;
782 MachineBasicBlock *Header = ML.getHeader();
784 for (auto &MI : *Header) {
785 const MCInstrDesc &MCID = MI.getDesc();
786 uint64_t Flags = MCID.TSFlags;
787 if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
790 if (isVCTP(&MI) || isVPTOpcode(MI.getOpcode()))
793 // Predicated loads will write zeros to the falsely predicated bytes of the
794 // destination register.
795 if (isVectorPredicated(&MI)) {
797 FalseLanesZero.insert(&MI);
798 Predicated.insert(&MI);
802 if (MI.getNumDefs() == 0)
805 if (!producesFalseLanesZero(MI, QPRs, RDA, FalseLanesZero)) {
806 // We require retaining and horizontal operations to operate upon zero'd
807 // false lanes to ensure the conversion doesn't change the output.
808 if (retainsPreviousHalfElement(MI) || isHorizontalReduction(MI))
810 // Otherwise we need to evaluate this instruction later to see whether
811 // unknown false lanes will get masked away by their user(s).
812 FalseLanesUnknown.insert(&MI);
813 } else if (!isHorizontalReduction(MI))
814 FalseLanesZero.insert(&MI);
817 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
818 SmallPtrSetImpl<MachineInstr *> &Predicated) {
819 SmallPtrSet<MachineInstr *, 2> Uses;
820 RDA.getGlobalUses(MI, MO.getReg(), Uses);
821 for (auto *Use : Uses) {
822 if (Use != MI && !Predicated.count(Use))
828 // Visit the unknowns in reverse so that we can start at the values being
829 // stored and then we can work towards the leaves, hopefully adding more
830 // instructions to Predicated. Successfully terminating the loop means that
831 // all the unknown values have to found to be masked by predicated user(s).
832 // For any unpredicated values, we store them in NonPredicated so that we
833 // can later check whether these form a reduction.
834 SmallPtrSet<MachineInstr*, 2> NonPredicated;
835 for (auto *MI : reverse(FalseLanesUnknown)) {
836 for (auto &MO : MI->operands()) {
837 if (!isRegInClass(MO, QPRs) || !MO.isDef())
839 if (!HasPredicatedUsers(MI, MO, Predicated)) {
840 LLVM_DEBUG(dbgs() << "ARM Loops: Found an unknown def of : "
841 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
842 NonPredicated.insert(MI);
846 // Any unknown false lanes have been masked away by the user(s).
847 Predicated.insert(MI);
850 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
851 SmallPtrSet<MachineInstr*, 2> LiveOutUsers;
852 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
853 ML.getExitBlocks(ExitBlocks);
854 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
855 assert(ExitBlocks.size() == 1 && "Expected a single exit block");
856 MachineBasicBlock *ExitBB = ExitBlocks.front();
857 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
858 // Check Q-regs that are live in the exit blocks. We don't collect scalars
859 // because they won't be affected by lane predication.
860 if (QPRs->contains(RegMask.PhysReg)) {
861 if (auto *MI = RDA.getLocalLiveOutMIDef(Header, RegMask.PhysReg))
862 LiveOutMIs.insert(MI);
863 RDA.getLiveInUses(ExitBB, RegMask.PhysReg, LiveOutUsers);
867 // If we have any non-predicated live-outs, they need to be part of a
868 // reduction that we can fixup later. The reduction that the form of an
869 // operation that uses its previous values through a vmov and then a vpsel
870 // resides in the exit blocks to select the final bytes from n and n-1
872 if (!NonPredicated.empty() &&
873 !FindValidReduction(NonPredicated, LiveOutUsers))
876 // We've already validated that any VPT predication within the loop will be
877 // equivalent when we perform the predication transformation; so we know that
878 // any VPT predicated instruction is predicated upon VCTP. Any live-out
879 // instruction needs to be predicated, so check this here. The instructions
880 // in NonPredicated have been found to be a reduction that we can ensure its
882 for (auto *MI : LiveOutMIs)
883 if (!isVectorPredicated(MI) && !NonPredicated.count(MI))
889 void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils) {
893 if (!End->getOperand(1).isMBB())
894 report_fatal_error("Expected LoopEnd to target basic block");
896 // TODO Maybe there's cases where the target doesn't have to be the header,
897 // but for now be safe and revert.
898 if (End->getOperand(1).getMBB() != ML.getHeader()) {
899 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n");
904 // The WLS and LE instructions have 12-bits for the label offset. WLS
905 // requires a positive offset, while LE uses negative.
906 if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML.getHeader()) ||
907 !BBUtils->isBBInRange(End, ML.getHeader(), 4094)) {
908 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
913 if (Start->getOpcode() == ARM::t2WhileLoopStart &&
914 (BBUtils->getOffsetOf(Start) >
915 BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
916 !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
917 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
922 InsertPt = Revert ? nullptr : isSafeToDefineLR();
924 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
928 LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
930 if (!IsTailPredicationLegal()) {
931 LLVM_DEBUG(if (!VCTP)
932 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
933 dbgs() << "ARM Loops: Tail-predication is not valid.\n");
937 assert(ML.getBlocks().size() == 1 &&
938 "Shouldn't be processing a loop with more than one block");
939 CannotTailPredicate = !ValidateTailPredicate(InsertPt);
940 LLVM_DEBUG(if (CannotTailPredicate)
941 dbgs() << "ARM Loops: Couldn't validate tail predicate.\n");
944 bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
945 if (CannotTailPredicate)
949 // If we find another VCTP, check whether it uses the same value as the main VCTP.
950 // If it does, store it in the SecondaryVCTPs set, else refuse it.
952 if (!VCTP->getOperand(1).isIdenticalTo(MI->getOperand(1)) ||
953 !RDA.hasSameReachingDef(VCTP, MI, MI->getOperand(1).getReg())) {
954 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
955 "definition from the main VCTP");
958 LLVM_DEBUG(dbgs() << "ARM Loops: Found secondary VCTP: " << *MI);
959 SecondaryVCTPs.insert(MI);
961 LLVM_DEBUG(dbgs() << "ARM Loops: Found 'main' VCTP: " << *MI);
964 } else if (isVPTOpcode(MI->getOpcode())) {
965 if (MI->getOpcode() != ARM::MVE_VPST) {
966 assert(MI->findRegisterDefOperandIdx(ARM::VPR) != -1 &&
967 "VPT does not implicitly define VPR?!");
968 CurrentPredicate.insert(MI);
971 VPTBlocks.emplace_back(MI, CurrentPredicate);
972 CurrentBlock = &VPTBlocks.back();
974 } else if (MI->getOpcode() == ARM::MVE_VPSEL ||
975 MI->getOpcode() == ARM::MVE_VPNOT) {
976 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
977 // 1) It will use the VPR as a predicate operand, but doesn't have to be
978 // instead a VPT block, which means we can assert while building up
979 // the VPT block because we don't find another VPT or VPST to being a new
981 // 2) VPSEL still requires a VPR operand even after tail predicating,
982 // which means we can't remove it unless there is another
983 // instruction, such as vcmp, that can provide the VPR def.
989 const MCInstrDesc &MCID = MI->getDesc();
990 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
991 const MachineOperand &MO = MI->getOperand(i);
992 if (!MO.isReg() || MO.getReg() != ARM::VPR)
996 CurrentPredicate.insert(MI);
998 } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) {
999 CurrentBlock->addInst(MI, CurrentPredicate);
1002 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
1007 // If we find a vpr def that is not already predicated on the vctp, we've
1008 // got disjoint predicates that may not be equivalent when we do the
1010 if (IsDef && !IsUse && VCTP && !isVCTP(MI)) {
1011 LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI);
1015 uint64_t Flags = MCID.TSFlags;
1016 if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
1019 // If we find an instruction that has been marked as not valid for tail
1020 // predication, only allow the instruction if it's contained within a valid
1022 if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) {
1023 LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI);
1027 // If the instruction is already explicitly predicated, then the conversion
1028 // will be fine, but ensure that all memory operations are predicated.
1029 return !IsUse && MI->mayLoadOrStore() ? false : true;
1032 bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
1033 const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
1038 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
1040 MLI = &getAnalysis<MachineLoopInfo>();
1041 RDA = &getAnalysis<ReachingDefAnalysis>();
1042 MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
1043 MRI = &MF->getRegInfo();
1044 TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
1045 TRI = ST.getRegisterInfo();
1046 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
1047 BBUtils->computeAllBlockSizes();
1048 BBUtils->adjustBBOffsetsAfter(&MF->front());
1050 bool Changed = false;
1051 for (auto ML : *MLI) {
1052 if (!ML->getParentLoop())
1053 Changed |= ProcessLoop(ML);
1055 Changed |= RevertNonLoops();
1059 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
1061 bool Changed = false;
1063 // Process inner loops first.
1064 for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
1065 Changed |= ProcessLoop(*I);
1067 LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";
1068 if (auto *Preheader = ML->getLoopPreheader())
1069 dbgs() << " - " << Preheader->getName() << "\n";
1070 else if (auto *Preheader = MLI->findLoopPreheader(ML))
1071 dbgs() << " - " << Preheader->getName() << "\n";
1072 else if (auto *Preheader = MLI->findLoopPreheader(ML, true))
1073 dbgs() << " - " << Preheader->getName() << "\n";
1074 for (auto *MBB : ML->getBlocks())
1075 dbgs() << " - " << MBB->getName() << "\n";
1078 // Search the given block for a loop start instruction. If one isn't found,
1079 // and there's only one predecessor block, search that one too.
1080 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
1081 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
1082 for (auto &MI : *MBB) {
1083 if (isLoopStart(MI))
1086 if (MBB->pred_size() == 1)
1087 return SearchForStart(*MBB->pred_begin());
1091 LowOverheadLoop LoLoop(*ML, *MLI, *RDA, *TRI, *TII);
1092 // Search the preheader for the start intrinsic.
1093 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
1094 // with potentially multiple set.loop.iterations, so we need to enable this.
1095 if (LoLoop.Preheader)
1096 LoLoop.Start = SearchForStart(LoLoop.Preheader);
1100 // Find the low-overhead loop components and decide whether or not to fall
1101 // back to a normal loop. Also look for a vctp instructions and decide
1102 // whether we can convert that predicate using tail predication.
1103 for (auto *MBB : reverse(ML->getBlocks())) {
1104 for (auto &MI : *MBB) {
1105 if (MI.isDebugValue())
1107 else if (MI.getOpcode() == ARM::t2LoopDec)
1109 else if (MI.getOpcode() == ARM::t2LoopEnd)
1111 else if (isLoopStart(MI))
1113 else if (MI.getDesc().isCall()) {
1114 // TODO: Though the call will require LE to execute again, does this
1115 // mean we should revert? Always executing LE hopefully should be
1116 // faster than performing a sub,cmp,br or even subs,br.
1117 LoLoop.Revert = true;
1118 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
1120 // Record VPR defs and build up their corresponding vpt blocks.
1121 // Check we know how to tail predicate any mve instructions.
1122 LoLoop.AnalyseMVEInst(&MI);
1127 LLVM_DEBUG(LoLoop.dump());
1128 if (!LoLoop.FoundAllComponents()) {
1129 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
1133 // Check that the only instruction using LoopDec is LoopEnd.
1134 // TODO: Check for copy chains that really have no effect.
1135 SmallPtrSet<MachineInstr*, 2> Uses;
1136 RDA->getReachingLocalUses(LoLoop.Dec, ARM::LR, Uses);
1137 if (Uses.size() > 1 || !Uses.count(LoLoop.End)) {
1138 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
1139 LoLoop.Revert = true;
1141 LoLoop.CheckLegality(BBUtils.get());
1146 // WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1147 // beq that branches to the exit branch.
1148 // TODO: We could also try to generate a cbz if the value in LR is also in
1149 // another low register.
1150 void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
1151 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
1152 MachineBasicBlock *MBB = MI->getParent();
1153 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
1154 TII->get(ARM::t2CMPri));
1155 MIB.add(MI->getOperand(0));
1157 MIB.addImm(ARMCC::AL);
1158 MIB.addReg(ARM::NoRegister);
1160 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1161 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1162 ARM::tBcc : ARM::t2Bcc;
1164 MIB = BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
1165 MIB.add(MI->getOperand(1)); // branch target
1166 MIB.addImm(ARMCC::EQ); // condition code
1167 MIB.addReg(ARM::CPSR);
1168 MI->eraseFromParent();
1171 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
1172 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
1173 MachineBasicBlock *MBB = MI->getParent();
1174 SmallPtrSet<MachineInstr*, 1> Ignore;
1175 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
1176 if (I->getOpcode() == ARM::t2LoopEnd) {
1182 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
1183 bool SetFlags = RDA->isSafeToDefRegAt(MI, ARM::CPSR, Ignore);
1185 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
1186 TII->get(ARM::t2SUBri));
1187 MIB.addDef(ARM::LR);
1188 MIB.add(MI->getOperand(1));
1189 MIB.add(MI->getOperand(2));
1190 MIB.addImm(ARMCC::AL);
1194 MIB.addReg(ARM::CPSR);
1195 MIB->getOperand(5).setIsDef(true);
1199 MI->eraseFromParent();
1203 // Generate a subs, or sub and cmp, and a branch instead of an LE.
1204 void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
1205 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
1207 MachineBasicBlock *MBB = MI->getParent();
1210 MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
1211 TII->get(ARM::t2CMPri));
1212 MIB.addReg(ARM::LR);
1214 MIB.addImm(ARMCC::AL);
1215 MIB.addReg(ARM::NoRegister);
1218 MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
1219 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
1220 ARM::tBcc : ARM::t2Bcc;
1223 MachineInstrBuilder MIB =
1224 BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(BrOpc));
1225 MIB.add(MI->getOperand(1)); // branch target
1226 MIB.addImm(ARMCC::NE); // condition code
1227 MIB.addReg(ARM::CPSR);
1228 MI->eraseFromParent();
1231 // Perform dead code elimation on the loop iteration count setup expression.
1232 // If we are tail-predicating, the number of elements to be processed is the
1233 // operand of the VCTP instruction in the vector body, see getCount(), which is
1234 // register $r3 in this example:
1236 // $lr = big-itercount-expression
1238 // t2DoLoopStart renamable $lr
1241 // $vpr = MVE_VCTP32 renamable $r3
1242 // renamable $lr = t2LoopDec killed renamable $lr, 1
1243 // t2LoopEnd renamable $lr, %vector.body
1246 // What we would like achieve here is to replace the do-loop start pseudo
1247 // instruction t2DoLoopStart with:
1249 // $lr = MVE_DLSTP_32 killed renamable $r3
1251 // Thus, $r3 which defines the number of elements, is written to $lr,
1252 // and then we want to delete the whole chain that used to define $lr,
1253 // see the comment below how this chain could look like.
1255 void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
1256 if (!LoLoop.IsTailPredicationLegal())
1259 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
1261 MachineInstr *Def = RDA->getMIOperand(LoLoop.Start, 0);
1263 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
1267 // Collect and remove the users of iteration count.
1268 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,
1269 LoLoop.End, LoLoop.InsertPt };
1270 SmallPtrSet<MachineInstr*, 2> Remove;
1271 if (RDA->isSafeToRemove(Def, Remove, Killed))
1272 LoLoop.ToRemove.insert(Remove.begin(), Remove.end());
1274 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
1278 // Collect the dead code and the MBBs in which they reside.
1279 RDA->collectKilledOperands(Def, Killed);
1280 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
1281 for (auto *MI : Killed)
1282 BasicBlocks.insert(MI->getParent());
1284 // Collect IT blocks in all affected basic blocks.
1285 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
1286 for (auto *MBB : BasicBlocks) {
1287 for (auto &MI : *MBB) {
1288 if (MI.getOpcode() != ARM::t2IT)
1290 RDA->getReachingLocalUses(&MI, ARM::ITSTATE, ITBlocks[&MI]);
1294 // If we're removing all of the instructions within an IT block, then
1295 // also remove the IT instruction.
1296 SmallPtrSet<MachineInstr*, 2> ModifiedITs;
1297 for (auto *MI : Killed) {
1298 if (MachineOperand *MO = MI->findRegisterUseOperand(ARM::ITSTATE)) {
1299 MachineInstr *IT = RDA->getMIOperand(MI, *MO);
1300 auto &CurrentBlock = ITBlocks[IT];
1301 CurrentBlock.erase(MI);
1302 if (CurrentBlock.empty())
1303 ModifiedITs.erase(IT);
1305 ModifiedITs.insert(IT);
1309 // Delete the killed instructions only if we don't have any IT blocks that
1310 // need to be modified because we need to fixup the mask.
1311 // TODO: Handle cases where IT blocks are modified.
1312 if (ModifiedITs.empty()) {
1313 LLVM_DEBUG(dbgs() << "ARM Loops: Will remove iteration count:\n";
1314 for (auto *MI : Killed)
1315 dbgs() << " - " << *MI);
1316 LoLoop.ToRemove.insert(Killed.begin(), Killed.end());
1318 LLVM_DEBUG(dbgs() << "ARM Loops: Would need to modify IT block(s).\n");
1321 MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
1322 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
1323 // When using tail-predication, try to delete the dead code that was used to
1324 // calculate the number of loop iterations.
1325 IterationCountDCE(LoLoop);
1327 MachineInstr *InsertPt = LoLoop.InsertPt;
1328 MachineInstr *Start = LoLoop.Start;
1329 MachineBasicBlock *MBB = InsertPt->getParent();
1330 bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
1331 unsigned Opc = LoLoop.getStartOpcode();
1332 MachineOperand &Count = LoLoop.getCount();
1334 MachineInstrBuilder MIB =
1335 BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));
1337 MIB.addDef(ARM::LR);
1340 MIB.add(Start->getOperand(1));
1342 // If we're inserting at a mov lr, then remove it as it's redundant.
1343 if (InsertPt != Start)
1344 LoLoop.ToRemove.insert(InsertPt);
1345 LoLoop.ToRemove.insert(Start);
1346 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
1350 void ARMLowOverheadLoops::FixupReductions(LowOverheadLoop &LoLoop) const {
1351 LLVM_DEBUG(dbgs() << "ARM Loops: Fixing up reduction(s).\n");
1352 auto BuildMov = [this](MachineInstr &InsertPt, Register To, Register From) {
1353 MachineBasicBlock *MBB = InsertPt.getParent();
1354 MachineInstrBuilder MIB =
1355 BuildMI(*MBB, &InsertPt, InsertPt.getDebugLoc(), TII->get(ARM::MVE_VORR));
1362 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted VMOV: " << *MIB);
1365 for (auto &Reduction : LoLoop.Reductions) {
1366 MachineInstr &Copy = Reduction->Copy;
1367 MachineInstr &Reduce = Reduction->Reduce;
1368 Register DestReg = Copy.getOperand(0).getReg();
1370 // Change the initialiser if present
1371 if (Reduction->Init) {
1372 MachineInstr *Init = Reduction->Init;
1374 for (unsigned i = 0; i < Init->getNumOperands(); ++i) {
1375 MachineOperand &MO = Init->getOperand(i);
1376 if (MO.isReg() && MO.isUse() && MO.isTied() &&
1377 Init->findTiedOperandIdx(i) == 0)
1378 Init->getOperand(i).setReg(DestReg);
1380 Init->getOperand(0).setReg(DestReg);
1381 LLVM_DEBUG(dbgs() << "ARM Loops: Changed init regs: " << *Init);
1383 BuildMov(LoLoop.Preheader->instr_back(), DestReg, Copy.getOperand(1).getReg());
1385 // Change the reducing op to write to the register that is used to copy
1386 // its value on the next iteration. Also update the tied-def operand.
1387 Reduce.getOperand(0).setReg(DestReg);
1388 Reduce.getOperand(5).setReg(DestReg);
1389 LLVM_DEBUG(dbgs() << "ARM Loops: Changed reduction regs: " << Reduce);
1391 // Instead of a vpsel, just copy the register into the necessary one.
1392 MachineInstr &VPSEL = Reduction->VPSEL;
1393 if (VPSEL.getOperand(0).getReg() != DestReg)
1394 BuildMov(VPSEL, VPSEL.getOperand(0).getReg(), DestReg);
1396 // Remove the unnecessary instructions.
1397 LLVM_DEBUG(dbgs() << "ARM Loops: Removing:\n"
1399 << " - " << VPSEL << "\n");
1400 Copy.eraseFromParent();
1401 VPSEL.eraseFromParent();
1405 void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
1406 auto RemovePredicate = [](MachineInstr *MI) {
1407 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
1408 if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) {
1409 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
1410 "Expected Then predicate!");
1411 MI->getOperand(PIdx).setImm(ARMVCC::None);
1412 MI->getOperand(PIdx+1).setReg(0);
1414 llvm_unreachable("trying to unpredicate a non-predicated instruction");
1417 // There are a few scenarios which we have to fix up:
1418 // 1. VPT Blocks with non-uniform predicates:
1419 // - a. When the divergent instruction is a vctp
1420 // - b. When the block uses a vpst, and is only predicated on the vctp
1421 // - c. When the block uses a vpt and (optionally) contains one or more
1423 // 2. VPT Blocks with uniform predicates:
1424 // - a. The block uses a vpst, and is only predicated on the vctp
1425 for (auto &Block : LoLoop.getVPTBlocks()) {
1426 SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
1427 if (Block.HasNonUniformPredicate()) {
1428 PredicatedMI *Divergent = Block.getDivergent();
1429 if (isVCTP(Divergent->MI)) {
1430 // The vctp will be removed, so the block mask of the vp(s)t will need
1431 // to be recomputed.
1432 LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen());
1433 } else if (Block.isVPST() && Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
1434 // The VPT block has a non-uniform predicate but it uses a vpst and its
1435 // entry is guarded only by a vctp, which means we:
1436 // - Need to remove the original vpst.
1437 // - Then need to unpredicate any following instructions, until
1438 // we come across the divergent vpr def.
1439 // - Insert a new vpst to predicate the instruction(s) that following
1440 // the divergent vpr def.
1441 // TODO: We could be producing more VPT blocks than necessary and could
1442 // fold the newly created one into a proceeding one.
1443 for (auto I = ++MachineBasicBlock::iterator(Block.getPredicateThen()),
1444 E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I)
1445 RemovePredicate(&*I);
1448 auto E = MachineBasicBlock::reverse_iterator(Divergent->MI);
1449 auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI);
1450 MachineInstr *InsertAt = nullptr;
1456 // Create a VPST (with a null mask for now, we'll recompute it later).
1457 MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt,
1458 InsertAt->getDebugLoc(),
1459 TII->get(ARM::MVE_VPST));
1461 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen());
1462 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
1463 LoLoop.ToRemove.insert(Block.getPredicateThen());
1464 LoLoop.BlockMasksToRecompute.insert(MIB.getInstr());
1466 // Else, if the block uses a vpt, iterate over the block, removing the
1467 // extra VCTPs it may contain.
1468 else if (Block.isVPT()) {
1469 bool RemovedVCTP = false;
1470 for (PredicatedMI &Elt : Block.getInsts()) {
1471 MachineInstr *MI = Elt.MI;
1473 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *MI);
1474 LoLoop.ToRemove.insert(MI);
1480 LoLoop.BlockMasksToRecompute.insert(Block.getPredicateThen());
1482 } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP) && Block.isVPST()) {
1483 // A vpt block starting with VPST, is only predicated upon vctp and has no
1484 // internal vpr defs:
1486 // - Unpredicate the remaining instructions.
1487 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getPredicateThen());
1488 LoLoop.ToRemove.insert(Block.getPredicateThen());
1489 for (auto &PredMI : Insts)
1490 RemovePredicate(PredMI.MI);
1493 LLVM_DEBUG(dbgs() << "ARM Loops: Removing remaining VCTPs...\n");
1494 // Remove the "main" VCTP
1495 LoLoop.ToRemove.insert(LoLoop.VCTP);
1496 LLVM_DEBUG(dbgs() << " " << *LoLoop.VCTP);
1497 // Remove remaining secondary VCTPs
1498 for (MachineInstr *VCTP : LoLoop.SecondaryVCTPs) {
1499 // All VCTPs that aren't marked for removal yet should be unpredicated ones.
1500 // The predicated ones should have already been marked for removal when
1501 // visiting the VPT blocks.
1502 if (LoLoop.ToRemove.insert(VCTP).second) {
1503 assert(getVPTInstrPredicate(*VCTP) == ARMVCC::None &&
1504 "Removing Predicated VCTP without updating the block mask!");
1505 LLVM_DEBUG(dbgs() << " " << *VCTP);
1510 void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
1512 // Combine the LoopDec and LoopEnd instructions into LE(TP).
1513 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
1514 MachineInstr *End = LoLoop.End;
1515 MachineBasicBlock *MBB = End->getParent();
1516 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
1517 ARM::MVE_LETP : ARM::t2LEUpdate;
1518 MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
1520 MIB.addDef(ARM::LR);
1521 MIB.add(End->getOperand(0));
1522 MIB.add(End->getOperand(1));
1523 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
1524 LoLoop.ToRemove.insert(LoLoop.Dec);
1525 LoLoop.ToRemove.insert(End);
1529 // TODO: We should be able to automatically remove these branches before we
1530 // get here - probably by teaching analyzeBranch about the pseudo
1532 // If there is an unconditional branch, after I, that just branches to the
1533 // next block, remove it.
1534 auto RemoveDeadBranch = [](MachineInstr *I) {
1535 MachineBasicBlock *BB = I->getParent();
1536 MachineInstr *Terminator = &BB->instr_back();
1537 if (Terminator->isUnconditionalBranch() && I != Terminator) {
1538 MachineBasicBlock *Succ = Terminator->getOperand(0).getMBB();
1539 if (BB->isLayoutSuccessor(Succ)) {
1540 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
1541 Terminator->eraseFromParent();
1546 if (LoLoop.Revert) {
1547 if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
1548 RevertWhile(LoLoop.Start);
1550 LoLoop.Start->eraseFromParent();
1551 bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec);
1552 RevertLoopEnd(LoLoop.End, FlagsAlreadySet);
1554 LoLoop.Start = ExpandLoopStart(LoLoop);
1555 RemoveDeadBranch(LoLoop.Start);
1556 LoLoop.End = ExpandLoopEnd(LoLoop);
1557 RemoveDeadBranch(LoLoop.End);
1558 if (LoLoop.IsTailPredicationLegal()) {
1559 ConvertVPTBlocks(LoLoop);
1560 FixupReductions(LoLoop);
1562 for (auto *I : LoLoop.ToRemove) {
1563 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
1564 I->eraseFromParent();
1566 for (auto *I : LoLoop.BlockMasksToRecompute) {
1567 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
1568 recomputeVPTBlockMask(*I);
1569 LLVM_DEBUG(dbgs() << " ... done: " << *I);
1573 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
1575 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
1576 for (auto *MBB : PostOrder) {
1577 recomputeLiveIns(*MBB);
1578 // FIXME: For some reason, the live-in print order is non-deterministic for
1579 // our tests and I can't out why... So just sort them.
1580 MBB->sortUniqueLiveIns();
1583 for (auto *MBB : reverse(PostOrder))
1584 recomputeLivenessFlags(*MBB);
1586 // We've moved, removed and inserted new instructions, so update RDA.
1590 bool ARMLowOverheadLoops::RevertNonLoops() {
1591 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1592 bool Changed = false;
1594 for (auto &MBB : *MF) {
1595 SmallVector<MachineInstr*, 4> Starts;
1596 SmallVector<MachineInstr*, 4> Decs;
1597 SmallVector<MachineInstr*, 4> Ends;
1599 for (auto &I : MBB) {
1601 Starts.push_back(&I);
1602 else if (I.getOpcode() == ARM::t2LoopDec)
1604 else if (I.getOpcode() == ARM::t2LoopEnd)
1608 if (Starts.empty() && Decs.empty() && Ends.empty())
1613 for (auto *Start : Starts) {
1614 if (Start->getOpcode() == ARM::t2WhileLoopStart)
1617 Start->eraseFromParent();
1619 for (auto *Dec : Decs)
1622 for (auto *End : Ends)
1628 FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1629 return new ARMLowOverheadLoops();