Optimization of array bounds checks involving bitwise AND could be improved #65550

Description

Currently optimization of array bounds checks involving a bitwise AND only seems to work when one operand is a constant, which limits the applicability, and leaves out an important use case of bitwise AND: the array[value & (array.Length - 1)] pattern. That pattern is safe (cannot index the array out-of-bounds) in almost all cases, even when the length of the array is not a power of two, the only bad case is when the array can have a length of zero.

In general for unsigned integers there is a relation a & b <= min(a, b). For signed integers we have some cases:

• If both a and b are known to be non-negative, the same relation as for unsigned integers holds.
• If a can be negative but b is non-negative, the relation becomes a & b <= b.
• If b can be negative but a is non-negative, the relation becomes a & b <= a.
• If both a and b can be negative, we don't really know anything.

Hacker's Delight chapter 4 "Arithmetic Bounds" discusses tighter bounds, but they only work on numeric ranges while the above also works for symbolic ranges.

There are also bounds for bitwise OR, for example if neither 2 * a nor 2 * b overflow, then a | b <= 2 * max(a, b), however I don't expect this to be very productive for the optimization of array bounds checks.

Regression?

Not a regression.

Example

Code such as this could have the array bounds check optimized away:

static int SumOfWrappedRange(int[] data, int from, int to)
{
    int res = 0;
    if (data.Length == 0)
        return res;
    for (int i = from; i < to; i++)
        res += data[i & (data.Length - 1)];
    return res;
}

Such code is clearly intended to work with a power-of-two array length, but it is safe (just nonsensical) even without assuming that the length is a power of two, so in theory the JIT compiler should be able to elide the array bounds check here.

Bonus

Whenever an array bounds check is optimized away, it should also be possible to optimize away the redundant sign-extension of the index, after all it is apparently known to be non-negative otherwise the array bounds check couldn't have been optimized away.

category:cq
theme:bounds-checks
skill-level:intermediate
cost:small
impact:small