Help us understand the problem. What is going on with this article?

コンパイラは関数のインライン展開を☓☓段で力尽きる

More than 3 years have passed since last update.

はじめに

「コンパイラって、関数のインライン展開を何段までやってくれるんでしょうか?これってトリビアになりませんか?」

このトリビアの種、つまりこういうことになります。

「コンパイラに多段呼び出しの関数を食わせてインライン展開させた時、☓☓段で力尽きる」

実際に調べてみた。

ソース

関数の多段呼び出しをするコードを吐くRubyコードを書いた。

test.rb
num = ARGV[0].to_i

puts <<EOS
#include <stdio.h>
int
func0(int a){
  return a + 1;
}
EOS

num.times do |i|
  puts "int func#{i+1}(int a){return func#{i}(a);}"
end

puts <<EOS
int
main(void){
  int a = 0;
  printf("%d\\n",func#{num}(a));
}
EOS

例えば10段ならこんなの。

$ ruby test.rb 10 > test10.cpp
test10.cpp
#include <stdio.h>
int
func0(int a){
  return a + 1;
}
int func1(int a){return func0(a);}
int func2(int a){return func1(a);}
int func3(int a){return func2(a);}
int func4(int a){return func3(a);}
int func5(int a){return func4(a);}
int func6(int a){return func5(a);}
int func7(int a){return func6(a);}
int func8(int a){return func7(a);}
int func9(int a){return func8(a);}
int func10(int a){return func9(a);}
int
main(void){
  int a = 0;
  printf("%d\n",func10(a));
}

コンパイラのバージョンとオプション

  • g++ 6.3.0 (-O2)
  • clang++ Apple LLVM version 8.0.0 (-O2)
  • icpc 16.0.4 (-O2)

検証

アセンブリを見て、printfの直前でfuncをcallするかどうかで判定。とりあえず100段くらいまで。

  • g++ (Linux)
test100.s
main:
        subq    $8, %rsp
        movl    $1, %esi
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
  • clang++ (MacOS)
test100.s
_main:
  pushq %rbp
  movq  %rsp, %rbp
  leaq  L_.str(%rip), %rdi
  movl  $1, %esi
  xorl  %eax, %eax
  callq _printf
  • icpc
test100.s
main:
        movl      $.L_2__STRING.0, %edi
        movl      $1, %esi
        orl       $32832, (%rsp) 
        xorl      %eax, %eax
        ldmxcsr   (%rsp)
        call      printf

うん、全部即値で返せてる。

次、1000段。

  • g++(Linux)
test1000.s
main:
        subq    $8, %rsp
        movl    $1, %esi
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
  • clang++ (MacOS)
test1000.s
_main:
  pushq %rbp
  movq  %rsp, %rbp
  leaq  L_.str(%rip), %rdi
  movl  $1, %esi
  xorl  %eax, %eax
  callq _printf
  • icpc
test1000.s
        stmxcsr   (%rsp)
        xorl      %edi, %edi
        orl       $32832, (%rsp)
        ldmxcsr   (%rsp)
#       func3(int)
        call      _Z5func3i
        movl      $.L_2__STRING.0, %edi
        movl      %eax, %esi
        xorl      %eax, %eax
#       printf(const char *, ...)
        call      printf

あ、関数呼び出しになっている。しかもfunc3を呼んでいる。それぞれの関数の中身はこうなっている。

test1000.s
func4(int):
        incl      %edi
        movl      %edi, %eax
        ret


func5(int):
#       func3(int)
        jmp       func3(int)

うん、func4まではincl呼んでるけど、func5からなぜかfunc3を呼んでる。

ちなみに、997段の展開では最後まで行く。

$ ruby test.rb 997 > test997.cpp
$ icpc -O2 -S test997.cpp
test997.s
main:
(snip)
        stmxcsr   (%rsp)
        movl      $.L_2__STRING.0, %edi
        movl      $1, %esi 
        orl       $32832, (%rsp)
        xorl      %eax, %eax
        ldmxcsr   (%rsp)
#       printf(const char *, ...)
        call      printf 
(snip)
func997(int):
        incl      %edi 
        movl      %edi, %eax
        ret

998段では途中でインライン展開をやめ、なぜか奇数番の関数だけjmp命令を出す。

test998.s
main:
(snip)
        stmxcsr   (%rsp)
        xorl      %edi, %edi  
        orl       $32832, (%rsp)
        ldmxcsr   (%rsp)  
        call      func3(int)      
        movl      $.L_2__STRING.0, %edi 
        movl      %eax, %esi 
        xorl      %eax, %eax 
#       printf(const char *, ...)
        call      printf

func5(int):
#       func3(int)
        jmp       func3(int)  

func6(int):
        incl      %edi 
        movl      %edi, %eax 
        ret 

具体的には、func5,7,9,...,func249だけjmp命令となり、それ以外はincになっている。

ちなみにg++やclang++は5000段でも最後までインライン展開して即値にした。

まとめ

こうしてこの世界にまた一つ
新たなトリビアが生まれた。

インテルコンパイラは、関数のインライン展開を998段で力尽きる。

おまけ:関数ポインタの場合

関数ポインタを関数の引数に渡した場合を考える。こんなの。

test.cpp
#include <stdio.h>

int
func(int a){
  return a+1;
}

int
test(int (*p)(int),int a){
  return p(a);
}

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

g++やclang++では、これを即値にもっていける。

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

icpcは、testはインライン展開するが、funcの展開はできない。

..B1.6:
        stmxcsr   (%rsp)
        xorl      %edi, %edi
        orl       $32832, (%rsp)
        ldmxcsr   (%rsp)
        call      func(int)
        movl      $.L_2__STRING.0, %edi
        movl      %eax, %esi
        xorl      %eax, %eax
        call      printf
kaityo256
ロボ太 記事中に明示されていない場合、私の記事はCC-BY 4.0で、記事に含まれるソースコードはMITライセンスで公開します。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした