AliasAnalysis.cpp revision 2c20ef506f65f649fd9fb8823f8c7b0086b1ba5c
1//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/BasicBlock.h" 29#include "llvm/Instructions.h" 30#include "llvm/Target/TargetData.h" 31#include <iostream> 32using namespace llvm; 33 34// Register the AliasAnalysis interface, providing a nice name to refer to. 35namespace { 36 RegisterAnalysisGroup<AliasAnalysis> Z("Alias Analysis"); 37} 38 39//===----------------------------------------------------------------------===// 40// Default chaining methods 41//===----------------------------------------------------------------------===// 42 43AliasAnalysis::AliasResult 44AliasAnalysis::alias(const Value *V1, unsigned V1Size, 45 const Value *V2, unsigned V2Size) { 46 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 47 return AA->alias(V1, V1Size, V2, V2Size); 48} 49 50void AliasAnalysis::getMustAliases(Value *P, std::vector<Value*> &RetVals) { 51 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 52 return AA->getMustAliases(P, RetVals); 53} 54 55bool AliasAnalysis::pointsToConstantMemory(const Value *P) { 56 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 57 return AA->pointsToConstantMemory(P); 58} 59 60bool AliasAnalysis::doesNotAccessMemory(Function *F) { 61 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 62 return AA->doesNotAccessMemory(F); 63} 64 65bool AliasAnalysis::onlyReadsMemory(Function *F) { 66 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 67 return doesNotAccessMemory(F) || AA->onlyReadsMemory(F); 68} 69 70bool AliasAnalysis::hasNoModRefInfoForCalls() const { 71 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 72 return AA->hasNoModRefInfoForCalls(); 73} 74 75void AliasAnalysis::deleteValue(Value *V) { 76 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 77 AA->deleteValue(V); 78} 79 80void AliasAnalysis::copyValue(Value *From, Value *To) { 81 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 82 AA->copyValue(From, To); 83} 84 85AliasAnalysis::ModRefResult 86AliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 87 // FIXME: we can do better. 88 assert(AA && "AA didn't call InitializeAliasAnalysis in its run method!"); 89 return AA->getModRefInfo(CS1, CS2); 90} 91 92 93//===----------------------------------------------------------------------===// 94// AliasAnalysis non-virtual helper method implementation 95//===----------------------------------------------------------------------===// 96 97AliasAnalysis::ModRefResult 98AliasAnalysis::getModRefInfo(LoadInst *L, Value *P, unsigned Size) { 99 return alias(L->getOperand(0), TD->getTypeSize(L->getType()), 100 P, Size) ? Ref : NoModRef; 101} 102 103AliasAnalysis::ModRefResult 104AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) { 105 // If the stored address cannot alias the pointer in question, then the 106 // pointer cannot be modified by the store. 107 if (!alias(S->getOperand(1), TD->getTypeSize(S->getOperand(0)->getType()), 108 P, Size)) 109 return NoModRef; 110 111 // If the pointer is a pointer to constant memory, then it could not have been 112 // modified by this store. 113 return pointsToConstantMemory(P) ? NoModRef : Mod; 114} 115 116AliasAnalysis::ModRefResult 117AliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 118 ModRefResult Mask = ModRef; 119 if (Function *F = CS.getCalledFunction()) 120 if (onlyReadsMemory(F)) { 121 if (doesNotAccessMemory(F)) return NoModRef; 122 Mask = Ref; 123 } 124 125 if (!AA) return Mask; 126 127 // If P points to a constant memory location, the call definitely could not 128 // modify the memory location. 129 if ((Mask & Mod) && AA->pointsToConstantMemory(P)) 130 Mask = Ref; 131 132 return ModRefResult(Mask & AA->getModRefInfo(CS, P, Size)); 133} 134 135// AliasAnalysis destructor: DO NOT move this to the header file for 136// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 137// the AliasAnalysis.o file in the current .a file, causing alias analysis 138// support to not be included in the tool correctly! 139// 140AliasAnalysis::~AliasAnalysis() {} 141 142/// setTargetData - Subclasses must call this method to initialize the 143/// AliasAnalysis interface before any other methods are called. 144/// 145void AliasAnalysis::InitializeAliasAnalysis(Pass *P) { 146 TD = &P->getAnalysis<TargetData>(); 147 AA = &P->getAnalysis<AliasAnalysis>(); 148} 149 150// getAnalysisUsage - All alias analysis implementations should invoke this 151// directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that 152// TargetData is required by the pass. 153void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 154 AU.addRequired<TargetData>(); // All AA's need TargetData. 155 AU.addRequired<AliasAnalysis>(); // All AA's chain 156} 157 158/// canBasicBlockModify - Return true if it is possible for execution of the 159/// specified basic block to modify the value pointed to by Ptr. 160/// 161bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB, 162 const Value *Ptr, unsigned Size) { 163 return canInstructionRangeModify(BB.front(), BB.back(), Ptr, Size); 164} 165 166/// canInstructionRangeModify - Return true if it is possible for the execution 167/// of the specified instructions to modify the value pointed to by Ptr. The 168/// instructions to consider are all of the instructions in the range of [I1,I2] 169/// INCLUSIVE. I1 and I2 must be in the same basic block. 170/// 171bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 172 const Instruction &I2, 173 const Value *Ptr, unsigned Size) { 174 assert(I1.getParent() == I2.getParent() && 175 "Instructions not in same basic block!"); 176 BasicBlock::iterator I = const_cast<Instruction*>(&I1); 177 BasicBlock::iterator E = const_cast<Instruction*>(&I2); 178 ++E; // Convert from inclusive to exclusive range. 179 180 for (; I != E; ++I) // Check every instruction in range 181 if (getModRefInfo(I, const_cast<Value*>(Ptr), Size) & Mod) 182 return true; 183 return false; 184} 185 186// Because of the way .a files work, we must force the BasicAA implementation to 187// be pulled in if the AliasAnalysis classes are pulled in. Otherwise we run 188// the risk of AliasAnalysis being used, but the default implementation not 189// being linked into the tool that uses it. 190// 191namespace llvm { 192 extern void BasicAAStub(); 193} 194static IncludeFile INCLUDE_BASICAA_CPP((void*)&BasicAAStub); 195