AliasAnalysis.h revision d0fde30ce850b78371fd1386338350591f9ff494
1294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 2294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// 3294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// The LLVM Compiler Infrastructure 4294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// 5294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// This file was developed by the LLVM research group and is distributed under 6294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// the University of Illinois Open Source License. See LICENSE.TXT for details. 7294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// 8294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===----------------------------------------------------------------------===// 9294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// 10294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// This file defines the generic AliasAnalysis interface, which is used as the 11294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// common interface used by all clients of alias analysis information, and 12294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// implemented by all alias analysis implementations. Mod/Ref information is 13294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// also captured by this interface. 14d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46Ted Kremenek// 15294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// Implementations of this interface must implement the various virtual methods, 16294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// which automatically provides functionality for the entire suite of client 17740d490593e0de8732a697c9f77b90ddd463863bJordan Rose// APIs. 18294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// 194a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer// This API represents memory as a (Pointer, Size) pair. The Pointer component 204a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer// specifies the base memory address of the region, the Size specifies how large 21294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// of an area is being queried. If Size is 0, two pointers only alias if they 22294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// are exactly equal. If size is greater than zero, but small, the two pointers 23294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// alias if the areas pointed to overlap. If the size is very large (ie, ~0U), 24294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// then the two pointers alias if they may be pointing to components of the same 25fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose// memory object. Pointers that point to two completely different objects in 26fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose// memory never alias, regardless of the value of the Size component. 27fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose// 28fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose//===----------------------------------------------------------------------===// 29fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose 30fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H 31fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H 32fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose 33fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose#include "llvm/Support/CallSite.h" 34fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose 35fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rosenamespace llvm { 36fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Rose 37fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Roseclass LoadInst; 38fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Roseclass StoreInst; 39fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Roseclass TargetData; 40fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Roseclass AnalysisUsage; 41fdaa33818cf9bad8d092136e73bd2e489cb821baJordan Roseclass Pass; 423070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek 433070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenekclass AliasAnalysis { 440849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek const TargetData *TD; 450849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenekprotected: 463070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// InitializeAliasAnalysis - Subclasses must call this method to initialize 473070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// the AliasAnalysis interface before any other methods are called. This is 483070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// typically called by the run* methods of these subclasses. This may be 493070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// called multiple times. 503070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// 513070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek void InitializeAliasAnalysis(Pass *P); 523070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek 533070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek // getAnalysisUsage - All alias analysis implementations should invoke this 543070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that 553070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek // TargetData is required by the pass. 560849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek virtual void getAnalysisUsage(AnalysisUsage &AU) const; 573070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek 58e54cfc7b9990acffd0a8a4ba381717b4bb9f3011Jordan Rosepublic: 593070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek AliasAnalysis() : TD(0) {} 603070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek virtual ~AliasAnalysis(); // We want to be subclassed 613070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek 623070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// getTargetData - Every alias analysis implementation depends on the size of 633070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// data items in the current Target. This provides a uniform way to handle 643070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek /// it. 653070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek const TargetData &getTargetData() const { return *TD; } 66294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek 67294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek //===--------------------------------------------------------------------===// 680b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// Alias Queries... 690b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 700b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 710b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// Alias analysis result - Either we know for sure that it does not alias, we 720b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// know for sure it must alias, or we don't know anything: The two pointers 730b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// _might_ alias. This enum is designed so you can do things like: 740b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// if (AA.alias(P1, P2)) { ... } 750b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// to check to see if two pointers might alias. 76256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// 77256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; 780b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 790b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// alias - The main low level interface to the alias analysis implementation. 80256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// Returns a Result indicating whether the two pointers are aliased to each 81256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// other. This is the interface that must be implemented by specific alias 82256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// analysis implementations. 830b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 840b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks virtual AliasResult alias(const Value *V1, unsigned V1Size, 850b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks const Value *V2, unsigned V2Size) { 860b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return MayAlias; 87256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek } 880b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 890b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// getMustAliases - If there are any pointers known that must alias this 900b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// pointer, return them now. This allows alias-set based alias analyses to 910b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// perform a form a value numbering (which is exposed by load-vn). If an 920b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// alias analysis supports this, it should ADD any must aliased pointers to 930b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// the specified vector. 940b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 950b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) {} 960b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 970b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 980b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks //===--------------------------------------------------------------------===// 990b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// Simple mod/ref information... 1000b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 101256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek 102256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are 103256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek /// bits which may be or'd together. 1040b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 105256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; 106256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek 1070b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// getModRefInfo - Return information about whether or not an instruction may 1080b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// read or write memory specified by the pointer operand. An instruction 1090b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// that doesn't read or write memory may be trivially LICM'd for example. 1100b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 1110b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// getModRefInfo (for call sites) - Return whether information about whether 1120b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// a particular call site modifies or reads the memory specified by the 1130b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// pointer. 1140b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 1150b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) { 1160b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks return ModRef; 1170b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 1180b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 1190b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// getModRefInfo - Return information about whether two call sites may refer 1207fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek /// to the same set of memory locations. This function returns NoModRef if 1217fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek /// the two calls refer to disjoint memory locations, Ref if they both read 1227fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek /// some of the same memory, Mod if they both write to some of the same 1237fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek /// memory, and ModRef if they read and write to the same memory. 1247fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek /// 1257fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 126294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek return ModRef; 1270b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 1280b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks 1290b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// Convenience functions... 1300b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size); 1310b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks ModRefResult getModRefInfo(StoreInst*S, Value *P, unsigned Size); 1320b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) { 133852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose return getModRefInfo(CallSite(C), P, Size); 1340b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks } 135294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek ModRefResult getModRefInfo(InvokeInst*I, Value *P, unsigned Size) { 136852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose return getModRefInfo(CallSite(I), P, Size); 137852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose } 138852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) { 139852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose switch (I->getOpcode()) { 14048b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose case Instruction::Load: return getModRefInfo((LoadInst*)I, P, Size); 141852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose case Instruction::Store: return getModRefInfo((StoreInst*)I, P, Size); 1420b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks case Instruction::Call: return getModRefInfo((CallInst*)I, P, Size); 143852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size); 144852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose default: return NoModRef; 145852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose } 146852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose } 147852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose 1480b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// canBasicBlockModify - Return true if it is possible for execution of the 149852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose /// specified basic block to modify the value pointed to by Ptr. 15048b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose /// 151852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size); 152294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek 1530b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// canInstructionRangeModify - Return true if it is possible for the 1540b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// execution of the specified instructions to modify the value pointed to by 1550b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// Ptr. The instructions to consider are all of the instructions in the 1560b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 1570b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks /// 1580b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 1590b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks const Value *Ptr, unsigned Size); 1600b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks}; 16148b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose 16248b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose} // End llvm namespace 16348b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose 16448b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose#endif 16548b6247804eacc262cc5508e0fbb74ed819fbb6eJordan Rose