Variable not promoted to register due to unrelated pointer assignment

[damageboy]

I've chased the exact cause for this issue for a long long time, and I finally managed to narrow it down to a reproducible issue.

Environment

I'm using .NET 5.0 preview 3:

dotnet --info                                        
.NET Core SDK (reflecting any global.json):
 Version:   5.0.100-preview.3.20216.6
 Commit:    9f62a32109

Runtime Environment:
 OS Name:     clear-linux-os
 OS Version:  32910
 OS Platform: Linux
 RID:         linux-x64
 Base Path:   /home/dmg/dotnet/sdk/5.0.100-preview.3.20216.6/

Host (useful for support):
  Version: 5.0.0-preview.3.20214.6
  Commit:  b037784658

.NET SDKs installed:
  3.1.101 [/home/dmg/dotnet/sdk]
  3.1.102 [/home/dmg/dotnet/sdk]
  3.1.201 [/home/dmg/dotnet/sdk]
  5.0.100-preview.3.20216.6 [/home/dmg/dotnet/sdk]

.NET runtimes installed:
  Microsoft.AspNetCore.App 3.1.1 [/home/dmg/dotnet/shared/Microsoft.AspNetCore.App]
  Microsoft.AspNetCore.App 3.1.2 [/home/dmg/dotnet/shared/Microsoft.AspNetCore.App]
  Microsoft.AspNetCore.App 3.1.3 [/home/dmg/dotnet/shared/Microsoft.AspNetCore.App]
  Microsoft.AspNetCore.App 5.0.0-preview.3.20215.14 [/home/dmg/dotnet/shared/Microsoft.AspNetCore.App]
  Microsoft.NETCore.App 3.1.1 [/home/dmg/dotnet/shared/Microsoft.NETCore.App]
  Microsoft.NETCore.App 3.1.2 [/home/dmg/dotnet/shared/Microsoft.NETCore.App]
  Microsoft.NETCore.App 3.1.3 [/home/dmg/dotnet/shared/Microsoft.NETCore.App]
  Microsoft.NETCore.App 5.0.0-preview.3.20214.6 [/home/dmg/dotnet/shared/Microsoft.NETCore.App]

To install additional .NET runtimes or SDKs:
  https://aka.ms/dotnet-download

Buggy JIT behavior

The issue can be clearly seen when comparing the generated ASM between this buggy version:

Where in this order of variable declarations:

                var tmpLeft = _tempStart;
                var tmpRight = _tempEnd - N;
                var writeLeft = left;
                var writeRight = right - N - 1;


                var pBase = Int32PermTables.IntPermTablePtr;

Where the writeRight variable is declared before the pBase pointer is initialized, leads to the JIT incorrectly deciding to NOT promote writeRight into a register, later within the function:

M08_L00:
       mov       rcx,rsi
       sub       rcx,rax
       mov       r8,rcx
       sar       r8,3F
       and       r8,3
       add       rcx,r8
       sar       rcx,2
       mov       r8,[rbp-38] ; This is writeRight!
       mov       r9,r8
       sub       r9,rdx
       mov       r10,r9
       sar       r10,3F
       and       r10,3
       add       r9,r10
       sar       r9,2
       cmp       rcx,r9
       jg        short M08_L02
       lea       rcx,[rsi+20]
       jmp       short M08_L03

Workaround / Bug

By changing the order of declaration, as I did in my workaround version:

                // This time pBase is initialized BEFORE the other variables
                var pBase = Int32PermTables.IntPermTablePtr;


                var tmpLeft = _tempStart;
                var tmpRight = _tempEnd - N;
                var writeLeft = left;
                var writeRight = right - N - 1;

The generated assembly now correctly promotes the writeRight variable into a full fledged register without performing needless stack reads and write within my main loop:

M08_L00:
       mov       r8,rax
       sub       r8,r15
       mov       r9,r8
       sar       r9,3F
       and       r9,3
       add       r8,r9
       sar       r8,2
       mov       r9,rdx
       sub       r9,rcx
       mov       r10,r9
       sar       r10,3F
       and       r10,3
       add       r9,r10
       sar       r9,2
       cmp       r8,r9
       jg        short M08_L02
       lea       r8,[rax+20]
       jmp       short M08_L03

The full disassembly can be viewed here, in case someone is interested:

https://gist.github.com/damageboy/c09fc710d2b9010fe176645fa526a170

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

[BruceForstall]

@damageboy When you say "bug", are you saying that the JIT is generating incorrect code (that generates an incorrect result, or crashes)? Or just that the JIT is generating sub-optimal code because it isn't using a register for something it could?

cc @AndyAyersMS @CarolEidt

[damageboy]

Sorry for the long delay, was away from computer for a couple of days.

The code is completely correct, it's sub-optimal due to missed opportunity to promote memory access to register.

The "bug" is in the sense that it is completely erratic and dependent on moving the variable declaration later with respect to the pointer assignment I marked in the comment as:

                // This time pBase is initialized BEFORE the other variables

[BruceForstall]

Thanks for the update. Given that it's not a functional correctness issue, I'm setting the milestone to "Future". It still would be worth investigating and understanding why this behavior occurs.

[Genbox]

@damageboy has a really good article on the subject where this issue, as well as 2 other minor code quality issues, are described.

I'm all for better code quality as everyone benefits from them. A tight loop with 1-2 unnecessary instructions can blow the roof off performance-critical code.

I'll cheekily cc @mikedn as well since there has been no word from Andy or Carol yet.

[AndyAyersMS]

Sorry for the slow response. I'll try and take a look before too much longer, but my guess is this will end up being an allocator issue, and those can be tricky to address.

[damageboy]

It's not critical for me personally anymore, as I've worked around it, and I admit it's pretty obscure in many senses.
But these things always end up being surprising in the sense it might be affecting more people than just me.

Just to be clear, nothing is being blocked by this in any way on my end.

[dotnet-policy-service]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.