Теоретическое минимальное количество регистров для современного компьютера?

10

В бакалавриате я прошел курс по компиляторам, в котором мы написали компилятор, который компилирует исходные программы на игрушечном Java-подобном языке в игрушечный ассемблер (для которого у нас был переводчик). В проекте мы сделали несколько предположений о целевой машине, тесно связанной с «настоящими» нативными исполняемыми файлами, включая:

  • стек времени выполнения, отслеживаемый регистром выделенного указателя стека («SP»)
  • куча для динамического выделения объектов, отслеживаемая регистром выделенного указателя кучи («HP»)
  • регистр счетчика выделенных программ («ПК»)
  • целевая машина имеет 16 регистров
  • операции над данными (в отличие, например, от скачков) являются операциями регистр-регистр

Когда мы добрались до подразделения по использованию распределения регистров в качестве оптимизации, меня удивило: каково теоретическое минимальное количество регистров для такой машины? Исходя из наших предположений, вы можете видеть, что в нашем компиляторе мы использовали пять регистров (SP, HP, ПК и два для использования в качестве хранилища для бинарных операций). Хотя такие оптимизации, как распределение регистров, безусловно, могут использовать больше регистров, есть ли способ обойтись с меньшим количеством, сохраняя при этом такие структуры, как стек и куча? Я полагаю, что при адресации регистров (операции от регистра к регистру) нам нужно как минимум два регистра, но нужно ли нам больше двух?

compilers computer-architecture BlueBomber
источник
«Указатель кучи» кажется странной идеей. Потому что, в отличие от стека, куча не является LIFO и не сводится к семантике push / pop. Вы должны скорее видеть динамическое распределение памяти как вызовы подпрограмм malloc / free.
Ив Дауст

Ответы:

14

Если вы разрешаете прямой доступ к памяти по адресу памяти, вам не нужны никакие «регистры», потому что вы можете вместо этого использовать ячейки памяти. Например, память в ячейке 0 может быть счетчиком программ, в ячейке 1 у нас есть указатель стека и т. Д. Но это обман.

Поэтому, чтобы не допустить обмана, давайте предположим, что прямого доступа к памяти нет, поскольку мы могли бы использовать фиксированные области памяти в качестве регистров. Затем мы можем получить два регистра: счетчик программ и указатель стека, как описано в статье в Википедии о машинах стека . Стек доступен только через указатель стека, а программа доступна только через счетчик программ.

Другая возможность заключается в использовании счетчиков. Машина с двумя счетчиками является полной по Тьюрингу, т. Е. Может вычислять все, что может машина Тьюринга. Это снова хорошо объясняется в статье Википедии о счетчиках машин .

Андрей Бауэр
источник
Спасибо за ответ! Однако в статье о машинах стека упоминается, что машина способна к прямому доступу к памяти (для выполнения операций над самыми верхними элементами стека и повторного включения результата), так что это все еще обман, верно? Что касается счетчика, я прочитал эту статью. Я также прочитал аналогичное доказательство TC для 2-CM, но оба эффективно включают в себя хранение всей оперативной памяти в двух регистрах, что мне даже больше кажется обманом.
BlueBomber
Ну, в какой-то момент это уже не обман. Операции со стеком не являются мошенничеством, если они запрещают прямой доступ к фиксированному расположению в памяти. Допустимо иметь возможность, скажем, вращать три самых верхних элемента стека. Во всяком случае, ваш вопрос немного странный, так что не стоит зацикливаться на том, что обманывает, а что нет.
Андрей Бауэр
Еще раз спасибо за ответ. В любое время тема относится к теоретическим границам, обман становится еще менее приемлемым! Это не значит, что это не поучительно. Дело в том, что это не мошенничество, когда, ну, нет мошенничества, я думаю. Я нашел ваш первоначальный ответ информативным, но проблема в том, что наша модель перекрывает все модели машин Тьюринга, Счетчика и стековой машины, и, учитывая наши предположения (включая конечное число конечных регистров и отсутствие прямого доступа к памяти), мы можем получить только с двумя регистрами?
BlueBomber
1
Я нахожу этот вопрос странным, потому что трудно определить реальные концепции, такие как процессор, регистр, доступ к памяти и т. Д., Но вам нужно их закрепить, чтобы иметь возможность что-либо доказать. Таким образом, конечным результатом будет то, что все, что вы доказываете, легко доказать, но оно очень сильно зависит от того, как вы формализуете вопрос (каково ваше теоретическое представление о «процессоре», «регистре», «памяти» и т. Д.).
Андрей Бауэр
1
Учебник компилятора не позволяет нам много доказывать, по крайней мере, не в математическом смысле слова «доказать». Вам нужно сделать еще один шаг в формализации аппаратного обеспечения, чтобы прийти к чему-то, что позволит получить доказательства . Во всяком случае, мы расщепляем волосы, и я уже дал вам мой лучший ответ.
Андрей Бауэр
1

Архитектура PIC, которая была введена General Instruments в 1970-х годах и используется до сих пор, имеет следующие регистры:

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"

Типичная инструкция считывает регистр, выполняет вычисление с использованием значения read и W, а затем сохраняет результат вычисления либо в W, либо в регистр, который был прочитан. Одно из доступных вычислений выдает «прочитанное значение, игнорируя W»; другой - «возьми W, игнорируя прочитанное значение». Битовые комбинации, которые соответствуют «читать XX, затем брать W, игнорируя прочитанное значение и сохраняя результат в W», используются для NOP, а также для множества специальных инструкций.

Чтобы разрешить вычисление адреса, исполнительный модуль процессора будет следить за инструкциями, кодирующими адрес 00, и заменять содержимое регистра выбора файлов на адрес.

Хотя необходимость подачи всех значений через регистр W может быть узким местом, архитектура PIC имеет больший рабочий набор, чем другие архитектуры, использующие одно и то же слово инструкции длины. На PIC16C54 (все еще сделанном сегодня и очень похожем на PIC 1970-х) инструкции имеют длину 12 бит. Во многих других частях 16Cxx или 16Fxx инструкции имеют длину 14 бит и могут напрямую обращаться к 128-байтовому адресному пространству. Если рабочий набор программы хорошо согласуется с рабочим набором набора команд, оператор типа «total + = value», где «total» и «value» имеют тип unsigned char, будет компилироваться в:

movf  value,w
addwf total,f

На чем-то похожем на ARM, даже если у кого-то есть регистр, предварительно загруженный с базовым адресом своих переменных, код будет больше похож на:

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

Во многих случаях компилятор мог бы избежать загрузки и сохранения при каждой операции, но на чем-то вроде PIC преимущества большого рабочего набора могут иногда перевешивать ограничения, связанные с необходимостью постоянно проходить через W.

Supercat
источник