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);
85 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
86 return NoAA::getModRefInfo(CS1,CS2);
89 /// hasNoModRefInfoForCalls - We can provide mod/ref information against
90 /// non-escaping allocations.
91 virtual bool hasNoModRefInfoForCalls() const { return false; }
93 /// pointsToConstantMemory - Chase pointers until we find a (constant
95 bool pointsToConstantMemory(const Value *P);
97 virtual bool doesNotAccessMemory(Function *F);
98 virtual bool onlyReadsMemory(Function *F);
101 // CheckGEPInstructions - Check two GEP instructions with known
102 // must-aliasing base pointers. This checks to see if the index expressions
103 // preclude the pointers from aliasing...
105 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
107 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
111 // Register this pass...
112 RegisterOpt<BasicAliasAnalysis>
113 X("basicaa", "Basic Alias Analysis (default AA impl)");
115 // Declare that we implement the AliasAnalysis interface
116 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
117 } // End of anonymous namespace
119 // hasUniqueAddress - Return true if the specified value points to something
120 // with a unique, discernable, address.
121 static inline bool hasUniqueAddress(const Value *V) {
122 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
125 // getUnderlyingObject - This traverses the use chain to figure out what object
126 // the specified value points to. If the value points to, or is derived from, a
127 // unique object or an argument, return it.
128 static const Value *getUnderlyingObject(const Value *V) {
129 if (!isa<PointerType>(V->getType())) return 0;
131 // If we are at some type of object... return it.
132 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
134 // Traverse through different addressing mechanisms...
135 if (const Instruction *I = dyn_cast<Instruction>(V)) {
136 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
137 return getUnderlyingObject(I->getOperand(0));
138 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
139 if (CE->getOpcode() == Instruction::Cast ||
140 CE->getOpcode() == Instruction::GetElementPtr)
141 return getUnderlyingObject(CE->getOperand(0));
142 } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
148 static const User *isGEP(const Value *V) {
149 if (isa<GetElementPtrInst>(V) ||
150 (isa<ConstantExpr>(V) &&
151 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
152 return cast<User>(V);
156 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
157 assert(GEPOps.empty() && "Expect empty list to populate!");
158 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
159 cast<User>(V)->op_end());
161 // Accumulate all of the chained indexes into the operand array
162 V = cast<User>(V)->getOperand(0);
164 while (const User *G = isGEP(V)) {
165 if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
166 !cast<Constant>(GEPOps[0])->isNullValue())
167 break; // Don't handle folding arbitrary pointer offsets yet...
168 GEPOps.erase(GEPOps.begin()); // Drop the zero index
169 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
170 V = G->getOperand(0);
175 /// pointsToConstantMemory - Chase pointers until we find a (constant
177 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
178 if (const Value *V = getUnderlyingObject(P))
179 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
180 return GV->isConstant();
184 static bool AddressMightEscape(const Value *V) {
185 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
187 const Instruction *I = cast<Instruction>(*UI);
188 switch (I->getOpcode()) {
189 case Instruction::Load: break;
190 case Instruction::Store:
191 if (I->getOperand(0) == V)
192 return true; // Escapes if the pointer is stored.
194 case Instruction::GetElementPtr:
195 if (AddressMightEscape(I)) return true;
197 case Instruction::Cast:
198 if (!isa<PointerType>(I->getType()))
200 if (AddressMightEscape(I)) return true;
202 case Instruction::Ret:
203 // If returned, the address will escape to calling functions, but no
204 // callees could modify it.
213 // getModRefInfo - Check to see if the specified callsite can clobber the
214 // specified memory object. Since we only look at local properties of this
215 // function, we really can't say much about this query. We do, however, use
216 // simple "address taken" analysis on local objects.
218 AliasAnalysis::ModRefResult
219 BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
220 if (!isa<Constant>(P))
221 if (const AllocationInst *AI =
222 dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) {
223 // Okay, the pointer is to a stack allocated object. If we can prove that
224 // the pointer never "escapes", then we know the call cannot clobber it,
225 // because it simply can't get its address.
226 if (!AddressMightEscape(AI))
230 // The AliasAnalysis base class has some smarts, lets use them.
231 return AliasAnalysis::getModRefInfo(CS, P, Size);
234 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
235 // as array references. Note that this function is heavily tail recursive.
236 // Hopefully we have a smart C++ compiler. :)
238 AliasAnalysis::AliasResult
239 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
240 const Value *V2, unsigned V2Size) {
241 // Strip off any constant expression casts if they exist
242 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1))
243 if (CE->getOpcode() == Instruction::Cast &&
244 isa<PointerType>(CE->getOperand(0)->getType()))
245 V1 = CE->getOperand(0);
246 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
247 if (CE->getOpcode() == Instruction::Cast &&
248 isa<PointerType>(CE->getOperand(0)->getType()))
249 V2 = CE->getOperand(0);
251 // Are we checking for alias of the same value?
252 if (V1 == V2) return MustAlias;
254 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
255 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
256 return NoAlias; // Scalars cannot alias each other
258 // Strip off cast instructions...
259 if (const Instruction *I = dyn_cast<CastInst>(V1))
260 if (isa<PointerType>(I->getOperand(0)->getType()))
261 return alias(I->getOperand(0), V1Size, V2, V2Size);
262 if (const Instruction *I = dyn_cast<CastInst>(V2))
263 if (isa<PointerType>(I->getOperand(0)->getType()))
264 return alias(V1, V1Size, I->getOperand(0), V2Size);
266 // Figure out what objects these things are pointing to if we can...
267 const Value *O1 = getUnderlyingObject(V1);
268 const Value *O2 = getUnderlyingObject(V2);
270 // Pointing at a discernible object?
273 if (isa<Argument>(O1)) {
274 // Incoming argument cannot alias locally allocated object!
275 if (isa<AllocationInst>(O2)) return NoAlias;
276 // Otherwise, nothing is known...
277 } else if (isa<Argument>(O2)) {
278 // Incoming argument cannot alias locally allocated object!
279 if (isa<AllocationInst>(O1)) return NoAlias;
280 // Otherwise, nothing is known...
281 } else if (O1 != O2) {
282 // If they are two different objects, we know that we have no alias...
286 // If they are the same object, they we can look at the indexes. If they
287 // index off of the object is the same for both pointers, they must alias.
288 // If they are provably different, they must not alias. Otherwise, we
289 // can't tell anything.
293 if (!isa<Argument>(O1) && isa<ConstantPointerNull>(V2))
294 return NoAlias; // Unique values don't alias null
296 if (isa<GlobalVariable>(O1) || isa<AllocationInst>(O1))
297 if (cast<PointerType>(O1->getType())->getElementType()->isSized()) {
298 // If the size of the other access is larger than the total size of the
299 // global/alloca/malloc, it cannot be accessing the global (it's
300 // undefined to load or store bytes before or after an object).
301 const Type *ElTy = cast<PointerType>(O1->getType())->getElementType();
302 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
303 if (GlobalSize < V2Size && V2Size != ~0U)
309 if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1))
310 return NoAlias; // Unique values don't alias null
312 if (isa<GlobalVariable>(O2) || isa<AllocationInst>(O2))
313 if (cast<PointerType>(O2->getType())->getElementType()->isSized()) {
314 // If the size of the other access is larger than the total size of the
315 // global/alloca/malloc, it cannot be accessing the object (it's
316 // undefined to load or store bytes before or after an object).
317 const Type *ElTy = cast<PointerType>(O2->getType())->getElementType();
318 unsigned GlobalSize = getTargetData().getTypeSize(ElTy);
319 if (GlobalSize < V1Size && V1Size != ~0U)
324 // If we have two gep instructions with must-alias'ing base pointers, figure
325 // out if the indexes to the GEP tell us anything about the derived pointer.
326 // Note that we also handle chains of getelementptr instructions as well as
327 // constant expression getelementptrs here.
329 if (isGEP(V1) && isGEP(V2)) {
330 // Drill down into the first non-gep value, to test for must-aliasing of
331 // the base pointers.
332 const Value *BasePtr1 = V1, *BasePtr2 = V2;
334 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
335 } while (isGEP(BasePtr1) &&
336 cast<User>(BasePtr1)->getOperand(1) ==
337 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
339 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
340 } while (isGEP(BasePtr2) &&
341 cast<User>(BasePtr2)->getOperand(1) ==
342 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
344 // Do the base pointers alias?
345 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
346 if (BaseAlias == NoAlias) return NoAlias;
347 if (BaseAlias == MustAlias) {
348 // If the base pointers alias each other exactly, check to see if we can
349 // figure out anything about the resultant pointers, to try to prove
352 // Collect all of the chained GEP operands together into one simple place
353 std::vector<Value*> GEP1Ops, GEP2Ops;
354 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
355 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
357 // If GetGEPOperands were able to fold to the same must-aliased pointer,
358 // do the comparison.
359 if (BasePtr1 == BasePtr2) {
361 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
362 BasePtr2->getType(), GEP2Ops, V2Size);
363 if (GAlias != MayAlias)
369 // Check to see if these two pointers are related by a getelementptr
370 // instruction. If one pointer is a GEP with a non-zero index of the other
371 // pointer, we know they cannot alias.
375 std::swap(V1Size, V2Size);
378 if (V1Size != ~0U && V2Size != ~0U)
379 if (const User *GEP = isGEP(V1)) {
380 std::vector<Value*> GEPOperands;
381 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
383 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
384 if (R == MustAlias) {
385 // If there is at least one non-zero constant index, we know they cannot
387 bool ConstantFound = false;
388 bool AllZerosFound = true;
389 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
390 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
391 if (!C->isNullValue()) {
392 ConstantFound = true;
393 AllZerosFound = false;
397 AllZerosFound = false;
400 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
401 // the ptr, the end result is a must alias also.
406 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
409 // Otherwise we have to check to see that the distance is more than
410 // the size of the argument... build an index vector that is equal to
411 // the arguments provided, except substitute 0's for any variable
412 // indexes we find...
413 if (cast<PointerType>(
414 BasePtr->getType())->getElementType()->isSized()) {
415 for (unsigned i = 0; i != GEPOperands.size(); ++i)
416 if (!isa<ConstantInt>(GEPOperands[i]))
418 Constant::getNullValue(GEPOperands[i]->getType());
420 getTargetData().getIndexedOffset(BasePtr->getType(), GEPOperands);
422 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
432 static bool ValuesEqual(Value *V1, Value *V2) {
433 if (V1->getType() == V2->getType())
435 if (Constant *C1 = dyn_cast<Constant>(V1))
436 if (Constant *C2 = dyn_cast<Constant>(V2)) {
437 // Sign extend the constants to long types.
438 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
439 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
445 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
446 /// base pointers. This checks to see if the index expressions preclude the
447 /// pointers from aliasing...
448 AliasAnalysis::AliasResult BasicAliasAnalysis::
449 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
451 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
453 // We currently can't handle the case when the base pointers have different
454 // primitive types. Since this is uncommon anyway, we are happy being
455 // extremely conservative.
456 if (BasePtr1Ty != BasePtr2Ty)
459 const Type *GEPPointerTy = BasePtr1Ty;
461 // Find the (possibly empty) initial sequence of equal values... which are not
462 // necessarily constants.
463 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
464 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
465 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
466 unsigned UnequalOper = 0;
467 while (UnequalOper != MinOperands &&
468 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
469 // Advance through the type as we go...
471 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
472 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
474 // If all operands equal each other, then the derived pointers must
475 // alias each other...
477 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
478 "Ran out of type nesting, but not out of operands?");
483 // If we have seen all constant operands, and run out of indexes on one of the
484 // getelementptrs, check to see if the tail of the leftover one is all zeros.
485 // If so, return mustalias.
486 if (UnequalOper == MinOperands) {
487 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
489 bool AllAreZeros = true;
490 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
491 if (!isa<Constant>(GEP1Ops[i]) ||
492 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
496 if (AllAreZeros) return MustAlias;
500 // So now we know that the indexes derived from the base pointers,
501 // which are known to alias, are different. We can still determine a
502 // no-alias result if there are differing constant pairs in the index
503 // chain. For example:
504 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
506 unsigned SizeMax = std::max(G1S, G2S);
507 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work.
509 // Scan for the first operand that is constant and unequal in the
510 // two getelementptrs...
511 unsigned FirstConstantOper = UnequalOper;
512 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
513 const Value *G1Oper = GEP1Ops[FirstConstantOper];
514 const Value *G2Oper = GEP2Ops[FirstConstantOper];
516 if (G1Oper != G2Oper) // Found non-equal constant indexes...
517 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper)))
518 if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){
519 if (G1OC->getType() != G2OC->getType()) {
520 // Sign extend both operands to long.
521 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
522 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
523 GEP1Ops[FirstConstantOper] = G1OC;
524 GEP2Ops[FirstConstantOper] = G2OC;
528 // Make sure they are comparable (ie, not constant expressions), and
529 // make sure the GEP with the smaller leading constant is GEP1.
530 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
531 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
532 if (CV->getValue()) // If they are comparable and G2 > G1
533 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
538 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
541 // No shared constant operands, and we ran out of common operands. At this
542 // point, the GEP instructions have run through all of their operands, and we
543 // haven't found evidence that there are any deltas between the GEP's.
544 // However, one GEP may have more operands than the other. If this is the
545 // case, there may still be hope. Check this now.
546 if (FirstConstantOper == MinOperands) {
547 // Make GEP1Ops be the longer one if there is a longer one.
548 if (GEP1Ops.size() < GEP2Ops.size())
549 std::swap(GEP1Ops, GEP2Ops);
551 // Is there anything to check?
552 if (GEP1Ops.size() > MinOperands) {
553 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
554 if (isa<ConstantInt>(GEP1Ops[i]) &&
555 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
556 // Yup, there's a constant in the tail. Set all variables to
557 // constants in the GEP instruction to make it suiteable for
558 // TargetData::getIndexedOffset.
559 for (i = 0; i != MaxOperands; ++i)
560 if (!isa<ConstantInt>(GEP1Ops[i]))
561 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
562 // Okay, now get the offset. This is the relative offset for the full
564 const TargetData &TD = getTargetData();
565 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
567 // Now crop off any constants from the end...
568 GEP1Ops.resize(MinOperands);
569 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
571 // If the tail provided a bit enough offset, return noalias!
572 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
577 // Couldn't find anything useful.
581 // If there are non-equal constants arguments, then we can figure
582 // out a minimum known delta between the two index expressions... at
583 // this point we know that the first constant index of GEP1 is less
584 // than the first constant index of GEP2.
586 // Advance BasePtr[12]Ty over this first differing constant operand.
587 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
588 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
590 // We are going to be using TargetData::getIndexedOffset to determine the
591 // offset that each of the GEP's is reaching. To do this, we have to convert
592 // all variable references to constant references. To do this, we convert the
593 // initial equal sequence of variables into constant zeros to start with.
594 for (unsigned i = 0; i != FirstConstantOper; ++i)
595 if (!isa<ConstantInt>(GEP1Ops[i]) || !isa<ConstantInt>(GEP2Ops[i]))
596 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
598 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
600 // Loop over the rest of the operands...
601 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
602 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
603 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
604 // If they are equal, use a zero index...
605 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
606 if (!isa<ConstantInt>(Op1))
607 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
608 // Otherwise, just keep the constants we have.
611 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
612 // If this is an array index, make sure the array element is in range.
613 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
614 if (Op1C->getRawValue() >= AT->getNumElements())
615 return MayAlias; // Be conservative with out-of-range accesses
618 // GEP1 is known to produce a value less than GEP2. To be
619 // conservatively correct, we must assume the largest possible
620 // constant is used in this position. This cannot be the initial
621 // index to the GEP instructions (because we know we have at least one
622 // element before this one with the different constant arguments), so
623 // we know that the current index must be into either a struct or
624 // array. Because we know it's not constant, this cannot be a
625 // structure index. Because of this, we can calculate the maximum
628 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
629 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
634 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
635 // If this is an array index, make sure the array element is in range.
636 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
637 if (Op2C->getRawValue() >= AT->getNumElements())
638 return MayAlias; // Be conservative with out-of-range accesses
639 } else { // Conservatively assume the minimum value for this index
640 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
645 if (BasePtr1Ty && Op1) {
646 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
647 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
652 if (BasePtr2Ty && Op2) {
653 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
654 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
660 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
661 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
662 assert(Offset1 < Offset2 &&"There is at least one different constant here!");
664 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
665 //std::cerr << "Determined that these two GEP's don't alias ["
666 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
673 struct StringCompare {
674 bool operator()(const char *LHS, const char *RHS) {
675 return strcmp(LHS, RHS) < 0;
680 // Note that this list cannot contain libm functions (such as acos and sqrt)
681 // that set errno on a domain or other error.
682 static const char *DoesntAccessMemoryTable[] = {
684 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered",
686 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
687 "trunc", "truncf", "truncl", "ldexp",
689 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
691 "cos", "cosf", "cosl", "cosh", "coshf", "coshl",
692 "exp", "expf", "expl",
694 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl",
695 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
698 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
699 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
702 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
703 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
705 "iswctype", "towctrans", "towlower", "towupper",
709 "isinf", "isnan", "finite",
711 // C99 math functions
712 "copysign", "copysignf", "copysignd",
713 "nexttoward", "nexttowardf", "nexttowardd",
714 "nextafter", "nextafterf", "nextafterd",
717 "__fpclassify", "__fpclassifyf", "__fpclassifyl",
718 "__signbit", "__signbitf", "__signbitl",
721 static const unsigned DAMTableSize =
722 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
724 /// doesNotAccessMemory - Return true if we know that the function does not
725 /// access memory at all. Since basicaa does no analysis, we can only do simple
726 /// things here. In particular, if we have an external function with the name
727 /// of a standard C library function, we are allowed to assume it will be
728 /// resolved by libc, so we can hardcode some entries in here.
729 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
730 if (!F->isExternal()) return false;
732 static bool Initialized = false;
734 // Sort the table the first time through.
735 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
740 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
741 DoesntAccessMemoryTable+DAMTableSize,
742 F->getName().c_str(), StringCompare());
743 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
747 static const char *OnlyReadsMemoryTable[] = {
748 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
749 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
752 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
753 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
757 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
758 "wcsrchr", "wcsspn", "wcsstr",
761 "alphasort", "alphasort64", "versionsort", "versionsort64",
764 "nan", "nanf", "nand",
767 "feof", "ferror", "fileno",
768 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
771 static const unsigned ORMTableSize =
772 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
774 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
775 if (doesNotAccessMemory(F)) return true;
776 if (!F->isExternal()) return false;
778 static bool Initialized = false;
780 // Sort the table the first time through.
781 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
786 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
787 OnlyReadsMemoryTable+ORMTableSize,
788 F->getName().c_str(), StringCompare());
789 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();