AliasAnalysis.cpp revision 202375
1//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the generic AliasAnalysis interface which is used as the 11// common interface used by all clients and implementations of alias analysis. 12// 13// This file also implements the default version of the AliasAnalysis interface 14// that is to be used when no other implementation is specified. This does some 15// simple tests that detect obvious cases: two different global pointers cannot 16// alias, a global cannot alias a malloc, two different mallocs cannot alias, 17// etc. 18// 19// This alias analysis implementation really isn't very good for anything, but 20// it is very fast, and makes a nice clean default implementation. Because it 21// handles lots of little corner cases, other, more complex, alias analysis 22// implementations may choose to rely on this pass to resolve these simple and 23// easy cases. 24// 25//===----------------------------------------------------------------------===// 26 27#include "llvm/Analysis/AliasAnalysis.h" 28#include "llvm/Pass.h" 29#include "llvm/BasicBlock.h" 30#include "llvm/Function.h" 31#include "llvm/IntrinsicInst.h" 32#include "llvm/Instructions.h" 33#include "llvm/Type.h" 34#include "llvm/Target/TargetData.h" 35using namespace llvm; 36 37// Register the AliasAnalysis interface, providing a nice name to refer to. 38static RegisterAnalysisGroup<AliasAnalysis> Z("Alias Analysis"); 39char AliasAnalysis::ID = 0; 40 41//===----------------------------------------------------------------------===// 42// Default chaining methods 43//===----------------------------------------------------------------------===// 44 45AliasAnalysis::AliasResult 46AliasAnalysis::alias(const Value *V1, unsigned V1Size, 47 const Value *V2, unsigned V2Size) { 48 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 49 return AA->alias(V1, V1Size, V2, V2Size); 50} 51 52bool AliasAnalysis::pointsToConstantMemory(const Value *P) { 53 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 54 return AA->pointsToConstantMemory(P); 55} 56 57void AliasAnalysis::deleteValue(Value *V) { 58 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 59 AA->deleteValue(V); 60} 61 62void AliasAnalysis::copyValue(Value *From, Value *To) { 63 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 64 AA->copyValue(From, To); 65} 66 67AliasAnalysis::ModRefResult 68AliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 69 // FIXME: we can do better. 70 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 71 return AA->getModRefInfo(CS1, CS2); 72} 73 74 75//===----------------------------------------------------------------------===// 76// AliasAnalysis non-virtual helper method implementation 77//===----------------------------------------------------------------------===// 78 79AliasAnalysis::ModRefResult 80AliasAnalysis::getModRefInfo(LoadInst *L, Value *P, unsigned Size) { 81 return alias(L->getOperand(0), getTypeStoreSize(L->getType()), 82 P, Size) ? Ref : NoModRef; 83} 84 85AliasAnalysis::ModRefResult 86AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) { 87 // If the stored address cannot alias the pointer in question, then the 88 // pointer cannot be modified by the store. 89 if (!alias(S->getOperand(1), 90 getTypeStoreSize(S->getOperand(0)->getType()), P, Size)) 91 return NoModRef; 92 93 // If the pointer is a pointer to constant memory, then it could not have been 94 // modified by this store. 95 return pointsToConstantMemory(P) ? NoModRef : Mod; 96} 97 98AliasAnalysis::ModRefBehavior 99AliasAnalysis::getModRefBehavior(CallSite CS, 100 std::vector<PointerAccessInfo> *Info) { 101 if (CS.doesNotAccessMemory()) 102 // Can't do better than this. 103 return DoesNotAccessMemory; 104 ModRefBehavior MRB = getModRefBehavior(CS.getCalledFunction(), Info); 105 if (MRB != DoesNotAccessMemory && CS.onlyReadsMemory()) 106 return OnlyReadsMemory; 107 return MRB; 108} 109 110AliasAnalysis::ModRefBehavior 111AliasAnalysis::getModRefBehavior(Function *F, 112 std::vector<PointerAccessInfo> *Info) { 113 if (F) { 114 if (F->doesNotAccessMemory()) 115 // Can't do better than this. 116 return DoesNotAccessMemory; 117 if (F->onlyReadsMemory()) 118 return OnlyReadsMemory; 119 if (unsigned id = F->getIntrinsicID()) 120 return getModRefBehavior(id); 121 } 122 return UnknownModRefBehavior; 123} 124 125AliasAnalysis::ModRefBehavior AliasAnalysis::getModRefBehavior(unsigned iid) { 126#define GET_INTRINSIC_MODREF_BEHAVIOR 127#include "llvm/Intrinsics.gen" 128#undef GET_INTRINSIC_MODREF_BEHAVIOR 129} 130 131AliasAnalysis::ModRefResult 132AliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 133 ModRefBehavior MRB = getModRefBehavior(CS); 134 if (MRB == DoesNotAccessMemory) 135 return NoModRef; 136 137 ModRefResult Mask = ModRef; 138 if (MRB == OnlyReadsMemory) 139 Mask = Ref; 140 else if (MRB == AliasAnalysis::AccessesArguments) { 141 bool doesAlias = false; 142 for (CallSite::arg_iterator AI = CS.arg_begin(), AE = CS.arg_end(); 143 AI != AE; ++AI) 144 if (!isNoAlias(*AI, ~0U, P, Size)) { 145 doesAlias = true; 146 break; 147 } 148 149 if (!doesAlias) 150 return NoModRef; 151 } 152 153 if (!AA) return Mask; 154 155 // If P points to a constant memory location, the call definitely could not 156 // modify the memory location. 157 if ((Mask & Mod) && AA->pointsToConstantMemory(P)) 158 Mask = ModRefResult(Mask & ~Mod); 159 160 return ModRefResult(Mask & AA->getModRefInfo(CS, P, Size)); 161} 162 163// AliasAnalysis destructor: DO NOT move this to the header file for 164// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 165// the AliasAnalysis.o file in the current .a file, causing alias analysis 166// support to not be included in the tool correctly! 167// 168AliasAnalysis::~AliasAnalysis() {} 169 170/// InitializeAliasAnalysis - Subclasses must call this method to initialize the 171/// AliasAnalysis interface before any other methods are called. 172/// 173void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 174 TD = P->getAnalysisIfAvailable<TargetData>(); 175 AA = &P->getAnalysis<AliasAnalysis>(); 176} 177 178// getAnalysisUsage - All alias analysis implementations should invoke this 179// directly (using AliasAnalysis::getAnalysisUsage(AU)). 180void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 181 AU.addRequired<AliasAnalysis>(); // All AA's chain 182} 183 184/// getTypeStoreSize - Return the TargetData store size for the given type, 185/// if known, or a conservative value otherwise. 186/// 187unsigned AliasAnalysis::getTypeStoreSize(const Type *Ty) { 188 return TD ? TD->getTypeStoreSize(Ty) : ~0u; 189} 190 191/// canBasicBlockModify - Return true if it is possible for execution of the 192/// specified basic block to modify the value pointed to by Ptr. 193/// 194bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 195 const Value *Ptr, unsigned Size) { 196 return canInstructionRangeModify(BB.front(), BB.back(), Ptr, Size); 197} 198 199/// canInstructionRangeModify - Return true if it is possible for the execution 200/// of the specified instructions to modify the value pointed to by Ptr. The 201/// instructions to consider are all of the instructions in the range of [I1,I2] 202/// INCLUSIVE. I1 and I2 must be in the same basic block. 203/// 204bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 205 const Instruction &I2, 206 const Value *Ptr, unsigned Size) { 207 assert(I1.getParent() == I2.getParent() && 208 "Instructions not in same basic block!"); 209 BasicBlock::iterator I = const_cast<Instruction*>(&I1); 210 BasicBlock::iterator E = const_cast<Instruction*>(&I2); 211 ++E; // Convert from inclusive to exclusive range. 212 213 for (; I != E; ++I) // Check every instruction in range 214 if (getModRefInfo(I, const_cast<Value*>(Ptr), Size) & Mod) 215 return true; 216 return false; 217} 218 219/// isNoAliasCall - Return true if this pointer is returned by a noalias 220/// function. 221bool llvm::isNoAliasCall(const Value *V) { 222 if (isa<CallInst>(V) || isa<InvokeInst>(V)) 223 return CallSite(const_cast<Instruction*>(cast<Instruction>(V))) 224 .paramHasAttr(0, Attribute::NoAlias); 225 return false; 226} 227 228/// isIdentifiedObject - Return true if this pointer refers to a distinct and 229/// identifiable object. This returns true for: 230/// Global Variables and Functions (but not Global Aliases) 231/// Allocas and Mallocs 232/// ByVal and NoAlias Arguments 233/// NoAlias returns 234/// 235bool llvm::isIdentifiedObject(const Value *V) { 236 if (isa<AllocaInst>(V) || isNoAliasCall(V)) 237 return true; 238 if (isa<GlobalValue>(V) && !isa<GlobalAlias>(V)) 239 return true; 240 if (const Argument *A = dyn_cast<Argument>(V)) 241 return A->hasNoAliasAttr() || A->hasByValAttr(); 242 return false; 243} 244 245// Because of the way .a files work, we must force the BasicAA implementation to 246// be pulled in if the AliasAnalysis classes are pulled in. Otherwise we run 247// the risk of AliasAnalysis being used, but the default implementation not 248// being linked into the tool that uses it. 249DEFINING_FILE_FOR(AliasAnalysis) 250