From 394e321a2ea021194891cf5b0c5747a901fb7915 Mon Sep 17 00:00:00 2001 From: Yingwei Zheng Date: Thu, 20 Jun 2024 13:45:18 +0800 Subject: Reland "[CVP] Check whether the default case is reachable (#79993)" (#96089) This patch reverts https://github.com/llvm/llvm-project/pull/81585 as https://github.com/llvm/llvm-project/pull/78582 has been landed. Now clang works well with reproducer https://github.com/llvm/llvm-project/pull/79993#issuecomment-1936822679. --- .../Scalar/CorrelatedValuePropagation.cpp | 32 +++ .../Transforms/CorrelatedValuePropagation/basic.ll | 11 +- .../CorrelatedValuePropagation/switch.ll | 301 +++++++++++++++++++++ 3 files changed, 339 insertions(+), 5 deletions(-) create mode 100644 llvm/test/Transforms/CorrelatedValuePropagation/switch.ll diff --git a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index 50b5fdb..88adeb5 100644 --- a/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -366,6 +366,7 @@ static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, { // Scope for SwitchInstProfUpdateWrapper. It must not live during // ConstantFoldTerminator() as the underlying SwitchInst can be changed. SwitchInstProfUpdateWrapper SI(*I); + unsigned ReachableCaseCount = 0; for (auto CI = SI->case_begin(), CE = SI->case_end(); CI != CE;) { ConstantInt *Case = CI->getCaseValue(); @@ -402,6 +403,31 @@ static bool processSwitch(SwitchInst *I, LazyValueInfo *LVI, // Increment the case iterator since we didn't delete it. ++CI; + ++ReachableCaseCount; + } + + BasicBlock *DefaultDest = SI->getDefaultDest(); + if (ReachableCaseCount > 1 && + !isa(DefaultDest->getFirstNonPHIOrDbg())) { + ConstantRange CR = LVI->getConstantRangeAtUse(I->getOperandUse(0), + /*UndefAllowed*/ false); + // The default dest is unreachable if all cases are covered. + if (!CR.isSizeLargerThan(ReachableCaseCount)) { + BasicBlock *NewUnreachableBB = + BasicBlock::Create(BB->getContext(), "default.unreachable", + BB->getParent(), DefaultDest); + new UnreachableInst(BB->getContext(), NewUnreachableBB); + + DefaultDest->removePredecessor(BB); + SI->setDefaultDest(NewUnreachableBB); + + if (SuccessorsCount[DefaultDest] == 1) + DTU.applyUpdates({{DominatorTree::Delete, BB, DefaultDest}}); + DTU.applyUpdates({{DominatorTree::Insert, BB, NewUnreachableBB}}); + + ++NumDeadCases; + Changed = true; + } } } @@ -1283,6 +1309,12 @@ CorrelatedValuePropagationPass::run(Function &F, FunctionAnalysisManager &AM) { if (!Changed) { PA = PreservedAnalyses::all(); } else { +#if defined(EXPENSIVE_CHECKS) + assert(DT->verify(DominatorTree::VerificationLevel::Full)); +#else + assert(DT->verify(DominatorTree::VerificationLevel::Fast)); +#endif // EXPENSIVE_CHECKS + PA.preserve(); PA.preserve(); } diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll index 701d867..a3b1c89 100644 --- a/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/basic.ll @@ -442,7 +442,7 @@ define i32 @switch_range(i32 %cond) { ; CHECK-NEXT: entry: ; CHECK-NEXT: [[S:%.*]] = urem i32 [[COND:%.*]], 3 ; CHECK-NEXT: [[S1:%.*]] = add nuw nsw i32 [[S]], 1 -; CHECK-NEXT: switch i32 [[S1]], label [[UNREACHABLE:%.*]] [ +; CHECK-NEXT: switch i32 [[S1]], label [[DEFAULT_UNREACHABLE:%.*]] [ ; CHECK-NEXT: i32 1, label [[EXIT1:%.*]] ; CHECK-NEXT: i32 2, label [[EXIT2:%.*]] ; CHECK-NEXT: i32 3, label [[EXIT1]] @@ -451,6 +451,8 @@ define i32 @switch_range(i32 %cond) { ; CHECK-NEXT: ret i32 1 ; CHECK: exit2: ; CHECK-NEXT: ret i32 2 +; CHECK: default.unreachable: +; CHECK-NEXT: unreachable ; CHECK: unreachable: ; CHECK-NEXT: ret i32 0 ; @@ -513,10 +515,9 @@ define i8 @switch_defaultdest_multipleuse(i8 %t0) { ; CHECK-NEXT: entry: ; CHECK-NEXT: [[O:%.*]] = or i8 [[T0:%.*]], 1 ; CHECK-NEXT: [[R:%.*]] = srem i8 1, [[O]] -; CHECK-NEXT: switch i8 [[R]], label [[EXIT:%.*]] [ -; CHECK-NEXT: i8 0, label [[EXIT]] -; CHECK-NEXT: i8 1, label [[EXIT]] -; CHECK-NEXT: ] +; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK: default.unreachable: +; CHECK-NEXT: unreachable ; CHECK: exit: ; CHECK-NEXT: ret i8 0 ; diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll b/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll new file mode 100644 index 0000000..a0794d5 --- /dev/null +++ b/llvm/test/Transforms/CorrelatedValuePropagation/switch.ll @@ -0,0 +1,301 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4 +; RUN: opt < %s -passes=correlated-propagation -S | FileCheck %s + +define i32 @test_unreachable_default(i32 noundef %num) { +; CHECK-LABEL: define i32 @test_unreachable_default( +; CHECK-SAME: i32 noundef [[NUM:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[NUM]], -120 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[SUB]], 3 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2 +; CHECK-NEXT: switch i32 [[COND]], label [[DEFAULT_UNREACHABLE:%.*]] [ +; CHECK-NEXT: i32 0, label [[SW_BB:%.*]] +; CHECK-NEXT: i32 1, label [[SW_BB2:%.*]] +; CHECK-NEXT: i32 2, label [[SW_BB4:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @call0() +; CHECK-NEXT: br label [[CLEANUP:%.*]] +; CHECK: sw.bb2: +; CHECK-NEXT: [[CALL3:%.*]] = call i32 @call1() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.bb4: +; CHECK-NEXT: [[CALL5:%.*]] = call i32 @call2() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: default.unreachable: +; CHECK-NEXT: unreachable +; CHECK: sw.default: +; CHECK-NEXT: [[CALL6:%.*]] = call i32 @call3() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: cleanup: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT:%.*]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %sub = add i32 %num, -120 + %cmp = icmp ult i32 %sub, 3 + %cond = select i1 %cmp, i32 %sub, i32 2 + switch i32 %cond, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb2 + i32 2, label %sw.bb4 + ] + +sw.bb: + %call = call i32 @call0() + br label %cleanup + +sw.bb2: + %call3 = call i32 @call1() + br label %cleanup + +sw.bb4: + %call5 = call i32 @call2() + br label %cleanup + +sw.default: + %call6 = call i32 @call3() + br label %cleanup + +cleanup: + %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @test_unreachable_default_shared_edge(i32 noundef %num) { +; CHECK-LABEL: define i32 @test_unreachable_default_shared_edge( +; CHECK-SAME: i32 noundef [[NUM:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[NUM]], -120 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[SUB]], 3 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2 +; CHECK-NEXT: switch i32 [[COND]], label [[DEFAULT_UNREACHABLE:%.*]] [ +; CHECK-NEXT: i32 0, label [[SW_BB:%.*]] +; CHECK-NEXT: i32 1, label [[SW_BB2:%.*]] +; CHECK-NEXT: i32 2, label [[SW_BB4:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @call0() +; CHECK-NEXT: br label [[CLEANUP:%.*]] +; CHECK: sw.bb2: +; CHECK-NEXT: [[CALL3:%.*]] = call i32 @call1() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: default.unreachable: +; CHECK-NEXT: unreachable +; CHECK: sw.bb4: +; CHECK-NEXT: [[CALL5:%.*]] = call i32 @call4(i32 [[SUB]]) +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: cleanup: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %sub = add i32 %num, -120 + %cmp = icmp ult i32 %sub, 3 + %cond = select i1 %cmp, i32 %sub, i32 2 + switch i32 %cond, label %sw.bb4 [ + i32 0, label %sw.bb + i32 1, label %sw.bb2 + i32 2, label %sw.bb4 + ] + +sw.bb: + %call = call i32 @call0() + br label %cleanup + +sw.bb2: + %call3 = call i32 @call1() + br label %cleanup + +sw.bb4: + %val = phi i32 [ %sub, %entry ], [ %sub, %entry ] + %call5 = call i32 @call4(i32 %val) + br label %cleanup + +cleanup: + %retval.0 = phi i32 [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ] + ret i32 %retval.0 +} + +; Negative tests + +define i32 @test_reachable_default(i32 noundef %num) { +; CHECK-LABEL: define i32 @test_reachable_default( +; CHECK-SAME: i32 noundef [[NUM:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[NUM]], -120 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[SUB]], 3 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 4 +; CHECK-NEXT: switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [ +; CHECK-NEXT: i32 0, label [[SW_BB:%.*]] +; CHECK-NEXT: i32 1, label [[SW_BB2:%.*]] +; CHECK-NEXT: i32 2, label [[SW_BB4:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @call0() +; CHECK-NEXT: br label [[CLEANUP:%.*]] +; CHECK: sw.bb2: +; CHECK-NEXT: [[CALL3:%.*]] = call i32 @call1() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.bb4: +; CHECK-NEXT: [[CALL5:%.*]] = call i32 @call2() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.default: +; CHECK-NEXT: [[CALL6:%.*]] = call i32 @call3() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: cleanup: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %sub = add i32 %num, -120 + %cmp = icmp ult i32 %sub, 3 + %cond = select i1 %cmp, i32 %sub, i32 4 + switch i32 %cond, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb2 + i32 2, label %sw.bb4 + ] + +sw.bb: + %call = call i32 @call0() + br label %cleanup + +sw.bb2: + %call3 = call i32 @call1() + br label %cleanup + +sw.bb4: + %call5 = call i32 @call2() + br label %cleanup + +sw.default: + %call6 = call i32 @call3() + br label %cleanup + +cleanup: + %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @test_unreachable_default_cond_may_be_undef(i32 %num) { +; CHECK-LABEL: define i32 @test_unreachable_default_cond_may_be_undef( +; CHECK-SAME: i32 [[NUM:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[NUM]], -120 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[SUB]], 3 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2 +; CHECK-NEXT: switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [ +; CHECK-NEXT: i32 0, label [[SW_BB:%.*]] +; CHECK-NEXT: i32 1, label [[SW_BB2:%.*]] +; CHECK-NEXT: i32 2, label [[SW_BB4:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @call0() +; CHECK-NEXT: br label [[CLEANUP:%.*]] +; CHECK: sw.bb2: +; CHECK-NEXT: [[CALL3:%.*]] = call i32 @call1() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.bb4: +; CHECK-NEXT: [[CALL5:%.*]] = call i32 @call2() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.default: +; CHECK-NEXT: [[CALL6:%.*]] = call i32 @call3() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: cleanup: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[CALL6]], [[SW_DEFAULT]] ], [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %sub = add i32 %num, -120 + %cmp = icmp ult i32 %sub, 3 + %cond = select i1 %cmp, i32 %sub, i32 2 + switch i32 %cond, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb2 + i32 2, label %sw.bb4 + ] + +sw.bb: + %call = call i32 @call0() + br label %cleanup + +sw.bb2: + %call3 = call i32 @call1() + br label %cleanup + +sw.bb4: + %call5 = call i32 @call2() + br label %cleanup + +sw.default: + %call6 = call i32 @call3() + br label %cleanup + +cleanup: + %retval.0 = phi i32 [ %call6, %sw.default ], [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ] + ret i32 %retval.0 +} + +define i32 @test_default_is_already_unreachable(i32 %num) { +; CHECK-LABEL: define i32 @test_default_is_already_unreachable( +; CHECK-SAME: i32 [[NUM:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[NUM]], -120 +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[SUB]], 3 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 2 +; CHECK-NEXT: switch i32 [[COND]], label [[SW_DEFAULT:%.*]] [ +; CHECK-NEXT: i32 0, label [[SW_BB:%.*]] +; CHECK-NEXT: i32 1, label [[SW_BB2:%.*]] +; CHECK-NEXT: i32 2, label [[SW_BB4:%.*]] +; CHECK-NEXT: ] +; CHECK: sw.bb: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @call0() +; CHECK-NEXT: br label [[CLEANUP:%.*]] +; CHECK: sw.bb2: +; CHECK-NEXT: [[CALL3:%.*]] = call i32 @call1() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.bb4: +; CHECK-NEXT: [[CALL5:%.*]] = call i32 @call2() +; CHECK-NEXT: br label [[CLEANUP]] +; CHECK: sw.default: +; CHECK-NEXT: unreachable +; CHECK: cleanup: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[CALL5]], [[SW_BB4]] ], [ [[CALL3]], [[SW_BB2]] ], [ [[CALL]], [[SW_BB]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %sub = add i32 %num, -120 + %cmp = icmp ult i32 %sub, 3 + %cond = select i1 %cmp, i32 %sub, i32 2 + switch i32 %cond, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb2 + i32 2, label %sw.bb4 + ] + +sw.bb: + %call = call i32 @call0() + br label %cleanup + +sw.bb2: + %call3 = call i32 @call1() + br label %cleanup + +sw.bb4: + %call5 = call i32 @call2() + br label %cleanup + +sw.default: + unreachable + +cleanup: + %retval.0 = phi i32 [ %call5, %sw.bb4 ], [ %call3, %sw.bb2 ], [ %call, %sw.bb ] + ret i32 %retval.0 +} + +declare i32 @call0() +declare i32 @call1() +declare i32 @call2() +declare i32 @call3() +declare i32 @call4(i32) -- cgit v1.1