Generación y optimización de código

📐 Fundamento

Código de tres direcciones (Three-Address Code, TAC):

Cada instrucción tiene como máximo tres operandos: resultado = op1 operador op2.

# Fuente PupusaScript:
total <- precio * cantidad + descuento

# TAC generado:
t1 = precio * cantidad     # temporales t1, t2...
t2 = t1 + descuento
total = t2

Instrucciones TAC:

# Asignación simple
x = y

# Operación binaria
x = y op z       (op: +, -, *, /)

# Operación unaria
x = -y

# Salto incondicional
goto L

# Salto condicional
if x goto L
ifFalse x goto L

# Comparación
x = y < z       (resultado booleano)

# Llamada a función
param x          # pasar parámetro
call f, n        # llamar función f con n parámetros
x = call f, n   # con valor de retorno

Generador de TAC — un Visitor más:

class GeneradorTAC(Visitor):
    def __init__(self):
        self.instrucciones = []
        self.temp_count = 0
        self.label_count = 0
    
    def nuevo_temp(self) -> str:
        self.temp_count += 1
        return f"t{self.temp_count}"
    
    def nueva_etiqueta(self) -> str:
        self.label_count += 1
        return f"L{self.label_count}"
    
    def emit(self, instruccion: str):
        self.instrucciones.append(instruccion)
    
    def visitar_programa(self, nodo: Programa):
        for stmt in nodo.cuerpo:
            stmt.accept(self)
    
    def visitar_asignacion(self, nodo: Asignacion):
        lugar = nodo.valor.accept(self)
        self.emit(f"{nodo.destino} = {lugar}")
    
    def visitar_binop(self, nodo: BinOp) -> str:
        lugar_izq = nodo.izq.accept(self)
        lugar_der = nodo.der.accept(self)
        resultado = self.nuevo_temp()
        self.emit(f"{resultado} = {lugar_izq} {nodo.op} {lugar_der}")
        return resultado
    
    def visitar_numero(self, nodo: Numero) -> str:
        return str(nodo.valor)
    
    def visitar_identificador(self, nodo: Identificador) -> str:
        return nodo.nombre
    
    def visitar_si_stmt(self, nodo: SiStmt):
        cond = nodo.condicion.accept(self)
        etq_sino = self.nueva_etiqueta()
        etq_fin  = self.nueva_etiqueta()
        
        self.emit(f"ifFalse {cond} goto {etq_sino}")
        
        for stmt in nodo.entonces:
            stmt.accept(self)
        
        if nodo.sino:
            self.emit(f"goto {etq_fin}")
            self.emit(f"{etq_sino}:")
            for stmt in nodo.sino:
                stmt.accept(self)
            self.emit(f"{etq_fin}:")
        else:
            self.emit(f"{etq_sino}:")
    
    def visitar_imprimir(self, nodo: ImprimirStmt):
        lugar = nodo.expresion.accept(self)
        self.emit(f"param {lugar}")
        self.emit(f"call imprimir, 1")

# Ejemplo de uso:
generador = GeneradorTAC()
ast.accept(generador)
print('\n'.join(generador.instrucciones))

Salida para total <- precio * 1.13:

t1 = precio * 1.13
total = t1

Salida para el bloque si:

t2 = descuento > 0
ifFalse t2 goto L1
t3 = precio * 0.1
descuento_calc = t3
goto L2
L1:
descuento_calc = 0
L2:

📐 Fundamento

1. Constant Folding (pliegue de constantes):

Evaluar expresiones constantes en tiempo de compilación.

# Antes:
t1 = 1.0 * 0.13    # siempre 0.13 — calculable en compilación

# Después:
t1 = 0.13

def optimizar_constant_folding(instrucciones):
    resultado = []
    for inst in instrucciones:
        # Detectar patrón "t = constante op constante"
        m = re.match(r'(\w+) = ([\d.]+) ([+\-*/]) ([\d.]+)', inst)
        if m:
            dest, a, op, b = m.groups()
            a, b = float(a), float(b)
            valor = {'+': a+b, '-': a-b, '*': a*b, '/': a/b}[op]
            resultado.append(f"{dest} = {valor}")
        else:
            resultado.append(inst)
    return resultado

2. Dead Code Elimination (eliminación de código muerto):

# Antes (t1 nunca se usa):
t1 = x * 2
t2 = y + 3
resultado = t2

# Después:
t2 = y + 3
resultado = t2

3. Common Subexpression Elimination (CSE):

# Antes (precio * 1.13 calculado dos veces):
t1 = precio * 1.13
t2 = precio * 1.13    ← mismo cálculo
total = t1 + t2

# Después:
t1 = precio * 1.13
total = t1 + t1       ← reutilizar t1

4. Loop Invariant Code Motion:

Mover cálculos que no cambian dentro de un bucle, afuera del bucle.

# Antes:
while i < n:
    t1 = precio * iva    ← no depende de i, se calcula N veces
    total[i] = base + t1
    i = i + 1

# Después:
t1 = precio * iva        ← calculado una sola vez
while i < n:
    total[i] = base + t1
    i = i + 1

5. Strength Reduction:

Reemplazar operaciones costosas por equivalentes más baratas.

# Antes (multiplicación en cada iteración):
i = 0
while i < n:
    t1 = i * 4       ← multiplicación
    ...
    i = i + 1

# Después (solo suma):
i = 0; t1 = 0
while i < n:
    ...
    i = i + 1
    t1 = t1 + 4      ← suma (más barata que multiplicación)

Optimizaciones que hace LLVM:

📐 Fundamento

En lugar de generar código máquina nativo, podemos generar bytecode para una máquina virtual (VM). Python, Java, C#, y Lua lo hacen así.

from enum import Enum, auto

class Op(Enum):
    LOAD_CONST  = auto()  # push constante al stack
    LOAD_VAR    = auto()  # push variable al stack
    STORE_VAR   = auto()  # pop stack → variable
    BINARY_ADD  = auto()
    BINARY_SUB  = auto()
    BINARY_MUL  = auto()
    BINARY_DIV  = auto()
    COMPARE_LT  = auto()
    COMPARE_GT  = auto()
    JUMP_IF_FALSE = auto() # saltar si TOS es falso
    JUMP         = auto()
    PRINT        = auto()
    HALT         = auto()

class Instruccion:
    def __init__(self, op: Op, arg=None):
        self.op = op
        self.arg = arg

class VirtualMachine:
    """Stack-based virtual machine para PupusaScript."""
    
    def __init__(self, codigo: list[Instruccion]):
        self.codigo = codigo
        self.stack = []
        self.variables = {}
        self.pc = 0          # program counter
    
    def push(self, val): self.stack.append(val)
    def pop(self):       return self.stack.pop()
    
    def ejecutar(self):
        while self.pc < len(self.codigo):
            inst = self.codigo[self.pc]
            self.pc += 1
            
            match inst.op:
                case Op.LOAD_CONST:
                    self.push(inst.arg)
                
                case Op.LOAD_VAR:
                    if inst.arg not in self.variables:
                        raise RuntimeError(f"Variable '{inst.arg}' no inicializada")
                    self.push(self.variables[inst.arg])
                
                case Op.STORE_VAR:
                    self.variables[inst.arg] = self.pop()
                
                case Op.BINARY_ADD:
                    b, a = self.pop(), self.pop()
                    self.push(a + b)
                
                case Op.BINARY_MUL:
                    b, a = self.pop(), self.pop()
                    self.push(a * b)
                
                case Op.COMPARE_GT:
                    b, a = self.pop(), self.pop()
                    self.push(a > b)
                
                case Op.JUMP_IF_FALSE:
                    cond = self.pop()
                    if not cond:
                        self.pc = inst.arg
                
                case Op.JUMP:
                    self.pc = inst.arg
                
                case Op.PRINT:
                    print(self.pop())
                
                case Op.HALT:
                    break

# Bytecode para: precio <- 8.50 * 1.13; imprimir(precio)
programa = [
    Instruccion(Op.LOAD_CONST, 8.50),
    Instruccion(Op.LOAD_CONST, 1.13),
    Instruccion(Op.BINARY_MUL),
    Instruccion(Op.STORE_VAR, 'precio'),
    Instruccion(Op.LOAD_VAR, 'precio'),
    Instruccion(Op.PRINT),
    Instruccion(Op.HALT),
]

vm = VirtualMachine(programa)
vm.ejecutar()
# → 9.605