[ThinLTO] Thin link efficiency improvement: don't re-export globals (NFC)

[tejohnson]

Summary

We were reinvoking exportGlobalInModule numerous times redundantly.
No need to re-export globals referenced by a global that was already
exported in the module. This resulted in a large speedup in the thin
link for a big application, particularly when importing aggressiveness
was cranked up.

[mehdi_amini]

LGTM.
Do you have numbers on the overall improvement on the ThinLink?

[tejohnson]

In D27687#620614, @mehdi_amini wrote:

LGTM.
Do you have numbers on the overall improvement on the ThinLink?

I collected some this morning (see below).

However, I realized last night when I was building past the thin link stage that this patch is not correct. The reason is that the ExportList includes globals that were added because they were imported somewhere (in which case we have already processed their calls/references here and don't need to do it again), as well as those added to the ExportList by exportGlobalInModule (in which case we have not already processed their calls/refs). What we need to do is instead check if this was previously imported from this module, and only then we can skip the marking of its calls/references. I have a new patch I'm about to upload that does just that, and also adds a test that failed with this earlier patch (but not with the new patch).

The numbers were collected on my Xeon, which I tried to keep quiet during the measurements. I measured each 5 times. The baseline was somewhat noisy, but the improved version less so for some reason. With very aggressive importing enabled, this patch improves the thin link time between 3 and 14% (average 8%). With default importing thresholds the average improvement is only 3%.

I looked at this initially because a perf-events profile of the thin link showed that GlobalValueSummary::modulePath() was the hottest routine (it is invoked frequently by exportGloballnModule), and exportGlobalInModule was 7th. With this patch, modulePath() drops to the 2nd hottest and exportGlobalInModule drops to 9th. These were measured with the aggressive importing thresholds.

[tejohnson]

Fix patch and add test that would have caught problem with prior version

[tejohnson]

Mehdi - you lgtm'ed earlier but did you want to take another look since I changed the patch since then?

[mehdi_amini]

In D27687#621385, @tejohnson wrote:

However, I realized last night when I was building past the thin link stage that this patch is not correct. The reason is that the ExportList includes globals that were added because they were imported somewhere (in which case we have already processed their calls/references here and don't need to do it again), as well as those added to the ExportList by exportGlobalInModule (in which case we have not already processed their calls/refs).

Good catch!

I looked at this initially because a perf-events profile of the thin link showed that GlobalValueSummary::modulePath() was the hottest routine (it is invoked frequently by exportGloballnModule), and exportGlobalInModule was 7th.

This sounds suspicious to me: GlobalValueSummary::modulePath() is a simple accessor. For it to be so hot it means it is calls many times *and we're not doing anything with the returned value*.

[mehdi_amini]

(Still LGTM)

[tejohnson]

In D27687#624065, @mehdi_amini wrote:

In D27687#621385, @tejohnson wrote:

However, I realized last night when I was building past the thin link stage that this patch is not correct. The reason is that the ExportList includes globals that were added because they were imported somewhere (in which case we have already processed their calls/references here and don't need to do it again), as well as those added to the ExportList by exportGlobalInModule (in which case we have not already processed their calls/refs).

Good catch!

I looked at this initially because a perf-events profile of the thin link showed that GlobalValueSummary::modulePath() was the hottest routine (it is invoked frequently by exportGloballnModule), and exportGlobalInModule was 7th.

This sounds suspicious to me: GlobalValueSummary::modulePath() is a simple accessor. For it to be so hot it means it is calls many times *and we're not doing anything with the returned value*.

Figured out why - see D27755 (which is complementary to this patch)

[mehdi_amini]

In D27687#624080, @tejohnson wrote:

This sounds suspicious to me: GlobalValueSummary::modulePath() is a simple accessor. For it to be so hot it means it is calls many times *and we're not doing anything with the returned value*.

Figured out why - see D27755 (which is complementary to this patch)

Great!
I'm still quite surprised that the accessor modulePath() is the limit here:

auto SummaryIter = llvm::find_if(
    SummaryList->second,
    [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
      return Summary->modulePath() == ExportModulePath;
    });

I guess it is inlined and the profiler is likely not separating perfectly the body of modulePath() from the context.

lib/Transforms/IPO/FunctionImport.cpp

for (auto &Edge : Summary.calls()) {
     /// Since the traversal of the call graph is DFS, we can revisit a function
     /// a second time with a higher threshold. In this case, it is added back to
     /// the worklist with the new threshold.
     if (ProcessedThreshold && ProcessedThreshold >= Threshold) {
       DEBUG(dbgs() << "ignored! Target was already seen with Threshold "
                    << ProcessedThreshold << "\n");
       continue;
     }
+    bool PreviouslyImported = ProcessedThreshold != 0;
     // Mark this function as imported in this module, with the current Threshold
     ProcessedThreshold = Threshold;
 
     // Make exports in the source module.
     if (ExportLists) {
       auto &ExportList = (*ExportLists)[ExportModulePath];
       ExportList.insert(GUID);
-      // Mark all functions and globals referenced by this function as exported
+      if (!PreviouslyImported) {
+        // This is the first time this function was exported from its source
+        // module, so mark all functions and globals it references as exported
         // to the outside if they are defined in the same source module.
         for (auto &Edge : ResolvedCalleeSummary->calls()) {
           auto CalleeGUID = Edge.first.getGUID();
           exportGlobalInModule(Index, ExportModulePath, CalleeGUID, ExportList);
         }
         for (auto &Ref : ResolvedCalleeSummary->refs()) {
           auto GUID = Ref.getGUID();
           exportGlobalInModule(Index, ExportModulePath, GUID, ExportList);
         }
       }
+    }
 
     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
       // Adjust the threshold for next level of imported functions.
       // The threshold is different for hot callsites because we can then
       // inline chains of hot calls.
       if (IsHotCallsite)
         return Threshold * ImportHotInstrFactor;
       return Threshold * ImportInstrFactor;

test/ThinLTO/X86/Inputs/export.ll

+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+define i32 @main() #0 {
+entry:
+  call void @callstaticfunc()
+  ret i32 0
+}
+
+declare void @callstaticfunc()

test/ThinLTO/X86/export.ll

+; Do setup work for all below tests: generate bitcode and combined index
+; RUN: opt -module-summary %s -o %t1.bc
+; RUN: opt -module-summary %p/Inputs/export.ll -o %t2.bc
+; RUN: llvm-lto -thinlto-action=thinlink -o %t3.bc %t1.bc %t2.bc
+
+; Ensure statics are promoted/renamed correctly from this file.
+; RUN: llvm-lto -thinlto-action=promote %t1.bc -thinlto-index=%t3.bc -o - | llvm-dis -o - | FileCheck %s
+; CHECK-DAG: @staticvar.llvm.0 = hidden global
+; CHECK-DAG: define hidden void @staticfunc.llvm.0
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+@staticvar = internal global i32 1, align 4
+
+define void @callstaticfunc() #0 {
+entry:
+  call void @staticfunc()
+  ret void
+}
+
+define internal void @staticfunc() #0 {
+entry:
+  %0 = load i32, i32* @staticvar, align 4
+  ret void
+}