Aalborg den 22.04.2003

Kompilerkonstruktion: Registerallokering

Efter "opvarmningsrunden" i forrige uge med liveness analysis er vi nu klar til at se på selve registerallokeringen. Denne allokering har stor indflydelse på hvor stærkt target programmet kører. Registerallokering er et såkaldt NP-komplet problem dvs. at man ikke kan finde den bedste løsningen uden at prøve alle kombinationerne. Da der typiske er er utroligt mange kombinationer kan man i en kompiler ikke sats på at finde den bedste løsningen, men må nøjes med en god løsning. Heldigvis er der flere anvendelig heuristiske algoritmer til registerallokering som giver gode løsninger. Med en heuristisk algoritme menes en algoritme, som bruger man et sæt "tommelfingerregler", hvorved man så erfaringsmæssigt eller matematisk ved at man får en god løsning, men altså ikke den bedste løsning.

Litteratur

Appel kapitel 11

Læsevejledning

I sektion 11.0 gives målene for registerallokering (1) få så mange midlertidig variable i et så lille sæt registre som muligt og (2) eliminere så mange MOVE operationer som muligt. Begge mål skal få target programmet til at kører stærkt, men må naturligvis ikke påvirke korrektheden af et program.

I sektion 11.1 præsenteres en algoritme for registerallokering hvor inputtet til algoritmen er en inference graph (dem så vi på i forrige uges materiale). Dette input bruges til at bygge en farvetgraf hvor hver farve indikerer en register. Som når man maler sin stue kan man i graf farvning også spilde hvilket betyder at man ikke har registre nok tilgængeligt og må derfor gemme ting i hukommelsen (main memory). Sektion 11.1 ser altså på det første mål fra sektion 11.0

I sektion 11.2 kigger så på det andet mål fra sektion 11.0. Første diskuteres to strategier for at eliminere MOVE operationer vha. coalescing. Dernæst kombineres coalescing med registerallokerings algoritmen fra sektion 11.1.

Sektion 11.3 tilføjer et væsentlig punkt til graf farvningen, nemlig at nogle knuder kan have farver givet på forhånd hvilket i praksis betyder at de værdierne knuderne repræsenterer skal være gemt i bestemte registre. Der gives et længere eksempel på side 229 til 231 brug tid på at forstå dette eksempel.

Der gives lav prioritet til sektion 11.4. Denne sektion indeholder data strukturer og algoritmer for hvorledes graffarvning kan implementeres. Hvis i skal bruge dette i jeres projekt kan i finde detaljerne her.

Sektion 11.5 ser på en simplere algoritme for registerallokering hvor inputtet ikke er en inference graph, men en træstruktur. Dette gør opgaven betydelig simplere og passer godt samme men Visitor design mønstret.

Opgaver

(A) Opgave 11.1

(B) Opgave 11.2a og 11.2.b

Venlig hilsen

Kristian Torp
torp (at) cs (dot) auc (dot) dk