Částečné odstranění nadbytečnosti - Partial redundancy elimination

V teorii překladačů , částečného odstranění redundance (PRE) je optimalizační překladač , který eliminuje výrazy , které jsou vzhledem na některých, ale ne nutně všechny cesty prostřednictvím programu. PRE je forma společné eliminace subexprese .

Výraz se nazývá částečně nadbytečný, pokud je hodnota vypočítaná výrazem již k dispozici na některých, ale ne na všech cestách programu k tomuto výrazu. Výraz je zcela nadbytečný, pokud je hodnota vypočítaná výrazem k dispozici na všech cestách programem k tomuto výrazu. PRE může eliminovat částečně nadbytečné výrazy vložením částečně nadbytečného výrazu na cesty, které jej již nepočítají, čímž se částečně nadbytečný výraz stane plně nadbytečným.

Například v následujícím kódu: 

 if (some_condition) {
   // some code that does not alter x
   y = x + 4;
 }
 else {
   // other code that does not alter x
 }
 z = x + 4;

výraz x+4přiřazený zje částečně nadbytečný, protože je vypočítán dvakrát, pokud some_conditionje pravdivý. PRE by provedl pohyb kódu ve výrazu, aby poskytl následující optimalizovaný kód: 

 if (some_condition) {
   // some code that does not alter x
   t = x + 4;
   y = t;
 }
 else {
   // other code that does not alter x
   t = x + 4;
 }
 z = t;

Zajímavou vlastností PRE je, že provádí (formou) běžnou eliminaci subexprese a pohyb kódu invariantního vůči smyčce současně. PRE lze navíc rozšířit tak, aby eliminoval zraněné částečné propouštění, čímž účinně provádí snížení síly . Díky tomu je PRE jednou z nejdůležitějších optimalizací při optimalizaci překladačů. Tradičně se PRE používá na lexikálně ekvivalentní výrazy, ale v poslední době byly publikovány formulace PRE založené na statickém formuláři pro jedno přiřazení, které místo výrazů používají algoritmus PRE na hodnoty, sjednocující PRE a číslování globálních hodnot .

Viz také

Reference

Další čtení

  • Muchnick, Steven S. Pokročilý návrh a implementace kompilátoru . Morgan Kaufmann. 1997.
  • Knoop, J., Ruthing, O. a Steffen, B. Lazy Code Motion . Oznámení ACM SIGPLAN Vol. 27, č. 7, červenec 1992, konference '92 o PLDI.
  • Paleri, VK, Srikant, YN a Shankar, P. Jednoduchý algoritmus pro odstranění částečné nadbytečnosti . SIGPLAN Notices, sv. 33 (12). strany 35–43 (1998).
  • Kennedy, R., Chan, S., Liu, SM, Lo, R., Peng, T. a Chow, F. Částečné odstranění nadbytečnosti ve formě SSA . ACM Transactions on Programming Languages ​​Vol. 21, č. 3, s. 627–676, 1999.
  • VanDrunen, T. a Hosking, AL Value-Based Partial Redundancy Elimination , Lecture Notes in Computer Science Vol. 2985/2004, s. 167 - 184, 2004.
  • Cai, Q. a Xue, J. Optimální a efektivní částečná eliminace redundance na základě spekulací ". Mezinárodní sympozium o generování a optimalizaci kódu (CGO'03), 91-104, 2003.
  • Xue, J. a Knoop, J. Nový pohled na PRE jako problém maximálního toku . Mezinárodní konference o konstrukci kompilátorů (CC'06), strany 139–154, Vídeň, Rakousko, 2006.
  • Xue, J. a Cai Q. Celoživotní optimální algoritmus pro spekulativní PRE . ACM Transactions on Architecture and Code Optimization Vol. 3, č. 3, s. 115–155, 2006.