Geração de Código em Compiladores

Geração de Código em Compiladores: Da Representação Intermediária ao Código de Máquina
Aprenda os fundamentos e técnicas de geração de código em compiladores, com foco na transformação eficiente do código intermediário para código de máquina utilizando registradores.
Introdução à Geração de Código
O que veremos nesta aula
A geração de código é a fase final do processo de compilação, onde transformamos a representação intermediária em instruções executáveis pelo processador. Nesta aula, exploraremos como esse processo ocorre, com ênfase especial na alocação de registradores.
Você aprenderá as técnicas fundamentais para traduzir código de três endereços (TAC) em código de máquina, considerando as limitações dos recursos computacionais e otimizando o desempenho do programa compilado.
A geração de código é a etapa final do processo de compilação, transformando representações intermediárias em código executável.
Onde Estamos na Cadeia do Compilador
1
Análise Léxica
Transforma o código-fonte em tokens
2
Análise Sintática
Organiza tokens em estruturas gramaticais
3
Análise Semântica
Verifica tipos e escopo
4
Geração de Código Intermediário
Cria representação independente de máquina
5
Geração de Código
Traduz para código de máquina
Estamos aqui!
Após percorrer todas as etapas anteriores, chegamos à fase final: a geração de código. Neste ponto, já temos uma representação intermediária validada e estamos prontos para produzir o código que será executado diretamente pelo processador.
O Que é Geração de Código?
A geração de código é o processo de traduzir a representação intermediária de um programa em código de máquina executável pelo processador alvo. Esta etapa transforma abstrações de alto nível em instruções específicas de hardware.
Entrada
Código intermediário (geralmente TAC - Código de Três Endereços)
Processo
Mapeamento de operações abstratas para instruções específicas da arquitetura
Saída
Código de máquina otimizado para a arquitetura alvo
Desafios
Alocação eficiente de registradores, seleção de instruções, otimização local
Transformações no Processo de Compilação
1
AST (Árvore Sintática Abstrata)
Estrutura hierárquica que representa o programa fonte
2
Código Intermediário
Representação independente de máquina (TAC)
3
Código de Máquina
Instruções específicas para a arquitetura alvo
O processo de compilação envolve múltiplas transformações de representação. A AST é convertida em código intermediário para facilitar otimizações, que por sua vez é traduzido para código de máquina específico para o processador alvo.
O Papel da Geração de Código no Compilador
A geração de código é a ponte final entre a representação abstrata do programa e sua execução real no hardware. Seu papel é crucial pois determina:
A eficiência do código executável final
O uso apropriado dos recursos do processador
A corretude da execução do programa
O desempenho das aplicações compiladas
Um gerador de código eficiente maximiza o desempenho do programa compilado, enquanto preserva a semântica do código original.
Esta fase é frequentemente chamada de "backend" do compilador, em contraste com o "frontend" que lida com análise léxica, sintática e semântica.
Características do Código de Máquina
Específico para Arquitetura
Cada processador tem seu próprio conjunto de instruções (ISA)
Baixo Nível
Operações atômicas e primitivas que o processador executa diretamente
Orientado a Registradores
Utiliza registradores do processador para operações rápidas
Gerenciamento de Memória
Instruções específicas para carregar e armazenar dados na memória
O código de máquina representa as instruções em sua forma mais básica, muitas vezes como sequências de bytes que o processador interpreta diretamente. Estas instruções são projetadas para manipular dados em registradores e memória de maneira eficiente.
Exemplo: Da Expressão ao Código de Máquina
Expressão Original
a = b + c * d
Código Intermediário (TAC)
t1 = c * d
a = b + t1
Código de Máquina (ARM-like)
LOAD R1, c    // Carrega c em R1
LOAD R2, d    // Carrega d em R2
MUL R3, R1, R2 // R3 = R1 * R2
LOAD R4, b    // Carrega b em R4
ADD R5, R4, R3 // R5 = R4 + R3
STORE a, R5   // Armazena R5 em a
A tradução de uma expressão aritmética para código de máquina envolve a decomposição em operações básicas e o uso eficiente de registradores.
Impacto na Performance: Uso de Registradores
O uso eficiente de registradores é crucial para o desempenho do código gerado. Registradores são unidades de armazenamento extremamente rápidas dentro do processador, oferecendo acesso muito mais veloz que a memória principal.
Acesso Rápido
Registradores são 100-200 vezes mais rápidos que acessos à memória principal
Quantidade Limitada
Processadores modernos têm entre 8 e 32 registradores de propósito geral
Localidade de Referência
Manter dados acessados frequentemente em registradores reduz latência
Código de Três Endereços (TAC)
O Código de Três Endereços (TAC) é uma representação intermediária comumente usada em compiladores. Cada instrução tem no máximo três operandos e representa uma única operação:
x = y op z
x = op y
x = y
goto L
if x goto L
if x relop y goto L
Esta representação facilita a tradução para código de máquina por ser estruturalmente similar a instruções de baixo nível.
O TAC simplifica a tradução para código de máquina ao decompor expressões complexas em operações atômicas com no máximo três operandos.
Tradução de Operações Aritméticas
1
Identificar Operandos
Determinar a localização (registrador ou memória) de cada operando na instrução TAC
2
Carregar Valores
Se os operandos estiverem na memória, usar instruções LOAD para trazê-los para registradores
3
Executar Operação
Aplicar a instrução aritmética correspondente (ADD, SUB, MUL, DIV) nos registradores
4
Armazenar Resultado
Salvar o resultado em um registrador ou na memória, dependendo de seu uso futuro
A tradução eficiente de operações aritméticas requer um balanço entre manter valores em registradores para operações futuras e liberar registradores quando necessário.
Tradução de Estruturas de Controle
Tradução de if-then-else
# TAC
if x > y goto L1
z = 0
goto L2
L1: z = 1
L2: ...

# Código de máquina
LOAD R1, x
LOAD R2, y
CMP R1, R2
BGT L1    # Branch if Greater Than
MOV R3, 0
B L2      # Unconditional branch
L1: MOV R3, 1
L2: ...
Tradução de while
# TAC
L1: if x <= 0 goto L2
    x = x - 1
    goto L1
L2: ...

# Código de máquina
L1: LOAD R1, x
    CMP R1, 0
    BLE L2    # Branch if Less or Equal
    SUB R1, R1, 1
    STORE x, R1
    B L1
L2: ...
A tradução de estruturas de controle envolve a geração de instruções de salto condicional e incondicional, seguindo a lógica definida no código intermediário.
O Que São Registradores?
Registradores são unidades de armazenamento de alta velocidade incorporadas diretamente no processador. Diferente da memória principal, registradores:
São extremamente rápidos (acesso em um ciclo de clock)
Existem em quantidade muito limitada (geralmente 8-32)
São utilizados para armazenar operandos e resultados de operações
Possuem tamanho fixo (32 ou 64 bits em processadores modernos)
Os registradores são componentes fundamentais da arquitetura do processador, servindo como unidades de armazenamento ultrarrápidas para operações em andamento.
Por Que a Alocação de Registradores é um Problema?
A alocação de registradores é um desafio fundamental na geração de código devido à disparidade entre o número de variáveis em um programa e a quantidade limitada de registradores disponíveis.
Recurso Escasso
Número limitado de registradores vs. potencialmente centenas de variáveis
Impacto no Desempenho
Cada acesso à memória é 100-200 vezes mais lento que acesso a registrador
Complexidade Algorítmica
A alocação ótima de registradores é um problema NP-completo
Mapeamento de Variáveis para Registradores
O mapeamento de variáveis para registradores envolve decidir:
Quais variáveis manter em registradores
Qual registrador atribuir a cada variável
Quando mover variáveis entre registradores e memória
Um bom mapeamento minimiza os acessos à memória e maximiza o reuso de registradores, considerando o tempo de vida das variáveis.
A análise do tempo de vida das variáveis é essencial para determinar quando um registrador pode ser reutilizado para armazenar diferentes variáveis ao longo da execução do programa.
Técnicas Básicas de Alocação
Algoritmo Ingênuo
Carrega operandos da memória para registradores antes de cada operação e armazena resultados de volta na memória imediatamente. Simples, mas muito ineficiente devido aos frequentes acessos à memória.
Algoritmo Round-Robin
Atribui registradores em um ciclo rotativo. Quando todos os registradores estão ocupados, o próximo registrador é escolhido de acordo com alguma política (como o menos recentemente usado).
Alocação por Blocos Básicos
Aloca registradores dentro de blocos básicos (sequências de instruções sem desvios), permitindo otimizações locais sem considerar o fluxo entre blocos.
Estas técnicas básicas são simples de implementar, mas produzem código subótimo em comparação com métodos mais sofisticados que consideram o tempo de vida das variáveis.
Spilling: Quando a Memória é Necessária
O "spilling" ocorre quando não há registradores suficientes disponíveis para todas as variáveis ativas. Nesse caso, algumas variáveis precisam ser temporariamente armazenadas na memória.
Decisões de Spilling
Selecionar quais variáveis "derramar" para a memória baseado em critérios como frequência de uso, custo de recálculo, ou tempo até o próximo uso
Código de Spill
Gerar instruções adicionais para salvar e recarregar valores entre registradores e memória
Impacto no Desempenho
Cada operação de spilling adiciona acessos à memória, potencialmente reduzindo o desempenho
Técnica Linear Scan
O algoritmo Linear Scan é uma técnica de alocação de registradores que oferece um bom equilíbrio entre qualidade do código e complexidade de implementação:
Ordena os intervalos de vida das variáveis pelo ponto de início
Percorre a lista ordenada, alocando registradores
Quando todos os registradores estão em uso, escolhe uma variável para spilling
Tipicamente escolhe a variável cujo intervalo termina mais tarde
O Linear Scan percorre os intervalos de vida das variáveis em ordem cronológica, tornando decisões de alocação à medida que encontra o início e o fim de cada intervalo.
Esta técnica é amplamente utilizada em compiladores JIT (Just-In-Time) devido à sua eficiência computacional e qualidade razoável do código gerado.
Grafo de Interferência
O grafo de interferência é uma representação que mostra quais variáveis não podem ser alocadas ao mesmo registrador por estarem "vivas" simultaneamente.
Construção
Cada variável é um nó; existe uma aresta entre duas variáveis se seus tempos de vida se sobrepõem
Coloração
Atribuir "cores" (registradores) de modo que nós adjacentes tenham cores diferentes
Aplicação
Base para algoritmos sofisticados como Coloração de Grafo e Graph Coloring with Coalescing
A alocação baseada em grafos produz código de alta qualidade, mas tem maior complexidade computacional que métodos como Linear Scan.
Exemplo de Alocação com 3 Registradores
Código TAC
a = b + c
d = a * 2
e = d - c
f = e + b
Análise de Tempo de Vida
b: linha 1 até linha 4
c: linha 1 até linha 3
a: linha 1 até linha 2
d: linha 2 até linha 3
e: linha 3 até linha 4
f: apenas linha 4
Alocação com Linear Scan
# R1=b, R2=c
LOAD R1, b
LOAD R2, c
ADD R3, R1, R2   # R3=a
MUL R3, R3, 2    # R3=d (reutiliza R3)
SUB R3, R3, R2   # R3=e (reutiliza R3)
ADD R3, R3, R1   # R3=f (reutiliza R3)
STORE f, R3
Com apenas 3 registradores, conseguimos executar todo o código sem nenhum spilling, reutilizando registradores quando as variáveis não são mais necessárias.
Comparação entre Estratégias de Alocação
A escolha da estratégia de alocação de registradores depende do equilíbrio desejado entre tempo de compilação e qualidade do código gerado, além das características específicas da arquitetura alvo.
Modelo de Código de Máquina Fictício
Para facilitar o aprendizado, utilizaremos um modelo simplificado de código de máquina com características comuns a várias arquiteturas reais:
# Instruções de carregamento e armazenamento
LOAD Rx, var      # Carrega valor da variável para registrador
STORE var, Rx     # Armazena valor do registrador na variável

# Operações aritméticas
ADD Rd, Ra, Rb    # Rd = Ra + Rb
SUB Rd, Ra, Rb    # Rd = Ra - Rb
MUL Rd, Ra, Rb    # Rd = Ra * Rb
DIV Rd, Ra, Rb    # Rd = Ra / Rb

# Controle de fluxo
CMP Ra, Rb        # Compara Ra com Rb
BEQ label         # Salta para label se igual (=)
BNE label         # Salta para label se diferente (≠)
BLT label         # Salta para label se menor (<)
BGT label         # Salta para label se maior (>)
B label           # Salto incondicional
Este modelo inclui registradores de propósito geral (R0-R9) e cobre operações básicas necessárias para nossos exemplos.
Exemplo de Tradução: a = b + c
Código TAC
a = b + c
Tradução com Abordagem Ingênua
LOAD R1, b    # Carrega b em R1
LOAD R2, c    # Carrega c em R2
ADD R3, R1, R2 # R3 = R1 + R2
STORE a, R3   # Armazena R3 em a
Otimizações Possíveis
Se b ou c já estiverem em registradores de instruções anteriores, podemos reutilizá-los e evitar as operações LOAD.
A tradução de uma expressão simples como a = b + c ilustra os princípios básicos da geração de código: carregamento de operandos, execução da operação e armazenamento do resultado.
Em um compilador real, o código gerado seria influenciado pelo contexto - por exemplo, se a é usado em operações subsequentes, o resultado poderia ser mantido em um registrador em vez de ser imediatamente armazenado na memória.
Geração de Código em Python
Implementar um gerador de código em Python é uma abordagem didática para entender os conceitos fundamentais:
class Instruction:
    def __init__(self, op, dest=None, src1=None, src2=None):
        self.op = op
        self.dest = dest
        self.src1 = src1
        self.src2 = src2
    
    def __str__(self):
        if self.op == 'LOAD':
            return f"LOAD {self.dest}, {self.src1}"
        elif self.op == 'STORE':
            return f"STORE {self.src1}, {self.dest}"
        elif self.op in ['ADD', 'SUB', 'MUL', 'DIV']:
            return f"{self.op} {self.dest}, {self.src1}, {self.src2}"
        # ... outros casos ...
class CodeGenerator:
    def __init__(self):
        self.instructions = []
        self.next_reg = 0
    
    def get_register(self):
        reg = f"R{self.next_reg}"
        self.next_reg += 1
        return reg
    
    def generate_binary_op(self, op, dest, src1, src2):
        r1 = self.get_register()
        r2 = self.get_register()
        r3 = self.get_register()
        
        self.instructions.append(Instruction('LOAD', r1, src1))
        self.instructions.append(Instruction('LOAD', r2, src2))
        self.instructions.append(Instruction(op, r3, r1, r2))
        self.instructions.append(Instruction('STORE', dest, r3))
        
        return self.instructions
Este exemplo simplificado ilustra como podemos representar e gerar instruções de código de máquina a partir de código intermediário em Python.
Classe para Instruções e Tradutor
Uma implementação mais completa incluiria classes para representar diferentes aspectos da geração de código:
class TACTranslator:
    def __init__(self, register_count=8):
        self.instructions = []
        self.reg_manager = RegisterManager(register_count)
        self.variable_map = {}  # Mapeia variáveis para registradores
    
    def translate_instruction(self, tac_instr):
        if tac_instr.op == '+':
            return self._translate_add(tac_instr.dest, tac_instr.src1, tac_instr.src2)
        elif tac_instr.op == '*':
            return self._translate_mul(tac_instr.dest, tac_instr.src1, tac_instr.src2)
        # ... outros operadores ...
    
    def _translate_add(self, dest, src1, src2):
        # Lógica para traduzir adição, considerando alocação de registradores
        r1 = self._ensure_in_register(src1)
        r2 = self._ensure_in_register(src2)
        r_dest = self.reg_manager.allocate_register(dest)
        
        self.instructions.append(Instruction('ADD', r_dest, r1, r2))
        self.variable_map[dest] = r_dest
Esta estrutura permite implementar diferentes estratégias de alocação de registradores e expandir para suportar mais operações conforme necessário.
Impressão do Código Gerado
Para visualizar o código gerado, podemos implementar métodos de formatação e impressão:
def print_assembly(instructions):
    for i, instr in enumerate(instructions):
        print(f"{i:04d}: {instr}")

# Exemplo de uso
generator = CodeGenerator()
tac_instructions = [
    TACInstruction('+', 'a', 'b', 'c'),
    TACInstruction('*', 'd', 'a', '2'),
    # ... mais instruções ...
]

for tac in tac_instructions:
    generator.translate_instruction(tac)

print_assembly(generator.instructions)
A saída formatada facilitará a análise do código gerado:
0000: LOAD R0, b
0001: LOAD R1, c
0002: ADD R2, R0, R1
0003: STORE a, R2
0004: LOAD R3, a
0005: LOAD R4, 2
0006: MUL R5, R3, R4
0007: STORE d, R5
# ... outras instruções ...
Esta representação textual do código de máquina é similar ao código assembly, permitindo inspeção e depuração mais fáceis durante o desenvolvimento do gerador de código.
Construindo um Gerador de Código Simples
Definir a Representação Intermediária
Criar estruturas de dados para representar o código TAC que será traduzido
Implementar o Gerenciador de Registradores
Desenvolver uma classe que controle a alocação e liberação de registradores
Criar o Tradutor de Instruções
Implementar a lógica para traduzir cada tipo de instrução TAC para código de máquina
Adicionar Otimizações Simples
Implementar técnicas como reutilização de registradores e eliminação de cargas redundantes
Testar com Exemplos Diversos
Verificar o comportamento do gerador com diferentes padrões de código
Este processo iterativo permite construir um gerador de código funcional que demonstra os conceitos fundamentais da tradução de código intermediário para código de máquina.
Exercício Prático: TAC para Código de Máquina
Implemente um tradutor simples para converter o seguinte código TAC em código de máquina para nossa arquitetura fictícia:
x = a + b
y = c - d
z = x * y
if z > 10 goto L1
w = 0
goto L2
L1: w = z
L2: resultado = w + 5
Considere que você tem 4 registradores disponíveis (R0-R3) e implemente uma estratégia de alocação que minimize os acessos à memória.
Dica: Analise o tempo de vida das variáveis para determinar quando um registrador pode ser reutilizado.
Mini-Projeto: Função de Soma com Alocação de Registradores
Desenvolva um gerador de código para a seguinte função em pseudocódigo:
função soma_vetor(vetor, tamanho):
    total = 0
    i = 0
    enquanto i < tamanho faça:
        total = total + vetor[i]
        i = i + 1
    retornar total
Seu gerador deve:
Traduzir o pseudocódigo para TAC
Implementar alocação de registradores com Linear Scan
Gerar código de máquina otimizado
Imprimir o assembly resultante
Este mini-projeto integra os conceitos de tradução de código intermediário e alocação de registradores em um exemplo prático de processamento de vetor.
A alocação eficiente de registradores é particularmente importante em loops, onde o reuso adequado pode evitar operações de memória desnecessárias dentro do corpo do loop.
Resumo: Geração de Código e Próximos Passos
Conceitos Principais
Tradução de TAC para código de máquina, alocação de registradores, estratégias de geração de código
Técnicas Exploradas
Algoritmo Ingênuo, Linear Scan, Coloração de Grafo, gerenciamento de spilling
Implementação Prática
Estruturas de dados para representação de instruções, tradutor de TAC, impressão de código
Próxima Aula: Otimização de Código
Técnicas para melhorar o desempenho do código gerado: eliminação de código morto, propagação de constantes, otimização de loops
A geração de código é uma etapa crucial no processo de compilação, transformando representações abstratas em instruções executáveis. A alocação eficiente de registradores é um dos principais desafios desta etapa, impactando diretamente o desempenho do programa compilado.