Ruby: Shopifyによる新しい高速な静的型分析の実験（翻訳）

Ruby: Shopifyによる新しい高速な静的型分析の実験（翻訳）

11時をお知らせします。皆さんの大事な変数がどこを指しているかちゃんと把握していますか？¹

def shout(obj)
  obj.to_s + "!"
end

このコードを見ただけでobjの型を判断するのは困難です。to_sメソッドがあることを前提とするにしても、to_sという名前のメソッドは多くのクラスで定義されています。ここで呼び出しているのは果たしてどのto_sメソッドでしょう？shoutメソッドの戻り値型は？to_sが返すものがStringでない場合、こういったことを判断するのは非常に難しくなります。

型アノテーションを追加すれば、少しはましになるでしょうか。型がわかっていれば個別のものが何であるかについて完全な知識を得られそうに思えますが、実はそうはいきません。

Rubyは他の多くのオブジェクト指向言語と同様に「継承」と呼ばれる機能を備えています。つまり、IntegerやStringなどの型シグネチャは、そのクラスのインスタンスであることを意味することもあれば、そのクラスの「サブクラスの」インスタンスであることを意味することもあります。

さらに、段階的型チェッカー（例: Sorbet）にはT.unsafeやT.untypedといった機能が備わっていて、これを使うと型チェッカーにウソをつくことが可能になります。残念ながら、こうしたアノテーションのせいで、実行時型チェックを使わないと型システムが不健全になり、プログラムの最適化で使いたい基盤が不十分になってしまいます（以下の記事では、Pythonで同様の影響がどんなふうに起きているかが詳しく解説されています）。

参考: Compiling typed Python | Max Bernstein

Rubyのような動的言語のコンパイラを効果的に構築するには、コンパイラで正確な型情報が必要となります。つまり、コンパイラの設計者はこれらの情報を自力で手に入れて、型を自分でトラッキングしなければならないということです。

本記事では、Rubyの極めて小さいサブセットに対して、手続き間の型分析（interprocedual type analysis）を示します。こうした分析手法は、十分高度なコンパイラを用いたプログラム最適化で利用可能です。これはShopifyが取り組んでいるものではありませんが、興味深い内容なので、記事と分析結果をここで共有します。

ご注意いただきたいのですが、ここでいう分析は、よく引き合いに出される「型推論エンジン」や「型チェッカー」のことではありません。この型分析は、Hindley-Milner型システム（過去の著作も参照）や類似の制約ベース型システムと異なり、関数間にまたがるデータフローをトラッキングします。

この分析によって、shoutの呼び出し元をすべて特定して、すべての引数のto_sがStringを返すことを判定することが可能になり、そこから戻り値型がStringであると結論付けられる可能性が生じます。しかも、すべては型アノテーションが行われていないプログラムで行われます。

本記事では、この冒頭セクションの次に、一般的なRubyプログラムより丸かっこ()を多用するコード例を示します（ここで書いているミニRubyパーサーでは、丸かっこ()なしの呼び出しをサポートしていません）。

🔗 静的解析

最初は静的解析を見ていきましょう。いくつかの例を見てから、コードとベンチマークに進むことにします。

以下のプログラムが返す型は何だかおわかりですか？

1

はい、この型はInteger[1]ですね。単なるInteger型ではなく、分析時に利用できる正確な値に関する追加情報も持たせてあり、この情報が後で役に立ちます。

では以下の変数の場合はどうでしょう。変数aの型は？

a = 1

少なくともここまでは、別にひっかけ問題ではありません。これも Integer[1]です。しかし以下のように変数を2回割り当てたらどうなるでしょうか？

a = 1
a = "hello"

おっ、今度は複雑になってきましたね。
このプログラムを、実行「時間」をベースに2つのセグメントに論理的に区切るのであれば、変数aは最初Integer[1]で、次にString["hello"]になります。

これは、コードを分析するときに何らかの「時間」ステートという概念を持ち込まなければならなくなるということなので、あまり嬉しくありません。

そうする代わりに、入力コードを以下のような感じに書き換えれば、ずっと良くなるでしょう。

a0 = 1
a1 = "hello"

今度は2つの変数に異なる名前が与えられているので、時刻に影響されることなく2つの変数を簡単に区別できます。ここで登場しているのが静的単一代入（SSA: static single assignment）です。

入力プログラムをSSAに自動変換すると、その分多少複雑にはなるものの、すべての変数が単一かつイミュータブルな型であることが保証されます。私たちが他の形式の中間表現（IR: intermediate representation）ではなくSSAを用いて分析しているのは、これが理由です。本記事の残りの部分では、SSAが使われていることが前提となります。

分析を続けましょう。

以下のプログラムの変数は、それぞれどんな型になりますか？

a = 1
b = 2
c = a + b

aとbはどちらも定数なので、a+bを折りたたんで定数3にしても大丈夫でしょうか？大丈夫かもしれませんし、大丈夫でないかもしれません。

Rubyでは、「誰かがIntegerクラスにパッチを当てていないか」「他にも何か変なことをやってないか」というグローバルな知識がない限り、これを断定できません。

しかし本記事においては、私たちが「既存のクラスの意味を再定義することが不可能な世界（既に申し上げたように、ここで見ている言語はRubyと構文は似ていても意味論は異なります）」かつ「実行時に新しいクラスを追加することが不可能な世界（これは閉じた世界の仮説と呼ばれます）」に住んでいるということにしておきましょう。

この場合、定数を折りたたむのは絶対的に可能になります。すなわち、cの型はInteger[3]になります。

もっとややこしくしてみましょう。

if condition
  a = 3
else
  a = 4
end

個別の変数への割り当ては1回限りであると述べましたが、SSAはそうしたプログラムをファイ（Φ）ノードで表現できます。
ファイノードは一種の特殊な疑似命令で、データが複数の場所からやってくる場合にデータフローをトラッキングします。

ここでは、SSAがifの次にファイノードを1つ配置して、名前の異なる2つの変数を3番目の変数にマージします。

if condition
  a0 = 3
else
  a1 = 4
end
a2 = phi(a0, a1)

これは、以下のようにif式の戻り値を利用する場合にも同じことが行われます。

a = if condition
      3
    else
      4
    end

phi関数は、複数の入力値を1つにマージするために存在します。

私たちの分析では、ファイノードは入力の型の和集合（union）を算出する以外のことは何も行いません。これを行っている理由は、ここでは型を「その型が表す可能性のあるすべての値の集合」として扱っているためです。
たとえば、Integer[3]は{3}という集合ですが、Integerは{..., -2, -1, 0, 1, 2, ...}のような、メモリに載せきれない無限集合です。

これによって、a（a2）の型は、Integer[3 or 4]のような感じの型になりますが、前述したように、この集合は無制限に膨れ上がる可能性があります。これをまともなメモリ使用量に収め、まともな時間内に分析を完了するには、集合のサイズに制限を加えなければなりません。

ここで、有限高さ束（finite-height lattice）という概念が登場します。おっと、どうかページを閉じないでください！怖くありませんから。

ここでは束（lattice: そく）を、「集合（set）をもう少しだけ構造化したもの」という程度の意味で使っています²。集合をひたすら拡大して拡大して拡大しまくるunion（和集合）操作ではなく、集合の各レベルに対して限定的な個数のエントリを与え、その個数を超えると「限定を弱めた」次のレベルにオーバーフローします。

以下は、型の束（type lattice）の部分集合を図で表したものです。

私たちのプログラム分析では、束のあらゆる要素は必ずEmpty（=到達不能を意味する）から出発して、状態遷移の矢印に沿って要素が段階的に追加されます。ある整数の定数が1個存在する場合、Integer[N]というステートになります。これとは「別の」整数も存在する場合、情報の一部を失う形でIntegerというステートに移行しなければならなくなります。情報をこのような形で失うことは、精度と分析時間のトレードオフとなります。

話を先ほどの例に戻すと、変数a（Integer[3]とInteger[4]をマージしたもの）は、この束の上でInteger型に対応付けられることになります。

もっと複雑な例を見てみましょう。
たとえば、以下のようにおそらく条件がインライン定数になっているおかげで、条件がtrueになっていることが分析時に何らかの方法で判明したとします。

a = if true
      3
    else
      4
    end

世の中にある分析の多くは、このプログラムを「aに対して異なる値の入力が2つ存在しているのだから、aの型は引き続きIntegerである」と愚直に結論付けます。しかし実際には、このプログラムがelse分岐を決して通らないことは人間が見ても明らかです。分析方法によってはelse分岐のチェックを削除して無駄を減らすことは可能ですが、その場合はZadeckによる優れた業績である『Sparse Conditional Constant Propagation（SCCP: 疎な条件分岐を考慮した定数伝播）』を活用することになります。

🔗 「疎な条件分岐を考慮した定数伝播」とは

SCCPは、世の中にある多くの抽象解釈ベースの分析と異なり、ワークリスト（worklist）ベースの制御フローグラフ（GFG: control-flow graph）探索で型情報を利用します。
この方法では、分岐命令の条件が定数であることが（他の情報によって）わかっていれば、条件文のどちらの分岐も探索しません。その代わり、実効性のある分岐だけをワークリストにプッシュします。

ここではSSA（制御フローグラフ）内で作業しているので、制御フローを処理の粒度の単位として基本ブロックに分割します。分割された基本ブロックは命令のチャンクであり、末尾の命令だけが制御フローとして許可されます。

fn sctp(prog: &Program) -> AnalysisResult {
    // ...
    while block_worklist.len() > 0 || insn_worklist.len() > 0 {
        // 命令ワークリストから命令を1個読み出す
        while let Some(insn_id) = insn_worklist.pop_front() {
            let Insn { op, block_id, .. } = &prog.insns[insn_id.0];
            if let Op::IfTrue { val, then_block, else_block } = op {
                // 分岐が実行されないことを静的に把握している場合は
                // 分析しない
                match type_of(val) {
                    // Emptyはそのコードが（まだ）到達可能ではないことを表す
                    // 実行時には値を持たない
                    Type::Empty => {},
                    Type::Const(Value::Bool(false)) => block_worklist.push_back(*else_block),
                    Type::Const(Value::Bool(true)) => block_worklist.push_back(*then_block),
                    _ => {
                        block_worklist.push_back(*then_block);
                        block_worklist.push_back(*else_block);
                    }
                }
                continue;
            };
        }
        // ...
    }
    // ...
}

これにより、入力オペランドInteger[3]だけを認識するファイノードが生き残り、プログラムの後半での作業精度が向上します。
SCCPのオリジナル論文ではここで止まっていますが（論文にはページ制限があるので）、私たちはもう少し先に進みました。つまり、定数について推論するだけにとどまらず、完全な型の束を使って、手続き間で推論を実行するのです。

もっと複雑なスニペットに進む前に、手続き間分析（interprocedual analysis）が重要な理由を示す小さな例を見ていくことにしましょう。

以下ではdecisionsという関数があり、呼び出し側ではtrueを渡しています。

def decisions(condition)
  if condition
    3
  else
    4
  end
end

decisions(true)

decisions関数だけに注目して他を見なければ、この戻り値型はIntegerであると考えるでしょう。
しかし、すべての呼び出し側のフローから得られる情報をこの関数に渡せば、すべての（ここでは1個ですが）呼び出し側が関数にtrueを渡していることがわかります。つまり、このifでチェックが必要なのは、分岐の片方だけということになります。

さて、SCCPに詳しい方なら、果たしてこれを手続き同士で実行可能なのだろうかと疑問に思うかもしれません。SCCPは定義上、「どの命令が他のどんな命令を使うか」を事前に知っておく必要があります。
たとえば、出力命令Aについて何か新しい事実がわかった場合、その新しい情報をすべての利用場所に伝搬させなければなりません。
1個の関数の制御フローグラフだけなら、定義も利用場所もひと目でわかるので、大した作業ではありませんが、対象を複数の関数に拡大すると難しくなってきます。
この例では、conditionパラメータを「そこに実際に渡されるすべての実際の引数（ここでは定数ですが）が利用される場所」としてマーキングしなければなりません。

しかし呼び出し側はそのことをどうやって認識すればよいのでしょうか？

🔗 手続き間SCCP

アプリケーションのエントリポイントから始めることにしましょう。これは通常はどこかに置かれているmain関数で、そこではオブジェクトをアロケーションしたり他の関数をいくつか呼び出したりします。呼び出された関数は、さらに別の関数を呼び出し...という具合に、アプリケーションが終了するまで繰り返されます。

このような呼び出しと制御の戻りはグラフを形成しますが、このグラフを静的に把握することはできません。つまり、分析を開始した直後にはどんなグラフになるかは知りようがないということです。代わりに、呼び出しの端点を見つけるたびに段階的にグラフを構築する必要があります。

以下のコードスニペットでは、分析をエントリポイント（ここではmain関数）から開始することになります。
このスニペットではmainからfooを直接呼び出していることがわかります。そこで、「fooはmainによって呼び出されている」「しかも単にmainによって呼び出されているのではなく、main内部の特定の呼び出し元によって呼び出されている」とマーキングします。
次に、bar関数の開始部分（エントリ基本ブロック）をブロックワークリストにエンキューします。

def bar(a, b)
  a + b
end

def foo()
  bar(1, 2) + bar(3, 4)
end

def main()
  foo()
end

この分析は、どこかの時点でfooのエントリ基本ブロックをワークリストからポップしてから、fooを分析します。
barへの直接呼び出しが行われるたびに、呼び出しエッジ（call edge）が作成されます。さらに、bar関数には引数も渡しているので、1と3をパラメータaに紐づけ、2と4をパラメータbに紐づけます。それからbarのエントリブロックをエンキューします。

この時点で、Integer[1]とInteger[3]がパラメータaにマージされます（パラメータbでも同様のマージが行われます）。これは一種の手続き間ファイノードに似ているので、私たちの型束に対して同じunion操作を実行しなければなりません。

つまり、残念ながらbarへのどちらの呼び出しでもa+bを畳むことはできませんが、Integer+Integer=Integerであることはわかっているので、戻り値型は引き続きIntegerになります。

さて、ここでbarへの3つ目の呼び出しで仮にStringが渡されたとすると、すべての呼び出し側で結果が失われることになります。
どのパラメータもClassUnion[String, Integer]となり、さらに困ったことに関数の結果がAny型になってしまいます。しかも、個別の呼び出し側を別々に保持していないので、ClassUnion[String, Integer]という結果すら得られません。このため、分析の観点からは、既知の型を持たないString+Integerを調べることになる可能性があります（実際、例外などが発生する可能性もあります）。

しかし、個別の呼び出し側を別々に保持していたとしたらどうでしょうか？

🔗 感度

この種のものを、一般に「XX-感度（-sensitivity）」と呼びます。XXは分析を分割するときの戦略によって異なります。感度の1つの例は「呼び出し側感度（call-site sensitivity）」です。

特に、現在の分析を「呼び出し側=1感度」に拡張したい場合があります。この数値（k変数: これを増やすと精度は高くなるが分析が遅くなる）は、分析中にトラッキングしたい「コールフレーム（call frame）」の個数です。これは、to_sやeachのように非常に多用される（=呼び出し元が多くの異なる場所になる可能性が高い）ライブラリ関数に適しています。

呼び出し側=1感度の、まったく代表的でない例として、プログラム全体が（1 + 2 + 3 + 4 = 10として）完全にInteger[10]に定数に折りたためる場合が挙げられるでしょう。素晴らしい！しかし分析作業を重複実行する必要があるため、分析は遅くなります。
この手順を大まかに追ってみましょう。

現状の呼び出し側感度なし（呼び出し側=0感度）の場合:

• 引数に1と2が渡されるbar呼び出しをチェック
• barのパラメータをInteger[1]およびInteger[2]とマーキング
• barによる追加の左オペランドと右オペランドが定数のノードであることをチェック
• barによる追加がInteger[3]になることをマーキング
• barがInteger[3]を返すことをマーキング
• bar(1, 2)の結果をInteger[3]とマーキング

• 引数に3と4が渡されるbar呼び出しをチェック

• barのパラメータをIntegerおよびIntegerとマーキング（unionする必要がある）
• barの追加の結果をIntegerとマーキング（引数は定数ではない）
• barが返す結果をIntegerとマーキング
• foo独自の追加ではオペランドがIntegerとIntegerであることをチェック
• fooの追加の結果がIntegerを返すことをマーキング

呼び出し側=1感度の場合:

• 関数fooからbar呼び出しで引数に1と2が渡されることをチェック
• fooからの呼び出しコンテキストを新たに作成する
• foo0->barパラメータをInteger[1]およびInteger[2]とマーキング
• foo0->barによる追加の左オペランドと右オペランドが定数のノードであることをチェック
• foo0->barによる追加がInteger[3]になることをマーキング
• foo0->barがInteger[3]を返すことをマーキング
• bar(1, 2)の結果をInteger[3]とマーキング

• 引数に3と4が渡されるbar呼び出しをチェック

• barからの呼び出しコンテキストを新たに作成する
• foo1->barパラメータをInteger[3]およびInteger[4]とマーキング
• foo1->barによる追加がInteger[7]になることをマーキング
• foo1->barがInteger[7]を返すことをマーキング
• foo独自の追加ではオペランドがInteger[3]とInteger[4]であることをチェック
• fooの追加の結果がInteger[10]を返すことをマーキング

呼び出し入力と戻り値をマージして束を上に移動するのではなく、呼び出し側ごとにbarを1回ずつ分析する必要があることがわかります。これによって分析が遅くなります。

この他に、「コンテキスト感度（context sensitivity）」というものもあります。これは、呼び出しの分割を、プログラム内の場所に基づくのではなく、特定の呼び出し側について算出されたプロパティに基づいて行うものです。これは、「引数型のタプル」「定数値をすべて削除した引数型のタプル」または「まったく別の何か」である可能性があります。理想としては、呼び出し側がさまざまな多くの場所にわたっていても生成や比較を高速に行えるはずです。

感度には他にも「オブジェクト感度（object sensitivity）」や「フィールド感度（field sensitivity）」といったものがありますが、これらについては何も実装していないので、読者がここから文献をたどるための手がかりとして述べておくにとどめます。

本来のお題である手続き間SCCPの話に戻って、次はさらに厄介な要素であるオブジェクトを追加してみましょう。

🔗 オブジェクトとメソッド探索

Rubyが扱うのは整数や文字列だけではありません。
特殊なケースである大規模なオブジェクトシステムのオブジェクトは、さまざまなインスタンス変数やメソッドを抱えていたり、ユーザー定義のクラスのインスタンスであったりします。

class Point
  attr_accessor :x
  attr_accessor :y

  def initialize(x, y)
    @x = x
    @y = y
  end
end

p = Point.new(3, 4)
puts(p.x, p.y)

つまり私たちの静的分析では、あらゆるクラスを1つ残らずトラッキングしなければならなくなります。さもないと、「変数pの型は？」といった問いに正確に答えることも難しくなります。

pの型がわかるのはもちろん嬉しいことですが（いくつかのis_a?はSCCPで折り畳めるでしょう）、オブジェクトのインスタンス変数の型についてもトラッキングできれば、「p.xの型は？」といった問いにも答えられるようになるので、さらに便利です。

この論文（PDF）によれば、そうした情報を保存する方法について少なくとも2つの考え方があります。

1つは、論文で「フィールドベース（field-based）」と呼ばれているもので、フィールド型の名前に基づいてストレージを統合します。したがって、この場合、任意のフィールドxへのすべての潜在的な書き込みを同じバケットに分類して、unionでまとめられる可能性があります。

もう1つは、論文で「フィールド依存（field-sensitive）」と呼んでいる方法で、フィールド型のストレージをレシーバ（フィールドを保持するオブジェクト）クラスに基づいて統合します。この場合、p.xへの書き込みと読み取りで、プログラムの特定の位置におけるpの可能なすべての型が区別されます。

私たちの静的分析では後者のアプローチを選択し、フィールド依存にしました。

fn sctp(prog: &Program) -> AnalysisResult {
    // ...
    while block_worklist.len() > 0 || insn_worklist.len() > 0 {
        // 命令ワークリストから命令を1個読み込む
        while let Some(insn_id) = insn_worklist.pop_front() {
            let Insn { op, block_id, .. } = &prog.insns[insn_id.0];
            // （略）
            match op {
                Op::GetIvar { self_val, name } => {
                    let result = match type_of(self_val) {
                        Type::Object(classes) => {
                            // （略）
                            classes.iter().fold(Type::Empty, |acc, class_id| union(&acc, &ivar_types[class_id][name]))
                        }
                        ty => panic!("getivar on non-Object type {ty:?}"),
                    };
                    result
                }
            }
        }
    }
}

つまり、ここでは以下の2つを行う必要があります。

• 1: 各クラスのインスタンス変数（ivar）のフィールド型をトラッキングし続ける必要がある
• 2: 次に、指定のインスタンス変数を読み込むときに、レシーバのクラスになりえるすべてのクラスのフィールド型をunionで結合する必要がある

残念ながら、これによって複雑な「利用（use）」関係も作成されてしまいます。つまり、どのGetIvar命令も、それに影響を与える可能性があるすべてのSetIvar命令の「利用」になるということです。すなわち、Xというフィールド名を持つ何らかのクラスTについてT.Xを行うSetIvar命令がある場合は、そのようなクラスから読み出す可能性のあるGetIvar命令をすべて見つけて再分析しなければならなくなります（さらに、この情報を通常通り他の「利用」にも伝搬させる必要も生じます）。

こうしたunionやフロー変更やグラフ探索は、どれも時間のかかりそうな処理です。データ構造の効率が相当高いとしても、反復処理は膨大なものになります。
実際どのぐらい遅くなるのでしょうか？この疑問に答えるため、一種の「拷問テスト」を構築して、いくつかのワーストケースについて人工的なベンチマークを作成しました。

🔗 拷問テストを生成してどのぐらいスケールするかをテストする

コンパイラ設計のあらゆる点に関する大きな問題の1つは、大規模かつ代表的なベンチマークを見つけるのが難しいことです。
これにはさまざまな理由があります。巨大なプログラムほど依存関係も増えてくるので、その分配布やインストールやメンテナンスも難しくなる傾向がありますし、ソフトウェアによっては（オープンソースでない）クローズドなものや著作権で保護されているものもあります。私たちが作業しているミニ言語は実験用なので、その言語で書かれたプログラムは実世界には存在しません。ではどうすればよいでしょうか？

第1の問いは「何を測定するか」です。
この分析を実装してテストするときの主な懸念点の1つは、実行時間についてどの程度パフォーマンスが良好であるかを事前に知っておくことでした。巨大で複雑なプログラムに対してこの分析が通用することを確信できるようにしたいと思います。

YJITでの経験では、Shopifyのproduction環境のコードで実行した場合、YJITが9000個以上のメソッドをコンパイルすることがわかっています。YJITがコンパイルする「ホット（=頻繁に実行される）」メソッドが9000個ある場合、プログラム全体ではその10倍以上になると推測できそうなので、仮に100,000個のメソッドがあるとします。私たちが実験に使うミニ言語にはそこまで多くのメソッドはありませんが、同程度の規模で何らかのプログラムを合成することはできそうです。

私たちの分析が、大規模かつ本質的に困難になるように設計した「拷問テスト」に通用するのであれば、「現実の」プログラムにも対応できるはずだという十分な確信を得られると考えています。

合成テストプログラムを生成するために、互いに呼び出される関数同士の呼び出しグラフを生成する必要があります。この呼び出しグラフは、私たちの型分析が機能するうえで厳密には必ずしも必要ではありませんが、生成するプログラムが無限に再帰することなく常に終了するようにしたいのです。

これについては、有向非巡回グラフ（DAG: Directed Acyclic Graph）を直接生成するコード片を書けば済むので、実現はさほど難しくありませんでした（本記事末尾に記載したloupeリポジトリのrandom_dagを参照: この関数が生成する有向グラフには単一のrootノードがあり、その下にはノード間で循環が生じないよう相互接続された多数の子ノードがあります）。

最初の拷問テスト（gen_torture_testを参照）では、互いに呼び出しw行う200,000個の関数のグラフを生成しました。
一部の関数にはリーフ（leaf: 葉）ノードがあり、定数の整数かnilを返すことでどこからも呼び出されないことを表します。
呼び出しが行われる関数では子の戻り値を合計し、子がnilを返す場合は合計に0を追加します。つまり、リーフでない関数には、型情報に依存する動的な分岐が含まれることになります。

2つ目の拷問テスト（gen_torture_test_2を参照）では、呼び出し側がポリモーフィックやメガモーフィックの場合にどの程度分析がうまくいくかを評価したいと考えました（ポリモーフィックな呼び出し側とは、複数のクラスを処理する必要がある関数呼び出しであり、メガモーフィックな呼び出し側とは、5〜10個またはそれ以上の多数のクラスを処理する必要がある関数呼び出しのことです）。

最初に合成クラスを大量に生成します。生成するクラスの個数を5000にした理由は、現実の大規模プログラムに含まれる可能性のあるクラスの個数がそのぐらいになりそうだったからです。
個別のクラスには10個のインスタンス変数と10個のメソッドを含めるようにし、どれも同じ名前にしました（コードを生成しやすくするため）。

ポリモーフィックな呼び出し側やメガモーフィックな呼び出し側を生成するときには、クラスごとにインスタンスを生成してから、インスタンスのセットからクラスインスタンスをランダムな個数サンプリングして取り出しました。

また、ランダムな個数のクラスをサンプリングするためにパレート分布を利用しました。現実のプログラムの一般的な構造はこのパレート分布に最も近くなると私たちは信じています。つまり、呼び出し側のほとんどは1個のクラスしか扱わないモノモーフィックなもので、ごく少数の呼び出し側だけが著しくメガモーフィックになるということです。

私たちが生成した200個のランダムなDAGには、それぞれ750個のノードがあり、それぞれが個別のDAGのrootノードを呼び出すときにランダムな個数のクラスインスタンスを扱います。
次に、個別のDAGは、rootノードから受け取ったオブジェクトをすべての子ノードに渡します。これで、多数のポリモーフィック呼び出し側と、メガモーフィック呼び出し側が作成されます。
合成で得たプログラムの中には、最大144個の異なるクラスを受け取る呼び出し側も含まれています。

2回目の拷問テストにおける各DAGの構造は、1回目のものと似ていますが、各関数がパラメーターとして受け取ったオブジェクトのランダムに選択されたメソッドを呼び出し、それをDAG内の子関数として呼び出すという点が異なります。

利便性を考慮してメソッド名を常に各クラスで同じにしておいたので、構造上すべてのクラスで定義されていることがわかっているメソッドをランダムに選択するのは簡単です。
これにより、ポリモーフィックな呼び出し側をより多く作成できるようになりました。これがストレステストの目的です。各クラスのメソッドはすべてリーフメソッドであり、「nil」「ランダムな整数」「ランダムに選択したインスタンス変数」のいずれかを返せます。

🔗 この分析をどうやって実際にスケールさせるか

拷問テストジェネレータを用いて、クラスありのプログラムとクラスなしのプログラムをそれぞれ生成しました。

クラスありのプログラムには、175,000個の到達可能な関数（生成された合計205,000個のうち）と、300万個の命令、メガモーフィック なメソッド探索（最大144クラス）が含まれており。シングルコアで2.5秒で分析を完了します。

クラスなしのプログラムには200,000個の関数が含まれ、シングルコアで1.3秒で分析を完了します。

さて、この結果の絶対値にはあまり意味がありません（ハードウェアやコードベースなどによって大きく変わります）。しかし相対的に見れば、この種の分析は扱いやすい部類になるでしょう。分析に「数時間」かかることもありませんし、ましては私たちの分析ではこれといった最適化が行われていたわけでもありません。

正直に言うと、私たちはこの分析の実行速度に驚きました。当初は、20,000個のメソッドを60秒以下で分析できるだろうと予想していましたが、その10倍のサイズのプログラムを、私たちの予想をはるかに超える速度で分析できたのです。このことから考えて、人間が書いた大規模プログラムにもこの分析が通用しそうです。

オブジェクト感度を増やしたり、呼び出し側感度のk値を増やしたりすると、かなり遅くなるかもしれません。しかし、私たちの分析がこれほど高速であることから考えて、言語組み込みのメソッドの呼び出し側を選択的に分割・特殊化することで、実行時間を大幅に増やさずに、特定の部分で感度を増やすことは可能そうです。たとえば、Arrayクラスにメソッドが備わっているRubyのような言語であれば、すべてのArrayメソッド呼び出しを分割することで、高度にポリモーフィックな関数について分析の精度を高めることが可能かもしれません。

🔗 まとめ

私たちの、小さくもあり大きくもある静的型分析プロトタイプの記事をお読みいただきありがとうございます。この記事に対応するloupeというコードをGitHubリポジトリで公開していますが、それ以上のものではありません。これはあくまで私たちが構築した実験であり、より大きなプロジェクトにつながるものでもなければ、外部の人による貢献が期待されるツールでもありません。

プログラム分析の広大な世界についてさらに詳しく知りたい場合は、「制御フロー分析（CFA: control-flow analysis）」や「ポイントツー分析（point-to analysis）」などの用語を検索することをおすすめします。Ondřej Lhotákによる優れた講義のスライド（PDF）へのリンクを以下に貼っておきます。

 

関連記事

Ruby 3.4に導入される次世代の帯域外ガベージコレクション（翻訳）

Ruby LSPアドオンシステムの概要（翻訳）

YJIT: CRuby向けの新しいJITコンパイラを構築する（翻訳）