diff --git a/flang/docs/fstack-arrays.md b/flang/docs/fstack-arrays.md --- a/flang/docs/fstack-arrays.md +++ b/flang/docs/fstack-arrays.md @@ -129,7 +129,7 @@ ### 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. diff --git a/flang/lib/Optimizer/Transforms/StackArrays.cpp b/flang/lib/Optimizer/Transforms/StackArrays.cpp --- a/flang/lib/Optimizer/Transforms/StackArrays.cpp +++ b/flang/lib/Optimizer/Transforms/StackArrays.cpp @@ -139,9 +139,9 @@ }; class AllocationAnalysis - : public mlir::dataflow::DenseDataFlowAnalysis { + : public mlir::dataflow::DenseForwardDataFlowAnalysis { public: - using DenseDataFlowAnalysis::DenseDataFlowAnalysis; + using DenseForwardDataFlowAnalysis::DenseForwardDataFlowAnalysis; void visitOperation(mlir::Operation *op, const LatticePoint &before, LatticePoint *after) override; diff --git a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h --- a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h @@ -97,9 +97,9 @@ /// operands, by speculatively folding operations. When combined with dead-code /// analysis, this becomes sparse conditional constant propagation (SCCP). class SparseConstantPropagation - : public SparseDataFlowAnalysis> { + : public SparseForwardDataFlowAnalysis> { public: - using SparseDataFlowAnalysis::SparseDataFlowAnalysis; + using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis; void visitOperation(Operation *op, ArrayRef *> operands, diff --git a/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h --- a/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h @@ -54,10 +54,10 @@ }; //===----------------------------------------------------------------------===// -// 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 @@ -67,7 +67,7 @@ /// 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; @@ -159,22 +159,24 @@ }; //===----------------------------------------------------------------------===// -// 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 -class DenseDataFlowAnalysis : public AbstractDenseDataFlowAnalysis { +class DenseForwardDataFlowAnalysis + : public AbstractDenseForwardDataFlowAnalysis { static_assert( std::is_base_of::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 @@ -201,8 +203,8 @@ 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 @@ -232,7 +234,7 @@ RegionBranchOpInterface branch, std::optional regionFrom, std::optional regionTo, const LatticeT &before, LatticeT *after) { - AbstractDenseDataFlowAnalysis::visitRegionBranchControlFlowTransfer( + AbstractDenseForwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer( branch, regionFrom, regionTo, before, after); } diff --git a/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h --- a/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h @@ -82,9 +82,9 @@ /// using operations that define `InferIntRangeInterface` and also sets the /// range of iteration indices of loops with known bounds. class IntegerRangeAnalysis - : public SparseDataFlowAnalysis { + : public SparseForwardDataFlowAnalysis { public: - using SparseDataFlowAnalysis::SparseDataFlowAnalysis; + using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis; /// At an entry point, we cannot reason about interger value ranges. void setToEntryState(IntegerValueRangeLattice *lattice) override { diff --git a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h --- a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h @@ -168,15 +168,15 @@ }; //===----------------------------------------------------------------------===// -// 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. @@ -190,7 +190,7 @@ 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. @@ -248,22 +248,23 @@ }; //===----------------------------------------------------------------------===// -// 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 -class SparseDataFlowAnalysis : public AbstractSparseDataFlowAnalysis { +class SparseForwardDataFlowAnalysis + : public AbstractSparseForwardDataFlowAnalysis { static_assert( std::is_base_of::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. @@ -295,13 +296,14 @@ /// provided program point. const StateT *getLatticeElementFor(ProgramPoint point, Value value) { return static_cast( - 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 lattices) { - AbstractSparseDataFlowAnalysis::setAllToEntryStates( + AbstractSparseForwardDataFlowAnalysis::setAllToEntryStates( {reinterpret_cast(lattices.begin()), lattices.size()}); } @@ -338,8 +340,8 @@ // 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 diff --git a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp --- a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp @@ -96,7 +96,7 @@ } else { LLVM_DEBUG(llvm::dbgs() << "Folded to value: " << foldResult.get() << "\n"); - AbstractSparseDataFlowAnalysis::join( + AbstractSparseForwardDataFlowAnalysis::join( lattice, *getLatticeElement(foldResult.get())); } } diff --git a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp --- a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp @@ -15,10 +15,10 @@ 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 ®ion : top->getRegions()) { @@ -32,7 +32,7 @@ return success(); } -LogicalResult AbstractDenseDataFlowAnalysis::visit(ProgramPoint point) { +LogicalResult AbstractDenseForwardDataFlowAnalysis::visit(ProgramPoint point) { if (auto *op = llvm::dyn_cast_if_present(point)) processOperation(op); else if (auto *block = llvm::dyn_cast_if_present(point)) @@ -42,7 +42,7 @@ return success(); } -void AbstractDenseDataFlowAnalysis::visitCallOperation( +void AbstractDenseForwardDataFlowAnalysis::visitCallOperation( CallOpInterface call, AbstractDenseLattice *after) { const auto *predecessors = @@ -74,7 +74,7 @@ } } -void AbstractDenseDataFlowAnalysis::processOperation(Operation *op) { +void AbstractDenseForwardDataFlowAnalysis::processOperation(Operation *op) { // If the containing block is not executable, bail out. if (!getOrCreateFor(op, op->getBlock())->isLive()) return; @@ -103,7 +103,7 @@ visitOperationImpl(op, *before, after); } -void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) { +void AbstractDenseForwardDataFlowAnalysis::visitBlock(Block *block) { // If the block is not executable, bail out. if (!getOrCreateFor(block, block)->isLive()) return; @@ -160,7 +160,7 @@ } } -void AbstractDenseDataFlowAnalysis::visitRegionBranchOperation( +void AbstractDenseForwardDataFlowAnalysis::visitRegionBranchOperation( ProgramPoint point, RegionBranchOpInterface branch, AbstractDenseLattice *after) { // Get the terminator predecessors. @@ -220,8 +220,8 @@ } const AbstractDenseLattice * -AbstractDenseDataFlowAnalysis::getLatticeFor(ProgramPoint dependent, - ProgramPoint point) { +AbstractDenseForwardDataFlowAnalysis::getLatticeFor(ProgramPoint dependent, + ProgramPoint point) { AbstractDenseLattice *state = getLattice(point); addDependency(state, dependent); return state; diff --git a/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp b/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp --- a/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp @@ -200,7 +200,7 @@ if (auto loop = dyn_cast(op)) { std::optional iv = loop.getSingleInductionVar(); if (!iv) { - return SparseDataFlowAnalysis ::visitNonControlFlowArguments( + return SparseForwardDataFlowAnalysis ::visitNonControlFlowArguments( op, successor, argLattices, firstIndex); } std::optional lowerBound = loop.getSingleLowerBound(); @@ -228,6 +228,6 @@ return; } - return SparseDataFlowAnalysis::visitNonControlFlowArguments( + return SparseForwardDataFlowAnalysis::visitNonControlFlowArguments( op, successor, argLattices, firstIndex); } diff --git a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp --- a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp @@ -28,16 +28,17 @@ } //===----------------------------------------------------------------------===// -// AbstractSparseDataFlowAnalysis +// AbstractSparseForwardDataFlowAnalysis //===----------------------------------------------------------------------===// -AbstractSparseDataFlowAnalysis::AbstractSparseDataFlowAnalysis( +AbstractSparseForwardDataFlowAnalysis::AbstractSparseForwardDataFlowAnalysis( DataFlowSolver &solver) : DataFlowAnalysis(solver) { registerPointKind(); } -LogicalResult AbstractSparseDataFlowAnalysis::initialize(Operation *top) { +LogicalResult +AbstractSparseForwardDataFlowAnalysis::initialize(Operation *top) { // Mark the entry block arguments as having reached their pessimistic // fixpoints. for (Region ®ion : top->getRegions()) { @@ -51,7 +52,7 @@ } 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); @@ -68,7 +69,7 @@ return success(); } -LogicalResult AbstractSparseDataFlowAnalysis::visit(ProgramPoint point) { +LogicalResult AbstractSparseForwardDataFlowAnalysis::visit(ProgramPoint point) { if (Operation *op = llvm::dyn_cast_if_present(point)) visitOperation(op); else if (Block *block = llvm::dyn_cast_if_present(point)) @@ -78,7 +79,7 @@ return success(); } -void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) { +void AbstractSparseForwardDataFlowAnalysis::visitOperation(Operation *op) { // Exit early on operations with no results. if (op->getNumResults() == 0) return; @@ -128,7 +129,7 @@ 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; @@ -209,7 +210,7 @@ } } -void AbstractSparseDataFlowAnalysis::visitRegionSuccessors( +void AbstractSparseForwardDataFlowAnalysis::visitRegionSuccessors( ProgramPoint point, RegionBranchOpInterface branch, std::optional successorIndex, ArrayRef lattices) { @@ -267,21 +268,21 @@ } const AbstractSparseLattice * -AbstractSparseDataFlowAnalysis::getLatticeElementFor(ProgramPoint point, - Value value) { +AbstractSparseForwardDataFlowAnalysis::getLatticeElementFor(ProgramPoint point, + Value value) { AbstractSparseLattice *state = getLatticeElement(value); addDependency(state, point); return state; } -void AbstractSparseDataFlowAnalysis::setAllToEntryStates( +void AbstractSparseForwardDataFlowAnalysis::setAllToEntryStates( ArrayRef 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)); } diff --git a/mlir/test/lib/Analysis/CMakeLists.txt b/mlir/test/lib/Analysis/CMakeLists.txt --- a/mlir/test/lib/Analysis/CMakeLists.txt +++ b/mlir/test/lib/Analysis/CMakeLists.txt @@ -12,10 +12,10 @@ 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 diff --git a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.h b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.h --- a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.h +++ b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.h @@ -130,9 +130,9 @@ /// 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 { + : public SparseForwardDataFlowAnalysis { public: - using SparseDataFlowAnalysis::SparseDataFlowAnalysis; + using SparseForwardDataFlowAnalysis::SparseForwardDataFlowAnalysis; /// The underlying value of the results of an operation are not known. void visitOperation(Operation *op, diff --git a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestDenseForwardDataFlowAnalysis.cpp rename from mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp rename to mlir/test/lib/Analysis/DataFlow/TestDenseForwardDataFlowAnalysis.cpp --- a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp +++ b/mlir/test/lib/Analysis/DataFlow/TestDenseForwardDataFlowAnalysis.cpp @@ -1,10 +1,14 @@ -//===- 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" @@ -40,9 +44,10 @@ } }; -class LastModifiedAnalysis : public DenseDataFlowAnalysis { +class LastModifiedAnalysis + : public DenseForwardDataFlowAnalysis { 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 @@ -120,8 +125,8 @@ !testCallAndStore.getStoreBeforeCall()))) { return visitOperation(call, before, after); } - AbstractDenseDataFlowAnalysis::visitCallControlFlowTransfer(call, action, - before, after); + AbstractDenseForwardDataFlowAnalysis::visitCallControlFlowTransfer( + call, action, before, after); } void LastModifiedAnalysis::visitRegionBranchControlFlowTransfer( @@ -135,7 +140,7 @@ (!regionFrom && testStoreWithARegion.getStoreBeforeRegion()))) { return visitOperation(branch, before, after); } - AbstractDenseDataFlowAnalysis::visitRegionBranchControlFlowTransfer( + AbstractDenseForwardDataFlowAnalysis::visitRegionBranchControlFlowTransfer( branch, regionFrom, regionTo, before, after); } diff --git a/mlir/test/lib/Analysis/DataFlow/TestBackwardDataFlowAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestSparseBackwardDataFlowAnalysis.cpp rename from mlir/test/lib/Analysis/DataFlow/TestBackwardDataFlowAnalysis.cpp rename to mlir/test/lib/Analysis/DataFlow/TestSparseBackwardDataFlowAnalysis.cpp --- a/mlir/test/lib/Analysis/DataFlow/TestBackwardDataFlowAnalysis.cpp +++ b/mlir/test/lib/Analysis/DataFlow/TestSparseBackwardDataFlowAnalysis.cpp @@ -69,12 +69,12 @@ 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(r), op); + for (const WrittenTo *r : results) { + for (WrittenTo *operand : operands) { + meet(operand, *r); } + addDependency(const_cast(r), op); + } } void WrittenToAnalysis::visitBranchOperand(OpOperand &operand) {