Kääntäjätekniikka

Tietueiden ja varianttien välikoodigeneraatio

Tässä kuvatut muutokset luentoesimerkkiin löytyvät Yousourcesta.

Välikielen tyypitys

Kohdekoodin generoijan tulee kyetä selvittämään jokaisesta väliaikaismuuttujasta ja jokaisesta paikallisesta muuttujasta seuraavat seikat:

  • kuinka monta rekisteriä (ja millaisia rekistereitä) tarvitaan muuttujan sisällön tallentamiseen rekisterissä
    • kokonaisluku tyypillisesti yksi kokonaislukurekisteri
    • kokonaislukupari kaksi rekisteriä
    • jne
  • mikä on muuttujan vaatima alignment, jos se tallennetaan muistiin
  • mikä on muuttujan vaatima tila, jos se tallennetaan muistiin

Yksi ratkaisu olisi kiinnittää nämä tiedot jo välikielen generoinnissa (ks. esim. AJK-2009), mutta tämä tekee välikielen turhan riippuvaiseksi kohdekielen yksityiskohdista.

Tällä kertaa toin välikieleen mukaan pienen tyypityksen (jota pääsääntöisesti ei tarkasteta). Tässä tapauksessa päädyin seuraaviin välikielen tyyppeihin:

  • ir.VoidType, jota käytetään ilmaisemaan dataa, jota ei tarvitse tallentaa mihinkään
  • ir.IntType, jota käytetään kaikkiin konesanan kokoisiin muuttujiin, jotka eivät sisällä osoittimia ja joita voidaan käsitellä kokonaislukurekistereissä
  • ir.TupleType, jota käytetään kuvaamaan muuttujaa, jossa on kiinteä määrä kenttiä, joiden välikielityyppi on kiinnitetty (lähinnä tietueet)
  • ir.ClosureType, jota käytetään kuvaamaan aliohjelman sulkeumaa
  • ir.TaggedPtrType, jota käytetään varianttien esityksessä ja joka on olennaisesti pari, joka sisältää
    • kokonaisluvun, jonka maksimikoko on tyypissä rajoitettu (tag), ja
    • dataosoitteen.

Huomaa, että osoitintyyppi ei kerro, minkälaiseen dataan se osoittaa. Sitä tietoa ei tarvita osoittimen itsensä koon ja alignmentin selvittämiseen.

Sivunmennen sanoen ir.TaggedPtrTypestä

Data, jonka välikielityyppi ir.TaggedPtrType, voidaan esittää kahden konesanan parina, jossa ensimmäinen on tag ja toinen dataosoitin. Yleensä kuitenkin tagin lukualue on erittäin rajoitettu (esim. vain 0..3), jolloin voidaan käyttää tiukempiakin esitysmuotoja.

Dataosoittimet ovat yleensä alignattuja. Tämä tarkoittaa, että osoitin on aina jaollinen jollakin tietyllä kakkosen potenssilla eli sen vähiten merkitsevät bitit ovat nollia. Esimerkiksi jos dataosoitin on alignattu 8 tavuun, osoittimessa on kolme alinta bittiä aina nollia. Jos nyt tag mahtuu noihin kolmeen bittiin, voidaan ne tallentaa noihin bitteihin.

Tagin esittäminen alignment-biteissä on erityisen tehokasta, jos tagin arvo tiedetään käännösaikana aina, kun osoitteen takana olevaa dataa tarvitaan, koska tag voidaan tällöin vähentää tagin sisältävästä osoitteesta osana displacementia. Esimerkiksi, jos rekisterissä RDX on TaggedPtrType-arvo, jonka tagi on esitetty alignment-biteissä ja tagin tiedetään olevan 3, niin osoitteen takana oleva 64-bittinen kokonaisluku voidaan laskea yhteen RAX-rekisterin sisällön kanssa seuraavalla AMD64-käskyllä (Intel syntax):

    ADD RAX, [RDX-3]

ir.TupleType- ja ir.TaggedPtrType-accessorit

Päädyin lisäämään välikieleen mm. seuraavat operandiluokat:

  • ir.TupleElementAccessor-oliota luodessa annetaan operandi, joka sisältää monikon, sekä järjestysluvun, jolla viitataan monikon kenttään; oliota voidaan käyttää operandina viittaamaan kyseisen monikon kyseiseen kenttään
  • ir.TagAccessor-oliota luodessa annetaan operandi, joka on välikielityypiltään ir.TaggedPtrType; oliota voidaan käyttää operandina viittaamaan kyseisen osoittimen tagiin
  • ir.PointerTargetAccessor-oliota luodessa annetaan operandi, joka on välikielityypiltään ir.TaggedPtrType sekä tagin arvo; oliota voidaan käyttää operandina viittaamaan kyseisen osoittimen osoittamaan kohdeolioon (tagia tarvitaan yllä mainitun displacement-tempun toteuttamiseen ja sen tulee olla sama kuin osoitteen tagi)

Sen paremmin ir.TupleElementAccessorin kuin ir.PointerTargetAccessorin luonnissa annettu operandi ei saa olla ir.PointerTargetAccessor. Ajatus tässä on, että ir.PointerTargetAccessor kääntyy konekielessä epäsuoraksi osoitukseksi, ja epäsuoria osoituksia ei voi missään konekielessä laittaa sisäkkäin samaan operandiin; jotta epäsuoran osoituksen tulosta voisi käyttää toisessa epäsuorassa osoituksessa, on tuo tulos ensin ladattava eri käskyllä rekisteriin.

Sen sijaan ir.TupleElementAccessor voi esiintyä ir.PointerTargetAccessorin sisällä ja sitä voi käyttää useita kertoja sisäkkäin. Tämä siksi, että ir.TupleElementAccessor kääntyy konekielessä displacementiksi, joka voidaan ottaa osaksi epäsuoraa osoitusta, ja displacementit voidaan laskea yhteen.

Tietueiden välikoodikäsittely

Tietueilla on vain yksi keskeinen operaatio: kentän valinta (tietue.kenttä). Kun tietueen kenttien järjestys tiedetään, samoin kuin kunkin kentän koko, tietueen alkuosoitteen muuttaminen kentän alkuosoitteeksi on konekielessä yksinkertainen osoitteen ja käännösaikaisen vakion yhteenlasku, joka yleensä voidaan tehdä osana epäsuoraa osoitusta. Esimerkiksi jos

  • muuttujassa x on tietue, jossa on kolme 8-tavuista kenttää
  • x:n viimeinen on int-tyyppiä ja nimeltään c
  • muuttuja y on tyypiltään int
  • muuttujan x alkuosoite on rekisterissä RCX ja muuttujan y alkuosoite on rekisterissä RDX,

on lause

y = y + x.c

käännettävissä AMD64-käskyksi

ADD RDX, [RCX + 16]

ja lause

x.c = x.c + y

on käännettävissä AMD64-käskyksi

ADD [RCX + 16], RDX

Huomaa, kuinka sama epäsuora osoitus toimii sijoituslauseen kummillakin puolilla. Siksi kentän valinta kannattaa välikielessä esittää operandina. Tätä varten lisäsin välikieleen operandityypin ir.TupleElementAccessor. Yllä olevan esimerkin tapauksessa x.c johtaisi operandiin ir.TupleElementAccessor(ir.IntType(), x_op, 2), missä x_op on symbolitaulusta kaivettu x:n operandiesitys ja 2 on kentän c järjestysluku tietuetyypissä. Koska x_op sisältää tiedon x:n kenttien välikielityypeistä ja järjestyksestä, kohdekoodin generoija kykenee tästä laskemaan tarvittavan displacementin.

Variantti

Esitystapa muistissa

Variantissa on aina täsmälleen yksi kenttä aktiivinen, ja variantin tulee tietää, mikä kentistä on aktiivinen. Siksi variantti on olennaisesti pari:

  • tag, joka kertoo, mikä kenttä on aktiivinen ja
  • data, joka sisältää aktiivisen kentän datan

Mutta asiaa mutkistaa se, että kentät voivat olla eri kokoisia. Varataanko siis variantissa tilaa aina isoimman kentän datalle? Näin toimii C:n unioni (joka tosin ei tarvitse tagia). Vaihtoehtoisesti data voidaan laatikoida (box): varianttiin itseensä ei laiteta dataa sellaisenaan vaan vain osoitin dataan.

Luennolla variantteja suuniteltaessa sovittiin jo, että variantti on laatikoitu. Tärkein syy tähän oli rekursiivisten tietorakenteiden tukeminen, sillä johonkin kohtaan se osoitin on sullottava, ja variantti on varsin luonnollinen paikka sille.

Jäljellä on enää kysymys siitä, pitäisikö tag tallentaa varianttiin vai osoittimen taakse? Jotenkin tuntuisi luonnolliselta laittaa tag datan yhteyteen osoittimen taakse, mutta tässä on huono puoli: useimmissa varianteissa on vain kourallinen kenttiä, ja kokonaisen konesanan varaaminen tagia varten tuhlaa muistia. Kun tag laitetaan varianttiin itseensä osoittimen yhteyteen, voidaan käyttää yllä kuvattua ir.TaggedPointerType-ratkaisua, jolla tag saadaan useimmissa tapauksissa sullottua osoittimen kanssa samaan konesanaan.

Luentoesimerkissä tullaan käyttämään ratkaisua, jossa variantti esitetään ir.TaggedPointerTypenä.

Luominen

Luentoesimerkissä jäi kokonaan tarkastelematta aiemmin, miten varianttiolio luodaan. Jouduin tätä pohtimaan pitkään, koska vastaus ei ole ilmeinen.

Koska variantissa on täsmälleen yksi kenttä aina aktiivinen ja variantti tietää, mikä kentistä on aktiivinen, C-kielestä tuttu ajatus

union list li;
li.nonempty.car = item;
li.nonempty.cdr = old_list;

ei tule kyseeseen. Ongelma tässä on, että kääntäjä joutuisi generoimaan kummallekin sijoituslauseelle koodin, joka tarkistaa, onko nonempty aktiivinen ja jos se ei ole, aktivoimaan sen (eli luomaan osoittimen taakse sopivan olion). Vain hyvä optimoija voisi huomata, että tarkistukset ovat tarpeettomia, eikä luennoilla rakenneta optimoijia.

Siispä variantin luonnin tulee samanaikaisesti alustaa variantti kertomalla, mikä kenttä on aktiivinen ja mielellään myös antamalla sille sisällön. Päädyin lähdekielessä tällaiseen hieman epätavalliseen syntaksiin:

return new union list .nonempty = cell;
...
union list empty = new union list .empty = ();

Tässä new-avainsana aloittaa lausekkeen, joka luo uuden variantin, joka on annettua tyyppiä ja jonka annettu kenttä alustetaan annntun lausekkeen arvolla.

Välikieleen puolestani lisäsin kolmiosoitekäskyn TAGNEW, joka luo uuden olion annetulla sisällöllä ja laittaa kohdeoperandiin TaggedPointerType-osoittimen annetulla tagilla. Ylläolevista ensiksi mainittu tuottaa seuraavanlaisen välikoodin:

TAGNEW   tmp@1           cell            1
RET                      tmp@1

Jälkimmäinen puolestaan seuraavanlaisen:

TAGNEW   tmp@1           @void           0              
COPY     empty           tmp@1

Tässä kenttä empty vastaa tagia 0 ja kenttä nonempty tagia 1; @void on operandi, jolla ei ole sisältöä (tyypiltään VoidType); kenttä empty on myös tyyppiä void.

switch ... case

Luennolla variantin lukemiseen päätettiin käyttää switch-case-rakennetta. Esimerkiksi voitaisiin kirjoittaa seuraavanlainen lähdekielinen aliohjelma (joka löytyy test_ir.py:stä):

int second(union list li, int dflt) {
  switch (li) {
    case empty: return dflt;
    case nonempty=x:
      switch (x.cdr) {
        case empty: return dflt;
        case nonempty=x: return x.car;
      }
  }
}

Tällaisen rakenteen kääntäminen voi edetä esimerkiksi seuraavasti. Käydään caset kahdesti läpi:

  • Ensiksi generoidaan hyppytaulu, jossa kulloisenkin casen kenttää vastaavaa tagia verrataan variantin tagiin ja hypätään tarvittaessa kyseisen casen koodista generoituun välikoodiin. Hyppytaulun lopuksi tulee hypätä koko switch-lauseen ulkopuolelle, jos kaikkia tageja ei tullut testattua.
  • Tämän jälkeen jokaisesta casesta generoidaan välikoodi. Jos case sitoo muuttujan, symtabiin sidotaan ir.PointerTargetAccessor. Jokaisen casen loppuun generoidaan varmuuden vuoksi hyppy switch-rakenteen loppuun.

Sisemmästä switch-rakenteesta tulee jotain tämän näköistä hyppytauluvälikoodia:

	6	JE       9               tmp@1.1/tag     0              
	7	JE       11              tmp@1.1/tag     1              
	8	JMP      14
  • Tässä /tag tarkoittaa TagAccessoria ja .1 tarkoittaa TupleElementAccessoria kentälle numero 1; siispä tmp@1.1/tag viittaa väliaikaismuuttujan tmp@1 (joka on tuple) kentän 1 tagiin.
  • JE hyppää ensimmäisen operandin osoittamaan kohtaan välikoodia, jos kaksi viimeistä operandia ovat samansisältöisiä.

Saman switch-rakenteen case empty: return dflt; kääntyy seuraavanlaiseksi välikoodiksi:

	9	RET                      dflt                           
	10	JMP      14

Ja case nonempty=x: return x.car; puolestaan seuraavanlaiseksi välikoodiksi:

	11	COPY     tmp@2           [tmp@1.1/1]                    
	12	RET                      tmp@2.0                        
	13	JMP      14
  • Tässä [.../1] tarkoittaa PointerTargetAccessoria tagilla 1.

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