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