LLVM  15.0.0git
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/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>>
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
92  DenseMap<LatticeKey, LatticeVal> &ChangedValues,
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(
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.
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.
174  return BBExecutable.count(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.
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>
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>
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
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>
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(V);
257 }
258 
259 template <class LatticeKey, class LatticeVal, class KeyInfo>
261  BasicBlock *BB) {
262  if (!BBExecutable.insert(BB).second)
263  return;
264  LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
265  BBWorkList.push_back(BB); // Add the block to the work list!
266 }
267 
268 template <class LatticeKey, class LatticeVal, class KeyInfo>
270  BasicBlock *Source, BasicBlock *Dest) {
271  if (!KnownFeasibleEdges.insert(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(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>(I); ++I)
282  visitPHINode(*cast<PHINode>(I));
283  } else {
284  MarkBlockExecutable(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(TI.getNumSuccessors());
292  if (TI.getNumSuccessors() == 0)
293  return;
294 
295  if (BranchInst *BI = dyn_cast<BranchInst>(&TI)) {
296  if (BI->isUnconditional()) {
297  Succs[0] = true;
298  return;
299  }
300 
301  LatticeVal BCValue;
302  if (AggressiveUndef)
303  BCValue =
304  getValueState(KeyInfo::getLatticeKeyFromValue(BI->getCondition()));
305  else
306  BCValue = getExistingValueState(
307  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>(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 (TI.isExceptionalTerminator() ||
335  TI.isIndirectTerminator()) {
336  Succs.assign(Succs.size(), true);
337  return;
338  }
339 
340  SwitchInst &SI = cast<SwitchInst>(TI);
341  LatticeVal SCValue;
342  if (AggressiveUndef)
343  SCValue = getValueState(KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
344  else
345  SCValue = getExistingValueState(
346  KeyInfo::getLatticeKeyFromValue(SI.getCondition()));
347 
348  if (SCValue == LatticeFunc->getOverdefinedVal() ||
349  SCValue == LatticeFunc->getUntrackedVal()) {
350  // All destinations are executable!
351  Succs.assign(TI.getNumSuccessors(), 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>(C)) {
362  // All destinations are executable!
363  Succs.assign(TI.getNumSuccessors(), true);
364  return;
365  }
366  SwitchInst::CaseHandle Case = *SI.findCaseValue(cast<ConstantInt>(C));
367  Succs[Case.getSuccessorIndex()] = true;
368 }
369 
370 template <class LatticeKey, class LatticeVal, class KeyInfo>
372  BasicBlock *From, BasicBlock *To, bool AggressiveUndef) {
373  SmallVector<bool, 16> SuccFeasible;
374  Instruction *TI = From->getTerminator();
375  getFeasibleSuccessors(*TI, SuccFeasible, AggressiveUndef);
376 
377  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
378  if (TI->getSuccessor(i) == To && SuccFeasible[i])
379  return true;
380 
381  return false;
382 }
383 
384 template <class LatticeKey, class LatticeVal, class KeyInfo>
386  Instruction &TI) {
387  SmallVector<bool, 16> SuccFeasible;
388  getFeasibleSuccessors(TI, SuccFeasible, 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(BB, TI.getSuccessor(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(std::move(ChangedValue.first),
409  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, 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(PN.getIncomingBlock(i), PN.getParent(), true))
434  continue;
435 
436  // Merge in this value.
437  LatticeVal OpVal =
438  getValueState(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, 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>(&I))
455  return visitPHINode(*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(ChangedValue.first, ChangedValue.second);
464 
465  if (I.isTerminator())
466  visitTerminator(I);
467 }
468 
469 template <class LatticeKey, class LatticeVal, class KeyInfo>
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>(U))
483  if (BBExecutable.count(Inst->getParent())) // Inst is executable?
484  visitInst(*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>
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
i
i
Definition: README.txt:29
llvm::AbstractLatticeFunction::PrintLatticeVal
virtual void PrintLatticeVal(LatticeVal LV, raw_ostream &OS)
PrintLatticeVal - Render the given LatticeVal to the specified stream.
Definition: SparsePropagation.h:206
llvm::AbstractLatticeFunction::PrintLatticeKey
virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS)
PrintLatticeKey - Render the given LatticeKey to the specified stream.
Definition: SparsePropagation.h:219
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::AbstractLatticeFunction::MergeValues
virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y)
MergeValues - Compute and return the merge of the two specified lattice values.
Definition: SparsePropagation.h:83
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::SparseSolver::isBlockExecutable
bool isBlockExecutable(BasicBlock *BB) const
isBlockExecutable - Return true if there are any known feasible edges into the basic block.
Definition: SparsePropagation.h:173
llvm::SparseSolver::getValueState
LatticeVal getValueState(LatticeKey Key)
getValueState - Return the LatticeVal object corresponding to the given value from the ValueState map...
Definition: SparsePropagation.h:230
llvm::AbstractLatticeFunction::IsSpecialCasedPHI
virtual bool IsSpecialCasedPHI(PHINode *PN)
IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is one that the we want to hand...
Definition: SparsePropagation.h:78
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::AbstractLatticeFunction
AbstractLatticeFunction - This class is implemented by the dataflow instance to specify what the latt...
Definition: SparsePropagation.h:47
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::SparseSolver::operator=
SparseSolver & operator=(const SparseSolver &)=delete
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::AbstractLatticeFunction::AbstractLatticeFunction
AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal, LatticeVal untrackedVal)
Definition: SparsePropagation.h:52
llvm::AbstractLatticeFunction::IsUntrackedValue
virtual bool IsUntrackedValue(LatticeKey Key)
IsUntrackedValue - If the specified LatticeKey is obviously uninteresting to the analysis (i....
Definition: SparsePropagation.h:68
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
Constants.h
llvm::ISD::Constant
@ Constant
Definition: ISDOpcodes.h:76
llvm::User
Definition: User.h:44
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::SparseSolver::Solve
void Solve()
Solve - Solve for constants and executable blocks.
Definition: SparsePropagation.h:470
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
SmallPtrSet.h
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
llvm::LatticeKeyInfo
A template for translating between LLVM Values and LatticeKeys.
Definition: SparsePropagation.h:29
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AbstractLatticeFunction::GetValueFromLatticeVal
virtual Value * GetValueFromLatticeVal(LatticeVal LV, Type *Ty=nullptr)
GetValueFromLatticeVal - If the given LatticeVal is representable as an LLVM value,...
Definition: SparsePropagation.h:105
llvm::X86AS::SS
@ SS
Definition: X86.h:193
llvm::AbstractLatticeFunction::~AbstractLatticeFunction
virtual ~AbstractLatticeFunction()=default
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap< LatticeKey, LatticeVal >
I
#define I(x, y, z)
Definition: MD5.cpp:58
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::AbstractLatticeFunction::getUntrackedVal
LatticeVal getUntrackedVal() const
Definition: SparsePropagation.h:63
llvm::AbstractLatticeFunction::ComputeLatticeVal
virtual LatticeVal ComputeLatticeVal(LatticeKey Key)
ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.
Definition: SparsePropagation.h:72
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::AbstractLatticeFunction::getUndefVal
LatticeVal getUndefVal() const
Definition: SparsePropagation.h:61
llvm::SparseSolver::Print
void Print(raw_ostream &OS) const
Definition: SparsePropagation.h:502
llvm::AbstractLatticeFunction::getOverdefinedVal
LatticeVal getOverdefinedVal() const
Definition: SparsePropagation.h:62
llvm::SparseSolver::isEdgeFeasible
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To, bool AggressiveUndef=false)
isEdgeFeasible - Return true if the control flow edge from the 'From' basic block to the 'To' basic b...
Definition: SparsePropagation.h:371
llvm::SparseSolver::MarkBlockExecutable
void MarkBlockExecutable(BasicBlock *BB)
MarkBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
Definition: SparsePropagation.h:260
Instructions.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode
Definition: Instructions.h:2651
llvm::SmallVectorImpl< bool >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SparseSolver::getExistingValueState
LatticeVal getExistingValueState(LatticeKey Key) const
getExistingValueState - Return the LatticeVal object corresponding to the given value from the ValueS...
Definition: SparsePropagation.h:152
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::SparseSolver::SparseSolver
SparseSolver(AbstractLatticeFunction< LatticeKey, LatticeVal > *Lattice)
Definition: SparsePropagation.h:138
llvm::SparseSolver
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
Definition: SparsePropagation.h:36
llvm::AbstractLatticeFunction::ComputeInstructionState
virtual void ComputeInstructionState(Instruction &I, DenseMap< LatticeKey, LatticeVal > &ChangedValues, SparseSolver< LatticeKey, LatticeVal > &SS)=0
ComputeInstructionState - Compute the LatticeKeys that change as a result of executing instruction I.