Index: include/llvm/Analysis/SparsePropagation.h =================================================================== --- include/llvm/Analysis/SparsePropagation.h +++ include/llvm/Analysis/SparsePropagation.h @@ -30,22 +30,19 @@ class Instruction; class PHINode; class raw_ostream; -class SparseSolver; +template class SparseSolver; class TerminatorInst; class Value; template 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 AbstractLatticeFunction { private: LatticeVal UndefVal, OverdefinedVal, UntrackedVal; @@ -81,7 +78,8 @@ /// 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 &SS) { return nullptr; } @@ -100,7 +98,8 @@ /// 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 &SS) { return getOverdefinedVal(); // always safe, never useful. } @@ -110,12 +109,11 @@ /// 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 SparseSolver { /// LatticeFunc - This is the object that knows the lattice and how to do /// compute transfer functions. - AbstractLatticeFunction *LatticeFunc; + AbstractLatticeFunction *LatticeFunc; DenseMap ValueState; // The state each value is in. SmallPtrSet BBExecutable; // The bbs that are executable. @@ -130,7 +128,7 @@ std::set KnownFeasibleEdges; public: - explicit SparseSolver(AbstractLatticeFunction *Lattice) + explicit SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {} SparseSolver(const SparseSolver &) = delete; SparseSolver &operator=(const SparseSolver &) = delete; @@ -145,7 +143,7 @@ /// value. If an value is not in the map, it is returned as untracked, /// unlike the getOrInitValueState method. LatticeVal getLatticeState(Value *V) const { - DenseMap::const_iterator I = ValueState.find(V); + auto I = ValueState.find(V); return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); } Index: lib/Analysis/SparsePropagation.cpp =================================================================== --- lib/Analysis/SparsePropagation.cpp +++ lib/Analysis/SparsePropagation.cpp @@ -36,10 +36,13 @@ // AbstractLatticeFunction Implementation //===----------------------------------------------------------------------===// -AbstractLatticeFunction::~AbstractLatticeFunction() = default; +template +AbstractLatticeFunction::~AbstractLatticeFunction() = default; /// PrintValue - Render the specified lattice value to the specified stream. -void AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) { +template +void AbstractLatticeFunction::PrintValue(LatticeVal V, + raw_ostream &OS) { if (V == UndefVal) OS << "undefined"; else if (V == OverdefinedVal) @@ -59,8 +62,9 @@ /// 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::iterator I = ValueState.find(V); +template +LatticeVal SparseSolver::getOrInitValueState(Value *V) { + auto I = ValueState.find(V); if (I != ValueState.end()) return I->second; // Common case, in the map LatticeVal LV; @@ -85,8 +89,9 @@ /// 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::iterator I = ValueState.find(&Inst); +template +void SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) { + auto I = ValueState.find(&Inst); if (I != ValueState.end() && I->second == V) return; // No change. @@ -97,7 +102,8 @@ /// 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 +void SparseSolver::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! @@ -105,7 +111,9 @@ /// 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 +void SparseSolver::markEdgeExecutable(BasicBlock *Source, + BasicBlock *Dest) { if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second) return; // This edge is already known to be executable! @@ -125,9 +133,9 @@ /// getFeasibleSuccessors - Return a vector of booleans to indicate which /// successors are reachable from a given terminator instruction. -void SparseSolver::getFeasibleSuccessors(TerminatorInst &TI, - SmallVectorImpl &Succs, - bool AggressiveUndef) { +template +void SparseSolver::getFeasibleSuccessors( + TerminatorInst &TI, SmallVectorImpl &Succs, bool AggressiveUndef) { Succs.resize(TI.getNumSuccessors()); if (TI.getNumSuccessors() == 0) return; @@ -208,8 +216,9 @@ /// 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, - bool AggressiveUndef) { +template +bool SparseSolver::isEdgeFeasible(BasicBlock *From, BasicBlock *To, + bool AggressiveUndef) { SmallVector SuccFeasible; TerminatorInst *TI = From->getTerminator(); getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef); @@ -221,7 +230,8 @@ return false; } -void SparseSolver::visitTerminatorInst(TerminatorInst &TI) { +template +void SparseSolver::visitTerminatorInst(TerminatorInst &TI) { SmallVector SuccFeasible; getFeasibleSuccessors(TI, SuccFeasible, true); @@ -233,7 +243,8 @@ markEdgeExecutable(BB, TI.getSuccessor(i)); } -void SparseSolver::visitPHINode(PHINode &PN) { +template +void SparseSolver::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. @@ -279,7 +290,8 @@ UpdateState(PN, PNIV); } -void SparseSolver::visitInst(Instruction &I) { +template +void SparseSolver::visitInst(Instruction &I) { // PHIs are handled by the propagation logic, they are never passed into the // transfer functions. if (PHINode *PN = dyn_cast(&I)) @@ -295,7 +307,7 @@ visitTerminatorInst(*TI); } -void SparseSolver::Solve(Function &F) { +template void SparseSolver::Solve(Function &F) { MarkBlockExecutable(&F.getEntryBlock()); // Process the work lists until they are empty! @@ -331,7 +343,8 @@ } } -void SparseSolver::Print(Function &F, raw_ostream &OS) const { +template +void SparseSolver::Print(Function &F, raw_ostream &OS) const { OS << "\nFUNCTION: " << F.getName() << "\n"; for (auto &BB : F) { if (!BBExecutable.count(&BB))