MLIR  22.0.0git
LocalAliasAnalysis.cpp
Go to the documentation of this file.
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 
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/IR/ValueRange.h"
24 #include "mlir/Support/LLVM.h"
25 #include "llvm/Support/Casting.h"
26 #include <cassert>
27 #include <optional>
28 #include <utility>
29 
30 using namespace mlir;
31 
32 //===----------------------------------------------------------------------===//
33 // Underlying Address Computation
34 //===----------------------------------------------------------------------===//
35 
36 /// The maximum depth that will be searched when trying to find an underlying
37 /// value.
38 static constexpr unsigned maxUnderlyingValueSearchDepth = 10;
39 
40 /// Given a value, collect all of the underlying values being addressed.
41 static void collectUnderlyingAddressValues(Value value, unsigned maxDepth,
42  DenseSet<Value> &visited,
43  SmallVectorImpl<Value> &output);
44 
45 /// Given a successor (`region`) of a RegionBranchOpInterface, collect all of
46 /// the underlying values being addressed by one of the successor inputs. If the
47 /// provided `region` is null, as per `RegionBranchOpInterface` this represents
48 /// the parent operation.
49 static void collectUnderlyingAddressValues(RegionBranchOpInterface branch,
50  Region *region, Value inputValue,
51  unsigned inputIndex,
52  unsigned maxDepth,
53  DenseSet<Value> &visited,
54  SmallVectorImpl<Value> &output) {
55  // Given the index of a region of the branch (`predIndex`), or std::nullopt to
56  // represent the parent operation, try to return the index into the outputs of
57  // this region predecessor that correspond to the input values of `region`. If
58  // an index could not be found, std::nullopt is returned instead.
59  auto getOperandIndexIfPred =
60  [&](RegionBranchPoint pred) -> std::optional<unsigned> {
62  branch.getSuccessorRegions(pred, successors);
63  for (RegionSuccessor &successor : successors) {
64  if (successor.getSuccessor() != region)
65  continue;
66  // Check that the successor inputs map to the given input value.
67  ValueRange inputs = successor.getSuccessorInputs();
68  if (inputs.empty()) {
69  output.push_back(inputValue);
70  break;
71  }
72  unsigned firstInputIndex, lastInputIndex;
73  if (region) {
74  firstInputIndex = cast<BlockArgument>(inputs[0]).getArgNumber();
75  lastInputIndex = cast<BlockArgument>(inputs.back()).getArgNumber();
76  } else {
77  firstInputIndex = cast<OpResult>(inputs[0]).getResultNumber();
78  lastInputIndex = cast<OpResult>(inputs.back()).getResultNumber();
79  }
80  if (firstInputIndex > inputIndex || lastInputIndex < inputIndex) {
81  output.push_back(inputValue);
82  break;
83  }
84  return inputIndex - firstInputIndex;
85  }
86  return std::nullopt;
87  };
88 
89  // Check branches from the parent operation.
90  auto branchPoint = RegionBranchPoint::parent();
91  if (region)
92  branchPoint = region;
93 
94  if (std::optional<unsigned> operandIndex =
95  getOperandIndexIfPred(/*predIndex=*/RegionBranchPoint::parent())) {
97  branch.getEntrySuccessorOperands(branchPoint)[*operandIndex], maxDepth,
98  visited, output);
99  }
100  // Check branches from each child region.
101  Operation *op = branch.getOperation();
102  for (Region &region : op->getRegions()) {
103  if (std::optional<unsigned> operandIndex = getOperandIndexIfPred(region)) {
104  for (Block &block : region) {
105  // Try to determine possible region-branch successor operands for the
106  // current region.
107  if (auto term = dyn_cast<RegionBranchTerminatorOpInterface>(
108  block.getTerminator())) {
110  term.getSuccessorOperands(branchPoint)[*operandIndex], maxDepth,
111  visited, output);
112  } else if (block.getNumSuccessors()) {
113  // Otherwise, if this terminator may exit the region we can't make
114  // any assumptions about which values get passed.
115  output.push_back(inputValue);
116  return;
117  }
118  }
119  }
120  }
121 }
122 
123 /// Given a result, collect all of the underlying values being addressed.
124 static void collectUnderlyingAddressValues(OpResult result, unsigned maxDepth,
125  DenseSet<Value> &visited,
126  SmallVectorImpl<Value> &output) {
127  Operation *op = result.getOwner();
128 
129  // If this is a view, unwrap to the source.
130  if (ViewLikeOpInterface view = dyn_cast<ViewLikeOpInterface>(op)) {
131  if (result == view.getViewDest()) {
132  return collectUnderlyingAddressValues(view.getViewSource(), maxDepth,
133  visited, output);
134  }
135  }
136  // Check to see if we can reason about the control flow of this op.
137  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
138  return collectUnderlyingAddressValues(branch, /*region=*/nullptr, result,
139  result.getResultNumber(), maxDepth,
140  visited, output);
141  }
142 
143  output.push_back(result);
144 }
145 
146 /// Given a block argument, collect all of the underlying values being
147 /// addressed.
148 static void collectUnderlyingAddressValues(BlockArgument arg, unsigned maxDepth,
149  DenseSet<Value> &visited,
150  SmallVectorImpl<Value> &output) {
151  Block *block = arg.getOwner();
152  unsigned argNumber = arg.getArgNumber();
153 
154  // Handle the case of a non-entry block.
155  if (!block->isEntryBlock()) {
156  for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
157  auto branch = dyn_cast<BranchOpInterface>((*it)->getTerminator());
158  if (!branch) {
159  // We can't analyze the control flow, so bail out early.
160  output.push_back(arg);
161  return;
162  }
163 
164  // Try to get the operand passed for this argument.
165  unsigned index = it.getSuccessorIndex();
166  Value operand = branch.getSuccessorOperands(index)[argNumber];
167  if (!operand) {
168  // We can't analyze the control flow, so bail out early.
169  output.push_back(arg);
170  return;
171  }
172  collectUnderlyingAddressValues(operand, maxDepth, visited, output);
173  }
174  return;
175  }
176 
177  // Otherwise, check to see if we can reason about the control flow of this op.
178  Region *region = block->getParent();
179  Operation *op = region->getParentOp();
180  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
181  return collectUnderlyingAddressValues(branch, region, arg, argNumber,
182  maxDepth, visited, output);
183  }
184 
185  // We can't reason about the underlying address of this argument.
186  output.push_back(arg);
187 }
188 
189 /// Given a value, collect all of the underlying values being addressed.
190 static void collectUnderlyingAddressValues(Value value, unsigned maxDepth,
191  DenseSet<Value> &visited,
192  SmallVectorImpl<Value> &output) {
193  // Check that we don't infinitely recurse.
194  if (!visited.insert(value).second)
195  return;
196  if (maxDepth == 0) {
197  output.push_back(value);
198  return;
199  }
200  --maxDepth;
201 
202  if (BlockArgument arg = dyn_cast<BlockArgument>(value))
203  return collectUnderlyingAddressValues(arg, maxDepth, visited, output);
204  collectUnderlyingAddressValues(cast<OpResult>(value), maxDepth, visited,
205  output);
206 }
207 
208 /// Given a value, collect all of the underlying values being addressed.
210  SmallVectorImpl<Value> &output) {
211  DenseSet<Value> visited;
213  output);
214 }
215 
216 //===----------------------------------------------------------------------===//
217 // LocalAliasAnalysis: alias
218 //===----------------------------------------------------------------------===//
219 
220 /// Given a value, try to get an allocation effect attached to it. If
221 /// successful, `allocEffect` is populated with the effect. If an effect was
222 /// found, `allocScopeOp` is also specified if a parent operation of `value`
223 /// could be identified that bounds the scope of the allocated value; i.e. if
224 /// non-null it specifies the parent operation that the allocation does not
225 /// escape. If no scope is found, `allocScopeOp` is set to nullptr.
226 static LogicalResult
228  std::optional<MemoryEffects::EffectInstance> &effect,
229  Operation *&allocScopeOp) {
230  // Try to get a memory effect interface for the parent operation.
231  Operation *op;
232  if (BlockArgument arg = dyn_cast<BlockArgument>(value))
233  op = arg.getOwner()->getParentOp();
234  else
235  op = cast<OpResult>(value).getOwner();
236  MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);
237  if (!interface)
238  return failure();
239 
240  // Try to find an allocation effect on the resource.
241  if (!(effect = interface.getEffectOnValue<MemoryEffects::Allocate>(value)))
242  return failure();
243 
244  // If we found an allocation effect, try to find a scope for the allocation.
245  // If the resource of this allocation is automatically scoped, find the parent
246  // operation that bounds the allocation scope.
247  if (llvm::isa<SideEffects::AutomaticAllocationScopeResource>(
248  effect->getResource())) {
250  return success();
251  }
252 
253  // TODO: Here we could look at the users to see if the resource is either
254  // freed on all paths within the region, or is just not captured by anything.
255  // For now assume allocation scope to the function scope (we don't care if
256  // pointer escape outside function).
257  allocScopeOp = op->getParentOfType<FunctionOpInterface>();
258  return success();
259 }
260 
261 /// Given the two values, return their aliasing behavior.
263  if (lhs == rhs)
264  return AliasResult::MustAlias;
265  Operation *lhsAllocScope = nullptr, *rhsAllocScope = nullptr;
266  std::optional<MemoryEffects::EffectInstance> lhsAlloc, rhsAlloc;
267 
268  // Handle the case where lhs is a constant.
269  Attribute lhsAttr, rhsAttr;
270  if (matchPattern(lhs, m_Constant(&lhsAttr))) {
271  // TODO: This is overly conservative. Two matching constants don't
272  // necessarily map to the same address. For example, if the two values
273  // correspond to different symbols that both represent a definition.
274  if (matchPattern(rhs, m_Constant(&rhsAttr)))
275  return AliasResult::MayAlias;
276 
277  // Try to find an alloc effect on rhs. If an effect was found we can't
278  // alias, otherwise we might.
279  return succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope))
282  }
283  // Handle the case where rhs is a constant.
284  if (matchPattern(rhs, m_Constant(&rhsAttr))) {
285  // Try to find an alloc effect on lhs. If an effect was found we can't
286  // alias, otherwise we might.
287  return succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope))
290  }
291 
292  // Otherwise, neither of the values are constant so check to see if either has
293  // an allocation effect.
294  bool lhsHasAlloc = succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope));
295  bool rhsHasAlloc = succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope));
296  if (lhsHasAlloc == rhsHasAlloc) {
297  // If both values have an allocation effect we know they don't alias, and if
298  // neither have an effect we can't make an assumptions.
299  return lhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias;
300  }
301 
302  // When we reach this point we have one value with a known allocation effect,
303  // and one without. Move the one with the effect to the lhs to make the next
304  // checks simpler.
305  if (rhsHasAlloc) {
306  std::swap(lhs, rhs);
307  lhsAlloc = rhsAlloc;
308  lhsAllocScope = rhsAllocScope;
309  }
310 
311  // If the effect has a scoped allocation region, check to see if the
312  // non-effect value is defined above that scope.
313  if (lhsAllocScope) {
314  // If the parent operation of rhs is an ancestor of the allocation scope, or
315  // if rhs is an entry block argument of the allocation scope we know the two
316  // values can't alias.
317  Operation *rhsParentOp = rhs.getParentRegion()->getParentOp();
318  if (rhsParentOp->isProperAncestor(lhsAllocScope))
319  return AliasResult::NoAlias;
320  if (rhsParentOp == lhsAllocScope) {
321  BlockArgument rhsArg = dyn_cast<BlockArgument>(rhs);
322  if (rhsArg && rhs.getParentBlock()->isEntryBlock())
323  return AliasResult::NoAlias;
324  }
325  }
326 
327  // If we couldn't reason about the relationship between the two values,
328  // conservatively assume they might alias.
329  return AliasResult::MayAlias;
330 }
331 
332 /// Given the two values, return their aliasing behavior.
334  if (lhs == rhs)
335  return AliasResult::MustAlias;
336 
337  // Get the underlying values being addressed.
338  SmallVector<Value, 8> lhsValues, rhsValues;
339  collectUnderlyingAddressValues(lhs, lhsValues);
340  collectUnderlyingAddressValues(rhs, rhsValues);
341 
342  // If we failed to collect for either of the values somehow, conservatively
343  // assume they may alias.
344  if (lhsValues.empty() || rhsValues.empty())
345  return AliasResult::MayAlias;
346 
347  // Check the alias results against each of the underlying values.
348  std::optional<AliasResult> result;
349  for (Value lhsVal : lhsValues) {
350  for (Value rhsVal : rhsValues) {
351  AliasResult nextResult = aliasImpl(lhsVal, rhsVal);
352  result = result ? result->merge(nextResult) : nextResult;
353  }
354  }
355 
356  // We should always have a valid result here.
357  return *result;
358 }
359 
360 //===----------------------------------------------------------------------===//
361 // LocalAliasAnalysis: getModRef
362 //===----------------------------------------------------------------------===//
363 
365  // Check to see if this operation relies on nested side effects.
367  // TODO: To check recursive operations we need to check all of the nested
368  // operations, which can result in a quadratic number of queries. We should
369  // introduce some caching of some kind to help alleviate this, especially as
370  // this caching could be used in other areas of the codebase (e.g. when
371  // checking `wouldOpBeTriviallyDead`).
373  }
374 
375  // Otherwise, check to see if this operation has a memory effect interface.
376  MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);
377  if (!interface)
379 
380  // Build a ModRefResult by merging the behavior of the effects of this
381  // operation.
383  interface.getEffects(effects);
384 
386  for (const MemoryEffects::EffectInstance &effect : effects) {
387  if (isa<MemoryEffects::Allocate, MemoryEffects::Free>(effect.getEffect()))
388  continue;
389 
390  // Check for an alias between the effect and our memory location.
391  // TODO: Add support for checking an alias with a symbol reference.
392  AliasResult aliasResult = AliasResult::MayAlias;
393  if (Value effectValue = effect.getValue())
394  aliasResult = alias(effectValue, location);
395 
396  // If we don't alias, ignore this effect.
397  if (aliasResult.isNo())
398  continue;
399 
400  // Merge in the corresponding mod or ref for this effect.
401  if (isa<MemoryEffects::Read>(effect.getEffect())) {
402  result = result.merge(ModRefResult::getRef());
403  } else {
404  assert(isa<MemoryEffects::Write>(effect.getEffect()));
405  result = result.merge(ModRefResult::getMod());
406  }
407  if (result.isModAndRef())
408  break;
409  }
410  return result;
411 }
static LogicalResult getAllocEffectFor(Value value, std::optional< MemoryEffects::EffectInstance > &effect, Operation *&allocScopeOp)
Given a value, try to get an allocation effect attached to it.
static void collectUnderlyingAddressValues(Value value, unsigned maxDepth, DenseSet< Value > &visited, SmallVectorImpl< Value > &output)
Given a value, collect all of the underlying values being addressed.
static constexpr unsigned maxUnderlyingValueSearchDepth
The maximum depth that will be searched when trying to find an underlying value.
The possible results of an alias query.
Definition: AliasAnalysis.h:26
bool isNo() const
Returns if this result indicates no possibility of aliasing.
Definition: AliasAnalysis.h:59
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:41
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:37
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:34
Attributes are known-constant values of operations.
Definition: Attributes.h:25
This class represents an argument of a Block.
Definition: Value.h:309
Block * getOwner() const
Returns the block that owns this argument.
Definition: Value.h:318
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:321
Block represents an ordered list of Operations.
Definition: Block.h:33
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:27
pred_iterator pred_begin()
Definition: Block.h:236
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Definition: Block.cpp:36
pred_iterator pred_end()
Definition: Block.h:239
ModRefResult getModRef(Operation *op, Value location)
Return the modify-reference behavior of op on location.
virtual AliasResult aliasImpl(Value lhs, Value rhs)
Given the two values, return their aliasing behavior.
AliasResult alias(Value lhs, Value rhs)
Given two values, return their aliasing behavior.
The possible results of whether a memory access modifies or references a memory location.
Definition: AliasAnalysis.h:90
bool isModAndRef() const
Returns if this result modifies and references memory.
ModRefResult merge(const ModRefResult &other)
Merge this ModRef result with other and return the result.
static ModRefResult getRef()
Return a new result that indicates that the memory access may reference the value stored in memory.
static ModRefResult getNoModRef()
Return a new result that indicates that the memory access neither references nor modifies the value s...
static ModRefResult getModAndRef()
Return a new result that indicates that the memory access may reference and may modify the value stor...
static ModRefResult getMod()
Return a new result that indicates that the memory access may modify the value stored in memory.
This is a value defined by a result of an operation.
Definition: Value.h:447
Operation * getOwner() const
Returns the operation that owns this result.
Definition: Value.h:456
unsigned getResultNumber() const
Returns the number of this result.
Definition: Value.h:459
A trait of region holding operations that define a new scope for automatic allocations,...
This trait indicates that the memory effects of an operation includes the effects of operations neste...
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:749
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:234
OpTy getParentOfType()
Return the closest surrounding parent operation that is of type 'OpTy'.
Definition: Operation.h:238
Operation * getParentWithTrait()
Returns the closest surrounding parent operation with trait Trait.
Definition: Operation.h:248
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
Definition: Operation.cpp:218
This class represents a point being branched from in the methods of the RegionBranchOpInterface.
static constexpr RegionBranchPoint parent()
Returns an instance of RegionBranchPoint representing the parent operation.
This class represents a successor of a region.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
Operation * getParentOp()
Return the parent operation this region is attached to.
Definition: Region.h:200
This class represents a specific instance of an effect.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Block * getParentBlock()
Return the Block in which this Value is defined.
Definition: Value.cpp:46
Region * getParentRegion()
Return the Region in which this Value is defined.
Definition: Value.cpp:39
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition: Matchers.h:490
detail::constant_op_matcher m_Constant()
Matches a constant foldable operation.
Definition: Matchers.h:369
The following effect indicates that the operation allocates from some resource.