Compilation JIT

Catnip utilise un compilateur Just-In-Time (JIT) pour accélérer automatiquement le code qui tourne souvent.

Pourquoi un JIT

Le JIT corrige trois limites majeures de l'interprétation :

Performance : code natif 100-200x plus rapide que la VM sur les boucles numériques

Stack overflow : évite les limites de profondeur pour les fonctions récursives compilées

Transparence : activation automatique sans intervention utilisateur (détection à chaud)

Architecture : Trace-based JIT

Catnip utilise une approche trace-based plutôt que method-based :

• On enregistre l'exécution réelle d'une boucle ou fonction (trace)
• On compile cette trace linéaire en code natif
• Les branches rarement prises sont ignorées (guards + deoptimization)

Cette approche simplifie la compilation et optimise les chemins chauds réels plutôt que tous les chemins possibles.

La trace JIT regarde le réel, puis lui colle un circuit rapide en natif. Si ça part en freestyle, retour VM sans drame. On bétonne les trajets du quotidien, on tague le reste.

Références académiques

Trace compilation : Gal et al. 2009 - "Trace-based Just-in-Time Type Specialization for Dynamic Languages" (ACM PLDI)

Deoptimization : Hölzle et al. 1992 - "Debugging Optimized Code with Dynamic Deoptimization" (ACM PLDI)

Backend : Cranelift

Catnip utilise Cranelift comme backend de compilation :

Transparence : Cranelift n'est pas formellement prouvé dans ce repo.

• Bibliothèque Rust pour génération de code machine (x86-64, ARM64, etc.)
• Temps de compilation rapide (adapté au JIT)
• Utilisé par Wasmtime, SpiderMonkey, autres projets production
• Alternative moderne à LLVM pour cas d'usage JIT

Pourquoi Cranelift :

• Intégration Rust native (pas de FFI)
• Compile en ~100µs (vs millisecondes pour LLVM)
• API sûre (pas d'UB possible en Rust safe)
• Maintenance active (Bytecode Alliance)

Détection de code chaud

Le JIT surveille deux types de "hot paths" :

Loops (boucles)

Seuil : 100 itérations du même loop body

# Devient hot après 100 itérations
for i in range(10000) {
    sum = sum + i
}
# Itération 1-100 : interpréteur + profiling
# Itération 100 : compilation trace
# Itération 101+ : code natif

Functions (fonctions)

Seuil : 100 appels de la même fonction

fib = (n) => {
    if n < 2 { n } else { fib(n-1) + fib(n-2) }
}

fib(30)
# Appels 1-100 : interpréteur + profiling
# Appel 100 : compilation trace (avec CallSelf natif)
# Appel 101+ : code natif récursif

Identification : fonction identifiée par hash stable du bytecode + nom + nombre d'arguments

Optimisations supportées

Le JIT applique automatiquement :

Spécialisation de types : génère du code natif pour int/float détectés dans la trace

Élimination d'overhead : pas de boxing/unboxing, dispatch direct

Builtins natifs : abs, bool, int, max, min, round compilés en instructions machine (icmp/select/identity), float via callback extern C -- pas d'appel Python

Inline de fonctions pures : petites fonctions pures (\<20 opcodes) inlinées automatiquement

Récursion native : appels récursifs compilés en CALL natif (avec protection overflow)

Activation et contrôle

Défaut : JIT activé automatiquement en mode VM

Désactiver :

catnip -o jit:off script.cat

Pragma :

pragma("jit", False)  # Désactive JIT pour ce fichier

Variables d'environnement :

CATNIP_OPTIMIZE=jit:off catnip script.cat

Cache de traces

Les traces compilées sont persistées sur disque pour éliminer le warm-up au prochain lancement.

Mécanisme

1. Hash du bytecode : chaque programme reçoit un hash FNV-1a calculé sur les instructions (opcode + arg) ET le constant pool (valeurs NaN-boxed). Deux programmes avec les mêmes instructions mais des constantes différentes produisent des hash différents.

2. Stockage : les traces sont sérialisées en bincode dans ~/.cache/catnip/ (fichiers plats). Clé : jit_v{VERSION}_{HASH:016x}_{OFFSET:06x}.

3. Chargement : au moment où la VM détecte un loop chaud (seuil 100), elle vérifie d'abord le cache disque. Si une trace existe et que la version correspond, elle est rechargée et recompilée via Cranelift sans repasser par l'enregistrement.

4. Invalidation : par version Catnip + version format cache. Un changement de version invalide automatiquement les entrées.

Multiprocessus (ND)

Le cache est safe pour l'exécution concurrente ND (mode spawn) :

• Atomic writes : écriture dans fichier temporaire puis rename() (POSIX atomique)
• Last writer wins : toutes les traces pour un même offset sont équivalentes, pas besoin de lock
• Mémoire séparée : chaque worker recompile indépendamment depuis la trace cachée

Ce qui est cachée vs ce qui ne l'est pas

Cachée : la Trace (séquence de TraceOp, type, metadata) - structure sérialisable

Non cachée : le CompiledFn (pointeur vers code machine) - runtime-specific, non sérialisable

Les stencils Cranelift (code machine non relocaté + table de relocations) sont cachés séparément (jit_native_{SHA256}) via le trait CacheKvStore de Cranelift. Au rechargement, le stencil est désérialisé et les relocations appliquées par define_function_bytes + finalize_definitions -- sans repasser par la compilation Cranelift. La clé SHA-256 inclut le triple ISA + les flags CPU, ce qui invalide le cache en cas de changement d'architecture.

Le cache garde la trace (le plan), pas le binaire final. Chaque process forge son code machine localement.

Limitations et fallback

Le JIT ne compile pas tout le code :

Non compilable :

• Appels à fonctions Python externes (sauf builtins purs : abs, bool, float, int, max, min, round)
• Opérations non supportées (I/O, réflexion)
• Branches froides (rarement exécutées)

Comportement : fallback transparent vers l'interpréteur VM, aucune erreur

Deoptimization : si une guard échoue (type change, condition inattendue), retour à l'interpréteur

Performances typiques

Le JIT aime les workloads CPU-bound qui cognent fort. Si ton code attend surtout le réseau/disque, il reste zen et le gain reste modeste.

SSA et Block Parameters

Cranelift travaille en SSA (Static Single Assignment) en interne. Catnip utilise des block parameters explicites pour les variables loop-carried, plutôt que de s'appuyer sur l'inférence automatique de phi-nodes.

Pourquoi des block parameters

L'inférence automatique via use_var()/def_var() de Cranelift casse quand une variable est utilisée puis redéfinie dans le corps d'une boucle (def après use). Le résultat : la variable garde sa valeur initiale à chaque itération.

# Ce code bouclait infiniment avant le fix
total = 0
for i in range(1000) {
    total = total + i
}

Solution : passage explicite

Les variables mutées dans la boucle sont passées comme paramètres du bloc :

// Création des paramètres de boucle
let loop_params: Vec<Value> = locals_order
    .iter()
    .map(|_| builder.append_block_param(loop_block, types::I64))
    .collect();

// Jump initial avec valeurs initiales
builder.ins().jump(loop_block, &initial_vals);

// Back edge avec valeurs mises à jour
let back_args: Vec<Value> = locals_order
    .iter()
    .map(|slot| builder.use_var(slot_vars[slot]))
    .collect();
builder.ins().jump(loop_block, &back_args);

locals_order est trié en amont pour garantir que tous les jumps vers loop_block passent les arguments dans le même ordre.

Référence SSA : Cytron et al. (1991), "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" (IEEE TOPLAS). Construction SSA du pipeline CFG/SSA de Catnip : Braun et al. (2013), "Simple and Efficient Construction of Static Single Assignment Form".