ExplodedGraph.h revision 353358
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 44namespace clang { 45 46class CFG; 47class Decl; 48class Expr; 49class ParentMap; 50class Stmt; 51 52namespace ento { 53 54class 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 65class 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 134public: 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 255private: 256 void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); } 257 void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); } 258}; 259 260using InterExplodedGraphMap = 261 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>; 262 263class ExplodedGraph { 264protected: 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 304public: 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 416private: 417 bool shouldCollect(const ExplodedNode *node); 418 void collectNode(ExplodedNode *node); 419}; 420 421class ExplodedNodeSet { 422 using ImplTy = llvm::SmallSetVector<ExplodedNode *, 4>; 423 ImplTy Impl; 424 425public: 426 ExplodedNodeSet(ExplodedNode *N) { 427 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 467namespace 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