[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 #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

[antoniofrighetto]

@nikic Think handling this instead in foldSwitchToSelect would make sense too? Namely, drop restricting the inner vector in ResultVector size being one (and, possibly, completing the TODO):

llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp

Lines 6296 to 6311 in 18abc7e

	// Helper function that checks if it is possible to transform a switch with only
	// two cases (or two cases + default) that produces a result into a select.
	// TODO: Handle switches with more than 2 cases that map to the same result.
	static Value *foldSwitchToSelect(const SwitchCaseResultVectorTy &ResultVector,
	Constant *DefaultResult, Value *Condition,
	IRBuilder<> &Builder) {
	// If we are selecting between only two cases transform into a simple
	// select or a two-way select if default is possible.
	// Example:
	// switch (a) { %0 = icmp eq i32 %a, 10
	// case 10: return 42; %1 = select i1 %0, i32 42, i32 4
	// case 20: return 2; ----> %2 = icmp eq i32 %a, 20
	// default: return 4; %3 = select i1 %2, i32 2, i32 %1
	// }
	if (ResultVector.size() == 2 && ResultVector[0].second.size() == 1 &&
	ResultVector[1].second.size() == 1) {

For this, the resulting IR would look like:

define i64 @tgt(i32 %cmd) {
entry:
  %switch.selectcmp = icmp eq i32 %cmd, 13
  %switch.select = select i1 %switch.selectcmp, i64 0, i64 0
  %switch.selectcmp1 = icmp eq i32 %cmd, 1
  %switch.select2 = select i1 %switch.selectcmp1, i64 1, i64 %switch.select
  %switch.selectcmp2 = icmp eq i32 %cmd, 11
  %switch.select3 = select i1 %switch.selectcmp2, i64 1, i64 %switch.select2
  ret i64 %switch.select3
}

Only concern is that it might degenerate a bit here, perhaps would be more reasonable in simplifyDuplicateSwitchArms.

[antoniofrighetto]

Should be solved by d26df32, thanks for reporting.