Wikipedysta:Wojciech mula/Alokacja rejestrów

Alokacja rejestrów - jeden z końcowych etapów kompilacji programu komputerowego (poprzedzającym wybór instrukcji), której celem jest odwzorowanie zmiennych przetwarzanych w programie na zawartość konkretnych rejestrów mikroprocesora. Kompilatory posługują się abstrakcyjnym modelem, w którym liczba zmiennych jest nieograniczona, stąd zachodzi konieczność przyporządkowania ich skończonej liczbie rejestrów docelowego procesora. Od jakości algorytmu alokacji zależy wydajność skompilowanego programu, natomiast złożoności tego algorytmu wpływa na szybkość kompilacji.

Kluczowym etapem alokacji rejestrów jest określenie czasu życia zmiennej (ang. liveness analysis), to znaczy znalezienie przez ile instrukcji programu zmienna jest używana, a więc jak długo rejestr ją przechowujący nie może zostać przeznaczony na inną zmienną. Jeśli jednak w danym punkcie programu liczba jednocześnie używanych zmiennych przekracza liczbę dostępnych rejestrów, wówczas kompilator musi jedną ze zmiennych zapisać w pamięci tymczasowej (ang. register spill), zwolniony rejestr przeznaczyć na inną zmienną i przy ponownym odwołaniu odczytać wartość z pamięci. Strategie wyboru rejestru do zwolnienia są różne, może to być np. zbyt rzadki dostęp do zmiennej lub bardzo długi czas życia. Niekiedy zamiast wprowadzania zmiennej kompilator decyduje o ponownym obliczeniu wartości zmiennej, jeśli byłoby to opłacalne (czasowo lub pamięciowo).

Algorytm alokacji rejestrów musi również uwzględniać fakt, że niektóre CPU mają niejednorodną architekturę rejestrową. Na przykład dzielenie na procesorach x86 wymaga by dzielna była zapisana w parze rejestrów EDX i EAX, chociaż inne operacje arytmetyczne i logiczne przyjmują argumenty z dowolnych rejestrów; z kolei procesory Itanium posiadają rejestr przeznaczony wyłącznie do odczytu, o wartości 0.

Zobacz również

• optymalizacja kodu wynikowego