Al's Game Programming Blog

Today I worked on making the code generated by my translator a little less verbose. My strategy was to try and reconstruct the original C# expressions by analyzing the stack operations carried out by the IL assembly. This turned out to be quite straightforward. The main complication was aliasing. Unlike Java byte-code, MSIL byte-code permits variables to be aliased. I worked around this by only attempting to transform stack operations back into expressions between places where aliasing might occur.

For fun, I implemented Euclid's algorithm in C# and translated it to C++. Euclid's algorithm is one of the oldest formally described algorithms. It was originally described in "Elements" around 400BC, before the invention of algebra. Does that mean computer science predates mathematics? It was described in terms of geometric constructions. 2400 years later it is still in widespread use.

Anyway, this was my implementation:

static uint GCD(uint a, uint b)

{

    if (b == 0)

    {

        return a;

    }

    else

    {

        return GCD(b, a % b);

    }

}

And my C# to C++ translators output:

UInt32 GCD(UInt32 a, UInt32 b)

{

	Int si0;

	{

		UInt32 CS_36_1_36_0000;

		Int8 CS_36_4_36_0001;

		CS_36_4_36_0001 = Int(Int(Int(b) == Int(0)) == Int(0));

		if (Int(CS_36_4_36_0001)) goto L15;

		CS_36_1_36_0000 = Int(a);

		goto L27;

		L15: si0 = ::Test1::Program::GCD((UInt32) Int(b),

			(UInt32) Int(UInt(a) % UInt(b)));

		CS_36_1_36_0000 = Int(si0);

		goto L27;

		L27: return Int(CS_36_1_36_0000);

	}

}

Much less verbose! And there are still some improvements I can make. Here is the x86 disassembly of the compiled translation:

PUBLIC	?GCD@Program@Test1@@YAIII@Z

; Function compile flags: /Ogty

;	COMDAT ?GCD@Program@Test1@@YAIII@Z

_TEXT	SEGMENT

_a$ = 8

_b$ = 12

?GCD@Program@Test1@@YAIII@Z PROC NEAR

; Line 48

	mov	ecx, DWORD PTR _b$[esp-4]

	test	ecx, ecx

; Line 52

	mov	eax, DWORD PTR _a$[esp-4]

$L15$1360:

	je	SHORT $L27$1362

	xor	edx, edx

	div	ecx

	mov	DWORD PTR _b$[esp-4], edx

	mov	DWORD PTR _a$[esp-4], ecx

	jmp	?GCD@Program@Test1@@YAIII@Z

$L27$1362:

; Line 57

	ret	0

?GCD@Program@Test1@@YAIII@Z ENDP

_TEXT	ENDS

So it seems that, by using C++ as an intermediate language, C# programs can be compiled into quite reasonable native code. Notice that the C++ compiler was able to apply the tail recursion optimization.