ExplodedGraph.h source code [clang_source_code/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h]

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	NodeGroup(bool Flag = false) : P(Flag) {
92	assert(getFlag() == Flag);
93	}
94
95	ExplodedNode * const *begin() const;
96
97	ExplodedNode * const *end() const;
98
99	unsigned size() const;
100
101	bool empty() const { return P == 0 \|\| getFlag() != 0; }
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	bool getFlag() const {
117	return (P & 1);
118	}
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	public:
135	explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state,
136	bool IsSink)
137	: Location(loc), State(std::move(state)), Succs(IsSink) {
138	assert(isSink() == IsSink);
139	}
140
141	/// getLocation - Returns the edge associated with the given node.
142	ProgramPoint getLocation() const { return Location; }
143
144	const LocationContext *getLocationContext() const {
145	return getLocation().getLocationContext();
146	}
147
148	const StackFrameContext *getStackFrame() const {
149	return getLocation().getStackFrame();
150	}
151
152	const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); }
153
154	CFG &getCFG() const { return *getLocationContext()->getCFG(); }
155
156	ParentMap &getParentMap() const {return getLocationContext()->getParentMap();}
157
158	template <typename T>
159	T &getAnalysis() const {
160	return *getLocationContext()->getAnalysis<T>();
161	}
162
163	const ProgramStateRef &getState() const { return State; }
164
165	template <typename T>
166	Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION {
167	return Location.getAs<T>();
168	}
169
170	/// Get the value of an arbitrary expression at this node.
171	SVal getSVal(const Stmt *S) const {
172	return getState()->getSVal(S, getLocationContext());
173	}
174
175	static void Profile(llvm::FoldingSetNodeID &ID,
176	const ProgramPoint &Loc,
177	const ProgramStateRef &state,
178	bool IsSink) {
179	ID.Add(Loc);
180	ID.AddPointer(state.get());
181	ID.AddBoolean(IsSink);
182	}
183
184	void Profile(llvm::FoldingSetNodeID& ID) const {
185	// We avoid copy constructors by not using accessors.
186	Profile(ID, Location, State, isSink());
187	}
188
189	/// addPredeccessor - Adds a predecessor to the current node, and
190	/// in tandem add this node as a successor of the other node.
191	void addPredecessor(ExplodedNode *V, ExplodedGraph &G);
192
193	unsigned succ_size() const { return Succs.size(); }
194	unsigned pred_size() const { return Preds.size(); }
195	bool succ_empty() const { return Succs.empty(); }
196	bool pred_empty() const { return Preds.empty(); }
197
198	bool isSink() const { return Succs.getFlag(); }
199
200	bool hasSinglePred() const {
201	return (pred_size() == 1);
202	}
203
204	ExplodedNode *getFirstPred() {
205	return pred_empty() ? nullptr : *(pred_begin());
206	}
207
208	const ExplodedNode *getFirstPred() const {
209	return const_cast<ExplodedNode*>(this)->getFirstPred();
210	}
211
212	ExplodedNode *getFirstSucc() {
213	return succ_empty() ? nullptr : *(succ_begin());
214	}
215
216	const ExplodedNode *getFirstSucc() const {
217	return const_cast<ExplodedNode*>(this)->getFirstSucc();
218	}
219
220	// Iterators over successor and predecessor vertices.
221	using succ_iterator = ExplodedNode * const *;
222	using const_succ_iterator = const ExplodedNode * const *;
223	using pred_iterator = ExplodedNode * const *;
224	using const_pred_iterator = const ExplodedNode * const *;
225
226	pred_iterator pred_begin() { return Preds.begin(); }
227	pred_iterator pred_end() { return Preds.end(); }
228
229	const_pred_iterator pred_begin() const {
230	return const_cast<ExplodedNode*>(this)->pred_begin();
231	}
232	const_pred_iterator pred_end() const {
233	return const_cast<ExplodedNode*>(this)->pred_end();
234	}
235
236	succ_iterator succ_begin() { return Succs.begin(); }
237	succ_iterator succ_end() { return Succs.end(); }
238
239	const_succ_iterator succ_begin() const {
240	return const_cast<ExplodedNode*>(this)->succ_begin();
241	}
242	const_succ_iterator succ_end() const {
243	return const_cast<ExplodedNode*>(this)->succ_end();
244	}
245
246	int64_t getID(ExplodedGraph *G) const;
247
248	/// The node is trivial if it has only one successor, only one predecessor,
249	/// it's predecessor has only one successor,
250	/// and its program state is the same as the program state of the previous
251	/// node.
252	/// Trivial nodes may be skipped while printing exploded graph.
253	bool isTrivial() const;
254
255	private:
256	void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
257	void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
258	};
259
260	using InterExplodedGraphMap =
261	llvm::DenseMap<const ExplodedNode , const ExplodedNode >;
262
263	class ExplodedGraph {
264	protected:
265	friend class CoreEngine;
266
267	// Type definitions.
268	using NodeVector = std::vector<ExplodedNode *>;
269
270	/// The roots of the simulation graph. Usually there will be only
271	/// one, but clients are free to establish multiple subgraphs within a single
272	/// SimulGraph. Moreover, these subgraphs can often merge when paths from
273	/// different roots reach the same state at the same program location.
274	NodeVector Roots;
275
276	/// The nodes in the simulation graph which have been
277	/// specially marked as the endpoint of an abstract simulation path.
278	NodeVector EndNodes;
279
280	/// Nodes - The nodes in the graph.
281	llvm::FoldingSet<ExplodedNode> Nodes;
282
283	/// BVC - Allocator and context for allocating nodes and their predecessor
284	/// and successor groups.
285	BumpVectorContext BVC;
286
287	/// NumNodes - The number of nodes in the graph.
288	unsigned NumNodes = 0;
289
290	/// A list of recently allocated nodes that can potentially be recycled.
291	NodeVector ChangedNodes;
292
293	/// A list of nodes that can be reused.
294	NodeVector FreeNodes;
295
296	/// Determines how often nodes are reclaimed.
297	///
298	/// If this is 0, nodes will never be reclaimed.
299	unsigned ReclaimNodeInterval = 0;
300
301	/// Counter to determine when to reclaim nodes.
302	unsigned ReclaimCounter;
303
304	public:
305	ExplodedGraph();
306	~ExplodedGraph();
307
308	/// Retrieve the node associated with a (Location,State) pair,
309	/// where the 'Location' is a ProgramPoint in the CFG. If no node for
310	/// this pair exists, it is created. IsNew is set to true if
311	/// the node was freshly created.
312	ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
313	bool IsSink = false,
314	bool* IsNew = nullptr);
315
316	/// Create a node for a (Location, State) pair,
317	/// but don't store it for deduplication later. This
318	/// is useful when copying an already completed
319	/// ExplodedGraph for further processing.
320	ExplodedNode *createUncachedNode(const ProgramPoint &L,
321	ProgramStateRef State,
322	bool IsSink = false);
323
324	std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
325	return llvm::make_unique<ExplodedGraph>();
326	}
327
328	/// addRoot - Add an untyped node to the set of roots.
329	ExplodedNode addRoot(ExplodedNode V) {
330	Roots.push_back(V);
331	return V;
332	}
333
334	/// addEndOfPath - Add an untyped node to the set of EOP nodes.
335	ExplodedNode addEndOfPath(ExplodedNode V) {
336	EndNodes.push_back(V);
337	return V;
338	}
339
340	unsigned num_roots() const { return Roots.size(); }
341	unsigned num_eops() const { return EndNodes.size(); }
342
343	bool empty() const { return NumNodes == 0; }
344	unsigned size() const { return NumNodes; }
345
346	void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
347
348	// Iterators.
349	using NodeTy = ExplodedNode;
350	using AllNodesTy = llvm::FoldingSet<ExplodedNode>;
351	using roots_iterator = NodeVector::iterator;
352	using const_roots_iterator = NodeVector::const_iterator;
353	using eop_iterator = NodeVector::iterator;
354	using const_eop_iterator = NodeVector::const_iterator;
355	using node_iterator = AllNodesTy::iterator;
356	using const_node_iterator = AllNodesTy::const_iterator;
357
358	node_iterator nodes_begin() { return Nodes.begin(); }
359
360	node_iterator nodes_end() { return Nodes.end(); }
361
362	const_node_iterator nodes_begin() const { return Nodes.begin(); }
363
364	const_node_iterator nodes_end() const { return Nodes.end(); }
365
366	roots_iterator roots_begin() { return Roots.begin(); }
367
368	roots_iterator roots_end() { return Roots.end(); }
369
370	const_roots_iterator roots_begin() const { return Roots.begin(); }
371
372	const_roots_iterator roots_end() const { return Roots.end(); }
373
374	eop_iterator eop_begin() { return EndNodes.begin(); }
375
376	eop_iterator eop_end() { return EndNodes.end(); }
377
378	const_eop_iterator eop_begin() const { return EndNodes.begin(); }
379
380	const_eop_iterator eop_end() const { return EndNodes.end(); }
381
382	llvm::BumpPtrAllocator & getAllocator() { return BVC.getAllocator(); }
383	BumpVectorContext &getNodeAllocator() { return BVC; }
384
385	using NodeMap = llvm::DenseMap<const ExplodedNode , ExplodedNode >;
386
387	/// Creates a trimmed version of the graph that only contains paths leading
388	/// to the given nodes.
389	///
390	/// \param Nodes The nodes which must appear in the final graph. Presumably
391	/// these are end-of-path nodes (i.e. they have no successors).
392	/// \param[out] ForwardMap A optional map from nodes in this graph to nodes in
393	/// the returned graph.
394	/// \param[out] InverseMap An optional map from nodes in the returned graph to
395	/// nodes in this graph.
396	/// \returns The trimmed graph
397	std::unique_ptr<ExplodedGraph>
398	trim(ArrayRef<const NodeTy *> Nodes,
399	InterExplodedGraphMap *ForwardMap = nullptr,
400	InterExplodedGraphMap *InverseMap = nullptr) const;
401
402	/// Enable tracking of recently allocated nodes for potential reclamation
403	/// when calling reclaimRecentlyAllocatedNodes().
404	void enableNodeReclamation(unsigned Interval) {
405	ReclaimCounter = ReclaimNodeInterval = Interval;
406	}
407
408	/// Reclaim "uninteresting" nodes created since the last time this method
409	/// was called.
410	void reclaimRecentlyAllocatedNodes();
411
412	/// Returns true if nodes for the given expression kind are always
413	/// kept around.
414	static bool isInterestingLValueExpr(const Expr *Ex);
415
416	private:
417	bool shouldCollect(const ExplodedNode *node);
418	void collectNode(ExplodedNode *node);
419	};
420
421	class ExplodedNodeSet {
422	using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>;
423	ImplTy Impl;
424
425	public:
426	ExplodedNodeSet(ExplodedNode *N) {
427	(N)->isSink()", "/home/seafit/code_projects/clang_source/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h", 427, __PRETTY_FUNCTION__))" file_link="../../../../../../include/assert.h.html#88" macro="true">assert(N && !static_cast<ExplodedNode*>(N)->isSink());
428	Impl.insert(N);
429	}
430
431	ExplodedNodeSet() = default;
432
433	void Add(ExplodedNode *N) {
434	if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
435	}
436
437	using iterator = ImplTy::iterator;
438	using const_iterator = ImplTy::const_iterator;
439
440	unsigned size() const { return Impl.size(); }
441	bool empty() const { return Impl.empty(); }
442	bool erase(ExplodedNode *N) { return Impl.remove(N); }
443
444	void clear() { Impl.clear(); }
445
446	void insert(const ExplodedNodeSet &S) {
447	assert(&S != this);
448	if (empty())
449	Impl = S.Impl;
450	else
451	Impl.insert(S.begin(), S.end());
452	}
453
454	iterator begin() { return Impl.begin(); }
455	iterator end() { return Impl.end(); }
456
457	const_iterator begin() const { return Impl.begin(); }
458	const_iterator end() const { return Impl.end(); }
459	};
460
461	} // namespace ento
462
463	} // namespace clang
464
465	// GraphTraits
466
467	namespace llvm {
468	template <> struct GraphTraits<clang::ento::ExplodedGraph *> {
469	using GraphTy = clang::ento::ExplodedGraph *;
470	using NodeRef = clang::ento::ExplodedNode *;
471	using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
472	using nodes_iterator = llvm::df_iterator<GraphTy>;
473
474	static NodeRef getEntryNode(const GraphTy G) {
475	return *G->roots_begin();
476	}
477
478	static bool predecessorOfTrivial(NodeRef N) {
479	return N->succ_size() == 1 && N->getFirstSucc()->isTrivial();
480	}
481
482	static ChildIteratorType child_begin(NodeRef N) {
483	if (predecessorOfTrivial(N))
484	return child_begin(*N->succ_begin());
485	return N->succ_begin();
486	}
487
488	static ChildIteratorType child_end(NodeRef N) {
489	if (predecessorOfTrivial(N))
490	return child_end(N->getFirstSucc());
491	return N->succ_end();
492	}
493
494	static nodes_iterator nodes_begin(const GraphTy G) {
495	return df_begin(G);
496	}
497
498	static nodes_iterator nodes_end(const GraphTy G) {
499	return df_end(G);
500	}
501	};
502	} // namespace llvm
503
504	#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H
505