AliasAnalysis.h revision 62b5c167de0ca5883a7ad5eb0900eb0c15ad3707
14df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 24df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// 34df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// This file defines the generic AliasAnalysis interface, which is used as the 44df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// common interface used by all clients of alias analysis information, and 51c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// implemented by all alias analysis implementations. Mod/Ref information is 61c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// also captured by this interface. 74df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// 84df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// Implementations of this interface must implement the various virtual methods, 94df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// which automatically provides functionality for the entire suite of client 104df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// APIs. 114df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner// 121c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// This API represents memory as a (Pointer, Size) pair. The Pointer component 131c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// specifies the base memory address of the region, the Size specifies how large 141c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// of an area is being queried. If Size is 0, two pointers only alias if they 151c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// are exactly equal. If size is greater than zero, but small, the two pointers 161c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// alias if the areas pointed to overlap. If the size is very large (ie, ~0U), 171c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// then the two pointers alias if they may be pointing to components of the same 181c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// memory object. Pointers that point to two completely different objects in 191c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// memory never alias, regardless of the value of the Size component. 201c56b730a6313886076d7b293a126ae5576f5288Chris Lattner// 214df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner//===----------------------------------------------------------------------===// 224df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 234df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H 244df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H 254df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 261c56b730a6313886076d7b293a126ae5576f5288Chris Lattner#include "llvm/Support/CallSite.h" 271c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass LoadInst; 281c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass StoreInst; 291c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass TargetData; 301c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass AnalysisUsage; 311c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass Pass; 321c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 331c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerclass AliasAnalysis { 341c56b730a6313886076d7b293a126ae5576f5288Chris Lattner const TargetData *TD; 351c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerprotected: 361c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// InitializeAliasAnalysis - Subclasses must call this method to initialize 371c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// the AliasAnalysis interface before any other methods are called. This is 381c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// typically called by the run* methods of these subclasses. This may be 391c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// called multiple times. 401c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// 411c56b730a6313886076d7b293a126ae5576f5288Chris Lattner void InitializeAliasAnalysis(Pass *P); 421c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 431c56b730a6313886076d7b293a126ae5576f5288Chris Lattner // getAnalysisUsage - All alias analysis implementations should invoke this 441c56b730a6313886076d7b293a126ae5576f5288Chris Lattner // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that 451c56b730a6313886076d7b293a126ae5576f5288Chris Lattner // TargetData is required by the pass. 461c56b730a6313886076d7b293a126ae5576f5288Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const; 471c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 481c56b730a6313886076d7b293a126ae5576f5288Chris Lattnerpublic: 491c56b730a6313886076d7b293a126ae5576f5288Chris Lattner AliasAnalysis() : TD(0) {} 501c56b730a6313886076d7b293a126ae5576f5288Chris Lattner virtual ~AliasAnalysis(); // We want to be subclassed 511c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 521c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// getTargetData - Every alias analysis implementation depends on the size of 531c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// data items in the current Target. This provides a uniform way to handle 541c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// it. 551c56b730a6313886076d7b293a126ae5576f5288Chris Lattner const TargetData &getTargetData() const { return *TD; } 564df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 571c56b730a6313886076d7b293a126ae5576f5288Chris Lattner //===--------------------------------------------------------------------===// 581c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// Alias Queries... 591c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// 604df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 61f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// Alias analysis result - Either we know for sure that it does not alias, we 62f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// know for sure it must alias, or we don't know anything: The two pointers 63f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// _might_ alias. This enum is designed so you can do things like: 64f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// if (AA.alias(P1, P2)) { ... } 65f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// to check to see if two pointers might alias. 66f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 671c56b730a6313886076d7b293a126ae5576f5288Chris Lattner enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; 684df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 69f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// alias - The main low level interface to the alias analysis implementation. 70f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// Returns a Result indicating whether the two pointers are aliased to each 71f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// other. This is the interface that must be implemented by specific alias 72f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// analysis implementations. 73f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 741c56b730a6313886076d7b293a126ae5576f5288Chris Lattner virtual AliasResult alias(const Value *V1, unsigned V1Size, 751c56b730a6313886076d7b293a126ae5576f5288Chris Lattner const Value *V2, unsigned V2Size) { 761c56b730a6313886076d7b293a126ae5576f5288Chris Lattner return MayAlias; 771c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 784df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 7962b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// getMustAliases - If there are any pointers known that must alias this 8062b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// pointer, return them now. This allows alias-set based alias analyses to 8162b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// perform a form a value numbering (which is exposed by load-vn). If an 8262b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// alias analysis supports this, it should ADD any must aliased pointers to 8362b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// the specified vector. 8462b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner /// 8562b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) {} 8662b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner 8762b5c167de0ca5883a7ad5eb0900eb0c15ad3707Chris Lattner 881c56b730a6313886076d7b293a126ae5576f5288Chris Lattner //===--------------------------------------------------------------------===// 891c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// Simple mod/ref information... 90f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 914df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 921c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are 931c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// bits which may be or'd together. 94f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 951c56b730a6313886076d7b293a126ae5576f5288Chris Lattner enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; 961c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 971c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// getModRefInfo - Return information about whether or not an instruction may 981c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// read or write memory specified by the pointer operand. An instruction 991c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// that doesn't read or write memory may be trivially LICM'd for example. 1001c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 1011c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// getModRefInfo (for call sites) - Return whether information about whether 1021c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// a particular call site modifies or reads the memory specified by the 1031c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// pointer. 1041c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// 1051c56b730a6313886076d7b293a126ae5576f5288Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 1061c56b730a6313886076d7b293a126ae5576f5288Chris Lattner return ModRef; 1071c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1081c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 1091c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// getModRefInfo - Return information about whether two call sites may refer 1101c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// to the same set of memory locations. This function returns NoModRef if 1111c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// the two calls refer to disjoint memory locations, Ref if they both read 1121c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// some of the same memory, Mod if they both write to some of the same 1131c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// memory, and ModRef if they read and write to the same memory. 1141c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// 1151c56b730a6313886076d7b293a126ae5576f5288Chris Lattner virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 1161c56b730a6313886076d7b293a126ae5576f5288Chris Lattner return ModRef; 1171c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1181c56b730a6313886076d7b293a126ae5576f5288Chris Lattner 1191c56b730a6313886076d7b293a126ae5576f5288Chris Lattner /// Convenience functions... 1201c56b730a6313886076d7b293a126ae5576f5288Chris Lattner ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size); 1211c56b730a6313886076d7b293a126ae5576f5288Chris Lattner ModRefResult getModRefInfo(StoreInst*S, Value *P, unsigned Size); 1221c56b730a6313886076d7b293a126ae5576f5288Chris Lattner ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) { 1231c56b730a6313886076d7b293a126ae5576f5288Chris Lattner return getModRefInfo(CallSite(C), P, Size); 1241c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1251c56b730a6313886076d7b293a126ae5576f5288Chris Lattner ModRefResult getModRefInfo(InvokeInst*I, Value *P, unsigned Size) { 1261c56b730a6313886076d7b293a126ae5576f5288Chris Lattner return getModRefInfo(CallSite(I), P, Size); 1271c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1281c56b730a6313886076d7b293a126ae5576f5288Chris Lattner ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) { 1291c56b730a6313886076d7b293a126ae5576f5288Chris Lattner switch (I->getOpcode()) { 1301c56b730a6313886076d7b293a126ae5576f5288Chris Lattner case Instruction::Load: return getModRefInfo((LoadInst*)I, P, Size); 1311c56b730a6313886076d7b293a126ae5576f5288Chris Lattner case Instruction::Store: return getModRefInfo((StoreInst*)I, P, Size); 1321c56b730a6313886076d7b293a126ae5576f5288Chris Lattner case Instruction::Call: return getModRefInfo((CallInst*)I, P, Size); 1331c56b730a6313886076d7b293a126ae5576f5288Chris Lattner case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size); 1341c56b730a6313886076d7b293a126ae5576f5288Chris Lattner default: return NoModRef; 1351c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1361c56b730a6313886076d7b293a126ae5576f5288Chris Lattner } 1374df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 138f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// canBasicBlockModify - Return true if it is possible for execution of the 139f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// specified basic block to modify the value pointed to by Ptr. 140f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 1411c56b730a6313886076d7b293a126ae5576f5288Chris Lattner bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size); 1424df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 143f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// canInstructionRangeModify - Return true if it is possible for the 144f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// execution of the specified instructions to modify the value pointed to by 145f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// Ptr. The instructions to consider are all of the instructions in the 146f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 147f12c2c28bd72091f2d7fff5718265c5ad52e7af8Chris Lattner /// 1484df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 1491c56b730a6313886076d7b293a126ae5576f5288Chris Lattner const Value *Ptr, unsigned Size); 1504df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner}; 1514df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner 1524df22c0100fe27f19e6f4874f24eedd0742b9cf4Chris Lattner#endif 153