[test] Make bt_order_by_weight in switch.ll more robust

[aeubanks]

Summary

Branch weights are not represented internally linearly with the value in
the IR. In its current state the test happened to pass, but the branch
weights for 0,3,6 and 2,5,8,9 were not actually equal.

$ opt -passes='print<branch-prob>'

shows that the sum of the branch probabilities going to bb0 and bb2 were not the same.

Printing analysis results of BPI for function 'bt_order_by_weight':
---- Branch Probabilities ----
  edge entry -> bb0 probability is 0x00000003 / 0x80000000 = 0.00%
  edge entry -> bb2 probability is 0x00000004 / 0x80000000 = 0.00%

with this change:

Printing analysis results of BPI for function 'bt_order_by_weight':
---- Branch Probabilities ----
  edge entry -> bb0 probability is 0x00000004 / 0x80000000 = 0.00%
  edge entry -> bb2 probability is 0x00000004 / 0x80000000 = 0.00%

[hans]

Thanks for fixing, but can you please elaborate a little since I'm not familiar with the details here:

Branch weights are not represented internally linearly with the value in the IR.

That's surprising. How are they represented then? In the IR, the weights for cases 0,3,6 and 2,5,8,9 both add up to 12. Did that not reflect how the weights added up internally.

Also, going over uint32_t messes with the values, and this test shouldn't be testing for that.

Is something else handling that, then? I think there was a bug here, which is exactly why the test is checking that things still work when this happens.

[aeubanks]

restore large branch weights
update comments

[aeubanks]

In D90273#2358349, @hans wrote:

Thanks for fixing, but can you please elaborate a little since I'm not familiar with the details here:

Branch weights are not represented internally linearly with the value in the IR.

That's surprising. How are they represented then? In the IR, the weights for cases 0,3,6 and 2,5,8,9 both add up to 12. Did that not reflect how the weights added up internally.

Sometimes weights have +1 added to them for practical/theoretical reasons. They are also scaled if the total branch weights overflow uint32.
But having 0 for most of the branch weights should be more robust.

Also, going over uint32_t messes with the values, and this test shouldn't be testing for that.

Is something else handling that, then? I think there was a bug here, which is exactly why the test is checking that things still work when this happens.

Restored the large branch weights.

[hans]

lgtm thanks!

llvm/test/CodeGen/X86/switch.ll

switch i32 %x, label %return [
     i32 9, label %bb2
   ], !prof !1
 bb0: tail call void @g(i32 0) br label %return
 bb1: tail call void @g(i32 1) br label %return
 bb2: tail call void @g(i32 2) br label %return
 return: ret void
 
 ; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
-; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 12,
-; but the latter set has more cases, so should be tested for earlier.
-; The bit test on 0,3,6 is unnecessary as all cases cover the rage [0, 9].
-; The range check guarantees that cases other than 1,4,7 and 2,5,8,9 must be
-; in 0,3,6.
+; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 20,
+; but the latter set has more cases, so should be tested for earlier. The bit
+; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range
+; check guarantees that cases other than 1,4,7 and 2,5,8,9 must be in 0,3,6.
 
 ; CHECK-LABEL: bt_order_by_weight
 ; 146 = 2^1 + 2^4 + 2^7
 ; CHECK: movl $146
 ; CHECK: btl
 ; 292 = 2^2 + 2^5 + 2^8 + 2^9
 ; CHECK: movl $804
 ; CHECK: btl
 ; 73 = 2^0 + 2^3 + 2^6
 ; CHECK-NOT: movl $73
 ; CHECK-NOT: btl
 }
 
 !1 = !{!"branch_weights",
        ; Default:
        i32 1,
        ; Cases 0,3,6:
-       i32 4, i32 4, i32 4,
+       i32 0, i32 0, i32 20,
        ; Cases 1,4,7:
        i32 4294967295, i32 2, i32 4294967295,
        ; Cases 2,5,8,9:
-       i32 3, i32 3, i32 3, i32 3}
+       i32 0, i32 0, i32 0, i32 20}
 
 define void @order_by_weight_and_fallthrough(i32 %x) {
 entry:
   switch i32 %x, label %return [
     i32 100, label %bb1
     i32 200, label %bb0
     i32 300, label %bb0
   ], !prof !2