diff --git a/mlir/include/mlir/Analysis/AliasAnalysis.h b/mlir/include/mlir/Analysis/AliasAnalysis.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/AliasAnalysis.h @@ -0,0 +1,171 @@ +//===- AliasAnalysis.h - Alias Analysis in 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 +// +//===----------------------------------------------------------------------===// +// +// This header file defines utilities and analyses for performing alias queries +// and related memory queries in MLIR. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_ALIASANALYSIS_H_ +#define MLIR_ANALYSIS_ALIASANALYSIS_H_ + +#include "mlir/IR/Operation.h" + +namespace mlir { + +//===----------------------------------------------------------------------===// +// AliasResult +//===----------------------------------------------------------------------===// + +/// The possible results of an alias query. +class AliasResult { +public: + enum Kind { + /// The two locations do not alias at all. + /// + /// This value is arranged to convert to false, while all other values + /// convert to true. This allows a boolean context to convert the result to + /// a binary flag indicating whether there is the possibility of aliasing. + NoAlias = 0, + /// The two locations may or may not alias. This is the least precise + /// result. + MayAlias, + /// The two locations alias, but only due to a partial overlap. + PartialAlias, + /// The two locations precisely alias each other. + MustAlias, + }; + + AliasResult(Kind kind) : kind(kind) {} + bool operator==(const AliasResult &other) const { return kind == other.kind; } + bool operator!=(const AliasResult &other) const { return !(*this == other); } + + /// Allow conversion to bool to signal if there is an aliasing or not. + explicit operator bool() const { return kind != NoAlias; } + + /// Merge this alias result with `other` and return a new result that + /// represents the conservative merge of both results. If the results + /// represent a known alias, the stronger alias is chosen (i.e. + /// Partial+Must=Must). If the two results are conflicting, MayAlias is + /// returned. + AliasResult merge(AliasResult other) const; + + /// Returns if this result is a partial alias. + bool isNo() const { return kind == NoAlias; } + + /// Returns if this result is a may alias. + bool isMay() const { return kind == MayAlias; } + + /// Returns if this result is a must alias. + bool isMust() const { return kind == MustAlias; } + + /// Returns if this result is a partial alias. + bool isPartial() const { return kind == PartialAlias; } + + /// Return the internal kind of this alias result. + Kind getKind() const { return kind; } + +private: + /// The internal kind of the result. + Kind kind; +}; + +//===----------------------------------------------------------------------===// +// AliasAnalysisTraits +//===----------------------------------------------------------------------===// + +namespace detail { +/// This class contains various internal trait classes used by the main +/// AliasAnalysis class below. +struct AliasAnalysisTraits { + /// This class represents the `Concept` of an alias analysis implementation. + /// It is the abstract base class used by the AliasAnalysis class for + /// querying into derived analysis implementations. + class Concept { + public: + virtual ~Concept() {} + + /// Given two values, return their aliasing behavior. + virtual AliasResult alias(Value lhs, Value rhs) = 0; + }; + + /// This class represents the `Model` of an alias analysis implementation + /// `ImplT`. A model is instantiated for each alias analysis implementation + /// to implement the `Concept` without the need for the derived + /// implementation to inherit from the `Concept` class. + template class Model final : public Concept { + public: + explicit Model(ImplT &&impl) : impl(std::forward(impl)) {} + ~Model() override = default; + + /// Given two values, return their aliasing behavior. + AliasResult alias(Value lhs, Value rhs) final { + return impl.alias(lhs, rhs); + } + + private: + ImplT impl; + }; +}; +} // end namespace detail + +//===----------------------------------------------------------------------===// +// AliasAnalysis +//===----------------------------------------------------------------------===// + +/// This class represents the main alias analysis interface in MLIR. It +/// functions as an aggregate of various different alias analysis +/// implementations. This aggregation allows for utilizing the strengths of +/// different alias analysis implementations that either target or have access +/// to different aliasing information. This is especially important for MLIR +/// given the scope of different types of memory models and aliasing behaviors. +/// For users of this analysis that want to perform aliasing queries, see the +/// `Alias Queries` section below for the available methods. For users of this +/// analysis that want to add a new alias analysis implementation to the +/// aggregate, see the `Alias Implementations` section below. +class AliasAnalysis { + using Concept = detail::AliasAnalysisTraits::Concept; + template + using Model = detail::AliasAnalysisTraits::Model; + +public: + AliasAnalysis(Operation *op); + + //===--------------------------------------------------------------------===// + // Alias Implementations + //===--------------------------------------------------------------------===// + + /// Add a new alias analysis implementation `AnalysisT` to this analysis + /// aggregate. This allows for users to access this implementation when + /// performing alias queries. Implementations added here must provide the + /// following: + /// * AnalysisT(AnalysisT &&) + /// * AliasResult alias(Value lhs, Value rhs) + /// - This method returns an `AliasResult` that corresponds to the + /// aliasing behavior between `lhs` and `rhs`. + template + void addAnalysisImplementation(AnalysisT &&analysis) { + aliasImpls.push_back( + std::make_unique>(std::forward(analysis))); + } + + //===--------------------------------------------------------------------===// + // Alias Queries + //===--------------------------------------------------------------------===// + + /// Given two values, return their aliasing behavior. + AliasResult alias(Value lhs, Value rhs); + +private: + /// A set of internal alias analysis implementations. + SmallVector, 4> aliasImpls; +}; + +} // end namespace mlir + +#endif // MLIR_ANALYSIS_ALIASANALYSIS_H_ diff --git a/mlir/include/mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h b/mlir/include/mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h @@ -0,0 +1,31 @@ +//===- LocalAliasAnalysis.h - Local Stateless 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. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains the implementation of a local stateless alias analysis. +// This analysis walks from the values being compared to determine their +// potential for aliasing. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_ALIASANALYSIS_LOCALALIASANALYSIS_H_ +#define MLIR_ANALYSIS_ALIASANALYSIS_LOCALALIASANALYSIS_H_ + +#include "mlir/Analysis/AliasAnalysis.h" + +namespace mlir { +/// This class implements a location form of aliasing that tries to identify the +/// underlying values addressed by each value and performs a few basic checks to +/// see if they alias. +class LocalAliasAnalysis { +public: + /// Given two values, return their aliasing behavior. + AliasResult alias(Value lhs, Value rhs); +}; +} // end namespace mlir + +#endif // MLIR_ANALYSIS_ALIASANALYSIS_LOCALALIASANALYSIS_H_ diff --git a/mlir/include/mlir/IR/OpDefinition.h b/mlir/include/mlir/IR/OpDefinition.h --- a/mlir/include/mlir/IR/OpDefinition.h +++ b/mlir/include/mlir/IR/OpDefinition.h @@ -1133,8 +1133,8 @@ : public TraitBase { public: static LogicalResult verifyTrait(Operation *op) { - if (op->hasTrait()) - return op->emitOpError("is expected to have regions"); + static_assert(!ConcreteType::template hasTrait(), + "expected operation to have one or more regions"); return success(); } }; diff --git a/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td b/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td --- a/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td +++ b/mlir/include/mlir/Interfaces/SideEffectInterfaceBase.td @@ -110,6 +110,22 @@ llvm::erase_if(effects, [&](auto &it) { return it.getValue() != value; }); } + /// Return the effect of the given type `Effect` that is applied to the + /// given value, or None if no effect exists. + template + ::llvm::Optional<::mlir::SideEffects::EffectInstance<}] # baseEffect # [{>> + getEffectOnValue(::mlir::Value value) { + llvm::SmallVector<::mlir::SideEffects::EffectInstance< + }] # baseEffect # [{>, 4> effects; + getEffects(effects); + auto it = llvm::find_if(effects, [&](auto &it) { + return isa(it.getEffect()) && it.getValue() == value; + }); + if (it == effects.end()) + return llvm::None; + return *it; + } + /// Collect all of the effect instances that operate on the provided symbol /// reference and place them in 'effects'. void getEffectsOnSymbol(::mlir::SymbolRefAttr value, diff --git a/mlir/lib/Analysis/AliasAnalysis.cpp b/mlir/lib/Analysis/AliasAnalysis.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/AliasAnalysis.cpp @@ -0,0 +1,47 @@ +//===- AliasAnalysis.cpp - Alias Analysis for MLIR ------------------------===// +// +// 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/AliasAnalysis.h" +#include "mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h" + +using namespace mlir; + +//===----------------------------------------------------------------------===// +// AliasResult +//===----------------------------------------------------------------------===// + +/// Merge this alias result with `other` and return a new result that +/// represents the conservative merge of both results. +AliasResult AliasResult::merge(AliasResult other) const { + if (kind == other.kind) + return *this; + // A mix of PartialAlias and MustAlias is PartialAlias. + if ((isPartial() && other.isMust()) || (other.isPartial() && isMust())) + return PartialAlias; + // Otherwise, don't assume anything. + return MayAlias; +} + +//===----------------------------------------------------------------------===// +// AliasAnalysis +//===----------------------------------------------------------------------===// + +AliasAnalysis::AliasAnalysis(Operation *op) { + addAnalysisImplementation(LocalAliasAnalysis()); +} + +/// Given the two values, return their aliasing behavior. +AliasResult AliasAnalysis::alias(Value lhs, Value rhs) { + // Check each of the alias analysis implemenations for an alias result. + for (const std::unique_ptr &aliasImpl : aliasImpls) { + AliasResult result = aliasImpl->alias(lhs, rhs); + if (!result.isMay()) + return result; + } + return AliasResult::MayAlias; +} diff --git a/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp @@ -0,0 +1,335 @@ +//===- LocalAliasAnalysis.cpp - Local stateless alias Analysis for MLIR ---===// +// +// 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/AliasAnalysis/LocalAliasAnalysis.h" + +#include "mlir/IR/Matchers.h" +#include "mlir/Interfaces/ControlFlowInterfaces.h" +#include "mlir/Interfaces/SideEffectInterfaces.h" +#include "mlir/Interfaces/ViewLikeInterface.h" + +using namespace mlir; + +//===----------------------------------------------------------------------===// +// Underlying Address Computation +//===----------------------------------------------------------------------===// + +/// The maximum depth that will be searched when trying to find an underlying +/// value. +static constexpr unsigned maxUnderlyingValueSearchDepth = 10; + +/// Given a value, collect all of the underlying values being addressed. +static void collectUnderlyingAddressValues(Value value, unsigned maxDepth, + DenseSet &visited, + SmallVectorImpl &output); + +/// Given a successor (`region`) of a RegionBranchOpInterface, collect all of +/// the underlying values being addressed by one of the successor inputs. If the +/// provided `region` is null, as per `RegionBranchOpInterface` this represents +/// the parent operation. +static void collectUnderlyingAddressValues(RegionBranchOpInterface branch, + Region *region, Value inputValue, + unsigned inputIndex, + unsigned maxDepth, + DenseSet &visited, + SmallVectorImpl &output) { + // Given the index of a region of the branch (`predIndex`), or None to + // represent the parent operation, try to return the index into the outputs of + // this region predecessor that correspond to the input values of `region`. If + // an index could not be found, None is returned instead. + auto getOperandIndexIfPred = + [&](Optional predIndex) -> Optional { + SmallVector successors; + branch.getSuccessorRegions(predIndex, successors); + for (RegionSuccessor &successor : successors) { + if (successor.getSuccessor() != region) + continue; + // Check that the successor inputs map to the given input value. + ValueRange inputs = successor.getSuccessorInputs(); + if (inputs.empty()) { + output.push_back(inputValue); + break; + } + unsigned firstInputIndex, lastInputIndex; + if (region) { + firstInputIndex = inputs[0].cast().getArgNumber(); + lastInputIndex = inputs.back().cast().getArgNumber(); + } else { + firstInputIndex = inputs[0].cast().getResultNumber(); + lastInputIndex = inputs.back().cast().getResultNumber(); + } + if (firstInputIndex > inputIndex || lastInputIndex < inputIndex) { + output.push_back(inputValue); + break; + } + return inputIndex - firstInputIndex; + } + return llvm::None; + }; + + // Check branches from the parent operation. + if (region) { + if (Optional operandIndex = + getOperandIndexIfPred(/*predIndex=*/llvm::None)) { + collectUnderlyingAddressValues( + branch.getSuccessorEntryOperands( + region->getRegionNumber())[*operandIndex], + maxDepth, visited, output); + } + } + // Check branches from each child region. + Operation *op = branch.getOperation(); + for (int i = 0, e = op->getNumRegions(); i != e; ++i) { + if (Optional operandIndex = getOperandIndexIfPred(i)) { + for (Block &block : op->getRegion(i)) { + Operation *term = block.getTerminator(); + if (term->hasTrait()) { + collectUnderlyingAddressValues(term->getOperand(*operandIndex), + maxDepth, visited, output); + } else if (term->getNumSuccessors()) { + // Otherwise, if this terminator may exit the region we can't make + // any assumptions about which values get passed. + output.push_back(inputValue); + return; + } + } + } + } +} + +/// Given a result, collect all of the underlying values being addressed. +static void collectUnderlyingAddressValues(OpResult result, unsigned maxDepth, + DenseSet &visited, + SmallVectorImpl &output) { + Operation *op = result.getOwner(); + + // If this is a view, unwrap to the source. + if (ViewLikeOpInterface view = dyn_cast(op)) + return collectUnderlyingAddressValues(view.getViewSource(), maxDepth, + visited, output); + // Check to see if we can reason about the control flow of this op. + if (auto branch = dyn_cast(op)) { + return collectUnderlyingAddressValues(branch, /*region=*/nullptr, result, + result.getResultNumber(), maxDepth, + visited, output); + } + + output.push_back(result); +} + +/// Given a block argument, collect all of the underlying values being +/// addressed. +static void collectUnderlyingAddressValues(BlockArgument arg, unsigned maxDepth, + DenseSet &visited, + SmallVectorImpl &output) { + Block *block = arg.getOwner(); + unsigned argNumber = arg.getArgNumber(); + + // Handle the case of a non-entry block. + if (!block->isEntryBlock()) { + for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) { + auto branch = dyn_cast((*it)->getTerminator()); + if (!branch) { + // We can't analyze the control flow, so bail out early. + output.push_back(arg); + return; + } + + // Try to get the operand passed for this argument. + unsigned index = it.getSuccessorIndex(); + Optional operands = branch.getSuccessorOperands(index); + if (!operands) { + // We can't analyze the control flow, so bail out early. + output.push_back(arg); + return; + } + collectUnderlyingAddressValues((*operands)[argNumber], maxDepth, visited, + output); + } + return; + } + + // Otherwise, check to see if we can reason about the control flow of this op. + Region *region = block->getParent(); + Operation *op = region->getParentOp(); + if (auto branch = dyn_cast(op)) { + return collectUnderlyingAddressValues(branch, region, arg, argNumber, + maxDepth, visited, output); + } + + // We can't reason about the underlying address of this argument. + output.push_back(arg); +} + +/// Given a value, collect all of the underlying values being addressed. +static void collectUnderlyingAddressValues(Value value, unsigned maxDepth, + DenseSet &visited, + SmallVectorImpl &output) { + // Check that we don't infinitely recurse. + if (!visited.insert(value).second) + return; + if (maxDepth == 0) { + output.push_back(value); + return; + } + --maxDepth; + + if (BlockArgument arg = value.dyn_cast()) + return collectUnderlyingAddressValues(arg, maxDepth, visited, output); + collectUnderlyingAddressValues(value.cast(), maxDepth, visited, + output); +} + +/// Given a value, collect all of the underlying values being addressed. +static void collectUnderlyingAddressValues(Value value, + SmallVectorImpl &output) { + DenseSet visited; + collectUnderlyingAddressValues(value, maxUnderlyingValueSearchDepth, visited, + output); +} + +//===----------------------------------------------------------------------===// +// LocalAliasAnalysis +//===----------------------------------------------------------------------===// + +/// Given a value, try to get an allocation effect attached to it. If +/// successful, `allocEffect` is populated with the effect. If an effect was +/// found, `allocScopeOp` is also specified if a parent operation of `value` +/// could be identified that bounds the scope of the allocated value; i.e. if +/// non-null it specifies the parent operation that the allocation does not +/// escape. If no scope is found, `allocScopeOp` is set to nullptr. +static LogicalResult +getAllocEffectFor(Value value, Optional &effect, + Operation *&allocScopeOp) { + // Try to get a memory effect interface for the parent operation. + Operation *op; + if (BlockArgument arg = value.dyn_cast()) + op = arg.getOwner()->getParentOp(); + else + op = value.cast().getOwner(); + MemoryEffectOpInterface interface = dyn_cast(op); + if (!interface) + return failure(); + + // Try to find an allocation effect on the resource. + if (!(effect = interface.getEffectOnValue(value))) + return failure(); + + // If we found an allocation effect, try to find a scope for the allocation. + // If the resource of this allocation is automatically scoped, find the parent + // operation that bounds the allocation scope. + if (llvm::isa( + effect->getResource())) { + allocScopeOp = op->getParentWithTrait(); + return success(); + } + + // TODO: Here we could look at the users to see if the resource is either + // freed on all paths within the region, or is just not captured by anything. + allocScopeOp = nullptr; + return success(); +} + +/// Given the two values, return their aliasing behavior. +static AliasResult aliasImpl(Value lhs, Value rhs) { + if (lhs == rhs) + return AliasResult::MustAlias; + Operation *lhsAllocScope = nullptr, *rhsAllocScope = nullptr; + Optional lhsAlloc, rhsAlloc; + + // Handle the case where lhs is a constant. + Attribute lhsAttr, rhsAttr; + if (matchPattern(lhs, m_Constant(&lhsAttr))) { + // TODO: This is overly conservative. Two matching constants don't + // necessarily map to the same address. For example, if the two values + // correspond to different symbols that both represent a definition. + if (matchPattern(rhs, m_Constant(&rhsAttr))) + return AliasResult::MayAlias; + + // Try to find an alloc effect on rhs. If an effect was found we can't + // alias, otherwise we might. + return succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope)) + ? AliasResult::NoAlias + : AliasResult::MayAlias; + } + // Handle the case where rhs is a constant. + if (matchPattern(rhs, m_Constant(&rhsAttr))) { + // Try to find an alloc effect on lhs. If an effect was found we can't + // alias, otherwise we might. + return succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope)) + ? AliasResult::NoAlias + : AliasResult::MayAlias; + } + + // Otherwise, neither of the values are constant so check to see if either has + // an allocation effect. + bool lhsHasAlloc = succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope)); + bool rhsHasAlloc = succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope)); + if (lhsHasAlloc == rhsHasAlloc) { + // If both values have an allocation effect we know they don't alias, and if + // neither have an effect we can't make an assumptions. + return lhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias; + } + + // When we reach this point we have one value with a known allocation effect, + // and one without. Move the one with the effect to the lhs to make the next + // checks simpler. + if (rhsHasAlloc) { + std::swap(lhs, rhs); + lhsAlloc = rhsAlloc; + lhsAllocScope = rhsAllocScope; + } + + // If the effect has a scoped allocation region, check to see if the + // non-effect value is defined above that scope. + if (lhsAllocScope) { + // If the parent operation of rhs is an ancestor of the allocation scope, or + // if rhs is an entry block argument of the allocation scope we know the two + // values can't alias. + Operation *rhsParentOp = rhs.getParentRegion()->getParentOp(); + if (rhsParentOp->isProperAncestor(lhsAllocScope)) + return AliasResult::NoAlias; + if (rhsParentOp == lhsAllocScope) { + BlockArgument rhsArg = rhs.dyn_cast(); + if (rhsArg && rhs.getParentBlock()->isEntryBlock()) + return AliasResult::NoAlias; + } + } + + // If we couldn't reason about the relationship between the two values, + // conservatively assume they might alias. + return AliasResult::MayAlias; +} + +/// Given the two values, return their aliasing behavior. +AliasResult LocalAliasAnalysis::alias(Value lhs, Value rhs) { + if (lhs == rhs) + return AliasResult::MustAlias; + + // Get the underlying values being addressed. + SmallVector lhsValues, rhsValues; + collectUnderlyingAddressValues(lhs, lhsValues); + collectUnderlyingAddressValues(rhs, rhsValues); + + // If we failed to collect for either of the values somehow, conservatively + // assume they may alias. + if (lhsValues.empty() || rhsValues.empty()) + return AliasResult::MayAlias; + + // Check the alias results against each of the underlying values. + Optional result; + for (Value lhsVal : lhsValues) { + for (Value rhsVal : rhsValues) { + AliasResult nextResult = aliasImpl(lhsVal, rhsVal); + result = result ? result->merge(nextResult) : nextResult; + } + } + + // We should always have a valid result here. + return *result; +} 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,4 +1,5 @@ set(LLVM_OPTIONAL_SOURCES + AliasAnalysis.cpp AffineAnalysis.cpp AffineStructures.cpp BufferAliasAnalysis.cpp @@ -11,15 +12,20 @@ PresburgerSet.cpp SliceAnalysis.cpp Utils.cpp + + AliasAnalysis/LocalAliasAnalysis.cpp ) add_mlir_library(MLIRAnalysis + AliasAnalysis.cpp BufferAliasAnalysis.cpp CallGraph.cpp Liveness.cpp NumberOfExecutions.cpp SliceAnalysis.cpp + AliasAnalysis/LocalAliasAnalysis.cpp + ADDITIONAL_HEADER_DIRS ${MLIR_MAIN_INCLUDE_DIR}/mlir/Analysis diff --git a/mlir/test/Analysis/test-alias-analysis.mlir b/mlir/test/Analysis/test-alias-analysis.mlir new file mode 100644 --- /dev/null +++ b/mlir/test/Analysis/test-alias-analysis.mlir @@ -0,0 +1,235 @@ +// RUN: mlir-opt %s -pass-pipeline='func(test-alias-analysis)' -split-input-file -allow-unregistered-dialect 2>&1 | FileCheck %s + +// CHECK-LABEL: Testing : "simple" +// CHECK-DAG: func.region0#0 <-> func.region0#1: MayAlias + +// CHECK-DAG: alloca_1#0 <-> alloca_2#0: NoAlias +// CHECK-DAG: alloca_1#0 <-> alloc_1#0: NoAlias +// CHECK-DAG: alloca_1#0 <-> alloc_2#0: NoAlias +// CHECK-DAG: alloca_1#0 <-> func.region0#0: NoAlias +// CHECK-DAG: alloca_1#0 <-> func.region0#1: NoAlias + +// CHECK-DAG: alloca_2#0 <-> alloc_1#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> alloc_2#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> func.region0#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> func.region0#1: NoAlias + +// TODO: The MayAlias below is overly conservative and should be provably +// NoAlias with a proper escape analysis. +// CHECK-DAG: alloc_1#0 <-> alloc_2#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> func.region0#0: MayAlias +// CHECK-DAG: alloc_1#0 <-> func.region0#1: MayAlias + +// CHECK-DAG: alloc_2#0 <-> func.region0#0: MayAlias +// CHECK-DAG: alloc_2#0 <-> func.region0#1: MayAlias +func @simple(%arg: memref<2xf32>, %arg1: memref<2xf32>) attributes {test.ptr = "func"} { + %0 = alloca() {test.ptr = "alloca_1"} : memref<8x64xf32> + %1 = alloca() {test.ptr = "alloca_2"} : memref<8x64xf32> + %2 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + %3 = alloc() {test.ptr = "alloc_2"} : memref<8x64xf32> + return +} + +// ----- + +// CHECK-LABEL: Testing : "control_flow" +// CHECK-DAG: alloca_1#0 <-> func.region0.block1#0: MustAlias +// CHECK-DAG: alloca_1#0 <-> func.region0.block2#0: MustAlias + +// CHECK-DAG: alloca_2#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> func.region0.block2#0: NoAlias + +// CHECK-DAG: alloc_1#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> func.region0.block2#0: NoAlias + +// CHECK-DAG: func.region0#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: func.region0#0 <-> func.region0.block2#0: NoAlias + +// CHECK-DAG: func.region0#1 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: func.region0#1 <-> func.region0.block2#0: NoAlias + +// CHECK-DAG: func.region0.block1#0 <-> func.region0.block2#0: MustAlias +func @control_flow(%arg: memref<2xf32>, %cond: i1) attributes {test.ptr = "func"} { + %0 = alloca() {test.ptr = "alloca_1"} : memref<8x64xf32> + %1 = alloca() {test.ptr = "alloca_2"} : memref<8x64xf32> + %2 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + cond_br %cond, ^bb1(%0 : memref<8x64xf32>), ^bb2(%0 : memref<8x64xf32>) + +^bb1(%arg1: memref<8x64xf32>): + br ^bb2(%arg1 : memref<8x64xf32>) + +^bb2(%arg2: memref<8x64xf32>): + return +} + +// ----- + +// CHECK-LABEL: Testing : "control_flow_merge" +// CHECK-DAG: alloca_1#0 <-> func.region0.block1#0: MustAlias +// CHECK-DAG: alloca_1#0 <-> func.region0.block2#0: MayAlias + +// CHECK-DAG: alloca_2#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> func.region0.block2#0: NoAlias + +// CHECK-DAG: alloc_1#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> func.region0.block2#0: MayAlias + +// CHECK-DAG: func.region0#0 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: func.region0#0 <-> func.region0.block2#0: MayAlias + +// CHECK-DAG: func.region0#1 <-> func.region0.block1#0: NoAlias +// CHECK-DAG: func.region0#1 <-> func.region0.block2#0: MayAlias + +// CHECK-DAG: func.region0.block1#0 <-> func.region0.block2#0: MayAlias +func @control_flow_merge(%arg: memref<2xf32>, %cond: i1) attributes {test.ptr = "func"} { + %0 = alloca() {test.ptr = "alloca_1"} : memref<8x64xf32> + %1 = alloca() {test.ptr = "alloca_2"} : memref<8x64xf32> + %2 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + cond_br %cond, ^bb1(%0 : memref<8x64xf32>), ^bb2(%2 : memref<8x64xf32>) + +^bb1(%arg1: memref<8x64xf32>): + br ^bb2(%arg1 : memref<8x64xf32>) + +^bb2(%arg2: memref<8x64xf32>): + return +} + +// ----- + +// CHECK-LABEL: Testing : "region_control_flow" +// CHECK-DAG: alloca_1#0 <-> if_alloca#0: MustAlias +// CHECK-DAG: alloca_1#0 <-> if_alloca_merge#0: MayAlias +// CHECK-DAG: alloca_1#0 <-> if_alloc#0: NoAlias + +// CHECK-DAG: alloca_2#0 <-> if_alloca#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> if_alloca_merge#0: MayAlias +// CHECK-DAG: alloca_2#0 <-> if_alloc#0: NoAlias + +// CHECK-DAG: alloc_1#0 <-> if_alloca#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> if_alloca_merge#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> if_alloc#0: MustAlias + +// CHECK-DAG: if_alloca#0 <-> if_alloca_merge#0: MayAlias +// CHECK-DAG: if_alloca#0 <-> if_alloc#0: NoAlias +// CHECK-DAG: if_alloca#0 <-> func.region0#0: NoAlias +// CHECK-DAG: if_alloca#0 <-> func.region0#1: NoAlias + +// CHECK-DAG: if_alloca_merge#0 <-> if_alloc#0: NoAlias +// CHECK-DAG: if_alloca_merge#0 <-> func.region0#0: NoAlias +// CHECK-DAG: if_alloca_merge#0 <-> func.region0#1: NoAlias + +// CHECK-DAG: if_alloc#0 <-> func.region0#0: MayAlias +// CHECK-DAG: if_alloc#0 <-> func.region0#1: MayAlias +func @region_control_flow(%arg: memref<2xf32>, %cond: i1) attributes {test.ptr = "func"} { + %0 = alloca() {test.ptr = "alloca_1"} : memref<8x64xf32> + %1 = alloca() {test.ptr = "alloca_2"} : memref<8x64xf32> + %2 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + %3 = scf.if %cond -> (memref<8x64xf32>) { + scf.yield %0 : memref<8x64xf32> + } else { + scf.yield %0 : memref<8x64xf32> + } {test.ptr = "if_alloca"} + + %4 = scf.if %cond -> (memref<8x64xf32>) { + scf.yield %0 : memref<8x64xf32> + } else { + scf.yield %1 : memref<8x64xf32> + } {test.ptr = "if_alloca_merge"} + + %5 = scf.if %cond -> (memref<8x64xf32>) { + scf.yield %2 : memref<8x64xf32> + } else { + scf.yield %2 : memref<8x64xf32> + } {test.ptr = "if_alloc"} + return +} + +// ----- + +// CHECK-LABEL: Testing : "region_loop_control_flow" +// CHECK-DAG: alloca_1#0 <-> for_alloca#0: MustAlias +// CHECK-DAG: alloca_1#0 <-> for_alloca.region0#0: MayAlias +// CHECK-DAG: alloca_1#0 <-> for_alloca.region0#1: MustAlias + +// CHECK-DAG: alloca_2#0 <-> for_alloca#0: NoAlias +// CHECK-DAG: alloca_2#0 <-> for_alloca.region0#0: MayAlias +// CHECK-DAG: alloca_2#0 <-> for_alloca.region0#1: NoAlias + +// CHECK-DAG: alloc_1#0 <-> for_alloca#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> for_alloca.region0#0: MayAlias +// CHECK-DAG: alloc_1#0 <-> for_alloca.region0#1: NoAlias + +// CHECK-DAG: for_alloca#0 <-> for_alloca.region0#0: MayAlias +// CHECK-DAG: for_alloca#0 <-> for_alloca.region0#1: MustAlias +// CHECK-DAG: for_alloca#0 <-> func.region0#0: NoAlias +// CHECK-DAG: for_alloca#0 <-> func.region0#1: NoAlias +// CHECK-DAG: for_alloca#0 <-> func.region0#2: NoAlias +// CHECK-DAG: for_alloca#0 <-> func.region0#3: NoAlias + +// CHECK-DAG: for_alloca.region0#0 <-> for_alloca.region0#1: MayAlias +// CHECK-DAG: for_alloca.region0#0 <-> func.region0#0: MayAlias +// CHECK-DAG: for_alloca.region0#0 <-> func.region0#1: MayAlias +// CHECK-DAG: for_alloca.region0#0 <-> func.region0#2: MayAlias +// CHECK-DAG: for_alloca.region0#0 <-> func.region0#3: MayAlias + +// CHECK-DAG: for_alloca.region0#1 <-> func.region0#0: NoAlias +// CHECK-DAG: for_alloca.region0#1 <-> func.region0#1: NoAlias +// CHECK-DAG: for_alloca.region0#1 <-> func.region0#2: NoAlias +// CHECK-DAG: for_alloca.region0#1 <-> func.region0#3: NoAlias +func @region_loop_control_flow(%arg: memref<2xf32>, %loopI0 : index, + %loopI1 : index, %loopI2 : index) attributes {test.ptr = "func"} { + %0 = alloca() {test.ptr = "alloca_1"} : memref<8x64xf32> + %1 = alloca() {test.ptr = "alloca_2"} : memref<8x64xf32> + %2 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + %result = scf.for %i0 = %loopI0 to %loopI1 step %loopI2 iter_args(%si = %0) -> (memref<8x64xf32>) { + scf.yield %si : memref<8x64xf32> + } {test.ptr = "for_alloca"} + return +} + +// ----- + +// CHECK-LABEL: Testing : "view_like" +// CHECK-DAG: alloc_1#0 <-> view#0: NoAlias + +// CHECK-DAG: alloca_1#0 <-> view#0: MustAlias + +// CHECK-DAG: view#0 <-> func.region0#0: NoAlias +// CHECK-DAG: view#0 <-> func.region0#1: NoAlias +func @view_like(%arg: memref<2xf32>, %size: index) attributes {test.ptr = "func"} { + %1 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + %c0 = constant 0 : index + %2 = alloca (%size) {test.ptr = "alloca_1"} : memref + %3 = view %2[%c0][] {test.ptr = "view"} : memref to memref<8x64xf32> + return +} + +// ----- + +// CHECK-LABEL: Testing : "constants" +// CHECK-DAG: alloc_1#0 <-> constant_1#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> constant_2#0: NoAlias +// CHECK-DAG: alloc_1#0 <-> constant_3#0: NoAlias + +// CHECK-DAG: constant_1#0 <-> constant_2#0: MayAlias +// CHECK-DAG: constant_1#0 <-> constant_3#0: MayAlias +// CHECK-DAG: constant_1#0 <-> func.region0#0: MayAlias + +// CHECK-DAG: constant_2#0 <-> constant_3#0: MayAlias +// CHECK-DAG: constant_2#0 <-> func.region0#0: MayAlias + +// CHECK-DAG: constant_3#0 <-> func.region0#0: MayAlias +func @constants(%arg: memref<2xf32>) attributes {test.ptr = "func"} { + %1 = alloc() {test.ptr = "alloc_1"} : memref<8x64xf32> + + %c0 = constant {test.ptr = "constant_1"} 0 : index + %c0_2 = constant {test.ptr = "constant_2"} 0 : index + %c1 = constant {test.ptr = "constant_3"} 1 : index + + return +} diff --git a/mlir/test/lib/Analysis/CMakeLists.txt b/mlir/test/lib/Analysis/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/mlir/test/lib/Analysis/CMakeLists.txt @@ -0,0 +1,20 @@ +# Exclude tests from libMLIR.so +add_mlir_library(MLIRTestAnalysis + TestAliasAnalysis.cpp + + EXCLUDE_FROM_LIBMLIR + + ADDITIONAL_HEADER_DIRS + ${MLIR_MAIN_INCLUDE_DIR}/mlir/Transforms + + DEPENDS + MLIRStandardOpsIncGen + + LINK_LIBS PUBLIC + MLIRAnalysis + MLIRPass + MLIRTestDialect + ) + +include_directories(${CMAKE_CURRENT_SOURCE_DIR}/../Dialect/Test) +include_directories(${CMAKE_CURRENT_BINARY_DIR}/../Dialect/Test) diff --git a/mlir/test/lib/Analysis/TestAliasAnalysis.cpp b/mlir/test/lib/Analysis/TestAliasAnalysis.cpp new file mode 100644 --- /dev/null +++ b/mlir/test/lib/Analysis/TestAliasAnalysis.cpp @@ -0,0 +1,100 @@ +//===- TestAliasAnalysis.cpp - Test alias analysis results ----------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// This file contains test passes for constructing and testing alias analysis +// results. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/AliasAnalysis.h" +#include "mlir/Pass/Pass.h" + +using namespace mlir; + +namespace { +struct TestAliasAnalysisPass + : public PassWrapper> { + void runOnOperation() override { + llvm::errs() << "Testing : "; + if (Attribute testName = getOperation()->getAttr("test.name")) + llvm::errs() << testName << "\n"; + else + llvm::errs() << getOperation()->getAttr("sym_name") << "\n"; + + // Collect all of the values to check for aliasing behavior. + AliasAnalysis &aliasAnalysis = getAnalysis(); + SmallVector valsToCheck; + getOperation()->walk([&](Operation *op) { + if (!op->getAttr("test.ptr")) + return; + valsToCheck.append(op->result_begin(), op->result_end()); + for (Region ®ion : op->getRegions()) + for (Block &block : region) + valsToCheck.append(block.args_begin(), block.args_end()); + }); + + // Check for aliasing behavior between each of the values. + for (auto it = valsToCheck.begin(), e = valsToCheck.end(); it != e; ++it) + for (auto innerIt = valsToCheck.begin(); innerIt != it; ++innerIt) + printAliasResult(aliasAnalysis.alias(*innerIt, *it), *innerIt, *it); + } + + /// Print the result of an alias query. + void printAliasResult(AliasResult result, Value lhs, Value rhs) { + printAliasOperand(lhs); + llvm::errs() << " <-> "; + printAliasOperand(rhs); + llvm::errs() << ": "; + + switch (result.getKind()) { + case AliasResult::NoAlias: + llvm::errs() << "NoAlias"; + break; + case AliasResult::MayAlias: + llvm::errs() << "MayAlias"; + break; + case AliasResult::PartialAlias: + llvm::errs() << "PartialAlias"; + break; + case AliasResult::MustAlias: + llvm::errs() << "MustAlias"; + break; + } + llvm::errs() << "\n"; + } + /// Print a value that is used as an operand of an alias query. + void printAliasOperand(Value value) { + if (BlockArgument arg = value.dyn_cast()) { + Region *region = arg.getParentRegion(); + unsigned parentBlockNumber = + std::distance(region->begin(), arg.getOwner()->getIterator()); + llvm::errs() << region->getParentOp() + ->getAttrOfType("test.ptr") + .getValue() + << ".region" << region->getRegionNumber(); + if (parentBlockNumber != 0) + llvm::errs() << ".block" << parentBlockNumber; + llvm::errs() << "#" << arg.getArgNumber(); + return; + } + OpResult result = value.cast(); + llvm::errs() + << result.getOwner()->getAttrOfType("test.ptr").getValue() + << "#" << result.getResultNumber(); + } +}; +} // end anonymous namespace + +namespace mlir { +namespace test { +void registerTestAliasAnalysisPass() { + PassRegistration pass("test-alias-analysis", + "Test alias analysis results."); +} +} // namespace test +} // namespace mlir diff --git a/mlir/test/lib/CMakeLists.txt b/mlir/test/lib/CMakeLists.txt --- a/mlir/test/lib/CMakeLists.txt +++ b/mlir/test/lib/CMakeLists.txt @@ -1,3 +1,4 @@ +add_subdirectory(Analysis) add_subdirectory(Dialect) add_subdirectory(IR) add_subdirectory(Pass) diff --git a/mlir/tools/mlir-opt/CMakeLists.txt b/mlir/tools/mlir-opt/CMakeLists.txt --- a/mlir/tools/mlir-opt/CMakeLists.txt +++ b/mlir/tools/mlir-opt/CMakeLists.txt @@ -15,6 +15,7 @@ MLIRAffineTransformsTestPasses MLIRShapeTestPasses MLIRSPIRVTestPasses + MLIRTestAnalysis MLIRTestDialect MLIRTestIR MLIRTestPass diff --git a/mlir/tools/mlir-opt/mlir-opt.cpp b/mlir/tools/mlir-opt/mlir-opt.cpp --- a/mlir/tools/mlir-opt/mlir-opt.cpp +++ b/mlir/tools/mlir-opt/mlir-opt.cpp @@ -60,6 +60,7 @@ void registerPatternsTestPass(); void registerSimpleParametricTilingPass(); void registerTestAffineLoopParametricTilingPass(); +void registerTestAliasAnalysisPass(); void registerTestCallGraphPass(); void registerTestConstantFold(); void registerTestConvVectorization(); @@ -129,6 +130,7 @@ test::registerPatternsTestPass(); test::registerSimpleParametricTilingPass(); test::registerTestAffineLoopParametricTilingPass(); + test::registerTestAliasAnalysisPass(); test::registerTestCallGraphPass(); test::registerTestConstantFold(); #if MLIR_CUDA_CONVERSIONS_ENABLED