Ershovin numero

Ershov-lukuja käytetään koodin optimoinnissa lausekkeen käyttämien rekisterien määrän minimoimiseksi . Niitä voidaan käyttää rekisterioptimaalisissa menetelmissä, kun koodilohkossa on vain yksi lauseke. Kun lauseke E = E 1 -operaatio E 2 , niin tavoitteena on luoda koodi siten, että käytettävien rekisterien kokonaismäärä minimoidaan ja mikäli käytettävissä olevia rekistereitä ei ole riittävästi, tilapäisten määrä minimoidaan. muuttujia (eli muistin sanoja).

Tietyn lausekepuun solmun Ershov-luku n määritellään seuraavasti [1] :

Kaikkien lehtien arvo on 1.
Yhden lapsisolmun sisäisen solmun Ershov-numero on yhtä suuri kuin lapsisolmun luku.
Ershov-solmun numero, jossa on kaksi lasta, on: a) suurin lapsisolmujen lukumäärästä, jos lapsisolmujen Ershov-luvut ovat erilaiset; b) lapsisolmun lukumäärä kasvaa yhdellä, jos lapsisolmujen Ershov-luvut ovat samat.

Ershov - solmun numero edustaa vähimmäismäärää rekistereitä, jotka tarvitaan suorittamaan osalauseke, jonka juuri on tämä solmu. Ajatuksena on ensin suorittaa lapsilauseke suuremmalla Ershov-luvulla, sitten toinen lapsilauseke ja sitten operaatio juurissa.

Esimerkki

Harkitse ilmaisua . Merkitään tämän lausekkeen puun solmut (katso oikealla oleva kuva) Ershov-lukuja vastaavilla nimiöillä. Meillä on '+'-operaatio juuressa, vasemman ja oikean alipuun otsikot ovat 2, joten juuren nimi on 3, joten lausekkeen toteuttamiseen tarvitaan 3 rekisteriä. ${\näyttötyyli (ab)+e\times (c+d)}$

Jokainen viidestä lehdestä on merkitty "1" (ensimmäisen säännön mukaan). Säännön 3 mukaan alkion "b" solmut t1 ja t2 saavat tunnisteita, jotka ovat yhtä suuria kuin 2. Nyt solmulla t3 on lapsisolmuja, joilla on erilaiset tunnisteet, joten sille nimike on myös 2 (säännön 3 mukaan kohta "a"). Solmulla t4 on jälleen lapsia, joilla on samat tunnisteet, joten sen tunniste on yhtä suuri kuin 3 (sääntö 3, kohta "b").

Koodin luominen

Alla on rekursiivinen algoritmi konekoodin luomiseksi [2] . Algoritmilla on "kanta" rekistereille, eli rekistereitä käytetään solmulle, jonka Ershov-luku on k : ${\displaystyle R_{b},R_{b+1},\dots ,R_{b+k-1))$

Luodaksemme sisäisen solmun (ei lehden) konekoodin Ershov-luvulla k ja kahdella alisolmulla, joiden lukumäärä on yhtä suuri (yhtä kuin k-1 ), suoritamme:
- Luomme koodin oikealle lapsisolmulle, jossa on kanta , tulos sijoitetaan rekisteriin ; $b+1$ $R_{b+k-1}$
- Luomme koodin vasemmalle kantasolmulle , jonka tulos sijoitetaan rekisteriin ; $b$ ${\displaystyle R_{b+k-2))$
- Luo tiimi "Operaatio" ; ${\displaystyle R_{b+k-1},R_{b+k-2},R_{b+k-1))$
Tarkastellaan solmua, jonka tunniste on k , ja alisolmuilla on erilaiset tunnisteet. Tässä tapauksessa yhdellä lapsisolmuista on nimike k ja toisessa jokin alempi tunniste m . Toimi tällaiselle solmulle seuraavasti:
- Luomme koodin lapsisolmulle, jolla on suurempi Ershov-numero, käytä kantaa b , tulos sijoitetaan rekisteriin ; $R_{b+k-1}$
- Luomme koodin toiselle lapsisolmulle, käytä kantaa b , tulos sijoitetaan rekisteriin ; $R_{b+m-1}$
- Luomme komennon "Operation" tai "Operation" (riippuen siitä, missä solmu, jossa on suurempi määrä Ershovia, sijaitsee); ${\displaystyle R_{b+k-1},R_{b+m-2},R_{b+k-1))$ ${\displaystyle R_{b+k-1},R_{b+k-1},R_{b+m-1))$
Lehtisolmulle, jossa on operandi x , luomme Lataa-komennon . $R_{b},x$

Lausekkeen arviointi riittämättömällä määrällä rekistereitä

Jos lausekkeen juurisolmun Ershov-numero on suurempi kuin käytettävissä olevien rekisterien määrä, niin Ershov-lukua voidaan käyttää koodin luomiseen minimimäärällä latausta ja tallentamiseen toimintoja seuraavasti [3]

Sillä juuri tehdä

Luomme koodin lapsisolmulle, jolla on suurempi Ershov-numero;
Luomme komennon tallentaaksesi tuloksen muistiin;
Luomme koodin lapsisolmulle, jolla on pienempi Ershov-numero;
Luomme käskyn ladata tallennettu arvo rekisteriin;
Luomme komennon, joka suorittaa toiminnon juurissa.

Katso myös

Strahler-Philosophovin luku, minimimäärä rekistereitä, jotka vaaditaan lausekkeen suorittamiseen ilman ulkoista muistia
Verkko-Ullman-algoritmi , pohjimmiltaan sama käsite

Muistiinpanot

↑ Aho, Lam, Seti, Ullman, 2008 , s. 689-692.
↑ Aho, Lam, Seti, Ullman, 2008 , s. 690.
↑ Aho, Lam, Seti, Ullman, 2008 , s. 692-693.

Kirjallisuus

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. 8.10.1 Ershov-luvut // Kääntäjät (periaatteet, tekniikat ja työkalut). - Moskova, Pietari, Kiova: "Williams", 2008. - ISBN 978-5-8459-1349-4 .

Linkit

Carleton Universityn sivu optimaalisesta koodin luomisesta ja Ershov-numeroiden käytöstä .