MLIR  21.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 value this lattice is located at.
40  Value getAnchor() const { return cast<Value>(AnalysisState::getAnchor()); }
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 value this lattice is located at.
90  Value getAnchor() const { return cast<Value>(anchor); }
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.
182 ///
183 /// Visit a program point in sparse forward data-flow analysis will invoke the
184 /// transfer function of the operation preceding the program point iterator.
185 /// Visit a program point at the begining of block will visit the block itself.
187 public:
188  /// Initialize the analysis by visiting every owner of an SSA value: all
189  /// operations and blocks.
190  LogicalResult initialize(Operation *top) override;
191 
192  /// Visit a program point. If this is at beginning of block and all
193  /// control-flow predecessors or callsites are known, then the arguments
194  /// lattices are propagated from them. If this is after call operation or an
195  /// operation with region control-flow, then its result lattices are set
196  /// accordingly. Otherwise, the operation transfer function is invoked.
197  LogicalResult visit(ProgramPoint *point) override;
198 
199 protected:
201 
202  /// The operation transfer function. Given the operand lattices, this
203  /// function is expected to set the result lattices.
204  virtual LogicalResult
207  ArrayRef<AbstractSparseLattice *> resultLattices) = 0;
208 
209  /// The transfer function for calls to external functions.
210  virtual void visitExternalCallImpl(
211  CallOpInterface call,
213  ArrayRef<AbstractSparseLattice *> resultLattices) = 0;
214 
215  /// Given an operation with region control-flow, the lattices of the operands,
216  /// and a region successor, compute the lattice values for block arguments
217  /// that are not accounted for by the branching control flow (ex. the bounds
218  /// of loops).
220  Operation *op, const RegionSuccessor &successor,
221  ArrayRef<AbstractSparseLattice *> argLattices, unsigned firstIndex) = 0;
222 
223  /// Get the lattice element of a value.
225 
226  /// Get a read-only lattice element for a value and add it as a dependency to
227  /// a program point.
229  Value value);
230 
231  /// Set the given lattice element(s) at control flow entry point(s).
232  virtual void setToEntryState(AbstractSparseLattice *lattice) = 0;
234 
235  /// Join the lattice element and propagate and update if it changed.
236  void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs);
237 
238  /// Visits a call operation. Given the operand lattices, sets the result
239  /// lattices. Performs interprocedural data flow as follows: if the call
240  /// operation targets an external function, or if the solver is not
241  /// interprocedural, attempts to infer the results from the call arguments
242  /// using the user-provided `visitExternalCallImpl`. Otherwise, computes the
243  /// result lattices from the return sites if all return sites are known;
244  /// otherwise, conservatively marks the result lattices as having reached
245  /// their pessimistic fixpoints.
246  /// This method can be overridden to, for example, be less conservative and
247  /// propagate the information even if some return sites are unknown.
248  virtual LogicalResult
249  visitCallOperation(CallOpInterface call,
251  ArrayRef<AbstractSparseLattice *> resultLattices);
252 
253  /// Visits a callable operation. Computes the argument lattices from call
254  /// sites if all call sites are known; otherwise, conservatively marks them
255  /// as having reached their pessimistic fixpoints.
256  /// This method can be overridden to, for example, be less conservative and
257  /// propagate the information even if some call sites are unknown.
258  virtual void
259  visitCallableOperation(CallableOpInterface callable,
261 
262 private:
263  /// Recursively initialize the analysis on nested operations and blocks.
264  LogicalResult initializeRecursively(Operation *op);
265 
266  /// Visit an operation. If this is a call operation or an operation with
267  /// region control-flow, then its result lattices are set accordingly.
268  /// Otherwise, the operation transfer function is invoked.
269  LogicalResult visitOperation(Operation *op);
270 
271  /// Visit a block to compute the lattice values of its arguments. If this is
272  /// an entry block, then the argument values are determined from the block's
273  /// "predecessors" as set by `PredecessorState`. The predecessors can be
274  /// region terminators or callable callsites. Otherwise, the values are
275  /// determined from block predecessors.
276  void visitBlock(Block *block);
277 
278  /// Visit a program point `point` with predecessors within a region branch
279  /// operation `branch`, which can either be the entry block of one of the
280  /// regions or the parent operation itself, and set either the argument or
281  /// parent result lattices.
282  /// This method can be overridden to control precisely how the region
283  /// successors of `branch` are visited. For example in order to precisely
284  /// control the order in which predecessor operand lattices are propagated
285  /// from. An override is responsible for visiting all the known predecessors
286  /// and propagating therefrom.
287  virtual void
288  visitRegionSuccessors(ProgramPoint *point, RegionBranchOpInterface branch,
289  RegionBranchPoint successor,
291 };
292 
293 //===----------------------------------------------------------------------===//
294 // SparseForwardDataFlowAnalysis
295 //===----------------------------------------------------------------------===//
296 
297 /// A sparse forward data-flow analysis for propagating SSA value lattices
298 /// across the IR by implementing transfer functions for operations.
299 ///
300 /// `StateT` is expected to be a subclass of `AbstractSparseLattice`.
301 template <typename StateT>
304  static_assert(
305  std::is_base_of<AbstractSparseLattice, StateT>::value,
306  "analysis state class expected to subclass AbstractSparseLattice");
307 
308 public:
311 
312  /// Visit an operation with the lattices of its operands. This function is
313  /// expected to set the lattices of the operation's results.
314  virtual LogicalResult visitOperation(Operation *op,
315  ArrayRef<const StateT *> operands,
316  ArrayRef<StateT *> results) = 0;
317 
318  /// Visit a call operation to an externally defined function given the
319  /// lattices of its arguments.
320  virtual void visitExternalCall(CallOpInterface call,
321  ArrayRef<const StateT *> argumentLattices,
322  ArrayRef<StateT *> resultLattices) {
323  setAllToEntryStates(resultLattices);
324  }
325 
326  /// Given an operation with possible region control-flow, the lattices of the
327  /// operands, and a region successor, compute the lattice values for block
328  /// arguments that are not accounted for by the branching control flow (ex.
329  /// the bounds of loops). By default, this method marks all such lattice
330  /// elements as having reached a pessimistic fixpoint. `firstIndex` is the
331  /// index of the first element of `argLattices` that is set by control-flow.
333  const RegionSuccessor &successor,
334  ArrayRef<StateT *> argLattices,
335  unsigned firstIndex) {
336  setAllToEntryStates(argLattices.take_front(firstIndex));
337  setAllToEntryStates(argLattices.drop_front(
338  firstIndex + successor.getSuccessorInputs().size()));
339  }
340 
341 protected:
342  /// Get the lattice element for a value.
343  StateT *getLatticeElement(Value value) override {
344  return getOrCreate<StateT>(value);
345  }
346 
347  /// Get the lattice element for a value and create a dependency on the
348  /// provided program point.
349  const StateT *getLatticeElementFor(ProgramPoint *point, Value value) {
350  return static_cast<const StateT *>(
352  value));
353  }
354 
355  /// Set the given lattice element(s) at control flow entry point(s).
356  virtual void setToEntryState(StateT *lattice) = 0;
359  {reinterpret_cast<AbstractSparseLattice *const *>(lattices.begin()),
360  lattices.size()});
361  }
362 
363 private:
364  /// Type-erased wrappers that convert the abstract lattice operands to derived
365  /// lattices and invoke the virtual hooks operating on the derived lattices.
366  LogicalResult visitOperationImpl(
368  ArrayRef<AbstractSparseLattice *> resultLattices) override {
369  return visitOperation(
370  op,
371  {reinterpret_cast<const StateT *const *>(operandLattices.begin()),
372  operandLattices.size()},
373  {reinterpret_cast<StateT *const *>(resultLattices.begin()),
374  resultLattices.size()});
375  }
376  void visitExternalCallImpl(
377  CallOpInterface call,
378  ArrayRef<const AbstractSparseLattice *> argumentLattices,
379  ArrayRef<AbstractSparseLattice *> resultLattices) override {
381  call,
382  {reinterpret_cast<const StateT *const *>(argumentLattices.begin()),
383  argumentLattices.size()},
384  {reinterpret_cast<StateT *const *>(resultLattices.begin()),
385  resultLattices.size()});
386  }
387  void visitNonControlFlowArgumentsImpl(
388  Operation *op, const RegionSuccessor &successor,
389  ArrayRef<AbstractSparseLattice *> argLattices,
390  unsigned firstIndex) override {
392  op, successor,
393  {reinterpret_cast<StateT *const *>(argLattices.begin()),
394  argLattices.size()},
395  firstIndex);
396  }
397  void setToEntryState(AbstractSparseLattice *lattice) override {
398  return setToEntryState(reinterpret_cast<StateT *>(lattice));
399  }
400 };
401 
402 //===----------------------------------------------------------------------===//
403 // AbstractSparseBackwardDataFlowAnalysis
404 //===----------------------------------------------------------------------===//
405 
406 /// Base class for sparse backward data-flow analyses. Similar to
407 /// AbstractSparseForwardDataFlowAnalysis, but walks bottom to top.
409 public:
410  /// Initialize the analysis by visiting the operation and everything nested
411  /// under it.
412  LogicalResult initialize(Operation *top) override;
413 
414  /// Visit a program point. If it is after call operation or an operation with
415  /// block or region control-flow, then operand lattices are set accordingly.
416  /// Otherwise, invokes the operation transfer function (`visitOperationImpl`).
417  LogicalResult visit(ProgramPoint *point) override;
418 
419 protected:
421  DataFlowSolver &solver, SymbolTableCollection &symbolTable);
422 
423  /// The operation transfer function. Given the result lattices, this
424  /// function is expected to set the operand lattices.
425  virtual LogicalResult visitOperationImpl(
426  Operation *op, ArrayRef<AbstractSparseLattice *> operandLattices,
427  ArrayRef<const AbstractSparseLattice *> resultLattices) = 0;
428 
429  /// The transfer function for calls to external functions.
430  virtual void visitExternalCallImpl(
431  CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
432  ArrayRef<const AbstractSparseLattice *> resultLattices) = 0;
433 
434  // Visit operands on branch instructions that are not forwarded.
435  virtual void visitBranchOperand(OpOperand &operand) = 0;
436 
437  // Visit operands on call instructions that are not forwarded.
438  virtual void visitCallOperand(OpOperand &operand) = 0;
439 
440  /// Set the given lattice element(s) at control flow exit point(s) and
441  /// propagate the update if it chaned.
442  virtual void setToExitState(AbstractSparseLattice *lattice) = 0;
443 
444  /// Set the given lattice element(s) at control flow exit point(s) and
445  /// propagate the update if it chaned.
447 
448  /// Get the lattice element for a value.
450 
451  /// Get the lattice elements for a range of values.
453 
454  /// Join the lattice element and propagate and update if it changed.
455  void meet(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs);
456 
457  /// Visits a callable operation. If all the call sites are known computes the
458  /// operand lattices of `op` from the result lattices of all the call sites;
459  /// otherwise, conservatively marks them as having reached their pessimistic
460  /// fixpoints.
461  /// This method can be overridden to, for example, be less conservative and
462  /// propagate the information even if some call sites are unknown.
463  virtual LogicalResult
464  visitCallableOperation(Operation *op, CallableOpInterface callable,
465  ArrayRef<AbstractSparseLattice *> operandLattices);
466 
467 private:
468  /// Recursively initialize the analysis on nested operations and blocks.
469  LogicalResult initializeRecursively(Operation *op);
470 
471  /// Visit an operation. If this is a call operation or an operation with
472  /// region control-flow, then its operand lattices are set accordingly.
473  /// Otherwise, the operation transfer function is invoked.
474  LogicalResult visitOperation(Operation *op);
475 
476  /// Visit a block.
477  void visitBlock(Block *block);
478 
479  /// Visit an op with regions (like e.g. `scf.while`)
480  void visitRegionSuccessors(RegionBranchOpInterface branch,
482 
483  /// Visit a `RegionBranchTerminatorOpInterface` to compute the lattice values
484  /// of its operands, given its parent op `branch`. The lattice value of an
485  /// operand is determined based on the corresponding arguments in
486  /// `terminator`'s region successor(s).
487  void visitRegionSuccessorsFromTerminator(
488  RegionBranchTerminatorOpInterface terminator,
489  RegionBranchOpInterface branch);
490 
491  /// Get the lattice element for a value, and also set up
492  /// dependencies so that the analysis on the given ProgramPoint is re-invoked
493  /// if the value changes.
494  const AbstractSparseLattice *getLatticeElementFor(ProgramPoint *point,
495  Value value);
496 
497  /// Get the lattice elements for a range of values, and also set up
498  /// dependencies so that the analysis on the given ProgramPoint is re-invoked
499  /// if any of the values change.
501  getLatticeElementsFor(ProgramPoint *point, ValueRange values);
502 
503  SymbolTableCollection &symbolTable;
504 };
505 
506 //===----------------------------------------------------------------------===//
507 // SparseBackwardDataFlowAnalysis
508 //===----------------------------------------------------------------------===//
509 
510 /// A sparse (backward) data-flow analysis for propagating SSA value lattices
511 /// backwards across the IR by implementing transfer functions for operations.
512 ///
513 /// `StateT` is expected to be a subclass of `AbstractSparseLattice`.
514 ///
515 /// Visit a program point in sparse backward data-flow analysis will invoke the
516 /// transfer function of the operation preceding the program point iterator.
517 /// Visit a program point at the begining of block will visit the block itself.
518 template <typename StateT>
521 public:
523  SymbolTableCollection &symbolTable)
524  : AbstractSparseBackwardDataFlowAnalysis(solver, symbolTable) {}
525 
526  /// Visit an operation with the lattices of its results. This function is
527  /// expected to set the lattices of the operation's operands.
528  virtual LogicalResult visitOperation(Operation *op,
529  ArrayRef<StateT *> operands,
530  ArrayRef<const StateT *> results) = 0;
531 
532  /// Visit a call to an external function. This function is expected to set
533  /// lattice values of the call operands. By default, calls `visitCallOperand`
534  /// for all operands.
535  virtual void visitExternalCall(CallOpInterface call,
536  ArrayRef<StateT *> argumentLattices,
537  ArrayRef<const StateT *> resultLattices) {
538  (void)argumentLattices;
539  (void)resultLattices;
540  for (OpOperand &operand : call->getOpOperands()) {
541  visitCallOperand(operand);
542  }
543  };
544 
545 protected:
546  /// Get the lattice element for a value.
547  StateT *getLatticeElement(Value value) override {
548  return getOrCreate<StateT>(value);
549  }
550 
551  /// Set the given lattice element(s) at control flow exit point(s).
552  virtual void setToExitState(StateT *lattice) = 0;
553  void setToExitState(AbstractSparseLattice *lattice) override {
554  return setToExitState(reinterpret_cast<StateT *>(lattice));
555  }
558  {reinterpret_cast<AbstractSparseLattice *const *>(lattices.begin()),
559  lattices.size()});
560  }
561 
562 private:
563  /// Type-erased wrappers that convert the abstract lattice operands to derived
564  /// lattices and invoke the virtual hooks operating on the derived lattices.
565  LogicalResult visitOperationImpl(
566  Operation *op, ArrayRef<AbstractSparseLattice *> operandLattices,
567  ArrayRef<const AbstractSparseLattice *> resultLattices) override {
568  return visitOperation(
569  op,
570  {reinterpret_cast<StateT *const *>(operandLattices.begin()),
571  operandLattices.size()},
572  {reinterpret_cast<const StateT *const *>(resultLattices.begin()),
573  resultLattices.size()});
574  }
575 
576  void visitExternalCallImpl(
577  CallOpInterface call, ArrayRef<AbstractSparseLattice *> operandLattices,
578  ArrayRef<const AbstractSparseLattice *> resultLattices) override {
580  call,
581  {reinterpret_cast<StateT *const *>(operandLattices.begin()),
582  operandLattices.size()},
583  {reinterpret_cast<const StateT *const *>(resultLattices.begin()),
584  resultLattices.size()});
585  }
586 };
587 
588 } // end namespace dataflow
589 } // end namespace mlir
590 
591 #endif // MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H
Base class for generic analysis states.
LatticeAnchor getAnchor() const
Returns the lattice anchor this state is located at.
LatticeAnchor anchor
The lattice anchor to which the state belongs.
Block represents an ordered list of Operations.
Definition: Block.h:33
Base class for all data-flow analyses.
The general data-flow analysis solver.
This class represents an operand of an operation.
Definition: Value.h:257
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:387
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) and propagate the update if it chaned.
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 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 LogicalResult visitCallableOperation(Operation *op, CallableOpInterface callable, ArrayRef< AbstractSparseLattice * > operandLattices)
Visits a callable operation.
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) and propagate the update if it chaned.
virtual LogicalResult visitOperationImpl(Operation *op, ArrayRef< AbstractSparseLattice * > operandLattices, ArrayRef< const AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
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 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).
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.
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,...
virtual LogicalResult visitCallOperation(CallOpInterface call, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)
Visits a call operation.
virtual void visitCallableOperation(CallableOpInterface callable, ArrayRef< AbstractSparseLattice * > argLattices)
Visits a callable operation.
virtual LogicalResult visitOperationImpl(Operation *op, ArrayRef< const AbstractSparseLattice * > operandLattices, ArrayRef< AbstractSparseLattice * > resultLattices)=0
The operation transfer function.
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.
virtual ChangeResult meet(const AbstractSparseLattice &rhs)
Meet (intersect) the information in this lattice with 'rhs'.
Value getAnchor() const
Return the value this lattice is located at.
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.
Value getAnchor() const
Return the value this lattice is located at.
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.
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) and propagate the update if it chaned.
SparseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
virtual void setToExitState(StateT *lattice)=0
Set the given lattice element(s) at control flow exit point(s).
virtual LogicalResult visitOperation(Operation *op, ArrayRef< StateT * > operands, ArrayRef< const StateT * > results)=0
Visit an operation with the lattices of its results.
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 LogicalResult visitOperation(Operation *op, ArrayRef< const StateT * > operands, ArrayRef< StateT * > results)=0
Visit an operation with the lattices of its operands.
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,...
SparseForwardDataFlowAnalysis(DataFlowSolver &solver)
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
Program point represents a specific location in the execution of a program.