Estimate speedup due to inlining and use that to adjust threshold.

[eraman]

Summary

This adds a heuristic that estimates the speedup due to inlining a callsite and increases thresholds for callsites that have an estimated speedup above a configurable minimum. The speedup is define as WeightedSavings / (WeightedCost + WeightedSavings). WeightedCost above is obtained by weighting the cost (already computed by the analysis) per basic block with the block's frequency. In order to compute the WeightedSavings, we keep track of savings due to inlining. There are 3 components to the Savings: a. The cost savings due to elimination of call overhead and argument setup overhead, b. The cost savings due to SROA, and c. The cost savings due to elimination of instructions after inlining. Note that the savings does not include the cost of blocks that are unreachable in the call context since, irresepective of inlining, those blocks are not reachable in a dynamic sense. Similar to WeightedCost, WeightedSavings is calculated by weighting the savings per block with its frequency.

This analysis is triggered only when the callsite's frequency relative to caller's entry exceeds a configurable parameter. In my experiments, I noticed that not having this filter results in increased code size in the cold regions.

I have done some parameter tuning using a hacked up version of this code (to work on the old PM) on a set of internal benchmarks. I do expect more tuning to be done on a broader set of benchmarks. Since this is active only with the new PM based pipeline, I haven't added a flag to disable this but I'll add them if you prefer so.

[efriedma]

lib/Analysis/InlineCost.cpp

1356

CalleeBFI is unused?

[eraman]

Thanks for the comment!

lib/Analysis/InlineCost.cpp

1356

Ouch. This is badly broken. In two places where I should have used CalleeBFI, I've used CallerBFI. getBlockFreq returns 0 if the BB is not in the function whose BFI is used. The tests still pass because I've used getEntryFreq of Caller (instead of Callee) which still returns a valid value and the weighted savings associated with the entry block (elimination of the call and arg setup) is enough to result in the speedup. I'll send a revised patch tomorrow.

[eraman]

• Use CalleeBFI to get the current block's frequency.
• Move accumulateCost into this patch instead of it being part of the dependent patch.

[davidxl]

lib/Analysis/InlineCost.cpp

89

Does this mean globally hot callsites may not get the speed up bonus if their relative frequency to caller entry is smaller than 8? while a less hot callsite may get both hot callsite bump and big speedup bump?

246

Document the method.

247

hasLargeSpeedup ?

508

should this be called inside the lambda?

541

why does this need to be guarded here?

989

Why is the guard needed here?

1089

Perhaps at least add parameter passing to the savings?

[eraman]

Thanks for the comments.

lib/Analysis/InlineCost.cpp

89

That is possible. The easy fix is to check if the callsite is hot or if it's relative frequency exceeds this threshold. I have made this change.

541

We want to give a bonus if the speedup only happens due to inlining. In most cases, if Evaluate returns a constant, then we would have looked up the SimplifiedValues. But it is also possible that the IR actually has an instruction with two constant operands which were not cleaned by earlier simplification pass and we don't want to consider it an inlining benefit (since a later simplification pass will simplify it). I don't think it is very likely in a reasonable pass pipeline, but explicitly having this guard makes the intention cleaner.

989

Same explanation as above.

[eraman]

Rebase and address David's comments.

[davidxl]

lib/Analysis/InlineCost.cpp

541

Can you add a brief comment about this?

557

Better filter cold callsite out too.

989

A brief comment.

test/Transforms/Inline/speedup-analysis.ll

4

what do the savings come from in this case? just the call overhead?

[chandlerc]

Some initial (minor) comments. It'd also help I think to rebase this as some of the refactorings land.

lib/Analysis/InlineCost.cpp

80

nit: Please use vertical whitespace before the comment for the second flag.

More substantive comment, what unit is this? The "desc" string only says "speedup", but it isn't clear if you mean "10% faster after inlining"? If so, that seems a surprisingly low threshold...

90–91

The flag seems to indicate this is the value of the frequency itself... the comment seems to indicate it is relative... Makes it hard for me to understand the value used...

174

I think it'd be better to have the argument always passed and match the accumulateCost API?

[Prazek]

lib/Analysis/InlineCost.cpp

493

range based for loop? There should be something like .operands()

[chandlerc]

lib/Analysis/InlineCost.cpp

493

I looked and there isn't really. I can add one though.

[Prazek]

lib/Analysis/InlineCost.cpp

493

That would be great, thanks

[chandlerc]

lib/Analysis/InlineCost.cpp

493

Huh, I must have missed it. Danny added an 'indices' method back in 2015. =D

[eraman]

lib/Analysis/InlineCost.cpp

80

I've tried to expand this a bit. PTAL.

Regarding the threshold being low: When I tuned it originally, it was before r286814 which added -30 to the cost for every inlining. At least to account that this needs to be revised up. In any case, I'll collect more numbers on the size/performance tradeoff and follow up.

90–91

It is relative. I've updated the variable name, flag name and the description to make this clear.

493

I see indices() in some other classes but not in GetElementPtrInst

test/Transforms/Inline/speedup-analysis.ll

4

Yes, the savings come from eliminating the call.

[eraman]

Address review comments.

[eraman]

Sorry for the delay in collecting performance numbers. I now have some data to share. First, some details on the methodology. I used ~400 microbenchmarks used internally at Google. I built them with the following percentage values of min-speedup-for-bonus: 0%, 5%, 10%, and 15%. I ran each benchmark 10 times in each configuration. Speedup/slowdown for a benchmark is calculated only when the p-value <=0.05 (and thus the results might include different subset of benchmarks for different configs). The numbers presented below are the geomean across all benchmarks.

Config | #Benchmarks | Geomean | #Slowdowns | #Speedups | Size increase percentage
0% | 134 | 2.92% | 51 | 83 | 2.45%
5% | 121 | 1.05% | 41 | 80 | 1.58%
10% | 115 | 0.8% | 51 | 64 | 1.32%
15% | 160 | 1.03% | 44 | 116| 1.02%

Some observations:

• The best geomean performance comes when the min-speedup-for-bonus is set to 0%. I interpret this to mean that it is generally a performance win to increase the threshold for hot callsites, and the speedup estimation is a way to control the size growth.
• The performance when the min-speedup-for-bonus is set to 10% sits in-between that of 5% and 15%. As I mentioned above, these are not apples-to-apples comparisons beacause we compute geomean on a different set of benchmarks. Even for the same benchmark, it is possible (and it does happen) that the performance numbers are not monotonically decreasing as the min-speedup-for-bonus is increased.
• For comparison, I calculated the size growth if we simply apply a 3X multiplier to the threshold irrespective of the callsite frequency. The size increase is 9.7%.

I'm collecting SPEC numbers now. I've also fixed a bug in the code and will update the patch shortly.

[eraman]

Fix a bug and rebase.

[davidxl]

Given the performance data, I suggest drop the min speedup requirement to 0 at O3.

[chandlerc]

In D30062#728588, @eraman wrote:

Sorry for the delay in collecting performance numbers. I now have some data to share. First, some details on the methodology. I used ~400 microbenchmarks used internally at Google. I built them with the following percentage values of min-speedup-for-bonus: 0%, 5%, 10%, and 15%. I ran each benchmark 10 times in each configuration. Speedup/slowdown for a benchmark is calculated only when the p-value <=0.05 (and thus the results might include different subset of benchmarks for different configs). The numbers presented below are the geomean across all benchmarks.

Config | #Benchmarks | Geomean | #Slowdowns | #Speedups | Size increase percentage
0% | 134 | 2.92% | 51 | 83 | 2.45%
5% | 121 | 1.05% | 41 | 80 | 1.58%
10% | 115 | 0.8% | 51 | 64 | 1.32%
15% | 160 | 1.03% | 44 | 116| 1.02%

Some observations:

• The best geomean performance comes when the min-speedup-for-bonus is set to 0%. I interpret this to mean that it is generally a performance win to increase the threshold for hot callsites, and the speedup estimation is a way to control the size growth.
• The performance when the min-speedup-for-bonus is set to 10% sits in-between that of 5% and 15%. As I mentioned above, these are not apples-to-apples comparisons beacause we compute geomean on a different set of benchmarks. Even for the same benchmark, it is possible (and it does happen) that the performance numbers are not monotonically decreasing as the min-speedup-for-bonus is increased.
• For comparison, I calculated the size growth if we simply apply a 3X multiplier to the threshold irrespective of the callsite frequency. The size increase is 9.7%.

The data here is really interesting, but I'm not sure about using the 0% threshold...

What I mean by that, is that if we use a 0% min-speedup-for-bonus, then we essentially aren't using the speedup computation at all are we? It seems like this would be roughly the same as just applying a similar multiplier to the threshold based on call site hotness. Maybe I just don't understand what the result of this is (sorry if I'm just failing to page back in all of the details)? If my understanding is correct though, then I would focus on that first and get it in, and then return to the speedup heuristic to see if there are wins to be found by doing a speedup analysis to bonus less hot call sites, or doing it to give an *even higher* threshold when a call site is both hot *and* gives a speedup on inlining.

I'm collecting SPEC numbers now. I've also fixed a bug in the code and will update the patch shortly.

Please also collect LLVM test suite numbers with the SPEC numbers.

One thing that would be particularly important though is to collect larger application *size* numbers. I don't think the size growth numbers from microbenchmarks are really going to tell us what we need to know to make good threshold decisions where size is a factor (especially O2 vs. O3).

lib/Analysis/InlineCost.cpp

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 "));
 
+// The following options control the heuristic that estimates speedup due to
+// inlining and adds a threshold bonus when the speedup is above a certain
+// limit.
+//
+/// Threshold bonus to apply when inlining is expected to result in a speedup.
+/// The bonus is expressed as a percent value. The unbonused threshold is
+/// multiplied by this threshold to arrive at the threshold increase.
+static cl::opt<int>
+    SpeedupBonusPercent("speedup-bonus-percent", cl::Hidden, cl::init(200),
+                        cl::ZeroOrMore,
+                        cl::desc("Bonus for callees showing speedup"));
+/// Minimum estimated speedup required to apply a threshold bonus.
+static cl::opt<int>
+    MinSpeedupForBonus("min-speedup-for-bonus", cl::Hidden, cl::init(10),
+                       cl::ZeroOrMore,
+                       cl::desc("Speedup percentage to apply bonus"));
+
+/// Minimum block frequency of callsite to apply speedup-based bonus.
+/// This limits size increase due to speedup bonus by applying the heuristic
+/// only when the callsite is relatively hot compared to caller's entry.
+static cl::opt<unsigned> MinBFForSpeedupBonus(
+    "min-freq-for-speedup-bonus", cl::Hidden, cl::init(8), cl::ZeroOrMore,
+    cl::desc("Min relative callsite freq to apply speedup bonus"));
+
 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;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// 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;
 
+  BlockFrequencyInfo *CallerBFI, *CalleeBFI;
   int Threshold;
   int Cost;
 
   bool IsCallerRecursive;
   bool IsRecursiveCall;
   bool ExposesReturnsTwice;
   bool HasDynamicAlloca;
   bool ContainsNoDuplicateCall;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   /// is CFG altering simplifications -- when we prove a basic block dead, that
   /// can cause dramatic shifts in the cost of inlining a function.
   DenseMap<Value *, Constant *> SimplifiedValues;
 
   /// Keep track of the values which map back (through function arguments) to
   /// allocas on the caller stack which could be simplified through SROA.
   DenseMap<Value *, Value *> SROAArgValues;
 
+  // We track unweighted and weighted(by block frequency) SROA cost savings.
+  using SROACostTy = std::pair<int, uint64_t>;
+
   /// The mapping of caller Alloca values to their accumulated cost savings. If
   /// we have to disable SROA for one of the allocas, this tells us how much
   /// cost must be added.
-  DenseMap<Value *, int> SROAArgCosts;
+  DenseMap<Value *, SROACostTy> SROAArgCosts;
 
   /// Keep track of values which map to a pointer base and constant offset.
   DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs;
 
   // Custom simplification helper routines.
   bool isAllocaDerivedArg(Value *V);
   bool lookupSROAArgAndCost(Value *V, Value *&Arg,
-                            DenseMap<Value *, int>::iterator &CostIt);
-  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
+                            DenseMap<Value *, SROACostTy>::iterator &CostIt);
+  void disableSROA(DenseMap<Value *, SROACostTy>::iterator CostIt);
   void disableSROA(Value *V);
-  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
+  void accumulateSROACost(DenseMap<Value *, SROACostTy>::iterator CostIt,
                           int InstructionCost);
   void accumulateCost(int InstructionCost);
+  void accumulateSavings(int Savings = InlineConstants::InstrCost);
   bool isGEPFree(GetElementPtrInst &GEP);
   bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
   bool simplifyCallSite(Function *F, CallSite CS);
   ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
 
   /// Return true if the given argument to the function being considered for
   /// inlining has the given attribute set either at the call site or the
   /// function declaration.  Primarily used to inspect call site specific
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
   /// Simplify \p I if its operands are constants and update SimplifiedValues.
   /// Transfom is a lambda specific to instruction type that evaluates the
   /// instruction when all the operands are constants.
   bool
   simplifyInstruction(Instruction &I,
                       function_ref<Constant *(ArrayRef<Constant *>)> Evaluate);
+  int getSpeedupBonus(CallSite &CS, int Threshold);
+  bool hasEstimatedSpeedup();
 
 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), 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) {}
+        NumInstructionsSimplified(0), SROACostSavings(0), WeightedSavings(0),
+        WeightedCost(0), SROACostSavingsLost(0), CurrBBFreq(1) {}
 
   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.
   unsigned NumConstantArgs;
   unsigned NumConstantOffsetPtrArgs;
   unsigned NumAllocaArgs;
   unsigned NumConstantPtrCmps;
   unsigned NumConstantPtrDiffs;
   unsigned NumInstructionsSimplified;
   unsigned SROACostSavings;
+  int WeightedSavings, WeightedCost;
   unsigned SROACostSavingsLost;
+  /// The block frequency of the current block being analyzed.
+  uint64_t CurrBBFreq;
 
   void dump();
 };
 
 } // namespace
 
 /// \brief Test whether the given value is an Alloca-derived function argument.
 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
   return SROAArgValues.count(V);
 }
 
 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
 /// Returns false if V does not map to a SROA-candidate.
 bool CallAnalyzer::lookupSROAArgAndCost(
-    Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
+    Value *V, Value *&Arg, DenseMap<Value *, SROACostTy>::iterator &CostIt) {
   if (SROAArgValues.empty() || SROAArgCosts.empty())
     return false;
 
   DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
   if (ArgIt == SROAArgValues.end())
     return false;
 
   Arg = ArgIt->second;
   CostIt = SROAArgCosts.find(Arg);
   return CostIt != SROAArgCosts.end();
 }
 
 /// \brief Disable SROA for the candidate marked by this cost iterator.
 ///
 /// This marks the candidate as no longer viable for SROA, and adds the cost
 /// savings associated with it back into the inline cost measurement.
-void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
+void CallAnalyzer::disableSROA(DenseMap<Value *, SROACostTy>::iterator CostIt) {
   // If we're no longer able to perform SROA we need to undo its cost savings
   // and prevent subsequent analysis.
-  Cost += CostIt->second;
-  SROACostSavings -= CostIt->second;
-  SROACostSavingsLost += CostIt->second;
+  Cost += CostIt->second.first;
+  WeightedCost += CostIt->second.second;
+  SROACostSavings -= CostIt->second.first;
+  WeightedSavings -= CostIt->second.second;
+  SROACostSavingsLost += CostIt->second.first;
   SROAArgCosts.erase(CostIt);
 }
 
 /// \brief If 'V' maps to a SROA candidate, disable SROA for it.
 void CallAnalyzer::disableSROA(Value *V) {
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(V, SROAArg, CostIt))
     disableSROA(CostIt);
 }
 
 /// \brief Accumulate the given cost for a particular SROA candidate.
-void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
-                                      int InstructionCost) {
-  CostIt->second += InstructionCost;
+void CallAnalyzer::accumulateSROACost(
+    DenseMap<Value *, SROACostTy>::iterator CostIt, int InstructionCost) {
+  CostIt->second.first += InstructionCost;
   SROACostSavings += InstructionCost;
+  // FIXME: We use saturating multiply on uint64_t here and below where we
+  // compute weighted cost/savings. If this proves to be less precise, consider
+  // using 128 bit APInt and also use relative block frequency (scale block
+  // frequencies relative to entry block).
+  auto WeightedCost = SaturatingMultiply(CurrBBFreq, (uint64_t)InstructionCost);
+  CostIt->second.second += WeightedCost;
+  WeightedSavings += WeightedCost;
 }
 
 /// \brief Accumulate a constant GEP offset into an APInt if possible.
 ///
 /// Returns false if unable to compute the offset for any reason. Respects any
 /// simplified values known during the analysis of this callsite.
 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
   const DataLayout &DL = F.getParent()->getDataLayout();
bool CallAnalyzer::visitPHI(PHINode &I) {
   // SROA if it *might* be used in an inappropriate manner.
 
   // Phi nodes are always zero-cost.
   return true;
 }
 
 void CallAnalyzer::accumulateCost(int InstructionCost) {
   Cost += InstructionCost;
+  WeightedCost += SaturatingMultiply(CurrBBFreq, (uint64_t)InstructionCost);
 }
 
 bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   bool SROACandidate =
       lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt);
 
   // Try to fold GEPs of constant-offset call site argument pointers. This
   // requires target data and inbounds GEPs.
   if (I.isInBounds()) {
     // Check if we have a base + offset for the pointer.
     Value *Ptr = I.getPointerOperand();
     std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
     if (BaseAndOffset.first) {
       // Check if the offset of this GEP is constant, and if so accumulate it
       // into Offset.
       if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
         // Non-constant GEPs aren't folded, and disable SROA.
         if (SROACandidate)
           disableSROA(CostIt);
+        // isGEPFree looks up SimplifiedValues and so we should ideally be
+        // tracking savings here, but that would require calling the TTI hook
+        // with and without simplified values. So we take the conservative route
+        // and assume no savings due to the lookup.
         return isGEPFree(I);
       }
 
       // Add the result as a new mapping to Base + Offset.
       ConstantOffsetPtrs[&I] = BaseAndOffset;
 
       // Also handle SROA candidates here, we already know that the GEP is
       // all-constant indexed.
       if (SROACandidate)
         SROAArgValues[&I] = SROAArg;
 
       return true;
     }
   }
 
+  bool SVLookup = false;
+
   // Lambda to check whether a GEP's indices are all constant.
   auto isGEPOffsetConstant = [&](GetElementPtrInst &GEP) {
-    for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
-      if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
+    for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E;
+         ++I) {
+      if (!isa<Constant>(*I)) {
+        if (SimplifiedValues.lookup(*I))
+          SVLookup = true;
+        else
           return false;
+      }
+    }
     return true;
   };
 
   if (isGEPOffsetConstant(I)) {
     if (SROACandidate)
       SROAArgValues[&I] = SROAArg;
+    if (SVLookup)
+      accumulateSavings();
 
     // Constant GEPs are modeled as free.
     return true;
   }
 
   // Variable GEPs will require math and will disable SROA.
   if (SROACandidate)
     disableSROA(CostIt);
   return isGEPFree(I);
 }
 
+void CallAnalyzer::accumulateSavings(int Savings) {
+  WeightedSavings += SaturatingMultiply(CurrBBFreq, (uint64_t)Savings);
+}
+
 bool CallAnalyzer::simplifyInstruction(
     Instruction &I, function_ref<Constant *(ArrayRef<Constant *>)> Evaluate) {
   Constant *COps[2];
   int N = 0;
+  bool Lookup = false;
   for (Value *Op : I.operands()) {
     Constant *COp = dyn_cast<Constant>(Op);
-    if (!COp)
+    if (!COp) {
       COp = SimplifiedValues.lookup(Op);
+      Lookup = true;
+    }
     if (!COp)
       return false;
     COps[N++] = COp;
   }
   if (auto *C = Evaluate(COps)) {
     SimplifiedValues[&I] = C;
+    if (Lookup)
+      accumulateSavings();
     return true;
   }
   return false;
 }
 
+int CallAnalyzer::getSpeedupBonus(CallSite &CS, int Threshold) {
+  if (!CallerBFI)
+    return 0;
+  auto EntryFreq = CallerBFI->getEntryFreq();
+  auto *BB = CS.getInstruction()->getParent();
+  auto CallSiteFreq = CallerBFI->getBlockFreq(BB).getFrequency();
+  if (CallSiteFreq / EntryFreq < MinBFForSpeedupBonus)
+    return 0;
+  return SpeedupBonusPercent * Threshold / 100;
+}
+
+bool CallAnalyzer::hasEstimatedSpeedup() {
+  int D = std::max(1, WeightedCost + WeightedSavings);
+  int Speedup = WeightedSavings * 100 / D;
+  return Speedup > MinSpeedupForBonus;
+}
+
 bool CallAnalyzer::visitBitCast(BitCastInst &I) {
   // Propagate constants through bitcasts.
   auto Evaluate = [&](ArrayRef<Constant *> COps) -> Constant * {
     return ConstantExpr::getBitCast(COps[0], I.getType());
   };
   if (simplifyInstruction(I, Evaluate))
     return true;
 
   // Track base/offsets through casts
   std::pair<Value *, APInt> BaseAndOffset =
       ConstantOffsetPtrs.lookup(I.getOperand(0));
   // Casts don't change the offset, just wrap it up.
   if (BaseAndOffset.first)
     ConstantOffsetPtrs[&I] = BaseAndOffset;
 
   // Also look for SROA candidates here.
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
     SROAArgValues[&I] = SROAArg;
 
   // Bitcasts are always zero cost.
   return true;
 }
 
 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
   // This is really weird. Technically, ptrtoint will disable SROA. However,
   // unless that ptrtoint is *used* somewhere in the live basic blocks after
   // inlining, it will be nuked, and SROA should proceed. All of the uses which
   // would block SROA would also block SROA if applied directly to a pointer,
   // and so we can just add the integer in here. The only places where SROA is
   // preserved either cannot fire on an integer, or won't in-and-of themselves
   // disable SROA (ext) w/o some later use that we would see and disable.
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
     SROAArgValues[&I] = SROAArg;
 
   return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
 }
 
 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
   // Propagate constants through ptrtoint.
bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
   if (IntegerSize <= DL.getPointerSizeInBits()) {
     std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
     if (BaseAndOffset.first)
       ConstantOffsetPtrs[&I] = BaseAndOffset;
   }
 
   // "Propagate" SROA here in the same manner as we do for ptrtoint above.
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
     SROAArgValues[&I] = SROAArg;
 
   return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
 }
 
 bool CallAnalyzer::visitCastInst(CastInst &I) {
   // Propagate constants through ptrtoint.
void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) {
   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);
-    BlockFrequencyInfo *CallerBFI = GetBFI ? &((*GetBFI)(*Caller)) : nullptr;
     if (PSI) {
       if (PSI->isHotCallSite(CS, CallerBFI)) {
         DEBUG(dbgs() << "Hot callsite.\n");
         Threshold = MaxIfValid(Threshold, Params.HotCallSiteThreshold);
       } else if (PSI->isFunctionEntryHot(&Callee)) {
         DEBUG(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
bool CallAnalyzer::visitCmpInst(CmpInst &I) {
   if (LHSBase) {
     std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
     if (RHSBase && LHSBase == RHSBase) {
       // We have common bases, fold the icmp to a constant based on the
       // offsets.
       Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
       Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
       if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
+        accumulateSavings();
         SimplifiedValues[&I] = C;
         ++NumConstantPtrCmps;
         return true;
       }
     }
   }
 
   // If the comparison is an equality comparison with null, we can simplify it
   // if we know the value (argument) can't be null
   if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
       isKnownNonNullInCallee(I.getOperand(0))) {
+    if (isAllocaDerivedArg(I.getOperand(0)))
+      accumulateSavings();
     bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
     SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
                                       : ConstantInt::getFalse(I.getType());
     return true;
   }
   // Finally check for SROA candidates in comparisons.
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
     if (isa<ConstantPointerNull>(I.getOperand(1))) {
       accumulateSROACost(CostIt, InlineConstants::InstrCost);
       return true;
     }
 
     disableSROA(CostIt);
   }
bool CallAnalyzer::visitSub(BinaryOperator &I) {
   if (LHSBase) {
     std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
     if (RHSBase && LHSBase == RHSBase) {
       // We have common bases, fold the subtract to a constant based on the
       // offsets.
       Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
       Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
       if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
+        accumulateSavings();
         SimplifiedValues[&I] = C;
         ++NumConstantPtrDiffs;
         return true;
       }
     }
   }
 
   // Otherwise, fall back to the generic logic for simplifying and handling
bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
   disableSROA(LHS);
   disableSROA(RHS);
 
   return false;
 }
 
 bool CallAnalyzer::visitLoad(LoadInst &I) {
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
     if (I.isSimple()) {
       accumulateSROACost(CostIt, InlineConstants::InstrCost);
       return true;
     }
 
     disableSROA(CostIt);
   }
 
   return false;
 }
 
 bool CallAnalyzer::visitStore(StoreInst &I) {
   Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
+  DenseMap<Value *, SROACostTy>::iterator CostIt;
   if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
     if (I.isSimple()) {
       accumulateSROACost(CostIt, InlineConstants::InstrCost);
       return true;
     }
 
     disableSROA(CostIt);
   }

 /// free.
 bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
   // FIXME: Using the instsimplify logic directly for this is inefficient
   // because we have to continually rebuild the argument list even when no
   // simplifications can be performed. Until that is fixed with remapping
   // inside of instsimplify, directly constant fold calls here.
   if (!canConstantFoldCallTo(F))
     return false;
+  bool SVLookup = false;
   // Try to re-map the arguments to constants.
   SmallVector<Constant *, 4> ConstantArgs;
   ConstantArgs.reserve(CS.arg_size());
   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
        ++I) {
     Constant *C = dyn_cast<Constant>(*I);
-    if (!C)
+    if (!C) {
       C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
+      SVLookup = true;
+    }
     if (!C)
       return false; // This argument doesn't map to a constant.
 
     ConstantArgs.push_back(C);
   }
   if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
     SimplifiedValues[CS.getInstruction()] = C;
+
+    // FIXME: Increase the savings associated with simplifying a callsite.
+    if (SVLookup)
+      accumulateSavings(InlineConstants::InstrCost +
+                        InlineConstants::CallPenalty);
+
     return true;
   }
 
   return false;
 }
 
 bool CallAnalyzer::visitCallSite(CallSite CS) {
   if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
bool CallAnalyzer::visitCallSite(CallSite CS) {
   auto IndirectCallParams = Params;
   IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
   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());
+    // FIXME: This underestimates the savings due to removing a call. Perhaps we
+    // should get the weighted cost and savings of inlining the indirect call,
+    // scale it based on callsite and callee's enrtry frequencies and add them
+    // up to the current callee's weighted cost and savings.
+    accumulateSavings(InlineConstants::InstrCost +
+                      InlineConstants::CallPenalty);
   }
 
   return Base::visitCallSite(CS);
 }
 
 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
   // At least one return instruction will be free after inlining.
   bool Free = !HasReturn;
   HasReturn = true;
   return Free;
 }
 
 bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
   // We model unconditional branches as essentially free -- they really
   // shouldn't exist at all, but handling them makes the behavior of the
   // inliner more regular and predictable. Interestingly, conditional branches
   // which will fold away are also free.
-  return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
-         dyn_cast_or_null<ConstantInt>(
-             SimplifiedValues.lookup(BI.getCondition()));
+  if (BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()))
+    return true;
+  if (dyn_cast_or_null<ConstantInt>(
+          SimplifiedValues.lookup(BI.getCondition()))) {
+    accumulateSavings();
+    return true;
+  }
+  return false;
 }
 
 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   // We model unconditional switches as free, see the comments on handling
   // branches.
   if (isa<ConstantInt>(SI.getCondition()))
     return true;
 
for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
       SuccessorBlocks.insert(I.getCaseSuccessor());
 
     // Add cost corresponding to the number of distinct destinations. The first
     // we model as free because of fallthrough.
     return (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
   };
 
   if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
-    if (isa<ConstantInt>(V))
+    if (isa<ConstantInt>(V)) {
+      accumulateSavings(SwitchInstCost(SI));
       return true;
+    }
 
   accumulateCost(SwitchInstCost(SI));
   return false;
 }
 
 bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
   // We never want to inline functions that contain an indirectbr.  This is
   // incorrect because all the blockaddress's (in static global initializers

 ///
 /// This method walks the analyzer over every instruction in the given basic
 /// block and accounts for their cost during inlining at this callsite. It
 /// aborts early if the threshold has been exceeded or an impossible to inline
 /// construct has been detected. It returns false if inlining is no longer
 /// viable, and true if inlining remains viable.
 bool CallAnalyzer::analyzeBlock(BasicBlock *BB,
                                 SmallPtrSetImpl<const Value *> &EphValues) {
+  if (CallerBFI)
+    CurrBBFreq = CallerBFI->getBlockFreq(BB).getFrequency();
+
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     // FIXME: Currently, the number of instructions in a function regardless of
     // our ability to simplify them during inline to constants or dead code,
     // are actually used by the vector bonus heuristic. As long as that's true,
     // we have to special case debug intrinsics here to prevent differences in
     // inlining due to debug symbols. Eventually, the number of unsimplified
     // instructions shouldn't factor into the cost computation, but until then,
     // hack around it here.
bool CallAnalyzer::analyzeCall(CallSite CS) {
   // low. Note that these bonuses are some what arbitrary and evolved over time
   // by accident as much as because they are principled bonuses.
   //
   // FIXME: It would be nice to remove all such bonuses. At least it would be
   // nice to base the bonus values on something more scientific.
   assert(NumInstructions == 0);
   assert(NumVectorInstructions == 0);
 
+  Function *Caller = CS.getInstruction()->getParent()->getParent();
+  CallerBFI = nullptr;
+  CalleeBFI = nullptr;
+  if (GetBFI) {
+    CallerBFI = &((*GetBFI)(*Caller));
+    if (!F.isDeclaration())
+      CalleeBFI = &((*GetBFI)(F));
+    // While evaluating the weighted savings due to removal of argument setup
+    // and the call overhead, we want to use the entry block's frequency.
+    CurrBBFreq = CallerBFI->getEntryFreq();
+  }
   // Update the threshold based on callsite properties
   updateThreshold(CS, F);
 
   FiftyPercentVectorBonus = 3 * Threshold / 2;
   TenPercentVectorBonus = 3 * Threshold / 4;
   const DataLayout &DL = F.getParent()->getDataLayout();
 
   // Track whether the post-inlining function would have more than one basic
   // block. A single basic block is often intended for inlining. Balloon the
   // threshold by 50% until we pass the single-BB phase.
   bool SingleBB = true;
   int SingleBBBonus = Threshold / 2;
+  int SpeedupBonus = getSpeedupBonus(CS, Threshold);
 
   // Speculatively apply all possible bonuses to Threshold. If cost exceeds
   // this Threshold any time, and cost cannot decrease, we can stop processing
   // the rest of the function body.
-  Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
+  Threshold += (SingleBBBonus + FiftyPercentVectorBonus + SpeedupBonus);
 
   // Give out bonuses per argument, as the instructions setting them up will
   // be gone after inlining.
   for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
     if (CS.isByValArgument(I)) {
       // We approximate the number of loads and stores needed by dividing the
       // size of the byval type by the target's pointer size.
       PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
       unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
       unsigned PointerSize = DL.getPointerSizeInBits();
       // Ceiling division.
       unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
 
       // If it generates more than 8 stores it is likely to be expanded as an
       // inline memcpy so we take that as an upper bound. Otherwise we assume
       // one load and one store per word copied.
       // FIXME: The maxStoresPerMemcpy setting from the target should be used
       // here instead of a magic number of 8, but it's not available via
       // DataLayout.
       NumStores = std::min(NumStores, 8U);
 
       accumulateCost(-2 * NumStores * InlineConstants::InstrCost);
+      accumulateSavings(2 * NumStores * InlineConstants::InstrCost);
     } else {
       // For non-byval arguments subtract off one instruction per call
       // argument.
       accumulateCost(-InlineConstants::InstrCost);
+      accumulateSavings(InlineConstants::InstrCost);
     }
   }
   // The call instruction also disappears after inlining.
   accumulateCost(-InlineConstants::InstrCost - InlineConstants::CallPenalty);
+  accumulateSavings(InlineConstants::InstrCost + InlineConstants::CallPenalty);
 
   // If there is only one call of the function, and it has internal linkage,
   // the cost of inlining it drops dramatically.
   bool OnlyOneCallAndLocalLinkage =
       F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction();
   if (OnlyOneCallAndLocalLinkage)
     Cost -= InlineConstants::LastCallToStaticBonus;
 
   // If this function uses the coldcc calling convention, prefer not to inline
   // it.
   if (F.getCallingConv() == CallingConv::Cold)
     accumulateCost(InlineConstants::ColdccPenalty);
 
   // Check if we're done. This can happen due to bonuses and penalties.
   if (Cost > Threshold)
     return false;
 
   if (F.empty())
     return true;
 
-  Function *Caller = CS.getInstruction()->getParent()->getParent();
   // Check if the caller function is recursive itself.
   for (User *U : Caller->users()) {
     CallSite Site(U);
     if (!Site)
       continue;
     Instruction *I = Site.getInstruction();
     if (I->getParent()->getParent() == Caller) {
       IsCallerRecursive = true;
for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
 
     Value *PtrArg = *CAI;
     if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
       ConstantOffsetPtrs[&*FAI] = std::make_pair(PtrArg, C->getValue());
 
       // We can SROA any pointer arguments derived from alloca instructions.
       if (isa<AllocaInst>(PtrArg)) {
         SROAArgValues[&*FAI] = PtrArg;
-        SROAArgCosts[PtrArg] = 0;
+        SROAArgCosts[PtrArg] = {0, 0};
       }
     }
   }
   NumConstantArgs = SimplifiedValues.size();
   NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
   NumAllocaArgs = SROAArgValues.size();
 
   // FIXME: If a caller has multiple calls to a callee, we end up recomputing
bool CallAnalyzer::analyzeCall(CallSite CS) {
   // We applied the maximum possible vector bonus at the beginning. Now,
   // subtract the excess bonus, if any, from the Threshold before
   // comparing against Cost.
   if (NumVectorInstructions <= NumInstructions / 10)
     Threshold -= FiftyPercentVectorBonus;
   else if (NumVectorInstructions <= NumInstructions / 2)
     Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
 
+  if (!hasEstimatedSpeedup())
+    Threshold -= SpeedupBonus;
+
   return Cost < std::max(1, Threshold);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 /// \brief Dump stats about this call's analysis.
 LLVM_DUMP_METHOD void CallAnalyzer::dump() {
 #define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
   DEBUG_PRINT_STAT(NumConstantArgs);
   DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
   DEBUG_PRINT_STAT(NumAllocaArgs);
   DEBUG_PRINT_STAT(NumConstantPtrCmps);
   DEBUG_PRINT_STAT(NumConstantPtrDiffs);
   DEBUG_PRINT_STAT(NumInstructionsSimplified);
   DEBUG_PRINT_STAT(NumInstructions);
   DEBUG_PRINT_STAT(SROACostSavings);
   DEBUG_PRINT_STAT(SROACostSavingsLost);
   DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
   DEBUG_PRINT_STAT(Cost);
+  DEBUG_PRINT_STAT(WeightedCost);
+  DEBUG_PRINT_STAT(WeightedSavings);
   DEBUG_PRINT_STAT(Threshold);
 #undef DEBUG_PRINT_STAT
 }
 #endif
 
 /// \brief Test that two functions either have or have not the given attribute
 ///        at the same time.
 template <typename AttrKind>

test/Transforms/Inline/speedup-analysis.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-threshold=10 -speedup-bonus-percent=1000
+; Test that a callee that does not fit within the threshold gets inlined
+; because of the estimated speedup heuristic.
+define i32 @caller(i32 %n) {
+; CHECK-LABEL: define i32 @caller
+entry:
+  br label %loop
+loop:
+  %r = phi i32 [%n, %entry], [%result, %loop]
+; CHECK-NOT: call i32 @callee
+  %result = call i32 @callee(i32 %r)
+  %cond = icmp sle i32 %result, 100
+  br i1 %cond, label %loop, label %exit
+exit:
+; CHECK: ret
+  ret i32 %result
+}
+
+define i32 @callee(i32 %n) {
+  %cond = icmp sle i32 %n, 100
+  br i1 %cond, label %cond_true, label %cond_false, !prof !0
+
+cond_true:
+  %n1 = add i32 %n, 1
+  %n2 = add i32 %n1, 1
+  ret i32 %n2
+cond_false:
+  call void @extern()
+  call void @extern()
+  call void @extern()
+  ret i32 0
+}
+declare void @extern()
+
+!0 = !{!"branch_weights", i32 1, i32 0}

test/Transforms/Inline/speedup-analysis2.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -inline-threshold=10 -speedup-bonus-percent=1000
+; Test that a callee that does not fit within the threshold gets inlined
+; because of the estimated speedup heuristic. The callee has a switch statement.
+; Since only one of the cases is executed per invocation of the callee, the
+; weighted cost of the callee is low and results in a big relative speedup as the
+; benefits of removing the function call is accounted for.
+
+define i32 @caller(i32 %n) {
+; CHECK-LABEL: define i32 @caller
+entry:
+  br label %loop
+loop:
+  %r = phi i32 [%n, %entry], [%result, %loop]
+; CHECK-NOT: call i32 @callee
+  %result = call i32 @callee(i32 %r)
+  %cond = icmp sle i32 %result, 100
+  br i1 %cond, label %loop, label %exit
+exit:
+; CHECK: ret
+  ret i32 %result
+}
+
+define i32 @callee(i32 %n) {
+entry:
+  switch i32 %n, label %return [
+    i32 1, label %sw.bb1
+    i32 2, label %sw.bb2
+    i32 3, label %sw.bb3
+    i32 4, label %sw.bb4
+    i32 5, label %sw.bb5
+    i32 6, label %sw.bb6
+    i32 7, label %sw.bb7
+  ]
+
+sw.bb1:
+  %r1 = add i32 %n, 1
+  br label %return
+
+sw.bb2:
+  %r2 = add i32 %n, 2
+  br label %return
+
+sw.bb3:
+  %r3 = add i32 %n, 3
+  br label %return
+
+sw.bb4:
+  %r4 = add i32 %n, 4
+  br label %return
+
+sw.bb5:
+  %r5 = add i32 %n, 5
+  br label %return
+
+sw.bb6:
+  %r6 = add i32 %n, 6
+  br label %return
+
+sw.bb7:
+  %r7 = add i32 %n, 7
+  br label %return
+
+return:
+  %res = phi i32 [%n, %entry], [%r1, %sw.bb1], [%r2, %sw.bb2], [%r3, %sw.bb3], [%r4, %sw.bb4], [%r5, %sw.bb5], [%r6, %sw.bb6], [%r7, %sw.bb7]
+  ret i32 %res
+
+}
+declare void @extern()
+