Kääntäjätekniikka

Luento 3 (21.3.2017)

Tämän luennon aiheet

• administrivia
• aliohjelmien teoriaa
• pinolokaalit muuttujat
• rekursiiviset aliohjelmat
• häntäkutsun poisto
• ensiluokkaiset aliohjelmat

Yksityiskohdat tänään vain AMD64 SysV ABI:n mukaisesti.

Esimerkkikoodit

Yousourcessa (huomaa branch!)

Kurssin tilannepäivitys

C-kirjastofunktioiden yhteenveto

• täällä

Lisäys suositeltujen kirjojen listaan

Kurssin opiskelijan löytö:

• Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs ja Koen Langendoen: Modern Compiler Design. 2nd edition. New York, NY: Springer, 2012. doi:10.1007/978-1-4614-4699-6

Harjoitustön tilanne

• Suunnitelman ohjeellinen deadline oli eilen. (Vielä ehtii!)
• Tee Yousourceen tai Githubiin git-varasto (repository)
  • jos se ei ole julkinen, anna lukuoikeus AJK:lle ja VT:lle (Yousourcessa antkaij ja aleator).
• Laita suunnitelma esimerkkiohjelmineen gitiin
• Tägää suunnitelma.
• Laita harjoitustyösi tiedot Korppiin.
  • Laita URLiksi varaston pääsivu, älä sen pull-osoitetta (haluan copypastettaa sen selaimeen!)
• Seuraava ohjeellinen deadline on kahden viikon kuluttua 3.4.2017 (jäsennin valmis)

Aliohjelmien teoriaa

Aliohjelman aktivaatio

• Kun aliohjelmaa kutsutaan, sen paikallisista muuttujista (myös parametrit) muodostetaan uudet esiintymät.
• Näiden paikallisten muuttujien esiintymien kokoelmaa kutsutaan aliohjelman aktivaatioksi.
• Aktivaatio pääsääntöisesti tuhotaan aliohjelman suorituksen päättyessä.
• Aliohjelmasta voi olla samanaikaisesti useita aktivaatioita.

Aktivaatioiden samanaikaisuus

• Säikeet
  • Eri säikeissä voi olla samanaikaisesti sama aliohjelma käynnissä.
• Rekursio
  • Jos aliohjelma kutsuu itseään (vaikka epäsuorasti), on siitä samassa säikeessä olemassa yhtä aikaa useita aktivaatioita.
• callcc (Scheme, ML)
• ensiluokkaiset aliohjelmat

Aktivaation tulee tietää

• aliohjelman saamat argumentit
• aliohjelman paikallisten muuttujien tähän aktivaatioon liittyvät esiintymät
• Mihin osoitteeseen tulee hypätä aliohjelman tultua valmiiksi? (paluuosoite)
• Mihin aliohjelma-aktivaatioon siirrytään aliohjelman tultua valmiiksi? (dynaaminen linkki)
• Jos kyseessä on aliohjelman A sisäinen aliohjelma B, missä A:n aktivaatiossa esiintyvät B:n tarvitsemat A:n paikalliset muuttujat? (staattinen linkki)
• Jos kyseessä on olion metodi, osoitin olion ilmentymään (this, self)

Nämä tiedot sisältävää tietorakennetta sanotaan aktivaatiotietueeksi (activation record)

Aktivaatiopino

• Saman säikeen aliohjelma-aktivaatiot muodostavat (yleensä) pinon
  • ... toteutettuna yksinkertaisesti linkittynä listana (linkkinä dynaaminen linkki)
• Aliohjelmaa kutsuttaessa sille muodostetaan aktivaatiotietue, joka lisätään pinon päällimmäiseksi.
• Aliohjelman päättyessä sen aktivaatiotietue on pinon päällimmäisenä; poistetaan se pinosta ja tuhotaan se.
• Tavallisesti aktivaatiopino rakennetaan niin, että aktivaatiotietueet ovat fyysisestikin päällekäin muistissa.
  • Näin aktivaatiotietueen luominen ja tuhoaminen on erittäin nopeaa.
  • Jos on useita säikeitä, jokaisella on oma aktivaatiopinonsa.

AMD64 SysV ABI:

Perustyyppisten parametrien välitys

• totuusarvot, kokonaisluvut (max 64 bittiä) ja osoittimet:
  • rdi, rsi, rdx, rcx, r8, r9
• liukuluvut (max 64 bittiä):
  • xmm0–xmm7
  • jos kutsuttava on stdarg-funktio (esim. printf), al:ssä oltava yläraja liukulukurekisterien käytölle (0–8)
• rekisterit otetaan käyttöön argumenttilistaa vasemmalta oikealle läpikäymällä
  • jos kaikki argumentille sopivat rekisterit on jo käytetty, argumentti välitetään pinossa

AMD64 SysV ABI:

Tietueiden parametrivälitys

• tietue välitetään kokonaan pinossa, jos
  • kooltaan yli 32 tavua tai
  • kentät eivät noudata alignment-vaatimuksia tai
  • mikään osa tietueesta välitettäisiin mistään syystä pinossa
• muuten tietue jaetaan 8 tavun osiin, jotka välitetään erikseen:
  • jos ainakin yksi osassa olevista kentistä välitetään kokonaisluvun tavoin, koko osa välitetään kokonaisluvun tavoin
  • muuten koko osa välitetään liukuluvun tavoin
• esimerkkejä: struct-amd64.S + struct-c.c; struct2-amd64.S + struct2-c.c; struct3-amd64.S + struct3-c.c

AMD SysV ABI:

Paluuarvon välitys

• paluuarvon luokittelu kuten parametreille
• pinossa välitettävä paluuarvo käsitellään erikseen:
  • kutsuja varaa paluuarvolle tilaa
  • paluuarvon tilan osoite välitetään rdi-rekisterissä aliohjelmalle
  • palatessa rax:ssa tulee olla rdi:ssä välitetty osoite
• totuusarvot, kokonaisluvut ja osoittimet palautetaan rekistereissä rax ja rdx
• liukuluvut palautetaan rekistereissä xmm0 ja xmm1
• kaksi rekisteriä varataan, jotta 16-tavuinen (joskus jopa 32-tavuinen) tietue voidaan palauttaa rekistereissä

Välihuomautus: Staattinen linkki ja this

• sekä staattinen linkki että this tulee välittää parametreina normaaliin tapaan

AMD64 SysV ABI:

Pinon käyttö aliohjelmakutsussa

• pinossa välitettävät argumentit laitetaan pinoon argumenttilistaa oikealta vasemmalle läpi käyden
  • argumentin koko pyöristetään ylöspäin niin, että se on jaollinen 8 tavulla
• ensimmäisen argumentin
  • osoite tulee olla 8 tavulla mutta ei 16 tavulla jaollinen
  • tulee olla pinossa päällimmäisenä kun call-käsky aloitetaan
• kutsuja poistaa argumentit pinosta

AMD64 SysV ABI:

Pinokehys

• engl. stack frame
• aliohjelman käytössä oleva osa pinosta
• on melkein sama asia kuin aktivaatiotietue
  • pinoargumentit kuuluvat aktivaatiotietueeseen mutta eivät pinokehykseen
• alkaa paluuosoitteesta ja päättyy pino-osoittimen rsp osoittamaan kohtaan
  • huomaa: pino kasvaa alaspäin
  • jos aliohjelma ei kutsu muita aliohjelmia, se saa käyttää myös 128 tavua rsp:n jälkeen (alapuolelta)
• paluuosoitteen osoitteen tulee olla 16 tavulla jaollinen
  • kutsujan vastuulla huolehtia tästä
  • kutsuttava saa olettaa tämän pätevän

AMD64 SysV ABI:

Aliohjelman prologi ja epilogi

Luodaan ja puretaan pinokehys:

push    rbp
mov     rbp,    rsp
sub     rsp,    n
...
mov     rsp,    rbp
pop     rbp
ret

missä n on paikallisten muuttujien tarvitsema tila tavuina (16:lla jaollinen).

• sub voidaan korvata jonolla push-käskyjä
  • huolehdi, että rsp:n muutos on 16:lla jaollinen
• muistissa oleva data kannattaa pushata
  • ei tarvitse lukea rekisteriin

AMD64: Muistiosoitukset

Useimmat käskyt sallivat, että yksi operandeista viittaa muistiin. Muistiosoituksen yleinen muoto on

[r1 + s * r2 + d]

• hakasulkeissa olevan lausekkeen arvo on muistiosoite, josta data luetaan
• r1 ja r2 ovat kokonaislukurekistereitä
• s on 1, 2, 4 tai 8 (vakio)
• d on enintään 32-bittinen etumerkillinen vakio
• enintään kaksi termeistä voi puuttua
• muistiosoituksen eteen pitää tavallisesti kirjoittaa byte ptr, word ptr, dword ptr tai qword ptr kertomaan operandin koko (8, 16, 32 tai 64 bittiä), jos käskyllä ei ole myös rekisterioperandia

Digressio: LEA-käsky (AMD64)

LEA rekisteri, [lauseke]

• sijoittaa rekisteriin lausekkeen arvon
• lauseke on mikä vain joka kepaa muistiosoitukseksi
  • mutta LEA ei lataa mitään muistista!
• voi käyttää kokonaislukuaritmetiikkaan muistiosoitelausekkeen yleisen muodon rajoissa
• voi myös käyttää osoitteen laskemiseksi rekisteriin

AMD64 SysV ABI:

Kehysosoitin

• rbp-rekisteri on kehysosoitin, engl. frame pointer
• 1. pinoargumentti löytyy osoitteesta rbp+16
• jos 1. pinoargumentti oli 64 bittiä leveä, 2. pinoargumentti löytyy osoitteesta rbp+24
• paikalliset muuttujat löytyvät negatiivisista offseteista rbp:n suhteen
• ei pakollinen jos paikallisten muuttujien tarvitseman tilan koko on vakio
  • tällöin argumentit ja paikalliset muuttujat indeksoidaan rsp:n suhteen

AMD64 SysV ABI:

Paikalliset muuttujat

• paikalliset muuttujat, jotka eivät mahdu rekistereihin tai joilla tarvitsee olla osoitin, tallennetaan pinoon
  • myös callee save -rekisterien tallennukset
• paikallisille muuttujille varattu osa pinokehyksestä alkaa rbp:stä ja päättyy rsp:hen
  • kannattaa jakaa suunnitelmallisesti eri muuttujille
• paikalliseen muuttujaan viitataan [rbp-n], missä n on muuttujan offset suhteessa rbp:hen

Rekursiiviset aliohjelmat

Rekursiivisessa aliohjelmassa paikalliset muuttujat on pääsääntöisesti pakko laittaa pinoon, jos niiden tulee säilyä yli rekursiivisen kutsun.

Muutoin rekursiivisessa aliohjelmassa ei ole mitään ihmeellistä.

Esimerkkejä: factorial, treesum (ks myös C-koodi)

Häntäkutsun poisto

    call    f
    mov     rsp,    rbp
    pop     rbp
    ret

voidaan vaihtaa muotoon

    mov     rsp,    rbp
    pop     rbp
    jmp     f

jos kutsuja ja kutsuttava eivät ota pinossa välitettäviä parametreja.

esimerkki: ennen jälkeen

Huomioita häntäkutsun poistosta

• muuttaa pinoa syövän rekursion pinoon koskemattomaksi iteraatioksi
  • mutta ei rajoitu vain rekursion tapaukseen
• mahdollista vain, jos kutsun paluuarvo välitetään sellaisenaan ja välittömästi kutsujan kutsujalle
• joskus häntäkutsun poiston jälkeen kehyksen rakentaminen ja purkaminen voidaan jättää tekemättä (esimerkki)
• jotkin lähdekielet vaativat, että jokainen häntäkutsu on poistettava
  • tällöin kieli ei välttämättä tarvitse erillisiä silmukkarakenteita

Standardi ABI ei sovellu kaikkeen

Seuraavat temput eivät onnistu standardi-ABIen kanssa:

• häntäkutsun poisto, kun kutsuja ottaa vähemmän tavuja pinoargumentteina kuin kutsuttava
• osittain kutsutut aliohjelmat ja ensiluokkaiset aliohjelmat

Näitä tarvitsevan kääntäjän tulee määritellä oma ABI.

• voi olla fiksua tarjota ohjelmoijalle mahdollisuus määritellä, että jokin aliohjelma noudattaa poikkeuksellisesti standardi-ABIa

Vapaaehtoinen harjoitustehtävä

Kirjoita ensin C-kielellä yksinkertaisesti linkitetyn listan (alkiotyyppinä long) käsittelykirjasto (add_front, remove_first, map – missä map ottaa parametrinaan yksiparametrisen funktion ja listan ja kutsuu ko. funktiota jokaiselle listan alkiolle) ja sitten sitä käyttäen testipääohjelma, joka käyttäen map-funktiota laskee listan alkioiden summan.

Sen jälkeen kirjoita sama assemblynä.