BasicAliasAnalysis.cpp revision 3a7a68c10880c2a28387617b42d14d774e218727
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" 178556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands#include "llvm/Analysis/CaptureTracking.h" 18534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen#include "llvm/Analysis/Passes.h" 196eb88d44c93f782a988039a047a9b80354a81887Chris Lattner#include "llvm/Constants.h" 20d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/DerivedTypes.h" 214244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Function.h" 224244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/GlobalVariable.h" 23eb62bc77b68e8d2350453d15aca300f481a612d5Alkis Evlogimenos#include "llvm/Instructions.h" 249b636cb3385376faa7f33a943cac7d40bff1531aOwen Anderson#include "llvm/IntrinsicInst.h" 25508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson#include "llvm/LLVMContext.h" 263a7a68c10880c2a28387617b42d14d774e218727Dan Gohman#include "llvm/Operator.h" 274244bb5bbd6fd815f86fc121ca507c6bd04459b3Chris Lattner#include "llvm/Pass.h" 28d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner#include "llvm/Target/TargetData.h" 29a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner#include "llvm/ADT/SmallVector.h" 30718cb665ca6ce2bc4d8e8479f46a45db91b49f86Owen Anderson#include "llvm/ADT/STLExtras.h" 31a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 32c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 3390aa839c88776e3dd0b3a798a98ea30d85b6b53cChris Lattner#include "llvm/Support/GetElementPtrTypeIterator.h" 3420aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 35ec4e8085e83fa1f14a82849548f7c1ad82009adeChris Lattnerusing namespace llvm; 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 37defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 38defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// Useful predicates 39defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 40defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 41defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic const User *isGEP(const Value *V) { 423a7a68c10880c2a28387617b42d14d774e218727Dan Gohman if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) 433a7a68c10880c2a28387617b42d14d774e218727Dan Gohman // For the purposes of BasicAliasAnalysis, if the GEP has overflow it 443a7a68c10880c2a28387617b42d14d774e218727Dan Gohman // could do crazy things. 453a7a68c10880c2a28387617b42d14d774e218727Dan Gohman if (GEP->hasNoPointerOverflow()) 463a7a68c10880c2a28387617b42d14d774e218727Dan Gohman return GEP; 47defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return 0; 48defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 49defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 50defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic const Value *GetGEPOperands(const Value *V, 51b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner SmallVector<Value*, 16> &GEPOps) { 52defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner assert(GEPOps.empty() && "Expect empty list to populate!"); 53defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner GEPOps.insert(GEPOps.end(), cast<User>(V)->op_begin()+1, 54defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner cast<User>(V)->op_end()); 55defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 56defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // Accumulate all of the chained indexes into the operand array 57defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner V = cast<User>(V)->getOperand(0); 58defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 59defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner while (const User *G = isGEP(V)) { 60defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) || 61defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner !cast<Constant>(GEPOps[0])->isNullValue()) 62defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner break; // Don't handle folding arbitrary pointer offsets yet... 63defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner GEPOps.erase(GEPOps.begin()); // Drop the zero index 64defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner GEPOps.insert(GEPOps.begin(), G->op_begin()+1, G->op_end()); 65defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner V = G->getOperand(0); 66defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner } 67defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return V; 68defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 69defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 70defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isKnownNonNull - Return true if we know that the specified value is never 71defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// null. 72defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic bool isKnownNonNull(const Value *V) { 73defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // Alloca never returns null, malloc might. 74defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (isa<AllocaInst>(V)) return true; 75defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 76defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // A byval argument is never null. 77defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (const Argument *A = dyn_cast<Argument>(V)) 78defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return A->hasByValAttr(); 79defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 80defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // Global values are not null unless extern weak. 81defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (const GlobalValue *GV = dyn_cast<GlobalValue>(V)) 82defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return !GV->hasExternalWeakLinkage(); 83defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 84defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 85defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 86defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isNonEscapingLocalObject - Return true if the pointer is to a function-local 87defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// object that never escapes from the function. 88defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic bool isNonEscapingLocalObject(const Value *V) { 89defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is a local allocation, check to see if it escapes. 9002ff308aa1c165d37fcf35f618243180ee68eeddNick Lewycky if (isa<AllocationInst>(V) || isNoAliasCall(V)) 918556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands return !PointerMayBeCaptured(V, false); 9291c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands 93defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner // If this is an argument that corresponds to a byval or noalias argument, 9491c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // then it has not escaped before entering the function. Check if it escapes 9591c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // inside the function. 96defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (const Argument *A = dyn_cast<Argument>(V)) 9791c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands if (A->hasByValAttr() || A->hasNoAliasAttr()) { 9891c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands // Don't bother analyzing arguments already known not to escape. 9991c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands if (A->hasNoCaptureAttr()) 10091c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands return true; 1018556d2a7f155c7edfaf454a3acda8ce28863c5e4Duncan Sands return !PointerMayBeCaptured(V, false); 10291c9c31033ff8166289bfee050b02bb6b586d510Duncan Sands } 103defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 104defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 105defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 106defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 107defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// isObjectSmallerThan - Return true if we can prove that the object specified 108defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner/// by V is smaller than Size. 109defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattnerstatic bool isObjectSmallerThan(const Value *V, unsigned Size, 110defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner const TargetData &TD) { 111295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner const Type *AccessTy; 112295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 113defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = GV->getType()->getElementType(); 114295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(V)) { 115defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (!AI->isArrayAllocation()) 116defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = AI->getType()->getElementType(); 117295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner else 118295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 119295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } else if (const Argument *A = dyn_cast<Argument>(V)) { 120defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner if (A->hasByValAttr()) 121defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner AccessTy = cast<PointerType>(A->getType())->getElementType(); 122295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner else 123295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 124295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } else { 125295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner return false; 126295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner } 127defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 128295d4e953a1214f60632220b9fcb31c1af8b0c27Chris Lattner if (AccessTy->isSized()) 129777d2306b36816a53bc1ae1244c0dc7d998ae691Duncan Sands return TD.getTypeAllocSize(AccessTy) < Size; 130defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner return false; 131defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner} 132defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 133defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 134defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// NoAA Pass 135defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 136defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 137d501c13b7d6ce418b0144886dde16525d13f835aChris Lattnernamespace { 138b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// NoAA - This class implements the -no-aa pass, which always returns "I 139b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// don't know" for alias queries. NoAA is unlike other alias analysis 140b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// implementations, in that it does not chain to a previous analysis. As 141b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// such it doesn't follow many of the rules that other alias analyses must. 142b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// 1439525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis { 1441997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 145ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman NoAA() : ImmutablePass(&ID) {} 146ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman explicit NoAA(void *PID) : ImmutablePass(PID) { } 147794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 148689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 149689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner AU.addRequired<TargetData>(); 150689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 1512b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 152689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner virtual void initializePass() { 153689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner TD = &getAnalysis<TargetData>(); 154689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner } 155689835a2d98ddd1e3766f5ce6816c8d908e8fff1Chris Lattner 156b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual AliasResult alias(const Value *V1, unsigned V1Size, 157b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner const Value *V2, unsigned V2Size) { 158b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return MayAlias; 159b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 160b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 1610af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner virtual void getArgumentAccesses(Function *F, CallSite CS, 1620af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner std::vector<PointerAccessInfo> &Info) { 163c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("This method may not be called on this function!"); 1640af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner } 1650af024c5d00c2a2d0e35ba33f4aaf4ed3fadfae2Chris Lattner 166b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { } 167b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool pointsToConstantMemory(const Value *P) { return false; } 168b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 169b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 170b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 171b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 172b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner return ModRef; 173b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner } 174b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual bool hasNoModRefInfoForCalls() const { return true; } 175b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 176b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void deleteValue(Value *V) {} 177b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner virtual void copyValue(Value *From, Value *To) {} 178b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner }; 179844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} // End of anonymous namespace 1802b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 181844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Register this pass... 182844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar NoAA::ID = 0; 183844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<NoAA> 184844731a7f1909f55935e3514c9e713a62d67662eDan GohmanU("no-aa", "No Alias Analysis (always returns 'may' alias)", true, true); 185b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 186844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Declare that we implement the AliasAnalysis interface 187844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterAnalysisGroup<AliasAnalysis> V(U); 188b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 189534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createNoAAPass() { return new NoAA(); } 190b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner 191defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 192defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner// BasicAA Pass 193defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner//===----------------------------------------------------------------------===// 194defa1c8034c5d69b1b91fc970f5faef255bdc660Chris Lattner 195b52f44086006434039b0c5df55aaac1079d26b96Chris Lattnernamespace { 196b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// BasicAliasAnalysis - This is the default alias analysis implementation. 197b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// Because it doesn't chain to a previous alias analysis (like -no-aa), it 198b52f44086006434039b0c5df55aaac1079d26b96Chris Lattner /// derives from the NoAA class. 1999525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA { 2001997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Class identification, replacement for typeinfo 201ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman BasicAliasAnalysis() : NoAA(&ID) {} 202d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner AliasResult alias(const Value *V1, unsigned V1Size, 203d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size); 204bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 20504b75935462642641469fb264aab9f1110ce2666Chris Lattner ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 20620d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner ModRefResult getModRefInfo(CallSite CS1, CallSite CS2); 207e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 208e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// hasNoModRefInfoForCalls - We can provide mod/ref information against 209e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner /// non-escaping allocations. 210e181b94309e34f9c16830a0a2a22e1c3c4b7f7acChris Lattner virtual bool hasNoModRefInfoForCalls() const { return false; } 21165585aa3fcb6c70ab36fb8965ac864378f5e3d44Chris Lattner 212bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// pointsToConstantMemory - Chase pointers until we find a (constant 213bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner /// global) or not. 214bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner bool pointsToConstantMemory(const Value *P); 215bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner 216d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner private: 217b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // CheckGEPInstructions - Check two GEP instructions with known 218b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // must-aliasing base pointers. This checks to see if the index expressions 219d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // preclude the pointers from aliasing... 220b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AliasResult 221fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner CheckGEPInstructions(const Type* BasePtr1Ty, 222fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size, 223fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type *BasePtr2Ty, 224fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2Size); 225d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner }; 226844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} // End of anonymous namespace 2272b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 228844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Register this pass... 229844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar BasicAliasAnalysis::ID = 0; 230844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<BasicAliasAnalysis> 231844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("basicaa", "Basic Alias Analysis (default AA impl)", false, true); 232d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 233844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Declare that we implement the AliasAnalysis interface 234844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterAnalysisGroup<AliasAnalysis, true> Y(X); 235d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 236534927d82de6d1be0f6e939263eeb309ad135661Jeff CohenImmutablePass *llvm::createBasicAliasAnalysisPass() { 237534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen return new BasicAliasAnalysis(); 238534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen} 239534927d82de6d1be0f6e939263eeb309ad135661Jeff Cohen 2404a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 241bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// pointsToConstantMemory - Chase pointers until we find a (constant 242bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner/// global) or not. 243bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattnerbool BasicAliasAnalysis::pointsToConstantMemory(const Value *P) { 244a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (const GlobalVariable *GV = 2455d0392c6b370758750b397e254a6c6f028479969Duncan Sands dyn_cast<GlobalVariable>(P->getUnderlyingObject())) 246a413960a4847b996e48ebad5c41f094df441641dChris Lattner return GV->isConstant(); 247bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner return false; 248bc1daaa8bb13f2cce6801f49928697fcde095a2eChris Lattner} 2494a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 250e79422096ea5319a365d160693d0957a2a4df75eOwen Anderson 25104b75935462642641469fb264aab9f1110ce2666Chris Lattner// getModRefInfo - Check to see if the specified callsite can clobber the 25204b75935462642641469fb264aab9f1110ce2666Chris Lattner// specified memory object. Since we only look at local properties of this 25304b75935462642641469fb264aab9f1110ce2666Chris Lattner// function, we really can't say much about this query. We do, however, use 25404b75935462642641469fb264aab9f1110ce2666Chris Lattner// simple "address taken" analysis on local objects. 25504b75935462642641469fb264aab9f1110ce2666Chris Lattner// 25604b75935462642641469fb264aab9f1110ce2666Chris LattnerAliasAnalysis::ModRefResult 25704b75935462642641469fb264aab9f1110ce2666Chris LattnerBasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 258fd687500384803311556571989dc14cd84786904Chris Lattner if (!isa<Constant>(P)) { 2595d0392c6b370758750b397e254a6c6f028479969Duncan Sands const Value *Object = P->getUnderlyingObject(); 260a413960a4847b996e48ebad5c41f094df441641dChris Lattner 261a413960a4847b996e48ebad5c41f094df441641dChris Lattner // If this is a tail call and P points to a stack location, we know that 262a413960a4847b996e48ebad5c41f094df441641dChris Lattner // the tail call cannot access or modify the local stack. 263a413960a4847b996e48ebad5c41f094df441641dChris Lattner // We cannot exclude byval arguments here; these belong to the caller of 264a413960a4847b996e48ebad5c41f094df441641dChris Lattner // the current function not to the current function, and a tail callee 265a413960a4847b996e48ebad5c41f094df441641dChris Lattner // may reference them. 266a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (isa<AllocaInst>(Object)) 267a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) 268a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (CI->isTailCall()) 269a413960a4847b996e48ebad5c41f094df441641dChris Lattner return NoModRef; 270a413960a4847b996e48ebad5c41f094df441641dChris Lattner 27125df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner // If the pointer is to a locally allocated object that does not escape, 27225df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner // then the call can not mod/ref the pointer unless the call takes the 27325df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner // argument without capturing it. 274826f7cebfd347bf2218ba35486bc13623523ed7fNick Lewycky if (isNonEscapingLocalObject(Object) && CS.getInstruction() != Object) { 27525df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner bool passedAsArg = false; 27625df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner // TODO: Eventually only check 'nocapture' arguments. 27725df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 27825df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner CI != CE; ++CI) 27925df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner if (isa<PointerType>((*CI)->getType()) && 28025df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner alias(cast<Value>(CI), ~0U, P, ~0U) != NoAlias) 28125df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner passedAsArg = true; 28225df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner 28325df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner if (!passedAsArg) 28425df20f169eb90d2e5f9cff3018a4d935ee5d796Chris Lattner return NoModRef; 28504b75935462642641469fb264aab9f1110ce2666Chris Lattner } 286fd687500384803311556571989dc14cd84786904Chris Lattner } 28704b75935462642641469fb264aab9f1110ce2666Chris Lattner 288bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner // The AliasAnalysis base class has some smarts, lets use them. 289bbcc147220d885b129743c009c3e46a7a3d8ab2eChris Lattner return AliasAnalysis::getModRefInfo(CS, P, Size); 29004b75935462642641469fb264aab9f1110ce2666Chris Lattner} 29104b75935462642641469fb264aab9f1110ce2666Chris Lattner 292a413960a4847b996e48ebad5c41f094df441641dChris Lattner 29320d6f0982ad33818cfa141f80157ac13e36d5550Chris LattnerAliasAnalysis::ModRefResult 29420d6f0982ad33818cfa141f80157ac13e36d5550Chris LattnerBasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 29520d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner // If CS1 or CS2 are readnone, they don't interact. 29620d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner ModRefBehavior CS1B = AliasAnalysis::getModRefBehavior(CS1); 29720d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner if (CS1B == DoesNotAccessMemory) return NoModRef; 29820d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner 29920d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner ModRefBehavior CS2B = AliasAnalysis::getModRefBehavior(CS2); 30020d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner if (CS2B == DoesNotAccessMemory) return NoModRef; 30120d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner 30220d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner // If they both only read from memory, just return ref. 30320d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner if (CS1B == OnlyReadsMemory && CS2B == OnlyReadsMemory) 30420d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner return Ref; 30520d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner 30620d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner // Otherwise, fall back to NoAA (mod+ref). 30720d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner return NoAA::getModRefInfo(CS1, CS2); 30820d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner} 30920d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner 31020d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner 311d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such 312b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner// as array references. 313d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner// 314d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerAliasAnalysis::AliasResult 315d501c13b7d6ce418b0144886dde16525d13f835aChris LattnerBasicAliasAnalysis::alias(const Value *V1, unsigned V1Size, 316d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner const Value *V2, unsigned V2Size) { 317001dbfebcbbded8c8e74b19e838b50da2b6c6fb5Owen Anderson Context = &V1->getType()->getContext(); 318001dbfebcbbded8c8e74b19e838b50da2b6c6fb5Owen Anderson 319b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Strip off any constant expression casts if they exist 320b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V1)) 3213da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 322b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V1 = CE->getOperand(0); 323b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V2)) 3243da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->isCast() && isa<PointerType>(CE->getOperand(0)->getType())) 325b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner V2 = CE->getOperand(0); 326b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 327d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Are we checking for alias of the same value? 328d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner if (V1 == V2) return MustAlias; 329d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 33002ff308aa1c165d37fcf35f618243180ee68eeddNick Lewycky if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) 331d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; // Scalars cannot alias each other 332d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 333b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // Strip off cast instructions. Since V1 and V2 are pointers, they must be 334b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // pointer<->pointer bitcasts. 3353da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (const BitCastInst *I = dyn_cast<BitCastInst>(V1)) 336241607d01648e85754f72de945684c7a8641a292Chris Lattner return alias(I->getOperand(0), V1Size, V2, V2Size); 3373da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (const BitCastInst *I = dyn_cast<BitCastInst>(V2)) 338241607d01648e85754f72de945684c7a8641a292Chris Lattner return alias(V1, V1Size, I->getOperand(0), V2Size); 339d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 340b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // Figure out what objects these things are pointing to if we can. 3415d0392c6b370758750b397e254a6c6f028479969Duncan Sands const Value *O1 = V1->getUnderlyingObject(); 3425d0392c6b370758750b397e254a6c6f028479969Duncan Sands const Value *O2 = V2->getUnderlyingObject(); 343d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 344a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (O1 != O2) { 345a413960a4847b996e48ebad5c41f094df441641dChris Lattner // If V1/V2 point to two different objects we know that we have no alias. 346a413960a4847b996e48ebad5c41f094df441641dChris Lattner if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) 347a413960a4847b996e48ebad5c41f094df441641dChris Lattner return NoAlias; 348a413960a4847b996e48ebad5c41f094df441641dChris Lattner 349b2b32fd3fe22ca6b165d9c21d7ec0bcd2af105f5Nick Lewycky // Arguments can't alias with local allocations or noalias calls. 350b2b32fd3fe22ca6b165d9c21d7ec0bcd2af105f5Nick Lewycky if ((isa<Argument>(O1) && (isa<AllocationInst>(O2) || isNoAliasCall(O2))) || 351b2b32fd3fe22ca6b165d9c21d7ec0bcd2af105f5Nick Lewycky (isa<Argument>(O2) && (isa<AllocationInst>(O1) || isNoAliasCall(O1)))) 352a413960a4847b996e48ebad5c41f094df441641dChris Lattner return NoAlias; 35302ff308aa1c165d37fcf35f618243180ee68eeddNick Lewycky 354a413960a4847b996e48ebad5c41f094df441641dChris Lattner // Most objects can't alias null. 355a413960a4847b996e48ebad5c41f094df441641dChris Lattner if ((isa<ConstantPointerNull>(V2) && isKnownNonNull(O1)) || 356a413960a4847b996e48ebad5c41f094df441641dChris Lattner (isa<ConstantPointerNull>(V1) && isKnownNonNull(O2))) 357a413960a4847b996e48ebad5c41f094df441641dChris Lattner return NoAlias; 3580a1ac907c30cd3a5d0d8f96c1015bdb1c7461290Chris Lattner } 359a413960a4847b996e48ebad5c41f094df441641dChris Lattner 360a413960a4847b996e48ebad5c41f094df441641dChris Lattner // If the size of one access is larger than the entire object on the other 361a413960a4847b996e48ebad5c41f094df441641dChris Lattner // side, then we know such behavior is undefined and can assume no alias. 362a413960a4847b996e48ebad5c41f094df441641dChris Lattner const TargetData &TD = getTargetData(); 363a413960a4847b996e48ebad5c41f094df441641dChris Lattner if ((V1Size != ~0U && isObjectSmallerThan(O2, V1Size, TD)) || 364a413960a4847b996e48ebad5c41f094df441641dChris Lattner (V2Size != ~0U && isObjectSmallerThan(O1, V2Size, TD))) 365a413960a4847b996e48ebad5c41f094df441641dChris Lattner return NoAlias; 366a413960a4847b996e48ebad5c41f094df441641dChris Lattner 367845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner // If one pointer is the result of a call/invoke and the other is a 368845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner // non-escaping local object, then we know the object couldn't escape to a 369845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner // point where the call could return it. 370845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner if ((isa<CallInst>(O1) || isa<InvokeInst>(O1)) && 371826f7cebfd347bf2218ba35486bc13623523ed7fNick Lewycky isNonEscapingLocalObject(O2) && O1 != O2) 372845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner return NoAlias; 373845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner if ((isa<CallInst>(O2) || isa<InvokeInst>(O2)) && 374826f7cebfd347bf2218ba35486bc13623523ed7fNick Lewycky isNonEscapingLocalObject(O1) && O1 != O2) 375845f0d2f0fd4a268ca1b3df9afb3de523f6dfa9dChris Lattner return NoAlias; 376a413960a4847b996e48ebad5c41f094df441641dChris Lattner 377b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have two gep instructions with must-alias'ing base pointers, figure 378b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // out if the indexes to the GEP tell us anything about the derived pointer. 379b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Note that we also handle chains of getelementptr instructions as well as 380b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant expression getelementptrs here. 381d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 382b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (isGEP(V1) && isGEP(V2)) { 383b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner const User *GEP1 = cast<User>(V1); 384b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner const User *GEP2 = cast<User>(V2); 385b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner 386b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // If V1 and V2 are identical GEPs, just recurse down on both of them. 387b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // This allows us to analyze things like: 388b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // P = gep A, 0, i, 1 389b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // Q = gep B, 0, i, 1 390b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // by just analyzing A and B. This is even safe for variable indices. 391b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner if (GEP1->getType() == GEP2->getType() && 392b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP1->getNumOperands() == GEP2->getNumOperands() && 393b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType() && 394b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner // All operands are the same, ignoring the base. 395b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner std::equal(GEP1->op_begin()+1, GEP1->op_end(), GEP2->op_begin()+1)) 396b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner return alias(GEP1->getOperand(0), V1Size, GEP2->getOperand(0), V2Size); 397b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner 398b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner 399b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Drill down into the first non-gep value, to test for must-aliasing of 400b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // the base pointers. 401b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner while (isGEP(GEP1->getOperand(0)) && 402b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP1->getOperand(1) == 403508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context->getNullValue(GEP1->getOperand(1)->getType())) 404b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP1 = cast<User>(GEP1->getOperand(0)); 405b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner const Value *BasePtr1 = GEP1->getOperand(0); 406b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner 407b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner while (isGEP(GEP2->getOperand(0)) && 408b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP2->getOperand(1) == 409508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context->getNullValue(GEP2->getOperand(1)->getType())) 410b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner GEP2 = cast<User>(GEP2->getOperand(0)); 411b957bda0bcb81c88ed4464d07100c349af76890fChris Lattner const Value *BasePtr2 = GEP2->getOperand(0); 412b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 413b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Do the base pointers alias? 414241607d01648e85754f72de945684c7a8641a292Chris Lattner AliasResult BaseAlias = alias(BasePtr1, ~0U, BasePtr2, ~0U); 415b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == NoAlias) return NoAlias; 416b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BaseAlias == MustAlias) { 417b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the base pointers alias each other exactly, check to see if we can 418b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // figure out anything about the resultant pointers, to try to prove 419b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // non-aliasing. 420b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 421b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Collect all of the chained GEP operands together into one simple place 422a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner SmallVector<Value*, 16> GEP1Ops, GEP2Ops; 4234a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr1 = GetGEPOperands(V1, GEP1Ops); 4244a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner BasePtr2 = GetGEPOperands(V2, GEP2Ops); 4254a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 426730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner // If GetGEPOperands were able to fold to the same must-aliased pointer, 427730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner // do the comparison. 428730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner if (BasePtr1 == BasePtr2) { 429730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner AliasResult GAlias = 430fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner CheckGEPInstructions(BasePtr1->getType(), 431fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner &GEP1Ops[0], GEP1Ops.size(), V1Size, 432fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner BasePtr2->getType(), 433fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner &GEP2Ops[0], GEP2Ops.size(), V2Size); 434730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner if (GAlias != MayAlias) 435730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner return GAlias; 436730b1ad2c4e33dd8b0f22744ece4f884f44c816aChris Lattner } 437b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 438b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 439d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 440d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Check to see if these two pointers are related by a getelementptr 441d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // instruction. If one pointer is a GEP with a non-zero index of the other 442d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // pointer, we know they cannot alias. 443d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 4444a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (isGEP(V2)) { 445d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1, V2); 446d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner std::swap(V1Size, V2Size); 447d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 448d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 449c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V1Size != ~0U && V2Size != ~0U) 4503ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer if (isGEP(V1)) { 451a77600e8612c51e75f55710ce9af7eb8aba8b083Chris Lattner SmallVector<Value*, 16> GEPOperands; 4524a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner const Value *BasePtr = GetGEPOperands(V1, GEPOperands); 4534a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner 4544a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner AliasResult R = alias(BasePtr, V1Size, V2, V2Size); 455c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (R == MustAlias) { 456c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // If there is at least one non-zero constant index, we know they cannot 457c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // alias. 458c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner bool ConstantFound = false; 45988d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner bool AllZerosFound = true; 4604a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner for (unsigned i = 0, e = GEPOperands.size(); i != e; ++i) 4614a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (const Constant *C = dyn_cast<Constant>(GEPOperands[i])) { 462c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (!C->isNullValue()) { 463c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner ConstantFound = true; 464c54735e7cbd639a612837d93bf75d73507dd7d47Chris Lattner AllZerosFound = false; 465c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner break; 46688d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } 46788d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner } else { 46888d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner AllZerosFound = false; 469c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 47088d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 47188d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // If we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 must aliases 47288d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner // the ptr, the end result is a must alias also. 47388d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner if (AllZerosFound) 47488d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner return MustAlias; 47588d3e03429bf3b0e78b1cccbad8a9246a7fdb23eChris Lattner 476c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (ConstantFound) { 477c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner if (V2Size <= 1 && V1Size <= 1) // Just pointer check? 478d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return NoAlias; 4792b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 480c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // Otherwise we have to check to see that the distance is more than 481c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the size of the argument... build an index vector that is equal to 482c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // the arguments provided, except substitute 0's for any variable 483c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner // indexes we find... 484a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos if (cast<PointerType>( 485a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos BasePtr->getType())->getElementType()->isSized()) { 486a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos for (unsigned i = 0; i != GEPOperands.size(); ++i) 4870bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(GEPOperands[i])) 488a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos GEPOperands[i] = 489508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context->getNullValue(GEPOperands[i]->getType()); 490a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos int64_t Offset = 491829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner getTargetData().getIndexedOffset(BasePtr->getType(), 492829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner &GEPOperands[0], 493829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner GEPOperands.size()); 494a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos 495a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos if (Offset >= (int64_t)V2Size || Offset <= -(int64_t)V1Size) 496a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos return NoAlias; 497a95cf3024b9a3c3ed6bf3e862d956ce46a8cbebeAlkis Evlogimenos } 498c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 499c330ee6f0245569ade06f72af30bd85ae3cb3341Chris Lattner } 500d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 5012b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 502d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 503d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 504d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 5051832705b06e0378040c5fc94042fd0b0a9ee5b61Duncan Sands// This function is used to determine if the indices of two GEP instructions are 5063da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer// equal. V1 and V2 are the indices. 50707cf79ef537caff6d39145f190a28a336e629b6fOwen Andersonstatic bool IndexOperandsEqual(Value *V1, Value *V2, LLVMContext *Context) { 50828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (V1->getType() == V2->getType()) 50928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return V1 == V2; 51028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C1 = dyn_cast<Constant>(V1)) 51128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (Constant *C2 = dyn_cast<Constant>(V2)) { 5123da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // Sign extend the constants to long types, if necessary 513c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (C1->getType() != Type::Int64Ty) 514508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson C1 = Context->getConstantExprSExt(C1, Type::Int64Ty); 515c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (C2->getType() != Type::Int64Ty) 516508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson C2 = Context->getConstantExprSExt(C2, Type::Int64Ty); 51728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return C1 == C2; 51828977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 51928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner return false; 52028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner} 52128977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner 522b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// CheckGEPInstructions - Check two GEP instructions with known must-aliasing 523b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// base pointers. This checks to see if the index expressions preclude the 524b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner/// pointers from aliasing... 525b83eb6447ba155342598f0fabe1f08f5baa9164aReid SpencerAliasAnalysis::AliasResult 526b83eb6447ba155342598f0fabe1f08f5baa9164aReid SpencerBasicAliasAnalysis::CheckGEPInstructions( 527fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type* BasePtr1Ty, Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1S, 528fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Type *BasePtr2Ty, Value **GEP2Ops, unsigned NumGEP2Ops, unsigned G2S) { 529b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We currently can't handle the case when the base pointers have different 530b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // primitive types. Since this is uncommon anyway, we are happy being 531b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // extremely conservative. 532b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty != BasePtr2Ty) 533b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 534b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 535c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos const PointerType *GEPPointerTy = cast<PointerType>(BasePtr1Ty); 536b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 537001dbfebcbbded8c8e74b19e838b50da2b6c6fb5Owen Anderson Context = &GEPPointerTy->getContext(); 538001dbfebcbbded8c8e74b19e838b50da2b6c6fb5Owen Anderson 539b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Find the (possibly empty) initial sequence of equal values... which are not 540b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // necessarily constants. 541fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner unsigned NumGEP1Operands = NumGEP1Ops, NumGEP2Operands = NumGEP2Ops; 542b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MinOperands = std::min(NumGEP1Operands, NumGEP2Operands); 543b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned MaxOperands = std::max(NumGEP1Operands, NumGEP2Operands); 544b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner unsigned UnequalOper = 0; 545b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner while (UnequalOper != MinOperands && 546508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson IndexOperandsEqual(GEP1Ops[UnequalOper], GEP2Ops[UnequalOper], 547508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context)) { 548b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance through the type as we go... 549b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner ++UnequalOper; 550b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 551b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[UnequalOper-1]); 552b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else { 553b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If all operands equal each other, then the derived pointers must 554b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // alias each other... 555b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 556b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner assert(UnequalOper == NumGEP1Operands && UnequalOper == NumGEP2Operands && 557b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner "Ran out of type nesting, but not out of operands?"); 558b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MustAlias; 559920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 560920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 561920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 562b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If we have seen all constant operands, and run out of indexes on one of the 563b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // getelementptrs, check to see if the tail of the leftover one is all zeros. 564b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If so, return mustalias. 5654a83088b307968c25d11ea3e7de254cfb1771aebChris Lattner if (UnequalOper == MinOperands) { 566fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops < NumGEP2Ops) { 567fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(GEP1Ops, GEP2Ops); 568fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 569fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 5702b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 571b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner bool AllAreZeros = true; 572b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = UnequalOper; i != MaxOperands; ++i) 573a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (!isa<Constant>(GEP1Ops[i]) || 574b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner !cast<Constant>(GEP1Ops[i])->isNullValue()) { 575b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner AllAreZeros = false; 576b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner break; 577b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 578b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (AllAreZeros) return MustAlias; 579b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 580b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 5812b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 582d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // So now we know that the indexes derived from the base pointers, 583d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // which are known to alias, are different. We can still determine a 584d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // no-alias result if there are differing constant pairs in the index 585d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // chain. For example: 586d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S)) 587d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // 5885a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // We have to be careful here about array accesses. In particular, consider: 5895a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // A[1][0] vs A[0][i] 5905a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // In this case, we don't *know* that the array will be accessed in bounds: 5915a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // the index could even be negative. Because of this, we have to 5925a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // conservatively *give up* and return may alias. We disregard differing 5935a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // array subscripts that are followed by a variable index without going 5945a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // through a struct. 5955a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // 596d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned SizeMax = std::max(G1S, G2S); 597eaf8f9c667b15cf09b4608558cc24675e92ad2cdChris Lattner if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work. 598920bd79f344acfabe23c8fb00363c58532426753Chris Lattner 599d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Scan for the first operand that is constant and unequal in the 60028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // two getelementptrs... 601d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner unsigned FirstConstantOper = UnequalOper; 602b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (; FirstConstantOper != MinOperands; ++FirstConstantOper) { 603b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G1Oper = GEP1Ops[FirstConstantOper]; 604b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const Value *G2Oper = GEP2Ops[FirstConstantOper]; 6052b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 6066eb88d44c93f782a988039a047a9b80354a81887Chris Lattner if (G1Oper != G2Oper) // Found non-equal constant indexes... 607a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (Constant *G1OC = dyn_cast<ConstantInt>(const_cast<Value*>(G1Oper))) 608a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner if (Constant *G2OC = dyn_cast<ConstantInt>(const_cast<Value*>(G2Oper))){ 60928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC->getType() != G2OC->getType()) { 61028977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // Sign extend both operands to long. 611c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (G1OC->getType() != Type::Int64Ty) 612508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson G1OC = Context->getConstantExprSExt(G1OC, Type::Int64Ty); 613c5b206b6be61d0d933b98b6af5e22f42edd48ad1Reid Spencer if (G2OC->getType() != Type::Int64Ty) 614508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson G2OC = Context->getConstantExprSExt(G2OC, Type::Int64Ty); 61528977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP1Ops[FirstConstantOper] = G1OC; 61628977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner GEP2Ops[FirstConstantOper] = G2OC; 61728977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 6185a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 61928977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner if (G1OC != G2OC) { 62007a96765daedf180a7102d39fe56c499878312b7Dan Gohman // Handle the "be careful" case above: if this is an array/vector 6215a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner // subscript, scan for a subsequent variable array index. 62272776d219014f6b07485e7dcc5a818849904e720Dan Gohman if (const SequentialType *STy = 62372776d219014f6b07485e7dcc5a818849904e720Dan Gohman dyn_cast<SequentialType>(BasePtr1Ty)) { 62472776d219014f6b07485e7dcc5a818849904e720Dan Gohman const Type *NextTy = STy; 6255a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner bool isBadCase = false; 6265a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 62772776d219014f6b07485e7dcc5a818849904e720Dan Gohman for (unsigned Idx = FirstConstantOper; 6287765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner Idx != MinOperands && isa<SequentialType>(NextTy); ++Idx) { 6295a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner const Value *V1 = GEP1Ops[Idx], *V2 = GEP2Ops[Idx]; 6305a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (!isa<Constant>(V1) || !isa<Constant>(V2)) { 6315a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner isBadCase = true; 6325a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner break; 6335a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 63472776d219014f6b07485e7dcc5a818849904e720Dan Gohman // If the array is indexed beyond the bounds of the static type 63572776d219014f6b07485e7dcc5a818849904e720Dan Gohman // at this level, it will also fall into the "be careful" case. 63672776d219014f6b07485e7dcc5a818849904e720Dan Gohman // It would theoretically be possible to analyze these cases, 63772776d219014f6b07485e7dcc5a818849904e720Dan Gohman // but for now just be conservatively correct. 63872776d219014f6b07485e7dcc5a818849904e720Dan Gohman if (const ArrayType *ATy = dyn_cast<ArrayType>(STy)) 63972776d219014f6b07485e7dcc5a818849904e720Dan Gohman if (cast<ConstantInt>(G1OC)->getZExtValue() >= 64072776d219014f6b07485e7dcc5a818849904e720Dan Gohman ATy->getNumElements() || 64172776d219014f6b07485e7dcc5a818849904e720Dan Gohman cast<ConstantInt>(G2OC)->getZExtValue() >= 64272776d219014f6b07485e7dcc5a818849904e720Dan Gohman ATy->getNumElements()) { 64372776d219014f6b07485e7dcc5a818849904e720Dan Gohman isBadCase = true; 64472776d219014f6b07485e7dcc5a818849904e720Dan Gohman break; 64572776d219014f6b07485e7dcc5a818849904e720Dan Gohman } 64672776d219014f6b07485e7dcc5a818849904e720Dan Gohman if (const VectorType *VTy = dyn_cast<VectorType>(STy)) 64772776d219014f6b07485e7dcc5a818849904e720Dan Gohman if (cast<ConstantInt>(G1OC)->getZExtValue() >= 64872776d219014f6b07485e7dcc5a818849904e720Dan Gohman VTy->getNumElements() || 64972776d219014f6b07485e7dcc5a818849904e720Dan Gohman cast<ConstantInt>(G2OC)->getZExtValue() >= 65072776d219014f6b07485e7dcc5a818849904e720Dan Gohman VTy->getNumElements()) { 65172776d219014f6b07485e7dcc5a818849904e720Dan Gohman isBadCase = true; 65272776d219014f6b07485e7dcc5a818849904e720Dan Gohman break; 65372776d219014f6b07485e7dcc5a818849904e720Dan Gohman } 65472776d219014f6b07485e7dcc5a818849904e720Dan Gohman STy = cast<SequentialType>(NextTy); 6557765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner NextTy = cast<SequentialType>(NextTy)->getElementType(); 6565a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 6575a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 6585a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (isBadCase) G1OC = 0; 6595a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 6605a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner 661a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner // Make sure they are comparable (ie, not constant expressions), and 662a35339dfb67cec3d7e9783c9c6d3de110ea6bafeChris Lattner // make sure the GEP with the smaller leading constant is GEP1. 6635a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner if (G1OC) { 664e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Constant *Compare = ConstantExpr::getICmp(ICmpInst::ICMP_SGT, 665e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer G1OC, G2OC); 6666b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CV = dyn_cast<ConstantInt>(Compare)) { 667fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (CV->getZExtValue()) { // If they are comparable and G2 > G1 6685a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner std::swap(GEP1Ops, GEP2Ops); // Make GEP1 < GEP2 669fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 670fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 6715a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner break; 6725a3cf8de5db8d2ca91e77132a40b590c27f497ecChris Lattner } 67328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner } 6746eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 6756eb88d44c93f782a988039a047a9b80354a81887Chris Lattner } 676b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)->getTypeAtIndex(G1Oper); 677d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 6782b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 679b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // No shared constant operands, and we ran out of common operands. At this 680b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // point, the GEP instructions have run through all of their operands, and we 681b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // haven't found evidence that there are any deltas between the GEP's. 682b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // However, one GEP may have more operands than the other. If this is the 68328977af72a11fcad5d1b54d7a96b3df02828f6fcChris Lattner // case, there may still be hope. Check this now. 684b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (FirstConstantOper == MinOperands) { 685b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Make GEP1Ops be the longer one if there is a longer one. 686fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops < NumGEP2Ops) { 687b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner std::swap(GEP1Ops, GEP2Ops); 688fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner std::swap(NumGEP1Ops, NumGEP2Ops); 689fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner } 690b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 691b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Is there anything to check? 692fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner if (NumGEP1Ops > MinOperands) { 693b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper; i != MaxOperands; ++i) 6946b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (isa<ConstantInt>(GEP1Ops[i]) && 695843f0767acd05baed952d39e77ea89b438430a4fZhou Sheng !cast<ConstantInt>(GEP1Ops[i])->isZero()) { 696b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Yup, there's a constant in the tail. Set all variables to 69798e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz // constants in the GEP instruction to make it suitable for 698b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // TargetData::getIndexedOffset. 699b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (i = 0; i != MaxOperands; ++i) 7000bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(GEP1Ops[i])) 701508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP1Ops[i] = Context->getNullValue(GEP1Ops[i]->getType()); 702b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Okay, now get the offset. This is the relative offset for the full 703b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // instruction. 704b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner const TargetData &TD = getTargetData(); 705fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner int64_t Offset1 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 706fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner NumGEP1Ops); 707b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 708fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner // Now check without any constants at the end. 709fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner int64_t Offset2 = TD.getIndexedOffset(GEPPointerTy, GEP1Ops, 710fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner MinOperands); 7112b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 71298e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz // Make sure we compare the absolute difference. 71398e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz if (Offset1 > Offset2) 71498e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz std::swap(Offset1, Offset2); 71598e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz 716b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If the tail provided a bit enough offset, return noalias! 717b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if ((uint64_t)(Offset2-Offset1) >= SizeMax) 718b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return NoAlias; 71998e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz // Otherwise break - we don't look for another constant in the tail. 72098e3a6829aaf070a8893a164d6dc8c75f9f9feaaWojciech Matyjewicz break; 721b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 722b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 7232b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 724b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Couldn't find anything useful. 725b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; 726b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 727d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 728d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // If there are non-equal constants arguments, then we can figure 729d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // out a minimum known delta between the two index expressions... at 730d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // this point we know that the first constant index of GEP1 is less 731d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // than the first constant index of GEP2. 732b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 733b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Advance BasePtr[12]Ty over this first differing constant operand. 7342cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner BasePtr2Ty = cast<CompositeType>(BasePtr1Ty)-> 7352cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner getTypeAtIndex(GEP2Ops[FirstConstantOper]); 7362cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner BasePtr1Ty = cast<CompositeType>(BasePtr1Ty)-> 7372cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner getTypeAtIndex(GEP1Ops[FirstConstantOper]); 7382b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 739b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We are going to be using TargetData::getIndexedOffset to determine the 740b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // offset that each of the GEP's is reaching. To do this, we have to convert 741b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // all variable references to constant references. To do this, we convert the 7422cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner // initial sequence of array subscripts into constant zeros to start with. 7432cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner const Type *ZeroIdxTy = GEPPointerTy; 7442cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner for (unsigned i = 0; i != FirstConstantOper; ++i) { 7452cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner if (!isa<StructType>(ZeroIdxTy)) 746508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP1Ops[i] = GEP2Ops[i] = Context->getNullValue(Type::Int32Ty); 747b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 7482cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(ZeroIdxTy)) 7492cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner ZeroIdxTy = CT->getTypeAtIndex(GEP1Ops[i]); 7502cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner } 7512cfdd2854c7bcc050758749a2e28e5f7b3c1b35fChris Lattner 752b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // We know that GEP1Ops[FirstConstantOper] & GEP2Ops[FirstConstantOper] are ok 7532b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 754d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner // Loop over the rest of the operands... 755b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner for (unsigned i = FirstConstantOper+1; i != MaxOperands; ++i) { 756fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Value *Op1 = i < NumGEP1Ops ? GEP1Ops[i] : 0; 757fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner const Value *Op2 = i < NumGEP2Ops ? GEP2Ops[i] : 0; 758b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If they are equal, use a zero index... 759b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1 == Op2 && BasePtr1Ty == BasePtr2Ty) { 7600bb38313ae78a621a0596dc1089522ad5255e399Chris Lattner if (!isa<ConstantInt>(Op1)) 761508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP1Ops[i] = GEP2Ops[i] = Context->getNullValue(Op1->getType()); 762b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // Otherwise, just keep the constants we have. 763d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } else { 764b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op1) { 765b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) { 766b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 7677765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) { 768b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer if (Op1C->getZExtValue() >= AT->getNumElements()) 769b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 770f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) { 771f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner if (Op1C->getZExtValue() >= VT->getNumElements()) 7727765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner return MayAlias; // Be conservative with out-of-range accesses 7737765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner } 7747765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner 775b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { 776b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // GEP1 is known to produce a value less than GEP2. To be 777b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // conservatively correct, we must assume the largest possible 778b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // constant is used in this position. This cannot be the initial 779b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // index to the GEP instructions (because we know we have at least one 780b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // element before this one with the different constant arguments), so 781b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // we know that the current index must be into either a struct or 782b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // array. Because we know it's not constant, this cannot be a 783b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // structure index. Because of this, we can calculate the maximum 784b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // value possible. 785b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // 786b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr1Ty)) 787508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP1Ops[i] = 788508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context->getConstantInt(Type::Int64Ty,AT->getNumElements()-1); 7899907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr1Ty)) 790508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP1Ops[i] = 791508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson Context->getConstantInt(Type::Int64Ty,VT->getNumElements()-1); 792b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 793d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 7942b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 795b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (Op2) { 796b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const ConstantInt *Op2C = dyn_cast<ConstantInt>(Op2)) { 797b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner // If this is an array index, make sure the array element is in range. 798f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner if (const ArrayType *AT = dyn_cast<ArrayType>(BasePtr2Ty)) { 799b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer if (Op2C->getZExtValue() >= AT->getNumElements()) 800b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner return MayAlias; // Be conservative with out-of-range accesses 801f88380ba2cf472db6576a8534315449931e8cf50Chris Lattner } else if (const VectorType *VT = dyn_cast<VectorType>(BasePtr2Ty)) { 8029907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner if (Op2C->getZExtValue() >= VT->getNumElements()) 8037765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner return MayAlias; // Be conservative with out-of-range accesses 8047765d71304f0f26ab348deb41af9b6ae033aae4dChris Lattner } 805b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } else { // Conservatively assume the minimum value for this index 806508955156a25a9abc470a29e1760aa176d341cf9Owen Anderson GEP2Ops[i] = Context->getNullValue(Op2->getType()); 807b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 808920bd79f344acfabe23c8fb00363c58532426753Chris Lattner } 809b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 810b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 811b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr1Ty && Op1) { 812b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr1Ty)) 813b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = CT->getTypeAtIndex(GEP1Ops[i]); 814b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 815b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr1Ty = 0; 816b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner } 817b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner 818b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (BasePtr2Ty && Op2) { 819b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner if (const CompositeType *CT = dyn_cast<CompositeType>(BasePtr2Ty)) 820b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = CT->getTypeAtIndex(GEP2Ops[i]); 821b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner else 822b307c88fe799eb69c37bee2840d9fde93d407e3aChris Lattner BasePtr2Ty = 0; 823d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 824d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 8252b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 826c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos if (GEPPointerTy->getElementType()->isSized()) { 827829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner int64_t Offset1 = 828fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner getTargetData().getIndexedOffset(GEPPointerTy, GEP1Ops, NumGEP1Ops); 829829621c59e9e4e2f4e15cd562688fae9f82ea549Chris Lattner int64_t Offset2 = 830fd1ad3b730a087555655b55d6345f6c0677cd7bdChris Lattner getTargetData().getIndexedOffset(GEPPointerTy, GEP2Ops, NumGEP2Ops); 8319907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner assert(Offset1 != Offset2 && 8329907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner "There is at least one different constant here!"); 8339907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner 8349907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner // Make sure we compare the absolute difference. 8359907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner if (Offset1 > Offset2) 8369907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner std::swap(Offset1, Offset2); 8379907cb12ae431ed6168bbb93088195b530b62ce8Chris Lattner 838c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos if ((uint64_t)(Offset2-Offset1) >= SizeMax) { 839e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Determined that these two GEP's don't alias [" 840e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2; 841c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos return NoAlias; 842c49741d047f7cf1143aa34a3a97379a8d1b5f0e5Alkis Evlogimenos } 843d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner } 844d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner return MayAlias; 845d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner} 846d501c13b7d6ce418b0144886dde16525d13f835aChris Lattner 8474f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Make sure that anything that uses AliasAnalysis pulls in this file... 8484f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(BasicAliasAnalysis) 849