En la teoría del compilador , la eliminación de redundancia parcial (PRE) es una optimización del compilador que elimina las expresiones que son redundantes en algunas pero no necesariamente en todas las rutas a través de un programa. PRE es una forma de eliminación común de subexpresiones .
Una expresión se denomina parcialmente redundante si el valor calculado por la expresión ya está disponible en algunas, pero no en todas, las rutas a través de un programa a esa expresión. Una expresión es completamente redundante si el valor calculado por la expresión está disponible en todas las rutas del programa a esa expresión. PRE puede eliminar expresiones parcialmente redundantes insertando la expresión parcialmente redundante en las rutas que aún no la calculan, lo que hace que la expresión parcialmente redundante sea totalmente redundante.
Por ejemplo, en el siguiente código:
if ( some_condition ) { // algún código que no altera x y = x + 4 ; } else { // otro código que no altera x } z = x + 4 ;
la expresión x+4
asignada a z
es parcialmente redundante porque se calcula dos veces si some_condition
es verdadera. PRE realizaría movimiento de código en la expresión para producir el siguiente código optimizado:
if ( some_condition ) { // algún código que no altera x t = x + 4 ; y = t ; } else { // otro código que no altera x t = x + 4 ; } z = t ;
Una propiedad interesante de PRE es que realiza (una forma de) eliminación de subexpresiones comunes y movimiento de código invariante de bucle al mismo tiempo. [1] [2] Además, PRE puede extenderse para eliminar redundancias parciales lesionadas , realizando así efectivamente la reducción de fuerza . Esto hace que PRE sea una de las optimizaciones más importantes en la optimización de compiladores. Tradicionalmente, PRE se aplica a expresiones léxicamente equivalentes, pero recientemente se han publicado formulaciones de PRE basadas en una forma de asignación única estática que aplican el algoritmo PRE a valores en lugar de expresiones, unificando PRE y la numeración de valores globales .
Ver también
Referencias
- ^ Optimización global por supresión de despidos parciales , Morel y Renvoise, 1979
- ^ Eliminación efectiva de redundancia parcial , Briggs y Cooper, 1994
Otras lecturas
- Muchnick, Steven S. Diseño e implementación avanzados del compilador . Morgan Kaufmann. 1997.
- Knoop, J., Ruthing, O. y Steffen, B. Lazy Code Motion . Avisos ACM SIGPLAN Vol. 27, Núm. 7, julio de 1992, '92 Conference on PLDI.
- Paleri, VK, Srikant, YN y Shankar, P. Un algoritmo simple para la eliminación de redundancia parcial . Avisos SIGPLAN, vol. 33 (12). páginas 35–43 (1998).
- Kennedy, R., Chan, S., Liu, SM, Lo, R., Peng, T. y Chow, F. Eliminación parcial de redundancia en forma SSA . Transacciones de ACM en lenguajes de programación Vol. 21, Núm. 3, págs. 627–676, 1999.
- VanDrunen, T., y Hosking, Eliminación de redundancia parcial basada en valores de AL , Lecture Notes in Computer Science Vol. 2985/2004, págs.167-184, 2004.
- Cai, Q. y Xue, J. Eliminación de redundancia parcial basada en la especulación óptima y eficiente ". Simposio internacional sobre generación y optimización de código (CGO'03), 91-104, 2003.
- Xue, J. y Knoop, J. Una nueva mirada al PRE como un problema de flujo máximo . Conferencia internacional sobre construcción de compiladores (CC'06), páginas 139-154, Viena, Austria, 2006.
- Xue, J. y Cai Q. Un algoritmo óptimo de por vida para PRE especulativo . Transacciones ACM sobre arquitectura y optimización de código Vol. 3, núm. 3, págs. 115-155, 2006.