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