La optimización de compiladores es un problema fundamental en la informática, buscando transformar código fuente en binarios eficientes sin alterar su semántica. QBE, un compilador de backend ligero, aborda este desafío centrándose en una Intermediate Language (IL) simple y un modelo de compilación por función. La versión 1.3 se enfoca en cerrar la brecha de rendimiento con compiladores comerciales, especialmente en cargas de trabajo intensivas en CPU, y en mejorar la flexibilidad para la generación de código moderno.
El problema central es cómo aplicar optimizaciones complejas y realizar una selección de instrucciones eficiente en un compilador con recursos limitados y un diseño de 'streaming' por función, que restringe el análisis global. La necesidad de generar código independiente de la posición (PIC) para bibliotecas compartidas añade otra capa de complejidad, requiriendo mecanismos para resolver direcciones de símbolos en tiempo de ejecución.
Arquitectura del Sistema
QBE opera con una Intermediate Language (IL) de bajo nivel, diseñada para ser simple y fácil de optimizar. El proceso de compilación es predominantemente por función, lo que impone ciertas restricciones en optimizaciones que requieren un análisis inter-procedural, como el inlining. La versión 1.3 introduce un nuevo algoritmo de emparejamiento de IL, implementado a través de una herramienta de metaprogramación OCaml llamada mgen.
mgen compila patrones de IL (expresados en un formato 'lispy') en código C idiomático. Este código C se inyecta en el compilador para realizar la selección de instrucciones. El algoritmo de emparejamiento se basa en un enfoque de numeración de árboles, similar al compilador de C de Plan9 de Ken Thompson. Cada nodo en el Directed Acyclic Graph (DAG) de instrucciones se asocia con un bitset que indica qué patrones de usuario de alto nivel coinciden. La selección del patrón más adecuado se realiza mediante lógica manual, y las variables dentro de los patrones son recolectadas por programas generados por mgen en un lenguaje de bytecode simple, interpretado por la función runmatch().
Para el soporte de código independiente de la posición (PIC), QBE 1.3 introduce un nuevo flag DYNCONST en la especificación de IL. Este flag permite el acceso indirecto a globales (como la Global Offset Table en ELF), resolviendo direcciones de símbolos en tiempo de ejecución. El compilador ahora puede generar y enlazar con objetos compartidos, lo que es crucial para la creación de bibliotecas dinámicas.
Flujo de Selección de Instrucciones con mgen
- 1 Definición de Patrones IL Ingeniero define patrones IL 'lispy' en bloques de comentarios.
- 2 Ejecución de mgen Herramienta OCaml `mgen` procesa patrones IL.
- 3 Generación de Código C `mgen` produce código C idiomático para emparejar patrones.
- 4 Compilación QBE QBE compila el código C generado junto con su lógica.
- 5 Emparejamiento DAG IL En tiempo de compilación, se numeran nodos del DAG de IL.
- 6 Asociación Bitset Cada nodo IL se asocia con un bitset de patrones coincidentes.
- 7 Selección de Patrón Lógica manual selecciona el patrón más adecuado.
- 8 Ejecución Matcher Programas de bytecode generados por `mgen` recolectan variables.
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | QBE (compilador) | Backend de compilador para generar código máquina optimizado. vs GCC, LLVM |
| data-processing | OCaml (mgen) | Herramienta de metaprogramación para generar código C a partir de patrones IL. |
Trade-offs
Ganancias
- ▲ Rendimiento del código generado
- ▲ Flexibilidad en selección de instrucciones
- ▲ Soporte para objetos compartidos y PIC
Costes
- △ Complejidad del compilador (introducción de mgen)
- ▲ Incompatibilidad de inlining con modelo de compilación por función
function w $load() { @start %v =w load extern $dlvar ret %v }Fundamentos Teóricos
El algoritmo de emparejamiento de patrones de IL en QBE 1.3, inspirado en el compilador de C de Plan9 de Ken Thompson, se basa en principios de reconocimiento de patrones en grafos. Este enfoque tiene raíces en la teoría de compiladores y la optimización de código, donde la transformación de árboles de sintaxis abstracta (ASTs) o DAGs de IL es fundamental. La idea de numeración de árboles para identificar subexpresiones comunes y aplicar reglas de reescritura es un concepto clásico en la optimización de compiladores, relacionado con técnicas como la Eliminación de Subexpresiones Comunes (CSE).
La generación de código independiente de la posición (PIC) y el manejo de la Global Offset Table (GOT) y la Procedure Linkage Table (PLT) son conceptos bien establecidos en la arquitectura de sistemas operativos y el enlazado dinámico, descritos en profundidad en textos fundamentales sobre diseño de sistemas operativos y compiladores, como 'Compilers: Principles, Techniques, and Tools' de Aho, Sethi y Ullman (conocido como el 'Dragon Book'). La necesidad de resolver símbolos en tiempo de ejecución es una consecuencia directa de la modularidad y el reuso de código en sistemas distribuidos y bibliotecas compartidas.