MLIR  15.0.0git
AliasAnalysis.h
Go to the documentation of this file.
1 //===- AliasAnalysis.h - Alias Analysis in MLIR -----------------*- 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 // This header file defines utilities and analyses for performing alias queries
10 // and related memory queries in MLIR.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_ANALYSIS_ALIASANALYSIS_H_
15 #define MLIR_ANALYSIS_ALIASANALYSIS_H_
16 
17 #include "mlir/IR/Operation.h"
18 
19 namespace mlir {
20 
21 //===----------------------------------------------------------------------===//
22 // AliasResult
23 //===----------------------------------------------------------------------===//
24 
25 /// The possible results of an alias query.
26 class AliasResult {
27 public:
28  enum Kind {
29  /// The two locations do not alias at all.
30  ///
31  /// This value is arranged to convert to false, while all other values
32  /// convert to true. This allows a boolean context to convert the result to
33  /// a binary flag indicating whether there is the possibility of aliasing.
34  NoAlias = 0,
35  /// The two locations may or may not alias. This is the least precise
36  /// result.
38  /// The two locations alias, but only due to a partial overlap.
40  /// The two locations precisely alias each other.
42  };
43 
44  AliasResult(Kind kind) : kind(kind) {}
45  bool operator==(const AliasResult &other) const { return kind == other.kind; }
46  bool operator!=(const AliasResult &other) const { return !(*this == other); }
47 
48  /// Allow conversion to bool to signal if there is an aliasing or not.
49  explicit operator bool() const { return kind != NoAlias; }
50 
51  /// Merge this alias result with `other` and return a new result that
52  /// represents the conservative merge of both results. If the results
53  /// represent a known alias, the stronger alias is chosen (i.e.
54  /// Partial+Must=Must). If the two results are conflicting, MayAlias is
55  /// returned.
56  AliasResult merge(AliasResult other) const;
57 
58  /// Returns if this result is a partial alias.
59  bool isNo() const { return kind == NoAlias; }
60 
61  /// Returns if this result is a may alias.
62  bool isMay() const { return kind == MayAlias; }
63 
64  /// Returns if this result is a must alias.
65  bool isMust() const { return kind == MustAlias; }
66 
67  /// Returns if this result is a partial alias.
68  bool isPartial() const { return kind == PartialAlias; }
69 
70  /// Print this alias result to the provided output stream.
71  void print(raw_ostream &os) const;
72 
73 private:
74  /// The internal kind of the result.
75  Kind kind;
76 };
77 
78 inline raw_ostream &operator<<(raw_ostream &os, const AliasResult &result) {
79  result.print(os);
80  return os;
81 }
82 
83 //===----------------------------------------------------------------------===//
84 // ModRefResult
85 //===----------------------------------------------------------------------===//
86 
87 /// The possible results of whether a memory access modifies or references
88 /// a memory location. The possible results are: no access at all, a
89 /// modification, a reference, or both a modification and a reference.
90 class LLVM_NODISCARD ModRefResult {
91  /// Note: This is a simplified version of the ModRefResult in
92  /// `llvm/Analysis/AliasAnalysis.h`, and namely removes the `Must` concept. If
93  /// this becomes useful/necessary we should add it here.
94  enum class Kind {
95  /// The access neither references nor modifies the value stored in memory.
96  NoModRef = 0,
97  /// The access may reference the value stored in memory.
98  Ref = 1,
99  /// The access may modify the value stored in memory.
100  Mod = 2,
101  /// The access may reference and may modify the value stored in memory.
102  ModRef = Ref | Mod,
103  };
104 
105 public:
106  bool operator==(const ModRefResult &rhs) const { return kind == rhs.kind; }
107  bool operator!=(const ModRefResult &rhs) const { return !(*this == rhs); }
108 
109  /// Return a new result that indicates that the memory access neither
110  /// references nor modifies the value stored in memory.
111  static ModRefResult getNoModRef() { return Kind::NoModRef; }
112 
113  /// Return a new result that indicates that the memory access may reference
114  /// the value stored in memory.
115  static ModRefResult getRef() { return Kind::Ref; }
116 
117  /// Return a new result that indicates that the memory access may modify the
118  /// value stored in memory.
119  static ModRefResult getMod() { return Kind::Mod; }
120 
121  /// Return a new result that indicates that the memory access may reference
122  /// and may modify the value stored in memory.
123  static ModRefResult getModAndRef() { return Kind::ModRef; }
124 
125  /// Returns if this result does not modify or reference memory.
126  LLVM_NODISCARD bool isNoModRef() const { return kind == Kind::NoModRef; }
127 
128  /// Returns if this result modifies memory.
129  LLVM_NODISCARD bool isMod() const {
130  return static_cast<int>(kind) & static_cast<int>(Kind::Mod);
131  }
132 
133  /// Returns if this result references memory.
134  LLVM_NODISCARD bool isRef() const {
135  return static_cast<int>(kind) & static_cast<int>(Kind::Ref);
136  }
137 
138  /// Returns if this result modifies *or* references memory.
139  LLVM_NODISCARD bool isModOrRef() const { return kind != Kind::NoModRef; }
140 
141  /// Returns if this result modifies *and* references memory.
142  LLVM_NODISCARD bool isModAndRef() const { return kind == Kind::ModRef; }
143 
144  /// Merge this ModRef result with `other` and return the result.
146  return ModRefResult(static_cast<Kind>(static_cast<int>(kind) |
147  static_cast<int>(other.kind)));
148  }
149  /// Intersect this ModRef result with `other` and return the result.
151  return ModRefResult(static_cast<Kind>(static_cast<int>(kind) &
152  static_cast<int>(other.kind)));
153  }
154 
155  /// Print this ModRef result to the provided output stream.
156  void print(raw_ostream &os) const;
157 
158 private:
159  ModRefResult(Kind kind) : kind(kind) {}
160 
161  /// The internal kind of the result.
162  Kind kind;
163 };
164 
165 inline raw_ostream &operator<<(raw_ostream &os, const ModRefResult &result) {
166  result.print(os);
167  return os;
168 }
169 
170 //===----------------------------------------------------------------------===//
171 // AliasAnalysisTraits
172 //===----------------------------------------------------------------------===//
173 
174 namespace detail {
175 /// This class contains various internal trait classes used by the main
176 /// AliasAnalysis class below.
178  /// This class represents the `Concept` of an alias analysis implementation.
179  /// It is the abstract base class used by the AliasAnalysis class for
180  /// querying into derived analysis implementations.
181  class Concept {
182  public:
183  virtual ~Concept() = default;
184 
185  /// Given two values, return their aliasing behavior.
186  virtual AliasResult alias(Value lhs, Value rhs) = 0;
187 
188  /// Return the modify-reference behavior of `op` on `location`.
189  virtual ModRefResult getModRef(Operation *op, Value location) = 0;
190  };
191 
192  /// This class represents the `Model` of an alias analysis implementation
193  /// `ImplT`. A model is instantiated for each alias analysis implementation
194  /// to implement the `Concept` without the need for the derived
195  /// implementation to inherit from the `Concept` class.
196  template <typename ImplT> class Model final : public Concept {
197  public:
198  explicit Model(ImplT &&impl) : impl(std::forward<ImplT>(impl)) {}
199  ~Model() override = default;
200 
201  /// Given two values, return their aliasing behavior.
202  AliasResult alias(Value lhs, Value rhs) final {
203  return impl.alias(lhs, rhs);
204  }
205 
206  /// Return the modify-reference behavior of `op` on `location`.
207  ModRefResult getModRef(Operation *op, Value location) final {
208  return impl.getModRef(op, location);
209  }
210 
211  private:
212  ImplT impl;
213  };
214 };
215 } // namespace detail
216 
217 //===----------------------------------------------------------------------===//
218 // AliasAnalysis
219 //===----------------------------------------------------------------------===//
220 
221 /// This class represents the main alias analysis interface in MLIR. It
222 /// functions as an aggregate of various different alias analysis
223 /// implementations. This aggregation allows for utilizing the strengths of
224 /// different alias analysis implementations that either target or have access
225 /// to different aliasing information. This is especially important for MLIR
226 /// given the scope of different types of memory models and aliasing behaviors.
227 /// For users of this analysis that want to perform aliasing queries, see the
228 /// `Alias Queries` section below for the available methods. For users of this
229 /// analysis that want to add a new alias analysis implementation to the
230 /// aggregate, see the `Alias Implementations` section below.
233  template <typename ImplT>
235 
236 public:
238 
239  //===--------------------------------------------------------------------===//
240  // Alias Implementations
241  //===--------------------------------------------------------------------===//
242 
243  /// Add a new alias analysis implementation `AnalysisT` to this analysis
244  /// aggregate. This allows for users to access this implementation when
245  /// performing alias queries. Implementations added here must provide the
246  /// following:
247  /// * AnalysisT(AnalysisT &&)
248  /// * AliasResult alias(Value lhs, Value rhs)
249  /// - This method returns an `AliasResult` that corresponds to the
250  /// aliasing behavior between `lhs` and `rhs`. The conservative "I don't
251  /// know" result of this method should be MayAlias.
252  /// * ModRefResult getModRef(Operation *op, Value location)
253  /// - This method returns a `ModRefResult` that corresponds to the
254  /// modify-reference behavior of `op` on the given `location`. The
255  /// conservative "I don't know" result of this method should be ModRef.
256  template <typename AnalysisT>
257  void addAnalysisImplementation(AnalysisT &&analysis) {
258  aliasImpls.push_back(
259  std::make_unique<Model<AnalysisT>>(std::forward<AnalysisT>(analysis)));
260  }
261 
262  //===--------------------------------------------------------------------===//
263  // Alias Queries
264  //===--------------------------------------------------------------------===//
265 
266  /// Given two values, return their aliasing behavior.
267  AliasResult alias(Value lhs, Value rhs);
268 
269  //===--------------------------------------------------------------------===//
270  // ModRef Queries
271  //===--------------------------------------------------------------------===//
272 
273  /// Return the modify-reference behavior of `op` on `location`.
274  ModRefResult getModRef(Operation *op, Value location);
275 
276 private:
277  /// A set of internal alias analysis implementations.
279 };
280 
281 } // namespace mlir
282 
283 #endif // MLIR_ANALYSIS_ALIASANALYSIS_H_
Include the generated interface declarations.
static ModRefResult getRef()
Return a new result that indicates that the memory access may reference the value stored in memory...
bool isPartial() const
Returns if this result is a partial alias.
Definition: AliasAnalysis.h:68
RHS of mod is always a constant or a symbolic expression with a positive value.
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
The possible results of an alias query.
Definition: AliasAnalysis.h:26
LLVM_NODISCARD bool isModOrRef() const
Returns if this result modifies or references memory.
ModRefResult intersect(const ModRefResult &other)
Intersect this ModRef result with other and return the result.
The two locations precisely alias each other.
Definition: AliasAnalysis.h:41
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:39
The possible results of whether a memory access modifies or references a memory location.
Definition: AliasAnalysis.h:90
bool isMust() const
Returns if this result is a must alias.
Definition: AliasAnalysis.h:65
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
Definition: AliasAnalysis.h:78
LLVM_NODISCARD bool isRef() const
Returns if this result references memory.
AliasResult alias(Value lhs, Value rhs) final
Given two values, return their aliasing behavior.
This class contains various internal trait classes used by the main AliasAnalysis class below...
LLVM_NODISCARD bool isMod() const
Returns if this result modifies memory.
AliasResult(Kind kind)
Definition: AliasAnalysis.h:44
void print(raw_ostream &os) const
Print this ModRef result to the provided output stream.
This class represents the Model of an alias analysis implementation ImplT.
ModRefResult getModRef(Operation *op, Value location) final
Return the modify-reference behavior of op on location.
bool isMay() const
Returns if this result is a may alias.
Definition: AliasAnalysis.h:62
This class represents the main alias analysis interface in MLIR.
bool isNo() const
Returns if this result is a partial alias.
Definition: AliasAnalysis.h:59
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
The two locations do not alias at all.
Definition: AliasAnalysis.h:34
AliasResult merge(AliasResult other) const
Merge this alias result with other and return a new result that represents the conservative merge of ...
static ModRefResult getMod()
Return a new result that indicates that the memory access may modify 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...
ModRefResult merge(const ModRefResult &other)
Merge this ModRef result with other and return the result.
void print(raw_ostream &os) const
Print this alias result to the provided output stream.
LLVM_NODISCARD bool isNoModRef() const
Returns if this result does not modify or reference memory.
bool operator==(const ModRefResult &rhs) const
void addAnalysisImplementation(AnalysisT &&analysis)
Add a new alias analysis implementation AnalysisT to this analysis aggregate.
bool operator!=(const ModRefResult &rhs) const
The two locations may or may not alias.
Definition: AliasAnalysis.h:37
LLVM_NODISCARD bool isModAndRef() const
Returns if this result modifies and references memory.
This class represents the Concept of an alias analysis implementation.
bool operator==(const AliasResult &other) const
Definition: AliasAnalysis.h:45
bool operator!=(const AliasResult &other) const
Definition: AliasAnalysis.h:46
static ModRefResult getModAndRef()
Return a new result that indicates that the memory access may reference and may modify the value stor...