[LCG] Add the really, *really* boring edge insertion case: adding an

[oota-llvm.git] / lib / Analysis / LazyCallGraph.cpp

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 1ac30769a520b20a3db9de979a43563d4569ac1f..6c4574f867cbfc7323136483c20c2ac16cf26abf 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -75,12 +75,25 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
   findCallees(Worklist, Visited, Callees, CalleeIndexMap);
 }
 
+void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) {
+  if (Node *N = G->lookup(Callee))
+    return insertEdgeInternal(*N);
+
+  CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size()));
+  Callees.push_back(&Callee);
+}
+
+void LazyCallGraph::Node::insertEdgeInternal(Node &CalleeN) {
+  CalleeIndexMap.insert(std::make_pair(&CalleeN.getFunction(), Callees.size()));
+  Callees.push_back(&CalleeN);
+}
+
 void LazyCallGraph::Node::removeEdgeInternal(Function &Callee) {
   auto IndexMapI = CalleeIndexMap.find(&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);
 }
 
@@ -107,11 +120,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)
@@ -146,6 +162,16 @@ void LazyCallGraph::SCC::insert(Node &N) {
   G->SCCMap[&N] = this;
 }
 
+void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
+  // First insert it into the caller.
+  CallerN.insertEdgeInternal(CalleeN);
+
+  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
+  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
+
+  // Nothing changes about this SCC or any other.
+}
+
 void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
   // First remove it from the node.
   CallerN.removeEdgeInternal(CalleeN.getFunction());
@@ -284,10 +310,8 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
   // First remove it from the node.
   CallerN.removeEdgeInternal(CalleeN.getFunction());
 
-  // We return a list of the resulting SCCs, where 'this' is always the first
-  // element.
+  // We return a list of the resulting *new* SCCs in postorder.
   SmallVector<SCC *, 1> ResultSCCs;
-  ResultSCCs.push_back(this);
 
   // Direct recursion doesn't impact the SCC graph at all.
   if (&CallerN == &CalleeN)
@@ -337,7 +361,7 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
     }
   }
 #ifndef NDEBUG
-  if (ResultSCCs.size() > 1)
+  if (!ResultSCCs.empty())
     assert(!IsLeafSCC && "This SCC cannot be a leaf as we have split out new "
                          "SCCs by removing this edge.");
   if (!std::any_of(G->LeafSCCs.begin(), G->LeafSCCs.end(),
@@ -347,7 +371,7 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
 #endif
   // If this SCC stopped being a leaf through this edge removal, remove it from
   // the leaf SCC list.
-  if (!IsLeafSCC && ResultSCCs.size() > 1)
+  if (!IsLeafSCC && !ResultSCCs.empty())
     G->LeafSCCs.erase(std::remove(G->LeafSCCs.begin(), G->LeafSCCs.end(), this),
                      G->LeafSCCs.end());
 
@@ -355,6 +379,13 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
   return ResultSCCs;
 }
 
+void LazyCallGraph::insertEdge(Node &CallerN, Function &Callee) {
+  assert(SCCMap.empty() && DFSStack.empty() &&
+         "This method cannot be called after SCCs have been formed!");
+
+  return CallerN.insertEdgeInternal(Callee);
+}
+
 void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) {
   assert(SCCMap.empty() && DFSStack.empty() &&
          "This method cannot be called after SCCs have been formed!");
@@ -378,8 +409,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);
     }
   }