[VPlan] Disconnect VPRegionBlock from successors in graph iterator(NFCI)

[fhahn]

Summary

This updates the VPAllSuccessorsIterator to not connect the
VPRegionBlock itself to its successors. The successors are connected to
the exit block of the region. At the moment, this doesn't change any
exisint functionality.

But the new schema ensures the following property when used for
VPDominatorTree:

1. Entry & exit blocks of regions dominate the successors of the region.

This allows for convenient checking of dominance between defs and uses
that are not defined in the same region. I will share a follow-up patch
to use it for the VPDominatorTree soon.

Depends on D140500.

[fhahn]

ping :)

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanCFG.h

148

nit: the Region blocks themselves are (continue to be) directly connected to their successors, it is how the iterate traverses successors of a region - as those of its exit blocks, only.

160

nit: worth commenting that null is returned if given block and all its parents have no successors. (Independent of this patch.)

198–199

This is fine as every region has an entry block, which is what this 1 represents, independent of how many successors R may have, if any.

So current VPAllSuccessorIterator visits successors of a region twice - once coming from the exit block and once coming from the region, and the latter is removed here? Is it possible to test that it iterates over blocks correctly?

nit: can define NumSuccessors after early exiting if Block is region, or set it to 1 for regions instead of early exiting.

nit: can set NumSuccessors to zero if !ParentWithSuccs, instead of Block->getNumSuccessors(). (Independent of this patch).

[fhahn]

Address latest comments and rebase on top of fixes for independent suggestions.

[Ayal]

Looks good to me, thanks for adding the test!

llvm/lib/Transforms/Vectorize/VPlanCFG.h

193

nit: can comment that 'entry' is the 1 "successor".

[fhahn]

(submit pending comment responses I missed to submit earlier)

llvm/lib/Transforms/Vectorize/VPlanCFG.h

148

Thanks, I clarified the comment that this is limited to the iterator traversal.

160

Will do separately, thanks!

198–199

So current VPAllSuccessorIterator visits successors of a region twice - once coming from the exit block and once coming from the region, and the latter is removed here? Is it possible to test that it iterates over blocks correctly?

Added a test in 3632bf85079bc497993def427223e9d74389a659 that use the iterator on a region directly.

nit: can define NumSuccessors after early exiting if Block is region, or set it to 1 for regions instead of early exiting.

moved, thanks!

nit: can set NumSuccessors to zero if !ParentWithSuccs, instead of Block->getNumSuccessors(). (Independent of this patch).

done in c95138392a75021c98f53b423b29995cb8a3283b, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanCFG.h

193

Done in the committed version.

llvm/lib/Transforms/Vectorize/VPlanCFG.h

static nodes_iterator nodes_end(GraphRef N) {
     return nodes_iterator::end(N);
   }
 };
 
 /// Iterator to traverse all successors of a VPBlockBase node. This includes the
 /// entry node of 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.
+// traversal of the graph. Region blocks themselves traverse only their entries
+// directly and not their successors. Those will be traversed when a region's
+// exiting block is traversed
 template <typename BlockPtrTy>
 class VPAllSuccessorsIterator
     : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
                                   std::forward_iterator_tag, VPBlockBase> {
   BlockPtrTy Block;
   /// Index of the current successor. For VPBasicBlock nodes, this simply is the
   /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
   /// used for the region's entry block, and SuccessorIdx - 1 are the indices
   /// for the successor array.
   size_t SuccessorIdx;
 
   static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
     while (Current && Current->getNumSuccessors() == 0)
       Current = Current->getParent();
     return Current;
   }
 
   /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
   /// both the const and non-const operator* implementations.
   template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
     if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
-      if (SuccIdx == 0)
-        return R->getEntry();
-      SuccIdx--;
+      assert(SuccIdx == 0);
     }
 
     // For exit blocks, use the next parent region with successors.
     return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
   }
 
 public:
   VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
       : Block(Block), SuccessorIdx(Idx) {}
   VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
       : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
 
   VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) {
     Block = R.Block;
     SuccessorIdx = R.SuccessorIdx;
     return *this;
   }
 
   static VPAllSuccessorsIterator end(BlockPtrTy Block) {
+    if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
+      // Traverse through the region's entry node.
+      return {R, 1};
+    }
     BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
     unsigned NumSuccessors =
         ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0;
-
-    if (auto *R = dyn_cast<VPRegionBlock>(Block))
-      return {R, NumSuccessors + 1};
     return {Block, NumSuccessors};
   }
 
   bool operator==(const VPAllSuccessorsIterator &R) const {
     return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
   }
 
   const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
 

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

TEST(VPBasicBlockTest, TraversingIteratorTest) {
     VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
     VPBlockUtils::connectBlocks(R2BB1, R2BB2);
     VPBlockUtils::connectBlocks(R1, R2);
 
     // Successors of R1.
     SmallVector<const VPBlockBase *> FromIterator(
         VPAllSuccessorsIterator<VPBlockBase *>(R1),
         VPAllSuccessorsIterator<VPBlockBase *>::end(R1));
-    EXPECT_EQ(2u, FromIterator.size());
+    EXPECT_EQ(1u, FromIterator.size());
     EXPECT_EQ(R1BB1, FromIterator[0]);
-    EXPECT_EQ(R2, FromIterator[1]);
 
     // Depth-first.
     VPBlockRecursiveTraversalWrapper<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]);