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/GetElementPtrTypeIterator.h"
29 // Make sure that anything that uses AliasAnalysis pulls in this file...
30 void llvm::BasicAAStub() {}
33 /// NoAA - This class implements the -no-aa pass, which always returns "I
34 /// don't know" for alias queries. NoAA is unlike other alias analysis
35 /// implementations, in that it does not chain to a previous analysis. As
36 /// such it doesn't follow many of the rules that other alias analyses must.
38 struct NoAA : public ImmutablePass, public AliasAnalysis {
39 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
40 AU.addRequired<TargetData>();
43 virtual void initializePass() {
44 TD = &getAnalysis<TargetData>();
47 virtual AliasResult alias(const Value *V1, unsigned V1Size,
48 const Value *V2, unsigned V2Size) {
52 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
53 std::vector<PointerAccessInfo> *Info) {
54 return UnknownModRefBehavior;
57 virtual void getArgumentAccesses(Function *F, CallSite CS,
58 std::vector<PointerAccessInfo> &Info) {
59 assert(0 && "This method may not be called on this function!");
62 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
63 virtual bool pointsToConstantMemory(const Value *P) { return false; }
64 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
67 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
70 virtual bool hasNoModRefInfoForCalls() const { return true; }
72 virtual void deleteValue(Value *V) {}
73 virtual void copyValue(Value *From, Value *To) {}
76 // Register this pass...
78 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
80 // Declare that we implement the AliasAnalysis interface
81 RegisterAnalysisGroup<AliasAnalysis, NoAA> V;
82 } // End of anonymous namespace
84 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
87 /// BasicAliasAnalysis - This is the default alias analysis implementation.
88 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
89 /// derives from the NoAA class.
90 struct BasicAliasAnalysis : public NoAA {
91 AliasResult alias(const Value *V1, unsigned V1Size,
92 const Value *V2, unsigned V2Size);
94 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
95 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
96 return NoAA::getModRefInfo(CS1,CS2);
99 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
100 /// non-escaping allocations.
101 virtual bool hasNoModRefInfoForCalls() const { return false; }
103 /// pointsToConstantMemory - Chase pointers until we find a (constant
105 bool pointsToConstantMemory(const Value *P);
107 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
108 std::vector<PointerAccessInfo> *Info);
111 // CheckGEPInstructions - Check two GEP instructions with known
112 // must-aliasing base pointers. This checks to see if the index expressions
113 // preclude the pointers from aliasing...
115 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
117 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
121 // Register this pass...
122 RegisterOpt<BasicAliasAnalysis>
123 X("basicaa", "Basic Alias Analysis (default AA impl)");
125 // Declare that we implement the AliasAnalysis interface
126 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
127 } // End of anonymous namespace
129 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
130 return new BasicAliasAnalysis();
133 // hasUniqueAddress - Return true if the specified value points to something
134 // with a unique, discernable, address.
135 static inline bool hasUniqueAddress(const Value *V) {
136 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
139 // getUnderlyingObject - This traverses the use chain to figure out what object
140 // the specified value points to. If the value points to, or is derived from, a
141 // unique object or an argument, return it.
142 static const Value *getUnderlyingObject(const Value *V) {
143 if (!isa<PointerType>(V->getType())) return 0;
145 // If we are at some type of object... return it.
146 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
148 // Traverse through different addressing mechanisms...
149 if (const Instruction *I = dyn_cast<Instruction>(V)) {
150 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
151 return getUnderlyingObject(I->getOperand(0));
152 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
153 if (CE->getOpcode() == Instruction::Cast ||
154 CE->getOpcode() == Instruction::GetElementPtr)
155 return getUnderlyingObject(CE->getOperand(0));
156 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
162 static const User *isGEP(const Value *V) {
163 if (isa<GetElementPtrInst>(V) ||
164 (isa<ConstantExpr>(V) &&
165 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
166 return cast<User>(V);
170 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
171 assert(GEPOps.empty() && "Expect empty list to populate!");
172 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
173 cast<User>(V)->op_end());
175 // Accumulate all of the chained indexes into the operand array
176 V = cast<User>(V)->getOperand(0);
178 while (const User *G = isGEP(V)) {
179 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
180 !cast<Constant>(GEPOps[0])->isNullValue())
181 break; // Don't handle folding arbitrary pointer offsets yet...
182 GEPOps.erase(GEPOps.begin()); // Drop the zero index
183 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
184 V = G->getOperand(0);
189 /// pointsToConstantMemory - Chase pointers until we find a (constant
191 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
192 if (const Value *V = getUnderlyingObject(P))
193 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
194 return GV->isConstant();
198 static bool AddressMightEscape(const Value *V) {
199 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
201 const Instruction *I = cast<Instruction>(*UI);
202 switch (I->getOpcode()) {
203 case Instruction::Load: break;
204 case Instruction::Store:
205 if (I->getOperand(0) == V)
206 return true; // Escapes if the pointer is stored.
208 case Instruction::GetElementPtr:
209 if (AddressMightEscape(I)) return true;
211 case Instruction::Cast:
212 if (!isa<PointerType>(I->getType()))
214 if (AddressMightEscape(I)) return true;
216 case Instruction::Ret:
217 // If returned, the address will escape to calling functions, but no
218 // callees could modify it.
227 // getModRefInfo - Check to see if the specified callsite can clobber the
228 // specified memory object. Since we only look at local properties of this
229 // function, we really can't say much about this query. We do, however, use
230 // simple "address taken" analysis on local objects.
232 AliasAnalysis::ModRefResult
233 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
234 if (!isa<Constant>(P))
235 if (const AllocationInst *AI =
236 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
237 // Okay, the pointer is to a stack allocated object. If we can prove that
238 // the pointer never "escapes", then we know the call cannot clobber it,
239 // because it simply can't get its address.
240 if (!AddressMightEscape(AI))
243 // If this is a tail call and P points to a stack location, we know that
244 // the tail call cannot access or modify the local stack.
245 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
246 if (CI->isTailCall() && isa<AllocaInst>(AI))
250 // The AliasAnalysis base class has some smarts, lets use them.
251 return AliasAnalysis::getModRefInfo(CS, P, Size);
254 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
255 // as array references. Note that this function is heavily tail recursive.
256 // Hopefully we have a smart C++ compiler. :)
258 AliasAnalysis::AliasResult
259 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
260 const Value *V2, unsigned V2Size) {
261 // Strip off any constant expression casts if they exist
262 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
263 if (CE->getOpcode() == Instruction::Cast &&
264 isa<PointerType>(CE->getOperand(0)->getType()))
265 V1 = CE->getOperand(0);
266 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
267 if (CE->getOpcode() == Instruction::Cast &&
268 isa<PointerType>(CE->getOperand(0)->getType()))
269 V2 = CE->getOperand(0);
271 // Are we checking for alias of the same value?
272 if (V1 == V2) return MustAlias;
274 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
275 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
276 return NoAlias; // Scalars cannot alias each other
278 // Strip off cast instructions...
279 if (const Instruction *I = dyn_cast<CastInst>(V1))
280 if (isa<PointerType>(I->getOperand(0)->getType()))
281 return alias(I->getOperand(0), V1Size, V2, V2Size);
282 if (const Instruction *I = dyn_cast<CastInst>(V2))
283 if (isa<PointerType>(I->getOperand(0)->getType()))
284 return alias(V1, V1Size, I->getOperand(0), V2Size);
286 // Figure out what objects these things are pointing to if we can...
287 const Value *O1 = getUnderlyingObject(V1);
288 const Value *O2 = getUnderlyingObject(V2);
290 // Pointing at a discernible object?
293 if (isa<Argument>(O1)) {
294 // Incoming argument cannot alias locally allocated object!
295 if (isa<AllocationInst>(O2)) return NoAlias;
296 // Otherwise, nothing is known...
297 } else if (isa<Argument>(O2)) {
298 // Incoming argument cannot alias locally allocated object!
299 if (isa<AllocationInst>(O1)) return NoAlias;
300 // Otherwise, nothing is known...
301 } else if (O1 != O2) {
302 // If they are two different objects, we know that we have no alias...
306 // If they are the same object, they we can look at the indexes. If they
307 // index off of the object is the same for both pointers, they must alias.
308 // If they are provably different, they must not alias. Otherwise, we
309 // can't tell anything.
313 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
314 return NoAlias; // Unique values don't alias null
316 if (isa<GlobalVariable>(O1) ||
317 (isa<AllocationInst>(O1) &&
318 !cast<AllocationInst>(O1)->isArrayAllocation()))
319 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
320 // If the size of the other access is larger than the total size of the
321 // global/alloca/malloc, it cannot be accessing the global (it's
322 // undefined to load or store bytes before or after an object).
323 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
324 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
325 if (GlobalSize < V2Size && V2Size != ~0U)
331 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
332 return NoAlias; // Unique values don't alias null
334 if (isa<GlobalVariable>(O2) ||
335 (isa<AllocationInst>(O2) &&
336 !cast<AllocationInst>(O2)->isArrayAllocation()))
337 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
338 // If the size of the other access is larger than the total size of the
339 // global/alloca/malloc, it cannot be accessing the object (it's
340 // undefined to load or store bytes before or after an object).
341 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
342 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
343 if (GlobalSize < V1Size && V1Size != ~0U)
348 // If we have two gep instructions with must-alias'ing base pointers, figure
349 // out if the indexes to the GEP tell us anything about the derived pointer.
350 // Note that we also handle chains of getelementptr instructions as well as
351 // constant expression getelementptrs here.
353 if (isGEP(V1) && isGEP(V2)) {
354 // Drill down into the first non-gep value, to test for must-aliasing of
355 // the base pointers.
356 const Value *BasePtr1 = V1, *BasePtr2 = V2;
358 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
359 } while (isGEP(BasePtr1) &&
360 cast<User>(BasePtr1)->getOperand(1) ==
361 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
363 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
364 } while (isGEP(BasePtr2) &&
365 cast<User>(BasePtr2)->getOperand(1) ==
366 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
368 // Do the base pointers alias?
369 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
370 if (BaseAlias == NoAlias) return NoAlias;
371 if (BaseAlias == MustAlias) {
372 // If the base pointers alias each other exactly, check to see if we can
373 // figure out anything about the resultant pointers, to try to prove
376 // Collect all of the chained GEP operands together into one simple place
377 std::vector<Value*> GEP1Ops, GEP2Ops;
378 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
379 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
381 // If GetGEPOperands were able to fold to the same must-aliased pointer,
382 // do the comparison.
383 if (BasePtr1 == BasePtr2) {
385 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
386 BasePtr2->getType(), GEP2Ops, V2Size);
387 if (GAlias != MayAlias)
393 // Check to see if these two pointers are related by a getelementptr
394 // instruction. If one pointer is a GEP with a non-zero index of the other
395 // pointer, we know they cannot alias.
399 std::swap(V1Size, V2Size);
402 if (V1Size != ~0U && V2Size != ~0U)
403 if (const User *GEP = isGEP(V1)) {
404 std::vector<Value*> GEPOperands;
405 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
407 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
408 if (R == MustAlias) {
409 // If there is at least one non-zero constant index, we know they cannot
411 bool ConstantFound = false;
412 bool AllZerosFound = true;
413 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
414 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
415 if (!C->isNullValue()) {
416 ConstantFound = true;
417 AllZerosFound = false;
421 AllZerosFound = false;
424 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
425 // the ptr, the end result is a must alias also.
430 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
433 // Otherwise we have to check to see that the distance is more than
434 // the size of the argument... build an index vector that is equal to
435 // the arguments provided, except substitute 0's for any variable
436 // indexes we find...
437 if (cast<PointerType>(
438 BasePtr->getType())->getElementType()->isSized()) {
439 for (unsigned i = 0; i != GEPOperands.size(); ++i)
440 if (!isa<ConstantInt>(GEPOperands[i]))
442 Constant::getNullValue(GEPOperands[i]->getType());
444 getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands);
446 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
456 static bool ValuesEqual(Value *V1, Value *V2) {
457 if (V1->getType() == V2->getType())
459 if (Constant *C1 = dyn_cast<Constant>(V1))
460 if (Constant *C2 = dyn_cast<Constant>(V2)) {
461 // Sign extend the constants to long types.
462 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
463 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
469 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
470 /// base pointers. This checks to see if the index expressions preclude the
471 /// pointers from aliasing...
472 AliasAnalysis::AliasResult BasicAliasAnalysis::
473 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
475 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
477 // We currently can't handle the case when the base pointers have different
478 // primitive types. Since this is uncommon anyway, we are happy being
479 // extremely conservative.
480 if (BasePtr1Ty != BasePtr2Ty)
483 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
485 // Find the (possibly empty) initial sequence of equal values... which are not
486 // necessarily constants.
487 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
488 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
489 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
490 unsigned UnequalOper = 0;
491 while (UnequalOper != MinOperands &&
492 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
493 // Advance through the type as we go...
495 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
496 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
498 // If all operands equal each other, then the derived pointers must
499 // alias each other...
501 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
502 "Ran out of type nesting, but not out of operands?");
507 // If we have seen all constant operands, and run out of indexes on one of the
508 // getelementptrs, check to see if the tail of the leftover one is all zeros.
509 // If so, return mustalias.
510 if (UnequalOper == MinOperands) {
511 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
513 bool AllAreZeros = true;
514 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
515 if (!isa<Constant>(GEP1Ops[i]) ||
516 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
520 if (AllAreZeros) return MustAlias;
524 // So now we know that the indexes derived from the base pointers,
525 // which are known to alias, are different. We can still determine a
526 // no-alias result if there are differing constant pairs in the index
527 // chain. For example:
528 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
530 // We have to be careful here about array accesses. In particular, consider:
531 // A[1][0] vs A[0][i]
532 // In this case, we don't *know* that the array will be accessed in bounds:
533 // the index could even be negative. Because of this, we have to
534 // conservatively *give up* and return may alias. We disregard differing
535 // array subscripts that are followed by a variable index without going
538 unsigned SizeMax = std::max(G1S, G2S);
539 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
541 // Scan for the first operand that is constant and unequal in the
542 // two getelementptrs...
543 unsigned FirstConstantOper = UnequalOper;
544 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
545 const Value *G1Oper = GEP1Ops[FirstConstantOper];
546 const Value *G2Oper = GEP2Ops[FirstConstantOper];
548 if (G1Oper != G2Oper) // Found non-equal constant indexes...
549 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
550 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
551 if (G1OC->getType() != G2OC->getType()) {
552 // Sign extend both operands to long.
553 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
554 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
555 GEP1Ops[FirstConstantOper] = G1OC;
556 GEP2Ops[FirstConstantOper] = G2OC;
560 // Handle the "be careful" case above: if this is an array
561 // subscript, scan for a subsequent variable array index.
562 if (isa<ArrayType>(BasePtr1Ty)) {
563 const Type *NextTy =cast<ArrayType>(BasePtr1Ty)->getElementType();
564 bool isBadCase = false;
566 for (unsigned Idx = FirstConstantOper+1;
567 Idx != MinOperands && isa<ArrayType>(NextTy); ++Idx) {
568 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
569 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
573 NextTy = cast<ArrayType>(NextTy)->getElementType();
576 if (isBadCase) G1OC = 0;
579 // Make sure they are comparable (ie, not constant expressions), and
580 // make sure the GEP with the smaller leading constant is GEP1.
582 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
583 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
584 if (CV->getValue()) // If they are comparable and G2 > G1
585 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
591 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
594 // No shared constant operands, and we ran out of common operands. At this
595 // point, the GEP instructions have run through all of their operands, and we
596 // haven't found evidence that there are any deltas between the GEP's.
597 // However, one GEP may have more operands than the other. If this is the
598 // case, there may still be hope. Check this now.
599 if (FirstConstantOper == MinOperands) {
600 // Make GEP1Ops be the longer one if there is a longer one.
601 if (GEP1Ops.size() < GEP2Ops.size())
602 std::swap(GEP1Ops, GEP2Ops);
604 // Is there anything to check?
605 if (GEP1Ops.size() > MinOperands) {
606 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
607 if (isa<ConstantInt>(GEP1Ops[i]) &&
608 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
609 // Yup, there's a constant in the tail. Set all variables to
610 // constants in the GEP instruction to make it suiteable for
611 // TargetData::getIndexedOffset.
612 for (i = 0; i != MaxOperands; ++i)
613 if (!isa<ConstantInt>(GEP1Ops[i]))
614 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
615 // Okay, now get the offset. This is the relative offset for the full
617 const TargetData &TD = getTargetData();
618 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
620 // Now crop off any constants from the end...
621 GEP1Ops.resize(MinOperands);
622 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
624 // If the tail provided a bit enough offset, return noalias!
625 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
630 // Couldn't find anything useful.
634 // If there are non-equal constants arguments, then we can figure
635 // out a minimum known delta between the two index expressions... at
636 // this point we know that the first constant index of GEP1 is less
637 // than the first constant index of GEP2.
639 // Advance BasePtr[12]Ty over this first differing constant operand.
640 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
641 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
642 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
643 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
645 // We are going to be using TargetData::getIndexedOffset to determine the
646 // offset that each of the GEP's is reaching. To do this, we have to convert
647 // all variable references to constant references. To do this, we convert the
648 // initial sequence of array subscripts into constant zeros to start with.
649 const Type *ZeroIdxTy = GEPPointerTy;
650 for (unsigned i = 0; i != FirstConstantOper; ++i) {
651 if (!isa<StructType>(ZeroIdxTy))
652 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
654 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
655 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
658 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
660 // Loop over the rest of the operands...
661 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
662 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
663 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
664 // If they are equal, use a zero index...
665 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
666 if (!isa<ConstantInt>(Op1))
667 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
668 // Otherwise, just keep the constants we have.
671 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
672 // If this is an array index, make sure the array element is in range.
673 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
674 if (Op1C->getRawValue() >= AT->getNumElements())
675 return MayAlias; // Be conservative with out-of-range accesses
678 // GEP1 is known to produce a value less than GEP2. To be
679 // conservatively correct, we must assume the largest possible
680 // constant is used in this position. This cannot be the initial
681 // index to the GEP instructions (because we know we have at least one
682 // element before this one with the different constant arguments), so
683 // we know that the current index must be into either a struct or
684 // array. Because we know it's not constant, this cannot be a
685 // structure index. Because of this, we can calculate the maximum
688 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
689 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
694 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
695 // If this is an array index, make sure the array element is in range.
696 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
697 if (Op2C->getRawValue() >= AT->getNumElements())
698 return MayAlias; // Be conservative with out-of-range accesses
699 } else { // Conservatively assume the minimum value for this index
700 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
705 if (BasePtr1Ty && Op1) {
706 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
707 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
712 if (BasePtr2Ty && Op2) {
713 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
714 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
720 if (GEPPointerTy->getElementType()->isSized()) {
721 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
722 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
723 assert(Offset1<Offset2 && "There is at least one different constant here!");
725 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
726 //std::cerr << "Determined that these two GEP's don't alias ["
727 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
735 struct StringCompare {
736 bool operator()(const char *LHS, const char *RHS) {
737 return strcmp(LHS, RHS) < 0;
742 // Note that this list cannot contain libm functions (such as acos and sqrt)
743 // that set errno on a domain or other error.
744 static const char *DoesntAccessMemoryFns[] = {
745 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
746 "trunc", "truncf", "truncl", "ldexp",
748 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
750 "cos", "cosf", "cosl",
751 "exp", "expf", "expl",
753 "sin", "sinf", "sinl",
754 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
756 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
759 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
760 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
763 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
764 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
766 "iswctype", "towctrans", "towlower", "towupper",
770 "isinf", "isnan", "finite",
772 // C99 math functions
773 "copysign", "copysignf", "copysignd",
774 "nexttoward", "nexttowardf", "nexttowardd",
775 "nextafter", "nextafterf", "nextafterd",
778 "__signbit", "__signbitf", "__signbitl",
782 static const char *OnlyReadsMemoryFns[] = {
783 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
784 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
787 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
788 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
792 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
793 "wcsrchr", "wcsspn", "wcsstr",
796 "alphasort", "alphasort64", "versionsort", "versionsort64",
799 "nan", "nanf", "nand",
802 "feof", "ferror", "fileno",
803 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
806 AliasAnalysis::ModRefBehavior
807 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
808 std::vector<PointerAccessInfo> *Info) {
809 if (!F->isExternal()) return UnknownModRefBehavior;
811 static std::vector<const char*> NoMemoryTable, OnlyReadsMemoryTable;
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;