LLVM API Documentation
00001 //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements an abstract sparse conditional propagation algorithm, 00011 // modeled after SCCP, but with a customizable lattice function. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H 00016 #define LLVM_ANALYSIS_SPARSE_PROPAGATION_H 00017 00018 #include "llvm/ADT/DenseMap.h" 00019 #include "llvm/ADT/SmallPtrSet.h" 00020 #include <iosfwd> 00021 #include <vector> 00022 #include <set> 00023 00024 namespace llvm { 00025 class Value; 00026 class Constant; 00027 class Argument; 00028 class Instruction; 00029 class PHINode; 00030 class TerminatorInst; 00031 class BasicBlock; 00032 class Function; 00033 class SparseSolver; 00034 class LLVMContext; 00035 00036 template<typename T> class SmallVectorImpl; 00037 00038 /// AbstractLatticeFunction - This class is implemented by the dataflow instance 00039 /// to specify what the lattice values are and how they handle merges etc. 00040 /// This gives the client the power to compute lattice values from instructions, 00041 /// constants, etc. The requirement is that lattice values must all fit into 00042 /// a void*. If a void* is not sufficient, the implementation should use this 00043 /// pointer to be a pointer into a uniquing set or something. 00044 /// 00045 class AbstractLatticeFunction { 00046 public: 00047 typedef void *LatticeVal; 00048 private: 00049 LatticeVal UndefVal, OverdefinedVal, UntrackedVal; 00050 public: 00051 AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, 00052 LatticeVal untrackedVal) { 00053 UndefVal = undefVal; 00054 OverdefinedVal = overdefinedVal; 00055 UntrackedVal = untrackedVal; 00056 } 00057 virtual ~AbstractLatticeFunction(); 00058 00059 LatticeVal getUndefVal() const { return UndefVal; } 00060 LatticeVal getOverdefinedVal() const { return OverdefinedVal; } 00061 LatticeVal getUntrackedVal() const { return UntrackedVal; } 00062 00063 /// IsUntrackedValue - If the specified Value is something that is obviously 00064 /// uninteresting to the analysis (and would always return UntrackedVal), 00065 /// this function can return true to avoid pointless work. 00066 virtual bool IsUntrackedValue(Value *V) { 00067 return false; 00068 } 00069 00070 /// ComputeConstant - Given a constant value, compute and return a lattice 00071 /// value corresponding to the specified constant. 00072 virtual LatticeVal ComputeConstant(Constant *C) { 00073 return getOverdefinedVal(); // always safe 00074 } 00075 00076 /// GetConstant - If the specified lattice value is representable as an LLVM 00077 /// constant value, return it. Otherwise return null. The returned value 00078 /// must be in the same LLVM type as Val. 00079 virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) { 00080 return 0; 00081 } 00082 00083 /// ComputeArgument - Given a formal argument value, compute and return a 00084 /// lattice value corresponding to the specified argument. 00085 virtual LatticeVal ComputeArgument(Argument *I) { 00086 return getOverdefinedVal(); // always safe 00087 } 00088 00089 /// MergeValues - Compute and return the merge of the two specified lattice 00090 /// values. Merging should only move one direction down the lattice to 00091 /// guarantee convergence (toward overdefined). 00092 virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) { 00093 return getOverdefinedVal(); // always safe, never useful. 00094 } 00095 00096 /// ComputeInstructionState - Given an instruction and a vector of its operand 00097 /// values, compute the result value of the instruction. 00098 virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) { 00099 return getOverdefinedVal(); // always safe, never useful. 00100 } 00101 00102 /// PrintValue - Render the specified lattice value to the specified stream. 00103 virtual void PrintValue(LatticeVal V, std::ostream &OS); 00104 }; 00105 00106 00107 /// SparseSolver - This class is a general purpose solver for Sparse Conditional 00108 /// Propagation with a programmable lattice function. 00109 /// 00110 class SparseSolver { 00111 typedef AbstractLatticeFunction::LatticeVal LatticeVal; 00112 00113 /// LatticeFunc - This is the object that knows the lattice and how to do 00114 /// compute transfer functions. 00115 AbstractLatticeFunction *LatticeFunc; 00116 00117 LLVMContext *Context; 00118 00119 DenseMap<Value*, LatticeVal> ValueState; // The state each value is in. 00120 SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable. 00121 00122 std::vector<Instruction*> InstWorkList; // Worklist of insts to process. 00123 00124 std::vector<BasicBlock*> BBWorkList; // The BasicBlock work list 00125 00126 /// KnownFeasibleEdges - Entries in this set are edges which have already had 00127 /// PHI nodes retriggered. 00128 typedef std::pair<BasicBlock*,BasicBlock*> Edge; 00129 std::set<Edge> KnownFeasibleEdges; 00130 00131 SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT 00132 void operator=(const SparseSolver&); // DO NOT IMPLEMENT 00133 public: 00134 explicit SparseSolver(AbstractLatticeFunction *Lattice, LLVMContext *C) 00135 : LatticeFunc(Lattice), Context(C) {} 00136 ~SparseSolver() { 00137 delete LatticeFunc; 00138 } 00139 00140 /// Solve - Solve for constants and executable blocks. 00141 /// 00142 void Solve(Function &F); 00143 00144 void Print(Function &F, std::ostream &OS) const; 00145 00146 /// getLatticeState - Return the LatticeVal object that corresponds to the 00147 /// value. If an value is not in the map, it is returned as untracked, 00148 /// unlike the getOrInitValueState method. 00149 LatticeVal getLatticeState(Value *V) const { 00150 DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V); 00151 return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal(); 00152 } 00153 00154 /// getOrInitValueState - Return the LatticeVal object that corresponds to the 00155 /// value, initializing the value's state if it hasn't been entered into the 00156 /// map yet. This function is necessary because not all values should start 00157 /// out in the underdefined state... Arguments should be overdefined, and 00158 /// constants should be marked as constants. 00159 /// 00160 LatticeVal getOrInitValueState(Value *V); 00161 00162 /// isEdgeFeasible - Return true if the control flow edge from the 'From' 00163 /// basic block to the 'To' basic block is currently feasible. If 00164 /// AggressiveUndef is true, then this treats values with unknown lattice 00165 /// values as undefined. This is generally only useful when solving the 00166 /// lattice, not when querying it. 00167 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, 00168 bool AggressiveUndef = false); 00169 00170 /// isBlockExecutable - Return true if there are any known feasible 00171 /// edges into the basic block. This is generally only useful when 00172 /// querying the lattice. 00173 bool isBlockExecutable(BasicBlock *BB) const { 00174 return BBExecutable.count(BB); 00175 } 00176 00177 private: 00178 /// UpdateState - When the state for some instruction is potentially updated, 00179 /// this function notices and adds I to the worklist if needed. 00180 void UpdateState(Instruction &Inst, LatticeVal V); 00181 00182 /// MarkBlockExecutable - This method can be used by clients to mark all of 00183 /// the blocks that are known to be intrinsically live in the processed unit. 00184 void MarkBlockExecutable(BasicBlock *BB); 00185 00186 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB 00187 /// work list if it is not already executable. 00188 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest); 00189 00190 /// getFeasibleSuccessors - Return a vector of booleans to indicate which 00191 /// successors are reachable from a given terminator instruction. 00192 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs, 00193 bool AggressiveUndef); 00194 00195 void visitInst(Instruction &I); 00196 void visitPHINode(PHINode &I); 00197 void visitTerminatorInst(TerminatorInst &TI); 00198 00199 }; 00200 00201 } // end namespace llvm 00202 00203 #endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H