[PruneEH][NewPM] Port prune-eh to NPM

[aeubanks]

Summary

All tests under Transforms/PruneEH/ now pass under NPM.

[aeubanks]

remove debugging code

[aeubanks]

extra parentheses

[asbirlea]

I think for clarify this could be split into a patch that updates the current pass to use the CallGraphUpdater, and a patch that only adds the pass for the new pass manager.

llvm/lib/Transforms/IPO/PruneEH.cpp

72–73

I'm not clear if at this point we guarantee that there are no nullptrs in Functions. It would be good to pre-check this.
e.g.

if (Functions.contains (nullptr)) {
  SCCMightUnwind = true;
  SCCMightReturn = true;
  Functions.delete(nullptr); //then the for here and at line 158 doesn't need the check which was in the original and removed here.
}

84

This check for null won't be needed then.

87

The early exit condition !SCCMightUnwind || !SCCMightReturn could be triggered here, so perhaps add:

if (SCCMightUnwind && SCCMightReturn)
          break;

[aeubanks]

In D87625#2272011, @asbirlea wrote:

I think for clarify this could be split into a patch that updates the current pass to use the CallGraphUpdater, and a patch that only adds the pass for the new pass manager.

CallGraphUpdater: https://reviews.llvm.org/D87632
There I also added asserts that all Functions were not null.

[aeubanks]

Move break outside if/else

[aeubanks]

rebase past CallGraphUpdater change

[aeubanks]

asbirlea, you mentioned offline that there were passes that replaced this in the NPM and that this shouldn't be ported, do you know what those are so I can put them in the description of another change pinning tests to the legacy PM?

[asbirlea]

I think for prune-eh, the NPM inliner was intended to address the same cleanup, but I don't have all the context.
@chandlerc for more details.

[aeubanks]

Looking at the pass, it looks like it can be run independently of an inliner since it simply changes invokes into calls whenever possible.
There are lots of random tests that use this pass, and there's even a C API for it.
I think we should port this, and this patch is pretty small. Of course we can always remove it later if we decide to.

[aeubanks]

Abandoned in favor of https://reviews.llvm.org/D90012

llvm/include/llvm/Transforms/IPO/PruneEH.h

+//===- PruneEH.h - Pass which deletes unused exception handlers -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a simple interprocedural pass which walks the
+// call-graph, turning invoke instructions into calls, iff the callee cannot
+// throw an exception, and marking functions 'nounwind' if they cannot throw.
+// It implements this as a bottom-up traversal of the call-graph.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_PRUNEEH_H
+#define LLVM_TRANSFORMS_IPO_PRUNEEH_H
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+struct PruneEHPass : PassInfoMixin<PruneEHPass> {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR);
+};
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_PRUNEEH_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/HotColdSplitting.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
 #include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
+#include "llvm/Transforms/IPO/PruneEH.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Instrumentation/AddressSanitizer.h"

llvm/lib/Passes/PassRegistry.def

 CGSCC_PASS("argpromotion", ArgumentPromotionPass())
 CGSCC_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 CGSCC_PASS("function-attrs", PostOrderFunctionAttrsPass())
 CGSCC_PASS("attributor-cgscc", AttributorCGSCCPass())
 CGSCC_PASS("inline", InlinerPass())
 CGSCC_PASS("openmpopt", OpenMPOptPass())
 CGSCC_PASS("coro-split", CoroSplitPass())
 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())
+CGSCC_PASS("prune-eh", PruneEHPass())
 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis())

llvm/lib/Transforms/IPO/PruneEH.cpp

 //===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a simple interprocedural pass which walks the
 // call-graph, turning invoke instructions into calls, iff the callee cannot
 // throw an exception, and marking functions 'nounwind' if they cannot throw.
 // It implements this as a bottom-up traversal of the call-graph.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Transforms/IPO/PruneEH.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "prune-eh"
 
 STATISTIC(NumRemoved, "Number of invokes removed");
 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
 
 namespace {
   struct PruneEH : public CallGraphSCCPass {
     static char ID; // Pass identification, replacement for typeid
     PruneEH() : CallGraphSCCPass(ID) {
       initializePruneEHPass(*PassRegistry::getPassRegistry());
     }
 
     // runOnSCC - Analyze the SCC, performing the transformation if possible.
     bool runOnSCC(CallGraphSCC &SCC) override;
-
   };
 }
-static bool SimplifyFunction(Function *F, CallGraph &CG);
-static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG);
+static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU);
+static void DeleteBasicBlock(BasicBlock *BB, CallGraphUpdater &CGU);
 
 char PruneEH::ID = 0;
 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 INITIALIZE_PASS_END(PruneEH, "prune-eh",
                 "Remove unused exception handling info", false, false)
 
 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
 
-static bool runImpl(CallGraphSCC &SCC, CallGraph &CG) {
-  SmallPtrSet<CallGraphNode *, 8> SCCNodes;
+static bool runImpl(CallGraphUpdater &CGU, SetVector<Function *> &Functions) {
   bool MadeChange = false;
 
-  // Fill SCCNodes with the elements of the SCC.  Used for quickly
-  // looking up whether a given CallGraphNode is in this SCC.
-  for (CallGraphNode *I : SCC)
-    SCCNodes.insert(I);
-
   // First pass, scan all of the functions in the SCC, simplifying them
   // according to what we know.
-  for (CallGraphNode *I : SCC)
-    if (Function *F = I->getFunction())
-      MadeChange |= SimplifyFunction(F, CG);
+  for (Function *F : Functions)
+    MadeChange |= SimplifyFunction(F, CGU);
 
   // Next, check to see if any callees might throw or if there are any external
   // functions in this SCC: if so, we cannot prune any functions in this SCC.
   // Definitions that are weak and not declared non-throwing might be
   // overridden at linktime with something that throws, so assume that.
   // If this SCC includes the unwind instruction, we KNOW it throws, so
   // obviously the SCC might throw.
   //
   bool SCCMightUnwind = false, SCCMightReturn = false;
-  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end();
-       (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
-    Function *F = (*I)->getFunction();
+  for (Function *F : Functions) {
     if (!F) {
       SCCMightUnwind = true;
       SCCMightReturn = true;
     } else if (!F->hasExactDefinition()) {
       SCCMightUnwind |= !F->doesNotThrow();
       SCCMightReturn |= !F->doesNotReturn();
     } else {
       bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
       bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
       // Determine if we should scan for InlineAsm in a naked function as it
       // is the only way to return without a ReturnInst.  Only do this for
       // no-inline functions as functions which may be inlined cannot
if (!F) {
             break;
 
           // Check to see if this function performs an unwind or calls an
           // unwinding function.
           if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
             bool InstMightUnwind = true;
             if (const auto *CI = dyn_cast<CallInst>(&I)) {
               if (Function *Callee = CI->getCalledFunction()) {
-                CallGraphNode *CalleeNode = CG[Callee];
                 // If the callee is outside our current SCC then we may throw
                 // because it might.  If it is inside, do nothing.
-                if (SCCNodes.count(CalleeNode) > 0)
+                if (Functions.contains(Callee))
                   InstMightUnwind = false;
               }
             }
             SCCMightUnwind |= InstMightUnwind;
           }
           if (CheckReturnViaAsm && !SCCMightReturn)
             if (const auto *CB = dyn_cast<CallBase>(&I))
               if (const auto *IA = dyn_cast<InlineAsm>(CB->getCalledOperand()))
                 if (IA->hasSideEffects())
                   SCCMightReturn = true;
         }
 
-        if (SCCMightUnwind && SCCMightReturn)
-          break;
-      }
-    }
-  }
+      }
 
   // If the SCC doesn't unwind or doesn't throw, note this fact.
   if (!SCCMightUnwind || !SCCMightReturn)
-    for (CallGraphNode *I : SCC) {
-      Function *F = I->getFunction();
-
+    for (Function *F : Functions) {
       if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) {
         F->addFnAttr(Attribute::NoUnwind);
         MadeChange = true;
       }
 
       if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) {
         F->addFnAttr(Attribute::NoReturn);
         MadeChange = true;
       }
     }
 
-  for (CallGraphNode *I : SCC) {
+  for (Function *F : Functions) {
     // Convert any invoke instructions to non-throwing functions in this node
     // into call instructions with a branch.  This makes the exception blocks
     // dead.
-    if (Function *F = I->getFunction())
-      MadeChange |= SimplifyFunction(F, CG);
+    MadeChange |= SimplifyFunction(F, CGU);
   }
 
   return MadeChange;
 }
 
-
 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
+  SetVector<Function *> Functions;
+  for (auto &N : SCC) {
+    if (auto *F = N->getFunction())
+      Functions.insert(F);
+  }
   CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
-  return runImpl(SCC, CG);
+  CallGraphUpdater CGU;
+  CGU.initialize(CG, SCC);
+  return runImpl(CGU, Functions);
 }
 
 
 // SimplifyFunction - Given information about callees, simplify the specified
 // function if we have invokes to non-unwinding functions or code after calls to
 // no-return functions.
-static bool SimplifyFunction(Function *F, CallGraph &CG) {
+static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU) {
   bool MadeChange = false;
   for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
       if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
         BasicBlock *UnwindBlock = II->getUnwindDest();
         removeUnwindEdge(&*BB);
 
         // If the unwind block is now dead, nuke it.
         if (pred_empty(UnwindBlock))
-          DeleteBasicBlock(UnwindBlock, CG);  // Delete the new BB.
+          DeleteBasicBlock(UnwindBlock, CGU); // Delete the new BB.
 
         ++NumRemoved;
         MadeChange = true;
       }
 
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
       if (CallInst *CI = dyn_cast<CallInst>(I++))
         if (CI->doesNotReturn() && !CI->isMustTailCall() &&
             !isa<UnreachableInst>(I)) {
           // This call calls a function that cannot return.  Insert an
           // unreachable instruction after it and simplify the code.  Do this
           // by splitting the BB, adding the unreachable, then deleting the
           // new BB.
           BasicBlock *New = BB->splitBasicBlock(I);
 
           // Remove the uncond branch and add an unreachable.
           BB->getInstList().pop_back();
           new UnreachableInst(BB->getContext(), &*BB);
 
-          DeleteBasicBlock(New, CG);  // Delete the new BB.
+          DeleteBasicBlock(New, CGU); // Delete the new BB.
           MadeChange = true;
           ++NumUnreach;
           break;
         }
   }
 
   return MadeChange;
 }
 
 /// DeleteBasicBlock - remove the specified basic block from the program,
 /// updating the callgraph to reflect any now-obsolete edges due to calls that
 /// exist in the BB.
-static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG) {
+static void DeleteBasicBlock(BasicBlock *BB, CallGraphUpdater &CGU) {
   assert(pred_empty(BB) && "BB is not dead!");
 
   Instruction *TokenInst = nullptr;
 
-  CallGraphNode *CGN = CG[BB->getParent()];
   for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
     --I;
 
     if (I->getType()->isTokenTy()) {
       TokenInst = &*I;
       break;
     }
 
     if (auto *Call = dyn_cast<CallBase>(&*I)) {
       const Function *Callee = Call->getCalledFunction();
       if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
-        CGN->removeCallEdgeFor(*Call);
+        CGU.removeCallSite(*Call);
       else if (!Callee->isIntrinsic())
-        CGN->removeCallEdgeFor(*Call);
+        CGU.removeCallSite(*Call);
     }
 
     if (!I->use_empty())
       I->replaceAllUsesWith(UndefValue::get(I->getType()));
   }
 
   if (TokenInst) {
     if (!TokenInst->isTerminator())
       changeToUnreachable(TokenInst->getNextNode(), /*UseLLVMTrap=*/false);
   } else {
     // Get the list of successors of this block.
     std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
 
     for (unsigned i = 0, e = Succs.size(); i != e; ++i)
       Succs[i]->removePredecessor(BB);
 
     BB->eraseFromParent();
   }
 }
+
+PreservedAnalyses PruneEHPass::run(LazyCallGraph::SCC &C,
+                                   CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+                                   CGSCCUpdateResult &UR) {
+  SetVector<Function *> Functions;
+  for (auto &N : C)
+    Functions.insert(&N.getFunction());
+  CallGraphUpdater CGU;
+  CGU.initialize(CG, C, AM, UR);
+  return runImpl(CGU, Functions) ? PreservedAnalyses::none()
+                                 : PreservedAnalyses::all();
+}

llvm/test/Transforms/PruneEH/looptest.ll

 ; RUN: opt < %s -prune-eh -S | FileCheck %s
+; RUN: opt < %s -passes=prune-eh -S | FileCheck %s
 
 declare void @nounwind() nounwind
 
 define internal void @foo() {
   call void @nounwind()
   ret void
 }