diff --git a/mlir/include/mlir/Analysis/BufferAliasAnalysis.h b/mlir/include/mlir/Analysis/BufferAliasAnalysis.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/BufferAliasAnalysis.h @@ -0,0 +1,59 @@ +//===- 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/Interfaces/ControlFlowInterfaces.td b/mlir/include/mlir/Interfaces/ControlFlowInterfaces.td --- a/mlir/include/mlir/Interfaces/ControlFlowInterfaces.td +++ b/mlir/include/mlir/Interfaces/ControlFlowInterfaces.td @@ -140,6 +140,13 @@ }]; let extraClassDeclaration = [{ + /// Convenience helper in case none of the operands is known. + void getSuccessorRegions(Optional index, + SmallVectorImpl ®ions) { + SmallVector nullAttrs(getOperation()->getNumOperands()); + getSuccessorRegions(index, nullAttrs, regions); + } + /// Verify types along control flow edges described by this interface. static LogicalResult verifyTypes(Operation *op) { return detail::verifyTypesAlongControlFlowEdges(op); 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 @@ -28,6 +28,7 @@ #ifndef MLIR_TRANSFORMS_BUFFERIZE_H #define MLIR_TRANSFORMS_BUFFERIZE_H +#include "mlir/Analysis/BufferAliasAnalysis.h" #include "mlir/Analysis/Liveness.h" #include "mlir/Dialect/StandardOps/IR/Ops.h" #include "mlir/IR/Builders.h" @@ -279,46 +280,6 @@ // clang-format on } -/// 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 BufferPlacementAliasAnalysis { -public: - using ValueSetT = SmallPtrSet; - using ValueMapT = llvm::DenseMap; - -public: - /// Constructs a new alias analysis using the op provided. - BufferPlacementAliasAnalysis(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; -}; - /// A simple analysis that detects allocation operations. class BufferPlacementAllocs { public: @@ -369,7 +330,7 @@ /// The base class for all BufferPlacement transformations. class BufferPlacementTransformationBase { public: - using ValueSetT = BufferPlacementAliasAnalysis::ValueSetT; + using ValueSetT = BufferAliasAnalysis::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 @@ -404,7 +365,7 @@ protected: /// Alias information that can be updated during the insertion of copies. - BufferPlacementAliasAnalysis aliases; + BufferAliasAnalysis aliases; /// Stores all internally managed allocations. BufferPlacementAllocs allocs; diff --git a/mlir/lib/Analysis/BufferAliasAnalysis.cpp b/mlir/lib/Analysis/BufferAliasAnalysis.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/BufferAliasAnalysis.cpp @@ -0,0 +1,115 @@ +//===- BufferAliasAnalysis.cpp - 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 +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/BufferAliasAnalysis.h" + +#include "mlir/Interfaces/ControlFlowInterfaces.h" +#include "mlir/Interfaces/ViewLikeInterface.h" +#include "llvm/ADT/SetOperations.h" + +using namespace mlir; + +/// Constructs a new alias analysis using the op provided. +BufferAliasAnalysis::BufferAliasAnalysis(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 { + 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()) { + for (Value aliasValue : it->second) + queue.push_back(aliasValue); + } + } + } + return result; +} + +/// Removes the given values from all alias sets. +void BufferAliasAnalysis::remove(const SmallPtrSetImpl &aliasValues) { + for (auto &entry : aliases) + 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)); + }; + + // Add additional aliases created by view changes to the alias list. + op->walk([&](ViewLikeOpInterface viewInterface) { + aliases[viewInterface.getViewSource()].insert( + viewInterface.getOperation()->getResult(0)); + }); + + // Query all branch interfaces to link block argument aliases. + op->walk([&](BranchOpInterface branchInterface) { + Block *parentBlock = branchInterface.getOperation()->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.getOperation()->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()); + } + } + } + } + }); +} 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 @@ -1,6 +1,7 @@ set(LLVM_OPTIONAL_SOURCES AffineAnalysis.cpp AffineStructures.cpp + BufferAliasAnalysis.cpp CallGraph.cpp Liveness.cpp LoopAnalysis.cpp @@ -11,6 +12,7 @@ ) add_mlir_library(MLIRAnalysis + BufferAliasAnalysis.cpp CallGraph.cpp Liveness.cpp SliceAnalysis.cpp @@ -52,4 +54,4 @@ MLIRSCF ) -add_subdirectory(Presburger) \ No newline at end of file +add_subdirectory(Presburger) 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 BufferPlacementAliasAnalysis class). Consider the following +// (using the BufferAliasAnalysis class). Consider the following // example: // // ^bb0(%arg0): @@ -31,7 +31,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 copy buffer for %arg1 that will -// contain the actual contents. Using the class BufferPlacementAliasAnalysis, we +// contain the actual contents. Using the class BufferAliasAnalysis, 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 @@ -91,112 +91,6 @@ regionInterface.getSuccessorRegions(index, operandAttributes, successors); } -//===----------------------------------------------------------------------===// -// BufferPlacementAliasAnalysis -//===----------------------------------------------------------------------===// - -/// Constructs a new alias analysis using the op provided. -BufferPlacementAliasAnalysis::BufferPlacementAliasAnalysis(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. -BufferPlacementAliasAnalysis::ValueSetT -BufferPlacementAliasAnalysis::resolve(Value value) const { - ValueSetT result; - - /// Recursively determines alias information for the given value. It stores - /// all newly found potential aliases in the given result set. - std::function resolveRecursive = [&](Value current) { - if (!result.insert(current).second) - return; - auto it = aliases.find(current); - if (it == aliases.end()) - return; - for (Value alias : it->second) - resolveRecursive(alias); - }; - - resolveRecursive(value); - return result; -} - -/// Removes the given values from all alias sets. -void BufferPlacementAliasAnalysis::remove( - const SmallPtrSetImpl &aliasValues) { - for (auto &entry : aliases) - 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 BufferPlacementAliasAnalysis::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.getOperation()->getResult(0)); - }); - - // Query all branch interfaces to link block argument aliases. - op->walk([&](BranchOpInterface branchInterface) { - Block *parentBlock = branchInterface.getOperation()->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; - getSuccessorRegions(regionInterface, /*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.getOperation()->getRegions()) { - // Iterate over all successor region entries that are reachable from the - // current region. - SmallVector successorRegions; - getSuccessorRegions(regionInterface, region.getRegionNumber(), - successorRegions); - for (RegionSuccessor &successorRegion : successorRegions) { - // Iterate over all immediate terminator operations and wire the - // successor inputs with the operands of each terminator. - walkReturnOperations(®ion, [&](Operation *terminator) { - registerAliases(terminator->getOperands(), - successorRegion.getSuccessorInputs()); - }); - } - } - }); -} - //===----------------------------------------------------------------------===// // BufferPlacementAllocs //===----------------------------------------------------------------------===//