Rematerialization

Rematerialization 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.

Traditional optimizations such as common subexpress 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 devestating side effect that it can increase the live ranges of variables, resulting in spills during register allocation. Rematerialization is nearly the opposite: it decreases register pressure by increasing the amount of CPU computation.

Rematerialization works by keeping track of the expression used to compute each variable, using the concept of available expressions. Sometimes the variables used to compute a value are modified, and so can no longer be used to rematerialize that value. We say that this expression is no longer available. We must also fulfill other criteria, such as 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.