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

    <tr>
        <th>Summary</th>
        <td>
            Simple bit manipulation resulting in disjoint set could be tracked
        </td>
    </tr>

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

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

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

<pre>
    I just saw this scenario in my real code (simplified):

```zig
export fn foo(s: u64) u64 {
    const iter = s & ~(s << 1);
    return iter | (iter << 1);
}
```

For your convenience, here is a C version:

```c
#include <stdint.h>

uint64_t foo(uint64_t s) {
    uint64_t iter = s & ~(s << 1);
    return iter | (iter << 1);
}
```

Currently gives this assembly:

```asm
foo:
        lea     rax, [rdi + rdi]
 andn    rax, rax, rdi
        lea     rcx, [rax + rax]
        or rax, rcx
        ret
```

I realized that there is an optimization here, we can turn the `|` into a `+`, because `iter` is necessarily disjoint with `iter << 1`. [Z3 agrees](https://alive2.llvm.org/ce/z/ALEMHA). That means we can get this emit:

```asm
foo:
        lea     rax, [rdi + rdi]
 andn    rax, rax, rdi
        lea     rax, [rax + 2*rax]
 ret
```


</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMVEGPqzYQ_jXmMnoRmITAgUPCPtQntadWPfRSGXsCs8_YkW2yyR762ysTkt28avfahxAj7JnPM983HuE99QaxZps92zwlYgqDdfWfQpMS7nvSWXWpv8Hz5AN48QJhIA9eohGOLJCB8QIOhQZpFQLjpafxqOlAqBivWL5j6RNLb98ivb6v1F9X8Hy0LsDBwMHaGM3yHUzFmvEqGmDb_dURAEBa4wNQQAcsfwIPjBfwT4wCljcsbyCbz3wX4jBMziwx2yYmuMT_159tn35I833urXVwsZOLWZzQEBqJjDcwoEMgDwIaOKHzZM1HVcvln-dkpJ4iX3njgyITVgPLv74PmsiEYv13WHi5__rIzAMr963_iZhmcg5N0Bfo6YT-2iHCexw7ffmICuHH60os7-YDy6NRzNaJc2SYbfZOETC-B6eIbZZkQBhl3rndjKIP0OQdTZyvaOL8hrY81t2B5Plxy2H4hIZv8zWgV1QQBhEg3BvDgD0GGulVBLJmbpiI_4IghYFZhjAgRLxtw4oUyAQLYl7g-_nbQIdSTH72ijrNbh4MSvReONIXUOSfLZkALxSGm9-bnkW6irX_lYPoHaKPlfNyCOEY7xzjLeOt0HRCvtL6NK6s6xlvY4-3r4y3u1-__vbLjvFqBX_E8kYUxt9q6DFcZceRws8kufhRcs747kH2z0VNVJ2rKq9EgnW25cW62mRZmQy1kJJnWVXyg1h3mG5LlW3zoitkysv1ZpMnVPOUr9MqK7J8U-blqitVVSmO1YFXMlMlW6c4CtJ3thPyfsI6S8uSV4kWHWo_T2XODb7AvMs4j0Pa1THoSzf1nq1TTT74N5hAQWP9exzDCB0FGIWh46Sv3efQTzqQ6ePsvreMxwDSTlpBhxCckN9RJZPT9WN_9BSGqVtJOzLexgMX8-Xo7DPKwHg7p-kZb5c6TjX_NwAA__-le82_">