Hispanopedia WikiEn la teoría del compilador , la eliminación de redundancia parcial (PRE) es una optimización del compilador que elimina expresiones que son redundantes en algunas, pero no necesariamente en todas las rutas de un programa. PRE es una forma de eliminación de subexpresiones comunes .
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 hacia esa expresión. Una expresión es totalmente redundante si el valor calculado por la expresión está disponible en todas las rutas a través del programa hacia 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+4asignada a zes parcialmente redundante porque se calcula dos veces si some_conditiones verdadera. PRE realizaría un movimiento de código en la expresión para generar 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 se puede extender para eliminar redundancias parciales dañadas , realizando así de manera efectiva 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 la 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 .
Véase también
Referencias
- ^ Optimización global mediante la supresión de redundancias parciales, Morel y Renvoise, 1979
- ^ Eliminación eficaz de redundancia parcial, Briggs y Cooper, 1994
Lectura adicional
- Muchnick, Steven S. Diseño e implementación de compiladores avanzados . Morgan Kaufmann. 1997.
- Knoop, J., Ruthing, O. y Steffen, B. Lazy Code Motion . ACM SIGPLAN Notices Vol. 27, Núm. 7, julio de 1992, Conferencia '92 sobre PLDI.
- Paleri, VK, Srikant, YN y Shankar, P. Un algoritmo simple para la eliminación parcial de redundancia . SIGPLAN Notices, 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 formato SSA . ACM Transactions on Programming Languages Vol. 21, Núm. 3, págs. 627–676, 1999.
- VanDrunen, T., y Hosking, AL Eliminación de redundancia parcial basada en valores , Notas de clase en Ciencias de la computación, vol. 2985/2004, págs. 167 – 184, 2004.
- Cai, Q. y Xue, J. "Eliminación de redundancia parcial basada en 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 a 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 . ACM Transactions on Architecture and Code Optimization Vol. 3, Núm. 3, págs. 115–155, 2006.