[thinlto] Add cold-callsite import heuristic

[Prazek]

Summary

Not tunned up heuristic, but with this small heuristic there is about
+0.10% improvement on SPEC 2006

[Prazek]

Small typos

[mehdi_amini]

Not tunned up heuristic, but with this small heuristic there is about +0.10% improvement on SPEC 2006

This is not clear to me: I would expect only a compile time impact on this, why is there a perf improvement?

lib/Transforms/IPO/FunctionImport.cpp

64

ZeroOrMore? Why isn't the default fine?

305

Too many nested ternary operator IMO (I think more than one hurt readability in general).

[eraman]

How does this result in improved performance? If the

In D24940#553322, @mehdi_amini wrote:

Not tunned up heuristic, but with this small heuristic there is about +0.10% improvement on SPEC 2006

This is not clear to me: I would expect only a compile time impact on this, why is there a perf improvement?

The inliner and the importer use a different metric to determine what is cold: the importer uses the ProfleSummaryInfo while the inliner checks if the entry count is less than a fraction of max_entry_count (the inliner's code is the one that needs to change, but that's dependent on porting inliner to the new PM) This would explain the performance improvement (inliner normally inlines functions that are considered cold as determined by PSI.isColdCount() but prevented from doing so if they aren't imported). If we were to fix the inliner first, then this change should be nop in terms of performance.

[Prazek]

In D24940#553351, @eraman wrote:

How does this result in improved performance? If the

In D24940#553322, @mehdi_amini wrote:

Not tunned up heuristic, but with this small heuristic there is about +0.10% improvement on SPEC 2006

This is not clear to me: I would expect only a compile time impact on this, why is there a perf improvement?

The inliner and the importer use a different metric to determine what is cold: the importer uses the ProfleSummaryInfo while the inliner checks if the entry count is less than a fraction of max_entry_count (the inliner's code is the one that needs to change, but that's dependent on porting inliner to the new PM) This would explain the performance improvement (inliner normally inlines functions that are considered cold as determined by PSI.isColdCount() but prevented from doing so if they aren't imported). If we were to fix the inliner first, then this change should be nop in terms of performance.

Well, I think there is another reason - if I won't import function, that is called only from cold block, then it won't gonna be inlined, where the inliner in the trunk doesn't have any heuristic on NOT inlining functions to cold block
(it have heuristic to not inline functions to block ending with unreachable, but it is not connected to PGO). So by not importing some functions I prevent inliner from inlining stuff that it shouldn't.

[tejohnson]

In D24940#554135, @Prazek wrote:

In D24940#553351, @eraman wrote:

How does this result in improved performance? If the

In D24940#553322, @mehdi_amini wrote:

Not tunned up heuristic, but with this small heuristic there is about +0.10% improvement on SPEC 2006

This is not clear to me: I would expect only a compile time impact on this, why is there a perf improvement?

The inliner and the importer use a different metric to determine what is cold: the importer uses the ProfleSummaryInfo while the inliner checks if the entry count is less than a fraction of max_entry_count (the inliner's code is the one that needs to change, but that's dependent on porting inliner to the new PM) This would explain the performance improvement (inliner normally inlines functions that are considered cold as determined by PSI.isColdCount() but prevented from doing so if they aren't imported). If we were to fix the inliner first, then this change should be nop in terms of performance.

Well, I think there is another reason - if I won't import function, that is called only from cold block, then it won't gonna be inlined, where the inliner in the trunk doesn't have any heuristic on NOT inlining functions to cold block
(it have heuristic to not inline functions to block ending with unreachable, but it is not connected to PGO). So by not importing some functions I prevent inliner from inlining stuff that it shouldn't.

It is possible, but realistically 0.10% improvement is not enough to draw any strong conclusions.

Overall looks fine, will re-review when you've addressed Mehdi's comments.

[Prazek]

nits

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

305

I was trying to avoid using not const variable here because the scope is very big. Maybe I shoudl use lambda?

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

305

Oh I see why you did it. Maybe a static function close to the cl::opt?

const float BonusMultiplier = getBonusMultiplierForHotness(Edge.second.Hotness);

(Straw man naming)

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

305

what about

auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) {
    if (Hotness == CalleeInfo::HotnessType::Hot)
      return ImportHotMultiplier;
    if (Hotness == CalleeInfo::HotnessType::Cold)
      return ImportColdMultiplier;
    return 1.0;
  };
  
  const auto NewThreshold = Threshold * GetBonusMultiplier(Edge.second.Hotness);

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

305

That's fine with me.

(I wouldn't use a lambda as there is not much value seeing this boilerplate when reading this loop body, but I don't mind if you prefer it).

[Prazek]

lambda

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

305

I prefere lambda because it has smaller scope as function, and you don't have to jump in the file to read 5 simple lines.
So I will stay with it.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

305

I agree... when there is an actual value to read these lines! Otherwise apply this principles means inlining the whole program as nested lambda into the main() :p
So it is always a signal/noise ratio evaluation. Having a lambda means the code is available, but it means the body of the current function is longer.
(Here I felt I can read and understand the code in the loop without the need to see the body of a function with a name GetBonusMultiplier)

[Prazek]

lib/Transforms/IPO/FunctionImport.cpp

305

The boilerplate is actually not that big, there is actually one line more (because I would have to declare a variable to store result ).

I guess the real question is, should I hide implementation or not, because wrapping in the function/lambda is clearly win.

So if you think that function will be better then I will change it because both works for me, and I want to push it upstream before I will finish internship (Friday)

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

305

I don't think it makes much of a difference here, this is why I mentioned before either way is fine, pick your favorite.
I'm fine continuing bike-shedding this though :)

I can't believe your internship is already done, time flies...

[mehdi_amini]

test/Transforms/FunctionImport/hotness_based_import.ll

32

If this test passes, I think there's something wrong (the prefix is the same as the previous one...)

lib/Transforms/IPO/FunctionImport.cpp

static cl::opt<unsigned> ImportInstrLimit(
     cl::desc("Only import functions with less than N instructions"));
 
 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> ImportHotMultiplier(
     "import-hot-multiplier", cl::init(3.0), cl::Hidden, cl::value_desc("x"),
-    cl::ZeroOrMore, cl::desc("Multiply the `import-instr-limit` threshold for "
-                             "hot callsites"));
+    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"));
 
 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
                                   cl::desc("Print imported functions"));
 
 // Temporary allows the function import pass to disable always linking
 // referenced discardable symbols.
 static cl::opt<bool>
     DontForceImportReferencedDiscardableSymbols("disable-force-link-odr",
                                                 cl::init(false), cl::Hidden);
 
 static cl::opt<bool> EnableImportMetadata(
     "enable-import-metadata", cl::init(
 #if !defined(NDEBUG)
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;
     }
 
-    // FIXME: Also lower the threshold for cold callsites.
+    auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
+      if (Hotness == CalleeInfo::HotnessType::Hot)
+        return ImportHotMultiplier;
+      if (Hotness == CalleeInfo::HotnessType::Cold)
+        return ImportColdMultiplier;
+      return 1.0;
+    };
+
     const auto NewThreshold =
-        Edge.second.Hotness == CalleeInfo::HotnessType::Hot
-            ? Threshold * ImportHotMultiplier
-            : Threshold;
+        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)) {
       ResolvedCalleeSummary = cast<FunctionSummary>(
           &cast<AliasSummary>(CalleeSummary)->getAliasee());
       assert(

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-cold-multiplier=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 @cold()
 ; 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()
 
 
 ; 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 @cold()
 ; 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()
 ; HOT-ONE-NOT: define available_externally void @none2()
 ; HOT-ONE-NOT: define available_externally void @none3()
 ; HOT-ONE-NOT: define available_externally void @cold2()
 
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=1 -import-hot-multiplier=1.0 -import-cold-multiplier=1.0 --S | FileCheck %s --check-prefix=CHECK --check-prefix=HOT-ONE
+; HOT-COLD-ONE-DAG: define available_externally void @hot1()
+; HOT-COLD-ONE-DAG: define available_externally void @cold()
+; HOT-COLD-ONE-DAG: define available_externally void @none1()
+; HOT-COLD-ONE-NOT: define available_externally void @hot2()
+; HOT-COLD-ONE-NOT: define available_externally void @hot3()
+; HOT-COLD-ONE-NOT: define available_externally void @none2()
+; HOT-COLD-ONE-NOT: define available_externally void @none3()
+; HOT-COLD-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.
-; 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
+; 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-NOT: define available_externally void @hot2()
 ; HOT-ZERO-NOT: define available_externally void @hot1()
 ; HOT-ZERO-NOT: define available_externally void @hot3()