refal-5-lambda Удалять и не порождать неиспользуемые функции

UPD: более верная постановка задачи в комментариях (https://github.com/bmstu-iu9/refal-5-lambda/issues/228#issuecomment-714307025).

Эта задача — подзадача для #91.

@InfiniteDisorder реализовал оптимизацию встраивания и прогонки #122, однако, реализовал не оптимально. Когда в процессе прогонки в программе формируется вызов «усечённой» функции <Func*n …>, тело функции Func*n добавляется к синтаксическому дереву. Добавление это преждевременное, поскольку на следующей итерации оптимизации вызов Func*n может прогнаться/встроиться и в конечной программе Func*n никогда вызываться не будет.

Правильным является вариант, когда функции Func*n добавляются в дерево только тогда, когда вызов <Func*n …> становится холодным, т.е. не подлежащим дальнейшей оптимизации. Но что, если лимит итераций иссяк, но функцию Func*n можно ещё прогнать? В этом случае усечённая Func*n должна добавляться в OptTree-Drive-Finalize.

Вообще, привлекательно выглядит вариант вообще не добавлять в дерево тела встраиваемых или прогоняемых функций, если они не вызываются из единицы трансляции или не entry. Но так делать нельзя, поскольку такие функции могут вызываться через Mu, т.е. должны быть доступны для рефлексии. Функции Func*n или Func@n могут пристутствовать в программе или не присутствовать, в зависимости от ключей компиляции, но функция Func без суффиксов присутствовать должна обязательно. В принципе, можно не добавлять в дерево вспомогательные функции вроде Func\n, Func=n, Func:n и другие (например, Func?m?n, добавляемые Desugaring-UnCondition), если они растворились при оптимизации. Надо оценить затратность реализации и, возможно, так и сделать.

Jun 30 '19 14:06 Mazdaywik

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

Но, если подумать, он решает и настоящую проблему. Текущая задача предполагает создавать функции только в тот момент, когда её уже нельзя дальше прогнать: наткнулись на Undefined или предложения закончились (создаётся вызов пустой функции). Либо нельзя встроить, получилось сопоставление с сужениями. Очевидно, в этих же случаях мы прекратим прогонять предложения, если их будем прогонять все вместе.

Jul 04 '19 10:07 Mazdaywik

Тема задачи уточнилась. Здесь теперь предлагается после выполнения оптимизаций чистить программу от неиспользуемых функций с суффиксами. Чистить от любых неиспользуемых локальных функций нельзя, ибо есть функция Mu, выполняющая вызов по имени. А функции с суффиксами вызывать через Mu не следует.

При этом программа также может очиститься от функций \n, =n и :n, что не страшно. Если вложенные функции, присваивания и блоки встроились/прогнались, значит, вспомогательные функции уже не нужны.

Aug 01 '19 18:08 Mazdaywik

Задача #254 (новая реализация метафункций) ввела понятие метатаблиц — особого рода функций, содержащих отображения имён на все функции без суффиксов текущей области видимости.

Поэтому теперь неиспользуемые функции определяются синтаксически — все entry-функции считаем используемыми, все функции с именами INIT и FINAL считаем используемыми, все функции, которые прямо или косвенно из них доступны — тоже используемые. Метафункции содержат указатели на метатаблицы, поэтому если метафункции используются, то автоматически используются и все локальные функции. Если метафункции не используются, то можно удалять и неиспользуемые локальные функции независимо от того, есть у них суффиксы или нет.

Jun 24 '20 15:06 Mazdaywik

Помечу как курсовую, хотя она мне кажется слишком простой для курсовой.

Берите, пока я не передумал.

Oct 04 '20 17:10 Mazdaywik

Не, она не подходит на курсовую. Бессодержательная.

Oct 09 '20 08:10 Mazdaywik

Древесная оптимизация может сделать используемые функции неиспользуемыми. В исходной программе функция E была entry и вызывала функцию L. Оптимизатор или встроил L в точку вызова, или породил новый экземпляр L@1. Функция L не вызывается.

При этом, есть проблема: о том, что функция L не используется, оптимизатор не знает. И если L вызывает какую-нибудь функцию F, вызов которой можно оптимизировать, будет перестроено тело функции L, хотя она совершенно не нужна. Т.е. будет выполняться заведомо лишняя работа.

Поэтому предлагается одновременно оптимизировать функции и помечать среди них используемые. Как это сделать?

Рассмотрим общий случай включённой прогонки и специализации. Специализация на данный момент имеет оптимизацию: после анализа функции (шагов прогонки вызовов в нём и прохода специализатора) она помечается «замороженной» и на последующих проходах не сканируется.

Предлагается сделать зеркальный шаг: «замораживать» (другой заморозкой — блокировать) также функции, которые ещё никем не вызваны. В начале заблокированы только входные точки: entry, INIT, FINAL. Проходы прогонки и специализации над ними порождают функции-хвосты F*n и экземпляры F@n. Перед заморозкой этих функций их тела сканируются и извлекаются вызываемые из них функции (включая указатели и АТД). Функции с данными именами разблокируются. Следующие проходы прогонки и специализации анализируют хвосты, экземпляры и разблокированные функции. Повторяем до тех пор, пока у проходов есть работа — если новый проход не породил хвосты, экземпляры и ничего нового не разблокировал, оптимизация завершается.

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

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

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

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

Заметка на полях

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

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

Эти рассуждения актуальны не только и не столько для обычных указателей вида &Func, но и для абстрактных скобок, теги которых присутствуют только в образцах.

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

Заметим ещё, что вызов неиспользуемой функции может появиться и в результате прогонки. Рассмотрим пример:

$ENTRY F {
  s.F = <Test s.F> <s.F>;
}

Test {
  &NotUsed = 1;
  s._ = 2;
}

NotUsed {
  = "Hello!";
}

Указатель на NotUsed не может появиться в поле зрения. Но при прогонке может появиться вызов этой функции:

$ENTRY F {
  &NotUsed = 1 <NotUsed>;
  s.F = 2 <s.F>;
}

И попробуй выяви такую неиспользуемую функцию чисто синтаксически.

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

Oct 22 '20 07:10 Mazdaywik

Интересный нюанс. Допустим, у нас есть программа

$ENTRY Test {
  e.X = <Map {{ &Test\1 … }} e.X>;
}

Test\1 { … }

Map {  …  }

По идее, вызов Map здесь должен проспециализироваться по замыканию, а значит, замыкание должно стать неиспользуемой функцией, подлежащей удалению.

Но! Получится вот что:

$ENTRY Test {
  e.X = <Map@1 e.X>;
}

Test\1 { … }

Map {  …  }

Map@0 { }

Map@1 {
  …

  e.dyn = <Map@0 {{ &Test\1 … }} e.dyn>
}

Из-за аварийного предложения функция Test\1 формально продолжает использоваться! Но она в программе явно не нужна! Возможное решение — преобразовывать все упоминания функций в аварийном предложении на упоминания пустых функций

  e.dyn = <Map@0 {{ &Test\1@0 … }} e.dyn>

Поскольку заранее неизвестно (вернее, заранее трудно сказать), по чему будут специализированы функции, @0-функции нужно будет добавлять всем функциям в единице трансляции. Всё равно у нас есть средство чистки, которое удалит лишние.

Но что делать в этой ситуации?

$EXTERN Ext;

$ENTRY Test {
  e.X = <Map &Ext e.X>;
}

Map { … }

В аварийном предложении будет

  e.dyn = <Map@0 &Ext e.dyn>

Если её переименовывать в &Ext@0, то, значит, @0-функции нужно добавлять и для внешних функций. Либо, при переименовании проверять, что функция является локальной.

Другое интересное соображение. Если в предложении где-то есть вызов пустой функции, то все вызовы, записанные справа от него оптимизировать (прогонять/специализировать) нет никакого смысла: они всё равно не вызовутся. Аналогично, все эти вызовы не следует считать и используемыми, инструмент чистки должен их игнорировать. Как это осуществить — я пока не придумал.

Nov 29 '20 08:11 Mazdaywik

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

Dec 06 '20 06:12 Mazdaywik

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

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

(ColdFunction s.ColdBy s.Scope (e.Name) e.Body)

Причины на данный момент две: DRIVE и SPEC. Предлагается добавить следующие: UNUSED и SCANNED.

В начале работы программы все функции, кроме входных точек ($ENTRY, __INIT, __FINAL), заморожены как UNUSED.
Проход прогонки оптимизирует размороженные функции. При этом хвостовые функции он не добавляет.
Размораживаем функции DRIVE.
Проход специализации оптимизирует размороженные функции.
Размораживаем функции SPEC.
Проход разморозки проходит по всем размороженным функциям, выбирает из них ссылки, функции замораживает как USED. Для найденных ссылок размораживаются функции UNUSED, генерируются функции-хвосты (если они ещё не сгенерированы).
Если есть размороженные функции и остались проходы оптимизации, иди к пункту 2. Если есть размороженные функции, но проходы оптимизации закончились, иди к пункту 6.

В данной схеме пункты 2–3 и 4–5 могут отсутствовать, если соответствующие оптимизации выключены.

Если в файле есть нативные вставки, то по умолчанию разморожены все функции без суффиксов.

Jul 20 '21 17:07 Mazdaywik

refal-5-lambda refal-5-lambda copied to clipboard

Удалять и не порождать неиспользуемые функции

refal-5-lambda
refal-5-lambda copied to clipboard