Author: Mogball Date: 2022-06-29T10:51:15-07:00 New Revision: df33ad34c5a0f3cf1e6ab28c63a6d0df5c8d77df
URL: https://github.com/llvm/llvm-project/commit/df33ad34c5a0f3cf1e6ab28c63a6d0df5c8d77df DIFF: https://github.com/llvm/llvm-project/commit/df33ad34c5a0f3cf1e6ab28c63a6d0df5c8d77df.diff LOG: [deadcode analysis] move all the files around Added: mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp Modified: mlir/lib/Analysis/CMakeLists.txt mlir/test/lib/Analysis/CMakeLists.txt Removed: mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h mlir/lib/Analysis/SparseDataFlowAnalysis.cpp mlir/test/Analysis/test-dead-code-analysis.mlir mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp ################################################################################ diff --git a/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h new file mode 100644 index 0000000000000..5e04516e310b1 --- /dev/null +++ b/mlir/include/mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h @@ -0,0 +1,66 @@ +//===- ConstantPropagationAnalysis.h - Constant propagation analysis ------===// +// +// 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 implements constant propagation analysis. In this file are defined +// the lattice value class that represents constant values in the program and +// a sparse constant propagation analysis that uses operation folders to +// speculate about constant values in the program. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H +#define MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H + +#include "mlir/Analysis/DataFlow/SparseAnalysis.h" + +namespace mlir { +namespace dataflow { + +//===----------------------------------------------------------------------===// +// ConstantValue +//===----------------------------------------------------------------------===// + +/// This lattice value represents a known constant value of a lattice. +class ConstantValue { +public: + /// Construct a constant value with a known constant. + ConstantValue(Attribute knownValue = {}, Dialect *dialect = nullptr) + : constant(knownValue), dialect(dialect) {} + + /// Get the constant value. Returns null if no value was determined. + Attribute getConstantValue() const { return constant; } + + /// Get the dialect instance that can be used to materialize the constant. + Dialect *getConstantDialect() const { return dialect; } + + /// Compare the constant values. + bool operator==(const ConstantValue &rhs) const { + return constant == rhs.constant; + } + + /// The union with another constant value is null if they are diff erent, and + /// the same if they are the same. + static ConstantValue join(const ConstantValue &lhs, + const ConstantValue &rhs) { + return lhs == rhs ? lhs : ConstantValue(); + } + + /// Print the constant value. + void print(raw_ostream &os) const; + +private: + /// The constant value. + Attribute constant; + /// An dialect instance that can be used to materialize the constant. + Dialect *dialect; +}; + +} // end namespace dataflow +} // end namespace mlir + +#endif // MLIR_ANALYSIS_DATAFLOW_CONSTANTPROPAGATIONANALYSIS_H diff --git a/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h new file mode 100644 index 0000000000000..df8e445d8ea11 --- /dev/null +++ b/mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h @@ -0,0 +1,229 @@ +//===- DeadCodeAnalysis.h - Dead code analysis ----------------------------===// +// +// 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 implements dead code analysis using the data-flow analysis +// framework. This analysis uses the results of constant propagation to +// determine live blocks, control-flow edges, and control-flow predecessors. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H +#define MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H + +#include "mlir/Analysis/DataFlowFramework.h" +#include "mlir/IR/SymbolTable.h" +#include "mlir/Interfaces/CallInterfaces.h" +#include "mlir/Interfaces/ControlFlowInterfaces.h" +#include "llvm/ADT/SmallPtrSet.h" + +namespace mlir { +namespace dataflow { + +//===----------------------------------------------------------------------===// +// Executable +//===----------------------------------------------------------------------===// + +/// This is a simple analysis state that represents whether the associated +/// program point (either a block or a control-flow edge) is live. +class Executable : public AnalysisState { +public: + using AnalysisState::AnalysisState; + + /// The state is initialized by default. + bool isUninitialized() const override { return false; } + + /// The state is always initialized. + ChangeResult defaultInitialize() override { return ChangeResult::NoChange; } + + /// Set the state of the program point to live. + ChangeResult setToLive(); + + /// Get whether the program point is live. + bool isLive() const { return live; } + + /// Print the liveness. + void print(raw_ostream &os) const override; + + /// When the state of the program point is changed to live, re-invoke + /// subscribed analyses on the operations in the block and on the block + /// itself. + void onUpdate(DataFlowSolver *solver) const override; + + /// Subscribe an analysis to changes to the liveness. + void blockContentSubscribe(DataFlowAnalysis *analysis) { + subscribers.insert(analysis); + } + +private: + /// Whether the program point is live. Optimistically assume that the program + /// point is dead. + bool live = false; + + /// A set of analyses that should be updated when this state changes. + SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>, + SmallPtrSet<DataFlowAnalysis *, 4>> + subscribers; +}; + +//===----------------------------------------------------------------------===// +// PredecessorState +//===----------------------------------------------------------------------===// + +/// This analysis state represents a set of live control-flow "predecessors" of +/// a program point (either an operation or a block), which are the last +/// operations along all execution paths that pass through this point. +/// +/// For example, in dead-code analysis, an operation with region control-flow +/// can be the predecessor of a region's entry block or itself, the exiting +/// terminator of a region can be the predecessor of the parent operation or +/// another region's entry block, the callsite of a callable operation can be +/// the predecessor to its entry block, and the exiting terminator or a callable +/// operation can be the predecessor of the call operation. +/// +/// The state can indicate that it is underdefined, meaning that not all live +/// control-flow predecessors can be known. +class PredecessorState : public AnalysisState { +public: + using AnalysisState::AnalysisState; + + /// The state is initialized by default. + bool isUninitialized() const override { return false; } + + /// The state is always initialized. + ChangeResult defaultInitialize() override { return ChangeResult::NoChange; } + + /// Print the known predecessors. + void print(raw_ostream &os) const override; + + /// Returns true if all predecessors are known. + bool allPredecessorsKnown() const { return allKnown; } + + /// Indicate that there are potentially unknown predecessors. + ChangeResult setHasUnknownPredecessors() { + return std::exchange(allKnown, false) ? ChangeResult::Change + : ChangeResult::NoChange; + } + + /// Get the known predecessors. + ArrayRef<Operation *> getKnownPredecessors() const { + return knownPredecessors.getArrayRef(); + } + + /// Add a known predecessor. + ChangeResult join(Operation *predecessor) { + return knownPredecessors.insert(predecessor) ? ChangeResult::Change + : ChangeResult::NoChange; + } + +private: + /// Whether all predecessors are known. Optimistically assume that we know + /// all predecessors. + bool allKnown = true; + + /// The known control-flow predecessors of this program point. + SetVector<Operation *, SmallVector<Operation *, 4>, + SmallPtrSet<Operation *, 4>> + knownPredecessors; +}; + +//===----------------------------------------------------------------------===// +// CFGEdge +//===----------------------------------------------------------------------===// + +/// This program point represents a control-flow edge between a block and one +/// of its successors. +class CFGEdge + : public GenericProgramPointBase<CFGEdge, std::pair<Block *, Block *>> { +public: + using Base::Base; + + /// Get the block from which the edge originates. + Block *getFrom() const { return getValue().first; } + /// Get the target block. + Block *getTo() const { return getValue().second; } + + /// Print the blocks between the control-flow edge. + void print(raw_ostream &os) const override; + /// Get a fused location of both blocks. + Location getLoc() const override; +}; + +//===----------------------------------------------------------------------===// +// DeadCodeAnalysis +//===----------------------------------------------------------------------===// + +/// Dead code analysis analyzes control-flow, as understood by +/// `RegionBranchOpInterface` and `BranchOpInterface`, and the callgraph, as +/// understood by `CallableOpInterface` and `CallOpInterface`. +/// +/// This analysis uses known constant values of operands to determine the +/// liveness of each block and each edge between a block and its predecessors. +/// For region control-flow, this analysis determines the predecessor operations +/// for region entry blocks and region control-flow operations. For the +/// callgraph, this analysis determines the callsites and live returns of every +/// function. +class DeadCodeAnalysis : public DataFlowAnalysis { +public: + explicit DeadCodeAnalysis(DataFlowSolver &solver); + + /// Initialize the analysis by visiting every operation with potential + /// control-flow semantics. + LogicalResult initialize(Operation *top) override; + + /// Visit an operation with control-flow semantics and deduce which of its + /// successors are live. + LogicalResult visit(ProgramPoint point) override; + +private: + /// Find and mark symbol callables with potentially unknown callsites as + /// having overdefined predecessors. `top` is the top-level operation that the + /// analysis is operating on. + void initializeSymbolCallables(Operation *top); + + /// Recursively Initialize the analysis on nested regions. + LogicalResult initializeRecursively(Operation *op); + + /// Visit the given call operation and compute any necessary lattice state. + void visitCallOperation(CallOpInterface call); + + /// Visit the given branch operation with successors and try to determine + /// which are live from the current block. + void visitBranchOperation(BranchOpInterface branch); + + /// 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); + + /// Visit the given terminator operation that exits a region under an + /// operation with control-flow semantics. These are terminators with no CFG + /// successors. + void visitRegionTerminator(Operation *op, RegionBranchOpInterface branch); + + /// Visit the given terminator operation that exits a callable region. These + /// are terminators with no CFG successors. + void visitCallableTerminator(Operation *op, CallableOpInterface callable); + + /// Mark the edge between `from` and `to` as executable. + void markEdgeLive(Block *from, Block *to); + + /// Mark the entry blocks of the operation as executable. + void markEntryBlocksLive(Operation *op); + + /// Get the constant values of the operands of the operation. Returns none if + /// any of the operand lattices are uninitialized. + Optional<SmallVector<Attribute>> getOperandValues(Operation *op); + + /// A symbol table used for O(1) symbol lookups during simplification. + SymbolTableCollection symbolTable; +}; + +} // end namespace dataflow +} // end namespace mlir + +#endif // MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H diff --git a/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h new file mode 100644 index 0000000000000..f15416a9cfad2 --- /dev/null +++ b/mlir/include/mlir/Analysis/DataFlow/SparseAnalysis.h @@ -0,0 +1,185 @@ +//===- SparseAnalysis.h - Sparse data-flow analysis -----------------------===// +// +// 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 implements sparse data-flow analysis using the data-flow analysis +// framework. The analysis is forward and conditional and uses the results of +// dead code analysis to prune dead code during the analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H +#define MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H + +#include "mlir/Analysis/DataFlowFramework.h" +#include "llvm/ADT/SmallPtrSet.h" + +namespace mlir { +namespace dataflow { + +//===----------------------------------------------------------------------===// +// AbstractSparseLattice +//===----------------------------------------------------------------------===// + +/// This class represents an abstract lattice. A lattice contains information +/// about an SSA value and is what's propagated across the IR by sparse +/// data-flow analysis. +class AbstractSparseLattice : public AnalysisState { +public: + /// Lattices can only be created for values. + AbstractSparseLattice(Value value) : AnalysisState(value) {} + + /// Join the information contained in 'rhs' into this lattice. Returns + /// if the value of the lattice changed. + virtual ChangeResult join(const AbstractSparseLattice &rhs) = 0; + + /// Returns true if the lattice element is at fixpoint and further calls to + /// `join` will not update the value of the element. + virtual bool isAtFixpoint() const = 0; + + /// Mark the lattice element as having reached a pessimistic fixpoint. This + /// means that the lattice may potentially have conflicting value states, and + /// only the most conservative value should be relied on. + virtual ChangeResult markPessimisticFixpoint() = 0; + + /// When the lattice gets updated, propagate an update to users of the value + /// using its use-def chain to subscribed analyses. + void onUpdate(DataFlowSolver *solver) const override; + + /// Subscribe an analysis to updates of the lattice. When the lattice changes, + /// subscribed analyses are re-invoked on all users of the value. This is + /// more efficient than relying on the dependency map. + void useDefSubscribe(DataFlowAnalysis *analysis) { + useDefSubscribers.insert(analysis); + } + +private: + /// A set of analyses that should be updated when this lattice changes. + SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>, + SmallPtrSet<DataFlowAnalysis *, 4>> + useDefSubscribers; +}; + +//===----------------------------------------------------------------------===// +// Lattice +//===----------------------------------------------------------------------===// + +/// 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. +/// * bool operator==(const ValueT &rhs) const; +/// +template <typename ValueT> +class Lattice : public AbstractSparseLattice { +public: + using AbstractSparseLattice::AbstractSparseLattice; + + /// Get a lattice element with a known value. + Lattice(const ValueT &knownValue = ValueT()) + : AbstractSparseLattice(Value()), 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 { + return const_cast<Lattice<ValueT> *>(this)->getValue(); + } + + /// Returns true if the value of this lattice hasn't yet been initialized. + bool isUninitialized() const override { return !optimisticValue.hasValue(); } + /// Force the initialization of the element by setting it to its pessimistic + /// fixpoint. + ChangeResult defaultInitialize() override { + return markPessimisticFixpoint(); + } + + /// 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 override { return optimisticValue == knownValue; } + + /// Join the information contained in the 'rhs' lattice into this + /// lattice. Returns if the state of the current lattice changed. + ChangeResult join(const AbstractSparseLattice &rhs) override { + const Lattice<ValueT> &rhsLattice = + static_cast<const Lattice<ValueT> &>(rhs); + + // If 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() override { + 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; + } + + /// Print the lattice element. + void print(raw_ostream &os) const override { + os << "["; + knownValue.print(os); + os << ", "; + if (optimisticValue) + optimisticValue->print(os); + else + os << "<NULL>"; + os << "]"; + } + +private: + /// The value that is conservatively known to be true. + ValueT knownValue; + /// The currently computed value that is optimistically assumed to be true, + /// or None if the lattice element is uninitialized. + Optional<ValueT> optimisticValue; +}; + +} // end namespace dataflow +} // end namespace mlir + +#endif // MLIR_ANALYSIS_DATAFLOW_SPARSEANALYSIS_H diff --git a/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h b/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h deleted file mode 100644 index ee9392b387e60..0000000000000 --- a/mlir/include/mlir/Analysis/SparseDataFlowAnalysis.h +++ /dev/null @@ -1,418 +0,0 @@ -//===- SparseDataFlowAnalysis.h - Sparse data-flow analysis ---------------===// -// -// 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 implements sparse data-flow analysis using the data-flow analysis -// framework. The analysis is forward and conditional and uses the results of -// dead code analysis to prune dead code during the analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H -#define MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H - -#include "mlir/Analysis/DataFlowFramework.h" -#include "mlir/IR/SymbolTable.h" -#include "mlir/Interfaces/CallInterfaces.h" -#include "mlir/Interfaces/ControlFlowInterfaces.h" -#include "llvm/ADT/SmallPtrSet.h" - -namespace mlir { - -//===----------------------------------------------------------------------===// -// AbstractSparseLattice -//===----------------------------------------------------------------------===// - -/// This class represents an abstract lattice. A lattice contains information -/// about an SSA value and is what's propagated across the IR by sparse -/// data-flow analysis. -class AbstractSparseLattice : public AnalysisState { -public: - /// Lattices can only be created for values. - AbstractSparseLattice(Value value) : AnalysisState(value) {} - - /// Join the information contained in 'rhs' into this lattice. Returns - /// if the value of the lattice changed. - virtual ChangeResult join(const AbstractSparseLattice &rhs) = 0; - - /// Returns true if the lattice element is at fixpoint and further calls to - /// `join` will not update the value of the element. - virtual bool isAtFixpoint() const = 0; - - /// Mark the lattice element as having reached a pessimistic fixpoint. This - /// means that the lattice may potentially have conflicting value states, and - /// only the most conservative value should be relied on. - virtual ChangeResult markPessimisticFixpoint() = 0; - - /// When the lattice gets updated, propagate an update to users of the value - /// using its use-def chain to subscribed analyses. - void onUpdate(DataFlowSolver *solver) const override; - - /// Subscribe an analysis to updates of the lattice. When the lattice changes, - /// subscribed analyses are re-invoked on all users of the value. This is - /// more efficient than relying on the dependency map. - void useDefSubscribe(DataFlowAnalysis *analysis) { - useDefSubscribers.insert(analysis); - } - -private: - /// A set of analyses that should be updated when this lattice changes. - SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>, - SmallPtrSet<DataFlowAnalysis *, 4>> - useDefSubscribers; -}; - -//===----------------------------------------------------------------------===// -// Lattice -//===----------------------------------------------------------------------===// - -/// 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. -/// * bool operator==(const ValueT &rhs) const; -/// -template <typename ValueT> -class Lattice : public AbstractSparseLattice { -public: - using AbstractSparseLattice::AbstractSparseLattice; - - /// Get a lattice element with a known value. - Lattice(const ValueT &knownValue = ValueT()) - : AbstractSparseLattice(Value()), 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 { - return const_cast<Lattice<ValueT> *>(this)->getValue(); - } - - /// Returns true if the value of this lattice hasn't yet been initialized. - bool isUninitialized() const override { return !optimisticValue.hasValue(); } - /// Force the initialization of the element by setting it to its pessimistic - /// fixpoint. - ChangeResult defaultInitialize() override { - return markPessimisticFixpoint(); - } - - /// 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 override { return optimisticValue == knownValue; } - - /// Join the information contained in the 'rhs' lattice into this - /// lattice. Returns if the state of the current lattice changed. - ChangeResult join(const AbstractSparseLattice &rhs) override { - const Lattice<ValueT> &rhsLattice = - static_cast<const Lattice<ValueT> &>(rhs); - - // If 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() override { - 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; - } - - /// Print the lattice element. - void print(raw_ostream &os) const override { - os << "["; - knownValue.print(os); - os << ", "; - if (optimisticValue) { - optimisticValue->print(os); - } else { - os << "<NULL>"; - } - os << "]"; - } - -private: - /// The value that is conservatively known to be true. - ValueT knownValue; - /// The currently computed value that is optimistically assumed to be true, - /// or None if the lattice element is uninitialized. - Optional<ValueT> optimisticValue; -}; - -//===----------------------------------------------------------------------===// -// Executable -//===----------------------------------------------------------------------===// - -/// This is a simple analysis state that represents whether the associated -/// program point (either a block or a control-flow edge) is live. -class Executable : public AnalysisState { -public: - using AnalysisState::AnalysisState; - - /// The state is initialized by default. - bool isUninitialized() const override { return false; } - - /// The state is always initialized. - ChangeResult defaultInitialize() override { return ChangeResult::NoChange; } - - /// Set the state of the program point to live. - ChangeResult setToLive(); - - /// Get whether the program point is live. - bool isLive() const { return live; } - - /// Print the liveness; - void print(raw_ostream &os) const override; - - /// When the state of the program point is changed to live, re-invoke - /// subscribed analyses on the operations in the block and on the block - /// itself. - void onUpdate(DataFlowSolver *solver) const override; - - /// Subscribe an analysis to changes to the liveness. - void blockContentSubscribe(DataFlowAnalysis *analysis) { - subscribers.insert(analysis); - } - -private: - /// Whether the program point is live. Optimistically assume that the program - /// point is dead. - bool live = false; - - /// A set of analyses that should be updated when this state changes. - SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>, - SmallPtrSet<DataFlowAnalysis *, 4>> - subscribers; -}; - -//===----------------------------------------------------------------------===// -// ConstantValue -//===----------------------------------------------------------------------===// - -/// This lattice value represents a known constant value of a lattice. -class ConstantValue { -public: - /// Construct a constant value with a known constant. - ConstantValue(Attribute knownValue = {}, Dialect *dialect = nullptr) - : constant(knownValue), dialect(dialect) {} - - /// Get the constant value. Returns null if no value was determined. - Attribute getConstantValue() const { return constant; } - - /// Get the dialect instance that can be used to materialize the constant. - Dialect *getConstantDialect() const { return dialect; } - - /// Compare the constant values. - bool operator==(const ConstantValue &rhs) const { - return constant == rhs.constant; - } - - /// The union with another constant value is null if they are diff erent, and - /// the same if they are the same. - static ConstantValue join(const ConstantValue &lhs, - const ConstantValue &rhs) { - return lhs == rhs ? lhs : ConstantValue(); - } - - /// Print the constant value. - void print(raw_ostream &os) const; - -private: - /// The constant value. - Attribute constant; - /// An dialect instance that can be used to materialize the constant. - Dialect *dialect; -}; - -//===----------------------------------------------------------------------===// -// PredecessorState -//===----------------------------------------------------------------------===// - -/// This analysis state represents a set of known predecessors. This state is -/// used in sparse data-flow analysis to reason about region control-flow and -/// callgraphs. The state may also indicate that not all predecessors can be -/// known, if for example not all callsites of a callable are visible. -class PredecessorState : public AnalysisState { -public: - using AnalysisState::AnalysisState; - - /// The state is initialized by default. - bool isUninitialized() const override { return false; } - - /// The state is always initialized. - ChangeResult defaultInitialize() override { return ChangeResult::NoChange; } - - /// Print the known predecessors. - void print(raw_ostream &os) const override; - - /// Returns true if all predecessors are known. - bool allPredecessorsKnown() const { return allKnown; } - - /// Indicate that there are potentially unknown predecessors. - ChangeResult setHasUnknownPredecessors() { - if (!allKnown) - return ChangeResult::NoChange; - allKnown = false; - return ChangeResult::Change; - } - - /// Get the known predecessors. - ArrayRef<Operation *> getKnownPredecessors() const { - return knownPredecessors.getArrayRef(); - } - - /// Add a known predecessor. - ChangeResult join(Operation *predecessor) { - return knownPredecessors.insert(predecessor) ? ChangeResult::Change - : ChangeResult::NoChange; - } - -private: - /// Whether all predecessors are known. Optimistically assume that we know - /// all predecessors. - bool allKnown = true; - - /// The known control-flow predecessors of this program point. - SetVector<Operation *, SmallVector<Operation *, 4>, - SmallPtrSet<Operation *, 4>> - knownPredecessors; -}; - -//===----------------------------------------------------------------------===// -// CFGEdge -//===----------------------------------------------------------------------===// - -/// This program point represents a control-flow edge between a block and one -/// of its successors. -class CFGEdge - : public GenericProgramPointBase<CFGEdge, std::pair<Block *, Block *>> { -public: - using Base::Base; - - /// Get the block from which the edge originates. - Block *getFrom() const { return getValue().first; } - /// Get the target block. - Block *getTo() const { return getValue().second; } - - /// Print the blocks between the control-flow edge. - void print(raw_ostream &os) const override; - /// Get a fused location of both blocks. - Location getLoc() const override; -}; - -//===----------------------------------------------------------------------===// -// DeadCodeAnalysis -//===----------------------------------------------------------------------===// - -/// Dead code analysis analyzes control-flow, as understood by -/// `RegionBranchOpInterface` and `BranchOpInterface`, and the callgraph, as -/// understood by `CallableOpInterface` and `CallOpInterface`. -/// -/// This analysis uses known constant values of operands to determine the -/// liveness of each block and each edge between a block and its predecessors. -/// For region control-flow, this analysis determines the predecessor operations -/// for region entry blocks and region control-flow operations. For the -/// callgraph, this analysis determines the callsites and live returns of every -/// function. -class DeadCodeAnalysis : public DataFlowAnalysis { -public: - explicit DeadCodeAnalysis(DataFlowSolver &solver); - - /// Initialize the analysis by visiting every operation with potential - /// control-flow semantics. - LogicalResult initialize(Operation *top) override; - - /// Visit an operation with control-flow semantics and deduce which of its - /// successors are live. - LogicalResult visit(ProgramPoint point) override; - -private: - /// Find and mark symbol callables with potentially unknown callsites as - /// having overdefined predecessors. `top` is the top-level operation that the - /// analysis is operating on. - void initializeSymbolCallables(Operation *top); - - /// Recursively Initialize the analysis on nested regions. - LogicalResult initializeRecursively(Operation *op); - - /// Visit the given call operation and compute any necessary lattice state. - void visitCallOperation(CallOpInterface call); - - /// Visit the given branch operation with successors and try to determine - /// which are live from the current block. - void visitBranchOperation(BranchOpInterface branch); - - /// 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); - - /// Visit the given terminator operation that exits a region under an - /// operation with control-flow semantics. These are terminators with no CFG - /// successors. - void visitRegionTerminator(Operation *op, RegionBranchOpInterface branch); - - /// Visit the given terminator operation that exits a callable region. These - /// are terminators with no CFG successors. - void visitCallableTerminator(Operation *op, CallableOpInterface callable); - - /// Mark the edge between `from` and `to` as executable. - void markEdgeLive(Block *from, Block *to); - - /// Mark the entry blocks of the operation as executable. - void markEntryBlocksLive(Operation *op); - - /// Get the constant values of the operands of the operation. Returns none if - /// any of the operand lattices are uninitialized. - Optional<SmallVector<Attribute>> getOperandValues(Operation *op); - - /// A symbol table used for O(1) symbol lookups during simplification. - SymbolTableCollection symbolTable; -}; - -} // end namespace mlir - -#endif // MLIR_ANALYSIS_SPARSEDATAFLOWANALYSIS_H diff --git a/mlir/lib/Analysis/CMakeLists.txt b/mlir/lib/Analysis/CMakeLists.txt index 662bc1084c5ff..2e37135adac44 100644 --- a/mlir/lib/Analysis/CMakeLists.txt +++ b/mlir/lib/Analysis/CMakeLists.txt @@ -7,9 +7,12 @@ set(LLVM_OPTIONAL_SOURCES IntRangeAnalysis.cpp Liveness.cpp SliceAnalysis.cpp - SparseDataFlowAnalysis.cpp AliasAnalysis/LocalAliasAnalysis.cpp + + DataFlow/ConstantPropagationAnalysis.cpp + DataFlow/DeadCodeAnalysis.cpp + DataFlow/SparseAnalysis.cpp ) add_mlir_library(MLIRAnalysis @@ -22,10 +25,13 @@ add_mlir_library(MLIRAnalysis IntRangeAnalysis.cpp Liveness.cpp SliceAnalysis.cpp - SparseDataFlowAnalysis.cpp AliasAnalysis/LocalAliasAnalysis.cpp + DataFlow/ConstantPropagationAnalysis.cpp + DataFlow/DeadCodeAnalysis.cpp + DataFlow/SparseAnalysis.cpp + ADDITIONAL_HEADER_DIRS ${MLIR_MAIN_INCLUDE_DIR}/mlir/Analysis diff --git a/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp new file mode 100644 index 0000000000000..f97f8ccdb8649 --- /dev/null +++ b/mlir/lib/Analysis/DataFlow/ConstantPropagationAnalysis.cpp @@ -0,0 +1,22 @@ +//===- ConstantPropagationAnalysis.cpp - Constant propagation analysis ----===// +// +// 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/DataFlow/ConstantPropagationAnalysis.h" + +using namespace mlir; +using namespace mlir::dataflow; + +//===----------------------------------------------------------------------===// +// ConstantValue +//===----------------------------------------------------------------------===// + +void ConstantValue::print(raw_ostream &os) const { + if (constant) + return constant.print(os); + os << "<NO VALUE>"; +} diff --git a/mlir/lib/Analysis/SparseDataFlowAnalysis.cpp b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp similarity index 93% rename from mlir/lib/Analysis/SparseDataFlowAnalysis.cpp rename to mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp index 41ff8381b0749..20c3b55f32934 100644 --- a/mlir/lib/Analysis/SparseDataFlowAnalysis.cpp +++ b/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp @@ -1,4 +1,4 @@ -//===- SparseDataFlowAnalysis.cpp - Sparse data-flow analysis -------------===// +//===- DeadCodeAnalysis.cpp - Dead code analysis --------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,22 +6,11 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/SparseDataFlowAnalysis.h" - -#define DEBUG_TYPE "dataflow" +#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h" +#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h" using namespace mlir; - -//===----------------------------------------------------------------------===// -// AbstractSparseLattice -//===----------------------------------------------------------------------===// - -void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const { - // Push all users of the value to the queue. - for (Operation *user : point.get<Value>().getUsers()) - for (DataFlowAnalysis *analysis : useDefSubscribers) - solver->enqueue({user, analysis}); -} +using namespace mlir::dataflow; //===----------------------------------------------------------------------===// // Executable @@ -49,22 +38,13 @@ void Executable::onUpdate(DataFlowSolver *solver) const { solver->enqueue({&op, analysis}); } else if (auto *programPoint = point.dyn_cast<GenericProgramPoint *>()) { // Re-invoke the analysis on the successor block. - if (auto *edge = dyn_cast<CFGEdge>(programPoint)) + if (auto *edge = dyn_cast<CFGEdge>(programPoint)) { for (DataFlowAnalysis *analysis : subscribers) solver->enqueue({edge->getTo(), analysis}); + } } } -//===----------------------------------------------------------------------===// -// ConstantValue -//===----------------------------------------------------------------------===// - -void ConstantValue::print(raw_ostream &os) const { - if (constant) - return constant.print(os); - os << "<NO VALUE>"; -} - //===----------------------------------------------------------------------===// // PredecessorState //===----------------------------------------------------------------------===// @@ -350,7 +330,6 @@ void DeadCodeAnalysis::visitRegionBranchOperation( SmallVector<RegionSuccessor> successors; branch.getSuccessorRegions(/*index=*/{}, *operands, successors); - for (const RegionSuccessor &successor : successors) { // Mark the entry block as executable. Region *region = successor.getSuccessor(); diff --git a/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp new file mode 100644 index 0000000000000..e2640280fffd2 --- /dev/null +++ b/mlir/lib/Analysis/DataFlow/SparseAnalysis.cpp @@ -0,0 +1,23 @@ +//===- SparseAnalysis.cpp - Sparse data-flow analysis ---------------------===// +// +// 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/DataFlow/SparseAnalysis.h" + +using namespace mlir; +using namespace mlir::dataflow; + +//===----------------------------------------------------------------------===// +// AbstractSparseLattice +//===----------------------------------------------------------------------===// + +void AbstractSparseLattice::onUpdate(DataFlowSolver *solver) const { + // Push all users of the value to the queue. + for (Operation *user : point.get<Value>().getUsers()) + for (DataFlowAnalysis *analysis : useDefSubscribers) + solver->enqueue({user, analysis}); +} diff --git a/mlir/test/Analysis/test-dead-code-analysis.mlir b/mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir similarity index 100% rename from mlir/test/Analysis/test-dead-code-analysis.mlir rename to mlir/test/Analysis/DataFlow/test-dead-code-analysis.mlir diff --git a/mlir/test/lib/Analysis/CMakeLists.txt b/mlir/test/lib/Analysis/CMakeLists.txt index 128615659cf30..8e9446c78bfc2 100644 --- a/mlir/test/lib/Analysis/CMakeLists.txt +++ b/mlir/test/lib/Analysis/CMakeLists.txt @@ -4,7 +4,6 @@ add_mlir_library(MLIRTestAnalysis TestCallGraph.cpp TestDataFlow.cpp TestDataFlowFramework.cpp - TestDeadCodeAnalysis.cpp TestLiveness.cpp TestMatchReduction.cpp TestMemRefBoundCheck.cpp @@ -12,6 +11,7 @@ add_mlir_library(MLIRTestAnalysis TestMemRefStrideCalculation.cpp TestSlice.cpp + DataFlow/TestDeadCodeAnalysis.cpp EXCLUDE_FROM_LIBMLIR diff --git a/mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp b/mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp similarity index 96% rename from mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp rename to mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp index a7c33526c80de..8106c94d57368 100644 --- a/mlir/test/lib/Analysis/TestDeadCodeAnalysis.cpp +++ b/mlir/test/lib/Analysis/DataFlow/TestDeadCodeAnalysis.cpp @@ -6,11 +6,13 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/SparseDataFlowAnalysis.h" +#include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h" +#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h" #include "mlir/IR/Matchers.h" #include "mlir/Pass/Pass.h" using namespace mlir; +using namespace mlir::dataflow; /// Print the liveness of every block, control-flow edge, and the predecessors /// of all regions, callables, and calls. _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits