Posted at

コンパイラによるリンク時最適化(Link Time Optimization)

More than 1 year has passed since last update.


はじめに

一般に、コンパイラによる最適化は局所的であればあるほど効きやすい。例えば同じ関数内ならできる最適化が、グローバル変数がからむとできなくなったり、ファイルをまたぐとできなくなったりする。しかし、最近はリンク時最適化(Link Time Optimization, LTO)と呼ばれる、異なるオブジェクトファイル間にまたがる最適化ができるようになってきた。

ここではいくつかの例で、リンク時最適化として何ができるか紹介してみたいと思う。使うコンパイラは以下の通り。


  • g++ (Homebrew GCC 7.3.0_1) 7.3.0

  • clang++ Apple LLVM version 9.1.0 (clang-902.0.39.2)


リンク時最適化の例

簡単なサンプルを示そう。

こんなコードを考える。

#include <cstdio>

int func() {
return 1;
}

int main() {
printf("%d\n", func());
}

常に1を返す関数funcmain関数から呼び出してその内容を表示するコードである。このコードは、関数をインライン展開し、func()を1に置き換えることができる。俗にいう定数伝播と呼ばれる最適化である。

最適化オプション無しでコンパイルすると、そのままfuncを呼ぶコードを吐く。

_main:

pushq %rbp
movq %rsp, %rbp
call func()
movl %eax, %esi
leaq lC0(%rip), %rdi
movl $0, %eax
call _printf
movl $0, %eax
popq %rbp

call func()の行があるのがわかる。しかし、最適化レベルを上げるとこの行は消える。

$ g++ -O3 -S test.cpp

_main:

subq $8, %rsp
movl $1, %esi
xorl %eax, %eax
leaq lC0(%rip), %rdi
call _printf
xorl %eax, %eax
addq $8, %rsp

関数呼び出しが消え、1が直接printfに渡されるようになったのがわかると思う。

では、funcの実体が他のファイルにあったらどうなるだろう?こんな構成を考える。


test.cpp

int func() {

return 1;
}


main.cpp

#include <cstdio>

int func();
int main(void) {
printf("%d\n", func());
}

これは最適化レベルを上げても最適化できなくなる。

$ g++ -O3 main.cpp test.cpp

$ objdump -d a.out | c++filt
(snip)
_main:
100000f40: 48 83 ec 08 subq $8, %rsp
100000f44: e8 e7 ff ff ff callq -25 <func()>
100000f49: 48 8d 3d 32 00 00 00 leaq 50(%rip), %rdi
100000f50: 89 c6 movl %eax, %esi
100000f52: 31 c0 xorl %eax, %eax
100000f54: e8 07 00 00 00 callq 7
100000f59: 31 c0 xorl %eax, %eax
100000f5b: 48 83 c4 08 addq $8, %rsp
100000f5f: c3 retq
(snip)

実行バイナリにfuncの関数呼び出しが残ってしまうことがわかる。

さて、リンク時最適化(LTO)の出番である。LTOを有効にするには、コンパイル時に-fltoをつける。

$ g++ -O3 -flto -c main.cpp

$ g++ -O3 -flto -c test.cpp

さて、-fltoオプションをつけても、オブジェクトファイルの内容そのものは変更されていない。

-fltoなしの場合の逆アセンブリ

$ g++ -O3 -flto -c main.cpp 

$ objdump -d main.o

main.o: file format Mach-O 64-bit x86-64

Disassembly of section __TEXT,__text_startup:

_main:
10: 48 83 ec 08 subq $8, %rsp
14: e8 00 00 00 00 callq 0 <_main+0x9>
19: 48 8d 3d 00 00 00 00 leaq (%rip), %rdi
20: 89 c6 movl %eax, %esi
22: 31 c0 xorl %eax, %eax
24: e8 00 00 00 00 callq 0 <_main+0x19>
29: 31 c0 xorl %eax, %eax
2b: 48 83 c4 08 addq $8, %rsp
2f: c3 retq

-fltoありの場合の逆アセンブリ

$ g++ -O3 -flto -c main.cpp 

$ objdump -d main.o

main.o: file format Mach-O 64-bit x86-64

Disassembly of section __TEXT,__text_startup:

_main:
10: 48 83 ec 08 subq $8, %rsp
14: e8 00 00 00 00 callq 0 <_main+0x9>
19: 48 8d 3d 00 00 00 00 leaq (%rip), %rdi
20: 89 c6 movl %eax, %esi
22: 31 c0 xorl %eax, %eax
24: e8 00 00 00 00 callq 0 <_main+0x19>
29: 31 c0 xorl %eax, %eax
2b: 48 83 c4 08 addq $8, %rsp
2f: c3 retq

全く違いが無いのがわかる。しかし、-fltoをつけると、オブジェクトファイルのサイズは肥大化する。

$ g++ -O3 -c main.cpp;ls -lh main.o |awk '{print $5}'

976B

$ g++ -O3 -c -flto main.cpp;ls -lh main.o |awk '{print $5}'
3.6K

-fltoをつけることでオブジェクトファイルのサイズが1KBから3.6KBに増加した。これはオブジェクトファイルに中間表現を丸々突っ込んでいるからである。

さて、同様にtest.cpp-fltoをつけてコンパイルし、リンクする。

$ g++ -O3 -c -flto main.cpp      

$ g++ -O3 -c -flto test.cpp
$ g++ -O3 main.o test.o
$ objdump -d a.out | c++filt
(snip)
_main:
100000f50: 48 83 ec 08 subq $8, %rsp
100000f54: be 01 00 00 00 movl $1, %esi
100000f59: 31 c0 xorl %eax, %eax
100000f5b: 48 8d 3d 2c 00 00 00 leaq 44(%rip), %rdi
100000f62: e8 07 00 00 00 callq 7
100000f67: 31 c0 xorl %eax, %eax
100000f69: 48 83 c4 08 addq $8, %rsp
100000f6d: c3 retq
(snip)

関数呼び出しが消え、printfに直接1が渡されるようになったのがわかると思う。

ここで、最後のリンク

$ g++ -O3 main.o test.o

この実行に時間がかかるようになった。これは、オブジェクトファイルに残しておいた中間表現を全部くっつけた上で、コンパイルし直しているからである。従って、-fltoをつけるとリンクにすごく時間がかかるようになる(そこでコンパイルし直しているから)1

全く同様なことがclang++でもできる。そのままでは最適化できないが・・・

$ clang++ -O3 main.cpp test.cpp

$ objdump -d a.out | c++filt
(snip)
_main:
100000f60: 55 pushq %rbp
100000f61: 48 89 e5 movq %rsp, %rbp
100000f64: e8 17 00 00 00 callq 23 <func()>
100000f69: 89 c1 movl %eax, %ecx
100000f6b: 48 8d 3d 3c 00 00 00 leaq 60(%rip), %rdi
100000f72: 31 c0 xorl %eax, %eax
100000f74: 89 ce movl %ecx, %esi
100000f76: e8 11 00 00 00 callq 17
100000f7b: 31 c0 xorl %eax, %eax
100000f7d: 5d popq %rbp
100000f7e: c3 retq
100000f7f: 90 nop
(snip)

-fltoをつけると最適化される。

$ clang++ -O3 -flto main.cpp test.cpp

$ objdump -d a.out | c++filt
(snip)
_main:
100000f70: 55 pushq %rbp
100000f71: 48 89 e5 movq %rsp, %rbp
100000f74: 48 8d 3d 33 00 00 00 leaq 51(%rip), %rdi
100000f7b: be 01 00 00 00 movl $1, %esi
100000f80: 31 c0 xorl %eax, %eax
100000f82: e8 05 00 00 00 callq 5
100000f87: 31 c0 xorl %eax, %eax
100000f89: 5d popq %rbp
100000f8a: c3 retq
(snip)


例2: 条件分岐削除

LTOは、基本的に複数のファイルをバカでかい一つのファイルにまとめて一気に最適化をかけているので、一つのファイルでできることはだいたいできる。例えば、複数ファイルにまたがる条件分岐削除もできる。


test.cpp

int func() {

return 1;
}


main.cpp

#include <cstdio>

int func();
int main() {
if (func() > 0) {
return 0;
} else {
return 1;
}
}

LTO無し

$ g++ -O3 main.cpp test.cpp

$ objdump -d a.out | c++filt
(snip)
_main:
100000f70: 48 83 ec 08 subq $8, %rsp
100000f74: e8 e7 ff ff ff callq -25 <func()>
100000f79: 85 c0 testl %eax, %eax
100000f7b: 0f 9e c0 setle %al
100000f7e: 48 83 c4 08 addq $8, %rsp
100000f82: 0f b6 c0 movzbl %al, %eax
100000f85: c3 retq

LTOあり

$ g++ -O3 -flto main.cpp test.cpp

$ objdump -d a.out | c++filt
(snip)
_main:
100000fa0: 31 c0 xorl %eax, %eax
100000fa2: c3 retq

関数呼び出しが消え、いきなり0を返すようになったのがわかると思う。clang++も同様である。


例3: グローバル変数解析

一般にコンパイラはグローバル変数がからんだ最適化は苦手である。グローバル変数はいつ誰が触るかわからないからだ。例えばこんなコードを書いてみる。


test.cpp

int hoge = 1;



main.cpp

#include <cstdio>

extern int hoge;
int main() {
if (hoge > 0) {
return 0;
} else {
return 1;
}
}

extern宣言された変数hogeは、最初に値が設定されたきり、誰も修正しない。従って、このコードの実行を通して値は変化せず、定数とみなすことができる。しかし、g++はこれを見抜くことができない。

LTOなし

_main:

100000fb0: 48 8d 05 49 00 00 00 leaq 73(%rip), %rax
100000fb7: 8b 00 movl (%rax), %eax
100000fb9: 85 c0 testl %eax, %eax
100000fbb: 0f 9e c0 setle %al
100000fbe: 0f b6 c0 movzbl %al, %eax
100000fc1: c3 retq

LTOあり

_main:

100000fb0: 8b 15 4a 00 00 00 movl 74(%rip), %edx
100000fb6: 31 c0 xorl %eax, %eax
100000fb8: 85 d2 testl %edx, %edx
100000fba: 0f 9e c0 setle %al
100000fbd: c3 retq

どちらもグローバル変数の内容をチェックして分岐している。

しかし、clang++はこの変数が「定数」であることを見抜くことができる。

LTOなし

_main:

100000fa0: 55 pushq %rbp
100000fa1: 48 89 e5 movq %rsp, %rbp
100000fa4: 48 8d 0d 55 00 00 00 leaq 85(%rip), %rcx
100000fab: 31 c0 xorl %eax, %eax
100000fad: 83 39 00 cmpl $0, (%rcx)
100000fb0: 0f 9e c0 setle %al
100000fb3: 5d popq %rbp
100000fb4: c3 retq

LTOあり

_main:

100000fb0: 55 pushq %rbp
100000fb1: 48 89 e5 movq %rsp, %rbp
100000fb4: 31 c0 xorl %eax, %eax
100000fb6: 5d popq %rbp
100000fb7: c3 retq

変数のチェックが消え、問答無用で0を返してしまうようになったのがわかると思う。

ちなみに、g++は単一ファイルであっても、グローバル変数がからむ最適化はできない。


test2.cpp

#include <cstdio>

int hoge = 1;
int main() {
if (hoge > 0) {
return 0;
} else {
return 1;
}
}

$ g++ -flto -O3 test2.cpp ;objdump -d a.out | c++filt

(snip)
_main:
100000fb0: 8b 15 4a 00 00 00 movl 74(%rip), %edx # hogeの読み込み
100000fb6: 31 c0 xorl %eax, %eax
100000fb8: 85 d2 testl %edx, %edx
100000fba: 0f 9e c0 setle %al
100000fbd: c3 retq

clang++はできる。

$ clang++ -flto -O3 test2.cpp;objdump -d a.out | c++filt 

(snip)
_main:
100000fb0: 55 pushq %rbp
100000fb1: 48 89 e5 movq %rsp, %rbp
100000fb4: 31 c0 xorl %eax, %eax
100000fb6: 5d popq %rbp
100000fb7: c3 retq


例4: ループ展開

こんなコードを考える。


test.cpp

int func(int i) {

return i * 2;
}


main.cpp

#include <cstdio>


int func(int);

int main() {
int sum = 0;
for (int i = 0; i < 100; i++) {
sum += func(i);
}
printf("%d\n", sum);
}


引数の二倍を返す関数funcについて、0から99まで数字を入れてその総和を返すコードである。g++、clang++ともに普通にコンパイルするとループをまわすのだが、LTOをかけるとどちらも即値を返せるようになる

LTOなし

$ g++ -O3 main.cpp test.cpp   

$ objdump -d a.out | c++filt
(snip)
_main:
100000f00: 55 pushq %rbp
100000f01: 31 ed xorl %ebp, %ebp
100000f03: 53 pushq %rbx
100000f04: 31 db xorl %ebx, %ebx
100000f06: 48 83 ec 08 subq $8, %rsp
100000f0a: 66 0f f 44 00 00 nopw (%rax,%rax)
100000f10: 89 df movl %ebx, %edi
100000f12: 83 c3 01 addl $1, %ebx
100000f15: e8 d6 ff ff ff callq -42 <func(int)>
100000f1a: 01 c5 addl %eax, %ebp
100000f1c: 83 fb 64 cmpl $100, %ebx
100000f1f: 75 ef jne -17 <_main+0x10>
100000f21: 48 8d 3d 32 00 00 00 leaq 50(%rip), %rdi
100000f28: 89 ee movl %ebp, %esi
100000f2a: 31 c0 xorl %eax, %eax
100000f2c: e8 09 00 00 00 callq 9
100000f31: 48 83 c4 08 addq $8, %rsp
100000f35: 31 c0 xorl %eax, %eax
100000f37: 5b popq %rbx
100000f38: 5d popq %rbp
100000f39: c3 retq

LTOあり

$ g++ -O3 -flto main.cpp test.cpp   

$ objdump -d a.out | c++filt
(snip)
_main:
100000f50: 48 83 ec 08 subq $8, %rsp
100000f54: be ac 26 00 00 movl $9900, %esi
100000f59: 31 c0 xorl %eax, %eax
100000f5b: 48 8d 3d 2c 00 00 00 leaq 44(%rip), %rdi
100000f62: e8 07 00 00 00 callq 7
100000f67: 31 c0 xorl %eax, %eax
100000f69: 48 83 c4 08 addq $8, %rsp
100000f6d: c3 retq

ループがごそっと消えて、最終結果「9900」を直接代入しているのがわかると思う。clang++も同様。


まとめ

リンク時最適化(Link Time Optimization, LTO)について、g++、clang++で何ができて、何ができないかをまとめてみた。LTOは、オブジェクトファイルに中間コードを吐いておき、最後にコンパイルしなおす、という方法で実装されているため、要するに単一ファイルでできる最適化はできるし、単一ファイルでできない最適化はできないと覚えておけば良いと思う。

余談だが、局所的な最適化についてはg++、clang++のほうがインテルコンパイラの方が優れている印象だったが、LTOを含むグローバルな最適化については、(少なくとも昔は)インテルコンパイラの方がかなり賢い印象だった。しかし、最近いろいろ調べてみると、g++/clang++のグローバル最適化もだいぶ賢くなってきている感じ。いずれにせよ、コンパイラの最適化技術の進展はすごいですね・・・。





  1. この方法だとコード全体が大きいときに時間がかかりすぎるため、Scalable Whole Program optimizer (WHOPR)という仕組みがあるらしいのだが、著者はよく知らない。