MLIR  16.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 std::nullopt 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, std::nullopt 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 std::nullopt;
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  }
82  if (Optional<unsigned> operandIndex =
83  getOperandIndexIfPred(/*predIndex=*/std::nullopt)) {
85  branch.getSuccessorEntryOperands(regionIndex)[*operandIndex], maxDepth,
86  visited, output);
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  Value operand = branch.getSuccessorOperands(index)[argNumber];
153  if (!operand) {
154  // We can't analyze the control flow, so bail out early.
155  output.push_back(arg);
156  return;
157  }
158  collectUnderlyingAddressValues(operand, maxDepth, visited, output);
159  }
160  return;
161  }
162 
163  // Otherwise, check to see if we can reason about the control flow of this op.
164  Region *region = block->getParent();
165  Operation *op = region->getParentOp();
166  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
167  return collectUnderlyingAddressValues(branch, region, arg, argNumber,
168  maxDepth, visited, output);
169  }
170 
171  // We can't reason about the underlying address of this argument.
172  output.push_back(arg);
173 }
174 
175 /// Given a value, collect all of the underlying values being addressed.
176 static void collectUnderlyingAddressValues(Value value, unsigned maxDepth,
177  DenseSet<Value> &visited,
178  SmallVectorImpl<Value> &output) {
179  // Check that we don't infinitely recurse.
180  if (!visited.insert(value).second)
181  return;
182  if (maxDepth == 0) {
183  output.push_back(value);
184  return;
185  }
186  --maxDepth;
187 
188  if (BlockArgument arg = value.dyn_cast<BlockArgument>())
189  return collectUnderlyingAddressValues(arg, maxDepth, visited, output);
190  collectUnderlyingAddressValues(value.cast<OpResult>(), maxDepth, visited,
191  output);
192 }
193 
194 /// Given a value, collect all of the underlying values being addressed.
196  SmallVectorImpl<Value> &output) {
197  DenseSet<Value> visited;
199  output);
200 }
201 
202 //===----------------------------------------------------------------------===//
203 // LocalAliasAnalysis: alias
204 //===----------------------------------------------------------------------===//
205 
206 /// Given a value, try to get an allocation effect attached to it. If
207 /// successful, `allocEffect` is populated with the effect. If an effect was
208 /// found, `allocScopeOp` is also specified if a parent operation of `value`
209 /// could be identified that bounds the scope of the allocated value; i.e. if
210 /// non-null it specifies the parent operation that the allocation does not
211 /// escape. If no scope is found, `allocScopeOp` is set to nullptr.
212 static LogicalResult
214  Operation *&allocScopeOp) {
215  // Try to get a memory effect interface for the parent operation.
216  Operation *op;
217  if (BlockArgument arg = value.dyn_cast<BlockArgument>())
218  op = arg.getOwner()->getParentOp();
219  else
220  op = value.cast<OpResult>().getOwner();
221  MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);
222  if (!interface)
223  return failure();
224 
225  // Try to find an allocation effect on the resource.
226  if (!(effect = interface.getEffectOnValue<MemoryEffects::Allocate>(value)))
227  return failure();
228 
229  // If we found an allocation effect, try to find a scope for the allocation.
230  // If the resource of this allocation is automatically scoped, find the parent
231  // operation that bounds the allocation scope.
232  if (llvm::isa<SideEffects::AutomaticAllocationScopeResource>(
233  effect->getResource())) {
235  return success();
236  }
237 
238  // TODO: Here we could look at the users to see if the resource is either
239  // freed on all paths within the region, or is just not captured by anything.
240  // For now assume allocation scope to the function scope (we don't care if
241  // pointer escape outside function).
242  allocScopeOp = op->getParentOfType<FunctionOpInterface>();
243  return success();
244 }
245 
246 /// Given the two values, return their aliasing behavior.
247 static AliasResult aliasImpl(Value lhs, Value rhs) {
248  if (lhs == rhs)
249  return AliasResult::MustAlias;
250  Operation *lhsAllocScope = nullptr, *rhsAllocScope = nullptr;
251  Optional<MemoryEffects::EffectInstance> lhsAlloc, rhsAlloc;
252 
253  // Handle the case where lhs is a constant.
254  Attribute lhsAttr, rhsAttr;
255  if (matchPattern(lhs, m_Constant(&lhsAttr))) {
256  // TODO: This is overly conservative. Two matching constants don't
257  // necessarily map to the same address. For example, if the two values
258  // correspond to different symbols that both represent a definition.
259  if (matchPattern(rhs, m_Constant(&rhsAttr)))
260  return AliasResult::MayAlias;
261 
262  // Try to find an alloc effect on rhs. If an effect was found we can't
263  // alias, otherwise we might.
264  return succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope))
267  }
268  // Handle the case where rhs is a constant.
269  if (matchPattern(rhs, m_Constant(&rhsAttr))) {
270  // Try to find an alloc effect on lhs. If an effect was found we can't
271  // alias, otherwise we might.
272  return succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope))
275  }
276 
277  // Otherwise, neither of the values are constant so check to see if either has
278  // an allocation effect.
279  bool lhsHasAlloc = succeeded(getAllocEffectFor(lhs, lhsAlloc, lhsAllocScope));
280  bool rhsHasAlloc = succeeded(getAllocEffectFor(rhs, rhsAlloc, rhsAllocScope));
281  if (lhsHasAlloc == rhsHasAlloc) {
282  // If both values have an allocation effect we know they don't alias, and if
283  // neither have an effect we can't make an assumptions.
284  return lhsHasAlloc ? AliasResult::NoAlias : AliasResult::MayAlias;
285  }
286 
287  // When we reach this point we have one value with a known allocation effect,
288  // and one without. Move the one with the effect to the lhs to make the next
289  // checks simpler.
290  if (rhsHasAlloc) {
291  std::swap(lhs, rhs);
292  lhsAlloc = rhsAlloc;
293  lhsAllocScope = rhsAllocScope;
294  }
295 
296  // If the effect has a scoped allocation region, check to see if the
297  // non-effect value is defined above that scope.
298  if (lhsAllocScope) {
299  // If the parent operation of rhs is an ancestor of the allocation scope, or
300  // if rhs is an entry block argument of the allocation scope we know the two
301  // values can't alias.
302  Operation *rhsParentOp = rhs.getParentRegion()->getParentOp();
303  if (rhsParentOp->isProperAncestor(lhsAllocScope))
304  return AliasResult::NoAlias;
305  if (rhsParentOp == lhsAllocScope) {
306  BlockArgument rhsArg = rhs.dyn_cast<BlockArgument>();
307  if (rhsArg && rhs.getParentBlock()->isEntryBlock())
308  return AliasResult::NoAlias;
309  }
310  }
311 
312  // If we couldn't reason about the relationship between the two values,
313  // conservatively assume they might alias.
314  return AliasResult::MayAlias;
315 }
316 
317 /// Given the two values, return their aliasing behavior.
319  if (lhs == rhs)
320  return AliasResult::MustAlias;
321 
322  // Get the underlying values being addressed.
323  SmallVector<Value, 8> lhsValues, rhsValues;
324  collectUnderlyingAddressValues(lhs, lhsValues);
325  collectUnderlyingAddressValues(rhs, rhsValues);
326 
327  // If we failed to collect for either of the values somehow, conservatively
328  // assume they may alias.
329  if (lhsValues.empty() || rhsValues.empty())
330  return AliasResult::MayAlias;
331 
332  // Check the alias results against each of the underlying values.
333  Optional<AliasResult> result;
334  for (Value lhsVal : lhsValues) {
335  for (Value rhsVal : rhsValues) {
336  AliasResult nextResult = aliasImpl(lhsVal, rhsVal);
337  result = result ? result->merge(nextResult) : nextResult;
338  }
339  }
340 
341  // We should always have a valid result here.
342  return *result;
343 }
344 
345 //===----------------------------------------------------------------------===//
346 // LocalAliasAnalysis: getModRef
347 //===----------------------------------------------------------------------===//
348 
350  // Check to see if this operation relies on nested side effects.
352  // TODO: To check recursive operations we need to check all of the nested
353  // operations, which can result in a quadratic number of queries. We should
354  // introduce some caching of some kind to help alleviate this, especially as
355  // this caching could be used in other areas of the codebase (e.g. when
356  // checking `wouldOpBeTriviallyDead`).
358  }
359 
360  // Otherwise, check to see if this operation has a memory effect interface.
361  MemoryEffectOpInterface interface = dyn_cast<MemoryEffectOpInterface>(op);
362  if (!interface)
364 
365  // Build a ModRefResult by merging the behavior of the effects of this
366  // operation.
368  interface.getEffects(effects);
369 
371  for (const MemoryEffects::EffectInstance &effect : effects) {
372  if (isa<MemoryEffects::Allocate, MemoryEffects::Free>(effect.getEffect()))
373  continue;
374 
375  // Check for an alias between the effect and our memory location.
376  // TODO: Add support for checking an alias with a symbol reference.
377  AliasResult aliasResult = AliasResult::MayAlias;
378  if (Value effectValue = effect.getValue())
379  aliasResult = alias(effectValue, location);
380 
381  // If we don't alias, ignore this effect.
382  if (aliasResult.isNo())
383  continue;
384 
385  // Merge in the corresponding mod or ref for this effect.
386  if (isa<MemoryEffects::Read>(effect.getEffect())) {
387  result = result.merge(ModRefResult::getRef());
388  } else {
389  assert(isa<MemoryEffects::Write>(effect.getEffect()));
390  result = result.merge(ModRefResult::getMod());
391  }
392  if (result.isModAndRef())
393  break;
394  }
395  return result;
396 }
static constexpr const bool value
static AliasResult aliasImpl(Value lhs, Value rhs)
Given the two values, return their aliasing behavior.
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.
static LogicalResult getAllocEffectFor(Value value, Optional< MemoryEffects::EffectInstance > &effect, Operation *&allocScopeOp)
Given a value, try to get an allocation effect attached to it.
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:296
Block * getOwner() const
Returns the block that owns this argument.
Definition: Value.h:305
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:308
Block represents an ordered list of Operations.
Definition: Block.h:30
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
pred_iterator pred_begin()
Definition: Block.h:219
bool isEntryBlock()
Return if this block is the entry block in the parent region.
Definition: Block.cpp:35
pred_iterator pred_end()
Definition: Block.h:222
ModRefResult getModRef(Operation *op, Value location)
Return the modify-reference behavior of op on location.
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:442
Operation * getOwner() const
Returns the operation that owns this result.
Definition: Value.h:451
unsigned getResultNumber() const
Returns the number of this result.
Definition: Value.h:454
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 a basic unit of execution within MLIR.
Definition: Operation.h:31
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:532
unsigned getNumSuccessors()
Definition: Operation.h:510
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:477
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:165
OpTy getParentOfType()
Return the closest surrounding parent operation that is of type 'OpTy'.
Definition: Operation.h:169
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:490
Operation * getParentWithTrait()
Returns the closest surrounding parent operation with trait Trait.
Definition: Operation.h:179
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
Definition: Operation.cpp:176
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
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
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:349
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
U dyn_cast() const
Definition: Value.h:95
Block * getParentBlock()
Return the Block in which this Value is defined.
Definition: Value.cpp:48
Region * getParentRegion()
Return the Region in which this Value is defined.
Definition: Value.cpp:41
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition: Matchers.h:329
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
Definition: LogicalResult.h:68
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
Optional< OperandRange > getRegionBranchSuccessorOperands(Operation *operation, Optional< unsigned > regionIndex)
Returns the read only operands that are passed to the region with the given regionIndex.
detail::constant_op_matcher m_Constant()
Matches a constant foldable operation.
Definition: Matchers.h:255
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
The following effect indicates that the operation allocates from some resource.