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 bool pointsToConstantMemory(const MemoryLocation &Loc, AAQueryInfo &AAQI,
570 bool OrLocal = false);
571 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
572 bool IgnoreLocals = false);
573 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2,
574 AAQueryInfo &AAQIP);
575 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
576 AAQueryInfo &AAQI);
577 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
578 AAQueryInfo &AAQI);
579 ModRefInfo getModRefInfo(const VAArgInst *V, const MemoryLocation &Loc,
580 AAQueryInfo &AAQI);
581 ModRefInfo getModRefInfo(const LoadInst *L, const MemoryLocation &Loc,
582 AAQueryInfo &AAQI);
583 ModRefInfo getModRefInfo(const StoreInst *S, const MemoryLocation &Loc,
584 AAQueryInfo &AAQI);
585 ModRefInfo getModRefInfo(const FenceInst *S, const MemoryLocation &Loc,
586 AAQueryInfo &AAQI);
587 ModRefInfo getModRefInfo(const AtomicCmpXchgInst *CX,
588 const MemoryLocation &Loc, AAQueryInfo &AAQI);
589 ModRefInfo getModRefInfo(const AtomicRMWInst *RMW, const MemoryLocation &Loc,
590 AAQueryInfo &AAQI);
591 ModRefInfo getModRefInfo(const CatchPadInst *I, const MemoryLocation &Loc,
592 AAQueryInfo &AAQI);
593 ModRefInfo getModRefInfo(const CatchReturnInst *I, const MemoryLocation &Loc,
594 AAQueryInfo &AAQI);
595 ModRefInfo getModRefInfo(const Instruction *I,
596 const std::optional<MemoryLocation> &OptLoc,
597 AAQueryInfo &AAQIP);
598 ModRefInfo callCapturesBefore(const Instruction *I,
599 const MemoryLocation &MemLoc, DominatorTree *DT,
600 AAQueryInfo &AAQIP);
601 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI);
602
603private:
604 class Concept;
605
606 template <typename T> class Model;
607
608 friend class AAResultBase;
609
610 const TargetLibraryInfo &TLI;
611
612 std::vector<std::unique_ptr<Concept>> AAs;
613
614 std::vector<AnalysisKey *> AADeps;
615
616 friend class BatchAAResults;
617};
618
619/// This class is a wrapper over an AAResults, and it is intended to be used
620/// only when there are no IR changes inbetween queries. BatchAAResults is
621/// reusing the same `AAQueryInfo` to preserve the state across queries,
622/// esentially making AA work in "batch mode". The internal state cannot be
623/// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
624/// or create a new BatchAAResults.
625class BatchAAResults {
626 AAResults &AA;
627 AAQueryInfo AAQI;
628 SimpleCaptureInfo SimpleCI;
629
630public:
631 BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(AAR, &SimpleCI) {}
632 BatchAAResults(AAResults &AAR, CaptureInfo *CI) : AA(AAR), AAQI(AAR, CI) {}
633
634 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
635 return AA.alias(LocA, LocB, AAQI);
636 }
637 bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
638 return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
639 }
640 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc,
641 bool IgnoreLocals = false) {
642 return AA.getModRefInfoMask(Loc, AAQI, IgnoreLocals);
643 }
644 ModRefInfo getModRefInfo(const Instruction *I,
645 const std::optional<MemoryLocation> &OptLoc) {
646 return AA.getModRefInfo(I, OptLoc, AAQIP&: AAQI);
647 }
648 ModRefInfo getModRefInfo(const Instruction *I, const CallBase *Call2) {
649 return AA.getModRefInfo(I, Call2, AAQIP&: AAQI);
650 }
651 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
652 return AA.getArgModRefInfo(Call, ArgIdx);
653 }
654 MemoryEffects getMemoryEffects(const CallBase *Call) {
655 return AA.getMemoryEffects(Call, AAQI);
656 }
657 bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
658 return alias(LocA, LocB) == AliasResult::MustAlias;
659 }
660 bool isMustAlias(const Value *V1, const Value *V2) {
661 return alias(LocA: MemoryLocation(V1, LocationSize::precise(Value: 1)),
662 LocB: MemoryLocation(V2, LocationSize::precise(Value: 1))) ==
663 AliasResult::MustAlias;
664 }
665 ModRefInfo callCapturesBefore(const Instruction *I,
666 const MemoryLocation &MemLoc,
667 DominatorTree *DT) {
668 return AA.callCapturesBefore(I, MemLoc, DT, AAQIP&: AAQI);
669 }
670
671 /// Assume that values may come from different cycle iterations.
672 void enableCrossIterationMode() {
673 AAQI.MayBeCrossIteration = true;
674 }
675
676 /// Disable the use of the dominator tree during alias analysis queries.
677 void disableDominatorTree() { AAQI.UseDominatorTree = false; }
678};
679
680/// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
681/// pointer or reference.
682using AliasAnalysis = AAResults;
683
684/// A private abstract base class describing the concept of an individual alias
685/// analysis implementation.
686///
687/// This interface is implemented by any \c Model instantiation. It is also the
688/// interface which a type used to instantiate the model must provide.
689///
690/// All of these methods model methods by the same name in the \c
691/// AAResults class. Only differences and specifics to how the
692/// implementations are called are documented here.
693class AAResults::Concept {
694public:
695 virtual ~Concept() = 0;
696
697 //===--------------------------------------------------------------------===//
698 /// \name Alias Queries
699 /// @{
700
701 /// The main low level interface to the alias analysis implementation.
702 /// Returns an AliasResult indicating whether the two pointers are aliased to
703 /// each other. This is the interface that must be implemented by specific
704 /// alias analysis implementations.
705 virtual AliasResult alias(const MemoryLocation &LocA,
706 const MemoryLocation &LocB, AAQueryInfo &AAQI,
707 const Instruction *CtxI) = 0;
708
709 /// @}
710 //===--------------------------------------------------------------------===//
711 /// \name Simple mod/ref information
712 /// @{
713
714 /// Returns a bitmask that should be unconditionally applied to the ModRef
715 /// info of a memory location. This allows us to eliminate Mod and/or Ref from
716 /// the ModRef info based on the knowledge that the memory location points to
717 /// constant and/or locally-invariant memory.
718 virtual ModRefInfo getModRefInfoMask(const MemoryLocation &Loc,
719 AAQueryInfo &AAQI,
720 bool IgnoreLocals) = 0;
721
722 /// Get the ModRef info associated with a pointer argument of a callsite. The
723 /// result's bits are set to indicate the allowed aliasing ModRef kinds. Note
724 /// that these bits do not necessarily account for the overall behavior of
725 /// the function, but rather only provide additional per-argument
726 /// information.
727 virtual ModRefInfo getArgModRefInfo(const CallBase *Call,
728 unsigned ArgIdx) = 0;
729
730 /// Return the behavior of the given call site.
731 virtual MemoryEffects getMemoryEffects(const CallBase *Call,
732 AAQueryInfo &AAQI) = 0;
733
734 /// Return the behavior when calling the given function.
735 virtual MemoryEffects getMemoryEffects(const Function *F) = 0;
736
737 /// getModRefInfo (for call sites) - Return information about whether
738 /// a particular call site modifies or reads the specified memory location.
739 virtual ModRefInfo getModRefInfo(const CallBase *Call,
740 const MemoryLocation &Loc,
741 AAQueryInfo &AAQI) = 0;
742
743 /// Return information about whether two call sites may refer to the same set
744 /// of memory locations. See the AA documentation for details:
745 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
746 virtual ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
747 AAQueryInfo &AAQI) = 0;
748
749 /// @}
750};
751
752/// A private class template which derives from \c Concept and wraps some other
753/// type.
754///
755/// This models the concept by directly forwarding each interface point to the
756/// wrapped type which must implement a compatible interface. This provides
757/// a type erased binding.
758template <typename AAResultT> class AAResults::Model final : public Concept {
759 AAResultT &Result;
760
761public:
762 explicit Model(AAResultT &Result, AAResults &AAR) : Result(Result) {}
763 ~Model() override = default;
764
765 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
766 AAQueryInfo &AAQI, const Instruction *CtxI) override {
767 return Result.alias(LocA, LocB, AAQI, CtxI);
768 }
769
770 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
771 bool IgnoreLocals) override {
772 return Result.getModRefInfoMask(Loc, AAQI, IgnoreLocals);
773 }
774
775 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) override {
776 return Result.getArgModRefInfo(Call, ArgIdx);
777 }
778
779 MemoryEffects getMemoryEffects(const CallBase *Call,
780 AAQueryInfo &AAQI) override {
781 return Result.getMemoryEffects(Call, AAQI);
782 }
783
784 MemoryEffects getMemoryEffects(const Function *F) override {
785 return Result.getMemoryEffects(F);
786 }
787
788 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
789 AAQueryInfo &AAQI) override {
790 return Result.getModRefInfo(Call, Loc, AAQI);
791 }
792
793 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
794 AAQueryInfo &AAQI) override {
795 return Result.getModRefInfo(Call1, Call2, AAQI);
796 }
797};
798
799/// A base class to help implement the function alias analysis results concept.
800///
801/// Because of the nature of many alias analysis implementations, they often
802/// only implement a subset of the interface. This base class will attempt to
803/// implement the remaining portions of the interface in terms of simpler forms
804/// of the interface where possible, and otherwise provide conservatively
805/// correct fallback implementations.
806///
807/// Implementors of an alias analysis should derive from this class, and then
808/// override specific methods that they wish to customize. There is no need to
809/// use virtual anywhere.
810class AAResultBase {
811protected:
812 explicit AAResultBase() = default;
813
814 // Provide all the copy and move constructors so that derived types aren't
815 // constrained.
816 AAResultBase(const AAResultBase &Arg) {}
817 AAResultBase(AAResultBase &&Arg) {}
818
819public:
820 AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB,
821 AAQueryInfo &AAQI, const Instruction *I) {
822 return AliasResult::MayAlias;
823 }
824
825 ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI,
826 bool IgnoreLocals) {
827 return ModRefInfo::ModRef;
828 }
829
830 ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
831 return ModRefInfo::ModRef;
832 }
833
834 MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI) {
835 return MemoryEffects::unknown();
836 }
837
838 MemoryEffects getMemoryEffects(const Function *F) {
839 return MemoryEffects::unknown();
840 }
841
842 ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc,
843 AAQueryInfo &AAQI) {
844 return ModRefInfo::ModRef;
845 }
846
847 ModRefInfo getModRefInfo(const CallBase *Call1, const CallBase *Call2,
848 AAQueryInfo &AAQI) {
849 return ModRefInfo::ModRef;
850 }
851};
852
853/// Return true if this pointer is returned by a noalias function.
854bool isNoAliasCall(const Value *V);
855
856/// Return true if this pointer refers to a distinct and identifiable object.
857/// This returns true for:
858/// Global Variables and Functions (but not Global Aliases)
859/// Allocas
860/// ByVal and NoAlias Arguments
861/// NoAlias returns (e.g. calls to malloc)
862///
863bool isIdentifiedObject(const Value *V);
864
865/// Return true if V is umabigously identified at the function-level.
866/// Different IdentifiedFunctionLocals can't alias.
867/// Further, an IdentifiedFunctionLocal can not alias with any function
868/// arguments other than itself, which is not necessarily true for
869/// IdentifiedObjects.
870bool isIdentifiedFunctionLocal(const Value *V);
871
872/// Returns true if the pointer is one which would have been considered an
873/// escape by isNonEscapingLocalObject.
874bool isEscapeSource(const Value *V);
875
876/// Return true if Object memory is not visible after an unwind, in the sense
877/// that program semantics cannot depend on Object containing any particular
878/// value on unwind. If the RequiresNoCaptureBeforeUnwind out parameter is set
879/// to true, then the memory is only not visible if the object has not been
880/// captured prior to the unwind. Otherwise it is not visible even if captured.
881bool isNotVisibleOnUnwind(const Value *Object,
882 bool &RequiresNoCaptureBeforeUnwind);
883
884/// Return true if the Object is writable, in the sense that any location based
885/// on this pointer that can be loaded can also be stored to without trapping.
886/// Additionally, at the point Object is declared, stores can be introduced
887/// without data races. At later points, this is only the case if the pointer
888/// can not escape to a different thread.
889///
890/// If ExplicitlyDereferenceableOnly is set to true, this property only holds
891/// for the part of Object that is explicitly marked as dereferenceable, e.g.
892/// using the dereferenceable(N) attribute. It does not necessarily hold for
893/// parts that are only known to be dereferenceable due to the presence of
894/// loads.
895bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly);
896
897/// A manager for alias analyses.
898///
899/// This class can have analyses registered with it and when run, it will run
900/// all of them and aggregate their results into single AA results interface
901/// that dispatches across all of the alias analysis results available.
902///
903/// Note that the order in which analyses are registered is very significant.
904/// That is the order in which the results will be aggregated and queried.
905///
906/// This manager effectively wraps the AnalysisManager for registering alias
907/// analyses. When you register your alias analysis with this manager, it will
908/// ensure the analysis itself is registered with its AnalysisManager.
909///
910/// The result of this analysis is only invalidated if one of the particular
911/// aggregated AA results end up being invalidated. This removes the need to
912/// explicitly preserve the results of `AAManager`. Note that analyses should no
913/// longer be registered once the `AAManager` is run.
914class AAManager : public AnalysisInfoMixin<AAManager> {
915public:
916 using Result = AAResults;
917
918 /// Register a specific AA result.
919 template <typename AnalysisT> void registerFunctionAnalysis() {
920 ResultGetters.push_back(Elt: &getFunctionAAResultImpl<AnalysisT>);
921 }
922
923 /// Register a specific AA result.
924 template <typename AnalysisT> void registerModuleAnalysis() {
925 ResultGetters.push_back(Elt: &getModuleAAResultImpl<AnalysisT>);
926 }
927
928 Result run(Function &F, FunctionAnalysisManager &AM);
929
930private:
931 friend AnalysisInfoMixin<AAManager>;
932
933 static AnalysisKey Key;
934
935 SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
936 AAResults &AAResults),
937 4> ResultGetters;
938
939 template <typename AnalysisT>
940 static void getFunctionAAResultImpl(Function &F,
941 FunctionAnalysisManager &AM,
942 AAResults &AAResults) {
943 AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
944 AAResults.addAADependencyID(ID: AnalysisT::ID());
945 }
946
947 template <typename AnalysisT>
948 static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
949 AAResults &AAResults) {
950 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
951 if (auto *R =
952 MAMProxy.template getCachedResult<AnalysisT>(*F.getParent())) {
953 AAResults.addAAResult(*R);
954 MAMProxy
955 .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
956 }
957 }
958};
959
960/// A wrapper pass to provide the legacy pass manager access to a suitably
961/// prepared AAResults object.
962class AAResultsWrapperPass : public FunctionPass {
963 std::unique_ptr<AAResults> AAR;
964
965public:
966 static char ID;
967
968 AAResultsWrapperPass();
969
970 AAResults &getAAResults() { return *AAR; }
971 const AAResults &getAAResults() const { return *AAR; }
972
973 bool runOnFunction(Function &F) override;
974
975 void getAnalysisUsage(AnalysisUsage &AU) const override;
976};
977
978/// A wrapper pass for external alias analyses. This just squirrels away the
979/// callback used to run any analyses and register their results.
980struct ExternalAAWrapperPass : ImmutablePass {
981 using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
982
983 CallbackT CB;
984
985 static char ID;
986
987 ExternalAAWrapperPass();
988
989 explicit ExternalAAWrapperPass(CallbackT CB);
990
991 void getAnalysisUsage(AnalysisUsage &AU) const override {
992 AU.setPreservesAll();
993 }
994};
995
996/// A wrapper pass around a callback which can be used to populate the
997/// AAResults in the AAResultsWrapperPass from an external AA.
998///
999/// The callback provided here will be used each time we prepare an AAResults
1000/// object, and will receive a reference to the function wrapper pass, the
1001/// function, and the AAResults object to populate. This should be used when
1002/// setting up a custom pass pipeline to inject a hook into the AA results.
1003ImmutablePass *createExternalAAWrapperPass(
1004 std::function<void(Pass &, Function &, AAResults &)> Callback);
1005
1006} // end namespace llvm
1007
1008#endif // LLVM_ANALYSIS_ALIASANALYSIS_H
1009

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