This is an archive of the discontinued LLVM Phabricator instance.

	//===- DataFlowAnalysis.h - General DataFlow Analysis Utilities -- C++ --===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// This file has several utilities and algorithms that perform abstract dataflow
	// analysis over the IR. These allow for users to hook into various analysis
	// propagation algorithms without needing to reinvent the traversal over the
	// different types of control structures present within MLIR, such as regions,
	// the callgraph, etc. A few of the main entry points are detailed below:
	//
	// FowardDataFlowAnalysis:
	// This class provides support for defining dataflow algorithms that are
	// forward, sparse, pessimistic (except along unreached backedges) and
	// context-insensitive for the interprocedural aspects.
	//
	//===----------------------------------------------------------------------===//

	#ifndef MLIR_ANALYSIS_DATAFLOWANALYSIS_H
	#define MLIR_ANALYSIS_DATAFLOWANALYSIS_H

	#include "mlir/Analysis/DataFlowFramework.h"
	#include "mlir/IR/Value.h"
	#include "mlir/Interfaces/ControlFlowInterfaces.h"
	#include "llvm/ADT/DenseMap.h"
	#include "llvm/ADT/Optional.h"
	#include "llvm/Support/Allocator.h"

	/// TODO: Remove this file when SCCP and integer range analysis have been ported
	/// to the new framework.

	namespace mlir {
	//===----------------------------------------------------------------------===//
	// AbstractLatticeElement
	//===----------------------------------------------------------------------===//

	namespace detail {
	/// This class represents an abstract lattice. A lattice is what gets propagated
	/// across the IR, and contains the information for a specific Value.
	class AbstractLatticeElement {
	public:
	virtual ~AbstractLatticeElement();

	/// Returns true if the value of this lattice is uninitialized, meaning that
	/// it hasn't yet been initialized.
	virtual bool isUninitialized() const = 0;

	/// Join the information contained in 'rhs' into this lattice. Returns
	/// if the value of the lattice changed.
	virtual ChangeResult join(const AbstractLatticeElement &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;

	/// Mark the lattice element as having reached an optimistic fixpoint. This
	/// means that we optimistically assume the current value is the true state.
	virtual void markOptimisticFixpoint() = 0;

	/// Returns true if the lattice has reached a fixpoint. A fixpoint is when the
	/// information optimistically assumed to be true is the same as the
	/// information known to be true.
	virtual bool isAtFixpoint() const = 0;
	};
	} // namespace detail

	//===----------------------------------------------------------------------===//
	// LatticeElement
	//===----------------------------------------------------------------------===//

	/// This class represents a lattice holding a specific value of type `ValueT`.
	/// Lattice values (`ValueT`) are required to adhere to the following:
	/// * 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.
	/// * static ValueT getPessimisticValueState(MLIRContext *context);
	/// - This method computes a pessimistic/conservative value state assuming
	/// no information about the state of the IR.
	/// * static ValueT getPessimisticValueState(Value value);
	/// - This method computes a pessimistic/conservative value state for
	/// `value` assuming only information present in the current IR.
	/// * bool operator==(const ValueT &rhs) const;
	///
	template <typename ValueT>
	class LatticeElement final : public detail::AbstractLatticeElement {
	public:
	LatticeElement() = delete;
	LatticeElement(const ValueT &knownValue) : knownValue(knownValue) {}

	/// Return the value held by this lattice. This requires that the value is
	/// initialized.
	ValueT &getValue() {
	assert(!isUninitialized() && "expected known lattice element");
	return *optimisticValue;
	}
	const ValueT &getValue() const {
	assert(!isUninitialized() && "expected known lattice element");
	return *optimisticValue;
	}

	/// Returns true if the value of this lattice hasn't yet been initialized.
	bool isUninitialized() const final { return !optimisticValue; }

	/// Join the information contained in the 'rhs' lattice into this
	/// lattice. Returns if the state of the current lattice changed.
	ChangeResult join(const detail::AbstractLatticeElement &rhs) final {
	const LatticeElement<ValueT> &rhsLattice =
	static_cast<const LatticeElement<ValueT> &>(rhs);

	// If we are at a fixpoint, or rhs is uninitialized, there is nothing to do.
	if (isAtFixpoint() \|\| 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;
	return ChangeResult::Change;
	}

	// Otherwise, join rhs with the current optimistic value.
	ValueT newValue = ValueT::join(*optimisticValue, rhs);
	assert(ValueT::join(newValue, *optimisticValue) == 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)
	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() final {
	if (isAtFixpoint())
	return ChangeResult::NoChange;

	// For this fixed point, we take whatever we knew to be true and set that to
	// our optimistic value.
	optimisticValue = knownValue;
	return ChangeResult::Change;
	}

	/// Mark the lattice element as having reached an optimistic fixpoint. This
	/// means that we optimistically assume the current value is the true state.
	void markOptimisticFixpoint() final {
	assert(!isUninitialized() && "expected an initialized value");
	knownValue = *optimisticValue;
	}

	/// Returns true if the lattice has reached a fixpoint. A fixpoint is when the
	/// information optimistically assumed to be true is the same as the
	/// information known to be true.
	bool isAtFixpoint() const final { return optimisticValue == knownValue; }

	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;
	};

	//===----------------------------------------------------------------------===//
	// ForwardDataFlowAnalysisBase
	//===----------------------------------------------------------------------===//

	namespace detail {
	/// This class is the non-templated virtual base class for the
	/// ForwardDataFlowAnalysis. This class provides opaque hooks to the main
	/// algorithm.
	class ForwardDataFlowAnalysisBase {
	public:
	virtual ~ForwardDataFlowAnalysisBase();

	/// Initialize and compute the analysis on operations rooted under the given
	/// top-level operation. Note that the top-level operation is not visited.
	void run(Operation *topLevelOp);

	/// Return the lattice element attached to the given value. If a lattice has
	/// not been added for the given value, a new 'uninitialized' value is
	/// inserted and returned.
	AbstractLatticeElement &getLatticeElement(Value value);

	/// Return the lattice element attached to the given value, or nullptr if no
	/// lattice for the value has yet been created.
	AbstractLatticeElement *lookupLatticeElement(Value value);

	/// Visit the given operation, and join any necessary analysis state
	/// into the lattices for the results and block arguments owned by this
	/// operation using the provided set of operand lattice elements (all pointer
	/// values are guaranteed to be non-null). Returns if any result or block
	/// argument value lattices changed during the visit. The lattice for a result
	/// or block argument value can be obtained and join'ed into by using
	/// `getLatticeElement`.
	virtual ChangeResult
	visitOperation(Operation *op,
	ArrayRef<AbstractLatticeElement *> operands) = 0;

	/// Given a BranchOpInterface, and the current lattice elements that
	/// correspond to the branch operands (all pointer values are guaranteed to be
	/// non-null), try to compute a specific set of successors that would be
	/// selected for the branch. Returns failure if not computable, or if all of
	/// the successors would be chosen. If a subset of successors can be selected,
	/// `successors` is populated.
	virtual LogicalResult
	getSuccessorsForOperands(BranchOpInterface branch,
	ArrayRef<AbstractLatticeElement *> operands,
	SmallVectorImpl<Block *> &successors) = 0;

	/// Given a RegionBranchOpInterface, and the current lattice elements that
	/// correspond to the branch operands (all pointer values are guaranteed to be
	/// non-null), compute a specific set of region successors that would be
	/// selected.
	virtual void
	getSuccessorsForOperands(RegionBranchOpInterface branch,
	Optional<unsigned> sourceIndex,
	ArrayRef<AbstractLatticeElement *> operands,
	SmallVectorImpl<RegionSuccessor> &successors) = 0;

	/// Given a operation with successor regions, one of those regions,
	/// and the lattice elements corresponding to the operation's
	/// arguments, compute the latice values for block arguments
	/// that are not accounted for by the branching control flow (ex. the
	/// bounds of loops).
	virtual ChangeResult
	visitNonControlFlowArguments(Operation *op, const RegionSuccessor &region,
	ArrayRef<AbstractLatticeElement *> operands) = 0;

	/// Create a new uninitialized lattice element. An optional value is provided
	/// which, if valid, should be used to initialize the known conservative state
	/// of the lattice.
	virtual AbstractLatticeElement *createLatticeElement(Value value = {}) = 0;

	private:
	/// A map from SSA value to lattice element.
	DenseMap<Value, AbstractLatticeElement *> latticeValues;
	};
	} // namespace detail

	//===----------------------------------------------------------------------===//
	// ForwardDataFlowAnalysis
	//===----------------------------------------------------------------------===//

	/// This class provides a general forward dataflow analysis driver
	/// utilizing the lattice classes defined above, to enable the easy definition
	/// of dataflow analysis algorithms. More specifically this driver is useful for
	/// defining analyses that are forward, sparse, pessimistic (except along
	/// unreached backedges) and context-insensitive for the interprocedural
	/// aspects.
	template <typename ValueT>
	class ForwardDataFlowAnalysis : public detail::ForwardDataFlowAnalysisBase {
	public:
	ForwardDataFlowAnalysis(MLIRContext *context) : context(context) {}

	/// Return the MLIR context used when constructing this analysis.
	MLIRContext *getContext() { return context; }

	/// Compute the analysis on operations rooted under the given top-level
	/// operation. Note that the top-level operation is not visited.
	void run(Operation *topLevelOp) {
	detail::ForwardDataFlowAnalysisBase::run(topLevelOp);
	}

	/// Return the lattice element attached to the given value, or nullptr if no
	/// lattice for the value has yet been created.
	LatticeElement<ValueT> *lookupLatticeElement(Value value) {
	return static_cast<LatticeElement<ValueT> *>(
	detail::ForwardDataFlowAnalysisBase::lookupLatticeElement(value));
	}

	protected:
	/// Return the lattice element attached to the given value. If a lattice has
	/// not been added for the given value, a new 'uninitialized' value is
	/// inserted and returned.
	LatticeElement<ValueT> &getLatticeElement(Value value) {
	return static_cast<LatticeElement<ValueT> &>(
	detail::ForwardDataFlowAnalysisBase::getLatticeElement(value));
	}

	/// Mark all of the lattices for the given range of Values as having reached a
	/// pessimistic fixpoint.
	ChangeResult markAllPessimisticFixpoint(ValueRange values) {
	ChangeResult result = ChangeResult::NoChange;
	for (Value value : values)
	result \|= getLatticeElement(value).markPessimisticFixpoint();
	return result;
	}

	/// Visit the given operation, and join any necessary analysis state
	/// into the lattices for the results and block arguments owned by this
	/// operation using the provided set of operand lattice elements (all pointer
	/// values are guaranteed to be non-null). Returns if any result or block
	/// argument value lattices changed during the visit. The lattice for a result
	/// or block argument value can be obtained by using
	/// `getLatticeElement`.
	virtual ChangeResult
	visitOperation(Operation *op,
	ArrayRef<LatticeElement<ValueT> *> operands) = 0;

	/// Given a BranchOpInterface, and the current lattice elements that
	/// correspond to the branch operands (all pointer values are guaranteed to be
	/// non-null), try to compute a specific set of successors that would be
	/// selected for the branch. Returns failure if not computable, or if all of
	/// the successors would be chosen. If a subset of successors can be selected,
	/// `successors` is populated.
	virtual LogicalResult
	getSuccessorsForOperands(BranchOpInterface branch,
	ArrayRef<LatticeElement<ValueT> *> operands,
	SmallVectorImpl<Block *> &successors) {
	return failure();
	}

	/// Given a RegionBranchOpInterface, and the current lattice elements that
	/// correspond to the branch operands (all pointer values are guaranteed to be
	/// non-null), compute a specific set of region successors that would be
	/// selected.
	virtual void
	getSuccessorsForOperands(RegionBranchOpInterface branch,
	Optional<unsigned> sourceIndex,
	ArrayRef<LatticeElement<ValueT> *> operands,
	SmallVectorImpl<RegionSuccessor> &successors) {
	SmallVector<Attribute> constantOperands(operands.size());
	branch.getSuccessorRegions(sourceIndex, constantOperands, successors);
	}

	/// Given a operation with successor regions, one of those regions,
	/// and the lattice elements corresponding to the operation's
	/// arguments, compute the latice values for block 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. The region in the
	/// RegionSuccessor and the operand latice elements are guaranteed to be
	/// non-null.
	virtual ChangeResult
	visitNonControlFlowArguments(Operation *op, const RegionSuccessor &successor,
	ArrayRef<LatticeElement<ValueT> *> operands) {
	ChangeResult result = ChangeResult::NoChange;
	Region *region = successor.getSuccessor();
	ValueRange succArgs = successor.getSuccessorInputs();
	Block *block = &region->front();
	Block::BlockArgListType arguments = block->getArguments();
	if (arguments.size() != succArgs.size()) {
	unsigned firstArgIdx =
	succArgs.empty() ? 0
	: succArgs[0].cast<BlockArgument>().getArgNumber();
	result \|= markAllPessimisticFixpoint(arguments.take_front(firstArgIdx));
	result \|= markAllPessimisticFixpoint(
	arguments.drop_front(firstArgIdx + succArgs.size()));
	}
	return result;
	}

	private:
	/// Type-erased wrappers that convert the abstract lattice operands to derived
	/// lattices and invoke the virtual hooks operating on the derived lattices.
	ChangeResult
	visitOperation(Operation *op,
	ArrayRef<detail::AbstractLatticeElement *> operands) final {
	LatticeElement<ValueT> const derivedOperandBase =
	reinterpret_cast<LatticeElement<ValueT> const >(operands.data());
	return visitOperation(
	op, llvm::makeArrayRef(derivedOperandBase, operands.size()));
	}
	LogicalResult
	getSuccessorsForOperands(BranchOpInterface branch,
	ArrayRef<detail::AbstractLatticeElement *> operands,
	SmallVectorImpl<Block *> &successors) final {
	LatticeElement<ValueT> const derivedOperandBase =
	reinterpret_cast<LatticeElement<ValueT> const >(operands.data());
	return getSuccessorsForOperands(
	branch, llvm::makeArrayRef(derivedOperandBase, operands.size()),
	successors);
	}
	void
	getSuccessorsForOperands(RegionBranchOpInterface branch,
	Optional<unsigned> sourceIndex,
	ArrayRef<detail::AbstractLatticeElement *> operands,
	SmallVectorImpl<RegionSuccessor> &successors) final {
	LatticeElement<ValueT> const derivedOperandBase =
	reinterpret_cast<LatticeElement<ValueT> const >(operands.data());
	getSuccessorsForOperands(
	branch, sourceIndex,
	llvm::makeArrayRef(derivedOperandBase, operands.size()), successors);
	}
	ChangeResult visitNonControlFlowArguments(
	Operation *op, const RegionSuccessor &region,
	ArrayRef<detail::AbstractLatticeElement *> operands) final {
	LatticeElement<ValueT> const derivedOperandBase =
	reinterpret_cast<LatticeElement<ValueT> const >(operands.data());
	return visitNonControlFlowArguments(
	op, region, llvm::makeArrayRef(derivedOperandBase, operands.size()));
	}

	/// Create a new uninitialized lattice element. An optional value is provided,
	/// which if valid, should be used to initialize the known conservative state
	/// of the lattice.
	detail::AbstractLatticeElement *createLatticeElement(Value value) final {
	ValueT knownValue = value ? ValueT::getPessimisticValueState(value)
	: ValueT::getPessimisticValueState(context);
	return new (allocator.Allocate()) LatticeElement<ValueT>(knownValue);
	}

	/// An allocator used for new lattice elements.
	llvm::SpecificBumpPtrAllocator<LatticeElement<ValueT>> allocator;

	/// The MLIRContext of this solver.
	MLIRContext *context;
	};

	} // namespace mlir

	#endif // MLIR_ANALYSIS_DATAFLOWANALYSIS_H

mlir/lib/Analysis/CMakeLists.txt

	set(LLVM_OPTIONAL_SOURCES			set(LLVM_OPTIONAL_SOURCES
	AliasAnalysis.cpp			AliasAnalysis.cpp
	BufferViewFlowAnalysis.cpp			BufferViewFlowAnalysis.cpp
	CallGraph.cpp			CallGraph.cpp
	DataFlowAnalysis.cpp
	DataLayoutAnalysis.cpp			DataLayoutAnalysis.cpp
	Liveness.cpp			Liveness.cpp
	SliceAnalysis.cpp			SliceAnalysis.cpp

	AliasAnalysis/LocalAliasAnalysis.cpp			AliasAnalysis/LocalAliasAnalysis.cpp

	DataFlow/ConstantPropagationAnalysis.cpp			DataFlow/ConstantPropagationAnalysis.cpp
	DataFlow/DeadCodeAnalysis.cpp			DataFlow/DeadCodeAnalysis.cpp
	▲ Show 20 Lines • Show All 41 Lines • Show Last 20 Lines

mlir/lib/Analysis/DataFlowAnalysis.cpp

	//===- DataFlowAnalysis.cpp -----------------------------------------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#include "mlir/Analysis/DataFlowAnalysis.h"
	#include "mlir/IR/Operation.h"
	#include "mlir/Interfaces/CallInterfaces.h"
	#include "mlir/Interfaces/ControlFlowInterfaces.h"
	#include "llvm/ADT/ArrayRef.h"
	#include "llvm/ADT/SmallPtrSet.h"

	#include <queue>

	using namespace mlir;
	using namespace mlir::detail;

	namespace {
	/// This class contains various state used when computing the lattice elements
	/// of a callable operation.
	class CallableLatticeState {
	public:
	/// Build a lattice state with a given callable region, and a specified number
	/// of results to be initialized to the default lattice element.
	CallableLatticeState(ForwardDataFlowAnalysisBase &analysis,
	Region *callableRegion, unsigned numResults)
	: callableArguments(callableRegion->getArguments()),
	resultLatticeElements(numResults) {
	for (AbstractLatticeElement *&it : resultLatticeElements)
	it = analysis.createLatticeElement();
	}

	/// Returns the arguments to the callable region.
	Block::BlockArgListType getCallableArguments() const {
	return callableArguments;
	}

	/// Returns the lattice element for the results of the callable region.
	auto getResultLatticeElements() {
	return llvm::make_pointee_range(resultLatticeElements);
	}

	/// Add a call to this callable. This is only used if the callable defines a
	/// symbol.
	void addSymbolCall(Operation *op) { symbolCalls.push_back(op); }

	/// Return the calls that reference this callable. This is only used
	/// if the callable defines a symbol.
	ArrayRef<Operation *> getSymbolCalls() const { return symbolCalls; }

	private:
	/// The arguments of the callable region.
	Block::BlockArgListType callableArguments;

	/// The lattice state for each of the results of this region. The return
	/// values of the callable aren't SSA values, so we need to track them
	/// separately.
	SmallVector<AbstractLatticeElement *, 4> resultLatticeElements;

	/// The calls referencing this callable if this callable defines a symbol.
	/// This removes the need to recompute symbol references during propagation.
	/// Value based references are trivial to resolve, so they can be done
	/// in-place.
	SmallVector<Operation *, 4> symbolCalls;
	};

	/// This class represents the solver for a forward dataflow analysis. This class
	/// acts as the propagation engine for computing which lattice elements.
	class ForwardDataFlowSolver {
	public:
	/// Initialize the solver with the given top-level operation.
	ForwardDataFlowSolver(ForwardDataFlowAnalysisBase &analysis, Operation *op);

	/// Run the solver until it converges.
	void solve();

	private:
	/// Initialize the set of symbol defining callables that can have their
	/// arguments and results tracked. 'op' is the top-level operation that the
	/// solver is operating on.
	void initializeSymbolCallables(Operation *op);

	/// Visit the users of the given IR that reside within executable blocks.
	template <typename T>
	void visitUsers(T &value) {
	for (Operation *user : value.getUsers())
	if (isBlockExecutable(user->getBlock()))
	visitOperation(user);
	}

	/// Visit the given operation and compute any necessary lattice state.
	void visitOperation(Operation *op);

	/// Visit the given call operation and compute any necessary lattice state.
	void visitCallOperation(CallOpInterface op);

	/// Visit the given callable operation and compute any necessary lattice
	/// state.
	void visitCallableOperation(Operation *op);

	/// Visit the given region branch operation, which defines regions, and
	/// compute any necessary lattice state. This also resolves the lattice state
	/// of both the operation results and any nested regions.
	void visitRegionBranchOperation(
	RegionBranchOpInterface branch,
	ArrayRef<AbstractLatticeElement *> operandLattices);

	/// Visit the given set of region successors, computing any necessary lattice
	/// state. The provided function returns the input operands to the region at
	/// the given index. If the index is 'None', the input operands correspond to
	/// the parent operation results.
	void visitRegionSuccessors(
	Operation *parentOp, ArrayRef<RegionSuccessor> regionSuccessors,
	ArrayRef<AbstractLatticeElement *> operandLattices,
	function_ref<OperandRange(Optional<unsigned>)> getInputsForRegion);

	/// Visit the given terminator operation and compute any necessary lattice
	/// state.
	void
	visitTerminatorOperation(Operation *op,
	ArrayRef<AbstractLatticeElement *> operandLattices);

	/// Visit the given terminator operation that exits a callable region. These
	/// are terminators with no CFG successors.
	void visitCallableTerminatorOperation(
	Operation callable, Operation terminator,
	ArrayRef<AbstractLatticeElement *> operandLattices);

	/// Visit the given block and compute any necessary lattice state.
	void visitBlock(Block *block);

	/// Visit argument #'i' of the given block and compute any necessary lattice
	/// state.
	void visitBlockArgument(Block *block, int i);

	/// Mark the entry block of the given region as executable. Returns NoChange
	/// if the block was already marked executable. If `markPessimisticFixpoint`
	/// is true, the arguments of the entry block are also marked as having
	/// reached the pessimistic fixpoint.
	ChangeResult markEntryBlockExecutable(Region *region,
	bool markPessimisticFixpoint);

	/// Mark the given block as executable. Returns NoChange if the block was
	/// already marked executable.
	ChangeResult markBlockExecutable(Block *block);

	/// Returns true if the given block is executable.
	bool isBlockExecutable(Block *block) const;

	/// Mark the edge between 'from' and 'to' as executable.
	void markEdgeExecutable(Block from, Block to);

	/// Return true if the edge between 'from' and 'to' is executable.
	bool isEdgeExecutable(Block from, Block to) const;

	/// Mark the given value as having reached the pessimistic fixpoint. This
	/// means that we cannot further refine the state of this value.
	void markPessimisticFixpoint(Value value);

	/// Mark all of the given values as having reaching the pessimistic fixpoint.
	template <typename ValuesT>
	void markAllPessimisticFixpoint(ValuesT values) {
	for (auto value : values)
	markPessimisticFixpoint(value);
	}
	template <typename ValuesT>
	void markAllPessimisticFixpoint(Operation *op, ValuesT values) {
	markAllPessimisticFixpoint(values);
	opWorklist.push(op);
	}
	template <typename ValuesT>
	void markAllPessimisticFixpointAndVisitUsers(ValuesT values) {
	for (auto value : values) {
	AbstractLatticeElement &lattice = analysis.getLatticeElement(value);
	if (lattice.markPessimisticFixpoint() == ChangeResult::Change)
	visitUsers(value);
	}
	}

	/// Returns true if the given value was marked as having reached the
	/// pessimistic fixpoint.
	bool isAtFixpoint(Value value) const;

	/// Merge in the given lattice 'from' into the lattice 'to'. 'owner'
	/// corresponds to the parent operation of the lattice for 'to'.
	void join(Operation *owner, AbstractLatticeElement &to,
	const AbstractLatticeElement &from);

	/// A reference to the dataflow analysis being computed.
	ForwardDataFlowAnalysisBase &analysis;

	/// The set of blocks that are known to execute, or are intrinsically live.
	SmallPtrSet<Block *, 16> executableBlocks;

	/// The set of control flow edges that are known to execute.
	DenseSet<std::pair<Block , Block >> executableEdges;

	/// A worklist containing blocks that need to be processed.
	std::queue<Block *> blockWorklist;

	/// A worklist of operations that need to be processed.
	std::queue<Operation *> opWorklist;

	/// The callable operations that have their argument/result state tracked.
	DenseMap<Operation *, CallableLatticeState> callableLatticeState;

	/// A map between a call operation and the resolved symbol callable. This
	/// avoids re-resolving symbol references during propagation. Value based
	/// callables are trivial to resolve, so they can be done in-place.
	DenseMap<Operation , Operation > callToSymbolCallable;

	/// A symbol table used for O(1) symbol lookups during simplification.
	SymbolTableCollection symbolTable;
	};
	} // namespace

	ForwardDataFlowSolver::ForwardDataFlowSolver(
	ForwardDataFlowAnalysisBase &analysis, Operation *op)
	: analysis(analysis) {
	/// Initialize the solver with the regions within this operation.
	for (Region &region : op->getRegions()) {
	// Mark the entry block as executable. The values passed to these regions
	// are also invisible, so mark any arguments as reaching the pessimistic
	// fixpoint.
	markEntryBlockExecutable(&region, /markPessimisticFixpoint=/true);
	}
	initializeSymbolCallables(op);
	}

	void ForwardDataFlowSolver::solve() {
	while (!blockWorklist.empty() \|\| !opWorklist.empty()) {
	// Process any operations in the op worklist.
	while (!opWorklist.empty()) {
	Operation *nextOp = opWorklist.front();
	opWorklist.pop();
	visitUsers(*nextOp);
	}

	// Process any blocks in the block worklist.
	while (!blockWorklist.empty()) {
	Block *nextBlock = blockWorklist.front();
	blockWorklist.pop();
	visitBlock(nextBlock);
	}
	}
	}

	void ForwardDataFlowSolver::initializeSymbolCallables(Operation *op) {
	// Initialize the set of symbol callables that can have their state tracked.
	// This tracks which symbol callable operations we can propagate within and
	// out of.
	auto walkFn = [&](Operation *symTable, bool allUsesVisible) {
	Region &symbolTableRegion = symTable->getRegion(0);
	Block *symbolTableBlock = &symbolTableRegion.front();
	for (auto callable : symbolTableBlock->getOps<CallableOpInterface>()) {
	// We won't be able to track external callables.
	Region *callableRegion = callable.getCallableRegion();
	if (!callableRegion)
	continue;
	// We only care about symbol defining callables here.
	auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
	if (!symbol)
	continue;
	callableLatticeState.try_emplace(callable, analysis, callableRegion,
	callable.getCallableResults().size());

	// If not all of the uses of this symbol are visible, we can't track the
	// state of the arguments.
	if (symbol.isPublic() \|\| (!allUsesVisible && symbol.isNested())) {
	for (Region &region : callable->getRegions())
	markEntryBlockExecutable(&region, /markPessimisticFixpoint=/true);
	}
	}
	if (callableLatticeState.empty())
	return;

	// After computing the valid callables, walk any symbol uses to check
	// for non-call references. We won't be able to track the lattice state
	// for arguments to these callables, as we can't guarantee that we can see
	// all of its calls.
	Optional<SymbolTable::UseRange> uses =
	SymbolTable::getSymbolUses(&symbolTableRegion);
	if (!uses) {
	// If we couldn't gather the symbol uses, conservatively assume that
	// we can't track information for any nested symbols.
	op->walk([&](CallableOpInterface op) { callableLatticeState.erase(op); });
	return;
	}

	for (const SymbolTable::SymbolUse &use : *uses) {
	// If the use is a call, track it to avoid the need to recompute the
	// reference later.
	if (auto callOp = dyn_cast<CallOpInterface>(use.getUser())) {
	Operation *symCallable = callOp.resolveCallable(&symbolTable);
	auto callableLatticeIt = callableLatticeState.find(symCallable);
	if (callableLatticeIt != callableLatticeState.end()) {
	callToSymbolCallable.try_emplace(callOp, symCallable);

	// We only need to record the call in the lattice if it produces any
	// values.
	if (callOp->getNumResults())
	callableLatticeIt->second.addSymbolCall(callOp);
	}
	continue;
	}
	// This use isn't a call, so don't we know all of the callers.
	auto *symbol = symbolTable.lookupSymbolIn(op, use.getSymbolRef());
	auto it = callableLatticeState.find(symbol);
	if (it != callableLatticeState.end()) {
	for (Region &region : it->first->getRegions())
	markEntryBlockExecutable(&region, /markPessimisticFixpoint=/true);
	}
	}
	};
	SymbolTable::walkSymbolTables(op, /allSymUsesVisible=/!op->getBlock(),
	walkFn);
	}

	void ForwardDataFlowSolver::visitOperation(Operation *op) {
	// Collect all of the lattice elements feeding into this operation. If any are
	// not yet resolved, bail out and wait for them to resolve.
	SmallVector<AbstractLatticeElement *, 8> operandLattices;
	operandLattices.reserve(op->getNumOperands());
	for (Value operand : op->getOperands()) {
	AbstractLatticeElement *operandLattice =
	analysis.lookupLatticeElement(operand);
	if (!operandLattice \|\| operandLattice->isUninitialized())
	return;
	operandLattices.push_back(operandLattice);
	}

	// If this is a terminator operation, process any control flow lattice state.
	if (op->hasTrait<OpTrait::IsTerminator>())
	visitTerminatorOperation(op, operandLattices);

	// Process call operations. The call visitor processes result values, so we
	// can exit afterwards.
	if (CallOpInterface call = dyn_cast<CallOpInterface>(op))
	return visitCallOperation(call);

	// Process callable operations. These are specially handled region operations
	// that track dataflow via calls.
	if (isa<CallableOpInterface>(op)) {
	// If this callable has a tracked lattice state, it will be visited by calls
	// that reference it instead. This way, we don't assume that it is
	// executable unless there is a proper reference to it.
	if (callableLatticeState.count(op))
	return;
	return visitCallableOperation(op);
	}

	// Process region holding operations.
	if (op->getNumRegions()) {
	// Check to see if we can reason about the internal control flow of this
	// region operation.
	if (auto branch = dyn_cast<RegionBranchOpInterface>(op))
	return visitRegionBranchOperation(branch, operandLattices);

	for (Region &region : op->getRegions()) {
	analysis.visitNonControlFlowArguments(op, RegionSuccessor(&region),
	operandLattices);
	// `visitNonControlFlowArguments` is required to define all of the region
	// argument lattices.
	assert(llvm::none_of(
	region.getArguments(),
	[&](Value value) {
	return analysis.getLatticeElement(value).isUninitialized();
	}) &&
	"expected `visitNonControlFlowArguments` to define all argument "
	"lattices");
	markEntryBlockExecutable(&region, /markPessimisticFixpoint=/false);
	}
	}

	// If this op produces no results, it can't produce any constants.
	if (op->getNumResults() == 0)
	return;

	// If all of the results of this operation are already resolved, bail out
	// early.
	auto isAtFixpointFn = [&](Value value) { return isAtFixpoint(value); };
	if (llvm::all_of(op->getResults(), isAtFixpointFn))
	return;

	// Visit the current operation.
	if (analysis.visitOperation(op, operandLattices) == ChangeResult::Change)
	opWorklist.push(op);

	// `visitOperation` is required to define all of the result lattices.
	assert(llvm::none_of(
	op->getResults(),
	[&](Value value) {
	return analysis.getLatticeElement(value).isUninitialized();
	}) &&
	"expected `visitOperation` to define all result lattices");
	}

	void ForwardDataFlowSolver::visitCallableOperation(Operation *op) {
	// Mark the regions as executable. If we aren't tracking lattice state for
	// this callable, mark all of the region arguments as having reached a
	// fixpoint.
	bool isTrackingLatticeState = callableLatticeState.count(op);
	for (Region &region : op->getRegions())
	markEntryBlockExecutable(&region, !isTrackingLatticeState);

	// TODO: Add support for non-symbol callables when necessary. If the callable
	// has non-call uses we would mark as having reached pessimistic fixpoint,
	// otherwise allow for propagating the return values out.
	markAllPessimisticFixpoint(op, op->getResults());
	}

	void ForwardDataFlowSolver::visitCallOperation(CallOpInterface op) {
	ResultRange callResults = op->getResults();

	// Resolve the callable operation for this call.
	Operation *callableOp = nullptr;
	if (Value callableValue = op.getCallableForCallee().dyn_cast<Value>())
	callableOp = callableValue.getDefiningOp();
	else
	callableOp = callToSymbolCallable.lookup(op);

	// The callable of this call can't be resolved, mark any results overdefined.
	if (!callableOp)
	return markAllPessimisticFixpoint(op, callResults);

	// If this callable is tracking state, merge the argument operands with the
	// arguments of the callable.
	auto callableLatticeIt = callableLatticeState.find(callableOp);
	if (callableLatticeIt == callableLatticeState.end())
	return markAllPessimisticFixpoint(op, callResults);

	OperandRange callOperands = op.getArgOperands();
	auto callableArgs = callableLatticeIt->second.getCallableArguments();
	for (auto it : llvm::zip(callOperands, callableArgs)) {
	BlockArgument callableArg = std::get<1>(it);
	AbstractLatticeElement &argValue = analysis.getLatticeElement(callableArg);
	AbstractLatticeElement &operandValue =
	analysis.getLatticeElement(std::get<0>(it));
	if (argValue.join(operandValue) == ChangeResult::Change)
	visitUsers(callableArg);
	}

	// Visit the callable.
	visitCallableOperation(callableOp);

	// Merge in the lattice state for the callable results as well.
	auto callableResults = callableLatticeIt->second.getResultLatticeElements();
	for (auto it : llvm::zip(callResults, callableResults))
	join(/owner=/op,
	/to=/analysis.getLatticeElement(std::get<0>(it)),
	/from=/std::get<1>(it));
	}

	void ForwardDataFlowSolver::visitRegionBranchOperation(
	RegionBranchOpInterface branch,
	ArrayRef<AbstractLatticeElement *> operandLattices) {
	// Check to see which regions are executable.
	SmallVector<RegionSuccessor, 1> successors;
	analysis.getSuccessorsForOperands(branch, /sourceIndex=/llvm::None,
	operandLattices, successors);

	// If the interface identified that no region will be executed. Mark
	// any results of this operation as overdefined, as we can't reason about
	// them.
	// TODO: If we had an interface to detect pass through operands, we could
	// resolve some results based on the lattice state of the operands. We could
	// also allow for the parent operation to have itself as a region successor.
	if (successors.empty())
	return markAllPessimisticFixpoint(branch, branch->getResults());
	return visitRegionSuccessors(branch, successors, operandLattices,
	[&](Optional<unsigned> index) {
	return branch.getSuccessorEntryOperands(index);
	});
	}

	void ForwardDataFlowSolver::visitRegionSuccessors(
	Operation *parentOp, ArrayRef<RegionSuccessor> regionSuccessors,
	ArrayRef<AbstractLatticeElement *> operandLattices,
	function_ref<OperandRange(Optional<unsigned>)> getInputsForRegion) {
	for (const RegionSuccessor &it : regionSuccessors) {
	Region *region = it.getSuccessor();
	ValueRange succArgs = it.getSuccessorInputs();

	// Check to see if this is the parent operation.
	if (!region) {
	ResultRange results = parentOp->getResults();
	if (llvm::all_of(results, [&](Value res) { return isAtFixpoint(res); }))
	continue;

	// Mark the results outside of the input range as having reached the
	// pessimistic fixpoint.
	// TODO: This isn't exactly ideal. There may be situations in which a
	// region operation can provide information for certain results that
	// aren't part of the control flow.
	if (succArgs.size() != results.size()) {
	opWorklist.push(parentOp);
	if (succArgs.empty()) {
	markAllPessimisticFixpoint(results);
	continue;
	}

	unsigned firstResIdx = succArgs[0].cast<OpResult>().getResultNumber();
	markAllPessimisticFixpoint(results.take_front(firstResIdx));
	markAllPessimisticFixpoint(
	results.drop_front(firstResIdx + succArgs.size()));
	}

	// Update the lattice for any operation results.
	OperandRange operands = getInputsForRegion(/index=/llvm::None);
	for (auto it : llvm::zip(succArgs, operands))
	join(parentOp, analysis.getLatticeElement(std::get<0>(it)),
	analysis.getLatticeElement(std::get<1>(it)));
	continue;
	}
	assert(!region->empty() && "expected region to be non-empty");
	Block *entryBlock = &region->front();
	markBlockExecutable(entryBlock);

	// If all of the arguments have already reached a fixpoint, the arguments
	// have already been fully resolved.
	Block::BlockArgListType arguments = entryBlock->getArguments();
	if (llvm::all_of(arguments, [&](Value arg) { return isAtFixpoint(arg); }))
	continue;

	if (succArgs.size() != arguments.size()) {
	if (analysis.visitNonControlFlowArguments(
	parentOp, it, operandLattices) == ChangeResult::Change) {
	unsigned firstArgIdx =
	succArgs.empty() ? 0
	: succArgs[0].cast<BlockArgument>().getArgNumber();
	for (Value v : arguments.take_front(firstArgIdx)) {
	assert(!analysis.getLatticeElement(v).isUninitialized() &&
	"Non-control flow block arg has no lattice value after "
	"analysis callback");
	visitUsers(v);
	}
	for (Value v : arguments.drop_front(firstArgIdx + succArgs.size())) {
	assert(!analysis.getLatticeElement(v).isUninitialized() &&
	"Non-control flow block arg has no lattice value after "
	"analysis callback");
	visitUsers(v);
	}
	}
	}

	// Update the lattice of arguments that have inputs from the predecessor.
	OperandRange succOperands = getInputsForRegion(region->getRegionNumber());
	for (auto it : llvm::zip(succArgs, succOperands)) {
	AbstractLatticeElement &argValue =
	analysis.getLatticeElement(std::get<0>(it));
	AbstractLatticeElement &operandValue =
	analysis.getLatticeElement(std::get<1>(it));
	if (argValue.join(operandValue) == ChangeResult::Change)
	visitUsers(std::get<0>(it));
	}
	}
	}

	void ForwardDataFlowSolver::visitTerminatorOperation(
	Operation op, ArrayRef<AbstractLatticeElement > operandLattices) {
	// If this operation has no successors, we treat it as an exiting terminator.
	if (op->getNumSuccessors() == 0) {
	Region *parentRegion = op->getParentRegion();
	Operation *parentOp = parentRegion->getParentOp();

	// Check to see if this is a terminator for a callable region.
	if (isa<CallableOpInterface>(parentOp))
	return visitCallableTerminatorOperation(parentOp, op, operandLattices);

	// Otherwise, check to see if the parent tracks region control flow.
	auto regionInterface = dyn_cast<RegionBranchOpInterface>(parentOp);
	if (!regionInterface \|\| !isBlockExecutable(parentOp->getBlock()))
	return;

	// Query the set of successors of the current region using the current
	// optimistic lattice state.
	SmallVector<RegionSuccessor, 1> regionSuccessors;
	analysis.getSuccessorsForOperands(regionInterface,
	parentRegion->getRegionNumber(),
	operandLattices, regionSuccessors);
	if (regionSuccessors.empty())
	return;

	// Try to get "region-like" successor operands if possible in order to
	// propagate the operand states to the successors.
	if (isRegionReturnLike(op)) {
	auto getOperands = [&](Optional<unsigned> regionIndex) {
	// Determine the individual region successor operands for the given
	// region index (if any).
	return *getRegionBranchSuccessorOperands(op, regionIndex);
	};
	return visitRegionSuccessors(parentOp, regionSuccessors, operandLattices,
	getOperands);
	}

	// If this terminator is not "region-like", conservatively mark all of the
	// successor values as having reached the pessimistic fixpoint.
	for (auto &it : regionSuccessors) {
	// If the successor is a region, mark the entry block as executable so
	// that we visit operations defined within. If the successor is the
	// parent operation, we simply mark the control flow results as having
	// reached the pessimistic state.
	if (Region *region = it.getSuccessor())
	markEntryBlockExecutable(region, /markPessimisticFixpoint=/true);
	else
	markAllPessimisticFixpointAndVisitUsers(it.getSuccessorInputs());
	}
	}

	// Try to resolve to a specific set of successors with the current optimistic
	// lattice state.
	Block *block = op->getBlock();
	if (auto branch = dyn_cast<BranchOpInterface>(op)) {
	SmallVector<Block *> successors;
	if (succeeded(analysis.getSuccessorsForOperands(branch, operandLattices,
	successors))) {
	for (Block *succ : successors)
	markEdgeExecutable(block, succ);
	return;
	}
	}

	// Otherwise, conservatively treat all edges as executable.
	for (Block *succ : op->getSuccessors())
	markEdgeExecutable(block, succ);
	}

	void ForwardDataFlowSolver::visitCallableTerminatorOperation(
	Operation callable, Operation terminator,
	ArrayRef<AbstractLatticeElement *> operandLattices) {
	// If there are no exiting values, we have nothing to track.
	if (terminator->getNumOperands() == 0)
	return;

	// If this callable isn't tracking any lattice state there is nothing to do.
	auto latticeIt = callableLatticeState.find(callable);
	if (latticeIt == callableLatticeState.end())
	return;
	assert(callable->getNumResults() == 0 && "expected symbol callable");

	// If this terminator is not "return-like", conservatively mark all of the
	// call-site results as having reached the pessimistic fixpoint.
	auto callableResultLattices = latticeIt->second.getResultLatticeElements();
	if (!terminator->hasTrait<OpTrait::ReturnLike>()) {
	for (auto &it : callableResultLattices)
	it.markPessimisticFixpoint();
	for (Operation *call : latticeIt->second.getSymbolCalls())
	markAllPessimisticFixpoint(call, call->getResults());
	return;
	}

	// Merge the lattice state for terminator operands into the results.
	ChangeResult result = ChangeResult::NoChange;
	for (auto it : llvm::zip(operandLattices, callableResultLattices))
	result \|= std::get<1>(it).join(*std::get<0>(it));
	if (result == ChangeResult::NoChange)
	return;

	// If any of the result lattices changed, update the callers.
	for (Operation *call : latticeIt->second.getSymbolCalls())
	for (auto it : llvm::zip(call->getResults(), callableResultLattices))
	join(call, analysis.getLatticeElement(std::get<0>(it)), std::get<1>(it));
	}

	void ForwardDataFlowSolver::visitBlock(Block *block) {
	// If the block is not the entry block we need to compute the lattice state
	// for the block arguments. Entry block argument lattices are computed
	// elsewhere, such as when visiting the parent operation.
	if (!block->isEntryBlock()) {
	for (int i : llvm::seq<int>(0, block->getNumArguments()))
	visitBlockArgument(block, i);
	}

	// Visit all of the operations within the block.
	for (Operation &op : *block)
	visitOperation(&op);
	}

	void ForwardDataFlowSolver::visitBlockArgument(Block *block, int i) {
	BlockArgument arg = block->getArgument(i);
	AbstractLatticeElement &argLattice = analysis.getLatticeElement(arg);
	if (argLattice.isAtFixpoint())
	return;

	ChangeResult updatedLattice = ChangeResult::NoChange;
	for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
	Block pred = it;

	// We only care about this predecessor if it is going to execute.
	if (!isEdgeExecutable(pred, block))
	continue;

	// Try to get the operand forwarded by the predecessor. If we can't reason
	// about the terminator of the predecessor, mark as having reached a
	// fixpoint.
	auto branch = dyn_cast<BranchOpInterface>(pred->getTerminator());
	if (!branch) {
	updatedLattice \|= argLattice.markPessimisticFixpoint();
	break;
	}
	Value operand = branch.getSuccessorOperands(it.getSuccessorIndex())[i];
	if (!operand) {
	updatedLattice \|= argLattice.markPessimisticFixpoint();
	break;
	}

	// If the operand hasn't been resolved, it is uninitialized and can merge
	// with anything.
	AbstractLatticeElement *operandLattice =
	analysis.lookupLatticeElement(operand);
	if (!operandLattice)
	continue;

	// Otherwise, join the operand lattice into the argument lattice.
	updatedLattice \|= argLattice.join(*operandLattice);
	if (argLattice.isAtFixpoint())
	break;
	}

	// If the lattice changed, visit users of the argument.
	if (updatedLattice == ChangeResult::Change)
	visitUsers(arg);
	}

	ChangeResult
	ForwardDataFlowSolver::markEntryBlockExecutable(Region *region,
	bool markPessimisticFixpoint) {
	if (!region->empty()) {
	if (markPessimisticFixpoint)
	markAllPessimisticFixpoint(region->front().getArguments());
	return markBlockExecutable(&region->front());
	}
	return ChangeResult::NoChange;
	}

	ChangeResult ForwardDataFlowSolver::markBlockExecutable(Block *block) {
	bool marked = executableBlocks.insert(block).second;
	if (marked)
	blockWorklist.push(block);
	return marked ? ChangeResult::Change : ChangeResult::NoChange;
	}

	bool ForwardDataFlowSolver::isBlockExecutable(Block *block) const {
	return executableBlocks.count(block);
	}

	void ForwardDataFlowSolver::markEdgeExecutable(Block from, Block to) {
	executableEdges.insert(std::make_pair(from, to));

	// Mark the destination as executable, and reprocess its arguments if it was
	// already executable.
	if (markBlockExecutable(to) == ChangeResult::NoChange) {
	for (int i : llvm::seq<int>(0, to->getNumArguments()))
	visitBlockArgument(to, i);
	}
	}

	bool ForwardDataFlowSolver::isEdgeExecutable(Block from, Block to) const {
	return executableEdges.count(std::make_pair(from, to));
	}

	void ForwardDataFlowSolver::markPessimisticFixpoint(Value value) {
	analysis.getLatticeElement(value).markPessimisticFixpoint();
	}

	bool ForwardDataFlowSolver::isAtFixpoint(Value value) const {
	if (auto *lattice = analysis.lookupLatticeElement(value))
	return lattice->isAtFixpoint();
	return false;
	}

	void ForwardDataFlowSolver::join(Operation *owner, AbstractLatticeElement &to,
	const AbstractLatticeElement &from) {
	if (to.join(from) == ChangeResult::Change)
	opWorklist.push(owner);
	}

	//===----------------------------------------------------------------------===//
	// AbstractLatticeElement
	//===----------------------------------------------------------------------===//

	AbstractLatticeElement::~AbstractLatticeElement() = default;

	//===----------------------------------------------------------------------===//
	// ForwardDataFlowAnalysisBase
	//===----------------------------------------------------------------------===//

	ForwardDataFlowAnalysisBase::~ForwardDataFlowAnalysisBase() = default;

	AbstractLatticeElement &
	ForwardDataFlowAnalysisBase::getLatticeElement(Value value) {
	AbstractLatticeElement *&latticeValue = latticeValues[value];
	if (!latticeValue)
	latticeValue = createLatticeElement(value);
	return *latticeValue;
	}

	AbstractLatticeElement *
	ForwardDataFlowAnalysisBase::lookupLatticeElement(Value value) {
	return latticeValues.lookup(value);
	}

	void ForwardDataFlowAnalysisBase::run(Operation *topLevelOp) {
	// Run the main dataflow solver.
	ForwardDataFlowSolver solver(*this, topLevelOp);
	solver.solve();

	// Any values that are still uninitialized now go to a pessimistic fixpoint,
	// otherwise we assume an optimistic fixpoint has been reached.
	for (auto &it : latticeValues)
	if (it.second->isUninitialized())
	it.second->markPessimisticFixpoint();
	else
	it.second->markOptimisticFixpoint();
	}

mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp

	//===- TosaInferShapes.cpp ------------------------------------------------===//			//===- TosaInferShapes.cpp ------------------------------------------------===//
	//			//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.			// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.			// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception			// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//
	//			//
	// Propogate shapes forward along TOSA operations to resolve dynamic shape			// Propogate shapes forward along TOSA operations to resolve dynamic shape
	// operations.			// operations.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#include "mlir/Analysis/DataFlowAnalysis.h"
	#include "mlir/Dialect/Func/IR/FuncOps.h"			#include "mlir/Dialect/Func/IR/FuncOps.h"
	#include "mlir/Dialect/Tensor/IR/Tensor.h"			#include "mlir/Dialect/Tensor/IR/Tensor.h"
	#include "mlir/Dialect/Tosa/IR/TosaOps.h"			#include "mlir/Dialect/Tosa/IR/TosaOps.h"
	#include "mlir/Dialect/Tosa/Transforms/PassDetail.h"			#include "mlir/Dialect/Tosa/Transforms/PassDetail.h"
	#include "mlir/Dialect/Tosa/Transforms/Passes.h"			#include "mlir/Dialect/Tosa/Transforms/Passes.h"
	#include "mlir/Dialect/Tosa/Utils/ShapeUtils.h"			#include "mlir/Dialect/Tosa/Utils/ShapeUtils.h"
	#include "mlir/IR/BlockAndValueMapping.h"			#include "mlir/IR/BlockAndValueMapping.h"
	#include "mlir/IR/Builders.h"			#include "mlir/IR/Builders.h"
	▲ Show 20 Lines • Show All 305 Lines • Show Last 20 Lines

mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp

	//===- CheckUses.cpp - Expensive transform value validity checks ----------===//			//===- CheckUses.cpp - Expensive transform value validity checks ----------===//
	//			//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.			// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.			// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception			// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//
	//			//
	// This file defines a pass that performs expensive opt-in checks for Transform			// This file defines a pass that performs expensive opt-in checks for Transform
	// dialect values being potentially used after they have been consumed.			// dialect values being potentially used after they have been consumed.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#include "mlir/Analysis/DataFlowAnalysis.h"
	#include "mlir/Dialect/Transform/IR/TransformInterfaces.h"			#include "mlir/Dialect/Transform/IR/TransformInterfaces.h"
	#include "mlir/Dialect/Transform/Transforms/Passes.h"			#include "mlir/Dialect/Transform/Transforms/Passes.h"
	#include "mlir/Interfaces/SideEffectInterfaces.h"			#include "mlir/Interfaces/SideEffectInterfaces.h"
	#include "mlir/Pass/Pass.h"			#include "mlir/Pass/Pass.h"
	#include "llvm/ADT/SetOperations.h"			#include "llvm/ADT/SetOperations.h"

	using namespace mlir;			using namespace mlir;

	▲ Show 20 Lines • Show All 380 Lines • Show Last 20 Lines

mlir/test/Analysis/test-data-flow.mlir

This file was deleted.

	// RUN: mlir-opt -test-data-flow --allow-unregistered-dialect %s 2>&1 \| FileCheck %s

	// CHECK-LABEL: Testing : "loop-arg-pessimistic"
	module attributes {test.name = "loop-arg-pessimistic"} {
	func.func @f() -> index {
	// CHECK: Visiting : %{{.*}} = arith.constant 0
	// CHECK-NEXT: Result 0 moved from uninitialized to 1
	%c0 = arith.constant 0 : index
	// CHECK: Visiting : %{{.*}} = arith.constant 1
	// CHECK-NEXT: Result 0 moved from uninitialized to 1
	%c1 = arith.constant 1 : index
	// CHECK: Visiting region branch op : %{{.*}} = scf.for
	// CHECK: Block argument 0 moved from uninitialized to 1
	%0 = scf.for %arg1 = %c0 to %c1 step %c1 iter_args(%arg2 = %c0) -> index {
	// CHECK: Visiting : %{{.}} = arith.addi %{{.}}, %{{.*}}
	// CHECK-NEXT: Arg 0 : 1
	// CHECK-NEXT: Arg 1 : 1
	// CHECK-NEXT: Result 0 moved from uninitialized to 1
	%10 = arith.addi %arg1, %arg2 : index
	scf.yield %10 : index
	}
	return %0 : index
	}
	}

mlir/test/lib/Analysis/CMakeLists.txt

	# Exclude tests from libMLIR.so			# Exclude tests from libMLIR.so
	add_mlir_library(MLIRTestAnalysis			add_mlir_library(MLIRTestAnalysis
	TestAliasAnalysis.cpp			TestAliasAnalysis.cpp
	TestCallGraph.cpp			TestCallGraph.cpp
	TestDataFlow.cpp
	TestDataFlowFramework.cpp			TestDataFlowFramework.cpp
	TestLiveness.cpp			TestLiveness.cpp
	TestMatchReduction.cpp			TestMatchReduction.cpp
	TestMemRefBoundCheck.cpp			TestMemRefBoundCheck.cpp
	TestMemRefDependenceCheck.cpp			TestMemRefDependenceCheck.cpp
	TestMemRefStrideCalculation.cpp			TestMemRefStrideCalculation.cpp
	TestSlice.cpp			TestSlice.cpp

	Show All 18 Lines

mlir/test/lib/Analysis/TestDataFlow.cpp

This file was deleted.

	//===- TestDataFlow.cpp - Test data flow analysis system -------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// This file contains test passes for defining and running a dataflow analysis.
	//
	//===----------------------------------------------------------------------===//

	#include "mlir/Analysis/DataFlowAnalysis.h"
	#include "mlir/IR/BuiltinOps.h"
	#include "mlir/IR/OperationSupport.h"
	#include "mlir/Pass/Pass.h"
	#include "llvm/ADT/STLExtras.h"

	using namespace mlir;

	namespace {
	struct WasAnalyzed {
	WasAnalyzed(bool wasAnalyzed) : wasAnalyzed(wasAnalyzed) {}

	static WasAnalyzed join(const WasAnalyzed &a, const WasAnalyzed &b) {
	return a.wasAnalyzed && b.wasAnalyzed;
	}

	static WasAnalyzed getPessimisticValueState(MLIRContext *context) {
	return false;
	}

	static WasAnalyzed getPessimisticValueState(Value v) {
	return getPessimisticValueState(v.getContext());
	}

	bool operator==(const WasAnalyzed &other) const {
	return wasAnalyzed == other.wasAnalyzed;
	}

	bool wasAnalyzed;
	};

	struct TestAnalysis : public ForwardDataFlowAnalysis<WasAnalyzed> {
	using ForwardDataFlowAnalysis<WasAnalyzed>::ForwardDataFlowAnalysis;

	ChangeResult
	visitOperation(Operation *op,
	ArrayRef<LatticeElement<WasAnalyzed> *> operands) final {
	ChangeResult ret = ChangeResult::NoChange;
	llvm::errs() << "Visiting : ";
	op->print(llvm::errs());
	llvm::errs() << "\n";

	WasAnalyzed result(true);
	for (auto &pair : llvm::enumerate(operands)) {
	LatticeElement<WasAnalyzed> *elem = pair.value();
	llvm::errs() << "Arg " << pair.index();
	if (!elem->isUninitialized()) {
	llvm::errs() << " : " << elem->getValue().wasAnalyzed << "\n";
	result = WasAnalyzed::join(result, elem->getValue());
	} else {
	llvm::errs() << " uninitialized\n";
	}
	}
	for (const auto &pair : llvm::enumerate(op->getResults())) {
	LatticeElement<WasAnalyzed> &lattice = getLatticeElement(pair.value());
	llvm::errs() << "Result " << pair.index() << " moved from ";
	if (lattice.isUninitialized())
	llvm::errs() << "uninitialized";
	else
	llvm::errs() << lattice.getValue().wasAnalyzed;
	ret \|= lattice.join({result});
	llvm::errs() << " to " << lattice.getValue().wasAnalyzed << "\n";
	}
	return ret;
	}

	ChangeResult visitNonControlFlowArguments(
	Operation *op, const RegionSuccessor &successor,
	ArrayRef<LatticeElement<WasAnalyzed> *> operands) final {
	ChangeResult ret = ChangeResult::NoChange;
	llvm::errs() << "Visiting region branch op : ";
	op->print(llvm::errs());
	llvm::errs() << "\n";

	Region *region = successor.getSuccessor();
	Block *block = &region->front();
	Block::BlockArgListType arguments = block->getArguments();
	// Mark all arguments to blocks as analyzed unless they already have
	// an unanalyzed state.
	for (const auto &pair : llvm::enumerate(arguments)) {
	LatticeElement<WasAnalyzed> &lattice = getLatticeElement(pair.value());
	llvm::errs() << "Block argument " << pair.index() << " moved from ";
	if (lattice.isUninitialized())
	llvm::errs() << "uninitialized";
	else
	llvm::errs() << lattice.getValue().wasAnalyzed;
	ret \|= lattice.join({true});
	llvm::errs() << " to " << lattice.getValue().wasAnalyzed << "\n";
	}
	return ret;
	}
	};

	struct TestDataFlowPass
	: public PassWrapper<TestDataFlowPass, OperationPass<ModuleOp>> {
	MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestDataFlowPass)

	StringRef getArgument() const final { return "test-data-flow"; }
	StringRef getDescription() const final {
	return "Print the actions taken during a dataflow analysis.";
	}
	void runOnOperation() override {
	llvm::errs() << "Testing : " << getOperation()->getAttr("test.name")
	<< "\n";
	TestAnalysis analysis(getOperation().getContext());
	analysis.run(getOperation());
	}
	};
	} // namespace

	namespace mlir {
	namespace test {
	void registerTestDataFlowPass() { PassRegistration<TestDataFlowPass>(); }
	} // namespace test
	} // namespace mlir

mlir/tools/mlir-opt/mlir-opt.cpp

Show First 20 Lines • Show All 64 Lines • ▼ Show 20 Lines
void registerTestAffineLoopParametricTilingPass();		void registerTestAffineLoopParametricTilingPass();
void registerTestAliasAnalysisPass();		void registerTestAliasAnalysisPass();
void registerTestBuiltinAttributeInterfaces();		void registerTestBuiltinAttributeInterfaces();
void registerTestCallGraphPass();		void registerTestCallGraphPass();
void registerTestConstantFold();		void registerTestConstantFold();
void registerTestControlFlowSink();		void registerTestControlFlowSink();
void registerTestGpuSerializeToCubinPass();		void registerTestGpuSerializeToCubinPass();
void registerTestGpuSerializeToHsacoPass();		void registerTestGpuSerializeToHsacoPass();
void registerTestDataFlowPass();
void registerTestDataLayoutQuery();		void registerTestDataLayoutQuery();
void registerTestDeadCodeAnalysisPass();		void registerTestDeadCodeAnalysisPass();
void registerTestDecomposeCallGraphTypes();		void registerTestDecomposeCallGraphTypes();
void registerTestDiagnosticsPass();		void registerTestDiagnosticsPass();
void registerTestDominancePass();		void registerTestDominancePass();
void registerTestDynamicPipelinePass();		void registerTestDynamicPipelinePass();
void registerTestExpandMathPass();		void registerTestExpandMathPass();
void registerTestFooAnalysisPass();		void registerTestFooAnalysisPass();
▲ Show 20 Lines • Show All 86 Lines • ▼ Show 20 Lines	void registerTestPasses() {
mlir::test::registerTestDiagnosticsPass();		mlir::test::registerTestDiagnosticsPass();
#if MLIR_CUDA_CONVERSIONS_ENABLED		#if MLIR_CUDA_CONVERSIONS_ENABLED
mlir::test::registerTestGpuSerializeToCubinPass();		mlir::test::registerTestGpuSerializeToCubinPass();
#endif		#endif
#if MLIR_ROCM_CONVERSIONS_ENABLED		#if MLIR_ROCM_CONVERSIONS_ENABLED
mlir::test::registerTestGpuSerializeToHsacoPass();		mlir::test::registerTestGpuSerializeToHsacoPass();
#endif		#endif
mlir::test::registerTestDecomposeCallGraphTypes();		mlir::test::registerTestDecomposeCallGraphTypes();
mlir::test::registerTestDataFlowPass();
mlir::test::registerTestDataLayoutQuery();		mlir::test::registerTestDataLayoutQuery();
mlir::test::registerTestDeadCodeAnalysisPass();		mlir::test::registerTestDeadCodeAnalysisPass();
mlir::test::registerTestDominancePass();		mlir::test::registerTestDominancePass();
mlir::test::registerTestDynamicPipelinePass();		mlir::test::registerTestDynamicPipelinePass();
mlir::test::registerTestExpandMathPass();		mlir::test::registerTestExpandMathPass();
mlir::test::registerTestFooAnalysisPass();		mlir::test::registerTestFooAnalysisPass();
mlir::test::registerTestComposeSubView();		mlir::test::registerTestComposeSubView();
mlir::test::registerTestMultiBuffering();		mlir::test::registerTestMultiBuffering();
▲ Show 20 Lines • Show All 52 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Delete ForwardDataFlowAnalysisClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 443132

mlir/include/mlir/Analysis/DataFlowAnalysis.h

mlir/lib/Analysis/CMakeLists.txt

mlir/lib/Analysis/DataFlowAnalysis.cpp

mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp

mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp

mlir/test/Analysis/test-data-flow.mlir

mlir/test/lib/Analysis/CMakeLists.txt

mlir/test/lib/Analysis/TestDataFlow.cpp

mlir/tools/mlir-opt/mlir-opt.cpp

[mlir] Delete ForwardDataFlowAnalysis
ClosedPublic