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