TIES448 luento 13

Käskyjen valinnan ongelmanasettelu

  • Tehtävänä löytää kohdekoodi, joka toteuttaa välikoodin ilmaiseman ohjelman.
  • Kohdekielen ominaisuudet vaikuttavat merkittävästi ongelman hankaluuteen.
  • Päätettävä:
    • Kuinka huonoa koodia siedetään?
    • Mikä on suoritusajan ja kohdeohjelman koon suhteellinen tärkeys?

Triviaali tapa on huono

Yksi tapa on kääntää jokainen välikielen käsky yksi kerrallaan:

# a, b, c, d, e globaaleja muuttujia
# a := b + c
MOV RAX, b
MOV RBX, c
ADD RAX, RBX
MOV a, RAX
# d := a + e
MOV RAX, a # !
MOV RBX, e
ADD RAX, RBX
MOV d, RAX

Tämä tuottaa ylimääräistä työtä (edellä huutomerkillä merkitty käsky).

Mitä käskyä käyttäisi?

  • Ei ole lainkaan sama – kohdekoodin laadun kannalta mitä käskyä milloinkin käytetään.
    • i := i + 1
      • ADD iREG, 1
      • INC iREG
  • Objektiivisia mittareita
    • generoidun koodin pituus
    • generoidun koodin suoritusaikamittarit
  • Koodin pituus AMD64:ssä
    • ADD RAX, 1: viisi tavua
    • INC RAX: kaksi tavua
  • Generoidun koodin suoritusaika AMD 15h:ssa:
    • ADD RAX, 1: FastPath Single, latenssi 1
    • INC RAX: FastPath Single, latenssi 1
  • Lisäksi INC ei koske CF:ään – mahdollinen etu tietoriippuvuuksien kautta.

Mitä käskyä käyttäisi?

x := x + y missä x on rekisterissä RBX ja y muistissa:

MOV RCX, y    # FastPath Single 4
ADD RBX, RCX  # FastPath Single 1

vai

ADD RBX, y    # FastPath Single 5

Jälkimmäinen on yleensä parempi valinta. Vähemmän rekisteripainetta ja vähemmän käskyjä dekoodattavaksi.

Mitä käskyä käyttäisi?

x := x * 8 missä (unsigned) x on rekisterissä RAX

MOV RDX, 8    # ?
MUL RDX       # FastPath Single 6 (repeat after 4 cycles)

vai

SHL RAX, 3    # FastPath Single 1

Kohdekoodin generoinnista

  • Kaksi keskeistä ongelmaa:
    • käskyjen valinta (engl. instruction selection)
    • rekisterien valinta (engl. register allocation)
  • Voidaan tehdä kolmessa eri järjestyksessä
    • käskyt ennen rekistereitä
      • Rekisterien valinta pystyy ottamaan huomioon käskyjen erityispiirteet.
      • Joudutaan luomaan uusi väliesitys, jossa käskyjen operandit eivät ole vielä kiinnitetty.
    • rekisterit ennen käskyjä
      • Käskyjen valinta voi tuottaa suoraan konekoodia (tai assemblyä)
      • ei tarvetta uudelle väliesitykselle.
      • Rekisterien valinta tapahtuu sokeasti, jolloin kohdekoodiin voidaan joutua tekemään turhia kiertotemppuja.
    • lomittain
      • Koodaaminen on suhteellisen helppoa.
      • Rekisterien valinta perustuu liian vähään tietoon ja tuottaa huonon tuloksen.

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
  • 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)\).

Yksinkertainen menetelmä (lokaali)

  • Generoidaan koodi käymällä välikoodi kertaalleen läpi.
  • Rekisterin valinta tehdään samalla.
  • Tuloksena lausekkeelle kohtuullinen koodi, muuten aika huono.

Triviaali rekisterivalinta

  • Pidetään kirjaa, mikä operandi on missäkin rekisterissä, ja mitkä rekisterit ovat vapaina.
  • Kun tarvitaan rekisteri, katsotaan, onko yhtään vapaana. Jos on, varataan se tähän käyttöön. Jos ei:
    • Valitaan jokin varattu rekisteri (esim. se, jota on käytetty kauimman aikaa sitten).
    • Tallennetaan sen arvo pinossa sille varattuun tilaan.
    • Varataan ko. rekisteri tähän uuteen käyttöön.
    • Ladataan tarvittaessa muistista valittuun rekisterin operandin arvo.
  • Tehdään peruslohko kerrallaan
    • Peruslohkon alussa kaikki rekisterit vapaina
    • Peruslohkon lopuksi kopioidaan tarvittaessa rekisterien sisältö muistiin

Koodigenerointi

  • Kullekin kolmiosoitekoodin käskylle a := OP b c tee seuraavaa:
    • Valitse tarvittaessa rekisterit a:lle, b:lle ja c:lle.
    • Lataa b ja c tarvittaessa muistista.
    • Generoi OP:ta vastaavat käskyt.
  • Algoritmi olettaa, että OP:n käskyt eivät tuhoa minkään rekisterin arvoa. Jos oletus ei päde, algoritmi vaatii pientä säätöä.

Kohti parempaa rekisterien valintaa

  • Luentojen esitys globaalista rekisterien valinnasta perustuu pääosin Appelin lukuihin 10 ja 11.

Käskyt ennen rekistereitä: helppo väliesitys

  • Esitetään kukin käsky oliona, jossa on
    • käskyn mahdollinen kohdenimi (hyppyjä varten)
    • käskyn merkkijonomalline, jossa on ”aukot” operandeille
    • käskyn operandit pääosin viittauksina välikoodin operandiolioihin
      • kustakin tieto, luetaanko tai kirjoiteaanko siihen
    • luettelo operandeista, joita käytetään implisiittisesti
    • tieto, kopioiko käsky dataa operandista operandiin muuttamtta sitä
  • Jokaiselle fyysiselle rekisterille oma väliaikaismuuttujansa
    • kopiointi tällaiseen ilmaisee pakon käyttää kyseistä rekisteriä
  • Aliohjelman tai kunkin peruslohkon käskyt kootaan listaksi

Käskyjen ja rekisterien valinnan työnjako

  • Käskyjen valinta
    • Generoi varsinaiseen toimintaan liittyvät käskyt.
    • Generoi siirrot nimettyyn rekisteriin tai nimetystä rekisteristä, kun tämä on välttämätöntä.
  • Rekisterien valinta
    • Päättää, mitkä operandit ovat muistissa ja mitkä rekistereissä.
    • Päättää rekisterien multipleksauksesta.
    • Generoi tiedon siirtoon (muistin ja rekisterien välillä) liittyvät käskyt.

Käskyjen valinta tiilisäännöillä

  • Käydään aliohjelman välikoodi läpi lopusta alkuun.
  • Jos käsky on jo käsitelty, hypätään sen yli.
  • Etsitään tiilisäännöstöstä käsiteltävään käskyyn sopiva sääntö ja liitetään ko. käskyyn säännöstön ilmaisema kohdekielinen käskyjono.
    • Jos useampia sopii, valitaan se, joka merkitsee useamman käskyn käsitellyksi (maximal munch)
    • Merkitään kaikki tiilisääntöön osallistuneet käskyt käsitellyiksi.

Tiilisäännöt

  • Tiilisääntö koostuu puuhahmosta ja kohdekoodifragmentista.
  • Puuhahmo on välikielen käskyistä muodostettu puu, jossa käskyn lapsena voi olla käskyn lisäksi myös metamuuttuja.
  • Puuhahmo sovitetaan kolmiosoitekäskyyn seuraavasti:
    • puuhahmon juuren tulee vastata tarkasteltavaa käskyä
    • puuhahmon alipuihin sovitetaan käskyn vastaavan operandin tuottavaa käskyä (jos tämä on selvitettävissä yksiselitteisesti)
      • (helppoa kolmikkoesityksessä, hankalampaa nelikkoesityksessä)
    • metamuuttuja sopii mihin vain operandiin
  • Metamuuttujaan voidaan viitata fragmentista; tällöin fragmenttiin laitetaan ko. metamuuttujan kohdalla oleva operandi.

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.

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.