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   assert(!Type.isNull());
28   if (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 static std::pair<BoolValue *, BoolValue *>
59 makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {
60   auto Res = std::make_pair(&LHS, &RHS);
61   if (&RHS < &LHS)
62     std::swap(Res.first, Res.second);
63   return Res;
64 }
65 
66 BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS,
67                                                            BoolValue &RHS) {
68   if (&LHS == &RHS)
69     return LHS;
70 
71   auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
72                                          nullptr);
73   if (Res.second)
74     Res.first->second =
75         &takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS));
76   return *Res.first->second;
77 }
78 
79 BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS,
80                                                            BoolValue &RHS) {
81   if (&LHS == &RHS)
82     return LHS;
83 
84   auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS),
85                                          nullptr);
86   if (Res.second)
87     Res.first->second =
88         &takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS));
89   return *Res.first->second;
90 }
91 
92 BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) {
93   auto Res = NegationVals.try_emplace(&Val, nullptr);
94   if (Res.second)
95     Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val));
96   return *Res.first->second;
97 }
98 
99 BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS,
100                                                            BoolValue &RHS) {
101   return &LHS == &RHS ? getBoolLiteralValue(true)
102                       : getOrCreateDisjunction(getOrCreateNegation(LHS), RHS);
103 }
104 
105 BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS,
106                                                    BoolValue &RHS) {
107   return &LHS == &RHS
108              ? getBoolLiteralValue(true)
109              : getOrCreateConjunction(getOrCreateImplication(LHS, RHS),
110                                       getOrCreateImplication(RHS, LHS));
111 }
112 
113 AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() {
114   return createAtomicBoolValue();
115 }
116 
117 void DataflowAnalysisContext::addFlowConditionConstraint(
118     AtomicBoolValue &Token, BoolValue &Constraint) {
119   auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint);
120   if (!Res.second) {
121     Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint);
122   }
123 }
124 
125 AtomicBoolValue &
126 DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) {
127   auto &ForkToken = makeFlowConditionToken();
128   FlowConditionDeps[&ForkToken].insert(&Token);
129   addFlowConditionConstraint(ForkToken, Token);
130   return ForkToken;
131 }
132 
133 AtomicBoolValue &
134 DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken,
135                                             AtomicBoolValue &SecondToken) {
136   auto &Token = makeFlowConditionToken();
137   FlowConditionDeps[&Token].insert(&FirstToken);
138   FlowConditionDeps[&Token].insert(&SecondToken);
139   addFlowConditionConstraint(Token,
140                              getOrCreateDisjunction(FirstToken, SecondToken));
141   return Token;
142 }
143 
144 Solver::Result
145 DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) {
146   Constraints.insert(&getBoolLiteralValue(true));
147   Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false)));
148   return S->solve(std::move(Constraints));
149 }
150 
151 bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token,
152                                                    BoolValue &Val) {
153   // Returns true if and only if truth assignment of the flow condition implies
154   // that `Val` is also true. We prove whether or not this property holds by
155   // reducing the problem to satisfiability checking. In other words, we attempt
156   // to show that assuming `Val` is false makes the constraints induced by the
157   // flow condition unsatisfiable.
158   llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)};
159   llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
160   addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
161   return isUnsatisfiable(std::move(Constraints));
162 }
163 
164 bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) {
165   // Returns true if and only if we cannot prove that the flow condition can
166   // ever be false.
167   llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)};
168   llvm::DenseSet<AtomicBoolValue *> VisitedTokens;
169   addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
170   return isUnsatisfiable(std::move(Constraints));
171 }
172 
173 bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1,
174                                                    BoolValue &Val2) {
175   llvm::DenseSet<BoolValue *> Constraints = {
176       &getOrCreateNegation(getOrCreateIff(Val1, Val2))};
177   return isUnsatisfiable(Constraints);
178 }
179 
180 void DataflowAnalysisContext::addTransitiveFlowConditionConstraints(
181     AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
182     llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) {
183   auto Res = VisitedTokens.insert(&Token);
184   if (!Res.second)
185     return;
186 
187   auto ConstraintsIT = FlowConditionConstraints.find(&Token);
188   if (ConstraintsIT == FlowConditionConstraints.end()) {
189     Constraints.insert(&Token);
190   } else {
191     // Bind flow condition token via `iff` to its set of constraints:
192     // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints
193     Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second));
194   }
195 
196   auto DepsIT = FlowConditionDeps.find(&Token);
197   if (DepsIT != FlowConditionDeps.end()) {
198     for (AtomicBoolValue *DepToken : DepsIT->second) {
199       addTransitiveFlowConditionConstraints(*DepToken, Constraints,
200                                             VisitedTokens);
201     }
202   }
203 }
204 
205 } // namespace dataflow
206 } // namespace clang
207 
208 using namespace clang;
209 
210 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
211   const Expr *Current = &E;
212   if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
213     Current = EWC->getSubExpr();
214     assert(Current != nullptr);
215   }
216   Current = Current->IgnoreParens();
217   assert(Current != nullptr);
218   return *Current;
219 }
220 
221 const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
222   if (auto *E = dyn_cast<Expr>(&S))
223     return ignoreCFGOmittedNodes(*E);
224   return S;
225 }
226 
227 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single
228 // field decl will be modeled for all instances of the inherited field.
229 static void
230 getFieldsFromClassHierarchy(QualType Type,
231                             llvm::DenseSet<const FieldDecl *> &Fields) {
232   if (Type->isIncompleteType() || Type->isDependentType() ||
233       !Type->isRecordType())
234     return;
235 
236   for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
237     Fields.insert(Field);
238   if (auto *CXXRecord = Type->getAsCXXRecordDecl())
239     for (const CXXBaseSpecifier &Base : CXXRecord->bases())
240       getFieldsFromClassHierarchy(Base.getType(), Fields);
241 }
242 
243 /// Gets the set of all fields in the type.
244 llvm::DenseSet<const FieldDecl *>
245 clang::dataflow::getObjectFields(QualType Type) {
246   llvm::DenseSet<const FieldDecl *> Fields;
247   getFieldsFromClassHierarchy(Type, Fields);
248   return Fields;
249 }
250