TIES448 Kääntäjätekniikka

Luento 2 (16.3.2017)

Esimerkkikoodit

Yousourcessa

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.

Luettavaa

Viralliset dokumentaatiot (laajoja, pitkälti TMI):

Konekielten yleispiirteitä

  • erittäin yksinkertainen rakenne
  • tyypittömyys (”kaikki on sanoja”)
  • rekisterit (ei nimettyjä paikallisia muuttujia)
  • alkeistoimituksiin rajoittuminen
  • abstraktiokeinojen puute

Konekielen rakenne

  • Konekielinen ohjelma on jono käskyjä
  • Kukin käsky koostuu (tavallisesti) operaatiokoodista eli opkoodista (engl. opcode) sekä 0–3 operandista
  • Käskyjen koodaustapa riippuu ISA:sta. Esimerkiksi
    • IA32:ssa kolmitavuinen käsky 80 F1 12 käskee XORraamaan luvun 18 ja erään rekisterin arvon ja tallettamaan tuloksen ko. rekisteriin.

Konekielen tyypit

  • Konekielessä kaikki data on eri mittaisia bittijonoja.
  • Kohdedatan pituus ja tulkinta riippuvat täysin opkoodista.
  • Tyyppitarkastusta ei ole.
  • tyypillisiä konekielen tyyppejä:
    • \(n\)-bittinen etumerkitön kokonaisluku (aritmetiikka modulo \(2^n\))
    • \(n\)-bittinen etumerkillinen kokonaisluku (kahden komplementti)
    • \(n\) bitin bittijono
    • \(n\) bitin IEEE-liukuluku
    • \(n = 8, 16, 32, 64(, 128)\) (paitsi liukuluvuilla \(n = (16,) 32, 64\))

Symbolinen konekieli

  • Tunnetaan myös nimellä assembly.
  • Ihmisen luettavaksi tarkoitettu konekielen esitystapa.
  • Joka ISA:lla on oma assemblynsä, joillakin on jopa useampia.
  • Yksi käsky esitetään yhdellä rivillä.
  • Kullakin opkoodilla on lyhyt nimi eli muistikas (engl. mnemonic).
  • Operandit esitetään havainnollisella tavalla.

Assemblerit

  • Yksinkertainen kääntäjä, ns. assembler, kääntää symbolisen konekielen konekieleksi.
  • Monilla ISA:illa on monta eri assembleria
  • Osa assemblereista tukee monta ISA:ta
  • tällä luennolla käytämme GNU:n assembleria sekä ARMille että AMD64:lle
    • ARMilla unified-syntaksia
    • AMD64:llä Intel-syntaksia (melkein sama kuin nasmissa)

Ensimmäinen ohjelma

ARM

@ Lasketaan 1+1 (kokonaisluvuilla), tulos mainin paluuarvona

        .syntax unified

        .global main

        .text

main:   mov     r0, #1
        add     r0, r0, #1
        bx      lr

Käännös ja suoritus Debianin tai Ubuntun ARMv7-emulaatiossa:

$ arm-linux-gnueabihf-gcc -o minimal-arm minimal-arm.s
$ ./minimal-arm 
$ echo $?

AMD64

# Lasketaan 1+1 (kokonaisluvuilla), tulos mainin paluuarvona

        .intel_syntax noprefix
        
        .global main

        .text
        
main:   mov     rax, 1
        add     rax, 1
        ret

Käännös ja suoritus Linuxin komentorivillä (AMD64-koneessa, 64-bittinen käyttöjärjestelmä):

$ gcc -o minimal-amd64 minimal-amd64.s 
$ ./minimal-amd64 
$ echo $?

Sivuhuomautus

Käännämme gcc:llä, koska

  • gcc tajuaa tiedostopäätteestä .s, että syöte on assemblya
    • kutsuu automaattisesti assembleria
  • gcc hoitaa linkityksen puolestamme
  • gcc linkittää mukaan C-standardikirjaston
    • mukaan lukien C:n alustuskirjaston, joka kutsuu main-funktiota

Ensimmäiset rivit

  • Kommenttirivi alussa; kommentti päättyy rivin loppuun ja alkaa
    • @ (ARM)
    • # (AMD64)
  • Seuraava epätyhjä rivi valitsee käytetyn syntaksin
  • Kolmas epätyhjä rivi .global main ilmoittaa, että nimi main on julkinen

Assemblerin toimintaperiaate

  • pääsääntöisesti jokainen epätyhjä rivi muuttuu jonoksi tavuja ohjelmassa
    • myös käskyrivit koodataan jonoiksi tavuja
    • kommenttirivit lasketaan tyhjiksi
  • poikkeuksena osa riveistä, joilla esiintyy ns. "pseudokäskyjä", jotka alkavat pisteellä
  • ohjelma jaetaan osiin (section):
    • .text-osaan ohjelmakoodi ja vakiot
    • .data-osaan alustetut globaalit muuttujat
    • .bss-osaan nollaksi alustettavat globaalit muuttujat
  • osaan tulee kaikki osan ilmoittavan pseudokäskyn jälkeen tulevat tavut

Ensimmäinen koodirivi

        @ ARM
main:   mov     r0, #1
        # AMD64
main:   mov     rax, 1
  • Rivin alussa on label main
    • main tarkoittaa tästä lähtien labelia seuraavan tavun osoitetta
  • Siirretään rekisteriin kokonaislukuvakio 1
  • Käsky alkaa muistikkaalla (engl. mnemonic), joka kertoo käskyn operaation
    • tässä sattumalta molemmissa assemblyissä sama muistikas, aina näin ei ole
  • Käskyn operandit erotetaan toisistaan pilkulla
    • eka operandi on operaation kohde
  • Vakio kirjoitetaan AMD64:ssä sellaisenaan, ARMissa eteen laitetaan #

Rekisterit

  • keskusyksikön sisällä olevia nimettyjä muistiyksiköitä
  • rekisterin käyttö olennaisesti muistin käyttöä nopeampaa
  • joissakin ISA:issa laskenta mahdollista vain rekistereissä
  • erittäin rajattu määrä, kourallisesta muutamaan kymmeneen
  • ARMv7:ssa
    • 32-bittisiä yleisrekistereitä 13 kpl (R0–R12)
    • 64-bittisiä liukulukurekistereitä 16 tai 32 kpl (D0–D31)
  • AMD64:ssä
    • 64-bittisiä kokonaislukurekistereitä 16 kpl (RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8–R15)
    • 2×64-bittisiä liukulukurekistereitä 16 kpl (XMM0–XMM15)

AMD64:n alirekisterit

  • Jokaisella AMD64:n kokonaislukurekisterillä on nimettyjä alirekistereitä
  • RAX, RBX, RCX, RDX:
    • 32 alinta bittiä EAX, EBX, ECX, EDX
    • 16 alinta bittiä AX, BX, CX, DX
      • jonka 8 ylintä bittiä AH, BH, CH, DH
    • 8 alinta bittiä AL, BL, CL, DL
  • RSI, RDI, RBP, RSP, R8–R15:
    • 32 alinta bittiä ESI, EDI, EBP, ESP, R8D–R15D
    • 16 alinta bittiä SI, DI, BP, SP, R8W–R15W
    • 8 alinta bittiä SIL, DIL, BPL, SPL, R8B–R15B

Toinen koodirivi

        @ ARM
        add     r0, r0, #1
        # AMD64
        add     rax, 1
  • molemmissa taas puolivahingossa sama muistikas
    • ARM:n add laskee toisen ja kolmannen operandin yhteen ja tallettaa tuloksen ensimmäiseen operandiin
    • AMD64:n add laskee operandit yhteen ja tallettaa tuloksen ensimmäiseen operandiin
  • add tekee molemmissa kokonaislukuyhteenlaskun!
    • liukulukulaskentaan on eri käskyt

Kolmas koodirivi

        @ ARM
        bx      lr
        # AMD64
        ret
  • käskyt tekevät "pellin alla" aika lailla eri asioita, mutta lopputulos on molemmissa sama:
  • palataan aliohjelmasta main sen kutsujaan

Toinen ohjelma

ARM

        @ Kopioidaan syöte tulosteeseen

        .syntax unified
        .global main
        .text

main:   push    {ip,lr}
0:      bl      getchar
        cmp     r0,     #0
        blt     1f
        bl      putchar
        b       0b
1:      mov     r0,     #0
        pop     {ip,lr}
        bx      lr

AMD64

        # Kopioidaan syöte tulosteeseen

        .intel_syntax noprefix
        .global main
        .text

main:   push    rbp
0:      call    getchar
        cmp     eax,    0
        jl      1f
        mov     rdi,    rax
        call    putchar
        jmp     0b
1:      mov     rax,    0
        pop     rbp
        ret

Suuruusvertailujen koodaaminen

        @ ARM
        cmp     r0,     #0
        # AMD64
        cmp     eax,    0
  • cmp suorittaa molemmissa assemblyissä vähennyslaskun, jonka tulosta ei tallenneta mihinkään
  • tuloksen ominaisuuksia tallennetaan lippuihin, mm.
    • N / SF: oliko negatiivinen?
    • Z / ZF: oliko nolla?
    • V / OF: tuottiko ylivuodon?
    • C / CF: tuottiko carry-tilanteen?
    • (ARM / AMD64)

Valintojen tekeminen

        @ ARM
        blt     1f
...
1:
        # AMD64
        jl      1f
...
1:
  • lippujen perusteella voidaan tehdä ehdollisia hyppyjä
    • hyppykäskyn nimi alkaa ARMissa b ja AMD64:ssä j
    • nimi jatkuu ehdon kuvauksella
  • hypyn kohteena jokin lähellä oleva käsky
    • 1f viittaa käskyä seuraavaan 1:-labeliin
    • 1b viittaa käskyä edeltävään 1:-labeliin
    • 2f / 2: jne myös mahdollisia
    • voi myös käyttää tavallisia nimettyä labeleita

Ehdollisia hyppykäskyjä ARMissa

Käsky Ehto cmp \(a\),\(b\) \(a\)
beq \(Z = 1\) \(a = b\) \(a = 0\)
bne \(Z = 0\) \(a \neq b\) \(a \neq 0\)
bmi \(N = 1\) \(a < 0\)
bpl \(N = 0\) \(a \geq 0\)
bhi \(C=1\land V=0\) \(a > b\) (u)
bls \(C=0\lor V=1\) \(a \leq b\) (u)
bge \(N = V\) \(a \geq b\) (s)
blt \(N \neq V\) \(a < b\) (s)
bgt \(Z=0\land N=V\) \(a > b\) (s)
ble \(Z=1\lor N\neq V\) \(a \leq b\) (s)
  • u tarkoittaa etumerkitöntä tulkintaa
  • s tarkoittaa kahden komplementti -tulkintaa

Ehdollisia hyppykäskyjä AMD64:ssä

Käsky Ehto cmp \(a\),\(b\) \(a\)
je, jz \(ZF = 1\) \(a = b\) \(a = 0\)
jne, jnz \(ZF = 0\) \(a \neq b\) \(a \neq 0\)
js \(SF = 1\) \(a < 0\)
jns \(SF = 0\) \(a \geq 0\)
jb \(CF=1\) \(a < b\) (u)
jnb \(CF=0\) \(a \geq b\) (u)
jge \(SF = OF\) \(a \geq b\) (s)
jl \(SF \neq OF\) \(a < b\) (s)
jg \(ZF=0\land SF=OF\) \(a > b\) (s)
jle \(ZF=1\lor SF\neq OF\) \(a \leq b\) (s)
  • u tarkoittaa etumerkitöntä tulkintaa
  • s tarkoittaa kahden komplementti -tulkintaa

Silmukat

        @ ARM
0:
...
        blt     1f
...
        b       0b
1:
        # AMD64
0:
...
        jl      1f
...
        jmp     0b
1:
  • silmukoita ei ole, ne on koodattava hyppykäskyistä
  • while (e) S kääntyy muotoon
    • e
    • jos epätosi, hyppää ulos
    • S
    • hyppää silmukan alkuun
  • ehdoton hyppy ARM:ssa b ja AMD64:ssä jmp

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

Aliohjelmakutsut ARM:ssa

        bl      getchar         @ int getchar(void)
        cmp     r0,     #0
        blt     1f
        bl      putchar         @ int putchar(int)
  • aliohjelmakutsukäsky on bl
    • paluuosoite tallentuu automaattisesti rekisteriin lr eli r14
    • kutsujan oma paluuosoite tuhoutuu samalla
  • 4 ensimmäistä kokonaislukuparametria välitetään rekistereissä r0, r1, r2 ja r3
  • kokonaislukupaluuarvo välitetään rekisterissä r0

Aliohjelman koodaus ARM:ssa

main:   push    {ip,lr}
...
        mov     r0,     #0
        pop     {ip,lr}
        bx      lr
  • jos aliohjelma kutsuu muita aliohjelmia, sen paluuosoite on pelastettava rekisteristä lr
    • yksinkertaisinta laittaa pinoon: push {ip,lr}
    • samalla laitetaan pinoon jokin muu rekisteri (tässä ip), jotta pino-osoitin pysyy 8:lla jaollisena
    • ennen paluuta otetaan takaisin pinosta: pop {ip,lr}
  • paluukäsky bx lr hyppää lr-rekisterissä olevaan osoitteeseen
    • periaatteessa on muitakin tapoja, mutta niissä on omat kommervenkkinsä, tämä on turvallisin
  • kokonaislukupaluuarvo laitetaan rekisteriin r0

Aliohjelmat AMD64:ssä (SysV ABI)

main:   push    rbp
        call    getchar         # int getchar(void)
        cmp     eax,    0
        jl      1f
        mov     rdi,    rax
        call    putchar         # int putchar(int)
...
1:      mov     rax,    0
        pop     rbp
        ret
  • aliohjelmakutsukäsky on call ja paluukäsky ret
    • paluuosoite kulkee automaattisesti pinossa
    • paluuosoite on 8 tavua pitkä, mutta pinon osoitteen tulee olla 16:lla jaollinen kutsun tapahduttua, joten laitetaan jotain muuta myös pinoon
  • 6 ensimmäistä kokonaislukuparametria välitetään rekistereissä rdi, rsi, rdx, rcx, r8 ja r9
  • kokonaislukupaluuarvo välitetään rekisterissä rax
    • mutta rax on 64-bittinen, int on 32-bittinen, joten vertailu tehdään yllä rax:n 32-bittisellä osarekisterillä eax

Caller save ja callee save

  • rekisterit jaetaan kahteen luokkaan:
    • caller save: rekisteri, jota aliohjelma saa käyttää vapaasti aliohjelmakutsujen välissä, mutta jonka arvo ei välttämättä säily aliohjelmakutsun yli
    • callee save: rekisteri, jota aliohjelma saa käyttää vain, jos se tallettaa sen alkuperäisen arvon ja palauttaa sen ennen paluutaan
      • ARM:ssa r4, r5, r6, r7, r8, r10, r11
      • AMD64:ssä (SysV ABI) rbx, rbp, r12, r13, r14, r15

Rekisterien arvojen talletus pinoon

  • ARM:ssa
    • push {rekisteri,...,rekisteri} laittaa pinoon
      • laita pinoon aina 8:lla jaollinen määrä tavuja kerrallaan
      • rekisterien luettelon tulee olla numerojärjestyksessä
      • ip on numeroltaan r12, lr on r14
    • pop {rekisteri,...,rekisteri} ottaa pinosta
      • sama luettelo rekistereitä!
  • AMD64:ssä
    • push rekisteri laitaa pinoon
      • huolehdi, että aliohjelmakutsun laitettua paluuosoitteen pinoon pino-osoitin on jaollinen 16:lla
    • pop rekisteri poistaa pinosta
      • poista käänteisessä järjestyksessä (LIFO!)

Liukuluvut ARM:ssa (armhf)

  • Yksinkertaisuuden vuoksi:
    • vain kaksoistarkkuus (double, 64 bittiä)
    • vain armhf ("hardware float") -järjestelmät
  • Samalla myös esimerkki
    • globaaleista muuttujista
    • merkkijonovakioista

Keskiarvoaliohjelma

avg:    vadd.f64        d0, d0, d1
        vmov.f64        d1, #2.0
        vdiv.f64        d0, d0, d1
        bx              lr
  • Liukulukurekisterit ovat nimeltään d0,...,d15 ja joissakin prosessoreissa lisäksi d16,...,d31
    • d8,...,d15 ovat callee save
  • Liukulukukäskyjen muistikkaat alkavat kirjaimella v ja päättyvät pääosin tyyppimäärittelyyn .f64 ("64-bittinen liukuluku")
  • 8 ensimmäistä liukulukuparameteria välitetään liukulukurekistereissä d0,...,d7
    • poikkeuksena printf ym (stdarg.h-aliohjelmat)
  • liukulukupaluuarvo välitetään d0:ssa

Liukulukujen lukeminen scanf:lla

        ldr     r0, =rfmt
        ldr     r4, =tmp1
        ldr     r5, =tmp2
        mov     r1, r4
        mov     r2, r5
        bl      scanf
        cmp     r0, 2
        bne     1f
        vldr    d0, [r4]
        vldr    d1, [r5]
...
        .balign 8
rfmt:   .asciz  "%lf %lf\n"

        .bss
        .balign 8
        .comm   tmp1,   8
        .comm   tmp2,   8

Formaattimerkkijono

        ldr             r0, =rfmt
...
        .balign         8
rfmt:   .asciz          "%lf %lf\n"
  • Merkkijonovakio (ei Unicode) kirjoitetaan .text-osaan .asciz-pseudokäskyllä.
    • Sille annetaan nimi kuten aliohjelmalla.
    • Ennen merkkijonovakiota varmistetaan, että osoite on kahdeksalla jaollinen, pseudokäskyllä .balign 8
  • Nimetty osoite luetaan rekisteriin (pseudo)käskyllä ldr r0, =rfmt
    • assembler vääntää tästä pellin alla vähän monimutkaisemman

Luettujen lukujen tallennusmuuttujat

        ldr     r1, =tmp1
        ldr     r2, =tmp2
...
        .bss
        .balign 8
        .comm   tmp1,   8
        .comm   tmp2,   8
  • Jokaista formaattimerkkijonossa olevaa %lf-osajonoa kohti pitää olla yksi tallennusmuuttuja, jonka osoite viedään parametina.
  • Globaalit muuttujat voidaan luoda .bss-osaan
    • Muuttujalle annetaan nimi tmp1 ja 8 tavua tilaa pseudokäskyllä .comm tmp1, 8
    • Muuttujat alustuvat ohjelman käynnistyessä nollabittijonoiksi

Lukemisen onnistumisen tarkastaminen ja lukujen käyttöönotto

        bl              scanf
        cmp             r0, 2
        bne             1f
        ldr             r0, =tmp1
        ldr             r1, =tmp2
        vldr            d0, [r0]
        vldr            d1, [r1]
  • scanf palauttaa onnistuneesti luettujen muuttujien lukumäärän
  • luetut luvut siirretään liukulukurekistereihin vldr-käskyllä
    • [r0] tarkoittaa, että operandi löytyy muistista r0:n sisältämän osoitteen kohdalta
  • huomaa, että tmp1 ja tmp2 -osoitteet lasketaan nyt monta kertaa
    • voi myös tallettaa callee save -rekistereihin odottamaan uudelleenkäyttöä (näin alkuperäisessä ohjelmassa)
    • muista tallettaa näiden rekisterien alkuperäiset arvot pinoon!

Tuloksen tulostaminen printf-aliohjelmalla

        ldr             r0, =wfmt
        vmov            r2, r3, d0
        bl              printf
...
        .balign         8
wfmt:   .asciz          "%lf\n"
  • printf:n formaattimerkkijonossa esiintyvä %lf tarkoittaa, että printf:lle pitää antaa lisäksi double-tyyppinen parametri
  • printf:n kaltaisille aliohjelmille (stdargs) double-parameterit jaetaan kahdeksi 32-bittiseksi parametriksi, jotka välitetään kahdella jaollisesta rekisteristä alkaen kuten kokonaisluvut
    • mov r2, r3, d0 tekee tämän parameterinvälityksen

Liukuluvut AMD64:ssä

  • yksinkertaisuuden vuoksi vain kaksoistarkkuus (double)
  • Samalla myös esimerkki
    • globaaleista muuttujista
    • merkkijonovakioista

Keskiarvoaliohjelma

avg:    addsd           xmm0, xmm1
        mov             rax, 2
        cvtsi2sd        xmm1, rax
        divsd           xmm0, xmm1
        ret
  • 8 ensimmäistä liukulukuparametria välitetään rekistereissä xmm0,...,xmmm7
  • liukulukupaluuarvo välitetään rekisterissä xmm0
  • addsd laskee kaksi liukulukua yhteen
  • cvtsi2sd muuttaa kokonaisluvun liukuluvuksi
  • divsd on jakolasku

Liukulukujen lukeminen scanf:llä

        lea     rdi,    [rfmt]
        mov     al,     0
        lea     rsi,    [tmp1]
        lea     rdx,    [tmp2]
        call    scanf
  • lea laskee ensimmäiseen operandiinsa toisen operandinsa muistiosoitteen
    • hakasulkeisiin kirjoitetaan muistiosoitteen lähde
      • voi olla vakio, rekisteri tai vähän monimutkaisempaa
  • scanf-funktion tyyppisille aliohjelmille (stdarg) on kerrottava al-rekisterissä, montako liukulukuparametria on enintään rekistereissä

Lukujen tulostaminen printf:llä

        movsd   xmm0,   [tmp1]
        movsd   xmm1,   [tmp2]
        lea     rdi,    [wfmt]
        mov     al,     1
        call    printf
  • movsd lataa liukuluvun muistista
  • liukulukuparametrit välitetään myös stdarg-funktioille liukulukurekistereissä
    • al:ssä kerrottava liukulukurekistereissä olevien parametrien enimmäismäärä
      • ei tarvitse olla tarkka tieto, mutta max 8

C-kirjastofunktioiden yhteenveto

Vapaaehtoisia harjoitustehtäviä

Kirjoita assembly-ohjelma:

  1. joka lukee käyttäjältä rivin ja tulostaa saman rivin niin, että pienet kirjaimet on muutettu isoiksi kirjaimiksi (vain ASCII, eli ei ääkkösiä ym).
  2. joka laskee syötteessä olevien sanojen lukumäärän.
  3. joka tulostaa Fibonaccin lukujonon (siihen asti kunnes 64-bittisestä kokonaisluvusta loppuu esitystarkkuus tai kunnes käyttäjä ohjelman keskeyttää Ctrl-C:llä)

Näitä voidaan käsitellä ohjauksissa.

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