[CGSCC][Inliner] Handle new non-trivial edges in updateCGAndAnalysisManagerForPass

[aeubanks]

Summary

Previously the inliner did a bit of a hack by adding ref edges for all
new edges introduced by performing an inline before calling
updateCGAndAnalysisManagerForPass(). This was because
updateCGAndAnalysisManagerForPass() didn't handle new non-trivial call
edges.

This adds handling of non-trivial call edges to
updateCGAndAnalysisManagerForPass(). The inliner called
updateCGAndAnalysisManagerForFunctionPass() since it was handling adding
newly introduced edges (so updateCGAndAnalysisManagerForPass() would
only have to handle promotion), but now it needs to call
updateCGAndAnalysisManagerForCGSCCPass() since
updateCGAndAnalysisManagerForPass() is now handling the new call edges
and function passes cannot add new edges.

We follow the previous path of adding trivial ref edges then letting promotion
handle changing the ref edges to call edges and the CGSCC updates. So
this still does not allow adding call edges that result in an addition
of a non-trivial ref edge.

This is in preparation for better detecting devirtualization. Previously
since the inliner itself would add ref edges,
updateCGAndAnalysisManagerForPass() would think that promotion and thus
devirtualization had happened after any sort of inlining.

[aeubanks]

llvm/lib/Analysis/CGSCCPassManager.cpp

550–551

As a side note, this assert was previously incorrect, it should have checked the two SCCs, not RefSCCs. With this change this is now what we actually want to assert. For example, it didn't catch the added test, instead a later assert triggered on the added test.

[aeubanks]

remove leftover dump

[asbirlea]

This is great, thank you!

[uabelho]

llvm/lib/Transforms/IPO/Inliner.cpp

947

This seems to be the last use of RC ( I see "set but not used" warnings about RC when compiling with gcc 7.4 now). Should RC be removed now?

[aeubanks]

llvm/lib/Transforms/IPO/Inliner.cpp

947

Fixed with b9406121a04eb04069b58815185f6da4ee22b455

llvm/lib/Analysis/CGSCCPassManager.cpp

static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   }
 
   // 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);
+    // Add a trivial ref edge to be promoted later on alongside
+    // PromotedRefTargets.
+    RC->insertTrivialRefEdge(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);
if (C != &TargetC) {
       continue;
     }
 
     // Now update the call graph.
     C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
                                C, AM, UR);
   }
 
+  // We added a ref edge earlier for new call edges, promote those to call edges
+  // alongside PromotedRefTargets.
+  for (Node *E : NewCallEdges)
+    PromotedRefTargets.insert(E);
+
   // 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) {

llvm/lib/Transforms/IPO/Inliner.cpp

for (int I = 0; I < (int)Calls.size(); ++I) {
     // Back the call index up by one to put us in a good position to go around
     // the outer loop.
     --I;
 
     if (!DidInline)
       continue;
     Changed = true;
 
-    // Add all the inlined callees' edges as ref edges to the caller. These are
-    // by definition trivial edges as we always have *some* transitive ref edge
-    // chain. While in some cases these edges are direct calls inside the
-    // callee, they have to be modeled in the inliner as reference edges as
-    // there may be a reference edge anywhere along the chain from the current
-    // caller to the callee that causes the whole thing to appear like
-    // a (transitive) reference edge that will require promotion to a call edge
-    // below.
-    for (Function *InlinedCallee : InlinedCallees) {
-      LazyCallGraph::Node &CalleeN = *CG.lookup(*InlinedCallee);
-      for (LazyCallGraph::Edge &E : *CalleeN)
-        RC->insertTrivialRefEdge(N, E.getNode());
-    }
-
     // At this point, since we have made changes we have at least removed
     // a call instruction. However, in the process we do some incremental
     // simplification of the surrounding code. This simplification can
     // essentially do all of the same things as a function pass and we can
     // re-use the exact same logic for updating the call graph to reflect the
     // change.
 
     // Inside the update, we also update the FunctionAnalysisManager in the
     // proxy for this particular SCC. We do this as the SCC may have changed and
     // as we're going to mutate this particular function we want to make sure
     // the proxy is in place to forward any invalidation events.
     LazyCallGraph::SCC *OldC = C;
-    C = &updateCGAndAnalysisManagerForFunctionPass(CG, *C, N, AM, UR, FAM);
+    C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM);
     LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
     RC = &C->getOuterRefSCC();
 
     // If this causes an SCC to split apart into multiple smaller SCCs, there
     // is a subtle risk we need to prepare for. Other transformations may
     // expose an "infinite inlining" opportunity later, and because of the SCC
     // mutation, we will revisit this function and potentially re-inline. If we
     // do, and that re-inlining also has the potentially to mutate the SCC

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
     }
   }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
+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(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
+                                           CGSCCAnalysisManager &AM,
+                                           LazyCallGraph &CG,
+                                           CGSCCUpdateResult &UR) {
+    if (Ran)
+      return;
+
+    auto &FAM =
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
+    for (auto &N : C) {
+      auto &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());
+
+      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(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+
+  ASSERT_TRUE(Ran);
+}
+
 #endif
 } // namespace