[ThinLTO] Ensure we always select the same function copy to import

[tejohnson]

Summary

Check if the first eligible callee is under the instruction threshold.
Checking this on the first eligible callee ensures that we don't end
up selecting different callees to import when we invoke this routine
with different thresholds due to reaching the callee via paths that
are shallower or hotter (when there are multiple copies, i.e. with
weak or linkonce linkage). We don't want to leave the decision of which
copy to import up to the backend.

[mehdi_amini]

LGTM.

[tejohnson]

Unfortunately I had to revert this in r308206. A ThinLTO bot was failing with a linker undefined reference error:
http://green.lab.llvm.org/green/job/clang-stage2-configure-Rthinlto_build/3663/

It seems unlikely that this heuristic change would directly cause that, but I don't have time to dig into it at the moment. Hopefully it is reproducible with lld or gold (this was ld64 on Darwin). I am not sure if I will have much time to spend looking into it this week, unfortunately.

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

 /// - One from a module already being imported from in order to reduce the
 ///   number of source modules parsed/linked.
 /// - One that has PGO data attached.
 /// - [insert you fancy metric here]
 static const GlobalValueSummary *
 selectCallee(const ModuleSummaryIndex &Index,
              ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
              unsigned Threshold, StringRef CallerModulePath) {
+  // Find the first eligible callee (e.g. legality checks).
   auto It = llvm::find_if(
       CalleeSummaryList,
       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
         auto *GVSummary = SummaryPtr.get();
         if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))
           // There is no point in importing these, we can't inline them
           return false;
         if (auto *AS = dyn_cast<AliasSummary>(GVSummary)) {
auto It = llvm::find_if(
         // entry in the list - in that case this must be a reference due
         // to indirect call profile data, since a function pointer can point to
         // a local in another module.
         if (GlobalValue::isLocalLinkage(Summary->linkage()) &&
             CalleeSummaryList.size() > 1 &&
             Summary->modulePath() != CallerModulePath)
           return false;
 
-        if (Summary->instCount() > Threshold)
-          return false;
-
         if (Summary->notEligibleToImport())
           return false;
 
         return true;
       });
   if (It == CalleeSummaryList.end())
     return nullptr;
 
-  return cast<GlobalValueSummary>(It->get());
+  // Now check if the first eligible callee is under the instruction
+  // threshold. Checking this on the first eligible callee ensures that
+  // we don't end up selecting different callees to import when we invoke
+  // this routine with different thresholds (when there are multiple copies,
+  // i.e. with weak or linkonce linkage).
+  auto *Summary = dyn_cast<FunctionSummary>(It->get());
+  if (auto *AS = dyn_cast<AliasSummary>(It->get()))
+    Summary = cast<FunctionSummary>(&AS->getAliasee());
+  assert(Summary && "Expected FunctionSummary, or alias to one");
+  if (Summary->instCount() > Threshold)
+    return nullptr;
+
+  return Summary;
 }
 
 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
                             GlobalValue::GUID>;
 
 /// 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.

llvm/trunk/test/Transforms/FunctionImport/Inputs/funcimport_resolved1.ll

+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+define void @foo() {
+  call void @linkonceodrfunc()
+  call void @linkonceodrfunc2()
+  ret void
+}
+
+define linkonce_odr void @linkonceodrfunc() {
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  ret void
+}
+
+define linkonce_odr void @linkonceodrfunc2() {
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  call void @f()
+  ret void
+}
+
+define internal void @f() {
+  ret void
+}

llvm/trunk/test/Transforms/FunctionImport/Inputs/funcimport_resolved2.ll

+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.11.0"
+
+define linkonce_odr void @linkonceodrfunc() {
+  ret void
+}

llvm/trunk/test/Transforms/FunctionImport/funcimport_resolved.ll

+; Test to ensure that we always select the same copy of a linkonce function
+; when it is encountered with different thresholds. Initially, we will encounter
+; the copy in funcimport_resolved1.ll with a lower threshold by reaching it
+; from the deeper call chain via foo(), and it won't be selected for importing.
+; Later we encounter it with a higher threshold via the direct call from main()
+; and it will be selected. We don't want to select both the copy from
+; funcimport_resolved1.ll and the smaller one from funcimport_resolved2.ll,
+; leaving it up to the backend to figure out which one to actually import.
+; The linkonce_odr may have different instruction counts in practice due to
+; different inlines in the compile step.
+
+; RUN: opt -module-summary %s -o %t.bc
+; RUN: opt -module-summary %p/Inputs/funcimport_resolved1.ll -o %t2.bc
+; RUN: opt -module-summary %p/Inputs/funcimport_resolved2.ll -o %t3.bc
+
+; First do a sanity check that all callees are imported with the default
+; instruction limit
+; RUN: llvm-lto2 run %t.bc %t2.bc %t3.bc -o %t4 -r=%t.bc,_main,pl -r=%t.bc,_linkonceodrfunc,l -r=%t.bc,_foo,l -r=%t2.bc,_foo,pl -r=%t2.bc,_linkonceodrfunc,pl -r=%t2.bc,_linkonceodrfunc2,pl -r=%t3.bc,_linkonceodrfunc,l -debug-only=function-import 2>&1 | FileCheck %s --check-prefix=INSTLIMDEFAULT
+; INSTLIMDEFAULT-DAG: Is importing function {{.*}} foo from {{.*}}funcimport_resolved1.ll
+; INSTLIMDEFAULT-DAG: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved1.ll
+; INSTLIMDEFAULT-DAG: Is importing function {{.*}} linkonceodrfunc2 from {{.*}}funcimport_resolved1.ll
+; INSTLIMDEFAULT-DAG: Is importing function {{.*}} f from {{.*}}funcimport_resolved1.ll
+
+; Now run with the lower threshold that will only allow linkonceodrfunc to be
+; imported from funcimport_resolved1.ll the second time it is encountered.
+; RUN: llvm-lto2 run %t.bc %t2.bc %t3.bc -o %t4 -r=%t.bc,_main,pl -r=%t.bc,_linkonceodrfunc,l -r=%t.bc,_foo,l -r=%t2.bc,_foo,pl -r=%t2.bc,_linkonceodrfunc,pl -r=%t2.bc,_linkonceodrfunc2,pl -r=%t3.bc,_linkonceodrfunc,l -debug-only=function-import -import-instr-limit=8 2>&1 | FileCheck %s --check-prefix=INSTLIM8
+; INSTLIM8-DAG: Is importing function {{.*}} foo from {{.*}}funcimport_resolved1.ll
+; INSTLIM8-DAG: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved1.ll
+; INSTLIM8-DAG: Not importing function {{.*}} linkonceodrfunc2 from {{.*}}funcimport_resolved1.ll
+; INSTLIM8-DAG: Is importing function {{.*}} f from {{.*}}funcimport_resolved1.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 (...) @foo()
+  call void (...) @linkonceodrfunc()
+  ret i32 0
+}
+
+declare void @foo(...) #1
+declare void @linkonceodrfunc(...) #1