Kääntäjätekniikka

Luento 14 (4.5.2017)

Kääntäjän rakenne

# compilerstructure

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.

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