Representacao Intermediaria
Video da aula estara disponivel em breve
Por que uma Representacao Intermediaria?
Apos as fases de analise (lexica, sintatica, semantica), o compilador precisa traduzir o programa para a linguagem-alvo. Mas traduzir diretamente da AST para assembly e problematico: cada par (linguagem-fonte, arquitetura-alvo) exigiria um tradutor diferente. A solucao e usar uma representacao intermediaria (IR) que desacopla o front-end do back-end.
Diagrama
SEM IR (M linguagens x N arquiteturas = M*N tradutores):
C --------+----> x86
Java -----+----> ARM
Python ---+----> RISC-V
Rust -----+----> MIPS
4 linguagens x 4 arquiteturas = 16 tradutores
COM IR (M + N componentes):
C ------\ /----> x86
Java ----\ /-----> ARM
+---> IR (SSA) --+
Python --/ \-----> RISC-V
Rust ---/ \----> MIPS
4 front-ends + 4 back-ends = 8 componentes
LLVM usa exatamente essa estrategia com LLVM IR!A IR serve como uma "lingua franca" entre o front-end (que entende a linguagem-fonte) e o back-end (que entende a maquina-alvo). Alem disso, muitas otimizacoes sao feitas na IR, porque ela e mais simples e uniforme que a AST ou o assembly final.
Three-Address Code (TAC)
O Three-Address Code (codigo de tres enderecos) e uma das IRs mais classicas. Cada instrucao tem no maximo tres operandos: dois fontes e um destino. Operacoes complexas sao quebradas em sequencias de instrucoes simples.
Exemplo
Expressao original: resultado = (a + b) * (c - d) + e
Three-Address Code:
t1 = a + b # primeira sub-expressao
t2 = c - d # segunda sub-expressao
t3 = t1 * t2 # multiplicacao dos intermediarios
t4 = t3 + e # soma final
resultado = t4 # atribuicao
Tipos de instrucoes TAC:
x = y op z # operacao binaria
x = op y # operacao unaria
x = y # copia
goto L # salto incondicional
if x goto L # salto condicional
if x relop y goto L # salto condicional com comparacao
param x # parametro de funcao
call p, n # chamada de funcao p com n args
return x # retorno de funcao
x = y[i] # acesso a array
x[i] = y # escrita em arrayGerando TAC a partir da AST
Vamos construir um gerador de TAC que percorre a AST e produz instrucoes de tres enderecos. Cada no da AST gera uma ou mais instrucoes, e temporarios (t1, t2, ...) sao criados conforme necessario.
Python
from dataclasses import dataclass, field
from typing import List, Union
# --- Instrucoes TAC ---
@dataclass
class TACInstruction:
"""Uma instrucao de tres enderecos."""
op: str
result: str
arg1: str = ""
arg2: str = ""
def __str__(self):
if self.op == 'copy':
return f" {self.result} = {self.arg1}"
elif self.op == 'goto':
return f" goto {self.result}"
elif self.op == 'ifgoto':
return f" if {self.arg1} goto {self.result}"
elif self.op == 'label':
return f"{self.result}:"
elif self.op == 'param':
return f" param {self.arg1}"
elif self.op == 'call':
return f" {self.result} = call {self.arg1}, {self.arg2}"
elif self.op == 'return':
return f" return {self.arg1}"
else:
return f" {self.result} = {self.arg1} {self.op} {self.arg2}"
# --- Nos AST (simplificados) ---
@dataclass
class NumberNode:
value: float
@dataclass
class VarNode:
name: str
@dataclass
class BinOpNode:
op: str
left: object
right: object
@dataclass
class AssignNode:
target: str
value: object
@dataclass
class IfNode:
condition: object
then_body: list
else_body: list = None
# --- Gerador de TAC ---
class TACGenerator:
"""Gera Three-Address Code a partir de uma AST."""
def __init__(self):
self.instructions: List[TACInstruction] = []
self.temp_count = 0
self.label_count = 0
def new_temp(self) -> str:
"""Cria um novo temporario t1, t2, ..."""
self.temp_count += 1
return f"t{self.temp_count}"
def new_label(self) -> str:
"""Cria um novo label L1, L2, ..."""
self.label_count += 1
return f"L{self.label_count}"
def emit(self, instruction: TACInstruction):
self.instructions.append(instruction)
def generate(self, node) -> str:
"""Gera TAC para um no AST. Retorna o temporario com o resultado."""
if isinstance(node, NumberNode):
t = self.new_temp()
self.emit(TACInstruction('copy', t, str(node.value)))
return t
elif isinstance(node, VarNode):
return node.name
elif isinstance(node, BinOpNode):
left = self.generate(node.left)
right = self.generate(node.right)
t = self.new_temp()
self.emit(TACInstruction(node.op, t, left, right))
return t
elif isinstance(node, AssignNode):
val = self.generate(node.value)
self.emit(TACInstruction('copy', node.target, val))
return node.target
elif isinstance(node, IfNode):
cond = self.generate(node.condition)
else_label = self.new_label()
end_label = self.new_label()
self.emit(TACInstruction('ifgoto', else_label,
f"!{cond}"))
for stmt in node.then_body:
self.generate(stmt)
self.emit(TACInstruction('goto', end_label))
self.emit(TACInstruction('label', else_label))
if node.else_body:
for stmt in node.else_body:
self.generate(stmt)
self.emit(TACInstruction('label', end_label))
return ""
def dump(self):
for instr in self.instructions:
print(instr)
# --- Exemplo ---
# resultado = (a + b) * (c - d)
ast = AssignNode(
"resultado",
BinOpNode("*",
BinOpNode("+", VarNode("a"), VarNode("b")),
BinOpNode("-", VarNode("c"), VarNode("d"))
)
)
gen = TACGenerator()
gen.generate(ast)
gen.dump()
Saida
t1 = a + b
t2 = c - d
t3 = t1 * t2
resultado = t3Static Single Assignment (SSA)
A forma SSA (Static Single Assignment) e uma variante de IR onde cada variavel e atribuida exatamente uma vez. Quando uma variavel precisa ser atribuida em mais de um ponto (por exemplo, nos dois lados de um if), usamos funcoes phi que selecionam o valor correto dependendo de qual caminho foi tomado.
Exemplo
Codigo original: TAC normal: Forma SSA:
x = 1 x = 1 x1 = 1
if (cond): if !cond goto L1 if !cond goto L1
x = x + 1 x = x + 1 x2 = x1 + 1
else: goto L2 goto L2
x = x * 2 L1: L1:
print(x) x = x * 2 x3 = x1 * 2
L2: L2:
print(x) x4 = phi(x2, x3)
print(x4)
A funcao phi(x2, x3) escolhe:
- x2 se veio do bloco "then"
- x3 se veio do bloco "else"
Por que SSA e util?
- Cada definicao e unica -> facil rastrear de onde vem cada valor
- Simplifica muitas otimizacoes (constant propagation, dead code elimination)
- LLVM IR e baseada em SSA
- GCC usa GIMPLE (que converte para SSA para otimizacoes)Niveis de IR
Na pratica, compiladores usam multiplos niveis de IR, cada um mais proximo da maquina-alvo:
Diagrama
AST (High-level)
|
v
HIR - High-level IR # Preserva loops, ifs, structs
| Exemplo: GIMPLE (GCC) # Operacoes de alto nivel
v # Tipos mantidos
MIR - Mid-level IR # Fluxo de controle explicito
| Exemplo: LLVM IR, SSA # Sem loops -> branches + labels
v # Onde a maioria das otimizacoes acontece
LIR - Low-level IR # Proximo do assembly
Exemplo: RTL (GCC), # Registros virtuais
MachineIR (LLVM) # Instrucoes quase 1:1 com ISA
Exemplo concreto - LLVM IR para "int soma(int a, int b)":
define i32 @soma(i32 %a, i32 %b) {
entry:
%result = add i32 %a, %b
ret i32 %result
}
Caracteristicas:
- Tipada (i32 = inteiro 32 bits)
- SSA (cada %var e atribuida uma vez)
- Instrucoes simples (add, ret, br, icmp)
- Independente de arquiteturaBlocos Basicos e Control Flow Graph
Para analisar e otimizar o codigo, organizamos as instrucoes TAC em blocos basicos e construimos um grafo de fluxo de controle (CFG).
Diagrama
Um bloco basico e uma sequencia maximal de instrucoes
que executa do inicio ao fim sem desvios internos:
- Entrada so pelo topo (nenhuma instrucao no meio e alvo de salto)
- Saida so pelo fundo (so a ultima instrucao pode ser branch/goto)
Algoritmo para encontrar blocos basicos:
1. Leaders (primeira instrucao de cada bloco):
- Primeira instrucao do programa
- Alvo de qualquer goto/branch
- Instrucao imediatamente apos um goto/branch
2. Cada bloco vai de um leader ate o proximo leader
Exemplo:
Instrucao Bloco
-------- -----
t1 = a + b B1 (leader: primeira instrucao)
if t1 > 0 goto L1 B1
t2 = c * d B2 (leader: apos branch)
goto L2 B2
L1: B3 (leader: alvo de goto)
t2 = c + d B3
L2: B4 (leader: alvo de goto)
resultado = t2 B4
CFG (Control Flow Graph):
+----+
| B1 |
+----+
/ \
v v
+----+ +----+
| B2 | | B3 |
+----+ +----+
\ /
v v
+----+
| B4 |
+----+
Python
from dataclasses import dataclass, field
from typing import List, Dict, Set
@dataclass
class BasicBlock:
"""Um bloco basico no CFG."""
label: str
instructions: List[str] = field(default_factory=list)
successors: List[str] = field(default_factory=list)
predecessors: List[str] = field(default_factory=list)
class CFGBuilder:
"""Constroi um Control Flow Graph a partir de instrucoes TAC."""
def __init__(self):
self.blocks: Dict[str, BasicBlock] = {}
def build(self, instructions: List[str]) -> Dict[str, BasicBlock]:
# Passo 1: Identificar leaders
leaders = {0} # Primeira instrucao
for i, instr in enumerate(instructions):
if instr.strip().startswith('goto') or \
instr.strip().startswith('if'):
if i + 1 < len(instructions):
leaders.add(i + 1)
# Alvo do salto
label = instr.split()[-1]
for j, other in enumerate(instructions):
if other.strip().startswith(f"{label}:"):
leaders.add(j)
elif instr.strip().endswith(':'):
leaders.add(i)
# Passo 2: Criar blocos
sorted_leaders = sorted(leaders)
for idx, start in enumerate(sorted_leaders):
end = sorted_leaders[idx + 1] if idx + 1 < len(sorted_leaders) else len(instructions)
block = BasicBlock(f"B{idx}", instructions[start:end])
self.blocks[block.label] = block
# Passo 3: Conectar arestas (successors/predecessors)
block_list = list(self.blocks.values())
for i, block in enumerate(block_list):
last = block.instructions[-1].strip()
if last.startswith('goto'):
target = self._find_block_for_label(last.split()[-1])
if target:
block.successors.append(target)
elif last.startswith('if'):
target = self._find_block_for_label(last.split()[-1])
if target:
block.successors.append(target)
if i + 1 < len(block_list):
block.successors.append(block_list[i + 1].label)
else:
if i + 1 < len(block_list):
block.successors.append(block_list[i + 1].label)
return self.blocks
def _find_block_for_label(self, label):
for name, block in self.blocks.items():
if any(i.strip().startswith(f"{label}:") for i in block.instructions):
return name
return NoneNo harness.os: Sessao como Representacao Intermediaria
Conexao com harness.os: Uma sessao do harness.os funciona como uma IR entre a "linguagem-fonte" (intencao do usuario) e o "codigo-alvo" (artefatos produzidos). O contexto da sessao e a IR que conecta input a output.
Quando um agente recebe uma tarefa, ele constroi um contexto intermediario antes de produzir resultados. Esse contexto e analogo a uma IR de compilador:
Python
from dataclasses import dataclass, field
from typing import List, Dict, Optional
@dataclass
class ContextChunk:
"""Um pedaco de contexto carregado na sessao."""
source: str # 'knowledge', 'rules', 'handoff', 'file'
domain: str # 'build', 'product', 'operations', 'domain'
content: str
tokens: int # custo em tokens
relevance: float # 0.0 a 1.0
@dataclass
class SessionContextIR:
"""IR que representa o contexto de uma sessao do harness.os.
Analogia com IR de compilador:
- Front-end: request parsing (entender o que o usuario quer)
- IR: este contexto (informacoes necessarias para executar)
- Back-end: code generation (produzir artefatos)
"""
task: str
chunks: List[ContextChunk] = field(default_factory=list)
total_tokens: int = 0
budget: int = 200_000 # limite de tokens da janela
def add_chunk(self, chunk: ContextChunk):
"""Adiciona contexto a IR, respeitando budget."""
if self.total_tokens + chunk.tokens > self.budget:
print(f"[WARN] Budget excedido. Ignorando: {chunk.source}")
return False
self.chunks.append(chunk)
self.total_tokens += chunk.tokens
return True
def get_context_by_domain(self, domain: str) -> List[ContextChunk]:
return [c for c in self.chunks if c.domain == domain]
def utilization(self) -> float:
"""Porcentagem do budget utilizada."""
return self.total_tokens / self.budget * 100
def dump(self):
print(f"=== SessionContextIR ===")
print(f"Task: {self.task}")
print(f"Tokens: {self.total_tokens:,} / {self.budget:,} "
f"({self.utilization():.1f}%)")
print(f"Chunks: {len(self.chunks)}")
for c in self.chunks:
print(f" [{c.source}] {c.domain} "
f"({c.tokens:,} tokens, relevance={c.relevance})")
# Exemplo de uso
session = SessionContextIR(task="Criar modulo de compiladores")
session.add_chunk(ContextChunk("handoff", "build",
"Ultima sessao: criou modulos 1-4...", 500, 0.9))
session.add_chunk(ContextChunk("knowledge", "build",
"Template HTML para licoes...", 2000, 1.0))
session.add_chunk(ContextChunk("rules", "build",
"Commit hygiene: sem co-author...", 300, 0.6))
session.dump()
Saida
=== SessionContextIR ===
Task: Criar modulo de compiladores
Tokens: 2,800 / 200,000 (1.4%)
Chunks: 3
[handoff] build (500 tokens, relevance=0.9)
[knowledge] build (2,000 tokens, relevance=1.0)
[rules] build (300 tokens, relevance=0.6)Resumo
- A representacao intermediaria desacopla front-end e back-end, reduzindo M*N tradutores para M+N componentes
- Three-Address Code (TAC) usa instrucoes com no maximo tres operandos, facilitando otimizacao
- SSA (Static Single Assignment) garante que cada variavel e definida exatamente uma vez, com funcoes phi para pontos de juncao
- Blocos basicos e o CFG organizam o codigo para analise de fluxo
- Compiladores reais usam multiplos niveis de IR (HIR, MIR, LIR)
- No harness.os, o contexto da sessao e uma IR entre a intencao do usuario e os artefatos produzidos
Exercicio
Implemente um conversor de TAC para forma SSA. Dado um programa TAC com multiplas atribuicoes a mesma variavel, renomeie as variaveis (x -> x1, x2, ...) e insira funcoes phi nos pontos de juncao do CFG. Teste com um programa que tenha um if/else onde a mesma variavel e atribuida nos dois lados.
Verifique seu entendimento
Qual e a principal vantagem da forma SSA sobre TAC convencional?