/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- 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 the template classes ExplodedNode and ExplodedGraph, |
10 | | // which represent a path-sensitive, intra-procedural "exploded graph." |
11 | | // See "Precise interprocedural dataflow analysis via graph reachability" |
12 | | // by Reps, Horwitz, and Sagiv |
13 | | // (http://portal.acm.org/citation.cfm?id=199462) for the definition of an |
14 | | // exploded graph. |
15 | | // |
16 | | //===----------------------------------------------------------------------===// |
17 | | |
18 | | #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H |
19 | | #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H |
20 | | |
21 | | #include "clang/Analysis/AnalysisDeclContext.h" |
22 | | #include "clang/Analysis/ProgramPoint.h" |
23 | | #include "clang/Analysis/Support/BumpVector.h" |
24 | | #include "clang/Basic/LLVM.h" |
25 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" |
26 | | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" |
27 | | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" |
28 | | #include "llvm/ADT/ArrayRef.h" |
29 | | #include "llvm/ADT/DenseMap.h" |
30 | | #include "llvm/ADT/DepthFirstIterator.h" |
31 | | #include "llvm/ADT/FoldingSet.h" |
32 | | #include "llvm/ADT/GraphTraits.h" |
33 | | #include "llvm/ADT/Optional.h" |
34 | | #include "llvm/ADT/STLExtras.h" |
35 | | #include "llvm/ADT/SetVector.h" |
36 | | #include "llvm/Support/Allocator.h" |
37 | | #include "llvm/Support/Compiler.h" |
38 | | #include <cassert> |
39 | | #include <cstdint> |
40 | | #include <memory> |
41 | | #include <utility> |
42 | | #include <vector> |
43 | | |
44 | | namespace clang { |
45 | | |
46 | | class CFG; |
47 | | class Decl; |
48 | | class Expr; |
49 | | class ParentMap; |
50 | | class Stmt; |
51 | | |
52 | | namespace ento { |
53 | | |
54 | | class ExplodedGraph; |
55 | | |
56 | | //===----------------------------------------------------------------------===// |
57 | | // ExplodedGraph "implementation" classes. These classes are not typed to |
58 | | // contain a specific kind of state. Typed-specialized versions are defined |
59 | | // on top of these classes. |
60 | | //===----------------------------------------------------------------------===// |
61 | | |
62 | | // ExplodedNode is not constified all over the engine because we need to add |
63 | | // successors to it at any time after creating it. |
64 | | |
65 | | class ExplodedNode : public llvm::FoldingSetNode { |
66 | | friend class BranchNodeBuilder; |
67 | | friend class CoreEngine; |
68 | | friend class EndOfFunctionNodeBuilder; |
69 | | friend class ExplodedGraph; |
70 | | friend class IndirectGotoNodeBuilder; |
71 | | friend class NodeBuilder; |
72 | | friend class SwitchNodeBuilder; |
73 | | |
74 | | /// Efficiently stores a list of ExplodedNodes, or an optional flag. |
75 | | /// |
76 | | /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing |
77 | | /// for the case when there is only one node in the group. This is a fairly |
78 | | /// common case in an ExplodedGraph, where most nodes have only one |
79 | | /// predecessor and many have only one successor. It can also be used to |
80 | | /// store a flag rather than a node list, which ExplodedNode uses to mark |
81 | | /// whether a node is a sink. If the flag is set, the group is implicitly |
82 | | /// empty and no nodes may be added. |
83 | | class NodeGroup { |
84 | | // Conceptually a discriminated union. If the low bit is set, the node is |
85 | | // a sink. If the low bit is not set, the pointer refers to the storage |
86 | | // for the nodes in the group. |
87 | | // This is not a PointerIntPair in order to keep the storage type opaque. |
88 | | uintptr_t P; |
89 | | |
90 | | public: |
91 | 11.9M | NodeGroup(bool Flag = false) : P(Flag) { |
92 | 11.9M | assert(getFlag() == Flag); |
93 | 11.9M | } |
94 | | |
95 | | ExplodedNode * const *begin() const; |
96 | | |
97 | | ExplodedNode * const *end() const; |
98 | | |
99 | | unsigned size() const; |
100 | | |
101 | 14.2M | bool empty() const { return P == 0 || getFlag() != 014.1M ; } |
102 | | |
103 | | /// Adds a node to the list. |
104 | | /// |
105 | | /// The group must not have been created with its flag set. |
106 | | void addNode(ExplodedNode *N, ExplodedGraph &G); |
107 | | |
108 | | /// Replaces the single node in this group with a new node. |
109 | | /// |
110 | | /// Note that this should only be used when you know the group was not |
111 | | /// created with its flag set, and that the group is empty or contains |
112 | | /// only a single node. |
113 | | void replaceNode(ExplodedNode *node); |
114 | | |
115 | | /// Returns whether this group was created with its flag set. |
116 | 101M | bool getFlag() const { |
117 | 101M | return (P & 1); |
118 | 101M | } |
119 | | }; |
120 | | |
121 | | /// Location - The program location (within a function body) associated |
122 | | /// with this node. |
123 | | const ProgramPoint Location; |
124 | | |
125 | | /// State - The state associated with this node. |
126 | | ProgramStateRef State; |
127 | | |
128 | | /// Preds - The predecessors of this node. |
129 | | NodeGroup Preds; |
130 | | |
131 | | /// Succs - The successors of this node. |
132 | | NodeGroup Succs; |
133 | | |
134 | | int64_t Id; |
135 | | |
136 | | public: |
137 | | explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, |
138 | | int64_t Id, bool IsSink) |
139 | 5.96M | : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) { |
140 | 5.96M | assert(isSink() == IsSink); |
141 | 5.96M | } |
142 | | |
143 | | /// getLocation - Returns the edge associated with the given node. |
144 | 43.3M | ProgramPoint getLocation() const { return Location; } |
145 | | |
146 | 20.3M | const LocationContext *getLocationContext() const { |
147 | 20.3M | return getLocation().getLocationContext(); |
148 | 20.3M | } |
149 | | |
150 | 775k | const StackFrameContext *getStackFrame() const { |
151 | 775k | return getLocation().getStackFrame(); |
152 | 775k | } |
153 | | |
154 | 15.0k | const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } |
155 | | |
156 | 4.69k | CFG &getCFG() const { return *getLocationContext()->getCFG(); } |
157 | | |
158 | | const CFGBlock *getCFGBlock() const; |
159 | | |
160 | 2.88M | const ParentMap &getParentMap() const { |
161 | 2.88M | return getLocationContext()->getParentMap(); |
162 | 2.88M | } |
163 | | |
164 | | template <typename T> |
165 | | T &getAnalysis() const { |
166 | | return *getLocationContext()->getAnalysis<T>(); |
167 | | } |
168 | | |
169 | 17.8M | const ProgramStateRef &getState() const { return State; } |
170 | | |
171 | | template <typename T> |
172 | 5.33M | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { |
173 | 5.33M | return Location.getAs<T>(); |
174 | 5.33M | } llvm::Optional<clang::BlockEdge> clang::ento::ExplodedNode::getLocationAs<clang::BlockEdge>() const & Line | Count | Source | 172 | 24.8k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 24.8k | return Location.getAs<T>(); | 174 | 24.8k | } |
llvm::Optional<clang::CallEnter> clang::ento::ExplodedNode::getLocationAs<clang::CallEnter>() const & Line | Count | Source | 172 | 3.20M | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 3.20M | return Location.getAs<T>(); | 174 | 3.20M | } |
llvm::Optional<clang::CallExitEnd> clang::ento::ExplodedNode::getLocationAs<clang::CallExitEnd>() const & Line | Count | Source | 172 | 1.81k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 1.81k | return Location.getAs<T>(); | 174 | 1.81k | } |
llvm::Optional<clang::StmtPoint> clang::ento::ExplodedNode::getLocationAs<clang::StmtPoint>() const & Line | Count | Source | 172 | 1.27k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 1.27k | return Location.getAs<T>(); | 174 | 1.27k | } |
llvm::Optional<clang::PostStore> clang::ento::ExplodedNode::getLocationAs<clang::PostStore>() const & Line | Count | Source | 172 | 92.3k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 92.3k | return Location.getAs<T>(); | 174 | 92.3k | } |
llvm::Optional<clang::PostInitializer> clang::ento::ExplodedNode::getLocationAs<clang::PostInitializer>() const & Line | Count | Source | 172 | 95.1k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 95.1k | return Location.getAs<T>(); | 174 | 95.1k | } |
llvm::Optional<clang::PostStmt> clang::ento::ExplodedNode::getLocationAs<clang::PostStmt>() const & Line | Count | Source | 172 | 110k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 110k | return Location.getAs<T>(); | 174 | 110k | } |
llvm::Optional<clang::CallExitBegin> clang::ento::ExplodedNode::getLocationAs<clang::CallExitBegin>() const & Line | Count | Source | 172 | 151k | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 151k | return Location.getAs<T>(); | 174 | 151k | } |
llvm::Optional<clang::PreStmt> clang::ento::ExplodedNode::getLocationAs<clang::PreStmt>() const & Line | Count | Source | 172 | 1.65M | Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { | 173 | 1.65M | return Location.getAs<T>(); | 174 | 1.65M | } |
|
175 | | |
176 | | /// Get the value of an arbitrary expression at this node. |
177 | 322k | SVal getSVal(const Stmt *S) const { |
178 | 322k | return getState()->getSVal(S, getLocationContext()); |
179 | 322k | } |
180 | | |
181 | | static void Profile(llvm::FoldingSetNodeID &ID, |
182 | | const ProgramPoint &Loc, |
183 | | const ProgramStateRef &state, |
184 | 3.84M | bool IsSink) { |
185 | 3.84M | ID.Add(Loc); |
186 | 3.84M | ID.AddPointer(state.get()); |
187 | 3.84M | ID.AddBoolean(IsSink); |
188 | 3.84M | } |
189 | | |
190 | 1.40M | void Profile(llvm::FoldingSetNodeID& ID) const { |
191 | | // We avoid copy constructors by not using accessors. |
192 | 1.40M | Profile(ID, Location, State, isSink()); |
193 | 1.40M | } |
194 | | |
195 | | /// addPredeccessor - Adds a predecessor to the current node, and |
196 | | /// in tandem add this node as a successor of the other node. |
197 | | void addPredecessor(ExplodedNode *V, ExplodedGraph &G); |
198 | | |
199 | 2.43M | unsigned succ_size() const { return Succs.size(); } |
200 | 2.64M | unsigned pred_size() const { return Preds.size(); } |
201 | 46.8k | bool succ_empty() const { return Succs.empty(); } |
202 | 10.5M | bool pred_empty() const { return Preds.empty(); } |
203 | | |
204 | 28.6M | bool isSink() const { return Succs.getFlag(); } |
205 | | |
206 | 36 | bool hasSinglePred() const { |
207 | 36 | return (pred_size() == 1); |
208 | 36 | } |
209 | | |
210 | 8.65M | ExplodedNode *getFirstPred() { |
211 | 8.58M | return pred_empty() ? nullptr71.4k : *(pred_begin()); |
212 | 8.65M | } |
213 | | |
214 | 8.58M | const ExplodedNode *getFirstPred() const { |
215 | 8.58M | return const_cast<ExplodedNode*>(this)->getFirstPred(); |
216 | 8.58M | } |
217 | | |
218 | 4.41k | ExplodedNode *getFirstSucc() { |
219 | 4.26k | return succ_empty() ? nullptr156 : *(succ_begin()); |
220 | 4.41k | } |
221 | | |
222 | 2.50k | const ExplodedNode *getFirstSucc() const { |
223 | 2.50k | return const_cast<ExplodedNode*>(this)->getFirstSucc(); |
224 | 2.50k | } |
225 | | |
226 | | // Iterators over successor and predecessor vertices. |
227 | | using succ_iterator = ExplodedNode * const *; |
228 | | using succ_range = llvm::iterator_range<succ_iterator>; |
229 | | |
230 | | using const_succ_iterator = const ExplodedNode * const *; |
231 | | using const_succ_range = llvm::iterator_range<const_succ_iterator>; |
232 | | |
233 | | using pred_iterator = ExplodedNode * const *; |
234 | | using pred_range = llvm::iterator_range<pred_iterator>; |
235 | | |
236 | | using const_pred_iterator = const ExplodedNode * const *; |
237 | | using const_pred_range = llvm::iterator_range<const_pred_iterator>; |
238 | | |
239 | 11.8M | pred_iterator pred_begin() { return Preds.begin(); } |
240 | 1.67M | pred_iterator pred_end() { return Preds.end(); } |
241 | 0 | pred_range preds() { return {Preds.begin(), Preds.end()}; } |
242 | | |
243 | 2.95M | const_pred_iterator pred_begin() const { |
244 | 2.95M | return const_cast<ExplodedNode*>(this)->pred_begin(); |
245 | 2.95M | } |
246 | 1.67M | const_pred_iterator pred_end() const { |
247 | 1.67M | return const_cast<ExplodedNode*>(this)->pred_end(); |
248 | 1.67M | } |
249 | 0 | const_pred_range preds() const { return {Preds.begin(), Preds.end()}; } |
250 | | |
251 | 1.43M | succ_iterator succ_begin() { return Succs.begin(); } |
252 | 19.2k | succ_iterator succ_end() { return Succs.end(); } |
253 | 0 | succ_range succs() { return {Succs.begin(), Succs.end()}; } |
254 | | |
255 | 1.12M | const_succ_iterator succ_begin() const { |
256 | 1.12M | return const_cast<ExplodedNode*>(this)->succ_begin(); |
257 | 1.12M | } |
258 | 18.8k | const_succ_iterator succ_end() const { |
259 | 18.8k | return const_cast<ExplodedNode*>(this)->succ_end(); |
260 | 18.8k | } |
261 | 1.81M | const_succ_range succs() const { return {Succs.begin(), Succs.end()}; } |
262 | | |
263 | 3.52M | int64_t getID() const { return Id; } |
264 | | |
265 | | /// The node is trivial if it has only one successor, only one predecessor, |
266 | | /// it's predecessor has only one successor, |
267 | | /// and its program state is the same as the program state of the previous |
268 | | /// node. |
269 | | /// Trivial nodes may be skipped while printing exploded graph. |
270 | | bool isTrivial() const; |
271 | | |
272 | | /// If the node's program point corresponds to a statement, retrieve that |
273 | | /// statement. Useful for figuring out where to put a warning or a note. |
274 | | /// If the statement belongs to a body-farmed definition, |
275 | | /// retrieve the call site for that definition. |
276 | | const Stmt *getStmtForDiagnostics() const; |
277 | | |
278 | | /// Find the next statement that was executed on this node's execution path. |
279 | | /// Useful for explaining control flow that follows the current node. |
280 | | /// If the statement belongs to a body-farmed definition, retrieve the |
281 | | /// call site for that definition. |
282 | | const Stmt *getNextStmtForDiagnostics() const; |
283 | | |
284 | | /// Find the statement that was executed immediately before this node. |
285 | | /// Useful when the node corresponds to a CFG block entrance. |
286 | | /// If the statement belongs to a body-farmed definition, retrieve the |
287 | | /// call site for that definition. |
288 | | const Stmt *getPreviousStmtForDiagnostics() const; |
289 | | |
290 | | /// Find the statement that was executed at or immediately before this node. |
291 | | /// Useful when any nearby statement will do. |
292 | | /// If the statement belongs to a body-farmed definition, retrieve the |
293 | | /// call site for that definition. |
294 | | const Stmt *getCurrentOrPreviousStmtForDiagnostics() const; |
295 | | |
296 | | private: |
297 | 312k | void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } |
298 | 312k | void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } |
299 | | }; |
300 | | |
301 | | using InterExplodedGraphMap = |
302 | | llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>; |
303 | | |
304 | | class ExplodedGraph { |
305 | | protected: |
306 | | friend class CoreEngine; |
307 | | |
308 | | // Type definitions. |
309 | | using NodeVector = std::vector<ExplodedNode *>; |
310 | | |
311 | | /// The roots of the simulation graph. Usually there will be only |
312 | | /// one, but clients are free to establish multiple subgraphs within a single |
313 | | /// SimulGraph. Moreover, these subgraphs can often merge when paths from |
314 | | /// different roots reach the same state at the same program location. |
315 | | NodeVector Roots; |
316 | | |
317 | | /// The nodes in the simulation graph which have been |
318 | | /// specially marked as the endpoint of an abstract simulation path. |
319 | | NodeVector EndNodes; |
320 | | |
321 | | /// Nodes - The nodes in the graph. |
322 | | llvm::FoldingSet<ExplodedNode> Nodes; |
323 | | |
324 | | /// BVC - Allocator and context for allocating nodes and their predecessor |
325 | | /// and successor groups. |
326 | | BumpVectorContext BVC; |
327 | | |
328 | | /// NumNodes - The number of nodes in the graph. |
329 | | int64_t NumNodes = 0; |
330 | | |
331 | | /// A list of recently allocated nodes that can potentially be recycled. |
332 | | NodeVector ChangedNodes; |
333 | | |
334 | | /// A list of nodes that can be reused. |
335 | | NodeVector FreeNodes; |
336 | | |
337 | | /// Determines how often nodes are reclaimed. |
338 | | /// |
339 | | /// If this is 0, nodes will never be reclaimed. |
340 | | unsigned ReclaimNodeInterval = 0; |
341 | | |
342 | | /// Counter to determine when to reclaim nodes. |
343 | | unsigned ReclaimCounter; |
344 | | |
345 | | public: |
346 | | ExplodedGraph(); |
347 | | ~ExplodedGraph(); |
348 | | |
349 | | /// Retrieve the node associated with a (Location,State) pair, |
350 | | /// where the 'Location' is a ProgramPoint in the CFG. If no node for |
351 | | /// this pair exists, it is created. IsNew is set to true if |
352 | | /// the node was freshly created. |
353 | | ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State, |
354 | | bool IsSink = false, |
355 | | bool* IsNew = nullptr); |
356 | | |
357 | | /// Create a node for a (Location, State) pair, |
358 | | /// but don't store it for deduplication later. This |
359 | | /// is useful when copying an already completed |
360 | | /// ExplodedGraph for further processing. |
361 | | ExplodedNode *createUncachedNode(const ProgramPoint &L, |
362 | | ProgramStateRef State, |
363 | | int64_t Id, |
364 | | bool IsSink = false); |
365 | | |
366 | 14.2k | std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const { |
367 | 14.2k | return std::make_unique<ExplodedGraph>(); |
368 | 14.2k | } |
369 | | |
370 | | /// addRoot - Add an untyped node to the set of roots. |
371 | 42.1k | ExplodedNode *addRoot(ExplodedNode *V) { |
372 | 42.1k | Roots.push_back(V); |
373 | 42.1k | return V; |
374 | 42.1k | } |
375 | | |
376 | | /// addEndOfPath - Add an untyped node to the set of EOP nodes. |
377 | 20.6k | ExplodedNode *addEndOfPath(ExplodedNode *V) { |
378 | 20.6k | EndNodes.push_back(V); |
379 | 20.6k | return V; |
380 | 20.6k | } |
381 | | |
382 | 27.9k | unsigned num_roots() const { return Roots.size(); } |
383 | 0 | unsigned num_eops() const { return EndNodes.size(); } |
384 | | |
385 | 0 | bool empty() const { return NumNodes == 0; } |
386 | 0 | unsigned size() const { return NumNodes; } |
387 | | |
388 | 13.6k | void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); } |
389 | | |
390 | | // Iterators. |
391 | | using NodeTy = ExplodedNode; |
392 | | using AllNodesTy = llvm::FoldingSet<ExplodedNode>; |
393 | | using roots_iterator = NodeVector::iterator; |
394 | | using const_roots_iterator = NodeVector::const_iterator; |
395 | | using eop_iterator = NodeVector::iterator; |
396 | | using const_eop_iterator = NodeVector::const_iterator; |
397 | | using node_iterator = AllNodesTy::iterator; |
398 | | using const_node_iterator = AllNodesTy::const_iterator; |
399 | | |
400 | 396 | node_iterator nodes_begin() { return Nodes.begin(); } |
401 | | |
402 | 653 | node_iterator nodes_end() { return Nodes.end(); } |
403 | | |
404 | 0 | const_node_iterator nodes_begin() const { return Nodes.begin(); } |
405 | | |
406 | 0 | const_node_iterator nodes_end() const { return Nodes.end(); } |
407 | | |
408 | 15.4k | roots_iterator roots_begin() { return Roots.begin(); } |
409 | | |
410 | 0 | roots_iterator roots_end() { return Roots.end(); } |
411 | | |
412 | 0 | const_roots_iterator roots_begin() const { return Roots.begin(); } |
413 | | |
414 | 0 | const_roots_iterator roots_end() const { return Roots.end(); } |
415 | | |
416 | 0 | eop_iterator eop_begin() { return EndNodes.begin(); } |
417 | | |
418 | 0 | eop_iterator eop_end() { return EndNodes.end(); } |
419 | | |
420 | 0 | const_eop_iterator eop_begin() const { return EndNodes.begin(); } |
421 | | |
422 | 0 | const_eop_iterator eop_end() const { return EndNodes.end(); } |
423 | | |
424 | 5.72M | llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); } |
425 | 82.8k | BumpVectorContext &getNodeAllocator() { return BVC; } |
426 | | |
427 | | using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>; |
428 | | |
429 | | /// Creates a trimmed version of the graph that only contains paths leading |
430 | | /// to the given nodes. |
431 | | /// |
432 | | /// \param Nodes The nodes which must appear in the final graph. Presumably |
433 | | /// these are end-of-path nodes (i.e. they have no successors). |
434 | | /// \param[out] ForwardMap A optional map from nodes in this graph to nodes in |
435 | | /// the returned graph. |
436 | | /// \param[out] InverseMap An optional map from nodes in the returned graph to |
437 | | /// nodes in this graph. |
438 | | /// \returns The trimmed graph |
439 | | std::unique_ptr<ExplodedGraph> |
440 | | trim(ArrayRef<const NodeTy *> Nodes, |
441 | | InterExplodedGraphMap *ForwardMap = nullptr, |
442 | | InterExplodedGraphMap *InverseMap = nullptr) const; |
443 | | |
444 | | /// Enable tracking of recently allocated nodes for potential reclamation |
445 | | /// when calling reclaimRecentlyAllocatedNodes(). |
446 | 13.7k | void enableNodeReclamation(unsigned Interval) { |
447 | 13.7k | ReclaimCounter = ReclaimNodeInterval = Interval; |
448 | 13.7k | } |
449 | | |
450 | | /// Reclaim "uninteresting" nodes created since the last time this method |
451 | | /// was called. |
452 | | void reclaimRecentlyAllocatedNodes(); |
453 | | |
454 | | /// Returns true if nodes for the given expression kind are always |
455 | | /// kept around. |
456 | | static bool isInterestingLValueExpr(const Expr *Ex); |
457 | | |
458 | | private: |
459 | | bool shouldCollect(const ExplodedNode *node); |
460 | | void collectNode(ExplodedNode *node); |
461 | | }; |
462 | | |
463 | | class ExplodedNodeSet { |
464 | | using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>; |
465 | | ImplTy Impl; |
466 | | |
467 | | public: |
468 | 1.44M | ExplodedNodeSet(ExplodedNode *N) { |
469 | 1.44M | assert(N && !static_cast<ExplodedNode*>(N)->isSink()); |
470 | 1.44M | Impl.insert(N); |
471 | 1.44M | } |
472 | | |
473 | 10.5M | ExplodedNodeSet() = default; |
474 | | |
475 | 4.30M | void Add(ExplodedNode *N) { |
476 | 4.30M | if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N); |
477 | 4.30M | } |
478 | | |
479 | | using iterator = ImplTy::iterator; |
480 | | using const_iterator = ImplTy::const_iterator; |
481 | | |
482 | 43.3k | unsigned size() const { return Impl.size(); } |
483 | 14.6M | bool empty() const { return Impl.empty(); } |
484 | 2.87M | bool erase(ExplodedNode *N) { return Impl.remove(N); } |
485 | | |
486 | 2.40M | void clear() { Impl.clear(); } |
487 | | |
488 | 8.09M | void insert(const ExplodedNodeSet &S) { |
489 | 8.09M | assert(&S != this); |
490 | 8.09M | if (empty()) |
491 | 8.05M | Impl = S.Impl; |
492 | 44.4k | else |
493 | 44.4k | Impl.insert(S.begin(), S.end()); |
494 | 8.09M | } |
495 | | |
496 | 8.91M | iterator begin() { return Impl.begin(); } |
497 | 8.89M | iterator end() { return Impl.end(); } |
498 | | |
499 | 4.15M | const_iterator begin() const { return Impl.begin(); } |
500 | 4.15M | const_iterator end() const { return Impl.end(); } |
501 | | }; |
502 | | |
503 | | } // namespace ento |
504 | | |
505 | | } // namespace clang |
506 | | |
507 | | // GraphTraits |
508 | | |
509 | | namespace llvm { |
510 | | template <> struct GraphTraits<clang::ento::ExplodedGraph *> { |
511 | | using GraphTy = clang::ento::ExplodedGraph *; |
512 | | using NodeRef = clang::ento::ExplodedNode *; |
513 | | using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; |
514 | | using nodes_iterator = llvm::df_iterator<GraphTy>; |
515 | | |
516 | 9 | static NodeRef getEntryNode(const GraphTy G) { |
517 | 9 | return *G->roots_begin(); |
518 | 9 | } |
519 | | |
520 | 1.50k | static bool predecessorOfTrivial(NodeRef N) { |
521 | 1.50k | return N->succ_size() == 1 && N->getFirstSucc()->isTrivial()1.44k ; |
522 | 1.50k | } |
523 | | |
524 | 648 | static ChildIteratorType child_begin(NodeRef N) { |
525 | 648 | if (predecessorOfTrivial(N)) |
526 | 348 | return child_begin(*N->succ_begin()); |
527 | 300 | return N->succ_begin(); |
528 | 300 | } |
529 | | |
530 | 855 | static ChildIteratorType child_end(NodeRef N) { |
531 | 855 | if (predecessorOfTrivial(N)) |
532 | 464 | return child_end(N->getFirstSucc()); |
533 | 391 | return N->succ_end(); |
534 | 391 | } |
535 | | |
536 | 9 | static nodes_iterator nodes_begin(const GraphTy G) { |
537 | 9 | return df_begin(G); |
538 | 9 | } |
539 | | |
540 | 9 | static nodes_iterator nodes_end(const GraphTy G) { |
541 | 9 | return df_end(G); |
542 | 9 | } |
543 | | }; |
544 | | } // namespace llvm |
545 | | |
546 | | #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H |