Desenvolver un compilador é unha tarefa moi difícil. Pero, afortunadamente, co desenvolvemento de proxectos como LLVM simplifícase moito a solución a este problema, o que permite que ata un só programador cree unha nova linguaxe que teña un rendemento próximo ao C. Traballar con LLVM é complicado polo feito de que este sistema está representado por unha gran cantidade de código, equipado con pouca documentación. Para tentar corrixir esta deficiencia, o autor do material, cuxa tradución hoxe publicamos, vai mostrar exemplos de código escrito en Go e mostrar como se traducen por primeira vez a , e despois en LLVM IR usando o compilador . O código Go SSA e LLVM IR editouse lixeiramente para eliminar cousas que non son relevantes para as explicacións que se dan aquí, co fin de que as explicacións sexan máis comprensibles.
Primeiro exemplo
A primeira función que vou ver aquí é un mecanismo sinxelo para engadir números:
func myAdd(a, b int) int{
return a + b
}Esta función é moi sinxela e, quizais, nada podería ser máis sinxelo. Tradúcese no seguinte código Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Con esta vista, as suxestións de tipo de datos colócanse á dereita e pódense ignorar na maioría dos casos.
Este pequeno exemplo xa che permite ver a esencia dun aspecto de SSA. É dicir, ao converter o código en forma SSA, cada expresión divídese nas partes máis elementais das que está composta. No noso caso, o comando return a + b, de feito, representa dúas operacións: sumar dous números e devolver o resultado.
Ademais, aquí podes ver os bloques básicos do programa; neste código só hai un bloque: o bloque de entrada. A continuación falaremos máis sobre os bloques.
O código Go SSA convértese facilmente a LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
O que podes notar é que aínda que aquí se usan diferentes estruturas sintácticas, a estrutura da función permanece basicamente inalterada. O código LLVM IR é un pouco máis forte que o código Go SSA, semellante ao C. Aquí, na declaración da función, primeiro hai unha descrición do tipo de datos que devolve, o tipo de argumento indícase antes do nome do argumento. Ademais, para simplificar a análise IR, os nomes das entidades globais van precedidos do símbolo @, e antes dos nomes locais hai un símbolo % (unha función tamén se considera unha entidade global).
Unha cousa a ter en conta deste código é a decisión de representación do tipo de Go int, que se pode representar como un valor de 32 ou 64 bits, dependendo do compilador e do destino da compilación, é aceptado cando LLVM xera o código IR. Esta é unha das moitas razóns polas que o código LLVM IR non é, como moita xente pensa, independente da plataforma. Tal código, creado para unha plataforma, non pode simplemente ser tomado e compilado para outra plataforma (a menos que sexa adecuado para resolver este problema ).
Outro punto interesante a destacar é que o tipo i64 non é un número enteiro con signo: é neutro en canto a representar o signo do número. Dependendo da instrución, pode representar tanto números asinados como sen asinar. No caso da representación da operación de suma, isto non importa, polo que non hai diferenzas ao traballar con números asinados ou sen asinar. Aquí gustaríame notar que na linguaxe C, desbordar unha variable enteira con signo leva a un comportamento indefinido, polo que a interface Clang engade unha bandeira á operación. nsw (sen envolver asinado), o que lle di a LLVM que pode asumir que a adición nunca se desborda.
Isto pode ser importante para algunhas optimizacións. Por exemplo, engadindo dous valores i16 nunha plataforma de 32 bits (con rexistros de 32 bits) require, despois da adición, unha operación de expansión de signos para permanecer dentro do rango. i16. Debido a isto, moitas veces é máis eficiente realizar operacións enteiras baseadas nos tamaños do rexistro da máquina.
O que ocorre despois con este código IR non nos interesa agora. Optimízase o código (pero no caso dun exemplo sinxelo como o noso non se optimiza nada) e despois convértese en código máquina.
Segundo exemplo
O seguinte exemplo que veremos será un pouco máis complicado. É dicir, estamos a falar dunha función que suma unha porción de números enteiros:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Este código convértese no seguinte 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í xa podes ver máis construcións típicas para representar código no formulario SSA. Quizais a característica máis obvia deste código é o feito de que non hai comandos de control de fluxo estruturados. Para controlar o fluxo de cálculos, só hai saltos condicionais e incondicionais e, se consideramos este comando como un comando para controlar o fluxo, un comando de retorno.
De feito, aquí podes prestar atención ao feito de que o programa non está dividido en bloques usando chaves (como na familia de linguaxes C). Está dividido por etiquetas, que lembran as linguaxes ensambladoras, e preséntase en forma de bloques básicos. En SSA, os bloques básicos defínense como secuencias contiguas de código que comezan cunha etiqueta e rematan con instrucións básicas de finalización de bloques, como - return и jump.
Outro detalle interesante deste código está representado pola instrución phi. As instrucións son bastante inusuales e poden tardar algún tempo en entenderse. lembra, iso é a abreviatura de Static Single Assignment. Esta é unha representación intermedia do código empregado polos compiladores, na que a cada variable se lle asigna un valor só unha vez. Isto é xenial para expresar funcións sinxelas como a nosa función myAddmostrado anteriormente, pero non é adecuado para funcións máis complexas como a función que se comenta nesta sección sum. En particular, as variables cambian durante a execución do bucle i и n.
SSA evita a restrición de asignación de valores variables unha vez usando a chamada instrución phi (o seu nome é tomado do alfabeto grego). O caso é que para que a representación SSA do código se xere para linguaxes como C, tes que recorrer a algúns trucos. O resultado de chamar a esta instrución é o valor actual da variable (i ou n), e utilízase unha lista de bloques básicos como parámetros. Por exemplo, considere esta instrución:
t0 = phi [entry: 0:int, for.body: t6] #n
O seu significado é o seguinte: se o bloque básico anterior era un bloque entry (entrada), entón t0 é unha constante 0, e se o bloque básico anterior era for.body, entón tes que tomar o valor t6 desde este bloque. Todo isto pode parecer bastante misterioso, pero este mecanismo é o que fai que o SSA funcione. Desde unha perspectiva humana, todo isto fai que o código sexa difícil de entender, pero o feito de que cada valor se asigne só unha vez fai que moitas optimizacións sexan moito máis fáciles.
Ten en conta que se escribes o teu propio compilador, normalmente non terás que tratar con este tipo de cousas. Incluso Clang non xera todas estas instrucións phi, usa un mecanismo alloca (semella traballar con variables locais comúns). Entón, cando se executa un pase de optimización LLVM chamado , instrucións alloca convertido ao formulario SSA. TinyGo, con todo, recibe a entrada de Go SSA, que, convenientemente, xa está convertido ao formulario SSA.
Outra innovación do fragmento de código intermedio en consideración é que o acceso aos elementos de corte por índice se representa en forma dunha operación de cálculo da dirección e dunha operación de desreferenciación do punteiro resultante. Aquí podes ver a adición directa de constantes ao código IR (por exemplo - 1:int). No exemplo coa función myAdd isto non foi usado. Agora que eliminamos esas funcións, vexamos en que se converte este código cando se converte ao formulario 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 a mesma estrutura, que inclúe outras estruturas sintácticas. Por exemplo, nas chamadas phi valores e etiquetas intercambiadas. Non obstante, hai algo aquí ao que paga a pena prestarlle especial atención.
Para comezar, aquí podes ver unha sinatura de función completamente diferente. LLVM non admite porcións e, como resultado, como unha optimización, o compilador TinyGo que xerou este código intermedio dividiu a descrición desta estrutura de datos en partes. Podería representar tres elementos de corte (ptr, len и cap) como estrutura (struct), pero representalos como tres entidades separadas permite algunhas optimizacións. Outros compiladores poden representar o segmento doutros xeitos, dependendo das convencións de chamada das funcións da plataforma de destino.
Outra característica interesante deste código é o uso da instrución getelementptr (moitas veces abreviado como GEP).
Esta instrución funciona con punteiros e úsase para obter un punteiro a un elemento de corte. Por exemplo, comparémolo co seguinte código escrito en C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ou co seguinte equivalente a este:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
O máis importante aquí é que as instrucións getelementptr non realiza operacións de desreferenciación. Só calcula un novo punteiro baseándose no existente. Pódese tomar como instrucións mul и add a nivel de hardware. Podes ler máis sobre as instrucións do GEP .
Outra característica interesante deste código intermedio é o uso da instrución icmp. Esta é unha instrución de propósito xeral que se usa para implementar comparacións de enteiros. O resultado desta instrución é sempre un valor de tipo i1 - Valor lóxico. Neste caso, faise unha comparación mediante a palabra clave slt (asinado menos que), xa que estamos comparando dous números representados anteriormente polo tipo int. Se estivésemos comparando dous enteiros sen signo, usaríamos icmp, e a palabra clave utilizada na comparación sería ult. Para comparar números de coma flotante, utilízase outra instrución, fcmp, que funciona dun xeito similar.
Resultados de
Creo que neste material cubrín as características máis importantes de LLVM IR. Por suposto, aquí hai moito máis. En particular, a representación intermedia do código pode conter moitas anotacións que permiten que os pases de optimización teñan en conta certas características do código coñecidas polo compilador que non se poden expresar doutro xeito en IR. Por exemplo, esta é unha bandeira inbounds Instrucións GEP ou bandeiras nsw и nuw, que se pode engadir ás instrucións add. O mesmo ocorre coa palabra clave private, indicando ao optimizador que a función que marca non será referenciada desde fóra da unidade de compilación actual. Isto permite moitas optimizacións interprocedurais interesantes, como eliminar argumentos non utilizados.
Podes ler máis sobre LLVM en , ao que se referirá a miúdo ao desenvolver o seu propio compilador baseado en LLVM. Aquí , que busca desenvolver un compilador para unha linguaxe moi sinxela. Ambas fontes de información serán útiles para crear o seu propio compilador.
Queridos lectores! Estás a usar LLVM?
Fonte: www.habr.com