JIT: Optimize range checks for a[i & C], a[i % c] and a[(i & c1)>>c2)] patterns#1644
JIT: Optimize range checks for a[i & C], a[i % c] and a[(i & c1)>>c2)] patterns#1644erozenfeld merged 11 commits intodotnet:masterfrom
Conversation
|
PTAL @dotnet/jit-contrib |
|
Will this work for a static span lifted to a local? Something like e.g. private static ReadOnlySpan<byte> s_hexEncodeMap => new byte[] { (byte)'0', (byte)'1', (byte)'2', (byte)'3', (byte)'4', (byte)'5', (byte)'6', (byte)'7', (byte)'8', (byte)'9', (byte)'A', (byte)'B', (byte)'C', (byte)'D', (byte)'E', (byte)'F' };
/// <summary>
/// A faster version of String.Concat(<paramref name="str"/>, <paramref name="separator"/>, <paramref name="number"/>.ToString("X8"))
/// </summary>
/// <param name="str"></param>
/// <param name="separator"></param>
/// <param name="number"></param>
/// <returns></returns>
public static string ConcatAsHexSuffix(string str, char separator, uint number)
{
var length = 1 + 8;
if (str != null)
{
length += str.Length;
}
return string.Create(length, (str, separator, number), (buffer, tuple) =>
{
var (tupleStr, tupleSeparator, tupleNumber) = tuple;
var hexEncodeMap = s_hexEncodeMap;
var i = 0;
if (tupleStr != null)
{
tupleStr.AsSpan().CopyTo(buffer);
i = tupleStr.Length;
}
var number = (int)tupleNumber;
buffer[i + 8] = (char)hexEncodeMap[number & 0xF];
buffer[i + 7] = (char)hexEncodeMap[(number >> 4) & 0xF];
buffer[i + 6] = (char)hexEncodeMap[(number >> 8) & 0xF];
buffer[i + 5] = (char)hexEncodeMap[(number >> 12) & 0xF];
buffer[i + 4] = (char)hexEncodeMap[(number >> 16) & 0xF];
buffer[i + 3] = (char)hexEncodeMap[(number >> 20) & 0xF];
buffer[i + 2] = (char)hexEncodeMap[(number >> 24) & 0xF];
buffer[i + 1] = (char)hexEncodeMap[(number >> 28) & 0xF];
buffer[i] = tupleSeparator;
});
}
|
|
@benaadams yeah should work (just checked - no range checks for |
|
Added PR then 😄 dotnet/aspnetcore#18406 |
|
How can you prove that the length of |
Its getter which is a look up into readonly data. Not sure it can be reassigned in anyway? |
|
Not sure that there is anything that guarantees it is read only. |
|
Its a method not a value; with the following il .method private hidebysig specialname static
valuetype [System.Private.CoreLib]System.ReadOnlySpan`1<uint8> get_s_hexEncodeMap () cil managed
{
// Method begins at RVA 0x2050
// Code size 13 (0xd)
.maxstack 8
IL_0000: ldsflda valuetype '<PrivateImplementationDetails>'/'__StaticArrayInitTypeSize=16' '<PrivateImplementationDetails>'::CE27CB141098FEB00714E758646BE3E99C185B71
IL_0005: ldc.i4.s 16
IL_0007: newobj instance void valuetype [System.Private.CoreLib]System.ReadOnlySpan`1<uint8>::.ctor(void*, int32)
IL_000c: ret
} |
|
Or following asm C.get_s_hexEncodeMap()
L0000: mov rax, 0x2d1c3a60844
L000a: mov [rcx], rax
L000d: mov dword [rcx+0x8], 0x10
L0014: mov rax, rcx
L0017: retSo the length is fixed at |
|
I see it is not an array but a [ReadOnly]Span which is a struct with a length field. |
|
And to get this optimization, the JIT probably has to inline: |
|
Not sure I understand, its the same pattern as in the summary of the PR static ReadOnlySpan<byte> span => new byte[] { 1,2,3,4 };
byte Case1(int i) => span[i & 2]; |
Well, jit already does that, see sharplab.io (thanks to Roslyn dotnet/roslyn#24621) |
|
Another improvement based on this change dotnet/aspnetcore#18450 |
|
@EgorBo, @dotnet/jit-contrib, what are the next steps for this PR? It's green, existing feedback appears to be addressed, and there's been no activity on it for a few weeks. Thanks. |
it's ready for review from my end. |
src/coreclr/tests/src/JIT/opt/AssertionPropagation/ArrBoundBinaryOp.cs
Outdated
Show resolved
Hide resolved
|
@dotnet/jit-contrib I think this can be merged. Anyone else wants to take a look at the final version? |
|
Thank you @EgorBo ! |
Optimize range checks for the following cases:
See asm diff for the snippet above ^.
This PR currently handles only
&, % and >>operators with constantop2and ignores actual range ofop1(always sets 0 as a lower limit andop2->IconValue()as an upper limit) to keep this PR simple and harmless.jit-diff:
The jit diff is quite small but there are few more places in the BCL where we can slightly tune and benefit from this opt, e.g.: here, also, see this comment. Also all
[x % c]patterns require cast touint.PS: range checks are not eliminated when CNS is negative