Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пн авг 20, 2018 07:26

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Новый подход к генерации Фортом машинного кода
СообщениеДобавлено: Вт янв 26, 2010 22:08 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Автор: 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. Addison­Wesley, 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 priority­based 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 Wen­mei W. Hwu. Profile­guided 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 dynamically­typed object­oriented 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 (ASPLOS­II), 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 68000­based subroutine­threaded 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 fig­Forth. 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 High­Performance Smalltalk System. MIT
Press, 1987.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 26, 2010 23:36 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
ps. Это первая из статей Эртла о нативной компиляции форта. По хорошему конечно надо переводить его диссер, где описан и этот подход, и то, что в gForth, и компиляция через Си-код... Но объём... Так что буду, время от времени, подбрасывать сюда отдельные статьи.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт янв 26, 2010 23:50 
Не в сети
Moderator
Moderator

Зарегистрирован: Ср май 10, 2006 15:37
Сообщения: 1132
Откуда: Chelyabinsk ( Ural)
Благодарил (а): 0 раз.
Поблагодарили: 9 раз.
Методики Ертла ( vmgen ) использованы в CACAO JVM ( cacaovm.org )

P.S Возможно интересно генерить код из форта в байт-код Java и использовать, по возможности,
уже существующюю реализацию JIT для CACAO
Близкая тема и методики оптимизации использованные в tamarin-tracing


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 13:35 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4926
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
однако, есть и более простой вариант.
Заставить генерировать форт текст для Low Level Virtual Machine переложив все оптимизации на него.
основные особенности:
Плюс - простота (относительно самостоятельного решения),
минус - придется за собой тягать чужой код, или заставлять пользователя его скачивать самостоятельно.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 13:49 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4926
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
И все же мне гораздо интереснее тема верификации кода!
в чем-то эти темы пересекаются, по крайней мере требуют обе построения графов и контроля прохождения данных.
интересно, кто-нить занимался вопросами верификации форт-кода?

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 14:37 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
mOleg писал(а):
однако, есть и более простой вариант.
Заставить генерировать форт текст для Low Level Virtual Machine переложив все оптимизации на него.
основные особенности:


код для gcc генерировать ещё проще (хотя у llvm оптимизатор, судя по всему, лучше). Опять же gcc - это самый что ни на есть мейнстрим, а llvm и, тем более, cacao vm - ещё нет.

Статья Эртла про генерацию gcc кода, с написанным его студентом под gforth прототипом на подходе.

mOleg писал(а):
И все же мне гораздо интереснее тема верификации кода!
в чем-то эти темы пересекаются, по крайней мере требуют обе построения графов и контроля прохождения данных.


Да, согласен, что это важнее.

mOleg писал(а):
интересно, кто-нить занимался вопросами верификации форт-кода?


ну разве что вот это:

http://www.cat-language.com/ - конкатенативный язык CAT (под .net) с выводом типов по Хиндли-Миллеру (исходники ядра на C#, есть альтернативные на других языках)
http://code.google.com/p/cvml/ - CVML собственная виртуальная машина для cat (на С++)

Правда язык Cat далековат от форта, это такой Joy, т.е. куда менее гибкий конкатенативный язык.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 14:44 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4926
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
be_nt_all писал(а):
код для gcc генерировать ещё проще (хотя у llvm оптимизатор, судя по всему, лучше). Опять же gcc - это самый что ни на есть мейнстрим, а llvm и, тем более, cacao vm - ещё нет.

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 14:50 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
mOleg писал(а):
особой разницы нет, придется с собой таскать еще один компилятор. это огромный минус.


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

зы. так сказать, минусы unix way. Если взять тот же gforth, то без gсс под рукой он годится только, как верно заметил Хищник на поиграться с командной строкой. Для всего остального надо делать биндинги к системным библиотекам, для чего gforth требует немножко c-кода (в особо тяжёлых случаях - пересборки ядра, в смысле ядра форта конечно, а не линукса).


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 15:41 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4926
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
вообще тут достаточно уникальный случай. Оптимизация всего кода не возможна (да и не нужна).
Оптимизация нужна кусочная, по крайней мере, если мы хотим оставаться с привычными словарными статьями и возможностью вызова отдельных определений, а это важный момент. Значит, нужно оптимизировать отдельно каждое определение, если возможно делать "инлайн" подстановки простых слов, и оставлять вызовы больших слов.
Первое. что приходит на ум, для каждого примитива написать некий псевдокод, в виде, который например, проглотит LLVM и вообще не заморачиваться с оптимизациями.
То есть, к примеру, имеем что-то вроде:
over { mov tp+1,tp-1,tp }
+ { add tp+1,tp-1,tp }
и так далее.
То есть подобное, кажется, делал Михаил в отношении ассемблера.
потом получим "простыни" кусков псевдокода, который будет оптимизировать внешний механизм и только в случае сборки готового образа программы. (может несколько сумбурно выражаюсь).
Кстати, замечу, что оптимизировать удобно именно шитый код, то есть последовательность вызовов, а не текстовое представление исходника.
Это позволит с одной стороны сильно упростить анализ текста (оно уже откомпилировалось), убрать возню с именами, а значит всякими переопределениями имен и ээ полиморфизмом имен, т.к. ссылки на код уникальны.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 15:54 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Да. Именно так (какие-то специфические оптимизации есть со временем делать, но это детали).

Причём будет ли это байт-код llvm или код на C - не суть разница вообще. С llvm преимущество в том, что это виртуальная машина с возможностью компиляции, т.е. прямо на ней можно форт-программы и крутить.

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

Про forth->gcc статью ждите послезавтра.

зы.

mOleg писал(а):
Это позволит с одной стороны сильно упростить анализ текста (оно уже откомпилировалось), убрать возню с именами, а значит всякими переопределениями имен и ээ полиморфизмом имен, т.к. ссылки на код уникальны.


Вероятно да, по крайней мере в большинстве случаев.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 16:27 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
Кстати, выигрыш от оптимизации определение-за-раз будет невелик.
Особенно если программа пишется в стиле одно слово-одна строка.
При этом очень много времени уйдет на манипуляции стеком.
Похоже, самым важным для оптимизации будет мощный инлайнер.
Собирал ли кто статистику, сколько времени в реальных программах уходит на прием-передачу параметров через стек?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 16:34 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
dynamic-wind писал(а):
Похоже, самым важным для оптимизации будет мощный инлайнер.


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

А статистика... Да в тех же статьях Эртла где то должно что-то подобное быть, поищу.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 16:46 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
Все эти новые подходы генерации эффективного кода будут не сильно эффективны по простой причине, все они базируются на преобразовании кода целевой машины,
который эмулирует код виртуальной машины. Это обстоятельство ограничивает степень оптимизации целевого кода, так как не учитывает все возможности целевого кода.
Виртуальная машинка-то проста и нужно небольшое подмножество инструкций целевой машины, чтобы ее эмулировать. Вот с этим-то подмножеством инструкций и будет работать
оптимизатор не выходя за его рамки, и это-то и не даст получить на самом деле оптимальный код целевой машины.
Вот пример:
Код:
\ получить номер самого младшего единичного бита
: LO-BIT ( n -- k )
32 0 DO DUP 1 AND IF DROP I LEAVE ELSE 1 RSHIFT THEN LOOP ;

SEE LO-BIT

: lo-bit ( n -- k )
A=L\A ;

SEE lo-bit

log
CODE LO-BIT
5AEB17 8945FC           MOV     FC [EBP] , EAX
5AEB1A C745F820000000   MOV     F8 [EBP] , # 20
5AEB21 33C0             XOR     EAX , EAX
5AEB23 BA00000080       MOV     EDX , # 80000000
5AEB28 2B55F8           SUB     EDX , F8 [EBP]
5AEB2B 8D1C02           LEA     EBX , [EDX] [EAX]
5AEB2E 8B45FC           MOV     EAX , FC [EBP]
5AEB31 6860EB5A00       PUSH    , # 5AEB60
5AEB36 52               PUSH    EDX
5AEB37 53               PUSH    EBX
5AEB38 8BC8             MOV     ECX , EAX
5AEB3A 81E101000000     AND     ECX , # 1
5AEB40 0F840E000000     JE      5AEB54  ( LO-BIT+3D  )
5AEB46 8B0424           MOV     EAX , [ESP]
5AEB49 2B442404         SUB     EAX , 4 [ESP]
5AEB4D 8D642408         LEA     ESP , 8 [ESP]
5AEB51 C3               RET     NEAR
5AEB52 EB03             JMP     5AEB57
5AEB54 C1E801           SHR     EAX , 1
5AEB57 FF0424           INC     [ESP]   \ Press <enter> | q | any
5AEB5A 71DC             JNO     5AEB38
5AEB5C 8D64240C         LEA     ESP , C [ESP]
5AEB60 C3               RET     NEAR
END-CODE
( 74 bytes, 23 instructions )


CODE lo-bit
5AEB77 0FBCC0           BSF     EAX , EAX
5AEB7A C3               RET     NEAR
END-CODE
( 4 bytes, 2 instructions )

Ok

Оптимизатор не выйдет из плоскости команд виртульной машины в пространство команд целевой машины.
Есть ведь еще и наборы SSE и т.п.
Это справедливо и для других целевых платформ гораздо сложнее виртуальной машинки форта.
Кстати peephole-оптимизация(макроподстановки) позволяет выходить из плоскости в пространство.

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 16:56 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июн 25, 2009 11:12
Сообщения: 412
Благодарил (а): 41 раз.
Поблагодарили: 8 раз.
be_nt_all писал(а):
И в переведённой мной статье, если ты заметил, много говорится о межпроцедурном распределении регистров.

Заметил с превеликим скепсисом.
Global RA -- красивая штука, но она БЕСПОЛЕЗНА для x86 (для которого даже стандартные алгоритмы local RA дают паршивый результат)! С другой стороны, если ориентироваться на Sparc/MIPS/..., global RA поможет.
Есть еще call-site register targeting, то есть если известны все точки вызова данного слова, следует генерировать код, помещающий аргументы в одни и те же регистры с минимумом пересылок. Опять же полезно, когда этих регистров достаточно.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср янв 27, 2010 17:08 
Не в сети
Аватара пользователя

Зарегистрирован: Пн ноя 27, 2006 22:09
Сообщения: 115
Откуда: Ростов-на-Дону
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
chess писал(а):
Все эти новые подходы генерации эффективного кода будут не сильно эффективны по простой причине, все они базируются на преобразовании кода целевой машины


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

А так, SSE очень хорошо задействовать в языках вроде J и K.

upd. Имхо, как раз таки peephole (щелевая) оптимизация работает с кодом целевой машины.

Здесь же предлагается строить абстрактный DAG, в котором вызов слова и возврат из него мало чем отличаются, скажем от ветвей IF-ELSE-THEN, проводить с этим графом некоторые преобразования, а потом генерировать по нему код.


Последний раз редактировалось be_nt_all Ср янв 27, 2010 17:31, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу 1, 2, 3  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB