<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/83417>83417</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [SimplifyCFG] Missed optimization: simplify if-else BBs that share common destinations
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          XChy
      </td>
    </tr>
</table>

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/Q3dd5y

### Motivating example 

```llvm
define void @src(i1 %c1, i1 %c2) {
entry:
  br i1 %c1, label %then, label %else

then:
  br i1 %c2, label %bb1, label %bb2
  
else:
  br i1 %c2, label %bb2, label %bb1

bb1:
 call void @dummy1()
  ret void
bb2:
  call void @dummy2()
  ret void
}
```
can be folded to
```llvm
define void @tgt(i1 %c1, i1 %c2) {
entry:
  %xor = xor i1 %c1, %c2
  br i1 %xor, label %bb2, label %bb1

bb1:
  call void @dummy1()
  ret void
bb2:
 call void @dummy2()
  ret void
}
```
Here both `then` and `else` are trivial basicblocks with only a conditional branch inst, but I think it's possible to generalize it, 
like replacing the condition of one of branch inst with `%c3`: https://alive2.llvm.org/ce/z/Xw9Ms2.

### Real-world motivation

This snippet of IR is derived from [z3/src/sat/tactic/goal2sat.cpp@convert_iff](https://github.com/Z3Prover/z3/blob/2880ea39719971226e616d1077788288d6107632/src/sat/tactic/goal2sat.cpp#L626) (after O3 pipeline).
The example above is a reduced version. Original IR comes from https://github.com/dtcxzyw/llvm-opt-benchmark/blob/main/bench/z3/original/goal2sat.cpp.ll, if you want optimal one, please email me please.

**Let me know if you can confirm that it's an optimization opportunity, thanks.**
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJysVU1v4zYT_jX0ZRBDGllfBx-SGHrfBXaxbdrDopeCkkbW1BQpkLQd59cXlOzEyS6CdFuAMD0aztczD4fSOd5qorVI70S6Wci9741df7vvT4vatKf1reIDIYzWmE4kt9B7PzqR3AqsBFZy0i6VOgxLY7cCq4YEVk8Cq1-Ttk1PItqI6Pb8i8m84IvxfJCe9RboUQ6jInh1MIvmFfzOn1rqWBMcDLcgVpGzjcCCYxCYNrHAezj_R4EliPxutiLt7SkkO0kAtYVrGyVrUkH0PelXH0g5us5oOvAjP_jKrK7jNzJeTM4JBb8f8fO936tsgvjspJFKPePS7ofhFAssBJaXIJb8pL_Y4lUC3xvje8Yi37zp0Cw2UkNN0BnVUgvefLSNfut_po0C00djQSQbCPu1_Wz8Ft5HY38a338F8H-E7__JEtTG9yCyaOJiFoHUbRAnSgXREnjLB5YKaum4qZVpdg6O7HswWp1AQmN0y56NDmes1E0PrJ0PWNR7D5_A96x3wF5g7mA0znGtCLyBLWmyUvETTdr7M58V7wgsjUo24TL7nl5igOnAaArbVaw5n1AZpk0S9n8yVL4dyy8Olz-eKg8k1c3RWNXCcB4wRl8f_b1nB07zOJIPaX16AHbQkuUDtdBZM4BI754SgdU0YConvcDKy8ZzELdGKnTSL5txFKuoMfpA1v_JXSfSjcDidRlb9v2-XjZmEFj9kfxizYFsqCP4r5WpBVZYFBHJpMzjssxjxIyyOGvjKM_zosCiaLM4yrMEP5QRJp8zzKabg4XsPFn4msDIIynWJLBcXmCg57Era3OggIIES-2-oRYOZB0bvYSvlrccqPLpARozkJsheqfK1jePT6ejwCo078aM_qYm3fSDtLuXogfJOkhBc8HDnGO9qWmp1DQVOjiZPRyl9mBGz4NUgVpBNSqSjoAGyQoGOstvGBLWZ_JBv9PmePEXxlZjdMd2AN9LfyG-1HMUfpIzkcfRWL_X7E8hpO-l3rnl7HbRrpO2TEq5oHWcRyVG5SrBRb8uU0rbrCmLMsooSrtuJSlOKMc6xlpGuOA1RriKEMsYMUnyZRetoriMEplmdSETFKtoKuv5JizYuT2ti2QV54tpeLnp3UbUdIRJKRDDM27XUwPq_daJVaTYeffixbNX04P_Gw-j4u50X_1PpBv4ws5R-6r0cDnd-RRwdxOGDdzduRku14eh05hhMBpacp71ZOUWe6vW7_BkehDOJBmt-YuawOqpACewmgr8OwAA__9ZHpL2">