From 4835441d02c19e1c906d6c510c3e35f41d910fe7 Mon Sep 17 00:00:00 2001 From: Zhixun Tan Date: Mon, 15 Aug 2022 13:20:48 -0400 Subject: [PATCH] [mlir][dataflow] Remove Abstract{Sparse,Dense}Lattice::isAtFixpoint() and an ineffective optimization to simplify public API Currently, in the MLIR `{Sparse,Dense}DataFlowAnalysis` API, there is a small optimization: Before running a transfer function, if the "out state" is already at the pessimistic fixpoint (bottom lattice value), then we know that it cannot possibly be changed, therefore we can skip the transfer function. I benchmarked and found that this optimization is ineffective, so we can remove it and simplify `{Sparse,Dense}DataFlowAnalysis`. In a subsequent patch, I plan to change/remove the concept of the pessimistic fixpoint so that the API is further simplified. Benchmark: I ran the following tests 5 times (after 3 warmup runs), and timed the `initializeAndRun()` function. | Test | Before (us) | After (us) | | mlir-opt -test-dead-code-analysis mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir | 181.2536 | 187.7074 | | mlir-opt -- -test-dead-code-analysis mlir/test/Analysis/DataFlow/test-last-modified-callgraph.mlir | 109.5504 | 105.0654 | | mlir-opt -- -test-dead-code-analysis mlir/test/Analysis/DataFlow/test-last-modified.mlir | 333.3646 | 322.4224 | | mlir-opt -- -allow-unregistered-dialect -sccp mlir/test/Analysis/DataFlow/test-combined-sccp.mlir | 1027.1492 | 1081.818 | Note: `test-combined-sccp.mlir` is crafted by combining `mlir/test/Transforms/sccp.mlir`, `mlir/test/Transforms/sccp-structured.mlir` and `mlir/test/Transforms/sccp-callgraph.mlir`. Reviewed By: aartbik, Mogball Differential Revision: https://reviews.llvm.org/D131660 --- mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h | 4 ---- mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h | 15 +++------------ mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp | 4 ---- mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp | 12 ------------ .../lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp | 3 --- 5 files changed, 3 insertions(+), 35 deletions(-) diff --git a/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h index 43432c7..1e66a4a 100644 --- a/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/DenseAnalysis.h @@ -42,10 +42,6 @@ public: /// Reset the dense lattice to a pessimistic value. This occurs when the /// analysis cannot reason about the data-flow. virtual ChangeResult reset() = 0; - - /// Returns true if the lattice state has reached a pessimistic fixpoint. That - /// is, no further modifications to the lattice can occur. - virtual bool isAtFixpoint() const = 0; }; //===----------------------------------------------------------------------===// diff --git a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h index 34cd5aa..17a0f16 100644 --- a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h @@ -38,10 +38,6 @@ public: /// if the value of the lattice changed. virtual ChangeResult join(const AbstractSparseLattice &rhs) = 0; - /// Returns true if the lattice element is at fixpoint and further calls to - /// `join` will not update the value of the element. - virtual bool isAtFixpoint() const = 0; - /// Mark the lattice element as having reached a pessimistic fixpoint. This /// means that the lattice may potentially have conflicting value states, and /// only the most conservative value should be relied on. @@ -103,19 +99,14 @@ public: return markPessimisticFixpoint(); } - /// Returns true if the lattice has reached a fixpoint. A fixpoint is when - /// the information optimistically assumed to be true is the same as the - /// information known to be true. - bool isAtFixpoint() const override { return optimisticValue == knownValue; } - /// Join the information contained in the 'rhs' lattice into this /// lattice. Returns if the state of the current lattice changed. ChangeResult join(const AbstractSparseLattice &rhs) override { const Lattice &rhsLattice = static_cast &>(rhs); - // If we are at a fixpoint, or rhs is uninitialized, there is nothing to do. - if (isAtFixpoint() || rhsLattice.isUninitialized()) + // If rhs is uninitialized, there is nothing to do. + if (rhsLattice.isUninitialized()) return ChangeResult::NoChange; // Join the rhs value into this lattice. @@ -150,7 +141,7 @@ public: /// means that the lattice may potentially have conflicting value states, /// and only the conservatively known value state should be relied on. ChangeResult markPessimisticFixpoint() override { - if (isAtFixpoint()) + if (optimisticValue == knownValue) return ChangeResult::NoChange; // For this fixed point, we take whatever we knew to be true and set that diff --git a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp index 4c0a166..659ae3c 100644 --- a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp @@ -49,8 +49,6 @@ void AbstractDenseDataFlowAnalysis::visitOperation(Operation *op) { // Get the dense lattice to update. AbstractDenseLattice *after = getLattice(op); - if (after->isAtFixpoint()) - return; // If this op implements region control-flow, then control-flow dictates its // transfer function. @@ -91,8 +89,6 @@ void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) { // Get the dense lattice to update. AbstractDenseLattice *after = getLattice(block); - if (after->isAtFixpoint()) - return; // The dense lattices of entry blocks are set by region control-flow or the // callgraph. diff --git a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp index 776f284..ca82e32 100644 --- a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp @@ -87,16 +87,10 @@ void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) { // Get the result lattices. SmallVector resultLattices; resultLattices.reserve(op->getNumResults()); - // Track whether all results have reached their fixpoint. - bool allAtFixpoint = true; for (Value result : op->getResults()) { AbstractSparseLattice *resultLattice = getLatticeElement(result); - allAtFixpoint &= resultLattice->isAtFixpoint(); resultLattices.push_back(resultLattice); } - // If all result lattices have reached a fixpoint, there is nothing to do. - if (allAtFixpoint) - return; // The results of a region branch operation are determined by control-flow. if (auto branch = dyn_cast(op)) { @@ -145,16 +139,10 @@ void AbstractSparseDataFlowAnalysis::visitBlock(Block *block) { // Get the argument lattices. SmallVector argLattices; argLattices.reserve(block->getNumArguments()); - bool allAtFixpoint = true; for (BlockArgument argument : block->getArguments()) { AbstractSparseLattice *argLattice = getLatticeElement(argument); - allAtFixpoint &= argLattice->isAtFixpoint(); argLattices.push_back(argLattice); } - // If all argument lattices have reached their fixpoints, then there is - // nothing to do. - if (allAtFixpoint) - return; // The argument lattices of entry blocks are set by region control-flow or the // callgraph. diff --git a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp index 669e683..070bbb9 100644 --- a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp +++ b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp @@ -73,9 +73,6 @@ public: return ChangeResult::Change; } - /// The lattice is never at a fixpoint. - bool isAtFixpoint() const override { return false; } - /// Join the last modifications. ChangeResult join(const AbstractDenseLattice &lattice) override { const auto &rhs = static_cast(lattice); -- 2.7.4