[VPlan] Introduce VPConstant specialization for VPValue

[sguggill]

Summary

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

This change allows us to share the same set of VPConstants 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

llvm/lib/Transforms/Vectorize/VPlan.h

   /// Holds the name of the VPlan, for printing.
   std::string Name;
 
+  /// 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

 
   void setName(const Twine &newName) { Name = newName.str(); }
 
+  /// Create a new VPConstant for \p Const if it doesn't exist or retrieve the
+  /// existing one.
+  VPConstant *getOrCreateVPConstant(Constant *Const) {
+    std::unique_ptr<VPConstant> &UPtr = VPConstants[Const];
+    if (!UPtr)
+      // Const is a new VPConstant to be inserted in the map.
+      UPtr.reset(new VPConstant(Const));
+
+    return UPtr.get();
+  }
+
   /// Add \p VPVal to the pool of external definitions if it's not already
   /// in the pool.
   void addExternalDef(VPValue *VPVal) {

     return map_range(Operands, Fn);
   }
 
+  // Verify that VPConstants are unique in the pool and that the map keys are
+  // consistent with the underlying IR information of each VPConstant.
+  void verifyVPConstants() 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::dump() const { dbgs() << *this << '\n'; }
 #endif
 
+void VPlan::verifyVPConstants() const {
+  SmallPtrSet<const Constant *, 16> ConstantSet;
+  for (const auto &Pair : VPConstants) {
+    const Constant *KeyConst = Pair.first;
+    assert(
+        KeyConst == Pair.second->getConstant() &&
+        "Constant key and VPConstant's underlying Constant must be the same!");
+    // Checking that an element is repeated in a map is unnecessary but it
+    // will catch bugs if the data structure is changed in the future.
+    assert(!ConstantSet.count(KeyConst) && "Repeated VPConstant!");
+    ConstantSet.insert(KeyConst);
+  }
+}
+
 void VPlan::updateDominatorTree(DominatorTree *DT, BasicBlock *LoopPreHeaderBB,
                                 BasicBlock *LoopLatchBB,
                                 BasicBlock *LoopExitBB) {

llvm/lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

 // for *Instruction's operands* and not to create regular VPInstruction's. For
 // the latter, please, look at 'createVPInstructionsForVPBB'.
 VPValue *PlainCFGBuilder::getOrCreateVPOperand(Value *IRVal) {
+  // Constant operand
+  if (Constant *IRConst = dyn_cast<Constant>(IRVal))
+    return Plan.getOrCreateVPConstant(IRConst);
+
   auto VPValIt = IRDef2VPValue.find(IRVal);
   if (VPValIt != IRDef2VPValue.end())
     // Operand has an associated VPInstruction or VPValue that was previously

       assert(isa<BranchInst>(TI) && "Unsupported terminator!");
       auto *Br = cast<BranchInst>(TI);
       Value *BrCond = Br->getCondition();
-      // Look up the branch condition to get the corresponding VPValue
-      // representing the condition bit in VPlan (which may be in another VPBB).
-      assert(IRDef2VPValue.count(BrCond) &&
-             "Missing condition bit in IRDef2VPValue!");
-      VPValue *VPCondBit = IRDef2VPValue[BrCond];
+      VPValue *VPCondBit;
+      if (Constant *ConstBrCond = dyn_cast<Constant>(BrCond)) {
+        // Create new VPConstant for constant branch condition.
+        VPCondBit = Plan.getOrCreateVPConstant(ConstBrCond);
+      } else {
+        // Look up the branch condition to get the corresponding VPValue
+        // representing the condition bit in VPlan (which may be in another
+        // VPBB).
+        assert(IRDef2VPValue.count(BrCond) &&
+               "Missing condition bit in IRDef2VPValue!");
+        VPCondBit = IRDef2VPValue[BrCond];
+      }
 
       // Link successors using condition bit.
       VPBB->setTwoSuccessors(SuccVPBB0, SuccVPBB1, VPCondBit);

   Plan.setEntry(TopRegion);
   LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
 
-  Verifier.verifyHierarchicalCFG(TopRegion);
+  Verifier.verifyHierarchicalCFG(Plan, TopRegion);
 
   // Compute plain CFG dom tree for VPLInfo.
   VPDomTree.recalculate(*TopRegion);

llvm/lib/Transforms/Vectorize/VPlanValue.h

   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.
   enum {
+    VPConstantSC,
     VPValueSC,
     VPVInstructionSC,
     VPVMemoryInstructionSC,

   /// for any other purpose, as the values may change as LLVM evolves.
   unsigned getVPValueID() const { return SubclassID; }
 
-  void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
+  virtual void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const;
   void print(raw_ostream &OS, VPSlotTracker &Tracker) const;
 
   /// Dump the value to stderr (for debugging).

   }
 };
 
+/// This class augments VPValue with constant operands that encapsulates LLVM
+/// Constant information. In the same way as LLVM Constant, VPConstant is
+/// immutable (once created they never change) and are fully shared by
+/// structural equivalence (e.g. i32 7 == i32 7, but i32 7 != i64 7). This means
+/// that two structurally equivalent VPConstants will always have the same
+/// address.
+class VPConstant : public VPValue {
+  // VPlan is currently the context where we hold the pool of VPConstants.
+  friend class VPlan;
+
+protected:
+  VPConstant(Constant *Const) : VPValue(VPValue::VPConstantSC, Const) {}
+
+  /// Return the underlying Constant attached to this VPConstant. This interface
+  /// is similar to getValue() but hides the cast when we are working with
+  /// VPConstant pointers.
+  Constant *getConstant() const {
+    assert(isa<Constant>(UnderlyingVal) &&
+           "Expected Constant as underlying Value.");
+    return cast<Constant>(UnderlyingVal);
+  }
+
+public:
+  VPConstant(const VPConstant &) = delete;
+  VPConstant &operator=(const VPConstant &) const = delete;
+
+  void printAsOperand(raw_ostream &OS, VPSlotTracker &Tracker) const override {
+    OS << "ir<";
+    UnderlyingVal->printAsOperand(OS, false);
+    OS << ">";
+  }
+
+  /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPConstantSC;
+  }
+};
+
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H

llvm/lib/Transforms/Vectorize/VPlanVerifier.h

 
 namespace llvm {
 class VPRegionBlock;
+class VPlan;
 
 /// Struct with utility functions that can be used to check the consistency and
 /// invariants of a VPlan, including the components of its H-CFG.

   /// verification process comprises the following steps:
   /// 1. Region/Block verification: Check the Region/Block verification
   /// invariants for every region in the H-CFG.
-  void verifyHierarchicalCFG(const VPRegionBlock *TopRegion) const;
+  void verifyHierarchicalCFG(const VPlan &Plan,
+                             const VPRegionBlock *TopRegion) const;
 };
 } // namespace llvm
 

llvm/lib/Transforms/Vectorize/VPlanVerifier.cpp

 }
 
 void VPlanVerifier::verifyHierarchicalCFG(
-    const VPRegionBlock *TopRegion) const {
+    const VPlan &Plan, const VPRegionBlock *TopRegion) const {
   if (!EnableHCFGVerifier)
     return;
 
+  Plan.verifyVPConstants();
+
   LLVM_DEBUG(dbgs() << "Verifying VPlan H-CFG.\n");
   assert(!TopRegion->getParent() && "VPlan Top Region should have no parent.");
   verifyRegionRec(TopRegion);

llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp

   EXPECT_EQ(&*Plan, VecBB->getPlan());
 
   auto Iter = VecBB->begin();
-  VPInstruction *Phi = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *Phi = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::PHI, Phi->getOpcode());
+  EXPECT_TRUE(isa<VPConstant>(Phi->getOperand(0)));
 
-  VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *Idx = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());
   EXPECT_EQ(2u, Idx->getNumOperands());
   EXPECT_EQ(Phi, Idx->getOperand(1));
 
-  VPInstruction *Load = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *Load = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::Load, Load->getOpcode());
   EXPECT_EQ(1u, Load->getNumOperands());
   EXPECT_EQ(Idx, Load->getOperand(0));
 
-  VPInstruction *Add = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *Add = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::Add, Add->getOpcode());
   EXPECT_EQ(2u, Add->getNumOperands());
   EXPECT_EQ(Load, Add->getOperand(0));
+  EXPECT_TRUE(isa<VPConstant>(Add->getOperand(1)));
 
-  VPInstruction *Store = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *Store = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::Store, Store->getOpcode());
   EXPECT_EQ(2u, Store->getNumOperands());
   EXPECT_EQ(Add, Store->getOperand(0));
   EXPECT_EQ(Idx, Store->getOperand(1));
 
-  VPInstruction *IndvarAdd = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *IndvarAdd = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode());
   EXPECT_EQ(2u, IndvarAdd->getNumOperands());
   EXPECT_EQ(Phi, IndvarAdd->getOperand(0));
+  EXPECT_TRUE(isa<VPConstant>(IndvarAdd->getOperand(1)));
 
-  VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);
+  VPInstruction *ICmp = cast<VPInstruction>(&*Iter++);
   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
   EXPECT_EQ(2u, ICmp->getNumOperands());
   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));