vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085

1 files changed, 736 insertions, 232 deletions

diff --git a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp
index e1c5a9c3e223..6717d4706aef 100644
--- a/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp
+++ b/llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp
@@ -15,6 +15,26 @@
 /// - t2LoopDec - placed within in the loop body.
 /// - t2LoopEnd - the loop latch terminator.
 ///
+/// In addition to this, we also look for the presence of the VCTP instruction,
+/// which determines whether we can generated the tail-predicated low-overhead
+/// loop form.
+///
+/// Assumptions and Dependencies:
+/// Low-overhead loops are constructed and executed using a setup instruction:
+/// DLS, WLS, DLSTP or WLSTP and an instruction that loops back: LE or LETP.
+/// WLS(TP) and LE(TP) are branching instructions with a (large) limited range
+/// but fixed polarity: WLS can only branch forwards and LE can only branch
+/// backwards. These restrictions mean that this pass is dependent upon block
+/// layout and block sizes, which is why it's the last pass to run. The same is
+/// true for ConstantIslands, but this pass does not increase the size of the
+/// basic blocks, nor does it change the CFG. Instructions are mainly removed
+/// during the transform and pseudo instructions are replaced by real ones. In
+/// some cases, when we have to revert to a 'normal' loop, we have to introduce
+/// multiple instructions for a single pseudo (see RevertWhile and
+/// RevertLoopEnd). To handle this situation, t2WhileLoopStart and t2LoopEnd
+/// are defined to be as large as this maximum sequence of replacement
+/// instructions.
+///
 //===----------------------------------------------------------------------===//
 
 #include "ARM.h"
@@ -22,9 +42,16 @@
 #include "ARMBaseRegisterInfo.h"
 #include "ARMBasicBlockInfo.h"
 #include "ARMSubtarget.h"
+#include "Thumb2InstrInfo.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
+#include "llvm/CodeGen/MachineLoopUtils.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/ReachingDefAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
 
 using namespace llvm;
 
@@ -33,10 +60,154 @@ using namespace llvm;
 
 namespace {
 
+  struct PredicatedMI {
+    MachineInstr *MI = nullptr;
+    SetVector<MachineInstr*> Predicates;
+
+  public:
+    PredicatedMI(MachineInstr *I, SetVector<MachineInstr*> &Preds) :
+    MI(I) {
+      Predicates.insert(Preds.begin(), Preds.end());
+    }
+  };
+
+  // Represent a VPT block, a list of instructions that begins with a VPST and
+  // has a maximum of four proceeding instructions. All instructions within the
+  // block are predicated upon the vpr and we allow instructions to define the
+  // vpr within in the block too.
+  class VPTBlock {
+    std::unique_ptr<PredicatedMI> VPST;
+    PredicatedMI *Divergent = nullptr;
+    SmallVector<PredicatedMI, 4> Insts;
+
+  public:
+    VPTBlock(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
+      VPST = std::make_unique<PredicatedMI>(MI, Preds);
+    }
+
+    void addInst(MachineInstr *MI, SetVector<MachineInstr*> &Preds) {
+      LLVM_DEBUG(dbgs() << "ARM Loops: Adding predicated MI: " << *MI);
+      if (!Divergent && !set_difference(Preds, VPST->Predicates).empty()) {
+        Divergent = &Insts.back();
+        LLVM_DEBUG(dbgs() << " - has divergent predicate: " << *Divergent->MI);
+      }
+      Insts.emplace_back(MI, Preds);
+      assert(Insts.size() <= 4 && "Too many instructions in VPT block!");
+    }
+
+    // Have we found an instruction within the block which defines the vpr? If
+    // so, not all the instructions in the block will have the same predicate.
+    bool HasNonUniformPredicate() const {
+      return Divergent != nullptr;
+    }
+
+    // Is the given instruction part of the predicate set controlling the entry
+    // to the block.
+    bool IsPredicatedOn(MachineInstr *MI) const {
+      return VPST->Predicates.count(MI);
+    }
+
+    // Is the given instruction the only predicate which controls the entry to
+    // the block.
+    bool IsOnlyPredicatedOn(MachineInstr *MI) const {
+      return IsPredicatedOn(MI) && VPST->Predicates.size() == 1;
+    }
+
+    unsigned size() const { return Insts.size(); }
+    SmallVectorImpl<PredicatedMI> &getInsts() { return Insts; }
+    MachineInstr *getVPST() const { return VPST->MI; }
+    PredicatedMI *getDivergent() const { return Divergent; }
+  };
+
+  struct LowOverheadLoop {
+
+    MachineLoop *ML = nullptr;
+    MachineFunction *MF = nullptr;
+    MachineInstr *InsertPt = nullptr;
+    MachineInstr *Start = nullptr;
+    MachineInstr *Dec = nullptr;
+    MachineInstr *End = nullptr;
+    MachineInstr *VCTP = nullptr;
+    VPTBlock *CurrentBlock = nullptr;
+    SetVector<MachineInstr*> CurrentPredicate;
+    SmallVector<VPTBlock, 4> VPTBlocks;
+    bool Revert = false;
+    bool CannotTailPredicate = false;
+
+    LowOverheadLoop(MachineLoop *ML) : ML(ML) {
+      MF = ML->getHeader()->getParent();
+    }
+
+    // If this is an MVE instruction, check that we know how to use tail
+    // predication with it. Record VPT blocks and return whether the
+    // instruction is valid for tail predication.
+    bool ValidateMVEInst(MachineInstr *MI);
+
+    void AnalyseMVEInst(MachineInstr *MI) {
+      CannotTailPredicate = !ValidateMVEInst(MI);
+    }
+
+    bool IsTailPredicationLegal() const {
+      // For now, let's keep things really simple and only support a single
+      // block for tail predication.
+      return !Revert && FoundAllComponents() && VCTP &&
+             !CannotTailPredicate && ML->getNumBlocks() == 1;
+    }
+
+    bool ValidateTailPredicate(MachineInstr *StartInsertPt,
+                               ReachingDefAnalysis *RDA,
+                               MachineLoopInfo *MLI);
+
+    // Is it safe to define LR with DLS/WLS?
+    // LR can be defined if it is the operand to start, because it's the same
+    // value, or if it's going to be equivalent to the operand to Start.
+    MachineInstr *IsSafeToDefineLR(ReachingDefAnalysis *RDA);
+
+    // Check the branch targets are within range and we satisfy our
+    // restrictions.
+    void CheckLegality(ARMBasicBlockUtils *BBUtils, ReachingDefAnalysis *RDA,
+                       MachineLoopInfo *MLI);
+
+    bool FoundAllComponents() const {
+      return Start && Dec && End;
+    }
+
+    SmallVectorImpl<VPTBlock> &getVPTBlocks() { return VPTBlocks; }
+
+    // Return the loop iteration count, or the number of elements if we're tail
+    // predicating.
+    MachineOperand &getCount() {
+      return IsTailPredicationLegal() ?
+        VCTP->getOperand(1) : Start->getOperand(0);
+    }
+
+    unsigned getStartOpcode() const {
+      bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
+      if (!IsTailPredicationLegal())
+        return IsDo ? ARM::t2DLS : ARM::t2WLS;
+
+      return VCTPOpcodeToLSTP(VCTP->getOpcode(), IsDo);
+    }
+
+    void dump() const {
+      if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
+      if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
+      if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;
+      if (VCTP) dbgs() << "ARM Loops: Found VCTP: " << *VCTP;
+      if (!FoundAllComponents())
+        dbgs() << "ARM Loops: Not a low-overhead loop.\n";
+      else if (!(Start && Dec && End))
+        dbgs() << "ARM Loops: Failed to find all loop components.\n";
+    }
+  };
+
   class ARMLowOverheadLoops : public MachineFunctionPass {
     MachineFunction           *MF = nullptr;
+    MachineLoopInfo           *MLI = nullptr;
+    ReachingDefAnalysis       *RDA = nullptr;
     const ARMBaseInstrInfo    *TII = nullptr;
     MachineRegisterInfo       *MRI = nullptr;
+    const TargetRegisterInfo  *TRI = nullptr;
     std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
 
   public:
@@ -47,6 +218,7 @@ namespace {
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<MachineLoopInfo>();
+      AU.addRequired<ReachingDefAnalysis>();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
@@ -54,7 +226,8 @@ namespace {
 
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
-          MachineFunctionProperties::Property::NoVRegs);
+          MachineFunctionProperties::Property::NoVRegs).set(
+          MachineFunctionProperties::Property::TracksLiveness);
     }
 
     StringRef getPassName() const override {
@@ -64,8 +237,6 @@ namespace {
   private:
     bool ProcessLoop(MachineLoop *ML);
 
-    MachineInstr * IsSafeToDefineLR(MachineInstr *MI);
-
     bool RevertNonLoops();
 
     void RevertWhile(MachineInstr *MI) const;
@@ -74,9 +245,13 @@ namespace {
 
     void RevertLoopEnd(MachineInstr *MI, bool SkipCmp = false) const;
 
-    void Expand(MachineLoop *ML, MachineInstr *Start,
-                MachineInstr *InsertPt, MachineInstr *Dec,
-                MachineInstr *End, bool Revert);
+    void RemoveLoopUpdate(LowOverheadLoop &LoLoop);
+
+    void ConvertVPTBlocks(LowOverheadLoop &LoLoop);
+
+    MachineInstr *ExpandLoopStart(LowOverheadLoop &LoLoop);
+
+    void Expand(LowOverheadLoop &LoLoop);
 
   };
 }
@@ -86,128 +261,321 @@ char ARMLowOverheadLoops::ID = 0;
 INITIALIZE_PASS(ARMLowOverheadLoops, DEBUG_TYPE, ARM_LOW_OVERHEAD_LOOPS_NAME,
                 false, false)
 
-bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
-  const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
-  if (!ST.hasLOB())
-    return false;
+MachineInstr *LowOverheadLoop::IsSafeToDefineLR(ReachingDefAnalysis *RDA) {
+  // We can define LR because LR already contains the same value.
+  if (Start->getOperand(0).getReg() == ARM::LR)
+    return Start;
 
-  MF = &mf;
-  LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
+  unsigned CountReg = Start->getOperand(0).getReg();
+  auto IsMoveLR = [&CountReg](MachineInstr *MI) {
+    return MI->getOpcode() == ARM::tMOVr &&
+           MI->getOperand(0).getReg() == ARM::LR &&
+           MI->getOperand(1).getReg() == CountReg &&
+           MI->getOperand(2).getImm() == ARMCC::AL;
+   };
 
-  auto &MLI = getAnalysis<MachineLoopInfo>();
-  MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
-  MRI = &MF->getRegInfo();
-  TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
-  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
-  BBUtils->computeAllBlockSizes();
-  BBUtils->adjustBBOffsetsAfter(&MF->front());
+  MachineBasicBlock *MBB = Start->getParent();
 
-  bool Changed = false;
-  for (auto ML : MLI) {
-    if (!ML->getParentLoop())
-      Changed |= ProcessLoop(ML);
-  }
-  Changed |= RevertNonLoops();
-  return Changed;
+  // Find an insertion point:
+  // - Is there a (mov lr, Count) before Start? If so, and nothing else writes
+  //   to Count before Start, we can insert at that mov.
+  if (auto *LRDef = RDA->getReachingMIDef(Start, ARM::LR))
+    if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
+      return LRDef;
+
+  // - Is there a (mov lr, Count) after Start? If so, and nothing else writes
+  //   to Count after Start, we can insert at that mov.
+  if (auto *LRDef = RDA->getLocalLiveOutMIDef(MBB, ARM::LR))
+    if (IsMoveLR(LRDef) && RDA->hasSameReachingDef(Start, LRDef, CountReg))
+      return LRDef;
+
+  // We've found no suitable LR def and Start doesn't use LR directly. Can we
+  // just define LR anyway?
+  if (!RDA->isRegUsedAfter(Start, ARM::LR))
+    return Start;
+
+  return nullptr;
 }
 
-static bool IsLoopStart(MachineInstr &MI) {
-  return MI.getOpcode() == ARM::t2DoLoopStart ||
-         MI.getOpcode() == ARM::t2WhileLoopStart;
+// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
+// not define a register that is used by any instructions, after and including,
+// 'To'. These instructions also must not redefine any of Froms operands.
+template<typename Iterator>
+static bool IsSafeToMove(MachineInstr *From, MachineInstr *To, ReachingDefAnalysis *RDA) {
+  SmallSet<int, 2> Defs;
+  // First check that From would compute the same value if moved.
+  for (auto &MO : From->operands()) {
+    if (!MO.isReg() || MO.isUndef() || !MO.getReg())
+      continue;
+    if (MO.isDef())
+      Defs.insert(MO.getReg());
+    else if (!RDA->hasSameReachingDef(From, To, MO.getReg()))
+      return false;
+  }
+
+  // Now walk checking that the rest of the instructions will compute the same
+  // value.
+  for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
+    for (auto &MO : I->operands())
+      if (MO.isReg() && MO.getReg() && MO.isUse() && Defs.count(MO.getReg()))
+        return false;
+  }
+  return true;
 }
 
-template<typename T>
-static MachineInstr* SearchForDef(MachineInstr *Begin, T End, unsigned Reg) {
-  for(auto &MI : make_range(T(Begin), End)) {
-    for (auto &MO : MI.operands()) {
-      if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg)
+bool LowOverheadLoop::ValidateTailPredicate(MachineInstr *StartInsertPt,
+    ReachingDefAnalysis *RDA, MachineLoopInfo *MLI) {
+  assert(VCTP && "VCTP instruction expected but is not set");
+  // All predication within the loop should be based on vctp. If the block
+  // isn't predicated on entry, check whether the vctp is within the block
+  // and that all other instructions are then predicated on it.
+  for (auto &Block : VPTBlocks) {
+    if (Block.IsPredicatedOn(VCTP))
+      continue;
+    if (!Block.HasNonUniformPredicate() || !isVCTP(Block.getDivergent()->MI)) {
+      LLVM_DEBUG(dbgs() << "ARM Loops: Found unsupported diverging predicate: "
+                 << *Block.getDivergent()->MI);
+      return false;
+    }
+    SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
+    for (auto &PredMI : Insts) {
+      if (PredMI.Predicates.count(VCTP) || isVCTP(PredMI.MI))
         continue;
-      return &MI;
+      LLVM_DEBUG(dbgs() << "ARM Loops: Can't convert: " << *PredMI.MI
+                        << " - which is predicated on:\n";
+                        for (auto *MI : PredMI.Predicates)
+                          dbgs() << "   - " << *MI;
+                 );
+      return false;
     }
   }
-  return nullptr;
-}
 
-static MachineInstr* SearchForUse(MachineInstr *Begin,
-                                  MachineBasicBlock::iterator End,
-                                  unsigned Reg) {
-  for(auto &MI : make_range(MachineBasicBlock::iterator(Begin), End)) {
-    for (auto &MO : MI.operands()) {
-      if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg)
-        continue;
-      return &MI;
+  // For tail predication, we need to provide the number of elements, instead
+  // of the iteration count, to the loop start instruction. The number of
+  // elements is provided to the vctp instruction, so we need to check that
+  // we can use this register at InsertPt.
+  Register NumElements = VCTP->getOperand(1).getReg();
+
+  // If the register is defined within loop, then we can't perform TP.
+  // TODO: Check whether this is just a mov of a register that would be
+  // available.
+  if (RDA->getReachingDef(VCTP, NumElements) >= 0) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: VCTP operand is defined in the loop.\n");
+    return false;
+  }
+
+  // The element count register maybe defined after InsertPt, in which case we
+  // need to try to move either InsertPt or the def so that the [w|d]lstp can
+  // use the value.
+  MachineBasicBlock *InsertBB = InsertPt->getParent();
+  if (!RDA->isReachingDefLiveOut(InsertPt, NumElements)) {
+    if (auto *ElemDef = RDA->getLocalLiveOutMIDef(InsertBB, NumElements)) {
+      if (IsSafeToMove<MachineBasicBlock::reverse_iterator>(ElemDef, InsertPt, RDA)) {
+        ElemDef->removeFromParent();
+        InsertBB->insert(MachineBasicBlock::iterator(InsertPt), ElemDef);
+        LLVM_DEBUG(dbgs() << "ARM Loops: Moved element count def: "
+                   << *ElemDef);
+      } else if (IsSafeToMove<MachineBasicBlock::iterator>(InsertPt, ElemDef, RDA)) {
+        InsertPt->removeFromParent();
+        InsertBB->insertAfter(MachineBasicBlock::iterator(ElemDef), InsertPt);
+        LLVM_DEBUG(dbgs() << "ARM Loops: Moved start past: " << *ElemDef);
+      } else {
+        LLVM_DEBUG(dbgs() << "ARM Loops: Unable to move element count to loop "
+                   << "start instruction.\n");
+        return false;
+      }
     }
   }
-  return nullptr;
+
+  // Especially in the case of while loops, InsertBB may not be the
+  // preheader, so we need to check that the register isn't redefined
+  // before entering the loop.
+  auto CannotProvideElements = [&RDA](MachineBasicBlock *MBB,
+                                      Register NumElements) {
+    // NumElements is redefined in this block.
+    if (RDA->getReachingDef(&MBB->back(), NumElements) >= 0)
+      return true;
+
+    // Don't continue searching up through multiple predecessors.
+    if (MBB->pred_size() > 1)
+      return true;
+
+    return false;
+  };
+
+  // First, find the block that looks like the preheader.
+  MachineBasicBlock *MBB = MLI->findLoopPreheader(ML, true);
+  if (!MBB) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find preheader.\n");
+    return false;
+  }
+
+  // Then search backwards for a def, until we get to InsertBB.
+  while (MBB != InsertBB) {
+    if (CannotProvideElements(MBB, NumElements)) {
+      LLVM_DEBUG(dbgs() << "ARM Loops: Unable to provide element count.\n");
+      return false;
+    }
+    MBB = *MBB->pred_begin();
+  }
+
+  LLVM_DEBUG(dbgs() << "ARM Loops: Will use tail predication.\n");
+  return true;
 }
 
-// Is it safe to define LR with DLS/WLS?
-// LR can defined if it is the operand to start, because it's the same value,
-// or if it's going to be equivalent to the operand to Start.
-MachineInstr *ARMLowOverheadLoops::IsSafeToDefineLR(MachineInstr *Start) {
+void LowOverheadLoop::CheckLegality(ARMBasicBlockUtils *BBUtils,
+                                    ReachingDefAnalysis *RDA,
+                                    MachineLoopInfo *MLI) {
+  if (Revert)
+    return;
 
-  auto IsMoveLR = [](MachineInstr *MI, unsigned Reg) {
-    return MI->getOpcode() == ARM::tMOVr &&
-           MI->getOperand(0).getReg() == ARM::LR &&
-           MI->getOperand(1).getReg() == Reg &&
-           MI->getOperand(2).getImm() == ARMCC::AL;
-   };
+  if (!End->getOperand(1).isMBB())
+    report_fatal_error("Expected LoopEnd to target basic block");
 
-  MachineBasicBlock *MBB = Start->getParent();
-  unsigned CountReg = Start->getOperand(0).getReg();
-  // Walk forward and backward in the block to find the closest instructions
-  // that define LR. Then also filter them out if they're not a mov lr.
-  MachineInstr *PredLRDef = SearchForDef(Start, MBB->rend(), ARM::LR);
-  if (PredLRDef && !IsMoveLR(PredLRDef, CountReg))
-    PredLRDef = nullptr;
-
-  MachineInstr *SuccLRDef = SearchForDef(Start, MBB->end(), ARM::LR);
-  if (SuccLRDef && !IsMoveLR(SuccLRDef, CountReg))
-    SuccLRDef = nullptr;
-
-  // We've either found one, two or none mov lr instructions... Now figure out
-  // if they are performing the equilvant mov that the Start instruction will.
-  // Do this by scanning forward and backward to see if there's a def of the
-  // register holding the count value. If we find a suitable def, return it as
-  // the insert point. Later, if InsertPt != Start, then we can remove the
-  // redundant instruction.
-  if (SuccLRDef) {
-    MachineBasicBlock::iterator End(SuccLRDef);
-    if (!SearchForDef(Start, End, CountReg)) {
-      return SuccLRDef;
-    } else
-      SuccLRDef = nullptr;
+  // TODO Maybe there's cases where the target doesn't have to be the header,
+  // but for now be safe and revert.
+  if (End->getOperand(1).getMBB() != ML->getHeader()) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n");
+    Revert = true;
+    return;
   }
-  if (PredLRDef) {
-    MachineBasicBlock::reverse_iterator End(PredLRDef);
-    if (!SearchForDef(Start, End, CountReg)) {
-      return PredLRDef;
-    } else
-      PredLRDef = nullptr;
+
+  // The WLS and LE instructions have 12-bits for the label offset. WLS
+  // requires a positive offset, while LE uses negative.
+  if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) ||
+      !BBUtils->isBBInRange(End, ML->getHeader(), 4094)) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
+    Revert = true;
+    return;
   }
 
-  // We can define LR because LR already contains the same value.
-  if (Start->getOperand(0).getReg() == ARM::LR)
-    return Start;
+  if (Start->getOpcode() == ARM::t2WhileLoopStart &&
+      (BBUtils->getOffsetOf(Start) >
+       BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
+       !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
+    Revert = true;
+    return;
+  }
 
-  // We've found no suitable LR def and Start doesn't use LR directly. Can we
-  // just define LR anyway? 
-  const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
-  LivePhysRegs LiveRegs(*TRI);
-  LiveRegs.addLiveOuts(*MBB);
+  InsertPt = Revert ? nullptr : IsSafeToDefineLR(RDA);
+  if (!InsertPt) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
+    Revert = true;
+    return;
+  } else
+    LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
 
-  // Not if we've haven't found a suitable mov and LR is live out.
-  if (LiveRegs.contains(ARM::LR))
-    return nullptr;
+  if (!IsTailPredicationLegal()) {
+    LLVM_DEBUG(if (!VCTP)
+                 dbgs() << "ARM Loops: Didn't find a VCTP instruction.\n";
+               dbgs() << "ARM Loops: Tail-predication is not valid.\n");
+    return;
+  }
 
-  // If LR is not live out, we can insert the instruction if nothing else
-  // uses LR after it.
-  if (!SearchForUse(Start, MBB->end(), ARM::LR))
-    return Start;
+  assert(ML->getBlocks().size() == 1 &&
+         "Shouldn't be processing a loop with more than one block");
+  CannotTailPredicate = !ValidateTailPredicate(InsertPt, RDA, MLI);
+  LLVM_DEBUG(if (CannotTailPredicate)
+             dbgs() << "ARM Loops: Couldn't validate tail predicate.\n");
+}
 
-  LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find suitable insertion point for"
-             << " LR\n");
-  return nullptr;
+bool LowOverheadLoop::ValidateMVEInst(MachineInstr* MI) {
+  if (CannotTailPredicate)
+    return false;
+
+  // Only support a single vctp.
+  if (isVCTP(MI) && VCTP)
+    return false;
+
+  // Start a new vpt block when we discover a vpt.
+  if (MI->getOpcode() == ARM::MVE_VPST) {
+    VPTBlocks.emplace_back(MI, CurrentPredicate);
+    CurrentBlock = &VPTBlocks.back();
+    return true;
+  } else if (isVCTP(MI))
+    VCTP = MI;
+  else if (MI->getOpcode() == ARM::MVE_VPSEL ||
+           MI->getOpcode() == ARM::MVE_VPNOT)
+    return false;
+
+  // TODO: Allow VPSEL and VPNOT, we currently cannot because:
+  // 1) It will use the VPR as a predicate operand, but doesn't have to be
+  //    instead a VPT block, which means we can assert while building up
+  //    the VPT block because we don't find another VPST to being a new
+  //    one.
+  // 2) VPSEL still requires a VPR operand even after tail predicating,
+  //    which means we can't remove it unless there is another
+  //    instruction, such as vcmp, that can provide the VPR def.
+
+  bool IsUse = false;
+  bool IsDef = false;
+  const MCInstrDesc &MCID = MI->getDesc();
+  for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
+    const MachineOperand &MO = MI->getOperand(i);
+    if (!MO.isReg() || MO.getReg() != ARM::VPR)
+      continue;
+
+    if (MO.isDef()) {
+      CurrentPredicate.insert(MI);
+      IsDef = true;
+    } else if (ARM::isVpred(MCID.OpInfo[i].OperandType)) {
+      CurrentBlock->addInst(MI, CurrentPredicate);
+      IsUse = true;
+    } else {
+      LLVM_DEBUG(dbgs() << "ARM Loops: Found instruction using vpr: " << *MI);
+      return false;
+    }
+  }
+
+  // If we find a vpr def that is not already predicated on the vctp, we've
+  // got disjoint predicates that may not be equivalent when we do the
+  // conversion.
+  if (IsDef && !IsUse && VCTP && !isVCTP(MI)) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Found disjoint vpr def: " << *MI);
+    return false;
+  }
+
+  uint64_t Flags = MCID.TSFlags;
+  if ((Flags & ARMII::DomainMask) != ARMII::DomainMVE)
+    return true;
+
+  // If we find an instruction that has been marked as not valid for tail
+  // predication, only allow the instruction if it's contained within a valid
+  // VPT block.
+  if ((Flags & ARMII::ValidForTailPredication) == 0 && !IsUse) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Can't tail predicate: " << *MI);
+    return false;
+  }
+
+  return true;
+}
+
+bool ARMLowOverheadLoops::runOnMachineFunction(MachineFunction &mf) {
+  const ARMSubtarget &ST = static_cast<const ARMSubtarget&>(mf.getSubtarget());
+  if (!ST.hasLOB())
+    return false;
+
+  MF = &mf;
+  LLVM_DEBUG(dbgs() << "ARM Loops on " << MF->getName() << " ------------- \n");
+
+  MLI = &getAnalysis<MachineLoopInfo>();
+  RDA = &getAnalysis<ReachingDefAnalysis>();
+  MF->getProperties().set(MachineFunctionProperties::Property::TracksLiveness);
+  MRI = &MF->getRegInfo();
+  TII = static_cast<const ARMBaseInstrInfo*>(ST.getInstrInfo());
+  TRI = ST.getRegisterInfo();
+  BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(*MF));
+  BBUtils->computeAllBlockSizes();
+  BBUtils->adjustBBOffsetsAfter(&MF->front());
+
+  bool Changed = false;
+  for (auto ML : *MLI) {
+    if (!ML->getParentLoop())
+      Changed |= ProcessLoop(ML);
+  }
+  Changed |= RevertNonLoops();
+  return Changed;
 }
 
 bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
@@ -218,14 +586,21 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
   for (auto I = ML->begin(), E = ML->end(); I != E; ++I)
     Changed |= ProcessLoop(*I);
 
-  LLVM_DEBUG(dbgs() << "ARM Loops: Processing " << *ML);
+  LLVM_DEBUG(dbgs() << "ARM Loops: Processing loop containing:\n";
+             if (auto *Preheader = ML->getLoopPreheader())
+               dbgs() << " - " << Preheader->getName() << "\n";
+             else if (auto *Preheader = MLI->findLoopPreheader(ML))
+               dbgs() << " - " << Preheader->getName() << "\n";
+             for (auto *MBB : ML->getBlocks())
+               dbgs() << " - " << MBB->getName() << "\n";
+            );
 
   // Search the given block for a loop start instruction. If one isn't found,
   // and there's only one predecessor block, search that one too.
   std::function<MachineInstr*(MachineBasicBlock*)> SearchForStart =
     [&SearchForStart](MachineBasicBlock *MBB) -> MachineInstr* {
     for (auto &MI : *MBB) {
-      if (IsLoopStart(MI))
+      if (isLoopStart(MI))
         return &MI;
     }
     if (MBB->pred_size() == 1)
@@ -233,53 +608,43 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
     return nullptr;
   };
 
-  MachineInstr *Start = nullptr;
-  MachineInstr *Dec = nullptr;
-  MachineInstr *End = nullptr;
-  bool Revert = false;
-
-  // Search the preheader for the start intrinsic, or look through the
-  // predecessors of the header to find exactly one set.iterations intrinsic.
+  LowOverheadLoop LoLoop(ML);
+  // Search the preheader for the start intrinsic.
   // FIXME: I don't see why we shouldn't be supporting multiple predecessors
   // with potentially multiple set.loop.iterations, so we need to enable this.
-  if (auto *Preheader = ML->getLoopPreheader()) {
-    Start = SearchForStart(Preheader);
-  } else {
-    LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find loop preheader!\n"
-               << " - Performing manual predecessor search.\n");
-    MachineBasicBlock *Pred = nullptr;
-    for (auto *MBB : ML->getHeader()->predecessors()) {
-      if (!ML->contains(MBB)) {
-        if (Pred) {
-          LLVM_DEBUG(dbgs() << " - Found multiple out-of-loop preds.\n");
-          Start = nullptr;
-          break;
-        }
-        Pred = MBB;
-        Start = SearchForStart(MBB);
-      }
-    }
-  }
+  if (auto *Preheader = ML->getLoopPreheader())
+    LoLoop.Start = SearchForStart(Preheader);
+  else if (auto *Preheader = MLI->findLoopPreheader(ML, true))
+    LoLoop.Start = SearchForStart(Preheader);
+  else
+    return false;
 
   // Find the low-overhead loop components and decide whether or not to fall
-  // back to a normal loop.
+  // back to a normal loop. Also look for a vctp instructions and decide
+  // whether we can convert that predicate using tail predication.
   for (auto *MBB : reverse(ML->getBlocks())) {
     for (auto &MI : *MBB) {
       if (MI.getOpcode() == ARM::t2LoopDec)
-        Dec = &MI;
+        LoLoop.Dec = &MI;
       else if (MI.getOpcode() == ARM::t2LoopEnd)
-        End = &MI;
-      else if (IsLoopStart(MI))
-        Start = &MI;
+        LoLoop.End = &MI;
+      else if (isLoopStart(MI))
+        LoLoop.Start = &MI;
       else if (MI.getDesc().isCall()) {
         // TODO: Though the call will require LE to execute again, does this
         // mean we should revert? Always executing LE hopefully should be
         // faster than performing a sub,cmp,br or even subs,br.
-        Revert = true;
+        LoLoop.Revert = true;
         LLVM_DEBUG(dbgs() << "ARM Loops: Found call.\n");
+      } else {
+        // Record VPR defs and build up their corresponding vpt blocks.
+        // Check we know how to tail predicate any mve instructions.
+        LoLoop.AnalyseMVEInst(&MI);
       }
 
-      if (!Dec || End)
+      // We need to ensure that LR is not used or defined inbetween LoopDec and
+      // LoopEnd.
+      if (!LoLoop.Dec || LoLoop.End || LoLoop.Revert)
         continue;
 
       // If we find that LR has been written or read between LoopDec and
@@ -294,61 +659,21 @@ bool ARMLowOverheadLoops::ProcessLoop(MachineLoop *ML) {
         if (MI.getOpcode() != ARM::t2LoopDec && MO.isReg() &&
             MO.getReg() == ARM::LR) {
           LLVM_DEBUG(dbgs() << "ARM Loops: Found LR Use/Def: " << MI);
-          Revert = true;
+          LoLoop.Revert = true;
           break;
         }
       }
     }
-
-    if (Dec && End && Revert)
-      break;
   }
 
-  LLVM_DEBUG(if (Start) dbgs() << "ARM Loops: Found Loop Start: " << *Start;
-             if (Dec) dbgs() << "ARM Loops: Found Loop Dec: " << *Dec;
-             if (End) dbgs() << "ARM Loops: Found Loop End: " << *End;);
-
-  if (!Start && !Dec && !End) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: Not a low-overhead loop.\n");
-    return Changed;
-  } else if (!(Start && Dec && End)) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: Failed to find all loop components.\n");
+  LLVM_DEBUG(LoLoop.dump());
+  if (!LoLoop.FoundAllComponents()) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Didn't find loop start, update, end\n");
     return false;
   }
 
-  if (!End->getOperand(1).isMBB())
-    report_fatal_error("Expected LoopEnd to target basic block");
-
-  // TODO Maybe there's cases where the target doesn't have to be the header,
-  // but for now be safe and revert.
-  if (End->getOperand(1).getMBB() != ML->getHeader()) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: LoopEnd is not targetting header.\n");
-    Revert = true;
-  }
-
-  // The WLS and LE instructions have 12-bits for the label offset. WLS
-  // requires a positive offset, while LE uses negative.
-  if (BBUtils->getOffsetOf(End) < BBUtils->getOffsetOf(ML->getHeader()) ||
-      !BBUtils->isBBInRange(End, ML->getHeader(), 4094)) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: LE offset is out-of-range\n");
-    Revert = true;
-  }
-  if (Start->getOpcode() == ARM::t2WhileLoopStart &&
-      (BBUtils->getOffsetOf(Start) >
-       BBUtils->getOffsetOf(Start->getOperand(1).getMBB()) ||
-       !BBUtils->isBBInRange(Start, Start->getOperand(1).getMBB(), 4094))) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: WLS offset is out-of-range!\n");
-    Revert = true;
-  }
-
-  MachineInstr *InsertPt = Revert ? nullptr : IsSafeToDefineLR(Start);
-  if (!InsertPt) {
-    LLVM_DEBUG(dbgs() << "ARM Loops: Unable to find safe insertion point.\n");
-    Revert = true;
-  } else
-    LLVM_DEBUG(dbgs() << "ARM Loops: Start insertion point: " << *InsertPt);
-
-  Expand(ML, Start, InsertPt, Dec, End, Revert);
+  LoLoop.CheckLegality(BBUtils.get(), RDA, MLI);
+  Expand(LoLoop);
   return true;
 }
 
@@ -365,7 +690,7 @@ void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
   MIB.addImm(0);
   MIB.addImm(ARMCC::AL);
   MIB.addReg(ARM::NoRegister);
-  
+
   MachineBasicBlock *DestBB = MI->getOperand(1).getMBB();
   unsigned BrOpc = BBUtils->isBBInRange(MI, DestBB, 254) ?
     ARM::tBcc : ARM::t2Bcc;
@@ -378,19 +703,15 @@ void ARMLowOverheadLoops::RevertWhile(MachineInstr *MI) const {
 }
 
 bool ARMLowOverheadLoops::RevertLoopDec(MachineInstr *MI,
-                                        bool AllowFlags) const {
+                                        bool SetFlags) const {
   LLVM_DEBUG(dbgs() << "ARM Loops: Reverting to sub: " << *MI);
   MachineBasicBlock *MBB = MI->getParent();
 
-  // If nothing uses or defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
-  bool SetFlags = false;
-  if (AllowFlags) {
-    if (auto *Def = SearchForDef(MI, MBB->end(), ARM::CPSR)) {
-      if (!SearchForUse(MI, MBB->end(), ARM::CPSR) &&
-          Def->getOpcode() == ARM::t2LoopEnd)
-        SetFlags = true;
-    }
-  }
+  // If nothing defines CPSR between LoopDec and LoopEnd, use a t2SUBS.
+  if (SetFlags &&
+      (RDA->isRegUsedAfter(MI, ARM::CPSR) ||
+       !RDA->hasSameReachingDef(MI, &MBB->back(), ARM::CPSR)))
+      SetFlags = false;
 
   MachineInstrBuilder MIB = BuildMI(*MBB, MI, MI->getDebugLoc(),
                                     TII->get(ARM::t2SUBri));
@@ -438,44 +759,223 @@ void ARMLowOverheadLoops::RevertLoopEnd(MachineInstr *MI, bool SkipCmp) const {
   MI->eraseFromParent();
 }
 
-void ARMLowOverheadLoops::Expand(MachineLoop *ML, MachineInstr *Start,
-                                 MachineInstr *InsertPt,
-                                 MachineInstr *Dec, MachineInstr *End,
-                                 bool Revert) {
+MachineInstr* ARMLowOverheadLoops::ExpandLoopStart(LowOverheadLoop &LoLoop) {
+  MachineInstr *InsertPt = LoLoop.InsertPt;
+  MachineInstr *Start = LoLoop.Start;
+  MachineBasicBlock *MBB = InsertPt->getParent();
+  bool IsDo = Start->getOpcode() == ARM::t2DoLoopStart;
+  unsigned Opc = LoLoop.getStartOpcode();
+  MachineOperand &Count = LoLoop.getCount();
 
-  auto ExpandLoopStart = [this](MachineLoop *ML, MachineInstr *Start,
-                                MachineInstr *InsertPt) {
-    MachineBasicBlock *MBB = InsertPt->getParent();
-    unsigned Opc = Start->getOpcode() == ARM::t2DoLoopStart ?
-      ARM::t2DLS : ARM::t2WLS;
-    MachineInstrBuilder MIB =
-      BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));
+  MachineInstrBuilder MIB =
+    BuildMI(*MBB, InsertPt, InsertPt->getDebugLoc(), TII->get(Opc));
 
-    MIB.addDef(ARM::LR);
-    MIB.add(Start->getOperand(0));
-    if (Opc == ARM::t2WLS)
-      MIB.add(Start->getOperand(1));
-
-    if (InsertPt != Start)
-      InsertPt->eraseFromParent();
-    Start->eraseFromParent();
-    LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
-    return &*MIB;
+  MIB.addDef(ARM::LR);
+  MIB.add(Count);
+  if (!IsDo)
+    MIB.add(Start->getOperand(1));
+
+  // When using tail-predication, try to delete the dead code that was used to
+  // calculate the number of loop iterations.
+  if (LoLoop.IsTailPredicationLegal()) {
+    SmallVector<MachineInstr*, 4> Killed;
+    SmallVector<MachineInstr*, 4> Dead;
+    if (auto *Def = RDA->getReachingMIDef(Start,
+                                          Start->getOperand(0).getReg())) {
+      Killed.push_back(Def);
+
+      while (!Killed.empty()) {
+        MachineInstr *Def = Killed.back();
+        Killed.pop_back();
+        Dead.push_back(Def);
+        for (auto &MO : Def->operands()) {
+          if (!MO.isReg() || !MO.isKill())
+            continue;
+
+          MachineInstr *Kill = RDA->getReachingMIDef(Def, MO.getReg());
+          if (Kill && RDA->getNumUses(Kill, MO.getReg()) == 1)
+            Killed.push_back(Kill);
+        }
+      }
+      for (auto *MI : Dead)
+        MI->eraseFromParent();
+    }
+  }
+
+  // If we're inserting at a mov lr, then remove it as it's redundant.
+  if (InsertPt != Start)
+    InsertPt->eraseFromParent();
+  Start->eraseFromParent();
+  LLVM_DEBUG(dbgs() << "ARM Loops: Inserted start: " << *MIB);
+  return &*MIB;
+}
+
+// Goal is to optimise and clean-up these loops:
+//
+//   vector.body:
+//     renamable $vpr = MVE_VCTP32 renamable $r3, 0, $noreg
+//     renamable $r3, dead $cpsr = tSUBi8 killed renamable $r3(tied-def 0), 4
+//     ..
+//     $lr = MVE_DLSTP_32 renamable $r3
+//
+// The SUB is the old update of the loop iteration count expression, which
+// is no longer needed. This sub is removed when the element count, which is in
+// r3 in this example, is defined by an instruction in the loop, and it has
+// no uses.
+//
+void ARMLowOverheadLoops::RemoveLoopUpdate(LowOverheadLoop &LoLoop) {
+  Register ElemCount = LoLoop.VCTP->getOperand(1).getReg();
+  MachineInstr *LastInstrInBlock = &LoLoop.VCTP->getParent()->back();
+
+  LLVM_DEBUG(dbgs() << "ARM Loops: Trying to remove loop update stmt\n");
+
+  if (LoLoop.ML->getNumBlocks() != 1) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Single block loop expected\n");
+    return;
+  }
+
+  LLVM_DEBUG(dbgs() << "ARM Loops: Analyzing elemcount in operand: ";
+             LoLoop.VCTP->getOperand(1).dump());
+
+  // Find the definition we are interested in removing, if there is one.
+  MachineInstr *Def = RDA->getReachingMIDef(LastInstrInBlock, ElemCount);
+  if (!Def) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Can't find a def, nothing to do.\n");
+    return;
+  }
+
+  // Bail if we define CPSR and it is not dead
+  if (!Def->registerDefIsDead(ARM::CPSR, TRI)) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: CPSR is not dead\n");
+    return;
+  }
+
+  // Bail if elemcount is used in exit blocks, i.e. if it is live-in.
+  if (isRegLiveInExitBlocks(LoLoop.ML, ElemCount)) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Elemcount is live-out, can't remove stmt\n");
+    return;
+  }
+
+  // Bail if there are uses after this Def in the block.
+  SmallVector<MachineInstr*, 4> Uses;
+  RDA->getReachingLocalUses(Def, ElemCount, Uses);
+  if (Uses.size()) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Local uses in block, can't remove stmt\n");
+    return;
+  }
+
+  Uses.clear();
+  RDA->getAllInstWithUseBefore(Def, ElemCount, Uses);
+
+  // Remove Def if there are no uses, or if the only use is the VCTP
+  // instruction.
+  if (!Uses.size() || (Uses.size() == 1 && Uses[0] == LoLoop.VCTP)) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Removing loop update instruction: ";
+               Def->dump());
+    Def->eraseFromParent();
+    return;
+  }
+
+  LLVM_DEBUG(dbgs() << "ARM Loops: Can't remove loop update, it's used by:\n";
+             for (auto U : Uses) U->dump());
+}
+
+void ARMLowOverheadLoops::ConvertVPTBlocks(LowOverheadLoop &LoLoop) {
+  auto RemovePredicate = [](MachineInstr *MI) {
+    LLVM_DEBUG(dbgs() << "ARM Loops: Removing predicate from: " << *MI);
+    if (int PIdx = llvm::findFirstVPTPredOperandIdx(*MI)) {
+      assert(MI->getOperand(PIdx).getImm() == ARMVCC::Then &&
+             "Expected Then predicate!");
+      MI->getOperand(PIdx).setImm(ARMVCC::None);
+      MI->getOperand(PIdx+1).setReg(0);
+    } else
+      llvm_unreachable("trying to unpredicate a non-predicated instruction");
   };
 
+  // There are a few scenarios which we have to fix up:
+  // 1) A VPT block with is only predicated by the vctp and has no internal vpr
+  //    defs.
+  // 2) A VPT block which is only predicated by the vctp but has an internal
+  //    vpr def.
+  // 3) A VPT block which is predicated upon the vctp as well as another vpr
+  //    def.
+  // 4) A VPT block which is not predicated upon a vctp, but contains it and
+  //    all instructions within the block are predicated upon in.
+
+  for (auto &Block : LoLoop.getVPTBlocks()) {
+    SmallVectorImpl<PredicatedMI> &Insts = Block.getInsts();
+    if (Block.HasNonUniformPredicate()) {
+      PredicatedMI *Divergent = Block.getDivergent();
+      if (isVCTP(Divergent->MI)) {
+        // The vctp will be removed, so the size of the vpt block needs to be
+        // modified.
+        uint64_t Size = getARMVPTBlockMask(Block.size() - 1);
+        Block.getVPST()->getOperand(0).setImm(Size);
+        LLVM_DEBUG(dbgs() << "ARM Loops: Modified VPT block mask.\n");
+      } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
+        // The VPT block has a non-uniform predicate but it's entry is guarded
+        // only by a vctp, which means we:
+        // - Need to remove the original vpst.
+        // - Then need to unpredicate any following instructions, until
+        //   we come across the divergent vpr def.
+        // - Insert a new vpst to predicate the instruction(s) that following
+        //   the divergent vpr def.
+        // TODO: We could be producing more VPT blocks than necessary and could
+        // fold the newly created one into a proceeding one.
+        for (auto I = ++MachineBasicBlock::iterator(Block.getVPST()),
+             E = ++MachineBasicBlock::iterator(Divergent->MI); I != E; ++I)
+          RemovePredicate(&*I);
+
+        unsigned Size = 0;
+        auto E = MachineBasicBlock::reverse_iterator(Divergent->MI);
+        auto I = MachineBasicBlock::reverse_iterator(Insts.back().MI);
+        MachineInstr *InsertAt = nullptr;
+        while (I != E) {
+          InsertAt = &*I;
+          ++Size;
+          ++I;
+        }
+        MachineInstrBuilder MIB = BuildMI(*InsertAt->getParent(), InsertAt,
+                                          InsertAt->getDebugLoc(),
+                                          TII->get(ARM::MVE_VPST));
+        MIB.addImm(getARMVPTBlockMask(Size));
+        LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST());
+        LLVM_DEBUG(dbgs() << "ARM Loops: Created VPST: " << *MIB);
+        Block.getVPST()->eraseFromParent();
+      }
+    } else if (Block.IsOnlyPredicatedOn(LoLoop.VCTP)) {
+      // A vpt block which is only predicated upon vctp and has no internal vpr
+      // defs:
+      // - Remove vpst.
+      // - Unpredicate the remaining instructions.
+      LLVM_DEBUG(dbgs() << "ARM Loops: Removing VPST: " << *Block.getVPST());
+      Block.getVPST()->eraseFromParent();
+      for (auto &PredMI : Insts)
+        RemovePredicate(PredMI.MI);
+    }
+  }
+
+  LLVM_DEBUG(dbgs() << "ARM Loops: Removing VCTP: " << *LoLoop.VCTP);
+  LoLoop.VCTP->eraseFromParent();
+}
+
+void ARMLowOverheadLoops::Expand(LowOverheadLoop &LoLoop) {
+
   // Combine the LoopDec and LoopEnd instructions into LE(TP).
-  auto ExpandLoopEnd = [this](MachineLoop *ML, MachineInstr *Dec,
-                              MachineInstr *End) {
+  auto ExpandLoopEnd = [this](LowOverheadLoop &LoLoop) {
+    MachineInstr *End = LoLoop.End;
     MachineBasicBlock *MBB = End->getParent();
+    unsigned Opc = LoLoop.IsTailPredicationLegal() ?
+      ARM::MVE_LETP : ARM::t2LEUpdate;
     MachineInstrBuilder MIB = BuildMI(*MBB, End, End->getDebugLoc(),
-                                      TII->get(ARM::t2LEUpdate));
+                                      TII->get(Opc));
     MIB.addDef(ARM::LR);
     MIB.add(End->getOperand(0));
     MIB.add(End->getOperand(1));
     LLVM_DEBUG(dbgs() << "ARM Loops: Inserted LE: " << *MIB);
 
-    End->eraseFromParent();
-    Dec->eraseFromParent();
+    LoLoop.End->eraseFromParent();
+    LoLoop.Dec->eraseFromParent();
     return &*MIB;
   };
 
@@ -496,18 +996,22 @@ void ARMLowOverheadLoops::Expand(MachineLoop *ML, MachineInstr *Start,
     }
   };
 
-  if (Revert) {
-    if (Start->getOpcode() == ARM::t2WhileLoopStart)
-      RevertWhile(Start);
+  if (LoLoop.Revert) {
+    if (LoLoop.Start->getOpcode() == ARM::t2WhileLoopStart)
+      RevertWhile(LoLoop.Start);
     else
-      Start->eraseFromParent();
-    bool FlagsAlreadySet = RevertLoopDec(Dec, true);
-    RevertLoopEnd(End, FlagsAlreadySet);
+      LoLoop.Start->eraseFromParent();
+    bool FlagsAlreadySet = RevertLoopDec(LoLoop.Dec, true);
+    RevertLoopEnd(LoLoop.End, FlagsAlreadySet);
   } else {
-    Start = ExpandLoopStart(ML, Start, InsertPt);
-    RemoveDeadBranch(Start);
-    End = ExpandLoopEnd(ML, Dec, End);
-    RemoveDeadBranch(End);
+    LoLoop.Start = ExpandLoopStart(LoLoop);
+    RemoveDeadBranch(LoLoop.Start);
+    LoLoop.End = ExpandLoopEnd(LoLoop);
+    RemoveDeadBranch(LoLoop.End);
+    if (LoLoop.IsTailPredicationLegal()) {
+      RemoveLoopUpdate(LoLoop);
+      ConvertVPTBlocks(LoLoop);
+    }
   }
 }
 
@@ -521,7 +1025,7 @@ bool ARMLowOverheadLoops::RevertNonLoops() {
     SmallVector<MachineInstr*, 4> Ends;
 
     for (auto &I : MBB) {
-      if (IsLoopStart(I))
+      if (isLoopStart(I))
         Starts.push_back(&I);
       else if (I.getOpcode() == ARM::t2LoopDec)
         Decs.push_back(&I);