===== Optimisation de Code =====

Le code intermédiaire généré par un compilateur à la forme suivante.
  - A quel type de programme correspond ce code intermédiaire? // Tri à bulles //
  - Tracer le graphe des flôts 
  - Eliminer les sous-expressions communes
  - Effectuer une propagation des copies et éliminer le code inutile.
  - 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 | <del>T7 = 4*i</del> | T7 <-> T6 et T6 n'est pas modifié avant utilisation de T7 : éliminer T7 |
| 17 | T8 = 4*j |
| 18 | T9 = a[T8] |
| 19 | a[<del>T7</del> T6] = T9 |
| 20 | <del>T10 = 4*j</del> | T8 <-> T10 et T8 n'est pas modifié avant utilisation de T10 : éliminer T10 |
| 21 | a[<del>T10</del> 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 |<del> T12 = 4*i</del> | T12 <-> T11 et T11 n'est pas modifié avant utilisation de T12 : éliminer T12 |
| 26 | T13 = 4*n |
| 27 | T14 = a[T13] |
| 28 | a[<del>T12</del>T11] = T14 |
| 29 | <del>T15 = 4*n</del> | T15 <-> T13 et T13 n'est pas modifié avant utilisation de T15 : éliminer T15 |
| 30 | a[<del>T15</del>T13] = 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 ====