Haut niveau / optimisation sémantique

Question

J'écris un compilateur, et je suis à la recherche de ressources sur l'optimisation. Je compile en code machine, donc tout à l'exécution est hors de question.

Ce que j'ai cherché ces derniers temps est moins optimisation de code et plus sémantique / optimisation de haut niveau. Par exemple:

free(malloc(400)); // should be completely optimized away

Même si ces fonctions étaient complètement inline, ils pourraient éventuellement appeler des fonctions de mémoire OS qui ne peut jamais être mise en ligne. J'aimerais être en mesure d'éliminer complètement cette déclaration sans créer des règles spéciales cas dans le compilateur (après tout, malloc est juste une autre fonction).

Un autre exemple:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

Dans cette situation, j'aimerais pouvoir initialiser la capacité de b à str.Length + 2 (assez pour tenir exactement le résultat, sans perdre la mémoire).

Pour être tout à fait honnête, je ne sais pas où commencer dans la lutte contre ce problème, donc j'espérais un endroit pour commencer. Y at-il eu des travaux dans des domaines similaires? Y a-t-il des compilateurs qui ont mis en œuvre quelque chose comme ça dans un sens général?

Answer 1

Pour faire une optimisation sur 2 ou plusieurs opérations, vous devez comprendre la relation algébrique de ces deux opérations. Si vous affichez les opérations dans leur domaine de problème, ils ont souvent de telles relations.

Votre libre (malloc (400)) est possible parce que libre et malloc sont inverses dans le domaine d'allocation de stockage. Beaucoup d'opérations ont et l'enseignement du inverses compilateur qu'ils sont inverses, et de démontrer que les résultats d'une manière inconditionnelle flux de données dans l'autre, est ce qui est nécessaire. Vous devez vous assurer que vos sont vraiment inverses inverses et il n'y a pas une surprise quelque part; a / x * x ressemble juste la valeur a, mais si x est égal à zéro, vous obtenez un piège. Si vous ne se soucient pas du piège, il est l'inverse; si vous faites attention du piège alors l'optimisation est plus complexe:       (Si (x == 0) puis piège () d'autre a) qui est toujours une bonne optimisation si vous pensez fracture est cher.

D'autres relations « algébriques » sont possibles. Par exemple, il y a peut idempotent opérations: mise à zéro une variable (réglage quoi que ce soit à la même valeur à plusieurs reprises), etc. Il y a des opérations où l'on agit opérandes comme un élément d'identité; X + 0 ==> X pour tout 0. Si X et 0 sont des matrices, cela est encore vrai et un gain de temps important.

D'autres optimisations peuvent se produire lorsque vous pouvez raisonner abstraitement sur ce que le code fait. « L'interprétation abstraite » est un ensemble de techniques pour raisonner sur les valeurs de classement des résultats intéressants dans différents bacs (par exemple, ce nombre entier est inconnu, nul, négatif ou positif). Pour ce faire, vous devez décider bacs sont utiles, puis calculer la valeur abstraite à chaque point. C'est utile quand il existe des tests sur les catégories (par exemple, « si (x <0) {... » et vous savez abstraite que x est inférieur à zéro; vous pouvez les optimiser loin le conditionnel.

Une autre façon est de définir ce qu'est un calcul fait symboliquement, et simuler le calcul pour voir le résultat. Voilà comment vous calculé la taille effective du tampon nécessaire; vous calculé la taille du tampon symbolique avant que la boucle a commencé, et simulé l'effet d'exécuter la boucle pour toutes les itérations. Pour cela, vous devez être en mesure de construire des formules symboliques représentant les propriétés du programme, composer de telles formules, et souvent simplifier ces formules quand ils unusably complexes (types de fane dans l'abstrait schéma d'interprétation). Vous voulez également un tel calcul symbolique prendre en compte les propriétés algébriques décrites plus haut. Les outils qui font bien sont bonnes à des formules construire, et les systèmes de transformation du programme sont souvent de bonnes bases pour cela. Un système de transformation du programme source-source qui peut être utilisé pour faire est DMS Software Reengineering Toolkit .

Ce qui est difficile est de décider quelles optimisations vaut la peine, parce que vous pouvez mettre fin à de garder une trace de grandes quantités de choses qui ne peuvent pas payer. cycles informatiques sont moins en moins cher, et il est donc logique de suivre plusieurs propriétés du code dans le compilateur.

Answer 2

Le Broadway cadre de peut-être dans la veine de Qu'est-ce que vous cherchez. Documents sur la "transformation source-source" sera probablement aussi instructif.