From d9cbceb041fda981e5bb14f4cbea712302fc9cdb Mon Sep 17 00:00:00 2001 From: Arthur Eubanks Date: Fri, 6 Nov 2020 18:32:46 -0800 Subject: [PATCH] [CGSCC][Inliner] Handle new non-trivial edges in updateCGAndAnalysisManagerForPass 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. Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D91046 --- llvm/lib/Analysis/CGSCCPassManager.cpp | 9 +++- llvm/lib/Transforms/IPO/Inliner.cpp | 16 +----- llvm/unittests/Analysis/CGSCCPassManagerTest.cpp | 65 ++++++++++++++++++++++++ 3 files changed, 74 insertions(+), 16 deletions(-) diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp index 61c03f9..fddc710 100644 --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -549,7 +549,9 @@ static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass( // 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. @@ -664,6 +666,11 @@ static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass( 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); diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp index 890be9a..0e2e0db 100644 --- a/llvm/lib/Transforms/IPO/Inliner.cpp +++ b/llvm/lib/Transforms/IPO/Inliner.cpp @@ -933,20 +933,6 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 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 @@ -959,7 +945,7 @@ PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, // 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(); diff --git a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp index 9193a2d..2795a35 100644 --- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp +++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp @@ -1838,5 +1838,70 @@ TEST_F(CGSCCPassManagerTest, TestInsertionOfNewRefSCCMutuallyRecursive) { MPM.run(*M, MAM); } +TEST_F(CGSCCPassManagerTest, TestInsertionOfNewNonTrivialCallEdge) { + std::unique_ptr 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(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 -- 2.7.4