[SimplifyCFG] Missed optimization: merge switch branches into default if they hold the same value in phi as the default branch

[XChy]

Alive2 proof: https://alive2.llvm.org/ce/z/8U-LhB

Motivating example

define i64 @src(i32 %cmd) #0 {
entry:
  switch i32 %cmd, label %sw.default [
    i32 1, label %sw.bb2
    i32 11, label %sw.epilog
    i32 13, label %sw.bb1
    i32 0, label %sw.bb1
  ]

sw.bb1:                                         ; preds = %entry, %entry
  br label %sw.epilog

sw.bb2:                                         ; preds = %entry
  br label %sw.epilog

sw.default:                                    ; preds = %entry
  br label %sw.epilog

sw.epilog:                                     ; preds = %entry, %sw.default, %sw.bb2, %sw.bb1
  %ret = phi i64 [ 0, %sw.default ], [ 0, %sw.bb1 ], [ 1, %entry ], [ 1, %sw.bb2 ]
  ret i64 %ret
}

switch(13) and switch(0) produce the same %ret as default case:

define i64 @tgt(i32 %cmd) #0 {
entry:
  switch i32 %cmd, label %sw.epilog [
    i32 1, label %sw.bb2
    i32 11, label %sw.bb1
  ]

sw.bb1:                                         ; preds = %entry
  br label %sw.epilog

sw.bb2:                                         ; preds = %entry
  br label %sw.epilog

sw.epilog:                                     ; preds = %entry, %sw.bb2, %sw.bb1
  %ret = phi i64 [ 1, %sw.bb1 ], [ 1, %sw.bb2 ], [ 0, %entry ]
  ret i64 %ret
}

Real-world motivation

This snippet of IR is derived from openssl/crypto/bio/bss_conn.c@conn_ctrl (after O3 pipeline). The example above is a reduced version. If you're interested in the original suboptimal IR and optimal IR, see also:https://godbolt.org/z/nndaqfM9e

Let me know if you can confirm that it's an optimization opportunity, thanks.

[XChy]

For reference, GCC does optimize it as expected: https://godbolt.org/z/zEc9T14cf

[nikic]

Hm, I feel like I've seen a patch for something like this before. Maybe lost somewhere on phabricator...

[nikic]

This looks very related to the issue that https://github.com/llvm/llvm-project/pull/114262 addressed. This case is slightly different because the default branch doesn't go to a dedicated block, it goes directly to the phi. cc @michaelmaitland