Update loop branch_weight metadata after loop rotation.

[trentxintong]

Summary

Update loop branch_weight metadata after loop rotation.

In case we have branch_weight in the unrotated loop header, we update
it after rotation, more specifically we update the branch in the guard
block and the branch in the rotated latch block.

[danielcdh]

test/Transforms/LoopRotate/loop-rotate-pgo.ll

60

I'm a little confused the logic here. For the following code:

L1:
if (cond) { // taken probability 7/35

stmt;
goto L1;

}

The loop rotate originally transforms it to:

if (cond) { // taken probability 7/35
L1:

stmt;
if (cond) { // taken probability 7/35
  goto L1;
}

}

Your patch change it to:

if (cond) { // taken probability 7/28
L1:

stmt
if (cond) { // taken probability 1/7
  goto L1;
}

}

Assuming "cond" has fixed taken probability, the original probability seems more correct to me? Or am I missing something?

[trentxintong]

@danielcdh Its the true the cond is not changed, but the inputs to the condition has changed, before you were testing with index variable in the loop header, now u have 2 conditions and the SSA values you use in the conditions have changed, so the probability needs to be adjusted. I will explain more when i get to office.

[trentxintong]

After we rotate the loop, we duplicate the comparison the old header into the guard block and we move the header to the end of the loop. So basically we have 2 branches that carry the branch_weight metadata they need to be adjusted. With this patch, we only do the adjustment for loop with only 1 exitting block, if the loop has early exits, its harder to adjust the branch weight properly. e.g. if we have an early exit in the loop, we will not be able to tell whether the latch block will ever be reached after rotation, not to mention to adjust its branch weight, (we need to look at the branch weights of the early exits to do this properly).

There are 2 conditions that are constant after rotation, (1) # of times the loop body is executed and (2) the # of times the exit block is executed. (these are the values we can get by extracting the prof metadata from the header branch before rotation). The backedge weight should simply be the # of times the loop body is executed - # of times the loop exit is executed. With the loop exit count, loop body weight and loop backedge weight, we can compute the branch weight for the guard block.

This is true iff the loop executes at least once every time. If the loop body execute seldom, they we can not do it (and we will get a negative backedge weight num with # of times the loop body is executed - # of times the loop exit is executed.) In this case, we cap the backedge # to 1 (should be 0). And with this information we can compute loop exit weight and all the other weights.

Thats roughly what the patch is doing and how the numbers in the test case is computed.

[mkuper]

lib/Transforms/Scalar/LoopRotation.cpp

476

Also, regardless of the rest of the discussion - I don't think we should drop the metadata on the floor if we fail.

I don't think "No data is better than imprecise data" is right in the general case, but that's arguable. Specifically here, though, we're imprecise even if updateLoopEstimatedBranchWeight() succeeds, because of the assumptions we make on the distribution.

[trentxintong]

lib/Transforms/Scalar/LoopRotation.cpp

476

I am fine changing this, i.e. keeping the metadata when we cant update them properly. I think they would still be useful (not counter-productive) in this case, even though imprecise.

[trentxintong]

Address suggestions.

[trentxintong]

Hopefully remove some unrelated changes to some unrelated files.

[trentxintong]

I only want the head commit to be included in this patch.

[trentxintong]

I want to merge https://reviews.llvm.org/D28460, but I do not know how to do
so on Phabricator. So I merged it manually =).

[danielcdh]

Thanks a lot for the example, I'll look into it.

Dehao

[danielcdh]

Looks like this patch will make the "always call" worse:

Without this patch:

pushq   %rbx
movq    %rdi, %rbx
cmpl    $0, (%rbx)
jne     .LBB1_3

.LBB1_1: # =>This Inner Loop Header: Depth=1

movq    %rbx, %rdi
callq   call_me
cmpl    $0, (%rbx)
je      .LBB1_1

.LBB1_3:

popq    %rbx
retq

With this patch:

pushq   %rbx
movq    %rdi, %rbx
cmpl    $0, (%rbx)
je      .LBB1_1

.LBB1_3:

popq    %rbx
retq

.LBB1_1: # =>This Inner Loop Header: Depth=1

movq    %rbx, %rdi
callq   call_me
cmpl    $0, (%rbx)
jne     .LBB1_3
jmp     .LBB1_1

As the trip count of this loop is always 1, the first code will have no taken branches, while with this patch, it will have 2 taken branches.

[trentxintong]

Guard block branches to preheader instead of header.

[danielcdh]

Talked with Xin offline:

1. The comparison I made is (clean client v.s. entire patch), while Xin is comparing (D28460 v.s. entire patch)
2. We both agree that the patch works fine for cases when avg trip count >= 0.5
3. For cases when avg trip count <0.5 3.1 both have good code layout, the set probability for the guard branch are both reasonable 3.2 this patch will peel the loop by 1, while no_patch will not peel the loop, so the patch has code size overhead 3.3 the peeled loop may have better performance on the cold path when the loop trip count is unevenly distributed (but I started to doubt this now)
4. If 3.3 is true, then the problem becomes whether we want to trade code size for performance at cold path. Xin is going to run some benchmarks with and without the test to measure code size and performance impact of this patch and report back.

[trentxintong]

I am still in middle of getting a machine which i can do performance runs on. The machine I have is not very stable, i.e. specrun # fluctuates from run to run.

[davidxl]

lib/Transforms/Scalar/LoopRotation.cpp

84

name the parameters.

474

Remove the comment about OrigHeader BR. After Block merging, it will become the latch block branch instruction.

Is it better to call this after MergeBlockInfoPredecessor when loop L is a more consistent state?

501

exitting --> exiting

526

you need a test case to cover LoopBodyWeight > LoopExitWeight case --- not the one with known tripcount. For the constant trip count case, the guard BR gets eliminated.

565

Explain this condition? Perhaps a test case?

568

This is probably not quite correct.

For the case when LoopBodyWeight > LoopExitWeight, especially when the runtime trip count is large, the guard BR should have very biased against exiting. I think it is reasonable to use an arbitrary biased exit probability such as 1/100.

For cases when LoopBodyWeight and LoopExitWeight are close (e.g., trip count < 5), it is reasonable to keep GuardBR has the same exit branch probability as the new LatchBR. This applies to LoopBodyWeight < LoopExitWeight case as well.

test/Transforms/LoopRotate/loop-rotate-pgo.ll

10

Perhaps name it 'loop_with_known_trip_count'

17

This loop has statically known trip count. The profile data does not match it. Use a different meta data.

33

add comment the loop body is by-passed most of the time.

37

explicitly check br instruction as well so that two branch targets are listed. !prof is meaningless without looking at the branch

51

Same here -- also check branch instruction

[trentxintong]

I am very sorry I have not put up the #s for speccpu 2006. I am stuck in middle of a few things and I will put it up as soon as I have them. I will also address the comments too.

[trentxintong]

Address davidxl's comments.

I reworked how !prof metadata is computed after loop rotation.

There is one test case in peel-loop-pgo.ll. thats because I corrected how
estimated loop trip count is computed. I think its a good idea to fix loop rotation
metadada and getEstimatedTripCount together as getEstimatedTripCount uses
!prof metadata which is computed in a new way. However, the drawback is that
i need to modify a test case unrelated to loop rotation.

[trentxintong]

I ran C/C++ benchmarks in CPU2006 with the current state of the patch (baseline is without the metadata adjustment, negative percent means the benchmark runs slower or code size becomes smaller after the patch. It seems the the regressions in 429 and 444 are real. And we also have a code size reduction of -2.41% in 401. Overall, we have more performance regressions after we adjust the metadata this way.

Benchmark	Perf		CodeSize
400		-0.22%		0.00%
401		0.76%		-2.41%
403		-0.51%		0.07%
429		-2.09%		0.32%
445		0.64%		-0.08%
456		-0.29%		0.01%
458		0.00%		-0.04%
462		-0.15%		0.00%
464		0.16%		0.00%
471		-0.38%		-0.02%
473		0.00%		-0.21%
483		-0.40%		-0.04%
433		0.73%		0.03%
444		-2.15%		-0.26%
447		-0.17%		-0.06%
450		0.00%		-0.05%
453		0.38%		-0.01%
470		0.12%		0.00%
482		0.18%		0.14%

[davidxl]

lib/Transforms/Scalar/LoopRotation.cpp

542

What if the average trip count is > 20? In that case, 0.05 is larger than the latch br exit probability which is not right. The 'min' needs to be taken.

It is also better to use fixed point operation (with BranchProbablilty and BlockFrequency classes)

BranchProbability GuardBP(5, 100);
uint64_t NotTakenOnceWeight = (BlockFrequency(LoopExitWeight) * GuardBP).getFrequency();
uint64_t LoopPHWeight = LoopExitWeight - NotTakenOnceWeight;

GuardBR->setMetadata(MD_prof, ...);

'5' also needs to be a parameter. Do not use hard coded number.

574

same here, 0.95 may be smaller than the original Header BR's exit branch probability. The max should be taken.

The value 0.5 is not necessary -- why not just directly use original header BR's exit BP?

587

This can be done by computing the right notTakenOnceRatio above.

600

The weight computation code above should be refactored and shared across different cases. The difference only lies in the way NotTakenOnceRatio is computed.

[trentxintong]

Sorry for the really long hiatus. I am getting back to this one.

[trentxintong]

Rework the reworked metadata update in loop rotation. I still have some hardcoded numbers
i do not know whether to put them as options.

At least, we should try to agree on the mechanism itself and start collecting some numbers.

[trentxintong]

Add asserts and comments.

[trentxintong]

Incorrectly used max in place of min.

[davidxl]

lib/Transforms/Scalar/LoopRotation.cpp

512

maximum--> minimum

529

Avoid using floating point operation here. Just do:

if (LoopBodyWeight > 20 * LoopExitWeight) ..

Branch Weight Data is actually 32bit, so there is no risk of overflow here.

535

When ACT < 0.2, it seems simpler just do

NotTakenOnceProb = (ExitWeight - BodyWeight)/ExitWeight.

550

This adjustment will create weird results:

For ACT between 1 and 5, the computed NonTakenOnce Prob is kept which 50%. However, when ACT is between 0.5 and 1, the resulting not taken once Prob is smaller than 50% which contradicts to the trend -- the smaller ACT is, the more likely it is not executed once.

To fix this, do the following:

When ACT is between 0.5 and 5, use 50%
When ACT is less than 0.5, use (ExitWeight - BodyWeight)/ExitWeight

This makes the weight 'continuous and the special handling using 'min' can be removed.

lib/IR/Metadata.cpp

void Instruction::getAllMetadataOtherThanDebugLocImpl(
   assert(hasMetadataHashEntry() &&
          getContext().pImpl->InstructionMetadata.count(this) &&
          "Shouldn't have called this");
   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
   assert(!Info.empty() && "Shouldn't have called this");
   Info.getAll(Result);
 }
 
+
 bool Instruction::extractProfMetadata(uint64_t &TrueVal,
                                       uint64_t &FalseVal) const {
   assert(
       (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) &&
       "Looking for branch weights on something besides branch or select");
 
   auto *ProfileData = getMetadata(LLVMContext::MD_prof);
   if (!ProfileData || ProfileData->getNumOperands() != 3)

lib/Transforms/Scalar/LoopRotation.cpp

 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
LoopRotate(unsigned MaxHeaderSize, LoopInfo *LI,
              DominatorTree *DT, ScalarEvolution *SE)
       : MaxHeaderSize(MaxHeaderSize), LI(LI), TTI(TTI), AC(AC), DT(DT), SE(SE) {
   }
   bool processLoop(Loop *L);
 
 private:
   bool rotateLoop(Loop *L, bool SimplifiedLatch);
   bool simplifyLoopLatch(Loop *L);
+
+  /// Return true if we are able to find and update the branch_weight metadata
+  /// for the rotated loop latch and guard block, false otherwise.
+  bool updateLoopEstimatedBranchWeight(Loop *L, BranchInst *, BranchInst *);
 };
 } // end anonymous namespace
 
 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
 /// old header into the preheader.  If there were uses of the values produced by
 /// these instruction that were outside of the loop, we have to insert PHI nodes
 /// to merge the two values.  Do this now.
 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                             BasicBlock *OrigPreheader,
                                             ValueToValueMapTy &ValueMap) {
   // Remove PHI node entries that are no longer live.
   BasicBlock::iterator I, E = OrigHeader->end();
   for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
     PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
 
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // At this point, we've finished our major CFG changes.  As part of cloning
   // 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());
+  BranchInst *GBI = PHBI;
   assert(PHBI->isConditional() && "Should be clone of BI condbr!");
   if (!isa<ConstantInt>(PHBI->getCondition()) ||
       PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) !=
           NewHeader) {
     // The conditional branch can't be folded, handle the general case.
     // Update DominatorTree to reflect the CFG change we just made.  Then split
     // edges as necessary to preserve LoopSimplify form.
     if (DT) {
assert(SplitLatchEdge &&
            "Despite splitting all preds, failed to split latch exit?");
   } else {
     // We can fold the conditional branch in the preheader, this makes things
     // simpler. The first step is to remove the extra edge to the Exit block.
     Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
     BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
     NewBI->setDebugLoc(PHBI->getDebugLoc());
     PHBI->eraseFromParent();
+    GBI = NewBI;
 
     // With our CFG finalized, update DomTree if it is available.
     if (DT) {
       // Update OrigHeader to be dominated by the new header block.
       DT->changeImmediateDominator(NewHeader, OrigPreheader);
       DT->changeImmediateDominator(OrigHeader, OrigLatch);
 
       // Brute force incremental dominator tree update. Call
if (DT) {
         }
 
         // If the dominator changed, this may have an effect on other
         // predecessors, continue until we reach a fixpoint.
       } while (Changed);
     }
   }
 
+  // Adjust the loop branch metadata, and in case we do not know how to
+  // update them properly, simply drop them. No data is better than imprecise
+  // data.
+  if (!updateLoopEstimatedBranchWeight(L, GBI, BI /* OrigHeader BR */)) {
+    BI->setMetadata(LLVMContext::MD_prof, nullptr);
+    GBI->setMetadata(LLVMContext::MD_prof, nullptr);
+  }
+
   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
 
   // Now that the CFG and DomTree are in a consistent state again, try to merge
   // the OrigHeader block into OrigLatch.  This will succeed if they are
   // connected by an unconditional branch.  This is just a cleanup so the
   // emitted code isn't too gross in this common case.
   MergeBlockIntoPredecessor(OrigHeader, DT, LI);
 
   DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 
   ++NumRotated;
   return true;
 }
 
+/// We have now rotated the loop, update branch weight prof metadata in case
+/// we have it.
+bool LoopRotate::updateLoopEstimatedBranchWeight(Loop *L,
+                                                 BranchInst *GuardBR,
+                                                 BranchInst *LatchBR) {
+  // If loop has multiple exitting block, we need to look through each one
+  // of them and reason about their profile metadata to compute the rotated
+  // loop metadata correctly. e.g. if we have an early exit in the loop,
+  // we will not be able to tell whether the latch block will ever be
+  // reached after rotation, i.e. early exit could have been taken.
+  // we bail for now.
+  //
+  // FIXME: Handle loops with early exits.
+  if (!L->getExitingBlock())
+    return false;
+
+  // Update latch branch metadata. After the loop is rotated, the # of times 
+  // the loop body is executed remain the same and the # of times the exit
+  // block is executed remain the same as well. We use these information to
+  // compute the weight for the rest of the branches.
+  uint64_t LoopBodyWeight, LoopExitWeight;
+  uint64_t BackedgeWeight = 1, NotTakeOnceWeight = 1;
+  if (LatchBR->extractProfMetadata(LoopBodyWeight, LoopExitWeight)) {
+    // Make sure the loop body and exit weight gets its correct value.
+    bool LoopBodyOnTrue = LatchBR->getSuccessor(0) == L->getHeader();
+    if (!LoopBodyOnTrue)
+      std::swap(LoopBodyWeight, LoopExitWeight);
+
+    MDBuilder MDB(LatchBR->getFunction()->getContext());
+    if (LoopBodyWeight >= LoopExitWeight) {
+      // In case profiled LoopBodyWeight >= LoopExitWeight, we assume the
+      // branch-to-exit in the guard branch is never taken, as on average the
+      // loop body is executed at least once before the exit is taken.
+      //
+      // Backedge weight is simply the difference of # of times the loop
+      // body is executed and the # of times the loop body is entered through
+      // a forwarding branch, same as LoopExitWeight here. We also make sure
+      // backedge is at least 1, i.e. BackedgeWeight is initialized to 1.
+      if (LoopBodyWeight != LoopExitWeight)
+        BackedgeWeight = LoopBodyWeight - LoopExitWeight;
+    } else {
+      // In case of profiled LoopBodyWeight < LoopExitWeight, we know that
+      // when the unrotated loop header is hit, the loop body is not executed
+      // at all some of the time. And for times which the loop body is executed
+      // its probably just a small # of iterations, assuming the loop executes
+      // similar # of iterations every time its hit. In this case, we assume
+      // backedge weight is 1.
+      uint64_t OrigLoopExitWeight = LoopExitWeight;
+      // The # of times the LoopExitWeight is taken is the same as the # of
+      // times the loop body is executed, as we basically ignore backedge in
+      // this case.
+      LoopExitWeight = LoopBodyWeight;
+      NotTakeOnceWeight = OrigLoopExitWeight - LoopExitWeight;
+    }
+
+    // Sanity check ... no branch weight should be smaller than 1.
+    assert(BackedgeWeight > 0 && LoopExitWeight > 0 &&
+           NotTakeOnceWeight > 0 && "Invalid branch weight detected!");
+
+    // Update the latch branch and guard branch metadata.
+    LatchBR->setMetadata(LLVMContext::MD_prof, LoopBodyOnTrue ? 
+                         MDB.createBranchWeights(BackedgeWeight,
+                                                 LoopExitWeight) :
+                         MDB.createBranchWeights(LoopExitWeight,
+                                                 BackedgeWeight));
+    if (GuardBR->isUnconditional()) {
+      GuardBR->setMetadata(LLVMContext::MD_prof, nullptr);
+    } else {
+      GuardBR->setMetadata(LLVMContext::MD_prof,
+                           GuardBR->getSuccessor(0) == L->getHeader() ?
+                           MDB.createBranchWeights(LoopExitWeight,
+                                                   NotTakeOnceWeight) :
+                           MDB.createBranchWeights(NotTakeOnceWeight,
+                                                   LoopExitWeight));
+    }
+    return true;
+  }
+
+  // We do not know how to update the branches' metadata.
+  return false;
+}
+
 /// Determine whether the instructions in this range may be safely and cheaply
 /// speculated. This is not an important enough situation to develop complex
 /// heuristics. We handle a single arithmetic instruction along with any type
 /// conversions.
 static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
                                   BasicBlock::iterator End, Loop *L) {
   bool seenIncrement = false;
   bool MultiExitLoop = false;
 
   if (!L->getExitingBlock())
     MultiExitLoop = true;
 
   for (BasicBlock::iterator I = Begin; I != End; ++I) {
 
     if (!isSafeToSpeculativelyExecute(&*I))
       return false;
 
     if (isa<DbgInfoIntrinsic>(I))
       continue;
 
     switch (I->getOpcode()) {
     default:
       return false;
     case Instruction::GetElementPtr:
       // GEPs are cheap if all indices are constant.
       if (!cast<GEPOperator>(I)->hasAllConstantIndices())
         return false;
       // fall-thru to increment case
       LLVM_FALLTHROUGH;
     case Instruction::Add:
     case Instruction::Sub:

test/Transforms/LoopRotate/loop-rotate-pgo.ll

+; RUN: opt -S -loop-rotate < %s | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.12.0"
+
+; This loop has a big trip count as the for.body is executed
+; 35 times and the exit is executed 7 times. In such case we
+; can generate a non-trivial prof metadata for the latch after
+; rotation.
+define i32 @loops_with_big_tripcount() {
+entry:
+   br label %for.cond
+
+for.cond:
+   %index = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+   %cmp = icmp slt i32 %index, 1024
+   br i1 %cmp, label %for.body, label %for.end, !prof !0
+
+for.body:
+   br label %for.inc
+
+; CHECK: for.inc
+; CHECK: icmp slt i32 %inc, 1024
+; CHECK-NEXT: !prof !0
+for.inc:
+   %inc = add nsw i32 %index, 1
+   br label %for.cond
+
+for.end:
+   ret i32 0
+}
+
+; This loop has a small trip count, most of the time it simply branches
+; to for.end. 
+define i32 @loops_with_small_tripcount(i32 %a) {
+; CHECK: icmp slt i32 15, %a
+; CHECK-NEXT: !prof !0 
+entry:
+   br label %for.cond
+
+for.cond:
+   %index = phi i32 [ 15, %entry ], [ %inc, %for.inc ]
+   %cmp = icmp slt i32 %index, %a 
+   br i1 %cmp, label %for.end, label %for.body, !prof !0
+
+for.body:
+   br label %for.inc
+
+; CHECK: for.inc
+; CHECK: icmp slt i32 %inc, %a
+; CHECK-NEXT: !prof !1
+for.inc:
+   %inc = add nsw i32 %index, 1
+   br label %for.cond
+
+for.end:
+   ret i32 0
+}
+
+; CHECK: !0 = !{!"branch_weights", i32 28, i32 7}
+; CHECK: !1 = !{!"branch_weights", i32 7, i32 1}
+!0 = !{!"branch_weights", i32 35, i32 7}