デコンパイル&リコンパイルをやってみた

エミュレータは内部で機械語のリコンパイルをして速度向上を図っている。だが自分のノートパソコンではリコンパイルを有効にしても実機と同等の速度で動かすことができなかった。そこでソースコードを落として調べてみようとしたのだが、余り時間がなくて深く読むことができない。とりあえず読んだ感じでは実機の機械語と1対1のコードを生成していたような気がする。
ここで一つアイデアが浮かんだ。実機の機械語を一度Cにデコンパイルし、その後別の最適化コンパイラを使ってネイティブなコードを吐かせてみてはどうか?ネイティブなCPUが持つ拡張命令も使えてお得なのではないか?コンパイラによっては自動ベクトル化とかもやってくれるのではないか?ということで、実機のアセンブラを勉強する時間がないので、手元のi386マシンで試してみた。
検証に使用したコードは以下のエラトステネスのふるいのコード。コンセプト証明が出来れば良いので簡単なコードにした。いずれもCygwin+gcc3.4.4で行っている。

static const int MAX = 10000000;
static bool prime[MAX];
int main()
{
	for (int i = 0; i < MAX; ++i){
		prime[i] = true;
	}
	prime[0] = prime[1] = false;
	for (int i = 2; i < MAX; ++i){
		for (int j = i * 2; j < MAX; j += i){
			prime[j] = false;
		}
	}
}

続いて最適化オプションを付けないでコンパイルして出力されるアセンブラ

	.file	"test.original.cpp"
.lcomm _prime,10000000
	.def	___main;	.scl	2;	.type	32;	.endef
	.text
	.align 2
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$24, %esp
	andl	$-16, %esp
	movl	$0, %eax
	addl	$15, %eax
	addl	$15, %eax
	shrl	$4, %eax
	sall	$4, %eax
	movl	%eax, -12(%ebp)
	movl	-12(%ebp), %eax
	call	__alloca
	call	___main
	movl	$0, -4(%ebp)
L2:
	cmpl	$9999999, -4(%ebp)
	jg	L3
	movl	-4(%ebp), %eax
	addl	$_prime, %eax
	movb	$1, (%eax)
	leal	-4(%ebp), %eax
	incl	(%eax)
	jmp	L2
L3:
	movb	$0, _prime+1
	movb	$0, _prime
	movl	$2, -4(%ebp)
L5:
	cmpl	$9999999, -4(%ebp)
	jg	L6
	movl	-4(%ebp), %eax
	addl	%eax, %eax
	movl	%eax, -8(%ebp)
L8:
	cmpl	$9999999, -8(%ebp)
	jg	L7
	movl	-8(%ebp), %eax
	addl	$_prime, %eax
	movb	$0, (%eax)
	movl	-4(%ebp), %edx
	leal	-8(%ebp), %eax
	addl	%edx, (%eax)
	jmp	L8
L7:
	leal	-4(%ebp), %eax
	incl	(%eax)
	jmp	L5
L6:
	movl	$0, %eax
	leave
	ret
	.section .rdata,"dr"
	.align 4
_MAX:
	.long	10000000

続いて最適化オプションありでコンパイルして出力されたアセンブラ

	.file	"test.original.cpp"
.lcomm _prime,10000000
	.def	___main;	.scl	2;	.type	32;	.endef
	.text
	.align 2
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	subl	$8, %esp
	andl	$-16, %esp
	call	__alloca
	call	___main
	xorl	%eax, %eax
	.p2align 4,,15
L5:
	movb	$1, _prime(%eax)
	incl	%eax
	cmpl	$9999999, %eax
	jle	L5
	movb	$0, _prime+1
	movl	$2, %edx
	movb	$0, _prime
	.p2align 4,,15
L13:
	leal	(%edx,%edx), %eax
	jmp	L20
	.p2align 4,,7
L22:
	movb	$0, _prime(%eax)
	addl	%edx, %eax
L20:
	cmpl	$9999999, %eax
	jle	L22
	incl	%edx
	cmpl	$9999999, %edx
	jle	L13
	leave
	xorl	%eax, %eax
	ret

とりあえずそれぞれ手動でCのコードに変換してみる。

//	.file	"test.original.cpp"
//.lcomm _prime,10000000
static char _prime[100000000];

//	.def	___main;	.scl	2;	.type	32;	.endef
//	.text
//	.align 2
//.globl _main
//	.def	_main;	.scl	2;	.type	32;	.endef
int main()
{
	long eax = 0;
	long edx = 0;
	union {
		char ebp_c[8];
		short ebp_s[4];
		long ebp_l[2];
	};
	//_main:
	//	pushl	%ebp
	//	movl	%esp, %ebp
	//	subl	$24, %esp
	//	andl	$-16, %esp
	//	movl	$0, %eax
	//	addl	$15, %eax
	//	addl	$15, %eax
	//	shrl	$4, %eax
	//	sall	$4, %eax
	//	movl	%eax, -12(%ebp)
	//	movl	-12(%ebp), %eax
	//	call	__alloca
	//	call	___main
	//	movl	$0, -4(%ebp)
	ebp_l[1] = 0;

	//L2:
L2:
	//	cmpl	$9999999, -4(%ebp)
	//	jg	L3
	if (ebp_l[1] > 9999999){
		goto L3;
	}
	//	movl	-4(%ebp), %eax
	eax = ebp_l[1];
	//	addl	$_prime, %eax
	eax += (long)_prime;
	//	movb	$1, (%eax)
	*(char*)eax = 1;
	//	leal	-4(%ebp), %eax
	eax = (long)&ebp_l[1];
	//	incl	(%eax)
	++(*(long*)eax);
	//	jmp	L2
	goto L2;

	//L3:
L3:
	//	movb	$0, _prime+1
	_prime[1] = 0;
	//	movb	$0, _prime
	_prime[0] = 0;
	//	movl	$2, -4(%ebp)
	ebp_l[1] = 2;

	//L5:
L5:
	//	cmpl	$9999999, -4(%ebp)
	//	jg	L6
	if (ebp_l[1] > 9999999){
		goto L6;
	}
	//	movl	-4(%ebp), %eax
	eax = ebp_l[1];
	//	addl	%eax, %eax
	eax += eax;
	//	movl	%eax, -8(%ebp)
	ebp_l[0] = eax;

	//L8:
L8:
	//	cmpl	$9999999, -8(%ebp)
	//	jg	L7
	if (ebp_l[0] > 9999999){
		goto L7;
	}
	//	movl	-8(%ebp), %eax
	eax = ebp_l[0];
	//	addl	$_prime, %eax
	eax += (long)_prime;
	//	movb	$0, (%eax)
	*(char*)eax = 0;
	//	movl	-4(%ebp), %edx
	edx = ebp_l[1];
	//	leal	-8(%ebp), %eax
	eax = (long)&ebp_l[0];
	//	addl	%edx, (%eax)
	*(long*)eax += edx;
	//	jmp	L8
	goto L8;

	//L7:
L7:
	//	leal	-4(%ebp), %eax
	eax = (long)&ebp_l[1];
	//	incl	(%eax)
	++(*(long*)eax);
	//	jmp	L5
	goto L5;

	//L6:
L6:
	//	movl	$0, %eax
	eax = 0;
	//	leave
	//	ret
	//	.section .rdata,"dr"
	//	.align 4
	//_MAX:
	//	.long	10000000
}
//	.file	"test.cpp"
//.lcomm _prime,10000000
static char _prime[100000000];

//	.def	___main;	.scl	2;	.type	32;	.endef
//	.text
//	.align 2
//	.p2align 4,,15
//.globl _main
//	.def	_main;	.scl	2;	.type	32;	.endef
int main()
{
	long eax = 0;
	long edx = 0;
	union {
		char ebp_c[8];
		short ebp_s[4];
		long ebp_l[2];
	};

	//_main:
	//	pushl	%ebp
	//	movl	$16, %eax
	//	movl	%esp, %ebp
	//	subl	$8, %esp
	//	andl	$-16, %esp
	//	call	__alloca
	//	call	___main
	//	xorl	%eax, %eax
	eax = 0;

	//	.p2align 4,,15

	//L5:
L5:
	//	movb	$1, _prime(%eax)
	_prime[eax] = 1;
	//	incl	%eax
	++eax;
	//	cmpl	$9999999, %eax
	//	jle	L5
	if (eax <= 9999999){
		goto L5;
	}
	//	movb	$0, _prime+1
	_prime[1] = 0;
	//	movl	$2, %edx
	edx = 2;
	//	movb	$0, _prime
	_prime[0] = 0;
	//	.p2align 4,,15

	//L13:
L13:
	//	leal	(%edx,%edx), %eax
	eax = edx + edx;

	//	jmp	L20
	goto L20;
	//	.p2align 4,,7
	//L22:
L22:
	//	movb	$0, _prime(%eax)
	_prime[eax] = 0;
	//	addl	%edx, %eax
	eax += edx;
	//L20:
L20:
	//	cmpl	$9999999, %eax
	//	jle	L22
	if (eax <= 9999999){
		goto L22;
	}
	//	incl	%edx
	++edx;
	//	cmpl	$9999999, %edx
	//	jle	L13
	if (edx <= 9999999){
		goto L13;
	}
	//	leave
	//	xorl	%eax, %eax
	eax = 0;
	//	ret
}

それぞれをもう一度最適化オプションありでコンパイルして出力されたアセンブラ

	.file	"test.normal.cpp"
.lcomm __prime,100000000
	.def	___main;	.scl	2;	.type	32;	.endef
	.text
	.align 2
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	subl	$8, %esp
	andl	$-16, %esp
	call	__alloca
	call	___main
	movl	$0, -4(%ebp)
	leal	-8(%ebp), %edx
	jmp	L2
L13:
	movb	$1, __prime(%eax)
	incl	4(%edx)
L2:
	movl	4(%edx), %eax
	cmpl	$9999999, %eax
	jle	L13
L4:
L5:
	movb	$0, __prime+1
	movb	$0, __prime
	movl	$2, 4(%edx)
	movl	4(%edx), %eax
	cmpl	$9999999, %eax
	jg	L7
L15:
	addl	%eax, %eax
	jmp	L11
	.p2align 4,,7
L14:
	movb	$0, __prime(%eax)
	movl	4(%edx), %ecx
	movl	-8(%ebp), %eax
	addl	%ecx, %eax
L11:
L8:
	movl	%eax, -8(%ebp)
	cmpl	$9999999, %eax
	jle	L14
L10:
	incl	4(%edx)
	movl	4(%edx), %eax
	cmpl	$9999999, %eax
	jle	L15
L7:
	leave
	xorl	%eax, %eax
	ret
	.file	"test.optimize.cpp"
.lcomm __prime,100000000
	.def	___main;	.scl	2;	.type	32;	.endef
	.text
	.align 2
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	subl	$8, %esp
	andl	$-16, %esp
	call	__alloca
	call	___main
	xorl	%eax, %eax
	.p2align 4,,15
L2:
	movb	$1, __prime(%eax)
	incl	%eax
	cmpl	$9999999, %eax
	jle	L2
	movb	$0, __prime+1
	movl	$2, %edx
	movb	$0, __prime
L4:
	leal	(%edx,%edx), %eax
	jmp	L5
	.p2align 4,,7
L6:
	movb	$0, __prime(%eax)
	addl	%edx, %eax
L5:
	cmpl	$9999999, %eax
	jle	L6
	incl	%edx
	cmpl	$9999999, %edx
	jle	L4
	leave
	xorl	%eax, %eax
	ret

最後にそれぞれの実行時間

$ g++ test.original.cpp -O2 && time ./a.exe

real    0m2.410s
user    0m2.339s
sys     0m0.015s

$ g++ test.normal.cpp -O2 && time ./a.exe

real    0m2.980s
user    0m2.901s
sys     0m0.016s

$ g++ test.optimize.cpp -O2 && time ./a.exe

real    0m2.470s
user    0m2.401s
sys     0m0.015s

と微妙なところだが、元のソースコードを最適化オプションありでコンパイルして実行した結果と、最適化オプションありでコンパイルして出力されたアセンブラをCに変換してもう一度最適化オプションありでコンパイルして実行した結果(長い!)がほぼ同等となった。より高度のなコンパイラを使えばより最適化されたコードが生成されるかもしれない。
これをエミュレータの高速化に生かすことができるだろうか?