Template the sparse propagation solver instead of using void pointers

[• dberlin]

Summary

This avoids using void * as the type of the lattice value and ugly casts needed to make that happen.
(If folks want to use references, etc, they can use a reference_wrapper).

[davide]

Pretty cool :)

[mssimpso]

Thanks!

[mssimpso]

Hi Danny,

I didn't think about this previously, but now that AbstractLatticeFunction and SparseSolver are templates, shouldn't we move the contents of the .cpp over to the .h? I'm having trouble instantiating them now with this split implementation.

[• dberlin]

Ah, the joy of not having users to break.
Yes, i expect you will have to move a bunch if not all of these to the header.

llvm/trunk/include/llvm/Analysis/SparsePropagation.h

 
 class Argument;
 class BasicBlock;
 class Constant;
 class Function;
 class Instruction;
 class PHINode;
 class raw_ostream;
-class SparseSolver;
+template <class LatticeVal> class SparseSolver;
 class TerminatorInst;
 class Value;
 template <typename T> class SmallVectorImpl;
 
 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
-/// to specify what the lattice values are and how they handle merges etc.
-/// This gives the client the power to compute lattice values from instructions,
-/// constants, etc.  The requirement is that lattice values must all fit into
-/// a void*.  If a void* is not sufficient, the implementation should use this
-/// pointer to be a pointer into a uniquing set or something.
-///
-class AbstractLatticeFunction {
-public:
-  using LatticeVal = void *;
+/// to specify what the lattice values are and how they handle merges etc.  This
+/// gives the client the power to compute lattice values from instructions,
+/// constants, etc.  The current requirement is that lattice values must be
+/// copyable.  At the moment, nothing tries to avoid copying.
+
 
+template <class LatticeVal> class AbstractLatticeFunction {
 private:
   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
 
 public:
   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
                           LatticeVal untrackedVal) {
     UndefVal = undefVal;
     OverdefinedVal = overdefinedVal;
public:
 
   /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
   /// one that the we want to handle through ComputeInstructionState.
   virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
 
   /// GetConstant - If the specified lattice value is representable as an LLVM
   /// constant value, return it.  Otherwise return null.  The returned value
   /// must be in the same LLVM type as Val.
-  virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
+  virtual Constant *GetConstant(LatticeVal LV, Value *Val,
+                                SparseSolver<LatticeVal> &SS) {
     return nullptr;
   }
 
   /// ComputeArgument - Given a formal argument value, compute and return a
   /// lattice value corresponding to the specified argument.
   virtual LatticeVal ComputeArgument(Argument *I) {
     return getOverdefinedVal(); // always safe
   }
 
   /// MergeValues - Compute and return the merge of the two specified lattice
   /// values.  Merging should only move one direction down the lattice to
   /// guarantee convergence (toward overdefined).
   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
     return getOverdefinedVal(); // always safe, never useful.
   }
 
   /// ComputeInstructionState - Given an instruction and a vector of its operand
   /// values, compute the result value of the instruction.
-  virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
+  virtual LatticeVal ComputeInstructionState(Instruction &I,
+                                             SparseSolver<LatticeVal> &SS) {
     return getOverdefinedVal(); // always safe, never useful.
   }
 
   /// PrintValue - Render the specified lattice value to the specified stream.
   virtual void PrintValue(LatticeVal V, raw_ostream &OS);
 };
 
 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
 /// Propagation with a programmable lattice function.
-class SparseSolver {
-  using LatticeVal = AbstractLatticeFunction::LatticeVal;
+template <class LatticeVal> class SparseSolver {
 
   /// LatticeFunc - This is the object that knows the lattice and how to do
   /// compute transfer functions.
-  AbstractLatticeFunction *LatticeFunc;
+  AbstractLatticeFunction<LatticeVal> *LatticeFunc;
 
   DenseMap<Value *, LatticeVal> ValueState;   // The state each value is in.
   SmallPtrSet<BasicBlock *, 16> BBExecutable; // The bbs that are executable.
 
   std::vector<Instruction *> InstWorkList; // Worklist of insts to process.
 
   std::vector<BasicBlock *> BBWorkList; // The BasicBlock work list
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   std::set<Edge> KnownFeasibleEdges;
 
 public:
-  explicit SparseSolver(AbstractLatticeFunction *Lattice)
+  explicit SparseSolver(AbstractLatticeFunction<LatticeVal> *Lattice)
       : LatticeFunc(Lattice) {}
   SparseSolver(const SparseSolver &) = delete;
   SparseSolver &operator=(const SparseSolver &) = delete;
   ~SparseSolver() { delete LatticeFunc; }
 
   /// Solve - Solve for constants and executable blocks.
   void Solve(Function &F);
 
   void Print(Function &F, raw_ostream &OS) const;
 
   /// getLatticeState - Return the LatticeVal object that corresponds to the
   /// value.  If an value is not in the map, it is returned as untracked,
   /// unlike the getOrInitValueState method.
   LatticeVal getLatticeState(Value *V) const {
-    DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
+    auto I = ValueState.find(V);
     return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
   }
 
   /// getOrInitValueState - Return the LatticeVal object that corresponds to the
   /// value, initializing the value's state if it hasn't been entered into the
   /// map yet.   This function is necessary because not all values should start
   /// out in the underdefined state... Arguments should be overdefined, and
   /// constants should be marked as constants.

llvm/trunk/lib/Analysis/SparsePropagation.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "sparseprop"
 
 //===----------------------------------------------------------------------===//
 //                  AbstractLatticeFunction Implementation
 //===----------------------------------------------------------------------===//
 
-AbstractLatticeFunction::~AbstractLatticeFunction() = default;
+template <class LatticeVal>
+AbstractLatticeFunction<LatticeVal>::~AbstractLatticeFunction() = default;
 
 /// PrintValue - Render the specified lattice value to the specified stream.
-void AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) {
+template <class LatticeVal>
+void AbstractLatticeFunction<LatticeVal>::PrintValue(LatticeVal V,
+                                                     raw_ostream &OS) {
   if (V == UndefVal)
     OS << "undefined";
   else if (V == OverdefinedVal)
     OS << "overdefined";
   else if (V == UntrackedVal)
     OS << "untracked";
   else
     OS << "unknown lattice value";
 }
 
 //===----------------------------------------------------------------------===//
 //                          SparseSolver Implementation
 //===----------------------------------------------------------------------===//
 
 /// getOrInitValueState - Return the LatticeVal object that corresponds to the
 /// value, initializing the value's state if it hasn't been entered into the
 /// map yet.   This function is necessary because not all values should start
 /// out in the underdefined state... Arguments should be overdefined, and
 /// constants should be marked as constants.
-SparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) {
-  DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
+template <class LatticeVal>
+LatticeVal SparseSolver<LatticeVal>::getOrInitValueState(Value *V) {
+  auto I = ValueState.find(V);
   if (I != ValueState.end()) return I->second;  // Common case, in the map
   
   LatticeVal LV;
   if (LatticeFunc->IsUntrackedValue(V))
     return LatticeFunc->getUntrackedVal();
   else if (Constant *C = dyn_cast<Constant>(V))
     LV = LatticeFunc->ComputeConstant(C);
   else if (Argument *A = dyn_cast<Argument>(V))
     LV = LatticeFunc->ComputeArgument(A);
   else if (!isa<Instruction>(V))
     // All other non-instructions are overdefined.
     LV = LatticeFunc->getOverdefinedVal();
   else
     // All instructions are underdefined by default.
     LV = LatticeFunc->getUndefVal();
   
   // If this value is untracked, don't add it to the map.
   if (LV == LatticeFunc->getUntrackedVal())
     return LV;
   return ValueState[V] = LV;
 }
 
 /// UpdateState - When the state for some instruction is potentially updated,
 /// this function notices and adds I to the worklist if needed.
-void SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) {
-  DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst);
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::UpdateState(Instruction &Inst, LatticeVal V) {
+  auto I = ValueState.find(&Inst);
   if (I != ValueState.end() && I->second == V)
     return;  // No change.
   
   // An update.  Visit uses of I.
   ValueState[&Inst] = V;
   InstWorkList.push_back(&Inst);
 }
 
 /// MarkBlockExecutable - This method can be used by clients to mark all of
 /// the blocks that are known to be intrinsically live in the processed unit.
-void SparseSolver::MarkBlockExecutable(BasicBlock *BB) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::MarkBlockExecutable(BasicBlock *BB) {
   DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
   BBExecutable.insert(BB);   // Basic block is executable!
   BBWorkList.push_back(BB);  // Add the block to the work list!
 }
 
 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
 /// work list if it is not already executable...
-void SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::markEdgeExecutable(BasicBlock *Source,
+                                                  BasicBlock *Dest) {
   if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
     return;  // This edge is already known to be executable!
   
   DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
         << " -> " << Dest->getName() << "\n");
 
   if (BBExecutable.count(Dest)) {
     // The destination is already executable, but we just made an edge
     // feasible that wasn't before.  Revisit the PHI nodes in the block
     // because they have potentially new operands.
     for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
       visitPHINode(*cast<PHINode>(I));
   } else {
     MarkBlockExecutable(Dest);
   }
 }
 
 /// getFeasibleSuccessors - Return a vector of booleans to indicate which
 /// successors are reachable from a given terminator instruction.
-void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI,
-                                         SmallVectorImpl<bool> &Succs,
-                                         bool AggressiveUndef) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::getFeasibleSuccessors(
+    TerminatorInst &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) {
   Succs.resize(TI.getNumSuccessors());
   if (TI.getNumSuccessors() == 0) return;
   
   if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
     if (BI->isUnconditional()) {
       Succs[0] = true;
       return;
     }
if (!C || !isa<ConstantInt>(C)) {
     return;
   }
   SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
   Succs[Case.getSuccessorIndex()] = true;
 }
 
 /// isEdgeFeasible - Return true if the control flow edge from the 'From'
 /// basic block to the 'To' basic block is currently feasible...
-bool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To,
+template <class LatticeVal>
+bool SparseSolver<LatticeVal>::isEdgeFeasible(BasicBlock *From, BasicBlock *To,
                                               bool AggressiveUndef) {
   SmallVector<bool, 16> SuccFeasible;
   TerminatorInst *TI = From->getTerminator();
   getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
   
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     if (TI->getSuccessor(i) == To && SuccFeasible[i])
       return true;
   
   return false;
 }
 
-void SparseSolver::visitTerminatorInst(TerminatorInst &TI) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::visitTerminatorInst(TerminatorInst &TI) {
   SmallVector<bool, 16> SuccFeasible;
   getFeasibleSuccessors(TI, SuccFeasible, true);
   
   BasicBlock *BB = TI.getParent();
   
   // Mark all feasible successors executable...
   for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
     if (SuccFeasible[i])
       markEdgeExecutable(BB, TI.getSuccessor(i));
 }
 
-void SparseSolver::visitPHINode(PHINode &PN) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::visitPHINode(PHINode &PN) {
   // The lattice function may store more information on a PHINode than could be
   // computed from its incoming values.  For example, SSI form stores its sigma
   // functions as PHINodes with a single incoming value.
   if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
     LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this);
     if (IV != LatticeFunc->getUntrackedVal())
       UpdateState(PN, IV);
     return;
for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     if (PNIV == Overdefined)
       break;  // Rest of input values don't matter.
   }
 
   // Update the PHI with the compute value, which is the merge of the inputs.
   UpdateState(PN, PNIV);
 }
 
-void SparseSolver::visitInst(Instruction &I) {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::visitInst(Instruction &I) {
   // PHIs are handled by the propagation logic, they are never passed into the
   // transfer functions.
   if (PHINode *PN = dyn_cast<PHINode>(&I))
     return visitPHINode(*PN);
   
   // Otherwise, ask the transfer function what the result is.  If this is
   // something that we care about, remember it.
   LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this);
   if (IV != LatticeFunc->getUntrackedVal())
     UpdateState(I, IV);
   
   if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I))
     visitTerminatorInst(*TI);
 }
 
-void SparseSolver::Solve(Function &F) {
+template <class LatticeVal> void SparseSolver<LatticeVal>::Solve(Function &F) {
   MarkBlockExecutable(&F.getEntryBlock());
   
   // Process the work lists until they are empty!
   while (!BBWorkList.empty() || !InstWorkList.empty()) {
     // Process the instruction work list.
     while (!InstWorkList.empty()) {
       Instruction *I = InstWorkList.back();
       InstWorkList.pop_back();
while (!BBWorkList.empty()) {
       // Notify all instructions in this basic block that they are newly
       // executable.
       for (Instruction &I : *BB)
         visitInst(I);
     }
   }
 }
 
-void SparseSolver::Print(Function &F, raw_ostream &OS) const {
+template <class LatticeVal>
+void SparseSolver<LatticeVal>::Print(Function &F, raw_ostream &OS) const {
   OS << "\nFUNCTION: " << F.getName() << "\n";
   for (auto &BB : F) {
     if (!BBExecutable.count(&BB))
       OS << "INFEASIBLE: ";
     OS << "\t";
     if (BB.hasName())
       OS << BB.getName() << ":\n";
     else