Incorrect (?) optimizations of overlapped struct copy in unsafe code

[jkotas]

The JIT assumes that structs cannot overlap when generating code for struct copies. This assumption is not guaranteed in unsafe code. I have noticed it while looking at dotnet/coreclr#9786.

Compile with /o+ on x64:

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

[StructLayout(LayoutKind.Sequential, Size = 64)]
struct Block64 { }

unsafe class Test
{
    [MethodImpl(MethodImplOptions.NoInlining)]
    static void Copy(Block64* pDest, Block64* pSrc)
    {
        *pDest = *pSrc;
    }

    static void Main()
    {
        byte[] buf = new byte[65];
        for (int i = 0; i < buf.Length; i++) buf[i] = (byte)i;

        fixed (byte* p = buf)
        {
            Copy((Block64*)(p + 1), (Block64*)p);
        }

        Console.Write("Expected: 16 Actual: " + buf[17].ToString());
    }
}

Result: Expected: 16 Actual: 15
category:correctness
theme:block-opts
skill-level:expert
cost:small
impact:small

[jkotas]

cc @dotnet/jit-contrib

[russellhadley]

@jkotas I've been staring at this on and off all morning. I've also been asking around to get second opinions and there doesn't seem to be a consensus. It boils down in my mind to if there's a rule in the spec that says that I have to treat pointers to structs in unsafe blocks as byte pointers. Do you have any more historical context here? How should I be looking at this?

[jkotas]

Right, the rules of what sort of aliasing is ok vs. no ok to depend in unsafe code has never been strictly codified (related to https://github.com/dotnet/coreclr/issues/5870).

My take on this is that the operations on unsafe pointers should work just like in C/C++ because of it is what people expect. Do C/C++ compilers assume noaliasing for assignments of POD structs?

[briansull]

I'm not sure there is such a thing as an "unsafe pointer" there are only unsafe operations.
(Such as the cast from byte* into Block64* )
Which basically mean trust me I know what I'm doing here.

I think that you can rewrite your example and remove the "unsafe"on the class
And just use the unsafe on the method or on the fixed block:

unsafe static void Main()
unsafe { fixed (byte* p = buf) ... }

[russellhadley]

@jkotas, In C++ you would have to assume that they overlapped. I went back and got a few second opinions from people who implemented IJW and the like and for C# we also should assume that for this case they overlap. I'm going to need to keep digging on this, make sure the IL is right, etc., but your results indicate a bug.

[mikedn]

In C++ you would have to assume that they overlapped

Why? I don't think there's anything in the C++ standard that would require that. Most likely this would be in the "undefined behavior" bucket.

(V)C++ version of the C# example:

struct Block64 {
    char x[64];
};

__declspec(noinline) void Copy(Block64* pDest, Block64* pSrc) {
    *pDest = *pSrc;
}

int main() {
    char* buf = new char[65];
    for (int i = 0; i < 65; i++)
        buf[i] = i;

    char* p = buf;
    Copy((Block64*)(p + 1), (Block64*)p);

    printf("Expected: 16 Actual: %d\n", buf[17]);
}

Of course, it prints the same result: Expected: 16 Actual: 15. The code generated for the Copy function is:

01261000 0F 10 02             movups      xmm0,xmmword ptr [edx]  
01261003 0F 11 01             movups      xmmword ptr [ecx],xmm0  
01261006 0F 10 42 10          movups      xmm0,xmmword ptr [edx+10h]  
0126100A 0F 11 41 10          movups      xmmword ptr [ecx+10h],xmm0  
0126100E 0F 10 42 20          movups      xmm0,xmmword ptr [edx+20h]  
01261012 0F 11 41 20          movups      xmmword ptr [ecx+20h],xmm0  
01261016 0F 10 42 30          movups      xmm0,xmmword ptr [edx+30h]  
0126101A 0F 11 41 30          movups      xmmword ptr [ecx+30h],xmm0  

[JosephTremoulet]

I believe that a C++ compiler is allowed to use memcpy semantics to lower a struct assignment, but also that it's not allowed to elide struct copies if doing so would introduce an overlapping struct assignment (unless it lowers the resulting possibly-overlapping assignment with memmove semantics). For example:

struct S {
    int data[64];
};

S bar1(S* s) { return *s; }
void bar2(S* dst, S src) { *dst = src; }

void foo(S* dst, S* src, int c) {
    switch (c) {
    case 1:
        // Direct assignment; memcpy semantics
        *dst = *src;
        break;
    case 2:
        // Call gets inlined, but temp introduced for return actual isn't elided
        *dst = bar1(src);
        break;
    case 3:
        // Call gets inlined, but temp introduced for actual arg isn't elided
        bar2(dst, *src);
    }
}

So it would seem that a C++ compiler presented with source that looks like the C# above would use memcpy semantics, but since it compiles to IL with separate ldobj/stobj instructions using a stack temporary intermediate, a C++ compiler presented with source that looks like the MSIL would emit two copies (or could use memmove semantics). I'm guessing that the guideline of "operations on unsafe pointers should work just like in C/C++ because of it is what people expect" applies more to what C/C++ does with code that looks like the C# code, but it's not clear how we could pattern-match the resultant IL without coming up too broad or to narrow to line up with C/C++ in terms of eliding temps (and of course pattern-matching IL could mess up IL generators other than the C# compiler). The definition of cpblk indicates that the jit can use memcpy semantics for it (and maybe IJW uses it for struct assignments?), but if the C# compiler uses it, I don't know when.

[russellhadley]

My original thought was that as pointers to the same non-integral struct type they could certainly overlap and require memmove semantics to be correct. But the point seems to be whether we need to enforce memcpy (overlap unsafe) vs memmove (safe) semantics. @cmckinsey you had the case where this bit us before in managed C++ and IJW. Can you comment here? From an aliasing perspective in the optimizer we certainly have to track these as potentially aliasing, but I need to spend some more time with the C++ spec to see if a buildin assignment operator should work this way.

[mikedn]

but I need to spend some more time with the C++ spec to see if a buildin assignment operator should work this way.

From the C++ spec 5.18/8

If the value being stored in an object is read via another object that overlaps in any way the storage of the first object, then the overlap shall be exact and the two objects shall have the same type, otherwise the behavior is undefined. [Note: This restriction applies to the relationship between the left and right sides of the assignment operation; it is not a statement about how the target of the assignment may be aliased in general. See 3.10. —end note]