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

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

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