Make sure total loop body weight is preserved in loop peeling

[trentxintong]

Summary

Regardless how the loop body weight is distributed, we should preserve
total loop body weight. i.e. we should have same weight reaching the body of the loop
or its duplicates in peeled and unpeeled case.

[trentxintong]

Rework BE count for the remainder loop a bit.

[mkuper]

Argh, you're right, I got the accounting wrong.
LGTM. thanks for fixing this.

[davidxl]

lib/Transforms/Utils/LoopUnrollPeel.cpp

338

Might be better to name it

CurHeaderWeight or just HeaderWeight

351

This comment is not accurate. Better

"Subtract the exit weight from the current header weight -- the exit weight is exactly ..."

393

remaining loop body weight --> current header weight

loop body entry count --> current loop exit weight

[trentxintong]

Address davidxl suggestions.

[davidxl]

lgtm

lib/Transforms/Utils/LoopUnrollPeel.cpp

bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
 
   // If we have branch weight information, we'll want to update it for the
   // newly created branches.
   BranchInst *LatchBR =
       cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
   unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
 
   uint64_t TrueWeight, FalseWeight;
-  uint64_t ExitWeight = 0, BackEdgeWeight = 0;
+  uint64_t ExitWeight = 0, LoopBodyWeight = 0;
   if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
     ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
-    BackEdgeWeight = HeaderIdx ? FalseWeight : TrueWeight;
+    // The # of times the loop body executes is the sum of the exit block
+    // weight and the # of times the backedges are taken.
+    LoopBodyWeight = TrueWeight + FalseWeight;
   }
 
   // For each peeled-off iteration, make a copy of the loop.
   for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
     SmallVector<BasicBlock *, 8> NewBlocks;
     ValueToValueMapTy VMap;
 
     // The exit weight of the previous iteration is the header entry weight
     // of the current iteration. So this is exactly how many dynamic iterations
     // the current peeled-off static iteration uses up.
     // FIXME: due to the way the distribution is constructed, we need a
     // guard here to make sure we don't end up with non-positive weights.
-    if (ExitWeight < BackEdgeWeight)
-      BackEdgeWeight -= ExitWeight;
+    if (ExitWeight < LoopBodyWeight)
+      LoopBodyWeight -= ExitWeight;
     else
-      BackEdgeWeight = 1;
+      LoopBodyWeight = 1;
 
     cloneLoopBlocks(L, Iter, InsertTop, InsertBot, Exit,
                     NewBlocks, LoopBlocks, VMap, LVMap, LI);
     updateBranchWeights(InsertBot, cast<BranchInst>(VMap[LatchBR]), Iter,
                         PeelCount, ExitWeight);
 
     InsertTop = InsertBot;
     InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
     if (LatchInst && L->contains(LatchInst))
       NewVal = LVMap[LatchInst];
 
     PHI->setIncomingValue(PHI->getBasicBlockIndex(NewPreHeader), NewVal);
   }
 
   // Adjust the branch weights on the loop exit.
   if (ExitWeight) {
+    // The backedge count is the difference of remaining loop body weight and
+    // loop body entry count. If the remaining loop body weight is smaller than
+    // this loop body entry weight, we mark the loop backedge weight as 1. We
+    // also re-adjust ExitWeight so that the sum of the exit counts is the same
+    // as the entry count.
+    uint64_t BackEdgeWeight = 0;
+    if (ExitWeight < LoopBodyWeight)
+      BackEdgeWeight = LoopBodyWeight - ExitWeight;
+    else {
+      BackEdgeWeight = 1;
+      ExitWeight -= 1;
+    }
     MDBuilder MDB(LatchBR->getContext());
     MDNode *WeightNode =
         HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
                   : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
     LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
   }
 
   // If the loop is nested, we changed the parent loop, update SE.
   if (Loop *ParentLoop = L->getParentLoop())
     SE->forgetLoop(ParentLoop);
 
   NumPeeled++;
 
   return true;
 }

test/Transforms/LoopUnroll/peel-loop-pgo.ll

 }
 
 !0 = !{!"function_entry_count", i64 1}
 !1 = !{!"branch_weights", i32 3001, i32 1001}
 
 ;CHECK: !1 = !{!"branch_weights", i32 900, i32 101}
 ;CHECK: !2 = !{!"branch_weights", i32 540, i32 360}
 ;CHECK: !3 = !{!"branch_weights", i32 162, i32 378}
-;CHECK: !4 = !{!"branch_weights", i32 560, i32 162}
+;CHECK: !4 = !{!"branch_weights", i32 1399, i32 162}