3 ms·
A couple of years ago I wrote a direct-threaded .NET interpreter. This article made me go and have a look at the assembly that is being generated for the simple
by chrisb 15y ago
A couple of years ago I wrote a direct-threaded .NET interpreter. This article made me go and have a look at the assembly that is being generated for the simple 'add' instruction case.
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):
JIT_ADD_I32I32_start:
BINARY_OP(I32, I32, I32, +);
0041164D mov eax,dword ptr [pCurEvalStack]
00411650 sub eax,4
00411653 mov dword ptr [pCurEvalStack],eax
00411656 mov ecx,dword ptr [pCurEvalStack]
00411659 mov edx,dword ptr [ecx-4]
0041165C mov eax,dword ptr [pCurEvalStack]
0041165F add edx,dword ptr [eax]
00411661 mov ecx,dword ptr [pCurEvalStack]
00411664 mov dword ptr [ecx-4],edx
JIT_ADD_I32I32_end:
GO_NEXT();
00411667 mov edi,dword ptr [pCurOp]
0041166A add edi,4
0041166D mov dword ptr [pCurOp],edi
00411670 jmp dword ptr [edi-4]
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 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:
#define BINARY_OP(returnType, type1, type2, op) \
pCurEvalStack -= sizeof(type1) + sizeof(type2) - sizeof(returnType); \
*(returnType*)(pCurEvalStack - sizeof(returnType)) = \
*(type1*)(pCurEvalStack - sizeof(returnType)) op \
*(type2*)(pCurEvalStack - sizeof(returnType) + sizeof(type1))
...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.
- chrisb 15y agoFrustratingly, I just changed the macro to this: #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)); \ } And the assembly generated is this: 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 which is still unimaginably terrible. Why isn't it re-using values that have already been loaded into registers? Why isn't it using a register for pRet? I've even told it to! Although I think it's documented that the MS compiler ignores the 'register' keyword. And this is with all optimisations turned on. How depressing.
- maximilianburke 15y agoMost compilers completely ignore "register" these days. I believe also that aliasing the stack when you're performing the actual operation is greatly hindering the compiler's ability to optimize.
- chrisb 15y agoIt does look as though no optimisation is being performed at all. 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?
- kenjackson 15y agoHow long is long? Is this a code gened function? I've seen in some compilers that they sometimes have limits where they turn off optimization due to throughput issues. If you could break the function up in to pieces, and see if it still doesn't optimize.
- chrisb 15y agoThe function is just over 2900 lines long. Every line crafted lovingly by hand. The whole source file is here: http://pastebin.com/9L8N3AVF 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 :)
- 15y ago
- deleted 15y ago[deleted]
- fleitz 15y agoIt that what NGEN really generates or is that what your interpreter generated?
- chrisb 15y agoThis is nothing to do with NGEN. 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)