ExplodedGraph.h revision 11062b118476368fa5b294954713e5df97d8599f
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// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 16#define LLVM_CLANG_ANALYSIS_EXPLODEDGRAPH 17 18#include "clang/Analysis/ProgramPoint.h" 19#include "clang/AST/Decl.h" 20#include "llvm/ADT/SmallVector.h" 21#include "llvm/ADT/FoldingSet.h" 22#include "llvm/ADT/SmallPtrSet.h" 23#include "llvm/Support/Allocator.h" 24#include "llvm/ADT/OwningPtr.h" 25#include "llvm/ADT/GraphTraits.h" 26#include "llvm/ADT/DepthFirstIterator.h" 27#include "llvm/Support/Casting.h" 28 29namespace clang { 30 31class GRCoreEngineImpl; 32class ExplodedNodeImpl; 33class CFG; 34class ASTContext; 35 36class GRStmtNodeBuilderImpl; 37class GRBranchNodeBuilderImpl; 38class GRIndirectGotoNodeBuilderImpl; 39class GRSwitchNodeBuilderImpl; 40class GREndPathNodebuilderImpl; 41 42class ExplodedNodeImpl : public llvm::FoldingSetNode { 43protected: 44 friend class ExplodedGraphImpl; 45 friend class GRCoreEngineImpl; 46 friend class GRStmtNodeBuilderImpl; 47 friend class GRBranchNodeBuilderImpl; 48 friend class GRIndirectGotoNodeBuilderImpl; 49 friend class GRSwitchNodeBuilderImpl; 50 friend class GREndPathNodeBuilderImpl; 51 52 class NodeGroup { 53 enum { Size1 = 0x0, SizeOther = 0x1, AuxFlag = 0x2, Mask = 0x3 }; 54 uintptr_t P; 55 56 unsigned getKind() const { 57 return P & 0x1; 58 } 59 60 void* getPtr() const { 61 assert (!getFlag()); 62 return reinterpret_cast<void*>(P & ~Mask); 63 } 64 65 ExplodedNodeImpl* getNode() const { 66 return reinterpret_cast<ExplodedNodeImpl*>(getPtr()); 67 } 68 69 public: 70 NodeGroup() : P(0) {} 71 72 ~NodeGroup(); 73 74 ExplodedNodeImpl** begin() const; 75 76 ExplodedNodeImpl** end() const; 77 78 unsigned size() const; 79 80 bool empty() const { return size() == 0; } 81 82 void addNode(ExplodedNodeImpl* N); 83 84 void setFlag() { 85 assert (P == 0); 86 P = AuxFlag; 87 } 88 89 bool getFlag() const { 90 return P & AuxFlag ? true : false; 91 } 92 }; 93 94 /// Location - The program location (within a function body) associated 95 /// with this node. 96 const ProgramPoint Location; 97 98 /// State - The state associated with this node. Normally this value 99 /// is immutable, but we anticipate there will be times when algorithms 100 /// that directly manipulate the analysis graph will need to change it. 101 void* State; 102 103 /// Preds - The predecessors of this node. 104 NodeGroup Preds; 105 106 /// Succs - The successors of this node. 107 NodeGroup Succs; 108 109 /// Construct a ExplodedNodeImpl with the provided location and state. 110 explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state) 111 : Location(loc), State(state) {} 112 113 /// addPredeccessor - Adds a predecessor to the current node, and 114 /// in tandem add this node as a successor of the other node. 115 void addPredecessor(ExplodedNodeImpl* V) { 116 assert (!V->isSink()); 117 Preds.addNode(V); 118 V->Succs.addNode(this); 119 } 120 121public: 122 123 /// getLocation - Returns the edge associated with the given node. 124 ProgramPoint getLocation() const { return Location; } 125 126 unsigned succ_size() const { return Succs.size(); } 127 unsigned pred_size() const { return Preds.size(); } 128 bool succ_empty() const { return Succs.empty(); } 129 bool pred_empty() const { return Preds.empty(); } 130 131 bool isSink() const { return Succs.getFlag(); } 132 void markAsSink() { Succs.setFlag(); } 133}; 134 135 136template <typename StateTy> 137struct GRTrait { 138 static inline void Profile(llvm::FoldingSetNodeID& ID, const StateTy* St) { 139 St->Profile(ID); 140 } 141}; 142 143 144template <typename StateTy> 145class ExplodedNode : public ExplodedNodeImpl { 146public: 147 /// Construct a ExplodedNodeImpl with the given node ID, program edge, 148 /// and state. 149 explicit ExplodedNode(const ProgramPoint& loc, StateTy* St) 150 : ExplodedNodeImpl(loc, St) {} 151 152 /// getState - Returns the state associated with the node. 153 inline StateTy* getState() const { 154 return static_cast<StateTy*>(State); 155 } 156 157 // Profiling (for FoldingSet). 158 159 static inline void Profile(llvm::FoldingSetNodeID& ID, 160 const ProgramPoint& Loc, 161 StateTy* state) { 162 ID.Add(Loc); 163 GRTrait<StateTy>::Profile(ID, state); 164 } 165 166 inline void Profile(llvm::FoldingSetNodeID& ID) const { 167 Profile(ID, getLocation(), getState()); 168 } 169 170 // Iterators over successor and predecessor vertices. 171 typedef ExplodedNode** succ_iterator; 172 typedef const ExplodedNode** const_succ_iterator; 173 typedef ExplodedNode** pred_iterator; 174 typedef const ExplodedNode** const_pred_iterator; 175 176 pred_iterator pred_begin() { return (ExplodedNode**) Preds.begin(); } 177 pred_iterator pred_end() { return (ExplodedNode**) Preds.end(); } 178 179 const_pred_iterator pred_begin() const { 180 return const_cast<ExplodedNode*>(this)->pred_begin(); 181 } 182 const_pred_iterator pred_end() const { 183 return const_cast<ExplodedNode*>(this)->pred_end(); 184 } 185 186 succ_iterator succ_begin() { return (ExplodedNode**) Succs.begin(); } 187 succ_iterator succ_end() { return (ExplodedNode**) Succs.end(); } 188 189 const_succ_iterator succ_begin() const { 190 return const_cast<ExplodedNode*>(this)->succ_begin(); 191 } 192 const_succ_iterator succ_end() const { 193 return const_cast<ExplodedNode*>(this)->succ_end(); 194 } 195}; 196 197 198class ExplodedGraphImpl { 199protected: 200 friend class GRCoreEngineImpl; 201 friend class GRStmtNodeBuilderImpl; 202 friend class GRBranchNodeBuilderImpl; 203 friend class GRIndirectGotoNodeBuilderImpl; 204 friend class GRSwitchNodeBuilderImpl; 205 friend class GREndPathNodeBuilderImpl; 206 207 // Type definitions. 208 typedef llvm::SmallVector<ExplodedNodeImpl*,2> RootsTy; 209 typedef llvm::SmallVector<ExplodedNodeImpl*,10> EndNodesTy; 210 211 /// Roots - The roots of the simulation graph. Usually there will be only 212 /// one, but clients are free to establish multiple subgraphs within a single 213 /// SimulGraph. Moreover, these subgraphs can often merge when paths from 214 /// different roots reach the same state at the same program location. 215 RootsTy Roots; 216 217 /// EndNodes - The nodes in the simulation graph which have been 218 /// specially marked as the endpoint of an abstract simulation path. 219 EndNodesTy EndNodes; 220 221 /// Allocator - BumpPtrAllocator to create nodes. 222 llvm::BumpPtrAllocator Allocator; 223 224 /// cfg - The CFG associated with this analysis graph. 225 CFG& cfg; 226 227 /// CodeDecl - The declaration containing the code being analyzed. This 228 /// can be a FunctionDecl or and ObjCMethodDecl. 229 Decl& CodeDecl; 230 231 /// Ctx - The ASTContext used to "interpret" CodeDecl. 232 ASTContext& Ctx; 233 234 /// NumNodes - The number of nodes in the graph. 235 unsigned NumNodes; 236 237 /// getNodeImpl - Retrieve the node associated with a (Location,State) 238 /// pair, where 'State' is represented as an opaque void*. This method 239 /// is intended to be used only by GRCoreEngineImpl. 240 virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State, 241 bool* IsNew) = 0; 242 243 virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0; 244 245 /// addRoot - Add an untyped node to the set of roots. 246 ExplodedNodeImpl* addRoot(ExplodedNodeImpl* V) { 247 Roots.push_back(V); 248 return V; 249 } 250 251 /// addEndOfPath - Add an untyped node to the set of EOP nodes. 252 ExplodedNodeImpl* addEndOfPath(ExplodedNodeImpl* V) { 253 EndNodes.push_back(V); 254 return V; 255 } 256 257 // ctor. 258 ExplodedGraphImpl(CFG& c, Decl& cd, ASTContext& ctx) 259 : cfg(c), CodeDecl(cd), Ctx(ctx), NumNodes(0) {} 260 261public: 262 virtual ~ExplodedGraphImpl() {} 263 264 unsigned num_roots() const { return Roots.size(); } 265 unsigned num_eops() const { return EndNodes.size(); } 266 267 bool empty() const { return NumNodes == 0; } 268 unsigned size() const { return NumNodes; } 269 270 llvm::BumpPtrAllocator& getAllocator() { return Allocator; } 271 CFG& getCFG() { return cfg; } 272 ASTContext& getContext() { return Ctx; } 273 274 const Decl& getCodeDecl() const { return CodeDecl; } 275 276 const FunctionDecl* getFunctionDecl() const { 277 return llvm::dyn_cast<FunctionDecl>(&CodeDecl); 278 } 279 280 ExplodedGraphImpl* Trim(ExplodedNodeImpl** NBeg, 281 ExplodedNodeImpl** NEnd) const; 282 283}; 284 285template <typename STATE> 286class ExplodedGraph : public ExplodedGraphImpl { 287public: 288 typedef STATE StateTy; 289 typedef ExplodedNode<StateTy> NodeTy; 290 typedef llvm::FoldingSet<NodeTy> AllNodesTy; 291 292protected: 293 /// Nodes - The nodes in the graph. 294 AllNodesTy Nodes; 295 296protected: 297 virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, 298 void* State, bool* IsNew) { 299 300 return getNode(L, static_cast<StateTy*>(State), IsNew); 301 } 302 303 virtual ExplodedGraphImpl* MakeEmptyGraph() const { 304 return new ExplodedGraph(cfg, CodeDecl, Ctx); 305 } 306 307public: 308 ExplodedGraph(CFG& c, Decl& cd, ASTContext& ctx) 309 : ExplodedGraphImpl(c, cd, ctx) {} 310 311 /// getNode - Retrieve the node associated with a (Location,State) pair, 312 /// where the 'Location' is a ProgramPoint in the CFG. If no node for 313 /// this pair exists, it is created. IsNew is set to true if 314 /// the node was freshly created. 315 NodeTy* getNode(const ProgramPoint& L, StateTy* State, bool* IsNew = NULL) { 316 317 // Profile 'State' to determine if we already have an existing node. 318 llvm::FoldingSetNodeID profile; 319 void* InsertPos = 0; 320 321 NodeTy::Profile(profile, L, State); 322 NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos); 323 324 if (!V) { 325 // Allocate a new node. 326 V = (NodeTy*) Allocator.Allocate<NodeTy>(); 327 new (V) NodeTy(L, State); 328 329 // Insert the node into the node set and return it. 330 Nodes.InsertNode(V, InsertPos); 331 332 ++NumNodes; 333 334 if (IsNew) *IsNew = true; 335 } 336 else 337 if (IsNew) *IsNew = false; 338 339 return V; 340 } 341 342 // Iterators. 343 typedef NodeTy** roots_iterator; 344 typedef const NodeTy** const_roots_iterator; 345 typedef NodeTy** eop_iterator; 346 typedef const NodeTy** const_eop_iterator; 347 typedef typename AllNodesTy::iterator node_iterator; 348 typedef typename AllNodesTy::const_iterator const_node_iterator; 349 350 node_iterator nodes_begin() { 351 return Nodes.begin(); 352 } 353 354 node_iterator nodes_end() { 355 return Nodes.end(); 356 } 357 358 const_node_iterator nodes_begin() const { 359 return Nodes.begin(); 360 } 361 362 const_node_iterator nodes_end() const { 363 return Nodes.end(); 364 } 365 366 roots_iterator roots_begin() { 367 return reinterpret_cast<roots_iterator>(Roots.begin()); 368 } 369 370 roots_iterator roots_end() { 371 return reinterpret_cast<roots_iterator>(Roots.end()); 372 } 373 374 const_roots_iterator roots_begin() const { 375 return const_cast<ExplodedGraph>(this)->roots_begin(); 376 } 377 378 const_roots_iterator roots_end() const { 379 return const_cast<ExplodedGraph>(this)->roots_end(); 380 } 381 382 eop_iterator eop_begin() { 383 return reinterpret_cast<eop_iterator>(EndNodes.begin()); 384 } 385 386 eop_iterator eop_end() { 387 return reinterpret_cast<eop_iterator>(EndNodes.end()); 388 } 389 390 const_eop_iterator eop_begin() const { 391 return const_cast<ExplodedGraph>(this)->eop_begin(); 392 } 393 394 const_eop_iterator eop_end() const { 395 return const_cast<ExplodedGraph>(this)->eop_end(); 396 } 397 398 // Utility. 399 400 ExplodedGraph* Trim(NodeTy** NBeg, NodeTy** NEnd) const { 401 402 if (NBeg == NEnd) 403 return NULL; 404 405 assert (NBeg < NEnd); 406 407 ExplodedNodeImpl** NBegImpl = (ExplodedNodeImpl**) NBeg; 408 ExplodedNodeImpl** NEndImpl = (ExplodedNodeImpl**) NEnd; 409 410 return static_cast<ExplodedGraph*>(ExplodedGraphImpl::Trim(NBegImpl, 411 NEndImpl)); 412 } 413}; 414 415 416template <typename StateTy> 417class ExplodedNodeSet { 418 419 typedef ExplodedNode<StateTy> NodeTy; 420 typedef llvm::SmallPtrSet<NodeTy*,5> ImplTy; 421 ImplTy Impl; 422 423public: 424 ExplodedNodeSet(NodeTy* N) { 425 assert (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()); 426 Impl.insert(N); 427 } 428 429 ExplodedNodeSet() {} 430 431 inline void Add(NodeTy* N) { 432 if (N && !static_cast<ExplodedNodeImpl*>(N)->isSink()) Impl.insert(N); 433 } 434 435 typedef typename ImplTy::iterator iterator; 436 typedef typename ImplTy::const_iterator const_iterator; 437 438 inline unsigned size() const { return Impl.size(); } 439 inline bool empty() const { return Impl.empty(); } 440 441 inline void clear() { Impl.clear(); } 442 443 inline iterator begin() { return Impl.begin(); } 444 inline iterator end() { return Impl.end(); } 445 446 inline const_iterator begin() const { return Impl.begin(); } 447 inline const_iterator end() const { return Impl.end(); } 448}; 449 450} // end clang namespace 451 452// GraphTraits 453 454namespace llvm { 455 template<typename StateTy> 456 struct GraphTraits<clang::ExplodedNode<StateTy>*> { 457 typedef clang::ExplodedNode<StateTy> NodeType; 458 typedef typename NodeType::succ_iterator ChildIteratorType; 459 typedef llvm::df_iterator<NodeType*> nodes_iterator; 460 461 static inline NodeType* getEntryNode(NodeType* N) { 462 return N; 463 } 464 465 static inline ChildIteratorType child_begin(NodeType* N) { 466 return N->succ_begin(); 467 } 468 469 static inline ChildIteratorType child_end(NodeType* N) { 470 return N->succ_end(); 471 } 472 473 static inline nodes_iterator nodes_begin(NodeType* N) { 474 return df_begin(N); 475 } 476 477 static inline nodes_iterator nodes_end(NodeType* N) { 478 return df_end(N); 479 } 480 }; 481 482 template<typename StateTy> 483 struct GraphTraits<const clang::ExplodedNode<StateTy>*> { 484 typedef const clang::ExplodedNode<StateTy> NodeType; 485 typedef typename NodeType::succ_iterator ChildIteratorType; 486 typedef llvm::df_iterator<NodeType*> nodes_iterator; 487 488 static inline NodeType* getEntryNode(NodeType* N) { 489 return N; 490 } 491 492 static inline ChildIteratorType child_begin(NodeType* N) { 493 return N->succ_begin(); 494 } 495 496 static inline ChildIteratorType child_end(NodeType* N) { 497 return N->succ_end(); 498 } 499 500 static inline nodes_iterator nodes_begin(NodeType* N) { 501 return df_begin(N); 502 } 503 504 static inline nodes_iterator nodes_end(NodeType* N) { 505 return df_end(N); 506 } 507 }; 508 509} // end llvm namespace 510 511#endif 512