From 13ffd110ada372b07140a635b86a21e5a142c461 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 5 Aug 2017 03:37:37 +0000 Subject: [PATCH] [LCG] Remove the use of the parent sets to compute connectivity when merging RefSCCs. The logic to directly use the reference edges is simpler and not substantially slower (despite the comments to the contrary) because this is not actually an especially hot part of LCG in practice. llvm-svn: 310161 --- llvm/lib/Analysis/LazyCallGraph.cpp | 30 ++++++++++++++---------------- 1 file changed, 14 insertions(+), 16 deletions(-) diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp index d287f81..fbf39a2 100644 --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -957,22 +957,20 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { // RefSCCs (and their edges) are visited here. auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl &Set) { Set.insert(&SourceC); - SmallVector Worklist; - Worklist.push_back(&SourceC); - do { - RefSCC &RC = *Worklist.pop_back_val(); - for (RefSCC &ParentRC : RC.parents()) { - // Skip any RefSCCs outside the range of source to target in the - // postorder sequence. - int ParentIdx = G->getRefSCCIndex(ParentRC); - assert(ParentIdx > SourceIdx && "Parent cannot precede source in postorder!"); - if (ParentIdx > TargetIdx) - continue; - if (Set.insert(&ParentRC).second) - // First edge connecting to this parent, add it to our worklist. - Worklist.push_back(&ParentRC); - } - } while (!Worklist.empty()); + auto IsConnected = [&](RefSCC &RC) { + for (SCC &C : RC) + for (Node &N : C) + for (Edge &E : *N) + if (Set.count(G->lookupRefSCC(E.getNode()))) + return true; + + return false; + }; + + for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1, + G->PostOrderRefSCCs.begin() + TargetIdx + 1)) + if (IsConnected(*C)) + Set.insert(C); }; // Use a normal worklist to find which SCCs the target connects to. We still -- 2.7.4