LLVM  6.0.0svn
Classes | Namespaces | Typedefs | Functions | Variables
AliasAnalysisSummary.h File Reference

This file defines various utility types and functions useful to summary-based alias analysis. More...

#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/CallSite.h"
#include <bitset>
Include dependency graph for AliasAnalysisSummary.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  llvm::cflaa::InterfaceValue
 We use InterfaceValue to describe parameters/return value, as well as potential memory locations that are pointed to by parameters/return value, of a function. More...
 
struct  llvm::cflaa::ExternalRelation
 We use ExternalRelation to describe an externally visible aliasing relations between parameters/return value of a function. More...
 
struct  llvm::cflaa::ExternalAttribute
 We use ExternalAttribute to describe an externally visible AliasAttrs for parameters/return value. More...
 
struct  llvm::cflaa::AliasSummary
 AliasSummary is just a collection of ExternalRelation and ExternalAttribute. More...
 
struct  llvm::cflaa::InstantiatedValue
 This is the result of instantiating InterfaceValue at a particular callsite. More...
 
struct  llvm::cflaa::InstantiatedRelation
 This is the result of instantiating ExternalRelation at a particular callsite. More...
 
struct  llvm::cflaa::InstantiatedAttr
 This is the result of instantiating ExternalAttribute at a particular callsite. More...
 
struct  llvm::DenseMapInfo< cflaa::InstantiatedValue >
 

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 
 llvm::cflaa
 

Typedefs

typedef std::bitset< NumAliasAttrs > llvm::cflaa::AliasAttrs
 These are attributes that an alias analysis can use to mark certain special properties of a given pointer. More...
 

Functions

AliasAttrs llvm::cflaa::getAttrNone ()
 Attr represent whether the said pointer comes from an unknown source (such as opaque memory or an integer cast). More...
 
AliasAttrs llvm::cflaa::getAttrUnknown ()
 AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such as opaque memory or an integer cast). More...
 
bool llvm::cflaa::hasUnknownAttr (AliasAttrs Attr)
 
AliasAttrs llvm::cflaa::getAttrCaller ()
 AttrCaller represent whether the said pointer comes from a source not known to the current function but known to the caller. More...
 
bool llvm::cflaa::hasCallerAttr (AliasAttrs Attr)
 
bool llvm::cflaa::hasUnknownOrCallerAttr (AliasAttrs Attr)
 
AliasAttrs llvm::cflaa::getAttrEscaped ()
 AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown world (e.g. More...
 
bool llvm::cflaa::hasEscapedAttr (AliasAttrs Attr)
 
AliasAttrs llvm::cflaa::getGlobalOrArgAttrFromValue (const Value &)
 AttrGlobal represent whether the said pointer is a global value. More...
 
bool llvm::cflaa::isGlobalOrArgAttr (AliasAttrs Attr)
 
AliasAttrs llvm::cflaa::getExternallyVisibleAttrs (AliasAttrs)
 Given an AliasAttrs, return a new AliasAttrs that only contains attributes meaningful to the caller. More...
 
bool llvm::cflaa::operator== (InterfaceValue LHS, InterfaceValue RHS)
 
bool llvm::cflaa::operator!= (InterfaceValue LHS, InterfaceValue RHS)
 
bool llvm::cflaa::operator< (InterfaceValue LHS, InterfaceValue RHS)
 
bool llvm::cflaa::operator> (InterfaceValue LHS, InterfaceValue RHS)
 
bool llvm::cflaa::operator<= (InterfaceValue LHS, InterfaceValue RHS)
 
bool llvm::cflaa::operator>= (InterfaceValue LHS, InterfaceValue RHS)
 
int64_t llvm::cflaa::addOffset (int64_t LHS, int64_t RHS)
 
bool llvm::cflaa::operator== (ExternalRelation LHS, ExternalRelation RHS)
 
bool llvm::cflaa::operator!= (ExternalRelation LHS, ExternalRelation RHS)
 
bool llvm::cflaa::operator< (ExternalRelation LHS, ExternalRelation RHS)
 
bool llvm::cflaa::operator> (ExternalRelation LHS, ExternalRelation RHS)
 
bool llvm::cflaa::operator<= (ExternalRelation LHS, ExternalRelation RHS)
 
bool llvm::cflaa::operator>= (ExternalRelation LHS, ExternalRelation RHS)
 
Optional< InstantiatedValue > llvm::cflaa::instantiateInterfaceValue (InterfaceValue IValue, CallSite CS)
 
bool llvm::cflaa::operator== (InstantiatedValue LHS, InstantiatedValue RHS)
 
bool llvm::cflaa::operator!= (InstantiatedValue LHS, InstantiatedValue RHS)
 
bool llvm::cflaa::operator< (InstantiatedValue LHS, InstantiatedValue RHS)
 
bool llvm::cflaa::operator> (InstantiatedValue LHS, InstantiatedValue RHS)
 
bool llvm::cflaa::operator<= (InstantiatedValue LHS, InstantiatedValue RHS)
 
bool llvm::cflaa::operator>= (InstantiatedValue LHS, InstantiatedValue RHS)
 
Optional< InstantiatedRelation > llvm::cflaa::instantiateExternalRelation (ExternalRelation ERelation, CallSite CS)
 
Optional< InstantiatedAttr > llvm::cflaa::instantiateExternalAttribute (ExternalAttribute EAttr, CallSite CS)
 

Variables

static const unsigned llvm::cflaa::NumAliasAttrs = 32
 The number of attributes that AliasAttr should contain. More...
 
static const unsigned llvm::cflaa::MaxSupportedArgsInSummary = 50
 The maximum number of arguments we can put into a summary. More...
 
static const int64_t llvm::cflaa::UnknownOffset = INT64_MAX
 

Detailed Description

This file defines various utility types and functions useful to summary-based alias analysis.

Summary-based analysis, also known as bottom-up analysis, is a style of interprocedrual static analysis that tries to analyze the callees before the callers get analyzed. The key idea of summary-based analysis is to first process each function indepedently, outline its behavior in a condensed summary, and then instantiate the summary at the callsite when the said function is called elsewhere. This is often in contrast to another style called top-down analysis, in which callers are always analyzed first before the callees.

In a summary-based analysis, functions must be examined independently and out-of-context. We have no information on the state of the memory, the arguments, the global values, and anything else external to the function. To carry out the analysis conservative assumptions have to be made about those external states. In exchange for the potential loss of precision, the summary we obtain this way is highly reusable, which makes the analysis easier to scale to large programs even if carried out context-sensitively.

Currently, all CFL-based alias analyses adopt the summary-based approach and therefore heavily rely on this header.

Definition in file AliasAnalysisSummary.h.