ExplodedGraph.h revision 341825
1//===- ExplodedGraph.h - Local, Path-Sens. "Exploded Graph" -----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the template classes ExplodedNode and ExplodedGraph, 11// which represent a path-sensitive, intra-procedural "exploded graph." 12// See "Precise interprocedural dataflow analysis via graph reachability" 13// by Reps, Horwitz, and Sagiv 14// (http://portal.acm.org/citation.cfm?id=199462) for the definition of an 15// exploded graph. 16// 17//===----------------------------------------------------------------------===// 18 19#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 20#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 21 22#include "clang/Analysis/AnalysisDeclContext.h" 23#include "clang/Analysis/ProgramPoint.h" 24#include "clang/Analysis/Support/BumpVector.h" 25#include "clang/Basic/LLVM.h" 26#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 27#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" 28#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 29#include "llvm/ADT/ArrayRef.h" 30#include "llvm/ADT/DenseMap.h" 31#include "llvm/ADT/DepthFirstIterator.h" 32#include "llvm/ADT/FoldingSet.h" 33#include "llvm/ADT/GraphTraits.h" 34#include "llvm/ADT/Optional.h" 35#include "llvm/ADT/STLExtras.h" 36#include "llvm/ADT/SetVector.h" 37#include "llvm/Support/Allocator.h" 38#include "llvm/Support/Compiler.h" 39#include <cassert> 40#include <cstdint> 41#include <memory> 42#include <utility> 43#include <vector> 44 45namespace clang { 46 47class CFG; 48class Decl; 49class Expr; 50class ParentMap; 51class Stmt; 52 53namespace ento { 54 55class ExplodedGraph; 56 57//===----------------------------------------------------------------------===// 58// ExplodedGraph "implementation" classes. These classes are not typed to 59// contain a specific kind of state. Typed-specialized versions are defined 60// on top of these classes. 61//===----------------------------------------------------------------------===// 62 63// ExplodedNode is not constified all over the engine because we need to add 64// successors to it at any time after creating it. 65 66class ExplodedNode : public llvm::FoldingSetNode { 67 friend class BranchNodeBuilder; 68 friend class CoreEngine; 69 friend class EndOfFunctionNodeBuilder; 70 friend class ExplodedGraph; 71 friend class IndirectGotoNodeBuilder; 72 friend class NodeBuilder; 73 friend class SwitchNodeBuilder; 74 75 /// Efficiently stores a list of ExplodedNodes, or an optional flag. 76 /// 77 /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing 78 /// for the case when there is only one node in the group. This is a fairly 79 /// common case in an ExplodedGraph, where most nodes have only one 80 /// predecessor and many have only one successor. It can also be used to 81 /// store a flag rather than a node list, which ExplodedNode uses to mark 82 /// whether a node is a sink. If the flag is set, the group is implicitly 83 /// empty and no nodes may be added. 84 class NodeGroup { 85 // Conceptually a discriminated union. If the low bit is set, the node is 86 // a sink. If the low bit is not set, the pointer refers to the storage 87 // for the nodes in the group. 88 // This is not a PointerIntPair in order to keep the storage type opaque. 89 uintptr_t P; 90 91 public: 92 NodeGroup(bool Flag = false) : P(Flag) { 93 assert(getFlag() == Flag); 94 } 95 96 ExplodedNode * const *begin() const; 97 98 ExplodedNode * const *end() const; 99 100 unsigned size() const; 101 102 bool empty() const { return P == 0 || getFlag() != 0; } 103 104 /// Adds a node to the list. 105 /// 106 /// The group must not have been created with its flag set. 107 void addNode(ExplodedNode *N, ExplodedGraph &G); 108 109 /// Replaces the single node in this group with a new node. 110 /// 111 /// Note that this should only be used when you know the group was not 112 /// created with its flag set, and that the group is empty or contains 113 /// only a single node. 114 void replaceNode(ExplodedNode *node); 115 116 /// Returns whether this group was created with its flag set. 117 bool getFlag() const { 118 return (P & 1); 119 } 120 }; 121 122 /// Location - The program location (within a function body) associated 123 /// with this node. 124 const ProgramPoint Location; 125 126 /// State - The state associated with this node. 127 ProgramStateRef State; 128 129 /// Preds - The predecessors of this node. 130 NodeGroup Preds; 131 132 /// Succs - The successors of this node. 133 NodeGroup Succs; 134 135public: 136 explicit ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, 137 bool IsSink) 138 : Location(loc), State(std::move(state)), Succs(IsSink) { 139 assert(isSink() == IsSink); 140 } 141 142 /// getLocation - Returns the edge associated with the given node. 143 ProgramPoint getLocation() const { return Location; } 144 145 const LocationContext *getLocationContext() const { 146 return getLocation().getLocationContext(); 147 } 148 149 const StackFrameContext *getStackFrame() const { 150 return getLocation().getStackFrame(); 151 } 152 153 const Decl &getCodeDecl() const { return *getLocationContext()->getDecl(); } 154 155 CFG &getCFG() const { return *getLocationContext()->getCFG(); } 156 157 ParentMap &getParentMap() const {return getLocationContext()->getParentMap();} 158 159 template <typename T> 160 T &getAnalysis() const { 161 return *getLocationContext()->getAnalysis<T>(); 162 } 163 164 const ProgramStateRef &getState() const { return State; } 165 166 template <typename T> 167 Optional<T> getLocationAs() const LLVM_LVALUE_FUNCTION { 168 return Location.getAs<T>(); 169 } 170 171 /// Get the value of an arbitrary expression at this node. 172 SVal getSVal(const Stmt *S) const { 173 return getState()->getSVal(S, getLocationContext()); 174 } 175 176 static void Profile(llvm::FoldingSetNodeID &ID, 177 const ProgramPoint &Loc, 178 const ProgramStateRef &state, 179 bool IsSink) { 180 ID.Add(Loc); 181 ID.AddPointer(state.get()); 182 ID.AddBoolean(IsSink); 183 } 184 185 void Profile(llvm::FoldingSetNodeID& ID) const { 186 // We avoid copy constructors by not using accessors. 187 Profile(ID, Location, State, isSink()); 188 } 189 190 /// addPredeccessor - Adds a predecessor to the current node, and 191 /// in tandem add this node as a successor of the other node. 192 void addPredecessor(ExplodedNode *V, ExplodedGraph &G); 193 194 unsigned succ_size() const { return Succs.size(); } 195 unsigned pred_size() const { return Preds.size(); } 196 bool succ_empty() const { return Succs.empty(); } 197 bool pred_empty() const { return Preds.empty(); } 198 199 bool isSink() const { return Succs.getFlag(); } 200 201 bool hasSinglePred() const { 202 return (pred_size() == 1); 203 } 204 205 ExplodedNode *getFirstPred() { 206 return pred_empty() ? nullptr : *(pred_begin()); 207 } 208 209 const ExplodedNode *getFirstPred() const { 210 return const_cast<ExplodedNode*>(this)->getFirstPred(); 211 } 212 213 const ExplodedNode *getFirstSucc() const { 214 return succ_empty() ? nullptr : *(succ_begin()); 215 } 216 217 // Iterators over successor and predecessor vertices. 218 using succ_iterator = ExplodedNode * const *; 219 using const_succ_iterator = const ExplodedNode * const *; 220 using pred_iterator = ExplodedNode * const *; 221 using const_pred_iterator = const ExplodedNode * const *; 222 223 pred_iterator pred_begin() { return Preds.begin(); } 224 pred_iterator pred_end() { return Preds.end(); } 225 226 const_pred_iterator pred_begin() const { 227 return const_cast<ExplodedNode*>(this)->pred_begin(); 228 } 229 const_pred_iterator pred_end() const { 230 return const_cast<ExplodedNode*>(this)->pred_end(); 231 } 232 233 succ_iterator succ_begin() { return Succs.begin(); } 234 succ_iterator succ_end() { return Succs.end(); } 235 236 const_succ_iterator succ_begin() const { 237 return const_cast<ExplodedNode*>(this)->succ_begin(); 238 } 239 const_succ_iterator succ_end() const { 240 return const_cast<ExplodedNode*>(this)->succ_end(); 241 } 242 243 // For debugging. 244 245public: 246 class Auditor { 247 public: 248 virtual ~Auditor(); 249 250 virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst) = 0; 251 }; 252 253 static void SetAuditor(Auditor* A); 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 469 template<> struct GraphTraits<clang::ento::ExplodedNode*> { 470 using NodeRef = clang::ento::ExplodedNode *; 471 using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator; 472 using nodes_iterator = llvm::df_iterator<NodeRef>; 473 474 static NodeRef getEntryNode(NodeRef N) { return N; } 475 476 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 477 478 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 479 480 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } 481 482 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } 483 }; 484 485 template<> struct GraphTraits<const clang::ento::ExplodedNode*> { 486 using NodeRef = const clang::ento::ExplodedNode *; 487 using ChildIteratorType = clang::ento::ExplodedNode::const_succ_iterator; 488 using nodes_iterator = llvm::df_iterator<NodeRef>; 489 490 static NodeRef getEntryNode(NodeRef N) { return N; } 491 492 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } 493 494 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } 495 496 static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); } 497 498 static nodes_iterator nodes_end(NodeRef N) { return df_end(N); } 499 }; 500 501} // namespace llvm 502 503#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H 504