JIT: dead stores are not eliminated

[EgorBo]

Couldn't find any related issue and decided to file it:

unsafe void DeadStore1(int* array)
{
    *array = 1;
    *array = 2;
    *array = 3;
}

void DeadStore2(ref int x)
{
    x = 1;
    x = 2;
    x = 3;
}

void DeadStore3(int[] array)
{
    if (0 < (uint)array.Length)
    {
        array[0] = 1;
        array[0] = 2;
        array[0] = 3;
    }
}

Codegen:

; DeadStore1(long):this
G_M36731_IG01:
G_M36731_IG02:
       mov      dword ptr [rdx], 1
       mov      dword ptr [rdx], 2
       mov      dword ptr [rdx], 3
G_M36731_IG03:
       ret      
; Total bytes of code: 19


; DeadStore2(byref):this
G_M42680_IG01:
G_M42680_IG02:
       mov      dword ptr [rdx], 1
       mov      dword ptr [rdx], 2
       mov      dword ptr [rdx], 3
G_M42680_IG03:
       ret      
; Total bytes of code: 19


; DeadStore3(System.Int32[]):this
G_M18892_IG01:
G_M18892_IG02:
       mov      eax, dword ptr [rdx+8]
       test     eax, eax
       je       SHORT G_M18892_IG04
G_M18892_IG03:		;; bbWeight=0.50
       mov      dword ptr [rdx+16], 1
       mov      dword ptr [rdx+16], 2
       mov      dword ptr [rdx+16], 3
G_M18892_IG04:
       ret      
; Total bytes of code: 29

In none of these cases dead stores were eliminated.
Is it a known Value Numbering limitation?

Mono-LLVM:

00000000000b10 <Program_DeadStore1_int_>:
 b10:   c7 06 03 00 00 00       mov    DWORD PTR [rsi],0x3
 b16:   c3                      ret

0000000000000b20 <Program_DeadStore2_int_>:
 b20:   c7 06 03 00 00 00       mov    DWORD PTR [rsi],0x3
 b26:   c3                      ret

0000000000000b30 <Program_DeadStore3_int__>:
 b30:   83 7e 18 00             cmp    DWORD PTR [rsi+0x18],0x0
 b34:   74 07                   je     b3d <Program_DeadStore3_int__+0xd>
 b36:   c7 46 20 03 00 00 00    mov    DWORD PTR [rsi+0x20],0x3
 b3d:   c3                      ret

category:cq
theme:optimization
skill-level:intermediate
cost:small
impact:small

[omariom]

How often people write such code? 👀

[gfoidl]

Aside question: will the cpu eliminate the dead stores?
(So the cost would be fetching and decoding the redundant instructions).

[ArtBlnd]

@gfoidl I don't think CPU can eliminate those codes.
storing data directly into memory will not be eliminated because CPU does not know that memory has side-effects.

[kunalspathak]

Another case to note:

public class MyType<T>
{
    T value;
    public MyType(T _value)
    {
        value = _value;
    }
    public T GetValue()
    {
        return value;
    }
}
[MethodImpl(MethodImplOptions.NoInlining)]
uint deadStore()
{
    char result;
    result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue();
    result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue();
    result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue();
    result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue(); result = myType.GetValue();
    return result;
}

Code generated for x64:

G_M30105_IG02:
       488B4108             mov      rax, gword ptr [rcx+8]
       488BD0               mov      rdx, rax
       3912                 cmp      dword ptr [rdx], edx  # <-- Not sure what this cmp are for?
       488BD0               mov      rdx, rax
       3912                 cmp      dword ptr [rdx], edx
       488BD0               mov      rdx, rax
       3912                 cmp      dword ptr [rdx], edx
       488BD0               mov      rdx, rax
       3912                 cmp      dword ptr [rdx], edx
       488BD0               mov      rdx, rax
       3912                 cmp      dword ptr [rdx], edx
       488BD0               mov      rdx, rax

Code generated for arm64:

G_M5313_IG02:
        F9400400          ldr     x0, [x0,#8]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]
        AA0003E1          mov     x1, x0
        B940003F          ldr     wzr, [x1]

[erozenfeld]

@EgorBo I looked at your examples in #13727 (comment)
The jit currently can't track dead assignments to the heap. Adding a general optimization to handle them would be expensive in terms of jit throughput since it will require heap alias analysis. We could handle these trivial examples (when there are no trees between the stores) as peaphole optimizations but I suspect these cases don't happen often enough to justify it.

[erozenfeld]

The example in #13727 (comment) is different since these are redundant null checks. We should be able to handle it.

[erozenfeld]

Analysis of the example in #13727 (comment).

For simplicity I reduced the number of

result = myType.GetValue();

from 16 to 3.

Before null check folding optimization (in earlyProp) we have:

tmp1 = [this+8]
nullcheck tmp1
tmp2 = [this+8]
nullcheck tmp2
tmp3 = [this+8]
nullcheck tmp3
return [tmp3+8]

The optimization gets rid of the last nullcheck but can't do anything with the earlier nullchecks. It doesn't understand that tmp1, tmp2, and tmp3 all have the same value.

tmp1 = [this+8]
nullcheck tmp1
tmp2 = [this+8]
nullcheck tmp2
tmp3 = [this+8]
return [tmp3+8]

After CSE we end up with:

tmp1 = comma(cse0 = [this+8], cse0)
nullcheck tmp1
tmp2 = cse0
nullcheck tmp2
tmp3 = cse0
return [tmp3+8]

Here occurrences of cse0 and tmp2 and tmp3 have the same liberal value number but different conservative value numbers. In theory we could propagate conservative value numbers everywhere we can after CSE, although not having def->use links in SSA might be a problem. If we do propagate conservative value numbers, assertion propagation should be able to eliminate the second nullcheck and the assignment to tmp2. We would still be left with the first nullcheck and the assignment to tmp1.

Another idea is to run null check folding after CSE either instead or in addition to the existing pass. It would still have to changed in a non-trivial way to get rid of the nullcheck's.

Since there is no easy solution here, moving this issue to future.