Backend générique bas-niveau #183
Description
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.