2025/08/25 11:22 Linear Scan with Lifetime Holes
ロボ子、今日はLifetime Holesの話じゃ。
Lifetime Holes、ですか？初めて聞く言葉です。
Lifetime Holesは、線形スキャンレジスタ割り当てに導入された概念で、プログラムのグラフ構造をより適切に反映させるものなのじゃ。
プログラムのグラフ構造を反映させる、ですか。具体的にはどういうことでしょう？
命令の線形化されたシーケンスが、グラフとして格納されたプログラムのメタデータを格納または使用するための優れたプロキシではないために必要になるのじゃ。
なるほど。線形化されたシーケンスだけでは表現しきれない情報を補完するということですね。
その通り！Virtual RegisterのLifetime Intervalは、そのレジスタが必要なすべての部分をカバーする必要があるけど、その間に使われていない部分、つまりLifetime Holesが存在するのじゃ。
例えば、どのような状況でLifetime Holesが発生するのですか？
コントロールフローダイヤモンドの例がわかりやすいぞ。B1からB3またはB2にジャンプし、B4でマージされるような場合、Virtual Register R0がB1で定義され、B3でのみ使用されると、B2の部分がHoleになるのじゃ。
コントロールフローが分岐と合流を繰り返す場合に、レジスタが使用されない期間が生じるということですね。
そういうことじゃ。WimmerのInterval構築アルゴリズムだと、このHoleを考慮してIntervalを割り当てる必要があるのじゃ。
具体的には、Intervalデータ構造やアルゴリズムにどのような変更が必要になるのでしょうか？
Intervalデータ構造を、単一のRangeではなく、複数のRangeをサポートするように変更するのじゃ。`Range`の配列を使うことで、複数のRangeを扱えるようにするぞ。
`Range`の配列ですか。より柔軟にレジスタの生存期間を表現できるのですね。
そうじゃ。Interval構築アルゴリズムも、Lifetime Holesを考慮するように変更する必要があるぞ。新しいRangeをソートされた順序で`@ranges`配列の先頭に追加したり、既存のRangeとの重複をチェックしてマージしたりするのじゃ。
線形スキャンアルゴリズムにも変更が必要なのですね。
Mössenböck2002のアルゴリズムを参考に、`inactive`という4番目のセットを追加するのじゃ。これは、現在のIntervalの開始位置を含むHolesを持つIntervalを保持するためのものじゃ。
`inactive`セットですか。Holesを持つIntervalを管理することで、より効率的なレジスタ割り当てが可能になるのですね。
その通り！解決関数は変更せずに維持できるし、IntervalはLifetime Holesを持つけど、そのライフタイム全体で1つの場所しか持たないのじゃ。
今後の展望としては、どのようなものがあるのでしょうか？
Interval Splittingを追加することで、関数呼び出しでABI制約をより明確に処理し、スクラッチレジスタの予約への依存をなくすことができるのじゃ。
Interval Splitting、ですか。さらに複雑な最適化も可能になるのですね。
そうじゃな。しかし、レジスタ割り当ての話を聞いていると、昔、飼っていたハムスターに回し車を割り当ててあげたら、全然使ってくれなかったのを思い出すのじゃ。あれは、ハムスターにとってのLifetime Holeだったのかも…。
博士、それは少し違うと思います…。
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。