2073 lines · cpp
1//===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/LazyCallGraph.h"10 11#include "llvm/ADT/ArrayRef.h"12#include "llvm/ADT/STLExtras.h"13#include "llvm/ADT/Sequence.h"14#include "llvm/ADT/SmallPtrSet.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/iterator_range.h"17#include "llvm/Analysis/TargetLibraryInfo.h"18#include "llvm/IR/Constants.h"19#include "llvm/IR/Function.h"20#include "llvm/IR/GlobalVariable.h"21#include "llvm/IR/InstIterator.h"22#include "llvm/IR/Instruction.h"23#include "llvm/IR/Module.h"24#include "llvm/IR/PassManager.h"25#include "llvm/Support/Casting.h"26#include "llvm/Support/Compiler.h"27#include "llvm/Support/Debug.h"28#include "llvm/Support/GraphWriter.h"29#include "llvm/Support/raw_ostream.h"30#include <algorithm>31 32#ifdef EXPENSIVE_CHECKS33#include "llvm/ADT/ScopeExit.h"34#endif35 36using namespace llvm;37 38#define DEBUG_TYPE "lcg"39 40template struct LLVM_EXPORT_TEMPLATE Any::TypeId<const LazyCallGraph::SCC *>;41 42void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,43 Edge::Kind EK) {44 EdgeIndexMap.try_emplace(&TargetN, Edges.size());45 Edges.emplace_back(TargetN, EK);46}47 48void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {49 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);50}51 52bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {53 auto IndexMapI = EdgeIndexMap.find(&TargetN);54 if (IndexMapI == EdgeIndexMap.end())55 return false;56 57 Edges[IndexMapI->second] = Edge();58 EdgeIndexMap.erase(IndexMapI);59 return true;60}61 62static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,63 DenseMap<LazyCallGraph::Node *, int> &EdgeIndexMap,64 LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) {65 if (!EdgeIndexMap.try_emplace(&N, Edges.size()).second)66 return;67 68 LLVM_DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n");69 Edges.emplace_back(LazyCallGraph::Edge(N, EK));70}71 72LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() {73 assert(!Edges && "Must not have already populated the edges for this node!");74 75 LLVM_DEBUG(dbgs() << " Adding functions called by '" << getName()76 << "' to the graph.\n");77 78 Edges = EdgeSequence();79 80 SmallVector<Constant *, 16> Worklist;81 SmallPtrSet<Function *, 4> Callees;82 SmallPtrSet<Constant *, 16> Visited;83 84 // Find all the potential call graph edges in this function. We track both85 // actual call edges and indirect references to functions. The direct calls86 // are trivially added, but to accumulate the latter we walk the instructions87 // and add every operand which is a constant to the worklist to process88 // afterward.89 //90 // Note that we consider *any* function with a definition to be a viable91 // edge. Even if the function's definition is subject to replacement by92 // some other module (say, a weak definition) there may still be93 // optimizations which essentially speculate based on the definition and94 // a way to check that the specific definition is in fact the one being95 // used. For example, this could be done by moving the weak definition to96 // a strong (internal) definition and making the weak definition be an97 // alias. Then a test of the address of the weak function against the new98 // strong definition's address would be an effective way to determine the99 // safety of optimizing a direct call edge.100 for (BasicBlock &BB : *F)101 for (Instruction &I : BB) {102 if (auto *CB = dyn_cast<CallBase>(&I))103 if (Function *Callee = CB->getCalledFunction())104 if (!Callee->isDeclaration())105 if (Callees.insert(Callee).second) {106 Visited.insert(Callee);107 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee),108 LazyCallGraph::Edge::Call);109 }110 111 for (Value *Op : I.operand_values())112 if (Constant *C = dyn_cast<Constant>(Op))113 if (Visited.insert(C).second)114 Worklist.push_back(C);115 }116 117 // We've collected all the constant (and thus potentially function or118 // function containing) operands to all the instructions in the function.119 // Process them (recursively) collecting every function found.120 visitReferences(Worklist, Visited, [&](Function &F) {121 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F),122 LazyCallGraph::Edge::Ref);123 });124 125 // Add implicit reference edges to any defined libcall functions (if we126 // haven't found an explicit edge).127 for (auto *F : G->LibFunctions)128 if (!Visited.count(F))129 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*F),130 LazyCallGraph::Edge::Ref);131 132 return *Edges;133}134 135void LazyCallGraph::Node::replaceFunction(Function &NewF) {136 assert(F != &NewF && "Must not replace a function with itself!");137 F = &NewF;138}139 140#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)141LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {142 dbgs() << *this << '\n';143}144#endif145 146static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {147 LibFunc LF;148 149 // Either this is a normal library function or a "vectorizable"150 // function. Not using the VFDatabase here because this query151 // is related only to libraries handled via the TLI.152 return TLI.getLibFunc(F, LF) ||153 TLI.isKnownVectorFunctionInLibrary(F.getName());154}155 156LazyCallGraph::LazyCallGraph(157 Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {158 LLVM_DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()159 << "\n");160 for (Function &F : M) {161 if (F.isDeclaration())162 continue;163 // If this function is a known lib function to LLVM then we want to164 // synthesize reference edges to it to model the fact that LLVM can turn165 // arbitrary code into a library function call.166 if (isKnownLibFunction(F, GetTLI(F)))167 LibFunctions.insert(&F);168 169 if (F.hasLocalLinkage())170 continue;171 172 // External linkage defined functions have edges to them from other173 // modules.174 LLVM_DEBUG(dbgs() << " Adding '" << F.getName()175 << "' to entry set of the graph.\n");176 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref);177 }178 179 // Externally visible aliases of internal functions are also viable entry180 // edges to the module.181 for (auto &A : M.aliases()) {182 if (A.hasLocalLinkage())183 continue;184 if (Function* F = dyn_cast<Function>(A.getAliasee())) {185 LLVM_DEBUG(dbgs() << " Adding '" << F->getName()186 << "' with alias '" << A.getName()187 << "' to entry set of the graph.\n");188 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(*F), Edge::Ref);189 }190 }191 192 // Now add entry nodes for functions reachable via initializers to globals.193 SmallVector<Constant *, 16> Worklist;194 SmallPtrSet<Constant *, 16> Visited;195 for (GlobalVariable &GV : M.globals())196 if (GV.hasInitializer())197 if (Visited.insert(GV.getInitializer()).second)198 Worklist.push_back(GV.getInitializer());199 200 LLVM_DEBUG(201 dbgs() << " Adding functions referenced by global initializers to the "202 "entry set.\n");203 visitReferences(Worklist, Visited, [&](Function &F) {204 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),205 LazyCallGraph::Edge::Ref);206 });207}208 209LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)210 : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),211 EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),212 SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) {213 updateGraphPtrs();214}215 216#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)217void LazyCallGraph::verify() {218 for (RefSCC &RC : postorder_ref_sccs()) {219 RC.verify();220 }221}222#endif223 224bool LazyCallGraph::invalidate(Module &, const PreservedAnalyses &PA,225 ModuleAnalysisManager::Invalidator &) {226 // Check whether the analysis, all analyses on functions, or the function's227 // CFG have been preserved.228 auto PAC = PA.getChecker<llvm::LazyCallGraphAnalysis>();229 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>());230}231 232LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {233 BPA = std::move(G.BPA);234 NodeMap = std::move(G.NodeMap);235 EntryEdges = std::move(G.EntryEdges);236 SCCBPA = std::move(G.SCCBPA);237 SCCMap = std::move(G.SCCMap);238 LibFunctions = std::move(G.LibFunctions);239 updateGraphPtrs();240 return *this;241}242 243#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)244LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {245 dbgs() << *this << '\n';246}247#endif248 249#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)250void LazyCallGraph::SCC::verify() {251 assert(OuterRefSCC && "Can't have a null RefSCC!");252 assert(!Nodes.empty() && "Can't have an empty SCC!");253 254 for (Node *N : Nodes) {255 assert(N && "Can't have a null node!");256 assert(OuterRefSCC->G->lookupSCC(*N) == this &&257 "Node does not map to this SCC!");258 assert(N->DFSNumber == -1 &&259 "Must set DFS numbers to -1 when adding a node to an SCC!");260 assert(N->LowLink == -1 &&261 "Must set low link to -1 when adding a node to an SCC!");262 for (Edge &E : **N)263 assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");264 265#ifdef EXPENSIVE_CHECKS266 // Verify that all nodes in this SCC can reach all other nodes.267 SmallVector<Node *, 4> Worklist;268 SmallPtrSet<Node *, 4> Visited;269 Worklist.push_back(N);270 while (!Worklist.empty()) {271 Node *VisitingNode = Worklist.pop_back_val();272 if (!Visited.insert(VisitingNode).second)273 continue;274 for (Edge &E : (*VisitingNode)->calls())275 Worklist.push_back(&E.getNode());276 }277 for (Node *NodeToVisit : Nodes) {278 assert(Visited.contains(NodeToVisit) &&279 "Cannot reach all nodes within SCC");280 }281#endif282 }283}284#endif285 286bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {287 if (this == &C)288 return false;289 290 for (Node &N : *this)291 for (Edge &E : N->calls())292 if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)293 return true;294 295 // No edges found.296 return false;297}298 299bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {300 if (this == &TargetC)301 return false;302 303 LazyCallGraph &G = *OuterRefSCC->G;304 305 // Start with this SCC.306 SmallPtrSet<const SCC *, 16> Visited = {this};307 SmallVector<const SCC *, 16> Worklist = {this};308 309 // Walk down the graph until we run out of edges or find a path to TargetC.310 do {311 const SCC &C = *Worklist.pop_back_val();312 for (Node &N : C)313 for (Edge &E : N->calls()) {314 SCC *CalleeC = G.lookupSCC(E.getNode());315 if (!CalleeC)316 continue;317 318 // If the callee's SCC is the TargetC, we're done.319 if (CalleeC == &TargetC)320 return true;321 322 // If this is the first time we've reached this SCC, put it on the323 // worklist to recurse through.324 if (Visited.insert(CalleeC).second)325 Worklist.push_back(CalleeC);326 }327 } while (!Worklist.empty());328 329 // No paths found.330 return false;331}332 333LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}334 335#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)336LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {337 dbgs() << *this << '\n';338}339#endif340 341#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)342void LazyCallGraph::RefSCC::verify() {343 assert(G && "Can't have a null graph!");344 assert(!SCCs.empty() && "Can't have an empty SCC!");345 346 // Verify basic properties of the SCCs.347 SmallPtrSet<SCC *, 4> SCCSet;348 for (SCC *C : SCCs) {349 assert(C && "Can't have a null SCC!");350 C->verify();351 assert(&C->getOuterRefSCC() == this &&352 "SCC doesn't think it is inside this RefSCC!");353 bool Inserted = SCCSet.insert(C).second;354 assert(Inserted && "Found a duplicate SCC!");355 auto IndexIt = SCCIndices.find(C);356 assert(IndexIt != SCCIndices.end() &&357 "Found an SCC that doesn't have an index!");358 }359 360 // Check that our indices map correctly.361 for (auto [C, I] : SCCIndices) {362 assert(C && "Can't have a null SCC in the indices!");363 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");364 assert(SCCs[I] == C && "Index doesn't point to SCC!");365 }366 367 // Check that the SCCs are in fact in post-order.368 for (int I = 0, Size = SCCs.size(); I < Size; ++I) {369 SCC &SourceSCC = *SCCs[I];370 for (Node &N : SourceSCC)371 for (Edge &E : *N) {372 if (!E.isCall())373 continue;374 SCC &TargetSCC = *G->lookupSCC(E.getNode());375 if (&TargetSCC.getOuterRefSCC() == this) {376 assert(SCCIndices.find(&TargetSCC)->second <= I &&377 "Edge between SCCs violates post-order relationship.");378 continue;379 }380 }381 }382 383#ifdef EXPENSIVE_CHECKS384 // Verify that all nodes in this RefSCC can reach all other nodes.385 SmallVector<Node *> Nodes;386 for (SCC *C : SCCs) {387 for (Node &N : *C)388 Nodes.push_back(&N);389 }390 for (Node *N : Nodes) {391 SmallVector<Node *, 4> Worklist;392 SmallPtrSet<Node *, 4> Visited;393 Worklist.push_back(N);394 while (!Worklist.empty()) {395 Node *VisitingNode = Worklist.pop_back_val();396 if (!Visited.insert(VisitingNode).second)397 continue;398 for (Edge &E : **VisitingNode)399 Worklist.push_back(&E.getNode());400 }401 for (Node *NodeToVisit : Nodes) {402 assert(Visited.contains(NodeToVisit) &&403 "Cannot reach all nodes within RefSCC");404 }405 }406#endif407}408#endif409 410bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {411 if (&RC == this)412 return false;413 414 // Search all edges to see if this is a parent.415 for (SCC &C : *this)416 for (Node &N : C)417 for (Edge &E : *N)418 if (G->lookupRefSCC(E.getNode()) == &RC)419 return true;420 421 return false;422}423 424bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {425 if (&RC == this)426 return false;427 428 // For each descendant of this RefSCC, see if one of its children is the429 // argument. If not, add that descendant to the worklist and continue430 // searching.431 SmallVector<const RefSCC *, 4> Worklist;432 SmallPtrSet<const RefSCC *, 4> Visited;433 Worklist.push_back(this);434 Visited.insert(this);435 do {436 const RefSCC &DescendantRC = *Worklist.pop_back_val();437 for (SCC &C : DescendantRC)438 for (Node &N : C)439 for (Edge &E : *N) {440 auto *ChildRC = G->lookupRefSCC(E.getNode());441 if (ChildRC == &RC)442 return true;443 if (!ChildRC || !Visited.insert(ChildRC).second)444 continue;445 Worklist.push_back(ChildRC);446 }447 } while (!Worklist.empty());448 449 return false;450}451 452/// Generic helper that updates a postorder sequence of SCCs for a potentially453/// cycle-introducing edge insertion.454///455/// A postorder sequence of SCCs of a directed graph has one fundamental456/// property: all deges in the DAG of SCCs point "up" the sequence. That is,457/// all edges in the SCC DAG point to prior SCCs in the sequence.458///459/// This routine both updates a postorder sequence and uses that sequence to460/// compute the set of SCCs connected into a cycle. It should only be called to461/// insert a "downward" edge which will require changing the sequence to462/// restore it to a postorder.463///464/// When inserting an edge from an earlier SCC to a later SCC in some postorder465/// sequence, all of the SCCs which may be impacted are in the closed range of466/// those two within the postorder sequence. The algorithm used here to restore467/// the state is as follows:468///469/// 1) Starting from the source SCC, construct a set of SCCs which reach the470/// source SCC consisting of just the source SCC. Then scan toward the471/// target SCC in postorder and for each SCC, if it has an edge to an SCC472/// in the set, add it to the set. Otherwise, the source SCC is not473/// a successor, move it in the postorder sequence to immediately before474/// the source SCC, shifting the source SCC and all SCCs in the set one475/// position toward the target SCC. Stop scanning after processing the476/// target SCC.477/// 2) If the source SCC is now past the target SCC in the postorder sequence,478/// and thus the new edge will flow toward the start, we are done.479/// 3) Otherwise, starting from the target SCC, walk all edges which reach an480/// SCC between the source and the target, and add them to the set of481/// connected SCCs, then recurse through them. Once a complete set of the482/// SCCs the target connects to is known, hoist the remaining SCCs between483/// the source and the target to be above the target. Note that there is no484/// need to process the source SCC, it is already known to connect.485/// 4) At this point, all of the SCCs in the closed range between the source486/// SCC and the target SCC in the postorder sequence are connected,487/// including the target SCC and the source SCC. Inserting the edge from488/// the source SCC to the target SCC will form a cycle out of precisely489/// these SCCs. Thus we can merge all of the SCCs in this closed range into490/// a single SCC.491///492/// This process has various important properties:493/// - Only mutates the SCCs when adding the edge actually changes the SCC494/// structure.495/// - Never mutates SCCs which are unaffected by the change.496/// - Updates the postorder sequence to correctly satisfy the postorder497/// constraint after the edge is inserted.498/// - Only reorders SCCs in the closed postorder sequence from the source to499/// the target, so easy to bound how much has changed even in the ordering.500/// - Big-O is the number of edges in the closed postorder range of SCCs from501/// source to target.502///503/// This helper routine, in addition to updating the postorder sequence itself504/// will also update a map from SCCs to indices within that sequence.505///506/// The sequence and the map must operate on pointers to the SCC type.507///508/// Two callbacks must be provided. The first computes the subset of SCCs in509/// the postorder closed range from the source to the target which connect to510/// the source SCC via some (transitive) set of edges. The second computes the511/// subset of the same range which the target SCC connects to via some512/// (transitive) set of edges. Both callbacks should populate the set argument513/// provided.514template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,515 typename ComputeSourceConnectedSetCallableT,516 typename ComputeTargetConnectedSetCallableT>517static iterator_range<typename PostorderSequenceT::iterator>518updatePostorderSequenceForEdgeInsertion(519 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,520 SCCIndexMapT &SCCIndices,521 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,522 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {523 int SourceIdx = SCCIndices[&SourceSCC];524 int TargetIdx = SCCIndices[&TargetSCC];525 assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");526 527 SmallPtrSet<SCCT *, 4> ConnectedSet;528 529 // Compute the SCCs which (transitively) reach the source.530 ComputeSourceConnectedSet(ConnectedSet);531 532 // Partition the SCCs in this part of the port-order sequence so only SCCs533 // connecting to the source remain between it and the target. This is534 // a benign partition as it preserves postorder.535 auto SourceI = std::stable_partition(536 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,537 [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });538 for (int I = SourceIdx, E = TargetIdx + 1; I < E; ++I)539 SCCIndices.find(SCCs[I])->second = I;540 541 // If the target doesn't connect to the source, then we've corrected the542 // post-order and there are no cycles formed.543 if (!ConnectedSet.count(&TargetSCC)) {544 assert(SourceI > (SCCs.begin() + SourceIdx) &&545 "Must have moved the source to fix the post-order.");546 assert(*std::prev(SourceI) == &TargetSCC &&547 "Last SCC to move should have bene the target.");548 549 // Return an empty range at the target SCC indicating there is nothing to550 // merge.551 return make_range(std::prev(SourceI), std::prev(SourceI));552 }553 554 assert(SCCs[TargetIdx] == &TargetSCC &&555 "Should not have moved target if connected!");556 SourceIdx = SourceI - SCCs.begin();557 assert(SCCs[SourceIdx] == &SourceSCC &&558 "Bad updated index computation for the source SCC!");559 560 // See whether there are any remaining intervening SCCs between the source561 // and target. If so we need to make sure they all are reachable form the562 // target.563 if (SourceIdx + 1 < TargetIdx) {564 ConnectedSet.clear();565 ComputeTargetConnectedSet(ConnectedSet);566 567 // Partition SCCs so that only SCCs reached from the target remain between568 // the source and the target. This preserves postorder.569 auto TargetI = std::stable_partition(570 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,571 [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });572 for (int I = SourceIdx + 1, E = TargetIdx + 1; I < E; ++I)573 SCCIndices.find(SCCs[I])->second = I;574 TargetIdx = std::prev(TargetI) - SCCs.begin();575 assert(SCCs[TargetIdx] == &TargetSCC &&576 "Should always end with the target!");577 }578 579 // At this point, we know that connecting source to target forms a cycle580 // because target connects back to source, and we know that all the SCCs581 // between the source and target in the postorder sequence participate in that582 // cycle.583 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);584}585 586bool LazyCallGraph::RefSCC::switchInternalEdgeToCall(587 Node &SourceN, Node &TargetN,588 function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {589 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");590 SmallVector<SCC *, 1> DeletedSCCs;591 592#ifdef EXPENSIVE_CHECKS593 verify();594 auto VerifyOnExit = make_scope_exit([&]() { verify(); });595#endif596 597 SCC &SourceSCC = *G->lookupSCC(SourceN);598 SCC &TargetSCC = *G->lookupSCC(TargetN);599 600 // If the two nodes are already part of the same SCC, we're also done as601 // we've just added more connectivity.602 if (&SourceSCC == &TargetSCC) {603 SourceN->setEdgeKind(TargetN, Edge::Call);604 return false; // No new cycle.605 }606 607 // At this point we leverage the postorder list of SCCs to detect when the608 // insertion of an edge changes the SCC structure in any way.609 //610 // First and foremost, we can eliminate the need for any changes when the611 // edge is toward the beginning of the postorder sequence because all edges612 // flow in that direction already. Thus adding a new one cannot form a cycle.613 int SourceIdx = SCCIndices[&SourceSCC];614 int TargetIdx = SCCIndices[&TargetSCC];615 if (TargetIdx < SourceIdx) {616 SourceN->setEdgeKind(TargetN, Edge::Call);617 return false; // No new cycle.618 }619 620 // Compute the SCCs which (transitively) reach the source.621 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {622#ifdef EXPENSIVE_CHECKS623 // Check that the RefSCC is still valid before computing this as the624 // results will be nonsensical of we've broken its invariants.625 verify();626#endif627 ConnectedSet.insert(&SourceSCC);628 auto IsConnected = [&](SCC &C) {629 for (Node &N : C)630 for (Edge &E : N->calls())631 if (ConnectedSet.count(G->lookupSCC(E.getNode())))632 return true;633 634 return false;635 };636 637 for (SCC *C :638 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))639 if (IsConnected(*C))640 ConnectedSet.insert(C);641 };642 643 // Use a normal worklist to find which SCCs the target connects to. We still644 // bound the search based on the range in the postorder list we care about,645 // but because this is forward connectivity we just "recurse" through the646 // edges.647 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {648#ifdef EXPENSIVE_CHECKS649 // Check that the RefSCC is still valid before computing this as the650 // results will be nonsensical of we've broken its invariants.651 verify();652#endif653 ConnectedSet.insert(&TargetSCC);654 SmallVector<SCC *, 4> Worklist;655 Worklist.push_back(&TargetSCC);656 do {657 SCC &C = *Worklist.pop_back_val();658 for (Node &N : C)659 for (Edge &E : *N) {660 if (!E.isCall())661 continue;662 SCC &EdgeC = *G->lookupSCC(E.getNode());663 if (&EdgeC.getOuterRefSCC() != this)664 // Not in this RefSCC...665 continue;666 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)667 // Not in the postorder sequence between source and target.668 continue;669 670 if (ConnectedSet.insert(&EdgeC).second)671 Worklist.push_back(&EdgeC);672 }673 } while (!Worklist.empty());674 };675 676 // Use a generic helper to update the postorder sequence of SCCs and return677 // a range of any SCCs connected into a cycle by inserting this edge. This678 // routine will also take care of updating the indices into the postorder679 // sequence.680 auto MergeRange = updatePostorderSequenceForEdgeInsertion(681 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,682 ComputeTargetConnectedSet);683 684 // Run the user's callback on the merged SCCs before we actually merge them.685 if (MergeCB)686 MergeCB(ArrayRef(MergeRange.begin(), MergeRange.end()));687 688 // If the merge range is empty, then adding the edge didn't actually form any689 // new cycles. We're done.690 if (MergeRange.empty()) {691 // Now that the SCC structure is finalized, flip the kind to call.692 SourceN->setEdgeKind(TargetN, Edge::Call);693 return false; // No new cycle.694 }695 696#ifdef EXPENSIVE_CHECKS697 // Before merging, check that the RefSCC remains valid after all the698 // postorder updates.699 verify();700#endif701 702 // Otherwise we need to merge all the SCCs in the cycle into a single result703 // SCC.704 //705 // NB: We merge into the target because all of these functions were already706 // reachable from the target, meaning any SCC-wide properties deduced about it707 // other than the set of functions within it will not have changed.708 for (SCC *C : MergeRange) {709 assert(C != &TargetSCC &&710 "We merge *into* the target and shouldn't process it here!");711 SCCIndices.erase(C);712 TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());713 for (Node *N : C->Nodes)714 G->SCCMap[N] = &TargetSCC;715 C->clear();716 DeletedSCCs.push_back(C);717 }718 719 // Erase the merged SCCs from the list and update the indices of the720 // remaining SCCs.721 int IndexOffset = MergeRange.end() - MergeRange.begin();722 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());723 for (SCC *C : make_range(EraseEnd, SCCs.end()))724 SCCIndices[C] -= IndexOffset;725 726 // Now that the SCC structure is finalized, flip the kind to call.727 SourceN->setEdgeKind(TargetN, Edge::Call);728 729 // And we're done, but we did form a new cycle.730 return true;731}732 733void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,734 Node &TargetN) {735 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");736 737#ifdef EXPENSIVE_CHECKS738 verify();739 auto VerifyOnExit = make_scope_exit([&]() { verify(); });740#endif741 742 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");743 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");744 assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&745 "Source and Target must be in separate SCCs for this to be trivial!");746 747 // Set the edge kind.748 SourceN->setEdgeKind(TargetN, Edge::Ref);749}750 751iterator_range<LazyCallGraph::RefSCC::iterator>752LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {753 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");754 755#ifdef EXPENSIVE_CHECKS756 verify();757 auto VerifyOnExit = make_scope_exit([&]() { verify(); });758#endif759 760 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");761 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");762 763 SCC &TargetSCC = *G->lookupSCC(TargetN);764 assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "765 "the same SCC to require the "766 "full CG update.");767 768 // Set the edge kind.769 SourceN->setEdgeKind(TargetN, Edge::Ref);770 771 // Otherwise we are removing a call edge from a single SCC. This may break772 // the cycle. In order to compute the new set of SCCs, we need to do a small773 // DFS over the nodes within the SCC to form any sub-cycles that remain as774 // distinct SCCs and compute a postorder over the resulting SCCs.775 //776 // However, we specially handle the target node. The target node is known to777 // reach all other nodes in the original SCC by definition. This means that778 // we want the old SCC to be replaced with an SCC containing that node as it779 // will be the root of whatever SCC DAG results from the DFS. Assumptions780 // about an SCC such as the set of functions called will continue to hold,781 // etc.782 783 SCC &OldSCC = TargetSCC;784 SmallVector<std::pair<Node *, EdgeSequence::call_iterator>, 16> DFSStack;785 SmallVector<Node *, 16> PendingSCCStack;786 SmallVector<SCC *, 4> NewSCCs;787 788 // Prepare the nodes for a fresh DFS.789 SmallVector<Node *, 16> Worklist;790 Worklist.swap(OldSCC.Nodes);791 for (Node *N : Worklist) {792 N->DFSNumber = N->LowLink = 0;793 G->SCCMap.erase(N);794 }795 796 // Force the target node to be in the old SCC. This also enables us to take797 // a very significant short-cut in the standard Tarjan walk to re-form SCCs798 // below: whenever we build an edge that reaches the target node, we know799 // that the target node eventually connects back to all other nodes in our800 // walk. As a consequence, we can detect and handle participants in that801 // cycle without walking all the edges that form this connection, and instead802 // by relying on the fundamental guarantee coming into this operation (all803 // nodes are reachable from the target due to previously forming an SCC).804 TargetN.DFSNumber = TargetN.LowLink = -1;805 OldSCC.Nodes.push_back(&TargetN);806 G->SCCMap[&TargetN] = &OldSCC;807 808 // Scan down the stack and DFS across the call edges.809 for (Node *RootN : Worklist) {810 assert(DFSStack.empty() &&811 "Cannot begin a new root with a non-empty DFS stack!");812 assert(PendingSCCStack.empty() &&813 "Cannot begin a new root with pending nodes for an SCC!");814 815 // Skip any nodes we've already reached in the DFS.816 if (RootN->DFSNumber != 0) {817 assert(RootN->DFSNumber == -1 &&818 "Shouldn't have any mid-DFS root nodes!");819 continue;820 }821 822 RootN->DFSNumber = RootN->LowLink = 1;823 int NextDFSNumber = 2;824 825 DFSStack.emplace_back(RootN, (*RootN)->call_begin());826 do {827 auto [N, I] = DFSStack.pop_back_val();828 auto E = (*N)->call_end();829 while (I != E) {830 Node &ChildN = I->getNode();831 if (ChildN.DFSNumber == 0) {832 // We haven't yet visited this child, so descend, pushing the current833 // node onto the stack.834 DFSStack.emplace_back(N, I);835 836 assert(!G->SCCMap.count(&ChildN) &&837 "Found a node with 0 DFS number but already in an SCC!");838 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;839 N = &ChildN;840 I = (*N)->call_begin();841 E = (*N)->call_end();842 continue;843 }844 845 // Check for the child already being part of some component.846 if (ChildN.DFSNumber == -1) {847 if (G->lookupSCC(ChildN) == &OldSCC) {848 // If the child is part of the old SCC, we know that it can reach849 // every other node, so we have formed a cycle. Pull the entire DFS850 // and pending stacks into it. See the comment above about setting851 // up the old SCC for why we do this.852 int OldSize = OldSCC.size();853 OldSCC.Nodes.push_back(N);854 OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());855 PendingSCCStack.clear();856 while (!DFSStack.empty())857 OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);858 for (Node &N : drop_begin(OldSCC, OldSize)) {859 N.DFSNumber = N.LowLink = -1;860 G->SCCMap[&N] = &OldSCC;861 }862 N = nullptr;863 break;864 }865 866 // If the child has already been added to some child component, it867 // couldn't impact the low-link of this parent because it isn't868 // connected, and thus its low-link isn't relevant so skip it.869 ++I;870 continue;871 }872 873 // Track the lowest linked child as the lowest link for this node.874 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");875 if (ChildN.LowLink < N->LowLink)876 N->LowLink = ChildN.LowLink;877 878 // Move to the next edge.879 ++I;880 }881 if (!N)882 // Cleared the DFS early, start another round.883 break;884 885 // We've finished processing N and its descendants, put it on our pending886 // SCC stack to eventually get merged into an SCC of nodes.887 PendingSCCStack.push_back(N);888 889 // If this node is linked to some lower entry, continue walking up the890 // stack.891 if (N->LowLink != N->DFSNumber)892 continue;893 894 // Otherwise, we've completed an SCC. Append it to our post order list of895 // SCCs.896 int RootDFSNumber = N->DFSNumber;897 // Find the range of the node stack by walking down until we pass the898 // root DFS number.899 auto SCCNodes = make_range(900 PendingSCCStack.rbegin(),901 find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {902 return N->DFSNumber < RootDFSNumber;903 }));904 905 // Form a new SCC out of these nodes and then clear them off our pending906 // stack.907 NewSCCs.push_back(G->createSCC(*this, SCCNodes));908 for (Node &N : *NewSCCs.back()) {909 N.DFSNumber = N.LowLink = -1;910 G->SCCMap[&N] = NewSCCs.back();911 }912 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());913 } while (!DFSStack.empty());914 }915 916 // Insert the remaining SCCs before the old one. The old SCC can reach all917 // other SCCs we form because it contains the target node of the removed edge918 // of the old SCC. This means that we will have edges into all the new SCCs,919 // which means the old one must come last for postorder.920 int OldIdx = SCCIndices[&OldSCC];921 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());922 923 // Update the mapping from SCC* to index to use the new SCC*s, and remove the924 // old SCC from the mapping.925 for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)926 SCCIndices[SCCs[Idx]] = Idx;927 928 return make_range(SCCs.begin() + OldIdx,929 SCCs.begin() + OldIdx + NewSCCs.size());930}931 932void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,933 Node &TargetN) {934 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");935 936 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");937 assert(G->lookupRefSCC(TargetN) != this &&938 "Target must not be in this RefSCC.");939#ifdef EXPENSIVE_CHECKS940 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&941 "Target must be a descendant of the Source.");942#endif943 944 // Edges between RefSCCs are the same regardless of call or ref, so we can945 // just flip the edge here.946 SourceN->setEdgeKind(TargetN, Edge::Call);947 948#ifdef EXPENSIVE_CHECKS949 verify();950#endif951}952 953void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,954 Node &TargetN) {955 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");956 957 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");958 assert(G->lookupRefSCC(TargetN) != this &&959 "Target must not be in this RefSCC.");960#ifdef EXPENSIVE_CHECKS961 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&962 "Target must be a descendant of the Source.");963#endif964 965 // Edges between RefSCCs are the same regardless of call or ref, so we can966 // just flip the edge here.967 SourceN->setEdgeKind(TargetN, Edge::Ref);968 969#ifdef EXPENSIVE_CHECKS970 verify();971#endif972}973 974void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,975 Node &TargetN) {976 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");977 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");978 979 SourceN->insertEdgeInternal(TargetN, Edge::Ref);980 981#ifdef EXPENSIVE_CHECKS982 verify();983#endif984}985 986void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,987 Edge::Kind EK) {988 // First insert it into the caller.989 SourceN->insertEdgeInternal(TargetN, EK);990 991 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");992 993 assert(G->lookupRefSCC(TargetN) != this &&994 "Target must not be in this RefSCC.");995#ifdef EXPENSIVE_CHECKS996 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&997 "Target must be a descendant of the Source.");998#endif999 1000#ifdef EXPENSIVE_CHECKS1001 verify();1002#endif1003}1004 1005SmallVector<LazyCallGraph::RefSCC *, 1>1006LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {1007 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");1008 RefSCC &SourceC = *G->lookupRefSCC(SourceN);1009 assert(&SourceC != this && "Source must not be in this RefSCC.");1010#ifdef EXPENSIVE_CHECKS1011 assert(SourceC.isDescendantOf(*this) &&1012 "Source must be a descendant of the Target.");1013#endif1014 1015 SmallVector<RefSCC *, 1> DeletedRefSCCs;1016 1017#ifdef EXPENSIVE_CHECKS1018 verify();1019 auto VerifyOnExit = make_scope_exit([&]() { verify(); });1020#endif1021 1022 int SourceIdx = G->RefSCCIndices[&SourceC];1023 int TargetIdx = G->RefSCCIndices[this];1024 assert(SourceIdx < TargetIdx &&1025 "Postorder list doesn't see edge as incoming!");1026 1027 // Compute the RefSCCs which (transitively) reach the source. We do this by1028 // working backwards from the source using the parent set in each RefSCC,1029 // skipping any RefSCCs that don't fall in the postorder range. This has the1030 // advantage of walking the sparser parent edge (in high fan-out graphs) but1031 // more importantly this removes examining all forward edges in all RefSCCs1032 // within the postorder range which aren't in fact connected. Only connected1033 // RefSCCs (and their edges) are visited here.1034 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {1035 Set.insert(&SourceC);1036 auto IsConnected = [&](RefSCC &RC) {1037 for (SCC &C : RC)1038 for (Node &N : C)1039 for (Edge &E : *N)1040 if (Set.count(G->lookupRefSCC(E.getNode())))1041 return true;1042 1043 return false;1044 };1045 1046 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,1047 G->PostOrderRefSCCs.begin() + TargetIdx + 1))1048 if (IsConnected(*C))1049 Set.insert(C);1050 };1051 1052 // Use a normal worklist to find which SCCs the target connects to. We still1053 // bound the search based on the range in the postorder list we care about,1054 // but because this is forward connectivity we just "recurse" through the1055 // edges.1056 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {1057 Set.insert(this);1058 SmallVector<RefSCC *, 4> Worklist;1059 Worklist.push_back(this);1060 do {1061 RefSCC &RC = *Worklist.pop_back_val();1062 for (SCC &C : RC)1063 for (Node &N : C)1064 for (Edge &E : *N) {1065 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());1066 if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)1067 // Not in the postorder sequence between source and target.1068 continue;1069 1070 if (Set.insert(&EdgeRC).second)1071 Worklist.push_back(&EdgeRC);1072 }1073 } while (!Worklist.empty());1074 };1075 1076 // Use a generic helper to update the postorder sequence of RefSCCs and return1077 // a range of any RefSCCs connected into a cycle by inserting this edge. This1078 // routine will also take care of updating the indices into the postorder1079 // sequence.1080 iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =1081 updatePostorderSequenceForEdgeInsertion(1082 SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,1083 ComputeSourceConnectedSet, ComputeTargetConnectedSet);1084 1085 // Build a set, so we can do fast tests for whether a RefSCC will end up as1086 // part of the merged RefSCC.1087 SmallPtrSet<RefSCC *, 16> MergeSet(llvm::from_range, MergeRange);1088 1089 // This RefSCC will always be part of that set, so just insert it here.1090 MergeSet.insert(this);1091 1092 // Now that we have identified all the SCCs which need to be merged into1093 // a connected set with the inserted edge, merge all of them into this SCC.1094 SmallVector<SCC *, 16> MergedSCCs;1095 int SCCIndex = 0;1096 for (RefSCC *RC : MergeRange) {1097 assert(RC != this && "We're merging into the target RefSCC, so it "1098 "shouldn't be in the range.");1099 1100 // Walk the inner SCCs to update their up-pointer and walk all the edges to1101 // update any parent sets.1102 // FIXME: We should try to find a way to avoid this (rather expensive) edge1103 // walk by updating the parent sets in some other manner.1104 for (SCC &InnerC : *RC) {1105 InnerC.OuterRefSCC = this;1106 SCCIndices[&InnerC] = SCCIndex++;1107 for (Node &N : InnerC)1108 G->SCCMap[&N] = &InnerC;1109 }1110 1111 // Now merge in the SCCs. We can actually move here so try to reuse storage1112 // the first time through.1113 if (MergedSCCs.empty())1114 MergedSCCs = std::move(RC->SCCs);1115 else1116 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());1117 RC->SCCs.clear();1118 DeletedRefSCCs.push_back(RC);1119 }1120 1121 // Append our original SCCs to the merged list and move it into place.1122 for (SCC &InnerC : *this)1123 SCCIndices[&InnerC] = SCCIndex++;1124 MergedSCCs.append(SCCs.begin(), SCCs.end());1125 SCCs = std::move(MergedSCCs);1126 1127 // Remove the merged away RefSCCs from the post order sequence.1128 for (RefSCC *RC : MergeRange)1129 G->RefSCCIndices.erase(RC);1130 int IndexOffset = MergeRange.end() - MergeRange.begin();1131 auto EraseEnd =1132 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());1133 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))1134 G->RefSCCIndices[RC] -= IndexOffset;1135 1136 // At this point we have a merged RefSCC with a post-order SCCs list, just1137 // connect the nodes to form the new edge.1138 SourceN->insertEdgeInternal(TargetN, Edge::Ref);1139 1140 // We return the list of SCCs which were merged so that callers can1141 // invalidate any data they have associated with those SCCs. Note that these1142 // SCCs are no longer in an interesting state (they are totally empty) but1143 // the pointers will remain stable for the life of the graph itself.1144 return DeletedRefSCCs;1145}1146 1147void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {1148 assert(G->lookupRefSCC(SourceN) == this &&1149 "The source must be a member of this RefSCC.");1150 assert(G->lookupRefSCC(TargetN) != this &&1151 "The target must not be a member of this RefSCC");1152 1153#ifdef EXPENSIVE_CHECKS1154 verify();1155 auto VerifyOnExit = make_scope_exit([&]() { verify(); });1156#endif1157 1158 // First remove it from the node.1159 bool Removed = SourceN->removeEdgeInternal(TargetN);1160 (void)Removed;1161 assert(Removed && "Target not in the edge set for this caller?");1162}1163 1164SmallVector<LazyCallGraph::RefSCC *, 1>1165LazyCallGraph::RefSCC::removeInternalRefEdges(1166 ArrayRef<std::pair<Node *, Node *>> Edges) {1167 // We return a list of the resulting *new* RefSCCs in post-order.1168 SmallVector<RefSCC *, 1> Result;1169 1170#ifdef EXPENSIVE_CHECKS1171 // Verify the RefSCC is valid to start with and that either we return an empty1172 // list of result RefSCCs and this RefSCC remains valid, or we return new1173 // RefSCCs and this RefSCC is dead.1174 verify();1175 auto VerifyOnExit = make_scope_exit([&]() {1176 // If we didn't replace our RefSCC with new ones, check that this one1177 // remains valid.1178 if (G)1179 verify();1180 });1181#endif1182 1183 // First remove the actual edges.1184 for (auto [SourceN, TargetN] : Edges) {1185 assert(!(**SourceN)[*TargetN].isCall() &&1186 "Cannot remove a call edge, it must first be made a ref edge");1187 1188 bool Removed = (*SourceN)->removeEdgeInternal(*TargetN);1189 (void)Removed;1190 assert(Removed && "Target not in the edge set for this caller?");1191 }1192 1193 // Direct self references don't impact the ref graph at all.1194 // If all targets are in the same SCC as the source, because no call edges1195 // were removed there is no RefSCC structure change.1196 if (llvm::all_of(Edges, [&](std::pair<Node *, Node *> E) {1197 return E.first == E.second ||1198 G->lookupSCC(*E.first) == G->lookupSCC(*E.second);1199 }))1200 return Result;1201 1202 // We build somewhat synthetic new RefSCCs by providing a postorder mapping1203 // for each inner SCC. We store these inside the low-link field of the nodes1204 // rather than associated with SCCs because this saves a round-trip through1205 // the node->SCC map and in the common case, SCCs are small. We will verify1206 // that we always give the same number to every node in the SCC such that1207 // these are equivalent.1208 int PostOrderNumber = 0;1209 1210 // Reset all the other nodes to prepare for a DFS over them, and add them to1211 // our worklist.1212 SmallVector<Node *, 8> Worklist;1213 for (SCC *C : SCCs) {1214 for (Node &N : *C)1215 N.DFSNumber = N.LowLink = 0;1216 1217 Worklist.append(C->Nodes.begin(), C->Nodes.end());1218 }1219 1220 // Track the number of nodes in this RefSCC so that we can quickly recognize1221 // an important special case of the edge removal not breaking the cycle of1222 // this RefSCC.1223 const int NumRefSCCNodes = Worklist.size();1224 1225 SmallVector<std::pair<Node *, EdgeSequence::iterator>, 4> DFSStack;1226 SmallVector<Node *, 4> PendingRefSCCStack;1227 do {1228 assert(DFSStack.empty() &&1229 "Cannot begin a new root with a non-empty DFS stack!");1230 assert(PendingRefSCCStack.empty() &&1231 "Cannot begin a new root with pending nodes for an SCC!");1232 1233 Node *RootN = Worklist.pop_back_val();1234 // Skip any nodes we've already reached in the DFS.1235 if (RootN->DFSNumber != 0) {1236 assert(RootN->DFSNumber == -1 &&1237 "Shouldn't have any mid-DFS root nodes!");1238 continue;1239 }1240 1241 RootN->DFSNumber = RootN->LowLink = 1;1242 int NextDFSNumber = 2;1243 1244 DFSStack.emplace_back(RootN, (*RootN)->begin());1245 do {1246 auto [N, I] = DFSStack.pop_back_val();1247 auto E = (*N)->end();1248 1249 assert(N->DFSNumber != 0 && "We should always assign a DFS number "1250 "before processing a node.");1251 1252 while (I != E) {1253 Node &ChildN = I->getNode();1254 if (ChildN.DFSNumber == 0) {1255 // Mark that we should start at this child when next this node is the1256 // top of the stack. We don't start at the next child to ensure this1257 // child's lowlink is reflected.1258 DFSStack.emplace_back(N, I);1259 1260 // Continue, resetting to the child node.1261 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;1262 N = &ChildN;1263 I = ChildN->begin();1264 E = ChildN->end();1265 continue;1266 }1267 if (ChildN.DFSNumber == -1) {1268 // If this child isn't currently in this RefSCC, no need to process1269 // it.1270 ++I;1271 continue;1272 }1273 1274 // Track the lowest link of the children, if any are still in the stack.1275 // Any child not on the stack will have a LowLink of -1.1276 assert(ChildN.LowLink != 0 &&1277 "Low-link must not be zero with a non-zero DFS number.");1278 if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)1279 N->LowLink = ChildN.LowLink;1280 ++I;1281 }1282 1283 // We've finished processing N and its descendants, put it on our pending1284 // stack to eventually get merged into a RefSCC.1285 PendingRefSCCStack.push_back(N);1286 1287 // If this node is linked to some lower entry, continue walking up the1288 // stack.1289 if (N->LowLink != N->DFSNumber) {1290 assert(!DFSStack.empty() &&1291 "We never found a viable root for a RefSCC to pop off!");1292 continue;1293 }1294 1295 // Otherwise, form a new RefSCC from the top of the pending node stack.1296 int RefSCCNumber = PostOrderNumber++;1297 int RootDFSNumber = N->DFSNumber;1298 1299 // Find the range of the node stack by walking down until we pass the1300 // root DFS number. Update the DFS numbers and low link numbers in the1301 // process to avoid re-walking this list where possible.1302 auto StackRI = find_if(reverse(PendingRefSCCStack), [&](Node *N) {1303 if (N->DFSNumber < RootDFSNumber)1304 // We've found the bottom.1305 return true;1306 1307 // Update this node and keep scanning.1308 N->DFSNumber = -1;1309 // Save the post-order number in the lowlink field so that we can use1310 // it to map SCCs into new RefSCCs after we finish the DFS.1311 N->LowLink = RefSCCNumber;1312 return false;1313 });1314 auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());1315 1316 // If we find a cycle containing all nodes originally in this RefSCC then1317 // the removal hasn't changed the structure at all. This is an important1318 // special case, and we can directly exit the entire routine more1319 // efficiently as soon as we discover it.1320 if (llvm::size(RefSCCNodes) == NumRefSCCNodes) {1321 // Clear out the low link field as we won't need it.1322 for (Node *N : RefSCCNodes)1323 N->LowLink = -1;1324 // Return the empty result immediately.1325 return Result;1326 }1327 1328 // We've already marked the nodes internally with the RefSCC number so1329 // just clear them off the stack and continue.1330 PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());1331 } while (!DFSStack.empty());1332 1333 assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");1334 assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");1335 } while (!Worklist.empty());1336 1337 assert(PostOrderNumber > 1 &&1338 "Should never finish the DFS when the existing RefSCC remains valid!");1339 1340 // Otherwise we create a collection of new RefSCC nodes and build1341 // a radix-sort style map from postorder number to these new RefSCCs. We then1342 // append SCCs to each of these RefSCCs in the order they occurred in the1343 // original SCCs container.1344 for (int I = 0; I < PostOrderNumber; ++I)1345 Result.push_back(G->createRefSCC(*G));1346 1347 // Insert the resulting postorder sequence into the global graph postorder1348 // sequence before the current RefSCC in that sequence, and then remove the1349 // current one.1350 //1351 // FIXME: It'd be nice to change the APIs so that we returned an iterator1352 // range over the global postorder sequence and generally use that sequence1353 // rather than building a separate result vector here.1354 int Idx = G->getRefSCCIndex(*this);1355 G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx);1356 G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(),1357 Result.end());1358 for (int I : seq<int>(Idx, G->PostOrderRefSCCs.size()))1359 G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I;1360 1361 for (SCC *C : SCCs) {1362 // We store the SCC number in the node's low-link field above.1363 int SCCNumber = C->begin()->LowLink;1364 // Clear out all the SCC's node's low-link fields now that we're done1365 // using them as side-storage.1366 for (Node &N : *C) {1367 assert(N.LowLink == SCCNumber &&1368 "Cannot have different numbers for nodes in the same SCC!");1369 N.LowLink = -1;1370 }1371 1372 RefSCC &RC = *Result[SCCNumber];1373 int SCCIndex = RC.SCCs.size();1374 RC.SCCs.push_back(C);1375 RC.SCCIndices[C] = SCCIndex;1376 C->OuterRefSCC = &RC;1377 }1378 1379 // Now that we've moved things into the new RefSCCs, clear out our current1380 // one.1381 G = nullptr;1382 SCCs.clear();1383 SCCIndices.clear();1384 1385#ifdef EXPENSIVE_CHECKS1386 // Verify the new RefSCCs we've built.1387 for (RefSCC *RC : Result)1388 RC->verify();1389#endif1390 1391 // Return the new list of SCCs.1392 return Result;1393}1394 1395void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,1396 Node &TargetN) {1397#ifdef EXPENSIVE_CHECKS1398 auto ExitVerifier = make_scope_exit([this] { verify(); });1399 1400 // Check that we aren't breaking some invariants of the SCC graph. Note that1401 // this is quadratic in the number of edges in the call graph!1402 SCC &SourceC = *G->lookupSCC(SourceN);1403 SCC &TargetC = *G->lookupSCC(TargetN);1404 if (&SourceC != &TargetC)1405 assert(SourceC.isAncestorOf(TargetC) &&1406 "Call edge is not trivial in the SCC graph!");1407#endif1408 1409 // First insert it into the source or find the existing edge.1410 auto [Iterator, Inserted] =1411 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());1412 if (!Inserted) {1413 // Already an edge, just update it.1414 Edge &E = SourceN->Edges[Iterator->second];1415 if (E.isCall())1416 return; // Nothing to do!1417 E.setKind(Edge::Call);1418 } else {1419 // Create the new edge.1420 SourceN->Edges.emplace_back(TargetN, Edge::Call);1421 }1422}1423 1424void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {1425#ifdef EXPENSIVE_CHECKS1426 auto ExitVerifier = make_scope_exit([this] { verify(); });1427 1428 // Check that we aren't breaking some invariants of the RefSCC graph.1429 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);1430 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);1431 if (&SourceRC != &TargetRC)1432 assert(SourceRC.isAncestorOf(TargetRC) &&1433 "Ref edge is not trivial in the RefSCC graph!");1434#endif1435 1436 // First insert it into the source or find the existing edge.1437 auto [Iterator, Inserted] =1438 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());1439 (void)Iterator;1440 if (!Inserted)1441 // Already an edge, we're done.1442 return;1443 1444 // Create the new edge.1445 SourceN->Edges.emplace_back(TargetN, Edge::Ref);1446}1447 1448void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {1449 Function &OldF = N.getFunction();1450 1451#ifdef EXPENSIVE_CHECKS1452 auto ExitVerifier = make_scope_exit([this] { verify(); });1453 1454 assert(G->lookupRefSCC(N) == this &&1455 "Cannot replace the function of a node outside this RefSCC.");1456 1457 assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&1458 "Must not have already walked the new function!'");1459 1460 // It is important that this replacement not introduce graph changes so we1461 // insist that the caller has already removed every use of the original1462 // function and that all uses of the new function correspond to existing1463 // edges in the graph. The common and expected way to use this is when1464 // replacing the function itself in the IR without changing the call graph1465 // shape and just updating the analysis based on that.1466 assert(&OldF != &NewF && "Cannot replace a function with itself!");1467 assert(OldF.use_empty() &&1468 "Must have moved all uses from the old function to the new!");1469#endif1470 1471 N.replaceFunction(NewF);1472 1473 // Update various call graph maps.1474 G->NodeMap.erase(&OldF);1475 G->NodeMap[&NewF] = &N;1476 1477 // Update lib functions.1478 if (G->isLibFunction(OldF)) {1479 G->LibFunctions.remove(&OldF);1480 G->LibFunctions.insert(&NewF);1481 }1482}1483 1484void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {1485 assert(SCCMap.empty() &&1486 "This method cannot be called after SCCs have been formed!");1487 1488 return SourceN->insertEdgeInternal(TargetN, EK);1489}1490 1491void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {1492 assert(SCCMap.empty() &&1493 "This method cannot be called after SCCs have been formed!");1494 1495 bool Removed = SourceN->removeEdgeInternal(TargetN);1496 (void)Removed;1497 assert(Removed && "Target not in the edge set for this caller?");1498}1499 1500void LazyCallGraph::markDeadFunction(Function &F) {1501 // FIXME: This is unnecessarily restrictive. We should be able to remove1502 // functions which recursively call themselves.1503 assert(F.hasZeroLiveUses() &&1504 "This routine should only be called on trivially dead functions!");1505 1506 // We shouldn't remove library functions as they are never really dead while1507 // the call graph is in use -- every function definition refers to them.1508 assert(!isLibFunction(F) &&1509 "Must not remove lib functions from the call graph!");1510 1511 auto NI = NodeMap.find(&F);1512 assert(NI != NodeMap.end() && "Removed function should be known!");1513 1514 Node &N = *NI->second;1515 1516 // Remove all call edges out of dead function.1517 for (Edge E : *N) {1518 if (E.isCall())1519 N->setEdgeKind(E.getNode(), Edge::Ref);1520 }1521}1522 1523void LazyCallGraph::removeDeadFunctions(ArrayRef<Function *> DeadFs) {1524 if (DeadFs.empty())1525 return;1526 1527 // Group dead functions by the RefSCC they're in.1528 DenseMap<RefSCC *, SmallVector<Node *, 1>> RCs;1529 for (Function *DeadF : DeadFs) {1530 Node *N = lookup(*DeadF);1531#ifndef NDEBUG1532 for (Edge &E : **N) {1533 assert(!E.isCall() &&1534 "dead function shouldn't have any outgoing call edges");1535 }1536#endif1537 RefSCC *RC = lookupRefSCC(*N);1538 RCs[RC].push_back(N);1539 }1540 // Remove outgoing edges from all dead functions. Dead functions should1541 // already have had their call edges removed in markDeadFunction(), so we only1542 // need to worry about spurious ref edges.1543 for (auto [RC, DeadNs] : RCs) {1544 SmallVector<std::pair<Node *, Node *>> InternalEdgesToRemove;1545 for (Node *DeadN : DeadNs) {1546 for (Edge &E : **DeadN) {1547 if (lookupRefSCC(E.getNode()) == RC)1548 InternalEdgesToRemove.push_back({DeadN, &E.getNode()});1549 else1550 RC->removeOutgoingEdge(*DeadN, E.getNode());1551 }1552 }1553 // We ignore the returned RefSCCs since at this point we're done with CGSCC1554 // iteration and don't need to add it to any worklists.1555 (void)RC->removeInternalRefEdges(InternalEdgesToRemove);1556 for (Node *DeadN : DeadNs) {1557 RefSCC *DeadRC = lookupRefSCC(*DeadN);1558 assert(DeadRC->size() == 1);1559 assert(DeadRC->begin()->size() == 1);1560 DeadRC->clear();1561 DeadRC->G = nullptr;1562 }1563 }1564 // Clean up data structures.1565 for (Function *DeadF : DeadFs) {1566 Node &N = *lookup(*DeadF);1567 1568 EntryEdges.removeEdgeInternal(N);1569 SCCMap.erase(SCCMap.find(&N));1570 NodeMap.erase(NodeMap.find(DeadF));1571 1572 N.clear();1573 N.G = nullptr;1574 N.F = nullptr;1575 }1576}1577 1578// Gets the Edge::Kind from one function to another by looking at the function's1579// instructions. Asserts if there is no edge.1580// Useful for determining what type of edge should exist between functions when1581// the edge hasn't been created yet.1582static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction,1583 Function &NewFunction) {1584 // In release builds, assume that if there are no direct calls to the new1585 // function, then there is a ref edge. In debug builds, keep track of1586 // references to assert that there is actually a ref edge if there is no call1587 // edge.1588#ifndef NDEBUG1589 SmallVector<Constant *, 16> Worklist;1590 SmallPtrSet<Constant *, 16> Visited;1591#endif1592 1593 for (Instruction &I : instructions(OriginalFunction)) {1594 if (auto *CB = dyn_cast<CallBase>(&I)) {1595 if (Function *Callee = CB->getCalledFunction()) {1596 if (Callee == &NewFunction)1597 return LazyCallGraph::Edge::Kind::Call;1598 }1599 }1600#ifndef NDEBUG1601 for (Value *Op : I.operand_values()) {1602 if (Constant *C = dyn_cast<Constant>(Op)) {1603 if (Visited.insert(C).second)1604 Worklist.push_back(C);1605 }1606 }1607#endif1608 }1609 1610#ifndef NDEBUG1611 bool FoundNewFunction = false;1612 LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &F) {1613 if (&F == &NewFunction)1614 FoundNewFunction = true;1615 });1616 assert(FoundNewFunction && "No edge from original function to new function");1617#endif1618 1619 return LazyCallGraph::Edge::Kind::Ref;1620}1621 1622void LazyCallGraph::addSplitFunction(Function &OriginalFunction,1623 Function &NewFunction) {1624 assert(lookup(OriginalFunction) &&1625 "Original function's node should already exist");1626 Node &OriginalN = get(OriginalFunction);1627 SCC *OriginalC = lookupSCC(OriginalN);1628 RefSCC *OriginalRC = lookupRefSCC(OriginalN);1629 1630#ifdef EXPENSIVE_CHECKS1631 OriginalRC->verify();1632 auto VerifyOnExit = make_scope_exit([&]() { OriginalRC->verify(); });1633#endif1634 1635 assert(!lookup(NewFunction) &&1636 "New function's node should not already exist");1637 Node &NewN = initNode(NewFunction);1638 1639 Edge::Kind EK = getEdgeKind(OriginalFunction, NewFunction);1640 1641 SCC *NewC = nullptr;1642 for (Edge &E : *NewN) {1643 Node &EN = E.getNode();1644 if (EK == Edge::Kind::Call && E.isCall() && lookupSCC(EN) == OriginalC) {1645 // If the edge to the new function is a call edge and there is a call edge1646 // from the new function to any function in the original function's SCC,1647 // it is in the same SCC (and RefSCC) as the original function.1648 NewC = OriginalC;1649 NewC->Nodes.push_back(&NewN);1650 break;1651 }1652 }1653 1654 if (!NewC) {1655 for (Edge &E : *NewN) {1656 Node &EN = E.getNode();1657 if (lookupRefSCC(EN) == OriginalRC) {1658 // If there is any edge from the new function to any function in the1659 // original function's RefSCC, it is in the same RefSCC as the original1660 // function but a new SCC.1661 RefSCC *NewRC = OriginalRC;1662 NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));1663 1664 // The new function's SCC is not the same as the original function's1665 // SCC, since that case was handled earlier. If the edge from the1666 // original function to the new function was a call edge, then we need1667 // to insert the newly created function's SCC before the original1668 // function's SCC. Otherwise, either the new SCC comes after the1669 // original function's SCC, or it doesn't matter, and in both cases we1670 // can add it to the very end.1671 int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC]1672 : NewRC->SCCIndices.size();1673 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);1674 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)1675 NewRC->SCCIndices[NewRC->SCCs[I]] = I;1676 1677 break;1678 }1679 }1680 }1681 1682 if (!NewC) {1683 // We didn't find any edges back to the original function's RefSCC, so the1684 // new function belongs in a new RefSCC. The new RefSCC goes before the1685 // original function's RefSCC.1686 RefSCC *NewRC = createRefSCC(*this);1687 NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));1688 NewRC->SCCIndices[NewC] = 0;1689 NewRC->SCCs.push_back(NewC);1690 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;1691 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);1692 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)1693 RefSCCIndices[PostOrderRefSCCs[I]] = I;1694 }1695 1696 SCCMap[&NewN] = NewC;1697 1698 OriginalN->insertEdgeInternal(NewN, EK);1699}1700 1701void LazyCallGraph::addSplitRefRecursiveFunctions(1702 Function &OriginalFunction, ArrayRef<Function *> NewFunctions) {1703 assert(!NewFunctions.empty() && "Can't add zero functions");1704 assert(lookup(OriginalFunction) &&1705 "Original function's node should already exist");1706 Node &OriginalN = get(OriginalFunction);1707 RefSCC *OriginalRC = lookupRefSCC(OriginalN);1708 1709#ifdef EXPENSIVE_CHECKS1710 OriginalRC->verify();1711 auto VerifyOnExit = make_scope_exit([&]() {1712 OriginalRC->verify();1713 for (Function *NewFunction : NewFunctions)1714 lookupRefSCC(get(*NewFunction))->verify();1715 });1716#endif1717 1718 bool ExistsRefToOriginalRefSCC = false;1719 1720 for (Function *NewFunction : NewFunctions) {1721 Node &NewN = initNode(*NewFunction);1722 1723 OriginalN->insertEdgeInternal(NewN, Edge::Kind::Ref);1724 1725 // Check if there is any edge from any new function back to any function in1726 // the original function's RefSCC.1727 for (Edge &E : *NewN) {1728 if (lookupRefSCC(E.getNode()) == OriginalRC) {1729 ExistsRefToOriginalRefSCC = true;1730 break;1731 }1732 }1733 }1734 1735 RefSCC *NewRC;1736 if (ExistsRefToOriginalRefSCC) {1737 // If there is any edge from any new function to any function in the1738 // original function's RefSCC, all new functions will be in the same RefSCC1739 // as the original function.1740 NewRC = OriginalRC;1741 } else {1742 // Otherwise the new functions are in their own RefSCC.1743 NewRC = createRefSCC(*this);1744 // The new RefSCC goes before the original function's RefSCC in postorder1745 // since there are only edges from the original function's RefSCC to the new1746 // RefSCC.1747 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;1748 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);1749 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)1750 RefSCCIndices[PostOrderRefSCCs[I]] = I;1751 }1752 1753 for (Function *NewFunction : NewFunctions) {1754 Node &NewN = get(*NewFunction);1755 // Each new function is in its own new SCC. The original function can only1756 // have a ref edge to new functions, and no other existing functions can1757 // have references to new functions. Each new function only has a ref edge1758 // to the other new functions.1759 SCC *NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));1760 // The new SCCs are either sibling SCCs or parent SCCs to all other existing1761 // SCCs in the RefSCC. Either way, they can go at the back of the postorder1762 // SCC list.1763 auto Index = NewRC->SCCIndices.size();1764 NewRC->SCCIndices[NewC] = Index;1765 NewRC->SCCs.push_back(NewC);1766 SCCMap[&NewN] = NewC;1767 }1768 1769#ifndef NDEBUG1770 for (Function *F1 : NewFunctions) {1771 assert(getEdgeKind(OriginalFunction, *F1) == Edge::Kind::Ref &&1772 "Expected ref edges from original function to every new function");1773 Node &N1 = get(*F1);1774 for (Function *F2 : NewFunctions) {1775 if (F1 == F2)1776 continue;1777 Node &N2 = get(*F2);1778 assert(!N1->lookup(N2)->isCall() &&1779 "Edges between new functions must be ref edges");1780 }1781 }1782#endif1783}1784 1785LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {1786 return *new (MappedN = BPA.Allocate()) Node(*this, F);1787}1788 1789void LazyCallGraph::updateGraphPtrs() {1790 // Walk the node map to update their graph pointers. While this iterates in1791 // an unstable order, the order has no effect, so it remains correct.1792 for (auto &FunctionNodePair : NodeMap)1793 FunctionNodePair.second->G = this;1794 1795 for (auto *RC : PostOrderRefSCCs)1796 RC->G = this;1797}1798 1799LazyCallGraph::Node &LazyCallGraph::initNode(Function &F) {1800 Node &N = get(F);1801 N.DFSNumber = N.LowLink = -1;1802 N.populate();1803 NodeMap[&F] = &N;1804 return N;1805}1806 1807template <typename RootsT, typename GetBeginT, typename GetEndT,1808 typename GetNodeT, typename FormSCCCallbackT>1809void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,1810 GetEndT &&GetEnd, GetNodeT &&GetNode,1811 FormSCCCallbackT &&FormSCC) {1812 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));1813 1814 SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;1815 SmallVector<Node *, 16> PendingSCCStack;1816 1817 // Scan down the stack and DFS across the call edges.1818 for (Node *RootN : Roots) {1819 assert(DFSStack.empty() &&1820 "Cannot begin a new root with a non-empty DFS stack!");1821 assert(PendingSCCStack.empty() &&1822 "Cannot begin a new root with pending nodes for an SCC!");1823 1824 // Skip any nodes we've already reached in the DFS.1825 if (RootN->DFSNumber != 0) {1826 assert(RootN->DFSNumber == -1 &&1827 "Shouldn't have any mid-DFS root nodes!");1828 continue;1829 }1830 1831 RootN->DFSNumber = RootN->LowLink = 1;1832 int NextDFSNumber = 2;1833 1834 DFSStack.emplace_back(RootN, GetBegin(*RootN));1835 do {1836 auto [N, I] = DFSStack.pop_back_val();1837 auto E = GetEnd(*N);1838 while (I != E) {1839 Node &ChildN = GetNode(I);1840 if (ChildN.DFSNumber == 0) {1841 // We haven't yet visited this child, so descend, pushing the current1842 // node onto the stack.1843 DFSStack.emplace_back(N, I);1844 1845 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;1846 N = &ChildN;1847 I = GetBegin(*N);1848 E = GetEnd(*N);1849 continue;1850 }1851 1852 // If the child has already been added to some child component, it1853 // couldn't impact the low-link of this parent because it isn't1854 // connected, and thus its low-link isn't relevant so skip it.1855 if (ChildN.DFSNumber == -1) {1856 ++I;1857 continue;1858 }1859 1860 // Track the lowest linked child as the lowest link for this node.1861 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");1862 if (ChildN.LowLink < N->LowLink)1863 N->LowLink = ChildN.LowLink;1864 1865 // Move to the next edge.1866 ++I;1867 }1868 1869 // We've finished processing N and its descendants, put it on our pending1870 // SCC stack to eventually get merged into an SCC of nodes.1871 PendingSCCStack.push_back(N);1872 1873 // If this node is linked to some lower entry, continue walking up the1874 // stack.1875 if (N->LowLink != N->DFSNumber)1876 continue;1877 1878 // Otherwise, we've completed an SCC. Append it to our post order list of1879 // SCCs.1880 int RootDFSNumber = N->DFSNumber;1881 // Find the range of the node stack by walking down until we pass the1882 // root DFS number.1883 auto SCCNodes = make_range(1884 PendingSCCStack.rbegin(),1885 find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {1886 return N->DFSNumber < RootDFSNumber;1887 }));1888 // Form a new SCC out of these nodes and then clear them off our pending1889 // stack.1890 FormSCC(SCCNodes);1891 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());1892 } while (!DFSStack.empty());1893 }1894}1895 1896/// Build the internal SCCs for a RefSCC from a sequence of nodes.1897///1898/// Appends the SCCs to the provided vector and updates the map with their1899/// indices. Both the vector and map must be empty when passed into this1900/// routine.1901void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {1902 assert(RC.SCCs.empty() && "Already built SCCs!");1903 assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");1904 1905 for (Node *N : Nodes) {1906 assert(N->LowLink >= (*Nodes.begin())->LowLink &&1907 "We cannot have a low link in an SCC lower than its root on the "1908 "stack!");1909 1910 // This node will go into the next RefSCC, clear out its DFS and low link1911 // as we scan.1912 N->DFSNumber = N->LowLink = 0;1913 }1914 1915 // Each RefSCC contains a DAG of the call SCCs. To build these, we do1916 // a direct walk of the call edges using Tarjan's algorithm. We reuse the1917 // internal storage as we won't need it for the outer graph's DFS any longer.1918 buildGenericSCCs(1919 Nodes, [](Node &N) { return N->call_begin(); },1920 [](Node &N) { return N->call_end(); },1921 [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },1922 [this, &RC](node_stack_range Nodes) {1923 RC.SCCs.push_back(createSCC(RC, Nodes));1924 for (Node &N : *RC.SCCs.back()) {1925 N.DFSNumber = N.LowLink = -1;1926 SCCMap[&N] = RC.SCCs.back();1927 }1928 });1929 1930 // Wire up the SCC indices.1931 for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)1932 RC.SCCIndices[RC.SCCs[I]] = I;1933}1934 1935void LazyCallGraph::buildRefSCCs() {1936 if (EntryEdges.empty() || !PostOrderRefSCCs.empty())1937 // RefSCCs are either non-existent or already built!1938 return;1939 1940 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");1941 1942 SmallVector<Node *, 16> Roots;1943 for (Edge &E : *this)1944 Roots.push_back(&E.getNode());1945 1946 // The roots will be iterated in order.1947 buildGenericSCCs(1948 Roots,1949 [](Node &N) {1950 // We need to populate each node as we begin to walk its edges.1951 N.populate();1952 return N->begin();1953 },1954 [](Node &N) { return N->end(); },1955 [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },1956 [this](node_stack_range Nodes) {1957 RefSCC *NewRC = createRefSCC(*this);1958 buildSCCs(*NewRC, Nodes);1959 1960 // Push the new node into the postorder list and remember its position1961 // in the index map.1962 bool Inserted =1963 RefSCCIndices.try_emplace(NewRC, PostOrderRefSCCs.size()).second;1964 (void)Inserted;1965 assert(Inserted && "Cannot already have this RefSCC in the index map!");1966 PostOrderRefSCCs.push_back(NewRC);1967#ifdef EXPENSIVE_CHECKS1968 NewRC->verify();1969#endif1970 });1971}1972 1973void LazyCallGraph::visitReferences(SmallVectorImpl<Constant *> &Worklist,1974 SmallPtrSetImpl<Constant *> &Visited,1975 function_ref<void(Function &)> Callback) {1976 while (!Worklist.empty()) {1977 Constant *C = Worklist.pop_back_val();1978 1979 if (Function *F = dyn_cast<Function>(C)) {1980 if (!F->isDeclaration())1981 Callback(*F);1982 continue;1983 }1984 1985 // blockaddresses are weird and don't participate in the call graph anyway,1986 // skip them.1987 if (isa<BlockAddress>(C))1988 continue;1989 1990 for (Value *Op : C->operand_values())1991 if (Visited.insert(cast<Constant>(Op)).second)1992 Worklist.push_back(cast<Constant>(Op));1993 }1994}1995 1996AnalysisKey LazyCallGraphAnalysis::Key;1997 1998LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}1999 2000static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {2001 OS << " Edges in function: " << N.getFunction().getName() << "\n";2002 for (LazyCallGraph::Edge &E : N.populate())2003 OS << " " << (E.isCall() ? "call" : "ref ") << " -> "2004 << E.getFunction().getName() << "\n";2005 2006 OS << "\n";2007}2008 2009static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {2010 OS << " SCC with " << C.size() << " functions:\n";2011 2012 for (LazyCallGraph::Node &N : C)2013 OS << " " << N.getFunction().getName() << "\n";2014}2015 2016static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {2017 OS << " RefSCC with " << C.size() << " call SCCs:\n";2018 2019 for (LazyCallGraph::SCC &InnerC : C)2020 printSCC(OS, InnerC);2021 2022 OS << "\n";2023}2024 2025PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,2026 ModuleAnalysisManager &AM) {2027 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);2028 2029 OS << "Printing the call graph for module: " << M.getModuleIdentifier()2030 << "\n\n";2031 2032 for (Function &F : M)2033 printNode(OS, G.get(F));2034 2035 G.buildRefSCCs();2036 for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())2037 printRefSCC(OS, C);2038 2039 return PreservedAnalyses::all();2040}2041 2042LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)2043 : OS(OS) {}2044 2045static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) {2046 std::string Name =2047 "\"" + DOT::EscapeString(std::string(N.getFunction().getName())) + "\"";2048 2049 for (LazyCallGraph::Edge &E : N.populate()) {2050 OS << " " << Name << " -> \""2051 << DOT::EscapeString(std::string(E.getFunction().getName())) << "\"";2052 if (!E.isCall()) // It is a ref edge.2053 OS << " [style=dashed,label=\"ref\"]";2054 OS << ";\n";2055 }2056 2057 OS << "\n";2058}2059 2060PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,2061 ModuleAnalysisManager &AM) {2062 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);2063 2064 OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";2065 2066 for (Function &F : M)2067 printNodeDOT(OS, G.get(F));2068 2069 OS << "}\n";2070 2071 return PreservedAnalyses::all();2072}2073