Ershovo číslo

Ershova čísla se používají při optimalizaci kódu , aby se minimalizoval počet registrů používaných výrazem . Mohou být použity v metodách optimálních pro registr, když je v bloku kódu pouze jeden výraz. Vzhledem k výrazu E = E 1 operace E 2 je pak cílem vygenerovat kód tak, aby se minimalizoval celkový počet použitých registrů a v případě nedostatečného počtu dostupných registrů minimalizoval počet dočasných registrů. proměnné (tedy slova paměti).

Ershovovo číslo n uzlu daného stromu výrazů je definováno takto [1] :

Všechny listy mají hodnotu 1.
Ershovovo číslo vnitřního uzlu s jedním podřízeným uzlem se rovná číslu podřízeného uzlu.
Číslo Ershovova uzlu se dvěma dětmi je: a) největší z počtu podřízených uzlů, pokud jsou Ershova čísla podřízených uzlů různá; b) počet podřízených uzlů zvýšený o 1, pokud jsou Ershova čísla podřízených uzlů stejná.

Číslo Ershovova uzlu představuje minimální počet registrů potřebných k provedení podvýrazu, jehož kořenem je tento uzel. Cílem je nejprve provést podřízený výraz s větším Ershovým číslem, poté druhý podřízený výraz a poté operaci v kořenu.

Příklad

Podívejme se na výraz . Označme uzly stromu (viz obrázek vpravo) tohoto výrazu štítky rovnými Ershovovým číslům. V kořeni máme operaci '+', popisky levého a pravého podstromu jsou 2, takže označení kořene je 3, takže k implementaci výrazu jsou potřeba 3 registry. $(ab)+e\times (c+d)$

Každý z pěti listů je označen „1“ (podle 1. pravidla). Podle pravidla 3 dostanou uzly t1 a t2 položky "b" štítky rovné 2. Nyní má uzel t3 podřízené uzly s různými štítky, takže pro něj bude štítek také 2 (podle pravidla 3 položka "a"). Uzel t4 má opět potomky se stejnými štítky, takže štítek pro něj bude roven 3 (pravidlo 3, položka „b“).

Generování kódu

Níže je uveden rekurzivní algoritmus pro generování strojového kódu [2] . Algoritmus má „základ“ pro registry, to znamená , že registry budou použity pro uzel s Ershovovým číslem k : ${\displaystyle R_{b},R_{b+1},\dots ,R_{b+k-1))$

Abychom vygenerovali strojový kód interního uzlu (nikoli listu) s Ershovovým číslem k a dvěma podřízenými uzly se stejnými čísly (rovnými k-1 ), provedeme:
- Vytvoříme kód pro správný podřízený uzel se základnou , výsledek bude umístěn do registru ; $b+1$ $R_{b+k-1}$
- Vytvoříme kód pro levý podřízený uzel s bází , výsledek bude umístěn do registru ; $b$ ${\displaystyle R_{b+k-2))$
- Vytvořte tým "Operace" ; ${\displaystyle R_{b+k-1},R_{b+k-2},R_{b+k-1))$
Nechť je uvažován uzel s označením k a podřízené uzly mají různá označení. V tomto případě má jeden z podřízených uzlů označení k a druhý nějaký nižší štítek m . Pro takový uzel proveďte následující:
- Vytvoříme kód pro podřízený uzel s větším Ershovým číslem, použijeme základ b , výsledek bude umístěn do registru ; $R_{b+k-1}$
- Vytvoříme kód pro další podřízený uzel, použijeme základ b , výsledek bude umístěn do registru ; $R_{b+m-1}$
- Vytvoříme příkaz "Operace" nebo "Operace" (podle toho, kde se nachází uzel s větším počtem Ershov); ${\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))$
Pro listový uzel s operandem x vytvoříme příkaz Načíst . $R_{b},x$

Vyhodnocení výrazu s nedostatečným počtem registrů

Pokud je Ershovovo číslo kořenového uzlu výrazu větší než dostupný počet registrů, lze Ershovo číslo použít ke generování kódu s minimálním počtem operací načítání a ukládání následovně [3]

Pro kořen udělat

Vytvoříme kód pro podřízený uzel s větším Ershovovým číslem;
Vytvoříme příkaz pro uložení výsledku do paměti;
Vytvoříme kód pro podřízený uzel s menším Ershovým číslem;
Vytvoříme instrukci pro načtení uložené hodnoty do registru;
Vytvoříme příkaz, který provede operaci v rootu.

Viz také

Strahlerovo-Philosophovo číslo, minimální počet registrů potřebných k provedení výrazu bez externí paměti
Algoritmus Network-Ullman , v podstatě stejný koncept

Poznámky

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

Literatura

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. 8.10.1 Ershova čísla // Kompilátory (principy, technologie a nástroje). - Moskva, Petrohrad, Kyjev: "Williams", 2008. - ISBN 978-5-8459-1349-4 .

Odkazy

Stránka Carleton University o optimálním generování kódu a používání Ershovových čísel .