[mlir] NFC: rename XDataFlowAnalysis to XForwardDataFlowAnalysis

[ftynse]

Summary

This makes naming consisnt with XBackwardDataFlowAnalysis.

[phisiart]

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

60

Now we can remove the ().

165

Now we can remove the ().

mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h

174

Now we can remove the ().

254

Now we can remove the ().

342–343

Let's remove the ().

flang/docs/fstack-arrays.md

 existing implementation already uses stack allocations (or better) where
 possible, and most such dummy arguments will be removed from generated code.
 
 #### `BufferizeHLFIR.cpp`
 TODO
 
 ### Detecting Allocations to Move
 Allocations which could be moved to the stack will be detected by performing a
-forward dense data flow analysis using `mlir::dataflow::DenseDataFlowAnalysis`.
+forward dense data flow analysis using `mlir::dataflow::DenseForwardDataFlowAnalysis`.
 This analysis will search for SSA values created by a `fir.allocmem` which are
 always freed using `fir.freemem` within the same function.
 
 Tracking allocations by SSA values will miss some cases where address
 calculations are duplicated in different blocks: resulting in different SSA
 values as arguments for the allocation and the free. It is believed that simple
 tracking of SSA values is sufficient for detecting the allocations for array
 temporaries added by Flang, because these temporaries should be simple arrays:

flang/lib/Optimizer/Transforms/StackArrays.cpp

public:
   /// freed before the function returns, plus whre to insert replacement
   /// fir.alloca ops
   void appendFreedValues(llvm::DenseSet<mlir::Value> &out) const;
 
   std::optional<AllocationState> get(mlir::Value val) const;
 };
 
 class AllocationAnalysis
-    : public mlir::dataflow::DenseDataFlowAnalysis<LatticePoint> {
+    : public mlir::dataflow::DenseForwardDataFlowAnalysis<LatticePoint> {
 public:
-  using DenseDataFlowAnalysis::DenseDataFlowAnalysis;
+  using DenseForwardDataFlowAnalysis::DenseForwardDataFlowAnalysis;
 
   void visitOperation(mlir::Operation *op, const LatticePoint &before,
                       LatticePoint *after) override;
 
   /// At an entry point, the last modifications of all memory resources are
   /// yet to be determined
   void setToEntryState(LatticePoint *lattice) override;
 

mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h

 // SparseConstantPropagation
 //===----------------------------------------------------------------------===//
 
 /// This analysis implements sparse constant propagation, which attempts to
 /// determine constant-valued results for operations using constant-valued
 /// operands, by speculatively folding operations. When combined with dead-code
 /// analysis, this becomes sparse conditional constant propagation (SCCP).
 class SparseConstantPropagation
-    : public SparseDataFlowAnalysis<Lattice<ConstantValue>> {
+    : public SparseForwardDataFlowAnalysis<Lattice<ConstantValue>> {
 public:
-  using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
+  using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis;
 
   void visitOperation(Operation *op,
                       ArrayRef<const Lattice<ConstantValue> *> operands,
                       ArrayRef<Lattice<ConstantValue> *> results) override;
 
   void setToEntryState(Lattice<ConstantValue> *lattice) override;
 };
 
 } // end namespace dataflow
 } // end namespace mlir
 
 #endif // MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H

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

public:
   }
 
   virtual ChangeResult meet(const AbstractDenseLattice &rhs) {
     return ChangeResult::NoChange;
   }
 };
 
 //===----------------------------------------------------------------------===//
-// AbstractDenseDataFlowAnalysis
+// AbstractDenseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// Base class for dense (forward) data-flow analyses. Dense data-flow analysis
+/// 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 {
+class AbstractDenseForwardDataFlowAnalysis : 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
private:
   void visitBlock(Block *block);
 
   /// Visit an operation for which the data flow is described by the
   /// `CallOpInterface`.
   void visitCallOperation(CallOpInterface call, AbstractDenseLattice *after);
 };
 
 //===----------------------------------------------------------------------===//
-// DenseDataFlowAnalysis
+// DenseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// A dense (forward) data-flow analysis for propagating lattices before and
+/// 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.
 ///
 /// `LatticeT` is expected to be a subclass of `AbstractDenseLattice`.
 template <typename LatticeT>
-class DenseDataFlowAnalysis : public AbstractDenseDataFlowAnalysis {
+class DenseForwardDataFlowAnalysis
+    : public AbstractDenseForwardDataFlowAnalysis {
   static_assert(
       std::is_base_of<AbstractDenseLattice, LatticeT>::value,
       "analysis state class expected to subclass AbstractDenseLattice");
 
 public:
-  using AbstractDenseDataFlowAnalysis::AbstractDenseDataFlowAnalysis;
+  using AbstractDenseForwardDataFlowAnalysis::
+      AbstractDenseForwardDataFlowAnalysis;
 
   /// Visit an operation with the dense lattice before its execution. This
   /// 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;
 
   /// Hook for customizing the behavior of lattice propagation along the call
public:
   /// the lattice prior to entering the callee, the custom behavior can be added
   /// for `action == CallControlFlowAction::Enter`. If the `call` op may affect
   /// the lattice post exiting the callee, the custom behavior can be added for
   /// `action == CallControlFlowAction::Exit`.
   virtual void visitCallControlFlowTransfer(CallOpInterface call,
                                             CallControlFlowAction action,
                                             const LatticeT &before,
                                             LatticeT *after) {
-    AbstractDenseDataFlowAnalysis::visitCallControlFlowTransfer(call, action,
-                                                                before, after);
+    AbstractDenseForwardDataFlowAnalysis::visitCallControlFlowTransfer(
+        call, action, before, after);
   }
 
   /// Hook for customizing the behavior of lattice propagation along the control
   /// flow edges between regions and their parent op. The control flows from
   /// `regionFrom` to `regionTo`, both of which may be `nullopt` to indicate the
   /// parent op. The lattice is propagated forward along this edge. The lattices
   /// are as follows:
   ///   - `before:`
public:
   /// for `regionFrom == nullopt`. If the `branch` op may affect the lattice
   /// after all terminated, the custom behavior can be added for `regionTo ==
   /// nullptr`. The behavior can be further refined for specific pairs of "from"
   /// and "to" regions.
   virtual void visitRegionBranchControlFlowTransfer(
       RegionBranchOpInterface branch, std::optional<unsigned> regionFrom,
       std::optional<unsigned> regionTo, const LatticeT &before,
       LatticeT *after) {
-    AbstractDenseDataFlowAnalysis::visitRegionBranchControlFlowTransfer(
+    AbstractDenseForwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer(
         branch, regionFrom, regionTo, before, after);
   }
 
 protected:
   /// Get the dense lattice after this program point.
   LatticeT *getLattice(ProgramPoint point) override {
     return getOrCreate<LatticeT>(point);
   }

mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h

public:
   /// value of the SSA value.
   void onUpdate(DataFlowSolver *solver) const override;
 };
 
 /// Integer range analysis determines the integer value range of SSA values
 /// using operations that define `InferIntRangeInterface` and also sets the
 /// range of iteration indices of loops with known bounds.
 class IntegerRangeAnalysis
-    : public SparseDataFlowAnalysis<IntegerValueRangeLattice> {
+    : public SparseForwardDataFlowAnalysis<IntegerValueRangeLattice> {
 public:
-  using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
+  using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis;
 
   /// At an entry point, we cannot reason about interger value ranges.
   void setToEntryState(IntegerValueRangeLattice *lattice) override {
     propagateIfChanged(lattice, lattice->join(IntegerValueRange::getMaxRange(
                                     lattice->getPoint())));
   }
 
   /// Visit an operation. Invoke the transfer function on each operation that

mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h

public:
   void print(raw_ostream &os) const override { value.print(os); }
 
 private:
   /// The currently computed value that is optimistically assumed to be true.
   ValueT value;
 };
 
 //===----------------------------------------------------------------------===//
-// AbstractSparseDataFlowAnalysis
+// AbstractSparseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// Base class for sparse (forward) data-flow analyses. A sparse analysis
+/// Base class for sparse forward data-flow analyses. A sparse analysis
 /// implements a transfer function on operations from the lattices of the
 /// operands to the lattices of the results. This analysis will propagate
 /// lattices across control-flow edges and the callgraph using liveness
 /// information.
-class AbstractSparseDataFlowAnalysis : public DataFlowAnalysis {
+class AbstractSparseForwardDataFlowAnalysis : public DataFlowAnalysis {
 public:
   /// Initialize the analysis by visiting every owner of an SSA value: all
   /// operations and blocks.
   LogicalResult initialize(Operation *top) override;
 
   /// Visit a program point. If this is a block and all control-flow
   /// predecessors or callsites are known, then the arguments lattices are
   /// propagated from them. If this is a call operation or an operation with
   /// region control-flow, then its result lattices are set accordingly.
   /// Otherwise, the operation transfer function is invoked.
   LogicalResult visit(ProgramPoint point) override;
 
 protected:
-  explicit AbstractSparseDataFlowAnalysis(DataFlowSolver &solver);
+  explicit AbstractSparseForwardDataFlowAnalysis(DataFlowSolver &solver);
 
   /// The operation transfer function. Given the operand lattices, this
   /// function is expected to set the result lattices.
   virtual void
   visitOperationImpl(Operation *op,
                      ArrayRef<const AbstractSparseLattice *> operandLattices,
                      ArrayRef<AbstractSparseLattice *> resultLattices) = 0;
 
private:
   /// regions or the parent operation itself, and set either the argument or
   /// parent result lattices.
   void visitRegionSuccessors(ProgramPoint point, RegionBranchOpInterface branch,
                              std::optional<unsigned> successorIndex,
                              ArrayRef<AbstractSparseLattice *> lattices);
 };
 
 //===----------------------------------------------------------------------===//
-// SparseDataFlowAnalysis
+// SparseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// A sparse (forward) data-flow analysis for propagating SSA value lattices
+/// A sparse forward data-flow analysis for propagating SSA value lattices
 /// across the IR by implementing transfer functions for operations.
 ///
 /// `StateT` is expected to be a subclass of `AbstractSparseLattice`.
 template <typename StateT>
-class SparseDataFlowAnalysis : public AbstractSparseDataFlowAnalysis {
+class SparseForwardDataFlowAnalysis
+    : public AbstractSparseForwardDataFlowAnalysis {
   static_assert(
       std::is_base_of<AbstractSparseLattice, StateT>::value,
       "analysis state class expected to subclass AbstractSparseLattice");
 
 public:
-  explicit SparseDataFlowAnalysis(DataFlowSolver &solver)
-      : AbstractSparseDataFlowAnalysis(solver) {}
+  explicit SparseForwardDataFlowAnalysis(DataFlowSolver &solver)
+      : AbstractSparseForwardDataFlowAnalysis(solver) {}
 
   /// Visit an operation with the lattices of its operands. This function is
   /// expected to set the lattices of the operation's results.
   virtual void visitOperation(Operation *op, ArrayRef<const StateT *> operands,
                               ArrayRef<StateT *> results) = 0;
 
   /// Given an operation with possible region control-flow, the lattices of the
   /// operands, and a region successor, compute the lattice values for block
protected:
   StateT *getLatticeElement(Value value) override {
     return getOrCreate<StateT>(value);
   }
 
   /// Get the lattice element for a value and create a dependency on the
   /// provided program point.
   const StateT *getLatticeElementFor(ProgramPoint point, Value value) {
     return static_cast<const StateT *>(
-        AbstractSparseDataFlowAnalysis::getLatticeElementFor(point, value));
+        AbstractSparseForwardDataFlowAnalysis::getLatticeElementFor(point,
+                                                                    value));
   }
 
   /// Set the given lattice element(s) at control flow entry point(s).
   virtual void setToEntryState(StateT *lattice) = 0;
   void setAllToEntryStates(ArrayRef<StateT *> lattices) {
-    AbstractSparseDataFlowAnalysis::setAllToEntryStates(
+    AbstractSparseForwardDataFlowAnalysis::setAllToEntryStates(
         {reinterpret_cast<AbstractSparseLattice *const *>(lattices.begin()),
          lattices.size()});
   }
 
 private:
   /// Type-erased wrappers that convert the abstract lattice operands to derived
   /// lattices and invoke the virtual hooks operating on the derived lattices.
   void visitOperationImpl(
private:
   void setToEntryState(AbstractSparseLattice *lattice) override {
     return setToEntryState(reinterpret_cast<StateT *>(lattice));
   }
 };
 
 //===----------------------------------------------------------------------===//
 // AbstractSparseBackwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-/// Base class for sparse (backward) data-flow analyses. Similar to
-/// AbstractSparseDataFlowAnalysis, but walks bottom to top.
+/// Base class for sparse backward data-flow analyses. Similar to
+/// AbstractSparseForwardDataFlowAnalysis, but walks bottom to top.
 class AbstractSparseBackwardDataFlowAnalysis : public DataFlowAnalysis {
 public:
   /// Initialize the analysis by visiting the operation and everything nested
   /// under it.
   LogicalResult initialize(Operation *top) override;
 
   /// Visit a program point. If this is a call operation or an operation with
   /// block or region control-flow, then operand lattices are set accordingly.

mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp

for (const auto it : llvm::zip(results, foldResults)) {
     OpFoldResult foldResult = std::get<1>(it);
     if (Attribute attr = llvm::dyn_cast_if_present<Attribute>(foldResult)) {
       LLVM_DEBUG(llvm::dbgs() << "Folded to constant: " << attr << "\n");
       propagateIfChanged(lattice,
                          lattice->join(ConstantValue(attr, op->getDialect())));
     } else {
       LLVM_DEBUG(llvm::dbgs()
                  << "Folded to value: " << foldResult.get<Value>() << "\n");
-      AbstractSparseDataFlowAnalysis::join(
+      AbstractSparseForwardDataFlowAnalysis::join(
           lattice, *getLatticeElement(foldResult.get<Value>()));
     }
   }
 }
 
 void SparseConstantPropagation::setToEntryState(
     Lattice<ConstantValue> *lattice) {
   propagateIfChanged(lattice,
                      lattice->join(ConstantValue::getUnknownConstant()));
 }

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

 #include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
 #include "mlir/Interfaces/CallInterfaces.h"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 
 using namespace mlir;
 using namespace mlir::dataflow;
 
 //===----------------------------------------------------------------------===//
-// AbstractDenseDataFlowAnalysis
+// AbstractDenseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-LogicalResult AbstractDenseDataFlowAnalysis::initialize(Operation *top) {
+LogicalResult AbstractDenseForwardDataFlowAnalysis::initialize(Operation *top) {
   // Visit every operation and block.
   processOperation(top);
   for (Region &region : top->getRegions()) {
     for (Block &block : region) {
       visitBlock(&block);
       for (Operation &op : block)
         if (failed(initialize(&op)))
           return failure();
     }
   }
   return success();
 }
 
-LogicalResult AbstractDenseDataFlowAnalysis::visit(ProgramPoint point) {
+LogicalResult AbstractDenseForwardDataFlowAnalysis::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 AbstractDenseDataFlowAnalysis::visitCallOperation(
+void AbstractDenseForwardDataFlowAnalysis::visitCallOperation(
     CallOpInterface call, AbstractDenseLattice *after) {
 
   const auto *predecessors =
       getOrCreateFor<PredecessorState>(call.getOperation(), call);
   // If not all return sites are known, then conservatively assume we can't
   // reason about the data-flow.
   if (!predecessors->allPredecessorsKnown())
     return setToEntryState(after);
for (Operation *predecessor : predecessors->getKnownPredecessors()) {
     AbstractDenseLattice *latticeAfterCall = after;
     const AbstractDenseLattice *latticeAtCalleeReturn =
         getLatticeFor(call.getOperation(), predecessor);
     visitCallControlFlowTransfer(call, CallControlFlowAction::ExitCallee,
                                  *latticeAtCalleeReturn, latticeAfterCall);
   }
 }
 
-void AbstractDenseDataFlowAnalysis::processOperation(Operation *op) {
+void AbstractDenseForwardDataFlowAnalysis::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 *after = getLattice(op);
 
   // Get the dense state before the execution of the op.
void AbstractDenseForwardDataFlowAnalysis::processOperation(Operation *op) {
   // sites.
   if (auto call = dyn_cast<CallOpInterface>(op))
     return visitCallOperation(call, after);
 
   // Invoke the operation transfer function.
   visitOperationImpl(op, *before, after);
 }
 
-void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) {
+void AbstractDenseForwardDataFlowAnalysis::visitBlock(Block *block) {
   // If the block is not executable, bail out.
   if (!getOrCreateFor<Executable>(block, block)->isLive())
     return;
 
   // Get the dense lattice to update.
   AbstractDenseLattice *after = getLattice(block);
 
   // The dense lattices of entry blocks are set by region control-flow or the
if (!getOrCreateFor<Executable>(
              ->isLive())
       continue;
 
     // Merge in the state from the predecessor's terminator.
     join(after, *getLatticeFor(block, predecessor->getTerminator()));
   }
 }
 
-void AbstractDenseDataFlowAnalysis::visitRegionBranchOperation(
+void AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation(
     ProgramPoint point, RegionBranchOpInterface branch,
     AbstractDenseLattice *after) {
   // Get the terminator predecessors.
   const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
   assert(predecessors->allPredecessorsKnown() &&
          "unexpected unresolved region successors");
 
   for (Operation *op : predecessors->getKnownPredecessors()) {
if (auto *toBlock = point.dyn_cast<Block *>()) {
       } else {
         join(after, *before);
       }
     }
   }
 }
 
 const AbstractDenseLattice *
-AbstractDenseDataFlowAnalysis::getLatticeFor(ProgramPoint dependent,
+AbstractDenseForwardDataFlowAnalysis::getLatticeFor(ProgramPoint dependent,
                                                     ProgramPoint point) {
   AbstractDenseLattice *state = getLattice(point);
   addDependency(state, dependent);
   return state;
 }
 
 //===----------------------------------------------------------------------===//
 // AbstractDenseBackwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//

mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp

auto getLoopBoundFromFold = [&](std::optional<OpFoldResult> loopBound,
     return getUpper ? APInt::getSignedMaxValue(width)
                     : APInt::getSignedMinValue(width);
   };
 
   // Infer bounds for loop arguments that have static bounds
   if (auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
     std::optional<Value> iv = loop.getSingleInductionVar();
     if (!iv) {
-      return SparseDataFlowAnalysis ::visitNonControlFlowArguments(
+      return SparseForwardDataFlowAnalysis ::visitNonControlFlowArguments(
           op, successor, argLattices, firstIndex);
     }
     std::optional<OpFoldResult> lowerBound = loop.getSingleLowerBound();
     std::optional<OpFoldResult> upperBound = loop.getSingleUpperBound();
     std::optional<OpFoldResult> step = loop.getSingleStep();
     APInt min = getLoopBoundFromFold(lowerBound, iv->getType(),
                                      /*getUpper=*/false);
     APInt max = getLoopBoundFromFold(upperBound, iv->getType(),
if (auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
     }
 
     IntegerValueRangeLattice *ivEntry = getLatticeElement(*iv);
     auto ivRange = ConstantIntRanges::fromSigned(min, max);
     propagateIfChanged(ivEntry, ivEntry->join(IntegerValueRange{ivRange}));
     return;
   }
 
-  return SparseDataFlowAnalysis::visitNonControlFlowArguments(
+  return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments(
       op, successor, argLattices, firstIndex);
 }

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp

void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const {
 
   // Push all users of the value to the queue.
   for (Operation *user : point.get<Value>().getUsers())
     for (DataFlowAnalysis *analysis : useDefSubscribers)
       solver->enqueue({user, analysis});
 }
 
 //===----------------------------------------------------------------------===//
-// AbstractSparseDataFlowAnalysis
+// AbstractSparseForwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
-AbstractSparseDataFlowAnalysis::AbstractSparseDataFlowAnalysis(
+AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis(
     DataFlowSolver &solver)
     : DataFlowAnalysis(solver) {
   registerPointKind<CFGEdge>();
 }
 
-LogicalResult AbstractSparseDataFlowAnalysis::initialize(Operation *top) {
+LogicalResult
+AbstractSparseForwardDataFlowAnalysis::initialize(Operation *top) {
   // Mark the entry block arguments as having reached their pessimistic
   // fixpoints.
   for (Region &region : top->getRegions()) {
     if (region.empty())
       continue;
     for (Value argument : region.front().getArguments())
       setToEntryState(getLatticeElement(argument));
   }
 
   return initializeRecursively(top);
 }
 
 LogicalResult
-AbstractSparseDataFlowAnalysis::initializeRecursively(Operation *op) {
+AbstractSparseForwardDataFlowAnalysis::initializeRecursively(Operation *op) {
   // Initialize the analysis by visiting every owner of an SSA value (all
   // operations and blocks).
   visitOperation(op);
   for (Region &region : op->getRegions()) {
     for (Block &block : region) {
       getOrCreate<Executable>(&block)->blockContentSubscribe(this);
       visitBlock(&block);
       for (Operation &op : block)
         if (failed(initializeRecursively(&op)))
           return failure();
     }
   }
 
   return success();
 }
 
-LogicalResult AbstractSparseDataFlowAnalysis::visit(ProgramPoint point) {
+LogicalResult AbstractSparseForwardDataFlowAnalysis::visit(ProgramPoint point) {
   if (Operation *op = llvm::dyn_cast_if_present<Operation *>(point))
     visitOperation(op);
   else if (Block *block = llvm::dyn_cast_if_present<Block *>(point))
     visitBlock(block);
   else
     return failure();
   return success();
 }
 
-void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) {
+void AbstractSparseForwardDataFlowAnalysis::visitOperation(Operation *op) {
   // Exit early on operations with no results.
   if (op->getNumResults() == 0)
     return;
 
   // If the containing block is not executable, bail out.
   if (!getOrCreate<Executable>(op->getBlock())->isLive())
     return;
 
for (Value operand : op->getOperands()) {
     operandLattice->useDefSubscribe(this);
     operandLattices.push_back(operandLattice);
   }
 
   // Invoke the operation transfer function.
   visitOperationImpl(op, operandLattices, resultLattices);
 }
 
-void AbstractSparseDataFlowAnalysis::visitBlock(Block *block) {
+void AbstractSparseForwardDataFlowAnalysis::visitBlock(Block *block) {
   // Exit early on blocks with no arguments.
   if (block->getNumArguments() == 0)
     return;
 
   // If the block is not executable, bail out.
   if (!getOrCreate<Executable>(block)->isLive())
     return;
 
if (auto branch =
         }
       }
     } else {
       return setAllToEntryStates(argLattices);
     }
   }
 }
 
-void AbstractSparseDataFlowAnalysis::visitRegionSuccessors(
+void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors(
     ProgramPoint point, RegionBranchOpInterface branch,
     std::optional<unsigned> successorIndex,
     ArrayRef<AbstractSparseLattice *> lattices) {
   const auto *predecessors = getOrCreateFor<PredecessorState>(point, point);
   assert(predecessors->allPredecessorsKnown() &&
          "unexpected unresolved region successors");
 
   for (Operation *op : predecessors->getKnownPredecessors()) {
for (Operation *op : predecessors->getKnownPredecessors()) {
     }
 
     for (auto it : llvm::zip(*operands, lattices.drop_front(firstIndex)))
       join(std::get<1>(it), *getLatticeElementFor(point, std::get<0>(it)));
   }
 }
 
 const AbstractSparseLattice *
-AbstractSparseDataFlowAnalysis::getLatticeElementFor(ProgramPoint point,
+AbstractSparseForwardDataFlowAnalysis::getLatticeElementFor(ProgramPoint point,
                                                             Value value) {
   AbstractSparseLattice *state = getLatticeElement(value);
   addDependency(state, point);
   return state;
 }
 
-void AbstractSparseDataFlowAnalysis::setAllToEntryStates(
+void AbstractSparseForwardDataFlowAnalysis::setAllToEntryStates(
     ArrayRef<AbstractSparseLattice *> lattices) {
   for (AbstractSparseLattice *lattice : lattices)
     setToEntryState(lattice);
 }
 
-void AbstractSparseDataFlowAnalysis::join(AbstractSparseLattice *lhs,
-                                          const AbstractSparseLattice &rhs) {
+void AbstractSparseForwardDataFlowAnalysis::join(
+    AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs) {
   propagateIfChanged(lhs, lhs->join(rhs));
 }
 
 //===----------------------------------------------------------------------===//
 // AbstractSparseBackwardDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
 AbstractSparseBackwardDataFlowAnalysis::AbstractSparseBackwardDataFlowAnalysis(

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
+  DataFlow/TestDenseForwardDataFlowAnalysis.cpp
   DataFlow/TestLivenessAnalysis.cpp
+  DataFlow/TestSparseBackwardDataFlowAnalysis.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/TestDenseDataFlowAnalysis.h

struct UnderlyingValueLattice : public Lattice<UnderlyingValue> {
   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 SparseForwardDataFlowAnalysis<UnderlyingValueLattice> {
 public:
-  using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
+  using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis;
 
   /// 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);
   }
 

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

-//===- TestDenseDataFlowAnalysis.cpp - Test dense data flow analysis ------===//
+//===- TestDenseForwardDataFlowAnalysis.cpp -------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
+//
+// Implementation of tests passes exercising dense forward data flow analysis.
+//
+//===----------------------------------------------------------------------===//
 
 #include "TestDenseDataFlowAnalysis.h"
 #include "TestDialect.h"
 #include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h"
 #include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
 #include "mlir/Analysis/DataFlow/DenseAnalysis.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 #include "mlir/Pass/Pass.h"
return AccessLatticeBase::merge(static_cast<AccessLatticeBase>(
         static_cast<const LastModification &>(lattice)));
   }
 
   void print(raw_ostream &os) const override {
     return AccessLatticeBase::print(os);
   }
 };
 
-class LastModifiedAnalysis : public DenseDataFlowAnalysis<LastModification> {
+class LastModifiedAnalysis
+    : public DenseForwardDataFlowAnalysis<LastModification> {
 public:
-  using DenseDataFlowAnalysis::DenseDataFlowAnalysis;
+  using DenseForwardDataFlowAnalysis::DenseForwardDataFlowAnalysis;
 
   /// 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;
 
void LastModifiedAnalysis::visitCallControlFlowTransfer(
   auto testCallAndStore =
       dyn_cast<::test::TestCallAndStoreOp>(call.getOperation());
   if (testCallAndStore && ((action == CallControlFlowAction::EnterCallee &&
                             testCallAndStore.getStoreBeforeCall()) ||
                            (action == CallControlFlowAction::ExitCallee &&
                             !testCallAndStore.getStoreBeforeCall()))) {
     return visitOperation(call, before, after);
   }
-  AbstractDenseDataFlowAnalysis::visitCallControlFlowTransfer(call, action,
-                                                              before, after);
+  AbstractDenseForwardDataFlowAnalysis::visitCallControlFlowTransfer(
+      call, action, before, after);
 }
 
 void LastModifiedAnalysis::visitRegionBranchControlFlowTransfer(
     RegionBranchOpInterface branch, std::optional<unsigned> regionFrom,
     std::optional<unsigned> regionTo, const LastModification &before,
     LastModification *after) {
   auto testStoreWithARegion =
       dyn_cast<::test::TestStoreWithARegion>(branch.getOperation());
   if (testStoreWithARegion &&
       ((!regionTo && !testStoreWithARegion.getStoreBeforeRegion()) ||
        (!regionFrom && testStoreWithARegion.getStoreBeforeRegion()))) {
     return visitOperation(branch, before, after);
   }
-  AbstractDenseDataFlowAnalysis::visitRegionBranchControlFlowTransfer(
+  AbstractDenseForwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer(
       branch, regionFrom, regionTo, before, after);
 }
 
 namespace {
 struct TestLastModifiedPass
     : public PassWrapper<TestLastModifiedPass, OperationPass<>> {
   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestLastModifiedPass)
 

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

void WrittenToAnalysis::visitOperation(Operation *op,
                                        ArrayRef<WrittenTo *> operands,
                                        ArrayRef<const WrittenTo *> results) {
   if (auto store = dyn_cast<memref::StoreOp>(op)) {
     SetVector<StringAttr> newWrites;
     newWrites.insert(op->getAttrOfType<StringAttr>("tag_name"));
     propagateIfChanged(operands[0], operands[0]->addWrites(newWrites));
     return;
   } // By default, every result of an op depends on every operand.
-    for (const WrittenTo *r : results) {
-      for (WrittenTo *operand : operands) {
-        meet(operand, *r);
-      }
-      addDependency(const_cast<WrittenTo *>(r), op);
-    }
 }
 
 void WrittenToAnalysis::visitBranchOperand(OpOperand &operand) {
   // Mark branch operands as "brancharg%d", with %d the operand number.
   WrittenTo *lattice = getLatticeElement(operand.get());
   SetVector<StringAttr> newWrites;
   newWrites.insert(
       StringAttr::get(operand.getOwner()->getContext(),