[thinlto] Don't decay threshold for hot callsites

[Prazek]

Summary

We don't want to decay hot callsites to import chains of hot
callsites. The same mechanism is used in LIPO.

[Prazek]

deleted debug

[tejohnson]

(As discussed offline, Piotr will test on SPEC and get back with performance data).

test/Transforms/FunctionImport/hotness_based_import.ll

38

Comment doesn't make much sense - we are checking that they aren't imported.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

385

I rather express this differently: using different factors for the hotness.
(You current proposal would be using 1 as a factor for "hot" calls chains).

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

385

ok I will add different Factor

test/Transforms/FunctionImport/hotness_based_import.ll

38

oh yea, I forgot to remove this.

[Prazek]

fixes

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

344

As mentioned in D24638, you could achieve the same result by adjusting the Threshold when pushing on the stack instead of passing more context to the next iteration and delaying the adjustment.

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

344

just to make sure - you want to apply the threshold: lines

if (IsHotCallsite)
    Threshold = Threshold * ImportHotInstrFactor;
else
    Threshold = Threshold * ImportInstrFactor;

here, and don't do any threshold changes in the while loop? (So worklist will only contain FunctionSummary - because threshold and my bool won't be needed)

If so, then it seems like a good idea!

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

344

Right: doing all the threshold management at the same place.

[Prazek]

I have some initial results. It looks like because inliner doesn't know how to inline hot callsites, then most of the SPEC benchmarks have the same binary as current trunk (with hot heuristic).
But on the google branch with smarter inliner there is clear win in povray, about +0.5% compared to current trunk with hot heuristic, over all other benchmarks that produced different binary are not much different.

So the question is - should I temporary set the hot-evolution-factor to the same as normal evolution factor? So this way We won't import more functions that inliner won't inline, and then when new inliner will make it to trunk, to switch it to 1.0

[Prazek]

moved calculating threshold

[tejohnson]

In D24976#556151, @Prazek wrote:

I have some initial results. It looks like because inliner doesn't know how to inline hot callsites, then most of the SPEC benchmarks have the same binary as current trunk (with hot heuristic).
But on the google branch with smarter inliner there is clear win in povray, about +0.5% compared to current trunk with hot heuristic, over all other benchmarks that produced different binary are not much different.

So the question is - should I temporary set the hot-evolution-factor to the same as normal evolution factor? So this way We won't import more functions that inliner won't inline, and then when new inliner will make it to trunk, to switch it to 1.0

Can you enable your importing stats to see how many extra funcs we import in trunk?

lib/Transforms/IPO/FunctionImport.cpp

268–269

Change not needed now

289

These few lines no longer need changing

376–377

No need to change these lines, just remove the threshold adjustment (makes the actual functional change clearer without other changes).

[mehdi_amini]

So the question is - should I temporary set the hot-evolution-factor to the same as normal evolution factor? So this way We won't import more functions that inliner won't inline, and then when new inliner will make it to trunk, to switch it to 1.0

I'm fine designing the importer independently knowing that the inliner will be updated at some point to match, even if it means that in the meantime we import more than necessary when PGO is enabled.

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

289

I think they need: I am ussing isHotCallsite later, and it also makes code cleaner

[Prazek]

Addressed Teresa comments

[Prazek]

In D24976#556227, @tejohnson wrote:

In D24976#556151, @Prazek wrote:

I have some initial results. It looks like because inliner doesn't know how to inline hot callsites, then most of the SPEC benchmarks have the same binary as current trunk (with hot heuristic).
But on the google branch with smarter inliner there is clear win in povray, about +0.5% compared to current trunk with hot heuristic, over all other benchmarks that produced different binary are not much different.

So the question is - should I temporary set the hot-evolution-factor to the same as normal evolution factor? So this way We won't import more functions that inliner won't inline, and then when new inliner will make it to trunk, to switch it to 1.0

Can you enable your importing stats to see how many extra funcs we import in trunk?

These are the numbers of imported functions for povray
trunk_without_hot trunk trunk_hot_chaians
1738 1863 1876

So we import 13 functions more. This is kinda expected, there should not be many hot chains

lib/Transforms/IPO/FunctionImport.cpp

for (auto &Ref : GVS->refs()) {
     auto GUID = Ref.getGUID();
     auto *RefSummary = FindGlobalSummaryInModule(GUID);
     if (RefSummary)
       // Found a ref in the current module, mark it as exported
       ExportList.insert(GUID);
   }
 }
 
-using EdgeInfo = std::pair<const FunctionSummary *, unsigned /* Threshold */>;
+using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
+    bool /* CalledFromHotBlock */>;
 
 /// Compute the list of functions to import for a given caller. Mark these
 /// imported functions and the symbols they reference in their source module as
 /// exported from their source module.
 static void computeImportForFunction(
     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
   for (auto &Edge : Summary.calls()) {
     auto GUID = Edge.first.getGUID();
     DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n");
 
     if (DefinedGVSummaries.count(GUID)) {
       DEBUG(dbgs() << "ignored! Target already in destination module.\n");
       continue;
     }
 
+    const bool IsHotCallsite = Edge.second.Hotness == CalleeInfo::HotnessType::Hot;
     // FIXME: Also lower the threshold for cold callsites.
     const auto NewThreshold =
-        Edge.second.Hotness == CalleeInfo::HotnessType::Hot
+        IsHotCallsite
             ? Threshold * ImportHotMultiplier
             : Threshold;
     auto *CalleeSummary = selectCallee(GUID, NewThreshold, Index);
     if (!CalleeSummary) {
       DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
       continue;
     }
     // "Resolve" the summary, traversing alias,
if (ExportLists) {
       }
       for (auto &Ref : ResolvedCalleeSummary->refs()) {
         auto GUID = Ref.getGUID();
         exportGlobalInModule(Index, ExportModulePath, GUID, ExportList);
       }
     }
 
     // Insert the newly imported function to the worklist.
-    Worklist.push_back(std::make_pair(ResolvedCalleeSummary, Threshold));
+    Worklist.emplace_back(ResolvedCalleeSummary, Threshold, IsHotCallsite);
   }
 }
 
 /// Given the list of globals defined in a module, compute the list of imports
 /// as well as the list of "exports", i.e. the list of symbols referenced from
 /// another module (that may require promotion).
 static void ComputeImportForModule(
     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
if (!FuncSummary)
       // Skip import for global variables
       continue;
     DEBUG(dbgs() << "Initalize import for " << GVSummary.first << "\n");
     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
                              DefinedGVSummaries, Worklist, ImportList,
                              ExportLists);
   }
 
-  while (!Worklist.empty()) {
-    auto FuncInfo = Worklist.pop_back_val();
-    auto *Summary = FuncInfo.first;
-    auto Threshold = FuncInfo.second;
-
-    // Process the newly imported functions and add callees to the worklist.
-    // Adjust the threshold
+  while (!Worklist.empty()) {
+    const FunctionSummary *Summary;
+    unsigned Threshold;
+    bool IsHotCallsite;
+    std::tie(Summary, Threshold, IsHotCallsite) = Worklist.pop_back_val();
+
+    // Adjust the threshold only for non-hot callsites. We don't do it for hot
+    // callsites because we can then inline chain of hot calls.
+    if (!IsHotCallsite)
       Threshold = Threshold * ImportInstrFactor;
-
     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
                              Worklist, ImportList, ExportLists);
   }
 }
 
 } // anonymous namespace
 
 /// Compute all the import and export for every module using the Index.

test/Transforms/FunctionImport/Inputs/hotness_based_import.ll

 ; ModuleID = 'thinlto-function-summary-callgraph-profile-summary2.ll'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 
 define void @hot1() #1 {
   ret void
 }
-define void @hot2() #1 {
-  call void @externalFunction()
-  call void @externalFunction()
+define void @hot2() #1 !prof !20  {
+  call void @calledFromHot()
+  call void @calledFromHot()
   ret void
 }
-define void @hot3() #1 {
-  call void @externalFunction()
-  call void @externalFunction()
-  call void @externalFunction()
+define void @hot3() #1 !prof !20 {
+  call void @calledFromHot()
+  call void @calledFromHot()
+  call void @calledFromHot()
   ret void
 }
-define void @cold() #1 {
+define void @cold() #1 !prof !0 {
   ret void
 }
-define void @cold2() #1 {
-  call void @externalFunction()
-  call void @externalFunction()
+define void @cold2() #1 !prof !0  {
+  call void @calledFromHot()
+  call void @calledFromHot()
   ret void
 }
 
 define void @none1() #1 {
   ret void
 }
+
 define void @none2() #1 {
-  call void @externalFunction()
+  call void @calledFromHot()
   ret void
 }
 define void @none3() #1 {
-  call void @externalFunction()
-  call void @externalFunction()
+  call void @calledFromHot()
+  call void @calledFromHot()
+  ret void
+}
+
+define void @calledFromCold() {
+  ret void
+}
+
+define void @calledFromHot() !prof !20 {
+  call void @calledFromHot2()
+  ret void
+}
+
+define void @calledFromHot2() {
+  call void @calledFromHot3()
   ret void
 }
 
+declare void @calledFromHot3()
+
+!0 = !{!"function_entry_count", i64 1}
+!20 = !{!"function_entry_count", i64 110}
+
+!llvm.module.flags = !{!1}
 
-declare void @externalFunction()
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 10}
+!6 = !{!"MaxInternalCount", i64 1}
+!7 = !{!"MaxFunctionCount", i64 1000}
+!8 = !{!"NumCounts", i64 3}
+!9 = !{!"NumFunctions", i64 3}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13, !14}
+!12 = !{i32 10000, i64 100, i32 1}
+!13 = !{i32 999000, i64 100, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}
 No newline at end of file

test/Transforms/FunctionImport/hotness_based_import.ll

 ; Test to check the callgraph in summary when there is PGO
 ; RUN: opt -module-summary %s -o %t.bc
 ; RUN: opt -module-summary %p/Inputs/hotness_based_import.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Test import with default hot multiplier (3)
 ; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 --S | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-DEFAULT
 ; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 --S -import-hot-multiplier=3.0 | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-DEFAULT
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 --S -import-hot-multiplier=3.0 -import-instr-evolution-factor=0.0 | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-DEFAULT
 ; HOT-DEFAULT-DAG: define available_externally void @hot1()
 ; HOT-DEFAULT-DAG: define available_externally void @hot2()
+; HOT-DEFAULT-DAG: define available_externally void @calledFromHot()
+; HOT-DEFAULT-DAG: define available_externally void @calledFromHot2()
 ; HOT-DEFAULT-DAG: define available_externally void @cold()
 ; HOT-DEFAULT-DAG: define available_externally void @none1()
 
 ; HOT-DEFAULT-NOT: define available_externally void @hot3()
 ; HOT-DEFAULT-NOT: define available_externally void @none2()
 ; HOT-DEFAULT-NOT: define available_externally void @none3()
 ; HOT-DEFAULT-NOT: define available_externally void @cold2()
 
 
 ; Test import with hot multiplier 1.0 - treat hot callsites as normal.
 ; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 -import-hot-multiplier=1.0 --S | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-ONE
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 -import-hot-multiplier=1.0 --S | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-ONE
 ; HOT-ONE-DAG: define available_externally void @hot1()
 ; HOT-ONE-DAG: define available_externally void @cold()
 ; HOT-ONE-DAG: define available_externally void @none1()
 ; HOT-ONE-NOT: define available_externally void @hot2()
 ; HOT-ONE-NOT: define available_externally void @hot3()
 ; HOT-ONE-NOT: define available_externally void @none2()
 ; HOT-ONE-NOT: define available_externally void @none3()
 ; HOT-ONE-NOT: define available_externally void @cold2()
 
 
 ; Test import with hot multiplier 0.0 and high threshold - don't import functions called from hot callsite.
+; for hot callsites the threshold doesn't decay, that's why it doesn't make difference if the import factor
+; is 0 or higher - calledFromHot's will be imported
 ; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=10 -import-hot-multiplier=0.0 --S | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-ZERO
 ; HOT-ZERO-DAG: define available_externally void @cold()
 ; HOT-ZERO-DAG: define available_externally void @none1()
 ; HOT-ZERO-DAG: define available_externally void @none2()
 ; HOT-ZERO-DAG: define available_externally void @none3()
 ; HOT-ZERO-DAG: define available_externally void @cold2()
 ; HOT-ZERO-NOT: define available_externally void @hot2()
 ; HOT-ZERO-NOT: define available_externally void @hot1()
 ; HOT-ZERO-NOT: define available_externally void @hot3()
-
+; HOT-ZERO-NOT: define available_externally void @calledFromHot()
+; HOT-ZERO-NOT: define available_externally void @calledFromHot2()
 
 
 ; ModuleID = 'thinlto-function-summary-callgraph.ll'
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; This function have high profile count, so entry block is hot.
 define void @hot_function(i1 %a, i1 %a2) !prof !20 {