From 1b34b84ddd666a30b0e7e18177997bab32e826b7 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Thu, 9 Apr 2020 15:21:24 -0500 Subject: [PATCH] [CallGraphUpdater] Update the ExternalCallingNode for node replacements Summary: While it is uncommon that the ExternalCallingNode needs to be updated, it can happen. It is uncommon because most functions listed as callees have external linkage, modifying them is usually not allowed. That said, there are also internal functions that have, or better had, their "address taken" at construction time. We conservatively assume various uses cause the address "to be taken". Furthermore, the user might have become dead at some point. As a consequence, transformations, e.g., the Attributor, might be able to replace a function that is listed as callee of the ExternalCallingNode. Since there is no function corresponding to the ExternalCallingNode, we did just remove the node from the callee list if we replaced it (so far). Now it would be preferable to replace it if needed and remove it otherwise. However, removing the node has implications on the CGSCC iteration. Locally, that caused some other nodes to be never visited but it is for sure possible other (bad) side effects can occur. As it seems conservatively safe to keep the new node in the callee list we will do that for now. Reviewers: lebedev.ri, hfinkel, fhahn, probinson, wristow, loladiro, sstefan1, uenoku Subscribers: hiraditya, bollu, uenoku, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D77854 --- llvm/include/llvm/Analysis/CallGraph.h | 4 +++ llvm/lib/Analysis/CallGraph.cpp | 10 ++++++ llvm/lib/Transforms/Utils/CallGraphUpdater.cpp | 2 +- llvm/unittests/IR/LegacyPassManagerTest.cpp | 45 +++++++++++++++++++++++--- 4 files changed, 56 insertions(+), 5 deletions(-) diff --git a/llvm/include/llvm/Analysis/CallGraph.h b/llvm/include/llvm/Analysis/CallGraph.h index 768dcea..4cb4cfa 100644 --- a/llvm/include/llvm/Analysis/CallGraph.h +++ b/llvm/include/llvm/Analysis/CallGraph.h @@ -138,6 +138,10 @@ public: return CallsExternalNode.get(); } + /// Old node has been deleted, and New is to be used in its place, update the + /// ExternalCallingNode. + void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New); + //===--------------------------------------------------------------------- // Functions to keep a call graph up to date with a function that has been // modified. diff --git a/llvm/lib/Analysis/CallGraph.cpp b/llvm/lib/Analysis/CallGraph.cpp index 7dd5a71..2843358 100644 --- a/llvm/lib/Analysis/CallGraph.cpp +++ b/llvm/lib/Analysis/CallGraph.cpp @@ -129,6 +129,16 @@ void CallGraph::print(raw_ostream &OS) const { LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); } #endif +void CallGraph::ReplaceExternalCallEdge(CallGraphNode *Old, + CallGraphNode *New) { + for (auto &CR : ExternalCallingNode->CalledFunctions) + if (CR.second == Old) { + CR.second->DropRef(); + CR.second = New; + CR.second->AddRef(); + } +} + // removeFunctionFromModule - Unlink the function from this module, returning // it. Because this removes the function from the module, the call graph node // is destroyed. This is only valid if the function does not call any other diff --git a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp index 00c6007..2cccfba 100644 --- a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp +++ b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp @@ -117,10 +117,10 @@ void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) { ReplacedFunctions.insert(&OldFn); if (CG) { // Update the call graph for the newly promoted function. - // CG->spliceFunction(&OldFn, &NewFn); CallGraphNode *OldCGN = (*CG)[&OldFn]; CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn); NewCGN->stealCalledFunctionsFrom(OldCGN); + CG->ReplaceExternalCallEdge(OldCGN, NewCGN); // And update the SCC we're iterating as well. CGSCC->ReplaceNode(OldCGN, NewCGN); diff --git a/llvm/unittests/IR/LegacyPassManagerTest.cpp b/llvm/unittests/IR/LegacyPassManagerTest.cpp index 2fa9746..4456e6a 100644 --- a/llvm/unittests/IR/LegacyPassManagerTest.cpp +++ b/llvm/unittests/IR/LegacyPassManagerTest.cpp @@ -459,7 +459,7 @@ namespace llvm { Function* func_test3 = Function::Create( /*Type=*/FuncTy_0, - /*Linkage=*/GlobalValue::ExternalLinkage, + /*Linkage=*/GlobalValue::InternalLinkage, /*Name=*/"test3", mod); func_test3->setCallingConv(CallingConv::C); AttributeList func_test3_PAL; @@ -546,6 +546,9 @@ namespace llvm { BasicBlock::Create(Context, "return", func_test4, nullptr); // Block entry (label_entry_11) + auto *AI = new AllocaInst(func_test3->getType(), 0, "func3ptr", + label_entry_11); + new StoreInst(func_test3, AI, label_entry_11); BranchInst::Create(label_bb, label_entry_11); // Block bb (label_bb) @@ -579,6 +582,8 @@ namespace llvm { unsigned NumSCCs = 0; unsigned NumFns = 0; bool SetupWorked = true; + unsigned NumExtCalledBefore = 0; + unsigned NumExtCalledAfter = 0; CallGraphUpdater CGU; @@ -590,6 +595,10 @@ namespace llvm { CGPass::run(); + CallGraph &CG = const_cast(SCMM.getCallGraph()); + CallGraphNode *ExtCallingNode = CG.getExternalCallingNode(); + NumExtCalledBefore = ExtCallingNode->size(); + if (SCMM.size() <= 1) return false; @@ -600,6 +609,7 @@ namespace llvm { Function *Test2aF = M->getFunction("test2a"); Function *Test2bF = M->getFunction("test2b"); Function *Test3F = M->getFunction("test3"); + auto InSCC = [&](Function *Fn) { return llvm::any_of(SCMM, [Fn](CallGraphNode *CGN) { return CGN->getFunction() == Fn; @@ -614,16 +624,41 @@ namespace llvm { if (!CI || CI->getCalledFunction() != Test2aF) return SetupWorked = false; - CI->setCalledFunction(Test3F); + // Create a replica of test3 and just move the blocks there. + Function *Test3FRepl = Function::Create( + /*Type=*/Test3F->getFunctionType(), + /*Linkage=*/GlobalValue::InternalLinkage, + /*Name=*/"test3repl", Test3F->getParent()); + while (!Test3F->empty()) { + BasicBlock &BB = Test3F->front(); + BB.removeFromParent(); + BB.insertInto(Test3FRepl); + } + + CGU.initialize(CG, SCMM); - CGU.initialize(const_cast(SCMM.getCallGraph()), SCMM); + // Replace test3 with the replica. This is legal as it is actually + // internal and the "capturing use" is not really capturing anything. + CGU.replaceFunctionWith(*Test3F, *Test3FRepl); + Test3F->replaceAllUsesWith(Test3FRepl); + + // Rewrite the call in test1 to point to the replica of 3 not test2. + CI->setCalledFunction(Test3FRepl); + + // Delete test2a and test2b and reanalyze 1 as we changed calls inside. CGU.removeFunction(*Test2aF); CGU.removeFunction(*Test2bF); CGU.reanalyzeFunction(*Test1F); + return true; } - bool doFinalization(CallGraph &CG) override { return CGU.finalize(); } + bool doFinalization(CallGraph &CG) override { + CGU.finalize(); + // We removed test2 and replaced the internal test3. + NumExtCalledAfter = CG.getExternalCallingNode()->size(); + return true; + } }; TEST(PassManager, CallGraphUpdater0) { @@ -646,6 +681,8 @@ namespace llvm { ASSERT_EQ(P->NumSCCs, 3U); ASSERT_EQ(P->NumFns, 5U); ASSERT_EQ(M->getFunctionList().size(), 3U); + ASSERT_EQ(P->NumExtCalledBefore, /* test1, 2a, 2b, 3, 4 */ 5U); + ASSERT_EQ(P->NumExtCalledAfter, /* test1, 3repl, 4 */ 3U); } } } -- 2.7.4