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
52namespace llvm {
53
54class AnalysisUsage;
55class AtomicCmpXchgInst;
56class BasicAAResult;
57class BasicBlock;
58class CatchPadInst;
59class CatchReturnInst;
60class DominatorTree;
61class FenceInst;
62class Function;
63class InvokeInst;
64class PreservedAnalyses;
65class TargetLibraryInfo;
66class 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.
81class AliasResult {
82private:
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
92public:
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
136static_assert(sizeof(AliasResult) == 4,
137 "AliasResult size is intended to be 4 bytes!");
138
139/// << operator for AliasResult.
140raw_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.
148enum 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
185LLVM_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}
189LLVM_NODISCARD inline bool isModOrRefSet(const ModRefInfo MRI) {
190 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustModRef);
191}
192LLVM_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}
196LLVM_NODISCARD inline bool isModSet(const ModRefInfo MRI) {
197 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustMod);
198}
199LLVM_NODISCARD inline bool isRefSet(const ModRefInfo MRI) {
200 return static_cast<int>(MRI) & static_cast<int>(ModRefInfo::MustRef);
201}
202LLVM_NODISCARD inline bool isMustSet(const ModRefInfo MRI) {
203 return !(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::NoModRef));
204}
205
206LLVM_NODISCARD inline ModRefInfo setMod(const ModRefInfo MRI) {
207 return ModRefInfo(static_cast<int>(MRI) |
208 static_cast<int>(ModRefInfo::MustMod));
209}
210LLVM_NODISCARD inline ModRefInfo setRef(const ModRefInfo MRI) {
211 return ModRefInfo(static_cast<int>(MRI) |
212 static_cast<int>(ModRefInfo::MustRef));
213}
214LLVM_NODISCARD inline ModRefInfo setMust(const ModRefInfo MRI) {
215 return ModRefInfo(static_cast<int>(MRI) &
216 static_cast<int>(ModRefInfo::MustModRef));
217}
218LLVM_NODISCARD inline ModRefInfo setModAndRef(const ModRefInfo MRI) {
219 return ModRefInfo(static_cast<int>(MRI) |
220 static_cast<int>(ModRefInfo::MustModRef));
221}
222LLVM_NODISCARD inline ModRefInfo clearMod(const ModRefInfo MRI) {
223 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Ref));
224}
225LLVM_NODISCARD inline ModRefInfo clearRef(const ModRefInfo MRI) {
226 return ModRefInfo(static_cast<int>(MRI) & static_cast<int>(ModRefInfo::Mod));
227}
228LLVM_NODISCARD inline ModRefInfo clearMust(const ModRefInfo MRI) {
229 return ModRefInfo(static_cast<int>(MRI) |
230 static_cast<int>(ModRefInfo::NoModRef));
231}
232LLVM_NODISCARD inline ModRefInfo unionModRef(const ModRefInfo MRI1,
233 const ModRefInfo MRI2) {
234 return ModRefInfo(static_cast<int>(MRI1) | static_cast<int>(MRI2));
235}
236LLVM_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.
246enum 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.
262enum 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.
376LLVM_NODISCARD inline ModRefInfo
377createModRefInfo(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.
383struct AACacheLoc {
384 const Value *Ptr;
385 LocationSize Size;
386};
387
388template <> 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.
414class AAQueryInfo {
415public:
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
454class BatchAAResults;
455
456class AAResults {
457public:
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
837private:
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.
889class BatchAAResults {
890 AAResults &AA;
891 AAQueryInfo AAQI;
892
893public:
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.
932using 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.
943class AAResults::Concept {
944public:
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.
1007template <typename AAResultT> class AAResults::Model final : public Concept {
1008 AAResultT &Result;
1009
1010public:
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.
1064template <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
1081protected:
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
1151public:
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.
1186bool 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///
1195bool 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.
1202bool 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.
1221class AAManager : public AnalysisInfoMixin<AAManager> {
1222public:
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
1237private:
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.
1269class AAResultsWrapperPass : public FunctionPass {
1270 std::unique_ptr<AAResults> AAR;
1271
1272public:
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.
1287struct 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
1303FunctionPass *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.
1312ImmutablePass *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.
1322AAResults 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.
1326void getAAResultsAnalysisUsage(AnalysisUsage &AU);
1327
1328} // end namespace llvm
1329
1330#endif // LLVM_ANALYSIS_ALIASANALYSIS_H
1331