Jit creates multiple zeroes in registers

@CarolEidt

This is a follow-up from #1007.

For this example

using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

public class C {
    [StructLayout(LayoutKind.Sequential, Size = 20)]
    public struct Buffer
    {
        public ulong Field1;
        public ulong Field2;
        public uint Field3;
    }
    
    public void M() {
        var buf = new Buffer();
        buf.Field1 = 2;
        
        DoSomethingWithMyType(buf);
    }
    
    [MethodImpl(MethodImplOptions.NoInlining)]
    public void DoSomethingWithMyType(Buffer buf)
    {
        // Do Something.. to prevent the JIT from optimizing it all awayyyy
    }
}

the jit generates the folllowing code:

G_M25775_IG01:
       4883EC38             sub      rsp, 56
G_M25775_IG02:
       33C9                 xor      rcx, rcx
       33C0                 xor      eax, eax
       BA02000000           mov      edx, 2
       4C8D442420           lea      r8, bword ptr [rsp+20H]
       498910               mov      qword ptr [r8], rdx
       49894808             mov      qword ptr [r8+8], rcx
       41894010             mov      dword ptr [r8+16], eax
       488D4C2420           lea      rcx, bword ptr [rsp+20H]
       E881A9FFFF           call     C:DoSomethingWithMyType(Buffer)
       90                   nop
G_M25775_IG03:
       4883C438             add      rsp, 56
       C3                   ret
; Total bytes of code 45, prolog size 4, PerfScore 12.00, (MethodHash=0c929b50) for method C:M()

Both rcx and rax are used to hold 0.

@CarolEidt's comment from #1007:
I believe there's a separate issue that occurs when the register allocator enregisters a promoted field that's being set to zero. If that field is then only used to copy to another field on the stack (or if it is spilled) we can wind up creating multiple zeros in registers.

There are a number of instances of these kinds of issues in the frameworks.
A couple to look at to see if they can be addressed by the same fix(es):

Microsoft.CodeAnalysis.VisualBasic.SyntaxFacts:BeginOfBlockStatementIfAny(Microsoft.CodeAnalysis.SyntaxNode):Microsoft.CodeAnalysis.SyntaxNode In Microsoft.CodeAnalysis.VisualBasic.dll. This has the "multiple copies of zero" problem (on x64, both Windows and Linux).

category:cq
theme:register-allocator
skill-level:expert
cost:medium

@dotnet/jit-contrib

@erozenfeld

@erozenfeld milestone? Future?

@CarolEidt

I think it can be Future unless @CarolEidt thinks we should try to fix this in .NET 5. I'm not sure how much register allocator work will be involved in fixing this.

This also comes up for HWIntrinsics and SIMDIntrinsics where multiple SIMD registers may hold "zero" at the same time.

Let's mark it as future. Does not preclude us from looking at it in .Net 5.

Agreed - I'm pretty sure that I wouldn't be able to get to this in the immediate future, and I suspect that the best near-term way to address this would be to see if we can get these addressed by extending the existing constant register support in the JIT to enable reuse of dead lclVar values.

Of course, I'd be happy to support/consult with someone who wanted to dive in to the register allocator and work on this (or figure out another good way to address it)!

This and #37216 should be analyzed to see whether they remain after work that was done for .NET 5 to eliminate redundant zeroing.

Where do we first create the zeroing pattern? Morph?

Yes

fgMorphInitBlock: using field by field initialization.
GenTreeNode creates assertion:
               [000018] -A----------              *  ASG       long  
In BB01 New Local Constant Assertion: V03 == 0 index=#01, mask=0000000000000001
GenTreeNode creates assertion:
               [000021] -A----------              *  ASG       long  
In BB01 New Local Constant Assertion: V04 == 0 index=#02, mask=0000000000000002
GenTreeNode creates assertion:
               [000025] -A----------              *  ASG       int   
In BB01 New Local Constant Assertion: V05 == 0 index=#03, mask=0000000000000004
fgMorphInitBlock (after):
               [000026] -A---+------              *  COMMA     void  
               [000022] -A----------              +--*  COMMA     void  
               [000018] -A----------              |  +--*  ASG       long  
               [000016] D------N----              |  |  +--*  LCL_VAR   long   V03 tmp1         
               [000017] ------------              |  |  \--*  CNS_INT   long   0
               [000021] -A----------              |  \--*  ASG       long  
               [000019] D------N----              |     +--*  LCL_VAR   long   V04 tmp2         
               [000020] ------------              |     \--*  CNS_INT   long   0
               [000025] -A----------              \--*  ASG       int   
               [000023] D------N----                 +--*  LCL_VAR   int    V05 tmp3         
               [000024] ------------                 \--*  CNS_INT   int    0

Seems like fgMorphPromoteLocalInitBlock could perhaps check and see if all assignments are integer types with a zero init pattern, and for intel 64 bit targets, just initialize a single zero temp of the longest size and use it for all cases.

For arm64 suspect we're already using the build-in zero reg?

Not as sure about 32 bit targets. What does the codegen look like on x86? Wondering if we end up zeroing 3 registers there...

I will try to come up with a fix as you suggested.

Thanks for asking me to check for other targets:

Arm64 - We do not use zero registers which is surprising. We still end up using 2 registers for 0.

G_M22067_IG01:              ;; offset=0000H
        A9BD7BFD          stp     fp, lr, [sp,#-48]!
        910003FD          mov     fp, sp
                                                ;; bbWeight=1    PerfScore 1.50
G_M22067_IG02:              ;; offset=0008H
        D2800001          mov     x1, #0
        52800002          mov     w2, #0
        D2800043          mov     x3, #2
        F9000FA3          str     x3, [fp,#24]
        F90013A1          str     x1, [fp,#32]
        B9002BA2          str     w2, [fp,#40]
        910063A1          add     x1, fp, #24   // [V06 tmp4]
        94000000          bl      C:DoSomethingWithMyType(Buffer):this
                                                ;; bbWeight=1    PerfScore 6.00
G_M22067_IG03:              ;; offset=0028H
        A8C37BFD          ldp     fp, lr, [sp],#48
        D65F03C0          ret     lr
                                                ;; bbWeight=1    PerfScore 2.00

For x86, I think we optimize the code because of the fact that we never use Buffer after the call.

G_M22067_IG01:              ;; offset=0000H
       55           push     ebp
       8BEC         mov      ebp, esp
       83EC08       sub      esp, 8
                                                ;; bbWeight=1    PerfScore 1.50
G_M22067_IG02:              ;; offset=0006H
       B802000000   mov      eax, 2
       33D2         xor      edx, edx
       8945F8       mov      dword ptr [ebp-08H], eax
       8955FC       mov      dword ptr [ebp-04H], edx
       8B45F8       mov      eax, dword ptr [ebp-08H]
       8B55FC       mov      edx, dword ptr [ebp-04H]
       6A00         push     0
       6A00         push     0
       6A00         push     0
       52           push     edx
       50           push     eax
       E86AFFFFFF   call     C:DoSomethingWithMyType(Buffer):this
                                                ;; bbWeight=1    PerfScore 10.50
G_M22067_IG03:              ;; offset=0026H
       8BE5         mov      esp, ebp
       5D           pop      ebp
       C3           ret

The surprising bits are from Linux/arm where we load/store multiple times to populate the struct fields.

G_M22067_IG01:              ;; offset=0000H
000000  B500           push    {lr}
000002  B08F           sub     sp, 60
                                                ;; bbWeight=1    PerfScore 2.00
G_M22067_IG02:              ;; offset=0004H
000004  2300           movs    r3, 0
000006  2200           movs    r2, 0
000008  930A           str     r3, [sp+0x28]
00000A  920B           str     r2, [sp+0x2c]
00000C  2202           movs    r2, 2
00000E  2100           movs    r1, 0
000010  920C           str     r2, [sp+0x30]
000012  910D           str     r1, [sp+0x34]
000014  9A0C           ldr     r2, [sp+0x30]
000016  990D           ldr     r1, [sp+0x34]
000018  9205           str     r2, [sp+0x14]
00001A  9106           str     r1, [sp+0x18]
00001C  9A0A           ldr     r2, [sp+0x28]
00001E  990B           ldr     r1, [sp+0x2c]
000020  9207           str     r2, [sp+0x1c]
000022  9108           str     r1, [sp+0x20]
000024  9309           str     r3, [sp+0x24]
000026  9907           ldr     r1, [sp+0x1c]
000028  9100           str     r1, [sp]
00002A  9908           ldr     r1, [sp+0x20]
00002C  9101           str     r1, [sp+0x04]
00002E  9909           ldr     r1, [sp+0x24]
000030  9102           str     r1, [sp+0x08]
000032  9A05           ldr     r2, [sp+0x14]
000034  9B06           ldr     r3, [sp+0x18]
000036  F246 51A0      movw    r1, 0x65a0
00003A  F6C0 2189      movt    r1, 0xa89
00003E  4788           blx     r1               // C:DoSomethingWithMyType(Buffer):this
                                                ;; bbWeight=1    PerfScore 28.00
G_M22067_IG03:              ;; offset=0040H
000040  B00F           add     sp, 60
000042  BD00           pop     {pc}

Seems like fgMorphPromoteLocalInitBlock could perhaps check and see if all assignments are integer types with a zero init pattern, and for intel 64 bit targets, just initialize a single zero temp of the longest size and use it for all cases.

I tried this approach, but constant propagation undo the work we do in morph and we end up with similar code.

***** BB01
STMT00000 (IL 0x000...0x003)
               [000033] -A---+------              *  COMMA     void  
               [000029] -A----------              +--*  COMMA     void  
               [000025] -A----------              |  +--*  COMMA     void  
               [000021] -A----------              |  |  +--*  ASG       long  
               [000020] D------N----              |  |  |  +--*  LCL_VAR   long   V06 tmp4         
               [000019] ------------              |  |  |  \--*  CNS_INT   long   0
               [000024] -A----------              |  |  \--*  ASG       long  
               [000022] D------N----              |  |     +--*  LCL_VAR   long   V03 tmp1         
               [000023] ------------              |  |     \--*  LCL_VAR   long   V06 tmp4         
               [000028] -A----------              |  \--*  ASG       long  
               [000026] D------N----              |     +--*  LCL_VAR   long   V04 tmp2         
               [000027] ------------              |     \--*  LCL_VAR   long   V06 tmp4         
               [000032] -A----------              \--*  ASG       int   
               [000030] D------N----                 +--*  LCL_VAR   int    V05 tmp3         
               [000031] ------------                 \--*  LCL_VAR   long   V06 tmp4  

------------
After constant propagation on [000027]:
STMT00000 (IL 0x000...0x003)
N013 ( 11, 11) [000033] -A----------              *  COMMA     void   $40
N009 (  6,  7) [000029] -A----------              +--*  COMMA     void   $c0
N005 (  1,  3) [000025] -A----------              |  +--*  COMMA     void   $140
N003 (  1,  3) [000021] -A------R---              |  |  +--*  ASG       long   $c0
N002 (  1,  1) [000020] D------N----              |  |  |  +--*  LCL_VAR   long   V06 tmp4         d:2 $c0
N001 (  1,  1) [000019] ------------              |  |  |  \--*  CNS_INT   long   0 $c0
N004 (  0,  0) [000024] ------------              |  |  \--*  NOP       void   $140
N008 (  5,  4) [000028] -A------R---              |  \--*  ASG       long   $c0
N007 (  3,  2) [000026] D------N----              |     +--*  LCL_VAR   long   V04 tmp2         d:2 $c0
               [000052] ------------              |     \--*  CNS_INT   long   0 $c0
N012 (  5,  4) [000032] -A------R---              \--*  ASG       int    $40
N011 (  3,  2) [000030] D------N----                 +--*  LCL_VAR   int    V05 tmp3         d:2 $40
N010 (  1,  1) [000031] ------------                 \--*  LCL_VAR   long   V06 tmp4         u:2 (last use) $c0

So I was trying to think of other mechanism through which we can capture such scenarios as well as the ones in #52286. The common pattern of these scenarios is constant propagation happens and we have multiple tree with structure like this:

STMT00001 (IL   ???...0x005)
N003 (  1,  3) [000007] -A------R---              *  ASG       long   $100
N002 (  1,  1) [000006] D------N----              +--*  LCL_VAR   long   V04 loc2         d:2 $100
N001 (  1,  1) [000005] ------------              \--*  CNS_INT   long   0 $100

***** BB01
STMT00002 (IL   ???...0x007)
N003 (  5,  4) [000010] -A------R---              *  ASG       long   $100
N002 (  3,  2) [000009] D------N----              +--*  LCL_VAR   long   V03 loc1         d:2 $100
N001 (  1,  1) [000008] ------------              \--*  CNS_INT   long   0 $100

Although it sounds great to propagate constant, but it is not always profitable (specially if the constant being propagated for assignment). It puts register pressure and generate inferior code as explained below:

During lowering, the above nodes are transformed into:

lowering store lcl var/field (after):
N001 (  1,  1) [000002] ------------         t2 =    CNS_INT   long   0 $100
                                                  /--*  t2     long   
N003 (  5,  4) [000004] DA----------              *  STORE_LCL_VAR long   V05 loc3         d:2

lowering store lcl var/field (before):
N001 (  1,  1) [000005] ------------         t5 =    CNS_INT   long   0 $100
                                                  /--*  t5     long   
N003 (  1,  3) [000007] DA----------              *  STORE_LCL_VAR long   V04 loc2         d:2

In register allocation, when we build intervals, we end up creating 3 ref positions for x = 0 operation.

The definition of constant value RefDef (t2 = CNS_INT long 0 )
The last use of constant value RefUse
The store of constant value into a variable RefDef.
Last 2 ref positions are created inside:

runtime/src/coreclr/jit/lsrabuild.cpp

Line 3327 in ce396bb

int LinearScan::BuildStoreLoc(GenTreeLclVarCommon* storeLoc)

When we allocate, we give a register say rdx to ref position #1 and #2 above. They are marked as holding a constant value. Since 2nd refposition was the last use of the constant, register rdx is technically available when we start the allocation of ref position #3. If that is the popular one, it gets assigned to ref position #3. When we do that, we unmark that rdx is holding a constant (although it still is). Thus rdx was a constant holding register whose constant got wiped off because it got allocated immediately to ref position #3.
Next, we try to allocate registers for second group of 3 refpositions:

We try to see if there is any register that contains a constant value and can be reused. Unfortunately, there is no such register and hence we allocate a different register to it, say rax.
Like the first group, we repeat same steps for 2nd and 3rd ref position and end up with different registers, all having zero value.

In a nutshell, here is allocating table looks like. #2, #3 and #4 forms the first group where we can see that rdx is assigned. #5, #6 and #7 forms the second group where rax is assigned.

---------------------------------+----+----+----+----+----+----+----+----+----+
LocRP# Name Type  Action    Reg  |rax |rcx |rdx |rbx |rbp |rsi |rdi |r8  |r9  |
---------------------------------+----+----+----+----+----+----+----+----+----+
                                 |    |V0 a|    |    |    |    |    |    |    |
 0.#0  V0   Parm   Keep     rcx  |    |V0 a|    |    |    |    |    |    |    |
 1.#1  BB1 PredBB0               |    |V0 a|    |    |    |    |    |    |    |
 6.#2  C5   Def    BSFIT(A) rdx  |    |V0 a|C5 a|    |    |    |    |    |    |
 7.#3  C5   Use *  Keep     rdx  |    |V0 a|C5 a|    |    |    |    |    |    |
 8.#4  V4   Def    COVRS(A) rdx  |    |V0 a|V4 a|    |    |    |    |    |    |
10.#5  C6   Def    ORDER(A) rax  |C6 a|V0 a|V4 a|    |    |    |    |    |    |
11.#6  C6   Use *  Keep     rax  |C6 a|V0 a|V4 a|    |    |    |    |    |    |
12.#7  V5   Def    COVRS(A) rax  |V5 a|V0 a|V4 a|    |    |    |    |    |    |

Here are few options that I explored and prototyped in past couple of days, but was not helpful (ignoring the facts that there were lot of asserts that I had to comment out)

Option1

What if, when assigning to ref position #4, we add an indicator saying "it holds constant value"? We can do that in

runtime/src/coreclr/jit/lsrabuild.cpp

Line 3446 in ce396bb

BuildStoreLocDef(storeLoc, varDsc, singleUseRef, 0);

if op1->IsCnsIntOrI(). Next, if the register rdx is getting assigned to such refpositions (like #4), do not clear the "constant value" flag. ("Constant value" flag tells that the register holds a constant value). Basically indicate that although rdx is being assigned to different non-constant interval, it still holds the constant value.
Next, when assigning to #5, we would get rdx back because it is still marked with "constant value". But when it gets assigned to the new interval of #5, make sure that we do not spill the value of #4 (that's what register allocator will do because it thinks that rdx was assigned to #4, but now since it is being assigned to #5, I need to store value of #4 on stack). And then reload the value. With that approach, I was able to get rdx being reused, but there were extra spills that got generated and I didn't debug. Also, there were lot of asserts on the way that I commented so was not sure if that was the right route to take.

This is in my private branch: https://github.com/kunalspathak/runtime/tree/const-prop-lsra

IN0001:        33D2                 xor      edx, edx
IN0002:        B802000000           mov      eax, 2
IN0003:        4889442420           mov      qword ptr [rsp+20H], rax
IN0004:        488B1424             mov      rdx, qword ptr [rsp]
IN0005:        4889542428           mov      qword ptr [rsp+28H], rdx
IN0006:        8B1424               mov      edx, dword ptr [rsp]
IN0007:        89542430             mov      dword ptr [rsp+30H], edx
IN0008:        488D542420           lea      rdx, bword ptr [rsp+20H]

Option2

After rdx is assigned to #2 and #3, somehow allocate different register rbx assigned to #4. That will make sure that rdx is still marked with having "constant value". However, with that, we will have to add an extra move to move the 0 value from rdx to rbx and might be worse.

  xor edx, edx
  mov ebx, edx

Thinking about these possible solutions in register allocation, I feel this is not a scenario that register allocator should/needs to handle. I believe the right phase to address this is somewhere earlier either in CSE, constant propagation, etc. I tried COMPlus_JitConstCSE=4, but that doesn't help. I think we need a phase that will reverse the constant propagation (at least for assignments) if there are more than X assignments of a constant C. So it should transform something like this:

T1 = 0
T2 = 0
T3 = 0

to

T1 = 0
T2 = T1
T3 = T1

What is the best phase to do this?

There is a concept in register allocation known as rematerialization: live ranges whose values can be cheaply recomputed. These live ranges never need spilling or home locations. Constants are the classic example.

So one model would be for us to aggressively CSE constants, and then during RA, mark the live ranges as rematerializable. Because these constants are "cheap to spill/reload" you could freely evict them from registers when you encounter pressure. So this opportunistic re-use gives you the same sort of "undo CSE" ability that you're referring to above, but it is based on RA knowledge so doesn't need to follow some simple heuristic like counting number of appearances or their weights or trying to guess when we have high pressure.

Not sure if this is what you are looking for...

Another approach I've seen used is to write a cheap/fast post-RA cleanup that just checks locally for constants and reuses them even if initially they weren't CSEd. This can often leverage "nearby" constant values to avoid rematerializing full literals, say if you have

t1 = 0x0000FFFF;
t2 = 0x00010000;

it might end up changing this to

t1 = 0x0000FFFF;
t2 = t1 + 1;

But it can't clean up bad spills, so likely you'd want to get the rematerialization in the RA working first.

Both options look like big work items, I guess they are out of 6.0 scope?

Maybe a part of option 2 can be done via something like "setOfConstRegs" and when we choose a free reg we first choose from "free & ~setOfConstReg"? We will create a bigger register pressure but only in cases where we still have free regs. Unfortunately, it could be a regression on x64 because reg encoding takes a different number of bytes, but maybe without #7996 it is currently random so the sum diff would be zero.

There is a concept in register allocation known as rematerialization: live ranges whose values can be cheaply recomputed. These live ranges never need spilling or home locations. Constants are the classic example.

I agree with Andy that we need rematerialization but I thought we have the necessary instruments to get it with a small tweaking, CSE already can do its part and + "cheap to spill/reload" sound like regOptional flag.

@AndyAyersMS

Thanks @AndyAyersMS and @sandreenko for the ideas. I skimmed through the rematerialization paper and sounds like a good idea. It is based on an initial pass where we annotate the information (terminology tags used in the paper) before hand so we can have enough information during allocation. As mentioned offline, I am thinking about similar pre-RA pass, not just for constants but also for better allocation in loops. I will try out some prototype to see how far I can go.

@sandreenko - We already have the concept of "setOfConstRegs":

runtime/src/coreclr/jit/lsra.h

Lines 1606 to 1619 in 127be4b

    
           regMaskTP m_RegistersWithConstants; 
        
           void clearConstantReg(regNumber reg, var_types regType) 
        
           { 
        
               m_RegistersWithConstants &= ~getRegMask(reg, regType); 
        
           } 
        
           void setConstantReg(regNumber reg, var_types regType) 
        
           { 
        
               m_RegistersWithConstants |= getRegMask(reg, regType); 
        
           } 
        
           bool isRegConstant(regNumber reg, var_types regType) 
        
           { 
        
               reg               = getRegForType(reg, regType); 
        
               regMaskTP regMask = getRegMask(reg, regType); 
        
               return (m_RegistersWithConstants & regMask) == regMask;

and we check it first during allocation before checking for any other heuristics.

runtime/src/coreclr/jit/lsra.cpp

Lines 3078 to 3086 in 7db5438

    
           if (freeCandidates != RBM_NONE) 
        
           { 
        
               if (currentInterval->isConstant && RefTypeIsDef(refPosition->refType)) 
        
               { 
        
                   matchingConstants = getMatchingConstants(selector.candidates, currentInterval, refPosition); 
        
                   found             = selector.applySelection(CONST_AVAILABLE, matchingConstants DEBUG_ARG(registerScore)); 
        
                   INTRACK_STATS_IF(found, updateLsraStat(STAT_CONST_AVAILABLE, refPosition->bbNum)); 
        
               } 
        
           }

However, while debugging this issue, I realized that sometimes the register that holds constant is marked as "busy" and we only check if any of the available regs have constant value or not. So, many times, we already filter out the register having constant value before checking if it exist in m_RegistersWithConstants. That might be something that need to be fixed and I tried fixing in my private branch I shared above.

I will mark this as "Future" for now.

Rematerialization related tracking issue - #6264

Navigation Menu

Repository navigation

Jit creates multiple zeroes in registers #37079

2 remaining items

Option1

Option2

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	regMaskTP m_RegistersWithConstants;
	void clearConstantReg(regNumber reg, var_types regType)
	{
	m_RegistersWithConstants &= ~getRegMask(reg, regType);
	}
	void setConstantReg(regNumber reg, var_types regType)
	{
	m_RegistersWithConstants \|= getRegMask(reg, regType);
	}
	bool isRegConstant(regNumber reg, var_types regType)
	{
	reg = getRegForType(reg, regType);
	regMaskTP regMask = getRegMask(reg, regType);
	return (m_RegistersWithConstants & regMask) == regMask;

	if (freeCandidates != RBM_NONE)
	{
	if (currentInterval->isConstant && RefTypeIsDef(refPosition->refType))
	{
	matchingConstants = getMatchingConstants(selector.candidates, currentInterval, refPosition);
	found = selector.applySelection(CONST_AVAILABLE, matchingConstants DEBUG_ARG(registerScore));
	INTRACK_STATS_IF(found, updateLsraStat(STAT_CONST_AVAILABLE, refPosition->bbNum));
	}
	}

Jit creates multiple zeroes in registers #37079

Description

Activity

erozenfeld commented on May 27, 2020

AndyAyersMS commented on May 27, 2020

erozenfeld commented on May 27, 2020

tannergooding commented on May 27, 2020

AndyAyersMS commented on Jun 1, 2020

CarolEidt commented on Jun 1, 2020

CarolEidt commented on Nov 10, 2020

2 remaining items

AndyAyersMS commented on Apr 9, 2021

kunalspathak commented on Apr 9, 2021

AndyAyersMS commented on Apr 9, 2021

kunalspathak commented on Apr 9, 2021

kunalspathak commented on May 11, 2021

kunalspathak commented on May 13, 2021

Option1

Option2

AndyAyersMS commented on May 13, 2021

sandreenko commented on May 14, 2021

kunalspathak commented on May 15, 2021

kunalspathak commented on Jul 21, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions