1//=====- CFLSummary.h - Abstract stratified sets implementation. --------=====// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9/// \file 10/// This file defines various utility types and functions useful to 11/// summary-based alias analysis. 12/// 13/// Summary-based analysis, also known as bottom-up analysis, is a style of 14/// interprocedrual static analysis that tries to analyze the callees before the 15/// callers get analyzed. The key idea of summary-based analysis is to first 16/// process each function indepedently, outline its behavior in a condensed 17/// summary, and then instantiate the summary at the callsite when the said 18/// function is called elsewhere. This is often in contrast to another style 19/// called top-down analysis, in which callers are always analyzed first before 20/// the callees. 21/// 22/// In a summary-based analysis, functions must be examined independently and 23/// out-of-context. We have no information on the state of the memory, the 24/// arguments, the global values, and anything else external to the function. To 25/// carry out the analysis conservative assumptions have to be made about those 26/// external states. In exchange for the potential loss of precision, the 27/// summary we obtain this way is highly reusable, which makes the analysis 28/// easier to scale to large programs even if carried out context-sensitively. 29/// 30/// Currently, all CFL-based alias analyses adopt the summary-based approach 31/// and therefore heavily rely on this header. 32/// 33//===----------------------------------------------------------------------===// 34 35#ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H 36#define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H 37 38#include "llvm/ADT/DenseMapInfo.h" 39#include "llvm/ADT/Optional.h" 40#include "llvm/ADT/SmallVector.h" 41#include "llvm/IR/CallSite.h" 42#include <bitset> 43 44namespace llvm { 45namespace cflaa { 46 47//===----------------------------------------------------------------------===// 48// AliasAttr related stuffs 49//===----------------------------------------------------------------------===// 50 51/// The number of attributes that AliasAttr should contain. Attributes are 52/// described below, and 32 was an arbitrary choice because it fits nicely in 32 53/// bits (because we use a bitset for AliasAttr). 54static const unsigned NumAliasAttrs = 32; 55 56/// These are attributes that an alias analysis can use to mark certain special 57/// properties of a given pointer. Refer to the related functions below to see 58/// what kinds of attributes are currently defined. 59typedef std::bitset<NumAliasAttrs> AliasAttrs; 60 61/// Attr represent whether the said pointer comes from an unknown source 62/// (such as opaque memory or an integer cast). 63AliasAttrs getAttrNone(); 64 65/// AttrUnknown represent whether the said pointer comes from a source not known 66/// to alias analyses (such as opaque memory or an integer cast). 67AliasAttrs getAttrUnknown(); 68bool hasUnknownAttr(AliasAttrs); 69 70/// AttrCaller represent whether the said pointer comes from a source not known 71/// to the current function but known to the caller. Values pointed to by the 72/// arguments of the current function have this attribute set 73AliasAttrs getAttrCaller(); 74bool hasCallerAttr(AliasAttrs); 75bool hasUnknownOrCallerAttr(AliasAttrs); 76 77/// AttrEscaped represent whether the said pointer comes from a known source but 78/// escapes to the unknown world (e.g. casted to an integer, or passed as an 79/// argument to opaque function). Unlike non-escaped pointers, escaped ones may 80/// alias pointers coming from unknown sources. 81AliasAttrs getAttrEscaped(); 82bool hasEscapedAttr(AliasAttrs); 83 84/// AttrGlobal represent whether the said pointer is a global value. 85/// AttrArg represent whether the said pointer is an argument, and if so, what 86/// index the argument has. 87AliasAttrs getGlobalOrArgAttrFromValue(const Value &); 88bool isGlobalOrArgAttr(AliasAttrs); 89 90/// Given an AliasAttrs, return a new AliasAttrs that only contains attributes 91/// meaningful to the caller. This function is primarily used for 92/// interprocedural analysis 93/// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal, 94/// and AttrEscaped 95AliasAttrs getExternallyVisibleAttrs(AliasAttrs); 96 97//===----------------------------------------------------------------------===// 98// Function summary related stuffs 99//===----------------------------------------------------------------------===// 100 101/// The maximum number of arguments we can put into a summary. 102LLVM_CONSTEXPR static unsigned MaxSupportedArgsInSummary = 50; 103 104/// We use InterfaceValue to describe parameters/return value, as well as 105/// potential memory locations that are pointed to by parameters/return value, 106/// of a function. 107/// Index is an integer which represents a single parameter or a return value. 108/// When the index is 0, it refers to the return value. Non-zero index i refers 109/// to the i-th parameter. 110/// DerefLevel indicates the number of dereferences one must perform on the 111/// parameter/return value to get this InterfaceValue. 112struct InterfaceValue { 113 unsigned Index; 114 unsigned DerefLevel; 115}; 116 117inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) { 118 return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; 119} 120inline bool operator!=(InterfaceValue lhs, InterfaceValue rhs) { 121 return !(lhs == rhs); 122} 123 124/// We use ExternalRelation to describe an externally visible aliasing relations 125/// between parameters/return value of a function. 126struct ExternalRelation { 127 InterfaceValue From, To; 128}; 129 130/// We use ExternalAttribute to describe an externally visible AliasAttrs 131/// for parameters/return value. 132struct ExternalAttribute { 133 InterfaceValue IValue; 134 AliasAttrs Attr; 135}; 136 137/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute 138struct AliasSummary { 139 // RetParamRelations is a collection of ExternalRelations. 140 SmallVector<ExternalRelation, 8> RetParamRelations; 141 142 // RetParamAttributes is a collection of ExternalAttributes. 143 SmallVector<ExternalAttribute, 8> RetParamAttributes; 144}; 145 146/// This is the result of instantiating InterfaceValue at a particular callsite 147struct InstantiatedValue { 148 Value *Val; 149 unsigned DerefLevel; 150}; 151Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite); 152 153/// This is the result of instantiating ExternalRelation at a particular 154/// callsite 155struct InstantiatedRelation { 156 InstantiatedValue From, To; 157}; 158Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation, 159 CallSite); 160 161/// This is the result of instantiating ExternalAttribute at a particular 162/// callsite 163struct InstantiatedAttr { 164 InstantiatedValue IValue; 165 AliasAttrs Attr; 166}; 167Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute, 168 CallSite); 169} 170 171template <> struct DenseMapInfo<cflaa::InstantiatedValue> { 172 static inline cflaa::InstantiatedValue getEmptyKey() { 173 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(), 174 DenseMapInfo<unsigned>::getEmptyKey()}; 175 } 176 static inline cflaa::InstantiatedValue getTombstoneKey() { 177 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(), 178 DenseMapInfo<unsigned>::getTombstoneKey()}; 179 } 180 static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { 181 return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue( 182 std::make_pair(IV.Val, IV.DerefLevel)); 183 } 184 static bool isEqual(const cflaa::InstantiatedValue &LHS, 185 const cflaa::InstantiatedValue &RHS) { 186 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; 187 } 188}; 189} 190 191#endif 192