[ARM][MVE] Some more dbg messages for MVETailPredication. NFC.

[SjoerdMeijer]

Summary

I've added a few more debug messages to MVETailPredication, because I wanted to trace better which instructions were added/removed. And while I was at it, I factored out one function which I thought was clearer, and have added some comments to describe better the flow between MVETailPredication and ARMLowOverheadLoops.

[samparker]

Cheers.

llvm/lib/Target/ARM/ARMLowOverheadLoops.cpp

 /// instructions into machine operations.
 /// The expectation is that the loop contains three pseudo instructions:
 /// - t2*LoopStart - placed in the preheader or pre-preheader. The do-loop
 ///   form should be in the preheader, whereas the while form should be in the
 ///   preheaders only predecessor.
 /// - 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.
+///
 //===----------------------------------------------------------------------===//
 
 #include "ARM.h"
 #include "ARMBaseInstrInfo.h"
 #include "ARMBaseRegisterInfo.h"
 #include "ARMBasicBlockInfo.h"
 #include "ARMSubtarget.h"
 #include "llvm/ADT/SetOperations.h"

llvm/lib/Target/ARM/MVETailPredication.cpp

 /// responsible for generating a vectorized loop in which the lanes are
 /// predicated upon the iteration counter. This pass looks at these predicated
 /// vector loops, that are targets for low-overhead loops, and prepares it for
 /// code generation. Once the vectorizer has produced a masked loop, there's a
 /// couple of final forms:
 /// - A tail-predicated loop, with implicit predication.
 /// - A loop containing multiple VCPT instructions, predicating multiple VPT
 ///   blocks of instructions operating on different vector types.
+///
+/// This pass inserts the inserts the VCTP intrinsic to represent the effect of
+/// tail predication. This will be picked up by the ARM Low-overhead loop pass,
+/// which performs the final transformation to a DLSTP or WLSTP tail-predicated
+/// loop.
 
 #include "ARM.h"
 #include "ARMSubtarget.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
private:
 
   /// Compute a value for the total number of elements that the predicated
   /// loop will process.
   Value *ComputeElements(Value *TripCount, VectorType *VecTy);
 
   /// Is the icmp that generates an i1 vector, based upon a loop counter
   /// and a limit that is defined outside the loop.
   bool isTailPredicate(Instruction *Predicate, Value *NumElements);
+
+  /// Insert the intrinsic to represent the effect of tail predication.
+  void InsertVCTPIntrinsic(Instruction *Predicate,
+                           DenseMap<Instruction*, Instruction*> &NewPredicates,
+                           VectorType *VecTy,
+                           Value *NumElements);
 };
 
 } // end namespace
 
 static bool IsDecrement(Instruction &I) {
   auto *Call = dyn_cast<IntrinsicInst>(&I);
   if (!Call)
     return false;
bool MVETailPredication::runOnLoop(Loop *L, LPPassManager&) {
   auto *ST = &TM.getSubtarget<ARMSubtarget>(F);
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   this->L = L;
 
   // The MVE and LOB extensions are combined to enable tail-predication, but
   // there's nothing preventing us from generating VCTP instructions for v8.1m.
   if (!ST->hasMVEIntegerOps() || !ST->hasV8_1MMainlineOps()) {
-    LLVM_DEBUG(dbgs() << "TP: Not a v8.1m.main+mve target.\n");
+    LLVM_DEBUG(dbgs() << "ARM TP: Not a v8.1m.main+mve target.\n");
     return false;
   }
 
   BasicBlock *Preheader = L->getLoopPreheader();
   if (!Preheader)
     return false;
 
   auto FindLoopIterations = [](BasicBlock *BB) -> IntrinsicInst* {
     for (auto &I : *BB) {
       auto *Call = dyn_cast<IntrinsicInst>(&I);
       if (!Call)
         continue;
 
       Intrinsic::ID ID = Call->getIntrinsicID();
       if (ID == Intrinsic::set_loop_iterations ||
           ID == Intrinsic::test_set_loop_iterations)
         return cast<IntrinsicInst>(&I);
     }
     return nullptr;
   };
 
   // Look for the hardware loop intrinsic that sets the iteration count.
   IntrinsicInst *Setup = FindLoopIterations(Preheader);
 
-  // The test.set iteration could live in the pre- preheader.
+  // The test.set iteration could live in the pre-preheader.
   if (!Setup) {
     if (!Preheader->getSinglePredecessor())
       return false;
     Setup = FindLoopIterations(Preheader->getSinglePredecessor());
     if (!Setup)
       return false;
   }
 
   // Search for the hardware loop intrinic that decrements the loop counter.
   IntrinsicInst *Decrement = nullptr;
   for (auto *BB : L->getBlocks()) {
     for (auto &I : *BB) {
       if (IsDecrement(I)) {
         Decrement = cast<IntrinsicInst>(&I);
         break;
       }
     }
   }
 
   if (!Decrement)
     return false;
 
-  LLVM_DEBUG(dbgs() << "TP: Running on Loop: " << *L
-             << *Setup << "\n"
+  LLVM_DEBUG(dbgs() << "ARM TP: Running on Loop: " << *L << *Setup << "\n"
              << *Decrement << "\n");
-  bool Changed = TryConvert(Setup->getArgOperand(0));
-  return Changed;
+  return TryConvert(Setup->getArgOperand(0));
 }
 
 bool MVETailPredication::isTailPredicate(Instruction *I, Value *NumElements) {
   // Look for the following:
 
   // %trip.count.minus.1 = add i32 %N, -1
   // %broadcast.splatinsert10 = insertelement <4 x i32> undef,
   //                                          i32 %trip.count.minus.1, i32 0
bool MVETailPredication::isTailPredicate(Instruction *I, Value *NumElements) {
   Value *TripCount = nullptr;
   if (!match(BECount, m_Add(m_Value(TripCount), m_AllOnes())))
     return false;
 
   if (TripCount != NumElements || !L->isLoopInvariant(BECount))
     return false;
 
   // Now back to searching inside the loop body...
-  // Find the add with takes the index iv and adds a constant vector to it. 
+  // Find the add with takes the index iv and adds a constant vector to it.
   Instruction *BroadcastSplat = nullptr;
   Constant *Const = nullptr;
   if (!match(Induction, m_Add(m_Instruction(BroadcastSplat),
                               m_Constant(Const))))
    return false;
 
   // Check that we're adding <0, 1, 2, 3...
   if (auto *CDS = dyn_cast<ConstantDataSequential>(Const)) {
bool MVETailPredication::isTailPredicate(Instruction *I, Value *NumElements) {
   auto *Phi = dyn_cast<PHINode>(IV);
   if (!Phi)
     return false;
 
   // TODO: Don't think we need to check the entry value.
   Value *OnEntry = Phi->getIncomingValueForBlock(L->getLoopPreheader());
   if (!match(OnEntry, m_Zero()))
     return false;
-  
   Value *InLoop = Phi->getIncomingValueForBlock(L->getLoopLatch());
   unsigned Lanes = cast<VectorType>(Insert->getType())->getNumElements();
 
   Instruction *LHS = nullptr;
   if (!match(InLoop, m_Add(m_Instruction(LHS), m_SpecificInt(Lanes))))
     return false;
-  
   return LHS == Phi;
 }
 
 static VectorType* getVectorType(IntrinsicInst *I) {
   unsigned TypeOp = I->getIntrinsicID() == Intrinsic::masked_load ? 0 : 1;
   auto *PtrTy = cast<PointerType>(I->getOperand(TypeOp)->getType());
   return cast<VectorType>(PtrTy->getElementType());
 }
 
 bool MVETailPredication::IsPredicatedVectorLoop() {
   // Check that the loop contains at least one masked load/store intrinsic.
   // We only support 'normal' vector instructions - other than masked
   // load/stores.
   for (auto *BB : L->getBlocks()) {
     for (auto &I : *BB) {
       if (IsMasked(&I)) {
         VectorType *VecTy = getVectorType(cast<IntrinsicInst>(&I));
         unsigned Lanes = VecTy->getNumElements();
         unsigned ElementWidth = VecTy->getScalarSizeInBits();
         // MVE vectors are 128-bit, but don't support 128 x i1.
         // TODO: Can we support vectors larger than 128-bits?
-        unsigned MaxWidth = TTI->getRegisterBitWidth(true); 
+        unsigned MaxWidth = TTI->getRegisterBitWidth(true);
         if (Lanes * ElementWidth > MaxWidth || Lanes == MaxWidth)
           return false;
         MaskedInsts.push_back(cast<IntrinsicInst>(&I));
       } else if (auto *Int = dyn_cast<IntrinsicInst>(&I)) {
         for (auto &U : Int->args()) {
           if (isa<VectorType>(U->getType()))
             return false;
         }

 // instruction. This can happen when we need to perform a select on values
 // from the last and previous iteration. Instead of doing a straight
 // replacement of that predicate with the vctp, clone the vctp and place it
 // in the block. This means that the VPR doesn't have to be live into the
 // exit block which should make it easier to convert this loop into a proper
 // tail predicated loop.
 static void Cleanup(DenseMap<Instruction*, Instruction*> &NewPredicates,
                     SetVector<Instruction*> &MaybeDead, Loop *L) {
-  if (BasicBlock *Exit = L->getUniqueExitBlock()) {
-    for (auto &Pair : NewPredicates) {
-      Instruction *OldPred = Pair.first;
-      Instruction *NewPred = Pair.second;
+  BasicBlock *Exit = L->getUniqueExitBlock();
+  if (!Exit) {
+    LLVM_DEBUG(dbgs() << "ARM TP: can't find loop exit block\n");
+    return;
+  }
+
 
-      for (auto &I : *Exit) {
-        if (I.isSameOperationAs(OldPred)) {
-          Instruction *PredClone = NewPred->clone();
-          PredClone->insertBefore(&I);
-          I.replaceAllUsesWith(PredClone);
-          MaybeDead.insert(&I);
-          break;
-        }
-      }
-    }
-  }
+        LLVM_DEBUG(dbgs() << "ARM TP: replacing: "; I.dump();
+                   dbgs() << "ARM TP: with:      "; PredClone->dump());
 
   // Drop references and add operands to check for dead.
   SmallPtrSet<Instruction*, 4> Dead;
   while (!MaybeDead.empty()) {
     auto *I = MaybeDead.front();
     MaybeDead.remove(I);
     if (I->hasNUsesOrMore(1))
       continue;
 
     for (auto &U : I->operands()) {
       if (auto *OpI = dyn_cast<Instruction>(U))
         MaybeDead.insert(OpI);
     }
     I->dropAllReferences();
     Dead.insert(I);
   }
 
-  for (auto *I : Dead)
+  for (auto *I : Dead) {
+    LLVM_DEBUG(dbgs() << "ARM TP: removing dead insn: "; I->dump());
     I->eraseFromParent();
+  }
 
   for (auto I : L->blocks())
     DeleteDeadPHIs(I);
 }
 
-bool MVETailPredication::TryConvert(Value *TripCount) {
-  if (!IsPredicatedVectorLoop())
-    return false;
-
-  LLVM_DEBUG(dbgs() << "TP: Found predicated vector loop.\n");
-
-  // Walk through the masked intrinsics and try to find whether the predicate
-  // operand is generated from an induction variable.
+void MVETailPredication::InsertVCTPIntrinsic(Instruction *Predicate,
+    DenseMap<Instruction*, Instruction*> &NewPredicates,
+    VectorType *VecTy, Value *NumElements) {
+  IRBuilder<> Builder(L->getHeader()->getFirstNonPHI());
   Module *M = L->getHeader()->getModule();
   Type *Ty = IntegerType::get(M->getContext(), 32);
-  SetVector<Instruction*> Predicates;
-  DenseMap<Instruction*, Instruction*> NewPredicates;
-
-  for (auto *I : MaskedInsts) {
-    Intrinsic::ID ID = I->getIntrinsicID();
-    unsigned PredOp = ID == Intrinsic::masked_load ? 2 : 3;
-    auto *Predicate = dyn_cast<Instruction>(I->getArgOperand(PredOp));
-    if (!Predicate || Predicates.count(Predicate))
-      continue;
-
-    VectorType *VecTy = getVectorType(I);
-    Value *NumElements = ComputeElements(TripCount, VecTy);
-    if (!NumElements)
-      continue;
-
-    if (!isTailPredicate(Predicate, NumElements)) {
-      LLVM_DEBUG(dbgs() << "TP: Not tail predicate: " << *Predicate <<  "\n");
-      continue;
-    }
-
-    LLVM_DEBUG(dbgs() << "TP: Found tail predicate: " << *Predicate << "\n");
-    Predicates.insert(Predicate);
 
-    // Insert a phi to count the number of elements processed by the loop.
-    IRBuilder<> Builder(L->getHeader()->getFirstNonPHI());
-    PHINode *Processed = Builder.CreatePHI(Ty, 2);
-    Processed->addIncoming(NumElements, L->getLoopPreheader());
 
-    // Insert the intrinsic to represent the effect of tail predication.
-    Builder.SetInsertPoint(cast<Instruction>(Predicate));
-    ConstantInt *Factor =
-      ConstantInt::get(cast<IntegerType>(Ty), VecTy->getNumElements());
-    Intrinsic::ID VCTPID;
-    switch (VecTy->getNumElements()) {
-    default:
-      llvm_unreachable("unexpected number of lanes");
-    case 4:  VCTPID = Intrinsic::arm_mve_vctp32; break;
-    case 8:  VCTPID = Intrinsic::arm_mve_vctp16; break;
-    case 16: VCTPID = Intrinsic::arm_mve_vctp8; break;
+
 
-      // FIXME: vctp64 currently not supported because the predicate
-      // vector wants to be <2 x i1>, but v2i1 is not a legal MVE
-      // type, so problems happen at isel time.
-      // Intrinsic::arm_mve_vctp64 exists for ACLE intrinsics
-      // purposes, but takes a v4i1 instead of a v2i1.
-    }
-    Function *VCTP = Intrinsic::getDeclaration(M, VCTPID);
-    Value *TailPredicate = Builder.CreateCall(VCTP, Processed);
-    Predicate->replaceAllUsesWith(TailPredicate);
-    NewPredicates[Predicate] = cast<Instruction>(TailPredicate);
 
-    // Add the incoming value to the new phi.
-    // TODO: This add likely already exists in the loop.
-    Value *Remaining = Builder.CreateSub(Processed, Factor);
-    Processed->addIncoming(Remaining, L->getLoopLatch());
-    LLVM_DEBUG(dbgs() << "TP: Insert processed elements phi: "
-               << *Processed << "\n"
-               << "TP: Inserted VCTP: " << *TailPredicate << "\n");
+  LLVM_DEBUG(dbgs() << "ARM TP: Insert processed elements phi: "
+             << "ARM TP: Inserted VCTP: " << *TailPredicate << "\n");
+}
+
+bool MVETailPredication::TryConvert(Value *TripCount) {
+  if (!IsPredicatedVectorLoop()) {
+    LLVM_DEBUG(dbgs() << "ARM TP: no masked instructions in loop");
+    return false;
+  }
+
+  LLVM_DEBUG(dbgs() << "ARM TP: Found predicated vector loop.\n");
+
+  // Walk through the masked intrinsics and try to find whether the predicate
+  // operand is generated from an induction variable.
+  SetVector<Instruction*> Predicates;
+  DenseMap<Instruction*, Instruction*> NewPredicates;
+
+  for (auto *I : MaskedInsts) {
+    Intrinsic::ID ID = I->getIntrinsicID();
+    unsigned PredOp = ID == Intrinsic::masked_load ? 2 : 3;
+    auto *Predicate = dyn_cast<Instruction>(I->getArgOperand(PredOp));
+    if (!Predicate || Predicates.count(Predicate))
+      continue;
+
+    VectorType *VecTy = getVectorType(I);
+    Value *NumElements = ComputeElements(TripCount, VecTy);
+    if (!NumElements)
+      continue;
+
+    if (!isTailPredicate(Predicate, NumElements)) {
+      LLVM_DEBUG(dbgs() << "ARM TP: Not tail predicate: " << *Predicate << "\n");
+      continue;
+    }
+
+    LLVM_DEBUG(dbgs() << "ARM TP: Found tail predicate: " << *Predicate << "\n");
+    Predicates.insert(Predicate);
+
+    InsertVCTPIntrinsic(Predicate, NewPredicates, VecTy, NumElements);
   }
 
   // Now clean up.
   Cleanup(NewPredicates, Predicates, L);
   return true;
 }
 
 Pass *llvm::createMVETailPredicationPass() {
   return new MVETailPredication();
 }
 
 char MVETailPredication::ID = 0;
 
 INITIALIZE_PASS_BEGIN(MVETailPredication, DEBUG_TYPE, DESC, false, false)
 INITIALIZE_PASS_END(MVETailPredication, DEBUG_TYPE, DESC, false, false)