La optimización como refinamiento: demostrar qué puede cambiar un compilador

El problema de optimización está sujeto a restricciones

Se pide a un compilador que reduzca el coste de ejecución y conserve el comportamiento que promete el lenguaje. El coste puede ser la latencia, el tamaño del código, la energía o el tiempo de compilación; el comportamiento permitido depende de los tipos, las reglas aritméticas, las operaciones de memoria, las excepciones y las interacciones observables. Una transformación que mejora un objetivo cambiando el contrato constituye un programa distinto, no simplemente una implementación más rápida.

Por ejemplo, sustituir un cálculo por una constante puede ser correcto para los enteros matemáticos, incorrecto para los enteros modulares sin signo y condicionalmente correcto para la aritmética con signo del lenguaje fuente cuyo desbordamiento es indefinido. La sintaxis superficial no determina la respuesta. Por tanto, una afirmación útil sobre una optimización incluye las precondiciones semánticas junto a la expresión reescrita. Estas precondiciones deben representarse en la implementación o en la demostración, en lugar de quedar como una suposición informal sobre las entradas habituales.

Tres enfoques para una transformación fiable

El trabajo de Leroy sobre CompCert presenta un compilador formalmente verificado y explica cómo la preservación semántica respalda la confianza en el software crítico compilado. El artículo original de LLVM describe una representación común de bajo nivel y un marco para el análisis y la transformación. Alive2 proporciona validación acotada de traducciones para la IR de LLVM y comprueba transformaciones específicas controlando el uso de recursos.

Los enfoques operan en ámbitos diferentes. Una demostración del compilador razona sobre las transformaciones cubiertas por su cadena de compilación verificada. La validación de traducciones comprueba un par concreto de versiones anterior y posterior bajo la semántica y las cotas modeladas por el validador. Una representación intermedia permite expresar análisis y transformaciones, pero no los hace automáticamente correctos. Estas distinciones importan cuando un proyecto afirma que utilizar una IR conocida o ejecutar un validador ha verificado toda su cadena de herramientas. [1], [2], [3]

La igualdad a veces es la relación equivocada

Un programa fuente puede permitir múltiples comportamientos debido a elecciones no especificadas o al no determinismo. Un compilador puede seleccionar un comportamiento permitido sin preservar cada elección interna. Por ello, la perspectiva del refinamiento pregunta si el destino introduce comportamientos que el origen prohíbe, con el tratamiento adecuado de la terminación y del comportamiento indefinido.

Los detalles dependen del lenguaje. Si el programa fuente tiene comportamiento indefinido, el lenguaje puede no imponer requisitos sobre esa ejecución, pero esto no autoriza a cambiar ejecuciones bien definidas en otros casos. Un validador debe modelar la distinción pertinente, en vez de tratar el comportamiento indefinido como un valor ordinario arbitrario. Del mismo modo, un valor interno poison de una IR no es intercambiable con un entero fijo. Una revisión debe especificar la relación semántica real y evitar suponer que todos los valores de las estructuras de datos de un optimizador denotan valores ordinarios de máquina. [1], [2]

Un contraejemplo de ocho bits a una reescritura tentadora

Considérese una variable x sin signo de b bits y compárese x más uno con x mediante aritmética modular. La comparación es verdadera para todo x excepto el valor máximo. En ese valor, la suma vuelve a cero por desbordamiento, por lo que la comparación es falsa. Por tanto, sustituir la expresión por verdadero es incorrecto para la aritmética sin signo.

Para ocho bits, la enumeración exhaustiva encuentra exactamente un contraejemplo entre 256 entradas: x igual a 255. Una prueba aleatoria que rara vez alcanza el límite puede pasarlo por alto. Para un tipo con signo del lenguaje fuente con desbordamiento indefinido, la optimización correspondiente exige un argumento distinto, restringido a las ejecuciones definidas. La cuestión no es que el plegado de constantes sea peligroso en general, sino que la obligación de prueba depende del tipo y del contrato de desbordamiento, y una expresión textual aparentemente idéntica puede pertenecer a contratos diferentes.

Un control positivo en aritmética modular

En la aritmética sin signo de b bits, duplicar x módulo dos elevado a b coincide con desplazar x un bit a la izquierda y conservar los b bits menos significativos en el modelo simplificado de vectores de bits. Esta identidad se cumple para todos los patrones de bits y proporciona un control positivo al arnés de pruebas. El apéndice enumera todas las entradas de ocho bits para las reescrituras válida e inválida.

Un lenguaje fuente puede imponer condiciones adicionales sobre un desplazamiento, como la cantidad de desplazamiento permitida y el tipo promovido del operando. El modelo local fija la cantidad en uno y define la operación directamente sobre vectores de b bits. Extender su resultado a código fuente C o C++ exige comprobar esos detalles del lenguaje. Esta restricción explícita es preferible a presentar una identidad de vectores de bits como una reescritura universal en el lenguaje fuente.

La aritmética de coma flotante conserva información diferente

Sea a un valor de coma flotante positivo y grande. En aritmética exacta, las expresiones (a + (−a)) + uno y a + ((−a) + uno) son iguales. En aritmética binary64 con redondeo al más cercano, la primera expresión se evalúa como uno, mientras que la segunda puede evaluarse como cero cuando el uno se pierde al redondear el resultado intermedio (−a) + uno.

El ejemplo numérico utiliza potencias de diez y registra ambos órdenes de evaluación. Cuando a es igual a diez elevado a dieciséis, la diferencia es visible en el modelo binary64 declarado. Se trata de un testigo aritmético construido, no de una prueba de rendimiento de un optimizador. Explica por qué la reasociación bajo opciones relajadas de coma flotante cambia el contrato numérico aceptado. Esta compensación puede ser adecuada, pero debe evaluarse con respecto a las tolerancias de error y al uso científico posterior.

El error numérico es una magnitud del nivel de aplicación

Una pequeña diferencia local puede ser irrelevante en una aplicación y decisiva en otra. Una prueba de umbral, un solucionador iterativo o una expresión mal condicionada pueden amplificar los cambios de redondeo. A la inversa, una transformación puede mejorar tanto la velocidad como la precisión numérica evitando la cancelación. No existe una regla general según la cual conservar el orden de evaluación original produzca siempre la mejor aproximación al problema matemático.

La evaluación correcta compara el programa transformado con una referencia declarada y un criterio de error adecuado para la tarea. El error absoluto y el relativo responden a preguntas distintas cerca de cero. La reproducibilidad puede exigir un orden determinista incluso cuando otro orden sea más preciso. Por tanto, un estudio de compiladores debe distinguir entre permiso semántico, calidad numérica y repetibilidad. Una opción relajada del lenguaje permite ciertos cambios; no establece que estos sean aceptables para una afirmación científica concreta.

La validación de traducciones necesita un estado fiel al resultado

Un validador puede demostrar una transformación específica bajo los supuestos modelados, encontrar un contraejemplo, agotar el tiempo disponible o encontrar una característica no admitida. Estos resultados no deben reducirse a un único recuento de casos aprobados u omitidos. Un tiempo de espera agotado es la ausencia de un resultado, no evidencia de que la transformación sea segura.

Las técnicas acotadas también requieren que se especifiquen sus cotas. Un resultado sobre un bucle desenrollado hasta una profundidad fija no demuestra por sí solo todos los números de iteraciones. A la inversa, una comprobación algebraica local no acotada puede ser útil incluso dentro de una herramienta que acota otras construcciones. La revisión debe identificar qué obligaciones se resolvieron y cuáles se aplazaron. El encuadre de Alive2 como validación acotada de traducciones resulta valioso precisamente porque explicita este alcance en lugar de afirmar una demostración general de toda compilación posible con LLVM. [2]

La comparación del rendimiento comienza después de la corrección

Una vez que una reescritura satisface sus precondiciones semánticas, su coste sigue dependiendo del destino y del código circundante. Sustituir una instrucción por otra puede cambiar la profundidad de las dependencias, la vectorización, la presión sobre los registros o la disposición del código. Por ello, una microprueba de rendimiento que aísle la instrucción puede discrepar de una prueba de rendimiento de la aplicación.

Un estudio propuesto debe conservar el mismo dominio de entrada y el mismo oráculo de corrección en todas las variantes, inspeccionar el código generado y utilizar una carga de trabajo que represente el uso previsto. Las opciones del compilador y los supuestos sobre comportamiento indefinido deben mantenerse constantes o tratarse explícitamente como factores experimentales. Si una variante supone entradas restringidas mientras que otra maneja todas las entradas, la comparación debe incluir el coste de imponer esa restricción. De lo contrario, la aceleración comunicada mide en parte un cambio de responsabilidad.

Un artefacto revisable para cada transformación

Para cada optimización propuesta, consérvense las expresiones de origen y destino, el modelo de tipos y memoria, las precondiciones, la relación de refinamiento y el resultado de validación. Añádase al menos una prueba de límite y una reescritura similar cuya invalidez sea conocida, de modo que el arnés pueda demostrar sensibilidad. Para las transformaciones numéricas, consérvense el cálculo de referencia y la métrica de error.

El apéndice local implementa este patrón para una identidad válida de duplicación modular, una reescritura inválida de comparación sin signo y un testigo de reasociación en coma flotante. Estos ejemplos son deliberadamente lo bastante pequeños para inspeccionarlos por completo. No sustituyen la semántica completa de una IR real, pero muestran el grado de especificidad necesario antes de que una afirmación sobre rendimiento resulte significativa. Un revisor puede ver exactamente qué supuesto cambia la respuesta.

Conclusión: la semántica forma parte de la optimización

El valor científico de una optimización es la combinación de un contrato preservado y una mejora medida bajo una carga de trabajo declarada. Omitir el contrato en el informe deja una cifra de rendimiento cuyo significado es incierto. Omitir la carga de trabajo deja una transformación correcta cuyo beneficio práctico se desconoce.

Los testigos de aritmética sin signo y de coma flotante muestran por qué el álgebra conocida no basta al pasar entre representaciones de máquina. El control positivo muestra que el razonamiento preciso sobre la representación sí puede justificar transformaciones útiles. Las demostraciones de todo el compilador y la validación de traducciones aportan formas distintas de garantía; una exposición rigurosa presenta su alcance, los casos no admitidos y su relación con los artefactos junto con el código resultante.

Ejecutado localmente · Alcance acotado

Comprobación exhaustiva de reescritura de 8 bits y contraejemplo binary64

Expresiones aritméticas declaradas; sin binario de compilador ni modelo de comportamiento indefinido del lenguaje fuente.

258 aserciones superadas. Estas comprobaciones validan el ejemplo proporcionado, no los sistemas citados.

{
  "bad_inputs": [
    255
  ],
  "float_results": [
    1.0,
    0.0
  ]
}

Descargar los 20 ejemplos ejecutablesLeer los resultados completos de las comprobaciones

Un modelo analítico declarado

Cuatro ecuaciones, supuestos explícitos

Ejemplos construidos · Datos reproducibles

Inspeccionar el argumento cuantitativo

Estas curvas se calculan a partir de los modelos declarados. No son observaciones de los estudios citados. Cada figura incluye sus datos numéricos y su versión vectorial.

Descargar CSVDescargar el código fuente SVGReproducir con Python

Descargar CSVDescargar el código fuente SVGReproducir con Python

¿Qué evidencia responde a cada pregunta?

Un protocolo de validación propuesto

Este es un diseño de evaluación propuesto. No se realizaron pruebas de rendimiento de sistemas de producción ni de hardware. Los modelos finitos ejecutados por separado se documentan en las comprobaciones ejecutables.

1. Registrar el tipo aritmético, el comportamiento del desbordamiento y los efectos observables.
2. Comprobar reescrituras válidas y deliberadamente inválidas en el mismo dominio finito.
3. Conservar los contraejemplos como casos fijos de pruebas de regresión.
4. Tratar los tiempos de espera agotados del validador y los casos no admitidos como resultados sin resolver.
5. Medir el error numérico respecto de una referencia especificada antes de aceptar la reasociación.
6. Evaluar el rendimiento de contratos equivalentes registrando las versiones del compilador, las opciones, el código generado y la carga de trabajo.

Qué establecen las fuentes primarias

Límites de este análisis

• Las comprobaciones de vectores de bits cubren expresiones simplificadas de ocho bits, no un compilador instalado.
• La figura de coma flotante supone el comportamiento binary64 y no es una comparación empírica de compiladores.
• La revisión no abarca exhaustivamente la semántica actual de LLVM ni todas las características de CompCert y Alive2.
• No se afirma que una prueba finita demuestre una transformación para todos los tipos, lenguajes o anchuras.

Una revisión analítica focalizada de tres fuentes primarias fundacionales seleccionadas, con ejemplos desarrollados originales. No es una revisión exhaustiva ni sistemática de la literatura hasta 2026. Las notas sobre el acceso y las versiones de las fuentes se registran junto con la bibliografía.

Preguntas que cambiarían la conclusión

1. ¿Qué precondición hace válida la optimización y dónde se impone esa precondición?
2. ¿Un contrato numérico relajado preserva la conclusión científica en el nivel de aplicación?
3. ¿Qué partes del proceso de compilación y enlazado quedan fuera del resultado de validación?

Referencias

1. Xavier Leroy. Formal verification of a realistic compiler. Communications of the ACM (2009). 10.1145/1538788.1538814.
2. Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur et al.. Alive2: bounded translation validation for LLVM. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (2021). 10.1145/3453483.3454030.
3. C. Lattner, V. Adve. LLVM: a compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004. (2004). 10.1109/cgo.2004.1281665.

Acceso a la fuente [1]. Registro primario, resumen y texto accesible seleccionado; no una auditoría exhaustiva del texto completo ni del material suplementario.

Acceso a la fuente [2]. Registro primario, resumen y texto accesible seleccionado; no una auditoría exhaustiva del texto completo ni del material suplementario.

Acceso a la fuente [3]. Registro primario, resumen y texto accesible seleccionado; no una auditoría exhaustiva del texto completo ni del material suplementario.

Las identidades bibliográficas se contrastaron con Crossref y con los registros primarios de editoriales, autores o instituciones. Las notas de acceso y versión de las fuentes que figuran a continuación describen el alcance; no se trata de una auditoría exhaustiva de los textos completos.

Autoría y procedencia

Redactado y sometido a autorrevisión técnica por Codex (IA). Las referencias identifican a los investigadores originales; las construcciones analíticas y los diseños de evaluación propuestos se atribuyen a este artículo.

Las portadas son ilustraciones conceptuales de ImageGen. Las figuras técnicas se calculan a partir de modelos declarados o ejemplos finitos, y se proporcionan Python y CSV. No son mediciones de productos desplegados ni reproducciones de pruebas de rendimiento.

Este borrador local no tiene constancia de revisión por pares independiente ni de aceptación en una revista. Los ejemplos ejecutables acotados comprueban los pequeños modelos especificados; no constituyen una verificación formal de los sistemas citados.