Optimisation de Code

Le code intermédiaire généré par un compilateur à la forme suivante.

  1. A quel type de programme correspond ce code intermédiaire? Tri à bulles
  2. Tracer le graphe des flôts
  3. Eliminer les sous-expressions communes
  4. Effectuer une propagation des copies et éliminer le code inutile.
  5. Traiter les variables d'induction et les invariantes de boucle.

Elimination de sous-expressions communes

01 i=m-1 début de bloc 0 (avant boucle )
02 j = n
03 T1 = 4*n
04 v =a [T1] fin de bloc 0 car un autre bloc démarre à la ligne suivante
05 i = i+1 début de bloc 1 (cible de goto remontant)
06 T2 = 4*i
07 T3 = a[T2]
08 if T3 < v goto 5 fin de bloc (car branchement)
09 j = j - 1 début de bloc 2
10 T4 = 4*j
11 T5 = a[T4]
12 if T5 > v goto 9
13 if i >= j goto 23 fin de bloc 2, car branchement
14 T6 = 4*i
15 x = a[T6]
16 T7 = 4*i T7 ↔ T6 et T6 n'est pas modifié avant utilisation de T7 : éliminer T7
17 T8 = 4*j
18 T9 = a[T8]
19 a[T7 T6] = T9
20 T10 = 4*j T8 ↔ T10 et T8 n'est pas modifié avant utilisation de T10 : éliminer T10
21 a[T10 T8] = x
22 goto 5 fin de bloc 3 : on sort pour aller dans bloc 1.
23 T11 = 4*i début de bloc 4 , qu'on peut entrer par branchement depuis la ligne 13.
24 x = a[T11]
25 T12 = 4*i T12 ↔ T11 et T11 n'est pas modifié avant utilisation de T12 : éliminer T12
26 T13 = 4*n
27 T14 = a[T13]
28 a[T12T11] = T14
29 T15 = 4*n T15 ↔ T13 et T13 n'est pas modifié avant utilisation de T15 : éliminer T15
30 a[T15T13] = x fin de bloc 4? on ne connait pas la suite…

Propagation des copies

on a

 24 x = a[T11]
 
 30 a[T15] = x

Alors, en supposant que l'assembleur permet des affectations de tableau à tableau, on peut écrire à la place

 24 noop
 
 30 a[T15] = a[T11]

Ensuite, on note que

 04  v = a[T1]
 
 08  if a[T2] < v...
 
 12  if a[T4 > v ...

pourrait donner, puisque la valeur de v ne sert pas ailleurs et la valeur de a[T1] n'est pas modifiée depuis l'affectation de v jusqu'à ces lignes,

 04  noop 
 
 08  if a[T2] < a[T1]...
 
 12  if a[T4 > a[T1] ...

Variables d'induction et invariantes de boucle


 
m1ilc/compil_td_5.txt · Dernière modification: 2010/01/04 16:31 par suitable