[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 ↗

(On Diff #72687)

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

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

385 ↗

(On Diff #72687)

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 ↗

(On Diff #72687)

ok I will add different Factor

test/Transforms/FunctionImport/hotness_based_import.ll

38 ↗

(On Diff #72687)

oh yea, I forgot to remove this.

[Prazek]

fixes

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

350 ↗

(On Diff #72706)

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

350 ↗

(On Diff #72706)

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

350 ↗

(On Diff #72706)

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

275 ↗

(On Diff #72922)

Change not needed now

295 ↗

(On Diff #72922)

These few lines no longer need changing

391 ↗

(On Diff #72922)

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

295 ↗

(On Diff #72922)

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

llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp

 
 static cl::opt<float>
     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
                       cl::Hidden, cl::value_desc("x"),
                       cl::desc("As we import functions, multiply the "
                                "`import-instr-limit` threshold by this factor "
                                "before processing newly imported functions"));
 
+static cl::opt<float> ImportHotInstrFactor(
+    "import-hot-evolution-factor", cl::init(1.0), cl::Hidden,
+    cl::value_desc("x"),
+    cl::desc("As we import functions called from hot callsite, multiply the "
+             "`import-instr-limit` threshold by this factor "
+             "before processing newly imported functions"));
+
 static cl::opt<float> ImportHotMultiplier(
     "import-hot-multiplier", cl::init(3.0), cl::Hidden, cl::value_desc("x"),
     cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
 
 // FIXME: This multiplier was not really tuned up.
 static cl::opt<float> ImportColdMultiplier(
     "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
     cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
         return ImportHotMultiplier;
       if (Hotness == CalleeInfo::HotnessType::Cold)
         return ImportColdMultiplier;
       return 1.0;
     };
 
     const auto NewThreshold =
         Threshold * GetBonusMultiplier(Edge.second.Hotness);
+
     auto *CalleeSummary = selectCallee(GUID, NewThreshold, Index);
     if (!CalleeSummary) {
       DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
       continue;
     }
     // "Resolve" the summary, traversing alias,
     const FunctionSummary *ResolvedCalleeSummary;
     if (isa<AliasSummary>(CalleeSummary)) {
if (ExportLists) {
         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;
+    };
+
+    bool IsHotCallsite = Edge.second.Hotness == CalleeInfo::HotnessType::Hot;
+
     // Insert the newly imported function to the worklist.
-    Worklist.push_back(std::make_pair(ResolvedCalleeSummary, Threshold));
+    Worklist.emplace_back(ResolvedCalleeSummary,
+                          GetAdjustedThreshold(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);
   }
 
+  // Process the newly imported functions and add callees to the worklist.
   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
-    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.

llvm/trunk/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 @calledFromCold()
+  call void @calledFromCold()
   ret void
 }
 
 define void @none1() #1 {
   ret void
 }
+
 define void @none2() #1 {
-  call void @externalFunction()
+  call void @calledFromNone()
   ret void
 }
 define void @none3() #1 {
-  call void @externalFunction()
-  call void @externalFunction()
+  call void @calledFromNone()
+  call void @calledFromNone()
+  ret void
+}
+
+define void @calledFromCold() {
   ret void
 }
 
+define void @calledFromHot() !prof !20 {
+  call void @calledFromHot2()
+  ret void
+}
+
+define void @calledFromHot2() !prof !20 {
+  call void @calledFromHot3()
+  ret void
+}
+
+define void @calledFromNone() !prof !0 {
+  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

llvm/trunk/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)
+; Test import with default hot multiplier (3) and default hot-evolution-factor (1.0)
 ; 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 -import-cold-multiplier=0.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 | 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
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 --S -import-hot-multiplier=3.0 -import-hot-evolution-factor=1.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 @none1()
-
 ; HOT-DEFAULT-NOT: define available_externally void @cold()
 ; 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()
+; HOT-DEFAULT-NOT: define available_externally void @calledFromCold()
+; HOT-DEFAULT-NOT: define available_externally void @calledFromNone()
 
+; This one tests if we decay threshold for hot callsites. With hot-evolution-factor of 0
+; we should not import any of calledFromHot functions
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 --S -import-hot-multiplier=3.0 -import-hot-evolution-factor=0.0 | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-EVOLUTION
+; HOT-EVOLUTION-DAG: define available_externally void @hot1()
+; HOT-EVOLUTION-DAG: define available_externally void @hot2()
+; HOT-EVOLUTION-DAG: define available_externally void @none1()
+; HOT-EVOLUTION-NOT: define available_externally void @hot3()
+; HOT-EVOLUTION-NOT: define available_externally void @cold()
+; HOT-EVOLUTION-NOT: define available_externally void @none2()
+; HOT-EVOLUTION-NOT: define available_externally void @none3()
+; HOT-EVOLUTION-NOT: define available_externally void @cold2()
+; HOT-EVOLUTION-NOT: define available_externally void @calledFromHot()
+; HOT-EVOLUTION-NOT: define available_externally void @calledFromHot2()
 
 ; 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
 ; HOT-ONE-DAG: define available_externally void @hot1()
 ; HOT-ONE-DAG: define available_externally void @none1()
 ; HOT-ONE-NOT: define available_externally void @cold()
 ; HOT-ONE-NOT: define available_externally void @hot2()
 ; HOT-ONE-NOT: define available_externally void @hot3()

 
 ; Test import with hot multiplier 0.0 and high threshold - don't import functions called from hot callsite.
 ; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=10 -import-hot-multiplier=0.0 -import-cold-multiplier=1.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-DAG: define available_externally void @calledFromCold()
+; HOT-ZERO-DAG: define available_externally void @calledFromNone()
 ; 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 {