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.

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).