BasicAliasAnalysis.cpp revision a35339dfb67cec3d7e9783c9c6d3de110ea6bafe
1//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 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. 7// 8//===----------------------------------------------------------------------===// 9// 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. 13// 14//===----------------------------------------------------------------------===// 15 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" 25#include <algorithm> 26using namespace llvm; 27 28// Make sure that anything that uses AliasAnalysis pulls in this file... 29void llvm::BasicAAStub() {} 30 31namespace { 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. 36 /// 37 struct NoAA : public ImmutablePass, public AliasAnalysis { 38 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 39 AU.addRequired<TargetData>(); 40 } 41 42 virtual void initializePass() { 43 TD = &getAnalysis<TargetData>(); 44 } 45 46 virtual AliasResult alias(const Value *V1, unsigned V1Size, 47 const Value *V2, unsigned V2Size) { 48 return MayAlias; 49 } 50 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) { 56 return ModRef; 57 } 58 virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 59 return ModRef; 60 } 61 virtual bool hasNoModRefInfoForCalls() const { return true; } 62 63 virtual void deleteValue(Value *V) {} 64 virtual void copyValue(Value *From, Value *To) {} 65 }; 66 67 // Register this pass... 68 RegisterOpt<NoAA> 69 U("no-aa", "No Alias Analysis (always returns 'may' alias)"); 70 71 // Declare that we implement the AliasAnalysis interface 72 RegisterAnalysisGroup<AliasAnalysis, NoAA> V; 73} // End of anonymous namespace 74 75 76namespace { 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); 83 84 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 85 86 /// hasNoModRefInfoForCalls - We can provide mod/ref information against 87 /// non-escaping allocations. 88 virtual bool hasNoModRefInfoForCalls() const { return false; } 89 90 /// pointsToConstantMemory - Chase pointers until we find a (constant 91 /// global) or not. 92 bool pointsToConstantMemory(const Value *P); 93 94 virtual bool doesNotAccessMemory(Function *F); 95 virtual bool onlyReadsMemory(Function *F); 96 97 private: 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... 101 AliasResult 102 CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 103 unsigned G1Size, 104 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 105 unsigned G2Size); 106 }; 107 108 // Register this pass... 109 RegisterOpt<BasicAliasAnalysis> 110 X("basicaa", "Basic Alias Analysis (default AA impl)"); 111 112 // Declare that we implement the AliasAnalysis interface 113 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 114} // End of anonymous namespace 115 116// hasUniqueAddress - Return true if the specified value points to something 117// with a unique, discernable, address. 118static inline bool hasUniqueAddress(const Value *V) { 119 return isa<GlobalValue>(V) || isa<AllocationInst>(V); 120} 121 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. 125static const Value *getUnderlyingObject(const Value *V) { 126 if (!isa<PointerType>(V->getType())) return 0; 127 128 // If we are at some type of object... return it. 129 if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 130 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)) { 140 return GV; 141 } 142 return 0; 143} 144 145static 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); 150 return 0; 151} 152 153static 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()); 157 158 // Accumulate all of the chained indexes into the operand array 159 V = cast<User>(V)->getOperand(0); 160 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); 168 } 169 return V; 170} 171 172/// pointsToConstantMemory - Chase pointers until we find a (constant 173/// global) or not. 174bool 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(); 178 return false; 179} 180 181static bool AddressMightEscape(const Value *V) { 182 for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 183 UI != E; ++UI) { 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. 190 break; 191 case Instruction::GetElementPtr: 192 if (AddressMightEscape(I)) return true; 193 break; 194 case Instruction::Cast: 195 if (!isa<PointerType>(I->getType())) 196 return true; 197 if (AddressMightEscape(I)) return true; 198 break; 199 case Instruction::Ret: 200 // If returned, the address will escape to calling functions, but no 201 // callees could modify it. 202 break; 203 default: 204 return true; 205 } 206 } 207 return false; 208} 209 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. 214// 215AliasAnalysis::ModRefResult 216BasicAliasAnalysis::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)) 224 return NoModRef; 225 } 226 227 // The AliasAnalysis base class has some smarts, lets use them. 228 return AliasAnalysis::getModRefInfo(CS, P, Size); 229} 230 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. :) 234// 235AliasAnalysis::AliasResult 236BasicAliasAnalysis::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); 247 248 // Are we checking for alias of the same value? 249 if (V1 == V2) return MustAlias; 250 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 254 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); 262 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); 266 267 // Pointing at a discernible object? 268 if (O1 && O2) { 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... 277 } else { 278 // If they are two different objects, we know that we have no alias... 279 if (O1 != O2) return NoAlias; 280 } 281 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 285 // tell anything. 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 290 } 291 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. 296 // 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; 301 do { 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())); 306 do { 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())); 311 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 318 // non-aliasing. 319 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); 324 325 // If GetGEPOperands were able to fold to the same must-aliased pointer, 326 // do the comparison. 327 if (BasePtr1 == BasePtr2) { 328 AliasResult GAlias = 329 CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 330 BasePtr2->getType(), GEP2Ops, V2Size); 331 if (GAlias != MayAlias) 332 return GAlias; 333 } 334 } 335 } 336 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. 340 // 341 if (isGEP(V2)) { 342 std::swap(V1, V2); 343 std::swap(V1Size, V2Size); 344 } 345 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); 350 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 354 // alias. 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; 362 break; 363 } 364 } else { 365 AllZerosFound = false; 366 } 367 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. 370 if (AllZerosFound) 371 return MustAlias; 372 373 if (ConstantFound) { 374 if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 375 return NoAlias; 376 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(), 386 GEPOperands); 387 if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 388 return NoAlias; 389 } 390 } 391 } 392 393 return MayAlias; 394} 395 396static bool ValuesEqual(Value *V1, Value *V2) { 397 if (V1->getType() == V2->getType()) 398 return V1 == V2; 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); 404 return C1 == C2; 405 } 406 return false; 407} 408 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... 412AliasAnalysis::AliasResult BasicAliasAnalysis:: 413CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 414 unsigned G1S, 415 const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 416 unsigned G2S) { 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) 421 return MayAlias; 422 423 const Type *GEPPointerTy = BasePtr1Ty; 424 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... 434 ++UnequalOper; 435 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 436 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 437 else { 438 // If all operands equal each other, then the derived pointers must 439 // alias each other... 440 BasePtr1Ty = 0; 441 assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 442 "Ran out of type nesting, but not out of operands?"); 443 return MustAlias; 444 } 445 } 446 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); 452 453 bool AllAreZeros = true; 454 for (unsigned i = UnequalOper; i != MaxOperands; ++i) 455 if (!isa<Constant>(GEP1Ops[i]) || 456 !cast<Constant>(GEP1Ops[i])->isNullValue()) { 457 AllAreZeros = false; 458 break; 459 } 460 if (AllAreZeros) return MustAlias; 461 } 462 463 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)) 469 // 470 unsigned SizeMax = std::max(G1S, G2S); 471 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... 472 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]; 479 480 if (G1Oper != G2Oper) // Found non-equal constant indexes... 481 if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 482 if (Constant *G2OC = dyn_cast<ConstantInt>(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; 489 } 490 491 if (G1OC != G2OC) { 492 // Make sure they are comparable (ie, not constant expressions), and 493 // 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 498 break; 499 } 500 } 501 } 502 BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 503 } 504 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); 514 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 527 // instruction. 528 const TargetData &TD = getTargetData(); 529 int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 530 531 // Now crop off any constants from the end... 532 GEP1Ops.resize(MinOperands); 533 int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 534 535 // If the tail provided a bit enough offset, return noalias! 536 if ((uint64_t)(Offset2-Offset1) >= SizeMax) 537 return NoAlias; 538 } 539 } 540 541 // Couldn't find anything useful. 542 return MayAlias; 543 } 544 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. 549 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]); 553 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<ConstantInt>(GEP1Ops[i]) || !isa<ConstantInt>(GEP2Ops[i])) 560 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy); 561 562 // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 563 564 // Loop over the rest of the operands... 565 for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 566 const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 567 const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 568 // If they are equal, use a zero index... 569 if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 570 if (!isa<ConstantInt>(Op1)) 571 GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 572 // Otherwise, just keep the constants we have. 573 } else { 574 if (Op1) { 575 if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 576 // If this is an array index, make sure the array element is in range. 577 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 578 if (Op1C->getRawValue() >= AT->getNumElements()) 579 return MayAlias; // Be conservative with out-of-range accesses 580 581 } else { 582 // GEP1 is known to produce a value less than GEP2. To be 583 // conservatively correct, we must assume the largest possible 584 // constant is used in this position. This cannot be the initial 585 // index to the GEP instructions (because we know we have at least one 586 // element before this one with the different constant arguments), so 587 // we know that the current index must be into either a struct or 588 // array. Because we know it's not constant, this cannot be a 589 // structure index. Because of this, we can calculate the maximum 590 // value possible. 591 // 592 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 593 GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1); 594 } 595 } 596 597 if (Op2) { 598 if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 599 // If this is an array index, make sure the array element is in range. 600 if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 601 if (Op2C->getRawValue() >= AT->getNumElements()) 602 return MayAlias; // Be conservative with out-of-range accesses 603 } else { // Conservatively assume the minimum value for this index 604 GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 605 } 606 } 607 } 608 609 if (BasePtr1Ty && Op1) { 610 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 611 BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 612 else 613 BasePtr1Ty = 0; 614 } 615 616 if (BasePtr2Ty && Op2) { 617 if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 618 BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 619 else 620 BasePtr2Ty = 0; 621 } 622 } 623 624 int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 625 int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 626 assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 627 628 if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 629 //std::cerr << "Determined that these two GEP's don't alias [" 630 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 631 return NoAlias; 632 } 633 return MayAlias; 634} 635 636namespace { 637 struct StringCompare { 638 bool operator()(const char *LHS, const char *RHS) { 639 return strcmp(LHS, RHS) < 0; 640 } 641 }; 642} 643 644// Note that this list cannot contain libm functions (such as acos and sqrt) 645// that set errno on a domain or other error. 646static const char *DoesntAccessMemoryTable[] = { 647 // LLVM intrinsics: 648 "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered", 649 650 "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 651 "trunc", "truncf", "truncl", "ldexp", 652 653 "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 654 "cbrt", 655 "cos", "cosf", "cosl", "cosh", "coshf", "coshl", 656 "exp", "expf", "expl", 657 "hypot", 658 "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl", 659 "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 660 661 // ctype.h 662 "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 663 "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 664 665 // wctype.h" 666 "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 667 "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 668 669 "iswctype", "towctrans", "towlower", "towupper", 670 671 "btowc", "wctob", 672 673 "isinf", "isnan", "finite", 674 675 // C99 math functions 676 "copysign", "copysignf", "copysignd", 677 "nexttoward", "nexttowardf", "nexttowardd", 678 "nextafter", "nextafterf", "nextafterd", 679 680 // glibc functions: 681 "__fpclassify", "__fpclassifyf", "__fpclassifyl", 682 "__signbit", "__signbitf", "__signbitl", 683}; 684 685static const unsigned DAMTableSize = 686 sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]); 687 688/// doesNotAccessMemory - Return true if we know that the function does not 689/// access memory at all. Since basicaa does no analysis, we can only do simple 690/// things here. In particular, if we have an external function with the name 691/// of a standard C library function, we are allowed to assume it will be 692/// resolved by libc, so we can hardcode some entries in here. 693bool BasicAliasAnalysis::doesNotAccessMemory(Function *F) { 694 if (!F->isExternal()) return false; 695 696 static bool Initialized = false; 697 if (!Initialized) { 698 // Sort the table the first time through. 699 std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize, 700 StringCompare()); 701 Initialized = true; 702 } 703 704 const char **Ptr = std::lower_bound(DoesntAccessMemoryTable, 705 DoesntAccessMemoryTable+DAMTableSize, 706 F->getName().c_str(), StringCompare()); 707 return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName(); 708} 709 710 711static const char *OnlyReadsMemoryTable[] = { 712 "atoi", "atol", "atof", "atoll", "atoq", "a64l", 713 "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 714 715 // Strings 716 "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 717 "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 718 "index", "rindex", 719 720 // Wide char strings 721 "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 722 "wcsrchr", "wcsspn", "wcsstr", 723 724 // glibc 725 "alphasort", "alphasort64", "versionsort", "versionsort64", 726 727 // C99 728 "nan", "nanf", "nand", 729 730 // File I/O 731 "feof", "ferror", "fileno", 732 "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 733}; 734 735static const unsigned ORMTableSize = 736 sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]); 737 738bool BasicAliasAnalysis::onlyReadsMemory(Function *F) { 739 if (doesNotAccessMemory(F)) return true; 740 if (!F->isExternal()) return false; 741 742 static bool Initialized = false; 743 if (!Initialized) { 744 // Sort the table the first time through. 745 std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize, 746 StringCompare()); 747 Initialized = true; 748 } 749 750 const char **Ptr = std::lower_bound(OnlyReadsMemoryTable, 751 OnlyReadsMemoryTable+ORMTableSize, 752 F->getName().c_str(), StringCompare()); 753 return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName(); 754} 755 756 757