Číslování hodnot - Value numbering

Číslování hodnot je technika určování, kdy jsou dva výpočty v programu ekvivalentní, a eliminace jednoho z nich pomocí optimalizace zachování sémantiky.

Globální číslování hodnot

Global value numbering (GVN) is a compiler optimization based on the static single assignment form (SSA) intermediate representation. Někdy pomáhá eliminovat nadbytečný kód, který běžná eliminace subexprese (CSE) neumožňuje. 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 místního číslování hodnot v tom, že mapování hodnot a čísel drží také přes hranice základních bloků a pro výpočet 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 := 3
x := 3
y := x + 4
z := w + 4

dobrá rutina GVN by přiřadila stejné číslo hodnoty wa xa stejné číslo hodnoty ya z. Například mapa by představovala optimální mapování hodnot a čísel pro tento blok. Pomocí těchto informací lze předchozí fragment kódu bezpečně transformovat na: 

w := 3
x := w
y := w + 4
z := y

V závislosti na kódu, který následuje po tomto fragmentu, může být šíření kopie schopno odebrat přiřazení do xa doz

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 × d
e := c
f := e × d

Bez šíření kopií, CSE by ne eliminovat recomputation přiřazené f, ale i špatná GVN algoritmus by měl objevit a odstranit tuto nadbytečnost.

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

Místní číslování hodnot (LVN) je optimalizace kompilátoru , jejímž cílem je najít více instancí ekvivalentních výrazů (tj. Výrazů, které přinášejí stejný výsledek) a nahradit je prvním výskytem. LVN je lokální optimalizace, což znamená, že na rozdíl od globálního číslování hodnot funguje současně na jednom základním bloku .

Čí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 is tagged as #1
b ← 5         b is tagged as #2
c ← a + b     c (#1 + #2) is tagged as #3
d ← 5         d is tagged as #2, the same as b
e ← a + d     e, being '#1 + #2' is tagged as #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římým použitím 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 pseudokód : 

a ← 1         a is tagged as #1
b ← 2         b is tagged as #2
c ← a + b     c is tagged as #3
b ← 3
d ← a + b     d is incorrectly tagged as #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ší. Tuto reprezentaci řeší použití reprezentace SSA.

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 + 2
b ← 2 + 1

Tento problém lze snadno vyřešit buď přidělením stejného čísla 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ů.

Optimalizátory číslování místních hodnot mohou také znát matematické identity. Za předpokladu, že „a“ je celé číslo, lze všem následujícím výrazům přiřadit stejnou hodnotu: 

b ← a + 0
c ← a * 1
d ← min(a, MAX_INT)
e ← max(a, a)
f ← a & 0xFF..FF       (assuming '&' denotes the bitwise operation)

Viz také

Reference

Další čtení