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
19namespace mlir {
20
21//===----------------------------------------------------------------------===//
22// AliasResult
23//===----------------------------------------------------------------------===//
24
25/// The possible results of an alias query.
26class AliasResult {
27public:
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
73private:
74 /// The internal kind of the result.
75 Kind kind;
76};
77
78inline 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.
90class [[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
105public:
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
158private:
159 ModRefResult(Kind kind) : kind(kind) {}
160
161 /// The internal kind of the result.
162 Kind kind;
163};
164
165inline raw_ostream &operator<<(raw_ostream &os, const ModRefResult &result) {
166 result.print(os);
167 return os;
168}
169
170//===----------------------------------------------------------------------===//
171// AliasAnalysisTraits
172//===----------------------------------------------------------------------===//
173
174namespace detail {
175/// This class contains various internal trait classes used by the main
176/// AliasAnalysis class below.
177struct 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.
232class AliasAnalysis {
233 using Concept = detail::AliasAnalysisTraits::Concept;
234 template <typename ImplT>
235 using Model = detail::AliasAnalysisTraits::Model<ImplT>;
236
237public:
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
277private:
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

source code of mlir/include/mlir/Analysis/AliasAnalysis.h