Desarrollar un compilador es una tarea muy difícil. Pero, afortunadamente, con el desarrollo de proyectos como LLVM, la solución a este problema se simplifica enormemente, lo que permite incluso a un solo programador crear un nuevo lenguaje con un rendimiento similar al de C. Trabajar con LLVM se complica por el hecho de que este El sistema está representado por una enorme cantidad de código, equipado con poca documentación. Para intentar corregir esta deficiencia, el autor del material, cuya traducción publicamos hoy, mostrará ejemplos de código escrito en Go y mostrará cómo se traducen por primera vez al , y luego en LLVM IR usando el compilador . El código IR de Go SSA y LLVM se ha editado ligeramente para eliminar elementos que no son relevantes para las explicaciones dadas aquí, a fin de que las explicaciones sean más comprensibles.
Primer ejemplo
La primera función que voy a ver aquí es un mecanismo simple para sumar números:
func myAdd(a, b int) int{
return a + b
}Esta función es muy sencilla y, quizás, nada podría ser más sencillo. Se traduce en el siguiente código Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Con esta vista, las sugerencias de tipos de datos se colocan a la derecha y se pueden ignorar en la mayoría de los casos.
Este pequeño ejemplo ya permite ver la esencia de un aspecto de la SSA. Es decir, al convertir código al formato SSA, cada expresión se descompone en las partes más elementales que la componen. En nuestro caso, el comando return a + b, de hecho, representa dos operaciones: sumar dos números y devolver el resultado.
Además, aquí puedes ver los bloques básicos del programa, en este código solo hay un bloque: el bloque de entrada. Hablaremos más sobre los bloques a continuación.
El código Go SSA se convierte fácilmente a LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Lo que puede notar es que aunque aquí se utilizan diferentes estructuras sintácticas, la estructura de la función básicamente no cambia. El código LLVM IR es un poco más fuerte que el código Go SSA, similar a C. Aquí, en la declaración de la función, primero hay una descripción del tipo de datos que devuelve, el tipo de argumento se indica antes del nombre del argumento. Además, para simplificar el análisis de IR, los nombres de las entidades globales están precedidos por el símbolo @, y antes de los nombres locales hay un símbolo % (una función también se considera una entidad global).
Una cosa a tener en cuenta sobre este código es que la decisión de representación de tipos de Go int, que se puede representar como un valor de 32 o 64 bits, según el compilador y el destino de la compilación, se acepta cuando LLVM genera el código IR. Esta es una de las muchas razones por las que el código IR de LLVM no es, como mucha gente piensa, independiente de la plataforma. Dicho código, creado para una plataforma, no puede simplemente tomarse y compilarse para otra plataforma (a menos que usted sea apto para resolver este problema). ).
Otro punto interesante que vale la pena señalar es que el tipo i64 no es un número entero con signo: es neutral en términos de representar el signo del número. Dependiendo de la instrucción, puede representar números con y sin signo. En el caso de la representación de la operación de suma, esto no importa, por lo que no hay diferencia entre trabajar con números con o sin signo. Aquí me gustaría señalar que en el lenguaje C, desbordar una variable entera con signo conduce a un comportamiento indefinido, por lo que la interfaz de Clang agrega una bandera a la operación. nsw (sin envoltura firmada), que le dice a LLVM que puede asumir que la suma nunca se desborda.
Esto puede ser importante para algunas optimizaciones. Por ejemplo, sumando dos valores i16 en una plataforma de 32 bits (con registros de 32 bits) requiere, después de la adición, una operación de expansión de signos para permanecer dentro del rango i16. Debido a esto, suele ser más eficiente realizar operaciones con números enteros basadas en el tamaño de los registros de la máquina.
Lo que suceda a continuación con este código IR no nos interesa especialmente ahora. El código se optimiza (pero en el caso de un ejemplo simple como el nuestro, no se optimiza nada) y luego se convierte en código de máquina.
Segundo ejemplo
El siguiente ejemplo que veremos será un poco más complicado. Es decir, estamos hablando de una función que suma una porción de números enteros:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Este código se convierte al siguiente código Go SSA:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Aquí ya puedes ver más construcciones típicas para representar código en formato SSA. Quizás la característica más obvia de este código es el hecho de que no existen comandos de control de flujo estructurados. Para controlar el flujo de cálculos, sólo existen saltos condicionales e incondicionales y, si consideramos este comando como un comando para controlar el flujo, un comando de retorno.
De hecho, aquí puede prestar atención al hecho de que el programa no está dividido en bloques mediante llaves (como en la familia de lenguajes C). Está dividido por etiquetas, que recuerdan a los lenguajes ensambladores, y se presenta en forma de bloques básicos. En SSA, los bloques básicos se definen como secuencias contiguas de código que comienzan con una etiqueta y terminan con instrucciones básicas para completar el bloque, como: return и jump.
Otro detalle interesante de este código está representado por la instrucción phi. Las instrucciones son bastante inusuales y puede llevar algún tiempo comprenderlas. recuerda eso es la abreviatura de Asignación única estática. Esta es una representación intermedia del código utilizado por los compiladores, en el que a cada variable se le asigna un valor solo una vez. Esto es genial para expresar funciones simples como nuestra función. myAddse muestra arriba, pero no es adecuado para funciones más complejas como la función analizada en esta sección sum. En particular, las variables cambian durante la ejecución del bucle. i и n.
SSA evita la restricción de asignar valores variables una vez mediante la llamada instrucción phi (su nombre está tomado del alfabeto griego). El caso es que para que se genere la representación SSA del código para lenguajes como C, hay que recurrir a algunos trucos. El resultado de llamar a esta instrucción es el valor actual de la variable (i o n), y se utiliza una lista de bloques básicos como parámetros. Por ejemplo, considere esta instrucción:
t0 = phi [entry: 0:int, for.body: t6] #n
Su significado es el siguiente: si el bloque básico anterior era un bloque entry (entrada), entonces t0 es una constante 0, y si el bloque básico anterior era for.body, entonces necesitas tomar el valor t6 de este bloque. Todo esto puede parecer bastante misterioso, pero este mecanismo es lo que hace que la SSA funcione. Desde una perspectiva humana, todo esto hace que el código sea difícil de entender, pero el hecho de que cada valor se asigne solo una vez hace que muchas optimizaciones sean mucho más fáciles.
Tenga en cuenta que si escribe su propio compilador, normalmente no tendrá que lidiar con este tipo de cosas. Incluso Clang no genera todas estas instrucciones. phi, utiliza un mecanismo alloca (se parece a trabajar con variables locales ordinarias). Luego, cuando se ejecuta un pase de optimización LLVM llamado , instrucciones alloca convertido al formulario SSA. TinyGo, sin embargo, recibe información de Go SSA, que, convenientemente, ya está convertida al formato SSA.
Otra innovación del fragmento de código intermedio considerado es que el acceso a los elementos de corte por índice se representa en forma de una operación de cálculo de la dirección y una operación de desreferenciación del puntero resultante. Aqui puede ver la adicion directa de constantes al codigo IR (por ejemplo - 1:int). En el ejemplo con la función myAdd esto no se ha utilizado. Ahora que hemos eliminado esas características, echemos un vistazo a en qué se convierte este código cuando se convierte al formato LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
}
Aquí, como antes, podemos ver la misma estructura, que incluye otras estructuras sintácticas. Por ejemplo, en llamadas phi valores y etiquetas intercambiados. Sin embargo, hay algo aquí a lo que merece la pena prestar especial atención.
Para empezar, aquí puede ver una firma de función completamente diferente. LLVM no admite sectores y, como resultado, como optimización, el compilador TinyGo que generó este código intermedio dividió la descripción de esta estructura de datos en partes. Podría representar tres elementos de corte (ptr, len и cap) como una estructura (struct), pero representarlos como tres entidades separadas permite algunas optimizaciones. Otros compiladores pueden representar el segmento de otras maneras, dependiendo de las convenciones de llamada de las funciones de la plataforma de destino.
Otra característica interesante de este código es el uso de la instrucción getelementptr (a menudo abreviado como GEP).
Esta instrucción funciona con punteros y se utiliza para obtener un puntero a un elemento de sector. Por ejemplo, comparémoslo con el siguiente código escrito en C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}O con el siguiente equivalente a esto:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
Lo más importante aquí es que las instrucciones getelementptr no realiza operaciones de desreferenciación. Simplemente calcula un nuevo puntero basado en el existente. Se puede tomar como instrucciones. mul и add a nivel de hardware. Puedes leer más sobre las instrucciones GEP. .
Otra característica interesante de este código intermedio es el uso de la instrucción icmp. Esta es una instrucción de propósito general que se utiliza para implementar comparaciones de números enteros. El resultado de esta instrucción es siempre un valor de tipo i1 — valor lógico. En este caso, se realiza una comparación utilizando la palabra clave slt (con signo menor que), ya que estamos comparando dos números previamente representados por el tipo int. Si estuviéramos comparando dos enteros sin signo, entonces usaríamos icmp, y la palabra clave utilizada en la comparación sería ult. Para comparar números de coma flotante, se utiliza otra instrucción, fcmp, que funciona de manera similar.
resultados
Creo que en este material he cubierto las características más importantes de LLVM IR. Por supuesto, hay mucho más aquí. En particular, la representación intermedia del código puede contener muchas anotaciones que permiten que los pasos de optimización tengan en cuenta ciertas características del código conocidas por el compilador que de otro modo no se pueden expresar en IR. Por ejemplo, esta es una bandera. inbounds Instrucciones o banderas de GEP nsw и nuw, que se puede agregar a las instrucciones add. Lo mismo ocurre con la palabra clave private, indicando al optimizador que no se hará referencia a la función que marca desde fuera de la unidad de compilación actual. Esto permite muchas optimizaciones interprocedimientos interesantes, como la eliminación de argumentos no utilizados.
Puede leer más sobre LLVM en , al que hará referencia con frecuencia cuando desarrolle su propio compilador basado en LLVM. Aquí , que busca desarrollar un compilador para un lenguaje muy simple. Ambas fuentes de información le resultarán útiles a la hora de crear su propio compilador.
Estimados lectores! ¿Estás usando LLVM?
Fuente: habr.com