MLIR  19.0.0git
DenseAnalysis.h
Go to the documentation of this file.
1 //===- DenseAnalysis.h - Dense 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 dense 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_DENSEDATAFLOWANALYSIS_H
16 #define MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H
17 
19 #include "mlir/IR/SymbolTable.h"
22 
23 namespace mlir {
24 namespace dataflow {
25 
26 //===----------------------------------------------------------------------===//
27 // CallControlFlowAction
28 //===----------------------------------------------------------------------===//
29 
30 /// Indicates whether the control enters, exits, or skips over the callee (in
31 /// the case of external functions).
33 
34 //===----------------------------------------------------------------------===//
35 // AbstractDenseLattice
36 //===----------------------------------------------------------------------===//
37 
38 /// This class represents a dense lattice. A dense lattice is attached to
39 /// operations to represent the program state after their execution or to blocks
40 /// to represent the program state at the beginning of the block. A dense
41 /// lattice is propagated through the IR by dense data-flow analysis.
43 public:
44  /// A dense lattice can only be created for operations and blocks.
46 
47  /// Join the lattice across control-flow or callgraph edges.
48  virtual ChangeResult join(const AbstractDenseLattice &rhs) {
50  }
51 
52  virtual ChangeResult meet(const AbstractDenseLattice &rhs) {
54  }
55 };
56 
57 //===----------------------------------------------------------------------===//
58 // AbstractDenseForwardDataFlowAnalysis
59 //===----------------------------------------------------------------------===//
60 
61 /// Base class for dense forward data-flow analyses. Dense data-flow analysis
62 /// attaches a lattice between the execution of operations and implements a
63 /// transfer function from the lattice before each operation to the lattice
64 /// after. The lattice contains information about the state of the program at
65 /// that point.
66 ///
67 /// In this implementation, a lattice attached to an operation represents the
68 /// state of the program after its execution, and a lattice attached to block
69 /// represents the state of the program right before it starts executing its
70 /// body.
72 public:
74 
75  /// Initialize the analysis by visiting every program point whose execution
76  /// may modify the program state; that is, every operation and block.
77  LogicalResult initialize(Operation *top) override;
78 
79  /// Visit a program point that modifies the state of the program. If this is a
80  /// block, then the state is propagated from control-flow predecessors or
81  /// callsites. If this is a call operation or region control-flow operation,
82  /// then the state after the execution of the operation is set by control-flow
83  /// or the callgraph. Otherwise, this function invokes the operation transfer
84  /// function.
85  LogicalResult visit(ProgramPoint point) override;
86 
87 protected:
88  /// Propagate the dense lattice before the execution of an operation to the
89  /// lattice after its execution.
90  virtual void visitOperationImpl(Operation *op,
91  const AbstractDenseLattice &before,
92  AbstractDenseLattice *after) = 0;
93 
94  /// Get the dense lattice after the execution of the given program point.
96 
97  /// Get the dense lattice after the execution of the given program point and
98  /// add it as a dependency to a program point. That is, every time the lattice
99  /// after point is updated, the dependent program point must be visited, and
100  /// the newly triggered visit might update the lattice after dependent.
102  ProgramPoint point);
103 
104  /// Set the dense lattice at control flow entry point and propagate an update
105  /// if it changed.
106  virtual void setToEntryState(AbstractDenseLattice *lattice) = 0;
107 
108  /// Join a lattice with another and propagate an update if it changed.
110  propagateIfChanged(lhs, lhs->join(rhs));
111  }
112 
113  /// Visit an operation. If this is a call operation or region control-flow
114  /// operation, then the state after the execution of the operation is set by
115  /// control-flow or the callgraph. Otherwise, this function invokes the
116  /// operation transfer function.
117  virtual void processOperation(Operation *op);
118 
119  /// Propagate the dense lattice forward along the control flow edge from
120  /// `regionFrom` to `regionTo` regions of the `branch` operation. `nullopt`
121  /// values correspond to control flow branches originating at or targeting the
122  /// `branch` operation itself. Default implementation just joins the states,
123  /// meaning that operations implementing `RegionBranchOpInterface` don't have
124  /// any effect on the lattice that isn't already expressed by the interface
125  /// itself.
127  RegionBranchOpInterface branch, std::optional<unsigned> regionFrom,
128  std::optional<unsigned> regionTo, const AbstractDenseLattice &before,
129  AbstractDenseLattice *after) {
130  join(after, before);
131  }
132 
133  /// Propagate the dense lattice forward along the call control flow edge,
134  /// which can be either entering or exiting the callee. Default implementation
135  /// for enter and exit callee actions just meets the states, meaning that
136  /// operations implementing `CallOpInterface` don't have any effect on the
137  /// lattice that isn't already expressed by the interface itself. Default
138  /// implementation for the external callee action additionally sets the
139  /// "after" lattice to the entry state.
140  virtual void visitCallControlFlowTransfer(CallOpInterface call,
141  CallControlFlowAction action,
142  const AbstractDenseLattice &before,
143  AbstractDenseLattice *after) {
144  join(after, before);
145  // Note that `setToEntryState` may be a "partial fixpoint" for some
146  // lattices, e.g., lattices that are lists of maps of other lattices will
147  // only set fixpoint for "known" lattices.
149  setToEntryState(after);
150  }
151 
152  /// Visit a program point within a region branch operation with predecessors
153  /// in it. This can either be an entry block of one of the regions of the
154  /// parent operation itself.
156  RegionBranchOpInterface branch,
157  AbstractDenseLattice *after);
158 
159 private:
160  /// Visit a block. The state at the start of the block is propagated from
161  /// control-flow predecessors or callsites.
162  void visitBlock(Block *block);
163 
164  /// Visit an operation for which the data flow is described by the
165  /// `CallOpInterface`.
166  void visitCallOperation(CallOpInterface call,
167  const AbstractDenseLattice &before,
168  AbstractDenseLattice *after);
169 };
170 
171 //===----------------------------------------------------------------------===//
172 // DenseForwardDataFlowAnalysis
173 //===----------------------------------------------------------------------===//
174 
175 /// A dense forward data-flow analysis for propagating lattices before and
176 /// after the execution of every operation across the IR by implementing
177 /// transfer functions for operations.
178 ///
179 /// `LatticeT` is expected to be a subclass of `AbstractDenseLattice`.
180 template <typename LatticeT>
183  static_assert(
184  std::is_base_of<AbstractDenseLattice, LatticeT>::value,
185  "analysis state class expected to subclass AbstractDenseLattice");
186 
187 public:
188  using AbstractDenseForwardDataFlowAnalysis::
189  AbstractDenseForwardDataFlowAnalysis;
190 
191  /// Visit an operation with the dense lattice before its execution. This
192  /// function is expected to set the dense lattice after its execution and
193  /// trigger change propagation in case of change.
194  virtual void visitOperation(Operation *op, const LatticeT &before,
195  LatticeT *after) = 0;
196 
197  /// Hook for customizing the behavior of lattice propagation along the call
198  /// control flow edges. Two types of (forward) propagation are possible here:
199  /// - `action == CallControlFlowAction::Enter` indicates that:
200  /// - `before` is the state before the call operation;
201  /// - `after` is the state at the beginning of the callee entry block;
202  /// - `action == CallControlFlowAction::Exit` indicates that:
203  /// - `before` is the state at the end of a callee exit block;
204  /// - `after` is the state after the call operation.
205  /// By default, the `after` state is simply joined with the `before` state.
206  /// Concrete analyses can override this behavior or delegate to the parent
207  /// call for the default behavior. Specifically, if the `call` op may affect
208  /// the lattice prior to entering the callee, the custom behavior can be added
209  /// for `action == CallControlFlowAction::Enter`. If the `call` op may affect
210  /// the lattice post exiting the callee, the custom behavior can be added for
211  /// `action == CallControlFlowAction::Exit`.
212  virtual void visitCallControlFlowTransfer(CallOpInterface call,
213  CallControlFlowAction action,
214  const LatticeT &before,
215  LatticeT *after) {
217  call, action, before, after);
218  }
219 
220  /// Hook for customizing the behavior of lattice propagation along the control
221  /// flow edges between regions and their parent op. The control flows from
222  /// `regionFrom` to `regionTo`, both of which may be `nullopt` to indicate the
223  /// parent op. The lattice is propagated forward along this edge. The lattices
224  /// are as follows:
225  /// - `before:`
226  /// - if `regionFrom` is a region, this is the lattice at the end of the
227  /// block that exits the region; note that for multi-exit regions, the
228  /// lattices are equal at the end of all exiting blocks, but they are
229  /// associated with different program points.
230  /// - otherwise, this is the lattice before the parent op.
231  /// - `after`:
232  /// - if `regionTo` is a region, this is the lattice at the beginning of
233  /// the entry block of that region;
234  /// - otherwise, this is the lattice after the parent op.
235  /// By default, the `after` state is simply joined with the `before` state.
236  /// Concrete analyses can override this behavior or delegate to the parent
237  /// call for the default behavior. Specifically, if the `branch` op may affect
238  /// the lattice before entering any region, the custom behavior can be added
239  /// for `regionFrom == nullopt`. If the `branch` op may affect the lattice
240  /// after all terminated, the custom behavior can be added for `regionTo ==
241  /// nullptr`. The behavior can be further refined for specific pairs of "from"
242  /// and "to" regions.
244  RegionBranchOpInterface branch, std::optional<unsigned> regionFrom,
245  std::optional<unsigned> regionTo, const LatticeT &before,
246  LatticeT *after) {
248  branch, regionFrom, regionTo, before, after);
249  }
250 
251 protected:
252  /// Get the dense lattice after this program point.
253  LatticeT *getLattice(ProgramPoint point) override {
254  return getOrCreate<LatticeT>(point);
255  }
256 
257  /// Set the dense lattice at control flow entry point and propagate an update
258  /// if it changed.
259  virtual void setToEntryState(LatticeT *lattice) = 0;
260  void setToEntryState(AbstractDenseLattice *lattice) override {
261  setToEntryState(static_cast<LatticeT *>(lattice));
262  }
263 
264  /// Type-erased wrappers that convert the abstract dense lattice to a derived
265  /// lattice and invoke the virtual hooks operating on the derived lattice.
267  AbstractDenseLattice *after) final {
268  visitOperation(op, static_cast<const LatticeT &>(before),
269  static_cast<LatticeT *>(after));
270  }
271  void visitCallControlFlowTransfer(CallOpInterface call,
272  CallControlFlowAction action,
273  const AbstractDenseLattice &before,
274  AbstractDenseLattice *after) final {
275  visitCallControlFlowTransfer(call, action,
276  static_cast<const LatticeT &>(before),
277  static_cast<LatticeT *>(after));
278  }
279  void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch,
280  std::optional<unsigned> regionFrom,
281  std::optional<unsigned> regionTo,
282  const AbstractDenseLattice &before,
283  AbstractDenseLattice *after) final {
284  visitRegionBranchControlFlowTransfer(branch, regionFrom, regionTo,
285  static_cast<const LatticeT &>(before),
286  static_cast<LatticeT *>(after));
287  }
288 };
289 
290 //===----------------------------------------------------------------------===//
291 // AbstractDenseBackwardDataFlowAnalysis
292 //===----------------------------------------------------------------------===//
293 
294 /// Base class for dense backward dataflow analyses. Such analyses attach a
295 /// lattice between the execution of operations and implement a transfer
296 /// function from the lattice after the operation ot the lattice before it, thus
297 /// propagating backward.
298 ///
299 /// In this implementation, a lattice attached to an operation represents the
300 /// state of the program before its execution, and a lattice attached to a block
301 /// represents the state of the program before the end of the block, i.e., after
302 /// its terminator.
304 public:
305  /// Construct the analysis in the given solver. Takes a symbol table
306  /// collection that is used to cache symbol resolution in interprocedural part
307  /// of the analysis. The symbol table need not be prefilled.
309  SymbolTableCollection &symbolTable)
310  : DataFlowAnalysis(solver), symbolTable(symbolTable) {}
311 
312  /// Initialize the analysis by visiting every program point whose execution
313  /// may modify the program state; that is, every operation and block.
314  LogicalResult initialize(Operation *top) override;
315 
316  /// Visit a program point that modifies the state of the program. The state is
317  /// propagated along control flow directions for branch-, region- and
318  /// call-based control flow using the respective interfaces. For other
319  /// operations, the state is propagated using the transfer function
320  /// (visitOperation).
321  ///
322  /// Note: the transfer function is currently *not* invoked for operations with
323  /// region or call interface, but *is* invoked for block terminators.
324  LogicalResult visit(ProgramPoint point) override;
325 
326 protected:
327  /// Propagate the dense lattice after the execution of an operation to the
328  /// lattice before its execution.
329  virtual void visitOperationImpl(Operation *op,
330  const AbstractDenseLattice &after,
331  AbstractDenseLattice *before) = 0;
332 
333  /// Get the dense lattice before the execution of the program point. That is,
334  /// before the execution of the given operation or after the execution of the
335  /// block.
337 
338  /// Get the dense lattice before the execution of the program point `point`
339  /// and declare that the `dependent` program point must be updated every time
340  /// `point` is.
342  ProgramPoint point);
343 
344  /// Set the dense lattice before at the control flow exit point and propagate
345  /// the update if it changed.
346  virtual void setToExitState(AbstractDenseLattice *lattice) = 0;
347 
348  /// Meet a lattice with another lattice and propagate an update if it changed.
350  propagateIfChanged(lhs, lhs->meet(rhs));
351  }
352 
353  /// Visit an operation. Dispatches to specialized methods for call or region
354  /// control-flow operations. Otherwise, this function invokes the operation
355  /// transfer function.
356  virtual void processOperation(Operation *op);
357 
358  /// Propagate the dense lattice backwards along the control flow edge from
359  /// `regionFrom` to `regionTo` regions of the `branch` operation. `nullopt`
360  /// values correspond to control flow branches originating at or targeting the
361  /// `branch` operation itself. Default implementation just meets the states,
362  /// meaning that operations implementing `RegionBranchOpInterface` don't have
363  /// any effect on the lattice that isn't already expressed by the interface
364  /// itself.
366  RegionBranchOpInterface branch, RegionBranchPoint regionFrom,
367  RegionBranchPoint regionTo, const AbstractDenseLattice &after,
368  AbstractDenseLattice *before) {
369  meet(before, after);
370  }
371 
372  /// Propagate the dense lattice backwards along the call control flow edge,
373  /// which can be either entering or exiting the callee. Default implementation
374  /// for enter and exit callee action just meets the states, meaning that
375  /// operations implementing `CallOpInterface` don't have any effect on the
376  /// lattice that isn't already expressed by the interface itself. Default
377  /// implementation for external callee action additional sets the result to
378  /// the exit (fixpoint) state.
379  virtual void visitCallControlFlowTransfer(CallOpInterface call,
380  CallControlFlowAction action,
381  const AbstractDenseLattice &after,
382  AbstractDenseLattice *before) {
383  meet(before, after);
384 
385  // Note that `setToExitState` may be a "partial fixpoint" for some lattices,
386  // e.g., lattices that are lists of maps of other lattices will only
387  // set fixpoint for "known" lattices.
389  setToExitState(before);
390  }
391 
392 private:
393  /// Visit a block. The state and the end of the block is propagated from
394  /// control-flow successors of the block or callsites.
395  void visitBlock(Block *block);
396 
397  /// Visit a program point within a region branch operation with successors
398  /// (from which the state is propagated) in or after it. `regionNo` indicates
399  /// the region that contains the successor, `nullopt` indicating the successor
400  /// of the branch operation itself.
401  void visitRegionBranchOperation(ProgramPoint point,
402  RegionBranchOpInterface branch,
403  RegionBranchPoint branchPoint,
404  AbstractDenseLattice *before);
405 
406  /// Visit an operation for which the data flow is described by the
407  /// `CallOpInterface`. Performs inter-procedural data flow as follows:
408  ///
409  /// - find the callable (resolve via the symbol table),
410  /// - get the entry block of the callable region,
411  /// - take the state before the first operation if present or at block end
412  /// otherwise,
413  /// - meet that state with the state before the call-like op, or use the
414  /// custom logic if overridden by concrete analyses.
415  void visitCallOperation(CallOpInterface call,
416  const AbstractDenseLattice &after,
417  AbstractDenseLattice *before);
418 
419  /// Symbol table for call-level control flow.
420  SymbolTableCollection &symbolTable;
421 };
422 
423 //===----------------------------------------------------------------------===//
424 // DenseBackwardDataFlowAnalysis
425 //===----------------------------------------------------------------------===//
426 
427 /// A dense backward dataflow analysis propagating lattices after and before the
428 /// execution of every operation across the IR by implementing transfer
429 /// functions for opreations.
430 ///
431 /// `LatticeT` is expected to be a subclass of `AbstractDenseLattice`.
432 template <typename LatticeT>
435  static_assert(std::is_base_of_v<AbstractDenseLattice, LatticeT>,
436  "analysis state expected to subclass AbstractDenseLattice");
437 
438 public:
441 
442  /// Transfer function. Visits an operation with the dense lattice after its
443  /// execution. This function is expected to set the dense lattice before its
444  /// execution and trigger propagation in case of change.
445  virtual void visitOperation(Operation *op, const LatticeT &after,
446  LatticeT *before) = 0;
447 
448  /// Hook for customizing the behavior of lattice propagation along the call
449  /// control flow edges. Two types of (back) propagation are possible here:
450  /// - `action == CallControlFlowAction::Enter` indicates that:
451  /// - `after` is the state at the top of the callee entry block;
452  /// - `before` is the state before the call operation;
453  /// - `action == CallControlFlowAction::Exit` indicates that:
454  /// - `after` is the state after the call operation;
455  /// - `before` is the state of exit blocks of the callee.
456  /// By default, the `before` state is simply met with the `after` state.
457  /// Concrete analyses can override this behavior or delegate to the parent
458  /// call for the default behavior. Specifically, if the `call` op may affect
459  /// the lattice prior to entering the callee, the custom behavior can be added
460  /// for `action == CallControlFlowAction::Enter`. If the `call` op may affect
461  /// the lattice post exiting the callee, the custom behavior can be added for
462  /// `action == CallControlFlowAction::Exit`.
463  virtual void visitCallControlFlowTransfer(CallOpInterface call,
464  CallControlFlowAction action,
465  const LatticeT &after,
466  LatticeT *before) {
468  call, action, after, before);
469  }
470 
471  /// Hook for customizing the behavior of lattice propagation along the control
472  /// flow edges between regions and their parent op. The control flows from
473  /// `regionFrom` to `regionTo`, both of which may be `nullopt` to indicate the
474  /// parent op. The lattice is propagated back along this edge. The lattices
475  /// are as follows:
476  /// - `after`:
477  /// - if `regionTo` is a region, this is the lattice at the beginning of
478  /// the entry block of that region;
479  /// - otherwise, this is the lattice after the parent op.
480  /// - `before:`
481  /// - if `regionFrom` is a region, this is the lattice at the end of the
482  /// block that exits the region; note that for multi-exit regions, the
483  /// lattices are equal at the end of all exiting blocks, but they are
484  /// associated with different program points.
485  /// - otherwise, this is the lattice before the parent op.
486  /// By default, the `before` state is simply met with the `after` state.
487  /// Concrete analyses can override this behavior or delegate to the parent
488  /// call for the default behavior. Specifically, if the `branch` op may affect
489  /// the lattice before entering any region, the custom behavior can be added
490  /// for `regionFrom == nullopt`. If the `branch` op may affect the lattice
491  /// after all terminated, the custom behavior can be added for `regionTo ==
492  /// nullptr`. The behavior can be further refined for specific pairs of "from"
493  /// and "to" regions.
495  RegionBranchOpInterface branch, RegionBranchPoint regionFrom,
496  RegionBranchPoint regionTo, const LatticeT &after, LatticeT *before) {
498  branch, regionFrom, regionTo, after, before);
499  }
500 
501 protected:
502  /// Get the dense lattice at the given program point.
503  LatticeT *getLattice(ProgramPoint point) override {
504  return getOrCreate<LatticeT>(point);
505  }
506 
507  /// Set the dense lattice at control flow exit point (after the terminator)
508  /// and propagate an update if it changed.
509  virtual void setToExitState(LatticeT *lattice) = 0;
510  void setToExitState(AbstractDenseLattice *lattice) final {
511  setToExitState(static_cast<LatticeT *>(lattice));
512  }
513 
514  /// Type-erased wrappers that convert the abstract dense lattice to a derived
515  /// lattice and invoke the virtual hooks operating on the derived lattice.
517  AbstractDenseLattice *before) final {
518  visitOperation(op, static_cast<const LatticeT &>(after),
519  static_cast<LatticeT *>(before));
520  }
521  void visitCallControlFlowTransfer(CallOpInterface call,
522  CallControlFlowAction action,
523  const AbstractDenseLattice &after,
524  AbstractDenseLattice *before) final {
525  visitCallControlFlowTransfer(call, action,
526  static_cast<const LatticeT &>(after),
527  static_cast<LatticeT *>(before));
528  }
530  RegionBranchOpInterface branch, RegionBranchPoint regionForm,
531  RegionBranchPoint regionTo, const AbstractDenseLattice &after,
532  AbstractDenseLattice *before) final {
533  visitRegionBranchControlFlowTransfer(branch, regionForm, regionTo,
534  static_cast<const LatticeT &>(after),
535  static_cast<LatticeT *>(before));
536  }
537 };
538 
539 } // end namespace dataflow
540 } // end namespace mlir
541 
542 #endif // MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H
Base class for generic analysis states.
AnalysisState(ProgramPoint point)
Create the analysis state at the given program point.
Block represents an ordered list of Operations.
Definition: Block.h:31
Base class for all data-flow analyses.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
DataFlowAnalysis(DataFlowSolver &solver)
Create an analysis with a reference to the parent solver.
The general data-flow analysis solver.
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 collection of SymbolTables.
Definition: SymbolTable.h:283
Base class for dense backward dataflow analyses.
virtual void setToExitState(AbstractDenseLattice *lattice)=0
Set the dense lattice before at the control flow exit point and propagate the update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the call control flow edge, which can be either entering ...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
virtual void visitOperationImpl(Operation *op, const AbstractDenseLattice &after, AbstractDenseLattice *before)=0
Propagate the dense lattice after the execution of an operation to the lattice before its execution.
void meet(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Meet a lattice with another lattice and propagate an update if it changed.
virtual void processOperation(Operation *op)
Visit an operation.
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice before the execution of the program point point and declare that the dependent ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice before the execution of the program point.
AbstractDenseBackwardDataFlowAnalysis(DataFlowSolver &solver, SymbolTableCollection &symbolTable)
Construct the analysis in the given solver.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, RegionBranchPoint regionFrom, RegionBranchPoint regionTo, const AbstractDenseLattice &after, AbstractDenseLattice *before)
Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions...
Base class for dense forward data-flow analyses.
Definition: DenseAnalysis.h:71
const AbstractDenseLattice * getLatticeFor(ProgramPoint dependent, ProgramPoint point)
Get the dense lattice after the execution of the given program point and add it as a dependency to a ...
virtual AbstractDenseLattice * getLattice(ProgramPoint point)=0
Get the dense lattice after the execution of the given program point.
void join(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs)
Join a lattice with another and propagate an update if it changed.
void visitRegionBranchOperation(ProgramPoint point, RegionBranchOpInterface branch, AbstractDenseLattice *after)
Visit a program point within a region branch operation with predecessors in it.
virtual void setToEntryState(AbstractDenseLattice *lattice)=0
Set the dense lattice at control flow entry point and propagate an update if it changed.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every program point whose execution may modify the program state;...
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the call control flow edge, which can be either entering or...
LogicalResult visit(ProgramPoint point) override
Visit a program point that modifies the state of the program.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, std::optional< unsigned > regionFrom, std::optional< unsigned > regionTo, const AbstractDenseLattice &before, AbstractDenseLattice *after)
Propagate the dense lattice forward along the control flow edge from regionFrom to regionTo regions o...
virtual void processOperation(Operation *op)
Visit an operation.
virtual void visitOperationImpl(Operation *op, const AbstractDenseLattice &before, AbstractDenseLattice *after)=0
Propagate the dense lattice before the execution of an operation to the lattice after its execution.
This class represents a dense lattice.
Definition: DenseAnalysis.h:42
virtual ChangeResult join(const AbstractDenseLattice &rhs)
Join the lattice across control-flow or callgraph edges.
Definition: DenseAnalysis.h:48
virtual ChangeResult meet(const AbstractDenseLattice &rhs)
Definition: DenseAnalysis.h:52
A dense backward dataflow analysis propagating lattices after and before the execution of every opera...
void visitOperationImpl(Operation *op, const AbstractDenseLattice &after, AbstractDenseLattice *before) final
Type-erased wrappers that convert the abstract dense lattice to a derived lattice and invoke the virt...
void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, RegionBranchPoint regionForm, RegionBranchPoint regionTo, const AbstractDenseLattice &after, AbstractDenseLattice *before) final
Propagate the dense lattice backwards along the control flow edge from regionFrom to regionTo regions...
virtual void setToExitState(LatticeT *lattice)=0
Set the dense lattice at control flow exit point (after the terminator) and propagate an update if it...
LatticeT * getLattice(ProgramPoint point) override
Get the dense lattice at the given program point.
virtual void visitOperation(Operation *op, const LatticeT &after, LatticeT *before)=0
Transfer function.
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const LatticeT &after, LatticeT *before)
Hook for customizing the behavior of lattice propagation along the call control flow edges.
void setToExitState(AbstractDenseLattice *lattice) final
Set the dense lattice before at the control flow exit point and propagate the update if it changed.
void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &after, AbstractDenseLattice *before) final
Propagate the dense lattice backwards along the call control flow edge, which can be either entering ...
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, RegionBranchPoint regionFrom, RegionBranchPoint regionTo, const LatticeT &after, LatticeT *before)
Hook for customizing the behavior of lattice propagation along the control flow edges between regions...
A dense forward data-flow analysis for propagating lattices before and after the execution of every o...
LatticeT * getLattice(ProgramPoint point) override
Get the dense lattice after this program point.
virtual void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const LatticeT &before, LatticeT *after)
Hook for customizing the behavior of lattice propagation along the call control flow edges.
void setToEntryState(AbstractDenseLattice *lattice) override
Set the dense lattice at control flow entry point and propagate an update if it changed.
virtual void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, std::optional< unsigned > regionFrom, std::optional< unsigned > regionTo, const LatticeT &before, LatticeT *after)
Hook for customizing the behavior of lattice propagation along the control flow edges between regions...
virtual void visitOperation(Operation *op, const LatticeT &before, LatticeT *after)=0
Visit an operation with the dense lattice before its execution.
virtual void setToEntryState(LatticeT *lattice)=0
Set the dense lattice at control flow entry point and propagate an update if it changed.
void visitOperationImpl(Operation *op, const AbstractDenseLattice &before, AbstractDenseLattice *after) final
Type-erased wrappers that convert the abstract dense lattice to a derived lattice and invoke the virt...
void visitRegionBranchControlFlowTransfer(RegionBranchOpInterface branch, std::optional< unsigned > regionFrom, std::optional< unsigned > regionTo, const AbstractDenseLattice &before, AbstractDenseLattice *after) final
Propagate the dense lattice forward along the control flow edge from regionFrom to regionTo regions o...
void visitCallControlFlowTransfer(CallOpInterface call, CallControlFlowAction action, const AbstractDenseLattice &before, AbstractDenseLattice *after) final
Propagate the dense lattice forward along the call control flow edge, which can be either entering or...
CallControlFlowAction
Indicates whether the control enters, exits, or skips over the callee (in the case of external functi...
Definition: DenseAnalysis.h:32
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
Fundamental IR components are supported as first-class program points.