Preguntas de optimizaciones del compilador

Question

1. ¿Cuáles son algunas de las formas en que un compilador elimina las repeticiones de subexpresiones repetidas? ¿Cómo hacer un seguimiento de las sub-expresiones? ¿Y cómo identificas las repetidas?
2. Además del uso de operadores bitwise, ¿cuáles son algunas de las técnicas de reducción de resistencia que utilizan los compiladores comunes?

Answer 1

1. Creo que muchos compiladores usan SSAPRE (Eliminación de Redundancia Parcial Estática de Asignación Única) para eliminar expresiones repetidas. Esto requiere que el código esté en formulario SSA , lo que permite muchas más optimizaciones.

2. No estoy realmente seguro de esto, pero mira esta lista de pases de LLVM . LLVM es un IR de optimización para compiladores que a menudo es más rápido que incluso GCC. Hay una pequeña explicación de cada pase. Si necesita más información, consulte la fuente de LLVM para estos pases. Está escrito en C ++ pero es bastante limpio y comprensible.

Editar: Por cierto, si estás desarrollando un compilador, te recomiendo encarecidamente LLVM, es muy fácil de usar y genera un código altamente optimizado.

Answer 2

Para 1, el nombre de la optimización que está buscando es la eliminación de subexpresión común (CSE). Dependiendo de su representación, esto puede ser bastante fácil. Generalmente, un compilador tendrá una representación intermedia de un programa donde las operaciones se desglosan tanto como sea posible y se linealizan. Así, por ejemplo, la expresión c = a * b + a * b se puede desglosar como:

v1 = a * b
v2 = a * b
c = v1 + v2

Por lo tanto, podría hacer CSE a un nivel muy bajo buscando operaciones con el mismo operador y operandos. Cuando encuentra un duplicado (v2 en este caso), reemplaza todas las instancias del mismo con el original. Entonces podríamos simplificar el código anterior para que sea:

v1 = a * b
c = v1 + v1

Esto generalmente supone que solo asignas una variable una vez (formulario de asignación estática simple), pero puedes implementar algo como esto sin esa restricción. Esto se vuelve más complicado cuando intenta realizar esta optimización entre sucursales. Como lo menciona Zifre, analice la Eliminación de redundancia parcial.

De cualquier manera, obtienes una mejora básica, y todo lo que necesitas para hacer un seguimiento de las expresiones básicas. Es posible que desee llevar esto un paso más allá y buscar identidades aritméticas. Por ejemplo, a * b es lo mismo que b * a . Además, x * (y + z) = x * y + x * z . Esto hace que su optimización sea más complicada, y no está claro si le daría tanta mejora de rendimiento. Como anécdota, la mayoría de los beneficios de una optimización CSE provienen de los cálculos de direcciones como los accesos de matriz, y no necesitará identidades complicadas como las anteriores.

Para 2, las reducciones de fuerza que son útiles realmente dependen de la arquitectura para la que se compila. Por lo general, esto solo implica transformar las multiplicaciones y divisiones en turnos, sumas y restas.

Answer 3

Recomendaría encarecidamente dos referencias impresas sobre estos temas:

1. Advanced Compiler Design & amp; Implementación por Steven S. Muchnick
2. Creación de un compilador de optimización por Robert Morgan

El libro Muchnick está en el lado formal pero es muy legible y tiene buenas descripciones de todas las técnicas de optimización importantes. El libro de Morgan tiene una sensación mucho más práctica y sería una gran base para un proyecto de compilación centrado en técnicas de optimización. Ninguno de los dos libros tiene mucho que decir sobre el análisis o el análisis léxico, se asume el conocimiento de estos temas.

Answer 4

Para agregar un libro más a la lista de recomendaciones, echa un vistazo a " Hacker's Delight " ; por Henry S. Warren. Es un gran compendio de técnicas para optimizar operaciones comunes, como transformar divisiones enteras en multiplicaciones.

Answer 5

Está buscando eliminación de redundancia parcial (PRE). Tanto el CSE (de las otras respuestas) como el movimiento de código invariante de bucle están incluidos en PRE. (Una variación de PRE es Lazy Code Motion, que creo que es óptima).

Consulte las notas de la conferencia de Keith Cooper , que Parece que describen las técnicas muy bien.

No NO use SSAPRE. AFAIK, esto requiere una forma particular de SSA conocida como HSSA, que tiene algunas desventajas:

• Es bastante complicado
• Requiere una numeración de valores global (por lo que SSAPRE no proporciona una numeración de valores, ya que se espera que ya exista).
• No proporciona nada si su idioma no admite punteros para apilar variables (y si lo hace, deje de escribir su propio análisis y use LLVM o gcc).
• gcc usó HSSA por un tiempo, pero se han alejado de él.
• LLVM experimentó con eso, pero AFAIK ya no lo usan.

EDITAR:

El libro de Muchnick tiene una descripción detallada, está vinculado en otra respuesta.