La optimización de mirilla es una técnica de optimización realizada en un pequeño conjunto de instrucciones generadas por el compilador; el pequeño conjunto se conoce como mirilla o ventana. [1]
La optimización de mirilla implica cambiar el pequeño conjunto de instrucciones a un conjunto equivalente que tenga un mejor rendimiento.
Por ejemplo:
- en lugar de empujar el registro A a la pila y luego volver a colocar inmediatamente el valor en el registro A, una optimización de mirilla eliminaría ambas instrucciones;
- en lugar de agregar A a A, una optimización de mirilla podría hacer un desplazamiento aritmético a la izquierda;
- en lugar de multiplicar un registro de coma flotante por 8, una optimización de mirilla podría escalar el exponente del registro de coma flotante por 3; y
- en lugar de multiplicar un índice por 4, agregar el resultado a una dirección base para obtener un valor de puntero y luego desreferenciar el puntero, una optimización de mirilla podría usar un modo de direccionamiento de hardware que logra el mismo resultado con una instrucción.
El término optimización de mirilla fue introducido por William Marshall McKeeman en 1965. [2]
Reglas de reemplazo
Técnicas comunes aplicadas en la optimización de mirillas: [3]
- Secuencias nulas: elimine las operaciones inútiles.
- Combinar operaciones: reemplace varias operaciones por una equivalente.
- Leyes algebraicas: use leyes algebraicas para simplificar o reordenar las instrucciones.
- Instrucciones de casos especiales: use las instrucciones diseñadas para casos de operandos especiales.
- Operaciones del modo de dirección: utilice los modos de dirección para simplificar el código.
Puede haber otros tipos de optimizaciones de mirilla.
Ejemplos de
Reemplazo de instrucciones lentas por otras más rápidas
El siguiente código de bytes de Java
...aload 1aload 1mul...
puede ser reemplazado por
...aload 1dupmul...
Este tipo de optimización, como la mayoría de las optimizaciones de mirilla, hace ciertas suposiciones sobre la eficiencia de las instrucciones. Por ejemplo, en este caso, se supone que la dup
operación (que duplica y empuja la parte superior de la pila ) es más eficiente que la aload X
operación (que carga una variable local identificada como X
y la empuja a la pila).
Eliminando código redundante
Otro ejemplo es eliminar los almacenes de carga redundantes.
a = b + c; d = a + e;
se implementa directamente como
MOV b , R0 ; Copie b al registro ADD c , R0 ; Agregue c al registro, el registro ahora es b + c MOV R0 , a ; Copie el registro en un MOV a , R0 ; Copie a al registro ADD e , R0 ; Agregue e al registro, el registro ahora es a + e [(b + c) + e] MOV R0 , d ; Copie el registro a d
pero se puede optimizar para
MOV b , R0 ; Copie b al registro ADD c , R0 ; Agregue c al registro, que ahora es b + c (a) MOV R0 , a ; Copie el registro en un ADD e , R0 ; Agregue e al registro, que ahora es b + c + e [(a) + e] MOV R0 , d ; Copie el registro a d
Eliminación de instrucciones de pila redundantes
Si el compilador guarda registros en la pila antes de llamar a una subrutina y los restaura al regresar, las llamadas consecutivas a subrutinas pueden tener instrucciones de pila redundantes.
Suponga que el compilador genera las siguientes instrucciones Z80 para cada llamada a procedimiento:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR POP HL POP DE POP BC POP AF
Si hubiera dos llamadas de subrutinas consecutivas, se verían así:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 POP HL POP DE POP BC POP AF PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR2 POP HL POP DE POP BC POP AF
La secuencia de registros POP seguida de PUSH para los mismos registros es generalmente redundante. En los casos en que sea redundante, una optimización de mirilla eliminaría estas instrucciones. En el ejemplo, esto haría que apareciera otro par POP / PUSH redundante en la mirilla, y estos serían eliminados a su vez. Suponiendo que la subrutina _ADDR2 no depende de los valores de registro anteriores, eliminar todo el código redundante en el ejemplo anterior eventualmente dejaría el siguiente código:
PUSH AF PUSH BC PUSH DE PUSH HL CALL _ADDR1 CALL _ADDR2 POP HL POP DE POP BC POP AF
Implementación
Los compiladores modernos a menudo implementan optimizaciones de mirilla con un algoritmo de coincidencia de patrones . [4]
Ver también
- Optimizadores de código de objeto , discusión en relación con la eficiencia algorítmica general
- Capex Corporation : produjo el optimizador COBOL , uno de los primeros optimizadores de código de objetos de mainframe para IBM Cobol.
- Superoptimización
- Digital Research XLT86 , un compilador de fuente a fuente de ensamblado optimizado
Referencias
- ↑ Muchnick, Steven Stanley (15 de agosto de 1997). Diseño e implementación de compiladores avanzados . Prensa académica / Morgan Kaufmann . ISBN 978-1-55860-320-2.
- ^ McKeeman, William Marshall (julio de 1965). "Optimización de mirillas". Comunicaciones de la ACM . 8 (7): 443–444. doi : 10.1145 / 364995.365000 .
- ^ Fischer, Charles N .; Cytron, Ron K .; LeBlanc, Jr., Richard J. (2010). Elaboración de un compilador (PDF) . Addison-Wesley . ISBN 978-0-13-606705-4. Archivado desde el original (PDF) el 2018-07-03 . Consultado el 2 de julio de 2018 .
- ^ Aho, Alfred Vaino ; Lam, Monica Sin-Ling ; Sethi, Ravi ; Ullman, Jeffrey David (2007). "Capítulo 8.9.2 Generación de código mediante mosaico de un árbol de entrada". Compiladores: principios, técnicas y herramientas (PDF) (2 ed.). Educación de Pearson . pag. 540. Archivado (PDF) desde el original el 10 de junio de 2018 . Consultado el 2 de julio de 2018 .
enlaces externos
La definición del diccionario de optimización de mirilla en Wikcionario