Numeracja wartości

Numerowanie wartości to technika określania, kiedy dwa obliczenia w programie są równoważne i eliminowania jednego z nich za pomocą optymalizacji zachowującej semantykę .

Globalna numeracja wartości

Globalne numerowanie wartości (GVN) to optymalizacja kompilatora oparta na statycznej reprezentacji pośredniej formularza pojedynczego przypisania (SSA). Czasami pomaga wyeliminować nadmiarowy kod , którego nie eliminuje wspólna eliminacja podwyrażeń (CSE). Jednocześnie jednak CSE może wyeliminować kod, którego nie robi GVN, więc oba są często spotykane w nowoczesnych kompilatorach. Globalne numerowanie wartości różni się od lokalnego numerowania wartości tym, że odwzorowania wartości i liczb obejmują również podstawowe granice bloków, a do obliczania odwzorowań używane są różne algorytmy.

Globalne numerowanie wartości polega na przypisywaniu numeru wartości do zmiennych i wyrażeń. Ten sam numer wartości jest przypisywany tym zmiennym i wyrażeniom, które są równoważne w sposób dający się udowodnić. Na przykład w poniższym kodzie:

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

dobra procedura GVN przypisze ten sam numer wartości do w i x oraz ten sam numer wartości do y i z . Na przykład mapa ${\ Displaystyle \ lewo \ {{w} \ mapsto 1, {x} \ mapsto 1, {y} \ mapsto 2, {z}\mapsto 2\right\}}$ stanowiłoby optymalne odwzorowanie wartości na liczbę dla tego bloku. Korzystając z tych informacji, poprzedni fragment kodu można bezpiecznie przekształcić w:

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

W zależności od kodu następującego po tym fragmencie, propagacja kopii może być w stanie usunąć przypisania do x i do z .

Powodem, dla którego GVN jest czasami potężniejszy niż CSE, jest fakt, że CSE dopasowuje leksykalnie identyczne wyrażenia, podczas gdy GVN próbuje określić podstawową równoważność. Na przykład w kodzie:

za := do × re mi := do fa := mi × re

Bez propagacji kopii CSE nie wyeliminowałoby ponownego obliczania przypisanego do f , ale nawet kiepski algorytm GVN powinien wykryć i wyeliminować tę nadmiarowość.

Formularz SSA jest wymagany do wykonania GVN, aby fałszywe ${\ Displaystyle \ lewo \ {{\ tekst {nazwa zmiennej}} \ mapsto {\ tekst {liczba wartości}} \ prawo \}} odwzorowania nie$ były Utworzony.

Lokalne numerowanie wartości

Lokalne numerowanie wartości (LVN) to optymalizacja kompilatora , której celem jest znalezienie wielu wystąpień równoważnych wyrażeń (tj. wyrażeń dających ten sam wynik) i zastąpienie ich pierwszym wystąpieniem. LVN jest lokalną optymalizacją, co oznacza, że ​​w przeciwieństwie do globalnej numeracji wartości , działa w danym momencie na jednym podstawowym bloku .

Lokalne numerowanie wartości polega na przypisywaniu każdej operacji unikalnego numeru i zapamiętywaniu tych powiązań. Kolejne instrukcje są następnie wyszukiwane iw przypadku, gdy identyczna instrukcja została już zarejestrowana, zastępowane wynikiem poprzedniej instrukcji. Na przykład:

a ← 4 a jest oznaczone jako #1 b ← 5 b jest oznaczone jako #2 c ← a + bc (#1 + #2) jest oznaczone jako #3 d ← 5 d jest oznaczone jako #2, to samo co b e ← a + de, bycie „#1 + #2” jest oznaczone jako #3

Przypisując liczby do instrukcji, porównywanie duplikatów zamienia się w proste porównania liczb całkowitych. W tym konkretnym przykładzie c i e mają przypisany ten sam numer (#3), sygnalizując w ten sposób kompilatorowi, że wszelkie odniesienia do e można po prostu zastąpić jedynkami do c .

Trudności i rozszerzenia

Problemy, gdy nie używasz SSA

Naiwna implementacja może próbować przeprowadzić optymalizację, używając bezpośrednio nazw zmiennych zamiast liczb. Jednak to podejście nie działa, gdy wartości zmiennych mogą się zmieniać. Rozważ pseudokod :

a ← 1 a jest oznaczone jako #1 b ← 2 b jest oznaczone jako #2 c ← a + bc jest oznaczone jako #3 b ← 3 d ← a + bd jest oznaczone nieprawidłowo jako #3

W tym scenariuszu d jest niepoprawnie przypisana liczba 3, ponieważ argumenty pasują do argumentów c . Jest to jednak niepoprawne, ponieważ b zmieniło wartość z 2 na 3, przez co rzeczywiste wyniki są inne. Użycie reprezentacji SSA rozwiązuje tę rozbieżność.

Korzystanie z tożsamości matematycznych

Prosta implementacja może również nie być w stanie przechwycić wszystkich równoważnych wyrażeń, nawet jeśli różnią się one tylko kolejnością operandów. W poniższym przykładzie a i b można przypisać ten sam numer:

za ← 1 + 2 b ← 2 + 1

Ten problem można łatwo rozwiązać, przypisując tę ​​samą liczbę obu przypadkom (tj. a + b i b + a są rejestrowane z tym samym numerem) lub sortując operandy przed sprawdzeniem odpowiedników.

Lokalne optymalizatory numeracji wartości mogą również być świadome tożsamości matematycznych. Zakładając że a jest liczbą całkowitą , wszystkim następującym wyrażeniom można przypisać tę samą wartość:

 b ← a + 0 c ← a * 1 d ← min(a, MAX_INT) e ← max(a, a) f ← a & 0xFF..FF (zakładając, że „&” oznacza bitowe  AND  ) 

Zobacz też

• Częściowa eliminacja redundancji
• Kompilator optymalizujący
• Eliminacja wspólnych podwyrażeń

Dalsza lektura

•    Kildall, Gary Arlen (1973). „Ujednolicone podejście do globalnej optymalizacji programów” . Materiały z 1. dorocznego sympozjum ACM SIGACT-SIGPLAN na temat zasad języków programowania . Popl '73: 194–206. doi : 10.1145/512927.512945 . hdl : 10945/42162 . ISBN 9781450373494 . S2CID 10219496 . Źródło 2006-11-20 . [1]
• Alpern, Bowen, Wegman, Mark N. i Zadeck, F. Kenneth. „Detecting Equality of Variables in Programs.”, Zapis konferencji z piętnastego dorocznego sympozjum ACM na temat zasad języków programowania ( POPL ), ACM Press, San Diego, Kalifornia, USA, styczeń 1988, strony 1–11.
• L. Taylor Simpson, „Eliminacja redundancji oparta na wartości”. Raport techniczny 96-308, Wydział Informatyki, Uniwersytet Rice, 1996. (praca doktorska autora)
•   Muchnick, Steven Stanley (1997). Zaawansowany projekt i implementacja kompilatora . Wydawcy Morgan Kaufmann . ISBN 978-1-55860-320-2 .
• Briggs, P.; Cooper, Keith D .; Simpson, L. Taylor (1997). „Numerowanie wartości”. Oprogramowanie — praktyka i doświadczenie . 27 (6): 701–724.