LLVM  14.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/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
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.
115  AbstractLatticeFunction<LatticeKey, LatticeVal> *LatticeFunc;
116 
117  /// ValueState - Holds the LatticeVals associated with LatticeKeys.
118  DenseMap<LatticeKey, LatticeVal> ValueState;
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.
127  SmallVector<BasicBlock *, 64> BBWorkList;
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.
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.
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.
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>
287 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::getFeasibleSuccessors(
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>
397 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitPHINode(PHINode &PN) {
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>
449 void SparseSolver<LatticeKey, LatticeVal, KeyInfo>::visitInst(Instruction &I) {
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.pop_back_val();
474 
475  LLVM_DEBUG(dbgs() << "\nPopped off V-WL: " << *V << "\n");
476 
477  // "V" got into the work list because it made a transition. See if any
478  // users are both live and in need of updating.
479  for (User *U : V->users())
480  if (Instruction *Inst = dyn_cast<Instruction>(U))
481  if (BBExecutable.count(Inst->getParent())) // Inst is executable?
482  visitInst(*Inst);
483  }
484 
485  // Process the basic block work list.
486  while (!BBWorkList.empty()) {
487  BasicBlock *BB = BBWorkList.pop_back_val();
488 
489  LLVM_DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
490 
491  // Notify all instructions in this basic block that they are newly
492  // executable.
493  for (Instruction &I : *BB)
494  visitInst(I);
495  }
496  }
497 }
498 
499 template <class LatticeKey, class LatticeVal, class KeyInfo>
501  raw_ostream &OS) const {
502  if (ValueState.empty())
503  return;
504 
505  LatticeKey Key;
506  LatticeVal LV;
507 
508  OS << "ValueState:\n";
509  for (auto &Entry : ValueState) {
510  std::tie(Key, LV) = Entry;
511  if (LV == LatticeFunc->getUntrackedVal())
512  continue;
513  OS << "\t";
514  LatticeFunc->PrintLatticeVal(LV, OS);
515  OS << ": ";
516  LatticeFunc->PrintLatticeKey(Key, OS);
517  OS << "\n";
518  }
519 }
520 } // end namespace llvm
521 
522 #undef DEBUG_TYPE
523 
524 #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:204
llvm::AbstractLatticeFunction::PrintLatticeKey
virtual void PrintLatticeKey(LatticeKey Key, raw_ostream &OS)
PrintLatticeKey - Render the given LatticeKey to the specified stream.
Definition: SparsePropagation.h:217
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
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:81
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:171
llvm::SparseSolver::getValueState
LatticeVal getValueState(LatticeKey Key)
getValueState - Return the LatticeVal object corresponding to the given value from the ValueState map...
Definition: SparsePropagation.h:228
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:76
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:45
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:50
llvm::AbstractLatticeFunction::IsUntrackedValue
virtual bool IsUntrackedValue(LatticeKey Key)
IsUntrackedValue - If the specified LatticeKey is obviously uninteresting to the analysis (i....
Definition: SparsePropagation.h:66
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:765
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:468
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:777
llvm::LatticeKeyInfo
A template for translating between LLVM Values and LatticeKeys.
Definition: SparsePropagation.h:27
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:103
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:59
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::AbstractLatticeFunction::getUntrackedVal
LatticeVal getUntrackedVal() const
Definition: SparsePropagation.h:61
llvm::AbstractLatticeFunction::ComputeLatticeVal
virtual LatticeVal ComputeLatticeVal(LatticeKey Key)
ComputeLatticeVal - Compute and return a LatticeVal corresponding to the given LatticeKey.
Definition: SparsePropagation.h:70
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:100
llvm::X86AS::SS
@ SS
Definition: X86.h:189
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
llvm::AbstractLatticeFunction::getUndefVal
LatticeVal getUndefVal() const
Definition: SparsePropagation.h:59
llvm::SparseSolver::Print
void Print(raw_ostream &OS) const
Definition: SparsePropagation.h:500
llvm::AbstractLatticeFunction::getOverdefinedVal
LatticeVal getOverdefinedVal() const
Definition: SparsePropagation.h:60
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:369
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:258
Instructions.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode
Definition: Instructions.h:2633
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:150
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::SparseSolver::SparseSolver
SparseSolver(AbstractLatticeFunction< LatticeKey, LatticeVal > *Lattice)
Definition: SparsePropagation.h:136
llvm::SparseSolver
SparseSolver - This class is a general purpose solver for Sparse Conditional Propagation with a progr...
Definition: SparsePropagation.h:34
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.