MLIR  14.0.0git
BufferViewFlowAnalysis.cpp
Go to the documentation of this file.
1 //======- BufferViewFlowAnalysis.cpp - Buffer alias analysis -*- C++ -*-======//
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 
13 #include "llvm/ADT/SetOperations.h"
14 
15 using namespace mlir;
16 
17 /// Constructs a new alias analysis using the op provided.
19 
20 /// Find all immediate and indirect dependent buffers this value could
21 /// potentially have. Note that the resulting set will also contain the value
22 /// provided as it is a dependent alias of itself.
25  ValueSetT result;
27  queue.push_back(rootValue);
28  while (!queue.empty()) {
29  Value currentValue = queue.pop_back_val();
30  if (result.insert(currentValue).second) {
31  auto it = dependencies.find(currentValue);
32  if (it != dependencies.end()) {
33  for (Value aliasValue : it->second)
34  queue.push_back(aliasValue);
35  }
36  }
37  }
38  return result;
39 }
40 
41 /// Removes the given values from all alias sets.
43  for (auto &entry : dependencies)
44  llvm::set_subtract(entry.second, aliasValues);
45 }
46 
47 /// This function constructs a mapping from values to its immediate
48 /// dependencies. It iterates over all blocks, gets their predecessors,
49 /// determines the values that will be passed to the corresponding block
50 /// arguments and inserts them into the underlying map. Furthermore, it wires
51 /// successor regions and branch-like return operations from nested regions.
52 void BufferViewFlowAnalysis::build(Operation *op) {
53  // Registers all dependencies of the given values.
54  auto registerDependencies = [&](auto values, auto dependencies) {
55  for (auto entry : llvm::zip(values, dependencies))
56  this->dependencies[std::get<0>(entry)].insert(std::get<1>(entry));
57  };
58 
59  // Add additional dependencies created by view changes to the alias list.
60  op->walk([&](ViewLikeOpInterface viewInterface) {
61  dependencies[viewInterface.getViewSource()].insert(
62  viewInterface->getResult(0));
63  });
64 
65  // Query all branch interfaces to link block argument dependencies.
66  op->walk([&](BranchOpInterface branchInterface) {
67  Block *parentBlock = branchInterface->getBlock();
68  for (auto it = parentBlock->succ_begin(), e = parentBlock->succ_end();
69  it != e; ++it) {
70  // Query the branch op interface to get the successor operands.
71  auto successorOperands =
72  branchInterface.getSuccessorOperands(it.getIndex());
73  if (!successorOperands.hasValue())
74  continue;
75  // Build the actual mapping of values to their immediate dependencies.
76  registerDependencies(successorOperands.getValue(), (*it)->getArguments());
77  }
78  });
79 
80  // Query the RegionBranchOpInterface to find potential successor regions.
81  op->walk([&](RegionBranchOpInterface regionInterface) {
82  // Extract all entry regions and wire all initial entry successor inputs.
83  SmallVector<RegionSuccessor, 2> entrySuccessors;
84  regionInterface.getSuccessorRegions(/*index=*/llvm::None, entrySuccessors);
85  for (RegionSuccessor &entrySuccessor : entrySuccessors) {
86  // Wire the entry region's successor arguments with the initial
87  // successor inputs.
88  assert(entrySuccessor.getSuccessor() &&
89  "Invalid entry region without an attached successor region");
90  registerDependencies(
91  regionInterface.getSuccessorEntryOperands(
92  entrySuccessor.getSuccessor()->getRegionNumber()),
93  entrySuccessor.getSuccessorInputs());
94  }
95 
96  // Wire flow between regions and from region exits.
97  for (Region &region : regionInterface->getRegions()) {
98  // Iterate over all successor region entries that are reachable from the
99  // current region.
100  SmallVector<RegionSuccessor, 2> successorRegions;
101  regionInterface.getSuccessorRegions(region.getRegionNumber(),
102  successorRegions);
103  for (RegionSuccessor &successorRegion : successorRegions) {
104  // Determine the current region index (if any).
105  Optional<unsigned> regionIndex;
106  Region *regionSuccessor = successorRegion.getSuccessor();
107  if (regionSuccessor)
108  regionIndex = regionSuccessor->getRegionNumber();
109  // Iterate over all immediate terminator operations and wire the
110  // successor inputs with the successor operands of each terminator.
111  for (Block &block : region) {
112  auto successorOperands = getRegionBranchSuccessorOperands(
113  block.getTerminator(), regionIndex);
114  if (successorOperands) {
115  registerDependencies(*successorOperands,
116  successorRegion.getSuccessorInputs());
117  }
118  }
119  }
120  }
121  });
122 }
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
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
Block represents an ordered list of Operations.
Definition: Block.h:29
ValueSetT resolve(Value value) const
Find all immediate and indirect views upon this value.
std::enable_if< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT >::type walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one)...
Definition: Operation.h:515
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
BufferViewFlowAnalysis(Operation *op)
Constructs a new alias analysis using the op provided.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:84
This class represents a successor of a region.
void remove(const SmallPtrSetImpl< Value > &aliasValues)
Removes the given values from all alias sets.
succ_iterator succ_end()
Definition: Block.h:254
succ_iterator succ_begin()
Definition: Block.h:253