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

    <tr>
        <th>Summary</th>
        <td>
            [JumpThreading][SimplifyCFG] Missing optimization : thread through BB based on known condition on edge
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </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/VvFox-

### Description:
For example:

```llvm
define i1 @src(i1 noundef %c) {
entry:
  br i1 %c, label %then, label %land.lhs.true

land.lhs.true:
  %c1 = tail call noundef i1 @cond() #2
  br label %then

then:
  %tobool = phi i1 [ false, %entry ], [ %c1, %land.lhs.true ]
  %or.cond = or i1 %c, %tobool
  ret i1 %or.cond
}
```

When `%c` is true, we will go into BB `%then` and then `%tobool` must be false. Therefore we can infer that `%or.cond` is true when `%c` is true. With this fact, we could directly thread the true branch of `%entry` to return true. Like:

```llvm
define i1 @tgt(i1 noundef %c) {
entry:
  br i1 %c, label %else, label  %land.lhs.true

land.lhs.true:
  %c1 = tail call noundef i1 @cond() #2
  br label %then

then:
  ret i1 %c1

else:
  ret i1 1
}
```

### Real-world motivation

This snippet of IR is derived from [redis/src/expire.c@expireSlaveKeys](https://github.com/redis/redis/blob/d8a21c5767b29d53e72c4f52c00c6bd15d8648ec/src/expire.c#L380C1-L380C1) (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/Gdbba3Eve

**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/eJzMVV2P6yYQ_TXkZbSWjT-SPORhs6mvbrtVpXtXvX3FMLbpYrAAZzf311dg56tbVa3Uh0pWCDAczgxnZphzstOIO1LuSXlYscn3xu5-e-pPq8aI0-5RySNSGK0xLckfofd-dCR_JLQmtGZxN1HqOCTGdoTWHAmtvxNa_3qszfsDSQ8kfVx-aT5_cEDHrRy9NDpAxd3aWMB3NowKL2vLb5XOX7hmXhLYSo0gMyBF6iwndCMz0GbSAlsgtOSEboGs97M5am9PF1SAxsaj0ewJFGtQhZnvUd8tKKZFonqXeDvhLaX7jStwgMyA5AfwTCrgTKkLq5ksN1oQuon0aE5vGN3TuLkszu_u8KYxRsV7xl5G5HIPLVMOA39Cy-gxkPIQ5-V-ZrZs3rGPRldoY5NAMWKbuzBd7j1bW_TL_nJoIb0-_Ondbp351qOGsBZQqxSkgxhD-gRvCG9SKegMSO0N7PeLYQxAlQLTAvz1_MKmSmGYnIcG5wgk8NKjxdZYDJCcaZC6RQu-Z345eiZ8JQBvf00sgW_S9-B76aBl3C9EuZmUACEtcq9O4HuLLJKbwRrLNO_BtAviLMAqBW9C2CarF_Bn-fpv5e47_9_IHRe5zAv_W71fZcazW7NI_4NZ9k9EeK1EX5CphzdjlYDBeHlksSbdmL6Eh3dajiP68J6fvwRlCLTyiAJaa4aQXhaFdITWsRTV-D5KiwknRTr__arYEX_Ck4sJubmvoZ30_dQk3AyE1meg89go0xBaiw2jGS_X1bqhW1HmuKa8aEvK05RXjchKsamKDfKPFGj-nG_Sp-xhHuZ32LDWo4VfchjliEpqJHSbnB3Gcx0G1pgjBn8ZWBQTRwFHtE4ancDnFk5mInRtMaQrWnQeBUgds8BY2UnNFLipMaOXA1MhdCGDr9MgPocITDnzsbd0RjRG-aWvhJbySTQNy3844v1bhu8ZPQwIr9q8gYzMYuJzo1tphzn1pSd07YDpmYL8Hh8bzDga6yct_SkQ8j3Try6ZYVdil4ttvmUr3GXrlFbZtiqLVb_jImuZqDCrMM9ybJEX2yrPt2m2KfJNgSu5oynNM5qVaVkWWZE0rME2zYuGV5u2wjKIY2BSXZrnSjo34W5dllW6isnhzl3Z7oLRQzN1jhSpks676zEvvYr9-8dpGF9iIZK6C0or91_lMCrZnp7qT6Q8wM_SOam7e_9D5C_1y5qp60PlbZhDAUbHkMZACjmHSwOKDleTVbu_EXIsXvPwMFrzO4bSWUcXg66jl38EAAD__xPbiWY">