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