Idempotent Slices with Applications to Code-Size Reduction

この論文は、一般的な制御フローグラフに適用可能な健全かつ効率的な「冪等バックスライス」の定式化と抽出アルゴリズムを提案し、これを用いて非連続な命令シーケンスをマージする疎なコードサイズ削減最適化を実現し、LLVM テストスイートにおいて最大 7.24% のコードサイズ削減を達成したことを報告しています。

要約

1. 問題：本屋（プログラム）が広すぎて、同じ本が何冊も並んでいる

コンピュータのプログラム（特に「LLVM」という中間言語で書かれたもの）は、巨大な本屋のようなものです。
開発者が書いたコードは、その本屋の棚に並んでいる本です。

しかし、この本屋には**「同じ内容の本が、あちこちに何冊も置かれている」**という問題があります。

• 「A さんの誕生日を計算する本」が、料理のレシピ本の中に 1 冊。
• 同じ「A さんの誕生日を計算する本」が、ゲームのスコア計算本の中に 1 冊。
• さらに、別のアプリの「A さんの誕生日を計算する本」が 1 冊。

これらは中身が全く同じなのに、棚（メモリ）を無駄に占有しています。これを「コードの重複」と呼びます。

2. 従来の方法：「連続した文章」だけをコピーして整理する

これまでも、この「同じ本」を 1 冊にまとめて、他の場所には「中身はこれです（参照先）」というメモを残す技術がありました。
しかし、従来の技術には**「連続している文章しかまとめられない」**という大きな弱点がありました。

• 例： 料理のレシピ本の中で、「卵を割る」→「混ぜる」→「焼く」という連続した手順が同じなら、まとめて 1 冊にできます。
• しかし： 「卵を割る」→（他の料理の説明が入る）→「混ぜる」→（また他の説明）→「焼く」というように、途中で他の説明が挟まっている場合、従来の技術は「これはバラバラだからまとめられない」と判断してしまいました。

3. 新しい発見：「同じ意味の塊（スライス）」を見つける魔法

この論文の著者たちは、**「連続していなくても、同じ意味を持つ『塊』を見つけ出してまとめられる」**新しい魔法（アルゴリズム）を発見しました。

彼らはこれを**「冪等（べきとう）スライス」**と呼んでいます。
これを「おまけの整理」に例えてみましょう。

• 冪等（Idempotent）とは？
  「同じことを何度繰り返しても、結果が変わらないこと」です。
  • 例：「100 円玉を 1 回渡す」も「2 回渡す」も、受け取った人は「100 円」を受け取ります（結果が変わらない）。
  • 逆に、「冷蔵庫のドアを開ける」は、1 回開けるのと 2 回開けるのでは、中身が変わるかもしれません（結果が変わる）。

この論文の魔法は、**「何度繰り返しても結果が変わらない、安全な計算の塊」**だけを抜き出して、新しい「共通の本（関数）」としてまとめます。

4. 具体的な仕組み：「GSA」という新しい地図

この魔法を成功させるために、著者たちはプログラムを**「GSA（ゲーテッド・スタティック・シングル・アサインメント）」**という新しい形式に変換しました。

• 従来の地図（SSA）： 「ここからここへ行く」という道順しか書いていない。
• 新しい地図（GSA）： 「ここからここへ行くのは、もし『晴れ』なら A 道、『雨』なら B 道」という、**「条件（ゲート）」**まで詳しく書いてある地図です。

この詳しい地図があるおかげで、従来の方法では「バラバラだからまとめられない」と思っていた部分でも、「あ、この『卵を割る』と『混ぜる』は、実は同じ条件で動いているから、まとめても安全だ！」と判断できるようになりました。

5. 結果：本屋が小さくなり、本棚が整理された

この新しい技術（SBCR）を使って、2000 以上のプログラムをテストしました。

• コードサイズ： 特定のプログラムでは、最大で約 12% 減しました。
  • 従来の技術（IROutliner や FMSA）では減らなかった部分も、この技術なら減らせたケースがあります。
  • 逆に、従来の技術が減らせた部分も、この技術では減らせない場合があり、**「お互いに得意分野が違う」**ことがわかりました。
• 実行速度： 本屋が小さくなったので、本を探す速度（実行速度）はほとんど変わらず、むしろ「同じ本が近所に集まった」ことで、少し速くなるケースもありました。
• 処理時間： 整理作業自体は少し時間がかかりますが、全体として実用的な範囲内です。

まとめ：なぜこれがすごいのか？

この論文が提案するのは、**「プログラムの『おまけ』を、連続していなくても、意味が同じなら大胆にまとめていい」**という新しい考え方です。

• 従来の考え： 「連続した文章しかまとめられない」。
• 新しい考え： 「条件付きで、飛び飛びの文章でも、同じ意味ならまとめていい」。

これにより、コンピュータのメモリ（本棚）を節約し、プログラムをより軽量化できます。特に、複雑な条件分岐（「もし A なら B、そうでなければ C」など）が絡み合っている現代のプログラムにおいて、この「飛び飛びの整理術」は非常に有効であることが証明されました。

つまり、**「プログラムの世界でも、同じ意味の『おまけ』を、形が違ってもまとめて整理すれば、世界はもっとシンプルになる」**という、とてもシンプルで強力なアイデアが、この論文の核心です。

技術概要

1. 問題定義 (The Problem)

• 既存手法の限界:
  • 従来のコードサイズ削減技術（関数マージや IR アウトラインナーなど）は、主に「連続した命令列」や「特定の構造（ハンモック構造など）」を持つコードに依存しています。
  • 既存の冪等スライス抽出アルゴリズム（Guimarães and Pereira [10]）は、SSA（Static Single Assignment）形式の特定の制約（CSSA 性質）を満たすプログラムや、単純な制御フローグラフ（CFG）に対しては機能しますが、より一般的な CFG や、$\phi$-関数のライブ範囲が重複する複雑なケースでは、必要な制御依存関係を正しく特定できず、スライスを抽出できない、あるいは不完全なスライスを生成する問題がありました。
• 課題:
  • 制御フローグラフ内の非連続な命令列や、ループ内・関数横断的な冗長性を安全に特定し、コードサイズを削減できる新しい最適化手法の必要性。
  • 冪等性（同じ入力に対して常に同じ出力を返し、副作用を持たない）を保証しつつ、スライスを独立した関数として抽出する確実なアルゴリズムの欠如。

2. 手法とアプローチ (Methodology)

著者らは、Gated Static Single Assignment (GSA) 形式を活用することで、上記の限界を克服するアルゴリズムを提案しました。

2.1 冪等スライスの定義

• 冪等実行 (Idempotent Execution): 入力変数へのバインディングが同じであれば、複数回実行しても結果が同一であり、プログラムの観測可能な状態（メモリ書き込みや例外発生など）を変更しない命令列。
• 冪等後方スライス: 特定の基準変数（slice criterion）に対して、その値を計算するすべての命令を含む「単一エントリー領域（Single-Entry Region）」であり、かつ冪等性を満たす部分プログラム。
  • 従来の「密スライス（Dense Slice）」とは異なり、スライスはループ内にとどまり、ループの反復ごとに異なる値を計算しないように制限されます。

2.2 GSA 形式への変換

• 従来の SSA 形式では、$\phi$-関数が制御フローの分岐情報を隠蔽しているため、制御依存関係の特定が困難でした。
• 著者らは、Tu and Padua [22] のアルゴリズムに基づき、SSA を GSA 形式 に変換します。
  • $\phi$-関数を、制御条件（述語）を明示的に伴う $\gamma$-関数（分岐点）、$\mu$-関数（ループヘッダ）、$\eta$-関数（値のゲート）に置き換えます。
  • これにより、データ依存関係と制御依存関係が命令文の構文上に明示的に表現され、スライス抽出の精度が向上します。

2.3 スライス抽出アルゴリズム

1. 依存グラフの構築: GSA 形式に変換されたプログラムに対し、基準変数から逆方向に依存グラフを走査します。
2. 停止条件:
   • 関数境界: 関数パラメータに到達した時点で停止。
   • ループ境界: 基準変数が定義されているループの深さより浅いレベル（または同じ深さの$\mu$-関数）に到達した時点で停止。これにより、スライスがループ外に漏れるのを防ぎます。
3. 領域の特定とアウトライニング: 抽出された変数を含む基本ブロックを特定し、それらを独立した関数として抽出（Outlining）します。
   • 制御フローの再構築には「転置（Transposition）」と「引力（Attraction）」のルールを用い、スライス領域が単一エントリー関数となるように CFG を修正します。

2.4 コードサイズ削減 (SBCR)

• 抽出されたスライスを関数化し、同構（isomorphic）なスライスを特定してマージします。
• コストモデル: 命令数（$I$）、パラメータ数（$P$）、出現回数（$C$）に基づき、アウトライニングとマージがコードサイズ削減に寄与するかを判断します（例：$I \le 20, P \le 1, C \ge 10$）。
• 利益がない場合は、抽出された関数を削除し、元のコードに戻すのではなく、最適化が適用されない状態を維持します。

3. 主要な貢献 (Key Contributions)

1. 冪等後方スライスの形式的定義とアルゴリズム:
   • GSA 形式を用いた、制御フローグラフの任意の構造（ハンモック構造の制限なし）に対応する、健全（Sound）かつ効率的なスライス抽出アルゴリズムを提案しました。
   • 既存手法が失敗するケース（$\phi$-関数の重複や複雑な制御フロー）を正しく処理できます。
2. スライスベースのコードサイズ削減 (SBCR) の実装:
   • LLVM コンパイラ（バージョン 17）に実装し、非連続な命令列や同一関数内の重複コードをマージする最適化パスを導入しました。
   • 既存の技術（FMSA, LLVM IROutliner）とは補完的な関係にあり、これらを組み合わせることでさらなる削減が可能であることを示しました。
3. 大規模な実証評価:
   • LLVM テストスイート（2,007 個のプログラム）全体を対象とした包括的な評価を行いました。

4. 実験結果 (Results)

• コードサイズ削減:
  • 特定のベンチマーク（特に -Os オプションで最適化されたもの）において、最大 -12.49% の .text セクションサイズ削減を達成しました（例：AMGmk）。
  • 削減効果があった 29 のプログラムにおいて、幾何平均で -7.24% の削減を実現しました。
  • 既存手法（FMSA や IROutliner）単体では削減できなかったケースや、逆にサイズが増加したケースでも、SBCR は削減に成功しました。
• 実行時間への影響:
  • 全体的な実行時間の統計的有意な変化は見られませんでした（幾何平均で +0.06%）。
  • 一部では命令キャッシュの局所性向上により速度向上が見られましたが、関数呼び出しオーバーヘッドによるわずかな遅延も観測されました。
• コンパイル時間:
  • 平均してコンパイル時間が約 4.22% 増加しました。これは、依存関係の解析や GSA 変換のコストによるものです。
• スケーラビリティ:
  • 理論的には $O(N^2)$ の計算量ですが、実際の実装ではスライスが小さく、コストモデルを満たす候補が少ないため、プログラムサイズに対して**ほぼ線形（Near-linear）**に動作することが確認されました。

5. 意義と結論 (Significance)

• 新しい冗長性の単位: 従来の「連続した命令列」だけでなく、意味論的に一貫した「冪等スライス」という単位で冗長性を捉えることで、より多様なコードパターン（ループ内や分岐を跨ぐ部分）の削減が可能になりました。
• 既存技術との補完性: SBCR は、シーケンスアライメントによるマージ（FMSA）や、単純な命令列のアウトライニング（IROutliner）とは異なるアプローチであり、これらを組み合わせることで、単独では達成できない大幅なコードサイズ削減を実現できます。
• 実用性: 大規模なテストスイートでの実装と評価を通じて、この手法が実世界のコンパイラパイプラインに統合可能であることが示されました。

総じて、この論文は、GSA 形式を活用した堅牢なスライス抽出アルゴリズムを提案し、それがコードサイズ削減において強力かつ補完的な最適化技術となり得ることを実証した重要な研究です。