TIES448 Luento 8

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:
  • pinokielet (kuten WebAssembly tai Java bytecode)

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 - 48
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ä.
• Kannattaa tehdä yksinkertainen (tarkastamaton) tyypitys, esim:
  • void (0 bittiä)
  • int (konesana, ei osoitin)
  • tuple<T1,...,Tn> (monikko: kiinteä määrä kiinteätyyppisiä alkioita)
  • ptr (osoitin dataan, osoittimen takana olevan datan tyyppiä ei kerrota)

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

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.

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.
• Vaihtoehtoisesti kaikki hypyt tapahtuvat symbolisen nimen kautta
  • Hypyt eteenpäin ja taaksepäin käyttäytyvät samalla tavalla.