Cours

pages

Slovak

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

Slovak

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Endri

Langue

Slovak

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 ﬂot 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.. ...

Voir

Publié par

Endri

Langue

Slovak

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 ﬂotdu 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

Voir