Rematerialization
Encyclopedia
Rematerialization or remat is a compiler optimization
which saves time by recomputing a value instead of loading it from memory. It is typically tightly integrated with register allocation
, where it is used as an alternative to spilling registers to memory. It was conceived by Preston Briggs, Keith D. Cooper, and Linda Torczon in 1992.
Traditional optimizations such as common subexpression elimination
and loop invariant hoisting often focus on eliminating redundant computation. Since computation requires CPU 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 decreases register pressure by increasing the amount of CPU computation. To avoid adding more computation time than necessary, rematerialization 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
.
Compiler optimization
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
which saves time by recomputing a value instead of loading it from memory. It is typically tightly integrated with register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
, where it is used as an alternative to spilling registers to memory. It was conceived by Preston Briggs, Keith D. Cooper, and Linda Torczon in 1992.
Traditional optimizations such as common subexpression elimination
Common subexpression elimination
In computer science, common subexpression elimination is a compiler optimization that searches for instances of identical expressions , and analyses whether it is worthwhile replacing them with a single variable holding the computed value.- Example :In the following code: a = b * c + g; d = b * c...
and loop invariant hoisting often focus on eliminating redundant computation. Since computation requires CPU 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 decreases register pressure by increasing the amount of CPU computation. To avoid adding more computation time than necessary, rematerialization 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
Available expression
In the field of compiler optimizations, available expressions is an analysis algorithm that determines for each point in the program the set of expressions that need not be recomputed. Those expressions are said to be available at such a point...
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
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
.
External links
- 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 gccGNU Compiler CollectionThe GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...
's implementation of rematerialization.