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 ,
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.
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 ):
Egy aritmetikai kifejezésnél az absztrakt szintaxisfa így néz ki:
= / \ a* / \ / \ ++ / \ / \ /\d3 + * / \ / \ bcfgAz 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 + * / \ / \ bcfgMost ú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 0Ebbő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.
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.