[mlir][dataflow] Remove Lattice::isUninitialized().

[phisiart]

Summary

Currently, for sparse analyses, we always store a Optional<ValueT> in each lattice element. When it's None, we consider the lattice element as uninitialized.

However:

• Not all lattices have an uninitialized state. For example, Executable and PredecessorState have default values so they are always initialized.

• In dense analyses, we don't have the concept of an uninitialized state.

Given these inconsistencies, this patch removes Lattice::isUninitialized(). Individual analysis states are now default-constructed. If the default state of an analysis can be considered as "uninitialized" then this analysis should implement the following logic:

• Special join rule: join(uninitialized, any) == any.

• Special bail out logic: if any of the input states is uninitialized, exit the transfer function early.

Depends On D132086

[phisiart]

Reformat.

[Mogball]

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

93

Can you replace Optional<Impl> with just an Attribute and a flag? Or at least do Optional<Attribute> since the dialect value doesn't place a role in the analysis very much.

[phisiart]

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

93

I feel like we cannot remove the dialect field here.

Looking at https://github.com/llvm/llvm-project/blob/67d0d7ac0acb0665d6a09f61278fbcf51f0114c2/mlir/lib/Transforms/SCCP.cpp#L54:

Value constant = folder.getOrCreateConstant(builder, dialect,
                                            latticeValue.getConstantValue(),
                                            value.getType(), value.getLoc());

SCCP uses the stored dialect to materializeConstant.

I tried to create a patch that removes dialect from ConstantPropagationAnalysis.h and re-computes the dialect in SCCP by looking at the getDefiningOp() of the current Value to be folded.

However, we cannot do this when the current Value is a block argument. Hence, this test case failed:

// CHECK-LABEL: func @simple_control_flow
func.func @simple_control_flow(%arg0 : i32) -> i32 {
  // CHECK: %[[CST:.*]] = arith.constant 1 : i32

  %cond = arith.constant true
  %1 = arith.constant 1 : i32
  cf.cond_br %cond, ^bb1, ^bb2(%arg0 : i32)

^bb1:
  cf.br ^bb2(%1 : i32)

^bb2(%arg : i32):
  // CHECK: ^bb2(%{{.*}}: i32):
  // CHECK: return %[[CST]] : i32

  return %arg : i32
}

In this test case, ConstantPropagationAnalysis is able to figure out that %arg is a constant, but we also need to know that the dialect is arith so that we can materializeConstant. However, the fact that the dialect is arith can only be propagated through the dataflow from the definition %1.

(Note: I created https://reviews.llvm.org/D133250 to demonstrate how I removed dialect.)

Therefore, I think that we still need to store dialect. Do you have another way of handling this?

[Mogball]

The dialect can either be metadata unrelated to the constant, like how it was before. Or you can do what integer range analysis does and materialize a constant block argument using the dialect of the parent op. I think that's the better approach anyways.

[rriddle]

In D132800#3768501, @Mogball wrote:

The dialect can either be metadata unrelated to the constant, like how it was before. Or you can do what integer range analysis does and materialize a constant block argument using the dialect of the parent op. I think that's the better approach anyways.

How does that work though? The func dialect won't be able to materialize an arith constant (or really any other constant). This also won't work for propagating constants through calls, given that the dialect of the call generally won't be able to materialize the constant either.

[Mogball]

Ugh that's true. Integer range inference (the test pass) is broken then. At least I wouldn't have the Impl struct and just have Optional<Attribute> with a Dialect * hanging around as metadata

[phisiart]

In D132800#3768503, @Mogball wrote:

Ugh that's true. Integer range inference (the test pass) is broken then. At least I wouldn't have the Impl struct and just have Optional<Attribute> with a Dialect * hanging around as metadata

I think that dialect is part of the state itself, instead of additional metadata.

1. dialect is only valid when the state is initialized. In other words, if we define ConstantValue as { Optional<Attribute> value; Dialect *dialect; }, then dialect is only valid when value is not None. So we might as well put them together under a single Optional.

2. dialect participates in the == comparison and join. Consider two ConstantValues with the same value but different dialects, they are still not equal (and thus joining them would still result in UnknownConstant()) because we don't know which dialect to use when materializing the attribute into an op. (Note that the current patch is incorrect - it doesn't compare the dialect.)

How about we change ConstantValue into { bool isInitialized; Attribute value; Dialect *dialect; }?

[phisiart]

Created https://reviews.llvm.org/D133260 for letting dialect participate in equality comparison. Will rebase this patch on top of that one.

[Mogball]

I don't necessarily agree that the dialect is part of the state. It doesn't make sense that a constant shouldn't be propagated even though it has a known value because the dialect of their source operations differ. Most dialects don't have their own constant operations and will end up sharing the same op in their constant materializer (e.g. arith.constant).

It doesn't make sense to me that the fold result of a math.absi should differ from that of an arith.addi if their attributes are the same but their dialects are different (both dialects use arith.constant).

Otherwise, you might end up in situation where sccp isn't idempotent because the first iteration bottoms out with unequal dialects, which both end up getting materialized as arith.constant, and then another iteration properly propagates the constants into another block, for example

[phisiart]

In D132800#3768799, @Mogball wrote:

It doesn't make sense to me that the fold result of a math.absi should differ from that of an arith.addi if their attributes are the same but their dialects are different (both dialects use arith.constant).

Oh I see, I had a misunderstanding previously.

• Previously I thought that if the input to math.absi is { constant = -1; dialect = arith; }, then the output is { constant = 1; dialect = arith; }. But actually it is { constant = 1; dialect = math; }.
• Previously I thought that if the input to math.absi is { constant = -1; dialect = my_own_dialect; }, then the output should be { constant = 1; dialect = my_own_dialect; }. But actually it is { constant = 1; dialect = math; }.
• Previously I thought that if the inputs to arith.addi are { constant = 1; dialect = my_own_dialect; } and { constant = 2; dialect = my_own_dialect; }, then the output is { constant = 3; dialect = my_own_dialect; }. But actually it is { constant = 3; dialect = arith; }.

Now it makes sense. Let me drop https://reviews.llvm.org/D133260 and change this patch then.

[phisiart]

Update the definition of ConstantValue into { Optional<Attribute> constant; Dialect *dialect; }.

[Mogball]

One last comment and LGTM

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

85–87

Can you default initialize this to nullptr so it doesn't have some garbage value?

[Mogball]

Thanks for all the improvements

[phisiart]

Initialize ConstantValue::dialect with nullptr.

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

 
 //===----------------------------------------------------------------------===//
 // ConstantValue
 //===----------------------------------------------------------------------===//
 
 /// This lattice value represents a known constant value of a lattice.
 class ConstantValue {
 public:
+  /// Construct a constant value as uninitialized.
+  explicit ConstantValue() = default;
+
   /// Construct a constant value with a known constant.
-  ConstantValue(Attribute knownValue = {}, Dialect *dialect = nullptr)
-      : constant(knownValue), dialect(dialect) {}
+  explicit ConstantValue(Attribute constant, Dialect *dialect)
+      : constant(constant), dialect(dialect) {}
 
   /// Get the constant value. Returns null if no value was determined.
-  Attribute getConstantValue() const { return constant; }
+  Attribute getConstantValue() const {
+    assert(!isUninitialized());
+    return *constant;
+  }
 
   /// Get the dialect instance that can be used to materialize the constant.
-  Dialect *getConstantDialect() const { return dialect; }
+  Dialect *getConstantDialect() const {
+    assert(!isUninitialized());
+    return dialect;
+  }
 
   /// 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 state where the constant value is uninitialized. This happens when the
+  /// state hasn't been set during the analysis.
+  static ConstantValue getUninitialized() { return ConstantValue{}; }
+
+  /// Whether the state is uninitialized.
+  bool isUninitialized() const { return !constant.has_value(); }
+
   /// The state where the constant value is unknown.
-  static ConstantValue getUnknownConstant() { return {}; }
+  static ConstantValue getUnknownConstant() {
+    return ConstantValue{/*constant=*/nullptr, /*dialect=*/nullptr};
+  }
 
   /// 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();
+    if (lhs.isUninitialized())
+      return rhs;
+    if (rhs.isUninitialized())
+      return lhs;
+    if (lhs == rhs)
+      return lhs;
+    return getUnknownConstant();
   }
 
 private:
   /// The constant value.
-  Attribute constant;
-  /// An dialect instance that can be used to materialize the constant.
-  Dialect *dialect;
+  Optional<Attribute> constant;
+  /// A dialect instance that can be used to materialize the constant.
+  Dialect *dialect = nullptr;
 };
 
 //===----------------------------------------------------------------------===//
 // SparseConstantPropagation
 //===----------------------------------------------------------------------===//
 
 /// This analysis implements sparse constant propagation, which attempts to
 /// determine constant-valued results for operations using constant-valued
 /// operands, by speculatively folding operations. When combined with dead-code
 /// analysis, this becomes sparse conditional constant propagation (SCCP).
 class SparseConstantPropagation
     : public SparseDataFlowAnalysis<Lattice<ConstantValue>> {
 public:
   using SparseDataFlowAnalysis::SparseDataFlowAnalysis;

mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h

 //===----------------------------------------------------------------------===//
 
 /// This is a simple analysis state that represents whether the associated
 /// program point (either a block or a control-flow edge) is live.
 class Executable : public AnalysisState {
 public:
   using AnalysisState::AnalysisState;
 
-  /// The state is initialized by default.
-  bool isUninitialized() const override { return false; }
-
   /// Set the state of the program point to live.
   ChangeResult setToLive();
 
   /// Get whether the program point is live.
   bool isLive() const { return live; }
 
   /// Print the liveness.
   void print(raw_ostream &os) const override;

 /// propagated from each predecessor to the successor point.
 ///
 /// The state can indicate that it is underdefined, meaning that not all live
 /// control-flow predecessors can be known.
 class PredecessorState : public AnalysisState {
 public:
   using AnalysisState::AnalysisState;
 
-  /// The state is initialized by default.
-  bool isUninitialized() const override { return false; }
-
   /// Print the known predecessors.
   void print(raw_ostream &os) const override;
 
   /// Returns true if all predecessors are known.
   bool allPredecessorsKnown() const { return allKnown; }
 
   /// Indicate that there are potentially unknown predecessors.
   ChangeResult setHasUnknownPredecessors() {

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

 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 getMaxRange(Value value);
 
   /// Create an integer value range lattice value.
-  IntegerValueRange(ConstantIntRanges value) : value(std::move(value)) {}
+  IntegerValueRange(Optional<ConstantIntRanges> value = None)
+      : value(std::move(value)) {}
+
+  /// Whether the range is uninitialized. This happens when the state hasn't
+  /// been set during the analysis.
+  bool isUninitialized() const { return !value.has_value(); }
 
   /// Get the known integer value range.
-  const ConstantIntRanges &getValue() const { return value; }
+  const ConstantIntRanges &getValue() const {
+    assert(!isUninitialized());
+    return *value;
+  }
 
   /// Compare two ranges.
   bool operator==(const IntegerValueRange &rhs) const {
     return value == rhs.value;
   }
 
   /// Take the union of two ranges.
   static IntegerValueRange join(const IntegerValueRange &lhs,
                                 const IntegerValueRange &rhs) {
-    return lhs.value.rangeUnion(rhs.value);
+    if (lhs.isUninitialized())
+      return rhs;
+    if (rhs.isUninitialized())
+      return lhs;
+    return IntegerValueRange{lhs.getValue().rangeUnion(rhs.getValue())};
   }
 
   /// Print the integer value range.
   void print(raw_ostream &os) const { os << value; }
 
 private:
   /// The known integer value range.
-  ConstantIntRanges value;
+  Optional<ConstantIntRanges> value;
 };
 
 /// This lattice element represents the integer value range of an SSA value.
 /// When this lattice is updated, it automatically updates the constant value
 /// of the SSA value (if the range can be narrowed to one).
 class IntegerValueRangeLattice : public Lattice<IntegerValueRange> {
 public:
   using Lattice::Lattice;

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

 public:
   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 *value;
-  }
+  ValueT &getValue() { 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 !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()) {
-      value = rhs;
-      return ChangeResult::Change;
-    }
-
     // Otherwise, join rhs with the current optimistic value.
-    ValueT newValue = ValueT::join(*value, rhs);
-    assert(ValueT::join(newValue, *value) == 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 == value)
       return ChangeResult::NoChange;
 
     value = newValue;
     return ChangeResult::Change;
   }
 
   /// Print the lattice element.
-  void print(raw_ostream &os) const override {
-    if (value)
-      value->print(os);
-    else
-      os << "<NULL>";
-  }
+  void print(raw_ostream &os) const override { value.print(os); }
 
 private:
-  /// The currently computed value that is optimistically assumed to be true,
-  /// or None if the lattice element is uninitialized.
-  Optional<ValueT> value;
+  /// The currently computed value that is optimistically assumed to be true.
+  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

mlir/include/mlir/Analysis/DataFlowFramework.h

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
   /// to optionally enqueue more work items. For example, if a state tracks
   /// dependents through the IR (e.g. use-def chains), this function can be
   /// implemented to push those dependents on the worklist.

mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp

 using namespace mlir;
 using namespace mlir::dataflow;
 
 //===----------------------------------------------------------------------===//
 // ConstantValue
 //===----------------------------------------------------------------------===//
 
 void ConstantValue::print(raw_ostream &os) const {
-  if (constant)
-    return constant.print(os);
-  os << "<NO VALUE>";
+  if (isUninitialized()) {
+    os << "<UNINITIALIZED>";
+    return;
+  }
+  if (getConstantValue() == nullptr) {
+    os << "<UNKNOWN>";
+    return;
+  }
+  return getConstantValue().print(os);
 }
 
 //===----------------------------------------------------------------------===//
 // SparseConstantPropagation
 //===----------------------------------------------------------------------===//
 
 void SparseConstantPropagation::visitOperation(
     Operation *op, ArrayRef<const Lattice<ConstantValue> *> operands,
     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()) {
     setAllToEntryStates(results);
     return;
   }
 
   SmallVector<Attribute, 8> constantOperands;
   constantOperands.reserve(op->getNumOperands());
-  for (auto *operandLattice : operands)
+  for (auto *operandLattice : operands) {
+    if (operandLattice->getValue().isUninitialized())
+      return;
     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

mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp

 static Optional<SmallVector<Attribute>> getOperandValuesImpl(
     Operation *op,
     function_ref<const Lattice<ConstantValue> *(Value)> getLattice) {
   SmallVector<Attribute> operands;
   operands.reserve(op->getNumOperands());
   for (Value operand : op->getOperands()) {
     const Lattice<ConstantValue> *cv = getLattice(operand);
     // If any of the operands' values are uninitialized, bail out.
-    if (cv->isUninitialized())
+    if (cv->getValue().isUninitialized())
       return {};
     operands.push_back(cv->getValue().getConstantValue());
   }
   return operands;
 }
 
 Optional<SmallVector<Attribute>>
 DeadCodeAnalysis::getOperandValues(Operation *op) {

mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp

void AbstractDenseDataFlowAnalysis::visitOperation(Operation *op) {
   }
 
   // Get the dense state before the execution of the op.
   const AbstractDenseLattice *before;
   if (Operation *prev = op->getPrevNode())
     before = getLatticeFor(op, prev);
   else
     before = getLatticeFor(op, op->getBlock());
-  // If the incoming lattice is uninitialized, bail out.
-  if (before->isUninitialized())
-    return;
 
   // Invoke the operation transfer function.
   visitOperationImpl(op, *before, after);
 }
 
 void AbstractDenseDataFlowAnalysis::visitBlock(Block *block) {
   // If the block is not executable, bail out.
   if (!getOrCreateFor<Executable>(block, block)->isLive())

mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp

 using namespace mlir::dataflow;
 
 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}};
+  return IntegerValueRange{ConstantIntRanges{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();
void IntegerValueRangeLattice::onUpdate(DataFlowSolver *solver) const {
   solver->propagateIfChanged(
       cv, cv->join(ConstantValue(IntegerAttr::get(value.getType(), *constant),
                                  dialect)));
 }
 
 void IntegerRangeAnalysis::visitOperation(
     Operation *op, ArrayRef<const IntegerValueRangeLattice *> operands,
     ArrayRef<IntegerValueRangeLattice *> results) {
+  // If the lattice on any operand is unitialized, bail out.
+  if (llvm::any_of(operands, [](const IntegerValueRangeLattice *lattice) {
+        return lattice->getValue().isUninitialized();
+      })) {
+    return;
+  }
+
   // 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())) {
     Value value = std::get<1>(it);
     if (value.getType().isIntOrIndex()) {
       hasIntegerResult = true;
     } else {
void IntegerRangeAnalysis::visitOperation(
   auto joinCallback = [&](Value v, const ConstantIntRanges &attrs) {
     auto result = v.dyn_cast<OpResult>();
     if (!result)
       return;
     assert(llvm::is_contained(op->getResults(), result));
 
     LLVM_DEBUG(llvm::dbgs() << "Inferred range " << attrs << "\n");
     IntegerValueRangeLattice *lattice = results[result.getResultNumber()];
-    Optional<IntegerValueRange> oldRange;
-    if (!lattice->isUninitialized())
-      oldRange = lattice->getValue();
+    IntegerValueRange oldRange = lattice->getValue();
 
-    ChangeResult changed = lattice->join(attrs);
+    ChangeResult changed = lattice->join(IntegerValueRange{attrs});
 
     // Catch loop results with loop variant bounds and conservatively make
     // 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 isYieldedResult = llvm::any_of(v.getUsers(), [](Operation *op) {
       return op->hasTrait<OpTrait::IsTerminator>();
     });
-    if (isYieldedResult && oldRange.has_value() &&
-        !(lattice->getValue() == *oldRange)) {
+    if (isYieldedResult && !oldRange.isUninitialized() &&
+        !(lattice->getValue() == oldRange)) {
       LLVM_DEBUG(llvm::dbgs() << "Loop variant loop result detected\n");
       changed |= lattice->join(IntegerValueRange::getMaxRange(v));
     }
     propagateIfChanged(lattice, changed);
   };
 
   inferrable.inferResultRanges(argRanges, joinCallback);
 }
auto joinCallback = [&](Value v, const ConstantIntRanges &attrs) {
       auto arg = v.dyn_cast<BlockArgument>();
       if (!arg)
         return;
       if (!llvm::is_contained(successor.getSuccessor()->getArguments(), arg))
         return;
 
       LLVM_DEBUG(llvm::dbgs() << "Inferred range " << attrs << "\n");
       IntegerValueRangeLattice *lattice = argLattices[arg.getArgNumber()];
-      Optional<IntegerValueRange> oldRange;
-      if (!lattice->isUninitialized())
-        oldRange = lattice->getValue();
+      IntegerValueRange oldRange = lattice->getValue();
 
-      ChangeResult changed = lattice->join(attrs);
+      ChangeResult changed = lattice->join(IntegerValueRange{attrs});
 
       // Catch loop results with loop variant bounds and conservatively make
       // 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)) {
+      if (isYieldedValue && !oldRange.isUninitialized() &&
+          !(lattice->getValue() == oldRange)) {
         LLVM_DEBUG(llvm::dbgs() << "Loop variant loop result detected\n");
         changed |= lattice->join(IntegerValueRange::getMaxRange(v));
       }
       propagateIfChanged(lattice, changed);
     };
 
     inferrable.inferResultRanges(argRanges, joinCallback);
     return;
if (auto loop = dyn_cast<LoopLikeOpInterface>(op)) {
     } else {
       // Correct the upper bound by subtracting 1 so that it becomes a <=
       // bound, because loops do not generally include their upper bound.
       max -= 1;
     }
 
     IntegerValueRangeLattice *ivEntry = getLatticeElement(*iv);
     auto ivRange = ConstantIntRanges::fromSigned(min, max);
-    propagateIfChanged(ivEntry, ivEntry->join(ivRange));
+    propagateIfChanged(ivEntry, ivEntry->join(IntegerValueRange{ivRange}));
     return;
   }
 
   return SparseDataFlowAnalysis::visitNonControlFlowArguments(
       op, successor, argLattices, firstIndex);
 }

mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp

void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) {
   }
 
   // Grab the lattice elements of the operands.
   SmallVector<const AbstractSparseLattice *> operandLattices;
   operandLattices.reserve(op->getNumOperands());
   for (Value operand : op->getOperands()) {
     AbstractSparseLattice *operandLattice = getLatticeElement(operand);
     operandLattice->useDefSubscribe(this);
-    // If any of the operand states are not initialized, bail out.
-    if (operandLattice->isUninitialized())
-      return;
     operandLattices.push_back(operandLattice);
   }
 
   // Invoke the operation transfer function.
   visitOperationImpl(op, operandLattices, resultLattices);
 }
 
 void AbstractSparseDataFlowAnalysis::visitBlock(Block *block) {

mlir/lib/Transforms/SCCP.cpp

 
 /// Replace the given value with a constant if the corresponding lattice
 /// represents a constant. Returns success if the value was replaced, failure
 /// otherwise.
 static LogicalResult replaceWithConstant(DataFlowSolver &solver,
                                          OpBuilder &builder,
                                          OperationFolder &folder, Value value) {
   auto *lattice = solver.lookupState<Lattice<ConstantValue>>(value);
-  if (!lattice || lattice->isUninitialized())
+  if (!lattice || lattice->getValue().isUninitialized())
     return failure();
   const ConstantValue &latticeValue = lattice->getValue();
   if (!latticeValue.getConstantValue())
     return failure();
 
   // Attempt to materialize a constant for the given value.
   Dialect *dialect = latticeValue.getConstantDialect();
   Value constant = folder.getOrCreateConstant(builder, dialect,

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:
   /// Create an underlying value state with a known underlying value.
-  UnderlyingValue(Value underlyingValue) : underlyingValue(underlyingValue) {}
+  explicit UnderlyingValue(Optional<Value> underlyingValue = None)
+      : underlyingValue(underlyingValue) {}
+
+  /// Whether the state is uninitialized.
+  bool isUninitialized() const { return !underlyingValue.has_value(); }
 
   /// Returns the underlying value.
-  Value getUnderlyingValue() const { return underlyingValue; }
+  Value getUnderlyingValue() const {
+    assert(!isUninitialized());
+    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 : Value();
+    if (lhs.isUninitialized())
+      return rhs;
+    if (rhs.isUninitialized())
+      return lhs;
+    return lhs.underlyingValue == rhs.underlyingValue
+               ? lhs
+               : UnderlyingValue(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;
+  Optional<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; }
-
   /// Clear all modifications.
   ChangeResult reset() {
     if (lastMods.empty())
       return ChangeResult::NoChange;
     lastMods.clear();
     return ChangeResult::Change;
   }
 

 
 /// Look for the most underlying value of a value.
 static Value getMostUnderlyingValue(
     Value value,
     function_ref<const UnderlyingValueLattice *(Value)> getUnderlyingValueFn) {
   const UnderlyingValueLattice *underlying;
   do {
     underlying = getUnderlyingValueFn(value);
-    if (!underlying || underlying->isUninitialized())
+    if (!underlying || underlying->getValue().isUninitialized())
       return {};
     Value underlyingValue = underlying->getValue().getUnderlyingValue();
     if (underlyingValue == value)
       break;
     value = underlyingValue;
   } while (true);
   return value;
 }

mlir/test/lib/Analysis/TestDataFlowFramework.cpp

 /// This analysis state represents an integer that is XOR'd with other states.
 class FooState : public AnalysisState {
 public:
   MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(FooState)
 
   using AnalysisState::AnalysisState;
 
   /// Returns true if the state is uninitialized.
-  bool isUninitialized() const override { return !state; }
+  bool isUninitialized() const { return !state; }
 
   /// Print the integer value or "none" if uninitialized.
   void print(raw_ostream &os) const override {
     if (state)
       os << *state;
     else
       os << "none";
   }

mlir/test/lib/Transforms/TestIntRangeInference.cpp

 using namespace mlir;
 using namespace mlir::dataflow;
 
 /// Patterned after SCCP
 static LogicalResult replaceWithConstant(DataFlowSolver &solver, OpBuilder &b,
                                          OperationFolder &folder, Value value) {
   auto *maybeInferredRange =
       solver.lookupState<IntegerValueRangeLattice>(value);
-  if (!maybeInferredRange || maybeInferredRange->isUninitialized())
+  if (!maybeInferredRange || maybeInferredRange->getValue().isUninitialized())
     return failure();
   const ConstantIntRanges &inferredRange =
       maybeInferredRange->getValue().getValue();
   Optional<APInt> maybeConstValue = inferredRange.getConstantValue();
   if (!maybeConstValue.has_value())
     return failure();
 
   Operation *maybeDefiningOp = value.getDefiningOp();