[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

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

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 ↗

(On Diff #370437)

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

10870 ↗

(On Diff #370437)

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 ↗

(On Diff #370437)

Should this be renamed for BitTestBlock AND JumpTableHeader?

[nickdesaulniers]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

3022 ↗

(On Diff #370437)

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/include/llvm/CodeGen/SwitchLoweringUtils.h

struct BitTestBlock {
   bool Emitted;
   bool ContiguousRange;
   MachineBasicBlock *Parent;
   MachineBasicBlock *Default;
   BitTestInfo Cases;
   BranchProbability Prob;
   BranchProbability DefaultProb;
   bool OmitRangeCheck;
+  bool UnreachableDefault;
 
   BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E,
                bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
-               BitTestInfo C, BranchProbability Pr)
+               BitTestInfo C, BranchProbability Pr, bool Ud)
       : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
         RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
-        Cases(std::move(C)), Prob(Pr), OmitRangeCheck(false) {}
+        Cases(std::move(C)), Prob(Pr), OmitRangeCheck(false),
+        UnreachableDefault(Ud) {}
 };
 
 /// Return the range of values within a range.
 uint64_t getJumpTableRange(const CaseClusterVector &Clusters, unsigned First,
                            unsigned Last);
 
 /// Return the number of cases within a range.
 uint64_t getJumpTableNumCases(const SmallVectorImpl<unsigned> &TotalCases,

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) {
+      if ((BTB.ContiguousRange || BTB.UnreachableDefault) && j + 2 == ej) {
         // Second-to-last bit-test with contiguous range: fall through to the
         // target of the final bit test.
+        // Second-to-last bit-test with unreachable default: jump to the target
+        // of the next 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.UnreachableDefault) && 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/lib/CodeGen/SwitchLoweringUtils.cpp

llvm::sort(CBV, [](const CaseBits &a, const CaseBits &b) {
     return a.Mask < b.Mask;
   });
 
   for (auto &CB : CBV) {
     MachineBasicBlock *BitTestBB =
         FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
     BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb));
   }
+  bool DefaultUnreachable =
+      isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
   BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
                             SI->getCondition(), -1U, MVT::Other, false,
                             ContiguousRange, nullptr, nullptr, std::move(BTI),
-                            TotalProb);
+                            TotalProb, DefaultUnreachable);
 
   BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
                                     BitTestCases.size() - 1, TotalProb);
   return true;
 }
 
 void SwitchCG::sortAndRangeify(CaseClusterVector &Clusters) {
 #ifndef NDEBUG

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) {
+; 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.2: # %return
+; CHECK-NEXT:    retl
+; CHECK-NEXT:  .LBB1_1: # %sw.epilog8
+; CHECK-NEXT:    movl $1, %eax
+; CHECK-NEXT:    retl
+  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
+  ]
+
+sw.bb2:
+  br label %return
+
+sw.bb4:
+  br label %return
+
+sw.epilog8:
+  br label %return
+
+if.then.unreachabledefault:
+  unreachable
+
+return:
+  %retval.0 = phi i32 [ 1, %sw.epilog8 ], [ 0, %sw.bb2 ], [ 0, %sw.bb4 ]
+  ret i32 %retval.0
+}

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

+; RUN: llc -mtriple=x86_64-- -print-after=finalize-isel -stop-after=finalize-isel %s -o /dev/null 2>&1 | FileCheck %s
+
+; PR50080
+; The important part of this test is that we emit only 1 bit test (BT32rr)
+; rather than 2 since the default BB of the switch is unreachable.
+define i32 @baz(i32 %0) {
+; CHECK: bb.0 (%ir-block.1):
+; CHECK:   successors: %bb.4(0x80000000); %bb.4(100.00%)
+; CHECK:   liveins: $edi
+; CHECK:   %1:gr32 = COPY $edi
+; CHECK:   %2:gr32 = MOV32r0 implicit-def dead $eflags
+; CHECK:   %3:gr32 = COPY %1:gr32
+; CHECK: bb.4 (%ir-block.1):
+; CHECK: ; predecessors: %bb.0
+; CHECK:   successors: %bb.3(0x55555555), %bb.1(0x2aaaaaab); %bb.3(66.67%), %bb.1(33.33%)
+; CHECK:   %4:gr32 = MOV32ri 13056
+; CHECK:   BT32rr killed %4:gr32, %3:gr32, implicit-def $eflags
+; CHECK:   JCC_1 %bb.3, 2, implicit $eflags
+; CHECK:   JMP_1 %bb.1
+; CHECK: bb.5 (%ir-block.1):
+; CHECK: bb.1.sw.epilog8:
+; CHECK: ; predecessors: %bb.4
+; CHECK:   successors: %bb.3(0x80000000); %bb.3(100.00%)
+; CHECK:   %5:gr32 = MOV32ri 1
+; CHECK:   JMP_1 %bb.3
+; CHECK: bb.2.if.then.unreachabledefault:
+; CHECK: bb.3.return:
+; CHECK: ; predecessors: %bb.4, %bb.1
+; CHECK:   %0:gr32 = PHI %2:gr32, %bb.4, %5:gr32, %bb.1
+; CHECK:   $eax = COPY %0:gr32
+; CHECK:   RET 0, $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
+    i32 13, label %sw.bb4
+  ]
+
+sw.bb2:
+  br label %return
+
+sw.bb4:
+  br label %return
+
+sw.epilog8:
+  br label %return
+
+if.then.unreachabledefault:
+  unreachable
+
+return:
+  %retval.0 = phi i32 [ 1, %sw.epilog8 ], [ 0, %sw.bb2 ], [ 0, %sw.bb4 ]
+  ret i32 %retval.0
+}