博士

ロボ子、Javaのデコンパイラの話じゃ。既存のCFRとかVineflowerってやつ、どうもイマイチらしいのじゃ。

ロボ子

そうなのですか、博士。具体的に何が問題なのでしょう？

博士

制御フロー抽出戦略が不十分らしいのじゃ。`if`文とか`while`文をうまく扱えないみたい。

ロボ子

ふむふむ。既存のアプローチは、バイトコードを直接構造にマッチングさせたり、制御フローグラフ（CFG）を構築して解析したりするようですが…。

博士

`javac`コンパイラが最適化しちゃうから、バイトコードのマッチングは難しいのじゃ。CFGも複雑になりがちで、特に`if`文の中に`continue`文があるときとか、お手上げ状態になるらしい。

ロボ子

なるほど。CFGの解析は再帰的になりやすく、処理が遅くなるという問題もあるのですね。

博士

そこで新しい手法の登場じゃ！CFGを線形化して、プログラムの順序を保ちつつ、抽象構文木（AST）を構築するらしい。

ロボ子

線形化ですか。具体的にはどのように？

博士

入力プログラムをアトム（分割不能な命令）とか条件付き`goto`文のリストとして扱うのじゃ。で、出力プログラムはアトム、ラベル付きブロック、条件付き`break`や`continue`文のリストになる。

ロボ子

ブロックという概念が出てきましたね。文を含み、`break`や`continue`で制御される構造のことですね。

博士

そうそう。あと、ギャップっていうのは、入力プログラム内の連続する文の間の空間のことじゃ。アローは、そのギャップ間のジャンプを示す矢印。

ロボ子

アローセットでプログラム内のジャンプ構造を表現するのですね。Ramshawの手法というのも出てきましたが…。

博士

アローが木構造を形成する場合、ブロックに直接変換できるのじゃ。アローのテールを拡張しても、ジャンプの実装可能性は損なわれないらしい。

ロボ子

`continue`や`break`文を考慮して、アローの競合を解決したり、外側からブロックを構築して不要なアローを無視したりする改善が加えられているのですね。

博士

アルゴリズムとしては、範囲[l; r]内でアローが交差しないギャップを検索して分割、再帰するのじゃ。ブロックを作成して、範囲内の`continue`や`break`文を処理する。

ロボ子

フォワードアローのみを考慮してギャップを検索し、ディスパッチャを導入してバックワードアローを処理する、と。

博士

そう！ディスパッチャは、複雑な制御フローを処理するためのフォールバックじゃ。

ロボ子

実装には、セグメント木や区間木が使われているのですね。アローの追加、削除、ギャップの検索を高速化したり、バックワードアローの検索を効率化したりするために。

博士

結論としては、この手法で準線形時間で高品質な制御フロー復元アルゴリズムを実装できるってことじゃ！バイトコードベースの言語に適用できるけど、ネイティブコードにはコードの並び替えが必要らしい。

ロボ子

なるほど、勉強になりました！

博士

ところでロボ子、このアルゴリズム、まるで迷路みたいじゃな。出口を探すのが大変じゃけど、見つけた時の達成感は格別じゃ！