Network-Ullman algoritmus

Network-Ullman algoritmus
Valaki után elnevezve Ravi Sethi [d] ésJeffrey Ullman
célja keresse meg egy kifejezés optimális fordítási sorrendjét
Adatstruktúra grafikon

A Network-Ullman algoritmus egy olyan algoritmus, amely absztrakt szintaxisfákat olyan gépi kódra fordít , amely a lehető legkevesebb regisztert használja . Az algoritmus nevét fejlesztőiről, Ravi Seti és Jeffrey Ullmanról kapta ,

Áttekintés

Az aritmetikai kifejezések kódjának generálásakor a fordítónak el kell döntenie, hogy melyik a legjobb módja a kifejezés lefordításának a használt utasítások száma, valamint az adott részfa kiértékeléséhez szükséges regiszterek száma szempontjából. Különösen abban az esetben, ha a szabad regiszterek száma kicsi, a végrehajtás sorrendje lehet fontos a generált kód hosszához, mivel az eltérő kiértékelési sorrend több-kevesebb köztes értékeket eredményezhet, amelyek kiürülnek a memóriába és majd helyreállították. A Network-Ullman algoritmus (más néven Network-Ullmann számozás ) rendelkezik azzal a tulajdonsággal, hogy olyan kódot állít elő, amely minimális számú utasítást, valamint minimális számú memóriahivatkozást igényel (feltételezve, hogy legalább a műveletek kommutatívak és asszociatívak , de a elosztási törvény , azaz nem hajtják végre). Megjegyzendő, hogy az algoritmus akkor is sikeres, ha sem kommutativitás , sem asszociativitás nem fordul elő a kifejezésben, ezért aritmetikai transzformációk nem alkalmazhatók. Az algoritmus nem használ általános részkifejezés-detektálást vagy általános irányított aciklikus gráfok explicit használatát fák helyett.

Egy egyszerű Net-Ullman algoritmus

Az egyszerű hálózat-Ullmann algoritmus a következőképpen működik ( a betöltés/tárolás architektúrához ):

  1. Az absztrakt szintaxisfa bejárása előre vagy hátra
    1. Bármely nem állandó levél csomóponthoz 1-et rendelünk (vagyis 1 regiszterre van szükségünk egy változó / mező / stb. tárolásához). Bármely konstans lap (a művelet jobb oldala - literálok, értékek) 0-t kap.
    2. Bármely n nem levél csomóponthoz annyi regiszter van hozzárendelve, hogy a megfelelő n részfa kiszámításához szükséges legyen . Ha a bal oldali részfában ( l ) szükséges regiszterek száma nem egyenlő a jobb oldali részfában ( r ) szükséges regiszterek számával, akkor az aktuális n csomópontban szükséges regiszterek száma max(l, r). Ha l == r , akkor az aktuális csomóponthoz szükséges regiszterek száma .
  2. Kódgenerálás
    1. Ha az n csomópont bal oldali részfájának kiszámításához szükséges regiszterek száma nagyobb, mint a jobb oldali részfa regisztereinek száma, akkor először a bal oldali részfa kerül kiszámításra (mert egy extra regiszterre lehet szükség a jobb oldali részfa eredményének tárolásához, átfedi a bal oldali részfa regisztere). Ha a jobb oldali részfa több regisztert igényel, mint a bal, akkor először a jobb oldali fa kerül kiértékelésre. Ha mindkét részfa azonos számú regisztert igényel, akkor a végrehajtás sorrendje nem számít.

Példa

Egy aritmetikai kifejezésnél az absztrakt szintaxisfa így néz ki:

= / \ a* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

Az algoritmus végrehajtásához csak a számtani kifejezést kell ellenőriznünk , pl. csak a '=' cél megfelelő részfáját kell megnéznünk:

* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfg

Most úgy kezdjük a fát, hogy hozzárendeljük az egyes részfák kiértékeléséhez szükséges regiszterek számát (megjegyezzük, hogy a kifejezés utolsó tagja egy állandó):

* 2 / \ / \ + 2 + 1 / \ / \ / d 1 3 0 + 1 * 1 / \ / \ b 1 c 0 f 1 g 0

Ebből a fából láthatja, hogy 2 regiszterre van szükségünk a '*' bal oldali részfájának kiszámításához, de csak egy regiszterre van szükségünk a jobb oldali részfa kiszámításához. A 'c' és 'g' csomópontoknak nincs szükségük regiszterekre a következő okok miatt: Ha T a fa levele, akkor a T kiértékelendő regiszterek száma 1 vagy 0 attól függően, hogy T a bal vagy a jobb részfában van-e. (mert az olyan műveletek, mint az R1, A hozzáadása, közvetlenül feldolgozhatják A megfelelő komponensét anélkül, hogy regisztrálnák azt). Ezért kezdjük a bal oldali részfa végrehajtásával, mivel olyan helyzetbe kerülhetünk, hogy csak két regiszterünk van a teljes kifejezés kiértékeléséhez. Ha először a jobb oldali részfát számítjuk ki (amihez csak egy regiszter szükséges), akkor a jobb oldali részfa eredményét kellene tárolnunk, miközben a bal oldali részfát (amelynek még 2 regiszterre van szüksége), így 3 regiszterre van szükség. A bal oldali részfa kiértékeléséhez két regiszterre van szükség, de az eredmény egy regiszterben tárolható, és mivel a jobb oldali részfa kiértékeléséhez egy regiszter szükséges, a kifejezés csak két regiszterrel értékelhető ki.

Továbbfejlesztett Net-Ullman algoritmus

A Network-Ullman algoritmus továbbfejlesztett változatában az aritmetikai kifejezéseket először a használt operátorok aritmetikai tulajdonságainak felhasználásával konvertálják.

Lásd még

Jegyzetek

Irodalom

Linkek