SparsePropagation.h revision 875646f376f6c83bf8426fdb44e1dbf312cf784e
1//===- SparsePropagation.h - Sparse Conditional Property Propagation ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements an abstract sparse conditional propagation algorithm, 11// modeled after SCCP, but with a customizable lattice function. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H 16#define LLVM_ANALYSIS_SPARSE_PROPAGATION_H 17 18#include "llvm/ADT/DenseMap.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include <vector> 21#include <set> 22 23namespace llvm { 24 class Value; 25 class Constant; 26 class Argument; 27 class Instruction; 28 class PHINode; 29 class TerminatorInst; 30 class BasicBlock; 31 class Function; 32 class SparseSolver; 33 class LLVMContext; 34 class raw_ostream; 35 36 template<typename T> class SmallVectorImpl; 37 38/// AbstractLatticeFunction - This class is implemented by the dataflow instance 39/// to specify what the lattice values are and how they handle merges etc. 40/// This gives the client the power to compute lattice values from instructions, 41/// constants, etc. The requirement is that lattice values must all fit into 42/// a void*. If a void* is not sufficient, the implementation should use this 43/// pointer to be a pointer into a uniquing set or something. 44/// 45class AbstractLatticeFunction { 46public: 47 typedef void *LatticeVal; 48private: 49 LatticeVal UndefVal, OverdefinedVal, UntrackedVal; 50public: 51 AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, 52 LatticeVal untrackedVal) { 53 UndefVal = undefVal; 54 OverdefinedVal = overdefinedVal; 55 UntrackedVal = untrackedVal; 56 } 57 virtual ~AbstractLatticeFunction(); 58 59 LatticeVal getUndefVal() const { return UndefVal; } 60 LatticeVal getOverdefinedVal() const { return OverdefinedVal; } 61 LatticeVal getUntrackedVal() const { return UntrackedVal; } 62 63 /// IsUntrackedValue - If the specified Value is something that is obviously 64 /// uninteresting to the analysis (and would always return UntrackedVal), 65 /// this function can return true to avoid pointless work. 66 virtual bool IsUntrackedValue(Value *V) { 67 return false; 68 } 69 70 /// ComputeConstant - Given a constant value, compute and return a lattice 71 /// value corresponding to the specified constant. 72 virtual LatticeVal ComputeConstant(Constant *C) { 73 return getOverdefinedVal(); // always safe 74 } 75 76 /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is 77 /// one that the we want to handle through ComputeInstructionState. 78 virtual bool IsSpecialCasedPHI(PHINode *PN) { 79 return false; 80 } 81 82 /// GetConstant - If the specified lattice value is representable as an LLVM 83 /// constant value, return it. Otherwise return null. The returned value 84 /// must be in the same LLVM type as Val. 85 virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) { 86 return 0; 87 } 88 89 /// ComputeArgument - Given a formal argument value, compute and return a 90 /// lattice value corresponding to the specified argument. 91 virtual LatticeVal ComputeArgument(Argument *I) { 92 return getOverdefinedVal(); // always safe 93 } 94 95 /// MergeValues - Compute and return the merge of the two specified lattice 96 /// values. Merging should only move one direction down the lattice to 97 /// guarantee convergence (toward overdefined). 98 virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) { 99 return getOverdefinedVal(); // always safe, never useful. 100 } 101 102 /// ComputeInstructionState - Given an instruction and a vector of its operand 103 /// values, compute the result value of the instruction. 104 virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) { 105 return getOverdefinedVal(); // always safe, never useful. 106 } 107 108 /// PrintValue - Render the specified lattice value to the specified stream. 109 virtual void PrintValue(LatticeVal V, raw_ostream &OS); 110}; 111 112 113/// SparseSolver - This class is a general purpose solver for Sparse Conditional 114/// Propagation with a programmable lattice function. 115/// 116class SparseSolver { 117 typedef AbstractLatticeFunction::LatticeVal LatticeVal; 118 119 /// LatticeFunc - This is the object that knows the lattice and how to do 120 /// compute transfer functions. 121 AbstractLatticeFunction *LatticeFunc; 122 123 LLVMContext *Context; 124 125 DenseMap<Value*, LatticeVal> ValueState; // The state each value is in. 126 SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable. 127 128 std::vector<Instruction*> InstWorkList; // Worklist of insts to process. 129 130 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 131 132 /// KnownFeasibleEdges - Entries in this set are edges which have already had 133 /// PHI nodes retriggered. 134 typedef std::pair<BasicBlock*,BasicBlock*> Edge; 135 std::set<Edge> KnownFeasibleEdges; 136 137 SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT 138 void operator=(const SparseSolver&); // DO NOT IMPLEMENT 139public: 140 explicit SparseSolver(AbstractLatticeFunction *Lattice, LLVMContext *C) 141 : LatticeFunc(Lattice), Context(C) {} 142 ~SparseSolver() { 143 delete LatticeFunc; 144 } 145 146 /// Solve - Solve for constants and executable blocks. 147 /// 148 void Solve(Function &F); 149 150 void Print(Function &F, raw_ostream &OS) const; 151 152 /// getLatticeState - Return the LatticeVal object that corresponds to the 153 /// value. If an value is not in the map, it is returned as untracked, 154 /// unlike the getOrInitValueState method. 155 LatticeVal getLatticeState(Value *V) const { 156 DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 157 return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); 158 } 159 160 /// getOrInitValueState - Return the LatticeVal object that corresponds to the 161 /// value, initializing the value's state if it hasn't been entered into the 162 /// map yet. This function is necessary because not all values should start 163 /// out in the underdefined state... Arguments should be overdefined, and 164 /// constants should be marked as constants. 165 /// 166 LatticeVal getOrInitValueState(Value *V); 167 168 /// isEdgeFeasible - Return true if the control flow edge from the 'From' 169 /// basic block to the 'To' basic block is currently feasible. If 170 /// AggressiveUndef is true, then this treats values with unknown lattice 171 /// values as undefined. This is generally only useful when solving the 172 /// lattice, not when querying it. 173 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, 174 bool AggressiveUndef = false); 175 176 /// isBlockExecutable - Return true if there are any known feasible 177 /// edges into the basic block. This is generally only useful when 178 /// querying the lattice. 179 bool isBlockExecutable(BasicBlock *BB) const { 180 return BBExecutable.count(BB); 181 } 182 183private: 184 /// UpdateState - When the state for some instruction is potentially updated, 185 /// this function notices and adds I to the worklist if needed. 186 void UpdateState(Instruction &Inst, LatticeVal V); 187 188 /// MarkBlockExecutable - This method can be used by clients to mark all of 189 /// the blocks that are known to be intrinsically live in the processed unit. 190 void MarkBlockExecutable(BasicBlock *BB); 191 192 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 193 /// work list if it is not already executable. 194 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); 195 196 /// getFeasibleSuccessors - Return a vector of booleans to indicate which 197 /// successors are reachable from a given terminator instruction. 198 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs, 199 bool AggressiveUndef); 200 201 void visitInst(Instruction &I); 202 void visitPHINode(PHINode &I); 203 void visitTerminatorInst(TerminatorInst &TI); 204 205}; 206 207} // end namespace llvm 208 209#endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H 210