2023.02.03

エフェクト解析による動的言語最適化 Part.2

門脇宗平

こんにちは。リクルートAdvanced Technology Lab客員研究員の門脇です。
普段はJulia Computingという、プログラミング言語Juliaの開発やJuliaを使ったビジネスを行っている会社のソフトウェアエンジニアとして、特にJuliaのコンパイラの開発に携わっています。

今回のブログ記事では、前回の記事に引き続き、現在のJuliaの最新版であるv1.8から追加された新しいコンパイラ機能エフェクト解析についてご紹介します。

エフェクト解析を用いたJulia言語コンパイラの最適化について、以下のアウトラインで紹介しています:

Part.1 (前回の記事)
- Part.1ではPart.2の前提となる知識の導入をしました。
- まずJuliaの基本的な設計思想とコンパイラのデザインを理解し、Juliaコンパイラが直面しているトレードオフについて解説し、
- エフェクト解析を利用してそのトレードオフを改善するアイディアConcrete Evaluationを簡単に導入しました。
Part.2 (今回の記事)
- Part.2ではそのアイディアConcrete Evaluationをより詳細に掘り下げていきます。
- まず、Juliaコンパイラが直面するトレードオフを解決するアイディアConcrete Evaluationをより具体的に理解し、
- 実際にConcrete Evaluationを行うために必要な条件(エフェクト)を確認します。
- そして今回我々が実装したエフェクト解析のデザインを説明します。
- 最後にエフェクト解析に関してJuliaプログラマが利用可能なアノテーションやエフェクトフレンドリーなJuliaコードを書くためのtipsを紹介していきます。

まだPart.1を読まれていない方はぜひそちらの方から読んでみてください。 Part.2ではPart.1で紹介・議論された内容、その中でも特にJuliaコンパイラの基本的な設計思想については既知のものとして進めますが、 Juliaコンパイラの定数伝播の仕組みやConcrete Evaluationのアイディアについてはこの記事でまた改めて詳細に説明していきます。

!!! warning !!! 以下のご紹介するコードは、2023年02月03日時点でのnightlyバージョン1.10.0-DEV.482 (2023-02-03)で実行しています。今回取り上げているエフェクト解析およびコンパイラ最適化は現在も細かな修正が加えられており、他のバージョンでは同様の実験結果が得られない場合があります。

おさらい: Juliaプログラムのコンパイルを最適化するアイディア Concrete Evaluation

前回のブログでは、以下の事柄を確認しました:

Juliaの言語設計においては、抽象解釈ベースのプログラム解析に基づく最適化が非常に重要であり、抽象解釈の精度とレイテンシのトレードオフが問題となる
定数情報を用いた抽象解釈(定数伝播)はより精度の高い解析と強力な最適化を可能にする一方で、過度な定数伝播が生じた場合に深刻なレイテンシ上の問題を引き起こしてしまう

そして、今回Juliaコンパイラに追加されたエフェクトシステムは、この抽象解釈における精度とレイテンシのトレードオフを一気に改善するための秘策であることを説明しました。

つまり、抽象解釈中に解析されている関数呼び出しについて、特定の条件が満たされると証明できる場合に、その関数呼び出しへの定数伝播のプロセスをまるっと実際のプログラム実行で置き換えてしまうことで、定数伝播にかかるコンパイルタイムコストを削減することができるのです。

そのようにして、静的な抽象解釈のプロセスに動的で具体的なプログラム実行を部分的に入れ込むことを、我々は"Abstract Interpretation"(抽象解釈)と対比させ、 (Partial) Concrete Evaluation(抽象解釈の部分的な具体化)と呼んでいます。

定数伝播と Concrete Evaluation

では、実際今回考えるConcrete Evaluationとは具体的にどういったものなのでしょうか。 Concrete Evaluationを理解するためには、まずはJuliaコンパイラにおける定数伝播の仕組みをしっかりと理解することが必要です。ここでは説明のため、次のような関数fをコンパイルする場合を考えてみます:

julia> function f()
           a = 1.0
           b = sin(a)
           c = sin(b)
           return c
       end;

julia> function f()

a = 1.0

b = sin(a)

c = sin(b)

return c

end;

f()という関数呼び出しをコンパイルする時、Julia処理系は抽象解釈技術を用いてf内の変数や関数の返り値の型を推論し、インライン展開などの様々な最適化を施します。抽象解釈による型推論の結果を@code_typedマクロを使って確認してみると以下のようになっています。

julia> @code_typed optimize=false f()
CodeInfo(
1 ─     (a = 1.0)::Core.Const(1.0)
│       (b = Main.sin(a::Core.Const(1.0)))::Core.Const(0.8414709848078965)
│       (c = Main.sin(b::Core.Const(0.8414709848078965)))::Core.Const(0.7456241416655579)
└──     return c::Core.Const(0.7456241416655579)
) => Float64

julia> @code_typed optimize=false f()

CodeInfo(

1 ─ (a = 1.0)::Core.Const(1.0)

│ (b = Main.sin(a::Core.Const(1.0)))::Core.Const(0.8414709848078965)

│ (c = Main.sin(b::Core.Const(0.8414709848078965)))::Core.Const(0.7456241416655579)

└── return c::Core.Const(0.7456241416655579)

) => Float64

ここで注目したいのは、Julia処理系の抽象解釈ルーチンが(a = 1.0)::Core.Const(1.0)という定数情報を利用して、その後のMain.sin(a::Core.Const(1.0))の返り値を定数値Core.Const(0.8414709848078965)として解析していることです¹。

今回考えるConcrete Evaluationが実装されるまでは、Juliaコンパイラは定数伝播(constant-propagation)と呼ばれる技術を用いてこうした定数情報の解析を行ってきました。つまり、抽象解釈の解析の精度を高めるために、型レベルの抽象解釈に付随して、定数レベルの情報を用いた抽象解釈を行っているのです。では具体的にMain.sin(a)という関数呼び出しに対して、定数伝播を行うとはどういうことなのでしょうか。 Juliaではsinなどの基本的な算術関数もJulia自身で実装されているおり、Juliaプログラムとしては以下のように実装されています²:

function sin(x::T) where T<:Union{Float32, Float64}
    absx = abs(x)
    if absx < T(pi)/4 #|x| ~<= pi/4, no need for reduction
        if absx < sqrt(eps(T))
            return x
        end
        return sin_kernel(x)
    elseif isnan(x)
        return T(NaN)
    elseif isinf(x)
        sin_domain_error(x)
    end
    n, y = rem_pio2_kernel(x)
    n = n&3
    if n == 0
        return sin_kernel(y)
    elseif n == 1
        return cos_kernel(y)
    elseif n == 2
        return -sin_kernel(y)
    else
        return -cos_kernel(y)
    end
end

function sin(x::T) where T<:Union{Float32, Float64}

absx = abs(x)

if absx < T(pi)/4 #|x| ~<= pi/4, no need for reduction

if absx < sqrt(eps(T))

return x

end

return sin_kernel(x)

elseif isnan(x)

return T(NaN)

elseif isinf(x)

sin_domain_error(x)

end

n, y = rem_pio2_kernel(x)

n = n&3

if n == 0

return sin_kernel(y)

elseif n == 1

return cos_kernel(y)

elseif n == 2

return -sin_kernel(y)

else

return -cos_kernel(y)

end

Juliaコンパイラにおいて、「f()中のMain.sin(a::Core.Const(1.0))呼び出しに対して定数伝播を行う」とはつまり、「sin(x::T) where T<:Union{Float32, Flaot64}に対してx::Core.Const(1.0)という情報を用いて抽象解釈を行う」ということです。 Cthulhu.jlというサードパーティパッケージを利用してその様子を確認することができます:

julia> using Cthulhu
julia> # おまじない： 説明のため、今回紹介する "Concrete-Evaluation" を一時無効化する
       function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,
           @nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)
           return nothing # disable both [semi-]concrete evaluation for now
       end
julia> @descend optimize=false debuginfo=:none f()
f() @ Main none:1
Variables
  #self#::Core.Const(f)
  c::Float64
  b::Float64
  a::Float64
∘ ─ %0 = invoke f()::Core.Const(0.7456241416655579)
1 ─     (a = 1.0)::Core.Const(1.0)
│       (b = Main.sin(a::Core.Const(1.0)))::Core.Const(0.8414709848078965)
│       (c = Main.sin(b::Core.Const(0.8414709848078965)))::Core.Const(0.7456241416655579)
└──     return c::Core.Const(0.7456241416655579)
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
• %2 = < constprop > sin(::Core.Const(1.0))::Core.Const(0.8414709848078965)
  %3 = < constprop > sin(::Core.Const(0.8414709848078965))::Core.Const(0.7456241416655579)
  ↩
sin(x::T) where T<:Union{Float32, Float64} @ Base.Math special/trig.jl:29
Variables
  #self#::Core.Const(sin)
  x::Core.Const(1.0)
  @_3::Int64
  y::Base.Math.DoubleFloat64
  n::Int64
  absx::Float64
∘ ─ %0 = invoke sin(::Float64)::Core.Const(0.8414709848078965)
1 ─       Core.NewvarNode(:(@_3))::Any
│         Core.NewvarNode(:(y))::Any
│         Core.NewvarNode(:(n))::Any
│         (absx = Base.Math.abs(x))::Core.Const(1.0)
│   %5  = absx::Core.Const(1.0)
│   %6  = ($(Expr(:static_parameter, 1)))(Base.Math.pi)::Core.Const(3.141592653589793)
│   %7  = (%6 / 4)::Core.Const(0.7853981633974483)
│         (%5 < %7)::Core.Const(false)
└──       goto #2
2 ─       Base.Math.isnan(x)::Core.Const(false)
└──       goto #3
3 ─       Base.Math.isinf(x)::Core.Const(false)
└──       goto #4
4 ─ %14 = Base.Math.rem_pio2_kernel(x)::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))
│   %15 = Base.indexed_iterate(%14, 1)::Core.Const((1, 2))
│         (n = Core.getfield(%15, 1))::Core.Const(1)
│         (@_3 = Core.getfield(%15, 2))::Core.Const(2)
│   %18 = Base.indexed_iterate(%14, 2, @_3::Core.Const(2))::Core.Const((Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17), 3))
│         (y = Core.getfield(%18, 1))::Core.Const(Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))
│         (n = n::Core.Const(1) & 3)::Core.Const(1)
│         (n::Core.Const(1) == 0)::Core.Const(false)
└──       goto #5
5 ─       (n::Core.Const(1) == 1)::Core.Const(true)
│         nothing::Any
│   %25 = Base.Math.cos_kernel(y::Core.Const(Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))::Core.Const(0.8414709848078965)
└──       return %25
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
• %4 = < constprop > abs(::Core.Const(1.0))::Core.Const(1.0)
  %6 = Float64(::Irrational{:π})::Core.Const(3.141592653589793)
  %7 = < constprop > /(::Core.Const(3.141592653589793),::Core.Const(4))::Core.Const(0.7853981633974483)
  %8 = < constprop > <(::Core.Const(1.0),::Core.Const(0.7853981633974483))::Core.Const(false)
  %10 = < constprop > isnan(::Core.Const(1.0))::Core.Const(false)
  %12 = < constprop > isinf(::Core.Const(1.0))::Core.Const(false)
  %14 = < constprop > rem_pio2_kernel(::Core.Const(1.0))::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))
  %15 = < constprop > indexed_iterate(::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))),::Core.Const(1))::Core.Const((1, 2))
  %18 = < constprop > indexed_iterate(::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))),::Core.Const(2),::Core.Const(2))::…
v  %20 = < constprop > &(::Core.Const(1),::Core.Const(3))::Core.Const(1)

julia> using Cthulhu

julia> # おまじない：説明のため、今回紹介する "Concrete-Evaluation" を一時無効化する

function Core.Compiler.concrete_eval_eligible(interp::Cthulhu.CthulhuInterpreter,

@nospecialize(f), result::Core.Compiler.MethodCallResult, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)

return nothing # disable both [semi-]concrete evaluation for now

end

julia> @descend optimize=false debuginfo=:none f()

f() @ Main none:1

Variables

#self#::Core.Const(f)

c::Float64

b::Float64

a::Float64

∘ ─ %0 = invoke f()::Core.Const(0.7456241416655579)

1 ─ (a = 1.0)::Core.Const(1.0)

│ (b = Main.sin(a::Core.Const(1.0)))::Core.Const(0.8414709848078965)

│ (c = Main.sin(b::Core.Const(0.8414709848078965)))::Core.Const(0.7456241416655579)

└── return c::Core.Const(0.7456241416655579)

Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.

Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.

Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code

Actions: [E]dit source code, [R]evise and redisplay

Advanced: dump [P]arams cache.

• %2 = < constprop > sin(::Core.Const(1.0))::Core.Const(0.8414709848078965)

%3 = < constprop > sin(::Core.Const(0.8414709848078965))::Core.Const(0.7456241416655579)

↩

sin(x::T) where T<:Union{Float32, Float64} @ Base.Math special/trig.jl:29

Variables

#self#::Core.Const(sin)

x::Core.Const(1.0)

@_3::Int64

y::Base.Math.DoubleFloat64

n::Int64

absx::Float64

∘ ─ %0 = invoke sin(::Float64)::Core.Const(0.8414709848078965)

1 ─ Core.NewvarNode(:(@_3))::Any

│ Core.NewvarNode(:(y))::Any

│ Core.NewvarNode(:(n))::Any

│ (absx = Base.Math.abs(x))::Core.Const(1.0)

│ %5 = absx::Core.Const(1.0)

│ %6 = ($(Expr(:static_parameter, 1)))(Base.Math.pi)::Core.Const(3.141592653589793)

│ %7 = (%6 / 4)::Core.Const(0.7853981633974483)

│ (%5 < %7)::Core.Const(false)

└── goto #2

2 ─ Base.Math.isnan(x)::Core.Const(false)

└── goto #3

3 ─ Base.Math.isinf(x)::Core.Const(false)

└── goto #4

4 ─ %14 = Base.Math.rem_pio2_kernel(x)::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))

│ %15 = Base.indexed_iterate(%14, 1)::Core.Const((1, 2))

│ (n = Core.getfield(%15, 1))::Core.Const(1)

│ (@_3 = Core.getfield(%15, 2))::Core.Const(2)

│ %18 = Base.indexed_iterate(%14, 2, @_3::Core.Const(2))::Core.Const((Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17), 3))

│ (y = Core.getfield(%18, 1))::Core.Const(Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))

│ (n = n::Core.Const(1) & 3)::Core.Const(1)

│ (n::Core.Const(1) == 0)::Core.Const(false)

└── goto #5

5 ─ (n::Core.Const(1) == 1)::Core.Const(true)

│ nothing::Any

│ %25 = Base.Math.cos_kernel(y::Core.Const(Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))::Core.Const(0.8414709848078965)

└── return %25

Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.

Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.

Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code

Actions: [E]dit source code, [R]evise and redisplay

Advanced: dump [P]arams cache.

• %4 = < constprop > abs(::Core.Const(1.0))::Core.Const(1.0)

%6 = Float64(::Irrational{:π})::Core.Const(3.141592653589793)

%7 = < constprop > /(::Core.Const(3.141592653589793),::Core.Const(4))::Core.Const(0.7853981633974483)

%8 = < constprop > <(::Core.Const(1.0),::Core.Const(0.7853981633974483))::Core.Const(false)

%10 = < constprop > isnan(::Core.Const(1.0))::Core.Const(false)

%12 = < constprop > isinf(::Core.Const(1.0))::Core.Const(false)

%14 = < constprop > rem_pio2_kernel(::Core.Const(1.0))::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17)))

%15 = < constprop > indexed_iterate(::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))),::Core.Const(1))::Core.Const((1, 2))

%18 = < constprop > indexed_iterate(::Core.Const((1, Base.Math.DoubleFloat64(-0.5707963267948967, 4.9789962508669555e-17))),::Core.Const(2),::Core.Const(2))::…

v %20 = < constprop > &(::Core.Const(1),::Core.Const(3))::Core.Const(1)

後半のsin(x::T) where T<:Union{Float32, Float64} @ Base.Math special/trig.jl:29以降を見ると、 x::Core.Const(1.0)という定数情報がsin(x)で使われているサブルーチンへと伝播している様子が確認できます。ここで注意したいのは、(absx = Base.Math.abs(x))::Core.Const(1.0)や(%5 < %7)::Core.Const(false)などにおける、 Base.Math.absや<といった演算もJuliaで実装されている関数であり、それらの実装に対しても定数伝播が起きているということです。そのように定数情報が次々と伝播していくことで、最終的にCore.Const(0.8414709848078965)という返り値の定数情報を獲得しています。そうして得られたMain.sin(a::Core.Const(1.0))::Core.Const(0.8414709848078965)という返り値の定数情報は、 f内のMain.sin(b::Core.Const(0.8414709848078965))という関数呼び出しに対してさらに定数伝播していきます。

具体的にどの程度の定数伝播が起きているのでしょうか。前回の記事で紹介したprofile_absintを使って確認してみます。

julia> function profile_absint((interp, mi))
           cnt, locs = 0, Set{Tuple{Symbol,Int32}}()
           cnt_with_const, locs_with_const = 0, Set{Tuple{Symbol,Int32}}()
           for (mi, inferred) in interp.unopt
               if isa(mi, Core.MethodInstance)
                   # non constant inference
                   cnt += 1
                   foreach(lin->push!(locs, (lin.file, lin.line)), inferred.src.linetable)
               else
                   # constant inference
                   cnt_with_const += 1
                   foreach(lin->push!(locs_with_const, (lin.file, lin.line)), inferred.src.linetable)
               end
           end
           function print_profile_info((cnt, locs))
               linecnt = length(locs)
               filecnt = length(unique(first.(locs)))
               println("    analyzed $cnt calls / $linecnt lines (in $filecnt files)")
           end
           println("Profiling results on: ", mi)
           println("  [non-constant absint]")
           print_profile_info((cnt, locs))
           println("  [constant absint]")
           print_profile_info((cnt_with_const, locs_with_const))
       end;
julia> profile_absint(Cthulhu.@interp f())
Profiling results on: MethodInstance for f()
  [non-constant absint]
    analyzed 239 calls / 284 lines (in 18 files)
  [constant absint]
    analyzed 388 calls / 138 lines (in 13 files)

julia> function profile_absint((interp, mi))

cnt, locs = 0, Set{Tuple{Symbol,Int32}}()

cnt_with_const, locs_with_const = 0, Set{Tuple{Symbol,Int32}}()

for (mi, inferred) in interp.unopt

if isa(mi, Core.MethodInstance)

# non constant inference

cnt += 1

foreach(lin->push!(locs, (lin.file, lin.line)), inferred.src.linetable)

else

# constant inference

cnt_with_const += 1

foreach(lin->push!(locs_with_const, (lin.file, lin.line)), inferred.src.linetable)

end

function print_profile_info((cnt, locs))

linecnt = length(locs)

filecnt = length(unique(first.(locs)))

println(" analyzed $cnt calls / $linecnt lines (in $filecnt files)")

end

println("Profiling results on: ", mi)

println(" [non-constant absint]")

print_profile_info((cnt, locs))

println(" [constant absint]")

print_profile_info((cnt_with_const, locs_with_const))

end;

julia> profile_absint(Cthulhu.@interp f())

Profiling results on: MethodInstance for f()

[non-constant absint]

analyzed 239 calls / 284 lines (in 18 files)

[constant absint]

analyzed 388 calls / 138 lines (in 13 files)

Juliaコンパイラにおいては、型レベルでの解析が済んだ関数呼び出しに対して、定数情報が得られる場合に限って定数伝播が行われるため、ナイーブに考えると定数伝播される関数呼び出しの方が少なくなるはずですが、実際には239個の関数呼び出しが型レベルで解析されているのに対し、それよりも多い388個の関数呼び出しが定数情報を用いて再解析されているのがわかります。このことはつまり、定数伝播においては 解析のキャッシュの利用がしにくい ということを意味しています。 f()の例で言うと、sin(a::Core.Const(1.0))とsin(b::Core.Const(0.8414709848078965))という関数呼び出しにおいて、 a::Core.Const(1.0)とb::Core.Const(0.8414709848078965)という2つの異なる定数情報を伝播させると、解析対象となるコールグラフ(sin)が同一であったとしても、全く異なる2つの抽象解釈が必要となるのです。

逆に型レベルの情報だけを用いて抽象解釈を行った場合は、キャッシュの利用が可能です。 Main.sin(a::Float64)という解析は、Main.sin(b::Float64)という解析と 型レベルのドメインにおいては 全く同一の解析とみなすことができるからです。

このことはf()に少し手を加えたg()に対するプロファイリング結果と見比べるとよくわかります。型レベルで解析された関数呼び出しの個数は239個から変わってないのに対して、定数伝播された関数呼び出しの数は388個から410個に増えています。

julia> function g()
           a = 1.0
           b = sin(a)
           c = sin(b)
           d = sin(c) # <= もう1つ`sin`呼び出しを追加
           return d
       end;
julia> profile_absint(Cthulhu.@interp g())
Profiling results on: MethodInstance for g()
  [non-constant absint]
    analyzed 239 calls / 285 lines (in 18 files)
  [constant absint]
    analyzed 410 calls / 143 lines (in 13 files)

julia> function g()

a = 1.0

b = sin(a)

c = sin(b)

d = sin(c) # <= もう1つ`sin`呼び出しを追加

return d

end;

julia> profile_absint(Cthulhu.@interp g())

Profiling results on: MethodInstance for g()

[non-constant absint]

analyzed 239 calls / 285 lines (in 18 files)

[constant absint]

analyzed 410 calls / 143 lines (in 13 files)

この定数伝播における解析情報のキャッシュの利用の難しさにより、以下のような極端なケースで過剰な定数伝播が発生してしまいます。

function heavy_constprop()
    v0 = 1.0
    v1 = sin(v0)
    v2 = sin(v1)
    v3 = sin(v2)
    ...
    v1000 = sin(v999)
    return v1000
end

function heavy_constprop()

v0 = 1.0

v1 = sin(v0)

v2 = sin(v1)

v3 = sin(v2)

...

v1000 = sin(v999)

return v1000

end

こういった巨大な関数は通常のプログラミングではあまり目にかかりませんが、コードの自動生成を利用するシュミレーションなどの場面では自動生成された巨大な関数をコンパイルしなくてはならないこともあります。実際に、上のheavy_constprop関数は、Juliaの強力なメタプログラミング機能を利用して以下のように簡単に定義できます。

julia> let param = 1000
           ex = Expr(:block)
           var = gensym()
           push!(ex.args, :($var = 1.0))
           for i = 1:param
               newvar = Symbol("v", i)
               push!(ex.args, :($newvar = sin($var)))
               var = newvar
           end
           @eval global function heavy_constprop()
               $ex
           end
       end;
julia> profile_absint(@time Cthulhu.@interp heavy_constprop())
 16.537585 seconds (11.86 M allocations: 813.889 MiB, 11.47% gc time)
Profiling results on: MethodInstance for heavy_constprop()
  [non-constant absint]
    analyzed 239 calls / 281 lines (in 18 files)
  [constant absint]
    analyzed 22344 calls / 143 lines (in 13 files)

julia> let param = 1000

ex = Expr(:block)

var = gensym()

push!(ex.args, :($var = 1.0))

for i = 1:param

newvar = Symbol("v", i)

push!(ex.args, :($newvar = sin($var)))

var = newvar

end

@eval global function heavy_constprop()

$ex

end

end;

julia> profile_absint(@time Cthulhu.@interp heavy_constprop())

16.537585 seconds (11.86 M allocations: 813.889 MiB, 11.47% gc time)

Profiling results on: MethodInstance for heavy_constprop()

[non-constant absint]

analyzed 239 calls / 281 lines (in 18 files)

[constant absint]

analyzed 22344 calls / 143 lines (in 13 files)

22344個もの関数呼び出しを解析をするために、16.53秒も時間がかかっていることが確認できます。

今回紹介するConcrete Evaluationのアイディアは、こうした定数情報を用いた抽象解釈(定数伝播)の問題点を解決するため、関数呼び出しが特定の条件を満たすと証明できた場合に、その関数呼び出しをコンパイル時に実際に行ってしまって、定数情報を用いた抽象解釈のプロセスをまるっと実際の実行結果で置き換えてしまおう、というものです。つまり、具体的には上記heavy_constprop()のコンパイル時にそれぞれのsin(v)呼び出しを実際に評価し、

function f()
    v0 = 1.0
    v1 = 0.8414709848078965
    v2 = 0.7456241416655579
    v3 = 0.6784304773607402
    ...
    v1000 = 0.05459297151018517
    return v1000
end

function f()

v0 = 1.0

v1 = 0.8414709848078965

v2 = 0.7456241416655579

v3 = 0.6784304773607402

...

v1000 = 0.05459297151018517

return v1000

end

というイメージで解析を行うことで、先ほどCthulhuを用いて確認したような定数伝播を行わずとも、強力な最適化を行ってしまおうということです。

特にsinのような比較的シンプルで小さな関数に関しては、実際に実行してしまう方が、定数ドメインでの抽象解釈による解析を行うよりも簡単であることが多く、大幅にレイテンシを改善することができます。

Part 1.で説明したように、Juliaにおけるコンパイルの方式は基本的にはAoTコンパイルに近いものですが、 Julia処理系がコンパイルを行うタイミングは「コンパイル対象の関数の呼び出しの実行直前」であり、依存関係などの解決は既に行われており、サブルーチンの関数に対してはコンパイル時に実際に実行することが可能です。このJIT処理系としてのJuliaコンパイラの特性を活かし、抽象解釈によるプログラム解析に実際の(具体的な)プログラム実行を入れ込む、というのが今回紹介するConcrete Evaluationのアイディアなのです。

Concrete Evaluationに必要なエフェクトシステム

それでは、実際どのような関数呼び出しについてConcrete Evaluationを行うことができるかを考えてみましょう。

まず、大前提として、対象の関数呼び出しの全ての引数がコンパイル時に定数値として解析されていることが必要です。ただ、全ての引数が定数であるからといって、Concrete Evaluationを行える訳ではありません。 Concrete Evaluationとはつまるところ、「ある関数呼び出しの抽象解釈をスキップし、代わりにその呼び出しの実際に行い、その実行結果を呼び出し元における抽象解釈プロセスに埋め込む」ということです。 Juliaコンパイラにおいてはコンパイル対象のプログラムの中間表現に対してまず抽象解釈を行った後、抽象解釈により型付けされた中間表現に対して様々な最適化を加えていくので、その抽象解釈中に行われるConcrete Evaluationによって元のプログラムのセマンティクスが変わってしまうことがないようにしなければなりません。

結論から先に言うと、Concrete Evaluationを行うためにはConcrete Evaluationの対象の関数fが次の3つの性質を満たすことが求められます:

effect_free: fの実行がfに閉じない副作用を持たない
consistent: 同一³な入力に対してfの終了(リターンをするor例外を投げる)の仕方が同じであり、かつリターンをする場合は返り値が同一になる
terminate: fの実行が「リーズナブル」な時間内で終了する ⁴

以下では上記の3つがなぜ必要なのかをより具体的に説明していきます。

まず、 effect_freeから考えてみましょう。次のようなコンスタントではないグローバルな変数vへの書き込みを行う関数effectful(a)をConcrete Evaluateすることはできません:

function effectful()
    global v = 42
    return v
end

function effectful()

global v = 42

return v

end

なぜならば、こうした対象の関数に閉じていない、外部から観測可能な状態(上の場合はグローバル変数vの値)に対する変更(副作用)は、対象の関数呼び出しの実行時に発生しなくてはならないからです。つまり、例えばもしeffectfulの呼び出しをConcrete Evaluateしコンパイル時に1度だけ評価したあと、実際のランタイムにおいては呼び出しを行わない場合、元プログラムのセマンティクスを変えてしまう危険性があるということです:

julia> effectful() # `effectful`がコンパイルされ、実行される
julia> v = 0        # グローバル変数`v`への変更はいつでも起きうる
julia> effectful() # この2度目の実行においても`global v = 42`という代入はもう一度発生する必要がある

julia> effectful() # `effectful`がコンパイルされ、実行される

julia> v = 0 # グローバル変数`v`への変更はいつでも起きうる

julia> effectful() # この2度目の実行においても`global v = 42`という代入はもう一度発生する必要がある

次に、対象の関数呼び出しに対する抽象解釈の結果を、Concrete Evaluationした結果を用いて健全に置き換えるためには、対象の関数呼び出しの返り値が同一の入力に対して常に同一である必要があります。この制約がconsistentです。これはどういうことかというと、次のようなシステム時間により返り値が変わるような関数inconsistent(a)は、実行時の外部環境により実行結果が変わってしまい、ある1つの実行結果を用いてその関数の全ての呼び出し結果を健全に抽象化することはできないため、 inconsistentの呼び出しをConcrete Evaluationした結果を抽象解釈に使うことはできないということです:

julia> inconsistent(a) = (isodd(Int(floor(time()))) ? sin : cos)(a);
# `inconsistent(42)`の結果は実行のタイミングで変化するためConcrete Evaluationすることはできない
julia> call_inconsistent() = inconsistent(42);
julia> call_inconsistent()
-0.9165215479156338
julia> call_inconsistent()
-0.39998531498835127

julia> inconsistent(a) = (isodd(Int(floor(time()))) ? sin : cos)(a);

# `inconsistent(42)`の結果は実行のタイミングで変化するためConcrete Evaluationすることはできない

julia> call_inconsistent() = inconsistent(42);

julia> call_inconsistent()

-0.9165215479156338

julia> call_inconsistent()

-0.39998531498835127

この制約は特にJuliaにおいては、Concrete Evaluation対象の関数呼び出しはミュータブルな構造体を新たにアロケートして返してはならない、ということも意味します。なぜなら、Juliaではミュータブルな構造体の同一性はオブジェクトのアドレスによって判断され、ミュータブルな構造体の異なるアロケーションは同一にはならないため、ミュータブルな構造体を返す関数の返り値を、１つの実行結果を用いて健全に抽象化することができないからです:

julia> inconsistent_alloc(a) = Any[a]; # allocate and return new vector containing the argument
julia> call_inconsistent() = inconsistent_alloc(42);
# `inconsistent_alloc`がアロケートする配列のアドレスはそれぞれ異なるため、
# 配列の要素が同一である場合でも、配列自体は同一にならない
julia> call_inconsistent() === call_inconsistent()
false

julia> inconsistent_alloc(a) = Any[a]; # allocate and return new vector containing the argument

julia> call_inconsistent() = inconsistent_alloc(42);

# `inconsistent_alloc`がアロケートする配列のアドレスはそれぞれ異なるため、

# 配列の要素が同一である場合でも、配列自体は同一にならない

julia> call_inconsistent() === call_inconsistent()

false

最後に、コンパイル時に安全にConcrete Evaluationを行うためには、対象の関数呼び出しがリーズナブルな時間で終了すること(terminate)が求められます。つまり、次のようなその終了性が担保されていない関数may_not_terminateをConcrete Evaluationすることは避けなくてはなりません:

function may_not_terminate(a)
    s = 0
    try
        while true
            s += sin(a)
        end
    catch
        return s # catch e.g. `InterruptException`
    end
end

function may_not_terminate(a)

s = 0

try

while true

s += sin(a)

end

catch

return s # catch e.g. `InterruptException`

end

このような関数を闇雲にコンパイルしようとしてしまうと、コンパイルが走ったまま処理系が終了しないといった事態が起こってしまいます。ユーザーコードが実行時に終了する必要はありませんが、そのユーザーコードをコンパイルする言語処理系の処理は確実に終了することが担保されている必要があるため、 Concrete Evaluationを行うためにはこのterminateという条件が必要になるのです。

以上の3つの性質がConcrete Evaluationを行うための条件であり、我々はこれらの性質をまとめてエフェクト (Computational Effect)と呼んでいます⁵。

逆にいうと、次のような関数simpleの呼び出しsimple(42)は、以上の条件を満たすためConcrete Evaluationすることが可能です:

function simple(a)
    return sin(a) + cos(a)
end

function simple(a)

return sin(a) + cos(a)

end

effect_free: sin(::Int) :: Float64、cos(::Int) :: Float64および::Float64 + ::Float64の実行は外部環境の状態を変更することがない
consistent: simple(a::Int)の返り値は、同一の入力aに対して常に同一である
terminate: simple(::Int)に必要な基本的な算術演算のみであり、かなり高速に終了する

つまり、次のsimple_caller関数を呼び出すたびに、 simple(42)という関数呼び出しを行う必要はなく、コンパイル時に1度実行を行った結果を保持しておいて、ランタイムではその結果を返せば良いのです:

julia> simple_caller() = simple(42);
julia> @code_typed simple_caller() # コンパイルされた`simple_caller`の中身は1つの定数値を返せば良い:
CodeInfo(
1 ─     return -1.316506862903985
) => Float64

julia> simple_caller() = simple(42);

julia> @code_typed simple_caller() # コンパイルされた`simple_caller`の中身は1つの定数値を返せば良い:

CodeInfo(

1 ─ return -1.316506862903985

) => Float64

ここで、他言語でのエフェクト解析の実装に詳しい方はもしかすると、上記のリストの中にnothrow(関数が例外を投げないこと)が条件に入ってないことが気になったかもしれませんそれはなぜかというと、Concrete Evaluationの対象の関数が例外を投げた場合でも、 consistentが担保されている限り、その関数の呼び出しは「(同一の入力に対して)常に同じように例外を投げる」ことが言えるため、 1つの実行結果で健全にその関数の呼び出しの結果を抽象化できるからです。

具体的に考えてみましょう。先ほど考えたsimple関数は、呼び出しa = Infという入力に対して例外を送出します:

julia> simple(Inf)
ERROR: DomainError with Inf:
sin(x) is only defined for finite x.
Stacktrace:
 [1] sin_domain_error(x::Float64)
   @ Base.Math ./special/trig.jl:28
 [2] sin(x::Float64)
   @ Base.Math ./special/trig.jl:39
 [3] simple(a::Float64)
   @ Main ./none:2
 [4] top-level scope
   @ none:1

julia> simple(Inf)

ERROR: DomainError with Inf:

sin(x) is only defined for finite x.

Stacktrace:

[1] sin_domain_error(x::Float64)

@ Base.Math ./special/trig.jl:28

[2] sin(x::Float64)

@ Base.Math ./special/trig.jl:39

[3] simple(a::Float64)

@ Main ./none:2

[4] top-level scope

@ none:1

ここでInfという引数値は定数値であるため、そのconsistent-cyから、simple関数はa = Infという入力に対して常に同じように例外を投げることが言えます。プログラムが例外を投げる場合は、Juliaの抽象解釈における「型がつかない場合」を表すUnion{}という特殊な型で表すことができるため、 Concrete Evaluationが例外を送出した場合はUnion{}を用いて(ある定数値に対する)全ての実行結果を健全に抽象化することができるのです:

julia> simple_caller_inf() = simple(Inf);
julia> @code_typed simple_caller_inf()
CodeInfo(
1 ─     invoke Main.simple(Main.Inf::Float64)::Union{}
└──     unreachable
) => Union{}

julia> simple_caller_inf() = simple(Inf);

julia> @code_typed simple_caller_inf()

CodeInfo(

1 ─ invoke Main.simple(Main.Inf::Float64)::Union{}

└── unreachable

) => Union{}

エフェクト解析のデザイン

それでは、Juliaプログラムにおいて関数呼び出しが持つエフェクトを自動的に導出する解析をどのように実装するかを考えてみます。

今回紹介するエフェクト解析は、Juliaコンパイラに実装されている抽象解釈に基づく型解析を前提としてデザインされています。そのため、このエフェクト解析のデザインをよく理解するためには、Juliaコンパイラが行う型解析のデザインを理解する必要があるのですが、その型解析自体の実装をここで紹介するのは大変なので、ここではハイレベルな説明に留めておくことにします。 Juliaコンパイラが行う抽象解釈に基づく型解析をより詳しく理解したい方は、こちらのブログ記事を参照してください。

さて、Juliaコンパイラが行う型解析は、前回の記事で紹介したような、ある関数呼び出しに対して、引数の型情報を次々に伝播させていくことで、その関数呼び出しが実行時にとる型を推論する解析です。抽象解釈自体は非常に汎用的なフレームワークであり、実に様々なバリエーションがありますが、ここでは以下の2つの観点から抽象解釈のデザインを考えてみます。

関数呼び出しの扱い:
- intra-procedural: 解析対象のプログラムに含まれる関数呼び出しはビルトインのもののみ、あるいは事前に型アノテーションなどから情報が得られるもののみを扱う
- inter-procedural: 解析対象のプログラムに含まれるビルトインでない関数呼び出しに対しても再帰的に解析を行う
flow-sensitivity:
- flow-insensitive: 対象のプログラムが持つ性質について、最終的な結論のみ解析する
- flow-sensitive: 対象のプログラムが持つ性質について、各ポイントにおける状態を別々に解析し、コントロールフローに沿って情報を伝播させる形で解析する

ローカルな収束のみを考えればよいintra-proceduralな抽象解釈は比較的シンプルですが、 intra-proceduralな解析で事前に型の解決がなされていないプログラムを扱うためには、プログラマによる型アノテーションや事前のインライン展開などを必要となってしまいます。

inter-proceduralな抽象解釈は、解析のエントリポイントで得られる情報を次々に伝播させていくことで、プログラマによるアノテーションを必要とせずとも、型付けの済んでいないプログラムを解析することができる一方、一方で、解析のグローバルな収束性を考慮しなくてはならず、また解析結果のキャッシュが必須になったりなど、実装が複雑になり解析のコストが増大しやすいという欠点があります。

同様に、解析をflow-sensitiveにした場合、flow-insensitiveにした場合よりもより精度の高い解析が可能ですが、プログラムの各ポイントでの抽象状態を別々に管理しなくてはならないので、解析のコストが高くなります。

以上の2つの観点から考えると、Juliaコンパイラが行う型解析は以下のように説明することができます:

inter-procedural: 解析対象の関数呼び出しに含まれる別のビルトインでない関数呼び出しについても再帰的に解析し、その返り値型を解析する
flow-sensitive: 関数呼び出しの返り値の型を推論するだけではなく、ローカル変数が各プログラムポイントでもつ型を別々に解析する

型の解決を可能な限り(実行時まで)遅らせることで、プログラムのジェネリクスを保ちつつも強力な最適化を得ようとするJuliaのプログラミングモデルでは、プログラムが本来持ちうるジェネリクスを損いかねない型アノテーションの強制や、ローカル変数の型についての制約をなるべく無くしたいことを考えれば、以上のようなデザインで型解析が実装されていることに納得できるのではないのかと思います。

つまり、何が言いたいかというと、Juliaのプログラミングモデルによる要請から、 Juliaコンパイラは既にかなり高度な抽象解釈の実装を持っているということです。

特に、inter-proceduralに抽象解釈を行うための、解析のグローバルな収束性の担保や、解析情報のキャッシュを行うためのシステムといった資産は非常に有用です。そのため、今回我々は既にある型解析を行うための抽象解釈を拡張し、それに付随する形でエフェクト解析をデザインしました。

inter-proceduralに解析を行う抽象解釈として実装されているため、プログラマが事前にエフェクトのアノテーションを与えなくても、自動的に対象の関数呼び出しが持つエフェクトを解析します。

一方型解析と異なる点としては、flow-sensitivityが挙げられます。つまり、このエフェクト解析は、対象の関数呼び出しが全体として持つエフェクトを1つだけ導出するということです。その理由は、型解析においては、関数中のローカル変数の各ポイントにおける型情報に解析する必要があるのに対し、この(Concrete Evaluationを目的とする)エフェクト解析においては、対象の関数呼び出しそれ自体が持つエフェクトにのみ興味があるということを意味しています。

具体例で考えてみましょう。次のような関数kernelがあるとします。

function kernel(n::Int)
    if n > 0
        x = n         # x::Int
        return sin(x) # sin(x::Int)::Float64
    else
        x = rand()    # x::Float64
        return cos(x) # cos(x::Float64)::Float64
    end
end

function kernel(n::Int)

if n > 0

x = n # x::Int

return sin(x) # sin(x::Int)::Float64

else

x = rand() # x::Float64

return cos(x) # cos(x::Float64)::Float64

end

kernel(::Int)という関数呼び出しを解析する場合、型解析としては、ローカル変数xが持つ型をそれぞれのif/elseブロックごとにflow-sensitiveに解析することで、 sin(x)やcos(x)といったジェネリックな関数の呼び出しがそれぞれどのメソッドにディスパッチが分かり、 xの持つ型をUnion{Int,Float64}とひとまとめにしてflow-insensitiveに解析する場合に比べて、大きく解析の精度を上げることができます。一方で、エフェクト情報としては、kernel(::Int)の呼び出しがif/elseそれぞれのブロックにおいてどのようなエフェクトを持つかは最終的に欲しい情報ではありません。 nの定数情報がわかる場合にkernelをConcrete Evaluationできるかどうかという観点においては、 kernelが全体として持つエフェクト、つまり、if/else両方のブロックで発生しうるエフェクトをひとまとめにしたエフェクトを導出すれば良いということです。

解析の大雑把なイメージを説明するためにまず、kernelに対するJuliaコンパイラの型解析の様子を確認してみます:

julia> code_typed(kernel, (Int,); optimize=false) |> only
CodeInfo(
1 ─      Core.NewvarNode(:(x))::Any
│   %2 = (n > 0)::Bool
└──      goto #3 if not %2
2 ─      (x = n)::Int64
│   %5 = Main.sin(x::Int64)::Float64
└──      return %5
3 ─      (x = Main.rand())::Float64
│   %8 = Main.cos(x::Float64)::Float64
└──      return %8
) => Float64

julia> code_typed(kernel, (Int,); optimize=false) |> only

CodeInfo(

1 ─ Core.NewvarNode(:(x))::Any

│ %2 = (n > 0)::Bool

└── goto #3 if not %2

2 ─ (x = n)::Int64

│ %5 = Main.sin(x::Int64)::Float64

└── return %5

3 ─ (x = Main.rand())::Float64

│ %8 = Main.cos(x::Float64)::Float64

└── return %8

) => Float64

Juliaコンパイラは次のようなイメージで型解析を行います:

プログラムの実行順に沿う形で、最初のステートメントからreturnステートメントに向かって順方向に解析を走らせる
(n > 0)::Boolのように、関数呼び出しのステートメントがあった場合、引数情報を伝播させてinter-proceduralに解析を行う
(x = n)::Int64/(x = Main.rand())::Float64のように、ローカル変数の型をそれぞれのプログラムポイントごとにflow-sensitiveに解析する

エフェクト解析も1つめと2つめの点では同様です。ただし3つめの点については異なり、関数呼び出しが全体として持つエフェクトをただ1つ管理し、それぞれのプログラムポイントで発生しうるローカルなエフェクトを考慮しながら、その最終的なエフェクトを解析していきます。つまり、エフェクトを次のようなデータ構造として表現した場合、

struct Effects
    consistent::Bool
    effect_free::Bool
    terminates::Bool
end
function join_effects(a::Effects, b::Effects)
    return Effects(a.consistent & b.consistent,
                   a.effect_free & b.effect_free,
                   a.terminates & b.terminates)
end

struct Effects

consistent::Bool

effect_free::Bool

terminates::Bool

end

function join_effects(a::Effects, b::Effects)

return Effects(a.consistent & b.consistent,

a.effect_free & b.effect_free,

a.terminates & b.terminates)

end

まず関数呼び出しが持つエフェクトをfinal_effects = Effects(true, true, true)として初期化したあとは、抽象解釈のメインループに沿って、各ステートメントにおけるエフェクトlocal_effects::Effectsを解析し、 final_effects = join_effects(final_effects, local_effects)のように最終的なエフェクトを更新していくことで、その関数呼び出しが全体として持ちうるエフェクトを導出するというイメージです。

後は各ステートメントにおけるローカルなエフェクトの解析ができれば、今回欲しいエフェクト解析に必要な要素が揃います。あるステートメントに対する解析としては、ビルトインでない関数呼び出しを型解析と同様inter-proceduralに再帰的に解析するとして、ビルトイン関数の呼び出し、および関数呼び出し以外のプログラム構成要素が持つエフェクトをルールとして与えることができます。具体的には、以下のようなルールを一つ一つ定義していきます:

ミュータブルなアロケーションを行うnewステートメントのエフェクトをEffects(false, true, true)とする(consistentフラグをfalseにする)
グローバル変数への書き込みを行うビルトイン関数setglobal!のエフェクトをEffects(true, false, true)とする(effect_freeフラグをfalseにする)
逆方向へのジャンプを行うgotoステートメントのエフェクトをEffects(true, true, false)とする(terminateフラグをfalseにする)

以上のエフェクト解析のデザインの利点は以下のようなものです:

型解析を行う抽象解釈に組み込むため、inter-proceduralな解析結果のキャッシュなど、既存の実装を使いまわすことができる
関数呼び出し全体のエフェクトを表すグローバルなエフェクトを1つだけ管理し、ローカルなエフェクトを保持しないことで、flow-sensitiveな型解析に比較してシンプルに解析を行うことができる
consistentやeffect_freeなどそれぞれのエフェクトは本質的には別々に解析されているため、新しいエフェクトを追加するなどの拡張がしやすい

一方で問題点もあります。このエフェクト解析の実装は、本質的には型解析を行う抽象解釈のドメインを拡張していることになります。そのため、これまでは型情報だけを考慮して抽象解釈の収束性を担保できていましたが、今回エフェクト解析を追加したことにより、厳密には、エフェクト情報も考慮して抽象解釈の収束条件を考えなくてはいけなくなっています⁶。

実際の解析結果を確認してみる

それでは、Juliaコンパイラに実装されているエフェクト解析を実際に使ってみましょう。 code_typedと同じようなインターフェースで使えるBase.infer_effectsを利用して、任意の関数呼び出しが持つエフェクトを解析することができます。試しにsin(::Int)という関数呼び出しの持つエフェクトを確認してみます:

julia> Base.infer_effects(sin, (Int,))
(+c,+e,!n,+t,+s,!m,+i)

1 2	julia> Base.infer_effects(sin, (Int,)) (+c,+e,!n,+t,+s,!m,+i)

記号の意味は以下のようになっています:

アルファベットでない記号:
- +: 次のアルファベットで表される性質が保証されていることを表す
- !: 次のアルファベットで表される性質が保証されていないことを表す
- (?: 次のアルファベットで表される性質はこの関数呼び出し単体としては保証されていないが、この関数を呼び出すコンテクストによってはこの性質が保証されうることを表す)
アルファベット:
- c: consistentを表す
- e: effect_freeを表す
- n: nothrowを表す
- t: terminateを表す
- s: notaskstate(タスクローカルな状態へのアクセスがないこと)を表す
- m: inaccessiblememonly(LLVM表現における同一名のアトリビューションと対応)を表す
- i: noinbounds(@inbounds/@boundscheckによるconsistentのテイントがないこと)を表す

この記事で紹介していないエフェクトもありますが、 Concrete Evaluationを考える場合はc/e/tのみを確認すれば大丈夫です。上記の出力ではsin(::Int)のエフェクトは(+c,+e,!n,+t,+s,!m,+i)と推論されているので、 sin(::Int)の呼び出しがConcrete Evaluation可能なことがわかります。

Core.Compiler.is_foldableというユーティリティクエリを使ってテストを行うこともできます:

julia> using Test
julia> @test Core.Compiler.is_foldable(Base.infer_effects(sin, (Int,)))
Test Passed

julia> using Test

julia> @test Core.Compiler.is_foldable(Base.infer_effects(sin, (Int,)))

Test Passed

次にこの記事の前半で紹介した関数のエフェクトも確認してみましょう。保証されるべきでない性質が正しくテイントされているのが確認できると思います:

julia> Base.infer_effects(effectful)
(!c,!e,!n,+t,+s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(effectful))
false
julia> Base.infer_effects(inconsistent, (Int,))
(!c,!e,!n,!t,!s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(inconsistent, (Int,)))
false
julia> Base.infer_effects(inconsistent_alloc, (Int,))
(!c,+e,!n,+t,+s,+m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(inconsistent_alloc, (Int,)))
false
julia> Base.infer_effects(may_not_terminate, (Int,))
(+c,+e,!n,!t,+s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(may_not_terminate, (Int,)))
false

julia> Base.infer_effects(effectful)

(!c,!e,!n,+t,+s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(effectful))

false

julia> Base.infer_effects(inconsistent, (Int,))

(!c,!e,!n,!t,!s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(inconsistent, (Int,)))

false

julia> Base.infer_effects(inconsistent_alloc, (Int,))

(!c,+e,!n,+t,+s,+m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(inconsistent_alloc, (Int,)))

false

julia> Base.infer_effects(may_not_terminate, (Int,))

(+c,+e,!n,!t,+s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(may_not_terminate, (Int,)))

false

Juliaプログラマが利用可能なアノテーション

Juliaコンパイラが行う抽象解釈に基づく解析は、「できる限りの範囲で詳細に」といったスタンスで、もっぱら最適化を目的として行われるものであるため、場合によっては欲しい解析結果が得られない場合があります。

現在の解析の実装では、具体的に以下のような場合で解析の精度が得られないことがあります:

ループ/再帰呼び出しを含むコード: terminateが保証できないことが多い
ccallを含むコード: foreignコードのエフェクトは解析不能なため、全ての性質の保証ができない
@inbounds/@boundscheckを含むコード: --check-boundsフラグ、またはコンテクストごとの@inboundsの有無によって挙動が変化してしまうため、consistentが保証できない場合が多い

例えば、以下のような関数foldable(n::Int)を考えてみます:

function foldable(n::Int)
    n > 20 && error("`n` is expected to be lower than 20")
    s = 0.0
    for i = 1:n
        s += sin(i)
    end
    return s
end

function foldable(n::Int)

n > 20 && error("`n` is expected to be lower than 20")

s = 0.0

for i = 1:n

s += sin(i)

end

return s

end

foldable(n::Int)のエフェクトを確認すると、terminateがうまく解析できていないことがわかります:

julia> Base.infer_effects(foldable, (Int,))
(+c,+e,!n,!t,+s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(foldable, (Int,)))
false
julia> code_typed(; optimize=false) do
           foldable(15) # Concrete Evaluationできない
       end |> only
CodeInfo(
1 ─ %1 = Main.foldable(15)::Float64
└──      return %1
) => Float64

julia> Base.infer_effects(foldable, (Int,))

(+c,+e,!n,!t,+s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(foldable, (Int,)))

false

julia> code_typed(; optimize=false) do

foldable(15) # Concrete Evaluationできない

end |> only

CodeInfo(

1 ─ %1 = Main.foldable(15)::Float64

└── return %1

) => Float64

これは、Juliaコンパイラの抽象解釈が現状のところループ終了条件をうまく判定できないからなのですが、ループ終了条件の解析は一般にかなり難しく、今後も実装できるか微妙なところです。一方このコードを書いた我々プログラマとしては、n ≤ 20という条件からこのループが常に終了するということは容易にわかります。こんな時には、Base.@assume_effectsによるアノテーションを用いてその事実をJuliaコンパイラに教えてあげることができます:

# `:terminates_locally`アノテーションを用いて、`foldable`内のループが終了することをコンパイラに教える
julia> Base.@assume_effects :terminates_locally function foldable(n::Int)
           n > 20 && error("`n` is expected to be lower than 20")
           s = 0.0
           for i = 1:n
               s += sin(i)
           end
           return s
       end;
julia> Base.infer_effects(foldable, (Int,))
(+c,+e,!n,+t,+s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(foldable, (Int,)))
true
julia> code_typed(; optimize=false) do
           foldable(15) # # Concrete Evaluation可能
       end |> only
CodeInfo(
1 ─ %1 = Main.foldable(15)::Core.Const(1.9356874793455001)
└──      return %1
) => Float64

# `:terminates_locally`アノテーションを用いて、`foldable`内のループが終了することをコンパイラに教える

julia> Base.@assume_effects :terminates_locally function foldable(n::Int)

n > 20 && error("`n` is expected to be lower than 20")

s = 0.0

for i = 1:n

s += sin(i)

end

return s

end;

julia> Base.infer_effects(foldable, (Int,))

(+c,+e,!n,+t,+s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(foldable, (Int,)))

true

julia> code_typed(; optimize=false) do

foldable(15) # # Concrete Evaluation可能

end |> only

CodeInfo(

1 ─ %1 = Main.foldable(15)::Core.Const(1.9356874793455001)

└── return %1

) => Float64

Base.@assume_effectsを用いて@ccallのエフェクトを与えることもできます。スペシャルケースされている一部のccallを除いて、ほとんどのccallはデフォルトで全てのエフェクト性質をテイントしてしまうので、もしccallを含むコードをConcrete Evaluationしたい場合はBase.@assume_effectsを使う必要があります:

julia> Base.infer_effects((Type,Type)) do s, t
           Base.@assume_effects :total !:nothrow @ccall jl_type_intersection(s::Any, t::Any)::Any
       end
(+c,+e,!n,+t,+s,+m,+i)

julia> Base.infer_effects((Type,Type)) do s, t

Base.@assume_effects :total !:nothrow @ccall jl_type_intersection(s::Any, t::Any)::Any

end

(+c,+e,!n,+t,+s,+m,+i)

また同様の理由から、I/Oを含むコードの多くはConcrete Evaluationできません。特にエラーメッセージなどでInterpolationを使っている時に発生します:

julia> function unfoldable(n::Int)
           n > 20 && error("`n` is expected to be lower than 20, but given $n")
           return sin(n)
       end;
julia> Base.infer_effects(unfoldable, (Int,))
(!c,!e,!n,!t,!s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(unfoldable, (Int,)))
false

julia> function unfoldable(n::Int)

n > 20 && error("`n` is expected to be lower than 20, but given $n")

return sin(n)

end;

julia> Base.infer_effects(unfoldable, (Int,))

(!c,!e,!n,!t,!s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(unfoldable, (Int,)))

false

そんな時は、@lazy_strを使うことでこの問題を回避できます。 @lazy_strによって作られるLazyStringオブジェクトは通常のStringと同じように振る舞いますが、そのI/O出力はエラーの発生時など必要な時まで遅延されているので、エラーメッセージとしてLazyStringを使うことによって、 I/Oによるエフェクトのテイントを回避することができるのです:

julia> function lazy_foldable(n::Int)
           n > 20 && error(lazy"`n` is expected to be lower than 20, but given $n")
           return sin(n)
       end;
julia> Base.infer_effects(lazy_foldable, (Int,))
(+c,+e,!n,+t,+s,!m,+i)
julia> Core.Compiler.is_foldable(Base.infer_effects(lazy_foldable, (Int,)))
true

julia> function lazy_foldable(n::Int)

n > 20 && error(lazy"`n` is expected to be lower than 20, but given $n")

return sin(n)

end;

julia> Base.infer_effects(lazy_foldable, (Int,))

(+c,+e,!n,+t,+s,!m,+i)

julia> Core.Compiler.is_foldable(Base.infer_effects(lazy_foldable, (Int,)))

true

最適化したいコードのエフェクトがうまく解析されていない時に、具体的にどこでエフェクトがテイントされているか調べたい時は、 Cthulhu.jlのwith_effectsオプションが便利です:

julia> descend(unfoldable, (Int,); optimize=false, with_effects=true)
unfoldable(n::Int64) @ Main REPL[1]:1
Variables
  #self#::Core.Const(unfoldable)
  n::Int64
∘ ─ %0 = invoke unfoldable(::Int64)::Float64 (!c,!e,!n,!t,!s,!m,+i)
    @ REPL[1]:2 within `unfoldable`
1 ─ %1 = (n > 20)::Bool (+c,+e,+n,+t,+s,+m,+i)
└──      goto #3 if not %1
2 ─ %3 = Base.string("`n` is expected to be lower than 20, but given ", n)::String (!c,!e,!n,!t,!s,!m,+i)
│        Main.error(%3)::Union{} (+c,+e,!n,+t,+s,+m,+i)
└──      Core.Const(:(goto %6))::Union{}
    @ REPL[1]:3 within `unfoldable`
3 ┄ %6 = Main.sin(n)::Float64 (+c,+e,!n,+t,+s,!m,+i)
└──      return %6
Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.
Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.
Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code
Actions: [E]dit source code, [R]evise and redisplay
Advanced: dump [P]arams cache.
 • %1 = >(::Int64,::Int64)::Bool (+c,+e,+n,+t,+s,+m,+i)
   %3 = string(::String,::Int64)::String (!c,!e,!n,!t,!s,!m,+i)
   %4 = error(::String)::Union{} (+c,+e,!n,+t,+s,+m,+i)
   %6 = sin(::Int64)::Float64 (+c,+e,!n,+t,+s,!m,+i)
   ↩

julia> descend(unfoldable, (Int,); optimize=false, with_effects=true)

unfoldable(n::Int64) @ Main REPL[1]:1

Variables

#self#::Core.Const(unfoldable)

n::Int64

∘ ─ %0 = invoke unfoldable(::Int64)::Float64 (!c,!e,!n,!t,!s,!m,+i)

@ REPL[1]:2 within `unfoldable`

1 ─ %1 = (n > 20)::Bool (+c,+e,+n,+t,+s,+m,+i)

└── goto #3 if not %1

2 ─ %3 = Base.string("`n` is expected to be lower than 20, but given ", n)::String (!c,!e,!n,!t,!s,!m,+i)

│ Main.error(%3)::Union{} (+c,+e,!n,+t,+s,+m,+i)

└── Core.Const(:(goto %6))::Union{}

@ REPL[1]:3 within `unfoldable`

3 ┄ %6 = Main.sin(n)::Float64 (+c,+e,!n,+t,+s,!m,+i)

└── return %6

Select a call to descend into or ↩ to ascend. [q]uit. [b]ookmark.

Toggles: [o]ptimize, [w]arn, [h]ide type-stable statements, [d]ebuginfo, [r]emarks, [e]ffects, [i]nlining costs, [t]ype annotations, [s]yntax highlight for Source/LLVM/Native.

Show: [S]ource code, [A]ST, [T]yped code, [L]LVM IR, [N]ative code

Actions: [E]dit source code, [R]evise and redisplay

Advanced: dump [P]arams cache.

• %1 = >(::Int64,::Int64)::Bool (+c,+e,+n,+t,+s,+m,+i)

%3 = string(::String,::Int64)::String (!c,!e,!n,!t,!s,!m,+i)

%4 = error(::String)::Union{} (+c,+e,!n,+t,+s,+m,+i)

%6 = sin(::Int64)::Float64 (+c,+e,!n,+t,+s,!m,+i)

↩

エフェクトのさらなる応用可能性

今回我々はConcrete Evaluationを行うためにエフェクト解析を導入しましたが、実はエフェクトは他の様々な最適化に応用できます。実際に既にJuliaコンパイラで実装されている、エフェクトを利用した最適化には以下のようなものがあります:

デッドコールエリミネーション(Dead Call Elimination):
- 返り値が利用されていない関数呼び出しを削除する
- nothrow, effect_free, terminateが証明された関数呼び出しに対して適用可能
- Core.Compiler.is_removable_if_unusedクエリでテスト可能
Finalizer Inlining
- オブジェクトの生存区間の最後にfinalizer呼び出しをインライン展開する
- nothrow, notaskstateが証明されたfinalizerについて適用可能
- Core.Compiler.is_finalizer_inlineableクエリでテスト可能

さらに、ループやmapなどを自動的に並列化する"Automatic Parallelization"なども可能になります。また、エフェクトのドメインをさらに拡張し、エスケープ情報なども組み込むことで、スタックアロケーションやより強力なSROAなどもできるのではないかと考えています。

まとめ

この記事では、前回の記事の内容を前提として、 Concrete Evaluationを行うために必要なエフェクトシステムを考察し、そうしたエフェクトを導出するためにJuliaコンパイラに実装された解析のデザインを紹介しました。また、Juliaプログラマがコード最適化を行う上で利用可能なエフェクトアノテーションや、 Juliaコンパイラがそのエフェクトを証明しやすいコードを書くためのtipsも紹介しました。

今後もJuliaに関する様々な内容を発信していきます。ぜひ楽しみにお待ちください。

ConstはJuliaコンパイラの抽象解釈の実装における定数値を表す特殊な抽象状態。↩︎
https://github.com/JuliaLang/julia/blob/c9eccfc1e863bcbf7ef3be55403c5bcd60a1494e/base/special/trig.jl#L29-L52から引用。↩︎
この記事での「同一性」はJulia処理系内における同一性、つまり===関数がtrueを返すような関係を指します。↩︎
この「終了性」は言葉通りの意味よりもより強い制約であり、「この関数fをコンパイルプロセスで呼び出しても問題ないくらい素早く終了する」といったくらいの意味を指します。↩︎
ここまでかなりざっくりと「エフェクト」を定義してきましたが、これらの定義がJulia言語処理系に特有のエフェクトの定義であることをここで断っておきます。 Julia言語処理系における「エフェクト」の定義のより具体的な説明については、こちらのドキュメントをご参照ください。↩︎
現状のJuliaコンパイラにおいては、この2つの異なるドメインを正しく考慮して抽象解釈の収束条件を判定している訳ではなく、型情報が収束すればエフェクト情報も収束すると仮定して、型情報のみを用いて収束条件を判定しています。↩︎

Recruit Tech Blog

タグから見つける

タグから見つける

職種を選択

事業領域を選択

エフェクト解析による動的言語最適化 Part.2

おさらい: Juliaプログラムのコンパイルを最適化するアイディア Concrete Evaluation

定数伝播と Concrete Evaluation

Concrete Evaluationに必要なエフェクトシステム

エフェクト解析のデザイン

実際の解析結果を確認してみる

Juliaプログラマが利用可能なアノテーション

エフェクトのさらなる応用可能性

まとめ