lacc
1.0.0
Este é um projeto de brinquedo meu, com o objetivo de fazer um compilador para C, escrito em C, que é capaz de se compilar.
Clone e construa a partir da fonte, e o binário será colocado em bin/lacc .
git clone https://github.com/larmel/lacc.git
cd lacc
./configure
make
make install
A configuração padrão inclui algumas sondagens básicas do ambiente para detectar para qual máquina e LIBC estamos compilando. As plataformas reconhecidas atualmente incluem Linux com Glibc ou Musl e OpenBSD.
Certos cabeçalhos da biblioteca padrão, como stddef.h e stdarg.h , contêm definições que são inerentemente específicas do compilador e são fornecidas especificamente para LACC sob lib/. Se você deseja usar bin/lacc diretamente sem instalar os cabeçalhos, poderá substituir o local configurando --libdir para apontar diretamente para esta pasta.
O alvo install copiará os binários e os cabeçalhos para os locais usuais, ou conforme configurado com --prefix ou --bindir . Há também uma opção para definir DESTDIR . Execute make uninstall para remover todos os arquivos que foram copiados.
Consulte ./configure --help para opções para personalizar parâmetros de construção e instalação.
A interface da linha de comando é mantida semelhante ao GCC e outros compiladores, usando principalmente um subconjunto dos mesmos sinalizadores e opções.
-E Output preprocessed.
-S Output GNU style textual x86_64 assembly.
-c Output x86_64 ELF object file.
-dot Output intermediate representation in dot format.
-o Specify output file name. If not speficied, default to input file
name with suffix changed to '.s', '.o' or '.dot' when compiling
with -S, -c or -dot, respectively. Otherwise use stdout.
-std= Specify C standard, valid options are c89, c99, and c11.
-I Add directory to search for included files.
-w Disable warnings.
-g Generate debug information (DWARF).
-O{0..3} Set optimization level.
-D X[=] Define macro, optionally with a value. For example -DNDEBUG, or
-D 'FOO(a)=a*2+1'.
-f[no-]PIC Generate position-independent code.
-v Print verbose diagnostic information. This will dump a lot of
internal state during compilation, and can be useful for debugging.
--help Print help text.
Argumentos que não correspondem a nenhuma opção são tomados para serem arquivos de entrada. Se nenhum modo de compilação for especificado, o LACC atuará como um invólucro para o ligante /bin/ld do sistema. Alguns sinalizadores comuns de ligação são suportados.
-Wl, Specify linker options, separated by commas.
-L Add linker include directory.
-l Add linker library.
-shared Passed to linker as is.
-rdynamic Pass -export-dynamic to linker.
Como exemplo de invocação, aqui está compilando o teste/c89/fact.c para o código do objeto e, em seguida, usando o vinculador do sistema para produzir o executável final.
bin/lacc -c test/c89/fact.c -o fact.o
bin/lacc fact.o -o fact
O programa faz parte do conjunto de testes, calculando 5! Usando a recursão e saindo da resposta. Em execução ./fact seguido de echo $? deve imprimir 120 .
O compilador está escrito em C89, contando cerca de 19k linhas de código no total. Não há dependências externas, exceto o Libary padrão C e algumas chamadas de sistema necessárias para invocar o vinculador.
A implementação é organizada em quatro partes principais; pré -processador, analisador, otimizador e back -end, cada um em seu próprio diretório em SRC/. Em geral, cada módulo (um arquivo .c normalmente emparelhado com um arquivo .h que definindo a interface público) depende principalmente de cabeçalhos em sua própria subárvore. As declarações compartilhadas em nível global residem em incluir/lacc/. É aqui que você encontrará as estruturas de dados principais e interfaces entre pré -processamento, análise e geração de código.
O pré -processamento inclui arquivos de leitura, tokenização, expansão de macro e manuseio de diretiva. A interface do pré -processador é peek(0) , peekn(1) , consume(1) , try_consume(1) e next(0) , que analisa um fluxo de objetos struct token pré -processados. Estes são definidos em incluir/lacc/token.h.
O processamento de entrada é feito completamente preguiçosamente, impulsionado pelo analisador chamando essas funções para consumir mais entradas. Um tampão de tokens pré -processados é mantido para LookaHead e preenchido sob demanda quando está espreitando.
O código é modelado como gráfico de fluxo de controle dos blocos básicos, cada um mantendo uma sequência de instruções de código de três esforços. Cada variável externa ou definição de função é representada por um objeto struct definition , definindo um único struct symbol e um CFG mantendo o código. As estruturas de dados que apóiam a representação intermediária podem ser encontradas em incluir/lacc/ir.h.
Visualizar a representação intermediária é um alvo de saída separado. Se a opção -DOT for especificada, um arquivo de texto formatado de ponto será produzido como saída.
bin/lacc -dot -I include src/backend/compile.c -o compile.dot
dot -Tps compile.dot -o compile.ps
Abaixo está um exemplo de uma função encontrada no src/back -end/compile.c, mostrando uma fatia do gráfico completo. A saída completa pode ser gerada como um arquivo PostScript executando os comandos mostrados.
Cada bloco básico no gráfico possui uma lista de instruções, mais comumente IR_ASSIGN , que atribui uma expressão ( struct expression ) a uma variável ( struct var ). As expressões também contêm operandos variáveis, que podem codificar localizações de memória, endereços e ponteiros dereferenciados em alto nível.
DIRECT referem -se à memória em *(&symbol + offset) , onde o símbolo é uma variável ou temporária em um local específico na memória (por exemplo, pilha).ADDRESS representam exatamente o endereço de um operando DIRECT , a saber (&symbol + offset) .DEREF referem -se à memória apontada por um símbolo (que deve ser do tipo de ponteiro). A expressão é *(symbol + offset) , que requer duas operações de carga para mapear para montagem. Somente DEREF e as variáveis DIRECT podem ser alvos de atribuição ou valor L.IMMEDIATE mantém um número constante ou string. Avaliação de operandos imediatos faz dobragem constante automaticamente.O analisador é descida recursiva codificada à mão, com as peças principais divididas em src/parser/declaração.c, src/parser/inicializer.c, src/parser/expressão.c e src/parser/declaration.c. O gráfico de fluxo de controle atual de função e o bloco básico ativo atual nesse gráfico são passados como argumentos para cada produção. O gráfico é construído gradualmente à medida que as novas instruções de código de três endereços são adicionadas ao bloco atual.
O exemplo a seguir mostra a regra de análise para bitwise ou expressões, que adiciona uma nova operação IR_OP_OR ao bloco atual. A lógica em eval_expr garantirá que o value e block->expr sejam válidos, terminando em caso de erro.
static struct block *inclusive_or_expression(
struct definition *def,
struct block *block)
{
struct var value;
block = exclusive_or_expression(def, block);
while (try_consume('|')) {
value = eval(def, block, block->expr);
block = exclusive_or_expression(def, block);
block->expr = eval_or(def, block, value, eval(def, block, block->expr));
}
return block;
}
O resultado da avaliação mais recente é sempre armazenado no block->expr . A ramificação é feita instanciando novos blocos básicos e mantendo as dicas. Cada bloco básico possui um ponteiro de ramificação verdadeiro e falso para outros blocos, e é assim que as ramificações e os Gotos são modelados. Observe que em nenhum momento existe qualquer estrutura de árvore de sintaxe sendo construída. Existe apenas implicitamente na recursão.
A principal motivação para a criação de um gráfico de fluxo de controle é poder fazer a análise e otimização do fluxo de dados. Os recursos atuais aqui ainda são limitados, mas podem ser facilmente estendidos com passos e otimização adicionais e mais avançados.
A análise de vida é usada para descobrir, em todas as afirmações, que os símbolos podem ser lidos posteriormente. O algoritmo de fluxo de dados é implementado usando máscaras de bits para representar símbolos, numerando-os 1-63. Como conseqüência, a otimização funciona apenas em funções com menos de 64 variáveis. O algoritmo também deve ser muito conservador, pois não há análise de alias de ponteiro (ainda).
Usando as informações de vida, um passe de transformação que faz a eliminação da loja morta pode remover nós IR_ASSIGN que provavelmente não fazem nada, reduzindo o tamanho do código gerado.
Existem três metas de back -end: código de montagem textual, arquivos de objeto ELF e ponto para a representação intermediária. Cada objeto struct definition produzido do analisador é passado para o módulo src/back -end/compile.c. Aqui, fazemos um mapeamento da representação do gráfico de fluxo de controle intermediário até um IR de nível mais baixo, reduzindo o código para algo que representa diretamente as instruções x86_64. A definição para isso pode ser encontrada no src/back -end/x86_64/coding.h.
Dependendo dos ponteiros da função configurados no início do programa, as instruções são enviadas para o back -end do ELF ou a montagem de texto. O código para saída de montagem de texto é, portanto, muito simples, mais ou menos apenas um mapeamento entre as instruções de IR de baixo nível e seu código de montagem de sintaxe do GNU. Consulte SRC/Backend/x86_64/Assemble.c.
A saída de pontos é um pipeline separado que não precisa de IR de baixo nível a ser gerado. O módulo de compilação simplesmente encaminhará o CFG para SRC/back -end/graphviz/dot.c.
O teste é feito comparando a saída de tempo de execução dos programas compilados com o LACC e o System Compiler (CC). Uma coleção de pequenos programas independentes usados para validação pode ser encontrada no teste/ diretório. Os testes são executados usando o check.sh, que validarão saídas de pré -processamento, montagem e ELF.
$ test/check.sh bin/lacc test/c89/fact.c
[-E: Ok!] [-S: Ok!] [-c: Ok!] [-c -O1: Ok!] :: test/c89/fact.c
Um teste completo do compilador é feito passando por todos os casos de teste em uma versão auto-hospedada do LACC.
make -C test
Isso primeiro usará o bin/lacc já construído para produzir bin/bootstrap/lacc , que por sua vez é usado para construir bin/selfhost/lacc . Entre os estágios de bootstrap e autohost, os arquivos de objeto intermediário são comparados quanto à igualdade. Se tudo funcionar corretamente, esses estágios devem produzir binários idênticos. O compilador é '' bom '' quando todos os testes passam no binário autohost. Isso sempre deve ser verde, em todos os compromissos.
É difícil criar um bom conjunto de testes, cobrindo todos os casos possíveis. Para eliminar os bugs, podemos usar o CSmith para gerar programas aleatórios adequados para validação.
./csmith.sh
O script csmith.sh executa o CSmith para gerar uma sequência infinita de programas aleatórios até que algo falhe no chicote de teste. Normalmente, ele executa milhares de testes sem falha.
Os programas gerados pelo CSmith contêm um conjunto de variáveis globais e funções que fazem mutações nelas. No final, uma soma de verificação do estado completo de todas as variáveis é emitida. Essa soma de verificação pode ser comparada com diferentes compiladores para encontrar discretâncias ou bugs. Consulte Doc/Random.c para um programa de exemplo gerado pelo CSmith, que também é compilado corretamente pelo LACC.
Quando um bug é encontrado, podemos usar crédito para fazer uma repro mínima. Isso acabará como um novo caso de teste no pacote de teste normal.
Algum esforço foi feito para tornar o próprio compilador rápido (embora o código gerado ainda seja muito não otimizado). Servindo como um teste de referência de desempenho e teste de correção, usamos o mecanismo de banco de dados SQLite. O código -fonte é distribuído como um arquivo C ~ 7 MB (7184634 bytes), abrangendo mais de 200 K linhas (incluindo comentários e espaço em branco), o que é perfeito para testar o estresse do compilador.
As experiências a seguir foram executadas em um laptop com uma CPU i5-7300U, compilando a versão 3.20.1 do SQLite3. As medições são feitas de compilação ao código do objeto (-C).
São necessários menos de 200 ms para compilar o arquivo com o LACC, mas, em vez do tempo, analisamos uma amostra mais precisa dos ciclos e instruções da CPU executadas. Os dados do contador de desempenho de hardware são coletados com perf stat e as alocações de memória com valgrind --trace-children=yes . Em Valgrind, estamos contando apenas contribuições do próprio compilador (executável cc1 ) enquanto executamos o GCC.
Os números para o LACC são de uma construção otimizada produzida por make CC='clang -O3 -DNDEBUG' bin/lacc . Cada compilador é chamado com argumentos -c sqlite/sqlite3.c -o foo.o
| Compilador | Ciclos | Instruções | Alocações | Bytes alocados | Tamanho do resultado |
|---|---|---|---|---|---|
| LACC | 412.334.334 | 619.466.003 | 49.020 | 24.244.107 | 1.590.482 |
| TCC (0.9.27) | 245.142.166 | 397.514.762 | 2.909 | 23.020.917 | 1.409.716 |
| GCC (9.3.0) | 9.958.514.599 | 14.524.274.665 | 1.546.790 | 1.111.331.606 | 1.098.408 |
| Clang (10.0.0) | 4.351.456.211 | 5.466.808.426 | 1.434.072 | 476.529.342 | 1.116.992 |
Ainda há trabalho a ser feito para se aproximar do TCC, que provavelmente é um dos compiladores C mais rápidos disponíveis. Ainda assim, estamos a uma distância razoável do desempenho do TCC e uma ordem de magnitude melhor que o GCC e o CLANG.
Na tabela acima, podemos ver que o tamanho do arquivo de objeto SQLite gerado pelo LACC é maior do que o gerado por outros compiladores, sugerindo que produzimos um código menos ideal.
Para comparar a qualidade relativa do código gerado a partir de LACC e GCC, podemos observar o número de instruções dinâmicas executadas pelo binário autohost versus um binário construído pelo GCC. Executamos o mesmo teste acima, compilando SQLite em código de objeto. Os alvos para o teste são a construção do compilador padrão ( bin/lacc ) produzido pelo GCC e o binário autohost ( bin/selfhost/lacc ) produzido pelo LACC. Ambos os alvos são produzidos sem otimizações ativadas e sem definir NDEBUG .
| Compilador | Ciclos | Instruções |
|---|---|---|
| LACC | 946.315.653 | 1.481.608.726 |
| LACC (Autohost) | 1.417.112.690 | 2.046.996.115 |
O binário auto -adquirido é mais lento para compilar o sqlite do que o compilador construído pelo GCC, mostrando que o LACC realmente gera código bastante ineficiente. Melhorar o back -end com melhor seleção de instruções é uma prioridade; portanto, esses números devem se aproximar no futuro.
Estes são alguns recursos úteis para a criação de um compilador C direcionando x86_64.
