Teoretyczna minimalna liczba rejestrów dla nowoczesnego komputera?

Podczas studiów licencjackich wziąłem kurs na kompilatory, w którym napisaliśmy kompilator, który kompiluje programy źródłowe w zabawnym języku podobnym do języka Java z językiem montażu zabawek (dla którego mieliśmy tłumacza). W projekcie przyjęliśmy pewne założenia dotyczące maszyny docelowej ściśle związane z „prawdziwymi” natywnymi plikami wykonywalnymi, w tym:

• stos czasu wykonywania, śledzony przez rejestr dedykowanego wskaźnika stosu („SP”)
• sterta do dynamicznego przydzielania obiektów, śledzona przez dedykowany rejestr wskaźnika sterty („HP”)
• dedykowany rejestr licznika programów („PC”)
• maszyna docelowa ma 16 rejestrów
• operacje na danych (w przeciwieństwie do np. skoków) są operacjami typu rejestr-rejestr

Kiedy dotarliśmy do jednostki, wykorzystującej przydział rejestrów jako optymalizację, zastanawiałem się: jaka jest teoretyczna minimalna liczba rejestrów dla takiej maszyny? Z naszych założeń widać, że w naszym kompilatorze wykorzystaliśmy pięć rejestrów (SP, HP, PC oraz dwa do wykorzystania jako pamięć do operacji binarnych). Podczas gdy optymalizacje, takie jak alokacja rejestrów, z pewnością mogą korzystać z większej liczby rejestrów, czy istnieje sposób na uzyskanie mniejszej liczby przy jednoczesnym zachowaniu struktur takich jak stos i stos? Przypuszczam, że przy adresowaniu rejestrów (operacje rejestr-rejestr) potrzebujemy co najmniej dwóch rejestrów, ale czy potrzebujemy więcej niż dwóch?

Jeśli zezwalasz na bezpośredni dostęp do pamięci według adresu pamięci, nie potrzebujesz żadnych „rejestrów”, ponieważ zamiast tego możesz użyć lokalizacji pamięci. Na przykład pamięć w lokalizacji 0 może być licznikiem programu, w lokalizacji 1 mamy wskaźnik stosu itp. Ale to oszustwo.

Aby nie dopuścić do oszustwa, załóżmy, że nie ma bezpośredniego dostępu do pamięci, ponieważ moglibyśmy użyć ustalonych lokalizacji pamięci jako rejestrów. Następnie możemy uciec od dwóch rejestrów, licznika programów i wskaźnika stosu, jak wyjaśniono w artykule Wikipedii na temat maszyn stosowych . Stos jest dostępny tylko poprzez wskaźnik stosu, a program jest dostępny tylko przez licznik programu.

Inną możliwością jest użycie liczników. Maszyna z dwoma licznikami jest ukończona przez Turinga, tzn. Może obliczyć wszystko, co potrafi maszyna Turinga. To znowu jest ładnie wyjaśnione w artykule Wikipedii na temat liczników .

Architektura PIC, która została wprowadzona przez General Instruments w latach 70. XX wieku i jest nadal używana, miała następujące rejestry:

W register (not addressible)
01    Timer/Counter
02    Program Counter
03    Status
04    File-Select Register
05-07 One register for each I/O port
08-1F General-purpose registers/"memory"

Typowa instrukcja odczytuje rejestr, wykonuje obliczenia przy użyciu wartości read i W, a następnie zapisuje wynik obliczeń w W lub w rejestrze, który został odczytany. Jedno z dostępnych obliczeń daje „odczytaną wartość, ignorując W”; innym jest „weź W, ignorując odczytaną wartość”. Wzorce bitów, które odpowiadają „odczytać XX, a następnie wziąć W, ignorując odczytaną wartość i zapisać wynik w W”, są używane dla NOP, jak również dla szeregu specjalnych instrukcji.

Aby umożliwić obliczenia adresu, jednostka wykonawcza procesora będzie szukała instrukcji, które kodują adres 00, i zastępuje zawartość rejestru wyboru plików.

Chociaż konieczność wprowadzania wszystkich wartości przez rejestr W może być wąskim gardłem, architektura PIC ma większy zestaw roboczy niż inne architektury używające tego samego słowa instrukcji długości. Na PIC16C54 (wciąż produkowanym do dziś i bardzo podobnym do PIC z lat 70.) instrukcje mają długość 12 bitów. W wielu innych częściach 16Cxx lub 16Fxx instrukcje mają długość 14 bitów i mogą bezpośrednio uzyskiwać dostęp do 128-bajtowej przestrzeni adresowej. Jeśli zestaw roboczy programu dobrze pasuje do zestawu roboczego zestawu instrukcji, instrukcja typu „total + = wartość”, gdzie „total” i „value” są typu unsigned char, skompiluje się w celu:

movf  value,w
addwf total,f

Na czymś takim jak ARM, nawet jeśli rejestr ma wstępnie załadowany adres podstawowy swoich zmiennych, kod byłby bardziej podobny do:

ldr    r0,[r7+value]
ldr    r1,[r7+total]
add    r1,r1,r0
str    r1,[r7+total]

W wielu przypadkach kompilator byłby w stanie uniknąć wykonywania obciążeń i zapisywania przy każdej operacji, ale w przypadku czegoś takiego jak PIC korzyści z większego zestawu roboczego mogą czasami przewyższać ograniczenia związane z koniecznością przechodzenia przez W przez cały czas.