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

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

Open
#346 0 comments 0 reactions 0 assignees View on GitHub
task
Dominant language
C++
Stars
97
Forks
40
PR merge metrics
No merged PRs in 30d

Description

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

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

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

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

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

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

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

https://github.com/bmstu-iu9/refal-5-lambda/blob/db0ccf9cb8ce6548e964381dda6977d3a6e79baf/src/compiler/Log-AST.ref#L253-L302

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

https://github.com/bmstu-iu9/refal-5-lambda/blob/db0ccf9cb8ce6548e964381dda6977d3a6e79baf/src/compiler/Log-AST.ref#L299-L302

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

https://github.com/bmstu-iu9/refal-5-lambda/blob/db0ccf9cb8ce6548e964381dda6977d3a6e79baf/src/compiler/Log-AST.ref#L232-L240

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

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

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

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

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

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

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

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

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

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

Contributor guide

No contributing guide indexed for this repository

Research direction

Read src/compiler/Checker.ref, src/compiler/Checker-Screening.ref, and the linked Log-AST.ref implementation first; then locate the tree optimizer entry point and existing screening flow. Done means the screening detector is placed in the optimization stage, redundant clauses are removed, and the requested backend warning and -Werror behavior is addressed.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.