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/Analysis/BasicAliasAnalysis.h"
28 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
29 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
30 #include "llvm/Analysis/CaptureTracking.h"
31 #include "llvm/Analysis/GlobalsModRef.h"
32 #include "llvm/Analysis/MemoryLocation.h"
33 #include "llvm/Analysis/ObjCARCAliasAnalysis.h"
34 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
35 #include "llvm/Analysis/ScopedNoAliasAA.h"
36 #include "llvm/Analysis/TargetLibraryInfo.h"
37 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
38 #include "llvm/Analysis/ValueTracking.h"
39 #include "llvm/IR/Argument.h"
40 #include "llvm/IR/Attributes.h"
41 #include "llvm/IR/BasicBlock.h"
42 #include "llvm/IR/Instruction.h"
43 #include "llvm/IR/Instructions.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Type.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Pass.h"
49 #include "llvm/Support/AtomicOrdering.h"
50 #include "llvm/Support/Casting.h"
51 #include "llvm/Support/CommandLine.h"
52 #include <algorithm>
53 #include <cassert>
54 #include <functional>
55 #include <iterator>
56
57 using namespace llvm;
58
59 /// Allow disabling BasicAA from the AA results. This is particularly useful
60 /// when testing to isolate a single AA implementation.
61 cl::opt<bool> DisableBasicAA("disable-basic-aa", cl::Hidden, cl::init(false));
62
AAResults(AAResults && Arg)63 AAResults::AAResults(AAResults &&Arg)
64 : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
65 for (auto &AA : AAs)
66 AA->setAAResults(this);
67 }
68
~AAResults()69 AAResults::~AAResults() {
70 // FIXME; It would be nice to at least clear out the pointers back to this
71 // aggregation here, but we end up with non-nesting lifetimes in the legacy
72 // pass manager that prevent this from working. In the legacy pass manager
73 // we'll end up with dangling references here in some cases.
74 #if 0
75 for (auto &AA : AAs)
76 AA->setAAResults(nullptr);
77 #endif
78 }
79
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator & Inv)80 bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
81 FunctionAnalysisManager::Invalidator &Inv) {
82 // AAResults preserves the AAManager by default, due to the stateless nature
83 // of AliasAnalysis. There is no need to check whether it has been preserved
84 // explicitly. Check if any module dependency was invalidated and caused the
85 // AAManager to be invalidated. Invalidate ourselves in that case.
86 auto PAC = PA.getChecker<AAManager>();
87 if (!PAC.preservedWhenStateless())
88 return true;
89
90 // Check if any of the function dependencies were invalidated, and invalidate
91 // ourselves in that case.
92 for (AnalysisKey *ID : AADeps)
93 if (Inv.invalidate(ID, F, PA))
94 return true;
95
96 // Everything we depend on is still fine, so are we. Nothing to invalidate.
97 return false;
98 }
99
100 //===----------------------------------------------------------------------===//
101 // Default chaining methods
102 //===----------------------------------------------------------------------===//
103
alias(const MemoryLocation & LocA,const MemoryLocation & LocB)104 AliasResult AAResults::alias(const MemoryLocation &LocA,
105 const MemoryLocation &LocB) {
106 AAQueryInfo AAQIP;
107 return alias(LocA, LocB, AAQIP);
108 }
109
alias(const MemoryLocation & LocA,const MemoryLocation & LocB,AAQueryInfo & AAQI)110 AliasResult AAResults::alias(const MemoryLocation &LocA,
111 const MemoryLocation &LocB, AAQueryInfo &AAQI) {
112 for (const auto &AA : AAs) {
113 auto Result = AA->alias(LocA, LocB, AAQI);
114 if (Result != MayAlias)
115 return Result;
116 }
117 return MayAlias;
118 }
119
pointsToConstantMemory(const MemoryLocation & Loc,bool OrLocal)120 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
121 bool OrLocal) {
122 AAQueryInfo AAQIP;
123 return pointsToConstantMemory(Loc, AAQIP, OrLocal);
124 }
125
pointsToConstantMemory(const MemoryLocation & Loc,AAQueryInfo & AAQI,bool OrLocal)126 bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
127 AAQueryInfo &AAQI, bool OrLocal) {
128 for (const auto &AA : AAs)
129 if (AA->pointsToConstantMemory(Loc, AAQI, OrLocal))
130 return true;
131
132 return false;
133 }
134
getArgModRefInfo(const CallBase * Call,unsigned ArgIdx)135 ModRefInfo AAResults::getArgModRefInfo(const CallBase *Call, unsigned ArgIdx) {
136 ModRefInfo Result = ModRefInfo::ModRef;
137
138 for (const auto &AA : AAs) {
139 Result = intersectModRef(Result, AA->getArgModRefInfo(Call, ArgIdx));
140
141 // Early-exit the moment we reach the bottom of the lattice.
142 if (isNoModRef(Result))
143 return ModRefInfo::NoModRef;
144 }
145
146 return Result;
147 }
148
getModRefInfo(Instruction * I,const CallBase * Call2)149 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2) {
150 AAQueryInfo AAQIP;
151 return getModRefInfo(I, Call2, AAQIP);
152 }
153
getModRefInfo(Instruction * I,const CallBase * Call2,AAQueryInfo & AAQI)154 ModRefInfo AAResults::getModRefInfo(Instruction *I, const CallBase *Call2,
155 AAQueryInfo &AAQI) {
156 // We may have two calls.
157 if (const auto *Call1 = dyn_cast<CallBase>(I)) {
158 // Check if the two calls modify the same memory.
159 return getModRefInfo(Call1, Call2, AAQI);
160 } else if (I->isFenceLike()) {
161 // If this is a fence, just return ModRef.
162 return ModRefInfo::ModRef;
163 } else {
164 // Otherwise, check if the call modifies or references the
165 // location this memory access defines. The best we can say
166 // is that if the call references what this instruction
167 // defines, it must be clobbered by this location.
168 const MemoryLocation DefLoc = MemoryLocation::get(I);
169 ModRefInfo MR = getModRefInfo(Call2, DefLoc, AAQI);
170 if (isModOrRefSet(MR))
171 return setModAndRef(MR);
172 }
173 return ModRefInfo::NoModRef;
174 }
175
getModRefInfo(const CallBase * Call,const MemoryLocation & Loc)176 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
177 const MemoryLocation &Loc) {
178 AAQueryInfo AAQIP;
179 return getModRefInfo(Call, Loc, AAQIP);
180 }
181
getModRefInfo(const CallBase * Call,const MemoryLocation & Loc,AAQueryInfo & AAQI)182 ModRefInfo AAResults::getModRefInfo(const CallBase *Call,
183 const MemoryLocation &Loc,
184 AAQueryInfo &AAQI) {
185 ModRefInfo Result = ModRefInfo::ModRef;
186
187 for (const auto &AA : AAs) {
188 Result = intersectModRef(Result, AA->getModRefInfo(Call, Loc, AAQI));
189
190 // Early-exit the moment we reach the bottom of the lattice.
191 if (isNoModRef(Result))
192 return ModRefInfo::NoModRef;
193 }
194
195 // Try to refine the mod-ref info further using other API entry points to the
196 // aggregate set of AA results.
197 auto MRB = getModRefBehavior(Call);
198 if (onlyAccessesInaccessibleMem(MRB))
199 return ModRefInfo::NoModRef;
200
201 if (onlyReadsMemory(MRB))
202 Result = clearMod(Result);
203 else if (doesNotReadMemory(MRB))
204 Result = clearRef(Result);
205
206 if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
207 bool IsMustAlias = true;
208 ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
209 if (doesAccessArgPointees(MRB)) {
210 for (auto AI = Call->arg_begin(), AE = Call->arg_end(); AI != AE; ++AI) {
211 const Value *Arg = *AI;
212 if (!Arg->getType()->isPointerTy())
213 continue;
214 unsigned ArgIdx = std::distance(Call->arg_begin(), AI);
215 MemoryLocation ArgLoc =
216 MemoryLocation::getForArgument(Call, ArgIdx, TLI);
217 AliasResult ArgAlias = alias(ArgLoc, Loc);
218 if (ArgAlias != NoAlias) {
219 ModRefInfo ArgMask = getArgModRefInfo(Call, ArgIdx);
220 AllArgsMask = unionModRef(AllArgsMask, ArgMask);
221 }
222 // Conservatively clear IsMustAlias unless only MustAlias is found.
223 IsMustAlias &= (ArgAlias == MustAlias);
224 }
225 }
226 // Return NoModRef if no alias found with any argument.
227 if (isNoModRef(AllArgsMask))
228 return ModRefInfo::NoModRef;
229 // Logical & between other AA analyses and argument analysis.
230 Result = intersectModRef(Result, AllArgsMask);
231 // If only MustAlias found above, set Must bit.
232 Result = IsMustAlias ? setMust(Result) : clearMust(Result);
233 }
234
235 // If Loc is a constant memory location, the call definitely could not
236 // modify the memory location.
237 if (isModSet(Result) && pointsToConstantMemory(Loc, AAQI, /*OrLocal*/ false))
238 Result = clearMod(Result);
239
240 return Result;
241 }
242
getModRefInfo(const CallBase * Call1,const CallBase * Call2)243 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
244 const CallBase *Call2) {
245 AAQueryInfo AAQIP;
246 return getModRefInfo(Call1, Call2, AAQIP);
247 }
248
getModRefInfo(const CallBase * Call1,const CallBase * Call2,AAQueryInfo & AAQI)249 ModRefInfo AAResults::getModRefInfo(const CallBase *Call1,
250 const CallBase *Call2, AAQueryInfo &AAQI) {
251 ModRefInfo Result = ModRefInfo::ModRef;
252
253 for (const auto &AA : AAs) {
254 Result = intersectModRef(Result, AA->getModRefInfo(Call1, Call2, AAQI));
255
256 // Early-exit the moment we reach the bottom of the lattice.
257 if (isNoModRef(Result))
258 return ModRefInfo::NoModRef;
259 }
260
261 // Try to refine the mod-ref info further using other API entry points to the
262 // aggregate set of AA results.
263
264 // If Call1 or Call2 are readnone, they don't interact.
265 auto Call1B = getModRefBehavior(Call1);
266 if (Call1B == FMRB_DoesNotAccessMemory)
267 return ModRefInfo::NoModRef;
268
269 auto Call2B = getModRefBehavior(Call2);
270 if (Call2B == FMRB_DoesNotAccessMemory)
271 return ModRefInfo::NoModRef;
272
273 // If they both only read from memory, there is no dependence.
274 if (onlyReadsMemory(Call1B) && onlyReadsMemory(Call2B))
275 return ModRefInfo::NoModRef;
276
277 // If Call1 only reads memory, the only dependence on Call2 can be
278 // from Call1 reading memory written by Call2.
279 if (onlyReadsMemory(Call1B))
280 Result = clearMod(Result);
281 else if (doesNotReadMemory(Call1B))
282 Result = clearRef(Result);
283
284 // If Call2 only access memory through arguments, accumulate the mod/ref
285 // information from Call1's references to the memory referenced by
286 // Call2's arguments.
287 if (onlyAccessesArgPointees(Call2B)) {
288 if (!doesAccessArgPointees(Call2B))
289 return ModRefInfo::NoModRef;
290 ModRefInfo R = ModRefInfo::NoModRef;
291 bool IsMustAlias = true;
292 for (auto I = Call2->arg_begin(), E = Call2->arg_end(); I != E; ++I) {
293 const Value *Arg = *I;
294 if (!Arg->getType()->isPointerTy())
295 continue;
296 unsigned Call2ArgIdx = std::distance(Call2->arg_begin(), I);
297 auto Call2ArgLoc =
298 MemoryLocation::getForArgument(Call2, Call2ArgIdx, TLI);
299
300 // ArgModRefC2 indicates what Call2 might do to Call2ArgLoc, and the
301 // dependence of Call1 on that location is the inverse:
302 // - If Call2 modifies location, dependence exists if Call1 reads or
303 // writes.
304 // - If Call2 only reads location, dependence exists if Call1 writes.
305 ModRefInfo ArgModRefC2 = getArgModRefInfo(Call2, Call2ArgIdx);
306 ModRefInfo ArgMask = ModRefInfo::NoModRef;
307 if (isModSet(ArgModRefC2))
308 ArgMask = ModRefInfo::ModRef;
309 else if (isRefSet(ArgModRefC2))
310 ArgMask = ModRefInfo::Mod;
311
312 // ModRefC1 indicates what Call1 might do to Call2ArgLoc, and we use
313 // above ArgMask to update dependence info.
314 ModRefInfo ModRefC1 = getModRefInfo(Call1, Call2ArgLoc, AAQI);
315 ArgMask = intersectModRef(ArgMask, ModRefC1);
316
317 // Conservatively clear IsMustAlias unless only MustAlias is found.
318 IsMustAlias &= isMustSet(ModRefC1);
319
320 R = intersectModRef(unionModRef(R, ArgMask), Result);
321 if (R == Result) {
322 // On early exit, not all args were checked, cannot set Must.
323 if (I + 1 != E)
324 IsMustAlias = false;
325 break;
326 }
327 }
328
329 if (isNoModRef(R))
330 return ModRefInfo::NoModRef;
331
332 // If MustAlias found above, set Must bit.
333 return IsMustAlias ? setMust(R) : clearMust(R);
334 }
335
336 // If Call1 only accesses memory through arguments, check if Call2 references
337 // any of the memory referenced by Call1's arguments. If not, return NoModRef.
338 if (onlyAccessesArgPointees(Call1B)) {
339 if (!doesAccessArgPointees(Call1B))
340 return ModRefInfo::NoModRef;
341 ModRefInfo R = ModRefInfo::NoModRef;
342 bool IsMustAlias = true;
343 for (auto I = Call1->arg_begin(), E = Call1->arg_end(); I != E; ++I) {
344 const Value *Arg = *I;
345 if (!Arg->getType()->isPointerTy())
346 continue;
347 unsigned Call1ArgIdx = std::distance(Call1->arg_begin(), I);
348 auto Call1ArgLoc =
349 MemoryLocation::getForArgument(Call1, Call1ArgIdx, TLI);
350
351 // ArgModRefC1 indicates what Call1 might do to Call1ArgLoc; if Call1
352 // might Mod Call1ArgLoc, then we care about either a Mod or a Ref by
353 // Call2. If Call1 might Ref, then we care only about a Mod by Call2.
354 ModRefInfo ArgModRefC1 = getArgModRefInfo(Call1, Call1ArgIdx);
355 ModRefInfo ModRefC2 = getModRefInfo(Call2, Call1ArgLoc, AAQI);
356 if ((isModSet(ArgModRefC1) && isModOrRefSet(ModRefC2)) ||
357 (isRefSet(ArgModRefC1) && isModSet(ModRefC2)))
358 R = intersectModRef(unionModRef(R, ArgModRefC1), Result);
359
360 // Conservatively clear IsMustAlias unless only MustAlias is found.
361 IsMustAlias &= isMustSet(ModRefC2);
362
363 if (R == Result) {
364 // On early exit, not all args were checked, cannot set Must.
365 if (I + 1 != E)
366 IsMustAlias = false;
367 break;
368 }
369 }
370
371 if (isNoModRef(R))
372 return ModRefInfo::NoModRef;
373
374 // If MustAlias found above, set Must bit.
375 return IsMustAlias ? setMust(R) : clearMust(R);
376 }
377
378 return Result;
379 }
380
getModRefBehavior(const CallBase * Call)381 FunctionModRefBehavior AAResults::getModRefBehavior(const CallBase *Call) {
382 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
383
384 for (const auto &AA : AAs) {
385 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(Call));
386
387 // Early-exit the moment we reach the bottom of the lattice.
388 if (Result == FMRB_DoesNotAccessMemory)
389 return Result;
390 }
391
392 return Result;
393 }
394
getModRefBehavior(const Function * F)395 FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
396 FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
397
398 for (const auto &AA : AAs) {
399 Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
400
401 // Early-exit the moment we reach the bottom of the lattice.
402 if (Result == FMRB_DoesNotAccessMemory)
403 return Result;
404 }
405
406 return Result;
407 }
408
operator <<(raw_ostream & OS,AliasResult AR)409 raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
410 switch (AR) {
411 case NoAlias:
412 OS << "NoAlias";
413 break;
414 case MustAlias:
415 OS << "MustAlias";
416 break;
417 case MayAlias:
418 OS << "MayAlias";
419 break;
420 case PartialAlias:
421 OS << "PartialAlias";
422 break;
423 }
424 return OS;
425 }
426
427 //===----------------------------------------------------------------------===//
428 // Helper method implementation
429 //===----------------------------------------------------------------------===//
430
getModRefInfo(const LoadInst * L,const MemoryLocation & Loc)431 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
432 const MemoryLocation &Loc) {
433 AAQueryInfo AAQIP;
434 return getModRefInfo(L, Loc, AAQIP);
435 }
getModRefInfo(const LoadInst * L,const MemoryLocation & Loc,AAQueryInfo & AAQI)436 ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
437 const MemoryLocation &Loc,
438 AAQueryInfo &AAQI) {
439 // Be conservative in the face of atomic.
440 if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
441 return ModRefInfo::ModRef;
442
443 // If the load address doesn't alias the given address, it doesn't read
444 // or write the specified memory.
445 if (Loc.Ptr) {
446 AliasResult AR = alias(MemoryLocation::get(L), Loc, AAQI);
447 if (AR == NoAlias)
448 return ModRefInfo::NoModRef;
449 if (AR == MustAlias)
450 return ModRefInfo::MustRef;
451 }
452 // Otherwise, a load just reads.
453 return ModRefInfo::Ref;
454 }
455
getModRefInfo(const StoreInst * S,const MemoryLocation & Loc)456 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
457 const MemoryLocation &Loc) {
458 AAQueryInfo AAQIP;
459 return getModRefInfo(S, Loc, AAQIP);
460 }
getModRefInfo(const StoreInst * S,const MemoryLocation & Loc,AAQueryInfo & AAQI)461 ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
462 const MemoryLocation &Loc,
463 AAQueryInfo &AAQI) {
464 // Be conservative in the face of atomic.
465 if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
466 return ModRefInfo::ModRef;
467
468 if (Loc.Ptr) {
469 AliasResult AR = alias(MemoryLocation::get(S), Loc, AAQI);
470 // If the store address cannot alias the pointer in question, then the
471 // specified memory cannot be modified by the store.
472 if (AR == NoAlias)
473 return ModRefInfo::NoModRef;
474
475 // If the pointer is a pointer to constant memory, then it could not have
476 // been modified by this store.
477 if (pointsToConstantMemory(Loc, AAQI))
478 return ModRefInfo::NoModRef;
479
480 // If the store address aliases the pointer as must alias, set Must.
481 if (AR == MustAlias)
482 return ModRefInfo::MustMod;
483 }
484
485 // Otherwise, a store just writes.
486 return ModRefInfo::Mod;
487 }
488
getModRefInfo(const FenceInst * S,const MemoryLocation & Loc)489 ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
490 AAQueryInfo AAQIP;
491 return getModRefInfo(S, Loc, AAQIP);
492 }
493
getModRefInfo(const FenceInst * S,const MemoryLocation & Loc,AAQueryInfo & AAQI)494 ModRefInfo AAResults::getModRefInfo(const FenceInst *S,
495 const MemoryLocation &Loc,
496 AAQueryInfo &AAQI) {
497 // If we know that the location is a constant memory location, the fence
498 // cannot modify this location.
499 if (Loc.Ptr && pointsToConstantMemory(Loc, AAQI))
500 return ModRefInfo::Ref;
501 return ModRefInfo::ModRef;
502 }
503
getModRefInfo(const VAArgInst * V,const MemoryLocation & Loc)504 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
505 const MemoryLocation &Loc) {
506 AAQueryInfo AAQIP;
507 return getModRefInfo(V, Loc, AAQIP);
508 }
509
getModRefInfo(const VAArgInst * V,const MemoryLocation & Loc,AAQueryInfo & AAQI)510 ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
511 const MemoryLocation &Loc,
512 AAQueryInfo &AAQI) {
513 if (Loc.Ptr) {
514 AliasResult AR = alias(MemoryLocation::get(V), Loc, AAQI);
515 // If the va_arg address cannot alias the pointer in question, then the
516 // specified memory cannot be accessed by the va_arg.
517 if (AR == NoAlias)
518 return ModRefInfo::NoModRef;
519
520 // If the pointer is a pointer to constant memory, then it could not have
521 // been modified by this va_arg.
522 if (pointsToConstantMemory(Loc, AAQI))
523 return ModRefInfo::NoModRef;
524
525 // If the va_arg aliases the pointer as must alias, set Must.
526 if (AR == MustAlias)
527 return ModRefInfo::MustModRef;
528 }
529
530 // Otherwise, a va_arg reads and writes.
531 return ModRefInfo::ModRef;
532 }
533
getModRefInfo(const CatchPadInst * CatchPad,const MemoryLocation & Loc)534 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
535 const MemoryLocation &Loc) {
536 AAQueryInfo AAQIP;
537 return getModRefInfo(CatchPad, Loc, AAQIP);
538 }
539
getModRefInfo(const CatchPadInst * CatchPad,const MemoryLocation & Loc,AAQueryInfo & AAQI)540 ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
541 const MemoryLocation &Loc,
542 AAQueryInfo &AAQI) {
543 if (Loc.Ptr) {
544 // If the pointer is a pointer to constant memory,
545 // then it could not have been modified by this catchpad.
546 if (pointsToConstantMemory(Loc, AAQI))
547 return ModRefInfo::NoModRef;
548 }
549
550 // Otherwise, a catchpad reads and writes.
551 return ModRefInfo::ModRef;
552 }
553
getModRefInfo(const CatchReturnInst * CatchRet,const MemoryLocation & Loc)554 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
555 const MemoryLocation &Loc) {
556 AAQueryInfo AAQIP;
557 return getModRefInfo(CatchRet, Loc, AAQIP);
558 }
559
getModRefInfo(const CatchReturnInst * CatchRet,const MemoryLocation & Loc,AAQueryInfo & AAQI)560 ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
561 const MemoryLocation &Loc,
562 AAQueryInfo &AAQI) {
563 if (Loc.Ptr) {
564 // If the pointer is a pointer to constant memory,
565 // then it could not have been modified by this catchpad.
566 if (pointsToConstantMemory(Loc, AAQI))
567 return ModRefInfo::NoModRef;
568 }
569
570 // Otherwise, a catchret reads and writes.
571 return ModRefInfo::ModRef;
572 }
573
getModRefInfo(const AtomicCmpXchgInst * CX,const MemoryLocation & Loc)574 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
575 const MemoryLocation &Loc) {
576 AAQueryInfo AAQIP;
577 return getModRefInfo(CX, Loc, AAQIP);
578 }
579
getModRefInfo(const AtomicCmpXchgInst * CX,const MemoryLocation & Loc,AAQueryInfo & AAQI)580 ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
581 const MemoryLocation &Loc,
582 AAQueryInfo &AAQI) {
583 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
584 if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
585 return ModRefInfo::ModRef;
586
587 if (Loc.Ptr) {
588 AliasResult AR = alias(MemoryLocation::get(CX), Loc, AAQI);
589 // If the cmpxchg address does not alias the location, it does not access
590 // it.
591 if (AR == NoAlias)
592 return ModRefInfo::NoModRef;
593
594 // If the cmpxchg address aliases the pointer as must alias, set Must.
595 if (AR == MustAlias)
596 return ModRefInfo::MustModRef;
597 }
598
599 return ModRefInfo::ModRef;
600 }
601
getModRefInfo(const AtomicRMWInst * RMW,const MemoryLocation & Loc)602 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
603 const MemoryLocation &Loc) {
604 AAQueryInfo AAQIP;
605 return getModRefInfo(RMW, Loc, AAQIP);
606 }
607
getModRefInfo(const AtomicRMWInst * RMW,const MemoryLocation & Loc,AAQueryInfo & AAQI)608 ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
609 const MemoryLocation &Loc,
610 AAQueryInfo &AAQI) {
611 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
612 if (isStrongerThanMonotonic(RMW->getOrdering()))
613 return ModRefInfo::ModRef;
614
615 if (Loc.Ptr) {
616 AliasResult AR = alias(MemoryLocation::get(RMW), Loc, AAQI);
617 // If the atomicrmw address does not alias the location, it does not access
618 // it.
619 if (AR == NoAlias)
620 return ModRefInfo::NoModRef;
621
622 // If the atomicrmw address aliases the pointer as must alias, set Must.
623 if (AR == MustAlias)
624 return ModRefInfo::MustModRef;
625 }
626
627 return ModRefInfo::ModRef;
628 }
629
630 /// Return information about whether a particular call site modifies
631 /// or reads the specified memory location \p MemLoc before instruction \p I
632 /// in a BasicBlock.
633 /// FIXME: this is really just shoring-up a deficiency in alias analysis.
634 /// BasicAA isn't willing to spend linear time determining whether an alloca
635 /// was captured before or after this particular call, while we are. However,
636 /// with a smarter AA in place, this test is just wasting compile time.
callCapturesBefore(const Instruction * I,const MemoryLocation & MemLoc,DominatorTree * DT)637 ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
638 const MemoryLocation &MemLoc,
639 DominatorTree *DT) {
640 if (!DT)
641 return ModRefInfo::ModRef;
642
643 const Value *Object = getUnderlyingObject(MemLoc.Ptr);
644 if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
645 isa<Constant>(Object))
646 return ModRefInfo::ModRef;
647
648 const auto *Call = dyn_cast<CallBase>(I);
649 if (!Call || Call == Object)
650 return ModRefInfo::ModRef;
651
652 if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
653 /* StoreCaptures */ true, I, DT,
654 /* include Object */ true))
655 return ModRefInfo::ModRef;
656
657 unsigned ArgNo = 0;
658 ModRefInfo R = ModRefInfo::NoModRef;
659 bool IsMustAlias = true;
660 // Set flag only if no May found and all operands processed.
661 for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
662 CI != CE; ++CI, ++ArgNo) {
663 // Only look at the no-capture or byval pointer arguments. If this
664 // pointer were passed to arguments that were neither of these, then it
665 // couldn't be no-capture.
666 if (!(*CI)->getType()->isPointerTy() ||
667 (!Call->doesNotCapture(ArgNo) && ArgNo < Call->getNumArgOperands() &&
668 !Call->isByValArgument(ArgNo)))
669 continue;
670
671 AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
672 // If this is a no-capture pointer argument, see if we can tell that it
673 // is impossible to alias the pointer we're checking. If not, we have to
674 // assume that the call could touch the pointer, even though it doesn't
675 // escape.
676 if (AR != MustAlias)
677 IsMustAlias = false;
678 if (AR == NoAlias)
679 continue;
680 if (Call->doesNotAccessMemory(ArgNo))
681 continue;
682 if (Call->onlyReadsMemory(ArgNo)) {
683 R = ModRefInfo::Ref;
684 continue;
685 }
686 // Not returning MustModRef since we have not seen all the arguments.
687 return ModRefInfo::ModRef;
688 }
689 return IsMustAlias ? setMust(R) : clearMust(R);
690 }
691
692 /// canBasicBlockModify - Return true if it is possible for execution of the
693 /// specified basic block to modify the location Loc.
694 ///
canBasicBlockModify(const BasicBlock & BB,const MemoryLocation & Loc)695 bool AAResults::canBasicBlockModify(const BasicBlock &BB,
696 const MemoryLocation &Loc) {
697 return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
698 }
699
700 /// canInstructionRangeModRef - Return true if it is possible for the
701 /// execution of the specified instructions to mod\ref (according to the
702 /// mode) the location Loc. The instructions to consider are all
703 /// of the instructions in the range of [I1,I2] INCLUSIVE.
704 /// I1 and I2 must be in the same basic block.
canInstructionRangeModRef(const Instruction & I1,const Instruction & I2,const MemoryLocation & Loc,const ModRefInfo Mode)705 bool AAResults::canInstructionRangeModRef(const Instruction &I1,
706 const Instruction &I2,
707 const MemoryLocation &Loc,
708 const ModRefInfo Mode) {
709 assert(I1.getParent() == I2.getParent() &&
710 "Instructions not in same basic block!");
711 BasicBlock::const_iterator I = I1.getIterator();
712 BasicBlock::const_iterator E = I2.getIterator();
713 ++E; // Convert from inclusive to exclusive range.
714
715 for (; I != E; ++I) // Check every instruction in range
716 if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
717 return true;
718 return false;
719 }
720
721 // Provide a definition for the root virtual destructor.
722 AAResults::Concept::~Concept() = default;
723
724 // Provide a definition for the static object used to identify passes.
725 AnalysisKey AAManager::Key;
726
727 namespace {
728
729
730 } // end anonymous namespace
731
ExternalAAWrapperPass()732 ExternalAAWrapperPass::ExternalAAWrapperPass() : ImmutablePass(ID) {
733 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
734 }
735
ExternalAAWrapperPass(CallbackT CB)736 ExternalAAWrapperPass::ExternalAAWrapperPass(CallbackT CB)
737 : ImmutablePass(ID), CB(std::move(CB)) {
738 initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
739 }
740
741 char ExternalAAWrapperPass::ID = 0;
742
743 INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
744 false, true)
745
746 ImmutablePass *
createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback)747 llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
748 return new ExternalAAWrapperPass(std::move(Callback));
749 }
750
AAResultsWrapperPass()751 AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
752 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
753 }
754
755 char AAResultsWrapperPass::ID = 0;
756
757 INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
758 "Function Alias Analysis Results", false, true)
INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)759 INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
760 INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
761 INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
762 INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
763 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
764 INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
765 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
766 INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
767 INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
768 INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
769 "Function Alias Analysis Results", false, true)
770
771 FunctionPass *llvm::createAAResultsWrapperPass() {
772 return new AAResultsWrapperPass();
773 }
774
775 /// Run the wrapper pass to rebuild an aggregation over known AA passes.
776 ///
777 /// This is the legacy pass manager's interface to the new-style AA results
778 /// aggregation object. Because this is somewhat shoe-horned into the legacy
779 /// pass manager, we hard code all the specific alias analyses available into
780 /// it. While the particular set enabled is configured via commandline flags,
781 /// adding a new alias analysis to LLVM will require adding support for it to
782 /// this list.
runOnFunction(Function & F)783 bool AAResultsWrapperPass::runOnFunction(Function &F) {
784 // NB! This *must* be reset before adding new AA results to the new
785 // AAResults object because in the legacy pass manager, each instance
786 // of these will refer to the *same* immutable analyses, registering and
787 // unregistering themselves with them. We need to carefully tear down the
788 // previous object first, in this case replacing it with an empty one, before
789 // registering new results.
790 AAR.reset(
791 new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F)));
792
793 // BasicAA is always available for function analyses. Also, we add it first
794 // so that it can trump TBAA results when it proves MustAlias.
795 // FIXME: TBAA should have an explicit mode to support this and then we
796 // should reconsider the ordering here.
797 if (!DisableBasicAA)
798 AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
799
800 // Populate the results with the currently available AAs.
801 if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
802 AAR->addAAResult(WrapperPass->getResult());
803 if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
804 AAR->addAAResult(WrapperPass->getResult());
805 if (auto *WrapperPass =
806 getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
807 AAR->addAAResult(WrapperPass->getResult());
808 if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
809 AAR->addAAResult(WrapperPass->getResult());
810 if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
811 AAR->addAAResult(WrapperPass->getResult());
812 if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
813 AAR->addAAResult(WrapperPass->getResult());
814 if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
815 AAR->addAAResult(WrapperPass->getResult());
816
817 // If available, run an external AA providing callback over the results as
818 // well.
819 if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
820 if (WrapperPass->CB)
821 WrapperPass->CB(*this, F, *AAR);
822
823 // Analyses don't mutate the IR, so return false.
824 return false;
825 }
826
getAnalysisUsage(AnalysisUsage & AU) const827 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
828 AU.setPreservesAll();
829 AU.addRequired<BasicAAWrapperPass>();
830 AU.addRequired<TargetLibraryInfoWrapperPass>();
831
832 // We also need to mark all the alias analysis passes we will potentially
833 // probe in runOnFunction as used here to ensure the legacy pass manager
834 // preserves them. This hard coding of lists of alias analyses is specific to
835 // the legacy pass manager.
836 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
837 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
838 AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
839 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
840 AU.addUsedIfAvailable<SCEVAAWrapperPass>();
841 AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
842 AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
843 AU.addUsedIfAvailable<ExternalAAWrapperPass>();
844 }
845
createLegacyPMAAResults(Pass & P,Function & F,BasicAAResult & BAR)846 AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
847 BasicAAResult &BAR) {
848 AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F));
849
850 // Add in our explicitly constructed BasicAA results.
851 if (!DisableBasicAA)
852 AAR.addAAResult(BAR);
853
854 // Populate the results with the other currently available AAs.
855 if (auto *WrapperPass =
856 P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
857 AAR.addAAResult(WrapperPass->getResult());
858 if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
859 AAR.addAAResult(WrapperPass->getResult());
860 if (auto *WrapperPass =
861 P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
862 AAR.addAAResult(WrapperPass->getResult());
863 if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
864 AAR.addAAResult(WrapperPass->getResult());
865 if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
866 AAR.addAAResult(WrapperPass->getResult());
867 if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
868 AAR.addAAResult(WrapperPass->getResult());
869 if (auto *WrapperPass = P.getAnalysisIfAvailable<ExternalAAWrapperPass>())
870 if (WrapperPass->CB)
871 WrapperPass->CB(P, F, AAR);
872
873 return AAR;
874 }
875
isNoAliasCall(const Value * V)876 bool llvm::isNoAliasCall(const Value *V) {
877 if (const auto *Call = dyn_cast<CallBase>(V))
878 return Call->hasRetAttr(Attribute::NoAlias);
879 return false;
880 }
881
isNoAliasArgument(const Value * V)882 bool llvm::isNoAliasArgument(const Value *V) {
883 if (const Argument *A = dyn_cast<Argument>(V))
884 return A->hasNoAliasAttr();
885 return false;
886 }
887
isIdentifiedObject(const Value * V)888 bool llvm::isIdentifiedObject(const Value *V) {
889 if (isa<AllocaInst>(V))
890 return true;
891 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
892 return true;
893 if (isNoAliasCall(V))
894 return true;
895 if (const Argument *A = dyn_cast<Argument>(V))
896 return A->hasNoAliasAttr() || A->hasByValAttr();
897 return false;
898 }
899
isIdentifiedFunctionLocal(const Value * V)900 bool llvm::isIdentifiedFunctionLocal(const Value *V) {
901 return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
902 }
903
getAAResultsAnalysisUsage(AnalysisUsage & AU)904 void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
905 // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
906 // more alias analyses are added to llvm::createLegacyPMAAResults, they need
907 // to be added here also.
908 AU.addRequired<TargetLibraryInfoWrapperPass>();
909 AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
910 AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
911 AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
912 AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
913 AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
914 AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
915 AU.addUsedIfAvailable<ExternalAAWrapperPass>();
916 }
917