- Rematerialization
Rematerialization is a
compiler optimization which saves time by recomputing a value instead of loading it from memory. It is typically tightly integrated withregister allocation , where it is used as an alternative to spilling registers to memory. It was conceived byPreston Briggs ,Keith D. Cooper , andLinda Torczon in1992 .Traditional optimizations such as
common subexpression elimination andloop invariant hoisting often focus on eliminating redundant computation. Since computation requiresCPU cycles, this is usually a good thing, but it has the potentially devastating side effect that it can increase the live ranges of variables and create many new variables, resulting in spills during register allocation. Rematerialization is nearly the opposite: it decreasesregister pressure by increasing the amount of CPU computation. To avoid adding more computation time than necessary, rematerialize is done only when the compiler can be confident that it will be of benefit — that is, when a register spill to memory would otherwise occur.Rematerialization works by keeping track of the expression used to compute each variable, using the concept of
available expression s. Sometimes the variables used to compute a value are modified, and so can no longer be used to rematerialize that value. The expression is then said to no longer be available. Other criteria must also be fulfilled, for example a maximum complexity on the expression used to rematerialize the value; it would do no good to rematerialize a value using a complex computation that takes more time than a load. Usually the expression must also have no side effects.External links
* P. Briggs, K. D. Cooper, and L. Torczon. [http://citeseer.ist.psu.edu/briggs92rematerialization.html 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. [http://gcc.fyxm.net/summit/2004/Register%20Rematerialization.pdf Register Rematerialization in GCC] . Discusses gcc's implementation of rematerialization.
Wikimedia Foundation. 2010.
