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 "llvm/IR/InstrTypes.h" 41#include <bitset> 42 43namespace llvm { 44namespace cflaa { 45 46//===----------------------------------------------------------------------===// 47// AliasAttr related stuffs 48//===----------------------------------------------------------------------===// 49 50/// The number of attributes that AliasAttr should contain. Attributes are 51/// described below, and 32 was an arbitrary choice because it fits nicely in 32 52/// bits (because we use a bitset for AliasAttr). 53static const unsigned NumAliasAttrs = 32; 54 55/// These are attributes that an alias analysis can use to mark certain special 56/// properties of a given pointer. Refer to the related functions below to see 57/// what kinds of attributes are currently defined. 58typedef std::bitset<NumAliasAttrs> AliasAttrs; 59 60/// Attr represent whether the said pointer comes from an unknown source 61/// (such as opaque memory or an integer cast). 62AliasAttrs getAttrNone(); 63 64/// AttrUnknown represent whether the said pointer comes from a source not known 65/// to alias analyses (such as opaque memory or an integer cast). 66AliasAttrs getAttrUnknown(); 67bool hasUnknownAttr(AliasAttrs); 68 69/// AttrCaller represent whether the said pointer comes from a source not known 70/// to the current function but known to the caller. Values pointed to by the 71/// arguments of the current function have this attribute set 72AliasAttrs getAttrCaller(); 73bool hasCallerAttr(AliasAttrs); 74bool hasUnknownOrCallerAttr(AliasAttrs); 75 76/// AttrEscaped represent whether the said pointer comes from a known source but 77/// escapes to the unknown world (e.g. casted to an integer, or passed as an 78/// argument to opaque function). Unlike non-escaped pointers, escaped ones may 79/// alias pointers coming from unknown sources. 80AliasAttrs getAttrEscaped(); 81bool hasEscapedAttr(AliasAttrs); 82 83/// AttrGlobal represent whether the said pointer is a global value. 84/// AttrArg represent whether the said pointer is an argument, and if so, what 85/// index the argument has. 86AliasAttrs getGlobalOrArgAttrFromValue(const Value &); 87bool isGlobalOrArgAttr(AliasAttrs); 88 89/// Given an AliasAttrs, return a new AliasAttrs that only contains attributes 90/// meaningful to the caller. This function is primarily used for 91/// interprocedural analysis 92/// Currently, externally visible AliasAttrs include AttrUnknown, AttrGlobal, 93/// and AttrEscaped 94AliasAttrs getExternallyVisibleAttrs(AliasAttrs); 95 96//===----------------------------------------------------------------------===// 97// Function summary related stuffs 98//===----------------------------------------------------------------------===// 99 100/// The maximum number of arguments we can put into a summary. 101static const unsigned MaxSupportedArgsInSummary = 50; 102 103/// We use InterfaceValue to describe parameters/return value, as well as 104/// potential memory locations that are pointed to by parameters/return value, 105/// of a function. 106/// Index is an integer which represents a single parameter or a return value. 107/// When the index is 0, it refers to the return value. Non-zero index i refers 108/// to the i-th parameter. 109/// DerefLevel indicates the number of dereferences one must perform on the 110/// parameter/return value to get this InterfaceValue. 111struct InterfaceValue { 112 unsigned Index; 113 unsigned DerefLevel; 114}; 115 116inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) { 117 return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel; 118} 119inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) { 120 return !(LHS == RHS); 121} 122inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) { 123 return LHS.Index < RHS.Index || 124 (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel); 125} 126inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) { 127 return RHS < LHS; 128} 129inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) { 130 return !(RHS < LHS); 131} 132inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) { 133 return !(LHS < RHS); 134} 135 136// We use UnknownOffset to represent pointer offsets that cannot be determined 137// at compile time. Note that MemoryLocation::UnknownSize cannot be used here 138// because we require a signed value. 139static const int64_t UnknownOffset = INT64_MAX; 140 141inline int64_t addOffset(int64_t LHS, int64_t RHS) { 142 if (LHS == UnknownOffset || RHS == UnknownOffset) 143 return UnknownOffset; 144 // FIXME: Do we need to guard against integer overflow here? 145 return LHS + RHS; 146} 147 148/// We use ExternalRelation to describe an externally visible aliasing relations 149/// between parameters/return value of a function. 150struct ExternalRelation { 151 InterfaceValue From, To; 152 int64_t Offset; 153}; 154 155inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) { 156 return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset; 157} 158inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) { 159 return !(LHS == RHS); 160} 161inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) { 162 if (LHS.From < RHS.From) 163 return true; 164 if (LHS.From > RHS.From) 165 return false; 166 if (LHS.To < RHS.To) 167 return true; 168 if (LHS.To > RHS.To) 169 return false; 170 return LHS.Offset < RHS.Offset; 171} 172inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) { 173 return RHS < LHS; 174} 175inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) { 176 return !(RHS < LHS); 177} 178inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) { 179 return !(LHS < RHS); 180} 181 182/// We use ExternalAttribute to describe an externally visible AliasAttrs 183/// for parameters/return value. 184struct ExternalAttribute { 185 InterfaceValue IValue; 186 AliasAttrs Attr; 187}; 188 189/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute 190struct AliasSummary { 191 // RetParamRelations is a collection of ExternalRelations. 192 SmallVector<ExternalRelation, 8> RetParamRelations; 193 194 // RetParamAttributes is a collection of ExternalAttributes. 195 SmallVector<ExternalAttribute, 8> RetParamAttributes; 196}; 197 198/// This is the result of instantiating InterfaceValue at a particular call 199struct InstantiatedValue { 200 Value *Val; 201 unsigned DerefLevel; 202}; 203Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue, 204 CallBase &Call); 205 206inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) { 207 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; 208} 209inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) { 210 return !(LHS == RHS); 211} 212inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) { 213 return std::less<Value *>()(LHS.Val, RHS.Val) || 214 (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel); 215} 216inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) { 217 return RHS < LHS; 218} 219inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) { 220 return !(RHS < LHS); 221} 222inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) { 223 return !(LHS < RHS); 224} 225 226/// This is the result of instantiating ExternalRelation at a particular 227/// callsite 228struct InstantiatedRelation { 229 InstantiatedValue From, To; 230 int64_t Offset; 231}; 232Optional<InstantiatedRelation> 233instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call); 234 235/// This is the result of instantiating ExternalAttribute at a particular 236/// callsite 237struct InstantiatedAttr { 238 InstantiatedValue IValue; 239 AliasAttrs Attr; 240}; 241Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute EAttr, 242 CallBase &Call); 243} 244 245template <> struct DenseMapInfo<cflaa::InstantiatedValue> { 246 static inline cflaa::InstantiatedValue getEmptyKey() { 247 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(), 248 DenseMapInfo<unsigned>::getEmptyKey()}; 249 } 250 static inline cflaa::InstantiatedValue getTombstoneKey() { 251 return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(), 252 DenseMapInfo<unsigned>::getTombstoneKey()}; 253 } 254 static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { 255 return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue( 256 std::make_pair(IV.Val, IV.DerefLevel)); 257 } 258 static bool isEqual(const cflaa::InstantiatedValue &LHS, 259 const cflaa::InstantiatedValue &RHS) { 260 return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; 261 } 262}; 263} 264 265#endif 266