Back-end e Geração Final de Código

Compiladores: Back-end e Geração Final de Código
Bem-vindo ao curso de compiladores! Neste módulo, vamos explorar o fascinante mundo do back-end de compiladores e a geração final de código, etapa crucial que transforma representações intermediárias em instruções executáveis pela máquina.
O Papel do Back-end na Compilação
O back-end de um compilador representa a etapa final do processo de compilação, responsável por transformar a representação intermediária (gerada pelo front-end) em código de máquina ou assembly executável.
Enquanto o front-end se preocupa com a análise sintática e semântica do código-fonte, o back-end concentra-se em produzir código eficiente que possa ser executado diretamente pelo hardware alvo.
Diagrama simplificado do processo de compilação com destaque para a fase de back-end.
Cadeia de Compilação Revisitada
Código-fonte
Programa escrito em linguagem de alto nível (C, Java, etc.)
Front-end
Análise léxica, sintática e semântica, gerando árvore sintática e código intermediário
Back-end
Tradução para assembly, alocação de registradores, otimização e geração final de código
Código executável
Instruções de máquina prontas para execução no hardware alvo
Tarefas Típicas do Back-end
Tradução do Código Intermediário
Conversão da representação intermediária (IR) em instruções assembly ou de máquina específicas para a arquitetura alvo.
Alocação de Registradores
Decisão sobre quais variáveis serão armazenadas em registradores (acesso rápido) ou na memória, otimizando o uso dos recursos limitados da CPU.
Otimização de Código
Aplicação de técnicas para melhorar o desempenho do código gerado, como eliminação de código morto, peephole optimization e loop unrolling.
Geração de Código Final
Produção do código de máquina final ou assembly, incluindo a organização das seções de dados e código no formato exigido pelo sistema operacional.
Entrada para o Back-end: Código Intermediário
O back-end recebe como entrada uma representação intermediária (IR) do código-fonte, que pode ser:
Árvore Sintática Abstrata (AST)
Código de Três Endereços (TAC)
Representação em triplas ou quádruplas
Outras formas de IR (SSA, LLVM IR, etc.)
Estas representações abstraem detalhes da linguagem de origem e facilitam a geração de código para diferentes arquiteturas.
Exemplo de representações intermediárias: AST e TAC para uma expressão simples.
Exemplo de Código Intermediário
Considere a expressão: a = b + c * d
Em Código de Três Endereços (TAC):
t1 = c * d
t2 = b + t1
a = t2
Esta representação intermediária é independente da arquitetura e serve como entrada ideal para o back-end do compilador.
Em formato de árvore (AST):
A estrutura hierárquica da AST preserva a ordem de avaliação das operações.
O que é Assembly?
Assembly é uma linguagem de programação de baixo nível que representa as instruções do processador em um formato simbólico e legível por humanos.
Cada instrução assembly normalmente corresponde a uma única instrução de máquina, oferecendo controle direto sobre o hardware, mas com sintaxe mais compreensível que código binário.
Diferentes arquiteturas de processadores (x86, ARM, RISC-V) possuem conjuntos de instruções assembly distintos.
O código assembly é uma representação simbólica das instruções de máquina binárias.
Modelo Didático de Máquina
1
Registradores de Propósito Geral
AX, BX, CX, DX: Registradores primários
SI, DI: Registradores de índice
SP: Ponteiro de pilha
BP: Ponteiro de base
2
Registradores de Controle
IP: Ponteiro de instrução
FLAGS: Indicadores de resultado (Zero, Sinal, etc.)
3
Segmentos de Memória
CS: Segmento de código
DS: Segmento de dados
SS: Segmento de pilha
Este modelo simplificado, inspirado na arquitetura x86, será utilizado em nossos exemplos didáticos para facilitar a compreensão dos conceitos de geração de código.
Instruções Assembly Básicas
Tradução de Expressões para Assembly
A tradução de expressões para assembly segue um padrão relativamente simples:
Avaliar operandos (pode envolver cálculos recursivos)
Carregar operandos em registradores
Executar a operação
Armazenar o resultado
Expressões complexas são decompostas em operações mais simples, seguindo a ordem de precedência dos operadores.
O processo de tradução requer um mapeamento cuidadoso entre variáveis do programa e registradores ou posições de memória.
Exemplo: Tradução de Expressões Simples
Código-fonte:
a = b + c;
Código intermediário (TAC):
t1 = b + c
a = t1
Código assembly:
MOV AX, [b]    ; Carrega b em AX
ADD AX, [c]    ; Soma c a AX
MOV [a], AX    ; Armazena resultado em a
Onde [x] representa o endereço de memória da variável x.
Tradução de Expressões Complexas
Código-fonte:
x = (a + b) * (c - d);
Código intermediário (TAC):
t1 = a + b
t2 = c - d
t3 = t1 * t2
x = t3
Código assembly:
MOV AX, [a] ; Carrega a em AX
ADD AX, [b] ; Soma b a AX
MOV BX, AX ; Salva (a+b) em BX
MOV AX, [c] ; Carrega c em AX
SUB AX, [d] ; Subtrai d de AX
MUL BX ; Multiplica AX por BX
MOV [x], AX ; Armazena resultado em x
Sistema de Execução: Stack e Heap
Stack (Pilha)
Região de memória gerenciada automaticamente que segue a estrutura LIFO (Last In, First Out). Usada para:
Armazenar variáveis locais
Endereços de retorno de funções
Salvar estado de registradores
Passar parâmetros para funções
Heap (Monte)
Região de memória para alocação dinâmica. Características:
Gerenciada pelo programador
Usada para objetos de tamanho variável
Requer alocação e liberação explícitas
Sujeita a fragmentação
Chamada de Função e Controle de Fluxo
Preparação para Chamada
Os argumentos da função são empilhados na stack, em ordem inversa (do último para o primeiro).
Salvamento do Contexto
O endereço de retorno (próxima instrução após a chamada) é colocado na pilha.
Transferência de Controle
O fluxo de execução salta para o início da função chamada (usando JMP ou CALL).
Execução da Função
A função é executada, com acesso aos parâmetros através da pilha.
Retorno
O valor de retorno é colocado em um registrador designado, o endereço de retorno é recuperado da pilha, e o controle volta à função chamadora.
Exemplo de Chamada de Função
Código-fonte:
int soma(int a, int b) {
    return a + b;
}

int main() {
    int x = 5;
    int y = 10;
    int z = soma(x, y);
    return 0;
}
Código assembly (simplificado):
soma:
 PUSH BP ; Salva BP antigo
 MOV BP, SP ; BP aponta para stack frame
 MOV AX, [BP+8] ; Carrega primeiro parâmetro (a)
 ADD AX, [BP+12]; Soma segundo parâmetro (b)
 POP BP ; Restaura BP
 RET ; Retorna (AX contém resultado)

main:
 MOV [x], 5 ; x = 5
 MOV [y], 10 ; y = 10
 PUSH [y] ; Empilha segundo argumento
 PUSH [x] ; Empilha primeiro argumento
 CALL soma ; Chama função soma
 ADD SP, 8 ; Limpa parâmetros da pilha
 MOV [z], AX ; z = resultado da soma
 MOV AX, 0 ; Retorno = 0
 RET ; Retorna para sistema
Organização de Variáveis na Memória
Variáveis Globais
Alocadas na seção de dados do programa
Endereço fixo durante toda a execução
Acesso direto por endereço absoluto
Visíveis em todo o programa
Variáveis Locais
Alocadas na pilha (stack)
Endereço relativo ao frame pointer (BP)
Criadas na entrada da função
Destruídas na saída da função
Escopo limitado à função
Acesso à Memória e Endereçamento
1
Endereçamento Direto
Acessa diretamente um endereço de memória específico.
MOV AX, [1000]   ; Carrega em AX o valor do endereço 1000
2
Endereçamento Indireto
Usa um registrador como ponteiro para o endereço de memória.
MOV BX, 1000    ; BX contém o endereço
MOV AX, [BX]    ; Carrega em AX o valor apontado por BX
3
Endereçamento Base + Deslocamento
Combina um registrador base com um deslocamento fixo.
MOV BP, 2000    ; BP é o registrador base
MOV AX, [BP+8]  ; Carrega em AX o valor do endereço BP+8
4
Endereçamento Indexado
Útil para arrays, combina um endereço base com um índice em registrador.
MOV SI, 4 ; SI é o índice (multiplicado por tamanho do item)
MOV AX, [array+SI] ; Carrega o elemento array[1] (assumindo int)
Ferramentas para Geração de Código
Formatos de Saída
Texto assembly (.asm, .s): Legível por humanos, requer um montador
Código objeto (.o, .obj): Binário parcialmente ligado
Executável (.exe, .elf): Binário final pronto para execução
A escolha do formato depende dos objetivos do compilador e do ambiente de destino.
Ferramentas como assemblers (montadores) e linkers (ligadores) processam a saída do back-end para criar o executável final.
Assembly Fictício para Ensino
Para fins didáticos, podemos usar um "assembly fictício" simplificado que mantenha a essência da geração de código sem as complexidades específicas de arquiteturas reais.
Vantagens do Assembly Fictício
Foco nos conceitos fundamentais
Remoção de detalhes de arquitetura complexos
Facilidade de entendimento e implementação
Transferência de conhecimento para arquiteturas reais
Características
Conjunto reduzido de registradores
Instruções básicas com sintaxe clara
Modelo de memória simplificado
Sistemas de endereçamento comuns
Sem otimizações específicas de arquitetura
Gerador de Código com Estrutura de Template
Uma abordagem comum para a geração de código é o uso de templates ou padrões predefinidos para cada tipo de instrução ou estrutura.
Para cada padrão da linguagem intermediária, o gerador seleciona um template correspondente de código assembly e preenche os espaços com os operandos específicos.
# Exemplo de templates em pseudocódigo
templates = {
 "assign": "MOV {dest}, {src}",
 "add": "MOV AX, {op1}\nADD AX, {op2}\nMOV {dest}, AX",
 "sub": "MOV AX, {op1}\nSUB AX, {op2}\nMOV {dest}, AX",
 "if": "CMP {cond}, 0\nJE {else_label}",
 # mais templates...
}
Implementação de Gerador em Python
class GeradorCodigo:
 def __init__(self):
 self.codigo = []
 self.contador_label = 0
 
 def gerar_label(self):
 label = f"L{self.contador_label}"
 self.contador_label += 1
 return label
 
 def emitir(self, instrucao):
 self.codigo.append(instrucao)
 
 def gerar_atribuicao(self, dest, src):
 self.emitir(f"MOV AX, {src}")
 self.emitir(f"MOV {dest}, AX")
 
 def gerar_operacao(self, dest, op1, op2, operador):
 self.emitir(f"MOV AX, {op1}")
 if operador == "+":
 self.emitir(f"ADD AX, {op2}")
 elif operador == "-":
 self.emitir(f"SUB AX, {op2}")
 elif operador == "*":
 self.emitir(f"MOV BX, {op2}")
 self.emitir(f"MUL BX")
 # outros operadores...
 self.emitir(f"MOV {dest}, AX")
 
 def obter_codigo(self):
 return "\n".join(self.codigo)
Tradução de Estruturas de Controle
If-Else
# Código fonte
if (x > 0) {
    y = 1;
} else {
    y = 0;
}

# Assembly
    MOV AX, [x]
    CMP AX, 0
    JLE else_label
    MOV [y], 1
    JMP end_if
else_label:
    MOV [y], 0
end_if:
While Loop
# Código fonte
while (i < 10) {
 sum = sum + i;
 i = i + 1;
}

# Assembly
loop_start:
 MOV AX, [i]
 CMP AX, 10
 JGE loop_end
 MOV AX, [sum]
 ADD AX, [i]
 MOV [sum], AX
 MOV AX, [i]
 ADD AX, 1
 MOV [i], AX
 JMP loop_start
loop_end:
Uso Eficiente de Registradores
Alocação de Registradores
O processo de determinar quais variáveis ficam em registradores (acesso rápido) e quais ficam na memória (acesso mais lento).
Problema NP-completo, frequentemente resolvido com heurísticas e coloração de grafos.
Registradores Temporários
Usados para armazenar resultados intermediários de cálculos. Estratégias comuns:
Pré-alocação de registradores para cada temporário
Alocação sob demanda com spilling (descarregamento para a memória)
Reutilização de registradores quando possível
Análise de Vida Útil
Determina onde uma variável "nasce" (primeira atribuição) e "morre" (último uso), permitindo reutilizar registradores para variáveis com períodos de vida não sobrepostos.
Otimizações no Back-end
Peephole Optimization
Examina uma pequena sequência de instruções ("janela") e a substitui por uma versão mais eficiente.
# Antes da otimização
MOV AX, 5
MOV BX, AX

# Após otimização
MOV BX, 5
Eliminação de Código Morto
Remove instruções que não afetam o resultado final do programa.
# Antes da otimização
MOV AX, 10
ADD AX, 5
MOV AX, 20  ; Sobrescreve cálculo anterior

# Após otimização
MOV AX, 20
Strength Reduction
Substitui operações caras por equivalentes mais baratas.
# Antes da otimização
MUL BX, 2 ; Multiplicação

# Após otimização
ADD BX, BX ; Adição é mais rápida
Exercício Guiado: Tradução Manual
Vamos traduzir a expressão: result = (x + y) * z / 2
Assumindo que todas as variáveis são inteiras e já foram declaradas, siga os passos:
Decompor a expressão em operações mais simples
Determinar a ordem de avaliação
Alocar registradores para valores temporários
Escrever as instruções assembly correspondentes
Solução:
; Calcular (x + y)
MOV AX, [x] ; Carrega x em AX
ADD AX, [y] ; Adiciona y a AX
MOV BX, AX ; Salva (x + y) em BX

; Multiplicar por z
MOV AX, BX ; Carrega (x + y) em AX
MOV CX, [z] ; Carrega z em CX
MUL CX ; AX = AX * CX

; Dividir por 2
MOV BX, 2 ; Carrega 2 em BX
DIV BX ; AX = AX / BX

; Armazenar resultado
MOV [result], AX ; Salva resultado
Mini-Compilador: Arquitetura
Parser
Analisa o código-fonte e gera a AST ou TAC
Analisador Semântico
Verifica tipos e escopo das variáveis
Gerador de Código Intermediário
Produz a representação intermediária otimizada
Gerador de Código Final
Traduz para assembly ou código de máquina
Mini-Compilador: Implementação de Back-end
import sys

class GeradorCodigoAssembly:
 def __init__(self):
 self.codigo = []
 self.contador_temp = 0
 self.contador_label = 0
 self.variaveis = {}
 
 def gerar_temp(self):
 temp = f"t{self.contador_temp}"
 self.contador_temp += 1
 return temp
 
 def gerar_label(self):
 label = f"L{self.contador_label}"
 self.contador_label += 1
 return label
 
 def emitir(self, instrucao):
 self.codigo.append(instrucao)
 
 def processar_tac(self, tac_instrucoes):
 for instrucao in tac_instrucoes:
 partes = instrucao.split()
 
 if len(partes) == 3 and partes[1] == "=":
 # Atribuição simples: a = b
 dest, _, src = partes
 self.emitir(f"MOV AX, {src}")
 self.emitir(f"MOV {dest}, AX")
 
 elif len(partes) == 5 and partes[1] == "=":
 # Operação binária: a = b op c
 dest, _, op1, op, op2 = partes
 self.emitir(f"MOV AX, {op1}")
 
 if op == "+":
 self.emitir(f"ADD AX, {op2}")
 elif op == "-":
 self.emitir(f"SUB AX, {op2}")
 elif op == "*":
 self.emitir(f"MOV BX, {op2}")
 self.emitir(f"MUL BX")
 elif op == "/":
 self.emitir(f"MOV BX, {op2}")
 self.emitir(f"DIV BX")
 
 self.emitir(f"MOV {dest}, AX")
 
 # Outros tipos de instruções...
 
 def obter_codigo(self):
 return "\n".join(self.codigo)

# Exemplo de uso
tac = [
 "t1 = a + b",
 "t2 = t1 * c",
 "result = t2"
]

gerador = GeradorCodigoAssembly()
gerador.processar_tac(tac)
print(gerador.obter_codigo())
Exemplo Completo: Programa de Soma e Subtração
Código-fonte:
// Programa simples de cálculo
int main() {
    int a = 10;
    int b = 5;
    int soma = a + b;
    int diferenca = a - b;
    
    if (soma > 10) {
        return soma;
    } else {
        return diferenca;
    }
}
Código assembly gerado:
section .data
 a dd 10 ; int a = 10
 b dd 5 ; int b = 5
 soma dd 0 ; int soma
 diferenca dd 0 ; int diferenca

section .text
global main
main:
 ; Calcular soma = a + b
 MOV EAX, [a]
 ADD EAX, [b]
 MOV [soma], EAX
 
 ; Calcular diferenca = a - b
 MOV EAX, [a]
 SUB EAX, [b]
 MOV [diferenca], EAX
 
 ; if (soma > 10)
 MOV EAX, [soma]
 CMP EAX, 10
 JLE else_branch
 
 ; return soma
 MOV EAX, [soma]
 JMP end_if
 
else_branch:
 ; return diferenca
 MOV EAX, [diferenca]
 
end_if:
 RET
Resumo e Próximos Passos
O que Aprendemos
Estrutura e função do back-end de compiladores
Tradução de código intermediário para assembly
Organização da memória e acesso a variáveis
Implementação de estruturas de controle
Técnicas básicas de geração de código
Tópicos Avançados
Otimizações avançadas (loop unrolling, inlining)
Algoritmos de alocação de registradores
JIT (Just-In-Time) compilation
Compilação para GPUs e processadores vetoriais
Sistemas de tipos em tempo de execução
Projetos Práticos
Implementar um compilador completo para linguagem simples
Adicionar otimizações ao back-end
Gerar código para uma arquitetura real (x86, ARM)
Criar visualizações do processo de compilação
Recursos Adicionais
Livros: "Engineering a Compiler", "Compilers: Principles, Techniques, and Tools"
Frameworks: LLVM, GCC
Tutoriais online e documentação de linguagens assembly