Программная оптимизация использования регистров

Пусть в составе процессора имеется небольшое ко­личество регистров (примерно 16-32) и ответственность за их оп­тимальное использование перекладывается на программы компиляторов с языков высокого уровня в машинный код. Естественно, что в исходном тексте программы на языке высокого уровня никаких ссылок на регистры не содержится. Обращение ко всем языковым кон­струкциям, описывающим данные в программе, производится на уровне симво­лов языка. Компилятор должен так преобразовать исходный текст программы в последовательность машинных команд, чтобы как можно больше часто используемых в текущем фрагменте переменных хранилось в регистрах, а не в оперативной памяти. В итоге, количество операций пересылки данных между регистрами и оперативной памятью будет минимальным.

Исследования показали, что применение даже простых алгоритмов оптимизации делает излишним использование количества регист­ров свыше 64. Применение же сложных алгоритмов оптимизации позволяет вполне обойтись 32 регистрами без сколько-нибудь заметного снижения производительно­сти. Кроме того, исследователи пришли к выводу, что при использовании небольшо­го количества регистров (например, 16) компьютер без специализации регистров ра­ботает быстрее, чем компьютер с разделением регистров по типам форматов чисел. Аналогичные результаты были получены и в ряде других работ, в которых сравни­валась эффективность использования оптимизирующих компиляторов для процессо­ров с малым числом регистров по сравнению с процессорами с расширенным набо­ром регистров, организованных в виде регистровых окон.

Аппаратный подход к повышению эффективности использования регистров

Регистровые окна

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

Поскольку большинство операндов машинных команд представляет собой локальные скалярные переменные, то логично было бы держать эти переменные в регистрах. Для хранения небольшого числа час­то используемых глобальных переменных также целесообразно было бы выделить необходимое количество регистров.

Проблема состоит в том, что определение "локальности" переменной изменяется при каждом вызове очередной процедуры или возврате из нее, а эти операции выполняются в ходе работы программы очень часто. При использовании стека при каждом вызове процедуры локальные переменные вызывающей про­граммы (которая, в свою очередь, может быть процедурой по отношению к за­пустившей ее программе) должны пересылаться из регистров в стек, который находится в оперативной памяти, чтобы осво­бодить регистры для локальных переменных вызываемой процедуры. Кроме то­го, в вызываемую процедуру требуется еще передать и параметры вызова. При возврате из процедуры следует, во-первых, восстановить в регистрах сохранен­ные в стеке (в памяти) переменные, а во-вторых, передать в вызывающую программу резуль­таты выполнения завершенной процедуры.

Для эффективного решения этой проблемы в процессоре, имеющем в своем составе значительное число регистров, необходимо ответить на несколько вопросов:

какое распределение числа локальных переменных в процедурах;

какое распределение числа передаваемых параметров и возвращаемых результатов;

какое распределение вложенности вызовов процедур.

Результаты исследования значительного числа программ показали, что:

в типичной процедуре используется весьма небольшое коли­чество локальных переменных;

при вызове процедуре передается, как правило, всего несколько параметров;

размер возвращаемых результатов также невелик;

глубина вложенности вызовов в ти­пичной процедуре изменяется в весьма узких пределах.

Учитывая эти особенности типичных программ, было предложено разделить весь набор регистров процессора на ряд небольших групп — регист­ровых окон (register window). Каждое регистровое окно в процессе выполне­ния программы будет связываться с определенной процедурой. При вызове очередной процедуры вместо того, чтобы пересылать содержимое регист­ров в оперативную память и записывать в них локальные переменные и параметры вызо­ва, процессор может автоматически переключаться на использование регист­рового окна, связываемого с новой процедурой. Если регистровые окна вло­женных процедур будут частично перекрываются, т.е. некоторые регистры будут входить в состав двух соседних регистровых окон, то это обеспечит автоматическую передачу параметров в вызываемую процедуру и возврат результатов в вызывающую процедуру.

Описанная концепция иллюстрируется схемой, приведенной на рис. 13.1.

Рис. 13.1 Перекрывающиеся регистровые окна

В любой момент времени в ходе выполнения программы процессор "видит" только одно регистровое окно и обращается к регистрам, которые входят в него, так, как если бы они были единственными регистрами процессора (т.е. имели адреса от 0 до N-1).

Регистровое окно делится на три области фиксированного размера.

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

Область локальных регистров используется для хранения локальных переменных процедуры. Назначение каждого из регистров определенной переменной в этой области про­изводится компилятором.

Область временных регистров используется для пере­дачи параметров и приема результатов из процедуры следующего уровня вложенности, т.е. процедуры, вызываемой данной процедурой. Область временных регистров окна одного уровня физически представляет те же регист­ры, что и область регистров параметров окна следующего уровня. Такое пере­крытие окон позволяет передавать в процедуру параметры, не выполняя при этом операций пересылки данных.

Чтобы такую схему разделения регистров процессора можно было использо­вать при любой последовательности вызовов/возвратов, возможной в реальных программах, количество регистровых окон не должно ограничиваться. Посколь­ку физически это реализовать невозможно, регистровые окна применяются для работы с несколькими последними по уровню вложенности процедурами. Данные, касающиеся процедур меньшего уровня вложенности, должны при этом сохраняться в оперативной памяти. Они переписываются в высвобождающиеся регист­ровые окна при понижении уровня вложенности текущей выполняемой процедуры. Таким образом, в процессоре перекрывающиеся регистровые окна име­ют такую же организацию, как и кольцевой буфер данных.

При использовании набора из N регист­ровых окон, они обеспечивают обработку (N-1)вложенных вызовов процедур. Значение N может быть довольно небольшим. В ряде работ было показано, что при использова­нии восьми окон сохранять в оперативной памяти и восстанавливать из нее содержимое реги­стрового окна приходится при выполнении только 1% всех операций вызова и возврата из процедур.