[VPlan] Introduce VPExternalDef specialization for VPValue

[sguggill]

Summary

The changes here introduce VPExternalDef specialization for VPValues. When constructing VPlan for a candidate loop in the native path, we now create a VPExternalDef when the corresponding underlying value is defined outside the candidate loop.

This change allows us to share the same set of VPExternalDefs in different VPlans constructed for a candidate loop. The sub-class can also be used to infer a VPValue uniformity in VPlan based divergence analysis. These changes will be posted in subsequent follow up patches.

[sguggill]

ping

[fhahn]

Satish, did you see the recent changes to VPValue, which allows for easy distinction if the value is a live-in or defined in a plan? D92281 added a VPValue::getLiveInIRValue member to access live-in IR values and VPValue::getDef() can be used to check if the value is defined inside a plan. It returns nullptr for live-ins. Given that, I am not sure if the extra class provides enough benefits to justify the additional complexity?

[sguggill]

In D94426#2518215, @fhahn wrote:

Satish, did you see the recent changes to VPValue, which allows for easy distinction if the value is a live-in or defined in a plan? D92281 added a VPValue::getLiveInIRValue member to access live-in IR values and VPValue::getDef() can be used to check if the value is defined inside a plan. It returns nullptr for live-ins. Given that, I am not sure if the extra class provides enough benefits to justify the additional complexity?

Hi Florian, I will try to refactor these patches using the recent VPValue changes. Thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

   /// Holds all the VPConstants created for this VPlan.
   DenseMap<Constant *, std::unique_ptr<VPConstant>> VPConstants;
 
-  /// Holds all the external definitions created for this VPlan.
-  // TODO: Introduce a specific representation for external definitions in
-  // VPlan. External definitions must be immutable and hold a pointer to its
-  // underlying IR that will be used to implement its structural comparison
-  // (operators '==' and '<').
-  SmallPtrSet<VPValue *, 16> VPExternalDefs;
+  /// Holds all the external definitions representing an underlying Value
+  /// in this VPlan. CFGBuilder ensures these are unique.
+  SmallVector<std::unique_ptr<VPExternalDef>, 16> VPExternalDefs;
 
   /// Represents the backedge taken count of the original loop, for folding
   /// the tail.

       delete VPV;
     if (BackedgeTakenCount)
       delete BackedgeTakenCount;
-    for (VPValue *Def : VPExternalDefs)
-      delete Def;
     for (VPValue *CBV : VPCBVs)
       delete CBV;
   }

     return UPtr.get();
   }
 
-  /// Add \p VPVal to the pool of external definitions if it's not already
-  /// in the pool.
-  void addExternalDef(VPValue *VPVal) {
-    VPExternalDefs.insert(VPVal);
+  /// Create a VPExternalDef for a given Value \p ExtDef.
+  VPExternalDef *getVPExternalDef(Value *ExtDef) {
+    VPExternalDefs.emplace_back(new VPExternalDef(ExtDef));
+    return VPExternalDefs.back().get();
   }
 
   /// Add \p CBV to the vector of condition bit values.

   // consistent with the underlying IR information of each VPConstant.
   void verifyVPConstants() const;
 
+  // Verify that VPExternalDefs are unique in the pool.
+  void verifyVPExternalDefs() const;
+
 private:
   /// Add to the given dominator tree the header block and every new basic block
   /// that was created between it and the latch block, inclusive.

llvm/lib/Transforms/Vectorize/VPlan.cpp

   }
 }
 
+void VPlan::verifyVPExternalDefs() const {
+  SmallPtrSet<const Value *, 16> ValueSet;
+  for (const auto &Def : VPExternalDefs) {
+    const Value *KeyVal = Def->getUnderlyingValue();
+    assert(!ValueSet.count(KeyVal) && "Repeated VPExternalDef!");
+    ValueSet.insert(KeyVal);
+  }
+}
+
 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
                                 BasicBlock *LoopLatchBB,
                                 BasicBlock *LoopExitBB) {

 
 void VPSlotTracker::assignSlots(const VPlan &Plan) {
 
-  for (const VPValue *V : Plan.VPExternalDefs)
-    assignSlot(V);
-
   for (auto &E : Plan.Value2VPValue)
     if (!isa<VPInstruction>(E.second))
       assignSlot(E.second);

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

 
   // A and B: Create VPValue and add it to the pool of external definitions and
   // to the Value->VPValue map.
-  VPValue *NewVPVal = new VPValue(IRVal);
-  Plan.addExternalDef(NewVPVal);
-  IRDef2VPValue[IRVal] = NewVPVal;
-  return NewVPVal;
+  VPExternalDef *ExtDef = Plan.getVPExternalDef(IRVal);
+  IRDef2VPValue[IRVal] = ExtDef;
+  return ExtDef;
 }
 
 // Create new VPInstructions in a VPBasicBlock, given its BasicBlock

llvm/lib/Transforms/Vectorize/VPlanValue.h

   /// type identification.
   enum {
     VPConstantSC,
+    VPExternalDefSC,
     VPValueSC,
     VPVInstructionSC,
     VPVMemoryInstructionSC,

   }
 };
 
+/// This class augments VPValue with definitions that happen outside of the
+/// top region represented in VPlan. Similar to VPConstants and Constants,
+/// VPExternalDefs are immutable (once created they never change) and are fully
+/// shared by structural equivalence (e.g. i32 %param0 == i32 %param0). They
+/// must be created through the VPlan::getVPExternalDef interface, to guarantee
+/// that only one instance of each external definition is created.
+class VPExternalDef : public VPValue {
+  // VPlan is currently the context where the pool of VPExternalDefs is held.
+  friend class VPlan;
+
+private:
+  // Construct a VPExternalDef given a Value \p ExtVal.
+  VPExternalDef(Value *ExtVal) : VPValue(VPValue::VPExternalDefSC, ExtVal) {}
+
+public:
+  VPExternalDef(const VPExternalDef &) = delete;
+  VPExternalDef &operator=(const VPExternalDef &) const = delete;
+
+  void printAsOperand(raw_ostream &OS) const {
+    assert(UnderlyingVal && "Expected underlying value!");
+    UnderlyingVal->printAsOperand(OS);
+  }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPExternalDefSC;
+  }
+};
+
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

     return;
 
   Plan.verifyVPConstants();
+  Plan.verifyVPExternalDefs();
 
   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

   VPInstruction *Idx = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());
   EXPECT_EQ(2u, Idx->getNumOperands());
+  EXPECT_TRUE(isa<VPExternalDef>(Idx->getOperand(0)));
   EXPECT_EQ(Phi, Idx->getOperand(1));
 
   VPInstruction *Load = cast<VPInstruction>(&*Iter++);

   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
   EXPECT_EQ(2u, ICmp->getNumOperands());
   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));
+  EXPECT_TRUE(isa<VPExternalDef>(ICmp->getOperand(1)));
   EXPECT_EQ(VecBB->getCondBit(), ICmp);
 
   // Add an external value to check we do not print the list of external values,