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/ObjCARCAliasAnalysis.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 "llvm/Support/CommandLine.h"
50#include <algorithm>
51#include <cassert>
52#include <functional>
53#include <iterator>
54
55#define DEBUG_TYPE "aa"
56
57using namespace llvm;
58
59STATISTIC(NumNoAlias, "Number of NoAlias results");
60STATISTIC(NumMayAlias, "Number of MayAlias results");
61STATISTIC(NumMustAlias, "Number of MustAlias results");
62
63namespace llvm {
64/// Allow disabling BasicAA from the AA results. This is particularly useful
65/// when testing to isolate a single AA implementation.
66cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(Val: false));
67} // namespace llvm
68
69#ifndef NDEBUG
70/// Print a trace of alias analysis queries and their results.
71static cl::opt<bool> EnableAATrace("aa-trace", cl::Hidden, cl::init(false));
72#else
73static const bool EnableAATrace = false;
74#endif
75
76AAResults::AAResults(AAResults &&Arg)
77 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {}
78
79AAResults::~AAResults() {}
80
81bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
82 FunctionAnalysisManager::Invalidator &Inv) {
83 // AAResults preserves the AAManager by default, due to the stateless nature
84 // of AliasAnalysis. There is no need to check whether it has been preserved
85 // explicitly. Check if any module dependency was invalidated and caused the
86 // AAManager to be invalidated. Invalidate ourselves in that case.
87 auto PAC = PA.getChecker<AAManager>();
88 if (!PAC.preservedWhenStateless())
89 return true;
90
91 // Check if any of the function dependencies were invalidated, and invalidate
92 // ourselves in that case.
93 for (AnalysisKey *ID : AADeps)
94 if (Inv.invalidate(ID, IR&: F, PA))
95 return true;
96
97 // Everything we depend on is still fine, so are we. Nothing to invalidate.
98 return false;
99}
100
101//===----------------------------------------------------------------------===//
102// Default chaining methods
103//===----------------------------------------------------------------------===//
104
105AliasResult AAResults::alias(const MemoryLocation &LocA,
106 const MemoryLocation &LocB) {
107 SimpleAAQueryInfo AAQIP(*this);
108 return alias(LocA, LocB, AAQI&: AAQIP, CtxI: nullptr);
109}
110
111AliasResult AAResults::alias(const MemoryLocation &LocA,
112 const MemoryLocation &LocB, AAQueryInfo &AAQI,
113 const Instruction *CtxI) {
114 AliasResult Result = AliasResult::MayAlias;
115
116 if (EnableAATrace) {
117 for (unsigned I = 0; I < AAQI.Depth; ++I)
118 dbgs() << " ";
119 dbgs() << "Start " << *LocA.Ptr << " @ " << LocA.Size << ", "
120 << *LocB.Ptr << " @ " << LocB.Size << "\n";
121 }
122
123 AAQI.Depth++;
124 for (const auto &AA : AAs) {
125 Result = AA->alias(LocA, LocB, AAQI, CtxI);
126 if (Result != AliasResult::MayAlias)
127 break;
128 }
129 AAQI.Depth--;
130
131 if (EnableAATrace) {
132 for (unsigned I = 0; I < AAQI.Depth; ++I)
133 dbgs() << " ";
134 dbgs() << "End " << *LocA.Ptr << " @ " << LocA.Size << ", "
135 << *LocB.Ptr << " @ " << LocB.Size << " = " << Result << "\n";
136 }
137
138 if (AAQI.Depth == 0) {
139 if (Result == AliasResult::NoAlias)
140 ++NumNoAlias;
141 else if (Result == AliasResult::MustAlias)
142 ++NumMustAlias;
143 else
144 ++NumMayAlias;
145 }
146 return Result;
147}
148
149ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,
150 bool IgnoreLocals) {
151 SimpleAAQueryInfo AAQIP(*this);
152 return getModRefInfoMask(Loc, AAQI&: AAQIP, IgnoreLocals);
153}
154
155ModRefInfo AAResults::getModRefInfoMask(const MemoryLocation &Loc,
156 AAQueryInfo &AAQI, bool IgnoreLocals) {
157 ModRefInfo Result = ModRefInfo::ModRef;
158
159 for (const auto &AA : AAs) {
160 Result &= AA->getModRefInfoMask(Loc, AAQI, IgnoreLocals);
161
162 // Early-exit the moment we reach the bottom of the lattice.
163 if (isNoModRef(MRI: Result))
164 return ModRefInfo::NoModRef;
165 }
166
167 return Result;
168}
169
170ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
171 ModRefInfo Result = ModRefInfo::ModRef;
172
173 for (const auto &AA : AAs) {
174 Result &= AA->getArgModRefInfo(Call, ArgIdx);
175
176 // Early-exit the moment we reach the bottom of the lattice.
177 if (isNoModRef(MRI: Result))
178 return ModRefInfo::NoModRef;
179 }
180
181 return Result;
182}
183
184ModRefInfo AAResults::getModRefInfo(const Instruction *I,
185 const CallBase *Call2) {
186 SimpleAAQueryInfo AAQIP(*this);
187 return getModRefInfo(I, Call2, AAQIP);
188}
189
190ModRefInfo AAResults::getModRefInfo(const Instruction *I, const CallBase *Call2,
191 AAQueryInfo &AAQI) {
192 // We may have two calls.
193 if (const auto *Call1 = dyn_cast<CallBase>(Val: I)) {
194 // Check if the two calls modify the same memory.
195 return getModRefInfo(Call1, Call2, AAQI);
196 }
197 // If this is a fence, just return ModRef.
198 if (I->isFenceLike())
199 return ModRefInfo::ModRef;
200 // Otherwise, check if the call modifies or references the
201 // location this memory access defines. The best we can say
202 // is that if the call references what this instruction
203 // defines, it must be clobbered by this location.
204 const MemoryLocation DefLoc = MemoryLocation::get(Inst: I);
205 ModRefInfo MR = getModRefInfo(Call: Call2, Loc: DefLoc, AAQI);
206 if (isModOrRefSet(MRI: MR))
207 return ModRefInfo::ModRef;
208 return ModRefInfo::NoModRef;
209}
210
211ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
212 const MemoryLocation &Loc,
213 AAQueryInfo &AAQI) {
214 ModRefInfo Result = ModRefInfo::ModRef;
215
216 for (const auto &AA : AAs) {
217 Result &= AA->getModRefInfo(Call, Loc, AAQI);
218
219 // Early-exit the moment we reach the bottom of the lattice.
220 if (isNoModRef(MRI: Result))
221 return ModRefInfo::NoModRef;
222 }
223
224 // Try to refine the mod-ref info further using other API entry points to the
225 // aggregate set of AA results.
226
227 // We can completely ignore inaccessible memory here, because MemoryLocations
228 // can only reference accessible memory.
229 auto ME = getMemoryEffects(Call, AAQI)
230 .getWithoutLoc(Loc: IRMemLocation::InaccessibleMem);
231 if (ME.doesNotAccessMemory())
232 return ModRefInfo::NoModRef;
233
234 ModRefInfo ArgMR = ME.getModRef(Loc: IRMemLocation::ArgMem);
235 ModRefInfo OtherMR = ME.getWithoutLoc(Loc: IRMemLocation::ArgMem).getModRef();
236 if ((ArgMR | OtherMR) != OtherMR) {
237 // Refine the modref info for argument memory. We only bother to do this
238 // if ArgMR is not a subset of OtherMR, otherwise this won't have an impact
239 // on the final result.
240 ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
241 for (const auto &I : llvm::enumerate(First: Call->args())) {
242 const Value *Arg = I.value();
243 if (!Arg->getType()->isPointerTy())
244 continue;
245 unsigned ArgIdx = I.index();
246 MemoryLocation ArgLoc = MemoryLocation::getForArgument(Call, ArgIdx, TLI);
247 AliasResult ArgAlias = alias(LocA: ArgLoc, LocB: Loc, AAQI, CtxI: Call);
248 if (ArgAlias != AliasResult::NoAlias)
249 AllArgsMask |= getArgModRefInfo(Call, ArgIdx);
250 }
251 ArgMR &= AllArgsMask;
252 }
253
254 Result &= ArgMR | OtherMR;
255
256 // Apply the ModRef mask. This ensures that if Loc is a constant memory
257 // location, we take into account the fact that the call definitely could not
258 // modify the memory location.
259 if (!isNoModRef(MRI: Result))
260 Result &= getModRefInfoMask(Loc);
261
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 return Result;
370}
371
372MemoryEffects AAResults::getMemoryEffects(const CallBase *Call,
373 AAQueryInfo &AAQI) {
374 MemoryEffects Result = MemoryEffects::unknown();
375
376 for (const auto &AA : AAs) {
377 Result &= AA->getMemoryEffects(Call, AAQI);
378
379 // Early-exit the moment we reach the bottom of the lattice.
380 if (Result.doesNotAccessMemory())
381 return Result;
382 }
383
384 return Result;
385}
386
387MemoryEffects AAResults::getMemoryEffects(const CallBase *Call) {
388 SimpleAAQueryInfo AAQI(*this);
389 return getMemoryEffects(Call, AAQI);
390}
391
392MemoryEffects AAResults::getMemoryEffects(const Function *F) {
393 MemoryEffects Result = MemoryEffects::unknown();
394
395 for (const auto &AA : AAs) {
396 Result &= AA->getMemoryEffects(F);
397
398 // Early-exit the moment we reach the bottom of the lattice.
399 if (Result.doesNotAccessMemory())
400 return Result;
401 }
402
403 return Result;
404}
405
406raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
407 switch (AR) {
408 case AliasResult::NoAlias:
409 OS << "NoAlias";
410 break;
411 case AliasResult::MustAlias:
412 OS << "MustAlias";
413 break;
414 case AliasResult::MayAlias:
415 OS << "MayAlias";
416 break;
417 case AliasResult::PartialAlias:
418 OS << "PartialAlias";
419 if (AR.hasOffset())
420 OS << " (off " << AR.getOffset() << ")";
421 break;
422 }
423 return OS;
424}
425
426raw_ostream &llvm::operator<<(raw_ostream &OS, ModRefInfo MR) {
427 switch (MR) {
428 case ModRefInfo::NoModRef:
429 OS << "NoModRef";
430 break;
431 case ModRefInfo::Ref:
432 OS << "Ref";
433 break;
434 case ModRefInfo::Mod:
435 OS << "Mod";
436 break;
437 case ModRefInfo::ModRef:
438 OS << "ModRef";
439 break;
440 }
441 return OS;
442}
443
444raw_ostream &llvm::operator<<(raw_ostream &OS, MemoryEffects ME) {
445 for (IRMemLocation Loc : MemoryEffects::locations()) {
446 switch (Loc) {
447 case IRMemLocation::ArgMem:
448 OS << "ArgMem: ";
449 break;
450 case IRMemLocation::InaccessibleMem:
451 OS << "InaccessibleMem: ";
452 break;
453 case IRMemLocation::Other:
454 OS << "Other: ";
455 break;
456 }
457 OS << ME.getModRef(Loc) << ", ";
458 }
459 return OS;
460}
461
462//===----------------------------------------------------------------------===//
463// Helper method implementation
464//===----------------------------------------------------------------------===//
465
466ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
467 const MemoryLocation &Loc,
468 AAQueryInfo &AAQI) {
469 // Be conservative in the face of atomic.
470 if (isStrongerThan(AO: L->getOrdering(), Other: AtomicOrdering::Unordered))
471 return ModRefInfo::ModRef;
472
473 // If the load address doesn't alias the given address, it doesn't read
474 // or write the specified memory.
475 if (Loc.Ptr) {
476 AliasResult AR = alias(LocA: MemoryLocation::get(LI: L), LocB: Loc, AAQI, CtxI: L);
477 if (AR == AliasResult::NoAlias)
478 return ModRefInfo::NoModRef;
479 }
480 // Otherwise, a load just reads.
481 return ModRefInfo::Ref;
482}
483
484ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
485 const MemoryLocation &Loc,
486 AAQueryInfo &AAQI) {
487 // Be conservative in the face of atomic.
488 if (isStrongerThan(AO: S->getOrdering(), Other: AtomicOrdering::Unordered))
489 return ModRefInfo::ModRef;
490
491 if (Loc.Ptr) {
492 AliasResult AR = alias(LocA: MemoryLocation::get(SI: S), LocB: Loc, AAQI, CtxI: S);
493 // If the store address cannot alias the pointer in question, then the
494 // specified memory cannot be modified by the store.
495 if (AR == AliasResult::NoAlias)
496 return ModRefInfo::NoModRef;
497
498 // Examine the ModRef mask. If Mod isn't present, then return NoModRef.
499 // This ensures that if Loc is a constant memory location, we take into
500 // account the fact that the store definitely could not modify the memory
501 // location.
502 if (!isModSet(MRI: getModRefInfoMask(Loc)))
503 return ModRefInfo::NoModRef;
504 }
505
506 // Otherwise, a store just writes.
507 return ModRefInfo::Mod;
508}
509
510ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
511 const MemoryLocation &Loc,
512 AAQueryInfo &AAQI) {
513 // All we know about a fence instruction is what we get from the ModRef
514 // mask: if Loc is a constant memory location, the fence definitely could
515 // not modify it.
516 if (Loc.Ptr)
517 return getModRefInfoMask(Loc);
518 return ModRefInfo::ModRef;
519}
520
521ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
522 const MemoryLocation &Loc,
523 AAQueryInfo &AAQI) {
524 if (Loc.Ptr) {
525 AliasResult AR = alias(LocA: MemoryLocation::get(VI: V), LocB: Loc, AAQI, CtxI: V);
526 // If the va_arg address cannot alias the pointer in question, then the
527 // specified memory cannot be accessed by the va_arg.
528 if (AR == AliasResult::NoAlias)
529 return ModRefInfo::NoModRef;
530
531 // If the pointer is a pointer to invariant memory, then it could not have
532 // been modified by this va_arg.
533 return getModRefInfoMask(Loc, AAQI);
534 }
535
536 // Otherwise, a va_arg reads and writes.
537 return ModRefInfo::ModRef;
538}
539
540ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
541 const MemoryLocation &Loc,
542 AAQueryInfo &AAQI) {
543 if (Loc.Ptr) {
544 // If the pointer is a pointer to invariant memory,
545 // then it could not have been modified by this catchpad.
546 return getModRefInfoMask(Loc, AAQI);
547 }
548
549 // Otherwise, a catchpad reads and writes.
550 return ModRefInfo::ModRef;
551}
552
553ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
554 const MemoryLocation &Loc,
555 AAQueryInfo &AAQI) {
556 if (Loc.Ptr) {
557 // If the pointer is a pointer to invariant memory,
558 // then it could not have been modified by this catchpad.
559 return getModRefInfoMask(Loc, AAQI);
560 }
561
562 // Otherwise, a catchret reads and writes.
563 return ModRefInfo::ModRef;
564}
565
566ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
567 const MemoryLocation &Loc,
568 AAQueryInfo &AAQI) {
569 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
570 if (isStrongerThanMonotonic(AO: CX->getSuccessOrdering()))
571 return ModRefInfo::ModRef;
572
573 if (Loc.Ptr) {
574 AliasResult AR = alias(LocA: MemoryLocation::get(CXI: CX), LocB: Loc, AAQI, CtxI: CX);
575 // If the cmpxchg address does not alias the location, it does not access
576 // it.
577 if (AR == AliasResult::NoAlias)
578 return ModRefInfo::NoModRef;
579 }
580
581 return ModRefInfo::ModRef;
582}
583
584ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
585 const MemoryLocation &Loc,
586 AAQueryInfo &AAQI) {
587 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
588 if (isStrongerThanMonotonic(AO: RMW->getOrdering()))
589 return ModRefInfo::ModRef;
590
591 if (Loc.Ptr) {
592 AliasResult AR = alias(LocA: MemoryLocation::get(RMWI: RMW), LocB: Loc, AAQI, CtxI: RMW);
593 // If the atomicrmw address does not alias the location, it does not access
594 // it.
595 if (AR == AliasResult::NoAlias)
596 return ModRefInfo::NoModRef;
597 }
598
599 return ModRefInfo::ModRef;
600}
601
602ModRefInfo AAResults::getModRefInfo(const Instruction *I,
603 const std::optional<MemoryLocation> &OptLoc,
604 AAQueryInfo &AAQIP) {
605 if (OptLoc == std::nullopt) {
606 if (const auto *Call = dyn_cast<CallBase>(Val: I))
607 return getMemoryEffects(Call, AAQI&: AAQIP).getModRef();
608 }
609
610 const MemoryLocation &Loc = OptLoc.value_or(u: MemoryLocation());
611
612 switch (I->getOpcode()) {
613 case Instruction::VAArg:
614 return getModRefInfo(V: (const VAArgInst *)I, Loc, AAQI&: AAQIP);
615 case Instruction::Load:
616 return getModRefInfo(L: (const LoadInst *)I, Loc, AAQI&: AAQIP);
617 case Instruction::Store:
618 return getModRefInfo(S: (const StoreInst *)I, Loc, AAQI&: AAQIP);
619 case Instruction::Fence:
620 return getModRefInfo(S: (const FenceInst *)I, Loc, AAQI&: AAQIP);
621 case Instruction::AtomicCmpXchg:
622 return getModRefInfo(CX: (const AtomicCmpXchgInst *)I, Loc, AAQI&: AAQIP);
623 case Instruction::AtomicRMW:
624 return getModRefInfo(RMW: (const AtomicRMWInst *)I, Loc, AAQI&: AAQIP);
625 case Instruction::Call:
626 case Instruction::CallBr:
627 case Instruction::Invoke:
628 return getModRefInfo(Call: (const CallBase *)I, Loc, AAQI&: AAQIP);
629 case Instruction::CatchPad:
630 return getModRefInfo(CatchPad: (const CatchPadInst *)I, Loc, AAQI&: AAQIP);
631 case Instruction::CatchRet:
632 return getModRefInfo(CatchRet: (const CatchReturnInst *)I, Loc, AAQI&: AAQIP);
633 default:
634 assert(!I->mayReadOrWriteMemory() &&
635 "Unhandled memory access instruction!");
636 return ModRefInfo::NoModRef;
637 }
638}
639
640/// Return information about whether a particular call site modifies
641/// or reads the specified memory location \p MemLoc before instruction \p I
642/// in a BasicBlock.
643/// FIXME: this is really just shoring-up a deficiency in alias analysis.
644/// BasicAA isn't willing to spend linear time determining whether an alloca
645/// was captured before or after this particular call, while we are. However,
646/// with a smarter AA in place, this test is just wasting compile time.
647ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
648 const MemoryLocation &MemLoc,
649 DominatorTree *DT,
650 AAQueryInfo &AAQI) {
651 if (!DT)
652 return ModRefInfo::ModRef;
653
654 const Value *Object = getUnderlyingObject(V: MemLoc.Ptr);
655 if (!isIdentifiedFunctionLocal(V: Object))
656 return ModRefInfo::ModRef;
657
658 const auto *Call = dyn_cast<CallBase>(Val: I);
659 if (!Call || Call == Object)
660 return ModRefInfo::ModRef;
661
662 if (PointerMayBeCapturedBefore(V: Object, /* ReturnCaptures */ true,
663 /* StoreCaptures */ true, I, DT,
664 /* include Object */ IncludeI: true))
665 return ModRefInfo::ModRef;
666
667 unsigned ArgNo = 0;
668 ModRefInfo R = ModRefInfo::NoModRef;
669 // Set flag only if no May found and all operands processed.
670 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
671 CI != CE; ++CI, ++ArgNo) {
672 // Only look at the no-capture or byval pointer arguments. If this
673 // pointer were passed to arguments that were neither of these, then it
674 // couldn't be no-capture.
675 if (!(*CI)->getType()->isPointerTy() ||
676 (!Call->doesNotCapture(OpNo: ArgNo) && ArgNo < Call->arg_size() &&
677 !Call->isByValArgument(ArgNo)))
678 continue;
679
680 AliasResult AR =
681 alias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: *CI),
682 LocB: MemoryLocation::getBeforeOrAfter(Ptr: Object), AAQI, CtxI: Call);
683 // If this is a no-capture pointer argument, see if we can tell that it
684 // is impossible to alias the pointer we're checking. If not, we have to
685 // assume that the call could touch the pointer, even though it doesn't
686 // escape.
687 if (AR == AliasResult::NoAlias)
688 continue;
689 if (Call->doesNotAccessMemory(OpNo: ArgNo))
690 continue;
691 if (Call->onlyReadsMemory(OpNo: ArgNo)) {
692 R = ModRefInfo::Ref;
693 continue;
694 }
695 return ModRefInfo::ModRef;
696 }
697 return R;
698}
699
700/// canBasicBlockModify - Return true if it is possible for execution of the
701/// specified basic block to modify the location Loc.
702///
703bool AAResults::canBasicBlockModify(const BasicBlock &BB,
704 const MemoryLocation &Loc) {
705 return canInstructionRangeModRef(I1: BB.front(), I2: BB.back(), Loc, Mode: ModRefInfo::Mod);
706}
707
708/// canInstructionRangeModRef - Return true if it is possible for the
709/// execution of the specified instructions to mod\ref (according to the
710/// mode) the location Loc. The instructions to consider are all
711/// of the instructions in the range of [I1,I2] INCLUSIVE.
712/// I1 and I2 must be in the same basic block.
713bool AAResults::canInstructionRangeModRef(const Instruction &I1,
714 const Instruction &I2,
715 const MemoryLocation &Loc,
716 const ModRefInfo Mode) {
717 assert(I1.getParent() == I2.getParent() &&
718 "Instructions not in same basic block!");
719 BasicBlock::const_iterator I = I1.getIterator();
720 BasicBlock::const_iterator E = I2.getIterator();
721 ++E; // Convert from inclusive to exclusive range.
722
723 for (; I != E; ++I) // Check every instruction in range
724 if (isModOrRefSet(MRI: getModRefInfo(I: &*I, OptLoc: Loc) & Mode))
725 return true;
726 return false;
727}
728
729// Provide a definition for the root virtual destructor.
730AAResults::Concept::~Concept() = default;
731
732// Provide a definition for the static object used to identify passes.
733AnalysisKey AAManager::Key;
734
735ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {
736 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
737}
738
739ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB)
740 : ImmutablePass(ID), CB(std::move(CB)) {
741 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
742}
743
744char ExternalAAWrapperPass::ID = 0;
745
746INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
747 false, true)
748
749ImmutablePass *
750llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
751 return new ExternalAAWrapperPass(std::move(Callback));
752}
753
754AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
755 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
756}
757
758char AAResultsWrapperPass::ID = 0;
759
760INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
761 "Function Alias Analysis Results", false, true)
762INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
763INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
764INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
765INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
766INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
767INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
768INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
769 "Function Alias Analysis Results", false, true)
770
771/// Run the wrapper pass to rebuild an aggregation over known AA passes.
772///
773/// This is the legacy pass manager's interface to the new-style AA results
774/// aggregation object. Because this is somewhat shoe-horned into the legacy
775/// pass manager, we hard code all the specific alias analyses available into
776/// it. While the particular set enabled is configured via commandline flags,
777/// adding a new alias analysis to LLVM will require adding support for it to
778/// this list.
779bool AAResultsWrapperPass::runOnFunction(Function &F) {
780 // NB! This *must* be reset before adding new AA results to the new
781 // AAResults object because in the legacy pass manager, each instance
782 // of these will refer to the *same* immutable analyses, registering and
783 // unregistering themselves with them. We need to carefully tear down the
784 // previous object first, in this case replacing it with an empty one, before
785 // registering new results.
786 AAR.reset(
787 p: new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
788
789 // BasicAA is always available for function analyses. Also, we add it first
790 // so that it can trump TBAA results when it proves MustAlias.
791 // FIXME: TBAA should have an explicit mode to support this and then we
792 // should reconsider the ordering here.
793 if (!DisableBasicAA)
794 AAR->addAAResult(AAResult&: getAnalysis<BasicAAWrapperPass>().getResult());
795
796 // Populate the results with the currently available AAs.
797 if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
798 AAR->addAAResult(AAResult&: WrapperPass->getResult());
799 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
800 AAR->addAAResult(AAResult&: WrapperPass->getResult());
801 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
802 AAR->addAAResult(AAResult&: WrapperPass->getResult());
803 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
804 AAR->addAAResult(AAResult&: WrapperPass->getResult());
805
806 // If available, run an external AA providing callback over the results as
807 // well.
808 if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
809 if (WrapperPass->CB)
810 WrapperPass->CB(*this, F, *AAR);
811
812 // Analyses don't mutate the IR, so return false.
813 return false;
814}
815
816void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
817 AU.setPreservesAll();
818 AU.addRequiredTransitive<BasicAAWrapperPass>();
819 AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
820
821 // We also need to mark all the alias analysis passes we will potentially
822 // probe in runOnFunction as used here to ensure the legacy pass manager
823 // preserves them. This hard coding of lists of alias analyses is specific to
824 // the legacy pass manager.
825 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
826 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
827 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
828 AU.addUsedIfAvailable<SCEVAAWrapperPass>();
829 AU.addUsedIfAvailable<ExternalAAWrapperPass>();
830}
831
832AAManager::Result AAManager::run(Function &F, FunctionAnalysisManager &AM) {
833 Result R(AM.getResult<TargetLibraryAnalysis>(IR&: F));
834 for (auto &Getter : ResultGetters)
835 (*Getter)(F, AM, R);
836 return R;
837}
838
839bool llvm::isNoAliasCall(const Value *V) {
840 if (const auto *Call = dyn_cast<CallBase>(Val: V))
841 return Call->hasRetAttr(Kind: Attribute::NoAlias);
842 return false;
843}
844
845static bool isNoAliasOrByValArgument(const Value *V) {
846 if (const Argument *A = dyn_cast<Argument>(Val: V))
847 return A->hasNoAliasAttr() || A->hasByValAttr();
848 return false;
849}
850
851bool llvm::isIdentifiedObject(const Value *V) {
852 if (isa<AllocaInst>(Val: V))
853 return true;
854 if (isa<GlobalValue>(Val: V) && !isa<GlobalAlias>(Val: V))
855 return true;
856 if (isNoAliasCall(V))
857 return true;
858 if (isNoAliasOrByValArgument(V))
859 return true;
860 return false;
861}
862
863bool llvm::isIdentifiedFunctionLocal(const Value *V) {
864 return isa<AllocaInst>(Val: V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);
865}
866
867bool llvm::isEscapeSource(const Value *V) {
868 if (auto *CB = dyn_cast<CallBase>(Val: V))
869 return !isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(Call: CB,
870 MustPreserveNullness: true);
871
872 // The load case works because isNonEscapingLocalObject considers all
873 // stores to be escapes (it passes true for the StoreCaptures argument
874 // to PointerMayBeCaptured).
875 if (isa<LoadInst>(Val: V))
876 return true;
877
878 // The inttoptr case works because isNonEscapingLocalObject considers all
879 // means of converting or equating a pointer to an int (ptrtoint, ptr store
880 // which could be followed by an integer load, ptr<->int compare) as
881 // escaping, and objects located at well-known addresses via platform-specific
882 // means cannot be considered non-escaping local objects.
883 if (isa<IntToPtrInst>(Val: V))
884 return true;
885
886 // Same for inttoptr constant expressions.
887 if (auto *CE = dyn_cast<ConstantExpr>(Val: V))
888 if (CE->getOpcode() == Instruction::IntToPtr)
889 return true;
890
891 return false;
892}
893
894bool llvm::isNotVisibleOnUnwind(const Value *Object,
895 bool &RequiresNoCaptureBeforeUnwind) {
896 RequiresNoCaptureBeforeUnwind = false;
897
898 // Alloca goes out of scope on unwind.
899 if (isa<AllocaInst>(Val: Object))
900 return true;
901
902 // Byval goes out of scope on unwind.
903 if (auto *A = dyn_cast<Argument>(Val: Object))
904 return A->hasByValAttr() || A->hasAttribute(Kind: Attribute::DeadOnUnwind);
905
906 // A noalias return is not accessible from any other code. If the pointer
907 // does not escape prior to the unwind, then the caller cannot access the
908 // memory either.
909 if (isNoAliasCall(V: Object)) {
910 RequiresNoCaptureBeforeUnwind = true;
911 return true;
912 }
913
914 return false;
915}
916
917// We don't consider globals as writable: While the physical memory is writable,
918// we may not have provenance to perform the write.
919bool llvm::isWritableObject(const Value *Object,
920 bool &ExplicitlyDereferenceableOnly) {
921 ExplicitlyDereferenceableOnly = false;
922
923 // TODO: Alloca might not be writable after its lifetime ends.
924 // See https://github.com/llvm/llvm-project/issues/51838.
925 if (isa<AllocaInst>(Val: Object))
926 return true;
927
928 if (auto *A = dyn_cast<Argument>(Val: Object)) {
929 if (A->hasAttribute(Kind: Attribute::Writable)) {
930 ExplicitlyDereferenceableOnly = true;
931 return true;
932 }
933
934 return A->hasByValAttr();
935 }
936
937 // TODO: Noalias shouldn't imply writability, this should check for an
938 // allocator function instead.
939 return isNoAliasCall(V: Object);
940}
941