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/Constants.h"
18 #include "llvm/DerivedTypes.h"
19 #include "llvm/Function.h"
20 #include "llvm/GlobalVariable.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/Pass.h"
23 #include "llvm/Target/TargetData.h"
24 #include "llvm/Support/GetElementPtrTypeIterator.h"
28 // Make sure that anything that uses AliasAnalysis pulls in this file...
29 void llvm::BasicAAStub() {}
32 /// NoAA - This class implements the -no-aa pass, which always returns "I
33 /// don't know" for alias queries. NoAA is unlike other alias analysis
34 /// implementations, in that it does not chain to a previous analysis. As
35 /// such it doesn't follow many of the rules that other alias analyses must.
37 struct NoAA : public ImmutablePass, public AliasAnalysis {
38 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
39 AU.addRequired<TargetData>();
42 virtual void initializePass() {
43 TD = &getAnalysis<TargetData>();
46 virtual AliasResult alias(const Value *V1, unsigned V1Size,
47 const Value *V2, unsigned V2Size) {
51 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
52 virtual bool pointsToConstantMemory(const Value *P) { return false; }
53 virtual bool doesNotAccessMemory(Function *F) { return false; }
54 virtual bool onlyReadsMemory(Function *F) { return false; }
55 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
58 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
61 virtual bool hasNoModRefInfoForCalls() const { return true; }
63 virtual void deleteValue(Value *V) {}
64 virtual void copyValue(Value *From, Value *To) {}
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 AliasResult alias(const Value *V1, unsigned V1Size,
82 const Value *V2, unsigned V2Size);
84 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
86 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
87 /// non-escaping allocations.
88 virtual bool hasNoModRefInfoForCalls() const { return false; }
90 /// pointsToConstantMemory - Chase pointers until we find a (constant
92 bool pointsToConstantMemory(const Value *P);
94 virtual bool doesNotAccessMemory(Function *F);
95 virtual bool onlyReadsMemory(Function *F);
98 // CheckGEPInstructions - Check two GEP instructions with known
99 // must-aliasing base pointers. This checks to see if the index expressions
100 // preclude the pointers from aliasing...
102 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
104 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
108 // Register this pass...
109 RegisterOpt<BasicAliasAnalysis>
110 X("basicaa", "Basic Alias Analysis (default AA impl)");
112 // Declare that we implement the AliasAnalysis interface
113 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
114 } // End of anonymous namespace
116 // hasUniqueAddress - Return true if the specified value points to something
117 // with a unique, discernable, address.
118 static inline bool hasUniqueAddress(const Value *V) {
119 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
122 // getUnderlyingObject - This traverses the use chain to figure out what object
123 // the specified value points to. If the value points to, or is derived from, a
124 // unique object or an argument, return it.
125 static const Value *getUnderlyingObject(const Value *V) {
126 if (!isa<PointerType>(V->getType())) return 0;
128 // If we are at some type of object... return it.
129 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
131 // Traverse through different addressing mechanisms...
132 if (const Instruction *I = dyn_cast<Instruction>(V)) {
133 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
134 return getUnderlyingObject(I->getOperand(0));
135 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
136 if (CE->getOpcode() == Instruction::Cast ||
137 CE->getOpcode() == Instruction::GetElementPtr)
138 return getUnderlyingObject(CE->getOperand(0));
139 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
145 static const User *isGEP(const Value *V) {
146 if (isa<GetElementPtrInst>(V) ||
147 (isa<ConstantExpr>(V) &&
148 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
149 return cast<User>(V);
153 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
154 assert(GEPOps.empty() && "Expect empty list to populate!");
155 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
156 cast<User>(V)->op_end());
158 // Accumulate all of the chained indexes into the operand array
159 V = cast<User>(V)->getOperand(0);
161 while (const User *G = isGEP(V)) {
162 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
163 !cast<Constant>(GEPOps[0])->isNullValue())
164 break; // Don't handle folding arbitrary pointer offsets yet...
165 GEPOps.erase(GEPOps.begin()); // Drop the zero index
166 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
167 V = G->getOperand(0);
172 /// pointsToConstantMemory - Chase pointers until we find a (constant
174 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
175 if (const Value *V = getUnderlyingObject(P))
176 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
177 return GV->isConstant();
181 static bool AddressMightEscape(const Value *V) {
182 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
184 const Instruction *I = cast<Instruction>(*UI);
185 switch (I->getOpcode()) {
186 case Instruction::Load: break;
187 case Instruction::Store:
188 if (I->getOperand(0) == V)
189 return true; // Escapes if the pointer is stored.
191 case Instruction::GetElementPtr:
192 if (AddressMightEscape(I)) return true;
194 case Instruction::Cast:
195 if (!isa<PointerType>(I->getType()))
197 if (AddressMightEscape(I)) return true;
199 case Instruction::Ret:
200 // If returned, the address will escape to calling functions, but no
201 // callees could modify it.
210 // getModRefInfo - Check to see if the specified callsite can clobber the
211 // specified memory object. Since we only look at local properties of this
212 // function, we really can't say much about this query. We do, however, use
213 // simple "address taken" analysis on local objects.
215 AliasAnalysis::ModRefResult
216 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
217 if (!isa<Constant>(P))
218 if (const AllocationInst *AI =
219 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
220 // Okay, the pointer is to a stack allocated object. If we can prove that
221 // the pointer never "escapes", then we know the call cannot clobber it,
222 // because it simply can't get its address.
223 if (!AddressMightEscape(AI))
227 // The AliasAnalysis base class has some smarts, lets use them.
228 return AliasAnalysis::getModRefInfo(CS, P, Size);
231 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
232 // as array references. Note that this function is heavily tail recursive.
233 // Hopefully we have a smart C++ compiler. :)
235 AliasAnalysis::AliasResult
236 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
237 const Value *V2, unsigned V2Size) {
238 // Strip off any constant expression casts if they exist
239 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
240 if (CE->getOpcode() == Instruction::Cast &&
241 isa<PointerType>(CE->getOperand(0)->getType()))
242 V1 = CE->getOperand(0);
243 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
244 if (CE->getOpcode() == Instruction::Cast &&
245 isa<PointerType>(CE->getOperand(0)->getType()))
246 V2 = CE->getOperand(0);
248 // Are we checking for alias of the same value?
249 if (V1 == V2) return MustAlias;
251 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
252 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
253 return NoAlias; // Scalars cannot alias each other
255 // Strip off cast instructions...
256 if (const Instruction *I = dyn_cast<CastInst>(V1))
257 if (isa<PointerType>(I->getOperand(0)->getType()))
258 return alias(I->getOperand(0), V1Size, V2, V2Size);
259 if (const Instruction *I = dyn_cast<CastInst>(V2))
260 if (isa<PointerType>(I->getOperand(0)->getType()))
261 return alias(V1, V1Size, I->getOperand(0), V2Size);
263 // Figure out what objects these things are pointing to if we can...
264 const Value *O1 = getUnderlyingObject(V1);
265 const Value *O2 = getUnderlyingObject(V2);
267 // Pointing at a discernible object?
269 if (isa<Argument>(O1)) {
270 // Incoming argument cannot alias locally allocated object!
271 if (isa<AllocationInst>(O2)) return NoAlias;
272 // Otherwise, nothing is known...
273 } else if (isa<Argument>(O2)) {
274 // Incoming argument cannot alias locally allocated object!
275 if (isa<AllocationInst>(O1)) return NoAlias;
276 // Otherwise, nothing is known...
278 // If they are two different objects, we know that we have no alias...
279 if (O1 != O2) return NoAlias;
282 // If they are the same object, they we can look at the indexes. If they
283 // index off of the object is the same for both pointers, they must alias.
284 // If they are provably different, they must not alias. Otherwise, we can't
286 } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
287 return NoAlias; // Unique values don't alias null
288 } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
289 return NoAlias; // Unique values don't alias null
292 // If we have two gep instructions with must-alias'ing base pointers, figure
293 // out if the indexes to the GEP tell us anything about the derived pointer.
294 // Note that we also handle chains of getelementptr instructions as well as
295 // constant expression getelementptrs here.
297 if (isGEP(V1) && isGEP(V2)) {
298 // Drill down into the first non-gep value, to test for must-aliasing of
299 // the base pointers.
300 const Value *BasePtr1 = V1, *BasePtr2 = V2;
302 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
303 } while (isGEP(BasePtr1) &&
304 cast<User>(BasePtr1)->getOperand(1) ==
305 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
307 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
308 } while (isGEP(BasePtr2) &&
309 cast<User>(BasePtr2)->getOperand(1) ==
310 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
312 // Do the base pointers alias?
313 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
314 if (BaseAlias == NoAlias) return NoAlias;
315 if (BaseAlias == MustAlias) {
316 // If the base pointers alias each other exactly, check to see if we can
317 // figure out anything about the resultant pointers, to try to prove
320 // Collect all of the chained GEP operands together into one simple place
321 std::vector<Value*> GEP1Ops, GEP2Ops;
322 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
323 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
325 // If GetGEPOperands were able to fold to the same must-aliased pointer,
326 // do the comparison.
327 if (BasePtr1 == BasePtr2) {
329 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
330 BasePtr2->getType(), GEP2Ops, V2Size);
331 if (GAlias != MayAlias)
337 // Check to see if these two pointers are related by a getelementptr
338 // instruction. If one pointer is a GEP with a non-zero index of the other
339 // pointer, we know they cannot alias.
343 std::swap(V1Size, V2Size);
346 if (V1Size != ~0U && V2Size != ~0U)
347 if (const User *GEP = isGEP(V1)) {
348 std::vector<Value*> GEPOperands;
349 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
351 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
352 if (R == MustAlias) {
353 // If there is at least one non-zero constant index, we know they cannot
355 bool ConstantFound = false;
356 bool AllZerosFound = true;
357 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
358 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
359 if (!C->isNullValue()) {
360 ConstantFound = true;
361 AllZerosFound = false;
365 AllZerosFound = false;
368 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
369 // the ptr, the end result is a must alias also.
374 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
377 // Otherwise we have to check to see that the distance is more than
378 // the size of the argument... build an index vector that is equal to
379 // the arguments provided, except substitute 0's for any variable
380 // indexes we find...
381 for (unsigned i = 0; i != GEPOperands.size(); ++i)
382 if (!isa<Constant>(GEPOperands[i]) || isa<GlobalValue>(GEPOperands[i]) ||
383 isa<ConstantExpr>(GEPOperands[i]))
384 GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType());
385 int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(),
387 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
396 static bool ValuesEqual(Value *V1, Value *V2) {
397 if (V1->getType() == V2->getType())
399 if (Constant *C1 = dyn_cast<Constant>(V1))
400 if (Constant *C2 = dyn_cast<Constant>(V2)) {
401 // Sign extend the constants to long types.
402 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
403 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
409 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
410 /// base pointers. This checks to see if the index expressions preclude the
411 /// pointers from aliasing...
412 AliasAnalysis::AliasResult BasicAliasAnalysis::
413 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
415 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
417 // We currently can't handle the case when the base pointers have different
418 // primitive types. Since this is uncommon anyway, we are happy being
419 // extremely conservative.
420 if (BasePtr1Ty != BasePtr2Ty)
423 const Type *GEPPointerTy = BasePtr1Ty;
425 // Find the (possibly empty) initial sequence of equal values... which are not
426 // necessarily constants.
427 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
428 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
429 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
430 unsigned UnequalOper = 0;
431 while (UnequalOper != MinOperands &&
432 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
433 // Advance through the type as we go...
435 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
436 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
438 // If all operands equal each other, then the derived pointers must
439 // alias each other...
441 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
442 "Ran out of type nesting, but not out of operands?");
447 // If we have seen all constant operands, and run out of indexes on one of the
448 // getelementptrs, check to see if the tail of the leftover one is all zeros.
449 // If so, return mustalias.
450 if (UnequalOper == MinOperands) {
451 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
453 bool AllAreZeros = true;
454 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
455 if (!isa<Constant>(GEP1Ops[i]) ||
456 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
460 if (AllAreZeros) return MustAlias;
464 // So now we know that the indexes derived from the base pointers,
465 // which are known to alias, are different. We can still determine a
466 // no-alias result if there are differing constant pairs in the index
467 // chain. For example:
468 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
470 unsigned SizeMax = std::max(G1S, G2S);
471 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
473 // Scan for the first operand that is constant and unequal in the
474 // two getelementptrs...
475 unsigned FirstConstantOper = UnequalOper;
476 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
477 const Value *G1Oper = GEP1Ops[FirstConstantOper];
478 const Value *G2Oper = GEP2Ops[FirstConstantOper];
480 if (G1Oper != G2Oper) // Found non-equal constant indexes...
481 if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper)))
482 if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) {
483 if (G1OC->getType() != G2OC->getType()) {
484 // Sign extend both operands to long.
485 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
486 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
487 GEP1Ops[FirstConstantOper] = G1OC;
488 GEP2Ops[FirstConstantOper] = G2OC;
492 // Make sure they are comparable (ie, not constant expressions)...
493 // and make sure the GEP with the smaller leading constant is GEP1.
494 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
495 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
496 if (CV->getValue()) // If they are comparable and G2 > G1
497 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
502 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
505 // No shared constant operands, and we ran out of common operands. At this
506 // point, the GEP instructions have run through all of their operands, and we
507 // haven't found evidence that there are any deltas between the GEP's.
508 // However, one GEP may have more operands than the other. If this is the
509 // case, there may still be hope. Check this now.
510 if (FirstConstantOper == MinOperands) {
511 // Make GEP1Ops be the longer one if there is a longer one.
512 if (GEP1Ops.size() < GEP2Ops.size())
513 std::swap(GEP1Ops, GEP2Ops);
515 // Is there anything to check?
516 if (GEP1Ops.size() > MinOperands) {
517 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
518 if (isa<ConstantInt>(GEP1Ops[i]) &&
519 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
520 // Yup, there's a constant in the tail. Set all variables to
521 // constants in the GEP instruction to make it suiteable for
522 // TargetData::getIndexedOffset.
523 for (i = 0; i != MaxOperands; ++i)
524 if (!isa<ConstantInt>(GEP1Ops[i]))
525 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
526 // Okay, now get the offset. This is the relative offset for the full
528 const TargetData &TD = getTargetData();
529 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
531 // Now crop off any constants from the end...
532 GEP1Ops.resize(MinOperands);
533 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
535 // If the tail provided a bit enough offset, return noalias!
536 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
541 // Couldn't find anything useful.
545 // If there are non-equal constants arguments, then we can figure
546 // out a minimum known delta between the two index expressions... at
547 // this point we know that the first constant index of GEP1 is less
548 // than the first constant index of GEP2.
550 // Advance BasePtr[12]Ty over this first differing constant operand.
551 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
552 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
554 // We are going to be using TargetData::getIndexedOffset to determine the
555 // offset that each of the GEP's is reaching. To do this, we have to convert
556 // all variable references to constant references. To do this, we convert the
557 // initial equal sequence of variables into constant zeros to start with.
558 for (unsigned i = 0; i != FirstConstantOper; ++i) {
559 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) ||
560 !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i]))
561 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
564 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
566 // Loop over the rest of the operands...
567 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
568 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
569 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
570 // If they are equal, use a zero index...
571 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
572 if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1))
573 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
574 // Otherwise, just keep the constants we have.
577 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
578 // If this is an array index, make sure the array element is in range.
579 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
580 if (Op1C->getRawValue() >= AT->getNumElements())
581 return MayAlias; // Be conservative with out-of-range accesses
584 // GEP1 is known to produce a value less than GEP2. To be
585 // conservatively correct, we must assume the largest possible
586 // constant is used in this position. This cannot be the initial
587 // index to the GEP instructions (because we know we have at least one
588 // element before this one with the different constant arguments), so
589 // we know that the current index must be into either a struct or
590 // array. Because we know it's not constant, this cannot be a
591 // structure index. Because of this, we can calculate the maximum
594 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
595 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
600 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
601 // If this is an array index, make sure the array element is in range.
602 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
603 if (Op2C->getRawValue() >= AT->getNumElements())
604 return MayAlias; // Be conservative with out-of-range accesses
605 } else { // Conservatively assume the minimum value for this index
606 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
611 if (BasePtr1Ty && Op1) {
612 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
613 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
618 if (BasePtr2Ty && Op2) {
619 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
620 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
626 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
627 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
628 assert(Offset1 < Offset2 &&"There is at least one different constant here!");
630 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
631 //std::cerr << "Determined that these two GEP's don't alias ["
632 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
639 struct StringCompare {
640 bool operator()(const char *LHS, const char *RHS) {
641 return strcmp(LHS, RHS) < 0;
646 // Note that this list cannot contain libm functions (such as acos and sqrt)
647 // that set errno on a domain or other error.
648 static const char *DoesntAccessMemoryTable[] = {
650 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered",
652 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
653 "trunc", "truncf", "truncl", "ldexp",
655 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
657 "cos", "cosf", "cosl", "cosh", "coshf", "coshl",
658 "exp", "expf", "expl",
660 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl",
661 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
664 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
665 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
668 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
669 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
671 "iswctype", "towctrans", "towlower", "towupper",
675 "isinf", "isnan", "finite",
677 // C99 math functions
678 "copysign", "copysignf", "copysignd",
679 "nexttoward", "nexttowardf", "nexttowardd",
680 "nextafter", "nextafterf", "nextafterd",
683 "__fpclassify", "__fpclassifyf", "__fpclassifyl",
684 "__signbit", "__signbitf", "__signbitl",
687 static const unsigned DAMTableSize =
688 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
690 /// doesNotAccessMemory - Return true if we know that the function does not
691 /// access memory at all. Since basicaa does no analysis, we can only do simple
692 /// things here. In particular, if we have an external function with the name
693 /// of a standard C library function, we are allowed to assume it will be
694 /// resolved by libc, so we can hardcode some entries in here.
695 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
696 if (!F->isExternal()) return false;
698 static bool Initialized = false;
700 // Sort the table the first time through.
701 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
706 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
707 DoesntAccessMemoryTable+DAMTableSize,
708 F->getName().c_str(), StringCompare());
709 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
713 static const char *OnlyReadsMemoryTable[] = {
714 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
715 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
718 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
719 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
723 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
724 "wcsrchr", "wcsspn", "wcsstr",
727 "alphasort", "alphasort64", "versionsort", "versionsort64",
730 "nan", "nanf", "nand",
733 "feof", "ferror", "fileno",
734 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
737 static const unsigned ORMTableSize =
738 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
740 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
741 if (doesNotAccessMemory(F)) return true;
742 if (!F->isExternal()) return false;
744 static bool Initialized = false;
746 // Sort the table the first time through.
747 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
752 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
753 OnlyReadsMemoryTable+ORMTableSize,
754 F->getName().c_str(), StringCompare());
755 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();