]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Analysis/AliasAnalysis.cpp
1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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,
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
25 //===----------------------------------------------------------------------===//
27 #include "llvm/Analysis/AliasAnalysis.h"
28 #include "llvm/Analysis/CFG.h"
29 #include "llvm/Analysis/CaptureTracking.h"
30 #include "llvm/Analysis/ValueTracking.h"
31 #include "llvm/IR/BasicBlock.h"
32 #include "llvm/IR/DataLayout.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/Function.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/LLVMContext.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Target/TargetLibraryInfo.h"
43 // Register the AliasAnalysis interface, providing a nice name to refer to.
44 INITIALIZE_ANALYSIS_GROUP(AliasAnalysis
, "Alias Analysis", NoAA
)
45 char AliasAnalysis::ID
= 0;
47 //===----------------------------------------------------------------------===//
48 // Default chaining methods
49 //===----------------------------------------------------------------------===//
51 AliasAnalysis::AliasResult
52 AliasAnalysis::alias(const Location
&LocA
, const Location
&LocB
) {
53 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
54 return AA
->alias(LocA
, LocB
);
57 bool AliasAnalysis::pointsToConstantMemory(const Location
&Loc
,
59 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
60 return AA
->pointsToConstantMemory(Loc
, OrLocal
);
63 AliasAnalysis::Location
64 AliasAnalysis::getArgLocation(ImmutableCallSite CS
, unsigned ArgIdx
,
65 AliasAnalysis::ModRefResult
&Mask
) {
66 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
67 return AA
->getArgLocation(CS
, ArgIdx
, Mask
);
70 void AliasAnalysis::deleteValue(Value
*V
) {
71 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
75 void AliasAnalysis::copyValue(Value
*From
, Value
*To
) {
76 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
77 AA
->copyValue(From
, To
);
80 void AliasAnalysis::addEscapingUse(Use
&U
) {
81 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
82 AA
->addEscapingUse(U
);
86 AliasAnalysis::ModRefResult
87 AliasAnalysis::getModRefInfo(ImmutableCallSite CS
,
88 const Location
&Loc
) {
89 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
91 ModRefBehavior MRB
= getModRefBehavior(CS
);
92 if (MRB
== DoesNotAccessMemory
)
95 ModRefResult Mask
= ModRef
;
96 if (onlyReadsMemory(MRB
))
99 if (onlyAccessesArgPointees(MRB
)) {
100 bool doesAlias
= false;
101 ModRefResult AllArgsMask
= NoModRef
;
102 if (doesAccessArgPointees(MRB
)) {
103 for (ImmutableCallSite::arg_iterator AI
= CS
.arg_begin(), AE
= CS
.arg_end();
105 const Value
*Arg
= *AI
;
106 if (!Arg
->getType()->isPointerTy())
108 ModRefResult ArgMask
;
110 getArgLocation(CS
, (unsigned) std::distance(CS
.arg_begin(), AI
),
112 if (!isNoAlias(CSLoc
, Loc
)) {
114 AllArgsMask
= ModRefResult(AllArgsMask
| ArgMask
);
120 Mask
= ModRefResult(Mask
& AllArgsMask
);
123 // If Loc is a constant memory location, the call definitely could not
124 // modify the memory location.
125 if ((Mask
& Mod
) && pointsToConstantMemory(Loc
))
126 Mask
= ModRefResult(Mask
& ~Mod
);
128 // If this is the end of the chain, don't forward.
129 if (!AA
) return Mask
;
131 // Otherwise, fall back to the next AA in the chain. But we can merge
132 // in any mask we've managed to compute.
133 return ModRefResult(AA
->getModRefInfo(CS
, Loc
) & Mask
);
136 AliasAnalysis::ModRefResult
137 AliasAnalysis::getModRefInfo(ImmutableCallSite CS1
, ImmutableCallSite CS2
) {
138 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
140 // If CS1 or CS2 are readnone, they don't interact.
141 ModRefBehavior CS1B
= getModRefBehavior(CS1
);
142 if (CS1B
== DoesNotAccessMemory
) return NoModRef
;
144 ModRefBehavior CS2B
= getModRefBehavior(CS2
);
145 if (CS2B
== DoesNotAccessMemory
) return NoModRef
;
147 // If they both only read from memory, there is no dependence.
148 if (onlyReadsMemory(CS1B
) && onlyReadsMemory(CS2B
))
151 AliasAnalysis::ModRefResult Mask
= ModRef
;
153 // If CS1 only reads memory, the only dependence on CS2 can be
154 // from CS1 reading memory written by CS2.
155 if (onlyReadsMemory(CS1B
))
156 Mask
= ModRefResult(Mask
& Ref
);
158 // If CS2 only access memory through arguments, accumulate the mod/ref
159 // information from CS1's references to the memory referenced by
161 if (onlyAccessesArgPointees(CS2B
)) {
162 AliasAnalysis::ModRefResult R
= NoModRef
;
163 if (doesAccessArgPointees(CS2B
)) {
164 for (ImmutableCallSite::arg_iterator
165 I
= CS2
.arg_begin(), E
= CS2
.arg_end(); I
!= E
; ++I
) {
166 const Value
*Arg
= *I
;
167 if (!Arg
->getType()->isPointerTy())
169 ModRefResult ArgMask
;
171 getArgLocation(CS2
, (unsigned) std::distance(CS2
.arg_begin(), I
),
173 // ArgMask indicates what CS2 might do to CS2Loc, and the dependence of
174 // CS1 on that location is the inverse.
177 else if (ArgMask
== Ref
)
180 R
= ModRefResult((R
| (getModRefInfo(CS1
, CS2Loc
) & ArgMask
)) & Mask
);
188 // If CS1 only accesses memory through arguments, check if CS2 references
189 // any of the memory referenced by CS1's arguments. If not, return NoModRef.
190 if (onlyAccessesArgPointees(CS1B
)) {
191 AliasAnalysis::ModRefResult R
= NoModRef
;
192 if (doesAccessArgPointees(CS1B
)) {
193 for (ImmutableCallSite::arg_iterator
194 I
= CS1
.arg_begin(), E
= CS1
.arg_end(); I
!= E
; ++I
) {
195 const Value
*Arg
= *I
;
196 if (!Arg
->getType()->isPointerTy())
198 ModRefResult ArgMask
;
199 Location CS1Loc
= getArgLocation(
200 CS1
, (unsigned)std::distance(CS1
.arg_begin(), I
), ArgMask
);
201 // ArgMask indicates what CS1 might do to CS1Loc; if CS1 might Mod
202 // CS1Loc, then we care about either a Mod or a Ref by CS2. If CS1
203 // might Ref, then we care only about a Mod by CS2.
204 ModRefResult ArgR
= getModRefInfo(CS2
, CS1Loc
);
205 if (((ArgMask
& Mod
) != NoModRef
&& (ArgR
& ModRef
) != NoModRef
) ||
206 ((ArgMask
& Ref
) != NoModRef
&& (ArgR
& Mod
) != NoModRef
))
207 R
= ModRefResult((R
| ArgMask
) & Mask
);
216 // If this is the end of the chain, don't forward.
217 if (!AA
) return Mask
;
219 // Otherwise, fall back to the next AA in the chain. But we can merge
220 // in any mask we've managed to compute.
221 return ModRefResult(AA
->getModRefInfo(CS1
, CS2
) & Mask
);
224 AliasAnalysis::ModRefBehavior
225 AliasAnalysis::getModRefBehavior(ImmutableCallSite CS
) {
226 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
228 ModRefBehavior Min
= UnknownModRefBehavior
;
230 // Call back into the alias analysis with the other form of getModRefBehavior
231 // to see if it can give a better response.
232 if (const Function
*F
= CS
.getCalledFunction())
233 Min
= getModRefBehavior(F
);
235 // If this is the end of the chain, don't forward.
238 // Otherwise, fall back to the next AA in the chain. But we can merge
239 // in any result we've managed to compute.
240 return ModRefBehavior(AA
->getModRefBehavior(CS
) & Min
);
243 AliasAnalysis::ModRefBehavior
244 AliasAnalysis::getModRefBehavior(const Function
*F
) {
245 assert(AA
&& "AA didn't call InitializeAliasAnalysis in its run method!");
246 return AA
->getModRefBehavior(F
);
249 //===----------------------------------------------------------------------===//
250 // AliasAnalysis non-virtual helper method implementation
251 //===----------------------------------------------------------------------===//
253 AliasAnalysis::Location
AliasAnalysis::getLocation(const LoadInst
*LI
) {
255 LI
->getAAMetadata(AATags
);
257 return Location(LI
->getPointerOperand(),
258 getTypeStoreSize(LI
->getType()), AATags
);
261 AliasAnalysis::Location
AliasAnalysis::getLocation(const StoreInst
*SI
) {
263 SI
->getAAMetadata(AATags
);
265 return Location(SI
->getPointerOperand(),
266 getTypeStoreSize(SI
->getValueOperand()->getType()), AATags
);
269 AliasAnalysis::Location
AliasAnalysis::getLocation(const VAArgInst
*VI
) {
271 VI
->getAAMetadata(AATags
);
273 return Location(VI
->getPointerOperand(), UnknownSize
, AATags
);
276 AliasAnalysis::Location
277 AliasAnalysis::getLocation(const AtomicCmpXchgInst
*CXI
) {
279 CXI
->getAAMetadata(AATags
);
281 return Location(CXI
->getPointerOperand(),
282 getTypeStoreSize(CXI
->getCompareOperand()->getType()),
286 AliasAnalysis::Location
287 AliasAnalysis::getLocation(const AtomicRMWInst
*RMWI
) {
289 RMWI
->getAAMetadata(AATags
);
291 return Location(RMWI
->getPointerOperand(),
292 getTypeStoreSize(RMWI
->getValOperand()->getType()), AATags
);
295 AliasAnalysis::Location
296 AliasAnalysis::getLocationForSource(const MemTransferInst
*MTI
) {
297 uint64_t Size
= UnknownSize
;
298 if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(MTI
->getLength()))
299 Size
= C
->getValue().getZExtValue();
301 // memcpy/memmove can have AA tags. For memcpy, they apply
302 // to both the source and the destination.
304 MTI
->getAAMetadata(AATags
);
306 return Location(MTI
->getRawSource(), Size
, AATags
);
309 AliasAnalysis::Location
310 AliasAnalysis::getLocationForDest(const MemIntrinsic
*MTI
) {
311 uint64_t Size
= UnknownSize
;
312 if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(MTI
->getLength()))
313 Size
= C
->getValue().getZExtValue();
315 // memcpy/memmove can have AA tags. For memcpy, they apply
316 // to both the source and the destination.
318 MTI
->getAAMetadata(AATags
);
320 return Location(MTI
->getRawDest(), Size
, AATags
);
325 AliasAnalysis::ModRefResult
326 AliasAnalysis::getModRefInfo(const LoadInst
*L
, const Location
&Loc
) {
327 // Be conservative in the face of volatile/atomic.
328 if (!L
->isUnordered())
331 // If the load address doesn't alias the given address, it doesn't read
332 // or write the specified memory.
333 if (!alias(getLocation(L
), Loc
))
336 // Otherwise, a load just reads.
340 AliasAnalysis::ModRefResult
341 AliasAnalysis::getModRefInfo(const StoreInst
*S
, const Location
&Loc
) {
342 // Be conservative in the face of volatile/atomic.
343 if (!S
->isUnordered())
346 // If the store address cannot alias the pointer in question, then the
347 // specified memory cannot be modified by the store.
348 if (!alias(getLocation(S
), Loc
))
351 // If the pointer is a pointer to constant memory, then it could not have been
352 // modified by this store.
353 if (pointsToConstantMemory(Loc
))
356 // Otherwise, a store just writes.
360 AliasAnalysis::ModRefResult
361 AliasAnalysis::getModRefInfo(const VAArgInst
*V
, const Location
&Loc
) {
362 // If the va_arg address cannot alias the pointer in question, then the
363 // specified memory cannot be accessed by the va_arg.
364 if (!alias(getLocation(V
), Loc
))
367 // If the pointer is a pointer to constant memory, then it could not have been
368 // modified by this va_arg.
369 if (pointsToConstantMemory(Loc
))
372 // Otherwise, a va_arg reads and writes.
376 AliasAnalysis::ModRefResult
377 AliasAnalysis::getModRefInfo(const AtomicCmpXchgInst
*CX
, const Location
&Loc
) {
378 // Acquire/Release cmpxchg has properties that matter for arbitrary addresses.
379 if (CX
->getSuccessOrdering() > Monotonic
)
382 // If the cmpxchg address does not alias the location, it does not access it.
383 if (!alias(getLocation(CX
), Loc
))
389 AliasAnalysis::ModRefResult
390 AliasAnalysis::getModRefInfo(const AtomicRMWInst
*RMW
, const Location
&Loc
) {
391 // Acquire/Release atomicrmw has properties that matter for arbitrary addresses.
392 if (RMW
->getOrdering() > Monotonic
)
395 // If the atomicrmw address does not alias the location, it does not access it.
396 if (!alias(getLocation(RMW
), Loc
))
402 // FIXME: this is really just shoring-up a deficiency in alias analysis.
403 // BasicAA isn't willing to spend linear time determining whether an alloca
404 // was captured before or after this particular call, while we are. However,
405 // with a smarter AA in place, this test is just wasting compile time.
406 AliasAnalysis::ModRefResult
407 AliasAnalysis::callCapturesBefore(const Instruction
*I
,
408 const AliasAnalysis::Location
&MemLoc
,
410 if (!DT
|| !DL
) return AliasAnalysis::ModRef
;
412 const Value
*Object
= GetUnderlyingObject(MemLoc
.Ptr
, DL
);
413 if (!isIdentifiedObject(Object
) || isa
<GlobalValue
>(Object
) ||
414 isa
<Constant
>(Object
))
415 return AliasAnalysis::ModRef
;
417 ImmutableCallSite
CS(I
);
418 if (!CS
.getInstruction() || CS
.getInstruction() == Object
)
419 return AliasAnalysis::ModRef
;
421 if (llvm::PointerMayBeCapturedBefore(Object
, /* ReturnCaptures */ true,
422 /* StoreCaptures */ true, I
, DT
,
423 /* include Object */ true))
424 return AliasAnalysis::ModRef
;
427 AliasAnalysis::ModRefResult R
= AliasAnalysis::NoModRef
;
428 for (ImmutableCallSite::arg_iterator CI
= CS
.arg_begin(), CE
= CS
.arg_end();
429 CI
!= CE
; ++CI
, ++ArgNo
) {
430 // Only look at the no-capture or byval pointer arguments. If this
431 // pointer were passed to arguments that were neither of these, then it
432 // couldn't be no-capture.
433 if (!(*CI
)->getType()->isPointerTy() ||
434 (!CS
.doesNotCapture(ArgNo
) && !CS
.isByValArgument(ArgNo
)))
437 // If this is a no-capture pointer argument, see if we can tell that it
438 // is impossible to alias the pointer we're checking. If not, we have to
439 // assume that the call could touch the pointer, even though it doesn't
441 if (isNoAlias(AliasAnalysis::Location(*CI
),
442 AliasAnalysis::Location(Object
)))
444 if (CS
.doesNotAccessMemory(ArgNo
))
446 if (CS
.onlyReadsMemory(ArgNo
)) {
447 R
= AliasAnalysis::Ref
;
450 return AliasAnalysis::ModRef
;
455 // AliasAnalysis destructor: DO NOT move this to the header file for
456 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
457 // the AliasAnalysis.o file in the current .a file, causing alias analysis
458 // support to not be included in the tool correctly!
460 AliasAnalysis::~AliasAnalysis() {}
462 /// InitializeAliasAnalysis - Subclasses must call this method to initialize the
463 /// AliasAnalysis interface before any other methods are called.
465 void AliasAnalysis::InitializeAliasAnalysis(Pass
*P
) {
466 DataLayoutPass
*DLP
= P
->getAnalysisIfAvailable
<DataLayoutPass
>();
467 DL
= DLP
? &DLP
->getDataLayout() : nullptr;
468 TLI
= P
->getAnalysisIfAvailable
<TargetLibraryInfo
>();
469 AA
= &P
->getAnalysis
<AliasAnalysis
>();
472 // getAnalysisUsage - All alias analysis implementations should invoke this
473 // directly (using AliasAnalysis::getAnalysisUsage(AU)).
474 void AliasAnalysis::getAnalysisUsage(AnalysisUsage
&AU
) const {
475 AU
.addRequired
<AliasAnalysis
>(); // All AA's chain
478 /// getTypeStoreSize - Return the DataLayout store size for the given type,
479 /// if known, or a conservative value otherwise.
481 uint64_t AliasAnalysis::getTypeStoreSize(Type
*Ty
) {
482 return DL
? DL
->getTypeStoreSize(Ty
) : UnknownSize
;
485 /// canBasicBlockModify - Return true if it is possible for execution of the
486 /// specified basic block to modify the location Loc.
488 bool AliasAnalysis::canBasicBlockModify(const BasicBlock
&BB
,
489 const Location
&Loc
) {
490 return canInstructionRangeModRef(BB
.front(), BB
.back(), Loc
, Mod
);
493 /// canInstructionRangeModRef - Return true if it is possible for the
494 /// execution of the specified instructions to mod\ref (according to the
495 /// mode) the location Loc. The instructions to consider are all
496 /// of the instructions in the range of [I1,I2] INCLUSIVE.
497 /// I1 and I2 must be in the same basic block.
498 bool AliasAnalysis::canInstructionRangeModRef(const Instruction
&I1
,
499 const Instruction
&I2
,
501 const ModRefResult Mode
) {
502 assert(I1
.getParent() == I2
.getParent() &&
503 "Instructions not in same basic block!");
504 BasicBlock::const_iterator I
= &I1
;
505 BasicBlock::const_iterator E
= &I2
;
506 ++E
; // Convert from inclusive to exclusive range.
508 for (; I
!= E
; ++I
) // Check every instruction in range
509 if (getModRefInfo(I
, Loc
) & Mode
)
514 /// isNoAliasCall - Return true if this pointer is returned by a noalias
516 bool llvm::isNoAliasCall(const Value
*V
) {
517 if (isa
<CallInst
>(V
) || isa
<InvokeInst
>(V
))
518 return ImmutableCallSite(cast
<Instruction
>(V
))
519 .paramHasAttr(0, Attribute::NoAlias
);
523 /// isNoAliasArgument - Return true if this is an argument with the noalias
525 bool llvm::isNoAliasArgument(const Value
*V
)
527 if (const Argument
*A
= dyn_cast
<Argument
>(V
))
528 return A
->hasNoAliasAttr();
532 /// isIdentifiedObject - Return true if this pointer refers to a distinct and
533 /// identifiable object. This returns true for:
534 /// Global Variables and Functions (but not Global Aliases)
535 /// Allocas and Mallocs
536 /// ByVal and NoAlias Arguments
539 bool llvm::isIdentifiedObject(const Value
*V
) {
540 if (isa
<AllocaInst
>(V
))
542 if (isa
<GlobalValue
>(V
) && !isa
<GlobalAlias
>(V
))
544 if (isNoAliasCall(V
))
546 if (const Argument
*A
= dyn_cast
<Argument
>(V
))
547 return A
->hasNoAliasAttr() || A
->hasByValAttr();
551 /// isIdentifiedFunctionLocal - Return true if V is umabigously identified
552 /// at the function-level. Different IdentifiedFunctionLocals can't alias.
553 /// Further, an IdentifiedFunctionLocal can not alias with any function
554 /// arguments other than itself, which is not necessarily true for
555 /// IdentifiedObjects.
556 bool llvm::isIdentifiedFunctionLocal(const Value
*V
)
558 return isa
<AllocaInst
>(V
) || isNoAliasCall(V
) || isNoAliasArgument(V
);