LLVM  10.0.0svn
SparsePropagation.h
Go to the documentation of this file.
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/IR/Instructions.h"
18 #include "llvm/Support/Debug.h"
19 #include <set>
20 
21 #define DEBUG_TYPE "sparseprop"
22 
23 namespace llvm {
24 
25 /// A template for translating between LLVM Values and LatticeKeys. Clients must
26 /// provide a specialization of LatticeKeyInfo for their LatticeKey type.
27 template <class LatticeKey> struct LatticeKeyInfo {
28  // static inline Value *getValueFromLatticeKey(LatticeKey Key);
29  // static inline LatticeKey getLatticeKeyFromValue(Value *V);
30 };
31 
32 template <class LatticeKey, class LatticeVal,
33  class KeyInfo = LatticeKeyInfo<LatticeKey>>
35 
36 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
37 /// to specify what the lattice values are and how they handle merges etc. This
38 /// gives the client the power to compute lattice values from instructions,
39 /// constants, etc. The current requirement is that lattice values must be
40 /// copyable. At the moment, nothing tries to avoid copying. Additionally,
41 /// lattice keys must be able to be used as keys of a mapping data structure.
42 /// Internally, the generic solver currently uses a DenseMap to map lattice keys
43 /// to lattice values. If the lattice key is a non-standard type, a
44 /// specialization of DenseMapInfo must be provided.
45 template <class LatticeKey, class LatticeVal> class AbstractLatticeFunction {
46 private:
47  LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
48 
49 public:
50  AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
51  LatticeVal untrackedVal) {
52  UndefVal = undefVal;
53  OverdefinedVal = overdefinedVal;
54  UntrackedVal = untrackedVal;
55  }
56 
57  virtual ~AbstractLatticeFunction() = default;
58 
59  LatticeVal getUndefVal() const { return UndefVal; }
60  LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
61  LatticeVal getUntrackedVal() const { return UntrackedVal; }
62 
63  /// IsUntrackedValue - If the specified LatticeKey is obviously uninteresting
64  /// to the analysis (i.e., it would always return UntrackedVal), this
65  /// function can return true to avoid pointless work.
66  virtual bool IsUntrackedValue(LatticeKey Key) { return false; }
67 
68  /// ComputeLatticeVal - Compute and return a LatticeVal corresponding to the
69  /// given LatticeKey.
70  virtual LatticeVal ComputeLatticeVal(LatticeKey Key) {
71  return getOverdefinedVal();
72  }
73 
74  /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
75  /// one that the we want to handle through ComputeInstructionState.
76  virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
77 
78  /// MergeValues - Compute and return the merge of the two specified lattice
79  /// values. Merging should only move one direction down the lattice to
80  /// guarantee convergence (toward overdefined).
81  virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
82  return getOverdefinedVal(); // always safe, never useful.
83  }
84 
85  /// ComputeInstructionState - Compute the LatticeKeys that change as a result
86  /// of executing instruction \p I. Their associated LatticeVals are store in
87  /// \p ChangedValues.
88  virtual void
89  ComputeInstructionState(Instruction &I,
90  DenseMap<LatticeKey, LatticeVal> &ChangedValues,
92 
93  /// PrintLatticeVal - Render the given LatticeVal to the specified stream.
94  virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS);
95 
96  /// PrintLatticeKey - Render the given LatticeKey to the specified stream.
97  virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS);
98 
99  /// GetValueFromLatticeVal - If the given LatticeVal is representable as an
100  /// LLVM value, return it; otherwise, return nullptr. If a type is given, the
101  /// returned value must have the same type. This function is used by the
102  /// generic solver in attempting to resolve branch and switch conditions.
103  virtual Value *GetValueFromLatticeVal(LatticeVal LV, Type *Ty = nullptr) {
104  return nullptr;
105  }
106 };
107 
108 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
109 /// Propagation with a programmable lattice function.
110 template <class LatticeKey, class LatticeVal, class KeyInfo>
111 class SparseSolver {
112 
113  /// LatticeFunc - This is the object that knows the lattice and how to
114  /// compute transfer functions.
116 
117  /// ValueState - Holds the LatticeVals associated with LatticeKeys.
119 
120  /// BBExecutable - Holds the basic blocks that are executable.
121  SmallPtrSet<BasicBlock *, 16> BBExecutable;
122 
123  /// ValueWorkList - Holds values that should be processed.
124  SmallVector<Value *, 64> ValueWorkList;
125 
126  /// BBWorkList - Holds basic blocks that should be processed.
128 
129  using Edge = std::pair<BasicBlock *, BasicBlock *>;
130 
131  /// KnownFeasibleEdges - Entries in this set are edges which have already had
132  /// PHI nodes retriggered.
133  std::set<Edge> KnownFeasibleEdges;
134 
135 public:
136  explicit SparseSolver(
138  : LatticeFunc(Lattice) {}
139  SparseSolver(const SparseSolver &) = delete;
140  SparseSolver &operator=(const SparseSolver &) = delete;
141 
142  /// Solve - Solve for constants and executable blocks.
143  void Solve();
144 
145  void Print(raw_ostream &OS) const;
146 
147  /// getExistingValueState - Return the LatticeVal object corresponding to the
148  /// given value from the ValueState map. If the value is not in the map,
149  /// UntrackedVal is returned, unlike the getValueState method.
150  LatticeVal getExistingValueState(LatticeKey Key) const {
151  auto I = ValueState.find(Key);
152  return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
153  }
154 
155  /// getValueState - Return the LatticeVal object corresponding to the given
156  /// value from the ValueState map. If the value is not in the map, its state
157  /// is initialized.
158  LatticeVal getValueState(LatticeKey Key);
159 
160  /// isEdgeFeasible - Return true if the control flow edge from the 'From'
161  /// basic block to the 'To' basic block is currently feasible. If
162  /// AggressiveUndef is true, then this treats values with unknown lattice
163  /// values as undefined. This is generally only useful when solving the
164  /// lattice, not when querying it.
165  bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
166  bool AggressiveUndef = false);
167 
168  /// isBlockExecutable - Return true if there are any known feasible
169  /// edges into the basic block. This is generally only useful when
170  /// querying the lattice.
171  bool isBlockExecutable(BasicBlock *BB) const {
172  return BBExecutable.count(BB);
173  }
174 
175  /// MarkBlockExecutable - This method can be used by clients to mark all of
176  /// the blocks that are known to be intrinsically live in the processed unit.
177  void MarkBlockExecutable(BasicBlock *BB);
178 
179 private:
180  /// UpdateState - When the state of some LatticeKey is potentially updated to
181  /// the given LatticeVal, this function notices and adds the LLVM value
182  /// corresponding the key to the work list, if needed.
183  void UpdateState(LatticeKey Key, LatticeVal LV);
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(Instruction &TI, SmallVectorImpl<bool> &Succs,
192  bool AggressiveUndef);
193 
194  void visitInst(Instruction &I);
195  void visitPHINode(PHINode &I);
196  void visitTerminator(Instruction &TI);
197 };
198 
199 //===----------------------------------------------------------------------===//
200 // AbstractLatticeFunction Implementation
201 //===----------------------------------------------------------------------===//
202 
203 template <class LatticeKey, class LatticeVal>
205  LatticeVal V, raw_ostream &OS) {
206  if (V == UndefVal)
207  OS << "undefined";
208  else if (V == OverdefinedVal)
209  OS << "overdefined";
210  else if (V == UntrackedVal)
211  OS << "untracked";
212  else
213  OS << "unknown lattice value";
214 }
215 
216 template <class LatticeKey, class LatticeVal>
218  LatticeKey Key, raw_ostream &OS) {
219  OS << "unknown lattice key";
220 }
221 
222 //===----------------------------------------------------------------------===//
223 // SparseSolver Implementation
224 //===----------------------------------------------------------------------===//
225 
226 template <class LatticeKey, class LatticeVal, class KeyInfo>
227 LatticeVal
229  auto I = ValueState.find(Key);
230  if (I != ValueState.end())
231  return I->second; // Common case, in the map
232 
233  if (LatticeFunc->IsUntrackedValue(Key))
234  return LatticeFunc->getUntrackedVal();
235  LatticeVal LV = LatticeFunc->ComputeLatticeVal(Key);
236 
237  // If this value is untracked, don't add it to the map.
238  if (LV == LatticeFunc->getUntrackedVal())
239  return LV;
240  return ValueState[Key] = std::move(LV);
241 }
242 
243 template <class LatticeKey, class LatticeVal, class KeyInfo>
245  LatticeVal LV) {
246  auto I = ValueState.find(Key);
247  if (I != ValueState.end() && I->second == LV)
248  return; // No change.
249 
250  // Update the state of the given LatticeKey and add its corresponding LLVM
251  // value to the work list.
252  ValueState[Key] = std::move(LV);
253  if (Value *V = KeyInfo::getValueFromLatticeKey(Key))
254  ValueWorkList.push_back(V);
255 }
256 
257 template <class LatticeKey, class LatticeVal, class KeyInfo>
259  BasicBlock *BB) {
260  if (!BBExecutable.insert(BB).second)
261  return;
262  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
263  BBWorkList.push_back(BB); // Add the block to the work list!
264 }
265 
266 template <class LatticeKey, class LatticeVal, class KeyInfo>
268  BasicBlock *Source, BasicBlock *Dest) {
269  if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
270  return; // This edge is already known to be executable!
271 
272  LLVM_DEBUG(dbgs() << "Marking Edge Executable: " << Source->getName()
273  << " -> " << Dest->getName() << "\n");
274 
275  if (BBExecutable.count(Dest)) {
276  // The destination is already executable, but we just made an edge
277  // feasible that wasn't before. Revisit the PHI nodes in the block
278  // because they have potentially new operands.
279  for (BasicBlock::iterator I = Dest->begin(); isa<PHINode>(I); ++I)
280  visitPHINode(*cast<PHINode>(I));
281  } else {
282  MarkBlockExecutable(Dest);
283  }
284 }
285 
286 template <class LatticeKey, class LatticeVal, class KeyInfo>
288  Instruction &TI, SmallVectorImpl<bool> &Succs, bool AggressiveUndef) {
289  Succs.resize(TI.getNumSuccessors());
290  if (TI.getNumSuccessors() == 0)
291  return;
292 
293  if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
294  if (BI->isUnconditional()) {
295  Succs[0] = true;
296  return;
297  }
298 
299  LatticeVal BCValue;
300  if (AggressiveUndef)
301  BCValue =
302  getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
303  else
304  BCValue = getExistingValueState(
305  KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
306 
307  if (BCValue == LatticeFunc->getOverdefinedVal() ||
308  BCValue == LatticeFunc->getUntrackedVal()) {
309  // Overdefined condition variables can branch either way.
310  Succs[0] = Succs[1] = true;
311  return;
312  }
313 
314  // If undefined, neither is feasible yet.
315  if (BCValue == LatticeFunc->getUndefVal())
316  return;
317 
318  Constant *C =
319  dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
320  std::move(BCValue), BI->getCondition()->getType()));
321  if (!C || !isa<ConstantInt>(C)) {
322  // Non-constant values can go either way.
323  Succs[0] = Succs[1] = true;
324  return;
325  }
326 
327  // Constant condition variables mean the branch can only go a single way
328  Succs[C->isNullValue()] = true;
329  return;
330  }
331 
332  if (TI.isExceptionalTerminator() ||
333  TI.isIndirectTerminator()) {
334  Succs.assign(Succs.size(), true);
335  return;
336  }
337 
338  SwitchInst &SI = cast<SwitchInst>(TI);
339  LatticeVal SCValue;
340  if (AggressiveUndef)
341  SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
342  else
343  SCValue = getExistingValueState(
344  KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
345 
346  if (SCValue == LatticeFunc->getOverdefinedVal() ||
347  SCValue == LatticeFunc->getUntrackedVal()) {
348  // All destinations are executable!
349  Succs.assign(TI.getNumSuccessors(), true);
350  return;
351  }
352 
353  // If undefined, neither is feasible yet.
354  if (SCValue == LatticeFunc->getUndefVal())
355  return;
356 
357  Constant *C = dyn_cast_or_null<Constant>(LatticeFunc->GetValueFromLatticeVal(
358  std::move(SCValue), SI.getCondition()->getType()));
359  if (!C || !isa<ConstantInt>(C)) {
360  // All destinations are executable!
361  Succs.assign(TI.getNumSuccessors(), true);
362  return;
363  }
364  SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
365  Succs[Case.getSuccessorIndex()] = true;
366 }
367 
368 template <class LatticeKey, class LatticeVal, class KeyInfo>
370  BasicBlock *From, BasicBlock *To, bool AggressiveUndef) {
371  SmallVector<bool, 16> SuccFeasible;
372  Instruction *TI = From->getTerminator();
373  getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
374 
375  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
376  if (TI->getSuccessor(i) == To && SuccFeasible[i])
377  return true;
378 
379  return false;
380 }
381 
382 template <class LatticeKey, class LatticeVal, class KeyInfo>
384  Instruction &TI) {
385  SmallVector<bool, 16> SuccFeasible;
386  getFeasibleSuccessors(TI, SuccFeasible, true);
387 
388  BasicBlock *BB = TI.getParent();
389 
390  // Mark all feasible successors executable...
391  for (unsigned i = 0, e = SuccFeasible.size(); i != e; ++i)
392  if (SuccFeasible[i])
393  markEdgeExecutable(BB, TI.getSuccessor(i));
394 }
395 
396 template <class LatticeKey, class LatticeVal, class KeyInfo>
398  // The lattice function may store more information on a PHINode than could be
399  // computed from its incoming values. For example, SSI form stores its sigma
400  // functions as PHINodes with a single incoming value.
401  if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
402  DenseMap<LatticeKey, LatticeVal> ChangedValues;
403  LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
404  for (auto &ChangedValue : ChangedValues)
405  if (ChangedValue.second != LatticeFunc->getUntrackedVal())
406  UpdateState(std::move(ChangedValue.first),
407  std::move(ChangedValue.second));
408  return;
409  }
410 
411  LatticeKey Key = KeyInfo::getLatticeKeyFromValue(&PN);
412  LatticeVal PNIV = getValueState(Key);
413  LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
414 
415  // If this value is already overdefined (common) just return.
416  if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())
417  return; // Quick exit
418 
419  // Super-extra-high-degree PHI nodes are unlikely to ever be interesting,
420  // and slow us down a lot. Just mark them overdefined.
421  if (PN.getNumIncomingValues() > 64) {
422  UpdateState(Key, Overdefined);
423  return;
424  }
425 
426  // Look at all of the executable operands of the PHI node. If any of them
427  // are overdefined, the PHI becomes overdefined as well. Otherwise, ask the
428  // transfer function to give us the merge of the incoming values.
429  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
430  // If the edge is not yet known to be feasible, it doesn't impact the PHI.
431  if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))
432  continue;
433 
434  // Merge in this value.
435  LatticeVal OpVal =
436  getValueState(KeyInfo::getLatticeKeyFromValue(PN.getIncomingValue(i)));
437  if (OpVal != PNIV)
438  PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
439 
440  if (PNIV == Overdefined)
441  break; // Rest of input values don't matter.
442  }
443 
444  // Update the PHI with the compute value, which is the merge of the inputs.
445  UpdateState(Key, PNIV);
446 }
447 
448 template <class LatticeKey, class LatticeVal, class KeyInfo>
450  // PHIs are handled by the propagation logic, they are never passed into the
451  // transfer functions.
452  if (PHINode *PN = dyn_cast<PHINode>(&I))
453  return visitPHINode(*PN);
454 
455  // Otherwise, ask the transfer function what the result is. If this is
456  // something that we care about, remember it.
457  DenseMap<LatticeKey, LatticeVal> ChangedValues;
458  LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);
459  for (auto &ChangedValue : ChangedValues)
460  if (ChangedValue.second != LatticeFunc->getUntrackedVal())
461  UpdateState(ChangedValue.first, ChangedValue.second);
462 
463  if (I.isTerminator())
464  visitTerminator(I);
465 }
466 
467 template <class LatticeKey, class LatticeVal, class KeyInfo>
469  // Process the work lists until they are empty!
470  while (!BBWorkList.empty() || !ValueWorkList.empty()) {
471  // Process the value work list.
472  while (!ValueWorkList.empty()) {
473  Value *V = ValueWorkList.back();
474  ValueWorkList.pop_back();
475 
476  LLVM_DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");
477 
478  // "V" got into the work list because it made a transition. See if any
479  // users are both live and in need of updating.
480  for (User *U : V->users())
481  if (Instruction *Inst = dyn_cast<Instruction>(U))
482  if (BBExecutable.count(Inst->getParent())) // Inst is executable?
483  visitInst(*Inst);
484  }
485 
486  // Process the basic block work list.
487  while (!BBWorkList.empty()) {
488  BasicBlock *BB = BBWorkList.back();
489  BBWorkList.pop_back();
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>
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
uint64_t CallInst * C
void Print(raw_ostream &OS) const
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y)
MergeValues - Compute and return the merge of the two specified lattice values.
SparseSolver(AbstractLatticeFunction< LatticeKey, LatticeVal > *Lattice)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS)
PrintLatticeVal - Render the given LatticeVal to the specified stream.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Value * getCondition() const
bool isTerminator() const
Definition: Instruction.h:128
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:144
virtual Value * GetValueFromLatticeVal(LatticeVal LV, Type *Ty=nullptr)
GetValueFromLatticeVal - If the given LatticeVal is representable as an LLVM value, return it; otherwise, return nullptr.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:273
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:412
Key
PAL metadata keys.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:85
void Solve()
Solve - Solve for constants and executable blocks.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS)
PrintLatticeKey - Render the given LatticeKey to the specified stream.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
This is an important base class in LLVM.
Definition: Constant.h:41
LatticeVal getUntrackedVal() const
const Instruction & back() const
Definition: BasicBlock.h:287
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
bool isExceptionalTerminator() const
Definition: Instruction.h:135
size_t size() const
Definition: SmallVector.h:52
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, bool AggressiveUndef=false)
isEdgeFeasible - Return true if the control flow edge from the &#39;From&#39; basic block to the &#39;To&#39; basic b...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
CaseIt findCaseValue(const ConstantInt *C)
Search all of the case values for the specified constant.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
LatticeVal getValueState(LatticeKey Key)
getValueState - Return the LatticeVal object corresponding to the given value from the ValueState map...
iterator_range< user_iterator > users()
Definition: Value.h:419
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
unsigned getSuccessorIndex() const
Returns successor index for current case successor.
virtual bool IsSpecialCasedPHI(PHINode *PN)
IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is one that the we want to hand...
AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, LatticeVal untrackedVal)
bool isBlockExecutable(BasicBlock *BB) const
isBlockExecutable - Return true if there are any known feasible edges into the basic block...
virtual bool IsUntrackedValue(LatticeKey Key)
IsUntrackedValue - If the specified LatticeKey is obviously uninteresting to the analysis (i...
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
LatticeVal getOverdefinedVal() const
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:82
bool isIndirectTerminator() const
Definition: Instruction.h:138
Multiway switch.
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
LLVM Value Representation.
Definition: Value.h:73
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
#define LLVM_DEBUG(X)
Definition: Debug.h:122
virtual LatticeVal ComputeLatticeVal(LatticeKey Key)
ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.
const BasicBlock * getParent() const
Definition: Instruction.h:66
void resize(size_type N)
Definition: SmallVector.h:344
A template for translating between LLVM Values and LatticeKeys.