bmstu-iu9 / bmstu-iu9/refal-5-lambda

Универсальная древесная оптимизация $OPT

Open
#314 9 comments 0 reactions 1 assignee Claimed by @Mazdaywik View on GitHub
task
Dominant language
C++
Stars
97
Forks
40
PR merge metrics
No merged PRs in 30d

Description

Мотивация
========
Имеющаяся схема древесной оптимизации слишком сложна. Во-первых, есть несколько ключевых слов, объявляющих функции, вызовы которых компилятор должен оптимизировать: `$SPEC`, `$DRIVE`, `$INLINE`. Причём для `$SPEC` пользователь должен понимать разницу между динамическими и статическими параметрами, а также сложные ограничения для последних. С метками `$DRIVE` и `$INLINE` всё ещё сложнее, т.к. различия между ними не синтаксические, а семантические. При неправильной пометке статического параметра мы получим синтаксическую ошибку. А при неправильной пометке функции как `$DRIVE` или `$INLINE` получим зацикливание.

В компиляторе есть механизм, позволяющий автоматически размечать оптимизируемые функции (#252). Но он пытается пометить для оптимизации все возможные функции, что может негативно сказаться на времени компиляции. Экспериментов с `-OiDS` и `-OiDGS` пока не выполнялось, поскольку разметка пока медленная, её код предстоит оптимизировать (#310).

Кроме того, сложный интерфейс командной строки — много разных опций (по алфавиту): `-OA`, `-OD`, `-OI`, (`-Oi`), `-OS`, `-OT`.

Также надо отметить, что оптимизации прогонки и специализации хорошо работают в тандеме. Специализация без прогонки не даёт ускорения, прогонка без специализации оптимизирует гораздо меньше.

Интерфейс
=======
Предлагается ввести единственное ключевое слово — `$OPT`, которым помечать функции, вызовы которых надо оптимизировать. Оно будет заменять собой объявления `$SPEC`, `$DRIVE` и `$INLINE`. Семантика у него будет следующая:
* Если данную функцию безопасно прогонять, то вызов будет прогнан.
* Иначе вызовы этой функции будут специализироваться.
* Специализированные экземпляры этой функции также будут неявно иметь метку `$OPT`, поэтому на следующих циклах оптимизации могут быть прогнаны (а может даже, и специализированы?).
* Режим оптимизации включается опцией `-OT`.
* Безымянные функции, присваивания и блоки, а также вспомогательные функции условий для режима `-OC-` неявно имеют метку `$OPT`.
* Опция `-OA` означает, что все пользовательские функции неявно имеют метку `$OPT`.

Детали реализации
=============
* Для эффективного решения этой задачи специализатор должен осуществлять элементы прогонки (#251). В этом случае будут оптимизироваться функции, которые ранее могли иметь только метку `$INLINE`.
Можно показать, что если рекурсивная функция имела метку `$INLINE` и была специализирована с элементами прогонки, её экземпляры будут пригодны для обычной прогонки и встроятся в точку вызова на следующих итерациях.
* Проверка допустимости прогонки будет выполняться алгоритмом разметки (#252). В графе алгоритма разметки будут находиться только оптимизируемые функции (что сократит размер этого графа и повысит быстродействие), корнями графа будут вызовы оптимизируемых функций из всех неоптимизируемых + entry-функции + `INIT` + `FINAL`.
* Данный подход неточно упоминался в задачах #251, #252 и ошибке #278. Здесь он сформулирован полностью.
* Интересный вопрос: продумать возможность специализации экземпляров — когда это не будет приводить к зацикливанию?

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.