Génération et optimisation de code

La génération et l'optimisation de code transforment les représentations intermédiaires en code cible efficace, permettant aux programmes de s'exécuter plus rapidement ou d'utiliser moins de ressources tout en préservant leur sémantique.

Definition

La génération de code est la production d'instructions cibles (code machine ou bytecode) à partir d'une représentation intermédiaire, et l'optimisation est l'application de transformations préservant la sémantique qui améliorent la vitesse, la taille ou l'utilisation des ressources d'un programme.

Scope

Ce sujet couvre les parties arrière (back end) et médiane (middle end) d'un compilateur : les représentations intermédiaires telles que la forme d'affectation statique unique (SSA), l'analyse de flux de données, les optimisations classiques (propagation de constantes, élimination des sous-expressions communes, optimisations de boucles), la sélection d'instructions, l'ordonnancement d'instructions et l'allocation de registres. Il aborde la manière dont les transformations préservent la sémantique du programme tout en améliorant ses performances.

Core questions

• Comment les transformations de programme peuvent-elles améliorer les performances sans modifier le comportement ?
• Quelles représentations intermédiaires rendent l'analyse d'optimisation efficace ?
• Comment les registres machine limités sont-ils alloués à de nombreuses valeurs de programme ?
• Comment l'exactitude et les performances sont-elles arbitrées dans une optimisation agressive ?

Key theories

Forme d'affectation statique unique

Cytron et ses collègues ont proposé un algorithme efficace pour convertir les programmes en forme SSA, où chaque variable est affectée une seule fois, simplifiant considérablement de nombreuses optimisations basées sur le flux de données.

Allocation de registres par coloration de graphe

Chaitin a modélisé l'allocation de registres comme une coloration de graphe d'un graphe d'interférence, fournissant l'approche fondamentale pour attribuer des valeurs de programme à un ensemble limité de registres machine.

Optimisation basée sur le flux de données

Muchnick et le Dragon Book formalisent l'analyse de flux de données comme le cadre sous-jacent aux optimisations classiques, calculant les propriétés du programme nécessaires pour justifier des transformations sûres.

Clinical relevance

L'optimisation de la génération de code détermine l'efficacité avec laquelle les programmes utilisent les processeurs et la mémoire, ayant un impact considérable sur la consommation d'énergie et les coûts à grande échelle. La forme SSA et l'allocation de registres par coloration de graphe restent des éléments centraux des compilateurs de production et des systèmes juste-à-temps (just-in-time).

History

L'optimisation a débuté avec le compilateur Fortran et s'est développée grâce à l'analyse de flux de données d'Allen et Cocke dans les années 1970. L'allocation de registres par coloration de graphe de Chaitin (1981-82) et la construction efficace de la forme SSA par Cytron et al. (1991) sont devenues des piliers des compilateurs modernes, permettant les pipelines d'optimisation sophistiqués utilisés dans les chaînes d'outils actuelles.

Debates

Agressivité de l'optimisation versus exactitude et prévisibilité

Les concepteurs de compilateurs débattent de l'agressivité de l'optimisation, car l'exploitation de comportements indéfinis et le réordonnancement peuvent générer de la vitesse mais introduire des résultats surprenants ou dangereux, suscitant un intérêt pour l'optimisation vérifiée et prévisible.

Key figures

• Frances Allen
• Gregory Chaitin
• Ron Cytron
• Steven Muchnick
• Alfred Aho

Seminal works

• cytron1991
• chaitin1982
• muchnick1997
• aho2006

Frequently asked questions

Qu'est-ce que la forme SSA ?

La forme d'affectation statique unique est une représentation intermédiaire dans laquelle chaque variable est affectée exactement une fois et les utilisations sont liées à une seule définition, ce qui simplifie et renforce de nombreuses optimisations de compilateur.

Pourquoi l'allocation de registres est-elle difficile ?

Les programmes utilisent généralement beaucoup plus de valeurs qu'il n'y a de registres machine, le compilateur doit donc décider quelles valeurs partagent les registres et lesquelles sont déversées en mémoire ; le problème fondamental est équivalent à la coloration de graphe, qui est généralement difficile du point de vue computationnel.