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_BUFFER_ALIAS_ANALYSIS_H +#define MLIR_ANALYSIS_BUFFER_ALIAS_ANALYSIS_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, e.g., for buffer placement +/// where safe positions allocs and deallocs must be determined. +class BufferAliasAnalysis { +public: + using ValueSetT = SmallPtrSet; + using ValueMapT = llvm::DenseMap; + +public: + /// Constructs a new alias analysis using the op provided. + BufferAliasAnalysis(Operation *op) { build(op); } + + /// Find all immediate aliases this value could potentially have. + ValueMapT::const_iterator find(Value value) const { + return aliases.find(value); + } + + /// 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. + /// 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 build(Operation *op); + + /// Maps values to all immediate aliases this value can have. + ValueMapT aliases; +}; + +} // namespace mlir + +#endif // MLIR_ANALYSIS_BUFFER_ALIAS_ANALYSIS_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/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,104 @@ +//===- 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; + +BufferAliasAnalysis::ValueSetT +BufferAliasAnalysis::resolve(Value rootValue) const { + ValueSetT result; + SmallVector queue; + queue.push_back(rootValue); + while (!queue.empty()) { + Value currentValue = queue.back(); + queue.pop_back(); + 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; +} + +void BufferAliasAnalysis::remove(const SmallPtrSetImpl &aliasValues) { + for (auto &entry : aliases) + llvm::set_subtract(entry.second, aliasValues); +} + +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 return-like 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/BufferPlacement.cpp b/mlir/lib/Transforms/BufferPlacement.cpp --- a/mlir/lib/Transforms/BufferPlacement.cpp +++ b/mlir/lib/Transforms/BufferPlacement.cpp @@ -15,7 +15,7 @@ // does not pay attention to aliases, which can occur due to branches (and their // associated block arguments) in general. For this purpose, BufferPlacement // firstly finds all possible aliases for a single value (using the -// BufferPlacementAliasAnalysis class). Consider the following example: +// BufferAliasAnalysis class). Consider the following example: // // ^bb0(%arg0): // cond_br %cond, ^bb1, ^bb2 @@ -34,7 +34,7 @@ // (or even has to stay due to additional dependencies) at this location and 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 @@ -56,6 +56,7 @@ //===----------------------------------------------------------------------===// #include "PassDetail.h" +#include "mlir/Analysis/BufferAliasAnalysis.h" #include "mlir/Analysis/Liveness.h" #include "mlir/Dialect/Linalg/IR/LinalgOps.h" #include "mlir/Dialect/StandardOps/IR/Ops.h" @@ -79,148 +80,7 @@ } } -/// Wrapper for the actual `RegionBranchOpInterface.getSuccessorRegions` -/// function that initializes the required `operandAttributes` array. -static void getSuccessorRegions(RegionBranchOpInterface regionInterface, - llvm::Optional index, - SmallVectorImpl &successors) { - // Create a list of null attributes for each operand to comply with the - // `getSuccessorRegions` interface definition that requires a single - // attribute per operand. - SmallVector operandAttributes( - regionInterface.getOperation()->getNumOperands()); - - // Get all successor regions using the temporarily allocated - // `operandAttributes`. - regionInterface.getSuccessorRegions(index, operandAttributes, successors); -} - namespace { -//===----------------------------------------------------------------------===// -// BufferPlacementAliasAnalysis -//===----------------------------------------------------------------------===// - -/// 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) { build(op); } - - /// Find all immediate aliases this value could potentially have. - ValueMapT::const_iterator find(Value value) const { - return aliases.find(value); - } - - /// 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 { - ValueSetT result; - resolveRecursive(value, result); - return result; - } - - /// Removes the given values from all alias sets. - void remove(const SmallPtrSetImpl &aliasValues) { - for (auto &entry : aliases) - llvm::set_subtract(entry.second, aliasValues); - } - -private: - /// Recursively determines alias information for the given value. It stores - /// all newly found potential aliases in the given result set. - void resolveRecursive(Value value, ValueSetT &result) const { - if (!result.insert(value).second) - return; - auto it = aliases.find(value); - if (it == aliases.end()) - return; - for (Value alias : it->second) - resolveRecursive(alias, result); - } - - /// 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 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()); - }); - } - } - }); - } - - /// Maps values to all immediate aliases this value can have. - ValueMapT aliases; -}; - //===----------------------------------------------------------------------===// // Backedges //===----------------------------------------------------------------------===// @@ -305,7 +165,7 @@ // The main buffer placement analysis used to place allocs, copies and deallocs. class BufferPlacement { public: - using ValueSetT = BufferPlacementAliasAnalysis::ValueSetT; + using ValueSetT = BufferAliasAnalysis::ValueSetT; /// An intermediate representation of a single allocation node. struct AllocEntry { @@ -542,7 +402,7 @@ // parent operation. In this case, we have to introduce an additional copy // for buffer that is passed to the argument. SmallVector successorRegions; - getSuccessorRegions(regionInterface, llvm::None, successorRegions); + regionInterface.getSuccessorRegions(llvm::None, successorRegions); auto *it = llvm::find_if(successorRegions, [&](RegionSuccessor &successorRegion) { return successorRegion.getSuccessor() == argRegion; @@ -595,8 +455,8 @@ // Query the regionInterface to get all successor regions of the current // one. SmallVector successorRegions; - getSuccessorRegions(regionInterface, region.getRegionNumber(), - successorRegions); + regionInterface.getSuccessorRegions(region.getRegionNumber(), + successorRegions); // Try to find a matching region successor. RegionSuccessor *regionSuccessor = llvm::find_if(successorRegions, regionPredicate); @@ -767,7 +627,7 @@ Operation *operation; /// Alias information that can be updated during the insertion of copies. - BufferPlacementAliasAnalysis aliases; + BufferAliasAnalysis aliases; /// Maps allocation nodes to their associated blocks. AllocEntryList allocs;