Экстракоды при синтезе программ
Введение
Впервые термин «экстракод» я услышал еще применительно к командам БЭСМ-6. Сейчас это слово практически не используется, наиболее близкое понятие – «системный вызов». Из-за особенностей системы команд БЭСМ-6, те экстракоды действительно больше напоминали дополнительные встроенные инструкции, чем, например, вызов функции в MS-DOS с помощью INT 21H.
Смысл термина «экстракод» вполне прозрачен: это расширение системы команд для того, чтобы создать из реальной машины виртуальную машину для заданного языка, например, Паскаль-машину или Лисп-машину. А транслятор после этапа анализа исходного текста программы должен провести синтез программы – т.е. перевести результаты анализа в команды этой виртуальной машины.
Кстати, Лисп-машину когда-то действительно собирались воплотить в аппаратуре. Однако создание таких машин для конкретных языков было бы экономически слишком невыгодно по сравнению с универсальными и поэтому мы сейчас используем исключительно универсальные (с точки зрения языков) компьютеры. Правда, по мере развития и удешевления технологий разработки и производства процессоров, экономические преимущества универсальных систем команд над специальными могут стать не столь очевидными.
Пример использования экстракода при компиляции
Я утверждаю, что понятия языка PL/1 лучше, чем у многих других языков отражены в командах архитектуры IA-32, поскольку в момент разработки процессора 8086 (вторая половина 70-х годов) требования поддержки языков высокого уровня ориентировались на основные языки того времени, среди которых заметное место занимал и PL/1.
Рассмотрим на простом примере, как понятия языка высокого уровня преобразуются в команды IA-32. Например, в PL/1 есть такие объекты, как строки постоянной длины.
В рассматриваемом подмножестве языка длина такой строки не должна превышать число, занимающее байт. Со строками можно работать различным образом, например, сравнивать на равенство или даже на «больше-меньше». А в архитектуре IA-32 есть команда CMPSB, которая как раз и сравнивает две «цепочки» байт в памяти. Казалось бы, и компилятор должен реализовать сравнение строк постоянной длины с помощью одной этой команды (с повторением) REPE CMPSB. Однако на самом деле сравнение реализовано так:
declare
s1 char(10),
s2 char(15);
if s1>s2 then …
BF0A000000 mov edi,offset S2
B00F mov al,15
BE00000000 mov esi,offset S1
B10A mov cl,10
E800000000 call ?SCCCM
7505 jbe @1
…Почему же даже для такой простой операции потребовался системный вызов? Дело в том, что команда CMPSB близка к понятию сравнения строк в PL/1, но не полностью совпадает. В языке, если сравниваются две строки разной длины, то сначала более короткая из них дополняется пробелами, а уже после идет само сравнение.
Команда же CMPSB по определению не сравнивает строки разной длины. Зачем же потребовалось вводить в язык такое странное требование, как продолжать сравнивать одну строку, когда другая уже закончилась? Как раз в понятиях языка все логично. Короткая строка дополняется пробелами не только при сравнении, но и при присваивании в более длинную строку. Тогда после такого присваивания и сравнения, получится правильный результат «строки равны», хотя они и продолжают иметь разную длину. Если же заканчивать сравнение по исчерпанию одной из строк, можно получить неверный результат сравнения, например, для строк «12345» и «123456», которые, очевидно, не равны.
Вот если бы в процессоре была команда сравнения PL1_CMPSB, которая не только бы выполняла действия, аналогичные CMPSB, но и по значению, скажем, в регистре AL определяла бы, сколько еще байт осталось в более длинной строке и сравнивала бы этот остаток с пробелами, вот тогда компилятор мог бы генерировать сравнение строк в смысле языка PL/1 одной этой командой.
А ведь в примере компилятор как раз это и делает. Только несуществующую команду PL1_CMPSB он заменяет вызовом системной подпрограммы, которую я называю экстракодом. Этот конкретный экстракод имеет странное имя-аббревиатуру ?SCCCM, буквы которой систематизированы и в данном случае показывают, что идет работа со строками (String) и сравниваются (Compare) две строки постоянной длины (Сhar и Char), находящиеся не в стеке, а в «статической» памяти (Memory). Система при составлении названий экстракодов нужна, поскольку их разновидностей достаточно много.
Отличия экстракодов от системных подпрограмм
Может показаться, что слишком много внимания уделено обычному вызову системной процедуры при генерации программы. Но это не совсем обычный вызов.
Первое отличие экстракодов от «обычных» вызовов подпрограмм – это отсутствие общих правил передачи параметров. В этом они больше похожи на команды IA-32, где тоже нет общих правил, а в каждом случае могут быть свои. Например, просто из вида команды REPE CMPSB, не имеющей параметров, невозможно догадаться, что она одновременно использует и меняет регистры ESI, EDI и ECX.
Конечно, и передача параметров в «обычные» подпрограммы может быть организована через регистры, а не, например, через стек. Собственно так и сделано в 64-разрядных Windows API, где используются регистры RCX, RDX, R8 и R9. Но там всегда используются эти регистры, в то время как в каждом конкретном экстракоде (как и в каждой конкретной команде) могут быть разные. Поэтому в приведенном выше примере загрузка адресов и длин строк идет в конкретные регистры, сразу, так сказать, на свои места и дополнительных пересылок внутри экстракода уже не требуется.
Второе отличие экстракода от «обычной» системной подпрограммы – его полная открытость для компилятора. В отличие от идеи модуля-«черного ящика», когда снаружи известен только вход и выход, компилятору известно, какие регистры «портит» (т.е. использует) данный экстракод при выполнении.
Это позволяет проводить ряд оптимизаций при распределении регистров. Хотя часто и при работе с «обычными» подпрограммами компилятор также использует некоторую информацию (например, соглашение о не меняющихся внутри подпрограммы ESI и EDI), в случае экстракода работа идет по-другому. Соглашение о ESI и EDI по существу означает запрет на их использование. Точнее, подпрограмма при использовании должна сохранить, а затем восстановить их значения. Внутри же экстракода, как и внутри команды, никаких запретов нет и сохранять регистры не требуется (например, они и являются результатом), а при необходимости это сделает компилятор «снаружи» вызова.
Наконец, третье отличие от простых вызовов системных подпрограмм – это отсутствие общих правил возврата результата. В примере со сравнением строк экстракод возвращает не какое-либо значение в регистре EAX как типичная подпрограмма, а прямо состояние регистра флагов процессора, собственно как это и должна делать команда сравнения CMPSB (так как внутри экстракода ?SCCCM она и является основным действием).
Все эти отличия делают экстракоды более похожими на команды, чем на подпрограммы, а стиль генерации программы экстракодами больше похожим на программирование на ассемблере, хотя формально в программе получается много вызовов системных подпрограмм.
Правда, если «тело» экстракода короткое, его можно вставить в программу напрямую, без команды вызова. Но обычно команд внутри экстракода достаточно много, чтобы не обращать внимания на экономию времени за счет исключения инструкций вызова и возврата, особенно учитывая, что при подстановке экстракодов, так сказать, «inline», код программы сильно увеличивается и это совсем не ускоряет ее исполнение.
Могут возразить, что понятие экстракода избыточно, поскольку уже есть термин «интринсик». На мой взгляд, между экстракодом и интринсик’ом есть такие же различия, как между программированием «снизу вверх» и «сверху вниз». Интринсик – это момент перехода от абстрактных команд к командам конкретного процессора («сверху-вниз»), а экстракод – это конструирование новых «команд» из имеющихся в процессоре для применения в программе (т.е. «снизу-вверх»). При этом в обоих случаях могут генерироваться одни и те же реальные команды процессора.
Да и слово «интринсик» очень неудобопроизносимое по-русски.
Типы экстракодов при компиляции выражений
Несмотря на то, что входные и выходные параметры экстракодов могут быть организованы совершенно по-разному, при компиляции выражений над объектами, которые не помещаются в обычные регистры (например, строки или даже 8-байтные числа в формате IEEE-754), получается 4 группы схожих экстракодов, в зависимости от операндов или как просто переменных, или как результатов предыдущих вычислений. Например, вот 4 разновидности экстракода операции деления :
declare
(x,y,z) float(53);
z=x/y; оба операнда в переменных, экстракод деления ?FDF_M
z=(x+1)/y; левый операнд в стеке, экстракод деления ?FDF_L
z=x/(y+1); правый операнд в стеке, экстракод деления ?FDF_R
z=(x+1)/(y+1); оба операнда в стеке, экстракод деления ?FDF_SРазличаются эти разновидности, естественно, способом загрузки исходных параметров, или через указатель стека ESP (RSP) или через адрес переменной. При генерации выражения компилятор выбирает нужный тип экстракода исходя из числа операций внутреннего представления программы. Если операнд загружается одной единственной операцией – значит, он берется из переменной. Если же операций несколько – значит, данный операнд сам является результатом вычисления и как результат уже помещен в стек предыдущими сгенерированными командами.
В случае работы с FPU процессора в большинстве случаев используется стек FPU, а не стек самого процессора. Только в этом случае последний из типов экстракода, например, деления ?FDF_S может быть сведен к генерации единственной команды FDIV.
Наибольшее число разновидностей экстракодов получается при работе с комплексными числами, поскольку в этом случае каждая из 4 групп экстракодов делится еще на 3 подгруппы, в зависимости оба ли операнда комплексные или один операнд комплексный, а другой – действительный.
Пример оптимизации при использовании экстракодов
Рассмотрим еще один простой пример, часто встречающийся в программах на PL/1:
s=substr(s,2); Здесь из строки s выбрасывается первый символ, что обычно используется в цикле обработки символов, пока строка s не станет пустой. В данном случае обрабатывается объект – строка переменной длины (ее текущая длина записана первым байтом по адресу строки).
declare
s char(*) varying;
s=substr(s,2);
B202 mov dl,2
BE00000000 mov esi,offset S
8BFE mov edi,esi
E800000000 call ?VS2AD
E800000000 call ?SMCVFРеализация отбрасывания первого символа строки выполнена с помощью двух экстракодов, один из которых выделяет подстроку, а второй переписывает ее в заданную строку, в данном случае в ту же самую.
Причина, по которой нельзя выполнить это прямо двумя командами типа LEA ESI,[ESI+EDX]-1 и REP MOVSB по сути та же самая, что и в предыдущем примере: эти команды близки, но не тождественны командам PL/1-машины «выделение подстроки» и «присвоение строке».
Поэтому хотя команды LEA и MOVSB и являются основами соответствующих экстракодов, требуется выполнить еще ряд действий. Например, при выделении подстроки в смысле PL/1 нужно еще убедиться, что строка не пустая и заданное начало подстроки не выходит за ее границу. А при присваивании строки в общем случае может еще потребоваться дописывание пробелами, как и в разобранном выше сравнении строк.
В данном примере видно, как информация о работе экстракодов используется для сокращения команд подготовки параметров. Компилятор «знает», что экстракод выделения подстроки ?VS2AD не использует EDI и поэтому сразу загружает его значением, нужным для последующей пересылки. А поскольку это значение сначала совпадает с загрузкой ESI, вместо команды mov edi,offset s используется более короткая команда mov edi,esi.
Экстракод ?VS2AD возвращает результат через регистр ESI (начало подстроки) и AL (длина подстроки), причем всегда еще и CL=AL. Для работы второго экстракода пересылки ?SMCVF нужно установить значения в регистры ESI, EDI и CL, поскольку внутри все сведется, в конце концов, к выполнению команды REP MOVSB.
Но регистр EDI уже установлен, нужное значение в регистре ESI загружено после работы первого экстракода и в CL уже находится длина переписываемой подстроки. Поэтому компилятору можно сразу генерировать вызов второго экстракода без дополнительных загрузок регистров. Получается, что на выполнение оператора отбрасывания первого символа строки в программе потребовалось всего 19 байт кодов.
При этом выполнение требуемых действий осуществляется внутри экстракодов максимально эффективно для архитектуры IA-32, а именно командами загрузки адреса LEA и «цепочечной» пересылкой MOVS. Кроме этого внутри экстракодов выполняются дополнительные проверки и действия, необходимые для соблюдения требований языка PL/1. Компилятору не нужно каждый раз генерировать эти действия, он имеет дело только с экстракодами, по существу со своей специальной системой команд.
Конечно, всегда имеются и «обычные» встроенные функции, например, ACOS, которые компилятор обрабатывает как стандартный вызов подпрограммы без привлечения понятия экстракода. Эти встроенные функции имеют такие же общие правила передачи параметров и возврата результата, как и подпрограммы, описанные пользователем, и ничем от таких подпрограмм не отличаются, за исключением того, что их не нужно описывать и их «тела» находятся в той же системной библиотеке, что и «тела» экстракодов.
Отличие компилятора от транслятора
Немного отвлекаясь от темы статьи, хотелось бы отметить, что я везде использую термин «компилятор», а не «транслятор».
В определении отличия компилятора от транслятора, на мой взгляд, существует некоторая путаница. Например, в Википедии прямо написано, что компиляция – это трансляция программ. Получается, что компилятор и транслятор – это одно и то же.
Наверное, правильнее было бы обратить внимание в той же Википедии на статью «литературная компиляция», поскольку человек, первый применивший термин «компиляция» в программировании, конечно же имел ввиду именно ее аналог в литературе. Эта компиляция происходит от латинского слова «compilatio» – ограбить.
Получается, что «компилятор» – это «грабитель». Ну, или менее экзотично, литературный и компьютерный компиляторы создают «свое» с помощью «чужого». На мой взгляд, это и есть главное отличие компилятора от транслятора. В своей работе, он использует «чужие», заранее написанные коды с помощью системных вызовов или, как в рассмотренных случаях, с помощью экстракодов.
Если же «чужие» коды в принципе не используются – это транслятор. Например, не может быть компилятора с ассемблера, поскольку никаких «чужих» кодов при генерации ассемблерных команд ему использовать не требуется. Но вернемся к экстракодам.
Случай совпадения команд виртуальной и реальной машины
Разумеется, если команды виртуальной машины совпадают с реальными командами, экстракоды исчезают. Например, это происходит при работе с целыми числами:
declare
(x,y,z) fixed(31);
x=y*10-z/4;
6B05040000000A imul eax,Y,10
8B1D08000000 mov ebx,Z
C1FB02 sar ebx,2
2BC3 sub eax,ebx
A300000000 mov X,eaxЗдесь все действия однозначно отображаются на соответствующие команды процессора, хотя некоторые встроенные функции, например min и max могут реализовываться и через экстракоды.
Экстракоды и CISC-команды
Анализ применения экстракодов заставил даже по-новому взглянуть на RISC- и CISC-процессоры (т.е. на процессоры с сокращенным и обычным набором команд).
Безусловно, есть ряд задач, которые успешно решаются упрощенным набором команд. Однако в большом числе случаев RISC-команды создают только иллюзию упрощения решения, а на самом деле перекладывают сложность выполнения с процессора на программу. Команды становятся проще, а программа из них сложнее, да и число обращений к памяти больше.
Экстракоды при компиляции с языка достаточно высокого уровня – это, конечно, аналог CISC-команд. Но даже в простой операции сравнения строк имеющейся CISC-команды CMPSB оказалось недостаточно для полного соблюдения требований языка.
Я бы предпочел, чтобы, например, все действия гипотетической команды PL1_CMPSB выполнялись бы внутри процессора. Это еще усложнило бы CISC-команды, но повысило бы общую производительность программы. Т.е. для упрощения компиляции и снижения числа обращений к памяти не хватает именно CISC- , а не RISC-команд. И с помощью экстракодов приходится создавать все новые и новые CISC-команды.
В конце концов, количество транзисторов на кристалле все время увеличивается. Для организации полноценной памяти на одном кристалле их все равно мало, а для реализации даже полной системы команд уже с избытком. Так пусть уж процессор больше действий выполняет внутри себя, не обращаясь к памяти.
Преимущества такого подхода хорошо видны на примере команды извлечения квадратного корня. Эта команда необходима во многих алгоритмах. Конечно, можно было бы не включать команду FSQRT в FPU процессора, а вычислять ее подпрограммой (например, по методу Ньютона). Однако вряд ли удалось бы реализовать такое вычисление быстрее, чем микропрограммой в кристалле процессора. Притом, что во время (длительного) выполнения команды FSQRT возможно параллельное выполнение других команд, например, целочисленной арифметики, что еще больше увеличивает общую производительность.
Заключение
Технология генерации программ с помощью экстракодов, как и любая другая, имеет и достоинства и недостатки.
Экстракоды могут уменьшить число уровней абстракции при приближении понятий языка к машинным командам. Причем, если понятия языка хорошо отображаются на процессорные инструкции, экстракоды становятся короткими и быстрыми, в ряде случаев просто исчезая и однозначно превращаясь в соответствующие команды процессора.
Использование экстракодов с одной стороны несколько усложняет компилятор, поскольку появляется большое число разновидностей передачи параметров и возврата результатов, что отражает архитектуру процессора, в данном случае команды IA-32. Зато, с другой стороны, весь процесс компиляции упрощается и сводится к единообразным вызовам экстракодов даже в случае достаточно сложных действий, над сложными объектами, описанными в программе.
В ряде компиляторов приняты единые правила передачи параметров и возврата результата, как для системных подпрограмм, так и для подпрограмм, написанных пользователем. Это, конечно, упрощает компилятор, но увеличивает число пересылок параметров прежде, чем над ними будет выполнено нужное действие, а это, в свою очередь, снижает эффективность выполнения.
Экстракоды находятся между двумя крайними стилями генерации кодов программы. Одна крайность – это генерация в виде байт-кода, когда виртуальная машина совершенно не похожа на реальную, и требуется интерпретатор для исполнения каждой виртуальной команды. Другая крайность – это генерация строго в машинные коды, по существу программирование на ассемблере.
Экстракоды позволяют с одной стороны сохранить некоторые особенности архитектуры процессора и. тем самым, повысить эффективность особенно за счет сокращения числа подготовительных действий. С другой стороны, при компиляции экстракоды позволяют оставаться на достаточно высоком уровне абстракции языка за счет использования более сложных команд (пусть и реализованных через подпрограммы), чем реально существующие процессорные инструкции. При этом генерируемый код остается вполне компактным.
