Change sample profile format to hierarchical using inline stack.

[danielcdh]

Summary

Updates the profile format to support inline stacks, which provides context-senstive information than flat profile.

[danielcdh]

Update documentation of the profile format.

[danielcdh]

clang-format and replace std::string with StringRef

[dnovillo]

include/llvm/ProfileData/SampleProf.h

90

Perhaps make CallsiteLocation inherit from LineLocation? Or embed it. I think inheriting from it may make better sense.

203

Move this typedef below. No need to forward declare FunctionSamples.

248

Too similar to samplesAt(). Merge them?

263

Likewise with functionSamplesAt. Why not allow functionSamplesAt to return an empty FunctionSamples instance? Seems better than dealing with potential segfaults because of the nullptrs.

To avoid unnecessary insertions, we can use ::find() in functionSamplesAt(). Similarly with samplesAt().

Having two functions with almost the same semantics is confusing.

lib/ProfileData/SampleProfReader.cpp

44

Add a short explanation of what the 'inline stack' is.

Also, the user documentation in tools/clang/docs/UsersManual.rst will need to be updated.

188

Can we split this in two changes? The new parsing code is not completely related to the inline stack functionality. While I agree that not using REs may be faster, it's not really something we care about.

Could you modify it so the switch out of RE-based parsing is done in a later patch?

lib/Transforms/IPO/SampleProfile.cpp

301

s/NULL/nullptr/

This happens in several places.

368

Isn't it sufficient to mark these functions as hot or always_inline?

[danielcdh]

Integrate comments.

include/llvm/ProfileData/SampleProf.h

203

You mean move typedef inside the class? But the type is global and other modules actually uses this type.

248

This is a const member function, while samplesAt can modify member variables. Not sure how to merge them?

263

Save as above. Want to make the function as const member function. I will have a separate patch to remove samplesAt sampleRecordAt and functionSamplesAt entirely, leaving only const member funcntions.

lib/ProfileData/SampleProfReader.cpp

44

Updated the document in this file. Will have a separate patch to update the clang doc bits.

188

That is what I initially tried to do. But I need to write new REs for the new profile format (with hierarchical profile format), spent 1+ hour designing REs, and finally gave up. So if we are gonna abandon the RE, then it does not make sense to spend effort to invent new RE for the new format.

lib/Transforms/IPO/SampleProfile.cpp

368

No, we actually need to have inlining done before annotation.

[dnovillo]

include/llvm/ProfileData/SampleProf.h

203

I meant moving it after FunctionSamples's definition, but I now see that it makes no sense. This map is used inside FunctionSamples. Ignore me :)

263

Ah, good. Yeah, your plan makes perfect sense.

lib/ProfileData/SampleProfReader.cpp

44

SGTM.

48

s/tip/top/

50

r/symol in/symbol to/

188

Ah, OK. Yeah, REs are sometimes annoying to define. No worries then. We can refine this later. I've no problems with the code as you wrote it.

lib/Transforms/IPO/SampleProfile.cpp

368

Oh, yes, we discussed this before. The way propagation works now, we need to have the interesting inline decisions applied to align the block weights properly.

I think we will want to revisit this at some point. It would be nice if we can avoid doing the inliner's job here and still deal with the weights properly in the propagator.

Could you add a TODO here? Thanks.

test/Transforms/SampleProfile/Inputs/calls.prof

8

Could you leave the original comment in? Useful for documentation.

test/Transforms/SampleProfile/syntax.ll

8

Hm, not sure about losing this capability of tolerating badly mangled functions. I specifically added this because the optimized binaries sometimes don't have properly mangled symbols. The thinking was to be more tolerant of this.

See the comment in SampleProfileReaderText::read(). If we are really going to not tolerate this anymore, could you please make it part of a different patch? This will break internal tests.

[danielcdh]

Integrate comments.

test/Transforms/SampleProfile/Inputs/calls.prof

8

The new format does not take comments in profile. Do you think we want to support it?

[dnovillo]

LGTM with the support of '#' comments in the input text profile.

test/Transforms/SampleProfile/Inputs/calls.prof

8

Yeah. It's easy enough to support and since the text format is used for tests, it's a useful feature to have.

[danielcdh]

submitted

include/llvm/ProfileData/SampleProf.h

 /// that are on the same line but belong to different basic blocks
 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
 struct LineLocation {
   LineLocation(int L, unsigned D) : LineOffset(L), Discriminator(D) {}
   int LineOffset;
   unsigned Discriminator;
 };
 
+/// Represents the relative location of a callsite.
+///
+/// Callsite locations are specified by the line offset from the
+/// beginning of the function (marked by the line where the function
+/// head is), the discriminator value within that line, and the callee
+/// function name.
+struct CallsiteLocation {
+  CallsiteLocation(int L, unsigned D, std::string N) : LineOffset(L),
+                                                       Discriminator(D),
+                                                       CalleeName(N) {}
+  int LineOffset;
+  unsigned Discriminator;
+  StringRef CalleeName;
+};
+
 } // End namespace sampleprof
 
 template <> struct DenseMapInfo<sampleprof::LineLocation> {
   typedef DenseMapInfo<int> OffsetInfo;
   typedef DenseMapInfo<unsigned> DiscriminatorInfo;
   static inline sampleprof::LineLocation getEmptyKey() {
     return sampleprof::LineLocation(OffsetInfo::getEmptyKey(),
                                     DiscriminatorInfo::getEmptyKey());
   }
   static inline sampleprof::LineLocation getTombstoneKey() {
     return sampleprof::LineLocation(OffsetInfo::getTombstoneKey(),
                                     DiscriminatorInfo::getTombstoneKey());
   }
   static inline unsigned getHashValue(sampleprof::LineLocation Val) {
     return DenseMapInfo<std::pair<int, unsigned>>::getHashValue(
         std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator));
   }
   static inline bool isEqual(sampleprof::LineLocation LHS,
                              sampleprof::LineLocation RHS) {
     return LHS.LineOffset == RHS.LineOffset &&
            LHS.Discriminator == RHS.Discriminator;
   }
 };
 
+template <> struct DenseMapInfo<sampleprof::CallsiteLocation> {
+  typedef DenseMapInfo<int> OffsetInfo;
+  typedef DenseMapInfo<unsigned> DiscriminatorInfo;
+  typedef DenseMapInfo<StringRef> CalleeNameInfo;
+  static inline sampleprof::CallsiteLocation getEmptyKey() {
+    return sampleprof::CallsiteLocation(OffsetInfo::getEmptyKey(),
+                                        DiscriminatorInfo::getEmptyKey(), "");
+  }
+  static inline sampleprof::CallsiteLocation getTombstoneKey() {
+    return sampleprof::CallsiteLocation(OffsetInfo::getTombstoneKey(),
+                                        DiscriminatorInfo::getTombstoneKey(),
+                                        "");
+  }
+  static inline unsigned getHashValue(sampleprof::CallsiteLocation Val) {
+    return DenseMapInfo<std::pair<int, unsigned>>::getHashValue(
+        std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator));
+  }
+  static inline bool isEqual(sampleprof::CallsiteLocation LHS,
+                             sampleprof::CallsiteLocation RHS) {
+    return LHS.LineOffset == RHS.LineOffset &&
+           LHS.Discriminator == RHS.Discriminator &&
+           LHS.CalleeName == RHS.CalleeName;
+  }
+};
+
 namespace sampleprof {
 
 /// Representation of a single sample record.
 ///
 /// A sample record is represented by a positive integer value, which
 /// indicates how frequently was the associated line location executed.
 ///
 /// Additionally, if the associated location contains a function call,
public:
   }
 
 private:
   unsigned NumSamples;
   CallTargetMap CallTargets;
 };
 
 typedef DenseMap<LineLocation, SampleRecord> BodySampleMap;
+class FunctionSamples;
+typedef DenseMap<CallsiteLocation, FunctionSamples> CallsiteSampleMap;
 
 /// Representation of the samples collected for a function.
 ///
 /// This data structure contains all the collected samples for the body
 /// of a function. Each sample corresponds to a LineLocation instance
 /// within the body of the function.
 class FunctionSamples {
 public:
public:
   }
 
   /// Return the number of samples collected at the given location.
   /// Each location is specified by \p LineOffset and \p Discriminator.
   unsigned samplesAt(int LineOffset, unsigned Discriminator) {
     return sampleRecordAt(LineLocation(LineOffset, Discriminator)).getSamples();
   }
 
-  bool empty() const { return BodySamples.empty(); }
+  /// Return the number of samples collected at the given location.
+  /// Each location is specified by \p LineOffset and \p Discriminator.
+  /// If the location is not found in profile, return 0.
+  unsigned findSamplesAt(int LineOffset, unsigned Discriminator) const {
+    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
+    if (ret == BodySamples.end())
+      return 0;
+    else
+      return ret->second.getSamples();
+  }
+
+  /// Return the function samples at the given callsite location.
+  FunctionSamples &functionSamplesAt(const CallsiteLocation &Loc) {
+    return CallsiteSamples[Loc];
+  }
+
+  /// Return a pointer to function samples at the given callsite location.
+  const FunctionSamples *findFunctionSamplesAt(
+      const CallsiteLocation &Loc) const {
+    auto iter = CallsiteSamples.find(Loc);
+    if (iter == CallsiteSamples.end()) {
+      return NULL;
+    } else {
+      return &iter->second;
+    }
+  }
+
+  bool empty() const { return TotalSamples == 0; }
 
   /// Return the total number of samples collected inside the function.
   unsigned getTotalSamples() const { return TotalSamples; }
 
   /// Return the total number of samples collected at the head of the
   /// function.
   unsigned getHeadSamples() const { return TotalHeadSamples; }
 
   /// Return all the samples collected in the body of the function.
   const BodySampleMap &getBodySamples() const { return BodySamples; }
 
+  /// Return all the callsite samples collected in the body of the function.
+  const CallsiteSampleMap &getCallsiteSamples() const {
+    return CallsiteSamples;
+  }
+
   /// Merge the samples in \p Other into this one.
   void merge(const FunctionSamples &Other) {
     addTotalSamples(Other.getTotalSamples());
     addHeadSamples(Other.getHeadSamples());
     for (const auto &I : Other.getBodySamples()) {
       const LineLocation &Loc = I.first;
       const SampleRecord &Rec = I.second;
       sampleRecordAt(Loc).merge(Rec);
     }
+    for (const auto &I : Other.getCallsiteSamples()) {
+      const CallsiteLocation &Loc = I.first;
+      const FunctionSamples &Rec = I.second;
+      functionSamplesAt(Loc).merge(Rec);
+    }
   }
 
 private:
   /// Total number of samples collected inside this function.
   ///
   /// Samples are cumulative, they include all the samples collected
   /// inside this function and all its inlined callees.
   unsigned TotalSamples;
 
   /// Total number of samples collected at the head of the function.
   /// This is an approximation of the number of calls made to this function
   /// at runtime.
   unsigned TotalHeadSamples;
 
   /// Map instruction locations to collected samples.
   ///
   /// Each entry in this map contains the number of samples
   /// collected at the corresponding line offset. All line locations
   /// are an offset from the start of the function.
   BodySampleMap BodySamples;
+
+  CallsiteSampleMap CallsiteSamples;
 };
 
 } // End namespace sampleprof
 
 } // End namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_

lib/ProfileData/SampleProfReader.cpp

 //
 // Function names must be mangled in order for the profile loader to
 // match them in the current translation unit. The two numbers in the
 // function header specify how many total samples were accumulated in the
 // function (first number), and the total number of samples accumulated
 // in the prologue of the function (second number). This head sample
 // count provides an indicator of how frequently the function is invoked.
 //
 // Each sampled line may contain several items. Some are optional (marked
 // below):
 //
 // a. Source line offset. This number represents the line number
 //    in the function where the sample was collected. The line number is
 //    always relative to the line where symbol of the function is
 //    defined. So, if the function has its header at line 280, the offset
 //    13 is at line 293 in the file.
 //
 //    Note that this offset should never be a negative number. This could
 //    happen in cases like macros. The debug machinery will register the
 //    line number at the point of macro expansion. So, if the macro was
 //    expanded in a line before the start of the function, the profile
 //    converter should emit a 0 as the offset (this means that the optimizers
 //    will not be able to associate a meaningful weight to the instructions

 //===----------------------------------------------------------------------===//
 
 #include "llvm/ProfileData/SampleProfReader.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
-#include "llvm/Support/Regex.h"
+#include "llvm/ADT/DenseMap.h"
 
 using namespace llvm::sampleprof;
 using namespace llvm;
 
 /// \brief Print the samples collected for a function on stream \p OS.
 ///
 /// \param OS Stream to emit the output to.
 void FunctionSamples::print(raw_ostream &OS) {

 }
 
 /// \brief Dump all the function profiles found on stream \p OS.
 void SampleProfileReader::dump(raw_ostream &OS) {
   for (const auto &I : Profiles)
     dumpFunctionProfile(I.getKey(), OS);
 }
 
+/// \brief Parse \p Input as function head.
+///
+/// Parse one line of \p Input, and update function name in \p FName,
+/// function's total sample count in \p NumSamples, function's entry
+/// count in \p NumHeadSamples.
+///
+/// \returns true if parsing is successful.
+static bool ParseHead(const StringRef &Input,
+                      StringRef &FName,
+                      unsigned &NumSamples,
+                      unsigned &NumHeadSamples) {
+  if (Input[0] == ' ')
+    return false;
+  size_t n1 = Input.find(':');
+  FName = Input.substr(0, n1);
+  size_t n2 = Input.find(':', n1 + 1);
+  if (Input.substr(n1+1, n2-n1-1).getAsInteger(10, NumSamples))
+    return false;
+  if (Input.substr(n2+1).getAsInteger(10, NumHeadSamples))
+    return false;
+  return true;
+}
+
+/// \brief Parse \p Input as line sample.
+///
+/// \param Input input line.
+/// \param IsCallsite true if the line represents an inlined callsite.
+/// \param Depth the depth of the inline stack.
+/// \param NumSamples total samples of the line/inlined callsite.
+/// \param LineOffset line offset to the start of the function.
+/// \param Discriminator discriminator of the line.
+/// \param TargetCountMap map from indirect call target to count.
+///
+/// returns true if parsing is successful.
+static bool ParseLine(const StringRef &Input,
+                      bool &IsCallsite,
+                      unsigned &Depth,
+                      unsigned &NumSamples,
+                      unsigned &LineOffset,
+                      unsigned &Discriminator,
+                      StringRef &CalleeName,
+                      DenseMap<StringRef, unsigned> &TargetCountMap) {
+  for (Depth = 0; Input[Depth] == ' '; Depth++)
+    ;
+  if (Depth == 0)
+    return false;
+
+  size_t n1 = Input.find(':');
+  StringRef Loc = Input.substr(Depth, n1 - Depth);
+  size_t n2 = Loc.find('.');
+  if (n2 == StringRef::npos) {
+    if (Loc.getAsInteger(10, LineOffset))
+      return false;
+    Discriminator = 0;
+  } else {
+    if (Loc.substr(0, n2).getAsInteger(10, LineOffset))
+      return false;
+    if (Loc.substr(n2+1).getAsInteger(10, Discriminator))
+      return false;
+  }
+
+  StringRef Rest = Input.substr(n1 + 2);
+  if (Rest[0] >= '0' && Rest[0] <= '9') {
+    IsCallsite = false;
+    size_t n3 = Rest.find(' ');
+    if (n3 == StringRef::npos) {
+      if (Rest.getAsInteger(10, NumSamples))
+        return false;
+    } else {
+      if (Rest.substr(0, n3).getAsInteger(10, NumSamples))
+        return false;
+    }
+    while (n3 != StringRef::npos) {
+      Rest = Rest.substr(n3 + 1);
+      n3 = Rest.find(' ');
+      StringRef pair = Rest;
+      if (n3 != StringRef::npos) {
+        pair = Rest.substr(0, n3);
+      }
+      int n4 = pair.find(':');
+      unsigned count;
+      if (pair.substr(n4+1).getAsInteger(10, count))
+        return false;
+      TargetCountMap[pair.substr(0, n4)] = count;
+    }
+  } else {
+    IsCallsite = true;
+    int n3 = Rest.find(':');
+    CalleeName = Rest.substr(0, n3);
+    if (Rest.substr(n3+1).getAsInteger(10, NumSamples))
+      return false;
+  }
+  return true;
+}
+
 /// \brief Load samples from a text file.
 ///
 /// See the documentation at the top of the file for an explanation of
 /// the expected format.
 ///
 /// \returns true if the file was loaded successfully, false otherwise.
 std::error_code SampleProfileReaderText::read() {
   line_iterator LineIt(*Buffer, /*SkipBlanks=*/true, '#');
 
-  // Read the profile of each function. Since each function may be
-  // mentioned more than once, and we are collecting flat profiles,
-  // accumulate samples as we parse them.
-  Regex HeadRE("^([^0-9].*):([0-9]+):([0-9]+)$");
-  Regex LineSampleRE("^([0-9]+)\\.?([0-9]+)?: ([0-9]+)(.*)$");
-  Regex CallSampleRE(" +([^0-9 ][^ ]*):([0-9]+)");
+  std::vector<FunctionSamples *> InlineStack;
+
   while (!LineIt.is_at_eof()) {
     // Read the header of each function.
     //
     // Note that for function identifiers we are actually expecting
     // mangled names, but we may not always get them. This happens when
     // the compiler decides not to emit the function (e.g., it was inlined
     // and removed). In this case, the binary will not have the linkage
     // name for the function, so the profiler will emit the function's
     // unmangled name, which may contain characters like ':' and '>' in its
     // name (member functions, templates, etc).
     //
     // The only requirement we place on the identifier, then, is that it
     // should not begin with a number.
-    SmallVector<StringRef, 4> Matches;
-    if (!HeadRE.match(*LineIt, &Matches)) {
+    if ((*LineIt)[0] != ' ') {
+      unsigned NumSamples, NumHeadSamples;
+      StringRef FName;
+      if (!ParseHead(*LineIt, FName, NumSamples, NumHeadSamples)) {
         reportError(LineIt.line_number(),
                     "Expected 'mangled_name:NUM:NUM', found " + *LineIt);
         return sampleprof_error::malformed;
       }
-    assert(Matches.size() == 4);
-    StringRef FName = Matches[1];
-    unsigned NumSamples, NumHeadSamples;
-    Matches[2].getAsInteger(10, NumSamples);
-    Matches[3].getAsInteger(10, NumHeadSamples);
       Profiles[FName] = FunctionSamples();
       FunctionSamples &FProfile = Profiles[FName];
       FProfile.addTotalSamples(NumSamples);
       FProfile.addHeadSamples(NumHeadSamples);
-    ++LineIt;
-
-    // Now read the body. The body of the function ends when we reach
-    // EOF or when we see the start of the next function.
-    while (!LineIt.is_at_eof() && isdigit((*LineIt)[0])) {
-      if (!LineSampleRE.match(*LineIt, &Matches)) {
+      InlineStack.clear();
+      InlineStack.push_back(&FProfile);
+    } else {
+      unsigned NumSamples;
+      StringRef FName;
+      DenseMap<StringRef, unsigned> TargetCountMap;
+      bool IsCallsite;
+      unsigned Depth, LineOffset, Discriminator;
+      if (!ParseLine(*LineIt, IsCallsite, Depth, NumSamples,
+                     LineOffset, Discriminator, FName, TargetCountMap)) {
         reportError(LineIt.line_number(),
                     "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " +
                         *LineIt);
         return sampleprof_error::malformed;
       }
-      assert(Matches.size() == 5);
-      unsigned LineOffset, NumSamples, Discriminator = 0;
-      Matches[1].getAsInteger(10, LineOffset);
-      if (Matches[2] != "")
-        Matches[2].getAsInteger(10, Discriminator);
-      Matches[3].getAsInteger(10, NumSamples);
-
-      // If there are function calls in this line, generate a call sample
-      // entry for each call.
-      std::string CallsLine(Matches[4]);
-      while (CallsLine != "") {
-        SmallVector<StringRef, 3> CallSample;
-        if (!CallSampleRE.match(CallsLine, &CallSample)) {
-          reportError(LineIt.line_number(),
-                      "Expected 'mangled_name:NUM', found " + CallsLine);
-          return sampleprof_error::malformed;
+      if (IsCallsite) {
+        while(InlineStack.size() > Depth) {
+          InlineStack.pop_back();
+        }
+        FunctionSamples &FSamples = InlineStack.back()->functionSamplesAt(
+            CallsiteLocation(LineOffset, Discriminator, FName));
+        FSamples.addTotalSamples(NumSamples);
+        InlineStack.push_back(&FSamples);
+      } else {
+        while(InlineStack.size() > Depth) {
+          InlineStack.pop_back();
         }
-        StringRef CalledFunction = CallSample[1];
-        unsigned CalledFunctionSamples;
-        CallSample[2].getAsInteger(10, CalledFunctionSamples);
+        FunctionSamples &FProfile = *InlineStack.back();
+        for (const auto &name_count : TargetCountMap) {
           FProfile.addCalledTargetSamples(LineOffset, Discriminator,
-                                        CalledFunction, CalledFunctionSamples);
-        CallsLine = CallSampleRE.sub("", CallsLine);
+                                          name_count.first, name_count.second);
         }
-
         FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
-      ++LineIt;
       }
     }
+    ++LineIt;
+  }
 
   return sampleprof_error::success;
 }
 
 template <typename T> ErrorOr<T> SampleProfileReaderBinary::readNumber() {
   unsigned NumBytesRead = 0;
   std::error_code EC;
   uint64_t Val = decodeULEB128(Data, &NumBytesRead);

lib/Transforms/IPO/SampleProfile.cpp

 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Pass.h"
 #include "llvm/ProfileData/SampleProfReader.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Utils/Cloning.h"
 #include <cctype>
 
 using namespace llvm;
 using namespace sampleprof;
 
 #define DEBUG_TYPE "sample-profile"
 
 // Command line option to specify the file to read samples from. This is
public:
   }
 
 protected:
   bool runOnFunction(Function &F);
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F);
   unsigned getInstWeight(Instruction &I);
   unsigned getBlockWeight(BasicBlock *BB);
+  const FunctionSamples *findCalleeFunctionSamples(const CallInst &I) const;
+  const FunctionSamples *findFunctionSamples(const Instruction &I) const;
+  bool inlineHotFunctions(Function &F);
   void printEdgeWeight(raw_ostream &OS, Edge E);
   void printBlockWeight(raw_ostream &OS, BasicBlock *BB);
   void printBlockEquivalence(raw_ostream &OS, BasicBlock *BB);
   bool computeBlockWeights(Function &F);
   void findEquivalenceClasses(Function &F);
   void findEquivalencesFor(BasicBlock *BB1,
                            SmallVector<BasicBlock *, 8> Descendants,
                            DominatorTreeBase<BasicBlock> *DomTree);
unsigned SampleProfileLoader::getInstWeight(Instruction &Inst) {
 
   unsigned Lineno = DLoc.getLine();
   if (Lineno < HeaderLineno)
     return 0;
 
   const DILocation *DIL = DLoc;
   int LOffset = Lineno - HeaderLineno;
   unsigned Discriminator = DIL->getDiscriminator();
-  unsigned Weight = Samples->samplesAt(LOffset, Discriminator);
+  const FunctionSamples *FS = findFunctionSamples(Inst);
+  unsigned Weight = 0;
+  if (FS)
+    Weight = FS->findSamplesAt(LOffset, Discriminator);
   DEBUG(dbgs() << "    " << Lineno << "." << Discriminator << ":" << Inst
                << " (line offset: " << LOffset << "." << Discriminator
                << " - weight: " << Weight << ")\n");
   return Weight;
 }
 
 /// \brief Compute the weight of a basic block.
 ///
for (auto &BB : F) {
     unsigned Weight = getBlockWeight(&BB);
     Changed |= (Weight > 0);
     DEBUG(printBlockWeight(dbgs(), &BB));
   }
 
   return Changed;
 }
 
+/// \brief Get the FunctionSamples for a call instruction.
+///
+/// The FunctionSamples of a call instruction \p Inst is the inlined
+/// instance in which that call instruction is calling to. It contains
+/// all samples that resides in the inlined instance. We first find the
+/// inlined instance in which the call instruction is from, then we
+/// traverse its children to find the callsite with the matching
+/// location and callee function name.
+///
+/// \param Inst Call instruction to query.
+///
+/// \returns The FunctionSamples pointer to the inlined instance.
+const FunctionSamples *SampleProfileLoader::findCalleeFunctionSamples(
+    const CallInst &Inst) const {
+  const DILocation *DIL = Inst.getDebugLoc();
+  if (!DIL) {
+    return NULL;
+  }
+  DISubprogram *SP = DIL->getScope()->getSubprogram();
+  if (!SP || DIL->getLine() < SP->getLine())
+    return NULL;
+
+  Function *CalleeFunc = Inst.getCalledFunction();
+  if (!CalleeFunc) {
+    return NULL;
+  }
+
+  StringRef CalleeName = CalleeFunc->getName();
+  const FunctionSamples *FS = findFunctionSamples(Inst);
+  if (FS == NULL)
+    return NULL;
+
+  return FS->findFunctionSamplesAt(
+      CallsiteLocation(DIL->getLine() - SP->getLine(),
+                       DIL->getDiscriminator(),
+                       CalleeName));
+}
+
+/// \brief Get the FunctionSamples for an instruction.
+///
+/// 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 {
+  SmallVector<CallsiteLocation, 10> S;
+  const DILocation *DIL = Inst.getDebugLoc();
+  if (!DIL) {
+    return Samples;
+  }
+  StringRef CalleeName;
+  for (const DILocation *DIL = Inst.getDebugLoc(); DIL;
+       DIL = DIL->getInlinedAt()) {
+    DISubprogram *SP = DIL->getScope()->getSubprogram();
+    if (!SP || DIL->getLine() < SP->getLine())
+      return NULL;
+    if (!CalleeName.empty()) {
+      S.push_back(CallsiteLocation(DIL->getLine() - SP->getLine(),
+                                   DIL->getDiscriminator(),
+                                   CalleeName));
+    }
+    CalleeName = SP->getLinkageName();
+  }
+  if (S.size() == 0)
+    return Samples;
+  const FunctionSamples *FS = Samples;
+  for (int i = S.size() - 1; i >= 0 && FS != NULL; i--) {
+    FS = FS->findFunctionSamplesAt(S[i]);
+  }
+  return FS;
+}
+
+/// \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.
+///
+/// \param F function to perform iterative inlining.
+///
+/// \returns True if there is any inline happened.
+bool SampleProfileLoader::inlineHotFunctions(Function &F) {
+  bool Changed = false;
+  while (true) {
+    bool LocalChanged = false;
+    SmallVector<CallInst *, 10> CIS;
+    for (auto &BB : F) {
+      for (auto &I : BB.getInstList()) {
+        CallInst *CI = dyn_cast<CallInst>(&I);
+        if (CI) {
+          const FunctionSamples *FS = findCalleeFunctionSamples(*CI);
+          if (FS && FS->getTotalSamples() > 0) {
+            CIS.push_back(CI);
+          }
+        }
+      }
+    }
+    for (auto CI : CIS) {
+      InlineFunctionInfo IFI;
+      if (InlineFunction(CI, IFI))
+        LocalChanged = true;
+    }
+    if (LocalChanged) {
+      Changed = true;
+    } else {
+      break;
+    }
+  }
+  return Changed;
+}
+
 /// \brief Find equivalence classes for the given block.
 ///
 /// This finds all the blocks that are guaranteed to execute the same
 /// number of times as \p BB1. To do this, it traverses all the
 /// descendants of \p BB1 in the dominator or post-dominator tree.
 ///
 /// A block BB2 will be in the same equivalence class as \p BB1 if
 /// the following holds:
bool SampleProfileLoader::emitAnnotations(Function &F) {
   // Initialize invariants used during computation and propagation.
   HeaderLineno = getFunctionLoc(F);
   if (HeaderLineno == 0)
     return false;
 
   DEBUG(dbgs() << "Line number for the first instruction in " << F.getName()
                << ": " << HeaderLineno << "\n");
 
+  Changed |= inlineHotFunctions(F);
+
   // Compute basic block weights.
   Changed |= computeBlockWeights(F);
 
   if (Changed) {
     // Compute dominance and loop info needed for propagation.
     computeDominanceAndLoopInfo(F);
 
     // Find equivalence classes.

test/Transforms/SampleProfile/Inputs/bad_discriminator_value.prof

 empty:100:0
  1.-3: 10

test/Transforms/SampleProfile/Inputs/bad_fn_header.prof

 3empty:100:BAD
  0: 0
  1: 100

test/Transforms/SampleProfile/Inputs/bad_mangle.prof

 double convert<std::string, float>(float):2909472:181842
  0: 181842
  1: 181842

test/Transforms/SampleProfile/Inputs/bad_sample_line.prof

 empty:100:0
  0: 0
  1: BAD

test/Transforms/SampleProfile/Inputs/bad_samples.prof

 empty:100:0
  1.3: -10

test/Transforms/SampleProfile/Inputs/branch.prof

 main:15680:0
  0: 0
  4: 0
  7: 0
  9: 10226
  10: 2243
  16: 0
  18: 0

test/Transforms/SampleProfile/Inputs/calls.prof

 _Z3sumii:105580:5279
  0: 5279
  1: 5279
  2: 5279
 main:225715:0
  2.1: 5553
  3: 5391
-# This indicates that at line 3 of this function, the 'then' branch
-# of the conditional is taken (discriminator '1').
-3.1: 5752  _Z3sumii:5860
+ 3.1: 5752 _Z3sumii:5860

test/Transforms/SampleProfile/Inputs/discriminator.prof

 foo:1000:0
  1: 1
  2: 1
  2.1: 100
  3: 100
  3.1: 5
  4: 100
  5: 1

test/Transforms/SampleProfile/Inputs/entry_counts.prof

 empty:100:13293
  0: 0
  1: 100

test/Transforms/SampleProfile/Inputs/fnptr.prof

 _Z3fooi:7711:610
  1: 610
 _Z3bari:20301:1437
  1: 1437
 main:184019:0
  4: 534
  6: 2080
  9: 2064 _Z3bari:1471 _Z3fooi:631
  5.1: 1075
  5: 1075
  7: 534
  4.2: 534

test/Transforms/SampleProfile/Inputs/inline.prof

+main:225715:0
+ 2.1: 5553
+ 3: 5391
+ 3.1: _Z3sumii:5860
+  0: 5279
+  1: 5279
+  2: 5279

test/Transforms/SampleProfile/Inputs/propagate.prof

 _Z3fooiil:58139:0
  0: 0
  1: 0
  2: 0
  4: 1
  5: 10
  6: 0
  7: 5
  8: 3
  9: 0
  10: 0
  11: 6339
  12: 16191
  13: 8141
  16: 1
  18: 0
  19: 0

test/Transforms/SampleProfile/Inputs/syntax.prof

 empty:100:0
  0: 0
  1: 100

test/Transforms/SampleProfile/inline.ll

+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/inline.prof -S | FileCheck %s
+
+; Original C++ test case
+;
+; #include <stdio.h>
+;
+; int sum(int x, int y) {
+;   return x + y;
+; }
+;
+; int main() {
+;   int s, i = 0;
+;   while (i++ < 20000 * 20000)
+;     if (i != 100) s = sum(i, s); else s = 30;
+;   printf("sum is %d\n", s);
+;   return 0;
+; }
+;
+@.str = private unnamed_addr constant [11 x i8] c"sum is %d\0A\00", align 1
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z3sumii(i32 %x, i32 %y) {
+entry:
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4, !dbg !11
+  %1 = load i32, i32* %y.addr, align 4, !dbg !11
+  %add = add nsw i32 %0, %1, !dbg !11
+  ret i32 %add, !dbg !11
+}
+
+; Function Attrs: uwtable
+define i32 @main() {
+entry:
+  %retval = alloca i32, align 4
+  %s = alloca i32, align 4
+  %i = alloca i32, align 4
+  store i32 0, i32* %retval
+  store i32 0, i32* %i, align 4, !dbg !12
+  br label %while.cond, !dbg !13
+
+while.cond:                                       ; preds = %if.end, %entry
+  %0 = load i32, i32* %i, align 4, !dbg !14
+  %inc = add nsw i32 %0, 1, !dbg !14
+  store i32 %inc, i32* %i, align 4, !dbg !14
+  %cmp = icmp slt i32 %0, 400000000, !dbg !14
+  br i1 %cmp, label %while.body, label %while.end, !dbg !14
+
+while.body:                                       ; preds = %while.cond
+  %1 = load i32, i32* %i, align 4, !dbg !16
+  %cmp1 = icmp ne i32 %1, 100, !dbg !16
+  br i1 %cmp1, label %if.then, label %if.else, !dbg !16
+
+
+if.then:                                          ; preds = %while.body
+  %2 = load i32, i32* %i, align 4, !dbg !18
+  %3 = load i32, i32* %s, align 4, !dbg !18
+  %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
+; CHECK-NOT: call i32 @_Z3sumii
+  store i32 %call, i32* %s, align 4, !dbg !18
+  br label %if.end, !dbg !18
+
+if.else:                                          ; preds = %while.body
+  store i32 30, i32* %s, align 4, !dbg !20
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  br label %while.cond, !dbg !22
+
+while.end:                                        ; preds = %while.cond
+  %4 = load i32, i32* %s, align 4, !dbg !24
+  %call2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i32 0, i32 0), i32 %4), !dbg !24
+  ret i32 0, !dbg !25
+}
+
+declare i32 @printf(i8*, ...) #2
+
+!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: 0, file: !1, enums: !2, retainedTypes: !2, subprograms: !3, globals: !2, imports: !2)
+!1 = !DIFile(filename: "calls.cc", directory: ".")
+!2 = !{}
+!3 = !{!4, !7}
+!4 = distinct !DISubprogram(name: "sum", line: 3, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, scopeLine: 3, file: !1, scope: !5, type: !6, function: i32 (i32, i32)* @_Z3sumii, variables: !2)
+!5 = !DIFile(filename: "calls.cc", directory: ".")
+!6 = !DISubroutineType(types: !2)
+!7 = distinct !DISubprogram(name: "main", line: 7, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: false, scopeLine: 7, file: !1, scope: !5, type: !6, function: i32 ()* @main, variables: !2)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 1, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.5 "}
+!11 = !DILocation(line: 4, scope: !4)
+!12 = !DILocation(line: 8, scope: !7)
+!13 = !DILocation(line: 9, scope: !7)
+!14 = !DILocation(line: 9, scope: !15)
+!15 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !7)
+!16 = !DILocation(line: 10, scope: !17)
+!17 = distinct !DILexicalBlock(line: 10, column: 0, file: !1, scope: !7)
+!18 = !DILocation(line: 10, scope: !19)
+!19 = !DILexicalBlockFile(discriminator: 1, file: !1, scope: !17)
+!20 = !DILocation(line: 10, scope: !21)
+!21 = !DILexicalBlockFile(discriminator: 2, file: !1, scope: !17)
+!22 = !DILocation(line: 10, scope: !23)
+!23 = !DILexicalBlockFile(discriminator: 3, file: !1, scope: !17)
+!24 = !DILocation(line: 11, scope: !7)
+!25 = !DILocation(line: 12, scope: !7)

test/Transforms/SampleProfile/syntax.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/syntax.prof 2>&1 | FileCheck -check-prefix=NO-DEBUG %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=missing.prof 2>&1 | FileCheck -check-prefix=MISSING-FILE %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_fn_header.prof 2>&1 | FileCheck -check-prefix=BAD-FN-HEADER %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_sample_line.prof 2>&1 | FileCheck -check-prefix=BAD-SAMPLE-LINE %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_line_values.prof 2>&1 | FileCheck -check-prefix=BAD-LINE-VALUES %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_discriminator_value.prof 2>&1 | FileCheck -check-prefix=BAD-DISCRIMINATOR-VALUE %s
 ; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_samples.prof 2>&1 | FileCheck -check-prefix=BAD-SAMPLES %s
-; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_mangle.prof 2>&1 >/dev/null
+; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_mangle.prof 2>&1 | FileCheck -check-prefix=BAD-MANGLE %s
 
 define void @empty() {
 entry:
   ret void
 }
 ; NO-DEBUG: warning: No debug information found in function empty: Function profile not used
 ; MISSING-FILE: missing.prof: Could not open profile:
 ; BAD-FN-HEADER: error: {{.*}}bad_fn_header.prof:1: Expected 'mangled_name:NUM:NUM', found 3empty:100:BAD
 ; BAD-SAMPLE-LINE: error: {{.*}}bad_sample_line.prof:3: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1: BAD
 ; BAD-LINE-VALUES: error: {{.*}}bad_line_values.prof:2: Expected 'mangled_name:NUM:NUM', found -1: 10
 ; BAD-DISCRIMINATOR-VALUE: error: {{.*}}bad_discriminator_value.prof:2: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1.-3: 10
 ; BAD-SAMPLES: error: {{.*}}bad_samples.prof:2: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1.3: -10
+; BAD-MANGLE: error: {{.*}}bad_mangle.prof:1: Expected 'mangled_name:NUM:NUM', found double convert<std::string, float>(float):2909472:181842

test/tools/llvm-profdata/Inputs/sample-profile.proftext

 _Z3bari:20301:1437
  1: 1437
 _Z3fooi:7711:610
  1: 610
 main:184019:0
  4: 534
  4.2: 534
  5: 1075
  5.1: 1075
  6: 2080
  7: 534
-9: 2064  _Z3bari:1471  _Z3fooi:631
+ 9: 2064 _Z3bari:1471 _Z3fooi:631