再実体化

再実体化（英: Rematerializationあるいは remat）とは、コンパイラ最適化手法の一つで、メモリからロードせずに再計算を行うことで実行時間を節約するものである。典型的にレジスタ割り付けと統合した形で用いられ、レジスタに格納しきれずメモリにデータを書き込んでしまうことを避けるために使用される。再実体化は Preston Briggs、Keith D. Cooper、Linda Torczon によって 1992 年に提唱された。

共通部分式除去のような古典的な最適化では無駄な計算を避けることに焦点が置かれる。計算には CPU サイクルが必要であるため、通常これは望ましいことである。しかし、変数の生存時間を増大させ、また新しい変数を多数作成するため、レジスタ割り当ての際にメモリにデータを追い出す必要を生じるという大きな副作用を潜在的に抱えている。再実体化はほぼその逆であり、CPU の計算量を増加させて割り当てるレジスタを減少させる。必要以上の計算量増加を防ぐため、コンパイラが十分有益と確信できる場合、すなわちレジスタがあふれてメモリを使用するような場合のみ行われる。

再実体化は、available expression の考え方を用いて各変数を計算する式を監視することによって動作する。ある値を計算するために用いられる変数は変更されることもあり、その場合にはもはや値の再実体化に使用することができない。このとき、その式は利用可能でないと呼ばれる。もう一つの条件として、例えば値の再実体化を行う式の複雑さの最大値がある。ロードする以上に時間のかかる非常に複雑な計算を行って再実体化を行うのは望ましくない。通常は式に副作用があってはならない。

外部リンク

• P. Briggs, K. D. Cooper, and L. Torczon. Rematerialization. Proceedings of the SIGPLAN 92 Conference on Programming Language Design and Implementation, SIGPLAN Notices 27(7), p.311-321. July 1992. The CiteSeer page for the original paper.
• Mukta Punjani. Register Rematerialization in GCC. Discusses gcc's implementation of rematerialization.