Algoritmus Network-Ullman

Algoritmus Network-Ullman
Pojmenoval podle Ravi Sethi [d] aJeffrey Ullman
účel hledat optimální pořadí překladu výrazu
Datová struktura graf

Algoritmus Network-Ullman je algoritmus pro převod abstraktních syntaktických stromů do strojového kódu , který používá co nejméně registrů . Algoritmus je pojmenován po jeho vývojářích Ravi Seti a Jeffrey Ullman ,

Přehled

Při generování kódu pro aritmetické výrazy se musí kompilátor rozhodnout, jaký je nejlepší způsob překladu výrazu z hlediska počtu použitých instrukcí a také počtu registrů potřebných k vyhodnocení konkrétního podstromu. Zejména v případě, kdy je počet volných registrů malý, může být pořadí provádění důležité pro délku generovaného kódu, protože jiné pořadí vyhodnocení může vést k víceméně mezilehlým hodnotám, které se vymažou do paměti a poté obnovena. Algoritmus Network-Ullman (také známý jako Network-Ullmann číslování ) má tu vlastnost, že vytváří kód, který vyžaduje minimální počet instrukcí a také minimální počet referencí paměti (za předpokladu, že alespoň operace jsou komutativní a asociativní , ale distributivní právo , tj . není vykonáváno). Všimněte si, že algoritmus uspěje, i když se ve výrazu nevyskytuje ani komutativnost ani asociativita , a proto nelze použít aritmetické transformace. Algoritmus také nepoužívá společnou detekci podvýrazů nebo explicitní použití obecně orientovaných acyklických grafů namísto stromů.

Jednoduchý Net-Ullmanův algoritmus

Algoritmus Simple Network-Ullmann funguje následovně (pro architekturu load/store ):

  1. Procházení abstraktního stromu syntaxe vpřed nebo vzad
    1. Každému nekonstantnímu listovému uzlu přiřadíme 1 (to znamená, že potřebujeme 1 registr pro uložení proměnné / pole / atd.). Libovolnému listu konstant (pravá strana operace - literály, hodnoty) bude přiřazena 0.
    2. Libovolnému nelistovému uzlu n je přiřazen počet registrů potřebných k výpočtu odpovídajícího podstromu n . Pokud se počet registrů potřebných v levém podstromu ( l ) nerovná počtu registrů potřebných v pravém podstromu ( r ), počet registrů potřebných v aktuálním uzlu n je max(l, r). Pokud l == r , pak počet registrů požadovaných pro aktuální uzel je .
  2. Generování kódu
    1. Pokud je počet registrů potřebných k výpočtu levého podstromu uzlu n větší než počet registrů pro pravý podstrom, pak se nejprve vypočítá levý podstrom (protože může být zapotřebí jeden registr navíc k uložení výsledku pravého podstromu, překrytý registrem levého podstromu). Pokud pravý podstrom vyžaduje více registrů než levý, pak se nejprve vyhodnotí pravý strom. Pokud oba podstromy vyžadují stejný počet registrů, pak na pořadí provádění nezáleží.

Příklad

Pro aritmetický výraz vypadá abstraktní strom syntaxe takto:

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

K provedení algoritmu potřebujeme pouze zkontrolovat aritmetický výraz , tj. stačí se podívat na správný podstrom cíle '=':

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

Nyní zahájíme procházku stromem přiřazením počtu registrů potřebných k vyhodnocení každého podstromu (všimněte si, že poslední výraz ve výrazu je konstanta):

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

Z tohoto stromu můžete vidět, že pro výpočet levého podstromu '*' potřebujeme 2 registry, ale pro výpočet pravého podstromu potřebujeme pouze jeden registr. Uzly 'c' a 'g' nepotřebují registry z následujících důvodů: Je-li T listem stromu, pak počet registrů pro vyhodnocení T je buď 1 nebo 0 v závislosti na tom, zda je T v levém nebo pravém podstromu. (protože operace jako přidání R1, A mohou zpracovat správnou složku A přímo bez její registrace). Proto bychom měli začít provedením levého podstromu, protože se můžeme dostat do situace, kdy máme k vyhodnocení celého výrazu pouze dva registry. Pokud bychom nejprve počítali pravý podstrom (který vyžaduje pouze jeden registr), museli bychom uložit výsledek pravého podstromu při výpočtu levého podstromu (který stále potřebuje 2 registry), takže jsou potřeba 3 registry. Vyhodnocení levého podstromu vyžaduje dva registry, ale výsledek lze uložit do jednoho registru, a protože pravý podstrom vyžaduje k vyhodnocení jeden registr, lze výraz vyhodnotit pouze se dvěma registry.

Vylepšený Net-Ullmanův algoritmus

Ve vylepšené verzi algoritmu Network-Ullman jsou aritmetické výrazy nejprve převedeny pomocí aritmetických vlastností použitých operátorů.

Viz také

Poznámky

Literatura

Odkazy