1 //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the default implementation of the Alias Analysis interface
11 // that simply implements a few identities (two different globals cannot alias,
12 // etc), but otherwise does no analysis.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/Analysis/Passes.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DerivedTypes.h"
20 #include "llvm/Function.h"
21 #include "llvm/ParameterAttributes.h"
22 #include "llvm/GlobalVariable.h"
23 #include "llvm/Instructions.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Target/TargetData.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/StringMap.h"
29 #include "llvm/ADT/BitVector.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/GetElementPtrTypeIterator.h"
33 #include "llvm/Support/ManagedStatic.h"
38 /// NoAA - This class implements the -no-aa pass, which always returns "I
39 /// don't know" for alias queries. NoAA is unlike other alias analysis
40 /// implementations, in that it does not chain to a previous analysis. As
41 /// such it doesn't follow many of the rules that other alias analyses must.
43 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
44 static char ID; // Class identification, replacement for typeinfo
45 NoAA() : ImmutablePass((intptr_t)&ID) {}
46 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { }
48 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
49 AU.addRequired<TargetData>();
52 virtual void initializePass() {
53 TD = &getAnalysis<TargetData>();
56 virtual AliasResult alias(const Value *V1, unsigned V1Size,
57 const Value *V2, unsigned V2Size) {
61 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
62 std::vector<PointerAccessInfo> *Info) {
63 return UnknownModRefBehavior;
66 virtual void getArgumentAccesses(Function *F, CallSite CS,
67 std::vector<PointerAccessInfo> &Info) {
68 assert(0 && "This method may not be called on this function!");
71 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
72 virtual bool pointsToConstantMemory(const Value *P) { return false; }
73 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
76 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
79 virtual bool hasNoModRefInfoForCalls() const { return true; }
81 virtual void deleteValue(Value *V) {}
82 virtual void copyValue(Value *From, Value *To) {}
85 // Register this pass...
88 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
90 // Declare that we implement the AliasAnalysis interface
91 RegisterAnalysisGroup<AliasAnalysis> V(U);
92 } // End of anonymous namespace
94 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
97 /// BasicAliasAnalysis - This is the default alias analysis implementation.
98 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
99 /// derives from the NoAA class.
100 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
101 static char ID; // Class identification, replacement for typeinfo
102 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { }
103 AliasResult alias(const Value *V1, unsigned V1Size,
104 const Value *V2, unsigned V2Size);
106 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
107 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
108 return NoAA::getModRefInfo(CS1,CS2);
111 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
112 /// non-escaping allocations.
113 virtual bool hasNoModRefInfoForCalls() const { return false; }
115 /// pointsToConstantMemory - Chase pointers until we find a (constant
117 bool pointsToConstantMemory(const Value *P);
119 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
120 std::vector<PointerAccessInfo> *Info);
123 // CheckGEPInstructions - Check two GEP instructions with known
124 // must-aliasing base pointers. This checks to see if the index expressions
125 // preclude the pointers from aliasing...
127 CheckGEPInstructions(const Type* BasePtr1Ty,
128 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
129 const Type *BasePtr2Ty,
130 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
133 // Register this pass...
134 char BasicAliasAnalysis::ID = 0;
135 RegisterPass<BasicAliasAnalysis>
136 X("basicaa", "Basic Alias Analysis (default AA impl)");
138 // Declare that we implement the AliasAnalysis interface
139 RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
140 } // End of anonymous namespace
142 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
143 return new BasicAliasAnalysis();
146 // getUnderlyingObject - This traverses the use chain to figure out what object
147 // the specified value points to. If the value points to, or is derived from, a
148 // unique object or an argument, return it.
149 static const Value *getUnderlyingObject(const Value *V) {
150 if (!isa<PointerType>(V->getType())) return 0;
152 // If we are at some type of object, return it. GlobalValues and Allocations
153 // have unique addresses.
154 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V))
157 // Traverse through different addressing mechanisms...
158 if (const Instruction *I = dyn_cast<Instruction>(V)) {
159 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
160 return getUnderlyingObject(I->getOperand(0));
161 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
162 if (CE->getOpcode() == Instruction::BitCast ||
163 CE->getOpcode() == Instruction::GetElementPtr)
164 return getUnderlyingObject(CE->getOperand(0));
169 static const User *isGEP(const Value *V) {
170 if (isa<GetElementPtrInst>(V) ||
171 (isa<ConstantExpr>(V) &&
172 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
173 return cast<User>(V);
177 static const Value *GetGEPOperands(const Value *V,
178 SmallVector<Value*, 16> &GEPOps){
179 assert(GEPOps.empty() && "Expect empty list to populate!");
180 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
181 cast<User>(V)->op_end());
183 // Accumulate all of the chained indexes into the operand array
184 V = cast<User>(V)->getOperand(0);
186 while (const User *G = isGEP(V)) {
187 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
188 !cast<Constant>(GEPOps[0])->isNullValue())
189 break; // Don't handle folding arbitrary pointer offsets yet...
190 GEPOps.erase(GEPOps.begin()); // Drop the zero index
191 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
192 V = G->getOperand(0);
197 /// pointsToConstantMemory - Chase pointers until we find a (constant
199 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
200 if (const Value *V = getUnderlyingObject(P))
201 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
202 return GV->isConstant();
206 // Determine if an AllocationInst instruction escapes from the function it is
207 // contained in. If it does not escape, there is no way for another function to
208 // mod/ref it. We do this by looking at its uses and determining if the uses
209 // can escape (recursively).
210 static bool AddressMightEscape(const Value *V) {
211 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
213 const Instruction *I = cast<Instruction>(*UI);
214 switch (I->getOpcode()) {
215 case Instruction::Load:
217 case Instruction::Store:
218 if (I->getOperand(0) == V)
219 return true; // Escapes if the pointer is stored.
221 case Instruction::GetElementPtr:
222 if (AddressMightEscape(I))
225 case Instruction::BitCast:
226 if (!isa<PointerType>(I->getType()))
228 if (AddressMightEscape(I))
231 case Instruction::Ret:
232 // If returned, the address will escape to calling functions, but no
233 // callees could modify it.
242 // getModRefInfo - Check to see if the specified callsite can clobber the
243 // specified memory object. Since we only look at local properties of this
244 // function, we really can't say much about this query. We do, however, use
245 // simple "address taken" analysis on local objects.
247 AliasAnalysis::ModRefResult
248 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
249 if (!isa<Constant>(P))
250 if (const AllocationInst *AI =
251 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
252 // Okay, the pointer is to a stack allocated object. If we can prove that
253 // the pointer never "escapes", then we know the call cannot clobber it,
254 // because it simply can't get its address.
255 if (!AddressMightEscape(AI))
258 // If this is a tail call and P points to a stack location, we know that
259 // the tail call cannot access or modify the local stack.
260 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
261 if (CI->isTailCall() && isa<AllocaInst>(AI))
265 // The AliasAnalysis base class has some smarts, lets use them.
266 return AliasAnalysis::getModRefInfo(CS, P, Size);
269 static bool isNoAliasArgument(const Argument *Arg) {
270 const Function *Func = Arg->getParent();
271 const ParamAttrsList *Attr = Func->getFunctionType()->getParamAttrs();
274 for (Function::const_arg_iterator I = Func->arg_begin(),
275 E = Func->arg_end(); I != E; ++I, ++Idx) {
277 Attr->paramHasAttr(Idx, ParamAttr::NoAlias))
284 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
285 // as array references. Note that this function is heavily tail recursive.
286 // Hopefully we have a smart C++ compiler. :)
288 AliasAnalysis::AliasResult
289 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
290 const Value *V2, unsigned V2Size) {
291 // Strip off any constant expression casts if they exist
292 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
293 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
294 V1 = CE->getOperand(0);
295 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
296 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
297 V2 = CE->getOperand(0);
299 // Are we checking for alias of the same value?
300 if (V1 == V2) return MustAlias;
302 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
303 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty)
304 return NoAlias; // Scalars cannot alias each other
306 // Strip off cast instructions...
307 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
308 return alias(I->getOperand(0), V1Size, V2, V2Size);
309 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
310 return alias(V1, V1Size, I->getOperand(0), V2Size);
312 // Figure out what objects these things are pointing to if we can...
313 const Value *O1 = getUnderlyingObject(V1);
314 const Value *O2 = getUnderlyingObject(V2);
316 // Pointing at a discernible object?
319 if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
320 // Incoming argument cannot alias locally allocated object!
321 if (isa<AllocationInst>(O2)) return NoAlias;
323 // If they are two different objects, and one is a noalias argument
324 // then they do not alias.
325 if (O1 != O2 && isNoAliasArgument(O1Arg))
328 // Otherwise, nothing is known...
331 if (const Argument *O2Arg = dyn_cast<Argument>(O2)) {
332 // Incoming argument cannot alias locally allocated object!
333 if (isa<AllocationInst>(O1)) return NoAlias;
335 // If they are two different objects, and one is a noalias argument
336 // then they do not alias.
337 if (O1 != O2 && isNoAliasArgument(O2Arg))
340 // Otherwise, nothing is known...
342 } else if (O1 != O2) {
343 if (!isa<Argument>(O1))
344 // If they are two different objects, and neither is an argument,
345 // we know that we have no alias...
349 // If they are the same object, they we can look at the indexes. If they
350 // index off of the object is the same for both pointers, they must alias.
351 // If they are provably different, they must not alias. Otherwise, we
352 // can't tell anything.
356 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
357 return NoAlias; // Unique values don't alias null
359 if (isa<GlobalVariable>(O1) ||
360 (isa<AllocationInst>(O1) &&
361 !cast<AllocationInst>(O1)->isArrayAllocation()))
362 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
363 // If the size of the other access is larger than the total size of the
364 // global/alloca/malloc, it cannot be accessing the global (it's
365 // undefined to load or store bytes before or after an object).
366 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
367 unsigned GlobalSize = getTargetData().getABITypeSize(ElTy);
368 if (GlobalSize < V2Size && V2Size != ~0U)
374 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
375 return NoAlias; // Unique values don't alias null
377 if (isa<GlobalVariable>(O2) ||
378 (isa<AllocationInst>(O2) &&
379 !cast<AllocationInst>(O2)->isArrayAllocation()))
380 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
381 // If the size of the other access is larger than the total size of the
382 // global/alloca/malloc, it cannot be accessing the object (it's
383 // undefined to load or store bytes before or after an object).
384 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
385 unsigned GlobalSize = getTargetData().getABITypeSize(ElTy);
386 if (GlobalSize < V1Size && V1Size != ~0U)
391 // If we have two gep instructions with must-alias'ing base pointers, figure
392 // out if the indexes to the GEP tell us anything about the derived pointer.
393 // Note that we also handle chains of getelementptr instructions as well as
394 // constant expression getelementptrs here.
396 if (isGEP(V1) && isGEP(V2)) {
397 // Drill down into the first non-gep value, to test for must-aliasing of
398 // the base pointers.
399 const Value *BasePtr1 = V1, *BasePtr2 = V2;
401 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
402 } while (isGEP(BasePtr1) &&
403 cast<User>(BasePtr1)->getOperand(1) ==
404 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
406 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
407 } while (isGEP(BasePtr2) &&
408 cast<User>(BasePtr2)->getOperand(1) ==
409 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
411 // Do the base pointers alias?
412 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
413 if (BaseAlias == NoAlias) return NoAlias;
414 if (BaseAlias == MustAlias) {
415 // If the base pointers alias each other exactly, check to see if we can
416 // figure out anything about the resultant pointers, to try to prove
419 // Collect all of the chained GEP operands together into one simple place
420 SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
421 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
422 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
424 // If GetGEPOperands were able to fold to the same must-aliased pointer,
425 // do the comparison.
426 if (BasePtr1 == BasePtr2) {
428 CheckGEPInstructions(BasePtr1->getType(),
429 &GEP1Ops[0], GEP1Ops.size(), V1Size,
431 &GEP2Ops[0], GEP2Ops.size(), V2Size);
432 if (GAlias != MayAlias)
438 // Check to see if these two pointers are related by a getelementptr
439 // instruction. If one pointer is a GEP with a non-zero index of the other
440 // pointer, we know they cannot alias.
444 std::swap(V1Size, V2Size);
447 if (V1Size != ~0U && V2Size != ~0U)
449 SmallVector<Value*, 16> GEPOperands;
450 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
452 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
453 if (R == MustAlias) {
454 // If there is at least one non-zero constant index, we know they cannot
456 bool ConstantFound = false;
457 bool AllZerosFound = true;
458 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
459 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
460 if (!C->isNullValue()) {
461 ConstantFound = true;
462 AllZerosFound = false;
466 AllZerosFound = false;
469 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
470 // the ptr, the end result is a must alias also.
475 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
478 // Otherwise we have to check to see that the distance is more than
479 // the size of the argument... build an index vector that is equal to
480 // the arguments provided, except substitute 0's for any variable
481 // indexes we find...
482 if (cast<PointerType>(
483 BasePtr->getType())->getElementType()->isSized()) {
484 for (unsigned i = 0; i != GEPOperands.size(); ++i)
485 if (!isa<ConstantInt>(GEPOperands[i]))
487 Constant::getNullValue(GEPOperands[i]->getType());
489 getTargetData().getIndexedOffset(BasePtr->getType(),
493 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
503 // This function is used to determin if the indices of two GEP instructions are
504 // equal. V1 and V2 are the indices.
505 static bool IndexOperandsEqual(Value *V1, Value *V2) {
506 if (V1->getType() == V2->getType())
508 if (Constant *C1 = dyn_cast<Constant>(V1))
509 if (Constant *C2 = dyn_cast<Constant>(V2)) {
510 // Sign extend the constants to long types, if necessary
511 if (C1->getType() != Type::Int64Ty)
512 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
513 if (C2->getType() != Type::Int64Ty)
514 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
520 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
521 /// base pointers. This checks to see if the index expressions preclude the
522 /// pointers from aliasing...
523 AliasAnalysis::AliasResult
524 BasicAliasAnalysis::CheckGEPInstructions(
525 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
526 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
527 // We currently can't handle the case when the base pointers have different
528 // primitive types. Since this is uncommon anyway, we are happy being
529 // extremely conservative.
530 if (BasePtr1Ty != BasePtr2Ty)
533 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
535 // Find the (possibly empty) initial sequence of equal values... which are not
536 // necessarily constants.
537 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
538 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
539 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
540 unsigned UnequalOper = 0;
541 while (UnequalOper != MinOperands &&
542 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
543 // Advance through the type as we go...
545 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
546 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
548 // If all operands equal each other, then the derived pointers must
549 // alias each other...
551 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
552 "Ran out of type nesting, but not out of operands?");
557 // If we have seen all constant operands, and run out of indexes on one of the
558 // getelementptrs, check to see if the tail of the leftover one is all zeros.
559 // If so, return mustalias.
560 if (UnequalOper == MinOperands) {
561 if (NumGEP1Ops < NumGEP2Ops) {
562 std::swap(GEP1Ops, GEP2Ops);
563 std::swap(NumGEP1Ops, NumGEP2Ops);
566 bool AllAreZeros = true;
567 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
568 if (!isa<Constant>(GEP1Ops[i]) ||
569 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
573 if (AllAreZeros) return MustAlias;
577 // So now we know that the indexes derived from the base pointers,
578 // which are known to alias, are different. We can still determine a
579 // no-alias result if there are differing constant pairs in the index
580 // chain. For example:
581 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
583 // We have to be careful here about array accesses. In particular, consider:
584 // A[1][0] vs A[0][i]
585 // In this case, we don't *know* that the array will be accessed in bounds:
586 // the index could even be negative. Because of this, we have to
587 // conservatively *give up* and return may alias. We disregard differing
588 // array subscripts that are followed by a variable index without going
591 unsigned SizeMax = std::max(G1S, G2S);
592 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
594 // Scan for the first operand that is constant and unequal in the
595 // two getelementptrs...
596 unsigned FirstConstantOper = UnequalOper;
597 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
598 const Value *G1Oper = GEP1Ops[FirstConstantOper];
599 const Value *G2Oper = GEP2Ops[FirstConstantOper];
601 if (G1Oper != G2Oper) // Found non-equal constant indexes...
602 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
603 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
604 if (G1OC->getType() != G2OC->getType()) {
605 // Sign extend both operands to long.
606 if (G1OC->getType() != Type::Int64Ty)
607 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
608 if (G2OC->getType() != Type::Int64Ty)
609 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
610 GEP1Ops[FirstConstantOper] = G1OC;
611 GEP2Ops[FirstConstantOper] = G2OC;
615 // Handle the "be careful" case above: if this is an array/vector
616 // subscript, scan for a subsequent variable array index.
617 if (isa<SequentialType>(BasePtr1Ty)) {
619 cast<SequentialType>(BasePtr1Ty)->getElementType();
620 bool isBadCase = false;
622 for (unsigned Idx = FirstConstantOper+1;
623 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
624 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
625 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
629 NextTy = cast<SequentialType>(NextTy)->getElementType();
632 if (isBadCase) G1OC = 0;
635 // Make sure they are comparable (ie, not constant expressions), and
636 // make sure the GEP with the smaller leading constant is GEP1.
638 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
640 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
641 if (CV->getZExtValue()) { // If they are comparable and G2 > G1
642 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
643 std::swap(NumGEP1Ops, NumGEP2Ops);
650 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
653 // No shared constant operands, and we ran out of common operands. At this
654 // point, the GEP instructions have run through all of their operands, and we
655 // haven't found evidence that there are any deltas between the GEP's.
656 // However, one GEP may have more operands than the other. If this is the
657 // case, there may still be hope. Check this now.
658 if (FirstConstantOper == MinOperands) {
659 // Make GEP1Ops be the longer one if there is a longer one.
660 if (NumGEP1Ops < NumGEP2Ops) {
661 std::swap(GEP1Ops, GEP2Ops);
662 std::swap(NumGEP1Ops, NumGEP2Ops);
665 // Is there anything to check?
666 if (NumGEP1Ops > MinOperands) {
667 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
668 if (isa<ConstantInt>(GEP1Ops[i]) &&
669 !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
670 // Yup, there's a constant in the tail. Set all variables to
671 // constants in the GEP instruction to make it suiteable for
672 // TargetData::getIndexedOffset.
673 for (i = 0; i != MaxOperands; ++i)
674 if (!isa<ConstantInt>(GEP1Ops[i]))
675 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
676 // Okay, now get the offset. This is the relative offset for the full
678 const TargetData &TD = getTargetData();
679 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
682 // Now check without any constants at the end.
683 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
686 // If the tail provided a bit enough offset, return noalias!
687 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
692 // Couldn't find anything useful.
696 // If there are non-equal constants arguments, then we can figure
697 // out a minimum known delta between the two index expressions... at
698 // this point we know that the first constant index of GEP1 is less
699 // than the first constant index of GEP2.
701 // Advance BasePtr[12]Ty over this first differing constant operand.
702 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
703 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
704 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
705 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
707 // We are going to be using TargetData::getIndexedOffset to determine the
708 // offset that each of the GEP's is reaching. To do this, we have to convert
709 // all variable references to constant references. To do this, we convert the
710 // initial sequence of array subscripts into constant zeros to start with.
711 const Type *ZeroIdxTy = GEPPointerTy;
712 for (unsigned i = 0; i != FirstConstantOper; ++i) {
713 if (!isa<StructType>(ZeroIdxTy))
714 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
716 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
717 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
720 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
722 // Loop over the rest of the operands...
723 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
724 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
725 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
726 // If they are equal, use a zero index...
727 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
728 if (!isa<ConstantInt>(Op1))
729 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
730 // Otherwise, just keep the constants we have.
733 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
734 // If this is an array index, make sure the array element is in range.
735 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
736 if (Op1C->getZExtValue() >= AT->getNumElements())
737 return MayAlias; // Be conservative with out-of-range accesses
738 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
739 if (Op1C->getZExtValue() >= PT->getNumElements())
740 return MayAlias; // Be conservative with out-of-range accesses
744 // GEP1 is known to produce a value less than GEP2. To be
745 // conservatively correct, we must assume the largest possible
746 // constant is used in this position. This cannot be the initial
747 // index to the GEP instructions (because we know we have at least one
748 // element before this one with the different constant arguments), so
749 // we know that the current index must be into either a struct or
750 // array. Because we know it's not constant, this cannot be a
751 // structure index. Because of this, we can calculate the maximum
754 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
755 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
756 else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty))
757 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,VT->getNumElements()-1);
762 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
763 // If this is an array index, make sure the array element is in range.
764 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
765 if (Op2C->getZExtValue() >= AT->getNumElements())
766 return MayAlias; // Be conservative with out-of-range accesses
767 } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) {
768 if (Op2C->getZExtValue() >= VT->getNumElements())
769 return MayAlias; // Be conservative with out-of-range accesses
771 } else { // Conservatively assume the minimum value for this index
772 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
777 if (BasePtr1Ty && Op1) {
778 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
779 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
784 if (BasePtr2Ty && Op2) {
785 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
786 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
792 if (GEPPointerTy->getElementType()->isSized()) {
794 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
796 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
797 assert(Offset1 != Offset2 &&
798 "There is at least one different constant here!");
800 // Make sure we compare the absolute difference.
801 if (Offset1 > Offset2)
802 std::swap(Offset1, Offset2);
804 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
805 //cerr << "Determined that these two GEP's don't alias ["
806 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
814 struct VISIBILITY_HIDDEN StringCompare {
815 bool operator()(const char *LHS, const char *RHS) {
816 return strcmp(LHS, RHS) < 0;
821 // Note that this list cannot contain libm functions (such as acos and sqrt)
822 // that set errno on a domain or other error.
823 static const char *DoesntAccessMemoryFns[] = {
824 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
825 "trunc", "truncf", "truncl", "ldexp",
827 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
829 "cos", "cosf", "cosl",
830 "exp", "expf", "expl",
832 "sin", "sinf", "sinl",
833 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
835 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
838 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
839 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
842 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
843 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
845 "iswctype", "towctrans", "towlower", "towupper",
849 "isinf", "isnan", "finite",
851 // C99 math functions
852 "copysign", "copysignf", "copysignd",
853 "nexttoward", "nexttowardf", "nexttowardd",
854 "nextafter", "nextafterf", "nextafterd",
857 "__signbit", "__signbitf", "__signbitl",
861 static const char *OnlyReadsMemoryFns[] = {
862 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
863 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
866 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
867 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
871 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
872 "wcsrchr", "wcsspn", "wcsstr",
875 "alphasort", "alphasort64", "versionsort", "versionsort64",
878 "nan", "nanf", "nand",
881 "feof", "ferror", "fileno",
882 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
885 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
886 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
888 static ManagedStatic<BitVector> NoMemoryIntrinsics;
889 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
892 AliasAnalysis::ModRefBehavior
893 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
894 std::vector<PointerAccessInfo> *Info) {
895 if (!F->isDeclaration()) return UnknownModRefBehavior;
897 static bool Initialized = false;
899 NoMemoryTable->insert(NoMemoryTable->end(),
900 DoesntAccessMemoryFns,
901 array_endof(DoesntAccessMemoryFns));
903 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
905 array_endof(OnlyReadsMemoryFns));
907 // Sort the table the first time through.
908 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
909 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
912 NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
913 OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
914 #define GET_MODREF_BEHAVIOR
915 #include "llvm/Intrinsics.gen"
916 #undef GET_MODREF_BEHAVIOR
921 // If this is an intrinsic, we can use lookup tables
922 if (unsigned id = F->getIntrinsicID()) {
923 if (NoMemoryIntrinsics->test(id))
924 return DoesNotAccessMemory;
925 if (OnlyReadsMemoryIntrinsics->test(id))
926 return OnlyReadsMemory;
928 return UnknownModRefBehavior;
931 ValueName *Name = F->getValueName();
933 return UnknownModRefBehavior;
935 unsigned NameLen = Name->getKeyLength();
936 const char *NamePtr = Name->getKeyData();
938 // If there is an embedded nul character in the function name, we can never
940 if (strlen(NamePtr) != NameLen)
941 return UnknownModRefBehavior;
943 std::vector<const char*>::iterator Ptr =
944 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
945 NamePtr, StringCompare());
946 if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
947 return DoesNotAccessMemory;
949 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
950 OnlyReadsMemoryTable->end(),
951 NamePtr, StringCompare());
952 if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
953 return OnlyReadsMemory;
955 const ParamAttrsList *Attrs = F->getFunctionType()->getParamAttrs();
956 if (Attrs && Attrs->paramHasAttr(0, ParamAttr::ReadNone))
957 return DoesNotAccessMemory;
958 if (Attrs && Attrs->paramHasAttr(0, ParamAttr::ReadOnly))
959 return OnlyReadsMemory;
961 return UnknownModRefBehavior;
964 // Make sure that anything that uses AliasAnalysis pulls in this file...
965 DEFINING_FILE_FOR(BasicAliasAnalysis)