Mazdaywik
commented
5 years ago Предлагается воплотить подход Романенко, но с модификациями. Предлагается использовать те же 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 может приводить к чередованию лёгких и тяжёлых команд. Это не недостаток самой команды, это недостаток наивной реализации. Более разумная реализация будет выбирать из четырёх категорий команд:
- Лёгкая команда из текущего диапазона.
- Лёгкая команда из другого диапазона.
- Тяжёлая команда из текущего диапазона.
- Тяжёлая команда из другого диапазона.
Команды, соответственно, упорядочены по снижению их привлекательности. Такой подход уже похож на разумный компромисс между минимизацией команд SETB и приоритетным выбором лёгких команд.
Но и этот подход не идеален. Можно придумать примеры, когда лёгкие и тяжёлые команды всё равно будут чередоваться. Например:
t.X t.X A e.YЗдесь символ A, очевидно, лёгкая команда, но прежде необходимо выполнить сопоставление с повторной переменной. Возможное решение — разнести распознавание t-переменных и проверку одноимённых на равенство. Аналогично можно поступить и с некоторыми повторными e-переменными, например, (e.X) (e.X) — две закрытые и проверка значений на равенство.
Будет ли окупать себя такое разделение одной команды на две — вопрос исследования.
Но вообще можно предусмотреть проход peephole-оптимизации — соответствующие две последовательные команды сливать в одну (t-переменная слева + две t-переменные равны → повторная t-переменная слева).
И вообще, если уж объединять команды, можно для каждой команды сопоставления предусмотреть двойник — команда + SETB, которая загружает диапазон, а затем сопоставляет. Осмысленно ли такое удвоение опкодов — тоже вопрос исследования.
Эта задача — подзадача для #194.
Мотивация
Как описано в #169, текущий язык сборки сформировался стихийно. Сначала я придумал кодогенерацию в Си++ для первой версии Простого Рефала. Она основана была на диапазонах вида
[first, last], от которых откусываются сопоставляемые объекты:https://github.com/bmstu-iu9/refal-5-lambda/blob/ab2c5c1d9b10a2c73843619c32bb29c2443fc35d/doc/historical/note000.txt#L909-L921
Позже был разработан интерпретируемый код, но подход остался тем же. Была реализована оптимизация построения результатных выражений, где нужно было сохранять указатели на части аргумента — команды сопоставления дополнились близнецами, которые ещё и сохраняют сами указатели. На сколько от этого теряется производительность, я не мерял.
Сейчас мне этот подход не нравится. Гораздо разумнее реализован вариант в диссертации Романенко. У него диапазоны открытые
(left, right), при этом границами служат сами сопоставленные элементы. При сопоставлении проверяется, что граница не пустая, сохраняется на вершине стека под очередным номером новый элемент, никакие другие указатели не изменяются.Что это даёт. В случае удлинения переменных или оптимизации образцов не приходится сохранять диапазоны, они не меняются. Код самих команд получается проще. Их можно описать макросом, который будет встроен в код интерпретатора (или даже в код прямой кодогенерации). Автоматически получается базис для оптимизации построения правой части (хотя таковая оптимизация у него не выполняется). Автоматически получается базис для построения дерева сопоставления (основанный на построении общих префиксов).
Недостатком кода Романенко является наличие команды
SETB— установки диапазона. Анализируемый диапазон в командах явным образом не передаётся, вместо этого есть некоторый «текущий». И при сопоставлении текущий модифицируется. А это значит, что компилятор должен соблюдать локальность при трансляции образцов — минимизировать количество командSETB. Если в текущем диапазоне сопоставляется повторная t-переменная, а в соседнем — константная литера, то по умолчанию выгоднее сопоставить повторную переменную, поскольку иначе придётся вставитьSETB.Что предлагается
Предлагается воплотить подход Романенко, но с модификациями. Предлагается использовать те же 4-байтовые команды, но в них передавать не один номер диапазона, а пару номеров граничных элементов. Соответственно, команда
SETBстановится не нужна. Остаётся один байт на номер инструкции и один байт на значение инструкции. Точно также, как и у Романенко, для t-переменных тоже хранить пару указателей, это удобно.Предлагается также хранить e-переменные как закрытые диапазоны
[begin, end], на этапе сопоставления пустые переменные хранить «нахлёстом» —end->next == begin. Перед построением правой части переменные будут нормализоваться, т.е. пустые вновь будут изображаться парой нулевых указателей. Прежде всего, это упростит сопоставление с повторными переменными — не придётся особым образом рассматривать пустой диапазон. Скорее всего упростятся циклы удлинения открытых переменных, по той же причине. В оптимизации построения результатных выражений можно будет разрешить плиткам начинаться и кончаться на e-переменную — для плиток, целиком состоящих из одних e-переменных, потребуется нормализация, остальное будет работать нормально.Также предлагается модифицировать код построения результатных выражений, как описано в #196, в контексте текущей заявки речь идёт об учёте последовательного выделения памяти.
Из других дополнений. Команды
icPushStackвсегда идут парами — помещается на стек закрывающая, потом открывающая скобка. Имеет смысл ввести команду, которая кладёт на стек сразу обе скобки. Получим экономию на одной команде.Новый язык сборки позволяет сравнительно просто оптимизировать совместное сопоставление с образцом — выделяя префиксы. Можно сделать режим простого выделения префиксов режимом по умолчанию.