From 742805e0ea2f98e22aef1b43654d91d93d33a417 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 7 Dec 2016 01:42:40 +0000 Subject: [PATCH] [LCG] Add basic verification of the parent set and fix bugs it uncovers. The existing unittests actually cover this now that we verify things. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@288875 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/LazyCallGraph.cpp | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index d1689377ac6..2d18017320d 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -289,6 +289,20 @@ void LazyCallGraph::RefSCC::verify() { "Edge to a RefSCC missing us in its parent set."); } } + + // Check that our parents are actually parents. + for (RefSCC *ParentRC : Parents) { + assert(ParentRC != this && "Cannot be our own parent!"); + auto HasConnectingEdge = [&] { + for (SCC &C : *ParentRC) + for (Node &N : C) + for (Edge &E : N) + if (G->lookupRefSCC(*E.getNode()) == this) + return true; + return false; + }; + assert(HasConnectingEdge() && "No edge connects the parent to us!"); + } } #endif @@ -937,9 +951,13 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices, ComputeSourceConnectedSet, ComputeTargetConnectedSet); - // Build a set so we can do fast tests for whether a merge is occuring. + // Build a set so we can do fast tests for whether a RefSCC will end up as + // part of the merged RefSCC. SmallPtrSet MergeSet(MergeRange.begin(), MergeRange.end()); + // This RefSCC will always be part of that set, so just insert it here. + MergeSet.insert(this); + // Now that we have identified all of the SCCs which need to be merged into // a connected set with the inserted edge, merge all of them into this SCC. SmallVector MergedSCCs; @@ -1360,12 +1378,13 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { SmallVector OldParents(Parents.begin(), Parents.end()); Parents.clear(); for (RefSCC *ParentRC : OldParents) - for (SCC *ParentC : ParentRC->SCCs) - for (Node &ParentN : *ParentC) + for (SCC &ParentC : *ParentRC) + for (Node &ParentN : ParentC) for (Edge &E : ParentN) { assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); RefSCC &RC = *G->lookupRefSCC(*E.getNode()); - RC.Parents.insert(ParentRC); + if (&RC != ParentRC) + RC.Parents.insert(ParentRC); } // If this SCC stopped being a leaf through this edge removal, remove it from -- 2.11.0