AliasAnalysis.cpp revision 53ad0edd361c724df623c082a8a37eaf762d1703
153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation -==// 253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This file implements the generic AliasAnalysis interface which is used as the 453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// common interface used by all clients and implementations of alias analysis. 553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This file also implements the default version of the AliasAnalysis interface 753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// that is to be used when no other implementation is specified. This does some 853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// simple tests that detect obvious cases: two different global pointers cannot 953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// alias, a global cannot alias a malloc, two different mallocs cannot alias, 1053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// etc. 1153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 1253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// This alias analysis implementation really isn't very good for anything, but 1353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// it is very fast, and makes a nice clean default implementation. Because it 1453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// handles lots of little corner cases, other, more complex, alias analysis 1553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// implementations may choose to rely on this pass to resolve these simple and 1653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// easy cases. 1753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 1853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===----------------------------------------------------------------------===// 1953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 2053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/Analysis/BasicAliasAnalysis.h" 2153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/BasicBlock.h" 2253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/Support/InstVisitor.h" 2353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/iMemory.h" 2453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/Constants.h" 2553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/GlobalValue.h" 2653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner#include "llvm/Pass.h" 2753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 2853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// Register the AliasAnalysis interface, providing a nice name to refer to. 2953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerstatic RegisterAnalysisGroup<AliasAnalysis> X("Alias Analysis"); 3053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 3153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// CanModify - Define a little visitor class that is used to check to see if 3253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// arbitrary chunks of code can modify a specified pointer. 3353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 3453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnernamespace { 3553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner struct CanModify : public InstVisitor<CanModify, bool> { 3653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const AliasAnalysis &AA; 3753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Value *Ptr; 3853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 3953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner CanModify(const AliasAnalysis *aa, const Value *ptr) 4053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner : AA(*aa), Ptr(ptr) {} 4153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 4253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool visitInvokeInst(InvokeInst &II) { 4353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return AA.canInvokeModify(II, Ptr); 4453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner } 4553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool visitCallInst(CallInst &CI) { 4653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return AA.canCallModify(CI, Ptr); 4753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner } 4853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool visitStoreInst(StoreInst &SI) { 4953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(!SI.hasIndices() && "Only support stores without indexing!"); 5053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return AA.alias(Ptr, SI.getOperand(1)); 5153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner } 5253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 5353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // Other instructions do not alias anything. 5453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool visitInstruction(Instruction &I) { return false; } 5553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner }; 5653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 5753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 5853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis destructor: DO NOT move this to the header file for 5953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// AliasAnalysis or else clients of the AliasAnalysis class may not depend on 6053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the AliasAnalysis.o file in the current .a file, causing alias analysis 6153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// support to not be included in the tool correctly! 6253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 6353ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::~AliasAnalysis() {} 6453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 6553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// canBasicBlockModify - Return true if it is possible for execution of the 6653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// specified basic block to modify the value pointed to by Ptr. 6753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 6853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canBasicBlockModify(const BasicBlock &bb, 6953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Value *Ptr) const { 7053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner CanModify CM(this, Ptr); 7153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner BasicBlock &BB = const_cast<BasicBlock&>(bb); 7253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 7353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 7453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (CM.visit(I)) // Check every instruction in the basic block... 7553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 7653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 7753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 7853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 7953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 8053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// canInstructionRangeModify - Return true if it is possible for the execution 8153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// of the specified instructions to modify the value pointed to by Ptr. The 8253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// instructions to consider are all of the instructions in the range of [I1,I2] 8353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// INCLUSIVE. I1 and I2 must be in the same basic block. 8453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 8553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerbool AliasAnalysis::canInstructionRangeModify(const Instruction &I1, 8653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Instruction &I2, 8753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Value *Ptr) const { 8853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner assert(I1.getParent() == I2.getParent() && 8953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner "Instructions not in same basic block!"); 9053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner CanModify CM(this, Ptr); 9153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner BasicBlock::iterator I = const_cast<Instruction*>(&I1); 9253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner BasicBlock::iterator E = const_cast<Instruction*>(&I2); 9353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner ++E; // Convert from inclusive to exclusive range. 9453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 9553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner for (; I != E; ++I) 9653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (CM.visit(I)) // Check every instruction in the basic block... 9753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return true; 9853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 9953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return false; 10053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 10153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 10253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===----------------------------------------------------------------------===// 10353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// BasicAliasAnalysis Pass Implementation 10453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner//===----------------------------------------------------------------------===// 10553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 10653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// Because of the way .a files work, the implementation of the 10753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// BasicAliasAnalysis class MUST be in the AliasAnalysis file itself, or else we 10853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// run the risk of AliasAnalysis being used, but the default implementation not 10953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// being linked into the tool that uses it. As such, we register and implement 11053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// the class here. 11153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// 11253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnernamespace { 11353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // Register this pass... 11453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner RegisterOpt<BasicAliasAnalysis> 11553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner X("basicaa", "Basic Alias Analysis (default AA impl)"); 11653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 11753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // Declare that we implement the AliasAnalysis interface 11853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner RegisterAnalysisGroup<AliasAnalysis, BasicAliasAnalysis, true> Y; 11953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} // End of anonymous namespace 12053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 12153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 12253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 12353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner// hasUniqueAddress - Return true if the 12453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattnerstatic inline bool hasUniqueAddress(const Value *V) { 12553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return isa<GlobalValue>(V) || isa<MallocInst>(V) || isa<AllocaInst>(V); 12653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 12753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 12853ad0edd361c724df623c082a8a37eaf762d1703Chris LattnerAliasAnalysis::Result BasicAliasAnalysis::alias(const Value *V1, 12953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner const Value *V2) const { 13053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // Strip off constant pointer refs if they exist 13153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V1)) 13253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner V1 = CPR->getValue(); 13353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V2)) 13453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner V2 = CPR->getValue(); 13553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 13653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // Are we checking for alias of the same value? 13753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (V1 == V2) return MustAlias; 13853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 13953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (!isa<PointerType>(V1->getType()) || !isa<PointerType>(V2->getType())) 14053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return NoAlias; // Scalars cannot alias each other 14153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 14253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool V1Unique = hasUniqueAddress(V1); 14353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner bool V2Unique = hasUniqueAddress(V2); 14453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 14553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if (V1Unique && V2Unique) 14653ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return NoAlias; // Can't alias if they are different unique values 14753ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 14853ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner if ((V1Unique && isa<ConstantPointerNull>(V2)) || 14953ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner (V2Unique && isa<ConstantPointerNull>(V1))) 15053ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return NoAlias; // Unique values don't alias null 15153ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 15253ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner // TODO: Handle getelementptr with nonzero offset 15353ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner 15453ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner return MayAlias; 15553ad0edd361c724df623c082a8a37eaf762d1703Chris Lattner} 156