Superoptimización

La superoptimización es el proceso mediante el cual un compilador encuentra automáticamente la secuencia óptima de instrucciones sin bucles. Los compiladores del mundo real generalmente no pueden producir código verdaderamente óptimo , y si bien la mayoría de las optimizaciones estándar solo mejoran el código parcialmente, el objetivo de un superoptimizador es encontrar la secuencia óptima, la forma canónica . Los superoptimizadores pueden usarse para mejorar los optimizadores convencionales al resaltar las oportunidades perdidas para que un humano pueda escribir reglas adicionales.

El término superoptimización fue acuñado por Alexia Massalin en el artículo de 1987 «Superoptimizer: A Look at the Smallest Program» ^{[ 1 ]} . La etiqueta «optimización de programas» se ha aplicado a un campo que no aspira a optimizar, sino solo a mejorar. Esta denominación errónea obligó a Massalin a llamar a su sistema superoptimizador, que en realidad es un optimizador para encontrar un programa óptimo ^{[ 2 ] .}

En 1992, se desarrolló el Superoptimizador GNU (GSO) para integrarse en la Colección de Compiladores GNU (GCC). ^{[ 3 ] [ 4 ]} Posteriormente, se desarrollaron y ampliaron estas ideas.

Tradicionalmente, la superoptimización se realiza mediante una búsqueda exhaustiva por fuerza bruta en el espacio de secuencias de instrucciones válidas. Este método es costoso y, en gran medida, poco práctico para compiladores de propósito general. Sin embargo, se ha demostrado su utilidad para optimizar bucles internos críticos para el rendimiento. También es posible utilizar un solucionador SMT para abordar el problema, lo que mejora enormemente la eficiencia de la búsqueda (aunque las entradas más complejas que un bloque básico siguen estando fuera de su alcance). ^{[ 5 ]}

En 2001, Compaq Research demostró la superoptimización dirigida por objetivos en el proyecto Denali. ^{[ 6 ]} En 2006, se aplicó la programación declarativa de conjuntos de respuestas a la superoptimización en el proyecto TOAST ( Total Optimisation using Answer Set Technology ) ^{[ 7 ]} en la Universidad de Bath . ^{[ 8 ] [ 9 ]}

La superoptimización puede utilizarse para generar automáticamente optimizadores de mirilla de propósito general . ^{[ 10 ]}

Existen varios superoptimizadores disponibles para su descarga gratuita.

• Para la familia de conjuntos de instrucciones x86:
  • Superoptimizador GNU (superopt) ^{[ 11 ]} (GSO) (1992) ^{[ 3 ] [ 4 ]} – también admite muchas otras ISA
  • STOKE, ^{[ 12 ]} un optimizador estocástico ^{[ 13 ]} para el lenguaje ensamblador x86-64 x86 .
• Para ARM:
  • Superoptimizador ilimitado, ^{[ 5 ]} transformando LLVM IR en lenguaje ensamblador ARMv7-A
• Para sistemas embebidos:
  • SuperOptimizador de microcontrolador PIC (2003) ^{[ 14 ] [ 15 ]}
  • Un estudio de viabilidad realizado por Embecosm (2014) para AVR , basado en GSO ^{[ 16 ] [ 17 ]}
• Para la JVM:
  • Superoptimizador de Clojure para la máquina virtual de Java (2012) ^{[ 18 ]}
• Para LLVM IR:
  • souper ^{[ 19 ]} superoptimizador para programas en el lenguaje intermedio LLVM .
• Para WebAssembly
  • slumps ^{[ 20 ]} proporciona superoptimización para programas WASM basados ​​en souper.

• Optimización de mirillas
• Eliminación de código muerto
• Metacompilación