サブルーチン推論

Question

コンパイルされたプログラムからサブルーチンを推論するアルゴリズム/テクニックを記述した論文はありますか？つまり、プログラムに複数回現れるコードブロックを見つけるアルゴリズムはありますか？これらのブロックは、（プログラムの振る舞いを変更することなく）並べ替えられた命令を持つことができるため、一致が見つかる可能性が高くなります。

このプロセスは、呼び出しを避けるためにコンパイラによって行われるサブルーチンインライン化とは反対に見えますが、バイナリサイズは大きくなります。

これは非常に難しい理論上の問題です。

Answer 1

これは興味深い問題です。人々は実際にこれに取り組んだ。クイック検索は、これら二つを返します。

• キースD.クーパー、ナサニエル・マッキントッシュ：Enhanced Code Compression for Embedded RISC Processors、PLDI 1999

• クリストファー・W・フレイザー、ユージンW.マイヤーズ、アラン・L.ウェント：Analyzing and Compressing Assembly Code、SIGPLAN通知、1984年6月

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

Answer 2

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

read about our CloneDRクローン検出器は、ソースファイルの構文ツリーを比較し、正確なミスマッチを見つけることによって重複したコードを検出します。 1つのソースファイル内ではなく、多くのファイルで実行されます。これは「共通部分式」検出のようなものですが、宣言や実行可能コードでも機能します。一致が正確でない場合、 "サブルーチン"（抽象化）のパラメータを決定できます。

アルゴリズムの説明については、Clone Detection Using Abstract Syntax treesの論文を参照してください。

CloneDRは、language-precise front end parsersを使用して、多くの言語でこれを行います。

このサイトでは、CloneDRの仕組みを説明し、他のクローン検出ツールと比較しています。

CloneDRは、「命令の並べ替え」を処理しません。 PDGを比較して重複を見つけるスケーラビリティの低いメソッドはこれを行うことができます。これらはデータフローグラフを比較するのに非常に近く、マシン命令コードの一致を見つけるのに適しています。

Answer 3

多分これはダムですが、「diff」と考えてください。これは基本的にこれの制限されたバージョンです。