Coverage Report

Created: 2022-05-14 11:35

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- DataflowEnvironment.cpp ---------------------------------*- C++ -*-===//
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 an Environment class that is used by dataflow analyses
10
//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
11
//  program at given program points.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
16
#include "clang/AST/Decl.h"
17
#include "clang/AST/DeclCXX.h"
18
#include "clang/AST/ExprCXX.h"
19
#include "clang/AST/Type.h"
20
#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
21
#include "clang/Analysis/FlowSensitive/StorageLocation.h"
22
#include "clang/Analysis/FlowSensitive/Value.h"
23
#include "llvm/ADT/DenseMap.h"
24
#include "llvm/ADT/DenseSet.h"
25
#include "llvm/Support/Casting.h"
26
#include "llvm/Support/ErrorHandling.h"
27
#include <cassert>
28
#include <memory>
29
#include <utility>
30
31
namespace clang {
32
namespace dataflow {
33
34
// FIXME: convert these to parameters of the analysis or environment. Current
35
// settings have been experimentaly validated, but only for a particular
36
// analysis.
37
static constexpr int MaxCompositeValueDepth = 3;
38
static constexpr int MaxCompositeValueSize = 1000;
39
40
/// Returns a map consisting of key-value entries that are present in both maps.
41
template <typename K, typename V>
42
llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
43
66.0k
                                        const llvm::DenseMap<K, V> &Map2) {
44
66.0k
  llvm::DenseMap<K, V> Result;
45
66.0k
  for (auto &Entry : Map1) {
46
1.14k
    auto It = Map2.find(Entry.first);
47
1.14k
    if (It != Map2.end() && 
Entry.second == It->second876
)
48
876
      Result.insert({Entry.first, Entry.second});
49
1.14k
  }
50
66.0k
  return Result;
51
66.0k
}
llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > clang::dataflow::intersectDenseMaps<clang::ValueDecl const*, clang::dataflow::StorageLocation*>(llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&, llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&)
Line
Count
Source
43
22.0k
                                        const llvm::DenseMap<K, V> &Map2) {
44
22.0k
  llvm::DenseMap<K, V> Result;
45
22.0k
  for (auto &Entry : Map1) {
46
312
    auto It = Map2.find(Entry.first);
47
312
    if (It != Map2.end() && 
Entry.second == It->second300
)
48
300
      Result.insert({Entry.first, Entry.second});
49
312
  }
50
22.0k
  return Result;
51
22.0k
}
llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > clang::dataflow::intersectDenseMaps<clang::Expr const*, clang::dataflow::StorageLocation*>(llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > const&, llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > const&)
Line
Count
Source
43
22.0k
                                        const llvm::DenseMap<K, V> &Map2) {
44
22.0k
  llvm::DenseMap<K, V> Result;
45
22.0k
  for (auto &Entry : Map1) {
46
828
    auto It = Map2.find(Entry.first);
47
828
    if (It != Map2.end() && 
Entry.second == It->second572
)
48
572
      Result.insert({Entry.first, Entry.second});
49
828
  }
50
22.0k
  return Result;
51
22.0k
}
llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > clang::dataflow::intersectDenseMaps<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> >(llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > const&, llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > const&)
Line
Count
Source
43
22.0k
                                        const llvm::DenseMap<K, V> &Map2) {
44
22.0k
  llvm::DenseMap<K, V> Result;
45
22.0k
  for (auto &Entry : Map1) {
46
4
    auto It = Map2.find(Entry.first);
47
4
    if (It != Map2.end() && Entry.second == It->second)
48
4
      Result.insert({Entry.first, Entry.second});
49
4
  }
50
22.0k
  return Result;
51
22.0k
}
52
53
/// Returns true if and only if `Val1` is equivalent to `Val2`.
54
static bool equivalentValues(QualType Type, Value *Val1,
55
                             const Environment &Env1, Value *Val2,
56
                             const Environment &Env2,
57
28
                             Environment::ValueModel &Model) {
58
28
  if (Val1 == Val2)
59
17
    return true;
60
61
11
  if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
62
7
    auto *IndVal2 = cast<IndirectionValue>(Val2);
63
7
    assert(IndVal1->getKind() == IndVal2->getKind());
64
7
    if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc())
65
6
      return true;
66
7
  }
67
68
5
  return Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
69
11
}
70
71
/// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
72
/// respectively, of the same type `Type`. Merging generally produces a single
73
/// value that (soundly) approximates the two inputs, although the actual
74
/// meaning depends on `Model`.
75
static Value *mergeDistinctValues(QualType Type, Value *Val1,
76
                                  const Environment &Env1, Value *Val2,
77
                                  const Environment &Env2,
78
                                  Environment &MergedEnv,
79
48
                                  Environment::ValueModel &Model) {
80
  // Join distinct boolean values preserving information about the constraints
81
  // in the respective path conditions.
82
  //
83
  // FIXME: Does not work for backedges, since the two (or more) paths will not
84
  // have mutually exclusive conditions.
85
48
  if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
86
26
    auto *Expr2 = cast<BoolValue>(Val2);
87
26
    return &Env1.makeOr(Env1.makeAnd(Env1.getFlowConditionToken(), *Expr1),
88
26
                        Env1.makeAnd(Env2.getFlowConditionToken(), *Expr2));
89
26
  }
90
91
  // FIXME: add unit tests that cover this statement.
92
22
  if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
93
2
    auto *IndVal2 = cast<IndirectionValue>(Val2);
94
2
    assert(IndVal1->getKind() == IndVal2->getKind());
95
2
    if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc()) {
96
2
      return Val1;
97
2
    }
98
2
  }
99
100
  // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
101
  // returns false to avoid storing unneeded values in `DACtx`.
102
20
  if (Value *MergedVal = MergedEnv.createValue(Type))
103
20
    if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
104
20
      return MergedVal;
105
106
0
  return nullptr;
107
20
}
108
109
/// Initializes a global storage value.
110
805
static void initGlobalVar(const VarDecl &D, Environment &Env) {
111
805
  if (!D.hasGlobalStorage() ||
112
805
      
Env.getStorageLocation(D, SkipPast::None) != nullptr45
)
113
763
    return;
114
115
42
  auto &Loc = Env.createStorageLocation(D);
116
42
  Env.setStorageLocation(D, Loc);
117
42
  if (auto *Val = Env.createValue(D.getType()))
118
42
    Env.setValue(Loc, *Val);
119
42
}
120
121
/// Initializes a global storage value.
122
1.21k
static void initGlobalVar(const Decl &D, Environment &Env) {
123
1.21k
  if (auto *V = dyn_cast<VarDecl>(&D))
124
805
    initGlobalVar(*V, Env);
125
1.21k
}
126
127
/// Initializes global storage values that are declared or referenced from
128
/// sub-statements of `S`.
129
// FIXME: Add support for resetting globals after function calls to enable
130
// the implementation of sound analyses.
131
3.50k
static void initGlobalVars(const Stmt &S, Environment &Env) {
132
3.50k
  for (auto *Child : S.children()) {
133
3.20k
    if (Child != nullptr)
134
3.20k
      initGlobalVars(*Child, Env);
135
3.20k
  }
136
137
3.50k
  if (auto *DS = dyn_cast<DeclStmt>(&S)) {
138
292
    if (DS->isSingleDecl()) {
139
290
      initGlobalVar(*DS->getSingleDecl(), Env);
140
290
    } else {
141
2
      for (auto *D : DS->getDeclGroup())
142
4
        initGlobalVar(*D, Env);
143
2
    }
144
3.21k
  } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
145
655
    initGlobalVar(*E->getDecl(), Env);
146
2.55k
  } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
147
268
    initGlobalVar(*E->getMemberDecl(), Env);
148
268
  }
149
3.50k
}
150
151
static void
152
getFieldsFromClassHierarchy(QualType Type, bool IgnorePrivateFields,
153
3.92k
                            llvm::DenseSet<const FieldDecl *> &Fields) {
154
3.92k
  if (Type->isIncompleteType() || Type->isDependentType() ||
155
3.92k
      !Type->isRecordType())
156
0
    return;
157
158
3.92k
  for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
159
409
    if (IgnorePrivateFields &&
160
409
        
(40
Field->getAccess() == AS_private40
||
161
40
         
(24
Field->getAccess() == AS_none24
&&
Type->getAsRecordDecl()->isClass()0
)))
162
16
      continue;
163
393
    Fields.insert(Field);
164
393
  }
165
3.92k
  if (auto *CXXRecord = Type->getAsCXXRecordDecl()) {
166
3.92k
    for (const CXXBaseSpecifier &Base : CXXRecord->bases()) {
167
      // Ignore private fields (including default access in C++ classes) in
168
      // base classes, because they are not visible in derived classes.
169
1.26k
      getFieldsFromClassHierarchy(Base.getType(), /*IgnorePrivateFields=*/true,
170
1.26k
                                  Fields);
171
1.26k
    }
172
3.92k
  }
173
3.92k
}
174
175
/// Gets the set of all fields accesible from the type.
176
///
177
/// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
178
/// field decl will be modeled for all instances of the inherited field.
179
static llvm::DenseSet<const FieldDecl *>
180
2.66k
getAccessibleObjectFields(QualType Type) {
181
2.66k
  llvm::DenseSet<const FieldDecl *> Fields;
182
  // Don't ignore private fields for the class itself, only its super classes.
183
2.66k
  getFieldsFromClassHierarchy(Type, /*IgnorePrivateFields=*/false, Fields);
184
2.66k
  return Fields;
185
2.66k
}
186
187
Environment::Environment(DataflowAnalysisContext &DACtx)
188
22.3k
    : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
189
190
Environment::Environment(const Environment &Other)
191
    : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc),
192
      ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
193
      MemberLocToStruct(Other.MemberLocToStruct),
194
157k
      FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
195
157k
}
196
197
0
Environment &Environment::operator=(const Environment &Other) {
198
0
  Environment Copy(Other);
199
0
  *this = std::move(Copy);
200
0
  return *this;
201
0
}
202
203
Environment::Environment(DataflowAnalysisContext &DACtx,
204
                         const DeclContext &DeclCtx)
205
294
    : Environment(DACtx) {
206
294
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
207
294
    assert(FuncDecl->getBody() != nullptr);
208
0
    initGlobalVars(*FuncDecl->getBody(), *this);
209
294
    for (const auto *ParamDecl : FuncDecl->parameters()) {
210
142
      assert(ParamDecl != nullptr);
211
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
212
142
      setStorageLocation(*ParamDecl, ParamLoc);
213
142
      if (Value *ParamVal = createValue(ParamDecl->getType()))
214
142
        setValue(ParamLoc, *ParamVal);
215
142
    }
216
294
  }
217
218
294
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
219
5
    if (!MethodDecl->isStatic()) {
220
5
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
221
      // FIXME: Add support for union types.
222
5
      if (!ThisPointeeType->isUnionType()) {
223
5
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
224
5
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
225
5
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
226
5
          setValue(ThisPointeeLoc, *ThisPointeeVal);
227
5
      }
228
5
    }
229
5
  }
230
294
}
Unexecuted instantiation: clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&)
clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&)
Line
Count
Source
205
294
    : Environment(DACtx) {
206
294
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
207
294
    assert(FuncDecl->getBody() != nullptr);
208
0
    initGlobalVars(*FuncDecl->getBody(), *this);
209
294
    for (const auto *ParamDecl : FuncDecl->parameters()) {
210
142
      assert(ParamDecl != nullptr);
211
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
212
142
      setStorageLocation(*ParamDecl, ParamLoc);
213
142
      if (Value *ParamVal = createValue(ParamDecl->getType()))
214
142
        setValue(ParamLoc, *ParamVal);
215
142
    }
216
294
  }
217
218
294
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
219
5
    if (!MethodDecl->isStatic()) {
220
5
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
221
      // FIXME: Add support for union types.
222
5
      if (!ThisPointeeType->isUnionType()) {
223
5
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
224
5
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
225
5
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
226
5
          setValue(ThisPointeeLoc, *ThisPointeeVal);
227
5
      }
228
5
    }
229
5
  }
230
294
}
231
232
bool Environment::equivalentTo(const Environment &Other,
233
6
                               Environment::ValueModel &Model) const {
234
6
  assert(DACtx == Other.DACtx);
235
236
6
  if (DeclToLoc != Other.DeclToLoc)
237
0
    return false;
238
239
6
  if (ExprToLoc != Other.ExprToLoc)
240
0
    return false;
241
242
6
  if (MemberLocToStruct != Other.MemberLocToStruct)
243
0
    return false;
244
245
  // Compare the contents for the intersection of their domains.
246
29
  
for (auto &Entry : LocToVal)6
{
247
29
    const StorageLocation *Loc = Entry.first;
248
29
    assert(Loc != nullptr);
249
250
0
    Value *Val = Entry.second;
251
29
    assert(Val != nullptr);
252
253
0
    auto It = Other.LocToVal.find(Loc);
254
29
    if (It == Other.LocToVal.end())
255
1
      continue;
256
28
    assert(It->second != nullptr);
257
258
28
    if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
259
0
      return false;
260
28
  }
261
262
6
  return true;
263
6
}
264
265
LatticeJoinEffect Environment::join(const Environment &Other,
266
22.0k
                                    Environment::ValueModel &Model) {
267
22.0k
  assert(DACtx == Other.DACtx);
268
269
0
  auto Effect = LatticeJoinEffect::Unchanged;
270
271
22.0k
  Environment JoinedEnv(*DACtx);
272
273
22.0k
  JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
274
22.0k
  if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
275
12
    Effect = LatticeJoinEffect::Changed;
276
277
22.0k
  JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
278
22.0k
  if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
279
120
    Effect = LatticeJoinEffect::Changed;
280
281
22.0k
  JoinedEnv.MemberLocToStruct =
282
22.0k
      intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
283
22.0k
  if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
284
0
    Effect = LatticeJoinEffect::Changed;
285
286
  // FIXME: set `Effect` as needed.
287
22.0k
  JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
288
22.0k
      *FlowConditionToken, *Other.FlowConditionToken);
289
290
22.0k
  for (auto &Entry : LocToVal) {
291
1.01k
    const StorageLocation *Loc = Entry.first;
292
1.01k
    assert(Loc != nullptr);
293
294
0
    Value *Val = Entry.second;
295
1.01k
    assert(Val != nullptr);
296
297
0
    auto It = Other.LocToVal.find(Loc);
298
1.01k
    if (It == Other.LocToVal.end())
299
214
      continue;
300
804
    assert(It->second != nullptr);
301
302
804
    if (Val == It->second) {
303
756
      JoinedEnv.LocToVal.insert({Loc, Val});
304
756
      continue;
305
756
    }
306
307
48
    if (Value *MergedVal = mergeDistinctValues(
308
48
            Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model))
309
48
      JoinedEnv.LocToVal.insert({Loc, MergedVal});
310
48
  }
311
22.0k
  if (LocToVal.size() != JoinedEnv.LocToVal.size())
312
120
    Effect = LatticeJoinEffect::Changed;
313
314
22.0k
  *this = std::move(JoinedEnv);
315
316
22.0k
  return Effect;
317
22.0k
}
318
319
1.66k
StorageLocation &Environment::createStorageLocation(QualType Type) {
320
1.66k
  assert(!Type.isNull());
321
1.66k
  if (Type->isStructureOrClassType() || 
Type->isUnionType()802
) {
322
    // FIXME: Explore options to avoid eager initialization of fields as some of
323
    // them might not be needed for a particular analysis.
324
864
    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
325
864
    for (const FieldDecl *Field : getAccessibleObjectFields(Type)) {
326
127
      FieldLocs.insert({Field, &createStorageLocation(Field->getType())});
327
127
    }
328
864
    return takeOwnership(
329
864
        std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
330
864
  }
331
799
  return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
332
1.66k
}
333
334
761
StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
335
  // Evaluated declarations are always assigned the same storage locations to
336
  // ensure that the environment stabilizes across loop iterations. Storage
337
  // locations for evaluated declarations are stored in the analysis context.
338
761
  if (auto *Loc = DACtx->getStorageLocation(D))
339
290
    return *Loc;
340
471
  auto &Loc = createStorageLocation(D.getType());
341
471
  DACtx->setStorageLocation(D, Loc);
342
471
  return Loc;
343
761
}
344
345
2.04k
StorageLocation &Environment::createStorageLocation(const Expr &E) {
346
  // Evaluated expressions are always assigned the same storage locations to
347
  // ensure that the environment stabilizes across loop iterations. Storage
348
  // locations for evaluated expressions are stored in the analysis context.
349
2.04k
  if (auto *Loc = DACtx->getStorageLocation(E))
350
1.03k
    return *Loc;
351
1.00k
  auto &Loc = createStorageLocation(E.getType());
352
1.00k
  DACtx->setStorageLocation(E, Loc);
353
1.00k
  return Loc;
354
2.04k
}
355
356
761
void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
357
761
  assert(DeclToLoc.find(&D) == DeclToLoc.end());
358
0
  DeclToLoc[&D] = &Loc;
359
761
}
360
361
StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
362
1.57k
                                                 SkipPast SP) const {
363
1.57k
  auto It = DeclToLoc.find(&D);
364
1.57k
  return It == DeclToLoc.end() ? 
nullptr347
:
&skip(*It->second, SP)1.22k
;
365
1.57k
}
366
367
2.52k
void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
368
2.52k
  const Expr &CanonE = ignoreCFGOmittedNodes(E);
369
2.52k
  assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
370
0
  ExprToLoc[&CanonE] = &Loc;
371
2.52k
}
372
373
StorageLocation *Environment::getStorageLocation(const Expr &E,
374
3.97k
                                                 SkipPast SP) const {
375
  // FIXME: Add a test with parens.
376
3.97k
  auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
377
3.97k
  return It == ExprToLoc.end() ? 
nullptr467
:
&skip(*It->second, SP)3.50k
;
378
3.97k
}
379
380
37
StorageLocation *Environment::getThisPointeeStorageLocation() const {
381
37
  return DACtx->getThisPointeeStorageLocation();
382
37
}
383
384
3.37k
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
385
3.37k
  LocToVal[&Loc] = &Val;
386
387
3.37k
  if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
388
1.26k
    auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
389
390
1.26k
    const QualType Type = AggregateLoc.getType();
391
1.26k
    assert(Type->isStructureOrClassType());
392
393
166
    for (const FieldDecl *Field : getAccessibleObjectFields(Type)) {
394
166
      assert(Field != nullptr);
395
0
      StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
396
166
      MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
397
166
      if (auto *FieldVal = StructVal->getChild(*Field))
398
164
        setValue(FieldLoc, *FieldVal);
399
166
    }
400
1.26k
  }
401
402
0
  auto IT = MemberLocToStruct.find(&Loc);
403
3.37k
  if (IT != MemberLocToStruct.end()) {
404
    // `Loc` is the location of a struct member so we need to also update the
405
    // value of the member in the corresponding `StructValue`.
406
407
176
    assert(IT->second.first != nullptr);
408
0
    StructValue &StructVal = *IT->second.first;
409
410
176
    assert(IT->second.second != nullptr);
411
0
    const ValueDecl &Member = *IT->second.second;
412
413
176
    StructVal.setChild(Member, Val);
414
176
  }
415
3.37k
}
416
417
5.93k
Value *Environment::getValue(const StorageLocation &Loc) const {
418
5.93k
  auto It = LocToVal.find(&Loc);
419
5.93k
  return It == LocToVal.end() ? 
nullptr11
:
It->second5.91k
;
420
5.93k
}
421
422
142
Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
423
142
  auto *Loc = getStorageLocation(D, SP);
424
142
  if (Loc == nullptr)
425
0
    return nullptr;
426
142
  return getValue(*Loc);
427
142
}
428
429
2.86k
Value *Environment::getValue(const Expr &E, SkipPast SP) const {
430
2.86k
  auto *Loc = getStorageLocation(E, SP);
431
2.86k
  if (Loc == nullptr)
432
212
    return nullptr;
433
2.65k
  return getValue(*Loc);
434
2.86k
}
435
436
746
Value *Environment::createValue(QualType Type) {
437
746
  llvm::DenseSet<QualType> Visited;
438
746
  int CreatedValuesCount = 0;
439
746
  Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
440
746
                                                CreatedValuesCount);
441
746
  if (CreatedValuesCount > MaxCompositeValueSize) {
442
0
    llvm::errs() << "Attempting to initialize a huge value of type: " << Type
443
0
                 << '\n';
444
0
  }
445
746
  return Val;
446
746
}
447
448
Value *Environment::createValueUnlessSelfReferential(
449
    QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
450
888
    int &CreatedValuesCount) {
451
888
  assert(!Type.isNull());
452
453
  // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
454
888
  if ((Depth > 1 && 
CreatedValuesCount > MaxCompositeValueSize31
) ||
455
888
      Depth > MaxCompositeValueDepth)
456
0
    return nullptr;
457
458
888
  if (Type->isBooleanType()) {
459
71
    CreatedValuesCount++;
460
71
    return &makeAtomicBoolValue();
461
71
  }
462
463
817
  if (Type->isIntegerType()) {
464
210
    CreatedValuesCount++;
465
210
    return &takeOwnership(std::make_unique<IntegerValue>());
466
210
  }
467
468
607
  if (Type->isReferenceType()) {
469
26
    CreatedValuesCount++;
470
26
    QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
471
26
    auto &PointeeLoc = createStorageLocation(PointeeType);
472
473
26
    if (!Visited.contains(PointeeType.getCanonicalType())) {
474
22
      Visited.insert(PointeeType.getCanonicalType());
475
22
      Value *PointeeVal = createValueUnlessSelfReferential(
476
22
          PointeeType, Visited, Depth, CreatedValuesCount);
477
22
      Visited.erase(PointeeType.getCanonicalType());
478
479
22
      if (PointeeVal != nullptr)
480
22
        setValue(PointeeLoc, *PointeeVal);
481
22
    }
482
483
26
    return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
484
26
  }
485
486
581
  if (Type->isPointerType()) {
487
26
    CreatedValuesCount++;
488
26
    QualType PointeeType = Type->castAs<PointerType>()->getPointeeType();
489
26
    auto &PointeeLoc = createStorageLocation(PointeeType);
490
491
26
    if (!Visited.contains(PointeeType.getCanonicalType())) {
492
22
      Visited.insert(PointeeType.getCanonicalType());
493
22
      Value *PointeeVal = createValueUnlessSelfReferential(
494
22
          PointeeType, Visited, Depth, CreatedValuesCount);
495
22
      Visited.erase(PointeeType.getCanonicalType());
496
497
22
      if (PointeeVal != nullptr)
498
21
        setValue(PointeeLoc, *PointeeVal);
499
22
    }
500
501
26
    return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
502
26
  }
503
504
555
  if (Type->isStructureOrClassType()) {
505
530
    CreatedValuesCount++;
506
    // FIXME: Initialize only fields that are accessed in the context that is
507
    // being analyzed.
508
530
    llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
509
530
    for (const FieldDecl *Field : getAccessibleObjectFields(Type)) {
510
100
      assert(Field != nullptr);
511
512
0
      QualType FieldType = Field->getType();
513
100
      if (Visited.contains(FieldType.getCanonicalType()))
514
2
        continue;
515
516
98
      Visited.insert(FieldType.getCanonicalType());
517
98
      if (auto *FieldValue = createValueUnlessSelfReferential(
518
98
              FieldType, Visited, Depth + 1, CreatedValuesCount))
519
98
        FieldValues.insert({Field, FieldValue});
520
98
      Visited.erase(FieldType.getCanonicalType());
521
98
    }
522
523
530
    return &takeOwnership(
524
530
        std::make_unique<StructValue>(std::move(FieldValues)));
525
530
  }
526
527
25
  return nullptr;
528
555
}
529
530
5.42k
StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
531
5.42k
  switch (SP) {
532
2.42k
  case SkipPast::None:
533
2.42k
    return Loc;
534
2.29k
  case SkipPast::Reference:
535
    // References cannot be chained so we only need to skip past one level of
536
    // indirection.
537
2.29k
    if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
538
1.56k
      return Val->getPointeeLoc();
539
736
    return Loc;
540
694
  case SkipPast::ReferenceThenPointer:
541
694
    StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
542
694
    if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
543
50
      return Val->getPointeeLoc();
544
644
    return LocPastRef;
545
5.42k
  }
546
0
  llvm_unreachable("bad SkipPast kind");
547
0
}
548
549
const StorageLocation &Environment::skip(const StorageLocation &Loc,
550
0
                                         SkipPast SP) const {
551
0
  return skip(*const_cast<StorageLocation *>(&Loc), SP);
552
0
}
553
554
401
void Environment::addToFlowCondition(BoolValue &Val) {
555
401
  DACtx->addFlowConditionConstraint(*FlowConditionToken, Val);
556
401
}
557
558
414
bool Environment::flowConditionImplies(BoolValue &Val) const {
559
414
  return DACtx->flowConditionImplies(*FlowConditionToken, Val);
560
414
}
561
562
} // namespace dataflow
563
} // namespace clang