diff --git a/mlir/include/mlir/Analysis/DataFlowFramework.h b/mlir/include/mlir/Analysis/DataFlowFramework.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/DataFlowFramework.h @@ -0,0 +1,452 @@ +//===- DataFlowFramework.h - A generic framework for 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 defines a generic framework for writing data-flow analysis in MLIR. +// The framework consists of a solver that runs the fixed-point iteration and +// manages analysis dependencies and a data-flow analysis class for implementing +// specific analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H +#define MLIR_ANALYSIS_DATAFLOWFRAMEWORK_H + +#include "mlir/Analysis/DataFlowAnalysis.h" +#include "mlir/IR/Operation.h" +#include "mlir/Support/StorageUniquer.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/Support/TypeName.h" +#include +#include + +namespace mlir { + +/// Forward declare the analysis state class. +class AnalysisState; + +/// Abstract class for generic program points. In classical data-flow analysis, +/// programs points represent positions in a program to which lattice elements +/// are attached. In sparse data-flow analysis, these can be SSA values, and in +/// dense data-flow analysis, these are the program points before and after +/// every operation. +/// +/// In the general MLIR data-flow analysis framework, program points are an +/// extensible concept. Program points are uniquely identifiable objects to +/// which analysis states can be attached. The semantics of program points are +/// defined by the analyses that specify their transfer functions. +/// +/// Program points are implemented using MLIR's storage uniquer framework and +/// type ID system to provide RTTI. +class ProgramPoint : public StorageUniquer::BaseStorage { +public: + virtual ~ProgramPoint(); + + /// Create an abstract program point with type identifier. + explicit ProgramPoint(TypeID typeID) : typeID(typeID) {} + + /// Get the abstract program point's type identifier. + TypeID getTypeID() const { return typeID; } + + /// Get a derived source location for the program point. + virtual Location getLoc() const = 0; + + /// Print the program point. + virtual void print(llvm::raw_ostream &os) const = 0; + +private: + /// The type identifier of the program point. + TypeID typeID; + + /// A type-erased set of analysis states associated with this point. For + /// efficiency, they are stored directly on the program point. + DenseMap states; + + /// Allow the framework to access the analysis states. + friend class DataFlowSolver; +}; + +/// Base class for generic program points based on a concrete program point +/// type and a content key. This class defines the common methods required for +/// operability with the storage uniquer framework. +/// +/// The provided key type uniquely identifies the concrete program point +/// instance and are the data members of the class. +template +class ProgramPointBase : public BaseT { +public: + /// The concrete key type used by the storage uniquer. + using KeyTy = Key; + /// Alias for the base class. + using Base = ProgramPointBase; + + /// Construct an instance of the program point using the provided key and the + /// type ID of the concrete type. + template + explicit ProgramPointBase(KeyT &&key) + : BaseT(TypeID::get()), key(std::forward(key)) {} + + /// Get a uniqued instance of this program point class with the given + /// arguments. + template + static ConcreteT *get(StorageUniquer &uniquer, Args &&...args) { + return uniquer.get(/*initFn=*/{}, std::forward(args)...); + } + + /// Allocate space for a program point and construct it in-place. + template + static ConcreteT *construct(StorageUniquer::StorageAllocator &alloc, + KeyT &&key) { + return new (alloc.allocate()) ConcreteT(std::forward(key)); + } + + /// Two program points are equal if their keys are equal. + bool operator==(const KeyTy &key) const { return this->key == key; } + + /// Provide LLVM-style RTTI using type IDs. + static bool classof(const BaseT *point) { + return point->getTypeID() == TypeID::get(); + } + + /// Get the contents of the program point. + const KeyTy &getValue() const { return key; } + +private: + /// The program point key and contents. + KeyTy key; +}; + +/// Forward declaration of the data-flow analysis class. +class DataFlowAnalysis; + +/// The general data-flow analysis solver. This class is responsible for +/// orchestrating child data-flow analyses, running the fixed-point iteration +/// algorithm, managing analysis state and program point memory, and tracking +/// dependencies beteen analyses, program points, and analysis states. +/// +/// Steps to run a data-flow analysis: +/// +/// 1. Load and prime children analyses. Children analyses are instantiated in +/// the solver and "primed", building their dependency relations. +/// 2. Configure and run the analysis. The solver invokes the children analyses +/// according to their dependency relations until a fixed point is reached. +/// 3. Query analysis state results from the solver. +/// +/// TODO: Optimize the internal implementation of the solver. +class DataFlowSolver { +public: + /// Fundamental IR components are supported as first-class program points. + struct Point : public llvm::PointerUnion { + using ParentTy = llvm::PointerUnion; + /// Inherit constructors. + using ParentTy::PointerUnion; + /// Allow implicit conversion from the parent type. + Point(ParentTy point) : ParentTy(point) {} + + /// Print the program point. + void print(llvm::raw_ostream &os) const; + + /// Get the source location of the program point. + Location getLoc() const; + }; + + /// Load an analysis into the solver. Return the analysis instance. + template + AnalysisT *load(Args &&...args) { + AnalysisT *result = static_cast( + childAnalyses + .insert({TypeID::get(), + std::unique_ptr( + new AnalysisT(*this, std::forward(args)...))}) + .first->second.get()); +#ifndef NDEBUG + result->debugName = llvm::getTypeName(); +#endif // NDEBUG + return result; + } + + /// Prime the children analyses starting from the provided top-level + /// operation and run the analysis until fixpoint. + LogicalResult primeAndRun(Operation *top); + + /// Lookup an analysis state for the given program point. Returns null if one + /// does not exist. + template + const StateT *lookupState( + PointT point, + std::enable_if_t< + std::is_base_of>::value> + * = nullptr) const { + const AnalysisState *state = point->states.lookup(TypeID::get()); + return static_cast(state); + } + template + const StateT *lookupState( + PointT point, + std::enable_if_t< + !std::is_base_of>::value> + * = nullptr) const { + const AnalysisState *state = + analysisStates.lookup({point, TypeID::get()}); + return static_cast(state); + } + + /// Get a uniqued program point instance. If one is not present, it is + /// created with the provided arguments. + template + PointT *getProgramPoint(Args &&...args) { + uniquer.registerParametricStorageType(); + return PointT::get(uniquer, std::forward(args)...); + } + +protected: + /// Get the state associated with the given program point. If it does not + /// exist, create an uninitialized state. + template + StateT *getOrCreateState( + PointT point, + std::enable_if_t>::value> * = nullptr) { + AnalysisState *&state = point->states[TypeID::get()]; + if (!state) + state = createState(point); + return static_cast(state); + } + template + StateT *getOrCreateState( + PointT point, + std::enable_if_t>::value> * = nullptr) { + AnalysisState *&state = + analysisStates[{Point(point), TypeID::get()}]; + if (!state) + state = createState(point); + return static_cast(state); + } + + /// Propagate an update to an analysis state if it changed by pushing dependee + /// work items to the back of the queue. + void propagateIfChanged(AnalysisState *state, ChangeResult changed); + + /// Draw a dependency from an analysis state to a child analysis and program + /// point. If the state is updated, the child analysis must be invoked on the + /// given program point again. + void drawDependency(AnalysisState *state, DataFlowAnalysis *analysis, + Point point); + + /// Create an uninitialized analysis state of the given kind. Analysis states + /// are expected to be default-constructible to their uninitialized state. + template StateT *createState(PointT point); + +private: + /// A work item on the solver queue is a program point, child analysis pair. + /// Each item is processed by invoking the child analysis at the program + /// point. + using WorkItem = std::pair; + /// The solver's work queue. Work items can be inserted to the front of the + /// queue to be processed greedily, speeding up computations that otherwise + /// quickly degenerate to quadratic due to propagation of state updates. + std::queue worklist; + + /// Type-erased instances of the children analyses. + DenseMap> childAnalyses; + + /// The storage uniquer instance that owns the memory of the allocated program + /// points. + StorageUniquer uniquer; + + /// A type-erased "allocator" for analysis states. + std::list> stateAllocator; + + /// A type-erased map of program points to associated analysis states for + /// first-class program points. + DenseMap, AnalysisState *> analysisStates; + + /// Allow the base child analysis class to access the internals of the solver. + friend class DataFlowAnalysis; +}; + +/// Base class for generic analysis states. Analysis states contain data-flow +/// information that are attached to program points and which evolve as the +/// analysis iterates. +/// +/// This class places no restrictions on the semantics of analysis states beyond +/// these requirements. +/// +/// 1. Querying the state of a program point prior to visiting that point +/// results in uninitialized state. Analyses must be aware of unintialized +/// states. +/// 2. Analysis states can reach fixpoints, where subsequent updates will never +/// trigger a change in the state. +/// 3. Analysis states that are uninitialized can be forcefully initialized to a +/// default value. +class AnalysisState { +public: + virtual ~AnalysisState(); + + /// Returns true if the analysis state is uninitialized. + virtual bool isUninitialized() const = 0; + + /// Force an uninitialized analysis state to initialize itself with a default + /// value. + virtual ChangeResult defaultInitialize() = 0; + + /// Print the contents of the analysis state. + virtual void print(llvm::raw_ostream &os) const = 0; + +private: + /// The dependency relations originating from this analysis state. An entry + /// `state -> (analysis, point)` is created when `analysis` queries `state` + /// when updating `point`. + /// + /// When this state is updated, all dependee child analysis invocations are + /// pushed to the back of the queue. Use a `SetVector` to keep the analysis + /// deterministic. + /// + /// Store the dependees on the analysis state for efficiency. + SetVector> dependees; + +#ifndef NDEBUG + /// When compiling with debugging, keep a back reference to the point. + DataFlowSolver::Point point; + /// When compiling with debugging, keep a name for the analysis state. + StringRef debugName; +#endif // NDEBUG + + /// Allow the framework to access the dependees. + friend class DataFlowSolver; +}; + +template +StateT *DataFlowSolver::createState(PointT point) { + stateAllocator.push_back( + std::make_unique(StateT::getForPoint({point}))); + AnalysisState *state = stateAllocator.back().get(); +#ifndef NDEBUG + state->point = Point(point); + state->debugName = llvm::getTypeName(); +#endif // NDEBUG + return static_cast(state); +} + +/// Base class for all child data-flow analyses. A child analysis is expected to +/// build an initial dependency graph (and optionally provide an initial state) +/// when primed and define transfer functions when visiting program points. +/// +/// In classical data-flow analysis, the dependency graph is fixed and analyses +/// define explicit transfer functions between input states and output states. +/// But in this framework, the dependency graph can change during the analysis. +/// And the transfer functions are opaque in that the solver doesn't know what +/// states calling `visit` on an analysis will be updated. This allows multiple +/// analysis to plug in and provide values for the same state. +/// +/// Generally, when an analysis queries an uninitialized state, it is expected +/// to "bail out", i.e., not provide any updates. When the value is initialized, +/// the solver will re-invoke the analysis. If the solver exhausts its worklist, +/// however, and there are still uninitialized states, the solver "nudges" the +/// analysis by default-initializing those states. +/// +/// See `SparseDataFlowAnalysis` and `DenseDataFlowAnalysis` for examples. +class DataFlowAnalysis { +public: + using Point = DataFlowSolver::Point; + + virtual ~DataFlowAnalysis(); + + /// Prime the analysis from the provided top-level operation by building an + /// initial dependency graph between all program points of interest. This can + /// be implemented by calling `visit` on all program points of interest below + /// the top-level operation. + /// + /// An analysis can optionally provide initial values to certain analysis + /// states to influence the evolution of the analysis. + virtual LogicalResult prime(Operation *top) = 0; + + /// Visit the given program point. This function is invoked by the solver on + /// this analysis with a given program point when a dependent analysis state + /// is updated. The function is similar to a transfer function; it queries + /// certain analysis states and sets other states. + /// + /// The function is expected to create dependencies on queried states and + /// propagate updates on updated states. A dependency can be created by + /// calling `drawDependency` between the input state and a program point, + /// indicating that, if the state is updated, the solver should invoke `solve` + /// on the program point. The dependee point does not have to be the same as + /// the provided point. An update to a state is propagated by calling + /// `propagateIfChange` on the state. If the state has changed, then all its + /// dependees are placed on the worklist. + /// + /// The dependency graph does not need to be static. Each invocation of + /// `visit` can add new dependencies, but these dependecies will not be + /// dynamically added to the worklist because the solver doesn't know what + /// will provide a value for then. + virtual LogicalResult visit(Point point) = 0; + +protected: + /// Create an analysis with a reference to the parent solver. + explicit DataFlowAnalysis(DataFlowSolver &solver); + + /// Create a dependency between the given analysis state and program point + /// on this analysis. + void drawDependency(AnalysisState *state, Point point); + + /// Propagate an update to a state if it changed. + void propagateIfChanged(AnalysisState *state, ChangeResult changed); + + /// Get or create a custom program point. + template + PointT *getProgramPoint(Args &&...args) { + return solver.getProgramPoint(std::forward(args)...); + } + + /// Get the analysis state assiocated with the program point. The returned + /// state is expected to be "write-only", and any updates need to be + /// propagated by `propagateIfChanged`. + template + StateT *getOrCreate(PointT point) { + return solver.getOrCreateState(point); + } + + /// Get a read-only analysis state for the given point and create a dependency + /// on `dependee`. If the return state is updated elsewhere, this analysis is + /// re-invoked on the dependee. + template + const StateT *getOrCreateFor(Point dependee, PointT point) { + StateT *state = getOrCreate(point); + drawDependency(state, dependee); + return state; + } + +#ifndef NDEBUG + StringRef debugName; +#endif // NDEBUG + +private: + /// The parent data-flow solver. + DataFlowSolver &solver; + + /// Allow the data-flow solver to access the internals of this class. + friend class DataFlowSolver; +}; + +llvm::raw_ostream &operator<<(llvm::raw_ostream &os, + const mlir::AnalysisState &state); +llvm::raw_ostream &operator<<(llvm::raw_ostream &os, + mlir::DataFlowSolver::Point point); + +} // end namespace mlir + +namespace llvm { +/// Allow hashing of program points. +template <> +struct DenseMapInfo + : public DenseMapInfo {}; +} // end namespace llvm + +#endif // MLIR_ANALYSIS_DATAFLOWFRAMEWORK_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 @@ -15,6 +15,7 @@ BufferViewFlowAnalysis.cpp CallGraph.cpp DataFlowAnalysis.cpp + DataFlowFramework.cpp DataLayoutAnalysis.cpp Liveness.cpp SliceAnalysis.cpp diff --git a/mlir/lib/Analysis/DataFlowFramework.cpp b/mlir/lib/Analysis/DataFlowFramework.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/DataFlowFramework.cpp @@ -0,0 +1,149 @@ +//===- DataFlowFramework.cpp - A generic framework for 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/DataFlowFramework.h" +#include "llvm/Support/Debug.h" + +#define DEBUG_TYPE "dataflow" + +namespace mlir { + +ProgramPoint::~ProgramPoint() = default; + +AnalysisState::~AnalysisState() = default; + +void DataFlowSolver::Point::print(llvm::raw_ostream &os) const { + if (isNull()) { + os << ""; + return; + } + if (auto *programPoint = dyn_cast()) + return programPoint->print(os); + if (auto *op = dyn_cast()) + return op->print(os); + if (auto value = dyn_cast()) + return value.print(os); + if (auto *block = dyn_cast()) + return block->print(os); + auto *region = get(); + os << "{\n"; + for (Block &block : *region) { + block.print(os); + os << "\n"; + } + os << "}"; +} + +Location DataFlowSolver::Point::getLoc() const { + if (auto *programPoint = dyn_cast()) + return programPoint->getLoc(); + if (auto *op = dyn_cast()) + return op->getLoc(); + if (auto value = dyn_cast()) + return value.getLoc(); + if (auto *block = dyn_cast()) + return block->getParent()->getLoc(); + return get()->getLoc(); +} + +LogicalResult DataFlowSolver::primeAndRun(Operation *top) { + // Prime the analysis. + for (DataFlowAnalysis &analysis : + llvm::make_pointee_range(llvm::make_second_range(childAnalyses))) { + LLVM_DEBUG(llvm::dbgs() + << "Priming analysis: " << analysis.debugName << "\n"); + if (failed(analysis.prime(top))) + return failure(); + } + + // Run the analysis until fixpoint. + Point point; + DataFlowAnalysis *analysis; + + do { + // Exhaust the worklist. + while (!worklist.empty()) { + std::tie(point, analysis) = worklist.front(); + worklist.pop(); + + LLVM_DEBUG(llvm::dbgs() << "Invoking '" << analysis->debugName + << "' on: " << point << "\n"); + if (failed(analysis->visit(point))) + return failure(); + } + + // "Nudge" the state of the analysis by forcefully initializing states that + // are still uninitialized. All uninitialized states in the graph can be + // initialized in any order because the analysis reached fixpoint, meaning + // that there are no work items that would have further nudged the analysis. + for (AnalysisState &state : llvm::make_pointee_range(stateAllocator)) { + if (!state.isUninitialized()) + continue; + LLVM_DEBUG(llvm::dbgs() << "Default initializing " << state.debugName + << " of " << state.point << "\n"); + propagateIfChanged(&state, state.defaultInitialize()); + } + + // Iterate until all states are in some initialized state and the worklist + // is exhausted. + } while (!worklist.empty()); + + return success(); +} + +void DataFlowSolver::propagateIfChanged(AnalysisState *state, + ChangeResult changed) { + if (changed == ChangeResult::Change) { + LLVM_DEBUG(llvm::dbgs() << "Propagating update to " << state->debugName + << " of " << state->point << "\n" + << "Value: " << *state << "\n"); + for (const WorkItem &item : state->dependees) + worklist.push(item); + } +} + +void DataFlowSolver::drawDependency(AnalysisState *state, + DataFlowAnalysis *analysis, Point point) { + auto inserted = state->dependees.insert({point, analysis}); + (void)inserted; +#ifndef NDEBUG + if (inserted) { + LLVM_DEBUG(llvm::dbgs() + << "Creating dependency between " << state->debugName << " of " + << state->point << "\nand " << analysis->debugName << " on " + << point << "\n"); + } +#endif // NDEBUG +} + +DataFlowAnalysis::~DataFlowAnalysis() = default; + +DataFlowAnalysis::DataFlowAnalysis(DataFlowSolver &solver) : solver(solver) {} + +void DataFlowAnalysis::drawDependency(AnalysisState *state, Point point) { + solver.drawDependency(state, this, point); +} + +void DataFlowAnalysis::propagateIfChanged(AnalysisState *state, + ChangeResult changed) { + solver.propagateIfChanged(state, changed); +} + +llvm::raw_ostream &operator<<(llvm::raw_ostream &os, + const AnalysisState &state) { + state.print(os); + return os; +} + +llvm::raw_ostream &operator<<(llvm::raw_ostream &os, + DataFlowSolver::Point point) { + point.print(os); + return os; +} + +} // end namespace mlir diff --git a/mlir/test/Analysis/test-foo-analysis.mlir b/mlir/test/Analysis/test-foo-analysis.mlir new file mode 100644 --- /dev/null +++ b/mlir/test/Analysis/test-foo-analysis.mlir @@ -0,0 +1,95 @@ +// RUN: mlir-opt -split-input-file -pass-pipeline='func.func(test-foo-analysis)' %s 2>&1 | FileCheck %s + +// CHECK-LABEL: function: @test_default_init +func.func @test_default_init() -> () { + // CHECK: a -> 0 + "test.foo"() {tag = "a"} : () -> () + return +} + +// ----- + +// CHECK-LABEL: function: @test_one_join +func.func @test_one_join() -> () { + // CHECK: a -> 0 + "test.foo"() {tag = "a"} : () -> () + // CHECK: b -> 1 + "test.foo"() {tag = "b", foo = 1 : ui64} : () -> () + return +} + +// ----- + +// CHECK-LABEL: function: @test_two_join +func.func @test_two_join() -> () { + // CHECK: a -> 0 + "test.foo"() {tag = "a"} : () -> () + // CHECK: b -> 1 + "test.foo"() {tag = "b", foo = 1 : ui64} : () -> () + // CHECK: c -> 0 + "test.foo"() {tag = "c", foo = 1 : ui64} : () -> () + return +} + +// ----- + +// CHECK-LABEL: function: @test_fork +func.func @test_fork() -> () { + // CHECK: init -> 1 + "test.branch"() [^bb0, ^bb1] {tag = "init", foo = 1 : ui64} : () -> () + +^bb0: + // CHECK: a -> 3 + "test.branch"() [^bb2] {tag = "a", foo = 2 : ui64} : () -> () + +^bb1: + // CHECK: b -> 5 + "test.branch"() [^bb2] {tag = "b", foo = 4 : ui64} : () -> () + +^bb2: + // CHECK: end -> 6 + "test.foo"() {tag = "end"} : () -> () + return + +} + +// ----- + +// CHECK-LABEL: function: @test_simple_loop +func.func @test_simple_loop() -> () { + // CHECK: init -> 1 + "test.branch"() [^bb0] {tag = "init", foo = 1 : ui64} : () -> () + +^bb0: + // CHECK: a -> 1 + "test.foo"() {tag = "a", foo = 3 : ui64} : () -> () + "test.branch"() [^bb0, ^bb1] : () -> () + +^bb1: + // CHECK: end -> 3 + "test.foo"() {tag = "end"} : () -> () + return +} + +// ----- + +// CHECK-LABEL: function: @test_double_loop +func.func @test_double_loop() -> () { + // CHECK: init -> 2 + "test.branch"() [^bb0] {tag = "init", foo = 2 : ui64} : () -> () + +^bb0: + // CHECK: a -> 1 + "test.foo"() {tag = "a", foo = 3 : ui64} : () -> () + "test.branch"() [^bb0, ^bb1] : () -> () + +^bb1: + // CHECK: b -> 4 + "test.foo"() {tag = "b", foo = 5 : ui64} : () -> () + "test.branch"() [^bb0, ^bb2] : () -> () + +^bb2: + // CHECK: end -> 4 + "test.foo"() {tag = "end"} : () -> () + return +} 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 @@ -3,6 +3,7 @@ TestAliasAnalysis.cpp TestCallGraph.cpp TestDataFlow.cpp + TestDataFlowFramework.cpp TestLiveness.cpp TestMatchReduction.cpp TestMemRefBoundCheck.cpp diff --git a/mlir/test/lib/Analysis/TestDataFlowFramework.cpp b/mlir/test/lib/Analysis/TestDataFlowFramework.cpp new file mode 100644 --- /dev/null +++ b/mlir/test/lib/Analysis/TestDataFlowFramework.cpp @@ -0,0 +1,186 @@ +//===- TestDataFlowFramework.cpp - Test data-flow analysis framework +//-------===// +// +// 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/DataFlowFramework.h" +#include "mlir/Dialect/Func/IR/FuncOps.h" +#include "mlir/IR/Matchers.h" +#include "mlir/Pass/Pass.h" + +using namespace mlir; + +namespace { +/// This analysis state represents an integer that is XOR'd with other states. +class FooState : public AnalysisState { +public: + MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(FooState) + + explicit FooState(uint64_t value = 0) : state(value) {} + + static FooState getForPoint(Operation *op) { return FooState(); } + static FooState getForPoint(Block *block) { return FooState(); } + + /// Default-initialize the state to zero. + ChangeResult defaultInitialize() override { return join(FooState()); } + + /// Returns true if the state is uninitialized. + bool isUninitialized() const override { return !state; } + + /// Print the integer value or "none" if uninitialized. + void print(llvm::raw_ostream &os) const override { + if (state) + os << *state; + else + os << "none"; + } + + /// Join the state with another. If either is unintialized, take the + /// initialized value. Otherwise, XOR the integer values. + ChangeResult join(const FooState &rhs) { + if (rhs.isUninitialized()) + return ChangeResult::NoChange; + if (isUninitialized()) { + state = rhs.state; + return ChangeResult::Change; + } + uint64_t before = *state; + state = before ^ *rhs.state; + return before == *state ? ChangeResult::NoChange : ChangeResult::Change; + } + + /// Set the value of the state directly. + ChangeResult set(const FooState &rhs) { + ChangeResult result = + state == rhs.state ? ChangeResult::NoChange : ChangeResult::Change; + if (result == ChangeResult::Change) + state = rhs.state; + return result; + } + + /// Returns the integer value of the state. + uint64_t getValue() const { return *state; } + +private: + /// An optional integer value. + Optional state; +}; + +/// This analysis computes `FooState` across operations and control-flow edges. +/// If an op specifies a `foo` integer attribute, the contained value is XOR'd +/// with the value before the operation. +class FooAnalysis : public DataFlowAnalysis { +public: + MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(FooAnalysis) + + using DataFlowAnalysis::DataFlowAnalysis; + + LogicalResult prime(Operation *top) override; + LogicalResult visit(Point point) override; + +private: + void visitBlock(Block *block); + void visitOperation(Operation *op); +}; + +struct TestFooAnalysisPass + : public PassWrapper> { + MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(TestFooAnalysisPass) + + StringRef getArgument() const override { return "test-foo-analysis"; } + + void runOnOperation() override; +}; +} // namespace + +LogicalResult FooAnalysis::prime(Operation *top) { + if (top->getNumRegions() != 1) + return top->emitError("expected a single region top-level op"); + for (Block &block : top->getRegion(0)) { + visitBlock(&block); + for (Operation &op : block) { + if (op.getNumRegions()) + return op.emitError("unexpected op with regions"); + visitOperation(&op); + } + } + return success(); +} + +LogicalResult FooAnalysis::visit(Point point) { + if (auto *op = point.dyn_cast()) { + visitOperation(op); + return success(); + } + if (auto *block = point.dyn_cast()) { + visitBlock(block); + return success(); + } + return emitError(point.getLoc(), "unknown point kind"); +} + +void FooAnalysis::visitBlock(Block *block) { + if (block->isEntryBlock()) { + // This is the initial state. Let the framework default-initialize it. + return; + } + FooState *state = getOrCreate(block); + ChangeResult result = ChangeResult::NoChange; + for (Block *pred : block->getPredecessors()) { + // Join the state at the terminators of all predecessors. + const FooState *predState = + getOrCreateFor(block, pred->getTerminator()); + result |= state->join(*predState); + } + propagateIfChanged(state, result); +} + +void FooAnalysis::visitOperation(Operation *op) { + FooState *state = getOrCreate(op); + ChangeResult result = ChangeResult::NoChange; + + // Copy the state across the operation. + const FooState *prevState; + if (Operation *prev = op->getPrevNode()) + prevState = getOrCreateFor(op, prev); + else + prevState = getOrCreateFor(op, op->getBlock()); + result |= state->set(*prevState); + + // Modify the state with the attribute, if specified. + if (auto attr = op->getAttrOfType("foo")) { + uint64_t value = attr.getUInt(); + result |= state->join(FooState(value)); + } + propagateIfChanged(state, result); +} + +void TestFooAnalysisPass::runOnOperation() { + func::FuncOp func = getOperation(); + DataFlowSolver solver; + solver.load(); + if (failed(solver.primeAndRun(func))) + return signalPassFailure(); + + llvm::raw_ostream &os = llvm::errs(); + os << "function: @" << func.getSymName() << "\n"; + + func.walk([&](Operation *op) { + auto tag = op->getAttrOfType("tag"); + if (!tag) + return; + const FooState *state = solver.lookupState(op); + assert(state && !state->isUninitialized()); + os << tag.getValue() << " -> " << state->getValue() << "\n"; + }); +} + +namespace mlir { +namespace test { +void registerTestFooAnalysisPass() { 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 @@ -77,6 +77,7 @@ void registerTestDominancePass(); void registerTestDynamicPipelinePass(); void registerTestExpandTanhPass(); +void registerTestFooAnalysisPass(); void registerTestComposeSubView(); void registerTestMultiBuffering(); void registerTestIRVisitorsPass(); @@ -173,6 +174,7 @@ mlir::test::registerTestDominancePass(); mlir::test::registerTestDynamicPipelinePass(); mlir::test::registerTestExpandTanhPass(); + mlir::test::registerTestFooAnalysisPass(); mlir::test::registerTestComposeSubView(); mlir::test::registerTestMultiBuffering(); mlir::test::registerTestIRVisitorsPass(); diff --git a/utils/bazel/llvm-project-overlay/mlir/BUILD.bazel b/utils/bazel/llvm-project-overlay/mlir/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/mlir/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/mlir/BUILD.bazel @@ -5809,17 +5809,12 @@ "lib/Analysis/*/*.cpp", "lib/Analysis/*/*.h", ], - exclude = [ - "lib/Analysis/Vector*.cpp", - "lib/Analysis/Vector*.h", - ], ), hdrs = glob( [ "include/mlir/Analysis/*.h", "include/mlir/Analysis/*/*.h", ], - exclude = ["include/mlir/Analysis/Vector*.h"], ), includes = ["include"], deps = [ diff --git a/utils/bazel/llvm-project-overlay/mlir/test/BUILD.bazel b/utils/bazel/llvm-project-overlay/mlir/test/BUILD.bazel --- a/utils/bazel/llvm-project-overlay/mlir/test/BUILD.bazel +++ b/utils/bazel/llvm-project-overlay/mlir/test/BUILD.bazel @@ -26,6 +26,7 @@ "//mlir:Affine", "//mlir:AffineAnalysis", "//mlir:Analysis", + "//mlir:FuncDialect", "//mlir:IR", "//mlir:MemRefDialect", "//mlir:Pass",