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().getTypeSize(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().getTypeSize(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 *PT = dyn_cast<VectorType>(BasePtr1Ty))
757 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
763 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
764 // If this is an array index, make sure the array element is in range.
765 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
766 if (Op2C->getZExtValue() >= AT->getNumElements())
767 return MayAlias; // Be conservative with out-of-range accesses
768 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
769 if (Op2C->getZExtValue() >= PT->getNumElements())
770 return MayAlias; // Be conservative with out-of-range accesses
772 } else { // Conservatively assume the minimum value for this index
773 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
778 if (BasePtr1Ty && Op1) {
779 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
780 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
785 if (BasePtr2Ty && Op2) {
786 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
787 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
793 if (GEPPointerTy->getElementType()->isSized()) {
795 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
797 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
798 assert(Offset1<Offset2 && "There is at least one different constant here!");
800 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
801 //cerr << "Determined that these two GEP's don't alias ["
802 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
810 struct VISIBILITY_HIDDEN StringCompare {
811 bool operator()(const char *LHS, const char *RHS) {
812 return strcmp(LHS, RHS) < 0;
817 // Note that this list cannot contain libm functions (such as acos and sqrt)
818 // that set errno on a domain or other error.
819 static const char *DoesntAccessMemoryFns[] = {
820 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
821 "trunc", "truncf", "truncl", "ldexp",
823 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
825 "cos", "cosf", "cosl",
826 "exp", "expf", "expl",
828 "sin", "sinf", "sinl",
829 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
831 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
834 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
835 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
838 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
839 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
841 "iswctype", "towctrans", "towlower", "towupper",
845 "isinf", "isnan", "finite",
847 // C99 math functions
848 "copysign", "copysignf", "copysignd",
849 "nexttoward", "nexttowardf", "nexttowardd",
850 "nextafter", "nextafterf", "nextafterd",
853 "__signbit", "__signbitf", "__signbitl",
857 static const char *OnlyReadsMemoryFns[] = {
858 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
859 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
862 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
863 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
867 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
868 "wcsrchr", "wcsspn", "wcsstr",
871 "alphasort", "alphasort64", "versionsort", "versionsort64",
874 "nan", "nanf", "nand",
877 "feof", "ferror", "fileno",
878 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
881 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
882 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
884 static ManagedStatic<BitVector> NoMemoryIntrinsics;
885 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
888 AliasAnalysis::ModRefBehavior
889 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
890 std::vector<PointerAccessInfo> *Info) {
891 if (!F->isDeclaration()) return UnknownModRefBehavior;
893 static bool Initialized = false;
895 NoMemoryTable->insert(NoMemoryTable->end(),
896 DoesntAccessMemoryFns,
897 array_endof(DoesntAccessMemoryFns));
899 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
901 array_endof(OnlyReadsMemoryFns));
903 // Sort the table the first time through.
904 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
905 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
908 NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
909 OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
910 #define GET_MODREF_BEHAVIOR
911 #include "llvm/Intrinsics.gen"
912 #undef GET_MODREF_BEHAVIOR
917 // If this is an intrinsic, we can use lookup tables
918 if (unsigned id = F->getIntrinsicID()) {
919 if (NoMemoryIntrinsics->test(id))
920 return DoesNotAccessMemory;
921 if (OnlyReadsMemoryIntrinsics->test(id))
922 return OnlyReadsMemory;
924 return UnknownModRefBehavior;
927 ValueName *Name = F->getValueName();
928 unsigned NameLen = Name->getKeyLength();
929 const char *NamePtr = Name->getKeyData();
931 // If there is an embedded nul character in the function name, we can never
933 if (strlen(NamePtr) != NameLen)
934 return UnknownModRefBehavior;
936 std::vector<const char*>::iterator Ptr =
937 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
938 NamePtr, StringCompare());
939 if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
940 return DoesNotAccessMemory;
942 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
943 OnlyReadsMemoryTable->end(),
944 NamePtr, StringCompare());
945 if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
946 return OnlyReadsMemory;
948 return UnknownModRefBehavior;
951 // Make sure that anything that uses AliasAnalysis pulls in this file...
952 DEFINING_FILE_FOR(BasicAliasAnalysis)