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/GlobalVariable.h"
22 #include "llvm/Instructions.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Target/TargetData.h"
25 #include "llvm/Support/Compiler.h"
26 #include "llvm/Support/GetElementPtrTypeIterator.h"
27 #include "llvm/Support/ManagedStatic.h"
32 /// NoAA - This class implements the -no-aa pass, which always returns "I
33 /// don't know" for alias queries. NoAA is unlike other alias analysis
34 /// implementations, in that it does not chain to a previous analysis. As
35 /// such it doesn't follow many of the rules that other alias analyses must.
37 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
38 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
39 AU.addRequired<TargetData>();
42 virtual void initializePass() {
43 TD = &getAnalysis<TargetData>();
46 virtual AliasResult alias(const Value *V1, unsigned V1Size,
47 const Value *V2, unsigned V2Size) {
51 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
52 std::vector<PointerAccessInfo> *Info) {
53 return UnknownModRefBehavior;
56 virtual void getArgumentAccesses(Function *F, CallSite CS,
57 std::vector<PointerAccessInfo> &Info) {
58 assert(0 && "This method may not be called on this function!");
61 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
62 virtual bool pointsToConstantMemory(const Value *P) { return false; }
63 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
66 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
69 virtual bool hasNoModRefInfoForCalls() const { return true; }
71 virtual void deleteValue(Value *V) {}
72 virtual void copyValue(Value *From, Value *To) {}
75 // Register this pass...
77 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
79 // Declare that we implement the AliasAnalysis interface
80 RegisterAnalysisGroup<AliasAnalysis> V(U);
81 } // End of anonymous namespace
83 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
86 /// BasicAliasAnalysis - This is the default alias analysis implementation.
87 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
88 /// derives from the NoAA class.
89 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
90 AliasResult alias(const Value *V1, unsigned V1Size,
91 const Value *V2, unsigned V2Size);
93 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
94 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
95 return NoAA::getModRefInfo(CS1,CS2);
98 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
99 /// non-escaping allocations.
100 virtual bool hasNoModRefInfoForCalls() const { return false; }
102 /// pointsToConstantMemory - Chase pointers until we find a (constant
104 bool pointsToConstantMemory(const Value *P);
106 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
107 std::vector<PointerAccessInfo> *Info);
110 // CheckGEPInstructions - Check two GEP instructions with known
111 // must-aliasing base pointers. This checks to see if the index expressions
112 // preclude the pointers from aliasing...
114 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
116 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
120 // Register this pass...
121 RegisterPass<BasicAliasAnalysis>
122 X("basicaa", "Basic Alias Analysis (default AA impl)");
124 // Declare that we implement the AliasAnalysis interface
125 RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
126 } // End of anonymous namespace
128 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
129 return new BasicAliasAnalysis();
132 // hasUniqueAddress - Return true if the specified value points to something
133 // with a unique, discernable, address.
134 static inline bool hasUniqueAddress(const Value *V) {
135 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
138 // getUnderlyingObject - This traverses the use chain to figure out what object
139 // the specified value points to. If the value points to, or is derived from, a
140 // unique object or an argument, return it.
141 static const Value *getUnderlyingObject(const Value *V) {
142 if (!isa<PointerType>(V->getType())) return 0;
144 // If we are at some type of object... return it.
145 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
147 // Traverse through different addressing mechanisms...
148 if (const Instruction *I = dyn_cast<Instruction>(V)) {
149 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
150 return getUnderlyingObject(I->getOperand(0));
151 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
152 if (CE->getOpcode() == Instruction::Cast ||
153 CE->getOpcode() == Instruction::GetElementPtr)
154 return getUnderlyingObject(CE->getOperand(0));
155 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
161 static const User *isGEP(const Value *V) {
162 if (isa<GetElementPtrInst>(V) ||
163 (isa<ConstantExpr>(V) &&
164 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
165 return cast<User>(V);
169 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
170 assert(GEPOps.empty() && "Expect empty list to populate!");
171 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
172 cast<User>(V)->op_end());
174 // Accumulate all of the chained indexes into the operand array
175 V = cast<User>(V)->getOperand(0);
177 while (const User *G = isGEP(V)) {
178 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
179 !cast<Constant>(GEPOps[0])->isNullValue())
180 break; // Don't handle folding arbitrary pointer offsets yet...
181 GEPOps.erase(GEPOps.begin()); // Drop the zero index
182 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
183 V = G->getOperand(0);
188 /// pointsToConstantMemory - Chase pointers until we find a (constant
190 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
191 if (const Value *V = getUnderlyingObject(P))
192 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
193 return GV->isConstant();
197 static bool AddressMightEscape(const Value *V) {
198 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
200 const Instruction *I = cast<Instruction>(*UI);
201 switch (I->getOpcode()) {
202 case Instruction::Load: break;
203 case Instruction::Store:
204 if (I->getOperand(0) == V)
205 return true; // Escapes if the pointer is stored.
207 case Instruction::GetElementPtr:
208 if (AddressMightEscape(I)) return true;
210 case Instruction::Cast:
211 if (!isa<PointerType>(I->getType()))
213 if (AddressMightEscape(I)) return true;
215 case Instruction::Ret:
216 // If returned, the address will escape to calling functions, but no
217 // callees could modify it.
226 // getModRefInfo - Check to see if the specified callsite can clobber the
227 // specified memory object. Since we only look at local properties of this
228 // function, we really can't say much about this query. We do, however, use
229 // simple "address taken" analysis on local objects.
231 AliasAnalysis::ModRefResult
232 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
233 if (!isa<Constant>(P))
234 if (const AllocationInst *AI =
235 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
236 // Okay, the pointer is to a stack allocated object. If we can prove that
237 // the pointer never "escapes", then we know the call cannot clobber it,
238 // because it simply can't get its address.
239 if (!AddressMightEscape(AI))
242 // If this is a tail call and P points to a stack location, we know that
243 // the tail call cannot access or modify the local stack.
244 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
245 if (CI->isTailCall() && isa<AllocaInst>(AI))
249 // The AliasAnalysis base class has some smarts, lets use them.
250 return AliasAnalysis::getModRefInfo(CS, P, Size);
253 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
254 // as array references. Note that this function is heavily tail recursive.
255 // Hopefully we have a smart C++ compiler. :)
257 AliasAnalysis::AliasResult
258 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
259 const Value *V2, unsigned V2Size) {
260 // Strip off any constant expression casts if they exist
261 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
262 if (CE->getOpcode() == Instruction::Cast &&
263 isa<PointerType>(CE->getOperand(0)->getType()))
264 V1 = CE->getOperand(0);
265 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
266 if (CE->getOpcode() == Instruction::Cast &&
267 isa<PointerType>(CE->getOperand(0)->getType()))
268 V2 = CE->getOperand(0);
270 // Are we checking for alias of the same value?
271 if (V1 == V2) return MustAlias;
273 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
274 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
275 return NoAlias; // Scalars cannot alias each other
277 // Strip off cast instructions...
278 if (const Instruction *I = dyn_cast<CastInst>(V1))
279 if (isa<PointerType>(I->getOperand(0)->getType()))
280 return alias(I->getOperand(0), V1Size, V2, V2Size);
281 if (const Instruction *I = dyn_cast<CastInst>(V2))
282 if (isa<PointerType>(I->getOperand(0)->getType()))
283 return alias(V1, V1Size, I->getOperand(0), V2Size);
285 // Figure out what objects these things are pointing to if we can...
286 const Value *O1 = getUnderlyingObject(V1);
287 const Value *O2 = getUnderlyingObject(V2);
289 // Pointing at a discernible object?
292 if (isa<Argument>(O1)) {
293 // Incoming argument cannot alias locally allocated object!
294 if (isa<AllocationInst>(O2)) return NoAlias;
295 // Otherwise, nothing is known...
296 } else if (isa<Argument>(O2)) {
297 // Incoming argument cannot alias locally allocated object!
298 if (isa<AllocationInst>(O1)) return NoAlias;
299 // Otherwise, nothing is known...
300 } else if (O1 != O2) {
301 // If they are two different objects, we know that we have no alias...
305 // If they are the same object, they we can look at the indexes. If they
306 // index off of the object is the same for both pointers, they must alias.
307 // If they are provably different, they must not alias. Otherwise, we
308 // can't tell anything.
312 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
313 return NoAlias; // Unique values don't alias null
315 if (isa<GlobalVariable>(O1) ||
316 (isa<AllocationInst>(O1) &&
317 !cast<AllocationInst>(O1)->isArrayAllocation()))
318 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
319 // If the size of the other access is larger than the total size of the
320 // global/alloca/malloc, it cannot be accessing the global (it's
321 // undefined to load or store bytes before or after an object).
322 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
323 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
324 if (GlobalSize < V2Size && V2Size != ~0U)
330 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
331 return NoAlias; // Unique values don't alias null
333 if (isa<GlobalVariable>(O2) ||
334 (isa<AllocationInst>(O2) &&
335 !cast<AllocationInst>(O2)->isArrayAllocation()))
336 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
337 // If the size of the other access is larger than the total size of the
338 // global/alloca/malloc, it cannot be accessing the object (it's
339 // undefined to load or store bytes before or after an object).
340 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
341 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
342 if (GlobalSize < V1Size && V1Size != ~0U)
347 // If we have two gep instructions with must-alias'ing base pointers, figure
348 // out if the indexes to the GEP tell us anything about the derived pointer.
349 // Note that we also handle chains of getelementptr instructions as well as
350 // constant expression getelementptrs here.
352 if (isGEP(V1) && isGEP(V2)) {
353 // Drill down into the first non-gep value, to test for must-aliasing of
354 // the base pointers.
355 const Value *BasePtr1 = V1, *BasePtr2 = V2;
357 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
358 } while (isGEP(BasePtr1) &&
359 cast<User>(BasePtr1)->getOperand(1) ==
360 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
362 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
363 } while (isGEP(BasePtr2) &&
364 cast<User>(BasePtr2)->getOperand(1) ==
365 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
367 // Do the base pointers alias?
368 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
369 if (BaseAlias == NoAlias) return NoAlias;
370 if (BaseAlias == MustAlias) {
371 // If the base pointers alias each other exactly, check to see if we can
372 // figure out anything about the resultant pointers, to try to prove
375 // Collect all of the chained GEP operands together into one simple place
376 std::vector<Value*> GEP1Ops, GEP2Ops;
377 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
378 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
380 // If GetGEPOperands were able to fold to the same must-aliased pointer,
381 // do the comparison.
382 if (BasePtr1 == BasePtr2) {
384 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
385 BasePtr2->getType(), GEP2Ops, V2Size);
386 if (GAlias != MayAlias)
392 // Check to see if these two pointers are related by a getelementptr
393 // instruction. If one pointer is a GEP with a non-zero index of the other
394 // pointer, we know they cannot alias.
398 std::swap(V1Size, V2Size);
401 if (V1Size != ~0U && V2Size != ~0U)
402 if (const User *GEP = isGEP(V1)) {
403 std::vector<Value*> GEPOperands;
404 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
406 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
407 if (R == MustAlias) {
408 // If there is at least one non-zero constant index, we know they cannot
410 bool ConstantFound = false;
411 bool AllZerosFound = true;
412 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
413 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
414 if (!C->isNullValue()) {
415 ConstantFound = true;
416 AllZerosFound = false;
420 AllZerosFound = false;
423 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
424 // the ptr, the end result is a must alias also.
429 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
432 // Otherwise we have to check to see that the distance is more than
433 // the size of the argument... build an index vector that is equal to
434 // the arguments provided, except substitute 0's for any variable
435 // indexes we find...
436 if (cast<PointerType>(
437 BasePtr->getType())->getElementType()->isSized()) {
438 for (unsigned i = 0; i != GEPOperands.size(); ++i)
439 if (!isa<ConstantInt>(GEPOperands[i]))
441 Constant::getNullValue(GEPOperands[i]->getType());
443 getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands);
445 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
455 static bool ValuesEqual(Value *V1, Value *V2) {
456 if (V1->getType() == V2->getType())
458 if (Constant *C1 = dyn_cast<Constant>(V1))
459 if (Constant *C2 = dyn_cast<Constant>(V2)) {
460 // Sign extend the constants to long types.
461 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
462 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
468 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
469 /// base pointers. This checks to see if the index expressions preclude the
470 /// pointers from aliasing...
471 AliasAnalysis::AliasResult
472 BasicAliasAnalysis::CheckGEPInstructions(
473 const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, unsigned G1S,
474 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, unsigned G2S) {
475 // We currently can't handle the case when the base pointers have different
476 // primitive types. Since this is uncommon anyway, we are happy being
477 // extremely conservative.
478 if (BasePtr1Ty != BasePtr2Ty)
481 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
483 // Find the (possibly empty) initial sequence of equal values... which are not
484 // necessarily constants.
485 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
486 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
487 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
488 unsigned UnequalOper = 0;
489 while (UnequalOper != MinOperands &&
490 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
491 // Advance through the type as we go...
493 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
494 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
496 // If all operands equal each other, then the derived pointers must
497 // alias each other...
499 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
500 "Ran out of type nesting, but not out of operands?");
505 // If we have seen all constant operands, and run out of indexes on one of the
506 // getelementptrs, check to see if the tail of the leftover one is all zeros.
507 // If so, return mustalias.
508 if (UnequalOper == MinOperands) {
509 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
511 bool AllAreZeros = true;
512 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
513 if (!isa<Constant>(GEP1Ops[i]) ||
514 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
518 if (AllAreZeros) return MustAlias;
522 // So now we know that the indexes derived from the base pointers,
523 // which are known to alias, are different. We can still determine a
524 // no-alias result if there are differing constant pairs in the index
525 // chain. For example:
526 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
528 // We have to be careful here about array accesses. In particular, consider:
529 // A[1][0] vs A[0][i]
530 // In this case, we don't *know* that the array will be accessed in bounds:
531 // the index could even be negative. Because of this, we have to
532 // conservatively *give up* and return may alias. We disregard differing
533 // array subscripts that are followed by a variable index without going
536 unsigned SizeMax = std::max(G1S, G2S);
537 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
539 // Scan for the first operand that is constant and unequal in the
540 // two getelementptrs...
541 unsigned FirstConstantOper = UnequalOper;
542 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
543 const Value *G1Oper = GEP1Ops[FirstConstantOper];
544 const Value *G2Oper = GEP2Ops[FirstConstantOper];
546 if (G1Oper != G2Oper) // Found non-equal constant indexes...
547 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
548 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
549 if (G1OC->getType() != G2OC->getType()) {
550 // Sign extend both operands to long.
551 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
552 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
553 GEP1Ops[FirstConstantOper] = G1OC;
554 GEP2Ops[FirstConstantOper] = G2OC;
558 // Handle the "be careful" case above: if this is an array
559 // subscript, scan for a subsequent variable array index.
560 if (isa<ArrayType>(BasePtr1Ty)) {
561 const Type *NextTy =cast<ArrayType>(BasePtr1Ty)->getElementType();
562 bool isBadCase = false;
564 for (unsigned Idx = FirstConstantOper+1;
565 Idx != MinOperands && isa<ArrayType>(NextTy); ++Idx) {
566 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
567 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
571 NextTy = cast<ArrayType>(NextTy)->getElementType();
574 if (isBadCase) G1OC = 0;
577 // Make sure they are comparable (ie, not constant expressions), and
578 // make sure the GEP with the smaller leading constant is GEP1.
580 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
581 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
582 if (CV->getValue()) // If they are comparable and G2 > G1
583 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
589 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
592 // No shared constant operands, and we ran out of common operands. At this
593 // point, the GEP instructions have run through all of their operands, and we
594 // haven't found evidence that there are any deltas between the GEP's.
595 // However, one GEP may have more operands than the other. If this is the
596 // case, there may still be hope. Check this now.
597 if (FirstConstantOper == MinOperands) {
598 // Make GEP1Ops be the longer one if there is a longer one.
599 if (GEP1Ops.size() < GEP2Ops.size())
600 std::swap(GEP1Ops, GEP2Ops);
602 // Is there anything to check?
603 if (GEP1Ops.size() > MinOperands) {
604 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
605 if (isa<ConstantInt>(GEP1Ops[i]) &&
606 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
607 // Yup, there's a constant in the tail. Set all variables to
608 // constants in the GEP instruction to make it suiteable for
609 // TargetData::getIndexedOffset.
610 for (i = 0; i != MaxOperands; ++i)
611 if (!isa<ConstantInt>(GEP1Ops[i]))
612 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
613 // Okay, now get the offset. This is the relative offset for the full
615 const TargetData &TD = getTargetData();
616 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
618 // Now crop off any constants from the end...
619 GEP1Ops.resize(MinOperands);
620 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
622 // If the tail provided a bit enough offset, return noalias!
623 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
628 // Couldn't find anything useful.
632 // If there are non-equal constants arguments, then we can figure
633 // out a minimum known delta between the two index expressions... at
634 // this point we know that the first constant index of GEP1 is less
635 // than the first constant index of GEP2.
637 // Advance BasePtr[12]Ty over this first differing constant operand.
638 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
639 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
640 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
641 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
643 // We are going to be using TargetData::getIndexedOffset to determine the
644 // offset that each of the GEP's is reaching. To do this, we have to convert
645 // all variable references to constant references. To do this, we convert the
646 // initial sequence of array subscripts into constant zeros to start with.
647 const Type *ZeroIdxTy = GEPPointerTy;
648 for (unsigned i = 0; i != FirstConstantOper; ++i) {
649 if (!isa<StructType>(ZeroIdxTy))
650 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
652 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
653 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
656 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
658 // Loop over the rest of the operands...
659 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
660 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
661 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
662 // If they are equal, use a zero index...
663 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
664 if (!isa<ConstantInt>(Op1))
665 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
666 // Otherwise, just keep the constants we have.
669 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
670 // If this is an array index, make sure the array element is in range.
671 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
672 if (Op1C->getZExtValue() >= AT->getNumElements())
673 return MayAlias; // Be conservative with out-of-range accesses
676 // GEP1 is known to produce a value less than GEP2. To be
677 // conservatively correct, we must assume the largest possible
678 // constant is used in this position. This cannot be the initial
679 // index to the GEP instructions (because we know we have at least one
680 // element before this one with the different constant arguments), so
681 // we know that the current index must be into either a struct or
682 // array. Because we know it's not constant, this cannot be a
683 // structure index. Because of this, we can calculate the maximum
686 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
687 GEP1Ops[i] = ConstantInt::get(Type::LongTy, AT->getNumElements()-1);
692 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
693 // If this is an array index, make sure the array element is in range.
694 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
695 if (Op2C->getZExtValue() >= AT->getNumElements())
696 return MayAlias; // Be conservative with out-of-range accesses
697 } else { // Conservatively assume the minimum value for this index
698 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
703 if (BasePtr1Ty && Op1) {
704 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
705 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
710 if (BasePtr2Ty && Op2) {
711 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
712 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
718 if (GEPPointerTy->getElementType()->isSized()) {
719 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
720 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
721 assert(Offset1<Offset2 && "There is at least one different constant here!");
723 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
724 //std::cerr << "Determined that these two GEP's don't alias ["
725 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
733 struct StringCompare {
734 bool operator()(const char *LHS, const char *RHS) {
735 return strcmp(LHS, RHS) < 0;
740 // Note that this list cannot contain libm functions (such as acos and sqrt)
741 // that set errno on a domain or other error.
742 static const char *DoesntAccessMemoryFns[] = {
743 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
744 "trunc", "truncf", "truncl", "ldexp",
746 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
748 "cos", "cosf", "cosl",
749 "exp", "expf", "expl",
751 "sin", "sinf", "sinl",
752 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
754 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
757 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
758 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
761 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
762 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
764 "iswctype", "towctrans", "towlower", "towupper",
768 "isinf", "isnan", "finite",
770 // C99 math functions
771 "copysign", "copysignf", "copysignd",
772 "nexttoward", "nexttowardf", "nexttowardd",
773 "nextafter", "nextafterf", "nextafterd",
776 "__signbit", "__signbitf", "__signbitl",
780 static const char *OnlyReadsMemoryFns[] = {
781 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
782 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
785 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
786 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
790 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
791 "wcsrchr", "wcsspn", "wcsstr",
794 "alphasort", "alphasort64", "versionsort", "versionsort64",
797 "nan", "nanf", "nand",
800 "feof", "ferror", "fileno",
801 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
804 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
805 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
808 AliasAnalysis::ModRefBehavior
809 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
810 std::vector<PointerAccessInfo> *Info) {
811 if (!F->isExternal()) return UnknownModRefBehavior;
813 static bool Initialized = false;
815 NoMemoryTable->insert(NoMemoryTable->end(),
816 DoesntAccessMemoryFns,
817 DoesntAccessMemoryFns+
818 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0]));
820 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
823 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0]));
824 #define GET_MODREF_BEHAVIOR
825 #include "llvm/Intrinsics.gen"
826 #undef GET_MODREF_BEHAVIOR
828 // Sort the table the first time through.
829 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
830 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
835 std::vector<const char*>::iterator Ptr =
836 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
837 F->getName().c_str(), StringCompare());
838 if (Ptr != NoMemoryTable->end() && *Ptr == F->getName())
839 return DoesNotAccessMemory;
841 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
842 OnlyReadsMemoryTable->end(),
843 F->getName().c_str(), StringCompare());
844 if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName())
845 return OnlyReadsMemory;
847 return UnknownModRefBehavior;
850 // Make sure that anything that uses AliasAnalysis pulls in this file...
851 DEFINING_FILE_FOR(BasicAliasAnalysis)