[PartialInlining] Add frequency based cost analysis

[davidxl]

Summary

In this patch, the runtime and size cost of making calls to outlined function is computed and compared with potential savings of partial inlining.

[davidxl]

Update test case -- added a cold region test.

[eraman]

I am not fully sure if this cost model - first check if the function is a suitable candidate for outlining and then use inliner's cost analysis to inline the original function to its callsites - is the right one. Specifically, I'm thinking if both should be done on a per-callsite basis.

lib/Transforms/IPO/PartialInlining.cpp

396

This should ideally be in InlineCost. Not all instructions have the same cost (eg. switch). At the least it should be documented here.

413

nit: This is also in multiples of InstrCost like SizeCost above. Using a consistent naming will make this more readable.

443

I wonder if it is better to first clone the function and then call this isPartialInliningBeneficial. We might end up cloning it unnecessarily, but could reuse all these analyses which are computed on the duplicate function later.

453

std::max?

458

NonWeightedSavings above only includes the savings due to elimination of call and arg setup. Since inlining also can eliminate instructions in a given context, we are likely undercounting the savings here.

lib/Transforms/Utils/CodeExtractor.cpp

701

This should be multiplied by InstrCost.

705

This is different from how it is used in InlineCost. In inline cost analysis, there is no separate static and runtime costs and even CallPenalty is meant to model static cost (saving and restoring registers etc). It is clear that they need to be modeled separately, but for now I prefer replicating what is in InlineCost.cpp and may be assign both the same value.

[davidxl]

Addressed review feedbacks by eraman

[davidxl]

lib/Transforms/IPO/PartialInlining.cpp

396

Added comment.

458

possibly. Since the inlined region is just a set of guarding blocks, the addition benefit is probably not that high.

lib/Transforms/Utils/CodeExtractor.cpp

701

removed the function. Use the actual extracted function to compute instead.

[eraman]

lib/Transforms/IPO/PartialInlining.cpp

103–138

Add an empty line between functions (her and in other places)

376

It wasn't obvious to me why callee entry freq >= outlining call's frequency. I think I understand it now - we ensure the non-return block has a single predecessor and hence can't be in a loop, but a comment above would help.

395

This is not in multiples of InstrCost (and also inliner's switch cost computation is more sophisticated now, but you've the TODO above)

427

may be add an assert that OutlinedFunctionCost >= OutlinedRegionCost to potentially catch any bugs.

589

nullptr instead of 0

lib/Transforms/Utils/CodeExtractor.cpp

23

Why do you need this?

754

Why not grab the (only)user to this function in unswitchFunction and get the basic block from there. It adds some overhead, but IMO is cleaner than this.

[davidxl]

1. Addressed review feedbacks
2. More refactorings and naming cleanups (for consistency)
3. Added handling of function entry count update and a new test case for it.

[davidxl]

lib/Transforms/Utils/CodeExtractor.cpp

23

for getCallsiteCost and getInlineCost interface.

754

can you clarify on this?

[eraman]

lib/Transforms/Utils/CodeExtractor.cpp

23

I don't see any use of those interfaces in CodeExtractor.cpp. Am I missing something?

754

Something like cast<CallInst>(*F->user_begin())->getParent() in unswitchFunction should work right?

[davidxl]

Address feedback -- revert change in CodeExtractor.h and .cc file

Also let the cost analysis only trust PGO and user annotation data. Without PGO, add an option to control the aggressiveness.

[davidxl]

Further tuned cost/benefit computation with SPEC 2k/06 tuning. Get speedups in a few benchmarks and fixed the regression in perlbmk (many cases with early return branch which is never taken).

[dberris]

Drive-by-comment.

lib/Transforms/IPO/PartialInlining.cpp

624–625

nit: No need for {}'s in single-line bodies.

[davidxl]

Remove { }

[eraman]

In terms of correctness and heuristics this looks good. I'v a few comments that are mostly stylistic and documentation issues.

lib/Transforms/IPO/PartialInlining.cpp

49

make this cl::ReallyHidden since it is only used in testing

65

The description string and comment does not make it clear whether this is the upper limit (I think it is) or not.

103–138

an empty line below

119

typo: successfully -> successful

123

Empty line?

137

Not sure if this has been clang-formatted because it looks like the next two lines can be merged into one (I may be wrong)

140

Inline -> InlineCost. usedto->used to

352

I prefer auto here and below since the get methods clearly convey the type.

361

This certainly need some more comments. Essentially you don't want to over-estimate the savings and hence you assume that outlinined region is at least OutlineRegionFreqPercent likely even if BFI tells otherwise.

362

Flip the branch condition and so an early return?

363

std::min

372

auto here and in the next line.

455

move the BFI computation to a lambda maybe?

602

Instead of using two variables with similar names, why not initialize the uint64_t to 0 above the previous if and inside the if do F->getEntryCount()->getValue() ?

[davidxl]

lib/Transforms/IPO/PartialInlining.cpp

65

Updated the comment.

137

The ; will be @column 80 which clang-format does not like.

602

Both vars are used later. I changed the second var name to make it look friendiler.

[davidxl]

Address review feedbacks.

[eraman]

LGTM

lib/Transforms/IPO/PartialInlining.cpp

372

I think you can use auto for NormWeightedRCost also.

include/llvm/Transforms/Utils/CodeExtractor.h

public:
     /// \brief Create a code extractor for a loop body.
     ///
     /// Behaves just like the generic code sequence constructor, but uses the
     /// block sequence of the loop.
     CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs = false,
                   BlockFrequencyInfo *BFI = nullptr,
                   BranchProbabilityInfo *BPI = nullptr);
 
+    /// Return the costs of outlining the extracted region.
+    /// The first member of the returned tuple is the estimate size
+    /// cost and the second is runtime cost.
+    std::tuple<int, int> computeOutliningCost();
+
     /// \brief Perform the extraction, returning the new function.
     ///
     /// Returns zero when called on a CodeExtractor instance where isEligible
     /// returns false.
     Function *extractCodeRegion();
 
     /// \brief Test whether this code extractor is eligible.
     ///

lib/Transforms/IPO/PartialInlining.cpp

 // that surrounds the body of the function.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DiagnosticInfo.h"

 
 STATISTIC(NumPartialInlined,
           "Number of callsites functions partially inlined into.");
 
 // Command line option to disable partial-inlining. The default is false:
 static cl::opt<bool>
     DisablePartialInlining("disable-partial-inlining", cl::init(false),
                            cl::Hidden, cl::desc("Disable partial ininling"));
+// This is an option used by testing:
+static cl::opt<bool>
+    SkipCostAnalysis("skip-partial-inlining-cost-analysis", cl::init(false),
+                           cl::Hidden, cl::desc("Skip Cost Analysis"));
 
 static cl::opt<unsigned> MaxNumInlineBlocks(
     "max-num-inline-blocks", cl::init(5), cl::Hidden,
     cl::desc("Max Number of Blocks  To be Partially Inlined"));
 
 // Command line option to set the maximum number of partial inlining allowed
 // for the module. The default value of -1 means no limit.
 static cl::opt<int> MaxNumPartialInlining(
     "max-partial-inlining", cl::init(-1), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Max number of partial inlining. The default is unlimited"));
 
 namespace {
 
 struct FunctionOutliningInfo {
   FunctionOutliningInfo()
       : Entries(), ReturnBlock(nullptr), NonReturnBlock(nullptr),
         ReturnBlockPreds() {}
   // Returns the number of blocks to be inlined including all blocks
   // in Entries and one return block.
   unsigned GetNumInlinedBlocks() const { return Entries.size() + 1; }
 
   // A set of blocks including the function entry that guard
   // the region to be outlined.
   SmallVector<BasicBlock *, 4> Entries;
PartialInlinerImpl(
       std::function<AssumptionCache &(Function &)> *GetAC,
       std::function<TargetTransformInfo &(Function &)> *GTTI,
       Optional<function_ref<BlockFrequencyInfo &(Function &)>> GBFI,
       ProfileSummaryInfo *ProfSI)
       : GetAssumptionCache(GetAC), GetTTI(GTTI), GetBFI(GBFI), PSI(ProfSI) {}
   bool run(Module &M);
   Function *unswitchFunction(Function *F);
 
-  std::unique_ptr<FunctionOutliningInfo> computeOutliningInfo(Function *F);
-
 private:
   int NumPartialInlining = 0;
   std::function<AssumptionCache &(Function &)> *GetAssumptionCache;
   std::function<TargetTransformInfo &(Function &)> *GetTTI;
   Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI;
   ProfileSummaryInfo *PSI;
 
   bool shouldPartialInline(CallSite CS, OptimizationRemarkEmitter &ORE);
   bool IsLimitReached() {
     return (MaxNumPartialInlining != -1 &&
             NumPartialInlining >= MaxNumPartialInlining);
   }
+  CallSite getCallSite(User *U) {
+    CallSite CS;
+    if (CallInst *CI = dyn_cast<CallInst>(U))
+      CS = CallSite(CI);
+    else if (InvokeInst *II = dyn_cast<InvokeInst>(U))
+      CS = CallSite(II);
+    else
+      llvm_unreachable("All uses must be calls");
+    return CS;
+  }
+  CallSite getOneCallSiteTo(Function *F) {
+    User *User = *F->user_begin();
+    return getCallSite(User);
+  }
+  std::tuple<DebugLoc, BasicBlock *> getOneDebugLoc(Function *F) {
+    CallSite CS = getOneCallSiteTo(F);
+
+    DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
+    BasicBlock *Block = CS.getParent();
+    return std::make_tuple(DLoc, Block);
+  }
+
+  // Returns true of the benefit of eliminating the call outweights the
+  // additional runtime cost associated with the new call to the outlined
+  // function (extracted).
+  bool isPartialInliningBeneficial(Function *F, FunctionOutliningInfo *OI);
+  // Returns the cost associated with function outlining:
+  // - The first value is the non-weighted runtime cost for the call sequence
+  //   to the outlined function;
+  // - The second value is the code size estimate of the new call sequence.
+  // - The third value is the size estimate of the original code that is
+  //   extracted into the outlined function.
+  std::tuple<int, int, int>
+  computeOutliningCost(Function *F, const FunctionOutliningInfo *OutliningInfo);
+  std::unique_ptr<FunctionOutliningInfo> computeOutliningInfo(Function *F);
 };
 
 struct PartialInlinerLegacyPass : public ModulePass {
   static char ID; // Pass identification, replacement for typeid
   PartialInlinerLegacyPass() : ModulePass(ID) {
     initializePartialInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
PartialInlinerImpl::computeOutliningInfo(Function *F) {
 
   return OutliningInfo;
 }
 
 bool PartialInlinerImpl::shouldPartialInline(CallSite CS,
                                              OptimizationRemarkEmitter &ORE) {
   // TODO : more sharing with shouldInline in Inliner.cpp
   using namespace ore;
+  if (SkipCostAnalysis)
+    return true;
+
   Instruction *Call = CS.getInstruction();
   Function *Callee = CS.getCalledFunction();
   Function *Caller = CS.getCaller();
   auto &CalleeTTI = (*GetTTI)(*Callee);
   InlineCost IC = getInlineCost(CS, getInlineParams(), CalleeTTI,
                                 *GetAssumptionCache, GetBFI, PSI);
 
   if (IC.isAlways()) {
     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AlwaysInline", Call)
              << NV("Callee", Callee)
              << " should always be fully inlined, not partially");
     return false;
   }
 
   if (IC.isNever()) {
     ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
              << NV("Callee", Callee) << " not partially inlined into "
              << NV("Caller", Caller)
              << " because it should never be inlined (cost=never)");
     return false;
   }
 
   if (!IC) {
-    ORE.emit(OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "TooCostly", Call)
              << NV("Callee", Callee) << " not partially inlined into "
              << NV("Caller", Caller) << " because too costly to inline (cost="
              << NV("Cost", IC.getCost()) << ", threshold="
              << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")");
     return false;
   }
 
   ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "CanBePartiallyInlined", Call)
            << NV("Callee", Callee) << " can be partially inlined into "
            << NV("Caller", Caller) << " with cost=" << NV("Cost", IC.getCost())
            << " (threshold="
            << NV("Threshold", IC.getCostDelta() + IC.getCost()) << ")");
   return true;
 }
 
+std::tuple<int, int, int>
+PartialInlinerImpl::computeOutliningCost(Function *F,
+                                         const FunctionOutliningInfo *OI) {
+  std::vector<BasicBlock *> OutlinedRegion;
+
+  SmallPtrSet<const Value *, 32> EphValues;
+  CodeMetrics::collectEphemeralValues(F, &(*GetAssumptionCache)(*F), EphValues);
+
+  int OutlinedRegionSize = 0;
+  for (BasicBlock &BB : *F) {
+    if (&BB != OI->ReturnBlock &&
+        // Assuming Entry set is small -- do a linear search here.
+        std::find(OI->Entries.begin(), OI->Entries.end(), &BB) ==
+            OI->Entries.end()) {
+      OutlinedRegion.push_back(&BB);
+      for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) {
+        if (isa<DbgInfoIntrinsic>(I))
+          continue;
+        if (EphValues.count(&*I))
+          continue;
+        OutlinedRegionSize += InlineConstants::InstrCost;
+      }
+    }
+  }
+
+  int OutliningSizeCost, OutliningRuntimeCost;
+  std::tie(OutliningSizeCost, OutliningRuntimeCost) =
+      CodeExtractor(OutlinedRegion, nullptr, false, nullptr, nullptr)
+          .computeOutliningCost();
+  return std::make_tuple(OutliningSizeCost, OutliningRuntimeCost,
+                         OutlinedRegionSize);
+}
+
+bool PartialInlinerImpl::isPartialInliningBeneficial(
+    Function *F, FunctionOutliningInfo *OI) {
+  int NonWeightedRcost;
+  int SizeCost;
+  int OutlinedRegionSize;
+
+  if (SkipCostAnalysis)
+    return true;
+
+  std::tie(SizeCost, NonWeightedRcost, OutlinedRegionSize) =
+      computeOutliningCost(F, OI);
+
+  OptimizationRemarkEmitter ORE(F);
+  using namespace ore;
+  DebugLoc DLoc;
+  BasicBlock *Block;
+  std::tie(DLoc, Block) = getOneDebugLoc(F);
+
+  // The call sequence to the outlined function is larger than the original
+  // outlined region size, it does not increase the chances of inlining
+  // 'F' with outlining (The inliner using the size increase to model the
+  // the cost of inlining a callee).
+  if (OutlinedRegionSize < SizeCost) {
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "OutlineRegionTooSmall",
+                                        DLoc, Block)
+             << NV("Function", F)
+             << " not partially inlined into callers (Original Size = "
+             << NV("OutlinedRegionOriginalSize", OutlinedRegionSize)
+             << ", Size of call sequence to outlined function = "
+             << NV("NewSize", SizeCost) << ")");
+    return false;
+  }
+
+  // Now compare with weighted runtime cost:
+  LoopInfo LI{DominatorTree(*F)};
+  BranchProbabilityInfo BPI(*F, LI);
+  BlockFrequencyInfo BFI(*F, BPI, LI);
+
+  BlockFrequency EntryFreq = BFI.getBlockFreq(&F->getEntryBlock());
+  BlockFrequency OutlinedCallFreq = BFI.getBlockFreq(OI->NonReturnBlock);
+  CallSite CS = getOneCallSiteTo(F);
+  const DataLayout &DL = F->getParent()->getDataLayout();
+  // The savings of eliminating the call:
+  int NonWeightedSavings = getCallsiteCost(CS, DL);
+  int Denom = (NonWeightedSavings > NonWeightedRcost ? NonWeightedSavings
+                                                     : NonWeightedRcost);
+  BranchProbability NormWeightedSavings(NonWeightedSavings, Denom);
+  BranchProbability NormWeightedRcost(NonWeightedRcost, Denom);
+  // Weighted saving is smaller than weighted cost, return false
+  if (EntryFreq * NormWeightedSavings < OutlinedCallFreq * NormWeightedRcost) {
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "OutliningCallcostTooHigh",
+                                        DLoc, Block)
+             << NV("Function", F)
+             << " not partially inlined into callers, runtime overhead "
+             << " of making outlined call is too high");
+
+    return false;
+  }
+
+  // Ok, we can partial inline this function.
+  return true;
+}
+
 Function *PartialInlinerImpl::unswitchFunction(Function *F) {
 
   if (F->hasAddressTaken())
     return nullptr;
 
   // Let inliner handle it
   if (F->hasFnAttribute(Attribute::AlwaysInline))
     return nullptr;
 
   if (F->hasFnAttribute(Attribute::NoInline))
     return nullptr;
 
   if (PSI->isFunctionEntryCold(F))
     return nullptr;
 
+  if (F->user_begin() == F->user_end())
+    return nullptr;
+
   std::unique_ptr<FunctionOutliningInfo> OutliningInfo =
       computeOutliningInfo(F);
 
   if (!OutliningInfo)
     return nullptr;
 
+  if (!isPartialInliningBeneficial(F, OutliningInfo.get()))
+    return nullptr;
+
   // Clone the function, so that we can hack away on it.
   ValueToValueMapTy VMap;
   Function *DuplicateFunction = CloneFunction(F, VMap);
   BasicBlock *NewReturnBlock =
       cast<BasicBlock>(VMap[OutliningInfo->ReturnBlock]);
   BasicBlock *NewNonReturnBlock =
       cast<BasicBlock>(VMap[OutliningInfo->NonReturnBlock]);
   DenseSet<BasicBlock *> NewEntries;
Function *PartialInlinerImpl::unswitchFunction(Function *F) {
   DT.recalculate(*DuplicateFunction);
 
   // Manually calculate a BlockFrequencyInfo and BranchProbabilityInfo.
   LoopInfo LI(DT);
   BranchProbabilityInfo BPI(*DuplicateFunction, LI);
   BlockFrequencyInfo BFI(*DuplicateFunction, BPI, LI);
 
   // Extract the body of the if.
   Function *ExtractedFunction =
       CodeExtractor(ToExtract, &DT, /*AggregateArgs*/ false, &BFI, &BPI)
           .extractCodeRegion();
 
   // Inline the top-level if test into all callers.
   std::vector<User *> Users(DuplicateFunction->user_begin(),
                             DuplicateFunction->user_end());
 
   for (User *User : Users) {
-    CallSite CS;
-    if (CallInst *CI = dyn_cast<CallInst>(User))
-      CS = CallSite(CI);
-    else if (InvokeInst *II = dyn_cast<InvokeInst>(User))
-      CS = CallSite(II);
-    else
-      llvm_unreachable("All uses must be calls");
+    CallSite CS = getCallSite(User);
 
     if (IsLimitReached())
       continue;
 
     OptimizationRemarkEmitter ORE(CS.getCaller());
     if (!shouldPartialInline(CS, ORE))
       continue;
 
     DebugLoc DLoc = CS.getInstruction()->getDebugLoc();
     BasicBlock *Block = CS.getParent();
     ORE.emit(OptimizationRemark(DEBUG_TYPE, "PartiallyInlined", DLoc, Block)
              << ore::NV("Callee", F) << " partially inlined into "
              << ore::NV("Caller", CS.getCaller()));
 
     InlineFunctionInfo IFI(nullptr, GetAssumptionCache);
     InlineFunction(CS, IFI);
     NumPartialInlining++;
     // update stats
     NumPartialInlined++;
   }
 
   // Ditch the duplicate, since we're done with it, and rewrite all remaining
   // users (function pointers, etc.) back to the original function.
   DuplicateFunction->replaceAllUsesWith(F);
   DuplicateFunction->eraseFromParent();
 
 
   return ExtractedFunction;
 }
 
 bool PartialInlinerImpl::run(Module &M) {
   if (DisablePartialInlining)
     return false;
 
   std::vector<Function *> Worklist;

lib/Transforms/Utils/CodeExtractor.cpp

 
 #include "llvm/Transforms/Utils/CodeExtractor.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"

     TheSwitch->setCondition(call);
     TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks));
     // Remove redundant case
     TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1));
     break;
   }
 }
 
+// The cost of outlining the region consists of the following parts:
+//   0. The new call/return instruction
+//   1. Input parmater passing
+//   2. Output parameter stack allocation in caller
+//   3. Output parameter pointer passing
+//   4. Output parameter stores (at the exit of the outlined function)
+//   5. Output parmaeter loads (right after the call to the outlined function)
+//   6. For multiple exits region, the branch cost (conditional branch) incurred
+//      aftter the call to outlined function
+// The first returned value is the size cost and the second is estimated
+// runtime cost. The runtime cost models the increased runtime overhead
+// due to the newly created instructions, while the size cost models the
+// size impact of the call sequence to the outlined function.
+std::tuple<int, int> CodeExtractor::computeOutliningCost() {
+  ValueSet inputs, outputs;
+  SmallPtrSet<BasicBlock *, 1> ExitBlocks;
+
+  if (!isEligible())
+    return std::make_tuple(0, 0);
+
+  int RCost = 0, SCost = 0;
+
+  for (BasicBlock *Block : Blocks) {
+    if (dyn_cast<ReturnInst>(Block->getTerminator())) {
+      NumExitBlocks++;
+      continue;
+    }
+    for (succ_iterator SI = succ_begin(Block), SE = succ_end(Block); SI != SE;
+         ++SI) {
+      if (!Blocks.count(*SI))
+        NumExitBlocks++;
+    }
+  }
+
+  // Find inputs to, outputs from the code region.
+  findInputsOutputs(inputs, outputs);
+  // TODO: check parameter attribute, callingConv etc.
+  RCost = (inputs.size() + outputs.size()) * InlineConstants::InstrCost;
+  // For each output parameter, there is cost associated with stack
+  // usage, before return stores, and after call re-loads:
+  RCost += 3 * outputs.size() * InlineConstants::InstrCost;
+  // Branch cost:
+  RCost += NumExitBlocks;
+
+  SCost = RCost;
+  // Now the cost of calling the outlined function itself:
+  RCost += InlineConstants::CallPenalty;
+  SCost += InlineConstants::InstrCost;
+  return std::make_tuple(SCost, RCost);
+}
+
 void CodeExtractor::moveCodeToFunction(Function *newFunction) {
   Function *oldFunc = (*Blocks.begin())->getParent();
   Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList();
   Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList();
 
   for (BasicBlock *Block : Blocks) {
     // Delete the basic block from the old function, and the list of blocks
     oldBlocks.remove(Block);

   }
 
   // Check for no total weight.
   if (BranchDist.Total == 0)
     return;
 
   // Normalize the distribution so that they can fit in unsigned.
   BranchDist.normalize();
 
   // Create normalized branch weights and set the metadata.
   for (unsigned I = 0, E = BranchDist.Weights.size(); I < E; ++I) {
     const auto &Weight = BranchDist.Weights[I];
 
     // Get the weight and update the current BFI.
     BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
     BranchProbability BP(Weight.Amount, BranchDist.Total);
     BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);

test/Transforms/CodeExtractor/ExtractedFnEntryCount.ll

-; RUN: opt < %s -partial-inliner -S | FileCheck %s
+; RUN: opt < %s -partial-inliner -skip-partial-inlining-cost-analysis -S | FileCheck %s
 
 ; This test checks to make sure that the CodeExtractor
 ;  properly sets the entry count for the function that is
 ;  extracted based on the root block being extracted and also
 ;  takes into consideration if the block has edges coming from
 ;  a block that is also being extracted.
 
 define i32 @inlinedFunc(i1 %cond) !prof !1 {

test/Transforms/CodeExtractor/MultipleExitBranchProb.ll

-; RUN: opt < %s -partial-inliner -max-num-inline-blocks=2 -S | FileCheck %s
+; RUN: opt < %s -partial-inliner -max-num-inline-blocks=2 -skip-partial-inlining-cost-analysis -S | FileCheck %s
 
 ; This test checks to make sure that CodeExtractor updates
 ;  the exit branch probabilities for multiple exit blocks.
 
 define i32 @inlinedFunc(i1 %cond) !prof !1 {
 entry:
   br i1 %cond, label %if.then, label %return, !prof !2
 if.then:

test/Transforms/CodeExtractor/PartialInlineHighCost.ll

+; The outlined region has high frequency  and the outlining
+; call sequence is expensive (input, output, multiple exit etc)
+; RUN: opt < %s -partial-inliner -S | FileCheck %s
+; RUN: opt < %s -passes=partial-inliner -S | FileCheck %s
+; RUN: opt < %s -partial-inliner -skip-partial-inlining-cost-analysis -S | FileCheck --check-prefix=NOCOST %s
+; RUN: opt < %s -passes=partial-inliner -skip-partial-inlining-cost-analysis -S | FileCheck  --check-prefix=NOCOST %s
+
+
+; Function Attrs: nounwind
+define i32 @bar(i32 %arg) local_unnamed_addr #0 {
+bb:
+  %tmp = icmp slt i32 %arg, 0
+  br i1 %tmp, label %bb1, label %bb16, !prof !1
+
+bb1:                                              ; preds = %bb
+  %tmp2 = tail call i32 (...) @foo() #0
+  %tmp3 = tail call i32 (...) @foo() #0
+  %tmp4 = tail call i32 (...) @foo() #0
+  %tmp5 = tail call i32 (...) @foo() #0
+  %tmp6 = tail call i32 (...) @foo() #0
+  %tmp7 = tail call i32 (...) @foo() #0
+  %tmp8 = add nsw i32 %arg, 1
+  %tmp9 = tail call i32 @goo(i32 %tmp8) #0
+  %tmp10 = tail call i32 (...) @foo() #0
+  %tmp11 = icmp eq i32 %tmp10, 0
+  br i1 %tmp11, label %bb12, label %bb16
+
+bb12:                                             ; preds = %bb1
+  %tmp13 = tail call i32 (...) @foo() #0
+  %tmp14 = icmp eq i32 %tmp13, 0
+  %tmp15 = select i1 %tmp14, i32 0, i32 3
+  br label %bb16
+
+bb16:                                             ; preds = %bb12, %bb1, %bb
+  %tmp17 = phi i32 [ 2, %bb1 ], [ %tmp15, %bb12 ], [ 0, %bb ]
+  ret i32 %tmp17
+}
+
+; Function Attrs: nounwind
+declare i32 @foo(...) local_unnamed_addr #0
+
+; Function Attrs: nounwind
+declare i32 @goo(i32) local_unnamed_addr #0
+
+; Function Attrs: nounwind
+define i32 @dummy_caller(i32 %arg) local_unnamed_addr #0 {
+bb:
+; CHECK-LABEL: @dummy_caller
+; CHECK-NOT: br i1
+; CHECK-NOT: call{{.*}}bar. 
+; NOCOST-LABEL: @dummy_caller
+; NOCOST: br i1
+; NOCOST: call{{.*}}bar.
+  %tmp = tail call i32 @bar(i32 %arg)
+  ret i32 %tmp
+}
+
+attributes #0 = { nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0 (trunk 301898)"}
+!1 = !{!"branch_weights", i32 2000, i32 1}

test/Transforms/CodeExtractor/X86/InheritTargetAttributes.ll

-; RUN: opt < %s -partial-inliner | llc -filetype=null
-; RUN: opt < %s -partial-inliner -S | FileCheck %s
+; RUN: opt < %s -partial-inliner -skip-partial-inlining-cost-analysis | llc -filetype=null
+; RUN: opt < %s -partial-inliner -skip-partial-inlining-cost-analysis -S | FileCheck %s
 ; This testcase checks to see if CodeExtractor properly inherits
 ;   target specific attributes for the extracted function. This can
 ;   cause certain instructions that depend on the attributes to not
 ;   be lowered. Like in this test where we try to 'select' the blendvps
 ;   intrinsic on x86 that requires the +sse4.1 target feature.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"