[CallGraphUpdater] Remove nodes from their SCC (old PM)

[jdoerfert]

Summary

We can and should remove deleted nodes from their respective SCCs. We
did not do this before and this was a potential problem even though I
couldn't locally trigger an issue. Since the DeleteNode would assert
if the node was not in the SCC, we know we only remove nodes from their
SCC and only once (when run on all the Attributor tests).

[hfinkel]

LGTM

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

115

I realize that this probably doesn't matter, but I wonder if the code would be clearer here if you wrote:

if (CG && ...)

because you've dereferencing CG here and use of CGSCC is guarded below by GC (instead of directly by checking CGSCC). Keeping the guarding conditions the same should make the code more readable by eliminating potential questions about why they're different.

[MaskRay]

llvm/lib/Analysis/CallGraphSCCPass.cpp

566

clang-format prefers /*New=*/nullptr

[jdoerfert]

addressed nits

llvm/include/llvm/Analysis/CallGraphSCCPass.h

public:
 
   bool isSingular() const { return Nodes.size() == 1; }
   unsigned size() const { return Nodes.size(); }
 
   /// ReplaceNode - This informs the SCC and the pass manager that the specified
   /// Old node has been deleted, and New is to be used in its place.
   void ReplaceNode(CallGraphNode *Old, CallGraphNode *New);
 
+  /// DeleteNode - This informs the SCC and the pass manager that the specified
+  /// Old node has been deleted.
+  void DeleteNode(CallGraphNode *Old);
+
   using iterator = std::vector<CallGraphNode *>::const_iterator;
 
   iterator begin() const { return Nodes.begin(); }
   iterator end() const { return Nodes.end(); }
 
   const CallGraph &getCallGraph() { return CG; }
 };
 

llvm/lib/Analysis/CallGraphSCCPass.cpp

void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
   }
 
   // Update the active scc_iterator so that it doesn't contain dangling
   // pointers to the old CallGraphNode.
   scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
   CGI->ReplaceNode(Old, New);
 }
 
+void CallGraphSCC::DeleteNode(CallGraphNode *Old) {
+  ReplaceNode(Old, /* New */ nullptr);
+}
+
 //===----------------------------------------------------------------------===//
 // CallGraphSCCPass Implementation
 //===----------------------------------------------------------------------===//
 
 /// Assign pass manager to manage this pass.
 void CallGraphSCCPass::assignPassManager(PMStack &PMS,
                                          PassManagerType PreferredType) {
   // Find CGPassManager

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

 
 void CallGraphUpdater::removeFunction(Function &DeadFn) {
   DeadFn.deleteBody();
   DeadFn.setLinkage(GlobalValue::ExternalLinkage);
   if (DeadFn.hasComdat())
     DeadFunctionsInComdats.push_back(&DeadFn);
   else
     DeadFunctions.push_back(&DeadFn);
+
+  // For the old call graph we remove the function from the SCC right away.
+  if (CGSCC && !ReplacedFunctions.count(&DeadFn))
+    CGSCC->DeleteNode((*CG)[&DeadFn]);
 }
 
 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
   OldFn.removeDeadConstantUsers();
   ReplacedFunctions.insert(&OldFn);
   if (CG) {
     // Update the call graph for the newly promoted function.
     CallGraphNode *OldCGN = (*CG)[&OldFn];

llvm/unittests/IR/LegacyPassManagerTest.cpp

Function *splitSimpleFunction(Function &F) {
       CI.clone()->insertBefore(ReturnInst::Create(Context, Entry));
       CI.setCalledFunction(SF);
       return SF;
     }
 
     struct CGModifierPass : public CGPass {
       unsigned NumSCCs = 0;
       unsigned NumFns = 0;
-      bool SetupWorked = true;
+      unsigned NumFnDecls = 0;
+      unsigned SetupWorked = 0;
       unsigned NumExtCalledBefore = 0;
       unsigned NumExtCalledAfter = 0;
 
       CallGraphUpdater CGU;
 
       bool runOnSCC(CallGraphSCC &SCMM) override {
         ++NumSCCs;
-        for (CallGraphNode *N : SCMM)
-          if (N->getFunction())
+        for (CallGraphNode *N : SCMM) {
+          if (N->getFunction()){
             ++NumFns;
-
+            NumFnDecls += N->getFunction()->isDeclaration();
+          }
+        }
         CGPass::run();
 
         CallGraph &CG = const_cast<CallGraph &>(SCMM.getCallGraph());
         CallGraphNode *ExtCallingNode = CG.getExternalCallingNode();
         NumExtCalledBefore = ExtCallingNode->size();
 
         if (SCMM.size() <= 1)
           return false;
struct CGModifierPass : public CGPass {
         auto InSCC = [&](Function *Fn) {
           return llvm::any_of(SCMM, [Fn](CallGraphNode *CGN) {
             return CGN->getFunction() == Fn;
           });
         };
 
         if (!Test1F || !Test2aF || !Test2bF || !Test3F || !InSCC(Test1F) ||
             !InSCC(Test2aF) || !InSCC(Test2bF) || !InSCC(Test3F))
-          return SetupWorked = false;
+          return false;
 
         CallInst *CI = dyn_cast<CallInst>(&Test1F->getEntryBlock().front());
         if (!CI || CI->getCalledFunction() != Test2aF)
-          return SetupWorked = false;
+          return false;
+
+        SetupWorked += 1;
 
         // 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();
struct CGModifierPass : public CGPass {
         NumExtCalledAfter = CG.getExternalCallingNode()->size();
         return true;
       }
     };
 
     TEST(PassManager, CallGraphUpdater0) {
       // SCC#1: test1->test2a->test2b->test3->test1
       // SCC#2: test4
-      // SCC#3: indirect call node
+      // SCC#3: test3 (the empty function declaration as we replaced it with
+      //               test3repl when we visited SCC#1)
+      // SCC#4: test2a->test2b (the empty function declarations as we deleted
+      //                        these functions when we visited SCC#1)
+      // SCC#5: indirect call node
 
       LLVMContext Context;
       std::unique_ptr<Module> M(makeLLVMModule(Context));
       ASSERT_EQ(M->getFunctionList().size(), 4U);
       Function *F = M->getFunction("test2");
       Function *SF = splitSimpleFunction(*F);
       CallInst::Create(F, "", &SF->getEntryBlock());
       ASSERT_EQ(M->getFunctionList().size(), 5U);
       CGModifierPass *P = new CGModifierPass();
       legacy::PassManager Passes;
       Passes.add(P);
       Passes.run(*M);
-      ASSERT_TRUE(P->SetupWorked);
-      ASSERT_EQ(P->NumSCCs, 3U);
-      ASSERT_EQ(P->NumFns, 5U);
+      ASSERT_EQ(P->SetupWorked, 1U);
+      ASSERT_EQ(P->NumSCCs, 5U);
+      ASSERT_EQ(P->NumFns, 8U);
+      ASSERT_EQ(P->NumFnDecls, 3U);
       ASSERT_EQ(M->getFunctionList().size(), 3U);
       ASSERT_EQ(P->NumExtCalledBefore, /* test1, 2a, 2b, 3, 4 */ 5U);
       ASSERT_EQ(P->NumExtCalledAfter, /* test1, 3repl, 4 */ 3U);
     }
   }
 }
 
 INITIALIZE_PASS(ModuleNDM, "mndm", "mndm", false, false)
 INITIALIZE_PASS_BEGIN(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(CGPass, "cgp","cgp", false, false)
 INITIALIZE_PASS(FPass, "fp","fp", false, false)
 INITIALIZE_PASS_BEGIN(LPass, "lp","lp", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LPass, "lp","lp", false, false)