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