Inscrivez-allocation et les renversements, la manière facile?

https://stackoverflow.com/questions/1960888

21-09-2019
|

Question

Je suis à la recherche d'un moyen d'affecter les variables locales aux registres. Je connais deux ou trois méthodes sérieuses pour le faire (à savoir celles qui sont mentionnées sur Wikipedia ) , mais je suis coincé sur la façon dont « un déversement de » est accompli. En outre, la littérature est assez intimidant. J'espère qu'il ya quelque chose de simple qui satisfera mes priorités:

Correctness - un algorithme qui va générer un code correct quel que soit le nombre de variables locales il y a
Simplicité -. Quelque chose que je peux comprendre sans avoir à lire trop la littérature
Efficacité - il doit être mieux que la méthode actuelle, qui est:

Traduire une x = y # z de fonctionnement à:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Comme je cible Intel 386, certaines contraintes sont pertinentes:

Les opérations binaires prennent deux arguments, dont l'un est une source et la destination. opérations unaires prennent un seul argument.
Les opérations ne peuvent accéder à un emplacement de mémoire; opérations binaires doivent donc au moins un argument dans un registre.
Il y a un maximum de six registres disponibles: %eax %ebx %ecx %edx %esi %edi. (%ebp pourrait également être inclus en dernier recours.)
Il y a des cas particuliers tels que pour la division entière et le retour des registres, mais je peux les ignorer pour l'instant.

Il y a trois étapes le compilateur passe à travers au moment:

i386ification:. Toutes les opérations sont converties en une forme a = a # b (ou a = #a pour les opérations unaires)
Analyse Vivacité:. Les ensembles de variables vivantes avant et après chaque opération sont déterminées
l'allocation des registres:. Un graphe d'interférence est construit et coloré

Et puis le compilateur jette ses crayons dans l'air et ne sait pas quoi faire.

Exemple

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Voici le graphe d'interférence assez jolie pour la fonction, et la CFG des informations liveness. L'image CFG nécessite un certain défilement vertical, malheureusement.

Sept couleurs ont été utilisées. Je voudrais renverser l'un d'eux (ou l'ensemble des variables attribuées cette couleur). La méthode de choix qui est pas trop important. Ce qui est délicat est de savoir comment traiter les variables renversées.

Disons que je répands « rose », qui est l'ensemble des variables t, $t4, $t7. Cela signifie que ces opérations se rapportant à l'une de ces variables y accéder à partir de sa position sur le cadre de la pile, plutôt que par un registre. Cela devrait fonctionner pour cet exemple.

Mais si le programme était:

...
a = a + b
...

et les deux a et b ont dû être renversé? Je ne peux pas émettre un addl b, a d'instruction avec deux adresses mémoire. Je besoin d'un autre registre de rechange pour maintenir temporairement l'un des opérandes, et cela signifie répandre une autre couleur. Ceci suggère une méthode générale de:

Si toutes les variables peuvent être colorées avec des couleurs r, super!
Sinon, renverser certaines couleurs et leurs variables associées.
Si une opération existe que les accès deux variables renversées, renverser une autre couleur et utiliser le registre de rechange pour le stockage temporaire pour toutes ces opérations.

À ce stade, je pense que beaucoup plus de choses est renversé que nécessaire, et je me demande s'il y a un moyen de renverser les choses plus intelligemment, comme déversant une partie de la vie d'une variable plutôt than la variable entière lui-même. Techniques sont-il des simples (ish) que je pourrais utiliser ici? Encore une fois, je ne suis pas viser particulièrement élevé - certainement pas assez élevé pour exiger quoi que ce soit la lecture trop profond. ; -)

Problèmes spécifiques

Le problème principal est spécifique: lorsqu'une variable est renversé, comment cela affecte les instructions générées? Faites toutes les instructions en utilisant ce besoin variable pour accéder directement à la mémoire (de sa position de pile)? Comment cela fonctionnera si une opération utilise deux variables renversé? (L'architecture ne permet pas d'instructions pour accéder à deux emplacements de mémoire distincts.)

Des problèmes secondaires sont:

Comment puis-je déterminer où insérer des instructions de chargement / stockage, pour l'exactitude (et moins important, l'efficacité)?
Puis-je renverser une variable pour seulement une partie de sa vie quand il n'est pas utilisé immédiatement, et unspill plus tard? Alors que toutes les instructions agissent sur les registres unspilled. Une variable peut vivre dans des registres différents à des moments différents.
Puis-je être un peu plus efficace avec des cas particuliers. Par exemple, %eax est utilisé pour la valeur de retour, il serait bien à retourner la variable qui est arrivé à attribuer à ce registre au moment où le retour a été rencontré. De même, certains registres sont « callee-save », donc si moins de variables se trouvaient être en direct au moment d'un appel de fonction, les ayant attribuées aux non-callee-save registres signifierait que je peux éviter de stocker ces registres.
formeraient SSA aide beaucoup (le cas échéant)? Être en mesure d'éliminer et d'évaluer les sous-expressions communes constantes pourrait réduire (?) La pression s'inscrire, mais sinon cela aurait-il un effet?

Les aspects que je ne suis pas préoccupé (en ce moment) sont les suivants:

l'allocation et l'optimisation Stack: il est mis en œuvre déjà naïvement, et peuvent être optimisés en utilisant le graphe d'interférence le cas échéant
Efficacité de la compilation, aussi longtemps qu'elle se termine. (NP-complet ne signifie pas doit être évité un algorithme donné.)

Mise à jour

Désolé pour le temps d'arrêt - j'ai réfléchi sur les réponses données et en essayant de trouver une approche facile à prendre pour commencer à mettre en œuvre certaines des idées. Pour être honnête, j'ai ... tergiverser: - \

J'ai trouvé la présentation très agréable (PPT, malheureusement):

http: //www.cs. princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

Ce qui répond à la question sur la façon de répondre à des besoins de fonctionnement spécifiques (comme en utilisant le même registre pour la source et la destination, ou avoir besoin d'un certain registre pour certaines opérations). Ce que je ne suis pas sûr de savoir si le cycle Vivacité-coloration-allocation se termine.

Je vais essayer de faire un travail réel et nous espérons bientôt fermer la question.

La solution

Je l'ai utilisé une approche gourmande dans un allocateur JVM une fois, ce qui a fonctionné assez bien. Fondamentalement commencer au sommet d'un bloc de base avec les valeurs stockées dans la pile. Ensuite, il suffit de numériser les instructions vers l'avant, le maintien d'une liste des registres qui contiennent une valeur, et si la valeur est sale (qui doit être écrit en arrière). Si une instruction utilise une valeur qui ne soit pas dans un registre (ou non dans le registre correct), délivre une charge (ou déplacer) pour le mettre dans un registre libre avant l'instruction. Si une instruction écrit une valeur, assurez-vous qu'il est dans un registre et le marquer sale après l'instruction.

Si vous avez besoin d'un registre, renversez un registre utilisé par désaffecter la valeur de celle-ci, et de l'écriture à la pile si elle est sale et vivre. A la fin du bloc de base, écrire de nouveau tous les registres sales et en direct.

Ce schéma montre clairement exactement où toutes les charges / magasins vont, les générer comme vous allez. Il est facilement adaptable aux instructions qui prennent une valeur en mémoire, ou qui peut prendre l'une des deux arguments en mémoire, mais pas les deux.

Si vous êtes OK d'avoir toutes les données sur la pile à chaque limite de bloc de base, ce système fonctionne assez bien. Il devrait donner des résultats similaires à balayage linéaire dans un bloc de base, comme il le fait essentiellement des choses très similaires.

Vous pouvez obtenir arbitrairement compliqué sur la façon de décider quelles valeurs et quels sont les registres renversez à allouer. Certains préanalyse peut être utile, par exemple par marquage de chaque valeur avec un spécifique registre, il doit être en un moment donné dans le bloc de base (par exemple, eax pour une valeur de retour, ou ecx pour une quantité de décalage), et en préférant ce registre lorsque la valeur est tout d'abord affecté (et d'éviter que le registre à d'autres allocations). Mais il est facile de séparer l'exactitude de l'algorithme des heuristiques d'amélioration.

Je l'ai utilisé ce allocateur dans un compilateur SSA, YMMV.

Autres conseils

Première: Il n'y a pas moyen intelligent de le faire. Le problème est NP-complet; -)

Comment se fait renverser:

Vous exécutez votre algorithme d'allocation de registre et obtenir une liste des variables que vous devez renverser. Maintenant, vous pouvez allouer un peu d'espace sur la pile au début de votre fonction. Lien chaque variable déversée aussi une place sur la pile. Si vous voulez être la mémoire intelligente coalesce avec des plages vivantes ne se chevauchent pas. Chaque fois que vous devez renverser un registre enregistrer dans la mémoire et le charger, quand il est à nouveau nécessaire.

Comment gérer EAX:

Marquer le registre comme rempli, mais ne stocke pas une variable dans ce (pré-allocation). Cela rendra le générateur de code clair que le registre. Pour être intelligent magasin la valeur dans un autre registre si cela est utile.

Simple et facile façons correctes pour manipuler spilling:

Il suffit de tout renverser. Cela suppose que la plage active est le programme complet de toutes les variables. Cela peut être augmentée en utilisant des trucs comme compter ou de l'utilisation LRU pour choisir les registres doivent être libérés.

La meilleure chose à faire est probablement allocation de registre de balayage linéaire . Il devrait être assez facile à mettre en œuvre, même lors de l'utilisation de pré-allocation. Je vous suggère de regarder dans le papier lié.

Réponses spécifiques

Qu'est-ce que correct signifie pour vous? algorithmes Même les allocations simples sont correctes si vous ne faites pas une erreur de programmation. Épreuvage correct (mathématique) est beaucoup plus difficile. Les deux charges et les magasins doivent être insérés avant que la valeur / registre est à nouveau nécessaire. Les deux doivent être insérés après la valeur est stockée / créée.
Oui. Si vous programmez cette façon. Si votre algorithme peut gérer une valeur dans plusieurs registres au cours de son livetime vous pouvez utiliser ces optimisations.
Il est à nouveau à vous de mettre en œuvre certaines améliorations. Une possibilité serait de eax bloc seulement quand il est nécessaire, non pas pour l'ensemble du programme.
Dans certaines conditions SSA ne l'aide. graphiques de Inference de code SSA sont toujours href="http://en.wikipedia.org/wiki/Chordal", ce qui signifie qu'il n'y a pas de cycle avec plus de 3 noeuds. Ceci est un cas particulier de coloration graphique, où une coloration minimale peut être trouvée dans le temps polynomiale. La conversion en Afrique subsaharienne ne signifie pas nécessairement plus ou moins de pression de registre. Tandis que la forme SSA a des variables généralement plus, ceux-ci ont tendance à avoir livetimes plus petits.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow