MLIR  20.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 indicates no possibility of aliasing.
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 [[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  [[nodiscard]] bool isNoModRef() const { return kind == Kind::NoModRef; }
127 
128  /// Returns if this result modifies memory.
129  [[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  [[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  [[nodiscard]] bool isModOrRef() const { return kind != Kind::NoModRef; }
140 
141  /// Returns if this result modifies *and* references memory.
142  [[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>
197  class Model final : public Concept {
198  public:
199  explicit Model(ImplT &&impl) : impl(std::forward<ImplT>(impl)) {}
200  ~Model() override = default;
201 
202  /// Given two values, return their aliasing behavior.
203  AliasResult alias(Value lhs, Value rhs) final {
204  return impl.alias(lhs, rhs);
205  }
206 
207  /// Return the modify-reference behavior of `op` on `location`.
208  ModRefResult getModRef(Operation *op, Value location) final {
209  return impl.getModRef(op, location);
210  }
211 
212  private:
213  ImplT impl;
214  };
215 };
216 } // namespace detail
217 
218 //===----------------------------------------------------------------------===//
219 // AliasAnalysis
220 //===----------------------------------------------------------------------===//
221 
222 /// This class represents the main alias analysis interface in MLIR. It
223 /// functions as an aggregate of various different alias analysis
224 /// implementations. This aggregation allows for utilizing the strengths of
225 /// different alias analysis implementations that either target or have access
226 /// to different aliasing information. This is especially important for MLIR
227 /// given the scope of different types of memory models and aliasing behaviors.
228 /// For users of this analysis that want to perform aliasing queries, see the
229 /// `Alias Queries` section below for the available methods. For users of this
230 /// analysis that want to add a new alias analysis implementation to the
231 /// aggregate, see the `Alias Implementations` section below.
234  template <typename ImplT>
236 
237 public:
239 
240  //===--------------------------------------------------------------------===//
241  // Alias Implementations
242  //===--------------------------------------------------------------------===//
243 
244  /// Add a new alias analysis implementation `AnalysisT` to this analysis
245  /// aggregate. This allows for users to access this implementation when
246  /// performing alias queries. Implementations added here must provide the
247  /// following:
248  /// * AnalysisT(AnalysisT &&)
249  /// * AliasResult alias(Value lhs, Value rhs)
250  /// - This method returns an `AliasResult` that corresponds to the
251  /// aliasing behavior between `lhs` and `rhs`. The conservative "I don't
252  /// know" result of this method should be MayAlias.
253  /// * ModRefResult getModRef(Operation *op, Value location)
254  /// - This method returns a `ModRefResult` that corresponds to the
255  /// modify-reference behavior of `op` on the given `location`. The
256  /// conservative "I don't know" result of this method should be ModRef.
257  template <typename AnalysisT>
258  void addAnalysisImplementation(AnalysisT &&analysis) {
259  aliasImpls.push_back(
260  std::make_unique<Model<AnalysisT>>(std::forward<AnalysisT>(analysis)));
261  }
262 
263  //===--------------------------------------------------------------------===//
264  // Alias Queries
265  //===--------------------------------------------------------------------===//
266 
267  /// Given two values, return their aliasing behavior.
268  AliasResult alias(Value lhs, Value rhs);
269 
270  //===--------------------------------------------------------------------===//
271  // ModRef Queries
272  //===--------------------------------------------------------------------===//
273 
274  /// Return the modify-reference behavior of `op` on `location`.
275  ModRefResult getModRef(Operation *op, Value location);
276 
277 private:
278  /// A set of internal alias analysis implementations.
280 };
281 
282 } // namespace mlir
283 
284 #endif // MLIR_ANALYSIS_ALIASANALYSIS_H_
static void print(spirv::VerCapExtAttr triple, DialectAsmPrinter &printer)
This class represents the main alias analysis interface in MLIR.
AliasAnalysis(Operation *op)
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.
void addAnalysisImplementation(AnalysisT &&analysis)
Add a new alias analysis implementation AnalysisT to this analysis aggregate.
The possible results of an alias query.
Definition: AliasAnalysis.h:26
AliasResult(Kind kind)
Definition: AliasAnalysis.h:44
bool isPartial() const
Returns if this result is a partial alias.
Definition: AliasAnalysis.h:68
bool operator==(const AliasResult &other) const
Definition: AliasAnalysis.h:45
bool isMay() const
Returns if this result is a may alias.
Definition: AliasAnalysis.h:62
AliasResult merge(AliasResult other) const
Merge this alias result with other and return a new result that represents the conservative merge of ...
bool operator!=(const AliasResult &other) const
Definition: AliasAnalysis.h:46
void print(raw_ostream &os) const
Print this alias result to the provided output stream.
bool isMust() const
Returns if this result is a must alias.
Definition: AliasAnalysis.h:65
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
@ PartialAlias
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 isModAndRef() const
Returns if this result modifies and references memory.
ModRefResult intersect(const ModRefResult &other)
Intersect this ModRef result with other and return the result.
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...
bool isMod() const
Returns if this result modifies memory.
bool operator==(const ModRefResult &rhs) const
bool isNoModRef() const
Returns if this result does not modify or reference memory.
static ModRefResult getModAndRef()
Return a new result that indicates that the memory access may reference and may modify the value stor...
void print(raw_ostream &os) const
Print this ModRef result to the provided output stream.
bool operator!=(const ModRefResult &rhs) const
static ModRefResult getMod()
Return a new result that indicates that the memory access may modify the value stored in memory.
bool isRef() const
Returns if this result references memory.
bool isModOrRef() const
Returns if this result modifies or references memory.
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
This class represents the Concept of an alias analysis implementation.
virtual ModRefResult getModRef(Operation *op, Value location)=0
Return the modify-reference behavior of op on location.
virtual AliasResult alias(Value lhs, Value rhs)=0
Given two values, return their aliasing behavior.
This class represents the Model of an alias analysis implementation ImplT.
AliasResult alias(Value lhs, Value rhs) final
Given two values, return their aliasing behavior.
ModRefResult getModRef(Operation *op, Value location) final
Return the modify-reference behavior of op on location.
Kind
An enumeration of the kinds of predicates.
Definition: Predicate.h:44
Include the generated interface declarations.
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
Definition: AliasAnalysis.h:78
This class contains various internal trait classes used by the main AliasAnalysis class below.