Questions sur l'optimisation du compilateur

Question

1. De quelles manières un compilateur élimine-t-il les recalculs répétés de sous-expressions? Comment garder une trace des sous-expressions? Et comment identifiez-vous ceux qui se répètent?
2. Outre l'utilisation des opérateurs au niveau des bits, quelles sont certaines des techniques de réduction de la force couramment utilisées par les compilateurs?

Answer 1

1. Je pense que de nombreux compilateurs utilisent SSAPRE (élimination de la redondance partielle d'affectation unique statique) pour éliminer les expressions répétées. Cela nécessite que le code soit au format formulaire SSA , ce qui permet de nombreuses autres optimisations.

2. Je ne suis pas vraiment sûr de cela, mais regardez cette liste de passes LLVM . La LLVM est un IR optimisé pour les compilateurs qui est souvent plus rapide que même GCC. Il y a une petite explication de chaque passe. Si vous avez besoin de plus d'informations, consultez la source LLVM pour ces passes. Il est écrit en C ++ mais reste assez clair et compréhensible.

Éditer: Au fait, si vous développez un compilateur, je recommande vivement LLVM, il est très facile à utiliser et génère un code hautement optimisé.

Answer 2

Pour 1, le nom de l'optimisation que vous recherchez est une élimination de sous-expression commune (CSE). En fonction de votre représentation, cela peut être assez facile. Habituellement, un compilateur aura une représentation intermédiaire d’un programme dans lequel les opérations sont autant que possible décomposées et linéarisées. Ainsi, par exemple, l'expression c = a * b + a * b peut être décomposée en:

v1 = a * b
v2 = a * b
c = v1 + v2

Vous pouvez donc faire du CST à un niveau très bas en recherchant des opérations avec le même opérateur et les mêmes opérandes. Lorsque vous rencontrez un doublon (v2 dans ce cas), vous remplacez toutes les instances de celui-ci par l'original. Nous pourrions donc simplifier le code ci-dessus pour qu'il soit:

v1 = a * b
c = v1 + v1

Cela suppose généralement que vous n'affectez chaque variable qu'une seule fois (formulaire d'affectation statique unique), mais vous pouvez mettre en œuvre quelque chose comme ceci sans cette restriction. Cela devient plus compliqué lorsque vous essayez d'effectuer cette optimisation sur plusieurs branches. Comme Zifre le mentionne, examinez l’élimination de la redondance partielle.

Dans tous les cas, vous obtenez des améliorations de base et il vous suffit de suivre les expressions de base. Vous voudrez peut-être aller un peu plus loin et rechercher des identités arithmétiques. Par exemple, a * b est identique à b * a . De plus, x * (y + z) = x * y + x * z . Cela rend votre optimisation plus compliquée et il n’est pas clair que cela apporterait une telle amélioration des performances. De manière anecdotique, la plupart des avantages d'une optimisation CSE proviennent de calculs d'adresse tels que des accès à des tableaux, et vous n'aurez pas besoin d'identités complexes comme celles ci-dessus.

Pour 2, les réductions de résistance utiles dépendent vraiment de l'architecture pour laquelle vous avez compilé. Habituellement, cela implique simplement de transformer les multiplications et les divisions en décalages, additions et soustractions.

Answer 3

Je recommanderais vivement deux références imprimées sur ces sujets:

1. Conception du compilateur avancé & amp; Mise en œuvre par Steven S. Muchnick
2. Création d'un compilateur d'optimisation par Robert Morgan

Le livre Muchnick est formel, mais il est très lisible et contient une bonne description de toutes les techniques d’optimisation importantes. Le livre Morgan est beaucoup plus pratique et constituerait une excellente base pour un projet de compilation axé sur les techniques d'optimisation. Ni l'un ni l'autre livre n'a beaucoup à dire sur l'analyse lexicale ou l'analyse syntaxique, la connaissance de ces sujets est supposée.

Answer 4

Pour ajouter un livre de plus à la liste des recommandations, consultez " Le délice de pirates " ; par Henry S. Warren. C'est un excellent compendium de techniques d'optimisation d'opérations courantes, telles que la transformation de divisions entières en multiplications.

Answer 5

Vous recherchez une élimination de la redondance partielle (PRE). Les mouvements CSE (des autres réponses) et le code invariant de la boucle sont tous deux assimilés par PRE. (Une variante de PRE est Lazy Code Motion, qui, à mon avis, est optimale).

Découvrez les les notes de conférence de Keith Cooper , qui semblent très bien décrire les techniques.

Ne PAS utilisez SSAPRE. Pour autant que je sache, cela nécessite une forme particulière d’ASS, appelée HSSA, qui présente quelques inconvénients:

• C'est assez compliqué
• Il nécessite une numérotation de valeur globale (et donc SSAPRE ne fournit pas de numérotation de valeur, car il devrait déjà exister).
• Il ne fournit rien si votre langue ne prend pas en charge les pointeurs pour empiler les variables (et si c'est le cas, arrêtez d'écrire votre propre analyse et utilisez LLVM ou gcc).
• gcc a utilisé HSSA pendant un certain temps, mais ils s'en sont éloignés.
• LLVM l'a expérimenté, mais autant que je sache, ils ne l'utilisent plus.

EDIT:

Le livre de Muchnick a une description détaillée, son lien dans une autre réponse.