Separate the logic when handling indirect calls in SamplePGO ThinLTO compile phase and other phases.

[danielcdh]

Summary

In SamplePGO ThinLTO compile phase, we will not invoke ICP as it may introduce confusion to the 2nd annotation. This patch extracted that logic and makes it clearer before profile annotation. In the mean time, we need to make function importing process both inlined callsites as well as not promoted indirect callsites.

[danielcdh]

refactor

[tejohnson]

Is this patch NFC? It looks like there is some new handling for indirect call targets in findImportedFunctions that makes it non-NFC. Could you split this into an NFC refactoring patch and a separate non-NFC patch with the enhancements if so? I think that would be clearer and easier to review.

include/llvm/ProfileData/SampleProf.h

342

Needs comment.

include/llvm/Transforms/SampleProfile.h

29

How about IsThinLTOPreLink for consistency with Phase? (Here and in other classes)

lib/Transforms/IPO/SampleProfile.cpp

89

Similar, let's use PreLink instead of Compile, to be consistent with terminology introduced for pass pipeline. After looking at how this is used, it does something different than what I originally thought. I first read this as whether to invoke this pass during the ThinLTO compile/pre-link, but it is actually forcing simulation of being in that phase. So maybe better to have something like "SampleProfileForceThinLTOPreLink" or similar.

I see this is used when invoked via opt. Can the phase be forced instead by using "-passes='thinlto-pre-link<O2>" (see test/Other/new-pm-thinlto-defaults.ll)?

[danielcdh]

In D38094#885238, @tejohnson wrote:

Is this patch NFC? It looks like there is some new handling for indirect call targets in findImportedFunctions that makes it non-NFC. Could you split this into an NFC refactoring patch and a separate non-NFC patch with the enhancements if so? I think that would be clearer and easier to review.

Submitted the NFC change in r314601 and rebased the patch

[danielcdh]

rebase and address Teresa's comments

[tejohnson]

include/llvm/ProfileData/SampleProf.h

343

What is "FS"? Also, the sentence is unclear, partly because there is an "if" with no corresponding "then". Is this handling indirect or direct calls (CallTargets is not documented - could you add a doxygen description to it)? From the comments it sounds like this is looking for additional hot targets that we didn't import/inline in the profiled binary, but might want to now with additional profile data (?)

lib/Transforms/IPO/SampleProfile.cpp

770–806

Suggest reversing the sense of this condition and moving the shorter pre link case up here.

[danielcdh]

update

[tejohnson]

lgtm

include/llvm/ProfileData/SampleProf.h

public:
   /// \p Threshold, add its corresponding GUID to \p S.
   void findImportedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
                              uint64_t Threshold) const {
     if (TotalSamples <= Threshold)
       return;
     Function *F = M->getFunction(Name);
     if (!F || !F->getSubprogram())
       S.insert(Function::getGUID(Name));
+    for (const auto &BS : BodySamples)
+      for (const auto &TS : BS.second.getCallTargets())
+        if (TS.getValue() > Threshold) {
+          Function *Callee = M->getFunction(TS.getKey());
+          if (!Callee || !Callee->getSubprogram())
+            S.insert(Function::getGUID(TS.getKey()));
+        }
     for (auto CS : CallsiteSamples)
       for (const auto &NameFS : CS.second)
         NameFS.second.findImportedFunctions(S, M, Threshold);
   }
 
   /// Set the name of the function.
   void setName(StringRef FunctionName) { Name = FunctionName; }
 

include/llvm/Transforms/SampleProfile.h

 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// The sample profiler data loader pass.
 class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
-  SampleProfileLoaderPass(std::string File = "") : ProfileFileName(File) {}
+  SampleProfileLoaderPass(std::string File = "", bool InThinLTOCompile = false)
+      : ProfileFileName(File), InThinLTOCompile(InThinLTOCompile) {}
 
 private:
   std::string ProfileFileName;
+  bool InThinLTOCompile;
 };
 
 } // End llvm namespace
 #endif

lib/Passes/PassBuilder.cpp

PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   if (PGOOpt && !PGOOpt->SampleProfileFile.empty() &&
       Phase == ThinLTOPhase::PostLink)
     EarlyFPM.addPass(InstCombinePass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(EarlyFPM)));
 
   if (PGOOpt && !PGOOpt->SampleProfileFile.empty()) {
     // Annotate sample profile right after early FPM to ensure freshness of
     // the debug info.
-    MPM.addPass(SampleProfileLoaderPass(PGOOpt->SampleProfileFile));
+    MPM.addPass(SampleProfileLoaderPass(PGOOpt->SampleProfileFile,
+                                        Phase == ThinLTOPhase::PreLink));
     // Do not invoke ICP in the ThinLTOPrelink phase as it makes it hard
     // for the profile annotation to be accurate in the ThinLTO backend.
     if (Phase != ThinLTOPhase::PreLink)
       // We perform early indirect call promotion here, before globalopt.
       // This is important for the ThinLTO backend phase because otherwise
       // imported available_externally functions look unreferenced and are
       // removed.
       MPM.addPass(PGOIndirectCallPromotion(Phase == ThinLTOPhase::PostLink,

lib/Transforms/IPO/SampleProfile.cpp

 static cl::opt<unsigned> SampleProfileSampleCoverage(
     "sample-profile-check-sample-coverage", cl::init(0), cl::value_desc("N"),
     cl::desc("Emit a warning if less than N% of samples in the input profile "
              "are matched to the IR."));
 static cl::opt<double> SampleProfileHotThreshold(
     "sample-profile-inline-hot-threshold", cl::init(0.1), cl::value_desc("N"),
     cl::desc("Inlined functions that account for more than N% of all samples "
              "collected in the parent function, will be inlined again."));
+static cl::opt<bool> SampleProfileInThinLTOCompile(
+    "sample-profile-in-thinlto-compile", cl::init(false), cl::value_desc("N"),
+    cl::desc("Whether the pass is invoked in ThinLTO compile phase. This is "
+             "for testing purpose only."));
 
 namespace {
 typedef DenseMap<const BasicBlock *, uint64_t> BlockWeightMap;
 typedef DenseMap<const BasicBlock *, const BasicBlock *> EquivalenceClassMap;
 typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
 typedef DenseMap<Edge, uint64_t> EdgeWeightMap;
 typedef DenseMap<const BasicBlock *, SmallVector<const BasicBlock *, 8>>
     BlockEdgeMap;

 /// \brief Sample profile pass.
 ///
 /// This pass reads profile data from the file specified by
 /// -sample-profile-file and annotates every affected function with the
 /// profile information found in that file.
 class SampleProfileLoader {
 public:
   SampleProfileLoader(
-      StringRef Name,
+      StringRef Name, bool InThinLTOCompile,
       std::function<AssumptionCache &(Function &)> GetAssumptionCache,
       std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo)
       : DT(nullptr), PDT(nullptr), LI(nullptr), GetAC(GetAssumptionCache),
         GetTTI(GetTargetTransformInfo), Reader(), Samples(nullptr),
-        Filename(Name), ProfileIsValid(false), TotalCollectedSamples(0),
-        ORE(nullptr) {}
+        Filename(Name), ProfileIsValid(false),
+        InThinLTOCompile(InThinLTOCompile || SampleProfileInThinLTOCompile),
+        TotalCollectedSamples(0), ORE(nullptr) {}
 
   bool doInitialization(Module &M);
   bool runOnModule(Module &M, ModuleAnalysisManager *AM);
 
   void dump() { Reader->dump(); }
 
 protected:
   bool runOnFunction(Function &F, ModuleAnalysisManager *AM);
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F);
   ErrorOr<uint64_t> getInstWeight(const Instruction &I);
   ErrorOr<uint64_t> getBlockWeight(const BasicBlock *BB);
   const FunctionSamples *findCalleeFunctionSamples(const Instruction &I) const;
   std::vector<const FunctionSamples *>
   findIndirectCallFunctionSamples(const Instruction &I) const;
   const FunctionSamples *findFunctionSamples(const Instruction &I) const;
+  bool inlineCallInstruction(Instruction *I);
   bool inlineHotFunctions(Function &F,
                           DenseSet<GlobalValue::GUID> &ImportGUIDs);
   void printEdgeWeight(raw_ostream &OS, Edge E);
   void printBlockWeight(raw_ostream &OS, const BasicBlock *BB) const;
   void printBlockEquivalence(raw_ostream &OS, const BasicBlock *BB);
   bool computeBlockWeights(Function &F);
   void findEquivalenceClasses(Function &F);
   template <bool IsPostDom>
protected:
   FunctionSamples *Samples;
 
   /// \brief Name of the profile file to load.
   std::string Filename;
 
   /// \brief Flag indicating whether the profile input loaded successfully.
   bool ProfileIsValid;
 
+  /// \brief Flag indicating if the pass is invoked in ThinLTO compile phase.
+  ///
+  /// In this phase, in annotation, we should not promote indirect calls.
+  /// Instead, we will mark GUIDs that needs to be annotated to the function.
+  bool InThinLTOCompile;
+
   /// \brief Total number of samples collected in this profile.
   ///
   /// This is the sum of all the samples collected in all the functions executed
   /// at runtime.
   uint64_t TotalCollectedSamples;
 
   /// \brief Optimization Remark Emitter used to emit diagnostic remarks.
   OptimizationRemarkEmitter *ORE;
 };
 
 class SampleProfileLoaderLegacyPass : public ModulePass {
 public:
   // Class identification, replacement for typeinfo
   static char ID;
 
-  SampleProfileLoaderLegacyPass(StringRef Name = SampleProfileFile)
-      : ModulePass(ID), SampleLoader(Name,
+  SampleProfileLoaderLegacyPass(StringRef Name = SampleProfileFile,
+                                bool InThinLTOCompile = false)
+      : ModulePass(ID), SampleLoader(Name, InThinLTOCompile,
                                      [&](Function &F) -> AssumptionCache & {
                                        return ACT->getAssumptionCache(F);
                                      },
                                      [&](Function &F) -> TargetTransformInfo & {
                                        return TTIWP->getTTI(F);
                                      }),
         ACT(nullptr), TTIWP(nullptr) {
     initializeSampleProfileLoaderLegacyPassPass(
if (S.size() == 0)
     return Samples;
   const FunctionSamples *FS = Samples;
   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
     FS = FS->findFunctionSamplesAt(S[i].first, S[i].second);
   }
   return FS;
 }
 
+bool SampleProfileLoader::inlineCallInstruction(Instruction *I) {
+  assert(isa<CallInst>(I) || isa<InvokeInst>(I));
+  CallSite CS(I);
+  Function *CalledFunction = CS.getCalledFunction();
+  assert(CalledFunction);
+  DebugLoc DLoc = I->getDebugLoc();
+  BasicBlock *BB = I->getParent();
+  InlineParams Params = getInlineParams();
+  Params.ComputeFullInlineCost = true;
+  // Checks if there is anything in the reachable portion of the callee at
+  // this callsite that makes this inlining potentially illegal. Need to
+  // set ComputeFullInlineCost, otherwise getInlineCost may return early
+  // when cost exceeds threshold without checking all IRs in the callee.
+  // The acutal cost does not matter because we only checks isNever() to
+  // see if it is legal to inline the callsite.
+  InlineCost Cost = getInlineCost(CS, Params, GetTTI(*CalledFunction), GetAC,
+                                  None, nullptr, nullptr);
+  if (Cost.isNever()) {
+    ORE->emit(OptimizationRemark(DEBUG_TYPE, "Not inline", DLoc, BB)
+              << "incompatible inlining");
+    return false;
+  }
+  InlineFunctionInfo IFI(nullptr, &GetAC);
+  if (InlineFunction(CS, IFI)) {
+    // The call to InlineFunction erases I, so we can't pass it here.
+    ORE->emit(OptimizationRemark(DEBUG_TYPE, "HotInline", DLoc, BB)
+              << "inlined hot callee '" << ore::NV("Callee", CalledFunction)
+              << "' into '" << ore::NV("Caller", BB->getParent()) << "'");
+    return true;
+  }
+  return false;
+}
+
 /// \brief Iteratively inline hot callsites of a function.
 ///
 /// Iteratively traverse all callsites of the function \p F, and find if
 /// the corresponding inlined instance exists and is hot in profile. If
 /// it is hot enough, inline the callsites and adds new callsites of the
 /// callee into the caller. If the call is an indirect call, first promote
 /// it to direct call. Each indirect call is limited with a single target.
 ///
for (auto &BB : F) {
             Hot = true;
         }
       }
       if (Hot) {
         CIS.insert(CIS.begin(), Candidates.begin(), Candidates.end());
       }
     }
     for (auto I : CIS) {
-      InlineFunctionInfo IFI(nullptr, &GetAC);
       Function *CalledFunction = CallSite(I).getCalledFunction();
       // Do not inline recursive calls.
       if (CalledFunction == &F)
         continue;
-      Instruction *DI = I;
-      if (!CalledFunction && !PromotedInsns.count(I) &&
-          CallSite(I).isIndirectCall()) {
+      if (CallSite(I).isIndirectCall()) {
+        if (PromotedInsns.count(I))
+          continue;
         for (const auto *FS : findIndirectCallFunctionSamples(*I)) {
+          if (!InThinLTOCompile) {
             auto CalleeFunctionName = FS->getName();
             // If it is a recursive call, we do not inline it as it could bloat
             // the code exponentially. There is way to better handle this, e.g.
             // clone the caller first, and inline the cloned caller if it is
-          // recursive. As llvm does not inline recursive calls, we will simply
-          // ignore it instead of handling it explicitly.
+            // recursive. As llvm does not inline recursive calls, we will
+            // simply ignore it instead of handling it explicitly.
             if (CalleeFunctionName == F.getName())
               continue;
-          const char *Reason = "Callee function not available";
             auto R = SymbolMap.find(CalleeFunctionName);
-          if (R == SymbolMap.end())
-            continue;
+            if (R != SymbolMap.end() && R->getValue() &&
+                !R->getValue()->isDeclaration()) {
+              const char *Reason = "Callee function not available";
               CalledFunction = R->getValue();
-          if (CalledFunction && isLegalToPromote(I, CalledFunction, &Reason)) {
-            // The indirect target was promoted and inlined in the profile, as a
-            // result, we do not have profile info for the branch probability.
-            // We set the probability to 80% taken to indicate that the static
-            // call is likely taken.
-            DI = dyn_cast<Instruction>(
+              if (R->getValue() && R->getValue()->getSubprogram() &&
+                  isLegalToPromote(I, R->getValue(), &Reason)) {
+                // The indirect target was promoted and inlined in the profile,
+                // as a result, we do not have profile info for the branch
+                // probability. We set the probability to 80% taken to indicate
+                // that the static call is likely taken.
+                Instruction *DI = dyn_cast<Instruction>(
                     promoteIndirectCall(I, CalledFunction, 80, 100, false, ORE)
                         ->stripPointerCasts());
                 PromotedInsns.insert(I);
+                // If there is profile mismatch, we should not attempt to inline
+                // DI.
+                if ((isa<CallInst>(DI) || isa<InvokeInst>(DI)) &&
+                    inlineCallInstruction(DI))
+                  LocalChanged = true;
               } else {
-            DEBUG(dbgs() << "\nFailed to promote indirect call to "
-                         << CalleeFunctionName << " because " << Reason
-                         << "\n");
+                DEBUG(dbgs()
+                      << "\nFailed to promote indirect call to "
+                      << CalleeFunctionName << " because " << Reason << "\n");
                 continue;
               }
             }
-        // If there is profile mismatch, we should not attempt to inline DI.
-        if (!isa<CallInst>(DI) && !isa<InvokeInst>(DI))
-          continue;
+          } else {
+            FS->findImportedFunctions(ImportGUIDs, F.getParent(),
+                                      Samples->getTotalSamples() *
+                                          SampleProfileHotThreshold / 100);
           }
-      if (!CalledFunction || !CalledFunction->getSubprogram()) {
-        // Handles functions that are imported from other modules.
-        for (const FunctionSamples *FS : findIndirectCallFunctionSamples(*I))
-          FS->findImportedFunctions(
-              ImportGUIDs, F.getParent(),
-              Samples->getTotalSamples() * SampleProfileHotThreshold / 100);
-        continue;
         }
-      assert(isa<CallInst>(DI) || isa<InvokeInst>(DI));
-      CallSite CS(DI);
-      DebugLoc DLoc = I->getDebugLoc();
-      BasicBlock *BB = I->getParent();
-      InlineParams Params = getInlineParams();
-      Params.ComputeFullInlineCost = true;
-      // Checks if there is anything in the reachable portion of the callee at
-      // this callsite that makes this inlining potentially illegal. Need to
-      // set ComputeFullInlineCost, otherwise getInlineCost may return early
-      // when cost exceeds threshold without checking all IRs in the callee.
-      // The acutal cost does not matter because we only checks isNever() to
-      // see if it is legal to inline the callsite.
-      InlineCost Cost = getInlineCost(CS, Params, GetTTI(*CalledFunction), GetAC,
-                                      None, nullptr, nullptr);
-      if (Cost.isNever()) {
-        ORE->emit(OptimizationRemark(DEBUG_TYPE, "Not inline", DLoc, BB)
-                  << "incompatible inlining");
-        continue;
-      }
-      if (InlineFunction(CS, IFI)) {
+      } else if (CalledFunction && CalledFunction->getSubprogram() &&
+                 !CalledFunction->isDeclaration()) {
+        if (inlineCallInstruction(I))
           LocalChanged = true;
-        // The call to InlineFunction erases DI, so we can't pass it here.
-        ORE->emit(OptimizationRemark(DEBUG_TYPE, "HotInline", DLoc, BB)
-                  << "inlined hot callee '"
-                  << ore::NV("Callee", CalledFunction) << "' into '"
-                  << ore::NV("Caller", &F) << "'");
+      } else if (InThinLTOCompile) {
+        findCalleeFunctionSamples(*I)->findImportedFunctions(
+            ImportGUIDs, F.getParent(),
+            Samples->getTotalSamples() * SampleProfileHotThreshold / 100);
       }
     }
     if (LocalChanged) {
       Changed = true;
     } else {
       break;
     }
   }
PreservedAnalyses SampleProfileLoaderPass::run(Module &M,
 
   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
   auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
     return FAM.getResult<TargetIRAnalysis>(F);
   };
 
-  SampleProfileLoader SampleLoader(ProfileFileName.empty() ? SampleProfileFile
-                                                           : ProfileFileName,
-                                   GetAssumptionCache, GetTTI);
+  SampleProfileLoader SampleLoader(
+      ProfileFileName.empty() ? SampleProfileFile : ProfileFileName,
+      InThinLTOCompile, GetAssumptionCache, GetTTI);
 
   SampleLoader.doInitialization(M);
 
   if (!SampleLoader.runOnModule(M, &AM))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }

test/Transforms/SampleProfile/Inputs/import.prof

 test:10000:0
  3: foo:1000
   3: bar:200
    4: baz:10
  4: foo1:1000
   1: 1000
  4: foo2:1000
-  1: 1000
+  1: 1000 foo3:1000

test/Transforms/SampleProfile/import.ll

-; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/import.prof -S | FileCheck %s
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/import.prof -sample-profile-in-thinlto-compile -S | FileCheck %s
 
 ; Tests whether the functions in the inline stack are added to the
 ; function_entry_count metadata.
 
 declare void @foo()
 
 define void @test(void ()*) !dbg !7 {
   %2 = alloca void ()*
   store void ()* %0, void ()** %2
   %3 = load void ()*, void ()** %2
   ; CHECK: call {{.*}}, !prof ![[PROF:[0-9]+]]
   call void @foo(), !dbg !18
   call void %3(), !dbg !19
   ret void
 }
 
-; GUIDs of foo, bar, foo1 and foo2 should be included in the metadata to make
-; sure hot inline stacks are imported.
-; CHECK: !{!"function_entry_count", i64 1, i64 2494702099028631698, i64 6699318081062747564, i64 7682762345278052905, i64 -2012135647395072713}
+; GUIDs of foo, bar, foo1, foo2 and foo3 should be included in the metadata to
+; make sure hot inline stacks are imported.
+; CHECK: !{!"function_entry_count", i64 1, i64 2494702099028631698, i64 6699318081062747564, i64 7682762345278052905,  i64 -7908226060800700466, i64 -2012135647395072713}
 
 !llvm.dbg.cu = !{!0}
 !llvm.module.flags = !{!8, !9}
 !llvm.ident = !{!10}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, producer: "clang version 3.5 ", isOptimized: false, emissionKind: NoDebug, file: !1, enums: !2, retainedTypes: !2, globals: !2, imports: !2)
 !1 = !DIFile(filename: "calls.cc", directory: ".")
 !2 = !{}