diff options
author | Chandler Carruth <chandlerc@gmail.com> | 2014-04-30 10:48:36 +0000 |
---|---|---|
committer | Chandler Carruth <chandlerc@gmail.com> | 2014-04-30 10:48:36 +0000 |
commit | 491f476b8bf5d2b201733c27a079a9a7015ffc44 (patch) | |
tree | 98b2ad761bee8b18c106f7a9c2984e3fac56b0f3 | |
parent | 0a780977749191616c2ceac32acca441ab519e07 (diff) | |
download | llvm-491f476b8bf5d2b201733c27a079a9a7015ffc44.tar.gz llvm-491f476b8bf5d2b201733c27a079a9a7015ffc44.tar.bz2 llvm-491f476b8bf5d2b201733c27a079a9a7015ffc44.tar.xz |
[LCG] Add the really, *really* boring edge insertion case: adding an
edge entirely within an existing SCC. Shockingly, making the connected
component more connected is ... a total snooze fest. =]
Anyways, its wired up, and I even added a test case to make sure it
pretty much sorta works. =D
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207631 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/Analysis/LazyCallGraph.h | 9 | ||||
-rw-r--r-- | lib/Analysis/LazyCallGraph.cpp | 23 | ||||
-rw-r--r-- | unittests/Analysis/LazyCallGraphTest.cpp | 46 |
3 files changed, 74 insertions, 4 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h index df3925aba6..2b391e0476 100644 --- a/include/llvm/Analysis/LazyCallGraph.h +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -186,6 +186,9 @@ public: /// \brief Internal helper to insert a callee. void insertEdgeInternal(Function &Callee); + /// \brief Internal helper to insert a callee. + void insertEdgeInternal(Node &CalleeN); + /// \brief Internal helper to remove a callee from this node. void removeEdgeInternal(Function &Callee); @@ -249,6 +252,12 @@ public: /// Note that these methods sometimes have complex runtimes, so be careful /// how you call them. + /// \brief Insert an edge from one node in this SCC to another in this SCC. + /// + /// By the definition of an SCC, this does not change the nature or make-up + /// of any SCCs. + void insertIntraSCCEdge(Node &CallerN, Node &CalleeN); + /// \brief Remove an edge whose source is in this SCC and target is *not*. /// /// This removes an inter-SCC edge. All inter-SCC edges originating from diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index dd940a98f3..6c4574f867 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -76,11 +76,16 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) } void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) { - CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size())); if (Node *N = G->lookup(Callee)) - Callees.push_back(N); - else - Callees.push_back(&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) { @@ -157,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()); diff --git a/unittests/Analysis/LazyCallGraphTest.cpp b/unittests/Analysis/LazyCallGraphTest.cpp index e8fd1a469e..ea68fa77c0 100644 --- a/unittests/Analysis/LazyCallGraphTest.cpp +++ b/unittests/Analysis/LazyCallGraphTest.cpp @@ -386,6 +386,52 @@ TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { EXPECT_EQ(BC.parent_end(), BC.parent_begin()); } +TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { + std::unique_ptr<Module> M1 = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " call void @c()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " call void @a()\n" + " ret void\n" + "}\n"); + LazyCallGraph CG1(*M1); + + // Force the graph to be fully expanded. + auto SCCI = CG1.postorder_scc_begin(); + 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)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + + // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. + SCC.insertIntraSCCEdge(A, C); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(&SCC, CG1.lookupSCC(A)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + + // Insert a self edge from 'a' back to 'a'. + SCC.insertIntraSCCEdge(A, A); + EXPECT_EQ(3, std::distance(A.begin(), A.end())); + EXPECT_EQ(&SCC, CG1.lookupSCC(A)); + EXPECT_EQ(&SCC, CG1.lookupSCC(B)); + EXPECT_EQ(&SCC, CG1.lookupSCC(C)); +} + TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { // A nice fully connected (including self-edges) SCC. std::unique_ptr<Module> M1 = parseAssembly( |