llvm/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

//===- CGSCCPassManagerTest.cpp -------------------------------------------===//
//
// 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/CGSCCPassManager.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PassInstrumentation.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/Transforms/Utils/CallGraphUpdater.h"
#include "gtest/gtest.h"

usingnamespacellvm;

namespace {

class TestModuleAnalysis : public AnalysisInfoMixin<TestModuleAnalysis> { … };

AnalysisKey TestModuleAnalysis::Key;

class TestSCCAnalysis : public AnalysisInfoMixin<TestSCCAnalysis> { … };

AnalysisKey TestSCCAnalysis::Key;

class TestFunctionAnalysis : public AnalysisInfoMixin<TestFunctionAnalysis> { … };

AnalysisKey TestFunctionAnalysis::Key;

class TestImmutableFunctionAnalysis
    : public AnalysisInfoMixin<TestImmutableFunctionAnalysis> { … };

AnalysisKey TestImmutableFunctionAnalysis::Key;

struct LambdaModulePass : public PassInfoMixin<LambdaModulePass> { … };

struct LambdaSCCPass : public PassInfoMixin<LambdaSCCPass> { … };

struct LambdaFunctionPass : public PassInfoMixin<LambdaFunctionPass> { … };

std::unique_ptr<Module> parseIR(const char *IR) { … }

class CGSCCPassManagerTest : public ::testing::Test { … };

TEST_F(CGSCCPassManagerTest, Basic) { … }

// Test that an SCC pass which fails to preserve a module analysis does in fact
// invalidate that module analysis.
TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesModuleAnalysis) { … }

// Similar to the above, but test that this works for function passes embedded
// *within* a CGSCC layer.
TEST_F(CGSCCPassManagerTest, TestFunctionPassInsideCGSCCInvalidatesModuleAnalysis) { … }

// Test that a Module pass which fails to preserve an SCC analysis in fact
// invalidates that analysis.
TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysis) { … }

// Check that marking the SCC analysis preserved is sufficient to avoid
// invaliadtion. This should only run the analysis once for each SCC.
TEST_F(CGSCCPassManagerTest, TestModulePassCanPreserveSCCAnalysis) { … }

// Check that even when the analysis is preserved, if the SCC information isn't
// we still nuke things because the SCC keys could change.
TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysisOnCGChange) { … }

// Test that an SCC pass which fails to preserve a Function analysis in fact
// invalidates that analysis.
TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesFunctionAnalysis) { … }

// Check that marking the SCC analysis preserved is sufficient. This should
// only run the analysis once the SCC.
TEST_F(CGSCCPassManagerTest, TestSCCPassCanPreserveFunctionAnalysis) { … }

// Note that there is no test for invalidating the call graph or other
// structure with an SCC pass because there is no mechanism to do that from
// withinsuch a pass. Instead, such a pass has to directly update the call
// graph structure.

// Test that a madule pass invalidates function analyses when the CGSCC proxies
// and pass manager.
TEST_F(CGSCCPassManagerTest,
       TestModulePassInvalidatesFunctionAnalysisNestedInCGSCC) { … }

// Check that by marking the function pass and proxies as preserved, this
// propagates all the way through.
TEST_F(CGSCCPassManagerTest,
       TestModulePassCanPreserveFunctionAnalysisNestedInCGSCC) { … }

// Check that if the lazy call graph itself isn't preserved we still manage to
// invalidate everything.
TEST_F(CGSCCPassManagerTest,
       TestModulePassInvalidatesFunctionAnalysisNestedInCGSCCOnCGChange) { … }

/// A test CGSCC-level analysis pass which caches in its result another
/// analysis pass and uses it to serve queries. This requires the result to
/// invalidate itself when its dependency is invalidated.
///
/// FIXME: Currently this doesn't also depend on a function analysis, and if it
/// did we would fail to invalidate it correctly.
struct TestIndirectSCCAnalysis
    : public AnalysisInfoMixin<TestIndirectSCCAnalysis> { … };

AnalysisKey TestIndirectSCCAnalysis::Key;

/// A test analysis pass which caches in its result the result from the above
/// indirect analysis pass.
///
/// This allows us to ensure that whenever an analysis pass is invalidated due
/// to dependencies (especially dependencies across IR units that trigger
/// asynchronous invalidation) we correctly detect that this may in turn cause
/// other analysis to be invalidated.
struct TestDoublyIndirectSCCAnalysis
    : public AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis> { … };

AnalysisKey TestDoublyIndirectSCCAnalysis::Key;

/// A test analysis pass which caches results from three different IR unit
/// layers and requires intermediate layers to correctly propagate the entire
/// distance.
struct TestIndirectFunctionAnalysis
    : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> { … };

AnalysisKey TestIndirectFunctionAnalysis::Key;

TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) { … }

TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) { … }

// The (negative) tests below check for assertions so we only run them if NDEBUG
// is not defined.
#ifndef NDEBUG

struct LambdaSCCPassNoPreserve : public PassInfoMixin<LambdaSCCPassNoPreserve> {
  template <typename T>
  LambdaSCCPassNoPreserve(T &&Arg) : Func(std::forward<T>(Arg)) {}

  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
    Func(C, AM, CG, UR);
    PreservedAnalyses PA;
    // We update the core CGSCC data structures and so can preserve the proxy to
    // the function analysis manager.
    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
    return PA;
  }

  std::function<void(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
                     LazyCallGraph &, CGSCCUpdateResult &)>
      Func;
};

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses0) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(h3, h1, h2)")
          return;

        auto &FAM =
            AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
        Function *FnX = M->getFunction("x");
        Function *FnH1 = M->getFunction("h1");
        Function *FnH2 = M->getFunction("h2");
        Function *FnH3 = M->getFunction("h3");
        ASSERT_NE(FnX, nullptr);
        ASSERT_NE(FnH1, nullptr);
        ASSERT_NE(FnH2, nullptr);
        ASSERT_NE(FnH3, nullptr);

        // And insert a call to `h1`, `h2`, and `h3`.
        BasicBlock::iterator IP = FnH2->getEntryBlock().begin();
        (void)CallInst::Create(FnH1, {}, "", IP);
        (void)CallInst::Create(FnH2, {}, "", IP);
        (void)CallInst::Create(FnH3, {}, "", IP);

        auto &H2N = *llvm::find_if(
            C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
        ASSERT_NO_FATAL_FAILURE(
            updateCGAndAnalysisManagerForCGSCCPass(CG, C, H2N, AM, UR, FAM));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses1) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) {
    if (C.getName() != "(h3, h1, h2)")
      return;

    auto &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
    Function *FnX = M->getFunction("x");
    Function *FnH1 = M->getFunction("h1");
    Function *FnH2 = M->getFunction("h2");
    Function *FnH3 = M->getFunction("h3");
    ASSERT_NE(FnX, nullptr);
    ASSERT_NE(FnH1, nullptr);
    ASSERT_NE(FnH2, nullptr);
    ASSERT_NE(FnH3, nullptr);

    // And insert a call to `h1`, `h2`, and `h3`.
    BasicBlock::iterator IP = FnH2->getEntryBlock().begin();
    (void)CallInst::Create(FnH1, {}, "", IP);
    (void)CallInst::Create(FnH2, {}, "", IP);
    (void)CallInst::Create(FnH3, {}, "", IP);

    auto &H2N = *llvm::find_if(
        C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
    ASSERT_DEATH(
        updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR, FAM),
        "Any new calls should be modeled as");
  }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses2) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(f)")
          return;

        auto &FAM =
            AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
        Function *FnF = M->getFunction("f");
        Function *FnH2 = M->getFunction("h2");
        ASSERT_NE(FnF, nullptr);
        ASSERT_NE(FnH2, nullptr);

        // And insert a call to `h2`
        BasicBlock::iterator IP = FnF->getEntryBlock().begin();
        (void)CallInst::Create(FnH2, {}, "", IP);

        auto &FN = *llvm::find_if(
            C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
        ASSERT_NO_FATAL_FAILURE(
            updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses3) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) {
    if (C.getName() != "(f)")
      return;

    auto &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
    Function *FnF = M->getFunction("f");
    Function *FnH2 = M->getFunction("h2");
    ASSERT_NE(FnF, nullptr);
    ASSERT_NE(FnH2, nullptr);

    // And insert a call to `h2`
    BasicBlock::iterator IP = FnF->getEntryBlock().begin();
    (void)CallInst::Create(FnH2, {}, "", IP);

    auto &FN = *llvm::find_if(
        C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
    ASSERT_DEATH(
        updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR, FAM),
        "Any new calls should be modeled as");
  }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses4) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(f)")
          return;

        auto &FAM =
            AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
        Function *FnF = M->getFunction("f");
        Function *FnewF = Function::Create(FnF->getFunctionType(),
                                           FnF->getLinkage(), "newF", *M);
        BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
        ReturnInst::Create(FnewF->getContext(), BB);

        // And insert a call to `newF`
        BasicBlock::iterator IP = FnF->getEntryBlock().begin();
        (void)CallInst::Create(FnewF, {}, "", IP);

        // Use the CallGraphUpdater to update the call graph for the new
        // function.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        CGU.registerOutlinedFunction(*FnF, *FnewF);

        auto &FN = *llvm::find_if(
            C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });

        ASSERT_NO_FATAL_FAILURE(
            updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses5) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) {
    if (C.getName() != "(f)")
      return;

    auto &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
    Function *FnF = M->getFunction("f");
    Function *FnewF =
        Function::Create(FnF->getFunctionType(), FnF->getLinkage(), "newF", *M);
    BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
    ReturnInst::Create(FnewF->getContext(), BB);

    // Use the CallGraphUpdater to update the call graph for the new
    // function.
    CallGraphUpdater CGU;
    CGU.initialize(CG, C, AM, UR);

    // And insert a call to `newF`
    BasicBlock::iterator IP = FnF->getEntryBlock().begin();
    (void)CallInst::Create(FnewF, {}, "", IP);

    auto &FN = *llvm::find_if(
        C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });

    ASSERT_DEATH(updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM),
                 "should already have an associated node");
  }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses6) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(h3, h1, h2)")
          return;

        Function *FnX = M->getFunction("x");
        Function *FnH1 = M->getFunction("h1");
        Function *FnH2 = M->getFunction("h2");
        Function *FnH3 = M->getFunction("h3");
        ASSERT_NE(FnX, nullptr);
        ASSERT_NE(FnH1, nullptr);
        ASSERT_NE(FnH2, nullptr);
        ASSERT_NE(FnH3, nullptr);

        // And insert a call to `h1`, `h2`, and `h3`.
        BasicBlock::iterator IP = FnH2->getEntryBlock().begin();
        (void)CallInst::Create(FnH1, {}, "", IP);
        (void)CallInst::Create(FnH2, {}, "", IP);
        (void)CallInst::Create(FnH3, {}, "", IP);

        // Use the CallGraphUpdater to update the call graph for the new
        // function.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH2));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses7) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(f)")
          return;

        Function *FnF = M->getFunction("f");
        Function *FnH2 = M->getFunction("h2");
        ASSERT_NE(FnF, nullptr);
        ASSERT_NE(FnH2, nullptr);

        // And insert a call to `h2`
        BasicBlock::iterator IP = FnF->getEntryBlock().begin();
        (void)CallInst::Create(FnH2, {}, "", IP);

        // Use the CallGraphUpdater to update the call graph for the new
        // function.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnF));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses8) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(f)")
          return;

        Function *FnF = M->getFunction("f");
        Function *FnewF = Function::Create(FnF->getFunctionType(),
                                           FnF->getLinkage(), "newF", *M);
        BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
        auto *RI = ReturnInst::Create(FnewF->getContext(), BB);
        while (FnF->getEntryBlock().size() > 1)
          FnF->getEntryBlock().front().moveBefore(RI);
        ASSERT_NE(FnF, nullptr);

        // Create an unused constant that is referencing the old (=replaced)
        // function.
        ConstantExpr::getPtrToInt(FnF, Type::getInt64Ty(FnF->getContext()));

        // Use the CallGraphUpdater to update the call graph.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        ASSERT_NO_FATAL_FAILURE(CGU.replaceFunctionWith(*FnF, *FnewF));
        ASSERT_TRUE(FnF->isDeclaration());
        ASSERT_EQ(FnF->getNumUses(), 0U);
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses9) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(f)")
          return;

        Function *FnF = M->getFunction("f");

        // Use the CallGraphUpdater to update the call graph.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnF));
        ASSERT_EQ(M->getFunctionList().size(), 6U);
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
  ASSERT_EQ(M->getFunctionList().size(), 5U);
}

TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses10) {
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (C.getName() != "(h3, h1, h2)")
          return;

        Function *FnX = M->getFunction("x");
        Function *FnH1 = M->getFunction("h1");
        Function *FnH2 = M->getFunction("h2");
        Function *FnH3 = M->getFunction("h3");
        ASSERT_NE(FnX, nullptr);
        ASSERT_NE(FnH1, nullptr);
        ASSERT_NE(FnH2, nullptr);
        ASSERT_NE(FnH3, nullptr);

        // And insert a call to `h1`, and `h3`.
        BasicBlock::iterator IP = FnH1->getEntryBlock().begin();
        (void)CallInst::Create(FnH1, {}, "", IP);
        (void)CallInst::Create(FnH3, {}, "", IP);

        // Remove the `h2` call.
        ASSERT_TRUE(isa<CallBase>(IP));
        ASSERT_EQ(cast<CallBase>(IP)->getCalledFunction(), FnH2);
        IP->eraseFromParent();

        // Use the CallGraphUpdater to update the call graph.
        CallGraphUpdater CGU;
        CGU.initialize(CG, C, AM, UR);
        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH1));
        ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnH2));
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
}

// Returns a vector containing the SCC's nodes. Useful for not iterating over an
// SCC while mutating it.
static SmallVector<LazyCallGraph::Node *> SCCNodes(LazyCallGraph::SCC &C) {
  SmallVector<LazyCallGraph::Node *> Nodes;
  for (auto &N : C)
    Nodes.push_back(&N);

  return Nodes;
}

// Start with call recursive f, create f -> g and ref recursive f.
TEST_F(CGSCCPassManagerTest, TestInsertionOfNewFunctions1) {
  std::unique_ptr<Module> M = parseIR("define void @f() {\n"
                                      "entry:\n"
                                      "  call void @f()\n"
                                      "  ret void\n"
                                      "}\n");

  bool Ran = false;

  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (Ran)
          return;

        auto &FAM =
            AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();

        for (LazyCallGraph::Node *N : SCCNodes(C)) {
          Function &F = N->getFunction();
          if (F.getName() != "f")
            continue;

          // Create a new function 'g'.
          auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
                                     F.getAddressSpace(), "g", F.getParent());
          auto *GBB =
              BasicBlock::Create(F.getParent()->getContext(), "entry", G);
          (void)ReturnInst::Create(G->getContext(), GBB);
          // Instruct the LazyCallGraph to create a new node for 'g', as the
          // single node in a new SCC, into the call graph. As a result
          // the call graph is composed of a single RefSCC with two SCCs:
          // [(f), (g)].

          // "Demote" the 'f -> f' call edge to a ref edge.
          // 1. Erase the call edge from 'f' to 'f'.
          F.getEntryBlock().front().eraseFromParent();
          // 2. Insert a ref edge from 'f' to 'f'.
          (void)CastInst::CreatePointerCast(
              &F, PointerType::getUnqual(F.getContext()), "f.ref",
              F.getEntryBlock().begin());
          // 3. Insert a ref edge from 'f' to 'g'.
          (void)CastInst::CreatePointerCast(
              G, PointerType::getUnqual(F.getContext()), "g.ref",
              F.getEntryBlock().begin());

          CG.addSplitFunction(F, *G);

          ASSERT_FALSE(verifyModule(*F.getParent(), &errs()));

          ASSERT_NO_FATAL_FAILURE(
              updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
              << "Updating the call graph with a demoted, self-referential "
                 "call edge 'f -> f', and a newly inserted ref edge 'f -> g', "
                 "caused a fatal failure";

          Ran = true;
        }
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
  ASSERT_TRUE(Ran);
}

// Start with f, end with f -> g1, f -> g2, and f -ref-> (h1 <-ref-> h2).
TEST_F(CGSCCPassManagerTest, TestInsertionOfNewFunctions2) {
  std::unique_ptr<Module> M = parseIR("define void @f() {\n"
                                      "entry:\n"
                                      "  ret void\n"
                                      "}\n");

  bool Ran = false;

  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) {
    if (Ran)
      return;

    auto &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();

    for (LazyCallGraph::Node *N : SCCNodes(C)) {
      Function &F = N->getFunction();
      if (F.getName() != "f")
        continue;

      // Create g1 and g2.
      auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
                                  F.getAddressSpace(), "g1", F.getParent());
      auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
                                  F.getAddressSpace(), "g2", F.getParent());
      BasicBlock *G1BB =
          BasicBlock::Create(F.getParent()->getContext(), "entry", G1);
      BasicBlock *G2BB =
          BasicBlock::Create(F.getParent()->getContext(), "entry", G2);
      (void)ReturnInst::Create(G1->getContext(), G1BB);
      (void)ReturnInst::Create(G2->getContext(), G2BB);

      // Add 'f -> g1' call edge.
      (void)CallInst::Create(G1, {}, "", F.getEntryBlock().begin());
      // Add 'f -> g2' call edge.
      (void)CallInst::Create(G2, {}, "", F.getEntryBlock().begin());

      CG.addSplitFunction(F, *G1);
      CG.addSplitFunction(F, *G2);

      // Create mutually recursive functions (ref only) 'h1' and 'h2'.
      auto *H1 = Function::Create(F.getFunctionType(), F.getLinkage(),
                                  F.getAddressSpace(), "h1", F.getParent());
      auto *H2 = Function::Create(F.getFunctionType(), F.getLinkage(),
                                  F.getAddressSpace(), "h2", F.getParent());
      BasicBlock *H1BB =
          BasicBlock::Create(F.getParent()->getContext(), "entry", H1);
      BasicBlock *H2BB =
          BasicBlock::Create(F.getParent()->getContext(), "entry", H2);
      (void)CastInst::CreatePointerCast(
          H2, PointerType::getUnqual(F.getContext()), "h2.ref", H1BB);
      (void)ReturnInst::Create(H1->getContext(), H1BB);
      (void)CastInst::CreatePointerCast(
          H1, PointerType::getUnqual(F.getContext()), "h1.ref", H2BB);
      (void)ReturnInst::Create(H2->getContext(), H2BB);

      // Add 'f -> h1' ref edge.
      (void)CastInst::CreatePointerCast(H1,
                                        PointerType::getUnqual(F.getContext()),
                                        "h1.ref", F.getEntryBlock().begin());
      // Add 'f -> h2' ref edge.
      (void)CastInst::CreatePointerCast(H2,
                                        PointerType::getUnqual(F.getContext()),
                                        "h2.ref", F.getEntryBlock().begin());

      CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 2>({H1, H2}));

      ASSERT_FALSE(verifyModule(*F.getParent(), &errs()));

      ASSERT_NO_FATAL_FAILURE(
          updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
          << "Updating the call graph with mutually recursive g1 <-> g2, h1 "
             "<-> h2 caused a fatal failure";

      Ran = true;
    }
  }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
  ASSERT_TRUE(Ran);
}

TEST_F(CGSCCPassManagerTest, TestDeletionOfFunctionInNonTrivialRefSCC) {
  std::unique_ptr<Module> M = parseIR("define void @f1() {\n"
                                      "entry:\n"
                                      "  call void @f2()\n"
                                      "  ret void\n"
                                      "}\n"
                                      "define void @f2() {\n"
                                      "entry:\n"
                                      "  call void @f1()\n"
                                      "  ret void\n"
                                      "}\n");

  bool Ran = false;
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve(
      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
          CGSCCUpdateResult &UR) {
        if (Ran)
          return;

        LazyCallGraph::Node *N1 = nullptr;

        for (LazyCallGraph::Node *N : SCCNodes(C)) {
          Function &F = N->getFunction();
          if (F.getName() != "f1")
            continue;
          N1 = N;

          Function &F2 = *F.getParent()->getFunction("f2");

          // Remove f1 <-> f2 references
          F.getEntryBlock().front().eraseFromParent();
          F2.getEntryBlock().front().eraseFromParent();

          CallGraphUpdater CGU;
          CGU.initialize(CG, C, AM, UR);
          CGU.removeFunction(F2);
          CGU.reanalyzeFunction(F);

          Ran = true;
        }

        // Check that updateCGAndAnalysisManagerForCGSCCPass() after
        // CallGraphUpdater::removeFunction() succeeds.
        updateCGAndAnalysisManagerForCGSCCPass(CG, *CG.lookupSCC(*N1), *N1, AM,
                                               UR, FAM);
      }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);

  ASSERT_TRUE(Ran);
}

TEST_F(CGSCCPassManagerTest, TestInsertionOfNewNonTrivialCallEdge) {
  std::unique_ptr<Module> M = parseIR("define void @f1() {\n"
                                      "entry:\n"
                                      "  %a = bitcast void ()* @f4 to i8*\n"
                                      "  %b = bitcast void ()* @f2 to i8*\n"
                                      "  ret void\n"
                                      "}\n"
                                      "define void @f2() {\n"
                                      "entry:\n"
                                      "  %a = bitcast void ()* @f1 to i8*\n"
                                      "  %b = bitcast void ()* @f3 to i8*\n"
                                      "  ret void\n"
                                      "}\n"
                                      "define void @f3() {\n"
                                      "entry:\n"
                                      "  %a = bitcast void ()* @f2 to i8*\n"
                                      "  %b = bitcast void ()* @f4 to i8*\n"
                                      "  ret void\n"
                                      "}\n"
                                      "define void @f4() {\n"
                                      "entry:\n"
                                      "  %a = bitcast void ()* @f3 to i8*\n"
                                      "  %b = bitcast void ()* @f1 to i8*\n"
                                      "  ret void\n"
                                      "}\n");

  bool Ran = false;
  CGSCCPassManager CGPM;
  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
                                           CGSCCAnalysisManager &AM,
                                           LazyCallGraph &CG,
                                           CGSCCUpdateResult &UR) {
    if (Ran)
      return;

    auto &FAM =
        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();

    for (LazyCallGraph::Node *N : SCCNodes(C)) {
      Function &F = N->getFunction();
      if (F.getName() != "f1")
        continue;

      Function *F3 = F.getParent()->getFunction("f3");
      ASSERT_TRUE(F3 != nullptr);

      // Create call from f1 to f3.
      (void)CallInst::Create(F3, {}, "",
                             F.getEntryBlock().getTerminator()->getIterator());

      ASSERT_NO_FATAL_FAILURE(
          updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
          << "Updating the call graph with mutually recursive g1 <-> g2, h1 "
             "<-> h2 caused a fatal failure";

      Ran = true;
    }
  }));

  ModulePassManager MPM;
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);

  ASSERT_TRUE(Ran);
}

TEST_F(CGSCCPassManagerTest, TestFunctionPassesAreQueriedForInvalidation) {
  std::unique_ptr<Module> M = parseIR("define void @f() { ret void }");
  CGSCCPassManager CGPM;
  bool SCCCalled = false;
  FunctionPassManager FPM;
  int ImmRuns = 0;
  FAM.registerPass([&] { return TestImmutableFunctionAnalysis(ImmRuns); });
  FPM.addPass(RequireAnalysisPass<TestImmutableFunctionAnalysis, Function>());
  CGPM.addPass(
      LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
        SCCCalled = true;
        return PreservedAnalyses::none();
      }));
  CGPM.addPass(createCGSCCToFunctionPassAdaptor(
      RequireAnalysisPass<TestImmutableFunctionAnalysis, Function>()));
  ModulePassManager MPM;

  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
  MPM.run(*M, MAM);
  ASSERT_EQ(ImmRuns, 1);
  ASSERT_TRUE(SCCCalled);
}

#endif
} // namespace