Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/AliasAnalysisSummary.h
Line
Count
Source (jump to first uncovered line)
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
43
namespace llvm {
44
namespace 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).
53
static 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.
58
typedef 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).
62
AliasAttrs 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).
66
AliasAttrs getAttrUnknown();
67
bool 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
72
AliasAttrs getAttrCaller();
73
bool hasCallerAttr(AliasAttrs);
74
bool 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.
80
AliasAttrs getAttrEscaped();
81
bool 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.
86
AliasAttrs getGlobalOrArgAttrFromValue(const Value &);
87
bool 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
94
AliasAttrs getExternallyVisibleAttrs(AliasAttrs);
95
96
//===----------------------------------------------------------------------===//
97
// Function summary related stuffs
98
//===----------------------------------------------------------------------===//
99
100
/// The maximum number of arguments we can put into a summary.
101
static 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.
111
struct InterfaceValue {
112
  unsigned Index;
113
  unsigned DerefLevel;
114
};
115
116
51
inline bool operator==(InterfaceValue LHS, InterfaceValue RHS) {
117
51
  return LHS.Index == RHS.Index && 
LHS.DerefLevel == RHS.DerefLevel0
;
118
51
}
119
33
inline bool operator!=(InterfaceValue LHS, InterfaceValue RHS) {
120
33
  return !(LHS == RHS);
121
33
}
122
0
inline bool operator<(InterfaceValue LHS, InterfaceValue RHS) {
123
0
  return LHS.Index < RHS.Index ||
124
0
         (LHS.Index == RHS.Index && LHS.DerefLevel < RHS.DerefLevel);
125
0
}
126
0
inline bool operator>(InterfaceValue LHS, InterfaceValue RHS) {
127
0
  return RHS < LHS;
128
0
}
129
0
inline bool operator<=(InterfaceValue LHS, InterfaceValue RHS) {
130
0
  return !(RHS < LHS);
131
0
}
132
0
inline bool operator>=(InterfaceValue LHS, InterfaceValue RHS) {
133
0
  return !(LHS < RHS);
134
0
}
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.
139
static const int64_t UnknownOffset = INT64_MAX;
140
141
0
inline int64_t addOffset(int64_t LHS, int64_t RHS) {
142
0
  if (LHS == UnknownOffset || RHS == UnknownOffset)
143
0
    return UnknownOffset;
144
0
  // FIXME: Do we need to guard against integer overflow here?
145
0
  return LHS + RHS;
146
0
}
147
148
/// We use ExternalRelation to describe an externally visible aliasing relations
149
/// between parameters/return value of a function.
150
struct ExternalRelation {
151
  InterfaceValue From, To;
152
  int64_t Offset;
153
};
154
155
0
inline bool operator==(ExternalRelation LHS, ExternalRelation RHS) {
156
0
  return LHS.From == RHS.From && LHS.To == RHS.To && LHS.Offset == RHS.Offset;
157
0
}
158
0
inline bool operator!=(ExternalRelation LHS, ExternalRelation RHS) {
159
0
  return !(LHS == RHS);
160
0
}
161
0
inline bool operator<(ExternalRelation LHS, ExternalRelation RHS) {
162
0
  if (LHS.From < RHS.From)
163
0
    return true;
164
0
  if (LHS.From > RHS.From)
165
0
    return false;
166
0
  if (LHS.To < RHS.To)
167
0
    return true;
168
0
  if (LHS.To > RHS.To)
169
0
    return false;
170
0
  return LHS.Offset < RHS.Offset;
171
0
}
172
0
inline bool operator>(ExternalRelation LHS, ExternalRelation RHS) {
173
0
  return RHS < LHS;
174
0
}
175
0
inline bool operator<=(ExternalRelation LHS, ExternalRelation RHS) {
176
0
  return !(RHS < LHS);
177
0
}
178
0
inline bool operator>=(ExternalRelation LHS, ExternalRelation RHS) {
179
0
  return !(LHS < RHS);
180
0
}
181
182
/// We use ExternalAttribute to describe an externally visible AliasAttrs
183
/// for parameters/return value.
184
struct ExternalAttribute {
185
  InterfaceValue IValue;
186
  AliasAttrs Attr;
187
};
188
189
/// AliasSummary is just a collection of ExternalRelation and ExternalAttribute
190
struct 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
199
struct InstantiatedValue {
200
  Value *Val;
201
  unsigned DerefLevel;
202
};
203
Optional<InstantiatedValue> instantiateInterfaceValue(InterfaceValue IValue,
204
                                                      CallBase &Call);
205
206
1.28k
inline bool operator==(InstantiatedValue LHS, InstantiatedValue RHS) {
207
1.28k
  return LHS.Val == RHS.Val && 
LHS.DerefLevel == RHS.DerefLevel276
;
208
1.28k
}
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>
233
instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call);
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 EAttr,
242
                                                        CallBase &Call);
243
}
244
245
template <> struct DenseMapInfo<cflaa::InstantiatedValue> {
246
21.8k
  static inline cflaa::InstantiatedValue getEmptyKey() {
247
21.8k
    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getEmptyKey(),
248
21.8k
                                    DenseMapInfo<unsigned>::getEmptyKey()};
249
21.8k
  }
250
18.7k
  static inline cflaa::InstantiatedValue getTombstoneKey() {
251
18.7k
    return cflaa::InstantiatedValue{DenseMapInfo<Value *>::getTombstoneKey(),
252
18.7k
                                    DenseMapInfo<unsigned>::getTombstoneKey()};
253
18.7k
  }
254
13.4k
  static unsigned getHashValue(const cflaa::InstantiatedValue &IV) {
255
13.4k
    return DenseMapInfo<std::pair<Value *, unsigned>>::getHashValue(
256
13.4k
        std::make_pair(IV.Val, IV.DerefLevel));
257
13.4k
  }
258
  static bool isEqual(const cflaa::InstantiatedValue &LHS,
259
140k
                      const cflaa::InstantiatedValue &RHS) {
260
140k
    return LHS.Val == RHS.Val && 
LHS.DerefLevel == RHS.DerefLevel118k
;
261
140k
  }
262
};
263
}
264
265
#endif