Автор:
Anton Ertl
Дата публикации: 1992 год
Оригинал статьи:
A new approach to Forth native code generation.
Перевел:
be_nt_all
Новый подход к генерации Фортом машинного кода
Аннотация
RAFTS — это каркас для применения современного состояния искусства и технологии компиляции для компиляции Форта. Сердцем RAFTS является простой метод трансформации Форт программ в диаграмму потоков данных и форму статического одиночного присваивания. К этим формам могут быть применены стандартные техники генерации и оптимизации.
В частности, RAFTS использует межпроцедурное распределение регистров для почти полного исключения доступа к стеку. Он также удаляет почти все изменения указателя стека. Подстановка и оптимизация хвостовых вызовов сокращают избыточные вызовы слов. RAFTS компилирует все Forthы, включая трудные случаи, типа неизвестной глубины стека, слов PICK, ROLL и EXECUTE. И наконец, RAFTS разработан для интерактивных Forth систем; он не ограничен пакетными компиляторами.
1 Введение
Традиционно, Forth реализуется с использованием интерпретатора шитого кода [Tin81]. Это делает компилятор крайне простым: слово компилируется путём подстановки его адреса в текущее определение. Узкие по производительности места обходятся путём ручного переписывания критичных участков на ассемблере. Это может быть уместным в программировании встраиваемых систем, где нет требования переносимости, имеющего место в программных системах общего назначения.
Другой популярный путь к эффективности — создание специальной аппаратуры, можно привести примеры множества исследовательских прототипов и нескольких коммерчески доступных процессоров, разработанных для эффективной работы Форта [Koo89, HFWZ87]. Код для таких стековых машин генерируется простым, компилятором со щелевой оптимизацией.
Последние исследования [Ung87, CU89, KB92] доказали, что нетрадиционные языки могут быть эффективно реализованы на общепринятой аппаратуре с использованием агрессивных техник компиляции, выгоды специализированных архитектур компенсируются улучшением технологии устройств с широко доступной RISC архитектурой.
Особые требования Форта — это быстрая работа со стеком и быстрый вызов процедур. Оптимизация работы со стеком особенно важна для RISC процессоров, где доступ к стеку не может быть скрыт режимах адресации с автоинкрементом/автодекрементом, и, обычно, требует двух инструкций. Уйти от этих особых требований Форта при отображении на общепринятую «железо» проще, чем для друших нетрадиционных языков. Однако, особое внимание следует уделить сохранению интерактивности Форта.
RAFTS — это каркас для применения современного состояния искусства и технологии компиляции для компиляции Форта, а именно — межпроцедурного распределения регистров (Раздел 3.5), подстановки, оптимизации хвостовых вызовов (Раздел 3.3), выбора и планирования инструкций (Раздел 3.1). Некоторые новые техники введены специально для нужд работы с Фортом: простая методика трансформации Форт-программ в диаграммы потоков данных (Раздел 3.1) и форму со статическими единичными присваиваниями (Раздел 3.2), мнинимизация обновлений указателя стека (Раздел 3.4), обход случая неизвестной высоты стека (Раздел 3.6), PICK и ROLL (Раздел 3.8).
2 Родственные работы
Парсеры (синтаксические анализаторы) могут преобразовывать постфиксный код в деревья, напр. диаграммы потоков данных. Но парсеры не могут обрабатывать слова манипуляции стеком или несколькими стеками, они не могут производить DAGи и методика из Раздела 3.1 проще.
Стековые языки используются как промежуточный код при компиляции. При генерации кода такие компиляторы испытывают проблемы, близкие к генерации машинного кода из Форта[^1]. Генератор кода из Amsterdam Compiler Kit (ACK) похож на RAFTS использованием стека, но он выполняет все задачи по генерации кода в одно и то же время [TvSKS83]. Во всех остальных вопросах ACK другой: в отличие от RAFTS, он ничего не делает на Forth-уровне, ACK выполняет все возможные оптимизации на уровне постфиксного кода, поскольку его цель — независимость от машины.
[^1]: Однако, они обычно не имеют дело с вещами вроде SWAP, и там гораздо сильней акцент на (локальные) переменные.
Рис. 1 . Построение диаграммы потока данных (три снимка)
Имеется несколько компиляторов Форта, генерирующих машинный код [Ros86, Alm86]. Обычно они начинают с генерации подпрограммного шитого кода, а затем выполняют подстановку небольших подпрограмм, и щелевую оптимизацию полученного кода, чтобы исключить излишние pushи и popы. Излишние манипуляции со стеком всё ещё остаются. Роуз сообщает, что "в результате машинный код в два иди три раза медленнее, чем эквивалентный код, написанный на ассемблере, в основном из за использования стека вместо регистров."
Однако же некоторые компиляторы всё-таки сокращают излишнюю работу со стеком весьма изощренными способами. JForth V3.0 может сохранять пять значений в регистрах и полностью оптимизирует слова типа SWAP и ROT, исключая их. Эта оптимизация выполнима только для последовательности определённых примитивов. RAFTS же обычно всегда сохраняет в регистрах значение элементов стека. Неинтерактивный (т.е. пакетный) компилятор Almy CFORTH сохраняет в регистрах два значения и сокращает манипуляции со стеком [Alm86]. Он хранит значения в регистрах между границами базовых блоков. Однако отсутствие глобального распределения регистров в его компиляторе ведёт, в результате, к большому количеству перетасовок в регистрах, если доступно более чем два регистра.
3 RAFTS
3.1 Базовые блоки.
Диаграммы потоков данных. Базовые блоки состоят только из примитивов, таких как `+` и `!` (сохранить), литералов, констант и переменных, а также слов для работы со стеком, таких как `SWAP` и `R@`.
Слова работы со стеком компилируются путём их выполнения. При компиляции каких нибудь других слова, компилятор кладёт на стек, или снимает со стека столько элементов, сколько выполняемое в данный момент слово. Но само слово не выполняется. Вместо этого компилятор строит запись (структуру), которая содержит слово (чтобы указать тип узла) и операнды, взятые со стека. Указатель на эту структуру данных кладётся на стек вместо результата. Таким способом компилятор строит диаграмму потоков данных[^2] (см. Рис. 1). Эта структура данных широко используется в конструировании компиляторов, так что для дальнейшей компиляции могут быть использованы хорошо известные техники.
[^2]: Для основных блоков граф будет направленным ациклическим графом (ДАГом); в учебниках по компиляции его называют просто Даг и рисуют его сверху-вниз.
Дальнейшая обработка. Следующие три шага преобразования базовых блоков из форта в машинный код это выбор инструкций, планирование (переупорядочивание) инструкций и распределение регистров. Они были подробно описаны в литературе, так и здесь они не будут объяснятся углубленно.
При выборе инструкций операторы, скомбинированные в графы потоков данных, преобразуются в корректные инструкции для целевой машины, превращая DAG оператора в DAG инструкции (см. Рис. 2). На сегодняшний день при выборе инструкций для CISC архитектур используют автомат разбора дерева генерируемый из дерева грамматик инструментами вроде Burg [FHP91]. Для RISC вполне подходит более простой подход: спускаемся вниз по графу и комбинируем по пути столько операторов, сколько представляется оптимальным для большинства RISC архитектур.
Рис. 2. Выбор и переупорядочивание инструкций (для MC88100)
Все элементы-ссылки на стек в настоящее время размещены в псевдорегистрах (px на Рис. 2), которые можно использовать в неограниченных количествах[^3]; внутри базового блока доступ к стеку исключается.
Распределение регистров заменяем псевдорегистры реальными регистрами, сливая избыточные псевдорегистры в память. RAFTS использует межпроцедурное распределение регистров, которое обсуждается в Разделе 3.5. В то же время, важно иметь в виду, что: указатели в ДАГе инструкций соответствует непосредственно псевдорегистрам; в частности, на границах основного блока указатели на стек также соответствуют псевдорегистрам (уже перед выбором инструкций).
[^3]: Действительно, для того, чтобы сделать преобразование в SSA-форму (static single assignment), важно, чтобы регистры не использовались повторно.
Планирование (переупорядочивание) инструкций упорядочивает узлы дага инструкций, т.е. преобразует DAG в список (см. рис. 2). Для RISCs цель планирования — избежать простоев конвейера. Стандартный алгоритм упорядочивания RISC инструкций — алгоритм LS (list scheduling) [GM86]. Для CISCs инструкций при упорядочивании минимизируется "давление на регистры". Это обычно выполняется при локальном распределении регистров [ASU86].
Вершины графа потока данных частично упорядоченны через его грани. Но для граней, которые вводятся в RAFTS, этого недостаточно, поскольку они отражают лишь зависимость от стека, а не от памяти. Поэтому компилятор также отслеживает доступ к памяти и вносит дополнительные грани между получениями из памяти и сохранением в память.
Подробности. Обрисуем некоторые подробности конструирования графа потоков данных: Если код принимает на входе со стека (стеков) некоторые параметры, компьютер пытается получить к ним доступ. Таким образом, компилятор должен обеспечить достаточное количество элементов в стеке. Эти элементы строятся для регистров, где будут находится при выполнении элементы стека при входе в основной блок.
Некоторые примитивы имеют несколько результатов, которые не слишком то вписываются в модель графе потока данных. Эти слова могут быть разделены на два класса: слова, которые действительно имеют несколько результатов, например, `/ MOD`, и слова с двойной точностью результата. Первые можно разделить на две операции, последнее решаются помещением указателя на два элемента в одной той же записи.
Есть также несколько примитивов, не возвращающих результатов, напр. `!`. Если вершины графа потока данных доступны только со стека, эти операции, и предшествующие им могут быть потеряны. Хотя такая ликвидация мертвого кода желательна в случаях вроде `drop`, сохранения в память удалять не следует. Поэтому компилятор запоминает их в специальный массив.
Если компилятор написан в форте, частное использования им стека не должно конфликтовать с использованием для компиляции. Это легко достичь, используя различные стеки для различных целей.
3.2 Управляющие структуры
Управляющие структуры соединяют основные блоки. Это создает проблемы согласования основных блоков.
Расщепление потока управление (`IF`, `WHILE` и `UNTIL`) просто: При входе в него значения могут находится в регистрах. Объединение потоков управления (`ENDIF` и `BEGIN`) несколько сложнее [^4] : Соответствующие элементы стека объединяемых основных блоков, как правило, не располагаются в одном и том же регистре. На этот момент компилятор вставляет после слияния ?-функции (см. Рис. 3). ?-функции не соответствуют реальному коду (позднее они удаляются); они просто указывают, какие значения достигают точки объединения. Программа сейчас находится в SSA-форме (static single assignment) [CFR + 91], которая является прекрасным представлением для целей анализа и оптимизации. Оптимизации были подробно описаны в литературе, и здесь они не будут объяснятся углубленно.
[^4]: Кроме того, мы могли бы сделать объединение более простым, а расщепление — более сложным, установив, что значения должны оставаться при объединении в тех же регистрах.
Рис. 3. SSA форма для `IF SWAP ENDIF` и преобразование ункций в перемещения
После выполнения оптимизаций, SSA-форма может быть легко преобразована в более выполняемую форму: Каждая ?-функция заменяется перемещениями в родительском основном блоке (См. рис. 3). Если один из соединяемых основных блоков имеет несколько наследников (т.е. концы с расщеплением потока управления), движения должны быть включены в новый, пустой базовый блок. Многие из добавленных перемещений будут удалены при распределении регистров.
3.3 Вызовы
Слова и их вызовы обрабатываются как другие структуры управления: точка входа слова является объединением потоков управления, так достигается последовательное состояние. В точке входа аргументы вызывающей стороны снова представляются с помощью ?-функций. В дальнейшем они будут преобразованы в перемещения на вызывающей стороне. Как и другие расщепления управляющего потока, EXITы не вызывают проблем, пока у нас не будет несколько выходов в слове. Если слово имеет несколько EXITов, оно обрабатывается так, как будто сразу перед выходом имеется объединение потоков управления.
Подстановка стала отправной точкой большинства Форт компиляторов машинного кода. В фреймвоке RAFTS, она может устранять накладные расходы на вызовы и возвраты и изменение указателя стека, может улучшить распределение регистров и выявить возможности для дальнейшей оптимизации. При подстановке важно решить, что ей подлежит [CMCH92].
Если последнее полезное слово (т.е. не стековый манипулятор) это вызов, может быть применена оптимизация хвостового вызова: вызов преобразуется в переход на вызываемое слово, возврат из которого произойдёт в слово, вызвавшее вызывающее слово. Конечно, такая оптимизация не должна быть выполнена, если слово делает "жуткие вещи" с адресом возврата (например, выбрасывает его).
3.4 Обновления указателя стека
Почти все обновления указателя стека могут быть устранены оптимизацией: компилятор просто запоминает, насколько физический указатель стека отличается от логического указателя стека и обновляет это смещения во время компиляции. Есть только несколько случаев, когда обновление физическое указателя стека должна быть сформировано: слово может быть вызвано из нескольких мест, которые обычно имеют разные смещения. Компилятор присваивает смещения входа слова смещению одного из вызовов. А для других вызовов перед вызовом обновляется указатель стека. Это может привести к различным смещениям при объединении потоков управления. Поэтому, перед таким соединением должен быть сгенерирован еще один раунд обновления указателя, чтобы сделать смещения равными.
3.5 Распределение регистров
Учитывая высокую частоту вызовов (12% выполняемых примитивов [Koo89]), необходимо межпроцедурное распределение регистров, чтобы сделать использование регистров эффективным. В противном случае большая часть времени будет потрачена га сохранения и восстановления регистров при входе и выходе в процедуры, и вокруг их вызовов.
Есть ряд хороших алгоритмов распределения регистров, но еще не ясно, какой из них наиболее подходящий: он должна хорошо выполнять глобальное и межпроцедурное распределение, но в целях сохранения интерактивности, он не должен занять много времени.
Распределение регистров методом раскраски графа [Cha82, CH90, Bri92], являющееся сейчас стандартным способом, требует много времени и памяти. Иерархическая раскраска графа [CK91] выглядит лучше. Другие альтернативы — коагуляция [Mor91] и Межпроцедурные аллокаторы [Cho88].
Куда сливать. В маловероятном[^5] случае, что необходимо больше регистров, чем предусмотрено процессором, некоторые псевдорегистры сливаются в память. В обычных компиляторов они были, бы местоположены на стеке. Но в Forthе, это место может быть изменено стековыми операциями. Тем не менее, псевдорегистры могут быть слиты на любое свободное место на любом из стеков. Всё место, принадлежащие к элементам стека выделенным под регистры (???) и место за пределами логического указателя стека является свободным.
[^5]: см. эмпирической анализ использования стека в [HFWZ87, Koo89]
3.6 Неизвестная высота стека
Высоты стека фрагмента кода неизвестна, если она не может быть определена во время компиляции. Неизвестная высота стека редка (за исключением ?DUP), но встречается. Компилятор может обнаружить это путем сравнения логического указателя стека при объединении потоков управления. Если они различны, высота стека становится неизвестной[^6].
[^6]: компилятор может предупредить пользователя, поскольку неизвестная высота стека зачастую являются следствием ошибок программирования [Tev89].
RAFTS компилирует случай неизвестной высоты стека путём принудительного уравнивания высот стека при объединение базовых блоков: Одиг из базовых блоков считается стандартным и другие адаптируются к нему путём вставки кода для выравнивания указателя стека и соответствующих загрузок или сохранений. Если речь идет о цикле, корректирующий код должен быть вставлен в цикл. После перестройки для изменения положения позиции слитых значений (по отношению к логическому указателю стека), их, возможно, придется перенести, чтобы сделать состояние последовательным при соединении потоков управления.
Единственный распространённый случай переменного стекового эффекта — слово ?DUP в контексте вроде ?DUP 0= IF, где IF тоже имеет переменный стековый эффект. Однако, при комбинировании стековых эффектов обычно это исправляется. Компилятор может распознавать и обрабатывать эту ситуацию посредством специально построенной на этот случай логики.
3.7 EXECUTE
При компиляции EXECUTE, компилятор не знает, какое слово будет вызываться и поэтому не может выполнять межпроцедурное распределение регистров. Хуже того, стековый эффект выполненных слов неизвестен. Таким образом, при компиляции EXECUTE, состояние адаптированы по соглашению о вызове: некоторое число элементов с каждого стека должно быть размешено в определенных регистрах. Остальное хранится в соответствующих местах на стеке; физические указателей стеков должны быть обновлены для отражения их логического значения. Нужно определить эмпирически, сколько элементов каждого стек нужно разместить в регистрах.
Когда берется адрес слова, генерируется специальная версия слова, чтобы соответствовать соглашению о вызовах.
3.8 PICK и ROLL
Компиляция PICK и ROLL с константной вершиной стека (напр. 4 PICK) не представляет никакой проблемы. Они могут быть выполнены во время компиляции, как и другие слова - стековые манипуляторы. Но если значение вершины не может быть определено во время компиляции, это не представляется возможным.
Имеется два решения:
- Регистры сбрасываются в стек и выполняется операция. В случае ROLL, компилятор также считает регистры недействительными и перезагружает стек элементов по требованию.
- Они транслируются в что-то вроде
CASE 0 OF 0 PICK ENDOF
1 OF 1 PICK ENDOF
...
DUP PICK SWAP
ENDCASE
Для каждого элемента стека выделяется свой OF.
3.9 Как это собрать вместе
В ходе обработки ввода текста, компилятор создает граф потока данных для основного блока и графы потока управления для слов. Только для самых нижних слова в цепочке вызовов граф уже построен, поэтому межпроцедурной информации не достаточно, и компилятор откладывает оставшуюся работу на более поздний этапе.
Остальная компиляция запускается при первом вызове неоткомпилированного слова. Тогда это слово и все слова, которые оно вызывает компилируются: стек неизвестной высоты, EXECUTE, PICKи и ROLLы разрешаются путём добавления обновления указателя стека, и код преобразуется в форму SSA. После оптимизации, код преобразуется обратно из формы SSA. Затем выбранная инструкция выполняется. Упорядочивание инструкций и распределение регистров могут быть выполнены в любом порядке. Наконец, код представлены структурой данных компилятора, переводится в реальный код и выполняется слово.
4 Дальнейшая работа
Чтобы доказать пудинг, его нужно съесть. RAFTS должен быть реализован и оценен путем измерения. Для того, чтобы сделать это реальным, нужна полная система Forth декомпиляции и отладки.
Может ли представленные здесь методы применять для PostScript? Насколько выгодно это? Поскольку PostScript выполняет проверку типов времени исполнения, компилятору Postscript необходимы будут также методы сокращения накладных расходов, например, подобные разработанным Self-группой [CU89].
Удивительная легкость, с которой удобное представление, вроде графа потоков данных и SSA-формы могут быть получены из форт-кода, вдохновляет на вопрос, какие ещё хорошие свойства могут иметь стековые языки в целом, и форт в частности.
Благодарности
Felix Beer, Manfred Brockhaus, Andreas Krall, Herbert Pohlai и Franz Puntigam сделали полезные замечания по черновику этой статьи. Tom Almy, Mike Haas, Mike Hore и Bernd Paysan обсуждали свои компиляторы машинного кода со мной.
Литература:
[Alm86] Thomas Almy. Compiling Forth for performance. Journal of Forth Application and Research, 4(3):379--388, 1986.
[ASU86] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers. Principles, Techniques, and Tools. AddisonWesley, 1986.
[Bri92] Preston Briggs. Register Allocation via Graph Coloring. PhD thesis, Rice Univer
sity, Houston, 1992.
[CFR + 91] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, October 1991.
[CH90] Fred C. Chow and John L. Hennessy. The prioritybased coloring approach to register allocation. ACM Transactions on Programming Languages and Systems, 12(4):501--536, October 1990.
[Cha82] G. J. Chaitin. Register allocation & spilling via graph coloring. In SIGPLAN '82 Symposium on Compiler Construction, pages 98--105, 1982.
[Cho88] Fred C. Chow. Minimizing register usage penalty at procedure calls. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 85--94, 1988.
[CK91] David Callahan and Brian Koblenz. Register allocation via hierarchical graph coloring. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 192--203, Toronto, 1991.
[CMCH92] Pohua P. Chang, Scott A. Mahlke, William Y. Chen, and Wenmei W. Hwu. Profileguided automatic inline expansion for C programs. Software---Practice and Experience, 22(5):349--369, May 1992.
[CU89] Craig Chambers and David Ungar. Custumization: Optimizing compiler technology for Self, a dynamicallytyped objectoriented programming language. In SIGPLAN '89 Conference on Programming Language Design and Implementation, pages 146--160, 1989.
[FHP91] Christopher W. Fraser, Robert R. Henry, and Todd A. Proebsting. Burg --- Fast Optimal Instruction Selection and Tree Parsing, 1991. Available via anonymous ftp from kaese.cs.wisc.edu, file pub/burg.shar.Z.
[GM86] Phillip B. Gibbons and Steve S. Muchnick. Efficient instruction scheduling for a pipelined architecture. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, pages 11--16, 1986.
[HFWZ87] John R. Hayes, Martin E. Fraeman, Robert L. Williams, and Thomas Zaremba. An architecture for the direct execution of the Forth programming language. In Archi
tectural Support for Programming Languages and Operating Systems (ASPLOSII), pages 42--48, 1987.
[KB92] Andreas Krall and Thomas Berger. Fast Prolog with a VAM1p based Prolog compiler. In Programming Language Implementation and Logic Programming (PLILP '92), pages 245--259. Springer LNCS 631, 1992.
[Koo89] Philip J. Koopman, Jr. Stack Computers. Ellis Horwood Limited, 1989.
[Mor91] W. G. Morris. CCG: A prototype coagulating code generator. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 45--58, Toronto, 1991.
[Ros86] Anthony Rose. Design of a fast 68000based subroutinethreaded Forth with inline code & an optimizer. Journal of Forth Application and Research, 4(2):285--288, 1986. Proceedings of the 1986 Rochester Forth Conference.
[Tev89] Adin Tevet. Symbolic stack addressing. Journal of Forth Application and Research, 5(3):365--379, 1989.
[Tin81] C. H. Ting. Systems Guide to figForth. Offete Enterprises, Inc., San Mateo, CA 94402, 1981.
[TvSKS83] Andrew S. Tanenbaum, Hans van Staveren, E. G. Keizer, and Johan W. Stevenson. A practical tool kit for making portable compilers. Communications of the ACM, 26(9):654--660, September 1983.
[Ung87] David Ungar. The Design and Evaluation of a HighPerformance Smalltalk System. MIT
Press, 1987.