diff --git a/mlir/include/mlir/Analysis/BufferAliasAnalysis.h b/mlir/include/mlir/Analysis/BufferAliasAnalysis.h --- a/mlir/include/mlir/Analysis/BufferAliasAnalysis.h +++ b/mlir/include/mlir/Analysis/BufferAliasAnalysis.h @@ -9,6 +9,7 @@ #ifndef MLIR_ANALYSIS_BUFFERALIASANALYSIS_H #define MLIR_ANALYSIS_BUFFERALIASANALYSIS_H +#include "mlir/Analysis/BufferDependencyAnalysis.h" #include "mlir/IR/Operation.h" #include "llvm/ADT/SmallPtrSet.h" @@ -27,20 +28,17 @@ /// 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. + /// have, including preceding values that this value might have aliased (such + /// if `value` is created by a subview, this will return the parent view). + /// 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 {A, B, C} ValueSetT resolve(Value value) const; /// Removes the given values from all alias sets. @@ -51,7 +49,8 @@ void build(Operation *op); /// Maps values to all immediate aliases this value can have. - ValueMapT aliases; + BufferDependencyAnalysis dependentAliases; + ValueMapT reversedDependencies; }; } // namespace mlir diff --git a/mlir/include/mlir/Analysis/BufferDependencyAnalysis.h b/mlir/include/mlir/Analysis/BufferDependencyAnalysis.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/BufferDependencyAnalysis.h @@ -0,0 +1,71 @@ +//===- BufferDependencyAnalysis.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_BUFFERDEPENDENCYANALYSIS_H +#define MLIR_ANALYSIS_BUFFERDEPENDENCYANALYSIS_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 receive all aliases, use +/// BufferAliasAnalysis. +class BufferDependencyAnalysis { +public: + using ValueSetT = SmallPtrSet; + using ValueMapT = llvm::DenseMap; + + /// Constructs a new alias analysis using the op provided. + BufferDependencyAnalysis(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_BUFFERDEPENDENCYANALYSIS_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/BufferDependencyAnalysis.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 = BufferDependencyAnalysis::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; + BufferDependencyAnalysis aliases; /// Stores all internally managed allocations. BufferPlacementAllocs allocs; diff --git a/mlir/lib/Analysis/BufferAliasAnalysis.cpp b/mlir/lib/Analysis/BufferAliasAnalysis.cpp --- a/mlir/lib/Analysis/BufferAliasAnalysis.cpp +++ b/mlir/lib/Analysis/BufferAliasAnalysis.cpp @@ -15,7 +15,9 @@ using namespace mlir; /// Constructs a new alias analysis using the op provided. -BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) { build(op); } +BufferAliasAnalysis::BufferAliasAnalysis(Operation *op) : dependentAliases(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 @@ -28,19 +30,23 @@ 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 = reversedDependencies.find(currentValue); + if (it != reversedDependencies.end()) { for (Value aliasValue : it->second) queue.push_back(aliasValue); } } } + auto resultForward = dependentAliases.resolve(rootValue); + result.insert(resultForward.begin(), resultForward.end()); + return result; } /// Removes the given values from all alias sets. void BufferAliasAnalysis::remove(const SmallPtrSetImpl &aliasValues) { - for (auto &entry : aliases) + dependentAliases.remove(aliasValues); + for (auto &entry : reversedDependencies) llvm::set_subtract(entry.second, aliasValues); } @@ -50,65 +56,8 @@ /// 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)); - }; - - // Add additional aliases created by view changes to the alias list. - op->walk([&](ViewLikeOpInterface viewInterface) { - aliases[viewInterface.getViewSource()].insert(viewInterface->getResult(0)); - }); - - // Query all branch interfaces to link block argument aliases. - op->walk([&](BranchOpInterface branchInterface) { - Block *parentBlock = branchInterface->getBlock(); - for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end(); - it != e; ++it) { - // Query the branch op interface to get the successor operands. - auto successorOperands = - branchInterface.getSuccessorOperands(it.getIndex()); - if (!successorOperands.hasValue()) - continue; - // Build the actual mapping of values to their immediate aliases. - registerAliases(successorOperands.getValue(), (*it)->getArguments()); - } - }); - - // Query the RegionBranchOpInterface to find potential successor regions. - op->walk([&](RegionBranchOpInterface regionInterface) { - // Extract all entry regions and wire all initial entry successor inputs. - SmallVector entrySuccessors; - regionInterface.getSuccessorRegions(/*index=*/llvm::None, entrySuccessors); - for (RegionSuccessor &entrySuccessor : entrySuccessors) { - // Wire the entry region's successor arguments with the initial - // successor inputs. - assert(entrySuccessor.getSuccessor() && - "Invalid entry region without an attached successor region"); - registerAliases(regionInterface.getSuccessorEntryOperands( - entrySuccessor.getSuccessor()->getRegionNumber()), - entrySuccessor.getSuccessorInputs()); - } - - // Wire flow between regions and from region exits. - for (Region ®ion : regionInterface->getRegions()) { - // Iterate over all successor region entries that are reachable from the - // current region. - SmallVector successorRegions; - regionInterface.getSuccessorRegions(region.getRegionNumber(), - successorRegions); - for (RegionSuccessor &successorRegion : successorRegions) { - // Iterate over all immediate terminator operations and wire the - // successor inputs with the operands of each terminator. - for (Block &block : region) { - for (Operation &operation : block) { - if (operation.hasTrait()) - registerAliases(operation.getOperands(), - successorRegion.getSuccessorInputs()); - } - } - } - } - }); + for (auto i : dependentAliases) { + for (auto j : i.getSecond()) + reversedDependencies[j].insert(i.getFirst()); + } } diff --git a/mlir/lib/Analysis/BufferAliasAnalysis.cpp b/mlir/lib/Analysis/BufferDependencyAnalysis.cpp copy from mlir/lib/Analysis/BufferAliasAnalysis.cpp copy to mlir/lib/Analysis/BufferDependencyAnalysis.cpp --- a/mlir/lib/Analysis/BufferAliasAnalysis.cpp +++ b/mlir/lib/Analysis/BufferDependencyAnalysis.cpp @@ -1,4 +1,4 @@ -//===- BufferAliasAnalysis.cpp - Buffer alias analysis for MLIR -*- C++ -*-===// +//======- BufferDependencyAnalysis.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/BufferDependencyAnalysis.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); } +BufferDependencyAnalysis::BufferDependencyAnalysis(Operation *op) { build(op); } -/// Find all immediate and indirect aliases this value could potentially +/// Find all immediate and indirect dependencies 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 { +BufferDependencyAnalysis::ValueSetT +BufferDependencyAnalysis::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,31 @@ } /// Removes the given values from all alias sets. -void BufferAliasAnalysis::remove(const SmallPtrSetImpl &aliasValues) { - for (auto &entry : aliases) +void BufferDependencyAnalysis::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 BufferDependencyAnalysis::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 +73,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 +88,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 +107,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 @@ -3,6 +3,7 @@ AffineAnalysis.cpp AffineStructures.cpp BufferAliasAnalysis.cpp + BufferDependencyAnalysis.cpp CallGraph.cpp LinearTransform.cpp Liveness.cpp @@ -19,6 +20,7 @@ add_mlir_library(MLIRAnalysis AliasAnalysis.cpp BufferAliasAnalysis.cpp + BufferDependencyAnalysis.cpp CallGraph.cpp Liveness.cpp NumberOfExecutions.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 BufferDependencyAnalysis 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 BufferDependencyAnalysis, 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 BufferDependencyAnalysis::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 BufferDependencyAnalysis &aliasAnalysis) { Region *region = alloc.getParentRegion(); do { if (Operation *parentOp = region->getParentOp()) { @@ -301,6 +301,7 @@ /// Promote buffers to stack-based allocations. void promote(function_ref isSmallAlloc) { + llvm::SmallVector toErase; for (BufferPlacementAllocs::AllocEntry &entry : allocs) { Value alloc = std::get<0>(entry); Operation *dealloc = std::get<1>(entry); @@ -324,8 +325,10 @@ // Replace the original alloc by a newly created alloca. allocOp->replaceAllUsesWith(alloca); - allocOp->erase(); + toErase.push_back(allocOp); } + for (auto *allocOp : toErase) + allocOp->erase(); } };