blob: 45766a25f791b12f31dd047a5bbc916273207d69 [file] [log] [blame]
//======- BufferViewFlowAnalysis.cpp - Buffer alias analysis -*- C++ -*-======//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#include "mlir/Analysis/BufferViewFlowAnalysis.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.
BufferViewFlowAnalysis::BufferViewFlowAnalysis(Operation *op) { build(op); }
/// 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::resolve(Value rootValue) const {
ValueSetT result;
SmallVector<Value, 8> queue;
while (!queue.empty()) {
Value currentValue = queue.pop_back_val();
if (result.insert(currentValue).second) {
auto it = dependencies.find(currentValue);
if (it != dependencies.end()) {
for (Value aliasValue : it->second)
return result;
/// Removes the given values from all alias sets.
void BufferViewFlowAnalysis::remove(const SmallPtrSetImpl<Value> &aliasValues) {
for (auto &entry : dependencies)
llvm::set_subtract(entry.second, aliasValues);
/// 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))
// Add additional dependencies created by view changes to the alias list.
op->walk([&](ViewLikeOpInterface viewInterface) {
// 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();
it != e; ++it) {
// Query the branch op interface to get the successor operands.
auto successorOperands =
if (!successorOperands.hasValue())
// Build the actual mapping of values to their immediate dependencies.
registerDependencies(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<RegionSuccessor, 2> 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");
// Wire flow between regions and from region exits.
for (Region &region : regionInterface->getRegions()) {
// Iterate over all successor region entries that are reachable from the
// current region.
SmallVector<RegionSuccessor, 2> successorRegions;
for (RegionSuccessor &successorRegion : successorRegions) {
// Determine the current region index (if any).
Optional<unsigned> regionIndex;
Region *regionSuccessor = successorRegion.getSuccessor();
if (regionSuccessor)
regionIndex = regionSuccessor->getRegionNumber();
// Iterate over all immediate terminator operations and wire the
// successor inputs with the successor operands of each terminator.
for (Block &block : region) {
auto successorOperands = getRegionBranchSuccessorOperands(
block.getTerminator(), regionIndex);
if (successorOperands) {