Rematerialization

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. It was conceived by Preston Briggs, Keith D. Cooper, and Linda Torczon in 1992.

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. To avoid adding more computation time than necessary, rematerialize 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.

External links

* P. Briggs, K. D. Cooper, and L. Torczon. [http://citeseer.ist.psu.edu/briggs92rematerialization.html 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 Punjani. [http://gcc.fyxm.net/summit/2004/Register%20Rematerialization.pdf Register Rematerialization in GCC] . Discusses gcc's implementation of rematerialization.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • rematerialization — n. * * * …   Universalium

  • rematerialization — noun a) The act or process of rematerializing. b) A compiler optimization that saves time by recomputing a value instead of loading it from memory …   Wiktionary

  • rematerialization — n …   Useful english dictionary

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Transporter (Star Trek) — Transporter Transporter chamber aboard U.S.S. Enterprise D. Plot element from the Star Trek franchise First appearance Star Tr …   Wikipedia

  • Algorithmic efficiency — In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or… …   Wikipedia

  • Lookup table — In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since …   Wikipedia

  • Stargate (video game) — This article is about the 1980s Stargate video game. For other uses, see Stargate (disambiguation). Stargate Developer(s) Vid Kidz Publisher(s) Williams Electronics Designer(s) …   Wikipedia

  • Technology in Stargate — Naqahdah redirects here. For one of the archaeologically identified cultures of Pre Dynastic Egypt, see Naqadan culture. For the town on the west bank of the Nile in Egypt, see Naqada. For other uses, see Naqada (disambiguation). The most… …   Wikipedia

  • List of Stargate Atlantis characters — Season 4 cast from left to right: Dr. Rodney McKay, Col. Samantha Carter, Lt. Col. John Sheppard, Teyla Emmagan, and Ronon Dex. The characters from the Canadian military science fiction television series Stargate Atlantis were created by Brad… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”