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/Support/Compiler.h"
31 #include "llvm/Support/GetElementPtrTypeIterator.h"
32 #include "llvm/Support/ManagedStatic.h"
37 /// NoAA - This class implements the -no-aa pass, which always returns "I
38 /// don't know" for alias queries. NoAA is unlike other alias analysis
39 /// implementations, in that it does not chain to a previous analysis. As
40 /// such it doesn't follow many of the rules that other alias analyses must.
42 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
43 static char ID; // Class identification, replacement for typeinfo
44 NoAA() : ImmutablePass((intptr_t)&ID) {}
45 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { }
47 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
48 AU.addRequired<TargetData>();
51 virtual void initializePass() {
52 TD = &getAnalysis<TargetData>();
55 virtual AliasResult alias(const Value *V1, unsigned V1Size,
56 const Value *V2, unsigned V2Size) {
60 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
61 std::vector<PointerAccessInfo> *Info) {
62 return UnknownModRefBehavior;
65 virtual void getArgumentAccesses(Function *F, CallSite CS,
66 std::vector<PointerAccessInfo> &Info) {
67 assert(0 && "This method may not be called on this function!");
70 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
71 virtual bool pointsToConstantMemory(const Value *P) { return false; }
72 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
75 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
78 virtual bool hasNoModRefInfoForCalls() const { return true; }
80 virtual void deleteValue(Value *V) {}
81 virtual void copyValue(Value *From, Value *To) {}
84 // Register this pass...
87 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
89 // Declare that we implement the AliasAnalysis interface
90 RegisterAnalysisGroup<AliasAnalysis> V(U);
91 } // End of anonymous namespace
93 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
96 /// BasicAliasAnalysis - This is the default alias analysis implementation.
97 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
98 /// derives from the NoAA class.
99 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
100 static char ID; // Class identification, replacement for typeinfo
101 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { }
102 AliasResult alias(const Value *V1, unsigned V1Size,
103 const Value *V2, unsigned V2Size);
105 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
106 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
107 return NoAA::getModRefInfo(CS1,CS2);
110 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
111 /// non-escaping allocations.
112 virtual bool hasNoModRefInfoForCalls() const { return false; }
114 /// pointsToConstantMemory - Chase pointers until we find a (constant
116 bool pointsToConstantMemory(const Value *P);
118 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
119 std::vector<PointerAccessInfo> *Info);
122 // CheckGEPInstructions - Check two GEP instructions with known
123 // must-aliasing base pointers. This checks to see if the index expressions
124 // preclude the pointers from aliasing...
126 CheckGEPInstructions(const Type* BasePtr1Ty,
127 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
128 const Type *BasePtr2Ty,
129 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
132 // Register this pass...
133 char BasicAliasAnalysis::ID = 0;
134 RegisterPass<BasicAliasAnalysis>
135 X("basicaa", "Basic Alias Analysis (default AA impl)");
137 // Declare that we implement the AliasAnalysis interface
138 RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
139 } // End of anonymous namespace
141 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
142 return new BasicAliasAnalysis();
145 // getUnderlyingObject - This traverses the use chain to figure out what object
146 // the specified value points to. If the value points to, or is derived from, a
147 // unique object or an argument, return it.
148 static const Value *getUnderlyingObject(const Value *V) {
149 if (!isa<PointerType>(V->getType())) return 0;
151 // If we are at some type of object, return it. GlobalValues and Allocations
152 // have unique addresses.
153 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V))
156 // Traverse through different addressing mechanisms...
157 if (const Instruction *I = dyn_cast<Instruction>(V)) {
158 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
159 return getUnderlyingObject(I->getOperand(0));
160 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
161 if (CE->getOpcode() == Instruction::BitCast ||
162 CE->getOpcode() == Instruction::GetElementPtr)
163 return getUnderlyingObject(CE->getOperand(0));
168 static const User *isGEP(const Value *V) {
169 if (isa<GetElementPtrInst>(V) ||
170 (isa<ConstantExpr>(V) &&
171 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
172 return cast<User>(V);
176 static const Value *GetGEPOperands(const Value *V,
177 SmallVector<Value*, 16> &GEPOps){
178 assert(GEPOps.empty() && "Expect empty list to populate!");
179 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
180 cast<User>(V)->op_end());
182 // Accumulate all of the chained indexes into the operand array
183 V = cast<User>(V)->getOperand(0);
185 while (const User *G = isGEP(V)) {
186 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
187 !cast<Constant>(GEPOps[0])->isNullValue())
188 break; // Don't handle folding arbitrary pointer offsets yet...
189 GEPOps.erase(GEPOps.begin()); // Drop the zero index
190 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
191 V = G->getOperand(0);
196 /// pointsToConstantMemory - Chase pointers until we find a (constant
198 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
199 if (const Value *V = getUnderlyingObject(P))
200 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
201 return GV->isConstant();
205 // Determine if an AllocationInst instruction escapes from the function it is
206 // contained in. If it does not escape, there is no way for another function to
207 // mod/ref it. We do this by looking at its uses and determining if the uses
208 // can escape (recursively).
209 static bool AddressMightEscape(const Value *V) {
210 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
212 const Instruction *I = cast<Instruction>(*UI);
213 switch (I->getOpcode()) {
214 case Instruction::Load:
216 case Instruction::Store:
217 if (I->getOperand(0) == V)
218 return true; // Escapes if the pointer is stored.
220 case Instruction::GetElementPtr:
221 if (AddressMightEscape(I))
223 case Instruction::BitCast:
224 if (!isa<PointerType>(I->getType()))
226 if (AddressMightEscape(I))
229 case Instruction::Ret:
230 // If returned, the address will escape to calling functions, but no
231 // callees could modify it.
240 // getModRefInfo - Check to see if the specified callsite can clobber the
241 // specified memory object. Since we only look at local properties of this
242 // function, we really can't say much about this query. We do, however, use
243 // simple "address taken" analysis on local objects.
245 AliasAnalysis::ModRefResult
246 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
247 if (!isa<Constant>(P))
248 if (const AllocationInst *AI =
249 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
250 // Okay, the pointer is to a stack allocated object. If we can prove that
251 // the pointer never "escapes", then we know the call cannot clobber it,
252 // because it simply can't get its address.
253 if (!AddressMightEscape(AI))
256 // If this is a tail call and P points to a stack location, we know that
257 // the tail call cannot access or modify the local stack.
258 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
259 if (CI->isTailCall() && isa<AllocaInst>(AI))
263 // The AliasAnalysis base class has some smarts, lets use them.
264 return AliasAnalysis::getModRefInfo(CS, P, Size);
267 static bool isNoAliasArgument(const Argument *Arg) {
268 const Function *Func = Arg->getParent();
269 const ParamAttrsList *Attr = Func->getFunctionType()->getParamAttrs();
272 for (Function::const_arg_iterator I = Func->arg_begin(),
273 E = Func->arg_end(); I != E; ++I, ++Idx) {
275 Attr->paramHasAttr(Idx, ParamAttr::NoAlias))
282 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
283 // as array references. Note that this function is heavily tail recursive.
284 // Hopefully we have a smart C++ compiler. :)
286 AliasAnalysis::AliasResult
287 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
288 const Value *V2, unsigned V2Size) {
289 // Strip off any constant expression casts if they exist
290 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
291 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
292 V1 = CE->getOperand(0);
293 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
294 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
295 V2 = CE->getOperand(0);
297 // Are we checking for alias of the same value?
298 if (V1 == V2) return MustAlias;
300 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
301 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty)
302 return NoAlias; // Scalars cannot alias each other
304 // Strip off cast instructions...
305 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
306 return alias(I->getOperand(0), V1Size, V2, V2Size);
307 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
308 return alias(V1, V1Size, I->getOperand(0), V2Size);
310 // Figure out what objects these things are pointing to if we can...
311 const Value *O1 = getUnderlyingObject(V1);
312 const Value *O2 = getUnderlyingObject(V2);
314 // Pointing at a discernible object?
317 if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
318 // Incoming argument cannot alias locally allocated object!
319 if (isa<AllocationInst>(O2)) return NoAlias;
321 // If they are two different objects, and one is a noalias argument
322 // then they do not alias.
323 if (O1 != O2 && isNoAliasArgument(O1Arg))
326 // Otherwise, nothing is known...
329 if (const Argument *O2Arg = dyn_cast<Argument>(O2)) {
330 // Incoming argument cannot alias locally allocated object!
331 if (isa<AllocationInst>(O1)) return NoAlias;
333 // If they are two different objects, and one is a noalias argument
334 // then they do not alias.
335 if (O1 != O2 && isNoAliasArgument(O2Arg))
338 // Otherwise, nothing is known...
339 } else if (O1 != O2) {
340 // If they are two different objects, we know that we have no alias...
344 // If they are the same object, they we can look at the indexes. If they
345 // index off of the object is the same for both pointers, they must alias.
346 // If they are provably different, they must not alias. Otherwise, we
347 // can't tell anything.
351 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
352 return NoAlias; // Unique values don't alias null
354 if (isa<GlobalVariable>(O1) ||
355 (isa<AllocationInst>(O1) &&
356 !cast<AllocationInst>(O1)->isArrayAllocation()))
357 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
358 // If the size of the other access is larger than the total size of the
359 // global/alloca/malloc, it cannot be accessing the global (it's
360 // undefined to load or store bytes before or after an object).
361 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
362 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
363 if (GlobalSize < V2Size && V2Size != ~0U)
369 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
370 return NoAlias; // Unique values don't alias null
372 if (isa<GlobalVariable>(O2) ||
373 (isa<AllocationInst>(O2) &&
374 !cast<AllocationInst>(O2)->isArrayAllocation()))
375 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
376 // If the size of the other access is larger than the total size of the
377 // global/alloca/malloc, it cannot be accessing the object (it's
378 // undefined to load or store bytes before or after an object).
379 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
380 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
381 if (GlobalSize < V1Size && V1Size != ~0U)
386 // If we have two gep instructions with must-alias'ing base pointers, figure
387 // out if the indexes to the GEP tell us anything about the derived pointer.
388 // Note that we also handle chains of getelementptr instructions as well as
389 // constant expression getelementptrs here.
391 if (isGEP(V1) && isGEP(V2)) {
392 // Drill down into the first non-gep value, to test for must-aliasing of
393 // the base pointers.
394 const Value *BasePtr1 = V1, *BasePtr2 = V2;
396 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
397 } while (isGEP(BasePtr1) &&
398 cast<User>(BasePtr1)->getOperand(1) ==
399 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
401 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
402 } while (isGEP(BasePtr2) &&
403 cast<User>(BasePtr2)->getOperand(1) ==
404 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
406 // Do the base pointers alias?
407 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
408 if (BaseAlias == NoAlias) return NoAlias;
409 if (BaseAlias == MustAlias) {
410 // If the base pointers alias each other exactly, check to see if we can
411 // figure out anything about the resultant pointers, to try to prove
414 // Collect all of the chained GEP operands together into one simple place
415 SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
416 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
417 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
419 // If GetGEPOperands were able to fold to the same must-aliased pointer,
420 // do the comparison.
421 if (BasePtr1 == BasePtr2) {
423 CheckGEPInstructions(BasePtr1->getType(),
424 &GEP1Ops[0], GEP1Ops.size(), V1Size,
426 &GEP2Ops[0], GEP2Ops.size(), V2Size);
427 if (GAlias != MayAlias)
433 // Check to see if these two pointers are related by a getelementptr
434 // instruction. If one pointer is a GEP with a non-zero index of the other
435 // pointer, we know they cannot alias.
439 std::swap(V1Size, V2Size);
442 if (V1Size != ~0U && V2Size != ~0U)
444 SmallVector<Value*, 16> GEPOperands;
445 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
447 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
448 if (R == MustAlias) {
449 // If there is at least one non-zero constant index, we know they cannot
451 bool ConstantFound = false;
452 bool AllZerosFound = true;
453 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
454 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
455 if (!C->isNullValue()) {
456 ConstantFound = true;
457 AllZerosFound = false;
461 AllZerosFound = false;
464 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
465 // the ptr, the end result is a must alias also.
470 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
473 // Otherwise we have to check to see that the distance is more than
474 // the size of the argument... build an index vector that is equal to
475 // the arguments provided, except substitute 0's for any variable
476 // indexes we find...
477 if (cast<PointerType>(
478 BasePtr->getType())->getElementType()->isSized()) {
479 for (unsigned i = 0; i != GEPOperands.size(); ++i)
480 if (!isa<ConstantInt>(GEPOperands[i]))
482 Constant::getNullValue(GEPOperands[i]->getType());
484 getTargetData().getIndexedOffset(BasePtr->getType(),
488 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
498 // This function is used to determin if the indices of two GEP instructions are
499 // equal. V1 and V2 are the indices.
500 static bool IndexOperandsEqual(Value *V1, Value *V2) {
501 if (V1->getType() == V2->getType())
503 if (Constant *C1 = dyn_cast<Constant>(V1))
504 if (Constant *C2 = dyn_cast<Constant>(V2)) {
505 // Sign extend the constants to long types, if necessary
506 if (C1->getType() != Type::Int64Ty)
507 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
508 if (C2->getType() != Type::Int64Ty)
509 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
515 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
516 /// base pointers. This checks to see if the index expressions preclude the
517 /// pointers from aliasing...
518 AliasAnalysis::AliasResult
519 BasicAliasAnalysis::CheckGEPInstructions(
520 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
521 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
522 // We currently can't handle the case when the base pointers have different
523 // primitive types. Since this is uncommon anyway, we are happy being
524 // extremely conservative.
525 if (BasePtr1Ty != BasePtr2Ty)
528 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
530 // Find the (possibly empty) initial sequence of equal values... which are not
531 // necessarily constants.
532 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
533 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
534 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
535 unsigned UnequalOper = 0;
536 while (UnequalOper != MinOperands &&
537 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
538 // Advance through the type as we go...
540 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
541 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
543 // If all operands equal each other, then the derived pointers must
544 // alias each other...
546 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
547 "Ran out of type nesting, but not out of operands?");
552 // If we have seen all constant operands, and run out of indexes on one of the
553 // getelementptrs, check to see if the tail of the leftover one is all zeros.
554 // If so, return mustalias.
555 if (UnequalOper == MinOperands) {
556 if (NumGEP1Ops < NumGEP2Ops) {
557 std::swap(GEP1Ops, GEP2Ops);
558 std::swap(NumGEP1Ops, NumGEP2Ops);
561 bool AllAreZeros = true;
562 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
563 if (!isa<Constant>(GEP1Ops[i]) ||
564 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
568 if (AllAreZeros) return MustAlias;
572 // So now we know that the indexes derived from the base pointers,
573 // which are known to alias, are different. We can still determine a
574 // no-alias result if there are differing constant pairs in the index
575 // chain. For example:
576 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
578 // We have to be careful here about array accesses. In particular, consider:
579 // A[1][0] vs A[0][i]
580 // In this case, we don't *know* that the array will be accessed in bounds:
581 // the index could even be negative. Because of this, we have to
582 // conservatively *give up* and return may alias. We disregard differing
583 // array subscripts that are followed by a variable index without going
586 unsigned SizeMax = std::max(G1S, G2S);
587 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
589 // Scan for the first operand that is constant and unequal in the
590 // two getelementptrs...
591 unsigned FirstConstantOper = UnequalOper;
592 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
593 const Value *G1Oper = GEP1Ops[FirstConstantOper];
594 const Value *G2Oper = GEP2Ops[FirstConstantOper];
596 if (G1Oper != G2Oper) // Found non-equal constant indexes...
597 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
598 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
599 if (G1OC->getType() != G2OC->getType()) {
600 // Sign extend both operands to long.
601 if (G1OC->getType() != Type::Int64Ty)
602 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
603 if (G2OC->getType() != Type::Int64Ty)
604 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
605 GEP1Ops[FirstConstantOper] = G1OC;
606 GEP2Ops[FirstConstantOper] = G2OC;
610 // Handle the "be careful" case above: if this is an array/vector
611 // subscript, scan for a subsequent variable array index.
612 if (isa<SequentialType>(BasePtr1Ty)) {
614 cast<SequentialType>(BasePtr1Ty)->getElementType();
615 bool isBadCase = false;
617 for (unsigned Idx = FirstConstantOper+1;
618 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
619 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
620 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
624 NextTy = cast<SequentialType>(NextTy)->getElementType();
627 if (isBadCase) G1OC = 0;
630 // Make sure they are comparable (ie, not constant expressions), and
631 // make sure the GEP with the smaller leading constant is GEP1.
633 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
635 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
636 if (CV->getZExtValue()) { // If they are comparable and G2 > G1
637 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
638 std::swap(NumGEP1Ops, NumGEP2Ops);
645 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
648 // No shared constant operands, and we ran out of common operands. At this
649 // point, the GEP instructions have run through all of their operands, and we
650 // haven't found evidence that there are any deltas between the GEP's.
651 // However, one GEP may have more operands than the other. If this is the
652 // case, there may still be hope. Check this now.
653 if (FirstConstantOper == MinOperands) {
654 // Make GEP1Ops be the longer one if there is a longer one.
655 if (NumGEP1Ops < NumGEP2Ops) {
656 std::swap(GEP1Ops, GEP2Ops);
657 std::swap(NumGEP1Ops, NumGEP2Ops);
660 // Is there anything to check?
661 if (NumGEP1Ops > MinOperands) {
662 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
663 if (isa<ConstantInt>(GEP1Ops[i]) &&
664 !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
665 // Yup, there's a constant in the tail. Set all variables to
666 // constants in the GEP instruction to make it suiteable for
667 // TargetData::getIndexedOffset.
668 for (i = 0; i != MaxOperands; ++i)
669 if (!isa<ConstantInt>(GEP1Ops[i]))
670 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
671 // Okay, now get the offset. This is the relative offset for the full
673 const TargetData &TD = getTargetData();
674 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
677 // Now check without any constants at the end.
678 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
681 // If the tail provided a bit enough offset, return noalias!
682 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
687 // Couldn't find anything useful.
691 // If there are non-equal constants arguments, then we can figure
692 // out a minimum known delta between the two index expressions... at
693 // this point we know that the first constant index of GEP1 is less
694 // than the first constant index of GEP2.
696 // Advance BasePtr[12]Ty over this first differing constant operand.
697 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
698 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
699 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
700 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
702 // We are going to be using TargetData::getIndexedOffset to determine the
703 // offset that each of the GEP's is reaching. To do this, we have to convert
704 // all variable references to constant references. To do this, we convert the
705 // initial sequence of array subscripts into constant zeros to start with.
706 const Type *ZeroIdxTy = GEPPointerTy;
707 for (unsigned i = 0; i != FirstConstantOper; ++i) {
708 if (!isa<StructType>(ZeroIdxTy))
709 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
711 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
712 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
715 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
717 // Loop over the rest of the operands...
718 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
719 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
720 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
721 // If they are equal, use a zero index...
722 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
723 if (!isa<ConstantInt>(Op1))
724 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
725 // Otherwise, just keep the constants we have.
728 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
729 // If this is an array index, make sure the array element is in range.
730 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
731 if (Op1C->getZExtValue() >= AT->getNumElements())
732 return MayAlias; // Be conservative with out-of-range accesses
733 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
734 if (Op1C->getZExtValue() >= PT->getNumElements())
735 return MayAlias; // Be conservative with out-of-range accesses
739 // GEP1 is known to produce a value less than GEP2. To be
740 // conservatively correct, we must assume the largest possible
741 // constant is used in this position. This cannot be the initial
742 // index to the GEP instructions (because we know we have at least one
743 // element before this one with the different constant arguments), so
744 // we know that the current index must be into either a struct or
745 // array. Because we know it's not constant, this cannot be a
746 // structure index. Because of this, we can calculate the maximum
749 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
750 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
751 else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
752 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
758 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
759 // If this is an array index, make sure the array element is in range.
760 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
761 if (Op2C->getZExtValue() >= AT->getNumElements())
762 return MayAlias; // Be conservative with out-of-range accesses
763 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
764 if (Op2C->getZExtValue() >= PT->getNumElements())
765 return MayAlias; // Be conservative with out-of-range accesses
767 } else { // Conservatively assume the minimum value for this index
768 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
773 if (BasePtr1Ty && Op1) {
774 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
775 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
780 if (BasePtr2Ty && Op2) {
781 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
782 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
788 if (GEPPointerTy->getElementType()->isSized()) {
790 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
792 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
793 assert(Offset1<Offset2 && "There is at least one different constant here!");
795 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
796 //cerr << "Determined that these two GEP's don't alias ["
797 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
805 struct VISIBILITY_HIDDEN StringCompare {
806 bool operator()(const char *LHS, const char *RHS) {
807 return strcmp(LHS, RHS) < 0;
812 // Note that this list cannot contain libm functions (such as acos and sqrt)
813 // that set errno on a domain or other error.
814 static const char *DoesntAccessMemoryFns[] = {
815 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
816 "trunc", "truncf", "truncl", "ldexp",
818 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
820 "cos", "cosf", "cosl",
821 "exp", "expf", "expl",
823 "sin", "sinf", "sinl",
824 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
826 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
829 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
830 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
833 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
834 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
836 "iswctype", "towctrans", "towlower", "towupper",
840 "isinf", "isnan", "finite",
842 // C99 math functions
843 "copysign", "copysignf", "copysignd",
844 "nexttoward", "nexttowardf", "nexttowardd",
845 "nextafter", "nextafterf", "nextafterd",
848 "__signbit", "__signbitf", "__signbitl",
852 static const char *OnlyReadsMemoryFns[] = {
853 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
854 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
857 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
858 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
862 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
863 "wcsrchr", "wcsspn", "wcsstr",
866 "alphasort", "alphasort64", "versionsort", "versionsort64",
869 "nan", "nanf", "nand",
872 "feof", "ferror", "fileno",
873 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
876 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
877 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
879 static ManagedStatic<BitVector> NoMemoryIntrinsics;
880 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
883 AliasAnalysis::ModRefBehavior
884 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
885 std::vector<PointerAccessInfo> *Info) {
886 if (!F->isDeclaration()) return UnknownModRefBehavior;
888 static bool Initialized = false;
890 NoMemoryTable->insert(NoMemoryTable->end(),
891 DoesntAccessMemoryFns,
892 DoesntAccessMemoryFns+
893 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0]));
895 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
898 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0]));
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)