Kääntäjätekniikka

Luento 10 (28.4.2016)

Kääntäjän rakenne

Peruslohkot

• Peruslohkot (engl. basic block) voidaan etsiä niin välikielisestä kuin kohdekielisestä esityksestä
• Peruslohko on maksimaalinen ohjelman osa, jolle pätee seuraavaa:
  • Siihen kuuluvat käskyt esiintyvät ohjelmassa peräkkäin.
  • Siihen ei sisälly yhtään hyppykäskyä, paitsi mahdollisesti viimeisenä käskynä.
  • Mistään ei hypätä sen keskelle.
• Määritelmästä seuraa mm. seuraavaa:
  • Peruslohko vaihtuu aina hyppykäskyn jälkeen.
  • Hyppykäskyn kohde aloittaa aina peruslohkon.
  • Jokainen käsky kuuluu täsmälleen yhteen peruslohkoon.

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 RDX, 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.

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öä.

Parempi menetelmä (globaali)

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 viittauksina välikoodin operandiolioihin
  • tieto, onko käsky kopiointi rekisteristä rekisteriin
• Jokaiselle fyysiselle rekisterille oma väliaikaismuuttujansa
  • kopiointi tällaiseen ilmaisee pakon käyttää kyseistä rekisteriä
• Aliohjelman 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.