Coverage Report

Created: 2017-10-03 07:32

/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