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 44 namespace llvm { 45 namespace 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). 54 static 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. 59 typedef 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). 63 AliasAttrs 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). 67 AliasAttrs getAttrUnknown(); 68 bool 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 73 AliasAttrs getAttrCaller(); 74 bool hasCallerAttr(AliasAttrs); 75 bool 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. 81 AliasAttrs getAttrEscaped(); 82 bool 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. 87 AliasAttrs getGlobalOrArgAttrFromValue(const Value &); 88 bool 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 95 AliasAttrs getExternallyVisibleAttrs(AliasAttrs); 96 97 //===----------------------------------------------------------------------===// 98 // Function summary related stuffs 99 //===----------------------------------------------------------------------===// 100 101 /// The maximum number of arguments we can put into a summary. 102 LLVM_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. 112 struct InterfaceValue { 113 unsigned Index; 114 unsigned DerefLevel; 115 }; 116 117 inline bool operator==(InterfaceValue lhs, InterfaceValue rhs) { 118 return lhs.Index == rhs.Index && lhs.DerefLevel == rhs.DerefLevel; 119 } 120 inline 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. 126 struct ExternalRelation { 127 InterfaceValue From, To; 128 }; 129 130 /// We use ExternalAttribute to describe an externally visible AliasAttrs 131 /// for parameters/return value. 132 struct ExternalAttribute { 133 InterfaceValue IValue; 134 AliasAttrs Attr; 135 }; 136 137 /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute 138 struct 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 147 struct InstantiatedValue { 148 Value *Val; 149 unsigned DerefLevel; 150 }; 151 Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite); 152 153 /// This is the result of instantiating ExternalRelation at a particular 154 /// callsite 155 struct InstantiatedRelation { 156 InstantiatedValue From, To; 157 }; 158 Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation, 159 CallSite); 160 161 /// This is the result of instantiating ExternalAttribute at a particular 162 /// callsite 163 struct InstantiatedAttr { 164 InstantiatedValue IValue; 165 AliasAttrs Attr; 166 }; 167 Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute, 168 CallSite); 169 } 170 171 template <> 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