Kääntäjätekniikka

Luento 11 (25.4.2017)

Kääntäjän rakenne

# compilerstructure
test src Lähdeohjelma toks Sanasjono src->toks selaaja ast Rakennepuu toks->ast jäsentäjä ast->ast tarkastaja, sokerinpilkkoja il Välikoodi ast->il välikoodin generoija il->il optimoija asm Kohdekoodi il->asm kohdekoodin generoija asm->asm optimoija

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 - 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

# OP result arg1 arg2
0 := i 0
1 GOTO IF ≥ 8 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

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

rivi OP arg1 arg2
(0) := i 0
(1) ≥ i n
(2) GOTO IF ≥ (11) (1)
(3) :=[] a i
(4) - (3) 48
(5) ∗ 10 rv
(6) + (4) (5)
(7) := rv (6)
(8) + i 1
(9) := i (8)
(10) GOTO (1)

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

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.