contrib/llvm-project/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

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