[VPlan] Use recursive traversal iterator in VPSlotTracker.

[fhahn]

Summary

This patch simplifies VPSlotTracker by using the recursive traversal
iterator to traverse all blocks in a VPlan in reverse post-order when
numbering VPValues in a plan.

This depends on a fix to RPOT (D100169). It also extends the traversal
unit tests to check RPOT.

[a.elovikov]

llvm/lib/Transforms/Vectorize/VPlan.cpp

1243

I think that such usage would be the most common one (i.e. skipping the regions). Can we outline it into a separate helper somehow? The first idea coming to my mind is our custom VPlanRPOT class using the regular RPOT as a member and exposing iterators through filter_iterator, but maybe something nicer can be done as well.

[fhahn]

rebased after changes to D100175

[fhahn]

rebased to use utility from D101093 to create an iterator range that only contains VPBasicBlocks.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

1243

I've put up D101093, which adds a helper to turn an iterator range into an iterator range that only includes VPBasicBlocks and also casts them to VPBasicBlock when de-referencing. It should support arbitrary iterators (RPO, depth first, post order), at the cost of having separate versions for const VPBasicBlock * and VPBasicBLock *

[a.elovikov]

LGTM, thanks!

[fhahn]

rebased to use blocksOnly iterator.

llvm/lib/Transforms/Vectorize/VPlan.cpp

VPInterleavedAccessInfo::VPInterleavedAccessInfo(VPlan &Plan,
   visitRegion(cast<VPRegionBlock>(Plan.getEntry()), Old2New, IAI);
 }
 
 void VPSlotTracker::assignSlot(const VPValue *V) {
   assert(Slots.find(V) == Slots.end() && "VPValue already has a slot!");
   Slots[V] = NextSlot++;
 }
 
-void VPSlotTracker::assignSlots(const VPBlockBase *VPBB) {
-  if (auto *Region = dyn_cast<VPRegionBlock>(VPBB))
-    assignSlots(Region);
-  else
-    assignSlots(cast<VPBasicBlock>(VPBB));
-}
-
-void VPSlotTracker::assignSlots(const VPRegionBlock *Region) {
-  ReversePostOrderTraversal<const VPBlockBase *> RPOT(Region->getEntry());
-  for (const VPBlockBase *Block : RPOT)
-    assignSlots(Block);
-}
-
-void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
-  for (const VPRecipeBase &Recipe : *VPBB) {
-    for (VPValue *Def : Recipe.definedValues())
-      assignSlot(Def);
-  }
-}
-
 void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
   for (const VPValue *V : Plan.VPExternalDefs)
     assignSlot(V);
 
   if (Plan.BackedgeTakenCount)
     assignSlot(Plan.BackedgeTakenCount);
 
-  ReversePostOrderTraversal<const VPBlockBase *> RPOT(Plan.getEntry());
-  for (const VPBlockBase *Block : RPOT)
-    assignSlots(Block);
+  ReversePostOrderTraversal<
+      VPBlockRecursiveTraversalWrapper<const VPBlockBase *>>
+      RPOT(VPBlockRecursiveTraversalWrapper<const VPBlockBase *>(
+          Plan.getEntry()));
+  for (const VPBlockBase *Block : RPOT) {
+    auto *VPBB = dyn_cast<VPBasicBlock>(Block);
+    if (!VPBB)
+      continue;
+    for (const VPRecipeBase &Recipe : *VPBB) {
+      for (VPValue *Def : Recipe.definedValues())
+        assignSlot(Def);
+    }
+  }
 }

llvm/lib/Transforms/Vectorize/VPlanValue.h

 
 /// This class can be used to assign consecutive numbers to all VPValues in a
 /// VPlan and allows querying the numbering for printing, similar to the
 /// ModuleSlotTracker for IR values.
 class VPSlotTracker {
   DenseMap<const VPValue *, unsigned> Slots;
   unsigned NextSlot = 0;
 
-  void assignSlots(const VPBlockBase *VPBB);
-  void assignSlots(const VPRegionBlock *Region);
-  void assignSlots(const VPBasicBlock *VPBB);
   void assignSlot(const VPValue *V);
-
   void assignSlots(const VPlan &Plan);
 
 public:
   VPSlotTracker(const VPlan *Plan = nullptr) {
     if (Plan)
       assignSlots(*Plan);
   }
 

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

// 2 consecutive regions.
     EXPECT_EQ(R2BB1, FromIterator[1]);
     EXPECT_EQ(R2, FromIterator[2]);
     EXPECT_EQ(R1BB4, FromIterator[3]);
     EXPECT_EQ(R1BB2, FromIterator[4]);
     EXPECT_EQ(R1BB3, FromIterator[5]);
     EXPECT_EQ(R1BB1, FromIterator[6]);
     EXPECT_EQ(R1, FromIterator[7]);
 
+    ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
+        RPOT(Start);
+    FromIterator.clear();
+    for (VPBlockBase *VPBB : RPOT)
+      FromIterator.push_back(VPBB);
+    EXPECT_EQ(8u, FromIterator.size());
+    EXPECT_EQ(R1, FromIterator[0]);
+    EXPECT_EQ(R1BB1, FromIterator[1]);
+    EXPECT_EQ(R1BB3, FromIterator[2]);
+    EXPECT_EQ(R1BB2, FromIterator[3]);
+    EXPECT_EQ(R1BB4, FromIterator[4]);
+    EXPECT_EQ(R2, FromIterator[5]);
+    EXPECT_EQ(R2BB1, FromIterator[6]);
+    EXPECT_EQ(R2BB2, FromIterator[7]);
+
     // Use Plan to properly clean up created blocks.
     VPlan Plan;
     Plan.setEntry(R1);
   }
 
   // 2 nested regions.
   //  VPBB1
   //    |
//
     EXPECT_EQ(R1BB1, FromIterator[2]);
     EXPECT_EQ(R2, FromIterator[3]);
     EXPECT_EQ(R2BB1, FromIterator[4]);
     EXPECT_EQ(R2BB2, FromIterator[5]);
     EXPECT_EQ(R1BB3, FromIterator[6]);
     EXPECT_EQ(VPBB2, FromIterator[7]);
     EXPECT_EQ(R1BB2, FromIterator[8]);
 
+    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>>
+        RPOT(Start);
+    FromIterator.clear();
+    for (VPBlockBase *VPBB : RPOT)
+      FromIterator.push_back(VPBB);
+    EXPECT_EQ(9u, FromIterator.size());
+    EXPECT_EQ(VPBB1, FromIterator[0]);
+    EXPECT_EQ(R1, FromIterator[1]);
+    EXPECT_EQ(R1BB1, FromIterator[2]);
+    EXPECT_EQ(R1BB2, FromIterator[3]);
+    EXPECT_EQ(R2, FromIterator[4]);
+    EXPECT_EQ(R2BB1, FromIterator[5]);
+    EXPECT_EQ(R2BB2, FromIterator[6]);
+    EXPECT_EQ(R1BB3, FromIterator[7]);
+    EXPECT_EQ(VPBB2, FromIterator[8]);
+
     // Use Plan to properly clean up created blocks.
     VPlan Plan;
     Plan.setEntry(VPBB1);
   }
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 TEST(VPBasicBlockTest, print) {