再物質化

コンピュータサイエンスにおいて、再実体化またはリマットは、メモリから値をロードする代わりに再計算することで時間を節約するコンパイラの最適化である。これは通常、レジスタ割り当てと密接に統合されており、レジスタをメモリにスピルする代わりに使用される。これは、Gregory Chaitin、Marc Auslander、Ashok Chandra、John Cocke 、Martin Hopkins、およびPeter Marksteinによって考案され、1970年代後半に801ミニコンピュータ用のPl.8コンパイラに実装された。その後、1992年にPreston Briggs、 Keith D. Cooper 、およびLinda Torczonによって改良が行われた。

共通部分式の除去やループ不変式の巻き上げなどの従来の最適化では、冗長な計算の除去に重点が置かれることがよくあります。計算にはCPUサイクルが必要なので、これは通常は良いことですが、変数の有効範囲が拡大し、多くの新しい変数が作成され、レジスタ割り当て中にスピルが発生する可能性があるという、潜在的に壊滅的な副作用があります。再実体化はほぼ逆で、 CPU 計算量を増やすことでレジスタの負荷を減らします。必要以上に計算時間を追加しないようにするため、再実体化は、コンパイラがメリットがあると確信できる場合、つまり、そうでなければメモリへのレジスタ スピルが発生する場合にのみ行われます。

再マテリアライゼーションは、使用可能な式の概念を使用して、各変数を計算するために使用される式を追跡することによって機能します。値の計算に使用される変数が変更され、その値を再マテリアライズするために使用できなくなる場合があります。その場合、式は使用できなくなったとみなされます。値を再マテリアライズするために使用される式の最大複雑度など、他の基準も満たす必要があります。ロードよりも時間がかかる複雑な計算を使用して値を再マテリアライズしても意味がありません。通常、式には副作用があってはなりません。

• Chaitin、Gregory、Marc Auslander、Ashok Chandra、John Cocke、Martin Hopkins、および Peter Markstein。「カラーリングによるレジスタ割り当て、Computer Languages、Vol. 6、No. 1、1981、pp. 47-57」
• P. Briggs、KD Cooper、L. Torczon。再物質化。SIGPLAN 92 プログラミング言語の設計と実装に関する会議の議事録、SIGPLAN Notices 27(7)、p.311-321。1992 年 7 月。
• Mukta Punjabi。GCC でのレジスタの再マテリアライゼーション。gcc の再マテリアライゼーションの実装について説明します。