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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Failure to recognise CTTZ pattern using CTLZ
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            good first issue,
            llvm:instcombine,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    While we correctly fold this hackers delight ctpop pattern into ctz:
```ll
define i4 @src_ctpop(i4 %a0) {
  %dec = add i4 %a0, -1
  %not = xor i4 %a0, -1
 %and = and i4 %dec, %not
  %clz = tail call i4 @llvm.ctpop.i4(i4 %and)
 ret i4 %clz
}
define i4 @tgt_ctpop(i4 %a0) {
  %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false)
  ret i4 %ctz
}
```
we fail to recognise the related clz pattern:
```ll
define i4 @src_lz(i4 %a0) {
  %dec = add i4 %a0, -1
  %not = xor i4 %a0, -1
  %and = and i4 %dec, %not
  %clz = tail call i4 @llvm.ctlz.i4(i4 %and, i1 false) ; undef = true is ok as well
  %ctz = sub i4 4, %clz
  ret i4 %ctz
}
define i4 @tgt_lz(i4 %a0) {
  %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false)
  ret i4 %ctz
}
```

Alive2: https://alive2.llvm.org/ce/z/AdPVa5
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8VEGPszYQ_TXmMkpkDIRw4MAmQqraQ9WuWum7VMYewF3Hjuxht8uvryDZTdNttz20n4SEsN-8efOesYzRDA6xZsUDK46JnGj0of7h2x_Nybuk8_q1_nk0FuEFQfkQUJF9hd5bDTSaCKNUTxgiaLRmGAkUnf0ZzpIIgwPjyIOimWUN4w3b8ctjLeONxt44BJMDy3kM6pe1lIn9siIKyZmogJUPjDewLGhUwLIjSK3hBjnAJn1DOE8r4jcf_gKxfDp9oXBvFBrVgrgUv_EoO68wksaCktZeRVr7fNquKrcmvwl1molqqQ1IV1pl52Xe8vjnOWmgf5pT0afdab5rvg5oUuiljXjV8UchdBPybj_jzQtCv_CTh4DKD85EBBoRAlpJqGHx4JrivwrPzv9fcv9ddHb-kNyde8CyB5icxv7CEiYEE8E_gYzwguvodyHFqVs65Fcll9z_LoAPJ-Ez077KMWC8aax5RsGyBkaic1zCFi0TrVzXt2s7HwYmWoVMtDMTbaO__0kWia4zXWWVTLBOy13Ki_0-2ydjrWWpxQ7FrtipKs2rTnPsuZJlmSvVaZ2YWnBRpFykacF5tt9muuyKct9lSld77CuWczxJY9-7JybGCet0l-fZLrGyQxvXK0uIwXsNvQmRYAUxIZg4MCGWWpY1xkVS_tQZd9s6mRhRb_yZzMnMkox3y15xTEK9lG26aYiL1yZSvIkgQ3a9Kb9xkQ5XzuIIrTR2Cnj_Mx0eH7-834NTNG6Aw-N3X5Ip2Pre6cHQOHVb5U9MtKvqy2tzDv5XVMREu04WmWivDjzX4vcAAAD__waxqvA">