/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 | } |