[VPlan] Add vp_depth_first_deep (NFC)

[fhahn]

Summary

Similar to vp_depth_first_shallow (D140512) add vp_depth_first_deep to
make existing code clearer and more compact.

[Ayal]

Thanks for adding, looks good to me, ship it!

[fhahn]

Update block wrapper to use Deep naming as well.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

while (!Worklist.empty()) {
         if (VPRecipeBase *OpDef = operand->getDefiningRecipe())
           Worklist.push_back(OpDef);
     }
   });
 
   // Traverse all the recipes in the VPlan and collect the poison-generating
   // recipes in the backward slice starting at the address of a VPWidenRecipe or
   // VPInterleaveRecipe.
-  auto Iter = depth_first(
-      VPBlockRecursiveTraversalWrapper<VPBlockBase *>(State.Plan->getEntry()));
+  auto Iter = vp_depth_first_deep(State.Plan->getEntry());
   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
     for (VPRecipeBase &Recipe : *VPBB) {
       if (auto *WidenRec = dyn_cast<VPWidenMemoryInstructionRecipe>(&Recipe)) {
         Instruction &UnderlyingInstr = WidenRec->getIngredient();
         VPRecipeBase *AddrDef = WidenRec->getAddr()->getDefiningRecipe();
         if (AddrDef && WidenRec->isConsecutive() &&
             Legal->blockNeedsPredication(UnderlyingInstr.getParent()))
           collectPoisonGeneratingInstrsInBackwardSlice(AddrDef);
while (!Worklist.empty()) {
       // need to iterate.
       Changed = true;
     }
   } while (Changed);
 }
 
 void InnerLoopVectorizer::fixNonInductionPHIs(VPlan &Plan,
                                               VPTransformState &State) {
-  auto Iter = depth_first(
-      VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()));
+  auto Iter = vp_depth_first_deep(Plan.getEntry());
   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
     for (VPRecipeBase &P : VPBB->phis()) {
       VPWidenPHIRecipe *VPPhi = dyn_cast<VPWidenPHIRecipe>(&P);
       if (!VPPhi)
         continue;
       PHINode *NewPhi = cast<PHINode>(State.get(VPPhi, 0));
       // Make sure the builder has a valid insert point.
       Builder.SetInsertPoint(NewPhi);

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
   for (const auto &P : Plan.VPExternalDefs)
     assignSlot(P.second);
 
   assignSlot(&Plan.VectorTripCount);
   if (Plan.BackedgeTakenCount)
     assignSlot(Plan.BackedgeTakenCount);
 
-  ReversePostOrderTraversal<
-      VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>
-      RPOT(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
-          Plan.getEntry()));
+  ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<const VPBlockBase *>>
+      RPOT(VPBlockDeepTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
   for (const VPBasicBlock *VPBB :
        VPBlockUtils::blocksOnly<const VPBasicBlock>(RPOT))
     for (const VPRecipeBase &Recipe : *VPBB)
       for (VPValue *Def : Recipe.definedValues())
         assignSlot(Def);
 }
 
 bool vputils::onlyFirstLaneUsed(VPValue *Def) {

llvm/lib/Transforms/Vectorize/VPlanCFG.h

public:
   VPAllSuccessorsIterator operator++(int X) {
     VPAllSuccessorsIterator Orig = *this;
     SuccessorIdx++;
     return Orig;
   }
 };
 
 /// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
-template <typename BlockTy> class VPBlockRecursiveTraversalWrapper {
+template <typename BlockTy> class VPBlockDeepTraversalWrapper {
   BlockTy Entry;
 
 public:
-  VPBlockRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
+  VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
   BlockTy getEntry() { return Entry; }
 };
 
 /// GraphTraits specialization to recursively traverse VPBlockBase nodes,
 /// including traversing through VPRegionBlocks.  Exit blocks of a region
 /// implicitly have their parent region's successors. This ensures all blocks in
 /// a region are visited before any blocks in a successor region when doing a
 /// reverse post-order traversal of the graph.
-template <>
-struct GraphTraits<VPBlockRecursiveTraversalWrapper<VPBlockBase *>> {
+template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> {
   using NodeRef = VPBlockBase *;
   using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
 
-  static NodeRef
-  getEntryNode(VPBlockRecursiveTraversalWrapper<VPBlockBase *> N) {
+  static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) {
     return N.getEntry();
   }
 
   static inline ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N);
   }
 
   static inline ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType::end(N);
   }
 };
 
 template <>
-struct GraphTraits<VPBlockRecursiveTraversalWrapper<const VPBlockBase *>> {
+struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
   using NodeRef = const VPBlockBase *;
   using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
 
   static NodeRef
-  getEntryNode(VPBlockRecursiveTraversalWrapper<const VPBlockBase *> N) {
+  getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) {
     return N.getEntry();
   }
 
   static inline ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N);
   }
 
   static inline ChildIteratorType child_end(NodeRef N) {
vp_depth_first_shallow(VPBlockBase *G) {
   return depth_first(VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
 }
 inline iterator_range<
     df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
 vp_depth_first_shallow(const VPBlockBase *G) {
   return depth_first(VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
 }
 
+/// Returns an iterator range to traverse the graph starting at \p G in
+/// depth-first order while traversing through region blocks.
+inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
+vp_depth_first_deep(VPBlockBase *G) {
+  return depth_first(VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
+}
+inline iterator_range<
+    df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
+vp_depth_first_deep(const VPBlockBase *G) {
+  return depth_first(VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
+}
+
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

 
 void VPlanTransforms::VPInstructionsToVPRecipes(
     Loop *OrigLoop, VPlanPtr &Plan,
     function_ref<const InductionDescriptor *(PHINode *)>
         GetIntOrFpInductionDescriptor,
     SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE,
     const TargetLibraryInfo &TLI) {
 
-  ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
-      RPOT(Plan->getEntry());
+  ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(
+      Plan->getEntry());
   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) {
     VPRecipeBase *Term = VPBB->getTerminator();
     auto EndIter = Term ? Term->getIterator() : VPBB->end();
     // Introduce each ingredient into VPlan.
     for (VPRecipeBase &Ingredient :
          make_early_inc_range(make_range(VPBB->begin(), EndIter))) {
 
       VPValue *VPV = Ingredient.getVPSingleValue();
for (VPRecipeBase &Ingredient :
       for (auto *Def : NewRecipe->definedValues()) {
         Plan->addVPValue(Inst, Def);
       }
     }
   }
 }
 
 bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) {
-  auto Iter = depth_first(
-      VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()));
+  auto Iter = vp_depth_first_deep(Plan.getEntry());
   bool Changed = false;
   // First, collect the operands of all predicated replicate recipes as seeds
   // for sinking.
   SetVector<std::pair<VPBasicBlock *, VPRecipeBase *>> WorkList;
   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
     for (auto &Recipe : *VPBB) {
       auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
       if (!RepR || !RepR->isPredicated())

 
 bool VPlanTransforms::mergeReplicateRegionsIntoSuccessors(VPlan &Plan) {
   SetVector<VPRegionBlock *> DeletedRegions;
 
   // Collect replicate regions followed by an empty block, followed by another
   // replicate region with matching masks to process front. This is to avoid
   // iterator invalidation issues while merging regions.
   SmallVector<VPRegionBlock *, 8> WorkList;
-  for (VPRegionBlock *Region1 :
-       VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(
-           VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry())))) {
+  for (VPRegionBlock *Region1 : VPBlockUtils::blocksOnly<VPRegionBlock>(
+           vp_depth_first_deep(Plan.getEntry()))) {
     if (!Region1->isReplicator())
       continue;
     auto *MiddleBasicBlock =
         dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
     if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
       continue;
 
     auto *Region2 =
bool VPlanTransforms::mergeReplicateRegionsIntoSuccessors(VPlan &Plan) {
 
   for (VPRegionBlock *ToDelete : DeletedRegions)
     delete ToDelete;
   return !DeletedRegions.empty();
 }
 
 bool VPlanTransforms::mergeBlocksIntoPredecessors(VPlan &Plan) {
   SmallVector<VPBasicBlock *> WorkList;
-  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(depth_first(
-           VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry())))) {
+  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
+           vp_depth_first_deep(Plan.getEntry()))) {
     auto *PredVPBB =
         dyn_cast_or_null<VPBasicBlock>(VPBB->getSinglePredecessor());
     if (PredVPBB && PredVPBB->getNumSuccessors() == 1)
       WorkList.push_back(VPBB);
   }
 
   for (VPBasicBlock *VPBB : WorkList) {
     VPBasicBlock *PredVPBB = cast<VPBasicBlock>(VPBB->getSinglePredecessor());
if (WidenOriginalIV->needsVectorIV() ||
       WidenNewIV->replaceAllUsesWith(WidenOriginalIV);
       WidenNewIV->eraseFromParent();
       return;
     }
   }
 }
 
 void VPlanTransforms::removeDeadRecipes(VPlan &Plan) {
-  ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
-      RPOT(Plan.getEntry());
+  ReversePostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> RPOT(
+      Plan.getEntry());
 
   for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) {
     // The recipes in the block are processed in reverse order, to catch chains
     // of dead recipes.
     for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) {
       if (R.mayHaveSideEffects() || any_of(R.definedValues(), [](VPValue *V) {
             return V->getNumUsers() > 0;
           }))

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

for (const VPRecipeBase &R : *VPBB) {
     }
   }
   return true;
 }
 
 bool VPlanVerifier::verifyPlanIsValid(const VPlan &Plan) {
   DenseMap<const VPBlockBase *, unsigned> BlockNumbering;
   unsigned Cnt = 0;
-  auto Iter = depth_first(
-      VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(Plan.getEntry()));
+  auto Iter = vp_depth_first_deep(Plan.getEntry());
   for (const VPBlockBase *VPB : Iter) {
     BlockNumbering[VPB] = Cnt++;
     auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
     if (!VPBB)
       continue;
     if (!verifyVPBasicBlock(VPBB, BlockNumbering))
       return false;
   }
if (!LastInst || (LastInst->getOpcode() != VPInstruction::BranchOnCount &&
                     LastInst->getOpcode() != VPInstruction::BranchOnCond)) {
     errs() << "VPlan vector loop exit must end with BranchOnCount or "
               "BranchOnCond VPInstruction\n";
     return false;
   }
 
   for (const VPRegionBlock *Region :
        VPBlockUtils::blocksOnly<const VPRegionBlock>(
-           depth_first(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
-               Plan.getEntry())))) {
+           vp_depth_first_deep(Plan.getEntry()))) {
     if (Region->getEntry()->getNumPredecessors() != 0) {
       errs() << "region entry block has predecessors\n";
       return false;
     }
     if (Region->getExiting()->getNumSuccessors() != 0) {
       errs() << "region exiting block has successors\n";
       return false;
     }

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

TEST(VPBasicBlockTest, TraversingIteratorTest) {
     VPBasicBlock *VPBB3 = new VPBasicBlock();
     VPBasicBlock *VPBB4 = new VPBasicBlock();
 
     VPBlockUtils::connectBlocks(VPBB1, VPBB2);
     VPBlockUtils::connectBlocks(VPBB1, VPBB3);
     VPBlockUtils::connectBlocks(VPBB2, VPBB4);
     VPBlockUtils::connectBlocks(VPBB3, VPBB4);
 
-    VPBlockRecursiveTraversalWrapper<const VPBlockBase *> Start(VPBB1);
+    VPBlockDeepTraversalWrapper<const VPBlockBase *> Start(VPBB1);
     SmallVector<const VPBlockBase *> FromIterator(depth_first(Start));
     EXPECT_EQ(4u, FromIterator.size());
     EXPECT_EQ(VPBB1, FromIterator[0]);
     EXPECT_EQ(VPBB2, FromIterator[1]);
 
     // Use Plan to properly clean up created blocks.
     VPlan Plan;
     Plan.setEntry(VPBB1);
TEST(VPBasicBlockTest, TraversingIteratorTest) {
     // Successors of R1.
     SmallVector<const VPBlockBase *> FromIterator(
         VPAllSuccessorsIterator<VPBlockBase *>(R1),
         VPAllSuccessorsIterator<VPBlockBase *>::end(R1));
     EXPECT_EQ(1u, FromIterator.size());
     EXPECT_EQ(R1BB1, FromIterator[0]);
 
     // Depth-first.
-    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(R1);
+    VPBlockDeepTraversalWrapper<VPBlockBase *> Start(R1);
     FromIterator.clear();
     copy(df_begin(Start), df_end(Start), std::back_inserter(FromIterator));
     EXPECT_EQ(8u, FromIterator.size());
     EXPECT_EQ(R1, FromIterator[0]);
     EXPECT_EQ(R1BB1, FromIterator[1]);
     EXPECT_EQ(R1BB2, FromIterator[2]);
     EXPECT_EQ(R1BB4, FromIterator[3]);
     EXPECT_EQ(R2, FromIterator[4]);
TEST(VPBasicBlockTest, TraversingIteratorTest) {
     VPBlockUtils::connectBlocks(R2, R1BB3);
 
     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
     VPBlockUtils::connectBlocks(VPBB1, R1);
     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
     VPBlockUtils::connectBlocks(R1, VPBB2);
 
     // Depth-first.
-    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
     EXPECT_EQ(10u, FromIterator.size());
     EXPECT_EQ(VPBB1, FromIterator[0]);
     EXPECT_EQ(R1, FromIterator[1]);
     EXPECT_EQ(R1BB1, FromIterator[2]);
     EXPECT_EQ(R2, FromIterator[3]);
     EXPECT_EQ(R2BB1, FromIterator[4]);
     EXPECT_EQ(R2BB2, FromIterator[5]);
TEST(VPBasicBlockTest, TraversingIteratorTest) {
 
     VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
     R2->setParent(R1);
 
     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
     VPBlockUtils::connectBlocks(VPBB1, R1);
 
     // Depth-first.
-    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
     EXPECT_EQ(5u, FromIterator.size());
     EXPECT_EQ(VPBB1, FromIterator[0]);
     EXPECT_EQ(R1, FromIterator[1]);
     EXPECT_EQ(R2, FromIterator[2]);
     EXPECT_EQ(R2BB1, FromIterator[3]);
     EXPECT_EQ(R2BB2, FromIterator[4]);
 
TEST(VPBasicBlockTest, TraversingIteratorTest) {
     R2->setParent(R1);
 
     VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
     VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
     VPBlockUtils::connectBlocks(VPBB1, R1);
     VPBlockUtils::connectBlocks(R1, VPBB2);
 
     // Depth-first.
-    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    VPBlockDeepTraversalWrapper<VPBlockBase *> Start(VPBB1);
     SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
     EXPECT_EQ(7u, FromIterator.size());
     EXPECT_EQ(VPBB1, FromIterator[0]);
     EXPECT_EQ(R1, FromIterator[1]);
     EXPECT_EQ(R2, FromIterator[2]);
     EXPECT_EQ(R2BB1, FromIterator[3]);
     EXPECT_EQ(R3, FromIterator[4]);
     EXPECT_EQ(R3BB1, FromIterator[5]);
TEST(VPBasicBlockTest, TraversingIteratorTest) {
     EXPECT_EQ(R3BB1, FromIterator[1]);
     EXPECT_EQ(R3, FromIterator[2]);
     EXPECT_EQ(R2BB1, FromIterator[3]);
     EXPECT_EQ(R2, FromIterator[4]);
     EXPECT_EQ(R1, FromIterator[5]);
     EXPECT_EQ(VPBB1, FromIterator[6]);
 
     // Post-order, const VPRegionBlocks only.
-    VPBlockRecursiveTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
+    VPBlockDeepTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
     SmallVector<const VPRegionBlock *> FromIteratorVPRegion(
         VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)));
     EXPECT_EQ(3u, FromIteratorVPRegion.size());
     EXPECT_EQ(R3, FromIteratorVPRegion[0]);
     EXPECT_EQ(R2, FromIteratorVPRegion[1]);
     EXPECT_EQ(R1, FromIteratorVPRegion[2]);
 
     // Post-order, VPBasicBlocks only.