Geracao de Codigo

IR Otimizada
    |
    v
+------------------------+
| Instruction Selection  |   Mapear operacoes IR -> instrucoes ISA
| t1 = a + b             |   ADD R1, R2, R3
| t2 = t1 * 4            |   SHL R4, R1, #2  (shift em vez de mul!)
+------------------------+
    |
    v
+------------------------+
| Register Allocation    |   Mapear temporarios -> registros fisicos
| t1 -> R1               |   Minimizar spills (salvar em memoria)
| t2 -> R2               |   Grafo de interferencia
| a -> stack[0]           |   Coloracao de grafo
+------------------------+
    |
    v
+------------------------+
| Instruction Scheduling |   Reordenar para evitar stalls no pipeline
| Considerar latencias   |   Instrucoes independentes em paralelo
| Data dependencies      |   NOP elimination
+------------------------+
    |
    v
Assembly / Machine Code

IR:  t1 = x * 8

Opcao 1 (ingenua):           Opcao 2 (otimizada):
  MUL R1, Rx, #8               SHL R1, Rx, #3
  (multiplicacao: 3 ciclos)     (shift left: 1 ciclo)

  Multiplicar por potencia de 2 = shift left!
  x * 2^n = x << n

IR:  t2 = x * 7

Opcao 1:                     Opcao 2 (strength reduction):
  MUL R2, Rx, #7               SHL R2, Rx, #3    ; x * 8
  (multiplicacao: 3 ciclos)     SUB R2, R2, Rx    ; x*8 - x = x*7
                                (2 ciclos total)

IR:  if (x == 0) goto L1

x86:                          ARM:
  CMP eax, 0                   CBZ R0, L1
  JE L1                        (Compare and Branch if Zero)
  (2 instrucoes)                (1 instrucao)

Register Allocation via Graph Coloring:

Passo 1: Analise de liveness (quais temporarios estao vivos ao mesmo tempo)

  Instrucao       Live apos
  ---------       ---------
  t1 = a + b      {t1}
  t2 = c + d      {t1, t2}
  t3 = t1 * t2    {t3}         # t1 e t2 morrem aqui
  t4 = e + f      {t3, t4}
  res = t3 + t4   {res}

Passo 2: Grafo de interferencia (aresta = vivos ao mesmo tempo)

  t1 --- t2          t1 e t2 interferem (vivos juntos)
                     t3 e t4 interferem (vivos juntos)
  t3 --- t4          t1 e t3 NAO interferem
                     (posso usar o mesmo registro!)

Passo 3: Colorir o grafo com K cores (K = num. registros)

  Se K = 2 registros (R0, R1):
    t1 = R0
    t2 = R1     # t1 e t2 precisam de registros diferentes
    t3 = R0     # pode reusar R0 (t1 ja morreu)
    t4 = R1     # pode reusar R1 (t2 ja morreu)
    res = R0    # pode reusar R0

  Resultado: 0 spills! Todas cabem em 2 registros.

from typing import Dict, Set, List, Optional

class RegisterAllocator:
    """Alocador de registros por coloracao de grafo."""

    def __init__(self, num_registers: int):
        self.k = num_registers
        self.registers = [f"R{i}" for i in range(num_registers)]
        self.interference: Dict[str, Set[str]] = {}
        self.colors: Dict[str, str] = {}

    def add_interference(self, v1: str, v2: str):
        """Marca que v1 e v2 estao vivos ao mesmo tempo."""
        self.interference.setdefault(v1, set()).add(v2)
        self.interference.setdefault(v2, set()).add(v1)

    def allocate(self) -> Dict[str, str]:
        """Aloca registros usando coloracao gulosa."""
        # Ordenar por grau (mais interferencias primeiro)
        nodes = sorted(self.interference.keys(),
                       key=lambda v: len(self.interference[v]),
                       reverse=True)

        for node in nodes:
            # Cores usadas pelos vizinhos
            used = {self.colors[n] for n in self.interference[node]
                    if n in self.colors}
            # Escolher primeira cor disponivel
            for reg in self.registers:
                if reg not in used:
                    self.colors[node] = reg
                    break
            else:
                # SPILL: nao coube em nenhum registro
                self.colors[node] = f"stack[{node}]"
                print(f"  SPILL: {node} -> memoria")

        return self.colors


# Exemplo
alloc = RegisterAllocator(num_registers=2)
alloc.add_interference("t1", "t2")
alloc.add_interference("t3", "t4")

result = alloc.allocate()
for var, reg in result.items():
    print(f"  {var} -> {reg}")
# t1 -> R0, t2 -> R1, t3 -> R0, t4 -> R1

class SimpleCodeGen:
    """Gerador de codigo: TAC -> assembly simplificado."""

    def __init__(self, num_regs=4):
        self.output: List[str] = []
        self.reg_map: Dict[str, str] = {}
        self.free_regs = [f"R{i}" for i in range(num_regs)]
        self.spill_offset = 0

    def get_reg(self, var: str) -> str:
        """Obtem registro para variavel. Aloca se necessario."""
        if var in self.reg_map:
            return self.reg_map[var]
        if self.free_regs:
            reg = self.free_regs.pop(0)
            self.reg_map[var] = reg
            return reg
        # Spill: salvar algum registro na stack
        victim_var = next(iter(self.reg_map))
        victim_reg = self.reg_map.pop(victim_var)
        self.output.append(f"  STORE {victim_reg}, [SP+{self.spill_offset}]")
        self.spill_offset += 4
        self.reg_map[var] = victim_reg
        return victim_reg

    def free_reg(self, var: str):
        """Libera registro de variavel morta."""
        if var in self.reg_map:
            self.free_regs.append(self.reg_map.pop(var))

    def emit(self, line: str):
        self.output.append(line)

    def generate(self, tac_instructions):
        """Gera assembly a partir de instrucoes TAC."""
        for instr in tac_instructions:
            parts = instr.strip().split()

            if len(parts) == 0:
                continue

            # Label
            if parts[0].endswith(':'):
                self.emit(f"{parts[0]}")
                continue

            # goto L
            if parts[0] == 'goto':
                self.emit(f"  JMP {parts[1]}")
                continue

            # if cond goto L
            if parts[0] == 'if':
                cond_reg = self.get_reg(parts[1])
                self.emit(f"  CMP {cond_reg}, #0")
                self.emit(f"  BNE {parts[-1]}")
                continue

            # return x
            if parts[0] == 'return':
                src_reg = self.get_reg(parts[1])
                self.emit(f"  MOV R0, {src_reg}")
                self.emit(f"  RET")
                continue

            # x = y op z  (atribuicao)
            if len(parts) >= 3 and parts[1] == '=':
                dest = parts[0]
                if len(parts) == 5:
                    # x = y op z
                    arg1, op, arg2 = parts[2], parts[3], parts[4]
                    r1 = self.get_reg(arg1) if not arg1.isdigit() else f"#{arg1}"
                    r2 = self.get_reg(arg2) if not arg2.isdigit() else f"#{arg2}"
                    rd = self.get_reg(dest)
                    asm_op = {'+': 'ADD', '-': 'SUB', '*': 'MUL',
                              '/': 'DIV'}.get(op, op)
                    self.emit(f"  {asm_op} {rd}, {r1}, {r2}")
                elif len(parts) == 3:
                    # x = y (copy)
                    src = parts[2]
                    if src.isdigit():
                        rd = self.get_reg(dest)
                        self.emit(f"  MOV {rd}, #{src}")
                    else:
                        rs = self.get_reg(src)
                        rd = self.get_reg(dest)
                        self.emit(f"  MOV {rd}, {rs}")

    def dump(self):
        print("--- Assembly ---")
        for line in self.output:
            print(line)


# Exemplo: compilar "resultado = (a + b) * (c - d)"
tac = [
    "t1 = a + b",
    "t2 = c - d",
    "t3 = t1 * t2",
    "resultado = t3",
]

codegen = SimpleCodeGen(num_regs=4)
codegen.generate(tac)
codegen.dump()

--- Assembly ---
  ADD R0, R1, R2       ; t1 = a + b (assumindo a em R1, b em R2)
  SUB R3, R4, R5       ; t2 = c - d
  MUL R0, R0, R3       ; t3 = t1 * t2 (reutiliza R0)
  MOV R1, R0           ; resultado = t3

Antes (com stall):                   Depois (sem stall):

  LOAD R1, [addr1]   ; 3 ciclos       LOAD R1, [addr1]    ; 3 ciclos
  ADD R2, R1, #1     ; STALL!         LOAD R3, [addr2]    ; em paralelo!
  LOAD R3, [addr2]   ; 3 ciclos       ADD R4, R5, R6      ; nao depende
  ADD R4, R3, #2     ; STALL!         ADD R2, R1, #1      ; R1 ja disponivel
                                      ADD R4, R3, #2      ; R3 ja disponivel

  Pipeline stalls: 2                  Pipeline stalls: 0
  Total: ~12 ciclos                   Total: ~8 ciclos

Regra: Depois de LOAD, intercalar instrucoes que nao dependem
       do valor carregado para "esconder" a latencia.

soma.c                    gcc -S -O2 soma.c
+------------------+      +---------------------------+
| int soma(a, b) { |  ->  | soma:                     |
|   return a + b;  |      |   leal (%rdi,%rsi), %eax  |
| }                |      |   ret                     |
+------------------+      +---------------------------+
                                    |
                                    v  gcc -c soma.s
                          +---------------------------+
                          | soma.o (ELF object)       |
                          | .text: 8D 04 37 C3        |
                          | .symtab: soma (global)    |
                          +---------------------------+
                                    |
                                    v  gcc -o programa soma.o main.o
                          +---------------------------+
                          | programa (ELF executable)  |
                          | Entry point: 0x401000      |
                          | .text: codigo linkado      |
                          | .data: dados globais       |
                          +---------------------------+

Nota: leal (%rdi,%rsi), %eax  e uma unica instrucao x86
      que calcula rdi + rsi e coloca em eax.
      O compilador transformou a + b em UMA instrucao!

from dataclasses import dataclass
from typing import List, Dict

@dataclass
class ContextChunk:
    role: str      # 'system', 'knowledge', 'rules', 'task'
    content: str
    tokens: int

class PromptGenerator:
    """Gera prompt final a partir do contexto otimizado.

    Analogia com code generation:
      - IR (contexto) -> Assembly (prompt)
      - Register allocation -> Token budget allocation
      - Instruction selection -> Escolher formato do prompt
      - Output -> Artefatos gerados pelo LLM
    """

    def __init__(self, budget: int = 100_000):
        self.budget = budget
        self.sections: Dict[str, List[ContextChunk]] = {
            'system': [],
            'knowledge': [],
            'rules': [],
            'task': [],
        }

    def add_chunk(self, chunk: ContextChunk):
        self.sections[chunk.role].append(chunk)

    def generate(self) -> str:
        """Gera o prompt final respeitando o budget."""
        prompt_parts = []
        total = 0

        # Prioridade: system > rules > task > knowledge
        priority = ['system', 'rules', 'task', 'knowledge']

        for section in priority:
            for chunk in self.sections[section]:
                if total + chunk.tokens <= self.budget:
                    prompt_parts.append(
                        f"--- {section.upper()} ---\n{chunk.content}"
                    )
                    total += chunk.tokens

        prompt = "\n\n".join(prompt_parts)

        print(f"Prompt gerado: {total:,} tokens "
              f"({total/self.budget*100:.1f}% do budget)")
        return prompt


# Exemplo
gen = PromptGenerator(budget=10_000)
gen.add_chunk(ContextChunk('system',
    "Voce e um agente de desenvolvimento...", 200))
gen.add_chunk(ContextChunk('rules',
    "Nunca adicionar Co-Authored-By...", 100))
gen.add_chunk(ContextChunk('task',
    "Criar arquivo 05-03-geracao-de-codigo.html...", 500))
gen.add_chunk(ContextChunk('knowledge',
    "Template HTML padrao para licoes...", 2000))

prompt = gen.generate()
# Prompt gerado: 2,800 tokens (28.0% do budget)