Kääntäjätekniikka

Luento 8 (21.4.2016)

Kääntäjän rakenne

Välikoodin generointi

• tavoitteena muuttaa ohjelma muotoon, joka muistuttaa lopullista suorituskelpoista ohjelmaa
• muutamia yksinkertaistuksia välikielen generoinnin ja käsittelyn helpottamiseksi
• mahdollista kirjoittaa välikielelle tulkki ("virtuaalikone") esim. testausta varten
• olennainen käsitteellinen jako:
  • "lokaali" (hyppyjen välit)
  • "globaali" eli aliohjelman sisäinen
  • "interproseduraalinen" eli aliohjelmien välinen

Välikielet

• klassikko: kolmiosoitekoodi (engl. three-address code)
  • nelikot (engl. quadruples)
  • kolmikot (engl. triples)
  • välipuut ja -graafit (engl. intermediate trees / graphs)
• moderni:
  • SSA (static single-assignment form)
  • jatkeenvientikielet (engl. continuation-passing languages)

Erikoisempia vaihtoehtoja

Joissakin kääntäjissä on useita välikieliä. Esim GHC:

• Core
• STG
• Cmm
• LLVM IR (valinnainen)

Kolmiosoitekoodi

Määritelmä
Kolmiosoitekoodi on käskyjen jono. Käskyt ovat muotoa

x := OP y z

missä x, y ja z ovat operandeja ja OP on operaattori. Jotkin operandeista saattavat jäädä käyttämättä joillakin operaattoreilla.

• Operaattorien joukko on välikieleen pultattu kiinni.
• Operandeja ovat
  • vakiot,
  • ohjelmoijan muuttujat,
  • kääntäjän generoimat välitulokset ja
  • viittaukset käskyjonossa oleviin käskyihin

Operaattorityypit

• binääriset laskentaoperaattorit, esim. x := y + z
• unaariset laskentaoperaattorit, esim. x := −y
• kopiointioperaattori x := y
• ehdoton hyppy GOTO x
• ehdolliset hypyt, esim. GOTO x IF y ≥ z
• aliohjelmakutsuun liittyvät käskyt PARAM y, x := CALL y z
• indeksoitu luku, x := y[z]
• indeksoitu kirjoitus x[y] := z
• osoitteen kautta luku x := ∗y
• osoitteen ottaminen x := &y
• osoitteen kautta kirjoitus ∗x := y

Esimerkki

for (int i = 0; i < n; i++) {
rv = 10*rv + a[i] - 48;
}

muuttuu muotoon

0: i := 0
1: GOTO 8 IF i >= n
2: t1 := a[i]
3: t2 := t1 - 32
4: t3 := 10 * rv
5: rv := t2 + t3
6: i := i + 1
7: GOTO 1

Esitystapa: nelikot

Määritelmä
Nelikko on kolmiosoitekoodin käskyä esittävä tietue, jossa on kentät operaattorille ja kullekin kolmelle operandille.

• Engl. quadruple tai quad
• Lähes joka käskylle joutuu luomaan uuden, väliaikaisen muuttujan.
• Käskyjä voi siirtää paikasta toiseen varsin vaivattomasti.

Esimerkki

Operandien esittäminen

• Operandi esitetään viittauksena sitä kuvaavaan tietueeseen.
  • suora osoitin (esim. C:ssä tai Javassa) tai
  • symboli, joka viittaa symbolitauluun.
• Operandin tietueessa esitetään kaikki takapään tarvitsema tieto siitä.

Kolmikot

Määritelmä
Kolmikko on kolmiosoitekoodin käskyä esittävä tietue, jossa on kentät operaattorille ja kahdelle operandille. Viittaus käskyn tulokseen tehdään viittaamalla itse käskyyn.

• engl. triple
• Erillisiä väliaikaismuuttujia tarvitaan harvoin.
• Käskyn siirtäminen vaatii tarkkuutta, jotta viittaukset sen tulokseen eivät mene rikki.
  • helppo tapa korjata: käskyjonossa on vain viittaus kolmikkoon, ei itse kolmikkoa
  • näin esim. jos kolmikot ovat Java-olioita ja ne tallennetaan taulukkoon

Esimerkki

Puutulkinta

• Kolmiosoitekoodin kolmikkoesitys voidaan tulkita metsäksi.
• Onnistuu myös – hieman hankalammin – nelikkoesityksessä.
• Kukin käsky on jonkin puun solmu.
• Solmun lapsisolmut ovt ne käskyt, joihin solmukäsky viittaa datakäyttöä varten
  • poislukien siis hyppykäskyjen kohdeviittaukset
• Lausekkeet toteuttava kolmiosoitekoodi tulkittuna puuksi on olennaisesti sen rakennepuu.
  • Sama ei päde lauseille ja määrittelyille

Suunnatut syklittömät graafit (DAG)

• Kolmikkoesitystä generoitaessa voidaan pyrkiä poistamaan toistoa.
• Ideana laittaa generoidut käskykolmikot myös hajautustauluun, josta ne voidaan hakea operaattorin ja kahden operandin avulla.
• Kun meinataan generoida jokin käsky, katsotaan ensin, löytyykö se hajautustaulusta.
• Jos löytyy, käytetään löytynyttä käskyä eikä generoida uutta.
• Tuloksena olevan kolmikkoesityksen puutulkinta ei ole enää puu vaan DAG.
• Sivuvaikutukset monimutkaistavat:
  • Jos generoidaan sivuvaikuttava käsky, niin hajautustaulusta pitää poistaa ne käskyt, joiden laskemaan arvoon ko. sivuvaikutus saattaa vaikuttaa.

SSA

• engl. static single-assignment
• kolmiosoitekoodin muunnelma, jossa muuttujaan ei voi sijoittaa - sen voi vain alustaa
• lähdekielen muuttujasta x useita versioita x1, x2, . . .; joka lähdekielen sijoitus luo uuden version
• ongelma: mitä tehdään, jos sama muuttuja alustetaan eri tavalla eri suorituspoluilla?
• ratkaisu: ns Φ-funktio
  • käsky x7 := Φ(x6, x5) alustaa x7:n joko x6:llä tai x5:llä
  • Φ(x6, x5) on sallittu vain, jos molemmat eivät koskaan tule alustetuksi samalla ohjelman suorituskerralla
• yksinkertaistaa opimointianalyysien ja -muunnoksien oikeellisuustarkastelua
• SSA:sta lisää esim. Appel luku 19
• LLVM IR

CPS

• engl. continuation-passing style
• esitystapa, jossa kaikki funktiokutsut ovat häntäkutsuja
• kaikki hypyt, silmukat ym. esitetään funktiokutsuina
• suosittu innokkaiden funktiokielten kääntäjissä
• ekvivalentti SSA:n kanssa

Kolmiosoitekoodin generoinnista

• Kolmiosoitekoodia generoidaan kullekin aliohjelmalle erikseen.
• Kunkin aliohjelman kolmiosoitekoodi generoidaan ko. aliohjelman omaan käskyjonoon.
• Ideana on käydä aliohjelman rakennepuu jälkijärjestyksessä läpi.
• Tässäkin tarvitaan symbolitaulua, joka yhdistää muuttujat niitä esittäviin operandeihin.

Lausekkeet

• Lauseke laskee arvon, joka pitää tallettaa johonkin.
• Kaksi vaihtoehtoa:
  • Lausekkeen generoijalle kerrotaan, mihin lausekkeen tulos pitää tallettaa.
  • Lausekkeen generoija tallettaa tuloksen johonkin ja palauttaa tiedon tästä kutsujalleen.
    • yleensä uusi väliaikaismuuttuja

Totuusarvolausekkeet

• Totuusarvolausekkeilla on kaksi erilaista käyttötarkoitusta:
  • if-, while- ym. lauseiden testinä, jolloin lausekkeen arvo määrittää, minne hypätään;
  • totuusarvon laskemiseen esim. argumentiksi antamista tai paluuarvona palauttamista varten.
• Totuusarvolausekkeet voidaan kääntää kahdella tavalla:
  • generoidaan suoraan hypyt
  • lasketaan totuusarvo niin kuin mikä tahansa muu arvo

Hypyt

• Hypyt taaksepäin ovat helppoja: hyppykäskyyn voidaan saman tien kirjoittaa kohdekäskyn sijainti käskytaulukossa.
• Entäpä hypyt eteenpäin? Tarvitaan backpatching-tekniikkaa:
  • Hypyn kohdetta ilmaisemaan luodaan kohdeolio
  • Kohdeoliota voidaan käyttää hypyn kohteena. Jos hyppy oli taaksepäin, kohdeolio tietää, minne hypätään, ja kaikki on helppoa.
  • Jos hyppy on eteenpäin, kirjataan hyppykäsky ylös ja laitetaan sen kohteeksi jotain hyödytöntä.
  • Kun kohdeoliolle annetaan sijainti, käydään korjaamassa muistiin kirjattujen hyppykäskyjen kohteet.

Aliohjelmakutsut

• Välikoodin generoijan ei tarvitse tietää aliohjelmasta sen parametrien määrää ym. Ne oletetaan olevan ok tyyppitarkastuksen pohjalta.
• Argumentit pitää laskea yksi kerrallaan. Laskujärjestys riippuu kielestä: vasemmalta oikealle ja oikealta vasemmalle ovat tavallisimmat.
• Välikielessä ei kannata esittää kutsua monimutkaisesti. Esim. kolmiosoitekoodissa riittää hyvin jokin seuraavanlainen sekvenssi kutsulle f(x, y):

yp := ARG y
xp := ARG x, yp
res := CALL f, xp

• Tällöin kutsu ja parametrit muodostavat puun, jossa kutsu on ensimmäisenä ja parametrit lineaarisesti järjestyksessä oikeassa alipuussa.