BasicAliasAnalysis.cpp revision db5b80a7f2521a1f9ca8f339fdac2b6e11cc422a
19d7c9ea05316bab07b2b83caa357dac220078a65Chris Lattner//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 10d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// This file defines the default implementation of the Alias Analysis interface 11d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// that simply implements a few identities (two different globals cannot alias, 12d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// etc), but otherwise does no analysis. 13d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 14d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner//===----------------------------------------------------------------------===// 15d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 16d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Analysis/AliasAnalysis.h" 176eb88d44c93f782a988039a047a9b80354a81887Chris Lattner#include "llvm/Constants.h" 18d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/DerivedTypes.h" 194244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Function.h" 204244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/GlobalVariable.h" 214244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/iOther.h" 224244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/iMemory.h" 234244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Pass.h" 24d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Target/TargetData.h" 251af55e169396dfa057f0a6067fa8b16eb4317909Chris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 26ec4e8085e83fa1f14a82849548f7c1ad82009adeChris Lattnerusing namespace llvm; 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 28d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// Make sure that anything that uses AliasAnalysis pulls in this file... 29863914578a10d4cf83e1fdc5d7bc3242838c8e6fChris Lattnervoid llvm::BasicAAStub() {} 30d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 31d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnernamespace { 32b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// NoAA - This class implements the -no-aa pass, which always returns "I 33b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// don't know" for alias queries. NoAA is unlike other alias analysis 34b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// implementations, in that it does not chain to a previous analysis. As 35b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// such it doesn't follow many of the rules that other alias analyses must. 36b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// 37b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner struct NoAA : public ImmutablePass, public AliasAnalysis { 38689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 39689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner AU.addRequired<TargetData>(); 40689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 41689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner 42689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void initializePass() { 43689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner TD = &getAnalysis<TargetData>(); 44689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 45689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner 46b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual AliasResult alias(const Value *V1, unsigned V1Size, 47b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner const Value *V2, unsigned V2Size) { 48b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return MayAlias; 49b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 50b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 51b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 52b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool pointsToConstantMemory(const Value *P) { return false; } 53b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool doesNotAccessMemory(Function *F) { return false; } 54b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool onlyReadsMemory(Function *F) { return false; } 55b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 56b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 57b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 58b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 59b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 60b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 61b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool hasNoModRefInfoForCalls() const { return true; } 62b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 63b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void deleteValue(Value *V) {} 64b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void copyValue(Value *From, Value *To) {} 65b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner }; 66b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 67b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner // Register this pass... 68b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner RegisterOpt<NoAA> 69b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner U("no-aa", "No Alias Analysis (always returns 'may' alias)"); 70b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 71b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner // Declare that we implement the AliasAnalysis interface 72b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner RegisterAnalysisGroup<AliasAnalysis, NoAA> V; 73b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner} // End of anonymous namespace 74b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 75b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 76b52f44086006434039b0c5df55aaac1079d26b96Chris Lattnernamespace { 77b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// BasicAliasAnalysis - This is the default alias analysis implementation. 78b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 79b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// derives from the NoAA class. 80b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner struct BasicAliasAnalysis : public NoAA { 81d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner AliasResult alias(const Value *V1, unsigned V1Size, 82d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size); 83bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 8404b75935462642641469fb264aab9f1110ce2666Chris Lattner ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 8504b75935462642641469fb264aab9f1110ce2666Chris Lattner 86e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// hasNoModRefInfoForCalls - We can provide mod/ref information against 87e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// non-escaping allocations. 88e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner virtual bool hasNoModRefInfoForCalls() const { return false; } 8965585aa3fcb6c70ab36fb8965ac864378f5e3d44Chris Lattner 90bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// pointsToConstantMemory - Chase pointers until we find a (constant 91bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// global) or not. 92bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner bool pointsToConstantMemory(const Value *P); 93bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 944244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner virtual bool doesNotAccessMemory(Function *F); 954244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner virtual bool onlyReadsMemory(Function *F); 964244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 97d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner private: 98b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // CheckGEPInstructions - Check two GEP instructions with known 99b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // must-aliasing base pointers. This checks to see if the index expressions 100d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // preclude the pointers from aliasing... 101b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AliasResult 102b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner CheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 103b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned G1Size, 104b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 105b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned G2Size); 106d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner }; 107d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 108d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Register this pass... 109d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner RegisterOpt<BasicAliasAnalysis> 110d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner X("basicaa", "Basic Alias Analysis (default AA impl)"); 111d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 112d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Declare that we implement the AliasAnalysis interface 113d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 114d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} // End of anonymous namespace 115d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 116c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner// hasUniqueAddress - Return true if the specified value points to something 117c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner// with a unique, discernable, address. 118d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnerstatic inline bool hasUniqueAddress(const Value *V) { 119c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner return isa<GlobalValue>(V) || isa<AllocationInst>(V); 120d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 121d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 122c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner// getUnderlyingObject - This traverses the use chain to figure out what object 123c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner// the specified value points to. If the value points to, or is derived from, a 124c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner// unique object or an argument, return it. 125d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnerstatic const Value *getUnderlyingObject(const Value *V) { 126d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (!isa<PointerType>(V->getType())) return 0; 127d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 128d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If we are at some type of object... return it. 129c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner if (hasUniqueAddress(V) || isa<Argument>(V)) return V; 130d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 131d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Traverse through different addressing mechanisms... 132d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (const Instruction *I = dyn_cast<Instruction>(V)) { 133d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 134d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return getUnderlyingObject(I->getOperand(0)); 135388f669d956c08571108f26a5371e02269e662f5Chris Lattner } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 136388f669d956c08571108f26a5371e02269e662f5Chris Lattner if (CE->getOpcode() == Instruction::Cast || 137388f669d956c08571108f26a5371e02269e662f5Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 138388f669d956c08571108f26a5371e02269e662f5Chris Lattner return getUnderlyingObject(CE->getOperand(0)); 139e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 140e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer return GV; 141d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 142d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return 0; 143d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 144d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 145b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattnerstatic const User *isGEP(const Value *V) { 146b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (isa<GetElementPtrInst>(V) || 147b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner (isa<ConstantExpr>(V) && 148b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 149b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return cast<User>(V); 150b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return 0; 151b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner} 152d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 1534a83088b307968c25d11ea3e7de254cfb1771aebChris Lattnerstatic const Value *GetGEPOperands(const Value *V, std::vector<Value*> &GEPOps){ 1544a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner assert(GEPOps.empty() && "Expect empty list to populate!"); 1554a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 1564a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner cast<User>(V)->op_end()); 1574a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 1584a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner // Accumulate all of the chained indexes into the operand array 1594a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner V = cast<User>(V)->getOperand(0); 1604a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 1614a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner while (const User *G = isGEP(V)) { 162e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 1634a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner !cast<Constant>(GEPOps[0])->isNullValue()) 1644a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner break; // Don't handle folding arbitrary pointer offsets yet... 1654a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.erase(GEPOps.begin()); // Drop the zero index 1664a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 1674a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner V = G->getOperand(0); 1684a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner } 1694a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner return V; 1704a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner} 1714a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 172bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// pointsToConstantMemory - Chase pointers until we find a (constant 173bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// global) or not. 174bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattnerbool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 175a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner if (const Value *V = getUnderlyingObject(P)) 176a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 177a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner return GV->isConstant(); 178bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner return false; 179bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner} 1804a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 18104b75935462642641469fb264aab9f1110ce2666Chris Lattnerstatic bool AddressMightEscape(const Value *V) { 18204b75935462642641469fb264aab9f1110ce2666Chris Lattner for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 18304b75935462642641469fb264aab9f1110ce2666Chris Lattner UI != E; ++UI) { 18404b75935462642641469fb264aab9f1110ce2666Chris Lattner const Instruction *I = cast<Instruction>(*UI); 18504b75935462642641469fb264aab9f1110ce2666Chris Lattner switch (I->getOpcode()) { 18604b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::Load: break; 18704b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::Store: 18804b75935462642641469fb264aab9f1110ce2666Chris Lattner if (I->getOperand(0) == V) 18904b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; // Escapes if the pointer is stored. 19004b75935462642641469fb264aab9f1110ce2666Chris Lattner break; 19104b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::GetElementPtr: 19204b75935462642641469fb264aab9f1110ce2666Chris Lattner if (AddressMightEscape(I)) return true; 19304b75935462642641469fb264aab9f1110ce2666Chris Lattner break; 19404b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::Cast: 19504b75935462642641469fb264aab9f1110ce2666Chris Lattner if (!isa<PointerType>(I->getType())) 19604b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; 19704b75935462642641469fb264aab9f1110ce2666Chris Lattner if (AddressMightEscape(I)) return true; 19804b75935462642641469fb264aab9f1110ce2666Chris Lattner break; 199db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner case Instruction::Ret: 200db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner // If returned, the address will escape to calling functions, but no 201db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner // callees could modify it. 202db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner break; 20304b75935462642641469fb264aab9f1110ce2666Chris Lattner default: 20404b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; 20504b75935462642641469fb264aab9f1110ce2666Chris Lattner } 20604b75935462642641469fb264aab9f1110ce2666Chris Lattner } 20704b75935462642641469fb264aab9f1110ce2666Chris Lattner return false; 20804b75935462642641469fb264aab9f1110ce2666Chris Lattner} 20904b75935462642641469fb264aab9f1110ce2666Chris Lattner 21004b75935462642641469fb264aab9f1110ce2666Chris Lattner// getModRefInfo - Check to see if the specified callsite can clobber the 21104b75935462642641469fb264aab9f1110ce2666Chris Lattner// specified memory object. Since we only look at local properties of this 21204b75935462642641469fb264aab9f1110ce2666Chris Lattner// function, we really can't say much about this query. We do, however, use 21304b75935462642641469fb264aab9f1110ce2666Chris Lattner// simple "address taken" analysis on local objects. 21404b75935462642641469fb264aab9f1110ce2666Chris Lattner// 21504b75935462642641469fb264aab9f1110ce2666Chris LattnerAliasAnalysis::ModRefResult 21604b75935462642641469fb264aab9f1110ce2666Chris LattnerBasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 217e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer if (!isa<Constant>(P)) 21804b75935462642641469fb264aab9f1110ce2666Chris Lattner if (const AllocationInst *AI = 2197a82ba0510aece59f59fe988ab273c3542b4d559Chris Lattner dyn_cast_or_null<AllocationInst>(getUnderlyingObject(P))) { 22004b75935462642641469fb264aab9f1110ce2666Chris Lattner // Okay, the pointer is to a stack allocated object. If we can prove that 22104b75935462642641469fb264aab9f1110ce2666Chris Lattner // the pointer never "escapes", then we know the call cannot clobber it, 22204b75935462642641469fb264aab9f1110ce2666Chris Lattner // because it simply can't get its address. 22304b75935462642641469fb264aab9f1110ce2666Chris Lattner if (!AddressMightEscape(AI)) 22404b75935462642641469fb264aab9f1110ce2666Chris Lattner return NoModRef; 22504b75935462642641469fb264aab9f1110ce2666Chris Lattner } 22604b75935462642641469fb264aab9f1110ce2666Chris Lattner 227bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // The AliasAnalysis base class has some smarts, lets use them. 228bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner return AliasAnalysis::getModRefInfo(CS, P, Size); 22904b75935462642641469fb264aab9f1110ce2666Chris Lattner} 23004b75935462642641469fb264aab9f1110ce2666Chris Lattner 231d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 232d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// as array references. Note that this function is heavily tail recursive. 233d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// Hopefully we have a smart C++ compiler. :) 234d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 235d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerAliasAnalysis::AliasResult 236d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerBasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 237d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size) { 238b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Strip off any constant expression casts if they exist 239b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 240bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner if (CE->getOpcode() == Instruction::Cast && 241bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner isa<PointerType>(CE->getOperand(0)->getType())) 242b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V1 = CE->getOperand(0); 243b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 244bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner if (CE->getOpcode() == Instruction::Cast && 245bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner isa<PointerType>(CE->getOperand(0)->getType())) 246b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V2 = CE->getOperand(0); 247b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 248d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Are we checking for alias of the same value? 249d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (V1 == V2) return MustAlias; 250d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 251d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 252d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner V1->getType() != Type::LongTy && V2->getType() != Type::LongTy) 253d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; // Scalars cannot alias each other 254d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 255d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Strip off cast instructions... 256d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (const Instruction *I = dyn_cast<CastInst>(V1)) 257bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner if (isa<PointerType>(I->getOperand(0)->getType())) 258bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner return alias(I->getOperand(0), V1Size, V2, V2Size); 259d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (const Instruction *I = dyn_cast<CastInst>(V2)) 260bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner if (isa<PointerType>(I->getOperand(0)->getType())) 261bb8f43c8fcac4688f25c6d3a46651a0b1893eb03Chris Lattner return alias(V1, V1Size, I->getOperand(0), V2Size); 262d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 263d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Figure out what objects these things are pointing to if we can... 264d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *O1 = getUnderlyingObject(V1); 265d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *O2 = getUnderlyingObject(V2); 266d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 2672f2d06506c9167dada05b11debe717334de972d4Misha Brukman // Pointing at a discernible object? 268d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (O1 && O2) { 269c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner if (isa<Argument>(O1)) { 270c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner // Incoming argument cannot alias locally allocated object! 271c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner if (isa<AllocationInst>(O2)) return NoAlias; 272c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner // Otherwise, nothing is known... 273c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } else if (isa<Argument>(O2)) { 274c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner // Incoming argument cannot alias locally allocated object! 275c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner if (isa<AllocationInst>(O1)) return NoAlias; 276c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner // Otherwise, nothing is known... 277c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } else { 278c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner // If they are two different objects, we know that we have no alias... 279c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner if (O1 != O2) return NoAlias; 280c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } 281d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 282d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If they are the same object, they we can look at the indexes. If they 283d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // index off of the object is the same for both pointers, they must alias. 284d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If they are provably different, they must not alias. Otherwise, we can't 285d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // tell anything. 286c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } else if (O1 && !isa<Argument>(O1) && isa<ConstantPointerNull>(V2)) { 287d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; // Unique values don't alias null 288c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } else if (O2 && !isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) { 289d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; // Unique values don't alias null 290d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 291d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 292b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have two gep instructions with must-alias'ing base pointers, figure 293b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // out if the indexes to the GEP tell us anything about the derived pointer. 294b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Note that we also handle chains of getelementptr instructions as well as 295b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant expression getelementptrs here. 296d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 297b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (isGEP(V1) && isGEP(V2)) { 298b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Drill down into the first non-gep value, to test for must-aliasing of 299b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // the base pointers. 300b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *BasePtr1 = V1, *BasePtr2 = V2; 301b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner do { 302b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1 = cast<User>(BasePtr1)->getOperand(0); 303b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } while (isGEP(BasePtr1) && 304b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner cast<User>(BasePtr1)->getOperand(1) == 305b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner Constant::getNullValue(cast<User>(BasePtr1)->getOperand(1)->getType())); 306b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner do { 307b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2 = cast<User>(BasePtr2)->getOperand(0); 308b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } while (isGEP(BasePtr2) && 309b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner cast<User>(BasePtr2)->getOperand(1) == 310b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner Constant::getNullValue(cast<User>(BasePtr2)->getOperand(1)->getType())); 311b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 312b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Do the base pointers alias? 313b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AliasResult BaseAlias = alias(BasePtr1, V1Size, BasePtr2, V2Size); 314b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == NoAlias) return NoAlias; 315b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == MustAlias) { 316b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the base pointers alias each other exactly, check to see if we can 317b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // figure out anything about the resultant pointers, to try to prove 318b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // non-aliasing. 319b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 320b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Collect all of the chained GEP operands together into one simple place 3214a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner std::vector<Value*> GEP1Ops, GEP2Ops; 3224a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr1 = GetGEPOperands(V1, GEP1Ops); 3234a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr2 = GetGEPOperands(V2, GEP2Ops); 3244a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 325b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AliasResult GAlias = 326b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner CheckGEPInstructions(BasePtr1->getType(), GEP1Ops, V1Size, 327b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2->getType(), GEP2Ops, V2Size); 328b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (GAlias != MayAlias) 329b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return GAlias; 330b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 331b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 332d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 333d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Check to see if these two pointers are related by a getelementptr 334d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // instruction. If one pointer is a GEP with a non-zero index of the other 335d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // pointer, we know they cannot alias. 336d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 3374a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (isGEP(V2)) { 338d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1, V2); 339d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1Size, V2Size); 340d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 341d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 342c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V1Size != ~0U && V2Size != ~0U) 3434a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (const User *GEP = isGEP(V1)) { 3444a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner std::vector<Value*> GEPOperands; 3454a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 3464a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 3474a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 348c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (R == MustAlias) { 349c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // If there is at least one non-zero constant index, we know they cannot 350c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // alias. 351c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner bool ConstantFound = false; 35288d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner bool AllZerosFound = true; 3534a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 3544a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 355c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (!C->isNullValue()) { 356c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner ConstantFound = true; 357c54735e7cbd639a612837d93bf75d73507dd7d47Chris Lattner AllZerosFound = false; 358c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner break; 35988d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } 36088d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } else { 36188d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner AllZerosFound = false; 362c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 36388d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 36488d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 36588d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // the ptr, the end result is a must alias also. 36688d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner if (AllZerosFound) 36788d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner return MustAlias; 36888d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 369c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (ConstantFound) { 370c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 371d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; 372c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner 373c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // Otherwise we have to check to see that the distance is more than 374c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the size of the argument... build an index vector that is equal to 375c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the arguments provided, except substitute 0's for any variable 376c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // indexes we find... 3774a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner for (unsigned i = 0; i != GEPOperands.size(); ++i) 378e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer if (!isa<Constant>(GEPOperands[i]) || isa<GlobalValue>(GEPOperands[i]) || 3794a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner isa<ConstantExpr>(GEPOperands[i])) 3804a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOperands[i] =Constant::getNullValue(GEPOperands[i]->getType()); 3814a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner int64_t Offset = getTargetData().getIndexedOffset(BasePtr->getType(), 3824a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOperands); 3834a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 384c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner return NoAlias; 385c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 386c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 387d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 388c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner 389d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 390d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 391d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 39228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattnerstatic bool ValuesEqual(Value *V1, Value *V2) { 39328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (V1->getType() == V2->getType()) 39428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return V1 == V2; 39528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C1 = dyn_cast<Constant>(V1)) 39628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C2 = dyn_cast<Constant>(V2)) { 39728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // Sign extend the constants to long types. 39828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner C1 = ConstantExpr::getSignExtend(C1, Type::LongTy); 39928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner C2 = ConstantExpr::getSignExtend(C2, Type::LongTy); 40028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return C1 == C2; 40128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 40228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return false; 40328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner} 40428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner 405b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 406b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// base pointers. This checks to see if the index expressions preclude the 407b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// pointers from aliasing... 408b307c88fe799eb69c37bee2840d9fde93d407e3aChris LattnerAliasAnalysis::AliasResult BasicAliasAnalysis:: 409b307c88fe799eb69c37bee2840d9fde93d407e3aChris LattnerCheckGEPInstructions(const Type* BasePtr1Ty, std::vector<Value*> &GEP1Ops, 410b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned G1S, 411b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Type *BasePtr2Ty, std::vector<Value*> &GEP2Ops, 412b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned G2S) { 413b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We currently can't handle the case when the base pointers have different 414b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // primitive types. Since this is uncommon anyway, we are happy being 415b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // extremely conservative. 416b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty != BasePtr2Ty) 417b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 418b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 419b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Type *GEPPointerTy = BasePtr1Ty; 420b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 421b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Find the (possibly empty) initial sequence of equal values... which are not 422b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // necessarily constants. 423b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned NumGEP1Operands = GEP1Ops.size(), NumGEP2Operands = GEP2Ops.size(); 424b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 425b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 426b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned UnequalOper = 0; 427b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner while (UnequalOper != MinOperands && 42828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner ValuesEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 429b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance through the type as we go... 430b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner ++UnequalOper; 431b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 432b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 433b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else { 434b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If all operands equal each other, then the derived pointers must 435b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // alias each other... 436b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 437b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 438b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner "Ran out of type nesting, but not out of operands?"); 439b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MustAlias; 440920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 441920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 442920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 443b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have seen all constant operands, and run out of indexes on one of the 444b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // getelementptrs, check to see if the tail of the leftover one is all zeros. 445b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If so, return mustalias. 4464a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (UnequalOper == MinOperands) { 447b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (GEP1Ops.size() < GEP2Ops.size()) std::swap(GEP1Ops, GEP2Ops); 448d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 449b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner bool AllAreZeros = true; 450b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = UnequalOper; i != MaxOperands; ++i) 451e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer if (!isa<Constant>(GEP1Ops[i]) || 452b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner !cast<Constant>(GEP1Ops[i])->isNullValue()) { 453b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AllAreZeros = false; 454b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner break; 455b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 456b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (AllAreZeros) return MustAlias; 457b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 458b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 459d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 460d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // So now we know that the indexes derived from the base pointers, 461d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // which are known to alias, are different. We can still determine a 462d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // no-alias result if there are differing constant pairs in the index 463d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // chain. For example: 464d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 465d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 466d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned SizeMax = std::max(G1S, G2S); 467d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work... 468920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 469d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Scan for the first operand that is constant and unequal in the 47028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // two getelementptrs... 471d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned FirstConstantOper = UnequalOper; 472b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 473b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G1Oper = GEP1Ops[FirstConstantOper]; 474b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G2Oper = GEP2Ops[FirstConstantOper]; 475b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 4766eb88d44c93f782a988039a047a9b80354a81887Chris Lattner if (G1Oper != G2Oper) // Found non-equal constant indexes... 4776eb88d44c93f782a988039a047a9b80354a81887Chris Lattner if (Constant *G1OC = dyn_cast<Constant>(const_cast<Value*>(G1Oper))) 4786eb88d44c93f782a988039a047a9b80354a81887Chris Lattner if (Constant *G2OC = dyn_cast<Constant>(const_cast<Value*>(G2Oper))) { 47928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC->getType() != G2OC->getType()) { 48028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // Sign extend both operands to long. 48128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner G1OC = ConstantExpr::getSignExtend(G1OC, Type::LongTy); 48228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner G2OC = ConstantExpr::getSignExtend(G2OC, Type::LongTy); 48328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP1Ops[FirstConstantOper] = G1OC; 48428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP2Ops[FirstConstantOper] = G2OC; 48528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 48628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner 48728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC != G2OC) { 48828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // Make sure they are comparable (ie, not constant expressions)... 48928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // and make sure the GEP with the smaller leading constant is GEP1. 49028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner Constant *Compare = ConstantExpr::getSetGT(G1OC, G2OC); 49128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (ConstantBool *CV = dyn_cast<ConstantBool>(Compare)) { 49228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (CV->getValue()) // If they are comparable and G2 > G1 49328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 49428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner break; 49528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 4966eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 4976eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 498b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 499d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 500d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 501b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // No shared constant operands, and we ran out of common operands. At this 502b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // point, the GEP instructions have run through all of their operands, and we 503b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // haven't found evidence that there are any deltas between the GEP's. 504b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // However, one GEP may have more operands than the other. If this is the 50528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // case, there may still be hope. Check this now. 506b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (FirstConstantOper == MinOperands) { 507b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Make GEP1Ops be the longer one if there is a longer one. 508b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (GEP1Ops.size() < GEP2Ops.size()) 509b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner std::swap(GEP1Ops, GEP2Ops); 510b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 511b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Is there anything to check? 512b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (GEP1Ops.size() > MinOperands) { 513b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 514f70770abd53cf275368acd08f1f494301f4ce138Chris Lattner if (isa<ConstantInt>(GEP1Ops[i]) && 515b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner !cast<Constant>(GEP1Ops[i])->isNullValue()) { 516b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Yup, there's a constant in the tail. Set all variables to 517b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constants in the GEP instruction to make it suiteable for 518b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // TargetData::getIndexedOffset. 519b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (i = 0; i != MaxOperands; ++i) 520f70770abd53cf275368acd08f1f494301f4ce138Chris Lattner if (!isa<ConstantInt>(GEP1Ops[i])) 521b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 522b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Okay, now get the offset. This is the relative offset for the full 523b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // instruction. 524b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const TargetData &TD = getTargetData(); 525b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 526b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 527b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Now crop off any constants from the end... 528b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops.resize(MinOperands); 529b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops); 530b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 531b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the tail provided a bit enough offset, return noalias! 532b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if ((uint64_t)(Offset2-Offset1) >= SizeMax) 533b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return NoAlias; 534b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 535b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 536b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 537b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Couldn't find anything useful. 538b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 539b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 540d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 541d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If there are non-equal constants arguments, then we can figure 542d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // out a minimum known delta between the two index expressions... at 543d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // this point we know that the first constant index of GEP1 is less 544d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // than the first constant index of GEP2. 545b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 546b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance BasePtr[12]Ty over this first differing constant operand. 547b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP2Ops[FirstConstantOper]); 548b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(GEP1Ops[FirstConstantOper]); 549d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 550b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We are going to be using TargetData::getIndexedOffset to determine the 551b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // offset that each of the GEP's is reaching. To do this, we have to convert 552b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // all variable references to constant references. To do this, we convert the 553b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // initial equal sequence of variables into constant zeros to start with. 554b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = 0; i != FirstConstantOper; ++i) { 555b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (!isa<Constant>(GEP1Ops[i]) || isa<ConstantExpr>(GEP1Ops[i]) || 55628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner !isa<Constant>(GEP2Ops[i]) || isa<ConstantExpr>(GEP2Ops[i])) 55728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::UIntTy); 558b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 559b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 560b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 561d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 562d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Loop over the rest of the operands... 563b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 564b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *Op1 = i < GEP1Ops.size() ? GEP1Ops[i] : 0; 565b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *Op2 = i < GEP2Ops.size() ? GEP2Ops[i] : 0; 566b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If they are equal, use a zero index... 567b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 568b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (!isa<Constant>(Op1) || isa<ConstantExpr>(Op1)) 569b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 570b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Otherwise, just keep the constants we have. 571d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } else { 572b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1) { 573b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 574b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 575b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 576b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1C->getRawValue() >= AT->getNumElements()) 577b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 578b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 579b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { 580b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // GEP1 is known to produce a value less than GEP2. To be 581b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // conservatively correct, we must assume the largest possible 582b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant is used in this position. This cannot be the initial 583b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // index to the GEP instructions (because we know we have at least one 584b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // element before this one with the different constant arguments), so 585b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // we know that the current index must be into either a struct or 586b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // array. Because we know it's not constant, this cannot be a 587b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // structure index. Because of this, we can calculate the maximum 588b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // value possible. 589b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // 590b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 591b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops[i] = ConstantSInt::get(Type::LongTy,AT->getNumElements()-1); 592b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 593d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 594d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 595b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op2) { 596b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 597b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 598b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 599b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op2C->getRawValue() >= AT->getNumElements()) 600b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 601b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { // Conservatively assume the minimum value for this index 602b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 603b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 604920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 605b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 606b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 607b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty && Op1) { 608b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 609b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 610b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 611b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 612b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 613b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 614b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr2Ty && Op2) { 615b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 616b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 617b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 618b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = 0; 619d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 620d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 621d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 622b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner int64_t Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops); 623b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner int64_t Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops); 624d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner assert(Offset1 < Offset2 &&"There is at least one different constant here!"); 625d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 626807b7055b21c3262f6dfb15bbe22ef648e73c5a9Chris Lattner if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 627d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner //std::cerr << "Determined that these two GEP's don't alias [" 628d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 629d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; 630d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 631d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 632d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 633d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 6344244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnernamespace { 6354244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner struct StringCompare { 6364244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner bool operator()(const char *LHS, const char *RHS) { 6374244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner return strcmp(LHS, RHS) < 0; 6384244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner } 6394244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner }; 6404244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner} 6414244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 6424244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner// Note that this list cannot contain libm functions (such as acos and sqrt) 6434244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner// that set errno on a domain or other error. 6444244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerstatic const char *DoesntAccessMemoryTable[] = { 645b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner // LLVM intrinsics: 6464ee623de0b0fdaa2d5caa75bd65bc300cb889962Chris Lattner "llvm.frameaddress", "llvm.returnaddress", "llvm.readport", "llvm.isunordered", 647b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner 6484244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "abs", "labs", "llabs", "imaxabs", "fabs", "fabsf", "fabsl", 6494244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "trunc", "truncf", "truncl", "ldexp", 6504244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 6514244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "atan", "atanf", "atanl", "atan2", "atan2f", "atan2l", 6524244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "cbrt", 6534244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "cos", "cosf", "cosl", "cosh", "coshf", "coshl", 6544244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "exp", "expf", "expl", 6554244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "hypot", 6564244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "sin", "sinf", "sinl", "sinh", "sinhf", "sinhl", 6574244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "tan", "tanf", "tanl", "tanh", "tanhf", "tanhl", 6584244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 659bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // ctype.h 6604244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "isalnum", "isalpha", "iscntrl", "isdigit", "isgraph", "islower", "isprint" 6614244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "ispunct", "isspace", "isupper", "isxdigit", "tolower", "toupper", 6624244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 663bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // wctype.h" 6644244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "iswalnum", "iswalpha", "iswcntrl", "iswdigit", "iswgraph", "iswlower", 6654244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "iswprint", "iswpunct", "iswspace", "iswupper", "iswxdigit", 6664244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 667bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner "iswctype", "towctrans", "towlower", "towupper", 668bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner 6694244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "btowc", "wctob", 670002be767333e4253df6c5477dda28890dbd3488cChris Lattner 671002be767333e4253df6c5477dda28890dbd3488cChris Lattner "isinf", "isnan", "finite", 672002be767333e4253df6c5477dda28890dbd3488cChris Lattner 673002be767333e4253df6c5477dda28890dbd3488cChris Lattner // C99 math functions 674002be767333e4253df6c5477dda28890dbd3488cChris Lattner "copysign", "copysignf", "copysignd", 675002be767333e4253df6c5477dda28890dbd3488cChris Lattner "nexttoward", "nexttowardf", "nexttowardd", 676002be767333e4253df6c5477dda28890dbd3488cChris Lattner "nextafter", "nextafterf", "nextafterd", 677002be767333e4253df6c5477dda28890dbd3488cChris Lattner 678002be767333e4253df6c5477dda28890dbd3488cChris Lattner // glibc functions: 679002be767333e4253df6c5477dda28890dbd3488cChris Lattner "__fpclassify", "__fpclassifyf", "__fpclassifyl", 680002be767333e4253df6c5477dda28890dbd3488cChris Lattner "__signbit", "__signbitf", "__signbitl", 6814244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner}; 6824244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 6834244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerstatic const unsigned DAMTableSize = 6844244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner sizeof(DoesntAccessMemoryTable)/sizeof(DoesntAccessMemoryTable[0]); 6854244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 6864244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner/// doesNotAccessMemory - Return true if we know that the function does not 6874244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner/// access memory at all. Since basicaa does no analysis, we can only do simple 6884244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner/// things here. In particular, if we have an external function with the name 6894244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner/// of a standard C library function, we are allowed to assume it will be 6904244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner/// resolved by libc, so we can hardcode some entries in here. 6914244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerbool BasicAliasAnalysis::doesNotAccessMemory(Function *F) { 6924244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner if (!F->isExternal()) return false; 6934244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 6944244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner static bool Initialized = false; 6954244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner if (!Initialized) { 6964244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner // Sort the table the first time through. 6974244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner std::sort(DoesntAccessMemoryTable, DoesntAccessMemoryTable+DAMTableSize, 6984244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner StringCompare()); 6994244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner Initialized = true; 7004244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner } 7014244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7024244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner const char **Ptr = std::lower_bound(DoesntAccessMemoryTable, 7034244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner DoesntAccessMemoryTable+DAMTableSize, 7044244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner F->getName().c_str(), StringCompare()); 7054244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner return Ptr != DoesntAccessMemoryTable+DAMTableSize && *Ptr == F->getName(); 7064244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner} 7074244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7084244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7094244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerstatic const char *OnlyReadsMemoryTable[] = { 710002be767333e4253df6c5477dda28890dbd3488cChris Lattner "atoi", "atol", "atof", "atoll", "atoq", "a64l", 711002be767333e4253df6c5477dda28890dbd3488cChris Lattner "bcmp", "memcmp", "memchr", "memrchr", "wmemcmp", "wmemchr", 7124244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7134244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner // Strings 7144244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "strcmp", "strcasecmp", "strcoll", "strncmp", "strncasecmp", 7154244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "strchr", "strcspn", "strlen", "strpbrk", "strrchr", "strspn", "strstr", 716002be767333e4253df6c5477dda28890dbd3488cChris Lattner "index", "rindex", 7174244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7184244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner // Wide char strings 7194244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "wcschr", "wcscmp", "wcscoll", "wcscspn", "wcslen", "wcsncmp", "wcspbrk", 7204244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner "wcsrchr", "wcsspn", "wcsstr", 721002be767333e4253df6c5477dda28890dbd3488cChris Lattner 722002be767333e4253df6c5477dda28890dbd3488cChris Lattner // glibc 723002be767333e4253df6c5477dda28890dbd3488cChris Lattner "alphasort", "alphasort64", "versionsort", "versionsort64", 724002be767333e4253df6c5477dda28890dbd3488cChris Lattner 725002be767333e4253df6c5477dda28890dbd3488cChris Lattner // C99 726002be767333e4253df6c5477dda28890dbd3488cChris Lattner "nan", "nanf", "nand", 727b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner 728b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner // File I/O 729b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner "feof", "ferror", "fileno", 730b903fc5c1b62ebf7f9339d63a623596be792ef00Chris Lattner "feof_unlocked", "ferror_unlocked", "fileno_unlocked" 7314244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner}; 7324244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7334244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerstatic const unsigned ORMTableSize = 7344244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner sizeof(OnlyReadsMemoryTable)/sizeof(OnlyReadsMemoryTable[0]); 7354244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7364244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattnerbool BasicAliasAnalysis::onlyReadsMemory(Function *F) { 7374244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner if (doesNotAccessMemory(F)) return true; 7384244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner if (!F->isExternal()) return false; 7394244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7404244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner static bool Initialized = false; 7414244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner if (!Initialized) { 7424244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner // Sort the table the first time through. 7434244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner std::sort(OnlyReadsMemoryTable, OnlyReadsMemoryTable+ORMTableSize, 7444244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner StringCompare()); 7454244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner Initialized = true; 7464244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner } 7474244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7484244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner const char **Ptr = std::lower_bound(OnlyReadsMemoryTable, 7494244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner OnlyReadsMemoryTable+ORMTableSize, 7504244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner F->getName().c_str(), StringCompare()); 7514244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner return Ptr != OnlyReadsMemoryTable+ORMTableSize && *Ptr == F->getName(); 7524244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner} 7534244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 7544244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner 755