Kääntäjätekniikka

Luento 13 (17.5.2016)

Luennolla käsitelty esimerkkikoodi Yousourcessa

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.

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.