In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, rematerialization or remat is a
compiler optimization
An optimizing compiler is a compiler designed to generate code that is optimized in aspects such as minimizing program execution time, memory usage, storage size, and power consumption. Optimization is generally implemented as a sequence of op ...
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 (computer science), expression results to a limited number of processor registers.
Register allocation can happen over a basic bloc ...
, 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 Argentina, Argentine-United States, American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, ...
,
Marc Auslander,
Ashok Chandra,
John Cocke,
Martin Hopkins Martin may refer to:
Places Antarctica
* Martin Peninsula, Marie Byrd Land
* Port Martin, Adelie Land
* Point Martin, South Orkney Islands
Europe
* Martin, Croatia, a village
* Martin, Slovakia, a city
* Martín del Río, Aragón, Spain
* Mart ...
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 or Prestons may refer to:
Places Australia
*Preston, Victoria
** City of Preston (Victoria)
**Electoral district of Preston
**Preston railway station, Melbourne
* Preston, Queensland, Toowoomba and Lockyer Valley regions
* Preston, Quee ...
,
Keith D. Cooper
Keith D. Cooper is an American computer scientist and the L. John and Ann H. Doerr Professor of Computational Engineering at Rice University
William Marsh Rice University, commonly referred to as Rice University, is a Private university, pri ...
, and
Linda Torczon
Linda is an English feminine given name, derived from the Spanish word , meaning "pretty."
Linda may also refer to:
Names
* Linda (given name), a female given name (including a list of people and fictional characters so named)
* Linda (singer) ...
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
In computer programming, loop-invariant code consists of statements or expressions (in an imperative programming, imperative programming language) that can be moved outside the body of a loop without affecting the semantics of the program. Loop-i ...
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 primary processor in a given computer. Its electronic circuitry executes instructions of a computer program, such as arithmetic, log ...
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
In computer science, an instruction set architecture (ISA) is an abstract model that generally defines how software controls the CPU in a computer or a family of computers. A device or program that executes instructions described by that ISA, ...
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 poin ...
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 of the use of a medicinal drug or other treatment, usually adverse but sometimes beneficial, that is unintended. Herbal and traditional medicines also have side effects.
A drug or procedure usually used ...
.
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.
* Mukta Punjabi
Register Rematerialization in GCC Discusses
gcc's implementation of rematerialization.
{{Compiler optimizations
Compiler optimizations