MLIR  19.0.0git
SparseAnalysis.h
Go to the documentation of this file.
1 //===- SparseAnalysis.h - Sparse data-flow analysis -----------------------===//
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 sparse data-flow analysis using the data-flow analysis
10 // framework. The analysis is forward and conditional and uses the results of
11 // dead code analysis to prune dead code during the analysis.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
16 #define MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
17 
19 #include "mlir/IR/SymbolTable.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 
24 namespace mlir {
25 namespace dataflow {
26 
27 //===----------------------------------------------------------------------===//
28 // AbstractSparseLattice
29 //===----------------------------------------------------------------------===//
30 
31 /// This class represents an abstract lattice. A lattice contains information
32 /// about an SSA value and is what's propagated across the IR by sparse
33 /// data-flow analysis.
35 public:
36  /// Lattices can only be created for values.
38 
39  /// Return the program point this lattice is located at.
40  Value getPoint() const { return AnalysisState::getPoint().get<Value>(); }
41 
42  /// Join the information contained in 'rhs' into this lattice. Returns
43  /// if the value of the lattice changed.
44  virtual ChangeResult join(const AbstractSparseLattice &rhs) {
46  }
47 
48  /// Meet (intersect) the information in this lattice with 'rhs'. Returns
49  /// if the value of the lattice changed.
50  virtual ChangeResult meet(const AbstractSparseLattice &rhs) {
52  }
53 
54  /// When the lattice gets updated, propagate an update to users of the value
55  /// using its use-def chain to subscribed analyses.
56  void onUpdate(DataFlowSolver *solver) const override;
57 
58  /// Subscribe an analysis to updates of the lattice. When the lattice changes,
59  /// subscribed analyses are re-invoked on all users of the value. This is
60  /// more efficient than relying on the dependency map.
62  useDefSubscribers.insert(analysis);
63  }
64 
65 private:
66  /// A set of analyses that should be updated when this lattice changes.
69  useDefSubscribers;
70 };
71 
72 //===----------------------------------------------------------------------===//
73 // Lattice
74 //===----------------------------------------------------------------------===//
75 
76 /// This class represents a lattice holding a specific value of type `ValueT`.
77 /// Lattice values (`ValueT`) are required to adhere to the following:
78 ///
79 /// * static ValueT join(const ValueT &lhs, const ValueT &rhs);
80 /// - This method conservatively joins the information held by `lhs`
81 /// and `rhs` into a new value. This method is required to be monotonic.
82 /// * bool operator==(const ValueT &rhs) const;
83 ///
84 template <typename ValueT>
86 public:
88 
89  /// Return the program point this lattice is located at.
90  Value getPoint() const { return point.get<Value>(); }
91 
92  /// Return the value held by this lattice. This requires that the value is
93  /// initialized.
94  ValueT &getValue() { return value; }
95  const ValueT &getValue() const {
96  return const_cast<Lattice<ValueT> *>(this)->getValue();
97  }
98 
100 
101  /// Join the information contained in the 'rhs' lattice into this
102  /// lattice. Returns if the state of the current lattice changed.
103  ChangeResult join(const AbstractSparseLattice &rhs) override {
104  return join(static_cast<const LatticeT &>(rhs).getValue());
105  }
106 
107  /// Meet (intersect) the information contained in the 'rhs' lattice with
108  /// this lattice. Returns if the state of the current lattice changed.
109  ChangeResult meet(const AbstractSparseLattice &rhs) override {
110  return meet(static_cast<const LatticeT &>(rhs).getValue());
111  }
112 
113  /// Join the information contained in the 'rhs' value into this
114  /// lattice. Returns if the state of the current lattice changed.
115  ChangeResult join(const ValueT &rhs) {
116  // Otherwise, join rhs with the current optimistic value.
117  ValueT newValue = ValueT::join(value, rhs);
118  assert(ValueT::join(newValue, value) == newValue &&
119  "expected `join` to be monotonic");
120  assert(ValueT::join(newValue, rhs) == newValue &&
121  "expected `join` to be monotonic");
122 
123  // Update the current optimistic value if something changed.
124  if (newValue == value)
125  return ChangeResult::NoChange;
126 
127  value = newValue;
128  return ChangeResult::Change;
129  }
130 
131  /// Trait to check if `T` provides a `meet` method. Needed since for forward
132  /// analysis, lattices will only have a `join`, no `meet`, but we want to use
133  /// the same `Lattice` class for both directions.
134  template <typename T, typename... Args>
135  using has_meet = decltype(&T::meet);
136  template <typename T>
137  using lattice_has_meet = llvm::is_detected<has_meet, T>;
138 
139  /// Meet (intersect) the information contained in the 'rhs' value with this
140  /// lattice. Returns if the state of the current lattice changed. If the
141  /// lattice elements don't have a `meet` method, this is a no-op (see below.)
142  template <typename VT,
143  std::enable_if_t<lattice_has_meet<VT>::value> * = nullptr>
144  ChangeResult meet(const VT &rhs) {
145  ValueT newValue = ValueT::meet(value, rhs);
146  assert(ValueT::meet(newValue, value) == newValue &&
147  "expected `meet` to be monotonic");
148  assert(ValueT::meet(newValue, rhs) == newValue &&
149  "expected `meet` to be monotonic");
150 
151  // Update the current optimistic value if something changed.
152  if (newValue == value)
153  return ChangeResult::NoChange;
154 
155  value = newValue;
156  return ChangeResult::Change;
157  }
158 
159  template <typename VT,
160  std::enable_if_t<!lattice_has_meet<VT>::value> * = nullptr>
161  ChangeResult meet(const VT &rhs) {
162  return ChangeResult::NoChange;
163  }
164 
165  /// Print the lattice element.
166  void print(raw_ostream &os) const override { value.print(os); }
167 
168 private:
169  /// The currently computed value that is optimistically assumed to be true.
170  ValueT value;
171 };
172 
173 //===----------------------------------------------------------------------===//
174 // AbstractSparseForwardDataFlowAnalysis
175 //===----------------------------------------------------------------------===//
176 
177 /// Base class for sparse forward data-flow analyses. A sparse analysis
178 /// implements a transfer function on operations from the lattices of the
179 /// operands to the lattices of the results. This analysis will propagate
180 /// lattices across control-flow edges and the callgraph using liveness
181 /// information.
183 public:
184  /// Initialize the analysis by visiting every owner of an SSA value: all
185  /// operations and blocks.
186  LogicalResult initialize(Operation *top) override;
187 
188  /// Visit a program point. If this is a block and all control-flow
189  /// predecessors or callsites are known, then the arguments lattices are
190  /// propagated from them. If this is a call operation or an operation with
191  /// region control-flow, then its result lattices are set accordingly.
192  /// Otherwise, the operation transfer function is invoked.
193  LogicalResult visit(ProgramPoint point) override;
194 
195 protected:
197 
198  /// The operation transfer function. Given the operand lattices, this
199  /// function is expected to set the result lattices.
200  virtual void
203  ArrayRef<AbstractSparseLattice *> resultLattices) = 0;
204 
205  /// The transfer function for calls to external functions.
206  virtual void visitExternalCallImpl(
207  CallOpInterface call,
209  ArrayRef<AbstractSparseLattice *> resultLattices) = 0;
210 
211  /// Given an operation with region control-flow, the lattices of the operands,
212  /// and a region successor, compute the lattice values for block arguments
213  /// that are not accounted for by the branching control flow (ex. the bounds
214  /// of loops).
216  Operation *op, const RegionSuccessor &successor,
217  ArrayRef<AbstractSparseLattice *> argLattices, unsigned firstIndex) = 0;
218 
219  /// Get the lattice element of a value.
221 
222  /// Get a read-only lattice element for a value and add it as a dependency to
223  /// a program point.
225  Value value);
226 
227  /// Set the given lattice element(s) at control flow entry point(s).
228  virtual void setToEntryState(AbstractSparseLattice *lattice) = 0;
230 
231  /// Join the lattice element and propagate and update if it changed.
232  void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs);
233 
234 private:
235  /// Recursively initialize the analysis on nested operations and blocks.
236  LogicalResult initializeRecursively(Operation *op);
237 
238  /// Visit an operation. If this is a call operation or an operation with
239  /// region control-flow, then its result lattices are set accordingly.
240  /// Otherwise, the operation transfer function is invoked.
241  void visitOperation(Operation *op);
242 
243  /// Visit a block to compute the lattice values of its arguments. If this is
244  /// an entry block, then the argument values are determined from the block's
245  /// "predecessors" as set by `PredecessorState`. The predecessors can be
246  /// region terminators or callable callsites. Otherwise, the values are
247  /// determined from block predecessors.
248  void visitBlock(Block *block);
249 
250  /// Visit a program point `point` with predecessors within a region branch
251  /// operation `branch`, which can either be the entry block of one of the
252  /// regions or the parent operation itself, and set either the argument or
253  /// parent result lattices.
254  void visitRegionSuccessors(ProgramPoint point, RegionBranchOpInterface branch,
255  RegionBranchPoint successor,
257 };
258 
259 //===----------------------------------------------------------------------===//
260 // SparseForwardDataFlowAnalysis
261 //===----------------------------------------------------------------------===//
262 
263 /// A sparse forward data-flow analysis for propagating SSA value lattices
264 /// across the IR by implementing transfer functions for operations.
265 ///
266 /// `StateT` is expected to be a subclass of `AbstractSparseLattice`.
267 template <typename StateT>
270  static_assert(
271  std::is_base_of<AbstractSparseLattice, StateT>::value,
272  "analysis state class expected to subclass AbstractSparseLattice");
273 
274 public:
277 
278  /// Visit an operation with the lattices of its operands. This function is
279  /// expected to set the lattices of the operation's results.
281  ArrayRef<StateT *> results) = 0;
282 
283  /// Visit a call operation to an externally defined function given the
284  /// lattices of its arguments.
285  virtual void visitExternalCall(CallOpInterface call,
286  ArrayRef<const StateT *> argumentLattices,
287  ArrayRef<StateT *> resultLattices) {
288  setAllToEntryStates(resultLattices);
289  }
290 
291  /// Given an operation with possible region control-flow, the lattices of the
292  /// operands, and a region successor, compute the lattice values for block
293  /// arguments that are not accounted for by the branching control flow (ex.
294  /// the bounds of loops). By default, this method marks all such lattice
295  /// elements as having reached a pessimistic fixpoint. `firstIndex` is the
296  /// index of the first element of `argLattices` that is set by control-flow.
298  const RegionSuccessor &successor,
299  ArrayRef<StateT *> argLattices,
300  unsigned firstIndex) {
301  setAllToEntryStates(argLattices.take_front(firstIndex));
302  setAllToEntryStates(argLattices.drop_front(
303  firstIndex + successor.getSuccessorInputs().size()));
304  }
305 
306 protected:
307  /// Get the lattice element for a value.
308  StateT *getLatticeElement(Value value) override {
309  return getOrCreate<StateT>(value);
310  }
311 
312  /// Get the lattice element for a value and create a dependency on the
313  /// provided program point.
314  const StateT *getLatticeElementFor(ProgramPoint point, Value value) {
315  return static_cast<const StateT *>(
317  value));
318  }
319 
320  /// Set the given lattice element(s) at control flow entry point(s).
321  virtual void setToEntryState(StateT *lattice) = 0;
324  {reinterpret_cast<AbstractSparseLattice *const *>(lattices.begin()),
325  lattices.size()});
326  }
327 
328 private:
329  /// Type-erased wrappers that convert the abstract lattice operands to derived
330  /// lattices and invoke the virtual hooks operating on the derived lattices.
331  void visitOperationImpl(
333  ArrayRef<AbstractSparseLattice *> resultLattices) override {
335  op,
336  {reinterpret_cast<const StateT *const *>(operandLattices.begin()),
337  operandLattices.size()},
338  {reinterpret_cast<StateT *const *>(resultLattices.begin()),
339  resultLattices.size()});
340  }
341  void visitExternalCallImpl(
342  CallOpInterface call,
343  ArrayRef<const AbstractSparseLattice *> argumentLattices,
344  ArrayRef<AbstractSparseLattice *> resultLattices) override {
346  call,
347  {reinterpret_cast<const StateT *const *>(argumentLattices.begin()),
348  argumentLattices.size()},
349  {reinterpret_cast<StateT *const *>(resultLattices.begin()),
350  resultLattices.size()});
351  }
352  void visitNonControlFlowArgumentsImpl(
353  Operation *op, const RegionSuccessor &successor,
354  ArrayRef<AbstractSparseLattice *> argLattices,
355  unsigned firstIndex) override {
357  op, successor,
358  {reinterpret_cast<StateT *const *>(argLattices.begin()),
359  argLattices.size()},
360  firstIndex);
361  }
362  void setToEntryState(AbstractSparseLattice *lattice) override {
363  return setToEntryState(reinterpret_cast<StateT *>(lattice));
364  }
365 };
366 
367 //===----------------------------------------------------------------------===//
368 // AbstractSparseBackwardDataFlowAnalysis
369 //===----------------------------------------------------------------------===//
370 
371 /// Base class for sparse backward data-flow analyses. Similar to
372 /// AbstractSparseForwardDataFlowAnalysis, but walks bottom to top.
374 public:
375  /// Initialize the analysis by visiting the operation and everything nested
376  /// under it.
377  LogicalResult initialize(Operation *top) override;
378 
379  /// Visit a program point. If this is a call operation or an operation with
380  /// block or region control-flow, then operand lattices are set accordingly.
381  /// Otherwise, invokes the operation transfer function (`visitOperationImpl`).
382  LogicalResult visit(ProgramPoint point) override;
383 
384 protected:
386  DataFlowSolver &solver, SymbolTableCollection &symbolTable);
387 
388  /// The operation transfer function. Given the result lattices, this
389  /// function is expected to set the operand lattices.
390  virtual void visitOperationImpl(
391  Operation *op, ArrayRef<AbstractSparseLattice *> operandLattices,
392  ArrayRef<const AbstractSparseLattice *> resultLattices) = 0;
393 
394  /// The transfer function for calls to external functions.
395  virtual void visitExternalCallImpl(
396  CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
397  ArrayRef<const AbstractSparseLattice *> resultLattices) = 0;
398 
399  // Visit operands on branch instructions that are not forwarded.
400  virtual void visitBranchOperand(OpOperand &operand) = 0;
401 
402  // Visit operands on call instructions that are not forwarded.
403  virtual void visitCallOperand(OpOperand &operand) = 0;
404 
405  /// Set the given lattice element(s) at control flow exit point(s).
406  virtual void setToExitState(AbstractSparseLattice *lattice) = 0;
407 
408  /// Set the given lattice element(s) at control flow exit point(s).
410 
411  /// Get the lattice element for a value.
413 
414  /// Get the lattice elements for a range of values.
416 
417  /// Join the lattice element and propagate and update if it changed.
418  void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs);
419 
420 private:
421  /// Recursively initialize the analysis on nested operations and blocks.
422  LogicalResult initializeRecursively(Operation *op);
423 
424  /// Visit an operation. If this is a call operation or an operation with
425  /// region control-flow, then its operand lattices are set accordingly.
426  /// Otherwise, the operation transfer function is invoked.
427  void visitOperation(Operation *op);
428 
429  /// Visit a block.
430  void visitBlock(Block *block);
431 
432  /// Visit an op with regions (like e.g. `scf.while`)
433  void visitRegionSuccessors(RegionBranchOpInterface branch,
435 
436  /// Visit a `RegionBranchTerminatorOpInterface` to compute the lattice values
437  /// of its operands, given its parent op `branch`. The lattice value of an
438  /// operand is determined based on the corresponding arguments in
439  /// `terminator`'s region successor(s).
440  void visitRegionSuccessorsFromTerminator(
441  RegionBranchTerminatorOpInterface terminator,
442  RegionBranchOpInterface branch);
443 
444  /// Get the lattice element for a value, and also set up
445  /// dependencies so that the analysis on the given ProgramPoint is re-invoked
446  /// if the value changes.
447  const AbstractSparseLattice *getLatticeElementFor(ProgramPoint point,
448  Value value);
449 
450  /// Get the lattice elements for a range of values, and also set up
451  /// dependencies so that the analysis on the given ProgramPoint is re-invoked
452  /// if any of the values change.
454  getLatticeElementsFor(ProgramPoint point, ValueRange values);
455 
456  SymbolTableCollection &symbolTable;
457 };
458 
459 //===----------------------------------------------------------------------===//
460 // SparseBackwardDataFlowAnalysis
461 //===----------------------------------------------------------------------===//
462 
463 /// A sparse (backward) data-flow analysis for propagating SSA value lattices
464 /// backwards across the IR by implementing transfer functions for operations.
465 ///
466 /// `StateT` is expected to be a subclass of `AbstractSparseLattice`.
467 template <typename StateT>
470 public:
472  SymbolTableCollection &symbolTable)
473  : AbstractSparseBackwardDataFlowAnalysis(solver, symbolTable) {}
474 
475  /// Visit an operation with the lattices of its results. This function is
476  /// expected to set the lattices of the operation's operands.
477  virtual void visitOperation(Operation *op, ArrayRef<StateT *> operands,
478  ArrayRef<const StateT *> results) = 0;
479 
480  /// Visit a call to an external function. This function is expected to set
481  /// lattice values of the call operands. By default, calls `visitCallOperand`
482  /// for all operands.
483  virtual void visitExternalCall(CallOpInterface call,
484  ArrayRef<StateT *> argumentLattices,
485  ArrayRef<const StateT *> resultLattices) {
486  (void)argumentLattices;
487  (void)resultLattices;
488  for (OpOperand &operand : call->getOpOperands()) {
489  visitCallOperand(operand);
490  }
491  };
492 
493 protected:
494  /// Get the lattice element for a value.
495  StateT *getLatticeElement(Value value) override {
496  return getOrCreate<StateT>(value);
497  }
498 
499  /// Set the given lattice element(s) at control flow exit point(s).
500  virtual void setToExitState(StateT *lattice) = 0;
501  void setToExitState(AbstractSparseLattice *lattice) override {
502  return setToExitState(reinterpret_cast<StateT *>(lattice));
503  }
506  {reinterpret_cast<AbstractSparseLattice *const *>(lattices.begin()),
507  lattices.size()});
508  }
509 
510 private:
511  /// Type-erased wrappers that convert the abstract lattice operands to derived
512  /// lattices and invoke the virtual hooks operating on the derived lattices.
513  void visitOperationImpl(
514  Operation *op, ArrayRef<AbstractSparseLattice *> operandLattices,
515  ArrayRef<const AbstractSparseLattice *> resultLattices) override {
517  op,
518  {reinterpret_cast<StateT *const *>(operandLattices.begin()),
519  operandLattices.size()},
520  {reinterpret_cast<const StateT *const *>(resultLattices.begin()),
521  resultLattices.size()});
522  }
523 
524  void visitExternalCallImpl(
525  CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
526  ArrayRef<const AbstractSparseLattice *> resultLattices) override {
528  call,
529  {reinterpret_cast<StateT *const *>(operandLattices.begin()),
530  operandLattices.size()},
531  {reinterpret_cast<const StateT *const *>(resultLattices.begin()),
532  resultLattices.size()});
533  }
534 };
535 
536 } // end namespace dataflow
537 } // end namespace mlir
538 
539 #endif // MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
Base class for generic analysis states.
ProgramPoint getPoint() const
Returns the program point this state is located at.
ProgramPoint point
The program point to which the state belongs.
Block represents an ordered list of Operations.
Definition: Block.h:31
Base class for all data-flow analyses.
The general data-flow analysis solver.
This class represents an operand of an operation.
Definition: Value.h:267
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents a point being branched from in the methods of the RegionBranchOpInterface.
This class represents a successor of a region.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
This class represents a collection of SymbolTables.
Definition: SymbolTable.h:283
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:381
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Base class for sparse backward data-flow analyses.
virtual void setToExitState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
SmallVector< AbstractSparseLattice * > getLatticeElements(ValueRange values)
Get the lattice elements for a range of values.
AbstractSparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void visitBranchOperand(OpOperand &operand)=0
virtual void visitOperationImpl(Operation *op, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual void visitCallOperand(OpOperand &operand)=0
LogicalResult visit(ProgramPoint point) override
Visit a program point.
void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element for a value.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting the operation and everything nested under it.
void setAllToExitStates(ArrayRef< AbstractSparseLattice * > lattices)
Set the given lattice element(s) at control flow exit point(s).
Base class for sparse forward data-flow analyses.
LogicalResult visit(ProgramPoint point) override
Visit a program point.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every owner of an SSA value: all operations and blocks.
virtual void visitOperationImpl(Operation *op, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
virtual AbstractSparseLattice * getLatticeElement(Value value)=0
Get the lattice element of a value.
virtual void visitExternalCallImpl(CallOpInterface call, ArrayRef< const AbstractSparseLattice * > argumentLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The transfer function for calls to external functions.
void setAllToEntryStates(ArrayRef< AbstractSparseLattice * > lattices)
virtual void setToEntryState(AbstractSparseLattice *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
virtual void visitNonControlFlowArgumentsImpl(Operation *op, const RegionSuccessor &successor, ArrayRef< AbstractSparseLattice * > argLattices, unsigned firstIndex)=0
Given an operation with region control-flow, the lattices of the operands, and a region successor,...
const AbstractSparseLattice * getLatticeElementFor(ProgramPoint point, Value value)
Get a read-only lattice element for a value and add it as a dependency to a program point.
void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs)
Join the lattice element and propagate and update if it changed.
This class represents an abstract lattice.
void onUpdate(DataFlowSolver *solver) const override
When the lattice gets updated, propagate an update to users of the value using its use-def chain to s...
virtual ChangeResult join(const AbstractSparseLattice &rhs)
Join the information contained in 'rhs' into this lattice.
Value getPoint() const
Return the program point this lattice is located at.
virtual ChangeResult meet(const AbstractSparseLattice &rhs)
Meet (intersect) the information in this lattice with 'rhs'.
void useDefSubscribe(DataFlowAnalysis *analysis)
Subscribe an analysis to updates of the lattice.
AbstractSparseLattice(Value value)
Lattices can only be created for values.
This class represents a lattice holding a specific value of type ValueT.
ChangeResult join(const ValueT &rhs)
Join the information contained in the 'rhs' value into this lattice.
void print(raw_ostream &os) const override
Print the lattice element.
ChangeResult meet(const VT &rhs)
Meet (intersect) the information contained in the 'rhs' value with this lattice.
decltype(&T::meet) has_meet
Trait to check if T provides a meet method.
const ValueT & getValue() const
ValueT & getValue()
Return the value held by this lattice.
llvm::is_detected< has_meet, T > lattice_has_meet
ChangeResult join(const AbstractSparseLattice &rhs) override
Join the information contained in the 'rhs' lattice into this lattice.
ChangeResult meet(const AbstractSparseLattice &rhs) override
Meet (intersect) the information contained in the 'rhs' lattice with this lattice.
Value getPoint() const
Return the program point this lattice is located at.
A sparse (backward) data-flow analysis for propagating SSA value lattices backwards across the IR by ...
StateT * getLatticeElement(Value value) override
Get the lattice element for a value.
void setAllToExitStates(ArrayRef< StateT * > lattices)
virtual void visitExternalCall(CallOpInterface call, ArrayRef< StateT * > argumentLattices, ArrayRef< const StateT * > resultLattices)
Visit a call to an external function.
void setToExitState(AbstractSparseLattice *lattice) override
Set the given lattice element(s) at control flow exit point(s).
SparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void visitOperation(Operation *op, ArrayRef< StateT * > operands, ArrayRef< const StateT * > results)=0
Visit an operation with the lattices of its results.
virtual void setToExitState(StateT *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
A sparse forward data-flow analysis for propagating SSA value lattices across the IR by implementing ...
const StateT * getLatticeElementFor(ProgramPoint point, Value value)
Get the lattice element for a value and create a dependency on the provided program point.
virtual void visitExternalCall(CallOpInterface call, ArrayRef< const StateT * > argumentLattices, ArrayRef< StateT * > resultLattices)
Visit a call operation to an externally defined function given the lattices of its arguments.
StateT * getLatticeElement(Value value) override
Get the lattice element for a value.
virtual void setToEntryState(StateT *lattice)=0
Set the given lattice element(s) at control flow entry point(s).
void setAllToEntryStates(ArrayRef< StateT * > lattices)
virtual void visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor, ArrayRef< StateT * > argLattices, unsigned firstIndex)
Given an operation with possible region control-flow, the lattices of the operands,...
virtual void visitOperation(Operation *op, ArrayRef< const StateT * > operands, ArrayRef< StateT * > results)=0
Visit an operation with the lattices of its operands.
SparseForwardDataFlowAnalysis(DataFlowSolver &solver)
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
Fundamental IR components are supported as first-class program points.