Číslování hodnot - Value numbering
Číslování hodnot je technika určování, kdy dva výpočty v programu jsou ekvivalentní a eliminují jeden z nich sémantikou zachovávající optimalizaci.
Globální číslování hodnot
Globální číslování hodnot (GVN) je a optimalizace kompilátoru založeno na statický jednotný formulář přiřazení (SSA) střední zastoupení. Někdy pomáhá eliminovat nadbytečný kód že běžná eliminace subexprese (CSE) ne. Zároveň však CSE může eliminovat kód, který GVN nemá, takže oba se často nacházejí v moderních kompilátorech. Globální číslování hodnot se liší od číslování místních hodnot v tom, že mapování hodnot a čísel platí i přes hranice základních bloků a k výpočtu mapování se používají různé algoritmy.
Globální číslování hodnot funguje tak, že se proměnným a výrazům přiřadí číslo hodnoty. Stejné číslo hodnoty je přiřazeno těm proměnným a výrazům, které jsou prokazatelně ekvivalentní. Například v následujícím kódu:
w: = 3x: = 3y: = x + 4z: = w + 4
dobrá rutina GVN by přiřadila stejné číslo hodnoty w a Xa stejné číslo hodnoty do y a z. Například mapa by představovalo optimální mapování hodnot a čísel pro tento blok.Pomocí těchto informací může být předchozí fragment kódu bezpečně transformován na:
![[{w} mapsto 1, {x} mapsto 1, {y} mapsto 2, {z} mapsto 2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/98abaf785e047522405142cc103463672b37289a)
w: = 3x: = wy: = w + 4z: = y
V závislosti na kódu, který následuje po tomto fragmentu, šíření kopie může být schopen odebrat přiřazení uživateli X a do z
Důvod, že GVN je někdy silnější než CSE, pochází ze skutečnosti, že CSE odpovídá lexikálně identickým výrazům, zatímco GVN se pokouší určit základní ekvivalenci. Například v kódu:
a: = c × de: = cf: = e × d
Bez šíření kopií by CSE ne eliminovat přidělenou přepočet F, ale i špatný algoritmus GVN by měl tuto redundanci objevit a eliminovat.
K provádění GVN je vyžadován formulář SSA, aby se nevytvářelo falešné mapování {název proměnné → název hodnoty}.
Místní číslování hodnot
Číslování místních hodnot (LVN) je a optimalizace kompilátoru jehož cílem je najít více instancí ekvivalentních výrazů (tj. výrazů, které vedou ke stejnému výsledku) a nahradit je prvním výskytem. LVN je lokální optimalizace, což znamená, že na rozdíl od globální číslování hodnot funguje na jediném základní blok včas.
Číslování místních hodnot funguje tak, že každé operaci přiřadíte jedinečné číslo a zapamatujete si tato přidružení. Následné instrukce jsou poté vyhledány a v případě, že již byla zaregistrována identická instrukce, nahrazena výsledkem předchozí instrukce. Například:
a ← 4 a je označen jako # 1b ← 5 b je označen jako # 2c ← a + bc (# 1 + # 2) je označen jako # 3d ← 5 d je označen jako # 2, stejně jako být ← a + de , být '# 1 + # 2' je označeno jako # 3
Přiřazením čísel k instrukcím se porovnání pro duplikáty změní na jednoduché celočíselné srovnání. V tomto konkrétním příkladu je „c“ a „e“ přiřazeno stejné číslo (# 3), což signalizuje kompilátoru, že jakékoli odkazy na e mohou být jednoduše nahrazeny odkazy na c.
Potíže a rozšíření
Naivní implementace se může pokusit provést optimalizaci přímo pomocí názvů proměnných místo čísel. Tento přístup však nefunguje, když se hodnoty proměnných mohou změnit. Zvažte pseudo kód:
a ← 1 a je označen jako # 1b ← 2 b je označen jako # 2c ← a + b c je označen jako # 3b ← 3d ← a + b d je nesprávně označen jako # 3
V tomto scénáři je „d“ nesprávně přiřazeno číslo 3, protože argumenty odpovídají argumentům „c“. To je však nesprávné, protože „b“ změnilo hodnotu z 2 na 3, takže se skutečné výsledky liší.
Jednoduchá implementace také nemusí být schopna zachytit všechny ekvivalentní výrazy, i když se liší pouze podle pořadí jejich operandů. V následujícím příkladu lze „a“ a „b“ přiřadit stejné číslo:
a ← 1 + 2b ← 2 + 1
Tento problém lze snadno vyřešit buď přiřazením stejného čísla k oběma případům (tj. „A + b“ a „b + a“ jsou oba zaznamenány se stejným číslem) nebo tříděním operandů před kontrolou ekvivalentů.[1]
Optimalizátoři číslování místních hodnot si také mohou být vědomi matematických identit. Za předpokladu, že „a“ je celé číslo, lze všem následujícím výrazům přiřadit stejnou hodnotu:[2]
b ← a + 0c ← a * 1d ← min (a, MAX_INT) e ← max (a, a) f ← a & 0xFF..FF (za předpokladu, že '&' označuje bitový provoz )
Viz také
Reference
- ^ Cooper, Keith D .; Torczon, Linda. „Terminologie, zásady a obavy (s příklady z místního číslování hodnot)“. elsevier. Citováno 15. května 2017.
- ^ Cooper, Keith D .; Torczon, Linda. „Místní optimalizace: číslování hodnot“ (PDF). Rice University. Citováno 15. května 2017.
Další čtení
- Kildall, Gary Arlen (1973). „Jednotný přístup k globální optimalizaci programu“. Sborník z 1. ročníku sympozia ACM SIGACT-SIGPLAN o zásadách programovacích jazyků. Popl '73: 194–206. doi:10.1145/512927.512945. hdl:10945/42162. Citováno 2006-11-20. [1]
- Alpern, Bowen, Wegman, Mark N. a Zadeck, F. Kenneth. "Detekce rovnosti proměnných v programech.", Záznam z konference patnáctého výročního sympozia ACM o zásadách programovacích jazyků (POPL ), ACM Press, San Diego, CA, USA, leden 1988, strany 1–11.
- L. Taylor Simpson, „Odstranění nadbytečnosti založené na hodnotě“. Technical Report 96-308, Computer Science Department, Rice University, 1996. (autorská disertační práce)
- Muchnick, Steven Stanley (1997). Pokročilý návrh a implementace kompilátoru. Nakladatelé Morgan Kaufmann. ISBN 978-1-55860-320-2.
- Briggs, P .; Cooper, Keith D.; Simpson, L. Taylor (1997). "Číslování hodnot". Softwarová praxe a zkušenosti. 27 (6): 701–724.