Kääntäjätekniikka

Luento 17 (16.5.2017)

Korjaus

Käskyjen valinnan tuottamassa väliesityksessä käsky merkitään kopiointikäskyksi jos se siirtää dataa operandista operandiin muuttamatta sitä

Häirintägraafi

  • engl. interference graph
  • suuntaamaton graafi
  • Kukin paikallinen muuttuja, parametri ja kääntäjän generoima väliaikaismuuttuja on yksi solmu.
  • Kahden solmun välillä on kaari, jos niiden esittämiä muuttujia ei voi laittaa samaan rekisteriin.
    • tyypillisesti koska ne ovat elossa samaan aikaan

Häirintägraafin konstruointi

Jokaiselle aliohjelman käskylle \(n\):

  • Jos se on kopiointikäsky a := c, lisää kaari \(\{a, b\}\) jokaiselle \(b \in \mathrm{out}(n) \setminus \{c\}\).
  • Muutoin lisää kaari \(\{a, b\}\) jokaiselle \(a \in \mathrm{defn}(n)\) ja \(b \in \mathrm{out}(n)\).

Rekisterien valinta (häirintä)graafia värittämällä

  • Olkoon kohdekielessä \(k\) yleiskäyttöistä rekisteriä.
  • Jos häirintägraafi voidaan värittää \(k\):lla värillä siten, että solmuilla, joita yhdistää kaari, on eri väri, niin
    • kukin väri voidaan tulkita rekisteriksi, ja sijoittaa samanväriset muuttujat samaan rekisteriin!
  • Valitettavasti graafinväritys (ja siten globaali rekisteriallokaatio) on NP-täydellinen ongelma.
  • Seuraavassa kuitenkin hyväksi osoittautunut lähes lineaarinen algoritmi.

Vaiheet

Rakenna Rakenna aliohjelmaa kuvaava häirintägraafi. Tässä tarvitaan eloisuusanalyysiä.

Yksinkertaista (simplify) Valitse jokin solmu, jolla on vähemmän kaaria kuin koneessa on rekistereitä. Poista kyseinen solmu graafista, ja lisää se pinoon.

Läikytä (spill) Jos kaikilla solmuilla on vähintään niin monta kaarta kuin koneessa on rekistereitä, yksinkertaistus ei onnistu. Tällöin poista jokin sellainen solmu graafista, jonka pitäminen muistissa on vähiten huono idea. Lisää se pinoon.

Valitse (select) Jos graafi on tyhjä, palauta pinossa olevat solmut takaisin graafiin värittäen kukin solmu vuorollaan. Tämä onnistuu varmasti kaikille yksinkertaistetuille solmuille. Jos jotakin läikytettyä solmua ei saa väritettyä, jätä se värittämättä ja jatka pinojärjestyksessä.

Yritä uudelleen Jos solmuja jäi värittämättä, muokkaa ohjelmaa siten, että kyseiset solmut säilytetään muistissa ja ladataan rekistereihin vain silloin kun sitä tarvitaan. Aja sitten koko algoritmi alusta uudestaan.

Esiväritetyt solmut

  • Solmut, jotka edustavat nimettyjä rekistereitä, ovat esiväritettyjä (engl. precolored).
    • Yksinkertaistusaskel ei saa koskaan valita esiväritettyä solmua.
    • Esiväritettyä solmua ei saa koskaan läikyttää.
  • Valinta-askel aloitetaan, kun graafissa on vain esiväritetyt solmut

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.