Kääntäjätekniikka

Luento 3 (5.4.2016)

Huomioita akateemisesta rehellisyydestä

  • Rehellisyys on välttämätöntä mutta ei riittävää suoritukseen.
    • Aina pitää osoittaa myös itse asian osaamista.
  • Pelkkä copypaste ei ole yleensä riittävä vastaus mihinkään, vaikka se olisi rehellisesti tehty.
    • Yleensä vähintäänkin se copypaste pitää ymmärtää hyvin ja kyetä sen sisältö selittämään.
    • Kokoelma copypasteja saattaa olla riittävä vastaus, jos kokoelman kokoaminen osoittaa asian ymmärrystä.
      • Tosin harvoin johtaa hyvään arvosanaan.
    • Näihin sääntöihin on poikkeuksia.

Tämän luennon aiheet

  • aliohjelmien teoriaa
  • Application Binary Interface (ABI)
  • pinolokaalit muuttujat
  • rekursiiviset aliohjelmat
  • häntäkutsun poisto
  • ensiluokkaiset aliohjelmat

Esimerkkikoodit

Yousourcessa (huomaa branch!)

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.

Application Binary Interface

(ABI)

  • ISA-kohtainen
  • yleensä myös käyttöjärjestelmäkohtainen
  • voi olla myös kääntäjäkohtainen
  • määrittelee mm.
    • tietotyyppien esitystavat
    • aliohjelmien kutsurajapinnan
  • jos käännetty ohjelma ja käännetty kirjasto noudattavat samaa ABIa, ne voi linkittää yhteen

ABI-vaihtoehtoja

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

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 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
  • 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)
  • on melkein sama asia kuin aktivaatiotietue
    • pinoargumentit kuuluvat aktivaatiotietueeseen mutta eivät pinokehykseen

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 on lopulta 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 [ebp-n], missä n on muuttujan offset suhteessa ebp: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ä.

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.

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

Ensiluokkaiset aliohjelmat

  • Aliohjelma on ensiluokkainen (engl. first class), jos
    • se voidaan palauttaa aliohjelman paluuarvona ja tallettaa muuttujaan vapaasti ja
    • se voidaan määritellä toisen aliohjelman sisällä.
  • Kaksi ongelmaa:
    • Kun aliohjelma tallennetaan muuttujaan tai palautetaan paluuarvona, mitä sinne muuttujaan tai paluuarvoon oikeasti laitetaan?
    • Aliohjelma voi viitata jonkin toisen aliohjelman paikallisiin muuttujiin sen jälkeen kun ko. aliohjelma on jo lopettanut toimintansa!

Osittaiset kutsut

Aliohjelmaa voidaan kutsua osittain (engl. apply partially), jos

  • sitä voidaan kutsua vähemmällä määrällä argumentteja kuin se oikeasti ottaa ja
  • tämän kutsun paluuarvona on aliohjelma, joka muistaa sille jo annetut argumentit ja joka kutsuttaessa ottaa loput argumentit ja toimii sitten kuten alkuperäinen aliohjelma näillä argumenteilla.

Osittaisten kutsujen ongelmat ovat olennaisesti samat kuin ensiluokkaisten aliohjelmien ongelmat, vaikka aliohjelmia ei voisikaan määritellä toisten sisällä.

Sulkeuma

  • Sulkeuma on aliohjelmaa (ei sen aktivaatiota) ajon aikana edustava tietue.
  • Se sisältää riittävästi tietoa aliohjelmasta, että sen perusteella ko. aliohjelmaa voidaan kutsua tietämättä mitä aliohjelmaa ollaan kutsumassa.
  • Sulkeuma sisältää
    • osoitteen, johon hypätään aliohjelmaa kutsuttaessa
    • aliohjelman tarvitseman staattisen linkin
    • this (jos tarpeen)
    • osittain kutsutun aliohjelman tapauksessa jo annetut argumentit
  • Mutta miten ratkaistaan se, että staattisen linkin kohteena oleva aktivaatiotietue saattaa olla jo tuhottu sulkeuman kautta kutsuttaessa?

Yksinkertainen ratkaisu

  • Ei käytetä ISA:n tarjoamaa pinoa lainkaan.
  • Allokoidaan jokainen aktivaatiotietue keosta ja käytetään muistinsiivousta.
    • Jos muistinsiivousalgoritmi valitaan fiksusti, tämä ei juurikaan hidasta ohjelman toimintaa.
  • Tämä tapa on käytännössä pakollinen, jos callcc on tarjolla.

Vähän fiksumpi tapa

  • Jaetaan aktivaatiotietue kahteen eri tietueeseen.
  • Allokoidaan keosta tietue, jonne tallennetaan pakenevat (engl. escaping) paikalliset muuttujat.
  • Pinokehykseen jää kaikki muu sekä osoitin keossa olevaan pakenevien muuttujien tietueeseen.
  • Aliohjelman staattinen linkki ei osoita enää pinokehykseen vaan pakenevien muuttujien tietueeseen.

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