Improve PGO support for the new inliner

[eraman]

Summary

This adds the following to the new PM based inliner in PGO mode:

• Use block frequency analysis to derive callsite's profile count and use that to adjust thresholds of hot and cold callsites.
• Incrementally update the BFI of the caller after a callee gets inlined into it. This incremental update is only within an invocation of the run method - BFI is not preserved across calls to run.
• Update the function entry count of the callee after inlining it into a caller.

I've tuned the thresholds for the hot and cold callsites using a hacked up version of the old inliner that explicitly computes BFI on a set of internal benchmarks and spec. Once the new PM based pipeline stabilizes (IIRC Chandler mentioned there are known issues) I'll benchmark this again and adjust the thresholds if required.

[chandlerc]

Some quick initial comments, thanks!

include/llvm/Analysis/InlineCost.h

178

I would use llvm's function_ref rather than std::function -- it is much lighter weight and the caller can ensure that the function object outlives the call.

Also, I would prefer Optional<function_ref<...>> over function_ref<...>* as the pointer seems a more error prone API.

include/llvm/Transforms/Utils/Cloning.h

186

My brain is probably just being a bit dense, but is there no way to just give an (optional) BFI (or pair of BFIs) directly? This doesn't need to query recursively the way inline cost does?

lib/Analysis/InlineCost.cpp

648–649

It seems problematic to couple these hints in this way, and I think that results in the need to use a predicate here.

What about first a small refactoring patch that just separates the PSI-based threshold adjustment from InlineHint, and then this code can add a preferred path instead of the PSI-exclusive one when we have BFI available?

648–649

This code is now very confusing combined with the below code. What is it that determines whether a callsite is hot?

650

Why would CallBB ever be null?

656

You don't print cold here, just hot?

lib/Transforms/Utils/InlineFunction.cpp

1463–1474

I feel like much of this logic should really live in BFI next to the other logic for updating and maintaining these values rather than buried in the inliner.

In particular, it seems like there should be generic logic for taking a collection of basic blocks with existing frequencies and scaling them based on some other block's frequencies.

The same core logic seems like it should be usable by things like loop unrolling, loop splitting, etc where they clone a region of blocks that have existing *relative* frequencies but are suddenly below some dominating predicate that needs to scale those frequencies.

Then the only thing happening here is the cloning of (raw, unscaled) frequencies from the callee into the inlined blocks in the caller. That cloning logic makes sense here as it has everything to do with the inlining step and nothing to do with the particular values being cloned.

1494–1499

This is why I intensely dislike uint64_t... If these were int64_t, then this would just be std::max(0, ...).

Anyways, not something to change in this patch.

1586–1587

Why do we need a dedicated cloned blocks map rather than re-using the VMap below? That is the map the cloning routine uses to map between basic blocks IIRC, so it already seems like it would have the information we need.

[davidxl]

include/llvm/Transforms/Utils/Cloning.h

186

This sounds right. IFI probably just needs a pair of BFIs.

lib/Analysis/InlineCost.cpp

648–649

What the following code says is that if callsite hotness info is available, do not use callee-entry based hotness hint.

This needs to be documented.

lib/Transforms/Utils/InlineFunction.cpp

1463–1474

I agree this probably belongs to BFI. Besides IFI is not even used here.

[eraman]

Thanks for the detailed comments. In the course of addressing these, I've added an isColdCallSite and isHotCallSite to ProfileSummaryInfo and moved that logic out of inline cost.

include/llvm/Transforms/Utils/Cloning.h

186

Yes, GetBFI is not needed. Now passing caller and callee BFI pointers.

lib/Analysis/InlineCost.cpp

650

You're right, it can never be null. Removed the check.

656

I never needed it when I was debugging the code. I've added a new set of debug messages based on {callsite/callee} {hotness/coldness}

[eraman]

Address review comments.

[davidxl]

lib/Analysis/BlockFrequencyInfo.cpp

174

can this one be split into a different patch (and with a unit test)?

lib/Analysis/ProfileSummaryInfo.cpp

147

The following new APIs belong to a separate patch perhaps.

[eraman]

Rebase after pushing some refactoring from previous revision into separate patches.

[chandlerc]

This is looking pretty close. Couple of nits and a couple of more interesting comments inline.

lib/Analysis/InlineCost.cpp

657

nit: Here and below you shouldn't need the llvm:: qualifier on dbgs I think.

lib/Transforms/IPO/Inliner.cpp

769–773

I think you can name the lambda GetBFI and below pass it as {GetBFI} if GetBFI doesn't work. You shouldn't need to construct a variable for the function_ref.

lib/Transforms/Utils/InlineFunction.cpp

1396–1446

missing vertical whitespace here.

1409

The value map seems much larger than the set of basic blocks cloned? Why not walk the cloned region of basic blocks directly and just look them up in the value map?

2241–2248

If the else needs braces, use them on the if?

2244–2246

The location of this makes it easy to completely miss...

I wonder, would it be better to just do this immediately when we create AfterCallBB even though we'll delete it in some cases?

[eraman]

Thanks for the comments! Will update the diff in a bit.

lib/Transforms/IPO/Inliner.cpp

769–773

{GetBFI} does the trick. Thanks.

lib/Transforms/Utils/InlineFunction.cpp

2244–2246

I've moved it earlier as you prefer.

[eraman]

Address Chandler's comments.

[chandlerc]

Sorry, I think you should have argued with one of my suggestions, see below. =D Your code was already right.

I also have one comment below that I'd mostly like to talk about and address in a follow-up patch if needed, it doesn't need to block this going in. Feel free to submit once you go back to your original (better) approach on the loop.

lib/Analysis/InlineCost.cpp

52–62

Is there any way to avoid introducing yet another tunable here? It feels weird to have two cold tunables, and more weird for them to be different.

Also, I would expect the threshold here to be *very* similar to the -Oz inlining threshold. Should they be the same? Or at least documented together?

lib/Transforms/Utils/InlineFunction.cpp

1408–1409

I was hoping we could do still better by walking the inlined region in the caller so we would *only* touch cloned blocks. However, there isn't a map from cloned BB to original BB, which is why you can't do that. And why you wrote the code you did. Sorry for the confusion.

Unfortunately, I think walking the entire map is better than walking the entire callee as the map only contains the inlined part. Also, in all of the other code here we walk the map to find relatively sparse and infrequent things so it seems fine. Like I said, sorry for sending you down a wrong path, I hadn't thought about the lack of clone -> original BB.

[chandlerc]

(Er, I also thought David had already LGTMed for some reason, but it isn't showing... Clearly wait for his LGTM as well!)

[davidxl]

test/Transforms/Inline/function-count-update-2.ll

13

Check no calls remaining.

18

same here

test/Transforms/Inline/function-count-update-3.ll

14

Should it be C2 * (C1/C4) where C4 is the entry count of function C? which happens to be the same to C3 here. C3 is irrelevant

32

Also check remaining count of C

test/Transforms/Inline/inline-cold-callee.ll

30

Wrap callee2 call in conditional -- otherwise its entry count should be at least 50.

31

This test case is flawed. callee1's entry count should be a least 50 given new change.

test/Transforms/Inline/inline-cold-callsite.ll

16

Is there a need to introduce callee2? Just calling callee1 twice should also illustrate the point.

test/Transforms/Inline/inline-hot-callsite-2.ll

18

just reuse callee1?

[eraman]

lib/Analysis/InlineCost.cpp

52–62

Agreed. We likely want to have one threshold for Oz, cold callsite and cold callee. I'll get the numbers and send the threshold change separately.

lib/Transforms/Utils/InlineFunction.cpp

1408–1409

But the size of the value map is O(|instructions in the cloned region|) and not O(|BBs in the cloned region|). My thinking was O(|instructions in the cloned region|) likely to be greater than O(|BBs in the original callee|) and that's why you preferred this.

[chandlerc]

lib/Transforms/Utils/InlineFunction.cpp

1408–1409

Well, we already do tons of things O(|instructions in the cloned region|) including walking the VMap in at least three other places and the original InlineCost computation. This is typically OK because we have a constant bound on it (the threshold).

But we have no realistic bound on the number of basic blocks in the callee. So it might be faster on average but have much worse long tail.

I think I'd feel safer staying within the inlined region whether its instructions or basic blocks. And if this proves hot, we should just add a reverse map (at least for basic blocks) and walk the basic blocks in the cloned region.

[davide]

Sorry for arriving late, glad to see this making progress! I left one comment inline.

lib/Analysis/InlineCost.cpp

48–57

Is it possible to introduce another cl::opt here to disable this mode while in PGO? It would be extremely useful for testing the benefit of this feature compared to what's already there in PGO.

[davide]

lib/Analysis/InlineCost.cpp

1587–1588

Nit: the option is now called -inline-cold-callsite-threshold

[Prazek]

lib/Analysis/InlineCost.cpp

48–57

Probably passing normal inlining threshold would be the same as disabling this mode.

659–661

Are there any plans in the nearest future to only rely on caller hotness/coldness and not on callee hotness?

lib/Transforms/Utils/InlineFunction.cpp

1409

auto *ClonedBB

1416

auto

[eraman]

lib/Analysis/InlineCost.cpp

48–57

I'm generally wary of the proliferation of options, and as Piotr mentioned you could set -hot-callsite-threshold to the same value as -hinlinhint-threshold and -inline-cold-callsite-threshold to -cold-callee-threshold to get the same effect.

659–661

Not sure what qualifies as "nearest" future but the plan is to use the same threshold for cold callee, cold callsite and -Oz and once we fully migrate to the new PM based pipeline consider only the callsite's hotness.

1587–1588

Thanks. There is inconsistency in the way options are named, but I prefer to prefix inline- everywhere and will fix the other options in a separate patch.

lib/Transforms/Utils/InlineFunction.cpp

1408–1409

Ok, I'll revert back to walking the VMap.

test/Transforms/Inline/function-count-update-2.ll

13

There is nothing interesting in terms of inlining here (ie the decision to inline here doesn't exercise any code path associated with this patch), but if you insist I'll add the checks.

test/Transforms/Inline/function-count-update-3.ll

14

Good catch!

test/Transforms/Inline/inline-cold-callee.ll

31

Yes and I think the best course of action is to disable the test for the new PM. Excepting some profile insanity, there is no way a callee is going to be cold without all callsites to the callee being cold and callsite coldness takes precedence over callee precedence (and there is a separate test for that)

[eraman]

Address review comments.

[davidxl]

test/Transforms/Inline/function-count-update-2.ll

13

This is just to make sure the inline decisions and expected end result of callee entry count are fully in sync.

[eraman]

Fix a test case as suggested by David

[davidxl]

lgtm

[Prazek]

It is nice to see that gbranch inliner is moving forwards to the trunk :)

include/llvm/Analysis/BlockFrequencyInfo.h

public:
   /// \brief Returns the estimated profile count of \p Freq.
   /// This uses the frequency \p Freq and multiplies it by
   /// the enclosing function's count (if available) and returns the value.
   Optional<uint64_t> getProfileCountFromFreq(uint64_t Freq) const;
 
   // Set the frequency of the given basic block.
   void setBlockFreq(const BasicBlock *BB, uint64_t Freq);
 
+  /// Set the frequency of \p BB and scale the frequencies of \p BlocksToScale
+  /// such that their frequencies relative to \p BB remain the same.
+  void setBlockFreqAndScale(const BasicBlock *BB, uint64_t Freq,
+                            SmallVectorImpl<BasicBlock *> &BlocksToScale);
+
   /// calculate - compute block frequency info for the given function.
   void calculate(const Function &F, const BranchProbabilityInfo &BPI,
                  const LoopInfo &LI);
 
   // Print the block frequency Freq to OS using the current functions entry
   // frequency to convert freq into a relative decimal form.
   raw_ostream &printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const;
 

include/llvm/Analysis/InlineCost.h

 
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
 class AssumptionCacheTracker;
+class BlockFrequencyInfo;
 class CallSite;
 class DataLayout;
 class Function;
 class ProfileSummaryInfo;
 class TargetTransformInfo;
 
 namespace InlineConstants {
 // Various thresholds used by inline cost analysis.
struct InlineParams {
   /// Threshold to use when the caller is optimized for size.
   Optional<int> OptSizeThreshold;
 
   /// Threshold to use when the caller is optimized for minsize.
   Optional<int> OptMinSizeThreshold;
 
   /// Threshold to use when the callsite is considered hot.
   Optional<int> HotCallSiteThreshold;
+
+  /// Threshold to use when the callsite is considered cold.
+  Optional<int> ColdCallSiteThreshold;
 };
 
 /// Generate the parameters to tune the inline cost analysis based only on the
 /// commandline options.
 InlineParams getInlineParams();
 
 /// Generate the parameters to tune the inline cost analysis based on command
 /// line options. If -inline-threshold option is not explicitly passed,

 /// sufficiently low to warrant inlining.
 ///
 /// Also note that calling this function *dynamically* computes the cost of
 /// inlining the callsite. It is an expensive, heavyweight call.
 InlineCost
 getInlineCost(CallSite CS, const InlineParams &Params,
               TargetTransformInfo &CalleeTTI,
               std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
+              Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
               ProfileSummaryInfo *PSI);
 
 /// \brief Get an InlineCost with the callee explicitly specified.
 /// This allows you to calculate the cost of inlining a function via a
 /// pointer. This behaves exactly as the version with no explicit callee
 /// parameter in all other respects.
 //
 InlineCost
 getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params,
               TargetTransformInfo &CalleeTTI,
               std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
+              Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
               ProfileSummaryInfo *PSI);
 
 /// \brief Minimal filter to detect invalid constructs for inlining.
 bool isInlineViable(Function &Callee);
 }
 
 #endif

include/llvm/Analysis/ProfileSummaryInfo.h

 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <memory>
 
 namespace llvm {
 class BasicBlock;
 class BlockFrequencyInfo;
+class CallSite;
 class ProfileSummary;
 /// \brief Analysis providing profile information.
 ///
 /// This is an immutable analysis pass that provides ability to query global
 /// (program-level) profile information. The main APIs are isHotCount and
 /// isColdCount that tells whether a given profile count is considered hot/cold
 /// based on the profile summary. This also provides convenience methods to
 /// check whether a function is hot or cold.
public:
   /// \brief Returns true if \p F has cold function entry.
   bool isFunctionEntryCold(const Function *F);
   /// \brief Returns true if \p F is a hot function.
   bool isHotCount(uint64_t C);
   /// \brief Returns true if count \p C is considered cold.
   bool isColdCount(uint64_t C);
   /// \brief Returns true if BasicBlock \p B is considered hot.
   bool isHotBB(const BasicBlock *B, BlockFrequencyInfo *BFI);
+  /// \brief Returns true if BasicBlock \p B is considered cold.
+  bool isColdBB(const BasicBlock *B, BlockFrequencyInfo *BFI);
+  /// \brief Returns true if CallSite \p CS is considered hot.
+  bool isHotCallSite(const CallSite &CS, BlockFrequencyInfo *BFI);
+  /// \brief Returns true if Callsite \p CS is considered cold.
+  bool isColdCallSite(const CallSite &CS, BlockFrequencyInfo *BFI);
 };
 
 /// An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
 class ProfileSummaryInfoWrapperPass : public ImmutablePass {
   std::unique_ptr<ProfileSummaryInfo> PSI;
 
 public:
   static char ID;

include/llvm/Transforms/Utils/Cloning.h

 class CallSite;
 class Trace;
 class CallGraph;
 class DataLayout;
 class Loop;
 class LoopInfo;
 class AllocaInst;
 class AssumptionCacheTracker;
+class BlockFrequencyInfo;
 class DominatorTree;
 
 /// Return an exact copy of the specified module
 ///
 std::unique_ptr<Module> CloneModule(const Module *M);
 std::unique_ptr<Module> CloneModule(const Module *M, ValueToValueMapTy &VMap);
 
 /// Return a copy of the specified module. The ShouldCloneDefinition function
void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
                                Instruction *TheCall = nullptr);
 
 /// InlineFunctionInfo - This class captures the data input to the
 /// InlineFunction call, and records the auxiliary results produced by it.
 class InlineFunctionInfo {
 public:
   explicit InlineFunctionInfo(CallGraph *cg = nullptr,
                               std::function<AssumptionCache &(Function &)>
-                                  *GetAssumptionCache = nullptr)
-      : CG(cg), GetAssumptionCache(GetAssumptionCache) {}
+                                  *GetAssumptionCache = nullptr,
+                              BlockFrequencyInfo *CallerBFI = nullptr,
+                              BlockFrequencyInfo *CalleeBFI = nullptr)
+      : CG(cg), GetAssumptionCache(GetAssumptionCache), CallerBFI(CallerBFI),
+        CalleeBFI(CalleeBFI) {}
 
   /// CG - If non-null, InlineFunction will update the callgraph to reflect the
   /// changes it makes.
   CallGraph *CG;
   std::function<AssumptionCache &(Function &)> *GetAssumptionCache;
+  BlockFrequencyInfo *CallerBFI, *CalleeBFI;
 
   /// StaticAllocas - InlineFunction fills this in with all static allocas that
   /// get copied into the caller.
   SmallVector<AllocaInst *, 4> StaticAllocas;
 
   /// InlinedCalls - InlineFunction fills this in with callsites that were
   /// inlined from the callee.  This is only filled in if CG is non-null.
   SmallVector<WeakVH, 8> InlinedCalls;

lib/Analysis/BlockFrequencyInfo.cpp

BlockFrequencyInfo::getProfileCountFromFreq(uint64_t Freq) const {
   return BFI->getProfileCountFromFreq(*getFunction(), Freq);
 }
 
 void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
   assert(BFI && "Expected analysis to be available");
   BFI->setBlockFreq(BB, Freq);
 }
 
+void BlockFrequencyInfo::setBlockFreqAndScale(
+    const BasicBlock *AnchorBB, uint64_t Freq,
+    SmallVectorImpl<BasicBlock *> &BlocksToScale) {
+  assert(BFI && "Expected analysis to be available");
+  // Use 128 bits APInt to avoid overflow.
+  APInt NewFreq(128, Freq);
+  APInt OldFreq(128, BFI->getBlockFreq(AnchorBB).getFrequency());
+  for (auto *BB : BlocksToScale) {
+
+    APInt BBFreq(128, BFI->getBlockFreq(BB).getFrequency());
+
+    // Multiply first by NewFreq and then divide by OldFreq
+    // to minimize loss of precision.
+    BBFreq *= NewFreq;
+    BBFreq = BBFreq.udiv(OldFreq);
+    BFI->setBlockFreq(BB, BBFreq.getLimitedValue());
+  }
+  BFI->setBlockFreq(AnchorBB, Freq);
+}
+
 /// Pop up a ghostview window with the current block frequency propagation
 /// rendered using dot.
 void BlockFrequencyInfo::view() const {
 // This code is only for debugging.
 #ifndef NDEBUG
   ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
 #else
   errs() << "BlockFrequencyInfo::view is only available in debug builds on "

lib/Analysis/InlineCost.cpp

 
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/DataLayout.h"

 #define DEBUG_TYPE "inline-cost"
 
 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
 
 static cl::opt<int> InlineThreshold(
     "inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
     cl::desc("Control the amount of inlining to perform (default = 225)"));
 
 static cl::opt<int> HintThreshold(
     "inlinehint-threshold", cl::Hidden, cl::init(325),
     cl::desc("Threshold for inlining functions with inline hint"));
 
+static cl::opt<int>
+    ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
+                          cl::init(45),
+                          cl::desc("Threshold for inlining cold callsites"));
+
 // We introduce this threshold to help performance of instrumentation based
 // PGO before we actually hook up inliner with analysis passes such as BPI and
 // BFI.
 static cl::opt<int> ColdThreshold(
     "inlinecold-threshold", cl::Hidden, cl::init(225),
     cl::desc("Threshold for inlining functions with cold attribute"));
 
 static cl::opt<int>
     HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(3000),
                          cl::ZeroOrMore,
                          cl::desc("Threshold for hot callsites "));
 
 namespace {
 
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
 
   /// Getter for the cache of @llvm.assume intrinsics.
   std::function<AssumptionCache &(Function &)> &GetAssumptionCache;
 
+  /// Getter for BlockFrequencyInfo
+  Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI;
+
   /// Profile summary information.
   ProfileSummaryInfo *PSI;
 
   /// The called function.
   Function &F;
 
   /// The candidate callsite being analyzed. Please do not use this to do
   /// analysis in the caller function; we want the inline cost query to be
   /// easily cacheable. Instead, use the cover function paramHasAttr.
   CallSite CandidateCS;
 
   /// Tunable parameters that control the analysis.
   const InlineParams &Params;
-
   int Threshold;
   int Cost;
 
   bool IsCallerRecursive;
   bool IsRecursiveCall;
   bool ExposesReturnsTwice;
   bool HasDynamicAlloca;
   bool ContainsNoDuplicateCall;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitResumeInst(ResumeInst &RI);
   bool visitCleanupReturnInst(CleanupReturnInst &RI);
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const TargetTransformInfo &TTI,
                std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
+               Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
                ProfileSummaryInfo *PSI, Function &Callee, CallSite CSArg,
                const InlineParams &Params)
-      : TTI(TTI), GetAssumptionCache(GetAssumptionCache), PSI(PSI), F(Callee),
-        CandidateCS(CSArg), Params(Params), Threshold(Params.DefaultThreshold),
-        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
-        ExposesReturnsTwice(false), HasDynamicAlloca(false),
-        ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
-        HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
-        NumVectorInstructions(0), FiftyPercentVectorBonus(0),
-        TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
-        NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
-        NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
-        SROACostSavings(0), SROACostSavingsLost(0) {}
+      : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
+        PSI(PSI), F(Callee), CandidateCS(CSArg), Params(Params),
+        Threshold(Params.DefaultThreshold), Cost(0), IsCallerRecursive(false),
+        IsRecursiveCall(false), ExposesReturnsTwice(false),
+        HasDynamicAlloca(false), ContainsNoDuplicateCall(false),
+        HasReturn(false), HasIndirectBr(false), HasFrameEscape(false),
+        AllocatedSize(0), NumInstructions(0), NumVectorInstructions(0),
+        FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0),
+        NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
+        NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
+        NumInstructionsSimplified(0), SROACostSavings(0),
+        SROACostSavingsLost(0) {}
 
   bool analyzeCall(CallSite CS);
 
   int getThreshold() { return Threshold; }
   int getCost() { return Cost; }
 
   // Keep a bunch of stats about the cost savings found so we can print them
   // out when debugging.
void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) {
   };
 
   // Use the OptMinSizeThreshold or OptSizeThreshold knob if they are available
   // and reduce the threshold if the caller has the necessary attribute.
   if (Caller->optForMinSize())
     Threshold = MinIfValid(Threshold, Params.OptMinSizeThreshold);
   else if (Caller->optForSize())
     Threshold = MinIfValid(Threshold, Params.OptSizeThreshold);
 
   // Adjust the threshold based on inlinehint attribute and profile based
   // hotness information if the caller does not have MinSize attribute.
   if (!Caller->optForMinSize()) {
     if (Callee.hasFnAttribute(Attribute::InlineHint))
       Threshold = MaxIfValid(Threshold, Params.HintThreshold);
     if (PSI) {
-      uint64_t TotalWeight;
-      if (CS.getInstruction()->extractProfTotalWeight(TotalWeight) &&
-          PSI->isHotCount(TotalWeight)) {
+      BlockFrequencyInfo *CallerBFI = GetBFI ? &((*GetBFI)(*Caller)) : nullptr;
+      if (PSI->isHotCallSite(CS, CallerBFI)) {
+        DEBUG(llvm::dbgs() << "Hot callsite.\n");
         Threshold = MaxIfValid(Threshold, Params.HotCallSiteThreshold);
       } else if (PSI->isFunctionEntryHot(&Callee)) {
+        DEBUG(llvm::dbgs() << "Hot callee.\n");
         // If callsite hotness can not be determined, we may still know
         // that the callee is hot and treat it as a weaker hint for threshold
         // increase.
         Threshold = MaxIfValid(Threshold, Params.HintThreshold);
+      } else if (PSI->isColdCallSite(CS, CallerBFI)) {
+        DEBUG(llvm::dbgs() << "Cold callsite.\n");
+        Threshold = MinIfValid(Threshold, Params.ColdCallSiteThreshold);
       } else if (PSI->isFunctionEntryCold(&Callee)) {
+        DEBUG(llvm::dbgs() << "Cold callee.\n");
         Threshold = MinIfValid(Threshold, Params.ColdThreshold);
       }
     }
   }
 
   // Finally, take the target-specific inlining threshold multiplier into
   // account.
   Threshold *= TTI.getInliningThresholdMultiplier();
bool CallAnalyzer::visitCallSite(CallSite CS) {
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
   auto IndirectCallParams = Params;
   IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
-  CallAnalyzer CA(TTI, GetAssumptionCache, PSI, *F, CS, IndirectCallParams);
+  CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, *F, CS,
+                  IndirectCallParams);
   if (CA.analyzeCall(CS)) {
     // We were able to inline the indirect call! Subtract the cost from the
     // threshold to get the bonus we want to apply, but don't go below zero.
     Cost -= std::max(0, CA.getThreshold() - CA.getCost());
   }
 
   return Base::visitCallSite(CS);
 }
static bool functionsHaveCompatibleAttributes(Function *Caller,
                                               TargetTransformInfo &TTI) {
   return TTI.areInlineCompatible(Caller, Callee) &&
          AttributeFuncs::areInlineCompatible(*Caller, *Callee);
 }
 
 InlineCost llvm::getInlineCost(
     CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
     std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
+    Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
     ProfileSummaryInfo *PSI) {
   return getInlineCost(CS, CS.getCalledFunction(), Params, CalleeTTI,
-                       GetAssumptionCache, PSI);
+                       GetAssumptionCache, GetBFI, PSI);
 }
 
 InlineCost llvm::getInlineCost(
     CallSite CS, Function *Callee, const InlineParams &Params,
     TargetTransformInfo &CalleeTTI,
     std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
+    Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
     ProfileSummaryInfo *PSI) {
 
   // Cannot inline indirect calls.
   if (!Callee)
     return llvm::InlineCost::getNever();
 
   // Calls to functions with always-inline attributes should be inlined
   // whenever possible.
InlineCost llvm::getInlineCost(
   // we have *a* correct implementation of the source level function.
   if (Callee->isInterposable() || Callee->hasFnAttribute(Attribute::NoInline) ||
       CS.isNoInline())
     return llvm::InlineCost::getNever();
 
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
                      << "...\n");
 
-  CallAnalyzer CA(CalleeTTI, GetAssumptionCache, PSI, *Callee, CS, Params);
+  CallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, *Callee, CS,
+                  Params);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();
   if (ShouldInline && CA.getCost() >= CA.getThreshold())
else
     Params.DefaultThreshold = Threshold;
 
   // Set the HintThreshold knob from the -inlinehint-threshold.
   Params.HintThreshold = HintThreshold;
 
   // Set the HotCallSiteThreshold knob from the -hot-callsite-threshold.
   Params.HotCallSiteThreshold = HotCallSiteThreshold;
 
+  // Set the ColdCallSiteThreshold knob from the -cold-callsite-threshold.
+  Params.ColdCallSiteThreshold = ColdCallSiteThreshold;
+
   // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
   // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
   // -inlinehint-threshold commandline option is not explicitly given. If that
   // option is present, then its value applies even for callees with size and
   // minsize attributes.
   // If the -inline-threshold is not specified, set the ColdThreshold from the
   // -inlinecold-threshold even if it is not explicitly passed. If
   // -inline-threshold is specified, then -inlinecold-threshold needs to be

lib/Analysis/ProfileSummaryInfo.cpp

 //===- ProfileSummaryInfo.cpp - Global profile summary information --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains a pass that provides access to the global profile summary
 // information.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CallSite.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ProfileSummary.h"
 using namespace llvm;
 
 // The following two parameters determine the threshold for a count to be
 // considered hot/cold. These two parameters are percentile values (multiplied
 // by 10000). If the counts are sorted in descending order, the minimum count to
bool ProfileSummaryInfo::isHotBB(const BasicBlock *B, BlockFrequencyInfo *BFI) {
   // Use extractProfTotalWeight to get BB count.
   // For Sample PGO, BFI may not provide accurate BB count due to errors
   // magnified during sample count propagation. This serves as a backup plan
   // to ensure all hot BB will not be missed.
   // The query currently has false positives as branch instruction cloning does
   // not update/scale branch weights. Unlike false negatives, this will not cause
   // performance problem.
   uint64_t TotalCount;
-  if (B->getTerminator()->extractProfTotalWeight(TotalCount) &&
-      isHotCount(TotalCount))
+  auto *TI = B->getTerminator();
+  if (isa<ReturnInst>(TI))
+    return false;
+  if (TI->extractProfTotalWeight(TotalCount) && isHotCount(TotalCount))
     return true;
   return false;
 }
 
+bool ProfileSummaryInfo::isColdBB(const BasicBlock *B,
+                                  BlockFrequencyInfo *BFI) {
+  auto Count = BFI->getBlockProfileCount(B);
+  return Count && isColdCount(*Count);
+}
+
+bool ProfileSummaryInfo::isHotCallSite(const CallSite &CS,
+                                       BlockFrequencyInfo *BFI) {
+  auto *CallInst = CS.getInstruction();
+  if (!CS)
+    return false;
+  // Check if there is a profile metadata on the instruction. If it is present,
+  // determine hotness solely based on that.
+  uint64_t TotalCount;
+  if (CallInst->extractProfTotalWeight(TotalCount))
+    return isHotCount(TotalCount);
+  return BFI && isHotBB(CallInst->getParent(), BFI);
+}
+
+bool ProfileSummaryInfo::isColdCallSite(const CallSite &CS,
+                                        BlockFrequencyInfo *BFI) {
+  auto *CallInst = CS.getInstruction();
+  if (!CS)
+    return false;
+  // Check if there is a profile metadata on the instruction. If it is present,
+  // and tells that the callsite is not cold, then return false;
+  uint64_t TotalCount;
+  if (CallInst->extractProfTotalWeight(TotalCount) && !isColdCount(TotalCount))
+    return false;
+  return BFI && isColdBB(CallInst->getParent(), BFI);
+}
+
 INITIALIZE_PASS(ProfileSummaryInfoWrapperPass, "profile-summary-info",
                 "Profile summary info", false, true)
 
 ProfileSummaryInfoWrapperPass::ProfileSummaryInfoWrapperPass()
     : ImmutablePass(ID) {
   initializeProfileSummaryInfoWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 

lib/Transforms/IPO/InlineSimple.cpp

public:
 
   InlineCost getInlineCost(CallSite CS) override {
     Function *Callee = CS.getCalledFunction();
     TargetTransformInfo &TTI = TTIWP->getTTI(*Callee);
     std::function<AssumptionCache &(Function &)> GetAssumptionCache =
         [&](Function &F) -> AssumptionCache & {
       return ACT->getAssumptionCache(F);
     };
-    return llvm::getInlineCost(CS, Params, TTI, GetAssumptionCache, PSI);
+    return llvm::getInlineCost(CS, Params, TTI, GetAssumptionCache,
+                               /*GetBFI=*/None, PSI);
   }
 
   bool runOnSCC(CallGraphSCC &SCC) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   TargetTransformInfoWrapperPass *TTIWP;
 

lib/Transforms/IPO/Inliner.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DiagnosticInfo.h"
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
   Module &M = *InitialC.begin()->getFunction().getParent();
   ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M);
 
   std::function<AssumptionCache &(Function &)> GetAssumptionCache =
       [&](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
+  auto GetBFILambda = [&](Function &F) -> BlockFrequencyInfo & {
+    return FAM.getResult<BlockFrequencyAnalysis>(F);
+  };
 
-  // Setup the data structure used to plumb customization into the
-  // `InlineFunction` routine.
-  InlineFunctionInfo IFI(/*cg=*/nullptr, &GetAssumptionCache);
+  function_ref<BlockFrequencyInfo &(Function &)> GetBFI(GetBFILambda);
 
   auto GetInlineCost = [&](CallSite CS) {
     Function &Callee = *CS.getCalledFunction();
     auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
-    return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, PSI);
+    return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, GetBFI,
+                         PSI);
   };
 
   // We use a worklist of nodes to process so that we can handle if the SCC
   // structure changes and some nodes are no longer part of the current SCC. We
   // also need to use an updatable pointer for the SCC as a consequence.
   SmallVector<LazyCallGraph::Node *, 16> Nodes;
   for (auto &N : InitialC)
     Nodes.push_back(&N);
while (!Calls.empty()) {
       if (InlineHistoryID != -1 &&
           InlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory))
         continue;
 
       // Check whether we want to inline this callsite.
       if (!shouldInline(CS, GetInlineCost, ORE))
         continue;
 
+      // Setup the data structure used to plumb customization into the
+      // `InlineFunction` routine.
+      InlineFunctionInfo IFI(
+          /*cg=*/nullptr, &GetAssumptionCache,
+          &FAM.getResult<BlockFrequencyAnalysis>(*(CS.getCaller())),
+          &FAM.getResult<BlockFrequencyAnalysis>(Callee));
+
       if (!InlineFunction(CS, IFI))
         continue;
       DidInline = true;
       InlinedCallees.insert(&Callee);
 
       // Add any new callsites to defined functions to the worklist.
       if (!IFI.InlinedCallSites.empty()) {
         int NewHistoryID = InlineHistory.size();

lib/Transforms/Utils/InlineFunction.cpp

 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 
 using namespace llvm;
 
 static cl::opt<bool>
 EnableNoAliasConversion("enable-noalias-to-md-conversion", cl::init(true),
   cl::Hidden,
   cl::desc("Convert noalias attributes to metadata during inlining."));
for (BasicBlock::iterator BI = FI->begin(), BE = FI->end();
       // Don't update static allocas, as they may get moved later.
       if (auto *AI = dyn_cast<AllocaInst>(BI))
         if (allocaWouldBeStaticInEntry(AI))
           continue;
 
       BI->setDebugLoc(TheCallDL);
     }
   }
 }
+/// Update the block frequencies of the caller after a callee has been inlined.
+///
+/// Each block cloned into the caller has its block frequency scaled by the
+/// ratio of CallSiteFreq/CalleeEntryFreq. This ensures that the cloned copy of
+/// callee's entry block gets the same freqquency as the callsite block and the
+/// relative frequencies of all cloned blocks remain the same after cloning.
+static void updateCallerBFI(BasicBlock *CallSiteBlock,
+                            const ValueToValueMapTy &VMap,
+                            BlockFrequencyInfo *CallerBFI,
+                            BlockFrequencyInfo *CalleeBFI,
+                            const BasicBlock &CalleeEntryBlock) {
+  SmallVector<BasicBlock *, 16> ClonedBBs;
+  for (auto const &Entry : VMap) {
+    if (!isa<BasicBlock>(Entry.first) || !Entry.second)
+      continue;
+    const BasicBlock *OrigBB = cast<BasicBlock>(Entry.first);
+    BasicBlock *ClonedBB = cast<BasicBlock>(Entry.second);
+    ClonedBBs.push_back(ClonedBB);
+    CallerBFI->setBlockFreq(ClonedBB,
+                            CalleeBFI->getBlockFreq(OrigBB).getFrequency());
+  }
+  BasicBlock *EntryClone = cast<BasicBlock>(VMap.lookup(&CalleeEntryBlock));
+  CallerBFI->setBlockFreqAndScale(
+      EntryClone, CallerBFI->getBlockFreq(CallSiteBlock).getFrequency(),
+      ClonedBBs);
+}
+
+/// Update the entry count of callee after inlining.
+///
+/// The callsite's block count is subtracted from the callee's function entry
+/// count.
+static void updateCalleeCount(BlockFrequencyInfo &CallerBFI, BasicBlock *CallBB,
+                              Function *Callee) {
+  // If the callee has a original count of N, and the estimated count of
+  // callsite is M, the new callee count is set to N - M. M is estimated from
+  // the caller's entry count, its entry block frequency and the block frequency
+  // of the callsite.
+  Optional<uint64_t> CalleeCount = Callee->getEntryCount();
+  if (!CalleeCount)
+    return;
+  Optional<uint64_t> CallSiteCount = CallerBFI.getBlockProfileCount(CallBB);
+  if (!CallSiteCount)
+    return;
+  // Since CallSiteCount is an estimate, it could exceed the original callee
+  // count and has to be set to 0.
+  if (CallSiteCount.getValue() > CalleeCount.getValue())
+    Callee->setEntryCount(0);
+  else
+    Callee->setEntryCount(CalleeCount.getValue() - CallSiteCount.getValue());
+}
 
 /// This function inlines the called function into the basic block of the
 /// caller. This returns false if it is not possible to inline this call.
 /// The program is still in a well defined state if this occurs though.
 ///
 /// Note that this only does one level of inlining.  For example, if the
 /// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
 /// exists in the instruction stream.  Similarly this will inline a recursive
 /// function by one level.
 bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
                           AAResults *CalleeAAR, bool InsertLifetime) {
   Instruction *TheCall = CS.getInstruction();
   assert(TheCall->getParent() && TheCall->getParent()->getParent() &&
          "Instruction not in function!");
 
   // If IFI has any state in it, zap it before we fill it in.
   IFI.reset();
-  
-  const Function *CalledFunc = CS.getCalledFunction();
+  Function *CalledFunc = CS.getCalledFunction();
   if (!CalledFunc ||              // Can't inline external function or indirect
       CalledFunc->isDeclaration() || // call, or call to a vararg function!
       CalledFunc->getFunctionType()->isVarArg()) return false;
 
   // The inliner does not know how to inline through calls with operand bundles
   // in general ...
   if (CS.hasOperandBundles()) {
     for (int i = 0, e = CS.getNumOperandBundles(); i != e; ++i) {
       uint32_t Tag = CS.getOperandBundleAt(i).getTagID();
       // ... but it knows how to inline through "deopt" operand bundles ...
       if (Tag == LLVMContext::OB_deopt)
         continue;
       // ... and "funclet" operand bundles.
       if (Tag == LLVMContext::OB_funclet)
         continue;
 
       return false;
     }
   }
 
   // If the call to the callee cannot throw, set the 'nounwind' flag on any
   // calls that we inline.
   bool MarkNoUnwind = CS.doesNotThrow();
 
   BasicBlock *OrigBB = TheCall->getParent();
   Function *Caller = OrigBB->getParent();
 
   // GC poses two hazards to inlining, which only occur when the callee has GC:
   //  1. If the caller has no GC, then the callee's GC must be propagated to the
   //     caller.
   //  2. If the caller has a differing GC, it is invalid to inline.
   if (CalledFunc->hasGC()) {
     if (!Caller->hasGC())
       Caller->setGC(CalledFunc->getGC());
     else if (CalledFunc->getGC() != Caller->getGC())
       return false;
   }
 
   // Get the personality function from the callee if it contains a landing pad.
   Constant *CalledPersonality =
       CalledFunc->hasPersonalityFn()
           ? CalledFunc->getPersonalityFn()->stripPointerCasts()
bool llvm::InlineFunction(CallSite CS, InlineFunctionInfo &IFI,
   // Get an iterator to the last basic block in the function, which will have
   // the new function inlined after it.
   Function::iterator LastBlock = --Caller->end();
 
   // Make sure to capture all of the return instructions from the cloned
   // function.
   SmallVector<ReturnInst*, 8> Returns;
   ClonedCodeInfo InlinedFunctionInfo;
   Function::iterator FirstNewBlock;
 
   { // Scope to destroy VMap after cloning.
     ValueToValueMapTy VMap;
     // Keep a list of pair (dst, src) to emit byval initializations.
     SmallVector<std::pair<Value*, Value*>, 4> ByValInit;
 
     auto &DL = Caller->getParent()->getDataLayout();
 
     assert(CalledFunc->arg_size() == CS.arg_size() &&
Function::iterator FirstNewBlock;
 
     // We want the inliner to prune the code as it copies.  We would LOVE to
     // have no dead or constant instructions leftover after inlining occurs
     // (which can happen, e.g., because an argument was constant), but we'll be
     // happy with whatever the cloner can do.
     CloneAndPruneFunctionInto(Caller, CalledFunc, VMap,
                               /*ModuleLevelChanges=*/false, Returns, ".i",
                               &InlinedFunctionInfo, TheCall);
-
     // Remember the first block that is newly cloned over.
     FirstNewBlock = LastBlock; ++FirstNewBlock;
 
+    if (IFI.CallerBFI != nullptr && IFI.CalleeBFI != nullptr) {
+      // Update the BFI of blocks cloned into the caller.
+      updateCallerBFI(OrigBB, VMap, IFI.CallerBFI, IFI.CalleeBFI,
+                      CalledFunc->front());
+      // Update the profile count of callee.
+      updateCalleeCount(*IFI.CallerBFI, OrigBB, CalledFunc);
+    }
+
     // Inject byval arguments initialization.
     for (std::pair<Value*, Value*> &Init : ByValInit)
       HandleByValArgumentInit(Init.first, Init.second, Caller->getParent(),
                               &*FirstNewBlock, IFI);
 
     Optional<OperandBundleUse> ParentDeopt =
         CS.getOperandBundle(LLVMContext::OB_deopt);
     if (ParentDeopt) {
if (Returns.size() > 1) {
     TheCall->replaceAllUsesWith(UndefValue::get(TheCall->getType()));
   }
 
   // Since we are now done with the Call/Invoke, we can delete it.
   TheCall->eraseFromParent();
 
   // If we inlined any musttail calls and the original return is now
   // unreachable, delete it.  It can only contain a bitcast and ret.
   if (InlinedMustTailCalls && pred_begin(AfterCallBB) == pred_end(AfterCallBB))
     AfterCallBB->eraseFromParent();
+  else if (IFI.CallerBFI) {
+    // Copy original BB's block frequency to AfterCallBB
+    IFI.CallerBFI->setBlockFreq(
+        AfterCallBB, IFI.CallerBFI->getBlockFreq(OrigBB).getFrequency());
+  }
 
   // We should always be able to fold the entry block of the function into the
   // single predecessor of the block...
   assert(cast<BranchInst>(Br)->isUnconditional() && "splitBasicBlock broken!");
   BasicBlock *CalleeEntry = cast<BranchInst>(Br)->getSuccessor(0);
 
   // Splice the code entry block into calling block, right before the
   // unconditional branch.
   CalleeEntry->replaceAllUsesWith(OrigBB);  // Update PHI nodes

test/Transforms/Inline/function-count-update-2.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -S | FileCheck %s
+
+; This tests that the function count of a callee gets correctly updated after it
+; has been inlined into a two callsites.
+
+; CHECK: @callee() !prof [[COUNT:![0-9]+]]
+define i32 @callee() !prof !1 {
+  ret i32 0
+}
+
+define i32 @caller1() !prof !2 {
+  %i = call i32 @callee()
+  ret i32 %i
+}
+
+define i32 @caller2() !prof !3 {
+  %i = call i32 @callee()
+  ret i32 %i
+}
+
+!llvm.module.flags = !{!0}
+; CHECK: [[COUNT]] = !{!"function_entry_count", i64 0}
+!0 = !{i32 1, !"MaxFunctionCount", i32 1000}
+!1 = !{!"function_entry_count", i64 1000}
+!2 = !{!"function_entry_count", i64 600}
+!3 = !{!"function_entry_count", i64 400}
+

test/Transforms/Inline/function-count-update-3.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -S -inline-threshold=50 | FileCheck %s
+
+; This tests that the function count of a function gets properly scaled after 
+; inlining a call chain leading to the function.
+; Function a calls c with count 200 (C1)
+; Function b calls c with count 300
+; Function c calls e with count 250 (C2)
+; Entry count of e is 500 (C3)
+; c->e inlining does not happen since the cost exceeds threshold.
+; c then inlined into a.
+; e now gets inlined into a (through c) since the branch condition in e is now
+; known and hence the cost gets reduced.
+; Estimated count of a->e callsite = C2 * (C1 / C3)
+; Estimated count of a->e callsite = 250 * (200 / 500) = 100
+; Remaining count of e = C3 - 100 = 500 - 100 = 400
+
+@data = external global i32
+
+define i32 @a(i32 %a1) !prof !1 {
+  %a2 = call i32 @c(i32 %a1, i32 1)
+  ret i32 %a2
+}
+
+define i32 @b(i32 %b1) !prof !2 {
+  %b2 = call i32 @c(i32 %b1, i32 %b1)
+  ret i32 %b2
+}
+
+declare void @ext();
+
+define i32 @c(i32 %c1, i32 %c100) !prof !3 {
+  call void @ext()
+  %cond = icmp sle i32 %c1, 1
+  br i1 %cond, label %cond_true, label %cond_false
+
+cond_false:
+  ret i32 0
+
+cond_true:
+  %c11 = call i32 @e(i32 %c100)
+  ret i32 %c11
+}
+
+
+; CHECK: @e(i32 %c1) !prof [[COUNT:![0-9]+]]
+define i32 @e(i32 %c1) !prof !4 {
+  %cond = icmp sle i32 %c1, 1
+  br i1 %cond, label %cond_true, label %cond_false
+
+cond_false:
+  call void @ext()
+  %c2 = load i32, i32* @data, align 4
+  %c3 = add i32 %c1, %c2
+  %c4 = mul i32 %c3, %c2
+  %c5 = add i32 %c4, %c2
+  %c6 = mul i32 %c5, %c2
+  %c7 = add i32 %c6, %c2
+  %c8 = mul i32 %c7, %c2
+  %c9 = add i32 %c8, %c2
+  %c10 = mul i32 %c9, %c2
+  ret i32 %c10
+
+cond_true:
+  ret i32 0
+}
+
+!llvm.module.flags = !{!0}
+; CHECK: [[COUNT]] = !{!"function_entry_count", i64 400}
+!0 = !{i32 1, !"MaxFunctionCount", i32 5000}
+!1 = !{!"function_entry_count", i64 200}
+!2 = !{!"function_entry_count", i64 300}
+!3 = !{!"function_entry_count", i64 500}
+!4 = !{!"function_entry_count", i64 500}
+

test/Transforms/Inline/function-count-update.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -S | FileCheck %s
+
+; This tests that the function count of two callees get correctly updated after
+; they have been inlined into two back-to-back callsites in a single basic block
+; in the caller. The callees have the alwaysinline attribute and so they get
+; inlined both with the regular inliner pass and the always inline pass. In
+; both cases, the new count of each callee is the original count minus callsite
+; count which is 200 (since the caller's entry count is 400 and the block
+; containing the calls have a relative block frequency of 0.5).
+
+; CHECK: @callee1(i32 %n) #0 !prof [[COUNT1:![0-9]+]]
+define i32 @callee1(i32 %n) #0 !prof !1 {
+  %cond = icmp sle i32 %n, 10
+  br i1 %cond, label %cond_true, label %cond_false
+
+cond_true:
+  %r1 = add i32 %n, 1
+  ret i32 %r1
+cond_false:
+  %r2 = add i32 %n, 2
+  ret i32 %r2
+}
+
+; CHECK: @callee2(i32 %n) #0 !prof [[COUNT2:![0-9]+]]
+define i32 @callee2(i32 %n) #0 !prof !2 {
+  %r1 = add i32 %n, 1
+  ret i32 %r1
+}
+
+define i32 @caller(i32 %n) !prof !3 {
+  %cond = icmp sle i32 %n, 100
+  br i1 %cond, label %cond_true, label %cond_false
+
+cond_true:
+  %i = call i32 @callee1(i32 %n)
+  %j = call i32 @callee2(i32 %i)
+  ret i32 %j
+cond_false:
+  ret i32 0
+}
+
+!llvm.module.flags = !{!0}
+; CHECK: [[COUNT1]] = !{!"function_entry_count", i64 800}
+; CHECK: [[COUNT2]] = !{!"function_entry_count", i64 1800}
+!0 = !{i32 1, !"MaxFunctionCount", i32 1000}
+!1 = !{!"function_entry_count", i64 1000}
+!2 = !{!"function_entry_count", i64 2000}
+!3 = !{!"function_entry_count", i64 400}
+attributes #0 = { alwaysinline }
+

test/Transforms/Inline/inline-cold-callee.ll

 ; RUN: opt < %s -inline -inlinecold-threshold=0 -S | FileCheck %s
-; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inlinecold-threshold=0 -S | FileCheck %s
 
 ; This tests that a cold callee gets the (lower) inlinecold-threshold even without
 ; Cold hint and does not get inlined because the cost exceeds the inlinecold-threshold.
 ; A callee with identical body does gets inlined because cost fits within the
 ; inline-threshold
 
 define i32 @callee1(i32 %x) !prof !21 {
   %x1 = add i32 %x, 1
; CHECK-LABEL: @callee2(
   ret i32 %x3
 }
 
 define i32 @caller2(i32 %y1) !prof !22 {
 ; CHECK-LABEL: @caller2(
 ; CHECK: call i32 @callee2
 ; CHECK-NOT: call i32 @callee1
 ; CHECK: ret i32 %x3.i
   %y2 = call i32 @callee2(i32 %y1)
   %y3 = call i32 @callee1(i32 %y2)
   ret i32 %y3
 }
 
 declare void @extern()
 
 !llvm.module.flags = !{!1}
 !21 = !{!"function_entry_count", i64 100}
 !22 = !{!"function_entry_count", i64 1}

test/Transforms/Inline/inline-cold-callsite.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-threshold=100 -inline-cold-callsite-threshold=0 -S | FileCheck %s
+
+; This tests that a cold callsite gets the inline-cold-callsite-threshold
+; and does not get inlined. Another callsite to an identical callee that
+; is not cold gets inlined because cost is below the inline-threshold.
+
+define i32 @callee1(i32 %x) !prof !21 {
+  %x1 = add i32 %x, 1
+  %x2 = add i32 %x1, 1
+  %x3 = add i32 %x2, 1
+  call void @extern()
+  ret i32 %x3
+}
+
+define i32 @callee2(i32 %x) !prof !21 {
+; CHECK-LABEL: @callee2(
+  %x1 = add i32 %x, 1
+  %x2 = add i32 %x1, 1
+  %x3 = add i32 %x2, 1
+  call void @extern()
+  ret i32 %x3
+}
+
+define i32 @caller(i32 %n) !prof !22 {
+; CHECK-LABEL: @caller(
+  %cond = icmp sle i32 %n, 100
+  br i1 %cond, label %cond_true, label %cond_false, !prof !0
+
+cond_true:
+; CHECK-NOT: call i32 @callee1
+; CHECK: ret i32 %x3.i
+  %i = call i32 @callee1(i32 %n)
+  ret i32 %i
+cond_false:
+; CHECK: call i32 @callee2
+; CHECK: ret i32 %j
+  %j = call i32 @callee2(i32 %n)
+  ret i32 %j
+}
+declare void @extern()
+
+!0 = !{!"branch_weights", i32 200, i32 1}
+
+!llvm.module.flags = !{!1}
+!21 = !{!"function_entry_count", i64 200}
+!22 = !{!"function_entry_count", i64 200}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 1000}
+!6 = !{!"MaxInternalCount", i64 1}
+!7 = !{!"MaxFunctionCount", i64 1000}
+!8 = !{!"NumCounts", i64 3}
+!9 = !{!"NumFunctions", i64 3}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13, !14}
+!12 = !{i32 10000, i64 1000, i32 1}
+!13 = !{i32 999000, i64 1000, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}

test/Transforms/Inline/inline-hot-callee.ll

 ; RUN: opt < %s -inline -inline-threshold=0 -inlinehint-threshold=100 -S | FileCheck %s
-; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-threshold=0 -inlinehint-threshold=100 -S | FileCheck %s
 
 ; This tests that a hot callee gets the (higher) inlinehint-threshold even without
 ; inline hints and gets inlined because the cost is less than inlinehint-threshold.
 ; A cold callee with identical body does not get inlined because cost exceeds the
 ; inline-threshold
 
 define i32 @callee1(i32 %x) !prof !21 {
   %x1 = add i32 %x, 1

test/Transforms/Inline/inline-hot-callsite-2.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-threshold=0 -inlinehint-threshold=0 -hot-callsite-threshold=100 -S | FileCheck %s
+
+; This tests that a callsite which is determined to be hot based on the caller's
+; entry count and the callsite block frequency gets the hot-callsite-threshold.
+; Another callsite to an identical callee that is not hot does not get inlined
+; because cost exceeds the inline-threshold. inlinthint-threshold is set to 0
+; to ensure callee's hotness is not used to boost the threshold.
+
+define i32 @callee1(i32 %x) !prof !21 {
+  %x1 = add i32 %x, 1
+  %x2 = add i32 %x1, 1
+  %x3 = add i32 %x2, 1
+  call void @extern()
+  ret i32 %x3
+}
+
+define i32 @callee2(i32 %x) !prof !21 {
+; CHECK-LABEL: @callee2(
+  %x1 = add i32 %x, 1
+  %x2 = add i32 %x1, 1
+  %x3 = add i32 %x2, 1
+  call void @extern()
+  ret i32 %x3
+}
+
+define i32 @caller(i32 %n) !prof !22 {
+; CHECK-LABEL: @caller(
+  %cond = icmp sle i32 %n, 100
+  br i1 %cond, label %cond_true, label %cond_false, !prof !0
+
+cond_true:
+; CHECK-NOT: call i32 @callee1
+; CHECK: ret i32 %x3.i
+  %i = call i32 @callee1(i32 %n)
+  ret i32 %i
+cond_false:
+; CHECK: call i32 @callee2
+; CHECK: ret i32 %j
+  %j = call i32 @callee2(i32 %n)
+  ret i32 %j
+}
+declare void @extern()
+
+!0 = !{!"branch_weights", i32 64, i32 4}
+
+!llvm.module.flags = !{!1}
+!21 = !{!"function_entry_count", i64 200}
+!22 = !{!"function_entry_count", i64 200}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 1000}
+!6 = !{!"MaxInternalCount", i64 1}
+!7 = !{!"MaxFunctionCount", i64 1000}
+!8 = !{!"NumCounts", i64 3}
+!9 = !{!"NumFunctions", i64 3}
+!10 = !{!"DetailedSummary", !11}
+!11 = !{!12, !13, !14}
+!12 = !{i32 10000, i64 100, i32 1}
+!13 = !{i32 999000, i64 100, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}