1 //===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the default implementation of the Alias Analysis interface
11 // that simply implements a few identities (two different globals cannot alias,
12 // etc), but otherwise does no analysis.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/AliasAnalysis.h"
17 #include "llvm/Analysis/Passes.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DerivedTypes.h"
20 #include "llvm/Function.h"
21 #include "llvm/ParameterAttributes.h"
22 #include "llvm/GlobalVariable.h"
23 #include "llvm/Instructions.h"
24 #include "llvm/Intrinsics.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Target/TargetData.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/ADT/StringMap.h"
29 #include "llvm/ADT/BitVector.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/GetElementPtrTypeIterator.h"
33 #include "llvm/Support/ManagedStatic.h"
38 /// NoAA - This class implements the -no-aa pass, which always returns "I
39 /// don't know" for alias queries. NoAA is unlike other alias analysis
40 /// implementations, in that it does not chain to a previous analysis. As
41 /// such it doesn't follow many of the rules that other alias analyses must.
43 struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
44 static char ID; // Class identification, replacement for typeinfo
45 NoAA() : ImmutablePass((intptr_t)&ID) {}
46 explicit NoAA(intptr_t PID) : ImmutablePass(PID) { }
48 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
49 AU.addRequired<TargetData>();
52 virtual void initializePass() {
53 TD = &getAnalysis<TargetData>();
56 virtual AliasResult alias(const Value *V1, unsigned V1Size,
57 const Value *V2, unsigned V2Size) {
61 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
62 std::vector<PointerAccessInfo> *Info) {
63 return UnknownModRefBehavior;
66 virtual void getArgumentAccesses(Function *F, CallSite CS,
67 std::vector<PointerAccessInfo> &Info) {
68 assert(0 && "This method may not be called on this function!");
71 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
72 virtual bool pointsToConstantMemory(const Value *P) { return false; }
73 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
76 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
79 virtual bool hasNoModRefInfoForCalls() const { return true; }
81 virtual void deleteValue(Value *V) {}
82 virtual void copyValue(Value *From, Value *To) {}
85 // Register this pass...
88 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
90 // Declare that we implement the AliasAnalysis interface
91 RegisterAnalysisGroup<AliasAnalysis> V(U);
92 } // End of anonymous namespace
94 ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }
97 /// BasicAliasAnalysis - This is the default alias analysis implementation.
98 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
99 /// derives from the NoAA class.
100 struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
101 static char ID; // Class identification, replacement for typeinfo
102 BasicAliasAnalysis() : NoAA((intptr_t)&ID) { }
103 AliasResult alias(const Value *V1, unsigned V1Size,
104 const Value *V2, unsigned V2Size);
106 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
107 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
108 return NoAA::getModRefInfo(CS1,CS2);
111 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
112 /// non-escaping allocations.
113 virtual bool hasNoModRefInfoForCalls() const { return false; }
115 /// pointsToConstantMemory - Chase pointers until we find a (constant
117 bool pointsToConstantMemory(const Value *P);
119 virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
120 std::vector<PointerAccessInfo> *Info);
123 // CheckGEPInstructions - Check two GEP instructions with known
124 // must-aliasing base pointers. This checks to see if the index expressions
125 // preclude the pointers from aliasing...
127 CheckGEPInstructions(const Type* BasePtr1Ty,
128 Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,
129 const Type *BasePtr2Ty,
130 Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size);
133 // Register this pass...
134 char BasicAliasAnalysis::ID = 0;
135 RegisterPass<BasicAliasAnalysis>
136 X("basicaa", "Basic Alias Analysis (default AA impl)");
138 // Declare that we implement the AliasAnalysis interface
139 RegisterAnalysisGroup<AliasAnalysis, true> Y(X);
140 } // End of anonymous namespace
142 ImmutablePass *llvm::createBasicAliasAnalysisPass() {
143 return new BasicAliasAnalysis();
146 // getUnderlyingObject - This traverses the use chain to figure out what object
147 // the specified value points to. If the value points to, or is derived from, a
148 // unique object or an argument, return it.
149 static const Value *getUnderlyingObject(const Value *V) {
150 if (!isa<PointerType>(V->getType())) return 0;
152 // If we are at some type of object, return it. GlobalValues and Allocations
153 // have unique addresses.
154 if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V))
157 // Traverse through different addressing mechanisms...
158 if (const Instruction *I = dyn_cast<Instruction>(V)) {
159 if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I))
160 return getUnderlyingObject(I->getOperand(0));
161 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
162 if (CE->getOpcode() == Instruction::BitCast ||
163 CE->getOpcode() == Instruction::GetElementPtr)
164 return getUnderlyingObject(CE->getOperand(0));
169 static const User *isGEP(const Value *V) {
170 if (isa<GetElementPtrInst>(V) ||
171 (isa<ConstantExpr>(V) &&
172 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
173 return cast<User>(V);
177 static const Value *GetGEPOperands(const Value *V,
178 SmallVector<Value*, 16> &GEPOps){
179 assert(GEPOps.empty() && "Expect empty list to populate!");
180 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
181 cast<User>(V)->op_end());
183 // Accumulate all of the chained indexes into the operand array
184 V = cast<User>(V)->getOperand(0);
186 while (const User *G = isGEP(V)) {
187 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
188 !cast<Constant>(GEPOps[0])->isNullValue())
189 break; // Don't handle folding arbitrary pointer offsets yet...
190 GEPOps.erase(GEPOps.begin()); // Drop the zero index
191 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
192 V = G->getOperand(0);
197 /// pointsToConstantMemory - Chase pointers until we find a (constant
199 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
200 if (const Value *V = getUnderlyingObject(P))
201 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
202 return GV->isConstant();
206 // Determine if an AllocationInst instruction escapes from the function it is
207 // contained in. If it does not escape, there is no way for another function to
208 // mod/ref it. We do this by looking at its uses and determining if the uses
209 // can escape (recursively).
210 static bool AddressMightEscape(const Value *V) {
211 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
213 const Instruction *I = cast<Instruction>(*UI);
214 switch (I->getOpcode()) {
215 case Instruction::Load:
217 case Instruction::Store:
218 if (I->getOperand(0) == V)
219 return true; // Escapes if the pointer is stored.
221 case Instruction::GetElementPtr:
222 if (AddressMightEscape(I))
225 case Instruction::BitCast:
226 if (!isa<PointerType>(I->getType()))
228 if (AddressMightEscape(I))
231 case Instruction::Ret:
232 // If returned, the address will escape to calling functions, but no
233 // callees could modify it.
242 // getModRefInfo - Check to see if the specified callsite can clobber the
243 // specified memory object. Since we only look at local properties of this
244 // function, we really can't say much about this query. We do, however, use
245 // simple "address taken" analysis on local objects.
247 AliasAnalysis::ModRefResult
248 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
249 if (!isa<Constant>(P))
250 if (const AllocationInst *AI =
251 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
252 // Okay, the pointer is to a stack allocated object. If we can prove that
253 // the pointer never "escapes", then we know the call cannot clobber it,
254 // because it simply can't get its address.
255 if (!AddressMightEscape(AI))
258 // If this is a tail call and P points to a stack location, we know that
259 // the tail call cannot access or modify the local stack.
260 if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
261 if (CI->isTailCall() && isa<AllocaInst>(AI))
265 // The AliasAnalysis base class has some smarts, lets use them.
266 return AliasAnalysis::getModRefInfo(CS, P, Size);
269 static bool isNoAliasArgument(const Argument *Arg) {
270 const Function *Func = Arg->getParent();
271 const ParamAttrsList *Attr = Func->getFunctionType()->getParamAttrs();
274 for (Function::const_arg_iterator I = Func->arg_begin(),
275 E = Func->arg_end(); I != E; ++I, ++Idx) {
277 Attr->paramHasAttr(Idx, ParamAttr::NoAlias))
284 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
285 // as array references. Note that this function is heavily tail recursive.
286 // Hopefully we have a smart C++ compiler. :)
288 AliasAnalysis::AliasResult
289 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
290 const Value *V2, unsigned V2Size) {
291 // Strip off any constant expression casts if they exist
292 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
293 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
294 V1 = CE->getOperand(0);
295 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
296 if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType()))
297 V2 = CE->getOperand(0);
299 // Are we checking for alias of the same value?
300 if (V1 == V2) return MustAlias;
302 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
303 V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty)
304 return NoAlias; // Scalars cannot alias each other
306 // Strip off cast instructions...
307 if (const BitCastInst *I = dyn_cast<BitCastInst>(V1))
308 return alias(I->getOperand(0), V1Size, V2, V2Size);
309 if (const BitCastInst *I = dyn_cast<BitCastInst>(V2))
310 return alias(V1, V1Size, I->getOperand(0), V2Size);
312 // Figure out what objects these things are pointing to if we can...
313 const Value *O1 = getUnderlyingObject(V1);
314 const Value *O2 = getUnderlyingObject(V2);
316 // Pointing at a discernible object?
319 if (const Argument *O1Arg = dyn_cast<Argument>(O1)) {
320 // Incoming argument cannot alias locally allocated object!
321 if (isa<AllocationInst>(O2)) return NoAlias;
323 // If they are two different objects, and one is a noalias argument
324 // then they do not alias.
325 if (O1 != O2 && isNoAliasArgument(O1Arg))
328 // Otherwise, nothing is known...
331 if (const Argument *O2Arg = dyn_cast<Argument>(O2)) {
332 // Incoming argument cannot alias locally allocated object!
333 if (isa<AllocationInst>(O1)) return NoAlias;
335 // If they are two different objects, and one is a noalias argument
336 // then they do not alias.
337 if (O1 != O2 && isNoAliasArgument(O2Arg))
340 // Otherwise, nothing is known...
341 } else if (O1 != O2) {
342 if (!isa<Argument>(O1))
343 // If they are two different objects, we know that we have no alias...
347 // If they are the same object, they we can look at the indexes. If they
348 // index off of the object is the same for both pointers, they must alias.
349 // If they are provably different, they must not alias. Otherwise, we
350 // can't tell anything.
354 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
355 return NoAlias; // Unique values don't alias null
357 if (isa<GlobalVariable>(O1) ||
358 (isa<AllocationInst>(O1) &&
359 !cast<AllocationInst>(O1)->isArrayAllocation()))
360 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
361 // If the size of the other access is larger than the total size of the
362 // global/alloca/malloc, it cannot be accessing the global (it's
363 // undefined to load or store bytes before or after an object).
364 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
365 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
366 if (GlobalSize < V2Size && V2Size != ~0U)
372 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
373 return NoAlias; // Unique values don't alias null
375 if (isa<GlobalVariable>(O2) ||
376 (isa<AllocationInst>(O2) &&
377 !cast<AllocationInst>(O2)->isArrayAllocation()))
378 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
379 // If the size of the other access is larger than the total size of the
380 // global/alloca/malloc, it cannot be accessing the object (it's
381 // undefined to load or store bytes before or after an object).
382 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
383 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
384 if (GlobalSize < V1Size && V1Size != ~0U)
389 // If we have two gep instructions with must-alias'ing base pointers, figure
390 // out if the indexes to the GEP tell us anything about the derived pointer.
391 // Note that we also handle chains of getelementptr instructions as well as
392 // constant expression getelementptrs here.
394 if (isGEP(V1) && isGEP(V2)) {
395 // Drill down into the first non-gep value, to test for must-aliasing of
396 // the base pointers.
397 const Value *BasePtr1 = V1, *BasePtr2 = V2;
399 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
400 } while (isGEP(BasePtr1) &&
401 cast<User>(BasePtr1)->getOperand(1) ==
402 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
404 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
405 } while (isGEP(BasePtr2) &&
406 cast<User>(BasePtr2)->getOperand(1) ==
407 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
409 // Do the base pointers alias?
410 AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U);
411 if (BaseAlias == NoAlias) return NoAlias;
412 if (BaseAlias == MustAlias) {
413 // If the base pointers alias each other exactly, check to see if we can
414 // figure out anything about the resultant pointers, to try to prove
417 // Collect all of the chained GEP operands together into one simple place
418 SmallVector<Value*, 16> GEP1Ops, GEP2Ops;
419 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
420 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
422 // If GetGEPOperands were able to fold to the same must-aliased pointer,
423 // do the comparison.
424 if (BasePtr1 == BasePtr2) {
426 CheckGEPInstructions(BasePtr1->getType(),
427 &GEP1Ops[0], GEP1Ops.size(), V1Size,
429 &GEP2Ops[0], GEP2Ops.size(), V2Size);
430 if (GAlias != MayAlias)
436 // Check to see if these two pointers are related by a getelementptr
437 // instruction. If one pointer is a GEP with a non-zero index of the other
438 // pointer, we know they cannot alias.
442 std::swap(V1Size, V2Size);
445 if (V1Size != ~0U && V2Size != ~0U)
447 SmallVector<Value*, 16> GEPOperands;
448 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
450 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
451 if (R == MustAlias) {
452 // If there is at least one non-zero constant index, we know they cannot
454 bool ConstantFound = false;
455 bool AllZerosFound = true;
456 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
457 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
458 if (!C->isNullValue()) {
459 ConstantFound = true;
460 AllZerosFound = false;
464 AllZerosFound = false;
467 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
468 // the ptr, the end result is a must alias also.
473 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
476 // Otherwise we have to check to see that the distance is more than
477 // the size of the argument... build an index vector that is equal to
478 // the arguments provided, except substitute 0's for any variable
479 // indexes we find...
480 if (cast<PointerType>(
481 BasePtr->getType())->getElementType()->isSized()) {
482 for (unsigned i = 0; i != GEPOperands.size(); ++i)
483 if (!isa<ConstantInt>(GEPOperands[i]))
485 Constant::getNullValue(GEPOperands[i]->getType());
487 getTargetData().getIndexedOffset(BasePtr->getType(),
491 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
501 // This function is used to determin if the indices of two GEP instructions are
502 // equal. V1 and V2 are the indices.
503 static bool IndexOperandsEqual(Value *V1, Value *V2) {
504 if (V1->getType() == V2->getType())
506 if (Constant *C1 = dyn_cast<Constant>(V1))
507 if (Constant *C2 = dyn_cast<Constant>(V2)) {
508 // Sign extend the constants to long types, if necessary
509 if (C1->getType() != Type::Int64Ty)
510 C1 = ConstantExpr::getSExt(C1, Type::Int64Ty);
511 if (C2->getType() != Type::Int64Ty)
512 C2 = ConstantExpr::getSExt(C2, Type::Int64Ty);
518 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
519 /// base pointers. This checks to see if the index expressions preclude the
520 /// pointers from aliasing...
521 AliasAnalysis::AliasResult
522 BasicAliasAnalysis::CheckGEPInstructions(
523 const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S,
524 const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) {
525 // We currently can't handle the case when the base pointers have different
526 // primitive types. Since this is uncommon anyway, we are happy being
527 // extremely conservative.
528 if (BasePtr1Ty != BasePtr2Ty)
531 const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty);
533 // Find the (possibly empty) initial sequence of equal values... which are not
534 // necessarily constants.
535 unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops;
536 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
537 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
538 unsigned UnequalOper = 0;
539 while (UnequalOper != MinOperands &&
540 IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
541 // Advance through the type as we go...
543 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
544 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
546 // If all operands equal each other, then the derived pointers must
547 // alias each other...
549 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
550 "Ran out of type nesting, but not out of operands?");
555 // If we have seen all constant operands, and run out of indexes on one of the
556 // getelementptrs, check to see if the tail of the leftover one is all zeros.
557 // If so, return mustalias.
558 if (UnequalOper == MinOperands) {
559 if (NumGEP1Ops < NumGEP2Ops) {
560 std::swap(GEP1Ops, GEP2Ops);
561 std::swap(NumGEP1Ops, NumGEP2Ops);
564 bool AllAreZeros = true;
565 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
566 if (!isa<Constant>(GEP1Ops[i]) ||
567 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
571 if (AllAreZeros) return MustAlias;
575 // So now we know that the indexes derived from the base pointers,
576 // which are known to alias, are different. We can still determine a
577 // no-alias result if there are differing constant pairs in the index
578 // chain. For example:
579 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
581 // We have to be careful here about array accesses. In particular, consider:
582 // A[1][0] vs A[0][i]
583 // In this case, we don't *know* that the array will be accessed in bounds:
584 // the index could even be negative. Because of this, we have to
585 // conservatively *give up* and return may alias. We disregard differing
586 // array subscripts that are followed by a variable index without going
589 unsigned SizeMax = std::max(G1S, G2S);
590 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
592 // Scan for the first operand that is constant and unequal in the
593 // two getelementptrs...
594 unsigned FirstConstantOper = UnequalOper;
595 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
596 const Value *G1Oper = GEP1Ops[FirstConstantOper];
597 const Value *G2Oper = GEP2Ops[FirstConstantOper];
599 if (G1Oper != G2Oper) // Found non-equal constant indexes...
600 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
601 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
602 if (G1OC->getType() != G2OC->getType()) {
603 // Sign extend both operands to long.
604 if (G1OC->getType() != Type::Int64Ty)
605 G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty);
606 if (G2OC->getType() != Type::Int64Ty)
607 G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty);
608 GEP1Ops[FirstConstantOper] = G1OC;
609 GEP2Ops[FirstConstantOper] = G2OC;
613 // Handle the "be careful" case above: if this is an array/vector
614 // subscript, scan for a subsequent variable array index.
615 if (isa<SequentialType>(BasePtr1Ty)) {
617 cast<SequentialType>(BasePtr1Ty)->getElementType();
618 bool isBadCase = false;
620 for (unsigned Idx = FirstConstantOper+1;
621 Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) {
622 const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx];
623 if (!isa<Constant>(V1) || !isa<Constant>(V2)) {
627 NextTy = cast<SequentialType>(NextTy)->getElementType();
630 if (isBadCase) G1OC = 0;
633 // Make sure they are comparable (ie, not constant expressions), and
634 // make sure the GEP with the smaller leading constant is GEP1.
636 Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT,
638 if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) {
639 if (CV->getZExtValue()) { // If they are comparable and G2 > G1
640 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
641 std::swap(NumGEP1Ops, NumGEP2Ops);
648 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
651 // No shared constant operands, and we ran out of common operands. At this
652 // point, the GEP instructions have run through all of their operands, and we
653 // haven't found evidence that there are any deltas between the GEP's.
654 // However, one GEP may have more operands than the other. If this is the
655 // case, there may still be hope. Check this now.
656 if (FirstConstantOper == MinOperands) {
657 // Make GEP1Ops be the longer one if there is a longer one.
658 if (NumGEP1Ops < NumGEP2Ops) {
659 std::swap(GEP1Ops, GEP2Ops);
660 std::swap(NumGEP1Ops, NumGEP2Ops);
663 // Is there anything to check?
664 if (NumGEP1Ops > MinOperands) {
665 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
666 if (isa<ConstantInt>(GEP1Ops[i]) &&
667 !cast<ConstantInt>(GEP1Ops[i])->isZero()) {
668 // Yup, there's a constant in the tail. Set all variables to
669 // constants in the GEP instruction to make it suiteable for
670 // TargetData::getIndexedOffset.
671 for (i = 0; i != MaxOperands; ++i)
672 if (!isa<ConstantInt>(GEP1Ops[i]))
673 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
674 // Okay, now get the offset. This is the relative offset for the full
676 const TargetData &TD = getTargetData();
677 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
680 // Now check without any constants at the end.
681 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops,
684 // If the tail provided a bit enough offset, return noalias!
685 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
690 // Couldn't find anything useful.
694 // If there are non-equal constants arguments, then we can figure
695 // out a minimum known delta between the two index expressions... at
696 // this point we know that the first constant index of GEP1 is less
697 // than the first constant index of GEP2.
699 // Advance BasePtr[12]Ty over this first differing constant operand.
700 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->
701 getTypeAtIndex(GEP2Ops[FirstConstantOper]);
702 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->
703 getTypeAtIndex(GEP1Ops[FirstConstantOper]);
705 // We are going to be using TargetData::getIndexedOffset to determine the
706 // offset that each of the GEP's is reaching. To do this, we have to convert
707 // all variable references to constant references. To do this, we convert the
708 // initial sequence of array subscripts into constant zeros to start with.
709 const Type *ZeroIdxTy = GEPPointerTy;
710 for (unsigned i = 0; i != FirstConstantOper; ++i) {
711 if (!isa<StructType>(ZeroIdxTy))
712 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty);
714 if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy))
715 ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]);
718 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
720 // Loop over the rest of the operands...
721 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
722 const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0;
723 const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0;
724 // If they are equal, use a zero index...
725 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
726 if (!isa<ConstantInt>(Op1))
727 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
728 // Otherwise, just keep the constants we have.
731 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
732 // If this is an array index, make sure the array element is in range.
733 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
734 if (Op1C->getZExtValue() >= AT->getNumElements())
735 return MayAlias; // Be conservative with out-of-range accesses
736 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
737 if (Op1C->getZExtValue() >= PT->getNumElements())
738 return MayAlias; // Be conservative with out-of-range accesses
742 // GEP1 is known to produce a value less than GEP2. To be
743 // conservatively correct, we must assume the largest possible
744 // constant is used in this position. This cannot be the initial
745 // index to the GEP instructions (because we know we have at least one
746 // element before this one with the different constant arguments), so
747 // we know that the current index must be into either a struct or
748 // array. Because we know it's not constant, this cannot be a
749 // structure index. Because of this, we can calculate the maximum
752 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
753 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1);
754 else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty))
755 GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,PT->getNumElements()-1);
761 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
762 // If this is an array index, make sure the array element is in range.
763 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) {
764 if (Op2C->getZExtValue() >= AT->getNumElements())
765 return MayAlias; // Be conservative with out-of-range accesses
766 } else if (const VectorType *PT = dyn_cast<VectorType>(BasePtr1Ty)) {
767 if (Op2C->getZExtValue() >= PT->getNumElements())
768 return MayAlias; // Be conservative with out-of-range accesses
770 } else { // Conservatively assume the minimum value for this index
771 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
776 if (BasePtr1Ty && Op1) {
777 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
778 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
783 if (BasePtr2Ty && Op2) {
784 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
785 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
791 if (GEPPointerTy->getElementType()->isSized()) {
793 getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops);
795 getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops);
796 assert(Offset1<Offset2 && "There is at least one different constant here!");
798 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
799 //cerr << "Determined that these two GEP's don't alias ["
800 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
808 struct VISIBILITY_HIDDEN StringCompare {
809 bool operator()(const char *LHS, const char *RHS) {
810 return strcmp(LHS, RHS) < 0;
815 // Note that this list cannot contain libm functions (such as acos and sqrt)
816 // that set errno on a domain or other error.
817 static const char *DoesntAccessMemoryFns[] = {
818 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
819 "trunc", "truncf", "truncl", "ldexp",
821 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
823 "cos", "cosf", "cosl",
824 "exp", "expf", "expl",
826 "sin", "sinf", "sinl",
827 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
829 "floor", "floorf", "floorl", "ceil", "ceilf", "ceill",
832 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
833 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
836 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
837 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
839 "iswctype", "towctrans", "towlower", "towupper",
843 "isinf", "isnan", "finite",
845 // C99 math functions
846 "copysign", "copysignf", "copysignd",
847 "nexttoward", "nexttowardf", "nexttowardd",
848 "nextafter", "nextafterf", "nextafterd",
851 "__signbit", "__signbitf", "__signbitl",
855 static const char *OnlyReadsMemoryFns[] = {
856 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
857 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
860 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
861 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
865 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
866 "wcsrchr", "wcsspn", "wcsstr",
869 "alphasort", "alphasort64", "versionsort", "versionsort64",
872 "nan", "nanf", "nand",
875 "feof", "ferror", "fileno",
876 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
879 static ManagedStatic<std::vector<const char*> > NoMemoryTable;
880 static ManagedStatic<std::vector<const char*> > OnlyReadsMemoryTable;
882 static ManagedStatic<BitVector> NoMemoryIntrinsics;
883 static ManagedStatic<BitVector> OnlyReadsMemoryIntrinsics;
886 AliasAnalysis::ModRefBehavior
887 BasicAliasAnalysis::getModRefBehavior(Function *F, CallSite CS,
888 std::vector<PointerAccessInfo> *Info) {
889 if (!F->isDeclaration()) return UnknownModRefBehavior;
891 static bool Initialized = false;
893 NoMemoryTable->insert(NoMemoryTable->end(),
894 DoesntAccessMemoryFns,
895 array_endof(DoesntAccessMemoryFns));
897 OnlyReadsMemoryTable->insert(OnlyReadsMemoryTable->end(),
899 array_endof(OnlyReadsMemoryFns));
901 // Sort the table the first time through.
902 std::sort(NoMemoryTable->begin(), NoMemoryTable->end(), StringCompare());
903 std::sort(OnlyReadsMemoryTable->begin(), OnlyReadsMemoryTable->end(),
906 NoMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
907 OnlyReadsMemoryIntrinsics->resize(Intrinsic::num_intrinsics);
908 #define GET_MODREF_BEHAVIOR
909 #include "llvm/Intrinsics.gen"
910 #undef GET_MODREF_BEHAVIOR
915 // If this is an intrinsic, we can use lookup tables
916 if (unsigned id = F->getIntrinsicID()) {
917 if (NoMemoryIntrinsics->test(id))
918 return DoesNotAccessMemory;
919 if (OnlyReadsMemoryIntrinsics->test(id))
920 return OnlyReadsMemory;
922 return UnknownModRefBehavior;
925 ValueName *Name = F->getValueName();
926 unsigned NameLen = Name->getKeyLength();
927 const char *NamePtr = Name->getKeyData();
929 // If there is an embedded nul character in the function name, we can never
931 if (strlen(NamePtr) != NameLen)
932 return UnknownModRefBehavior;
934 std::vector<const char*>::iterator Ptr =
935 std::lower_bound(NoMemoryTable->begin(), NoMemoryTable->end(),
936 NamePtr, StringCompare());
937 if (Ptr != NoMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
938 return DoesNotAccessMemory;
940 Ptr = std::lower_bound(OnlyReadsMemoryTable->begin(),
941 OnlyReadsMemoryTable->end(),
942 NamePtr, StringCompare());
943 if (Ptr != OnlyReadsMemoryTable->end() && strcmp(*Ptr, NamePtr) == 0)
944 return OnlyReadsMemory;
946 return UnknownModRefBehavior;
949 // Make sure that anything that uses AliasAnalysis pulls in this file...
950 DEFINING_FILE_FOR(BasicAliasAnalysis)