[LTO][WPD] Ignore unreachable function by analyzing IR.

[mingmingl]

Summary

In regular LTO, analyze IR and discard unreachable functions when finding virtual call targets.

[mingmingl]

Combine if into &&.

[mingmingl]

Resolve a compile error.

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1051–1052

Since you are adding the IR check above, thinking that to optimize for compile time this lookup should be ignored if we have the def of Fn available (avoids an extra hash table lookup and analysis).

[mingmingl]

Save one index lookup if function def is present for IR analysis. Also simplify test case.

[mingmingl]

thanks for review!

I simplify the test case here, and could do the same for the previous two test cases either here or in a separate patch.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1051–1052

Done by "first analyze function def in IR if that's present, and use export summary as a fallback".

I took the liberty to add a comment like [1]; I'm wondering what's the idiomatic way to provide pointer a line of code w/ commit for reference?

[1]

// FWIW, the writer of `ExportSummary` guarantees that function declarations
  // won't have an entry in `ExportSummary`;
  // see llvm/lib/Analysis/ModuleSummaryAnalysis.cpp#L785 at commit cf9e61a for
  // a reference.

[mingmingl]

remove No newline at end of file by using a different editor

[tejohnson]

lgtm

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1051–1052

That's a good question on code reference. Usually I see references to the file or function granularity, not this specific. However, I don't think it is really needed here. Note on that below.

2110

I don't think this comment is really relevant here. Note you are coming into this part of the handling specifically when we *do* have a function declaration in this module, so it is a little confusing to explain why we don't create a summary for them. The reason why we may have a summary for what is a function decl in this combined regular LTO module is that we have the combined summaries of all of the ThinLTO modules, and the def is in one of those. So I would just keep the first sentence of this comment block ("Learn unreachability from ...").

[mingmingl]

Remove comments on function declarations, as a combined index may contain entries for func declarations.

[mingmingl]

thanks!

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1051–1052

Got it, thanks for the inputs!

2110

The reason why we may have a summary for what is a function decl in this combined regular LTO module is that we have the combined summaries of all of the ThinLTO modules, and the def is in one of those.

I will keep this in mind, thanks for pointing it out!

Removed the comment for function declaration.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

struct DevirtModule {
   bool run();
 
   // Look up the corresponding ValueInfo entry of `TheFn` in `ExportSummary`.
   //
   // Caller guarantees that `ExportSummary` is not nullptr.
   static ValueInfo lookUpFunctionValueInfo(Function *TheFn,
                                            ModuleSummaryIndex *ExportSummary);
 
+  // Returns true if the function definition must be unreachable.
+  //
+  // Note if this helper function returns true, `F` is guaranteed
+  // to be unreachable; if it returns false, `F` might still
+  // be unreachable but not covered by this helper function.
+  //
+  // Implementation-wise, if function definition is present, IR is analyzed; if
+  // not, look up function flags from ExportSummary as a fallback.
+  static bool mustBeUnreachableFunction(Function *const F,
+                                        ModuleSummaryIndex *ExportSummary);
+
   // Lower the module using the action and summary passed as command line
   // arguments. For testing purposes only.
   static bool
   runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
                 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
                 function_ref<DominatorTree &(Function &)> LookupDomTree);
 };
 
if (FunctionsToSkip.match(Fn->getName()))
       return false;
 
     // We can disregard __cxa_pure_virtual as a possible call target, as
     // calls to pure virtuals are UB.
     if (Fn->getName() == "__cxa_pure_virtual")
       continue;
 
     // We can disregard unreachable functions as possible call targets, as
     // unreachable functions shouldn't be called.
-    if (ExportSummary && (mustBeUnreachableFunction(
-                             lookUpFunctionValueInfo(Fn, ExportSummary)))) {
+    if (mustBeUnreachableFunction(Fn, ExportSummary))
       continue;
-    }
 
     TargetsForSlot.push_back({Fn, &TM});
   }
 
   // Give up if we couldn't find any targets.
   return !TargetsForSlot.empty();
 }
 
DevirtModule::lookUpFunctionValueInfo(Function *TheFn,
   // `enable-lto-internalization`.
   // 2. The GUID in ExportedSummary is computed using exported name.
   if ((!TheFnVI) && (TheFnGUID != TheFnGUIDWithExportedName)) {
     TheFnVI = ExportSummary->getValueInfo(TheFnGUIDWithExportedName);
   }
   return TheFnVI;
 }
 
+bool DevirtModule::mustBeUnreachableFunction(
+    Function *const F, ModuleSummaryIndex *ExportSummary) {
+  // First, learn unreachability by analyzing function IR.
+  if (!F->isDeclaration()) {
+    // A function must be unreachable if its entry block ends with an
+    // 'unreachable'.
+    return isa<UnreachableInst>(F->getEntryBlock().getTerminator());
+  }
+  // Learn unreachability from ExportSummary if ExportSummary is present.
+  return ExportSummary &&
+         ::mustBeUnreachableFunction(
+             DevirtModule::lookUpFunctionValueInfo(F, ExportSummary));
+}
+
 bool DevirtModule::run() {
   // If only some of the modules were split, we cannot correctly perform
   // this transformation. We already checked for the presense of type tests
   // with partially split modules during the thin link, and would have emitted
   // an error if any were found, so here we can simply return.
   if ((ExportSummary && ExportSummary->partiallySplitLTOUnits()) ||
       (ImportSummary && ImportSummary->partiallySplitLTOUnits()))
     return false;

llvm/test/Transforms/WholeProgramDevirt/devirt_single_after_filtering_unreachable_function.ll

+; Test that regular LTO will analyze IR, detect unreachable functions and discard unreachable functions
+; when finding virtual call targets.
+; In this test case, the unreachable function is the virtual deleting destructor of an abstract class.
+
+; RUN: opt -S -passes=wholeprogramdevirt -whole-program-visibility -pass-remarks=wholeprogramdevirt %s 2>&1 | FileCheck %s
+
+; CHECK: remark: tmp.cc:21:3: single-impl: devirtualized a call to _ZN7DerivedD0Ev
+; CHECK: remark: <unknown>:0:0: devirtualized _ZN7DerivedD0Ev
+
+source_filename = "tmp.cc"
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%Derived = type { %Base }
+%Base = type { i32 (...)** }
+
+@_ZTV7Derived = constant { [3 x i8*] } { [3 x i8*] [ i8* null, i8* null, i8* bitcast (void (%Derived*)* @_ZN7DerivedD0Ev to i8*)] }, !type !0, !type !1, !type !2, !type !3
+@_ZTV4Base = constant { [3 x i8*] } { [3 x i8*] [ i8* null, i8* null, i8* bitcast (void (%Base*)* @_ZN4BaseD0Ev to i8*)] }, !type !0, !type !1
+
+declare i1 @llvm.type.test(i8*, metadata)
+
+declare void @llvm.assume(i1)
+
+define i32 @func(%Base* %b) {
+entry:
+  %0 = bitcast %Base* %b to void (%Base*)***, !dbg !11
+  %vtable = load void (%Base*)**, void (%Base*)*** %0, !dbg !11
+  %1 = bitcast void (%Base*)** %vtable to i8*, !dbg !11
+  %2 = tail call i1 @llvm.type.test(i8* %1, metadata !"_ZTS4Base"), !dbg !11
+  tail call void @llvm.assume(i1 %2), !dbg !11
+  %vfn = getelementptr inbounds void (%Base*)*, void (%Base*)** %vtable, i64 0, !dbg !11
+  %3 = load void (%Base*)*, void (%Base*)** %vfn, !dbg !11
+  tail call void %3(%Base* %b), !dbg !11
+  ret i32 0
+}
+
+define void @_ZN7DerivedD0Ev(%Derived* %this) {
+entry:
+  ret void
+}
+
+define void @_ZN4BaseD0Ev(%Base* %this) {
+entry:
+  tail call void @llvm.trap()
+  unreachable
+}
+
+declare void @llvm.trap()
+
+!llvm.dbg.cu = !{!5}
+!llvm.module.flags = !{!7}
+
+!0 = !{i64 16, !"_ZTS4Base"}
+!1 = !{i64 32, !"_ZTSM4BaseFvvE.virtual"}
+!2 = !{i64 16, !"_ZTS7Derived"}
+!3 = !{i64 32, !"_ZTSM7DerivedFvvE.virtual"}
+!5 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !6)
+!6 = !DIFile(filename: "tmp.cc", directory: "")
+!7 = !{i32 2, !"Debug Info Version", i32 3}
+!10= distinct !DISubprogram(name: "func", scope: !6, file: !6, unit: !5)
+!11 = !DILocation(line: 21, column: 3, scope: !10)