Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

О реализации метода распределения регистров при компиляции

Введение

Введение

            Статья продолжает тему описания методов, примененных в компиляторе [1] с языка PL/1, разработанным американским специалистом Гарри Килдэллом (Gary Kildall). Несмотря на американское происхождение, этот компилятор можно также рассматривать и как отечественную разработку, поскольку автор после выпуска первых версий в 1982-84 гг. более ими не занимался, и дальнейшее развитие компилятора происходило уже в нашей стране.

            Статья предназначена для читателей, знакомых с командами процессоров IA-32 и интересующихся устройством реальных компиляторов и теми приемами, которые использовались для оптимизации кода. Здесь детально рассматривается реализация распределения регистров при генерации кода для процессоров IA-32 в одном конкретном и давно успешно применяемом компиляторе.

            Использование регистров IA-32 существенно влияет на генерируемый код в части размера и времени его выполнения. Однако задача их оптимального распределения в общем виде сложна: регистров мало, они взаимосвязаны (можно независимо обращаться к байтовым частям одного и того же регистра), есть короткая форма с использованием сумматора, для ряда команд нужно использовать только определенные регистры и т.п.

            Исходная версия компилятора потребовала значительной переработки, так как изначально код генерировался для процессоров 8080/8086, т.е. для существенно более ограниченной архитектуры (первый процессор IA-32 80386 был выпущен в 1985 году, уже после создания компилятора).

            Для лучшего понимания роли распределения регистров во всем процессе компиляции, сначала дается краткое описание реализации генерации кода.

Организация генерации кода в компиляторе

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

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

            Внутренние операции являются командами упрощенной абстрактной машины и не являются множеством команд IA-32.

            В результате обработки каждой внутренней операции компилятор генерирует одну или несколько команд уже из подмножества IA-32, причем сначала эти «команды» представляют собой лишь внутренние структуры компилятора, в которых есть ссылки на ноль, одну или две других внутренних структуры — т.е. на «операнды». Новые «команды» и «операнды» берутся компилятором из списка свободных структур, а после генерации кода и его записи в выходной объектный модуль, опять возвращаются в список свободных структур.

            Обработка внутренних операций в обратной польской записи ведется отдельными порциями-«выражениями». Концом очередного «выражения» служит появление во входном потоке конкретных внутренних операций, имеющих в своих атрибутах признак «конец выражения». Сами атрибуты постоянны и известны компилятору. Например, операция присваивания или условие в условном операторе являются одновременно и концами соответствующих «выражений».

            Однако, встретив очередной конец «выражения» компилятор не начинает немедленно доводить полученные в процессе обработки этого «выражения» «команды» (полуфабрикаты команд IA-32) до конечного состояния, а накапливает их в разумных пределах с целью последующей генерации кода и распределения регистров сразу для сравнительно большого фрагмента программы, большего, чем один оператор. Такое накапливание помогает оптимизации кода. Например, если в программе встретились два оператора присваивания целых переменных типа X=Y; Z=X;, компилятор может учесть, что к моменту второго присваивания в каком-либо регистре сохранилось значение X от предыдущего присваивания и повторная загрузка переменной в регистр не требуется.

            Далее блок накопленных «команд» последовательно проходит шесть этапов обработки до получения на выходе двоичного кода объектного модуля в формате Intel OMF, т.е. в данном компиляторе генератор кода команд IA-32 является шестипроходным.

Ступени генерации кода команд IA-32

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

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

            На втором проходе происходит вторая и последняя итерация распределения регистров: учитывается, что некоторые системные вызовы и вызовы подпрограмм «портят» значения регистров, а также распределяются регистры для объектов, не используемых как базовая или индексная часть адреса.

            На третьем проходе проводится генерация кода каждой команды, (кроме команд передачи управления) поскольку к этому моменту уже нет внутренних «операндов», не привязанных к конкретному регистру или участку памяти. На этой ступени также проводится различная оптимизация. Например, пара команд CALL и RET заменяется командой JMP (если не было передачи параметров через стек). Здесь же ищутся «лишние» команды типа LEA ESI,[ESI] или из цепочки команд:
AND AL,80h
CMP AL,0
JNZ …
исключается лишнее сравнение с нулем. Производится ряд других оптимизирующих и вспомогательных действий: свертка адресных выражений в формат SIB-байта, подстановка команды INTO для контроля целочисленных переполнений и т.п.

            На следующем четвертом проходе обрабатываются команды передачи управления (прогнозируется их длина). Обрабатываются также и метки в части определения уже известен или еще нет их адрес. Эта отдельная ступень нужна для того, чтобы заново, с учетом спрогнозированных длин, пересчитать все адреса блока команд.

            На пятом проходе генерируются коды команд передачи управления. После обработки очередной команды на этой ступени она, наконец, становится полностью готовой и записывается в объектный модуль в набор записей LEDATA+FIXUPP. Некоторые команды все же остаются «недостроенными» и для них после завершении всей компиляции в конец объектного модуля дописываются дополнительные настройки LEDATA+FIXUPP, позволяющие выполнить окончательную настройку уже не компилятору, а редактору связей на этапе объединений всех объектных модулей в загрузочный модуль. На этой ступени может быть выдан и листинг исходного текста вместе с готовыми командами. Такой листинг используется в приводимых ниже примерах.

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

            Такая многоступенчатая генерация кода является следствием сложной системы команд IA-32, в частности переменной длины команд, в том числе и команд передачи управления. В общем случае невозможно сгенерировать команду передачи управления (или она будет неоптимальной длины) пока не будут сгенерированы все остальные команды между этой командой и командой-целью перехода.

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

Подход к задаче распределения регистров

            Формально задача распределения регистров в данном компиляторе сводится к поиску всех внутренних «операндов», еще не привязанных к регистрам или объектам в памяти, и назначению каждому из них или одного из регистров IA-32 или, в некоторых случаях, адреса внутренней (недоступной пользователю) переменной, для которой компилятор тут же сам и выделит память.

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

Использование алгоритма Биледи

            Кроме модели процессора IA-32, в задаче распределения регистров применяется также алгоритм или принцип Л. А. Биледи. Этот специалист предложил в случае необходимости выбора ресурса из всех уже занятых, выбирать такой ресурс, в данном случае регистр, к которому произойдет обращение (из-за чего собственно он уже и занят) позже всех остальных, относительно текущей команды.

            Для реализации алгоритма Биледи модель процессора IA-32 хранит и текущие «времена жизни» всех регистров как целые числа, равные числу команд от текущей команды до команды, где этот регистр будет использован. При необходимости согласно принципу Биледи будет выбран тот регистр, «время жизни» у которого в данный момент наибольшее. При обработке следующей команды из блока накопленных команд «времена жизни» у всех регистров уменьшаются на единицу, так как они приближаются к местам своего использования. Имеется также два особых значения «времени жизни»:
  • ноль, означающее, что этот регистр распределять вообще нельзя (например, регистр стека ESP);
  • -1, означающее, что «время жизни» регистра не определено.

Организация модели процессора IA-32 для отслеживания регистров

            Модель процессора IA-32, отслеживающая текущее состояние всех регистров, состоит из таблицы ссылок на «операнды», ссылок на «команды» и значений «времени жизни». Число элементов таблицы равно числу рассматриваемых регистров, например, регистры AL, AH и EAX занимают в таблице отдельные места. Регистры математического «сопроцессора» и дополнительных множеств команд типа MMX или SSE2 в распределении не учитываются, так как такие команды используются только внутри системных подпрограмм или ассемблерных модулей и напрямую (за исключением некоторых команд запоминания результата) компилятором не генерируются.

            Ссылки на «команды» нужны для определения места, куда при необходимости вставлять команду запоминания.

            Когда регистр встречается (или задается) как первый «операнд» очередной обрабатываемой «команды», в таблицу заносится ссылка на эти «операнд» и «команду». Т.е. модель запоминает текущее состояние регистра, не анализируя при этом его действительное значение, которое будет при выполнении программы.

            Когда регистр встречается (или задается) как второй «операнд» очередной рассматриваемой «команды», ссылки в таблице заменяются на неопределенные. Т.е считается, что регистр выполнил свою роль и его значение далее неопределенно, а сам регистр стал свободен, даже если данная команда физически и не меняет свой второй операнд.

            Однако для команд пересылки регистра в переменную модель отслеживает в своей таблице тот факт, что в данной точке регистр имеет это значение (т.е. в соответствующий элемент таблицы регистров записывается ссылка на операнд-переменную). Именно это действие модели позволяет компилятору в паре смежных операторов присваивания X=Y; Z=X; не генерировать лишнюю загрузку во втором операторе. Когда потребуется регистр для загрузки X, в таблице модели оказывается, что такой регистр (т.е. с такой же ссылкой на переменную-операнд) уже есть и можно не искать новый свободный регистр, а использовать существующий.

            Поскольку некоторые регистры IA-32 взаимосвязаны, в модели также имеется специальная процедура, выполняющая отслеживание этой взаимосвязи. Входными параметрами для этой процедуры являются собственно заданный регистр (его номер в таблице) и алгоритм действия. По терминологии ООП процедура обрабатывает виртуальный метод. В данном компиляторе используется пять конкретных методов:
  • сброс регистра в неопределенное значение;
  • сброс регистра в неопределенное значение с запоминанием при необходимости предыдущего значения;
  • проверка занятости регистра в данный момент;
  • проверка занятости регистра на всем рассматриваемом участке;
  • отметка наименьшего «времени жизни» регистра для алгоритма Биледи.
            Например, если требуется сбросить в неопределенное значение регистр AL, то процедура сбросит в неопределенные значение не только элементы таблицы для AL, но еще и для EAX а также для условного арифметического регистра AD (пары EAX:EDX), который тоже считается регистром, хранящим результаты целочисленного деления и умножения. Т.е. будет отслежена связь IA-32 AL->EAX->EAX:EDX. При этом значение регистра AH останется в таблице неизмененным.

            При работе модели 16 и 32-битовые регистры, например, AX и EAX не различаются, так как обратиться независимо к старшей половине EAX нельзя. Но, конечно, при генерации кода длина 16-битовых регистров учитывается в виде соответствующего префикса команды.

            При обработке команд умножения и деления им выделяется условный арифметический регистр AD (т.е. пара EAX:EDX) и его сброс в модели автоматически приводит к сбросу группы регистров AL, AH, DL, DH, AX/EAX, DX/EDX.

            Если требуется найти свободный регистр, то он также ищется с помощью указанной процедуры, например, при проверке незанятости EAX нужно проверить и незанятость регистров AL/AH. Аналогично при поиске регистра с самым большим «временем жизни» для алгоритма Биледи выбирается наилучший регистр с учетом «времени жизни» взаимосвязанных с ним регистров.

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

            Хотя в командах IA-32 возможно использование одновременно двух регистров как косвенных (база + индекс), в данном компиляторе только один регистр задается как возможная дополнительная часть адреса. Использование сразу двух регистров и масштабирование в режиме адресации SIB-байта производится уже на третьем проходе генерации команд путем «свертки» нескольких последовательных простых команд.

Предпосылки к распределению регистров и принятые правила

            В командах IA-32 можно выделить случаи, когда регистр необходим и когда он желателен. Например, в команде MOV EAX, X где X — целая переменная, регистр необходим, так как в команде может быть только один операнд-ссылка на память. Строго говоря, команду с двумя адресами можно было бы смоделировать с помощью стека, например несуществующую команду IA-32 MOV X,Y можно изобразить парой команд PUSH Y и POP X, однако в данном компиляторе такой подход не используется. Кстати, в приведенном примере, использование стека по сравнению с двумя пересылками через регистр EAX увеличивает размер команд на 2 байта и происходит двойное дополнительное обращение к памяти (к стеку).

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

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

            Все регистры в компиляторе условно разделены на адресные и не адресные. Это идет еще от первых версий для 8080/8086, где не все регистры могли использоваться для вычисления адреса в команде. Однако и для команд IA-32, где уже нет таких ограничений, разделение регистров на две группы имеет смысл. Так, часто невыгодно «тратить» регистр EAX как индексный или базовый регистр, поскольку он тут же может потребоваться для пересылок, более коротких, чем через другие регистры. К тому же занятие регистра EAX для адреса автоматически означает еще и сброс значений в AL/AH, т.е. уменьшение числа свободных регистров.

            Для результата умножения и деления используется условный арифметический «регистр» EAX:EDX.

            Следует отметить, что в данном компиляторе параметры в подпрограммы (кроме процедур Win-32 API) передаются не через стек, а через список адресов в памяти, и поэтому регистр EBP часто свободен и может использоваться не только для адресации параметров или локальных переменных.

Принцип распределения регистров

            Описанная выше модель IA-32, алгоритм Биледи и приведенные правила использования регистров сами по себе еще не задают процесса распределения регистров.

            Собственно распределение регистров происходит следующим образом:
  • ищется свободный регистр в таблице;
  • если такой находится — задача выделения регистра решена;
  • если свободного регистра нет, выделяется уже занятый, а его значение запоминается и в нужном месте восстанавливается с помощью пары специальных команд, добавляемых компилятором в определенные места обрабатываемого блока команд.
            Особенностью рассматриваемого распределения является то, что служебная команда запоминания формируется в виде:
MOV <новый операнд-1>, <регистр>
а соответствующая команда восстановления в виде:
MOV <новый операнд-2>, <новый операнд-1>
            Может показаться нелогичным, что в команде восстановления не задается запомненный ранее регистр, а указывается новый внутренний операнд, для которого опять потребуется распределение регистров. Однако, такой прием увеличивает гибкость распределения, так как к моменту команды восстановления операционная обстановка изменится и необязательно наилучшим регистром останется первоначально выбранный. А с точки зрения логики безразлично, какой именно регистр был запомнен, раз все равно требуется команда восстановления.

            При этом достаточно будет обработать лишь команду восстановления, а парная ей команда запоминания определится «сама собой», как только будет определен <новый операнд-1>.

            Использование стека для запоминания и восстановления регистров в данном компиляторе применяется редко из-за специфики языка PL/1, требующей возможности передачи управления в обход нормального возврата из подпрограммы и как следствие особой реализации рекурсивных подпрограмм.

            Таким образом, принятый способ распределения регистров может вызывать появление новых пар служебных команд запоминания и восстановления. Команда запоминания оказывается «выше» текущее обрабатываемой команды, а команда восстановления — «ниже». Эти служебные команды помечаются компилятором, чтобы не путать их с остальными командами, использующими регистры, иначе процесс запоминания и восстановления может стать бесконечно рекурсивным.

            При этом, команды запоминания и восстановления создаются не вообще для всех регистров, используемых в программе, а только для ранее распределенных на двух проходах. А если регистр задан сразу после обработки внутренних операций, например в команде XOR AL,AL для обнуления сумматора, то такое появление AL как первого операнда команды не вызовет генерации дополнительных команд, а только будет учтено в модели сбросом AL в неопределенное значение.

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

Общая организация распределения регистров на первом и втором проходах

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

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

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

            В данном компиляторе как базовые и индексные используются регистры ESI/EDI/EBX/ECX, в командах восстановления ESI/EDI/EBP/EBX и для пересылок — любые подходящие и незанятые.

            Разница в использовании регистров как индексных и базовых и в командах восстановления (EBP вместо ECX) объясняется спецификой данного компилятора. Хотя, например, команда MOV EAX,[ECX] короче, чем MOV EAX,[EBP], в данном компиляторе ECX часто используется в системных вызовах обработки строк. Поэтому сначала идет попытка использовать как индексный все-таки ECX, однако если потребовалось восстановление, то ECX чаще остается занятым для строк и тогда использование EBP оказывается выгоднее. Разумеется, встречаются ситуации, где эти соображения несправедливы, но в среднем выигрыш от «несимметричного» использования ECX и EBP все же получается.

            На втором проходе учитываются вызовы подпрограмм, которые в принципе делают все значения регистров неопределенными. Перед вызовом подпрограммы генерируются в цикле пары команд запоминания и восстановления для всех регистров, которые ранее были распределены.

            Затем рассматриваются команды, у которых первый операнд — уже выделенный регистр. Например, это команды восстановления, сгенерированные на первом проходе. На втором проходе для них определяется и второй операнд.

            Начальным действием для команд с первым операндом-регистром является поиск в таблице модели такого регистра, который содержит ссылку на операнд, совпадающий со вторым операндом в рассматриваемой команде. Если такой регистр найден — он заменяет в текущей команде второй операнд, независимо от того, чем этот операнд являлся ранее: внутренним объектом компилятора или переменной пользователя, так как команда с двумя операндами-регистрами имеет более короткий код.

            Наконец последними рассматриваются команды, у которых первый операнд — внутренний объект компилятора. Это и команды восстановления, появившиеся на втором проходе из-за вызова подпрограмм и команды, полученные при обработке внутренних операций. Например, оператор присваивания X=Y; приведет к генерации двух команд:
MOV <внутренний операнд>,Y
MOV X,<внутренний операнд>
            Необходимо выделить регистр для <внутреннего операнда> первой команды, тогда вторая команда будет определена автоматически.

Реализация распределения регистров на первом проходе

            Вернемся к реализации распределения регистров в рассматриваемом компиляторе на более детальном уровне. На первом проходе работа по распределению регистров сравнительно небольшая:
  • в начале обработки все регистры считаются неопределенными;
  • если второй операнд очередной рассматриваемой команды — регистр, этот регистр «освобождается» от этого операнда (в модели таблицы пишутся неопределенные значения);
  • если первый операнд очередной рассматриваемой команды обычный регистр (не выделенный на этом проходе), то в таблице модели устанавливаются ссылки на текущие «операнд» и «команду», с автоматическим запоминанием (при необходимости) предыдущих распределений;
  • если первый операнд очередной рассматриваемой команды — это адресный элемент (типа базы или индекса), которому нужно выделить регистр, он выделяется из группы ESI/EDI/EBX/ECX с автоматическим запоминанием (при необходимости) предыдущих распределений;
  • для команд TEST, CMP и PUSH освобождается сбросом в неопределенное значение и первый операнд, как уже выполнивший свою задачу;
На первом проходе алгоритм Биледи не задействован.

Реализация распределения регистров на втором проходе

            Основной объем работ по распределению регистров выполняется на втором проходе обработки блока команд. В начале прохода опять все регистры считаются неопределенными. На втором проходе помимо таблицы модели используется еще одна таблица — карта занятости всех регистров, содержащая признаки занятости регистров в виде значения «да/нет». Такая карта используется при распределении регистров по «остаточному» принципу и учитывает не только текущее использование регистров, но и их использование во всем рассматриваемом фрагменте программы.

            Первым действием анализируется второй операнд очередной команды и если это «обычный» (т.е. не выделенный на этих проходах) регистр, то для команды обмена XCHG или для команд, имеющих два одинаковых операнда-регистра типа XOR AL,AL производится запоминание предыдущего значения регистра, если он был ранее распределен, так как данной командой это значение портится.

            Затем, как и на первом проходе, если второй операнд очередной рассматриваемой команды — регистр, этот регистр «освобождается» от этого операнда (в модели таблицы пишутся неопределенные значения), так как операнд выполнил свою задачу.

            Следующим шагом обработки текущая команда проверяется на вызов подпрограммы (CALL). У компилятора есть список вызовов служебных подпрограмм, которые не меняют регистров, такие подпрограммы на данном шаге просто попускаются. Однако все остальные вызовы могут изменить любые регистры, и поэтому перед командой CALL запоминаются значения всех распределенных ранее регистров. Причем и сама команда CALL в случае косвенного вызова может использовать регистры. В этих случаях они, входящие в первый операнд такой команды, «освобождаются» от операнда, как выполнившие свою задачу. После запоминания все регистры сбрасываются в неопределенные значения.

            Следующим шагом обработки идет проверка на метку, которая также имеет формат «команды». Если это метка — то перед ней все регистры уже должны иметь неопределенные значения, иначе из-за потенциальной возможности перехода на эту метку из другого места значение регистра нельзя учитывать, а компилятор сообщит об ошибке в своей работе.

            Наконец на следующем шаге выполняется вся существенная часть работ по распределению регистров. Рассматриваются два случая:
1. Первый операнд уже регистр и тогда обрабатывается второй операнд. Этот случай охватывает и команды восстановления, которым на первом проходе были назначены индексные или базовые регистры.
2. Первый операнд внутренний. Это, например, случай оператора присваивания типа X=Y; когда сначала приходится загружать значение Y в такой внутренний операнд, а затем его засылать в X, поскольку прямой команды пересылки типа MOV X,Y в процессорах IA-32 нет. В следующих разделах будут детально рассмотрены действия в этих двух случаях.

            После обработки этих двух случаев все операнды получают, наконец, свое значение как регистры или участки памяти. Как и на первом проходе для команд TEST, CMP и PUSH первый операнд «освобождается» сбросом в неопределенное значение, поскольку здесь он уже выполнил свое назначение.

            Далее первый операнд ищется в таблице модели и если какой-либо из регистров имел такое же значение (т.е. ссылку на этот же операнд), то такой регистр сбрасывается в неопределенное значение, так как текущая команда при выполнении программы в большинстве случаев изменит свой первый операнд. Так моделируется «выполнение» произвольной команды.

            Предпоследним действием обработки моделируется выполнение команды пересылки регистра во внутренний операнд. Например, если при выполнении оператора присваивания X=Y; когда был выделен регистр EAX и оператор превратился в две команды MOV EAX,Y и MOV X,EAX будет отмечено, что в EAX осталась ссылка на X.

            Последним действием обработки на втором проходе все определенные «времена жизни» регистров для алгоритма Биледи уменьшаются на единицу, поскольку идет продвижение на одну команду к концу блока команд, т.е. идет приближение к моменту использования каждого распределенного регистра.

            Затем начинается обработка следующей команды на втором проходе.

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

Обработка случая, когда первый операнд команды уже регистр

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

            Первым действием проверяется, нет ли готового регистра с нужной ссылкой и, если есть — этот регистр и выбирается для второго операнда, а команда, превращается в команду, у которой и второй операнд — регистр, т.е. приводится к более короткому виду.

            Затем при необходимости запоминается предыдущее значение ранее распределенного регистра - первого операнда, т.е. в этот момент опять могут быть добавлены команды запоминания и восстановления.

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

            Следующим шагом для всех команд восстановления универсальным способом выделяется регистр или память. Способ будет рассмотрен ниже.

            Затем, если первый операнд-регистр используется для вычисления адреса, ищется команда ниже, где он используется (встречается как второй или первый операнд) и считается его «время жизни» как число операций от текущей до команды использования.

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

Обработка случая, когда первый операнд — внутренний

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

            Сначала команда проверяется на команду запоминания, которая просто пропускается, так как достаточно обработать только соответствующую ей парную команду восстановления.

            Следующим шагом вычисляется «время жизни» первого операнда и для этого ниже ищется команда, где он используется.

            Если второй операнд — внутренний и запомненный, значит это команда восстановления, созданная на втором же проходе, т.е. имеющая оба внутренних операнда. В этом случае второму операнду универсальным способом выделяется регистр или память. Способ будет рассмотрен ниже.

            Затем, если второй операнд был адресом (т.е. базовым или индексным) первому операнду выделяются индексные или базовые регистры точно так же как и на первом проходе.

            Далее рассматриваются три особых случая, которые могут улучшить качество кода.
Первый особый случай: второй операнд регистр и есть рекомендация (указанная прямо в этом втором операнде) какой регистр выделять для первого операнда. Это часто используется при генерации системных вызовов, когда параметры нужно заслать в определенные регистры. Например, при обработке строки ее длину как результат вычисления нужно заслать в регистр CL. Однако если искать регистр среди свободных, то чаще первым свободным окажется AL и далее потребуется дополнительная пересылка MOV CL,AL. Если же задана рекомендация CL и он свободен, то сразу выделяется именно CL и пересылка ниже вырождается в команду MOV CL,CL. Подобные «пустые» пересылки автоматически исключаются на этапе генерации кода. Таким образом, рекомендованный регистр может сократить код. Если рекомендованный регистр уже занят — рекомендация игнорируется.
Второй особый случай: второй операнд команды регистр и этот регистр в данный момент не занят. В этом случае и первому операнду выделяется точно такой же регистр. Если это была пересылка — она автоматически уничтожится как и для первого особого случая, поскольку окажется «пустой».
Третий особый случай: второй операнд не регистр, но где-то ниже первый операнд данной команды будет использован для пересылки в некоторый конкретный регистр. Если до такого использования этот регистр не занимался и был свободен — он сразу и выделяется для первого операнда. В какой-то мере это просто общая форма первого особого случая. Точно так же команда пересылки где-то ниже выродится в «пустую» команду.

            Если особых случаев не обнаружено, то первому операнду выделяется регистр по общим правилам:

            Сначала проверяется, нет ли уже такого регистра (с точно такой же ссылкой на операнд как у второго операнда), если есть — этот регистр и выделяется.

            Если подходящего готового регистра не обнаружено, из всего диапазона допустимых регистров (или 8 или 16/32 битовых) ищется первый пустой с учетом свободности взаимосвязанных.

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

Выделение регистра или памяти в команде восстановления

            Выделение регистра или памяти второму операнду в команде восстановления не является последним этапом обработки, однако здесь распределение регистров всегда производится по «остаточному» принципу.

            Сначала создается текущая карта занятых и свободных регистров в данный момент.

            Затем, идя по выражению «вверх» ищется место, где заданный второй операнд «рождается». При этом все встречающиеся в командах регистры также отмечаются как занятые в карте регистров. А если попадается вызов подпрограммы, все регистры считаются неопределенными и второму операнду выделяется уже не регистр, а служебная переменная в памяти.

            Ищется подходящий свободный регистр из числа свободных нужного размера. Для адресных операндов рассматривается группа регистров ESI/EDI/EBP/EBX.

            Если регистр выделить не удалось, выделяется участок памяти нужного размера, вместо регистра задается адрес и размер статической памяти для программы увеличивается на эту длину.

Примеры распределения регистров



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

            1. Пример отдельного простого оператора присваивания. Чаще всего первым свободным регистром в таблице оказывается EAX, он и выделяется внутреннему операнду.
DCL(X,Y) FIXED(31);
X=Y;
000000 A10C000000   mov    eax,Y
000005 A308000000   mov    X,eax
            2. Пример двух операторов присваивания подряд. Модель «запомнила», что после команды mov X,eax в регистре eax сохранилась ссылка на X и команда mov eax,X выродилась в команду mov eax,eax которая в дальнейшем была отброшена.
DCL(X,Y,Z) FIXED(31);
X=Y;
000000 A10C000000   mov    eax,Y
000005 A308000000   mov    X,eax
Z=X;
00000A A310000000   mov    Z,eax
            3. Пример двух независимых операторов присваивания. Поскольку регистр EAX «освобождается» в модели сразу же в текущей команде, он тут же может быть распределен следующему операнду.
DCL(X,Y,Z,K) FIXED(31);
X=Y;
000000 A10C000000     mov    eax,Y
000005 A308000000     mov    X,eax
Z=K;
00000A A114000000     mov    eax,K
00000F A310000000     mov    Z,eax
            4. Пример распределения регистра для внутреннего операнда. В программе требуется проверить случай, когда оба массива X и Y нулевые. Результат сравнения с нулем запоминается в регистре AL с помощью команды SET, а затем переносится во внутренний операнд. Модель определила, что регистр AH свободен — он и выделяется внутреннему операнду. Включен режим компиляции, при котором выражения в условном операторе продолжают вычисляться, даже если конечный результат уже стал известен из предыдущих условий.
DCL (X,Y)(100) FIXED(31);
IF X=0 & Y=0 THEN …
000000 BF08000000   mov    edi,offset X
000005 B990010000   mov    ecx,400
00000A 32C0         xor  b al,al
00000C F3AE         repe   scasb
00000E 0F94C0       sete   al
000011 8AE0         mov  b ah,al               запоминание результата
000013 BF98010000   mov    edi,offset Y
000018 B990010000   mov    ecx,400
00001D 32C0         xor  b al,al
00001F F3AE         repe   scasb
000021 0F94C0       sete   al
000024 22E0         and  b ah,al                учет обоих сравнений
000026 7405         je     @1
            5. Пример распределения индексных регистров. Для массива X выделен «адресный» регистр EDI, для массива Y — ESI. В примере видно, что использование регистра EAX как индексного невыгодно, так как он часто используется в пересылках с более коротким кодом. «Свертки» адресации в SIB-байт не произошло, из-за того, что команды адресации оказались не смежными.
DCL (X,Y)(10,10) FIXED(31);
DCL (I,J)        FIXED(31);
IF X(I,J)^=Y(J,I) THEN …
000000 6B3D2C03000028 imul   edi,J,40
000007 A128030000     mov    eax,I
00000C C1E002         shl    eax,2
00000F 03F8           add    edi,eax
000011 6B352803000028 imul   esi,I,40
000018 A12C030000     mov    eax,J
00001D C1E002         shl    eax,2
000020 03F0           add    esi,eax
000022 8B876C010000   mov   eax,Y+0FFFFFFD4h[edi]
000028 3986DCFFFFFF   cmp   X+0FFFFFFD4h[esi],eax
00002E 7405           je     @1
            6. В этом примере, в отличие от предыдущего массивы используются с указателями, т.е. к индексной части добавляется еще базовая часть адреса. Постоянное «освобождение» регистров позволяет обойтись и в этом примере для всех внутренних операндов опять лишь тремя регистрами EAX, ESI и EDI.
DCL (X,Y)(10,10) FIXED(31)BASED;
DCL (I,J)        FIXED(31);
DCL (P,Q)        PTR;
IF P->X(I,J)^=Q->Y(J,I) THEN …
000000 8B3D14000000   mov    edi,Q
000006 6B050C00000028 imul   eax,J,40
00000D 03F8           add    edi,eax
00000F A108000000     mov    eax,I
000014 C1E002         shl    eax,2
000017 03F8           add    edi,eax
000019 8B3510000000   mov    esi,P
00001F 6B050800000028 imul   eax,I,40
000026 03F0           add    esi,eax
000028 A10C000000     mov    eax,J
00002D C1E002         shl    eax,2
000030 03F0           add    esi,eax
000032 8B47D4         mov    eax,0FFFFFFD4h[edi]
000035 3946D4         cmp    0FFFFFFD4h[esi],eax
000038 7405           je     @1
            7. Пример, отличающийся от предыдущего тем, что массив X теперь имеет тип FLOAT длиной 8 байт. Для преобразования целого во FLOAT используется системный вызов call ?QI3_F который может изменить все регистры. Поэтому индексный внутренний операнд запоминается в служебной переменной @0018, а после системного вызова восстанавливается. Первоначально для индекса выделяется EDI, а после восстановления уже EBX, так как через этот регистр передается адрес для системного вызова сравнения элементов типа FLOAT call ?FC44R. Несколько смежных команд адресации были «свернуты» в адресацию с SIB-байтом.
DCL X (10,10) FLOAT(53) BASED;
DCL Y (10,10) FIXED(31) BASED;
DCL (I,J)     FIXED(31);
DCL (P,Q)     PTR;
IF P->X(I,J)^=Q->Y(J,I) THEN…
000000 8B3D10000000   mov    edi,P
000006 6B050800000050 imul   eax,I,80
00000D 03F8           add    edi,eax
00000F A10C000000     mov    eax,J
000014 C1E003         shl    eax,3
000017 03F8           add    edi,eax
000019 893D18000000   mov    @0018h,edi                запоминание
00001F 8B3514000000   mov    esi,Q
000025 6B050C00000028 imul   eax,J,40
00002C 03F0           add    esi,eax
00002E A108000000     mov    eax,I
000033 8B5C86D4       mov    ebx,0FFFFFFD4h[esi+eax*4]
000037 F9             stc
000038 E800000000     call   ?QI3_F
00003D 8B1D18000000   mov    ebx,@0018h                восстановление
000043 8D5BA8         lea    ebx,0FFFFFFA8h[ebx]
000046 E800000000     call   ?FC44R
00004B 7405           je     @1

Заключение

            Рассмотренный метод распределения регистров, конечно, не является единственно возможным. Однако это надежный и сравнительно простой способ, отлаженный и проверенный в течение многих лет, при этом его объем составляет около 4% от числа всех команд компилятора.

            Особенностью данного метода является, во-первых, моделирование текущего состояния всех регистров в части наличия ссылок на одинаковые или разные объекты, а во-вторых, генерирование при необходимости служебных команд запоминания и восстановления. Причем окончательное распределение откладывается до команды восстановления, так как операционная обстановка к моменту восстановления может измениться. При удачном стечении обстоятельств команда запоминания или восстановления может выродиться в «пустую» пересылку, которая будет отброшена на следующем этапе обработки.

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

Литература

1. «PL/I language Programmer’s Guide» Digital Research, Сalifornia 1982 http://bitsavers.org/pdf/digitalResearch/pl1/
2. М.Гук, В. Юров «Процессоры Pentium 4, Athlon и Duron». СПб.: Из-во Питер, 2001

Автор: Д.Ю.Караваев. 05.03.2012

Последняя правка: 2018-10-29    16:00

Оцените

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Двадцать тысяч строк кода, которые потрясут мир?

Почему владение/заимствование в Rust такое сложное?

Масштабируемые архитектуры программ

Почему Хаскелл так мало используется в отрасли?

Бесплатный софт в мышеловке

Исповедь правового нигилиста

Русской операционной системой должна стать ReactOS

Почему обречён язык Форт

Программирование без программистов — это медицина без врачей

Электроника без электронщиков

Статьи Дмитрия Караваева

●  Идеальный транслятор

●  К вопросу о совершенствовании языка программирования

●  О реализации метода оптимизации при компиляции

●  О реализации метода распределения регистров при компиляции

●  О распределении памяти при выполнении теста Кнута

●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●  О размещении переменных в стеке

●  Сколько проходов должно быть у транслятора?

●  Чтение лексем

●  Экстракоды при синтезе программ

●  Об исключенных командах или за что «списали» инструкцию INTO?

●  Типы в инженерных задачах

●  Непрерывное компилирование

●  Об одной реализации специализированных операторов ввода-вывода

●  Особенности реализации структурной обработки исключений в Win64

●  О русском языке в программировании

●  Формула расчета точности для умножения

●  Права доступа к переменным

●  Скорость в попугаях

●  Крах операции «Инкогнито»

●  Предопределенный результат

Компьютерный юмор

Прочее

Последние комментарии

2018/12/08 23:03 ••• Попов Михаил
✎ Программирование без программистов — это медицина без врачей

2018/12/07 08:57 ••• Автор сайта
✎ Почему обречён язык Форт

2018/12/07 08:36 ••• Автор сайта
✎ Нужны ли беззнаковые целые?

2018/12/03 13:51 ••• kt
✎ Экстракоды при синтезе программ

2018/11/30 17:56 ••• Freeman
✎ Изменение приоритетов операций

2018/11/30 17:20 ••• Автор сайта
✎ Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

2018/11/26 14:23 ••• Автор сайта
✎ Так ли нужны операции «&&», «||» и «^^»?

2018/11/18 15:21 ••• Freeman
✎ Устарел ли текст как форма представления программы

2018/11/17 03:28 ••• Comdiv
✎ Изменение длины объекта в стеке во время исполнения

2018/11/16 12:53 ••• Автор сайта
✎ Помеченные комментарии

2018/11/11 14:01 ••• Александр Коновалов aka Маздайщик
✎ Нерабочий код

2018/11/11 13:39 ••• Александр Коновалов aka Маздайщик
✎ О русском языке в программировании