From 073b254cffeffdef36ffbee0c9afdc0da9cd6ac3 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Tue, 21 Sep 2021 10:22:40 +0700 Subject: [PATCH] [SimplifyCFG] Redirect switch cases that lead to UB into an unreachable block When following a case of a switch instruction is guaranteed to lead to UB, we can safely break these edges and redirect those cases into a newly created unreachable block. As result, CFG will become simpler and we can remove some of Phi inputs to make further analyzes easier. Patch by Dmitry Bakunevich! Differential Revision: https://reviews.llvm.org/D109428 Reviewed By: lebedev.ri --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 24 +++++++++++++- llvm/test/CodeGen/AArch64/arm64-ccmp.ll | 17 +--------- llvm/test/Transforms/SimplifyCFG/switch_ub.ll | 47 ++++++++------------------- 3 files changed, 37 insertions(+), 51 deletions(-) diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 0865e4a..2ff98b2 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -6629,8 +6629,30 @@ static bool removeUndefIntroducingPredecessor(BasicBlock *BB, if (DTU) DTU->applyUpdates({{DominatorTree::Delete, Predecessor, BB}}); return true; + } else if (SwitchInst *SI = dyn_cast(T)) { + // Redirect all branches leading to UB into + // a newly created unreachable block. + BasicBlock *Unreachable = BasicBlock::Create( + Predecessor->getContext(), "unreachable", BB->getParent(), BB); + Builder.SetInsertPoint(Unreachable); + // The new block contains only one instruction: Unreachable + Builder.CreateUnreachable(); + for (auto &Case : SI->cases()) + if (Case.getCaseSuccessor() == BB) { + BB->removePredecessor(Predecessor); + Case.setSuccessor(Unreachable); + } + if (SI->getDefaultDest() == BB) { + BB->removePredecessor(Predecessor); + SI->setDefaultDest(Unreachable); + } + + if (DTU) + DTU->applyUpdates( + { { DominatorTree::Insert, Predecessor, Unreachable }, + { DominatorTree::Delete, Predecessor, BB } }); + return true; } - // TODO: SwitchInst. } return false; diff --git a/llvm/test/CodeGen/AArch64/arm64-ccmp.ll b/llvm/test/CodeGen/AArch64/arm64-ccmp.ll index cc05240..d3721d3 100644 --- a/llvm/test/CodeGen/AArch64/arm64-ccmp.ll +++ b/llvm/test/CodeGen/AArch64/arm64-ccmp.ll @@ -367,22 +367,7 @@ declare i32 @foo() define void @build_modify_expr() nounwind ssp { ; CHECK-LABEL: build_modify_expr: ; CHECK: ; %bb.0: ; %entry -; CHECK-NEXT: cmp w8, #37 -; CHECK-NEXT: mov w8, #1 -; CHECK-NEXT: lsl x8, x8, xzr -; CHECK-NEXT: mov x9, #31 -; CHECK-NEXT: movk x9, #48, lsl #32 -; CHECK-NEXT: and x8, x8, x9 -; CHECK-NEXT: ccmp x8, #0, #4, ls -; CHECK-NEXT: b.eq LBB11_2 -; CHECK-NEXT: ; %bb.1: ; %if.end85 -; CHECK-NEXT: ret -; CHECK-NEXT: LBB11_2: ; %sw.bb.i.i.preheader -; CHECK-NEXT: ; implicit-def: $x8 -; CHECK-NEXT: LBB11_3: ; %sw.bb.i.i -; CHECK-NEXT: ; =>This Inner Loop Header: Depth=1 -; CHECK-NEXT: ldr x8, [x8, #32] -; CHECK-NEXT: b LBB11_3 +; CHECK-NEXT: ret entry: switch i32 undef, label %sw.bb.i.i [ i32 69, label %if.end85 diff --git a/llvm/test/Transforms/SimplifyCFG/switch_ub.ll b/llvm/test/Transforms/SimplifyCFG/switch_ub.ll index b9fcd54..0b48ee6 100644 --- a/llvm/test/Transforms/SimplifyCFG/switch_ub.ll +++ b/llvm/test/Transforms/SimplifyCFG/switch_ub.ll @@ -6,23 +6,15 @@ declare void @foo_01() declare void @foo_02() declare void @foo_03() -; TODO: Basing on fact that load(null) is UB, we can remove edge pred->bb. define i32 @test_01(i32* %p, i32 %x, i1 %cond) { ; CHECK-LABEL: @test_01( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[PRED:%.*]] -; CHECK: pred: -; CHECK-NEXT: switch i32 [[X:%.*]], label [[COMMON_RET:%.*]] [ -; CHECK-NEXT: i32 42, label [[BB]] -; CHECK-NEXT: i32 123456, label [[BB]] -; CHECK-NEXT: i32 -654321, label [[BB]] -; CHECK-NEXT: ] +; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[COMMON_RET:%.*]] ; CHECK: common.ret: -; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 0, [[PRED]] ] +; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] ; CHECK: bb: -; CHECK-NEXT: [[PHI:%.*]] = phi i32* [ null, [[PRED]] ], [ null, [[PRED]] ], [ null, [[PRED]] ], [ [[P:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R]] = load i32, i32* [[PHI]], align 4 +; CHECK-NEXT: [[R]] = load i32, i32* [[P:%.*]], align 4 ; CHECK-NEXT: br label [[COMMON_RET]] ; entry: @@ -42,23 +34,15 @@ other_succ: ret i32 0 } -; TODO: Basing on fact that load(null) is UB, we can remove edge pred->bb. define i32 @test_02(i32* %p, i32 %x, i1 %cond) { ; CHECK-LABEL: @test_02( ; CHECK-NEXT: entry: -; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[PRED:%.*]] -; CHECK: pred: -; CHECK-NEXT: switch i32 [[X:%.*]], label [[BB]] [ -; CHECK-NEXT: i32 42, label [[COMMON_RET:%.*]] -; CHECK-NEXT: i32 123456, label [[COMMON_RET]] -; CHECK-NEXT: i32 -654321, label [[COMMON_RET]] -; CHECK-NEXT: ] +; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[COMMON_RET:%.*]] ; CHECK: common.ret: -; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 0, [[PRED]] ], [ 0, [[PRED]] ], [ 0, [[PRED]] ] +; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] ; CHECK: bb: -; CHECK-NEXT: [[PHI:%.*]] = phi i32* [ null, [[PRED]] ], [ [[P:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R]] = load i32, i32* [[PHI]], align 4 +; CHECK-NEXT: [[R]] = load i32, i32* [[P:%.*]], align 4 ; CHECK-NEXT: br label [[COMMON_RET]] ; entry: @@ -78,13 +62,12 @@ other_succ: ret i32 0 } -; TODO: Basing on fact that load(null) is UB, we can remove edge pred->bb. define i32 @test_03(i32* %p, i32 %x, i1 %cond) { ; CHECK-LABEL: @test_03( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[PRED:%.*]] ; CHECK: pred: -; CHECK-NEXT: switch i32 [[X:%.*]], label [[BB]] [ +; CHECK-NEXT: switch i32 [[X:%.*]], label [[UNREACHABLE:%.*]] [ ; CHECK-NEXT: i32 42, label [[COMMON_RET:%.*]] ; CHECK-NEXT: i32 123456, label [[COMMON_RET]] ; CHECK-NEXT: i32 -654321, label [[COMMON_RET]] @@ -95,9 +78,10 @@ define i32 @test_03(i32* %p, i32 %x, i1 %cond) { ; CHECK: common.ret: ; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 1, [[DO_1]] ], [ 1, [[DO_2]] ], [ 1, [[DO_3]] ], [ 0, [[PRED]] ], [ 0, [[PRED]] ], [ 0, [[PRED]] ] ; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] +; CHECK: unreachable: +; CHECK-NEXT: unreachable ; CHECK: bb: -; CHECK-NEXT: [[PHI:%.*]] = phi i32* [ null, [[PRED]] ], [ [[P:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R]] = load i32, i32* [[PHI]], align 4 +; CHECK-NEXT: [[R]] = load i32, i32* [[P:%.*]], align 4 ; CHECK-NEXT: br label [[COMMON_RET]] ; CHECK: do_1: ; CHECK-NEXT: call void @foo_01() @@ -141,26 +125,21 @@ other_succ: ret i32 0 } -; TODO: Basing on fact that load(null) is UB, we can remove edge pred->bb. define i32 @test_04(i32* %p, i32 %x, i1 %cond) { ; CHECK-LABEL: @test_04( ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[COND:%.*]], label [[BB:%.*]], label [[PRED:%.*]] ; CHECK: pred: ; CHECK-NEXT: switch i32 [[X:%.*]], label [[COMMON_RET:%.*]] [ -; CHECK-NEXT: i32 42, label [[BB]] -; CHECK-NEXT: i32 123456, label [[BB]] -; CHECK-NEXT: i32 -654321, label [[BB]] -; CHECK-NEXT: i32 1, label [[DO_1:%.*]] -; CHECK-NEXT: i32 2, label [[DO_2:%.*]] ; CHECK-NEXT: i32 3, label [[DO_3:%.*]] +; CHECK-NEXT: i32 2, label [[DO_2:%.*]] +; CHECK-NEXT: i32 1, label [[DO_1:%.*]] ; CHECK-NEXT: ] ; CHECK: common.ret: ; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[R:%.*]], [[BB]] ], [ 1, [[DO_1]] ], [ 1, [[DO_2]] ], [ 1, [[DO_3]] ], [ 0, [[PRED]] ] ; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] ; CHECK: bb: -; CHECK-NEXT: [[PHI:%.*]] = phi i32* [ null, [[PRED]] ], [ null, [[PRED]] ], [ null, [[PRED]] ], [ [[P:%.*]], [[ENTRY:%.*]] ] -; CHECK-NEXT: [[R]] = load i32, i32* [[PHI]], align 4 +; CHECK-NEXT: [[R]] = load i32, i32* [[P:%.*]], align 4 ; CHECK-NEXT: br label [[COMMON_RET]] ; CHECK: do_1: ; CHECK-NEXT: call void @foo_01() -- 2.7.4