[VPlan] Use VPUser to manage CondBit

[fhahn]

Summary

VP blocks keep track of a condition, which is a VPValue. This patch
updates VPBlockBase to manage the value using VPUser, so
replaceAllUsesWith properly updates the condition bit as well.

This is required to enable VP2VP transformations and it helps with
simplifying some of the code required to manage condition bits.

[a.elovikov]

Hi Florian, I'm starting to familiarize myself with VPlan and wonder if that is a short/mid-term solution or something that is expected to be a long-term.

Have you considered modeling the edges using terminator instructions similar to what regular LLVM IR does? I see the following potential advantages:

1. More straightforward thinking about dominance relation/theoretical conception. CondBit might be defined inside the VPBB itself and in order to have that use not to break the dominance we need the VPBB "defined" at its end, which might be slightly confusing. I'm not sure if that can lead to any practical difficulties though.
2. By having a dedicated terminator we can put some special semantics/operation on the condition into that terminator. For example, VPBranchInst instruction for a regular branch on a uniform condition and something like VPBranchIfAllZero/VPBranchIfAllOnes(mask) when condition is varying. Of course, the same can be encoded into the VPBB itself, but the explicit instruction might be considered slightly more readable.
3. Potential simplification of successors/predecessors handling - that will be done by the def/use edges.

A big disadvantage is, obviously, that the change would be more invasive and the benefits aren't really too "objective". Still, it might be worth considering this direction.

What do you think?

[fhahn]

In D95382#2528700, @a.elovikov wrote:

Hi Florian, I'm starting to familiarize myself with VPlan and wonder if that is a short/mid-term solution or something that is expected to be a long-term.

Hi, that's great!

Have you considered modeling the edges using terminator instructions similar to what regular LLVM IR does? I see the following potential advantages:

1. More straightforward thinking about dominance relation/theoretical conception. CondBit might be defined inside the VPBB itself and in order to have that use not to break the dominance we need the VPBB "defined" at its end, which might be slightly confusing. I'm not sure if that can lead to any practical difficulties though.
2. By having a dedicated terminator we can put some special semantics/operation on the condition into that terminator. For example, VPBranchInst instruction for a regular branch on a uniform condition and something like VPBranchIfAllZero/VPBranchIfAllOnes(mask) when condition is varying. Of course, the same can be encoded into the VPBB itself, but the explicit instruction might be considered slightly more readable.
3. Potential simplification of successors/predecessors handling - that will be done by the def/use edges.

A big disadvantage is, obviously, that the change would be more invasive and the benefits aren't really too "objective". Still, it might be worth considering this direction.

What do you think?

Modeling terminators explicitly would certainly make a few things a bit nicer.

But I think in the short term, the amount of churn required to change that would not be worth it. The CondBit use in VPBlockBase is one of the few remaining cases not in the VPlan def-use chains and I think it would be preferable to get this wrapped up ASAP and re-visit the issue of explicit terminators in the future.

[gilr]

llvm/lib/Transforms/Vectorize/VPlan.h

381

Would it suffice for VPBlockBase to have a VPUser rather than being one? (may also align more easily with terminators in the future)

[fhahn]

Do not make VPBlockBase a VPUser yet, use a VPUser to manage CondBit instead, as suggested.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

381

Good idea, I updated the code to use a VPUser member to just manage the CondBit for now. There is at least VPValue *Predicate which should be updated before making VPBlockBase a VPUser, if we ever want to do that.

[gilr]

llvm/lib/Transforms/Vectorize/VPlan.h

401

Nit: IIRC the condition bit is only used by the native path (LV uses the BranchOnMask recipe instead), but LV still sets the condition bit in the call to setTwoSuccessors in insertTwoBlocksAfter, which will now create a redundant user of the condition bit. Not sure it is/will be a problem, but we could pass nullptr there to avoid it (requires removing the assert in setTwoSuccessors).

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.h

401

I am not sure I follow directly here. Do you mean using VPUser * and allocate it on demand? I think the extra field is currently not worth the trouble, and hopefully we will be able to unify the VPNative & regular paths in the future :)

llvm/lib/Transforms/Vectorize/VPlan.h

struct VPTransformState {
   /// Hold a pointer to InnerLoopVectorizer to reuse its IR generation methods.
   InnerLoopVectorizer *ILV;
 
   VPCallback &Callback;
 };
 
 /// VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
 /// A VPBlockBase can be either a VPBasicBlock or a VPRegionBlock.
-class VPBlockBase {
+class VPBlockBase : public VPUser {
   friend class VPBlockUtils;
 
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   /// An optional name for the block.
   std::string Name;
 
   /// The immediate VPRegionBlock which this VPBlockBase belongs to, or null if
   /// it is a topmost VPBlockBase.
   VPRegionBlock *Parent = nullptr;
 
   /// List of predecessor blocks.
   SmallVector<VPBlockBase *, 1> Predecessors;
 
   /// List of successor blocks.
   SmallVector<VPBlockBase *, 1> Successors;
 
-  /// Successor selector, null for zero or single successor blocks.
-  VPValue *CondBit = nullptr;
-
   /// Current block predicate - null if the block does not need a predicate.
   VPValue *Predicate = nullptr;
 
   /// VPlan containing the block. Can only be set on the entry block of the
   /// plan.
   VPlan *Plan = nullptr;
 
   /// Add \p Successor as the last successor to this block.
   void appendSuccessor(VPBlockBase *Successor) {
     assert(Successor && "Cannot add nullptr successor!");
     Successors.push_back(Successor);
class VPBlockBase : public VPUser {
   void removeSuccessor(VPBlockBase *Successor) {
     auto Pos = find(Successors, Successor);
     assert(Pos && "Successor does not exist");
     Successors.erase(Pos);
   }
 
 protected:
   VPBlockBase(const unsigned char SC, const std::string &N)
-      : SubclassID(SC), Name(N) {}
+      : VPUser(), SubclassID(SC), Name(N) {}
 
 public:
   /// An enumeration for keeping track of the concrete subclass of VPBlockBase
   /// that are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPBlockBase objects. They are used for concrete
   /// type identification.
   using VPBlockTy = enum { VPBasicBlockSC, VPRegionBlockSC };
 
public:
   /// predecessor. Otherwise return a null pointer.
   VPBlockBase *getSinglePredecessor() const {
     return (Predecessors.size() == 1 ? *Predecessors.begin() : nullptr);
   }
 
   size_t getNumSuccessors() const { return Successors.size(); }
   size_t getNumPredecessors() const { return Predecessors.size(); }
 
+  void dump() const;
+
   /// An Enclosing Block of a block B is any block containing B, including B
   /// itself. \return the closest enclosing block starting from "this", which
   /// has successors. \return the root enclosing block if all enclosing blocks
   /// have no successors.
   VPBlockBase *getEnclosingBlockWithSuccessors();
 
   /// \return the closest enclosing block starting from "this", which has
   /// predecessors. \return the root enclosing block if all enclosing blocks
public:
 
   /// \return the hierarchical predecessor of this VPBlockBase if it has a
   /// single hierarchical predecessor. Otherwise return a null pointer.
   VPBlockBase *getSingleHierarchicalPredecessor() {
     return getEnclosingBlockWithPredecessors()->getSinglePredecessor();
   }
 
   /// \return the condition bit selecting the successor.
-  VPValue *getCondBit() { return CondBit; }
+  VPValue *getCondBit() {
+    if (getNumOperands())
+      return getOperand(0);
+    return nullptr;
+  }
 
-  const VPValue *getCondBit() const { return CondBit; }
+  const VPValue *getCondBit() const {
+    if (getNumOperands())
+      return getOperand(0);
+    return nullptr;
+  }
 
-  void setCondBit(VPValue *CV) { CondBit = CV; }
+  void setCondBit(VPValue *CV) {
+    if (!CV) {
+      if (getNumOperands() == 1)
+        removeLastOperand();
+      return;
+    }
+    if (getNumOperands() == 1)
+      setOperand(0, CV);
+    else
+      addOperand(CV);
+  }
 
   VPValue *getPredicate() { return Predicate; }
 
   const VPValue *getPredicate() const { return Predicate; }
 
   void setPredicate(VPValue *Pred) { Predicate = Pred; }
 
   /// Set a given VPBlockBase \p Successor as the single successor of this
   /// VPBlockBase. This VPBlockBase is not added as predecessor of \p Successor.
   /// This VPBlockBase must have no successors.
   void setOneSuccessor(VPBlockBase *Successor) {
     assert(Successors.empty() && "Setting one successor when others exist.");
     appendSuccessor(Successor);
   }
 
   /// Set two given VPBlockBases \p IfTrue and \p IfFalse to be the two
   /// successors of this VPBlockBase. \p Condition is set as the successor
   /// selector. This VPBlockBase is not added as predecessor of \p IfTrue or \p
   /// IfFalse. This VPBlockBase must have no successors.
   void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
                         VPValue *Condition) {
     assert(Successors.empty() && "Setting two successors when others exist.");
     assert(Condition && "Setting two successors without condition!");
-    CondBit = Condition;
+    setCondBit(Condition);
     appendSuccessor(IfTrue);
     appendSuccessor(IfFalse);
   }
 
   /// Set each VPBasicBlock in \p NewPreds as predecessor of this VPBlockBase.
   /// This VPBlockBase must have no predecessors. This VPBlockBase is not added
   /// as successor of any VPBasicBlock in \p NewPreds.
   void setPredecessors(ArrayRef<VPBlockBase *> NewPreds) {
     assert(Predecessors.empty() && "Block predecessors already set.");
     for (auto *Pred : NewPreds)
       appendPredecessor(Pred);
   }
 
   /// Remove all the predecessor of this block.
   void clearPredecessors() { Predecessors.clear(); }
 
   /// Remove all the successors of this block and set to null its condition bit
   void clearSuccessors() {
     Successors.clear();
-    CondBit = nullptr;
+    setCondBit(nullptr);
   }
 
   /// The method which generates the output IR that correspond to this
   /// VPBlockBase, thereby "executing" the VPlan.
   virtual void execute(struct VPTransformState *State) = 0;
 
   /// Delete all blocks reachable from a given VPBlockBase, inclusive.
   static void deleteCFG(VPBlockBase *Entry);
class VPlan {
 
   /// Contains all VPValues that been allocated by addVPValue directly and need
   /// to be free when the plan's destructor is called.
   SmallVector<VPValue *, 16> VPValuesToFree;
 
   /// Holds the VPLoopInfo analysis for this VPlan.
   VPLoopInfo VPLInfo;
 
-  /// Holds the condition bit values built during VPInstruction to VPRecipe transformation.
-  SmallVector<VPValue *, 4> VPCBVs;
-
 public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {
     if (Entry)
       Entry->setPlan(this);
   }
 
   ~VPlan() {
     if (Entry) {
       VPValue DummyValue;
       for (VPBlockBase *Block : depth_first(Entry))
         Block->dropAllReferences(&DummyValue);
 
       VPBlockBase::deleteCFG(Entry);
     }
     for (VPValue *VPV : VPValuesToFree)
       delete VPV;
     if (BackedgeTakenCount)
       delete BackedgeTakenCount;
     for (VPValue *Def : VPExternalDefs)
       delete Def;
-    for (VPValue *CBV : VPCBVs)
-      delete CBV;
   }
 
   /// Generate the IR code for this VPlan.
   void execute(struct VPTransformState *State);
 
   VPBlockBase *getEntry() { return Entry; }
   const VPBlockBase *getEntry() const { return Entry; }
 
public:
   void setName(const Twine &newName) { Name = newName.str(); }
 
   /// Add \p VPVal to the pool of external definitions if it's not already
   /// in the pool.
   void addExternalDef(VPValue *VPVal) {
     VPExternalDefs.insert(VPVal);
   }
 
-  /// Add \p CBV to the vector of condition bit values.
-  void addCBV(VPValue *CBV) {
-    VPCBVs.push_back(CBV);
-  }
-
   void addVPValue(Value *V) {
     assert(V && "Trying to add a null Value to VPlan");
     assert(!Value2VPValue.count(V) && "Value already exists in VPlan");
     VPValue *VPV = new VPValue(V);
     Value2VPValue[V] = VPV;
     VPValuesToFree.push_back(VPV);
   }
 

llvm/lib/Transforms/Vectorize/VPlan.cpp

void VPSlotTracker::assignSlots(const VPBasicBlock *VPBB) {
   }
 }
 
 void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
   for (const VPValue *V : Plan.VPExternalDefs)
     assignSlot(V);
 
-  for (const VPValue *V : Plan.VPCBVs)
-    assignSlot(V);
-
   if (Plan.BackedgeTakenCount)
     assignSlot(Plan.BackedgeTakenCount);
 
   ReversePostOrderTraversal<const VPBlockBase *> RPOT(Plan.getEntry());
   for (const VPBlockBase *Block : RPOT)
     assignSlots(Block);
 }

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

VPRegionBlock *PlainCFGBuilder::buildPlainCFG() {
   // based on predecessors traversal.
 
   // Loop PH needs to be explicitly visited since it's not taken into account by
   // LoopBlocksDFS.
   BasicBlock *PreheaderBB = TheLoop->getLoopPreheader();
   assert((PreheaderBB->getTerminator()->getNumSuccessors() == 1) &&
          "Unexpected loop preheader");
   VPBasicBlock *PreheaderVPBB = getOrCreateVPBB(PreheaderBB);
-  createVPInstructionsForVPBB(PreheaderVPBB, PreheaderBB);
+  for (auto &I : *PreheaderBB) {
+    if (I.getType()->isVoidTy())
+      continue;
+    VPValue *VPV = new VPValue(&I);
+    Plan.addExternalDef(VPV);
+    IRDef2VPValue[&I] = VPV;
+  }
   // Create empty VPBB for Loop H so that we can link PH->H.
   VPBlockBase *HeaderVPBB = getOrCreateVPBB(TheLoop->getHeader());
   // Preheader's predecessors will be set during the loop RPO traversal below.
   PreheaderVPBB->setOneSuccessor(HeaderVPBB);
 
   LoopBlocksRPO RPO(TheLoop);
   RPO.perform(LI);
 

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

 void VPlanTransforms::VPInstructionsToVPRecipes(
     Loop *OrigLoop, VPlanPtr &Plan,
     LoopVectorizationLegality::InductionList &Inductions,
     SmallPtrSetImpl<Instruction *> &DeadInstructions) {
 
   auto *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
   ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
 
-  // Condition bit VPValues get deleted during transformation to VPRecipes.
-  // Create new VPValues and save away as condition bits. These will be deleted
-  // after finalizing the vector IR basic blocks.
-  for (VPBlockBase *Base : RPOT) {
-    VPBasicBlock *VPBB = Base->getEntryBasicBlock();
-    if (auto *CondBit = VPBB->getCondBit()) {
-      auto *NCondBit = new VPValue(CondBit->getUnderlyingValue());
-      VPBB->setCondBit(NCondBit);
-      Plan->addCBV(NCondBit);
-    }
-  }
   for (VPBlockBase *Base : RPOT) {
     // Do not widen instructions in pre-header and exit blocks.
     if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
       continue;
 
     VPBasicBlock *VPBB = Base->getEntryBasicBlock();
     // Introduce each ingredient into VPlan.
     for (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {

llvm/lib/Transforms/Vectorize/VPlanValue.h

public:
   }
 
   void setOperand(unsigned I, VPValue *New) {
     Operands[I]->removeUser(*this);
     Operands[I] = New;
     New->addUser(*this);
   }
 
+  void removeLastOperand() {
+    VPValue *Op = Operands.pop_back_val();
+    Op->removeUser(*this);
+  }
+
   typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
   typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
   typedef iterator_range<operand_iterator> operand_range;
   typedef iterator_range<const_operand_iterator> const_operand_range;
 
   operand_iterator op_begin() { return Operands.begin(); }
   const_operand_iterator op_begin() const { return Operands.begin(); }
   operand_iterator op_end() { return Operands.end(); }

 
 class VPlan;
 class VPBasicBlock;
 class VPRegionBlock;
 
 /// 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);