Julia SSA-form IR

Julia は最適化を行うために、静的単一代入形式の中間表現(SSA IR)を使用します。この IR は LLVM IR とは異なり、Julia 独自のものです。Julia 固有の最適化を可能にします。

  1. 基本ブロック(制御フローを含まない領域)は、明示的に注釈されます。
  2. if/else 文やループは、goto 文に変換されます。
  3. 複数の演算を含む行は、変数を導入して複数の行に分割されます。

たとえば、次の Julia コードは、

function foo(x)
    y = sin(x)
    if x > 5.0
        y = y + cos(x)
    end
    return exp(2) + y
end

Float64 引数を渡して呼び出すと、次のように変換されます。

using InteractiveUtils
@code_typed foo(1.0)
CodeInfo(
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
2 ─ %4 = invoke Main.cos(x::Float64)::Float64
└── %5 = Base.add_float(%1, %4)::Float64
3 ┄ %6 = φ (#2 => %5, #1 => %1)::Float64
│   %7 = Base.add_float(7.38905609893065, %6)::Float64
└──      return %7
) => Float64

この例では、これらの変更をすべて確認できます。

  1. 最初の基本ブロックは、次の部分全体です。
1 ─ %1 = invoke Main.sin(x::Float64)::Float64
│   %2 = Base.lt_float(x, 5.0)::Bool
└──      goto #3 if not %2
  1. if 文は goto #3 if not %2 に変換されます。x>5 が満たされない場合は第 3 基本ブロックへ、満たされる場合は第 2 基本ブロックへ進みます。
  2. %2 は、x > 5 を表すために導入された SSA 値です。

Background

Julia 0.7 以降、コンパイラの一部では、新しい SSA-form 中間表現(IR)が使われています。従来、コンパイラは Julia の AST を低レベル化した形式から LLVM IR を直接生成していました。この形式では構文上の抽象化の大部分が取り除かれていましたが、依然として抽象構文木にかなり近いものでした。最適化を容易にするため、時間をかけて SSA 値がこの IR に導入され、IR は線形化されました(つまり、関数の引数が SSA 値または定数だけで構成される形式に変換されました)。しかし、IR に Phi ノードがなかったため(バックエッジや条件分岐後の制御フローの合流に必要です)、非 SSA 値(スロット)は IR に残っていました。そのため、中間段階の最適化で SSA 形式の表現を使う利点の多くが失われていました。完全な SSA 形式の表現を使わずにこれらの最適化を実現するため、多大な努力が払われましたが、最終的には、そのような表現がないことが大きな障害となりました。

Categories of IR nodes

SSA IR の表現には、Phi、Pi、PhiC、Upsilon の 4 種類の IR ノードがあります(後者 2 つは例外処理でのみ使われます)。

Phi nodes and Pi nodes

Phi ノードは、一般的な SSA 抽象化の一部です(この概念に馴染みがなければ、上のリンクを参照してください)。Julia IR では、これらのノードは次のように表されます。

struct PhiNode
    edges::Vector{Int32}
    values::Vector{Any}
end

ここでは、2 つのベクトルの長さが常に同じになるようにしています。標準的な表現(コード生成器とインタープリターが扱う表現)では、エッジ値は到達元の文番号を示します(つまり、エッジに 15 が含まれる場合、この Phi ノードを対象とする goto、gotoifnot、または文 15 からの暗黙のフォールスルーが存在しなければなりません)。値は SSA 値または定数です。その経路で変数が定義されていない場合、値が未割り当てになることもあります。ただし、中間段階の最適化後には未定義性チェックが明示的に挿入され、ブール値として表されます。そのため、コード生成器は、Phi ノードの値が使われるとき、対応するスロットに値が割り当てられていると仮定できます。対応関係が不完全であること、つまり Phi ノードに欠けている入力エッジがあることも許されます。その場合、対応する値が使われないことが動的に保証されていなければなりません。

SSA の使用は、意味上、対応する先行ブロックの終端の後(「エッジ上」)に発生する点に注意してください。したがって、基本ブロックの先頭に複数の Phi ノードがある場合、それらは同時に実行されます。つまり、次の IR 断片でブロック 23 から来た場合、%46 は、このブロックに入る前の %45 に対応する値を取ります。

%45 = φ (#18 => %23, #23 => %50)
%46 = φ (#18 => 1.0, #23 => %45)

PiNode は、ある Pi ノードに支配される基本ブロック内で暗黙に仮定できる、静的に証明された情報を符号化します。概念的には、論文 ABCD: Eliminating Array Bounds Checks on Demand で紹介された手法や、LLVM の predicate info ノードと同等です。仕組みを確認するため、たとえば次のコードを考えてみましょう。

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    # use x
else
    # use x
end

述語の挿入を行うと、次のように変換できます。

%x::Union{Int, Float64} # %x is some Union{Int, Float64} typed ssa value
if isa(x, Int)
    %x_int = PiNode(x, Int)
    # use %x_int
else
    %x_float = PiNode(x, Float64)
    # use %x_float
end

Pi ノードは値に影響しないため、通常インタープリターでは無視されます。ただし、コンパイラではコード生成につながることがあります(たとえば、暗黙的なユニオン分割表現から、通常のボックス化されていない表現に切り替える場合など)。PiNode の主な利点は、これらの条件を考慮する最適化の多くで通常行われる def-use チェーンの走査だけで、値のパス条件を蓄積できることです。

PhiC nodes and Upsilon nodes

例外処理によって、値を追跡しなければならない制御フローエッジが IR に追加されるため、SSA の扱いはやや複雑になります。LLVM が採用している方法の 1 つは、例外を投げる可能性のある呼び出しを基本ブロックの終端にし、catch ハンドラーへの制御フローエッジを明示的に追加することです。

invoke @function_that_may_throw() to label %regular unwind to %catch

regular:
# Control flow continues here

catch:
# Exceptions go here

しかし、最適化パイプラインの開始時点では、どの呼び出しが例外を投げるか分からない Julia のような言語では、この方法に問題があります。すべての呼び出し(Julia ではすべての文に相当します)が例外を投げると保守的に仮定しなければなりません。これには、いくつかの悪影響があります。一方では、基本ブロックの範囲が実質的に各呼び出し 1 つだけになり、基本ブロック単位で演算を行う目的が損なわれます。他方では、各 catch 基本ブロックに n*m 個の Phi ノード引数が必要になります(n はクリティカル領域内の文の数、m は catch ブロックを通じて生存する値の数です)。

この問題を回避するため、Upsilon ノードと PhiC ノードを組み合わせて使います(C は catch を表します。IR の整形表示では、Unicode の下付き文字 c が使えないため φᶜ と表記されます)。これらのノードの捉え方はいくつかありますが、最も簡単なのは、各 PhiC を、一意の「複数回書き込み・1 回読み出し」スロットからの読み出しと考えることです。Upsilon は、それに対応する書き込み操作です。PhiC は、暗黙のスロットに書き込むすべての upsilon ノードをオペランドリストに持ちます。一方、Upsilon ノードには、どの PhiC ノードに書き込むかが記録されません。これは、ほかの SSA IR との統合をより自然にするためです。たとえば、PhiC ノードが使われなくなれば、安全に削除できます。Upsilon ノードについても同様です。ほとんどの IR パスでは、PhiC ノードを Phi ノードと同様に扱えます。use-def チェーンをたどることができ、元の Upsilon ノードと同じ場所に、新しい PhiC ノードや Upsilon ノードを持ち上げることもできます。この方式では、Upsilon ノード(および PhiC 引数)の数は、クリティカル領域内の文の数ではなく、特定の変数に値が割り当てられた回数(SSA 変換前)に比例します。

この方式の動作を確認するため、次の関数を考えてみましょう。

@noinline opaque() = invokelatest(identity, nothing) # Something opaque
function foo()
    local y
    x = 1
    try
        y = 2
        opaque()
        y = 3
        error()
    catch
    end
    (x, y)
end

対応する IR(関係のない型情報を除いたもの)は次のとおりです。

1 ─       nothing::Nothing
2 ─ %2  = $(Expr(:enter, #4))
3 ─ %3  = ϒ (false)
│   %4  = ϒ (#undef)
│   %5  = ϒ (1)
│   %6  = ϒ (true)
│   %7  = ϒ (2)
│         invoke Main.opaque()::Any
│   %9  = ϒ (true)
│   %10 = ϒ (3)
│         invoke Main.error()::Union{}
└──       $(Expr(:unreachable))::Union{}
4 ┄ %13 = φᶜ (%3, %6, %9)::Bool
│   %14 = φᶜ (%4, %7, %10)::Core.Compiler.MaybeUndef(Int64)
│   %15 = φᶜ (%5)::Core.Const(1)
└──       $(Expr(:leave, Core.SSAValue(2)))
5 ─       $(Expr(:pop_exception, :(%2)))::Any
│         $(Expr(:throw_undef_if_not, :y, :(%13)))::Any
│   %19 = Core.tuple(%15, %14)
└──       return %19

特に、クリティカル領域に入る時点で生存している値には、すべてクリティカル領域の先頭に upsilon ノードがあることに注目してください。catch ブロックには、関数の外部からの不可視な制御フローエッジがあると見なされるためです。その結果、catch ブロックを支配する SSA 値は存在せず、すべての入力値は φᶜ ノードを経由しなければなりません。

Main SSA data structure

主要な SSAIR データ構造について説明する価値があります。この構造は LLVM と WebKit の B3 IR に着想を得ています。データ構造の中核は、文を格納したフラットなベクトルです。各文には、ベクトル内の位置に基づいて暗黙的に SSA 値が割り当てられます(つまり、位置 1 の文の結果には SSAValue(1) などを使ってアクセスできます)。さらに、各 SSA 値の型も保持します。SSA 値は定義上、一度だけ割り当てられるため、この型は対応する位置にある式の結果型でもあります。ただし、この表現は比較的効率的である一方(代入を明示的に符号化する必要がないため)、順序が意味上重要になるという欠点があります。そのため、並べ替えや挿入を行うと文番号が変わります。また、use リストも保持しません(つまり、この対応表を明示的に計算しない限り、定義からすべての使用箇所をたどることはできません。ただし、def リストはインデックスから対応する文を参照できるため簡単に得られます)。そのため、LLVM 形式の RAUW(すべての使用箇所を置換する)操作は利用できません。

代わりに、次のようにしています。

  • 挿入するノードを別のバッファに保持します。バッファには、挿入位置、対応する値の型、ノード自体が含まれます。これらのノードには挿入バッファ内での出現順に番号が付けられるため、IR 内の別の場所からすぐにその値を使えます(たとえば、元の文リストに 12 個の文がある場合、最初に追加する文には SSAValue(13) でアクセスできます)。
  • RAUW 形式の操作は、対応する文のインデックスを置換後の値に設定して行います。
  • 文を削除するには、対応する文を nothing に設定します(これは、上記の仕組みに対する特殊な規約にすぎません)。
  • 削除する文が使われている場合、その使用箇所は nothing に設定されます。

上記のデータ構造を整理する compact! 関数があります。この関数は、ノードを適切な位置に挿入し、単純なコピー伝播を行い、変更された SSA 値を使う箇所の名前を付け替えます。しかし、この方式の巧妙な点は、後続のパスの一部として、この整理を遅延実行できることです。ほとんどの最適化パスは、解析や変更を行いながら文のリスト全体を走査する必要があります。そのため、文リストを走査するための IncrementalCompact イテレーターを用意しています。このイテレーターは必要な整理を行い、ノード自体とともに新しいインデックスを返します。この時点では、def-use チェーンをたどることも、IR を変更または削除することもできます(ただし、挿入はできません)。

この仕組みの考え方は、最適化パスがいずれにせよ該当するメモリにアクセスし、そのアクセスコストを負担するため、その際に追加の管理処理を行ってもオーバーヘッドは比較的小さい、というものです。また、IR の変更中にこれらのデータ構造を維持するコストも削減できます。