1//=====- CFLSummary.h - Abstract stratified sets implementation. --------=====// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8/// \file 9/// This file defines various utility types and functions useful to 10/// summary-based alias analysis. 11/// 12/// Summary-based analysis, also known as bottom-up analysis, is a style of 13/// interprocedrual static analysis that tries to analyze the callees before the 14/// callers get analyzed. The key idea of summary-based analysis is to first 15/// process each function independently, outline its behavior in a condensed 16/// summary, and then instantiate the summary at the callsite when the said 17/// function is called elsewhere. This is often in contrast to another style 18/// called top-down analysis, in which callers are always analyzed first before 19/// the callees. 20/// 21/// In a summary-based analysis, functions must be examined independently and 22/// out-of-context. We have no information on the state of the memory, the 23/// arguments, the global values, and anything else external to the function. To 24/// carry out the analysis conservative assumptions have to be made about those 25/// external states. In exchange for the potential loss of precision, the 26/// summary we obtain this way is highly reusable, which makes the analysis 27/// easier to scale to large programs even if carried out context-sensitively. 28/// 29/// Currently, all CFL-based alias analyses adopt the summary-based approach 30/// and therefore heavily rely on this header. 31/// 32//===----------------------------------------------------------------------===// 33 34#ifndef LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H 35#define LLVM_ANALYSIS_ALIASANALYSISSUMMARY_H 36 37#include "llvm/ADT/DenseMapInfo.h" 38#include "llvm/ADT/Optional.h" 39#include "llvm/ADT/SmallVector.h" 40#include <bitset> 41 42namespace llvm { 43 44class CallBase; 45class Value; 46 47namespace cflaa { 48 49//===----------------------------------------------------------------------===// 50// AliasAttr related stuffs 51//===----------------------------------------------------------------------===// 52 53/// The number of attributes that AliasAttr should contain. Attributes are 54/// described below, and 32 was an arbitrary choice because it fits nicely in 32 55/// bits (because we use a bitset for AliasAttr). 56static const unsigned NumAliasAttrs = 32; 57 58/// These are attributes that an alias analysis can use to mark certain special 59/// properties of a given pointer. Refer to the related functions below to see 60/// what kinds of attributes are currently defined. 61typedef std::bitset<NumAliasAttrs> AliasAttrs; 62 63/// Attr represent whether the said pointer comes from an unknown source 64/// (such as opaque memory or an integer cast). 65AliasAttrs getAttrNone(); 66 67/// AttrUnknown represent whether the said pointer comes from a source not known 68/// to alias analyses (such as opaque memory or an integer cast). 69AliasAttrs getAttrUnknown(); 70bool hasUnknownAttr(AliasAttrs); 71 72/// AttrCaller represent whether the said pointer comes from a source not known 73/// to the current function but known to the caller. Values pointed to by the 74/// arguments of the current function have this attribute set 75AliasAttrs getAttrCaller(); 76bool hasCallerAttr(AliasAttrs); 77bool hasUnknownOrCallerAttr(AliasAttrs); 78 79/// AttrEscaped represent whether the said pointer comes from a known source but 80/// escapes to the unknown world (e.g. casted to an integer, or passed as an 81/// argument to opaque function). Unlike non-escaped pointers, escaped ones may 82/// alias pointers coming from unknown sources. 83AliasAttrs getAttrEscaped(); 84bool hasEscapedAttr(AliasAttrs); 85 86/// AttrGlobal represent whether the said pointer is a global value. 87/// AttrArg represent whether the said pointer is an argument, and if so, what 88/// index the argument has. 89AliasAttrs getGlobalOrArgAttrFromValue(const Value &); 90bool isGlobalOrArgAttr(AliasAttrs); 91 92/// Given an AliasAttrs, return a new AliasAttrs that only contains attributes 93/// meaningful to the caller. This function is primarily used for 94/// interprocedural analysis 95/// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal, 96/// and AttrEscaped 97AliasAttrs getExternallyVisibleAttrs(AliasAttrs); 98 99//===----------------------------------------------------------------------===// 100// Function summary related stuffs 101//===----------------------------------------------------------------------===// 102 103/// The maximum number of arguments we can put into a summary. 104static const unsigned MaxSupportedArgsInSummary = 50; 105 106/// We use InterfaceValue to describe parameters/return value, as well as 107/// potential memory locations that are pointed to by parameters/return value, 108/// of a function. 109/// Index is an integer which represents a single parameter or a return value. 110/// When the index is 0, it refers to the return value. Non-zero index i refers 111/// to the i-th parameter. 112/// DerefLevel indicates the number of dereferences one must perform on the 113/// parameter/return value to get this InterfaceValue. 114struct InterfaceValue { 115 unsigned Index; 116 unsigned DerefLevel; 117}; 118 119inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) { 120 return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel; 121} 122inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) { 123 return !(LHS == RHS); 124} 125inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) { 126 return LHS.Index < RHS.Index || 127 (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel); 128} 129inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) { 130 return RHS < LHS; 131} 132inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) { 133 return !(RHS < LHS); 134} 135inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) { 136 return !(LHS < RHS); 137} 138 139// We use UnknownOffset to represent pointer offsets that cannot be determined 140// at compile time. Note that MemoryLocation::UnknownSize cannot be used here 141// because we require a signed value. 142static const int64_t UnknownOffset = INT64_MAX; 143 144inline int64_t addOffset(int64_t LHS, int64_t RHS) { 145 if (LHS == UnknownOffset || RHS == UnknownOffset) 146 return UnknownOffset; 147 // FIXME: Do we need to guard against integer overflow here? 148 return LHS + RHS; 149} 150 151/// We use ExternalRelation to describe an externally visible aliasing relations 152/// between parameters/return value of a function. 153struct ExternalRelation { 154 InterfaceValue From, To; 155 int64_t Offset; 156}; 157 158inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) { 159 return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset; 160} 161inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) { 162 return !(LHS == RHS); 163} 164inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) { 165 if (LHS.From < RHS.From) 166 return true; 167 if (LHS.From > RHS.From) 168 return false; 169 if (LHS.To < RHS.To) 170 return true; 171 if (LHS.To > RHS.To) 172 return false; 173 return LHS.Offset < RHS.Offset; 174} 175inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) { 176 return RHS < LHS; 177} 178inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) { 179 return !(RHS < LHS); 180} 181inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) { 182 return !(LHS < RHS); 183} 184 185/// We use ExternalAttribute to describe an externally visible AliasAttrs 186/// for parameters/return value. 187struct ExternalAttribute { 188 InterfaceValue IValue; 189 AliasAttrs Attr; 190}; 191 192/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute 193struct AliasSummary { 194 // RetParamRelations is a collection of ExternalRelations. 195 SmallVector<ExternalRelation, 8> RetParamRelations; 196 197 // RetParamAttributes is a collection of ExternalAttributes. 198 SmallVector<ExternalAttribute, 8> RetParamAttributes; 199}; 200 201/// This is the result of instantiating InterfaceValue at a particular call 202struct InstantiatedValue { 203 Value *Val; 204 unsigned DerefLevel; 205}; 206Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue, 207 CallBase &Call); 208 209inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) { 210 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; 211} 212inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) { 213 return !(LHS == RHS); 214} 215inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) { 216 return std::less<Value *>()(LHS.Val, RHS.Val) || 217 (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel); 218} 219inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) { 220 return RHS < LHS; 221} 222inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) { 223 return !(RHS < LHS); 224} 225inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) { 226 return !(LHS < RHS); 227} 228 229/// This is the result of instantiating ExternalRelation at a particular 230/// callsite 231struct InstantiatedRelation { 232 InstantiatedValue From, To; 233 int64_t Offset; 234}; 235Optional<InstantiatedRelation> 236instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call); 237 238/// This is the result of instantiating ExternalAttribute at a particular 239/// callsite 240struct InstantiatedAttr { 241 InstantiatedValue IValue; 242 AliasAttrs Attr; 243}; 244Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr, 245 CallBase &Call); 246} 247 248template <> struct DenseMapInfo<cflaa::InstantiatedValue> { 249 static inline cflaa::InstantiatedValue getEmptyKey() { 250 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(), 251 DenseMapInfo<unsigned>::getEmptyKey()}; 252 } 253 static inline cflaa::InstantiatedValue getTombstoneKey() { 254 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(), 255 DenseMapInfo<unsigned>::getTombstoneKey()}; 256 } 257 static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { 258 return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue( 259 std::make_pair(IV.Val, IV.DerefLevel)); 260 } 261 static bool isEqual(const cflaa::InstantiatedValue &LHS, 262 const cflaa::InstantiatedValue &RHS) { 263 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; 264 } 265}; 266} 267 268#endif 269