567 lines · cpp
1//===- LocalAliasAnalysis.cpp - Local stateless alias Analysis for MLIR ---===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "mlir/Analysis/AliasAnalysis/LocalAliasAnalysis.h"10 11#include "mlir/Analysis/AliasAnalysis.h"12#include "mlir/IR/Attributes.h"13#include "mlir/IR/Block.h"14#include "mlir/IR/Matchers.h"15#include "mlir/IR/OpDefinition.h"16#include "mlir/IR/Operation.h"17#include "mlir/IR/Region.h"18#include "mlir/IR/Value.h"19#include "mlir/Interfaces/ControlFlowInterfaces.h"20#include "mlir/Interfaces/FunctionInterfaces.h"21#include "mlir/Interfaces/SideEffectInterfaces.h"22#include "mlir/Interfaces/ViewLikeInterface.h"23#include "mlir/Support/LLVM.h"24#include "llvm/Support/Casting.h"25#include "llvm/Support/DebugLog.h"26#include <cassert>27#include <optional>28#include <utility>29 30using namespace mlir;31 32#define DEBUG_TYPE "local-alias-analysis"33 34//===----------------------------------------------------------------------===//35// Underlying Address Computation36//===----------------------------------------------------------------------===//37 38/// The maximum depth that will be searched when trying to find an underlying39/// value.40static constexpr unsigned maxUnderlyingValueSearchDepth = 10;41 42/// Given a value, collect all of the underlying values being addressed.43static void collectUnderlyingAddressValues(Value value, unsigned maxDepth,44 DenseSet<Value> &visited,45 SmallVectorImpl<Value> &output);46 47/// Given a RegionBranchOpInterface operation (`branch`), a Value`inputValue`48/// which is an input for the provided successor (`initialSuccessor`), try to49/// find the possible sources for the value along the control flow edges.50static void collectUnderlyingAddressValues2(51 RegionBranchOpInterface branch, RegionSuccessor initialSuccessor,52 Value inputValue, unsigned inputIndex, unsigned maxDepth,53 DenseSet<Value> &visited, SmallVectorImpl<Value> &output) {54 LDBG() << "collectUnderlyingAddressValues2: "55 << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions());56 LDBG() << " with initialSuccessor " << initialSuccessor;57 LDBG() << " inputValue: " << inputValue;58 LDBG() << " inputIndex: " << inputIndex;59 LDBG() << " maxDepth: " << maxDepth;60 ValueRange inputs = initialSuccessor.getSuccessorInputs();61 if (inputs.empty()) {62 LDBG() << " input is empty, enqueue value";63 output.push_back(inputValue);64 return;65 }66 unsigned firstInputIndex, lastInputIndex;67 if (isa<BlockArgument>(inputs[0])) {68 firstInputIndex = cast<BlockArgument>(inputs[0]).getArgNumber();69 lastInputIndex = cast<BlockArgument>(inputs.back()).getArgNumber();70 } else {71 firstInputIndex = cast<OpResult>(inputs[0]).getResultNumber();72 lastInputIndex = cast<OpResult>(inputs.back()).getResultNumber();73 }74 if (firstInputIndex > inputIndex || lastInputIndex < inputIndex) {75 LDBG() << " !! Input index " << inputIndex << " out of range "76 << firstInputIndex << " to " << lastInputIndex77 << ", adding input value to output";78 output.push_back(inputValue);79 return;80 }81 SmallVector<Value> predecessorValues;82 branch.getPredecessorValues(initialSuccessor, inputIndex - firstInputIndex,83 predecessorValues);84 LDBG() << " Found " << predecessorValues.size() << " predecessor values";85 for (Value predecessorValue : predecessorValues) {86 LDBG() << " Processing predecessor value: " << predecessorValue;87 collectUnderlyingAddressValues(predecessorValue, maxDepth, visited, output);88 }89}90 91/// Given a result, collect all of the underlying values being addressed.92static void collectUnderlyingAddressValues(OpResult result, unsigned maxDepth,93 DenseSet<Value> &visited,94 SmallVectorImpl<Value> &output) {95 LDBG() << "collectUnderlyingAddressValues (OpResult): " << result;96 LDBG() << " maxDepth: " << maxDepth;97 98 Operation *op = result.getOwner();99 100 // If this is a view, unwrap to the source.101 if (ViewLikeOpInterface view = dyn_cast<ViewLikeOpInterface>(op)) {102 if (result == view.getViewDest()) {103 LDBG() << " Unwrapping view to source: " << view.getViewSource();104 return collectUnderlyingAddressValues(view.getViewSource(), maxDepth,105 visited, output);106 }107 }108 // Check to see if we can reason about the control flow of this op.109 if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {110 LDBG() << " Processing region branch operation";111 return collectUnderlyingAddressValues2(112 branch, RegionSuccessor(op, op->getResults()), result,113 result.getResultNumber(), maxDepth, visited, output);114 }115 116 LDBG() << " Adding result to output: " << result;117 output.push_back(result);118}119 120/// Given a block argument, collect all of the underlying values being121/// addressed.122static void collectUnderlyingAddressValues(BlockArgument arg, unsigned maxDepth,123 DenseSet<Value> &visited,124 SmallVectorImpl<Value> &output) {125 LDBG() << "collectUnderlyingAddressValues (BlockArgument): " << arg;126 LDBG() << " maxDepth: " << maxDepth;127 LDBG() << " argNumber: " << arg.getArgNumber();128 LDBG() << " isEntryBlock: " << arg.getOwner()->isEntryBlock();129 130 Block *block = arg.getOwner();131 unsigned argNumber = arg.getArgNumber();132 133 // Handle the case of a non-entry block.134 if (!block->isEntryBlock()) {135 LDBG() << " Processing non-entry block with "136 << std::distance(block->pred_begin(), block->pred_end())137 << " predecessors";138 for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {139 auto branch = dyn_cast<BranchOpInterface>((*it)->getTerminator());140 if (!branch) {141 LDBG() << " Cannot analyze control flow, adding argument to output";142 // We can't analyze the control flow, so bail out early.143 output.push_back(arg);144 return;145 }146 147 // Try to get the operand passed for this argument.148 unsigned index = it.getSuccessorIndex();149 Value operand = branch.getSuccessorOperands(index)[argNumber];150 if (!operand) {151 LDBG() << " No operand found for argument, adding to output";152 // We can't analyze the control flow, so bail out early.153 output.push_back(arg);154 return;155 }156 LDBG() << " Processing operand from predecessor: " << operand;157 collectUnderlyingAddressValues(operand, maxDepth, visited, output);158 }159 return;160 }161 162 // Otherwise, check to see if we can reason about the control flow of this op.163 Region *region = block->getParent();164 Operation *op = region->getParentOp();165 if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {166 LDBG() << " Processing region branch operation for entry block";167 // We have to find the successor matching the region, so that the input168 // arguments are correctly set.169 // TODO: this isn't comprehensive: the successor may not be reachable from170 // the entry block.171 SmallVector<RegionSuccessor> successors;172 branch.getSuccessorRegions(RegionBranchPoint::parent(), successors);173 RegionSuccessor regionSuccessor(region);174 bool found = false;175 for (RegionSuccessor &successor : successors) {176 if (successor.getSuccessor() == region) {177 LDBG() << " Found matching region successor: " << successor;178 found = true;179 regionSuccessor = successor;180 break;181 }182 }183 if (!found) {184 LDBG()185 << " No matching region successor found, adding argument to output";186 output.push_back(arg);187 return;188 }189 return collectUnderlyingAddressValues2(190 branch, regionSuccessor, arg, argNumber, maxDepth, visited, output);191 }192 193 LDBG()194 << " Cannot reason about underlying address, adding argument to output";195 // We can't reason about the underlying address of this argument.196 output.push_back(arg);197}198 199/// Given a value, collect all of the underlying values being addressed.200static void collectUnderlyingAddressValues(Value value, unsigned maxDepth,201 DenseSet<Value> &visited,202 SmallVectorImpl<Value> &output) {203 LDBG() << "collectUnderlyingAddressValues: " << value;204 LDBG() << " maxDepth: " << maxDepth;205 206 // Check that we don't infinitely recurse.207 if (!visited.insert(value).second) {208 LDBG() << " Value already visited, skipping";209 return;210 }211 if (maxDepth == 0) {212 LDBG() << " Max depth reached, adding value to output";213 output.push_back(value);214 return;215 }216 --maxDepth;217 218 if (BlockArgument arg = dyn_cast<BlockArgument>(value)) {219 LDBG() << " Processing as BlockArgument";220 return collectUnderlyingAddressValues(arg, maxDepth, visited, output);221 }222 LDBG() << " Processing as OpResult";223 collectUnderlyingAddressValues(cast<OpResult>(value), maxDepth, visited,224 output);225}226 227/// Given a value, collect all of the underlying values being addressed.228static void collectUnderlyingAddressValues(Value value,229 SmallVectorImpl<Value> &output) {230 LDBG() << "collectUnderlyingAddressValues: " << value;231 DenseSet<Value> visited;232 collectUnderlyingAddressValues(value, maxUnderlyingValueSearchDepth, visited,233 output);234 LDBG() << " Collected " << output.size() << " underlying values";235}236 237//===----------------------------------------------------------------------===//238// LocalAliasAnalysis: alias239//===----------------------------------------------------------------------===//240 241/// Given a value, try to get an allocation effect attached to it. If242/// successful, `allocEffect` is populated with the effect. If an effect was243/// found, `allocScopeOp` is also specified if a parent operation of `value`244/// could be identified that bounds the scope of the allocated value; i.e. if245/// non-null it specifies the parent operation that the allocation does not246/// escape. If no scope is found, `allocScopeOp` is set to nullptr.247static LogicalResult248getAllocEffectFor(Value value,249 std::optional<MemoryEffects::EffectInstance> &effect,250 Operation *&allocScopeOp) {251 LDBG() << "getAllocEffectFor: " << value;252 253 // Try to get a memory effect interface for the parent operation.254 Operation *op;255 if (BlockArgument arg = dyn_cast<BlockArgument>(value)) {256 op = arg.getOwner()->getParentOp();257 LDBG() << " BlockArgument, parent op: "258 << OpWithFlags(op, OpPrintingFlags().skipRegions());259 } else {260 op = cast<OpResult>(value).getOwner();261 LDBG() << " OpResult, owner op: "262 << OpWithFlags(op, OpPrintingFlags().skipRegions());263 }264 265 MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);266 if (!interface) {267 LDBG() << " No memory effect interface found";268 return failure();269 }270 271 // Try to find an allocation effect on the resource.272 if (!(effect = interface.getEffectOnValue<MemoryEffects::Allocate>(value))) {273 LDBG() << " No allocation effect found on value";274 return failure();275 }276 277 LDBG() << " Found allocation effect";278 279 // If we found an allocation effect, try to find a scope for the allocation.280 // If the resource of this allocation is automatically scoped, find the parent281 // operation that bounds the allocation scope.282 if (llvm::isa<SideEffects::AutomaticAllocationScopeResource>(283 effect->getResource())) {284 allocScopeOp = op->getParentWithTrait<OpTrait::AutomaticAllocationScope>();285 if (allocScopeOp) {286 LDBG() << " Automatic allocation scope found: "287 << OpWithFlags(allocScopeOp, OpPrintingFlags().skipRegions());288 } else {289 LDBG() << " Automatic allocation scope found: null";290 }291 return success();292 }293 294 // TODO: Here we could look at the users to see if the resource is either295 // freed on all paths within the region, or is just not captured by anything.296 // For now assume allocation scope to the function scope (we don't care if297 // pointer escape outside function).298 allocScopeOp = op->getParentOfType<FunctionOpInterface>();299 if (allocScopeOp) {300 LDBG() << " Function scope found: "301 << OpWithFlags(allocScopeOp, OpPrintingFlags().skipRegions());302 } else {303 LDBG() << " Function scope found: null";304 }305 return success();306}307 308static Operation *isDistinctObjectsOp(Operation *op) {309 if (op && op->hasTrait<OpTrait::DistinctObjectsTrait>())310 return op;311 312 return nullptr;313}314 315static Value getDistinctObjectsOperand(Operation *op, Value value) {316 unsigned argNumber = cast<OpResult>(value).getResultNumber();317 return op->getOperand(argNumber);318}319 320static std::optional<AliasResult> checkDistinctObjects(Value lhs, Value rhs) {321 // We should already checked that lhs and rhs are different.322 assert(lhs != rhs && "lhs and rhs must be different");323 324 // Result and corresponding operand must alias.325 auto lhsOp = isDistinctObjectsOp(lhs.getDefiningOp());326 if (lhsOp && getDistinctObjectsOperand(lhsOp, lhs) == rhs)327 return AliasResult::MustAlias;328 329 auto rhsOp = isDistinctObjectsOp(rhs.getDefiningOp());330 if (rhsOp && getDistinctObjectsOperand(rhsOp, rhs) == lhs)331 return AliasResult::MustAlias;332 333 // If two different values come from the same `DistinctObjects` operation,334 // they don't alias.335 if (lhsOp && lhsOp == rhsOp)336 return AliasResult::NoAlias;337 338 return std::nullopt;339}340 341/// Given the two values, return their aliasing behavior.342AliasResult LocalAliasAnalysis::aliasImpl(Value lhs, Value rhs) {343 LDBG() << "aliasImpl: " << lhs << " vs " << rhs;344 345 if (lhs == rhs) {346 LDBG() << " Same value, must alias";347 return AliasResult::MustAlias;348 }349 350 Operation *lhsAllocScope = nullptr, *rhsAllocScope = nullptr;351 std::optional<MemoryEffects::EffectInstance> lhsAlloc, rhsAlloc;352 353 // Handle the case where lhs is a constant.354 Attribute lhsAttr, rhsAttr;355 if (matchPattern(lhs, m_Constant(&lhsAttr))) {356 LDBG() << " lhs is constant";357 // TODO: This is overly conservative. Two matching constants don't358 // necessarily map to the same address. For example, if the two values359 // correspond to different symbols that both represent a definition.360 if (matchPattern(rhs, m_Constant(&rhsAttr))) {361 LDBG() << " rhs is also constant, may alias";362 return AliasResult::MayAlias;363 }364 365 // Try to find an alloc effect on rhs. If an effect was found we can't366 // alias, otherwise we might.367 bool rhsHasAlloc =368 succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope));369 LDBG() << " rhs has alloc effect: " << rhsHasAlloc;370 return rhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias;371 }372 // Handle the case where rhs is a constant.373 if (matchPattern(rhs, m_Constant(&rhsAttr))) {374 LDBG() << " rhs is constant";375 // Try to find an alloc effect on lhs. If an effect was found we can't376 // alias, otherwise we might.377 bool lhsHasAlloc =378 succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope));379 LDBG() << " lhs has alloc effect: " << lhsHasAlloc;380 return lhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias;381 }382 383 if (std::optional<AliasResult> result = checkDistinctObjects(lhs, rhs))384 return *result;385 386 // Otherwise, neither of the values are constant so check to see if either has387 // an allocation effect.388 bool lhsHasAlloc = succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope));389 bool rhsHasAlloc = succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope));390 LDBG() << " lhs has alloc effect: " << lhsHasAlloc;391 LDBG() << " rhs has alloc effect: " << rhsHasAlloc;392 393 if (lhsHasAlloc == rhsHasAlloc) {394 // If both values have an allocation effect we know they don't alias, and if395 // neither have an effect we can't make an assumptions.396 LDBG() << " Both have same alloc status: "397 << (lhsHasAlloc ? "NoAlias" : "MayAlias");398 return lhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias;399 }400 401 // When we reach this point we have one value with a known allocation effect,402 // and one without. Move the one with the effect to the lhs to make the next403 // checks simpler.404 if (rhsHasAlloc) {405 LDBG() << " Swapping lhs and rhs to put alloc effect on lhs";406 std::swap(lhs, rhs);407 lhsAlloc = rhsAlloc;408 lhsAllocScope = rhsAllocScope;409 }410 411 // If the effect has a scoped allocation region, check to see if the412 // non-effect value is defined above that scope.413 if (lhsAllocScope) {414 LDBG() << " Checking allocation scope: "415 << OpWithFlags(lhsAllocScope, OpPrintingFlags().skipRegions());416 // If the parent operation of rhs is an ancestor of the allocation scope, or417 // if rhs is an entry block argument of the allocation scope we know the two418 // values can't alias.419 Operation *rhsParentOp = rhs.getParentRegion()->getParentOp();420 if (rhsParentOp->isProperAncestor(lhsAllocScope)) {421 LDBG() << " rhs parent is ancestor of alloc scope, no alias";422 return AliasResult::NoAlias;423 }424 if (rhsParentOp == lhsAllocScope) {425 BlockArgument rhsArg = dyn_cast<BlockArgument>(rhs);426 if (rhsArg && rhs.getParentBlock()->isEntryBlock()) {427 LDBG() << " rhs is entry block arg of alloc scope, no alias";428 return AliasResult::NoAlias;429 }430 }431 }432 433 // If we couldn't reason about the relationship between the two values,434 // conservatively assume they might alias.435 LDBG() << " Cannot reason about relationship, may alias";436 return AliasResult::MayAlias;437}438 439/// Given the two values, return their aliasing behavior.440AliasResult LocalAliasAnalysis::alias(Value lhs, Value rhs) {441 LDBG() << "alias: " << lhs << " vs " << rhs;442 443 if (lhs == rhs) {444 LDBG() << " Same value, must alias";445 return AliasResult::MustAlias;446 }447 448 // Get the underlying values being addressed.449 SmallVector<Value, 8> lhsValues, rhsValues;450 collectUnderlyingAddressValues(lhs, lhsValues);451 collectUnderlyingAddressValues(rhs, rhsValues);452 453 LDBG() << " lhs underlying values: " << lhsValues.size();454 LDBG() << " rhs underlying values: " << rhsValues.size();455 456 // If we failed to collect for either of the values somehow, conservatively457 // assume they may alias.458 if (lhsValues.empty() || rhsValues.empty()) {459 LDBG() << " Failed to collect underlying values, may alias";460 return AliasResult::MayAlias;461 }462 463 // Check the alias results against each of the underlying values.464 std::optional<AliasResult> result;465 for (Value lhsVal : lhsValues) {466 for (Value rhsVal : rhsValues) {467 LDBG() << " Checking underlying values: " << lhsVal << " vs " << rhsVal;468 AliasResult nextResult = aliasImpl(lhsVal, rhsVal);469 LDBG() << " Result: "470 << (nextResult == AliasResult::MustAlias ? "MustAlias"471 : nextResult == AliasResult::NoAlias ? "NoAlias"472 : "MayAlias");473 result = result ? result->merge(nextResult) : nextResult;474 }475 }476 477 // We should always have a valid result here.478 LDBG() << " Final result: "479 << (result->isMust() ? "MustAlias"480 : result->isNo() ? "NoAlias"481 : "MayAlias");482 return *result;483}484 485//===----------------------------------------------------------------------===//486// LocalAliasAnalysis: getModRef487//===----------------------------------------------------------------------===//488 489ModRefResult LocalAliasAnalysis::getModRef(Operation *op, Value location) {490 LDBG() << "getModRef: " << OpWithFlags(op, OpPrintingFlags().skipRegions())491 << " on location " << location;492 493 // Check to see if this operation relies on nested side effects.494 if (op->hasTrait<OpTrait::HasRecursiveMemoryEffects>()) {495 LDBG() << " Operation has recursive memory effects, returning ModAndRef";496 // TODO: To check recursive operations we need to check all of the nested497 // operations, which can result in a quadratic number of queries. We should498 // introduce some caching of some kind to help alleviate this, especially as499 // this caching could be used in other areas of the codebase (e.g. when500 // checking `wouldOpBeTriviallyDead`).501 return ModRefResult::getModAndRef();502 }503 504 // Otherwise, check to see if this operation has a memory effect interface.505 MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);506 if (!interface) {507 LDBG() << " No memory effect interface, returning ModAndRef";508 return ModRefResult::getModAndRef();509 }510 511 // Build a ModRefResult by merging the behavior of the effects of this512 // operation.513 SmallVector<MemoryEffects::EffectInstance> effects;514 interface.getEffects(effects);515 LDBG() << " Found " << effects.size() << " memory effects";516 517 ModRefResult result = ModRefResult::getNoModRef();518 for (const MemoryEffects::EffectInstance &effect : effects) {519 if (isa<MemoryEffects::Allocate, MemoryEffects::Free>(effect.getEffect())) {520 LDBG() << " Skipping alloc/free effect";521 continue;522 }523 524 // Check for an alias between the effect and our memory location.525 // TODO: Add support for checking an alias with a symbol reference.526 AliasResult aliasResult = AliasResult::MayAlias;527 if (Value effectValue = effect.getValue()) {528 LDBG() << " Checking alias between effect value " << effectValue529 << " and location " << location;530 aliasResult = alias(effectValue, location);531 LDBG() << " Alias result: "532 << (aliasResult.isMust() ? "MustAlias"533 : aliasResult.isNo() ? "NoAlias"534 : "MayAlias");535 } else {536 LDBG() << " No effect value, assuming MayAlias";537 }538 539 // If we don't alias, ignore this effect.540 if (aliasResult.isNo()) {541 LDBG() << " No alias, ignoring effect";542 continue;543 }544 545 // Merge in the corresponding mod or ref for this effect.546 if (isa<MemoryEffects::Read>(effect.getEffect())) {547 LDBG() << " Adding Ref to result";548 result = result.merge(ModRefResult::getRef());549 } else {550 assert(isa<MemoryEffects::Write>(effect.getEffect()));551 LDBG() << " Adding Mod to result";552 result = result.merge(ModRefResult::getMod());553 }554 if (result.isModAndRef()) {555 LDBG() << " Result is now ModAndRef, breaking";556 break;557 }558 }559 560 LDBG() << " Final ModRef result: "561 << (result.isModAndRef() ? "ModAndRef"562 : result.isMod() ? "Mod"563 : result.isRef() ? "Ref"564 : "NoModRef");565 return result;566}567