[mlir][dataflow] Remove Abstract{Sparse,Dense}Lattice::isAtFixpoint() and an ineffect...
authorZhixun Tan <phisiart@gmail.com>
Mon, 15 Aug 2022 17:20:48 +0000 (13:20 -0400)
committerJeff Niu <jeff@modular.com>
Mon, 15 Aug 2022 17:21:05 +0000 (13:21 -0400)
commit4835441d02c19e1c906d6c510c3e35f41d910fe7
tree5e2866e22ac8927be1f835160e387d73df385261
parent53d4ff4a4783d8b0a37e5349eace738f4aceed7c
[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
mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h
mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp
mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp
mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp