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