RFR: 8335444: Generalize implementation of AndNode mul_ring

[Jasmine Karthikeyan]

On Mon, 8 Jul 2024 03:37:30 GMT, Jasmine Karthikeyan <jkarthikeyan at openjdk.org> wrote:

> Hi all,
> I've written this patch which improves type calculation for bitwise-and functions. Previously, the only cases that were considered were if one of the inputs to the node were a positive constant. I've generalized this behavior, as well as added a case to better estimate the result for arbitrary ranges. Since these are very common patterns to see, this can help propagate more precise types throughout the ideal graph for a large number of methods, making other optimizations and analyses stronger. I was interested in where this patch improves types, so I ran CTW for `java_base` and `java_base_2` and printed out the differences in this gist [here](https://gist.github.com/jaskarth/b45260d81ab621656f4a55cc51cf5292). While I don't think it's particularly complicated I've also added some discussion of the mathematics below, mostly because I thought it was interesting to work through :)
> 
> This patch passes tier1-3 testing on my linux x64 machine. Thoughts and reviews would be very appreciated!

The common cases I saw in java.base and other real world programs that aren't handled currently are with positive ranges, negative constants, and ranges that cross 0. For positive ranges it's possible to generalize the existing case with a positive constant, and for negative constants and ranges that cross 0 I came up with an estimation.

For a positive constant $C$, we can say that for any integer type $I$ that the result of the operation $`I \mathbin{&} C`$ will be bounded by the range $[0, C]$. This can then be generalized to positive ranges, as for any constant $c_{1}$ such that $0 \le c_{1} \le C$ the result of $`I \mathbin{&} c_{1}`$ will also be bounded by $[0, C]$. Therefore, we can say that $`I \mathbin{&} [c_{1}, C]`$ for any $0 \le c_{1} \le C$ will be in the range $[0, C]$. This case can be further generalized if we know both ranges are positive. For the operation $`[L_{1}, U_{1}] \mathbin{&} [L_{2}, U_{2}]`$ where $L_{1} \ge 0$ and $L_{2} \ge 0$ the result will be bounded by $`[0, \text{min}(U_{1}, U_{2})]`$. Since bitwise-and can only remove bits, we know that the maximum possible value of the result will be determined by the range that has fewer bits set.

In the case of negative constants and ranges that cross 0 it's more difficult to numerically derive a solution due to two's complement, as the minimum value can be lower than both of the ranges' minimum values. Since a negative two's complement number will always begin with a sequence of 1s, and that sequence of 1s grows smaller as the number becomes lower, the lower bound will be the number that contains the sequence of ones of the smaller value of both ranges. For the upper bound, the result will be the higher value of both ranges, as the result of bitwise-and with a negative value can return a result up to the positive value.

While these methods produce much more precise types for many cases, they are by no means optimal. For that I think proper bitwise propagation is needed, such as with #17508. However, I think this is still worthwhile to get in since it's an easy win for most cases and is a pretty simple patch.

-------------

PR Comment: https://git.openjdk.org/jdk/pull/20066#issuecomment-2212937509