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 DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
27   if (!Type.isNull() &&
28       (Type->isStructureOrClassType() || Type->isUnionType())) {
29     // FIXME: Explore options to avoid eager initialization of fields as some of
30     // them might not be needed for a particular analysis.
31     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
32     for (const FieldDecl *Field : getObjectFields(Type))
33       FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
34     return takeOwnership(
35         std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
36   }
37   return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
38 }
39 
40 StorageLocation &
41 DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
42   if (auto *Loc = getStorageLocation(D))
43     return *Loc;
44   auto &Loc = getStableStorageLocation(D.getType());
45   setStorageLocation(D, Loc);
46   return Loc;
47 }
48 
49 StorageLocation &
50 DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
51   if (auto *Loc = getStorageLocation(E))
52     return *Loc;
53   auto &Loc = getStableStorageLocation(E.getType());
54   setStorageLocation(E, Loc);
55   return Loc;
56 }
57 
58 PointerValue &
59 DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
60   auto CanonicalPointeeType =
61       PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType();
62   auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
63   if (Res.second) {
64     auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
65     Res.first->second =
66         &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
67   }
68   return *Res.first->second;
69 }
70 
71 static std::pair<BoolValue *, BoolValue *>
72 makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
73   auto Res = std::make_pair(&LHS, &RHS);
74   if (&RHS < &LHS)
75     std::swap(Res.first, Res.second);
76   return Res;
77 }
78 
79 BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS,
80                                                            BoolValue &RHS) {
81   if (&LHS == &RHS)
82     return LHS;
83 
84   auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
85                                          nullptr);
86   if (Res.second)
87     Res.first->second =
88         &takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS));
89   return *Res.first->second;
90 }
91 
92 BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS,
93                                                            BoolValue &RHS) {
94   if (&LHS == &RHS)
95     return LHS;
96 
97   auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
98                                          nullptr);
99   if (Res.second)
100     Res.first->second =
101         &takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS));
102   return *Res.first->second;
103 }
104 
105 BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) {
106   auto Res = NegationVals.try_emplace(&Val, nullptr);
107   if (Res.second)
108     Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val));
109   return *Res.first->second;
110 }
111 
112 BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS,
113                                                            BoolValue &RHS) {
114   return &LHS == &RHS ? getBoolLiteralValue(true)
115                       : getOrCreateDisjunction(getOrCreateNegation(LHS), RHS);
116 }
117 
118 BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS,
119                                                    BoolValue &RHS) {
120   return &LHS == &RHS
121              ? getBoolLiteralValue(true)
122              : getOrCreateConjunction(getOrCreateImplication(LHS, RHS),
123                                       getOrCreateImplication(RHS, LHS));
124 }
125 
126 AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() {
127   return createAtomicBoolValue();
128 }
129 
130 void DataflowAnalysisContext::addFlowConditionConstraint(
131     AtomicBoolValue &Token, BoolValue &Constraint) {
132   auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint);
133   if (!Res.second) {
134     Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint);
135   }
136 }
137 
138 AtomicBoolValue &
139 DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) {
140   auto &ForkToken = makeFlowConditionToken();
141   FlowConditionDeps[&ForkToken].insert(&Token);
142   addFlowConditionConstraint(ForkToken, Token);
143   return ForkToken;
144 }
145 
146 AtomicBoolValue &
147 DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken,
148                                             AtomicBoolValue &SecondToken) {
149   auto &Token = makeFlowConditionToken();
150   FlowConditionDeps[&Token].insert(&FirstToken);
151   FlowConditionDeps[&Token].insert(&SecondToken);
152   addFlowConditionConstraint(Token,
153                              getOrCreateDisjunction(FirstToken, SecondToken));
154   return Token;
155 }
156 
157 Solver::Result
158 DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) {
159   Constraints.insert(&getBoolLiteralValue(true));
160   Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false)));
161   return S->solve(std::move(Constraints));
162 }
163 
164 bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token,
165                                                    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   llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)};
172   llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
173   addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
174   return isUnsatisfiable(std::move(Constraints));
175 }
176 
177 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   llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)};
181   llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
182   addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
183   return isUnsatisfiable(std::move(Constraints));
184 }
185 
186 bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1,
187                                                    BoolValue &Val2) {
188   llvm::DenseSet<BoolValue *> Constraints = {
189       &getOrCreateNegation(getOrCreateIff(Val1, Val2))};
190   return isUnsatisfiable(Constraints);
191 }
192 
193 void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
194     AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
195     llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) {
196   auto Res = VisitedTokens.insert(&Token);
197   if (!Res.second)
198     return;
199 
200   auto ConstraintsIT = FlowConditionConstraints.find(&Token);
201   if (ConstraintsIT == FlowConditionConstraints.end()) {
202     Constraints.insert(&Token);
203   } else {
204     // Bind flow condition token via `iff` to its set of constraints:
205     // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints
206     Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second));
207   }
208 
209   auto DepsIT = FlowConditionDeps.find(&Token);
210   if (DepsIT != FlowConditionDeps.end()) {
211     for (AtomicBoolValue *DepToken : DepsIT->second) {
212       addTransitiveFlowConditionConstraints(*DepToken, Constraints,
213                                             VisitedTokens);
214     }
215   }
216 }
217 
218 BoolValue &DataflowAnalysisContext::substituteBoolValue(
219     BoolValue &Val,
220     llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
221   auto IT = SubstitutionsCache.find(&Val);
222   if (IT != SubstitutionsCache.end()) {
223     // Return memoized result of substituting this boolean value.
224     return *IT->second;
225   }
226 
227   // Handle substitution on the boolean value (and its subvalues), saving the
228   // result into `SubstitutionsCache`.
229   BoolValue *Result;
230   switch (Val.getKind()) {
231   case Value::Kind::AtomicBool: {
232     Result = &Val;
233     break;
234   }
235   case Value::Kind::Negation: {
236     auto &Negation = *cast<NegationValue>(&Val);
237     auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache);
238     Result = &getOrCreateNegation(Sub);
239     break;
240   }
241   case Value::Kind::Disjunction: {
242     auto &Disjunct = *cast<DisjunctionValue>(&Val);
243     auto &LeftSub =
244         substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache);
245     auto &RightSub =
246         substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache);
247     Result = &getOrCreateDisjunction(LeftSub, RightSub);
248     break;
249   }
250   case Value::Kind::Conjunction: {
251     auto &Conjunct = *cast<ConjunctionValue>(&Val);
252     auto &LeftSub =
253         substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache);
254     auto &RightSub =
255         substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache);
256     Result = &getOrCreateConjunction(LeftSub, RightSub);
257     break;
258   }
259   default:
260     llvm_unreachable("Unhandled Value Kind");
261   }
262   SubstitutionsCache[&Val] = Result;
263   return *Result;
264 }
265 
266 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition(
267     AtomicBoolValue &Token,
268     llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {
269   assert(
270       Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() &&
271       Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() &&
272       "Do not substitute true/false boolean literals");
273   llvm::DenseMap<BoolValue *, BoolValue *> SubstitutionsCache(
274       Substitutions.begin(), Substitutions.end());
275   return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache);
276 }
277 
278 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache(
279     AtomicBoolValue &Token,
280     llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) {
281   auto ConstraintsIT = FlowConditionConstraints.find(&Token);
282   if (ConstraintsIT == FlowConditionConstraints.end()) {
283     return getBoolLiteralValue(true);
284   }
285   auto DepsIT = FlowConditionDeps.find(&Token);
286   if (DepsIT != FlowConditionDeps.end()) {
287     for (AtomicBoolValue *DepToken : DepsIT->second) {
288       auto &NewDep = buildAndSubstituteFlowConditionWithCache(
289           *DepToken, SubstitutionsCache);
290       SubstitutionsCache[DepToken] = &NewDep;
291     }
292   }
293   return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache);
294 }
295 
296 } // namespace dataflow
297 } // namespace clang
298 
299 using namespace clang;
300 
301 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
302   const Expr *Current = &E;
303   if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
304     Current = EWC->getSubExpr();
305     assert(Current != nullptr);
306   }
307   Current = Current->IgnoreParens();
308   assert(Current != nullptr);
309   return *Current;
310 }
311 
312 const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
313   if (auto *E = dyn_cast<Expr>(&S))
314     return ignoreCFGOmittedNodes(*E);
315   return S;
316 }
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                             llvm::DenseSet<const FieldDecl *> &Fields) {
323   if (Type->isIncompleteType() || Type->isDependentType() ||
324       !Type->isRecordType())
325     return;
326 
327   for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
328     Fields.insert(Field);
329   if (auto *CXXRecord = Type->getAsCXXRecordDecl())
330     for (const CXXBaseSpecifier &Base : CXXRecord->bases())
331       getFieldsFromClassHierarchy(Base.getType(), Fields);
332 }
333 
334 /// Gets the set of all fields in the type.
335 llvm::DenseSet<const FieldDecl *>
336 clang::dataflow::getObjectFields(QualType Type) {
337   llvm::DenseSet<const FieldDecl *> Fields;
338   getFieldsFromClassHierarchy(Type, Fields);
339   return Fields;
340 }
341