[BFI] Use rounding while computing profile counts.

[eraman]

Summary

Profile count of a block is computed by multiplying its block frequency
by entry count and dividing the result by entry block frequency. Do
rounded division in the last step and update test cases appropriately.

[davidxl]

lgtm

lib/Analysis/BlockFrequencyInfoImpl.cpp

BlockFrequencyInfoImplBase::getProfileCountFromFreq(const Function &F,
   auto EntryCount = F.getEntryCount();
   if (!EntryCount)
     return None;
   // Use 128 bit APInt to do the arithmetic to avoid overflow.
   APInt BlockCount(128, EntryCount.getCount());
   APInt BlockFreq(128, Freq);
   APInt EntryFreq(128, getEntryFreq());
   BlockCount *= BlockFreq;
-  BlockCount = BlockCount.udiv(EntryFreq);
+  // Rounded division of BlockCount by EntryFreq. Since EntryFreq is unsigned
+  // lshr by 1 gives EntryFreq/2.
+  BlockCount = (BlockCount + EntryFreq.lshr(1)).udiv(EntryFreq);
   return BlockCount.getLimitedValue();
 }
 
 bool
 BlockFrequencyInfoImplBase::isIrrLoopHeader(const BlockNode &Node) {
   if (!Node.isValid())
     return false;
   return IsIrrLoopHeader.test(Node.Index);

test/Analysis/BlockFrequencyInfo/irreducible_pgo.ll

 !40 = !{!"loop_header_weight", i64 100}
 !41 = !{!"branch_weights", i32 0, i32 1, i32 300, i32 99}
 !42 = !{!"loop_header_weight", i64 400}
 
 ; CHECK-LABEL: Printing analysis {{.*}} for function '_Z11irreduciblePh':
 ; CHECK-NEXT: block-frequency-info: _Z11irreduciblePh
 ; CHECK-NEXT: - entry: {{.*}} count = 1
 ; CHECK-NEXT: - for.cond1: {{.*}} count = 1
-; CHECK-NEXT: - dispatch_op: {{.*}} count = 201
-; CHECK-NEXT: - dispatch_op.sw.bb6_crit_edge: {{.*}} count = 200
-; CHECK-NEXT: - sw.bb: {{.*}} count = 0
-; CHECK-NEXT: - TARGET_1: {{.*}} count = 299
-; CHECK-NEXT: - sw.bb6: {{.*}} count = 500, irr_loop_header_weight = 501
-; CHECK-NEXT: - if.then: {{.*}} count = 299
-; CHECK-NEXT: - TARGET_2: {{.*}} count = 98
-; CHECK-NEXT: - sw.bb15: {{.*}} count = 99, irr_loop_header_weight = 100
-; CHECK-NEXT: - if.then18: {{.*}} count = 99
+; CHECK-NEXT: - dispatch_op: {{.*}} count = 202
+; CHECK-NEXT: - dispatch_op.sw.bb6_crit_edge: {{.*}} count = 201
+; CHECK-NEXT: - sw.bb: {{.*}} count = 1
+; CHECK-NEXT: - TARGET_1: {{.*}} count = 300
+; CHECK-NEXT: - sw.bb6: {{.*}} count = 501, irr_loop_header_weight = 501
+; CHECK-NEXT: - if.then: {{.*}} count = 300
+; CHECK-NEXT: - TARGET_2: {{.*}} count = 99
+; CHECK-NEXT: - sw.bb15: {{.*}} count = 100, irr_loop_header_weight = 100
+; CHECK-NEXT: - if.then18: {{.*}} count = 100
 ; CHECK-NEXT: - unknown_op: {{.*}} count = 0
 ; CHECK-NEXT: - sw.default: {{.*}} count = 0
 ; CHECK-NEXT: - exit: {{.*}} count = 1
-; CHECK-NEXT: - indirectgoto: {{.*}} count = 399, irr_loop_header_weight = 400
+; CHECK-NEXT: - indirectgoto: {{.*}} count = 400, irr_loop_header_weight = 400
 
 ; Missing some irr loop annotations.
 ; Function Attrs: noinline norecurse nounwind uwtable
 define i32 @_Z11irreduciblePh2(i8* nocapture readonly %p) !prof !27 {
 entry:
   %0 = load i32, i32* @tracing, align 4
   %1 = trunc i32 %0 to i8
   %tobool = icmp eq i32 %0, 0

test/Instrumentation/cgprofile.ll

 ; CHECK: ![[cgprof]] = !{i32 5, !"CG Profile", ![[prof:[0-9]+]]}
 ; CHECK: ![[prof]] = !{![[e0:[0-9]+]], ![[e1:[0-9]+]], ![[e2:[0-9]+]], ![[e3:[0-9]+]], ![[e4:[0-9]+]], ![[e5:[0-9]+]], ![[e6:[0-9]+]]}
 ; CHECK: ![[e0]] = !{void ()* @a, void ()* @b, i64 32}
 ; CHECK: ![[e1]] = !{void (i1)* @freq, i32 ()* @func4, i64 1030}
 ; CHECK: ![[e2]] = !{void (i1)* @freq, i32 ()* @func2, i64 410}
 ; CHECK: ![[e3]] = !{void (i1)* @freq, i32 ()* @func3, i64 150}
 ; CHECK: ![[e4]] = !{void (i1)* @freq, i32 ()* @func1, i64 10}
 ; CHECK: ![[e5]] = !{void (i1)* @freq, void ()* @a, i64 11}
-; CHECK: ![[e6]] = !{void (i1)* @freq, void ()* @b, i64 20}
+; CHECK: ![[e6]] = !{void (i1)* @freq, void ()* @b, i64 21}

unittests/Analysis/BlockFrequencyInfoTest.cpp

TEST_F(BlockFrequencyInfoTest, Basic) {
   uint64_t BB3Freq = BFI.getBlockFreq(BB3).getFrequency();
 
   EXPECT_EQ(BB0Freq, BB3Freq);
   EXPECT_EQ(BB0Freq, BB1Freq + BB2Freq);
   EXPECT_EQ(BB0Freq, BB3Freq);
 
   EXPECT_EQ(BFI.getBlockProfileCount(&BB0).getValue(), UINT64_C(100));
   EXPECT_EQ(BFI.getBlockProfileCount(BB3).getValue(), UINT64_C(100));
-  EXPECT_EQ(BFI.getBlockProfileCount(BB1).getValue(), 100 * BB1Freq / BB0Freq);
-  EXPECT_EQ(BFI.getBlockProfileCount(BB2).getValue(), 100 * BB2Freq / BB0Freq);
+  EXPECT_EQ(BFI.getBlockProfileCount(BB1).getValue(),
+            (100 * BB1Freq + BB0Freq / 2) / BB0Freq);
+  EXPECT_EQ(BFI.getBlockProfileCount(BB2).getValue(),
+            (100 * BB2Freq + BB0Freq / 2) / BB0Freq);
 
   // Scale the frequencies of BB0, BB1 and BB2 by a factor of two.
   SmallPtrSet<BasicBlock *, 4> BlocksToScale({BB1, BB2});
   BFI.setBlockFreqAndScale(&BB0, BB0Freq * 2, BlocksToScale);
   EXPECT_EQ(BFI.getBlockFreq(&BB0).getFrequency(), 2 * BB0Freq);
   EXPECT_EQ(BFI.getBlockFreq(BB1).getFrequency(), 2 * BB1Freq);
   EXPECT_EQ(BFI.getBlockFreq(BB2).getFrequency(), 2 * BB2Freq);
   EXPECT_EQ(BFI.getBlockFreq(BB3).getFrequency(), BB3Freq);
 }
 
 } // end anonymous namespace
 } // end namespace llvm