Backend générique bas-niveau

[david-michel1]

La représentation abstraite finale du programme à générer (BIR) est complexe et risque d'évoluer en fonction des choix d'architecture et d'optimisation, ce qui nécessiterait de mettre à jour tous les backends spécifiques (C, Java, etc.)

Pour pouvoir coder des backends tout en laissant la liberté de modifier le BIR, il serait envisageable de définir un backend générique bas-niveau qui se calerait sur le moins-disant des backends, une sorte d'assembleur avec uniquement un nombre fini (paramétrable) de registres (doublés, un booléen pour l'existence, un double pour la valeur), les opérations de base (arithmétique, arrondis, etc.), les sous-routines (règles, vérifs, fonctions MPP) et éventuellement un saut conditionnel pour les boucles et autres itérateurs. Il faudrait sans doute également ajouter les informations nécessaires pour générer les bons fichiers et y ranger les bonnes routines.

Ce backend très simple car bas-niveau serait figé afin que les parties en amont (analyse, transformation, optimisation) et en aval (génération de code) soient indépendantes.

En C la traduction serait quasi-immédiate et sans doute très économe en ressources. Pour une cible de plus haut niveau comme OCaml, la question de l'efficacité d'un style de programmation essentiellement impératif se pose. J'ai codé une sorte de prototype représentant un calcul bidon du type qui serait généré, avec 9 tables de variables et trois «registres» r0, r1 et r2:

open Array

type env = {
  t0 : float array;
  t1 : float array;
  t2 : float array;
  t3 : float array;
  t4 : float array;
  t5 : float array;
  t6 : float array;
  t7 : float array;
  t8 : float array;
  t9 : float array;
}

let e = {
  t0 = make 20000 5.0;
  t1 = make 20000 5.0;
  t2 = make 20000 5.0;
  t3 = make 20000 5.0;
  t4 = make 20000 5.0;
  t5 = make 20000 5.0;
  t6 = make 20000 5.0;
  t7 = make 20000 5.0;
  t8 = make 20000 5.0;
  t9 = make 20000 5.0;
}

let f () =
  let r0 = unsafe_get e.t0 100 in
  let r1 = unsafe_get e.t1 200 in
  let r0 = r0 *. r1 in
  let r1 = unsafe_get e.t2 300 in
  let r2 = unsafe_get e.t3 400 in
  let r1 = r1 *. r2 in
  let r2 = unsafe_get e.t4 300 in
  let r1 = r1 +. r2 in
  let r2 = unsafe_get e.t5 200 in
  let r1 = r1 +. r2 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t6 100 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t7 0 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t8 100 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t9 200 in
  let r0 = r0 +. r1 in
  Array.unsafe_set e.t0 0 r0

let g () =
  let r0 = unsafe_get e.t0 0 in
  let r1 = unsafe_get e.t1 96 in
  let r0 = r0 *. r1 in
  let r1 = unsafe_get e.t2 33 in
  let r2 = unsafe_get e.t3 458 in
  let r1 = r1 *. r2 in
  let r2 = unsafe_get e.t4 8563 in
  let r1 = r1 +. r2 in
  let r2 = unsafe_get e.t5 22 in
  let r1 = r1 +. r2 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t6 2569 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t7 456 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t8 78 in
  let r0 = r0 +. r1 in
  let r1 = unsafe_get e.t9 8569 in
  let r0 = r0 +. r1 in
  Array.unsafe_set e.t0 0 r0

let _ =
  f ();
  g ();
  print_float (Array.unsafe_get e.t0 0);
  print_newline ()

L'export en bytecode montre que le tas est uniquement utilisé pour stocker les tables de variables. Les calculs exploitent uniquement la pile:

$ ocamlc -dinstr run.ml
    branch L3
L1: const 0
    push
    envacc 1
    getfield 0
    ccall caml_array_unsafe_get_float, 2
    push
    const 96
    push
    envacc 1
    getfield 1
    ccall caml_array_unsafe_get_float, 2
    push
    acc 0
    push
    acc 2
    ccall caml_mul_float, 2
    push
    const 33
    push
    envacc 1
    getfield 2
    ccall caml_array_unsafe_get_float, 2
    push
    const 458
    push
    envacc 1
    getfield 3
    ccall caml_array_unsafe_get_float, 2
    push
    acc 0
    push
    acc 2
    ccall caml_mul_float, 2
    push
    ...

Le même exercice en assembleur X86_64 montre que seuls les registres machines sont utilisés pendant les calculs: le ramasse-miettes n'est jamais appelé. Tout d'abord les fonctions f et g sont des suites d'instructions simples:

$ ocamlopt -S run.ml && cat run.s
    ...
camlRun__f_1251:
    .cfi_startproc
.L100:
    movq    camlRun@GOTPCREL(%rip), %rax
    movq    (%rax), %rbx
    movq    (%rbx), %rax
    movsd   800(%rax), %xmm0
    movq    8(%rbx), %rdi
    movsd   1600(%rdi), %xmm1
    mulsd   %xmm1, %xmm0
    movq    16(%rbx), %rdi
    movsd   2400(%rdi), %xmm1
    movq    24(%rbx), %rdi
    movsd   3200(%rdi), %xmm2
    mulsd   %xmm2, %xmm1
    movq    32(%rbx), %rdi
    movsd   2400(%rdi), %xmm2
    addsd   %xmm2, %xmm1
    movq    40(%rbx), %rdi
    movsd   1600(%rdi), %xmm2
    addsd   %xmm2, %xmm1
    addsd   %xmm1, %xmm0
    movq    48(%rbx), %rdi
    movsd   800(%rdi), %xmm1
    addsd   %xmm1, %xmm0
    movq    56(%rbx), %rdi
    movsd   (%rdi), %xmm1
    addsd   %xmm1, %xmm0
    movq    64(%rbx), %rdi
    movsd   800(%rdi), %xmm1
    addsd   %xmm1, %xmm0
    movq    72(%rbx), %rbx
    movsd   1600(%rbx), %xmm1
    addsd   %xmm1, %xmm0
    movsd   %xmm0, (%rax)
    movq    $1, %rax
    ret
    ...

Ensuite les séquences d'appels aux fonctions f et g débutent par le chargement sur la pile de l'adresse de tous les tableaux utilisés, puis sont appelés l'une après l'autre:

.L118:
    leaq    8(%r15), %rax
    movq    $10240, -8(%rax)
    movq    %rbx, (%rax)
    movq    (%rsp), %rbx
    movq    %rbx, 8(%rax)
    movq    8(%rsp), %rbx
    movq    %rbx, 16(%rax)
    movq    16(%rsp), %rbx
    movq    %rbx, 24(%rax)
    movq    24(%rsp), %rbx
    movq    %rbx, 32(%rax)
    movq    32(%rsp), %rbx
    movq    %rbx, 40(%rax)
    movq    40(%rsp), %rbx
    movq    %rbx, 48(%rax)
    movq    48(%rsp), %rbx
    movq    %rbx, 56(%rax)
    movq    56(%rsp), %rbx
    movq    %rbx, 64(%rax)
    movq    64(%rsp), %rbx
    movq    %rbx, 72(%rax)
    movq    camlRun@GOTPCREL(%rip), %rbx
    movq    %rax, (%rbx)
    movq    camlRun__3@GOTPCREL(%rip), %rax
    movq    %rax, 8(%rbx)
    movq    camlRun__2@GOTPCREL(%rip), %rax
    movq    %rax, 16(%rbx)
    movq    $1, %rax
    call    camlRun__f_1251@PLT
.L112:
    movq    $1, %rax
    call    camlRun__g_1272@PLT

L'optimisation des programmes en style impératif lapidaire est donc excellente. Dans un autre langage de haut niveau (Haskell, Lisp, etc.), vraisemblablement, seule la pile serait exploitée sans qu'il y ait besoin d'activer un ramasse-miettes pendant les calculs. Le choix de la représentation la moins-disante, donc la plus proche du genre des langages machines qu'on retrouve dans la quasi-totalité des processeurs généralistes, semble être a priori le meilleur choix pour un backend final générique. La programmation des backends spécifiques en serait sans doute simplifiée et il n'y aurait plus qu'un backend commun à gérer en amont. Il faudrait faire en sorte que seule l'extension des opérateurs de base (ajout d'une fonction logarithme par exemple) soit éventuellement nécessaire.

[david-michel1]

Pour OCaml, le code assembleur est satisfaisant mais le bytecode ne dépile jamais les valeurs inutilisées, vu qu'il lui faudrait dépiler en bas de la pile… Pour une discipline d'usage des registres bien choisie, les représentations en arbre et en séquences d'un calcul sont équivalentes. On pourrait donc relaxer la représentation en autorisant les assignations de registres à êtres associées à des arbres représentant les expressions à calculer. La fonction transformant un arbre en séquence n'est pas compliquée et pourrait être ajoutée à la structure encapsulant le type du backend bas-niveau.

L'important est que la représentation bas-niveau soit figée, donc la plus proche possible de ce qui est traduisible dans le plus grand nombre de langages de programmation. En pratique on sera limité aux langages impératifs, aux langages fonctionnels et aux langages à piles (on oublie Prolog pour l'instant, ainsi que les machines de Turing, les systèmes de tagues et autres bizarreries). Les langages fonctionnels savent gérer les piles très hautes car leurs interpréteurs déterministes sont des machines à piles, mais les langages impératifs sont mauvais dans cet exercice (sauf exception ou paramétrage système généreux); dans ce dernier cas la traduction facilitée sous la forme que séquences d'instructions sur des registres prendrait tout son sens.

[denismerigoux]

Salut David, merci pour cette analyse qui est très pertinente. Je suis d'accord que si l'on veut faire de la génération de code bas-niveau avec un contrôle très fin sur l'assembleur optimisé alors une représentation intermédiaire comme celle que tu proposes est idéale. Je suis aussi d'accord qu'avoir une représentation intermédiaire figée (appelons là CGIR pour Code Generation Intermediate Representation) permettrait de faire une "separation of concerns" entre la pipeline depuis M/M++ et ce qui est génération de code vers les différents backends est une très bonne idée.

Par contre je ne suis pas encore convaincu qu'il faille être aussi bas-niveau que ce que tu proposes sur CGIR. En effet la CGIR que tu proposes est très proche d'une intermediate representation de bas niveau dans un compilateur optimisant, surtout pour la partie instructions à trois opérandes. En effet cette représentation en instructions à trois opérandes me semble être la principale différence entre la CGIR que tu proposes et ce qu'on a déjà dans le backend C DGFiP (où on utilise déjà des registres dans un tableau de variables, le TGV). C'est excellent si l'on cherche la performance mais je suis pas sûr que la performance du code généré soit le seul paramètre que l'on souhaite optimiser ici.

Pour le backend C de Mlang, la performance est le paramètre le plus important parce qu'on veut faire des opérations en batch donc on veut in fine les optims débloquée par les instructions à trois opérandes mais GCC ou Clang les font déjà dans leurs pipelines de compilation ; on peut très bien générer du code C avec des right-hand side d'assignation plus compliquée et le compilo C les optimisera (sans doute mieux que nous).

Pour ce qui est des autres backends plut haut niveau (Java, Ocaml, etc.), j'ai bien peur que la lisibilité du code généré soit un paramètre important qu'il nous faille respecter. En effet, même si sémantiquement on s'en fout et que le code généré peut être aussi dégeulasse que l'on veut tant qu'il soit sémantiquement correct, dans mon labo de recherche on a observé à de nombreuses reprises que la lisibilité du code généré était très importante pour convaincre les utilisateurs d'utiliser le code généré. Voir à ce propos : https://jonathan.protzenko.fr/2019/01/04/behind-the-scenes.html. C'est d'ailleurs un des requirements qui a influencé le design de BIR tel qu'elle est actuellement. Ce dont j'ai peur c'est qu'en introduisant les instructions à trois opérandes et la floppée de variables intermédiaires que ça entraîne ça ne dégrade trop la lisibilité du code, donc que les potentiels utilisateurs n'arrivent pas à relier le code généré au M/M++ source et qu'on ait du mal à faire adopter Mlang à cause de ça.

Pour écarter ce risque, le mieux c'est de discuter avec les potentiels utilisateurs de backends de Mlang (en Java, etc.) et leur demander s'ils seraient prêts à accepter du code générer sans regarder ce qu'il y a à l'intérieur. Si ils s'en foutent, alors go :) Sinon faut leur expliquer qu'ils ne peuvent pas avoir un code très performant ET très lisible :)

[david-michel1]

Après analyse plus approfondie du bytecode OCaml, je suis revenu dans mon second message sur les problèmes posés par une représentation trop proche d'un assembleur RISC, en particulier concernant les cibles de type machine à piles (genre machine ZINC). Je proposais de garder les expressions composés sous forme d'arbres. Une fonction qui transformerait les arbres en suite d'instructions sur des registres serait fournie pour ceux qui en aurait l'utilité.

On peut toujours généraliser une représentation. On pourrait même passer par des graphes de dépendances au lieu de listes d'instructions au cas où on voudrait exporter du code parallélisable. Mais ça serait inutile car la parallélisme dans la calculette est géré au niveau des contribuables. Vu qu'il y en a des millions, quel serait l'intérêt de faire du multithreading sur une seule instance de calcul ? Autant lancer une calculette sur chaque thread et traiter le plus de contribuables possible.

Je ne pense pas qu'il soit raisonnable de faire confiance à l'efficacité des outils tiers. Il y a de bons compilateurs optimisants; il y en a aussi de très mauvais, même sur des plateformes dites «pros». Il serait donc souhaitable - tant que le travail à engager reste raisonnable - de proposer un CGIR le plus optimisé possible qui soit compatible avec les cibles usuelles: impératives et fonctionnelles. Il y a un équilibre à trouver. Mais se dire que le compilateur fera de toute manière le boulot, c'est se défausser d'une responsabilité importante. Autant ne rien optimiser du tout dans ce cas: le compilateur C, Java, etc. s'en chargera… On se méprend beaucoup trop sur le talent des développeurs tiers, dont on ne sait rien a priori. J'ai déjà eu a corriger des bugs critiques dans des librairies standards réputées d'excellente qualité: elles me faisaient planter des applis en production (par exemple, le moteur d'expression régulière de Java a une complexité exponentielle qui fait que des applis peuvent mouliner jusqu'à la mort du système solaire à cause d'un analyseur mal foutu). La DGFiP exploite des tas d'infrastructures antédiluviennes, exotiques, paramétrées de manière opaque, parfois programmées en interne par on ne sait qui on ne sait quand: on ne sait pas ce qu'elles font. Le conseil habituellement donné est d'être souple avec les entrées et rigide avec les sorties, donc produire du code suffisamment efficace sans autre forme de retraitement; si tel ou tel compilateur réussit à optimiser encore un peu plus, et bien tant mieux.

Le code généré sera relu ou audité par des gens ayant une expertise assez élevée, le genre qui ne reculera pas devant un peu de complexité. Les programmes en C, même les plus simples, sont déjà illisibles. Si l'expert démissionne devant une fonction calculant des assignations d'expressions algébriques, il il faudra qu'il change de métier. L'excuse de la complexité, on me la donnait déjà pour justifier l'abandon des langages fonctionnels et autres méthodes formelles: typage trop complexe, les gens n'accrocheront pas, ça ne sert à rien… Ce qu'il faut, c'est que le code soit de qualité, donc qu'il soit uniforme, sans bizarrerie, avec un style homogène facile à comprendre quitte à le documenter. Le compirateur en C inclut des commentaires autour du code pour expliquer à quelles instructions elles se réfèrent.De toute manière, relire le code généré ne sert que pendant les phases de conception et de déboguage. Qui relit le code assembleur généré par gcc pour se convaincre qu'il est correct ? Les backends sont les assembleurs de MLang. Ceux qui auront à les certifier, ce seront sans doute des habitués du service BSI4-IRCALCUL.

A priori, on pourrait imaginer un CGIR isomorphe à un langage avec une mémoire globale de type clé-valeur, des procédures non-récursives (n entrées, aucune sortie), des assignations de type variable-expression, des sorties d'erreurs (informative, anomalie et discordance, bloquantes ou non) des itérateurs finis (typiquement des boucles pour I = X a Y avec I un compteur local) et un stop I pour sortir prématurément des boucles. On resterait sur quelque chose de tout de même expressif qui serait terminant et algorithmiquement complet, donc assez efficace tout en étant potentiellement prouvable automatiquement (équivalent à de la récursion primitive, cf. le langage LOOP-exit de Valarcher, https://lacl.u-pec.fr/valarcher/Publi/fi2011.pdf). On pourrait ajouter un découpage en modules et une décoration de type cible à certaines procédures pour signifier qu'elles seront des points d'entrées dans la librairie générée (modules/cible = fichier/fonction extern pour C, = classe/méthode publique pour Java, = module/valeur pour OCaml, etc.)

[denismerigoux]

Ok si je résume ta proposition :

• tu créés une nouvelle représentation intermédiaire CGIR qui se placera après BIR dans la chaîne de compilation et avant le backend C DGFiP
• CGIR est un langage impératif assez généraliste sans variables locales mais où tout est placé dans des registres matérialisés sous forme de tableau (comme le TGV), à base d'assignations avec des conditionnelles et des boucles limitées (pas de récursion générale), un système d'unités de compilation + prise en compte de la visibilité et la gestion d'erreur

Merci pour tes explications, je suis assez convaincu du bien-fondé de tout ça. Concernant la lisibilité je te fais confiance pour expliquer en interne quand il le faudra les choix qu'on a fait. Du coup les prochaines étapes ce serait :

• écrire l'AST de CGIR
• implémenter BIR -> CGIR
• implémenter CGIR -> backend C DGFiP

Tu penses pouvoir te charger ça dans les semaines à venir ?

[david-michel1]

Je vais essayer de faire quelque chose. Comme je suis encore en train de découvrir le code et les spécifications, je ne peux pas donner de calendrier précis pour l'instant. J'en saurai plus la semaine prochaine et j'espère avoir un prototype mi-octobre (en étant optimiste; j'ai des obligations les prochaines semaines).

Le cahier des charges sera sans doute à amender. J'imagine par exemple qu'il serait utile d'avoir des instructions applicables à toutes les variables de la même classe (saisie, calculée ou base), quelque chose dans ce genre:

# VAR est un identifiant local à la partie entre accolades
pour toute VAR calculee {
  VAR = indefini;
} 

Le code généré serait une itération sur les tableaux stockant les variables de ces classes, par exemple en C DGFIP:

for (int i = 0; i < taille_calculee; i++) {
  DC_[i] = 0;
}

L'étude du code des calculs primitifs et correctifs m'en apprendra plus. Ceci dit, ces calculs sont encore en cours de travaux et le résultat final dépendra des choix de conception du langage MPP.