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

    <tr>
        <th>Summary</th>
        <td>
            InstCombine introduces unnecessary `and 1` when folding `trunc nuw`+`zext`
        </td>
    </tr>

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

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

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

<pre>
    Rust in which we spotted this originally: <https://rust.godbolt.org/z/Knr5jdEY5>, cc https://github.com/rust-lang/rust/pull/139098#discussion_r2032140281

Take this input IR:
```llvm
define noundef range(i8 0, 14) i8 @match0(i8 noundef range(i8 0, 3) %0) unnamed_addr {
start:
  %1 = icmp eq i8 %0, 2
  %_2 = select i1 %1, i64 1, i64 0
  %2 = trunc nuw i64 %_2 to i1
  br i1 %2, label %bb2, label %bb3

bb2:                                              ; preds = %start
  br label %bb4

bb3:                                              ; preds = %start
  %b = trunc nuw i8 %0 to i1
  %3 = zext i1 %b to i8
  br label %bb4

bb4:                                              ; preds = %bb2, %bb3
  %_0.sroa.0.0 = phi i8 [ 13, %bb2 ], [ %3, %bb3 ]
  ret i8 %_0.sroa.0.0
}
```

Today <https://llvm.godbolt.org/z/vnfGGxfbr>, `--passes=instcombine` transforms that to
```llvm
source_filename = "/app/example.ll"

define noundef range(i8 0, 14) i8 @match0(i8 noundef range(i8 0, 3) %0) unnamed_addr {
  %1 = icmp eq i8 %0, 2
  br i1 %1, label %bb2, label %bb3

bb2:                                              ; preds = %start
  br label %bb4

bb3:                                              ; preds = %start
  %2 = and i8 %0, 1 ; 😢
  br label %bb4

bb4:                                              ; preds = %bb3, %bb2
  %_0.sroa.0.0 = phi i8 [ 13, %bb2 ], [ %2, %bb3 ]
  ret i8 %_0.sroa.0.0
}
```

However it should not be adding that `and i8 %0, 1` -- the `trunc nuw` means it ought to know it doesn't need to do that.

It should instead be emitting <https://alive2.llvm.org/ce/z/oN3dig>
```llvm
define noundef range(i8 0, 14) i8 @tgt(i8 noundef range(i8 0, 3) %0) unnamed_addr {
start:
  %1 = icmp eq i8 %0, 2
  br i1 %1, label %bb2, label %bb3

bb2:                                              ; preds = %start
  br label %bb4

bb3:                                              ; preds = %start
  br label %bb4

bb4:                                              ; preds = %bb3, %bb2
  %_0.sroa.0.0 = phi i8 [ 13, %bb2 ], [ %0, %bb3 ]
  ret i8 %_0.sroa.0.0
}
```

Note that the correctness for this doesn't depend on the range information; removing that from the parameter it still validates <https://alive2.llvm.org/ce/z/_ed2Ch>.

(If you run a full -O2 or -O3 then CVP will get rid of the `and`, but that's not run in -O1.  And InstCombine has the information it needs to do it correctly anyway, AFAICT, so it just should.)

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzkl0GP2zYThn8NfRnYoEjJlg4-eL1xvsUHJEUQFOhpQYkjiYlEqiRlx_n1BSnZ627SoMG2AdouFrBkvpx5OdYzFIVzqtGIW5Ldkex-IUbfGrt1lfG-r_pFaeR5-250HpSGU6uqFk4IbjDeowTfKgfGqkZp0XVnwndA-L71fnCE7wg7EHawo_OrxsjSdH5lbEPY4TNhh_9rm32Qr37JCH9F2B6qCn4_r1G-HctVZfo5yLITupmvCTsMY9cRdkh4QYucMC6Vq0bnlNGPllHOkpSyPCF0R-juvfiIk1mlh9HDw7uQhu7Imk7_XXfsCd1JrJVG0GbUEmuwQjdIWK5yoMFjkhJWgMqBpLQXvmrpNPhHeh7khGU0fI5aix7lo5DSAtncEbpzXlg_OYGgS4Dwe1BVPwD-GvPEuXtgF8UjixKHHVYeVBJnBYVap3C9oBf5pPZ21BXo8RQHpyjegEqirLRzHBamd6LELtyV5fN7PtUyDPAdfNcf4XcwWJQu-iEsm1Y-p7_JkV5y8L8yRwj9vBJTcW_qQFjGo-gzfrqUtozj-beMpi83Opf6WuTpl6YrZ41Y0RWNuqFV0XR2Bwm_yhmQ7D7eZXdxBU-B4kgIZtHPy72JGexv7m8RmEkxUpy_hDjw8RWIj7p-_fpTXdoZYrKmy-UgnENH-L3SzlemL5VGsqbgrdCuNrZ34FvhwZuvEOjMaCt8rFWHAZe5RIywgxgGwg74SfRDh6vAPpss_2Bo_wypV6aSfzNTU3cRWt4WIImTyIGS4kCKnOzY307PDQ4vo4e9lJ7_mRMe0YLy4FozdhK08VAiCCmVbqbnnqzp85oFPJZL8C2G0WuXCl_3KLQLAc3YtAEa-KjNKXwhDTpN2MaDxrAXG5AmZlhNZh6uJgKIKGQwgr3yPlj5AnHRqSOyVSR9IrzCGXPzhkvVBMZftGX6xv_Q_fI_QOE_Aiv6UqzeGI_zntEiVMZarLxG56A2dnqve4JB4oBagtFRHB8xUDrsO8Iro8NCLfbmeOWxtqaP2kFY0aOf-fWq6-AoOiWFR_ddvDyiZPuW8FcziYTlDzWczQh21CCgHrsOlm8ZGAvLtzwk17D_-Sc4hZwNerBKgqkvDUFoGWrB9lCOPpombONibwkBlYbl22QFsNMSHrTz-2nThVa4GOJm-WFpoV24uV8of6lndwahzydxDnl2h93D_n24clHzIZwApm6yIqwgdLeQWy4LXogFbpNNmiY8z9fpot1u-KYsihpLTKqCp1nNBeM0l5xVaVrkm4XaMsoymtI8KWhC0xXNUs4SUYsUkyLlgqQUe6G6a20XyrkRtwlPC5ov4gPv4oGFMY0niKPhdSC7X9htmLQsx8aRlHbKefcUxivf4fa2Qkp7a-RYoQv9Bit0TtjzpUXHvnwKP05tutjAn3Vnwu7ImoYXRrKmi9F222-cYWLDnD6WgzUfsArHmGjexYNMXN1xy34LAAD__7_Gt50">