AliasAnalysis.h revision e88ccb545d0e03fd4445d361100fc95f350c6663
14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===// 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The LLVM Compiler Infrastructure 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// This file is distributed under the University of Illinois Open Source 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// License. See LICENSE.TXT for details. 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//===----------------------------------------------------------------------===// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// This file defines the generic AliasAnalysis interface, which is used as the 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// common interface used by all clients of alias analysis information, and 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// implemented by all alias analysis implementations. Mod/Ref information is 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// also captured by this interface. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementations of this interface must implement the various virtual methods, 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// which automatically provides functionality for the entire suite of client 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// APIs. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// This API represents memory as a (Pointer, Size) pair. The Pointer component 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// specifies the base memory address of the region, the Size specifies how large 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of an area is being queried, or UnknownSize if the size is not known. 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Pointers that point to two completely different objects in memory never 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// alias, regardless of the value of the Size component. 2473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers// 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project//===----------------------------------------------------------------------===// 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "llvm/Support/CallSite.h" 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <vector> 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace llvm { 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass LoadInst; 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StoreInst; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass VAArgInst; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass TargetData; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass Pass; 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass AnalysisUsage; 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass AliasAnalysis { 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprotected: 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const TargetData *TD; 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprivate: 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AliasAnalysis *AA; // Previous Alias Analysis to chain to. 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprotected: 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// InitializeAliasAnalysis - Subclasses must call this method to initialize 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// the AliasAnalysis interface before any other methods are called. This is 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// typically called by the run* methods of these subclasses. This may be 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// called multiple times. 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void InitializeAliasAnalysis(Pass *P); 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// getAnalysisUsage - All alias analysis implementations should invoke this 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// directly (using AliasAnalysis::getAnalysisUsage(AU)). 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void getAnalysisUsage(AnalysisUsage &AU) const; 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectpublic: 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static char ID; // Class identification, replacement for typeinfo 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AliasAnalysis() : TD(0), AA(0) {} 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~AliasAnalysis(); // We want to be subclassed 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// UnknownSize - This is a special value which can be used with the 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// size arguments in alias queries to indicate that the caller does not 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// know the sizes of the potential memory references. 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static uint64_t const UnknownSize = ~UINT64_C(0); 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// getTargetData - Return a pointer to the current TargetData object, or 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// null if no TargetData object is available. 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const TargetData *getTargetData() const { return TD; } 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// getTypeStoreSize - Return the TargetData store size for the given type, 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// if known, or a conservative value otherwise. 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64_t getTypeStoreSize(const Type *Ty); 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project //===--------------------------------------------------------------------===// 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Alias Queries... 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Location - A description of a memory location. 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project struct Location { 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Ptr - The address of the start of the location. 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Value *Ptr; 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Size - The maximum size of the location, or UnknownSize if the size is 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// not known. Note that an unknown size does not mean the pointer aliases 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// the entire virtual address space, because there are restrictions on 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// stepping out of one object and into another. 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// See http://llvm.org/docs/LangRef.html#pointeraliasing 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64_t Size; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// TBAATag - The metadata node which describes the TBAA type of 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// the location, or null if there is no known unique tag. 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const MDNode *TBAATag; 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project explicit Location(const Value *P = 0, 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64_t S = UnknownSize, 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const MDNode *N = 0) 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : Ptr(P), Size(S), TBAATag(N) {} 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Location getWithNewPtr(const Value *NewPtr) const { 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Location Copy(*this); 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Copy.Ptr = NewPtr; 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Copy; 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Location getWithoutTBAATag() const { 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Location Copy(*this); 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Copy.TBAATag = 0; 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Copy; 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Alias analysis result - Either we know for sure that it does not alias, we 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// know for sure it must alias, or we don't know anything: The two pointers 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// _might_ alias. This enum is designed so you can do things like: 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// if (AA.alias(P1, P2)) { ... } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// to check to see if two pointers might alias. 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// See docs/AliasAnalysis.html for more information on the specific meanings 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// of these values. 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// alias - The main low level interface to the alias analysis implementation. 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Returns an AliasResult indicating whether the two pointers are aliased to 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// each other. This is the interface that must be implemented by specific 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// alias analysis implementations. 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual AliasResult alias(const Location &LocA, const Location &LocB); 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// alias - A convenience wrapper. 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AliasResult alias(const Value *V1, uint64_t V1Size, 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Value *V2, uint64_t V2Size) { 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return alias(Location(V1, V1Size), Location(V2, V2Size)); 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// alias - A convenience wrapper. 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AliasResult alias(const Value *V1, const Value *V2) { 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return alias(V1, UnknownSize, V2, UnknownSize); 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// isNoAlias - A trivial helper function to check to see if the specified 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// pointers are no-alias. 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool isNoAlias(const Location &LocA, const Location &LocB) { 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return alias(LocA, LocB) == NoAlias; 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// isNoAlias - A convenience wrapper. 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool isNoAlias(const Value *V1, uint64_t V1Size, 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Value *V2, uint64_t V2Size) { 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return isNoAlias(Location(V1, V1Size), Location(V2, V2Size)); 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// pointsToConstantMemory - If the specified memory location is 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// known to be constant, return true. If OrLocal is true and the 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// specified memory location is known to be "local" (derived from 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// an alloca), return true. Otherwise return false. 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool pointsToConstantMemory(const Location &Loc, 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool OrLocal = false); 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 16473018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers /// pointsToConstantMemory - A convenient wrapper. 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return pointsToConstantMemory(Location(P), OrLocal); 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project //===--------------------------------------------------------------------===// 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Simple mod/ref information... 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// ModRefResult - Represent the result of a mod/ref query. Mod and Ref are 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// bits which may be or'd together. 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// These values define additional bits used to define the 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// ModRefBehavior values. 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum { Nowhere = 0, ArgumentPointees = 4, Anywhere = 8 | ArgumentPointees }; 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// ModRefBehavior - Summary of how a function affects memory in the program. 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// Loads from constant globals are not considered memory accesses for this 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// interface. Also, functions may freely modify stack space local to their 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// invocation without having to report it through these interfaces. 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enum ModRefBehavior { 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// DoesNotAccessMemory - This function does not perform any non-local loads 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// or stores to memory. 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the GCC 'const' attribute. 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the LLVM IR 'readnone' attribute. 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the IntrNoMem LLVM intrinsic flag. 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DoesNotAccessMemory = Nowhere | NoModRef, 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// OnlyReadsArgumentPointees - The only memory references in this function 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// (if it has any) are non-volatile loads from objects pointed to by its 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// pointer-typed arguments, with arbitrary offsets. 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OnlyReadsArgumentPointees = ArgumentPointees | Ref, 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// OnlyAccessesArgumentPointees - The only memory references in this 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// function (if it has any) are non-volatile loads and stores from objects 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// pointed to by its pointer-typed arguments, with arbitrary offsets. 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag. 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OnlyAccessesArgumentPointees = ArgumentPointees | ModRef, 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// OnlyReadsMemory - This function does not perform any non-local stores or 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// volatile loads, but may read from any memory location. 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the GCC 'pure' attribute. 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the LLVM IR 'readonly' attribute. 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// This property corresponds to the IntrReadMem LLVM intrinsic flag. 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OnlyReadsMemory = Anywhere | Ref, 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// UnknownModRefBehavior - This indicates that the function could not be 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// classified into one of the behaviors above. 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project UnknownModRefBehavior = Anywhere | ModRef 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// getModRefBehavior - Return the behavior when calling the given call site. 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS); 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// getModRefBehavior - Return the behavior when calling the given function. 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// For use when the call site is not known. 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ModRefBehavior getModRefBehavior(const Function *F); 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// doesNotAccessMemory - If the specified call is known to never read or 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// write memory, return true. If the call only reads from known-constant 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// memory, it is also legal to return true. Calls that unwind the stack 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project /// are legal for this predicate. 233 /// 234 /// Many optimizations (such as CSE and LICM) can be performed on such calls 235 /// without worrying about aliasing properties, and many calls have this 236 /// property (e.g. calls to 'sin' and 'cos'). 237 /// 238 /// This property corresponds to the GCC 'const' attribute. 239 /// 240 bool doesNotAccessMemory(ImmutableCallSite CS) { 241 return getModRefBehavior(CS) == DoesNotAccessMemory; 242 } 243 244 /// doesNotAccessMemory - If the specified function is known to never read or 245 /// write memory, return true. For use when the call site is not known. 246 /// 247 bool doesNotAccessMemory(const Function *F) { 248 return getModRefBehavior(F) == DoesNotAccessMemory; 249 } 250 251 /// onlyReadsMemory - If the specified call is known to only read from 252 /// non-volatile memory (or not access memory at all), return true. Calls 253 /// that unwind the stack are legal for this predicate. 254 /// 255 /// This property allows many common optimizations to be performed in the 256 /// absence of interfering store instructions, such as CSE of strlen calls. 257 /// 258 /// This property corresponds to the GCC 'pure' attribute. 259 /// 260 bool onlyReadsMemory(ImmutableCallSite CS) { 261 return onlyReadsMemory(getModRefBehavior(CS)); 262 } 263 264 /// onlyReadsMemory - If the specified function is known to only read from 265 /// non-volatile memory (or not access memory at all), return true. For use 266 /// when the call site is not known. 267 /// 268 bool onlyReadsMemory(const Function *F) { 269 return onlyReadsMemory(getModRefBehavior(F)); 270 } 271 272 /// onlyReadsMemory - Return true if functions with the specified behavior are 273 /// known to only read from non-volatile memory (or not access memory at all). 274 /// 275 static bool onlyReadsMemory(ModRefBehavior MRB) { 276 return !(MRB & Mod); 277 } 278 279 /// onlyAccessesArgPointees - Return true if functions with the specified 280 /// behavior are known to read and write at most from objects pointed to by 281 /// their pointer-typed arguments (with arbitrary offsets). 282 /// 283 static bool onlyAccessesArgPointees(ModRefBehavior MRB) { 284 return !(MRB & Anywhere & ~ArgumentPointees); 285 } 286 287 /// doesAccessArgPointees - Return true if functions with the specified 288 /// behavior are known to potentially read or write from objects pointed 289 /// to be their pointer-typed arguments (with arbitrary offsets). 290 /// 291 static bool doesAccessArgPointees(ModRefBehavior MRB) { 292 return (MRB & ModRef) && (MRB & ArgumentPointees); 293 } 294 295 /// getModRefInfo - Return information about whether or not an instruction may 296 /// read or write the specified memory location. An instruction 297 /// that doesn't read or write memory may be trivially LICM'd for example. 298 ModRefResult getModRefInfo(const Instruction *I, 299 const Location &Loc) { 300 switch (I->getOpcode()) { 301 case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); 302 case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); 303 case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); 304 case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); 305 case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); 306 default: return NoModRef; 307 } 308 } 309 310 /// getModRefInfo - A convenience wrapper. 311 ModRefResult getModRefInfo(const Instruction *I, 312 const Value *P, uint64_t Size) { 313 return getModRefInfo(I, Location(P, Size)); 314 } 315 316 /// getModRefInfo (for call sites) - Return whether information about whether 317 /// a particular call site modifies or reads the specified memory location. 318 virtual ModRefResult getModRefInfo(ImmutableCallSite CS, 319 const Location &Loc); 320 321 /// getModRefInfo (for call sites) - A convenience wrapper. 322 ModRefResult getModRefInfo(ImmutableCallSite CS, 323 const Value *P, uint64_t Size) { 324 return getModRefInfo(CS, Location(P, Size)); 325 } 326 327 /// getModRefInfo (for calls) - Return whether information about whether 328 /// a particular call modifies or reads the specified memory location. 329 ModRefResult getModRefInfo(const CallInst *C, const Location &Loc) { 330 return getModRefInfo(ImmutableCallSite(C), Loc); 331 } 332 333 /// getModRefInfo (for calls) - A convenience wrapper. 334 ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { 335 return getModRefInfo(C, Location(P, Size)); 336 } 337 338 /// getModRefInfo (for invokes) - Return whether information about whether 339 /// a particular invoke modifies or reads the specified memory location. 340 ModRefResult getModRefInfo(const InvokeInst *I, 341 const Location &Loc) { 342 return getModRefInfo(ImmutableCallSite(I), Loc); 343 } 344 345 /// getModRefInfo (for invokes) - A convenience wrapper. 346 ModRefResult getModRefInfo(const InvokeInst *I, 347 const Value *P, uint64_t Size) { 348 return getModRefInfo(I, Location(P, Size)); 349 } 350 351 /// getModRefInfo (for loads) - Return whether information about whether 352 /// a particular load modifies or reads the specified memory location. 353 ModRefResult getModRefInfo(const LoadInst *L, const Location &Loc); 354 355 /// getModRefInfo (for loads) - A convenience wrapper. 356 ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { 357 return getModRefInfo(L, Location(P, Size)); 358 } 359 360 /// getModRefInfo (for stores) - Return whether information about whether 361 /// a particular store modifies or reads the specified memory location. 362 ModRefResult getModRefInfo(const StoreInst *S, const Location &Loc); 363 364 /// getModRefInfo (for stores) - A convenience wrapper. 365 ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size) { 366 return getModRefInfo(S, Location(P, Size)); 367 } 368 369 /// getModRefInfo (for va_args) - Return whether information about whether 370 /// a particular va_arg modifies or reads the specified memory location. 371 ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); 372 373 /// getModRefInfo (for va_args) - A convenience wrapper. 374 ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size) { 375 return getModRefInfo(I, Location(P, Size)); 376 } 377 378 /// getModRefInfo - Return information about whether two call sites may refer 379 /// to the same set of memory locations. See 380 /// http://llvm.org/docs/AliasAnalysis.html#ModRefInfo 381 /// for details. 382 virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, 383 ImmutableCallSite CS2); 384 385 //===--------------------------------------------------------------------===// 386 /// Higher level methods for querying mod/ref information. 387 /// 388 389 /// canBasicBlockModify - Return true if it is possible for execution of the 390 /// specified basic block to modify the value pointed to by Ptr. 391 bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); 392 393 /// canBasicBlockModify - A convenience wrapper. 394 bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){ 395 return canBasicBlockModify(BB, Location(P, Size)); 396 } 397 398 /// canInstructionRangeModify - Return true if it is possible for the 399 /// execution of the specified instructions to modify the value pointed to by 400 /// Ptr. The instructions to consider are all of the instructions in the 401 /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. 402 bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 403 const Location &Loc); 404 405 /// canInstructionRangeModify - A convenience wrapper. 406 bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, 407 const Value *Ptr, uint64_t Size) { 408 return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); 409 } 410 411 //===--------------------------------------------------------------------===// 412 /// Methods that clients should call when they transform the program to allow 413 /// alias analyses to update their internal data structures. Note that these 414 /// methods may be called on any instruction, regardless of whether or not 415 /// they have pointer-analysis implications. 416 /// 417 418 /// deleteValue - This method should be called whenever an LLVM Value is 419 /// deleted from the program, for example when an instruction is found to be 420 /// redundant and is eliminated. 421 /// 422 virtual void deleteValue(Value *V); 423 424 /// copyValue - This method should be used whenever a preexisting value in the 425 /// program is copied or cloned, introducing a new value. Note that analysis 426 /// implementations should tolerate clients that use this method to introduce 427 /// the same value multiple times: if the analysis already knows about a 428 /// value, it should ignore the request. 429 /// 430 virtual void copyValue(Value *From, Value *To); 431 432 /// replaceWithNewValue - This method is the obvious combination of the two 433 /// above, and it provided as a helper to simplify client code. 434 /// 435 void replaceWithNewValue(Value *Old, Value *New) { 436 copyValue(Old, New); 437 deleteValue(Old); 438 } 439}; 440 441/// isNoAliasCall - Return true if this pointer is returned by a noalias 442/// function. 443bool isNoAliasCall(const Value *V); 444 445/// isIdentifiedObject - Return true if this pointer refers to a distinct and 446/// identifiable object. This returns true for: 447/// Global Variables and Functions (but not Global Aliases) 448/// Allocas and Mallocs 449/// ByVal and NoAlias Arguments 450/// NoAlias returns 451/// 452bool isIdentifiedObject(const Value *V); 453 454} // End llvm namespace 455 456#endif 457