LazyCallGraph.cpp | Explore in Territory

//===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LazyCallGraph.h"

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>

#ifdef EXPENSIVE_CHECKS
#include "llvm/ADT/ScopeExit.h"
#endif

usingnamespacellvm;

#define DEBUG_TYPE …

void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
                                                     Edge::Kind EK) { … }

void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) { … }

bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) { … }

static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
                    DenseMap<LazyCallGraph::Node *, int> &EdgeIndexMap,
                    LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) { … }

LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() { … }

void LazyCallGraph::Node::replaceFunction(Function &NewF) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {
  dbgs() << *this << '\n';
}
#endif

static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) { … }

LazyCallGraph::LazyCallGraph(
    Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) { … }

LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
    : … { … }

#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
void LazyCallGraph::verify() {
  for (RefSCC &RC : postorder_ref_sccs()) {
    RC.verify();
  }
}
#endif

bool LazyCallGraph::invalidate(Module &, const PreservedAnalyses &PA,
                               ModuleAnalysisManager::Invalidator &) { … }

LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
  dbgs() << *this << '\n';
}
#endif

#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
void LazyCallGraph::SCC::verify() {
  assert(OuterRefSCC && "Can't have a null RefSCC!");
  assert(!Nodes.empty() && "Can't have an empty SCC!");

  for (Node *N : Nodes) {
    assert(N && "Can't have a null node!");
    assert(OuterRefSCC->G->lookupSCC(*N) == this &&
           "Node does not map to this SCC!");
    assert(N->DFSNumber == -1 &&
           "Must set DFS numbers to -1 when adding a node to an SCC!");
    assert(N->LowLink == -1 &&
           "Must set low link to -1 when adding a node to an SCC!");
    for (Edge &E : **N)
      assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");

#ifdef EXPENSIVE_CHECKS
    // Verify that all nodes in this SCC can reach all other nodes.
    SmallVector<Node *, 4> Worklist;
    SmallPtrSet<Node *, 4> Visited;
    Worklist.push_back(N);
    while (!Worklist.empty()) {
      Node *VisitingNode = Worklist.pop_back_val();
      if (!Visited.insert(VisitingNode).second)
        continue;
      for (Edge &E : (*VisitingNode)->calls())
        Worklist.push_back(&E.getNode());
    }
    for (Node *NodeToVisit : Nodes) {
      assert(Visited.contains(NodeToVisit) &&
             "Cannot reach all nodes within SCC");
    }
#endif
  }
}
#endif

bool LazyCallGraph::SCC::isParentOf(const SCC &C) const { … }

bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const { … }

LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : … { … }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
  dbgs() << *this << '\n';
}
#endif

#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
void LazyCallGraph::RefSCC::verify() {
  assert(G && "Can't have a null graph!");
  assert(!SCCs.empty() && "Can't have an empty SCC!");

  // Verify basic properties of the SCCs.
  SmallPtrSet<SCC *, 4> SCCSet;
  for (SCC *C : SCCs) {
    assert(C && "Can't have a null SCC!");
    C->verify();
    assert(&C->getOuterRefSCC() == this &&
           "SCC doesn't think it is inside this RefSCC!");
    bool Inserted = SCCSet.insert(C).second;
    assert(Inserted && "Found a duplicate SCC!");
    auto IndexIt = SCCIndices.find(C);
    assert(IndexIt != SCCIndices.end() &&
           "Found an SCC that doesn't have an index!");
  }

  // Check that our indices map correctly.
  for (auto [C, I] : SCCIndices) {
    assert(C && "Can't have a null SCC in the indices!");
    assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
    assert(SCCs[I] == C && "Index doesn't point to SCC!");
  }

  // Check that the SCCs are in fact in post-order.
  for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
    SCC &SourceSCC = *SCCs[I];
    for (Node &N : SourceSCC)
      for (Edge &E : *N) {
        if (!E.isCall())
          continue;
        SCC &TargetSCC = *G->lookupSCC(E.getNode());
        if (&TargetSCC.getOuterRefSCC() == this) {
          assert(SCCIndices.find(&TargetSCC)->second <= I &&
                 "Edge between SCCs violates post-order relationship.");
          continue;
        }
      }
  }

#ifdef EXPENSIVE_CHECKS
  // Verify that all nodes in this RefSCC can reach all other nodes.
  SmallVector<Node *> Nodes;
  for (SCC *C : SCCs) {
    for (Node &N : *C)
      Nodes.push_back(&N);
  }
  for (Node *N : Nodes) {
    SmallVector<Node *, 4> Worklist;
    SmallPtrSet<Node *, 4> Visited;
    Worklist.push_back(N);
    while (!Worklist.empty()) {
      Node *VisitingNode = Worklist.pop_back_val();
      if (!Visited.insert(VisitingNode).second)
        continue;
      for (Edge &E : **VisitingNode)
        Worklist.push_back(&E.getNode());
    }
    for (Node *NodeToVisit : Nodes) {
      assert(Visited.contains(NodeToVisit) &&
             "Cannot reach all nodes within RefSCC");
    }
  }
#endif
}
#endif

bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const { … }

bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const { … }

/// Generic helper that updates a postorder sequence of SCCs for a potentially
/// cycle-introducing edge insertion.
///
/// A postorder sequence of SCCs of a directed graph has one fundamental
/// property: all deges in the DAG of SCCs point "up" the sequence. That is,
/// all edges in the SCC DAG point to prior SCCs in the sequence.
///
/// This routine both updates a postorder sequence and uses that sequence to
/// compute the set of SCCs connected into a cycle. It should only be called to
/// insert a "downward" edge which will require changing the sequence to
/// restore it to a postorder.
///
/// When inserting an edge from an earlier SCC to a later SCC in some postorder
/// sequence, all of the SCCs which may be impacted are in the closed range of
/// those two within the postorder sequence. The algorithm used here to restore
/// the state is as follows:
///
/// 1) Starting from the source SCC, construct a set of SCCs which reach the
///    source SCC consisting of just the source SCC. Then scan toward the
///    target SCC in postorder and for each SCC, if it has an edge to an SCC
///    in the set, add it to the set. Otherwise, the source SCC is not
///    a successor, move it in the postorder sequence to immediately before
///    the source SCC, shifting the source SCC and all SCCs in the set one
///    position toward the target SCC. Stop scanning after processing the
///    target SCC.
/// 2) If the source SCC is now past the target SCC in the postorder sequence,
///    and thus the new edge will flow toward the start, we are done.
/// 3) Otherwise, starting from the target SCC, walk all edges which reach an
///    SCC between the source and the target, and add them to the set of
///    connected SCCs, then recurse through them. Once a complete set of the
///    SCCs the target connects to is known, hoist the remaining SCCs between
///    the source and the target to be above the target. Note that there is no
///    need to process the source SCC, it is already known to connect.
/// 4) At this point, all of the SCCs in the closed range between the source
///    SCC and the target SCC in the postorder sequence are connected,
///    including the target SCC and the source SCC. Inserting the edge from
///    the source SCC to the target SCC will form a cycle out of precisely
///    these SCCs. Thus we can merge all of the SCCs in this closed range into
///    a single SCC.
///
/// This process has various important properties:
/// - Only mutates the SCCs when adding the edge actually changes the SCC
///   structure.
/// - Never mutates SCCs which are unaffected by the change.
/// - Updates the postorder sequence to correctly satisfy the postorder
///   constraint after the edge is inserted.
/// - Only reorders SCCs in the closed postorder sequence from the source to
///   the target, so easy to bound how much has changed even in the ordering.
/// - Big-O is the number of edges in the closed postorder range of SCCs from
///   source to target.
///
/// This helper routine, in addition to updating the postorder sequence itself
/// will also update a map from SCCs to indices within that sequence.
///
/// The sequence and the map must operate on pointers to the SCC type.
///
/// Two callbacks must be provided. The first computes the subset of SCCs in
/// the postorder closed range from the source to the target which connect to
/// the source SCC via some (transitive) set of edges. The second computes the
/// subset of the same range which the target SCC connects to via some
/// (transitive) set of edges. Both callbacks should populate the set argument
/// provided.
template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
          typename ComputeSourceConnectedSetCallableT,
          typename ComputeTargetConnectedSetCallableT>
static iterator_range<typename PostorderSequenceT::iterator>
updatePostorderSequenceForEdgeInsertion(
    SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
    SCCIndexMapT &SCCIndices,
    ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
    ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) { … }

bool LazyCallGraph::RefSCC::switchInternalEdgeToCall(
    Node &SourceN, Node &TargetN,
    function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) { … }

void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
                                                           Node &TargetN) { … }

iterator_range<LazyCallGraph::RefSCC::iterator>
LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) { … }

void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
                                                     Node &TargetN) { … }

void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
                                                    Node &TargetN) { … }

void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
                                                  Node &TargetN) { … }

void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
                                               Edge::Kind EK) { … }

SmallVector<LazyCallGraph::RefSCC *, 1>
LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { … }

void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) { … }

SmallVector<LazyCallGraph::RefSCC *, 1>
LazyCallGraph::RefSCC::removeInternalRefEdges(
    ArrayRef<std::pair<Node *, Node *>> Edges) { … }

void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
                                                  Node &TargetN) { … }

void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) { … }

void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) { … }

void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) { … }

void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) { … }

void LazyCallGraph::markDeadFunction(Function &F) { … }

void LazyCallGraph::removeDeadFunctions(ArrayRef<Function *> DeadFs) { … }

// Gets the Edge::Kind from one function to another by looking at the function's
// instructions. Asserts if there is no edge.
// Useful for determining what type of edge should exist between functions when
// the edge hasn't been created yet.
static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction,
                                             Function &NewFunction) { … }

void LazyCallGraph::addSplitFunction(Function &OriginalFunction,
                                     Function &NewFunction) { … }

void LazyCallGraph::addSplitRefRecursiveFunctions(
    Function &OriginalFunction, ArrayRef<Function *> NewFunctions) { … }

LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { … }

void LazyCallGraph::updateGraphPtrs() { … }

LazyCallGraph::Node &LazyCallGraph::initNode(Function &F) { … }

template <typename RootsT, typename GetBeginT, typename GetEndT,
          typename GetNodeT, typename FormSCCCallbackT>
void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
                                     GetEndT &&GetEnd, GetNodeT &&GetNode,
                                     FormSCCCallbackT &&FormSCC) { … }

/// Build the internal SCCs for a RefSCC from a sequence of nodes.
///
/// Appends the SCCs to the provided vector and updates the map with their
/// indices. Both the vector and map must be empty when passed into this
/// routine.
void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) { … }

void LazyCallGraph::buildRefSCCs() { … }

void LazyCallGraph::visitReferences(SmallVectorImpl<Constant *> &Worklist,
                                    SmallPtrSetImpl<Constant *> &Visited,
                                    function_ref<void(Function &)> Callback) { … }

AnalysisKey LazyCallGraphAnalysis::Key;

LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : … { … }

static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) { … }

static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) { … }

static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) { … }

PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
                                                ModuleAnalysisManager &AM) { … }

LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
    : … { … }

static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) { … }

PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,
                                                   ModuleAnalysisManager &AM) { … }
llvm/llvm/lib/Analysis/LazyCallGraph.cpp
