BasicAliasAnalysis.cpp revision fd687500384803311556571989dc14cd84786904
19d7c9ea05316bab07b2b83caa357dac220078a65Chris Lattner//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 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" 17534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen#include "llvm/Analysis/Passes.h" 186eb88d44c93f782a988039a047a9b80354a81887Chris Lattner#include "llvm/Constants.h" 19d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/DerivedTypes.h" 204244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Function.h" 21406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb#include "llvm/ParameterAttributes.h" 224244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/GlobalVariable.h" 23eb62bc77b68e8d2350453d15aca300f481a612d5Alkis Evlogimenos#include "llvm/Instructions.h" 24a583990ec83a4773608084a9694943ddd268e571Chandler Carruth#include "llvm/Intrinsics.h" 254244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Pass.h" 26d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Target/TargetData.h" 27a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner#include "llvm/ADT/SmallVector.h" 28718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson#include "llvm/ADT/STLExtras.h" 29a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 3090aa839c88776e3dd0b3a798a98ea30d85b6b53cChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3190aa839c88776e3dd0b3a798a98ea30d85b6b53cChris Lattner#include "llvm/Support/ManagedStatic.h" 3220aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 33ec4e8085e83fa1f14a82849548f7c1ad82009adeChris Lattnerusing namespace llvm; 34d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 35d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnernamespace { 36b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// NoAA - This class implements the -no-aa pass, which always returns "I 37b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// don't know" for alias queries. NoAA is unlike other alias analysis 38b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// implementations, in that it does not chain to a previous analysis. As 39b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// such it doesn't follow many of the rules that other alias analyses must. 40b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// 419525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 421997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 43794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel NoAA() : ImmutablePass((intptr_t)&ID) {} 44a6900c7ad9752a27e2e3b1bd78b2af3b1381176dDan Gohman explicit NoAA(intptr_t PID) : ImmutablePass(PID) { } 45794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 46689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner AU.addRequired<TargetData>(); 48689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 492b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 50689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void initializePass() { 51689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner TD = &getAnalysis<TargetData>(); 52689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 53689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner 54b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual AliasResult alias(const Value *V1, unsigned V1Size, 55b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner const Value *V2, unsigned V2Size) { 56b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return MayAlias; 57b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 58b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 595226f6a901241c0aa1a8fbdccf1abb7a07e29d18Chris Lattner virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS, 605226f6a901241c0aa1a8fbdccf1abb7a07e29d18Chris Lattner std::vector<PointerAccessInfo> *Info) { 610af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner return UnknownModRefBehavior; 620af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner } 632b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 640af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner virtual void getArgumentAccesses(Function *F, CallSite CS, 650af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner std::vector<PointerAccessInfo> &Info) { 660af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner assert(0 && "This method may not be called on this function!"); 670af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner } 680af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner 69b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 70b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool pointsToConstantMemory(const Value *P) { return false; } 71b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 72b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 73b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 74b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 75b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 76b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 77b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool hasNoModRefInfoForCalls() const { return true; } 78b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 79b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void deleteValue(Value *V) {} 80b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void copyValue(Value *From, Value *To) {} 81b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner }; 822b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 83b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner // Register this pass... 841997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char NoAA::ID = 0; 857f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<NoAA> 86b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner U("no-aa", "No Alias Analysis (always returns 'may' alias)"); 87b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 88b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner // Declare that we implement the AliasAnalysis interface 89a5370172b64bed5daf8e2869d7bf7cb52f80d6b7Chris Lattner RegisterAnalysisGroup<AliasAnalysis> V(U); 90b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner} // End of anonymous namespace 91b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 92534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 93b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 94b52f44086006434039b0c5df55aaac1079d26b96Chris Lattnernamespace { 95b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// BasicAliasAnalysis - This is the default alias analysis implementation. 96b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 97b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// derives from the NoAA class. 989525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 991997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 10003265f98a3b2f49ecd0c01b868e0a9c844c3eeb7Anton Korobeynikov BasicAliasAnalysis() : NoAA((intptr_t)&ID) { } 101d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner AliasResult alias(const Value *V1, unsigned V1Size, 102d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size); 103bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 10404b75935462642641469fb264aab9f1110ce2666Chris Lattner ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 1054a7ebfa4111305ea22fc753d4f029eed88149662Reid Spencer ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 1064a7ebfa4111305ea22fc753d4f029eed88149662Reid Spencer return NoAA::getModRefInfo(CS1,CS2); 1074a7ebfa4111305ea22fc753d4f029eed88149662Reid Spencer } 10804b75935462642641469fb264aab9f1110ce2666Chris Lattner 109e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// hasNoModRefInfoForCalls - We can provide mod/ref information against 110e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// non-escaping allocations. 111e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner virtual bool hasNoModRefInfoForCalls() const { return false; } 11265585aa3fcb6c70ab36fb8965ac864378f5e3d44Chris Lattner 113bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// pointsToConstantMemory - Chase pointers until we find a (constant 114bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// global) or not. 115bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner bool pointsToConstantMemory(const Value *P); 116bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 117d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner private: 118b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // CheckGEPInstructions - Check two GEP instructions with known 119b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // must-aliasing base pointers. This checks to see if the index expressions 120d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // preclude the pointers from aliasing... 121b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AliasResult 122fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner CheckGEPInstructions(const Type* BasePtr1Ty, 123fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 124fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type *BasePtr2Ty, 125fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 126d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner }; 1272b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 128d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Register this pass... 1291997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char BasicAliasAnalysis::ID = 0; 1307f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner RegisterPass<BasicAliasAnalysis> 131d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner X("basicaa", "Basic Alias Analysis (default AA impl)"); 132d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 133d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Declare that we implement the AliasAnalysis interface 134a5370172b64bed5daf8e2869d7bf7cb52f80d6b7Chris Lattner RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 135d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} // End of anonymous namespace 136d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 137534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createBasicAliasAnalysisPass() { 138534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen return new BasicAliasAnalysis(); 139534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen} 140534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 141fd687500384803311556571989dc14cd84786904Chris Lattner/// getUnderlyingObject - This traverses the use chain to figure out what object 142fd687500384803311556571989dc14cd84786904Chris Lattner/// the specified value points to. If the value points to, or is derived from, 143fd687500384803311556571989dc14cd84786904Chris Lattner/// a unique object or an argument, return it. This returns: 144fd687500384803311556571989dc14cd84786904Chris Lattner/// Arguments, GlobalVariables, Functions, Allocas, Mallocs. 145d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnerstatic const Value *getUnderlyingObject(const Value *V) { 146d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (!isa<PointerType>(V->getType())) return 0; 147d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 1483da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // If we are at some type of object, return it. GlobalValues and Allocations 1493da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // have unique addresses. 1503da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (isa<GlobalValue>(V) || isa<AllocationInst>(V) || isa<Argument>(V)) 1513da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer return V; 1522b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 153d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Traverse through different addressing mechanisms... 154d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (const Instruction *I = dyn_cast<Instruction>(V)) { 1553da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I)) 156d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return getUnderlyingObject(I->getOperand(0)); 157388f669d956c08571108f26a5371e02269e662f5Chris Lattner } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 1583da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->getOpcode() == Instruction::BitCast || 159388f669d956c08571108f26a5371e02269e662f5Chris Lattner CE->getOpcode() == Instruction::GetElementPtr) 160388f669d956c08571108f26a5371e02269e662f5Chris Lattner return getUnderlyingObject(CE->getOperand(0)); 161d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 162d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return 0; 163d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 164d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 165b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattnerstatic const User *isGEP(const Value *V) { 166b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (isa<GetElementPtrInst>(V) || 167b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner (isa<ConstantExpr>(V) && 168b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner cast<ConstantExpr>(V)->getOpcode() == Instruction::GetElementPtr)) 169b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return cast<User>(V); 170b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return 0; 171b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner} 172d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 173a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattnerstatic const Value *GetGEPOperands(const Value *V, 174a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner SmallVector<Value*, 16> &GEPOps){ 1754a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner assert(GEPOps.empty() && "Expect empty list to populate!"); 1764a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 1774a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner cast<User>(V)->op_end()); 1784a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 1794a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner // Accumulate all of the chained indexes into the operand array 1804a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner V = cast<User>(V)->getOperand(0); 1814a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 1824a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner while (const User *G = isGEP(V)) { 183e840434755e2165ac20ec55e9d5ff3d2defac2d2Reid Spencer if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 1844a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner !cast<Constant>(GEPOps[0])->isNullValue()) 1854a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner break; // Don't handle folding arbitrary pointer offsets yet... 1864a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.erase(GEPOps.begin()); // Drop the zero index 1874a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 1884a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner V = G->getOperand(0); 1894a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner } 1904a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner return V; 1914a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner} 1924a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 193bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// pointsToConstantMemory - Chase pointers until we find a (constant 194bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// global) or not. 195bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattnerbool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 196a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner if (const Value *V = getUnderlyingObject(P)) 197a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 198a4dd6743e7b300a62b0ee288912657123dafe2f6Chris Lattner return GV->isConstant(); 199bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner return false; 200bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner} 2014a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 2023da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// Determine if an AllocationInst instruction escapes from the function it is 2033da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// contained in. If it does not escape, there is no way for another function to 2043da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// mod/ref it. We do this by looking at its uses and determining if the uses 2053da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// can escape (recursively). 20604b75935462642641469fb264aab9f1110ce2666Chris Lattnerstatic bool AddressMightEscape(const Value *V) { 20704b75935462642641469fb264aab9f1110ce2666Chris Lattner for (Value::use_const_iterator UI = V->use_begin(), E = V->use_end(); 20804b75935462642641469fb264aab9f1110ce2666Chris Lattner UI != E; ++UI) { 20904b75935462642641469fb264aab9f1110ce2666Chris Lattner const Instruction *I = cast<Instruction>(*UI); 21004b75935462642641469fb264aab9f1110ce2666Chris Lattner switch (I->getOpcode()) { 2113da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer case Instruction::Load: 2123da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer break; //next use. 21304b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::Store: 21404b75935462642641469fb264aab9f1110ce2666Chris Lattner if (I->getOperand(0) == V) 21504b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; // Escapes if the pointer is stored. 2163da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer break; // next use. 21704b75935462642641469fb264aab9f1110ce2666Chris Lattner case Instruction::GetElementPtr: 2183da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (AddressMightEscape(I)) 2193da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer return true; 220df344febe27b8fa68424032c4181e494307d6eafEvan Cheng break; // next use. 2213da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer case Instruction::BitCast: 22204b75935462642641469fb264aab9f1110ce2666Chris Lattner if (!isa<PointerType>(I->getType())) 22304b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; 2243da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (AddressMightEscape(I)) 2253da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer return true; 2263da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer break; // next use 227db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner case Instruction::Ret: 228db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner // If returned, the address will escape to calling functions, but no 229db5b80a7f2521a1f9ca8f339fdac2b6e11cc422aChris Lattner // callees could modify it. 2303da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer break; // next use 23104b75935462642641469fb264aab9f1110ce2666Chris Lattner default: 23204b75935462642641469fb264aab9f1110ce2666Chris Lattner return true; 23304b75935462642641469fb264aab9f1110ce2666Chris Lattner } 23404b75935462642641469fb264aab9f1110ce2666Chris Lattner } 23504b75935462642641469fb264aab9f1110ce2666Chris Lattner return false; 23604b75935462642641469fb264aab9f1110ce2666Chris Lattner} 23704b75935462642641469fb264aab9f1110ce2666Chris Lattner 23804b75935462642641469fb264aab9f1110ce2666Chris Lattner// getModRefInfo - Check to see if the specified callsite can clobber the 23904b75935462642641469fb264aab9f1110ce2666Chris Lattner// specified memory object. Since we only look at local properties of this 24004b75935462642641469fb264aab9f1110ce2666Chris Lattner// function, we really can't say much about this query. We do, however, use 24104b75935462642641469fb264aab9f1110ce2666Chris Lattner// simple "address taken" analysis on local objects. 24204b75935462642641469fb264aab9f1110ce2666Chris Lattner// 24304b75935462642641469fb264aab9f1110ce2666Chris LattnerAliasAnalysis::ModRefResult 24404b75935462642641469fb264aab9f1110ce2666Chris LattnerBasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 245fd687500384803311556571989dc14cd84786904Chris Lattner if (!isa<Constant>(P)) { 246fd687500384803311556571989dc14cd84786904Chris Lattner const Value *Object = getUnderlyingObject(P); 247fd687500384803311556571989dc14cd84786904Chris Lattner // Allocations and byval arguments are "new" objects. 248fd687500384803311556571989dc14cd84786904Chris Lattner if (isa<AllocationInst>(Object) || 249fd687500384803311556571989dc14cd84786904Chris Lattner (isa<Argument>(Object) && cast<Argument>(Object)->hasByValAttr())) { 25004b75935462642641469fb264aab9f1110ce2666Chris Lattner // Okay, the pointer is to a stack allocated object. If we can prove that 25104b75935462642641469fb264aab9f1110ce2666Chris Lattner // the pointer never "escapes", then we know the call cannot clobber it, 25204b75935462642641469fb264aab9f1110ce2666Chris Lattner // because it simply can't get its address. 253fd687500384803311556571989dc14cd84786904Chris Lattner if (!AddressMightEscape(Object)) 25404b75935462642641469fb264aab9f1110ce2666Chris Lattner return NoModRef; 25542e3c81c5f23c42ba2415a8f797d430dad387734Chris Lattner 25642e3c81c5f23c42ba2415a8f797d430dad387734Chris Lattner // If this is a tail call and P points to a stack location, we know that 25742e3c81c5f23c42ba2415a8f797d430dad387734Chris Lattner // the tail call cannot access or modify the local stack. 25842e3c81c5f23c42ba2415a8f797d430dad387734Chris Lattner if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 259fd687500384803311556571989dc14cd84786904Chris Lattner if (CI->isTailCall() && !isa<MallocInst>(Object)) 26042e3c81c5f23c42ba2415a8f797d430dad387734Chris Lattner return NoModRef; 26104b75935462642641469fb264aab9f1110ce2666Chris Lattner } 262fd687500384803311556571989dc14cd84786904Chris Lattner } 26304b75935462642641469fb264aab9f1110ce2666Chris Lattner 264bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // The AliasAnalysis base class has some smarts, lets use them. 265bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner return AliasAnalysis::getModRefInfo(CS, P, Size); 26604b75935462642641469fb264aab9f1110ce2666Chris Lattner} 26704b75935462642641469fb264aab9f1110ce2666Chris Lattner 268d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 269d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// as array references. Note that this function is heavily tail recursive. 270d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// Hopefully we have a smart C++ compiler. :) 271d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 272d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerAliasAnalysis::AliasResult 273d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerBasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 274d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size) { 275b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Strip off any constant expression casts if they exist 276b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 2773da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 278b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V1 = CE->getOperand(0); 279b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 2803da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 281b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V2 = CE->getOperand(0); 282b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 283d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Are we checking for alias of the same value? 284d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (V1 == V2) return MustAlias; 285d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 286d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) && 287c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer V1->getType() != Type::Int64Ty && V2->getType() != Type::Int64Ty) 288d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; // Scalars cannot alias each other 289d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 290d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Strip off cast instructions... 2913da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) 292241607d01648e85754f72de945684c7a8641a292Chris Lattner return alias(I->getOperand(0), V1Size, V2, V2Size); 2933da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 294241607d01648e85754f72de945684c7a8641a292Chris Lattner return alias(V1, V1Size, I->getOperand(0), V2Size); 295d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 296d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Figure out what objects these things are pointing to if we can... 297d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *O1 = getUnderlyingObject(V1); 298d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *O2 = getUnderlyingObject(V2); 299d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 3002f2d06506c9167dada05b11debe717334de972d4Misha Brukman // Pointing at a discernible object? 3010a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (O1) { 3020a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (O2) { 303a326b5da4bdab865ba440b57ae4487fbb16a0b7dChristopher Lamb if (const Argument *O1Arg = dyn_cast<Argument>(O1)) { 3040a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // Incoming argument cannot alias locally allocated object! 3050a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (isa<AllocationInst>(O2)) return NoAlias; 306406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb 307406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb // If they are two different objects, and one is a noalias argument 308406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb // then they do not alias. 309fd687500384803311556571989dc14cd84786904Chris Lattner if (O1 != O2 && O1Arg->hasNoAliasAttr()) 310406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb return NoAlias; 311fd687500384803311556571989dc14cd84786904Chris Lattner 312fd687500384803311556571989dc14cd84786904Chris Lattner // Byval arguments can't alias globals or other arguments. 313fd687500384803311556571989dc14cd84786904Chris Lattner if (O1 != O2 && O1Arg->hasByValAttr()) return NoAlias; 314fd687500384803311556571989dc14cd84786904Chris Lattner 3150a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // Otherwise, nothing is known... 316406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb } 317406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb 318a326b5da4bdab865ba440b57ae4487fbb16a0b7dChristopher Lamb if (const Argument *O2Arg = dyn_cast<Argument>(O2)) { 3190a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // Incoming argument cannot alias locally allocated object! 3200a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (isa<AllocationInst>(O1)) return NoAlias; 321406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb 322406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb // If they are two different objects, and one is a noalias argument 323406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb // then they do not alias. 324fd687500384803311556571989dc14cd84786904Chris Lattner if (O1 != O2 && O2Arg->hasNoAliasAttr()) 325406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb return NoAlias; 326406bfa3e21e8fab3deab240c30c763e78eddf2f5Christopher Lamb 327fd687500384803311556571989dc14cd84786904Chris Lattner // Byval arguments can't alias globals or other arguments. 328fd687500384803311556571989dc14cd84786904Chris Lattner if (O1 != O2 && O2Arg->hasByValAttr()) return NoAlias; 329fd687500384803311556571989dc14cd84786904Chris Lattner 3300a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // Otherwise, nothing is known... 331ef1502925851c813a57bb2257be3026e9de1fdd1Owen Anderson 332fd687500384803311556571989dc14cd84786904Chris Lattner } else if (O1 != O2 && !isa<Argument>(O1)) { 333fd687500384803311556571989dc14cd84786904Chris Lattner // If they are two different objects, and neither is an argument, 334fd687500384803311556571989dc14cd84786904Chris Lattner // we know that we have no alias. 335fd687500384803311556571989dc14cd84786904Chris Lattner return NoAlias; 3360a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner } 337321ff4e6d55401d8f30b9c10023f6fea1803ba18Christopher Lamb 3380a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // If they are the same object, they we can look at the indexes. If they 3390a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // index off of the object is the same for both pointers, they must alias. 3400a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // If they are provably different, they must not alias. Otherwise, we 3410a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // can't tell anything. 342c1820036bdedea566c89d2bd47bbbbe4384bdc73Chris Lattner } 343d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 344fd687500384803311556571989dc14cd84786904Chris Lattner // Unique values don't alias null, except non-byval arguments. 345fd687500384803311556571989dc14cd84786904Chris Lattner if (isa<ConstantPointerNull>(V2)) { 346fd687500384803311556571989dc14cd84786904Chris Lattner if (const Argument *O1Arg = dyn_cast<Argument>(O1)) { 347fd687500384803311556571989dc14cd84786904Chris Lattner if (O1Arg->hasByValAttr()) 348fd687500384803311556571989dc14cd84786904Chris Lattner return NoAlias; 349fd687500384803311556571989dc14cd84786904Chris Lattner } else { 350fd687500384803311556571989dc14cd84786904Chris Lattner return NoAlias; 351fd687500384803311556571989dc14cd84786904Chris Lattner } 352fd687500384803311556571989dc14cd84786904Chris Lattner } 3530a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner 3542b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman if (isa<GlobalVariable>(O1) || 35550bc9ef507090176773aa323e4d2d9413cc9d223Chris Lattner (isa<AllocationInst>(O1) && 35650bc9ef507090176773aa323e4d2d9413cc9d223Chris Lattner !cast<AllocationInst>(O1)->isArrayAllocation())) 3574e61676b568e6a30759d08073d174a0694dfea00Chris Lattner if (cast<PointerType>(O1->getType())->getElementType()->isSized()) { 3580a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // If the size of the other access is larger than the total size of the 3594e61676b568e6a30759d08073d174a0694dfea00Chris Lattner // global/alloca/malloc, it cannot be accessing the global (it's 3604e61676b568e6a30759d08073d174a0694dfea00Chris Lattner // undefined to load or store bytes before or after an object). 3614e61676b568e6a30759d08073d174a0694dfea00Chris Lattner const Type *ElTy = cast<PointerType>(O1->getType())->getElementType(); 362514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned GlobalSize = getTargetData().getABITypeSize(ElTy); 363eaf8f9c667b15cf09b4608558cc24675e92ad2cdChris Lattner if (GlobalSize < V2Size && V2Size != ~0U) 3640a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner return NoAlias; 3650a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner } 3660a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner } 3670a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner 3680a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (O2) { 3690a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner if (!isa<Argument>(O2) && isa<ConstantPointerNull>(V1)) 3700a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner return NoAlias; // Unique values don't alias null 3710a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner 37250bc9ef507090176773aa323e4d2d9413cc9d223Chris Lattner if (isa<GlobalVariable>(O2) || 37350bc9ef507090176773aa323e4d2d9413cc9d223Chris Lattner (isa<AllocationInst>(O2) && 37450bc9ef507090176773aa323e4d2d9413cc9d223Chris Lattner !cast<AllocationInst>(O2)->isArrayAllocation())) 3754e61676b568e6a30759d08073d174a0694dfea00Chris Lattner if (cast<PointerType>(O2->getType())->getElementType()->isSized()) { 3760a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner // If the size of the other access is larger than the total size of the 3774e61676b568e6a30759d08073d174a0694dfea00Chris Lattner // global/alloca/malloc, it cannot be accessing the object (it's 3784e61676b568e6a30759d08073d174a0694dfea00Chris Lattner // undefined to load or store bytes before or after an object). 3794e61676b568e6a30759d08073d174a0694dfea00Chris Lattner const Type *ElTy = cast<PointerType>(O2->getType())->getElementType(); 380514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned GlobalSize = getTargetData().getABITypeSize(ElTy); 381eaf8f9c667b15cf09b4608558cc24675e92ad2cdChris Lattner if (GlobalSize < V1Size && V1Size != ~0U) 3820a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner return NoAlias; 3830a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner } 384d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 385d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 386b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have two gep instructions with must-alias'ing base pointers, figure 387b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // out if the indexes to the GEP tell us anything about the derived pointer. 388b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Note that we also handle chains of getelementptr instructions as well as 389b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant expression getelementptrs here. 390d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 391b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (isGEP(V1) && isGEP(V2)) { 392b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Drill down into the first non-gep value, to test for must-aliasing of 393b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // the base pointers. 3944ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz const User *G = cast<User>(V1); 3954ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz while (isGEP(G->getOperand(0)) && 3964ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz G->getOperand(1) == 3974ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz Constant::getNullValue(G->getOperand(1)->getType())) 3984ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz G = cast<User>(G->getOperand(0)); 3994ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz const Value *BasePtr1 = G->getOperand(0); 4004ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz 4014ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz G = cast<User>(V2); 4024ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz while (isGEP(G->getOperand(0)) && 4034ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz G->getOperand(1) == 4044ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz Constant::getNullValue(G->getOperand(1)->getType())) 4054ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz G = cast<User>(G->getOperand(0)); 4064ba8cfc5a4e98dbe55529bb2a0de17565e90c128Wojciech Matyjewicz const Value *BasePtr2 = G->getOperand(0); 407b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 408b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Do the base pointers alias? 409241607d01648e85754f72de945684c7a8641a292Chris Lattner AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); 410b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == NoAlias) return NoAlias; 411b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == MustAlias) { 412b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the base pointers alias each other exactly, check to see if we can 413b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // figure out anything about the resultant pointers, to try to prove 414b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // non-aliasing. 415b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 416b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Collect all of the chained GEP operands together into one simple place 417a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 4184a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr1 = GetGEPOperands(V1, GEP1Ops); 4194a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr2 = GetGEPOperands(V2, GEP2Ops); 4204a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 421730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner // If GetGEPOperands were able to fold to the same must-aliased pointer, 422730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner // do the comparison. 423730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner if (BasePtr1 == BasePtr2) { 424730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner AliasResult GAlias = 425fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner CheckGEPInstructions(BasePtr1->getType(), 426fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner &GEP1Ops[0], GEP1Ops.size(), V1Size, 427fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner BasePtr2->getType(), 428fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner &GEP2Ops[0], GEP2Ops.size(), V2Size); 429730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner if (GAlias != MayAlias) 430730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner return GAlias; 431730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner } 432b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 433b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 434d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 435d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Check to see if these two pointers are related by a getelementptr 436d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // instruction. If one pointer is a GEP with a non-zero index of the other 437d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // pointer, we know they cannot alias. 438d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 4394a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (isGEP(V2)) { 440d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1, V2); 441d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1Size, V2Size); 442d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 443d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 444c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V1Size != ~0U && V2Size != ~0U) 4453ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer if (isGEP(V1)) { 446a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner SmallVector<Value*, 16> GEPOperands; 4474a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 4484a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 4494a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 450c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (R == MustAlias) { 451c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // If there is at least one non-zero constant index, we know they cannot 452c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // alias. 453c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner bool ConstantFound = false; 45488d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner bool AllZerosFound = true; 4554a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 4564a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 457c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (!C->isNullValue()) { 458c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner ConstantFound = true; 459c54735e7cbd639a612837d93bf75d73507dd7d47Chris Lattner AllZerosFound = false; 460c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner break; 46188d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } 46288d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } else { 46388d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner AllZerosFound = false; 464c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 46588d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 46688d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 46788d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // the ptr, the end result is a must alias also. 46888d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner if (AllZerosFound) 46988d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner return MustAlias; 47088d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 471c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (ConstantFound) { 472c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 473d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; 4742b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 475c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // Otherwise we have to check to see that the distance is more than 476c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the size of the argument... build an index vector that is equal to 477c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the arguments provided, except substitute 0's for any variable 478c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // indexes we find... 479a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos if (cast<PointerType>( 480a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos BasePtr->getType())->getElementType()->isSized()) { 481a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos for (unsigned i = 0; i != GEPOperands.size(); ++i) 4820bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(GEPOperands[i])) 483a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos GEPOperands[i] = 484a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos Constant::getNullValue(GEPOperands[i]->getType()); 485a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos int64_t Offset = 486829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner getTargetData().getIndexedOffset(BasePtr->getType(), 487829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner &GEPOperands[0], 488829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner GEPOperands.size()); 489a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos 490a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 491a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos return NoAlias; 492a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos } 493c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 494c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 495d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 4962b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 497d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 498d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 499d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 5003da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// This function is used to determin if the indices of two GEP instructions are 5013da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// equal. V1 and V2 are the indices. 5023da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencerstatic bool IndexOperandsEqual(Value *V1, Value *V2) { 50328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (V1->getType() == V2->getType()) 50428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return V1 == V2; 50528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C1 = dyn_cast<Constant>(V1)) 50628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C2 = dyn_cast<Constant>(V2)) { 5073da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // Sign extend the constants to long types, if necessary 508c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (C1->getType() != Type::Int64Ty) 509c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer C1 = ConstantExpr::getSExt(C1, Type::Int64Ty); 510c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (C2->getType() != Type::Int64Ty) 511c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer C2 = ConstantExpr::getSExt(C2, Type::Int64Ty); 51228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return C1 == C2; 51328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 51428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return false; 51528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner} 51628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner 517b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 518b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// base pointers. This checks to see if the index expressions preclude the 519b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// pointers from aliasing... 520b83eb6447ba155342598f0fabe1f08f5baa9164aReid SpencerAliasAnalysis::AliasResult 521b83eb6447ba155342598f0fabe1f08f5baa9164aReid SpencerBasicAliasAnalysis::CheckGEPInstructions( 522fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 523fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 524b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We currently can't handle the case when the base pointers have different 525b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // primitive types. Since this is uncommon anyway, we are happy being 526b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // extremely conservative. 527b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty != BasePtr2Ty) 528b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 529b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 530c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 531b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 532b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Find the (possibly empty) initial sequence of equal values... which are not 533b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // necessarily constants. 534fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 535b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 536b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 537b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned UnequalOper = 0; 538b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner while (UnequalOper != MinOperands && 5393da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper])) { 540b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance through the type as we go... 541b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner ++UnequalOper; 542b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 543b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 544b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else { 545b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If all operands equal each other, then the derived pointers must 546b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // alias each other... 547b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 548b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 549b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner "Ran out of type nesting, but not out of operands?"); 550b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MustAlias; 551920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 552920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 553920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 554b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have seen all constant operands, and run out of indexes on one of the 555b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // getelementptrs, check to see if the tail of the leftover one is all zeros. 556b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If so, return mustalias. 5574a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (UnequalOper == MinOperands) { 558fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops < NumGEP2Ops) { 559fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(GEP1Ops, GEP2Ops); 560fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 561fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 5622b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 563b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner bool AllAreZeros = true; 564b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = UnequalOper; i != MaxOperands; ++i) 565a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (!isa<Constant>(GEP1Ops[i]) || 566b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner !cast<Constant>(GEP1Ops[i])->isNullValue()) { 567b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AllAreZeros = false; 568b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner break; 569b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 570b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (AllAreZeros) return MustAlias; 571b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 572b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 5732b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 574d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // So now we know that the indexes derived from the base pointers, 575d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // which are known to alias, are different. We can still determine a 576d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // no-alias result if there are differing constant pairs in the index 577d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // chain. For example: 578d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 579d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 5805a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // We have to be careful here about array accesses. In particular, consider: 5815a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // A[1][0] vs A[0][i] 5825a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // In this case, we don't *know* that the array will be accessed in bounds: 5835a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // the index could even be negative. Because of this, we have to 5845a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // conservatively *give up* and return may alias. We disregard differing 5855a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // array subscripts that are followed by a variable index without going 5865a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // through a struct. 5875a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // 588d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned SizeMax = std::max(G1S, G2S); 589eaf8f9c667b15cf09b4608558cc24675e92ad2cdChris Lattner if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 590920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 591d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Scan for the first operand that is constant and unequal in the 59228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // two getelementptrs... 593d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned FirstConstantOper = UnequalOper; 594b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 595b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G1Oper = GEP1Ops[FirstConstantOper]; 596b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G2Oper = GEP2Ops[FirstConstantOper]; 5972b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 5986eb88d44c93f782a988039a047a9b80354a81887Chris Lattner if (G1Oper != G2Oper) // Found non-equal constant indexes... 599a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 600a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 60128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC->getType() != G2OC->getType()) { 60228977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // Sign extend both operands to long. 603c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (G1OC->getType() != Type::Int64Ty) 604c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer G1OC = ConstantExpr::getSExt(G1OC, Type::Int64Ty); 605c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (G2OC->getType() != Type::Int64Ty) 606c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer G2OC = ConstantExpr::getSExt(G2OC, Type::Int64Ty); 60728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP1Ops[FirstConstantOper] = G1OC; 60828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP2Ops[FirstConstantOper] = G2OC; 60928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 6105a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 61128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC != G2OC) { 61207a96765daedf180a7102d39fe56c499878312b7Dan Gohman // Handle the "be careful" case above: if this is an array/vector 6135a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // subscript, scan for a subsequent variable array index. 6147765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner if (isa<SequentialType>(BasePtr1Ty)) { 6157765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner const Type *NextTy = 6167765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner cast<SequentialType>(BasePtr1Ty)->getElementType(); 6175a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner bool isBadCase = false; 6185a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 6195a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner for (unsigned Idx = FirstConstantOper+1; 6207765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 6215a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 6225a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 6235a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner isBadCase = true; 6245a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner break; 6255a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 6267765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner NextTy = cast<SequentialType>(NextTy)->getElementType(); 6275a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 6285a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 6295a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (isBadCase) G1OC = 0; 6305a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 6315a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 632a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner // Make sure they are comparable (ie, not constant expressions), and 633a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner // make sure the GEP with the smaller leading constant is GEP1. 6345a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (G1OC) { 635e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 636e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer G1OC, G2OC); 6376b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 638fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (CV->getZExtValue()) { // If they are comparable and G2 > G1 6395a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 640fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 641fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 6425a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner break; 6435a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 64428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 6456eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 6466eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 647b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 648d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 6492b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 650b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // No shared constant operands, and we ran out of common operands. At this 651b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // point, the GEP instructions have run through all of their operands, and we 652b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // haven't found evidence that there are any deltas between the GEP's. 653b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // However, one GEP may have more operands than the other. If this is the 65428977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // case, there may still be hope. Check this now. 655b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (FirstConstantOper == MinOperands) { 656b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Make GEP1Ops be the longer one if there is a longer one. 657fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops < NumGEP2Ops) { 658b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner std::swap(GEP1Ops, GEP2Ops); 659fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 660fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 661b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 662b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Is there anything to check? 663fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops > MinOperands) { 664b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 6656b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (isa<ConstantInt>(GEP1Ops[i]) && 666843f0767acd05baed952d39e77ea89b438430a4fZhou Sheng !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 667b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Yup, there's a constant in the tail. Set all variables to 668b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constants in the GEP instruction to make it suiteable for 669b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // TargetData::getIndexedOffset. 670b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (i = 0; i != MaxOperands; ++i) 6710bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(GEP1Ops[i])) 672b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops[i] = Constant::getNullValue(GEP1Ops[i]->getType()); 673b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Okay, now get the offset. This is the relative offset for the full 674b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // instruction. 675b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const TargetData &TD = getTargetData(); 676fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 677fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner NumGEP1Ops); 678b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 679fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner // Now check without any constants at the end. 680fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 681fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner MinOperands); 6822b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 683b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the tail provided a bit enough offset, return noalias! 684b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if ((uint64_t)(Offset2-Offset1) >= SizeMax) 685b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return NoAlias; 686b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 687b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 6882b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 689b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Couldn't find anything useful. 690b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 691b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 692d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 693d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If there are non-equal constants arguments, then we can figure 694d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // out a minimum known delta between the two index expressions... at 695d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // this point we know that the first constant index of GEP1 is less 696d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // than the first constant index of GEP2. 697b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 698b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance BasePtr[12]Ty over this first differing constant operand. 6992cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 7002cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner getTypeAtIndex(GEP2Ops[FirstConstantOper]); 7012cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 7022cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner getTypeAtIndex(GEP1Ops[FirstConstantOper]); 7032b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 704b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We are going to be using TargetData::getIndexedOffset to determine the 705b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // offset that each of the GEP's is reaching. To do this, we have to convert 706b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // all variable references to constant references. To do this, we convert the 7072cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner // initial sequence of array subscripts into constant zeros to start with. 7082cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner const Type *ZeroIdxTy = GEPPointerTy; 7092cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner for (unsigned i = 0; i != FirstConstantOper; ++i) { 7102cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner if (!isa<StructType>(ZeroIdxTy)) 711c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Type::Int32Ty); 712b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 7132cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 7142cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 7152cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner } 7162cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner 717b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 7182b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 719d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Loop over the rest of the operands... 720b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 721fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 722fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 723b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If they are equal, use a zero index... 724b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 7250bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(Op1)) 726b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP1Ops[i] = GEP2Ops[i] = Constant::getNullValue(Op1->getType()); 727b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Otherwise, just keep the constants we have. 728d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } else { 729b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1) { 730b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 731b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 7327765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 733b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer if (Op1C->getZExtValue() >= AT->getNumElements()) 734b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 735f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) { 736f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner if (Op1C->getZExtValue() >= VT->getNumElements()) 7377765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner return MayAlias; // Be conservative with out-of-range accesses 7387765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner } 7397765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner 740b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { 741b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // GEP1 is known to produce a value less than GEP2. To be 742b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // conservatively correct, we must assume the largest possible 743b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant is used in this position. This cannot be the initial 744b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // index to the GEP instructions (because we know we have at least one 745b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // element before this one with the different constant arguments), so 746b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // we know that the current index must be into either a struct or 747b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // array. Because we know it's not constant, this cannot be a 748b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // structure index. Because of this, we can calculate the maximum 749b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // value possible. 750b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // 751b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 752241607d01648e85754f72de945684c7a8641a292Chris Lattner GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,AT->getNumElements()-1); 7539907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) 7549907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner GEP1Ops[i] = ConstantInt::get(Type::Int64Ty,VT->getNumElements()-1); 755b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 756d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 7572b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 758b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op2) { 759b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 760b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 761f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr2Ty)) { 762b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer if (Op2C->getZExtValue() >= AT->getNumElements()) 763b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 764f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr2Ty)) { 7659907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner if (Op2C->getZExtValue() >= VT->getNumElements()) 7667765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner return MayAlias; // Be conservative with out-of-range accesses 7677765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner } 768b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { // Conservatively assume the minimum value for this index 769b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner GEP2Ops[i] = Constant::getNullValue(Op2->getType()); 770b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 771920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 772b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 773b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 774b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty && Op1) { 775b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 776b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 777b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 778b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 779b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 780b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 781b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr2Ty && Op2) { 782b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 783b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 784b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 785b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = 0; 786d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 787d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 7882b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 789c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos if (GEPPointerTy->getElementType()->isSized()) { 790829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner int64_t Offset1 = 791fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 792829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner int64_t Offset2 = 793fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 7949907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner assert(Offset1 != Offset2 && 7959907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner "There is at least one different constant here!"); 7969907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner 7979907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner // Make sure we compare the absolute difference. 7989907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner if (Offset1 > Offset2) 7999907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner std::swap(Offset1, Offset2); 8009907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner 801c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 802e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Determined that these two GEP's don't alias [" 803e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 804c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos return NoAlias; 805c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos } 806d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 807d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 808d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 809d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 8104f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Make sure that anything that uses AliasAnalysis pulls in this file... 8114f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(BasicAliasAnalysis) 812