Kääntäjätekniikka

Luento 16 (11.5.2017)

Kurssin aikataulut

• Seuraava vaihepalautus maanantaina 15.5. klo 16:
  • Välikielen generointi valmis [tai muita ominaisuuksia 1 op:n arvosta lisää]
  • Esittelytilaisuus 15.5.2017 klo 16–18 AgC233 (yli jäävä aika ohjauksina)
• Perjantai 19.5.2017 ohjaus peruttu

Vinkki assembly-koodaukseen ja koodigenerointiin

Huom! Jos gcc valittaa kirjastofunktioita käytettäessä jotain seuraavanlaista (esim. uudehkoissa Ubuntuissa):

relocation R_X86_64_PC32 against symbol `GC_malloc' can not be used when making a shared object; recompile with -fPIC

Lisää gcc:n komentoriville -no-pie. Se saattaa auttaa.

Kohti parempaa rekisterien valintaa

Käskyt ennen rekistereitä: helppo väliesitys

• Esitetään kukin käsky oliona, jossa on
  • käskyn mahdollinen kohdenimi (hyppyjä varten)
  • käskyn merkkijonomalline, jossa on ”aukot” operandeille
  • käskyn operandit pääosin viittauksina välikoodin operandiolioihin
    • kustakin tieto, luetaanko tai kirjoiteaanko siihen
  • luettelo operandeista, joita käytetään implisiittisesti
  • tieto, kopioiko käsky dataa operandista operandiin muuttamtta sitä
• Jokaiselle fyysiselle rekisterille oma väliaikaismuuttujansa
  • kopiointi tällaiseen ilmaisee pakon käyttää kyseistä rekisteriä
• Aliohjelman tai kunkin peruslohkon käskyt kootaan listaksi

Käskyjen ja rekisterien valinnan työnjako

• Käskyjen valinta
  • Generoi varsinaiseen toimintaan liittyvät käskyt.
  • Generoi siirrot nimettyyn rekisteriin tai nimetystä rekisteristä, kun tämä on välttämätöntä.
• Rekisterien valinta
  • Päättää, mitkä operandit ovat muistissa ja mitkä rekistereissä.
  • Päättää rekisterien multipleksauksesta.
  • Generoi tiedon siirtoon (muistin ja rekisterien välillä) liittyvät käskyt.

Kontrollivuograafi

• engl. control flow graph
• suunnattu graafi, jossa
  • solmuja ovat peruslohkot tai yksittäiset käskyt ja
  • kaaret edustavat mahdollisia suorituspolkuja peruslohkosta tai käskystä toiseen

Terminologiaa

• Solmulla on
  • lähteviä kaaria (out-edges),
  • tulevia kaaria (in-edges),
  • seuraajasolmuja (successor nodes) ja
  • edeltäjäsolmuja (predecessor nodes).
• Solmun \(n\)
  • seuraajasolmujen joukko on \(\mathrm{succ}(n)\) ja
  • edeltäjäsolmujen joukko on \(\mathrm{pred}(n)\).

Eloisuusanalyysi

• engl. liveness analysis
• yksi tietovuoanalyysin (engl. data flow analysis) ilmentymä
• Muuttujalla tarkoitetaan tässä aliohjelman parametreja, muita paikallisia muuttujia sekä kääntäjän luomia väliaikaisia paikallisia muuttujia –
  • ei siis globaaleja muuttujia.
• Tarkastellaan kontrollivuograafia, jossa solmut ovat yksittäisiä käskyjä.
  • mahdollista toki käyttää myös peruslohkoja
  • peruslohkograafilla analyysi olisi nopeampaa mutta hieman sotkuisempaa

Muuttujan eloisuus

• Solmu käyttää (use) muuttujaa, jos sen sisältämä käsky lukee muuttujan arvon.
• Solmu määrittelee (def) muuttujan, jos sen sisältämä käsky kirjoittaa muuttujaan arvon.
• Muuttuja on elossa (engl. live) tietyssä kontrollivuograafin kaaressa, jos on olemassa suunnattu polku ko. kaaresta
  • solmuun, joka käyttää kyseistä muuttujaa
  • niin, etttä polulla ei ole kyseistä muuttujaa määrittelevää solmua.
• Muuttuja tulee elossa (engl. is live-in) solmuun, jos se on elossa jossain siihen tulevassa kaaressa.
• Muuttuja lähtee elossa (engl. is live-out) solmusta, jos se on elossa jossain siitä lähtevästä kaaresta.

Merkintöjä

• \(\mathrm{use}(n)\) on solmun \(n\) käyttämien muuttujien joukko.
• \(\mathrm{def}(n)\) on solmun \(n\) määrittelemien muuttujien joukko.
• \(\mathrm{in}(n)\) on solmuun \(n\) elossa tulevien muuttujien joukko.
• \(\mathrm{out}(n)\) on solmusta \(n\) elossa lähtevien muuttujien joukko.

Eloisuuden tietovuoyhtälöt

Kaikilla solmuilla \(n\) pätee

\[ \begin{aligned} \mathrm{in}(n) &= \mathrm{use}(n) \cup (\mathrm{out}(n) − \mathrm{def}(n)) \\ \mathrm{out}(n) &= \bigcup_{n' \in \mathrm{succ}(n)} \mathrm{in}(n') \end{aligned} \]

Knasterin ja Tarskin lauseen mukaan näillä joukkoyhtälöillä on

• vähintään yksi ratkaisu sekä
• yksikäsitteiset pienin ja suurin ratkaisu.

Ks. Alfred Tarski: A lattice-theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5:2: 285-–309, 1955. Project Euclid

Kiintopisteiteraatio

Yleinen algoritmi tällaisten joukkoyhtälöiden pienimmän ratkaisun etsimiseen on kiintopisteiteraatio:

• alustetaan yhtälöiden vasemmat puolet tyhjiksi
• tulkitaan joukkoyhtälöt sijoituslauseiksi ja toistetaan kunnes joukot eivät enää muutu

Tehokkuus riippuu kovasti siitä, missä järjestyksessä solmuja käydään läpi. Tässä tapauksessa tehokkainta on edetä ohjelman lopusta alkua kohti.

Kysymys

Mistä on kyse, jos muuttuja tulee elossa aliohjelman ensimmäiseen käskyyn?