Loading article…
コンピュータサイエンスにおいて、コード モーション(コード ホイスト、コード シンキング、ループ不変コード モーション、コード ファクタリングとも呼ばれる) は、パフォーマンスやサイズの利点を得るためにプログラム内でコードを移動するプロセスの総称であり、ほとんどの最適化コンパイラで実行される一般的な最適化です。コード モーションを取り巻く用語の意味に一貫性がないため、異なる種類のコード モーションを区別することが難しい場合があります。
用途
コード モーションにはさまざまな用途と利点があり、その多くは実装において互いに重複しています。
未使用/無駄な操作の削除
コードシンキングは、レイジーコードモーションとも呼ばれ、命令をそれが使用される分岐に移動することで無駄な命令を減らす技術の用語です。[1]操作が分岐の前に実行され、分岐パスの1つだけがその操作の結果を使用する場合、コードシンキングでは、その操作が使用される分岐に移動します。
この手法は、結果が破棄されたり使用されないときにコードを削除するという意味でデッド コード削除の一種ですが、デッド コード削除とは対照的に、実行コード パスでその命令の結果が使用される可能性がある場合でも、無意味な命令を削除できます。
プログラムのサイズを縮小する
コードファクタリングとは、ブランチ内の共通の依存関係をその上のブランチにマージするサイズ最適化手法のことです。[2]整数を因数分解して数を可能な限り小さな形式 (因数) に分解するのと同じように、コード因数分解では、共通の「因数」を重複がなくなるまでマージして、コードを可能な限り小さな形式に変換します。
依存関係の停止を減らす
グローバルコードモーション、ローカルコードモーション、コードスケジューリング、命令スケジューリング、コードホイスト/シンキングはすべて、CPU内での実行効率を向上させるために命令を再配置（または「スケジュール」）する技術を指す用語です。 [3] [4]現代のCPUは、クロックサイクルごとに5つ以上の命令をスケジュールできます。ただし、CPUは現在（またはまだ実行されていない）命令のデータに依存する命令をスケジュールすることはできません。コンパイラは、CPUが任意の時点で処理できる命令の量を最大化する方法で依存関係をインターリーブします。[5]
廃止されたIntel Itaniumアーキテクチャでは、分岐予測（BRP）命令はコンパイラによって手動で分岐の上に持ち上げられ、CPUがすぐに分岐を実行できるようにします。Itaniumは、プロセッサの効率を最大化するためにCPUからの追加コードスケジューリングに依存しています。[6]
ループ不変コードの動き
ループ不変コードの移動は、ループ不変コードをループの外側の位置に移動するプロセスです。これにより、同じ結果を得るために一部の計算が 2 回実行されるのを防ぐことで、ループの実行時間を短縮できます。
コンパイラの例
LLVM
LLVMは、単一の静的割り当て形式でシンクパスを持っています。LLVM 15.0は、コードパスのいずれかにストア命令が含まれている場合、またはエラーが発生する可能性がある場合、操作をシンクしません。[7]さらに、LLVMは命令をループ にシンクしません。
湾岸協力会議
GNUコンパイラコレクションは、コンパイルされたプログラムのサイズを縮小することを目的として、「コードファクタリング」という名前でコード移動を実装しています。[8] GCCは、「既存の依存関係を無効にせず、新しい依存関係を導入しない」場合に、コードを上方または下方に移動します。[9]
ルアJIT
LuaJIT は「割り当てシンク」という名前でコードシンクを使用し、コンパイルされたコードがループ内で一時オブジェクトの割り当てと収集に費やす時間を短縮します。[10]割り当てシンクは、割り当てられたオブジェクトが実行コードから逃れる可能性のある実行パスに割り当てを移動し、ヒープ割り当てが必要になります。削除された割り当てはすべて、フィールドを介したロードツーストア転送で埋められます。[11]
参照
参考文献
- ^ Craft, Michael; Offut, Jefferson (1994). 「コンパイラ最適化手法を使用した等価ミュータントの検出」.ソフトウェアテスト、検証、信頼性. 4 (3): 131–154. doi :10.1002/stvr.4370040303. S2CID 35717348. 2022年2月25日閲覧。
- ^ Lóki、Gábor、他「GCC でのコード ファクタリング」2004 GCC 開発者サミット議事録。2004 年。
- ^ Fasse, Justus、et al. Code Transformations to Increase Prepass Scheduling Opportunities in CompCert. Diss. Master Thesis of Science. Université Grenoble Alpes. https://www-verimag. imag. fr/~ boulme/CPP_2022/FASSE-Justus-MSc-Thesis_2021. pdf、2021 年。
- ^ Gupta, Rajiv (1998). 「グローバル命令 スケジューリングのためのコードモーションフレームワーク」。コンパイラ構築。コンピュータサイエンスの講義ノート。第 1383 巻。pp. 219–233。doi : 10.1007 / BFb0026434。ISBN 978-3-540-64304-3。
- ^ Chang, Pohua P.、他「スーパースカラーおよびスーパーパイプラインプロセッサにおけるプレパスコードスケジューリングの重要性」IEEE Transactions on Computers 44.3 (1995): 353-370。
- ^ Sharangpani, H.; Arora, H. (2000 年 9 月). 「Itanium プロセッサ マイクロアーキテクチャ」. IEEE Micro . 20 (5): 24–43. doi :10.1109/40.877948. ISSN 1937-4143.
- ^ 「LLVM: lib/Transforms/Scalar/Sink.cpp ソースファイル」. llvm.org . 2022年2月25日閲覧。
- ^ 「コードファクタリングの最適化 - GNU プロジェクト」。gcc.gnu.org 。2022年2 月 25 日閲覧。
- ^ 「GCC Developer's Summit 2004 - Code Factoring.pdf」(PDF) . gnu.org . 2022年2月25日閲覧。
- ^ 「git HEAD での割り当てシンク - luajit - FreeLists」。www.freelists.org。2022年2 月 25 日閲覧。
- ^ 「割り当てシンキング最適化」。wiki.luajit.org。