[PGO] Use sum of count values to fix func entry count and add a check to verify BFI counts

[xur]

Summary

Raw profile count values for each BB are not kept after profile annotation.
We record function entry count and branch weights and use them to compute the count when needed.
This mechanism works well in a perfect world, but often breaks in real programs,
because of number prevision, inconsistent profile, or bugs in BFI) .
This patch add functionality to compare BFI counts with real profile counts right after reading the profile.
It also fixes function entry count to make the BFI count close to real profile counts.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

257

It is probably more useful to have an option controlling checking hot BB's only -- check with either RawCount or BFI count is hot (can catch the case when a cold block becomes 'hot' with BFI info).

1559

what is the rationale and use of this fixup?

1612

Add comment of make variable name NonC0BBNum more obvious for its meaning.

1636

Variable not used.

llvm/test/Transforms/PGOProfile/fix_bfi.ll

1

Add an comment on the what the test case is testing (especially the fix check part).

[xur]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

257

Yes. Checking hot BFI counts will catch some abnormal cases.
The reason I used a cutoff instead of default hot threshold is that there could be too many hot BB to check for some programs.
Using a high cutoff could make the output much cleaner. And the user can specify the hot threshold from detailed summary.

I will probably keep this option and add another option that checking hot BB as you suggested.

1559

There is no perfect way to fix this: when the information is lost, we could not recover. This is just one way to fix it so that the total count close.

1612

will do.

1636

will put this variable under Debug macro.

llvm/test/Transforms/PGOProfile/fix_bfi.ll

1

will do.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1564

assert here that function entry count is already set.

1568

In what situation can this happen?

1571

how can this be possible?

1579

maybe early return?

1582

negate the logic and early return?

1583

assert SumBFCount is not zero

1585

early return?

1588

Is this handled by the next statements?

1602

Is this needed?

[xur]

I'm reviving this patch because this fixes one of our internal bugs.

Before the fix, The BFI counters are way off the raw profile counter:

` BB : Count=96615607 BFI Count=16

BB : Count=96615607  BFI Count=16
BB : Count=9874441  BFI Count=2
BB : Count=9849389  BFI Count=2
BB : Count=9928400  BFI Count=2
BB : Count=96694618  BFI Count=16
BB : Count=30  BFI Count=0
BB : Count=96694588  BFI Count=16
BB : Count=93506121  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=6933665  BFI Count=1
BB : Count=6933665  BFI Count=1
BB : Count=4641130  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=3439260  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=4624009  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=2299158  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2234047  BFI Count=0
BB : Count=3500  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2225955  BFI Count=0
BB : Count=18824  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230585  BFI Count=0
BB : Count=2229242  BFI Count=0
BB : Count=38  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=68611  BFI Count=0
BB : Count=103021581  BFI Count=16
BB : Count=103021611  BFI Count=16
BB : Count=6406005  BFI Count=1

`

With this patch, we can get:

`BB : Count=1  BFI Count=6145756
BB : Count=96615607  BFI Count=98836277
BB : Count=96615607  BFI Count=98836277
BB : Count=9874441  BFI Count=10101401
BB : Count=9849389  BFI Count=10075773
BB : Count=9928400  BFI Count=10075773
BB : Count=96694618  BFI Count=98836277
BB : Count=30  BFI Count=31
BB : Count=96694588  BFI Count=98836246
BB : Count=93506121  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=6933665  BFI Count=6844610
BB : Count=6933665  BFI Count=6844610
BB : Count=4641130  BFI Count=4581520
BB : Count=4634507  BFI Count=4574982
BB : Count=4634507  BFI Count=4574982
BB : Count=3439260  BFI Count=3395087
BB : Count=4634090  BFI Count=4574982
BB : Count=4624009  BFI Count=4565030
BB : Count=4634090  BFI Count=4574982
BB : Count=2299158  BFI Count=2269628
BB : Count=2230547  BFI Count=2201898
BB : Count=2234047  BFI Count=2205353
BB : Count=3500  BFI Count=3455
BB : Count=2230547  BFI Count=2201898
BB : Count=2225955  BFI Count=2197365
BB : Count=18824  BFI Count=18582
BB : Count=2230547  BFI Count=2201898
BB : Count=2230547  BFI Count=2201898
BB : Count=2230585  BFI Count=2201936
BB : Count=2229242  BFI Count=2200610
BB : Count=2230547  BFI Count=2201898
BB : Count=68611  BFI Count=67730
BB : Count=103021581  BFI Count=98836246
BB : Count=103021611  BFI Count=98836277
BB : Count=6406005  BFI Count=6145756

`

I will post the updated patch shortly.

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1568

I changed to findBBInfo.
Usually this won't happen. But this can happen if there is unreachable BB (like when build at -O0).

1571

If the entryCount is 0, we don't have Profile Count for BB.
This could happen if we did not fix the entryCount.

But now, 0 entryCount is not possible after we populatedCounters (if the maxcount is nonzero). This is not needed. I will remove.

1585

Done

1588

Changed the code.

1602

Probably not. I removed it.

[xur]

Updated the patch that addressed David's review comments.
One noticeable change was to .add a new option "pgo-vefify-hot-bfi" which will
output a message when one of the following happens:
(1) a hot rawCount becomes non-hot in BFI
(2) a cold rawCount becomes hot in BFI

-Rong

[davidxl]

Can you split this patch into two? one for verification, the other for fixing?

[wenlei]

We record function entry count and branch weights and use them to compute the count when needed. This mechanism works well in a perfect world, but often breaks in real programs

We're battling this exact problem from sample PGO side. And we have internal patches for comparing block counts from BFI with ground truth. Perhaps these all can be refactored to be shared between Instr PGO and sample PGO. +@hoy

How does fixing up entry count alone help mitigate this problem?

[hoy]

In D61540#2404348, @xur wrote:

I'm reviving this patch because this fixes one of our internal bugs.

Before the fix, The BFI counters are way off the raw profile counter:

` BB : Count=96615607 BFI Count=16

BB : Count=96615607  BFI Count=16
BB : Count=9874441  BFI Count=2
BB : Count=9849389  BFI Count=2
BB : Count=9928400  BFI Count=2
BB : Count=96694618  BFI Count=16
BB : Count=30  BFI Count=0
BB : Count=96694588  BFI Count=16
BB : Count=93506121  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=99833531  BFI Count=16
BB : Count=6933665  BFI Count=1
BB : Count=6933665  BFI Count=1
BB : Count=4641130  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=4634507  BFI Count=1
BB : Count=3439260  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=4624009  BFI Count=1
BB : Count=4634090  BFI Count=1
BB : Count=2299158  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2234047  BFI Count=0
BB : Count=3500  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2225955  BFI Count=0
BB : Count=18824  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=2230585  BFI Count=0
BB : Count=2229242  BFI Count=0
BB : Count=38  BFI Count=0
BB : Count=2230547  BFI Count=0
BB : Count=68611  BFI Count=0
BB : Count=103021581  BFI Count=16
BB : Count=103021611  BFI Count=16
BB : Count=6406005  BFI Count=1

`

With this patch, we can get:

`BB : Count=1  BFI Count=6145756
BB : Count=96615607  BFI Count=98836277
BB : Count=96615607  BFI Count=98836277
BB : Count=9874441  BFI Count=10101401
BB : Count=9849389  BFI Count=10075773
BB : Count=9928400  BFI Count=10075773
BB : Count=96694618  BFI Count=98836277
BB : Count=30  BFI Count=31
BB : Count=96694588  BFI Count=98836246
BB : Count=93506121  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=99833531  BFI Count=95577159
BB : Count=6933665  BFI Count=6844610
BB : Count=6933665  BFI Count=6844610
BB : Count=4641130  BFI Count=4581520
BB : Count=4634507  BFI Count=4574982
BB : Count=4634507  BFI Count=4574982
BB : Count=3439260  BFI Count=3395087
BB : Count=4634090  BFI Count=4574982
BB : Count=4624009  BFI Count=4565030
BB : Count=4634090  BFI Count=4574982
BB : Count=2299158  BFI Count=2269628
BB : Count=2230547  BFI Count=2201898
BB : Count=2234047  BFI Count=2205353
BB : Count=3500  BFI Count=3455
BB : Count=2230547  BFI Count=2201898
BB : Count=2225955  BFI Count=2197365
BB : Count=18824  BFI Count=18582
BB : Count=2230547  BFI Count=2201898
BB : Count=2230547  BFI Count=2201898
BB : Count=2230585  BFI Count=2201936
BB : Count=2229242  BFI Count=2200610
BB : Count=2230547  BFI Count=2201898
BB : Count=68611  BFI Count=67730
BB : Count=103021581  BFI Count=98836246
BB : Count=103021611  BFI Count=98836277
BB : Count=6406005  BFI Count=6145756

`

I will post the updated patch shortly.

Interesting to see the BFI-computed execution count diverse so much from real counts, even for PGO. I'm wondering if this is due to optimizations in the training build. For the example above, the BFI-computed block frequencies (ratio, not execution count) seem not diverging too much for each block, compared to the real profile counts.

[xur]

Split the verification to another patch.

verification patch:
https://reviews.llvm.org/D91813

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1591

Perhaps take the max of the original func entry count and the new entry count?

[xur]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1591

Not sure if want a max here. Here a value of 1 makes the sum of raw counters and sum of BFI counters close to each other, better than original func entry count.

Using max will never reduce the entry count -- I don't think that is what we want.

[davidxl]

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1591

I thought the intention of the patch is to correct the 'guessed' entry count which is usually '1'. If the original entry count is not 1, it is usually a value we can trust. Sometimes BFI can create insanely large counts which makes the scale really small. It ends up leading to new entry entry count to become 1 (from non-1 value). Is that the intended behavior?

[davidxl]

lgtm

llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 // Emit branch probability as optimization remarks.
 static cl::opt<bool>
     EmitBranchProbability("pgo-emit-branch-prob", cl::init(false), cl::Hidden,
                           cl::desc("When this option is on, the annotated "
                                    "branch probability will be emitted as "
                                    "optimization remarks: -{Rpass|"
                                    "pass-remarks}=pgo-instrumentation"));
 
+static cl::opt<bool> PGOVerifyBFI(
+    "pgo-verify-bfi", cl::init(false), cl::Hidden,
+    cl::desc("Print out non-match BFI counts after setting profile metadata."));
+
+static cl::opt<unsigned> PGOVerifyBFIRatio(
+    "pgo-verify-bfi-ratio", cl::init(5), cl::Hidden,
+    cl::desc("Print out non-match BFI if the difference percentage is greater "
+             "than this value (in percentage)."));
+
+static cl::opt<unsigned> PGOVerifyBFICutoff(
+    "pgo-verify-bfi-cutoff", cl::init(1), cl::Hidden,
+    cl::desc("Skip the counts whose profile count value is below."));
+
+static cl::opt<bool>
+    PGOFixEntryCount("pgo-fix-entry-count", cl::init(true), cl::Hidden,
+                     cl::desc("Fix function entry count in profile use."));
+
 // Command line option to turn on CFG dot dump after profile annotation.
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -pgo-view-counts
 extern cl::opt<PGOViewCountsType> PGOViewCounts;
 
 // Command line option to specify the name of the function for CFG dump
 // Defined in Analysis/BlockFrequencyInfo.cpp:  -view-bfi-func-name=
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 
#endif
   F.setEntryCount(ProfileCount(FuncEntryCount, Function::PCT_Real));
   uint64_t FuncMaxCount = FuncEntryCount;
   for (auto &BB : F) {
     auto BI = findBBInfo(&BB);
     if (BI == nullptr)
       continue;
     FuncMaxCount = std::max(FuncMaxCount, BI->CountValue);
   }
+
   markFunctionAttributes(FuncEntryCount, FuncMaxCount);
 
   // Now annotate select instructions
   FuncInfo.SIVisitor.annotateSelects(F, this, &CountPosition);
   assert(CountPosition == ProfileCountSize);
 
   LLVM_DEBUG(FuncInfo.dumpInfo("after reading profile."));
 }
PreservedAnalyses PGOInstrumentationGen::run(Module &M,
   };
 
   if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI, IsCS))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
+// Using the ratio b/w sums of profile count values and BFI count values to
+// adjust the func entry count.
+static void fixFuncEntryCount(PGOUseFunc &Func, LoopInfo &LI,
+                              BranchProbabilityInfo &NBPI) {
+  Function &F = Func.getFunc();
+  BlockFrequencyInfo NBFI(F, NBPI, LI);
+  auto SumCount = APFloat::getZero(APFloat::IEEEdouble());
+  auto SumBFCount = APFloat::getZero(APFloat::IEEEdouble());
+  for (auto &BBI : F) {
+    uint64_t CountValue = 0;
+    uint64_t BFICountValue = 0;
+    if (!Func.getBBInfo(&BBI).CountValid)
+      continue;
+    auto BFICount = NBFI.getBlockProfileCount(&BBI);
+    if (!BFICount)
+      continue;
+
+    CountValue = Func.getBBInfo(&BBI).CountValue;
+    BFICountValue = BFICount.getValue();
+    SumCount.add(APFloat(CountValue * 1.0), APFloat::rmNearestTiesToEven);
+    SumBFCount.add(APFloat(BFICountValue * 1.0), APFloat::rmNearestTiesToEven);
+  }
+  if (!SumCount.isZero()) {
+    double Scale = 1.0;
+    if (SumBFCount.compare(APFloat(1.0)) == APFloat::cmpGreaterThan &&
+        SumBFCount.compare(SumCount) != APFloat::cmpEqual)
+      Scale = (SumCount / SumBFCount).convertToDouble();
+
+    if (Scale >= 1.01 || Scale <= 0.99) {
+      uint64_t FuncEntryCount = Func.getBBInfo(&*F.begin()).CountValue;
+      uint64_t NewEntryCount = FuncEntryCount;
+      if (NewEntryCount == 0)
+        NewEntryCount = 1;
+      NewEntryCount = (0.5 + NewEntryCount * Scale);
+      if (NewEntryCount == 0)
+        NewEntryCount = 1;
+      if (NewEntryCount != FuncEntryCount) {
+        F.setEntryCount(ProfileCount(NewEntryCount, Function::PCT_Real));
+        LLVM_DEBUG(dbgs() << "FixFuncEntryCount: in " << F.getName()
+                          << ", entry_count " << FuncEntryCount << " --> "
+                          << NewEntryCount << "\n");
+      }
+    }
+    return;
+  }
+  F.setEntryCount(ProfileCount(0, Function::PCT_Real));
+}
+
+// Compare the profile count values with BFI count values, and print out
+// the non-matching ones.
+static void verifyFuncBFI(PGOUseFunc &Func, LoopInfo &LI,
+                          BranchProbabilityInfo &NBPI) {
+  Function &F = Func.getFunc();
+  BlockFrequencyInfo NBFI(F, NBPI, LI);
+  bool PrintFunc = false;
+  unsigned BBNum = 0, BBNoMatchNum = 0, NonC0BBNum = 0;
+  for (auto &BBI : F) {
+    uint64_t CountValue = 0;
+    uint64_t BFICountValue = 0;
+
+    if (Func.getBBInfo(&BBI).CountValid)
+      CountValue = Func.getBBInfo(&BBI).CountValue;
+
+    BBNum++;
+    if (CountValue)
+      NonC0BBNum++;
+    auto BFICount = NBFI.getBlockProfileCount(&BBI);
+    if (BFICount)
+      BFICountValue = BFICount.getValue();
+
+    if (CountValue < PGOVerifyBFICutoff && BFICountValue < PGOVerifyBFICutoff)
+      continue;
+
+    uint64_t Diff = (BFICountValue >= CountValue) ? BFICountValue - CountValue
+                                                  : CountValue - BFICountValue;
+    if (Diff != 0 && Diff >= CountValue / 100 * PGOVerifyBFIRatio) {
+      BBNoMatchNum++;
+      if (!PrintFunc) {
+        dbgs() << "VerifyFuncBFI: in " << F.getName() << "\n";
+        PrintFunc = true;
+      }
+      dbgs() << "  BB " << BBI.getName() << ": Count=" << CountValue
+             << "  BFI Count=" << BFICountValue << "\n";
+    }
+  }
+  if (BBNoMatchNum)
+    dbgs() << "In function " << F.getName() << ": Num_of_BB = " << BBNum
+           << " Num_of_zerovalue_BB = " << NonC0BBNum
+           << " Num_of_non_matching_BB = " << BBNoMatchNum << "\n";
+}
+
 static bool annotateAllFunctions(
     Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName,
     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI, bool IsCS) {
   LLVM_DEBUG(dbgs() << "Read in profile counters: ");
   auto &Ctx = M.getContext();
   // Read the counter array from file.
   auto ReaderOrErr =
static bool annotateAllFunctions(
 
   // TODO: might need to change the warning once the clang option is finalized.
   if (!PGOReader->isIRLevelProfile()) {
     Ctx.diagnose(DiagnosticInfoPGOProfile(
         ProfileFileName.data(), "Not an IR level instrumentation profile"));
     return false;
   }
 
+  M.setProfileSummary(PGOReader->getSummary(IsCS).getMD(M.getContext()),
+                      IsCS ? ProfileSummary::PSK_CSInstr
+                           : ProfileSummary::PSK_Instr);
   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
   collectComdatMembers(M, ComdatMembers);
   std::vector<Function *> HotFunctions;
   std::vector<Function *> ColdFunctions;
   for (auto &F : M) {
     if (F.isDeclaration())
       continue;
     auto *BPI = LookupBPI(F);
if (PGOViewRawCounts != PGOVCT_None &&
           WriteGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
         else
           ViewGraph(&Func, Twine("PGORawCounts_") + Func.getFunc().getName());
       else if (PGOViewRawCounts == PGOVCT_Text) {
         dbgs() << "pgo-view-raw-counts: " << Func.getFunc().getName() << "\n";
         Func.dumpInfo();
       }
     }
+
+    // Verify BlockFrequency and fix entry func entry count.
+    if (PGOVerifyBFI || PGOFixEntryCount) {
+      LoopInfo LI{DominatorTree(F)};
+      BranchProbabilityInfo NBPI(F, LI);
+      if (PGOFixEntryCount)
+        fixFuncEntryCount(Func, LI, NBPI);
+      if (PGOVerifyBFI)
+        verifyFuncBFI(Func, LI, NBPI);
+    }
   }
-  M.setProfileSummary(PGOReader->getSummary(IsCS).getMD(M.getContext()),
-                      IsCS ? ProfileSummary::PSK_CSInstr
-                           : ProfileSummary::PSK_Instr);
 
   // Set function hotness attribute from the profile.
   // We have to apply these attributes at the end because their presence
   // can affect the BranchProbabilityInfo of any callers, resulting in an
   // inconsistent MST between prof-gen and prof-use.
   for (auto &F : HotFunctions) {
     F->addFnAttr(Attribute::InlineHint);
     LLVM_DEBUG(dbgs() << "Set inline attribute to function: " << F->getName()

llvm/test/Transforms/PGOProfile/Inputs/fix_bfi.proftext

+# IR level Instrumentation Flag
+:ir
+sort_basket
+# Func Hash:
[phone]
+# Num Counters:
+7
+# Counter Values:
[phone]
[phone]
[phone]
[phone]
[phone]
+6990942
+6013544
+

llvm/test/Transforms/PGOProfile/fix_bfi.ll

+; RUN: llvm-profdata merge %S/Inputs/fix_bfi.proftext -o %t.profdata
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -S -pgo-fix-entry-count=true -pgo-verify-bfi-ratio=2 -pgo-verify-bfi=true 2>&1 | FileCheck %s --check-prefix=FIX-CHECK
+; RUN: opt < %s -pgo-instr-use -pgo-test-profile-file=%t.profdata -S -pgo-fix-entry-count=false -pgo-verify-bfi-ratio=2 -pgo-verify-bfi=true 2>&1 | FileCheck %s --check-prefix=NOFIX-CHECK
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.basket = type { %struct.arc*, i64, i64 }
+%struct.arc = type { i64, %struct.node*, %struct.node*, i32, %struct.arc*, %struct.arc*, i64, i64 }
+%struct.node = type { i64, i32, %struct.node*, %struct.node*, %struct.node*, %struct.node*, %struct.arc*, %struct.arc*, %struct.arc*, %struct.arc*, i64, i64, i32, i32 }
+
+@perm = internal unnamed_addr global [351 x %struct.basket*] zeroinitializer, align 16
+
+define dso_local void @sort_basket(i64 %min, i64 %max) {
+entry:
+  %add = add nsw i64 %min, %max
+  %div = sdiv i64 %add, 2
+  %arrayidx = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %div
+  %0 = load %struct.basket*, %struct.basket** %arrayidx, align 8
+  %abs_cost = getelementptr inbounds %struct.basket, %struct.basket* %0, i64 0, i32 2
+  %1 = load i64, i64* %abs_cost, align 8
+  br label %do.body
+
+do.body:
+  %r.0 = phi i64 [ %max, %entry ], [ %r.2, %if.end ]
+  %l.0 = phi i64 [ %min, %entry ], [ %l.2, %if.end ]
+  br label %while.cond
+
+while.cond:
+  %l.1 = phi i64 [ %l.0, %do.body ], [ %inc, %while.body ]
+  %arrayidx1 = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %l.1
+  %2 = load %struct.basket*, %struct.basket** %arrayidx1, align 8
+  %abs_cost2 = getelementptr inbounds %struct.basket, %struct.basket* %2, i64 0, i32 2
+  %3 = load i64, i64* %abs_cost2, align 8
+  %cmp = icmp sgt i64 %3, %1
+  br i1 %cmp, label %while.body, label %while.cond3
+
+while.body:
+  %inc = add nsw i64 %l.1, 1
+  br label %while.cond
+
+while.cond3:
+  %r.1 = phi i64 [ %r.0, %while.cond ], [ %dec, %while.body7 ]
+  %arrayidx4 = getelementptr inbounds [351 x %struct.basket*], [351 x %struct.basket*]* @perm, i64 0, i64 %r.1
+  %4 = load %struct.basket*, %struct.basket** %arrayidx4, align 8
+  %abs_cost5 = getelementptr inbounds %struct.basket, %struct.basket* %4, i64 0, i32 2
+  %5 = load i64, i64* %abs_cost5, align 8
+  %cmp6 = icmp sgt i64 %1, %5
+  br i1 %cmp6, label %while.body7, label %while.end8
+
+while.body7:
+  %dec = add nsw i64 %r.1, -1
+  br label %while.cond3
+
+while.end8:
+  %cmp9 = icmp slt i64 %l.1, %r.1
+  br i1 %cmp9, label %if.then, label %if.end
+
+if.then:
+  %6 = bitcast %struct.basket** %arrayidx1 to i64*
+  %7 = load i64, i64* %6, align 8
+  store %struct.basket* %4, %struct.basket** %arrayidx1, align 8
+  %8 = bitcast %struct.basket** %arrayidx4 to i64*
+  store i64 %7, i64* %8, align 8
+  br label %if.end
+
+if.end:
+  %cmp14 = icmp sgt i64 %l.1, %r.1
+  %not.cmp14 = xor i1 %cmp14, true
+  %9 = zext i1 %not.cmp14 to i64
+  %r.2 = sub i64 %r.1, %9
+  %not.cmp1457 = xor i1 %cmp14, true
+  %inc16 = zext i1 %not.cmp1457 to i64
+  %l.2 = add nsw i64 %l.1, %inc16
+  %cmp19 = icmp sgt i64 %l.2, %r.2
+  br i1 %cmp19, label %do.end, label %do.body
+
+do.end:
+  %cmp20 = icmp sgt i64 %r.2, %min
+  br i1 %cmp20, label %if.then21, label %if.end22
+
+if.then21:
+  call void @sort_basket(i64 %min, i64 %r.2)
+  br label %if.end22
+
+if.end22:
+  %cmp23 = icmp slt i64 %l.2, %max
+  %cmp24 = icmp slt i64 %l.2, 51
+  %or.cond = and i1 %cmp23, %cmp24
+  br i1 %or.cond, label %if.then25, label %if.end26
+
+if.then25:
+  call void @sort_basket(i64 %l.2, i64 %max)
+  br label %if.end26
+
+if.end26:
+  ret void
+}
+; FIX-CHECK: VerifyFuncBFI: in sort_basket
+; FIX-CHECK:   BB entry: Count=13338888  BFI Count=12949310
+; FIX-CHECK:   BB do.end: Count=13338888  BFI Count=12949310
+; FIX-CHECK:   BB if.end22: Count=13338888  BFI Count=12949310
+; FIX-CHECK:   BB if.end26: Count=13338888  BFI Count=12949310
+; FIX-CHECK: In function sort_basket: Num_of_BB = 14 Num_of_zerovalue_BB = 14 Num_of_non_matching_BB = 4
+; NOFIX-CHECK: VerifyFuncBFI: in sort_basket
+; NOFIX-CHECK:   BB do.body: Count=39637749  BFI Count=40801304
+; NOFIX-CHECK:   BB while.cond: Count=80655628  BFI Count=83956530
+; NOFIX-CHECK:   BB while.body: Count=41017879  BFI Count=42370585
+; NOFIX-CHECK:   BB while.cond3: Count=71254487  BFI Count=73756204
+; NOFIX-CHECK:   BB while.body7: Count=31616738  BFI Count=32954900
+; NOFIX-CHECK:   BB while.end8: Count=39637749  BFI Count=40801304
+; NOFIX-CHECK:   BB if.then: Count=32743703  BFI Count=33739540
+; NOFIX-CHECK:   BB if.end: Count=39637749  BFI Count=40801304
+; NOFIX-CHECK:   BB if.then25: Count=6013544  BFI Count=6277124
+; NOFIX-CHECK: In function sort_basket: Num_of_BB = 14 Num_of_zerovalue_BB = 14 Num_of_non_matching_BB = 9
+