LoopRotate: Add code to update branch weights

[MatzeB]

Summary

While loop rotation updates the branch_weights correctly for the most part there were some branches missing runtime unroll. This adds code to the loop rotation transformation to ensure that the computed block execution counts for the loop bodies are the same before and after the transformation.

Invariants and heuristics are explained in the comment in the new updateBranchWeights() function.

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

271–282

I have an alternative version of this, but wasn't sure how people feel about using non-ASCII characters:

[paulkirth]

llvm/include/llvm/IR/ProfDataUtils.h

67–71

Would you mind putting the changes to ProfDataUtils in a separate patch? I think these are good additions to the library, so I think it's better if they go in their own commit. Since it just renames an internal interface(practically speaking), it can probably be marked NFC/NFCI.

[paulkirth]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

291–306

This could probably be a helper function. It would also allow for expressive names for the Weight[0]/Weight[1] values, which will probably make it easier to follow.

Alternatively, you could group all of these counts into a struct. I'm not convinced that is worth it in this case, but it may make the code simpler to reason about and keep all the logic regarding the heuristic together.

This does come down to personal coding style, so don't consider these suggestions blocking.

[MatzeB]

llvm/include/llvm/IR/ProfDataUtils.h

67–71

Extracted as D157937 now.

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

291–306

What's the point though? The only other thing here is the construction of two MDNodes. Feels needlessly complicated to introduce a struct and separate function just for that...

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

291–306

I did introduce two local variables now, that give a name to Weights[0] and Weights[1], hope that is enough to resolve this.

[wenlei]

I think the heuristics are better than doing nothing in theory. Though one other thing to note is that for AutoFDO, if the profiled build also has the loop rotated, the incoming counts won't be right to begin with -- if the two branches after rotate are executed A times and B times, the original branch should be executed A+B times, but AutoFDO will annotate it with max(A,B) times for the original branch.

You may want to double check that for loop rotate happening in pass1 profiling build, the heuristic also generates reasonable counts comparing to ground truth.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

289

did you mean y1 == y - y0 # how many iterations loop body was executed?

290

Yeah, this is what i meant by saying "loop rotate count is unfixable"..

302

Heuristic is somewhat arbitrary anyways but I would still keep ExitCount0 as non-zero, so it's a "live" path to be conservative. Also BFI doesn't like zero edge counts is another reason..

[wenlei]

IIRC, mcf in spec has a function sort_basket which is known to be problematic for maintaining loop rotate counts, if you want to play with it a bit, especially the guessing part of the heuristic.

[paulkirth]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

291–306

Sorry, I could have worded that better as a "just a suggestion you can feel free to ignore". I tried to convey that at the end, but clearly missed my mark.

I was fine with the previous version, but those two thoughts came to mind, so I mentioned them. So nothing to resolve :)

What's the point though? The only other thing here is the construction of two MDNodes. Feels needlessly complicated to introduce a struct and separate function just for that...

Fair points. My thoughts were more about making this function easier to understand, but you're right that it probably isn't necessary and isn't that hard to follow right now.

Please feel free to ignore those suggestions, or restore the previous version if you'd rather.

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

302

I had that in earlier versions, but my experience while writing the tests anyway was that BFI handles zero-count-edges fine and the results just seem more natural and easier to reason about this way. While assigning non-zero immediately felt somewhat murky in what sort of "epsilon" should be used at all...

[wenlei]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

302

Problem with BFI often gets exposed with larger CFG that has implicit constraints, so small test case doesn't always show. Is there any specific problem you ran into with having ExitCount0 as 1? 1 should be a reasonable guess too. There are many places where we try to avoid zero when uncertain, which is sort of an unspoken convention.

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

302

The question when setting this to "1" is how you set the other case of the condbr. We can't just leave the other side as-is or risk ending up with ratios like 1:2 where the "1" clearly isn't a small number anymore.

But for putting something else here, do I go for 1:20, 1:100, 1:1000? I don't think I have a good feeling/guidance for that...

[MatzeB]

Change code to avoid zero branch-weights.

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

302

I now added some scaling logic and the code attempts to hit a 1:128 or higher ratio for the "nearly never taken" edge.

[wenlei]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

308

nit: follow convention for variable naming.

309–310

Could OrigLoopBackedgeCount + OrigLoopExitCount already overflow and defeat the check?

Maybe spell it explicitly with OrigLoopBackedgeCount >= high_bit || OrigLoopExitCount >= high_bit?

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

302

FWIW: Looked around and started a discussion on "likely"/"unlikely" branch weights in D158642 where I encountered the same problem.

[MatzeB]

• Fixed overflow test when scaling up weights.
• Still need a better way than hardcoding 127 as "likely" branch weight; hoping that people can give me some hint in the discussion I started in https://reviews.llvm.org/D158642

[wenlei]

I agree that hard coded probability is not great. But I also don't think there is a one-size-fit-all answer here. EH path can be unlikely, z-trip loop can be unlikely, [[unlikely]] hint can be unlikely, but they don't necessarily share the same probability.

I think something like InlineConstants, a global ProbabilityConstants may be an alternative.

But we can defer that part, and the change as is lgtm.

[mtrofin]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

294

nit: can you init ExitWeight0 at declaration (to avoid potential joys due to uninitialization later). In fact, setting it to 0 and flipping the conditional below and not having an else would do it.

690

const bool?

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

294

This is deliberately left uninitialized! The idea is that every branch in the following ifs will set a value for it. Leaving the variable uninitialized here, means we will get a compiler warning if we forget to set the value on any branch below which I think is more valuable than setting some kind of safe default here but not getting a warning anymore.

690

Sure, will add. (though FWIW const could be applied to the majority of the variables and parameters in all of LLVM. I just have a feeling the existing code usually limits const usage to pointer and reference targets...)

[mtrofin]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

250

nit: HasConditionalPreHeader.

294

Is it safe to rely on warnings though - is there at least a bot that treats uninitialized values as errors? But that aside, looks like 0 is the value when ConditionalPreHeader anyway, meaning 0 wouldn't be some safe default, rather, it's exactly what you'd want (assuming the if condition were swapped)

[MatzeB]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

294

Not sure if we have a -Werror bot, but the uninitialized variable warnings has always been part of -Wall. Also LLVM is warning free for most people (certainly is for me), new warning attract attention immediately. I have seen multiple instances in the past where someone added a new case to a complicated if-cascade but forgot to set a variables where the default was not suitable...

Probably not worth getting hung up on this particular one, so I'll change the default to = 0 and drop the ConditionalPreHeader case. But for the record: I disagree and certainly will not change other places in LLVM where I used similar patterns :)

[mtrofin]

lgtm. May be worth waiting for @xur 's feedback for these patches (he's out until Monday I think), he's spent quite some time in PGO land.

[MatzeB]

Factor out weights constant to match the style used in D158642

[MatzeB]

It seems there is no further feedback. Landing this now.

llvm/include/llvm/IR/ProfDataUtils.h

 ///
 /// \param ProfileData A pointer to an MDNode.
 /// \param [out] Weights An output vector to fill with branch weights
 /// \returns True if weights were extracted, False otherwise. When false Weights
 /// will be cleared.
 bool extractBranchWeights(const MDNode *ProfileData,
                           SmallVectorImpl<uint32_t> &Weights);
 
+/// Faster version of extractBranchWeights() that skips checks and must only
+/// be called with "branch_weights" metadata nodes.
+void extractFromBranchWeightMD(const MDNode *ProfileData,
+                               SmallVectorImpl<uint32_t> &Weights);
+
 /// Extract branch weights attatched to an Instruction
 ///
 /// \param I The Instruction to extract weights from.
 /// \param [out] Weights An output vector to fill with branch weights
 /// \returns True if weights were extracted, False otherwise. When false Weights
 /// will be cleared.
 bool extractBranchWeights(const Instruction &I,
                           SmallVectorImpl<uint32_t> &Weights);

llvm/lib/IR/ProfDataUtils.cpp

 // correctly, and can change the behavior in the future if the layout changes
 
 // The index at which the weights vector starts
 constexpr unsigned WeightsIdx = 1;
 
 // the minimum number of operands for MD_prof nodes with branch weights
 constexpr unsigned MinBWOps = 3;
 
-bool extractWeights(const MDNode *ProfileData,
-                    SmallVectorImpl<uint32_t> &Weights) {
-  // Assume preconditions are already met (i.e. this is valid metadata)
-  assert(ProfileData && "ProfileData was nullptr in extractWeights");
-  unsigned NOps = ProfileData->getNumOperands();
-
-  assert(WeightsIdx < NOps && "Weights Index must be less than NOps.");
-  Weights.resize(NOps - WeightsIdx);
-
-  for (unsigned Idx = WeightsIdx, E = NOps; Idx != E; ++Idx) {
-    ConstantInt *Weight =
-        mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx));
-    assert(Weight && "Malformed branch_weight in MD_prof node");
-    assert(Weight->getValue().getActiveBits() <= 32 &&
-           "Too many bits for uint32_t");
-    Weights[Idx - WeightsIdx] = Weight->getZExtValue();
-  }
-  return true;
-}
-
 // We may want to add support for other MD_prof types, so provide an abstraction
 // for checking the metadata type.
 bool isTargetMD(const MDNode *ProfData, const char *Name, unsigned MinOps) {
   // TODO: This routine may be simplified if MD_prof used an enum instead of a
   // string to differentiate the types of MD_prof nodes.
   if (!ProfData || !Name || MinOps < 2)
     return false;
 

 
 MDNode *getValidBranchWeightMDNode(const Instruction &I) {
   auto *ProfileData = getBranchWeightMDNode(I);
   if (ProfileData && ProfileData->getNumOperands() == 1 + I.getNumSuccessors())
     return ProfileData;
   return nullptr;
 }
 
+void extractFromBranchWeightMD(const MDNode *ProfileData,
+                               SmallVectorImpl<uint32_t> &Weights) {
+  assert(isBranchWeightMD(ProfileData) && "wrong metadata");
+
+  unsigned NOps = ProfileData->getNumOperands();
+  assert(WeightsIdx < NOps && "Weights Index must be less than NOps.");
+  Weights.resize(NOps - WeightsIdx);
+
+  for (unsigned Idx = WeightsIdx, E = NOps; Idx != E; ++Idx) {
+    ConstantInt *Weight =
+        mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx));
+    assert(Weight && "Malformed branch_weight in MD_prof node");
+    assert(Weight->getValue().getActiveBits() <= 32 &&
+           "Too many bits for uint32_t");
+    Weights[Idx - WeightsIdx] = Weight->getZExtValue();
+  }
+}
+
 bool extractBranchWeights(const MDNode *ProfileData,
                           SmallVectorImpl<uint32_t> &Weights) {
   if (!isBranchWeightMD(ProfileData))
     return false;
-  return extractWeights(ProfileData, Weights);
+  extractFromBranchWeightMD(ProfileData, Weights);
+  return true;
 }
 
 bool extractBranchWeights(const Instruction &I,
                           SmallVectorImpl<uint32_t> &Weights) {
   auto *ProfileData = I.getMetadata(LLVMContext::MD_prof);
   return extractBranchWeights(ProfileData, Weights);
 }
 

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/ProfDataUtils.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
if (!Exits.empty()) {
     // have compile-time effect only.
     return any_of(Exits, [](const BasicBlock *BB) {
       return !BB->getPostdominatingDeoptimizeCall();
     });
   }
   return false;
 }
 
+static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI,
+                                bool ConditionalPreHeader, bool SuccsSwapped) {
+  MDNode *WeightMD = getBranchWeightMDNode(PreHeaderBI);
+  if (WeightMD == nullptr)
+    return;
+
+  // LoopBI should currently be a clone of PreHeaderBI with the same
+  // metadata. But we double check to make sure we don't have a degenerate case
+  // where instsimplify changed the instructions.
+  if (WeightMD != getBranchWeightMDNode(LoopBI))
+    return;
+
+  SmallVector<uint32_t, 2> Weights;
+  extractFromBranchWeightMD(WeightMD, Weights);
+  if (Weights.size() != 2)
+    return;
+
+  if (SuccsSwapped)
+    std::swap(Weights[0], Weights[1]);
+
+  // Update branch weights. Consider the following edge-counts:
+  //
+  //    |  |--------             |
+  //    V  V       |             V
+  //   Br i1 ...   |            Br i1 ...
+  //   |       |   |            |     |
+  //  x|      y|   |  becomes:  |   y0|  |-----
+  //   V       V   |            |     V  V    |
+  // Exit    Loop  |            |     Loop    |
+  //           |   |            |   Br i1 ... |
+  //           -----            |   |      |  |
+  //                          x0| x1|   y1 |  |
+  //                            V   V      ----
+  //                            Exit
+  //
+  // The following must hold:
+  //  -  x == x0 + x1          # counts to "exit" must stay the same.
+  //  - y0 == x - x0 == x1     # how often loop was entered at all.
+  //  - y1 == y - x0
+  // Unfortunately we cannot generally deduce the ratio between x0 and x1 and
+  // have to guess it.
+
+  uint32_t ExitCount0; // aka x0
+  if (!ConditionalPreHeader) {
+    // pre-header turned into an unconditional jump.
+    ExitCount0 = 0;
+  } else {
+    // Here we cannot know how many 0-trip count loops we have, so we guess:
+    if (Weights[1] > Weights[0]) {
+      // If the loop count is bigger than the exit count then we set
+      // probabilities as if 0-trip count never happens.
+      ExitCount0 = 0;
+    } else {
+      // If there's a higher exit-count than backedge-count then we set
+      // probabilities as if there are only 0-trip and 1-trip cases.
+      ExitCount0 = Weights[0] - Weights[1];
+    }
+  }
+  uint32_t ExitCount1 = Weights[0] - ExitCount0;    // aka x1
+  uint32_t EnterCount = ExitCount1;                 // aka y0
+  uint32_t LoopBackCount = Weights[1] - EnterCount; // aka y1
+
+  MDBuilder MDB(LoopBI.getContext());
+  MDNode *LoopWeightMD =
+      MDB.createBranchWeights(SuccsSwapped ? LoopBackCount : ExitCount1,
+                              SuccsSwapped ? ExitCount1 : LoopBackCount);
+  LoopBI.setMetadata(LLVMContext::MD_prof, LoopWeightMD);
+  if (ConditionalPreHeader) {
+    MDNode *PreHeaderWeightMD =
+        MDB.createBranchWeights(SuccsSwapped ? EnterCount : ExitCount0,
+                                SuccsSwapped ? ExitCount0 : EnterCount);
+    PreHeaderBI.setMetadata(LLVMContext::MD_prof, PreHeaderWeightMD);
+  }
+}
+
 /// Rotate loop LP. Return true if the loop is rotated.
 ///
 /// \param SimplifiedLatch is true if the latch was just folded into the final
 /// loop exit. In this case we may want to rotate even though the new latch is
 /// now an exiting branch. This rotation would have happened had the latch not
 /// been simplified. However, if SimplifiedLatch is false, then we avoid
 /// rotating loops in which the latch exits to avoid excessive or endless
 /// rotation. LoopRotate should be repeatable and converge to a canonical
do {
     if (MSSAU && VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
 
     // Find new Loop header. NewHeader is a Header's one and only successor
     // that is inside loop.  Header's other successor is outside the
     // loop.  Otherwise loop is not suitable for rotation.
     BasicBlock *Exit = BI->getSuccessor(0);
     BasicBlock *NewHeader = BI->getSuccessor(1);
-    if (L->contains(Exit))
+    bool BISuccsSwapped = L->contains(Exit);
+    if (BISuccsSwapped)
       std::swap(Exit, NewHeader);
     assert(NewHeader && "Unable to determine new loop header");
     assert(L->contains(NewHeader) && !L->contains(Exit) &&
            "Unable to determine loop header and exit blocks");
 
     // This code assumes that the new header has exactly one predecessor.
     // Remove any single-entry PHI nodes in it.
     assert(NewHeader->getSinglePredecessor() &&
do {
     // the loop into the preheader we've simplified instructions and the
     // duplicated conditional branch may now be branching on a constant.  If it is
     // branching on a constant and if that constant means that we enter the loop,
     // then we fold away the cond branch to an uncond branch.  This simplifies the
     // loop in cases important for nested loops, and it also means we don't have
     // to split as many edges.
     BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
     assert(PHBI->isConditional() && "Should be clone of BI condbr!");
-    if (!isa<ConstantInt>(PHBI->getCondition()) ||
+    bool ConditionalPreHeader =
+        !isa<ConstantInt>(PHBI->getCondition()) ||
         PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
-        NewHeader) {
+            NewHeader;
+
+    updateBranchWeights(*PHBI, *BI, ConditionalPreHeader, BISuccsSwapped);
+
+    if (ConditionalPreHeader) {
       // The conditional branch can't be folded, handle the general case.
       // Split edges as necessary to preserve LoopSimplify form.
 
       // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
       // thus is not a preheader anymore.
       // Split the edge to form a real preheader.
       BasicBlock *NewPH = SplitCriticalEdge(
                                             OrigPreheader, NewHeader,

llvm/test/Transforms/LoopRotate/update-branch-weights.ll

+; RUN: opt < %s -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s --check-prefixes=BFI_BEFORE
+; RUN: opt < %s -passes='loop(loop-rotate),print<block-freq>' -disable-output 2>&1 | FileCheck %s --check-prefixes=BFI_AFTER
+; RUN: opt < %s -passes='loop(loop-rotate)' -S | FileCheck %s --check-prefixes=IR
+
+@g = global i32 0
+
+; We should get the same "count =" results for "outer_loop_body" and
+; "inner_loop_body" before and after the transformation.
+
+; BFI_BEFORE-LABEL: block-frequency-info: func0
+; BFI_BEFORE: - entry: float = 1.0, int = 8, count = 1
+; BFI_BEFORE: - outer_loop_header: float = 1001.0, int = 8008, count = 1001
+; BFI_BEFORE: - outer_loop_body: float = 1000.0, int = 8000, count = 1000
+; BFI_BEFORE: - inner_loop_header: float = 4000.0, int = 32000, count = 4000
+; BFI_BEFORE: - inner_loop_body: float = 3000.0, int = 24000, count = 3000
+; BFI_BEFORE: - inner_loop_exit: float = 1000.0, int = 8000, count = 1000
+; BFI_BEFORE: - outer_loop_exit: float = 1.0, int = 8, count = 1
+
+; BFI_AFTER-LABEL: block-frequency-info: func0
+; BFI_AFTER: - entry: float = 1.0, int = 8, count = 1
+; BFI_AFTER: - outer_loop_body: float = 1000.0, int = 7999, count = 1000
+; BFI_AFTER: - inner_loop_body: float = 3000.0, int = 23999, count = 3000
+; BFI_AFTER: - inner_loop_exit: float = 1000.0, int = 7999, count = 1000
+; BFI_AFTER: - outer_loop_exit: float = 1.0, int = 8, count = 1
+
+; IR: inner_loop_body:
+; IR:   br i1 %cmp1, label %inner_loop_body, label %inner_loop_exit, !prof [[PROF0:![0-9]+]]
+; IR: inner_loop_exit:
+; IR:   br i1 %cmp0, label %outer_loop_body, label %outer_loop_exit, !prof [[PROF1:![0-9]+]]
+;
+; A function with known loop-bounds where after loop-rotation we end with an
+; unconditional branch in the pre-header.
+define void @func0() !prof !0 {
+entry:
+  br label %outer_loop_header
+
+outer_loop_header:
+  %i0 = phi i32 [0, %entry], [%i0_inc, %inner_loop_exit]
+  %cmp0 = icmp slt i32 %i0, 1000
+  br i1 %cmp0, label %outer_loop_body, label %outer_loop_exit, !prof !1
+
+outer_loop_body:
+  store volatile i32 %i0, ptr @g, align 4
+  br label %inner_loop_header
+
+inner_loop_header:
+  %i1 = phi i32 [0, %outer_loop_body], [%i1_inc, %inner_loop_body]
+  %cmp1 = icmp slt i32 %i1, 3
+  br i1 %cmp1, label %inner_loop_body, label %inner_loop_exit, !prof !2
+
+inner_loop_body:
+  store volatile i32 %i1, ptr @g, align 4
+  %i1_inc = add i32 %i1, 1
+  br label %inner_loop_header
+
+inner_loop_exit:
+  %i0_inc = add i32 %i0, 1
+  br label %outer_loop_header
+
+outer_loop_exit:
+  ret void
+}
+
+; BFI_BEFORE-LABEL: block-frequency-info: func1
+; BFI_BEFORE: - entry: float = 1.0, int = 8, count = 1024
+; BFI_BEFORE: - loop_header: float = 21.0, int = 168, count = 21504
+; BFI_BEFORE: - loop_body: float = 20.0, int = 160, count = 20480
+; BFI_BEFORE: - loop_exit: float = 1.0, int = 8, count = 1024
+
+; BFI_AFTER-LABEL: block-frequency-info: func1
+; BFI_AFTER: - entry: float = 1.0, int = 8, count = 1024
+; BFI_AFTER: - loop_body.lr.ph: float = 1.0, int = 8, count = 1024
+; BFI_AFTER: - loop_body: float = 20.0, int = 160, count = 20480
+; BFI_AFTER: - loop_header.loop_exit_crit_edge: float = 1.0, int = 8, count = 1024
+; BFI_AFTER: - loop_exit: float = 1.0, int = 8, count = 1024
+
+; IR: entry:
+; IR:   br i1 %cmp1, label %loop_body.lr.ph, label %loop_exit, !prof [[PROF2:![0-9]+]]
+
+; IR: loop_body:
+; IR:   br i1 %cmp, label %loop_body, label %loop_header.loop_exit_crit_edge, !prof [[PROF3:![0-9]+]]
+
+; A function with unknown loop-bounds so loop-rotation so we end up with a
+; condition jump in pre-header and loop body. Variant where branch_weight
+; shows body is executed more often than header.
+define void @func1(i32 %n) !prof !3 {
+entry:
+  br label %loop_header
+
+loop_header:
+  %i = phi i32 [0, %entry], [%i_inc, %loop_body]
+  %cmp = icmp slt i32 %i, %n
+  br i1 %cmp, label %loop_body, label %loop_exit, !prof !4
+
+loop_body:
+  store volatile i32 %i, ptr @g, align 4
+  %i_inc = add i32 %i, 1
+  br label %loop_header
+
+loop_exit:
+  ret void
+}
+
+; BFI_BEFORE-LABEL: block-frequency-info: func2
+; BFI_BEFORE: - entry: float = 1.0, int = 256, count = 1024
+; BFI_BEFORE: - loop_header: float = 1.0312, int = 264, count = 1056
+; BFI_BEFORE: - loop_body: float = 0.03125, int = 8, count = 32
+; BFI_BEFORE: - loop_exit: float = 1.0, int = 256, count = 1024
+
+; BFI_AFTER-LABEL: block-frequency-info: func2
+; - entry: float = 1.0, int = 256, count = 1024
+; - loop_body.lr.ph: float = 0.03125, int = 8, count = 32
+; - loop_body: float = 0.03125, int = 8, count = 32
+; - loop_header.loop_exit_crit_edge: float = 0.03125, int = 8, count = 32
+; - loop_exit: float = 1.0, int = 256, count = 1024
+
+; IR: entry:
+; IR:   br i1 %cmp1, label %loop_exit, label %loop_body.lr.ph, !prof [[PROF4:![0-9]+]]
+
+; IR: loop_body:
+; IR:   br i1 %cmp, label %loop_header.loop_exit_crit_edge, label %loop_body, !prof [[PROF5:![0-9]+]]
+
+; A function with unknown loop-bounds so loop-rotation so we end up with a
+; condition jump in pre-header and loop body. Variant where branch_weight
+; shows loop-exit count higher than backedge counts.
+define void @func2(i32 %n) !prof !3 {
+entry:
+  br label %loop_header
+
+loop_header:
+  %i = phi i32 [0, %entry], [%i_inc, %loop_body]
+  %cmp = icmp slt i32 %i, %n
+  br i1 %cmp, label %loop_exit, label %loop_body, !prof !5
+
+loop_body:
+  store volatile i32 %i, ptr @g, align 4
+  %i_inc = add i32 %i, 1
+  br label %loop_header
+
+loop_exit:
+  ret void
+}
+
+!0 = !{!"function_entry_count", i64 1}
+!1 = !{!"branch_weights", i32 1000, i32 1}
+!2 = !{!"branch_weights", i32 3000, i32 1000}
+!3 = !{!"function_entry_count", i64 1024}
+!4 = !{!"branch_weights", i32 20480, i32 1024}
+!5 = !{!"branch_weights", i32 10240, i32 320}
+
+; IR: [[PROF0]] = !{!"branch_weights", i32 2000, i32 1000}
+; IR: [[PROF1]] = !{!"branch_weights", i32 999, i32 1}
+; IR: [[PROF2]] = !{!"branch_weights", i32 1024, i32 0}
+; IR: [[PROF3]] = !{!"branch_weights", i32 19456, i32 1024}
+; IR: [[PROF4]] = !{!"branch_weights", i32 9920, i32 320}
+; IR: [[PROF5]] = !{!"branch_weights", i32 320, i32 0}

llvm/test/Transforms/LoopSimplify/merge-exits.ll

 ; CHECK-NEXT:    [[T4]] = fadd float [[T3]], [[DISTERBHI_04]]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[T7:%.*]] = getelementptr float, ptr [[PEAKWEIGHT]], i64 [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    [[T8:%.*]] = load float, ptr [[T7]], align 4
 ; CHECK-NEXT:    [[T9]] = fadd float [[T8]], [[PEAKCOUNT_02]]
 ; CHECK-NEXT:    [[T10:%.*]] = fcmp olt float [[T4]], 2.500000e+00
 ; CHECK-NEXT:    [[T12:%.*]] = icmp sgt i64 [[TMP0]], [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[T10]], [[T12]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[BB]], label [[BB1_BB3_CRIT_EDGE:%.*]], !prof [[PROF0]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[BB]], label [[BB1_BB3_CRIT_EDGE:%.*]], !prof [[PROF1:![0-9]+]]
 ; CHECK:       bb1.bb3_crit_edge:
 ; CHECK-NEXT:    [[T4_LCSSA:%.*]] = phi float [ [[T4]], [[BB]] ]
 ; CHECK-NEXT:    [[T9_LCSSA:%.*]] = phi float [ [[T9]], [[BB]] ]
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    [[PEAKCOUNT_0_LCSSA:%.*]] = phi float [ [[T9_LCSSA]], [[BB1_BB3_CRIT_EDGE]] ], [ [[T0]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[DISTERBHI_0_LCSSA:%.*]] = phi float [ [[T4_LCSSA]], [[BB1_BB3_CRIT_EDGE]] ], [ 0.000000e+00, [[ENTRY]] ]
 ; CHECK-NEXT:    [[T13:%.*]] = fdiv float [[PEAKCOUNT_0_LCSSA]], [[DISTERBHI_0_LCSSA]]