Coverage Report

Created: 2022-07-16 07:03

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that
10
//  encompass the state of a program and stores context that is used during
11
//  dataflow analysis.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
16
#include "clang/AST/ExprCXX.h"
17
#include "clang/Analysis/FlowSensitive/Value.h"
18
#include <cassert>
19
#include <memory>
20
#include <utility>
21
22
namespace clang {
23
namespace dataflow {
24
25
StorageLocation &
26
3.10k
DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
27
3.10k
  if (!Type.isNull() &&
28
3.10k
      
(3.10k
Type->isStructureOrClassType()3.10k
||
Type->isUnionType()1.55k
)) {
29
    // FIXME: Explore options to avoid eager initialization of fields as some of
30
    // them might not be needed for a particular analysis.
31
1.55k
    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
32
1.55k
    for (const FieldDecl *Field : getObjectFields(Type))
33
193
      FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
34
1.55k
    return takeOwnership(
35
1.55k
        std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
36
1.55k
  }
37
1.55k
  return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
38
3.10k
}
39
40
StorageLocation &
41
1.00k
DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
42
1.00k
  if (auto *Loc = getStorageLocation(D))
43
366
    return *Loc;
44
642
  auto &Loc = getStableStorageLocation(D.getType());
45
642
  setStorageLocation(D, Loc);
46
642
  return Loc;
47
1.00k
}
48
49
StorageLocation &
50
3.53k
DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
51
3.53k
  if (auto *Loc = getStorageLocation(E))
52
1.83k
    return *Loc;
53
1.69k
  auto &Loc = getStableStorageLocation(E.getType());
54
1.69k
  setStorageLocation(E, Loc);
55
1.69k
  return Loc;
56
3.53k
}
57
58
PointerValue &
59
20
DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
60
20
  auto CanonicalPointeeType =
61
20
      PointeeType.isNull() ? 
PointeeType2
:
PointeeType.getCanonicalType()18
;
62
20
  auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
63
20
  if (Res.second) {
64
9
    auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
65
9
    Res.first->second =
66
9
        &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
67
9
  }
68
20
  return *Res.first->second;
69
20
}
70
71
static std::pair<BoolValue *, BoolValue *>
72
16.8k
makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
73
16.8k
  auto Res = std::make_pair(&LHS, &RHS);
74
16.8k
  if (&RHS < &LHS)
75
10.0k
    std::swap(Res.first, Res.second);
76
16.8k
  return Res;
77
16.8k
}
78
79
BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS,
80
6.26k
                                                           BoolValue &RHS) {
81
6.26k
  if (&LHS == &RHS)
82
2
    return LHS;
83
84
6.26k
  auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
85
6.26k
                                         nullptr);
86
6.26k
  if (Res.second)
87
2.84k
    Res.first->second =
88
2.84k
        &takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS));
89
6.26k
  return *Res.first->second;
90
6.26k
}
91
92
BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS,
93
10.5k
                                                           BoolValue &RHS) {
94
10.5k
  if (&LHS == &RHS)
95
3
    return LHS;
96
97
10.5k
  auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
98
10.5k
                                         nullptr);
99
10.5k
  if (Res.second)
100
4.68k
    Res.first->second =
101
4.68k
        &takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS));
102
10.5k
  return *Res.first->second;
103
10.5k
}
104
105
12.1k
BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) {
106
12.1k
  auto Res = NegationVals.try_emplace(&Val, nullptr);
107
12.1k
  if (Res.second)
108
3.69k
    Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val));
109
12.1k
  return *Res.first->second;
110
12.1k
}
111
112
BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS,
113
10.0k
                                                           BoolValue &RHS) {
114
10.0k
  return &LHS == &RHS ? 
getBoolLiteralValue(true)1
115
10.0k
                      : 
getOrCreateDisjunction(getOrCreateNegation(LHS), RHS)10.0k
;
116
10.0k
}
117
118
BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS,
119
4.99k
                                                   BoolValue &RHS) {
120
4.99k
  return &LHS == &RHS
121
4.99k
             ? 
getBoolLiteralValue(true)8
122
4.99k
             : getOrCreateConjunction(getOrCreateImplication(LHS, RHS),
123
4.98k
                                      getOrCreateImplication(RHS, LHS));
124
4.99k
}
125
126
8.27k
AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() {
127
8.27k
  return createAtomicBoolValue();
128
8.27k
}
129
130
void DataflowAnalysisContext::addFlowConditionConstraint(
131
8.46k
    AtomicBoolValue &Token, BoolValue &Constraint) {
132
8.46k
  auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint);
133
8.46k
  if (!Res.second) {
134
1.05k
    Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint);
135
1.05k
  }
136
8.46k
}
137
138
AtomicBoolValue &
139
6.91k
DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) {
140
6.91k
  auto &ForkToken = makeFlowConditionToken();
141
6.91k
  FlowConditionDeps[&ForkToken].insert(&Token);
142
6.91k
  addFlowConditionConstraint(ForkToken, Token);
143
6.91k
  return ForkToken;
144
6.91k
}
145
146
AtomicBoolValue &
147
DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken,
148
474
                                            AtomicBoolValue &SecondToken) {
149
474
  auto &Token = makeFlowConditionToken();
150
474
  FlowConditionDeps[&Token].insert(&FirstToken);
151
474
  FlowConditionDeps[&Token].insert(&SecondToken);
152
474
  addFlowConditionConstraint(Token,
153
474
                             getOrCreateDisjunction(FirstToken, SecondToken));
154
474
  return Token;
155
474
}
156
157
Solver::Result
158
688
DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) {
159
688
  Constraints.insert(&getBoolLiteralValue(true));
160
688
  Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false)));
161
688
  return S->solve(std::move(Constraints));
162
688
}
163
164
bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token,
165
648
                                                   BoolValue &Val) {
166
  // Returns true if and only if truth assignment of the flow condition implies
167
  // that `Val` is also true. We prove whether or not this property holds by
168
  // reducing the problem to satisfiability checking. In other words, we attempt
169
  // to show that assuming `Val` is false makes the constraints induced by the
170
  // flow condition unsatisfiable.
171
648
  llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)};
172
648
  llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
173
648
  addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
174
648
  return isUnsatisfiable(std::move(Constraints));
175
648
}
176
177
5
bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) {
178
  // Returns true if and only if we cannot prove that the flow condition can
179
  // ever be false.
180
5
  llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)};
181
5
  llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
182
5
  addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
183
5
  return isUnsatisfiable(std::move(Constraints));
184
5
}
185
186
bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1,
187
35
                                                   BoolValue &Val2) {
188
35
  llvm::DenseSet<BoolValue *> Constraints = {
189
35
      &getOrCreateNegation(getOrCreateIff(Val1, Val2))};
190
35
  return isUnsatisfiable(Constraints);
191
35
}
192
193
void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
194
    AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
195
5.67k
    llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) {
196
5.67k
  auto Res = VisitedTokens.insert(&Token);
197
5.67k
  if (!Res.second)
198
207
    return;
199
200
5.47k
  auto ConstraintsIT = FlowConditionConstraints.find(&Token);
201
5.47k
  if (ConstraintsIT == FlowConditionConstraints.end()) {
202
640
    Constraints.insert(&Token);
203
4.83k
  } else {
204
    // Bind flow condition token via `iff` to its set of constraints:
205
    // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints
206
4.83k
    Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second));
207
4.83k
  }
208
209
5.47k
  auto DepsIT = FlowConditionDeps.find(&Token);
210
5.47k
  if (DepsIT != FlowConditionDeps.end()) {
211
5.02k
    for (AtomicBoolValue *DepToken : DepsIT->second) {
212
5.02k
      addTransitiveFlowConditionConstraints(*DepToken, Constraints,
213
5.02k
                                            VisitedTokens);
214
5.02k
    }
215
4.81k
  }
216
5.47k
}
217
218
BoolValue &DataflowAnalysisContext::substituteBoolValue(
219
    BoolValue &Val,
220
90
    llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
221
90
  auto IT = SubstitutionsCache.find(&Val);
222
90
  if (IT != SubstitutionsCache.end()) {
223
    // Return memoized result of substituting this boolean value.
224
37
    return *IT->second;
225
37
  }
226
227
  // Handle substitution on the boolean value (and its subvalues), saving the
228
  // result into `SubstitutionsCache`.
229
53
  BoolValue *Result;
230
53
  switch (Val.getKind()) {
231
25
  case Value::Kind::AtomicBool: {
232
25
    Result = &Val;
233
25
    break;
234
0
  }
235
2
  case Value::Kind::Negation: {
236
2
    auto &Negation = *cast<NegationValue>(&Val);
237
2
    auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache);
238
2
    Result = &getOrCreateNegation(Sub);
239
2
    break;
240
0
  }
241
8
  case Value::Kind::Disjunction: {
242
8
    auto &Disjunct = *cast<DisjunctionValue>(&Val);
243
8
    auto &LeftSub =
244
8
        substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache);
245
8
    auto &RightSub =
246
8
        substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache);
247
8
    Result = &getOrCreateDisjunction(LeftSub, RightSub);
248
8
    break;
249
0
  }
250
18
  case Value::Kind::Conjunction: {
251
18
    auto &Conjunct = *cast<ConjunctionValue>(&Val);
252
18
    auto &LeftSub =
253
18
        substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache);
254
18
    auto &RightSub =
255
18
        substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache);
256
18
    Result = &getOrCreateConjunction(LeftSub, RightSub);
257
18
    break;
258
0
  }
259
0
  default:
260
0
    llvm_unreachable("Unhandled Value Kind");
261
53
  }
262
53
  SubstitutionsCache[&Val] = Result;
263
53
  return *Result;
264
53
}
265
266
BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition(
267
    AtomicBoolValue &Token,
268
19
    llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {
269
19
  assert(
270
19
      Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() &&
271
19
      Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() &&
272
19
      "Do not substitute true/false boolean literals");
273
0
  llvm::DenseMap<BoolValue *, BoolValue *> SubstitutionsCache(
274
19
      Substitutions.begin(), Substitutions.end());
275
19
  return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache);
276
19
}
277
278
BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache(
279
    AtomicBoolValue &Token,
280
36
    llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
281
36
  auto ConstraintsIT = FlowConditionConstraints.find(&Token);
282
36
  if (ConstraintsIT == FlowConditionConstraints.end()) {
283
0
    return getBoolLiteralValue(true);
284
0
  }
285
36
  auto DepsIT = FlowConditionDeps.find(&Token);
286
36
  if (DepsIT != FlowConditionDeps.end()) {
287
17
    for (AtomicBoolValue *DepToken : DepsIT->second) {
288
17
      auto &NewDep = buildAndSubstituteFlowConditionWithCache(
289
17
          *DepToken, SubstitutionsCache);
290
17
      SubstitutionsCache[DepToken] = &NewDep;
291
17
    }
292
11
  }
293
36
  return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache);
294
36
}
295
296
} // namespace dataflow
297
} // namespace clang
298
299
using namespace clang;
300
301
19.2k
const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
302
19.2k
  const Expr *Current = &E;
303
19.2k
  if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
304
326
    Current = EWC->getSubExpr();
305
326
    assert(Current != nullptr);
306
326
  }
307
0
  Current = Current->IgnoreParens();
308
19.2k
  assert(Current != nullptr);
309
0
  return *Current;
310
19.2k
}
311
312
196
const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
313
196
  if (auto *E = dyn_cast<Expr>(&S))
314
196
    return ignoreCFGOmittedNodes(*E);
315
0
  return S;
316
196
}
317
318
// FIXME: Does not precisely handle non-virtual diamond inheritance. A single
319
// field decl will be modeled for all instances of the inherited field.
320
static void
321
getFieldsFromClassHierarchy(QualType Type,
322
6.91k
                            llvm::DenseSet<const FieldDecl *> &Fields) {
323
6.91k
  if (Type->isIncompleteType() || Type->isDependentType() ||
324
6.91k
      !Type->isRecordType())
325
0
    return;
326
327
6.91k
  for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
328
541
    Fields.insert(Field);
329
6.91k
  if (auto *CXXRecord = Type->getAsCXXRecordDecl())
330
6.91k
    for (const CXXBaseSpecifier &Base : CXXRecord->bases())
331
2.17k
      getFieldsFromClassHierarchy(Base.getType(), Fields);
332
6.91k
}
333
334
/// Gets the set of all fields in the type.
335
llvm::DenseSet<const FieldDecl *>
336
4.73k
clang::dataflow::getObjectFields(QualType Type) {
337
4.73k
  llvm::DenseSet<const FieldDecl *> Fields;
338
4.73k
  getFieldsFromClassHierarchy(Type, Fields);
339
4.73k
  return Fields;
340
4.73k
}