In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, rematerialization or remat is a
compiler optimization
In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program. Common requirements are to minimize a program's execution time, memory footprint, storage size, and power con ...
which saves time by recomputing a value instead of loading it from memory. It is typically tightly integrated with
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocation' ...
, where it is used as an alternative to
spilling registers to memory. It was conceived by
Gregory Chaitin
Gregory John Chaitin ( ; born 25 June 1947) is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-t ...
,
Marc Auslander
Marc Alan Auslander is an American computer scientist known for his contributions to the PL/8 compiler. He spent his entire career at the IBM Thomas J. Watson Research Center in Yorktown Heights, NY.
Auslander received a Bachelor of Arts degre ...
,
Ashok Chandra,
John Cocke,
Martin Hopkins and
Peter Markstein
Peter may refer to:
People
* List of people named Peter, a list of people and fictional characters with the given name
* Peter (given name)
** Saint Peter (died 60s), apostle of Jesus, leader of the early Christian Church
* Peter (surname), a sur ...
and implemented in the Pl.8 compiler for the 801 Minicomputer in the late 1970s. Later improvements were made by
Preston Briggs
Preston is a place name, surname and given name that may refer to:
Places
England
*Preston, Lancashire, an urban settlement
**The City of Preston, Lancashire, a borough and non-metropolitan district which contains the settlement
**County Boro ...
,
Keith D. Cooper, and
Linda Torczon
Linda may refer to:
As a name
* Linda (given name), a female given name (including a list of people and fictional characters so named)
* Linda (singer) (born 1977), stage name of Svetlana Geiman, a Russian singer
* Anita Linda (born Alice Lake ...
in 1992.
Traditional optimizations such as
common subexpression elimination In compiler theory, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a sing ...
and
loop invariant hoisting
In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming language) that can be moved outside the body of a loop without affecting the semantics of the program. Loop-invariant code motion ( ...
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
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), the ...
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 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
In medicine, a side effect is an effect, whether therapeutic or adverse, that is secondary to the one intended; although the term is predominantly employed to describe adverse effects, it can also apply to beneficial, but unintended, consequence ...
.
External links
* Chaitin, Gregory, Marc Auslander, Ashok Chandra, John Cocke, Martin Hopkins, and Peter Markstein. "Register Allocation Via Coloring, Computer Languages, Vol. 6, No. 1, 1981, pp. 47-57"
* 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 Punjabi
Register Rematerialization in GCC Discusses
gcc's implementation of rematerialization.
{{Compiler optimizations
Compiler optimizations