El desarrollo de un compilador es una tarea muy pesada. Pero, afortunadamente, con el avance de proyectos como LLVM, la solución a este problema se simplifica considerablemente, lo que permite a incluso un programador solitario crear un nuevo lenguaje, cercano en rendimiento al C. Trabajar con LLVM se complica debido a que este sistema está representado por un gran volumen de código, con escasa documentación. Para intentar corregir esta desventaja, el autor del material, cuya traducción publicamos hoy, busca mostrar ejemplos de código escrito en Go y demostrar cómo se transpilan primero a , y luego a LLVM IR utilizando el compilador . El código Go SSA y LLVM IR se ha editado ligeramente, eliminando lo que no está relacionado con las explicaciones ofrecidas aquí, para que estas sean más comprensibles.
Primer ejemplo
La primera función que voy a analizar aquí es un mecanismo simple para sumar números:
func myAdd(a, b int) int{
return a + b
}Esta función es muy simple, y probablemente no hay nada más sencillo. Se transpila al siguiente código Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Con esta representación de la función, las indicaciones sobre los tipos de datos se colocan a la derecha, y en la mayoría de los casos se puede ignorar.
Este pequeño ejemplo ya permite ver la esencia de uno de los aspectos de SSA. A saber, al convertir el código a la forma SSA, cada expresión se descompone en las partes más elementales de las que consta. En nuestro caso, el comando return a + b, en realidad, representa dos operaciones: sumar dos números y devolver el resultado.
Además, aquí se pueden ver los bloques básicos del programa, en este código hay solo un bloque: el bloque de entrada (entry block). Hablaremos más sobre los bloques más adelante.
El código Go SSA se convierte fácilmente en LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Se puede notar que aunque aquí se utilizan otras construcciones sintácticas, la estructura de la función, en general, no ha cambiado. El código LLVM IR es un poco más fuerte que el código Go SSA, y es similar a C. Aquí, en la declaración de la función, primero se indica la descripción del tipo de datos que devuelve, y el tipo del argumento se especifica antes del nombre del argumento. Además, para facilitar el análisis del IR, antes de los nombres de las entidades globales se coloca un símbolo @, y antes de los nombres locales — un símbolo % (la función también se considera una entidad global).
Una de las características de este código, a la que hay que prestar atención, es que la decisión sobre la representación del tipo Go int, que puede presentarse como un valor de 32 bits o 64 bits, dependiendo del compilador y del objetivo de compilación, se toma al crear el código LLVM IR. Este es uno de los muchos motivos por los cuales el código LLVM IR no es, como muchos piensan, independiente de la plataforma. Tal código, creado para una plataforma, no se puede simplemente tomar y compilar para otra plataforma (si no se aborda el problema ).
Otro aspecto interesante a tener en cuenta es que el tipo i64 no es un número entero con signo: es neutral en cuanto a la representación del 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 la operación de suma, esto no importa, por lo que no hay diferencia en el trabajo con números con signo o sin signo. Aquí me gustaría señalar que en el lenguaje C, el desbordamiento de una variable entera con signo conduce a un comportamiento indefinido, por lo que el frontend de Clang agrega a la operación un indicador nsw (no signed wrap), que indica a LLVM que puede asumir que nunca ocurre un desbordamiento al sumar.
Esto puede ser importante para algunas optimizaciones. Por ejemplo, la suma de dos valores i16 en una plataforma de 32 bits (con registros de 32 bits) necesita, después de realizar la suma, una operación de extensión de signo para permanecer dentro del rango i16. Debido a esto, a menudo resulta más eficiente realizar operaciones enteras teniendo en cuenta los tamaños de registro de la máquina.
Lo que sucede después con este código IR no nos interesa particularmente en este momento. El código se optimiza (aunque en un caso tan simple como el nuestro, ya no se optimiza) y luego se convierte a código de máquina.
Segundo ejemplo
El siguiente ejemplo que vamos a considerar será un poco más complicado. En particular, se trata de una función que suma un slice 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 transforma en el siguiente código SSA de Go:
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 se pueden ver más construcciones características de la representación de código en forma SSA. Probablemente, la característica más obvia de este código es el hecho de que no hay comandos estructurados para el control del flujo de cálculo. Para controlar el flujo de cálculo, solo hay saltos condicionales y incondicionales, y si se considera este comando como un comando para controlar el flujo, el comando de retorno.
De hecho, se puede notar que el programa no está dividido en bloques utilizando llaves (como en los lenguajes de la familia C). Se divide en etiquetas, lo que recuerda los lenguajes ensambladores, y se presenta en forma de bloques básicos. En SSA, los bloques básicos son secuencias continuas de código que comienzan con una etiqueta y terminan con instrucciones de finalización del bloque básico, por ejemplo — return y jump.
Otro detalle interesante de este código está representado por la instrucción phi. Esta instrucción es bastante inusual, y puede llevar tiempo entenderla. Recuerde que — es una abreviatura para Static Single Assignment. Esta es una representación intermedia del código utilizada por los compiladores, en la que a cada variable se le asigna un valor solo una vez. Esto es ideal para expresar funciones simples, como nuestra función myAdd, mostrada arriba, pero no es adecuada para funciones más complejas — como la que se considera en esta sección suma. En particular, durante la ejecución de un bucle se cambian las variables i y n.
SSA elude la restricción de asignación única de valores a las variables utilizando la llamada instrucción phi (su nombre proviene del alfabeto griego). La cuestión es que para poder formar una representación SSA del código para lenguajes como C, es necesario recurrir a algunos trucos. El resultado de la llamada a esta instrucción es el valor actual de la variable (i o n), y como sus parámetros se utiliza una lista de bloques básicos. Por ejemplo, consideremos la siguiente instrucción:
t0 = phi [entry: 0:int, for.body: t6] #n Su significado es el siguiente: si el bloque básico anterior fue el bloque entry (de entrada), entonces t0 es una constante 0, y si el bloque básico anterior fue for.body, entonces se debe tomar el valor t6 de ese bloque. Todo esto puede parecer bastante misterioso, pero gracias a este mecanismo se asegura el funcionamiento de SSA. Desde el punto de vista humano, todo esto complica la comprensión del código, pero el hecho de que cada valor se asigna solo una vez simplifica muchas optimizaciones.
Tenga en cuenta que si está escribiendo su propio compilador, generalmente no tendrá que lidiar con cosas así. Incluso Clang no genera todas estas instrucciones phi, utiliza el mecanismo alloca (se asemeja al trabajo con variables locales ordinarias). Luego, durante un pase de optimización de LLVM, llamado , las instrucciones alloca se convierten a la forma SSA. TinyGo, sin embargo, obtiene la entrada de Go SSA, que, cómodamente, ya está convertida a la forma SSA.
Otra novedad del fragmento de código intermedio considerado es que el acceso a elementos de un slice por índice se presenta en forma de operación de cálculo de direcciones y operación de desreferenciación del puntero obtenido. Aquí también se puede ver la adición directa de constantes en el código IR (por ejemplo — 1:int). En el ejemplo con la función myAdd Similar code has not been used before. Now, having understood these features, let's look at how this code will be transformed into LLVM IR:
define i64 @sum(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.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
} Here, as before, we can see the same structure, including other syntactic constructs. For example, in the calls phi the values and labels have switched places. However, there is something here that deserves special attention.
To begin with, we can see a completely different function signature. LLVM does not support slices, so as an optimization, the TinyGo compiler that generated this intermediate code split the description of this data structure into parts. It could have represented the three slice elements (ptr, len y cap) as a structure (struct), but representing them as three separate entities allows for certain optimizations. Other compilers may represent a slice differently; it depends on the calling conventions of the target platform.
Another interesting feature of this code is the use of the instruction getelementptr (commonly abbreviated as GEP).
This instruction works with pointers and is used to obtain a pointer to an element of a slice. For example, let's compare it to the following code written in C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Or to the following, which is equivalent to it:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} The most important point here is that the instruction getelementptr does not perform dereferencing operations. It merely computes a new pointer based on the existing one. It can be viewed like mul y add at the hardware level. You can read more about the GEP instruction .
Another interesting feature of this intermediate code is the use of the instruction icmp. Esta es una instrucción de uso general utilizada para implementar la comparación de números enteros. El resultado de la ejecución de esta instrucción siempre es un valor del tipo i1 — un valor lógico. En este caso, se realiza la comparación utilizando la palabra clave slt (menor que firmado), ya que estamos comparando dos números previamente representados por el tipo int. Si estuviéramos comparando dos números enteros sin signo, entonces usaríamos la instrucción icmp, y la palabra clave utilizada en la comparación sería ult. Para comparar números de punto flotante se utiliza otra instrucción, fcmp, que funciona de manera similar.
Resultados
Considero que en este material he cubierto las características más importantes de LLVM IR. Por supuesto, hay mucho más. En particular, en la representación intermedia del código pueden existir muchas anotaciones que permiten tener en cuenta ciertas características del código durante las optimizaciones, que el compilador conoce y que no se pueden expresar de otra manera en IR. Por ejemplo, esta es la bandera inbounds de la instrucción GEP, o las banderas nsw y nuw, que pueden añadirse a la instrucción add. Lo mismo ocurre con la palabra clave private, que indica al optimizador que la función marcada no será referenciada desde fuera de la unidad de compilación actual. Esto permite realizar muchas optimizaciones interprocedurales interesantes, como eliminar argumentos no utilizados.
Puedes leer más sobre LLVM en , al que consultarás a menudo al desarrollar tu propio compilador basado en LLVM. Aquí tienes , donde se analiza el desarrollo de un compilador para un lenguaje muy simple. Ambas fuentes de información te serán útiles para crear tu propio compilador.
¡Estimados lectores! ¿Utilizas LLVM?
Fuente: habr.com
