Desenvolver um compilador é uma tarefa muito difícil. Mas, felizmente, com o desenvolvimento de projetos como o LLVM, a solução para esse problema é bastante simplificada, o que permite que até mesmo um único programador crie uma nova linguagem com desempenho próximo de C. Trabalhar com LLVM é complicado pelo fato de que este O sistema é representado por uma enorme quantidade de código, equipado com pouca documentação. Para tentar corrigir esta lacuna, o autor do material, cuja tradução publicamos hoje, vai demonstrar exemplos de códigos escritos em Go e mostrar como eles são primeiro traduzidos para e, em seguida, no LLVM IR usando o compilador . O código Go SSA e LLVM IR foi ligeiramente editado para remover itens que não são relevantes para as explicações fornecidas aqui, a fim de torná-las mais compreensíveis.
Primeiro exemplo
A primeira função que examinarei aqui é um mecanismo simples para somar números:
func myAdd(a, b int) int{
return a + b
}Esta função é muito simples e, talvez, nada pudesse ser mais simples. Isso se traduz no seguinte código Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Com esta visualização, as dicas de tipo de dados são colocadas à direita e podem ser ignoradas na maioria dos casos.
Este pequeno exemplo já permite ver a essência de um aspecto do SSA. Ou seja, ao converter o código para o formato SSA, cada expressão é dividida nas partes mais elementares que a compõem. No nosso caso, o comando return a + b, na verdade, representa duas operações: somar dois números e retornar o resultado.
Além disso, aqui você pode ver os blocos básicos do programa, neste código existe apenas um bloco - o bloco de entrada. Falaremos mais sobre blocos abaixo.
O código Go SSA é facilmente convertido em LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
O que você pode notar é que embora diferentes estruturas sintáticas sejam usadas aqui, a estrutura da função permanece basicamente inalterada. O código IR LLVM é um pouco mais forte que o código Go SSA, semelhante ao C. Aqui, na declaração da função, primeiro há uma descrição do tipo de dados que ela retorna, o tipo do argumento é indicado antes do nome do argumento. Além disso, para simplificar a análise de IR, os nomes das entidades globais são precedidos pelo símbolo @, e antes dos nomes locais há um símbolo % (uma função também é considerada uma entidade global).
Uma coisa a se notar sobre este código é que a decisão de representação de tipo do Go int, que pode ser representado como um valor de 32 ou 64 bits, dependendo do compilador e do destino da compilação, é aceito quando o LLVM gera o código IR. Esta é uma das muitas razões pelas quais o código IR LLVM não é, como muitas pessoas pensam, independente de plataforma. Tal código, criado para uma plataforma, não pode simplesmente ser obtido e compilado para outra plataforma (a menos que você seja adequado para resolver este problema ).
Outro ponto interessante que vale a pena observar é que o tipo i64 não é um número inteiro com sinal: é neutro em termos de representação do sinal do número. Dependendo da instrução, pode representar números assinados e não assinados. No caso da representação da operação de adição isso não importa, portanto não há diferença em trabalhar com números assinados ou não assinados. Aqui eu gostaria de observar que na linguagem C, o estouro de uma variável inteira assinada leva a um comportamento indefinido, então o frontend Clang adiciona um sinalizador à operação nsw (sem wrapper assinado), que informa ao LLVM que ele pode assumir que a adição nunca transborda.
Isso pode ser importante para algumas otimizações. Por exemplo, adicionando dois valores i16 em uma plataforma de 32 bits (com registradores de 32 bits) requer, após a adição, uma operação de expansão de sinal para permanecer no alcance i16. Por causa disso, muitas vezes é mais eficiente realizar operações inteiras com base nos tamanhos dos registradores da máquina.
O que acontece a seguir com este código IR não é de particular interesse para nós agora. O código é otimizado (mas no caso de um exemplo simples como o nosso nada é otimizado) e depois convertido em código de máquina.
Segundo exemplo
O próximo exemplo que veremos será um pouco mais complicado. Ou seja, estamos falando de uma função que soma uma fatia de inteiros:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Este código é convertido 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 t0Aqui você já pode ver mais construções típicas de representação de código no formato SSA. Talvez a característica mais óbvia deste código seja o fato de não haver comandos estruturados de controle de fluxo. Para controlar o fluxo de cálculos, existem apenas saltos condicionais e incondicionais, e, se considerarmos este comando como um comando de controle de fluxo, um comando de retorno.
Na verdade, aqui você pode prestar atenção ao fato de que o programa não é dividido em blocos usando chaves (como na família de linguagens C). Ele é dividido por rótulos, que lembram linguagens assembly, e apresentado na forma de blocos básicos. No SSA, os blocos básicos são definidos como sequências contíguas de código começando com um rótulo e terminando com instruções básicas de conclusão de bloco, como - return и jump.
Outro detalhe interessante deste código é representado pela instrução phi. As instruções são bastante incomuns e podem levar algum tempo para serem compreendidas. lembre-se disso é a abreviatura de Atribuição Única Estática. Esta é uma representação intermediária do código usado pelos compiladores, em que cada variável recebe um valor apenas uma vez. Isso é ótimo para expressar funções simples como nossa função myAddmostrado acima, mas não é adequado para funções mais complexas, como a função discutida nesta seção sum. Em particular, as variáveis mudam durante a execução do loop i и n.
SSA ignora a restrição de atribuição de valores de variáveis uma vez usando a chamada instrução phi (seu nome vem do alfabeto grego). O fato é que para que a representação SSA do código seja gerada para linguagens como C é necessário recorrer a alguns truques. O resultado da chamada desta instrução é o valor atual da variável (i ou n), e uma lista de blocos básicos é usada como parâmetros. Por exemplo, considere esta instrução:
t0 = phi [entry: 0:int, for.body: t6] #n
Seu significado é o seguinte: se o bloco básico anterior era um bloco entry (entrada), então t0 é uma constante 0, e se o bloco básico anterior foi for.body, então você precisa pegar o valor t6 deste bloco. Tudo isto pode parecer bastante misterioso, mas é este mecanismo que faz o SSA funcionar. Do ponto de vista humano, tudo isso torna o código difícil de entender, mas o fato de cada valor ser atribuído apenas uma vez torna muitas otimizações muito mais fáceis.
Observe que se você escrever seu próprio compilador, normalmente não terá que lidar com esse tipo de coisa. Mesmo o Clang não gera todas essas instruções phi, ele usa um mecanismo alloca (é semelhante a trabalhar com variáveis locais comuns). Então, ao executar uma passagem de otimização LLVM chamada , instruções alloca convertido para o formato SSA. O TinyGo, no entanto, recebe informações do Go SSA, que, convenientemente, já está convertido para o formato SSA.
Outra inovação do fragmento de código intermediário em consideração é que o acesso aos elementos da fatia por índice é representado na forma de uma operação de cálculo do endereço e uma operação de desreferenciação do ponteiro resultante. Aqui você pode ver a adição direta de constantes ao código IR (por exemplo - 1:int). No exemplo com a função myAdd isso não foi usado. Agora que já resolvemos esses recursos, vamos dar uma olhada no que esse código se torna quando convertido para o 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
}
Aqui, como antes, podemos ver a mesma estrutura, que inclui outras estruturas sintáticas. Por exemplo, em chamadas phi valores e rótulos trocados. No entanto, há algo aqui ao qual vale a pena prestar atenção especial.
Para começar, aqui você pode ver uma assinatura de função completamente diferente. O LLVM não oferece suporte a fatias e, como resultado, como otimização, o compilador TinyGo que gerou esse código intermediário dividiu a descrição dessa estrutura de dados em partes. Poderia representar três elementos de fatia (ptr, len и cap) como uma estrutura (struct), mas representá-los como três entidades separadas permite algumas otimizações. Outros compiladores podem representar a fatia de outras maneiras, dependendo das convenções de chamada das funções da plataforma alvo.
Outra característica interessante deste código é o uso da instrução getelementptr (frequentemente abreviado como GEP).
Esta instrução funciona com ponteiros e é usada para obter um ponteiro para um elemento de fatia. Por exemplo, vamos compará-lo com o seguinte código escrito em C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}Ou com o seguinte equivalente a isto:
int* sliceptr(int *ptr, int index) {
return ptr + index;
}
O mais importante aqui é que as instruções getelementptr não executa operações de desreferenciação. Apenas calcula um novo ponteiro com base no existente. Pode ser tomado como instruções mul и add no nível do hardware. Você pode ler mais sobre as instruções GEP .
Outra característica interessante deste código intermediário é a utilização da instrução icmp. Esta é uma instrução de uso geral usada para implementar comparações de inteiros. O resultado desta instrução é sempre um valor do tipo i1 - valor lógico. Neste caso, uma comparação é feita usando a palavra-chave slt (com sinal menor que), pois estamos comparando dois números anteriormente representados pelo tipo int. Se estivéssemos comparando dois inteiros sem sinal, usaríamos icmp, e a palavra-chave usada na comparação seria ult. Para comparar números de ponto flutuante, outra instrução é usada, fcmp, que funciona de maneira semelhante.
Resultados de
Acredito que neste material abordei os recursos mais importantes do LLVM IR. Claro, há muito mais aqui. Em particular, a representação intermediária do código pode conter muitas anotações que permitem passagens de otimização para levar em conta certas características do código conhecidas pelo compilador que não podem ser expressas de outra forma em IR. Por exemplo, esta é uma bandeira inbounds Instruções GEP ou sinalizadores nsw и nuw, que pode ser adicionado às instruções add. O mesmo vale para a palavra-chave private, indicando ao otimizador que a função marcada não será referenciada de fora da unidade de compilação atual. Isso permite muitas otimizações interprocedimentos interessantes, como a eliminação de argumentos não utilizados.
Você pode ler mais sobre o LLVM em , ao qual você se referirá frequentemente ao desenvolver seu próprio compilador baseado em LLVM. Aqui , que analisa o desenvolvimento de um compilador para uma linguagem muito simples. Ambas as fontes de informação serão úteis ao criar seu próprio compilador.
Caros leitores! Você está usando o LLVM?
Fonte: habr.com