JIT Compilation de Expresiones Regulares en ARM64 con Copy-and-Patch

La compilación Just-In-Time (JIT) es una técnica fundamental para optimizar el rendimiento de programas cuya lógica de ejecución se define o refina en tiempo de ejecución. Históricamente, la implementación de compiladores JIT ha sido una tarea compleja, requiriendo un conocimiento profundo de la arquitectura de la CPU y la programación en ensamblador, lo que ha limitado su adopción en sistemas de software de propósito general, como las bases de datos.

El problema fundamental que aborda la compilación JIT es la brecha de rendimiento entre la flexibilidad de la interpretación y la eficiencia del código compilado estáticamente. Al generar código máquina optimizado en tiempo de ejecución, los sistemas pueden aprovechar información dinámica (ej. tipos de datos, patrones de acceso) que no está disponible en tiempo de compilación. Este artículo explora cómo las herramientas modernas, incluyendo la asistencia de IA, pueden reducir significativamente la barrera de entrada para desarrollar compiladores JIT, haciendo que esta técnica sea más accesible y viable para una gama más amplia de aplicaciones, como motores de bases de datos o de expresiones regulares, donde la latencia de compilación es crítica.

Arquitectura del Sistema

El sistema se compone de un motor de expresiones regulares que, en lugar de interpretar un Árbol de Sintaxis Abstracta (AST), lo compila a código máquina ARM64 en tiempo de ejecución. La arquitectura se basa en tres componentes principales: el AST de la expresión regular, un 'Emitter' de código máquina y un cargador de código.

El AST representa la expresión regular con nodos para literales, concatenaciones y repeticiones. El 'Emitter' traduce este AST en una secuencia de instrucciones ARM64 utilizando la técnica de 'copy-and-patch'. Esta técnica emplea 'stencils', que son plantillas de código ensamblador predefinidas para operaciones comunes (ej. comparación de caracteres, saltos condicionales). El 'Emitter' rellena estas plantillas con valores específicos (ej. el byte del carácter a comparar, la dirección de salto) y las concatena para formar el programa completo. Para el backtracking en las repeticiones, se utiliza una pila explícita, gestionada por los registros x1 (top) y x2 (bottom) de ARM64, almacenando la dirección de reanudación y la posición de la cadena. La cadena de entrada se termina con un byte nulo para simplificar las comprobaciones de fin de cadena.

Finalmente, el cargador de código utiliza mmap para asignar un bloque de memoria con permisos de lectura, escritura y ejecución (PROT_READ | PROT_WRITE | PROT_EXEC). El código máquina generado por el 'Emitter' se copia a esta región de memoria. En macOS, se utilizan funciones específicas como pthread_jit_write_protect_np para gestionar la protección de escritura de la memoria JIT y sys_icache_invalidate para invalidar la caché de instrucciones, asegurando que la CPU ejecute el código recién generado. Una vez cargado, el puntero a esta memoria se 'transmuta' a una función Rust invocable, permitiendo la ejecución directa del código compilado.

enum Node {
    Literal(&'static str),
    Concatenation(Box<Node>, Box<Node>),
    Repetition(Box<Node>),
}

fn stencil_char(byte: u8, stencil_pos: usize, fail_pos: usize) -> [u32; CHAR_WORDS] {
    [
        0x39400009, // ldrb w9, [x0]
        0x7100013F | ((byte as u32) << 10), // cmp w9, #byte
        0x54000001 | cond_branch_offset(stencil_pos + 2, fail_pos), // b.ne fail
        0x91000400, // add x0, x0, #1
    ]
}

unsafe {
    let buf = libc::mmap(
        std::ptr::null_mut(),
        nbytes,
        libc::PROT_READ | libc::PROT_WRITE | libc::PROT_EXEC,
        libc::MAP_PRIVATE | libc::MAP_ANON | libc::MAP_JIT,
        -1,
        0,
    ) as *mut u32;
    // ... copy code ...
    let matcher: MatchFn = std::mem::transmute(self.buf);
    matcher(nul_terminated.as_ptr(), self.bstack.as_mut_ptr()) != 0
}

Fundamentos Teóricos

El concepto de compilación JIT tiene raíces profundas en la investigación de lenguajes de programación y sistemas operativos. La idea de generar código en tiempo de ejecución para optimizar el rendimiento se remonta a los primeros sistemas Lisp y Smalltalk. La técnica de 'copy-and-patch' utilizada en este artículo es una forma simplificada de generación de código, donde fragmentos de código precompilados (stencils) se ensamblan y modifican dinámicamente. Esto se relaciona con los principios de 'template-based code generation' y 'dynamic code generation' explorados en la literatura de compiladores.

Aunque el artículo no cita un paper específico, el manejo de expresiones regulares mediante autómatas finitos (deterministas o no deterministas) es un campo clásico de la informática teórica, formalizado por Kleene en los años 50. La compilación de expresiones regulares a código máquina es una aplicación directa de la transformación de un autómata a un programa imperativo, donde cada estado y transición se mapea a instrucciones de CPU. El uso de una pila para el backtracking en el manejo de repeticiones es una técnica común en la implementación de motores de expresiones regulares que emulan un autómata finito no determinista (NFA), similar a los algoritmos descritos por Thompson (1968) para la construcción de NFAs a partir de expresiones regulares.