Line data Source code
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 independently, 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 : inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
118 18 : return LHS.Index == RHS.Index && LHS.DerefLevel == RHS.DerefLevel;
119 : }
120 : inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
121 : return !(LHS == RHS);
122 : }
123 : inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
124 0 : return LHS.Index < RHS.Index ||
125 0 : (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
126 : }
127 : inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
128 : return RHS < LHS;
129 : }
130 : inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
131 : return !(RHS < LHS);
132 : }
133 : inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
134 : return !(LHS < RHS);
135 : }
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 : inline int64_t addOffset(int64_t LHS, int64_t RHS) {
143 : if (LHS == UnknownOffset || RHS == UnknownOffset)
144 : return UnknownOffset;
145 : // FIXME: Do we need to guard against integer overflow here?
146 : return LHS + RHS;
147 : }
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 : inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
157 0 : return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
158 : }
159 : inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
160 : return !(LHS == RHS);
161 : }
162 0 : inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
163 : if (LHS.From < RHS.From)
164 : return true;
165 : if (LHS.From > RHS.From)
166 : return false;
167 : if (LHS.To < RHS.To)
168 : return true;
169 : if (LHS.To > RHS.To)
170 : return false;
171 0 : return LHS.Offset < RHS.Offset;
172 : }
173 : inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
174 : return RHS < LHS;
175 : }
176 : inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
177 : return !(RHS < LHS);
178 : }
179 : inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
180 : return !(LHS < RHS);
181 : }
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 0 : inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
207 1290 : return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
208 : }
209 : inline bool operator!=(InstantiatedValue LHS, InstantiatedValue RHS) {
210 : return !(LHS == RHS);
211 : }
212 : inline 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 : }
216 : inline bool operator>(InstantiatedValue LHS, InstantiatedValue RHS) {
217 : return RHS < LHS;
218 : }
219 : inline bool operator<=(InstantiatedValue LHS, InstantiatedValue RHS) {
220 : return !(RHS < LHS);
221 : }
222 : inline 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
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 : 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 13413 : return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
256 13413 : std::make_pair(IV.Val, IV.DerefLevel));
257 : }
258 0 : static bool isEqual(const cflaa::InstantiatedValue &LHS,
259 : const cflaa::InstantiatedValue &RHS) {
260 100155 : return LHS.Val == RHS.Val && LHS.DerefLevel == RHS.DerefLevel;
261 : }
262 : };
263 : }
264 :
265 : #endif
|
