[VPlan] Add vp_depth_first_shallow + graph traits for wrapper(NFC)

[fhahn]

Summary

This patch adds a new VPBlockNonRecursiveTraversalWrapper struct to
provide graph traits specialization that do not traverse through
VPRegionBlocks. This matches the behavior of the existing traits for
plain VPBlockBase and is a step before moving the graph traits for
VPBlockBase to traverse through VPRegionBlocks to enable cross region
support in VPDominatorTree.

Depends on D140511.

[fhahn]

ping :)

[Ayal]

Ship it!

llvm/lib/Transforms/Vectorize/VPlanCFG.h

323

nit: for completeness can also introduce vp_depth_first_recursive(VPBlockBase *G) which returns depth_first(VPBlockRecursiveTraversalWrapper<VPBlockBase *>(G)); used elsewhere.

nit: "recursive" here stands for traversing inside regions of the hierarchical CFG. Perhaps a more accurate term is "deep" versus "flat" or "shallow", given the recursive nature of DFS itself.

[fhahn]

Adjust naming, add comment.

llvm/lib/Transforms/Vectorize/VPlanCFG.h

323

nit: for completeness can also introduce vp_depth_first_recursive(VPBlockBase *G) which returns depth_first(VPBlockRecursiveTraversalWrapper<VPBlockBase *>(G)); used elsewhere.

I'll add a separate patch for that.

nit: "recursive" here stands for traversing inside regions of the hierarchical CFG. Perhaps a more accurate term is "deep" versus "flat" or "shallow", given the recursive nature of DFS itself.

Updated the name to use _shallow instead of non recursive, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanCFG.h

323

Very good! Worth also renaming VPBlockNonRecursiveTraversalWrapper as VPBlockShallowTraversalWrapper to be consistent?

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanCFG.h

323

Done in the committed version, also added a comment to the definition of it.

llvm/lib/Transforms/Vectorize/VPlan.cpp

VPBlockBase *VPBlockBase::getEnclosingBlockWithPredecessors() {
   if (!Predecessors.empty() || !Parent)
     return this;
   assert(Parent->getEntry() == this &&
          "Block w/o predecessors not the entry of its parent.");
   return Parent->getEnclosingBlockWithPredecessors();
 }
 
 void VPBlockBase::deleteCFG(VPBlockBase *Entry) {
-  for (VPBlockBase *Block : to_vector(depth_first(Entry)))
+  for (VPBlockBase *Block : to_vector(vp_depth_first_shallow(Entry)))
     delete Block;
 }
 
 VPBasicBlock::iterator VPBasicBlock::getFirstNonPhi() {
   iterator It = begin();
   while (It != end() && It->isPhi())
     It++;
   return It;
for (const VPRecipeBase &Recipe : *this) {
     O << '\n';
   }
 
   printSuccessors(O, Indent);
 }
 #endif
 
 void VPRegionBlock::dropAllReferences(VPValue *NewValue) {
-  for (VPBlockBase *Block : depth_first(Entry))
+  for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
     // Drop all references in VPBasicBlocks and replace all uses with
     // DummyValue.
     Block->dropAllReferences(NewValue);
 }
 
 void VPRegionBlock::execute(VPTransformState *State) {
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(Entry);
+  ReversePostOrderTraversal<VPBlockNonRecursiveTraversalWrapper<VPBlockBase *>>
+      RPOT(Entry);
 
   if (!isReplicator()) {
     // Create and register the new vector loop.
     Loop *PrevLoop = State->CurrentVectorLoop;
     State->CurrentVectorLoop = State->LI->AllocateLoop();
     BasicBlock *VectorPH = State->CFG.VPBB2IRBB[getPreheaderVPBB()];
     Loop *ParentLoop = State->LI->getLoopFor(VectorPH);
 
void VPRegionBlock::execute(VPTransformState *State) {
   State->Instance.reset();
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void VPRegionBlock::print(raw_ostream &O, const Twine &Indent,
                           VPSlotTracker &SlotTracker) const {
   O << Indent << (isReplicator() ? "<xVFxUF> " : "<x1> ") << getName() << ": {";
   auto NewIndent = Indent + "  ";
-  for (auto *BlockBase : depth_first(Entry)) {
+  for (auto *BlockBase : vp_depth_first_shallow(Entry)) {
     O << '\n';
     BlockBase->print(O, NewIndent, SlotTracker);
   }
   O << Indent << "}\n";
 
   printSuccessors(O, Indent);
 }
 #endif
 
 VPlan::~VPlan() {
   clearLiveOuts();
 
   if (Entry) {
     VPValue DummyValue;
-    for (VPBlockBase *Block : depth_first(Entry))
+    for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
       Block->dropAllReferences(&DummyValue);
 
     VPBlockBase::deleteCFG(Entry);
   }
   for (VPValue *VPV : VPValuesToFree)
     delete VPV;
   if (TripCount)
     delete TripCount;
void VPlan::execute(VPTransformState *State) {
 
   // Initialize CFG state.
   State->CFG.PrevVPBB = nullptr;
   State->CFG.ExitBB = State->CFG.PrevBB->getSingleSuccessor();
   BasicBlock *VectorPreHeader = State->CFG.PrevBB;
   State->Builder.SetInsertPoint(VectorPreHeader->getTerminator());
 
   // Generate code in the loop pre-header and body.
-  for (VPBlockBase *Block : depth_first(Entry))
+  for (VPBlockBase *Block : vp_depth_first_shallow(Entry))
     Block->execute(State);
 
   VPBasicBlock *LatchVPBB = getVectorLoopRegion()->getExitingBasicBlock();
   BasicBlock *VectorLatchBB = State->CFG.VPBB2IRBB[LatchVPBB];
 
   // Fix the latch value of canonical, reduction and first-order recurrences
   // phis in the vector loop.
   VPBasicBlock *Header = getVectorLoopRegion()->getEntryBasicBlock();
void VPlan::print(raw_ostream &O) const {
   }
 
   if (BackedgeTakenCount && BackedgeTakenCount->getNumUsers()) {
     O << "\nLive-in ";
     BackedgeTakenCount->printAsOperand(O, SlotTracker);
     O << " = backedge-taken count\n";
   }
 
-  for (const VPBlockBase *Block : depth_first(getEntry())) {
+  for (const VPBlockBase *Block : vp_depth_first_shallow(getEntry())) {
     O << '\n';
     Block->print(O, "", SlotTracker);
   }
 
   if (!LiveOuts.empty())
     O << "\n";
   for (const auto &KV : LiveOuts) {
     O << "Live-out ";
if (Plan.BackedgeTakenCount) {
     Plan.BackedgeTakenCount->print(OS, SlotTracker);
     OS << " := BackedgeTakenCount";
   }
   OS << "\"]\n";
   OS << "node [shape=rect, fontname=Courier, fontsize=30]\n";
   OS << "edge [fontname=Courier, fontsize=30]\n";
   OS << "compound=true\n";
 
-  for (const VPBlockBase *Block : depth_first(Plan.getEntry()))
+  for (const VPBlockBase *Block : vp_depth_first_shallow(Plan.getEntry()))
     dumpBlock(Block);
 
   OS << "}\n";
 }
 
 void VPlanPrinter::dumpBlock(const VPBlockBase *Block) {
   if (const VPBasicBlock *BasicBlock = dyn_cast<VPBasicBlock>(Block))
     dumpBasicBlock(BasicBlock);
void VPlanPrinter::dumpRegion(const VPRegionBlock *Region) {
   OS << Indent << "subgraph " << getUID(Region) << " {\n";
   bumpIndent(1);
   OS << Indent << "fontname=Courier\n"
      << Indent << "label=\""
      << DOT::EscapeString(Region->isReplicator() ? "<xVFxUF> " : "<x1> ")
      << DOT::EscapeString(Region->getName()) << "\"\n";
   // Dump the blocks of the region.
   assert(Region->getEntry() && "Region contains no inner blocks.");
-  for (const VPBlockBase *Block : depth_first(Region->getEntry()))
+  for (const VPBlockBase *Block : vp_depth_first_shallow(Region->getEntry()))
     dumpBlock(Block);
   bumpIndent(-1);
   OS << Indent << "}\n";
   dumpEdges(Region);
 }
 
 void VPlanIngredient::print(raw_ostream &O) const {
   if (auto *Inst = dyn_cast<Instruction>(V)) {
interleaveComma(operands(), O, [&O, &SlotTracker](VPValue *Op) {
     Op->printAsOperand(O, SlotTracker);
   });
 }
 #endif
 
 void VPInterleavedAccessInfo::visitRegion(VPRegionBlock *Region,
                                           Old2NewTy &Old2New,
                                           InterleavedAccessInfo &IAI) {
-  ReversePostOrderTraversal<VPBlockBase *> RPOT(Region->getEntry());
+  ReversePostOrderTraversal<VPBlockNonRecursiveTraversalWrapper<VPBlockBase *>>
+      RPOT(Region->getEntry());
   for (VPBlockBase *Base : RPOT) {
     visitBlock(Base, Old2New, IAI);
   }
 }
 
 void VPInterleavedAccessInfo::visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,
                                          InterleavedAccessInfo &IAI) {
   if (VPBasicBlock *VPBB = dyn_cast<VPBasicBlock>(Block)) {

llvm/lib/Transforms/Vectorize/VPlanCFG.h

static inline ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N);
   }
 
   static inline ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType::end(N);
   }
 };
 
+template <typename BlockTy> class VPBlockNonRecursiveTraversalWrapper {
+  BlockTy Entry;
+
+public:
+  VPBlockNonRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
+  BlockTy getEntry() { return Entry; }
+};
+
+template <>
+struct GraphTraits<VPBlockNonRecursiveTraversalWrapper<VPBlockBase *>> {
+  using NodeRef = VPBlockBase *;
+  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
+
+  static NodeRef
+  getEntryNode(VPBlockNonRecursiveTraversalWrapper<VPBlockBase *> N) {
+    return N.getEntry();
+  }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->getSuccessors().begin();
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return N->getSuccessors().end();
+  }
+};
+
+template <>
+struct GraphTraits<VPBlockNonRecursiveTraversalWrapper<const VPBlockBase *>> {
+  using NodeRef = const VPBlockBase *;
+  using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
+
+  static NodeRef
+  getEntryNode(VPBlockNonRecursiveTraversalWrapper<const VPBlockBase *> N) {
+    return N.getEntry();
+  }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->getSuccessors().begin();
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return N->getSuccessors().end();
+  }
+};
+
+/// Returns an iterator range to traverse the graph starting at \p G in
+/// depth-first order. The iterator won't traverse through region blocks.
+inline iterator_range<
+    df_iterator<VPBlockNonRecursiveTraversalWrapper<VPBlockBase *>>>
+vp_depth_first_shallow(VPBlockBase *G) {
+  return depth_first(VPBlockNonRecursiveTraversalWrapper<VPBlockBase *>(G));
+}
+inline iterator_range<
+    df_iterator<VPBlockNonRecursiveTraversalWrapper<const VPBlockBase *>>>
+vp_depth_first_shallow(const VPBlockBase *G) {
+  return depth_first(
+      VPBlockNonRecursiveTraversalWrapper<const VPBlockBase *>(G));
+}
+
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

static bool hasDuplicates(const SmallVectorImpl<VPBlockBase *> &VPBlockVec) {
   return false;
 }
 #endif
 
 /// Helper function that verifies the CFG invariants of the VPBlockBases within
 /// \p Region. Checks in this function are generic for VPBlockBases. They are
 /// not specific for VPBasicBlocks or VPRegionBlocks.
 static void verifyBlocksInRegion(const VPRegionBlock *Region) {
-  for (const VPBlockBase *VPB : make_range(
-           df_iterator<const VPBlockBase *>::begin(Region->getEntry()),
-           df_iterator<const VPBlockBase *>::end(Region->getExiting()))) {
+  for (const VPBlockBase *VPB : vp_depth_first_shallow(Region->getEntry())) {
     // Check block's parent.
     assert(VPB->getParent() == Region && "VPBlockBase has wrong parent");
 
     auto *VPBB = dyn_cast<VPBasicBlock>(VPB);
     // Check block's condition bit.
     if (VPB->getNumSuccessors() > 1 || (VPBB && VPBB->isExiting()))
       assert(VPBB && VPBB->getTerminator() &&
              "Block has multiple successors but doesn't "