[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

1268

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

1268

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 VPBasicBlock *VPBB: VPBlockUtils::constBasicBlocksOnly(RPOT))
+    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);
   }