Quoi de neuf dans les techniques d'optimisation du compilateur ces dernières années?

14

Je m'intéresse à l'optimisation des flux de données et des graphes de flux de contrôle et en particulier aux calculs plus complexes. Mais il sera également intéressant de connaître les dernières inventions dans le domaine des optimisations de judas.

optimization compilers Evgeny Gavrin
la source
2
Dans ma thèse ( diapositives ), j'ai discuté et implémenté l'aplatissement des graphes d'appel dans LLVM; Fondamentalement, c'est une transformation interprocédurale qui supprime la notion de "fonction" car elle fusionne tout le code ensemble, permettant un tas de possibilités intéressantes telles que le mouvement du code interprocédural, les conventions d'appel optimisées pour le site d'appel, l'exécution sans pile, etc.
CAFxX
@CAFxX: les diapositives ont planté Open Office .. avez-vous des photos en ligne à la place?
Yttrill
@Yttrill: slideshare.net/CAFxX/…
CAFxX
Merci d'avoir pu voir cela, même si les graphiques devaient être fins pour être visibles, le texte était bon.
Yttrill

Réponses:

8

Je ne sais pas à quel point c'est nouveau, ou si c'est trop du côté appliqué pour votre intérêt, mais Hoopl montre comment une optimisation de contrôle / flux de données peut être modularisée, avec une propagation des faits sur les sommets du graphique de contrôle étant indépendante de la langage et optimisation spécifique.

Ils font référence à un algorithme de 2002 de Lerner, Grove et Chambers qui compose de simples optimisations en une "superoptimisation".

Max
la source
8

Je suppose que la technique de saturation d'égalité , en tant qu'approche différente du problème de l'optimisation de l'ordre des passes, serait pertinente. A ma connaissance, il n'a cependant pas encore été prouvé pratique par une implémentation concrète dans un compilateur à part entière. Les optimisations de compilation suivantes à partir de preuves peuvent également être intéressantes.

gasche
la source
6

Il y a eu un peu de renouveau dans les compilateurs d'optimisation vérifiés. En plus de l'article de Lerner (mentionné dans un commentaire précédent), vous pouvez regarder le projet CompCert dirigé par Xavier Leroy. Ils ont fait des trucs sympas en spécifiant les optimisations comme preuves vérifiables par machine (en utilisant Coq ). Je n'ai pas encore lu les articles, mais le projet Verified Software Toolchain à Princeton semble également produire des résultats intéressants dans ce domaine.

John Lasseter
la source
1
Nous travaillons également sur un projet similaire à CompCert: CerCo ( cerco.cs.unibo.it ). Contrairement à CompCert, nous visons à produire un compilateur de préservation des coûts concrets vérifié pour un grand sous-ensemble de C (CompCert montre seulement que les propriétés d'extension du programme source sont préservées par compilation). Nous implémentons également dans le compilateur quelques optimisations de boucle modérément complexes, ainsi que des optimisations "légères" comme CompCert, qui devront bien sûr être vérifiées comme étant économiques.
Dominic Mulligan
5

Reconnaître que baz [i] + = force (foo [i], foo [j]) dans une boucle FOR double a des résultats indépendants pour (i, j) et réorganiser les appels dans une courbe de remplissage d'espace sur (i, j) à réduire les échecs de cache.

Pas tout à fait "judas" mais obtenir un comportement inconscient du cache pour "gratuit" est bien.

Chad Brewbaker
la source