1//==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
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 implements the generic AliasAnalysis interface which is used as the
10// common interface used by all clients and implementations of alias analysis.
11//
12// This file also implements the default version of the AliasAnalysis interface
13// that is to be used when no other implementation is specified. This does some
14// simple tests that detect obvious cases: two different global pointers cannot
15// alias, a global cannot alias a malloc, two different mallocs cannot alias,
16// etc.
17//
18// This alias analysis implementation really isn't very good for anything, but
19// it is very fast, and makes a nice clean default implementation. Because it
20// handles lots of little corner cases, other, more complex, alias analysis
21// implementations may choose to rely on this pass to resolve these simple and
22// easy cases.
23//
24//===----------------------------------------------------------------------===//
25
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/ADT/Statistic.h"
28#include "llvm/Analysis/BasicAliasAnalysis.h"
29#include "llvm/Analysis/CaptureTracking.h"
30#include "llvm/Analysis/GlobalsModRef.h"
31#include "llvm/Analysis/MemoryLocation.h"
32#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
33#include "llvm/Analysis/ScopedNoAliasAA.h"
34#include "llvm/Analysis/TargetLibraryInfo.h"
35#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
36#include "llvm/Analysis/ValueTracking.h"
37#include "llvm/IR/Argument.h"
38#include "llvm/IR/Attributes.h"
39#include "llvm/IR/BasicBlock.h"
40#include "llvm/IR/Instruction.h"
41#include "llvm/IR/Instructions.h"
42#include "llvm/IR/Type.h"
43#include "llvm/IR/Value.h"
44#include "llvm/InitializePasses.h"
45#include "llvm/Pass.h"
46#include "llvm/Support/AtomicOrdering.h"
47#include "llvm/Support/Casting.h"
48#include "llvm/Support/CommandLine.h"
49#include <cassert>
50#include <functional>
51#include <iterator>
52
53#define DEBUG_TYPE "aa"
54
55using namespace llvm;
56
57STATISTIC(NumNoAlias, "Number of NoAlias results");
58STATISTIC(NumMayAlias, "Number of MayAlias results");
59STATISTIC(NumMustAlias, "Number of MustAlias results");
60
61/// Allow disabling BasicAA from the AA results. This is particularly useful
62/// when testing to isolate a single AA implementation.
63static cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden,
64 cl::init(Val: false));
65
66#ifndef NDEBUG
67/// Print a trace of alias analysis queries and their results.
68static cl::opt<bool> EnableAATrace("aa-trace", cl::Hidden, cl::init(false));
69#else
70static const bool EnableAATrace = false;
71#endif
72
73AAResults::AAResults(const TargetLibraryInfo &TLI) : TLI(TLI) {}
74
75AAResults::AAResults(AAResults &&Arg)
76 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {}
77
78AAResults::~AAResults() = default;
79
80bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
81 FunctionAnalysisManager::Invalidator &Inv) {
82 // AAResults preserves the AAManager by default, due to the stateless nature
83 // of AliasAnalysis. There is no need to check whether it has been preserved
84 // explicitly. Check if any module dependency was invalidated and caused the
85 // AAManager to be invalidated. Invalidate ourselves in that case.
86 auto PAC = PA.getChecker<AAManager>();
87 if (!PAC.preservedWhenStateless())
88 return true;
89
90 // Check if any of the function dependencies were invalidated, and invalidate
91 // ourselves in that case.
92 for (AnalysisKey *ID : AADeps)
93 if (Inv.invalidate(ID, IR&: F, PA))
94 return true;
95
96 // Everything we depend on is still fine, so are we. Nothing to invalidate.
97 return false;
98}
99
100//===----------------------------------------------------------------------===//
101// Default chaining methods
102//===----------------------------------------------------------------------===//
103
104AliasResult AAResults::alias(const MemoryLocation &LocA,
105 const MemoryLocation &LocB) {
106 SimpleAAQueryInfo AAQIP(*this);
107 return alias(LocA, LocB, AAQI&: AAQIP, CtxI: nullptr);
108}
109
110AliasResult AAResults::alias(const MemoryLocation &LocA,
111 const MemoryLocation &LocB, AAQueryInfo &AAQI,
112 const Instruction *CtxI) {
113 assert(LocA.Ptr->getType()->isPointerTy() &&
114 LocB.Ptr->getType()->isPointerTy() &&
115 "Can only call alias() on pointers");
116 AliasResult Result = AliasResult::MayAlias;
117
118 if (EnableAATrace) {
119 for (unsigned I = 0; I < AAQI.Depth; ++I)
120 dbgs() << " ";
121 dbgs() << "Start " << *LocA.Ptr << " @ " << LocA.Size << ", "
122 << *LocB.Ptr << " @ " << LocB.Size << "\n";
123 }
124
125 AAQI.Depth++;
126 for (const auto &AA : AAs) {
127 Result = AA->alias(LocA, LocB, AAQI, CtxI);
128 if (Result != AliasResult::MayAlias)
129 break;
130 }
131 AAQI.Depth--;
132
133 if (EnableAATrace) {
134 for (unsigned I = 0; I < AAQI.Depth; ++I)
135 dbgs() << " ";
136 dbgs() << "End " << *LocA.Ptr << " @ " << LocA.Size << ", "
137 << *LocB.Ptr << " @ " << LocB.Size << " = " << Result << "\n";
138 }
139
140 if (AAQI.Depth == 0) {
141 if (Result == AliasResult::NoAlias)
142 ++NumNoAlias;
143 else if (Result == AliasResult::MustAlias)
144 ++NumMustAlias;
145 else
146 ++NumMayAlias;
147 }
148 return Result;
149}
150
151AliasResult AAResults::aliasErrno(const MemoryLocation &Loc,
152 const Instruction *CtxI) {
153 AliasResult Result = AliasResult::MayAlias;
154
155 for (const auto &AA : AAs) {
156 Result = AA->aliasErrno(Loc, CtxI);
157 if (Result != AliasResult::MayAlias)
158 break;
159 }
160
161 return Result;
162}
163
164ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,
165 bool IgnoreLocals) {
166 SimpleAAQueryInfo AAQIP(*this);
167 return getModRefInfoMask(Loc, AAQI&: AAQIP, IgnoreLocals);
168}
169
170ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,
171 AAQueryInfo &AAQI, bool IgnoreLocals) {
172 ModRefInfo Result = ModRefInfo::ModRef;
173
174 for (const auto &AA : AAs) {
175 Result &= AA->getModRefInfoMask(Loc, AAQI, IgnoreLocals);
176
177 // Early-exit the moment we reach the bottom of the lattice.
178 if (isNoModRef(MRI: Result))
179 return ModRefInfo::NoModRef;
180 }
181
182 return Result;
183}
184
185ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
186 ModRefInfo Result = ModRefInfo::ModRef;
187
188 for (const auto &AA : AAs) {
189 Result &= AA->getArgModRefInfo(Call, ArgIdx);
190
191 // Early-exit the moment we reach the bottom of the lattice.
192 if (isNoModRef(MRI: Result))
193 return ModRefInfo::NoModRef;
194 }
195
196 return Result;
197}
198
199ModRefInfo AAResults::getModRefInfo(const Instruction *I,
200 const CallBase *Call2) {
201 SimpleAAQueryInfo AAQIP(*this);
202 return getModRefInfo(I, Call2, AAQIP);
203}
204
205ModRefInfo AAResults::getModRefInfo(const Instruction *I, const CallBase *Call2,
206 AAQueryInfo &AAQI) {
207 // We may have two calls.
208 if (const auto *Call1 = dyn_cast<CallBase>(Val: I)) {
209 // Check if the two calls modify the same memory.
210 return getModRefInfo(Call1, Call2, AAQI);
211 }
212 // If this is a fence, just return ModRef.
213 if (I->isFenceLike())
214 return ModRefInfo::ModRef;
215 // Otherwise, check if the call modifies or references the
216 // location this memory access defines. The best we can say
217 // is that if the call references what this instruction
218 // defines, it must be clobbered by this location.
219 const MemoryLocation DefLoc = MemoryLocation::get(Inst: I);
220 ModRefInfo MR = getModRefInfo(Call: Call2, Loc: DefLoc, AAQI);
221 if (isModOrRefSet(MRI: MR))
222 return ModRefInfo::ModRef;
223 return ModRefInfo::NoModRef;
224}
225
226ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
227 const MemoryLocation &Loc,
228 AAQueryInfo &AAQI) {
229 ModRefInfo Result = ModRefInfo::ModRef;
230
231 for (const auto &AA : AAs) {
232 Result &= AA->getModRefInfo(Call, Loc, AAQI);
233
234 // Early-exit the moment we reach the bottom of the lattice.
235 if (isNoModRef(MRI: Result))
236 return ModRefInfo::NoModRef;
237 }
238
239 // Apply the ModRef mask. This ensures that if Loc is a constant memory
240 // location, we take into account the fact that the call definitely could not
241 // modify the memory location.
242 if (!isNoModRef(MRI: Result))
243 Result &= getModRefInfoMask(Loc);
244
245 return Result;
246}
247
248ModRefInfo
249getModRefInfoInaccessibleAndTargetMemLoc(const MemoryEffects CallUse,
250 const MemoryEffects CallDef) {
251
252 ModRefInfo Result = ModRefInfo::NoModRef;
253 auto addModRefInfoForLoc = [&](IRMemLocation L) {
254 ModRefInfo UseMR = CallUse.getModRef(Loc: L);
255 if (UseMR == ModRefInfo::NoModRef)
256 return;
257 ModRefInfo DefMR = CallDef.getModRef(Loc: L);
258 if (DefMR == ModRefInfo::NoModRef)
259 return;
260 if (DefMR == ModRefInfo::Ref && DefMR == UseMR)
261 return;
262 Result |= UseMR;
263 };
264
265 addModRefInfoForLoc(IRMemLocation::InaccessibleMem);
266 for (auto Loc : MemoryEffects::targetMemLocations())
267 addModRefInfoForLoc(Loc);
268 return Result;
269}
270
271ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
272 const CallBase *Call2, AAQueryInfo &AAQI) {
273 ModRefInfo Result = ModRefInfo::ModRef;
274
275 for (const auto &AA : AAs) {
276 Result &= AA->getModRefInfo(Call1, Call2, AAQI);
277
278 // Early-exit the moment we reach the bottom of the lattice.
279 if (isNoModRef(MRI: Result))
280 return ModRefInfo::NoModRef;
281 }
282
283 // Try to refine the mod-ref info further using other API entry points to the
284 // aggregate set of AA results.
285
286 // If Call1 or Call2 are readnone, they don't interact.
287 auto Call1B = getMemoryEffects(Call: Call1, AAQI);
288 if (Call1B.doesNotAccessMemory())
289 return ModRefInfo::NoModRef;
290
291 auto Call2B = getMemoryEffects(Call: Call2, AAQI);
292 if (Call2B.doesNotAccessMemory())
293 return ModRefInfo::NoModRef;
294
295 // If they both only read from memory, there is no dependence.
296 if (Call1B.onlyReadsMemory() && Call2B.onlyReadsMemory())
297 return ModRefInfo::NoModRef;
298
299 // If Call1 only reads memory, the only dependence on Call2 can be
300 // from Call1 reading memory written by Call2.
301 if (Call1B.onlyReadsMemory())
302 Result &= ModRefInfo::Ref;
303 else if (Call1B.onlyWritesMemory())
304 Result &= ModRefInfo::Mod;
305
306 // If Call2 only access memory through arguments, accumulate the mod/ref
307 // information from Call1's references to the memory referenced by
308 // Call2's arguments.
309 if (Call2B.onlyAccessesArgPointees()) {
310 if (!Call2B.doesAccessArgPointees())
311 return ModRefInfo::NoModRef;
312 ModRefInfo R = ModRefInfo::NoModRef;
313 for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
314 const Value *Arg = *I;
315 if (!Arg->getType()->isPointerTy())
316 continue;
317 unsigned Call2ArgIdx = std::distance(first: Call2->arg_begin(), last: I);
318 auto Call2ArgLoc =
319 MemoryLocation::getForArgument(Call: Call2, ArgIdx: Call2ArgIdx, TLI);
320
321 // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
322 // dependence of Call1 on that location is the inverse:
323 // - If Call2 modifies location, dependence exists if Call1 reads or
324 // writes.
325 // - If Call2 only reads location, dependence exists if Call1 writes.
326 ModRefInfo ArgModRefC2 = getArgModRefInfo(Call: Call2, ArgIdx: Call2ArgIdx);
327 ModRefInfo ArgMask = ModRefInfo::NoModRef;
328 if (isModSet(MRI: ArgModRefC2))
329 ArgMask = ModRefInfo::ModRef;
330 else if (isRefSet(MRI: ArgModRefC2))
331 ArgMask = ModRefInfo::Mod;
332
333 // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
334 // above ArgMask to update dependence info.
335 ArgMask &= getModRefInfo(Call: Call1, Loc: Call2ArgLoc, AAQI);
336
337 R = (R | ArgMask) & Result;
338 if (R == Result)
339 break;
340 }
341
342 return R;
343 }
344
345 // If Call1 only accesses memory through arguments, check if Call2 references
346 // any of the memory referenced by Call1's arguments. If not, return NoModRef.
347 if (Call1B.onlyAccessesArgPointees()) {
348 if (!Call1B.doesAccessArgPointees())
349 return ModRefInfo::NoModRef;
350 ModRefInfo R = ModRefInfo::NoModRef;
351 for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
352 const Value *Arg = *I;
353 if (!Arg->getType()->isPointerTy())
354 continue;
355 unsigned Call1ArgIdx = std::distance(first: Call1->arg_begin(), last: I);
356 auto Call1ArgLoc =
357 MemoryLocation::getForArgument(Call: Call1, ArgIdx: Call1ArgIdx, TLI);
358
359 // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
360 // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
361 // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
362 ModRefInfo ArgModRefC1 = getArgModRefInfo(Call: Call1, ArgIdx: Call1ArgIdx);
363 ModRefInfo ModRefC2 = getModRefInfo(Call: Call2, Loc: Call1ArgLoc, AAQI);
364 if ((isModSet(MRI: ArgModRefC1) && isModOrRefSet(MRI: ModRefC2)) ||
365 (isRefSet(MRI: ArgModRefC1) && isModSet(MRI: ModRefC2)))
366 R = (R | ArgModRefC1) & Result;
367
368 if (R == Result)
369 break;
370 }
371
372 return R;
373 }
374
375 // If only Inaccessible and Target Memory Location have set ModRefInfo
376 // then check the relation between the same locations.
377 if (Call1B.onlyAccessesInaccessibleOrTargetMem() &&
378 Call2B.onlyAccessesInaccessibleOrTargetMem())
379 return getModRefInfoInaccessibleAndTargetMemLoc(CallUse: Call1B, CallDef: Call2B);
380
381 return Result;
382}
383
384ModRefInfo AAResults::getModRefInfo(const Instruction *I1,
385 const Instruction *I2) {
386 SimpleAAQueryInfo AAQIP(*this);
387 return getModRefInfo(I1, I2, AAQI&: AAQIP);
388}
389
390ModRefInfo AAResults::getModRefInfo(const Instruction *I1,
391 const Instruction *I2, AAQueryInfo &AAQI) {
392 // Early-exit if either instruction does not read or write memory.
393 if (!I1->mayReadOrWriteMemory() || !I2->mayReadOrWriteMemory())
394 return ModRefInfo::NoModRef;
395
396 if (const auto *Call2 = dyn_cast<CallBase>(Val: I2))
397 return getModRefInfo(I: I1, Call2, AAQI);
398
399 // FIXME: We can have a more precise result.
400 ModRefInfo MR = getModRefInfo(I: I1, OptLoc: MemoryLocation::getOrNone(Inst: I2), AAQIP&: AAQI);
401 return isModOrRefSet(MRI: MR) ? ModRefInfo::ModRef : ModRefInfo::NoModRef;
402}
403
404MemoryEffects AAResults::getMemoryEffects(const CallBase *Call,
405 AAQueryInfo &AAQI) {
406 MemoryEffects Result = MemoryEffects::unknown();
407
408 for (const auto &AA : AAs) {
409 Result &= AA->getMemoryEffects(Call, AAQI);
410
411 // Early-exit the moment we reach the bottom of the lattice.
412 if (Result.doesNotAccessMemory())
413 return Result;
414 }
415
416 return Result;
417}
418
419MemoryEffects AAResults::getMemoryEffects(const CallBase *Call) {
420 SimpleAAQueryInfo AAQI(*this);
421 return getMemoryEffects(Call, AAQI);
422}
423
424MemoryEffects AAResults::getMemoryEffects(const Function *F) {
425 MemoryEffects Result = MemoryEffects::unknown();
426
427 for (const auto &AA : AAs) {
428 Result &= AA->getMemoryEffects(F);
429
430 // Early-exit the moment we reach the bottom of the lattice.
431 if (Result.doesNotAccessMemory())
432 return Result;
433 }
434
435 return Result;
436}
437
438raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
439 switch (AR) {
440 case AliasResult::NoAlias:
441 OS << "NoAlias";
442 break;
443 case AliasResult::MustAlias:
444 OS << "MustAlias";
445 break;
446 case AliasResult::MayAlias:
447 OS << "MayAlias";
448 break;
449 case AliasResult::PartialAlias:
450 OS << "PartialAlias";
451 if (AR.hasOffset())
452 OS << " (off " << AR.getOffset() << ")";
453 break;
454 }
455 return OS;
456}
457
458//===----------------------------------------------------------------------===//
459// Helper method implementation
460//===----------------------------------------------------------------------===//
461
462ModRefInfo llvm::getSyncEffects(AAResults *AA, const MemoryLocation &Loc,
463 AAQueryInfo &AAQI) {
464 if (!Loc.Ptr)
465 return ModRefInfo::ModRef;
466
467 // If the location is *never* captured, it cannot be affected by
468 // synchronizing operations. However, we cannot ignore locations that are
469 // only captured after the operation, as the synchronization may still have
470 // an effect if the object is only captured *later*. As such, set I to null
471 // and ReturnCaptures to true here.
472 const Value *Obj = getUnderlyingObject(V: Loc.Ptr);
473 CaptureComponents CC = AAQI.CA->getCapturesBefore(
474 Object: Obj, /*I=*/nullptr, /*OrAt=*/true, /*ReturnCaptures=*/true);
475 if (capturesNothing(CC))
476 return ModRefInfo::NoModRef;
477
478 // If only read provenance was captured, other threads may only read the
479 // object.
480 ModRefInfo MR =
481 capturesReadProvenanceOnly(CC) ? ModRefInfo::Ref : ModRefInfo::ModRef;
482
483 // If Loc is a constant memory location, the synchronization operation
484 // definitely could not modify it.
485 return MR & AA->getModRefInfoMask(Loc);
486}
487
488ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
489 const MemoryLocation &Loc,
490 AAQueryInfo &AAQI) {
491 // If the load address doesn't alias the given address, it doesn't read
492 // or write the specified memory.
493 if (Loc.Ptr) {
494 AliasResult AR = alias(LocA: MemoryLocation::get(LI: L), LocB: Loc, AAQI, CtxI: L);
495 if (AR == AliasResult::NoAlias) {
496 // Synchronization effects may affect locations that do not alias.
497 if (isStrongerThanMonotonic(AO: L->getOrdering()))
498 return getSyncEffects(AA: this, Loc, AAQI);
499 return ModRefInfo::NoModRef;
500 }
501 }
502
503 // Preserve the ordering requirement.
504 if (isStrongerThanUnordered(AO: L->getOrdering()))
505 return ModRefInfo::ModRef;
506
507 // Otherwise, a load just reads.
508 return ModRefInfo::Ref;
509}
510
511ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
512 const MemoryLocation &Loc,
513 AAQueryInfo &AAQI) {
514 if (Loc.Ptr) {
515 AliasResult AR = alias(LocA: MemoryLocation::get(SI: S), LocB: Loc, AAQI, CtxI: S);
516 // If the store address cannot alias the pointer in question, then the
517 // specified memory cannot be modified by the store.
518 if (AR == AliasResult::NoAlias) {
519 // Synchronization effects may affect locations that do not alias.
520 if (isStrongerThanMonotonic(AO: S->getOrdering()))
521 return getSyncEffects(AA: this, Loc, AAQI);
522 return ModRefInfo::NoModRef;
523 }
524
525 // Examine the ModRef mask. If Mod isn't present, then return NoModRef.
526 // This ensures that if Loc is a constant memory location, we take into
527 // account the fact that the store definitely could not modify the memory
528 // location.
529 if (!isModSet(MRI: getModRefInfoMask(Loc)))
530 return ModRefInfo::NoModRef;
531 }
532
533 // Preserve the ordering requirement.
534 if (isStrongerThanUnordered(AO: S->getOrdering()))
535 return ModRefInfo::ModRef;
536
537 // Otherwise, a store just writes.
538 return ModRefInfo::Mod;
539}
540
541ModRefInfo AAResults::getModRefInfo(const FenceInst *F,
542 const MemoryLocation &Loc,
543 AAQueryInfo &AAQI) {
544 if (Loc.Ptr) {
545 ModRefInfo Result = ModRefInfo::ModRef;
546
547 for (const auto &AA : AAs) {
548 Result &= AA->getModRefInfo(F, Loc, AAQI);
549
550 if (isNoModRef(MRI: Result))
551 return ModRefInfo::NoModRef;
552 }
553
554 return Result & getSyncEffects(AA: this, Loc, AAQI);
555 }
556
557 return ModRefInfo::ModRef;
558}
559
560ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
561 const MemoryLocation &Loc,
562 AAQueryInfo &AAQI) {
563 if (Loc.Ptr) {
564 AliasResult AR = alias(LocA: MemoryLocation::get(VI: V), LocB: Loc, AAQI, CtxI: V);
565 // If the va_arg address cannot alias the pointer in question, then the
566 // specified memory cannot be accessed by the va_arg.
567 if (AR == AliasResult::NoAlias)
568 return ModRefInfo::NoModRef;
569
570 // If the pointer is a pointer to invariant memory, then it could not have
571 // been modified by this va_arg.
572 return getModRefInfoMask(Loc, AAQI);
573 }
574
575 // Otherwise, a va_arg reads and writes.
576 return ModRefInfo::ModRef;
577}
578
579ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
580 const MemoryLocation &Loc,
581 AAQueryInfo &AAQI) {
582 if (Loc.Ptr) {
583 // If the pointer is a pointer to invariant memory,
584 // then it could not have been modified by this catchpad.
585 return getModRefInfoMask(Loc, AAQI);
586 }
587
588 // Otherwise, a catchpad reads and writes.
589 return ModRefInfo::ModRef;
590}
591
592ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
593 const MemoryLocation &Loc,
594 AAQueryInfo &AAQI) {
595 if (Loc.Ptr) {
596 // If the pointer is a pointer to invariant memory,
597 // then it could not have been modified by this catchpad.
598 return getModRefInfoMask(Loc, AAQI);
599 }
600
601 // Otherwise, a catchret reads and writes.
602 return ModRefInfo::ModRef;
603}
604
605ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
606 const MemoryLocation &Loc,
607 AAQueryInfo &AAQI) {
608 if (Loc.Ptr) {
609 AliasResult AR = alias(LocA: MemoryLocation::get(CXI: CX), LocB: Loc, AAQI, CtxI: CX);
610 // If the cmpxchg address does not alias the location, it does not access
611 // it.
612 if (AR == AliasResult::NoAlias) {
613 // Synchronization effects may affect locations that do not alias.
614 if (isStrongerThanMonotonic(AO: CX->getMergedOrdering()))
615 return getSyncEffects(AA: this, Loc, AAQI);
616 return ModRefInfo::NoModRef;
617 }
618 }
619
620 return ModRefInfo::ModRef;
621}
622
623ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
624 const MemoryLocation &Loc,
625 AAQueryInfo &AAQI) {
626 if (Loc.Ptr) {
627 AliasResult AR = alias(LocA: MemoryLocation::get(RMWI: RMW), LocB: Loc, AAQI, CtxI: RMW);
628 // If the atomicrmw address does not alias the location, it does not access
629 // it.
630 if (AR == AliasResult::NoAlias) {
631 // Synchronization effects may affect locations that do not alias.
632 if (isStrongerThanMonotonic(AO: RMW->getOrdering()))
633 return getSyncEffects(AA: this, Loc, AAQI);
634 return ModRefInfo::NoModRef;
635 }
636 }
637
638 return ModRefInfo::ModRef;
639}
640
641ModRefInfo AAResults::getModRefInfo(const Instruction *I,
642 const std::optional<MemoryLocation> &OptLoc,
643 AAQueryInfo &AAQIP) {
644 if (OptLoc == std::nullopt) {
645 if (const auto *Call = dyn_cast<CallBase>(Val: I))
646 return getMemoryEffects(Call, AAQI&: AAQIP).getModRef();
647 }
648
649 const MemoryLocation &Loc = OptLoc.value_or(u: MemoryLocation());
650
651 switch (I->getOpcode()) {
652 case Instruction::VAArg:
653 return getModRefInfo(V: (const VAArgInst *)I, Loc, AAQI&: AAQIP);
654 case Instruction::Load:
655 return getModRefInfo(L: (const LoadInst *)I, Loc, AAQI&: AAQIP);
656 case Instruction::Store:
657 return getModRefInfo(S: (const StoreInst *)I, Loc, AAQI&: AAQIP);
658 case Instruction::Fence:
659 return getModRefInfo(F: (const FenceInst *)I, Loc, AAQI&: AAQIP);
660 case Instruction::AtomicCmpXchg:
661 return getModRefInfo(CX: (const AtomicCmpXchgInst *)I, Loc, AAQI&: AAQIP);
662 case Instruction::AtomicRMW:
663 return getModRefInfo(RMW: (const AtomicRMWInst *)I, Loc, AAQI&: AAQIP);
664 case Instruction::Call:
665 case Instruction::CallBr:
666 case Instruction::Invoke:
667 return getModRefInfo(Call: (const CallBase *)I, Loc, AAQI&: AAQIP);
668 case Instruction::CatchPad:
669 return getModRefInfo(CatchPad: (const CatchPadInst *)I, Loc, AAQI&: AAQIP);
670 case Instruction::CatchRet:
671 return getModRefInfo(CatchRet: (const CatchReturnInst *)I, Loc, AAQI&: AAQIP);
672 default:
673 assert(!I->mayReadOrWriteMemory() &&
674 "Unhandled memory access instruction!");
675 return ModRefInfo::NoModRef;
676 }
677}
678
679/// Return information about whether a particular call site modifies
680/// or reads the specified memory location \p MemLoc before instruction \p I
681/// in a BasicBlock.
682/// FIXME: this is really just shoring-up a deficiency in alias analysis.
683/// BasicAA isn't willing to spend linear time determining whether an alloca
684/// was captured before or after this particular call, while we are. However,
685/// with a smarter AA in place, this test is just wasting compile time.
686ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
687 const MemoryLocation &MemLoc,
688 DominatorTree *DT,
689 AAQueryInfo &AAQI) {
690 if (!DT)
691 return ModRefInfo::ModRef;
692
693 const Value *Object = getUnderlyingObject(V: MemLoc.Ptr);
694 if (!isIdentifiedFunctionLocal(V: Object))
695 return ModRefInfo::ModRef;
696
697 const auto *Call = dyn_cast<CallBase>(Val: I);
698 if (!Call || Call == Object)
699 return ModRefInfo::ModRef;
700
701 if (capturesAnything(CC: PointerMayBeCapturedBefore(
702 V: Object, /* ReturnCaptures */ true, I, DT,
703 /* include Object */ IncludeI: true, Mask: CaptureComponents::Provenance)))
704 return ModRefInfo::ModRef;
705
706 unsigned ArgNo = 0;
707 ModRefInfo R = ModRefInfo::NoModRef;
708 // Set flag only if no May found and all operands processed.
709 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
710 CI != CE; ++CI, ++ArgNo) {
711 // Only look at the no-capture or byval pointer arguments. If this
712 // pointer were passed to arguments that were neither of these, then it
713 // couldn't be no-capture.
714 if (!(*CI)->getType()->isPointerTy())
715 continue;
716
717 // Make sure we still check captures(ret: address, provenance) and
718 // captures(address) arguments, as these wouldn't be treated as a capture
719 // at the call-site.
720 CaptureInfo Captures = Call->getCaptureInfo(OpNo: ArgNo);
721 if (capturesAnyProvenance(CC: Captures.getOtherComponents()))
722 continue;
723
724 AliasResult AR =
725 alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: *CI),
726 LocB: MemoryLocation::getBeforeOrAfter(Ptr: Object), AAQI, CtxI: Call);
727 // If this is a no-capture pointer argument, see if we can tell that it
728 // is impossible to alias the pointer we're checking. If not, we have to
729 // assume that the call could touch the pointer, even though it doesn't
730 // escape.
731 if (AR == AliasResult::NoAlias)
732 continue;
733 if (Call->doesNotAccessMemory(OpNo: ArgNo))
734 continue;
735 if (Call->onlyReadsMemory(OpNo: ArgNo)) {
736 R = ModRefInfo::Ref;
737 continue;
738 }
739 return ModRefInfo::ModRef;
740 }
741 return R;
742}
743
744/// canBasicBlockModify - Return true if it is possible for execution of the
745/// specified basic block to modify the location Loc.
746///
747bool AAResults::canBasicBlockModify(const BasicBlock &BB,
748 const MemoryLocation &Loc) {
749 return canInstructionRangeModRef(I1: BB.front(), I2: BB.back(), Loc, Mode: ModRefInfo::Mod);
750}
751
752/// canInstructionRangeModRef - Return true if it is possible for the
753/// execution of the specified instructions to mod\ref (according to the
754/// mode) the location Loc. The instructions to consider are all
755/// of the instructions in the range of [I1,I2] INCLUSIVE.
756/// I1 and I2 must be in the same basic block.
757bool AAResults::canInstructionRangeModRef(const Instruction &I1,
758 const Instruction &I2,
759 const MemoryLocation &Loc,
760 const ModRefInfo Mode) {
761 assert(I1.getParent() == I2.getParent() &&
762 "Instructions not in same basic block!");
763 BasicBlock::const_iterator I = I1.getIterator();
764 BasicBlock::const_iterator E = I2.getIterator();
765 ++E; // Convert from inclusive to exclusive range.
766
767 for (; I != E; ++I) // Check every instruction in range
768 if (isModOrRefSet(MRI: getModRefInfo(I: &*I, OptLoc: Loc) & Mode))
769 return true;
770 return false;
771}
772
773// Provide a definition for the root virtual destructor.
774AAResults::Concept::~Concept() = default;
775
776// Provide a definition for the static object used to identify passes.
777AnalysisKey AAManager::Key;
778
779ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {}
780
781ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB, bool RunEarly)
782 : ImmutablePass(ID), CB(std::move(CB)), RunEarly(RunEarly) {}
783
784char ExternalAAWrapperPass::ID = 0;
785
786INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
787 false, true)
788
789ImmutablePass *
790llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback,
791 bool RunEarly) {
792 return new ExternalAAWrapperPass(std::move(Callback), RunEarly);
793}
794
795AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {}
796
797char AAResultsWrapperPass::ID = 0;
798
799INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
800 "Function Alias Analysis Results", false, true)
801INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
802INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
803INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
804INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
805INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
806INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
807INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
808 "Function Alias Analysis Results", false, true)
809
810/// Run the wrapper pass to rebuild an aggregation over known AA passes.
811///
812/// This is the legacy pass manager's interface to the new-style AA results
813/// aggregation object. Because this is somewhat shoe-horned into the legacy
814/// pass manager, we hard code all the specific alias analyses available into
815/// it. While the particular set enabled is configured via commandline flags,
816/// adding a new alias analysis to LLVM will require adding support for it to
817/// this list.
818bool AAResultsWrapperPass::runOnFunction(Function &F) {
819 // NB! This *must* be reset before adding new AA results to the new
820 // AAResults object because in the legacy pass manager, each instance
821 // of these will refer to the *same* immutable analyses, registering and
822 // unregistering themselves with them. We need to carefully tear down the
823 // previous object first, in this case replacing it with an empty one, before
824 // registering new results.
825 AAR.reset(
826 p: new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
827
828 // Add any target-specific alias analyses that should be run early.
829 auto *ExtWrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>();
830 if (ExtWrapperPass && ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {
831 LLVM_DEBUG(dbgs() << "AAResults register Early ExternalAA: "
832 << ExtWrapperPass->getPassName() << "\n");
833 ExtWrapperPass->CB(*this, F, *AAR);
834 }
835
836 // BasicAA is always available for function analyses. Also, we add it first
837 // so that it can trump TBAA results when it proves MustAlias.
838 // FIXME: TBAA should have an explicit mode to support this and then we
839 // should reconsider the ordering here.
840 if (!DisableBasicAA) {
841 LLVM_DEBUG(dbgs() << "AAResults register BasicAA\n");
842 AAR->addAAResult(AAResult&: getAnalysis<BasicAAWrapperPass>().getResult());
843 }
844
845 // Populate the results with the currently available AAs.
846 if (auto *WrapperPass =
847 getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>()) {
848 LLVM_DEBUG(dbgs() << "AAResults register ScopedNoAliasAA\n");
849 AAR->addAAResult(AAResult&: WrapperPass->getResult());
850 }
851 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>()) {
852 LLVM_DEBUG(dbgs() << "AAResults register TypeBasedAA\n");
853 AAR->addAAResult(AAResult&: WrapperPass->getResult());
854 }
855 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>()) {
856 LLVM_DEBUG(dbgs() << "AAResults register GlobalsAA\n");
857 AAR->addAAResult(AAResult&: WrapperPass->getResult());
858 }
859 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>()) {
860 LLVM_DEBUG(dbgs() << "AAResults register SCEVAA\n");
861 AAR->addAAResult(AAResult&: WrapperPass->getResult());
862 }
863
864 // If available, run an external AA providing callback over the results as
865 // well.
866 if (ExtWrapperPass && !ExtWrapperPass->RunEarly && ExtWrapperPass->CB) {
867 LLVM_DEBUG(dbgs() << "AAResults register Late ExternalAA: "
868 << ExtWrapperPass->getPassName() << "\n");
869 ExtWrapperPass->CB(*this, F, *AAR);
870 }
871
872 // Analyses don't mutate the IR, so return false.
873 return false;
874}
875
876void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
877 AU.setPreservesAll();
878 AU.addRequiredTransitive<BasicAAWrapperPass>();
879 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
880
881 // We also need to mark all the alias analysis passes we will potentially
882 // probe in runOnFunction as used here to ensure the legacy pass manager
883 // preserves them. This hard coding of lists of alias analyses is specific to
884 // the legacy pass manager.
885 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
886 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
887 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
888 AU.addUsedIfAvailable<SCEVAAWrapperPass>();
889 AU.addUsedIfAvailable<ExternalAAWrapperPass>();
890}
891
892AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) {
893 Result R(AM.getResult<TargetLibraryAnalysis>(IR&: F));
894 for (auto &Getter : ResultGetters)
895 (*Getter)(F, AM, R);
896 return R;
897}
898
899bool llvm::isNoAliasCall(const Value *V) {
900 if (const auto *Call = dyn_cast<CallBase>(Val: V))
901 return Call->hasRetAttr(Kind: Attribute::NoAlias);
902 return false;
903}
904
905static bool isNoAliasOrByValArgument(const Value *V) {
906 if (const Argument *A = dyn_cast<Argument>(Val: V))
907 return A->hasNoAliasAttr() || A->hasByValAttr();
908 return false;
909}
910
911bool llvm::isIdentifiedObject(const Value *V) {
912 if (isa<AllocaInst>(Val: V))
913 return true;
914 if (isa<GlobalValue>(Val: V) && !isa<GlobalAlias>(Val: V))
915 return true;
916 if (isNoAliasCall(V))
917 return true;
918 if (isNoAliasOrByValArgument(V))
919 return true;
920 return false;
921}
922
923bool llvm::isIdentifiedFunctionLocal(const Value *V) {
924 return isa<AllocaInst>(Val: V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);
925}
926
927bool llvm::isBaseOfObject(const Value *V) {
928 // TODO: We can handle other cases here
929 // 1) For GC languages, arguments to functions are often required to be
930 // base pointers.
931 // 2) Result of allocation routines are often base pointers. Leverage TLI.
932 return (isa<AllocaInst>(Val: V) || isa<GlobalVariable>(Val: V));
933}
934
935bool llvm::isEscapeSource(const Value *V) {
936 if (auto *CB = dyn_cast<CallBase>(Val: V)) {
937 if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
938 Call: CB, /*MustPreserveOffset=*/false))
939 return false;
940
941 // The return value of a function with a captures(ret: address, provenance)
942 // attribute is not necessarily an escape source. The return value may
943 // alias with a non-escaping object.
944 return !CB->hasArgumentWithAdditionalReturnCaptureComponents();
945 }
946
947 // The load case works because isNotCapturedBefore considers all
948 // stores to be escapes (it passes true for the StoreCaptures argument
949 // to PointerMayBeCaptured).
950 if (isa<LoadInst>(Val: V))
951 return true;
952
953 // The inttoptr case works because isNotCapturedBefore considers all
954 // means of converting or equating a pointer to an int (ptrtoint, ptr store
955 // which could be followed by an integer load, ptr<->int compare) as
956 // escaping, and objects located at well-known addresses via platform-specific
957 // means cannot be considered non-escaping local objects.
958 if (isa<IntToPtrInst>(Val: V))
959 return true;
960
961 // Capture tracking considers insertions into aggregates and vectors as
962 // captures. As such, extractions from aggregates and vectors are escape
963 // sources.
964 if (isa<ExtractValueInst, ExtractElementInst>(Val: V))
965 return true;
966
967 // Same for inttoptr constant expressions.
968 if (auto *CE = dyn_cast<ConstantExpr>(Val: V))
969 if (CE->getOpcode() == Instruction::IntToPtr)
970 return true;
971
972 return false;
973}
974
975bool llvm::isNotVisibleOnUnwind(const Value *Object,
976 bool &RequiresNoCaptureBeforeUnwind) {
977 RequiresNoCaptureBeforeUnwind = false;
978
979 // Alloca goes out of scope on unwind.
980 if (isa<AllocaInst>(Val: Object))
981 return true;
982
983 // Byval goes out of scope on unwind.
984 if (auto *A = dyn_cast<Argument>(Val: Object))
985 return A->hasByValAttr() || A->hasAttribute(Kind: Attribute::DeadOnUnwind);
986
987 // A noalias return is not accessible from any other code. If the pointer
988 // does not escape prior to the unwind, then the caller cannot access the
989 // memory either.
990 if (isNoAliasCall(V: Object)) {
991 RequiresNoCaptureBeforeUnwind = true;
992 return true;
993 }
994
995 return false;
996}
997
998// We don't consider globals as writable: While the physical memory is writable,
999// we may not have provenance to perform the write.
1000bool llvm::isWritableObject(const Value *Object,
1001 bool &ExplicitlyDereferenceableOnly) {
1002 ExplicitlyDereferenceableOnly = false;
1003
1004 // TODO: Alloca might not be writable after its lifetime ends.
1005 // See https://github.com/llvm/llvm-project/issues/51838.
1006 if (isa<AllocaInst>(Val: Object))
1007 return true;
1008
1009 if (auto *A = dyn_cast<Argument>(Val: Object)) {
1010 // Also require noalias, otherwise writability at function entry cannot be
1011 // generalized to writability at other program points, even if the pointer
1012 // does not escape.
1013 if (A->hasAttribute(Kind: Attribute::Writable) && A->hasNoAliasAttr()) {
1014 ExplicitlyDereferenceableOnly = true;
1015 return true;
1016 }
1017
1018 return A->hasByValAttr();
1019 }
1020
1021 // TODO: Noalias shouldn't imply writability, this should check for an
1022 // allocator function instead.
1023 return isNoAliasCall(V: Object);
1024}
1025