Ershov szám

Az Ershov-számokat a kódoptimalizálás során használják, hogy minimalizálják a kifejezés által használt regiszterek számát . Használhatók regiszter-optimális módszerekben, amikor csak egy kifejezés van egy kódblokkban. Ha az E = E 1 művelet E 2 kifejezést adjuk , akkor a cél az, hogy a kódot úgy állítsuk elő, hogy a felhasznált regiszterek összlétszáma minimális legyen, illetve nem elegendő számú elérhető regiszter esetén minimálisra csökkenjen az ideiglenes regiszterek száma. változók (azaz a memória szavai).

Egy adott kifejezésfa csomópontjának Ershov-számát a következőképpen definiáljuk [1] :

Minden levél értéke 1.
Egy gyermekcsomóponttal rendelkező belső csomópont Ershov-száma megegyezik egy gyermekcsomópont számával.
A két gyermekes Ershov csomópont száma: a) a gyermekcsomópontok száma közül a legnagyobb, ha az utódcsomópontok Ershov-számai eltérőek; b) a gyermekcsomópont száma 1-gyel nőtt, ha a gyermek csomópontok Ershov-számai megegyeznek.

Az Ershov csomópontszám a regiszterek minimális számát jelenti egy olyan részkifejezés végrehajtásához, amelynek gyökere ez a csomópont. Az ötlet az, hogy először a gyermek kifejezést hajtsuk végre egy nagyobb Ershov-számmal, majd a második gyermek kifejezést, majd a műveletet a gyökérben.

Példa

Nézzük a kifejezést . Jelöljük meg ennek a kifejezésnek a fa csomópontjait (lásd a jobb oldali ábrát) az Ershov-számokkal megegyező címkékkel. A gyökérben van egy '+' művelet, a bal és a jobb részfa címkéje 2, így a gyökér címkéje 3, tehát 3 regiszter szükséges a kifejezés megvalósításához. ${\megjelenítési stílus (ab)+e\times (c+d)}$

Mind az öt levél "1" címkével van ellátva (az 1. szabály szerint). A 3. szabály szerint a "b" elem t1 és t2 csomópontjai 2-vel egyenlő címkéket kapnak. Most a t3 csomópontnak vannak gyermekcsomópontjai különböző címkékkel, így számára a címke is 2 lesz (a 3. szabály szerint az "a" elem). A t4 csomópontnak ismét azonos címkéi vannak gyermekei, így a címke 3 lesz (3. szabály, "b" elem).

Kódgenerálás

Az alábbiakban egy rekurzív algoritmus található a gépi kód generálására [2] . Az algoritmusnak van egy „alapja” a regiszterekhez, vagyis a regisztereket egy k Ershov-számú csomóponthoz használják : ${\displaystyle R_{b},R_{b+1},\dots ,R_{b+k-1))$

Egy belső csomópont (nem levél) gépi kódjának generálásához k Ershov számmal és két azonos számú gyermekcsomóponttal (egyenlő k-1 ), a következőt hajtjuk végre:
- A megfelelő gyermek csomóponthoz kódot készítünk bázissal , az eredmény bekerül a regiszterbe ; $b+1$ $R_{b+k-1}$
- A bal oldali gyermekcsomóponthoz kódot készítünk bázissal , az eredmény bekerül a regiszterbe ; $b$ ${\displaystyle R_{b+k-2))$
- Hozzon létre egy csapatot "Művelet" ; ${\displaystyle R_{b+k-1},R_{b+k-2},R_{b+k-1))$
Legyen egy k címkével rendelkező csomópont, és a gyermek csomópontok különböző címkékkel rendelkeznek. Ebben az esetben az egyik gyermekcsomópont k címkével , a másik pedig valamivel alacsonyabb m címkével rendelkezik . Egy ilyen csomóponthoz tegye a következőket:
- Egy nagyobb Ershov-számú gyermekcsomóponthoz készítünk kódot, használjuk a b bázist , az eredmény a regiszterbe kerül ; $R_{b+k-1}$
- Kódot készítünk egy másik gyermek csomóponthoz, használd a b bázist , az eredmény a regiszterbe kerül ; $R_{b+m-1}$
- Létrehozzuk a "Művelet" vagy "Művelet" parancsot (attól függően, hogy hol található a nagyobb számú Ershov csomópont); ${\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))$
Az x operandust tartalmazó levélcsomóponthoz létrehozunk egy Betöltés parancsot . $R_{b},x$

Kifejezés kiértékelés nem elegendő számú regiszterrel

Ha a kifejezés gyökércsomópontjának Ershov-száma nagyobb, mint a rendelkezésre álló regiszterek száma, akkor az Ershov-számmal minimális betöltési számú kód generálható és mentési műveletek végezhetők az alábbiak szerint [3]

A gyökér számára

Létrehozunk egy kódot egy nagyobb Ershov-számú gyermekcsomóponthoz;
Létrehozunk egy parancsot az eredmény memóriába mentéséhez;
Létrehozunk egy kódot egy kisebb Ershov-számú gyermekcsomóponthoz;
Utasítást készítünk a tárolt érték regiszterbe való betöltésére;
Létrehozunk egy parancsot, amely a gyökérben hajtja végre a műveletet.

Lásd még

Strahler-Philosophov szám, a regiszterek minimális száma, amely egy kifejezés végrehajtásához külső memória nélkül
Network-Ullman algoritmus , lényegében ugyanaz a fogalom

Jegyzetek

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

Irodalom

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. 8.10.1 Ershov-számok // Fordítóprogramok (elvek, technológiák és eszközök). - Moszkva, Szentpétervár, Kijev: "Williams", 2008. - ISBN 978-5-8459-1349-4 .

Linkek

A Carleton Egyetem oldala az optimális kódgenerálásról és az Ershov-számok használatáról .