Bad x64 codegen in VerifyUnifierConsistency

[MichalStrehovsky]

@sergiy-k and I hit this in CoreRT, but this has a repro in CoreCLR too.

Compile the attached Program.txt
as csc /noconfig /nostdlib /r:System.Private.CoreLib.dll Program.cs /define:DEBUG /O (note: we define the DEBUG symbol and enable optimizations) and run the resulting executable with CoreRun. The code will hit an assert. Now drop the /O and the code won't hit the assert.

@sergiy-k found some suspicious use of rdi register in VerifyUnifierConsistency. Setting COMPlus_JitDisasm=VerifyUnifierConsistency and inspecting the use of rdi in the disassembly might be a good starting point.

[AndyAyersMS]

I'll take a look.

[AndyAyersMS]

Looks your diagnosis is spot-on. JIT is using r14d for walk1 but when it indexes into _entries it mysteriously switches over to using rdi:

G_M65020_IG12:
...
4C8B4610         mov      r8, gword ptr [rsi+16]      ;; get _entries from this
453B7008         cmp      r14d, dword ptr [r8+8]      ;; bounds check walk1
0F835F010000     jae      G_M65020_IG19
4D8D44F810       lea      r8, bword ptr [r8+8*rdi+16] ;; get address of _entries[walk1]...???

[mikedn]

it mysteriously switches over to using rdi

And it looks like the cast from int to long is missing too.

[AndyAyersMS]

Also a regression from 1.1. Note array bounds check and access will generally need two different registers, because this is an array of structs, so the physical index is the logical index * 24. 1.1 has *8 in the addressing mode and *3 earlier. 2.0 seems to lose the *3 somehow, presumably that is what should have been in rdi.

G_M65020_IG12:
 ...
 4863D5               movsxd   rdx, ebp
 4C8D3C52             lea      r15, [rdx+2*rdx]
 ...
 4C8B4610             mov      r8, gword ptr [rsi+16]
 413B6808             cmp      ebp, dword ptr [r8+8]
 0F8375010000         jae      G_M65020_IG20
 4F8D44F810           lea      r8, bword ptr [r8+8*r15+16]

Will keep digging... seems like maybe an optimizer bug at this point.

cc @dotnet/jit-contrib

[AndyAyersMS]

Best guess so far is that gtFoldExprSpecial sees a box(..) == null and deadcodes it, but hidden in the ... is a side effect to initialize the *3 cse (V37 here) that gets lost in the process:

Bashing [000121] to NOP as part of dead box operation
N040 (  1,  1) [000131] ------------             /--*  CNS_INT   ref    null $VN.Null
N041 ( 55, 53) [000132] NA-XGO------             *  NE        int    $26e
N039 ( 50, 51) [000130] -A-XGO------             \--*  BOX       ref    $5d0
N037 (  1,  1) [000128] ------------                |  /--*  LCL_VAR   ref    V08 tmp3         u:3 (last use) $2d5
N038 ( 44, 47) [000129] -A-XGO------                \--*  COMMA     ref    $2d5
N035 ( 38, 41) [000116] *A-XG-------                   |  /--*  IND       int    <l:$26d, c:$609>
N033 (  1,  1) [000571] ------------                   |  |  |  /--*  CNS_INT   long   8 field offset Fseq[_key] $1c3
N034 ( 36, 39) [000572] -A-XG--N----                   |  |  \--*  ADD       byref  $215
N030 ( 23, 23) [000592] -A--G-------                   |  |     |     /--*  ADDR      byref  $82
N029 ( 12, 12) [000114] aA--G--N----                   |  |     |     |  \--*  IND       struct <l:$680, c:$6c0>
N027 (  1,  1) [000584] ------------                   |  |     |     |     |  /--*  CNS_INT   long   16 Fseq[#FirstElem] $1c2
N028 ( 11, 11) [000585] -A-----N----                   |  |     |     |     \--*  ADD       byref  $82
N024 (  1,  1) [000581] -------N----                   |  |     |     |        |     /--*  CNS_INT   long   3 $1c8
N025 (  9,  9) [000582] -A-----N----                   |  |     |     |        |  /--*  LSH       long   $545
N022 (  1,  1) [000899] ------------                   |  |     |     |        |  |  |  /--*  LCL_VAR   long   V37 cse2          $544
N023 (  8,  8) [000900] -A----------                   |  |     |     |        |  |  \--*  COMMA     long   $544
N018 (  1,  1) [000590] ------------                   |  |     |     |        |  |     |     /--*  CNS_INT   long   3 $1c8
N019 (  7,  7) [000591] ------------                   |  |     |     |        |  |     |  /--*  MUL       long   $544
N017 (  2,  3) [000580] ------------                   |  |     |     |        |  |     |  |  \--*  CAST      long <- int $543
N016 (  1,  1) [000577] i-----------                   |  |     |     |        |  |     |  |     \--*  LCL_VAR   int    V03 loc2         u:4 $484
N021 (  7,  7) [000898] -A------R---                   |  |     |     |        |  |     \--*  ASG       long   $VN.Void
N020 (  1,  1) [000897] D------N----                   |  |     |     |        |  |        \--*  LCL_VAR   long   V37 cse2          $544
N026 ( 10, 10) [000583] -A-----N----                   |  |     |     |        \--*  ADD       byref  <l:$210, c:$20f>
N015 (  1,  1) [000576] ------------                   |  |     |     |           \--*  LCL_VAR   ref    V25 tmp20        u:3 (last use) <l:$2d7, c:$5cd>
N031 ( 31, 34) [000586] -A-XG-------                   |  |     |  /--*  COMMA     byref  <l:$214, c:$213>
N014 (  8, 11) [000579] ---X--------                   |  |     |  |  \--*  ARR_BOUNDS_CHECK_Rng void   <l:$2dd, c:$2dc>
N011 (  1,  1) [000113] ------------                   |  |     |  |     +--*  LCL_VAR   int    V03 loc2         u:4 $484
N013 (  3,  3) [000578] ---X--------                   |  |     |  |     \--*  ARR_LENGTH int    <l:$448, c:$447>
N012 (  1,  1) [000575] ------------                   |  |     |  |        \--*  LCL_VAR   ref    V25 tmp20        u:3 <l:$2d7, c:$5cd>
N032 ( 35, 38) [000587] -A-XG-------                   |  |     \--*  COMMA     byref  <l:$214, c:$213>
N008 (  4,  4) [000112] ---XG-------                   |  |        |  /--*  IND       ref    <l:$2d7, c:$5cd>
N006 (  1,  1) [000588] ------------                   |  |        |  |  |  /--*  CNS_INT   long   16 field offset Fseq[_entries] $1c2
N007 (  2,  2) [000589] -------N----                   |  |        |  |  \--*  ADD       byref  $206
N005 (  1,  1) [000111] ------------                   |  |        |  |     \--*  LCL_VAR   ref    V00 this         u:2 $100
N010 (  4,  4) [000574] -A-XG---R---                   |  |        \--*  ASG       ref    <l:$2d7, c:$5cd>
N009 (  1,  1) [000573] D------N----                   |  |           \--*  LCL_VAR   ref    V25 tmp20        d:3 <l:$2d7, c:$5cd>
N036 ( 43, 46) [000127] -A-XGO------                   \--*  ASG       int    $VN.Void
N004 (  4,  4) [000126] -----O-N----                      \--*  IND       int    <l:$26c, c:$609>
N002 (  1,  1) [000124] ------------                         |  /--*  CNS_INT   long   8 $1c3
N003 (  2,  2) [000125] -------N----                         \--*  ADD       byref  $20e
N001 (  1,  1) [000123] ------------                            \--*  LCL_VAR   ref    V08 tmp3         u:3 $2d5

Most of the other cases in this method check for side effects and defer; seems like we should verify the box arg is side-effect free here too.

[AndyAyersMS]

Because key is a value type, the assert below is trivially true. But it also generates a CSE used in the subsequent statement. Should be easy enough to create a small repro...

                    Debug.Assert(_entries[walk1]._key != null);
                    int hashCode = _entries[walk1]._key.GetHashCode();

[AndyAyersMS]

Somewhat simpler repro. Codegen bug is in Test as above.

using System;

public struct S<K>
{
    public int x;
    public int y;
    public K val;
}

public class X<K,V> 
{
    public X(K k)
    {
        a = new S<K>[2];
        a[1].val = k;
        a[1].x = 3;
        a[1].y = 4;
    }

    public void Assert(bool b)
    {
        if (!b) throw new Exception("bad!");
    }

    public int Test()
    {
        int r = 0;
        for (int i = 0; i < a.Length; i++)
        {
            Assert(a[i].val != null);
            r += a[i].val.GetHashCode();
        }
        return r;
    }

    S<K>[] a;
}

class B
{
    public static int Main()
    {
        var a = new X<int, string>(11);
        int z = a.Test();
        return (z == 11 ? 100 : 0);
    }
}

[AndyAyersMS]

The underlying assume-no-side-effects weakness in gtFoldExprSpecial predates 2.0 -- indeed it is there in the jit32 sources as well.

Not clear yet if we can expose this bug in older jits. It is showing up in 2.0 because of more aggressive CSEs.

[AndyAyersMS]

Adding a side effect check fixes the bad codegen, but is overly pessimistic. Likely need to rework the box code in the importer to forcibly move possible side effects out from under the box.

[AndyAyersMS]

Or maybe not, the optimization done in gtFoldExprSpecial effectively dead-codes a struct copy because it's folded in under the box. If we split it out it may become problematic.

This argues for drilling deeper into the box operand during gtFoldExprSpecial to try sort which of the side effects are "expected" and can be ignored and which others aren't... not thrilled about this but it is probably the most surgical fix.

[AndyAyersMS]

Simpler repro that does not require CSE. Here the call to Get is dropped.

using System;
using System.Runtime.CompilerServices;

public class X<K> 
{
    public X(K k1)
    {
        k = k1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public K Get()
    {
        Console.WriteLine("Get called");
        count++;
        return k;
    }

    public bool Test()
    {
        bool x = Get() != null;
        bool y = (count == 1);
        return x && y;
    }

    K k;
    int count;
}

class B
{
    public static int Main()
    {
        var a = new X<int>(11);
        bool result = a.Test();
        Console.WriteLine("Passed: {0}", result);
        return result ? 100 : 0;
    }
}

[AndyAyersMS]

One more example, this time we lose an exception-causing dereference.

using System;
using System.Runtime.CompilerServices;

public class X<K> 
{
    public X(K k1)
    {
        k = k1;
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    public static bool Test(X<K> a)
    {
        return (a.k != null);
    }

    public K k;
}

class B
{
    public static int Main()
    {
        X<int> a = null;
        bool result = false;
        try 
        {
            X<int>.Test(a);
        }
        catch (Exception)
        {
            result = true;
        }
        Console.WriteLine("Passed: {0}", result);
        return result ? 100 : 0;
    }
}

[AndyAyersMS]

Still searching for the right fix. Couple more notes.

1. The initial trees produced by the box are roughly
   Stmt1: newobj into a newly live local "boxTemp"
   Stmt2: ... tree of BOX(COMMA(boxTemp, ASG(exprToBox,boxTemp)
2. If BOX of a value type appears under a EQ/NE compare to null we optimize it in gtFoldExprSpecial. This can be called at various times and is even invoked in the importer.
3. The optimization replaces (EQ/NE, null (BOX ...)) with (0/1) as appropriate. Thus all side effects under the BOX are lost. It also nulls out Stmt1.
4. Most often the only side effect under the box is a modification of the "boxTemp" which dies at the compare so we are ok with losing those side effects.
5. But if the evaluation of exprToBox contains other side effects we may lose them too, and this is the bug we're trying to fix. Examples above show cases where these effects include embedded assignments for CSEs, calls, and exceptions.
6. Interestingly CSC now may use cgt.un for the compare of box vs null which breaks the pattern in gtFoldExprSpecial and prevents this optimization from happening early, in the importer -- later assertion prop changes the comparison operator to EQ/NE and it fires during optimization. So we should broaden the predicate types we look for in gtFoldExprSpecial to try and catch more cases of this earlier. Since this can nuke relatively large trees it is worth doing as early as possible.
7. Whether invoked early or late we run the risk of losing side effects. There is potentially some advantage to catching this early as the shape of the tree under the box is more constrained so presumably the necessary side effects could be more readily extracted.
8. Generally we would expect almost all cases could be found early since this is largely a type based optimization -- however if the null required const-prop or similar perhaps we would miss some if we only did this early.
9. One could imagine splitting off any side effects from exprToBox into yet another statement and (if anything is split) storing the result in another temp. Since the cases where exprToBox has side effects are rare this seems like a viable approach. However...
10. The BOX operator IR only appears for simple inline box cases; this has two sub cases, one where exprToBox is a simple scalar type and the other where it is a struct. Both cases are vulnerable to this. bug. So if we do the split as in 9, in the struct case we run the risk of creating a dead struct copy if we end up optimizing the box away, and an unnecessary struct copy if we don't optimize (say the BOX is not under a compare). I haven't gotten far enough along to see if we can optimize this away. This case may be rare enough that we'd be willing to pay this cost to avoid the bug.
11. Ideally we'd look ahead during importation and see that the BOX was feeding a compare and only then decide to split off the effects, but that's likely not viable.
12. But if we only did this optimization early, we might be able to look back when we did the optimization into the BOX tree and effectively split off the side effects (since as noted above the tree shapes are limited).
13. An attempt to do this splitting within gtFoldExprSpecial foundered because JTRUE is not well prepared to handle COMMA, so there's no easy way in an expression context to hold onto the effects.
14. This optimization is important and we need to inhibit as few cases as possible. There are many examples in corelib (presumably all correctly optimized?) so getting that down to minimal diffs is a good indicator of progress.