[Inline] Attempt to delete any discardable if unused functions

[aeubanks]

Summary

Previously we limited ourselves to only internal/private functions. We
can also delete linkonce_odr functions.

Minor compile time wins:
https://llvm-compile-time-tracker.com/compare.php?from=d51e3474e060cb0e90dc2e2487f778b0d3e6a8de&to=bccffe3f8d5dd4dda884c9ac1f93e51772519cad&stat=instructions

Major memory wins on tramp3d:
https://llvm-compile-time-tracker.com/compare.php?from=d51e3474e060cb0e90dc2e2487f778b0d3e6a8de&to=bccffe3f8d5dd4dda884c9ac1f93e51772519cad&stat=max-rss

[nikic]

I believe that for non-local linkage you also need to check for comdats. You can only drop the comdat as a whole, not an individual function.

[aeubanks]

check for comdats
this causes compile time regressions due to calling LazyCallGraph::removeDeadFunction() more, seeing if that can be optimized

[nikic]

In D115545#3190357, @aeubanks wrote:

this causes compile time regressions due to calling LazyCallGraph::removeDeadFunction() more, seeing if that can be optimized

That seems surprising, what's so expensive about that method?

[aeubanks]

In D115545#3192006, @nikic wrote:

In D115545#3190357, @aeubanks wrote:

this causes compile time regressions due to calling LazyCallGraph::removeDeadFunction() more, seeing if that can be optimized

That seems surprising, what's so expensive about that method?

Weird, I remeasured and it didn't show up as significant anymore.

Now filterDeadComdatFunctions() is extremely expensive, which makes sense since we're iterating over every function/global in the module on every inliner run on an SCC. Not sure there's a good way around this unless we start keeping track of comdat users within the comdat.
Shame since this saves a lot of memory of template heavy code: https://llvm-compile-time-tracker.com/compare.php?from=d66323c1ef28104ccf7d72e05954fc1241845a33&to=c0a6e811b81deee725a2eaf37662d7181e11e704&stat=max-rss. Which I actually don't really understand. I would have thought that we're already clearing function analyses due to the recently added eager invalidation flag, and I wouldn't think that the IR itself takes up that much memory compared to analyses, but maybe I'm wrong.

[nikic]

In D115545#3196100, @aeubanks wrote:

In D115545#3192006, @nikic wrote:

In D115545#3190357, @aeubanks wrote:

this causes compile time regressions due to calling LazyCallGraph::removeDeadFunction() more, seeing if that can be optimized

That seems surprising, what's so expensive about that method?

Weird, I remeasured and it didn't show up as significant anymore.

Now filterDeadComdatFunctions() is extremely expensive, which makes sense since we're iterating over every function/global in the module on every inliner run on an SCC. Not sure there's a good way around this unless we start keeping track of comdat users within the comdat.

Keeping track of users makes sense to me, and doesn't seem overly complicated. I've put up a prototype at D115864.

Shame since this saves a lot of memory of template heavy code: https://llvm-compile-time-tracker.com/compare.php?from=d66323c1ef28104ccf7d72e05954fc1241845a33&to=c0a6e811b81deee725a2eaf37662d7181e11e704&stat=max-rss. Which I actually don't really understand. I would have thought that we're already clearing function analyses due to the recently added eager invalidation flag, and I wouldn't think that the IR itself takes up that much memory compared to analyses, but maybe I'm wrong.

I believe we'd keep analyses queried on the callee (which should be BFI -> LI -> DT), as we'll only invalidate analysis on the caller after inlining is done. Which does seem like the right thing to do, otherwise we'd recompute those every time a callee is considered. But I also don't think these analyses are particularly large either.

[nikic]

In D115545#3197069, @nikic wrote:

In D115545#3196100, @aeubanks wrote:

In D115545#3192006, @nikic wrote:

In D115545#3190357, @aeubanks wrote:

this causes compile time regressions due to calling LazyCallGraph::removeDeadFunction() more, seeing if that can be optimized

That seems surprising, what's so expensive about that method?

Weird, I remeasured and it didn't show up as significant anymore.

Now filterDeadComdatFunctions() is extremely expensive, which makes sense since we're iterating over every function/global in the module on every inliner run on an SCC. Not sure there's a good way around this unless we start keeping track of comdat users within the comdat.

Keeping track of users makes sense to me, and doesn't seem overly complicated. I've put up a prototype at D115864.

Though testing that patch with this one the compile-time impact seems to be about the same, so either I did something wrong or the problem isn't with the comdat scan.

[nikic]

Okay, it turns out that we simply need all three. The combination of this patch, D115864 and https://github.com/llvm/llvm-project/commit/d66323c1ef28104ccf7d72e05954fc1241845a33 results in http://llvm-compile-time-tracker.com/compare.php?from=a8c2ba105d47fd9e085ee6f2154005de9888609b&to=9d87c1d809d575e34b55514557bbe66edeb0ef57&stat=instructions.

[nikic]

LGTM

llvm/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll

2

Ugh. I've dropped -inline from this test in https://github.com/llvm/llvm-project/commit/9e4aeb1f60a5ccf3f709cd5772473617f8538864.

[nikic]

Hm, it looks like this breaks the test-suite build under ReleaseLTO-g: https://llvm-compile-time-tracker.com/show_error.php?commit=bccffe3f8d5dd4dda884c9ac1f93e51772519cad

[aeubanks]

In D115545#3228162, @nikic wrote:

Hm, it looks like this breaks the test-suite build under ReleaseLTO-g: https://llvm-compile-time-tracker.com/show_error.php?commit=bccffe3f8d5dd4dda884c9ac1f93e51772519cad

taking a look

[aeubanks]

reduced repro

$ opt -passes=inline -o /dev/null -S a.ll
$ cat /tmp/a.ll
%a = type { i8*, i8* }

$f3 = comdat any

define linkonce_odr void @f1() {
  %call5 = call void (i64, %a*)* @f2(void (i64, %a*)* @f3)
  ret void
}

define linkonce_odr void (i64, %a*)* @f2(void (i64, %a*)* %__f) {
  call void @llvm.dbg.value(metadata void (i64, %a*)* %__f, metadata !2, metadata !DIExpression()), !dbg !10
  call void %__f(i64 0, %a* null)
  ret void (i64, %a*)* null
}

define linkonce_odr void @f3(i64 %t.coerce0, %a* %t.coerce1) comdat {
  ret void
}

; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
declare void @llvm.dbg.value(metadata, metadata, metadata) #0

attributes #0 = { nofree nosync nounwind readnone speculatable willreturn }

!llvm.module.flags = !{!0, !1}

!0 = !{i32 7, !"Dwarf Version", i32 4}
!1 = !{i32 2, !"Debug Info Version", i32 3}
!2 = !DILocalVariable(name: "__f", arg: 3, scope: !3, file: !4, line: 3814, type: !9)
!3 = distinct !DISubprogram(scope: !5, file: !4, line: 3814, type: !6, scopeLine: 3815, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !8, templateParams: !7, retainedNodes: !7)
!4 = !DIFile(filename: "a", directory: "")
!5 = !DINamespace(name: "std", scope: null)
!6 = !DISubroutineType(types: !7)
!7 = !{}
!8 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !4, isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !7, retainedTypes: !7, globals: !7, imports: !7, splitDebugInlining: false, nameTableKind: None)
!9 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !6, size: 64)
!10 = !DILocation(line: 0, scope: !3)

the crash is because use_empty() doesn't account for metadata uses and eventually we end up with

define linkonce_odr void @f1() {                                                                                                                                                                   
  call void @llvm.dbg.value(metadata void (i64, %a*)* @f3, metadata !2, metadata !DIExpression()), !dbg !10                                                                                        
  ret void                                                                                                                                                                                         
}                                                                                                                                                                                                  
                                                                                                                                                                                                   
declare linkonce_odr void @f3(i64 %t.coerce0, %a* %t.coerce1) comdat

and we delete @f3() even with the metadata reference

[aeubanks]

fix crash

[nikic]

llvm/lib/Transforms/IPO/Inliner.cpp

953–968

I don't think this is the right way to fix it. The whole premise of metadata users is that they automatically get dropped when the value is destroyed.

I think the problem here is that for the comdat case, we call recordInlining() rather than recordInliningWithCalleeDeleted(), and apparently for some reason the InlineAdvisor is actually responsible for destroying functions, so the function ends up only getting removed from the module, but not erased, and metadata users never get dropped. This means that other cleanup also won't happen, not just the incorrect metadata uses.

I think we either need to restrict this to the case where the comdat is trivial (only has one entry) and we can make the decision immediately, or we need to adjust the advisor API to separate out "recordInlining" from "recordCalleeDeleted". Not sure how that would interact with the ML inline advisor though, cc @mtrofin.

I'd recommend to go for the trivial comdat check for now, because I think that's the main interesting case anyway.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

953–968

I don't think this is the right way to fix it. The whole premise of metadata users is that they automatically get dropped when the value is destroyed.

I think the problem here is that for the comdat case, we call recordInlining() rather than recordInliningWithCalleeDeleted(), and apparently for some reason the InlineAdvisor is actually responsible for destroying functions, so the function ends up only getting removed from the module, but not erased, and metadata users never get dropped. This means that other cleanup also won't happen, not just the incorrect metadata uses.

I think we either need to restrict this to the case where the comdat is trivial (only has one entry) and we can make the decision immediately, or we need to adjust the advisor API to separate out "recordInlining" from "recordCalleeDeleted". Not sure how that would interact with the ML inline advisor though, cc @mtrofin.

I'd recommend to go for the trivial comdat check for now, because I think that's the main interesting case anyway.

953–968

The reason the advisor took the responsibility of actually deleting (i.e. delete - deleting) dead functions was to allow it to use function pointers to track some module-wide state. So then all other cleanup should have been done here, but the actual object is deleted at the end. We missed the cleanup in GlobalObject.

I think the better approach is to use Node (LazySCC::Node). I think I should do that change, remove the deleting responsibility from the Advisor, then we can delete functions at line 1048 down, and then, like @nikic observed, we should call here recordInliningWithCaleeDeleted, because we want to track if the effect of an inlining simplifies the call graph. If that sounds reasonable, I'll have the patch up shortly.

BTW - so if not all linkonce_odr functions can be deleted, then what happens, they'd still be emitted, but then, at link time, they'd be dropped?

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

953–968

D116964 for removing the deleting responsibility from the Advisor.

[aeubanks]

rebase past D116964
drop metadata use check

[nikic]

LGTM

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

967

can you make Advice->recordInliningWithCalleeDeleted happen in this case, too?

[nikic]

llvm/lib/Transforms/IPO/Inliner.cpp

967

I'm not sure that would be the right modelling. I believe the reasoning here is that even if we drop a linkonce_odr function in this module, there may be many other modules that also define the same function. It will only be really deleted if it is deleted from *all* modules. Otherwise dropping it in just one module has no effect after linking. I think this is why the inlining cost model does not apply the last call to local to linkonce_odr functions. And I would expect that the advisor would follow similar reasoning.

[mtrofin]

llvm/lib/Transforms/IPO/Inliner.cpp

967

It would hint to the ML Advisor (during training) that it did "a good thing" because, locally, at this module level, we did the best we could have for such a function (i.e. deleted it). But we can try this first ourselves and see if it significantly helps or not.

[jyknight]

This seems to cause a reproducible infinite loop inside the inliner on some inputs. I haven't narrowed down a repro case yet, but I'm going to revert this in the meantime.

[aeubanks]

I looked at the repro and I think that this is slowing down specific compiles a lot rather than hanging indefinitely. Taking a closer look.

[aeubanks]

a flame graph shows that removeDeadConstantUsers() is taking up almost half of the compile time in the repro

[nikic]

In D115545#3241068, @aeubanks wrote:

a flame graph shows that removeDeadConstantUsers() is taking up almost half of the compile time in the repro

Switching to hasOneLiveUse() instead should avoid that, as it will short-circuit.

llvm/lib/Transforms/IPO/Inliner.cpp

PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   // with all of their edges in the call graph before pruning out the ones that
   // got simplified away.
   SmallSetVector<Function *, 4> InlinedCallees;
 
   // Track the dead functions to delete once finished with inlining calls. We
   // defer deleting these to make it easier to handle the call graph updates.
   SmallVector<Function *, 4> DeadFunctions;
 
+  // Track potentially dead non-local functions with comdats to see if they can
+  // be deleted as a batch after inlining.
+  SmallVector<Function *, 4> DeadFunctionsInComdats;
+
   // Loop forward over all of the calls.
   while (!Calls->empty()) {
     // We expect the calls to typically be batched with sequences of calls that
     // have the same caller, so we first set up some shared infrastructure for
     // this caller. We also do any pruning we can at this layer on the caller
     // alone.
     Function &F = *Calls->front().first->getCaller();
     LazyCallGraph::Node &N = *CG.lookup(F);
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
             if (!NewCallee->isDeclaration())
               Calls->push({ICB, NewHistoryID});
         }
       }
 
       // Merge the attributes based on the inlining.
       AttributeFuncs::mergeAttributesForInlining(F, Callee);
 
-      // For local functions, check whether this makes the callee trivially
-      // dead. In that case, we can drop the body of the function eagerly
-      // which may reduce the number of callers of other functions to one,
-      // changing inline cost thresholds.
+      // For local functions or discardable functions without comdats, check
+      // whether this makes the callee trivially dead. In that case, we can drop
+      // the body of the function eagerly which may reduce the number of callers
+      // of other functions to one, changing inline cost thresholds. Non-local
+      // discardable functions with comdats are checked later on.
       bool CalleeWasDeleted = false;
-      if (Callee.hasLocalLinkage()) {
+      if (Callee.isDiscardableIfUnused()) {
         // To check this we also need to nuke any dead constant uses (perhaps
         // made dead by this operation on other functions).
         Callee.removeDeadConstantUsers();
         if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
+          if (Callee.hasLocalLinkage() || !Callee.hasComdat()) {
             Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
               return Call.first->getCaller() == &Callee;
             });
             // Clear the body and queue the function itself for deletion when we
             // finish inlining and call graph updates.
             // Note that after this point, it is an error to do anything other
             // than use the callee's address or delete it.
             Callee.dropAllReferences();
             assert(!is_contained(DeadFunctions, &Callee) &&
                    "Cannot put cause a function to become dead twice!");
             DeadFunctions.push_back(&Callee);
             CalleeWasDeleted = true;
+          } else {
+            DeadFunctionsInComdats.push_back(&Callee);
+          }
         }
       }
       if (CalleeWasDeleted)
         Advice->recordInliningWithCalleeDeleted();
       else
         Advice->recordInlining();
     }
 
while (!Calls->empty()) {
     }
     InlinedCallees.clear();
 
     // Invalidate analyses for this function now so that we don't have to
     // invalidate analyses for all functions in this SCC later.
     FAM.invalidate(F, PreservedAnalyses::none());
   }
 
+  // We must ensure that we only delete functions with comdats if every function
+  // in the comdat is going to be deleted.
+  if (!DeadFunctionsInComdats.empty()) {
+    filterDeadComdatFunctions(*DeadFunctionsInComdats[0]->getParent(),
+                              DeadFunctionsInComdats);
+    for (auto *Callee : DeadFunctionsInComdats)
+      Callee->dropAllReferences();
+    DeadFunctions.append(DeadFunctionsInComdats);
+  }
+
   // Now that we've finished inlining all of the calls across this SCC, delete
   // all of the trivially dead functions, updating the call graph and the CGSCC
   // pass manager in the process.
   //
   // Note that this walks a pointer set which has non-deterministic order but
   // that is OK as all we do is delete things and add pointers to unordered
   // sets.
   for (Function *DeadF : DeadFunctions) {

llvm/test/Transforms/Inline/delete-unused-function.ll

+; RUN: opt -passes=inline < %s -S | FileCheck %s
+
+; CHECK: define {{.*}}@caller
+; CHECK: define {{.*}}@f1
+; CHECK-NOT: define {{.*}}@f2
+; CHECK-NOT: define {{.*}}@f3
+; CHECK-NOT: define {{.*}}@f4
+; CHECK-NOT: define {{.*}}@f5
+; CHECK: define {{.*}}@f6
+; CHECK-NOT: define {{.*}}@f7
+; CHECK-NOT: define {{.*}}@f8
+
+$c1 = comdat any
+$c2 = comdat any
+$c3 = comdat any
+
+define void @caller() {
+  call void @f1()
+  call void @f2()
+  call void @f3()
+  call void @f4()
+  call void @f5()
+  call void @f6()
+  call void @f7()
+  call void @f8()
+  ret void
+}
+
+define void @f1() {
+  ret void
+}
+
+define internal void @f2() {
+  ret void
+}
+
+define private void @f3() {
+  ret void
+}
+
+define linkonce_odr void @f4() {
+  ret void
+}
+
+define linkonce_odr void @f5() comdat($c1) {
+  ret void
+}
+
+define linkonce_odr void @f6() comdat($c2) {
+  ret void
+}
+
+define linkonce_odr void @g() comdat($c2) {
+  ret void
+}
+
+define linkonce_odr void @f7() comdat($c3) {
+  ret void
+}
+
+define linkonce_odr void @f8() comdat($c3) {
+  ret void
+}

llvm/test/Transforms/LoopUnroll/2011-08-09-PhiUpdate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S < %s -instcombine -inline -jump-threading -loop-unroll -unroll-count=4 | FileCheck %s
 ;
 ; This is a test case that required a number of setup passes because
 ; it depends on block order.
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-macosx10.6.8"
 
 declare i1 @check() nounwind

 
 return:                                           ; preds = %do.cond, %land.lhs.true, %entry
   %retval.0 = phi i32 [ 0, %entry ], [ %call6, %land.lhs.true ], [ 0, %do.cond ]
   ret i32 %retval.0
 }
 
 define linkonce_odr i32 @bar() nounwind uwtable ssp align 2 {
 ;
-; CHECK-LABEL: @bar(
-; CHECK-NEXT:  land.lhs.true:
-; CHECK-NEXT:    [[CMP4:%.*]] = call zeroext i1 @check()
-; CHECK-NEXT:    br i1 [[CMP4]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
-; CHECK:       cond.true:
-; CHECK-NEXT:    [[TMP7:%.*]] = call i32 @getval()
-; CHECK-NEXT:    br label [[COND_END]]
-; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP7]], [[COND_TRUE]] ], [ 0, [[LAND_LHS_TRUE:%.*]] ]
-; CHECK-NEXT:    ret i32 [[COND]]
-;
 entry:
   br i1 undef, label %land.lhs.true, label %cond.end
 
 land.lhs.true:                                    ; preds = %entry
   %cmp4 = call zeroext i1 @check()
   br i1 %cmp4, label %cond.true, label %cond.end
 
 cond.true:                                        ; preds = %land.lhs.true
   %tmp7 = call i32 @getval()
   br label %cond.end
 
 cond.end:                                         ; preds = %cond.true, %land.lhs.true, %entry
   %cond = phi i32 [ %tmp7, %cond.true ], [ 0, %land.lhs.true ], [ 0, %entry ]
   ret i32 %cond
 }