[mlir] add backward dense dataflow analysis

[ftynse]

Summary

This is the counterpart to the forward dense dataflow analysis and
integrates into the dataflow framework. The implementation follows the
structure of existing dataflow analyses.

[ftynse]

Remove spurious changes

[Mogball]

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

207

How does the behaviour of linalg.generic differ from the interface here?

[phisiart]

Thanks! Let me go over this in more detail tonight.

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

228

it

[ftynse]

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

207

linalg.generic has its own semantics, specifically read/write to memref operands, and not just forwards control to its body. So the analysis should visit it as a regular operation in addition to following the control flow.

[phisiart]

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

64

Should we rename to AbstractDenseForwardDataFlowAnalysis? If you are concerned about backward compatibility, you can add:

using AbstractDenseDataFlowAnalysis = AbstractDenseForwardDataFlowAnalysis;

91–92

Note that when you "visit" a program point, you usually don't update the state on that program point itself.

Conceptually, this dataflow framework attaches states to "nodes" and visits "edges". For example, in a sparse analysis, you visit an op:

%result = some_op (%arg1, %arg2)

During the visit, you read the states on %arg1 and %arg2, and write the state on %result. You are not "updating" any state on some_op itself.

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

203

I'm a bit concerned about the design here:

In a dense forward analysis, getLattice(op) means the lattice element after op, but here it means the lattice element before op.

This inconsistency could lead to confusion when people read the results of multiple analyses. For example, live range analysis depends on reaching definition analysis (forward) and live variable analysis (backward). It could be weird if, in different analyses, getOrCreate<T>(op) loads lattice elements from different locations.

Should we make it consistent that getLattice(op) means after op, and getLattice(block) means at the entry of block?

284

I'm curious: why are we using meet in backward analysis and join in forward analysis? I tend to think that we can just use join in both cases.

I see that https://en.wikipedia.org/wiki/Join_and_meet says join and meet go in opposite directions, but it seems that we only need this separation if a lattice needs to define join and meet at the same time. But I think that in each analysis, we only need one kind of merge, right?

[Mogball]

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

203

It's contextual to the analysis what getLattice means. It could alleviate confusion to name them getLatticeAfter and getLatticeBefore respectively.

[ftynse]

Fix nitpicks.

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

64

Not in this patch, renamings are much better off as a standalone patch. And the change, if made, should also affect the sparse analyses that have the same duality. I don't have any problem with the existing naming convention, by the way.

91–92

I don't see how the suggested change reflects the associated comment. Both function arguments are program points. The comment argues that program points are "visited" and not "updated". The original commit uses "updated" consistently for both. The proposed change uses "visited" for one and "updated" for another, adding more terminology without removing the existing one. This only adds complexity and mental load and no clear value.

The documentation repeatedly states that state is attached to program points, e.g. https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Analysis/DataFlowFramework.h#L55-L57, https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Analysis/DataFlowFramework.h#L62-L63, https://github.com/llvm/llvm-project/blob/main/mlir/include/mlir/Analysis/DataFlowFramework.h#L264-L265, etc. So it doesn't sound right to start introducing some distinction at this level.

It sounds a bit of a mouthful to say, but maybe "analysis state associated with program point foo" would be clearer here.

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

203

The meaning of a lattice for a specific analysis is documented by the analysis. A lattice is defined for a program point. Program points are not limited to operations and blocks, so the API shouldn't over-optimize for those. Even for the operation and block points, the "before"/"after" distinction would be require using opposite calls: in forward analyses, one would want a getLatticeBefore(block) and a getLatticeAfter(op) since getLatticeAfter(block) cannot be clearly associated with the state at the beginning of the block. Since both directions will need to provide both "before" and 'after", the potential for misuse isn't really removed. For lattices associated with values or user-defined points, it's even less clear what "before" and 'after" would mean.

284

For consistency with the sparse analysis. The way that both analysis are currently written doesn't seem to differentiate between the two operations, and will likely have to be updated to support them properly.

[phisiart]

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

91–92

Sorry for the confusion.

---

The difference in the suggested change is subtle in dense analyses, but more obvious in sparse analyses.

In a sparse analysis, we attach lattices to mlir::Values and update these lattices, but visit mlir::Operations. In SparseAnalysis.h, visitOperation looks like this:

template <typename StateT>
class SparseDataFlowAnalysis : public AbstractSparseDataFlowAnalysis {
  ...
  virtual void visitOperation(Operation *op, ArrayRef<const StateT *> operands,
                              ArrayRef<StateT *> results) = 0;
  ...
};

The op was inserted in the worklist and visited, but operands and results are lattices attached to mlir::Values and those are updated during the visit.

Then, when a lattice on a mlir::Value is updated, all ops that use this mlir::Value are inserted to the worklist and visited. But the ops themselves are not "updated".

Both mlir::Operation * and mlir::Value are ProgramPoints.

---

Going back to dense analyses. Conceptually and theoretically speaking, when we attach lattices to mlir::Operation *s, we are not really attaching lattices onto the ops themselves, but before and after ops. This is also what the comment says ("Get the dense lattice after the execution of the given program point").

When we visit an mlir::Operation *, we are updating lattices before / after this op, but not the on the op itself.

Therefore, in a forward dense analysis, the full description is that:

Every time the lattice after point is updated, the dependent program point must be visited, and the newly triggered visit might update the lattice after dependent.

---

Apologize for being too pedantic here.

The comment here doesn't warrant so much attention, but I do want to note that in our past experience in using the dataflow API, we got confused by how to understand what are being visited and where are lattices attached, and after spending a lot of time, we found that the "node/edge" way of thinking helped a lot (this also fits the concept of transfer function - an op transfers from some input state(s) to some output state(s)).

I think the bigger issue is that ProgramPoint is very generic and used as both nodes (where we attach lattices) and edges (where we define transfer functions). This distinction exists throughout the framework but it's not explicitly spelled out in the type(s).

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

203

Sounds good, let's not change in this patch then.

Just a quick note: in our project, we have a wrapper of this API that provides four functions: GetStateBefore(op), GetStateAfter(op), GetStateAtEntryOf(block), GetStateAtEndOf(block) just to eliminate confusions.

284

Sounds good. Let's not change this patch then.

I kind of think that meet is unnecessary in sparse analysis as well and should be removed, but that's clearly out of the scope of this patch.

[ftynse]

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

91–92

Thanks for the detailed write-up! FWIW, it wasn't obvious for me what depends on what by reading the comment. I've put your full description into the comment for more clarity.

I can see the node/edge model and how it helps reasoning about regular dataflow analyses. MLIR needs to be very open as infrastructure, hence the notion of ProgramPoint that is extensible. I *think* the top-level data flow framework only reasons about those and, if we wanted to differentiate nodes and edges, we'd have to do it at that level. My current mental model is that only nodes, i.e. ProgramPoints matter. A lattice is associated with a program point. The framework visits program points: https://github.com/llvm/llvm-project/blob/425c57489283adcaa28e916c5b1c2826e7a0e042/mlir/include/mlir/Analysis/DataFlowFramework.h#L384. There are also dependencies between essentially pairs of (program point, lattice) so when a lattice is updated, the dependent program points need to be (re)visited and the corresponding lattices updated. But I don't really dissociate lattices and program points at that level. It's specific to an analysis and a program point that the lattice describes the state before or after a program point.

Where it gets tricky is that we may have program points that don't have a lattice associated (operations, blocks, and generic points for the sparse case) as well as program points that have a lattice associated but not directly visited (values in the sparse case). Furthermore, visiting a program point does not necessarily update the lattice associated with that point (which is reasonable given that it may be in a state where an update is no longer possible). What's worse, visiting a program point may update the lattices associated with *other* program points. This is the case for sparse analysis where visiting an operation or a block point updates the lattices for values. Maybe this is where the dissociation should happen and we should somehow indicate which kinds of program points are "visitable" and which kinds have lattices associated.

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

203

These sounds helpful as an addition. I suppose there is a way to implement them generically by checking if the state is associated with a forward or with a backward analysis. Any chance of upstreaming these?

284

I was thinking about making meet actually different from join in a correct way, but this probably needs a case where a lattice is used in both directions that I don't have.

There is a related issue. What currently happens is that the analysis will reset the lattice to the entry (for forward) or exit (for backward) state when it hits an ununalizable case. This implies that we start in the "bottom" state for joins (respectively in the" top" state for meets) so the following join (meet) always takes the other value. I suppose there are cases where we will need to differentiate the entry (exit) state and the state after hitting the unanalyzable case. That is, start in the "bottom" ("top") state and set to "top" ("bottom") state when using join (meet). For the propagation itself, it looks like having only "join" is sufficient, but for consistency checks of the lattice we may want "meet".

WDYT? We can start with removing "meet" from both and see where it goes from there.

mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h

 // dead code analysis to prune dead code during the analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H
 #define MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H
 
 #include "mlir/Analysis/DataFlowFramework.h"
+#include "mlir/IR/SymbolTable.h"
 
 namespace mlir {
 
 class RegionBranchOpInterface;
 
 namespace dataflow {
 
 //===----------------------------------------------------------------------===//
 // AbstractDenseLattice
 //===----------------------------------------------------------------------===//
 
 /// This class represents a dense lattice. A dense lattice is attached to
 /// operations to represent the program state after their execution or to blocks
 /// to represent the program state at the beginning of the block. A dense
 /// lattice is propagated through the IR by dense data-flow analysis.
 class AbstractDenseLattice : public AnalysisState {
 public:
   /// A dense lattice can only be created for operations and blocks.
   using AnalysisState::AnalysisState;
 
   /// Join the lattice across control-flow or callgraph edges.
-  virtual ChangeResult join(const AbstractDenseLattice &rhs) = 0;
+  virtual ChangeResult join(const AbstractDenseLattice &rhs) {
+    return ChangeResult::NoChange;
+  }
+
+  virtual ChangeResult meet(const AbstractDenseLattice &rhs) {
+    return ChangeResult::NoChange;
+  }
 };
 
 //===----------------------------------------------------------------------===//
 // AbstractDenseDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// Base class for dense data-flow analyses. Dense data-flow analysis attaches a
-/// lattice between the execution of operations and implements a transfer
-/// function from the lattice before each operation to the lattice after. The
-/// lattice contains information about the state of the program at that point.
+/// Base class for dense (forward) data-flow analyses. Dense data-flow analysis
+/// attaches a lattice between the execution of operations and implements a
+/// transfer function from the lattice before each operation to the lattice
+/// after. The lattice contains information about the state of the program at
+/// that point.
 ///
 /// In this implementation, a lattice attached to an operation represents the
 /// state of the program after its execution, and a lattice attached to block
 /// represents the state of the program right before it starts executing its
 /// body.
 class AbstractDenseDataFlowAnalysis : public DataFlowAnalysis {
 public:
   using DataFlowAnalysis::DataFlowAnalysis;
 
   /// Initialize the analysis by visiting every program point whose execution
   /// may modify the program state; that is, every operation and block.
   LogicalResult initialize(Operation *top) override;
 
   /// Visit a program point that modifies the state of the program. If this is a
protected:
   virtual void visitOperationImpl(Operation *op,
                                   const AbstractDenseLattice &before,
                                   AbstractDenseLattice *after) = 0;
 
   /// Get the dense lattice after the execution of the given program point.
   virtual AbstractDenseLattice *getLattice(ProgramPoint point) = 0;
 
   /// Get the dense lattice after the execution of the given program point and
-  /// add it as a dependency to a program point.
+  /// indicate that the `dependent` program point must be updated every time
+  /// `point` is.
   const AbstractDenseLattice *getLatticeFor(ProgramPoint dependent,
                                             ProgramPoint point);
 
   /// Set the dense lattice at control flow entry point and propagate an update
   /// if it changed.
   virtual void setToEntryState(AbstractDenseLattice *lattice) = 0;
 
   /// Join a lattice with another and propagate an update if it changed.
protected:
   /// in it. This can either be an entry block of one of the regions of the
   /// parent operation itself.
   void visitRegionBranchOperation(ProgramPoint point,
                                   RegionBranchOpInterface branch,
                                   AbstractDenseLattice *after);
 
 private:
   /// Visit a block. The state at the start of the block is propagated from
-  /// control-flow predecessors or callsites
+  /// control-flow predecessors or callsites.
   void visitBlock(Block *block);
 };
 
 //===----------------------------------------------------------------------===//
 // DenseDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
 /// A dense (forward) data-flow analysis for propagating lattices before and
 /// after the execution of every operation across the IR by implementing
 /// transfer functions for operations.
 ///
-/// `StateT` is expected to be a subclass of `AbstractDenseLattice`.
+/// `LatticeT` is expected to be a subclass of `AbstractDenseLattice`.
 template <typename LatticeT>
 class DenseDataFlowAnalysis : public AbstractDenseDataFlowAnalysis {
   static_assert(
       std::is_base_of<AbstractDenseLattice, LatticeT>::value,
       "analysis state class expected to subclass AbstractDenseLattice");
 
 public:
   using AbstractDenseDataFlowAnalysis::AbstractDenseDataFlowAnalysis;
 
   /// Visit an operation with the dense lattice before its execution. This
-  /// function is expected to set the dense lattice after its execution.
+  /// function is expected to set the dense lattice after its execution and
+  /// trigger change propagation in case of change.
   virtual void visitOperation(Operation *op, const LatticeT &before,
                               LatticeT *after) = 0;
 
 protected:
   /// Get the dense lattice after this program point.
   LatticeT *getLattice(ProgramPoint point) override {
     return getOrCreate<LatticeT>(point);
   }
protected:
   /// lattice and invoke the virtual hooks operating on the derived lattice.
   void visitOperationImpl(Operation *op, const AbstractDenseLattice &before,
                           AbstractDenseLattice *after) override {
     visitOperation(op, static_cast<const LatticeT &>(before),
                    static_cast<LatticeT *>(after));
   }
 };
 
+//===----------------------------------------------------------------------===//
+// AbstractDenseBackwardDataFlowAnalysis
+//===----------------------------------------------------------------------===//
+
+/// Base class for dense backward dataflow analyses. Such analyses attach a
+/// lattice between the execution of operations and implement a transfer
+/// function from the lattice after the operation ot the lattice before it, thus
+/// propagating backward.
+///
+/// In this implementation, a lattice attached to an operation represents the
+/// state of the program before its execution, and a lattice attached to a block
+/// represents the state of the program before the end of the block, i.e., after
+/// its terminator.
+class AbstractDenseBackwardDataFlowAnalysis : public DataFlowAnalysis {
+public:
+  /// Construct the analysis in the given solver. Takes a symbol table
+  /// collection that is used to cache symbol resolution in interprocedural part
+  /// of the analysis. The symbol table need not be prefilled.
+  AbstractDenseBackwardDataFlowAnalysis(DataFlowSolver &solver,
+                                        SymbolTableCollection &symbolTable)
+      : DataFlowAnalysis(solver), symbolTable(symbolTable) {}
+
+  /// Initialize the analysis by visiting every program point whose execution
+  /// may modify the program state; that is, every operation and block.
+  LogicalResult initialize(Operation *top) override;
+
+  /// Visit a program point that modifies the state of the program. The state is
+  /// propagated along control flow directions for branch-, region- and
+  /// call-based control flow using the respective interfaces. For other
+  /// operations, the state is propagated using the transfer function
+  /// (visitOperation).
+  ///
+  /// Note: the transfer function is currently *not* invoked for operations with
+  /// region or call interface, but *is* invoked for block terminators.
+  LogicalResult visit(ProgramPoint point) override;
+
+protected:
+  /// Propagate the dense lattice after the execution of an operation to the
+  /// lattice before its execution.
+  virtual void visitOperationImpl(Operation *op,
+                                  const AbstractDenseLattice &after,
+                                  AbstractDenseLattice *before) = 0;
+
+  /// Get the dense lattice before the execution of the program point. That is,
+  /// before the execution of the given operation or after the execution of the
+  /// block.
+  virtual AbstractDenseLattice *getLattice(ProgramPoint point) = 0;
+
+  /// Get the dense lattice before the execution of the program point `point`
+  /// and declare that the `dependent` program point must be updated every time
+  /// `point` is.
+  const AbstractDenseLattice *getLatticeFor(ProgramPoint dependent,
+                                            ProgramPoint point);
+
+  /// Set the dense lattice before at the control flow exit point and propagate
+  /// the update if it changed.
+  virtual void setToExitState(AbstractDenseLattice *lattice) = 0;
+
+  /// Meet a lattice with another lattice and propagate an update if ti changed
+  void meet(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs) {
+    propagateIfChanged(lhs, lhs->meet(rhs));
+  }
+
+  /// Visit an operation. If this is a call operation or region control-flow
+  /// operation, then the state after the execution of the operation is set by
+  /// control-flow or the callgraph. Otherwise, this function invokes the
+  /// operation transfer function.
+  virtual void processOperation(Operation *op);
+
+  /// Visit a program point within a region branch operation with successors
+  /// (from which the state is propagated) in or after it. `regionNo` indicates
+  /// the region that contains the successor, `nullopt` indicating the successor
+  /// of the branch operation itself.
+  void visitRegionBranchOperation(ProgramPoint point,
+                                  RegionBranchOpInterface branch,
+                                  std::optional<unsigned> regionNo,
+                                  AbstractDenseLattice *before);
+
+private:
+  /// VIsit a block. The state and the end of the block is propagated from
+  /// control-flow successors of the block or callsites.
+  void visitBlock(Block *block);
+
+  /// Symbol table for call-level control flow.
+  SymbolTableCollection &symbolTable;
+};
+
+//===----------------------------------------------------------------------===//
+// DenseBackwardDataFlowAnalysis
+//===----------------------------------------------------------------------===//
+
+/// A dense backward dataflow analysis propagating lattices after and before the
+/// execution of every operation across the IR by implementing transfer
+/// functions for opreations.
+///
+/// `LatticeT` is expected to be a subclass of `AbstractDenseLattice`.
+template <typename LatticeT>
+class DenseBackwardDataFlowAnalysis
+    : public AbstractDenseBackwardDataFlowAnalysis {
+  static_assert(std::is_base_of_v<AbstractDenseLattice, LatticeT>,
+                "analysis state expected to subclass AbstractDenseLattice");
+
+public:
+  using AbstractDenseBackwardDataFlowAnalysis::
+      AbstractDenseBackwardDataFlowAnalysis;
+
+  /// Transfer function. Visits an operation with the dense lattice after its
+  /// execution. This function is expected to set the dense lattice before its
+  /// execution and trigger propagation in case of change.
+  virtual void visitOperation(Operation *op, const LatticeT &after,
+                              LatticeT *before) = 0;
+
+protected:
+  /// Get the dense lattice at the given program point.
+  LatticeT *getLattice(ProgramPoint point) override {
+    return getOrCreate<LatticeT>(point);
+  }
+
+  /// Set the dense lattice at control flow exit point (after the terminator)
+  /// and propagate an update if it changed.
+  virtual void setToExitState(LatticeT *lattice) = 0;
+  void setToExitState(AbstractDenseLattice *lattice) override {
+    setToExitState(static_cast<LatticeT *>(lattice));
+  }
+
+  /// Type-erased wrapper that convert the abstract dense lattice to a derived
+  /// lattice and invoke the virtual hooks operating on the derived lattice.
+  void visitOperationImpl(Operation *op, const AbstractDenseLattice &after,
+                          AbstractDenseLattice *before) override {
+    visitOperation(op, static_cast<const LatticeT &>(after),
+                   static_cast<LatticeT *>(before));
+  }
+};
+
 } // end namespace dataflow
 } // end namespace mlir
 
 #endif // MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H

mlir/include/mlir/Analysis/DataFlowFramework.h

 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H
 #define MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H
 
 #include "mlir/IR/Operation.h"
 #include "mlir/Support/StorageUniquer.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Support/TypeName.h"
 #include <queue>
 
 namespace mlir {
 
 //===----------------------------------------------------------------------===//
 // ChangeResult
 //===----------------------------------------------------------------------===//

 
 //===----------------------------------------------------------------------===//
 // DataFlowSolver
 //===----------------------------------------------------------------------===//
 
 /// The general data-flow analysis solver. This class is responsible for
 /// orchestrating child data-flow analyses, running the fixed-point iteration
 /// algorithm, managing analysis state and program point memory, and tracking
-/// dependencies beteen analyses, program points, and analysis states.
+/// dependencies between analyses, program points, and analysis states.
 ///
 /// Steps to run a data-flow analysis:
 ///
 /// 1. Load and initialize children analyses. Children analyses are instantiated
 ///    in the solver and initialized, building their dependency relations.
 /// 2. Configure and run the analysis. The solver invokes the children analyses
 ///    according to their dependency relations until a fixed point is reached.
 /// 3. Query analysis state results from the solver.

 ///    default value.
 class AnalysisState {
 public:
   virtual ~AnalysisState();
 
   /// Create the analysis state at the given program point.
   AnalysisState(ProgramPoint point) : point(point) {}
 
-  /// Returns the program point this static is located at.
+  /// Returns the program point this state is located at.
   ProgramPoint getPoint() const { return point; }
 
   /// Print the contents of the analysis state.
   virtual void print(raw_ostream &os) const = 0;
+  LLVM_DUMP_METHOD void dump() const;
 
   /// Add a dependency to this analysis state on a program point and an
   /// analysis. If this state is updated, the analysis will be invoked on the
   /// given program point again (in onUpdate()).
   void addDependency(ProgramPoint dependent, DataFlowAnalysis *analysis);
 
 protected:
   /// This function is called by the solver when the analysis state is updated
public:
   /// calling `addDependency` between the input state and a program point,
   /// indicating that, if the state is updated, the solver should invoke `solve`
   /// on the program point. The dependent point does not have to be the same as
   /// the provided point. An update to a state is propagated by calling
   /// `propagateIfChange` on the state. If the state has changed, then all its
   /// dependents are placed on the worklist.
   ///
   /// The dependency graph does not need to be static. Each invocation of
-  /// `visit` can add new dependencies, but these dependecies will not be
+  /// `visit` can add new dependencies, but these dependencies will not be
   /// dynamically added to the worklist because the solver doesn't know what
   /// will provide a value for then.
   virtual LogicalResult visit(ProgramPoint point) = 0;
 
 protected:
   /// Create a dependency between the given analysis state and program point
   /// on this analysis.
   void addDependency(AnalysisState *state, ProgramPoint point);
 
   /// Propagate an update to a state if it changed.
   void propagateIfChanged(AnalysisState *state, ChangeResult changed);
 
   /// Register a custom program point class.
   template <typename PointT>
   void registerPointKind() {
     solver.uniquer.registerParametricStorageType<PointT>();
   }
 
   /// Get or create a custom program point.
   template <typename PointT, typename... Args>
   PointT *getProgramPoint(Args &&...args) {
     return solver.getProgramPoint<PointT>(std::forward<Args>(args)...);
   }
 
-  /// Get the analysis state assiocated with the program point. The returned
+  /// Get the analysis state associated with the program point. The returned
   /// state is expected to be "write-only", and any updates need to be
   /// propagated by `propagateIfChanged`.
   template <typename StateT, typename PointT>
   StateT *getOrCreate(PointT point) {
     return solver.getOrCreateState<StateT>(point);
   }
 
   /// Get a read-only analysis state for the given point and create a dependency

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

 
 const AbstractDenseLattice *
 AbstractDenseDataFlowAnalysis::getLatticeFor(ProgramPoint dependent,
                                              ProgramPoint point) {
   AbstractDenseLattice *state = getLattice(point);
   addDependency(state, dependent);
   return state;
 }
+
+//===----------------------------------------------------------------------===//
+// AbstractDenseBackwardDataFlowAnalysis
+//===----------------------------------------------------------------------===//
+
+LogicalResult
+AbstractDenseBackwardDataFlowAnalysis::initialize(Operation *top) {
+  // Visit every operation and block.
+  processOperation(top);
+  for (Region &region : top->getRegions()) {
+    for (Block &block : region) {
+      visitBlock(&block);
+      for (Operation &op : llvm::reverse(block)) {
+        if (failed(initialize(&op)))
+          return failure();
+      }
+    }
+  }
+  return success();
+}
+
+LogicalResult AbstractDenseBackwardDataFlowAnalysis::visit(ProgramPoint point) {
+  if (auto *op = llvm::dyn_cast_if_present<Operation *>(point))
+    processOperation(op);
+  else if (auto *block = llvm::dyn_cast_if_present<Block *>(point))
+    visitBlock(block);
+  else
+    return failure();
+  return success();
+}
+
+void AbstractDenseBackwardDataFlowAnalysis::processOperation(Operation *op) {
+  // If the containing block is not executable, bail out.
+  if (!getOrCreateFor<Executable>(op, op->getBlock())->isLive())
+    return;
+
+  // Get the dense lattice to update.
+  AbstractDenseLattice *before = getLattice(op);
+
+  // If the op implements region control flow, then the interface specifies the
+  // control function.
+  // TODO: this is not always true, e.g. linalg.generic, but is implement this
+  // way for consistency with the dense forward analysis.
+  if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
+    return visitRegionBranchOperation(op, branch, std::nullopt, before);
+
+  // If the op is a call-like, do inter-procedural data flow as follows:
+  //
+  //   - find the callable (resolve via the symbol table),
+  //   - get the entry block of the callable region,
+  //   - take the state before the first operation if present or at block end
+  //   otherwise,
+  //   - meet that state with the state before the call-like op.
+  if (auto call = dyn_cast<CallOpInterface>(op)) {
+    Operation *callee = call.resolveCallable(&symbolTable);
+    if (auto callable = dyn_cast<CallableOpInterface>(callee)) {
+      Region *region = callable.getCallableRegion();
+      if (region && !region->empty()) {
+        Block *entryBlock = &region->front();
+        if (entryBlock->empty())
+          meet(before, *getLatticeFor(op, entryBlock));
+        else
+          meet(before, *getLatticeFor(op, &entryBlock->front()));
+      } else {
+        setToExitState(before);
+      }
+    } else {
+      setToExitState(before);
+    }
+    return;
+  }
+
+  // Get the dense state after execution of this op.
+  const AbstractDenseLattice *after;
+  if (Operation *next = op->getNextNode())
+    after = getLatticeFor(op, next);
+  else
+    after = getLatticeFor(op, op->getBlock());
+
+  // Invoke the operation transfer function.
+  visitOperationImpl(op, *after, before);
+}
+
+void AbstractDenseBackwardDataFlowAnalysis::visitBlock(Block *block) {
+  // If the block is not executable, bail out.
+  if (!getOrCreateFor<Executable>(block, block)->isLive())
+    return;
+
+  AbstractDenseLattice *before = getLattice(block);
+
+  // We need "exit" blocks, i.e. the blocks that may return control to the
+  // parent operation.
+  auto isExitBlock = [](Block *b) {
+    // Treat empty and terminator-less blocks as exit blocks.
+    if (b->empty() || !b->back().mightHaveTrait<OpTrait::IsTerminator>())
+      return true;
+
+    // There may be a weird case where a terminator may be transferring control
+    // either to the parent or to another block, so exit blocks and successors
+    // are not mutually exclusive.
+    Operation *terminator = b->getTerminator();
+    return terminator && (terminator->hasTrait<OpTrait::ReturnLike>() ||
+                          isa<RegionBranchTerminatorOpInterface>(terminator));
+  };
+  if (isExitBlock(block)) {
+    // If this block is exiting from a callable, the successors of exiting from
+    // a callable are the successors of all call sites. And the call sites
+    // themselves are predecessors of the callable.
+    auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
+    if (callable && callable.getCallableRegion() == block->getParent()) {
+      const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);
+      // If not all call sites are known, conservative mark all lattices as
+      // having reached their pessimistic fix points.
+      if (!callsites->allPredecessorsKnown())
+        return setToExitState(before);
+
+      for (Operation *callsite : callsites->getKnownPredecessors()) {
+        if (Operation *next = callsite->getNextNode())
+          meet(before, *getLatticeFor(block, next));
+        else
+          meet(before, *getLatticeFor(block, callsite->getBlock()));
+      }
+      return;
+    }
+
+    // If this block is exiting from an operation with region-based control
+    // flow, follow that flow.
+    if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp())) {
+      visitRegionBranchOperation(block, branch,
+                                 block->getParent()->getRegionNumber(), before);
+      return;
+    }
+
+    // Cannot reason about successors of an exit block, set the pessimistic
+    // fixpoint.
+    return setToExitState(before);
+  }
+
+  // Meet the state with the state before block's successors.
+  for (Block *successor : block->getSuccessors()) {
+    if (!getOrCreateFor<Executable>(block,
+                                    getProgramPoint<CFGEdge>(block, successor))
+             ->isLive())
+      continue;
+
+    // Merge in the state from the successor: either the first operation, or the
+    // block itself when empty.
+    if (successor->empty())
+      meet(before, *getLatticeFor(block, successor));
+    else
+      meet(before, *getLatticeFor(block, &successor->front()));
+  }
+}
+
+void AbstractDenseBackwardDataFlowAnalysis::visitRegionBranchOperation(
+    ProgramPoint point, RegionBranchOpInterface branch,
+    std::optional<unsigned> regionNo, AbstractDenseLattice *before) {
+
+  // The successors of the operation may be either the first operation of the
+  // entry block of each possible successor region, or the next operation when
+  // the branch is a successor of itself.
+  SmallVector<RegionSuccessor> successors;
+  branch.getSuccessorRegions(regionNo, successors);
+  for (const RegionSuccessor &successor : successors) {
+    const AbstractDenseLattice *after;
+    if (successor.isParent() || successor.getSuccessor()->empty()) {
+      if (Operation *next = branch->getNextNode())
+        after = getLatticeFor(point, next);
+      else
+        after = getLatticeFor(point, branch->getBlock());
+    } else {
+      Region *successorRegion = successor.getSuccessor();
+      assert(!successorRegion->empty() && "unexpected empty successor region");
+      Block *successorBlock = &successorRegion->front();
+
+      if (!getOrCreateFor<Executable>(point, successorBlock)->isLive())
+        continue;
+
+      if (successorBlock->empty())
+        after = getLatticeFor(point, successorBlock);
+      else
+        after = getLatticeFor(point, &successorBlock->front());
+    }
+    meet(before, *after);
+  }
+}
+
+const AbstractDenseLattice *
+AbstractDenseBackwardDataFlowAnalysis::getLatticeFor(ProgramPoint dependent,
+                                                     ProgramPoint point) {
+  AbstractDenseLattice *state = getLattice(point);
+  addDependency(state, dependent);
+  return state;
+}

mlir/lib/Analysis/DataFlowFramework.cpp

DATAFLOW_DEBUG({
     if (inserted) {
       llvm::dbgs() << "Creating dependency between " << debugName << " of "
                    << point << "\nand " << debugName << " on " << dependent
                    << "\n";
     }
   });
 }
 
+void AnalysisState::dump() const { print(llvm::errs()); }
+
 //===----------------------------------------------------------------------===//
 // ProgramPoint
 //===----------------------------------------------------------------------===//
 
 void ProgramPoint::print(raw_ostream &os) const {
   if (isNull()) {
     os << "<NULL POINT>";
     return;
   }
   if (auto *programPoint = llvm::dyn_cast<GenericProgramPoint *>(*this))
     return programPoint->print(os);
   if (auto *op = llvm::dyn_cast<Operation *>(*this))
-    return op->print(os);
+    return op->print(os, OpPrintingFlags().skipRegions());
   if (auto value = llvm::dyn_cast<Value>(*this))
-    return value.print(os);
+    return value.print(os, OpPrintingFlags().skipRegions());
   return get<Block *>()->print(os);
 }
 
 Location ProgramPoint::getLoc() const {
   if (auto *programPoint = llvm::dyn_cast<GenericProgramPoint *>(*this))
     return programPoint->getLoc();
   if (auto *op = llvm::dyn_cast<Operation *>(*this))
     return op->getLoc();

mlir/test/Analysis/DataFlow/test-next-access.mlir

+// RUN: mlir-opt %s --test-next-access --split-input-file | FileCheck %s
+
+// CHECK-LABEL: @trivial
+func.func @trivial(%arg0: memref<f32>, %arg1: f32) -> f32 {
+  // CHECK:      name = "store"
+  // CHECK-SAME: next_access = ["unknown", ["load"]]
+  memref.store %arg1, %arg0[] {name = "store"} : memref<f32>
+  // CHECK:      name = "load"
+  // CHECK-SAME: next_access = ["unknown"]
+  %0 = memref.load %arg0[] {name = "load"} : memref<f32>
+  return %0 : f32
+}
+
+// CHECK-LABEL: @chain
+func.func @chain(%arg0: memref<f32>, %arg1: f32) -> f32 {
+  // CHECK:      name = "store"
+  // CHECK-SAME: next_access = ["unknown", ["load 1"]]
+  memref.store %arg1, %arg0[] {name = "store"} : memref<f32>
+  // CHECK:      name = "load 1"
+  // CHECK-SAME: next_access = {{\[}}["load 2"]]
+  %0 = memref.load %arg0[] {name = "load 1"} : memref<f32>
+  // CHECK:      name = "load 2"
+  // CHECK-SAME: next_access = ["unknown"]
+  %1 = memref.load %arg0[] {name = "load 2"} : memref<f32>
+  %2 = arith.addf %0, %1 : f32
+  return %2 : f32
+}
+
+// CHECK-LABEL: @branch
+func.func @branch(%arg0: memref<f32>, %arg1: f32, %arg2: i1) -> f32 {
+  // CHECK:      name = "store"
+  // CHECK-SAME: next_access = ["unknown", ["load 1", "load 2"]]
+  memref.store %arg1, %arg0[] {name = "store"} : memref<f32>
+  cf.cond_br %arg2, ^bb0, ^bb1
+
+^bb0:
+  %0 = memref.load %arg0[] {name = "load 1"} : memref<f32>
+  cf.br ^bb2(%0 : f32)
+
+^bb1:
+  %1 = memref.load %arg0[] {name = "load 2"} : memref<f32>
+  cf.br ^bb2(%1 : f32)
+
+^bb2(%phi: f32):
+  return %phi : f32
+}
+
+// CHECK-LABEL @dead_branch
+func.func @dead_branch(%arg0: memref<f32>, %arg1: f32) -> f32 {
+  // CHECK:      name = "store"
+  // CHECK-SAME: next_access = ["unknown", ["load 2"]]
+  memref.store %arg1, %arg0[] {name = "store"} : memref<f32>
+  cf.br ^bb1
+
+^bb0:
+  // CHECK:      name = "load 1"
+  // CHECK-SAME: next_access = "not computed"
+  %0 = memref.load %arg0[] {name = "load 1"} : memref<f32>
+  cf.br ^bb2(%0 : f32)
+
+^bb1:
+  %1 = memref.load %arg0[] {name = "load 2"} : memref<f32>
+  cf.br ^bb2(%1 : f32)
+
+^bb2(%phi: f32):
+  return %phi : f32
+}
+
+// CHECK-LABEL: @loop
+func.func @loop(%arg0: memref<?xf32>, %arg1: f32, %arg2: index, %arg3: index, %arg4: index) -> f32 {
+  %c0 = arith.constant 0.0 : f32
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["loop"], "unknown"]
+  // The above is not entirely correct when the loop has 0 iterations, but 
+  // the region control flow specificaiton is currently incapable of
+  // specifying that.
+  memref.load %arg0[%arg4] {name = "pre"} : memref<?xf32>
+  %l = scf.for %i = %arg2 to %arg3 step %arg4 iter_args(%ia = %c0) -> (f32) {
+    // CHECK:      name = "loop"
+    // CHECK-SAME: next_access = {{\[}}["outside", "loop"], "unknown"]
+    %0 = memref.load %arg0[%i] {name = "loop"} : memref<?xf32>
+    %1 = arith.addf %ia, %0 : f32
+    scf.yield %1 : f32
+  }
+  %v = memref.load %arg0[%arg3] {name = "outside"} : memref<?xf32>
+  %2 = arith.addf %v, %l : f32
+  return %2 : f32
+}
+
+// CHECK-LABEL: @conditional
+func.func @conditional(%cond: i1, %arg0: memref<f32>) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["then"]]
+  // The above is not entirely correct when the condition is false, but 
+  // the region control flow specificaiton is currently incapable of
+  // specifying that.
+  memref.load %arg0[] {name = "pre"}: memref<f32>
+  scf.if %cond {
+    // CHECK:      name = "then"
+    // CHECK-SAME: next_access = {{\[}}["post"]]
+    memref.load %arg0[] {name = "then"} : memref<f32>
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @two_sided_conditional
+func.func @two_sided_conditional(%cond: i1, %arg0: memref<f32>) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["then", "else"]]
+  memref.load %arg0[] {name = "pre"}: memref<f32>
+  scf.if %cond {
+    // CHECK:      name = "then"
+    // CHECK-SAME: next_access = {{\[}}["post"]]
+    memref.load %arg0[] {name = "then"} : memref<f32>
+  } else {
+    // CHECK:      name = "else"
+    // CHECK-SAME: next_access = {{\[}}["post"]]
+    memref.load %arg0[] {name = "else"} : memref<f32>
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @dead_conditional
+func.func @dead_conditional(%arg0: memref<f32>) {
+  %false = arith.constant 0 : i1
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = ["unknown"]
+  // The above is not entirely correct when the condition is false, but 
+  // the region control flow specificaiton is currently incapable of
+  // specifying that.
+  memref.load %arg0[] {name = "pre"}: memref<f32>
+  scf.if %false {
+    // CHECK:      name = "then"
+    // CHECK-SAME: next_access = "not computed"
+    memref.load %arg0[] {name = "then"} : memref<f32>
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @known_conditional
+func.func @known_conditional(%arg0: memref<f32>) {
+  %false = arith.constant 0 : i1
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["else"]]
+  memref.load %arg0[] {name = "pre"}: memref<f32>
+  scf.if %false {
+    // CHECK:      name = "then"
+    // CHECK-SAME: next_access = "not computed"
+    memref.load %arg0[] {name = "then"} : memref<f32>
+  } else {
+    // CHECK:      name = "else"
+    // CHECK-SAME: next_access = {{\[}}["post"]]
+    memref.load %arg0[] {name = "else"} : memref<f32>
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @loop_cf
+func.func @loop_cf(%arg0: memref<?xf32>, %arg1: f32, %arg2: index, %arg3: index, %arg4: index) -> f32 {
+  %cst = arith.constant 0.000000e+00 : f32
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["loop", "outside"], "unknown"]
+  %0 = memref.load %arg0[%arg4] {name = "pre"} : memref<?xf32>
+  cf.br ^bb1(%arg2, %cst : index, f32)
+^bb1(%1: index, %2: f32):
+  %3 = arith.cmpi slt, %1, %arg3 : index
+  cf.cond_br %3, ^bb2, ^bb3
+^bb2:
+  // CHECK:      name = "loop"
+  // CHECK-SAME: next_access = {{\[}}["loop", "outside"], "unknown"]
+  %4 = memref.load %arg0[%1] {name = "loop"} : memref<?xf32>
+  %5 = arith.addf %2, %4 : f32
+  %6 = arith.addi %1, %arg4 : index
+  cf.br ^bb1(%6, %5 : index, f32)
+^bb3:
+  %7 = memref.load %arg0[%arg3] {name = "outside"} : memref<?xf32>
+  %8 = arith.addf %7, %2 : f32
+  return %8 : f32
+}
+
+// CHECK-LABEL @conditional_cf
+func.func @conditional_cf(%arg0: i1, %arg1: memref<f32>) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["then", "post"]]
+  %0 = memref.load %arg1[] {name = "pre"} : memref<f32>
+  cf.cond_br %arg0, ^bb1, ^bb2
+^bb1:
+  // CHECK:      name = "then"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  %1 = memref.load %arg1[] {name = "then"} : memref<f32>
+  cf.br ^bb2
+^bb2:
+  %2 = memref.load %arg1[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @two_sided_conditional_cf
+func.func @two_sided_conditional_cf(%arg0: i1, %arg1: memref<f32>) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["then", "else"]]
+  %0 = memref.load %arg1[] {name = "pre"} : memref<f32>
+  cf.cond_br %arg0, ^bb1, ^bb2
+^bb1:
+  // CHECK:      name = "then"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  %1 = memref.load %arg1[] {name = "then"} : memref<f32>
+  cf.br ^bb3
+^bb2:
+  // CHECK:      name = "else"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  %2 = memref.load %arg1[] {name = "else"} : memref<f32>
+  cf.br ^bb3
+^bb3:
+  %3 = memref.load %arg1[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @dead_conditional_cf
+func.func @dead_conditional_cf(%arg0: memref<f32>) {
+  %false = arith.constant false
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  %0 = memref.load %arg0[] {name = "pre"} : memref<f32>
+  cf.cond_br %false, ^bb1, ^bb2
+^bb1:
+  // CHECK:      name = "then"
+  // CHECK-SAME: next_access = "not computed"
+  %1 = memref.load %arg0[] {name = "then"} : memref<f32>
+  cf.br ^bb2
+^bb2:
+  %2 = memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @known_conditional_cf
+func.func @known_conditional_cf(%arg0: memref<f32>) {
+  %false = arith.constant false
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["else"]]
+  %0 = memref.load %arg0[] {name = "pre"} : memref<f32>
+  cf.cond_br %false, ^bb1, ^bb2
+^bb1:
+  // CHECK:      name = "then"
+  // CHECK-SAME: next_access = "not computed"
+  %1 = memref.load %arg0[] {name = "then"} : memref<f32>
+  cf.br ^bb3
+^bb2:
+  // CHECK:      name = "else"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  %2 = memref.load %arg0[] {name = "else"} : memref<f32>
+  cf.br ^bb3
+^bb3:
+  %3 = memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// -----
+
+func.func private @callee1(%arg0: memref<f32>) {
+  // CHECK:      name = "callee1"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  memref.load %arg0[] {name = "callee1"} : memref<f32>
+  return
+}
+
+func.func private @callee2(%arg0: memref<f32>) {
+  // CHECK:      name = "callee2"
+  // CHECK-SAME: next_access = "not computed"
+  memref.load %arg0[] {name = "callee2"} : memref<f32>
+  return
+}
+
+// CHECK-LABEL: @simple_call
+func.func @simple_call(%arg0: memref<f32>) {
+  // CHECK:      name = "caller"
+  // CHECK-SAME: next_access = {{\[}}["callee1"]]
+  memref.load %arg0[] {name = "caller"} : memref<f32>
+  func.call @callee1(%arg0) : (memref<f32>) -> ()
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// -----
+
+// CHECK-LABEL: @infinite_recursive_call
+func.func @infinite_recursive_call(%arg0: memref<f32>) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["pre"]]
+  memref.load %arg0[] {name = "pre"} : memref<f32>
+  func.call @infinite_recursive_call(%arg0) : (memref<f32>) -> ()
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// -----
+
+// CHECK-LABEL: @recursive_call
+func.func @recursive_call(%arg0: memref<f32>, %cond: i1) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["pre"]]
+  // The above is not entirely correct when the condition is false, but 
+  // the region control flow specificaiton is currently incapable of
+  // specifying that.
+  memref.load %arg0[] {name = "pre"} : memref<f32>
+  scf.if %cond {
+    func.call @recursive_call(%arg0, %cond) : (memref<f32>, i1) -> ()
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// -----
+
+// CHECK-LABEL: @recursive_call_cf
+func.func @recursive_call_cf(%arg0: memref<f32>, %cond: i1) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["pre", "post"]]
+  %0 = memref.load %arg0[] {name = "pre"} : memref<f32>
+  cf.cond_br %cond, ^bb1, ^bb2
+^bb1:
+  call @recursive_call_cf(%arg0, %cond) : (memref<f32>, i1) -> ()
+  cf.br ^bb2
+^bb2:
+  %2 = memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}
+
+// -----
+
+func.func private @callee1(%arg0: memref<f32>) {
+  // CHECK:      name = "callee1"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  memref.load %arg0[] {name = "callee1"} : memref<f32>
+  return
+}
+
+func.func private @callee2(%arg0: memref<f32>) {
+  // CHECK:      name = "callee2"
+  // CHECK-SAME: next_access = {{\[}}["post"]]
+  memref.load %arg0[] {name = "callee2"} : memref<f32>
+  return
+}
+
+func.func @conditonal_call(%arg0: memref<f32>, %cond: i1) {
+  // CHECK:      name = "pre"
+  // CHECK-SAME: next_access = {{\[}}["callee1", "callee2"]]
+  memref.load %arg0[] {name = "pre"} : memref<f32>
+  scf.if %cond {
+    func.call @callee1(%arg0) : (memref<f32>) -> ()
+  } else {
+    func.call @callee2(%arg0) : (memref<f32>) -> ()
+  }
+  memref.load %arg0[] {name = "post"} : memref<f32>
+  return
+}

mlir/test/lib/Analysis/CMakeLists.txt

 # Exclude tests from libMLIR.so
 add_mlir_library(MLIRTestAnalysis
   TestAliasAnalysis.cpp
   TestCallGraph.cpp
   TestDataFlowFramework.cpp
   TestLiveness.cpp
   TestCFGLoopInfo.cpp
   TestMatchReduction.cpp
   TestMemRefBoundCheck.cpp
   TestMemRefDependenceCheck.cpp
   TestMemRefStrideCalculation.cpp
   TestSlice.cpp
 
   DataFlow/TestDeadCodeAnalysis.cpp
   DataFlow/TestDenseDataFlowAnalysis.cpp
   DataFlow/TestBackwardDataFlowAnalysis.cpp
+  DataFlow/TestDenseBackwardDataFlowAnalysis.cpp
 
   EXCLUDE_FROM_LIBMLIR
 
   LINK_LIBS PUBLIC
   MLIRAffineDialect
   MLIRAnalysis
   MLIRMemRefDialect
   MLIRPass
   MLIRTestDialect
   )
 
 target_include_directories(MLIRTestAnalysis
   PRIVATE
   ${CMAKE_CURRENT_SOURCE_DIR}/../Dialect/Test
   ${CMAKE_CURRENT_BINARY_DIR}/../Dialect/Test
   )

mlir/test/lib/Analysis/DataFlow/TestDenseBackwardDataFlowAnalysis.cpp

+//===- TestDenseBackwardDataFlowAnalysis.cpp - Test pass ------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Test pass for backward dense dataflow analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TestDenseDataFlowAnalysis.h"
+#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
+#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
+#include "mlir/Analysis/DataFlow/DenseAnalysis.h"
+#include "mlir/Analysis/DataFlowFramework.h"
+#include "mlir/IR/SymbolTable.h"
+#include "mlir/Interfaces/SideEffectInterfaces.h"
+#include "mlir/Pass/Pass.h"
+#include "mlir/Support/TypeID.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace mlir;
+using namespace mlir::dataflow;
+using namespace mlir::dataflow::test;
+
+namespace {
+
+class NextAccess : public AbstractDenseLattice, public test::AccessLatticeBase {
+public:
+  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(NextAccess)
+
+  using dataflow::AbstractDenseLattice::AbstractDenseLattice;
+
+  ChangeResult meet(const AbstractDenseLattice &lattice) override {
+    return AccessLatticeBase::merge(static_cast<test::AccessLatticeBase>(
+        static_cast<const NextAccess &>(lattice)));
+  }
+
+  void print(raw_ostream &os) const override {
+    return AccessLatticeBase::print(os);
+  }
+};
+
+class NextAccessAnalysis : public DenseBackwardDataFlowAnalysis<NextAccess> {
+public:
+  using DenseBackwardDataFlowAnalysis::DenseBackwardDataFlowAnalysis;
+
+  void visitOperation(Operation *op, const NextAccess &after,
+                      NextAccess *before) override;
+
+  // TODO: this isn't ideal for the analysis. When there is no next access, it
+  // means "we don't know what the next access is" rather than "there is no next
+  // access". But it's unclear how to differentiate the two cases...
+  void setToExitState(NextAccess *lattice) override {
+    propagateIfChanged(lattice, lattice->reset());
+  }
+};
+} // namespace
+
+void NextAccessAnalysis::visitOperation(Operation *op, const NextAccess &after,
+                                        NextAccess *before) {
+  auto memory = dyn_cast<MemoryEffectOpInterface>(op);
+  // If we can't reason about the memory effects, conservatively assume we can't
+  // say anything about the next access.
+  if (!memory)
+    return setToExitState(before);
+
+  SmallVector<MemoryEffects::EffectInstance> effects;
+  memory.getEffects(effects);
+  ChangeResult result = before->meet(after);
+  for (const MemoryEffects::EffectInstance &effect : effects) {
+    Value value = effect.getValue();
+
+    // Effects with unspecified value are treated conservatively and we cannot
+    // assume anything about the next access.
+    if (!value)
+      return setToExitState(before);
+
+    value = UnderlyingValueAnalysis::getMostUnderlyingValue(
+        value, [&](Value value) {
+          return getOrCreateFor<UnderlyingValueLattice>(op, value);
+        });
+    if (!value)
+      return;
+
+    result |= before->set(value, op);
+  }
+  propagateIfChanged(before, result);
+}
+
+namespace {
+struct TestNextAccessPass
+    : public PassWrapper<TestNextAccessPass, OperationPass<>> {
+  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestNextAccessPass)
+
+  StringRef getArgument() const override { return "test-next-access"; }
+
+  static constexpr llvm::StringLiteral kTagAttrName = "name";
+  static constexpr llvm::StringLiteral kNextAccessAttrName = "next_access";
+
+  void runOnOperation() override {
+    Operation *op = getOperation();
+    SymbolTableCollection symbolTable;
+
+    DataFlowSolver solver;
+    solver.load<DeadCodeAnalysis>();
+    solver.load<NextAccessAnalysis>(symbolTable);
+    solver.load<SparseConstantPropagation>();
+    solver.load<UnderlyingValueAnalysis>();
+    if (failed(solver.initializeAndRun(op))) {
+      emitError(op->getLoc(), "dataflow solver failed");
+      return signalPassFailure();
+    }
+
+    op->walk([&](Operation *op) {
+      auto tag = op->getAttrOfType<StringAttr>(kTagAttrName);
+      if (!tag)
+        return;
+
+      const NextAccess *nextAccess = solver.lookupState<NextAccess>(
+          op->getNextNode() == nullptr ? ProgramPoint(op->getBlock())
+                                       : op->getNextNode());
+      if (!nextAccess) {
+        op->setAttr(kNextAccessAttrName,
+                    StringAttr::get(op->getContext(), "not computed"));
+        return;
+      }
+
+      SmallVector<Attribute> attrs;
+      for (Value operand : op->getOperands()) {
+        Value value = UnderlyingValueAnalysis::getMostUnderlyingValue(
+            operand, [&](Value value) {
+              return solver.lookupState<UnderlyingValueLattice>(value);
+            });
+        std::optional<ArrayRef<Operation *>> nextAcc =
+            nextAccess->getAdjacentAccess(value);
+        if (!nextAcc) {
+          attrs.push_back(StringAttr::get(op->getContext(), "unknown"));
+          continue;
+        }
+
+        SmallVector<Attribute> innerAttrs;
+        innerAttrs.reserve(nextAcc->size());
+        for (Operation *nextAccOp : *nextAcc) {
+          if (auto nextAccTag =
+                  nextAccOp->getAttrOfType<StringAttr>(kTagAttrName)) {
+            innerAttrs.push_back(nextAccTag);
+            continue;
+          }
+          std::string repr;
+          llvm::raw_string_ostream os(repr);
+          nextAccOp->print(os);
+          innerAttrs.push_back(StringAttr::get(op->getContext(), os.str()));
+        }
+        attrs.push_back(ArrayAttr::get(op->getContext(), innerAttrs));
+      }
+
+      op->setAttr(kNextAccessAttrName, ArrayAttr::get(op->getContext(), attrs));
+    });
+  }
+};
+} // namespace
+
+namespace mlir::test {
+void registerTestNextAccessPass() { PassRegistration<TestNextAccessPass>(); }
+} // namespace mlir::test

mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.h

+//===- TestDenseDataFlowAnalysis.h - Dataflow test utilities ----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Analysis/DataFlow/SparseAnalysis.h"
+#include "mlir/Analysis/DataFlowFramework.h"
+#include "mlir/IR/Value.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/raw_ostream.h"
+#include <optional>
+
+namespace mlir {
+namespace dataflow {
+namespace test {
+
+/// This lattice represents a single underlying value for an SSA value.
+class UnderlyingValue {
+public:
+  /// Create an underlying value state with a known underlying value.
+  explicit UnderlyingValue(std::optional<Value> underlyingValue = std::nullopt)
+      : underlyingValue(underlyingValue) {}
+
+  /// Whether the state is uninitialized.
+  bool isUninitialized() const { return !underlyingValue.has_value(); }
+
+  /// Returns the underlying value.
+  Value getUnderlyingValue() const {
+    assert(!isUninitialized());
+    return *underlyingValue;
+  }
+
+  /// Join two underlying values. If there are conflicting underlying values,
+  /// go to the pessimistic value.
+  static UnderlyingValue join(const UnderlyingValue &lhs,
+                              const UnderlyingValue &rhs) {
+    if (lhs.isUninitialized())
+      return rhs;
+    if (rhs.isUninitialized())
+      return lhs;
+    return lhs.underlyingValue == rhs.underlyingValue
+               ? lhs
+               : UnderlyingValue(Value{});
+  }
+
+  /// Compare underlying values.
+  bool operator==(const UnderlyingValue &rhs) const {
+    return underlyingValue == rhs.underlyingValue;
+  }
+
+  void print(raw_ostream &os) const { os << underlyingValue; }
+
+private:
+  std::optional<Value> underlyingValue;
+};
+
+/// This lattice represents, for a given memory resource, the potential last
+/// operations that modified the resource.
+class AccessLatticeBase {
+public:
+  /// Clear all modifications.
+  ChangeResult reset() {
+    if (adjAccesses.empty())
+      return ChangeResult::NoChange;
+    adjAccesses.clear();
+    return ChangeResult::Change;
+  }
+
+  /// Join the last modifications.
+  ChangeResult merge(const AccessLatticeBase &rhs) {
+    ChangeResult result = ChangeResult::NoChange;
+    for (const auto &mod : rhs.adjAccesses) {
+      auto &lhsMod = adjAccesses[mod.first];
+      if (lhsMod != mod.second) {
+        lhsMod.insert(mod.second.begin(), mod.second.end());
+        result |= ChangeResult::Change;
+      }
+    }
+    return result;
+  }
+
+  /// Set the last modification of a value.
+  ChangeResult set(Value value, Operation *op) {
+    auto &lastMod = adjAccesses[value];
+    ChangeResult result = ChangeResult::NoChange;
+    if (lastMod.size() != 1 || *lastMod.begin() != op) {
+      result = ChangeResult::Change;
+      lastMod.clear();
+      lastMod.insert(op);
+    }
+    return result;
+  }
+
+  /// Get the adjacent accesses to a value. Returns std::nullopt if they
+  /// are not known.
+  std::optional<ArrayRef<Operation *>> getAdjacentAccess(Value value) const {
+    auto it = adjAccesses.find(value);
+    if (it == adjAccesses.end())
+      return {};
+    return it->second.getArrayRef();
+  }
+
+  void print(raw_ostream &os) const {
+    for (const auto &lastMod : adjAccesses) {
+      os << lastMod.first << ":\n";
+      for (Operation *op : lastMod.second)
+        os << "  " << *op << "\n";
+    }
+  }
+
+private:
+  /// The potential adjacent accesses to a memory resource. Use a set vector to
+  /// keep the results deterministic.
+  DenseMap<Value, SetVector<Operation *, SmallVector<Operation *, 2>,
+                            SmallPtrSet<Operation *, 2>>>
+      adjAccesses;
+};
+
+/// Define the lattice class explicitly to provide a type ID.
+struct UnderlyingValueLattice : public Lattice<UnderlyingValue> {
+  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(UnderlyingValueLattice)
+  using Lattice::Lattice;
+};
+
+/// An analysis that uses forwarding of values along control-flow and callgraph
+/// edges to determine single underlying values for block arguments. This
+/// analysis exists so that the test analysis and pass can test the behaviour of
+/// the dense data-flow analysis on the callgraph.
+class UnderlyingValueAnalysis
+    : public SparseDataFlowAnalysis<UnderlyingValueLattice> {
+public:
+  using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
+
+  /// The underlying value of the results of an operation are not known.
+  void visitOperation(Operation *op,
+                      ArrayRef<const UnderlyingValueLattice *> operands,
+                      ArrayRef<UnderlyingValueLattice *> results) override {
+    setAllToEntryStates(results);
+  }
+
+  /// At an entry point, the underlying value of a value is itself.
+  void setToEntryState(UnderlyingValueLattice *lattice) override {
+    propagateIfChanged(lattice,
+                       lattice->join(UnderlyingValue{lattice->getPoint()}));
+  }
+
+  /// Look for the most underlying value of a value.
+  static Value
+  getMostUnderlyingValue(Value value,
+                         function_ref<const UnderlyingValueLattice *(Value)>
+                             getUnderlyingValueFn) {
+    const UnderlyingValueLattice *underlying;
+    do {
+      underlying = getUnderlyingValueFn(value);
+      if (!underlying || underlying->getValue().isUninitialized())
+        return {};
+      Value underlyingValue = underlying->getValue().getUnderlyingValue();
+      if (underlyingValue == value)
+        break;
+      value = underlyingValue;
+    } while (true);
+    return value;
+  }
+};
+
+} // namespace test
+} // namespace dataflow
+} // namespace mlir

mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp

-//===- TestDeadCodeAnalysis.cpp - Test dead code analysis -----------------===//
+//===- TestDenseDataFlowAnalysis.cpp - Test dense data flow analysis ------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+#include "TestDenseDataFlowAnalysis.h"
 #include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
 #include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
 #include "mlir/Analysis/DataFlow/DenseAnalysis.h"
-#include "mlir/Analysis/DataFlow/SparseAnalysis.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Pass/Pass.h"
 #include <optional>
 
 using namespace mlir;
 using namespace mlir::dataflow;
+using namespace mlir::dataflow::test;
 
 namespace {
-/// This lattice represents a single underlying value for an SSA value.
-class UnderlyingValue {
-public:
-  /// Create an underlying value state with a known underlying value.
-  explicit UnderlyingValue(std::optional<Value> underlyingValue = std::nullopt)
-      : underlyingValue(underlyingValue) {}
-
-  /// Whether the state is uninitialized.
-  bool isUninitialized() const { return !underlyingValue.has_value(); }
-
-  /// Returns the underlying value.
-  Value getUnderlyingValue() const {
-    assert(!isUninitialized());
-    return *underlyingValue;
-  }
-
-  /// Join two underlying values. If there are conflicting underlying values,
-  /// go to the pessimistic value.
-  static UnderlyingValue join(const UnderlyingValue &lhs,
-                              const UnderlyingValue &rhs) {
-    if (lhs.isUninitialized())
-      return rhs;
-    if (rhs.isUninitialized())
-      return lhs;
-    return lhs.underlyingValue == rhs.underlyingValue
-               ? lhs
-               : UnderlyingValue(Value{});
-  }
-
-  /// Compare underlying values.
-  bool operator==(const UnderlyingValue &rhs) const {
-    return underlyingValue == rhs.underlyingValue;
-  }
-
-  void print(raw_ostream &os) const { os << underlyingValue; }
-
-private:
-  std::optional<Value> underlyingValue;
-};
 
 /// This lattice represents, for a given memory resource, the potential last
 /// operations that modified the resource.
-class LastModification : public AbstractDenseLattice {
+class LastModification : public AbstractDenseLattice,
+                         public test::AccessLatticeBase {
 public:
   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(LastModification)
 
   using AbstractDenseLattice::AbstractDenseLattice;
 
-  /// Clear all modifications.
-  ChangeResult reset() {
-    if (lastMods.empty())
-      return ChangeResult::NoChange;
-    lastMods.clear();
-    return ChangeResult::Change;
-  }
-
   /// Join the last modifications.
   ChangeResult join(const AbstractDenseLattice &lattice) override {
-    const auto &rhs = static_cast<const LastModification &>(lattice);
-    ChangeResult result = ChangeResult::NoChange;
-    for (const auto &mod : rhs.lastMods) {
-      auto &lhsMod = lastMods[mod.first];
-      if (lhsMod != mod.second) {
-        lhsMod.insert(mod.second.begin(), mod.second.end());
-        result |= ChangeResult::Change;
-      }
-    }
-    return result;
-  }
-
-  /// Set the last modification of a value.
-  ChangeResult set(Value value, Operation *op) {
-    auto &lastMod = lastMods[value];
-    ChangeResult result = ChangeResult::NoChange;
-    if (lastMod.size() != 1 || *lastMod.begin() != op) {
-      result = ChangeResult::Change;
-      lastMod.clear();
-      lastMod.insert(op);
-    }
-    return result;
-  }
-
-  /// Get the last modifications of a value. Returns std::nullopt if the last
-  /// modifications are not known.
-  std::optional<ArrayRef<Operation *>> getLastModifiers(Value value) const {
-    auto it = lastMods.find(value);
-    if (it == lastMods.end())
-      return {};
-    return it->second.getArrayRef();
+    return AccessLatticeBase::merge(static_cast<test::AccessLatticeBase>(
+        static_cast<const LastModification &>(lattice)));
   }
 
   void print(raw_ostream &os) const override {
-    for (const auto &lastMod : lastMods) {
-      os << lastMod.first << ":\n";
-      for (Operation *op : lastMod.second)
-        os << "  " << *op << "\n";
-    }
-  }
-
-private:
-  /// The potential last modifications of a memory resource. Use a set vector to
-  /// keep the results deterministic.
-  DenseMap<Value, SetVector<Operation *, SmallVector<Operation *, 2>,
-                            SmallPtrSet<Operation *, 2>>>
-      lastMods;
+    return AccessLatticeBase::print(os);
 };
 
 class LastModifiedAnalysis : public DenseDataFlowAnalysis<LastModification> {
 public:
   using DenseDataFlowAnalysis::DenseDataFlowAnalysis;
 
   /// Visit an operation. If the operation has no memory effects, then the state
   /// is propagated with no change. If the operation allocates a resource, then
   /// its reaching definitions is set to empty. If the operation writes to a
   /// resource, then its reaching definition is set to the written value.
   void visitOperation(Operation *op, const LastModification &before,
                       LastModification *after) override;
 
   /// At an entry point, the last modifications of all memory resources are
   /// unknown.
   void setToEntryState(LastModification *lattice) override {
     propagateIfChanged(lattice, lattice->reset());
   }
 };
-
-/// Define the lattice class explicitly to provide a type ID.
-struct UnderlyingValueLattice : public Lattice<UnderlyingValue> {
-  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(UnderlyingValueLattice)
-  using Lattice::Lattice;
-};
-
-/// An analysis that uses forwarding of values along control-flow and callgraph
-/// edges to determine single underlying values for block arguments. This
-/// analysis exists so that the test analysis and pass can test the behaviour of
-/// the dense data-flow analysis on the callgraph.
-class UnderlyingValueAnalysis
-    : public SparseDataFlowAnalysis<UnderlyingValueLattice> {
-public:
-  using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
-
-  /// The underlying value of the results of an operation are not known.
-  void visitOperation(Operation *op,
-                      ArrayRef<const UnderlyingValueLattice *> operands,
-                      ArrayRef<UnderlyingValueLattice *> results) override {
-    setAllToEntryStates(results);
-  }
-
-  /// At an entry point, the underlying value of a value is itself.
-  void setToEntryState(UnderlyingValueLattice *lattice) override {
-    propagateIfChanged(lattice,
-                       lattice->join(UnderlyingValue{lattice->getPoint()}));
-  }
-};
 } // end anonymous namespace
 
-/// Look for the most underlying value of a value.
-static Value getMostUnderlyingValue(
-    Value value,
-    function_ref<const UnderlyingValueLattice *(Value)> getUnderlyingValueFn) {
-  const UnderlyingValueLattice *underlying;
-  do {
-    underlying = getUnderlyingValueFn(value);
-    if (!underlying || underlying->getValue().isUninitialized())
-      return {};
-    Value underlyingValue = underlying->getValue().getUnderlyingValue();
-    if (underlyingValue == value)
-      break;
-    value = underlyingValue;
-  } while (true);
-  return value;
-}
-
 void LastModifiedAnalysis::visitOperation(Operation *op,
                                           const LastModification &before,
                                           LastModification *after) {
   auto memory = dyn_cast<MemoryEffectOpInterface>(op);
   // If we can't reason about the memory effects, then conservatively assume we
   // can't deduce anything about the last modifications.
   if (!memory)
     return setToEntryState(after);
 
   SmallVector<MemoryEffects::EffectInstance> effects;
   memory.getEffects(effects);
 
   ChangeResult result = after->join(before);
   for (const auto &effect : effects) {
     Value value = effect.getValue();
 
     // If we see an effect on anything other than a value, assume we can't
     // deduce anything about the last modifications.
     if (!value)
       return setToEntryState(after);
 
-    value = getMostUnderlyingValue(value, [&](Value value) {
+    value = UnderlyingValueAnalysis::getMostUnderlyingValue(
+        value, [&](Value value) {
           return getOrCreateFor<UnderlyingValueLattice>(op, value);
         });
     if (!value)
       return;
 
     // Nothing to do for reads.
     if (isa<MemoryEffects::Read>(effect.getEffect()))
       continue;
 
     result |= after->set(value, op);
op->walk([&](Operation *op) {
       if (!tag)
         return;
       os << "test_tag: " << tag.getValue() << ":\n";
       const LastModification *lastMods =
           solver.lookupState<LastModification>(op);
       assert(lastMods && "expected a dense lattice");
       for (auto [index, operand] : llvm::enumerate(op->getOperands())) {
         os << " operand #" << index << "\n";
-        Value value = getMostUnderlyingValue(operand, [&](Value value) {
+        Value value = UnderlyingValueAnalysis::getMostUnderlyingValue(
+            operand, [&](Value value) {
               return solver.lookupState<UnderlyingValueLattice>(value);
             });
         assert(value && "expected an underlying value");
         if (std::optional<ArrayRef<Operation *>> lastMod =
-                lastMods->getLastModifiers(value)) {
+                lastMods->getAdjacentAccess(value)) {
           for (Operation *lastModifier : *lastMod) {
             if (auto tagName =
                     lastModifier->getAttrOfType<StringAttr>("tag_name")) {
               os << "  - " << tagName.getValue() << "\n";
             } else {
               os << "  - " << lastModifier->getName() << "\n";
             }
           }

mlir/tools/mlir-opt/mlir-opt.cpp

 void registerTestLoopUnrollingPass();
 void registerTestLowerToLLVM();
 void registerTestMakeIsolatedFromAbovePass();
 void registerTestMatchReductionPass();
 void registerTestMathAlgebraicSimplificationPass();
 void registerTestMathPolynomialApproximationPass();
 void registerTestMemRefDependenceCheck();
 void registerTestMemRefStrideCalculation();
+void registerTestNextAccessPass();
 void registerTestOneToNTypeConversionPass();
 void registerTestOpaqueLoc();
 void registerTestPadFusion();
 void registerTestPDLByteCodePass();
 void registerTestPDLLPasses();
 void registerTestPreparationPassWithAllowedMemrefResults();
 void registerTestRecursiveTypesPass();
 void registerTestSCFUtilsPass();
#endif
   mlir::test::registerTestLoopUnrollingPass();
   mlir::test::registerTestLowerToLLVM();
   mlir::test::registerTestMakeIsolatedFromAbovePass();
   mlir::test::registerTestMatchReductionPass();
   mlir::test::registerTestMathAlgebraicSimplificationPass();
   mlir::test::registerTestMathPolynomialApproximationPass();
   mlir::test::registerTestMemRefDependenceCheck();
   mlir::test::registerTestMemRefStrideCalculation();
+  mlir::test::registerTestNextAccessPass();
   mlir::test::registerTestOneToNTypeConversionPass();
   mlir::test::registerTestOpaqueLoc();
   mlir::test::registerTestPadFusion();
   mlir::test::registerTestPDLByteCodePass();
   mlir::test::registerTestPDLLPasses();
   mlir::test::registerTestRecursiveTypesPass();
   mlir::test::registerTestSCFUtilsPass();
   mlir::test::registerTestSCFWhileOpBuilderPass();