Coverage Report

Created: 2022-07-16 07:03

/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
1.41k
                                        const llvm::DenseMap<K, V> &Map2) {
44
1.41k
  llvm::DenseMap<K, V> Result;
45
3.69k
  for (auto &Entry : Map1) {
46
3.69k
    auto It = Map2.find(Entry.first);
47
3.69k
    if (It != Map2.end() && 
Entry.second == It->second2.55k
)
48
2.55k
      Result.insert({Entry.first, Entry.second});
49
3.69k
  }
50
1.41k
  return Result;
51
1.41k
}
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
472
                                        const llvm::DenseMap<K, V> &Map2) {
44
472
  llvm::DenseMap<K, V> Result;
45
815
  for (auto &Entry : Map1) {
46
815
    auto It = Map2.find(Entry.first);
47
815
    if (It != Map2.end() && 
Entry.second == It->second807
)
48
807
      Result.insert({Entry.first, Entry.second});
49
815
  }
50
472
  return Result;
51
472
}
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
472
                                        const llvm::DenseMap<K, V> &Map2) {
44
472
  llvm::DenseMap<K, V> Result;
45
2.87k
  for (auto &Entry : Map1) {
46
2.87k
    auto It = Map2.find(Entry.first);
47
2.87k
    if (It != Map2.end() && 
Entry.second == It->second1.73k
)
48
1.73k
      Result.insert({Entry.first, Entry.second});
49
2.87k
  }
50
472
  return Result;
51
472
}
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
472
                                        const llvm::DenseMap<K, V> &Map2) {
44
472
  llvm::DenseMap<K, V> Result;
45
472
  for (auto &Entry : Map1) {
46
10
    auto It = Map2.find(Entry.first);
47
10
    if (It != Map2.end() && 
Entry.second == It->second8
)
48
8
      Result.insert({Entry.first, Entry.second});
49
10
  }
50
472
  return Result;
51
472
}
52
53
197
static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) {
54
197
  if (auto *IndVal1 = dyn_cast<ReferenceValue>(Val1)) {
55
11
    auto *IndVal2 = cast<ReferenceValue>(Val2);
56
11
    return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc();
57
11
  }
58
186
  if (auto *IndVal1 = dyn_cast<PointerValue>(Val1)) {
59
21
    auto *IndVal2 = cast<PointerValue>(Val2);
60
21
    return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
61
21
  }
62
165
  return false;
63
186
}
64
65
/// Returns true if and only if `Val1` is equivalent to `Val2`.
66
static bool equivalentValues(QualType Type, Value *Val1,
67
                             const Environment &Env1, Value *Val2,
68
                             const Environment &Env2,
69
99
                             Environment::ValueModel &Model) {
70
99
  return Val1 == Val2 || 
areEquivalentIndirectionValues(Val1, Val2)43
||
71
99
         
Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2)33
;
72
99
}
73
74
/// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
75
/// respectively, of the same type `Type`. Merging generally produces a single
76
/// value that (soundly) approximates the two inputs, although the actual
77
/// meaning depends on `Model`.
78
static Value *mergeDistinctValues(QualType Type, Value *Val1,
79
                                  const Environment &Env1, Value *Val2,
80
                                  const Environment &Env2,
81
                                  Environment &MergedEnv,
82
208
                                  Environment::ValueModel &Model) {
83
  // Join distinct boolean values preserving information about the constraints
84
  // in the respective path conditions.
85
  //
86
  // FIXME: Does not work for backedges, since the two (or more) paths will not
87
  // have mutually exclusive conditions.
88
208
  if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
89
54
    auto *Expr2 = cast<BoolValue>(Val2);
90
54
    auto &MergedVal = MergedEnv.makeAtomicBoolValue();
91
54
    MergedEnv.addToFlowCondition(MergedEnv.makeOr(
92
54
        MergedEnv.makeAnd(Env1.getFlowConditionToken(),
93
54
                          MergedEnv.makeIff(MergedVal, *Expr1)),
94
54
        MergedEnv.makeAnd(Env2.getFlowConditionToken(),
95
54
                          MergedEnv.makeIff(MergedVal, *Expr2))));
96
54
    return &MergedVal;
97
54
  }
98
99
  // FIXME: add unit tests that cover this statement.
100
154
  if (areEquivalentIndirectionValues(Val1, Val2)) {
101
2
    return Val1;
102
2
  }
103
104
  // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
105
  // returns false to avoid storing unneeded values in `DACtx`.
106
152
  if (Value *MergedVal = MergedEnv.createValue(Type))
107
152
    if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
108
152
      return MergedVal;
109
110
0
  return nullptr;
111
152
}
112
113
/// Initializes a global storage value.
114
1.20k
static void initGlobalVar(const VarDecl &D, Environment &Env) {
115
1.20k
  if (!D.hasGlobalStorage() ||
116
1.20k
      
Env.getStorageLocation(D, SkipPast::None) != nullptr57
)
117
1.15k
    return;
118
119
48
  auto &Loc = Env.createStorageLocation(D);
120
48
  Env.setStorageLocation(D, Loc);
121
48
  if (auto *Val = Env.createValue(D.getType()))
122
48
    Env.setValue(Loc, *Val);
123
48
}
124
125
/// Initializes a global storage value.
126
1.94k
static void initGlobalVar(const Decl &D, Environment &Env) {
127
1.94k
  if (auto *V = dyn_cast<VarDecl>(&D))
128
1.20k
    initGlobalVar(*V, Env);
129
1.94k
}
130
131
/// Initializes global storage values that are declared or referenced from
132
/// sub-statements of `S`.
133
// FIXME: Add support for resetting globals after function calls to enable
134
// the implementation of sound analyses.
135
5.62k
static void initGlobalVars(const Stmt &S, Environment &Env) {
136
5.62k
  for (auto *Child : S.children()) {
137
5.23k
    if (Child != nullptr)
138
5.23k
      initGlobalVars(*Child, Env);
139
5.23k
  }
140
141
5.62k
  if (auto *DS = dyn_cast<DeclStmt>(&S)) {
142
368
    if (DS->isSingleDecl()) {
143
366
      initGlobalVar(*DS->getSingleDecl(), Env);
144
366
    } else {
145
2
      for (auto *D : DS->getDeclGroup())
146
4
        initGlobalVar(*D, Env);
147
2
    }
148
5.25k
  } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
149
1.13k
    initGlobalVar(*E->getDecl(), Env);
150
4.12k
  } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
151
442
    initGlobalVar(*E->getMemberDecl(), Env);
152
442
  }
153
5.62k
}
154
155
Environment::Environment(DataflowAnalysisContext &DACtx)
156
867
    : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
157
158
Environment::Environment(const Environment &Other)
159
    : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc),
160
      ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
161
      MemberLocToStruct(Other.MemberLocToStruct),
162
6.91k
      FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
163
6.91k
}
164
165
0
Environment &Environment::operator=(const Environment &Other) {
166
0
  Environment Copy(Other);
167
0
  *this = std::move(Copy);
168
0
  return *this;
169
0
}
170
171
Environment::Environment(DataflowAnalysisContext &DACtx,
172
                         const DeclContext &DeclCtx)
173
391
    : Environment(DACtx) {
174
391
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
175
391
    assert(FuncDecl->getBody() != nullptr);
176
0
    initGlobalVars(*FuncDecl->getBody(), *this);
177
391
    for (const auto *ParamDecl : FuncDecl->parameters()) {
178
231
      assert(ParamDecl != nullptr);
179
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
180
231
      setStorageLocation(*ParamDecl, ParamLoc);
181
231
      if (Value *ParamVal = createValue(ParamDecl->getType()))
182
231
        setValue(ParamLoc, *ParamVal);
183
231
    }
184
391
  }
185
186
391
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
187
10
    auto *Parent = MethodDecl->getParent();
188
10
    assert(Parent != nullptr);
189
10
    if (Parent->isLambda())
190
3
      MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext());
191
192
10
    if (MethodDecl && 
!MethodDecl->isStatic()9
) {
193
9
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
194
      // FIXME: Add support for union types.
195
9
      if (!ThisPointeeType->isUnionType()) {
196
8
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
197
8
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
198
8
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
199
8
          setValue(ThisPointeeLoc, *ThisPointeeVal);
200
8
      }
201
9
    }
202
10
  }
203
391
}
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
173
391
    : Environment(DACtx) {
174
391
  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
175
391
    assert(FuncDecl->getBody() != nullptr);
176
0
    initGlobalVars(*FuncDecl->getBody(), *this);
177
391
    for (const auto *ParamDecl : FuncDecl->parameters()) {
178
231
      assert(ParamDecl != nullptr);
179
0
      auto &ParamLoc = createStorageLocation(*ParamDecl);
180
231
      setStorageLocation(*ParamDecl, ParamLoc);
181
231
      if (Value *ParamVal = createValue(ParamDecl->getType()))
182
231
        setValue(ParamLoc, *ParamVal);
183
231
    }
184
391
  }
185
186
391
  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
187
10
    auto *Parent = MethodDecl->getParent();
188
10
    assert(Parent != nullptr);
189
10
    if (Parent->isLambda())
190
3
      MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext());
191
192
10
    if (MethodDecl && 
!MethodDecl->isStatic()9
) {
193
9
      QualType ThisPointeeType = MethodDecl->getThisObjectType();
194
      // FIXME: Add support for union types.
195
9
      if (!ThisPointeeType->isUnionType()) {
196
8
        auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
197
8
        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
198
8
        if (Value *ThisPointeeVal = createValue(ThisPointeeType))
199
8
          setValue(ThisPointeeLoc, *ThisPointeeVal);
200
8
      }
201
9
    }
202
10
  }
203
391
}
204
205
bool Environment::equivalentTo(const Environment &Other,
206
50
                               Environment::ValueModel &Model) const {
207
50
  assert(DACtx == Other.DACtx);
208
209
50
  if (DeclToLoc != Other.DeclToLoc)
210
0
    return false;
211
212
50
  if (ExprToLoc != Other.ExprToLoc)
213
15
    return false;
214
215
  // Compare the contents for the intersection of their domains.
216
100
  
for (auto &Entry : LocToVal)35
{
217
100
    const StorageLocation *Loc = Entry.first;
218
100
    assert(Loc != nullptr);
219
220
0
    Value *Val = Entry.second;
221
100
    assert(Val != nullptr);
222
223
0
    auto It = Other.LocToVal.find(Loc);
224
100
    if (It == Other.LocToVal.end())
225
1
      continue;
226
99
    assert(It->second != nullptr);
227
228
99
    if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
229
12
      return false;
230
99
  }
231
232
23
  return true;
233
35
}
234
235
LatticeJoinEffect Environment::join(const Environment &Other,
236
472
                                    Environment::ValueModel &Model) {
237
472
  assert(DACtx == Other.DACtx);
238
239
0
  auto Effect = LatticeJoinEffect::Unchanged;
240
241
472
  Environment JoinedEnv(*DACtx);
242
243
472
  JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
244
472
  if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
245
8
    Effect = LatticeJoinEffect::Changed;
246
247
472
  JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
248
472
  if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
249
269
    Effect = LatticeJoinEffect::Changed;
250
251
472
  JoinedEnv.MemberLocToStruct =
252
472
      intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
253
472
  if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
254
2
    Effect = LatticeJoinEffect::Changed;
255
256
  // FIXME: set `Effect` as needed.
257
472
  JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
258
472
      *FlowConditionToken, *Other.FlowConditionToken);
259
260
3.07k
  for (auto &Entry : LocToVal) {
261
3.07k
    const StorageLocation *Loc = Entry.first;
262
3.07k
    assert(Loc != nullptr);
263
264
0
    Value *Val = Entry.second;
265
3.07k
    assert(Val != nullptr);
266
267
0
    auto It = Other.LocToVal.find(Loc);
268
3.07k
    if (It == Other.LocToVal.end())
269
843
      continue;
270
2.23k
    assert(It->second != nullptr);
271
272
2.23k
    if (Val == It->second) {
273
2.02k
      JoinedEnv.LocToVal.insert({Loc, Val});
274
2.02k
      continue;
275
2.02k
    }
276
277
208
    if (Value *MergedVal = mergeDistinctValues(
278
208
            Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model))
279
208
      JoinedEnv.LocToVal.insert({Loc, MergedVal});
280
208
  }
281
472
  if (LocToVal.size() != JoinedEnv.LocToVal.size())
282
271
    Effect = LatticeJoinEffect::Changed;
283
284
472
  *this = std::move(JoinedEnv);
285
286
472
  return Effect;
287
472
}
288
289
567
StorageLocation &Environment::createStorageLocation(QualType Type) {
290
567
  return DACtx->getStableStorageLocation(Type);
291
567
}
292
293
1.00k
StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
294
  // Evaluated declarations are always assigned the same storage locations to
295
  // ensure that the environment stabilizes across loop iterations. Storage
296
  // locations for evaluated declarations are stored in the analysis context.
297
1.00k
  return DACtx->getStableStorageLocation(D);
298
1.00k
}
299
300
3.53k
StorageLocation &Environment::createStorageLocation(const Expr &E) {
301
  // Evaluated expressions are always assigned the same storage locations to
302
  // ensure that the environment stabilizes across loop iterations. Storage
303
  // locations for evaluated expressions are stored in the analysis context.
304
3.53k
  return DACtx->getStableStorageLocation(E);
305
3.53k
}
306
307
1.02k
void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
308
1.02k
  assert(DeclToLoc.find(&D) == DeclToLoc.end());
309
0
  DeclToLoc[&D] = &Loc;
310
1.02k
}
311
312
StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
313
2.64k
                                                 SkipPast SP) const {
314
2.64k
  auto It = DeclToLoc.find(&D);
315
2.64k
  return It == DeclToLoc.end() ? 
nullptr697
:
&skip(*It->second, SP)1.94k
;
316
2.64k
}
317
318
5.19k
void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
319
5.19k
  const Expr &CanonE = ignoreCFGOmittedNodes(E);
320
5.19k
  assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
321
0
  ExprToLoc[&CanonE] = &Loc;
322
5.19k
}
323
324
StorageLocation *Environment::getStorageLocation(const Expr &E,
325
8.60k
                                                 SkipPast SP) const {
326
  // FIXME: Add a test with parens.
327
8.60k
  auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
328
8.60k
  return It == ExprToLoc.end() ? 
nullptr1.50k
:
&skip(*It->second, SP)7.09k
;
329
8.60k
}
330
331
48
StorageLocation *Environment::getThisPointeeStorageLocation() const {
332
48
  return DACtx->getThisPointeeStorageLocation();
333
48
}
334
335
20
PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
336
20
  return DACtx->getOrCreateNullPointerValue(PointeeType);
337
20
}
338
339
6.04k
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
340
6.04k
  LocToVal[&Loc] = &Val;
341
342
6.04k
  if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
343
2.14k
    auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
344
345
2.14k
    const QualType Type = AggregateLoc.getType();
346
2.14k
    assert(Type->isStructureOrClassType());
347
348
218
    for (const FieldDecl *Field : getObjectFields(Type)) {
349
218
      assert(Field != nullptr);
350
0
      StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
351
218
      MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
352
218
      if (auto *FieldVal = StructVal->getChild(*Field))
353
216
        setValue(FieldLoc, *FieldVal);
354
218
    }
355
2.14k
  }
356
357
0
  auto IT = MemberLocToStruct.find(&Loc);
358
6.04k
  if (IT != MemberLocToStruct.end()) {
359
    // `Loc` is the location of a struct member so we need to also update the
360
    // value of the member in the corresponding `StructValue`.
361
362
232
    assert(IT->second.first != nullptr);
363
0
    StructValue &StructVal = *IT->second.first;
364
365
232
    assert(IT->second.second != nullptr);
366
0
    const ValueDecl &Member = *IT->second.second;
367
368
232
    StructVal.setChild(Member, Val);
369
232
  }
370
6.04k
}
371
372
12.1k
Value *Environment::getValue(const StorageLocation &Loc) const {
373
12.1k
  auto It = LocToVal.find(&Loc);
374
12.1k
  return It == LocToVal.end() ? 
nullptr223
:
It->second11.8k
;
375
12.1k
}
376
377
174
Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
378
174
  auto *Loc = getStorageLocation(D, SP);
379
174
  if (Loc == nullptr)
380
0
    return nullptr;
381
174
  return getValue(*Loc);
382
174
}
383
384
4.89k
Value *Environment::getValue(const Expr &E, SkipPast SP) const {
385
4.89k
  auto *Loc = getStorageLocation(E, SP);
386
4.89k
  if (Loc == nullptr)
387
240
    return nullptr;
388
4.65k
  return getValue(*Loc);
389
4.89k
}
390
391
1.68k
Value *Environment::createValue(QualType Type) {
392
1.68k
  llvm::DenseSet<QualType> Visited;
393
1.68k
  int CreatedValuesCount = 0;
394
1.68k
  Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
395
1.68k
                                                CreatedValuesCount);
396
1.68k
  if (CreatedValuesCount > MaxCompositeValueSize) {
397
0
    llvm::errs() << "Attempting to initialize a huge value of type: " << Type
398
0
                 << '\n';
399
0
  }
400
1.68k
  return Val;
401
1.68k
}
402
403
Value *Environment::createValueUnlessSelfReferential(
404
    QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
405
1.91k
    int &CreatedValuesCount) {
406
1.91k
  assert(!Type.isNull());
407
408
  // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
409
1.91k
  if ((Depth > 1 && 
CreatedValuesCount > MaxCompositeValueSize31
) ||
410
1.91k
      Depth > MaxCompositeValueDepth)
411
0
    return nullptr;
412
413
1.91k
  if (Type->isBooleanType()) {
414
120
    CreatedValuesCount++;
415
120
    return &makeAtomicBoolValue();
416
120
  }
417
418
1.79k
  if (Type->isIntegerType()) {
419
611
    CreatedValuesCount++;
420
611
    return &takeOwnership(std::make_unique<IntegerValue>());
421
611
  }
422
423
1.18k
  if (Type->isReferenceType()) {
424
29
    CreatedValuesCount++;
425
29
    QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
426
29
    auto &PointeeLoc = createStorageLocation(PointeeType);
427
428
29
    if (Visited.insert(PointeeType.getCanonicalType()).second) {
429
25
      Value *PointeeVal = createValueUnlessSelfReferential(
430
25
          PointeeType, Visited, Depth, CreatedValuesCount);
431
25
      Visited.erase(PointeeType.getCanonicalType());
432
433
25
      if (PointeeVal != nullptr)
434
24
        setValue(PointeeLoc, *PointeeVal);
435
25
    }
436
437
29
    return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
438
29
  }
439
440
1.15k
  if (Type->isPointerType()) {
441
87
    CreatedValuesCount++;
442
87
    QualType PointeeType = Type->castAs<PointerType>()->getPointeeType();
443
87
    auto &PointeeLoc = createStorageLocation(PointeeType);
444
445
87
    if (Visited.insert(PointeeType.getCanonicalType()).second) {
446
83
      Value *PointeeVal = createValueUnlessSelfReferential(
447
83
          PointeeType, Visited, Depth, CreatedValuesCount);
448
83
      Visited.erase(PointeeType.getCanonicalType());
449
450
83
      if (PointeeVal != nullptr)
451
82
        setValue(PointeeLoc, *PointeeVal);
452
83
    }
453
454
87
    return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
455
87
  }
456
457
1.07k
  if (Type->isStructureOrClassType()) {
458
1.03k
    CreatedValuesCount++;
459
    // FIXME: Initialize only fields that are accessed in the context that is
460
    // being analyzed.
461
1.03k
    llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
462
1.03k
    for (const FieldDecl *Field : getObjectFields(Type)) {
463
130
      assert(Field != nullptr);
464
465
0
      QualType FieldType = Field->getType();
466
130
      if (Visited.contains(FieldType.getCanonicalType()))
467
2
        continue;
468
469
128
      Visited.insert(FieldType.getCanonicalType());
470
128
      if (auto *FieldValue = createValueUnlessSelfReferential(
471
128
              FieldType, Visited, Depth + 1, CreatedValuesCount))
472
128
        FieldValues.insert({Field, FieldValue});
473
128
      Visited.erase(FieldType.getCanonicalType());
474
128
    }
475
476
1.03k
    return &takeOwnership(
477
1.03k
        std::make_unique<StructValue>(std::move(FieldValues)));
478
1.03k
  }
479
480
32
  return nullptr;
481
1.07k
}
482
483
10.5k
StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
484
10.5k
  switch (SP) {
485
4.28k
  case SkipPast::None:
486
4.28k
    return Loc;
487
4.75k
  case SkipPast::Reference:
488
    // References cannot be chained so we only need to skip past one level of
489
    // indirection.
490
4.75k
    if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
491
2.98k
      return Val->getReferentLoc();
492
1.77k
    return Loc;
493
1.51k
  case SkipPast::ReferenceThenPointer:
494
1.51k
    StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
495
1.51k
    if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
496
114
      return Val->getPointeeLoc();
497
1.40k
    return LocPastRef;
498
10.5k
  }
499
0
  llvm_unreachable("bad SkipPast kind");
500
0
}
501
502
const StorageLocation &Environment::skip(const StorageLocation &Loc,
503
0
                                         SkipPast SP) const {
504
0
  return skip(*const_cast<StorageLocation *>(&Loc), SP);
505
0
}
506
507
1.05k
void Environment::addToFlowCondition(BoolValue &Val) {
508
1.05k
  DACtx->addFlowConditionConstraint(*FlowConditionToken, Val);
509
1.05k
}
510
511
640
bool Environment::flowConditionImplies(BoolValue &Val) const {
512
640
  return DACtx->flowConditionImplies(*FlowConditionToken, Val);
513
640
}
514
515
} // namespace dataflow
516
} // namespace clang