Repository navigation
JIT: Generalized struct promotion #76928
Description
Description
Struct promotion (a.k.a. scalar replacement of aggregates) is an optimization that replaces structs with their constituent fields, allowing those fields to be optimized as if they were normal local variables. This is a very important optimization for low-level performance oriented code that makes heavy use of structs, so it is important that it is supported well by the JIT.
Limitations
The JIT supports promotion but with the following limitations today:
- Only whole structs with at most 4 fields can be promoted
- Nested structs are not supported, except when the nested struct is a wrapper around a primitive type
- A struct must be promoted for the full duration of the function or not at all
- Structs with overlapping fields are not supported
This issue is about removing (some of) these limitations.
Q1 work items
- Initial prototype (JIT: Add a (disabled) prototype for a generalized promotion pass #83388)
Q2 work items
- Add a few struct promotion related benchmarks performance#2991
- SPMI: Add possibility to specify custom options in diffs pipeline #84645
- Efficient decomposition for assignments
- JIT: Add a pass of liveness for the new locals inside physical promotion #86043
- JIT: Pick some low-hanging fruit in physical promotion throughput #86792
- JIT: Stop using ref counts in forward sub #85909
- JIT: Adjust physical promotion heuristics #86660
- JIT: Regularize readbacks for parameters/OSR-locals in physical promotion #87165
- JIT: Handle primitive remainder stores to regularly promoted fields in physical promotion #87217
- JIT: Reorder physical promotion and forward sub #87265
- JIT: Add support for induced field accesses in physical promotion #87410
- JIT: Induce more physical promotions #87810
- JIT: Cache significant segments computations for layouts in physical promotion #87745
- JIT: Insert readbacks eagerly in physical promotion #87809
- JIT: Insert writebacks more eagerly #87869
- JIT: Add a size component to the physical promotion heuristic #87969
- Rework JIT<->EE communication for struct promotion #87917
- Investigate regressions (see JIT: Enable physical promotion by default #88090 (comment))
- JIT: Enable physical promotion by default #88090
Future work items
CQ
- Decomposition via arithmetic
- Share backing storage when promoted locals are stack spilled
- Allow small-typed mismatches
- Support some bitcasts
- Partial lifetime promotion
- Move ABI info determination earlier so it can be utilized
- Store-forwarding for call args passed in registers
- Load-forwarding for calls
- Store-forwarding for structs returned in registers (JIT: Add a simple store-forwarding optimization for structs returned in registers #86388; punted due to low impact; existing promotion takes care of it)
- Custom class layouts with GC pointers (for some efficient decomposed copies)
- JIT: Handle liveness for defined retbufs in physical promotion #86711
- Readback/writeback resolution
- Full support for
GetElement/WithElementfor SIMDs - Assignment decomposition for
GetElement/WithElement(JIT: Generalized struct promotion #76928 (comment))
Throughput
- More efficient accesses data structure
- Stop tracking accesses early when we know we won't promote (e.g. due to overlapping accesses)
- JIT: Add some limits in physical promotion #87729
- JIT: Optimize aggregate info iteration in physical promotion #87997
Related issues
- Promote (scalar replace) structs with more than 4 fields #6534
- JIT: Slow spills to stack in a loop on Linux vs Windows #58522
- Regressions due to QJFL and OSR #67594 (comment)
- Span<T> wrapped in a struct isn't performing as fast as it could be #68797
- Poor performance/code-gen with struct enumerators, especially when containing ReadOnlySpan #71510
- Poor codegen for "big" (> 4 fields) structs init #71565
- JIT: suboptimal generated code for struct overlapped field manipulation #69254
- Jit: Sub-optimal code when function is inlined #32415
- Recursive Promotion of structs containing fields of structs with a single pointer-sized field #7576
- RyuJIT x86: allow long-typed struct fields to be recursively promoted #6707
- Unused struct fields sometimes improve the codegen #79928
Activity
jakobbotsch commentedon Oct 12, 2022
cc @dotnet/jit-contrib
jakobbotsch commentedon Feb 22, 2023
The kinds of struct locals we can promote appear only as operands of
GT_ASG,GT_CALLandGT_RETURN, ForGT_ASGwe should be able to decompose directly as part of the generalized promotion pass. That leavesGT_CALLandGT_RETURN.My thinking for a while was to introduce a new node that represented the assembling of a local and its constituent fields, similar to
GT_FIELD_LIST. However, it would need an equivalent to appear on the LHS of assignments from calls, and of course downstream passes would need to be taught to handle this. Also, they would only be necessary on platforms with multi-reg args/returns.After thinking some more I've come back to another idea which I think I will investigate. Instead of introducing a new node in HIR that persists until lowering, we introduce the equivalent of
GT_PUTARG_REGforGT_CALLresults andGT_RETURN. That is, we would add nodesGT_GETRES_REGthat represents using one of the register results of aGT_CALLnode, and aGT_PUTRET_REGthat represents placing a value into one of the return registers. LSRA would get similar handling for these nodes as it has forGT_PUTARG_REGtoday (essentially that these registers are busy until they are used (for call)/or until aGT_RETURNis encountered).For the generalized struct promotion pass we would then only introduce new assignments: to pass one of these struct locals to a call, or to return one of them, it will just write all the constituent fields back into the struct local and leave the local in the call argument/
GT_RETURN.A priori this would just amount to a lot of unnecessary copying in the generated code. To get to an acceptable state, we would introduce an optimization in lowering to handle these patterns without copying. For example, after generalized struct promotion + rationalization, we would have LIR like:
we would do some analysis to figure out whether
V00is dead after this call (potentially even more precisely whetherV00 [0..8)/V00 [8..16)are dead). If yes, then we would transform this intoSimilarly for call results, e.g. we would get LIR like the following for generalized promotion after rationalization:
and, as an optimization, lower it into:
Some questions to investigate:
FIELD_LISTtransformation we do for our normal promotion)tannergooding commentedon Feb 22, 2023
What about for
GT_HWINTRINSIC, particularly in the case of things likestruct M2x4 { Vector4 X; Vector4 Y; }or similar?Same for cases like
GT_INTRINSICwhich were originally calls and which may become calls again in some cases (e.g.Math.Powif constant folding can't happen).jakobbotsch commentedon Feb 22, 2023
What particular intrinsics take arbitrary struct arguments? Can they be decomposed early like
ASGwould be?SingleAccretion commentedon Feb 22, 2023
There is #80297, where we are handling an intrinsic that essentially has a "multi-reg arg" via early decomposition into a
FIELD_LIST.tannergooding commentedon Feb 22, 2023
Single beat me to it, that was the example I was going to give 😄
jakobbotsch commentedon Feb 22, 2023
I don't see why the existing approach there wouldn't continue to work. The representation for call args here could also be
GT_FIELD_LISTbut it would require very early ABI handling for the struct args that I am not a fan of.jakobbotsch commentedon Feb 22, 2023
A similar node would be needed for parameters. Generalized promotion would create IR in the start of functions to load (parts of) parameters into the promoted field locals and lowering would optimize these into some
GT_GETPARAM_REGnode when possible. Then likely we would use the same source of liveness when homing parameters to figure out if we can avoid homing some of the struct parameter.JIT: Add a (disabled) prototype for a generalized promotion pass (#83388
4 remaining items
jakobbotsch commentedon Jun 8, 2023
(edit: not expected to be handled)
+16 (+21.33%) : 21081.dasm - System.Numerics.Tests.Perf_Matrix3x2:IsIdentityBenchmark():bool:this
Replacements:
Physical promotion means we replace a
LCL_FLDwithLCL_VAR. VN proves these to be a vector constant, but CSE does not kick in anymore due to the LCL_VAR, and then constant prop ends up creating some more copies of the vector constant. I think the issue is essentially #70182 as LSRA could probably realize and reuse the existing register that already contains the constant.jakobbotsch commentedon Jun 8, 2023
(edit: tracked by #87554)
+18 (+21.95%) : 17866.dasm - System.Numerics.Tests.Perf_Matrix3x2:GetDeterminantBenchmark():float:this
Replacements:
We end up creating IR that DNERs V04:
This is missing
GetElement/WithElementhandling that local morph has. With that handling I think we would end up with:Hacking this in we end up folding the entire benchmark to a constant:
jakobbotsch commentedon Jun 8, 2023
(edit: not expected to be handled)
+44 (+27.67%) : 1550.dasm - System.Text.Json.Utf8JsonReader:get_CurrentState():System.Text.Json.JsonReaderState:this
Replacements:
This is one of the cases where the heuristic does not take into account that decomposed assignments can be more expensive with many fields, especially considering we end spilling some of the fields. We end up with
to handle the assignment into the ret buffer. We do see some signs of why it could be beneficial to do the promotion as we are able to keep a bunch of the fields in registers instead of on stack, but we just don't have enough registers on x64 to do that for them all.
jakobbotsch commentedon Jun 15, 2023
With the perflab runs @cincuranet set up and a query from @AndyAyersMS I can start looking at micro benchmark regressions. The following lists all benchmarks with a ratio below 0.95, indicating that they regress by more than 5%. There are 56 entries in this list (for comparison, the query for benchmarks that improve by more than 5% returns 267 results, but take it with a grain of salt as many of these are noisy). The quality columns are computed as median divided by standard deviation, so larger numbers indicate more stable benchmarks.
MicroBenchmarks.Serializers.Xml_ToStream<MyEventsListerViewModel>.XmlSerializer_System.Memory.Constructors<Byte>.ArrayAsMemorySystem.Memory.Constructors<String>.MemoryMarshalCreateSpanSystem.Memory.Constructors<String>.MemoryMarshalCreateReadOnlySpanSystem.Collections.ContainsFalse<Int32>.Span(Size: 512)System.Collections.TryGetValueTrue<Int32, Int32>.Dictionary(Size: 512)System.Collections.ContainsKeyTrue<Int32, Int32>.Dictionary(Size: 512)System.Memory.Span<Byte>.Clear(Size: 512)System.Collections.CtorDefaultSize<String>.StackSystem.Buffers.Tests.ReadOnlySequenceTests<Byte>.FirstSingleSegmentSystem.Memory.ReadOnlySequence.Slice_Repeat_StartPosition_And_EndPosition(Segment: Multiple)jakobbotsch commentedon Jun 16, 2023
System.Numerics.Tests.Perf_Matrix4x4.IsIdentityBenchmark
Same as #76928 (comment):
jakobbotsch commentedon Jun 16, 2023
System.Numerics.Tests.Perf_Matrix3x2.SubtractBenchmark
Looks like physical promotion ends up with slightly different pipelining, which seems worse in the lab (however on my laptop Intel CPU, it seems to be sometimes faster than the original).
The codegen for this benchmark is terrible with and without physical promotion. The problem is around
V09that we end up address exposing -- the JIT is not able to see through theAsImpl()calls with full fidelity. If we changeAsImplto return by value instead of by ref then the problem is solved and the benchmark reduces to a vector constant. At the same time we can switch toUnsafe.BitCast. Does that seem reasonable @tannergooding ?System.Numerics.Tests.Perf_Matrix3x2.AddOperatorBenchmark,System.Numerics.Tests.Perf_Matrix3x2.SubtractOperatorBenchmark,System.Numerics.Tests.Perf_Matrix3x2.AddBenchmarkandSystem.Numerics.Tests.Perf_Matrix3x2.SubtractBenchmarkare all affected similarly.jakobbotsch commentedon Jun 16, 2023
System.Numerics.Tests.Perf_Matrix3x2.MultiplyByMatrixBenchmark
We need some more registers and also see the same kind of pipelining change as in the previous comment, but in addition we also DNER
V08due to #87554.System.Numerics.Tests.Perf_Matrix3x2.MultiplyByMatrixOperatorBenchmarkis similarly affected.jakobbotsch commentedon Jun 19, 2023
Promoting
TYP_SIMD32andTYP_SIMD64fields can be very expensive if we end up creating long lifetimes that span across calls where the upper halves need to be saved/restored. For example: https://gist.github.com/jakobbotsch/e09b0e75ecfac6934ae51c8902748491The pass does not currently have the necessary information to try to take this into account, so need to think about what to do here.
jakobbotsch commentedon Jun 21, 2023
Looking at this perfscore regression:
306966.04 ( 0.29% of base) : 53160.dasm - Benchmarks.SIMD.RayTracer.RayTracer:RenderSequential(Benchmarks.SIMD.RayTracer.Scene,int[]):this
This is a case where our lack of handling for call args shows up. We end up with an extra struct copy in
G_M31648_IG15because physical promotion inserts a writeback into the struct local, and then call args morphing creates a copy of it since it isn't a last use.One simple fix in physical promotion for the implicit byref case would be to create a new local to ensure that it is a last use; we can then handle it by our smarter decomposition. That might be a good short-term solution with large benefit.
There is also a redundant
leainstruction inG_M31648_IG18; we are not able to peel the address because it is aFIELD_ADDRnode. Also, the copy itself needs to usevextractpssince it isTYP_SIMD12.JIT: Enable physical promotion by default (#88090)