#define BINARY_OP(returnType, type1, type2, op) \
{ \
register PTR pRet = pCurEvalStack - sizeof(type1) - sizeof(type2); \
pCurEvalStack = pRet + sizeof(returnType); \
*(returnType*)pRet = *(type1*)pRet op *(type2*)(pRet + sizeof(type1)); \
}
BINARY_OP(I32, I32, I32, +);
004117BA mov eax,dword ptr [pCurEvalStack]
004117BD sub eax,8
004117C0 mov dword ptr [pRet],eax
004117C6 mov ecx,dword ptr [pRet]
004117CC add ecx,4
004117CF mov dword ptr [pCurEvalStack],ecx
004117D2 mov edx,dword ptr [pRet]
004117D8 mov eax,dword ptr [edx]
004117DA mov ecx,dword ptr [pRet]
004117E0 add eax,dword ptr [ecx+4]
004117E3 mov edx,dword ptr [pRet]
004117E9 mov dword ptr [edx],eax
And this is with all optimisations turned on. How depressing.
I just isolated the use of the BINARY_OP macro, and put it in a simple-ish test function. now it's being optimized excellently.
The function that contains the apparently unoptimisable code is in a hugely long and complex function, and I wonder if something in it is preventing all optimisation from occuring within that function. I've quickly looked through the assembly produced in the function and all of it appears unoptimised; whereas code in other functions is optimised ok.
What can prevent all optimisation from occuring in a function?
If you could break the function up in to pieces, and see if it still doesn't optimize.
The whole source file is here: http://pastebin.com/9L8N3AVF
The function starts at line 232, and the disassembly I was looking at is from line 1852.
This is the function that implements the direct-threaded interpreter. Direct-threading works by using goto's (jmp's) to dispatch the next instruction to be interpreted, which means that I don't think it can be broken up into multiple smaller functions.
Please let me know if you think I'm wrong :)
Things that the function contains that might disable optimization: a lot of gotos, inline assembly in GO_NEXT (this does affect optimization: http://msdn.microsoft.com/en-us/library/5hd5ywk0.aspx)...
It's also not immediately obvious to me that pCurEvalStack is initialized.
Having a look at the architecture optimization manual re: the redundant loads; it's not immediately obvious to me that modern processors won't handle this fine (http://www.intel.com/Assets/PDF/manual/248966.pdf).
pCurEvalStack = TestAdd(pCurEvalStack);
0040BFFA mov eax,dword ptr [pCurEvalStack]
0040BFFD mov dword ptr [ebp-694h],eax
0040C003 mov ecx,dword ptr [ebp-694h]
0040C009 sub ecx,8
0040C00C mov dword ptr [ebp-690h],ecx
0040C012 mov edx,dword ptr [ebp-694h]
0040C018 sub edx,4
0040C01B mov dword ptr [ebp-694h],edx
0040C021 mov eax,dword ptr [ebp-690h]
0040C027 mov ecx,dword ptr [eax]
0040C029 mov edx,dword ptr [ebp-694h]
0040C02F add ecx,dword ptr [edx]
0040C031 mov eax,dword ptr [ebp-690h]
0040C037 mov dword ptr [eax],ecx
0040C039 mov ecx,dword ptr [ebp-694h]
0040C03F mov dword ptr [pCurEvalStack],ecx
And pCurEvalStack is initialised in the LOAD_METHOD_STATE macro, referenced first on line 590, before interpretation begins.
I don't know what limits the compiler imposes, but I wouldn't be surprised if you hit them.
Ask yourself, do you even need a function that large? You might already be approaching the limits of the L1 cache, at which point you might as well be using separate functions since the call itself will be negligible to the cache miss.
Now I'm reasonably certain that the C standard does not allow inline assembly like this. However, given the decades of legacy software that Microsoft has to contend with I would not be too surprised if this was part of the reason.
By the way, GCC's computed gotos are not actually much better. In this case you get a control flow graph where you cannot split all critical edges. There is a workaround for this, but it's probably easier to just disable all optimizations that depend on it.
And almost all of the C code that I would like to be optimised is in short fairly self-contained statements that use their own local variables, so I would expect Again, I've tested this in a smaller function and good optimisation is done.
Therefore I am coming to the conclusion that the problem may just be the length of the function.
I don't have time to do it now, but next week I'll experiment with function length, although as I stated ealier - I'm fairly sure that a threaded interpreter has to be all implemented within a single function.
Same result both times.
This is the assembly produced by the Microsoft C compiler for the part of my interpreter that adds two 32-bit integers together.
This code is executed whenever the .NET IL 'add' opcode is encountered when the two top evaluation stack values are 32-bit integers.
(Note that the evaluation stack type analysis is done in a pre-execution stage, so when the code shown is executing it is already known that the top two stack values are 32-bit integers)
The .NET IL is stack-based which the interpreter runs directly, so it will never be as efficient as LuaJits register-based approach, but I was somewhat disappointed to see this as the output of the Windows VS2008 C compiler in release mode (enables all optimizations):
The assembly after 'BINARY_OP(...)' is the integer add code. pCurEvalStack points to the top of the current evaluation stack. Binary ops are performed on the top two items on the stack, and pushing the result back onto the stack.The assembly after 'GO_NEXT()' is the standard epilogue, which just dispatches the next instruction (see http://en.wikipedia.org/wiki/Threaded_code#Direct_threading for description of direct-threading).
There are 3 seperate loads of the same memory address, which surely can be done better.
I'll probably have a go at altering the definition of the BINARY_OP(...) macro to see if I can persuade it to generate better code. I'm not keen to hand-write the assembly for this as it can compile to multiple processors.
The macro is currently defined as:
...which can probably be improved, or at least specialised to give better results for binary ops where the operand and result types are all the same - e.g. integer addition.