Kääntäjätekniikka

Luento 18 (18.5.2017)

Aikatauluja

• Ensi viikko:
  • maanantaina ohjaukset normaalisti
  • tiistaina käsitellään funktiokielten kääntämistä
  • torstaina ei ole luentoa (helatorstai)
  • perjantaina ei ole ohjauksia (peruttu)
• Lähettäkää toiveita viimeisen viikon luentojen (30.5. ja 1.6.) aiheiksi
  • sposti tai Slack
• Seuraava inkrementtideadline maantaina 29.5.2017 klo 16, yksi seuraavista:
  • Kohdekielen generointi (ilman fiksua rekisteriallokaatiota) valmis
  • Muita ominaisuuksia 1 op:n arvosta lisää

Kirjallisuutta

• Luentojen esitys globaalista rekisterien valinnasta perustuu pääosin Appelin lukuihin 10 ja 11.

Turhien kopiointien poisto

Yhdistä (coalesce) Yksinkertaistusaskeleen jälkeen etsi jokin kopiointikäsky \(a := b\) ja yhdistä solmut \(a\) ja \(b\), jos se on sallittua. Poista tämän jälkeen ohjelmasta kyseinen kopiointikäsky.

• Solmujen yhdistäminen on kiellettyä, jos ne ovat naapureita. Muutoin sovelletaan jompaa kumpaa seuraavista:

  • Kaksi solmua saadaan yhdistää, jos yhdistetyllä solmulla on vähemmän kuin \(k\) sellaisia naapuria, jolla on vähintään \(k\) naapuria, missä \(k\) on koneen rekisterien määrä. (Briggsin kriteeri)

  • Solmut \(a\) ja \(b\) saadaan yhdistää, jos jokaiselle \(a\):n naapurille \(t\) pätee, että \(t\) ja \(b\) ovat naapureita tai \(t\):llä on vähintään \(k\) naapuria. (Georgen kriteeri)

Jäädytä (freeze) Jos yksinkertaistus ja yhdistäminen ei kumpikaan onnistu, valitse jokin sellainen solmu, jolla on vähän naapureita, ja joka on osallisena kopiointikäskyssä. Merkitse ko. kopiointikäsky ei-kopiointikäskyksi.

Jos aikaa jää

Luentoesimerkin kautta:

• merkkijonot
• I/O