デコンパイル&リコンパイルをやってみた
某エミュレータは内部で機械語のリコンパイルをして速度向上を図っている。だが自分のノートパソコンではリコンパイルを有効にしても実機と同等の速度で動かすことができなかった。そこでソースコードを落として調べてみようとしたのだが、余り時間がなくて深く読むことができない。とりあえず読んだ感じでは実機の機械語と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に変換してもう一度最適化オプションありでコンパイルして実行した結果(長い!)がほぼ同等となった。より高度のなコンパイラを使えばより最適化されたコードが生成されるかもしれない。
これをエミュレータの高速化に生かすことができるだろうか?