Assign weights to edges to jump table when lowering switch statement.

[congh]

Summary

Currently, when lowering switch statement and a new basic block is built for jump table, the edge to this new block is not assigned with a correct weight. This patch collects the edge weight from all its successors and assign this sum of weights to the edge (and also the other fall-through edge). Test cases are adjusted accordingly.

[davidxl]

Can we add more unit test cases (with annotated profile data) to cover profile update for various switch lowering strategies?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1901

Same bug occurs here too. The weight to MBB should be the sum of the ExtraWeight of all cases of 'B'. See visitBitTestCase.

[congh]

In D12166#229003, @davidxl wrote:

Can we add more unit test cases (with annotated profile data) to cover profile update for various switch lowering strategies?

OK. I will investigate on switch lowering and try to make a test case covering all cases with profile data check.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1901

You are right. I will also fix this issue in this patch.

[congh]

Update the patch by also adding forgotten edge weight when adding bit test header for lowering switch statement.

[davidxl]

This looks fine to me in general, but other reviewers or Hans may need to take a look.

(The additional test cases can be added as a follow up).

[congh]

In D12166#230433, @davidxl wrote:

This looks fine to me in general, but other reviewers or Hans may need to take a look.

(The additional test cases can be added as a follow up).

OK, thanks! I have added Hans as a reviewer.

[hans]

This looks fine to me, but it would be really nice to get tests here.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1901

Does it get the DefaultWeight right here? (Not a criticism, just wondering if this ever worked.)

8018

I think the sum of all the branch weights on a branch (in this case a SwitchInst) will not overflow an uint32_t. Since we're adding up weights from the same switch it should be safe to use uint32_t for JumpWeight and skip the ScaleWeights below.

[congh]

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

1901

Yes. getEdgeWeight() will retrieve edge weight through BPI from BB instead of MBB.

8018

You are right. I will replace uint64_t with uint32_t and remove ScaleWeights() here. Thanks for pointing it out!

[congh]

Change the type of weight from uint64_t to uint32_t as there won't be overflow in calculation.

Add a test case that checks if the edge weight to the jump table is correct.

[congh]

Fixed a small issue in the newly added test case.

[llvm-commits]

Hi Hans

Could you please take a look at this patch and see if it is ok to be
checked in? Thank you!

Cong

thanks,
Cong

• msg-3525-207.txt162 BDownload

[hans]

Yes, lgtm. Sorry for the delay.

test/CodeGen/X86/switch-jump-table.ll

58

This isn't really checking the probabilities though, but the block placement. Maybe that's the best we can do? :-/

Maybe use a more descriptive prefix than CHECK2? CHECK-PLACEMENT?

[congh]

test/CodeGen/X86/switch-jump-table.ll

58

As this fix is for lowering IR to MC so I think the best pass that we should indicate here is expand-isel-pseudos. I have updated it. I also changed CHECK2 into CHECK-JT-WEIGHT to make it more descriptive. Thanks!

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B,
 
   B.RegVT = VT.getSimpleVT();
   B.Reg = FuncInfo.CreateReg(B.RegVT);
   SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), dl, B.Reg, Sub);
 
   MachineBasicBlock* MBB = B.Cases[0].ThisBB;
 
   addSuccessorWithWeight(SwitchBB, B.Default);
   addSuccessorWithWeight(SwitchBB, MBB);
 
   SDValue BrRange = DAG.getNode(ISD::BRCOND, dl,
                                 MVT::Other, CopyTo, RangeCmp,
                                 DAG.getBasicBlock(B.Default));
 
   // Avoid emitting unnecessary branches to the next block.
   if (MBB != NextBlock(SwitchBB))
     BrRange = DAG.getNode(ISD::BR, dl, MVT::Other, BrRange,
switch (I->Kind) {
       case CC_JumpTable: {
         // FIXME: Optimize away range check based on pivot comparisons.
         JumpTableHeader *JTH = &JTCases[I->JTCasesIndex].first;
         JumpTable *JT = &JTCases[I->JTCasesIndex].second;
 
         // The jump block hasn't been inserted yet; insert it here.
         MachineBasicBlock *JumpMBB = JT->MBB;
         CurMF->insert(BBI, JumpMBB);
-        addSuccessorWithWeight(CurMBB, Fallthrough);
-        addSuccessorWithWeight(CurMBB, JumpMBB);
+
+        // Collect the sum of weights of outgoing edges from JumpMBB, which will
+        // be the edge weight on CurMBB->JumpMBB.
+        uint64_t JumpWeight = 0;
+        for (auto Succ : JumpMBB->successors())
+          JumpWeight += getEdgeWeight(JumpMBB, Succ);
+        uint32_t FallthruWeight = getEdgeWeight(CurMBB, Fallthrough);
+
+        // Scale down the sum if it cannot fit in 32-bit.
+        if (JumpWeight > UINT32_MAX) {
+          uint32_t Scale = JumpWeight / UINT32_MAX + 1;
+          JumpWeight /= Scale;
+          FallthruWeight /= Scale;
+        }
+
+        addSuccessorWithWeight(CurMBB, Fallthrough, FallthruWeight);
+        addSuccessorWithWeight(CurMBB, JumpMBB,
+                               static_cast<uint32_t>(JumpWeight));
 
         // The jump table header will be inserted in our current block, do the
         // range check, and fall through to our fallthrough block.
         JTH->HeaderBB = CurMBB;
         JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
 
         // If we're in the right place, emit the jump table header right now.
         if (CurMBB == SwitchMBB) {

test/CodeGen/ARM/jump-table-islands.ll

 ; RUN: llc -mtriple=armv7-apple-ios8.0 -o - %s | FileCheck %s
 
 %BigInt = type i5500
 
 define %BigInt @test_moved_jumptable(i1 %tst, i32 %sw, %BigInt %l) {
 ; CHECK-LABEL: test_moved_jumptable:
 
 ; CHECK:   adr {{r[0-9]+}}, [[JUMP_TABLE:LJTI[0-9]+_[0-9]+]]
 ; CHECK:   b [[SKIP_TABLE:LBB[0-9]+_[0-9]+]]
 
 ; CHECK: [[JUMP_TABLE]]:
 ; CHECK:   .data_region jt32
 ; CHECK:   .long LBB{{[0-9]+_[0-9]+}}-[[JUMP_TABLE]]
 
 ; CHECK: [[SKIP_TABLE]]:
-; CHECK:   add pc, {{r[0-9]+}}, {{r[0-9]+}}
+; CHECK:   add pc, lr, {{r[0-9]+}}
   br i1 %tst, label %simple, label %complex
 
 simple:
   br label %end
 
 complex:
   switch i32 %sw, label %simple [ i32 0, label %other
                                   i32 1, label %third

test/CodeGen/Mips/nacl-align.ll

 
 
 ; CHECK-LABEL:       test1:
 
 ; CHECK:             .align  4
 ; CHECK-NEXT:    ${{BB[0-9]+_[0-9]+}}:
 ; CHECK-NEXT:        jr      $ra
 ; CHECK-NEXT:        addiu   $2, $zero, 111
-; CHECK-NEXT:        .align  4
 ; CHECK-NEXT:    ${{BB[0-9]+_[0-9]+}}:
 ; CHECK-NEXT:        jr      $ra
-; CHECK-NEXT:        addiu   $2, $zero, 222
+; CHECK-NEXT:        addiu   $2, $zero, 555
 ; CHECK-NEXT:        .align  4
 ; CHECK-NEXT:    ${{BB[0-9]+_[0-9]+}}:
 ; CHECK-NEXT:        jr      $ra
-; CHECK-NEXT:        addiu   $2, $zero, 333
+; CHECK-NEXT:        addiu   $2, $zero, 222
 ; CHECK-NEXT:        .align  4
 ; CHECK-NEXT:    ${{BB[0-9]+_[0-9]+}}:
 ; CHECK-NEXT:        jr      $ra
-; CHECK-NEXT:        addiu   $2, $zero, 444
+; CHECK-NEXT:        addiu   $2, $zero, 333
 
 }
 
 
 ; This test tests that a block whose address is taken is bundle-aligned in NaCl.
 
 @bb_array = constant [2 x i8*] [i8* blockaddress(@test2, %bb1),
                                 i8* blockaddress(@test2, %bb2)], align 4

test/CodeGen/X86/switch-jump-table.ll

 ; RUN: llc -mtriple=i686-pc-gnu-linux < %s | FileCheck %s
 
 
 ; An unreachable default destination is replaced with the most popular case label.
 
 define void @sum2(i32 %x, i32* %to) {
 ; CHECK-LABEL: sum2:
 ; CHECK: movl 4(%esp), [[REG:%e[a-z]{2}]]
 ; CHECK: cmpl $3, [[REG]]
-; CHECK: jbe .LBB0_1
+; CHECK: ja .LBB0_6
+; CHECK-NEXT: # BB#1:
+; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4)
 ; CHECK: movl $4
 ; CHECK: retl
-; CHECK-LABEL: .LBB0_1:
-; CHECK-NEXT: jmpl *.LJTI0_0(,[[REG]],4)
 
 entry:
   switch i32 %x, label %default [
     i32 0, label %bb0
     i32 1, label %bb1
     i32 2, label %bb2
     i32 3, label %bb3
     i32 4, label %bb4

 
 ; The jump table has four entries.
 ; CHECK-LABEL: .LJTI0_0:
 ; CHECK-NEXT: .long  .LBB0_2
 ; CHECK-NEXT: .long  .LBB0_3
 ; CHECK-NEXT: .long  .LBB0_4
 ; CHECK-NEXT: .long  .LBB0_5
 ; CHECK-NOT: .long
 }

test/CodeGen/X86/switch.ll

 bb3: tail call void @g(i32 3) br label %return
 bb4: tail call void @g(i32 4) br label %return
 return: ret void
 
 ; Cases 0-5 could be lowered with two bit tests,
 ; but with 6-8, the whole switch is suitable for a jump table.
 ; CHECK-LABEL: jt_is_better
 ; CHECK: cmpl $8
-; CHECK: jbe
+; CHECK: ja
 ; CHECK: jmpq *.LJTI
 }
 
 
 define void @bt_is_better(i32 %x) {
 entry:
   switch i32 %x, label %return [
     i32 0, label %bb0