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