Переписывание языка сборки

[Mazdaywik]

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

Мотивация

Как описано в #169, текущий язык сборки сформировался стихийно. Сначала я придумал кодогенерацию в Си++ для первой версии Простого Рефала. Она основана была на диапазонах вида [first, last], от которых откусываются сопоставляемые объекты:

refal-5-lambda/doc/historical/note000.txt

Lines 909 to 921 in ab2c5c1

	Поддиапазоны аргумента и результата представляются парой итераторов двусвязно-
	го списка (обычных указателей на узлы). При этом первый итератор указывает на
	первый узел поддиапазона, второй итератор -- на последний. Пустая последователь-
	ность представляется парой итераторов, установленных в NULL. В начале я пытался
	использовать обозначение диапазонов в стиле STL -- указателями на первый элемент
	и на элемент, следующий за последним. Однако, для правильного обращения с подоб-
	ными поддиапазонами нужно более тщательно планировать последовательности команд
	построения результата, т.к. в результате переноса (splicing) элементов, находя-
	щихся непосредственно за рассматриваемым диапазонам, переместится и элемент, на
	который указывает концевой итератор -- пара [first, last) больше не будет ука-
	зывать на корректный диапазон. При использовании диапазонов [first, last] при
	любых операциях с соседними диапазонами итераторы на текущий диапазон не изме-
	нятся.

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

Сейчас мне этот подход не нравится. Гораздо разумнее реализован вариант в диссертации Романенко. У него диапазоны открытые (left, right), при этом границами служат сами сопоставленные элементы. При сопоставлении проверяется, что граница не пустая, сохраняется на вершине стека под очередным номером новый элемент, никакие другие указатели не изменяются.

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

Недостатком кода Романенко является наличие команды SETB — установки диапазона. Анализируемый диапазон в командах явным образом не передаётся, вместо этого есть некоторый «текущий». И при сопоставлении текущий модифицируется. А это значит, что компилятор должен соблюдать локальность при трансляции образцов — минимизировать количество команд SETB. Если в текущем диапазоне сопоставляется повторная t-переменная, а в соседнем — константная литера, то по умолчанию выгоднее сопоставить повторную переменную, поскольку иначе придётся вставить SETB.

Что предлагается

Предлагается воплотить подход Романенко, но с модификациями. Предлагается использовать те же 4-байтовые команды, но в них передавать не один номер диапазона, а пару номеров граничных элементов. Соответственно, команда SETB становится не нужна. Остаётся один байт на номер инструкции и один байт на значение инструкции. Точно также, как и у Романенко, для t-переменных тоже хранить пару указателей, это удобно.

Предлагается также хранить e-переменные как закрытые диапазоны [begin, end], на этапе сопоставления пустые переменные хранить «нахлёстом» — end->next == begin. Перед построением правой части переменные будут нормализоваться, т.е. пустые вновь будут изображаться парой нулевых указателей. Прежде всего, это упростит сопоставление с повторными переменными — не придётся особым образом рассматривать пустой диапазон. Скорее всего упростятся циклы удлинения открытых переменных, по той же причине. В оптимизации построения результатных выражений можно будет разрешить плиткам начинаться и кончаться на e-переменную — для плиток, целиком состоящих из одних e-переменных, потребуется нормализация, остальное будет работать нормально.

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

Из других дополнений. Команды icPushStack всегда идут парами — помещается на стек закрывающая, потом открывающая скобка. Имеет смысл ввести команду, которая кладёт на стек сразу обе скобки. Получим экономию на одной команде.

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

[Mazdaywik]

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

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

case icCharLeft:
  {
    if (left->next == right)
      MATCH_FAIL;
    left = left->next;
    if (left->tag != cDataChar || left->char_info != rasl->val)
      MATCH_FAIL;
    context[top++] = left;
  }
  break;

С явным хранением диапазонов уже так:

case icCharLeft:
  {
    Iter left = context[rasl->left];
    Iter right = context[rasl->right];
    if (left->next == right)
      MATCH_FAIL;
    left = left->next;
    if (left->tag != cDataChar || left->char_info != rasl->val)
      MATCH_FAIL;
    context[top++] = left;
  }
  break;

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

Выше описан «недостаток» SETB: выбор очередной «лёгкой» команды отождествления (символ, скобки, любая s-переменная, закрытая e-переменная, новая t-переменная) может приводить к избыточным командам SETB, минимизация команд SETB может приводить к чередованию лёгких и тяжёлых команд. Это не недостаток самой команды, это недостаток наивной реализации. Более разумная реализация будет выбирать из четырёх категорий команд:

1. Лёгкая команда из текущего диапазона.
2. Лёгкая команда из другого диапазона.
3. Тяжёлая команда из текущего диапазона.
4. Тяжёлая команда из другого диапазона.

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

Но и этот подход не идеален. Можно придумать примеры, когда лёгкие и тяжёлые команды всё равно будут чередоваться. Например:

t.X t.X A e.Y

Здесь символ A, очевидно, лёгкая команда, но прежде необходимо выполнить сопоставление с повторной переменной. Возможное решение — разнести распознавание t-переменных и проверку одноимённых на равенство. Аналогично можно поступить и с некоторыми повторными e-переменными, например, (e.X) (e.X) — две закрытые и проверка значений на равенство.

Будет ли окупать себя такое разделение одной команды на две — вопрос исследования.

Но вообще можно предусмотреть проход peephole-оптимизации — соответствующие две последовательные команды сливать в одну (t-переменная слева + две t-переменные равны → повторная t-переменная слева).

И вообще, если уж объединять команды, можно для каждой команды сопоставления предусмотреть двойник — команда + SETB, которая загружает диапазон, а затем сопоставляет. Осмысленно ли такое удвоение опкодов — тоже вопрос исследования.

[Mazdaywik]

Оптимизация давно назрела, а у меня самого руки не доходят. Выношу на диплом, чтобы хоть чьи-то руки дошли.

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

Задача предполагает решение двух подзадач:

• Изменения генерации сопоставления с образцом, описанное здесь.
• Генерация кода результатных выражений, как в Рефале-05, описана в Построение результатных выражений как в Рефале-05 #196.

В компиляторе есть ещё режимы оптимизации совместного сопоставления с образцом (флаг -OP) и построения результатного выражения (флаг -OR). Их тоже нужно будет переделать на новую кодогенерацию, вернее, написать новые их варианты.

И ещё, чтобы было совсем весело. Компилятор может генерировать код в двух режимах: режиме генерации интерпретируемого кода («байткода», в рантайме есть интерпретатор) и в режиме генерации кода в C++ (флаг -Od). Нужно доработать оба: в интерпретатор добавить поддержку новых кодов команд, в C++ API добавить новые функции для новых операций.

Материалы:

• Упомянутая диссертация С.А. Романенко — по сути нужно прочитать пункты 3.1…3.12. Возможно, для понимания контекста нужно будет прочитать по диагонали предшествующий текст.
• Генерация кода в Рефале-05 (из руководства по Рефалу-05) — по ссылке описана генерация кода как сопоставления с образцом, так и построения результатного выражения. Сопоставление с образцом в Рефале-5λ устроено также, как и в Рефале-05. Построение результатных выражений нужно сделать таким же, как в Рефале-05. Поэтому прочитать нужно целиком.
• https://github.com/bmstu-iu9/refal-5-lambda/blob/master/doc/РПЗ_Копьев_2016.pdf — записка к ВКР Евгения Копьёва, который делал оптимизацию построения результатных выражений. Алгоритм жадного строкового замощения (GST.ref) править не надо будет (он останется как есть), нужно будет переписать только HighLevelRASL-GenResult-Opt.ref. Вернее, написать альтернативный вариант, т.к. старый тоже нужно оставить.
• https://github.com/bmstu-iu9/refal-5-lambda/tree/master/doc/OptPattern — коллекция записок (курсовые, ВКР) к алгоритму совместного сопоставления с образцом. На самом деле, алгоритм меняться не должен, нужно будет поменять только некоторые детали.

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

На самом деле, слона можно есть по частям. И нужно. Сначала реализовать режимы -Ox и -Oy для базового случая без других оптимизаций (т.е. без -OP, -OR и -Od). Если в этом случае будут указаны несовместимые флаги (например, -OPx или -OyR, или -Odyx, и т.д.), флаги -Ox и -Oy сбрасывать, как будто их не было. Затем добавить поддержку одной комбинации флагов, другой комбинации флагов, третьей… пока не будут работать все комбинации, либо пока не кончится время, отведённое на ВКР.

[Mazdaywik]

Задача не была выбрана в качестве темы ВКР.