/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- DataflowEnvironment.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 an Environment class that is used by dataflow analyses |
10 | | // that run over Control-Flow Graphs (CFGs) to keep track of the state of the |
11 | | // program at given program points. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" |
16 | | #include "clang/AST/Decl.h" |
17 | | #include "clang/AST/DeclCXX.h" |
18 | | #include "clang/AST/ExprCXX.h" |
19 | | #include "clang/AST/Type.h" |
20 | | #include "clang/Analysis/FlowSensitive/DataflowLattice.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 "llvm/Support/Casting.h" |
26 | | #include "llvm/Support/ErrorHandling.h" |
27 | | #include <cassert> |
28 | | #include <memory> |
29 | | #include <utility> |
30 | | |
31 | | namespace clang { |
32 | | namespace dataflow { |
33 | | |
34 | | // FIXME: convert these to parameters of the analysis or environment. Current |
35 | | // settings have been experimentaly validated, but only for a particular |
36 | | // analysis. |
37 | | static constexpr int MaxCompositeValueDepth = 3; |
38 | | static constexpr int MaxCompositeValueSize = 1000; |
39 | | |
40 | | /// Returns a map consisting of key-value entries that are present in both maps. |
41 | | template <typename K, typename V> |
42 | | llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1, |
43 | 66.0k | const llvm::DenseMap<K, V> &Map2) { |
44 | 66.0k | llvm::DenseMap<K, V> Result; |
45 | 66.0k | for (auto &Entry : Map1) { |
46 | 1.14k | auto It = Map2.find(Entry.first); |
47 | 1.14k | if (It != Map2.end() && Entry.second == It->second876 ) |
48 | 876 | Result.insert({Entry.first, Entry.second}); |
49 | 1.14k | } |
50 | 66.0k | return Result; |
51 | 66.0k | } llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > clang::dataflow::intersectDenseMaps<clang::ValueDecl const*, clang::dataflow::StorageLocation*>(llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&, llvm::DenseMap<clang::ValueDecl const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::ValueDecl const*, void>, llvm::detail::DenseMapPair<clang::ValueDecl const*, clang::dataflow::StorageLocation*> > const&) Line | Count | Source | 43 | 22.0k | const llvm::DenseMap<K, V> &Map2) { | 44 | 22.0k | llvm::DenseMap<K, V> Result; | 45 | 22.0k | for (auto &Entry : Map1) { | 46 | 312 | auto It = Map2.find(Entry.first); | 47 | 312 | if (It != Map2.end() && Entry.second == It->second300 ) | 48 | 300 | Result.insert({Entry.first, Entry.second}); | 49 | 312 | } | 50 | 22.0k | return Result; | 51 | 22.0k | } |
llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > clang::dataflow::intersectDenseMaps<clang::Expr const*, clang::dataflow::StorageLocation*>(llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > const&, llvm::DenseMap<clang::Expr const*, clang::dataflow::StorageLocation*, llvm::DenseMapInfo<clang::Expr const*, void>, llvm::detail::DenseMapPair<clang::Expr const*, clang::dataflow::StorageLocation*> > const&) Line | Count | Source | 43 | 22.0k | const llvm::DenseMap<K, V> &Map2) { | 44 | 22.0k | llvm::DenseMap<K, V> Result; | 45 | 22.0k | for (auto &Entry : Map1) { | 46 | 828 | auto It = Map2.find(Entry.first); | 47 | 828 | if (It != Map2.end() && Entry.second == It->second572 ) | 48 | 572 | Result.insert({Entry.first, Entry.second}); | 49 | 828 | } | 50 | 22.0k | return Result; | 51 | 22.0k | } |
llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > clang::dataflow::intersectDenseMaps<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> >(llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > const&, llvm::DenseMap<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*>, llvm::DenseMapInfo<clang::dataflow::StorageLocation const*, void>, llvm::detail::DenseMapPair<clang::dataflow::StorageLocation const*, std::__1::pair<clang::dataflow::StructValue*, clang::ValueDecl const*> > > const&) Line | Count | Source | 43 | 22.0k | const llvm::DenseMap<K, V> &Map2) { | 44 | 22.0k | llvm::DenseMap<K, V> Result; | 45 | 22.0k | for (auto &Entry : Map1) { | 46 | 4 | auto It = Map2.find(Entry.first); | 47 | 4 | if (It != Map2.end() && Entry.second == It->second) | 48 | 4 | Result.insert({Entry.first, Entry.second}); | 49 | 4 | } | 50 | 22.0k | return Result; | 51 | 22.0k | } |
|
52 | | |
53 | | /// Returns true if and only if `Val1` is equivalent to `Val2`. |
54 | | static bool equivalentValues(QualType Type, Value *Val1, |
55 | | const Environment &Env1, Value *Val2, |
56 | | const Environment &Env2, |
57 | 28 | Environment::ValueModel &Model) { |
58 | 28 | if (Val1 == Val2) |
59 | 17 | return true; |
60 | | |
61 | 11 | if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) { |
62 | 7 | auto *IndVal2 = cast<IndirectionValue>(Val2); |
63 | 7 | assert(IndVal1->getKind() == IndVal2->getKind()); |
64 | 7 | if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc()) |
65 | 6 | return true; |
66 | 7 | } |
67 | | |
68 | 5 | return Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2); |
69 | 11 | } |
70 | | |
71 | | /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`, |
72 | | /// respectively, of the same type `Type`. Merging generally produces a single |
73 | | /// value that (soundly) approximates the two inputs, although the actual |
74 | | /// meaning depends on `Model`. |
75 | | static Value *mergeDistinctValues(QualType Type, Value *Val1, |
76 | | const Environment &Env1, Value *Val2, |
77 | | const Environment &Env2, |
78 | | Environment &MergedEnv, |
79 | 48 | Environment::ValueModel &Model) { |
80 | | // Join distinct boolean values preserving information about the constraints |
81 | | // in the respective path conditions. |
82 | | // |
83 | | // FIXME: Does not work for backedges, since the two (or more) paths will not |
84 | | // have mutually exclusive conditions. |
85 | 48 | if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) { |
86 | 26 | auto *Expr2 = cast<BoolValue>(Val2); |
87 | 26 | return &Env1.makeOr(Env1.makeAnd(Env1.getFlowConditionToken(), *Expr1), |
88 | 26 | Env1.makeAnd(Env2.getFlowConditionToken(), *Expr2)); |
89 | 26 | } |
90 | | |
91 | | // FIXME: add unit tests that cover this statement. |
92 | 22 | if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) { |
93 | 2 | auto *IndVal2 = cast<IndirectionValue>(Val2); |
94 | 2 | assert(IndVal1->getKind() == IndVal2->getKind()); |
95 | 2 | if (&IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc()) { |
96 | 2 | return Val1; |
97 | 2 | } |
98 | 2 | } |
99 | | |
100 | | // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge` |
101 | | // returns false to avoid storing unneeded values in `DACtx`. |
102 | 20 | if (Value *MergedVal = MergedEnv.createValue(Type)) |
103 | 20 | if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv)) |
104 | 20 | return MergedVal; |
105 | | |
106 | 0 | return nullptr; |
107 | 20 | } |
108 | | |
109 | | /// Initializes a global storage value. |
110 | 805 | static void initGlobalVar(const VarDecl &D, Environment &Env) { |
111 | 805 | if (!D.hasGlobalStorage() || |
112 | 805 | Env.getStorageLocation(D, SkipPast::None) != nullptr45 ) |
113 | 763 | return; |
114 | | |
115 | 42 | auto &Loc = Env.createStorageLocation(D); |
116 | 42 | Env.setStorageLocation(D, Loc); |
117 | 42 | if (auto *Val = Env.createValue(D.getType())) |
118 | 42 | Env.setValue(Loc, *Val); |
119 | 42 | } |
120 | | |
121 | | /// Initializes a global storage value. |
122 | 1.21k | static void initGlobalVar(const Decl &D, Environment &Env) { |
123 | 1.21k | if (auto *V = dyn_cast<VarDecl>(&D)) |
124 | 805 | initGlobalVar(*V, Env); |
125 | 1.21k | } |
126 | | |
127 | | /// Initializes global storage values that are declared or referenced from |
128 | | /// sub-statements of `S`. |
129 | | // FIXME: Add support for resetting globals after function calls to enable |
130 | | // the implementation of sound analyses. |
131 | 3.50k | static void initGlobalVars(const Stmt &S, Environment &Env) { |
132 | 3.50k | for (auto *Child : S.children()) { |
133 | 3.20k | if (Child != nullptr) |
134 | 3.20k | initGlobalVars(*Child, Env); |
135 | 3.20k | } |
136 | | |
137 | 3.50k | if (auto *DS = dyn_cast<DeclStmt>(&S)) { |
138 | 292 | if (DS->isSingleDecl()) { |
139 | 290 | initGlobalVar(*DS->getSingleDecl(), Env); |
140 | 290 | } else { |
141 | 2 | for (auto *D : DS->getDeclGroup()) |
142 | 4 | initGlobalVar(*D, Env); |
143 | 2 | } |
144 | 3.21k | } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) { |
145 | 655 | initGlobalVar(*E->getDecl(), Env); |
146 | 2.55k | } else if (auto *E = dyn_cast<MemberExpr>(&S)) { |
147 | 268 | initGlobalVar(*E->getMemberDecl(), Env); |
148 | 268 | } |
149 | 3.50k | } |
150 | | |
151 | | static void |
152 | | getFieldsFromClassHierarchy(QualType Type, bool IgnorePrivateFields, |
153 | 3.92k | llvm::DenseSet<const FieldDecl *> &Fields) { |
154 | 3.92k | if (Type->isIncompleteType() || Type->isDependentType() || |
155 | 3.92k | !Type->isRecordType()) |
156 | 0 | return; |
157 | | |
158 | 3.92k | for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) { |
159 | 409 | if (IgnorePrivateFields && |
160 | 409 | (40 Field->getAccess() == AS_private40 || |
161 | 40 | (24 Field->getAccess() == AS_none24 && Type->getAsRecordDecl()->isClass()0 ))) |
162 | 16 | continue; |
163 | 393 | Fields.insert(Field); |
164 | 393 | } |
165 | 3.92k | if (auto *CXXRecord = Type->getAsCXXRecordDecl()) { |
166 | 3.92k | for (const CXXBaseSpecifier &Base : CXXRecord->bases()) { |
167 | | // Ignore private fields (including default access in C++ classes) in |
168 | | // base classes, because they are not visible in derived classes. |
169 | 1.26k | getFieldsFromClassHierarchy(Base.getType(), /*IgnorePrivateFields=*/true, |
170 | 1.26k | Fields); |
171 | 1.26k | } |
172 | 3.92k | } |
173 | 3.92k | } |
174 | | |
175 | | /// Gets the set of all fields accesible from the type. |
176 | | /// |
177 | | /// FIXME: Does not precisely handle non-virtual diamond inheritance. A single |
178 | | /// field decl will be modeled for all instances of the inherited field. |
179 | | static llvm::DenseSet<const FieldDecl *> |
180 | 2.66k | getAccessibleObjectFields(QualType Type) { |
181 | 2.66k | llvm::DenseSet<const FieldDecl *> Fields; |
182 | | // Don't ignore private fields for the class itself, only its super classes. |
183 | 2.66k | getFieldsFromClassHierarchy(Type, /*IgnorePrivateFields=*/false, Fields); |
184 | 2.66k | return Fields; |
185 | 2.66k | } |
186 | | |
187 | | Environment::Environment(DataflowAnalysisContext &DACtx) |
188 | 22.3k | : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {} |
189 | | |
190 | | Environment::Environment(const Environment &Other) |
191 | | : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc), |
192 | | ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal), |
193 | | MemberLocToStruct(Other.MemberLocToStruct), |
194 | 157k | FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) { |
195 | 157k | } |
196 | | |
197 | 0 | Environment &Environment::operator=(const Environment &Other) { |
198 | 0 | Environment Copy(Other); |
199 | 0 | *this = std::move(Copy); |
200 | 0 | return *this; |
201 | 0 | } |
202 | | |
203 | | Environment::Environment(DataflowAnalysisContext &DACtx, |
204 | | const DeclContext &DeclCtx) |
205 | 294 | : Environment(DACtx) { |
206 | 294 | if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) { |
207 | 294 | assert(FuncDecl->getBody() != nullptr); |
208 | 0 | initGlobalVars(*FuncDecl->getBody(), *this); |
209 | 294 | for (const auto *ParamDecl : FuncDecl->parameters()) { |
210 | 142 | assert(ParamDecl != nullptr); |
211 | 0 | auto &ParamLoc = createStorageLocation(*ParamDecl); |
212 | 142 | setStorageLocation(*ParamDecl, ParamLoc); |
213 | 142 | if (Value *ParamVal = createValue(ParamDecl->getType())) |
214 | 142 | setValue(ParamLoc, *ParamVal); |
215 | 142 | } |
216 | 294 | } |
217 | | |
218 | 294 | if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) { |
219 | 5 | if (!MethodDecl->isStatic()) { |
220 | 5 | QualType ThisPointeeType = MethodDecl->getThisObjectType(); |
221 | | // FIXME: Add support for union types. |
222 | 5 | if (!ThisPointeeType->isUnionType()) { |
223 | 5 | auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType); |
224 | 5 | DACtx.setThisPointeeStorageLocation(ThisPointeeLoc); |
225 | 5 | if (Value *ThisPointeeVal = createValue(ThisPointeeType)) |
226 | 5 | setValue(ThisPointeeLoc, *ThisPointeeVal); |
227 | 5 | } |
228 | 5 | } |
229 | 5 | } |
230 | 294 | } Unexecuted instantiation: clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&) clang::dataflow::Environment::Environment(clang::dataflow::DataflowAnalysisContext&, clang::DeclContext const&) Line | Count | Source | 205 | 294 | : Environment(DACtx) { | 206 | 294 | if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) { | 207 | 294 | assert(FuncDecl->getBody() != nullptr); | 208 | 0 | initGlobalVars(*FuncDecl->getBody(), *this); | 209 | 294 | for (const auto *ParamDecl : FuncDecl->parameters()) { | 210 | 142 | assert(ParamDecl != nullptr); | 211 | 0 | auto &ParamLoc = createStorageLocation(*ParamDecl); | 212 | 142 | setStorageLocation(*ParamDecl, ParamLoc); | 213 | 142 | if (Value *ParamVal = createValue(ParamDecl->getType())) | 214 | 142 | setValue(ParamLoc, *ParamVal); | 215 | 142 | } | 216 | 294 | } | 217 | | | 218 | 294 | if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) { | 219 | 5 | if (!MethodDecl->isStatic()) { | 220 | 5 | QualType ThisPointeeType = MethodDecl->getThisObjectType(); | 221 | | // FIXME: Add support for union types. | 222 | 5 | if (!ThisPointeeType->isUnionType()) { | 223 | 5 | auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType); | 224 | 5 | DACtx.setThisPointeeStorageLocation(ThisPointeeLoc); | 225 | 5 | if (Value *ThisPointeeVal = createValue(ThisPointeeType)) | 226 | 5 | setValue(ThisPointeeLoc, *ThisPointeeVal); | 227 | 5 | } | 228 | 5 | } | 229 | 5 | } | 230 | 294 | } |
|
231 | | |
232 | | bool Environment::equivalentTo(const Environment &Other, |
233 | 6 | Environment::ValueModel &Model) const { |
234 | 6 | assert(DACtx == Other.DACtx); |
235 | | |
236 | 6 | if (DeclToLoc != Other.DeclToLoc) |
237 | 0 | return false; |
238 | | |
239 | 6 | if (ExprToLoc != Other.ExprToLoc) |
240 | 0 | return false; |
241 | | |
242 | 6 | if (MemberLocToStruct != Other.MemberLocToStruct) |
243 | 0 | return false; |
244 | | |
245 | | // Compare the contents for the intersection of their domains. |
246 | 29 | for (auto &Entry : LocToVal)6 { |
247 | 29 | const StorageLocation *Loc = Entry.first; |
248 | 29 | assert(Loc != nullptr); |
249 | | |
250 | 0 | Value *Val = Entry.second; |
251 | 29 | assert(Val != nullptr); |
252 | | |
253 | 0 | auto It = Other.LocToVal.find(Loc); |
254 | 29 | if (It == Other.LocToVal.end()) |
255 | 1 | continue; |
256 | 28 | assert(It->second != nullptr); |
257 | | |
258 | 28 | if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model)) |
259 | 0 | return false; |
260 | 28 | } |
261 | | |
262 | 6 | return true; |
263 | 6 | } |
264 | | |
265 | | LatticeJoinEffect Environment::join(const Environment &Other, |
266 | 22.0k | Environment::ValueModel &Model) { |
267 | 22.0k | assert(DACtx == Other.DACtx); |
268 | | |
269 | 0 | auto Effect = LatticeJoinEffect::Unchanged; |
270 | | |
271 | 22.0k | Environment JoinedEnv(*DACtx); |
272 | | |
273 | 22.0k | JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); |
274 | 22.0k | if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size()) |
275 | 12 | Effect = LatticeJoinEffect::Changed; |
276 | | |
277 | 22.0k | JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc); |
278 | 22.0k | if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size()) |
279 | 120 | Effect = LatticeJoinEffect::Changed; |
280 | | |
281 | 22.0k | JoinedEnv.MemberLocToStruct = |
282 | 22.0k | intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct); |
283 | 22.0k | if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size()) |
284 | 0 | Effect = LatticeJoinEffect::Changed; |
285 | | |
286 | | // FIXME: set `Effect` as needed. |
287 | 22.0k | JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions( |
288 | 22.0k | *FlowConditionToken, *Other.FlowConditionToken); |
289 | | |
290 | 22.0k | for (auto &Entry : LocToVal) { |
291 | 1.01k | const StorageLocation *Loc = Entry.first; |
292 | 1.01k | assert(Loc != nullptr); |
293 | | |
294 | 0 | Value *Val = Entry.second; |
295 | 1.01k | assert(Val != nullptr); |
296 | | |
297 | 0 | auto It = Other.LocToVal.find(Loc); |
298 | 1.01k | if (It == Other.LocToVal.end()) |
299 | 214 | continue; |
300 | 804 | assert(It->second != nullptr); |
301 | | |
302 | 804 | if (Val == It->second) { |
303 | 756 | JoinedEnv.LocToVal.insert({Loc, Val}); |
304 | 756 | continue; |
305 | 756 | } |
306 | | |
307 | 48 | if (Value *MergedVal = mergeDistinctValues( |
308 | 48 | Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model)) |
309 | 48 | JoinedEnv.LocToVal.insert({Loc, MergedVal}); |
310 | 48 | } |
311 | 22.0k | if (LocToVal.size() != JoinedEnv.LocToVal.size()) |
312 | 120 | Effect = LatticeJoinEffect::Changed; |
313 | | |
314 | 22.0k | *this = std::move(JoinedEnv); |
315 | | |
316 | 22.0k | return Effect; |
317 | 22.0k | } |
318 | | |
319 | 1.66k | StorageLocation &Environment::createStorageLocation(QualType Type) { |
320 | 1.66k | assert(!Type.isNull()); |
321 | 1.66k | if (Type->isStructureOrClassType() || Type->isUnionType()802 ) { |
322 | | // FIXME: Explore options to avoid eager initialization of fields as some of |
323 | | // them might not be needed for a particular analysis. |
324 | 864 | llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs; |
325 | 864 | for (const FieldDecl *Field : getAccessibleObjectFields(Type)) { |
326 | 127 | FieldLocs.insert({Field, &createStorageLocation(Field->getType())}); |
327 | 127 | } |
328 | 864 | return takeOwnership( |
329 | 864 | std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs))); |
330 | 864 | } |
331 | 799 | return takeOwnership(std::make_unique<ScalarStorageLocation>(Type)); |
332 | 1.66k | } |
333 | | |
334 | 761 | StorageLocation &Environment::createStorageLocation(const VarDecl &D) { |
335 | | // Evaluated declarations are always assigned the same storage locations to |
336 | | // ensure that the environment stabilizes across loop iterations. Storage |
337 | | // locations for evaluated declarations are stored in the analysis context. |
338 | 761 | if (auto *Loc = DACtx->getStorageLocation(D)) |
339 | 290 | return *Loc; |
340 | 471 | auto &Loc = createStorageLocation(D.getType()); |
341 | 471 | DACtx->setStorageLocation(D, Loc); |
342 | 471 | return Loc; |
343 | 761 | } |
344 | | |
345 | 2.04k | StorageLocation &Environment::createStorageLocation(const Expr &E) { |
346 | | // Evaluated expressions are always assigned the same storage locations to |
347 | | // ensure that the environment stabilizes across loop iterations. Storage |
348 | | // locations for evaluated expressions are stored in the analysis context. |
349 | 2.04k | if (auto *Loc = DACtx->getStorageLocation(E)) |
350 | 1.03k | return *Loc; |
351 | 1.00k | auto &Loc = createStorageLocation(E.getType()); |
352 | 1.00k | DACtx->setStorageLocation(E, Loc); |
353 | 1.00k | return Loc; |
354 | 2.04k | } |
355 | | |
356 | 761 | void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { |
357 | 761 | assert(DeclToLoc.find(&D) == DeclToLoc.end()); |
358 | 0 | DeclToLoc[&D] = &Loc; |
359 | 761 | } |
360 | | |
361 | | StorageLocation *Environment::getStorageLocation(const ValueDecl &D, |
362 | 1.57k | SkipPast SP) const { |
363 | 1.57k | auto It = DeclToLoc.find(&D); |
364 | 1.57k | return It == DeclToLoc.end() ? nullptr347 : &skip(*It->second, SP)1.22k ; |
365 | 1.57k | } |
366 | | |
367 | 2.52k | void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { |
368 | 2.52k | const Expr &CanonE = ignoreCFGOmittedNodes(E); |
369 | 2.52k | assert(ExprToLoc.find(&CanonE) == ExprToLoc.end()); |
370 | 0 | ExprToLoc[&CanonE] = &Loc; |
371 | 2.52k | } |
372 | | |
373 | | StorageLocation *Environment::getStorageLocation(const Expr &E, |
374 | 3.97k | SkipPast SP) const { |
375 | | // FIXME: Add a test with parens. |
376 | 3.97k | auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); |
377 | 3.97k | return It == ExprToLoc.end() ? nullptr467 : &skip(*It->second, SP)3.50k ; |
378 | 3.97k | } |
379 | | |
380 | 37 | StorageLocation *Environment::getThisPointeeStorageLocation() const { |
381 | 37 | return DACtx->getThisPointeeStorageLocation(); |
382 | 37 | } |
383 | | |
384 | 3.37k | void Environment::setValue(const StorageLocation &Loc, Value &Val) { |
385 | 3.37k | LocToVal[&Loc] = &Val; |
386 | | |
387 | 3.37k | if (auto *StructVal = dyn_cast<StructValue>(&Val)) { |
388 | 1.26k | auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc); |
389 | | |
390 | 1.26k | const QualType Type = AggregateLoc.getType(); |
391 | 1.26k | assert(Type->isStructureOrClassType()); |
392 | | |
393 | 166 | for (const FieldDecl *Field : getAccessibleObjectFields(Type)) { |
394 | 166 | assert(Field != nullptr); |
395 | 0 | StorageLocation &FieldLoc = AggregateLoc.getChild(*Field); |
396 | 166 | MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field); |
397 | 166 | if (auto *FieldVal = StructVal->getChild(*Field)) |
398 | 164 | setValue(FieldLoc, *FieldVal); |
399 | 166 | } |
400 | 1.26k | } |
401 | | |
402 | 0 | auto IT = MemberLocToStruct.find(&Loc); |
403 | 3.37k | if (IT != MemberLocToStruct.end()) { |
404 | | // `Loc` is the location of a struct member so we need to also update the |
405 | | // value of the member in the corresponding `StructValue`. |
406 | | |
407 | 176 | assert(IT->second.first != nullptr); |
408 | 0 | StructValue &StructVal = *IT->second.first; |
409 | | |
410 | 176 | assert(IT->second.second != nullptr); |
411 | 0 | const ValueDecl &Member = *IT->second.second; |
412 | | |
413 | 176 | StructVal.setChild(Member, Val); |
414 | 176 | } |
415 | 3.37k | } |
416 | | |
417 | 5.93k | Value *Environment::getValue(const StorageLocation &Loc) const { |
418 | 5.93k | auto It = LocToVal.find(&Loc); |
419 | 5.93k | return It == LocToVal.end() ? nullptr11 : It->second5.91k ; |
420 | 5.93k | } |
421 | | |
422 | 142 | Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const { |
423 | 142 | auto *Loc = getStorageLocation(D, SP); |
424 | 142 | if (Loc == nullptr) |
425 | 0 | return nullptr; |
426 | 142 | return getValue(*Loc); |
427 | 142 | } |
428 | | |
429 | 2.86k | Value *Environment::getValue(const Expr &E, SkipPast SP) const { |
430 | 2.86k | auto *Loc = getStorageLocation(E, SP); |
431 | 2.86k | if (Loc == nullptr) |
432 | 212 | return nullptr; |
433 | 2.65k | return getValue(*Loc); |
434 | 2.86k | } |
435 | | |
436 | 746 | Value *Environment::createValue(QualType Type) { |
437 | 746 | llvm::DenseSet<QualType> Visited; |
438 | 746 | int CreatedValuesCount = 0; |
439 | 746 | Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, |
440 | 746 | CreatedValuesCount); |
441 | 746 | if (CreatedValuesCount > MaxCompositeValueSize) { |
442 | 0 | llvm::errs() << "Attempting to initialize a huge value of type: " << Type |
443 | 0 | << '\n'; |
444 | 0 | } |
445 | 746 | return Val; |
446 | 746 | } |
447 | | |
448 | | Value *Environment::createValueUnlessSelfReferential( |
449 | | QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, |
450 | 888 | int &CreatedValuesCount) { |
451 | 888 | assert(!Type.isNull()); |
452 | | |
453 | | // Allow unlimited fields at depth 1; only cap at deeper nesting levels. |
454 | 888 | if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize31 ) || |
455 | 888 | Depth > MaxCompositeValueDepth) |
456 | 0 | return nullptr; |
457 | | |
458 | 888 | if (Type->isBooleanType()) { |
459 | 71 | CreatedValuesCount++; |
460 | 71 | return &makeAtomicBoolValue(); |
461 | 71 | } |
462 | | |
463 | 817 | if (Type->isIntegerType()) { |
464 | 210 | CreatedValuesCount++; |
465 | 210 | return &takeOwnership(std::make_unique<IntegerValue>()); |
466 | 210 | } |
467 | | |
468 | 607 | if (Type->isReferenceType()) { |
469 | 26 | CreatedValuesCount++; |
470 | 26 | QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType(); |
471 | 26 | auto &PointeeLoc = createStorageLocation(PointeeType); |
472 | | |
473 | 26 | if (!Visited.contains(PointeeType.getCanonicalType())) { |
474 | 22 | Visited.insert(PointeeType.getCanonicalType()); |
475 | 22 | Value *PointeeVal = createValueUnlessSelfReferential( |
476 | 22 | PointeeType, Visited, Depth, CreatedValuesCount); |
477 | 22 | Visited.erase(PointeeType.getCanonicalType()); |
478 | | |
479 | 22 | if (PointeeVal != nullptr) |
480 | 22 | setValue(PointeeLoc, *PointeeVal); |
481 | 22 | } |
482 | | |
483 | 26 | return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc)); |
484 | 26 | } |
485 | | |
486 | 581 | if (Type->isPointerType()) { |
487 | 26 | CreatedValuesCount++; |
488 | 26 | QualType PointeeType = Type->castAs<PointerType>()->getPointeeType(); |
489 | 26 | auto &PointeeLoc = createStorageLocation(PointeeType); |
490 | | |
491 | 26 | if (!Visited.contains(PointeeType.getCanonicalType())) { |
492 | 22 | Visited.insert(PointeeType.getCanonicalType()); |
493 | 22 | Value *PointeeVal = createValueUnlessSelfReferential( |
494 | 22 | PointeeType, Visited, Depth, CreatedValuesCount); |
495 | 22 | Visited.erase(PointeeType.getCanonicalType()); |
496 | | |
497 | 22 | if (PointeeVal != nullptr) |
498 | 21 | setValue(PointeeLoc, *PointeeVal); |
499 | 22 | } |
500 | | |
501 | 26 | return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc)); |
502 | 26 | } |
503 | | |
504 | 555 | if (Type->isStructureOrClassType()) { |
505 | 530 | CreatedValuesCount++; |
506 | | // FIXME: Initialize only fields that are accessed in the context that is |
507 | | // being analyzed. |
508 | 530 | llvm::DenseMap<const ValueDecl *, Value *> FieldValues; |
509 | 530 | for (const FieldDecl *Field : getAccessibleObjectFields(Type)) { |
510 | 100 | assert(Field != nullptr); |
511 | | |
512 | 0 | QualType FieldType = Field->getType(); |
513 | 100 | if (Visited.contains(FieldType.getCanonicalType())) |
514 | 2 | continue; |
515 | | |
516 | 98 | Visited.insert(FieldType.getCanonicalType()); |
517 | 98 | if (auto *FieldValue = createValueUnlessSelfReferential( |
518 | 98 | FieldType, Visited, Depth + 1, CreatedValuesCount)) |
519 | 98 | FieldValues.insert({Field, FieldValue}); |
520 | 98 | Visited.erase(FieldType.getCanonicalType()); |
521 | 98 | } |
522 | | |
523 | 530 | return &takeOwnership( |
524 | 530 | std::make_unique<StructValue>(std::move(FieldValues))); |
525 | 530 | } |
526 | | |
527 | 25 | return nullptr; |
528 | 555 | } |
529 | | |
530 | 5.42k | StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const { |
531 | 5.42k | switch (SP) { |
532 | 2.42k | case SkipPast::None: |
533 | 2.42k | return Loc; |
534 | 2.29k | case SkipPast::Reference: |
535 | | // References cannot be chained so we only need to skip past one level of |
536 | | // indirection. |
537 | 2.29k | if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc))) |
538 | 1.56k | return Val->getPointeeLoc(); |
539 | 736 | return Loc; |
540 | 694 | case SkipPast::ReferenceThenPointer: |
541 | 694 | StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference); |
542 | 694 | if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef))) |
543 | 50 | return Val->getPointeeLoc(); |
544 | 644 | return LocPastRef; |
545 | 5.42k | } |
546 | 0 | llvm_unreachable("bad SkipPast kind"); |
547 | 0 | } |
548 | | |
549 | | const StorageLocation &Environment::skip(const StorageLocation &Loc, |
550 | 0 | SkipPast SP) const { |
551 | 0 | return skip(*const_cast<StorageLocation *>(&Loc), SP); |
552 | 0 | } |
553 | | |
554 | 401 | void Environment::addToFlowCondition(BoolValue &Val) { |
555 | 401 | DACtx->addFlowConditionConstraint(*FlowConditionToken, Val); |
556 | 401 | } |
557 | | |
558 | 414 | bool Environment::flowConditionImplies(BoolValue &Val) const { |
559 | 414 | return DACtx->flowConditionImplies(*FlowConditionToken, Val); |
560 | 414 | } |
561 | | |
562 | | } // namespace dataflow |
563 | | } // namespace clang |