[GlobalOpt] Preserve CFG analyses

[aeubanks]

Summary

The only place we modify the CFG is when calling
removeUnreachableBlocks(), so insert a callback there which invalidates
analyses for that function (or recomputes DT in the legacy PM).

We may delete functions, make sure to clear analyses for those functions.

Small compile time wins across the board:
https://llvm-compile-time-tracker.com/compare.php?from=f444ea8ce0aaaa5ec1a4129809389da15cc41396&to=698f41f4fc26cbf1006ed5d88e9d658edfc5b749&stat=instructions

[nikic]

LGTM

[aeubanks]

fix https://github.com/llvm/llvm-project/issues/56131

[nikic]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

1918

Spurious newline?

llvm/lib/Transforms/IPO/GlobalOpt.cpp

static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
 
   // Retain the name of the old global variable. People who are debugging their
   // programs may expect these variables to be named the same.
   NewGV->takeName(GV);
   GV->eraseFromParent();
   return true;
 }
 
-static bool deleteIfDead(
-    GlobalValue &GV, SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
+static bool
+deleteIfDead(GlobalValue &GV,
+             SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
+             function_ref<void(Function &)> DeleteFnCallback = nullptr) {
   GV.removeDeadConstantUsers();
 
   if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
     return false;
 
   if (const Comdat *C = GV.getComdat())
     if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
       return false;
 
   bool Dead;
   if (auto *F = dyn_cast<Function>(&GV))
     Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
   else
     Dead = GV.use_empty();
   if (!Dead)
     return false;
 
   LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n");
+  if (auto *F = dyn_cast<Function>(&GV)) {
+    if (DeleteFnCallback)
+      DeleteFnCallback(*F);
+  }
   GV.eraseFromParent();
   ++NumDeleted;
   return true;
 }
 
 static bool isPointerValueDeadOnEntryToFunction(
     const Function *F, GlobalValue *GV,
     function_ref<DominatorTree &(Function &)> LookupDomTree) {

 }
 
 static bool
 OptimizeFunctions(Module &M,
                   function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                   function_ref<TargetTransformInfo &(Function &)> GetTTI,
                   function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
                   function_ref<DominatorTree &(Function &)> LookupDomTree,
-                  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
+                  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
+                  function_ref<void(Function &F)> ChangedCFGCallback,
+                  function_ref<void(Function &F)> DeleteFnCallback
+
+) {
 
   bool Changed = false;
 
   std::vector<Function *> AllCallsCold;
   for (Function &F : llvm::make_early_inc_range(M))
     if (hasOnlyColdCalls(F, GetBFI))
       AllCallsCold.push_back(&F);
 
   // Optimize functions.
   for (Function &F : llvm::make_early_inc_range(M)) {
     // Don't perform global opt pass on naked functions; we don't want fast
     // calling conventions for naked functions.
     if (F.hasFnAttribute(Attribute::Naked))
       continue;
 
     // Functions without names cannot be referenced outside this module.
     if (!F.hasName() && !F.isDeclaration() && !F.hasLocalLinkage())
       F.setLinkage(GlobalValue::InternalLinkage);
 
-    if (deleteIfDead(F, NotDiscardableComdats)) {
+    if (deleteIfDead(F, NotDiscardableComdats, DeleteFnCallback)) {
       Changed = true;
       continue;
     }
 
     // LLVM's definition of dominance allows instructions that are cyclic
     // in unreachable blocks, e.g.:
     // %pat = select i1 %condition, @global, i16* %pat
     // because any instruction dominates an instruction in a block that's
     // not reachable from entry.
     // So, remove unreachable blocks from the function, because a) there's
     // no point in analyzing them and b) GlobalOpt should otherwise grow
     // some more complicated logic to break these cycles.
-    // Removing unreachable blocks might invalidate the dominator so we
-    // recalculate it.
+    // Notify the analysis manager that we've modified the function's CFG.
     if (!F.isDeclaration()) {
       if (removeUnreachableBlocks(F)) {
-        auto &DT = LookupDomTree(F);
-        DT.recalculate(F);
         Changed = true;
+        ChangedCFGCallback(F);
       }
     }
 
     Changed |= processGlobal(F, GetTTI, GetTLI, LookupDomTree);
 
     if (!F.hasLocalLinkage())
       continue;
 
for (User *U : llvm::make_early_inc_range(CXAAtExitFn->users())) {
     ++NumCXXDtorsRemoved;
 
     Changed |= true;
   }
 
   return Changed;
 }
 
-static bool optimizeGlobalsInModule(
-    Module &M, const DataLayout &DL,
+static bool
+optimizeGlobalsInModule(Module &M, const DataLayout &DL,
                         function_ref<TargetLibraryInfo &(Function &)> GetTLI,
                         function_ref<TargetTransformInfo &(Function &)> GetTTI,
                         function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
-    function_ref<DominatorTree &(Function &)> LookupDomTree) {
+                        function_ref<DominatorTree &(Function &)> LookupDomTree,
+                        function_ref<void(Function &F)> ChangedCFGCallback,
+                        function_ref<void(Function &F)> DeleteFnCallback) {
   SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
   bool Changed = false;
   bool LocalChange = true;
   Optional<uint32_t> FirstNotFullyEvaluatedPriority;
 
   while (LocalChange) {
     LocalChange = false;
 
     NotDiscardableComdats.clear();
     for (const GlobalVariable &GV : M.globals())
       if (const Comdat *C = GV.getComdat())
         if (!GV.isDiscardableIfUnused() || !GV.use_empty())
           NotDiscardableComdats.insert(C);
     for (Function &F : M)
       if (const Comdat *C = F.getComdat())
         if (!F.isDefTriviallyDead())
           NotDiscardableComdats.insert(C);
     for (GlobalAlias &GA : M.aliases())
       if (const Comdat *C = GA.getComdat())
         if (!GA.isDiscardableIfUnused() || !GA.use_empty())
           NotDiscardableComdats.insert(C);
 
     // Delete functions that are trivially dead, ccc -> fastcc
     LocalChange |= OptimizeFunctions(M, GetTLI, GetTTI, GetBFI, LookupDomTree,
-                                     NotDiscardableComdats);
+                                     NotDiscardableComdats, ChangedCFGCallback,
+                                     DeleteFnCallback);
 
     // Optimize global_ctors list.
     LocalChange |=
         optimizeGlobalCtorsList(M, [&](uint32_t Priority, Function *F) {
           if (FirstNotFullyEvaluatedPriority &&
               *FirstNotFullyEvaluatedPriority != Priority)
             return false;
           bool Evaluated = EvaluateStaticConstructor(F, DL, &GetTLI(*F));
PreservedAnalyses GlobalOptPass::run(Module &M, ModuleAnalysisManager &AM) {
     };
     auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
       return FAM.getResult<TargetIRAnalysis>(F);
     };
 
     auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
       return FAM.getResult<BlockFrequencyAnalysis>(F);
     };
+    auto ChangedCFGCallback = [&FAM](Function &F) {
+      FAM.invalidate(F, PreservedAnalyses::none());
+    };
+    auto DeleteFnCallback = [&FAM](Function &F) { FAM.clear(F, F.getName()); };
 
-    if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree))
+    if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree,
+                                 ChangedCFGCallback, DeleteFnCallback))
       return PreservedAnalyses::all();
-    return PreservedAnalyses::none();
+
+    PreservedAnalyses PA = PreservedAnalyses::none();
+    // We made sure to clear analyses for deleted functions.
+    PA.preserve<FunctionAnalysisManagerModuleProxy>();
+    // The only place we modify the CFG is when calling
+    // removeUnreachableBlocks(), but there we make sure to invalidate analyses
+    // for modified functions.
+    PA.preserveSet<CFGAnalyses>();
+    return PA;
 }
 
 namespace {
 
 struct GlobalOptLegacyPass : public ModulePass {
   static char ID; // Pass identification, replacement for typeid
 
   GlobalOptLegacyPass() : ModulePass(ID) {
bool runOnModule(Module &M) override {
     auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
       return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     };
 
     auto GetBFI = [this](Function &F) -> BlockFrequencyInfo & {
       return this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
     };
 
-    return optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI,
-                                   LookupDomTree);
+    auto ChangedCFGCallback = [&LookupDomTree](Function &F) {
+      auto &DT = LookupDomTree(F);
+      DT.recalculate(F);
+    };
+
+    return optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree,
+                                   ChangedCFGCallback, nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
   }

llvm/test/Transforms/GlobalOpt/analysis-invalidation.ll

+; RUN: opt -passes='function(require<no-op-function>),globalopt' %s -debug-pass-manager -S 2>&1 | FileCheck %s
+
+; CHECK: Clearing all analysis results for: f
+; CHECK-NOT: @f
+
+define internal void @f() {
+  ret void
+}