Cours

Description

Remerciements: une partie de ces notes est basée sur le cours de Didier RemyAllocation des registres par coloriage de grapheLes grandes lignes:• on construit à partir de l’assembleur abstrait le graphe de flot du programme• en analysant ce graphe, on calcule la durée de vie de chaque temporaire• on remarque que deux temporaires ayant durées de vie disjointes peuvent partagerun même registre, sinon, ils interfèrent• on construit le graphe d’interférence: les noeuds sont les temporaires, les arêtesrelient deux noeuds qui interfèrent• si on arrive à k colorier le graphe, on sait placer tous les temporaires danskregistres• sinon, on met en pile un temporaire (“spill”), et on recommence toute l’allocationColoriageback endcoeur z }| {z }| {Générat. Sélection Durée ColoriageLinéar. d’instruct. de vie et “spilling”AST −→ IR −→ AA −→ AA −→ AA| {z }Allocation deregistres• Assigner à chaque groupe de temporaires qui n’interfèrent pas un registre dif férent.• En cas d’échec, choisir un temporaire pour l’allouer en pile (spill), et recom mencerConstruction du graphe d’interférenceUne fois l’analyse de durée de vie des temporaires faite, nousExemple1?1 z←x+z.................I........?.........................2 t←z .. life(t)={2 3;3 4}............................................ life(z)={0 1;1 2;4 5;5 6;5 1}......? ........................................3 t←t∗t. life(x)={0 1;1 2;2 3;3 4;4 5;5 1}..............................?...................4 z←t. x z.. ...

Informations

• Publié par: Endri
• Nombre de lectures: 44
• Langue: Slovak

Extrait

Remerciements: une partie de ces notes est basée sur le cours de Didier Remy

Allocation des registres par coloriage de graphe Les grandes lignes: on construit à partir de l’assembleur abstrait legraphe de flotdu programme en analysant ce graphe, on calcule ladurée de viede chaque temporaire on remarque que deux temporaires ayant durées de viedisjointespeuventpartager un même registre, sinon, ilsinterfèrent on construit legraphe d’interférence: les noeuds sont les temporaires, les arêtes relient deux noeuds qui interfèrent si on arrive àkcolorier le graphe, on sait placer tous les temporaires dansk registres sinon, on met en pile un temporaire (“spill”), eton recommencetoute l’allocation

Coloriage

backend coeur z }| { z }| { Générat. SélectionDurée Coloriage Linéar. d’instruct.de vieet “spilling” AST→IR→AA→AA→AA | {z } Allocation de registres Assigner àchaque groupe de temporaires qui n’interfèrent pasun registre dif férent. En cas d’échec, choisir un temporaire pour l’allouer en pile (spill), et recom mencer

Construction dugraphe d’interférence Une fois l’analyse de durée de vie des temporaires faite, nous Exemple

1