Рефакторинг архитектуры древесного оптимизатора

[Mazdaywik]

Задача блокирует задачи #252, #253, #260.

Мотивация

Если приглядеться к оптимизациям встраивания (не прогонки) и специализации, налицо схожий шаблон: берётся вызов функции, для него оптимизатор строит некоторое новое выражение и (опционально) новую функцию. Для встраивания это или результат шага вычисления этой функции, или вызов функции Func*n, вместе с которым и возвращается тело Func*n. Для специализации — это вызов Func@n и тело этой функции. Если сигнатура уже известная, то тело функции не формируется, поскольку оно уже создано.

Это наталкивает на мысль об обобщении этого кода.

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

Другое наблюдение: оптимизатор дерева в совокупности три раза совершает обход дерева: при охлаждении вызовов (OptTree-Simple), во время прогонки (OptTree-Drive) и во время специализации (OptTree-Spec). Очевидно, это лишняя работа.

Есть мысль разрешать одновременно и прогонку, и специализацию одной и той же функции. Приоритет имеет прогонка (включая встраивание): если вызов можно прогнать или встроить, то он, соответственно, прогоняется или встраивается. Иначе вызов специализируется. В частности, так по умолчанию должны обрабатываться безымянные функции (#160). Но сейчас так сделать сложно: проходы прогонки и специализации независимы, после неуспешной прогонки вызов охлаждается и игнорируется специализатором.

Отчасти эта задача — подзадача #229.

Реализация

Предлагается делать только один проход по программе за раз. Для каждого вызова сначала дёргать оптимизатор прогонки. Если он ничего не сделал, дёргать оптимизатор специализации. Если и он ничего не сделал, остужать вызов.

Ради общего API специализатор также должен будет возвращать подстановки-сужения, но они будут всегда пустыми. Очевидно, имеет смысл оптимизация пустых подстановок сужений — не пытаться применять их рекурсивно, а сразу ничего не делать.

Будут сложности с задачей #231 про неразменные аргументы. Концептуально пометка переменных неразменными относится только к прогонке, но её придётся выполнять на верхнем уровне оптимизатора. Это не очень красиво.

Исторический аспект

Используемая архитектура была выбрана ради возможности распараллеливания работ по прогонке и специализации на выпускных квалификационных работах — два студента могли независимо работать каждый над своей задачей. Логика неизбежно дублировалась, однако, на взаимодействие время совсем не терялось.

[Mazdaywik]

Сходство между прогонкой и специализацией чисто внешнее — и там, и там выполняется замена вызова функции на что-то новое + построение новых функций. Но есть и отличие.

Обработка вызова функции при специализации гораздо проще: не производятся сужения, иначе нужно работать с активными вызовами (#230 vs #245), один вызов всегда заменяется на один вызов.

Следствия:

• Независимые вызовы специализации друг на друга не влияют (кроме нумерации специализированных экземпляров) — достаточно одного прохода специализации по программе.
  Вызовы прогонки влияют, т.к. сужения могут происходить в соседний вызов. Для достижения неподвижной точки потребуется несколько проходов (о чём, отчасти, Недостаточная глубина оптимизации при поочерёдном выполнении прогонки и специализации #263).
• Для оптимизации обхода дерева прогонка использует понятия «тёплых» и «холодных» вызовов. Специализации они не нужны.
• Для углубления прогонки полезно введение понятия неразменных переменных (Разметка неразменных аргументов для прогонки #231). К специализации оно неприменимо.
• Прогонка выполняется в двух режимах — встраивание и собственно прогонка. Для специализации таких режимов нет.

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

[Mazdaywik]

Вообще, можно сделать некоторый рефакторинг, удалив избыточные проходы. Можно выполнять прогонку вызовов в предложении до тех пор, пока там можно что-то прогнать. Если ничего уже сделать нельзя, то выполняем специализацию всех специализируемых вызовов. Дальше предложение помечаем «холодным». Таким образом, проход по синтаксическому дереву на верхнем уровне не будет продублирован в разных файлах.

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