[SimplifyCFG] SwitchInst processing redirecting the UB edges from the BB with the phiNode, that contains the UB, to the new BB.

[dbakunevich]

Summary

This revision update function removeUndefIntroducingPredecessor in SImplifyCFG.
Adding processing of SwitchInst cases.
How it works:

main:
x = random(1, 2);
switch (x) {
     case 1: br BB1
     case 2: br BB2
     case 3: br BB3 ---------------------------> UnreachebleBlock
     case 4: br BB4 ---------------------------> UnreachebleBlock
}

BB1 and BB2:
phi = [...], ...
todo something


BB3 and BB4:---------------------------------> UnreachebleBlock:
phi = [undef, main] --------------------------> CreateUnreacheble()

[lebedev.ri]

Tests missing

[dbakunevich]

In D109428#2989031, @lebedev.ri wrote:

Tests missing

Should I create tests?

[lebedev.ri]

In D109428#2989037, @dbakunevich wrote:

In D109428#2989031, @lebedev.ri wrote:

Tests missing

Should I create tests?

Yes, please

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6647

Interesting follow-up can be done here. Imagine that after this is done, only one edge that doesn't go to unreachable remains. In this case, we can remove this switch and insert assume(switched_value == remained_case_value).

Totally fine if it's a separate patch.

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6638

"Create an unreachable block and redirect all edges going to BB into this block".

[mkazantsev]

You need to update Phis somehow.

[mkazantsev]

Are you sure you've updated the tests? I don't see unreachable block in them.

[mkazantsev]

llvm/test/Transforms/SimplifyCFG/switch_ub.ll

9

You can remove this TODO as well.

[mkazantsev]

Seems that optimizer has become too smart for these tests, I'll add more now. :)

[mkazantsev]

Please rebase on top of

commit 7e337d8ba2ff5015d83f355be1049e3e13fa4d18 (HEAD -> main, origin/main)
Author: Max Kazantsev <[e-mail]>
Date:   Mon Sep 13 15:27:33 2021 +0700

    [Test] Add more sophisticated tests for switch UB opt

    Optimizer is being too smart with existing tests, and the transform
    gets concealed by following transforms.

It should now be showing what this transform actually does.

[dbakunevich]

Please check new updates in this patch.

[mkazantsev]

LGTM with nits

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6616

Better

Redirect all branches leading to UB into a newly created unreachable block.

llvm/test/Transforms/SimplifyCFG/switch_ub.ll

64–65

Pls remove TODOs

[lebedev.ri]

lg

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6633–6635

Is the code clang-formatted?
Let's for consistency always do Insert first.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i)
               Builder.CreateAssumption(Builder.CreateNot(Cond));
             else
               Builder.CreateAssumption(Cond);
             Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1)
                                                        : BI->getSuccessor(0));
           }
           BI->eraseFromParent();
           if (DTU)
-            DTU->applyUpdates({{DominatorTree::Delete, Predecessor, BB}});
+            DTU->applyUpdates({ { DominatorTree::Delete, Predecessor, BB } });
           return true;
+        } else if (SwitchInst *SI = dyn_cast<SwitchInst>(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::Delete, Predecessor, BB },
+                  { DominatorTree::Insert, Predecessor, Unreachable } });
+          return true;
         }
-        // TODO: SwitchInst.
       }
 
   return false;
 }
 
 bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) {
   bool Changed = false;
 
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 
   // Remove basic blocks that have no predecessors (except the entry block)...
   // or that just have themself as a predecessor.  These are unreachable.
   if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) ||
       BB->getSinglePredecessor() == BB) {
     LLVM_DEBUG(dbgs() << "Removing BB: \n" << *BB);
     DeleteDeadBlock(BB, DTU);
     return true;

llvm/test/CodeGen/AArch64/arm64-ccmp.ll

 %str1 = type { %str2 }
 %str2 = type { [24 x i8], i8*, i32, %str1*, i32, [4 x i8], %str1*, %str1*, %str1*, %str1*, %str1*, %str1*, %str1*, %str1*, %str1*, i8*, i8, i8*, %str1*, i8* }
 
 ; Test case distilled from 126.gcc.
 ; The phi in sw.bb.i.i gets multiple operands for the %entry predecessor.
 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
     i32 70, label %if.end85
     i32 71, label %if.end85
     i32 72, label %if.end85
     i32 73, label %if.end85
     i32 105, label %if.end85

llvm/test/Transforms/SimplifyCFG/switch_ub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 ; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
 
 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:
   br i1 %cond, label %bb, label %pred
 
 pred:
   switch i32 %x, label %other_succ [i32 42, label %bb
   i32 123456, label %bb
   i32 -654321, label %bb]
 
 bb:
   %phi = phi i32* [null, %pred], [null, %pred], [null, %pred], [%p, %entry]
   %r = load i32, i32* %phi
   ret i32 %r
 
 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:
   br i1 %cond, label %bb, label %pred
 
 pred:
   switch i32 %x, label %bb [i32 42, label %other_succ
   i32 123456, label %other_succ
   i32 -654321, label %other_succ]
 
 bb:
   %phi = phi i32* [null, %pred], [%p, %entry]
   %r = load i32, i32* %phi
   ret i32 %r
 
 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]]
 ; CHECK-NEXT:    i32 1, label [[DO_1:%.*]]
 ; CHECK-NEXT:    i32 2, label [[DO_2:%.*]]
 ; CHECK-NEXT:    i32 3, label [[DO_3:%.*]]
 ; 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]] ], [ 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()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       do_2:
 ; CHECK-NEXT:    call void @foo_02()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       do_3:

 do_3:
   call void @foo_03()
   ret i32 1
 
 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()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       do_2:
 ; CHECK-NEXT:    call void @foo_02()
 ; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       do_3: