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...
341 } else if (O1 != O2) {
342 // If they are two different objects, we know that we have no alias...
346 // If they are the same object, they we can look at the indexes. If they
347 // index off of the object is the same for both pointers, they must alias.
348 // If they are provably different, they must not alias. Otherwise, we
349 // can't tell anything.
353 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
354 return NoAlias; // Unique values don't alias null
356 if (isa<GlobalVariable>(O1) ||
357 (isa<AllocationInst>(O1) &&
358 !cast<AllocationInst>(O1)->isArrayAllocation()))
359 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
360 // If the size of the other access is larger than the total size of the
361 // global/alloca/malloc, it cannot be accessing the global (it's
362 // undefined to load or store bytes before or after an object).
363 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
364 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
365 if (GlobalSize < V2Size && V2Size != ~0U)
371 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
372 return NoAlias; // Unique values don't alias null
374 if (isa<GlobalVariable>(O2) ||
375 (isa<AllocationInst>(O2) &&
376 !cast<AllocationInst>(O2)->isArrayAllocation()))
377 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
378 // If the size of the other access is larger than the total size of the
379 // global/alloca/malloc, it cannot be accessing the object (it's
380 // undefined to load or store bytes before or after an object).
381 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
382 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
383 if (GlobalSize < V1Size && V1Size != ~0U)
388 // If we have two gep instructions with must-alias'ing base pointers, figure
389 // out if the indexes to the GEP tell us anything about the derived pointer.
390 // Note that we also handle chains of getelementptr instructions as well as
391 // constant expression getelementptrs here.
393 if (isGEP(V1) && isGEP(V2)) {
394 // Drill down into the first non-gep value, to test for must-aliasing of
395 // the base pointers.
396 const Value *BasePtr1 = V1, *BasePtr2 = V2;
398 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
399 } while (isGEP(BasePtr1) &&
400 cast<User>(BasePtr1)->getOperand(1) ==
401 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
403 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
404 } while (isGEP(BasePtr2) &&
405 cast<User>(BasePtr2)->getOperand(1) ==
406 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
408 // Do the base pointers alias?
409 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
410 if (BaseAlias == NoAlias) return NoAlias;
411 if (BaseAlias == MustAlias) {
412 // If the base pointers alias each other exactly, check to see if we can
413 // figure out anything about the resultant pointers, to try to prove
416 // Collect all of the chained GEP operands together into one simple place
417 SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
418 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
419 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
421 // If GetGEPOperands were able to fold to the same must-aliased pointer,
422 // do the comparison.
423 if (BasePtr1 == BasePtr2) {
425 CheckGEPInstructions(BasePtr1->getType(),
426 &GEP1Ops[0], GEP1Ops.size(), V1Size,
428 &GEP2Ops[0], GEP2Ops.size(), V2Size);
429 if (GAlias != MayAlias)
435 // Check to see if these two pointers are related by a getelementptr
436 // instruction. If one pointer is a GEP with a non-zero index of the other
437 // pointer, we know they cannot alias.
441 std::swap(V1Size, V2Size);
444 if (V1Size != ~0U && V2Size != ~0U)
446 SmallVector<Value*, 16> GEPOperands;
447 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
449 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
450 if (R == MustAlias) {
451 // If there is at least one non-zero constant index, we know they cannot
453 bool ConstantFound = false;
454 bool AllZerosFound = true;
455 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
456 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
457 if (!C->isNullValue()) {
458 ConstantFound = true;
459 AllZerosFound = false;
463 AllZerosFound = false;
466 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
467 // the ptr, the end result is a must alias also.
472 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
475 // Otherwise we have to check to see that the distance is more than
476 // the size of the argument... build an index vector that is equal to
477 // the arguments provided, except substitute 0's for any variable
478 // indexes we find...
479 if (cast<PointerType>(
480 BasePtr->getType())->getElementType()->isSized()) {
481 for (unsigned i = 0; i != GEPOperands.size(); ++i)
482 if (!isa<ConstantInt>(GEPOperands[i]))
484 Constant::getNullValue(GEPOperands[i]->getType());
486 getTargetData().getIndexedOffset(BasePtr->getType(),
490 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
500 // This function is used to determin if the indices of two GEP instructions are
501 // equal. V1 and V2 are the indices.
502 static bool IndexOperandsEqual(Value *V1, Value *V2) {
503 if (V1->getType() == V2->getType())
505 if (Constant *C1 = dyn_cast<Constant>(V1))
506 if (Constant *C2 = dyn_cast<Constant>(V2)) {
507 // Sign extend the constants to long types, if necessary
508 if (C1->getType() != Type::Int64Ty)
509 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
510 if (C2->getType() != Type::Int64Ty)
511 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
517 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
518 /// base pointers. This checks to see if the index expressions preclude the
519 /// pointers from aliasing...
520 AliasAnalysis::AliasResult
521 BasicAliasAnalysis::CheckGEPInstructions(
522 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
523 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
524 // We currently can't handle the case when the base pointers have different
525 // primitive types. Since this is uncommon anyway, we are happy being
526 // extremely conservative.
527 if (BasePtr1Ty != BasePtr2Ty)
530 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
532 // Find the (possibly empty) initial sequence of equal values... which are not
533 // necessarily constants.
534 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
535 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
536 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
537 unsigned UnequalOper = 0;
538 while (UnequalOper != MinOperands &&
539 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
540 // Advance through the type as we go...
542 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
543 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
545 // If all operands equal each other, then the derived pointers must
546 // alias each other...
548 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
549 "Ran out of type nesting, but not out of operands?");
554 // If we have seen all constant operands, and run out of indexes on one of the
555 // getelementptrs, check to see if the tail of the leftover one is all zeros.
556 // If so, return mustalias.
557 if (UnequalOper == MinOperands) {
558 if (NumGEP1Ops < NumGEP2Ops) {
559 std::swap(GEP1Ops, GEP2Ops);
560 std::swap(NumGEP1Ops, NumGEP2Ops);
563 bool AllAreZeros = true;
564 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
565 if (!isa<Constant>(GEP1Ops[i]) ||
566 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
570 if (AllAreZeros) return MustAlias;
574 // So now we know that the indexes derived from the base pointers,
575 // which are known to alias, are different. We can still determine a
576 // no-alias result if there are differing constant pairs in the index
577 // chain. For example:
578 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
580 // We have to be careful here about array accesses. In particular, consider:
581 // A[1][0] vs A[0][i]
582 // In this case, we don't *know* that the array will be accessed in bounds:
583 // the index could even be negative. Because of this, we have to
584 // conservatively *give up* and return may alias. We disregard differing
585 // array subscripts that are followed by a variable index without going
588 unsigned SizeMax = std::max(G1S, G2S);
589 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
591 // Scan for the first operand that is constant and unequal in the
592 // two getelementptrs...
593 unsigned FirstConstantOper = UnequalOper;
594 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
595 const Value *G1Oper = GEP1Ops[FirstConstantOper];
596 const Value *G2Oper = GEP2Ops[FirstConstantOper];
598 if (G1Oper != G2Oper) // Found non-equal constant indexes...
599 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
600 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
601 if (G1OC->getType() != G2OC->getType()) {
602 // Sign extend both operands to long.
603 if (G1OC->getType() != Type::Int64Ty)
604 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
605 if (G2OC->getType() != Type::Int64Ty)
606 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
607 GEP1Ops[FirstConstantOper] = G1OC;
608 GEP2Ops[FirstConstantOper] = G2OC;
612 // Handle the "be careful" case above: if this is an array/vector
613 // subscript, scan for a subsequent variable array index.
614 if (isa<SequentialType>(BasePtr1Ty)) {
616 cast<SequentialType>(BasePtr1Ty)->getElementType();
617 bool isBadCase = false;
619 for (unsigned Idx = FirstConstantOper+1;
620 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
621 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
622 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
626 NextTy = cast<SequentialType>(NextTy)->getElementType();
629 if (isBadCase) G1OC = 0;
632 // Make sure they are comparable (ie, not constant expressions), and
633 // make sure the GEP with the smaller leading constant is GEP1.
635 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
637 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
638 if (CV->getZExtValue()) { // If they are comparable and G2 > G1
639 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
640 std::swap(NumGEP1Ops, NumGEP2Ops);
647 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
650 // No shared constant operands, and we ran out of common operands. At this
651 // point, the GEP instructions have run through all of their operands, and we
652 // haven't found evidence that there are any deltas between the GEP's.
653 // However, one GEP may have more operands than the other. If this is the
654 // case, there may still be hope. Check this now.
655 if (FirstConstantOper == MinOperands) {
656 // Make GEP1Ops be the longer one if there is a longer one.
657 if (NumGEP1Ops < NumGEP2Ops) {
658 std::swap(GEP1Ops, GEP2Ops);
659 std::swap(NumGEP1Ops, NumGEP2Ops);
662 // Is there anything to check?
663 if (NumGEP1Ops > MinOperands) {
664 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
665 if (isa<ConstantInt>(GEP1Ops[i]) &&
666 !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
667 // Yup, there's a constant in the tail. Set all variables to
668 // constants in the GEP instruction to make it suiteable for
669 // TargetData::getIndexedOffset.
670 for (i = 0; i != MaxOperands; ++i)
671 if (!isa<ConstantInt>(GEP1Ops[i]))
672 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
673 // Okay, now get the offset. This is the relative offset for the full
675 const TargetData &TD = getTargetData();
676 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
679 // Now check without any constants at the end.
680 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
683 // If the tail provided a bit enough offset, return noalias!
684 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
689 // Couldn't find anything useful.
693 // If there are non-equal constants arguments, then we can figure
694 // out a minimum known delta between the two index expressions... at
695 // this point we know that the first constant index of GEP1 is less
696 // than the first constant index of GEP2.
698 // Advance BasePtr[12]Ty over this first differing constant operand.
699 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
700 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
701 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
702 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
704 // We are going to be using TargetData::getIndexedOffset to determine the
705 // offset that each of the GEP's is reaching. To do this, we have to convert
706 // all variable references to constant references. To do this, we convert the
707 // initial sequence of array subscripts into constant zeros to start with.
708 const Type *ZeroIdxTy = GEPPointerTy;
709 for (unsigned i = 0; i != FirstConstantOper; ++i) {
710 if (!isa<StructType>(ZeroIdxTy))
711 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
713 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
714 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
717 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
719 // Loop over the rest of the operands...
720 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
721 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
722 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
723 // If they are equal, use a zero index...
724 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
725 if (!isa<ConstantInt>(Op1))
726 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
727 // Otherwise, just keep the constants we have.
730 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
731 // If this is an array index, make sure the array element is in range.
732 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
733 if (Op1C->getZExtValue() >= AT->getNumElements())
734 return MayAlias; // Be conservative with out-of-range accesses
735 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
736 if (Op1C->getZExtValue() >= PT->getNumElements())
737 return MayAlias; // Be conservative with out-of-range accesses
741 // GEP1 is known to produce a value less than GEP2. To be
742 // conservatively correct, we must assume the largest possible
743 // constant is used in this position. This cannot be the initial
744 // index to the GEP instructions (because we know we have at least one
745 // element before this one with the different constant arguments), so
746 // we know that the current index must be into either a struct or
747 // array. Because we know it's not constant, this cannot be a
748 // structure index. Because of this, we can calculate the maximum
751 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
752 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
753 else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
754 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
760 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
761 // If this is an array index, make sure the array element is in range.
762 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
763 if (Op2C->getZExtValue() >= AT->getNumElements())
764 return MayAlias; // Be conservative with out-of-range accesses
765 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
766 if (Op2C->getZExtValue() >= PT->getNumElements())
767 return MayAlias; // Be conservative with out-of-range accesses
769 } else { // Conservatively assume the minimum value for this index
770 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
775 if (BasePtr1Ty && Op1) {
776 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
777 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
782 if (BasePtr2Ty && Op2) {
783 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
784 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
790 if (GEPPointerTy->getElementType()->isSized()) {
792 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
794 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
795 assert(Offset1<Offset2 && "There is at least one different constant here!");
797 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
798 //cerr << "Determined that these two GEP's don't alias ["
799 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
807 struct VISIBILITY_HIDDEN StringCompare {
808 bool operator()(const char *LHS, const char *RHS) {
809 return strcmp(LHS, RHS) < 0;
814 // Note that this list cannot contain libm functions (such as acos and sqrt)
815 // that set errno on a domain or other error.
816 static const char *DoesntAccessMemoryFns[] = {
817 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
818 "trunc", "truncf", "truncl", "ldexp",
820 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
822 "cos", "cosf", "cosl",
823 "exp", "expf", "expl",
825 "sin", "sinf", "sinl",
826 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
828 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
831 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
832 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
835 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
836 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
838 "iswctype", "towctrans", "towlower", "towupper",
842 "isinf", "isnan", "finite",
844 // C99 math functions
845 "copysign", "copysignf", "copysignd",
846 "nexttoward", "nexttowardf", "nexttowardd",
847 "nextafter", "nextafterf", "nextafterd",
850 "__signbit", "__signbitf", "__signbitl",
854 static const char *OnlyReadsMemoryFns[] = {
855 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
856 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
859 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
860 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
864 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
865 "wcsrchr", "wcsspn", "wcsstr",
868 "alphasort", "alphasort64", "versionsort", "versionsort64",
871 "nan", "nanf", "nand",
874 "feof", "ferror", "fileno",
875 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
878 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
879 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
881 static ManagedStatic<BitVector> NoMemoryIntrinsics;
882 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
885 AliasAnalysis::ModRefBehavior
886 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
887 std::vector<PointerAccessInfo> *Info) {
888 if (!F->isDeclaration()) return UnknownModRefBehavior;
890 static bool Initialized = false;
892 NoMemoryTable->insert(NoMemoryTable->end(),
893 DoesntAccessMemoryFns,
894 array_endof(DoesntAccessMemoryFns));
896 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
898 array_endof(OnlyReadsMemoryFns));
900 // Sort the table the first time through.
901 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
902 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
905 NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
906 OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
907 #define GET_MODREF_BEHAVIOR
908 #include "llvm/Intrinsics.gen"
909 #undef GET_MODREF_BEHAVIOR
914 // If this is an intrinsic, we can use lookup tables
915 if (unsigned id = F->getIntrinsicID()) {
916 if (NoMemoryIntrinsics->test(id))
917 return DoesNotAccessMemory;
918 if (OnlyReadsMemoryIntrinsics->test(id))
919 return OnlyReadsMemory;
921 return UnknownModRefBehavior;
924 ValueName *Name = F->getValueName();
925 unsigned NameLen = Name->getKeyLength();
926 const char *NamePtr = Name->getKeyData();
928 // If there is an embedded nul character in the function name, we can never
930 if (strlen(NamePtr) != NameLen)
931 return UnknownModRefBehavior;
933 std::vector<const char*>::iterator Ptr =
934 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
935 NamePtr, StringCompare());
936 if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
937 return DoesNotAccessMemory;
939 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
940 OnlyReadsMemoryTable->end(),
941 NamePtr, StringCompare());
942 if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
943 return OnlyReadsMemory;
945 return UnknownModRefBehavior;
948 // Make sure that anything that uses AliasAnalysis pulls in this file...
949 DEFINING_FILE_FOR(BasicAliasAnalysis)