La représentation intermédiaire
Depuis des années, je trouve que la structure du microprocesseur 68000 de Motorola est très agréable pour celui qui souhaite utiliser son assembleur, particulièrement grâce à ses 2 X 8 registres interchangeables (D0 - D7, A0 - A7). Mais curieusement, si j'en crois ce que j'en ai lu, il est difficile de créer des compilateurs efficaces pour les architectures CISC, dont le 68000 et ses descendants sont un bon exemple. Comme l'absence de registres spécialisés doit au contraire éviter des problèmes potentiels, je suppose que cela vient de ses modes d'adressage, nombreux et élaborés.
Il m'est donc venu l'idée de la représentation intermédiaire. Il s'agirait d'une structure arborescente qui serait créée au moment de l'analyse du programme source, par exemple sous-programme par sous-programme, et qui en serait une traduction manipulable par les étapes suivantes du compilateur (j'ignore si cela a déjà été utilisé). Ce serait tout d'abord une copie fidèle du source mais elle serait ensuite transformée pour optimisation en suivant des règles précises et en fonction du processeur cible car les différentes architectures, qu'elles soient classées en CISC ou en RISC, ont chacune leurs spécificités. Pour le 68000 par exemple, en déplaçant des incrémentations de pointeurs il est possible de tirer parti de l'adressage indirect postincrémenté. Les règles se baseraient sur des particularités (ou leur absence) telles le fait qu'un indice utilisé dans une boucle ne soit modifié qu'à un seul endroit.
Une fois l'algorithme transformé (et en fait normalisé), il serait certainement beaucoup plus simple d'avoir une étape de génération de code qui soit efficace. L'optimisation de la représentation intermédiaire pourrait être déconnectable afin de choisir entre une compilation rapide et une compilation efficace.
Voici un exemple simple suivi de la façon dont le source peut être modifié (ce n'est pas la seule). Les traductions en assembleur 68000 n'ont été traitées que sur papier :
void Copier1() { short Tab1[10],Tab2[10]; short i; for (i = 0; i < 10; i++) Tab2[i] = Tab1[i]; } ;Traduction en assembleur 68000 Taille Duree (octets) (cycles) CLR.W D1 2 4 LEA Tab1(A6),A0 4 8 LEA Tab2(A6),A1 4 8 MOVEQ #20,D2 2 4 BRA Test_for_1 2 10 34 For_1: ------------- MOVE.W 0(A0,D1.W),0(A1,D1.W) 6 24 ADDQ.W #2,D1 2 4 Test_for_1: CMP.W D2,D1 2 4 BMI For_1 2 10/8 42 * 10 + 12 ---- ------------ 26 466 (10 itérations) void Copier2() { /* Optimisation propre à la famille 68000 */ short Tab1[10],Tab2[10]; short *pt1,*pt2; short i; i = 10-1; pt1 = Tab1; pt2 = Tab2; do *pt2++ = *pt1++; while (--i != -1); i = 10; /* optionnel */ } ;Traduction en assembleur 68000 Taille Duree (octets) (cycles) MOVEQ #9,D1 2 4 LEA Tab1(A6),A0 4 8 LEA Tab2(A6),A1 4 8 20 Do_1: ------------ MOVE.W (A0)+,(A1)+ 2 12 DBRA D1,Do_1 4 10/14 22 * 10 + 4 --------------- MOVEQ #10,D1 ; Opt 2 4 ---- ----- 18 248 (10 itérations)
Le fait que la valeur limite mettant fin à la boucle ne soit plus une constante mais une variable complique les choses :
void Copier3(short n) { short Tab1[100],Tab2[100]; short i; for (i = 0; i < n; i++) Tab2[i] = Tab1[i]; } ;Traduction en assembleur 68000 Taille Duree (octets) (cycles) CLR.L D1 2 6 LEA Tab1(A6),A0 4 8 LEA Tab2(A6),A1 4 8 MOVE.W n(A6),D2 4 12 EXT.L D2 2 4 (*) ASL.L #1,D2 2 10 BRA Test_for_1 2 10 58 For_1: ---------- MOVE.W 0(A0,D1.L),0(A1,D1.L) 6 24 ADDQ.L #2,D1 2 8 Test_for_1: CMP.L D2,D1 2 6 BMI For_1 2 10/8 48 * 10 + 14 ---- --------------- 32 552 (10 itérations) (*) Pour le 68020 et les 680x0 ultérieurs, il y a eu une amélioration des modes d'adressage qui permet d'éviter ici l'extension, la multiplication par 2 et l'utilisation des 32 bits de D1 et D2 (la multiplication par la taille des éléments du tableau est incluse dans le mode d'adressage utilisé). void Copier4(short n) { /* Optimisation propre à la famille 68000 */ short Tab1[100],Tab2[100]; short *pt1,*pt2; short i,j; i = 0; /* optionnel */ j = n; if (j > 0) /* Parce que n signé */ { i = j; /* optionnel */ pt1 = Tab1; pt2 = Tab2; while (--j != -1) *pt2++ = *pt1++; } } ;Traduction en assembleur 68000 Taille Duree (octets) (cycles) CLR.W D1 ; Opt 2 4 MOVE.W n(A6),D2 4 12 TST.W D2 2 4 BLE Fin_if_1 2 8 MOVE.W D2,D1 ; Opt 2 4 LEA Tab1(A6),A0 4 8 LEA Tab2(A6),A1 4 8 BRA Test_while_1 2 10 58 While_1: ----------- MOVE.W (A0)+,(A1)+ 2 12 Test_while_1: DBRA D2,While_1 4 10/14 22 * 10 + 14 ---- ---------------- Fin_if_1: 28 292 (10 itérations)
Il est à noter que même sans chercher à optimiser systématiquement le code, la représentation intermédiaire peut être balayée afin de comptabiliser les occurrences des identificateurs manipulés et leurs diverses utilisations. Ceci donne de précieuses indications sur les variables qu'il faut traiter en priorité et leurs affectations aux registres disponibles. On voit aussi que l'instruction LEA (Load Effective Address) est ici employée régulièrement.