前回長くなりすぎたので、追記分を分けておくことにした。
前回は簡易fizzbazzを逆アセンブルし、割り算の最適化に関して面白いものを見たのだった。
その続きとして、moduloではなく普通の割り算はどうなるんだろう、と思って以下のようなコードを書いてみた。
#include <stdint.h> int32_t div_by3(int32_t a) { return a / 3; } int32_t div_by4(int32_t a) { return a / 4; } int32_t div(int32_t a, int32_t b) { return a / b; }
逆アセンブルする。予想としては、div_by3は先のマジックナンバーを使った方法を、div_by4はsarで右シフトを、divは普通にidiv命令を使うというものだ。
それがたとえ-O0であったとしても。
結果は、
division.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <div_by3>: 0: push %rbp 1: mov %rsp,%rbp 4: mov %edi,-0x4(%rbp) 7: mov -0x4(%rbp),%ecx a: mov $0x55555556,%edx f: mov %ecx,%eax 11: imul %edx 13: mov %ecx,%eax 15: sar $0x1f,%eax 18: sub %eax,%edx 1a: mov %edx,%eax 1c: pop %rbp 1d: retq 000000000000001e <div_by4>: 1e: push %rbp 1f: mov %rsp,%rbp 22: mov %edi,-0x4(%rbp) 25: mov -0x4(%rbp),%eax 28: lea 0x3(%rax),%edx 2b: test %eax,%eax 2d: cmovs %edx,%eax 30: sar $0x2,%eax 33: pop %rbp 34: retq 0000000000000035 <div>: 35: push %rbp 36: mov %rsp,%rbp 39: mov %edi,-0x4(%rbp) 3c: mov %esi,-0x8(%rbp) 3f: mov -0x4(%rbp),%eax 42: cltd 43: idivl -0x8(%rbp) 46: pop %rbp 47: retq
ほぼ予想通りだ。見慣れたマジックナンバーと、sar命令がある。ただ、先に3を引いて符号によってはそちらを使っていたりするのが面白い。そしてそこでは（-O0なのに）減算命令ではなくアドレス演算を使っている。
長くなっているのは、最適化レベル以外にも多分、以上のような符号に由来するいくつかの面倒が理由にあるのだろう。
単に下の形に即値3や4を入れてもいいのにそうしないあたりが、除算命令の嫌われぶりを意味している気がする。多分最適化で定数伝播したらまっさきにこのdivとか消えるんだろうなと思うと少しかわいそう。
面倒な計算のいくつかが符号によるものではないかと思いついた以上、uint32_tを試さざるを得ない。
division.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <div_by3>: 0: push %rbp 1: mov %rsp,%rbp 4: mov %edi,-0x4(%rbp) 7: mov -0x4(%rbp),%eax a: mov $0xaaaaaaab,%edx f: mul %edx 11: mov %edx,%eax 13: shr %eax 15: pop %rbp 16: retq 0000000000000017 <div_by4>: 17: push %rbp 18: mov %rsp,%rbp 1b: mov %edi,-0x4(%rbp) 1e: mov -0x4(%rbp),%eax 21: shr $0x2,%eax 24: pop %rbp 25: retq 0000000000000026 <div>: 26: push %rbp 27: mov %rsp,%rbp 2a: mov %edi,-0x4(%rbp) 2d: mov %esi,-0x8(%rbp) 30: mov -0x4(%rbp),%eax 33: mov $0x0,%edx 38: divl -0x8(%rbp) 3b: pop %rbp 3c: retq
少し短くなった。そしてマジックナンバーが変わっている。面倒なので追わないが。算術右シフトがただの右シフトになっていたり、帳尻合わせと思しきtestやsubが消えている。
それぞれ最適化するとどうなるのだろう。符号付きは、
division.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <div_by3>: 0: mov %edi,%eax 2: mov $0x55555556,%edx 7: sar $0x1f,%edi a: imul %edx c: mov %edx,%eax e: sub %edi,%eax 10: retq 11: nopl 0x0(%rax,%rax,1) 16: nopw %cs:0x0(%rax,%rax,1) 1d: 0000000000000020 <div_by4>: 20: lea 0x3(%rdi),%eax 23: test %edi,%edi 25: cmovns %edi,%eax 28: sar $0x2,%eax 2b: retq 2c: nopl 0x0(%rax) 0000000000000030 <div>: 30: mov %edi,%eax 32: cltd 33: idiv %esi 35: retq
まあ基本的にはスタックを使わずに済ませるという感じだ。では符号無しならもっと簡単になるのだろうか。その程度なら今の自分の知識でも当てられそうだと思ったので、自力で予想してみる。上の-O0の結果をコピペしてレジスタしか使わないように書き換えてみる。
<div_by3>: mov %edi,%eax mov $0xaaaaaaab,%edx mul %edx mov %edx,%eax shr %eax retq <div_by4>: mov %edi,%eax shr $0x2,%eax retq <div>: mov %edi,%eax mov $0x0,%edx divl %esi retq
予想と言っても単にスタックに置いたあとレジスタにロードしている部分をレジスタ間移動に書き換えただけだが。 では答え合わせをしよう。
division.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <div_by3>: 0: mov %edi,%eax 2: mov $0xaaaaaaab,%edx 7: mul %edx 9: mov %edx,%eax b: shr %eax d: retq e: xchg %ax,%ax 0000000000000010 <div_by4>: 10: mov %edi,%eax 12: shr $0x2,%eax 15: retq 16: nopw %cs:0x0(%rax,%rax,1) 1d: 0000000000000020 <div>: 20: mov %edi,%eax 22: xor %edx,%edx 24: div %esi 26: retq
思っていたよりも予想と合致していて自分で驚いた。違うところといえば、22:の部分で即値0をロードするのでなくxorでゼロクリア(?)しているくらいだ。これらの手法で速度に差があるのだろうか。あとちゃんとゼロクリアされるんだろうか。自分自身との排他的論理和なので、これは必ずゼロクリアされる。しかし、値に依存してビットを変えねばならないxorよりも、何も考えずにゼロ埋めするmov $0x0の方が早そうに思うのだがこれは何か理由があるのだろうか。それと、気づきにくかったがdivl命令だったのがdivになっている。何故だ。レジスタの呼び方だけでサイズがわかるからだろうか。
まあ、でも一からこれを書くのは難しい（というかできない）よな、というのが正直な感想だ。コンパイラが非常に賢いという実感を改めた。
さて、こうなるとコンパイラがどこまで賢いのか少し試してみたくなる。まず、私は定数伝播のことを知っているので、実際に起きるか試してみたい。あ、そういえばずっとコンパイラのバージョンを言っていなかったので置いておこう。
$ gcc --version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609 Copyright (C) 2015 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
まず、コンパイラが関数の実装をそのまま見に行ける状況を考えたい。
#include <stdint.h> uint32_t div(uint32_t a, uint32_t b) { return a / b; } int main() { int retval = div(5, 3); return retval; }
これを逆アセンブルする。
$ gcc -std=c99 -Ofast -pedantic -c main.c && objdump -d main.o > main.asm
main.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <div>: 0: mov %edi,%eax 2: xor %edx,%edx 4: div %esi 6: retq Disassembly of section .text.startup: 0000000000000000 <main>: 0: mov $0x1,%eax 5: retq
mainが何もせずに即値を返す関数になっている。ただし、他とリンクする可能性があるからか（今回はコンパイルのみ行った）divの実装も削除されずに残っている。じゃあコンパイル・リンクを済ませて実行可能ファイルを作ったらどうなるのだろうと思ってやってみた。
$ gcc -std=c99 -Ofast -pedantic main.c && objdump -d a.out > a.asm
長くなるので載せないが、divはあった。この状況ではデッドコードと判定されないらしい。mainが定数を返すだけの関数なのは同じだったが。
では、翻訳単位を分けてみよう。ヘッダを作って、
#include <stdint.h> uint32_t div(uint32_t a, uint32_t b);
実装と、
#include "division.h" uint32_t div(uint32_t a, uint32_t b) { return a / b; }
mainに分ける。
#include "division.h" int main() { int retval = div(5, 3); return retval; }
この状態でファイルを一緒に渡してコンパイルしてみる。
$ gcc -std=c99 -Ofast -pedantic main.c division.c && objdump -d a.out > a.asm
いらないところは取り除いてmainとdivだけ示すと、
Disassembly of section .text: 0000000000400410 <main>: 400410: mov $0x3,%esi 400415: mov $0x5,%edi 40041a: jmpq 400540 <div> 40041f: nop 0000000000400540 <div>: 400540: mov %edi,%eax 400542: xor %edx,%edx 400544: div %esi 400546: retq 400547: nopw 0x0(%rax,%rax,1) 40054e:
mainが引数をレジスタesi、ediへ格納してdivへジャンプしている。関数呼び出しが残ってしまった。
そうなると分けてコンパイルして後でリンクしても当然同じになるだろう。やはり最適化のためにはinlineしかないのだろうか。
だが、我々はLTO(Link Time Optimization)を知っている。さっきのオプションにこれを追加してみよう。
$ gcc -std=c99 -Ofast -pedantic -flto main.c division.c && objdump -d a.out > a.asm
1秒以下ではあるが、一瞬止まったのが感じられる程度の時間が経過した後、出てきたmainは以下のようなものだった。
Disassembly of section .text: 00000000004003e0 <main>: 4003e0: mov $0x1,%eax 4003e5: retq 4003e6: nopw %cs:0x0(%rax,%rax,1) 4003ed:
即値を返すようになっている。LTOは効果があるのだ。もうひとつ驚いたことに、今度はdivが消えている。さっき実装も与えてコンパイルした場合は残っていたdivが、だ。リンクまで済んだ、ということが明確になるからだろうか。あるいは、リンク時最適化で関数のコール関係が明らかになり、判定できるようになったのか。このあたりはリンカの実装にも依存しそうなのでよくわからない。
では、これはどのように動いているのだろう。私の推測は、オブジェクトファイルのそれぞれに情報を少し追加し、リンク時にそれを読み取って全体のパスを一度再構築し、それに基づいて最適化するというものだ。もしそうならば、-fltoをつけずにコンパイルしたオブジェクトを-flto付きでリンクしても効果はないということになる。最適化に必要な情報がオブジェクトファイルに入っていないのだから。
では試そう。-fltoなしで双方コンパイルし、後でリンクする。
$ gcc -std=c99 -Ofast -pedantic -c main.c $ gcc -std=c99 -Ofast -pedantic -c division.c $ gcc -std=c99 -Ofast -pedantic -flto main.c division.c -o wo_lto.out
mainはdivへジャンプした。LTOはこのやり方では上手く動かない。
$ gcc -std=c99 -Ofast -pedantic -flto -c main.c $ gcc -std=c99 -Ofast -pedantic -flto -c division.c $ gcc -std=c99 -Ofast -pedantic -flto main.c division.c -o w_lto.out
mainは即値を返すようになった。ここでもまたdivが消えている。コンパイル時に-fltoオプションが効いていないとLTOは働かないのだ。
コンパイラの最適化は面白い。数カ月前、この人のブログ記事を読み漁っていた。
たくさんの最適化手法の紹介がなされており、非常に興味深い（他の話題もあるが）。たしか見つけた切っかけはRange-v3の最適化の記事だったと思う。
