From 31d2477c683f3c411195a896b852af286d49cfcb Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 23 Apr 2014 23:12:06 +0000 Subject: [PATCH] [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 --- include/llvm/Analysis/LazyCallGraph.h | 4 +- lib/Analysis/LazyCallGraph.cpp | 16 +++--- unittests/Analysis/LazyCallGraphTest.cpp | 70 ++++++++++++------------ 3 files changed, 45 insertions(+), 45 deletions(-) diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index ada278b1145..0bbf591a6c6 100644 --- 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 SCCBPA; /// \brief Maps Function -> SCC for fast lookup. - DenseMap SCCMap; + DenseMap SCCMap; /// \brief The leaf SCCs of the graph. /// diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index 4ad637583ef..d31793803ac 100644 --- 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 b08a3c51ec2..a880c64d50b 100644 --- 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)); } } -- 2.34.1