[mlir][dataflow] Consolidate AbstractSparseLattice::markPessimisticFixpoint() and AbstractDenseLattice::reset() into Abstract{Sparse,Dense}DataFlowAnalysis::setToEntryState().

[phisiart]

Summary

Rationale

For a program point where we cannot reason about incoming dataflow (e.g. an argument of an entry block), the framework needs to initialize the state.

Currently, AbstractSparseDataFlowAnalysis initializes such state to the "pessimistic fixpoint", and AbstractDenseDataFlowAnalysis calls the state's reset() function.

However, entry states aren't necessarily the pessimistic fixpoint. Example: in reaching definition, the pessimistic fixpoint is {all definitions}, but the entry state is {}.

This awkwardness might be why the dense analysis API currently uses reset() instead of markPessimisticFixpoint().

This patch consolidates entry point initialization into a single function setToEntryState().

API Location

Note that setToEntryState() is defined in the analysis rather than the lattice, so that we allow different analyses to use the same lattice but different entry states.

Removal of the concept of optimistic/known value

The concept of optimistic/known value is too specific to SCCP.

Furthermore, the known value is not really used: In the current SCCP implementation, the known value (pessimistic fixpoint) is always Attribute{} (non-constant). This means there's no point storing a knownValue in each state.

If we do need to re-introduce optimistic/known value, we should put it in the SCCP analysis, not the sparse analysis API.

Terminology

Please let me know if "entry state" is a good terminology.

I chose "entry" from Wikipedia (https://en.wikipedia.org/wiki/Data-flow_analysis#Basic_principles).

Another term I can think of is "boundary" (https://suif.stanford.edu/~courses/cs243/lectures/L3-DFA2-revised.pdf) which might be better since it also makes sense for backward analysis.

[Mogball]

Can you take a look at the failures?

ConstantPropagationAnalysis.cpp:42:5: error: use of undeclared identifier 'markAllPessimisticFixpoint'
    markAllPessimisticFixpoint(results);

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

50

Nit: I would call it getUnknownConstant

[phisiart]

Rename NonConstant to UnknownConstant.

[phisiart]

In D132086#3732322, @Mogball wrote:

Can you take a look at the failures?

ConstantPropagationAnalysis.cpp:42:5: error: use of undeclared identifier 'markAllPessimisticFixpoint'
    markAllPessimisticFixpoint(results);

I suspect that the failures are due to the fact that internally we are still using an older version of LLVM and there are problems with generating the external patch.

I think what I should do is to wait until our internal version catches up.

[Mogball]

You can try rebasing your commit

[phisiart]

Rebase.

[phisiart]

Reformat.

[Mogball]

Overall, I agree with the direction of this patch. My main concern is around having setValue on Lattice. I don't see the need for the function since join(any, entry_state) should result in entry_state.

I'm also not particularly fond of EntryState as the name, but I can't come up with anything better than DefaultValue but that's kind of vague.

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

79

Why do you need to be able to overwrite the value in lattice? join with an uninitialized value will always take the RHS value. In what cases would a lattice value be overwritten and changed back to its entry state? This wouldn't be guaranteed to be monotonic.

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

93

Can you name this something else, like newValue? And then drop this->

93–99

I would drop the rvalue reference. It doesn't add anything over just plain value here.

mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp

110

This should be join. I don't see the need to use setValue

[phisiart]

Remove setValue() - join() should be enough for a monotonic framework.

[phisiart]

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

93

Removed setValue() entirely.

93–99

Removed setValue() entirely.

[Mogball]

LGTM thanks!

[jsetoain]

Apologies. Broken herald rule.

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

public:
   /// Compare the constant values.
   bool operator==(const ConstantValue &rhs) const {
     return constant == rhs.constant;
   }
 
   /// Print the constant value.
   void print(raw_ostream &os) const;
 
-  /// The pessimistic value state of the constant value is unknown.
-  static ConstantValue getPessimisticValueState(Value value) { return {}; }
+  /// The state where the constant value is unknown.
+  static ConstantValue getUnknownConstant() { return {}; }
 
   /// The union with another constant value is null if they are different, and
   /// the same if they are the same.
   static ConstantValue join(const ConstantValue &lhs,
                             const ConstantValue &rhs) {
     return lhs == rhs ? lhs : ConstantValue();
   }
 

 class SparseConstantPropagation
     : public SparseDataFlowAnalysis<Lattice<ConstantValue>> {
 public:
   using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
 
   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

 /// lattice is propagated through the IR by dense data-flow analysis.
 class AbstractDenseLattice : public AnalysisState {
 public:
   /// A dense lattice can only be created for operations and blocks.
   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;
 };
 
 //===----------------------------------------------------------------------===//
 // AbstractDenseDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
 /// Base class for dense data-flow analyses. Dense data-flow analysis attaches a
 /// lattice between the execution of operations and implements a transfer
protected:
   /// Get the dense lattice after the execution of the given program point.
   virtual AbstractDenseLattice *getLattice(ProgramPoint point) = 0;
 
   /// Get the dense lattice after the execution of the given program point and
   /// add it as a dependency to a program point.
   const AbstractDenseLattice *getLatticeFor(ProgramPoint dependent,
                                             ProgramPoint point);
 
-  /// Mark the dense lattice as having reached its pessimistic fixpoint and
-  /// propagate an update if it changed.
-  void reset(AbstractDenseLattice *lattice) {
-    propagateIfChanged(lattice, lattice->reset());
-  }
+  /// Set the dense lattice at control flow entry point and propagate an update
+  /// if it changed.
+  virtual void setToEntryState(AbstractDenseLattice *lattice) = 0;
 
   /// Join a lattice with another and propagate an update if it changed.
   void join(AbstractDenseLattice *lhs, const AbstractDenseLattice &rhs) {
     propagateIfChanged(lhs, lhs->join(rhs));
   }
 
 private:
   /// Visit an operation. If this is a call operation or region control-flow
virtual void visitOperation(Operation *op, const LatticeT &before,
                               LatticeT *after) = 0;
 
 protected:
   /// Get the dense lattice after this program point.
   LatticeT *getLattice(ProgramPoint point) override {
     return getOrCreate<LatticeT>(point);
   }
 
+  /// Set the dense lattice at control flow entry point and propagate an update
+  /// if it changed.
+  virtual void setToEntryState(LatticeT *lattice) = 0;
+  void setToEntryState(AbstractDenseLattice *lattice) override {
+    setToEntryState(static_cast<LatticeT *>(lattice));
+  }
+
 private:
   /// Type-erased wrappers that convert the abstract dense lattice to a derived
   /// lattice and invoke the virtual hooks operating on the derived lattice.
   void visitOperationImpl(Operation *op, const AbstractDenseLattice &before,
                           AbstractDenseLattice *after) override {
     visitOperation(op, static_cast<const LatticeT &>(before),
                    static_cast<LatticeT *>(after));
   }
 };
 
 } // end namespace dataflow
 } // end namespace mlir
 
 #endif // MLIR_ANALYSIS_DENSEDATAFLOWANALYSIS_H

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

 namespace dataflow {
 
 /// This lattice value represents the integer range of an SSA value.
 class IntegerValueRange {
 public:
   /// Create a maximal range ([0, uint_max(t)] / [int_min(t), int_max(t)])
   /// range that is used to mark the value as unable to be analyzed further,
   /// where `t` is the type of `value`.
-  static IntegerValueRange getPessimisticValueState(Value value);
+  static IntegerValueRange getMaxRange(Value value);
 
   /// Create an integer value range lattice value.
   IntegerValueRange(ConstantIntRanges value) : value(std::move(value)) {}
 
   /// Get the known integer value range.
   const ConstantIntRanges &getValue() const { return value; }
 
   /// Compare two ranges.

 /// 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:
   using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
 
+  /// 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
   /// implements `InferIntRangeInterface`.
   void visitOperation(Operation *op,
                       ArrayRef<const IntegerValueRangeLattice *> operands,
                       ArrayRef<IntegerValueRangeLattice *> results) override;
 
   /// Visit block arguments or operation results of an operation with region
   /// control-flow for which values are not defined by region control-flow. This

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

 /// This class represents an abstract lattice. A lattice contains information
 /// about an SSA value and is what's propagated across the IR by sparse
 /// data-flow analysis.
 class AbstractSparseLattice : public AnalysisState {
 public:
   /// Lattices can only be created for values.
   AbstractSparseLattice(Value value) : AnalysisState(value) {}
 
+  /// Return the program point this lattice is located at.
+  Value getPoint() const { return AnalysisState::getPoint().get<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;
 
-  /// 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;
 
   /// Subscribe an analysis to updates of the lattice. When the lattice changes,
   /// subscribed analyses are re-invoked on all users of the value. This is
   /// more efficient than relying on the dependency map.
   void useDefSubscribe(DataFlowAnalysis *analysis) {

 ///   * static ValueT join(const ValueT &lhs, const ValueT &rhs);
 ///     - This method conservatively joins the information held by `lhs`
 ///       and `rhs` into a new value. This method is required to be monotonic.
 ///   * bool operator==(const ValueT &rhs) const;
 ///
 template <typename ValueT>
 class Lattice : public AbstractSparseLattice {
 public:
-  /// Construct a lattice with a known value.
-  explicit Lattice(Value value)
-      : AbstractSparseLattice(value),
-        knownValue(ValueT::getPessimisticValueState(value)) {}
+  using AbstractSparseLattice::AbstractSparseLattice;
+
+  /// Return the program point this lattice is located at.
+  Value getPoint() const { return point.get<Value>(); }
 
   /// Return the value held by this lattice. This requires that the value is
   /// initialized.
   ValueT &getValue() {
     assert(!isUninitialized() && "expected known lattice element");
-    return *optimisticValue;
+    return *value;
   }
   const ValueT &getValue() const {
     return const_cast<Lattice<ValueT> *>(this)->getValue();
   }
 
   /// Returns true if the value of this lattice hasn't yet been initialized.
-  bool isUninitialized() const override { return !optimisticValue.has_value(); }
+  bool isUninitialized() const override { return !value.has_value(); }
 
   /// 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 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) {
     // If the current lattice is uninitialized, copy the rhs value.
     if (isUninitialized()) {
-      optimisticValue = rhs;
+      value = rhs;
       return ChangeResult::Change;
     }
 
     // Otherwise, join rhs with the current optimistic value.
-    ValueT newValue = ValueT::join(*optimisticValue, rhs);
-    assert(ValueT::join(newValue, *optimisticValue) == newValue &&
+    ValueT newValue = ValueT::join(*value, rhs);
+    assert(ValueT::join(newValue, *value) == newValue &&
            "expected `join` to be monotonic");
     assert(ValueT::join(newValue, rhs) == newValue &&
            "expected `join` to be monotonic");
 
     // Update the current optimistic value if something changed.
-    if (newValue == optimisticValue)
+    if (newValue == value)
       return ChangeResult::NoChange;
 
-    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 (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;
+    value = newValue;
     return ChangeResult::Change;
   }
 
   /// Print the lattice element.
   void print(raw_ostream &os) const override {
-    os << "[";
-    knownValue.print(os);
-    os << ", ";
-    if (optimisticValue)
-      optimisticValue->print(os);
+    if (value)
+      value->print(os);
     else
       os << "<NULL>";
-    os << "]";
   }
 
 private:
-  /// The value that is conservatively known to be true.
-  ValueT knownValue;
   /// The currently computed value that is optimistically assumed to be true,
   /// or None if the lattice element is uninitialized.
-  Optional<ValueT> optimisticValue;
+  Optional<ValueT> value;
 };
 
 //===----------------------------------------------------------------------===//
 // AbstractSparseDataFlowAnalysis
 //===----------------------------------------------------------------------===//
 
 /// Base class for sparse (forward) data-flow analyses. A sparse analysis
 /// implements a transfer function on operations from the lattices of the
protected:
   /// Get the lattice element of a value.
   virtual AbstractSparseLattice *getLatticeElement(Value value) = 0;
 
   /// Get a read-only lattice element for a value and add it as a dependency to
   /// a program point.
   const AbstractSparseLattice *getLatticeElementFor(ProgramPoint point,
                                                     Value value);
 
-  /// Mark the given lattice elements as having reached their pessimistic
-  /// fixpoints and propagate an update if any changed.
-  void markAllPessimisticFixpoint(ArrayRef<AbstractSparseLattice *> lattices);
+  /// Set the given lattice element(s) at control flow entry point(s).
+  virtual void setToEntryState(AbstractSparseLattice *lattice) = 0;
+  void setAllToEntryStates(ArrayRef<AbstractSparseLattice *> lattices);
 
   /// Join the lattice element and propagate and update if it changed.
   void join(AbstractSparseLattice *lhs, const AbstractSparseLattice &rhs);
 
 private:
   /// Recursively initialize the analysis on nested operations and blocks.
   LogicalResult initializeRecursively(Operation *op);
 
public:
   /// arguments that are not accounted for by the branching control flow (ex.
   /// the bounds of loops). By default, this method marks all such lattice
   /// elements as having reached a pessimistic fixpoint. `firstIndex` is the
   /// index of the first element of `argLattices` that is set by control-flow.
   virtual void visitNonControlFlowArguments(Operation *op,
                                             const RegionSuccessor &successor,
                                             ArrayRef<StateT *> argLattices,
                                             unsigned firstIndex) {
-    markAllPessimisticFixpoint(argLattices.take_front(firstIndex));
-    markAllPessimisticFixpoint(argLattices.drop_front(
+    setAllToEntryStates(argLattices.take_front(firstIndex));
+    setAllToEntryStates(argLattices.drop_front(
         firstIndex + successor.getSuccessorInputs().size()));
   }
 
 protected:
   /// Get the lattice element for a value.
   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));
   }
 
-  /// Mark the lattice elements of a range of values as having reached their
-  /// pessimistic fixpoint.
-  void markAllPessimisticFixpoint(ArrayRef<StateT *> lattices) {
-    AbstractSparseDataFlowAnalysis::markAllPessimisticFixpoint(
+  /// 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(
         {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(
void visitNonControlFlowArgumentsImpl(
       ArrayRef<AbstractSparseLattice *> argLattices,
       unsigned firstIndex) override {
     visitNonControlFlowArguments(
         op, successor,
         {reinterpret_cast<StateT *const *>(argLattices.begin()),
          argLattices.size()},
         firstIndex);
   }
+  void setToEntryState(AbstractSparseLattice *lattice) override {
+    return setToEntryState(reinterpret_cast<StateT *>(lattice));
+  }
 };
 
 } // end namespace dataflow
 } // end namespace mlir
 
 #endif // MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H

mlir/include/mlir/Analysis/DataFlowFramework.h

 ///    default value.
 class AnalysisState {
 public:
   virtual ~AnalysisState();
 
   /// Create the analysis state at the given program point.
   AnalysisState(ProgramPoint point) : point(point) {}
 
+  /// Returns the program point this static is located at.
+  ProgramPoint getPoint() const { return point; }
+
   /// Returns true if the analysis state is uninitialized.
   virtual bool isUninitialized() const = 0;
 
   /// Print the contents of the analysis state.
   virtual void print(raw_ostream &os) const = 0;
 
 protected:
   /// This function is called by the solver when the analysis state is updated

mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp

void SparseConstantPropagation::visitOperation(
     ArrayRef<Lattice<ConstantValue> *> results) {
   LLVM_DEBUG(llvm::dbgs() << "SCP: Visiting operation: " << *op << "\n");
 
   // Don't try to simulate the results of a region operation as we can't
   // guarantee that folding will be out-of-place. We don't allow in-place
   // folds as the desire here is for simulated execution, and not general
   // folding.
   if (op->getNumRegions()) {
-    markAllPessimisticFixpoint(results);
+    setAllToEntryStates(results);
     return;
   }
 
   SmallVector<Attribute, 8> constantOperands;
   constantOperands.reserve(op->getNumOperands());
   for (auto *operandLattice : operands)
     constantOperands.push_back(operandLattice->getValue().getConstantValue());
 
   // Save the original operands and attributes just in case the operation
   // folds in-place. The constant passed in may not correspond to the real
   // runtime value, so in-place updates are not allowed.
   SmallVector<Value, 8> originalOperands(op->getOperands());
   DictionaryAttr originalAttrs = op->getAttrDictionary();
 
   // Simulate the result of folding this operation to a constant. If folding
   // fails or was an in-place fold, mark the results as overdefined.
   SmallVector<OpFoldResult, 8> foldResults;
   foldResults.reserve(op->getNumResults());
   if (failed(op->fold(constantOperands, foldResults))) {
-    markAllPessimisticFixpoint(results);
+    setAllToEntryStates(results);
     return;
   }
 
   // If the folding was in-place, mark the results as overdefined and reset
   // the operation. We don't allow in-place folds as the desire here is for
   // simulated execution, and not general folding.
   if (foldResults.empty()) {
     op->setOperands(originalOperands);
     op->setAttrs(originalAttrs);
-    markAllPessimisticFixpoint(results);
+    setAllToEntryStates(results);
     return;
   }
 
   // Merge the fold results into the lattice for this operation.
   assert(foldResults.size() == op->getNumResults() && "invalid result size");
   for (const auto it : llvm::zip(results, foldResults)) {
     Lattice<ConstantValue> *lattice = std::get<0>(it);
 
     // Merge in the result of the fold, either a constant or a value.
     OpFoldResult foldResult = std::get<1>(it);
     if (Attribute attr = foldResult.dyn_cast<Attribute>()) {
       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(
           lattice, *getLatticeElement(foldResult.get<Value>()));
     }
   }
 }
+
+void SparseConstantPropagation::setToEntryState(
+    Lattice<ConstantValue> *lattice) {
+  propagateIfChanged(lattice,
+                     lattice->join(ConstantValue::getUnknownConstant()));
+}

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

void AbstractDenseDataFlowAnalysis::visitOperation(Operation *op) {
 
   // If this is a call operation, then join its lattices across known return
   // sites.
   if (auto call = dyn_cast<CallOpInterface>(op)) {
     const auto *predecessors = getOrCreateFor<PredecessorState>(op, call);
     // If not all return sites are known, then conservatively assume we can't
     // reason about the data-flow.
     if (!predecessors->allPredecessorsKnown())
-      return reset(after);
+      return setToEntryState(after);
     for (Operation *predecessor : predecessors->getKnownPredecessors())
       join(after, *getLatticeFor(op, predecessor));
     return;
   }
 
   // Get the dense state before the execution of the op.
   const AbstractDenseLattice *before;
   if (Operation *prev = op->getPrevNode())
void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) {
   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);
       // If not all callsites are known, conservatively mark all lattices as
       // having reached their pessimistic fixpoints.
       if (!callsites->allPredecessorsKnown())
-        return reset(after);
+        return setToEntryState(after);
       for (Operation *callsite : callsites->getKnownPredecessors()) {
         // Get the dense lattice before the callsite.
         if (Operation *prev = callsite->getPrevNode())
           join(after, *getLatticeFor(block, prev));
         else
           join(after, *getLatticeFor(block, callsite->getBlock()));
       }
       return;
     }
 
     // Check if we can reason about the control-flow.
     if (auto branch = dyn_cast<RegionBranchOpInterface>(block->getParentOp()))
       return visitRegionBranchOperation(block, branch, after);
 
     // Otherwise, we can't reason about the data-flow.
-    return reset(after);
+    return setToEntryState(after);
   }
 
   // Join the state with the state after the block's predecessors.
   for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
        it != e; ++it) {
     // Skip control edges that aren't executable.
     Block *predecessor = *it;
     if (!getOrCreateFor<Executable>(

mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp

 #include "mlir/Interfaces/LoopLikeInterface.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "int-range-analysis"
 
 using namespace mlir;
 using namespace mlir::dataflow;
 
-IntegerValueRange IntegerValueRange::getPessimisticValueState(Value value) {
+IntegerValueRange IntegerValueRange::getMaxRange(Value value) {
   unsigned width = ConstantIntRanges::getStorageBitwidth(value.getType());
   APInt umin = APInt::getMinValue(width);
   APInt umax = APInt::getMaxValue(width);
   APInt smin = width != 0 ? APInt::getSignedMinValue(width) : umin;
   APInt smax = width != 0 ? APInt::getSignedMaxValue(width) : umax;
   return {{umin, umax, smin, smax}};
 }
 
 void IntegerValueRangeLattice::onUpdate(DataFlowSolver *solver) const {
   Lattice::onUpdate(solver);
 
   // If the integer range can be narrowed to a constant, update the constant
   // value of the SSA value.
   Optional<APInt> constant = getValue().getValue().getConstantValue();
   auto value = point.get<Value>();
   auto *cv = solver->getOrCreateState<Lattice<ConstantValue>>(value);
   if (!constant)
-    return solver->propagateIfChanged(cv, cv->markPessimisticFixpoint());
+    return solver->propagateIfChanged(
+        cv, cv->join(ConstantValue::getUnknownConstant()));
 
   Dialect *dialect;
   if (auto *parent = value.getDefiningOp())
     dialect = parent->getDialect();
   else
     dialect = value.getParentBlock()->getParentOp()->getDialect();
   solver->propagateIfChanged(
       cv, cv->join(ConstantValue(IntegerAttr::get(value.getType(), *constant),
                                  dialect)));
 }
 
 void IntegerRangeAnalysis::visitOperation(
     Operation *op, ArrayRef<const IntegerValueRangeLattice *> operands,
     ArrayRef<IntegerValueRangeLattice *> results) {
   // Ignore non-integer outputs - return early if the op has no scalar
   // integer results
   bool hasIntegerResult = false;
   for (auto it : llvm::zip(results, op->getResults())) {
-    if (std::get<1>(it).getType().isIntOrIndex()) {
+    Value value = std::get<1>(it);
+    if (value.getType().isIntOrIndex()) {
       hasIntegerResult = true;
     } else {
-      propagateIfChanged(std::get<0>(it),
-                         std::get<0>(it)->markPessimisticFixpoint());
+      IntegerValueRangeLattice *lattice = std::get<0>(it);
+      propagateIfChanged(lattice,
+                         lattice->join(IntegerValueRange::getMaxRange(value)));
     }
   }
   if (!hasIntegerResult)
     return;
 
   auto inferrable = dyn_cast<InferIntRangeInterface>(op);
   if (!inferrable)
-    return markAllPessimisticFixpoint(results);
+    return setAllToEntryStates(results);
 
   LLVM_DEBUG(llvm::dbgs() << "Inferring ranges for " << *op << "\n");
   SmallVector<ConstantIntRanges> argRanges(
       llvm::map_range(operands, [](const IntegerValueRangeLattice *val) {
         return val->getValue().getValue();
       }));
 
   auto joinCallback = [&](Value v, const ConstantIntRanges &attrs) {
auto joinCallback = [&](Value v, const ConstantIntRanges &attrs) {
     // the dataflow analysis in MLIR doesn't attempt to work out trip counts
     // and often can't).
     bool isYieldedResult = llvm::any_of(v.getUsers(), [](Operation *op) {
       return op->hasTrait<OpTrait::IsTerminator>();
     });
     if (isYieldedResult && oldRange.has_value() &&
         !(lattice->getValue() == *oldRange)) {
       LLVM_DEBUG(llvm::dbgs() << "Loop variant loop result detected\n");
-      changed |= lattice->markPessimisticFixpoint();
+      changed |= lattice->join(IntegerValueRange::getMaxRange(v));
     }
     propagateIfChanged(lattice, changed);
   };
 
   inferrable.inferResultRanges(argRanges, joinCallback);
 }
 
 void IntegerRangeAnalysis::visitNonControlFlowArguments(
auto joinCallback = [&](Value v, const ConstantIntRanges &attrs) {
       // them [-inf, inf] so we don't circle around infinitely often (because
       // the dataflow analysis in MLIR doesn't attempt to work out trip counts
       // and often can't).
       bool isYieldedValue = llvm::any_of(v.getUsers(), [](Operation *op) {
         return op->hasTrait<OpTrait::IsTerminator>();
       });
       if (isYieldedValue && oldRange && !(lattice->getValue() == *oldRange)) {
         LLVM_DEBUG(llvm::dbgs() << "Loop variant loop result detected\n");
-        changed |= lattice->markPessimisticFixpoint();
+        changed |= lattice->join(IntegerValueRange::getMaxRange(v));
       }
       propagateIfChanged(lattice, changed);
     };
 
     inferrable.inferResultRanges(argRanges, joinCallback);
     return;
   }
 

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp

 
 LogicalResult AbstractSparseDataFlowAnalysis::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())
-      markAllPessimisticFixpoint(getLatticeElement(argument));
+      setAllToEntryStates(getLatticeElement(argument));
   }
 
   return initializeRecursively(top);
 }
 
 LogicalResult
 AbstractSparseDataFlowAnalysis::initializeRecursively(Operation *op) {
   // Initialize the analysis by visiting every owner of an SSA value (all
void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) {
   }
 
   // The results of a call operation are determined by the callgraph.
   if (auto call = dyn_cast<CallOpInterface>(op)) {
     const auto *predecessors = getOrCreateFor<PredecessorState>(op, call);
     // If not all return sites are known, then conservatively assume we can't
     // reason about the data-flow.
     if (!predecessors->allPredecessorsKnown())
-      return markAllPessimisticFixpoint(resultLattices);
+      return setAllToEntryStates(resultLattices);
     for (Operation *predecessor : predecessors->getKnownPredecessors())
       for (auto it : llvm::zip(predecessor->getOperands(), resultLattices))
         join(std::get<1>(it), *getLatticeElementFor(op, std::get<0>(it)));
     return;
   }
 
   // Grab the lattice elements of the operands.
   SmallVector<const AbstractSparseLattice *> operandLattices;
void AbstractSparseDataFlowAnalysis::visitBlock(Block *block) {
   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);
       // If not all callsites are known, conservatively mark all lattices as
       // having reached their pessimistic fixpoints.
       if (!callsites->allPredecessorsKnown())
-        return markAllPessimisticFixpoint(argLattices);
+        return setAllToEntryStates(argLattices);
       for (Operation *callsite : callsites->getKnownPredecessors()) {
         auto call = cast<CallOpInterface>(callsite);
         for (auto it : llvm::zip(call.getArgOperands(), argLattices))
           join(std::get<1>(it), *getLatticeElementFor(block, std::get<0>(it)));
       }
       return;
     }
 
for (Block::pred_iterator it = block->pred_begin(), e = block->pred_end();
     if (auto branch =
             dyn_cast<BranchOpInterface>(predecessor->getTerminator())) {
       SuccessorOperands operands =
           branch.getSuccessorOperands(it.getSuccessorIndex());
       for (auto &it : llvm::enumerate(argLattices)) {
         if (Value operand = operands[it.index()]) {
           join(it.value(), *getLatticeElementFor(block, operand));
         } else {
-          // Conservatively mark internally produced arguments as having reached
-          // their pessimistic fixpoint.
-          markAllPessimisticFixpoint(it.value());
+          // Conservatively consider internally produced arguments as entry
+          // points.
+          setAllToEntryStates(it.value());
         }
       }
     } else {
-      return markAllPessimisticFixpoint(argLattices);
+      return setAllToEntryStates(argLattices);
     }
   }
 }
 
 void AbstractSparseDataFlowAnalysis::visitRegionSuccessors(
     ProgramPoint point, RegionBranchOpInterface branch,
     Optional<unsigned> successorIndex,
     ArrayRef<AbstractSparseLattice *> lattices) {
if (op == branch) {
       // Otherwise, try to deduce the operands from a region return-like op.
     } else {
       if (isRegionReturnLike(op))
         operands = getRegionBranchSuccessorOperands(op, successorIndex);
     }
 
     if (!operands) {
       // We can't reason about the data-flow.
-      return markAllPessimisticFixpoint(lattices);
+      return setAllToEntryStates(lattices);
     }
 
     ValueRange inputs = predecessors->getSuccessorInputs(op);
     assert(inputs.size() == operands->size() &&
            "expected the same number of successor inputs as operands");
 
     unsigned firstIndex = 0;
     if (inputs.size() != lattices.size()) {

 const AbstractSparseLattice *
 AbstractSparseDataFlowAnalysis::getLatticeElementFor(ProgramPoint point,
                                                      Value value) {
   AbstractSparseLattice *state = getLatticeElement(value);
   addDependency(state, point);
   return state;
 }
 
-void AbstractSparseDataFlowAnalysis::markAllPessimisticFixpoint(
+void AbstractSparseDataFlowAnalysis::setAllToEntryStates(
     ArrayRef<AbstractSparseLattice *> lattices) {
   for (AbstractSparseLattice *lattice : lattices)
-    propagateIfChanged(lattice, lattice->markPessimisticFixpoint());
+    setToEntryState(lattice);
 }
 
 void AbstractSparseDataFlowAnalysis::join(AbstractSparseLattice *lhs,
                                           const AbstractSparseLattice &rhs) {
   propagateIfChanged(lhs, lhs->join(rhs));
 }

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

LogicalResult visit(ProgramPoint point) override {
     Operation *op = point.get<Operation *>();
     Attribute value;
     if (matchPattern(op, m_Constant(&value))) {
       auto *constant = getOrCreate<Lattice<ConstantValue>>(op->getResult(0));
       propagateIfChanged(
           constant, constant->join(ConstantValue(value, op->getDialect())));
       return success();
     }
-    markAllPessimisticFixpoint(op->getResults());
+    setAllToUnknownConstants(op->getResults());
     for (Region &region : op->getRegions())
-      markAllPessimisticFixpoint(region.getArguments());
+      setAllToUnknownConstants(region.getArguments());
     return success();
   }
 
-  /// Mark the constant values of all given values as having reached a
-  /// pessimistic fixpoint.
-  void markAllPessimisticFixpoint(ValueRange values) {
+  /// Set all given values as not constants.
+  void setAllToUnknownConstants(ValueRange values) {
     for (Value value : values) {
-      auto *constantValue = getOrCreate<Lattice<ConstantValue>>(value);
-      propagateIfChanged(constantValue,
-                         constantValue->markPessimisticFixpoint());
+      auto *constant = getOrCreate<Lattice<ConstantValue>>(value);
+      propagateIfChanged(constant,
+                         constant->join(ConstantValue::getUnknownConstant()));
     }
   }
 };
 
 /// This is a simple pass that runs dead code analysis with a constant value
 /// provider that only understands constant operations.
 struct TestDeadCodeAnalysisPass
     : public PassWrapper<TestDeadCodeAnalysisPass, OperationPass<>> {

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

 
 using namespace mlir;
 using namespace mlir::dataflow;
 
 namespace {
 /// This lattice represents a single underlying value for an SSA value.
 class UnderlyingValue {
 public:
-  /// The pessimistic underlying value of a value is itself.
-  static UnderlyingValue getPessimisticValueState(Value value) {
-    return {value};
-  }
-
   /// Create an underlying value state with a known underlying value.
-  UnderlyingValue(Value underlyingValue = {})
-      : underlyingValue(underlyingValue) {}
+  UnderlyingValue(Value underlyingValue) : underlyingValue(underlyingValue) {}
 
   /// Returns the underlying value.
   Value getUnderlyingValue() const { return underlyingValue; }
 
   /// Join two underlying values. If there are conflicting underlying values,
   /// go to the pessimistic value.
   static UnderlyingValue join(const UnderlyingValue &lhs,
                               const UnderlyingValue &rhs) {
-    return lhs.underlyingValue == rhs.underlyingValue ? lhs : UnderlyingValue();
+    return lhs.underlyingValue == rhs.underlyingValue ? lhs : Value();
   }
 
   /// Compare underlying values.
   bool operator==(const UnderlyingValue &rhs) const {
     return underlyingValue == rhs.underlyingValue;
   }
 
   void print(raw_ostream &os) const { os << underlyingValue; }
 
 private:
   Value underlyingValue;
 };
 
 /// This lattice represents, for a given memory resource, the potential last
 /// operations that modified the resource.
 class LastModification : public AbstractDenseLattice {
 public:
   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(LastModification)
 
   using AbstractDenseLattice::AbstractDenseLattice;
 
   /// The lattice is always initialized.
   bool isUninitialized() const override { return false; }
 
-  /// Mark the lattice as having reached its pessimistic fixpoint. That is, the
-  /// last modifications of all memory resources are unknown.
-  ChangeResult reset() override {
+  /// Clear all modifications.
+  ChangeResult reset() {
     if (lastMods.empty())
       return ChangeResult::NoChange;
     lastMods.clear();
     return ChangeResult::Change;
   }
 
   /// Join the last modifications.
   ChangeResult join(const AbstractDenseLattice &lattice) override {
public:
   using DenseDataFlowAnalysis::DenseDataFlowAnalysis;
 
   /// 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;
+
+  /// At an entry point, the last modifications of all memory resources are
+  /// unknown.
+  void setToEntryState(LastModification *lattice) override {
+    propagateIfChanged(lattice, lattice->reset());
+  }
 };
 
 /// Define the lattice class explicitly to provide a type ID.
 struct UnderlyingValueLattice : public Lattice<UnderlyingValue> {
   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(UnderlyingValueLattice)
   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:
   using SparseDataFlowAnalysis::SparseDataFlowAnalysis;
 
   /// The underlying value of the results of an operation are not known.
   void visitOperation(Operation *op,
                       ArrayRef<const UnderlyingValueLattice *> operands,
                       ArrayRef<UnderlyingValueLattice *> results) override {
-    markAllPessimisticFixpoint(results);
+    setAllToEntryStates(results);
+  }
+
+  /// At an entry point, the underlying value of a value is itself.
+  void setToEntryState(UnderlyingValueLattice *lattice) override {
+    propagateIfChanged(lattice,
+                       lattice->join(UnderlyingValue{lattice->getPoint()}));
   }
 };
 } // end anonymous namespace
 
 /// Look for the most underlying value of a value.
 static Value getMostUnderlyingValue(
     Value value,
     function_ref<const UnderlyingValueLattice *(Value)> getUnderlyingValueFn) {

 
 void LastModifiedAnalysis::visitOperation(Operation *op,
                                           const LastModification &before,
                                           LastModification *after) {
   auto memory = dyn_cast<MemoryEffectOpInterface>(op);
   // If we can't reason about the memory effects, then conservatively assume we
   // can't deduce anything about the last modifications.
   if (!memory)
-    return reset(after);
+    return setToEntryState(after);
 
   SmallVector<MemoryEffects::EffectInstance> effects;
   memory.getEffects(effects);
 
   ChangeResult result = after->join(before);
   for (const auto &effect : effects) {
     Value value = effect.getValue();
 
     // If we see an effect on anything other than a value, assume we can't
     // deduce anything about the last modifications.
     if (!value)
-      return reset(after);
+      return setToEntryState(after);
 
     value = getMostUnderlyingValue(value, [&](Value value) {
       return getOrCreateFor<UnderlyingValueLattice>(op, value);
     });
     if (!value)
       return;
 
     // Nothing to do for reads.