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