Coverage Report

Created: 2018-11-16 02:38

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/SparsePropagation.h
Line
Count
Source (jump to first uncovered line)
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/IR/Instructions.h"
19
#include "llvm/Support/Debug.h"
20
#include <set>
21
22
#define DEBUG_TYPE "sparseprop"
23
24
namespace llvm {
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>>
35
class SparseSolver;
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.  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 {
47
private:
48
  LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
49
50
public:
51
  AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
52
13.4k
                          LatticeVal untrackedVal) {
53
13.4k
    UndefVal = undefVal;
54
13.4k
    OverdefinedVal = overdefinedVal;
55
13.4k
    UntrackedVal = untrackedVal;
56
13.4k
  }
57
58
13.4k
  virtual ~AbstractLatticeFunction() = default;
59
60
1.42M
  LatticeVal getUndefVal()       const { return UndefVal; }
61
26.8M
  LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
62
19.4M
  LatticeVal getUntrackedVal()   const { return UntrackedVal; }
63
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
1.75M
  virtual bool IsUntrackedValue(LatticeKey Key) { return false; }
68
69
  /// ComputeLatticeVal - Compute and return a LatticeVal corresponding to the
70
  /// given LatticeKey.
71
0
  virtual LatticeVal ComputeLatticeVal(LatticeKey Key) {
72
0
    return getOverdefinedVal();
73
0
  }
74
75
  /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
76
  /// one that the we want to handle through ComputeInstructionState.
77
2.14M
  virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
78
79
  /// MergeValues - Compute and return the merge of the two specified lattice
80
  /// values.  Merging should only move one direction down the lattice to
81
  /// guarantee convergence (toward overdefined).
82
0
  virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
83
0
    return getOverdefinedVal(); // always safe, never useful.
84
0
  }
85
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
0
  virtual Value *GetValueFromLatticeVal(LatticeVal LV, Type *Ty = nullptr) {
105
0
    return nullptr;
106
0
  }
107
};
108
109
/// SparseSolver - This class is a general purpose solver for Sparse Conditional
110
/// Propagation with a programmable lattice function.
111
template <class LatticeKey, class LatticeVal, class KeyInfo>
112
class SparseSolver {
113
114
  /// LatticeFunc - This is the object that knows the lattice and how to
115
  /// compute transfer functions.
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;
123
124
  /// ValueWorkList - Holds values that should be processed.
125
  SmallVector<Value *, 64> ValueWorkList;
126
127
  /// BBWorkList - Holds basic blocks that should be processed.
128
  SmallVector<BasicBlock *, 64> BBWorkList;
129
130
  using Edge = std::pair<BasicBlock *, BasicBlock *>;
131
132
  /// KnownFeasibleEdges - Entries in this set are edges which have already had
133
  /// PHI nodes retriggered.
134
  std::set<Edge> KnownFeasibleEdges;
135
136
public:
137
  explicit SparseSolver(
138
      AbstractLatticeFunction<LatticeKey, LatticeVal> *Lattice)
139
13.4k
      : LatticeFunc(Lattice) {}
140
  SparseSolver(const SparseSolver &) = delete;
141
  SparseSolver &operator=(const SparseSolver &) = delete;
142
143
  /// Solve - Solve for constants and executable blocks.
144
  void Solve();
145
146
  void Print(raw_ostream &OS) const;
147
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
66.9k
  LatticeVal getExistingValueState(LatticeKey Key) const {
152
66.9k
    auto I = ValueState.find(Key);
153
66.9k
    return I != ValueState.end() ? 
I->second54.3k
:
LatticeFunc->getUntrackedVal()12.5k
;
154
66.9k
  }
155
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);
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
  /// MarkBlockExecutable - This method can be used by clients to mark all of
177
  /// the blocks that are known to be intrinsically live in the processed unit.
178
  void MarkBlockExecutable(BasicBlock *BB);
179
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
186
  /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
187
  /// work list if it is not already executable.
188
  void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
189
190
  /// getFeasibleSuccessors - Return a vector of booleans to indicate which
191
  /// successors are reachable from a given terminator instruction.
192
  void getFeasibleSuccessors(Instruction &TI, SmallVectorImpl<bool> &Succs,
193
                             bool AggressiveUndef);
194
195
  void visitInst(Instruction &I);
196
  void visitPHINode(PHINode &I);
197
  void visitTerminator(Instruction &TI);
198
};
199
200
//===----------------------------------------------------------------------===//
201
//                  AbstractLatticeFunction Implementation
202
//===----------------------------------------------------------------------===//
203
204
template <class LatticeKey, class LatticeVal>
205
void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeVal(
206
0
    LatticeVal V, raw_ostream &OS) {
207
0
  if (V == UndefVal)
208
0
    OS << "undefined";
209
0
  else if (V == OverdefinedVal)
210
0
    OS << "overdefined";
211
0
  else if (V == UntrackedVal)
212
0
    OS << "untracked";
213
0
  else
214
0
    OS << "unknown lattice value";
215
0
}
216
217
template <class LatticeKey, class LatticeVal>
218
void AbstractLatticeFunction<LatticeKey, LatticeVal>::PrintLatticeKey(
219
0
    LatticeKey Key, raw_ostream &OS) {
220
0
  OS << "unknown lattice key";
221
0
}
222
223
//===----------------------------------------------------------------------===//
224
//                          SparseSolver Implementation
225
//===----------------------------------------------------------------------===//
226
227
template <class LatticeKey, class LatticeVal, class KeyInfo>
228
LatticeVal
229
10.7M
SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getValueState(LatticeKey Key) {
230
10.7M
  auto I = ValueState.find(Key);
231
10.7M
  if (I != ValueState.end())
232
9.03M
    return I->second; // Common case, in the map
233
1.75M
234
1.75M
  if (LatticeFunc->IsUntrackedValue(Key))
235
0
    return LatticeFunc->getUntrackedVal();
236
1.75M
  LatticeVal LV = LatticeFunc->ComputeLatticeVal(Key);
237
1.75M
238
1.75M
  // If this value is untracked, don't add it to the map.
239
1.75M
  if (LV == LatticeFunc->getUntrackedVal())
240
0
    return LV;
241
1.75M
  return ValueState[Key] = std::move(LV);
242
1.75M
}
243
244
template <class LatticeKey, class LatticeVal, class KeyInfo>
245
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::UpdateState(LatticeKey Key,
246
17.4M
                                                                LatticeVal LV) {
247
17.4M
  auto I = ValueState.find(Key);
248
17.4M
  if (I != ValueState.end() && 
I->second == LV10.4M
)
249
9.36M
    return; // No change.
250
8.13M
251
8.13M
  // Update the state of the given LatticeKey and add its corresponding LLVM
252
8.13M
  // value to the work list.
253
8.13M
  ValueState[Key] = std::move(LV);
254
8.13M
  if (Value *V = KeyInfo::getValueFromLatticeKey(Key))
255
8.13M
    ValueWorkList.push_back(V);
256
8.13M
}
257
258
template <class LatticeKey, class LatticeVal, class KeyInfo>
259
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::MarkBlockExecutable(
260
2.81M
    BasicBlock *BB) {
261
2.81M
  if (!BBExecutable.insert(BB).second)
262
415k
    return;
263
2.40M
  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
264
2.40M
  BBWorkList.push_back(BB); // Add the block to the work list!
265
2.40M
}
266
267
template <class LatticeKey, class LatticeVal, class KeyInfo>
268
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::markEdgeExecutable(
269
4.87M
    BasicBlock *Source, BasicBlock *Dest) {
270
4.87M
  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
271
2.05M
    return; // This edge is already known to be executable!
272
2.81M
273
2.81M
  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
274
2.81M
                    << " -> " << Dest->getName() << "\n");
275
2.81M
276
2.81M
  if (BBExecutable.count(Dest)) {
277
996k
    // The destination is already executable, but we just made an edge
278
996k
    // feasible that wasn't before.  Revisit the PHI nodes in the block
279
996k
    // because they have potentially new operands.
280
1.75M
    for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); 
++I759k
)
281
759k
      visitPHINode(*cast<PHINode>(I));
282
1.82M
  } else {
283
1.82M
    MarkBlockExecutable(Dest);
284
1.82M
  }
285
2.81M
}
286
287
template <class LatticeKey, class LatticeVal, class KeyInfo>
288
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
289
4.51M
    Instruction &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) {
290
4.51M
  Succs.resize(TI.getNumSuccessors());
291
4.51M
  if (TI.getNumSuccessors() == 0)
292
938k
    return;
293
3.57M
294
3.57M
  if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
295
3.47M
    if (BI->isUnconditional()) {
296
1.20M
      Succs[0] = true;
297
1.20M
      return;
298
1.20M
    }
299
2.27M
300
2.27M
    LatticeVal BCValue;
301
2.27M
    if (AggressiveUndef)
302
2.27M
      BCValue =
303
2.27M
          getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
304
0
    else
305
0
      BCValue = getExistingValueState(
306
0
          KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
307
2.27M
308
2.27M
    if (BCValue == LatticeFunc->getOverdefinedVal() ||
309
2.27M
        
BCValue == LatticeFunc->getUntrackedVal()140k
) {
310
2.13M
      // Overdefined condition variables can branch either way.
311
2.13M
      Succs[0] = Succs[1] = true;
312
2.13M
      return;
313
2.13M
    }
314
140k
315
140k
    // If undefined, neither is feasible yet.
316
140k
    if (BCValue == LatticeFunc->getUndefVal())
317
140k
      return;
318
0
319
0
    Constant *C =
320
0
        dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
321
0
            std::move(BCValue), BI->getCondition()->getType()));
322
0
    if (!C || !isa<ConstantInt>(C)) {
323
0
      // Non-constant values can go either way.
324
0
      Succs[0] = Succs[1] = true;
325
0
      return;
326
0
    }
327
0
328
0
    // Constant condition variables mean the branch can only go a single way
329
0
    Succs[C->isNullValue()] = true;
330
0
    return;
331
0
  }
332
102k
333
102k
  if (TI.isExceptionalTerminator()) {
334
72.8k
    Succs.assign(Succs.size(), true);
335
72.8k
    return;
336
72.8k
  }
337
29.9k
338
29.9k
  if (isa<IndirectBrInst>(TI)) {
339
10
    Succs.assign(Succs.size(), true);
340
10
    return;
341
10
  }
342
29.9k
343
29.9k
  SwitchInst &SI = cast<SwitchInst>(TI);
344
29.9k
  LatticeVal SCValue;
345
29.9k
  if (AggressiveUndef)
346
29.9k
    SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
347
18.4E
  else
348
18.4E
    SCValue = getExistingValueState(
349
18.4E
        KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
350
29.9k
351
29.9k
  if (SCValue == LatticeFunc->getOverdefinedVal() ||
352
29.9k
      
SCValue == LatticeFunc->getUntrackedVal()986
) {
353
28.9k
    // All destinations are executable!
354
28.9k
    Succs.assign(TI.getNumSuccessors(), true);
355
28.9k
    return;
356
28.9k
  }
357
982
358
982
  // If undefined, neither is feasible yet.
359
982
  if (SCValue == LatticeFunc->getUndefVal())
360
986
    return;
361
18.4E
362
18.4E
  Constant *C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
363
18.4E
      std::move(SCValue), SI.getCondition()->getType()));
364
18.4E
  if (!C || 
!isa<ConstantInt>(C)0
) {
365
0
    // All destinations are executable!
366
0
    Succs.assign(TI.getNumSuccessors(), true);
367
0
    return;
368
0
  }
369
18.4E
  SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
370
18.4E
  Succs[Case.getSuccessorIndex()] = true;
371
18.4E
}
372
373
template <class LatticeKey, class LatticeVal, class KeyInfo>
374
bool SparseSolver<LatticeKey, LatticeVal, KeyInfo>::isEdgeFeasible(
375
778k
    BasicBlock *From, BasicBlock *To, bool AggressiveUndef) {
376
778k
  SmallVector<bool, 16> SuccFeasible;
377
778k
  Instruction *TI = From->getTerminator();
378
778k
  getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
379
778k
380
1.18M
  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; 
++i410k
)
381
1.04M
    if (TI->getSuccessor(i) == To && 
SuccFeasible[i]778k
)
382
638k
      return true;
383
778k
384
778k
  
return false140k
;
385
778k
}
386
387
template <class LatticeKey, class LatticeVal, class KeyInfo>
388
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitTerminator(
389
3.74M
    Instruction &TI) {
390
3.74M
  SmallVector<bool, 16> SuccFeasible;
391
3.74M
  getFeasibleSuccessors(TI, SuccFeasible, true);
392
3.74M
393
3.74M
  BasicBlock *BB = TI.getParent();
394
3.74M
395
3.74M
  // Mark all feasible successors executable...
396
8.61M
  for (unsigned i = 0, e = SuccFeasible.size(); i != e; 
++i4.87M
)
397
4.87M
    if (SuccFeasible[i])
398
4.87M
      markEdgeExecutable(BB, TI.getSuccessor(i));
399
3.74M
}
400
401
template <class LatticeKey, class LatticeVal, class KeyInfo>
402
2.14M
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
403
2.14M
  // The lattice function may store more information on a PHINode than could be
404
2.14M
  // computed from its incoming values.  For example, SSI form stores its sigma
405
2.14M
  // functions as PHINodes with a single incoming value.
406
2.14M
  if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
407
0
    DenseMap<LatticeKey, LatticeVal> ChangedValues;
408
0
    LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
409
0
    for (auto &ChangedValue : ChangedValues)
410
0
      if (ChangedValue.second != LatticeFunc->getUntrackedVal())
411
0
        UpdateState(std::move(ChangedValue.first),
412
0
                    std::move(ChangedValue.second));
413
0
    return;
414
0
  }
415
2.14M
416
2.14M
  LatticeKey Key = KeyInfo::getLatticeKeyFromValue(&PN);
417
2.14M
  LatticeVal PNIV = getValueState(Key);
418
2.14M
  LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
419
2.14M
420
2.14M
  // If this value is already overdefined (common) just return.
421
2.14M
  if (PNIV == Overdefined || 
PNIV == LatticeFunc->getUntrackedVal()503k
)
422
1.64M
    return; // Quick exit
423
503k
424
503k
  // Super-extra-high-degree PHI nodes are unlikely to ever be interesting,
425
503k
  // and slow us down a lot.  Just mark them overdefined.
426
503k
  if (PN.getNumIncomingValues() > 64) {
427
24
    UpdateState(Key, Overdefined);
428
24
    return;
429
24
  }
430
503k
431
503k
  // Look at all of the executable operands of the PHI node.  If any of them
432
503k
  // are overdefined, the PHI becomes overdefined as well.  Otherwise, ask the
433
503k
  // transfer function to give us the merge of the incoming values.
434
791k
  
for (unsigned i = 0, e = PN.getNumIncomingValues(); 503k
i != e;
++i288k
) {
435
778k
    // If the edge is not yet known to be feasible, it doesn't impact the PHI.
436
778k
    if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))
437
140k
      continue;
438
638k
439
638k
    // Merge in this value.
440
638k
    LatticeVal OpVal =
441
638k
        getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(i)));
442
638k
    if (OpVal != PNIV)
443
506k
      PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
444
638k
445
638k
    if (PNIV == Overdefined)
446
490k
      break; // Rest of input values don't matter.
447
638k
  }
448
503k
449
503k
  // Update the PHI with the compute value, which is the merge of the inputs.
450
503k
  UpdateState(Key, PNIV);
451
503k
}
452
453
template <class LatticeKey, class LatticeVal, class KeyInfo>
454
24.3M
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) {
455
24.3M
  // PHIs are handled by the propagation logic, they are never passed into the
456
24.3M
  // transfer functions.
457
24.3M
  if (PHINode *PN = dyn_cast<PHINode>(&I))
458
1.38M
    return visitPHINode(*PN);
459
22.9M
460
22.9M
  // Otherwise, ask the transfer function what the result is.  If this is
461
22.9M
  // something that we care about, remember it.
462
22.9M
  DenseMap<LatticeKey, LatticeVal> ChangedValues;
463
22.9M
  LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);
464
22.9M
  for (auto &ChangedValue : ChangedValues)
465
16.9M
    if (ChangedValue.second != LatticeFunc->getUntrackedVal())
466
16.9M
      UpdateState(ChangedValue.first, ChangedValue.second);
467
22.9M
468
22.9M
  if (I.isTerminator())
469
3.74M
    visitTerminator(I);
470
22.9M
}
471
472
template <class LatticeKey, class LatticeVal, class KeyInfo>
473
13.4k
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Solve() {
474
13.4k
  // Process the work lists until they are empty!
475
37.9k
  while (!BBWorkList.empty() || 
!ValueWorkList.empty()25.7k
) {
476
24.4k
    // Process the value work list.
477
8.15M
    while (!ValueWorkList.empty()) {
478
8.13M
      Value *V = ValueWorkList.back();
479
8.13M
      ValueWorkList.pop_back();
480
8.13M
481
8.13M
      LLVM_DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");
482
8.13M
483
8.13M
      // "V" got into the work list because it made a transition. See if any
484
8.13M
      // users are both live and in need of updating.
485
8.13M
      for (User *U : V->users())
486
11.4M
        if (Instruction *Inst = dyn_cast<Instruction>(U))
487
11.4M
          if (BBExecutable.count(Inst->getParent())) // Inst is executable?
488
11.3M
            visitInst(*Inst);
489
8.13M
    }
490
24.4k
491
24.4k
    // Process the basic block work list.
492
2.42M
    while (!BBWorkList.empty()) {
493
2.40M
      BasicBlock *BB = BBWorkList.back();
494
2.40M
      BBWorkList.pop_back();
495
2.40M
496
2.40M
      LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
497
2.40M
498
2.40M
      // Notify all instructions in this basic block that they are newly
499
2.40M
      // executable.
500
2.40M
      for (Instruction &I : *BB)
501
12.9M
        visitInst(I);
502
2.40M
    }
503
24.4k
  }
504
13.4k
}
505
506
template <class LatticeKey, class LatticeVal, class KeyInfo>
507
void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::Print(
508
    raw_ostream &OS) const {
509
  if (ValueState.empty())
510
    return;
511
512
  LatticeKey Key;
513
  LatticeVal LV;
514
515
  OS << "ValueState:\n";
516
  for (auto &Entry : ValueState) {
517
    std::tie(Key, LV) = Entry;
518
    if (LV == LatticeFunc->getUntrackedVal())
519
      continue;
520
    OS << "\t";
521
    LatticeFunc->PrintLatticeVal(LV, OS);
522
    OS << ": ";
523
    LatticeFunc->PrintLatticeKey(Key, OS);
524
    OS << "\n";
525
  }
526
}
527
} // end namespace llvm
528
529
#undef DEBUG_TYPE
530
531
#endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H