Coverage Report

Created: 2022-05-17 06:19

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h
Line
Count
Source (jump to first uncovered line)
1
//===-- DataflowAnalysisContext.h -------------------------------*- 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
#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
16
#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
17
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/Expr.h"
20
#include "clang/Analysis/FlowSensitive/Solver.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 <cassert>
26
#include <memory>
27
#include <type_traits>
28
#include <utility>
29
#include <vector>
30
31
namespace clang {
32
namespace dataflow {
33
34
/// Skip past nodes that the CFG does not emit. These nodes are invisible to
35
/// flow-sensitive analysis, and should be ignored as they will effectively not
36
/// exist.
37
///
38
///   * `ParenExpr` - The CFG takes the operator precedence into account, but
39
///   otherwise omits the node afterwards.
40
///
41
///   * `ExprWithCleanups` - The CFG will generate the appropriate calls to
42
///   destructors and then omit the node.
43
///
44
const Expr &ignoreCFGOmittedNodes(const Expr &E);
45
const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
46
47
/// Owns objects that encompass the state of a program and stores context that
48
/// is used during dataflow analysis.
49
class DataflowAnalysisContext {
50
public:
51
  /// Constructs a dataflow analysis context.
52
  ///
53
  /// Requirements:
54
  ///
55
  ///  `S` must not be null.
56
  DataflowAnalysisContext(std::unique_ptr<Solver> S)
57
      : S(std::move(S)), TrueVal(createAtomicBoolValue()),
58
        FalseVal(createAtomicBoolValue()) {
59
    assert(this->S != nullptr);
60
  }
61
62
  /// Takes ownership of `Loc` and returns a reference to it.
63
  ///
64
  /// Requirements:
65
  ///
66
  ///  `Loc` must not be null.
67
  template <typename T>
68
  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
69
1.66k
  takeOwnership(std::unique_ptr<T> Loc) {
70
1.66k
    assert(Loc != nullptr);
71
0
    Locs.push_back(std::move(Loc));
72
1.66k
    return *cast<T>(Locs.back().get());
73
1.66k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::StorageLocation, clang::dataflow::AggregateStorageLocation>::value, clang::dataflow::AggregateStorageLocation&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::AggregateStorageLocation>(std::__1::unique_ptr<clang::dataflow::AggregateStorageLocation, std::__1::default_delete<clang::dataflow::AggregateStorageLocation> >)
Line
Count
Source
69
864
  takeOwnership(std::unique_ptr<T> Loc) {
70
864
    assert(Loc != nullptr);
71
0
    Locs.push_back(std::move(Loc));
72
864
    return *cast<T>(Locs.back().get());
73
864
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::StorageLocation, clang::dataflow::ScalarStorageLocation>::value, clang::dataflow::ScalarStorageLocation&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ScalarStorageLocation>(std::__1::unique_ptr<clang::dataflow::ScalarStorageLocation, std::__1::default_delete<clang::dataflow::ScalarStorageLocation> >)
Line
Count
Source
69
799
  takeOwnership(std::unique_ptr<T> Loc) {
70
799
    assert(Loc != nullptr);
71
0
    Locs.push_back(std::move(Loc));
72
799
    return *cast<T>(Locs.back().get());
73
799
  }
74
75
  /// Takes ownership of `Val` and returns a reference to it.
76
  ///
77
  /// Requirements:
78
  ///
79
  ///  `Val` must not be null.
80
  template <typename T>
81
  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
82
789k
  takeOwnership(std::unique_ptr<T> Val) {
83
789k
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
789k
    return *cast<T>(Vals.back().get());
86
789k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::AtomicBoolValue>::value, clang::dataflow::AtomicBoolValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::AtomicBoolValue>(std::__1::unique_ptr<clang::dataflow::AtomicBoolValue, std::__1::default_delete<clang::dataflow::AtomicBoolValue> >)
Line
Count
Source
82
202k
  takeOwnership(std::unique_ptr<T> Val) {
83
202k
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
202k
    return *cast<T>(Vals.back().get());
86
202k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ConjunctionValue>::value, clang::dataflow::ConjunctionValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ConjunctionValue>(std::__1::unique_ptr<clang::dataflow::ConjunctionValue, std::__1::default_delete<clang::dataflow::ConjunctionValue> >)
Line
Count
Source
82
60
  takeOwnership(std::unique_ptr<T> Val) {
83
60
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
60
    return *cast<T>(Vals.back().get());
86
60
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::DisjunctionValue>::value, clang::dataflow::DisjunctionValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::DisjunctionValue>(std::__1::unique_ptr<clang::dataflow::DisjunctionValue, std::__1::default_delete<clang::dataflow::DisjunctionValue> >)
Line
Count
Source
82
382k
  takeOwnership(std::unique_ptr<T> Val) {
83
382k
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
382k
    return *cast<T>(Vals.back().get());
86
382k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::NegationValue>::value, clang::dataflow::NegationValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::NegationValue>(std::__1::unique_ptr<clang::dataflow::NegationValue, std::__1::default_delete<clang::dataflow::NegationValue> >)
Line
Count
Source
82
202k
  takeOwnership(std::unique_ptr<T> Val) {
83
202k
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
202k
    return *cast<T>(Vals.back().get());
86
202k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::IntegerValue>::value, clang::dataflow::IntegerValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::IntegerValue>(std::__1::unique_ptr<clang::dataflow::IntegerValue, std::__1::default_delete<clang::dataflow::IntegerValue> >)
Line
Count
Source
82
210
  takeOwnership(std::unique_ptr<T> Val) {
83
210
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
210
    return *cast<T>(Vals.back().get());
86
210
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::ReferenceValue>::value, clang::dataflow::ReferenceValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::ReferenceValue>(std::__1::unique_ptr<clang::dataflow::ReferenceValue, std::__1::default_delete<clang::dataflow::ReferenceValue> >)
Line
Count
Source
82
1.07k
  takeOwnership(std::unique_ptr<T> Val) {
83
1.07k
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
1.07k
    return *cast<T>(Vals.back().get());
86
1.07k
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::PointerValue>::value, clang::dataflow::PointerValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::PointerValue>(std::__1::unique_ptr<clang::dataflow::PointerValue, std::__1::default_delete<clang::dataflow::PointerValue> >)
Line
Count
Source
82
58
  takeOwnership(std::unique_ptr<T> Val) {
83
58
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
58
    return *cast<T>(Vals.back().get());
86
58
  }
std::__1::enable_if<std::is_base_of<clang::dataflow::Value, clang::dataflow::StructValue>::value, clang::dataflow::StructValue&>::type clang::dataflow::DataflowAnalysisContext::takeOwnership<clang::dataflow::StructValue>(std::__1::unique_ptr<clang::dataflow::StructValue, std::__1::default_delete<clang::dataflow::StructValue> >)
Line
Count
Source
82
818
  takeOwnership(std::unique_ptr<T> Val) {
83
818
    assert(Val != nullptr);
84
0
    Vals.push_back(std::move(Val));
85
818
    return *cast<T>(Vals.back().get());
86
818
  }
87
88
  /// Assigns `Loc` as the storage location of `D`.
89
  ///
90
  /// Requirements:
91
  ///
92
  ///  `D` must not be assigned a storage location.
93
471
  void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
94
471
    assert(DeclToLoc.find(&D) == DeclToLoc.end());
95
0
    DeclToLoc[&D] = &Loc;
96
471
  }
97
98
  /// Returns the storage location assigned to `D` or null if `D` has no
99
  /// assigned storage location.
100
761
  StorageLocation *getStorageLocation(const ValueDecl &D) const {
101
761
    auto It = DeclToLoc.find(&D);
102
761
    return It == DeclToLoc.end() ? 
nullptr471
:
It->second290
;
103
761
  }
104
105
  /// Assigns `Loc` as the storage location of `E`.
106
  ///
107
  /// Requirements:
108
  ///
109
  ///  `E` must not be assigned a storage location.
110
1.00k
  void setStorageLocation(const Expr &E, StorageLocation &Loc) {
111
1.00k
    const Expr &CanonE = ignoreCFGOmittedNodes(E);
112
1.00k
    assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
113
0
    ExprToLoc[&CanonE] = &Loc;
114
1.00k
  }
115
116
  /// Returns the storage location assigned to `E` or null if `E` has no
117
  /// assigned storage location.
118
2.04k
  StorageLocation *getStorageLocation(const Expr &E) const {
119
2.04k
    auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
120
2.04k
    return It == ExprToLoc.end() ? 
nullptr1.00k
:
It->second1.03k
;
121
2.04k
  }
122
123
  /// Assigns `Loc` as the storage location of the `this` pointee.
124
  ///
125
  /// Requirements:
126
  ///
127
  ///  The `this` pointee must not be assigned a storage location.
128
5
  void setThisPointeeStorageLocation(StorageLocation &Loc) {
129
5
    assert(ThisPointeeLoc == nullptr);
130
0
    ThisPointeeLoc = &Loc;
131
5
  }
132
133
  /// Returns the storage location assigned to the `this` pointee or null if the
134
  /// `this` pointee has no assigned storage location.
135
37
  StorageLocation *getThisPointeeStorageLocation() const {
136
37
    return ThisPointeeLoc;
137
37
  }
138
139
  /// Returns a symbolic boolean value that models a boolean literal equal to
140
  /// `Value`.
141
1.20k
  AtomicBoolValue &getBoolLiteralValue(bool Value) const {
142
1.20k
    return Value ? 
TrueVal671
:
FalseVal530
;
143
1.20k
  }
144
145
  /// Creates an atomic boolean value.
146
202k
  AtomicBoolValue &createAtomicBoolValue() {
147
202k
    return takeOwnership(std::make_unique<AtomicBoolValue>());
148
202k
  }
149
150
  /// Returns a boolean value that represents the conjunction of `LHS` and
151
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
152
  /// order, will return the same result. If the given boolean values represent
153
  /// the same value, the result will be the value itself.
154
  BoolValue &getOrCreateConjunctionValue(BoolValue &LHS, BoolValue &RHS);
155
156
  /// Returns a boolean value that represents the disjunction of `LHS` and
157
  /// `RHS`. Subsequent calls with the same arguments, regardless of their
158
  /// order, will return the same result. If the given boolean values represent
159
  /// the same value, the result will be the value itself.
160
  BoolValue &getOrCreateDisjunctionValue(BoolValue &LHS, BoolValue &RHS);
161
162
  /// Returns a boolean value that represents the negation of `Val`. Subsequent
163
  /// calls with the same argument will return the same result.
164
  BoolValue &getOrCreateNegationValue(BoolValue &Val);
165
166
  /// Creates a fresh flow condition and returns a token that identifies it. The
167
  /// token can be used to perform various operations on the flow condition such
168
  /// as adding constraints to it, forking it, joining it with another flow
169
  /// condition, or checking implications.
170
  AtomicBoolValue &makeFlowConditionToken();
171
172
  /// Adds `Constraint` to the flow condition identified by `Token`.
173
  void addFlowConditionConstraint(AtomicBoolValue &Token,
174
                                  BoolValue &Constraint);
175
176
  /// Creates a new flow condition with the same constraints as the flow
177
  /// condition identified by `Token` and returns its token.
178
  AtomicBoolValue &forkFlowCondition(AtomicBoolValue &Token);
179
180
  /// Creates a new flow condition that represents the disjunction of the flow
181
  /// conditions identified by `FirstToken` and `SecondToken`, and returns its
182
  /// token.
183
  AtomicBoolValue &joinFlowConditions(AtomicBoolValue &FirstToken,
184
                                      AtomicBoolValue &SecondToken);
185
186
  /// Returns true if and only if the constraints of the flow condition
187
  /// identified by `Token` imply that `Val` is true.
188
  bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val);
189
190
  /// Returns true if and only if the constraints of the flow condition
191
  /// identified by `Token` are always true.
192
  bool flowConditionIsTautology(AtomicBoolValue &Token);
193
194
private:
195
  /// Adds all constraints of the flow condition identified by `Token` and all
196
  /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used
197
  /// to track tokens of flow conditions that were already visited by recursive
198
  /// calls.
199
  void addTransitiveFlowConditionConstraints(
200
      AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
201
      llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) const;
202
203
  std::unique_ptr<Solver> S;
204
205
  // Storage for the state of a program.
206
  std::vector<std::unique_ptr<StorageLocation>> Locs;
207
  std::vector<std::unique_ptr<Value>> Vals;
208
209
  // Maps from program declarations and statements to storage locations that are
210
  // assigned to them. These assignments are global (aggregated across all basic
211
  // blocks) and are used to produce stable storage locations when the same
212
  // basic blocks are evaluated multiple times. The storage locations that are
213
  // in scope for a particular basic block are stored in `Environment`.
214
  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
215
  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
216
217
  StorageLocation *ThisPointeeLoc = nullptr;
218
219
  AtomicBoolValue &TrueVal;
220
  AtomicBoolValue &FalseVal;
221
222
  // Indices that are used to avoid recreating the same composite boolean
223
  // values.
224
  llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
225
      ConjunctionVals;
226
  llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *>
227
      DisjunctionVals;
228
  llvm::DenseMap<BoolValue *, NegationValue *> NegationVals;
229
230
  // Flow conditions are tracked symbolically: each unique flow condition is
231
  // associated with a fresh symbolic variable (token), bound to the clause that
232
  // defines the flow condition. Conceptually, each binding corresponds to an
233
  // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition
234
  // token (an atomic boolean) and `Ci`s are the set of constraints in the flow
235
  // flow condition clause. Internally, we do not record the formula directly as
236
  // an "iff". Instead, a flow condition clause is encoded as conjuncts of the
237
  // form `(FC v !C1 v !C2 v ...) ^ (C1 v !FC) ^ (C2 v !FC) ^ ...`. The first
238
  // conjuct is stored in the `FlowConditionFirstConjuncts` map and the set of
239
  // remaining conjuncts are stored in the `FlowConditionRemainingConjuncts`
240
  // map, both keyed by the token of the flow condition.
241
  //
242
  // Flow conditions depend on other flow conditions if they are created using
243
  // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
244
  // dependencies is stored in the `FlowConditionDeps` map.
245
  llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>>
246
      FlowConditionDeps;
247
  llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionFirstConjuncts;
248
  llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<BoolValue *>>
249
      FlowConditionRemainingConjuncts;
250
};
251
252
} // namespace dataflow
253
} // namespace clang
254
255
#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H