Option Traduction de Programmes TD Mercredi 28 mars

Génération de code MMIX

Dans les 2 questions, on suppose que le registre 0 contient un pointeur vers un bloc de la pile où les variables sont rangées dans l’ordre a,b,c,d etc. et que toutes les variables sont de 4 octets avec signe.

1. Quel est le code optimum pour l’expression suivante si le nombre de registres disponibles est: (a) 5? ou (b) 6?

A[i]*B[i]*C[i]+A[j]*B[j]*C[j]+A[k]*B[k]*C[k]+A[l]*B[l]*C[l] +
X[s]*Y[s]+X[t]*Y[t]+X[u]*Y[u]+X[v]*Y[v]
2. ADDT $T1, $a,  $b
ADDT $T2, $b,  $c
ADDT $T3, $T1, $d
ADDT $T4, $T2, $T3
ADDT $T3, $b,  $c
ADDT $T5, $T1, $d
ADDT $T6, $T3, $T5
ADDT $T7, $a,  $c
ADDT $T8, $T7, $b
ADDT $T9, $T4, $T8
ADDT $d,  $T6, $T9

Pour cette suite d’instructions du code intermédiaire, donner

(a) Le graphe orienté acyclique des dépendances des valeurs calculées

(b) Un ordre de calcul de ces valeurs qui respecte les dépendances mais qui est différent de l’ordre cité

(c) Le graphe des incompatibilités des valeurs, étant donné cet ordre de calcul

(d) Le code généré en utilisant l’algorithme de coloration de ce graphe, si le nombre de registres disponibles est de 4.

Ce code est-il optimal? (pour votre ordre et/ou pour tous ordres)