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/Sequence.h"
42#include "llvm/ADT/SmallVector.h"
43#include "llvm/Analysis/MemoryLocation.h"
44#include "llvm/IR/PassManager.h"
45#include "llvm/Pass.h"
46#include "llvm/Support/ModRef.h"
47#include <cstdint>
48#include <functional>
49#include <memory>
50#include <optional>
51#include <vector>
52
53namespace llvm {
54
55class AnalysisUsage;
56class AtomicCmpXchgInst;
57class BasicBlock;
58class CatchPadInst;
59class CatchReturnInst;
60class DominatorTree;
61class FenceInst;
62class Function;
63class LoopInfo;
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 bool operator==(const AliasResult &Other) const {
118 return Alias == Other.Alias && HasOffset == Other.HasOffset &&
119 Offset == Other.Offset;
120 }
121 bool operator!=(const AliasResult &Other) const { return !(*this == Other); }
122
123 bool operator==(Kind K) const { return Alias == K; }
124 bool operator!=(Kind K) const { return !(*this == K); }
125
126 constexpr bool hasOffset() const { return HasOffset; }
127 constexpr int32_t getOffset() const {
128 assert(HasOffset && "No offset!");
129 return Offset;
130 }
131 void setOffset(int32_t NewOffset) {
132 if (isInt<OffsetBits>(x: NewOffset)) {
133 HasOffset = true;
134 Offset = NewOffset;
135 }
136 }
137
138 /// Helper for processing AliasResult for swapped memory location pairs.
139 void swap(bool DoSwap = true) {
140 if (DoSwap && hasOffset())
141 setOffset(-getOffset());
142 }
143};
144
145static_assert(sizeof(AliasResult) == 4,
146 "AliasResult size is intended to be 4 bytes!");
147
148/// << operator for AliasResult.
149raw_ostream &operator<<(raw_ostream &OS, AliasResult AR);
150
151/// Virtual base class for providers of capture information.
152struct CaptureInfo {
153 virtual ~CaptureInfo() = 0;
154
155 /// Check whether Object is not captured before instruction I. If OrAt is
156 /// true, captures by instruction I itself are also considered.
157 ///
158 /// If I is nullptr, then captures at any point will be considered.
159 virtual bool isNotCapturedBefore(const Value *Object, const Instruction *I,
160 bool OrAt) = 0;
161};
162
163/// Context-free CaptureInfo provider, which computes and caches whether an
164/// object is captured in the function at all, but does not distinguish whether
165/// it was captured before or after the context instruction.
166class SimpleCaptureInfo final : public CaptureInfo {
167 SmallDenseMap<const Value *, bool, 8> IsCapturedCache;
168
169public:
170 bool isNotCapturedBefore(const Value *Object, const Instruction *I,
171 bool OrAt) override;
172};
173
174/// Context-sensitive CaptureInfo provider, which computes and caches the
175/// earliest common dominator closure of all captures. It provides a good
176/// approximation to a precise "captures before" analysis.
177class EarliestEscapeInfo final : public CaptureInfo {
178 DominatorTree &DT;
179 const LoopInfo *LI;
180
181 /// Map from identified local object to an instruction before which it does
182 /// not escape, or nullptr if it never escapes. The "earliest" instruction
183 /// may be a conservative approximation, e.g. the first instruction in the
184 /// function is always a legal choice.
185 DenseMap<const Value *, Instruction *> EarliestEscapes;
186
187 /// Reverse map from instruction to the objects it is the earliest escape for.
188 /// This is used for cache invalidation purposes.
189 DenseMap<Instruction *, TinyPtrVector<const Value *>> Inst2Obj;
190
191public:
192 EarliestEscapeInfo(DominatorTree &DT, const LoopInfo *LI = nullptr)
193 : DT(DT), LI(LI) {}
194
195 bool isNotCapturedBefore(const Value *Object, const Instruction *I,
196 bool OrAt) override;
197
198 void removeInstruction(Instruction *I);
199};
200
201/// Cache key for BasicAA results. It only includes the pointer and size from
202/// MemoryLocation, as BasicAA is AATags independent. Additionally, it includes
203/// the value of MayBeCrossIteration, which may affect BasicAA results.
204struct AACacheLoc {
205 using PtrTy = PointerIntPair<const Value *, 1, bool>;
206 PtrTy Ptr;
207 LocationSize Size;
208
209 AACacheLoc(PtrTy Ptr, LocationSize Size) : Ptr(Ptr), Size(Size) {}
210 AACacheLoc(const Value *Ptr, LocationSize Size, bool MayBeCrossIteration)
211 : Ptr(Ptr, MayBeCrossIteration), Size(Size) {}
212};
213
214template <> struct DenseMapInfo<AACacheLoc> {
215 static inline AACacheLoc getEmptyKey() {
216 return {DenseMapInfo<AACacheLoc::PtrTy>::getEmptyKey(),
217 DenseMapInfo<LocationSize>::getEmptyKey()};
218 }
219 static inline AACacheLoc getTombstoneKey() {
220 return {DenseMapInfo<AACacheLoc::PtrTy>::getTombstoneKey(),
221 DenseMapInfo<LocationSize>::getTombstoneKey()};
222 }
223 static unsigned getHashValue(const AACacheLoc &Val) {
224 return DenseMapInfo<AACacheLoc::PtrTy>::getHashValue(V: Val.Ptr) ^
225 DenseMapInfo<LocationSize>::getHashValue(Val: Val.Size);
226 }
227 static bool isEqual(const AACacheLoc &LHS, const AACacheLoc &RHS) {
228 return LHS.Ptr == RHS.Ptr && LHS.Size == RHS.Size;
229 }
230};
231
232class AAResults;
233
234/// This class stores info we want to provide to or retain within an alias
235/// query. By default, the root query is stateless and starts with a freshly
236/// constructed info object. Specific alias analyses can use this query info to
237/// store per-query state that is important for recursive or nested queries to
238/// avoid recomputing. To enable preserving this state across multiple queries
239/// where safe (due to the IR not changing), use a `BatchAAResults` wrapper.
240/// The information stored in an `AAQueryInfo` is currently limitted to the
241/// caches used by BasicAA, but can further be extended to fit other AA needs.
242class AAQueryInfo {
243public:
244 using LocPair = std::pair<AACacheLoc, AACacheLoc>;
245 struct CacheEntry {
246 AliasResult Result;
247 /// Number of times a NoAlias assumption has been used.
248 /// 0 for assumptions that have not been used, -1 for definitive results.
249 int NumAssumptionUses;
250 /// Whether this is a definitive (non-assumption) result.
251 bool isDefinitive() const { return NumAssumptionUses < 0; }
252 };
253
254 // Alias analysis result aggregration using which this query is performed.
255 // Can be used to perform recursive queries.
256 AAResults &AAR;
257
258 using AliasCacheT = SmallDenseMap<LocPair, CacheEntry, 8>;
259 AliasCacheT AliasCache;
260
261 CaptureInfo *CI;
262
263 /// Query depth used to distinguish recursive queries.
264 unsigned Depth = 0;
265
266 /// How many active NoAlias assumption uses there are.
267 int NumAssumptionUses = 0;
268
269 /// Location pairs for which an assumption based result is currently stored.
270 /// Used to remove all potentially incorrect results from the cache if an
271 /// assumption is disproven.
272 SmallVector<AAQueryInfo::LocPair, 4> AssumptionBasedResults;
273
274 /// Tracks whether the accesses may be on different cycle iterations.
275 ///
276 /// When interpret "Value" pointer equality as value equality we need to make
277 /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
278 /// come from different "iterations" of a cycle and see different values for
279 /// the same "Value" pointer.
280 ///
281 /// The following example shows the problem:
282 /// %p = phi(%alloca1, %addr2)
283 /// %l = load %ptr
284 /// %addr1 = gep, %alloca2, 0, %l
285 /// %addr2 = gep %alloca2, 0, (%l + 1)
286 /// alias(%p, %addr1) -> MayAlias !
287 /// store %l, ...
288 bool MayBeCrossIteration = false;
289
290 /// Whether alias analysis is allowed to use the dominator tree, for use by
291 /// passes that lazily update the DT while performing AA queries.
292 bool UseDominatorTree = true;
293
294 AAQueryInfo(AAResults &AAR, CaptureInfo *CI) : AAR(AAR), CI(CI) {}
295};
296
297/// AAQueryInfo that uses SimpleCaptureInfo.
298class SimpleAAQueryInfo : public AAQueryInfo {
299 SimpleCaptureInfo CI;
300
301public:
302 SimpleAAQueryInfo(AAResults &AAR) : AAQueryInfo(AAR, &CI) {}
303};
304
305class BatchAAResults;
306
307class AAResults {
308public:
309 // Make these results default constructable and movable. We have to spell
310 // these out because MSVC won't synthesize them.
311 AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
312 AAResults(AAResults &&Arg);
313 ~AAResults();
314
315 /// Register a specific AA result.
316 template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
317 // FIXME: We should use a much lighter weight system than the usual
318 // polymorphic pattern because we don't own AAResult. It should
319 // ideally involve two pointers and no separate allocation.
320 AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
321 }
322
323 /// Register a function analysis ID that the results aggregation depends on.
324 ///
325 /// This is used in the new pass manager to implement the invalidation logic
326 /// where we must invalidate the results aggregation if any of our component
327 /// analyses become invalid.
328 void addAADependencyID(AnalysisKey *ID) { AADeps.push_back(x: ID); }
329
330 /// Handle invalidation events in the new pass manager.
331 ///
332 /// The aggregation is invalidated if any of the underlying analyses is
333 /// invalidated.
334 bool invalidate(Function &F, const PreservedAnalyses &PA,
335 FunctionAnalysisManager::Invalidator &Inv);
336
337 //===--------------------------------------------------------------------===//
338 /// \name Alias Queries
339 /// @{
340
341 /// The main low level interface to the alias analysis implementation.
342 /// Returns an AliasResult indicating whether the two pointers are aliased to
343 /// each other. This is the interface that must be implemented by specific
344 /// alias analysis implementations.
345 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
346
347 /// A convenience wrapper around the primary \c alias interface.
348 AliasResult alias(const Value *V1, LocationSize V1Size, const Value *V2,
349 LocationSize V2Size) {
350 return alias(LocA: MemoryLocation(V1, V1Size), LocB: MemoryLocation(V2, V2Size));
351 }
352
353 /// A convenience wrapper around the primary \c alias interface.
354 AliasResult alias(const Value *V1, const Value *V2) {
355 return alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: V1),
356 LocB: MemoryLocation::getBeforeOrAfter(Ptr: V2));
357 }
358
359 /// A trivial helper function to check to see if the specified pointers are
360 /// no-alias.
361 bool isNoAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
362 return alias(LocA, LocB) == AliasResult::NoAlias;
363 }
364
365 /// A convenience wrapper around the \c isNoAlias helper interface.
366 bool isNoAlias(const Value *V1, LocationSize V1Size, const Value *V2,
367 LocationSize V2Size) {
368 return isNoAlias(LocA: MemoryLocation(V1, V1Size), LocB: MemoryLocation(V2, V2Size));
369 }
370
371 /// A convenience wrapper around the \c isNoAlias helper interface.
372 bool isNoAlias(const Value *V1, const Value *V2) {
373 return isNoAlias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: V1),
374 LocB: MemoryLocation::getBeforeOrAfter(Ptr: V2));
375 }
376
377 /// A trivial helper function to check to see if the specified pointers are
378 /// must-alias.
379 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
380 return alias(LocA, LocB) == AliasResult::MustAlias;
381 }
382
383 /// A convenience wrapper around the \c isMustAlias helper interface.
384 bool isMustAlias(const Value *V1, const Value *V2) {
385 return alias(V1, V1Size: LocationSize::precise(Value: 1), V2, V2Size: LocationSize::precise(Value: 1)) ==
386 AliasResult::MustAlias;
387 }
388
389 /// Checks whether the given location points to constant memory, or if
390 /// \p OrLocal is true whether it points to a local alloca.
391 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
392 return isNoModRef(MRI: getModRefInfoMask(Loc, IgnoreLocals: OrLocal));
393 }
394
395 /// A convenience wrapper around the primary \c pointsToConstantMemory
396 /// interface.
397 bool pointsToConstantMemory(const Value *P, bool OrLocal = false) {
398 return pointsToConstantMemory(Loc: MemoryLocation::getBeforeOrAfter(Ptr: P), OrLocal);
399 }
400
401 /// @}
402 //===--------------------------------------------------------------------===//
403 /// \name Simple mod/ref information
404 /// @{
405
406 /// Returns a bitmask that should be unconditionally applied to the ModRef
407 /// info of a memory location. This allows us to eliminate Mod and/or Ref
408 /// from the ModRef info based on the knowledge that the memory location
409 /// points to constant and/or locally-invariant memory.
410 ///
411 /// If IgnoreLocals is true, then this method returns NoModRef for memory
412 /// that points to a local alloca.
413 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc,
414 bool IgnoreLocals = false);
415
416 /// A convenience wrapper around the primary \c getModRefInfoMask
417 /// interface.
418 ModRefInfo getModRefInfoMask(const Value *P, bool IgnoreLocals = false) {
419 return getModRefInfoMask(Loc: MemoryLocation::getBeforeOrAfter(Ptr: P), IgnoreLocals);
420 }
421
422 /// Get the ModRef info associated with a pointer argument of a call. The
423 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
424 /// that these bits do not necessarily account for the overall behavior of
425 /// the function, but rather only provide additional per-argument
426 /// information.
427 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx);
428
429 /// Return the behavior of the given call site.
430 MemoryEffects getMemoryEffects(const CallBase *Call);
431
432 /// Return the behavior when calling the given function.
433 MemoryEffects getMemoryEffects(const Function *F);
434
435 /// Checks if the specified call is known to never read or write memory.
436 ///
437 /// Note that if the call only reads from known-constant memory, it is also
438 /// legal to return true. Also, calls that unwind the stack are legal for
439 /// this predicate.
440 ///
441 /// Many optimizations (such as CSE and LICM) can be performed on such calls
442 /// without worrying about aliasing properties, and many calls have this
443 /// property (e.g. calls to 'sin' and 'cos').
444 ///
445 /// This property corresponds to the GCC 'const' attribute.
446 bool doesNotAccessMemory(const CallBase *Call) {
447 return getMemoryEffects(Call).doesNotAccessMemory();
448 }
449
450 /// Checks if the specified function is known to never read or write memory.
451 ///
452 /// Note that if the function only reads from known-constant memory, it is
453 /// also legal to return true. Also, function that unwind the stack are legal
454 /// for this predicate.
455 ///
456 /// Many optimizations (such as CSE and LICM) can be performed on such calls
457 /// to such functions without worrying about aliasing properties, and many
458 /// functions have this property (e.g. 'sin' and 'cos').
459 ///
460 /// This property corresponds to the GCC 'const' attribute.
461 bool doesNotAccessMemory(const Function *F) {
462 return getMemoryEffects(F).doesNotAccessMemory();
463 }
464
465 /// Checks if the specified call is known to only read from non-volatile
466 /// memory (or not access memory at all).
467 ///
468 /// Calls that unwind the stack are legal for this predicate.
469 ///
470 /// This property allows many common optimizations to be performed in the
471 /// absence of interfering store instructions, such as CSE of strlen calls.
472 ///
473 /// This property corresponds to the GCC 'pure' attribute.
474 bool onlyReadsMemory(const CallBase *Call) {
475 return getMemoryEffects(Call).onlyReadsMemory();
476 }
477
478 /// Checks if the specified function is known to only read from non-volatile
479 /// memory (or not access memory at all).
480 ///
481 /// Functions that unwind the stack are legal for this predicate.
482 ///
483 /// This property allows many common optimizations to be performed in the
484 /// absence of interfering store instructions, such as CSE of strlen calls.
485 ///
486 /// This property corresponds to the GCC 'pure' attribute.
487 bool onlyReadsMemory(const Function *F) {
488 return getMemoryEffects(F).onlyReadsMemory();
489 }
490
491 /// Check whether or not an instruction may read or write the optionally
492 /// specified memory location.
493 ///
494 ///
495 /// An instruction that doesn't read or write memory may be trivially LICM'd
496 /// for example.
497 ///
498 /// For function calls, this delegates to the alias-analysis specific
499 /// call-site mod-ref behavior queries. Otherwise it delegates to the specific
500 /// helpers above.
501 ModRefInfo getModRefInfo(const Instruction *I,
502 const std::optional<MemoryLocation> &OptLoc) {
503 SimpleAAQueryInfo AAQIP(*this);
504 return getModRefInfo(I, OptLoc, AAQIP);
505 }
506
507 /// A convenience wrapper for constructing the memory location.
508 ModRefInfo getModRefInfo(const Instruction *I, const Value *P,
509 LocationSize Size) {
510 return getModRefInfo(I, OptLoc: MemoryLocation(P, Size));
511 }
512
513 /// Return information about whether a call and an instruction may refer to
514 /// the same memory locations.
515 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call);
516
517 /// Return information about whether a particular call site modifies
518 /// or reads the specified memory location \p MemLoc before instruction \p I
519 /// in a BasicBlock.
520 ModRefInfo callCapturesBefore(const Instruction *I,
521 const MemoryLocation &MemLoc,
522 DominatorTree *DT) {
523 SimpleAAQueryInfo AAQIP(*this);
524 return callCapturesBefore(I, MemLoc, DT, AAQIP);
525 }
526
527 /// A convenience wrapper to synthesize a memory location.
528 ModRefInfo callCapturesBefore(const Instruction *I, const Value *P,
529 LocationSize Size, DominatorTree *DT) {
530 return callCapturesBefore(I, MemLoc: MemoryLocation(P, Size), DT);
531 }
532
533 /// @}
534 //===--------------------------------------------------------------------===//
535 /// \name Higher level methods for querying mod/ref information.
536 /// @{
537
538 /// Check if it is possible for execution of the specified basic block to
539 /// modify the location Loc.
540 bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc);
541
542 /// A convenience wrapper synthesizing a memory location.
543 bool canBasicBlockModify(const BasicBlock &BB, const Value *P,
544 LocationSize Size) {
545 return canBasicBlockModify(BB, Loc: MemoryLocation(P, Size));
546 }
547
548 /// Check if it is possible for the execution of the specified instructions
549 /// to mod\ref (according to the mode) the location Loc.
550 ///
551 /// The instructions to consider are all of the instructions in the range of
552 /// [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block.
553 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
554 const MemoryLocation &Loc,
555 const ModRefInfo Mode);
556
557 /// A convenience wrapper synthesizing a memory location.
558 bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2,
559 const Value *Ptr, LocationSize Size,
560 const ModRefInfo Mode) {
561 return canInstructionRangeModRef(I1, I2, Loc: MemoryLocation(Ptr, Size), Mode);
562 }
563
564 // CtxI can be nullptr, in which case the query is whether or not the aliasing
565 // relationship holds through the entire function.
566 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
567 AAQueryInfo &AAQI, const Instruction *CtxI = nullptr);
568
569 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
570 bool IgnoreLocals = false);
571 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2,
572 AAQueryInfo &AAQIP);
573 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
574 AAQueryInfo &AAQI);
575 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
576 AAQueryInfo &AAQI);
577 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
578 AAQueryInfo &AAQI);
579 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
580 AAQueryInfo &AAQI);
581 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
582 AAQueryInfo &AAQI);
583 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
584 AAQueryInfo &AAQI);
585 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
586 const MemoryLocation &Loc, AAQueryInfo &AAQI);
587 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
588 AAQueryInfo &AAQI);
589 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
590 AAQueryInfo &AAQI);
591 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
592 AAQueryInfo &AAQI);
593 ModRefInfo getModRefInfo(const Instruction *I,
594 const std::optional<MemoryLocation> &OptLoc,
595 AAQueryInfo &AAQIP);
596 ModRefInfo callCapturesBefore(const Instruction *I,
597 const MemoryLocation &MemLoc, DominatorTree *DT,
598 AAQueryInfo &AAQIP);
599 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI);
600
601private:
602 class Concept;
603
604 template <typename T> class Model;
605
606 friend class AAResultBase;
607
608 const TargetLibraryInfo &TLI;
609
610 std::vector<std::unique_ptr<Concept>> AAs;
611
612 std::vector<AnalysisKey *> AADeps;
613
614 friend class BatchAAResults;
615};
616
617/// This class is a wrapper over an AAResults, and it is intended to be used
618/// only when there are no IR changes inbetween queries. BatchAAResults is
619/// reusing the same `AAQueryInfo` to preserve the state across queries,
620/// esentially making AA work in "batch mode". The internal state cannot be
621/// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
622/// or create a new BatchAAResults.
623class BatchAAResults {
624 AAResults &AA;
625 AAQueryInfo AAQI;
626 SimpleCaptureInfo SimpleCI;
627
628public:
629 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {}
630 BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {}
631
632 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
633 return AA.alias(LocA, LocB, AAQI);
634 }
635 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
636 return isNoModRef(MRI: AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals: OrLocal));
637 }
638 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc,
639 bool IgnoreLocals = false) {
640 return AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals);
641 }
642 ModRefInfo getModRefInfo(const Instruction *I,
643 const std::optional<MemoryLocation> &OptLoc) {
644 return AA.getModRefInfo(I, OptLoc, AAQIP&: AAQI);
645 }
646 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2) {
647 return AA.getModRefInfo(I, Call2, AAQIP&: AAQI);
648 }
649 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
650 return AA.getArgModRefInfo(Call, ArgIdx);
651 }
652 MemoryEffects getMemoryEffects(const CallBase *Call) {
653 return AA.getMemoryEffects(Call, AAQI);
654 }
655 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
656 return alias(LocA, LocB) == AliasResult::MustAlias;
657 }
658 bool isMustAlias(const Value *V1, const Value *V2) {
659 return alias(LocA: MemoryLocation(V1, LocationSize::precise(Value: 1)),
660 LocB: MemoryLocation(V2, LocationSize::precise(Value: 1))) ==
661 AliasResult::MustAlias;
662 }
663 ModRefInfo callCapturesBefore(const Instruction *I,
664 const MemoryLocation &MemLoc,
665 DominatorTree *DT) {
666 return AA.callCapturesBefore(I, MemLoc, DT, AAQIP&: AAQI);
667 }
668
669 /// Assume that values may come from different cycle iterations.
670 void enableCrossIterationMode() {
671 AAQI.MayBeCrossIteration = true;
672 }
673
674 /// Disable the use of the dominator tree during alias analysis queries.
675 void disableDominatorTree() { AAQI.UseDominatorTree = false; }
676};
677
678/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
679/// pointer or reference.
680using AliasAnalysis = AAResults;
681
682/// A private abstract base class describing the concept of an individual alias
683/// analysis implementation.
684///
685/// This interface is implemented by any \c Model instantiation. It is also the
686/// interface which a type used to instantiate the model must provide.
687///
688/// All of these methods model methods by the same name in the \c
689/// AAResults class. Only differences and specifics to how the
690/// implementations are called are documented here.
691class AAResults::Concept {
692public:
693 virtual ~Concept() = 0;
694
695 //===--------------------------------------------------------------------===//
696 /// \name Alias Queries
697 /// @{
698
699 /// The main low level interface to the alias analysis implementation.
700 /// Returns an AliasResult indicating whether the two pointers are aliased to
701 /// each other. This is the interface that must be implemented by specific
702 /// alias analysis implementations.
703 virtual AliasResult alias(const MemoryLocation &LocA,
704 const MemoryLocation &LocB, AAQueryInfo &AAQI,
705 const Instruction *CtxI) = 0;
706
707 /// @}
708 //===--------------------------------------------------------------------===//
709 /// \name Simple mod/ref information
710 /// @{
711
712 /// Returns a bitmask that should be unconditionally applied to the ModRef
713 /// info of a memory location. This allows us to eliminate Mod and/or Ref from
714 /// the ModRef info based on the knowledge that the memory location points to
715 /// constant and/or locally-invariant memory.
716 virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc,
717 AAQueryInfo &AAQI,
718 bool IgnoreLocals) = 0;
719
720 /// Get the ModRef info associated with a pointer argument of a callsite. The
721 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
722 /// that these bits do not necessarily account for the overall behavior of
723 /// the function, but rather only provide additional per-argument
724 /// information.
725 virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
726 unsigned ArgIdx) = 0;
727
728 /// Return the behavior of the given call site.
729 virtual MemoryEffects getMemoryEffects(const CallBase *Call,
730 AAQueryInfo &AAQI) = 0;
731
732 /// Return the behavior when calling the given function.
733 virtual MemoryEffects getMemoryEffects(const Function *F) = 0;
734
735 /// getModRefInfo (for call sites) - Return information about whether
736 /// a particular call site modifies or reads the specified memory location.
737 virtual ModRefInfo getModRefInfo(const CallBase *Call,
738 const MemoryLocation &Loc,
739 AAQueryInfo &AAQI) = 0;
740
741 /// Return information about whether two call sites may refer to the same set
742 /// of memory locations. See the AA documentation for details:
743 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
744 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
745 AAQueryInfo &AAQI) = 0;
746
747 /// @}
748};
749
750/// A private class template which derives from \c Concept and wraps some other
751/// type.
752///
753/// This models the concept by directly forwarding each interface point to the
754/// wrapped type which must implement a compatible interface. This provides
755/// a type erased binding.
756template <typename AAResultT> class AAResults::Model final : public Concept {
757 AAResultT &Result;
758
759public:
760 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {}
761 ~Model() override = default;
762
763 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
764 AAQueryInfo &AAQI, const Instruction *CtxI) override {
765 return Result.alias(LocA, LocB, AAQI, CtxI);
766 }
767
768 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
769 bool IgnoreLocals) override {
770 return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals);
771 }
772
773 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
774 return Result.getArgModRefInfo(Call, ArgIdx);
775 }
776
777 MemoryEffects getMemoryEffects(const CallBase *Call,
778 AAQueryInfo &AAQI) override {
779 return Result.getMemoryEffects(Call, AAQI);
780 }
781
782 MemoryEffects getMemoryEffects(const Function *F) override {
783 return Result.getMemoryEffects(F);
784 }
785
786 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
787 AAQueryInfo &AAQI) override {
788 return Result.getModRefInfo(Call, Loc, AAQI);
789 }
790
791 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
792 AAQueryInfo &AAQI) override {
793 return Result.getModRefInfo(Call1, Call2, AAQI);
794 }
795};
796
797/// A base class to help implement the function alias analysis results concept.
798///
799/// Because of the nature of many alias analysis implementations, they often
800/// only implement a subset of the interface. This base class will attempt to
801/// implement the remaining portions of the interface in terms of simpler forms
802/// of the interface where possible, and otherwise provide conservatively
803/// correct fallback implementations.
804///
805/// Implementors of an alias analysis should derive from this class, and then
806/// override specific methods that they wish to customize. There is no need to
807/// use virtual anywhere.
808class AAResultBase {
809protected:
810 explicit AAResultBase() = default;
811
812 // Provide all the copy and move constructors so that derived types aren't
813 // constrained.
814 AAResultBase(const AAResultBase &Arg) {}
815 AAResultBase(AAResultBase &&Arg) {}
816
817public:
818 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
819 AAQueryInfo &AAQI, const Instruction *I) {
820 return AliasResult::MayAlias;
821 }
822
823 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
824 bool IgnoreLocals) {
825 return ModRefInfo::ModRef;
826 }
827
828 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
829 return ModRefInfo::ModRef;
830 }
831
832 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) {
833 return MemoryEffects::unknown();
834 }
835
836 MemoryEffects getMemoryEffects(const Function *F) {
837 return MemoryEffects::unknown();
838 }
839
840 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
841 AAQueryInfo &AAQI) {
842 return ModRefInfo::ModRef;
843 }
844
845 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
846 AAQueryInfo &AAQI) {
847 return ModRefInfo::ModRef;
848 }
849};
850
851/// Return true if this pointer is returned by a noalias function.
852bool isNoAliasCall(const Value *V);
853
854/// Return true if this pointer refers to a distinct and identifiable object.
855/// This returns true for:
856/// Global Variables and Functions (but not Global Aliases)
857/// Allocas
858/// ByVal and NoAlias Arguments
859/// NoAlias returns (e.g. calls to malloc)
860///
861bool isIdentifiedObject(const Value *V);
862
863/// Return true if V is umabigously identified at the function-level.
864/// Different IdentifiedFunctionLocals can't alias.
865/// Further, an IdentifiedFunctionLocal can not alias with any function
866/// arguments other than itself, which is not necessarily true for
867/// IdentifiedObjects.
868bool isIdentifiedFunctionLocal(const Value *V);
869
870/// Returns true if the pointer is one which would have been considered an
871/// escape by isNonEscapingLocalObject.
872bool isEscapeSource(const Value *V);
873
874/// Return true if Object memory is not visible after an unwind, in the sense
875/// that program semantics cannot depend on Object containing any particular
876/// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set
877/// to true, then the memory is only not visible if the object has not been
878/// captured prior to the unwind. Otherwise it is not visible even if captured.
879bool isNotVisibleOnUnwind(const Value *Object,
880 bool &RequiresNoCaptureBeforeUnwind);
881
882/// Return true if the Object is writable, in the sense that any location based
883/// on this pointer that can be loaded can also be stored to without trapping.
884/// Additionally, at the point Object is declared, stores can be introduced
885/// without data races. At later points, this is only the case if the pointer
886/// can not escape to a different thread.
887///
888/// If ExplicitlyDereferenceableOnly is set to true, this property only holds
889/// for the part of Object that is explicitly marked as dereferenceable, e.g.
890/// using the dereferenceable(N) attribute. It does not necessarily hold for
891/// parts that are only known to be dereferenceable due to the presence of
892/// loads.
893bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly);
894
895/// A manager for alias analyses.
896///
897/// This class can have analyses registered with it and when run, it will run
898/// all of them and aggregate their results into single AA results interface
899/// that dispatches across all of the alias analysis results available.
900///
901/// Note that the order in which analyses are registered is very significant.
902/// That is the order in which the results will be aggregated and queried.
903///
904/// This manager effectively wraps the AnalysisManager for registering alias
905/// analyses. When you register your alias analysis with this manager, it will
906/// ensure the analysis itself is registered with its AnalysisManager.
907///
908/// The result of this analysis is only invalidated if one of the particular
909/// aggregated AA results end up being invalidated. This removes the need to
910/// explicitly preserve the results of `AAManager`. Note that analyses should no
911/// longer be registered once the `AAManager` is run.
912class AAManager : public AnalysisInfoMixin<AAManager> {
913public:
914 using Result = AAResults;
915
916 /// Register a specific AA result.
917 template <typename AnalysisT> void registerFunctionAnalysis() {
918 ResultGetters.push_back(Elt: &getFunctionAAResultImpl<AnalysisT>);
919 }
920
921 /// Register a specific AA result.
922 template <typename AnalysisT> void registerModuleAnalysis() {
923 ResultGetters.push_back(Elt: &getModuleAAResultImpl<AnalysisT>);
924 }
925
926 Result run(Function &F, FunctionAnalysisManager &AM);
927
928private:
929 friend AnalysisInfoMixin<AAManager>;
930
931 static AnalysisKey Key;
932
933 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
934 AAResults &AAResults),
935 4> ResultGetters;
936
937 template <typename AnalysisT>
938 static void getFunctionAAResultImpl(Function &F,
939 FunctionAnalysisManager &AM,
940 AAResults &AAResults) {
941 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
942 AAResults.addAADependencyID(ID: AnalysisT::ID());
943 }
944
945 template <typename AnalysisT>
946 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
947 AAResults &AAResults) {
948 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
949 if (auto *R =
950 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) {
951 AAResults.addAAResult(*R);
952 MAMProxy
953 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
954 }
955 }
956};
957
958/// A wrapper pass to provide the legacy pass manager access to a suitably
959/// prepared AAResults object.
960class AAResultsWrapperPass : public FunctionPass {
961 std::unique_ptr<AAResults> AAR;
962
963public:
964 static char ID;
965
966 AAResultsWrapperPass();
967
968 AAResults &getAAResults() { return *AAR; }
969 const AAResults &getAAResults() const { return *AAR; }
970
971 bool runOnFunction(Function &F) override;
972
973 void getAnalysisUsage(AnalysisUsage &AU) const override;
974};
975
976/// A wrapper pass for external alias analyses. This just squirrels away the
977/// callback used to run any analyses and register their results.
978struct ExternalAAWrapperPass : ImmutablePass {
979 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
980
981 CallbackT CB;
982
983 static char ID;
984
985 ExternalAAWrapperPass();
986
987 explicit ExternalAAWrapperPass(CallbackT CB);
988
989 void getAnalysisUsage(AnalysisUsage &AU) const override {
990 AU.setPreservesAll();
991 }
992};
993
994/// A wrapper pass around a callback which can be used to populate the
995/// AAResults in the AAResultsWrapperPass from an external AA.
996///
997/// The callback provided here will be used each time we prepare an AAResults
998/// object, and will receive a reference to the function wrapper pass, the
999/// function, and the AAResults object to populate. This should be used when
1000/// setting up a custom pass pipeline to inject a hook into the AA results.
1001ImmutablePass *createExternalAAWrapperPass(
1002 std::function<void(Pass &, Function &, AAResults &)> Callback);
1003
1004} // end namespace llvm
1005
1006#endif // LLVM_ANALYSIS_ALIASANALYSIS_H
1007

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