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?

compilers computer-architecture

— BlueBomber
źródło

„Wskaźnik sterty” wydaje się dziwnym pomysłem. Ponieważ w przeciwieństwie do stosu, sterta nie jest LIFO i nie redukuje się do semantyki push / pop. Powinieneś raczej widzieć dynamiczny przydział pamięci jako połączenia z procedurami malloc / free.

— Yves Daoust,

Odpowiedzi:

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 .

— Andrej Bauer
źródło

Dziękuję za odpowiedź! Artykuł na temat maszyn stosowych wspomina jednak, że maszyna jest w stanie uzyskać bezpośredni dostęp do pamięci (w celu wykonywania operacji na najwyższych elementach stosu i odkładania wyniku z powrotem), więc nadal jest to oszustwo, prawda? Jeśli chodzi o licznik, przeczytałem ten artykuł. Przeczytałem również podobny dowód TC 2-CM, ale oba skutecznie obejmują przechowywanie całej pamięci RAM w dwóch rejestrach, co wydaje mi się jeszcze bardziej oszustwem.

— BlueBomber 15.01.2013

W pewnym momencie już nie oszukuje. Operacje na stosie nie oszukują, o ile uniemożliwiają bezpośredni dostęp do stałej lokalizacji w pamięci. Można, powiedzmy, obrócić trzy najwyższe elementy stosu. W każdym razie twoje pytanie jest trochę dziwne, więc nie opłaca się mieć obsesji na punkcie tego, co jest i nie oszukuje.

— Andrej Bauer,

Jeszcze raz dziękuję za odpowiedź. Za każdym razem, gdy temat dotyczy granic teoretycznych, oszukiwanie jest jeszcze mniej akceptowalne! Nie oznacza to jednak, że nie jest pouczające. Chodzi o to, że nie jest to oszustwo, kiedy, cóż, chyba nie ma oszukiwania. Znalazłem twoją wstępną odpowiedź, ale problem polega na tym, że nasz model pokrywa się z wszystkimi modelami maszyny Turinga, maszyny liczącej i maszyny stosu i biorąc pod uwagę nasze założenia (w tym skończoną liczbę rejestrów skończonych i brak bezpośredniego dostępu do pamięci), możemy to zrobić tylko z dwoma rejestrami?

— BlueBomber 15.01.2013

Uważam to pytanie za dziwne, ponieważ trudno jest określić rzeczywiste pojęcia, takie jak procesor, rejestr, dostęp do pamięci itp., Ale potrzebujesz tych przypiętych, aby móc cokolwiek udowodnić. Ostateczny wynik będzie taki, że wszystko, co udowodnisz, będzie łatwe do udowodnienia, ale zależy to w dużej mierze od tego, jak sformalizujesz pytanie (jakie jest twoje teoretyczne pojęcie „procesor”, „rejestr”, „pamięć” itd.).

— Andrej Bauer,

Podręcznik kompilatora nie pozwala nam wiele udowodnić, a przynajmniej nie w matematycznym znaczeniu słowa „udowodnić”. Musisz pójść o krok dalej w formalizacji sprzętu, aby dojść do czegoś, co pozwoli na dowód . W każdym razie dzielimy włosy, a ja już dałem ci najlepszą odpowiedź.

— Andrej Bauer,

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.

— supercat
źródło