[PM][CGSCC] Add a helper to update the call graph from SCC passes

[jdoerfert]

Summary

With this patch new trivial edges can be added to an SCC in a CGSCC
pass via the updateCGAndAnalysisManagerForCGSCCPass method. It shares
almost all the code with the existing
updateCGAndAnalysisManagerForFunctionPass method but it implements the
first step towards the TODOs.

This was initially part of D70927.

[merge_guards_bot]

Unit tests: pass. 61159 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[modocache]

My patch D71899 makes use of the API introduced in this patch (it's adds an outlining CGSCC pass to the new pass manager pipeline), and it works great! Thanks for this.

I'm not an expert in this area, so maybe @chandlerc should review this before this is committed. I had mostly nit-picks.

Also, one suggestion: the unit tests for this patch are great! As far as I can tell, they all test adding call edges. Could you add some for adding ref edges? I think that would improve the test coverage here, but also my patch D71899 relies on being able to add ref edges, so I want to make sure that doesn't break :)

llvm/include/llvm/Analysis/CGSCCPassManager.h

421

nit: git grep "CG-SCC" only turns up matches from this patch and D70927. I think "CGSCC" is the canonical abbreviation.

llvm/lib/Analysis/CGSCCPassManager.cpp

635

Small nitpick: This should be "new ref edge is not trivial", I think. The variable names, such as Node *CallTarget, could also be updated to refer to ref edges, not call edges.

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

1307

At first I wasn't sure why these tests were guarded by this, but as I read below I could see that they're primarily testing that updateCGAndAnalysisManagerFor{Function,CGSCC}Pass does not trigger an assert (and those would only fire if NDEBUG wasn't defined). I'm relatively new to this project so maybe it's just me, or maybe a comment here might be helpful.

1387

I think this sentence is missing its ending. Basically TestUpdateCGAndAnalysisManagerForPasses0 is testing that CGSCC passes can insert new edges, and TestUpdateCGAndAnalysisManagerForPasses1 is testing that function passes cannot -- is that right?

1444

Same as above, this sentence trails off. Tests TestUpdateCGAndAnalysisManagerForPasses2 and TestUpdateCGAndAnalysisManagerForPasses3 are testing inserting call edges across SCCs, is that right?

[jdoerfert]

First add new edges before the SCC might get split up

[jdoerfert]

Addressed comments

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

1387

Yes, correct. The sentence is not an assertion but a regular expression that checks for the assertion.

1444

The first tests add edges inside the SCC, the second inside the RefSCC but from an outer SCC to an inner one. Both are trivial so we should be all right adding them and then calling updateCGAndAnalysisManagerForCGSCCPass.

[merge_guards_bot]

Unit tests: pass. 61185 tests passed, 0 failed and 729 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[merge_guards_bot]

Unit tests: pass. 61185 tests passed, 0 failed and 729 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[modocache]

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

1387

Aha! Thanks, I didn't know that.

[modocache]

llvm/lib/Analysis/CGSCCPassManager.cpp

498

You'll need to add a (void)TargetRC; statement or something here and on similar lines. In release builds, I'm seeing the following warnings:

llvm/lib/Analysis/CGSCCPassManager.cpp:498:13: warning: unused variable 'TargetRC' [-Wunused-variable]
    RefSCC &TargetRC = TargetC.getOuterRefSCC();
            ^
llvm/lib/Analysis/CGSCCPassManager.cpp:508:13: warning: unused variable 'TargetRC' [-Wunused-variable]
    RefSCC &TargetRC = TargetC.getOuterRefSCC();
            ^

[jdoerfert]

llvm/lib/Analysis/CGSCCPassManager.cpp

498

Will do, thanks. (I add WITH_ASSERTS to my release build so I don't see these warnings).

[jdoerfert]

Addressed comment

[merge_guards_bot]

Unit tests: pass. 62376 tests passed, 0 failed and 839 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[JonChesterfield]

Change looks great to me. Straightforward, removes FIXME notes, has associated tests, already picked up a dependency. Thanks!

llvm/include/llvm/Analysis/CGSCCPassManager.h

 /// Function passes can only mutate the call graph in specific ways. This
 /// routine provides a helper that updates the call graph in those ways
 /// including returning whether any changes were made and populating a CG
 /// update result struct for the overall CGSCC walk.
 LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
     LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
 
+/// Helper to update the call graph after running a CGSCC pass.
+///
+/// CGSCC passes can only mutate the call graph in specific ways. This
+/// routine provides a helper that updates the call graph in those ways
+/// including returning whether any changes were made and populating a CG
+/// update result struct for the overall CGSCC walk.
+LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR);
+
 /// Adaptor that maps from a SCC to its functions.
 ///
 /// Designed to allow composition of a FunctionPass(Manager) and
 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 /// to a \c CGSCCAnalysisManager it will run the
 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.

llvm/lib/Analysis/CGSCCPassManager.cpp

for (SCC &NewC : llvm::reverse(make_range(std::next(NewSCCRange.begin()),
 
     // Also propagate a normal invalidation to the new SCC as only the current
     // will get one from the pass manager infrastructure.
     AM.invalidate(NewC, PA);
   }
   return C;
 }
 
-LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
+static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
-    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool FunctionPass) {
   using Node = LazyCallGraph::Node;
   using Edge = LazyCallGraph::Edge;
   using SCC = LazyCallGraph::SCC;
   using RefSCC = LazyCallGraph::RefSCC;
 
   RefSCC &InitialRC = InitialC.getOuterRefSCC();
   SCC *C = &InitialC;
   RefSCC *RC = &InitialRC;
   Function &F = N.getFunction();
 
   // Walk the function body and build up the set of retained, promoted, and
   // demoted edges.
   SmallVector<Constant *, 16> Worklist;
   SmallPtrSet<Constant *, 16> Visited;
   SmallPtrSet<Node *, 16> RetainedEdges;
   SmallSetVector<Node *, 4> PromotedRefTargets;
   SmallSetVector<Node *, 4> DemotedCallTargets;
+  SmallSetVector<Node *, 4> NewCallEdges;
+  SmallSetVector<Node *, 4> NewRefEdges;
 
   // First walk the function and handle all called functions. We do this first
   // because if there is a single call edge, whether there are ref edges is
   // irrelevant.
   for (Instruction &I : instructions(F))
     if (auto CS = CallSite(&I))
       if (Function *Callee = CS.getCalledFunction())
         if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
           Node &CalleeN = *G.lookup(*Callee);
           Edge *E = N->lookup(CalleeN);
-          // FIXME: We should really handle adding new calls. While it will
-          // make downstream usage more complex, there is no fundamental
-          // limitation and it will allow passes within the CGSCC to be a bit
-          // more flexible in what transforms they can do. Until then, we
-          // verify that new calls haven't been introduced.
-          assert(E && "No function transformations should introduce *new* "
-                      "call edges! Any new calls should be modeled as "
-                      "promoted existing ref edges!");
+          assert((E || !FunctionPass) &&
+                 "No function transformations should introduce *new* "
           bool Inserted = RetainedEdges.insert(&CalleeN).second;
           (void)Inserted;
           assert(Inserted && "We should never visit a function twice.");
-          if (!E->isCall())
+          if (!E)
+            NewCallEdges.insert(&CalleeN);
+          else if (!E->isCall())
             PromotedRefTargets.insert(&CalleeN);
         }
 
   // Now walk all references.
   for (Instruction &I : instructions(F))
     for (Value *Op : I.operand_values())
       if (auto *C = dyn_cast<Constant>(Op))
         if (Visited.insert(C).second)
           Worklist.push_back(C);
 
   auto VisitRef = [&](Function &Referee) {
     Node &RefereeN = *G.lookup(Referee);
     Edge *E = N->lookup(RefereeN);
-    // FIXME: Similarly to new calls, we also currently preclude
-    // introducing new references. See above for details.
-    assert(E && "No function transformations should introduce *new* ref "
-                "edges! Any new ref edges would require IPO which "
-                "function passes aren't allowed to do!");
+    assert((E || !FunctionPass) &&
+           "No function transformations should introduce *new* ref "
     bool Inserted = RetainedEdges.insert(&RefereeN).second;
     (void)Inserted;
     assert(Inserted && "We should never visit a function twice.");
-    if (E->isCall())
+    if (!E)
+      NewRefEdges.insert(&RefereeN);
+    else if (E->isCall())
       DemotedCallTargets.insert(&RefereeN);
   };
   LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
 
+  // Handle new ref edges.
+  for (Node *RefTarget : NewRefEdges) {
+    SCC &TargetC = *G.lookupSCC(*RefTarget);
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+    (void)TargetRC;
+    // TODO: This only allows trivial edges to be added for now.
+    assert(RC == &TargetRC ||
+           RC->isAncestorOf(TargetRC) && "New ref edge is not trivial!");
+    RC->insertTrivialRefEdge(N, *RefTarget);
+  }
+
+  // Handle new call edges.
+  for (Node *CallTarget : NewCallEdges) {
+    SCC &TargetC = *G.lookupSCC(*CallTarget);
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+    (void)TargetRC;
+    // TODO: This only allows trivial edges to be added for now.
+    assert(RC == &TargetRC ||
+           RC->isAncestorOf(TargetRC) && "New call edge is not trivial!");
+    RC->insertTrivialCallEdge(N, *CallTarget);
+  }
+
   // Include synthetic reference edges to known, defined lib functions.
   for (auto *F : G.getLibFunctions())
     // While the list of lib functions doesn't have repeats, don't re-visit
     // anything handled above.
     if (!Visited.count(F))
       VisitRef(*F);
 
   // First remove all of the edges that are no longer present in this function.
static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   }
 
   // Now promote ref edges into call edges.
   for (Node *CallTarget : PromotedRefTargets) {
     SCC &TargetC = *G.lookupSCC(*CallTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
 
     // The easy case is when the target RefSCC is not this RefSCC. This is
     // only supported when the target RefSCC is a child of this RefSCC.
     if (&TargetRC != RC) {
       assert(RC->isAncestorOf(TargetRC) &&
              "Cannot potentially form RefSCC cycles here!");
       RC->switchOutgoingEdgeToCall(N, *CallTarget);
       LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
                         << "' to '" << *CallTarget << "'\n");
       continue;
     }
static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   // manager now that all the updates have been applied.
   if (RC != &InitialRC)
     UR.UpdatedRC = RC;
   if (C != &InitialC)
     UR.UpdatedC = C;
 
   return *C;
 }
+
+LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
+  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR,
+                                           /* FunctionPass */ true);
+}
+LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
+  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR,
+                                           /* FunctionPass */ false);
+}

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) {
 
   // Re run the function analysis over the entire module, and then re-run it
   // over the `(h3, h1, h2)` SCC due to invalidation. Then we re-run it over
   // the entire module, then the three functions merged back into a single SCC,
   // those three functions again, then the two functions in SCCs above it in
   // the graph, and then over the whole module.
   EXPECT_EQ(6 + 3 + 6 + 3 + 3 + 2 + 6, IndirectFunctionAnalysisRuns);
 }
+
+// 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);
+    return PreservedAnalyses::none();
+  }
+
+  std::function<void(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
+                     LazyCallGraph &, CGSCCUpdateResult &)>
+      Func;
+};
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses0) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  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`.
+        Instruction *IP = &FnH2->getEntryBlock().front();
+        (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));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses1) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  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`.
+    Instruction *IP = &FnH2->getEntryBlock().front();
+    (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),
+                 "Any new calls should be modeled as");
+  }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
 }
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses2) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  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`
+        Instruction *IP = &FnF->getEntryBlock().front();
+        (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));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses3) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  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`
+    Instruction *IP = &FnF->getEntryBlock().front();
+    (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),
+                 "Any new calls should be modeled as");
+  }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+#endif
+} // namespace