[LCG] Actually test the *basic* edge removal bits (IE, the non-SCC

bits), and discover that it's totally broken. Yay tests. Boo bug. Fix
the basic edge removal so that it works by nulling out the removed edges
rather than actually removing them. This leaves the indices valid in the
map from callee to index, and preserves some of the locality for
iterating over edges. The iterator is made bidirectional to reflect that
it now has to skip over null entries, and the skipping logic is layered
onto it.

As future work, I would like to track essentially the "load factor" of
the edge list, and when it falls below a threshold do a compaction.

An alternative I considered (and continue to consider) is storing the
callees in a doubly linked list where each element of the list is in
a set (which is essentially the classical linked-hash-table
datastructure). The problem with that approach is that either you need
to heap allocate the linked list nodes and use pointers to them, or use
a bucket hash table (with even *more* linked list pointer overhead!),
etc. It's pretty easy to get 5x overhead for values that are just
pointers. So far, I think punching holes in the vector, and periodic
compaction is likely to be much more efficient overall in the space/time
tradeoff.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207619 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index 7f9a43aba36f17a0641755c70e69e3abe19b2512..df3925aba63319510c3541a44e83019b84d4a737 100644 (file)
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -115,7 +115,7 @@ public:
   /// the graph.
   class iterator
       : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator,
-                                     std::random_access_iterator_tag, Node> {
+                                     std::bidirectional_iterator_tag, Node> {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
@@ -124,11 +124,30 @@ public:
 
     // Build the iterator for a specific position in a node list.
     iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI)
-        : iterator_adaptor_base(NI), G(&G) {}
+        : iterator_adaptor_base(NI), G(&G) {
+      while (I->isNull())
+        ++I;
+    }
 
   public:
     iterator() {}
 
+    using iterator_adaptor_base::operator++;
+    iterator &operator++() {
+      do {
+        ++I;
+      } while (I->isNull());
+      return *this;
+    }
+
+    using iterator_adaptor_base::operator--;
+    iterator &operator--() {
+      do {
+        --I;
+      } while (I->isNull());
+      return *this;
+    }
+
     reference operator*() const {
       if (I->is<Node *>())
         return *I->get<Node *>();

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 05757e1e2f5830b279479152c15433310369af03..dd940a98f3b0b812a97218b73a5183fa910daa13 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -88,7 +88,7 @@ void LazyCallGraph::Node::removeEdgeInternal(Function &Callee) {
   assert(IndexMapI != CalleeIndexMap.end() &&
          "Callee not in the callee set for this caller?");
 
-  Callees.erase(Callees.begin() + IndexMapI->second);
+  Callees[IndexMapI->second] = nullptr;
   CalleeIndexMap.erase(IndexMapI);
 }
 
@@ -115,11 +115,14 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
                   "entry set.\n");
   findCallees(Worklist, Visited, EntryNodes, EntryIndexMap);
 
-  for (auto &Entry : EntryNodes)
+  for (auto &Entry : EntryNodes) {
+    assert(!Entry.isNull() &&
+           "We can't have removed edges before we finish the constructor!");
     if (Function *F = Entry.dyn_cast<Function *>())
       SCCEntryNodes.push_back(F);
     else
       SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction());
+  }
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
@@ -391,8 +394,9 @@ void LazyCallGraph::updateGraphPtrs() {
       Node *N = Worklist.pop_back_val();
       N->G = this;
       for (auto &Callee : N->Callees)
-        if (Node *CalleeN = Callee.dyn_cast<Node *>())
-          Worklist.push_back(CalleeN);
+        if (!Callee.isNull())
+          if (Node *CalleeN = Callee.dyn_cast<Node *>())
+            Worklist.push_back(CalleeN);
     }
   }
 

diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index 92b98418794bcdcea951aad8642765f89278b294..4ef77f632e79ea5e5aa21a527a6fcf3c98763207 100644 (file)
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -290,7 +290,17 @@ TEST(LazyCallGraphTest, BasicGraphMutation) {
   CG.insertEdge(C, C.getFunction());
   EXPECT_EQ(2, std::distance(C.begin(), C.end()));
   EXPECT_EQ(&B, &*C.begin());
-  EXPECT_EQ(&C, &*(C.begin() + 1));
+  EXPECT_EQ(&C, &*std::next(C.begin()));
+
+  CG.removeEdge(C, B.getFunction());
+  EXPECT_EQ(1, std::distance(C.begin(), C.end()));
+  EXPECT_EQ(&C, &*C.begin());
+
+  CG.removeEdge(C, C.getFunction());
+  EXPECT_EQ(0, std::distance(C.begin(), C.end()));
+
+  CG.removeEdge(B, C.getFunction());
+  EXPECT_EQ(0, std::distance(B.begin(), B.end()));
 }
 
 TEST(LazyCallGraphTest, MultiArmSCC) {