From 306d5ba0923b6554c5c6e1c43cae9ae08341459d Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 23 Apr 2014 23:34:48 +0000 Subject: [PATCH] [LCG] Switch the primary node iterator to be a *much* more normal C++ iterator, returning a Node by reference on dereference. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207048 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LazyCallGraph.h | 9 +-- lib/Analysis/LazyCallGraph.cpp | 72 ++++++++--------- unittests/Analysis/LazyCallGraphTest.cpp | 98 ++++++++++++------------ 3 files changed, 86 insertions(+), 93 deletions(-) diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index 1b0e1dbf279..6aa0b8e0a2f 100644 --- a/include/llvm/Analysis/LazyCallGraph.h +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -112,8 +112,7 @@ public: /// be scanned for "calls" or uses of functions and its child information /// will be constructed. All of these results are accumulated and cached in /// the graph. - class iterator : public std::iterator { + class iterator : public std::iterator { friend class LazyCallGraph; friend class LazyCallGraph::Node; typedef std::iteratoris()) - return NI->get(); + return *NI->get(); Function *F = NI->get(); Node &ChildN = G->get(*F); *NI = &ChildN; - return &ChildN; + return ChildN; } - pointer operator->() const { return operator*(); } + pointer operator->() const { return &operator*(); } iterator &operator++() { ++NI; diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index 128448e4c93..2da67227c3e 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -140,13 +140,13 @@ void LazyCallGraph::SCC::removeEdge(LazyCallGraph &G, Function &Caller, bool HasOtherCallToCalleeC = false; bool HasOtherCallOutsideSCC = false; for (Node *N : *this) { - for (Node *Callee : *N) { - SCC *OtherCalleeC = G.SCCMap.lookup(Callee); - if (OtherCalleeC == &CalleeC) { + for (Node &Callee : *N) { + SCC &OtherCalleeC = *G.SCCMap.lookup(&Callee); + if (&OtherCalleeC == &CalleeC) { HasOtherCallToCalleeC = true; break; } - if (OtherCalleeC != this) + if (&OtherCalleeC != this) HasOtherCallOutsideSCC = true; } if (HasOtherCallToCalleeC) @@ -234,35 +234,33 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, do { N = SI->first; for (auto I = SI->second, E = N->end(); I != E; ++I) { - Node *ChildN = *I; + 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); - assert(ChildSCC && - "Everything reachable must already be in *some* SCC"); - if (ChildSCC != this) { - ChildSCC->ParentSCCs.remove(this); + SCC &ChildSCC = *G.SCCMap.lookup(&ChildN); + if (&ChildSCC != this) { + ChildSCC.ParentSCCs.remove(this); continue; } - if (ChildN->DFSNumber == 0) { + if (ChildN.DFSNumber == 0) { // Mark that we should start at this child when next this node is the // top of the stack. We don't start at the next child to ensure this // child's lowlink is reflected. SI->second = I; // Recurse onto this node via a tail call. - DFSStack.push_back(std::make_pair(ChildN, ChildN->begin())); + DFSStack.push_back(std::make_pair(&ChildN, ChildN.begin())); PushedChildNode = true; break; } // Track the lowest link of the childen, if any are still in the stack. // Any child not on the stack will have a LowLink of -1. - assert(ChildN->LowLink != 0 && + assert(ChildN.LowLink != 0 && "Low-link must not be zero with a non-zero DFS number."); - if (ChildN->LowLink >= 0 && ChildN->LowLink < N->LowLink) - N->LowLink = ChildN->LowLink; + if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) + N->LowLink = ChildN.LowLink; } if (!PushedChildNode) // No more children to process for this stack entry. @@ -293,13 +291,11 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, N->LowLink = -1; Nodes.push_back(N); NodeSet.insert(&N->getFunction()); - for (Node *ChildN : *N) { - if (NewNodes.count(ChildN)) + for (Node &ChildN : *N) { + if (NewNodes.count(&ChildN)) continue; - SCC *ChildSCC = G.SCCMap.lookup(ChildN); - assert(ChildSCC && - "Must have all child SCCs processed when building a new SCC!"); - ChildSCC->ParentSCCs.insert(this); + SCC &ChildSCC = *G.SCCMap.lookup(&ChildN); + ChildSCC.ParentSCCs.insert(this); IsLeafSCC = false; } } @@ -409,13 +405,11 @@ LazyCallGraph::SCC *LazyCallGraph::formSCCFromDFSStack( // its children. bool IsLeafSCC = true; for (Node *SCCN : NewSCC->Nodes) - for (Node *SCCChildN : *SCCN) { - if (NewSCC->NodeSet.count(&SCCChildN->getFunction())) + for (Node &SCCChildN : *SCCN) { + if (NewSCC->NodeSet.count(&SCCChildN.getFunction())) continue; - SCC *ChildSCC = SCCMap.lookup(SCCChildN); - assert(ChildSCC && - "Must have all child SCCs processed when building a new SCC!"); - ChildSCC->ParentSCCs.insert(NewSCC); + SCC &ChildSCC = *SCCMap.lookup(&SCCChildN); + ChildSCC.ParentSCCs.insert(NewSCC); IsLeafSCC = false; } @@ -452,23 +446,23 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { do { Node *N = SI->first; for (auto I = SI->second, E = N->end(); I != E; ++I) { - Node *ChildN = *I; - if (ChildN->DFSNumber == 0) { + Node &ChildN = *I; + if (ChildN.DFSNumber == 0) { // Mark that we should start at this child when next this node is the // top of the stack. We don't start at the next child to ensure this // child's lowlink is reflected. SI->second = I; // Recurse onto this node via a tail call. - DFSStack.push_back(std::make_pair(ChildN, ChildN->begin())); + DFSStack.push_back(std::make_pair(&ChildN, ChildN.begin())); return LazyCallGraph::getNextSCCInPostOrder(); } // Track the lowest link of the childen, if any are still in the stack. - assert(ChildN->LowLink != 0 && + assert(ChildN.LowLink != 0 && "Low-link must not be zero with a non-zero DFS number."); - if (ChildN->LowLink >= 0 && ChildN->LowLink < N->LowLink) - N->LowLink = ChildN->LowLink; + if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) + N->LowLink = ChildN.LowLink; } // No more children to process for this stack entry. SI->second = N->end(); @@ -491,9 +485,9 @@ LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N, SmallPtrSetImpl &Printed) { // Recurse depth first through the nodes. - for (LazyCallGraph::Node *ChildN : N) - if (Printed.insert(ChildN)) - printNodes(OS, *ChildN, Printed); + for (LazyCallGraph::Node &ChildN : N) + if (Printed.insert(&ChildN)) + printNodes(OS, ChildN, Printed); OS << " Call edges in function: " << N.getFunction().getName() << "\n"; for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I) @@ -520,9 +514,9 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M, << "\n\n"; SmallPtrSet Printed; - for (LazyCallGraph::Node *N : G) - if (Printed.insert(N)) - printNodes(OS, *N, Printed); + for (LazyCallGraph::Node &N : G) + if (Printed.insert(&N)) + printNodes(OS, N, Printed); for (LazyCallGraph::SCC *SCC : G.postorder_sccs()) printSCC(OS, *SCC); diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index a880c64d50b..ff6919091c8 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -128,79 +128,79 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { // the IR, and everything in our module is an entry node, so just directly // build variables for each node. auto I = CG.begin(); - LazyCallGraph::Node *A1 = *I++; - EXPECT_EQ("a1", A1->getFunction().getName()); - LazyCallGraph::Node *A2 = *I++; - EXPECT_EQ("a2", A2->getFunction().getName()); - LazyCallGraph::Node *A3 = *I++; - EXPECT_EQ("a3", A3->getFunction().getName()); - LazyCallGraph::Node *B1 = *I++; - EXPECT_EQ("b1", B1->getFunction().getName()); - LazyCallGraph::Node *B2 = *I++; - EXPECT_EQ("b2", B2->getFunction().getName()); - LazyCallGraph::Node *B3 = *I++; - EXPECT_EQ("b3", B3->getFunction().getName()); - LazyCallGraph::Node *C1 = *I++; - EXPECT_EQ("c1", C1->getFunction().getName()); - LazyCallGraph::Node *C2 = *I++; - EXPECT_EQ("c2", C2->getFunction().getName()); - LazyCallGraph::Node *C3 = *I++; - EXPECT_EQ("c3", C3->getFunction().getName()); - LazyCallGraph::Node *D1 = *I++; - EXPECT_EQ("d1", D1->getFunction().getName()); - LazyCallGraph::Node *D2 = *I++; - EXPECT_EQ("d2", D2->getFunction().getName()); - LazyCallGraph::Node *D3 = *I++; - EXPECT_EQ("d3", D3->getFunction().getName()); + LazyCallGraph::Node &A1 = *I++; + EXPECT_EQ("a1", A1.getFunction().getName()); + LazyCallGraph::Node &A2 = *I++; + EXPECT_EQ("a2", A2.getFunction().getName()); + LazyCallGraph::Node &A3 = *I++; + EXPECT_EQ("a3", A3.getFunction().getName()); + LazyCallGraph::Node &B1 = *I++; + EXPECT_EQ("b1", B1.getFunction().getName()); + LazyCallGraph::Node &B2 = *I++; + EXPECT_EQ("b2", B2.getFunction().getName()); + LazyCallGraph::Node &B3 = *I++; + EXPECT_EQ("b3", B3.getFunction().getName()); + LazyCallGraph::Node &C1 = *I++; + EXPECT_EQ("c1", C1.getFunction().getName()); + LazyCallGraph::Node &C2 = *I++; + EXPECT_EQ("c2", C2.getFunction().getName()); + LazyCallGraph::Node &C3 = *I++; + EXPECT_EQ("c3", C3.getFunction().getName()); + LazyCallGraph::Node &D1 = *I++; + EXPECT_EQ("d1", D1.getFunction().getName()); + LazyCallGraph::Node &D2 = *I++; + EXPECT_EQ("d2", D2.getFunction().getName()); + LazyCallGraph::Node &D3 = *I++; + EXPECT_EQ("d3", D3.getFunction().getName()); EXPECT_EQ(CG.end(), I); // Build vectors and sort them for the rest of the assertions to make them // independent of order. std::vector Nodes; - for (LazyCallGraph::Node *N : *A1) - Nodes.push_back(N->getFunction().getName()); + for (LazyCallGraph::Node &N : A1) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("a2", Nodes[0]); EXPECT_EQ("b2", Nodes[1]); EXPECT_EQ("c3", Nodes[2]); Nodes.clear(); - EXPECT_EQ(A2->end(), std::next(A2->begin())); - EXPECT_EQ("a3", A2->begin()->getFunction().getName()); - EXPECT_EQ(A3->end(), std::next(A3->begin())); - EXPECT_EQ("a1", A3->begin()->getFunction().getName()); + EXPECT_EQ(A2.end(), std::next(A2.begin())); + EXPECT_EQ("a3", A2.begin()->getFunction().getName()); + EXPECT_EQ(A3.end(), std::next(A3.begin())); + EXPECT_EQ("a1", A3.begin()->getFunction().getName()); - for (LazyCallGraph::Node *N : *B1) - Nodes.push_back(N->getFunction().getName()); + for (LazyCallGraph::Node &N : B1) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("b2", Nodes[0]); EXPECT_EQ("d3", Nodes[1]); Nodes.clear(); - EXPECT_EQ(B2->end(), std::next(B2->begin())); - EXPECT_EQ("b3", B2->begin()->getFunction().getName()); - EXPECT_EQ(B3->end(), std::next(B3->begin())); - EXPECT_EQ("b1", B3->begin()->getFunction().getName()); + EXPECT_EQ(B2.end(), std::next(B2.begin())); + EXPECT_EQ("b3", B2.begin()->getFunction().getName()); + EXPECT_EQ(B3.end(), std::next(B3.begin())); + EXPECT_EQ("b1", B3.begin()->getFunction().getName()); - for (LazyCallGraph::Node *N : *C1) - Nodes.push_back(N->getFunction().getName()); + for (LazyCallGraph::Node &N : C1) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("c2", Nodes[0]); EXPECT_EQ("d2", Nodes[1]); Nodes.clear(); - EXPECT_EQ(C2->end(), std::next(C2->begin())); - EXPECT_EQ("c3", C2->begin()->getFunction().getName()); - EXPECT_EQ(C3->end(), std::next(C3->begin())); - EXPECT_EQ("c1", C3->begin()->getFunction().getName()); - - EXPECT_EQ(D1->end(), std::next(D1->begin())); - EXPECT_EQ("d2", D1->begin()->getFunction().getName()); - EXPECT_EQ(D2->end(), std::next(D2->begin())); - EXPECT_EQ("d3", D2->begin()->getFunction().getName()); - EXPECT_EQ(D3->end(), std::next(D3->begin())); - EXPECT_EQ("d1", D3->begin()->getFunction().getName()); + EXPECT_EQ(C2.end(), std::next(C2.begin())); + EXPECT_EQ("c3", C2.begin()->getFunction().getName()); + EXPECT_EQ(C3.end(), std::next(C3.begin())); + EXPECT_EQ("c1", C3.begin()->getFunction().getName()); + + EXPECT_EQ(D1.end(), std::next(D1.begin())); + EXPECT_EQ("d2", D1.begin()->getFunction().getName()); + EXPECT_EQ(D2.end(), std::next(D2.begin())); + EXPECT_EQ("d3", D2.begin()->getFunction().getName()); + EXPECT_EQ(D3.end(), std::next(D3.begin())); + EXPECT_EQ("d1", D3.begin()->getFunction().getName()); // Now lets look at the SCCs. auto SCCI = CG.postorder_scc_begin(); -- 2.34.1