MLIR  19.0.0git
OneShotAnalysis.h
Go to the documentation of this file.
1 //===- OneShotAnalysis.h - One-Shot (Single Pass) 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_ONESHOTANALYSIS_H
10 #define MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_ONESHOTANALYSIS_H
11 
13 #include "llvm/ADT/EquivalenceClasses.h"
14 #include <string>
15 
16 namespace mlir {
17 class DominanceInfo;
18 
19 namespace bufferization {
20 
21 struct OneShotBufferizationOptions;
22 struct BufferizationStatistics;
23 class OneShotAnalysisState;
24 
25 /// Options for analysis-enabled bufferization.
28 
30 
31  /// Specifies whether returning newly allocated memrefs from loops should be
32  /// allowed. Otherwise, a pass failure is triggered.
34 
35  /// Specifies whether the tensor IR should be annotated with alias sets.
36  bool dumpAliasSets = false;
37 
38  /// The heuristic controls the order in which ops are traversed during the
39  /// analysis.
41 
42  /// Specify the functions that should not be analyzed. copyBeforeWrite will be
43  /// set to true when bufferizing them.
45 };
46 
47 /// State for analysis-enabled bufferization. This class keeps track of alias
48 /// sets, equivalence sets, in-place OpOperands and other things.
49 ///
50 /// Note: Modifying the IR generally invalidates the result of the analysis.
51 /// Adding new operations is safe if they are analyzed subsequently.
53 public:
55  const OneShotBufferizationOptions &options);
56 
58 
59  ~OneShotAnalysisState() override = default;
60 
61  static bool classof(const AnalysisState *base) {
62  return base->getType() == TypeID::get<OneShotAnalysisState>();
63  }
64 
65  /// Return a reference to the BufferizationOptions.
67  return static_cast<const OneShotBufferizationOptions &>(
69  }
70 
71  /// Analyze the given op and its nested ops.
72  LogicalResult analyzeOp(Operation *op, const DominanceInfo &domInfo);
73 
74  /// Analyze a single op (without nested ops).
76 
77  /// Apply `fun` to all the members of the equivalence class of `v`.
78  void applyOnEquivalenceClass(Value v, function_ref<void(Value)> fun) const;
79 
80  /// Apply `fun` to all aliases of `v`.
81  void applyOnAliases(Value v, function_ref<void(Value)> fun) const;
82 
83  /// Return true if `v1` and `v2` bufferize to equivalent buffers.
84  bool areEquivalentBufferizedValues(Value v1, Value v2) const override;
85 
86  /// Return true if `v1` and `v2` may bufferize to aliasing buffers.
87  bool areAliasingBufferizedValues(Value v1, Value v2) const override;
88 
89  /// Mark the given OpOperand as in-place and merge the results' and operand's
90  /// aliasing sets.
91  void bufferizeInPlace(OpOperand &operand);
92 
93  /// Mark the given OpOperand as out-of-place.
94  void bufferizeOutOfPlace(OpOperand &operand);
95 
96  /// Add a new entry for `v` in the `aliasInfo` and `equivalentInfo`. In the
97  /// beginning the alias and equivalence sets only contain `v` itself.
99 
100  /// Find all tensor values in the given operation that have undefined contents
101  /// and store them in `undefinedTensorUses`.
103 
104  int64_t getStatNumTensorOutOfPlace() const { return statNumTensorOutOfPlace; }
105  int64_t getStatNumTensorInPlace() const { return statNumTensorInPlace; }
106 
107  /// Return `true` if the given tensor has undefined contents.
108  bool hasUndefinedContents(OpOperand *opOperand) const override;
109 
110  /// Return `true` if the given OpResult has been decided to bufferize inplace.
111  bool isInPlace(OpOperand &opOperand) const override;
112 
113  /// Return true if the buffer of the given tensor value is written to. Must
114  /// not be called for values inside not yet analyzed functions.
115  bool isValueWritten(Value value) const;
116 
117  /// Return true if the buffer of the given tensor value is writable.
118  bool isWritable(Value value) const;
119 
120  /// Find the definitions of the given tensor value or retrieve them from the
121  /// cache.
123 
124  /// Reset cached data structures.
125  void resetCache() override;
126 
127  /// Union the alias sets of `v1` and `v2`.
128  void unionAliasSets(Value v1, Value v2);
129 
130  /// Union the equivalence classes of `v1` and `v2`.
131  void unionEquivalenceClasses(Value v1, Value v2);
132 
133  /// Base class for OneShotAnalysisState extensions that allow
134  /// OneShotAnalysisState to contain user-specified information in the state
135  /// object. Clients are expected to derive this class, add the desired fields,
136  /// and make the derived class compatible with the MLIR TypeID mechanism.
137  ///
138  /// ```mlir
139  /// class MyExtension final : public OneShotAnalysisState::Extension {
140  /// public:
141  /// MyExtension(OneShotAnalysisState &state, int myData)
142  /// : Extension(state) {...}
143  /// private:
144  /// int mySupplementaryData;
145  /// };
146  /// ```
147  ///
148  /// Instances of this and derived classes are not expected to be created by
149  /// the user, instead they are directly constructed within a
150  /// OneShotAnalysisState. A OneShotAnalysisState can only contain one
151  /// extension with the given TypeID. Extensions can be obtained from a
152  /// OneShotAnalysisState instance.
153  ///
154  /// ```mlir
155  /// state.addExtension<MyExtension>(/*myData=*/42);
156  /// MyExtension *ext = state.getExtension<MyExtension>();
157  /// ext->doSomething();
158  /// ```
159  class Extension {
160  // Allow OneShotAnalysisState to allocate Extensions.
161  friend class OneShotAnalysisState;
162 
163  public:
164  /// Base virtual destructor.
165  // Out-of-line definition ensures symbols are emitted in a single object
166  // file.
167  virtual ~Extension();
168 
169  protected:
170  /// Constructs an extension of the given state object.
171  Extension(OneShotAnalysisState &state) : state(state) {}
172 
173  /// Provides read-only access to the parent OneShotAnalysisState object.
174  const OneShotAnalysisState &getAnalysisState() const { return state; }
175 
176  private:
177  /// Back-reference to the state that is being extended.
178  OneShotAnalysisState &state;
179  };
180 
181  /// Adds a new Extension of the type specified as template parameter,
182  /// constructing it with the arguments provided. The extension is owned by the
183  /// OneShotAnalysisState. It is expected that the state does not already have
184  /// an extension of the same type. Extension constructors are expected to take
185  /// a reference to OneShotAnalysisState as first argument, automatically
186  /// supplied by this call.
187  template <typename Ty, typename... Args>
188  Ty &addExtension(Args &&...args) {
189  static_assert(
190  std::is_base_of<Extension, Ty>::value,
191  "only a class derived from OneShotAnalysisState::Extension is allowed");
192  auto ptr = std::make_unique<Ty>(*this, std::forward<Args>(args)...);
193  auto result = extensions.try_emplace(TypeID::get<Ty>(), std::move(ptr));
194  assert(result.second && "extension already added");
195  return *static_cast<Ty *>(result.first->second.get());
196  }
197 
198  /// Returns the extension of the specified type.
199  template <typename Ty>
200  Ty *getExtension() {
201  static_assert(
202  std::is_base_of<Extension, Ty>::value,
203  "only a class derived from OneShotAnalysisState::Extension is allowed");
204  auto iter = extensions.find(TypeID::get<Ty>());
205  if (iter == extensions.end())
206  return nullptr;
207  return static_cast<Ty *>(iter->second.get());
208  }
209 
210  /// Returns the extension of the specified type.
211  template <typename Ty>
212  const Ty *getExtension() const {
213  return const_cast<OneShotAnalysisState *>(this)->getExtension<Ty>();
214  }
215 
216 private:
217  /// llvm::EquivalenceClasses wants comparable elements. This comparator uses
218  /// pointer comparison on the defining op. This is a poor man's comparison
219  /// but it's not like UnionFind needs ordering anyway.
220  struct ValueComparator {
221  bool operator()(const Value &lhs, const Value &rhs) const {
222  return lhs.getImpl() < rhs.getImpl();
223  }
224  };
225 
226  using EquivalenceClassRangeType = llvm::iterator_range<
227  llvm::EquivalenceClasses<Value, ValueComparator>::member_iterator>;
228  /// Check that aliasInfo for `v` exists and return a reference to it.
229  EquivalenceClassRangeType getAliases(Value v) const;
230 
231  /// Cache definitions of tensor values.
232  DenseMap<Value, SetVector<Value>> cachedDefinitions;
233 
234  /// Set of all OpResults that were decided to bufferize in-place.
235  llvm::DenseSet<OpOperand *> inplaceBufferized;
236 
237  /// Auxiliary structure to store all the values a given value may alias with.
238  /// Alias information is "may be" conservative: In the presence of branches, a
239  /// value may alias with one of multiple other values. The concrete aliasing
240  /// value may not even be known at compile time. All such values are
241  /// considered to be aliases.
242  llvm::EquivalenceClasses<Value, ValueComparator> aliasInfo;
243 
244  /// Auxiliary structure to store all the equivalent buffer classes. Equivalent
245  /// buffer information is "must be" conservative: Only if two values are
246  /// guaranteed to be equivalent at runtime, they said to be equivalent. It is
247  /// possible that, in the presence of branches, it cannot be determined
248  /// statically if two values are equivalent. In that case, the values are
249  /// considered to be not equivalent.
250  llvm::EquivalenceClasses<Value, ValueComparator> equivalentInfo;
251 
252  // Bufferization statistics.
253  int64_t statNumTensorOutOfPlace = 0;
254  int64_t statNumTensorInPlace = 0;
255 
256  /// A set of uses of tensors that have undefined contents.
257  DenseSet<OpOperand *> undefinedTensorUses;
258 
259  /// Extensions attached to the state, identified by the TypeID of their type.
260  /// Only one extension of any given type is allowed.
261  DenseMap<TypeID, std::unique_ptr<Extension>> extensions;
262 };
263 
264 /// Analyze `op` and its nested ops. Bufferization decisions are stored in
265 /// `state`.
266 LogicalResult analyzeOp(Operation *op, OneShotAnalysisState &state,
267  BufferizationStatistics *statistics = nullptr);
268 
269 /// Run One-Shot Bufferize on the given op: Analysis + Bufferization
270 LogicalResult
271 runOneShotBufferize(Operation *op, const OneShotBufferizationOptions &options,
272  BufferizationStatistics *statistics = nullptr);
273 
274 } // namespace bufferization
275 } // namespace mlir
276 
278 
279 #endif // MLIR_DIALECT_BUFFERIZATION_TRANSFORMS_ONESHOTANALYSIS_H
static llvm::ManagedStatic< PassManagerOptions > options
#define MLIR_DECLARE_EXPLICIT_TYPE_ID(CLASS_NAME)
Definition: TypeID.h:249
A class for computing basic dominance information.
Definition: Dominance.h:136
This class represents an operand of an operation.
Definition: Value.h:263
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
detail::ValueImpl * getImpl() const
Definition: Value.h:243
AnalysisState provides a variety of helper functions for dealing with tensor values.
const BufferizationOptions & getOptions() const
Return a reference to the BufferizationOptions.
Base class for OneShotAnalysisState extensions that allow OneShotAnalysisState to contain user-specif...
virtual ~Extension()
Base virtual destructor.
const OneShotAnalysisState & getAnalysisState() const
Provides read-only access to the parent OneShotAnalysisState object.
Extension(OneShotAnalysisState &state)
Constructs an extension of the given state object.
State for analysis-enabled bufferization.
void bufferizeOutOfPlace(OpOperand &operand)
Mark the given OpOperand as out-of-place.
bool isWritable(Value value) const
Return true if the buffer of the given tensor value is writable.
const SetVector< Value > & findDefinitionsCached(Value value)
Find the definitions of the given tensor value or retrieve them from the cache.
bool isInPlace(OpOperand &opOperand) const override
Return true if the given OpResult has been decided to bufferize inplace.
LogicalResult analyzeOp(Operation *op, const DominanceInfo &domInfo)
Analyze the given op and its nested ops.
bool isValueWritten(Value value) const
Return true if the buffer of the given tensor value is written to.
const Ty * getExtension() const
Returns the extension of the specified type.
const OneShotBufferizationOptions & getOptions() const
Return a reference to the BufferizationOptions.
Ty & addExtension(Args &&...args)
Adds a new Extension of the type specified as template parameter, constructing it with the arguments ...
void unionEquivalenceClasses(Value v1, Value v2)
Union the equivalence classes of v1 and v2.
OneShotAnalysisState(const OneShotAnalysisState &)=delete
void gatherUndefinedTensorUses(Operation *op)
Find all tensor values in the given operation that have undefined contents and store them in undefine...
void resetCache() override
Reset cached data structures.
LogicalResult analyzeSingleOp(Operation *op, const DominanceInfo &domInfo)
Analyze a single op (without nested ops).
void applyOnEquivalenceClass(Value v, function_ref< void(Value)> fun) const
Apply fun to all the members of the equivalence class of v.
bool hasUndefinedContents(OpOperand *opOperand) const override
Return true if the given tensor has undefined contents.
static bool classof(const AnalysisState *base)
void bufferizeInPlace(OpOperand &operand)
Mark the given OpOperand as in-place and merge the results' and operand's aliasing sets.
void applyOnAliases(Value v, function_ref< void(Value)> fun) const
Apply fun to all aliases of v.
bool areEquivalentBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 bufferize to equivalent buffers.
OneShotAnalysisState(Operation *op, const OneShotBufferizationOptions &options)
bool areAliasingBufferizedValues(Value v1, Value v2) const override
Return true if v1 and v2 may bufferize to aliasing buffers.
void unionAliasSets(Value v1, Value v2)
Union the alias sets of v1 and v2.
Ty * getExtension()
Returns the extension of the specified type.
void createAliasInfoEntry(Value v)
Add a new entry for v in the aliasInfo and equivalentInfo.
LogicalResult runOneShotBufferize(Operation *op, const OneShotBufferizationOptions &options, BufferizationStatistics *statistics=nullptr)
Run One-Shot Bufferize on the given op: Analysis + Bufferization.
LogicalResult analyzeOp(Operation *op, OneShotAnalysisState &state, BufferizationStatistics *statistics=nullptr)
Analyze op and its nested ops.
Include the generated interface declarations.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
Options for BufferizableOpInterface-based bufferization.
Options for analysis-enabled bufferization.
bool dumpAliasSets
Specifies whether the tensor IR should be annotated with alias sets.
bool allowReturnAllocsFromLoops
Specifies whether returning newly allocated memrefs from loops should be allowed.
AnalysisHeuristic analysisHeuristic
The heuristic controls the order in which ops are traversed during the analysis.
llvm::ArrayRef< std::string > noAnalysisFuncFilter
Specify the functions that should not be analyzed.
Compare two SSA values in a deterministic manner.