Optimisations

Vue d'ensemble des optimisations disponibles dans Catnip, avec l'idée simple : accélérer sans complexifier.

Niveaux d'Optimisation

Le niveau accepte les valeurs 0-3 et sépare deux paliers : 0 désactive toutes les passes, 1 et 2 activent les passes locales, 3 ajoute le tier inter-blocs CFG/SSA. Les niveaux 1 et 2 ne se distinguent pas encore l'un de l'autre ; les alias low/medium/high restent acceptés.

Le niveau est, par nature, un arbitrage compile/runtime (historiquement, sur le cœur Python, les passes dominaient la compile des petits scripts ; la réécriture Rust a ramené ce coût à ~7-10 %). Le seul tier assez coûteux pour justifier un palier distinct est l'optimisation inter-blocs (CFG/SSA : construction de graphe + SSA + reconstruction) : c'est ce qui occupe le niveau 3 (voir ARCHITECTURE).

Défauts par entrypoint :

Quand Désactiver les Optimisations

Les passes sont sûres (elles préservent les valeurs observables) et leur coût de compilation est faible (mesuré ~7-10 % d'une compile déjà rapide). Désactiver (optimize=0) sert surtout à :

• inspecter l'IR tel qu'écrit (-p 2 montre l'IR que le niveau 3 exécute, optimisations comprises) ;
• isoler une passe suspecte en cas de comportement inattendu ;
• comparer les sorties optimisé/non optimisé (c'est le protocole de test des passes elles-mêmes).

Le mode débrayé existe pour pouvoir prouver que le mode embrayé ne ment pas.

Contrôle du Niveau

Précédence : CLI/env > pragma in-file > config/défaut. Un -o level:N sur la ligne de commande (ou CATNIP_OPTIMIZE=level:N) l'emporte sur les pragma("optimize", ...) du fichier, qui l'emportent sur la config et le défaut.

Via CLI :

catnip script.cat                 # Défaut CLI : activé
catnip -o level:0 script.cat      # Désactive toutes les passes

# Alias textuels (none=0, low=1, medium=2, high=3)
catnip -o level:none script.cat   # Désactivé
catnip -o level:high script.cat   # Activé

Via pragma (file-scoped, s'applique au fichier qui le contient) :

pragma("optimize", 0)   # Désactive les passes pour ce fichier
pragma("optimize", 3)   # Les active

Via API Python :

from catnip import Catnip

cat = Catnip()              # Défaut API : désactivé
cat = Catnip(optimize=3)    # Activé ; ce kwarg est un override, les pragmas in-file ne le renversent pas

Introspection :

catnip.optimize  # Retourne le niveau actuel (0-3)

# Branchement conditionnel
if catnip.optimize > 0 {
    "code optimisé"
} else {
    "sans optimisation"
}

Passes Disponibles

Catnip applique deux types de passes complémentaires.

Les passes IR vivent dans catnip_core/src/semantic/passes/ (pur Rust, opèrent directement sur IR) et servent tous les pipelines. Le trait PurePass et le PureOptimizer appliquent les passes itérativement jusqu'au point fixe (max 10 itérations, détection par PartialEq). L'ancien pipeline PyO3 (catnip_rs/src/semantic/, classes Semantic et Optimizer exposées à Python) a été supprimé : hors production, il divergeait du pipeline vivant.

Passes IR (Niveau Expression)

Optimisations locales sur expressions et statements :

1. Constant Folding - Évalue les expressions constantes au compile-time

2. 2 + 3 → 5

3. True and False → False
4. Ne s'applique que si tous les opérandes sont des littéraux
5. Ne s'applique que si le résultat est exactement représentable en i64 : le folder calcule sur l'entier machine, le runtime promeut en entier long. Un dépassement (checked_add, checked_mul, checked_sub, checked_neg), un décalage qui perd un bit ou dont le compte sort de 0..64, et une puissance qui donne NaN à partir d'opérandes non-NaN laissent donc le nœud intact plutôt que de figer une valeur tronquée. La règle est la même partout : ne folder que ce qu'on sait rendre à l'identique.

Une constante mal repliée est une valeur fausse qui a l'air d'avoir été vérifiée à la compilation.

1. Strength Reduction - Simplifications booléennes (True and False → False) quand les deux opérandes sont des Bool littéraux — écrits tels quels, ou obtenus par une passe précédente ((1 == 1) and (2 == 2) est replié en entier)

2. Block Flattening - Simplifie les blocs imbriqués

3. { { x } y } → { x y }

4. Un bloc qui lie quoi que ce soit est conservé : il porte un scope, l'aplatir ferait fuiter les liaisons dans le bloc parent. Même prédicat de liaison que le pli de branche (binds_in_enclosing_scope) : affectations, défs de fonction/trait/enum/union, et captures de pattern d'un match niché comptent toutes

5. Dead Code Elimination - Supprime code inaccessible

6. Branches if False, while False, cases de match à guard constamment faux

7. Un match réduit à un seul case _ est remplacé par son corps ; le scrutinee est conservé s'il n'est pas un littéral (il peut porter des effets ou lever)
8. Un match dont tous les cases sont morts est conservé tel quel : au runtime il lève « no case matched »

9. Une branche à condition constante n'est repliée que si son corps ne lie rien. Un corps de branche est un bloc, et un bloc porte un scope là où un if n'en porte pas : replier if True { x = 1 } en { x = 1 } ferait décider à la condition, et à elle seule, si x survit au-delà. Prédicat folding_a_branch_moves_a_binding (semantic/passes/mod.rs), partagé avec Blunt Code — les deux passes font la même substitution, en garder une seule laisserait l'autre la refaire. Le prédicat descend dans les constructions non-scopantes — branches d'un if niché, bras et captures de pattern d'un match — puisque leurs liaisons appartiennent au même scope que le corps ; il s'arrête où un scope commence (bloc nu, lambda)

10. Blunt Code Simplification - Simplifie patterns maladroits

11. not (a == b) → a != b (et != → == ; les comparaisons d'ordre ne sont pas inversées : not (a < b) n'est pas équivalent à a >= b en présence de NaN)

12. Les simplifications and/or avec constantes (x and False → False, x or True → True) ne s'appliquent que quand les deux opérandes sont des Bool. En Catnip, and/or retournent toujours un booléen — simplifier avec un opérande non-bool changerait le type de retour
13. Le pli d'une branche à condition constante passe par la même garde de portée que Dead Code Elimination

Identités absentes par construction : sans information de type, les réécritures arithmétiques changent des valeurs observables dans un langage dynamique. "abc" * 0 vaut "" (pas 0), 7.5 // 1 vaut 7.0 (pas 7.5), 7 / 1 vaut 7.0 (pas 7), 5 == True vaut False (pas 5), not not 5 vaut True (pas 5), et x ** 2 ne peut pas devenir x * x (** et * dispatchent vers des surcharges distinctes). Le cas tout-littéral revient au constant folding.

Spécialisation arithmétique typée : quand un type est connu, l'analyse réécrit l'opération polymorphe en sa variante typée. Une opération binaire dont les deux opérandes sont prouvés int (resp. float) -- via un paramètre annoté, dont le type est garanti à l'entrée de la fonction (voir la spécialisation au boundary dans docs/lang/FUNCTIONS.md), un littéral, ou le résultat chaîné d'une réécriture typée -- devient AddInt/AddFloat, SubInt/SubFloat, MulInt/MulFloat ou DivFloat. La forme typée saute le dispatch de type et la recherche de surcharge à l'exécution, et fournit au JIT une trace déjà typée. La réécriture (rewrite_typed_arith, catnip_core/src/pipeline/semantic/) est sound par construction : un opérande dont le type n'est plus garanti (paramètre réassigné, lié par un pattern, variable de boucle, binding except, ou masqué par une définition locale) fait retomber l'opération sur sa forme polymorphe. La division vraie (/) n'a pas de variante entière : elle produit toujours un float, donc seule DivFloat existe et int / int reste polymorphe.

Passes désactivées : Constant Propagation, Copy Propagation et Dead Store Elimination sont retirées du pipeline. Leur suivi des assignations est insensible au flot de contrôle et aux scopes ; les réactiver demande un vrai dataflow (invalidation par branche, invalidation des sources de copies, détection de cycles).

Passes CFG/SSA (niveau 3)

Le module catnip_core/src/cfg/ contient une infrastructure complète CFG + SSA (Braun et al. 2013) : construction du graphe, passes inter-blocs (LICM, DSE globale, GVN — qui subsume la CSE syntaxique —, IV), destruction SSA et reconstruction IR. Le JIT construit ses propres CFG indépendamment.

Le niveau d'optimisation 3 câble le round-trip IR → CFG → SSA → LICM → DSE → GVN → destruction → reconstruction dans analyze_full. Le niveau par défaut est 2 : le tier inter-blocs se demande, par catnip -o level:3 ou pragma("optimize", 3), et la précédence est la même que pour les autres directives (CLI/env > pragma fichier > défaut).

Trois passes inter-blocs y tournent, chacune gardée pour refuser plutôt que dégrader : LICM (hoist des défs invariantes de while dans un bloc gardé par une copie de la condition — pas de spéculation zéro-itération), DSE (v1 étroite : seuls les stores « transparents » — littéral scalaire ou référence — tués sur tous les chemins tombent ; un call ou un op fautable dans la fenêtre fait barrière), GVN (les expressions redondantes prouvées scalaires immuables deviennent des copies — alias ou snapshot selon le nombre de défs du canonique).

Validé en différentiel d'exécution sur la suite entière, modes VM et AST (make test-cfg) : chaque test vert au niveau par défaut et au niveau 3 est un programme dont le tier ne change pas le comportement observable. Le harnais property-based cfg_proptest échantillonne l'espace entre ces cas.

Limite restante : le match round-trippe par préservation d'op, donc les passes ne descendent pas dans les arms — elles s'en protègent explicitement plutôt que de supposer l'arm vide. Détails dans ARCHITECTURE.

Architecture du Pipeline

Ordre d'exécution (SemanticAnalyzer::analyze_full, catnip_core/src/pipeline/semantic/mod.rs) :

1. Transform (interception des intrinsics : typeof, breakpoint)
2. Pré-scan des pragmas top-level (tco, optimize) -- précédence : override host (CLI/env) > pragma in-file > baseline
3. Marquage des tail calls (si TCO actif)
4. Passes IR (5 passes) jusqu'au point fixe, max 10 itérations (si optimisation active)
5. Validation des opcodes et pragmas, puis une pré-passe globale (collect_unique_fns) qui relève les signatures des fonctions à liaison prouvablement unique et les noms susceptibles de masquer un constructeur, suivie de la traversée type-aware (check_exhaustiveness) qui suit les types des variables sur un treillis plat (types.rs), lie les paramètres annotés, infère les champs de struct typés, et collecte les diagnostics : exhaustivité des match (I103) et incompatibilités de type prouvables (E300) -- aux sites de déclaration (défaut de param/champ, type de retour) comme aux sites d'appel (arguments positionnels et nommés vs paramètres d'une fonction unique, champs d'un constructeur de struct, payload d'une variante d'union, ou arité et arguments d'un appel à travers un paramètre de type fonction déclaré)
6. Réécriture des vérifications de retour de callback (rewrite_callback_return_checks) : chaque appel passant par un paramètre fonction de type déclaré est enveloppé dans un nœud IR CheckReturn, abaissé vers l'opcode boundary du type de retour. Pendant du rewrite_typed_arith ci-dessus, côté appelant plutôt que côté opération -- détail dans VM

Tail Call Optimization (TCO)

La TCO est une optimisation toujours active (indépendante du niveau) :

Principe : proper tail calls -- tout appel par nom en position terminale s'exécute en pile O(1), pas seulement l'auto-récursion. Couvre la récursion mutuelle (ping → pong → ping), les fonctions imbriquées et les appels terminaux vers une autre fonction.

is_even = (n) => { if n == 0 { True } else { is_odd(n - 1) } }   # ← tail call mutuel
is_odd  = (n) => { if n == 0 { False } else { is_even(n - 1) } }

Détection : traversée unique mark_tails dans l'analyseur sémantique (catnip_core/src/pipeline/semantic/mod.rs). Positions terminales propagées : dernière expression d'un bloc, corps des branches d'un if, corps des cases d'un match, expression d'un return. La traversée descend dans tous les corps de lambdas, y compris les définitions imbriquées et les lambdas passées en argument. Le flag ne peut jamais apparaître hors d'un corps de lambda (un signal TailCall qui fuirait au top-level surfacerait comme valeur).

Implémentation : trampoline pattern (pas de frame empilée). En VM, TailCall réutilise le frame courant (locals rebindés, piles vidées, code object remplacé si la cible diffère) ; en mode AST, l'appel retourne un signal TailCall consommé par la boucle trampoline, avec swap de scope synchronisé quand la cible change de closure (les écritures aux variables capturées sont propagées comme au retour d'un appel normal). Les cibles non-fonction (builtins, constructeurs de structs, fonctions d'un autre contexte Catnip) sont appelées directement.

Positions jamais terminales :

• corps de while/for (la boucle doit reprendre la main), y compris un return f() dans une boucle ;
• tout ce qui est sous try (le handler doit rester sur la pile) ;
• opérandes de and/or/?? (consommés par le test de vérité) ;
• arguments d'appels, conditions, guards de match.

Voir ARCHITECTURE section TCO pour détails.