[LCG] Switch the SCC lookup to be in terms of call graph nodes rather

than functions. So far, this access pattern is *much* more common. It
seems likely that any user of this interface is going to have nodes at
the point that they are querying the SCCs.

No functionality changed.

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

diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index ada278b114582d07fc30dc47b031aa408bebcd51..0bbf591a6c662e22d34e079122eaf44f858382ec 100644 (file)
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -328,7 +328,7 @@ public:
   ///
   /// \returns null if the function hasn't been assigned an SCC via the SCC
   /// iterator walk.
-  SCC *lookupSCC(const Function &F) const { return SCCMap.lookup(&F); }
+  SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
 
   /// \brief Get a graph node for a given function, scanning it to populate the
   /// graph data as necessary.
@@ -369,7 +369,7 @@ private:
   SpecificBumpPtrAllocator<SCC> SCCBPA;
 
   /// \brief Maps Function -> SCC for fast lookup.
-  DenseMap<const Function *, SCC *> SCCMap;
+  DenseMap<Node *, SCC *> SCCMap;
 
   /// \brief The leaf SCCs of the graph.
   ///

diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 4ad637583ef15b9dbe88d77f0839c53aa90b9e6b..d31793803ac001aa20c03c66240eeaf3f55aff9c 100644 (file)
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -141,7 +141,7 @@ void LazyCallGraph::SCC::removeEdge(LazyCallGraph &G, Function &Caller,
   bool HasOtherCallOutsideSCC = false;
   for (Node *N : *this) {
     for (Node *Callee : *N) {
-      SCC *OtherCalleeC = G.SCCMap.lookup(&Callee->F);
+      SCC *OtherCalleeC = G.SCCMap.lookup(Callee);
       if (OtherCalleeC == &CalleeC) {
         HasOtherCallToCalleeC = true;
         break;
@@ -237,7 +237,7 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
         Node *ChildN = *I;
         // If this child isn't currently in this SCC, no need to process it.
         // However, we do need to remove this SCC from its SCC's parent set.
-        SCC *ChildSCC = G.SCCMap.lookup(&ChildN->F);
+        SCC *ChildSCC = G.SCCMap.lookup(ChildN);
         assert(ChildSCC &&
                "Everything reachable must already be in *some* SCC");
         if (ChildSCC != this) {
@@ -296,7 +296,7 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller,
     for (Node *ChildN : *N) {
       if (NewNodes.count(ChildN))
         continue;
-      SCC *ChildSCC = G.SCCMap.lookup(&ChildN->getFunction());
+      SCC *ChildSCC = G.SCCMap.lookup(ChildN);
       assert(ChildSCC &&
              "Must have all child SCCs processed when building a new SCC!");
       ChildSCC->ParentSCCs.insert(this);
@@ -331,7 +331,7 @@ void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) {
   CallerN.Callees.erase(CallerN.Callees.begin() + IndexMapI->second);
   CallerN.CalleeIndexMap.erase(IndexMapI);
 
-  SCC *CallerC = SCCMap.lookup(&CallerN.F);
+  SCC *CallerC = SCCMap.lookup(&CallerN);
   if (!CallerC) {
     // We can only remove edges when the edge isn't actively participating in
     // a DFS walk. Either it must have been popped into an SCC, or it must not
@@ -347,7 +347,7 @@ void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) {
   assert(CalleeN && "If the caller is in an SCC, we have to have explored all "
                     "its transitively called functions.");
 
-  SCC *CalleeC = SCCMap.lookup(&Callee);
+  SCC *CalleeC = SCCMap.lookup(CalleeN);
   assert(CalleeC &&
          "The caller has an SCC, and thus by necessity so does the callee.");
 
@@ -395,7 +395,7 @@ LazyCallGraph::SCC *LazyCallGraph::formSCCFromDFSStack(
            "We cannot have a low link in an SCC lower than its root on the "
            "stack!");
 
-    SCCMap[&SCCN->getFunction()] = NewSCC;
+    SCCMap[SCCN] = NewSCC;
     NewSCC->Nodes.push_back(SCCN);
     bool Inserted =
         NewSCC->NodeSet.insert(&SCCN->getFunction());
@@ -412,7 +412,7 @@ LazyCallGraph::SCC *LazyCallGraph::formSCCFromDFSStack(
     for (Node *SCCChildN : *SCCN) {
       if (NewSCC->NodeSet.count(&SCCChildN->getFunction()))
         continue;
-      SCC *ChildSCC = SCCMap.lookup(&SCCChildN->getFunction());
+      SCC *ChildSCC = SCCMap.lookup(SCCChildN);
       assert(ChildSCC &&
              "Must have all child SCCs processed when building a new SCC!");
       ChildSCC->ParentSCCs.insert(NewSCC);
@@ -443,7 +443,7 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
   if (SI->first->DFSNumber == 0) {
     // This node hasn't been visited before, assign it a DFS number and remove
     // it from the entry set.
-    assert(!SCCMap.count(&SI->first->getFunction()) &&
+    assert(!SCCMap.count(SI->first) &&
            "Found a node with 0 DFS number but already in an SCC!");
     SI->first->LowLink = SI->first->DFSNumber = NextDFSNumber++;
     SCCEntryNodes.remove(&SI->first->getFunction());

diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp
index b08a3c51ec25febb3470f2825d0fc87da063e5a5..a880c64d50bd38b6aaf7a3074ddabbe0e877651a 100644 (file)
--- a/unittests/Analysis/LazyCallGraphTest.cpp
+++ b/unittests/Analysis/LazyCallGraphTest.cpp
@@ -293,16 +293,16 @@ TEST(LazyCallGraphTest, MultiArmSCC) {
   LazyCallGraph::SCC *SCC = *SCCI++;
   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
 
-  LazyCallGraph::Node *A = CG.lookup(lookupFunction(*M, "a"));
-  LazyCallGraph::Node *B = CG.lookup(lookupFunction(*M, "b"));
-  LazyCallGraph::Node *C = CG.lookup(lookupFunction(*M, "c"));
-  LazyCallGraph::Node *D = CG.lookup(lookupFunction(*M, "d"));
-  LazyCallGraph::Node *E = CG.lookup(lookupFunction(*M, "e"));
-  EXPECT_EQ(SCC, CG.lookupSCC(A->getFunction()));
-  EXPECT_EQ(SCC, CG.lookupSCC(B->getFunction()));
-  EXPECT_EQ(SCC, CG.lookupSCC(C->getFunction()));
-  EXPECT_EQ(SCC, CG.lookupSCC(D->getFunction()));
-  EXPECT_EQ(SCC, CG.lookupSCC(E->getFunction()));
+  LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
+  LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
+  LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
+  EXPECT_EQ(SCC, CG.lookupSCC(A));
+  EXPECT_EQ(SCC, CG.lookupSCC(B));
+  EXPECT_EQ(SCC, CG.lookupSCC(C));
+  EXPECT_EQ(SCC, CG.lookupSCC(D));
+  EXPECT_EQ(SCC, CG.lookupSCC(E));
 }
 
 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
@@ -322,20 +322,20 @@ TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
   for (LazyCallGraph::SCC *C : CG.postorder_sccs())
     (void)C;
 
-  LazyCallGraph::Node *A = CG.lookup(lookupFunction(*M, "a"));
-  LazyCallGraph::Node *B = CG.lookup(lookupFunction(*M, "b"));
-  LazyCallGraph::SCC *AC = CG.lookupSCC(lookupFunction(*M, "a"));
-  LazyCallGraph::SCC *BC = CG.lookupSCC(lookupFunction(*M, "b"));
+  LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
+  LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
+  LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
+  LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
 
-  EXPECT_EQ("b", A->begin()->getFunction().getName());
-  EXPECT_EQ(B->end(), B->begin());
-  EXPECT_EQ(AC, *BC->parent_begin());
+  EXPECT_EQ("b", A.begin()->getFunction().getName());
+  EXPECT_EQ(B.end(), B.begin());
+  EXPECT_EQ(&AC, *BC.parent_begin());
 
-  CG.removeEdge(*A, lookupFunction(*M, "b"));
+  CG.removeEdge(A, lookupFunction(*M, "b"));
 
-  EXPECT_EQ(A->end(), A->begin());
-  EXPECT_EQ(B->end(), B->begin());
-  EXPECT_EQ(BC->parent_end(), BC->parent_begin());
+  EXPECT_EQ(A.end(), A.begin());
+  EXPECT_EQ(B.end(), B.begin());
+  EXPECT_EQ(BC.parent_end(), BC.parent_begin());
 }
 
 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
@@ -369,27 +369,27 @@ TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
   LazyCallGraph::SCC *SCC = *SCCI++;
   EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
 
-  LazyCallGraph::Node *A = CG1.lookup(lookupFunction(*M1, "a"));
-  LazyCallGraph::Node *B = CG1.lookup(lookupFunction(*M1, "b"));
-  LazyCallGraph::Node *C = CG1.lookup(lookupFunction(*M1, "c"));
-  EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
-  EXPECT_EQ(SCC, CG1.lookupSCC(B->getFunction()));
-  EXPECT_EQ(SCC, CG1.lookupSCC(C->getFunction()));
+  LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
+  LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
+  LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
+  EXPECT_EQ(SCC, CG1.lookupSCC(A));
+  EXPECT_EQ(SCC, CG1.lookupSCC(B));
+  EXPECT_EQ(SCC, CG1.lookupSCC(C));
 
   // Remove the edge from b -> a, which should leave the 3 functions still in
   // a single connected component because of a -> b -> c -> a.
-  CG1.removeEdge(*B, A->getFunction());
-  EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
-  EXPECT_EQ(SCC, CG1.lookupSCC(B->getFunction()));
-  EXPECT_EQ(SCC, CG1.lookupSCC(C->getFunction()));
+  CG1.removeEdge(B, A.getFunction());
+  EXPECT_EQ(SCC, CG1.lookupSCC(A));
+  EXPECT_EQ(SCC, CG1.lookupSCC(B));
+  EXPECT_EQ(SCC, CG1.lookupSCC(C));
 
   // Remove the edge from c -> a, which should leave 'a' in the original SCC
   // and form a new SCC for 'b' and 'c'.
-  CG1.removeEdge(*C, A->getFunction());
-  EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
+  CG1.removeEdge(C, A.getFunction());
+  EXPECT_EQ(SCC, CG1.lookupSCC(A));
   EXPECT_EQ(1, std::distance(SCC->begin(), SCC->end()));
-  LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B->getFunction());
-  EXPECT_EQ(SCC2, CG1.lookupSCC(C->getFunction()));
+  LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B);
+  EXPECT_EQ(SCC2, CG1.lookupSCC(C));
 }
 
 }