¿Cuáles son algunos consejos para optimizar el código de ensamblado generado por un compilador?

Question

Actualmente estoy en el proceso de escribir un compiler y parece que me he encontrado con algunos problemas para obtener el código de salida que se ejecuta en un marco de tiempo decente.

Una breve descripción del compilador:

7Basic es un compilador que tiene como objetivo compilar código 7Basic directamente en código máquina para el objetivo de la arquitectura/plataforma. Actualmente, 7Basic genera ensamblaje x86 dado un archivo fuente.

El problema es que el código ensamblador generado por el compilador es lento e ineficiente.

Por ejemplo, el código this (que compila hasta this código de ensamblaje) tarda casi 80,47 veces más en ejecutarse que the equivalent C code.

Parte del problema es que el compilador genera código como el siguiente:

push eax 
push 5000000 
pop ebx 
pop eax 

En lugar de la más lógica:

mov ebx,5000000 

... que lleva a cabo la misma cosa.

Mi pregunta es: ¿cuáles son algunas técnicas para evitar este tipo de problema? El analizador básicamente utiliza recursividad para analizar las expresiones, por lo que el código generado refleja esto.

Answer 1

Una técnica se llama peephole optimisation. Esto requiere un enfoque iterativo para limpiar el código de ensamblaje. Esencialmente escaneas el código del ensamblaje, mirando solo dos o tres instrucciones a la vez, y ver si puedes reducirlos a algo más simple. Por ejemplo,

push eax  ; 1 
push 5000000 ; 2 
pop ebx   ; 3 
pop eax   ; 4 

El primer paso sería mirar a las líneas 2 y 3, y reemplazar eso con:

push eax  ; 1 
mov ebx,5000000 ; 2a 
pop eax   ; 4 

En segundo lugar, es posible considerar 1 y 4, y si eax no se toca en el instrucción media, retire los dos, dejando lo que quiere:

mov ebx,5000000 ; 2a 

Answer 2

Es posible que desee considerar la generación de código C en lugar de montaje y luego dejar que un compilador de C (por ejemplo, gcc) manejar el código g eneración para ti. No tiene sentido tratar de reinventar la rueda.

Answer 3

Hay un número de razones por las cuales un generador de código particular puede emitir la secuencia de instrucciones que usted enumera. Lo más probable es que el generador de código que está utilizando simplemente no intente emitir un código óptimo.

Este patrón de código emitido me sugiere que su generador de código no sabe que el x86 tiene instrucciones "mov inmediata" que incrustan el valor constante en la secuencia de instrucciones directamente. La codificación x86 para los códigos de operación con valores inmediatos puede ser un poco complicada (bytes R/M de longitud variable), pero esto ya es necesario si desea utilizar muchas de las instrucciones x86.

Este código emitido también sugiere que el generador de código no sabe que EAX no está modificado por las instrucciones EBX. Esto parece que el codegen se basa en plantillas y no en lógica discreta.

Este tipo de codegen ocurre cuando la representación de operaciones intermedia interna del compilador no es lo suficientemente detallada como para representar todas las facetas de la arquitectura de destino. Esto es particularmente cierto si la arquitectura del generador de códigos fue originalmente diseñada para un conjunto de instrucciones RISC, pero ha sido reutilizada para emitir instrucciones x86. La arquitectura RISC tiende a tener muy pocas y muy simples instrucciones de carga, almacenamiento y operación reg/reg, mientras que el conjunto de instrucciones x86 ha evolucionado orgánicamente durante décadas para incluir una amplia variedad de códigos de operación que operan directamente en la memoria, constantes en línea en las instrucciones, y todo un lío de otras cosas. Si la representación intermedia del compilador (gráfico de expresión) está cableada para RISC, será difícil hacer que asimile la amplia variedad y sutilezas de x86.

Answer 4

Estoy tomando un curso de compilación en este momento. He logrado un gran progreso en la generación de código eficiente, pero debes buscar en el libro de dragones. Es un rito de paso. Debería echarle un vistazo al código del libro de Jeremy Bennett, Introducción a las técnicas de compilación: Un primer curso usando ANSI C, LEX y YACC. El libro en sí es muy difícil de encontrar, pero puede descargar el código fuente para el compilador libre de

http://www.jeremybennett.com/publications/download.html

El archivo generador de código (cg.c) tiene algunas funciones para generar código optimizado bastante. El idioma de destino no es i386, pero debería considerar observar cómo describe los registros y realizar un seguimiento de dónde se almacenan las entradas de la tabla de símbolos. Su ensamblaje de salida podría optimizarse aún más, pero proporciona una gran base para producir código que podría rivalizar con la salida de gcc -S en algunos aspectos.

Una optimización general sería restar el puntero de la pila para reservar espacio para todas las variables locales y temporales al ingresar una función. Luego solo haga referencia a las compensaciones en lugar de presionar constantemente/hacer estallar.

Por ejemplo, si su código intermedio es una lista de cuádruples, simplemente debe recorrerlo para cada función y realizar un seguimiento de la compensación máxima. Luego imprima la línea para restar la cantidad de espacio en la pila. Esto elimina la necesidad de activar y desactivar tantas variables. Para eliminar la necesidad de abrirlos, simplemente puede mover su valor de su desplazamiento en la pila a un registro. Esto mejorará significativamente el rendimiento.

Answer 5

Las optimizaciones de mirilla ayudarán, pero un problema obvio es que su compilador no registra la asignación.

http://en.wikipedia.org/wiki/Register_allocation

Si desea obtener niveles de rendimiento graves, que estás haciendo a tener que ver en eso. Se puede hacer en un solo paso si lo haces con avidez "sobre la marcha".