MLIR  20.0.0git
BufferViewFlowAnalysis.h
Go to the documentation of this file.
1 //===- BufferViewFlowAnalysis.h - Buffer dependency 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 
9 #ifndef MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H
10 #define MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H
11 
12 #include "mlir/IR/Operation.h"
13 #include "llvm/ADT/SmallPtrSet.h"
14 
15 namespace mlir {
16 
17 /// A straight-forward alias analysis which ensures that all dependencies of all
18 /// values will be determined. This is a requirement for the BufferPlacement
19 /// class since you need to determine safe positions to place alloc and
20 /// deallocs. This alias analysis only finds aliases that might have been
21 /// created on top of the specified view. To find all aliases, resolve the
22 /// intial alloc/argument value.
24 public:
27 
28  /// Constructs a new alias analysis using the op provided.
30 
31  /// Find all immediate dependencies this value could potentially have.
32  ValueMapT::const_iterator find(Value value) const {
33  return dependencies.find(value);
34  }
35 
36  /// Returns the begin iterator to iterate over all dependencies.
37  ValueMapT::const_iterator begin() const { return dependencies.begin(); }
38 
39  /// Returns the end iterator that can be used in combination with find.
40  ValueMapT::const_iterator end() const { return dependencies.end(); }
41 
42  /// Find all immediate and indirect views upon this value. This will find all
43  /// dependencies on this value that can potentially be later in the execution
44  /// of the program, but will not return values that this alias might have been
45  /// created from (such as if the value is created by a subview, this will not
46  /// return the parent view if there is no cyclic behavior). Note that the
47  /// resulting set will also contain the value provided as it is an alias of
48  /// itself.
49  ///
50  /// A = *
51  /// B = subview(A)
52  /// C = B
53  ///
54  /// Results in resolve(B) returning {B, C}
55  ValueSetT resolve(Value value) const;
56  ValueSetT resolveReverse(Value value) const;
57 
58  /// Removes the given values from all alias sets.
59  void remove(const SetVector<Value> &aliasValues);
60 
61  /// Replaces all occurrences of 'from' in the internal datastructures with
62  /// 'to'. This is useful when the defining operation of a value has to be
63  /// re-built because additional results have to be added or the types of
64  /// results have to be changed.
65  void rename(Value from, Value to);
66 
67  /// Returns "true" if the given value may be a terminal.
68  bool mayBeTerminalBuffer(Value value) const;
69 
70 private:
71  /// This function constructs a mapping from values to its immediate
72  /// dependencies.
73  void build(Operation *op);
74 
75  /// Maps values to all immediate dependencies this value can have.
76  ValueMapT dependencies;
77  ValueMapT reverseDependencies;
78 
79  /// A set of all SSA values that may be terminal buffers.
80  DenseSet<Value> terminals;
81 };
82 
83 /// An is-same-buffer analysis that checks if two SSA values belong to the same
84 /// buffer allocation or not.
86 public:
88 
89  /// Return "true" if `v1` and `v2` originate from the same buffer allocation.
90  /// Return "false" if `v1` and `v2` originate from different allocations.
91  /// Return "nullopt" if we do not know for sure.
92  ///
93  /// Example 1: isSameAllocation(%0, %1) == true
94  /// ```
95  /// %0 = memref.alloc()
96  /// %1 = memref.subview %0
97  /// ```
98  ///
99  /// Example 2: isSameAllocation(%0, %1) == false
100  /// ```
101  /// %0 = memref.alloc()
102  /// %1 = memref.alloc()
103  /// ```
104  ///
105  /// Example 3: isSameAllocation(%0, %2) == nullopt
106  /// ```
107  /// %0 = memref.alloc()
108  /// %1 = memref.alloc()
109  /// %2 = arith.select %c, %0, %1
110  /// ```
111  std::optional<bool> isSameAllocation(Value v1, Value v2);
112 
113 private:
114  BufferViewFlowAnalysis analysis;
115 };
116 
117 } // namespace mlir
118 
119 #endif // MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_BUFFERVIEWFLOWANALYSIS_H
An is-same-buffer analysis that checks if two SSA values belong to the same buffer allocation or not.
std::optional< bool > isSameAllocation(Value v1, Value v2)
Return "true" if v1 and v2 originate from the same buffer allocation.
A straight-forward alias analysis which ensures that all dependencies of all values will be determine...
ValueMapT::const_iterator end() const
Returns the end iterator that can be used in combination with find.
SmallPtrSet< Value, 16 > ValueSetT
BufferViewFlowAnalysis(Operation *op)
Constructs a new alias analysis using the op provided.
ValueMapT::const_iterator begin() const
Returns the begin iterator to iterate over all dependencies.
void remove(const SetVector< Value > &aliasValues)
Removes the given values from all alias sets.
ValueSetT resolve(Value value) const
Find all immediate and indirect views upon this value.
llvm::DenseMap< Value, ValueSetT > ValueMapT
void rename(Value from, Value to)
Replaces all occurrences of 'from' in the internal datastructures with 'to'.
bool mayBeTerminalBuffer(Value value) const
Returns "true" if the given value may be a terminal.
ValueSetT resolveReverse(Value value) const
ValueMapT::const_iterator find(Value value) const
Find all immediate dependencies this value could potentially have.
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Include the generated interface declarations.