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 practical disciplines (includin ...
, 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 c ...
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 allocat ...
, 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 compute ...
,
Marc Auslander,
Ashok Chandra
Ashok K. Chandra (30 July 1948 – 15 November 2014) was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center. Chandra received his PhD in ...
,
John Cocke,
Martin Hopkins Martin may refer to:
Places
* Martin City (disambiguation)
* Martin County (disambiguation)
* Martin Township (disambiguation)
Antarctica
* Martin Peninsula, Marie Byrd Land
* Port Martin, Adelie Land
* Point Martin, South Orkney Islands
Aus ...
and
Peter Markstein 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 B ...
,
Keith D. Cooper, and
Linda Torczon 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 sin ...
and
loop invariant hoisting often focus on eliminating redundant computation. Since computation requires
CPU
A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, an ...
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), t ...
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 expressions. 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