Line data Source code
1 : //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the generic AliasAnalysis interface which is used as the
11 : // common interface used by all clients and implementations of alias analysis.
12 : //
13 : // This file also implements the default version of the AliasAnalysis interface
14 : // that is to be used when no other implementation is specified. This does some
15 : // simple tests that detect obvious cases: two different global pointers cannot
16 : // alias, a global cannot alias a malloc, two different mallocs cannot alias,
17 : // etc.
18 : //
19 : // This alias analysis implementation really isn't very good for anything, but
20 : // it is very fast, and makes a nice clean default implementation. Because it
21 : // handles lots of little corner cases, other, more complex, alias analysis
22 : // implementations may choose to rely on this pass to resolve these simple and
23 : // easy cases.
24 : //
25 : //===----------------------------------------------------------------------===//
26 :
27 : #include "llvm/Analysis/AliasAnalysis.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/CallSite.h"
44 : #include "llvm/IR/Instruction.h"
45 : #include "llvm/IR/Instructions.h"
46 : #include "llvm/IR/Module.h"
47 : #include "llvm/IR/Type.h"
48 : #include "llvm/IR/Value.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 : using namespace llvm;
59 :
60 : /// Allow disabling BasicAA from the AA results. This is particularly useful
61 : /// when testing to isolate a single AA implementation.
62 : static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
63 : cl::init(false));
64 :
65 1455052 : AAResults::AAResults(AAResults &&Arg)
66 1455052 : : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
67 3356935 : for (auto &AA : AAs)
68 1901884 : AA->setAAResults(this);
69 1455051 : }
70 :
71 4114138 : AAResults::~AAResults() {
72 : // FIXME; It would be nice to at least clear out the pointers back to this
73 : // aggregation here, but we end up with non-nesting lifetimes in the legacy
74 : // pass manager that prevent this from working. In the legacy pass manager
75 : // we'll end up with dangling references here in some cases.
76 : #if 0
77 : for (auto &AA : AAs)
78 : AA->setAAResults(nullptr);
79 : #endif
80 4113131 : }
81 :
82 1130 : bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
83 : FunctionAnalysisManager::Invalidator &Inv) {
84 : // Check if the AA manager itself has been invalidated.
85 : auto PAC = PA.getChecker<AAManager>();
86 1130 : if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())
87 : return true; // The manager needs to be blown away, clear everything.
88 :
89 : // Check all of the dependencies registered.
90 960 : for (AnalysisKey *ID : AADeps)
91 373 : if (Inv.invalidate(ID, F, PA))
92 : return true;
93 :
94 : // Everything we depend on is still fine, so are we. Nothing to invalidate.
95 : return false;
96 : }
97 :
98 : //===----------------------------------------------------------------------===//
99 : // Default chaining methods
100 : //===----------------------------------------------------------------------===//
101 :
102 39454176 : AliasResult AAResults::alias(const MemoryLocation &LocA,
103 : const MemoryLocation &LocB) {
104 65461904 : for (const auto &AA : AAs) {
105 58976281 : auto Result = AA->alias(LocA, LocB);
106 58976281 : if (Result != MayAlias)
107 : return Result;
108 : }
109 : return MayAlias;
110 : }
111 :
112 6749109 : bool AAResults::pointsToConstantMemory(const MemoryLocation &Loc,
113 : bool OrLocal) {
114 31839313 : for (const auto &AA : AAs)
115 25196883 : if (AA->pointsToConstantMemory(Loc, OrLocal))
116 : return true;
117 :
118 : return false;
119 : }
120 :
121 2212267 : ModRefInfo AAResults::getArgModRefInfo(ImmutableCallSite CS, unsigned ArgIdx) {
122 : ModRefInfo Result = ModRefInfo::ModRef;
123 :
124 11057549 : for (const auto &AA : AAs) {
125 8845283 : Result = intersectModRef(Result, AA->getArgModRefInfo(CS, ArgIdx));
126 :
127 : // Early-exit the moment we reach the bottom of the lattice.
128 8845283 : if (isNoModRef(Result))
129 : return ModRefInfo::NoModRef;
130 : }
131 :
132 : return Result;
133 : }
134 :
135 12365 : ModRefInfo AAResults::getModRefInfo(Instruction *I, ImmutableCallSite Call) {
136 : // We may have two calls.
137 12365 : if (auto CS = ImmutableCallSite(I)) {
138 : // Check if the two calls modify the same memory.
139 1228 : return getModRefInfo(CS, Call);
140 : } else if (I->isFenceLike()) {
141 : // If this is a fence, just return ModRef.
142 : return ModRefInfo::ModRef;
143 : } else {
144 : // Otherwise, check if the call modifies or references the
145 : // location this memory access defines. The best we can say
146 : // is that if the call references what this instruction
147 : // defines, it must be clobbered by this location.
148 : const MemoryLocation DefLoc = MemoryLocation::get(I);
149 11136 : ModRefInfo MR = getModRefInfo(Call, DefLoc);
150 11136 : if (isModOrRefSet(MR))
151 1115 : return setModAndRef(MR);
152 : }
153 10021 : return ModRefInfo::NoModRef;
154 : }
155 :
156 5462252 : ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS,
157 : const MemoryLocation &Loc) {
158 : ModRefInfo Result = ModRefInfo::ModRef;
159 :
160 27068209 : for (const auto &AA : AAs) {
161 21657767 : Result = intersectModRef(Result, AA->getModRefInfo(CS, Loc));
162 :
163 : // Early-exit the moment we reach the bottom of the lattice.
164 21657767 : if (isNoModRef(Result))
165 : return ModRefInfo::NoModRef;
166 : }
167 :
168 : // Try to refine the mod-ref info further using other API entry points to the
169 : // aggregate set of AA results.
170 5410442 : auto MRB = getModRefBehavior(CS);
171 10820884 : if (MRB == FMRB_DoesNotAccessMemory ||
172 5410442 : MRB == FMRB_OnlyAccessesInaccessibleMem)
173 : return ModRefInfo::NoModRef;
174 :
175 5386626 : if (onlyReadsMemory(MRB))
176 : Result = clearMod(Result);
177 5368745 : else if (doesNotReadMemory(MRB))
178 : Result = clearRef(Result);
179 :
180 5386626 : if (onlyAccessesArgPointees(MRB) || onlyAccessesInaccessibleOrArgMem(MRB)) {
181 : bool IsMustAlias = true;
182 : ModRefInfo AllArgsMask = ModRefInfo::NoModRef;
183 : if (doesAccessArgPointees(MRB)) {
184 13723250 : for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
185 10610525 : const Value *Arg = *AI;
186 21221050 : if (!Arg->getType()->isPointerTy())
187 7483686 : continue;
188 3126839 : unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
189 3126839 : MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx, TLI);
190 3126839 : AliasResult ArgAlias = alias(ArgLoc, Loc);
191 3126839 : if (ArgAlias != NoAlias) {
192 44381 : ModRefInfo ArgMask = getArgModRefInfo(CS, ArgIdx);
193 : AllArgsMask = unionModRef(AllArgsMask, ArgMask);
194 : }
195 : // Conservatively clear IsMustAlias unless only MustAlias is found.
196 3126839 : IsMustAlias &= (ArgAlias == MustAlias);
197 : }
198 : }
199 : // Return NoModRef if no alias found with any argument.
200 3112725 : if (isNoModRef(AllArgsMask))
201 : return ModRefInfo::NoModRef;
202 : // Logical & between other AA analyses and argument analysis.
203 : Result = intersectModRef(Result, AllArgsMask);
204 : // If only MustAlias found above, set Must bit.
205 34505 : Result = IsMustAlias ? setMust(Result) : clearMust(Result);
206 : }
207 :
208 : // If Loc is a constant memory location, the call definitely could not
209 : // modify the memory location.
210 2308406 : if (isModSet(Result) && pointsToConstantMemory(Loc, /*OrLocal*/ false))
211 : Result = clearMod(Result);
212 :
213 : return Result;
214 : }
215 :
216 2173480 : ModRefInfo AAResults::getModRefInfo(ImmutableCallSite CS1,
217 : ImmutableCallSite CS2) {
218 : ModRefInfo Result = ModRefInfo::ModRef;
219 :
220 10865201 : for (const auto &AA : AAs) {
221 8691770 : Result = intersectModRef(Result, AA->getModRefInfo(CS1, CS2));
222 :
223 : // Early-exit the moment we reach the bottom of the lattice.
224 8691770 : if (isNoModRef(Result))
225 : return ModRefInfo::NoModRef;
226 : }
227 :
228 : // Try to refine the mod-ref info further using other API entry points to the
229 : // aggregate set of AA results.
230 :
231 : // If CS1 or CS2 are readnone, they don't interact.
232 2173431 : auto CS1B = getModRefBehavior(CS1);
233 2173431 : if (CS1B == FMRB_DoesNotAccessMemory)
234 : return ModRefInfo::NoModRef;
235 :
236 2173339 : auto CS2B = getModRefBehavior(CS2);
237 2173339 : if (CS2B == FMRB_DoesNotAccessMemory)
238 : return ModRefInfo::NoModRef;
239 :
240 : // If they both only read from memory, there is no dependence.
241 2173045 : if (onlyReadsMemory(CS1B) && onlyReadsMemory(CS2B))
242 : return ModRefInfo::NoModRef;
243 :
244 : // If CS1 only reads memory, the only dependence on CS2 can be
245 : // from CS1 reading memory written by CS2.
246 2172084 : if (onlyReadsMemory(CS1B))
247 : Result = clearMod(Result);
248 2171738 : else if (doesNotReadMemory(CS1B))
249 : Result = clearRef(Result);
250 :
251 : // If CS2 only access memory through arguments, accumulate the mod/ref
252 : // information from CS1's references to the memory referenced by
253 : // CS2's arguments.
254 2172084 : if (onlyAccessesArgPointees(CS2B)) {
255 : if (!doesAccessArgPointees(CS2B))
256 : return ModRefInfo::NoModRef;
257 : ModRefInfo R = ModRefInfo::NoModRef;
258 : bool IsMustAlias = true;
259 10683634 : for (auto I = CS2.arg_begin(), E = CS2.arg_end(); I != E; ++I) {
260 8546393 : const Value *Arg = *I;
261 17092786 : if (!Arg->getType()->isPointerTy())
262 6408629 : continue;
263 2137764 : unsigned CS2ArgIdx = std::distance(CS2.arg_begin(), I);
264 2137764 : auto CS2ArgLoc = MemoryLocation::getForArgument(CS2, CS2ArgIdx, TLI);
265 :
266 : // ArgModRefCS2 indicates what CS2 might do to CS2ArgLoc, and the
267 : // dependence of CS1 on that location is the inverse:
268 : // - If CS2 modifies location, dependence exists if CS1 reads or writes.
269 : // - If CS2 only reads location, dependence exists if CS1 writes.
270 2137764 : ModRefInfo ArgModRefCS2 = getArgModRefInfo(CS2, CS2ArgIdx);
271 : ModRefInfo ArgMask = ModRefInfo::NoModRef;
272 2137764 : if (isModSet(ArgModRefCS2))
273 : ArgMask = ModRefInfo::ModRef;
274 485 : else if (isRefSet(ArgModRefCS2))
275 : ArgMask = ModRefInfo::Mod;
276 :
277 : // ModRefCS1 indicates what CS1 might do to CS2ArgLoc, and we use
278 : // above ArgMask to update dependence info.
279 2137764 : ModRefInfo ModRefCS1 = getModRefInfo(CS1, CS2ArgLoc);
280 : ArgMask = intersectModRef(ArgMask, ModRefCS1);
281 :
282 : // Conservatively clear IsMustAlias unless only MustAlias is found.
283 : IsMustAlias &= isMustSet(ModRefCS1);
284 :
285 : R = intersectModRef(unionModRef(R, ArgMask), Result);
286 2137764 : if (R == Result) {
287 : // On early exit, not all args were checked, cannot set Must.
288 92 : if (I + 1 != E)
289 : IsMustAlias = false;
290 92 : break;
291 : }
292 : }
293 :
294 2137333 : if (isNoModRef(R))
295 : return ModRefInfo::NoModRef;
296 :
297 : // If MustAlias found above, set Must bit.
298 1418 : return IsMustAlias ? setMust(R) : clearMust(R);
299 : }
300 :
301 : // If CS1 only accesses memory through arguments, check if CS2 references
302 : // any of the memory referenced by CS1's arguments. If not, return NoModRef.
303 34751 : if (onlyAccessesArgPointees(CS1B)) {
304 : if (!doesAccessArgPointees(CS1B))
305 : return ModRefInfo::NoModRef;
306 : ModRefInfo R = ModRefInfo::NoModRef;
307 : bool IsMustAlias = true;
308 28521 : for (auto I = CS1.arg_begin(), E = CS1.arg_end(); I != E; ++I) {
309 22834 : const Value *Arg = *I;
310 45668 : if (!Arg->getType()->isPointerTy())
311 16971 : continue;
312 5863 : unsigned CS1ArgIdx = std::distance(CS1.arg_begin(), I);
313 5863 : auto CS1ArgLoc = MemoryLocation::getForArgument(CS1, CS1ArgIdx, TLI);
314 :
315 : // ArgModRefCS1 indicates what CS1 might do to CS1ArgLoc; if CS1 might
316 : // Mod CS1ArgLoc, then we care about either a Mod or a Ref by CS2. If
317 : // CS1 might Ref, then we care only about a Mod by CS2.
318 5863 : ModRefInfo ArgModRefCS1 = getArgModRefInfo(CS1, CS1ArgIdx);
319 5863 : ModRefInfo ModRefCS2 = getModRefInfo(CS2, CS1ArgLoc);
320 5863 : if ((isModSet(ArgModRefCS1) && isModOrRefSet(ModRefCS2)) ||
321 130 : (isRefSet(ArgModRefCS1) && isModSet(ModRefCS2)))
322 : R = intersectModRef(unionModRef(R, ArgModRefCS1), Result);
323 :
324 : // Conservatively clear IsMustAlias unless only MustAlias is found.
325 : IsMustAlias &= isMustSet(ModRefCS2);
326 :
327 5863 : if (R == Result) {
328 : // On early exit, not all args were checked, cannot set Must.
329 55 : if (I + 1 != E)
330 : IsMustAlias = false;
331 55 : break;
332 : }
333 : }
334 :
335 5742 : if (isNoModRef(R))
336 : return ModRefInfo::NoModRef;
337 :
338 : // If MustAlias found above, set Must bit.
339 5704 : return IsMustAlias ? setMust(R) : clearMust(R);
340 : }
341 :
342 : return Result;
343 : }
344 :
345 10634239 : FunctionModRefBehavior AAResults::getModRefBehavior(ImmutableCallSite CS) {
346 : FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
347 :
348 51657483 : for (const auto &AA : AAs) {
349 41359534 : Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(CS));
350 :
351 : // Early-exit the moment we reach the bottom of the lattice.
352 41359534 : if (Result == FMRB_DoesNotAccessMemory)
353 : return Result;
354 : }
355 :
356 : return Result;
357 : }
358 :
359 10203954 : FunctionModRefBehavior AAResults::getModRefBehavior(const Function *F) {
360 : FunctionModRefBehavior Result = FMRB_UnknownModRefBehavior;
361 :
362 50852267 : for (const auto &AA : AAs) {
363 40651854 : Result = FunctionModRefBehavior(Result & AA->getModRefBehavior(F));
364 :
365 : // Early-exit the moment we reach the bottom of the lattice.
366 40651855 : if (Result == FMRB_DoesNotAccessMemory)
367 : return Result;
368 : }
369 :
370 : return Result;
371 : }
372 :
373 5666 : raw_ostream &llvm::operator<<(raw_ostream &OS, AliasResult AR) {
374 5666 : switch (AR) {
375 2454 : case NoAlias:
376 2454 : OS << "NoAlias";
377 2454 : break;
378 202 : case MustAlias:
379 202 : OS << "MustAlias";
380 202 : break;
381 2969 : case MayAlias:
382 2969 : OS << "MayAlias";
383 2969 : break;
384 41 : case PartialAlias:
385 41 : OS << "PartialAlias";
386 41 : break;
387 : }
388 5666 : return OS;
389 : }
390 :
391 : //===----------------------------------------------------------------------===//
392 : // Helper method implementation
393 : //===----------------------------------------------------------------------===//
394 :
395 701664 : ModRefInfo AAResults::getModRefInfo(const LoadInst *L,
396 : const MemoryLocation &Loc) {
397 : // Be conservative in the face of atomic.
398 701664 : if (isStrongerThan(L->getOrdering(), AtomicOrdering::Unordered))
399 : return ModRefInfo::ModRef;
400 :
401 : // If the load address doesn't alias the given address, it doesn't read
402 : // or write the specified memory.
403 701146 : if (Loc.Ptr) {
404 6594 : AliasResult AR = alias(MemoryLocation::get(L), Loc);
405 6594 : if (AR == NoAlias)
406 : return ModRefInfo::NoModRef;
407 3572 : if (AR == MustAlias)
408 33 : return ModRefInfo::MustRef;
409 : }
410 : // Otherwise, a load just reads.
411 : return ModRefInfo::Ref;
412 : }
413 :
414 17404793 : ModRefInfo AAResults::getModRefInfo(const StoreInst *S,
415 : const MemoryLocation &Loc) {
416 : // Be conservative in the face of atomic.
417 17404793 : if (isStrongerThan(S->getOrdering(), AtomicOrdering::Unordered))
418 : return ModRefInfo::ModRef;
419 :
420 17404719 : if (Loc.Ptr) {
421 16596128 : AliasResult AR = alias(MemoryLocation::get(S), Loc);
422 : // If the store address cannot alias the pointer in question, then the
423 : // specified memory cannot be modified by the store.
424 16596128 : if (AR == NoAlias)
425 : return ModRefInfo::NoModRef;
426 :
427 : // If the pointer is a pointer to constant memory, then it could not have
428 : // been modified by this store.
429 565903 : if (pointsToConstantMemory(Loc))
430 : return ModRefInfo::NoModRef;
431 :
432 : // If the store address aliases the pointer as must alias, set Must.
433 564382 : if (AR == MustAlias)
434 53484 : return ModRefInfo::MustMod;
435 : }
436 :
437 : // Otherwise, a store just writes.
438 : return ModRefInfo::Mod;
439 : }
440 :
441 535 : ModRefInfo AAResults::getModRefInfo(const FenceInst *S, const MemoryLocation &Loc) {
442 : // If we know that the location is a constant memory location, the fence
443 : // cannot modify this location.
444 535 : if (Loc.Ptr && pointsToConstantMemory(Loc))
445 15 : return ModRefInfo::Ref;
446 : return ModRefInfo::ModRef;
447 : }
448 :
449 3 : ModRefInfo AAResults::getModRefInfo(const VAArgInst *V,
450 : const MemoryLocation &Loc) {
451 3 : if (Loc.Ptr) {
452 1 : AliasResult AR = alias(MemoryLocation::get(V), Loc);
453 : // If the va_arg address cannot alias the pointer in question, then the
454 : // specified memory cannot be accessed by the va_arg.
455 1 : if (AR == NoAlias)
456 : return ModRefInfo::NoModRef;
457 :
458 : // If the pointer is a pointer to constant memory, then it could not have
459 : // been modified by this va_arg.
460 0 : if (pointsToConstantMemory(Loc))
461 : return ModRefInfo::NoModRef;
462 :
463 : // If the va_arg aliases the pointer as must alias, set Must.
464 0 : if (AR == MustAlias)
465 0 : return ModRefInfo::MustModRef;
466 : }
467 :
468 : // Otherwise, a va_arg reads and writes.
469 : return ModRefInfo::ModRef;
470 : }
471 :
472 2 : ModRefInfo AAResults::getModRefInfo(const CatchPadInst *CatchPad,
473 : const MemoryLocation &Loc) {
474 2 : if (Loc.Ptr) {
475 : // If the pointer is a pointer to constant memory,
476 : // then it could not have been modified by this catchpad.
477 0 : if (pointsToConstantMemory(Loc))
478 0 : return ModRefInfo::NoModRef;
479 : }
480 :
481 : // Otherwise, a catchpad reads and writes.
482 : return ModRefInfo::ModRef;
483 : }
484 :
485 6 : ModRefInfo AAResults::getModRefInfo(const CatchReturnInst *CatchRet,
486 : const MemoryLocation &Loc) {
487 6 : if (Loc.Ptr) {
488 : // If the pointer is a pointer to constant memory,
489 : // then it could not have been modified by this catchpad.
490 4 : if (pointsToConstantMemory(Loc))
491 0 : return ModRefInfo::NoModRef;
492 : }
493 :
494 : // Otherwise, a catchret reads and writes.
495 : return ModRefInfo::ModRef;
496 : }
497 :
498 1556 : ModRefInfo AAResults::getModRefInfo(const AtomicCmpXchgInst *CX,
499 : const MemoryLocation &Loc) {
500 : // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
501 1556 : if (isStrongerThanMonotonic(CX->getSuccessOrdering()))
502 : return ModRefInfo::ModRef;
503 :
504 6 : if (Loc.Ptr) {
505 0 : AliasResult AR = alias(MemoryLocation::get(CX), Loc);
506 : // If the cmpxchg address does not alias the location, it does not access
507 : // it.
508 0 : if (AR == NoAlias)
509 : return ModRefInfo::NoModRef;
510 :
511 : // If the cmpxchg address aliases the pointer as must alias, set Must.
512 0 : if (AR == MustAlias)
513 0 : return ModRefInfo::MustModRef;
514 : }
515 :
516 : return ModRefInfo::ModRef;
517 : }
518 :
519 2554 : ModRefInfo AAResults::getModRefInfo(const AtomicRMWInst *RMW,
520 : const MemoryLocation &Loc) {
521 : // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
522 2554 : if (isStrongerThanMonotonic(RMW->getOrdering()))
523 : return ModRefInfo::ModRef;
524 :
525 13 : if (Loc.Ptr) {
526 2 : AliasResult AR = alias(MemoryLocation::get(RMW), Loc);
527 : // If the atomicrmw address does not alias the location, it does not access
528 : // it.
529 2 : if (AR == NoAlias)
530 : return ModRefInfo::NoModRef;
531 :
532 : // If the atomicrmw address aliases the pointer as must alias, set Must.
533 0 : if (AR == MustAlias)
534 0 : return ModRefInfo::MustModRef;
535 : }
536 :
537 : return ModRefInfo::ModRef;
538 : }
539 :
540 : /// Return information about whether a particular call site modifies
541 : /// or reads the specified memory location \p MemLoc before instruction \p I
542 : /// in a BasicBlock. An ordered basic block \p OBB can be used to speed up
543 : /// instruction-ordering queries inside the BasicBlock containing \p I.
544 : /// FIXME: this is really just shoring-up a deficiency in alias analysis.
545 : /// BasicAA isn't willing to spend linear time determining whether an alloca
546 : /// was captured before or after this particular call, while we are. However,
547 : /// with a smarter AA in place, this test is just wasting compile time.
548 716807 : ModRefInfo AAResults::callCapturesBefore(const Instruction *I,
549 : const MemoryLocation &MemLoc,
550 : DominatorTree *DT,
551 : OrderedBasicBlock *OBB) {
552 716807 : if (!DT)
553 : return ModRefInfo::ModRef;
554 :
555 : const Value *Object =
556 716807 : GetUnderlyingObject(MemLoc.Ptr, I->getModule()->getDataLayout());
557 769825 : if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
558 : isa<Constant>(Object))
559 : return ModRefInfo::ModRef;
560 :
561 : ImmutableCallSite CS(I);
562 53018 : if (!CS.getInstruction() || CS.getInstruction() == Object)
563 : return ModRefInfo::ModRef;
564 :
565 53010 : if (PointerMayBeCapturedBefore(Object, /* ReturnCaptures */ true,
566 : /* StoreCaptures */ true, I, DT,
567 : /* include Object */ true,
568 : /* OrderedBasicBlock */ OBB))
569 : return ModRefInfo::ModRef;
570 :
571 : unsigned ArgNo = 0;
572 : ModRefInfo R = ModRefInfo::NoModRef;
573 : bool IsMustAlias = true;
574 : // Set flag only if no May found and all operands processed.
575 4054 : for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
576 4054 : CI != CE; ++CI, ++ArgNo) {
577 : // Only look at the no-capture or byval pointer arguments. If this
578 : // pointer were passed to arguments that were neither of these, then it
579 : // couldn't be no-capture.
580 8811 : if (!(*CI)->getType()->isPointerTy() ||
581 2088 : (!CS.doesNotCapture(ArgNo) &&
582 4176 : ArgNo < CS.getNumArgOperands() && !CS.isByValArgument(ArgNo)))
583 2627 : continue;
584 :
585 1062 : AliasResult AR = alias(MemoryLocation(*CI), MemoryLocation(Object));
586 : // If this is a no-capture pointer argument, see if we can tell that it
587 : // is impossible to alias the pointer we're checking. If not, we have to
588 : // assume that the call could touch the pointer, even though it doesn't
589 : // escape.
590 531 : if (AR != MustAlias)
591 : IsMustAlias = false;
592 531 : if (AR == NoAlias)
593 : continue;
594 352 : if (CS.doesNotAccessMemory(ArgNo))
595 : continue;
596 352 : if (CS.onlyReadsMemory(ArgNo)) {
597 : R = ModRefInfo::Ref;
598 : continue;
599 : }
600 : // Not returning MustModRef since we have not seen all the arguments.
601 : return ModRefInfo::ModRef;
602 : }
603 896 : return IsMustAlias ? setMust(R) : clearMust(R);
604 : }
605 :
606 : /// canBasicBlockModify - Return true if it is possible for execution of the
607 : /// specified basic block to modify the location Loc.
608 : ///
609 2 : bool AAResults::canBasicBlockModify(const BasicBlock &BB,
610 : const MemoryLocation &Loc) {
611 2 : return canInstructionRangeModRef(BB.front(), BB.back(), Loc, ModRefInfo::Mod);
612 : }
613 :
614 : /// canInstructionRangeModRef - Return true if it is possible for the
615 : /// execution of the specified instructions to mod\ref (according to the
616 : /// mode) the location Loc. The instructions to consider are all
617 : /// of the instructions in the range of [I1,I2] INCLUSIVE.
618 : /// I1 and I2 must be in the same basic block.
619 455 : bool AAResults::canInstructionRangeModRef(const Instruction &I1,
620 : const Instruction &I2,
621 : const MemoryLocation &Loc,
622 : const ModRefInfo Mode) {
623 : assert(I1.getParent() == I2.getParent() &&
624 : "Instructions not in same basic block!");
625 455 : BasicBlock::const_iterator I = I1.getIterator();
626 455 : BasicBlock::const_iterator E = I2.getIterator();
627 : ++E; // Convert from inclusive to exclusive range.
628 :
629 2362 : for (; I != E; ++I) // Check every instruction in range
630 2025 : if (isModOrRefSet(intersectModRef(getModRefInfo(&*I, Loc), Mode)))
631 : return true;
632 : return false;
633 : }
634 :
635 : // Provide a definition for the root virtual destructor.
636 : AAResults::Concept::~Concept() = default;
637 :
638 : // Provide a definition for the static object used to identify passes.
639 : AnalysisKey AAManager::Key;
640 :
641 : namespace {
642 :
643 : /// A wrapper pass for external alias analyses. This just squirrels away the
644 : /// callback used to run any analyses and register their results.
645 : struct ExternalAAWrapperPass : ImmutablePass {
646 : using CallbackT = std::function<void(Pass &, Function &, AAResults &)>;
647 :
648 : CallbackT CB;
649 :
650 : static char ID;
651 :
652 0 : ExternalAAWrapperPass() : ImmutablePass(ID) {
653 0 : initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
654 0 : }
655 :
656 2334 : explicit ExternalAAWrapperPass(CallbackT CB)
657 4668 : : ImmutablePass(ID), CB(std::move(CB)) {
658 2334 : initializeExternalAAWrapperPassPass(*PassRegistry::getPassRegistry());
659 2334 : }
660 :
661 2317 : void getAnalysisUsage(AnalysisUsage &AU) const override {
662 : AU.setPreservesAll();
663 2317 : }
664 : };
665 :
666 : } // end anonymous namespace
667 :
668 : char ExternalAAWrapperPass::ID = 0;
669 :
670 173138 : INITIALIZE_PASS(ExternalAAWrapperPass, "external-aa", "External Alias Analysis",
671 : false, true)
672 :
673 : ImmutablePass *
674 2334 : llvm::createExternalAAWrapperPass(ExternalAAWrapperPass::CallbackT Callback) {
675 2334 : return new ExternalAAWrapperPass(std::move(Callback));
676 : }
677 :
678 179318 : AAResultsWrapperPass::AAResultsWrapperPass() : FunctionPass(ID) {
679 89659 : initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
680 89659 : }
681 :
682 : char AAResultsWrapperPass::ID = 0;
683 :
684 85402 : INITIALIZE_PASS_BEGIN(AAResultsWrapperPass, "aa",
685 : "Function Alias Analysis Results", false, true)
686 85402 : INITIALIZE_PASS_DEPENDENCY(BasicAAWrapperPass)
687 85402 : INITIALIZE_PASS_DEPENDENCY(CFLAndersAAWrapperPass)
688 85402 : INITIALIZE_PASS_DEPENDENCY(CFLSteensAAWrapperPass)
689 85402 : INITIALIZE_PASS_DEPENDENCY(ExternalAAWrapperPass)
690 85402 : INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
691 85402 : INITIALIZE_PASS_DEPENDENCY(ObjCARCAAWrapperPass)
692 85402 : INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
693 85402 : INITIALIZE_PASS_DEPENDENCY(ScopedNoAliasAAWrapperPass)
694 85402 : INITIALIZE_PASS_DEPENDENCY(TypeBasedAAWrapperPass)
695 2404291 : INITIALIZE_PASS_END(AAResultsWrapperPass, "aa",
696 : "Function Alias Analysis Results", false, true)
697 :
698 0 : FunctionPass *llvm::createAAResultsWrapperPass() {
699 0 : return new AAResultsWrapperPass();
700 : }
701 :
702 : /// Run the wrapper pass to rebuild an aggregation over known AA passes.
703 : ///
704 : /// This is the legacy pass manager's interface to the new-style AA results
705 : /// aggregation object. Because this is somewhat shoe-horned into the legacy
706 : /// pass manager, we hard code all the specific alias analyses available into
707 : /// it. While the particular set enabled is configured via commandline flags,
708 : /// adding a new alias analysis to LLVM will require adding support for it to
709 : /// this list.
710 1205165 : bool AAResultsWrapperPass::runOnFunction(Function &F) {
711 : // NB! This *must* be reset before adding new AA results to the new
712 : // AAResults object because in the legacy pass manager, each instance
713 : // of these will refer to the *same* immutable analyses, registering and
714 : // unregistering themselves with them. We need to carefully tear down the
715 : // previous object first, in this case replacing it with an empty one, before
716 : // registering new results.
717 : AAR.reset(
718 1205165 : new AAResults(getAnalysis<TargetLibraryInfoWrapperPass>().getTLI()));
719 :
720 : // BasicAA is always available for function analyses. Also, we add it first
721 : // so that it can trump TBAA results when it proves MustAlias.
722 : // FIXME: TBAA should have an explicit mode to support this and then we
723 : // should reconsider the ordering here.
724 1205165 : if (!DisableBasicAA)
725 1204987 : AAR->addAAResult(getAnalysis<BasicAAWrapperPass>().getResult());
726 :
727 : // Populate the results with the currently available AAs.
728 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
729 1180715 : AAR->addAAResult(WrapperPass->getResult());
730 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
731 1180887 : AAR->addAAResult(WrapperPass->getResult());
732 1205165 : if (auto *WrapperPass =
733 1205165 : getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
734 883 : AAR->addAAResult(WrapperPass->getResult());
735 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<GlobalsAAWrapperPass>())
736 580089 : AAR->addAAResult(WrapperPass->getResult());
737 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<SCEVAAWrapperPass>())
738 7 : AAR->addAAResult(WrapperPass->getResult());
739 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
740 42 : AAR->addAAResult(WrapperPass->getResult());
741 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
742 64 : AAR->addAAResult(WrapperPass->getResult());
743 :
744 : // If available, run an external AA providing callback over the results as
745 : // well.
746 1205165 : if (auto *WrapperPass = getAnalysisIfAvailable<ExternalAAWrapperPass>())
747 156223 : if (WrapperPass->CB)
748 : WrapperPass->CB(*this, F, *AAR);
749 :
750 : // Analyses don't mutate the IR, so return false.
751 1205165 : return false;
752 : }
753 :
754 89662 : void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
755 : AU.setPreservesAll();
756 : AU.addRequired<BasicAAWrapperPass>();
757 : AU.addRequired<TargetLibraryInfoWrapperPass>();
758 :
759 : // We also need to mark all the alias analysis passes we will potentially
760 : // probe in runOnFunction as used here to ensure the legacy pass manager
761 : // preserves them. This hard coding of lists of alias analyses is specific to
762 : // the legacy pass manager.
763 : AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
764 : AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
765 : AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
766 : AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
767 : AU.addUsedIfAvailable<SCEVAAWrapperPass>();
768 : AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
769 : AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
770 89662 : }
771 :
772 1451366 : AAResults llvm::createLegacyPMAAResults(Pass &P, Function &F,
773 : BasicAAResult &BAR) {
774 1451366 : AAResults AAR(P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
775 :
776 : // Add in our explicitly constructed BasicAA results.
777 1451366 : if (!DisableBasicAA)
778 1451366 : AAR.addAAResult(BAR);
779 :
780 : // Populate the results with the other currently available AAs.
781 1451366 : if (auto *WrapperPass =
782 1451366 : P.getAnalysisIfAvailable<ScopedNoAliasAAWrapperPass>())
783 149766 : AAR.addAAResult(WrapperPass->getResult());
784 1451366 : if (auto *WrapperPass = P.getAnalysisIfAvailable<TypeBasedAAWrapperPass>())
785 149780 : AAR.addAAResult(WrapperPass->getResult());
786 1451366 : if (auto *WrapperPass =
787 1451366 : P.getAnalysisIfAvailable<objcarc::ObjCARCAAWrapperPass>())
788 86 : AAR.addAAResult(WrapperPass->getResult());
789 1451366 : if (auto *WrapperPass = P.getAnalysisIfAvailable<GlobalsAAWrapperPass>())
790 147133 : AAR.addAAResult(WrapperPass->getResult());
791 1451366 : if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLAndersAAWrapperPass>())
792 0 : AAR.addAAResult(WrapperPass->getResult());
793 1451366 : if (auto *WrapperPass = P.getAnalysisIfAvailable<CFLSteensAAWrapperPass>())
794 0 : AAR.addAAResult(WrapperPass->getResult());
795 :
796 1451366 : return AAR;
797 : }
798 :
799 28112553 : bool llvm::isNoAliasCall(const Value *V) {
800 28112553 : if (auto CS = ImmutableCallSite(V))
801 452336 : return CS.hasRetAttr(Attribute::NoAlias);
802 27660217 : return false;
803 : }
804 :
805 1714918 : bool llvm::isNoAliasArgument(const Value *V) {
806 : if (const Argument *A = dyn_cast<Argument>(V))
807 356208 : return A->hasNoAliasAttr();
808 : return false;
809 : }
810 :
811 103526845 : bool llvm::isIdentifiedObject(const Value *V) {
812 : if (isa<AllocaInst>(V))
813 : return true;
814 75303158 : if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V))
815 : return true;
816 22502077 : if (isNoAliasCall(V))
817 : return true;
818 : if (const Argument *A = dyn_cast<Argument>(V))
819 3761287 : return A->hasNoAliasAttr() || A->hasByValAttr();
820 : return false;
821 : }
822 :
823 2083965 : bool llvm::isIdentifiedFunctionLocal(const Value *V) {
824 1737245 : return isa<AllocaInst>(V) || isNoAliasCall(V) || isNoAliasArgument(V);
825 : }
826 :
827 20755 : void llvm::getAAResultsAnalysisUsage(AnalysisUsage &AU) {
828 : // This function needs to be in sync with llvm::createLegacyPMAAResults -- if
829 : // more alias analyses are added to llvm::createLegacyPMAAResults, they need
830 : // to be added here also.
831 : AU.addRequired<TargetLibraryInfoWrapperPass>();
832 : AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
833 : AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
834 : AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();
835 : AU.addUsedIfAvailable<GlobalsAAWrapperPass>();
836 : AU.addUsedIfAvailable<CFLAndersAAWrapperPass>();
837 : AU.addUsedIfAvailable<CFLSteensAAWrapperPass>();
838 20755 : }
|
