Élimination globale des sous-expressions communes

Lorsqu'on envisage l'optimisation des compilateurs, deux questions viennent immédiatement à l'esprit ; premièrement, pourquoi et dans quelle mesure l'optimisation est-elle nécessaire et deuxièmement, dans quelle mesure est-elle possible. Lorsque l'on considère la seconde question, on peut rapidement se décourager puisque l'on sait que le problème d'équivalence des programmes est récursivement insoluble. Il est, bien sûr, clair à partir de cela qu'il n'existera jamais de techniques pour générer un programme complètement optimal. Cependant, ces résultats d'insolvabilité n'excluent pas la possibilité de techniques ad hoc pour l'amélioration des programmes ou même une théorie partielle qui produit une classe de programmes équivalents optimisés à divers degrés. Les raisons pour lesquelles l'optimisation est requise semblent, à mon avis, tomber dans deux grandes catégories. La première que j'appellerai « locale » et la seconde « globale ».