Kontrollivuograafi
- engl. control flow graph
- suunnattu graafi, jossa
- solmuja ovat peruslohkot tai yksittäiset käskyt ja
- kaaret edustavat mahdollisia suorituspolkuja peruslohkosta tai käskystä toiseen
Terminologiaa
- Solmulla on
- lähteviä kaaria (out-edges),
- tulevia kaaria (in-edges),
- seuraajasolmuja (successor nodes) ja
- edeltäjäsolmuja (predecessor nodes).
- Solmun \(n\)
- seuraajasolmujen joukko on \(\mathrm{succ}(n)\) ja
- edeltäjäsolmujen joukko on \(\mathrm{pred}(n)\).
Eloisuusanalyysi
- engl. liveness analysis
- yksi tietovuoanalyysin (engl. data flow analysis) ilmentymä
- Muuttujalla tarkoitetaan tässä aliohjelman parametreja, muita paikallisia muuttujia sekä kääntäjän luomia väliaikaisia paikallisia muuttujia –
- ei siis globaaleja muuttujia.
- Tarkastellaan kontrollivuograafia, jossa solmut ovat yksittäisiä käskyjä.
- mahdollista toki käyttää myös peruslohkoja
- peruslohkograafilla analyysi olisi nopeampaa mutta hieman sotkuisempaa
Muuttujan eloisuus
- Solmu käyttää (use) muuttujaa, jos sen sisältämä käsky lukee muuttujan arvon.
- Solmu määrittelee (def) muuttujan, jos sen sisältämä käsky kirjoittaa muuttujaan arvon.
- Muuttuja on elossa (engl. live) tietyssä kontrollivuograafin kaaressa, jos on olemassa suunnattu polku ko. kaaresta
- solmuun, joka käyttää kyseistä muuttujaa
- niin, etttä polulla ei ole kyseistä muuttujaa määrittelevää solmua.
- Muuttuja tulee elossa (engl. is live-in) solmuun, jos se on elossa jossain siihen tulevassa kaaressa.
- Muuttuja lähtee elossa (engl. is live-out) solmusta, jos se on elossa jossain siitä lähtevästä kaaresta.
Merkintöjä
- \(\mathrm{use}(n)\) on solmun \(n\) käyttämien muuttujien joukko.
- \(\mathrm{def}(n)\) on solmun \(n\) määrittelemien muuttujien joukko.
- \(\mathrm{in}(n)\) on solmuun \(n\) elossa tulevien muuttujien joukko.
- \(\mathrm{out}(n)\) on solmusta \(n\) elossa lähtevien muuttujien joukko.
Eloisuuden tietovuoyhtälöt
Kaikilla solmuilla \(n\) pätee
\[ \begin{aligned} \mathrm{in}(n) &= \mathrm{use}(n) \cup (\mathrm{out}(n) − \mathrm{def}(n)) \\ \mathrm{out}(n) &= \bigcup_{n' \in \mathrm{succ}(n)} \mathrm{in}(n') \end{aligned} \]
Knasterin ja Tarskin lauseen mukaan näillä joukkoyhtälöillä on
- vähintään yksi ratkaisu sekä
- yksikäsitteiset pienin ja suurin ratkaisu.
Ks. Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5:2: 285-–309, 1955. Project Euclid
Kiintopisteiteraatio
Yleinen algoritmi tällaisten joukkoyhtälöiden pienimmän ratkaisun etsimiseen on kiintopisteiteraatio:
- alustetaan yhtälöiden vasemmat puolet tyhjiksi
- tulkitaan joukkoyhtälöt sijoituslauseiksi ja toistetaan kunnes joukot eivät enää muutu
Tehokkuus riippuu kovasti siitä, missä järjestyksessä solmuja käydään läpi. Tässä tapauksessa tehokkainta on edetä ohjelman lopusta alkua kohti.
Kysymys
Mistä on kyse, jos muuttuja tulee elossa aliohjelman ensimmäiseen käskyyn?
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.
Turhien kopiointien poisto
Yhdistä (coalesce) Yksinkertaistusaskeleen jälkeen etsi jokin kopiointikäsky \(a := b\) ja yhdistä solmut \(a\) ja \(b\), jos se on sallittua. Poista tämän jälkeen ohjelmasta kyseinen kopiointikäsky.
- Solmujen yhdistäminen on kiellettyä, jos ne ovat naapureita. Muutoin sovelletaan jompaa kumpaa seuraavista:
Kaksi solmua saadaan yhdistää, jos yhdistetyllä solmulla on vähemmän kuin \(k\) sellaisia naapuria, jolla on vähintään \(k\) naapuria, missä \(k\) on koneen rekisterien määrä. (Briggsin kriteeri)
Solmut \(a\) ja \(b\) saadaan yhdistää, jos jokaiselle \(a\):n naapurille \(t\) pätee, että \(t\) ja \(b\) ovat naapureita tai \(t\):llä on vähintään \(k\) naapuria. (Georgen kriteeri)
Jäädytä (freeze) Jos yksinkertaistus ja yhdistäminen ei kumpikaan onnistu, valitse jokin sellainen solmu, jolla on vähän naapureita, ja joka on osallisena kopiointikäskyssä. Merkitse ko. kopiointikäsky ei-kopiointikäskyksi.
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
Viimeinen luento oli tässä
- Mahdollisesti lisäluentoja tarpeen ja kiinnostuksen mukaan
- Ei lasketa tentin koealueeseen
These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.