[mlir][dataflow] Remove Abstract{Sparse,Dense}Lattice::isAtFixpoint() and an ineffective optimization to simplify public API

[phisiart]

Summary

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.

[aartbik]

I am added as reviewer due to the trigger word "sparse" ;-), but this changes looks acceptable (perhap make it a bit more clear that is does change semantics beyond just removing the function in the title)

[phisiart]

Also remove isAtFixpoint() from dense analysis.

[phisiart]

In D131660#3716480, @aartbik wrote:

I am added as reviewer due to the trigger word "sparse" ;-), but this changes looks acceptable (perhap make it a bit more clear that is does change semantics beyond just removing the function in the title)

I modified the title and description. Also included the change to dense analysis (it was previously missed).

[Mogball]

Thanks!

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

public:
   using AnalysisState::AnalysisState;
 
   /// Join the lattice across control-flow or callgraph edges.
   virtual ChangeResult join(const AbstractDenseLattice &rhs) = 0;
 
   /// 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;
 };
 
 //===----------------------------------------------------------------------===//
 // AbstractDenseDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
 /// Base class for dense data-flow analyses. Dense data-flow analysis attaches a
 /// lattice between the execution of operations and implements a transfer

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

 public:
   /// Lattices can only be created for values.
   AbstractSparseLattice(Value value) : AnalysisState(value) {}
 
   /// Join the information contained in 'rhs' into this lattice. Returns
   /// 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.
   virtual ChangeResult markPessimisticFixpoint() = 0;
 
   /// When the lattice gets updated, propagate an update to users of the value
   /// using its use-def chain to subscribed analyses.
   void onUpdate(DataFlowSolver *solver) const override;
public:
   /// Returns true if the value of this lattice hasn't yet been initialized.
   bool isUninitialized() const override { return !optimisticValue.has_value(); }
   /// Force the initialization of the element by setting it to its pessimistic
   /// fixpoint.
   ChangeResult defaultInitialize() override {
     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<ValueT> &rhsLattice =
         static_cast<const Lattice<ValueT> &>(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.
     return join(rhsLattice.getValue());
   }
 
   /// Join the information contained in the 'rhs' value into this
   /// lattice. Returns if the state of the current lattice changed.
ChangeResult join(const ValueT &rhs) {
     optimisticValue = newValue;
     return ChangeResult::Change;
   }
 
   /// Mark the lattice element as having reached a pessimistic fixpoint. This
   /// 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
     // to our optimistic value.
     optimisticValue = knownValue;
     return ChangeResult::Change;
   }
 

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

 
 void AbstractDenseDataFlowAnalysis::visitOperation(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);
-  if (after->isAtFixpoint())
-    return;
 
   // If this op implements region control-flow, then control-flow dictates its
   // transfer function.
   if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
     return visitRegionBranchOperation(op, branch, after);
 
   // If this is a call operation, then join its lattices across known return
   // sites.

 
 void AbstractDenseDataFlowAnalysis::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);
-  if (after->isAtFixpoint())
-    return;
 
   // The dense lattices of entry blocks are set by region control-flow or the
   // callgraph.
   if (block->isEntryBlock()) {
     // Check if this block is the entry block of a callable region.
     auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
     if (callable && callable.getCallableRegion() == block->getParent()) {
       const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp

void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) {
 
   // If the containing block is not executable, bail out.
   if (!getOrCreate<Executable>(op->getBlock())->isLive())
     return;
 
   // Get the result lattices.
   SmallVector<AbstractSparseLattice *> 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<RegionBranchOpInterface>(op)) {
     return visitRegionSuccessors({branch}, branch,
                                  /*successorIndex=*/llvm::None, resultLattices);
   }
 
   // The results of a call operation are determined by the callgraph.
void AbstractSparseDataFlowAnalysis::visitBlock(Block *block) {
 
   // If the block is not executable, bail out.
   if (!getOrCreate<Executable>(block)->isLive())
     return;
 
   // Get the argument lattices.
   SmallVector<AbstractSparseLattice *> 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.
   if (block->isEntryBlock()) {
     // Check if this block is the entry block of a callable region.
     auto callable = dyn_cast<CallableOpInterface>(block->getParentOp());
     if (callable && callable.getCallableRegion() == block->getParent()) {
       const auto *callsites = getOrCreateFor<PredecessorState>(block, callable);

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

public:
   /// last modifications of all memory resources are unknown.
   ChangeResult reset() override {
     if (lastMods.empty())
       return ChangeResult::NoChange;
     lastMods.clear();
     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<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());