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

    <tr>
        <th>Summary</th>
        <td>
            [ValueTracking] Missed optimization of modulo power-of-two
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          YanWQ-monad
      </td>
    </tr>
</table>

<pre>
    Recently I found a missed optimization related to modulo power-of-two. It's

https://github.com/dtcxzyw/llvm-opt-benchmark/blob/b79d63cb8adea5949cc449d4186e342d3dbdd871/bench/wasmtime-rs/optimized/1ham0fg2czw77e66.ll#L235

and it's compiled from [something](https://github.com/bytecodealliance/wasmtime/blob/a6f27eeb7e9ada3f1e10d75630f733b204e2c1ba/cranelift/codegen/meta/src/constant_hash.rs#L12-L42) like

``` rust
let modulo = if size.is_power_of_two() {  // i.e. ctpop(size) == 1
    size * 2
} else {
 size.next_power_of_two()
};

let result = xxx % modulo;
```

where `urem xxx, modulo` could be optimized to `and xxx, (modulo - 1)`.

To solve it, I have created a PR #91171 that enables the recognization of `.next_power_of_two()`, and I also have a draft patch that could recognize power-of-two from dom conditions.

However, the key problem in this case is that LLVM currently only search 2 levels beyond `phi` nodes, so the resursion of `isKnownToBeAPowerOfTwo` stops at `size * 2`, and fails to know `size` is a power-of-two from the condition.
https://github.com/llvm/llvm-project/blob/37ffbbb19576a884c5bb93b9ac0ae97f89523b6b/llvm/lib/Analysis/ValueTracking.cpp#L2197-L2199

Though changing `- 1` to `- 3` could make it work in this case, it's obviously not a proper way to solve the problem.

I am not sure if there is a way to handle this complex context across multiple basic blocks, or should we instead patch `wasmtime` to use `let modulo = (size + 1).next_power_of_two()`?

cc @nikic @dtcxzyw 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUVk1v4zYQ_TX0ZWBDor6sgw_JBkaDZtHtItiip4AfI4s1RQokFdn59QUlOXaKdIsCgSJLnHnzHt-MyLxXB4O4I8U9KR5WbAitdbs_mfnj93VnDZMrbuV59x0FmqDP8AiNHYwEBp3yHiXYPqhOvbGgrAGHmgWUECx0Vg7aQm9HdGvbrMNoN_AYCK08SR5Icjdf2xB6T7I7QveE7g8qtAPfCNsRupdBnN7OI6F7rV-7te3DmqMRbcfckdA915bHf1Uty0zwLZPIijqvhcjzWubptsQspzKTXMptlcalMZrQ_ch8F1SHa-cJ3S8EUBK6T1vWJc2BirexqrAsN1oTmj3RrLitmRkJamICwna90iihcbYDUtx722FolTmQ4oHQ7U_o8XNAYSUyrRUzAm8Ku7JjZUMrRF5hzSTLmhTTRFZFmSVNlWWcJjlSkXJG6F44ZlCrJsR7K_GAhtB9hyG-9E5Mj40PzISXlvl2E9lnTyldP-WU0Bq0OuItTVIm8x-4wYf5mcZw2VmSPYBqwKs33Cj_Mm30i21ewmgJ3caEpLoHmJmD2uAGROhtT-g2xkwLsoeYJZ1zA8CUDQi9A7rUUD0Aao8x17JqAjR4Cp9AvgeR7P6WSizboR90mMo-nU5AaLEwua69EL4NHVt0CKRMBoddjCT0yyWwTEDYQUvgCO82iuYnZRJNsqwmdLtotoY0Vlkmm1uIZwve6lecTPUFHqFlrwjC4dRLDL59B0KzOk2rFELLAqBhXKOH0CI4FPZgLg1om4j9r_KUSQSIpT0C097OSAykY02AngXRzggzrUtu_NDGs9el7UBYI1XE9R_4_GJHfEUXoWKFRzxD7yzX2IEyEFrlQTCPoPwM9vT04yuIwbl5xFijz-CROdECBY2vqD1wPFsjI7m-VVF4YyX6COHtooMfnL9qoPyvxo7m2d7j3bdY_W_N8zhtmQ-298BCXHXjt6s2DVPax208GjteVsVI5YF9IkWEf5di859zLU6zy1Drnf0LRbg2fFY1Dec8rYuqZNttLgrO64zXTCQM66rZ1gXNeMlv8qj4484wffYqDrQfTA_47Jg4KnPYiL6fRlhaV-t4rT84r7XDoQXRMnNQ5hC5RouWyWLiNWRXk3fsGC0Ko3XHDxsZdVvmoeWvyg5en8HYEMVytkcHIzvHjLPLo1yLHz7Y5hFYN4X5wWEcLWFqvUn0JUHLjNS4INuu13iKygc8BWDCWe-hG3RQvUbgzCsBXFtxnHxiHfh2IjIiKOMDMrlYnpTJ--iduQ9-6vl_jLtldAGh91Mj_6zPsv0tNyGA5IlRRzXdLJ82WMldJuusZivcpVValGWdJXTV7sQ2zRta1VtMmrRMZcKlLIqyKRFFWjbZSu1oQvOkSPOkzLeUbniV5kIKxkqsqiYXJE-wY0pvok021h1WyvsBdzVNqnylGUftp68-pQZHmF4SSuMhwO0mb_Lh4EmeaOWDv2YJKujpuPDBZqR4gK-fHAhs89lBYDU4vfvfHTKVGA0-Ufg7AAD__yZuyEw">