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. |
37 | MayAlias, |
38 | /// The two locations alias, but only due to a partial overlap. |
39 | PartialAlias, |
40 | /// The two locations precisely alias each other. |
41 | MustAlias, |
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. |
145 | ModRefResult merge(const ModRefResult &other) { |
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. |
150 | ModRefResult intersect(const ModRefResult &other) { |
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. |
177 | struct AliasAnalysisTraits { |
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. |
232 | class AliasAnalysis { |
233 | using Concept = detail::AliasAnalysisTraits::Concept; |
234 | template <typename ImplT> |
235 | using Model = detail::AliasAnalysisTraits::Model<ImplT>; |
236 | |
237 | public: |
238 | AliasAnalysis(Operation *op); |
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. |
279 | SmallVector<std::unique_ptr<Concept>, 4> aliasImpls; |
280 | }; |
281 | |
282 | } // namespace mlir |
283 | |
284 | #endif // MLIR_ANALYSIS_ALIASANALYSIS_H_ |
285 | |