Optimization of array bounds checks involving bitwise AND could be improved

IJzerbaard commented 2 years ago

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

dotnet-issue-labeler[bot] commented 2 years ago

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

ghost commented 2 years ago

Tagging subscribers to this area: @JulieLeeMSFT See info in area-owners.md if you want to be subscribed.

Issue Details

### 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.

Author:	IJzerbaard
Assignees:	-
Labels:	`area-CodeGen-coreclr`, `untriaged`
Milestone:	-

MichalPetryka commented 2 years ago

If you need a workaround, you can currently manually remove both the bounds check and sign extension by doing:

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 += Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(data), (nint)(uint)(i & (data.Length - 1)));
    return res;
}

JulieLeeMSFT commented 2 years ago

Moving this optimization to future since workaround is available. cc @dotnet/jit-contrib.

MineCake147E commented 9 months ago

A similar thing seems to apply to Span.Slice() with positive constant integer.

public static Span<byte> A(Span<byte> span)
{
    return span[..(span.Length & 0x7fff_fff0)];
}

sub rsp, 0x28
mov rax, [rdx]
mov edx, [rdx+8]
mov r8d, edx
and r8d, 0x7ffffff0
cmp r8d, edx
ja short L0028  ; unsigned comparison!
mov [rcx], rax
mov [rcx+8], r8d
mov rax, rcx
add rsp, 0x28
ret
mov rax, 0x7ff7f66aead8
call qword ptr [rax]
int3

Since Span.Slice() performs an unsigned comparison, the (uint)(Length & 0x7fff_fff0) <= (uint)Length should always be true as LLVM says,l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:49.10775875962996,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:clang_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-Ofast+-std%3Dc%2B%2B2c+-march%3Dsapphirerapids',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%231)',t:'0')),k:50.892241240370055,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4).

dotnet / runtime