[Analyzer] Don't cache report generation ExplodedNodes

[bcraig]

Summary

During the core analysis, ExplodedNodes are added to the ExplodedGraph, and those nodes are cached for deduplication purposes.

After core analysis, reports are generated. Here, trimmed copies of the ExplodedGraph are made. Since the ExplodedGraph has already been deduplicated, there is no need to deduplicate again.

This change makes it possible to add ExplodedNodes to an ExplodedGraph without the overhead of deduplication. "Uncached" nodes also cannot be iterated over, but none of the report generation code attempts to iterate over all nodes. This change reduces the analysis time of a large .C file from 3m43.941s to 3m40.256s (~1.6% speedup). It should slightly reduce memory consumption. Gains should be roughly proportional to the number (and path length) of static analysis warnings.

This patch enables future work that should remove the need for an InterExplodedGraphMap inverse map. I plan on using the (now unused) ExplodedNode link to connect new nodes to the original nodes.

[zaks.anna]

LGTM. Please, measure that this does not regress memory consumption just to be sure.

Thanks!
Anna.

[bcraig]

Old: 106,657,666
New: 105,346,818

Submitted in r273572

include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

public:
   /// \brief Retrieve the node associated with a (Location,State) pair,
   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
   ///  this pair exists, it is created. IsNew is set to true if
   ///  the node was freshly created.
   ExplodedNode *getNode(const ProgramPoint &L, ProgramStateRef State,
                         bool IsSink = false,
                         bool* IsNew = nullptr);
 
+  /// \brief Create a node for a (Location, State) pair,
+  ///  but don't store it for deduplication later.  This
+  ///  is useful when copying an already completed
+  ///  ExplodedGraph for further processing.
+  ExplodedNode *createUncachedNode(const ProgramPoint &L,
+    ProgramStateRef State,
+    bool IsSink = false);
+
   std::unique_ptr<ExplodedGraph> MakeEmptyGraph() const {
     return llvm::make_unique<ExplodedGraph>();
   }
 
   /// addRoot - Add an untyped node to the set of roots.
   ExplodedNode *addRoot(ExplodedNode *V) {
     Roots.push_back(V);
     return V;

lib/StaticAnalyzer/Core/BugReporter.cpp

bool TrimmedGraph::popNextReportGraph(ReportGraph &GraphWrapper) {
   GraphWrapper.BackMap.clear();
 
   // Now walk from the error node up the BFS path, always taking the
   // predeccessor with the lowest number.
   ExplodedNode *Succ = nullptr;
   while (true) {
     // Create the equivalent node in the new graph with the same state
     // and location.
-    ExplodedNode *NewN = GNew->getNode(OrigN->getLocation(), OrigN->getState(),
+    ExplodedNode *NewN = GNew->createUncachedNode(OrigN->getLocation(), OrigN->getState(),
                                        OrigN->isSink());
 
     // Store the mapping to the original node.
     InterExplodedGraphMap::const_iterator IMitr = InverseMap.find(OrigN);
     assert(IMitr != InverseMap.end() && "No mapping to original node.");
     GraphWrapper.BackMap[NewN] = IMitr->second;
 
     // Link up the new node with the previous node.

lib/StaticAnalyzer/Core/ExplodedGraph.cpp

if (!V) {
     if (IsNew) *IsNew = true;
   }
   else
     if (IsNew) *IsNew = false;
 
   return V;
 }
 
+ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
+                                                ProgramStateRef State,
+                                                bool IsSink) {
+  NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
+  new (V) NodeTy(L, State, IsSink);
+  return V;
+}
+
 std::unique_ptr<ExplodedGraph>
 ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
                     InterExplodedGraphMap *ForwardMap,
                     InterExplodedGraphMap *InverseMap) const {
 
   if (Nodes.empty())
     return nullptr;
 
while (!WL2.empty()) {
     const ExplodedNode *N = WL2.pop_back_val();
 
     // Skip this node if we have already processed it.
     if (Pass2.find(N) != Pass2.end())
       continue;
 
     // Create the corresponding node in the new graph and record the mapping
     // from the old node to the new node.
-    ExplodedNode *NewN = G->getNode(N->getLocation(), N->State, N->isSink(),
-                                    nullptr);
+    ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
     Pass2[N] = NewN;
 
     // Also record the reverse mapping from the new node to the old node.
     if (InverseMap) (*InverseMap)[NewN] = N;
 
     // If this node is a root, designate it as such in the graph.
     if (N->Preds.empty())
       G->addRoot(NewN);