diff options
-rw-r--r-- | include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 19 | ||||
-rw-r--r-- | lib/StaticAnalyzer/Core/ExplodedGraph.cpp | 12 |
2 files changed, 31 insertions, 0 deletions
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index e60922e478..5ce219b4ed 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -60,10 +60,20 @@ class ExplodedNode : public llvm::FoldingSetNode { friend class SwitchNodeBuilder; friend class EndOfFunctionNodeBuilder; + /// Efficiently stores a list of ExplodedNodes, or an optional flag. + /// + /// NodeGroup provides opaque storage for a list of ExplodedNodes, optimizing + /// for the case when there is only one node in the group. This is a fairly + /// common case in an ExplodedGraph, where most nodes have only one + /// predecessor and many have only one successor. It can also be used to + /// store a flag rather than a node list, which ExplodedNode uses to mark + /// whether a node is a sink. If the flag is set, the group is implicitly + /// empty and no nodes may be added. class NodeGroup { // Conceptually a discriminated union. If the low bit is set, the node is // a sink. If the low bit is not set, the pointer refers to the storage // for the nodes in the group. + // This is not a PointerIntPair in order to keep the storage type opaque. uintptr_t P; public: @@ -79,10 +89,19 @@ class ExplodedNode : public llvm::FoldingSetNode { bool empty() const { return P == 0 || getFlag() != 0; } + /// Adds a node to the list. + /// + /// The group must not have been created with its flag set. void addNode(ExplodedNode *N, ExplodedGraph &G); + /// Replaces the single node in this group with a new node. + /// + /// Note that this should only be used when you know the group was not + /// created with its flag set, and that the group is empty or contains + /// only a single node. void replaceNode(ExplodedNode *node); + /// Returns whether this group was created with its flag set. bool getFlag() const { return (P & 1); } diff --git a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp index 24d1c094d0..9145565d3a 100644 --- a/lib/StaticAnalyzer/Core/ExplodedGraph.cpp +++ b/lib/StaticAnalyzer/Core/ExplodedGraph.cpp @@ -162,6 +162,16 @@ void ExplodedGraph::reclaimRecentlyAllocatedNodes() { // ExplodedNode. //===----------------------------------------------------------------------===// +// An NodeGroup's storage type is actually very much like a TinyPtrVector: +// it can be either a pointer to a single ExplodedNode, or a pointer to a +// BumpVector allocated with the ExplodedGraph's allocator. This allows the +// common case of single-node NodeGroups to be implemented with no extra memory. +// +// Consequently, each of the NodeGroup methods have up to four cases to handle: +// 1. The flag is set and this group does not actually contain any nodes. +// 2. The group is empty, in which case the storage value is null. +// 3. The group contains a single node. +// 4. The group contains more than one node. typedef BumpVector<ExplodedNode *> ExplodedNodeVector; typedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage; @@ -175,6 +185,8 @@ void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) { } void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) { + assert(!getFlag()); + GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P); assert(Storage.is<ExplodedNode *>()); Storage = node; |