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

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