Del significado a las instrucciones

Cuando un programa en Wahoo llega al generador de código, todo sobre él se conoce: cada nombre es una casilla numerada, cada expresión tiene un tipo, cada pipe una firma. Lo que queda es traducirlo a un lenguaje con muchas menos ideas. WebAssembly no tiene question, ni bounce, ni run, ni texto, ni booleanos: tiene enteros de 32 bits, casillas locales, un vector lineal de bytes y una docena de formas de moverse entre instrucciones. Generar código es el arte de decir cosas ricas con un vocabulario pobre.

§Representaciones intermedias

Los compiladores reales rara vez saltan directamente de un árbol sintáctico a código máquina. Pasan por una o varias representaciones intermedias (IR), cada una más cercana a la máquina que la anterior. La clásica es el código de tres direcciones, en el que cada instrucción tiene como mucho un operador:

// a + b * 2
t1 = b * 2
t2 = a + t1

Desde finales de los ochenta casi todos los compiladores optimizadores usan un refinamiento suyo, la forma de asignación única estática (SSA), en la que cada variable se asigna exactamente una vez; una variable que cambia en un bucle se parte en versiones. La SSA simplifica muchas optimizaciones, porque la definición que llega a cada uso es evidente. LLVM, que Chris Lattner empezó en 2000, convirtió una IR en SSA bien diseñada en una interfaz pública: Clang, rustc, Swift, Julia y Zig traducen sus lenguajes a la IR de LLVM y dejan que un back end compartido haga el resto. Sin ese punto medio, M lenguajes y N procesadores necesitan M × N compiladores; con él, M + N.

La IR de Wahoo es la HIR tipada del capítulo 03, y su destino, WebAssembly, es en cierto modo otra IR: el navegador la compila una vez más para el procesador real (capítulo 06).

§Máquinas de pila

En una máquina de pila las instrucciones toman sus operandos de la cima de una pila y dejan allí su resultado. i32.const 2 apila un 2; i32.mul desapila dos números y apila su producto. Generar código para una expresión se reduce entonces a recorrer su árbol en postorden: primero el código de los operandos, de izquierda a derecha, y luego el operador.

a + b * 2

local.get $a     ;; pila: a
local.get $b     ;; pila: a b
i32.const 2      ;; pila: a b 2
i32.mul          ;; pila: a (b*2)
i32.add          ;; pila: a+b*2

Sin nombres temporales ni registros que elegir: la pila guarda los resultados intermedios. Por eso las máquinas de pila son destinos populares para las máquinas virtuales (la JVM, el CIL de .NET, el bytecode de CPython y WebAssembly lo son), y por eso la parte de expresiones de un generador de código para ellas cabe en unas pocas docenas de líneas.

§Traducir el control de flujo

Los procesadores no tienen if ni while, solo saltos condicionales. WebAssembly es algo más estructurado, a propósito: tiene bloques, bucles e if, y los saltos solo pueden salir de un bloque que los rodea (br a un block) o volver al principio de un bucle que los rodea (br a un loop). No hay un goto a cualquier dirección, y eso permite validar un módulo en una sola pasada rápida y compilarlo con seguridad. Un salto nombra su destino por profundidad: br 0 es la construcción más interior, br 1 la siguiente hacia fuera.

Esto es lo que el compilador de Wahoo emite de verdad para un bucle bounce (los comentarios ;; con números de línea los añade el compilador, para ligar cada instrucción con su código fuente):

world 1-1 {
  coin lives = 3
  bounce lives > 0 {
    wahoo(lives)
    damage lives
  }
}

(func $world_1_1
  (local $lives i32)
  ;; 2: coin lives = 3
  i32.const 3
  local.set $lives
  ;; 3: bounce lives > 0 {
  block
    loop
      local.get $lives
      i32.const 0
      i32.gt_s
      i32.eqz
      br_if 1          ;; condición falsa: salir del bloque
      ;; 4: wahoo(lives)
      local.get $lives
      call $print_coins
      call $print_newline
      ;; 5: damage lives
      local.get $lives
      i32.const 1
      i32.sub
      local.set $lives
      br 0             ;; volver al principio del bucle
    end
  end
)

El patrón es siempre el mismo: un block para tener adónde escapar, un loop para tener adónde volver, la condición negada con i32.eqz para que br_if 1 salga cuando es falsa, el cuerpo y un br 0 incondicional. Fíjate en damage lives: a estas alturas ya es lives = lives - 1, el desazucarado del comprobador. Un bucle run i from a to b se traduce igual, con una variable local oculta que guarda b para evaluarlo una sola vez.

question se corresponde con el if/else/end de WebAssembly. Los operadores de cortocircuito también lo usan: a and b se convierte en «calcula a; si es cierto, calcula b; si no, apila 0», un if que deja un valor en la pila (if (result i32)). Así es como goomba and explota() nunca llama a explota.

§Funciones y llamadas

Cada pipe se convierte en una función de WebAssembly cuyos parámetros son sus primeras variables locales. Una llamada apila los argumentos y ejecuta call; el motor se ocupa de la pila de llamadas. flag se convierte en return. Un detalle muestra lo estricto que es WebAssembly:

pipe max(a: coins, b: coins) -> coins {
  question a > b {
    flag a
  } else {
    flag b
  }
}

(func $max (param $a i32) (param $b i32) (result i32)
  ;; 2: question a > b {
  local.get $a
  local.get $b
  i32.gt_s
  if
    ;; 3: flag a
    local.get $a
    return
  else
    ;; 5: flag b
    local.get $b
    return
  end
  unreachable
)

Las dos ramas devuelven, así que nunca se alcanza el final de la función. Pero el validador no razona sobre eso: ve un if que no deja nada en la pila seguido del final de una función que debe devolver un i32, y rechazaría el módulo. La instrucción unreachable final le dice que el control nunca llega ahí. El comprobador de Wahoo ya lo ha demostrado (capítulo 03), así que el generador de código puede afirmarlo con seguridad.

§Los datos en memoria

Los números y los switches caben en una casilla de la pila, pero los textos no. WebAssembly da a cada módulo una memoria lineal, un simple vector de bytes, y el compilador decide cómo colocar los datos en ella. Wahoo guarda cada texto literal una sola vez, a partir de la dirección 16, como una longitud de cuatro bytes seguida de sus bytes UTF-8, rellenando hasta un múltiplo de cuatro. Un valor text es simplemente la dirección de su longitud. Los bytes los coloca un segmento de datos, que el motor copia en la memoria al arrancar el módulo:

(data (i32.const 16) "\04\00\00\00fib(\04\00\00\00) = ")

Dos literales idénticos se guardan una vez, así que tienen la misma dirección, y comparar direcciones es comparar textos. Los primeros dieciséis bytes se dejan vacíos para que ningún texto viva nunca en la dirección 0.

Imprimir no es algo que WebAssembly sepa hacer por sí solo: un módulo solo puede calcular y tocar su propia memoria. Todo lo demás se importa del anfitrión. Los módulos de Wahoo importan cuatro funciones, print_coins, print_switch, print_text y print_newline, y exportan dos cosas: su memoria (para que el anfitrión pueda leer los textos) y main, que juega todos los mundos en orden. En el navegador, el anfitrión son unas pocas líneas de JavaScript; en la línea de órdenes, unas pocas de Rust.

§Lo que además hacen los back ends reales

Compilar para una máquina de pila se salta los dos trabajos más duros de un back end para procesadores reales. La selección de instrucciones elige, entre las muchas secuencias de instrucciones que calculan lo mismo, una barata (x86 puede multiplicar por 5 con un único cálculo de dirección, lea). La asignación de registros decide qué valores viven en el puñado de registros del procesador y cuáles hay que derramar a memoria. En 1981 Gregory Chaitin mostró cómo tratarla como colorear un grafo, con un nodo por valor y una arista entre valores vivos a la vez: k registros son k colores. Colorear grafos es NP-completo, así que los asignadores reales se apoyan en buenas heurísticas, y los rápidos (en los JIT) en esquemas más simples como el barrido lineal. Cuando un navegador compila un módulo de Wahoo, es su motor quien hace este trabajo.