[ISEL][BitTestBlock] omit additional bit test when default destination is unreachable

[nickdesaulniers]

Summary

Otherwise we end up with an extra conditional jump, following by an
unconditional jump off the end of a function. ie.

bb.0:
  BT32rr ..
  JCC_1 %bb.4 ...
bb.1:
  BT32rr ..
  JCC_1 %bb.2 ...
  JMP_1 %bb.3
bb.2:
  ...
bb.3.unreachable:
bb.4:
  ...

Should be equivalent to:
bb.0:
  BT32rr ..
  JCC_1 %bb.4 ...
  JMP_1 %bb.2
bb.1:
bb.2:
  ...
bb.3.unreachable:
bb.4:
  ...

This can occur since at the higher level IR (Instruction) SwitchInsts
are required to have BBs for default destinations, even when it can be
deduced that such BBs are unreachable.

For most programs, this isn't an issue, just wasted instructions since the
unreachable has been statically proven.

The x86_64 Linux kernel when built with CONFIG_LTO_CLANG_THIN=y fails to
boot though once D106056 is re-applied. D106056 makes it more likely
that correlation-propagation (CVP) can deduce that the default case of
SwitchInsts are unreachable. The x86_64 kernel uses a binary post
processor called objtool, which emits this warning:

vmlinux.o: warning: objtool: cfg80211_edmg_chandef_valid()+0x169: can't
find jump dest instruction at .text.cfg80211_edmg_chandef_valid+0x17b

I haven't debugged precisely why this causes a failure at boot time, but
fixing this very obvious jump off the end of the function fixes the
warning and boot problem.

Link: https://bugs.llvm.org/show_bug.cgi?id=50080
Fixes: https://github.com/ClangBuiltLinux/linux/issues/679
Fixes: https://github.com/ClangBuiltLinux/linux/issues/1440

[lebedev.ri]

llvm/test/CodeGen/X86/SwitchLowering.ll

68

Precommit please

[nickdesaulniers]

• rebase on D109106

[nickdesaulniers]

ugh, global isel has this problem, too...

[hans]

llvm/lib/CodeGen/SwitchLoweringUtils.cpp

455 ↗

(On Diff #370104)

I don't think this line is quite right.

The "default" for a bit test is not necessarily the same as the default for the SwitchInst -- it's just the block that control falls through to if all the bit tests fail, and that block could be one that handles other switch cases. (It would be better if BitTestBlock.Default was renamed to BitTestBlock.Fallthrough).

You can see how BitTestBlock.Default gets set in SelectionDAGBuilder::lowerWorkItem():

// Fill in fields of the BitTestBlock.                          
BTB->Parent = CurMBB;
BTB->Default = Fallthrough;

However, that code does know whether the fallthrough block is unreachable, and already uses that to set the BitTestBlock::OmitRangeCheck. Maybe OmitRangeCheck could be renamed to UnreachableDefault, and used for both omitting the range check and skipping the last bit test?

[nickdesaulniers]

• reused OmitRangeCheck, remove UnreachableDefault

[nickdesaulniers]

llvm/lib/CodeGen/SwitchLoweringUtils.cpp

455 ↗

(On Diff #370104)

Oh, right, good point. Yeah, OmitRangeCheck is set based on the same criteria, I should just re-use that; then I don't need to add anything to BitTestBlock.

I think the identifier OmitRangeCheck is nice and explains what we're going to do, so I wont rename it to UnreachableDefault.

[nickdesaulniers]

Should I fix GlobalISel in this patch, or do so in a follow up (renaming this from ISEL to SDAGISEL)?

[nickdesaulniers]

I'm going to move llvm/test/CodeGen/X86/switch-bit-test-unreachable-default.ll to D109106 so that we can also see more easily what's changed by this commit. I'm also going to add a RUN with explicit -global-isel=0/-global-isel=1.

[nickdesaulniers]

• rebase on D109106; haven't fixed global isel yet.

[nickdesaulniers]

• fix global-isel, too

[nickdesaulniers]

• re-add [ISEL][BitTestBlock] I accidentally dropped when rebasing

[hans]

Nice, lgtm. Only some nits about names from my side now.

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

3022

I think UnreachableDefault (or UnreachableFallthrough) would be a better name now, since it doesn't just omit the range check, it also omits the last bit test.

Also some day we should unify all the switch lowering implementations in LLVM, I think there are four or so now :-)

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

10872–10873

The behaviour is really "skip the range check and last bit test", so the comment could either reflect that -- or if we rename the variable then maybe the comment becomes redundant and we can drop it.

[nickdesaulniers]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

3022

Should this be renamed for BitTestBlock AND JumpTableHeader?

[nickdesaulniers]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

3022

Created https://reviews.llvm.org/D109455 as a child revision. I'm going to land this as is to unblock https://reviews.llvm.org/D106056 ASAP (and get our failing boot tests back online).

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
       // the default block after the last bit test fails. This is because the
       // range check during bit test header creation has guaranteed that every
       // case here doesn't go outside the range. In this case, there is no need
       // to perform the last bit test, as it will always be true. Instead, make
       // the second-to-last bit-test fall through to the target of the last bit
       // test, and delete the last bit test.
 
       MachineBasicBlock *NextMBB;
-      if (BTB.ContiguousRange && j + 2 == ej) {
+      if ((BTB.ContiguousRange || BTB.OmitRangeCheck) && j + 2 == ej) {
         // Second-to-last bit-test with contiguous range: fall through to the
         // target of the final bit test.
         NextMBB = BTB.Cases[j + 1].TargetBB;
       } else if (j + 1 == ej) {
         // For the last bit test, fall through to Default.
         NextMBB = BTB.Default;
       } else {
         // Otherwise, fall through to the next bit test.
         NextMBB = BTB.Cases[j + 1].ThisBB;
       }
 
       emitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j], MBB);
 
-      if (BTB.ContiguousRange && j + 2 == ej) {
+      if ((BTB.ContiguousRange || BTB.OmitRangeCheck) && j + 2 == ej) {
         // We need to record the replacement phi edge here that normally
         // happens in emitBitTestCase before we delete the case, otherwise the
         // phi edge will be lost.
         addMachineCFGPred({BTB.Parent->getBasicBlock(),
                            BTB.Cases[ej - 1].TargetBB->getBasicBlock()},
                           MBB);
         // Since we're not going to use the final bit test, remove it.
         BTB.Cases.pop_back();

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

switch (I->Kind) {
         // If the cases in bit test don't form a contiguous range, we evenly
         // distribute the probability on the edge to Fallthrough to two
         // successors of CurMBB.
         if (!BTB->ContiguousRange) {
           BTB->Prob += DefaultProb / 2;
           BTB->DefaultProb -= DefaultProb / 2;
         }
 
-        if (FallthroughUnreachable) {
-          // Skip the range check if the fallthrough block is unreachable.
+        if (FallthroughUnreachable)
           BTB->OmitRangeCheck = true;
-        }
 
         // If we're in the right place, emit the bit test header right now.
         if (CurMBB == SwitchMBB) {
           visitBitTestHeader(*BTB, SwitchMBB);
           BTB->Emitted = true;
         }
         break;
       }

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
       // the default block after the last bit test fails. This is because the
       // range check during bit test header creation has guaranteed that every
       // case here doesn't go outside the range. In this case, there is no need
       // to perform the last bit test, as it will always be true. Instead, make
       // the second-to-last bit-test fall through to the target of the last bit
       // test, and delete the last bit test.
 
       MachineBasicBlock *NextMBB;
-      if (BTB.ContiguousRange && j + 2 == ej) {
-        // Second-to-last bit-test with contiguous range: fall through to the
-        // target of the final bit test.
+      if ((BTB.ContiguousRange || BTB.OmitRangeCheck) && j + 2 == ej) {
+        // Second-to-last bit-test with contiguous range or omitted range
+        // check: fall through to the target of the final bit test.
         NextMBB = BTB.Cases[j + 1].TargetBB;
       } else if (j + 1 == ej) {
         // For the last bit test, fall through to Default.
         NextMBB = BTB.Default;
       } else {
         // Otherwise, fall through to the next bit test.
         NextMBB = BTB.Cases[j + 1].ThisBB;
       }
 
       SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
                             FuncInfo->MBB);
 
       CurDAG->setRoot(SDB->getRoot());
       SDB->clear();
       CodeGenAndEmitDAG();
 
-      if (BTB.ContiguousRange && j + 2 == ej) {
+      if ((BTB.ContiguousRange || BTB.OmitRangeCheck) && j + 2 == ej) {
         // Since we're not going to use the final bit test, remove it.
         BTB.Cases.pop_back();
         break;
       }
     }
 
     // Update PHI Nodes
     for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();

llvm/test/CodeGen/X86/SwitchLowering.ll

 
 bb7:            ; preds = %bb, %bb
         tail call void @foo( i8 %tmp )
         ret i8* %tmp2
 }
 
 declare void @foo(i8)
 
+; PR50080
+; The important part of this test is that we emit only 1 bit test rather than
+; 2 since the default BB of the switch is unreachable.
 define i32 @baz(i32 %0) {
-; FIXME: Get rid of this conditional jump and bit test in .LBB1_1.
-; FIXME: .LBB1_4 should not have .LBB1_1 as a predecessor, or be past the end
-; FIXME: of the function.
 ; CHECK-LABEL: baz:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; CHECK-NEXT:    movl $13056, %edx # imm = 0x3300
 ; CHECK-NEXT:    btl %ecx, %edx
 ; CHECK-NEXT:    jae .LBB1_1
-; CHECK-NEXT:  # %bb.3: # %return
+; CHECK-NEXT:  # %bb.2: # %return
 ; CHECK-NEXT:    retl
-; CHECK-NEXT:  .LBB1_1:
-; CHECK-NEXT:    movl $48, %eax
-; CHECK-NEXT:    btl %ecx, %eax
-; CHECK-NEXT:    jae .LBB1_4
-; CHECK-NEXT:  # %bb.2: # %sw.epilog8
+; CHECK-NEXT:  .LBB1_1: # %sw.epilog8
 ; CHECK-NEXT:    movl $1, %eax
 ; CHECK-NEXT:    retl
-; CHECK-NEXT:  .LBB1_4: # %if.then.unreachabledefault
   switch i32 %0, label %if.then.unreachabledefault [
     i32 4, label %sw.epilog8
     i32 5, label %sw.epilog8
     i32 8, label %sw.bb2
     i32 9, label %sw.bb2
     i32 12, label %sw.bb4
     i32 13, label %sw.bb4
   ]

llvm/test/CodeGen/X86/switch-bit-test-unreachable-default.ll

 ; RUN: llc -mtriple=x86_64-- -global-isel=0 -print-after=finalize-isel \
 ; RUN:   -stop-after=finalize-isel %s -o /dev/null 2>&1 | \
 ; RUN:   FileCheck %s --check-prefix=CHECK-SDISEL
 ; RUN: llc -mtriple=x86_64-- -global-isel=1 -print-after=finalize-isel \
 ; RUN:   -stop-after=finalize-isel %s -o /dev/null 2>&1 | \
 ; RUN:   FileCheck %s --check-prefix=CHECK-GISEL
 
 ; PR50080
 define i32 @baz(i32 %0) {
-; FIXME: Get rid of this conditional jump and bit test in bb.5.
-; FIXME: bb.2 should not have bb.5 as a predecessor.
 ; CHECK-SDISEL: bb.0 (%ir-block.1):
 ; CHECK-SDISEL:   successors: %bb.4(0x80000000); %bb.4(100.00%)
 ; CHECK-SDISEL:   liveins: $edi
 ; CHECK-SDISEL:   %1:gr32 = COPY $edi
 ; CHECK-SDISEL:   %2:gr32 = MOV32r0 implicit-def dead $eflags
 ; CHECK-SDISEL:   %3:gr32 = COPY %1:gr32
 ; CHECK-SDISEL: bb.4 (%ir-block.1):
 ; CHECK-SDISEL: ; predecessors: %bb.0
-; CHECK-SDISEL:   successors: %bb.3(0x55555555), %bb.5(0x2aaaaaab); %bb.3(66.67%), %bb.5(33.33%)
+; CHECK-SDISEL:   successors: %bb.3(0x55555555), %bb.1(0x2aaaaaab); %bb.3(66.67%), %bb.1(33.33%)
 ; CHECK-SDISEL:   %4:gr32 = MOV32ri 13056
 ; CHECK-SDISEL:   BT32rr killed %4:gr32, %3:gr32, implicit-def $eflags
 ; CHECK-SDISEL:   JCC_1 %bb.3, 2, implicit $eflags
+; CHECK-SDISEL:   JMP_1 %bb.1
 ; CHECK-SDISEL: bb.5 (%ir-block.1):
-; CHECK-SDISEL: ; predecessors: %bb.4
-; CHECK-SDISEL:   successors: %bb.1(0x80000000), %bb.2(0x00000000); %bb.1(100.00%), %bb.2(0.00%)
-; CHECK-SDISEL:   %5:gr32 = MOV32ri 48
-; CHECK-SDISEL:   BT32rr killed %5:gr32, %3:gr32, implicit-def $eflags
-; CHECK-SDISEL:   JCC_1 %bb.1, 2, implicit $eflags
-; CHECK-SDISEL:   JMP_1 %bb.2
 ; CHECK-SDISEL: bb.1.sw.epilog8:
-; CHECK-SDISEL: ; predecessors: %bb.5
+; CHECK-SDISEL: ; predecessors: %bb.4
 ; CHECK-SDISEL:   successors: %bb.3(0x80000000); %bb.3(100.00%)
-; CHECK-SDISEL:   %6:gr32 = MOV32ri 1
+; CHECK-SDISEL:   %5:gr32 = MOV32ri 1
 ; CHECK-SDISEL:   JMP_1 %bb.3
 ; CHECK-SDISEL: bb.2.if.then.unreachabledefault:
-; CHECK-SDISEL: ; predecessors: %bb.5
 ; CHECK-SDISEL: bb.3.return:
 ; CHECK-SDISEL: ; predecessors: %bb.4, %bb.1
-; CHECK-SDISEL:   %0:gr32 = PHI %2:gr32, %bb.4, %6:gr32, %bb.1
+; CHECK-SDISEL:   %0:gr32 = PHI %2:gr32, %bb.4, %5:gr32, %bb.1
 ; CHECK-SDISEL:   $eax = COPY %0:gr32
 ; CHECK-SDISEL:   RET 0, $eax
 
 
-; FIXME: Get rid of this conditional jump and bit test in bb.6.
-; FIXME: bb.3 should not have bb.6 as a predecessor.
 ; CHECK-GISEL: bb.1 (%ir-block.1):
 ; CHECK-GISEL:   successors: %bb.5(0x80000000); %bb.5(100.00%)
 ; CHECK-GISEL:   liveins: $edi
 ; CHECK-GISEL:   %0:gr32 = COPY $edi
-; CHECK-GISEL:   %16:gr32 = MOV32ri 1
-; CHECK-GISEL:   %17:gr32 = MOV32r0 implicit-def $eflags
+; CHECK-GISEL:   %10:gr32 = MOV32ri 1
+; CHECK-GISEL:   %11:gr32 = MOV32r0 implicit-def $eflags
 ; CHECK-GISEL:   %2:gr32 = SUB32ri8 %0:gr32(tied-def 0), 0, implicit-def $eflags
 ; CHECK-GISEL: bb.5 (%ir-block.1):
 ; CHECK-GISEL: ; predecessors: %bb.1
-; CHECK-GISEL:   successors: %bb.4(0x55555555), %bb.6(0x2aaaaaab); %bb.4(66.67%), %bb.6(33.33%)
+; CHECK-GISEL:   successors: %bb.4(0x55555555), %bb.2(0x2aaaaaab); %bb.4(66.67%), %bb.2(33.33%)
 ; CHECK-GISEL:   %3:gr32 = MOV32ri 1
-; CHECK-GISEL:   %21:gr8 = COPY %2.sub_8bit:gr32
-; CHECK-GISEL:   $cl = COPY %21:gr8
+; CHECK-GISEL:   %13:gr8 = COPY %2.sub_8bit:gr32
+; CHECK-GISEL:   $cl = COPY %13:gr8
 ; CHECK-GISEL:   %4:gr32 = SHL32rCL %3:gr32(tied-def 0), implicit-def $eflags, implicit $cl
 ; CHECK-GISEL:   %6:gr32 = AND32ri %4:gr32(tied-def 0), 13056, implicit-def $eflags
 ; CHECK-GISEL:   %7:gr32 = MOV32r0 implicit-def $eflags
 ; CHECK-GISEL:   CMP32rr %6:gr32, %7:gr32, implicit-def $eflags
-; CHECK-GISEL:   %20:gr8 = SETCCr 5, implicit $eflags
-; CHECK-GISEL:   TEST8ri %20:gr8, 1, implicit-def $eflags
+; CHECK-GISEL:   %12:gr8 = SETCCr 5, implicit $eflags
+; CHECK-GISEL:   TEST8ri %12:gr8, 1, implicit-def $eflags
 ; CHECK-GISEL:   JCC_1 %bb.4, 5, implicit $eflags
+; CHECK-GISEL:   JMP_1 %bb.2
 ; CHECK-GISEL: bb.6 (%ir-block.1):
-; CHECK-GISEL: ; predecessors: %bb.5
-; CHECK-GISEL:   successors: %bb.2(0x80000000), %bb.3(0x00000000); %bb.2(100.00%), %bb.3(0.00%)
-; CHECK-GISEL:   %9:gr32 = MOV32ri 1
-; CHECK-GISEL:   %19:gr8 = COPY %2.sub_8bit:gr32
-; CHECK-GISEL:   $cl = COPY %19:gr8
-; CHECK-GISEL:   %10:gr32 = SHL32rCL %9:gr32(tied-def 0), implicit-def $eflags, implicit $cl
-; CHECK-GISEL:   %12:gr32 = AND32ri8 %10:gr32(tied-def 0), 48, implicit-def $eflags
-; CHECK-GISEL:   %13:gr32 = MOV32r0 implicit-def $eflags
-; CHECK-GISEL:   CMP32rr %12:gr32, %13:gr32, implicit-def $eflags
-; CHECK-GISEL:   %18:gr8 = SETCCr 5, implicit $eflags
-; CHECK-GISEL:   TEST8ri %18:gr8, 1, implicit-def $eflags
-; CHECK-GISEL:   JCC_1 %bb.2, 5, implicit $eflags
-; CHECK-GISEL:   JMP_1 %bb.3
 ; CHECK-GISEL: bb.2.sw.epilog8:
-; CHECK-GISEL: ; predecessors: %bb.6
+; CHECK-GISEL: ; predecessors: %bb.5
 ; CHECK-GISEL:   successors: %bb.4(0x80000000); %bb.4(100.00%)
 ; CHECK-GISEL:   JMP_1 %bb.4
 ; CHECK-GISEL: bb.3.if.then.unreachabledefault:
-; CHECK-GISEL: ; predecessors: %bb.6
 ; CHECK-GISEL: bb.4.return:
 ; CHECK-GISEL: ; predecessors: %bb.5, %bb.2
-; CHECK-GISEL:   %15:gr32 = PHI %16:gr32, %bb.2, %17:gr32, %bb.5
-; CHECK-GISEL:   $eax = COPY %15:gr32
+; CHECK-GISEL:   %9:gr32 = PHI %10:gr32, %bb.2, %11:gr32, %bb.5
+; CHECK-GISEL:   $eax = COPY %9:gr32
 ; CHECK-GISEL:   RET 0, implicit $eax
 
   switch i32 %0, label %if.then.unreachabledefault [
     i32 4, label %sw.epilog8
     i32 5, label %sw.epilog8
     i32 8, label %sw.bb2
     i32 9, label %sw.bb2
     i32 12, label %sw.bb4