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/Pass.h"
25 #include "llvm/Target/TargetData.h"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/Support/GetElementPtrTypeIterator.h"
29 #include "llvm/Support/ManagedStatic.h"
34 /// NoAA - This class implements the -no-aa pass, which always returns "I
35 /// don't know" for alias queries. NoAA is unlike other alias analysis
36 /// implementations, in that it does not chain to a previous analysis. As
37 /// such it doesn't follow many of the rules that other alias analyses must.
39 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
40 static char ID; // Class identification, replacement for typeinfo
41 NoAA() : ImmutablePass((intptr_t)&ID) {}
42 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { }
44 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.addRequired<TargetData>();
48 virtual void initializePass() {
49 TD = &getAnalysis<TargetData>();
52 virtual AliasResult alias(const Value *V1, unsigned V1Size,
53 const Value *V2, unsigned V2Size) {
57 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
58 std::vector<PointerAccessInfo> *Info) {
59 return UnknownModRefBehavior;
62 virtual void getArgumentAccesses(Function *F, CallSite CS,
63 std::vector<PointerAccessInfo> &Info) {
64 assert(0 && "This method may not be called on this function!");
67 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
68 virtual bool pointsToConstantMemory(const Value *P) { return false; }
69 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
72 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
75 virtual bool hasNoModRefInfoForCalls() const { return true; }
77 virtual void deleteValue(Value *V) {}
78 virtual void copyValue(Value *From, Value *To) {}
81 // Register this pass...
84 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
86 // Declare that we implement the AliasAnalysis interface
87 RegisterAnalysisGroup<AliasAnalysis> V(U);
88 } // End of anonymous namespace
90 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
93 /// BasicAliasAnalysis - This is the default alias analysis implementation.
94 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
95 /// derives from the NoAA class.
96 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
97 static char ID; // Class identification, replacement for typeinfo
98 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { }
99 AliasResult alias(const Value *V1, unsigned V1Size,
100 const Value *V2, unsigned V2Size);
102 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
103 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
104 return NoAA::getModRefInfo(CS1,CS2);
107 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
108 /// non-escaping allocations.
109 virtual bool hasNoModRefInfoForCalls() const { return false; }
111 /// pointsToConstantMemory - Chase pointers until we find a (constant
113 bool pointsToConstantMemory(const Value *P);
115 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
116 std::vector<PointerAccessInfo> *Info);
119 // CheckGEPInstructions - Check two GEP instructions with known
120 // must-aliasing base pointers. This checks to see if the index expressions
121 // preclude the pointers from aliasing...
123 CheckGEPInstructions(const Type* BasePtr1Ty,
124 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
125 const Type *BasePtr2Ty,
126 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
129 // Register this pass...
130 char BasicAliasAnalysis::ID = 0;
131 RegisterPass<BasicAliasAnalysis>
132 X("basicaa", "Basic Alias Analysis (default AA impl)");
134 // Declare that we implement the AliasAnalysis interface
135 RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
136 } // End of anonymous namespace
138 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
139 return new BasicAliasAnalysis();
142 // getUnderlyingObject - This traverses the use chain to figure out what object
143 // the specified value points to. If the value points to, or is derived from, a
144 // unique object or an argument, return it.
145 static const Value *getUnderlyingObject(const Value *V) {
146 if (!isa<PointerType>(V->getType())) return 0;
148 // If we are at some type of object, return it. GlobalValues and Allocations
149 // have unique addresses.
150 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V))
153 // Traverse through different addressing mechanisms...
154 if (const Instruction *I = dyn_cast<Instruction>(V)) {
155 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
156 return getUnderlyingObject(I->getOperand(0));
157 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
158 if (CE->getOpcode() == Instruction::BitCast ||
159 CE->getOpcode() == Instruction::GetElementPtr)
160 return getUnderlyingObject(CE->getOperand(0));
165 static const User *isGEP(const Value *V) {
166 if (isa<GetElementPtrInst>(V) ||
167 (isa<ConstantExpr>(V) &&
168 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
169 return cast<User>(V);
173 static const Value *GetGEPOperands(const Value *V,
174 SmallVector<Value*, 16> &GEPOps){
175 assert(GEPOps.empty() && "Expect empty list to populate!");
176 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
177 cast<User>(V)->op_end());
179 // Accumulate all of the chained indexes into the operand array
180 V = cast<User>(V)->getOperand(0);
182 while (const User *G = isGEP(V)) {
183 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
184 !cast<Constant>(GEPOps[0])->isNullValue())
185 break; // Don't handle folding arbitrary pointer offsets yet...
186 GEPOps.erase(GEPOps.begin()); // Drop the zero index
187 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
188 V = G->getOperand(0);
193 /// pointsToConstantMemory - Chase pointers until we find a (constant
195 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
196 if (const Value *V = getUnderlyingObject(P))
197 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
198 return GV->isConstant();
202 // Determine if an AllocationInst instruction escapes from the function it is
203 // contained in. If it does not escape, there is no way for another function to
204 // mod/ref it. We do this by looking at its uses and determining if the uses
205 // can escape (recursively).
206 static bool AddressMightEscape(const Value *V) {
207 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
209 const Instruction *I = cast<Instruction>(*UI);
210 switch (I->getOpcode()) {
211 case Instruction::Load:
213 case Instruction::Store:
214 if (I->getOperand(0) == V)
215 return true; // Escapes if the pointer is stored.
217 case Instruction::GetElementPtr:
218 if (AddressMightEscape(I))
220 case Instruction::BitCast:
221 if (!isa<PointerType>(I->getType()))
223 if (AddressMightEscape(I))
226 case Instruction::Ret:
227 // If returned, the address will escape to calling functions, but no
228 // callees could modify it.
237 // getModRefInfo - Check to see if the specified callsite can clobber the
238 // specified memory object. Since we only look at local properties of this
239 // function, we really can't say much about this query. We do, however, use
240 // simple "address taken" analysis on local objects.
242 AliasAnalysis::ModRefResult
243 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
244 if (!isa<Constant>(P))
245 if (const AllocationInst *AI =
246 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
247 // Okay, the pointer is to a stack allocated object. If we can prove that
248 // the pointer never "escapes", then we know the call cannot clobber it,
249 // because it simply can't get its address.
250 if (!AddressMightEscape(AI))
253 // If this is a tail call and P points to a stack location, we know that
254 // the tail call cannot access or modify the local stack.
255 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
256 if (CI->isTailCall() && isa<AllocaInst>(AI))
260 // The AliasAnalysis base class has some smarts, lets use them.
261 return AliasAnalysis::getModRefInfo(CS, P, Size);
264 static bool isNoAliasArgument(const Argument *Arg) {
265 const Function *Func = Arg->getParent();
266 const ParamAttrsList *Attr = Func->getFunctionType()->getParamAttrs();
269 for (Function::const_arg_iterator I = Func->arg_begin(),
270 E = Func->arg_end(); I != E; ++I, ++Idx) {
272 Attr->paramHasAttr(Idx, ParamAttr::NoAlias))
279 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
280 // as array references. Note that this function is heavily tail recursive.
281 // Hopefully we have a smart C++ compiler. :)
283 AliasAnalysis::AliasResult
284 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
285 const Value *V2, unsigned V2Size) {
286 // Strip off any constant expression casts if they exist
287 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
288 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
289 V1 = CE->getOperand(0);
290 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
291 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
292 V2 = CE->getOperand(0);
294 // Are we checking for alias of the same value?
295 if (V1 == V2) return MustAlias;
297 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
298 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty)
299 return NoAlias; // Scalars cannot alias each other
301 // Strip off cast instructions...
302 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
303 return alias(I->getOperand(0), V1Size, V2, V2Size);
304 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
305 return alias(V1, V1Size, I->getOperand(0), V2Size);
307 // Figure out what objects these things are pointing to if we can...
308 const Value *O1 = getUnderlyingObject(V1);
309 const Value *O2 = getUnderlyingObject(V2);
311 // Pointing at a discernible object?
314 if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
315 // Incoming argument cannot alias locally allocated object!
316 if (isa<AllocationInst>(O2)) return NoAlias;
318 // If they are two different objects, and one is a noalias argument
319 // then they do not alias.
320 if (O1 != O2 && isNoAliasArgument(O1Arg))
323 // Otherwise, nothing is known...
326 if (const Argument *O2Arg = dyn_cast<Argument>(O2)) {
327 // Incoming argument cannot alias locally allocated object!
328 if (isa<AllocationInst>(O1)) return NoAlias;
330 // If they are two different objects, and one is a noalias argument
331 // then they do not alias.
332 if (O1 != O2 && isNoAliasArgument(O2Arg))
335 // Otherwise, nothing is known...
336 } else if (O1 != O2) {
337 // If they are two different objects, we know that we have no alias...
341 // If they are the same object, they we can look at the indexes. If they
342 // index off of the object is the same for both pointers, they must alias.
343 // If they are provably different, they must not alias. Otherwise, we
344 // can't tell anything.
348 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
349 return NoAlias; // Unique values don't alias null
351 if (isa<GlobalVariable>(O1) ||
352 (isa<AllocationInst>(O1) &&
353 !cast<AllocationInst>(O1)->isArrayAllocation()))
354 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
355 // If the size of the other access is larger than the total size of the
356 // global/alloca/malloc, it cannot be accessing the global (it's
357 // undefined to load or store bytes before or after an object).
358 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
359 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
360 if (GlobalSize < V2Size && V2Size != ~0U)
366 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
367 return NoAlias; // Unique values don't alias null
369 if (isa<GlobalVariable>(O2) ||
370 (isa<AllocationInst>(O2) &&
371 !cast<AllocationInst>(O2)->isArrayAllocation()))
372 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
373 // If the size of the other access is larger than the total size of the
374 // global/alloca/malloc, it cannot be accessing the object (it's
375 // undefined to load or store bytes before or after an object).
376 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
377 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
378 if (GlobalSize < V1Size && V1Size != ~0U)
383 // If we have two gep instructions with must-alias'ing base pointers, figure
384 // out if the indexes to the GEP tell us anything about the derived pointer.
385 // Note that we also handle chains of getelementptr instructions as well as
386 // constant expression getelementptrs here.
388 if (isGEP(V1) && isGEP(V2)) {
389 // Drill down into the first non-gep value, to test for must-aliasing of
390 // the base pointers.
391 const Value *BasePtr1 = V1, *BasePtr2 = V2;
393 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
394 } while (isGEP(BasePtr1) &&
395 cast<User>(BasePtr1)->getOperand(1) ==
396 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
398 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
399 } while (isGEP(BasePtr2) &&
400 cast<User>(BasePtr2)->getOperand(1) ==
401 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
403 // Do the base pointers alias?
404 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
405 if (BaseAlias == NoAlias) return NoAlias;
406 if (BaseAlias == MustAlias) {
407 // If the base pointers alias each other exactly, check to see if we can
408 // figure out anything about the resultant pointers, to try to prove
411 // Collect all of the chained GEP operands together into one simple place
412 SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
413 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
414 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
416 // If GetGEPOperands were able to fold to the same must-aliased pointer,
417 // do the comparison.
418 if (BasePtr1 == BasePtr2) {
420 CheckGEPInstructions(BasePtr1->getType(),
421 &GEP1Ops[0], GEP1Ops.size(), V1Size,
423 &GEP2Ops[0], GEP2Ops.size(), V2Size);
424 if (GAlias != MayAlias)
430 // Check to see if these two pointers are related by a getelementptr
431 // instruction. If one pointer is a GEP with a non-zero index of the other
432 // pointer, we know they cannot alias.
436 std::swap(V1Size, V2Size);
439 if (V1Size != ~0U && V2Size != ~0U)
441 SmallVector<Value*, 16> GEPOperands;
442 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
444 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
445 if (R == MustAlias) {
446 // If there is at least one non-zero constant index, we know they cannot
448 bool ConstantFound = false;
449 bool AllZerosFound = true;
450 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
451 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
452 if (!C->isNullValue()) {
453 ConstantFound = true;
454 AllZerosFound = false;
458 AllZerosFound = false;
461 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
462 // the ptr, the end result is a must alias also.
467 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
470 // Otherwise we have to check to see that the distance is more than
471 // the size of the argument... build an index vector that is equal to
472 // the arguments provided, except substitute 0's for any variable
473 // indexes we find...
474 if (cast<PointerType>(
475 BasePtr->getType())->getElementType()->isSized()) {
476 for (unsigned i = 0; i != GEPOperands.size(); ++i)
477 if (!isa<ConstantInt>(GEPOperands[i]))
479 Constant::getNullValue(GEPOperands[i]->getType());
481 getTargetData().getIndexedOffset(BasePtr->getType(),
485 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
495 // This function is used to determin if the indices of two GEP instructions are
496 // equal. V1 and V2 are the indices.
497 static bool IndexOperandsEqual(Value *V1, Value *V2) {
498 if (V1->getType() == V2->getType())
500 if (Constant *C1 = dyn_cast<Constant>(V1))
501 if (Constant *C2 = dyn_cast<Constant>(V2)) {
502 // Sign extend the constants to long types, if necessary
503 if (C1->getType() != Type::Int64Ty)
504 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
505 if (C2->getType() != Type::Int64Ty)
506 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
512 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
513 /// base pointers. This checks to see if the index expressions preclude the
514 /// pointers from aliasing...
515 AliasAnalysis::AliasResult
516 BasicAliasAnalysis::CheckGEPInstructions(
517 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
518 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
519 // We currently can't handle the case when the base pointers have different
520 // primitive types. Since this is uncommon anyway, we are happy being
521 // extremely conservative.
522 if (BasePtr1Ty != BasePtr2Ty)
525 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
527 // Find the (possibly empty) initial sequence of equal values... which are not
528 // necessarily constants.
529 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
530 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
531 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
532 unsigned UnequalOper = 0;
533 while (UnequalOper != MinOperands &&
534 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
535 // Advance through the type as we go...
537 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
538 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
540 // If all operands equal each other, then the derived pointers must
541 // alias each other...
543 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
544 "Ran out of type nesting, but not out of operands?");
549 // If we have seen all constant operands, and run out of indexes on one of the
550 // getelementptrs, check to see if the tail of the leftover one is all zeros.
551 // If so, return mustalias.
552 if (UnequalOper == MinOperands) {
553 if (NumGEP1Ops < NumGEP2Ops) {
554 std::swap(GEP1Ops, GEP2Ops);
555 std::swap(NumGEP1Ops, NumGEP2Ops);
558 bool AllAreZeros = true;
559 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
560 if (!isa<Constant>(GEP1Ops[i]) ||
561 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
565 if (AllAreZeros) return MustAlias;
569 // So now we know that the indexes derived from the base pointers,
570 // which are known to alias, are different. We can still determine a
571 // no-alias result if there are differing constant pairs in the index
572 // chain. For example:
573 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
575 // We have to be careful here about array accesses. In particular, consider:
576 // A[1][0] vs A[0][i]
577 // In this case, we don't *know* that the array will be accessed in bounds:
578 // the index could even be negative. Because of this, we have to
579 // conservatively *give up* and return may alias. We disregard differing
580 // array subscripts that are followed by a variable index without going
583 unsigned SizeMax = std::max(G1S, G2S);
584 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
586 // Scan for the first operand that is constant and unequal in the
587 // two getelementptrs...
588 unsigned FirstConstantOper = UnequalOper;
589 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
590 const Value *G1Oper = GEP1Ops[FirstConstantOper];
591 const Value *G2Oper = GEP2Ops[FirstConstantOper];
593 if (G1Oper != G2Oper) // Found non-equal constant indexes...
594 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
595 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
596 if (G1OC->getType() != G2OC->getType()) {
597 // Sign extend both operands to long.
598 if (G1OC->getType() != Type::Int64Ty)
599 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
600 if (G2OC->getType() != Type::Int64Ty)
601 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
602 GEP1Ops[FirstConstantOper] = G1OC;
603 GEP2Ops[FirstConstantOper] = G2OC;
607 // Handle the "be careful" case above: if this is an array/vector
608 // subscript, scan for a subsequent variable array index.
609 if (isa<SequentialType>(BasePtr1Ty)) {
611 cast<SequentialType>(BasePtr1Ty)->getElementType();
612 bool isBadCase = false;
614 for (unsigned Idx = FirstConstantOper+1;
615 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
616 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
617 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
621 NextTy = cast<SequentialType>(NextTy)->getElementType();
624 if (isBadCase) G1OC = 0;
627 // Make sure they are comparable (ie, not constant expressions), and
628 // make sure the GEP with the smaller leading constant is GEP1.
630 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
632 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
633 if (CV->getZExtValue()) { // If they are comparable and G2 > G1
634 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
635 std::swap(NumGEP1Ops, NumGEP2Ops);
642 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
645 // No shared constant operands, and we ran out of common operands. At this
646 // point, the GEP instructions have run through all of their operands, and we
647 // haven't found evidence that there are any deltas between the GEP's.
648 // However, one GEP may have more operands than the other. If this is the
649 // case, there may still be hope. Check this now.
650 if (FirstConstantOper == MinOperands) {
651 // Make GEP1Ops be the longer one if there is a longer one.
652 if (NumGEP1Ops < NumGEP2Ops) {
653 std::swap(GEP1Ops, GEP2Ops);
654 std::swap(NumGEP1Ops, NumGEP2Ops);
657 // Is there anything to check?
658 if (NumGEP1Ops > MinOperands) {
659 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
660 if (isa<ConstantInt>(GEP1Ops[i]) &&
661 !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
662 // Yup, there's a constant in the tail. Set all variables to
663 // constants in the GEP instruction to make it suiteable for
664 // TargetData::getIndexedOffset.
665 for (i = 0; i != MaxOperands; ++i)
666 if (!isa<ConstantInt>(GEP1Ops[i]))
667 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
668 // Okay, now get the offset. This is the relative offset for the full
670 const TargetData &TD = getTargetData();
671 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
674 // Now check without any constants at the end.
675 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
678 // If the tail provided a bit enough offset, return noalias!
679 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
684 // Couldn't find anything useful.
688 // If there are non-equal constants arguments, then we can figure
689 // out a minimum known delta between the two index expressions... at
690 // this point we know that the first constant index of GEP1 is less
691 // than the first constant index of GEP2.
693 // Advance BasePtr[12]Ty over this first differing constant operand.
694 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
695 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
696 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
697 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
699 // We are going to be using TargetData::getIndexedOffset to determine the
700 // offset that each of the GEP's is reaching. To do this, we have to convert
701 // all variable references to constant references. To do this, we convert the
702 // initial sequence of array subscripts into constant zeros to start with.
703 const Type *ZeroIdxTy = GEPPointerTy;
704 for (unsigned i = 0; i != FirstConstantOper; ++i) {
705 if (!isa<StructType>(ZeroIdxTy))
706 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
708 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
709 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
712 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
714 // Loop over the rest of the operands...
715 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
716 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
717 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
718 // If they are equal, use a zero index...
719 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
720 if (!isa<ConstantInt>(Op1))
721 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
722 // Otherwise, just keep the constants we have.
725 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
726 // If this is an array index, make sure the array element is in range.
727 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
728 if (Op1C->getZExtValue() >= AT->getNumElements())
729 return MayAlias; // Be conservative with out-of-range accesses
730 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
731 if (Op1C->getZExtValue() >= PT->getNumElements())
732 return MayAlias; // Be conservative with out-of-range accesses
736 // GEP1 is known to produce a value less than GEP2. To be
737 // conservatively correct, we must assume the largest possible
738 // constant is used in this position. This cannot be the initial
739 // index to the GEP instructions (because we know we have at least one
740 // element before this one with the different constant arguments), so
741 // we know that the current index must be into either a struct or
742 // array. Because we know it's not constant, this cannot be a
743 // structure index. Because of this, we can calculate the maximum
746 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
747 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
748 else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
749 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
755 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
756 // If this is an array index, make sure the array element is in range.
757 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
758 if (Op2C->getZExtValue() >= AT->getNumElements())
759 return MayAlias; // Be conservative with out-of-range accesses
760 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
761 if (Op2C->getZExtValue() >= PT->getNumElements())
762 return MayAlias; // Be conservative with out-of-range accesses
764 } else { // Conservatively assume the minimum value for this index
765 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
770 if (BasePtr1Ty && Op1) {
771 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
772 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
777 if (BasePtr2Ty && Op2) {
778 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
779 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
785 if (GEPPointerTy->getElementType()->isSized()) {
787 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
789 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
790 assert(Offset1<Offset2 && "There is at least one different constant here!");
792 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
793 //cerr << "Determined that these two GEP's don't alias ["
794 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
802 struct VISIBILITY_HIDDEN StringCompare {
803 bool operator()(const char *LHS, const char *RHS) {
804 return strcmp(LHS, RHS) < 0;
809 // Note that this list cannot contain libm functions (such as acos and sqrt)
810 // that set errno on a domain or other error.
811 static const char *DoesntAccessMemoryFns[] = {
812 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
813 "trunc", "truncf", "truncl", "ldexp",
815 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
817 "cos", "cosf", "cosl",
818 "exp", "expf", "expl",
820 "sin", "sinf", "sinl",
821 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
823 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
826 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
827 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
830 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
831 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
833 "iswctype", "towctrans", "towlower", "towupper",
837 "isinf", "isnan", "finite",
839 // C99 math functions
840 "copysign", "copysignf", "copysignd",
841 "nexttoward", "nexttowardf", "nexttowardd",
842 "nextafter", "nextafterf", "nextafterd",
845 "__signbit", "__signbitf", "__signbitl",
849 static const char *OnlyReadsMemoryFns[] = {
850 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
851 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
854 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
855 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
859 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
860 "wcsrchr", "wcsspn", "wcsstr",
863 "alphasort", "alphasort64", "versionsort", "versionsort64",
866 "nan", "nanf", "nand",
869 "feof", "ferror", "fileno",
870 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
873 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
874 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
877 AliasAnalysis::ModRefBehavior
878 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
879 std::vector<PointerAccessInfo> *Info) {
880 if (!F->isDeclaration()) return UnknownModRefBehavior;
882 static bool Initialized = false;
884 NoMemoryTable->insert(NoMemoryTable->end(),
885 DoesntAccessMemoryFns,
886 DoesntAccessMemoryFns+
887 sizeof(DoesntAccessMemoryFns)/sizeof(DoesntAccessMemoryFns[0]));
889 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
892 sizeof(OnlyReadsMemoryFns)/sizeof(OnlyReadsMemoryFns[0]));
893 #define GET_MODREF_BEHAVIOR
894 #include "llvm/Intrinsics.gen"
895 #undef GET_MODREF_BEHAVIOR
897 // Sort the table the first time through.
898 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
899 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
904 std::vector<const char*>::iterator Ptr =
905 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
906 F->getName().c_str(), StringCompare());
907 if (Ptr != NoMemoryTable->end() && *Ptr == F->getName())
908 return DoesNotAccessMemory;
910 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
911 OnlyReadsMemoryTable->end(),
912 F->getName().c_str(), StringCompare());
913 if (Ptr != OnlyReadsMemoryTable->end() && *Ptr == F->getName())
914 return OnlyReadsMemory;
916 return UnknownModRefBehavior;
919 // Make sure that anything that uses AliasAnalysis pulls in this file...
920 DEFINING_FILE_FOR(BasicAliasAnalysis)