0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This file implements an abstract sparse conditional propagation algorithm,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 // modeled after SCCP, but with a customizable lattice function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17
|
|
121
|
18 #include "llvm/IR/Instructions.h"
|
|
|
19 #include "llvm/Support/Debug.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 #include <set>
|
|
121
|
21
|
|
|
22 #define DEBUG_TYPE "sparseprop"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 namespace llvm {
|
|
121
|
25
|
|
|
26 /// A template for translating between LLVM Values and LatticeKeys. Clients must
|
|
|
27 /// provide a specialization of LatticeKeyInfo for their LatticeKey type.
|
|
|
28 template <class LatticeKey> struct LatticeKeyInfo {
|
|
|
29 // static inline Value *getValueFromLatticeKey(LatticeKey Key);
|
|
|
30 // static inline LatticeKey getLatticeKeyFromValue(Value *V);
|
|
|
31 };
|
|
|
32
|
|
|
33 template <class LatticeKey, class LatticeVal,
|
|
|
34 class KeyInfo = LatticeKeyInfo<LatticeKey>>
|
|
95
|
35 class SparseSolver;
|
|
|
36
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
|
|
121
|
38 /// to specify what the lattice values are and how they handle merges etc. This
|
|
|
39 /// gives the client the power to compute lattice values from instructions,
|
|
|
40 /// constants, etc. The current requirement is that lattice values must be
|
|
|
41 /// copyable. At the moment, nothing tries to avoid copying. Additionally,
|
|
|
42 /// lattice keys must be able to be used as keys of a mapping data structure.
|
|
|
43 /// Internally, the generic solver currently uses a DenseMap to map lattice keys
|
|
|
44 /// to lattice values. If the lattice key is a non-standard type, a
|
|
|
45 /// specialization of DenseMapInfo must be provided.
|
|
|
46 template <class LatticeKey, class LatticeVal> class AbstractLatticeFunction {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 private:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
|
|
95
|
49
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 LatticeVal untrackedVal) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53 UndefVal = undefVal;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 OverdefinedVal = overdefinedVal;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 UntrackedVal = untrackedVal;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 }
|
|
121
|
57
|
|
|
58 virtual ~AbstractLatticeFunction() = default;
|
|
95
|
59
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 LatticeVal getUndefVal() const { return UndefVal; }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 LatticeVal getUntrackedVal() const { return UntrackedVal; }
|
|
95
|
63
|
|
121
|
64 /// IsUntrackedValue - If the specified LatticeKey is obviously uninteresting
|
|
|
65 /// to the analysis (i.e., it would always return UntrackedVal), this
|
|
|
66 /// function can return true to avoid pointless work.
|
|
|
67 virtual bool IsUntrackedValue(LatticeKey Key) { return false; }
|
|
95
|
68
|
|
121
|
69 /// ComputeLatticeVal - Compute and return a LatticeVal corresponding to the
|
|
|
70 /// given LatticeKey.
|
|
|
71 virtual LatticeVal ComputeLatticeVal(LatticeKey Key) {
|
|
|
72 return getOverdefinedVal();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 /// one that the we want to handle through ComputeInstructionState.
|
|
95
|
77 virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
|
|
|
78
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 /// MergeValues - Compute and return the merge of the two specified lattice
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 /// values. Merging should only move one direction down the lattice to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 /// guarantee convergence (toward overdefined).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 return getOverdefinedVal(); // always safe, never useful.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 }
|
|
95
|
85
|
|
121
|
86 /// ComputeInstructionState - Compute the LatticeKeys that change as a result
|
|
|
87 /// of executing instruction \p I. Their associated LatticeVals are store in
|
|
|
88 /// \p ChangedValues.
|
|
|
89 virtual void
|
|
|
90 ComputeInstructionState(Instruction &I,
|
|
|
91 DenseMap<LatticeKey, LatticeVal> &ChangedValues,
|
|
|
92 SparseSolver<LatticeKey, LatticeVal> &SS) = 0;
|
|
|
93
|
|
|
94 /// PrintLatticeVal - Render the given LatticeVal to the specified stream.
|
|
|
95 virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS);
|
|
|
96
|
|
|
97 /// PrintLatticeKey - Render the given LatticeKey to the specified stream.
|
|
|
98 virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS);
|
|
|
99
|
|
|
100 /// GetValueFromLatticeVal - If the given LatticeVal is representable as an
|
|
|
101 /// LLVM value, return it; otherwise, return nullptr. If a type is given, the
|
|
|
102 /// returned value must have the same type. This function is used by the
|
|
|
103 /// generic solver in attempting to resolve branch and switch conditions.
|
|
|
104 virtual Value *GetValueFromLatticeVal(LatticeVal LV, Type *Ty = nullptr) {
|
|
|
105 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 /// Propagation with a programmable lattice function.
|
|
121
|
111 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 class SparseSolver {
|
|
95
|
113
|
|
121
|
114 /// LatticeFunc - This is the object that knows the lattice and how to
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 /// compute transfer functions.
|
|
121
|
116 AbstractLatticeFunction<LatticeKey, LatticeVal> *LatticeFunc;
|
|
|
117
|
|
|
118 /// ValueState - Holds the LatticeVals associated with LatticeKeys.
|
|
|
119 DenseMap<LatticeKey, LatticeVal> ValueState;
|
|
|
120
|
|
|
121 /// BBExecutable - Holds the basic blocks that are executable.
|
|
|
122 SmallPtrSet<BasicBlock *, 16> BBExecutable;
|
|
95
|
123
|
|
121
|
124 /// ValueWorkList - Holds values that should be processed.
|
|
|
125 SmallVector<Value *, 64> ValueWorkList;
|
|
95
|
126
|
|
121
|
127 /// BBWorkList - Holds basic blocks that should be processed.
|
|
|
128 SmallVector<BasicBlock *, 64> BBWorkList;
|
|
95
|
129
|
|
121
|
130 using Edge = std::pair<BasicBlock *, BasicBlock *>;
|
|
95
|
131
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 /// KnownFeasibleEdges - Entries in this set are edges which have already had
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
133 /// PHI nodes retriggered.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 std::set<Edge> KnownFeasibleEdges;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136 public:
|
|
121
|
137 explicit SparseSolver(
|
|
|
138 AbstractLatticeFunction<LatticeKey, LatticeVal> *Lattice)
|
|
95
|
139 : LatticeFunc(Lattice) {}
|
|
121
|
140 SparseSolver(const SparseSolver &) = delete;
|
|
|
141 SparseSolver &operator=(const SparseSolver &) = delete;
|
|
95
|
142
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143 /// Solve - Solve for constants and executable blocks.
|
|
121
|
144 void Solve();
|
|
95
|
145
|
|
121
|
146 void Print(raw_ostream &OS) const;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147
|
|
121
|
148 /// getExistingValueState - Return the LatticeVal object corresponding to the
|
|
|
149 /// given value from the ValueState map. If the value is not in the map,
|
|
|
150 /// UntrackedVal is returned, unlike the getValueState method.
|
|
|
151 LatticeVal getExistingValueState(LatticeKey Key) const {
|
|
|
152 auto I = ValueState.find(Key);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 }
|
|
95
|
155
|
|
121
|
156 /// getValueState - Return the LatticeVal object corresponding to the given
|
|
|
157 /// value from the ValueState map. If the value is not in the map, its state
|
|
|
158 /// is initialized.
|
|
|
159 LatticeVal getValueState(LatticeKey Key);
|
|
95
|
160
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 /// isEdgeFeasible - Return true if the control flow edge from the 'From'
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162 /// basic block to the 'To' basic block is currently feasible. If
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 /// AggressiveUndef is true, then this treats values with unknown lattice
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164 /// values as undefined. This is generally only useful when solving the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 /// lattice, not when querying it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 bool AggressiveUndef = false);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 /// isBlockExecutable - Return true if there are any known feasible
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 /// edges into the basic block. This is generally only useful when
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 /// querying the lattice.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 bool isBlockExecutable(BasicBlock *BB) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 return BBExecutable.count(BB);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 }
|
|
95
|
175
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 /// MarkBlockExecutable - This method can be used by clients to mark all of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 /// the blocks that are known to be intrinsically live in the processed unit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 void MarkBlockExecutable(BasicBlock *BB);
|
|
95
|
179
|
|
121
|
180 private:
|
|
|
181 /// UpdateState - When the state of some LatticeKey is potentially updated to
|
|
|
182 /// the given LatticeVal, this function notices and adds the LLVM value
|
|
|
183 /// corresponding the key to the work list, if needed.
|
|
|
184 void UpdateState(LatticeKey Key, LatticeVal LV);
|
|
|
185
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187 /// work list if it is not already executable.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188 void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
|
|
95
|
189
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 /// getFeasibleSuccessors - Return a vector of booleans to indicate which
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 /// successors are reachable from a given terminator instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192 void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193 bool AggressiveUndef);
|
|
95
|
194
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 void visitInst(Instruction &I);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 void visitPHINode(PHINode &I);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197 void visitTerminatorInst(TerminatorInst &TI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199
|
|
121
|
200 //===----------------------------------------------------------------------===//
|
|
|
201 // AbstractLatticeFunction Implementation
|
|
|
202 //===----------------------------------------------------------------------===//
|
|
|
203
|
|
|
204 template <class LatticeKey, class LatticeVal>
|
|
|
205 void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeVal(
|
|
|
206 LatticeVal V, raw_ostream &OS) {
|
|
|
207 if (V == UndefVal)
|
|
|
208 OS << "undefined";
|
|
|
209 else if (V == OverdefinedVal)
|
|
|
210 OS << "overdefined";
|
|
|
211 else if (V == UntrackedVal)
|
|
|
212 OS << "untracked";
|
|
|
213 else
|
|
|
214 OS << "unknown lattice value";
|
|
|
215 }
|
|
|
216
|
|
|
217 template <class LatticeKey, class LatticeVal>
|
|
|
218 void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeKey(
|
|
|
219 LatticeKey Key, raw_ostream &OS) {
|
|
|
220 OS << "unknown lattice key";
|
|
|
221 }
|
|
|
222
|
|
|
223 //===----------------------------------------------------------------------===//
|
|
|
224 // SparseSolver Implementation
|
|
|
225 //===----------------------------------------------------------------------===//
|
|
|
226
|
|
|
227 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
228 LatticeVal
|
|
|
229 SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getValueState(LatticeKey Key) {
|
|
|
230 auto I = ValueState.find(Key);
|
|
|
231 if (I != ValueState.end())
|
|
|
232 return I->second; // Common case, in the map
|
|
|
233
|
|
|
234 if (LatticeFunc->IsUntrackedValue(Key))
|
|
|
235 return LatticeFunc->getUntrackedVal();
|
|
|
236 LatticeVal LV = LatticeFunc->ComputeLatticeVal(Key);
|
|
|
237
|
|
|
238 // If this value is untracked, don't add it to the map.
|
|
|
239 if (LV == LatticeFunc->getUntrackedVal())
|
|
|
240 return LV;
|
|
|
241 return ValueState[Key] = LV;
|
|
|
242 }
|
|
|
243
|
|
|
244 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
245 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,
|
|
|
246 LatticeVal LV) {
|
|
|
247 auto I = ValueState.find(Key);
|
|
|
248 if (I != ValueState.end() && I->second == LV)
|
|
|
249 return; // No change.
|
|
|
250
|
|
|
251 // Update the state of the given LatticeKey and add its corresponding LLVM
|
|
|
252 // value to the work list.
|
|
|
253 ValueState[Key] = LV;
|
|
|
254 if (Value *V = KeyInfo::getValueFromLatticeKey(Key))
|
|
|
255 ValueWorkList.push_back(V);
|
|
|
256 }
|
|
|
257
|
|
|
258 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
259 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::MarkBlockExecutable(
|
|
|
260 BasicBlock *BB) {
|
|
|
261 if (!BBExecutable.insert(BB).second)
|
|
|
262 return;
|
|
|
263 DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
|
|
|
264 BBWorkList.push_back(BB); // Add the block to the work list!
|
|
|
265 }
|
|
|
266
|
|
|
267 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
268 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::markEdgeExecutable(
|
|
|
269 BasicBlock *Source, BasicBlock *Dest) {
|
|
|
270 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
|
|
|
271 return; // This edge is already known to be executable!
|
|
|
272
|
|
|
273 DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName() << " -> "
|
|
|
274 << Dest->getName() << "\n");
|
|
|
275
|
|
|
276 if (BBExecutable.count(Dest)) {
|
|
|
277 // The destination is already executable, but we just made an edge
|
|
|
278 // feasible that wasn't before. Revisit the PHI nodes in the block
|
|
|
279 // because they have potentially new operands.
|
|
|
280 for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
|
|
|
281 visitPHINode(*cast<PHINode>(I));
|
|
|
282 } else {
|
|
|
283 MarkBlockExecutable(Dest);
|
|
|
284 }
|
|
|
285 }
|
|
|
286
|
|
|
287 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
288 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
|
|
|
289 TerminatorInst &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) {
|
|
|
290 Succs.resize(TI.getNumSuccessors());
|
|
|
291 if (TI.getNumSuccessors() == 0)
|
|
|
292 return;
|
|
|
293
|
|
|
294 if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
|
|
|
295 if (BI->isUnconditional()) {
|
|
|
296 Succs[0] = true;
|
|
|
297 return;
|
|
|
298 }
|
|
|
299
|
|
|
300 LatticeVal BCValue;
|
|
|
301 if (AggressiveUndef)
|
|
|
302 BCValue =
|
|
|
303 getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
|
|
|
304 else
|
|
|
305 BCValue = getExistingValueState(
|
|
|
306 KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
|
|
|
307
|
|
|
308 if (BCValue == LatticeFunc->getOverdefinedVal() ||
|
|
|
309 BCValue == LatticeFunc->getUntrackedVal()) {
|
|
|
310 // Overdefined condition variables can branch either way.
|
|
|
311 Succs[0] = Succs[1] = true;
|
|
|
312 return;
|
|
|
313 }
|
|
|
314
|
|
|
315 // If undefined, neither is feasible yet.
|
|
|
316 if (BCValue == LatticeFunc->getUndefVal())
|
|
|
317 return;
|
|
|
318
|
|
|
319 Constant *C =
|
|
|
320 dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
|
|
|
321 BCValue, BI->getCondition()->getType()));
|
|
|
322 if (!C || !isa<ConstantInt>(C)) {
|
|
|
323 // Non-constant values can go either way.
|
|
|
324 Succs[0] = Succs[1] = true;
|
|
|
325 return;
|
|
|
326 }
|
|
|
327
|
|
|
328 // Constant condition variables mean the branch can only go a single way
|
|
|
329 Succs[C->isNullValue()] = true;
|
|
|
330 return;
|
|
|
331 }
|
|
|
332
|
|
|
333 if (TI.isExceptional()) {
|
|
|
334 Succs.assign(Succs.size(), true);
|
|
|
335 return;
|
|
|
336 }
|
|
|
337
|
|
|
338 if (isa<IndirectBrInst>(TI)) {
|
|
|
339 Succs.assign(Succs.size(), true);
|
|
|
340 return;
|
|
|
341 }
|
|
|
342
|
|
|
343 SwitchInst &SI = cast<SwitchInst>(TI);
|
|
|
344 LatticeVal SCValue;
|
|
|
345 if (AggressiveUndef)
|
|
|
346 SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
|
|
|
347 else
|
|
|
348 SCValue = getExistingValueState(
|
|
|
349 KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
|
|
|
350
|
|
|
351 if (SCValue == LatticeFunc->getOverdefinedVal() ||
|
|
|
352 SCValue == LatticeFunc->getUntrackedVal()) {
|
|
|
353 // All destinations are executable!
|
|
|
354 Succs.assign(TI.getNumSuccessors(), true);
|
|
|
355 return;
|
|
|
356 }
|
|
|
357
|
|
|
358 // If undefined, neither is feasible yet.
|
|
|
359 if (SCValue == LatticeFunc->getUndefVal())
|
|
|
360 return;
|
|
|
361
|
|
|
362 Constant *C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
|
|
|
363 SCValue, SI.getCondition()->getType()));
|
|
|
364 if (!C || !isa<ConstantInt>(C)) {
|
|
|
365 // All destinations are executable!
|
|
|
366 Succs.assign(TI.getNumSuccessors(), true);
|
|
|
367 return;
|
|
|
368 }
|
|
|
369 SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
|
|
|
370 Succs[Case.getSuccessorIndex()] = true;
|
|
|
371 }
|
|
|
372
|
|
|
373 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
374 bool SparseSolver<LatticeKey, LatticeVal, KeyInfo>::isEdgeFeasible(
|
|
|
375 BasicBlock *From, BasicBlock *To, bool AggressiveUndef) {
|
|
|
376 SmallVector<bool, 16> SuccFeasible;
|
|
|
377 TerminatorInst *TI = From->getTerminator();
|
|
|
378 getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
|
|
|
379
|
|
|
380 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
|
|
|
381 if (TI->getSuccessor(i) == To && SuccFeasible[i])
|
|
|
382 return true;
|
|
|
383
|
|
|
384 return false;
|
|
|
385 }
|
|
|
386
|
|
|
387 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
388 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitTerminatorInst(
|
|
|
389 TerminatorInst &TI) {
|
|
|
390 SmallVector<bool, 16> SuccFeasible;
|
|
|
391 getFeasibleSuccessors(TI, SuccFeasible, true);
|
|
|
392
|
|
|
393 BasicBlock *BB = TI.getParent();
|
|
|
394
|
|
|
395 // Mark all feasible successors executable...
|
|
|
396 for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
|
|
|
397 if (SuccFeasible[i])
|
|
|
398 markEdgeExecutable(BB, TI.getSuccessor(i));
|
|
|
399 }
|
|
|
400
|
|
|
401 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
402 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
|
|
|
403 // The lattice function may store more information on a PHINode than could be
|
|
|
404 // computed from its incoming values. For example, SSI form stores its sigma
|
|
|
405 // functions as PHINodes with a single incoming value.
|
|
|
406 if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
|
|
|
407 DenseMap<LatticeKey, LatticeVal> ChangedValues;
|
|
|
408 LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
|
|
|
409 for (auto &ChangedValue : ChangedValues)
|
|
|
410 if (ChangedValue.second != LatticeFunc->getUntrackedVal())
|
|
|
411 UpdateState(ChangedValue.first, ChangedValue.second);
|
|
|
412 return;
|
|
|
413 }
|
|
|
414
|
|
|
415 LatticeKey Key = KeyInfo::getLatticeKeyFromValue(&PN);
|
|
|
416 LatticeVal PNIV = getValueState(Key);
|
|
|
417 LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
|
|
|
418
|
|
|
419 // If this value is already overdefined (common) just return.
|
|
|
420 if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())
|
|
|
421 return; // Quick exit
|
|
|
422
|
|
|
423 // Super-extra-high-degree PHI nodes are unlikely to ever be interesting,
|
|
|
424 // and slow us down a lot. Just mark them overdefined.
|
|
|
425 if (PN.getNumIncomingValues() > 64) {
|
|
|
426 UpdateState(Key, Overdefined);
|
|
|
427 return;
|
|
|
428 }
|
|
|
429
|
|
|
430 // Look at all of the executable operands of the PHI node. If any of them
|
|
|
431 // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the
|
|
|
432 // transfer function to give us the merge of the incoming values.
|
|
|
433 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
|
|
|
434 // If the edge is not yet known to be feasible, it doesn't impact the PHI.
|
|
|
435 if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))
|
|
|
436 continue;
|
|
|
437
|
|
|
438 // Merge in this value.
|
|
|
439 LatticeVal OpVal =
|
|
|
440 getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(i)));
|
|
|
441 if (OpVal != PNIV)
|
|
|
442 PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
|
|
|
443
|
|
|
444 if (PNIV == Overdefined)
|
|
|
445 break; // Rest of input values don't matter.
|
|
|
446 }
|
|
|
447
|
|
|
448 // Update the PHI with the compute value, which is the merge of the inputs.
|
|
|
449 UpdateState(Key, PNIV);
|
|
|
450 }
|
|
|
451
|
|
|
452 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
453 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) {
|
|
|
454 // PHIs are handled by the propagation logic, they are never passed into the
|
|
|
455 // transfer functions.
|
|
|
456 if (PHINode *PN = dyn_cast<PHINode>(&I))
|
|
|
457 return visitPHINode(*PN);
|
|
|
458
|
|
|
459 // Otherwise, ask the transfer function what the result is. If this is
|
|
|
460 // something that we care about, remember it.
|
|
|
461 DenseMap<LatticeKey, LatticeVal> ChangedValues;
|
|
|
462 LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);
|
|
|
463 for (auto &ChangedValue : ChangedValues)
|
|
|
464 if (ChangedValue.second != LatticeFunc->getUntrackedVal())
|
|
|
465 UpdateState(ChangedValue.first, ChangedValue.second);
|
|
|
466
|
|
|
467 if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I))
|
|
|
468 visitTerminatorInst(*TI);
|
|
|
469 }
|
|
|
470
|
|
|
471 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
472 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Solve() {
|
|
|
473 // Process the work lists until they are empty!
|
|
|
474 while (!BBWorkList.empty() || !ValueWorkList.empty()) {
|
|
|
475 // Process the value work list.
|
|
|
476 while (!ValueWorkList.empty()) {
|
|
|
477 Value *V = ValueWorkList.back();
|
|
|
478 ValueWorkList.pop_back();
|
|
|
479
|
|
|
480 DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");
|
|
|
481
|
|
|
482 // "V" got into the work list because it made a transition. See if any
|
|
|
483 // users are both live and in need of updating.
|
|
|
484 for (User *U : V->users())
|
|
|
485 if (Instruction *Inst = dyn_cast<Instruction>(U))
|
|
|
486 if (BBExecutable.count(Inst->getParent())) // Inst is executable?
|
|
|
487 visitInst(*Inst);
|
|
|
488 }
|
|
|
489
|
|
|
490 // Process the basic block work list.
|
|
|
491 while (!BBWorkList.empty()) {
|
|
|
492 BasicBlock *BB = BBWorkList.back();
|
|
|
493 BBWorkList.pop_back();
|
|
|
494
|
|
|
495 DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
|
|
|
496
|
|
|
497 // Notify all instructions in this basic block that they are newly
|
|
|
498 // executable.
|
|
|
499 for (Instruction &I : *BB)
|
|
|
500 visitInst(I);
|
|
|
501 }
|
|
|
502 }
|
|
|
503 }
|
|
|
504
|
|
|
505 template <class LatticeKey, class LatticeVal, class KeyInfo>
|
|
|
506 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Print(
|
|
|
507 raw_ostream &OS) const {
|
|
|
508 if (ValueState.empty())
|
|
|
509 return;
|
|
|
510
|
|
|
511 LatticeKey Key;
|
|
|
512 LatticeVal LV;
|
|
|
513
|
|
|
514 OS << "ValueState:\n";
|
|
|
515 for (auto &Entry : ValueState) {
|
|
|
516 std::tie(Key, LV) = Entry;
|
|
|
517 if (LV == LatticeFunc->getUntrackedVal())
|
|
|
518 continue;
|
|
|
519 OS << "\t";
|
|
|
520 LatticeFunc->PrintLatticeVal(LV, OS);
|
|
|
521 OS << ": ";
|
|
|
522 LatticeFunc->PrintLatticeKey(Key, OS);
|
|
|
523 OS << "\n";
|
|
|
524 }
|
|
|
525 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526 } // end namespace llvm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
527
|
|
121
|
528 #undef DEBUG_TYPE
|
|
|
529
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 #endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H
|
