コンパイルされたプログラムからサブルーチンを推論するためのアルゴリズム/テクニックを説明している論文はありますか? 言い換えれば、プログラムに複数回出現するコードのブロックを見つけるアルゴリズムはありますか? これらのブロックでは、一致を見つける可能性が高くなるように (もちろん、プログラムの動作を変更することなく) 命令を並べ替えることができます。
このプロセスは、呼び出しを回避するためにコンパイラーによって実行されるサブルーチンのインライン化の反対と見なすことができますが、バイナリ サイズは増加します。
これは非常に難しい理論的問題のように私には思えます。
なるほど、興味深い問題です。人々は実際にこれに取り組みました。クイック検索では、次の 2 つが返されます。
キース D. クーパー、ナサニエル マッキントッシュ:組み込み RISC プロセッサの拡張コード圧縮、PLDI 1999。
Christopher W. Fraser、Eugene W. Myers、Alan L. Wendt: Analyzing and Compressing Assembly Code、SIGPLAN Notices、1984 年 6 月。
しかし、おそらくもっとたくさんあります。Google Scholarを使用して、これらの古い論文を参照している最新の論文を見つけることができます。
あなたが探しているのは「クローン検出器」と呼ばれるものです。これは、ソース コードまたはオブジェクト コードで行うことができます。重要なアイデアは、許容する可変性のポイントを決定することです。
ソース ファイルの構文ツリーを比較し、完全一致とニアミス一致を見つけて重複コードを検出する CloneDR クローン検出器について読むことができます。1 つのソース ファイル内だけでなく、多くのファイルにわたって実行されます。これは「共通部分式」の検出に似ていますが、宣言と実行可能コードで機能します。一致が正確でない場合、「サブルーチン」(抽象化) のパラメーターを決定できます。
アルゴリズムの説明については、抽象構文ツリーを使用したクローン検出に関する私の論文を参照してください。
CloneDR は、言語に正確なフロント エンド パーサーを使用して、多くの言語に対してこれを行います。
このサイトでは、CloneDR の仕組みについて説明し、CloneDR を他の多くのクローン検出ツールと比較しています。
CloneDR は「命令の並べ替え」を処理しません。PDG を比較して重複を検出するスケーラビリティの低い方法でこれを行うことができます。これらは、データ フロー グラフの比較に非常に近く、マシン命令コードの一致を見つけるのに適している可能性があります。
たぶんこれはばかげている..しかし、「差分」を考慮してください。基本的にこれの制限付きバージョンを行います。