diff --git a/mlir/include/mlir/Analysis/BufferAliasAnalysis.h b/mlir/include/mlir/Analysis/BufferAliasAnalysis.h deleted file mode 100644 --- a/mlir/include/mlir/Analysis/BufferAliasAnalysis.h +++ /dev/null @@ -1,59 +0,0 @@ -//===- BufferAliasAnalysis.h - Buffer alias analysis for MLIR ---*- 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 -// -//===----------------------------------------------------------------------===// - -#ifndef MLIR_ANALYSIS_BUFFERALIASANALYSIS_H -#define MLIR_ANALYSIS_BUFFERALIASANALYSIS_H - -#include "mlir/IR/Operation.h" -#include "llvm/ADT/SmallPtrSet.h" - -namespace mlir { - -/// A straight-forward alias analysis which ensures that all aliases of all -/// values will be determined. This is a requirement for the BufferPlacement -/// class since you need to determine safe positions to place alloc and -/// deallocs. -class BufferAliasAnalysis { -public: - using ValueSetT = SmallPtrSet; - using ValueMapT = llvm::DenseMap; - -public: - /// Constructs a new alias analysis using the op provided. - BufferAliasAnalysis(Operation *op); - - /// Find all immediate aliases this value could potentially have. - ValueMapT::const_iterator find(Value value) const { - return aliases.find(value); - } - - /// Returns the begin iterator to iterate over all aliases. - ValueMapT::const_iterator begin() const { return aliases.begin(); } - - /// Returns the end iterator that can be used in combination with find. - ValueMapT::const_iterator end() const { return aliases.end(); } - - /// Find all immediate and indirect aliases this value could potentially - /// have. Note that the resulting set will also contain the value provided as - /// it is an alias of itself. - ValueSetT resolve(Value value) const; - - /// Removes the given values from all alias sets. - void remove(const SmallPtrSetImpl &aliasValues); - -private: - /// This function constructs a mapping from values to its immediate aliases. - void build(Operation *op); - - /// Maps values to all immediate aliases this value can have. - ValueMapT aliases; -}; - -} // namespace mlir - -#endif // MLIR_ANALYSIS_BUFFERALIASANALYSIS_H diff --git a/mlir/include/mlir/Analysis/BufferViewFlowAnalysis.h b/mlir/include/mlir/Analysis/BufferViewFlowAnalysis.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/BufferViewFlowAnalysis.h @@ -0,0 +1,71 @@ +//===- BufferViewFlowAnalysis.h - Buffer dependency analysis ---*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_BUFFERVIEWFLOWANALYSIS_H +#define MLIR_ANALYSIS_BUFFERVIEWFLOWANALYSIS_H + +#include "mlir/IR/Operation.h" +#include "llvm/ADT/SmallPtrSet.h" + +namespace mlir { + +/// A straight-forward alias analysis which ensures that all dependencies of all +/// values will be determined. This is a requirement for the BufferPlacement +/// class since you need to determine safe positions to place alloc and +/// deallocs. This alias analysis only finds aliases that might have been +/// created on top of the specified view. To find all aliases, resolve the +/// intial alloc/argument value. +class BufferViewFlowAnalysis { +public: + using ValueSetT = SmallPtrSet; + using ValueMapT = llvm::DenseMap; + + /// Constructs a new alias analysis using the op provided. + BufferViewFlowAnalysis(Operation *op); + + /// Find all immediate dependencies this value could potentially have. + ValueMapT::const_iterator find(Value value) const { + return dependencies.find(value); + } + + /// Returns the begin iterator to iterate over all dependencies. + ValueMapT::const_iterator begin() const { return dependencies.begin(); } + + /// Returns the end iterator that can be used in combination with find. + ValueMapT::const_iterator end() const { return dependencies.end(); } + + /// Find all immediate and indirect views upong this value. This will find all + /// dependencies on this value that can potentially be later in the execution + /// of the program, but will not return values that this alias might have been + /// created from (such as if `value is created by a subview, this will not + /// return the parent view if there is no cyclic behavior). Note that the + /// resulting set will also contain the value provided as it is an alias of + /// itself. + /// + /// A = * + /// B = subview(A) + /// C = B + /// + /// Results in resolve(B) returning {B, C} + ValueSetT resolve(Value value) const; + + /// Removes the given values from all alias sets. + void remove(const SmallPtrSetImpl &aliasValues); + +private: + /// This function constructs a mapping from values to its immediate + /// dependencies. + void build(Operation *op); + + /// Maps values to all immediate dependencies this value can have. + ValueMapT dependencies; +}; + +} // namespace mlir + +#endif // MLIR_ANALYSIS_BUFFERVIEWFLOWANALYSIS_H diff --git a/mlir/include/mlir/Transforms/BufferUtils.h b/mlir/include/mlir/Transforms/BufferUtils.h --- a/mlir/include/mlir/Transforms/BufferUtils.h +++ b/mlir/include/mlir/Transforms/BufferUtils.h @@ -14,7 +14,7 @@ #ifndef MLIR_TRANSFORMS_BUFFERUTILS_H #define MLIR_TRANSFORMS_BUFFERUTILS_H -#include "mlir/Analysis/BufferAliasAnalysis.h" +#include "mlir/Analysis/BufferViewFlowAnalysis.h" #include "mlir/Analysis/Liveness.h" #include "mlir/Dialect/StandardOps/IR/Ops.h" #include "mlir/IR/Builders.h" @@ -71,7 +71,7 @@ /// The base class for all BufferPlacement transformations. class BufferPlacementTransformationBase { public: - using ValueSetT = BufferAliasAnalysis::ValueSetT; + using ValueSetT = BufferViewFlowAnalysis::ValueSetT; /// Finds a common dominator for the given value while taking the positions /// of the values in the value set into account. It supports dominator and @@ -106,7 +106,7 @@ protected: /// Alias information that can be updated during the insertion of copies. - BufferAliasAnalysis aliases; + BufferViewFlowAnalysis aliases; /// Stores all internally managed allocations. BufferPlacementAllocs allocs; diff --git a/mlir/include/mlir/Transforms/Bufferize.h b/mlir/include/mlir/Transforms/Bufferize.h --- a/mlir/include/mlir/Transforms/Bufferize.h +++ b/mlir/include/mlir/Transforms/Bufferize.h @@ -23,7 +23,7 @@ #ifndef MLIR_TRANSFORMS_BUFFERIZE_H #define MLIR_TRANSFORMS_BUFFERIZE_H -#include "mlir/Analysis/BufferAliasAnalysis.h" +#include "mlir/Analysis/BufferViewFlowAnalysis.h" #include "mlir/Analysis/Liveness.h" #include "mlir/Dialect/StandardOps/IR/Ops.h" #include "mlir/IR/Builders.h" diff --git a/mlir/lib/Analysis/BufferAliasAnalysis.cpp b/mlir/lib/Analysis/BufferViewFlowAnalysis.cpp rename from mlir/lib/Analysis/BufferAliasAnalysis.cpp rename to mlir/lib/Analysis/BufferViewFlowAnalysis.cpp --- a/mlir/lib/Analysis/BufferAliasAnalysis.cpp +++ b/mlir/lib/Analysis/BufferViewFlowAnalysis.cpp @@ -1,4 +1,4 @@ -//===- BufferAliasAnalysis.cpp - Buffer alias analysis for MLIR -*- C++ -*-===// +//======- BufferViewFlowAnalysis.cpp - Buffer alias analysis -*- C++ -*-======// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,7 +6,7 @@ // //===----------------------------------------------------------------------===// -#include "mlir/Analysis/BufferAliasAnalysis.h" +#include "mlir/Analysis/BufferViewFlowAnalysis.h" #include "mlir/Interfaces/ControlFlowInterfaces.h" #include "mlir/Interfaces/ViewLikeInterface.h" @@ -15,21 +15,21 @@ using namespace mlir; /// Constructs a new alias analysis using the op provided. -BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) { build(op); } +BufferViewFlowAnalysis::BufferViewFlowAnalysis(Operation *op) { build(op); } -/// Find all immediate and indirect aliases this value could potentially -/// have. Note that the resulting set will also contain the value provided as -/// it is an alias of itself. -BufferAliasAnalysis::ValueSetT -BufferAliasAnalysis::resolve(Value rootValue) const { +/// Find all immediate and indirect dependent buffers this value could +/// potentially have. Note that the resulting set will also contain the value +/// provided as it is a dependent alias of itself. +BufferViewFlowAnalysis::ValueSetT +BufferViewFlowAnalysis::resolve(Value rootValue) const { ValueSetT result; SmallVector queue; queue.push_back(rootValue); while (!queue.empty()) { Value currentValue = queue.pop_back_val(); if (result.insert(currentValue).second) { - auto it = aliases.find(currentValue); - if (it != aliases.end()) { + auto it = dependencies.find(currentValue); + if (it != dependencies.end()) { for (Value aliasValue : it->second) queue.push_back(aliasValue); } @@ -39,29 +39,30 @@ } /// Removes the given values from all alias sets. -void BufferAliasAnalysis::remove(const SmallPtrSetImpl &aliasValues) { - for (auto &entry : aliases) +void BufferViewFlowAnalysis::remove(const SmallPtrSetImpl &aliasValues) { + for (auto &entry : dependencies) llvm::set_subtract(entry.second, aliasValues); } -/// This function constructs a mapping from values to its immediate aliases. -/// It iterates over all blocks, gets their predecessors, determines the -/// values that will be passed to the corresponding block arguments and -/// inserts them into the underlying map. Furthermore, it wires successor -/// regions and branch-like return operations from nested regions. -void BufferAliasAnalysis::build(Operation *op) { - // Registers all aliases of the given values. - auto registerAliases = [&](auto values, auto aliases) { - for (auto entry : llvm::zip(values, aliases)) - this->aliases[std::get<0>(entry)].insert(std::get<1>(entry)); +/// This function constructs a mapping from values to its immediate +/// dependencies. It iterates over all blocks, gets their predecessors, +/// determines the values that will be passed to the corresponding block +/// arguments and inserts them into the underlying map. Furthermore, it wires +/// successor regions and branch-like return operations from nested regions. +void BufferViewFlowAnalysis::build(Operation *op) { + // Registers all dependencies of the given values. + auto registerDependencies = [&](auto values, auto dependencies) { + for (auto entry : llvm::zip(values, dependencies)) + this->dependencies[std::get<0>(entry)].insert(std::get<1>(entry)); }; - // Add additional aliases created by view changes to the alias list. + // Add additional dependencies created by view changes to the alias list. op->walk([&](ViewLikeOpInterface viewInterface) { - aliases[viewInterface.getViewSource()].insert(viewInterface->getResult(0)); + dependencies[viewInterface.getViewSource()].insert( + viewInterface->getResult(0)); }); - // Query all branch interfaces to link block argument aliases. + // Query all branch interfaces to link block argument dependencies. op->walk([&](BranchOpInterface branchInterface) { Block *parentBlock = branchInterface->getBlock(); for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end(); @@ -71,8 +72,8 @@ branchInterface.getSuccessorOperands(it.getIndex()); if (!successorOperands.hasValue()) continue; - // Build the actual mapping of values to their immediate aliases. - registerAliases(successorOperands.getValue(), (*it)->getArguments()); + // Build the actual mapping of values to their immediate dependencies. + registerDependencies(successorOperands.getValue(), (*it)->getArguments()); } }); @@ -86,9 +87,10 @@ // successor inputs. assert(entrySuccessor.getSuccessor() && "Invalid entry region without an attached successor region"); - registerAliases(regionInterface.getSuccessorEntryOperands( - entrySuccessor.getSuccessor()->getRegionNumber()), - entrySuccessor.getSuccessorInputs()); + registerDependencies( + regionInterface.getSuccessorEntryOperands( + entrySuccessor.getSuccessor()->getRegionNumber()), + entrySuccessor.getSuccessorInputs()); } // Wire flow between regions and from region exits. @@ -104,8 +106,8 @@ for (Block &block : region) { for (Operation &operation : block) { if (operation.hasTrait()) - registerAliases(operation.getOperands(), - successorRegion.getSuccessorInputs()); + registerDependencies(operation.getOperands(), + successorRegion.getSuccessorInputs()); } } } 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,7 @@ AliasAnalysis.cpp AffineAnalysis.cpp AffineStructures.cpp - BufferAliasAnalysis.cpp + BufferViewFlowAnalysis.cpp CallGraph.cpp DataFlowAnalysis.cpp LinearTransform.cpp @@ -19,7 +19,7 @@ add_mlir_library(MLIRAnalysis AliasAnalysis.cpp - BufferAliasAnalysis.cpp + BufferViewFlowAnalysis.cpp CallGraph.cpp DataFlowAnalysis.cpp Liveness.cpp diff --git a/mlir/lib/Transforms/BufferDeallocation.cpp b/mlir/lib/Transforms/BufferDeallocation.cpp --- a/mlir/lib/Transforms/BufferDeallocation.cpp +++ b/mlir/lib/Transforms/BufferDeallocation.cpp @@ -15,7 +15,7 @@ // liveness analysis does not pay attention to aliases, which can occur due to // branches (and their associated block arguments) in general. For this purpose, // BufferDeallocation firstly finds all possible aliases for a single value -// (using the BufferAliasAnalysis class). Consider the following example: +// (using the BufferViewFlowAnalysis class). Consider the following example: // // ^bb0(%arg0): // cond_br %cond, ^bb1, ^bb2 @@ -30,7 +30,7 @@ // We should place the dealloc for %new_value in exit. However, we have to free // the buffer in the same block, because it cannot be freed in the post // dominator. However, this requires a new clone buffer for %arg1 that will -// contain the actual contents. Using the class BufferAliasAnalysis, we +// contain the actual contents. Using the class BufferViewFlowAnalysis, we // will find out that %new_value has a potential alias %arg1. In order to find // the dealloc position we have to find all potential aliases, iterate over // their uses and find the common post-dominator block (note that additional diff --git a/mlir/lib/Transforms/BufferOptimizations.cpp b/mlir/lib/Transforms/BufferOptimizations.cpp --- a/mlir/lib/Transforms/BufferOptimizations.cpp +++ b/mlir/lib/Transforms/BufferOptimizations.cpp @@ -58,7 +58,7 @@ /// Checks whether the given aliases leave the allocation scope. static bool leavesAllocationScope(Region *parentRegion, - const BufferAliasAnalysis::ValueSetT &aliases) { + const BufferViewFlowAnalysis::ValueSetT &aliases) { for (Value alias : aliases) { for (auto *use : alias.getUsers()) { // If there is at least one alias that leaves the parent region, we know @@ -74,7 +74,7 @@ /// Checks, if an automated allocation scope for a given alloc value exists. static bool hasAllocationScope(Value alloc, - const BufferAliasAnalysis &aliasAnalysis) { + const BufferViewFlowAnalysis &aliasAnalysis) { Region *region = alloc.getParentRegion(); do { if (Operation *parentOp = region->getParentOp()) {