O desenvolvimento de um compilador é uma tarefa bastante desafiadora. Porém, felizmente, com o avanço de projetos como o LLVM, a resolução desse problema se torna significativamente mais simples, permitindo que até mesmo um programador solitário crie uma nova linguagem com desempenho próximo ao de C. Trabalhar com o LLVM é complicado porque este sistema é apresentado através de uma enorme quantidade de código, acompanhada de uma documentação escassa. Para tentar corrigir essa deficiência, o autor do material, cuja tradução publicamos hoje, pretende demonstrar exemplos de código escritos em Go e mostrar como eles são traduzidos inicialmente para , e depois — para LLVM IR utilizando o compilador . O código Go SSA e LLVM IR foi ligeiramente editado, removendo o que não está relacionado às explicações apresentadas aqui, a fim de tornar essas explicações mais compreensíveis.
O primeiro exemplo
A primeira função que irei abordar aqui é um simples mecanismo para somar números:
func myAdd(a, b int) int{
return a + b
}Essa função é muito simples, e talvez não haja nada mais básico do que isso. Ela é traduzida para o seguinte código Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Nesta representação da função, as sugestões de tipos de dados são colocadas à direita, e na maioria das vezes podem ser ignoradas.
Este pequeno exemplo já permite observar a essência de um dos aspectos do SSA. Ou seja, ao transformar o código para a forma SSA, cada expressão é dividida em suas partes mais elementares. No nosso caso, o comando return a + b, na verdade, representa duas operações: a soma de dois números e o retorno do resultado.
Além disso, aqui também podemos ver os blocos básicos do programa; neste código, há apenas um bloco — o bloco de entrada (entry block). Faremos uma discussão mais detalhada sobre blocos mais adiante.
O código Go SSA se traduz facilmente em LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} É possível notar que, embora outras construções sintáticas sejam usadas, a estrutura da função, em grande parte, manteve-se inalterada. O código LLVM IR é um pouco mais robusto do que o código Go SSA, sendo semelhante ao C. Aqui, na declaração da função, primeiro aparece a descrição do tipo de dado que ela retorna, e o tipo do argumento é especificado antes do nome do argumento. Além disso, para facilitar a análise do IR, um símbolo precede os nomes das entidades globais. @, e um símbolo precede os locais. % (a função também é considerada uma entidade global).
Uma das características deste código à qual vale prestar atenção é que a decisão sobre a representação do tipo Go int, que pode ser representado por um valor de 32 ou 64 bits, dependendo do compilador e do objetivo da compilação, é tomada ao criar o código LLVM IR. Esta é uma das muitas razões pelas quais o código LLVM IR não é, como muitos pensam, independente de plataforma. Um código criado para uma plataforma não pode simplesmente ser compilado para outra plataforma (a menos que se aborde o problema ).
Outro ponto interessante a ser observado é que o tipo i64 não é um inteiro com sinal: ele é neutro em relação à representação do sinal do número. Dependendo da instrução, ele pode representar tanto números com sinal quanto números sem sinal. No caso da operação de adição, isso não faz diferença, portanto, não há distinção no trabalho com números com sinal ou sem sinal. Aqui, é importante destacar que, na linguagem C, o estouro de uma variável inteira com sinal resulta em comportamento indefinido, por isso o front-end Clang adiciona um sinal à operação nsw (no signed wrap), que indica ao LLVM que ele pode assumir que a adição nunca resulta em estouro.
Isso pode ser importante para algumas otimizações. Por exemplo, a adição de dois valores i16 em uma plataforma de 32 bits (com registradores de 32 bits) requer, após realizar a adição, uma operação de extensão de sinal para permanecer dentro do intervalo i16. Por causa disso, frequentemente é mais eficiente realizar operações inteiras considerando os tamanhos da máquina do registrador.
O que acontece a seguir com esse código IR não nos interessa muito agora. O código é otimizado (mas, no caso de um exemplo tão simples como o nosso, nada é otimizado), e depois é transformado em código de máquina.
Segundo exemplo
O próximo exemplo que iremos considerar será um pouco mais complexo. Em particular, trata-se de uma função que soma um slice de números inteiros:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Esse código é transformado no seguinte código SSA 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 t0Aqui já é possível ver mais construções típicas da representação de código na forma SSA. Provavelmente, a característica mais óbvia desse código é o fato de que não há comandos estruturados de controle de fluxo de execução. Para controlar o fluxo de execução, há apenas saltos condicionais e incondicionais, e, se considerarmos esse comando como um comando de controle de fluxo, o comando de retorno.
Na verdade, pode-se notar que o programa não está dividido em blocos usando chaves (como nas linguagens da família C). Ele é dividido em rótulos, o que lembra as linguagens assembly, e apresentado na forma de blocos básicos. Nos SSA, blocos básicos são sequências contínuas de código que começam com um rótulo e terminam com instruções de término de bloco básico, por exemplo — return e jump.
Outra característica interessante desse código é apresentada pela instrução phi. Essa instrução é bastante incomum e pode levar algum tempo para se entender. Lembre-se de que — é uma abreviação para Static Single Assignment. Este é uma representação intermediária do código usada por compiladores, onde cada variável recebe um valor apenas uma vez. Isso é ideal para expressar funções simples, como a nossa função myAdd, mostrada acima, mas não é adequada para funções mais complexas — como a discutida nesta seção sum. Em particular, durante a execução do laço, as variáveis mudam i e n.
SSA contorna a restrição de atribuição única de valores a variáveis usando o que é chamado de instrução phi (o nome vem do alfabeto grego). A questão é que, para formar a representação SSA do código para linguagens como C, é necessário recorrer a algumas artimanhas. O resultado da chamada a esta instrução é o valor atual da variável (i ou n), e a lista de blocos básicos é usada como seus parâmetros. Por exemplo, considere a seguinte instrução:
t0 = phi [entry: 0:int, for.body: t6] #n Seu significado é o seguinte: se o bloco básico anterior era o bloco entry (entrada), então t0 — é uma constante 0, e se o bloco básico anterior era for.body, então devemos pegar o valor t6 desse bloco. Isso pode parecer bastante misterioso, mas graças a esse mecanismo, a operação SSA é garantida. Do ponto de vista humano, isso complica a compreensão do código, mas o fato de que cada valor é atribuído apenas uma vez simplifica significativamente muitas otimizações.
Observe que se você estiver escrevendo seu próprio compilador, geralmente não precisa lidar com tais coisas. Mesmo Clang não gera todas essas instruções phi, ele usa o mecanismo alloca (que é semelhante ao trabalho com variáveis locais comuns). Então, durante a passagem de otimização da LLVM chamada , as instruções alloca são convertidas para a forma SSA. O TinyGo, no entanto, obtém dados da Go SSA, que, felizmente, já estão convertidos para a forma SSA.
Outra novidade do fragmento de código intermediário discutido é que o acesso aos elementos de um slice por índice é apresentado na forma de uma operação de cálculo de endereço e uma operação de desreferência do ponteiro obtido. Aqui podemos ver a adição direta de constantes no código IR (por exemplo — 1:int). No exemplo da função myAdd Isso não foi utilizado. Agora, entendendo essas particularidades, vamos ver como esse código se transforma na forma LLVM IR:
defina i64 @soma(i64* %ptr, i64 %len, i64 p) {
entrada:
br label %for.loop
for.loop: ; preds = %for.body, %entrada
%0 = phi i64 [ 0, %entrada ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entrada ], [ %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
} Aqui, como antes, podemos ver a mesma estrutura, incluindo outras construções sintáticas. Por exemplo, nas chamadas phi os valores e as etiquetas foram trocados. No entanto, há algo que merece atenção especial.
Para começar, podemos observar uma assinatura de função completamente diferente. O LLVM não suporta slices, portanto, como otimização, o compilador TinyGo, que gerou esse código intermediário, dividiu a descrição dessa estrutura de dados em partes. Ele poderia representar três elementos de um slice (ptr, len e cap) como uma estrutura (struct), mas representá-los como três entidades separadas permite realizar algumas otimizações. Outros compiladores podem representar os slices de outras maneiras, dependendo das convenções de chamada de função da plataforma de destino.
Outra característica interessante deste código é o uso da instrução getelementptr (geralmente abreviado como GEP).
Essa instrução trabalha com ponteiros e é usada para obter um ponteiro para um elemento de um slice. Por exemplo, vamos compará-la com o seguinte código em C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ou com o seguinte, equivalente a este:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} O mais importante aqui é que a instrução getelementptr não realiza operações de desreferenciamento. Ela apenas calcula um novo ponteiro, com base no existente. Pode ser vista como uma instrução mul e add em nível de hardware. Os detalhes sobre a instrução GEP podem ser encontrados .
Outra característica interessante deste código intermediário é o uso da instrução icmp. Este é um guia de uso geral, utilizado para implementar a comparação de números inteiros. O resultado da execução desta instrução é sempre um valor do tipo i1 — valor lógico. Neste caso, a comparação é feita usando a palavra-chave slt (signed less than), uma vez que estamos comparando dois números, anteriormente apresentados do tipo int. Se estivermos comparando dois números inteiros sem sinal, então usaríamos icmp, e a palavra-chave utilizada na comparação seria ult. Para comparar números de ponto flutuante, é utilizada outra instrução, fcmp, que funciona de maneira semelhante.
Resultados
Acredito que neste material abordei as características mais importantes do LLVM IR. Claro, há muito mais. Em particular, na representação intermediária do código, pode haver várias anotações que permitem levar em conta, durante as passagens de otimização, características específicas do código que o compilador conhece, mas que não podem ser expressas de outra forma no IR. Por exemplo, essa é a flag inbounds da instrução GEP, ou as flags nsw e nuw, que podem ser adicionadas à instrução add. O mesmo se aplica à palavra-chave private, que indica ao otimizador que a função marcada não será referenciada externamente à unidade de compilação atual. Isso permite realizar várias otimizações inter-procedimentais interessantes, como a remoção de argumentos não utilizados.
Você pode ler mais sobre LLVM em , que será uma referência frequente enquanto você desenvolve seu próprio compilador baseado em LLVM. Aqui está , que discute o desenvolvimento de um compilador para uma linguagem muito simples. Ambas essas fontes de informação serão úteis na criação do seu próprio compilador.
Prezados leitores! Você utiliza LLVM?
Fonte: habr.com
