Otimizacao
Video da aula estara disponivel em breve
Principios de Otimizacao
Otimizacao de compilador transforma o programa para que ele execute mais rapido, use menos memoria, ou consuma menos energia -- sem alterar seu comportamento observavel. O termo correto seria "melhoria" (improvement), ja que raramente alcancamos o otimo real, mas o termo "otimizacao" e consagrado na area.
Diagrama
Classificacao de otimizacoes:
Por escopo:
+------------------+-------------------------------------------+
| Otimizacao local | Dentro de um bloco basico |
| | Exemplos: constant folding, strength |
| | reduction, peephole |
+------------------+-------------------------------------------+
| Otimizacao global| Entre blocos basicos (intra-procedural) |
| | Exemplos: CSE, dead code elimination, |
| | code motion, copy propagation |
+------------------+-------------------------------------------+
| Inter-procedural | Entre funcoes |
| | Exemplos: inlining, interprocedural |
| | constant propagation |
+------------------+-------------------------------------------+
Por quando acontece:
+------------------+-------------------------------------------+
| Machine-indep. | Na IR (antes de gerar assembly) |
| | Mais portaveis, mais alto nivel |
+------------------+-------------------------------------------+
| Machine-dep. | No assembly/machine code |
| | Instruction selection, scheduling, |
| | register allocation |
+------------------+-------------------------------------------+Constant Folding e Constant Propagation
Constant folding calcula expressoes constantes em compile-time. Constant propagation substitui variaveis por seus valores constantes conhecidos.
Exemplo
Antes: Apos constant propagation + folding:
x = 3 x = 3
y = 5 y = 5
z = x + y z = 8 # 3 + 5 -> 8
w = z * 2 w = 16 # 8 * 2 -> 16
if w > 10 goto L1 goto L1 # 16 > 10 sempre true
print("nunca") # removido (dead code)
L1: L1:
print(w) print(16)
Python
from typing import Dict, List, Tuple, Optional
class ConstantFolder:
"""Realiza constant folding e propagation em instrucoes TAC."""
def __init__(self):
self.constants: Dict[str, float] = {}
def optimize(self, instructions: List[str]) -> List[str]:
result = []
for instr in instructions:
optimized = self._process(instr.strip())
if optimized is not None:
result.append(optimized)
return result
def _process(self, instr: str) -> Optional[str]:
# Atribuicao: x = expr
if '=' in instr and not instr.startswith('if'):
parts = instr.split('=', 1)
target = parts[0].strip()
expr = parts[1].strip()
# Substituir variaveis conhecidas (propagation)
tokens = expr.split()
for i, tok in enumerate(tokens):
if tok in self.constants:
tokens[i] = str(self.constants[tok])
expr = ' '.join(tokens)
# Tentar folding: se a expressao e constante, calcular
val = self._try_eval(expr)
if val is not None:
self.constants[target] = val
return f" {target} = {val}"
else:
return f" {target} = {expr}"
# Salto condicional: tentar avaliar condicao
elif instr.startswith('if'):
# Substituir variaveis na condicao
for var, val in self.constants.items():
instr = instr.replace(var, str(val))
# Tentar avaliar a condicao
cond = self._extract_condition(instr)
if cond is not None:
if cond:
label = instr.split()[-1]
return f" goto {label}"
else:
return None # Remove o branch (always false)
return f" {instr}"
return f" {instr}"
def _try_eval(self, expr: str) -> Optional[float]:
try:
return eval(expr)
except:
return None
def _extract_condition(self, instr: str) -> Optional[bool]:
try:
# "if 16 > 10 goto L1" -> eval("16 > 10")
parts = instr.split('goto')
cond = parts[0].replace('if', '').strip()
return bool(eval(cond))
except:
return None
# Exemplo
tac = [
"x = 3",
"y = 5",
"z = x + y",
"w = z * 2",
"if w > 10 goto L1",
"print('nunca')",
"L1:",
"print(w)",
]
folder = ConstantFolder()
optimized = folder.optimize(tac)
for line in optimized:
print(line)Common Subexpression Elimination (CSE)
CSE identifica expressoes que sao calculadas mais de uma vez e reutiliza o resultado anterior, evitando computacao redundante.
Exemplo
Antes: Apos CSE:
t1 = a + b t1 = a + b
t2 = t1 * c t2 = t1 * c
t3 = a + b # redundante! t3 = t1 # reutiliza t1
t4 = t3 + d t4 = t1 + d
Condicoes para CSE:
1. A expressao "a + b" ja foi calculada antes (em t1)
2. Nem 'a' nem 'b' foram redefinidos entre t1 e t3
3. Podemos substituir t3 por t1 com seguranca
Python
class CSEOptimizer:
"""Eliminacao de subexpressoes comuns."""
def optimize(self, instructions: List[Tuple[str, str, str, str]]):
"""Cada instrucao: (resultado, arg1, op, arg2)"""
available = {} # (arg1, op, arg2) -> resultado
result = []
for res, arg1, op, arg2 in instructions:
expr_key = (arg1, op, arg2)
if op and expr_key in available:
# Subexpressao ja calculada! Reutilizar.
prev_result = available[expr_key]
result.append((res, prev_result, 'copy', ''))
print(f" CSE: {res} = {arg1} {op} {arg2}"
f" -> {res} = {prev_result}")
else:
result.append((res, arg1, op, arg2))
if op:
available[expr_key] = res
# Invalidar expressoes que usam 'res' como operando
# (porque 'res' acaba de ser redefinido)
to_remove = []
for key in available:
if res in (key[0], key[2]):
to_remove.append(key)
for key in to_remove:
del available[key]
return result
# Exemplo
tac = [
("t1", "a", "+", "b"),
("t2", "t1", "*", "c"),
("t3", "a", "+", "b"), # CSE: reutilizar t1
("t4", "t3", "+", "d"),
]
cse = CSEOptimizer()
optimized = cse.optimize(tac)
# CSE: t3 = a + b -> t3 = t1Dead Code Elimination
Dead code elimination remove instrucoes cujos resultados nunca sao usados. Uma variavel e "morta" se seu valor nunca e lido antes de ser redefinida ou de o programa terminar.
Exemplo
Antes: Apos dead code elimination:
t1 = a + b t1 = a + b
t2 = c * d # dead! resultado = t1 + e
resultado = t1 + e
t3 = f - g # dead!
t2 e t3 nunca sao usados -> podem ser removidos.
Liveness analysis (analise ao contrario):
Comeca do fim do bloco, volta ao inicio.
Uma variavel e "viva" se sera lida no futuro.
Instrucao Live depois Live antes
--------- ----------- -----------
resultado = t1 + e {resultado} {t1, e}
t2 = c * d {t1, e} {t1, e, c, d} # t2 nao e live!
t1 = a + b {t1, e, c, d} {a, b, e, c, d}
t2 nao e live apos sua definicao -> DEAD CODE
Python
class DeadCodeEliminator:
"""Remove instrucoes cujo resultado nunca e usado."""
def eliminate(self, instructions: List[Tuple[str, str, str, str]],
live_out: set) -> List[Tuple]:
"""
instructions: lista de (result, arg1, op, arg2)
live_out: variaveis vivas apos o bloco (ex: {'resultado'})
"""
# Passo 1: Descobrir quais variaveis sao usadas
used = set(live_out)
essential = []
# Percorrer de tras para frente
for instr in reversed(instructions):
res, arg1, op, arg2 = instr
if res in used:
# Instrucao e necessaria
essential.append(instr)
used.discard(res)
# Seus operandos passam a ser usados
if arg1 and not arg1.replace('.','').isdigit():
used.add(arg1)
if arg2 and not arg2.replace('.','').isdigit():
used.add(arg2)
else:
print(f" DEAD: {res} = {arg1} {op} {arg2}")
return list(reversed(essential))
# Exemplo
tac = [
("t1", "a", "+", "b"),
("t2", "c", "*", "d"), # sera removido (dead)
("resultado", "t1", "+", "e"),
("t3", "f", "-", "g"), # sera removido (dead)
]
dce = DeadCodeEliminator()
alive = dce.eliminate(tac, {"resultado"})
print("Sobreviveram:", len(alive), "de", len(tac))Loop Optimizations
Loops sao responsaveis pela maior parte do tempo de execucao. Otimizacoes de loop tem grande impacto:
Exemplo
1. Loop-Invariant Code Motion (LICM)
Move computacoes que nao mudam para fora do loop.
Antes: Depois:
for i in range(1000): t = len(data) # movido
x = len(data) * i for i in range(1000):
print(x) x = t * i
print(x)
2. Strength Reduction
Substitui operacoes caras por equivalentes baratas.
Antes: Depois:
for i in range(100): t = 0
x = i * 4 for i in range(100):
a[x] = ... a[t] = ...
t = t + 4 # add em vez de mul
3. Loop Unrolling
Replica o corpo do loop para reduzir overhead de branch.
Antes: Depois:
for i in range(4): sum += a[0]
sum += a[i] sum += a[1]
sum += a[2]
sum += a[3]
4. Loop Fusion
Combina dois loops com o mesmo range.
Antes: Depois:
for i in range(n): for i in range(n):
a[i] = b[i] + 1 a[i] = b[i] + 1
for i in range(n): c[i] = a[i] * 2
c[i] = a[i] * 2Peephole Optimization
Peephole e uma otimizacao local que examina uma janela pequena de instrucoes consecutivas, buscando padroes que podem ser simplificados:
Python
class PeepholeOptimizer:
"""Otimizacao por janela deslizante (peephole)."""
def optimize(self, instructions: List[str]) -> List[str]:
result = list(instructions)
changed = True
while changed:
changed = False
i = 0
while i < len(result):
# Regra 1: x = x (copia redundante)
if self._is_self_copy(result[i]):
result.pop(i)
changed = True
continue
# Regra 2: x = y + 0 ou x = y * 1 (identidade)
replacement = self._identity_op(result[i])
if replacement:
result[i] = replacement
changed = True
# Regra 3: x = y * 0 -> x = 0
replacement = self._zero_mul(result[i])
if replacement:
result[i] = replacement
changed = True
# Regra 4: goto L seguido de L: (salto desnecessario)
if i + 1 < len(result):
if self._is_redundant_goto(result[i], result[i+1]):
result.pop(i)
changed = True
continue
# Regra 5: x = y * 2 -> x = y + y (strength reduction)
replacement = self._strength_reduce(result[i])
if replacement:
result[i] = replacement
changed = True
i += 1
return result
def _is_self_copy(self, instr):
parts = instr.strip().split('=')
return len(parts) == 2 and parts[0].strip() == parts[1].strip()
def _identity_op(self, instr):
# x = y + 0 -> x = y ou x = y * 1 -> x = y
parts = instr.strip().split()
if len(parts) == 5: # x = y op z
x, eq, y, op, z = parts
if (op == '+' and z == '0') or (op == '*' and z == '1'):
return f" {x} = {y}"
if (op == '+' and y == '0') or (op == '*' and y == '1'):
return f" {x} = {z}"
return None
def _zero_mul(self, instr):
parts = instr.strip().split()
if len(parts) == 5:
x, eq, y, op, z = parts
if op == '*' and (y == '0' or z == '0'):
return f" {x} = 0"
return None
def _is_redundant_goto(self, instr1, instr2):
if instr1.strip().startswith('goto'):
label = instr1.strip().split()[-1]
return instr2.strip() == f"{label}:"
return False
def _strength_reduce(self, instr):
parts = instr.strip().split()
if len(parts) == 5:
x, eq, y, op, z = parts
if op == '*' and z == '2':
return f" {x} = {y} + {y}"
return None
# Exemplo
tac = [
" x = x", # self-copy: removido
" t1 = a + 0", # identity: t1 = a
" t2 = b * 1", # identity: t2 = b
" t3 = c * 0", # zero mul: t3 = 0
" t4 = d * 2", # strength: t4 = d + d
" goto L1", # redundant goto: removido
"L1:",
]
peep = PeepholeOptimizer()
optimized = peep.optimize(tac)
for line in optimized:
print(line)Passes de Otimizacao em Pipeline
Na pratica, otimizacoes sao aplicadas em sequencia (pipeline de passes), e algumas passes habilitam outras. O GCC e o LLVM rodam dezenas de passes em ordem cuidadosamente escolhida.
Diagrama
Pipeline tipico de otimizacao (LLVM -O2):
IR
|
v
mem2reg # Promove alocacoes de stack para registros SSA
|
v
instcombine # Simplifica instrucoes (peephole)
|
v
simplifycfg # Simplifica o CFG (remove blocos vazios)
|
v
gvn # Global Value Numbering (CSE global)
|
v
licm # Loop Invariant Code Motion
|
v
loop-unroll # Unrolling de loops pequenos
|
v
dce # Dead Code Elimination
|
v
instcombine # Segunda rodada (novas oportunidades!)
|
v
IR otimizada
Observacoes:
- instcombine aparece DUAS VEZES (passes anteriores criam novas chances)
- A ordem importa! CSE antes de DCE produz mais dead code para eliminar
- gcc -O0: zero passes / gcc -O1: passes basicas / gcc -O2: agressivo
- gcc -O3: inclui loop unrolling, vectorization, inlining agressivoNo harness.os: Token Economy como Otimizacao
Conexao com harness.os: O token economy do harness.os e um problema de otimizacao: dado um budget finito de tokens na context window, maximizar a qualidade do output minimizando o custo de input. As mesmas tecnicas de compiladores se aplicam.
Python
from dataclasses import dataclass
from typing import List
@dataclass
class ContextChunk:
source: str
content: str
tokens: int
relevance: float
class ContextOptimizer:
"""Otimizador de contexto para sessoes do harness.os.
Aplica tecnicas de compilador ao token economy:
- Dead code elimination -> remover contexto irrelevante
- Constant folding -> pre-computar resumos
- CSE -> deduplicar knowledge chunks repetidos
- Strength reduction -> usar formato mais compacto
"""
def __init__(self, budget: int = 200_000):
self.budget = budget
def optimize(self, chunks: List[ContextChunk]) -> List[ContextChunk]:
print(f"Antes: {len(chunks)} chunks, "
f"{sum(c.tokens for c in chunks):,} tokens")
# Passo 1: Dead code elimination
# Remover chunks com relevancia muito baixa
chunks = [c for c in chunks if c.relevance >= 0.3]
# Passo 2: CSE - deduplicar conteudo identico
seen = set()
unique = []
for c in chunks:
key = c.content[:100] # hash pelos primeiros 100 chars
if key not in seen:
seen.add(key)
unique.append(c)
chunks = unique
# Passo 3: Ordenar por relevancia (mais relevante primeiro)
chunks.sort(key=lambda c: c.relevance, reverse=True)
# Passo 4: Cortar pelo budget
result = []
total = 0
for c in chunks:
if total + c.tokens <= self.budget:
result.append(c)
total += c.tokens
else:
print(f" Cortado (budget): {c.source} ({c.tokens:,} tokens)")
print(f"Depois: {len(result)} chunks, {total:,} tokens")
return result
# Exemplo
chunks = [
ContextChunk("handoff", "Sessao anterior...", 800, 0.9),
ContextChunk("knowledge", "Template HTML...", 2000, 1.0),
ContextChunk("rules", "Commit hygiene...", 300, 0.7),
ContextChunk("knowledge", "Template HTML...", 2000, 1.0), # dup!
ContextChunk("old_log", "Log de 3 meses...", 5000, 0.1), # irrelevante
]
opt = ContextOptimizer(budget=5000)
optimized = opt.optimize(chunks)
# Antes: 5 chunks, 10,100 tokens
# Depois: 3 chunks, 3,100 tokensResumo
- Constant folding e propagation avaliam expressoes constantes em compile-time
- CSE elimina calculos redundantes reutilizando resultados anteriores
- Dead code elimination remove instrucoes cujos resultados nunca sao usados
- Loop optimizations (LICM, strength reduction, unrolling, fusion) otimizam onde mais importa
- Peephole aplica regras de simplificacao em janelas pequenas de instrucoes
- Otimizacoes sao aplicadas em pipeline; a ordem importa e passes podem ser repetidas
- No harness.os, token economy e um problema de otimizacao: maximizar output quality dado budget finito
Exercicio
Construa um pipeline de otimizacao que aplica, em sequencia: constant propagation, CSE, dead code elimination e peephole. Teste com um programa TAC de pelo menos 15 instrucoes e mostre as instrucoes removidas/transformadas em cada passo. Calcule a "taxa de compressao" (instrucoes originais vs. finais).
Verifique seu entendimento
Por que a ordem das passes de otimizacao importa?