Продумать и реализовать изменения в архитектуре, необходимые для высокоуровневых оптимизаций

[Mazdaywik]

Эта задача — подзадача для #122 и #126.

Если внимательно посмотреть задачи по прогонке (#122) и специализации (#126) функций, а также на промежуточное представление, становится понятно, что актуальные структуры данных неадекватны новому синтаксису. Функции теперь могут быть, помимо типа entry/локальная, ещё и встраиваемыми, прогоняемыми и специализируемыми.

Со специализацией всё достаточно просто: для конструкта $SPEC можно просто добавить в синтаксическое дерево новый узел верхнего уровня.

А вот с $INLINE, $DRIVE и $ENTRY хитрее. Функция может быть помечена как $ENTRY в списке, подобном спискам $EXTERN, $ENUM и т.д. А ключевые слова $INLINE и $DRIVE могут находиться перед именем функции. Есть предложение для этого заменить s.ScopeClass на (e.Flags), где флагами могут быть Entry, Drive и Inline. Также для списков $ENTRY, $DRIVE и $INLINE потребуется новый узел верхнего уровня.

Подобное изменение AST потребует изменения обоих парсеров (SR-Parser.sref, R5-Parser.ref), Checker’а, возможно, движка (Driver.sref Engine.sref) и, конечно, рассахаривателя (Desugaring.sref, Desugaring-UnCondition.ref). Т.е. весь front-end.

Кстати, о рассахаривателе. Оптимизацию можно поместить как между рассахаривателем и высокоуровневым RASL’ом, так и внутри самого рассахаривателя после (опционального — см. #17) прохода удаления условий. Мне кажется, второй вариант предпочтительнее. Выход рассахаривателя для back-end’а менять не нужно.

О самой оптимизации. Оптимизация предполагает многократное и поочерёдное выполнение проходов специализации и прогонки/встраивания, одни проходы будут открывать возможность для других проходов. Например, специализация функции Map по применяемой функции откроет возможность прогонки этой функции, встраивание функции Pipe (Seq) откроет возможность встраиваний и специализаций перечисленных проходов.

Многократность проходов несёт в себе зерно зацикливания: можно легко написать такую программу, что компилятор на ней зациклится, бесконечно выполняя прогонку, специализацию или встраивание. Задача обнаружения зацикливаний — алгоритмически неразрешимая, для неё возможно найти только приближённое решение. Наиболее общие решения разрабатываются в теории суперкомпиляции (отношение Турчина, Хигмана-Крускала и разные эвристики), что для нашей задачи совершенно избыточно. Поэтому есть предложение выбрать прагматичный вариант: ограничить количество итераций некоторой верхней границей, которая задаётся опцией командной строки.

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

[Mazdaywik]

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

[Mazdaywik]

Заготовка для написания оптимизаторов находится в ветке mazdaywik-tree-opt, с ней же сейчас совпадают strixseloputo-tree-opt и madnaaaaas-tree-opt.

В этой ветке (а вернее в актуальной master под ней) есть удобный логгер, который в процессе компиляции пишет в указанный файл синтаксическое дерево до, во время и после оптимизации. Для ознакомления можно выполнить makeself с переменной окружения SRMAKE_FLAGS=--log=log.txt (без оптимизации) и SRMAKE_FLAGS="--log=log.txt -OT" (с оптимизацией).

На данный момент в каркасе добавлены следующие ключи

• -OT — оптимизация синтаксического дерева, раскрывает вызовы замыканий (см. далее), подразумевается неявно со всеми последующими.
• -OD — оптимизация прогонки — должна осуществлять прогонку функций, помеченных как $DRIVE и встраивание функций, помеченных как $INLINE.
• -OI — оптимизация встраивания — должна осуществлять встраивание функций, помеченных как $DRIVE и $INLINE.
• -OS — оптимизация специализации — должна специализировать функции, помеченные как $SPEC.

Опция --opt-tree-cycles=num определяет максимальное количество проходов оптимизатора по дереву. По умолчанию установлена в 100.

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

Итерации выполняются, пока счётчик не обнулится, либо пока дерево не перестанет меняться между проходами.

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

https://github.com/bmstu-iu9/simple-refal/blob/880708453f3d7bf557fb4ab7d7c6d7fdcb797566/src/compiler/OptTree-Drive.ref#L1-L25

https://github.com/bmstu-iu9/simple-refal/blob/880708453f3d7bf557fb4ab7d7c6d7fdcb797566/src/compiler/OptTree-Spec.ref#L1-L25

Функция OptTree-***-ExtractOptInfo извлекает из дерева информацию об оптимизируемых функциях в виде структуры данных e.***Info — это состояние оптимизатора между проходами. Та в свою очередь должна содержать список имён специализируемых функций (см. листинги).

Функция OptTree-*** выполняет один проход оптимизации — в общем случае изменяет дерево и своё состояние (e.***Info)

Функция OptTree-***-Finalize вызывается при завершении оптимизации, формирует «окончательное» дерево, удаляя из него какие-то промежуточные, недоделанные вычисления (может оказаться, что эта функция не нужна).

Я создал отдельные подзадачи #157 и #158, в которых описал первые шаги по реализации оптимизаторов (правки парсера, checker’а и рассахаривателя). К этим задачам можно будет приступить, когда я закончу задачу #159 (про entry-функции).

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

@StrixSeloputo и @madnaaaaas, отпишитесь в этом issue, если прочли этот комментарий и задачи #158 и #157 соответственно.

[Mazdaywik]

Выполнил задачу #159, обновил описания задач #157 и #158, ветки madnaaaaas-tree-opt и strixseloputo-tree-opt синхронизировал с mazdaywik-tree-opt.

@madnaaaaas и @StrixSeloputo , теперь можете писать свой код.

[Mazdaywik]

Каждая из задач #157 и #158 примерно на день работы.

[Mazdaywik]

Задачу можно закрыть. Всё сделано.

[Mazdaywik]

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