GitHub

Julia SSA-form IR

ジュリアは、最適化を行うために静的単一割り当て中間表現（SSA IR）を使用します。このIRはLLVM IRとは異なり、ジュリア特有のものです。ジュリア特有の最適化を可能にします。

  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値または定数のみになる形式に変換されました）。しかし、PhiノードがIRに存在しないため（バックエッジや条件付き制御フローの再統合に必要）、非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

両方のベクトルが常に同じ長さを持つことを保証する場所です。標準的な表現（codegenとインタプリタが扱うもの）では、エッジの値は来る文の番号を示します（つまり、エッジに15のエントリがある場合、文15からこのphiノードをターゲットにするgoto、gotoifnot、または暗黙のフォールスルーが必要です）。値はSSA値または定数です。また、変数がこのパスで定義されていなかった場合、値が未割り当てであることも可能です。ただし、未定義チェックは明示的に挿入され、中間エンドの最適化後にブール値として表現されるため、コード生成器はPhiノードの使用が対応するスロットに割り当てられた値を持つと仮定できます。また、マッピングが不完全であること、つまりPhiノードに欠落した入力エッジがあることも合法です。その場合、対応する値が使用されないことが動的に保証されなければなりません。

SSAは、対応する前駆体の終端子の後に意味的に発生することを使用します（「エッジ上で」）。したがって、基本ブロックの先頭に複数のPhiノードが出現する場合、それらは同時に実行されます。これは、次のIRスニペットにおいて、ブロック23から来た場合、%46はこのブロックに入る前に%45に関連付けられた値を取ることを意味します。

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

PiNodesは、特定のpiノードによって支配される基本ブロックで暗黙的に仮定される可能性のある静的に証明された情報をエンコードします。これは、論文ABCD: Eliminating Array Bounds Checks on Demandで導入された技術や、LLVMの述語情報ノードと概念的に同等です。彼らがどのように機能するかを理解するために、例えば考えてみてください。

%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ノードは一般的にインタプリタでは無視されます。なぜなら、それらは値に影響を与えないからですが、コンパイラではコード生成につながることがあります（例えば、暗黙のユニオン分割表現からプレーンなアンボックス表現に変更するためなど）。Piノードの主な有用性は、値のパス条件を、これらの条件を気にするほとんどの最適化のために一般的に行われるdef-useチェーンウォーキングによって簡単に蓄積できるという事実にあります。

PhiC nodes and Upsilon nodes

例外処理はSSAのストーリーを中程度に複雑にします。なぜなら、例外処理はIRに追加の制御フローエッジを導入し、その間で値を追跡する必要があるからです。これを行う一つのアプローチは、LLVMが採用しているもので、例外をスローする可能性のある呼び出しを基本ブロックの終端に置き、キャッチハンドラへの明示的な制御フローエッジを追加することです。

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

regular:
# Control flow continues here

catch:
# Exceptions go here

しかし、これはJuliaのような言語では問題があります。最適化パイプラインの開始時点では、どの呼び出しが例外を投げるかがわからないためです。私たちは、すべての呼び出し（Juliaではすべての文）が例外を投げると保守的に仮定しなければなりません。これにはいくつかの悪影響があります。一方では、基本ブロックの範囲が実質的に単一の呼び出しに制限され、基本ブロックレベルで操作を実行する目的が失われます。他方では、すべてのcatch基本ブロックにはn*mのphiノード引数が必要になります（nはクリティカル領域内の文の数、mはcatchブロックを通過するライブ値の数です）。

この問題を回避するために、Upsilon と PhiC ノードの組み合わせを使用します（Cは catch を意味し、IRのプリティプリンタでは φᶜ と書かれています。Unicodeの下付きcは利用できないためです）。これらのノードを考える方法はいくつかありますが、おそらく最も簡単なのは、各 PhiC をユニークなストア・マニー、リード・ワンスのスロットからのロードとして考えることです。Upsilon は対応するストア操作です。PhiC には、その暗黙のスロットにストアするすべてのアップサイロンノードのオペランドリストがあります。しかし、Upsilon ノードは、どの PhiC ノードにストアするかを記録しません。これは、SSA IRの他の部分とのより自然な統合のために行われています。例えば、PhiC ノードの使用がもうない場合、それを削除するのは安全であり、Upsilon ノードについても同様です。ほとんどのIRパスでは、PhiC ノードは Phi ノードのように扱うことができます。使用-定義チェーンをたどることができ、新しい PhiC ノードや新しい Upsilon ノードに持ち上げることができます（元の 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

特に注意すべきは、すべての値がクリティカル領域に入ると、クリティカル領域の上部にアップシロンノードが付与されることです。これは、キャッチブロックが関数の外部からの見えない制御フローエッジを持つと見なされるためです。その結果、SSA値はキャッチブロックを支配せず、すべての入力値は φᶜ ノードを通過する必要があります。

Main SSA data structure

主な SSAIR データ構造は議論の価値があります。これは LLVM と Webkit の B3 IR からインスピレーションを得ています。このデータ構造の核心は、ステートメントのフラットなベクターです。各ステートメントは、そのベクター内の位置に基づいて暗黙的に SSA 値が割り当てられます（つまり、インデックス 1 のステートメントの結果は SSAValue(1) を使用してアクセスできます）。各 SSA 値について、さらにその型を維持します。SSA 値は定義上一度だけ割り当てられるため、この型は対応するインデックスの式の結果型でもあります。しかし、この表現はかなり効率的である一方（割り当てを明示的にエンコードする必要がないため）、順序が意味的に重要であるという欠点もあります。したがって、順序の変更や挿入はステートメント番号を変更します。さらに、使用リストは保持していないため（つまり、定義からすべての使用に移動することは、このマップを明示的に計算しない限り不可能です）、LLVM スタイルの RAUW（すべての使用を置き換える）操作は利用できません。

その代わりに、私たちは次のことを行います：

  • ノードを挿入するための別のバッファを保持しています（挿入する位置、対応する値のタイプ、およびノード自体を含む）。これらのノードは挿入バッファ内での出現に基づいて番号付けされており、その値はIRの他の場所ですぐに使用できるようになっています（つまり、元のステートメントリストに12のステートメントがある場合、最初の新しいステートメントはSSAValue(13)としてアクセス可能です）。
  • RAUWスタイルの操作は、対応するステートメントインデックスを置き換え値に設定することによって実行されます。
  • ステートメントは、対応するステートメントを nothing に設定することで消去されます（これは本質的に上記の特別なケースの慣習です）。
  • もしその文が消去される場合、使用されているすべての箇所は nothing に設定されます。

compact! 関数は、ノードの挿入を適切な場所で行い、単純なコピー伝播を行い、変更された SSA 値に対して使用をリネームすることによって、上記のデータ構造を圧縮します。しかし、このスキームの巧妙な部分は、この圧縮が次のパスの一部として遅延的に行えることです。ほとんどの最適化パスは、ステートメントのリスト全体を歩きながら、分析や修正を行う必要があります。私たちは、ステートメントリストを反復処理するために使用できる IncrementalCompact イテレータを提供します。これにより、必要な圧縮が行われ、新しいノードのインデックスとノード自体が返されます。この時点で、def-use チェーンを歩くことや、IR に対して修正や削除を行うことは合法ですが、挿入は許可されていません。

この配置の背後にあるアイデアは、最適化パスが対応するメモリに触れる必要があり、対応するメモリアクセスのペナルティが発生するため、追加のハウスキーピングを行うことは比較的少ないオーバーヘッドで済むはずであり（IRの変更中にこれらのデータ構造を維持するためのオーバーヘッドを節約する）、ということです。