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