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 // FIXME: This could be extended for a very simple form of mod/ref information.
15 // If a pointer is locally allocated (either malloc or alloca) and never passed
16 // into a call or stored to memory, then we know that calls will not mod/ref the
17 // memory. This can be important for tailcallelim, and can support CSE of loads
18 // and dead store elimination across calls. This is particularly important for
19 // stack allocated arrays.
21 //===----------------------------------------------------------------------===//
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Constants.h"
25 #include "llvm/DerivedTypes.h"
26 #include "llvm/Function.h"
27 #include "llvm/GlobalVariable.h"
28 #include "llvm/iOther.h"
29 #include "llvm/iMemory.h"
30 #include "llvm/Pass.h"
31 #include "llvm/Target/TargetData.h"
32 #include "llvm/Support/GetElementPtrTypeIterator.h"
35 // Make sure that anything that uses AliasAnalysis pulls in this file...
36 void llvm::BasicAAStub() {}
39 /// NoAA - This class implements the -no-aa pass, which always returns "I
40 /// don't know" for alias queries. NoAA is unlike other alias analysis
41 /// implementations, in that it does not chain to a previous analysis. As
42 /// such it doesn't follow many of the rules that other alias analyses must.
44 struct NoAA : public ImmutablePass, public AliasAnalysis {
45 virtual AliasResult alias(const Value *V1, unsigned V1Size,
46 const Value *V2, unsigned V2Size) {
50 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
51 virtual bool pointsToConstantMemory(const Value *P) { return false; }
52 virtual bool doesNotAccessMemory(Function *F) { return false; }
53 virtual bool onlyReadsMemory(Function *F) { return false; }
54 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
57 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
60 virtual bool hasNoModRefInfoForCalls() const { return true; }
62 virtual void deleteValue(Value *V) {}
63 virtual void copyValue(Value *From, Value *To) {}
64 virtual void getAnalysisUsage(AnalysisUsage &AU) const {}
67 // Register this pass...
69 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
71 // Declare that we implement the AliasAnalysis interface
72 RegisterAnalysisGroup<AliasAnalysis, NoAA> V;
73 } // End of anonymous namespace
77 /// BasicAliasAnalysis - This is the default alias analysis implementation.
78 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
79 /// derives from the NoAA class.
80 struct BasicAliasAnalysis : public NoAA {
81 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
82 AU.addRequired<TargetData>();
85 virtual void initializePass() {
86 TD = &getAnalysis<TargetData>();
89 AliasResult alias(const Value *V1, unsigned V1Size,
90 const Value *V2, unsigned V2Size);
92 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
94 /// hasNoModRefInfoForCalls - We have no way to test one call against
95 /// another, unless they are pure or const.
96 virtual bool hasNoModRefInfoForCalls() const { return true; }
98 /// pointsToConstantMemory - Chase pointers until we find a (constant
100 bool pointsToConstantMemory(const Value *P);
102 virtual bool doesNotAccessMemory(Function *F);
103 virtual bool onlyReadsMemory(Function *F);
106 // CheckGEPInstructions - Check two GEP instructions with known
107 // must-aliasing base pointers. This checks to see if the index expressions
108 // preclude the pointers from aliasing...
110 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
112 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
116 // Register this pass...
117 RegisterOpt<BasicAliasAnalysis>
118 X("basicaa", "Basic Alias Analysis (default AA impl)");
120 // Declare that we implement the AliasAnalysis interface
121 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
122 } // End of anonymous namespace
124 // hasUniqueAddress - Return true if the specified value points to something
125 // with a unique, discernable, address.
126 static inline bool hasUniqueAddress(const Value *V) {
127 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
130 // getUnderlyingObject - This traverses the use chain to figure out what object
131 // the specified value points to. If the value points to, or is derived from, a
132 // unique object or an argument, return it.
133 static const Value *getUnderlyingObject(const Value *V) {
134 if (!isa<PointerType>(V->getType())) return 0;
136 // If we are at some type of object... return it.
137 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
139 // Traverse through different addressing mechanisms...
140 if (const Instruction *I = dyn_cast<Instruction>(V)) {
141 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
142 return getUnderlyingObject(I->getOperand(0));
143 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
144 if (CE->getOpcode() == Instruction::Cast ||
145 CE->getOpcode() == Instruction::GetElementPtr)
146 return getUnderlyingObject(CE->getOperand(0));
147 } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) {
148 return CPR->getValue();
153 static const User *isGEP(const Value *V) {
154 if (isa<GetElementPtrInst>(V) ||
155 (isa<ConstantExpr>(V) &&
156 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
157 return cast<User>(V);
161 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
162 assert(GEPOps.empty() && "Expect empty list to populate!");
163 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
164 cast<User>(V)->op_end());
166 // Accumulate all of the chained indexes into the operand array
167 V = cast<User>(V)->getOperand(0);
169 while (const User *G = isGEP(V)) {
170 if (!isa<Constant>(GEPOps[0]) ||
171 !cast<Constant>(GEPOps[0])->isNullValue())
172 break; // Don't handle folding arbitrary pointer offsets yet...
173 GEPOps.erase(GEPOps.begin()); // Drop the zero index
174 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
175 V = G->getOperand(0);
180 /// pointsToConstantMemory - Chase pointers until we find a (constant
182 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
183 if (const Value *V = getUnderlyingObject(P))
184 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
185 return GV->isConstant();
189 static bool AddressMightEscape(const Value *V) {
190 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
192 const Instruction *I = cast<Instruction>(*UI);
193 switch (I->getOpcode()) {
194 case Instruction::Load: break;
195 case Instruction::Store:
196 if (I->getOperand(0) == V)
197 return true; // Escapes if the pointer is stored.
199 case Instruction::GetElementPtr:
200 if (AddressMightEscape(I)) return true;
202 case Instruction::Cast:
203 if (!isa<PointerType>(I->getType()))
205 if (AddressMightEscape(I)) return true;
214 // getModRefInfo - Check to see if the specified callsite can clobber the
215 // specified memory object. Since we only look at local properties of this
216 // function, we really can't say much about this query. We do, however, use
217 // simple "address taken" analysis on local objects.
219 AliasAnalysis::ModRefResult
220 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
221 if (!isa<Constant>(P) && !isa<GlobalValue>(P))
222 if (const AllocationInst *AI =
223 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
224 // Okay, the pointer is to a stack allocated object. If we can prove that
225 // the pointer never "escapes", then we know the call cannot clobber it,
226 // because it simply can't get its address.
227 if (!AddressMightEscape(AI))
231 // The AliasAnalysis base class has some smarts, lets use them.
232 return AliasAnalysis::getModRefInfo(CS, P, Size);
235 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
236 // as array references. Note that this function is heavily tail recursive.
237 // Hopefully we have a smart C++ compiler. :)
239 AliasAnalysis::AliasResult
240 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
241 const Value *V2, unsigned V2Size) {
242 // Strip off any constant expression casts if they exist
243 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
244 if (CE->getOpcode() == Instruction::Cast)
245 V1 = CE->getOperand(0);
246 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
247 if (CE->getOpcode() == Instruction::Cast)
248 V2 = CE->getOperand(0);
250 // Strip off constant pointer refs if they exist
251 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
252 V1 = CPR->getValue();
253 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
254 V2 = CPR->getValue();
256 // Are we checking for alias of the same value?
257 if (V1 == V2) return MustAlias;
259 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
260 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
261 return NoAlias; // Scalars cannot alias each other
263 // Strip off cast instructions...
264 if (const Instruction *I = dyn_cast<CastInst>(V1))
265 return alias(I->getOperand(0), V1Size, V2, V2Size);
266 if (const Instruction *I = dyn_cast<CastInst>(V2))
267 return alias(V1, V1Size, I->getOperand(0), V2Size);
269 // Figure out what objects these things are pointing to if we can...
270 const Value *O1 = getUnderlyingObject(V1);
271 const Value *O2 = getUnderlyingObject(V2);
273 // Pointing at a discernible object?
275 if (isa<Argument>(O1)) {
276 // Incoming argument cannot alias locally allocated object!
277 if (isa<AllocationInst>(O2)) return NoAlias;
278 // Otherwise, nothing is known...
279 } else if (isa<Argument>(O2)) {
280 // Incoming argument cannot alias locally allocated object!
281 if (isa<AllocationInst>(O1)) return NoAlias;
282 // Otherwise, nothing is known...
284 // If they are two different objects, we know that we have no alias...
285 if (O1 != O2) return NoAlias;
288 // If they are the same object, they we can look at the indexes. If they
289 // index off of the object is the same for both pointers, they must alias.
290 // If they are provably different, they must not alias. Otherwise, we can't
292 } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
293 return NoAlias; // Unique values don't alias null
294 } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
295 return NoAlias; // Unique values don't alias null
298 // If we have two gep instructions with must-alias'ing base pointers, figure
299 // out if the indexes to the GEP tell us anything about the derived pointer.
300 // Note that we also handle chains of getelementptr instructions as well as
301 // constant expression getelementptrs here.
303 if (isGEP(V1) && isGEP(V2)) {
304 // Drill down into the first non-gep value, to test for must-aliasing of
305 // the base pointers.
306 const Value *BasePtr1 = V1, *BasePtr2 = V2;
308 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
309 } while (isGEP(BasePtr1) &&
310 cast<User>(BasePtr1)->getOperand(1) ==
311 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
313 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
314 } while (isGEP(BasePtr2) &&
315 cast<User>(BasePtr2)->getOperand(1) ==
316 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
318 // Do the base pointers alias?
319 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
320 if (BaseAlias == NoAlias) return NoAlias;
321 if (BaseAlias == MustAlias) {
322 // If the base pointers alias each other exactly, check to see if we can
323 // figure out anything about the resultant pointers, to try to prove
326 // Collect all of the chained GEP operands together into one simple place
327 std::vector<Value*> GEP1Ops, GEP2Ops;
328 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
329 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
332 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
333 BasePtr2->getType(), GEP2Ops, V2Size);
334 if (GAlias != MayAlias)
339 // Check to see if these two pointers are related by a getelementptr
340 // instruction. If one pointer is a GEP with a non-zero index of the other
341 // pointer, we know they cannot alias.
345 std::swap(V1Size, V2Size);
348 if (V1Size != ~0U && V2Size != ~0U)
349 if (const User *GEP = isGEP(V1)) {
350 std::vector<Value*> GEPOperands;
351 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
353 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
354 if (R == MustAlias) {
355 // If there is at least one non-zero constant index, we know they cannot
357 bool ConstantFound = false;
358 bool AllZerosFound = true;
359 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
360 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
361 if (!C->isNullValue()) {
362 ConstantFound = true;
363 AllZerosFound = false;
367 AllZerosFound = false;
370 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
371 // the ptr, the end result is a must alias also.
376 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
379 // Otherwise we have to check to see that the distance is more than
380 // the size of the argument... build an index vector that is equal to
381 // the arguments provided, except substitute 0's for any variable
382 // indexes we find...
383 for (unsigned i = 0; i != GEPOperands.size(); ++i)
384 if (!isa<Constant>(GEPOperands[i]) ||
385 isa<ConstantExpr>(GEPOperands[i]))
386 GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType());
387 int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(),
389 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
398 static bool ValuesEqual(Value *V1, Value *V2) {
399 if (V1->getType() == V2->getType())
401 if (Constant *C1 = dyn_cast<Constant>(V1))
402 if (Constant *C2 = dyn_cast<Constant>(V2)) {
403 // Sign extend the constants to long types.
404 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
405 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
411 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
412 /// base pointers. This checks to see if the index expressions preclude the
413 /// pointers from aliasing...
414 AliasAnalysis::AliasResult BasicAliasAnalysis::
415 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
417 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
419 // We currently can't handle the case when the base pointers have different
420 // primitive types. Since this is uncommon anyway, we are happy being
421 // extremely conservative.
422 if (BasePtr1Ty != BasePtr2Ty)
425 const Type *GEPPointerTy = BasePtr1Ty;
427 // Find the (possibly empty) initial sequence of equal values... which are not
428 // necessarily constants.
429 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
430 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
431 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
432 unsigned UnequalOper = 0;
433 while (UnequalOper != MinOperands &&
434 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
435 // Advance through the type as we go...
437 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
438 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
440 // If all operands equal each other, then the derived pointers must
441 // alias each other...
443 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
444 "Ran out of type nesting, but not out of operands?");
449 // If we have seen all constant operands, and run out of indexes on one of the
450 // getelementptrs, check to see if the tail of the leftover one is all zeros.
451 // If so, return mustalias.
452 if (UnequalOper == MinOperands) {
453 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
455 bool AllAreZeros = true;
456 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
457 if (!isa<Constant>(GEP1Ops[i]) ||
458 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
462 if (AllAreZeros) return MustAlias;
466 // So now we know that the indexes derived from the base pointers,
467 // which are known to alias, are different. We can still determine a
468 // no-alias result if there are differing constant pairs in the index
469 // chain. For example:
470 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
472 unsigned SizeMax = std::max(G1S, G2S);
473 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
475 // Scan for the first operand that is constant and unequal in the
476 // two getelementptrs...
477 unsigned FirstConstantOper = UnequalOper;
478 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
479 const Value *G1Oper = GEP1Ops[FirstConstantOper];
480 const Value *G2Oper = GEP2Ops[FirstConstantOper];
482 if (G1Oper != G2Oper) // Found non-equal constant indexes...
483 if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper)))
484 if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) {
485 if (G1OC->getType() != G2OC->getType()) {
486 // Sign extend both operands to long.
487 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
488 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
489 GEP1Ops[FirstConstantOper] = G1OC;
490 GEP2Ops[FirstConstantOper] = G2OC;
494 // Make sure they are comparable (ie, not constant expressions)...
495 // and make sure the GEP with the smaller leading constant is GEP1.
496 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
497 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
498 if (CV->getValue()) // If they are comparable and G2 > G1
499 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
504 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
507 // No shared constant operands, and we ran out of common operands. At this
508 // point, the GEP instructions have run through all of their operands, and we
509 // haven't found evidence that there are any deltas between the GEP's.
510 // However, one GEP may have more operands than the other. If this is the
511 // case, there may still be hope. Check this now.
512 if (FirstConstantOper == MinOperands) {
513 // Make GEP1Ops be the longer one if there is a longer one.
514 if (GEP1Ops.size() < GEP2Ops.size())
515 std::swap(GEP1Ops, GEP2Ops);
517 // Is there anything to check?
518 if (GEP1Ops.size() > MinOperands) {
519 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
520 if (isa<Constant>(GEP1Ops[i]) && !isa<ConstantExpr>(GEP1Ops[i]) &&
521 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
522 // Yup, there's a constant in the tail. Set all variables to
523 // constants in the GEP instruction to make it suiteable for
524 // TargetData::getIndexedOffset.
525 for (i = 0; i != MaxOperands; ++i)
526 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]))
527 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
528 // Okay, now get the offset. This is the relative offset for the full
530 const TargetData &TD = getTargetData();
531 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
533 // Now crop off any constants from the end...
534 GEP1Ops.resize(MinOperands);
535 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
537 // If the tail provided a bit enough offset, return noalias!
538 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
543 // Couldn't find anything useful.
547 // If there are non-equal constants arguments, then we can figure
548 // out a minimum known delta between the two index expressions... at
549 // this point we know that the first constant index of GEP1 is less
550 // than the first constant index of GEP2.
552 // Advance BasePtr[12]Ty over this first differing constant operand.
553 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
554 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
556 // We are going to be using TargetData::getIndexedOffset to determine the
557 // offset that each of the GEP's is reaching. To do this, we have to convert
558 // all variable references to constant references. To do this, we convert the
559 // initial equal sequence of variables into constant zeros to start with.
560 for (unsigned i = 0; i != FirstConstantOper; ++i) {
561 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) ||
562 !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i]))
563 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
566 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
568 // Loop over the rest of the operands...
569 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
570 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
571 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
572 // If they are equal, use a zero index...
573 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
574 if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1))
575 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
576 // Otherwise, just keep the constants we have.
579 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
580 // If this is an array index, make sure the array element is in range.
581 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
582 if (Op1C->getRawValue() >= AT->getNumElements())
583 return MayAlias; // Be conservative with out-of-range accesses
586 // GEP1 is known to produce a value less than GEP2. To be
587 // conservatively correct, we must assume the largest possible
588 // constant is used in this position. This cannot be the initial
589 // index to the GEP instructions (because we know we have at least one
590 // element before this one with the different constant arguments), so
591 // we know that the current index must be into either a struct or
592 // array. Because we know it's not constant, this cannot be a
593 // structure index. Because of this, we can calculate the maximum
596 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
597 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
602 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
603 // If this is an array index, make sure the array element is in range.
604 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
605 if (Op2C->getRawValue() >= AT->getNumElements())
606 return MayAlias; // Be conservative with out-of-range accesses
607 } else { // Conservatively assume the minimum value for this index
608 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
613 if (BasePtr1Ty && Op1) {
614 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
615 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
620 if (BasePtr2Ty && Op2) {
621 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
622 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
628 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
629 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
630 assert(Offset1 < Offset2 &&"There is at least one different constant here!");
632 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
633 //std::cerr << "Determined that these two GEP's don't alias ["
634 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
641 struct StringCompare {
642 bool operator()(const char *LHS, const char *RHS) {
643 return strcmp(LHS, RHS) < 0;
648 // Note that this list cannot contain libm functions (such as acos and sqrt)
649 // that set errno on a domain or other error.
650 static const char *DoesntAccessMemoryTable[] = {
652 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport",
654 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
655 "trunc", "truncf", "truncl", "ldexp",
657 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
659 "cos", "cosf", "cosl", "cosh", "coshf", "coshl",
660 "exp", "expf", "expl",
662 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl",
663 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
666 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
667 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
670 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
671 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
673 "iswctype", "towctrans", "towlower", "towupper",
677 "isinf", "isnan", "finite",
679 // C99 math functions
680 "copysign", "copysignf", "copysignd",
681 "nexttoward", "nexttowardf", "nexttowardd",
682 "nextafter", "nextafterf", "nextafterd",
685 "__fpclassify", "__fpclassifyf", "__fpclassifyl",
686 "__signbit", "__signbitf", "__signbitl",
689 static const unsigned DAMTableSize =
690 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
692 /// doesNotAccessMemory - Return true if we know that the function does not
693 /// access memory at all. Since basicaa does no analysis, we can only do simple
694 /// things here. In particular, if we have an external function with the name
695 /// of a standard C library function, we are allowed to assume it will be
696 /// resolved by libc, so we can hardcode some entries in here.
697 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
698 if (!F->isExternal()) return false;
700 static bool Initialized = false;
702 // Sort the table the first time through.
703 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
708 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
709 DoesntAccessMemoryTable+DAMTableSize,
710 F->getName().c_str(), StringCompare());
711 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
715 static const char *OnlyReadsMemoryTable[] = {
716 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
717 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
720 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
721 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
725 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
726 "wcsrchr", "wcsspn", "wcsstr",
729 "alphasort", "alphasort64", "versionsort", "versionsort64",
732 "nan", "nanf", "nand",
735 "feof", "ferror", "fileno",
736 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
739 static const unsigned ORMTableSize =
740 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
742 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
743 if (doesNotAccessMemory(F)) return true;
744 if (!F->isExternal()) return false;
746 static bool Initialized = false;
748 // Sort the table the first time through.
749 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
754 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
755 OnlyReadsMemoryTable+ORMTableSize,
756 F->getName().c_str(), StringCompare());
757 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();