Go CompilerのFunction Inlining

golang

Go Compilerが行う、関数の処理をインラインに展開することで呼び出しコストを削減するFunction Inliningの話。 式の数が40未満でループやクロージャなどが含まれないシンプルな処理の関数が対象となる。

(追記: 2021-02-17) Go 1.16でラベルのないループがInliningされるようになった

まずは次の例で挙動を確認する。

package main

import "fmt"

func myfunc(a, b int) int {
        return a + b
}

func main() {
        fmt.Println(myfunc(1, 2))
}

-gcflags-m を渡してビルドすると最適化の内容が確認でき、2つ渡すとより詳細な出力が得られる。

$ go tool compile -help
usage: compile [options] file.go...
...
  -m    print optimization decisions

myfunc()fmt.Println()がInliningされたことや、myfunc(1, 2)がヒープに割り当てられたことなどが分かる。 ちなみにコストの低いスタックか、高いヒープのどちらに割り当てるかはEscape analysisによって決まる。

$ go build -gcflags '-m -m' main.go 
# command-line-arguments
./main.go:5:6: can inline myfunc with cost 4 as: func(int, int) int { return a + b }  <----
./main.go:9:6: cannot inline main: function too complex: cost 83 exceeds budget 80
./main.go:10:20: inlining call to myfunc func(int, int) int { return a + b }
./main.go:10:13: inlining call to fmt.Println func(...interface {}) (int, error) { var fmt..autotmp_3 int; fmt..autotmp_3 = <N>; var fmt..autotmp_4 error; fmt..autotmp_4 = <N>; fmt..autotmp_3, fmt..autotmp_4 = fmt.Fprintln(io.Writer(os.Stdout), fmt.a...); return fmt..autotmp_3, fmt..autotmp_4 }
./main.go:10:20: myfunc(1, 2) escapes to heap:
./main.go:10:20:   flow: ~arg0 = &{storage for myfunc(1, 2)}:
./main.go:10:20:     from myfunc(1, 2) (spill) at ./main.go:10:20
./main.go:10:20:     from ~arg0 = <N> (assign-pair) at ./main.go:10:13
./main.go:10:20:   flow: {storage for []interface {} literal} = ~arg0:
./main.go:10:20:     from []interface {} literal (slice-literal-element) at ./main.go:10:13
./main.go:10:20:   flow: fmt.a = &{storage for []interface {} literal}:
./main.go:10:20:     from []interface {} literal (spill) at ./main.go:10:13
./main.go:10:20:     from fmt.a = []interface {} literal (assign) at ./main.go:10:13
./main.go:10:20:   flow: {heap} = *fmt.a:
./main.go:10:20:     from fmt.Fprintln(io.Writer(os.Stdout), fmt.a...) (call parameter) at ./main.go:10:13
./main.go:10:20: myfunc(1, 2) escapes to heap
./main.go:10:13: []interface {} literal does not escape
<autogenerated>:1: .this does not escape

objdumpで逆アセンブルしたものを見ても関数が呼び出しされている形跡はない。 さらに1+2が既に評価されている。

$ go tool objdump main | less
...
TEXT main.main(SB) /Users/sambaiz/go/src/github.com/sambaiz/hoge/main.go
  main.go:9             0x10a6a40               65488b0c2530000000      MOVQ GS:0x30, CX                        
  main.go:9             0x10a6a49               483b6110                CMPQ 0x10(CX), SP                       
  main.go:9             0x10a6a4d               0f867c000000            JBE 0x10a6acf                           
  main.go:9             0x10a6a53               4883ec58                SUBQ $0x58, SP                          
  main.go:9             0x10a6a57               48896c2450              MOVQ BP, 0x50(SP)                       
  main.go:9             0x10a6a5c               488d6c2450              LEAQ 0x50(SP), BP                       
  main.go:10            0x10a6a61               48c7042403000000        MOVQ $0x3, 0(SP)  <---- 1 + 2                      
  main.go:10            0x10a6a69               e83233f6ff              CALL runtime.convT64(SB)                
  main.go:10            0x10a6a6e               488b442408              MOVQ 0x8(SP), AX                        
  main.go:10            0x10a6a73               0f57c0                  XORPS X0, X0                            
  main.go:10            0x10a6a76               0f11442440              MOVUPS X0, 0x40(SP)                     
  main.go:10            0x10a6a7b               488d0d7ea90000          LEAQ runtime.rodata+43296(SB), CX       
  main.go:10            0x10a6a82               48894c2440              MOVQ CX, 0x40(SP)                       
  main.go:10            0x10a6a87               4889442448              MOVQ AX, 0x48(SP) 

次にInliningされないパターンを見るためループを入れてみる。//go:noinline pragmaを付けてもInliningさせなくすることができる。

func myfunc() int {
	n := 0
	for i := 0; i < 10; i++ {
		n += i
	}
	return n
}

Inliningされていないことを確認。

$ go build -gcflags '-m -m' main.go 
# command-line-arguments
./main.go:7:6: cannot inline myfunc: unhandled op FOR  <----
./main.go:15:6: cannot inline main: function too complex: cost 134 exceeds budget 80
./main.go:16:13: inlining call to fmt.Println func(...interface {}) (int, error) { var fmt..autotmp_3 int; fmt..autotmp_3 = <N>; var fmt..autotmp_4 error; fmt..autotmp_4 = <N>; fmt..autotmp_3, fmt..autotmp_4 = fmt.Fprintln(io.Writer(os.Stdout), fmt.a...); return fmt..autotmp_3, fmt..autotmp_4 }
./main.go:16:20: myfunc() escapes to heap:
./main.go:16:20:   flow: ~arg0 = &{storage for myfunc()}:
./main.go:16:20:     from myfunc() (spill) at ./main.go:16:20
./main.go:16:20:     from ~arg0 = <N> (assign-pair) at ./main.go:16:13
./main.go:16:20:   flow: {storage for []interface {} literal} = ~arg0:
./main.go:16:20:     from []interface {} literal (slice-literal-element) at ./main.go:16:13
./main.go:16:20:   flow: fmt.a = &{storage for []interface {} literal}:
./main.go:16:20:     from []interface {} literal (spill) at ./main.go:16:13
./main.go:16:20:     from fmt.a = []interface {} literal (assign) at ./main.go:16:13
./main.go:16:20:   flow: {heap} = *fmt.a:
./main.go:16:20:     from fmt.Fprintln(io.Writer(os.Stdout), fmt.a...) (call parameter) at ./main.go:16:13
./main.go:16:20: myfunc() escapes to heap
./main.go:16:13: []interface {} literal does not escape
<autogenerated>:1: .this does not escape

objdump からも myfunc() が呼び出されていることが確認できる。

$ go tool objdump main | less
...
TEXT main.main(SB) /Users/sambaiz/go/src/github.com/sambaiz/hoge/main.go
  main.go:15            0x10a6a60               65488b0c2530000000      MOVQ GS:0x30, CX                        
  main.go:15            0x10a6a69               483b6110                CMPQ 0x10(CX), SP                       
  main.go:15            0x10a6a6d               0f867c000000            JBE 0x10a6aef                           
  main.go:15            0x10a6a73               4883ec58                SUBQ $0x58, SP                          
  main.go:15            0x10a6a77               48896c2450              MOVQ BP, 0x50(SP)                       
  main.go:15            0x10a6a7c               488d6c2450              LEAQ 0x50(SP), BP                       
  main.go:16            0x10a6a81               e8baffffff              CALL main.myfunc(SB)  <----
  main.go:16            0x10a6a86               e81533f6ff              CALL runtime.convT64(SB)                
  main.go:16            0x10a6a8b               488b442408              MOVQ 0x8(SP), AX                        
  main.go:16            0x10a6a90               0f57c0                  XORPS X0, X0                            
  main.go:16            0x10a6a93               0f11442440              MOVUPS X0, 0x40(SP)                     
  main.go:16            0x10a6a98               488d0d81a90000          LEAQ runtime.types+43296(SB), CX        
  main.go:16            0x10a6a9f               48894c2440              MOVQ CX, 0x40(SP)                       
  main.go:16            0x10a6aa4               4889442448              MOVQ AX, 0x48(SP)                       

無名関数も同様にInliningできる場合はされ、できない場合はされない。

func main() {
	var myfunc = func() int {
		n := 0
		for i := 0; i < 10; i++ {
			n += i
		}
		return n
	}
	fmt.Println(myfunc())
}
main.go:23            0x10a6a61               488b0570c30200          MOVQ go.func.*+125(SB), AX              
main.go:23            0x10a6a68               488d1569c30200          LEAQ go.func.*+125(SB), DX              
main.go:23            0x10a6a6f               ffd0                    CALL AX

参考

Go Compilerのインライン展開についてまとめた - Qiita