From 47bf3e3812bc0e718b345857959333497cd12230 Mon Sep 17 00:00:00 2001 From: Zhixun Tan Date: Thu, 8 Sep 2022 08:43:47 -0700 Subject: [PATCH] [mlir][dataflow] Remove Lattice::isUninitialized(). Currently, for sparse analyses, we always store a `Optional` 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 Reviewed By: Mogball Differential Revision: https://reviews.llvm.org/D132800 --- .../DataFlow/ConstantPropagationAnalysis.h | 42 +++++++++++++++++----- .../mlir/Analysis/DataFlow/DeadCodeAnalysis.h | 6 ---- .../mlir/Analysis/DataFlow/IntegerRangeAnalysis.h | 20 ++++++++--- .../mlir/Analysis/DataFlow/SparseAnalysis.h | 34 ++++-------------- mlir/include/mlir/Analysis/DataFlowFramework.h | 3 -- .../DataFlow/ConstantPropagationAnalysis.cpp | 17 ++++++--- mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp | 2 +- mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp | 3 -- .../lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp | 30 +++++++++------- mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp | 3 -- mlir/lib/Transforms/SCCP.cpp | 2 +- .../DataFlow/TestDenseDataFlowAnalysis.cpp | 26 +++++++++----- mlir/test/lib/Analysis/TestDataFlowFramework.cpp | 2 +- mlir/test/lib/Transforms/TestIntRangeInference.cpp | 2 +- 14 files changed, 107 insertions(+), 85 deletions(-) diff --git a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h index 0935d8b..6c2b830 100644 --- a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h @@ -28,15 +28,24 @@ namespace dataflow { /// 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 { @@ -46,21 +55,36 @@ public: /// 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 constant; + /// A dialect instance that can be used to materialize the constant. + Dialect *dialect = nullptr; }; //===----------------------------------------------------------------------===// diff --git a/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h index 99ee208..4c79783 100644 --- a/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h @@ -38,9 +38,6 @@ 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(); @@ -95,9 +92,6 @@ 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; diff --git a/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h index 4cacc57..c11d305 100644 --- a/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/IntegerRangeAnalysis.h @@ -30,10 +30,18 @@ public: static IntegerValueRange getMaxRange(Value value); /// Create an integer value range lattice value. - IntegerValueRange(ConstantIntRanges value) : value(std::move(value)) {} + IntegerValueRange(Optional 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 { @@ -43,7 +51,11 @@ public: /// 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. @@ -51,7 +63,7 @@ public: private: /// The known integer value range. - ConstantIntRanges value; + Optional value; }; /// This lattice element represents the integer value range of an SSA value. diff --git a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h index dc4dd09..62d32b2 100644 --- a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h @@ -81,27 +81,17 @@ public: /// 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 *>(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 &rhsLattice = static_cast &>(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()); } @@ -109,15 +99,9 @@ public: /// 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"); @@ -131,17 +115,11 @@ public: } /// Print the lattice element. - void print(raw_ostream &os) const override { - if (value) - value->print(os); - else - os << ""; - } + 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 value; + /// The currently computed value that is optimistically assumed to be true. + ValueT value; }; //===----------------------------------------------------------------------===// diff --git a/mlir/include/mlir/Analysis/DataFlowFramework.h b/mlir/include/mlir/Analysis/DataFlowFramework.h index e6805ed..7028117 100644 --- a/mlir/include/mlir/Analysis/DataFlowFramework.h +++ b/mlir/include/mlir/Analysis/DataFlowFramework.h @@ -291,9 +291,6 @@ public: /// 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; diff --git a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp index 839c55d..db25c23 100644 --- a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp @@ -20,9 +20,15 @@ using namespace mlir::dataflow; //===----------------------------------------------------------------------===// void ConstantValue::print(raw_ostream &os) const { - if (constant) - return constant.print(os); - os << ""; + if (isUninitialized()) { + os << ""; + return; + } + if (getConstantValue() == nullptr) { + os << ""; + return; + } + return getConstantValue().print(os); } //===----------------------------------------------------------------------===// @@ -45,8 +51,11 @@ void SparseConstantPropagation::visitOperation( SmallVector 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 diff --git a/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp index 0f7a00c..07c8ed9 100644 --- a/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp @@ -318,7 +318,7 @@ static Optional> getOperandValuesImpl( for (Value operand : op->getOperands()) { const Lattice *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()); } diff --git a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp index 55e1cb1..c7bc02c 100644 --- a/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp @@ -74,9 +74,6 @@ void AbstractDenseDataFlowAnalysis::visitOperation(Operation *op) { 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); diff --git a/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp b/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp index 316097d..533d88d 100644 --- a/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/IntegerRangeAnalysis.cpp @@ -29,7 +29,7 @@ IntegerValueRange IntegerValueRange::getMaxRange(Value value) { 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 { @@ -57,6 +57,13 @@ void IntegerValueRangeLattice::onUpdate(DataFlowSolver *solver) const { void IntegerRangeAnalysis::visitOperation( Operation *op, ArrayRef operands, ArrayRef 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; @@ -91,11 +98,9 @@ void IntegerRangeAnalysis::visitOperation( LLVM_DEBUG(llvm::dbgs() << "Inferred range " << attrs << "\n"); IntegerValueRangeLattice *lattice = results[result.getResultNumber()]; - Optional 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 @@ -104,8 +109,8 @@ void IntegerRangeAnalysis::visitOperation( bool isYieldedResult = llvm::any_of(v.getUsers(), [](Operation *op) { return op->hasTrait(); }); - 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)); } @@ -134,11 +139,9 @@ void IntegerRangeAnalysis::visitNonControlFlowArguments( LLVM_DEBUG(llvm::dbgs() << "Inferred range " << attrs << "\n"); IntegerValueRangeLattice *lattice = argLattices[arg.getArgNumber()]; - Optional 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 @@ -147,7 +150,8 @@ void IntegerRangeAnalysis::visitNonControlFlowArguments( bool isYieldedValue = llvm::any_of(v.getUsers(), [](Operation *op) { return op->hasTrait(); }); - 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)); } @@ -212,7 +216,7 @@ void IntegerRangeAnalysis::visitNonControlFlowArguments( IntegerValueRangeLattice *ivEntry = getLatticeElement(*iv); auto ivRange = ConstantIntRanges::fromSigned(min, max); - propagateIfChanged(ivEntry, ivEntry->join(ivRange)); + propagateIfChanged(ivEntry, ivEntry->join(IntegerValueRange{ivRange})); return; } diff --git a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp index b565b31..6bddb84 100644 --- a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp @@ -117,9 +117,6 @@ void AbstractSparseDataFlowAnalysis::visitOperation(Operation *op) { 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); } diff --git a/mlir/lib/Transforms/SCCP.cpp b/mlir/lib/Transforms/SCCP.cpp index 385ff25..b32173a 100644 --- a/mlir/lib/Transforms/SCCP.cpp +++ b/mlir/lib/Transforms/SCCP.cpp @@ -43,7 +43,7 @@ static LogicalResult replaceWithConstant(DataFlowSolver &solver, OpBuilder &builder, OperationFolder &folder, Value value) { auto *lattice = solver.lookupState>(value); - if (!lattice || lattice->isUninitialized()) + if (!lattice || lattice->getValue().isUninitialized()) return failure(); const ConstantValue &latticeValue = lattice->getValue(); if (!latticeValue.getConstantValue()) diff --git a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp index c9eec64..f21a2ed 100644 --- a/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp +++ b/mlir/test/lib/Analysis/DataFlow/TestDenseDataFlowAnalysis.cpp @@ -21,16 +21,29 @@ namespace { class UnderlyingValue { public: /// Create an underlying value state with a known underlying value. - UnderlyingValue(Value underlyingValue) : underlyingValue(underlyingValue) {} + explicit UnderlyingValue(Optional 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. @@ -41,7 +54,7 @@ public: void print(raw_ostream &os) const { os << underlyingValue; } private: - Value underlyingValue; + Optional underlyingValue; }; /// This lattice represents, for a given memory resource, the potential last @@ -52,9 +65,6 @@ public: using AbstractDenseLattice::AbstractDenseLattice; - /// The lattice is always initialized. - bool isUninitialized() const override { return false; } - /// Clear all modifications. ChangeResult reset() { if (lastMods.empty()) @@ -169,7 +179,7 @@ static Value getMostUnderlyingValue( 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) diff --git a/mlir/test/lib/Analysis/TestDataFlowFramework.cpp b/mlir/test/lib/Analysis/TestDataFlowFramework.cpp index 8241e38..38c3df0 100644 --- a/mlir/test/lib/Analysis/TestDataFlowFramework.cpp +++ b/mlir/test/lib/Analysis/TestDataFlowFramework.cpp @@ -21,7 +21,7 @@ public: 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 { diff --git a/mlir/test/lib/Transforms/TestIntRangeInference.cpp b/mlir/test/lib/Transforms/TestIntRangeInference.cpp index e13c070..85d3a76 100644 --- a/mlir/test/lib/Transforms/TestIntRangeInference.cpp +++ b/mlir/test/lib/Transforms/TestIntRangeInference.cpp @@ -25,7 +25,7 @@ static LogicalResult replaceWithConstant(DataFlowSolver &solver, OpBuilder &b, OperationFolder &folder, Value value) { auto *maybeInferredRange = solver.lookupState(value); - if (!maybeInferredRange || maybeInferredRange->isUninitialized()) + if (!maybeInferredRange || maybeInferredRange->getValue().isUninitialized()) return failure(); const ConstantIntRanges &inferredRange = maybeInferredRange->getValue().getValue(); -- 2.7.4