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 void getAnalysisUsage(AnalysisUsage &AU) const {
46 AU.addRequired<TargetData>();
49 virtual void initializePass() {
50 TD = &getAnalysis<TargetData>();
53 virtual AliasResult alias(const Value *V1, unsigned V1Size,
54 const Value *V2, unsigned V2Size) {
58 virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
59 virtual bool pointsToConstantMemory(const Value *P) { return false; }
60 virtual bool doesNotAccessMemory(Function *F) { return false; }
61 virtual bool onlyReadsMemory(Function *F) { return false; }
62 virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
65 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
68 virtual bool hasNoModRefInfoForCalls() const { return true; }
70 virtual void deleteValue(Value *V) {}
71 virtual void copyValue(Value *From, Value *To) {}
74 // Register this pass...
76 U("no-aa", "No Alias Analysis (always returns 'may' alias)");
78 // Declare that we implement the AliasAnalysis interface
79 RegisterAnalysisGroup<AliasAnalysis, NoAA> V;
80 } // End of anonymous namespace
84 /// BasicAliasAnalysis - This is the default alias analysis implementation.
85 /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
86 /// derives from the NoAA class.
87 struct BasicAliasAnalysis : public NoAA {
88 AliasResult alias(const Value *V1, unsigned V1Size,
89 const Value *V2, unsigned V2Size);
91 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
93 /// hasNoModRefInfoForCalls - We have no way to test one call against
94 /// another, unless they are pure or const.
95 virtual bool hasNoModRefInfoForCalls() const { return true; }
97 /// pointsToConstantMemory - Chase pointers until we find a (constant
99 bool pointsToConstantMemory(const Value *P);
101 virtual bool doesNotAccessMemory(Function *F);
102 virtual bool onlyReadsMemory(Function *F);
105 // CheckGEPInstructions - Check two GEP instructions with known
106 // must-aliasing base pointers. This checks to see if the index expressions
107 // preclude the pointers from aliasing...
109 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
111 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
115 // Register this pass...
116 RegisterOpt<BasicAliasAnalysis>
117 X("basicaa", "Basic Alias Analysis (default AA impl)");
119 // Declare that we implement the AliasAnalysis interface
120 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
121 } // End of anonymous namespace
123 // hasUniqueAddress - Return true if the specified value points to something
124 // with a unique, discernable, address.
125 static inline bool hasUniqueAddress(const Value *V) {
126 return isa<GlobalValue>(V) || isa<AllocationInst>(V);
129 // getUnderlyingObject - This traverses the use chain to figure out what object
130 // the specified value points to. If the value points to, or is derived from, a
131 // unique object or an argument, return it.
132 static const Value *getUnderlyingObject(const Value *V) {
133 if (!isa<PointerType>(V->getType())) return 0;
135 // If we are at some type of object... return it.
136 if (hasUniqueAddress(V) || isa<Argument>(V)) return V;
138 // Traverse through different addressing mechanisms...
139 if (const Instruction *I = dyn_cast<Instruction>(V)) {
140 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
141 return getUnderlyingObject(I->getOperand(0));
142 } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
143 if (CE->getOpcode() == Instruction::Cast ||
144 CE->getOpcode() == Instruction::GetElementPtr)
145 return getUnderlyingObject(CE->getOperand(0));
146 } else if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V)) {
147 return CPR->getValue();
152 static const User *isGEP(const Value *V) {
153 if (isa<GetElementPtrInst>(V) ||
154 (isa<ConstantExpr>(V) &&
155 cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr))
156 return cast<User>(V);
160 static const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){
161 assert(GEPOps.empty() && "Expect empty list to populate!");
162 GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1,
163 cast<User>(V)->op_end());
165 // Accumulate all of the chained indexes into the operand array
166 V = cast<User>(V)->getOperand(0);
168 while (const User *G = isGEP(V)) {
169 if (!isa<Constant>(GEPOps[0]) ||
170 !cast<Constant>(GEPOps[0])->isNullValue())
171 break; // Don't handle folding arbitrary pointer offsets yet...
172 GEPOps.erase(GEPOps.begin()); // Drop the zero index
173 GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end());
174 V = G->getOperand(0);
179 /// pointsToConstantMemory - Chase pointers until we find a (constant
181 bool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) {
182 if (const Value *V = getUnderlyingObject(P))
183 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
184 return GV->isConstant();
188 static bool AddressMightEscape(const Value *V) {
189 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end();
191 const Instruction *I = cast<Instruction>(*UI);
192 switch (I->getOpcode()) {
193 case Instruction::Load: break;
194 case Instruction::Store:
195 if (I->getOperand(0) == V)
196 return true; // Escapes if the pointer is stored.
198 case Instruction::GetElementPtr:
199 if (AddressMightEscape(I)) return true;
201 case Instruction::Cast:
202 if (!isa<PointerType>(I->getType()))
204 if (AddressMightEscape(I)) return true;
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) && !isa<GlobalValue>(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 V1 = CE->getOperand(0);
245 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2))
246 if (CE->getOpcode() == Instruction::Cast)
247 V2 = CE->getOperand(0);
249 // Strip off constant pointer refs if they exist
250 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
251 V1 = CPR->getValue();
252 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
253 V2 = CPR->getValue();
255 // Are we checking for alias of the same value?
256 if (V1 == V2) return MustAlias;
258 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
259 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
260 return NoAlias; // Scalars cannot alias each other
262 // Strip off cast instructions...
263 if (const Instruction *I = dyn_cast<CastInst>(V1))
264 return alias(I->getOperand(0), V1Size, V2, V2Size);
265 if (const Instruction *I = dyn_cast<CastInst>(V2))
266 return alias(V1, V1Size, I->getOperand(0), V2Size);
268 // Figure out what objects these things are pointing to if we can...
269 const Value *O1 = getUnderlyingObject(V1);
270 const Value *O2 = getUnderlyingObject(V2);
272 // Pointing at a discernible object?
274 if (isa<Argument>(O1)) {
275 // Incoming argument cannot alias locally allocated object!
276 if (isa<AllocationInst>(O2)) return NoAlias;
277 // Otherwise, nothing is known...
278 } else if (isa<Argument>(O2)) {
279 // Incoming argument cannot alias locally allocated object!
280 if (isa<AllocationInst>(O1)) return NoAlias;
281 // Otherwise, nothing is known...
283 // If they are two different objects, we know that we have no alias...
284 if (O1 != O2) return NoAlias;
287 // If they are the same object, they we can look at the indexes. If they
288 // index off of the object is the same for both pointers, they must alias.
289 // If they are provably different, they must not alias. Otherwise, we can't
291 } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) {
292 return NoAlias; // Unique values don't alias null
293 } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) {
294 return NoAlias; // Unique values don't alias null
297 // If we have two gep instructions with must-alias'ing base pointers, figure
298 // out if the indexes to the GEP tell us anything about the derived pointer.
299 // Note that we also handle chains of getelementptr instructions as well as
300 // constant expression getelementptrs here.
302 if (isGEP(V1) && isGEP(V2)) {
303 // Drill down into the first non-gep value, to test for must-aliasing of
304 // the base pointers.
305 const Value *BasePtr1 = V1, *BasePtr2 = V2;
307 BasePtr1 = cast<User>(BasePtr1)->getOperand(0);
308 } while (isGEP(BasePtr1) &&
309 cast<User>(BasePtr1)->getOperand(1) ==
310 Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType()));
312 BasePtr2 = cast<User>(BasePtr2)->getOperand(0);
313 } while (isGEP(BasePtr2) &&
314 cast<User>(BasePtr2)->getOperand(1) ==
315 Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType()));
317 // Do the base pointers alias?
318 AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size);
319 if (BaseAlias == NoAlias) return NoAlias;
320 if (BaseAlias == MustAlias) {
321 // If the base pointers alias each other exactly, check to see if we can
322 // figure out anything about the resultant pointers, to try to prove
325 // Collect all of the chained GEP operands together into one simple place
326 std::vector<Value*> GEP1Ops, GEP2Ops;
327 BasePtr1 = GetGEPOperands(V1, GEP1Ops);
328 BasePtr2 = GetGEPOperands(V2, GEP2Ops);
331 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size,
332 BasePtr2->getType(), GEP2Ops, V2Size);
333 if (GAlias != MayAlias)
338 // Check to see if these two pointers are related by a getelementptr
339 // instruction. If one pointer is a GEP with a non-zero index of the other
340 // pointer, we know they cannot alias.
344 std::swap(V1Size, V2Size);
347 if (V1Size != ~0U && V2Size != ~0U)
348 if (const User *GEP = isGEP(V1)) {
349 std::vector<Value*> GEPOperands;
350 const Value *BasePtr = GetGEPOperands(V1, GEPOperands);
352 AliasResult R = alias(BasePtr, V1Size, V2, V2Size);
353 if (R == MustAlias) {
354 // If there is at least one non-zero constant index, we know they cannot
356 bool ConstantFound = false;
357 bool AllZerosFound = true;
358 for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i)
359 if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) {
360 if (!C->isNullValue()) {
361 ConstantFound = true;
362 AllZerosFound = false;
366 AllZerosFound = false;
369 // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases
370 // the ptr, the end result is a must alias also.
375 if (V2Size <= 1 && V1Size <= 1) // Just pointer check?
378 // Otherwise we have to check to see that the distance is more than
379 // the size of the argument... build an index vector that is equal to
380 // the arguments provided, except substitute 0's for any variable
381 // indexes we find...
382 for (unsigned i = 0; i != GEPOperands.size(); ++i)
383 if (!isa<Constant>(GEPOperands[i]) ||
384 isa<ConstantExpr>(GEPOperands[i]))
385 GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType());
386 int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(),
388 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size)
397 static bool ValuesEqual(Value *V1, Value *V2) {
398 if (V1->getType() == V2->getType())
400 if (Constant *C1 = dyn_cast<Constant>(V1))
401 if (Constant *C2 = dyn_cast<Constant>(V2)) {
402 // Sign extend the constants to long types.
403 C1 = ConstantExpr::getSignExtend(C1, Type::LongTy);
404 C2 = ConstantExpr::getSignExtend(C2, Type::LongTy);
410 /// CheckGEPInstructions - Check two GEP instructions with known must-aliasing
411 /// base pointers. This checks to see if the index expressions preclude the
412 /// pointers from aliasing...
413 AliasAnalysis::AliasResult BasicAliasAnalysis::
414 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops,
416 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops,
418 // We currently can't handle the case when the base pointers have different
419 // primitive types. Since this is uncommon anyway, we are happy being
420 // extremely conservative.
421 if (BasePtr1Ty != BasePtr2Ty)
424 const Type *GEPPointerTy = BasePtr1Ty;
426 // Find the (possibly empty) initial sequence of equal values... which are not
427 // necessarily constants.
428 unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size();
429 unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands);
430 unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands);
431 unsigned UnequalOper = 0;
432 while (UnequalOper != MinOperands &&
433 ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) {
434 // Advance through the type as we go...
436 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
437 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]);
439 // If all operands equal each other, then the derived pointers must
440 // alias each other...
442 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands &&
443 "Ran out of type nesting, but not out of operands?");
448 // If we have seen all constant operands, and run out of indexes on one of the
449 // getelementptrs, check to see if the tail of the leftover one is all zeros.
450 // If so, return mustalias.
451 if (UnequalOper == MinOperands) {
452 if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops);
454 bool AllAreZeros = true;
455 for (unsigned i = UnequalOper; i != MaxOperands; ++i)
456 if (!isa<Constant>(GEP1Ops[i]) ||
457 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
461 if (AllAreZeros) return MustAlias;
465 // So now we know that the indexes derived from the base pointers,
466 // which are known to alias, are different. We can still determine a
467 // no-alias result if there are differing constant pairs in the index
468 // chain. For example:
469 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
471 unsigned SizeMax = std::max(G1S, G2S);
472 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
474 // Scan for the first operand that is constant and unequal in the
475 // two getelementptrs...
476 unsigned FirstConstantOper = UnequalOper;
477 for (; FirstConstantOper != MinOperands; ++FirstConstantOper) {
478 const Value *G1Oper = GEP1Ops[FirstConstantOper];
479 const Value *G2Oper = GEP2Ops[FirstConstantOper];
481 if (G1Oper != G2Oper) // Found non-equal constant indexes...
482 if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper)))
483 if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) {
484 if (G1OC->getType() != G2OC->getType()) {
485 // Sign extend both operands to long.
486 G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy);
487 G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy);
488 GEP1Ops[FirstConstantOper] = G1OC;
489 GEP2Ops[FirstConstantOper] = G2OC;
493 // Make sure they are comparable (ie, not constant expressions)...
494 // and make sure the GEP with the smaller leading constant is GEP1.
495 Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC);
496 if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) {
497 if (CV->getValue()) // If they are comparable and G2 > G1
498 std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2
503 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper);
506 // No shared constant operands, and we ran out of common operands. At this
507 // point, the GEP instructions have run through all of their operands, and we
508 // haven't found evidence that there are any deltas between the GEP's.
509 // However, one GEP may have more operands than the other. If this is the
510 // case, there may still be hope. Check this now.
511 if (FirstConstantOper == MinOperands) {
512 // Make GEP1Ops be the longer one if there is a longer one.
513 if (GEP1Ops.size() < GEP2Ops.size())
514 std::swap(GEP1Ops, GEP2Ops);
516 // Is there anything to check?
517 if (GEP1Ops.size() > MinOperands) {
518 for (unsigned i = FirstConstantOper; i != MaxOperands; ++i)
519 if (isa<ConstantInt>(GEP1Ops[i]) &&
520 !cast<Constant>(GEP1Ops[i])->isNullValue()) {
521 // Yup, there's a constant in the tail. Set all variables to
522 // constants in the GEP instruction to make it suiteable for
523 // TargetData::getIndexedOffset.
524 for (i = 0; i != MaxOperands; ++i)
525 if (!isa<ConstantInt>(GEP1Ops[i]))
526 GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType());
527 // Okay, now get the offset. This is the relative offset for the full
529 const TargetData &TD = getTargetData();
530 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
532 // Now crop off any constants from the end...
533 GEP1Ops.resize(MinOperands);
534 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops);
536 // If the tail provided a bit enough offset, return noalias!
537 if ((uint64_t)(Offset2-Offset1) >= SizeMax)
542 // Couldn't find anything useful.
546 // If there are non-equal constants arguments, then we can figure
547 // out a minimum known delta between the two index expressions... at
548 // this point we know that the first constant index of GEP1 is less
549 // than the first constant index of GEP2.
551 // Advance BasePtr[12]Ty over this first differing constant operand.
552 BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]);
553 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]);
555 // We are going to be using TargetData::getIndexedOffset to determine the
556 // offset that each of the GEP's is reaching. To do this, we have to convert
557 // all variable references to constant references. To do this, we convert the
558 // initial equal sequence of variables into constant zeros to start with.
559 for (unsigned i = 0; i != FirstConstantOper; ++i) {
560 if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) ||
561 !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i]))
562 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy);
565 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok
567 // Loop over the rest of the operands...
568 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) {
569 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0;
570 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0;
571 // If they are equal, use a zero index...
572 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) {
573 if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1))
574 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType());
575 // Otherwise, just keep the constants we have.
578 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
579 // If this is an array index, make sure the array element is in range.
580 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
581 if (Op1C->getRawValue() >= AT->getNumElements())
582 return MayAlias; // Be conservative with out-of-range accesses
585 // GEP1 is known to produce a value less than GEP2. To be
586 // conservatively correct, we must assume the largest possible
587 // constant is used in this position. This cannot be the initial
588 // index to the GEP instructions (because we know we have at least one
589 // element before this one with the different constant arguments), so
590 // we know that the current index must be into either a struct or
591 // array. Because we know it's not constant, this cannot be a
592 // structure index. Because of this, we can calculate the maximum
595 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
596 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1);
601 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) {
602 // If this is an array index, make sure the array element is in range.
603 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty))
604 if (Op2C->getRawValue() >= AT->getNumElements())
605 return MayAlias; // Be conservative with out-of-range accesses
606 } else { // Conservatively assume the minimum value for this index
607 GEP2Ops[i] = Constant::getNullValue(Op2->getType());
612 if (BasePtr1Ty && Op1) {
613 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty))
614 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]);
619 if (BasePtr2Ty && Op2) {
620 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty))
621 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]);
627 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops);
628 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops);
629 assert(Offset1 < Offset2 &&"There is at least one different constant here!");
631 if ((uint64_t)(Offset2-Offset1) >= SizeMax) {
632 //std::cerr << "Determined that these two GEP's don't alias ["
633 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;
640 struct StringCompare {
641 bool operator()(const char *LHS, const char *RHS) {
642 return strcmp(LHS, RHS) < 0;
647 // Note that this list cannot contain libm functions (such as acos and sqrt)
648 // that set errno on a domain or other error.
649 static const char *DoesntAccessMemoryTable[] = {
651 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered",
653 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl",
654 "trunc", "truncf", "truncl", "ldexp",
656 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l",
658 "cos", "cosf", "cosl", "cosh", "coshf", "coshl",
659 "exp", "expf", "expl",
661 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl",
662 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl",
665 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint"
666 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper",
669 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower",
670 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit",
672 "iswctype", "towctrans", "towlower", "towupper",
676 "isinf", "isnan", "finite",
678 // C99 math functions
679 "copysign", "copysignf", "copysignd",
680 "nexttoward", "nexttowardf", "nexttowardd",
681 "nextafter", "nextafterf", "nextafterd",
684 "__fpclassify", "__fpclassifyf", "__fpclassifyl",
685 "__signbit", "__signbitf", "__signbitl",
688 static const unsigned DAMTableSize =
689 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]);
691 /// doesNotAccessMemory - Return true if we know that the function does not
692 /// access memory at all. Since basicaa does no analysis, we can only do simple
693 /// things here. In particular, if we have an external function with the name
694 /// of a standard C library function, we are allowed to assume it will be
695 /// resolved by libc, so we can hardcode some entries in here.
696 bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) {
697 if (!F->isExternal()) return false;
699 static bool Initialized = false;
701 // Sort the table the first time through.
702 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize,
707 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable,
708 DoesntAccessMemoryTable+DAMTableSize,
709 F->getName().c_str(), StringCompare());
710 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName();
714 static const char *OnlyReadsMemoryTable[] = {
715 "atoi", "atol", "atof", "atoll", "atoq", "a64l",
716 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr",
719 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp",
720 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr",
724 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk",
725 "wcsrchr", "wcsspn", "wcsstr",
728 "alphasort", "alphasort64", "versionsort", "versionsort64",
731 "nan", "nanf", "nand",
734 "feof", "ferror", "fileno",
735 "feof_unlocked", "ferror_unlocked", "fileno_unlocked"
738 static const unsigned ORMTableSize =
739 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]);
741 bool BasicAliasAnalysis::onlyReadsMemory(Function *F) {
742 if (doesNotAccessMemory(F)) return true;
743 if (!F->isExternal()) return false;
745 static bool Initialized = false;
747 // Sort the table the first time through.
748 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize,
753 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable,
754 OnlyReadsMemoryTable+ORMTableSize,
755 F->getName().c_str(), StringCompare());
756 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName();