バイナリ再コンパイラ

バイナリ再コンパイラは、実行可能なバイナリファイルを入力として受け取り、その構造を分析し、変換と最適化を適用し、最適化された新しい実行可能バイナリを出力するコンパイラです。 ^[1]

バイナリ再コンパイルの概念の基礎は、1981年にゲイリー・キルドール^[2]^[3]^[4]^[5]^[6]^[7]^{[8]が最適化}アセンブリコードトランスレータ XLT86を開発したときに確立されました。 ^[4]^[9]^[10]^[11]

参照

バイナリオプティマイザー（バイナリからバイナリ）
バイナリトランスレータ(バイナリからバイナリへ)
デコンパイラ（バイナリからソース）
逆アセンブラ（バイナリからソース）
動的再コンパイラ（バイナリからバイナリへ）
トランスコンパイラ（ソースからソースへ）
Honeywell Liberator ( Honeywell H200上でIBM 1401プログラムを実行)

参考文献

^ Mudge, Trevor; Reinhardt, Steve; Tyson, Gary. 「バイナリ再コンパイルとコンパイラ/アーキテクチャの複合強化研究」umich.edu .ミシガン大学(UM)。 2012-07-23 のオリジナルからアーカイブ。 2012-07-23に取得。
^ Kildall, Gary Arlen (1972 年 5 月)。コンパイル時のグローバル式最適化(博士論文)。米国ワシントン州シアトル:ワシントン大学、コンピュータサイエンスグループ。論文番号 20506、技術レポート番号 72-06-02。
^ Kildall, Gary Arlen (1973-10-01). 「グローバルプログラム最適化への統一アプローチ」(PDF) . Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) . POPL '73. Boston, Massachusetts, USA: 194– 206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID 10219496. 2017-06-29 にオリジナルからアーカイブ(PDF) . 2006-11-20に取得。（[1]）
^ ab Freiberger, Paul (1981-10-19). 「プログラムトランスレータは文字通りに、そして時には文脈に従ってそれを実行します」。InfoWorld - マイクロコンピュータユーザー向けニュース。特別セクション: コンピュータの互換性。第 3 巻、第 22 号。Popular Computing, Inc. p. 19。ISSN 0199-6649 。2020-01-15に取得。[…] 「ターゲットマイクロプロセッサの特殊な特性を考慮した変換スキームがない限り、自動トランスレータが機能する方法はありません」と、Digital Researchのプログラマーである Daniel Davis は説明します。「直接的な翻字になってしまいます。」 […] これらすべての制限にもかかわらず、トランスレータの開発は最近進歩しています。最も注目すべきは、Digital Research が 8 ビットから 16 ビットのアセンブリコードトランスレータを導入したことです。 Digital Research 社の社長Gary Kildall氏が行った調査によると、XLT86 は、従来のソフトウェアトランスレータ技術よりも進歩しているようです。Sorcim 氏の Trans や Intel 社の Convert 86 と同様に、 Kildall氏のパッケージは、アセンブリ言語コードを8080マイクロプロセッサから8086に変換します。ただし、Kildall 氏は、他のトランスレータの主な欠点のいくつかを考慮したグローバルフロー分析手法を採用しています。この手順では、8080 コードのセクションにおけるレジスタとフラグの使用を分析し、不要なコードを削除します。Digital Research 社のプログラマー Davis 氏によると、Kildall 氏が使用するアルゴリズムにより、トランスレータはプログラムを変換する際にコンテキストを考慮することができます。これまで、トランスレータプログラムの大きな問題の 1 つは、ソフトウェアが音訳以上の処理を実行できないことでした。Digital Research 社の新しいトランスレータが、コンテキストを考慮できるレベルまで技術を実際に進歩させれば、マイクロコンピュータ市場にさらに多くのソフトウェアトランスレータが普及する可能性があります。
^ Wharton, John Harrison (1994-08-01). 「業界のパイオニア、ゲイリー・キルドールが52歳で死去: 最初のマイクロコンピュータ言語とディスクオペレーティングシステムを作成」。マイクロプロセッサレポート。8 (10)。MicroDesign Resources Inc. (MDR)。2016年11月18日時点のオリジナルよりアーカイブ。 2016年11月18日閲覧。
^ 「SPA Award to Dr. Gary A. Kildall: 1995 SPA Lifetime Achievement Award Winner」。ソフトウェア出版社協会(SPA)。1995 年 3 月 13 日。2019 年 12 月 21 日時点のオリジナルよりアーカイブ。2019年 12 月 21 日に取得– www.digitalresearch.biz 経由。
^ Swaine, Michael (1997-04-01). 「Gary Kildall と Collegial Entrepreneurship」。Dr . Dobb's Journal。2007-01-24にオリジナルからアーカイブ。2006-11-20に取得。1995年 3 月、ソフトウェア発行者協会は、コンピュータ業界への貢献を称え、死後にGary を表彰しました。協会は、彼の業績の一部を次のように挙げています。[…] 1980 年代に、DRIを通じて、バイナリ再コンパイラを導入しました。[…]
^ Huitt, Robert; Eubanks, Gordon ; Rolander, Thomas "Tom" Alan ; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison ; Berg, Brian; Su, Weilian; Kildall, Scott ; Kampe, Bill (2014-04-25). Laws, David (ed.). 「Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication」(PDF) (ビデオトランスクリプション). Pacific Grove, California, USA: Computer History Museum . CHM 参照番号: X7170.2014 . 2020-01-19に取得. […] Rolander : 先ほど、Gary は問題に建築家としてアプローチするのが好きだったと述べました。 […] そして、彼はデータ構造の最も美しい図を描きました。 […] そして、それを終えて、データ構造が正しいと確信すると、彼は信じられないほど熱狂的なコーディングモードに入りました。1 日に 20 時間もコーディングを続けました […] その間、彼は完全に離れていました。何度か、何かを初めて実行したとき、それは真夜中だったこともありました。ソフトウェアを書いたことがある人なら誰でも、たとえば、画面に初めて表示されたら、誰かに知らせなければならないことを経験したことがあるでしょう。妻のロリは、私が真夜中に何度か電話を受けたことがあると言います。LOGO が 1 つの例で、XLT 86 も別の例です。彼は初めて実行し、誰かにそれを見せなければなりませんでした。そのため、何時であろうと、彼は私に電話し、私は行ってそれが実行しているのを見なければなりませんでした。 […][2][3] （33ページ）
^ Barry, Tim (1982-04-05). 「XLT-86、Digital Research の CP/M ユーティリティプログラム」。InfoWorld - マイクロコンピュータユーザー向けのニュースウィークリー。InfoWorld Software Review 。第 4 巻、第 13 号。Popular Computing, Inc. pp. 40– 41, 53。ISSN 0199-6649。2020-01-25取得。[…] XLT-86は、 PL/I-80で記述された分析トランスレータプログラムです。8080ソースプログラム全体を読み取り、それをマシンコードにアセンブルし、レジスタ、メモリ、フラグの使用率を分析して、最適化された 8086 アセンブリ言語プログラムを出力します。[ …] プログラム変換は 5 つのステップで進行します。まず、プログラムをスキャンしてアセンブルし、シンボルの値と位置を生成します。次に、プログラム構造を分析して基本ブロックに分解します。 3 番目に、基本ブロックを分析して、プログラムフローとリソースの使用状況を判断します。4 番目に、ブロック構造とレジスタ割り当てのデータがユーザー向けのリストにまとめられます。5 番目に、フロー情報とソースプログラムを使用して、8086 ソースプログラムが生成されます。[…]
^ Kildall, Gary Arlen (1982-04-19). Swaine, Michael ; Freiberger, Paul ; Markoff, John Gregory (eds.). 「Digital Research の創設者がビジネス観を語る」InfoWorld - The Newsweekly for Microcomputer Users . 特別セクション: CP/M. 第 4 巻、第 15 号。Popular Computing, Inc. pp. 23– 24. ISSN 0199-6649 . 2020-01-17に取得。[…] Kildall: […] 1 年半前、私はおそらく時間の 75% をビジネスに、25% をプログラミングに費やしていました。XLT -86 は当時取り組んでいた製品で、完成までに 9 か月かかりました。集中できていれば 3 か月のプロジェクトだったでしょう。 […]
^ Kildall, Gary Arlen (1982 年 6 月～7 月)。Bunnell , David Hugh ; Edlin, Jim (編著)。「Gary Kildall - The Man Who Created CP/M: CP/M's Creator - An Indepth PC-Exclusive Interview with Software Pioneer Gary Kildall」。PC Magazine。オペレーティングシステム。第 1 巻、第 3 号。Software Communications, Inc. pp. 32– 38, 40 。2020 年 1 月 17 日閲覧。 […] PC: プログラムを8080 形式から8086形式に変換する場合、どのような複雑な点がありますか? Kildall :ソースプログラムレベルでの直接的な変換は、ほぼ機械的に行うことができます。たとえば、8080 の「Add Immediate 5」命令は、8086 では「Add AL 5」になります。これは、オペコード自体の非常に直接的な変換です。機械的な翻訳の複雑さは、次のような状況から生じます。8080 の命令 DAD H は HL レジスターを取り、それに DE を追加します。8086 の場合、同等の命令は ADD DX BX のようなもので、特に問題はありません。DX レジスターは HL と同じで、BX は DE と同じであると言えばよいだけです。問題は、8086 の命令にはゼロフラグを設定する副作用があるのに対し、8080 の命令にはそれがないことです。機械的な翻訳では、フラグの保存、フラグの復元、シフトや回転などの操作を行うことになります。これらにより、同じセマンティック効果を得るために 5 つか 6 つの余分な命令が追加されます。8080 コードには、8086 コードでは非常に奇妙なシーケンスを生成するシーケンスが多数あります。フラグレジスターなどのせいで、うまくマッピングされないのです。ソフトウェアを移行する方法は、XLT-86と呼ばれるものです。発売されてから 6 か月ほど経ちます。 PC: 「より良い」コードとは、サイズが小さいということですか? Kildall: レジスタを節約してセマンティクスを保持しながら、すべての命令コードを直接変換した場合よりも 20 パーセント小さくなります。 PC: 変換されたプログラムのサイズは、8080 バージョンと比べてどうですか? Kildall: 8080 プログラムを 86 ランドに移し、XLT-86 変換を行うと、約 10 ～ 20 パーセント大きくなります。16 ビットマシンでは、すべての処理が難しく、命令コードが平均して少し大きくなります。興味深い現象ですが、16 ビットの世界で速度が大幅に向上しない理由の 1 つは、データバス上でより多くの命令コードが実行されるためです。 […]

さらに読む

Wenzl, Matthias; Merzdovnik, Georg; Ullrich, Johanna; Weippl, Edgar R. (2019 年 6 月) [2019 年 2 月、2018 年 11 月、2018 年 5 月]。「ハックから精巧な手法へ - バイナリ書き換えに関する調査」( PDF)。ACM Computing Surveys。52 (3)。ウィーン、オーストリア: 49:1–49:36。doi : 10.1145 /3316415。S2CID 195357367。記事 49。2021-01-15にオリジナルからアーカイブ(PDF) 。2021-11-28に取得。（36ページ）

[Mudge-1] Mudge, Trevor; Reinhardt, Steve; Tyson, Gary. 「バイナリ再コンパイルとコンパイラ/アーキテクチャの複合強化研究」umich.edu .ミシガン大学(UM)。 2012-07-23 のオリジナルからアーカイブ。 2012-07-23に取得。

[Kildall_1972_Optimization-2] Kildall, Gary Arlen (1972 年 5 月)。コンパイル時のグローバル式最適化(博士論文)。米国ワシントン州シアトル:ワシントン大学、コンピュータサイエンスグループ。論文番号 20506、技術レポート番号 72-06-02。

[Kildall_1973_Optimization-3] Kildall, Gary Arlen (1973-10-01). 「グローバルプログラム最適化への統一アプローチ」(PDF) . Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) . POPL '73. Boston, Massachusetts, USA: 194– 206. doi :10.1145/512927.512945. hdl :10945/42162. S2CID 10219496. 2017-06-29 にオリジナルからアーカイブ(PDF) . 2006-11-20に取得。（[1]）

[Freiberger_1981_Translators-4] Freiberger, Paul (1981-10-19). 「プログラムトランスレータは文字通りに、そして時には文脈に従ってそれを実行します」。InfoWorld - マイクロコンピュータユーザー向けニュース。特別セクション: コンピュータの互換性。第 3 巻、第 22 号。Popular Computing, Inc. p. 19。ISSN 0199-6649 。2020-01-15に取得。[…] 「ターゲットマイクロプロセッサの特殊な特性を考慮した変換スキームがない限り、自動トランスレータが機能する方法はありません」と、Digital Researchのプログラマーである Daniel Davis は説明します。「直接的な翻字になってしまいます。」 […] これらすべての制限にもかかわらず、トランスレータの開発は最近進歩しています。最も注目すべきは、Digital Research が 8 ビットから 16 ビットのアセンブリコードトランスレータを導入したことです。 Digital Research 社の社長Gary Kildall氏が行った調査によると、XLT86 は、従来のソフトウェアトランスレータ技術よりも進歩しているようです。Sorcim 氏の Trans や Intel 社の Convert 86 と同様に、 Kildall氏のパッケージは、アセンブリ言語コードを8080マイクロプロセッサから8086に変換します。ただし、Kildall 氏は、他のトランスレータの主な欠点のいくつかを考慮したグローバルフロー分析手法を採用しています。この手順では、8080 コードのセクションにおけるレジスタとフラグの使用を分析し、不要なコードを削除します。Digital Research 社のプログラマー Davis 氏によると、Kildall 氏が使用するアルゴリズムにより、トランスレータはプログラムを変換する際にコンテキストを考慮することができます。これまで、トランスレータプログラムの大きな問題の 1 つは、ソフトウェアが音訳以上の処理を実行できないことでした。Digital Research 社の新しいトランスレータが、コンテキストを考慮できるレベルまで技術を実際に進歩させれば、マイクロコンピュータ市場にさらに多くのソフトウェアトランスレータが普及する可能性があります。

[Wharton_1994-5] Wharton, John Harrison (1994-08-01). 「業界のパイオニア、ゲイリー・キルドールが52歳で死去: 最初のマイクロコンピュータ言語とディスクオペレーティングシステムを作成」。マイクロプロセッサレポート。8 (10)。MicroDesign Resources Inc. (MDR)。2016年11月18日時点のオリジナルよりアーカイブ。 2016年11月18日閲覧。

[SPA_1995-6] 「SPA Award to Dr. Gary A. Kildall: 1995 SPA Lifetime Achievement Award Winner」。ソフトウェア出版社協会(SPA)。1995 年 3 月 13 日。2019 年 12 月 21 日時点のオリジナルよりアーカイブ。2019年 12 月 21 日に取得– www.digitalresearch.biz 経由。

[Swaine_1997-7] Swaine, Michael (1997-04-01). 「Gary Kildall と Collegial Entrepreneurship」。Dr . Dobb's Journal。2007-01-24にオリジナルからアーカイブ。2006-11-20に取得。1995年 3 月、ソフトウェア発行者協会は、コンピュータ業界への貢献を称え、死後にGary を表彰しました。協会は、彼の業績の一部を次のように挙げています。[…] 1980 年代に、DRIを通じて、バイナリ再コンパイラを導入しました。[…]

[Laws_2014_IEEE-8] Huitt, Robert; Eubanks, Gordon ; Rolander, Thomas "Tom" Alan ; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison ; Berg, Brian; Su, Weilian; Kildall, Scott ; Kampe, Bill (2014-04-25). Laws, David (ed.). 「Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication」(PDF) (ビデオトランスクリプション). Pacific Grove, California, USA: Computer History Museum . CHM 参照番号: X7170.2014 . 2020-01-19に取得. […] Rolander : 先ほど、Gary は問題に建築家としてアプローチするのが好きだったと述べました。 […] そして、彼はデータ構造の最も美しい図を描きました。 […] そして、それを終えて、データ構造が正しいと確信すると、彼は信じられないほど熱狂的なコーディングモードに入りました。1 日に 20 時間もコーディングを続けました […] その間、彼は完全に離れていました。何度か、何かを初めて実行したとき、それは真夜中だったこともありました。ソフトウェアを書いたことがある人なら誰でも、たとえば、画面に初めて表示されたら、誰かに知らせなければならないことを経験したことがあるでしょう。妻のロリは、私が真夜中に何度か電話を受けたことがあると言います。LOGO が 1 つの例で、XLT 86 も別の例です。彼は初めて実行し、誰かにそれを見せなければなりませんでした。そのため、何時であろうと、彼は私に電話し、私は行ってそれが実行しているのを見なければなりませんでした。 […][2][3] （33ページ）

[Barry_1982_XLT86-9] Barry, Tim (1982-04-05). 「XLT-86、Digital Research の CP/M ユーティリティプログラム」。InfoWorld - マイクロコンピュータユーザー向けのニュースウィークリー。InfoWorld Software Review 。第 4 巻、第 13 号。Popular Computing, Inc. pp. 40– 41, 53。ISSN 0199-6649。2020-01-25取得。[…] XLT-86は、 PL/I-80で記述された分析トランスレータプログラムです。8080ソースプログラム全体を読み取り、それをマシンコードにアセンブルし、レジスタ、メモリ、フラグの使用率を分析して、最適化された 8086 アセンブリ言語プログラムを出力します。[ …] プログラム変換は 5 つのステップで進行します。まず、プログラムをスキャンしてアセンブルし、シンボルの値と位置を生成します。次に、プログラム構造を分析して基本ブロックに分解します。 3 番目に、基本ブロックを分析して、プログラムフローとリソースの使用状況を判断します。4 番目に、ブロック構造とレジスタ割り当てのデータがユーザー向けのリストにまとめられます。5 番目に、フロー情報とソースプログラムを使用して、8086 ソースプログラムが生成されます。[…]

[Swaine_1982_CPM-10] Kildall, Gary Arlen (1982-04-19). Swaine, Michael ; Freiberger, Paul ; Markoff, John Gregory (eds.). 「Digital Research の創設者がビジネス観を語る」InfoWorld - The Newsweekly for Microcomputer Users . 特別セクション: CP/M. 第 4 巻、第 15 号。Popular Computing, Inc. pp. 23– 24. ISSN 0199-6649 . 2020-01-17に取得。[…] Kildall: […] 1 年半前、私はおそらく時間の 75% をビジネスに、25% をプログラミングに費やしていました。XLT -86 は当時取り組んでいた製品で、完成までに 9 か月かかりました。集中できていれば 3 か月のプロジェクトだったでしょう。 […]

[Bunnell_1982_CPM-11] Kildall, Gary Arlen (1982 年 6 月～7 月)。Bunnell , David Hugh ; Edlin, Jim (編著)。「Gary Kildall - The Man Who Created CP/M: CP/M's Creator - An Indepth PC-Exclusive Interview with Software Pioneer Gary Kildall」。PC Magazine。オペレーティングシステム。第 1 巻、第 3 号。Software Communications, Inc. pp. 32– 38, 40 。2020 年 1 月 17 日閲覧。 […] PC: プログラムを8080 形式から8086形式に変換する場合、どのような複雑な点がありますか? Kildall :ソースプログラムレベルでの直接的な変換は、ほぼ機械的に行うことができます。たとえば、8080 の「Add Immediate 5」命令は、8086 では「Add AL 5」になります。これは、オペコード自体の非常に直接的な変換です。機械的な翻訳の複雑さは、次のような状況から生じます。8080 の命令 DAD H は HL レジスターを取り、それに DE を追加します。8086 の場合、同等の命令は ADD DX BX のようなもので、特に問題はありません。DX レジスターは HL と同じで、BX は DE と同じであると言えばよいだけです。問題は、8086 の命令にはゼロフラグを設定する副作用があるのに対し、8080 の命令にはそれがないことです。機械的な翻訳では、フラグの保存、フラグの復元、シフトや回転などの操作を行うことになります。これらにより、同じセマンティック効果を得るために 5 つか 6 つの余分な命令が追加されます。8080 コードには、8086 コードでは非常に奇妙なシーケンスを生成するシーケンスが多数あります。フラグレジスターなどのせいで、うまくマッピングされないのです。ソフトウェアを移行する方法は、XLT-86と呼ばれるものです。発売されてから 6 か月ほど経ちます。 PC: 「より良い」コードとは、サイズが小さいということですか? Kildall: レジスタを節約してセマンティクスを保持しながら、すべての命令コードを直接変換した場合よりも 20 パーセント小さくなります。 PC: 変換されたプログラムのサイズは、8080 バージョンと比べてどうですか? Kildall: 8080 プログラムを 86 ランドに移し、XLT-86 変換を行うと、約 10 ～ 20 パーセント大きくなります。16 ビットマシンでは、すべての処理が難しく、命令コードが平均して少し大きくなります。興味深い現象ですが、16 ビットの世界で速度が大幅に向上しない理由の 1 つは、データバス上でより多くの命令コードが実行されるためです。 […]