Votre optimisation d'arbre de syntaxe abstraite préférée

Question

Si vous construisiez un compilateur, quelle optimisation au niveau AST serait la plus agréable?

Answer 1

Une optimisation plus facile à faire sur l'AST (plutôt que, par exemple, le CFG) est l'optimisation d'appels en aval: si vous voyez un sous-arbre de la forme:

RETURN
    CALL f
        ARGS x, y, ...

Vous pouvez le remplacer par un saut vers f. Si f(a, b) est la fonction dans laquelle l'appel final apparaît, le remplacement est aussi simple que:

a = x; b = y
JUMP to root of tree

Je trouve plus facile de représenter ce saut comme un "ient spécial: redémarrer " déclaration, que la traduction AST - > CFG considère comme une arête vers le premier nœud. Passer à d'autres fonctions est un peu plus délicat, car vous ne pouvez pas simplement définir des variables locales, vous devez réellement anticiper la manière dont les arguments leur sont transmis et vous préparer à traduire cela à un niveau inférieur. Par exemple, l'AST pourrait avoir besoin d'un nœud spécial pouvant ordonner à une passe ultérieure d'écraser le cadre de pile actuel avec les arguments et de sauter en conséquence.

Answer 2

Généralement, vous ne pouvez pas réaliser d’optimisations intéressantes au niveau AST, car vous avez besoin d’informations sur la manière dont les données circulent d’une partie du programme à une autre. Bien que le flux de données soit implicite dans la signification de l'AST, il n'est pas facile de le déterminer en inspectant uniquement l'AST. C'est pourquoi les utilisateurs des compilateurs et des optimiseurs construisent d'autres représentations de programme (y compris des tables de symboles, des graphiques de flux de contrôle, la définition de définitions, le flux de données). et formulaires SSA, etc.).

Avoir un analyseur syntaxique pour une langue est l’essentiel pour analyser / manipuler cette langue. Vous avez besoin de tout cela pour faire du bon travail.

Si vous avez toutes les autres représentations, vous pouvez envisager d'effectuer des optimisations au niveau AST. La plupart des compilateurs de bâtiment ne s'en préoccupent pas; ils se convertissent en une représentation de flux de données et l'optimisent simplement. Mais si vous souhaitez reproduire le code source avec des modifications, vous avez besoin de l'AST. Vous aurez également besoin d'une jolie imprimante pour vous permettre de régénérer le code source. Si vous allez aussi loin, vous allez vous retrouver avec une source à la source système de transformation de programme.

Le DMS Software Reengineering Toolkit est un système qui transforme les AST, en utilisant tous ces autres représentations pour permettre les analyses nécessaires aux transformations.

Answer 3

L’un des avantages de l’optimisation dans AST est qu’elle peut réduire le temps d’exécution de certaines passes d’optimisation dorsales. Cependant, je pense que ces optimisations doivent être effectuées avec parcimonie, car vous pourriez entraver d'autres optimisations dans le code.

Cela étant dit, une optimisation simple mais intéressante à appliquer au niveau AST ou pendant la génération IR est la simplification de l'expression booléenne de la forme (1 || 2) ou (2 < 3 || A), etc. au résultat net. Je crois que quelques optimisations simples de judas peuvent également valoir la peine.