1 | //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- 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 file defines the generic AliasAnalysis interface, which is used as the |
10 | // common interface used by all clients of alias analysis information, and |
11 | // implemented by all alias analysis implementations. Mod/Ref information is |
12 | // also captured by this interface. |
13 | // |
14 | // Implementations of this interface must implement the various virtual methods, |
15 | // which automatically provides functionality for the entire suite of client |
16 | // APIs. |
17 | // |
18 | // This API identifies memory regions with the MemoryLocation class. The pointer |
19 | // component specifies the base memory address of the region. The Size specifies |
20 | // the maximum size (in address units) of the memory region, or |
21 | // MemoryLocation::UnknownSize if the size is not known. The TBAA tag |
22 | // identifies the "type" of the memory reference; see the |
23 | // TypeBasedAliasAnalysis class for details. |
24 | // |
25 | // Some non-obvious details include: |
26 | // - Pointers that point to two completely different objects in memory never |
27 | // alias, regardless of the value of the Size component. |
28 | // - NoAlias doesn't imply inequal pointers. The most obvious example of this |
29 | // is two pointers to constant memory. Even if they are equal, constant |
30 | // memory is never stored to, so there will never be any dependencies. |
31 | // In this and other situations, the pointers may be both NoAlias and |
32 | // MustAlias at the same time. The current API can only return one result, |
33 | // though this is rarely a problem in practice. |
34 | // |
35 | //===----------------------------------------------------------------------===// |
36 | |
37 | #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H |
38 | #define LLVM_ANALYSIS_ALIASANALYSIS_H |
39 | |
40 | #include "llvm/ADT/DenseMap.h" |
41 | #include "llvm/ADT/None.h" |
42 | #include "llvm/ADT/Optional.h" |
43 | #include "llvm/ADT/SmallVector.h" |
44 | #include "llvm/Analysis/MemoryLocation.h" |
45 | #include "llvm/IR/PassManager.h" |
46 | #include "llvm/Pass.h" |
47 | #include <cstdint> |
48 | #include <functional> |
49 | #include <memory> |
50 | #include <vector> |
51 | |
52 | namespace llvm { |
53 | |
54 | class AnalysisUsage; |
55 | class AtomicCmpXchgInst; |
56 | class BasicAAResult; |
57 | class BasicBlock; |
58 | class CatchPadInst; |
59 | class CatchReturnInst; |
60 | class DominatorTree; |
61 | class FenceInst; |
62 | class Function; |
63 | class InvokeInst; |
64 | class PreservedAnalyses; |
65 | class TargetLibraryInfo; |
66 | class Value; |
67 | |
68 | /// The possible results of an alias query. |
69 | /// |
70 | /// These results are always computed between two MemoryLocation objects as |
71 | /// a query to some alias analysis. |
72 | /// |
73 | /// Note that these are unscoped enumerations because we would like to support |
74 | /// implicitly testing a result for the existence of any possible aliasing with |
75 | /// a conversion to bool, but an "enum class" doesn't support this. The |
76 | /// canonical names from the literature are suffixed and unique anyways, and so |
77 | /// they serve as global constants in LLVM for these results. |
78 | /// |
79 | /// See docs/AliasAnalysis.html for more information on the specific meanings |
80 | /// of these values. |
81 | class AliasResult { |
82 | private: |
83 | static const int OffsetBits = 23; |
84 | static const int AliasBits = 8; |
85 | static_assert(AliasBits + 1 + OffsetBits <= 32, |
86 | "AliasResult size is intended to be 4 bytes!" ); |
87 | |
88 | unsigned int Alias : AliasBits; |
89 | unsigned int HasOffset : 1; |
90 | signed int Offset : OffsetBits; |
91 | |
92 | public: |
93 | enum Kind : uint8_t { |
94 | /// The two locations do not alias at all. |
95 | /// |
96 | /// This value is arranged to convert to false, while all other values |
97 | /// convert to true. This allows a boolean context to convert the result to |
98 | /// a binary flag indicating whether there is the possibility of aliasing. |
99 | NoAlias = 0, |
100 | /// The two locations may or may not alias. This is the least precise |
101 | /// result. |
102 | MayAlias, |
103 | /// The two locations alias, but only due to a partial overlap. |
104 | PartialAlias, |
105 | /// The two locations precisely alias each other. |
106 | MustAlias, |
107 | }; |
108 | static_assert(MustAlias < (1 << AliasBits), |
109 | "Not enough bit field size for the enum!" ); |
110 | |
111 | explicit AliasResult() = delete; |
112 | constexpr AliasResult(const Kind &Alias) |
113 | : Alias(Alias), HasOffset(false), Offset(0) {} |
114 | |
115 | operator Kind() const { return static_cast<Kind>(Alias); } |
116 | |
117 | constexpr bool hasOffset() const { return HasOffset; } |
118 | constexpr int32_t getOffset() const { |
119 | assert(HasOffset && "No offset!" ); |
120 | return Offset; |
121 | } |
122 | void setOffset(int32_t NewOffset) { |
123 | if (isInt<OffsetBits>(NewOffset)) { |
124 | HasOffset = true; |
125 | Offset = NewOffset; |
126 | } |
127 | } |
128 | |
129 | /// Helper for processing AliasResult for swapped memory location pairs. |
130 | void swap(bool DoSwap = true) { |
131 | if (DoSwap && hasOffset()) |
132 | setOffset(-getOffset()); |
133 | } |
134 | }; |
135 | |
136 | static_assert(sizeof(AliasResult) == 4, |
137 | "AliasResult size is intended to be 4 bytes!" ); |
138 | |
139 | /// << operator for AliasResult. |
140 | raw_ostream &operator<<(raw_ostream &OS, AliasResult AR); |
141 | |
142 | /// Flags indicating whether a memory access modifies or references memory. |
143 | /// |
144 | /// This is no access at all, a modification, a reference, or both |
145 | /// a modification and a reference. These are specifically structured such that |
146 | /// they form a three bit matrix and bit-tests for 'mod' or 'ref' or 'must' |
147 | /// work with any of the possible values. |
148 | enum class ModRefInfo : uint8_t { |
149 | /// Must is provided for completeness, but no routines will return only |
150 | /// Must today. See definition of Must below. |
151 | Must = 0, |
152 | /// The access may reference the value stored in memory, |
153 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
154 | MustRef = 1, |
155 | /// The access may modify the value stored in memory, |
156 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
157 | MustMod = 2, |
158 | /// The access may reference, modify or both the value stored in memory, |
159 | /// a mustAlias relation was found, and no mayAlias or partialAlias found. |
160 | MustModRef = MustRef | MustMod, |
161 | /// The access neither references nor modifies the value stored in memory. |
162 | NoModRef = 4, |
163 | /// The access may reference the value stored in memory. |
164 | Ref = NoModRef | MustRef, |
165 | /// The access may modify the value stored in memory. |
166 | Mod = NoModRef | MustMod, |
167 | /// The access may reference and may modify the value stored in memory. |
168 | ModRef = Ref | Mod, |
169 | |
170 | /// About Must: |
171 | /// Must is set in a best effort manner. |
172 | /// We usually do not try our best to infer Must, instead it is merely |
173 | /// another piece of "free" information that is presented when available. |
174 | /// Must set means there was certainly a MustAlias found. For calls, |
175 | /// where multiple arguments are checked (argmemonly), this translates to |
176 | /// only MustAlias or NoAlias was found. |
177 | /// Must is not set for RAR accesses, even if the two locations must |
178 | /// alias. The reason is that two read accesses translate to an early return |
179 | /// of NoModRef. An additional alias check to set Must may be |
180 | /// expensive. Other cases may also not set Must(e.g. callCapturesBefore). |
181 | /// We refer to Must being *set* when the most significant bit is *cleared*. |
182 | /// Conversely we *clear* Must information by *setting* the Must bit to 1. |
183 | }; |
184 | |
185 | LLVM_NODISCARD inline bool isNoModRef(const ModRefInfo MRI) { |
186 | return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
187 | static_cast<int>(ModRefInfo::Must); |
188 | } |
189 | LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) { |
190 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef); |
191 | } |
192 | LLVM_NODISCARD inline bool isModAndRefSet(const ModRefInfo MRI) { |
193 | return (static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef)) == |
194 | static_cast<int>(ModRefInfo::MustModRef); |
195 | } |
196 | LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) { |
197 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod); |
198 | } |
199 | LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) { |
200 | return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef); |
201 | } |
202 | LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) { |
203 | return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef)); |
204 | } |
205 | |
206 | LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) { |
207 | return ModRefInfo(static_cast<int>(MRI) | |
208 | static_cast<int>(ModRefInfo::MustMod)); |
209 | } |
210 | LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) { |
211 | return ModRefInfo(static_cast<int>(MRI) | |
212 | static_cast<int>(ModRefInfo::MustRef)); |
213 | } |
214 | LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) { |
215 | return ModRefInfo(static_cast<int>(MRI) & |
216 | static_cast<int>(ModRefInfo::MustModRef)); |
217 | } |
218 | LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) { |
219 | return ModRefInfo(static_cast<int>(MRI) | |
220 | static_cast<int>(ModRefInfo::MustModRef)); |
221 | } |
222 | LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) { |
223 | return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref)); |
224 | } |
225 | LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) { |
226 | return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod)); |
227 | } |
228 | LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) { |
229 | return ModRefInfo(static_cast<int>(MRI) | |
230 | static_cast<int>(ModRefInfo::NoModRef)); |
231 | } |
232 | LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1, |
233 | const ModRefInfo MRI2) { |
234 | return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2)); |
235 | } |
236 | LLVM_NODISCARD inline ModRefInfo intersectModRef(const ModRefInfo MRI1, |
237 | const ModRefInfo MRI2) { |
238 | return ModRefInfo(static_cast<int>(MRI1) & static_cast<int>(MRI2)); |
239 | } |
240 | |
241 | /// The locations at which a function might access memory. |
242 | /// |
243 | /// These are primarily used in conjunction with the \c AccessKind bits to |
244 | /// describe both the nature of access and the locations of access for a |
245 | /// function call. |
246 | enum FunctionModRefLocation { |
247 | /// Base case is no access to memory. |
248 | FMRL_Nowhere = 0, |
249 | /// Access to memory via argument pointers. |
250 | FMRL_ArgumentPointees = 8, |
251 | /// Memory that is inaccessible via LLVM IR. |
252 | FMRL_InaccessibleMem = 16, |
253 | /// Access to any memory. |
254 | FMRL_Anywhere = 32 | FMRL_InaccessibleMem | FMRL_ArgumentPointees |
255 | }; |
256 | |
257 | /// Summary of how a function affects memory in the program. |
258 | /// |
259 | /// Loads from constant globals are not considered memory accesses for this |
260 | /// interface. Also, functions may freely modify stack space local to their |
261 | /// invocation without having to report it through these interfaces. |
262 | enum FunctionModRefBehavior { |
263 | /// This function does not perform any non-local loads or stores to memory. |
264 | /// |
265 | /// This property corresponds to the GCC 'const' attribute. |
266 | /// This property corresponds to the LLVM IR 'readnone' attribute. |
267 | /// This property corresponds to the IntrNoMem LLVM intrinsic flag. |
268 | FMRB_DoesNotAccessMemory = |
269 | FMRL_Nowhere | static_cast<int>(ModRefInfo::NoModRef), |
270 | |
271 | /// The only memory references in this function (if it has any) are |
272 | /// non-volatile loads from objects pointed to by its pointer-typed |
273 | /// arguments, with arbitrary offsets. |
274 | /// |
275 | /// This property corresponds to the combination of the IntrReadMem |
276 | /// and IntrArgMemOnly LLVM intrinsic flags. |
277 | FMRB_OnlyReadsArgumentPointees = |
278 | FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Ref), |
279 | |
280 | /// The only memory references in this function (if it has any) are |
281 | /// non-volatile stores from objects pointed to by its pointer-typed |
282 | /// arguments, with arbitrary offsets. |
283 | /// |
284 | /// This property corresponds to the combination of the IntrWriteMem |
285 | /// and IntrArgMemOnly LLVM intrinsic flags. |
286 | FMRB_OnlyWritesArgumentPointees = |
287 | FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::Mod), |
288 | |
289 | /// The only memory references in this function (if it has any) are |
290 | /// non-volatile loads and stores from objects pointed to by its |
291 | /// pointer-typed arguments, with arbitrary offsets. |
292 | /// |
293 | /// This property corresponds to the IntrArgMemOnly LLVM intrinsic flag. |
294 | FMRB_OnlyAccessesArgumentPointees = |
295 | FMRL_ArgumentPointees | static_cast<int>(ModRefInfo::ModRef), |
296 | |
297 | /// The only memory references in this function (if it has any) are |
298 | /// reads of memory that is otherwise inaccessible via LLVM IR. |
299 | /// |
300 | /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
301 | FMRB_OnlyReadsInaccessibleMem = |
302 | FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Ref), |
303 | |
304 | /// The only memory references in this function (if it has any) are |
305 | /// writes to memory that is otherwise inaccessible via LLVM IR. |
306 | /// |
307 | /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
308 | FMRB_OnlyWritesInaccessibleMem = |
309 | FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::Mod), |
310 | |
311 | /// The only memory references in this function (if it has any) are |
312 | /// references of memory that is otherwise inaccessible via LLVM IR. |
313 | /// |
314 | /// This property corresponds to the LLVM IR inaccessiblememonly attribute. |
315 | FMRB_OnlyAccessesInaccessibleMem = |
316 | FMRL_InaccessibleMem | static_cast<int>(ModRefInfo::ModRef), |
317 | |
318 | /// The function may perform non-volatile loads from objects pointed |
319 | /// to by its pointer-typed arguments, with arbitrary offsets, and |
320 | /// it may also perform loads of memory that is otherwise |
321 | /// inaccessible via LLVM IR. |
322 | /// |
323 | /// This property corresponds to the LLVM IR |
324 | /// inaccessiblemem_or_argmemonly attribute. |
325 | FMRB_OnlyReadsInaccessibleOrArgMem = FMRL_InaccessibleMem | |
326 | FMRL_ArgumentPointees | |
327 | static_cast<int>(ModRefInfo::Ref), |
328 | |
329 | /// The function may perform non-volatile stores to objects pointed |
330 | /// to by its pointer-typed arguments, with arbitrary offsets, and |
331 | /// it may also perform stores of memory that is otherwise |
332 | /// inaccessible via LLVM IR. |
333 | /// |
334 | /// This property corresponds to the LLVM IR |
335 | /// inaccessiblemem_or_argmemonly attribute. |
336 | FMRB_OnlyWritesInaccessibleOrArgMem = FMRL_InaccessibleMem | |
337 | FMRL_ArgumentPointees | |
338 | static_cast<int>(ModRefInfo::Mod), |
339 | |
340 | /// The function may perform non-volatile loads and stores of objects |
341 | /// pointed to by its pointer-typed arguments, with arbitrary offsets, and |
342 | /// it may also perform loads and stores of memory that is otherwise |
343 | /// inaccessible via LLVM IR. |
344 | /// |
345 | /// This property corresponds to the LLVM IR |
346 | /// inaccessiblemem_or_argmemonly attribute. |
347 | FMRB_OnlyAccessesInaccessibleOrArgMem = FMRL_InaccessibleMem | |
348 | FMRL_ArgumentPointees | |
349 | static_cast<int>(ModRefInfo::ModRef), |
350 | |
351 | /// This function does not perform any non-local stores or volatile loads, |
352 | /// but may read from any memory location. |
353 | /// |
354 | /// This property corresponds to the GCC 'pure' attribute. |
355 | /// This property corresponds to the LLVM IR 'readonly' attribute. |
356 | /// This property corresponds to the IntrReadMem LLVM intrinsic flag. |
357 | FMRB_OnlyReadsMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Ref), |
358 | |
359 | // This function does not read from memory anywhere, but may write to any |
360 | // memory location. |
361 | // |
362 | // This property corresponds to the LLVM IR 'writeonly' attribute. |
363 | // This property corresponds to the IntrWriteMem LLVM intrinsic flag. |
364 | FMRB_OnlyWritesMemory = FMRL_Anywhere | static_cast<int>(ModRefInfo::Mod), |
365 | |
366 | /// This indicates that the function could not be classified into one of the |
367 | /// behaviors above. |
368 | FMRB_UnknownModRefBehavior = |
369 | FMRL_Anywhere | static_cast<int>(ModRefInfo::ModRef) |
370 | }; |
371 | |
372 | // Wrapper method strips bits significant only in FunctionModRefBehavior, |
373 | // to obtain a valid ModRefInfo. The benefit of using the wrapper is that if |
374 | // ModRefInfo enum changes, the wrapper can be updated to & with the new enum |
375 | // entry with all bits set to 1. |
376 | LLVM_NODISCARD inline ModRefInfo |
377 | createModRefInfo(const FunctionModRefBehavior FMRB) { |
378 | return ModRefInfo(FMRB & static_cast<int>(ModRefInfo::ModRef)); |
379 | } |
380 | |
381 | /// Reduced version of MemoryLocation that only stores a pointer and size. |
382 | /// Used for caching AATags independent BasicAA results. |
383 | struct AACacheLoc { |
384 | const Value *Ptr; |
385 | LocationSize Size; |
386 | }; |
387 | |
388 | template <> struct DenseMapInfo<AACacheLoc> { |
389 | static inline AACacheLoc getEmptyKey() { |
390 | return {DenseMapInfo<const Value *>::getEmptyKey(), |
391 | DenseMapInfo<LocationSize>::getEmptyKey()}; |
392 | } |
393 | static inline AACacheLoc getTombstoneKey() { |
394 | return {DenseMapInfo<const Value *>::getTombstoneKey(), |
395 | DenseMapInfo<LocationSize>::getTombstoneKey()}; |
396 | } |
397 | static unsigned getHashValue(const AACacheLoc &Val) { |
398 | return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^ |
399 | DenseMapInfo<LocationSize>::getHashValue(Val.Size); |
400 | } |
401 | static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) { |
402 | return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size; |
403 | } |
404 | }; |
405 | |
406 | /// This class stores info we want to provide to or retain within an alias |
407 | /// query. By default, the root query is stateless and starts with a freshly |
408 | /// constructed info object. Specific alias analyses can use this query info to |
409 | /// store per-query state that is important for recursive or nested queries to |
410 | /// avoid recomputing. To enable preserving this state across multiple queries |
411 | /// where safe (due to the IR not changing), use a `BatchAAResults` wrapper. |
412 | /// The information stored in an `AAQueryInfo` is currently limitted to the |
413 | /// caches used by BasicAA, but can further be extended to fit other AA needs. |
414 | class AAQueryInfo { |
415 | public: |
416 | using LocPair = std::pair<AACacheLoc, AACacheLoc>; |
417 | struct CacheEntry { |
418 | AliasResult Result; |
419 | /// Number of times a NoAlias assumption has been used. |
420 | /// 0 for assumptions that have not been used, -1 for definitive results. |
421 | int NumAssumptionUses; |
422 | /// Whether this is a definitive (non-assumption) result. |
423 | bool isDefinitive() const { return NumAssumptionUses < 0; } |
424 | }; |
425 | using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>; |
426 | AliasCacheT AliasCache; |
427 | |
428 | using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>; |
429 | IsCapturedCacheT IsCapturedCache; |
430 | |
431 | /// Query depth used to distinguish recursive queries. |
432 | unsigned Depth = 0; |
433 | |
434 | /// How many active NoAlias assumption uses there are. |
435 | int NumAssumptionUses = 0; |
436 | |
437 | /// Location pairs for which an assumption based result is currently stored. |
438 | /// Used to remove all potentially incorrect results from the cache if an |
439 | /// assumption is disproven. |
440 | SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults; |
441 | |
442 | AAQueryInfo() : AliasCache(), IsCapturedCache() {} |
443 | |
444 | /// Create a new AAQueryInfo based on this one, but with the cache cleared. |
445 | /// This is used for recursive queries across phis, where cache results may |
446 | /// not be valid. |
447 | AAQueryInfo withEmptyCache() { |
448 | AAQueryInfo NewAAQI; |
449 | NewAAQI.Depth = Depth; |
450 | return NewAAQI; |
451 | } |
452 | }; |
453 | |
454 | class BatchAAResults; |
455 | |
456 | class AAResults { |
457 | public: |
458 | // Make these results default constructable and movable. We have to spell |
459 | // these out because MSVC won't synthesize them. |
460 | AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {} |
461 | AAResults(AAResults &&Arg); |
462 | ~AAResults(); |
463 | |
464 | /// Register a specific AA result. |
465 | template <typename AAResultT> void addAAResult(AAResultT &AAResult) { |
466 | // FIXME: We should use a much lighter weight system than the usual |
467 | // polymorphic pattern because we don't own AAResult. It should |
468 | // ideally involve two pointers and no separate allocation. |
469 | AAs.emplace_back(new Model<AAResultT>(AAResult, *this)); |
470 | } |
471 | |
472 | /// Register a function analysis ID that the results aggregation depends on. |
473 | /// |
474 | /// This is used in the new pass manager to implement the invalidation logic |
475 | /// where we must invalidate the results aggregation if any of our component |
476 | /// analyses become invalid. |
477 | void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(ID); } |
478 | |
479 | /// Handle invalidation events in the new pass manager. |
480 | /// |
481 | /// The aggregation is invalidated if any of the underlying analyses is |
482 | /// invalidated. |
483 | bool invalidate(Function &F, const PreservedAnalyses &PA, |
484 | FunctionAnalysisManager::Invalidator &Inv); |
485 | |
486 | //===--------------------------------------------------------------------===// |
487 | /// \name Alias Queries |
488 | /// @{ |
489 | |
490 | /// The main low level interface to the alias analysis implementation. |
491 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
492 | /// each other. This is the interface that must be implemented by specific |
493 | /// alias analysis implementations. |
494 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB); |
495 | |
496 | /// A convenience wrapper around the primary \c alias interface. |
497 | AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2, |
498 | LocationSize V2Size) { |
499 | return alias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
500 | } |
501 | |
502 | /// A convenience wrapper around the primary \c alias interface. |
503 | AliasResult alias(const Value *V1, const Value *V2) { |
504 | return alias(MemoryLocation::getBeforeOrAfter(V1), |
505 | MemoryLocation::getBeforeOrAfter(V2)); |
506 | } |
507 | |
508 | /// A trivial helper function to check to see if the specified pointers are |
509 | /// no-alias. |
510 | bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
511 | return alias(LocA, LocB) == AliasResult::NoAlias; |
512 | } |
513 | |
514 | /// A convenience wrapper around the \c isNoAlias helper interface. |
515 | bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2, |
516 | LocationSize V2Size) { |
517 | return isNoAlias(MemoryLocation(V1, V1Size), MemoryLocation(V2, V2Size)); |
518 | } |
519 | |
520 | /// A convenience wrapper around the \c isNoAlias helper interface. |
521 | bool isNoAlias(const Value *V1, const Value *V2) { |
522 | return isNoAlias(MemoryLocation::getBeforeOrAfter(V1), |
523 | MemoryLocation::getBeforeOrAfter(V2)); |
524 | } |
525 | |
526 | /// A trivial helper function to check to see if the specified pointers are |
527 | /// must-alias. |
528 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
529 | return alias(LocA, LocB) == AliasResult::MustAlias; |
530 | } |
531 | |
532 | /// A convenience wrapper around the \c isMustAlias helper interface. |
533 | bool isMustAlias(const Value *V1, const Value *V2) { |
534 | return alias(V1, LocationSize::precise(1), V2, LocationSize::precise(1)) == |
535 | AliasResult::MustAlias; |
536 | } |
537 | |
538 | /// Checks whether the given location points to constant memory, or if |
539 | /// \p OrLocal is true whether it points to a local alloca. |
540 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false); |
541 | |
542 | /// A convenience wrapper around the primary \c pointsToConstantMemory |
543 | /// interface. |
544 | bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { |
545 | return pointsToConstantMemory(MemoryLocation::getBeforeOrAfter(P), OrLocal); |
546 | } |
547 | |
548 | /// @} |
549 | //===--------------------------------------------------------------------===// |
550 | /// \name Simple mod/ref information |
551 | /// @{ |
552 | |
553 | /// Get the ModRef info associated with a pointer argument of a call. The |
554 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
555 | /// that these bits do not necessarily account for the overall behavior of |
556 | /// the function, but rather only provide additional per-argument |
557 | /// information. This never sets ModRefInfo::Must. |
558 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx); |
559 | |
560 | /// Return the behavior of the given call site. |
561 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call); |
562 | |
563 | /// Return the behavior when calling the given function. |
564 | FunctionModRefBehavior getModRefBehavior(const Function *F); |
565 | |
566 | /// Checks if the specified call is known to never read or write memory. |
567 | /// |
568 | /// Note that if the call only reads from known-constant memory, it is also |
569 | /// legal to return true. Also, calls that unwind the stack are legal for |
570 | /// this predicate. |
571 | /// |
572 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
573 | /// without worrying about aliasing properties, and many calls have this |
574 | /// property (e.g. calls to 'sin' and 'cos'). |
575 | /// |
576 | /// This property corresponds to the GCC 'const' attribute. |
577 | bool doesNotAccessMemory(const CallBase *Call) { |
578 | return getModRefBehavior(Call) == FMRB_DoesNotAccessMemory; |
579 | } |
580 | |
581 | /// Checks if the specified function is known to never read or write memory. |
582 | /// |
583 | /// Note that if the function only reads from known-constant memory, it is |
584 | /// also legal to return true. Also, function that unwind the stack are legal |
585 | /// for this predicate. |
586 | /// |
587 | /// Many optimizations (such as CSE and LICM) can be performed on such calls |
588 | /// to such functions without worrying about aliasing properties, and many |
589 | /// functions have this property (e.g. 'sin' and 'cos'). |
590 | /// |
591 | /// This property corresponds to the GCC 'const' attribute. |
592 | bool doesNotAccessMemory(const Function *F) { |
593 | return getModRefBehavior(F) == FMRB_DoesNotAccessMemory; |
594 | } |
595 | |
596 | /// Checks if the specified call is known to only read from non-volatile |
597 | /// memory (or not access memory at all). |
598 | /// |
599 | /// Calls that unwind the stack are legal for this predicate. |
600 | /// |
601 | /// This property allows many common optimizations to be performed in the |
602 | /// absence of interfering store instructions, such as CSE of strlen calls. |
603 | /// |
604 | /// This property corresponds to the GCC 'pure' attribute. |
605 | bool onlyReadsMemory(const CallBase *Call) { |
606 | return onlyReadsMemory(getModRefBehavior(Call)); |
607 | } |
608 | |
609 | /// Checks if the specified function is known to only read from non-volatile |
610 | /// memory (or not access memory at all). |
611 | /// |
612 | /// Functions that unwind the stack are legal for this predicate. |
613 | /// |
614 | /// This property allows many common optimizations to be performed in the |
615 | /// absence of interfering store instructions, such as CSE of strlen calls. |
616 | /// |
617 | /// This property corresponds to the GCC 'pure' attribute. |
618 | bool onlyReadsMemory(const Function *F) { |
619 | return onlyReadsMemory(getModRefBehavior(F)); |
620 | } |
621 | |
622 | /// Checks if functions with the specified behavior are known to only read |
623 | /// from non-volatile memory (or not access memory at all). |
624 | static bool onlyReadsMemory(FunctionModRefBehavior MRB) { |
625 | return !isModSet(createModRefInfo(MRB)); |
626 | } |
627 | |
628 | /// Checks if functions with the specified behavior are known to only write |
629 | /// memory (or not access memory at all). |
630 | static bool doesNotReadMemory(FunctionModRefBehavior MRB) { |
631 | return !isRefSet(createModRefInfo(MRB)); |
632 | } |
633 | |
634 | /// Checks if functions with the specified behavior are known to read and |
635 | /// write at most from objects pointed to by their pointer-typed arguments |
636 | /// (with arbitrary offsets). |
637 | static bool onlyAccessesArgPointees(FunctionModRefBehavior MRB) { |
638 | return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_ArgumentPointees); |
639 | } |
640 | |
641 | /// Checks if functions with the specified behavior are known to potentially |
642 | /// read or write from objects pointed to be their pointer-typed arguments |
643 | /// (with arbitrary offsets). |
644 | static bool doesAccessArgPointees(FunctionModRefBehavior MRB) { |
645 | return isModOrRefSet(createModRefInfo(MRB)) && |
646 | ((unsigned)MRB & FMRL_ArgumentPointees); |
647 | } |
648 | |
649 | /// Checks if functions with the specified behavior are known to read and |
650 | /// write at most from memory that is inaccessible from LLVM IR. |
651 | static bool onlyAccessesInaccessibleMem(FunctionModRefBehavior MRB) { |
652 | return !((unsigned)MRB & FMRL_Anywhere & ~FMRL_InaccessibleMem); |
653 | } |
654 | |
655 | /// Checks if functions with the specified behavior are known to potentially |
656 | /// read or write from memory that is inaccessible from LLVM IR. |
657 | static bool doesAccessInaccessibleMem(FunctionModRefBehavior MRB) { |
658 | return isModOrRefSet(createModRefInfo(MRB)) && |
659 | ((unsigned)MRB & FMRL_InaccessibleMem); |
660 | } |
661 | |
662 | /// Checks if functions with the specified behavior are known to read and |
663 | /// write at most from memory that is inaccessible from LLVM IR or objects |
664 | /// pointed to by their pointer-typed arguments (with arbitrary offsets). |
665 | static bool onlyAccessesInaccessibleOrArgMem(FunctionModRefBehavior MRB) { |
666 | return !((unsigned)MRB & FMRL_Anywhere & |
667 | ~(FMRL_InaccessibleMem | FMRL_ArgumentPointees)); |
668 | } |
669 | |
670 | /// getModRefInfo (for call sites) - Return information about whether |
671 | /// a particular call site modifies or reads the specified memory location. |
672 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc); |
673 | |
674 | /// getModRefInfo (for call sites) - A convenience wrapper. |
675 | ModRefInfo getModRefInfo(const CallBase *Call, const Value *P, |
676 | LocationSize Size) { |
677 | return getModRefInfo(Call, MemoryLocation(P, Size)); |
678 | } |
679 | |
680 | /// getModRefInfo (for loads) - Return information about whether |
681 | /// a particular load modifies or reads the specified memory location. |
682 | ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc); |
683 | |
684 | /// getModRefInfo (for loads) - A convenience wrapper. |
685 | ModRefInfo getModRefInfo(const LoadInst *L, const Value *P, |
686 | LocationSize Size) { |
687 | return getModRefInfo(L, MemoryLocation(P, Size)); |
688 | } |
689 | |
690 | /// getModRefInfo (for stores) - Return information about whether |
691 | /// a particular store modifies or reads the specified memory location. |
692 | ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc); |
693 | |
694 | /// getModRefInfo (for stores) - A convenience wrapper. |
695 | ModRefInfo getModRefInfo(const StoreInst *S, const Value *P, |
696 | LocationSize Size) { |
697 | return getModRefInfo(S, MemoryLocation(P, Size)); |
698 | } |
699 | |
700 | /// getModRefInfo (for fences) - Return information about whether |
701 | /// a particular store modifies or reads the specified memory location. |
702 | ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc); |
703 | |
704 | /// getModRefInfo (for fences) - A convenience wrapper. |
705 | ModRefInfo getModRefInfo(const FenceInst *S, const Value *P, |
706 | LocationSize Size) { |
707 | return getModRefInfo(S, MemoryLocation(P, Size)); |
708 | } |
709 | |
710 | /// getModRefInfo (for cmpxchges) - Return information about whether |
711 | /// a particular cmpxchg modifies or reads the specified memory location. |
712 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
713 | const MemoryLocation &Loc); |
714 | |
715 | /// getModRefInfo (for cmpxchges) - A convenience wrapper. |
716 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, const Value *P, |
717 | LocationSize Size) { |
718 | return getModRefInfo(CX, MemoryLocation(P, Size)); |
719 | } |
720 | |
721 | /// getModRefInfo (for atomicrmws) - Return information about whether |
722 | /// a particular atomicrmw modifies or reads the specified memory location. |
723 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc); |
724 | |
725 | /// getModRefInfo (for atomicrmws) - A convenience wrapper. |
726 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const Value *P, |
727 | LocationSize Size) { |
728 | return getModRefInfo(RMW, MemoryLocation(P, Size)); |
729 | } |
730 | |
731 | /// getModRefInfo (for va_args) - Return information about whether |
732 | /// a particular va_arg modifies or reads the specified memory location. |
733 | ModRefInfo getModRefInfo(const VAArgInst *I, const MemoryLocation &Loc); |
734 | |
735 | /// getModRefInfo (for va_args) - A convenience wrapper. |
736 | ModRefInfo getModRefInfo(const VAArgInst *I, const Value *P, |
737 | LocationSize Size) { |
738 | return getModRefInfo(I, MemoryLocation(P, Size)); |
739 | } |
740 | |
741 | /// getModRefInfo (for catchpads) - Return information about whether |
742 | /// a particular catchpad modifies or reads the specified memory location. |
743 | ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc); |
744 | |
745 | /// getModRefInfo (for catchpads) - A convenience wrapper. |
746 | ModRefInfo getModRefInfo(const CatchPadInst *I, const Value *P, |
747 | LocationSize Size) { |
748 | return getModRefInfo(I, MemoryLocation(P, Size)); |
749 | } |
750 | |
751 | /// getModRefInfo (for catchrets) - Return information about whether |
752 | /// a particular catchret modifies or reads the specified memory location. |
753 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc); |
754 | |
755 | /// getModRefInfo (for catchrets) - A convenience wrapper. |
756 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const Value *P, |
757 | LocationSize Size) { |
758 | return getModRefInfo(I, MemoryLocation(P, Size)); |
759 | } |
760 | |
761 | /// Check whether or not an instruction may read or write the optionally |
762 | /// specified memory location. |
763 | /// |
764 | /// |
765 | /// An instruction that doesn't read or write memory may be trivially LICM'd |
766 | /// for example. |
767 | /// |
768 | /// For function calls, this delegates to the alias-analysis specific |
769 | /// call-site mod-ref behavior queries. Otherwise it delegates to the specific |
770 | /// helpers above. |
771 | ModRefInfo getModRefInfo(const Instruction *I, |
772 | const Optional<MemoryLocation> &OptLoc) { |
773 | AAQueryInfo AAQIP; |
774 | return getModRefInfo(I, OptLoc, AAQIP); |
775 | } |
776 | |
777 | /// A convenience wrapper for constructing the memory location. |
778 | ModRefInfo getModRefInfo(const Instruction *I, const Value *P, |
779 | LocationSize Size) { |
780 | return getModRefInfo(I, MemoryLocation(P, Size)); |
781 | } |
782 | |
783 | /// Return information about whether a call and an instruction may refer to |
784 | /// the same memory locations. |
785 | ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call); |
786 | |
787 | /// Return information about whether two call sites may refer to the same set |
788 | /// of memory locations. See the AA documentation for details: |
789 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
790 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2); |
791 | |
792 | /// Return information about whether a particular call site modifies |
793 | /// or reads the specified memory location \p MemLoc before instruction \p I |
794 | /// in a BasicBlock. |
795 | /// Early exits in callCapturesBefore may lead to ModRefInfo::Must not being |
796 | /// set. |
797 | ModRefInfo callCapturesBefore(const Instruction *I, |
798 | const MemoryLocation &MemLoc, DominatorTree *DT); |
799 | |
800 | /// A convenience wrapper to synthesize a memory location. |
801 | ModRefInfo callCapturesBefore(const Instruction *I, const Value *P, |
802 | LocationSize Size, DominatorTree *DT) { |
803 | return callCapturesBefore(I, MemoryLocation(P, Size), DT); |
804 | } |
805 | |
806 | /// @} |
807 | //===--------------------------------------------------------------------===// |
808 | /// \name Higher level methods for querying mod/ref information. |
809 | /// @{ |
810 | |
811 | /// Check if it is possible for execution of the specified basic block to |
812 | /// modify the location Loc. |
813 | bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc); |
814 | |
815 | /// A convenience wrapper synthesizing a memory location. |
816 | bool canBasicBlockModify(const BasicBlock &BB, const Value *P, |
817 | LocationSize Size) { |
818 | return canBasicBlockModify(BB, MemoryLocation(P, Size)); |
819 | } |
820 | |
821 | /// Check if it is possible for the execution of the specified instructions |
822 | /// to mod\ref (according to the mode) the location Loc. |
823 | /// |
824 | /// The instructions to consider are all of the instructions in the range of |
825 | /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. |
826 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
827 | const MemoryLocation &Loc, |
828 | const ModRefInfo Mode); |
829 | |
830 | /// A convenience wrapper synthesizing a memory location. |
831 | bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, |
832 | const Value *Ptr, LocationSize Size, |
833 | const ModRefInfo Mode) { |
834 | return canInstructionRangeModRef(I1, I2, MemoryLocation(Ptr, Size), Mode); |
835 | } |
836 | |
837 | private: |
838 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
839 | AAQueryInfo &AAQI); |
840 | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
841 | bool OrLocal = false); |
842 | ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2, |
843 | AAQueryInfo &AAQIP); |
844 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
845 | AAQueryInfo &AAQI); |
846 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
847 | AAQueryInfo &AAQI); |
848 | ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc, |
849 | AAQueryInfo &AAQI); |
850 | ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc, |
851 | AAQueryInfo &AAQI); |
852 | ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc, |
853 | AAQueryInfo &AAQI); |
854 | ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc, |
855 | AAQueryInfo &AAQI); |
856 | ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX, |
857 | const MemoryLocation &Loc, AAQueryInfo &AAQI); |
858 | ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc, |
859 | AAQueryInfo &AAQI); |
860 | ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc, |
861 | AAQueryInfo &AAQI); |
862 | ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc, |
863 | AAQueryInfo &AAQI); |
864 | ModRefInfo getModRefInfo(const Instruction *I, |
865 | const Optional<MemoryLocation> &OptLoc, |
866 | AAQueryInfo &AAQIP); |
867 | |
868 | class Concept; |
869 | |
870 | template <typename T> class Model; |
871 | |
872 | template <typename T> friend class AAResultBase; |
873 | |
874 | const TargetLibraryInfo &TLI; |
875 | |
876 | std::vector<std::unique_ptr<Concept>> AAs; |
877 | |
878 | std::vector<AnalysisKey *> AADeps; |
879 | |
880 | friend class BatchAAResults; |
881 | }; |
882 | |
883 | /// This class is a wrapper over an AAResults, and it is intended to be used |
884 | /// only when there are no IR changes inbetween queries. BatchAAResults is |
885 | /// reusing the same `AAQueryInfo` to preserve the state across queries, |
886 | /// esentially making AA work in "batch mode". The internal state cannot be |
887 | /// cleared, so to go "out-of-batch-mode", the user must either use AAResults, |
888 | /// or create a new BatchAAResults. |
889 | class BatchAAResults { |
890 | AAResults &AA; |
891 | AAQueryInfo AAQI; |
892 | |
893 | public: |
894 | BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {} |
895 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
896 | return AA.alias(LocA, LocB, AAQI); |
897 | } |
898 | bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) { |
899 | return AA.pointsToConstantMemory(Loc, AAQI, OrLocal); |
900 | } |
901 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) { |
902 | return AA.getModRefInfo(Call, Loc, AAQI); |
903 | } |
904 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2) { |
905 | return AA.getModRefInfo(Call1, Call2, AAQI); |
906 | } |
907 | ModRefInfo getModRefInfo(const Instruction *I, |
908 | const Optional<MemoryLocation> &OptLoc) { |
909 | return AA.getModRefInfo(I, OptLoc, AAQI); |
910 | } |
911 | ModRefInfo getModRefInfo(Instruction *I, const CallBase *Call2) { |
912 | return AA.getModRefInfo(I, Call2, AAQI); |
913 | } |
914 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
915 | return AA.getArgModRefInfo(Call, ArgIdx); |
916 | } |
917 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
918 | return AA.getModRefBehavior(Call); |
919 | } |
920 | bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) { |
921 | return alias(LocA, LocB) == AliasResult::MustAlias; |
922 | } |
923 | bool isMustAlias(const Value *V1, const Value *V2) { |
924 | return alias(MemoryLocation(V1, LocationSize::precise(1)), |
925 | MemoryLocation(V2, LocationSize::precise(1))) == |
926 | AliasResult::MustAlias; |
927 | } |
928 | }; |
929 | |
930 | /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis |
931 | /// pointer or reference. |
932 | using AliasAnalysis = AAResults; |
933 | |
934 | /// A private abstract base class describing the concept of an individual alias |
935 | /// analysis implementation. |
936 | /// |
937 | /// This interface is implemented by any \c Model instantiation. It is also the |
938 | /// interface which a type used to instantiate the model must provide. |
939 | /// |
940 | /// All of these methods model methods by the same name in the \c |
941 | /// AAResults class. Only differences and specifics to how the |
942 | /// implementations are called are documented here. |
943 | class AAResults::Concept { |
944 | public: |
945 | virtual ~Concept() = 0; |
946 | |
947 | /// An update API used internally by the AAResults to provide |
948 | /// a handle back to the top level aggregation. |
949 | virtual void setAAResults(AAResults *NewAAR) = 0; |
950 | |
951 | //===--------------------------------------------------------------------===// |
952 | /// \name Alias Queries |
953 | /// @{ |
954 | |
955 | /// The main low level interface to the alias analysis implementation. |
956 | /// Returns an AliasResult indicating whether the two pointers are aliased to |
957 | /// each other. This is the interface that must be implemented by specific |
958 | /// alias analysis implementations. |
959 | virtual AliasResult alias(const MemoryLocation &LocA, |
960 | const MemoryLocation &LocB, AAQueryInfo &AAQI) = 0; |
961 | |
962 | /// Checks whether the given location points to constant memory, or if |
963 | /// \p OrLocal is true whether it points to a local alloca. |
964 | virtual bool pointsToConstantMemory(const MemoryLocation &Loc, |
965 | AAQueryInfo &AAQI, bool OrLocal) = 0; |
966 | |
967 | /// @} |
968 | //===--------------------------------------------------------------------===// |
969 | /// \name Simple mod/ref information |
970 | /// @{ |
971 | |
972 | /// Get the ModRef info associated with a pointer argument of a callsite. The |
973 | /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note |
974 | /// that these bits do not necessarily account for the overall behavior of |
975 | /// the function, but rather only provide additional per-argument |
976 | /// information. |
977 | virtual ModRefInfo getArgModRefInfo(const CallBase *Call, |
978 | unsigned ArgIdx) = 0; |
979 | |
980 | /// Return the behavior of the given call site. |
981 | virtual FunctionModRefBehavior getModRefBehavior(const CallBase *Call) = 0; |
982 | |
983 | /// Return the behavior when calling the given function. |
984 | virtual FunctionModRefBehavior getModRefBehavior(const Function *F) = 0; |
985 | |
986 | /// getModRefInfo (for call sites) - Return information about whether |
987 | /// a particular call site modifies or reads the specified memory location. |
988 | virtual ModRefInfo getModRefInfo(const CallBase *Call, |
989 | const MemoryLocation &Loc, |
990 | AAQueryInfo &AAQI) = 0; |
991 | |
992 | /// Return information about whether two call sites may refer to the same set |
993 | /// of memory locations. See the AA documentation for details: |
994 | /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo |
995 | virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
996 | AAQueryInfo &AAQI) = 0; |
997 | |
998 | /// @} |
999 | }; |
1000 | |
1001 | /// A private class template which derives from \c Concept and wraps some other |
1002 | /// type. |
1003 | /// |
1004 | /// This models the concept by directly forwarding each interface point to the |
1005 | /// wrapped type which must implement a compatible interface. This provides |
1006 | /// a type erased binding. |
1007 | template <typename AAResultT> class AAResults::Model final : public Concept { |
1008 | AAResultT &Result; |
1009 | |
1010 | public: |
1011 | explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) { |
1012 | Result.setAAResults(&AAR); |
1013 | } |
1014 | ~Model() override = default; |
1015 | |
1016 | void setAAResults(AAResults *NewAAR) override { Result.setAAResults(NewAAR); } |
1017 | |
1018 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
1019 | AAQueryInfo &AAQI) override { |
1020 | return Result.alias(LocA, LocB, AAQI); |
1021 | } |
1022 | |
1023 | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
1024 | bool OrLocal) override { |
1025 | return Result.pointsToConstantMemory(Loc, AAQI, OrLocal); |
1026 | } |
1027 | |
1028 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override { |
1029 | return Result.getArgModRefInfo(Call, ArgIdx); |
1030 | } |
1031 | |
1032 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call) override { |
1033 | return Result.getModRefBehavior(Call); |
1034 | } |
1035 | |
1036 | FunctionModRefBehavior getModRefBehavior(const Function *F) override { |
1037 | return Result.getModRefBehavior(F); |
1038 | } |
1039 | |
1040 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
1041 | AAQueryInfo &AAQI) override { |
1042 | return Result.getModRefInfo(Call, Loc, AAQI); |
1043 | } |
1044 | |
1045 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
1046 | AAQueryInfo &AAQI) override { |
1047 | return Result.getModRefInfo(Call1, Call2, AAQI); |
1048 | } |
1049 | }; |
1050 | |
1051 | /// A CRTP-driven "mixin" base class to help implement the function alias |
1052 | /// analysis results concept. |
1053 | /// |
1054 | /// Because of the nature of many alias analysis implementations, they often |
1055 | /// only implement a subset of the interface. This base class will attempt to |
1056 | /// implement the remaining portions of the interface in terms of simpler forms |
1057 | /// of the interface where possible, and otherwise provide conservatively |
1058 | /// correct fallback implementations. |
1059 | /// |
1060 | /// Implementors of an alias analysis should derive from this CRTP, and then |
1061 | /// override specific methods that they wish to customize. There is no need to |
1062 | /// use virtual anywhere, the CRTP base class does static dispatch to the |
1063 | /// derived type passed into it. |
1064 | template <typename DerivedT> class AAResultBase { |
1065 | // Expose some parts of the interface only to the AAResults::Model |
1066 | // for wrapping. Specifically, this allows the model to call our |
1067 | // setAAResults method without exposing it as a fully public API. |
1068 | friend class AAResults::Model<DerivedT>; |
1069 | |
1070 | /// A pointer to the AAResults object that this AAResult is |
1071 | /// aggregated within. May be null if not aggregated. |
1072 | AAResults *AAR = nullptr; |
1073 | |
1074 | /// Helper to dispatch calls back through the derived type. |
1075 | DerivedT &derived() { return static_cast<DerivedT &>(*this); } |
1076 | |
1077 | /// A setter for the AAResults pointer, which is used to satisfy the |
1078 | /// AAResults::Model contract. |
1079 | void setAAResults(AAResults *NewAAR) { AAR = NewAAR; } |
1080 | |
1081 | protected: |
1082 | /// This proxy class models a common pattern where we delegate to either the |
1083 | /// top-level \c AAResults aggregation if one is registered, or to the |
1084 | /// current result if none are registered. |
1085 | class AAResultsProxy { |
1086 | AAResults *AAR; |
1087 | DerivedT &CurrentResult; |
1088 | |
1089 | public: |
1090 | AAResultsProxy(AAResults *AAR, DerivedT &CurrentResult) |
1091 | : AAR(AAR), CurrentResult(CurrentResult) {} |
1092 | |
1093 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
1094 | AAQueryInfo &AAQI) { |
1095 | return AAR ? AAR->alias(LocA, LocB, AAQI) |
1096 | : CurrentResult.alias(LocA, LocB, AAQI); |
1097 | } |
1098 | |
1099 | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
1100 | bool OrLocal) { |
1101 | return AAR ? AAR->pointsToConstantMemory(Loc, AAQI, OrLocal) |
1102 | : CurrentResult.pointsToConstantMemory(Loc, AAQI, OrLocal); |
1103 | } |
1104 | |
1105 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
1106 | return AAR ? AAR->getArgModRefInfo(Call, ArgIdx) |
1107 | : CurrentResult.getArgModRefInfo(Call, ArgIdx); |
1108 | } |
1109 | |
1110 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
1111 | return AAR ? AAR->getModRefBehavior(Call) |
1112 | : CurrentResult.getModRefBehavior(Call); |
1113 | } |
1114 | |
1115 | FunctionModRefBehavior getModRefBehavior(const Function *F) { |
1116 | return AAR ? AAR->getModRefBehavior(F) : CurrentResult.getModRefBehavior(F); |
1117 | } |
1118 | |
1119 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
1120 | AAQueryInfo &AAQI) { |
1121 | return AAR ? AAR->getModRefInfo(Call, Loc, AAQI) |
1122 | : CurrentResult.getModRefInfo(Call, Loc, AAQI); |
1123 | } |
1124 | |
1125 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
1126 | AAQueryInfo &AAQI) { |
1127 | return AAR ? AAR->getModRefInfo(Call1, Call2, AAQI) |
1128 | : CurrentResult.getModRefInfo(Call1, Call2, AAQI); |
1129 | } |
1130 | }; |
1131 | |
1132 | explicit AAResultBase() = default; |
1133 | |
1134 | // Provide all the copy and move constructors so that derived types aren't |
1135 | // constrained. |
1136 | AAResultBase(const AAResultBase &Arg) {} |
1137 | AAResultBase(AAResultBase &&Arg) {} |
1138 | |
1139 | /// Get a proxy for the best AA result set to query at this time. |
1140 | /// |
1141 | /// When this result is part of a larger aggregation, this will proxy to that |
1142 | /// aggregation. When this result is used in isolation, it will just delegate |
1143 | /// back to the derived class's implementation. |
1144 | /// |
1145 | /// Note that callers of this need to take considerable care to not cause |
1146 | /// performance problems when they use this routine, in the case of a large |
1147 | /// number of alias analyses being aggregated, it can be expensive to walk |
1148 | /// back across the chain. |
1149 | AAResultsProxy getBestAAResults() { return AAResultsProxy(AAR, derived()); } |
1150 | |
1151 | public: |
1152 | AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, |
1153 | AAQueryInfo &AAQI) { |
1154 | return AliasResult::MayAlias; |
1155 | } |
1156 | |
1157 | bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI, |
1158 | bool OrLocal) { |
1159 | return false; |
1160 | } |
1161 | |
1162 | ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) { |
1163 | return ModRefInfo::ModRef; |
1164 | } |
1165 | |
1166 | FunctionModRefBehavior getModRefBehavior(const CallBase *Call) { |
1167 | return FMRB_UnknownModRefBehavior; |
1168 | } |
1169 | |
1170 | FunctionModRefBehavior getModRefBehavior(const Function *F) { |
1171 | return FMRB_UnknownModRefBehavior; |
1172 | } |
1173 | |
1174 | ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, |
1175 | AAQueryInfo &AAQI) { |
1176 | return ModRefInfo::ModRef; |
1177 | } |
1178 | |
1179 | ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2, |
1180 | AAQueryInfo &AAQI) { |
1181 | return ModRefInfo::ModRef; |
1182 | } |
1183 | }; |
1184 | |
1185 | /// Return true if this pointer is returned by a noalias function. |
1186 | bool isNoAliasCall(const Value *V); |
1187 | |
1188 | /// Return true if this pointer refers to a distinct and identifiable object. |
1189 | /// This returns true for: |
1190 | /// Global Variables and Functions (but not Global Aliases) |
1191 | /// Allocas |
1192 | /// ByVal and NoAlias Arguments |
1193 | /// NoAlias returns (e.g. calls to malloc) |
1194 | /// |
1195 | bool isIdentifiedObject(const Value *V); |
1196 | |
1197 | /// Return true if V is umabigously identified at the function-level. |
1198 | /// Different IdentifiedFunctionLocals can't alias. |
1199 | /// Further, an IdentifiedFunctionLocal can not alias with any function |
1200 | /// arguments other than itself, which is not necessarily true for |
1201 | /// IdentifiedObjects. |
1202 | bool isIdentifiedFunctionLocal(const Value *V); |
1203 | |
1204 | /// A manager for alias analyses. |
1205 | /// |
1206 | /// This class can have analyses registered with it and when run, it will run |
1207 | /// all of them and aggregate their results into single AA results interface |
1208 | /// that dispatches across all of the alias analysis results available. |
1209 | /// |
1210 | /// Note that the order in which analyses are registered is very significant. |
1211 | /// That is the order in which the results will be aggregated and queried. |
1212 | /// |
1213 | /// This manager effectively wraps the AnalysisManager for registering alias |
1214 | /// analyses. When you register your alias analysis with this manager, it will |
1215 | /// ensure the analysis itself is registered with its AnalysisManager. |
1216 | /// |
1217 | /// The result of this analysis is only invalidated if one of the particular |
1218 | /// aggregated AA results end up being invalidated. This removes the need to |
1219 | /// explicitly preserve the results of `AAManager`. Note that analyses should no |
1220 | /// longer be registered once the `AAManager` is run. |
1221 | class AAManager : public AnalysisInfoMixin<AAManager> { |
1222 | public: |
1223 | using Result = AAResults; |
1224 | |
1225 | /// Register a specific AA result. |
1226 | template <typename AnalysisT> void registerFunctionAnalysis() { |
1227 | ResultGetters.push_back(&getFunctionAAResultImpl<AnalysisT>); |
1228 | } |
1229 | |
1230 | /// Register a specific AA result. |
1231 | template <typename AnalysisT> void registerModuleAnalysis() { |
1232 | ResultGetters.push_back(&getModuleAAResultImpl<AnalysisT>); |
1233 | } |
1234 | |
1235 | Result run(Function &F, FunctionAnalysisManager &AM); |
1236 | |
1237 | private: |
1238 | friend AnalysisInfoMixin<AAManager>; |
1239 | |
1240 | static AnalysisKey Key; |
1241 | |
1242 | SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM, |
1243 | AAResults &AAResults), |
1244 | 4> ResultGetters; |
1245 | |
1246 | template <typename AnalysisT> |
1247 | static void getFunctionAAResultImpl(Function &F, |
1248 | FunctionAnalysisManager &AM, |
1249 | AAResults &AAResults) { |
1250 | AAResults.addAAResult(AM.template getResult<AnalysisT>(F)); |
1251 | AAResults.addAADependencyID(AnalysisT::ID()); |
1252 | } |
1253 | |
1254 | template <typename AnalysisT> |
1255 | static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM, |
1256 | AAResults &AAResults) { |
1257 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); |
1258 | if (auto *R = |
1259 | MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) { |
1260 | AAResults.addAAResult(*R); |
1261 | MAMProxy |
1262 | .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>(); |
1263 | } |
1264 | } |
1265 | }; |
1266 | |
1267 | /// A wrapper pass to provide the legacy pass manager access to a suitably |
1268 | /// prepared AAResults object. |
1269 | class AAResultsWrapperPass : public FunctionPass { |
1270 | std::unique_ptr<AAResults> AAR; |
1271 | |
1272 | public: |
1273 | static char ID; |
1274 | |
1275 | AAResultsWrapperPass(); |
1276 | |
1277 | AAResults &getAAResults() { return *AAR; } |
1278 | const AAResults &getAAResults() const { return *AAR; } |
1279 | |
1280 | bool runOnFunction(Function &F) override; |
1281 | |
1282 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
1283 | }; |
1284 | |
1285 | /// A wrapper pass for external alias analyses. This just squirrels away the |
1286 | /// callback used to run any analyses and register their results. |
1287 | struct ExternalAAWrapperPass : ImmutablePass { |
1288 | using CallbackT = std::function<void(Pass &, Function &, AAResults &)>; |
1289 | |
1290 | CallbackT CB; |
1291 | |
1292 | static char ID; |
1293 | |
1294 | ExternalAAWrapperPass(); |
1295 | |
1296 | explicit ExternalAAWrapperPass(CallbackT CB); |
1297 | |
1298 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
1299 | AU.setPreservesAll(); |
1300 | } |
1301 | }; |
1302 | |
1303 | FunctionPass *createAAResultsWrapperPass(); |
1304 | |
1305 | /// A wrapper pass around a callback which can be used to populate the |
1306 | /// AAResults in the AAResultsWrapperPass from an external AA. |
1307 | /// |
1308 | /// The callback provided here will be used each time we prepare an AAResults |
1309 | /// object, and will receive a reference to the function wrapper pass, the |
1310 | /// function, and the AAResults object to populate. This should be used when |
1311 | /// setting up a custom pass pipeline to inject a hook into the AA results. |
1312 | ImmutablePass *createExternalAAWrapperPass( |
1313 | std::function<void(Pass &, Function &, AAResults &)> Callback); |
1314 | |
1315 | /// A helper for the legacy pass manager to create a \c AAResults |
1316 | /// object populated to the best of our ability for a particular function when |
1317 | /// inside of a \c ModulePass or a \c CallGraphSCCPass. |
1318 | /// |
1319 | /// If a \c ModulePass or a \c CallGraphSCCPass calls \p |
1320 | /// createLegacyPMAAResults, it also needs to call \p addUsedAAAnalyses in \p |
1321 | /// getAnalysisUsage. |
1322 | AAResults createLegacyPMAAResults(Pass &P, Function &F, BasicAAResult &BAR); |
1323 | |
1324 | /// A helper for the legacy pass manager to populate \p AU to add uses to make |
1325 | /// sure the analyses required by \p createLegacyPMAAResults are available. |
1326 | void getAAResultsAnalysisUsage(AnalysisUsage &AU); |
1327 | |
1328 | } // end namespace llvm |
1329 | |
1330 | #endif // LLVM_ANALYSIS_ALIASANALYSIS_H |
1331 | |