From 9a5d29b0bff0a4743cbf07c930a5e5b28111b55c Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Wed, 2 Oct 2019 14:35:06 +0000 Subject: [PATCH] Reapply r373431 "Switch lowering: omit range check for bit tests when default is unreachable (PR43129)" This was reverted in r373454 due to breaking the expensive-checks bot. This version addresses that by omitting the addSuccessorWithProb() call when omitting the range check. > Switch lowering: omit range check for bit tests when default is unreachable (PR43129) > > This is modeled after the same functionality for jump tables, which was > added in r357067. > > Differential revision: https://reviews.llvm.org/D68131 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@373477 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/SwitchLoweringUtils.h | 3 +- .../SelectionDAG/SelectionDAGBuilder.cpp | 43 +++++++++++-------- test/CodeGen/X86/switch-bt.ll | 5 +-- 3 files changed, 29 insertions(+), 22 deletions(-) diff --git a/include/llvm/CodeGen/SwitchLoweringUtils.h b/include/llvm/CodeGen/SwitchLoweringUtils.h index 31b5f794d90..b8adcf759b1 100644 --- a/include/llvm/CodeGen/SwitchLoweringUtils.h +++ b/include/llvm/CodeGen/SwitchLoweringUtils.h @@ -212,13 +212,14 @@ struct BitTestBlock { BitTestInfo Cases; BranchProbability Prob; BranchProbability DefaultProb; + bool OmitRangeCheck; BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT, bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D, BitTestInfo C, BranchProbability Pr) : 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) {} + Cases(std::move(C)), Prob(Pr), OmitRangeCheck(false) {} }; /// Return the range of values within a range. diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index ff6358b442a..c6587188bc0 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2622,17 +2622,11 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, // Subtract the minimum value. SDValue SwitchOp = getValue(B.SValue); EVT VT = SwitchOp.getValueType(); - SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, SwitchOp, - DAG.getConstant(B.First, dl, VT)); - - // Check range. - const TargetLowering &TLI = DAG.getTargetLoweringInfo(); - SDValue RangeCmp = DAG.getSetCC( - dl, TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), - Sub.getValueType()), - Sub, DAG.getConstant(B.Range, dl, VT), ISD::SETUGT); + SDValue RangeSub = + DAG.getNode(ISD::SUB, dl, VT, SwitchOp, DAG.getConstant(B.First, dl, VT)); // Determine the type of the test operands. + const TargetLowering &TLI = DAG.getTargetLoweringInfo(); bool UsePtrType = false; if (!TLI.isTypeLegal(VT)) { UsePtrType = true; @@ -2645,6 +2639,7 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, break; } } + SDValue Sub = RangeSub; if (UsePtrType) { VT = TLI.getPointerTy(DAG.getDataLayout()); Sub = DAG.getZExtOrTrunc(Sub, dl, VT); @@ -2656,20 +2651,29 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, MachineBasicBlock* MBB = B.Cases[0].ThisBB; - addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb); + if (!B.OmitRangeCheck) + addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb); addSuccessorWithProb(SwitchBB, MBB, B.Prob); SwitchBB->normalizeSuccProbs(); - SDValue BrRange = DAG.getNode(ISD::BRCOND, dl, - MVT::Other, CopyTo, RangeCmp, - DAG.getBasicBlock(B.Default)); + SDValue Root = CopyTo; + if (!B.OmitRangeCheck) { + // Conditional branch to the default block. + SDValue RangeCmp = DAG.getSetCC(dl, + TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), + RangeSub.getValueType()), + RangeSub, DAG.getConstant(B.Range, dl, RangeSub.getValueType()), + ISD::SETUGT); + + Root = DAG.getNode(ISD::BRCOND, dl, MVT::Other, Root, 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, - DAG.getBasicBlock(MBB)); + Root = DAG.getNode(ISD::BR, dl, MVT::Other, Root, DAG.getBasicBlock(MBB)); - DAG.setRoot(BrRange); + DAG.setRoot(Root); } /// visitBitTestCase - this function produces one "bit test" @@ -10164,8 +10168,6 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, break; } case CC_BitTests: { - // FIXME: If Fallthrough is unreachable, skip the range check. - // FIXME: Optimize away range check based on pivot comparisons. BitTestBlock *BTB = &SL->BitTestCases[I->BTCasesIndex]; @@ -10186,6 +10188,11 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, BTB->DefaultProb -= DefaultProb / 2; } + if (FallthroughUnreachable) { + // Skip the range check if the fallthrough block is unreachable. + BTB->OmitRangeCheck = true; + } + // If we're in the right place, emit the bit test header right now. if (CurMBB == SwitchMBB) { visitBitTestHeader(*BTB, SwitchMBB); diff --git a/test/CodeGen/X86/switch-bt.ll b/test/CodeGen/X86/switch-bt.ll index 797ad4bccfd..965cdbf17f5 100644 --- a/test/CodeGen/X86/switch-bt.ll +++ b/test/CodeGen/X86/switch-bt.ll @@ -157,13 +157,12 @@ sw.epilog: } -; TODO: Omit the range check when the default case is unreachable, see PR43129. +; Omit the range check when the default case is unreachable, see PR43129. declare void @g(i32) define void @test5(i32 %x) { ; CHECK-LABEL: test5 -; CHECK: cmpl $8, %edi -; CHECK: ja +; CHECK-NOT: cmp ; 73 = 2^0 + 2^3 + 2^6 ; CHECK: movl $73 -- 2.40.0