Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/StaticAnalyzer/Core/BasicValueFactory.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BasicValueFactory.cpp - Basic values for Path Sens analysis --------===//
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
//
9
//  This file defines BasicValueFactory, a class that manages the lifetime
10
//  of APSInt objects and symbolic constraints used by ExprEngine
11
//  and related classes.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
16
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
20
#include "llvm/ADT/APSInt.h"
21
#include "llvm/ADT/FoldingSet.h"
22
#include "llvm/ADT/ImmutableList.h"
23
#include "llvm/ADT/STLExtras.h"
24
#include <cassert>
25
#include <cstdint>
26
#include <utility>
27
28
using namespace clang;
29
using namespace ento;
30
31
void CompoundValData::Profile(llvm::FoldingSetNodeID& ID, QualType T,
32
1.33k
                              llvm::ImmutableList<SVal> L) {
33
1.33k
  T.Profile(ID);
34
1.33k
  ID.AddPointer(L.getInternalPointer());
35
1.33k
}
36
37
void LazyCompoundValData::Profile(llvm::FoldingSetNodeID& ID,
38
                                  const StoreRef &store,
39
72.3k
                                  const TypedValueRegion *region) {
40
72.3k
  ID.AddPointer(store.getStore());
41
72.3k
  ID.AddPointer(region);
42
72.3k
}
43
44
void PointerToMemberData::Profile(
45
    llvm::FoldingSetNodeID& ID, const DeclaratorDecl *D,
46
30
    llvm::ImmutableList<const CXXBaseSpecifier *> L) {
47
30
  ID.AddPointer(D);
48
30
  ID.AddPointer(L.getInternalPointer());
49
30
}
50
51
using SValData = std::pair<SVal, uintptr_t>;
52
using SValPair = std::pair<SVal, SVal>;
53
54
namespace llvm {
55
56
template<> struct FoldingSetTrait<SValData> {
57
9
  static inline void Profile(const SValData& X, llvm::FoldingSetNodeID& ID) {
58
9
    X.first.Profile(ID);
59
9
    ID.AddPointer( (void*) X.second);
60
9
  }
61
};
62
63
template<> struct FoldingSetTrait<SValPair> {
64
0
  static inline void Profile(const SValPair& X, llvm::FoldingSetNodeID& ID) {
65
0
    X.first.Profile(ID);
66
0
    X.second.Profile(ID);
67
0
  }
68
};
69
70
} // namespace llvm
71
72
using PersistentSValsTy =
73
    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValData>>;
74
75
using PersistentSValPairsTy =
76
    llvm::FoldingSet<llvm::FoldingSetNodeWrapper<SValPair>>;
77
78
10.8k
BasicValueFactory::~BasicValueFactory() {
79
10.8k
  // Note that the dstor for the contents of APSIntSet will never be called,
80
10.8k
  // so we iterate over the set and invoke the dstor for each APSInt.  This
81
10.8k
  // frees an aux. memory allocated to represent very large constants.
82
10.8k
  for (const auto &I : APSIntSet)
83
77.9k
    I.getValue().~APSInt();
84
10.8k
85
10.8k
  delete (PersistentSValsTy*) PersistentSVals;
86
10.8k
  delete (PersistentSValPairsTy*) PersistentSValPairs;
87
10.8k
}
88
89
1.49M
const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
90
1.49M
  llvm::FoldingSetNodeID ID;
91
1.49M
  void *InsertPos;
92
1.49M
93
1.49M
  using FoldNodeTy = llvm::FoldingSetNodeWrapper<llvm::APSInt>;
94
1.49M
95
1.49M
  X.Profile(ID);
96
1.49M
  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
97
1.49M
98
1.49M
  if (!P) {
99
77.9k
    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
100
77.9k
    new (P) FoldNodeTy(X);
101
77.9k
    APSIntSet.InsertNode(P, InsertPos);
102
77.9k
  }
103
1.49M
104
1.49M
  return *P;
105
1.49M
}
106
107
const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
108
65.9k
                                                bool isUnsigned) {
109
65.9k
  llvm::APSInt V(X, isUnsigned);
110
65.9k
  return getValue(V);
111
65.9k
}
112
113
const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
114
503k
                                           bool isUnsigned) {
115
503k
  llvm::APSInt V(BitWidth, isUnsigned);
116
503k
  V = X;
117
503k
  return getValue(V);
118
503k
}
119
120
205k
const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) {
121
205k
  return getValue(getAPSIntType(T).getValue(X));
122
205k
}
123
124
const CompoundValData*
125
BasicValueFactory::getCompoundValData(QualType T,
126
1.09k
                                      llvm::ImmutableList<SVal> Vals) {
127
1.09k
  llvm::FoldingSetNodeID ID;
128
1.09k
  CompoundValData::Profile(ID, T, Vals);
129
1.09k
  void *InsertPos;
130
1.09k
131
1.09k
  CompoundValData* D = CompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
132
1.09k
133
1.09k
  if (!D) {
134
866
    D = (CompoundValData*) BPAlloc.Allocate<CompoundValData>();
135
866
    new (D) CompoundValData(T, Vals);
136
866
    CompoundValDataSet.InsertNode(D, InsertPos);
137
866
  }
138
1.09k
139
1.09k
  return D;
140
1.09k
}
141
142
const LazyCompoundValData*
143
BasicValueFactory::getLazyCompoundValData(const StoreRef &store,
144
39.6k
                                          const TypedValueRegion *region) {
145
39.6k
  llvm::FoldingSetNodeID ID;
146
39.6k
  LazyCompoundValData::Profile(ID, store, region);
147
39.6k
  void *InsertPos;
148
39.6k
149
39.6k
  LazyCompoundValData *D =
150
39.6k
    LazyCompoundValDataSet.FindNodeOrInsertPos(ID, InsertPos);
151
39.6k
152
39.6k
  if (!D) {
153
10.9k
    D = (LazyCompoundValData*) BPAlloc.Allocate<LazyCompoundValData>();
154
10.9k
    new (D) LazyCompoundValData(store, region);
155
10.9k
    LazyCompoundValDataSet.InsertNode(D, InsertPos);
156
10.9k
  }
157
39.6k
158
39.6k
  return D;
159
39.6k
}
160
161
const PointerToMemberData *BasicValueFactory::getPointerToMemberData(
162
24
    const DeclaratorDecl *DD, llvm::ImmutableList<const CXXBaseSpecifier *> L) {
163
24
  llvm::FoldingSetNodeID ID;
164
24
  PointerToMemberData::Profile(ID, DD, L);
165
24
  void *InsertPos;
166
24
167
24
  PointerToMemberData *D =
168
24
      PointerToMemberDataSet.FindNodeOrInsertPos(ID, InsertPos);
169
24
170
24
  if (!D) {
171
20
    D = (PointerToMemberData*) BPAlloc.Allocate<PointerToMemberData>();
172
20
    new (D) PointerToMemberData(DD, L);
173
20
    PointerToMemberDataSet.InsertNode(D, InsertPos);
174
20
  }
175
24
176
24
  return D;
177
24
}
178
179
const PointerToMemberData *BasicValueFactory::accumCXXBase(
180
    llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
181
24
    const nonloc::PointerToMember &PTM) {
182
24
  nonloc::PointerToMember::PTMDataType PTMDT = PTM.getPTMData();
183
24
  const DeclaratorDecl *DD = nullptr;
184
24
  llvm::ImmutableList<const CXXBaseSpecifier *> PathList;
185
24
186
24
  if (PTMDT.isNull() || PTMDT.is<const DeclaratorDecl *>()) {
187
12
    if (PTMDT.is<const DeclaratorDecl *>())
188
12
      DD = PTMDT.get<const DeclaratorDecl *>();
189
12
190
12
    PathList = CXXBaseListFactory.getEmptyList();
191
12
  } else { // const PointerToMemberData *
192
12
    const PointerToMemberData *PTMD =
193
12
        PTMDT.get<const PointerToMemberData *>();
194
12
    DD = PTMD->getDeclaratorDecl();
195
12
196
12
    PathList = PTMD->getCXXBaseList();
197
12
  }
198
24
199
24
  for (const auto &I : llvm::reverse(PathRange))
200
28
    PathList = prependCXXBase(I, PathList);
201
24
  return getPointerToMemberData(DD, PathList);
202
24
}
203
204
const llvm::APSInt*
205
BasicValueFactory::evalAPSInt(BinaryOperator::Opcode Op,
206
31.9k
                             const llvm::APSInt& V1, const llvm::APSInt& V2) {
207
31.9k
  switch (Op) {
208
31.9k
    default:
209
0
      llvm_unreachable("Invalid Opcode.");
210
31.9k
211
31.9k
    case BO_Mul:
212
1.09k
      return &getValue( V1 * V2 );
213
31.9k
214
31.9k
    case BO_Div:
215
821
      if (V2 == 0) // Avoid division by zero
216
1
        return nullptr;
217
820
      return &getValue( V1 / V2 );
218
820
219
820
    case BO_Rem:
220
19
      if (V2 == 0) // Avoid division by zero
221
0
        return nullptr;
222
19
      return &getValue( V1 % V2 );
223
19
224
15.5k
    case BO_Add:
225
15.5k
      return &getValue( V1 + V2 );
226
19
227
1.34k
    case BO_Sub:
228
1.34k
      return &getValue( V1 - V2 );
229
19
230
341
    case BO_Shl: {
231
341
      // FIXME: This logic should probably go higher up, where we can
232
341
      // test these conditions symbolically.
233
341
234
341
      if (V2.isSigned() && 
V2.isNegative()329
)
235
3
        return nullptr;
236
338
237
338
      uint64_t Amt = V2.getZExtValue();
238
338
239
338
      if (Amt >= V1.getBitWidth())
240
6
        return nullptr;
241
332
242
332
      if (!Ctx.getLangOpts().CPlusPlus2a) {
243
330
        if (V1.isSigned() && 
V1.isNegative()174
)
244
2
          return nullptr;
245
328
246
328
        if (V1.isSigned() && 
Amt > V1.countLeadingZeros()172
)
247
2
          return nullptr;
248
328
      }
249
328
250
328
      return &getValue( V1.operator<<( (unsigned) Amt ));
251
328
    }
252
328
253
398
    case BO_Shr: {
254
398
      // FIXME: This logic should probably go higher up, where we can
255
398
      // test these conditions symbolically.
256
398
257
398
      if (V2.isSigned() && V2.isNegative())
258
0
        return nullptr;
259
398
260
398
      uint64_t Amt = V2.getZExtValue();
261
398
262
398
      if (Amt >= V1.getBitWidth())
263
0
        return nullptr;
264
398
265
398
      return &getValue( V1.operator>>( (unsigned) Amt ));
266
398
    }
267
398
268
4.86k
    case BO_LT:
269
4.86k
      return &getTruthValue( V1 < V2 );
270
398
271
398
    case BO_GT:
272
304
      return &getTruthValue( V1 > V2 );
273
398
274
398
    case BO_LE:
275
79
      return &getTruthValue( V1 <= V2 );
276
398
277
1.08k
    case BO_GE:
278
1.08k
      return &getTruthValue( V1 >= V2 );
279
398
280
5.13k
    case BO_EQ:
281
5.13k
      return &getTruthValue( V1 == V2 );
282
398
283
398
    case BO_NE:
284
274
      return &getTruthValue( V1 != V2 );
285
398
286
398
      // Note: LAnd, LOr, Comma are handled specially by higher-level logic.
287
398
288
410
    case BO_And:
289
410
      return &getValue( V1 & V2 );
290
398
291
398
    case BO_Or:
292
303
      return &getValue( V1 | V2 );
293
398
294
398
    case BO_Xor:
295
7
      return &getValue( V1 ^ V2 );
296
31.9k
  }
297
31.9k
}
298
299
const std::pair<SVal, uintptr_t>&
300
128
BasicValueFactory::getPersistentSValWithData(const SVal& V, uintptr_t Data) {
301
128
  // Lazily create the folding set.
302
128
  if (!PersistentSVals) 
PersistentSVals = new PersistentSValsTy()100
;
303
128
304
128
  llvm::FoldingSetNodeID ID;
305
128
  void *InsertPos;
306
128
  V.Profile(ID);
307
128
  ID.AddPointer((void*) Data);
308
128
309
128
  PersistentSValsTy& Map = *((PersistentSValsTy*) PersistentSVals);
310
128
311
128
  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValData>;
312
128
313
128
  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
314
128
315
128
  if (!P) {
316
119
    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
317
119
    new (P) FoldNodeTy(std::make_pair(V, Data));
318
119
    Map.InsertNode(P, InsertPos);
319
119
  }
320
128
321
128
  return P->getValue();
322
128
}
323
324
const std::pair<SVal, SVal>&
325
0
BasicValueFactory::getPersistentSValPair(const SVal& V1, const SVal& V2) {
326
0
  // Lazily create the folding set.
327
0
  if (!PersistentSValPairs) PersistentSValPairs = new PersistentSValPairsTy();
328
0
329
0
  llvm::FoldingSetNodeID ID;
330
0
  void *InsertPos;
331
0
  V1.Profile(ID);
332
0
  V2.Profile(ID);
333
0
334
0
  PersistentSValPairsTy& Map = *((PersistentSValPairsTy*) PersistentSValPairs);
335
0
336
0
  using FoldNodeTy = llvm::FoldingSetNodeWrapper<SValPair>;
337
0
338
0
  FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos);
339
0
340
0
  if (!P) {
341
0
    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
342
0
    new (P) FoldNodeTy(std::make_pair(V1, V2));
343
0
    Map.InsertNode(P, InsertPos);
344
0
  }
345
0
346
0
  return P->getValue();
347
0
}
348
349
0
const SVal* BasicValueFactory::getPersistentSVal(SVal X) {
350
0
  return &getPersistentSValWithData(X, 0).first;
351
0
}