IL to C++ compiler - Need advice on implementing context switching

I wonder if it has something to do the the "dup" instructions.

Yep. If you look at the generated code for IL3A-3F you can easily note that dup has no effect. If you remove the dup then your compiler would generate identical code. That's a good indication that something isn't right.

So when I perform the dup operation, the two top items on the stack now contain "pStr".

dup make a copy of the value, it seems to me that your implementation makes a copy of some sort of reference to the value.

but it is going to bloat the code a lot (or at least the source files) since I'll need to create a unique structure for each call.

Yes the sources will be a bit bigger but I'd say not by much. Note that you need one struct per method, not per call.

12 minutes ago,Dexter wrote

*snip*

Yep. If you look at the generated code for IL3A-3F you can easily note that dup has no effect. If you remove the dup then your compiler would generate identical code. That's a good indication that something isn't right.

*snip*

dup make a copy of the value, it seems to me that your implementation makes a copy of some sort of reference to the value.

I'm trying to understand how it is failing but I can't. To me, those instructions want to add 2 to the value of pStr, which it clearly does via this line of C++ code:

pStr = (Char*)(((Int32)pStr + (Int32)2));

Also, stepping through the code, the problem is not that pStr is incremented wrong, it is that m_length is incremented too late. You might be right but I can't figure it out.

Note the way the IL instructions are notated in the C++ code is that all IL instructions leading up to actual code are grouped together. So all instructions from IL3A-3F results in the line of code shown above. From what I can tell it is performing the correct operation on pStr. pStr showing up twice in the line of code is a direct result of the dup operation.

I think the bug must be somewhere else.

OK, let me detail this a bit:

IL_003a: // ldarg.1 - load pStr
IL_003b: // dup - duplicate pStr, now the stack contains the value of pStr twice
...
IL_003e: // add - add one of the pStrs and 2
IL_003f: // starg.s: Char* pStr - store the value on top of the stack to pStr
// !!!the original value of pStr remains on top of the stack!!!
    pStr = (Char*)(((Int32)pStr + (Int32)2));IL_0041: // ldind.u2 - load from the address on top of the stack
// that is, from the original pStr
...
    local0 = ((((UInt16)*(UInt16*)pStr) == 0) == 0); // load from pStr - not the original pStr but the incremented one

The net result is that since you're using the incremented pStr you're one character ahead, this is where the -1 differences comes from.

@Dexter:

Yes, I think you are correct. I'll need to figure out how to create temporary variables in the case of dup. Not as straightforward since ref types need to be stored on the virtual stack to make sure they are not GCd, and those are prepared when the function enters.

We have company coming over so I won't be able to look at this again until tomorrow or so.

EDIT: Actually, this might not be so difficult. I already do a pre-pass and attach local variables to certain instructions (newObj, newArr, call, etc), so I can do the same for dup. Then when the function code is written, I check all instructions for local variables (either ref of value types), and create that part of the code. So all I need to do is also create a local variable for dup to store its duplicated value in.

This dup instruction seems like it might be a problem. This is because as far as I can see, there is no way to statically determine what type of object will be on the top of the stack when the dup is encountered. Any part of the code could load a value on the stack, and then jump to the dup instruction.

So what kind of local variable needs to be created ahead of time to store the duplicate value? An object type? Then if the object on the stack is a value type, the value needs to be boxed.

Another option could be to determine all possible locations that could jump to the dup and determine what would be on the stack at that time. At runtime, choose the reserved local variable of the right type. Seems complicated but then again it probably would not be too common to find a dup where multiple areas of the code jumps to it.

Is there a better solution?

So using ILSpy and looking at it's C# version of the method, it looks like this:

public unsafe VirtualString(char* pStr)
{
    this.m_buffer = pStr;
    this.m_length = 0;
    if (this.m_buffer != null)
    {
        while (true)
        {
            char* expr_3B = pStr;
            pStr = expr_3B + (IntPtr)2 / 2;
            if (*(ushort*)expr_3B == 0)
            {
                break;
            }
            this.m_length += 1;
        }
    }
}

So that tells me that it clearly sees the temporary variable as the same type as pStr, and hardcoded as such. I assume that in this case it would be "illegal" IL if you did have a situation where you can reach the dup instruction with different types on the top of the stack. The IL documentation doesn't mention this detail at all. Neither does the book "The Common Language Infrastructure Annotated Standard". It literally just says "The dup instruction duplicates the top element of the stack". Nothing else.

Hmm, AFAIK "reach the dup instructions with different types" is not allowed. See 1.8.1.3 Merging Stack States in ECMA 335.

Even if this is allowed I think it's still possible to deal with. If a basic block containing dup is reached with 2 different stack states then this can be treated as if there actually were 2 distinct basic blocks in the first place.

6 hours ago,Dexter wrote

Hmm, AFAIK "reach the dup instructions with different types" is not allowed. See 1.8.1.3 Merging Stack States in ECMA 335.

Even if this is allowed I think it's still possible to deal with. If a basic block containing dup is reached with 2 different stack states then this can be treated as if there actually were 2 distinct basic blocks in the first place.

I looked at section 1.8.1.3 and it mentions how types can be converted. This does help me completely because during my code analysis lets say I find an Int16 on the stack. Now I create a local variable of type Int16. But the at runtime something jumps to the dup instruction from another part of the code, and there happens to be an Int32 on the stack. While I can cast to an Int16, I'm going to lose precision. For now I'm going to go with the assumption that there will always be the same type on the stack when reaching a dup instruction.

Anyway, I went ahead and changed the code to create an actual local variable for each dup instruction (with the assumption that it can always only be of the type that was on the stack during the initial code analysis pass). Unfortunately I am still seeing the bug where m_length is 1 less than it should be. Below is the new generated C++ code. To me it seems that instruction IL_0029 should jump to instruction IL_002d instead of IL_003a. It is basically skipping the first increment on m_length. Can you spot the bug in my C++ code?

[EDIT: OK, I'm currently struggling with C9's code formatter in order to not have it put all of the code on one line. I'm selecting the code in VS, copying it, opening the "</>" code editor dialog in C9, pasting it, selecting the language type, pressing Insert and then Submit. What am I doing wrong? For now, I'm pasting the unformatted code in addition to the single formatted line until I can figure the formatting out]

        Void T8012_VirtualString::T8012_Ctor_VirtualString(VirtualThread* pThread, T8012_VirtualString** pThis, Char* pStr)
        {

            // Ref type locals
            T8012_VirtualString** dupRef0 = (T8012_VirtualString**)&pThread->StackPointer[1];

            memset(&pThread->StackPointer[1], 0, sizeof(void*) * 1);
            pThread->StackPointer += 1;

            // Value type locals
            Bool local0 = false;
            Char* dupValue0 = 0;

        IL_0000: // ldarg.0
        IL_0001: // call: Void .ctor()
            (*pThis)->T8003_VirtualObject::T8003_Ctor_VirtualObject(pThread, (T8003_VirtualObject**)pThis);

        IL_0006: // nop
        IL_0007: // nop
        IL_0008: // ldarg.0
        IL_0009: // ldarg.1
        IL_000a: // stfld: Char* m_buffer
            (*pThis)->m_buffer = pStr;

        IL_000f: // ldarg.0
        IL_0010: // ldc.i4.0
        IL_0011: // stfld: UInt16 m_length
            (*pThis)->m_length = 0;

        IL_0016: // ldarg.0
        IL_0017: // ldfld: Char* m_buffer
        IL_001c: // ldc.i4.0
        IL_001d: // conv.u
        IL_001e: // ceq
        IL_0020: // ldc.i4.0
        IL_0021: // ceq
        IL_0023: // stloc.0
            local0 = (((*pThis)->m_buffer == (Int32)(UInt32)(0)) == 0);

        IL_0024: // ldloc.0
        IL_0025: // brtrue.s: 2
            if (local0 != 0)
                goto IL_0029;

        IL_0027: // br.s: 36
            goto IL_004d;

        IL_0029: // br.s: 15
            goto IL_003a;

        IL_002b: // ldarg.0
        IL_002c: // dup
            (*dupRef0) = *(pThis);

        IL_002d: // ldfld: UInt16 m_length
        IL_0032: // ldc.i4.1
        IL_0033: // add
        IL_0034: // conv.u2
        IL_0035: // stfld: UInt16 m_length
            (*pThis)->m_length = (Int32)(UInt16)(((Int32)(*dupRef0)->m_length + 1));

        IL_003a: // ldarg.1
        IL_003b: // dup
            dupValue0 = pStr;

        IL_003c: // ldc.i4.2
        IL_003d: // conv.i
        IL_003e: // add
        IL_003f: // starg.s: Char* pStr
            pStr = (Char*)(((Int32)dupValue0 + (Int32)2));

        IL_0041: // ldind.u2
        IL_0042: // ldc.i4.0
        IL_0043: // ceq
        IL_0045: // ldc.i4.0
        IL_0046: // ceq
        IL_0048: // stloc.0
            local0 = ((((UInt16)*(UInt16*)pStr) == 0) == 0);

        IL_0049: // ldloc.0
        IL_004a: // brtrue.s: -33
            if (local0 != 0)
                goto IL_002b;

        IL_004c: // nop
        IL_004d: // ret
            goto Exit;

        Exit:
            pThread->StackPointer -= 1;
        }

[Does the following block of code display properly for anyone? It is all on one line for me. I filed a C9 bug report about this and referred back to this post. I'll leave this extra block of code here until the bug in the forum has been fixed.]

void T8012_VirtualString::T8012_Ctor_VirtualString(VirtualThread* pThread, T8012_VirtualString** pThis, Char* pStr){    // Ref type locals    T8012_VirtualString** dupRef0 = (T8012_VirtualString**)&pThread->StackPointer[1];    memset(&pThread->StackPointer[1], 0, sizeof(void*) * 1);    pThread->StackPointer += 1;    // Value type locals    Bool local0 = false;    Char* dupValue0 = 0;IL_0000: // ldarg.0IL_0001: // call: Void .ctor()    (*pThis)->T8003_VirtualObject::T8003_Ctor_VirtualObject(pThread, (T8003_VirtualObject**)pThis);IL_0006: // nopIL_0007: // nopIL_0008: // ldarg.0IL_0009: // ldarg.1IL_000a: // stfld: Char* m_buffer    (*pThis)->m_buffer = pStr;IL_000f: // ldarg.0IL_0010: // ldc.i4.0IL_0011: // stfld: UInt16 m_length    (*pThis)->m_length = 0;IL_0016: // ldarg.0IL_0017: // ldfld: Char* m_bufferIL_001c: // ldc.i4.0IL_001d: // conv.uIL_001e: // ceqIL_0020: // ldc.i4.0IL_0021: // ceqIL_0023: // stloc.0    local0 = (((*pThis)->m_buffer == (Int32)(UInt32)(0)) == 0);IL_0024: // ldloc.0IL_0025: // brtrue.s: 2    if (local0 != 0)        goto IL_0029;IL_0027: // br.s: 36    goto IL_004d;IL_0029: // br.s: 15    goto IL_003a;IL_002b: // ldarg.0IL_002c: // dup    (*dupRef0) = *(pThis);IL_002d: // ldfld: UInt16 m_lengthIL_0032: // ldc.i4.1IL_0033: // addIL_0034: // conv.u2IL_0035: // stfld: UInt16 m_length    (*pThis)->m_length = (Int32)(UInt16)(((Int32)(*dupRef0)->m_length + 1));IL_003a: // ldarg.1IL_003b: // dup    dupValue0 = pStr;IL_003c: // ldc.i4.2IL_003d: // conv.iIL_003e: // addIL_003f: // starg.s: Char* pStr    pStr = (Char*)(((Int32)dupValue0 + (Int32)2));IL_0041: // ldind.u2IL_0042: // ldc.i4.0IL_0043: // ceqIL_0045: // ldc.i4.0IL_0046: // ceqIL_0048: // stloc.0    local0 = ((((UInt16)*(UInt16*)pStr) == 0) == 0);IL_0049: // ldloc.0IL_004a: // brtrue.s: -33    if (local0 != 0)        goto IL_002b;IL_004c: // nopIL_004d: // ret    goto Exit;Exit:    pThread->StackPointer -= 1;}

Hmm, you fixed the dup but the generated code is still not correct. In fact it behaves identically to the old code. It occurred to me now that the problem is more complicated than the buggy dup.

The IL execution stack contains values. When you do a ldarg (or any other ld) the value stored in the variable is loaded on the stack. After a ld you can modify the variable in any way you like, the stack will still contain the original value of the variable.

Your compiler treats the stack differently, it seems to store references to variables instead of values. This means that whenever you use a stack location that "references" a variable, you get the current value of the variable, not the original one that existed at the time ld was executed.

Let's see this in the code:

dupValue0 = pStr;
pStr = (Char*)(((Int32)dupValue0 + (Int32)2));
local0 = ((((UInt16)*(UInt16*)pStr) == 0) == 0);

Despite it being different, its behavior is exactly the same. The last statement still uses the modified value of pStr instead of using the original one. The correct code should look like this:

oldpStr = pStr;
pStr = (Char*)(((Int32)pStr + (Int32)2));
local0 = ((((UInt16)*(UInt16*)oldpStr) == 0) == 0);

PS: editor problems: don't paste from VS, it seems that it generates html that confuses the post editor. Paste the code to notepad and then copy paste from notepad. This ensures that you paste plain text and not some weird html.

Yes I believe you are correct about my compiler really storing references to the values instead of the actual values themselves. This means I will need to create more temporary local variables to hold the actual values on the stack. This might add a lot of local variables since it might be difficult to know when it is safe to re-use a temporary variable.

So basically for any instruction that pushes either a local or parameter value, I need to create a temporary local variable.

Hopefully the compiler can optimize most of those away, although it won't be able to do it for ref types which I store on the virtual stack.

An optimization in this case could be to keep track of the temp locals during the analysis pass and mark them as "free" when they get popped. Then they can be re-used the next time a local or parameter needs to be pushed on the stack (if they are of the same type of course). Basically a pool of temp locals.

About the code formatting: I tried everything, including pasting into Notepad first. It simply refuses to format the code correctly. I have had success with both pasting directly from VS (but into the popup "</>" code dialog), or via pasting dirently into the text editor after pasting into Notepad. I think the problem in this case is that a previous formatting tag somewhere on the page is confusing the formatter.

OK so I changed it such that every instruction that pushes a value onto the stack uses a temporary variable. The number of locals exploded as you can see below. It is not too important, since what I'm trying to determine is whether that will solve the problem. Well, the current code still has the bug where m_length has a value of 1 less than it should be. Now I'm completely at a loss as to what could be the cause of this issue.

Void T8013_VirtualString::T8013_Ctor_VirtualString(VirtualThread* pThread, T8013_VirtualString** pThis, Char* pStr)
{

    // Ref type locals
    T8013_VirtualString** temp0 = (T8013_VirtualString**)&pThread->StackPointer[1];
    T8013_VirtualString** temp1 = (T8013_VirtualString**)&pThread->StackPointer[2];
    T8013_VirtualString** temp3 = (T8013_VirtualString**)&pThread->StackPointer[3];
    T8013_VirtualString** temp4 = (T8013_VirtualString**)&pThread->StackPointer[4];
    T8013_VirtualString** temp10 = (T8013_VirtualString**)&pThread->StackPointer[5];
    T8013_VirtualString** temp11 = (T8013_VirtualString**)&pThread->StackPointer[6];
    T8013_VirtualString** temp23 = (T8013_VirtualString**)&pThread->StackPointer[7];
    T8013_VirtualString** temp24 = (T8013_VirtualString**)&pThread->StackPointer[8];
    T8013_VirtualString** temp26 = (T8013_VirtualString**)&pThread->StackPointer[9];
    T8013_VirtualString** temp27 = (T8013_VirtualString**)&pThread->StackPointer[10];
    T8013_VirtualString** temp33 = (T8013_VirtualString**)&pThread->StackPointer[11];
    T8013_VirtualString** temp34 = (T8013_VirtualString**)&pThread->StackPointer[12];

    memset(&pThread->StackPointer[1], 0, sizeof(void*) * 12);
    pThread->StackPointer += 12;

    // Value type locals
    Bool local0 = false;
    Char* temp2 = null;
    Char* temp5 = null;
    UInt32 temp6 = 0;
    Int32 temp7 = 0;
    Int32 temp8 = 0;
    Bool temp9 = false;
    UInt16 temp12 = 0;
    Int32 temp13 = 0;
    UInt16 temp14 = 0;
    Char* temp15 = null;
    Char* temp16 = null;
    Int32 temp17 = 0;
    Int32 temp18 = 0;
    UInt16 temp19 = 0;
    Int32 temp20 = 0;
    Int32 temp21 = 0;
    Bool temp22 = false;
    Char* temp25 = null;
    Char* temp28 = null;
    UInt32 temp29 = 0;
    Int32 temp30 = 0;
    Int32 temp31 = 0;
    Bool temp32 = false;
    UInt16 temp35 = 0;
    Int32 temp36 = 0;
    UInt16 temp37 = 0;
    Char* temp38 = null;
    Char* temp39 = null;
    Int32 temp40 = 0;
    Int32 temp41 = 0;
    UInt16 temp42 = 0;
    Int32 temp43 = 0;
    Int32 temp44 = 0;
    Bool temp45 = false;

IL_0000: // ldarg.0
    temp23 = pThis;

IL_0001: // call: Void .ctor()
    (*pThis)->T8003_VirtualObject::T8003_Ctor_VirtualObject(pThread, (T8003_VirtualObject**)pThis);

IL_0006: // nop
IL_0007: // nop
IL_0008: // ldarg.0
    temp24 = pThis;

IL_0009: // ldarg.1
    temp25 = pStr;

IL_000a: // stfld: Char* m_buffer
    (*pThis)->m_buffer = pStr;

IL_000f: // ldarg.0
    temp26 = pThis;

IL_0010: // ldc.i4.0
IL_0011: // stfld: UInt16 m_length
    (*pThis)->m_length = 0;

IL_0016: // ldarg.0
    temp27 = pThis;

IL_0017: // ldfld: Char* m_buffer
    temp28 = (*pThis)->m_buffer;

IL_001c: // ldc.i4.0
IL_001d: // conv.u
    temp29 = (Int32)(UInt32)(0);

IL_001e: // ceq
    temp30 = (temp28 == (Char*)temp29);

IL_0020: // ldc.i4.0
IL_0021: // ceq
    temp31 = (temp30 == 0);

IL_0023: // stloc.0
    local0 = temp31;

IL_0024: // ldloc.0
    temp32 = local0;

IL_0025: // brtrue.s: 2
    if (temp32 != 0)
        goto IL_0029;

IL_0027: // br.s: 36
    goto IL_004d;

IL_0029: // br.s: 15
    goto IL_003a;

IL_002b: // ldarg.0
    temp33 = pThis;

IL_002c: // dup
    (*temp34) = *(pThis);

IL_002d: // ldfld: UInt16 m_length
    temp35 = (*temp34)->m_length;

IL_0032: // ldc.i4.1
IL_0033: // add
    temp36 = ((Int32)temp35 + 1);

IL_0034: // conv.u2
    temp37 = (Int32)(UInt16)(temp36);

IL_0035: // stfld: UInt16 m_length
    (*pThis)->m_length = temp37;

IL_003a: // ldarg.1
    temp38 = pStr;

IL_003b: // dup
    temp39 = pStr;

IL_003c: // ldc.i4.2
IL_003d: // conv.i
    temp40 = (Int32)2;

IL_003e: // add
    temp41 = ((Int32)temp39 + temp40);

IL_003f: // starg.s: Char* pStr
    pStr = (Char*)(temp41);

IL_0041: // ldind.u2
    temp42 = ((UInt16)*(UInt16*)pStr);

IL_0042: // ldc.i4.0
IL_0043: // ceq
    temp43 = (temp42 == (UInt16)0);

IL_0045: // ldc.i4.0
IL_0046: // ceq
    temp44 = (temp43 == 0);

IL_0048: // stloc.0
    local0 = temp44;

IL_0049: // ldloc.0
    temp45 = local0;

IL_004a: // brtrue.s: -33
    if (temp45 != 0)
        goto IL_002b;

IL_004c: // nop
IL_004d: // ret
    goto Exit;

Exit:
    pThread->StackPointer -= 12;
}

I'm baffled. How did your compiler generate this line?

IL_0041: // ldind.u2
temp42 = ((UInt16)*(UInt16*)pStr);

Since we talk that the stack contains values and not variables, how did pStr got in this statement? It should be temp38 instead.

7 hours ago,Dexter wrote

I'm baffled. How did your compiler generate this line?

1 2	IL_0041: // ldind.u2 temp42 = ((UInt16)*(UInt16*)pStr);

Since we talk that the stack contains values and not variables, how did pStr got in this statement? It should be temp38 instead.

Yea good question. I reverted the changes I made to generate the temp variables because that was obviously not the ultimate solution.

My current idea is to load the variable names onto the stack just like I did before, but then when the variable gets popped, to step back through all of the previous instructions (up until the point it got pushed) and see if anything modified the variable since it was pushed. If so, it will go back and swap it out for a temp variable. It will also swap it out for a temp variable if any instructions inbetween are targets for any branch instruction (in case other code modified the variable).

The above solution should cut down dramatically on the number of temp locals. But now until I implement that, I might not be able to get back to this problem.

I plan to copy the above code into a simple function and play around with the code to see if using temp variables in the right places solves the problem. I'm sure it it related to not using temp variables in the right places, just like you mention. Once I understand exactly what the code is supposed to look like, I will make sure my compiler does the right thing.

 to step back through all of the previous instructions (up until the point it got pushed)

Hmm, this is very easy to do when the push and pop are in the same basic block. If they're in different blocks then things can get complicate. One thing that you should note about these temporaries is that they have limited lifetime. Once a temporary is popped it can be reused to store another value.

IMO, you're trying to get things working and optimize the code at the same time. I think it's better to just get things working first.

10 minutes ago,Dexter wrote

*snip*

Hmm, this is very easy to do when the push and pop are in the same basic block. If they're in different blocks then things can get complicate.

Yes that is why I think I should take into account when branch instructions come inbetween the push and pop instructions. Better to err on the safe side and create temp variables. However I don't think this will add a lot of temp variables because what I find with IL code is that the instructions are grouped pretty tightly. It pushes a few variables, then immediately pops them to perform some operation. I have not seen many cases where it pushes something then goes off to do something else first.

One thing that you should note about these temporaries is that they have limited lifetime. Once a temporary is popped it can be reused to store another value.

Yes I plan to have a temp variable pool, and when a temp is popped, it is freed back to the pool. If a following instruction needs a temp of the same type, it will get that freed variable.

IMO, you're trying to get things working and optimize the code at the same time. I think it's better to just get things working first.

True, but I always feel that if you know an area of the code needs to execute fast, at least try to keep that in mind so that you don't have to come back later and completely rewrite everything because it was the wrong approach. Also note that one of the goals of this project is to see how much I can outperform the .Net Micro Framework, so some dabbling in various performance tests along the way to see how viable all of this is, is fine I think.

Yes I plan to have a temp variable pool, and when a temp is popped, it is free back to the pool. If a following instruction needs a temp of the same size, it will get that freed variable.

Why? The compiler will find it much easier to optimise your temporaries to use less registers and stack space (on release builds) than you will, but doing it manually will force to compiler to take worse optimisations.

Make sure you don't ever do performance testing on a debug build, or you'll get a really strange impression of what code is fast and what code is slow.

@evildictaitor:

The C++ compiler will not be able to optimize my ref types away (and it shouldn't), because I store them on the virtual stack. Creating large numbers of temp ref types is not ideal because that will give more work to the GC, in addition to requiring a larger virtual stack (memory is quite limited on a microcontroller).

It should not be too difficult to implement a mechanism like I described to reduce the number of temp variables used. In addition, it makes debugging the C++ code easier if there aren't a huge amount of temp variables. Also remember that the C# method we are looking at is only about  6 lines of code, and it created 45 temp variables. This is going to get insane with complex code.

BTW, I had a typo in my previous post, which I fixed:

If a following instruction needs a temp of the same type [size -> type], it will get that freed variable.