We can improve the performance (generally) by memo-izing the action to map a debug location to its function summary.

[david2050]

Summary

Here are timings (as reported by "opt -time-passes") for
sample-profile pass for some files holding hot functions from a major
service©r. Average 17% reduction. Delta column is 100*(old-new)/old.

Old    New    Delta
0.0537 0.0538 -0.2%
0.8155 0.6522 20.0%
0.0779 0.0751  3.6%
0.0727 0.0913 -25.6%
0.1622 0.1302 19.7%
0.0627 0.0594  5.3%
0.0766 0.0744  2.9%
0.6426 0.4387 31.7%
0.3521 0.2776 21.2%
0.3549 0.2721 23.3%
0.0912 0.0904  0.9%
0.1236 0.1059 14.3%
0.0854 0.0866 -1.4%
0.0757 0.0722  4.6%
0.1293 0.1147 11.3%
0.1354 0.1122 17.1%
0.0767 0.0770 -0.4%
0.1135 0.0968 14.7%
0.0524 0.0608 -16.0%
0.1279 0.1106 13.5%
==========
3.6820 3.0520 17.1% Total

[david2050]

use mutable keyword

[dblaikie]

lib/Transforms/IPO/SampleProfile.cpp

727–733

Perhaps do an unconditional try_emplace and use the bool in the returned pair to decide if the work has already been done or not? This saves two map lookups on the first lookup.

pair<iterator, bool> p = try_emplace(DIL, nullptr);
if (p.second)
  p.first->second = findFunctionSamples(DIL)
return p.first->second;

[david2050]

lib/Transforms/IPO/SampleProfile.cpp

220

Any guidance on the use of mutable v. removing the "const" attributes on the 3 affected method?

727–733

I was uncertain if the iterator was save over the call but will update and in parallel test the change locally.

[david2050]

one hash lookup

[wmi]

Seems the compile time saving is got mainly because there are multiple instructions sharing the same debug location, is my understanding correct?

If the understanding is correct, the memorized mapping seems only useful inside of each function, and is it better to clean the map at the end of runOnFunction instead of holding all the entries for the module?

[wmi]

Seems the compile time saving is got mainly because there are multiple instructions sharing the same debug location, is my understanding correct?

Seems incorrect. findFunctionSamples may be called for the same instruction multiple times due to multiple iterations of hot functions inlining or profile propagation.

But we can still clean up the map at the end of runOnFunction.

[david2050]

clear map for every function

[david2050]

Resetting the function map is a small (< 2%) win

[wmi]

LGTM.

lib/Transforms/IPO/SampleProfile.cpp

public:
   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;
+  const FunctionSamples *findCalleeFunctionSamples(const Instruction &I);
   std::vector<const FunctionSamples *>
-  findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum) const;
-  const FunctionSamples *findFunctionSamples(const Instruction &I) const;
+  findIndirectCallFunctionSamples(const Instruction &I, uint64_t &Sum);
+  DenseMap<const DILocation *, const FunctionSamples *> DILocation2SampleMap;
+  const FunctionSamples *findFunctionSamples(const Instruction &I);
   bool inlineCallInstruction(Instruction *I);
   bool inlineHotFunctions(Function &F,
                           DenseSet<GlobalValue::GUID> &InlinedGUIDs);
   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);

 /// inlined instance in which the call instruction is from, then we
 /// traverse its children to find the callsite with the matching
 /// location.
 ///
 /// \param Inst Call/Invoke instruction to query.
 ///
 /// \returns The FunctionSamples pointer to the inlined instance.
 const FunctionSamples *
-SampleProfileLoader::findCalleeFunctionSamples(const Instruction &Inst) const {
+SampleProfileLoader::findCalleeFunctionSamples(const Instruction &Inst) {
   const DILocation *DIL = Inst.getDebugLoc();
   if (!DIL) {
     return nullptr;
   }
 
   StringRef CalleeName;
   if (const CallInst *CI = dyn_cast<CallInst>(&Inst))
     if (Function *Callee = CI->getCalledFunction())
       CalleeName = Callee->getName();
 
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (FS == nullptr)
     return nullptr;
 
   return FS->findFunctionSamplesAt(LineLocation(FunctionSamples::getOffset(DIL),
                                                 DIL->getBaseDiscriminator()),
                                    CalleeName);
 }
 
 /// Returns a vector of FunctionSamples that are the indirect call targets
 /// of \p Inst. The vector is sorted by the total number of samples. Stores
 /// the total call count of the indirect call in \p Sum.
 std::vector<const FunctionSamples *>
-SampleProfileLoader::findIndirectCallFunctionSamples(
-    const Instruction &Inst, uint64_t &Sum) const {
+SampleProfileLoader::findIndirectCallFunctionSamples(const Instruction &Inst,
+                                                     uint64_t &Sum) {
   const DILocation *DIL = Inst.getDebugLoc();
   std::vector<const FunctionSamples *> R;
 
   if (!DIL) {
     return R;
   }
 
   const FunctionSamples *FS = findFunctionSamples(Inst);

 /// The FunctionSamples of an instruction \p Inst is the inlined instance
 /// in which that instruction is coming from. We traverse the inline stack
 /// of that instruction, and match it with the tree nodes in the profile.
 ///
 /// \param Inst Instruction to query.
 ///
 /// \returns the FunctionSamples pointer to the inlined instance.
 const FunctionSamples *
-SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
+SampleProfileLoader::findFunctionSamples(const Instruction &Inst) {
   SmallVector<std::pair<LineLocation, StringRef>, 10> S;
   const DILocation *DIL = Inst.getDebugLoc();
   if (!DIL)
     return Samples;
-
-  return Samples->findFunctionSamples(DIL);
+  auto it = DILocation2SampleMap.find(DIL);
+  if (it != DILocation2SampleMap.end())
+    return it->second;
+  const FunctionSamples *s = Samples->findFunctionSamples(DIL);
+  DILocation2SampleMap.try_emplace(DIL, s);
+  return s;
 }
 
 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();