Single Static Assignment
Single Static Assignment to postać programu używana przez kompilatory w trakcie optymalizacji, w której każdej zmiennej wartość przypisuje się tylko raz.
Np. dla programu:
a = read(); b = a + 2; a = a + 1; f(a, b);
Postać SSA to:
a1 = read(); b1 = a1 + 2; a2 = a1 + 1; f(a2, b1);
Jeśli wartość zmiennej w danym użyciu może pochodzić z kilku różnych przypisań, używa się specjalnej funkcji Φ.
Dla:
a = 2; if (b > 0) a = 4; f(a);
Postacią SSA jest:
a1 = 2; if (b > 0) a2 = 4; a3 = Φ(a1, a2); f(a3);
Postać SSA ułatwia wiele rodzajów optymalizacji. Najprostszą jest propagacja stałych – jeśli wiemy, że do danej zmiennej SSA została przypisana pewna wartość, możemy zastąpić wszystkie użycia tej zmiennej przez daną stałą, nawet jeśli w oryginalnym programie zmienna ta była używana też do innych celów.
Więzy
Można też na tej postaci dokonywać łatwych wyliczeń więzów. Np. jeśli wiemy, że w programie jest wykonywany test czy a3 > 0
, i że a3 = Φ(a1, a2)
, możemy sprawdzić czy test ten jest spełniony nawet bez znajomości dokładnej wartości a3
.
Np. jeśli mamy kod tablicujący wartości funkcji sinus:
int rozmiar = 100; float tab[rozmiar];
i = 0; while (i < rozmiar) { tab[i] = sin(i * alpha); i = i + 1; }
Bezpieczeństwo wymaga, żeby wprowadzić testy, czy używany indeks jest poprawny (powinien to robić automatycznie kompilator; większość kompilatorów C/C++ tego nie robi, choć robią to kompilatory wielu innych języków):
int rozmiar = 100; float tab[rozmiar];
i = 0; while (i < rozmiar) { if (i < 0) raise InvalidArrayIndex; if (i >= rozmiar) raise InvalidArrayIndex; tab[i] = sin(i * alpha); i = i + 1; }
Po zmianie formy na SSA (blok pre-while
oznacza instrukcje wykonywane przed porównaniem, blok taki nie występuje w kodzie źródłowym, jednak kompilator musi go wygenerować, żeby umieścić tam wyliczenia i wywołania funkcji występujące w złożonych warunkach):
int rozmiar = 100; float tab[rozmiar];
i1 = 0; pre-while { i3 = Φ(i1, i2); } while (i3 < rozmiar) { if (i3 < 0) raise InvalidArrayIndex; if (i3 >= rozmiar) raise InvalidArrayIndex; tab[i] = sin(i3 * alpha); i2 = i3 + 1; }
To że i3 >= rozmiar
jest fałszywe kompilator wie z warunku, jaki występuje na początku bloku. Jednak i
musi w trakcie wykonywania programu przynajmniej raz złamać to założenie – osiąga przecież wartość rozmiar
żeby opuścić pętlę! Bez SSA trudniej byłoby rozważać takie przypadki. Podobnie kompilator może stwierdzić, że i1 >= 0
, i że jeśli i3 >= 0
, to i2 = i3 + 1 >= 0
(jeśli zajmie się też rozpatrywaniem kwestii przepełnienia).