diff --git a/mlir/include/mlir/Analysis/DataFlowAnalysis.h b/mlir/include/mlir/Analysis/DataFlowAnalysis.h --- a/mlir/include/mlir/Analysis/DataFlowAnalysis.h +++ b/mlir/include/mlir/Analysis/DataFlowAnalysis.h @@ -1,428 +0,0 @@ -//===- 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 -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 &rhsLattice = - static_cast &>(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 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 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 operands, - SmallVectorImpl &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 sourceIndex, - ArrayRef operands, - SmallVectorImpl &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 ®ion, - ArrayRef 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 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 -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 *lookupLatticeElement(Value value) { - return static_cast *>( - 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 &getLatticeElement(Value value) { - return static_cast &>( - 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 *> 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 *> operands, - SmallVectorImpl &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 sourceIndex, - ArrayRef *> operands, - SmallVectorImpl &successors) { - SmallVector 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 *> operands) { - ChangeResult result = ChangeResult::NoChange; - Region *region = successor.getSuccessor(); - ValueRange succArgs = successor.getSuccessorInputs(); - Block *block = ®ion->front(); - Block::BlockArgListType arguments = block->getArguments(); - if (arguments.size() != succArgs.size()) { - unsigned firstArgIdx = - succArgs.empty() ? 0 - : succArgs[0].cast().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 operands) final { - LatticeElement *const *derivedOperandBase = - reinterpret_cast *const *>(operands.data()); - return visitOperation( - op, llvm::makeArrayRef(derivedOperandBase, operands.size())); - } - LogicalResult - getSuccessorsForOperands(BranchOpInterface branch, - ArrayRef operands, - SmallVectorImpl &successors) final { - LatticeElement *const *derivedOperandBase = - reinterpret_cast *const *>(operands.data()); - return getSuccessorsForOperands( - branch, llvm::makeArrayRef(derivedOperandBase, operands.size()), - successors); - } - void - getSuccessorsForOperands(RegionBranchOpInterface branch, - Optional sourceIndex, - ArrayRef operands, - SmallVectorImpl &successors) final { - LatticeElement *const *derivedOperandBase = - reinterpret_cast *const *>(operands.data()); - getSuccessorsForOperands( - branch, sourceIndex, - llvm::makeArrayRef(derivedOperandBase, operands.size()), successors); - } - ChangeResult visitNonControlFlowArguments( - Operation *op, const RegionSuccessor ®ion, - ArrayRef operands) final { - LatticeElement *const *derivedOperandBase = - reinterpret_cast *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(knownValue); - } - - /// An allocator used for new lattice elements. - llvm::SpecificBumpPtrAllocator> allocator; - - /// The MLIRContext of this solver. - MLIRContext *context; -}; - -} // namespace mlir - -#endif // MLIR_ANALYSIS_DATAFLOWANALYSIS_H diff --git a/mlir/lib/Analysis/CMakeLists.txt b/mlir/lib/Analysis/CMakeLists.txt --- a/mlir/lib/Analysis/CMakeLists.txt +++ b/mlir/lib/Analysis/CMakeLists.txt @@ -2,7 +2,6 @@ AliasAnalysis.cpp BufferViewFlowAnalysis.cpp CallGraph.cpp - DataFlowAnalysis.cpp DataLayoutAnalysis.cpp Liveness.cpp SliceAnalysis.cpp diff --git a/mlir/lib/Analysis/DataFlowAnalysis.cpp b/mlir/lib/Analysis/DataFlowAnalysis.cpp --- a/mlir/lib/Analysis/DataFlowAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlowAnalysis.cpp @@ -1,818 +0,0 @@ -//===- 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 - -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 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 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 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 - 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 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 regionSuccessors, - ArrayRef operandLattices, - function_ref)> getInputsForRegion); - - /// Visit the given terminator operation and compute any necessary lattice - /// state. - void - visitTerminatorOperation(Operation *op, - ArrayRef 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 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 - void markAllPessimisticFixpoint(ValuesT values) { - for (auto value : values) - markPessimisticFixpoint(value); - } - template - void markAllPessimisticFixpoint(Operation *op, ValuesT values) { - markAllPessimisticFixpoint(values); - opWorklist.push(op); - } - template - 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 executableBlocks; - - /// The set of control flow edges that are known to execute. - DenseSet> executableEdges; - - /// A worklist containing blocks that need to be processed. - std::queue blockWorklist; - - /// A worklist of operations that need to be processed. - std::queue opWorklist; - - /// The callable operations that have their argument/result state tracked. - DenseMap 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 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 ®ion : 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(®ion, /*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()) { - // 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(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 ®ion : callable->getRegions()) - markEntryBlockExecutable(®ion, /*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 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(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 ®ion : it->first->getRegions()) - markEntryBlockExecutable(®ion, /*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 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()) - visitTerminatorOperation(op, operandLattices); - - // Process call operations. The call visitor processes result values, so we - // can exit afterwards. - if (CallOpInterface call = dyn_cast(op)) - return visitCallOperation(call); - - // Process callable operations. These are specially handled region operations - // that track dataflow via calls. - if (isa(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(op)) - return visitRegionBranchOperation(branch, operandLattices); - - for (Region ®ion : op->getRegions()) { - analysis.visitNonControlFlowArguments(op, RegionSuccessor(®ion), - 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(®ion, /*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 ®ion : op->getRegions()) - markEntryBlockExecutable(®ion, !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()) - 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 operandLattices) { - // Check to see which regions are executable. - SmallVector 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 index) { - return branch.getSuccessorEntryOperands(index); - }); -} - -void ForwardDataFlowSolver::visitRegionSuccessors( - Operation *parentOp, ArrayRef regionSuccessors, - ArrayRef operandLattices, - function_ref)> 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().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 = ®ion->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().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 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(parentOp)) - return visitCallableTerminatorOperation(parentOp, op, operandLattices); - - // Otherwise, check to see if the parent tracks region control flow. - auto regionInterface = dyn_cast(parentOp); - if (!regionInterface || !isBlockExecutable(parentOp->getBlock())) - return; - - // Query the set of successors of the current region using the current - // optimistic lattice state. - SmallVector 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 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(op)) { - SmallVector 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 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()) { - 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(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(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(®ion->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(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(); -} diff --git a/mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp b/mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp --- a/mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp +++ b/mlir/lib/Dialect/Tosa/Transforms/TosaInferShapes.cpp @@ -11,7 +11,6 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/DataFlowAnalysis.h" #include "mlir/Dialect/Func/IR/FuncOps.h" #include "mlir/Dialect/Tensor/IR/Tensor.h" #include "mlir/Dialect/Tosa/IR/TosaOps.h" diff --git a/mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp b/mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp --- a/mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp +++ b/mlir/lib/Dialect/Transform/Transforms/CheckUses.cpp @@ -11,7 +11,6 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/DataFlowAnalysis.h" #include "mlir/Dialect/Transform/IR/TransformInterfaces.h" #include "mlir/Dialect/Transform/Transforms/Passes.h" #include "mlir/Interfaces/SideEffectInterfaces.h" diff --git a/mlir/test/Analysis/test-data-flow.mlir b/mlir/test/Analysis/test-data-flow.mlir deleted file mode 100644 --- a/mlir/test/Analysis/test-data-flow.mlir +++ /dev/null @@ -1,24 +0,0 @@ -// 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 - } -} diff --git a/mlir/test/lib/Analysis/CMakeLists.txt b/mlir/test/lib/Analysis/CMakeLists.txt --- a/mlir/test/lib/Analysis/CMakeLists.txt +++ b/mlir/test/lib/Analysis/CMakeLists.txt @@ -2,7 +2,6 @@ add_mlir_library(MLIRTestAnalysis TestAliasAnalysis.cpp TestCallGraph.cpp - TestDataFlow.cpp TestDataFlowFramework.cpp TestLiveness.cpp TestMatchReduction.cpp diff --git a/mlir/test/lib/Analysis/TestDataFlow.cpp b/mlir/test/lib/Analysis/TestDataFlow.cpp deleted file mode 100644 --- a/mlir/test/lib/Analysis/TestDataFlow.cpp +++ /dev/null @@ -1,127 +0,0 @@ -//===- 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 { - using ForwardDataFlowAnalysis::ForwardDataFlowAnalysis; - - ChangeResult - visitOperation(Operation *op, - ArrayRef *> 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 *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 &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 *> 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 = ®ion->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 &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> { - 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(); } -} // namespace test -} // namespace mlir diff --git a/mlir/tools/mlir-opt/mlir-opt.cpp b/mlir/tools/mlir-opt/mlir-opt.cpp --- a/mlir/tools/mlir-opt/mlir-opt.cpp +++ b/mlir/tools/mlir-opt/mlir-opt.cpp @@ -70,7 +70,6 @@ void registerTestControlFlowSink(); void registerTestGpuSerializeToCubinPass(); void registerTestGpuSerializeToHsacoPass(); -void registerTestDataFlowPass(); void registerTestDataLayoutQuery(); void registerTestDeadCodeAnalysisPass(); void registerTestDecomposeCallGraphTypes(); @@ -173,7 +172,6 @@ mlir::test::registerTestGpuSerializeToHsacoPass(); #endif mlir::test::registerTestDecomposeCallGraphTypes(); - mlir::test::registerTestDataFlowPass(); mlir::test::registerTestDataLayoutQuery(); mlir::test::registerTestDeadCodeAnalysisPass(); mlir::test::registerTestDominancePass();