BasicAliasAnalysis.cpp revision 081c34b725980f995be9080eaec24cd3dfaaf065
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" 2130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner#include "llvm/GlobalAlias.h" 224244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/GlobalVariable.h" 23eb62bc77b68e8d2350453d15aca300f481a612d5Alkis Evlogimenos#include "llvm/Instructions.h" 249b636cb3385376faa7f33a943cac7d40bff1531aOwen Anderson#include "llvm/IntrinsicInst.h" 25b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman#include "llvm/LLVMContext.h" 263a7a68c10880c2a28387617b42d14d774e218727Dan Gohman#include "llvm/Operator.h" 274244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Pass.h" 285d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/CaptureTracking.h" 295d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/MemoryBuiltins.h" 305d5261c819fa2a203dc8d09c7bb71e041a12cd69Chris Lattner#include "llvm/Analysis/ValueTracking.h" 31d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Target/TargetData.h" 32e405c64f6b91635c8884411447ff5756c2e6b4c3Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 33a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner#include "llvm/ADT/SmallVector.h" 34c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 3530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 37ec4e8085e83fa1f14a82849548f7c1ad82009adeChris Lattnerusing namespace llvm; 38d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 39defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 40defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// Useful predicates 41defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 42defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 43defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isKnownNonNull - Return true if we know that the specified value is never 44defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// null. 45defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic bool isKnownNonNull(const Value *V) { 46defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // Alloca never returns null, malloc might. 47defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (isa<AllocaInst>(V)) return true; 48defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 49defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // A byval argument is never null. 50defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (const Argument *A = dyn_cast<Argument>(V)) 51defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return A->hasByValAttr(); 52defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 53defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // Global values are not null unless extern weak. 54defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 55defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return !GV->hasExternalWeakLinkage(); 56defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 57defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 58defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 59defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 60defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// object that never escapes from the function. 6121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool isNonEscapingLocalObject(const Value *V) { 62defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is a local allocation, check to see if it escapes. 6321de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (isa<AllocaInst>(V) || isNoAliasCall(V)) 64f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // Set StoreCaptures to True so that we can assume in our callers that the 65f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // pointer is not the result of a load instruction. Currently 66f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // PointerMayBeCaptured doesn't have any special analysis for the 67f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // StoreCaptures=false case; if it did, our callers could be refined to be 68f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman // more precise. 69f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 7091c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands 71defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is an argument that corresponds to a byval or noalias argument, 7291c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // then it has not escaped before entering the function. Check if it escapes 7391c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // inside the function. 7421de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (const Argument *A = dyn_cast<Argument>(V)) 7521de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (A->hasByValAttr() || A->hasNoAliasAttr()) { 7621de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // Don't bother analyzing arguments already known not to escape. 7721de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (A->hasNoCaptureAttr()) 7821de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return true; 7921de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true); 8021de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman } 81defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 82defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 83defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 846be2bd516a3022721480f8fee6986617baf0944fDan Gohman/// isEscapeSource - Return true if the pointer is one which would have 856be2bd516a3022721480f8fee6986617baf0944fDan Gohman/// been considered an escape by isNonEscapingLocalObject. 8621de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool isEscapeSource(const Value *V) { 8721de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V)) 8821de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return true; 896be2bd516a3022721480f8fee6986617baf0944fDan Gohman 906be2bd516a3022721480f8fee6986617baf0944fDan Gohman // The load case works because isNonEscapingLocalObject considers all 916be2bd516a3022721480f8fee6986617baf0944fDan Gohman // stores to be escapes (it passes true for the StoreCaptures argument 926be2bd516a3022721480f8fee6986617baf0944fDan Gohman // to PointerMayBeCaptured). 936be2bd516a3022721480f8fee6986617baf0944fDan Gohman if (isa<LoadInst>(V)) 946be2bd516a3022721480f8fee6986617baf0944fDan Gohman return true; 956be2bd516a3022721480f8fee6986617baf0944fDan Gohman 966be2bd516a3022721480f8fee6986617baf0944fDan Gohman return false; 976be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 98defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 99defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isObjectSmallerThan - Return true if we can prove that the object specified 100defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// by V is smaller than Size. 101defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic bool isObjectSmallerThan(const Value *V, unsigned Size, 1027b550ccfc5a3346c17e0390a59e2d6d19bc52705Chris Lattner const TargetData &TD) { 103295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner const Type *AccessTy; 104295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 105defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = GV->getType()->getElementType(); 1067b929dad59785f62a66f7c58615082f98441e95eVictor Hernandez } else if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 107defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (!AI->isArrayAllocation()) 108defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = AI->getType()->getElementType(); 109295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner else 110295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 11146e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez } else if (const CallInst* CI = extractMallocCall(V)) { 1127b550ccfc5a3346c17e0390a59e2d6d19bc52705Chris Lattner if (!isArrayMalloc(V, &TD)) 11346e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez // The size is the argument to the malloc call. 11471339c965ca6268b9bff91213364783c3d06f666Gabor Greif if (const ConstantInt* C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) 11546e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez return (C->getZExtValue() < Size); 11646e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez return false; 117295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } else if (const Argument *A = dyn_cast<Argument>(V)) { 118defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (A->hasByValAttr()) 119defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = cast<PointerType>(A->getType())->getElementType(); 120295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner else 121295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 122295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } else { 123295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 124295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } 125defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 126295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner if (AccessTy->isSized()) 127777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands return TD.getTypeAllocSize(AccessTy) < Size; 128defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 129defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 130defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 131defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 132defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// NoAA Pass 133defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 134defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 135d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnernamespace { 136b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// NoAA - This class implements the -no-aa pass, which always returns "I 137b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// don't know" for alias queries. NoAA is unlike other alias analysis 138b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// implementations, in that it does not chain to a previous analysis. As 139b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// such it doesn't follow many of the rules that other alias analyses must. 140b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// 1416726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct NoAA : public ImmutablePass, public AliasAnalysis { 1421997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 143081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson NoAA() : ImmutablePass(ID) { 144081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeNoAAPass(*PassRegistry::getPassRegistry()); 145081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 146081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson explicit NoAA(char &PID) : ImmutablePass(PID) {} 147794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 148689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 149689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 1502b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 151689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void initializePass() { 152fc2a3ed0c9e32cf7edaf5030fa0972b916cc5f0bDan Gohman TD = getAnalysisIfAvailable<TargetData>(); 153689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 154689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner 155b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, const Location &LocB) { 156b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return MayAlias; 157b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 158b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 1596ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS) { 1606ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return UnknownModRefBehavior; 1616ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1626ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(const Function *F) { 1636ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return UnknownModRefBehavior; 1646ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 1656ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 166b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual bool pointsToConstantMemory(const Location &Loc) { return false; } 16779fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 168b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 169b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 170b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 17179fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 17279fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman ImmutableCallSite CS2) { 173b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 174b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 175b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 176b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void deleteValue(Value *V) {} 177b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void copyValue(Value *From, Value *To) {} 1782033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner 1792033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 1805eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// an analysis interface through multiple inheritance. If needed, it 1815eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// should override this to adjust the this pointer as needed for the 1825eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// specified pass info. 18390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *ID) { 18490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (ID == &AliasAnalysis::ID) 1852033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return (AliasAnalysis*)this; 1862033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return this; 1872033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner } 188b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner }; 189844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} // End of anonymous namespace 1902b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 191844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Register this pass... 192844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar NoAA::ID = 0; 193d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(NoAA, AliasAnalysis, "no-aa", 194d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen Anderson "No Alias Analysis (always returns 'may' alias)", 195c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman true, true, true) 196b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 197534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 198b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 199defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 20030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner// GetElementPtr Instruction Decomposition and Analysis 20130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner//===----------------------------------------------------------------------===// 20230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 2038807e9fbdf81221b277506064c46829732f019cfChris Lattnernamespace { 2048807e9fbdf81221b277506064c46829732f019cfChris Lattner enum ExtensionKind { 2058807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_NotExtended, 2068807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_SignExt, 2078807e9fbdf81221b277506064c46829732f019cfChris Lattner EK_ZeroExt 2088807e9fbdf81221b277506064c46829732f019cfChris Lattner }; 2098807e9fbdf81221b277506064c46829732f019cfChris Lattner 2108807e9fbdf81221b277506064c46829732f019cfChris Lattner struct VariableGEPIndex { 2118807e9fbdf81221b277506064c46829732f019cfChris Lattner const Value *V; 2128807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension; 2138807e9fbdf81221b277506064c46829732f019cfChris Lattner int64_t Scale; 2148807e9fbdf81221b277506064c46829732f019cfChris Lattner }; 2158807e9fbdf81221b277506064c46829732f019cfChris Lattner} 2168807e9fbdf81221b277506064c46829732f019cfChris Lattner 21730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 21830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// GetLinearExpression - Analyze the specified value as a linear expression: 21930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// "A*V + B", where A and B are constant integers. Return the scale and offset 2202215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// values as APInts and return V as a Value*, and return whether we looked 2212215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// through any sign or zero extends. The incoming Value is known to have 2222215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// IntegerType and it may already be sign or zero extended. 2232215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// 2242215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// Note that this looks through extends, so the high bits may not be 2252215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner/// represented in the result. 22630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattnerstatic Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, 2272215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner ExtensionKind &Extension, 228ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner const TargetData &TD, unsigned Depth) { 22930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner assert(V->getType()->isIntegerTy() && "Not an integer value"); 23030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 23130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Limit our recursion depth. 23230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Depth == 6) { 23330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 1; 23430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset = 0; 23530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 23630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 23730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 23830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { 23930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 24030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner switch (BOp->getOpcode()) { 24130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner default: break; 24230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Or: 24330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // X|C == X+C if all the bits in C are unset in X. Otherwise we can't 24430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // analyze it. 245ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &TD)) 24630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 24730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // FALL THROUGH. 24830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Add: 2492215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 2502215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 25130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset += RHSC->getValue(); 25230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 25330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Mul: 2542215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 2552215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 25630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset *= RHSC->getValue(); 25730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale *= RHSC->getValue(); 25830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 25930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner case Instruction::Shl: 2602215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, 2612215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 26230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset <<= RHSC->getValue().getLimitedValue(); 26330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale <<= RHSC->getValue().getLimitedValue(); 26430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 26530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 26630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 26730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 26830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 26930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Since GEP indices are sign extended anyway, we don't care about the high 2702215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // bits of a sign or zero extended value - just scales and offsets. The 2712215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // extensions have to be consistent though. 2722215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner if ((isa<SExtInst>(V) && Extension != EK_ZeroExt) || 2732215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner (isa<ZExtInst>(V) && Extension != EK_SignExt)) { 27430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Value *CastOp = cast<CastInst>(V)->getOperand(0); 27530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned OldWidth = Scale.getBitWidth(); 27630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); 27730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale.trunc(SmallWidth); 27830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset.trunc(SmallWidth); 2792215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Extension = isa<SExtInst>(V) ? EK_SignExt : EK_ZeroExt; 2802215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 2812215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, 2822215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner TD, Depth+1); 28330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale.zext(OldWidth); 28430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset.zext(OldWidth); 2852215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 28630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return Result; 28730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 28830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 28930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 1; 29030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Offset = 0; 29130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 29230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 29330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 29430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it 29530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// into a base pointer with a constant offset and a number of scaled symbolic 29630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// offsets. 29730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 29830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// The scaled symbolic offsets (represented by pairs of a Value* and a scale in 29930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// the VarIndices vector) are Value*'s that are known to be scaled by the 30030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// specified amount, but which may have other unrepresented high bits. As such, 30130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// the gep cannot necessarily be reconstructed from its decomposed form. 30230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 30330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// When TargetData is around, this function is capable of analyzing everything 30430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// that Value::getUnderlyingObject() can look through. When not, it just looks 30530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// through pointer casts. 30630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// 30730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattnerstatic const Value * 30830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris LattnerDecomposeGEPExpression(const Value *V, int64_t &BaseOffs, 3098807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVectorImpl<VariableGEPIndex> &VarIndices, 31030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const TargetData *TD) { 31130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Limit recursion depth to limit compile time in crazy cases. 31230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned MaxLookup = 6; 31330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 31430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs = 0; 31530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner do { 31630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // See if this is a bitcast or GEP. 31730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const Operator *Op = dyn_cast<Operator>(V); 31830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Op == 0) { 31930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // The only non-operator case we can handle are GlobalAliases. 32030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 32130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!GA->mayBeOverridden()) { 32230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GA->getAliasee(); 32330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 32430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 32530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 32630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 32730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 32830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 32930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Op->getOpcode() == Instruction::BitCast) { 33030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = Op->getOperand(0); 33130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 33230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 33330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 33430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op); 33530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (GEPOp == 0) 33630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 33730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 33830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Don't attempt to analyze GEPs over unsized objects. 33930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!cast<PointerType>(GEPOp->getOperand(0)->getType()) 34030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner ->getElementType()->isSized()) 34130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 34230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 34330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we are lacking TargetData information, we can't compute the offets of 34430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // elements computed by GEPs. However, we can handle bitcast equivalent 34530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // GEPs. 346ff2efb9f9caf6669beb587aa4d65f24d3a026090Chris Lattner if (TD == 0) { 34730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (!GEPOp->hasAllZeroIndices()) 34830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 34930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GEPOp->getOperand(0); 35030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 35130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 35230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 35330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices. 35430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner gep_type_iterator GTI = gep_type_begin(GEPOp); 35530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (User::const_op_iterator I = GEPOp->op_begin()+1, 35630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner E = GEPOp->op_end(); I != E; ++I) { 35730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Value *Index = *I; 35830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Compute the (potentially symbolic) offset in bytes for this index. 35930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { 36030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // For a struct, add the member offset. 36130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 36230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (FieldNo == 0) continue; 36330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 36430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs += TD->getStructLayout(STy)->getElementOffset(FieldNo); 36530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 36630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 36730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 36830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // For an array/pointer, add the element offset, explicitly scaled. 36930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) { 37030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (CIdx->isZero()) continue; 37130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner BaseOffs += TD->getTypeAllocSize(*GTI)*CIdx->getSExtValue(); 37230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner continue; 37330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 37430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 37530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner uint64_t Scale = TD->getTypeAllocSize(*GTI); 3768807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension = EK_NotExtended; 37730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 3782215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // If the integer type is smaller than the pointer size, it is implicitly 3792215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // sign extended to pointer size. 38030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth(); 3812215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner if (TD->getPointerSizeInBits() > Width) 3822215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Extension = EK_SignExt; 3832215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner 3842215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner // Use GetLinearExpression to decompose the index into a C1*V+C2 form. 38530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner APInt IndexScale(Width, 0), IndexOffset(Width, 0); 3862215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, 3872215c607c3035be197f163beb5e7d8308f8787e5Chris Lattner *TD, 0); 38830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 38930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. 39030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. 39139e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman BaseOffs += IndexOffset.getSExtValue()*Scale; 39239e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman Scale *= IndexScale.getSExtValue(); 39330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 39430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 39530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we already had an occurrance of this index variable, merge this 39630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // scale into it. For example, we want to handle: 39730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // A[x][x] -> x*16 + x*4 -> x*20 39830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // This also ensures that 'x' only appears in the index list once. 39930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned i = 0, e = VarIndices.size(); i != e; ++i) { 4008807e9fbdf81221b277506064c46829732f019cfChris Lattner if (VarIndices[i].V == Index && 4018807e9fbdf81221b277506064c46829732f019cfChris Lattner VarIndices[i].Extension == Extension) { 4028807e9fbdf81221b277506064c46829732f019cfChris Lattner Scale += VarIndices[i].Scale; 40330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner VarIndices.erase(VarIndices.begin()+i); 40430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 40530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 40630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 40730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 40830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Make sure that we have a scale that makes sense for this target's 40930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // pointer size. 41030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (unsigned ShiftBits = 64-TD->getPointerSizeInBits()) { 41130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale <<= ShiftBits; 41239e30124e50534972c2e58f4dab7d67c0c437743Eli Friedman Scale = (int64_t)Scale >> ShiftBits; 41330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 41430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 4158807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Scale) { 4168807e9fbdf81221b277506064c46829732f019cfChris Lattner VariableGEPIndex Entry = {Index, Extension, Scale}; 4178807e9fbdf81221b277506064c46829732f019cfChris Lattner VarIndices.push_back(Entry); 4188807e9fbdf81221b277506064c46829732f019cfChris Lattner } 41930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 42030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 42130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Analyze the base pointer next. 42230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner V = GEPOp->getOperand(0); 42330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } while (--MaxLookup); 42430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 42530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If the chain of expressions is too deep, just return early. 42630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner return V; 42730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 42830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 42930963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// GetIndexDifference - Dest and Src are the variable indices from two 43030963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// decomposed GetElementPtr instructions GEP1 and GEP2 which have common base 43130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// pointers. Subtract the GEP2 indices from GEP1 to find the symbolic 43230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner/// difference between the two pointers. 4338807e9fbdf81221b277506064c46829732f019cfChris Lattnerstatic void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest, 4348807e9fbdf81221b277506064c46829732f019cfChris Lattner const SmallVectorImpl<VariableGEPIndex> &Src) { 43530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner if (Src.empty()) return; 43630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 43730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned i = 0, e = Src.size(); i != e; ++i) { 4388807e9fbdf81221b277506064c46829732f019cfChris Lattner const Value *V = Src[i].V; 4398807e9fbdf81221b277506064c46829732f019cfChris Lattner ExtensionKind Extension = Src[i].Extension; 4408807e9fbdf81221b277506064c46829732f019cfChris Lattner int64_t Scale = Src[i].Scale; 44130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 44230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // Find V in Dest. This is N^2, but pointer indices almost never have more 44330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // than a few variable indexes. 44430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner for (unsigned j = 0, e = Dest.size(); j != e; ++j) { 4458807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Dest[j].V != V || Dest[j].Extension != Extension) continue; 44630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 44730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we found it, subtract off Scale V's from the entry in Dest. If it 44830963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // goes to zero, remove the entry. 4498807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Dest[j].Scale != Scale) 4508807e9fbdf81221b277506064c46829732f019cfChris Lattner Dest[j].Scale -= Scale; 45130963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner else 45230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Dest.erase(Dest.begin()+j); 45330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner Scale = 0; 45430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner break; 45530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 45630963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 45730963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner // If we didn't consume this entry, add it to the end of the Dest list. 4588807e9fbdf81221b277506064c46829732f019cfChris Lattner if (Scale) { 4598807e9fbdf81221b277506064c46829732f019cfChris Lattner VariableGEPIndex Entry = { V, Extension, -Scale }; 4608807e9fbdf81221b277506064c46829732f019cfChris Lattner Dest.push_back(Entry); 4618807e9fbdf81221b277506064c46829732f019cfChris Lattner } 46230963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner } 46330963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner} 46430963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner 46530963fbe8fa0ba3a4cc35c7c6e8f24c772f1b40cChris Lattner//===----------------------------------------------------------------------===// 4666be2bd516a3022721480f8fee6986617baf0944fDan Gohman// BasicAliasAnalysis Pass 467defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 468defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 4699e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman#ifndef NDEBUG 4706be2bd516a3022721480f8fee6986617baf0944fDan Gohmanstatic const Function *getParent(const Value *V) { 4716f205cbceb487b327708faf7ad25007b754dcf36Dan Gohman if (const Instruction *inst = dyn_cast<Instruction>(V)) 4726be2bd516a3022721480f8fee6986617baf0944fDan Gohman return inst->getParent()->getParent(); 4736be2bd516a3022721480f8fee6986617baf0944fDan Gohman 4746f205cbceb487b327708faf7ad25007b754dcf36Dan Gohman if (const Argument *arg = dyn_cast<Argument>(V)) 4756be2bd516a3022721480f8fee6986617baf0944fDan Gohman return arg->getParent(); 4766be2bd516a3022721480f8fee6986617baf0944fDan Gohman 4776be2bd516a3022721480f8fee6986617baf0944fDan Gohman return NULL; 4786be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 4796be2bd516a3022721480f8fee6986617baf0944fDan Gohman 48021de4c0daf2b35963d16541a3007c543237eb7bfDan Gohmanstatic bool notDifferentParent(const Value *O1, const Value *O2) { 48121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman 48221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman const Function *F1 = getParent(O1); 48321de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman const Function *F2 = getParent(O2); 48421de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman 4856be2bd516a3022721480f8fee6986617baf0944fDan Gohman return !F1 || !F2 || F1 == F2; 4866be2bd516a3022721480f8fee6986617baf0944fDan Gohman} 4873432d70d5b48164f0adaec0771c89c54408e2be9Benjamin Kramer#endif 4886be2bd516a3022721480f8fee6986617baf0944fDan Gohman 489b52f44086006434039b0c5df55aaac1079d26b96Chris Lattnernamespace { 490b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// BasicAliasAnalysis - This is the default alias analysis implementation. 491b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 492b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// derives from the NoAA class. 4936726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct BasicAliasAnalysis : public NoAA { 4941997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 495081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson BasicAliasAnalysis() : NoAA(ID) { 496081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeBasicAliasAnalysisPass(*PassRegistry::getPassRegistry()); 497081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 4986be2bd516a3022721480f8fee6986617baf0944fDan Gohman 499c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman virtual void initializePass() { 500c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman InitializeAliasAnalysis(this); 501c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 502c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman 503c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 504c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman AU.addRequired<AliasAnalysis>(); 505c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 506c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman 507b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual AliasResult alias(const Location &LocA, 508b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &LocB) { 50950f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman assert(Visited.empty() && "Visited must be cleared after use!"); 510b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && 5119e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman "BasicAliasAnalysis doesn't support interprocedural queries."); 5126cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.TBAATag, 5136cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman LocB.Ptr, LocB.Size, LocB.TBAATag); 51450f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman Visited.clear(); 515f0429fd1ca7f6d359a33c20617785d7572a0292dEvan Cheng return Alias; 51650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 517bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 5186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 519b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc); 5206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 5216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 5226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ImmutableCallSite CS2) { 5236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // The AliasAnalysis base class has some smarts, lets use them. 5246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return AliasAnalysis::getModRefInfo(CS1, CS2); 5256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 526e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 527bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// pointsToConstantMemory - Chase pointers until we find a (constant 528bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// global) or not. 529b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman virtual bool pointsToConstantMemory(const Location &Loc); 5306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 5316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// getModRefBehavior - Return the behavior when calling the given 5326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// call site. 5336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 5346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 5356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// getModRefBehavior - Return the behavior when calling the given function. 5366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman /// For use when the call site is not known. 5376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman virtual ModRefBehavior getModRefBehavior(const Function *F); 538bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 5392033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner /// getAdjustedAnalysisPointer - This method is used when a pass implements 5405eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// an analysis interface through multiple inheritance. If needed, it 5415eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// should override this to adjust the this pointer as needed for the 5425eeb19d189fd448293e607227e5564d2efab0f7fDan Gohman /// specified pass info. 54390c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson virtual void *getAdjustedAnalysisPointer(const void *ID) { 54490c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson if (ID == &AliasAnalysis::ID) 5452033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return (AliasAnalysis*)this; 5462033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner return this; 5472033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner } 5482033097b1f5b1889a5d801febbc7848c7b8ca439Chris Lattner 549d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner private: 55050f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // Visited - Track instructions visited by a aliasPHI, aliasSelect(), and aliasGEP(). 55150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman SmallPtrSet<const Value*, 16> Visited; 5523dbe43b1b50472f4f24df17fff5ac2443be63d5fEvan Cheng 5535d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP 5545d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // instruction against another. 555539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner AliasResult aliasGEP(const GEPOperator *V1, unsigned V1Size, 55623e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *V2, unsigned V2Size, 5576cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo, 55823e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV1, const Value *UnderlyingV2); 55950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 5605d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI 5615d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner // instruction against another. 562d83c2ca3368f90d60234848e751842d29b248039Evan Cheng AliasResult aliasPHI(const PHINode *PN, unsigned PNSize, 5636cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *PNTBAAInfo, 5646cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 5656cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo); 56650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 5676665b0ea688941c1c044a5c034ee45d45862168fDan Gohman /// aliasSelect - Disambiguate a Select instruction against another value. 5686665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult aliasSelect(const SelectInst *SI, unsigned SISize, 5696cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *SITBAAInfo, 5706cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 5716cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo); 5726665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 57350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng AliasResult aliasCheck(const Value *V1, unsigned V1Size, 5746cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V1TBAATag, 5756cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 5766cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAATag); 577d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner }; 578844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} // End of anonymous namespace 5792b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 580844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Register this pass... 581844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BasicAliasAnalysis::ID = 0; 582d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen AndersonINITIALIZE_AG_PASS(BasicAliasAnalysis, AliasAnalysis, "basicaa", 583d8cc7be0262092882d848a1c7d8a4cb6752cce6fOwen Anderson "Basic Alias Analysis (default AA impl)", 584c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman false, true, false) 585d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 586534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createBasicAliasAnalysisPass() { 587534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen return new BasicAliasAnalysis(); 588534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen} 589534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 5904a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 591bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// pointsToConstantMemory - Chase pointers until we find a (constant 592bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// global) or not. 593b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohmanbool BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc) { 594a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (const GlobalVariable *GV = 595b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman dyn_cast<GlobalVariable>(Loc.Ptr->getUnderlyingObject())) 596b27db37ed05a846bd2e0fcdaf592e5bb1a573f8bChris Lattner // Note: this doesn't require GV to be "ODR" because it isn't legal for a 597b27db37ed05a846bd2e0fcdaf592e5bb1a573f8bChris Lattner // global to be marked constant in some modules and non-constant in others. 598b27db37ed05a846bd2e0fcdaf592e5bb1a573f8bChris Lattner // GV may even be a declaration, not a definition. 599a413960a4847b996e48ebad5c41f094df441641dChris Lattner return GV->isConstant(); 6006ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 601c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman return AliasAnalysis::pointsToConstantMemory(Loc); 602bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner} 6034a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 6046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// getModRefBehavior - Return the behavior when calling the given call site. 6056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 6066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanBasicAliasAnalysis::getModRefBehavior(ImmutableCallSite CS) { 6076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS.doesNotAccessMemory()) 6086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Can't do better than this. 6096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return DoesNotAccessMemory; 6106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman ModRefBehavior Min = UnknownModRefBehavior; 6126ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // If the callsite knows it only reads memory, don't return worse 6146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // than that. 6156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (CS.onlyReadsMemory()) 6166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Min = OnlyReadsMemory; 6176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // The AliasAnalysis base class has some smarts, lets use them. 6196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return std::min(AliasAnalysis::getModRefBehavior(CS), Min); 6206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 6216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 6226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// getModRefBehavior - Return the behavior when calling the given function. 6236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman/// For use when the call site is not known. 6246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanAliasAnalysis::ModRefBehavior 6256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan GohmanBasicAliasAnalysis::getModRefBehavior(const Function *F) { 6266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (F->doesNotAccessMemory()) 6276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Can't do better than this. 6286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return DoesNotAccessMemory; 6296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (F->onlyReadsMemory()) 6306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return OnlyReadsMemory; 6316ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (unsigned id = F->getIntrinsicID()) 6326ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return getIntrinsicModRefBehavior(id); 6336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman 634c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman return AliasAnalysis::getModRefBehavior(F); 6356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman} 636e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 6375d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// getModRefInfo - Check to see if the specified callsite can clobber the 6385d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// specified memory object. Since we only look at local properties of this 6395d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// function, we really can't say much about this query. We do, however, use 6405d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// simple "address taken" analysis on local objects. 64104b75935462642641469fb264aab9f1110ce2666Chris LattnerAliasAnalysis::ModRefResult 64279fca6fea87be7221843031870bbf2c9ae1fc555Dan GohmanBasicAliasAnalysis::getModRefInfo(ImmutableCallSite CS, 643b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Location &Loc) { 644b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) && 6459e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman "AliasAnalysis query involving multiple functions!"); 6469e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman 647b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman const Value *Object = Loc.Ptr->getUnderlyingObject(); 64892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 649b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If this is a tail call and Loc.Ptr points to a stack location, we know that 65092e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // the tail call cannot access or modify the local stack. 65192e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // We cannot exclude byval arguments here; these belong to the caller of 65292e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // the current function not to the current function, and a tail callee 65392e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // may reference them. 65492e803c2a412cda777535e4ae01fe78007997f8aChris Lattner if (isa<AllocaInst>(Object)) 65579fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 65692e803c2a412cda777535e4ae01fe78007997f8aChris Lattner if (CI->isTailCall()) 65792e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 65892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 65992e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // If the pointer is to a locally allocated object that does not escape, 660b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // then the call can not mod/ref the pointer unless the call takes the pointer 661b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // as an argument, and itself doesn't capture it. 662403ac2ece33046c58b66fffa105184f44fa4527eChris Lattner if (!isa<Constant>(Object) && CS.getInstruction() != Object && 66321de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman isNonEscapingLocalObject(Object)) { 664b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner bool PassedAsArg = false; 665b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner unsigned ArgNo = 0; 66679fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 667b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner CI != CE; ++CI, ++ArgNo) { 668b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // Only look at the no-capture pointer arguments. 6691df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!(*CI)->getType()->isPointerTy() || 670b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner !CS.paramHasAttr(ArgNo+1, Attribute::NoCapture)) 671b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner continue; 672b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner 673b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman // If this is a no-capture pointer argument, see if we can tell that it 674b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // is impossible to alias the pointer we're checking. If not, we have to 675b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // assume that the call could touch the pointer, even though it doesn't 676b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner // escape. 677b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (!isNoAlias(Location(cast<Value>(CI)), Loc)) { 678b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner PassedAsArg = true; 679b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner break; 680b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner } 681b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner } 682a413960a4847b996e48ebad5c41f094df441641dChris Lattner 683b34b82e9d1ec6ddbdc23dfd9bb65cd9d22527cd2Chris Lattner if (!PassedAsArg) 68492e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 68592e803c2a412cda777535e4ae01fe78007997f8aChris Lattner } 68692e803c2a412cda777535e4ae01fe78007997f8aChris Lattner 68792e803c2a412cda777535e4ae01fe78007997f8aChris Lattner // Finally, handle specific knowledge of intrinsics. 68879fca6fea87be7221843031870bbf2c9ae1fc555Dan Gohman const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()); 6896ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (II != 0) 6906ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman switch (II->getIntrinsicID()) { 6916ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman default: break; 6926ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memcpy: 6936ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memmove: { 6946ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman unsigned Len = UnknownSize; 6956ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) 6966ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Len = LenCI->getZExtValue(); 69771339c965ca6268b9bff91213364783c3d06f666Gabor Greif Value *Dest = II->getArgOperand(0); 6986ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Value *Src = II->getArgOperand(1); 699b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Dest, Len), Loc)) { 700b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Src, Len), Loc)) 7016ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 7026ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return Ref; 7036ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7046ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7056ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7066ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::memset: 7076ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // Since memset is 'accesses arguments' only, the AliasAnalysis base class 7086ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman // will handle it for the variable length case. 7096ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (ConstantInt *LenCI = dyn_cast<ConstantInt>(II->getArgOperand(2))) { 7106ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman unsigned Len = LenCI->getZExtValue(); 7116ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Value *Dest = II->getArgOperand(0); 712b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Dest, Len), Loc)) 7136ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 7146ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7156ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7166ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_cmp_swap: 7176ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_swap: 7186ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_add: 7196ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_sub: 7206ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_and: 7216ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_nand: 7226ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_or: 7236ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_xor: 7246ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_max: 7256ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_min: 7266ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_umax: 7276ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::atomic_load_umin: 7286ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman if (TD) { 7296ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman Value *Op1 = II->getArgOperand(0); 7306ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman unsigned Op1Size = TD->getTypeStoreSize(Op1->getType()); 731b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman MDNode *Tag = II->getMetadata(LLVMContext::MD_tbaa); 732b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(Op1, Op1Size, Tag), Loc)) 7336ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman return NoModRef; 7346ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 7356ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7366ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::lifetime_start: 7376ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::lifetime_end: 7386ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::invariant_start: { 7396ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman unsigned PtrSize = 7406ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 741b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(II->getArgOperand(1), 742b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman PtrSize, 743b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 744b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 74592e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 7466ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7475c9be67cffd689fa0e2111a3c60d7556c07b8608Nick Lewycky } 7486ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman case Intrinsic::invariant_end: { 7496ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman unsigned PtrSize = 7506ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman cast<ConstantInt>(II->getArgOperand(1))->getZExtValue(); 751b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman if (isNoAlias(Location(II->getArgOperand(2), 752b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman PtrSize, 753b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)), 754b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman Loc)) 75592e803c2a412cda777535e4ae01fe78007997f8aChris Lattner return NoModRef; 7566ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman break; 7576ce9d8b0edaf7c59f5a7c52d506c2801004698f0Dan Gohman } 75892e803c2a412cda777535e4ae01fe78007997f8aChris Lattner } 75904b75935462642641469fb264aab9f1110ce2666Chris Lattner 760bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // The AliasAnalysis base class has some smarts, lets use them. 761b2143b6247901ae4eca2192ee134564c4f5f7853Dan Gohman return AliasAnalysis::getModRefInfo(CS, Loc); 76265924111bf648db8f20599f485be918c7aa1e7efDan Gohman} 763a413960a4847b996e48ebad5c41f094df441641dChris Lattner 764539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction 765539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// against another pointer. We know that V1 is a GEP, but we don't know 76623e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner/// anything about V2. UnderlyingV1 is GEP1->getUnderlyingObject(), 76723e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner/// UnderlyingV2 is the same for V2. 768539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner/// 769d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerAliasAnalysis::AliasResult 770539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris LattnerBasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, unsigned V1Size, 77123e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *V2, unsigned V2Size, 7726cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo, 77323e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV1, 77423e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner const Value *UnderlyingV2) { 77550f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // If this GEP has been visited before, we're on a use-def cycle. 77650f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // Such cycles are only valid when PHI nodes are involved or in unreachable 77750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // code. The visitPHI function catches cycles containing PHIs, but there 77850f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // could still be a cycle without PHIs in unreachable code. 77950f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman if (!Visited.insert(GEP1)) 78050f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman return MayAlias; 78150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 782d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner int64_t GEP1BaseOffset; 7838807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVector<VariableGEPIndex, 4> GEP1VariableIndices; 784d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 785b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have two gep instructions with must-alias'ing base pointers, figure 786b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // out if the indexes to the GEP tell us anything about the derived pointer. 787539c9b99c27c0fe4f22a0498bc65334e4aa72ef0Chris Lattner if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) { 788b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Do the base pointers alias? 7896cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult BaseAlias = aliasCheck(UnderlyingV1, UnknownSize, 0, 7906cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman UnderlyingV2, UnknownSize, 0); 791d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 792d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If we get a No or May, then return it immediately, no amount of analysis 793d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // will improve this situation. 794d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (BaseAlias != MustAlias) return BaseAlias; 795d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 796d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Otherwise, we have a MustAlias. Since the base pointers alias each other 797d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // exactly, see if the computed offset from the common pointer tells us 798d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // about the relation of the resulting pointer. 799d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP1BasePtr = 800d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 801d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 802d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner int64_t GEP2BaseOffset; 8038807e9fbdf81221b277506064c46829732f019cfChris Lattner SmallVector<VariableGEPIndex, 4> GEP2VariableIndices; 804d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP2BasePtr = 805d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, TD); 806d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 807d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If DecomposeGEPExpression isn't able to look all the way through the 808d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // addressing operation, we must not have TD and this is too complex for us 809d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // to handle without it. 810d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { 811d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner assert(TD == 0 && 812d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner "DecomposeGEPExpression and getUnderlyingObject disagree!"); 813d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 814b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 815d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 816d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Subtract the GEP2 pointer from the GEP1 pointer to find out their 817d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // symbolic difference. 818d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner GEP1BaseOffset -= GEP2BaseOffset; 8196fc24467e91a2c515fa5347e90071573c454bccaDan Gohman GetIndexDifference(GEP1VariableIndices, GEP2VariableIndices); 820d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 821d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner } else { 822d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // Check to see if these two pointers are related by the getelementptr 823d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // instruction. If one pointer is a GEP with a non-zero index of the other 824d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // pointer, we know they cannot alias. 8255369250b73e172efe886b20bfcdab74e5b251a71Chris Lattner 8265369250b73e172efe886b20bfcdab74e5b251a71Chris Lattner // If both accesses are unknown size, we can't do anything useful here. 827ef1cfac9e50def9097cd3e3ab3c5cad7f4c758ccDan Gohman if (V1Size == UnknownSize && V2Size == UnknownSize) 828d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 829681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng 8306cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult R = aliasCheck(UnderlyingV1, UnknownSize, 0, 8316cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 832d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (R != MustAlias) 833d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If V2 may alias GEP base pointer, conservatively returns MayAlias. 834d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If V2 is known not to alias GEP base pointer, then the two values 835d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // cannot alias per GEP semantics: "A pointer value formed from a 836d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // getelementptr instruction is associated with the addresses associated 837d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // with the first operand of the getelementptr". 838d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return R; 839d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 840d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner const Value *GEP1BasePtr = 841d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, TD); 842d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner 843d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // If DecomposeGEPExpression isn't able to look all the way through the 844d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // addressing operation, we must not have TD and this is too complex for us 845d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // to handle without it. 846d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BasePtr != UnderlyingV1) { 847d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner assert(TD == 0 && 848d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner "DecomposeGEPExpression and getUnderlyingObject disagree!"); 849d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner return MayAlias; 850d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner } 85123e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner } 85223e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner 853d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // In the two GEP Case, if there is no difference in the offsets of the 854d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // computed pointers, the resultant pointers are a must alias. This 855d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // hapens when we have two lexically identical GEP's (for example). 856d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // 857d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 858d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner // must aliases the GEP, the end result is a must alias also. 859d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner if (GEP1BaseOffset == 0 && GEP1VariableIndices.empty()) 860681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng return MustAlias; 861681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng 8624e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // If we have a known constant offset, see if this offset is larger than the 8634e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // access size being queried. If so, and if no variable indices can remove 8644e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // pieces of this constant, then we know we have a no-alias. For example, 8654e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // &A[100] != &A. 8664e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner 8674e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // In order to handle cases like &A[100][i] where i is an out of range 8684e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // subscript, we have to ignore all constant offset pieces that are a multiple 8694e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // of a scaled index. Do this by removing constant offsets that are a 8704e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // multiple of any of our variable indices. This allows us to transform 8714e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // things like &A[i][1] because i has a stride of (e.g.) 8 bytes but the 1 8724e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // provides an offset of 4 bytes (assuming a <= 4 byte access). 873d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner for (unsigned i = 0, e = GEP1VariableIndices.size(); 874d84eb911a9f9c5b16fb6a737289a98651b94ce7fChris Lattner i != e && GEP1BaseOffset;++i) 8758807e9fbdf81221b277506064c46829732f019cfChris Lattner if (int64_t RemovedOffset = GEP1BaseOffset/GEP1VariableIndices[i].Scale) 8768807e9fbdf81221b277506064c46829732f019cfChris Lattner GEP1BaseOffset -= RemovedOffset*GEP1VariableIndices[i].Scale; 8774e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner 8784e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // If our known offset is bigger than the access size, we know we don't have 8794e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // an alias. 8804e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner if (GEP1BaseOffset) { 8814e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner if (GEP1BaseOffset >= (int64_t)V2Size || 8824e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner GEP1BaseOffset <= -(int64_t)V1Size) 883681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng return NoAlias; 884094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng } 8854e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner 886094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return MayAlias; 887094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng} 888094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 8895d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// aliasSelect - Provide a bunch of ad-hoc rules to disambiguate a Select 8905d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner/// instruction against another. 8916665b0ea688941c1c044a5c034ee45d45862168fDan GohmanAliasAnalysis::AliasResult 8926665b0ea688941c1c044a5c034ee45d45862168fDan GohmanBasicAliasAnalysis::aliasSelect(const SelectInst *SI, unsigned SISize, 8936cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *SITBAAInfo, 8946cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 8956cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 89650f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // If this select has been visited before, we're on a use-def cycle. 89750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // Such cycles are only valid when PHI nodes are involved or in unreachable 89850f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // code. The visitPHI function catches cycles containing PHIs, but there 89950f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // could still be a cycle without PHIs in unreachable code. 90050f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman if (!Visited.insert(SI)) 90150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman return MayAlias; 90250f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 9036665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If the values are Selects with the same condition, we can do a more precise 9046665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // check: just check for aliases between the values on corresponding arms. 9056665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) 9066665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (SI->getCondition() == SI2->getCondition()) { 9076665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 9086cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(SI->getTrueValue(), SISize, SITBAAInfo, 9096cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman SI2->getTrueValue(), V2Size, V2TBAAInfo); 9106665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 9116665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 9126665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 9136cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(SI->getFalseValue(), SISize, SITBAAInfo, 9146cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman SI2->getFalseValue(), V2Size, V2TBAAInfo); 9156665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (ThisAlias != Alias) 9166665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 9176665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return Alias; 9186665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 9196665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 9206665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If both arms of the Select node NoAlias or MustAlias V2, then returns 9216665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // NoAlias / MustAlias. Otherwise, returns MayAlias. 9226665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 9236cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getTrueValue(), SISize, SITBAAInfo); 9246665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 9256665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 92650f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 92750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // If V2 is visited, the recursive case will have been caught in the 92850f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // above aliasCheck call, so these subsequent calls to aliasCheck 92950f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // don't need to assume that V2 is being visited recursively. 93050f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman Visited.erase(V2); 93150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman 9326665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 9336cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(V2, V2Size, V2TBAAInfo, SI->getFalseValue(), SISize, SITBAAInfo); 9346665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (ThisAlias != Alias) 9356665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 9366665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return Alias; 9376665b0ea688941c1c044a5c034ee45d45862168fDan Gohman} 9386665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 939d83c2ca3368f90d60234848e751842d29b248039Evan Cheng// aliasPHI - Provide a bunch of ad-hoc rules to disambiguate a PHI instruction 9403dbe43b1b50472f4f24df17fff5ac2443be63d5fEvan Cheng// against another. 94150a5914e129c348e8878d4654b4306e0349281c2Evan ChengAliasAnalysis::AliasResult 942d83c2ca3368f90d60234848e751842d29b248039Evan ChengBasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize, 9436cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *PNTBAAInfo, 9446cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 9456cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 94650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // The PHI node has already been visited, avoid recursion any further. 94750f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman if (!Visited.insert(PN)) 94850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return MayAlias; 94950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 9506665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // If the values are PHIs in the same block, we can do a more precise 9516665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // as well as efficient check: just check for aliases between the values 9526665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // on corresponding edges. 9536665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (const PHINode *PN2 = dyn_cast<PHINode>(V2)) 9546665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (PN2->getParent() == PN->getParent()) { 9556665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult Alias = 9566cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(PN->getIncomingValue(0), PNSize, PNTBAAInfo, 9576665b0ea688941c1c044a5c034ee45d45862168fDan Gohman PN2->getIncomingValueForBlock(PN->getIncomingBlock(0)), 9586cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2Size, V2TBAAInfo); 9596665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (Alias == MayAlias) 9606665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 9616665b0ea688941c1c044a5c034ee45d45862168fDan Gohman for (unsigned i = 1, e = PN->getNumIncomingValues(); i != e; ++i) { 9626665b0ea688941c1c044a5c034ee45d45862168fDan Gohman AliasResult ThisAlias = 9636cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman aliasCheck(PN->getIncomingValue(i), PNSize, PNTBAAInfo, 9646665b0ea688941c1c044a5c034ee45d45862168fDan Gohman PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), 9656cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2Size, V2TBAAInfo); 9666665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (ThisAlias != Alias) 9676665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return MayAlias; 9686665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 9696665b0ea688941c1c044a5c034ee45d45862168fDan Gohman return Alias; 9706665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 9716665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 972a846a8a1dcb8ab28e75e364c0cf0272634d023f2Evan Cheng SmallPtrSet<Value*, 4> UniqueSrc; 97350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng SmallVector<Value*, 4> V1Srcs; 97450a5914e129c348e8878d4654b4306e0349281c2Evan Cheng for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 97550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng Value *PV1 = PN->getIncomingValue(i); 97650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (isa<PHINode>(PV1)) 97750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // If any of the source itself is a PHI, return MayAlias conservatively 978681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // to avoid compile time explosion. The worst possible case is if both 979681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // sides are PHI nodes. In which case, this is O(m x n) time where 'm' 980681a33e26dd3222477f13520b94e7417bff59e32Evan Cheng // and 'n' are the number of PHI sources. 98150a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return MayAlias; 98250a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (UniqueSrc.insert(PV1)) 98350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng V1Srcs.push_back(PV1); 98450a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 98550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 9866cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Alias = aliasCheck(V2, V2Size, V2TBAAInfo, 9876cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V1Srcs[0], PNSize, PNTBAAInfo); 988d83c2ca3368f90d60234848e751842d29b248039Evan Cheng // Early exit if the check of the first PHI source against V2 is MayAlias. 989d83c2ca3368f90d60234848e751842d29b248039Evan Cheng // Other results are not possible. 990d83c2ca3368f90d60234848e751842d29b248039Evan Cheng if (Alias == MayAlias) 991d83c2ca3368f90d60234848e751842d29b248039Evan Cheng return MayAlias; 992d83c2ca3368f90d60234848e751842d29b248039Evan Cheng 99350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // If all sources of the PHI node NoAlias or MustAlias V2, then returns 99450a5914e129c348e8878d4654b4306e0349281c2Evan Cheng // NoAlias / MustAlias. Otherwise, returns MayAlias. 99550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) { 99650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng Value *V = V1Srcs[i]; 9976665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 99850f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman // If V2 is visited, the recursive case will have been caught in the 9996665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // above aliasCheck call, so these subsequent calls to aliasCheck 10006665b0ea688941c1c044a5c034ee45d45862168fDan Gohman // don't need to assume that V2 is being visited recursively. 100150f424c3d079d4774bb323de1e0b77cf4627be69Dan Gohman Visited.erase(V2); 10026665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 10036cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult ThisAlias = aliasCheck(V2, V2Size, V2TBAAInfo, 10046cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V, PNSize, PNTBAAInfo); 1005d83c2ca3368f90d60234848e751842d29b248039Evan Cheng if (ThisAlias != Alias || ThisAlias == MayAlias) 100650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return MayAlias; 100750a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 100850a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 100950a5914e129c348e8878d4654b4306e0349281c2Evan Cheng return Alias; 101050a5914e129c348e8878d4654b4306e0349281c2Evan Cheng} 101150a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 101250a5914e129c348e8878d4654b4306e0349281c2Evan Cheng// aliasCheck - Provide a bunch of ad-hoc rules to disambiguate in common cases, 101350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng// such as array references. 1014094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng// 1015094f04b429c11547ed98d7a53dd3399db51083bdEvan ChengAliasAnalysis::AliasResult 101650a5914e129c348e8878d4654b4306e0349281c2Evan ChengBasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size, 10176cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V1TBAAInfo, 10186cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const Value *V2, unsigned V2Size, 10196cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman const MDNode *V2TBAAInfo) { 1020b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman // If either of the memory references is empty, it doesn't matter what the 1021b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman // pointer values are. 1022b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman if (V1Size == 0 || V2Size == 0) 1023b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman return NoAlias; 1024b57b6f1575ec87b22dc793fe03539cae9df0e586Dan Gohman 1025094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Strip off any casts if they exist. 1026094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng V1 = V1->stripPointerCasts(); 1027094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng V2 = V2->stripPointerCasts(); 1028094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1029094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Are we checking for alias of the same value? 1030094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (V1 == V2) return MustAlias; 1031094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 10321df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) 1033094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; // Scalars cannot alias each other 1034094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1035094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Figure out what objects these things are pointing to if we can. 1036094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng const Value *O1 = V1->getUnderlyingObject(); 1037094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng const Value *O2 = V2->getUnderlyingObject(); 1038094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1039f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman // Null values in the default address space don't point to any object, so they 1040f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman // don't alias any other pointer. 1041f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) 1042f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (CPN->getType()->getAddressSpace() == 0) 1043f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman return NoAlias; 1044f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) 1045f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman if (CPN->getType()->getAddressSpace() == 0) 1046f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman return NoAlias; 1047f75ef668a7d35d361e797b7b160008b37d62f15cDan Gohman 1048094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (O1 != O2) { 1049094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // If V1/V2 point to two different objects we know that we have no alias. 10509e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 1051094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 105220162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky 105320162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky // Constant pointers can't alias with non-const isIdentifiedObject objects. 10549e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || 10559e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) 105620162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky return NoAlias; 105720162ac5662a45388911ef1d35ba7559aae368f5Nick Lewycky 105821de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // Arguments can't alias with local allocations or noalias calls 105921de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman // in the same function. 10609e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if (((isa<Argument>(O1) && (isa<AllocaInst>(O2) || isNoAliasCall(O2))) || 106121de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman (isa<Argument>(O2) && (isa<AllocaInst>(O1) || isNoAliasCall(O1))))) 106221de4c0daf2b35963d16541a3007c543237eb7bfDan Gohman return NoAlias; 1063094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1064094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // Most objects can't alias null. 10659e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) || 10669e86f4364b912ae743490ba01d6989acfd12c046Dan Gohman (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2))) 1067094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 1068094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 1069b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // If one pointer is the result of a call/invoke or load and the other is a 1070b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // non-escaping local object within the same function, then we know the 1071b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // object couldn't escape to a point where the call could return it. 1072b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // 1073b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // Note that if the pointers are in different functions, there are a 1074b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // variety of complications. A call with a nocapture argument may still 1075b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // temporary store the nocapture argument's value in a temporary memory 1076b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // location if that memory location doesn't escape. Or it may pass a 1077b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman // nocapture value to other functions as long as they don't capture it. 1078b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman if (isEscapeSource(O1) && isNonEscapingLocalObject(O2)) 1079b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman return NoAlias; 1080b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman if (isEscapeSource(O2) && isNonEscapingLocalObject(O1)) 1081b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman return NoAlias; 1082b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman } 1083b8c86a010c2d958d6f655b0f66101d8964d7a0fcDan Gohman 1084094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // If the size of one access is larger than the entire object on the other 1085094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng // side, then we know such behavior is undefined and can assume no alias. 1086094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng if (TD) 1087ef1cfac9e50def9097cd3e3ab3c5cad7f4c758ccDan Gohman if ((V1Size != UnknownSize && isObjectSmallerThan(O2, V1Size, *TD)) || 1088ef1cfac9e50def9097cd3e3ab3c5cad7f4c758ccDan Gohman (V2Size != UnknownSize && isObjectSmallerThan(O1, V2Size, *TD))) 1089094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng return NoAlias; 1090094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng 10914e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the 10924e91ee7a2a80142c3774a9984f92a3fae1c126e7Chris Lattner // GEP can't simplify, we don't even look at the PHI cases. 1093391d23b6c29e17b5c969e732169a789ac9d0d422Chris Lattner if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) { 1094094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng std::swap(V1, V2); 1095094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng std::swap(V1Size, V2Size); 109623e2a5b2fff8b5b483a464ce1bea9a686e6731deChris Lattner std::swap(O1, O2); 1097094f04b429c11547ed98d7a53dd3399db51083bdEvan Cheng } 1098c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { 10996cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, V2TBAAInfo, O1, O2); 1100c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (Result != MayAlias) return Result; 1101c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 110250a5914e129c348e8878d4654b4306e0349281c2Evan Cheng 110350a5914e129c348e8878d4654b4306e0349281c2Evan Cheng if (isa<PHINode>(V2) && !isa<PHINode>(V1)) { 110450a5914e129c348e8878d4654b4306e0349281c2Evan Cheng std::swap(V1, V2); 110550a5914e129c348e8878d4654b4306e0349281c2Evan Cheng std::swap(V1Size, V2Size); 110650a5914e129c348e8878d4654b4306e0349281c2Evan Cheng } 1107c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const PHINode *PN = dyn_cast<PHINode>(V1)) { 11086cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Result = aliasPHI(PN, V1Size, V1TBAAInfo, 11096cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 1110c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (Result != MayAlias) return Result; 1111c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 11122b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 11136665b0ea688941c1c044a5c034ee45d45862168fDan Gohman if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) { 11146665b0ea688941c1c044a5c034ee45d45862168fDan Gohman std::swap(V1, V2); 11156665b0ea688941c1c044a5c034ee45d45862168fDan Gohman std::swap(V1Size, V2Size); 11166665b0ea688941c1c044a5c034ee45d45862168fDan Gohman } 1117c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { 11186cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman AliasResult Result = aliasSelect(S1, V1Size, V1TBAAInfo, 11196cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman V2, V2Size, V2TBAAInfo); 1120c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman if (Result != MayAlias) return Result; 1121c1be92f3bb9158eade30d97db6997e2fe78150abDan Gohman } 11226665b0ea688941c1c044a5c034ee45d45862168fDan Gohman 11236cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman return AliasAnalysis::alias(Location(V1, V1Size, V1TBAAInfo), 11246cc7c9b8fc185473c80b38d9ea176fcc88314fb5Dan Gohman Location(V2, V2Size, V2TBAAInfo)); 1125d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 1126d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 11275d56b2d47d324ecf2d1cc1551a28cce49d16ab01Chris Lattner// Make sure that anything that uses AliasAnalysis pulls in this file. 11284f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(BasicAliasAnalysis) 1129