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