Le Projet Doom

Késako le "code généré" ?

Le code généré est une technique d'optimisation qui consiste à générer "à la volée" un code optimisé pour nos données plutôt que d'utiliser un code generaliste plus lent.

Prennons par exemple le cas d'un algo généraliste qu'on voudrait optimiser parce qu'on y fait appel un grand nombre de fois :

A=DAT0.B
P=8
{
  ?ABIT=0.0 { B+B.A }
  ASRB.B
  P+1 UPNC
}

Ce code décale B champ A n fois vers la gauche, où n est le nombre de bits allumés dans Ab. Ce code ne sert strictement à rien dans Doom, ce n'est qu'un exemple. Mais imaginez que vous voulliez l'optimiser, que faire ?

La première optimisation évidente consiste à dérouler la boucle :

A=DAT0.B
?ABIT=0.0 { B+B.A }
?ABIT=0.1 { B+B.A }
?ABIT=0.2 { B+B.A }
?ABIT=0.3 { B+B.A }
?ABIT=0.4 { B+B.A }
?ABIT=0.5 { B+B.A }
?ABIT=0.6 { B+B.A }
?ABIT=0.7 { B+B.A }

Résultat : 37,5 octets au lieu de 12, mais seulement 247,5 cycles dans le pire des cas au lieu de 458,5 !!! Voilà une belle optimisation en vitesse... Bon bien sûr on pourrait améliorer encore, on pourrait par exemple utiliser une table donnant pour toutes les valeurs possibles de A (il y en a 256), le nombre de décalages de B à faire, et ensuite utiliser 9 routines spécialisés pour faire ces décalages, mais aucune des améliorations possibles ne peut égaler celle du code généré lorsque le nombre d'itérations augmente.

Maintenant, imaginez que la valeur lue de A ne change pas pendant un grand nombre d'itérations consécutives. C'est la première condition nécessaire pour qu'il soit interressant d'utiliser la technique du code généré. Par exemple, dans Doom, la valeur de l'angle de visée ne change pas pendant toute la durée de la construction de l'image. Dans ces conditions, si on connait la valeur de A on a envie d'optimiser la routine pour cette valeur precise. Par exemple si A vaut # ABh, le code devient :

BSL.A
B+B.A

En effet, # ABh = # 10101011b, il y a donc 5 bits allumés, et donc 5 décalages de B à faire, et c'est bien ce que fait ce code.
A titre de comparaison, ce code fait le calcul en seulement 2 octets et 16 cycles !!! Le gain est énorme !

C'est interessant, mais comment l'exploiter en pratique ?

La première solution consiste à écrire les 9 routines possibles suivant le nombre de bits allumés dans A :

*R0 RTN
*R1 B+B.A RTN
*R2 B+B.A B+B.A RTN
*R3 BSL.A BSRB.A RTN
*R4 BSL.A RTN
*R5 BSL.A B+B.A RTN
*R6 BSL.A B+B.A B+B.A RTN
*R7 BSL.A BSL.A BSRB.A RTN
*R8 BSL.A BSL.A RTN

Ensuite il suffit de stocker à une adresse fixe (par exemple en RAM système - que j'appelles d'habitude RAM reservée mais je ne veux pas qu'il y ai de confusion) l'adresse de la routine à utiliser. Ainsi pour utiliser la routine il suffit de faire :

*ROUTINE
LC(5) ADRESSE.ROUTINE
PC=(C)

Ce qui fait quand même 5.5 octets et 40 cycles en plus ! Lorsque A change il faut aussi mettre à jour la valeur de ADRESSE.ROUTINE, en comptant le nombre de bits de A et on récupérant l'adresse de la routine correspondante. C'est long mais comme cela n'arrive que très rarement on y gagne quand même.

Maintenant on peu encore gagner du temps lors de l'appel de la routine : il suffit de stocker directement la routine en RAM système, au lieu de son adresse (il faut pour cela avoir suffisement de place !). Ainsi la constante ADRESSE.ROUTINE est remplacée par la constante ROUTINE, et l'accès à la routine devient simplement :

GOSBVL ROUTINE

Par contre quand A change, il faut maintenant recopier la routine correspondante à l'adresse ROUTINE.

Maintenant il est important de vous reveler que tout ce que je viens de vous dire n'est pas du code généré, mais juste une introduction pour que vous en compreniez bien l'utilité ! En effet, il y a une deuxième condition nécessaire pour qu'il soit interessant d'utiliser le code généré : il faut que le nombre de routines possibles soit beaucoup trop grand pour rendre possible l'écriture de toutes les routines spécialisées. Dans l'exemple précédent, il n'y avait que neuf routines possibles, ce qui est codable, mais dans le cas qui nous interesse dans Doom, les angles peuvent prendre 256 valeurs possibles, et comme il s'agit de routines assez grosses, même en tennant compte des symétries, ça commence a prendre beaucoup de place : si chaque routine prennait en moyenne 20 octets, ça ferait plus de 5Ko en tout !!! Mais surtout ça ne serait pas réalisable, car personne ne voudrait s'embetter à écrire et optimiser 256 routines similaires ! Sans oublier que pour le débugage ça devient l'horreur !!! (en fait pour les angles on pourait éventuellement le faire, mais on risque fort d'utiliser le code généré pour le zoom des sprites, car là il y a encore plus de routines possibles, et encore plus compliquées !)

Du point de vue pratique, le code généré ne diffère de la technique précédante que sur la manière d'écrire la routine à l'adresse ROUTINE : au lieu de recopier cette routine, on la génére à la volée. Il s'agit en fait d'écrire en assembleur un code qui va écrire un autre code executable (cela n'a pourtant rien a voir avec de la compilation) ! Pour cela on part de la routine généraliste, dont on ne garde que les instructions qui ne dépendent pas de A, et on les convertit en langage machine (sans oublier que les codes LM sont donnés sans inversion !). Par exemple pour la routine donnée tout à l'heure :

A=DAT0.B % ça on s'en fout maintenant !
?ABIT=0.0 { B+B.A } % -> B+B.A -> 5C
?ABIT=0.1 { B+B.A } % idem
?ABIT=0.2 { B+B.A } % idem
?ABIT=0.3 { B+B.A } % idem
?ABIT=0.4 { B+B.A } % idem
?ABIT=0.5 { B+B.A } % idem
?ABIT=0.6 { B+B.A } % idem
?ABIT=0.7 { B+B.A } % idem
RTN % -> 10

Et hop voila une routine simple qui va générer le code correspondant pour une valeur de A lue :

A=DAT0.B % lecture de A
D0=(5)ROUTINE
LC 5C % code correspondant à "B+B.A"
P=8
{
  ?ABIT=0.0 {
    DAT0=C.B % écriture de l'instruction "B+B.A"
    D0+2 % on passe a l'instruction suivante
  }
  ASRB.B
  P+1 UPNC
}
LC 10 DAT0=C.B % écriture du RTN

Et voilà ! CA c'est du code généré ! Vous noterez quand même que le code généré est moins optimisé que ce qu'on pourrait faire à la main, puisqu'il ne remplace pas les séquences "B+B.A B+B.A B+B.A B+B.A" par "BSL.A". Mais ce n'est pas bien grave en fait...

J'espère que vous avez compris... Parce que je ne suis pas très sûr d'avoir été clair, malgrès mes efforts ;). Maintenant : essayez de faire une routine de multiplication en code généré, vous verrez, ce n'est pas si dur en fait à partir de mon exemple, et c'est l'essentiel de la routine de rotation...