Оптимизатор машкода. Вариант =KRoN='а.

Собственно, тема, ради которой заводился форум.

Краткая вводная.

Традиционно Форт пишется на компиляторах шитого кода. Это в некоторых случаях может дать даже выигрышь в сравнении с подпрограммными вызовами примитивов (call + ret вплоть до i486, например, занимает больше, чем LODSW...JMP для 8086/286 или MOV R, [R]...JMP для 386/486), но оборачивается потерями на вызове высокоуровневых слов и не даёт возможности оптимизации инлайнированием примитивов.

Существуют также компиляторы прямо в машинный код. Кажется, самый популярный среди таких и, кажется, единственный некоммерческий для x86 - это широкоизвестный SP-Forth Андрея Черезова ( * Главная - [RuFIG] ).

К нему имеется также весьма неплохой оптимизатор машкода, с версии SPF4, встраиваемый в Форт.

Результаты весьма неплохие. В целом программы немного уступают эквивалентным программам языков-рекордсменов (MSVC++, O'Caml, GCC), но обычно от единиц до десятков процентов (не "в разы"), а в некоторых случаях и превосходит.

Но всё могло бы быть значительно лучше...

Вот моя идея.

- Примитивы пишутся на специальном "переносимом" ассемблере, заточенным под совместимость с наиболее популярными процессорами PC/PPC - x86, ARM, MIPS, DragonBall.

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

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

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

Вот одно моё письмо с более детальной проработкой, редактировать под форум не буду

✂

Я тут сегодня подумал над идеей своего оптимизатора.
(Комп - старый ноутбук, правда, виснет ужасно - пришлось на бумажке ручкой!
)

В общем, вопрос представления процессора в виде модели оказался неактуален.

Попробую изложить свою идею в Форт-стиле, "снизу-вверх"

1. Нативный ассемблер. Обычный достаточно умный построчный компилятор ассемблера, написанный на Форте.

На входе:
- Строка с кодом операции ("mov ax, sp", "lea eax, [ebx+ecx*4]", "mov (R0)+,
R1" и т.п.).
- Базовый адрес компиляции (нужен для переходов, чтения переменных и т.п.)
- Возможно - список занятых регистров, которые нельзя использовать в операции (об этом чуть ниже, пункт 2).

На выходе:
- Строка двоичного кода операции.
- Число тактов на неё.
- Число байт на неё.
- Возможно - список занятых регистров после операции (см. опять же пункт 2).

Возможные ошибки кода - неверный опкод ("ADD [SP], [BX]"), слишком дальний переход. При переносе учёта занятых регистров в ассемблер - ещё ошибка "использование занятого регистра".

2. Собственно оптимизатор.

Самое хитрое и сложное в проработке.

Условный форт-псевдоассемблер в духе:
CODE +
SP1 SP0 ADD
SP 4 # ADD
NEXT
END-CODE

Регистры:
R0 R1 .. RN - регистры общего назначения
SP0 SP1 .. SPN - регистры стека
RP0 .. RPN - регистры стека возвратов
SP - указатель стека
RP - указатель стека возвратов

Байтовые регистры ещё хорошо не продумывал, что-то типа B0..BN или C0...CN.

Работаем построчно (создание заголовка и т.п. неинтересно и опускаю).

Функция "раскрутки" псевдокода рекурсивная.

-10- Берём наш "псевдоопкод"
-20- Если используется регистр, значение которого потеряно (-40-) - то возврат с ошибкой и вычисткой ветви.

-30- Пробуем менять все R0..RN по списку свободных регистров, SPN на [SP] и комбинации "MOV RX, SP; ..., [RX+N]" и т.п.
-40- Пробуем менять все R0...RN на занятые регистры - вдруг они по коду больше никогда не нужны.
-43- Пробуем сохранять все (по очереди, каждый вариант - отдельная ветка) РОН в свободные регистры, а освобождённые использовать под RN - вдруг такое сохранение в будущем поможет много сэкономить (неравнозначность регистров x86).
-46- Используем под RN память.

-50- Для всех полученных кодов запускаем ассемблерный компилер пункт 1.
-60- Если ошибка - убиваем, вычищаем память и т.п.
-70- Если длительность исполнения данной цепочки превышает уже вычисленное "рекордное" время, тоже убиваем.
-80- Рекурсивно запускаем компиляцию следующей строки для всех полученных вариантов.

- Когда дошли до конца, то обновляем общее "рекордное" по тактам время - для убиений параллельных веток.

- Записываем полученный код по HERE.

Ну как? По-моему, идея должна работать

"Занятость" регистров лучше переносить на компилятор в нативный год, ИМХО, чтобы не делать двойной работы в компиляторе псевдокода в нативный код - по "loop label" совершенно неясно, что модифицируется CX/ECX и т.п.

Флаги операций тоже надо будет учитывать и т.п.

Но это всё, ИМХО, уже рутина - глаза боятся, руки делают...

✂