Let edge weight be always greater than zero in both BPI and MBPI.

[congh]

Summary

Currently BPI requires that edge weights must be greater than 0, but MBPI doesn't have this requirement. In MBPI, when an edge weight is zero, it is treated as there is no weight info for that edge. At runtime, such a zero edge weight will be turned into a DEFAULT edge weight 16. This may lead to incorrect edge weights ratio when we originally have 0 and 1 as edge weights from the same block and later get 16 and 1. Zero weights can either mean no info or obtained from BPI or calculated by users, making it ambiguous. When we have all out-edges with zero weights from the same block, it is awkward to compute edge probabilities. Though this is worked-around by using default edge weights. However, if we require edge weights in MBPI also should be greater than zero, we won't have the issues above.

In addition, although BPI requires edge weights to be greater than zero, it doesn't guarantee this when weights are read from metadata. So we need to normalize edge weights when we read zero weight from metadata. For example, if we have 0 and 1 edge weights from the same block (assume it only has two out-edges), we can normalize them into 1 and UINT32_MAX - 1.

This patch contains the following changes:

1. Normalize edge weights in BPI to guarantee that they are greater than 0.
2. In MBPI don't turn zero edge weights into default weights as we should not have zero weights anymore.
3. (To discuss) Weight list can be empty previously when it is not used at all. I found it difficult to make weight list and successor list always synchronized so this patch will always update weight list whether it is used or not. Is this acceptable?
4. Adjust use and test cases accordingly.

[davidxl]

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

include/llvm/CodeGen/MachineBasicBlock.h

386 ↗

(On Diff #31689)

Is 16 a good default value to indicate missing information?

The current underlying (without this patch) assumption in MBPI is that if the weight list is empty, 0 weight represents 'unknown' weight -- otherwise it will be treated as a real zero value weight. This assumption is of course very weak and can break down at any time.

All these needs to be considered in the new design when weight is eliminated from the profiling related interfaces -- i.e., reserve a special value for unknown 'probability'.

lib/Analysis/BranchProbabilityInfo.cpp

210

Which clients produce zero weights ? It seems that Clang FE does not do that. See scaleBranchWeight in tools/clang/lib/CodeGen/CodeGenPGO.cpp

[congh]

In D11915#221748, @davidxl wrote:

Since we plan to change [M]MPI interfaces to hide weight which is internal, can we minimize this patch? My understanding is that minimal change is needed to make the weight normalization patch work well with zero weights.

Yes, I can reduce the size of this patch so that we only need to make sure there is no zero weight from BPI. This should make edge weights normalization work.

include/llvm/CodeGen/MachineBasicBlock.h

386 ↗

(On Diff #31689)

Both BPI and MBPI use 16 as default weight and that is why I also use 16 here. I agree with you. This doesn't matter now and we need to find out how to assign a default probability to a new successor if it is indicated explicitly.

lib/Analysis/BranchProbabilityInfo.cpp

210

It happens in test cases where the branch weight is explicitly assigned as zero.

[congh]

Reduce the patch by only eliminating zero weights in BPI.

[davidxl]

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

test/Analysis/BlockFrequencyInfo/bad_input.ll

12

Do we know what the original intention of the test case is?

[congh]

In D11915#221943, @davidxl wrote:

I thought we need to fix MBPI to handle bad interactions of with weight normalization and zero weight. Why do we need to fix BPI?

Zero weights have two meanings in MBPI: 1. It is a real zero weight that is from BPI. 2. It is an unknown weight. If we require that all weights from BPI cannot be zero, then it now only has the second meaning. The test failures on the weight normalization patch can now be fixed (note that those tests contains prof_data with 0 edge weights, which are eliminated in BPI now).

test/Analysis/BlockFrequencyInfo/bad_input.ll

12

This is testing if we have MD with 0, 3 as branch weights, in BFI we will get 1, 4 instead of 0, 3 as branch weights. In this patch we have eliminated zero weights so we should get 1 and a very large integer (around UINT32_MAX) as edge weights.

[davidxl]

test/Analysis/BlockFrequencyInfo/bad_input.ll

12

What existing code in BPI/BFI changes 0,3 into 1,4?

[congh]

test/Analysis/BlockFrequencyInfo/bad_input.ll

12

It is done in lib/Analysis/BlockFrequencyInfoImpl.cpp:265. Actually this turns the edge weights from 0,3 into 1, 3, and then the frequency ratio of the loop body over the exit now becomes 1:4.

[davidxl]

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.

---

Current situation:

1. there is no client (other than opt) producing zero weight for BPI
2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16

for MBPI

3. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
4. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.
5. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
6. the weight list and successor list can be out of sync.

[congh]

In D11915#222110, @davidxl wrote:

Ok -- it is a very messy situation that need lots of cleanup (summarized below). For now, since the only producer of zero weight for BPI is from 'opt' by reading developer's hand writing .ll file, I suggest simply set zero weight to 1 in calcMetaDataWeights to match BlockFrequencyInfoImpl's behavior.

Assume the user uses weights 0 and 1 to represent that one edge is very very cold and another one is very very hot, then this modification makes them to 1 and 1, which has the totally different meaning.

---

Current situation:

1. there is no client (other than opt) producing zero weight for BPI
2. BPI can have missing weights (empty map entry) -- in which case, the edge weight returned is DEFAULT_WEIGHT= 16

for MBPI

I think you mean MBB&MBPI as 3) & 6) below are for MBB.

3. the default weight in the setter interface is '0' -- which can not be differentiated with real zero weight
4. when Weight list for a BB is empty, the getter interface returns 16 as the default weight.

Here MBB returns 0 but MBPI turns it into 16.

5. the getter interface also unconditionally change 0 weight into DEFAULT_WEIGHT == 16
6. the weight list and successor list can be out of sync.

lib/Analysis/BranchProbabilityInfo.cpp

 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "branch-prob"
 
 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
                       "Branch Probability Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
if (!Weight)
       return false;
     assert(Weight->getValue().getActiveBits() <= 32 &&
            "Too many bits for uint32_t");
     Weights.push_back(Weight->getZExtValue());
     WeightSum += Weights.back();
   }
   assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
 
+  // Weight cannot be zero. Here we find out all zero weights read from MD, and
+  // replace them by 1. If any other weight is not zero, we need to normalize
+  // other weights so that the sum of all weights are maximized but less than
+  // UINT32_MAX.
+  auto ZeroWeightNum = std::count(Weights.begin(), Weights.end(), 0u);
+  if (ZeroWeightNum > 0) {
+    // If all weights are zeros, replace them by 1.
+    if (ZeroWeightNum == Weights.size())
+      std::fill(Weights.begin(), Weights.end(), 1u);
+    else {
+      uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / WeightSum;
+      if (ScalingFactor > 1)
+        for (auto &W : Weights)
+          W *= ScalingFactor;
+      std::replace(Weights.begin(), Weights.end(), 0u, 1u);
+    }
+    WeightSum += ZeroWeightNum;
+  }
+
   // If the sum of weights does not fit in 32 bits, scale every weight down
   // accordingly.
   uint64_t ScalingFactor =
       (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
 
   WeightSum = 0;
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
-    uint32_t W = Weights[i] / ScalingFactor;
+    // Make sure the weight is greater than 0.
+    uint32_t W = std::max<uint32_t>(Weights[i] / ScalingFactor, 1);
     WeightSum += W;
     setEdgeWeight(BB, i, W);
   }
   assert(WeightSum <= UINT32_MAX &&
          "Expected weights to scale down to 32 bits");
 
   return true;
 }

test/Analysis/BlockFrequencyInfo/bad_input.ll

 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
 
 declare void @g(i32 %x)
 
 ; CHECK-LABEL: Printing analysis {{.*}} for function 'branch_weight_0':
 ; CHECK-NEXT: block-frequency-info: branch_weight_0
 define void @branch_weight_0(i32 %a) {
 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %for.body
 
-; Check that we get 1,4 instead of 0,3.
-; CHECK-NEXT: for.body: float = 4.0,
+; Check that we get 1, ~UINT32_MAX instead of 0, 3.
+; CHECK-NEXT: for.body: float = 4294967291.0,
 for.body:
   %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   call void @g(i32 %i)
   %inc = add i32 %i, 1
   %cmp = icmp ugt i32 %inc, %a
   br i1 %cmp, label %for.end, label %for.body, !prof !0
 
 ; CHECK-NEXT: for.end: float = 1.0, int = [[ENTRY]]

test/Transforms/SampleProfile/branch.ll

 define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
 ; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
 
 entry:
   tail call void @llvm.dbg.value(metadata i32 %argc, i64 0, metadata !13, metadata !DIExpression()), !dbg !27
   tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
   %cmp = icmp slt i32 %argc, 2, !dbg !28
   br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 0 / 1 = 0%
-; CHECK: edge entry -> if.end probability is 1 / 1 = 100%
+; CHECK: edge entry -> return probability is 1 / 4294967295 = 2.32831e-08%
+; CHECK: edge entry -> if.end probability is 4294967294 / 4294967295 = 100% [HOT edge]
 
 if.end:                                           ; preds = %entry
   %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
   %0 = load i8*, i8** %arrayidx, align 8, !dbg !30, !tbaa !31
   %call = tail call i32 @atoi(i8* %0) #4, !dbg !30
   tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
   %cmp1 = icmp sgt i32 %call, 100, !dbg !35
   br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 0 / 1 = 0%
-; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100%
+; CHECK: edge if.end -> for.body probability is 1 / 4294967295 = 2.32831e-08%
+; CHECK: edge if.end -> if.end6 probability is 4294967294 / 4294967295 = 100% [HOT edge]
 
 for.body:                                         ; preds = %if.end, %for.body
   %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
   %s.015 = phi double [ %sub, %for.body ], [ 0x40370ABE6A337A81, %if.end ]
   %add = fadd double %s.015, 3.049000e+00, !dbg !36
   %conv = sitofp i32 %u.016 to double, !dbg !36
   %add4 = fadd double %add, %conv, !dbg !36
   tail call void @llvm.dbg.value(metadata double %add4, i64 0, metadata !18, metadata !DIExpression()), !dbg !36
   %div = fdiv double 3.940000e+00, %s.015, !dbg !37
   %mul = fmul double %div, 3.200000e-01, !dbg !37
   %add5 = fadd double %add4, %mul, !dbg !37
   %sub = fsub double %add4, %add5, !dbg !37
   tail call void @llvm.dbg.value(metadata double %sub, i64 0, metadata !18, metadata !DIExpression()), !dbg !37
   %inc = add nsw i32 %u.016, 1, !dbg !38
   tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
   %exitcond = icmp eq i32 %inc, %call, !dbg !38
   br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0%
-; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge]
+; CHECK: edge for.body -> if.end6 probability is 1 / 4294960905 = 2.32831e-08%
+; CHECK: edge for.body -> for.body probability is 4294960904 / 4294960905 = 100% [HOT edge]
 
 if.end6:                                          ; preds = %for.body, %if.end
   %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
   %call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
   br label %return, !dbg !40
 ; CHECK: edge if.end6 -> return probability is 16 / 16 = 100% [HOT edge]
 
 return:                                           ; preds = %entry, %if.end6

test/Transforms/SampleProfile/calls.ll

entry:
   br label %while.cond, !dbg !13
 
 while.cond:                                       ; preds = %if.end, %entry
   %0 = load i32, i32* %i, align 4, !dbg !14
   %inc = add nsw i32 %0, 1, !dbg !14
   store i32 %inc, i32* %i, align 4, !dbg !14
   %cmp = icmp slt i32 %0, 400000000, !dbg !14
   br i1 %cmp, label %while.body, label %while.end, !dbg !14
-; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0%
+; CHECK: edge while.cond -> while.body probability is 4294966572 / 4294966573 = 100% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 1 / 4294966573 = 2.32831e-08%
 
 while.body:                                       ; preds = %while.cond
   %1 = load i32, i32* %i, align 4, !dbg !16
   %cmp1 = icmp ne i32 %1, 100, !dbg !16
   br i1 %cmp1, label %if.then, label %if.else, !dbg !16
 ; Without discriminator information, the profiler used to think that
 ; both branches out of while.body had the same weight. In reality,
 ; the edge while.body->if.then is taken most of the time.
 ;
-; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge]
-; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0%
+; CHECK: edge while.body -> if.then probability is 4294966632 / 4294966633 = 100% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 1 / 4294966633 = 2.32831e-08%
 
 
 if.then:                                          ; preds = %while.body
   %2 = load i32, i32* %i, align 4, !dbg !18
   %3 = load i32, i32* %s, align 4, !dbg !18
   %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
   store i32 %call, i32* %s, align 4, !dbg !18
   br label %if.end, !dbg !18

test/Transforms/SampleProfile/propagate.ll

if.else:                                          ; preds = %entry
   store i64 0, i64* %i, align 8, !dbg !15
   br label %for.cond, !dbg !15
 
 for.cond:                                         ; preds = %for.inc16, %if.else
   %4 = load i64, i64* %i, align 8, !dbg !15
   %5 = load i64, i64* %N.addr, align 8, !dbg !15
   %cmp1 = icmp slt i64 %4, %5, !dbg !15
   br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0%
+; CHECK: edge for.cond -> for.body probability is 4294967290 / 4294967291 = 100% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 1 / 4294967291 = 2.32831e-08%
 
 for.body:                                         ; preds = %for.cond
   %6 = load i64, i64* %i, align 8, !dbg !18
   %7 = load i64, i64* %N.addr, align 8, !dbg !18
   %div = sdiv i64 %7, 3, !dbg !18
   %cmp2 = icmp sgt i64 %6, %div, !dbg !18
   br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
 ; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
if.else7:                                         ; preds = %if.end
   br label %for.cond8, !dbg !28
 
 for.cond8:                                        ; preds = %for.inc, %if.else7
   %13 = load i32, i32* %j, align 4, !dbg !28
   %conv9 = zext i32 %13 to i64, !dbg !28
   %14 = load i64, i64* %i, align 8, !dbg !28
   %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
   br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0%
+; CHECK: edge if.then6 -> if.end15 probability is 16 / 16 = 100% [HOT edge]
+; CHECK: edge for.cond8 -> for.end probability is 1 / 4294954189 = 2.32831e-08%
 
 for.body11:                                       ; preds = %for.cond8
   %15 = load i32, i32* %j, align 4, !dbg !31
   %16 = load i32, i32* %x.addr, align 4, !dbg !31
   %add12 = add i32 %16, %15, !dbg !31
   store i32 %add12, i32* %x.addr, align 4, !dbg !31
   %17 = load i32, i32* %y.addr, align 4, !dbg !33
   %sub13 = sub nsw i32 %17, 3, !dbg !33