サブルーチン推論

Question

コンパイルされたプログラムからサブルーチンを推測するためのアルゴリズム/手法を説明する論文はありますか？言い換えれば、プログラムに複数回表示されるコードブロックを見つけるアルゴリズムはありますか？これらのブロックは、命令を並べ替えて（もちろんプログラムの動作の変更なしで）、一致する可能性が高くなる可能性があります。

このプロセスは、コールを避けるためにコンパイラによって行われるが、バイナリサイズを増やすためにコンパイラによって行われるサブルーチンインラインの反対と見なすことができます。

これは非常に難しい理論的問題であるように思えます。

Answer 1

まあ、それは興味深い問題です。人々は実際にこれに取り組んでいました。簡単な検索でこれら2つを返します：

• キース・D・クーパー、ナサニエル・マッキントッシュ： 組み込みRISCプロセッサの強化コード圧縮, 、PLDI 1999。

• クリストファー・W・フレイザー、ユージン・W・マイヤーズ、アラン・L・ウェント： アセンブリコードの分析と圧縮, 、Sigplan Notices、1984年6月。

しかし、おそらくもっとたくさんあります。使用できます Google Scholar これらの古いものを参照するより最近の論文を見つけるため。

Answer 2

探しているものは「クローン検出器」と呼ばれます。これをソースコードまたはオブジェクトコードで行うことができます。重要なアイデアは、受け入れたい変動性のポイントを決定することです。

あなたはできる 私たちのclonedrについて読んでください ソースファイルの構文ツリーを比較することにより、重複したコードを見つけるクローン検出器、正確な一致とニアミスの一致を見つけます。 1つのソースファイル内ではなく、多くのファイルで行われます。これは「共通のサブエクスペッション」検出のようなものですが、実行可能コードと同様に宣言と機能します。一致が正確でない場合、「サブルーチン」（抽象化）のパラメーターを決定できます。

私の論文をご覧ください 抽象的構文ツリーを使用したクローン検出 アルゴリズムの説明。

Clonedrは、多くの言語でこれを使用して行います 言語プレシーズフロントエンドパーサー.

このサイトでは、Clonedrがどのように機能するかを説明し、Clonedrと他の多くのクローン検出ツールを比較しています。

Clonedrは「指示の並べ替え」を処理しません。 PDGを比較することで複製を見つけるほどスケーラブルではない方法がこれを行うことができます。これらは、マシン命令コードの一致を見つけるのに適しているかもしれないデータフローグラフの比較にかなり近いものです。

Answer 3

たぶんこれは愚かです。しかし、「diff」を考慮してください。基本的にこれの制限付きバージョンを実行します。