1 //===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==//
3 // This file implements the generic AliasAnalysis interface which is used as the
4 // common interface used by all clients and implementations of alias analysis.
6 // This file also implements the default version of the AliasAnalysis interface
7 // that is to be used when no other implementation is specified. This does some
8 // simple tests that detect obvious cases: two different global pointers cannot
9 // alias, a global cannot alias a malloc, two different mallocs cannot alias,
12 // This alias analysis implementation really isn't very good for anything, but
13 // it is very fast, and makes a nice clean default implementation. Because it
14 // handles lots of little corner cases, other, more complex, alias analysis
15 // implementations may choose to rely on this pass to resolve these simple and
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Analysis/BasicAliasAnalysis.h"
21 #include "llvm/BasicBlock.h"
22 #include "llvm/iMemory.h"
23 #include "llvm/iOther.h"
24 #include "llvm/Constants.h"
25 #include "llvm/ConstantHandling.h"
26 #include "llvm/GlobalValue.h"
27 #include "llvm/DerivedTypes.h"
28 #include "llvm/Target/TargetData.h"
30 // Register the AliasAnalysis interface, providing a nice name to refer to.
32 RegisterAnalysisGroup<AliasAnalysis> Z("Alias Analysis");
35 AliasAnalysis::ModRefResult
36 AliasAnalysis::getModRefInfo(LoadInst *L, Value *P, unsigned Size) {
37 return alias(L->getOperand(0), TD->getTypeSize(L->getType()),
38 P, Size) ? Ref : NoModRef;
41 AliasAnalysis::ModRefResult
42 AliasAnalysis::getModRefInfo(StoreInst *S, Value *P, unsigned Size) {
43 return alias(S->getOperand(1), TD->getTypeSize(S->getOperand(0)->getType()),
44 P, Size) ? Mod : NoModRef;
48 // AliasAnalysis destructor: DO NOT move this to the header file for
49 // AliasAnalysis or else clients of the AliasAnalysis class may not depend on
50 // the AliasAnalysis.o file in the current .a file, causing alias analysis
51 // support to not be included in the tool correctly!
53 AliasAnalysis::~AliasAnalysis() {}
55 /// setTargetData - Subclasses must call this method to initialize the
56 /// AliasAnalysis interface before any other methods are called.
58 void AliasAnalysis::InitializeAliasAnalysis(Pass *P) {
59 TD = &P->getAnalysis<TargetData>();
62 // getAnalysisUsage - All alias analysis implementations should invoke this
63 // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
64 // TargetData is required by the pass.
65 void AliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
66 AU.addRequired<TargetData>(); // All AA's need TargetData.
69 /// canBasicBlockModify - Return true if it is possible for execution of the
70 /// specified basic block to modify the value pointed to by Ptr.
72 bool AliasAnalysis::canBasicBlockModify(const BasicBlock &BB,
73 const Value *Ptr, unsigned Size) {
74 return canInstructionRangeModify(BB.front(), BB.back(), Ptr, Size);
77 /// canInstructionRangeModify - Return true if it is possible for the execution
78 /// of the specified instructions to modify the value pointed to by Ptr. The
79 /// instructions to consider are all of the instructions in the range of [I1,I2]
80 /// INCLUSIVE. I1 and I2 must be in the same basic block.
82 bool AliasAnalysis::canInstructionRangeModify(const Instruction &I1,
83 const Instruction &I2,
84 const Value *Ptr, unsigned Size) {
85 assert(I1.getParent() == I2.getParent() &&
86 "Instructions not in same basic block!");
87 BasicBlock::iterator I = const_cast<Instruction*>(&I1);
88 BasicBlock::iterator E = const_cast<Instruction*>(&I2);
89 ++E; // Convert from inclusive to exclusive range.
91 for (; I != E; ++I) // Check every instruction in range
92 if (getModRefInfo(I, const_cast<Value*>(Ptr), Size) & Mod)
97 //===----------------------------------------------------------------------===//
98 // BasicAliasAnalysis Pass Implementation
99 //===----------------------------------------------------------------------===//
101 // Because of the way .a files work, the implementation of the
102 // BasicAliasAnalysis class MUST be in the AliasAnalysis file itself, or else we
103 // run the risk of AliasAnalysis being used, but the default implementation not
104 // being linked into the tool that uses it. As such, we register and implement
108 // Register this pass...
109 RegisterOpt<BasicAliasAnalysis>
110 X("basicaa", "Basic Alias Analysis (default AA impl)");
112 // Declare that we implement the AliasAnalysis interface
113 RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y;
114 } // End of anonymous namespace
116 void BasicAliasAnalysis::initializePass() {
117 InitializeAliasAnalysis(this);
122 // hasUniqueAddress - Return true if the
123 static inline bool hasUniqueAddress(const Value *V) {
124 return isa<GlobalValue>(V) || isa<MallocInst>(V) || isa<AllocaInst>(V);
127 static const Value *getUnderlyingObject(const Value *V) {
128 if (!isa<PointerType>(V->getType())) return 0;
130 // If we are at some type of object... return it.
131 if (hasUniqueAddress(V)) return V;
133 // Traverse through different addressing mechanisms...
134 if (const Instruction *I = dyn_cast<Instruction>(V)) {
135 if (isa<CastInst>(I) || isa<GetElementPtrInst>(I))
136 return getUnderlyingObject(I->getOperand(0));
142 // alias - Provide a bunch of ad-hoc rules to disambiguate in common cases, such
143 // as array references. Note that this function is heavily tail recursive.
144 // Hopefully we have a smart C++ compiler. :)
146 AliasAnalysis::AliasResult
147 BasicAliasAnalysis::alias(const Value *V1, unsigned V1Size,
148 const Value *V2, unsigned V2Size) {
149 // Strip off constant pointer refs if they exist
150 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1))
151 V1 = CPR->getValue();
152 if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2))
153 V2 = CPR->getValue();
155 // Are we checking for alias of the same value?
156 if (V1 == V2) return MustAlias;
158 if ((!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) &&
159 V1->getType() != Type::LongTy && V2->getType() != Type::LongTy)
160 return NoAlias; // Scalars cannot alias each other
162 // Strip off cast instructions...
163 if (const Instruction *I = dyn_cast<CastInst>(V1))
164 return alias(I->getOperand(0), V1Size, V2, V2Size);
165 if (const Instruction *I = dyn_cast<CastInst>(V2))
166 return alias(V1, V1Size, I->getOperand(0), V2Size);
168 // Figure out what objects these things are pointing to if we can...
169 const Value *O1 = getUnderlyingObject(V1);
170 const Value *O2 = getUnderlyingObject(V2);
172 // Pointing at a discernable object?
174 // If they are two different objects, we know that we have no alias...
175 if (O1 != O2) return NoAlias;
177 // If they are the same object, they we can look at the indexes. If they
178 // index off of the object is the same for both pointers, they must alias.
179 // If they are provably different, they must not alias. Otherwise, we can't
181 } else if (O1 && isa<ConstantPointerNull>(V2)) {
182 return NoAlias; // Unique values don't alias null
183 } else if (O2 && isa<ConstantPointerNull>(V1)) {
184 return NoAlias; // Unique values don't alias null
187 // If we have two gep instructions with identical indices, return an alias
188 // result equal to the alias result of the original pointer...
190 if (const GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(V1))
191 if (const GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(V2))
192 if (GEP1->getNumOperands() == GEP2->getNumOperands() &&
193 GEP1->getOperand(0)->getType() == GEP2->getOperand(0)->getType()) {
195 CheckGEPInstructions((GetElementPtrInst*)GEP1, V1Size,
196 (GetElementPtrInst*)GEP2, V2Size);
197 if (GAlias != MayAlias)
201 // Check to see if these two pointers are related by a getelementptr
202 // instruction. If one pointer is a GEP with a non-zero index of the other
203 // pointer, we know they cannot alias.
205 if (isa<GetElementPtrInst>(V2)) {
207 std::swap(V1Size, V2Size);
210 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V1))
211 if (GEP->getOperand(0) == V2) {
212 // If there is at least one non-zero constant index, we know they cannot
214 for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
215 if (const Constant *C = dyn_cast<Constant>(GEP->getOperand(i)))
216 if (!C->isNullValue())
223 // CheckGEPInstructions - Check two GEP instructions of compatible types and
224 // equal number of arguments. This checks to see if the index expressions
225 // preclude the pointers from aliasing...
227 AliasAnalysis::AliasResult
228 BasicAliasAnalysis::CheckGEPInstructions(GetElementPtrInst *GEP1, unsigned G1S,
229 GetElementPtrInst *GEP2, unsigned G2S){
230 // Do the base pointers alias?
231 AliasResult BaseAlias = alias(GEP1->getOperand(0), G1S,
232 GEP2->getOperand(0), G2S);
233 if (BaseAlias != MustAlias) // No or May alias: We cannot add anything...
236 // Find the (possibly empty) initial sequence of equal values...
237 unsigned NumGEPOperands = GEP1->getNumOperands();
238 unsigned UnequalOper = 1;
239 while (UnequalOper != NumGEPOperands &&
240 GEP1->getOperand(UnequalOper) == GEP2->getOperand(UnequalOper))
243 // If all operands equal each other, then the derived pointers must
244 // alias each other...
245 if (UnequalOper == NumGEPOperands) return MustAlias;
247 // So now we know that the indexes derived from the base pointers,
248 // which are known to alias, are different. We can still determine a
249 // no-alias result if there are differing constant pairs in the index
250 // chain. For example:
251 // A[i][0] != A[j][1] iff (&A[0][1]-&A[0][0] >= std::max(G1S, G2S))
253 unsigned SizeMax = std::max(G1S, G2S);
254 if (SizeMax == ~0U) return MayAlias; // Avoid frivolous work...
256 // Scan for the first operand that is constant and unequal in the
257 // two getelemenptrs...
258 unsigned FirstConstantOper = UnequalOper;
259 for (; FirstConstantOper != NumGEPOperands; ++FirstConstantOper) {
260 const Value *G1Oper = GEP1->getOperand(FirstConstantOper);
261 const Value *G2Oper = GEP2->getOperand(FirstConstantOper);
262 if (G1Oper != G2Oper && // Found non-equal constant indexes...
263 isa<Constant>(G1Oper) && isa<Constant>(G2Oper)) {
264 // Make sure they are comparable... and make sure the GEP with
265 // the smaller leading constant is GEP1.
266 ConstantBool *Compare =
267 *cast<Constant>(GEP1->getOperand(FirstConstantOper)) >
268 *cast<Constant>(GEP2->getOperand(FirstConstantOper));
269 if (Compare) { // If they are comparable...
270 if (Compare->getValue())
271 std::swap(GEP1, GEP2); // Make GEP1 < GEP2
277 // No constant operands, we cannot tell anything...
278 if (FirstConstantOper == NumGEPOperands) return MayAlias;
280 // If there are non-equal constants arguments, then we can figure
281 // out a minimum known delta between the two index expressions... at
282 // this point we know that the first constant index of GEP1 is less
283 // than the first constant index of GEP2.
285 std::vector<Value*> Indices1;
286 Indices1.reserve(NumGEPOperands-1);
287 for (unsigned i = 1; i != FirstConstantOper; ++i)
288 Indices1.push_back(Constant::getNullValue(GEP1->getOperand(i)
290 std::vector<Value*> Indices2;
291 Indices2.reserve(NumGEPOperands-1);
292 Indices2 = Indices1; // Copy the zeros prefix...
294 // Add the two known constant operands...
295 Indices1.push_back((Value*)GEP1->getOperand(FirstConstantOper));
296 Indices2.push_back((Value*)GEP2->getOperand(FirstConstantOper));
298 const Type *GEPPointerTy = GEP1->getOperand(0)->getType();
300 // Loop over the rest of the operands...
301 for (unsigned i = FirstConstantOper+1; i!=NumGEPOperands; ++i){
302 const Value *Op1 = GEP1->getOperand(i);
303 const Value *Op2 = GEP1->getOperand(i);
304 if (Op1 == Op2) { // If they are equal, use a zero index...
305 Indices1.push_back(Constant::getNullValue(Op1->getType()));
306 Indices2.push_back(Indices1.back());
308 if (isa<Constant>(Op1))
309 Indices1.push_back((Value*)Op1);
311 // GEP1 is known to produce a value less than GEP2. To be
312 // conservatively correct, we must assume the largest
313 // possible constant is used in this position. This cannot
314 // be the initial index to the GEP instructions (because we
315 // know we have at least one element before this one with
316 // the different constant arguments), so we know that the
317 // current index must be into either a struct or array.
318 // Because of this, we can calculate the maximum value
321 const Type *ElTy = GEP1->getIndexedType(GEPPointerTy,
323 if (const StructType *STy = dyn_cast<StructType>(ElTy)) {
324 Indices1.push_back(ConstantUInt::get(Type::UByteTy,
325 STy->getNumContainedTypes()));
327 Indices1.push_back(ConstantSInt::get(Type::LongTy,
328 cast<ArrayType>(ElTy)->getNumElements()));
332 if (isa<Constant>(Op2))
333 Indices2.push_back((Value*)Op2);
334 else // Conservatively assume the minimum value for this index
335 Indices2.push_back(Constant::getNullValue(Op1->getType()));
339 unsigned Offset1 = getTargetData().getIndexedOffset(GEPPointerTy, Indices1);
340 unsigned Offset2 = getTargetData().getIndexedOffset(GEPPointerTy, Indices2);
341 assert(Offset1 < Offset2 &&"There is at least one different constant here!");
343 if (Offset2-Offset1 >= SizeMax) {
344 //std::cerr << "Determined that these two GEP's don't alias ["
345 // << SizeMax << " bytes]: \n" << *GEP1 << *GEP2;