1//===-- ARMLowOverheadLoops.cpp - CodeGen Low-overhead Loops ---*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8/// \file
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.
17///
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
20/// loop form.
21///
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
36/// instructions.
37///
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:
43/// \verbatim
44/// if VPT active: ; Between a DLSTP/LETP, or for predicated instrs
45/// VPR.P0 &= Value
46/// else
47/// VPR.P0 = Value
48/// \endverbatim
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//===----------------------------------------------------------------------===//
53
54#include "ARM.h"
55#include "ARMBaseInstrInfo.h"
56#include "ARMBasicBlockInfo.h"
57#include "ARMSubtarget.h"
58#include "MVETailPredUtils.h"
59#include "Thumb2InstrInfo.h"
60#include "llvm/ADT/SetVector.h"
61#include "llvm/CodeGen/LivePhysRegs.h"
62#include "llvm/CodeGen/MachineFrameInfo.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"
70
71using namespace llvm;
72
73#define DEBUG_TYPE "arm-low-overhead-loops"
74#define ARM_LOW_OVERHEAD_LOOPS_NAME "ARM Low Overhead Loops pass"
75
76static cl::opt<bool>
77DisableTailPredication("arm-loloops-disable-tailpred", cl::Hidden,
78 cl::desc("Disable tail-predication in the ARM LowOverheadLoop pass"),
79 cl::init(Val: false));
80
81static cl::opt<bool>
82 DisableOmitDLS("arm-disable-omit-dls", cl::Hidden,
83 cl::desc("Disable omitting 'dls lr, lr' instructions"),
84 cl::init(Val: false));
85
86static bool isVectorPredicated(MachineInstr *MI) {
87 int PIdx = llvm::findFirstVPTPredOperandIdx(MI: *MI);
88 return PIdx != -1 && MI->getOperand(i: PIdx + 1).getReg() == ARM::VPR;
89}
90
91static bool isVectorPredicate(MachineInstr *MI) {
92 return MI->findRegisterDefOperandIdx(Reg: ARM::VPR, /*TRI=*/nullptr) != -1;
93}
94
95static bool hasVPRUse(MachineInstr &MI) {
96 return MI.findRegisterUseOperandIdx(Reg: ARM::VPR, /*TRI=*/nullptr) != -1;
97}
98
99static bool isDomainMVE(MachineInstr *MI) {
100 uint64_t Domain = MI->getDesc().TSFlags & ARMII::DomainMask;
101 return Domain == ARMII::DomainMVE;
102}
103
104static int getVecSize(const MachineInstr &MI) {
105 const MCInstrDesc &MCID = MI.getDesc();
106 uint64_t Flags = MCID.TSFlags;
107 return (Flags & ARMII::VecSize) >> ARMII::VecSizeShift;
108}
109
110static bool shouldInspect(MachineInstr &MI) {
111 if (MI.isDebugInstr())
112 return false;
113 return isDomainMVE(MI: &MI) || isVectorPredicate(MI: &MI) || hasVPRUse(MI);
114}
115
116static bool isHorizontalReduction(const MachineInstr &MI) {
117 const MCInstrDesc &MCID = MI.getDesc();
118 uint64_t Flags = MCID.TSFlags;
119 return (Flags & ARMII::HorizontalReduction) != 0;
120}
121
122namespace {
123
124 using InstSet = SmallPtrSetImpl<MachineInstr *>;
125
126 class PostOrderLoopTraversal {
127 MachineLoop &ML;
128 MachineLoopInfo &MLI;
129 SmallPtrSet<MachineBasicBlock*, 4> Visited;
130 SmallVector<MachineBasicBlock*, 4> Order;
131
132 public:
133 PostOrderLoopTraversal(MachineLoop &ML, MachineLoopInfo &MLI)
134 : ML(ML), MLI(MLI) { }
135
136 const SmallVectorImpl<MachineBasicBlock*> &getOrder() const {
137 return Order;
138 }
139
140 // Visit all the blocks within the loop, as well as exit blocks and any
141 // blocks properly dominating the header.
142 void ProcessLoop() {
143 std::function<void(MachineBasicBlock *)> Search =
144 [this, &Search](MachineBasicBlock *MBB) -> void {
145 if (!Visited.insert(Ptr: MBB).second)
146 return;
147
148 for (auto *Succ : MBB->successors()) {
149 if (!ML.contains(BB: Succ))
150 continue;
151 Search(Succ);
152 }
153 Order.push_back(Elt: MBB);
154 };
155
156 // Insert exit blocks.
157 SmallVector<MachineBasicBlock*, 2> ExitBlocks;
158 ML.getExitBlocks(ExitBlocks);
159 append_range(C&: Order, R&: ExitBlocks);
160
161 // Then add the loop body.
162 Search(ML.getHeader());
163
164 // Then try the preheader and its predecessors.
165 std::function<void(MachineBasicBlock*)> GetPredecessor =
166 [this, &GetPredecessor] (MachineBasicBlock *MBB) -> void {
167 Order.push_back(Elt: MBB);
168 if (MBB->pred_size() == 1)
169 GetPredecessor(*MBB->pred_begin());
170 };
171
172 if (auto *Preheader = ML.getLoopPreheader())
173 GetPredecessor(Preheader);
174 else if (auto *Preheader = MLI.findLoopPreheader(L: &ML, SpeculativePreheader: true, FindMultiLoopPreheader: true))
175 GetPredecessor(Preheader);
176 }
177 };
178
179 class VPTBlock {
180 SmallVector<MachineInstr *, 4> Insts;
181
182 public:
183 VPTBlock(MachineInstr *MI) { Insts.push_back(Elt: MI); }
184
185 // Have we found an instruction within the block which defines the vpr? If
186 // so, not all the instructions in the block will have the same predicate.
187 bool hasUniformPredicate() { return getDivergent() == nullptr; }
188
189 // If it exists, return the first internal instruction which modifies the
190 // VPR.
191 MachineInstr *getDivergent() {
192 SmallVectorImpl<MachineInstr *> &Insts = getInsts();
193 for (unsigned i = 1; i < Insts.size(); ++i) {
194 MachineInstr *Next = Insts[i];
195 if (isVectorPredicate(MI: Next))
196 return Next; // Found an instruction altering the vpr.
197 }
198 return nullptr;
199 }
200
201 void insert(MachineInstr *MI) {
202 Insts.push_back(Elt: MI);
203 // VPT/VPST + 4 predicated instructions.
204 assert(Insts.size() <= 5 && "Too many instructions in VPT block!");
205 }
206
207 bool containsVCTP() const { return llvm::any_of(Range: Insts, P: isVCTP); }
208
209 unsigned size() const { return Insts.size(); }
210 SmallVectorImpl<MachineInstr *> &getInsts() { return Insts; }
211 };
212
213 // Represent the current state of the VPR and hold all instances which
214 // represent a VPT block, which is a list of instructions that begins with a
215 // VPT/VPST and has a maximum of four proceeding instructions. All
216 // instructions within the block are predicated upon the vpr and we allow
217 // instructions to define the vpr within in the block too.
218 class VPTState {
219 friend struct LowOverheadLoop;
220
221 SmallVector<VPTBlock, 4> Blocks;
222 SetVector<MachineInstr *> CurrentPredicates;
223 std::map<MachineInstr *, SetVector<MachineInstr *>> PredicatedInsts;
224
225 void CreateVPTBlock(MachineInstr *MI) {
226 assert((CurrentPredicates.size() || MI->getParent()->isLiveIn(ARM::VPR))
227 && "Can't begin VPT without predicate");
228 Blocks.emplace_back(Args&: MI);
229 // The execution of MI is predicated upon the current set of instructions
230 // that are AND'ed together to form the VPR predicate value. In the case
231 // that MI is a VPT, CurrentPredicates will also just be MI.
232 PredicatedInsts[MI] = CurrentPredicates;
233 }
234
235 void addInst(MachineInstr *MI) {
236 Blocks.back().insert(MI);
237 PredicatedInsts[MI] = CurrentPredicates;
238 }
239
240 void addPredicate(MachineInstr *MI) {
241 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VPT Predicate: " << *MI);
242 CurrentPredicates.insert(X: MI);
243 }
244
245 void resetPredicate(MachineInstr *MI) {
246 LLVM_DEBUG(dbgs() << "ARM Loops: Resetting VPT Predicate: " << *MI);
247 CurrentPredicates.clear();
248 CurrentPredicates.insert(X: MI);
249 }
250
251 public:
252 // Return whether the given instruction is predicated upon a VCTP.
253 bool isPredicatedOnVCTP(MachineInstr *MI, bool Exclusive = false) {
254 SetVector<MachineInstr *> &Predicates = PredicatedInsts[MI];
255 if (Exclusive && Predicates.size() != 1)
256 return false;
257 // We do not know how to convert an else predicate of a VCTP.
258 if (getVPTInstrPredicate(MI: *MI) == ARMVCC::Else)
259 return false;
260 return llvm::any_of(Range&: Predicates, P: isVCTP);
261 }
262
263 // Is the VPST, controlling the block entry, predicated upon a VCTP.
264 bool isEntryPredicatedOnVCTP(VPTBlock &Block, bool Exclusive = false) {
265 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
266 return isPredicatedOnVCTP(MI: Insts.front(), Exclusive);
267 }
268
269 // If this block begins with a VPT, we can check whether it's using
270 // at least one predicated input(s), as well as possible loop invariant
271 // which would result in it being implicitly predicated.
272 bool hasImplicitlyValidVPT(VPTBlock &Block, ReachingDefInfo &RDI) {
273 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
274 MachineInstr *VPT = Insts.front();
275 assert(isVPTOpcode(VPT->getOpcode()) &&
276 "Expected VPT block to begin with VPT/VPST");
277
278 if (VPT->getOpcode() == ARM::MVE_VPST)
279 return false;
280
281 // If the VPT block does not define something that is an "output", then
282 // the tail-predicated version will just perform a subset of the original
283 // vpt block, where the last lanes should not be used.
284 if (isVPTOpcode(Opc: VPT->getOpcode()) &&
285 all_of(Range&: Block.getInsts(), P: [](const MachineInstr *MI) {
286 return !MI->mayStore() && !MI->mayLoad() &&
287 !isHorizontalReduction(MI: *MI) && !isVCTP(MI);
288 }))
289 return true;
290
291 auto IsOperandPredicated = [&](MachineInstr *MI, unsigned Idx) {
292 MachineInstr *Op = RDI.getMIOperand(MI, MO&: MI->getOperand(i: Idx));
293 return Op && PredicatedInsts.count(x: Op) && isPredicatedOnVCTP(MI: Op);
294 };
295
296 auto IsOperandInvariant = [&](MachineInstr *MI, unsigned Idx) {
297 MachineOperand &MO = MI->getOperand(i: Idx);
298 if (!MO.isReg() || !MO.getReg())
299 return true;
300
301 SmallPtrSet<MachineInstr *, 2> Defs;
302 RDI.getGlobalReachingDefs(MI, Reg: MO.getReg(), Defs);
303 if (Defs.empty())
304 return true;
305
306 for (auto *Def : Defs)
307 if (Def->getParent() == VPT->getParent())
308 return false;
309 return true;
310 };
311
312 // Check that at least one of the operands is directly predicated on a
313 // vctp and allow an invariant value too.
314 return (IsOperandPredicated(VPT, 1) || IsOperandPredicated(VPT, 2)) &&
315 (IsOperandPredicated(VPT, 1) || IsOperandInvariant(VPT, 1)) &&
316 (IsOperandPredicated(VPT, 2) || IsOperandInvariant(VPT, 2));
317 }
318
319 bool isValid(ReachingDefInfo &RDI) {
320 // All predication within the loop should be based on vctp. If the block
321 // isn't predicated on entry, check whether the vctp is within the block
322 // and that all other instructions are then predicated on it.
323 for (auto &Block : Blocks) {
324 if (isEntryPredicatedOnVCTP(Block, Exclusive: false) &&
325 !any_of(Range: drop_begin(RangeOrContainer&: Block.getInsts()), P: [](const MachineInstr *MI) {
326 return getVPTInstrPredicate(MI: *MI) == ARMVCC::Else;
327 }))
328 continue;
329 if (hasImplicitlyValidVPT(Block, RDI))
330 continue;
331
332 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
333 // We don't know how to convert a block with just a VPT;VCTP into
334 // anything valid once we remove the VCTP. For now just bail out.
335 assert(isVPTOpcode(Insts.front()->getOpcode()) &&
336 "Expected VPT block to start with a VPST or VPT!");
337 if (Insts.size() == 2 && Insts.front()->getOpcode() != ARM::MVE_VPST &&
338 isVCTP(MI: Insts.back()))
339 return false;
340
341 for (auto *MI : Insts) {
342 // Check that any internal VCTPs are 'Then' predicated.
343 if (isVCTP(MI) && getVPTInstrPredicate(MI: *MI) != ARMVCC::Then)
344 return false;
345 // Skip other instructions that build up the predicate.
346 if (MI->getOpcode() == ARM::MVE_VPST || isVectorPredicate(MI))
347 continue;
348 // Check that any other instructions are predicated upon a vctp.
349 // TODO: We could infer when VPTs are implicitly predicated on the
350 // vctp (when the operands are predicated).
351 if (!isPredicatedOnVCTP(MI)) {
352 LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *MI);
353 return false;
354 }
355 }
356 }
357 return true;
358 }
359 };
360
361 struct LowOverheadLoop {
362
363 MachineLoop &ML;
364 MachineBasicBlock *Preheader = nullptr;
365 MachineLoopInfo &MLI;
366 ReachingDefInfo &RDI;
367 const TargetRegisterInfo &TRI;
368 const ARMBaseInstrInfo &TII;
369 MachineFunction *MF = nullptr;
370 MachineBasicBlock::iterator StartInsertPt;
371 MachineBasicBlock *StartInsertBB = nullptr;
372 MachineInstr *Start = nullptr;
373 MachineInstr *Dec = nullptr;
374 MachineInstr *End = nullptr;
375 MachineOperand TPNumElements;
376 SmallVector<MachineInstr *, 4> VCTPs;
377 SmallPtrSet<MachineInstr *, 4> ToRemove;
378 SmallPtrSet<MachineInstr *, 4> BlockMasksToRecompute;
379 SmallPtrSet<MachineInstr *, 4> DoubleWidthResultInstrs;
380 SmallPtrSet<MachineInstr *, 4> VMOVCopies;
381 bool Revert = false;
382 bool CannotTailPredicate = false;
383 VPTState VPTstate;
384
385 LowOverheadLoop(MachineLoop &ML, MachineLoopInfo &MLI, ReachingDefInfo &RDI,
386 const TargetRegisterInfo &TRI, const ARMBaseInstrInfo &TII)
387 : ML(ML), MLI(MLI), RDI(RDI), TRI(TRI), TII(TII),
388 TPNumElements(MachineOperand::CreateImm(Val: 0)) {
389 MF = ML.getHeader()->getParent();
390 if (auto *MBB = ML.getLoopPreheader())
391 Preheader = MBB;
392 else if (auto *MBB = MLI.findLoopPreheader(L: &ML, SpeculativePreheader: true, FindMultiLoopPreheader: true))
393 Preheader = MBB;
394 }
395
396 // If this is an MVE instruction, check that we know how to use tail
397 // predication with it. Record VPT blocks and return whether the
398 // instruction is valid for tail predication.
399 bool ValidateMVEInst(MachineInstr *MI);
400
401 void AnalyseMVEInst(MachineInstr *MI) {
402 CannotTailPredicate = !ValidateMVEInst(MI);
403 }
404
405 bool IsTailPredicationLegal() const {
406 // For now, let's keep things really simple and only support a single
407 // block for tail predication.
408 return !Revert && FoundAllComponents() && !VCTPs.empty() &&
409 !CannotTailPredicate && ML.getNumBlocks() == 1;
410 }
411
412 // Given that MI is a VCTP, check that is equivalent to any other VCTPs
413 // found.
414 bool AddVCTP(MachineInstr *MI);
415
416 // Check that the predication in the loop will be equivalent once we
417 // perform the conversion. Also ensure that we can provide the number
418 // of elements to the loop start instruction.
419 bool ValidateTailPredicate();
420
421 // Check that any values available outside of the loop will be the same
422 // after tail predication conversion.
423 bool ValidateLiveOuts();
424
425 // Check the branch targets are within range and we satisfy our
426 // restrictions.
427 void Validate(ARMBasicBlockUtils *BBUtils);
428
429 bool FoundAllComponents() const {
430 return Start && Dec && End;
431 }
432
433 SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTstate.Blocks; }
434
435 // Return the operand for the loop start instruction. This will be the loop
436 // iteration count, or the number of elements if we're tail predicating.
437 MachineOperand &getLoopStartOperand() {
438 if (IsTailPredicationLegal())
439 return TPNumElements;
440 return Start->getOperand(i: 1);
441 }
442
443 unsigned getStartOpcode() const {
444 bool IsDo = isDoLoopStart(MI: *Start);
445 if (!IsTailPredicationLegal())
446 return IsDo ? ARM::t2DLS : ARM::t2WLS;
447
448 return VCTPOpcodeToLSTP(Opcode: VCTPs.back()->getOpcode(), IsDoLoop: IsDo);
449 }
450
451 void dump() const {
452 if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
453 if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
454 if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
455 if (!VCTPs.empty()) {
456 dbgs() << "ARM Loops: Found VCTP(s):\n";
457 for (auto *MI : VCTPs)
458 dbgs() << " - " << *MI;
459 }
460 if (!FoundAllComponents())
461 dbgs() << "ARM Loops: Not a low-overhead loop.\n";
462 else if (!(Start && Dec && End))
463 dbgs() << "ARM Loops: Failed to find all loop components.\n";
464 }
465 };
466
467 class ARMLowOverheadLoops : public MachineFunctionPass {
468 MachineFunction *MF = nullptr;
469 MachineLoopInfo *MLI = nullptr;
470 ReachingDefInfo *RDI = nullptr;
471 const ARMBaseInstrInfo *TII = nullptr;
472 MachineRegisterInfo *MRI = nullptr;
473 const TargetRegisterInfo *TRI = nullptr;
474 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
475
476 public:
477 static char ID;
478
479 ARMLowOverheadLoops() : MachineFunctionPass(ID) { }
480
481 void getAnalysisUsage(AnalysisUsage &AU) const override {
482 AU.setPreservesCFG();
483 AU.addRequired<MachineLoopInfoWrapperPass>();
484 AU.addRequired<ReachingDefInfoWrapperPass>();
485 MachineFunctionPass::getAnalysisUsage(AU);
486 }
487
488 bool runOnMachineFunction(MachineFunction &MF) override;
489
490 MachineFunctionProperties getRequiredProperties() const override {
491 return MachineFunctionProperties().setNoVRegs().setTracksLiveness();
492 }
493
494 StringRef getPassName() const override {
495 return ARM_LOW_OVERHEAD_LOOPS_NAME;
496 }
497
498 private:
499 bool ProcessLoop(MachineLoop *ML);
500
501 bool RevertNonLoops();
502
503 void RevertWhile(MachineInstr *MI) const;
504 void RevertDo(MachineInstr *MI) const;
505
506 bool RevertLoopDec(MachineInstr *MI) const;
507
508 void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
509
510 void RevertLoopEndDec(MachineInstr *MI) const;
511
512 void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
513
514 MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
515
516 void Expand(LowOverheadLoop &LoLoop);
517
518 void IterationCountDCE(LowOverheadLoop &LoLoop);
519 };
520}
521
522char ARMLowOverheadLoops::ID = 0;
523
524INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
525 false, false)
526
527static bool TryRemove(MachineInstr *MI, ReachingDefInfo &RDI, InstSet &ToRemove,
528 InstSet &Ignore) {
529
530 // Check that we can remove all of Killed without having to modify any IT
531 // blocks.
532 auto WontCorruptITs = [](InstSet &Killed, ReachingDefInfo &RDI) {
533 // Collect the dead code and the MBBs in which they reside.
534 SmallPtrSet<MachineBasicBlock*, 2> BasicBlocks;
535 for (auto *Dead : Killed)
536 BasicBlocks.insert(Ptr: Dead->getParent());
537
538 // Collect IT blocks in all affected basic blocks.
539 std::map<MachineInstr *, SmallPtrSet<MachineInstr *, 2>> ITBlocks;
540 for (auto *MBB : BasicBlocks) {
541 for (auto &IT : *MBB) {
542 if (IT.getOpcode() != ARM::t2IT)
543 continue;
544 RDI.getReachingLocalUses(MI: &IT, Reg: MCRegister::from(Val: ARM::ITSTATE),
545 Uses&: ITBlocks[&IT]);
546 }
547 }
548
549 // If we're removing all of the instructions within an IT block, then
550 // also remove the IT instruction.
551 SmallPtrSet<MachineInstr *, 2> ModifiedITs;
552 SmallPtrSet<MachineInstr *, 2> RemoveITs;
553 for (auto *Dead : Killed) {
554 if (MachineOperand *MO =
555 Dead->findRegisterUseOperand(Reg: ARM::ITSTATE, /*TRI=*/nullptr)) {
556 MachineInstr *IT = RDI.getMIOperand(MI: Dead, MO&: *MO);
557 RemoveITs.insert(Ptr: IT);
558 auto &CurrentBlock = ITBlocks[IT];
559 CurrentBlock.erase(Ptr: Dead);
560 if (CurrentBlock.empty())
561 ModifiedITs.erase(Ptr: IT);
562 else
563 ModifiedITs.insert(Ptr: IT);
564 }
565 }
566 if (!ModifiedITs.empty())
567 return false;
568 Killed.insert_range(R&: RemoveITs);
569 return true;
570 };
571
572 SmallPtrSet<MachineInstr *, 2> Uses;
573 if (!RDI.isSafeToRemove(MI, ToRemove&: Uses, Ignore))
574 return false;
575
576 if (WontCorruptITs(Uses, RDI)) {
577 ToRemove.insert_range(R&: Uses);
578 LLVM_DEBUG(dbgs() << "ARM Loops: Able to remove: " << *MI
579 << " - can also remove:\n";
580 for (auto *Use : Uses)
581 dbgs() << " - " << *Use);
582
583 SmallPtrSet<MachineInstr*, 4> Killed;
584 RDI.collectKilledOperands(MI, Dead&: Killed);
585 if (WontCorruptITs(Killed, RDI)) {
586 ToRemove.insert_range(R&: Killed);
587 LLVM_DEBUG(for (auto *Dead : Killed)
588 dbgs() << " - " << *Dead);
589 }
590 return true;
591 }
592 return false;
593}
594
595bool LowOverheadLoop::ValidateTailPredicate() {
596 if (!IsTailPredicationLegal()) {
597 LLVM_DEBUG(if (VCTPs.empty())
598 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
599 dbgs() << "ARM Loops: Tail-predication is not valid.\n");
600 return false;
601 }
602
603 assert(!VCTPs.empty() && "VCTP instruction expected but is not set");
604 assert(ML.getBlocks().size() == 1 &&
605 "Shouldn't be processing a loop with more than one block");
606
607 if (DisableTailPredication) {
608 LLVM_DEBUG(dbgs() << "ARM Loops: tail-predication is disabled\n");
609 return false;
610 }
611
612 if (!VPTstate.isValid(RDI)) {
613 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid VPT state.\n");
614 return false;
615 }
616
617 if (!ValidateLiveOuts()) {
618 LLVM_DEBUG(dbgs() << "ARM Loops: Invalid live outs.\n");
619 return false;
620 }
621
622 // For tail predication, we need to provide the number of elements, instead
623 // of the iteration count, to the loop start instruction. The number of
624 // elements is provided to the vctp instruction, so we need to check that
625 // we can use this register at InsertPt.
626 MachineInstr *VCTP = VCTPs.back();
627 if (Start->getOpcode() == ARM::t2DoLoopStartTP ||
628 Start->getOpcode() == ARM::t2WhileLoopStartTP) {
629 TPNumElements = Start->getOperand(i: 2);
630 StartInsertPt = Start;
631 StartInsertBB = Start->getParent();
632 } else {
633 TPNumElements = VCTP->getOperand(i: 1);
634 MCRegister NumElements = TPNumElements.getReg().asMCReg();
635
636 // If the register is defined within loop, then we can't perform TP.
637 // TODO: Check whether this is just a mov of a register that would be
638 // available.
639 if (RDI.hasLocalDefBefore(MI: VCTP, Reg: NumElements)) {
640 LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
641 return false;
642 }
643
644 // The element count register maybe defined after InsertPt, in which case we
645 // need to try to move either InsertPt or the def so that the [w|d]lstp can
646 // use the value.
647
648 if (StartInsertPt != StartInsertBB->end() &&
649 !RDI.isReachingDefLiveOut(MI: &*StartInsertPt, Reg: NumElements)) {
650 if (auto *ElemDef =
651 RDI.getLocalLiveOutMIDef(MBB: StartInsertBB, Reg: NumElements)) {
652 if (RDI.isSafeToMoveForwards(From: ElemDef, To: &*StartInsertPt)) {
653 ElemDef->removeFromParent();
654 StartInsertBB->insert(I: StartInsertPt, MI: ElemDef);
655 LLVM_DEBUG(dbgs()
656 << "ARM Loops: Moved element count def: " << *ElemDef);
657 } else if (RDI.isSafeToMoveBackwards(From: &*StartInsertPt, To: ElemDef)) {
658 StartInsertPt->removeFromParent();
659 StartInsertBB->insertAfter(I: MachineBasicBlock::iterator(ElemDef),
660 MI: &*StartInsertPt);
661 LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
662 } else {
663 // If we fail to move an instruction and the element count is provided
664 // by a mov, use the mov operand if it will have the same value at the
665 // insertion point
666 MachineOperand Operand = ElemDef->getOperand(i: 1);
667 if (isMovRegOpcode(Opc: ElemDef->getOpcode()) &&
668 RDI.getUniqueReachingMIDef(MI: ElemDef, Reg: Operand.getReg().asMCReg()) ==
669 RDI.getUniqueReachingMIDef(MI: &*StartInsertPt,
670 Reg: Operand.getReg().asMCReg())) {
671 TPNumElements = Operand;
672 NumElements = TPNumElements.getReg();
673 } else {
674 LLVM_DEBUG(dbgs()
675 << "ARM Loops: Unable to move element count to loop "
676 << "start instruction.\n");
677 return false;
678 }
679 }
680 }
681 }
682
683 // Especially in the case of while loops, InsertBB may not be the
684 // preheader, so we need to check that the register isn't redefined
685 // before entering the loop.
686 auto CannotProvideElements = [this](MachineBasicBlock *MBB,
687 MCRegister NumElements) {
688 auto Back = MBB->getLastNonDebugInstr();
689 if (Back == MBB->end())
690 return false;
691 // NumElements is redefined in this block.
692 if (RDI.hasLocalDefBefore(MI: &*Back, Reg: NumElements))
693 return true;
694
695 // Don't continue searching up through multiple predecessors.
696 if (MBB->pred_size() > 1)
697 return true;
698
699 return false;
700 };
701
702 // Search backwards for a def, until we get to InsertBB.
703 MachineBasicBlock *MBB = Preheader;
704 while (MBB && MBB != StartInsertBB) {
705 if (CannotProvideElements(MBB, NumElements)) {
706 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
707 return false;
708 }
709 MBB = *MBB->pred_begin();
710 }
711 }
712
713 // Could inserting the [W|D]LSTP cause some unintended affects? In a perfect
714 // world the [w|d]lstp instruction would be last instruction in the preheader
715 // and so it would only affect instructions within the loop body. But due to
716 // scheduling, and/or the logic in this pass (above), the insertion point can
717 // be moved earlier. So if the Loop Start isn't the last instruction in the
718 // preheader, and if the initial element count is smaller than the vector
719 // width, the Loop Start instruction will immediately generate one or more
720 // false lane mask which can, incorrectly, affect the proceeding MVE
721 // instructions in the preheader.
722 if (std::any_of(first: StartInsertPt, last: StartInsertBB->end(), pred: shouldInspect)) {
723 LLVM_DEBUG(dbgs() << "ARM Loops: Instruction blocks [W|D]LSTP\n");
724 return false;
725 }
726
727 // For any DoubleWidthResultInstrs we found whilst scanning instructions, they
728 // need to compute an output size that is smaller than the VCTP mask operates
729 // on. The VecSize of the DoubleWidthResult is the larger vector size - the
730 // size it extends into, so any VCTP VecSize <= is valid.
731 unsigned VCTPVecSize = getVecSize(MI: *VCTP);
732 for (MachineInstr *MI : DoubleWidthResultInstrs) {
733 unsigned InstrVecSize = getVecSize(MI: *MI);
734 if (InstrVecSize > VCTPVecSize) {
735 LLVM_DEBUG(dbgs() << "ARM Loops: Double width result larger than VCTP "
736 << "VecSize:\n" << *MI);
737 return false;
738 }
739 }
740
741 // Check that the value change of the element count is what we expect and
742 // that the predication will be equivalent. For this we need:
743 // NumElements = NumElements - VectorWidth. The sub will be a sub immediate
744 // and we can also allow register copies within the chain too.
745 auto IsValidSub = [](MachineInstr *MI, int ExpectedVecWidth) {
746 return -getAddSubImmediate(MI&: *MI) == ExpectedVecWidth;
747 };
748
749 MachineBasicBlock *MBB = VCTP->getParent();
750 // Remove modifications to the element count since they have no purpose in a
751 // tail predicated loop. Explicitly refer to the vctp operand no matter which
752 // register NumElements has been assigned to, since that is what the
753 // modifications will be using
754 if (auto *Def = RDI.getUniqueReachingMIDef(
755 MI: &MBB->back(), Reg: VCTP->getOperand(i: 1).getReg().asMCReg())) {
756 SmallPtrSet<MachineInstr*, 2> ElementChain;
757 SmallPtrSet<MachineInstr*, 2> Ignore;
758 unsigned ExpectedVectorWidth = getTailPredVectorWidth(Opcode: VCTP->getOpcode());
759
760 Ignore.insert_range(R&: VCTPs);
761
762 if (TryRemove(MI: Def, RDI, ToRemove&: ElementChain, Ignore)) {
763 bool FoundSub = false;
764
765 for (auto *MI : ElementChain) {
766 if (isMovRegOpcode(Opc: MI->getOpcode()))
767 continue;
768
769 if (isSubImmOpcode(Opc: MI->getOpcode())) {
770 if (FoundSub || !IsValidSub(MI, ExpectedVectorWidth)) {
771 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
772 " count: " << *MI);
773 return false;
774 }
775 FoundSub = true;
776 } else {
777 LLVM_DEBUG(dbgs() << "ARM Loops: Unexpected instruction in element"
778 " count: " << *MI);
779 return false;
780 }
781 }
782 ToRemove.insert_range(R&: ElementChain);
783 }
784 }
785
786 // If we converted the LoopStart to a t2DoLoopStartTP/t2WhileLoopStartTP, we
787 // can also remove any extra instructions in the preheader, which often
788 // includes a now unused MOV.
789 if ((Start->getOpcode() == ARM::t2DoLoopStartTP ||
790 Start->getOpcode() == ARM::t2WhileLoopStartTP) &&
791 Preheader && !Preheader->empty() &&
792 !RDI.hasLocalDefBefore(MI: VCTP, Reg: VCTP->getOperand(i: 1).getReg())) {
793 if (auto *Def = RDI.getUniqueReachingMIDef(
794 MI: &Preheader->back(), Reg: VCTP->getOperand(i: 1).getReg().asMCReg())) {
795 SmallPtrSet<MachineInstr *, 2> Ignore(llvm::from_range, VCTPs);
796 TryRemove(MI: Def, RDI, ToRemove, Ignore);
797 }
798 }
799
800 return true;
801}
802
803static bool isRegInClass(const MachineOperand &MO,
804 const TargetRegisterClass *Class) {
805 return MO.isReg() && MO.getReg() && Class->contains(Reg: MO.getReg());
806}
807
808// MVE 'narrowing' operate on half a lane, reading from half and writing
809// to half, which are referred to has the top and bottom half. The other
810// half retains its previous value.
811static bool retainsPreviousHalfElement(const MachineInstr &MI) {
812 const MCInstrDesc &MCID = MI.getDesc();
813 uint64_t Flags = MCID.TSFlags;
814 return (Flags & ARMII::RetainsPreviousHalfElement) != 0;
815}
816
817// Some MVE instructions read from the top/bottom halves of their operand(s)
818// and generate a vector result with result elements that are double the
819// width of the input.
820static bool producesDoubleWidthResult(const MachineInstr &MI) {
821 const MCInstrDesc &MCID = MI.getDesc();
822 uint64_t Flags = MCID.TSFlags;
823 return (Flags & ARMII::DoubleWidthResult) != 0;
824}
825
826// Can this instruction generate a non-zero result when given only zeroed
827// operands? This allows us to know that, given operands with false bytes
828// zeroed by masked loads, that the result will also contain zeros in those
829// bytes.
830static bool canGenerateNonZeros(const MachineInstr &MI) {
831
832 // Check for instructions which can write into a larger element size,
833 // possibly writing into a previous zero'd lane.
834 if (producesDoubleWidthResult(MI))
835 return true;
836
837 switch (MI.getOpcode()) {
838 default:
839 break;
840 // FIXME: VNEG FP and -0? I think we'll need to handle this once we allow
841 // fp16 -> fp32 vector conversions.
842 // Instructions that perform a NOT will generate 1s from 0s.
843 case ARM::MVE_VMVN:
844 case ARM::MVE_VORN:
845 // Count leading zeros will do just that!
846 case ARM::MVE_VCLZs8:
847 case ARM::MVE_VCLZs16:
848 case ARM::MVE_VCLZs32:
849 return true;
850 }
851 return false;
852}
853
854// Look at its register uses to see if it only can only receive zeros
855// into its false lanes which would then produce zeros. Also check that
856// the output register is also defined by an FalseLanesZero instruction
857// so that if tail-predication happens, the lanes that aren't updated will
858// still be zeros.
859static bool producesFalseLanesZero(MachineInstr &MI,
860 const TargetRegisterClass *QPRs,
861 const ReachingDefInfo &RDI,
862 InstSet &FalseLanesZero) {
863 if (canGenerateNonZeros(MI))
864 return false;
865
866 bool isPredicated = isVectorPredicated(MI: &MI);
867 // Predicated loads will write zeros to the falsely predicated bytes of the
868 // destination register.
869 if (MI.mayLoad())
870 return isPredicated;
871
872 auto IsZeroInit = [](MachineInstr *Def) {
873 return !isVectorPredicated(MI: Def) &&
874 Def->getOpcode() == ARM::MVE_VMOVimmi32 &&
875 Def->getOperand(i: 1).getImm() == 0;
876 };
877
878 bool AllowScalars = isHorizontalReduction(MI);
879 for (auto &MO : MI.operands()) {
880 if (!MO.isReg() || !MO.getReg())
881 continue;
882 if (!isRegInClass(MO, Class: QPRs) && AllowScalars)
883 continue;
884 // Skip the lr predicate reg
885 int PIdx = llvm::findFirstVPTPredOperandIdx(MI);
886 if (PIdx != -1 && MO.getOperandNo() == PIdx + ARM::SUBOP_vpred_n_tp_reg)
887 continue;
888
889 // Check that this instruction will produce zeros in its false lanes:
890 // - If it only consumes false lanes zero or constant 0 (vmov #0)
891 // - If it's predicated, it only matters that it's def register already has
892 // false lane zeros, so we can ignore the uses.
893 SmallPtrSet<MachineInstr *, 2> Defs;
894 RDI.getGlobalReachingDefs(MI: &MI, Reg: MO.getReg(), Defs);
895 if (Defs.empty())
896 return false;
897 for (auto *Def : Defs) {
898 if (Def == &MI || FalseLanesZero.count(Ptr: Def) || IsZeroInit(Def))
899 continue;
900 if (MO.isUse() && isPredicated)
901 continue;
902 return false;
903 }
904 }
905 LLVM_DEBUG(dbgs() << "ARM Loops: Always False Zeros: " << MI);
906 return true;
907}
908
909bool LowOverheadLoop::ValidateLiveOuts() {
910 // We want to find out if the tail-predicated version of this loop will
911 // produce the same values as the loop in its original form. For this to
912 // be true, the newly inserted implicit predication must not change the
913 // the (observable) results.
914 // We're doing this because many instructions in the loop will not be
915 // predicated and so the conversion from VPT predication to tail-predication
916 // can result in different values being produced; due to the tail-predication
917 // preventing many instructions from updating their falsely predicated
918 // lanes. This analysis assumes that all the instructions perform lane-wise
919 // operations and don't perform any exchanges.
920 // A masked load, whether through VPT or tail predication, will write zeros
921 // to any of the falsely predicated bytes. So, from the loads, we know that
922 // the false lanes are zeroed and here we're trying to track that those false
923 // lanes remain zero, or where they change, the differences are masked away
924 // by their user(s).
925 // All MVE stores have to be predicated, so we know that any predicate load
926 // operands, or stored results are equivalent already. Other explicitly
927 // predicated instructions will perform the same operation in the original
928 // loop and the tail-predicated form too. Because of this, we can insert
929 // loads, stores and other predicated instructions into our Predicated
930 // set and build from there.
931 const TargetRegisterClass *QPRs = TRI.getRegClass(i: ARM::MQPRRegClassID);
932 SetVector<MachineInstr *> FalseLanesUnknown;
933 SmallPtrSet<MachineInstr *, 4> FalseLanesZero;
934 SmallPtrSet<MachineInstr *, 4> Predicated;
935 MachineBasicBlock *Header = ML.getHeader();
936
937 LLVM_DEBUG(dbgs() << "ARM Loops: Validating Live outs\n");
938
939 for (auto &MI : *Header) {
940 if (!shouldInspect(MI))
941 continue;
942
943 if (isVCTP(MI: &MI) || isVPTOpcode(Opc: MI.getOpcode()))
944 continue;
945
946 bool isPredicated = isVectorPredicated(MI: &MI);
947 bool retainsOrReduces =
948 retainsPreviousHalfElement(MI) || isHorizontalReduction(MI);
949
950 if (isPredicated)
951 Predicated.insert(Ptr: &MI);
952 if (producesFalseLanesZero(MI, QPRs, RDI, FalseLanesZero))
953 FalseLanesZero.insert(Ptr: &MI);
954 else if (MI.getNumDefs() == 0)
955 continue;
956 else if (!isPredicated && retainsOrReduces) {
957 LLVM_DEBUG(dbgs() << " Unpredicated instruction that retainsOrReduces: " << MI);
958 return false;
959 } else if (!isPredicated && MI.getOpcode() != ARM::MQPRCopy)
960 FalseLanesUnknown.insert(X: &MI);
961 }
962
963 LLVM_DEBUG({
964 dbgs() << " Predicated:\n";
965 for (auto *I : Predicated)
966 dbgs() << " " << *I;
967 dbgs() << " FalseLanesZero:\n";
968 for (auto *I : FalseLanesZero)
969 dbgs() << " " << *I;
970 dbgs() << " FalseLanesUnknown:\n";
971 for (auto *I : FalseLanesUnknown)
972 dbgs() << " " << *I;
973 });
974
975 auto HasPredicatedUsers = [this](MachineInstr *MI, const MachineOperand &MO,
976 SmallPtrSetImpl<MachineInstr *> &Predicated) {
977 SmallPtrSet<MachineInstr *, 2> Uses;
978 RDI.getGlobalUses(MI, Reg: MO.getReg().asMCReg(), Uses);
979 for (auto *Use : Uses) {
980 if (Use != MI && !Predicated.count(Ptr: Use))
981 return false;
982 }
983 return true;
984 };
985
986 // Visit the unknowns in reverse so that we can start at the values being
987 // stored and then we can work towards the leaves, hopefully adding more
988 // instructions to Predicated. Successfully terminating the loop means that
989 // all the unknown values have to found to be masked by predicated user(s).
990 // For any unpredicated values, we store them in NonPredicated so that we
991 // can later check whether these form a reduction.
992 SmallPtrSet<MachineInstr*, 2> NonPredicated;
993 for (auto *MI : reverse(C&: FalseLanesUnknown)) {
994 for (auto &MO : MI->operands()) {
995 if (!isRegInClass(MO, Class: QPRs) || !MO.isDef())
996 continue;
997 if (!HasPredicatedUsers(MI, MO, Predicated)) {
998 LLVM_DEBUG(dbgs() << " Found an unknown def of : "
999 << TRI.getRegAsmName(MO.getReg()) << " at " << *MI);
1000 NonPredicated.insert(Ptr: MI);
1001 break;
1002 }
1003 }
1004 // Any unknown false lanes have been masked away by the user(s).
1005 if (!NonPredicated.contains(Ptr: MI))
1006 Predicated.insert(Ptr: MI);
1007 }
1008
1009 SmallPtrSet<MachineInstr *, 2> LiveOutMIs;
1010 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
1011 ML.getExitBlocks(ExitBlocks);
1012 assert(ML.getNumBlocks() == 1 && "Expected single block loop!");
1013 assert(ExitBlocks.size() == 1 && "Expected a single exit block");
1014 MachineBasicBlock *ExitBB = ExitBlocks.front();
1015 for (const MachineBasicBlock::RegisterMaskPair &RegMask : ExitBB->liveins()) {
1016 // TODO: Instead of blocking predication, we could move the vctp to the exit
1017 // block and calculate it's operand there in or the preheader.
1018 if (RegMask.PhysReg == ARM::VPR) {
1019 LLVM_DEBUG(dbgs() << " VPR is live in to the exit block.");
1020 return false;
1021 }
1022 // Check Q-regs that are live in the exit blocks. We don't collect scalars
1023 // because they won't be affected by lane predication.
1024 if (QPRs->contains(Reg: RegMask.PhysReg))
1025 if (auto *MI = RDI.getLocalLiveOutMIDef(MBB: Header, Reg: RegMask.PhysReg))
1026 LiveOutMIs.insert(Ptr: MI);
1027 }
1028
1029 // We've already validated that any VPT predication within the loop will be
1030 // equivalent when we perform the predication transformation; so we know that
1031 // any VPT predicated instruction is predicated upon VCTP. Any live-out
1032 // instruction needs to be predicated, so check this here. The instructions
1033 // in NonPredicated have been found to be a reduction that we can ensure its
1034 // legality. Any MQPRCopy found will need to validate its input as if it was
1035 // live out.
1036 SmallVector<MachineInstr *> Worklist(LiveOutMIs.begin(), LiveOutMIs.end());
1037 while (!Worklist.empty()) {
1038 MachineInstr *MI = Worklist.pop_back_val();
1039 if (MI->getOpcode() == ARM::MQPRCopy) {
1040 LLVM_DEBUG(dbgs() << " Must generate copy as VMOV: " << *MI);
1041 VMOVCopies.insert(Ptr: MI);
1042 MachineInstr *CopySrc =
1043 RDI.getUniqueReachingMIDef(MI, Reg: MI->getOperand(i: 1).getReg());
1044 if (CopySrc)
1045 Worklist.push_back(Elt: CopySrc);
1046 } else if (NonPredicated.count(Ptr: MI) && FalseLanesUnknown.contains(key: MI)) {
1047 LLVM_DEBUG(dbgs() << " Unable to handle live out: " << *MI);
1048 VMOVCopies.clear();
1049 return false;
1050 } else if (isVectorPredicated(MI)) {
1051 // If this is a predicated instruction with merging semantics,
1052 // check where it gets its false lanes from, if any.
1053 int InactiveIdx = findVPTInactiveOperandIdx(MI: *MI);
1054 if (InactiveIdx != -1) {
1055 MachineInstr *FalseSrc = RDI.getUniqueReachingMIDef(
1056 MI, Reg: MI->getOperand(i: InactiveIdx).getReg());
1057 if (FalseSrc) {
1058 LLVM_DEBUG(dbgs()
1059 << " Must check source of false lanes for: " << *MI);
1060 Worklist.push_back(Elt: FalseSrc);
1061 }
1062 }
1063 }
1064 }
1065
1066 return true;
1067}
1068
1069void LowOverheadLoop::Validate(ARMBasicBlockUtils *BBUtils) {
1070 if (Revert)
1071 return;
1072
1073 // Check branch target ranges: WLS[TP] can only branch forwards and LE[TP]
1074 // can only jump back.
1075 auto ValidateRanges = [](MachineInstr *Start, MachineInstr *End,
1076 ARMBasicBlockUtils *BBUtils, MachineLoop &ML) {
1077 MachineBasicBlock *TgtBB = End->getOpcode() == ARM::t2LoopEnd
1078 ? End->getOperand(i: 1).getMBB()
1079 : End->getOperand(i: 2).getMBB();
1080 // TODO Maybe there's cases where the target doesn't have to be the header,
1081 // but for now be safe and revert.
1082 if (TgtBB != ML.getHeader()) {
1083 LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targeting header.\n");
1084 return false;
1085 }
1086
1087 // The WLS and LE instructions have 12-bits for the label offset. WLS
1088 // requires a positive offset, while LE uses negative.
1089 if (BBUtils->getOffsetOf(MI: End) < BBUtils->getOffsetOf(MBB: ML.getHeader()) ||
1090 !BBUtils->isBBInRange(MI: End, DestBB: ML.getHeader(), MaxDisp: 4094)) {
1091 LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
1092 return false;
1093 }
1094
1095 if (isWhileLoopStart(MI: *Start)) {
1096 MachineBasicBlock *TargetBB = getWhileLoopStartTargetBB(MI: *Start);
1097 if (BBUtils->getOffsetOf(MI: Start) > BBUtils->getOffsetOf(MBB: TargetBB) ||
1098 !BBUtils->isBBInRange(MI: Start, DestBB: TargetBB, MaxDisp: 4094)) {
1099 LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
1100 return false;
1101 }
1102 }
1103 return true;
1104 };
1105
1106 StartInsertPt = MachineBasicBlock::iterator(Start);
1107 StartInsertBB = Start->getParent();
1108 LLVM_DEBUG(dbgs() << "ARM Loops: Will insert LoopStart at "
1109 << *StartInsertPt);
1110
1111 Revert = !ValidateRanges(Start, End, BBUtils, ML);
1112 CannotTailPredicate = !ValidateTailPredicate();
1113}
1114
1115bool LowOverheadLoop::AddVCTP(MachineInstr *MI) {
1116 LLVM_DEBUG(dbgs() << "ARM Loops: Adding VCTP: " << *MI);
1117 if (VCTPs.empty()) {
1118 VCTPs.push_back(Elt: MI);
1119 return true;
1120 }
1121
1122 // If we find another VCTP, check whether it uses the same value as the main VCTP.
1123 // If it does, store it in the VCTPs set, else refuse it.
1124 MachineInstr *Prev = VCTPs.back();
1125 if (!Prev->getOperand(i: 1).isIdenticalTo(Other: MI->getOperand(i: 1)) ||
1126 !RDI.hasSameReachingDef(A: Prev, B: MI, Reg: MI->getOperand(i: 1).getReg().asMCReg())) {
1127 LLVM_DEBUG(dbgs() << "ARM Loops: Found VCTP with a different reaching "
1128 "definition from the main VCTP");
1129 return false;
1130 }
1131 VCTPs.push_back(Elt: MI);
1132 return true;
1133}
1134
1135static bool ValidateMVEStore(MachineInstr *MI, MachineLoop *ML) {
1136
1137 auto GetFrameIndex = [](MachineMemOperand *Operand) {
1138 const PseudoSourceValue *PseudoValue = Operand->getPseudoValue();
1139 if (PseudoValue && PseudoValue->kind() == PseudoSourceValue::FixedStack) {
1140 if (const auto *FS = dyn_cast<FixedStackPseudoSourceValue>(Val: PseudoValue)) {
1141 return FS->getFrameIndex();
1142 }
1143 }
1144 return -1;
1145 };
1146
1147 auto IsStackOp = [GetFrameIndex](MachineInstr *I) {
1148 switch (I->getOpcode()) {
1149 case ARM::MVE_VSTRWU32:
1150 case ARM::MVE_VLDRWU32: {
1151 return I->getOperand(i: 1).getReg() == ARM::SP &&
1152 I->memoperands().size() == 1 &&
1153 GetFrameIndex(I->memoperands().front()) >= 0;
1154 }
1155 default:
1156 return false;
1157 }
1158 };
1159
1160 // An unpredicated vector register spill is allowed if all of the uses of the
1161 // stack slot are within the loop
1162 if (MI->getOpcode() != ARM::MVE_VSTRWU32 || !IsStackOp(MI))
1163 return false;
1164
1165 // Search all blocks after the loop for accesses to the same stack slot.
1166 // ReachingDefAnalysis doesn't work for sp as it relies on registers being
1167 // live-out (which sp never is) to know what blocks to look in
1168 if (MI->memoperands().size() == 0)
1169 return false;
1170 int FI = GetFrameIndex(MI->memoperands().front());
1171
1172 auto &FrameInfo = MI->getParent()->getParent()->getFrameInfo();
1173 if (FI == -1 || !FrameInfo.isSpillSlotObjectIndex(ObjectIdx: FI))
1174 return false;
1175
1176 SmallVector<MachineBasicBlock *> Frontier;
1177 ML->getExitBlocks(ExitBlocks&: Frontier);
1178 SmallPtrSet<MachineBasicBlock *, 4> Visited{MI->getParent()};
1179 unsigned Idx = 0;
1180 while (Idx < Frontier.size()) {
1181 MachineBasicBlock *BB = Frontier[Idx];
1182 bool LookAtSuccessors = true;
1183 for (auto &I : *BB) {
1184 if (!IsStackOp(&I) || I.memoperands().size() == 0)
1185 continue;
1186 if (GetFrameIndex(I.memoperands().front()) != FI)
1187 continue;
1188 // If this block has a store to the stack slot before any loads then we
1189 // can ignore the block
1190 if (I.getOpcode() == ARM::MVE_VSTRWU32) {
1191 LookAtSuccessors = false;
1192 break;
1193 }
1194 // If the store and the load are using the same stack slot then the
1195 // store isn't valid for tail predication
1196 if (I.getOpcode() == ARM::MVE_VLDRWU32)
1197 return false;
1198 }
1199
1200 if (LookAtSuccessors) {
1201 for (auto *Succ : BB->successors()) {
1202 if (!Visited.contains(Ptr: Succ) && !is_contained(Range&: Frontier, Element: Succ))
1203 Frontier.push_back(Elt: Succ);
1204 }
1205 }
1206 Visited.insert(Ptr: BB);
1207 Idx++;
1208 }
1209
1210 return true;
1211}
1212
1213bool LowOverheadLoop::ValidateMVEInst(MachineInstr *MI) {
1214 if (CannotTailPredicate)
1215 return false;
1216
1217 if (!shouldInspect(MI&: *MI))
1218 return true;
1219
1220 if (MI->getOpcode() == ARM::MVE_VPSEL ||
1221 MI->getOpcode() == ARM::MVE_VPNOT) {
1222 // TODO: Allow VPSEL and VPNOT, we currently cannot because:
1223 // 1) It will use the VPR as a predicate operand, but doesn't have to be
1224 // instead a VPT block, which means we can assert while building up
1225 // the VPT block because we don't find another VPT or VPST to being a new
1226 // one.
1227 // 2) VPSEL still requires a VPR operand even after tail predicating,
1228 // which means we can't remove it unless there is another
1229 // instruction, such as vcmp, that can provide the VPR def.
1230 return false;
1231 }
1232
1233 // Record all VCTPs and check that they're equivalent to one another.
1234 if (isVCTP(MI) && !AddVCTP(MI))
1235 return false;
1236
1237 // Inspect uses first so that any instructions that alter the VPR don't
1238 // alter the predicate upon themselves.
1239 const MCInstrDesc &MCID = MI->getDesc();
1240 bool IsUse = false;
1241 unsigned LastOpIdx = MI->getNumOperands() - 1;
1242 for (const auto &Op : enumerate(First: reverse(C: MCID.operands()))) {
1243 const MachineOperand &MO = MI->getOperand(i: LastOpIdx - Op.index());
1244 if (!MO.isReg() || !MO.isUse() || MO.getReg() != ARM::VPR)
1245 continue;
1246
1247 if (ARM::isVpred(op: Op.value().OperandType)) {
1248 VPTstate.addInst(MI);
1249 IsUse = true;
1250 } else if (MI->getOpcode() != ARM::MVE_VPST) {
1251 LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
1252 return false;
1253 }
1254 }
1255
1256 // If we find an instruction that has been marked as not valid for tail
1257 // predication, only allow the instruction if it's contained within a valid
1258 // VPT block.
1259 bool RequiresExplicitPredication =
1260 (MCID.TSFlags & ARMII::ValidForTailPredication) == 0;
1261 if (isDomainMVE(MI) && RequiresExplicitPredication) {
1262 if (MI->getOpcode() == ARM::MQPRCopy)
1263 return true;
1264 if (!IsUse && producesDoubleWidthResult(MI: *MI)) {
1265 DoubleWidthResultInstrs.insert(Ptr: MI);
1266 return true;
1267 }
1268
1269 LLVM_DEBUG(if (!IsUse) dbgs()
1270 << "ARM Loops: Can't tail predicate: " << *MI);
1271 return IsUse;
1272 }
1273
1274 // If the instruction is already explicitly predicated, then the conversion
1275 // will be fine, but ensure that all store operations are predicated.
1276 if (MI->mayStore() && !ValidateMVEStore(MI, ML: &ML))
1277 return IsUse;
1278
1279 // If this instruction defines the VPR, update the predicate for the
1280 // proceeding instructions.
1281 if (isVectorPredicate(MI)) {
1282 // Clear the existing predicate when we're not in VPT Active state,
1283 // otherwise we add to it.
1284 if (!isVectorPredicated(MI))
1285 VPTstate.resetPredicate(MI);
1286 else
1287 VPTstate.addPredicate(MI);
1288 }
1289
1290 // Finally once the predicate has been modified, we can start a new VPT
1291 // block if necessary.
1292 if (isVPTOpcode(Opc: MI->getOpcode()))
1293 VPTstate.CreateVPTBlock(MI);
1294
1295 return true;
1296}
1297
1298bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
1299 const ARMSubtarget &ST = mf.getSubtarget<ARMSubtarget>();
1300 if (!ST.hasLOB())
1301 return false;
1302
1303 MF = &mf;
1304 LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
1305
1306 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1307 RDI = &getAnalysis<ReachingDefInfoWrapperPass>().getRDI();
1308 MF->getProperties().setTracksLiveness();
1309 MRI = &MF->getRegInfo();
1310 TII = ST.getInstrInfo();
1311 TRI = ST.getRegisterInfo();
1312 BBUtils = std::make_unique<ARMBasicBlockUtils>(args&: *MF);
1313 BBUtils->computeAllBlockSizes();
1314 BBUtils->adjustBBOffsetsAfter(MBB: &MF->front());
1315
1316 bool Changed = false;
1317 for (auto *ML : *MLI) {
1318 if (ML->isOutermost())
1319 Changed |= ProcessLoop(ML);
1320 }
1321 Changed |= RevertNonLoops();
1322 return Changed;
1323}
1324
1325bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
1326 bool Changed = false;
1327
1328 // Process inner loops first.
1329 for (MachineLoop *L : *ML)
1330 Changed |= ProcessLoop(ML: L);
1331
1332 LLVM_DEBUG({
1333 dbgs() << "ARM Loops: Processing loop containing:\n";
1334 if (auto *Preheader = ML->getLoopPreheader())
1335 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1336 else if (auto *Preheader = MLI->findLoopPreheader(ML, true, true))
1337 dbgs() << " - Preheader: " << printMBBReference(*Preheader) << "\n";
1338 for (auto *MBB : ML->getBlocks())
1339 dbgs() << " - Block: " << printMBBReference(*MBB) << "\n";
1340 });
1341
1342 // Search the given block for a loop start instruction. If one isn't found,
1343 // and there's only one predecessor block, search that one too.
1344 std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
1345 [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
1346 for (auto &MI : *MBB) {
1347 if (isLoopStart(MI))
1348 return &MI;
1349 }
1350 if (MBB->pred_size() == 1)
1351 return SearchForStart(*MBB->pred_begin());
1352 return nullptr;
1353 };
1354
1355 LowOverheadLoop LoLoop(*ML, *MLI, *RDI, *TRI, *TII);
1356 // Search the preheader for the start intrinsic.
1357 // FIXME: I don't see why we shouldn't be supporting multiple predecessors
1358 // with potentially multiple set.loop.iterations, so we need to enable this.
1359 if (LoLoop.Preheader)
1360 LoLoop.Start = SearchForStart(LoLoop.Preheader);
1361 else
1362 return Changed;
1363
1364 // Find the low-overhead loop components and decide whether or not to fall
1365 // back to a normal loop. Also look for a vctp instructions and decide
1366 // whether we can convert that predicate using tail predication.
1367 for (auto *MBB : reverse(C: ML->getBlocks())) {
1368 for (auto &MI : *MBB) {
1369 if (MI.isDebugValue())
1370 continue;
1371 else if (MI.getOpcode() == ARM::t2LoopDec)
1372 LoLoop.Dec = &MI;
1373 else if (MI.getOpcode() == ARM::t2LoopEnd)
1374 LoLoop.End = &MI;
1375 else if (MI.getOpcode() == ARM::t2LoopEndDec)
1376 LoLoop.End = LoLoop.Dec = &MI;
1377 else if (isLoopStart(MI))
1378 LoLoop.Start = &MI;
1379 else if (MI.getDesc().isCall()) {
1380 // TODO: Though the call will require LE to execute again, does this
1381 // mean we should revert? Always executing LE hopefully should be
1382 // faster than performing a sub,cmp,br or even subs,br.
1383 LoLoop.Revert = true;
1384 LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
1385 } else {
1386 // Record VPR defs and build up their corresponding vpt blocks.
1387 // Check we know how to tail predicate any mve instructions.
1388 LoLoop.AnalyseMVEInst(MI: &MI);
1389 }
1390 }
1391 }
1392
1393 LLVM_DEBUG(LoLoop.dump());
1394 if (!LoLoop.FoundAllComponents()) {
1395 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
1396 return Changed;
1397 }
1398
1399 assert(LoLoop.Start->getOpcode() != ARM::t2WhileLoopStart &&
1400 "Expected t2WhileLoopStart to be removed before regalloc!");
1401
1402 // Check that the only instruction using LoopDec is LoopEnd. This can only
1403 // happen when the Dec and End are separate, not a single t2LoopEndDec.
1404 // TODO: Check for copy chains that really have no effect.
1405 if (LoLoop.Dec != LoLoop.End) {
1406 SmallPtrSet<MachineInstr *, 2> Uses;
1407 RDI->getReachingLocalUses(MI: LoLoop.Dec, Reg: MCRegister::from(Val: ARM::LR), Uses);
1408 if (Uses.size() > 1 || !Uses.count(Ptr: LoLoop.End)) {
1409 LLVM_DEBUG(dbgs() << "ARM Loops: Unable to remove LoopDec.\n");
1410 LoLoop.Revert = true;
1411 }
1412 }
1413 LoLoop.Validate(BBUtils: BBUtils.get());
1414 Expand(LoLoop);
1415 return true;
1416}
1417
1418// WhileLoopStart holds the exit block, so produce a cmp lr, 0 and then a
1419// beq that branches to the exit branch.
1420// TODO: We could also try to generate a cbz if the value in LR is also in
1421// another low register.
1422void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
1423 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp: " << *MI);
1424 MachineBasicBlock *DestBB = getWhileLoopStartTargetBB(MI: *MI);
1425 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, MaxDisp: 254) ?
1426 ARM::tBcc : ARM::t2Bcc;
1427
1428 RevertWhileLoopStartLR(MI, TII, BrOpc);
1429}
1430
1431void ARMLowOverheadLoops::RevertDo(MachineInstr *MI) const {
1432 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to mov: " << *MI);
1433 RevertDoLoopStart(MI, TII);
1434}
1435
1436bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI) const {
1437 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
1438 MachineBasicBlock *MBB = MI->getParent();
1439 SmallPtrSet<MachineInstr*, 1> Ignore;
1440 for (auto I = MachineBasicBlock::iterator(MI), E = MBB->end(); I != E; ++I) {
1441 if (I->getOpcode() == ARM::t2LoopEnd) {
1442 Ignore.insert(Ptr: &*I);
1443 break;
1444 }
1445 }
1446
1447 // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
1448 bool SetFlags =
1449 RDI->isSafeToDefRegAt(MI, Reg: MCRegister::from(Val: ARM::CPSR), Ignore);
1450
1451 llvm::RevertLoopDec(MI, TII, SetFlags);
1452 return SetFlags;
1453}
1454
1455// Generate a subs, or sub and cmp, and a branch instead of an LE.
1456void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
1457 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to cmp, br: " << *MI);
1458
1459 MachineBasicBlock *DestBB = MI->getOperand(i: 1).getMBB();
1460 unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, MaxDisp: 254) ?
1461 ARM::tBcc : ARM::t2Bcc;
1462
1463 llvm::RevertLoopEnd(MI, TII, BrOpc, SkipCmp);
1464}
1465
1466// Generate a subs, or sub and cmp, and a branch instead of an LE.
1467void ARMLowOverheadLoops::RevertLoopEndDec(MachineInstr *MI) const {
1468 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to subs, br: " << *MI);
1469 assert(MI->getOpcode() == ARM::t2LoopEndDec && "Expected a t2LoopEndDec!");
1470 MachineBasicBlock *MBB = MI->getParent();
1471
1472 MachineInstrBuilder MIB =
1473 BuildMI(BB&: *MBB, I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode: ARM::t2SUBri));
1474 MIB.addDef(RegNo: ARM::LR);
1475 MIB.add(MO: MI->getOperand(i: 1));
1476 MIB.addImm(Val: 1);
1477 MIB.addImm(Val: ARMCC::AL);
1478 MIB.addReg(RegNo: ARM::NoRegister);
1479 MIB.addReg(RegNo: ARM::CPSR);
1480 MIB->getOperand(i: 5).setIsDef(true);
1481
1482 MachineBasicBlock *DestBB = MI->getOperand(i: 2).getMBB();
1483 unsigned BrOpc =
1484 BBUtils->isBBInRange(MI, DestBB, MaxDisp: 254) ? ARM::tBcc : ARM::t2Bcc;
1485
1486 // Create bne
1487 MIB = BuildMI(BB&: *MBB, I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode: BrOpc));
1488 MIB.add(MO: MI->getOperand(i: 2)); // branch target
1489 MIB.addImm(Val: ARMCC::NE); // condition code
1490 MIB.addReg(RegNo: ARM::CPSR);
1491
1492 MI->eraseFromParent();
1493}
1494
1495// Perform dead code elimation on the loop iteration count setup expression.
1496// If we are tail-predicating, the number of elements to be processed is the
1497// operand of the VCTP instruction in the vector body, see getCount(), which is
1498// register $r3 in this example:
1499//
1500// $lr = big-itercount-expression
1501// ..
1502// $lr = t2DoLoopStart renamable $lr
1503// vector.body:
1504// ..
1505// $vpr = MVE_VCTP32 renamable $r3
1506// renamable $lr = t2LoopDec killed renamable $lr, 1
1507// t2LoopEnd renamable $lr, %vector.body
1508// tB %end
1509//
1510// What we would like achieve here is to replace the do-loop start pseudo
1511// instruction t2DoLoopStart with:
1512//
1513// $lr = MVE_DLSTP_32 killed renamable $r3
1514//
1515// Thus, $r3 which defines the number of elements, is written to $lr,
1516// and then we want to delete the whole chain that used to define $lr,
1517// see the comment below how this chain could look like.
1518//
1519void ARMLowOverheadLoops::IterationCountDCE(LowOverheadLoop &LoLoop) {
1520 if (!LoLoop.IsTailPredicationLegal())
1521 return;
1522
1523 LLVM_DEBUG(dbgs() << "ARM Loops: Trying DCE on loop iteration count.\n");
1524
1525 MachineInstr *Def = RDI->getMIOperand(MI: LoLoop.Start, Idx: 1);
1526 if (!Def) {
1527 LLVM_DEBUG(dbgs() << "ARM Loops: Couldn't find iteration count.\n");
1528 return;
1529 }
1530
1531 // Collect and remove the users of iteration count.
1532 SmallPtrSet<MachineInstr*, 4> Killed = { LoLoop.Start, LoLoop.Dec,
1533 LoLoop.End };
1534 if (!TryRemove(MI: Def, RDI&: *RDI, ToRemove&: LoLoop.ToRemove, Ignore&: Killed))
1535 LLVM_DEBUG(dbgs() << "ARM Loops: Unsafe to remove loop iteration count.\n");
1536}
1537
1538MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
1539 LLVM_DEBUG(dbgs() << "ARM Loops: Expanding LoopStart.\n");
1540 // When using tail-predication, try to delete the dead code that was used to
1541 // calculate the number of loop iterations.
1542 IterationCountDCE(LoLoop);
1543
1544 MachineBasicBlock::iterator InsertPt = LoLoop.StartInsertPt;
1545 MachineInstr *Start = LoLoop.Start;
1546 MachineBasicBlock *MBB = LoLoop.StartInsertBB;
1547 unsigned Opc = LoLoop.getStartOpcode();
1548 MachineOperand &Count = LoLoop.getLoopStartOperand();
1549
1550 // A DLS lr, lr we needn't emit
1551 MachineInstr* NewStart;
1552 if (!DisableOmitDLS && Opc == ARM::t2DLS && Count.isReg() &&
1553 Count.getReg() == ARM::LR) {
1554 LLVM_DEBUG(dbgs() << "ARM Loops: Didn't insert start: DLS lr, lr");
1555 NewStart = nullptr;
1556 } else {
1557 MachineInstrBuilder MIB =
1558 BuildMI(BB&: *MBB, I: InsertPt, MIMD: Start->getDebugLoc(), MCID: TII->get(Opcode: Opc));
1559
1560 MIB.addDef(RegNo: ARM::LR);
1561 MIB.add(MO: Count);
1562 if (isWhileLoopStart(MI: *Start))
1563 MIB.addMBB(MBB: getWhileLoopStartTargetBB(MI: *Start));
1564
1565 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
1566 NewStart = &*MIB;
1567 }
1568
1569 LoLoop.ToRemove.insert(Ptr: Start);
1570 return NewStart;
1571}
1572
1573void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
1574 auto RemovePredicate = [](MachineInstr *MI) {
1575 if (MI->isDebugInstr())
1576 return;
1577 LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
1578 int PIdx = llvm::findFirstVPTPredOperandIdx(MI: *MI);
1579 assert(PIdx >= 1 && "Trying to unpredicate a non-predicated instruction");
1580 assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
1581 "Expected Then predicate!");
1582 MI->getOperand(i: PIdx).setImm(ARMVCC::None);
1583 MI->getOperand(i: PIdx + 1).setReg(0);
1584 };
1585
1586 for (auto &Block : LoLoop.getVPTBlocks()) {
1587 SmallVectorImpl<MachineInstr *> &Insts = Block.getInsts();
1588
1589 auto ReplaceVCMPWithVPT = [&](MachineInstr *&TheVCMP, MachineInstr *At) {
1590 assert(TheVCMP && "Replacing a removed or non-existent VCMP");
1591 // Replace the VCMP with a VPT
1592 MachineInstrBuilder MIB =
1593 BuildMI(BB&: *At->getParent(), I: At, MIMD: At->getDebugLoc(),
1594 MCID: TII->get(Opcode: VCMPOpcodeToVPT(Opcode: TheVCMP->getOpcode())));
1595 MIB.addImm(Val: ARMVCC::Then);
1596 // Register one
1597 MIB.add(MO: TheVCMP->getOperand(i: 1));
1598 // Register two
1599 MIB.add(MO: TheVCMP->getOperand(i: 2));
1600 // The comparison code, e.g. ge, eq, lt
1601 MIB.add(MO: TheVCMP->getOperand(i: 3));
1602 LLVM_DEBUG(dbgs() << "ARM Loops: Combining with VCMP to VPT: " << *MIB);
1603 LoLoop.BlockMasksToRecompute.insert(Ptr: MIB.getInstr());
1604 LoLoop.ToRemove.insert(Ptr: TheVCMP);
1605 TheVCMP = nullptr;
1606 };
1607
1608 if (LoLoop.VPTstate.isEntryPredicatedOnVCTP(Block, /*exclusive*/ Exclusive: true)) {
1609 MachineInstr *VPST = Insts.front();
1610 if (Block.hasUniformPredicate()) {
1611 // A vpt block starting with VPST, is only predicated upon vctp and has no
1612 // internal vpr defs:
1613 // - Remove vpst.
1614 // - Unpredicate the remaining instructions.
1615 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1616 for (unsigned i = 1; i < Insts.size(); ++i)
1617 RemovePredicate(Insts[i]);
1618 } else {
1619 // The VPT block has a non-uniform predicate but it uses a vpst and its
1620 // entry is guarded only by a vctp, which means we:
1621 // - Need to remove the original vpst.
1622 // - Then need to unpredicate any following instructions, until
1623 // we come across the divergent vpr def.
1624 // - Insert a new vpst to predicate the instruction(s) that following
1625 // the divergent vpr def.
1626 MachineInstr *Divergent = Block.getDivergent();
1627 MachineBasicBlock *MBB = Divergent->getParent();
1628 auto DivergentNext = ++MachineBasicBlock::iterator(Divergent);
1629 while (DivergentNext != MBB->end() && DivergentNext->isDebugInstr())
1630 ++DivergentNext;
1631
1632 bool DivergentNextIsPredicated =
1633 DivergentNext != MBB->end() &&
1634 getVPTInstrPredicate(MI: *DivergentNext) != ARMVCC::None;
1635
1636 for (auto I = ++MachineBasicBlock::iterator(VPST), E = DivergentNext;
1637 I != E; ++I)
1638 RemovePredicate(&*I);
1639
1640 // Check if the instruction defining vpr is a vcmp so it can be combined
1641 // with the VPST This should be the divergent instruction
1642 MachineInstr *VCMP =
1643 VCMPOpcodeToVPT(Opcode: Divergent->getOpcode()) != 0 ? Divergent : nullptr;
1644
1645 if (DivergentNextIsPredicated) {
1646 // Insert a VPST at the divergent only if the next instruction
1647 // would actually use it. A VCMP following a VPST can be
1648 // merged into a VPT so do that instead if the VCMP exists.
1649 if (!VCMP) {
1650 // Create a VPST (with a null mask for now, we'll recompute it
1651 // later)
1652 MachineInstrBuilder MIB =
1653 BuildMI(BB&: *Divergent->getParent(), I: Divergent,
1654 MIMD: Divergent->getDebugLoc(), MCID: TII->get(Opcode: ARM::MVE_VPST));
1655 MIB.addImm(Val: 0);
1656 LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
1657 LoLoop.BlockMasksToRecompute.insert(Ptr: MIB.getInstr());
1658 } else {
1659 // No RDI checks are necessary here since the VPST would have been
1660 // directly after the VCMP
1661 ReplaceVCMPWithVPT(VCMP, VCMP);
1662 }
1663 }
1664 }
1665 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1666 LoLoop.ToRemove.insert(Ptr: VPST);
1667 } else if (Block.containsVCTP()) {
1668 // The vctp will be removed, so either the entire block will be dead or
1669 // the block mask of the vp(s)t will need to be recomputed.
1670 MachineInstr *VPST = Insts.front();
1671 if (Block.size() == 2) {
1672 assert(VPST->getOpcode() == ARM::MVE_VPST &&
1673 "Found a VPST in an otherwise empty vpt block");
1674 LoLoop.ToRemove.insert(Ptr: VPST);
1675 } else
1676 LoLoop.BlockMasksToRecompute.insert(Ptr: VPST);
1677 } else if (Insts.front()->getOpcode() == ARM::MVE_VPST) {
1678 // If this block starts with a VPST then attempt to merge it with the
1679 // preceeding un-merged VCMP into a VPT. This VCMP comes from a VPT
1680 // block that no longer exists
1681 MachineInstr *VPST = Insts.front();
1682 auto Next = ++MachineBasicBlock::iterator(VPST);
1683 assert(getVPTInstrPredicate(*Next) != ARMVCC::None &&
1684 "The instruction after a VPST must be predicated");
1685 (void)Next;
1686 MachineInstr *VprDef = RDI->getUniqueReachingMIDef(MI: VPST, Reg: ARM::VPR);
1687 if (VprDef && VCMPOpcodeToVPT(Opcode: VprDef->getOpcode()) &&
1688 !LoLoop.ToRemove.contains(Ptr: VprDef)) {
1689 MachineInstr *VCMP = VprDef;
1690 // The VCMP and VPST can only be merged if the VCMP's operands will have
1691 // the same values at the VPST.
1692 // If any of the instructions between the VCMP and VPST are predicated
1693 // then a different code path is expected to have merged the VCMP and
1694 // VPST already.
1695 if (std::none_of(first: ++MachineBasicBlock::iterator(VCMP),
1696 last: MachineBasicBlock::iterator(VPST), pred: hasVPRUse) &&
1697 RDI->hasSameReachingDef(A: VCMP, B: VPST, Reg: VCMP->getOperand(i: 1).getReg()) &&
1698 RDI->hasSameReachingDef(A: VCMP, B: VPST, Reg: VCMP->getOperand(i: 2).getReg())) {
1699 ReplaceVCMPWithVPT(VCMP, VPST);
1700 LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *VPST);
1701 LoLoop.ToRemove.insert(Ptr: VPST);
1702 }
1703 }
1704 }
1705 }
1706
1707 LoLoop.ToRemove.insert_range(R&: LoLoop.VCTPs);
1708}
1709
1710void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
1711
1712 // Combine the LoopDec and LoopEnd instructions into LE(TP).
1713 auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
1714 MachineInstr *End = LoLoop.End;
1715 MachineBasicBlock *MBB = End->getParent();
1716 unsigned Opc = LoLoop.IsTailPredicationLegal() ?
1717 ARM::MVE_LETP : ARM::t2LEUpdate;
1718 MachineInstrBuilder MIB = BuildMI(BB&: *MBB, I: End, MIMD: End->getDebugLoc(),
1719 MCID: TII->get(Opcode: Opc));
1720 MIB.addDef(RegNo: ARM::LR);
1721 unsigned Off = LoLoop.Dec == LoLoop.End ? 1 : 0;
1722 MIB.add(MO: End->getOperand(i: Off + 0));
1723 MIB.add(MO: End->getOperand(i: Off + 1));
1724 LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
1725 LoLoop.ToRemove.insert(Ptr: LoLoop.Dec);
1726 LoLoop.ToRemove.insert(Ptr: End);
1727 return &*MIB;
1728 };
1729
1730 // TODO: We should be able to automatically remove these branches before we
1731 // get here - probably by teaching analyzeBranch about the pseudo
1732 // instructions.
1733 // If there is an unconditional branch, after I, that just branches to the
1734 // next block, remove it.
1735 auto RemoveDeadBranch = [](MachineInstr *I) {
1736 MachineBasicBlock *BB = I->getParent();
1737 MachineInstr *Terminator = &BB->instr_back();
1738 if (Terminator->isUnconditionalBranch() && I != Terminator) {
1739 MachineBasicBlock *Succ = Terminator->getOperand(i: 0).getMBB();
1740 if (BB->isLayoutSuccessor(MBB: Succ)) {
1741 LLVM_DEBUG(dbgs() << "ARM Loops: Removing branch: " << *Terminator);
1742 Terminator->eraseFromParent();
1743 }
1744 }
1745 };
1746
1747 // And VMOVCopies need to become 2xVMOVD for tail predication to be valid.
1748 // Anything other MQPRCopy can be converted to MVE_VORR later on.
1749 auto ExpandVMOVCopies = [this](SmallPtrSet<MachineInstr *, 4> &VMOVCopies) {
1750 for (auto *MI : VMOVCopies) {
1751 LLVM_DEBUG(dbgs() << "Converting copy to VMOVD: " << *MI);
1752 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1753 MachineBasicBlock *MBB = MI->getParent();
1754 Register Dst = MI->getOperand(i: 0).getReg();
1755 Register Src = MI->getOperand(i: 1).getReg();
1756 auto MIB1 = BuildMI(BB&: *MBB, I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode: ARM::VMOVD),
1757 DestReg: ARM::D0 + (Dst - ARM::Q0) * 2)
1758 .addReg(RegNo: ARM::D0 + (Src - ARM::Q0) * 2)
1759 .add(MOs: predOps(Pred: ARMCC::AL));
1760 (void)MIB1;
1761 LLVM_DEBUG(dbgs() << " into " << *MIB1);
1762 auto MIB2 = BuildMI(BB&: *MBB, I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode: ARM::VMOVD),
1763 DestReg: ARM::D0 + (Dst - ARM::Q0) * 2 + 1)
1764 .addReg(RegNo: ARM::D0 + (Src - ARM::Q0) * 2 + 1)
1765 .add(MOs: predOps(Pred: ARMCC::AL));
1766 LLVM_DEBUG(dbgs() << " and " << *MIB2);
1767 (void)MIB2;
1768 MI->eraseFromParent();
1769 }
1770 };
1771
1772 if (LoLoop.Revert) {
1773 if (isWhileLoopStart(MI: *LoLoop.Start))
1774 RevertWhile(MI: LoLoop.Start);
1775 else
1776 RevertDo(MI: LoLoop.Start);
1777 if (LoLoop.Dec == LoLoop.End)
1778 RevertLoopEndDec(MI: LoLoop.End);
1779 else
1780 RevertLoopEnd(MI: LoLoop.End, SkipCmp: RevertLoopDec(MI: LoLoop.Dec));
1781 } else {
1782 ExpandVMOVCopies(LoLoop.VMOVCopies);
1783 LoLoop.Start = ExpandLoopStart(LoLoop);
1784 if (LoLoop.Start)
1785 RemoveDeadBranch(LoLoop.Start);
1786 LoLoop.End = ExpandLoopEnd(LoLoop);
1787 RemoveDeadBranch(LoLoop.End);
1788 if (LoLoop.IsTailPredicationLegal())
1789 ConvertVPTBlocks(LoLoop);
1790 for (auto *I : LoLoop.ToRemove) {
1791 LLVM_DEBUG(dbgs() << "ARM Loops: Erasing " << *I);
1792 I->eraseFromParent();
1793 }
1794 for (auto *I : LoLoop.BlockMasksToRecompute) {
1795 LLVM_DEBUG(dbgs() << "ARM Loops: Recomputing VPT/VPST Block Mask: " << *I);
1796 recomputeVPTBlockMask(Instr&: *I);
1797 LLVM_DEBUG(dbgs() << " ... done: " << *I);
1798 }
1799 }
1800
1801 PostOrderLoopTraversal DFS(LoLoop.ML, *MLI);
1802 DFS.ProcessLoop();
1803 const SmallVectorImpl<MachineBasicBlock*> &PostOrder = DFS.getOrder();
1804 fullyRecomputeLiveIns(MBBs: PostOrder);
1805
1806 for (auto *MBB : reverse(C: PostOrder))
1807 recomputeLivenessFlags(MBB&: *MBB);
1808
1809 // We've moved, removed and inserted new instructions, so update RDI.
1810 RDI->reset();
1811}
1812
1813bool ARMLowOverheadLoops::RevertNonLoops() {
1814 LLVM_DEBUG(dbgs() << "ARM Loops: Reverting any remaining pseudos...\n");
1815 bool Changed = false;
1816
1817 for (auto &MBB : *MF) {
1818 SmallVector<MachineInstr*, 4> Starts;
1819 SmallVector<MachineInstr*, 4> Decs;
1820 SmallVector<MachineInstr*, 4> Ends;
1821 SmallVector<MachineInstr *, 4> EndDecs;
1822 SmallVector<MachineInstr *, 4> MQPRCopies;
1823
1824 for (auto &I : MBB) {
1825 if (isLoopStart(MI: I))
1826 Starts.push_back(Elt: &I);
1827 else if (I.getOpcode() == ARM::t2LoopDec)
1828 Decs.push_back(Elt: &I);
1829 else if (I.getOpcode() == ARM::t2LoopEnd)
1830 Ends.push_back(Elt: &I);
1831 else if (I.getOpcode() == ARM::t2LoopEndDec)
1832 EndDecs.push_back(Elt: &I);
1833 else if (I.getOpcode() == ARM::MQPRCopy)
1834 MQPRCopies.push_back(Elt: &I);
1835 }
1836
1837 if (Starts.empty() && Decs.empty() && Ends.empty() && EndDecs.empty() &&
1838 MQPRCopies.empty())
1839 continue;
1840
1841 Changed = true;
1842
1843 for (auto *Start : Starts) {
1844 if (isWhileLoopStart(MI: *Start))
1845 RevertWhile(MI: Start);
1846 else
1847 RevertDo(MI: Start);
1848 }
1849 for (auto *Dec : Decs)
1850 RevertLoopDec(MI: Dec);
1851
1852 for (auto *End : Ends)
1853 RevertLoopEnd(MI: End);
1854 for (auto *End : EndDecs)
1855 RevertLoopEndDec(MI: End);
1856 for (auto *MI : MQPRCopies) {
1857 LLVM_DEBUG(dbgs() << "Converting copy to VORR: " << *MI);
1858 assert(MI->getOpcode() == ARM::MQPRCopy && "Only expected MQPRCOPY!");
1859 MachineBasicBlock *MBB = MI->getParent();
1860 auto MIB = BuildMI(BB&: *MBB, I: MI, MIMD: MI->getDebugLoc(), MCID: TII->get(Opcode: ARM::MVE_VORR),
1861 DestReg: MI->getOperand(i: 0).getReg())
1862 .add(MO: MI->getOperand(i: 1))
1863 .add(MO: MI->getOperand(i: 1));
1864 addUnpredicatedMveVpredROp(MIB, DestReg: MI->getOperand(i: 0).getReg());
1865 MI->eraseFromParent();
1866 }
1867 }
1868 return Changed;
1869}
1870
1871FunctionPass *llvm::createARMLowOverheadLoopsPass() {
1872 return new ARMLowOverheadLoops();
1873}
1874