El desarrollo del 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 que incluso un solo programador cree un nuevo lenguaje cercano al rendimiento C. El trabajo con LLVM se complica por el hecho de que este sistema está representado por una gran cantidad de código, equipado con una pequeña documentación. Para intentar corregir esta falla, el autor del material que publicamos hoy demostrará ejemplos de código escrito en Go y mostrará cómo se traducen primero a
Go SSA y luego a LLVM IR usando el compilador
TinyGO . El código IR SSA y LLVM de Go ha sido ligeramente editado; algo que no es relevante para las explicaciones dadas aquí se ha eliminado para que estas explicaciones sean más comprensibles.
Primer ejemplo
La primera función que analizaré aquí es un mecanismo simple para agregar números:
func myAdd(a, b int) int{ return a + b }
Esta función es muy simple y, tal vez, nada es más fácil de inventar. Se traduce al siguiente código Go SSA:
func myAdd(a int, b int) int: entry: t0 = a + b int return t0
Con esta representación de la función, las sugerencias sobre los tipos de datos se colocan a la derecha, en la mayoría de los casos puede ignorarlas.
Este pequeño ejemplo ya le permite ver la esencia de un aspecto de SSA. Es decir, al convertir el código a la forma SSA, cada expresión se divide en las partes más elementales en las que consiste. En nuestro caso, el comando
return a + b , de hecho, representa dos operaciones: sumar dos números y devolver el resultado.
Además, aquí puede ver los bloques básicos del programa, en este código solo hay un bloque: la entrada (bloque de entrada). Hablaremos más sobre los bloques a continuación.
El código Go SSA se puede convertir fácilmente a LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 }
Puede notar que aunque aquí se usan otras construcciones sintácticas, la estructura de la función básicamente no ha cambiado. El código IR LLVM es ligeramente más fuerte que el código Go SSA, similar a C. Aquí, en la declaración de la función, primero viene una descripción del tipo de datos devuelto, el tipo del argumento se indica antes del nombre del argumento. Además, para simplificar el análisis IR, los nombres de las entidades globales están precedidos por el símbolo
@ , y antes de los nombres de las entidades locales por el carácter
% (la función también se considera una entidad global).
Una de las características de este código a las que debe prestar atención es que la decisión de representar el tipo Go
int , que puede representarse mediante un valor de 32 bits o 64 bits, según el compilador y el propósito de la compilación, se toma al crear LLVM Código IR Esta es una de las muchas razones por las que el código IR LLVM no es independiente de la plataforma. Dicho código creado para una plataforma no puede simplemente tomarse y compilarse para otra plataforma (a menos que aborde esta tarea
con extrema precaución ).
Otro punto interesante que vale la pena señalar es que el tipo
i64 no es un entero con signo: es neutral en términos de representar el signo del número. Dependiendo de la instrucción, puede representar tanto números con signo como números sin signo. En el caso de representar la operación de suma, esto no juega un papel, por lo que no hay diferencia en trabajar con números con o sin signo. Aquí, me gustaría señalar que en C, el desbordamiento de una variable entera con signo lleva a un comportamiento indefinido, por lo tanto, la interfaz de Clang agrega el indicador
nsw (sin envoltura firmada) a la operación, lo que indica a LLVM que puede proceder de la suposición de que con Además nunca se produce desbordamiento.
Esto puede ser importante para algunas optimizaciones. Por ejemplo, la adición de dos valores de
i16 en una plataforma de 32 bits (con registros de 32 bits) requiere, una vez completada la adición, que la operación de extensión de signo permanezca en el rango de
i16 . Debido a esto, a menudo es más eficiente realizar operaciones enteras teniendo en cuenta el tamaño de la máquina del registro.
Lo que sucede en el futuro con este código IR no es particularmente interesante para nosotros ahora. El código está optimizado (pero en el caso de un ejemplo tan simple como el nuestro, nada ya está optimizado), y luego se convierte en código de máquina.
Segundo ejemplo
El siguiente ejemplo, que examinaremos, será un poco más complicado. Es decir, estamos hablando de una función que suma la porción de 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 t0
Aquí ya puede ver más construcciones específicas para la presentación de código en forma de SSA. Probablemente la característica más obvia de este código es el hecho de que no hay comandos de control de flujo estructurados. Para controlar el flujo de los cálculos, solo hay 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 usando llaves (como en los lenguajes de la familia C). Está dividido por etiquetas, que se asemeja a los lenguajes de ensamblaje, y se presenta en forma de bloques base. En SSA, los bloques base son secuencias contiguas de código que comienzan con una etiqueta y terminan con instrucciones para completar el bloque base, por ejemplo,
return y
jump .
Otro detalle interesante de este código es la instrucción
phi . La instrucción es bastante inusual, puede tomar algún tiempo resolverlo. Recuerde que
SSA es la abreviatura de asignación estática individual. Esta es una representación intermedia del código utilizado por los compiladores, en el que cada variable se asigna solo una vez. Esto es excelente para expresar funciones simples como nuestra función
myAdd que se muestra arriba, pero no para funciones más complejas como la función de
sum discutida en esta sección. En particular, durante la ejecución del bucle, las variables
i y
n cambian.
SSA omite la restricción en una sola asignación de valores variables usando la llamada instrucción
phi (su nombre se toma del alfabeto griego). El hecho es que para que la representación SSA del código pueda formarse para lenguajes como C, debe 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 base como sus 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 base anterior era un bloque de
entry (entrada), entonces
t0 es constante
0 , y si el bloque base anterior era
for.body , entonces debe tomar el valor
t6 de este bloque. Todo esto puede parecer bastante misterioso, pero gracias a este mecanismo, la SSA está asegurada. Desde el punto de vista humano, todo esto complica la comprensión del código, pero el hecho de que cada valor se asigne solo una vez simplifica enormemente muchas optimizaciones.
Tenga en cuenta que si está escribiendo su propio compilador, generalmente no tiene que lidiar con tales cosas. Incluso Clang no genera todas estas instrucciones de
phi , usa el mecanismo de
alloca (se parece a trabajar con variables locales ordinarias). Luego, al realizar un pase de optimización de LLVM, llamado
mem2reg , las instrucciones de
alloca se convierten al formulario SSA. Sin embargo, TinyGo recibe información de Go SSA, que, convenientemente, ya se ha convertido al formulario SSA.
Otra innovación de este fragmento de código intermedio es que el acceso a los elementos del segmento por índice se presenta en la forma de la operación de cálculo de la dirección y la operación de desreferenciación del puntero obtenido. Aquí puede ver la adición directa de constantes al código IR (por ejemplo,
1:int ). En el ejemplo con la función
myAdd esto no se usó. Ahora que hemos descubierto estas características, veremos en qué se convertirá este código al convertirlo al formulario IR LLVM:
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 construcciones sintácticas. Por ejemplo, en llamadas
phi , se intercambian valores y etiquetas. Sin embargo, también hay algo a lo que vale la pena prestar especial atención.
Para empezar, aquí puede ver una firma completamente diferente de la función. LLVM no admite cortes, como resultado, en forma de 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 y
cap ) como una estructura (estructura), pero presentarlos como tres entidades separadas permite algunas optimizaciones. Otros compiladores pueden presentar el segmento de alguna otra manera, depende de las convenciones para llamar a las funciones de la plataforma de destino.
Otra característica interesante de este código es el uso de la
getelementptr (a menudo llamada GEP para abreviar).
Esta instrucción funciona con punteros y se usa para obtener un puntero a un elemento de división. 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 la instrucción
getelementptr no realiza operaciones de desreferenciación. Solo calcula un nuevo puntero basado en el existente. Se puede interpretar como
mul y
add a nivel de hardware. Los detalles sobre las instrucciones de GEP se pueden encontrar
aquí .
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 utilizada para implementar comparaciones de enteros. El resultado de esta instrucción es siempre un valor de tipo
i1 , un valor lógico. En este caso, se realiza una comparación usando la palabra clave
slt (con signo menor que), ya que estamos comparando dos números representados previamente por el tipo
int . Si tuviéramos que comparar dos enteros sin signo, entonces
icmp como una instrucción, 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.
Resumen
Creo que en este artículo examiné las características más importantes de LLVM IR. Por supuesto, todavía hay muchas cosas. En particular, la representación intermedia del código puede contener muchas anotaciones, lo que permite tener en cuenta ciertas características de optimización conocidas por el compilador durante los pases de optimización que no pueden expresarse en IR de ninguna otra manera. Por ejemplo, estos son los
inbounds de la instrucción
inbounds , o los
nuw nsw y
nuw , que se pueden agregar a la instrucción
add . Lo mismo se aplica a la palabra clave
private , que indica al optimizador que la función marcada por él no será referenciada desde fuera de la unidad de compilación actual. Esto le permite realizar muchas optimizaciones interprocedurales interesantes, como eliminar argumentos no utilizados.
Puede leer más sobre LLVM en la
documentación , a la que a menudo se referirá cuando desarrolle su propio compilador basado en LLVM. Aquí hay una
guía que analiza el desarrollo del compilador para un lenguaje muy simple. Ambas fuentes de información serán útiles al crear su propio compilador.
Estimados lectores! ¿Usas LLVM?