This article is about the compiler optimization. For the Star Trek transporter technology, see transporter (Star Trek). A transporter on the USS Enterprise (NCC-1701-D) In the Star Trek fictional universe, transporters are teleportation machines. ...

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. It was conceived by Preston Briggs, Keith D. Cooper, and Linda Torczon in 1992. Compiler optimization techniques are optimization techniques that have been programmed into a compiler. ... In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers. ... 1992 was a leap year starting on Wednesday. ...

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. Because we don't wish to add any more computation time than necessary, we rematerialize only when we are confident that it will be of benefit — that is, when we would otherwise spill a register to memory. In compiler theory, common subexpression elimination (CSE) is the practice of finding repeated redundant expression evaluations, and replacing them with a single computation assigned to a temporary variable. ... Loop-invariant code in an imperative programming language consists of statements which could be moved to before the loop (if the loop always terminates), or after the loop, without affecting the semantics of the program. ...

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.

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 original paper, in gzip'ed Postscript format.
• Mukta Punjani. Register Rematerialization in GCC. Discusses gcc's implementation of rematerialization.