From 800b12f90a43d83d17a0e31ad09983033b6789af Mon Sep 17 00:00:00 2001 From: Hans Wennborg Date: Fri, 29 Mar 2019 13:40:05 +0000 Subject: [PATCH] Switch lowering: exploit unreachable fall-through when lowering case range cluster In the example below, we would previously emit two range checks, one for cases 1--3 and one for 4--6. This patch makes us exploit the fact that the fall-through is unreachable and only one range check is necessary. switch i32 %i, label %default [ i32 1, label %bb1 i32 2, label %bb1 i32 3, label %bb1 i32 4, label %bb2 i32 5, label %bb2 i32 6, label %bb2 ] default: unreachable llvm-svn: 357252 --- .../CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 24 ++++++++++++++++--- .../lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h | 2 ++ .../CodeGen/AArch64/switch-unreachable-default.ll | 16 ++++++------- llvm/test/CodeGen/X86/switch.ll | 27 ++++++++++++++++++++++ 4 files changed, 57 insertions(+), 12 deletions(-) diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 4788a5c..05dca5f 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -2283,6 +2283,17 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, SDValue CondLHS = getValue(CB.CmpLHS); SDLoc dl = CB.DL; + if (CB.CC == ISD::SETTRUE) { + // Branch or fall through to TrueBB. + addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb); + SwitchBB->normalizeSuccProbs(); + if (CB.TrueBB != NextBlock(SwitchBB)) { + DAG.setRoot(DAG.getNode(ISD::BR, dl, MVT::Other, getControlRoot(), + DAG.getBasicBlock(CB.TrueBB))); + } + return; + } + // Build the setcc now. if (!CB.CmpMHS) { // Fold "(X == true)" to X and "(X == false)" to !X to @@ -10303,10 +10314,13 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, MachineBasicBlock *CurMBB = W.MBB; for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) { + bool FallthroughUnreachable = false; MachineBasicBlock *Fallthrough; if (I == W.LastCluster) { // For the last cluster, fall through to the default destination. Fallthrough = DefaultMBB; + FallthroughUnreachable = isa( + DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg()); } else { Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock()); CurMF->insert(BBI, Fallthrough); @@ -10343,9 +10357,7 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, } } - if (Fallthrough == DefaultMBB && - isa( - DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg())) { + if (FallthroughUnreachable) { // Skip the range check if the fallthrough block is unreachable. JTH->OmitRangeCheck = true; } @@ -10368,6 +10380,8 @@ 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 = &BitTestCases[I->BTCasesIndex]; @@ -10412,6 +10426,10 @@ void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, RHS = I->High; } + // If Fallthrough is unreachable, fold away the comparison. + if (FallthroughUnreachable) + CC = ISD::SETTRUE; + // The false probability is the sum of all unhandled cases. CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, getCurSDLoc(), I->Prob, UnhandledProbs); diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index 3ed1b64..e9b94d9 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -226,6 +226,8 @@ private: /// multi-case switch statements. struct CaseBlock { // The condition code to use for the case block's setcc node. + // Besides the integer condition codes, this can also be SETTRUE, in which + // case no comparison gets emitted. ISD::CondCode CC; // The LHS/MHS/RHS of the comparison to emit. diff --git a/llvm/test/CodeGen/AArch64/switch-unreachable-default.ll b/llvm/test/CodeGen/AArch64/switch-unreachable-default.ll index 9db3cee..9acc5a1 100644 --- a/llvm/test/CodeGen/AArch64/switch-unreachable-default.ll +++ b/llvm/test/CodeGen/AArch64/switch-unreachable-default.ll @@ -74,17 +74,15 @@ entry: i32 64, label %bb5 ] -; The switch is lowered with a jump table for cases 1--32 and case 64 checked -; separately. Even though the default of switch is unreachable, the fall-through -; for the jump table *is* reachable so the range check must be emitted. +; The switch is lowered with a jump table for cases 1--32 and case 64 handled +; separately. Even though the default of the switch is unreachable, the +; fall-through for the jump table *is* reachable so the range check must be +; emitted. ; ; CHECK-LABEL: reachable_fallthrough -; CHECK: sub -; CHECK: cmp +; CHECK: sub [[REG:w[0-9]+]], w0, #1 +; CHECK: cmp [[REG]], #31 ; CHECK: b.hi -; -; TODO: Drop the cmp for the 64 case since its fallthrough is unreachable. - def: unreachable bb1: br label %return @@ -94,6 +92,6 @@ bb4: br label %return bb5: br label %return return: - %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 0, %bb5 ] + %p = phi i32 [ 3, %bb1 ], [ 2, %bb2 ], [ 1, %bb3 ], [ 0, %bb4 ], [ 42, %bb5 ] ret i32 %p } diff --git a/llvm/test/CodeGen/X86/switch.ll b/llvm/test/CodeGen/X86/switch.ll index a0ebc4e..639b9c0 100644 --- a/llvm/test/CodeGen/X86/switch.ll +++ b/llvm/test/CodeGen/X86/switch.ll @@ -778,3 +778,30 @@ end: ; CHECK: btl ; CHECK-NOT: btl } + + +define void @range_with_unreachable_fallthrough(i32 %i) { +entry: + switch i32 %i, label %default [ + i32 1, label %bb1 + i32 2, label %bb1 + i32 3, label %bb1 + i32 4, label %bb2 + i32 5, label %bb2 + i32 6, label %bb2 + ] +bb1: tail call void @g(i32 0) br label %return +bb2: tail call void @g(i32 1) br label %return +default: unreachable + +return: + ret void + +; CHECK-LABEL: range_with_unreachable_fallthrough: +; Since the default is unreachable, either the 1--3 or the 4--6 cluster will be +; reached. Only one comparison should be emitted. +; CHECK: cmpl +; CHECK-NOT: cmpl +; CHECK: jmp g +; CHECK: jmp g +} -- 2.7.4