Generación y Optimización de Código
La generación y optimización de código traducen representaciones intermedias en código objetivo eficiente, transformando programas para que se ejecuten más rápido o utilicen menos recursos, preservando al mismo tiempo su significado.
Definition
La generación de código es la producción de instrucciones objetivo (código máquina o bytecode) a partir de una representación intermedia, y la optimización es la aplicación de transformaciones que preservan la semántica y que mejoran la velocidad, el tamaño o el uso de recursos de un programa.
Scope
Este tema cubre el back end y el middle end del compilador: representaciones intermedias como la forma de asignación estática única (SSA), el análisis de flujo de datos, las optimizaciones clásicas (propagación de constantes, eliminación de subexpresiones comunes, optimizaciones de bucles), la selección de instrucciones, la planificación de instrucciones y la asignación de registros. Aborda cómo las transformaciones preservan la semántica del programa al tiempo que mejoran el rendimiento.
Core questions
- ¿Cómo pueden las transformaciones de programas mejorar el rendimiento sin cambiar el comportamiento?
- ¿Qué representaciones intermedias hacen eficiente el análisis de optimización?
- ¿Cómo se asignan los registros de máquina limitados a muchos valores de programa?
- ¿Cómo se equilibran la corrección y el rendimiento en una optimización agresiva?
Key theories
- Forma de asignación estática única
- Cytron y sus colegas proporcionaron un algoritmo eficiente para convertir programas a la forma SSA, donde cada variable se asigna una vez, simplificando drásticamente muchas optimizaciones basadas en el flujo de datos.
- Asignación de registros por coloración de grafos
- Chaitin modeló la asignación de registros como una coloración de grafos de un grafo de interferencia, proporcionando el enfoque fundamental para asignar valores de programa a un conjunto limitado de registros de máquina.
- Optimización basada en el flujo de datos
- Muchnick y el Dragon Book formalizan el análisis de flujo de datos como el marco subyacente a las optimizaciones clásicas, calculando las propiedades del programa necesarias para justificar transformaciones seguras.
Clinical relevance
La optimización de la generación de código determina la eficiencia con la que los programas utilizan los procesadores y la memoria, con un amplio impacto en el uso de energía y el costo a escala. La forma SSA y la asignación de registros por coloración de grafos siguen siendo fundamentales para los compiladores de producción y los sistemas just-in-time.
History
La optimización comenzó con el compilador Fortran y maduró a través del análisis de flujo de datos de Allen y Cocke en la década de 1970. La asignación de registros por coloración de grafos de Chaitin en 1981-82 y la construcción eficiente de SSA de Cytron et al. en 1991 se convirtieron en pilares de los compiladores modernos, permitiendo las sofisticadas tuberías de optimización utilizadas en las cadenas de herramientas actuales.
Debates
- Agresividad de la optimización versus corrección y previsibilidad
- Los diseñadores de compiladores debaten cuán agresivamente optimizar, ya que explotar el comportamiento indefinido y la reordenación puede generar velocidad pero introducir resultados sorprendentes o inseguros, lo que impulsa el interés en la optimización verificada y predecible.
Key figures
- Frances Allen
- Gregory Chaitin
- Ron Cytron
- Steven Muchnick
- Alfred Aho
Related topics
Seminal works
- cytron1991
- chaitin1982
- muchnick1997
- aho2006
Frequently asked questions
- ¿Qué es la forma SSA?
- La forma de asignación estática única es una representación intermedia en la que cada variable se asigna exactamente una vez y los usos están vinculados a una única definición, lo que simplifica y fortalece muchas optimizaciones del compilador.
- ¿Por qué es difícil la asignación de registros?
- Los programas suelen utilizar muchos más valores de los que hay registros de máquina, por lo que el compilador debe decidir qué valores comparten registros y cuáles se desbordan a la memoria; el problema central es equivalente a la coloración de grafos, que es computacionalmente difícil en general.