O desenvolvimento do 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 um único programador crie uma nova linguagem com desempenho próximo ao C. Trabalhar com o LLVM é complicado pelo fato de esse sistema ser representado por uma enorme quantidade de código, equipada com pequena documentação. Para tentar corrigir essa falha, o autor do material, que publicamos hoje, demonstrará exemplos de código escritos em Go e mostrará como eles são transmitidos primeiro ao
Go SSA e depois ao LLVM IR usando o compilador
TinyGO . O código IR Go SSA e LLVM foi ligeiramente editado, algo que não pertence às explicações fornecidas aqui foi removido, a fim de tornar essas explicações mais compreensíveis.
Primeiro exemplo
A primeira função que vou analisar aqui é um mecanismo simples para adicionar números:
func myAdd(a, b int) int{ return a + b }
Essa função é muito simples e, talvez, nada seja mais fácil de não surgir. Ele se traduz no seguinte código Go SSA:
func myAdd(a int, b int) int: entry: t0 = a + b int return t0
Com essa representação da função, as dicas sobre os tipos de dados são colocadas à direita; na maioria dos casos, você pode ignorá-las.
Este pequeno exemplo já permite que você veja a essência de um aspecto do SSA. Ou seja, ao converter código para o formato SSA, cada expressão é dividida nas partes mais elementares das quais consiste. No nosso caso, o comando
return a + b , de fato, representa duas operações: adicionando dois números e retornando o resultado.
Além disso, aqui você pode ver os blocos básicos do programa, neste código há apenas um bloco - a entrada (bloco de entrada). Falaremos mais sobre os blocos abaixo.
O código Go SSA pode ser facilmente convertido em LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) { entry: %0 = add i64 %a, %b ret i64 %0 }
Você pode perceber que, embora outras construções sintáticas sejam usadas aqui, a estrutura da função basicamente não foi alterada. O código IR LLVM é um pouco mais forte que o código Go SSA, semelhante a C. Aqui, na declaração de função, primeiro vem uma descrição do tipo de dados retornado, o tipo de 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 das entidades locais, pelo caractere
% (a função também é considerada uma entidade global).
Um dos recursos desse código que você precisa prestar atenção é que a decisão de representar o tipo Go
int , que pode ser representado por um valor de 32 ou 64 bits, dependendo do compilador e da finalidade da compilação, é tomada ao criar o LLVM Código IR. Esse é um dos muitos motivos pelos quais o código LLVM IR não é independente da plataforma. Esse código criado para uma plataforma não pode simplesmente ser utilizado e compilado para outra plataforma (a menos que você faça essa tarefa
com extrema cautela ).
Outro ponto interessante a ser observado é que o tipo
i64 não é um número inteiro assinado: é neutro em termos de representação do sinal do número. Dependendo da instrução, ele pode representar números assinados e números não assinados. No caso de representar a operação de adição, isso não desempenha um papel; portanto, não há diferença em trabalhar com números com ou sem sinal. Aqui, eu gostaria de observar que em C, o excesso de uma variável inteira assinada leva a um comportamento indefinido; portanto, o front-end Clang adiciona o sinalizador
nsw (sem quebra automática assinada) à operação, o que indica ao LLVM que ele pode prosseguir com a suposição de que com adição nunca ocorre transbordamento.
Isso pode ser importante para algumas otimizações. Por exemplo, a adição de dois valores
i16 em uma plataforma de 32 bits (com registros de 32 bits) requer, após a conclusão da adição, a operação de extensão de sinal para permanecer no intervalo
i16 . Por esse motivo, geralmente é mais eficiente executar operações inteiras, levando em consideração o tamanho da máquina do registro.
O que acontece no futuro com esse código de RI não é particularmente interessante para nós agora. O código é otimizado (mas, no caso de um exemplo tão simples como o nosso, nada já está otimizado) e, em seguida, é convertido em código de máquina.
Segundo exemplo
O exemplo a seguir, que examinaremos, será um pouco mais complicado. Ou seja, estamos falando de uma função que soma a fatia de números 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 t0
Aqui você já pode ver mais construções específicas para a apresentação do código na forma de SSA. Provavelmente, o recurso mais óbvio desse código é o fato de que não há comandos estruturados de controle de fluxo. Para controlar o fluxo de cálculos, existem apenas saltos condicionais e incondicionais e, se considerarmos esse comando como um comando para controlar o fluxo, um comando de retorno.
De fato, aqui você pode prestar atenção ao fato de que o programa não é dividido em blocos usando chaves (como nos idiomas da família C). É dividido por etiquetas, que se assemelha a linguagens de montagem, e é apresentado na forma de blocos de base. No SSA, os blocos base são sequências contíguas de código que começam com um rótulo e terminam com instruções para concluir o bloco base, por exemplo,
return e
jump .
Outro detalhe interessante desse código é a instrução
phi . A instrução é bastante incomum, pode levar algum tempo para descobrir. Lembre-se de que
SSA é a abreviação de Atribuição única estática. Essa é uma representação intermediária do código usado pelos compiladores, no qual cada variável é atribuída apenas uma vez. Isso é ótimo para expressar funções simples como nossa função
myAdd mostrada acima, mas não para funções mais complexas, como a função
sum , discutida nesta seção. Em particular, durante a execução do loop, as variáveis
i e
n mudam.
O SSA ignora a restrição em uma única atribuição de valores de variáveis usando a chamada instrução
phi (seu nome é retirado do alfabeto grego). O fato é que, para que a representação SSA do código possa ser formada para idiomas 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 base é usada como seus parâmetros. Por exemplo, considere esta instrução:
t0 = phi [entry: 0:int, for.body: t6] #n
Seu significado é o seguinte: se o bloco base anterior era um bloco de
entry (entrada),
t0 é constante
0 e se o bloco base anterior era
for.body , é necessário pegar o valor
t6 desse bloco. Tudo isso pode parecer bastante misterioso, mas graças a esse mecanismo, o SSA é garantido. Do ponto de vista humano, tudo isso complica a compreensão do código, mas o fato de cada valor ser atribuído apenas uma vez simplifica bastante muitas otimizações.
Observe que se você estiver escrevendo seu próprio compilador, normalmente não precisará lidar com essas coisas. Mesmo Clang não gera todas essas instruções
phi , usa o mecanismo
alloca (se assemelha a trabalhar com variáveis locais comuns). Em seguida, ao executar um passo de otimização do LLVM, chamado
mem2reg , as instruções
alloca são convertidas para o formulário SSA. O TinyGo, no entanto, recebe entrada do Go SSA, que, convenientemente, já foi convertido para o formato SSA.
Outra inovação dessa parte do código intermediário é que o acesso aos elementos da fatia pelo índice é apresentado na forma da operação de cálculo do endereço e da operação de desreferenciamento do ponteiro obtido. 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 descobrimos esses recursos, veremos o que esse código se tornará ao convertê-lo para o formulário de IR do 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 }
Aqui, como antes, podemos ver a mesma estrutura, que inclui outras construções sintáticas. Por exemplo, nas chamadas
phi , valores e etiquetas são trocados. No entanto, também há algo que vale a pena prestar atenção especial.
Para iniciantes, aqui você pode ver uma assinatura completamente diferente da função. O LLVM não suporta fatias, como resultado, na forma de 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 fatia (
ptr ,
len e
cap ) como uma estrutura (struct), mas apresentá-los como três entidades separadas permite algumas otimizações. Outros compiladores podem apresentar a fatia de alguma outra maneira, isso depende das convenções para chamar funções da plataforma de destino.
Outra característica interessante desse código é o uso da
getelementptr (geralmente chamada de GEP para abreviar).
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 isso:
int* sliceptr(int *ptr, int index) { return ptr + index; }
O mais importante aqui é que a instrução
getelementptr não executa operações de desreferência. Ele calcula apenas um novo ponteiro com base no existente. Pode ser interpretado como
mul e
add no nível do hardware. Detalhes sobre as instruções do GEP podem ser encontrados
aqui .
Outra característica interessante desse código intermediário é o uso da instrução
icmp . Esta é uma instrução de uso geral usada para implementar comparações de números inteiros. O resultado desta instrução é sempre um valor do tipo
i1 - um valor lógico. Nesse caso, é feita uma comparação usando a palavra-chave
slt (com
slt menor que), pois estamos comparando dois números anteriormente representados pelo tipo
int . Se comparássemos dois números inteiros não assinados,
icmp como uma instrução, 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.
Sumário
Acredito que neste artigo examinei os recursos mais importantes do LLVM IR. Claro, ainda há muitas coisas. Em particular, na representação intermediária do código, pode haver muitas anotações que permitem levar em consideração certos recursos do código conhecidos pelo compilador durante as passagens de otimização que não podem ser expressos de outra maneira no IR. Por exemplo, esses são os sinalizadores
inbounds instrução
inbounds ou os
nuw nsw e
nuw , que podem ser adicionados à instrução
add . O mesmo se aplica à palavra-chave
private , que indica ao otimizador que a função marcada por ele não será referenciada de fora da unidade de compilação atual. Isso permite que você execute muitas otimizações interprocedimentais interessantes, como a eliminação de argumentos não utilizados.
Você pode ler mais sobre o LLVM na
documentação , à qual você frequentemente se refere ao desenvolver seu próprio compilador baseado em LLVM. Aqui está um
guia que discute o desenvolvimento do compilador para uma linguagem muito simples. Ambas as fontes de informação serão úteis ao criar seu próprio compilador.
Caros leitores! Você usa LLVM?