/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/AliasAnalysisSummary.h
Line | Count | Source (jump to first uncovered line) |
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 | | static const 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 | 51 | inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) { |
118 | 0 | return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel; |
119 | 51 | } |
120 | 33 | inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) { |
121 | 33 | return !(LHS == RHS); |
122 | 33 | } |
123 | 0 | inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) { |
124 | 0 | return LHS.Index < RHS.Index || |
125 | 0 | (LHS.Index == RHS.Index && 0 LHS.DerefLevel < RHS.DerefLevel0 ); |
126 | 0 | } |
127 | 0 | inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) { |
128 | 0 | return RHS < LHS; |
129 | 0 | } |
130 | 0 | inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) { |
131 | 0 | return !(RHS < LHS); |
132 | 0 | } |
133 | 0 | inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) { |
134 | 0 | return !(LHS < RHS); |
135 | 0 | } |
136 | | |
137 | | // We use UnknownOffset to represent pointer offsets that cannot be determined |
138 | | // at compile time. Note that MemoryLocation::UnknownSize cannot be used here |
139 | | // because we require a signed value. |
140 | | static const int64_t UnknownOffset = INT64_MAX; |
141 | | |
142 | 0 | inline int64_t addOffset(int64_t LHS, int64_t RHS) { |
143 | 0 | if (LHS == UnknownOffset || RHS == UnknownOffset) |
144 | 0 | return UnknownOffset; |
145 | 0 | // FIXME: Do we need to guard against integer overflow here? |
146 | 0 | return LHS + RHS; |
147 | 0 | } |
148 | | |
149 | | /// We use ExternalRelation to describe an externally visible aliasing relations |
150 | | /// between parameters/return value of a function. |
151 | | struct ExternalRelation { |
152 | | InterfaceValue From, To; |
153 | | int64_t Offset; |
154 | | }; |
155 | | |
156 | 0 | inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) { |
157 | 0 | return LHS.From == RHS.From && LHS.To == RHS.To0 && LHS.Offset == RHS.Offset0 ; |
158 | 0 | } |
159 | 0 | inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) { |
160 | 0 | return !(LHS == RHS); |
161 | 0 | } |
162 | 0 | inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) { |
163 | 0 | if (LHS.From < RHS.From) |
164 | 0 | return true; |
165 | 0 | if (0 LHS.From > RHS.From0 ) |
166 | 0 | return false; |
167 | 0 | if (0 LHS.To < RHS.To0 ) |
168 | 0 | return true; |
169 | 0 | if (0 LHS.To > RHS.To0 ) |
170 | 0 | return false; |
171 | 0 | return LHS.Offset < RHS.Offset; |
172 | 0 | } |
173 | 0 | inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) { |
174 | 0 | return RHS < LHS; |
175 | 0 | } |
176 | 0 | inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) { |
177 | 0 | return !(RHS < LHS); |
178 | 0 | } |
179 | 0 | inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) { |
180 | 0 | return !(LHS < RHS); |
181 | 0 | } |
182 | | |
183 | | /// We use ExternalAttribute to describe an externally visible AliasAttrs |
184 | | /// for parameters/return value. |
185 | | struct ExternalAttribute { |
186 | | InterfaceValue IValue; |
187 | | AliasAttrs Attr; |
188 | | }; |
189 | | |
190 | | /// AliasSummary is just a collection of ExternalRelation and ExternalAttribute |
191 | | struct AliasSummary { |
192 | | // RetParamRelations is a collection of ExternalRelations. |
193 | | SmallVector<ExternalRelation, 8> RetParamRelations; |
194 | | |
195 | | // RetParamAttributes is a collection of ExternalAttributes. |
196 | | SmallVector<ExternalAttribute, 8> RetParamAttributes; |
197 | | }; |
198 | | |
199 | | /// This is the result of instantiating InterfaceValue at a particular callsite |
200 | | struct InstantiatedValue { |
201 | | Value *Val; |
202 | | unsigned DerefLevel; |
203 | | }; |
204 | | Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue, CallSite); |
205 | | |
206 | 1.29k | inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) { |
207 | 276 | return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; |
208 | 1.29k | } |
209 | 0 | inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) { |
210 | 0 | return !(LHS == RHS); |
211 | 0 | } |
212 | 0 | inline bool operator<(InstantiatedValue LHS, InstantiatedValue RHS) { |
213 | 0 | return std::less<Value *>()(LHS.Val, RHS.Val) || |
214 | 0 | (LHS.Val == RHS.Val && LHS.DerefLevel < RHS.DerefLevel); |
215 | 0 | } |
216 | 0 | inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) { |
217 | 0 | return RHS < LHS; |
218 | 0 | } |
219 | 0 | inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) { |
220 | 0 | return !(RHS < LHS); |
221 | 0 | } |
222 | 0 | inline bool operator>=(InstantiatedValue LHS, InstantiatedValue RHS) { |
223 | 0 | return !(LHS < RHS); |
224 | 0 | } |
225 | | |
226 | | /// This is the result of instantiating ExternalRelation at a particular |
227 | | /// callsite |
228 | | struct InstantiatedRelation { |
229 | | InstantiatedValue From, To; |
230 | | int64_t Offset; |
231 | | }; |
232 | | Optional<InstantiatedRelation> instantiateExternalRelation(ExternalRelation, |
233 | | CallSite); |
234 | | |
235 | | /// This is the result of instantiating ExternalAttribute at a particular |
236 | | /// callsite |
237 | | struct InstantiatedAttr { |
238 | | InstantiatedValue IValue; |
239 | | AliasAttrs Attr; |
240 | | }; |
241 | | Optional<InstantiatedAttr> instantiateExternalAttribute(ExternalAttribute, |
242 | | CallSite); |
243 | | } |
244 | | |
245 | | template <> struct DenseMapInfo<cflaa::InstantiatedValue> { |
246 | 21.7k | static inline cflaa::InstantiatedValue getEmptyKey() { |
247 | 21.7k | return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(), |
248 | 21.7k | DenseMapInfo<unsigned>::getEmptyKey()}; |
249 | 21.7k | } |
250 | 18.6k | static inline cflaa::InstantiatedValue getTombstoneKey() { |
251 | 18.6k | return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(), |
252 | 18.6k | DenseMapInfo<unsigned>::getTombstoneKey()}; |
253 | 18.6k | } |
254 | 13.3k | static unsigned getHashValue(const cflaa::InstantiatedValue &IV) { |
255 | 13.3k | return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue( |
256 | 13.3k | std::make_pair(IV.Val, IV.DerefLevel)); |
257 | 13.3k | } |
258 | | static bool isEqual(const cflaa::InstantiatedValue &LHS, |
259 | 143k | const cflaa::InstantiatedValue &RHS) { |
260 | 117k | return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel; |
261 | 143k | } |
262 | | }; |
263 | | } |
264 | | |
265 | | #endif |