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