Удалять экранированные предложения на проходе оптимизации

[Mazdaywik]

Примечание. Ранее эта задача была частью формулировки задачи #341, но теперь она вынесена отдельно. Из формулировки #341 задача переноса логики на проход оптимизации удалена.

Введение

В компиляторе уже присутствует механизм распознавания экранируемых предложений — компилятор выдаёт предупреждения (при включённой опции -Wscreening) на случаи, когда предложение экранируется одним из предшествующих.

Модуль был реализован Александром Барлукой aka @nexterot (#256, #297) под руководством Антонины Николаевны Непейвода aka @TonitaN (теоретический фундамент) и меня (архитектура компилятора).

Мотивация

Интеграция в подсистему древесной оптимизации

На данный момент распознаватель экранирования используется только на этапе семантической проверки (Checker.ref, Checker-Screening.ref) и может только сообщать пользователю о потенциальных проблемах в коде.

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

Единственный случай, о котором я знаю

Есть функция MultilineTerm-Prefix, которая используется для вывода в лог синтаксического дерева. Вызывается она для термов, запись которых слишком длинна, чтобы уместиться в строку длиной 80 знаков. Такие термы нужно выводить в несколько строк. Вот её код:

refal-5-lambda/src/compiler/Log-AST.ref

Lines 253 to 302 in db0ccf9

	MultilineTerm-Prefix {
	(e.Prefix) e.Indent t.Term (e.Suffix)
	= t.Term
	: {
	(Brackets e.Expr)
	= (e.Prefix '(')
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent ')' e.Suffix);
	(ADT-Brackets (e.Name) e.Expr)
	= (e.Prefix '[' <DisplayName e.Name>)
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent ']' e.Suffix);
	(CallBrackets (Symbol Name e.Function) e.Expr)
	= (e.Prefix '<' <DisplayName e.Function>)
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '>' e.Suffix);
	(CallBrackets (TkVariable e.Indirect) e.Expr)
	= (e.Prefix '<' <TkVariable e.Indirect>)
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '>' e.Suffix);
	(CallBrackets (ClosureBrackets (Symbol Name e.Function) e.Context) e.Expr)
	= (e.Prefix '< {{' <DisplayName e.Function>)
	<Expression (e.Indent ' ') (e.Indent ' ') e.Context ()>
	(e.Indent ' }}')
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '>' e.Suffix);
	(CallBrackets e.Expr)
	= (e.Prefix '<')
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '>' e.Suffix);
	(ColdCallBrackets e.Expr)
	= (e.Prefix '<*')
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '*>' e.Suffix);
	(ClosureBrackets (Symbol Name e.Function) e.Expr)
	= (e.Prefix '{{' <DisplayName e.Function>)
	<Expression (e.Indent ' ') (e.Indent ' ') e.Expr ()>
	(e.Indent '}}' e.Suffix);
	(s.Type e.Value)
	= (e.Prefix <InlineTerm (s.Type e.Value)> e.Suffix);
	};
	}

Разбивать на несколько строк нужно скобки: на одной строке открывающая, затем строки с содержимым скобок, затем закрывающая. Для всех остальных термов вызывается функция InlineTerm, формирующая одну строчку с записью терма — см. последнее предложение:

refal-5-lambda/src/compiler/Log-AST.ref

Lines 299 to 302 in db0ccf9

	(s.Type e.Value)
	= (e.Prefix <InlineTerm (s.Type e.Value)> e.Suffix);
	};
	}

Функция InlineTerm определена так:

refal-5-lambda/src/compiler/Log-AST.ref

Lines 232 to 240 in db0ccf9

	InlineTerm {
	(Symbol e.Value) = <Symbol e.Value>;
	(TkVariable e.Value) = <TkVariable e.Value>;
	(Brackets e.Value) = <Brackets e.Value>;
	(ADT-Brackets e.Value) = <ADT-Brackets e.Value>;
	(CallBrackets e.Value) = <CallBrackets e.Value>;
	(ColdCallBrackets e.Value) = <ColdCallBrackets e.Value>;
	(ClosureBrackets e.Value) = <ClosureBrackets e.Value>;
	}

Внутри функции MultilineTerm-Prefix актуальны будут только строчки про символы и переменные — случаи строк про скобки уже разобраны. Но после прогонки они будут. Т.е. в оптимизированной программе будут заведомо избыточные предложения.

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

Однако, есть другие случаи, когда экранирование будет возникать в силу особенностей алгоритма.

• Прогонка вызовов функций в условиях + прогонка самих условий будут давать экранируемые предложения в случаях, когда условие всегда истинно. Пример этого разобран в Прогонка вызовов функций в условиях #283.
• Специализатор к экземплярам добавляет аварийное предложение, которое необходимо для отладки. Мотивация его добавления описана в Понятный аварийный дамп для специализированных функций #240 — рекомендуется пройти по ссылке, прежде чем читать дальше.

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

Дополнительная мотивация в том, что модуль Checker-Screening.ref содержит в себе часть рассахаривателя, т.к. использует средства (обобщённое сопоставление с образцом, ГСО), которые могут работать только с рассахаренным деревом. Это не очень красиво, т.к. рассахаривание выполняется дважды. Если распознаватель экранирования разместить после рассахаривателя (а именно там находится древесный оптимизатор), дублирования не будет.

Однако, тогда предупреждения сможет порождать back-end, что пока архитектурно не поддерживается. На самом деле, предупреждения от оптимизатора не новость — оптимизирующие компиляторы C/C++ при включении глубокой оптимизации выдают дополнительные предупреждения. Например, GCC на -O3 (или даже на -O2, не помню) выдаёт предупреждения о strict aliasing.

Реализация

При реализации нужно решить ряд следующих задач:

(некоторые пункты исключены, см. комментарии)

• Выбрать место для распознавателя экранирования на уровне архитектуры.

  Сейчас он находится в модуле семантической проверки, но должен находиться или в древесном оптимизаторе, или рядом с ним (скорее всего, и там, и там). Кроме того, нужно добавить возможность back-end’у выдавать предупреждения и отказывать в компиляции, если задан ключ -Werror (трактовать предупреждения как ошибки).

• Соответственно, перенести распознаватель экранирования в новое место.