RyuJIT: Index Variable Widening optimization for array accesses

[sivarv]

There are many benchstone benchmarks that would benefit from IV widening, which currently Legacy Jit64 does.

From benchmarkgames Mandelbrot and Nbody are such examples.

category:cq
theme:loop-opt
skill-level:expert
cost:large

[JosephTremoulet]

Copying over @mikedn's comment from dup dotnet/coreclr#11608:

An alternative solution for array indices might be to change signed casts to unsigned casts, I once tried that in dotnet/coreclr#8821 and it does improve performance in some cases. That approach unfortunately produced some regressions but there may be a way to do this cheaply in assertion propagation.

[mikedn]

there may be a way to do this cheaply in assertion propagation

It is possible to have optAssertionProp_Cast check for OAK_NO_THROW assertions, they imply that the index is positive and thus a signed cast can be turned into an unsigned cast. That means that instead of movsxd instruction we end up generating a shorter and 0 latency mov instruction. Saves about 7K in jit-diff fx and a tiny loop I tested with becomes 50% faster.

Unfortunately this fails to work in the common case - for (int i = 0; i < a.Length; i++) ... a[i] .... Such loops are handled by loop cloning which runs before assertion propagation and removes the range check.

[JosephTremoulet]

I wonder if it would be worth having an operator like GT_ASSUME to feed info to assertion prop (and that would get removed by rationalize or something); then loop cloning could leave an assume in place of the removed bounds check.

[mikedn]

We could probably have loop cloning preserve the range check and set GTF_ARR_BOUND_INBND so it is removed at a later time. But that may mean that assertion prop will do more work because it encounters more range checks.

I'll have to check if there other assertion kinds that can be used for this, loop cloning conditions should generate some.

There's also the question if loop cloning should be done so early, seems strange to me.

[mikedn]

I'll have to check if there other assertion kinds that can be used for this, loop cloning conditions should generate some.

I'm dumb, in the common case there will be no loop cloning conditions. There are probably only two ways to get this trick to work after loop cloning:

• keep the range checks (or replace them with something like GT_ASSUME)
• have RangeCheck do the cast conversion from signed to unsigned - probably too expensive to be worth it

[pentp]

There's some related discussion also here: dotnet/coreclr#21553. In summary, instead of/in addition to simply widening:

• Array/Span access is always bounds checked, so the induction variable is guaranteed to be non-negative and instead of movsxd could use just mov.
• Ideally, could take advantage of the x64 (and arm64) 32 bit instruction semantics that implicitly zero the upper bits which would eliminate all of the existing sign-extension overhead and potential instruction size overhead from induction variable widening (but introduce some new overhead in loop header in some cases to guarantee that upper 32bits are zero).

[pentp]

The expected benefits are somewhat reduced since #57970 removed movsxd uses.
Blindly widening the index variable (e.g., during importation) would probably actually reduce perf because the length comparison would need widening also then.

If we know that the index variable is 32-bit, could we just elide the zero-extension (cast) entirely because any time we load it to a register (or increment/modify it) it will be implicitly zero-extended anyway? Only situation that would need special handling then is if the index is from a narrowing cast - this should do an actual mov then...

[jakobbotsch]

Fixed by #97865