X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLazyCallGraph.cpp;h=767da4e31d1e42920b9e46bf98237330ee254551;hb=7a3eed6d22b235433aa7e69919c5333cf2a60c5d;hp=1ac30769a520b20a3db9de979a43563d4569ac1f;hpb=e3a8e534e15ea54ed7e634550573a9572976cc44;p=oota-llvm.git diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index 1ac30769a52..767da4e31d1 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -48,7 +48,7 @@ static void findCallees( } for (Value *Op : C->operand_values()) - if (Visited.insert(cast(Op))) + if (Visited.insert(cast(Op)).second) Worklist.push_back(cast(Op)); } } @@ -66,7 +66,7 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) for (Instruction &I : BB) for (Value *Op : I.operand_values()) if (Constant *C = dyn_cast(Op)) - if (Visited.insert(C)) + if (Visited.insert(C).second) Worklist.push_back(C); // We've collected all the constant (and thus potentially function or @@ -75,12 +75,25 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) findCallees(Worklist, Visited, Callees, CalleeIndexMap); } +void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) { + if (Node *N = G->lookup(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) { auto IndexMapI = CalleeIndexMap.find(&Callee); assert(IndexMapI != CalleeIndexMap.end() && "Callee not in the callee set for this caller?"); - Callees.erase(Callees.begin() + IndexMapI->second); + Callees[IndexMapI->second] = nullptr; CalleeIndexMap.erase(IndexMapI); } @@ -100,18 +113,21 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { SmallPtrSet Visited; for (GlobalVariable &GV : M.globals()) if (GV.hasInitializer()) - if (Visited.insert(GV.getInitializer())) + if (Visited.insert(GV.getInitializer()).second) Worklist.push_back(GV.getInitializer()); DEBUG(dbgs() << " Adding functions referenced by global initializers to the " "entry set.\n"); findCallees(Worklist, Visited, EntryNodes, EntryIndexMap); - for (auto &Entry : EntryNodes) + for (auto &Entry : EntryNodes) { + assert(!Entry.isNull() && + "We can't have removed edges before we finish the constructor!"); if (Function *F = Entry.dyn_cast()) SCCEntryNodes.push_back(F); else SCCEntryNodes.push_back(&Entry.get()->getFunction()); + } } LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) @@ -146,6 +162,165 @@ void LazyCallGraph::SCC::insert(Node &N) { G->SCCMap[&N] = this; } +bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const { + // Walk up the parents of this SCC and verify that we eventually find C. + SmallVector AncestorWorklist; + AncestorWorklist.push_back(this); + do { + const SCC *AncestorC = AncestorWorklist.pop_back_val(); + if (AncestorC->isChildOf(C)) + return true; + for (const SCC *ParentC : AncestorC->ParentSCCs) + AncestorWorklist.push_back(ParentC); + } while (!AncestorWorklist.empty()); + + return false; +} + +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::insertOutgoingEdge(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."); + + SCC &CalleeC = *G->SCCMap.lookup(&CalleeN); + assert(&CalleeC != this && "Callee must not be in this SCC."); + assert(CalleeC.isDescendantOf(*this) && + "Callee must be a descendant of the Caller."); + + // The only change required is to add this SCC to the parent set of the callee. + CalleeC.ParentSCCs.insert(this); +} + +SmallVector +LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { + // First insert it into the caller. + CallerN.insertEdgeInternal(CalleeN); + + assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC."); + + SCC &CallerC = *G->SCCMap.lookup(&CallerN); + assert(&CallerC != this && "Caller must not be in this SCC."); + assert(CallerC.isDescendantOf(*this) && + "Caller must be a descendant of the Callee."); + + // The algorithm we use for merging SCCs based on the cycle introduced here + // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse + // graph has the same cycle properties as the actual DAG of the SCCs, and + // when forming SCCs lazily by a DFS, the bottom of the graph won't exist in + // many cases which should prune the search space. + // + // FIXME: We can get this pruning behavior even after the incremental SCC + // formation by leaving behind (conservative) DFS numberings in the nodes, + // and pruning the search with them. These would need to be cleverly updated + // during the removal of intra-SCC edges, but could be preserved + // conservatively. + + // The set of SCCs that are connected to the caller, and thus will + // participate in the merged connected component. + SmallPtrSet ConnectedSCCs; + ConnectedSCCs.insert(this); + ConnectedSCCs.insert(&CallerC); + + // We build up a DFS stack of the parents chains. + SmallVector, 8> DFSSCCs; + SmallPtrSet VisitedSCCs; + int ConnectedDepth = -1; + SCC *C = this; + parent_iterator I = parent_begin(), E = parent_end(); + for (;;) { + while (I != E) { + SCC &ParentSCC = *I++; + + // If we have already processed this parent SCC, skip it, and remember + // whether it was connected so we don't have to check the rest of the + // stack. This also handles when we reach a child of the 'this' SCC (the + // callee) which terminates the search. + if (ConnectedSCCs.count(&ParentSCC)) { + ConnectedDepth = std::max(ConnectedDepth, DFSSCCs.size()); + continue; + } + if (VisitedSCCs.count(&ParentSCC)) + continue; + + // We fully explore the depth-first space, adding nodes to the connected + // set only as we pop them off, so "recurse" by rotating to the parent. + DFSSCCs.push_back(std::make_pair(C, I)); + C = &ParentSCC; + I = ParentSCC.parent_begin(); + E = ParentSCC.parent_end(); + } + + // If we've found a connection anywhere below this point on the stack (and + // thus up the parent graph from the caller), the current node needs to be + // added to the connected set now that we've processed all of its parents. + if ((int)DFSSCCs.size() == ConnectedDepth) { + --ConnectedDepth; // We're finished with this connection. + ConnectedSCCs.insert(C); + } else { + // Otherwise remember that its parents don't ever connect. + assert(ConnectedDepth < (int)DFSSCCs.size() && + "Cannot have a connected depth greater than the DFS depth!"); + VisitedSCCs.insert(C); + } + + if (DFSSCCs.empty()) + break; // We've walked all the parents of the caller transitively. + + // Pop off the prior node and position to unwind the depth first recursion. + std::tie(C, I) = DFSSCCs.pop_back_val(); + E = C->parent_end(); + } + + // 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. + // FIXME: This operation currently creates ordering stability problems + // because we don't use stably ordered containers for the parent SCCs or the + // connected SCCs. + unsigned NewNodeBeginIdx = Nodes.size(); + for (SCC *C : ConnectedSCCs) { + if (C == this) + continue; + for (SCC *ParentC : C->ParentSCCs) + if (!ConnectedSCCs.count(ParentC)) + ParentSCCs.insert(ParentC); + C->ParentSCCs.clear(); + + for (Node *N : *C) { + for (Node &ChildN : *N) { + SCC &ChildC = *G->SCCMap.lookup(&ChildN); + if (&ChildC != C) + ChildC.ParentSCCs.erase(C); + } + G->SCCMap[N] = this; + Nodes.push_back(N); + } + C->Nodes.clear(); + } + for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I) + for (Node &ChildN : **I) { + SCC &ChildC = *G->SCCMap.lookup(&ChildN); + if (&ChildC != this) + ChildC.ParentSCCs.insert(this); + } + + // We return the list of SCCs which were merged so that callers can + // invalidate any data they have associated with those SCCs. Note that these + // SCCs are no longer in an interesting state (they are totally empty) but + // the pointers will remain stable for the life of the graph itself. + return SmallVector(ConnectedSCCs.begin(), ConnectedSCCs.end()); +} + void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) { // First remove it from the node. CallerN.removeEdgeInternal(CalleeN.getFunction()); @@ -248,7 +423,7 @@ void LazyCallGraph::SCC::internalDFS( continue; } - // Track the lowest link of the childen, if any are still in the stack. + // Track the lowest link of the children, if any are still in the stack. // Any child not on the stack will have a LowLink of -1. assert(ChildN.LowLink != 0 && "Low-link must not be zero with a non-zero DFS number."); @@ -284,10 +459,8 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, // First remove it from the node. CallerN.removeEdgeInternal(CalleeN.getFunction()); - // We return a list of the resulting SCCs, where 'this' is always the first - // element. + // We return a list of the resulting *new* SCCs in postorder. SmallVector ResultSCCs; - ResultSCCs.push_back(this); // Direct recursion doesn't impact the SCC graph at all. if (&CallerN == &CalleeN) @@ -337,7 +510,7 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, } } #ifndef NDEBUG - if (ResultSCCs.size() > 1) + if (!ResultSCCs.empty()) assert(!IsLeafSCC && "This SCC cannot be a leaf as we have split out new " "SCCs by removing this edge."); if (!std::any_of(G->LeafSCCs.begin(), G->LeafSCCs.end(), @@ -347,7 +520,7 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, #endif // If this SCC stopped being a leaf through this edge removal, remove it from // the leaf SCC list. - if (!IsLeafSCC && ResultSCCs.size() > 1) + if (!IsLeafSCC && !ResultSCCs.empty()) G->LeafSCCs.erase(std::remove(G->LeafSCCs.begin(), G->LeafSCCs.end(), this), G->LeafSCCs.end()); @@ -355,6 +528,13 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, return ResultSCCs; } +void LazyCallGraph::insertEdge(Node &CallerN, Function &Callee) { + assert(SCCMap.empty() && DFSStack.empty() && + "This method cannot be called after SCCs have been formed!"); + + return CallerN.insertEdgeInternal(Callee); +} + void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); @@ -378,8 +558,9 @@ void LazyCallGraph::updateGraphPtrs() { Node *N = Worklist.pop_back_val(); N->G = this; for (auto &Callee : N->Callees) - if (Node *CalleeN = Callee.dyn_cast()) - Worklist.push_back(CalleeN); + if (!Callee.isNull()) + if (Node *CalleeN = Callee.dyn_cast()) + Worklist.push_back(CalleeN); } } @@ -416,9 +597,9 @@ LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN, bool IsLeafSCC = true; for (Node *SCCN : NewSCC->Nodes) for (Node &SCCChildN : *SCCN) { - if (SCCMap.lookup(&SCCChildN) == NewSCC) - continue; SCC &ChildSCC = *SCCMap.lookup(&SCCChildN); + if (&ChildSCC == NewSCC) + continue; ChildSCC.ParentSCCs.insert(NewSCC); IsLeafSCC = false; } @@ -473,7 +654,7 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { continue; } - // Track the lowest link of the childen, if any are still in the stack. + // Track the lowest link of the children, if any are still in the stack. assert(ChildN.LowLink != 0 && "Low-link must not be zero with a non-zero DFS number."); if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) @@ -507,7 +688,7 @@ 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)) + if (Printed.insert(&ChildN).second) printNodes(OS, ChildN, Printed); OS << " Call edges in function: " << N.getFunction().getName() << "\n"; @@ -536,7 +717,7 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M, SmallPtrSet Printed; for (LazyCallGraph::Node &N : G) - if (Printed.insert(&N)) + if (Printed.insert(&N).second) printNodes(OS, N, Printed); for (LazyCallGraph::SCC &SCC : G.postorder_sccs())