LLVM 19.0.0git
AliasAnalysis.cpp
Go to the documentation of this file.
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
27#include "llvm/ADT/Statistic.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"
43#include "llvm/IR/Type.h"
44#include "llvm/IR/Value.h"
46#include "llvm/Pass.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(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
77 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {}
78
80
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, 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
106 const MemoryLocation &LocB) {
107 SimpleAAQueryInfo AAQIP(*this);
108 return alias(LocA, LocB, AAQIP, nullptr);
109}
110
112 const MemoryLocation &LocB, AAQueryInfo &AAQI,
113 const Instruction *CtxI) {
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
150 bool IgnoreLocals) {
151 SimpleAAQueryInfo AAQIP(*this);
152 return getModRefInfoMask(Loc, AAQIP, IgnoreLocals);
153}
154
156 AAQueryInfo &AAQI, bool IgnoreLocals) {
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(Result))
165 }
166
167 return Result;
168}
169
170ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
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(Result))
179 }
180
181 return Result;
182}
183
185 const CallBase *Call2) {
186 SimpleAAQueryInfo AAQIP(*this);
187 return getModRefInfo(I, Call2, AAQIP);
188}
189
191 AAQueryInfo &AAQI) {
192 // We may have two calls.
193 if (const auto *Call1 = dyn_cast<CallBase>(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(I);
205 ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
206 if (isModOrRefSet(MR))
207 return ModRefInfo::ModRef;
209}
210
212 const MemoryLocation &Loc,
213 AAQueryInfo &AAQI) {
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(Result))
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)
231 if (ME.doesNotAccessMemory())
233
234 ModRefInfo ArgMR = ME.getModRef(IRMemLocation::ArgMem);
235 ModRefInfo OtherMR = ME.getWithoutLoc(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(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(ArgLoc, Loc, AAQI, 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(Result))
260 Result &= getModRefInfoMask(Loc);
261
262 return Result;
263}
264
266 const CallBase *Call2, AAQueryInfo &AAQI) {
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(Result))
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(Call1, AAQI);
282 if (Call1B.doesNotAccessMemory())
284
285 auto Call2B = getMemoryEffects(Call2, AAQI);
286 if (Call2B.doesNotAccessMemory())
288
289 // If they both only read from memory, there is no dependence.
290 if (Call1B.onlyReadsMemory() && Call2B.onlyReadsMemory())
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())
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(Call2->arg_begin(), I);
312 auto Call2ArgLoc =
313 MemoryLocation::getForArgument(Call2, 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(Call2, Call2ArgIdx);
322 if (isModSet(ArgModRefC2))
323 ArgMask = ModRefInfo::ModRef;
324 else if (isRefSet(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(Call1, 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())
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(Call1->arg_begin(), I);
350 auto Call1ArgLoc =
351 MemoryLocation::getForArgument(Call1, 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(Call1, Call1ArgIdx);
357 ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);
358 if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
359 (isRefSet(ArgModRefC1) && isModSet(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
373 AAQueryInfo &AAQI) {
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
388 SimpleAAQueryInfo AAQI(*this);
389 return getMemoryEffects(Call, AAQI);
390}
391
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
407 switch (AR) {
409 OS << "NoAlias";
410 break;
412 OS << "MustAlias";
413 break;
415 OS << "MayAlias";
416 break;
418 OS << "PartialAlias";
419 if (AR.hasOffset())
420 OS << " (off " << AR.getOffset() << ")";
421 break;
422 }
423 return OS;
424}
425
427 switch (MR) {
429 OS << "NoModRef";
430 break;
431 case ModRefInfo::Ref:
432 OS << "Ref";
433 break;
434 case ModRefInfo::Mod:
435 OS << "Mod";
436 break;
438 OS << "ModRef";
439 break;
440 }
441 return OS;
442}
443
446 switch (Loc) {
448 OS << "ArgMem: ";
449 break;
451 OS << "InaccessibleMem: ";
452 break;
454 OS << "Other: ";
455 break;
456 }
457 OS << ME.getModRef(Loc) << ", ";
458 }
459 return OS;
460}
461
462//===----------------------------------------------------------------------===//
463// Helper method implementation
464//===----------------------------------------------------------------------===//
465
467 const MemoryLocation &Loc,
468 AAQueryInfo &AAQI) {
469 // Be conservative in the face of atomic.
470 if (isStrongerThan(L->getOrdering(), 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(MemoryLocation::get(L), Loc, AAQI, L);
477 if (AR == AliasResult::NoAlias)
479 }
480 // Otherwise, a load just reads.
481 return ModRefInfo::Ref;
482}
483
485 const MemoryLocation &Loc,
486 AAQueryInfo &AAQI) {
487 // Be conservative in the face of atomic.
489 return ModRefInfo::ModRef;
490
491 if (Loc.Ptr) {
492 AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI, 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)
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(getModRefInfoMask(Loc)))
504 }
505
506 // Otherwise, a store just writes.
507 return ModRefInfo::Mod;
508}
509
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
522 const MemoryLocation &Loc,
523 AAQueryInfo &AAQI) {
524 if (Loc.Ptr) {
525 AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI, 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)
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
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
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
567 const MemoryLocation &Loc,
568 AAQueryInfo &AAQI) {
569 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
571 return ModRefInfo::ModRef;
572
573 if (Loc.Ptr) {
574 AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI, CX);
575 // If the cmpxchg address does not alias the location, it does not access
576 // it.
577 if (AR == AliasResult::NoAlias)
579 }
580
581 return ModRefInfo::ModRef;
582}
583
585 const MemoryLocation &Loc,
586 AAQueryInfo &AAQI) {
587 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
589 return ModRefInfo::ModRef;
590
591 if (Loc.Ptr) {
592 AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI, RMW);
593 // If the atomicrmw address does not alias the location, it does not access
594 // it.
595 if (AR == AliasResult::NoAlias)
597 }
598
599 return ModRefInfo::ModRef;
600}
601
603 const std::optional<MemoryLocation> &OptLoc,
604 AAQueryInfo &AAQIP) {
605 if (OptLoc == std::nullopt) {
606 if (const auto *Call = dyn_cast<CallBase>(I))
607 return getMemoryEffects(Call, AAQIP).getModRef();
608 }
609
610 const MemoryLocation &Loc = OptLoc.value_or(MemoryLocation());
611
612 switch (I->getOpcode()) {
613 case Instruction::VAArg:
614 return getModRefInfo((const VAArgInst *)I, Loc, AAQIP);
615 case Instruction::Load:
616 return getModRefInfo((const LoadInst *)I, Loc, AAQIP);
617 case Instruction::Store:
618 return getModRefInfo((const StoreInst *)I, Loc, AAQIP);
619 case Instruction::Fence:
620 return getModRefInfo((const FenceInst *)I, Loc, AAQIP);
621 case Instruction::AtomicCmpXchg:
622 return getModRefInfo((const AtomicCmpXchgInst *)I, Loc, AAQIP);
623 case Instruction::AtomicRMW:
624 return getModRefInfo((const AtomicRMWInst *)I, Loc, AAQIP);
625 case Instruction::Call:
626 case Instruction::CallBr:
627 case Instruction::Invoke:
628 return getModRefInfo((const CallBase *)I, Loc, AAQIP);
629 case Instruction::CatchPad:
630 return getModRefInfo((const CatchPadInst *)I, Loc, AAQIP);
631 case Instruction::CatchRet:
632 return getModRefInfo((const CatchReturnInst *)I, Loc, AAQIP);
633 default:
634 assert(!I->mayReadOrWriteMemory() &&
635 "Unhandled memory access instruction!");
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.
648 const MemoryLocation &MemLoc,
649 DominatorTree *DT,
650 AAQueryInfo &AAQI) {
651 if (!DT)
652 return ModRefInfo::ModRef;
653
654 const Value *Object = getUnderlyingObject(MemLoc.Ptr);
655 if (!isIdentifiedFunctionLocal(Object))
656 return ModRefInfo::ModRef;
657
658 const auto *Call = dyn_cast<CallBase>(I);
659 if (!Call || Call == Object)
660 return ModRefInfo::ModRef;
661
662 if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
663 /* StoreCaptures */ true, I, DT,
664 /* include Object */ true))
665 return ModRefInfo::ModRef;
666
667 unsigned ArgNo = 0;
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(ArgNo) && ArgNo < Call->arg_size() &&
677 !Call->isByValArgument(ArgNo)))
678 continue;
679
680 AliasResult AR =
682 MemoryLocation::getBeforeOrAfter(Object), AAQI, 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(ArgNo))
690 continue;
691 if (Call->onlyReadsMemory(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///
704 const MemoryLocation &Loc) {
705 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, 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.
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();
721 ++E; // Convert from inclusive to exclusive range.
722
723 for (; I != E; ++I) // Check every instruction in range
724 if (isModOrRefSet(getModRefInfo(&*I, Loc) & Mode))
725 return true;
726 return false;
727}
728
729// Provide a definition for the root virtual destructor.
731
732// Provide a definition for the static object used to identify passes.
733AnalysisKey AAManager::Key;
734
737}
738
740 : ImmutablePass(ID), CB(std::move(CB)) {
742}
743
745
746INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
747 false, true)
748
751 return new ExternalAAWrapperPass(std::move(Callback));
752}
753
756}
757
759
761 "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.
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 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(getAnalysis<BasicAAWrapperPass>().getResult());
795
796 // Populate the results with the currently available AAs.
797 if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
798 AAR->addAAResult(WrapperPass->getResult());
799 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
800 AAR->addAAResult(WrapperPass->getResult());
801 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
802 AAR->addAAResult(WrapperPass->getResult());
803 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
804 AAR->addAAResult(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
817 AU.setPreservesAll();
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.
830}
831
834 for (auto &Getter : ResultGetters)
835 (*Getter)(F, AM, R);
836 return R;
837}
838
840 if (const auto *Call = dyn_cast<CallBase>(V))
841 return Call->hasRetAttr(Attribute::NoAlias);
842 return false;
843}
844
845static bool isNoAliasOrByValArgument(const Value *V) {
846 if (const Argument *A = dyn_cast<Argument>(V))
847 return A->hasNoAliasAttr() || A->hasByValAttr();
848 return false;
849}
850
852 if (isa<AllocaInst>(V))
853 return true;
854 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
855 return true;
856 if (isNoAliasCall(V))
857 return true;
859 return true;
860 return false;
861}
862
864 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasOrByValArgument(V);
865}
866
868 if (auto *CB = dyn_cast<CallBase>(V))
870 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>(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>(V))
884 return true;
885
886 // Same for inttoptr constant expressions.
887 if (auto *CE = dyn_cast<ConstantExpr>(V))
888 if (CE->getOpcode() == Instruction::IntToPtr)
889 return true;
890
891 return false;
892}
893
895 bool &RequiresNoCaptureBeforeUnwind) {
896 RequiresNoCaptureBeforeUnwind = false;
897
898 // Alloca goes out of scope on unwind.
899 if (isa<AllocaInst>(Object))
900 return true;
901
902 // Byval goes out of scope on unwind.
903 if (auto *A = dyn_cast<Argument>(Object))
904 return A->hasByValAttr() || A->hasAttribute(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(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>(Object))
926 return true;
927
928 if (auto *A = dyn_cast<Argument>(Object)) {
929 if (A->hasAttribute(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(Object);
940}
static cl::opt< bool > EnableAATrace("aa-trace", cl::Hidden, cl::init(false))
Print a trace of alias analysis queries and their results.
static bool isNoAliasOrByValArgument(const Value *V)
Function Alias Analysis Results
Atomic ordering constants.
This file contains the simple types necessary to represent the attributes associated with functions a...
basic Basic Alias true
This is the interface for LLVM's primary stateless and local alias analysis.
block Block Frequency Analysis
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file provides utility analysis objects describing memory locations.
This file declares a simple ARC-aware AliasAnalysis using special knowledge of Objective C to enhance...
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This is the interface for a SCEV-based alias analysis.
This is the interface for a metadata-based scoped no-alias analysis.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This is the interface for a metadata-based TBAA.
A manager for alias analyses.
Result run(Function &F, FunctionAnalysisManager &AM)
This class stores info we want to provide to or retain within an alias query.
unsigned Depth
Query depth used to distinguish recursive queries.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Check whether or not an instruction may read or write the optionally specified memory location.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Return information about whether a particular call site modifies or reads the specified memory locati...
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
AAResults(const TargetLibraryInfo &TLI)
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
bool canInstructionRangeModRef(const Instruction &I1, const Instruction &I2, const MemoryLocation &Loc, const ModRefInfo Mode)
Check if it is possible for the execution of the specified instructions to mod(according to the mode)...
bool canBasicBlockModify(const BasicBlock &BB, const MemoryLocation &Loc)
Check if it is possible for execution of the specified basic block to modify the location Loc.
The possible results of an alias query.
Definition: AliasAnalysis.h:81
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:387
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:405
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Represent the analysis usage information of a pass.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:539
AtomicOrdering getSuccessOrdering() const
Returns the success ordering constraint of this cmpxchg instruction.
Definition: Instructions.h:626
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:748
AtomicOrdering getOrdering() const
Returns the ordering constraint of this rmw instruction.
Definition: Instructions.h:887
Legacy wrapper pass to provide the BasicAAResult object.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:165
const Instruction & front() const
Definition: BasicBlock.h:452
const Instruction & back() const
Definition: BasicBlock.h:454
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1455
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1623
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1629
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
An instruction for ordering other memory operations.
Definition: Instructions.h:460
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Legacy wrapper pass to provide the GlobalsAAResult object.
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:282
const BasicBlock * getParent() const
Definition: Instruction.h:151
An instruction for reading from memory.
Definition: Instructions.h:184
MemoryEffectsBase getWithoutLoc(Location Loc) const
Get new MemoryEffectsBase with NoModRef on the given Loc.
Definition: ModRef.h:177
ModRefInfo getModRef(Location Loc) const
Get ModRefInfo for the given Location.
Definition: ModRef.h:165
static auto locations()
Returns iterator over all supported location kinds.
Definition: ModRef.h:95
static MemoryEffectsBase unknown()
Create MemoryEffectsBase that can read and write any memory.
Definition: ModRef.h:112
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
const Value * Ptr
The address of the start of the location.
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
Legacy wrapper pass to provide the SCEVAAResult object.
Legacy wrapper pass to provide the ScopedNoAliasAAResult object.
AAQueryInfo that uses SimpleCaptureInfo.
An instruction for storing to memory.
Definition: Instructions.h:317
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Definition: Instructions.h:378
Analysis pass providing the TargetLibraryInfo.
Legacy wrapper pass to provide the TypeBasedAAResult object.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
self_iterator getIterator()
Definition: ilist_node.h:109
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
cl::opt< bool > DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(false))
Allow disabling BasicAA from the AA results.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2415
bool isStrongerThanMonotonic(AtomicOrdering AO)
bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, bool StoreCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
void initializeAAResultsWrapperPassPass(PassRegistry &)
bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(const CallBase *Call, bool MustPreserveNullness)
{launder,strip}.invariant.group returns pointer that aliases its argument, and it only captures point...
bool isModSet(const ModRefInfo MRI)
Definition: ModRef.h:48
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isModOrRefSet(const ModRefInfo MRI)
Definition: ModRef.h:42
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: ModRef.h:27
@ Ref
The access may reference the value stored in memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
IRMemLocation
The locations at which a function might access memory.
Definition: ModRef.h:59
@ ArgMem
Access to memory via argument pointers.
@ Other
Any other memory.
@ InaccessibleMem
Memory that is inaccessible via LLVM IR.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...
ImmutablePass * createExternalAAWrapperPass(std::function< void(Pass &, Function &, AAResults &)> Callback)
A wrapper pass around a callback which can be used to populate the AAResults in the AAResultsWrapperP...
void initializeExternalAAWrapperPassPass(PassRegistry &)
bool isNoModRef(const ModRefInfo MRI)
Definition: ModRef.h:39
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
bool isRefSet(const ModRefInfo MRI)
Definition: ModRef.h:51
bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
A wrapper pass for external alias analyses.
std::function< void(Pass &, Function &, AAResults &)> CallbackT