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