Go to Qiita Advent Calendar Top
LoginSignup
70
29

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@kaityo256(ロボ太)

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

Posted at

はじめに

一般に、コンパイラによる最適化は局所的であればあるほど効きやすい。例えば同じ関数内ならできる最適化が、グローバル変数がからむとできなくなったり、ファイルをまたぐとできなくなったりする。しかし、最近はリンク時最適化(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を返す関数funcをmain関数から呼び出してその内容を表示するコードである。このコードは、関数をインライン展開し、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)という仕組みがあるらしいのだが、著者はよく知らない。 ↩

70
29
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
70
29

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?