COLLAPSE. История создания.
Владимир Кладов, 2005-2006.

Эта история началась уже довольно давно. Примерно год назад, в 2004 г. Тогда, в процессе дописывания все новых и новых функций к своему эмулятору Спектрума (EmuZWin) я обнаружил, что код программы угрожающе растет, и архив, предназначенный для выкладывания на моем сайте, быстро приближается к мегабайту. И это несмотря на использование KOL/MCK, аккуратное программирование на ассемблере, использование упаковщиков... Тогда я начал задумываться, нельзя ли сократить код еще больше. Первое, что напрашивалось - это использование более компактного Z80-кода для программирования интерфейсной части самого  эмулятора (кстати, не факт, что я еще не воспользуюсь этой идеей в будущем). Да, Z80 - это несколько другая машина, чем IBM PC, хотя бы уже потому, что основная единица данных, с которой работает процессор - это все-таки 1 байт, а не 4. Пришлось бы делать специальную версию эмулирующего кода, который позволял бы эмулировать несуществующую в реальности Z80x2 машину, с автоматическим увеличение разрядности с 16 до 32 бит. И в конечном счете, переписывать весь код на ассемблер Z80x2.

Другая моя идея складывалась параллельно, и заключалась в использовании стековой машины наподобие Forth (Форт). Известно, что код форт-машины чрезвычайно компактен, и благодаря двухстековой архитектуре (один стек - для адресов возвратов, другой - для вычислений) допускает простую свертку функций, путем простого вынесения общих кусков кода за скобки отдельной процедуры. Прельщала меня в этом варианте возможность автоматической генерации кода MCK (т.е. код генерируется одновременно для Паскаль-версии инициализатора формы, и параллельно - для Форт-версии этого же инициализатора). Т.е. можно было бы получить автоматическое превращение части кода (и довольно немалой - в моем эмуляторе EmuZWin) в П-код, в несколько раз более компактный, и быстро сократить размер приложения. Часть кода, конечно, пришлось бы переписать руками на Форт-подобный язык, но без ручного переписывания части кода все равно не обойтись. А здесь я получал бы автоматически возможность использования новой технологии уменьшения кода во всех MCK-проектах. Достаточно объявить в опциях проекта символ условной компиляции Pcode, и как по мановению волшебной палочки - программа еще несколько уменьшилась.

Проблема замедления работы приложения из-за того, что часть кода будет не машинным кодом IBM PC, а эмулируемым байт-кодом Форт-машины, меня не волновала. По большому счету, для процедур инициализации замедление в несколько раз не смертельно,  кроме того, я уверен, что большая часть времени отнимается не работой моего собственного кода, а обращением к функциям API операционной системы.

Оставались проблемы состыковки Форт-машины и реальной среды Win32 на платформе PC (и в частности, среды программирования Delphi). Естественный, напрашивающийся сам собой способ вызова П-кода из машинного кода - это вызов подпрограммы эмуляции. При написании такого участка кода на ассемблере IBM возможно даже разместить П-код непосредственно вслед за командой CALL Emulate. Но при таком подходе на каждый участок кода, превращенный в П-код, пришлось бы затрачивать еще 5 байт на вход в эмулятор. Тут мне на ум пришло использовать систему обработки исключений в Windows (SEH). Если поставить свой обработчик выше всех прочих, так, чтобы он перехватывал исключения по недопустимому коду операции (привилегированные команды, например), то достаточно было бы использовать однобайтовый код вместо 5-байтовой инструкции CALL. Выполнение при таком подходе еще более замедлилось бы, разумеется. Но как я уже заметил, скорость меня особо не волновала. Кроме того, речь шла прежде всего об инициализирующих кусках кода, которые должны были отработать один раз - при запуске приложения или при первом открытии формы. Ну, и способ с вызовом эмулятора через CALL все еще оставался как возможный, просто появился новый более экономичный по размеру - в дополнение к предыдущему. В итоге я остановился на использовании 4х подряд следующих кодов $E4...$E7 - с них в PC начинаются команды IN/OUT, которые естественно недоступны напрямую на уровне привилегий пользователя и вызывают требуемое мне исключение. Почему 4 подряд следующих кода операции - см. ниже.

После проведения успешных экспериментов с SEH-обработчиком я двинулся дальше и попробовал как смог определить архитектуру П-машины. (Далее буду называть ее П-машиной, все-таки это не Форт-система, а просто 2х-стековая эмулируемая машина со своим набором команд). Собственно, под архитектурой здесь я определяю набор команд. Сразу скажу, что первый вариант, как и должно было случиться, оказался не очень удачным. Код эмулятора достигал 300-500 байтов, система команд оказалась несколько громоздкой. Наличие 1-байтных команд переходов наряду с 2х-байтыми добавляло головной боли при написании компилятора из исходного П-кода в откомпилированный байт-код. (И это при том, что участки кода, генерируемые MCK, вообще не требуют условных или безусловных переходов - они линейны). При проектировании первой версии я не учел то обстоятельство, что любая процедура в машинном коде фактически является новой командой П-машины, и нет вообще необходимости вводить ряд специализированных команд, логически отделяя их от вызовов процедур, кроме случаев, когда только часть байта используется для адресации, нумерации и задания других параметров. Тем не менее, развитие первой версии продвинулось вплоть до реализации эмулятора, написания BaseLib.pas, изготовления полнофункционального П-компилятора, отладчика П-кода, добавления в MCK кода для генерации П-кода наряду с обычным кодом - по крайней мере для нескольких объектов. В конце концов в этой работе наступил долгожданный перерыв, примерно на полгода, в течение которого я делал множество других вещей, усовершенствовал KOL&MCK, опять модифицировал эмулятор EmuZWin (и он все-таки перерос размер 1Мбайт архива), продолжал многие существующие проекты (Zoomer3, Hexapad), делал новые (А ну-ка почитай, Planogramma), начинал (без особой надежды на скорое завершение) новые большие и маленькие проекты (Periscope, например)... Разумеется, я еще и домашними делами занимался, и на даче жил (купил ноутбук), ребенок за это время пошел в школу, мы купили кучу мебели, обновили гардероб, я поругался с начальством по поводу низкой зарплаты (хм, да: я ведь еще и на работу хожу, и чего-то и там программирую, а не только в форумах отвечаю...), я начал финальную фазу ремонта квартиры, продолжающегося перманентно уже 7 лет...

Когда я наконец вернулся во время своего осеннего отпуска в идее Collapse, мысли мои прояснились, и я понял, что надо переделать ядро эмулятора и базовую архитектуру П-машины. Аксиомой должно быть: минимум П-команд помимо вызовов процедур по таблице, причем именно тот минимум, который необходим для команд с разрядностью операндов, не кратной 1 байту. И вот что получилось:

0xxx.xxxx - все, что начинается со старшего бита 0 - это переходы и загрузка коротких констант
1xxx.xxxx - все, что начинается со старшего бита 1 - это вызовы подпрограмм.

Далее уточняя, получаю:

000x.xxxx - загрузка констант от -16 до +15
001x.хххх yyyy.yyyy - безусловный переход на -4096..+4095 байт
010х.хххх yyyy.yyyy - условный переход (условие: на вершине вычислительного стека 0), так же на -4096..+4095 байт
011x.xxxx yyyy.yyyy - аналогично, но переход выполняется при условии, что на стеке не 0.

И для второй группы:

10xx.xxxx yyyy.yyyy - длинный (2х-байтный - это длинный) вызов процедур с номерами от 0 до 16383 по таблице процедур
11xx.xxxx - короткий (1-байтовый) вызов до 64 процедур.

И ВСЕ! Все остальные "команды" реализуются как процедуры (машинные или в П-коде) и включаются в код готового приложения лишь по мере необходимости. После учета всех изменений (в том числе рассмотренных ниже) код самого эмулятора уменьшился до 105 байт. Плюс около 132 байт занимает инициализация системы Collapse и обработчик SEH-исключений. Все прочие накладные расходы - это таблица адресов процедур, по 4 байта на каждый вход. Причем, если в предыдущей версии использовалась еще одна таблица битовых флажков (фактически по 2 бита на каждый вход - они задавали количество параметров, передаваемых через стек), то в новой версии удалось от этой таблицы отказаться и как следствие код вызова значительно упростился. Для вызова Паскаль-процедур (функций, методов) я решил использовать другой механизм, нежели прямой вызов. С помощью команды загрузки константы на вершину вычислительного стека загружается индекс процедуры в таблице (разумеется, когда все параметры для нее на стеке уже подготовлены), затем вызывается одна из трех процедур-команд PASCAL1, PASCAL2 или PASCAL3, которая осуществляет переброску нужного числа входных параметров из стека в регистры и передает управление вызванной процедуре.

Механизм возврата значения функции через регистр EBX остался тот же, что и в предыдущей версии. Если результат функции нужен, он должен быть переложен на стек немедленно после вызова функции отдельной командой RESULT. Даже в этом случае вызов функции получается вдвое короче, чем 5-байтный CALL в PC. Можно было бы сделать и наоборот - после вызова функции результат оказывается на вершине стека, а если он не нужен, он удаляется специальным вызовом процедуры-команды DEL. Но тогда при написании (или автоматическом формировании) П-кода надо точно знать, возвращает ли вызываемая процедура или функция значение. Вариант с возвратом значения через EBX значетельно проще для реализации.

В новой версии для хранения переменной SELF стал использоваться регистр EBP, в результате намного упростилась работа с ним, кадр возврата из П-процедуры сократился с 12 -16 байт до 8 байт. В нем теперь сохраняется только значение регистра  ESI (указатель очередной инструкции П-машины) и регистр EBP (текущее значение переменной SELF).

В новой версии все переходы стали 2х-байтовыми, а это означает отсутствие проблем с оптимизацией переходов в П-компиляторе (в программе, которая превращается последовательность П-команд в соответствующую ей последовательность ассемблерных инструкций). И при этом переход с помощью таких 2х-байтовых команд возможен на -4096..+4095 байт, что намного больше, чем позволяют 2х-байтовые команды переходов в PC (-128..+127). Этого должно хватить на все случаи, а если и не хватит, всегда можно добавить процедуру-команду для перехода на -32768..+32767 или даже на -2**23..+2**23-1. То же самое и с процедурами. Всегда возможно увеличить таблицу процедур за пределы 16384 входов, и выполнять вызов процедур последовательностью из двух команд - загрузки константы на вершину стека, и вызовом специальной функции, которая вызывает подпрограмму по ее номеру в вершине стека. Или добавить процедуру-команду, которая принимает 2х- или даже 3х-байтный индекс в качестве операнда. Таким образом, П-машина легко масштабируется вверх по разрядности - при необходимости. Более того, если число процедур существенно меньше, чем 16384, то вполне возможно увеличивать количество процедур, вызываемых 1-байтной командой, за счет снижения разрядности при 2х-байтном обращении к процедурам. Например, если число процедур не превышает 1024, то разрядности можно перераспределить следующим образом:

1000.00xx yyyy.yyyy - вызов до 1024 процедур 2х-байтовый
$85..$FF - вызов до 123 процедур 1-байтовый

Как и в предыдущей версии, П-компилятор выполняет первый проход компиляции с целью определить, какие именно П-процедуры используются в коде, и посчитать количество использований каждой процедуры из таблицы процедур. Затем все процедуры в таблице сортируются по убыванию числа использования, таким образом, те из них, что вызываются чаще, автоматически с большей вероятностью вызываются теперь 1-байтовой командой. Естественно, это экономит код. В новой версии П-компилятора я задумал некоторое усовершенствование процесса формирования таблицы процедур. Для того, чтобы по возможности пореже изменять на диске файл, содержащий таблицу процедур, сортировка теперь не меняет содержимое таблицы каждый раз, а только в случае, если возникает перенос отдельных процедур через границу 1- и 2х-байтного вызова. Кроме того, особо стали учитываться процедуры, которые всегда вызываются через загрузку своего индекса на стек константой и последующим обращением к процедуре, их вызывающей. Такие процедуры вообще не учитываются в новой версии для целей определения необходимой разрядности команд вызова подпрограмм, и могут спокойно располагаться за границей такой разрядности (как например, для случая 1024 процедур, адресуемых 2х-байтными вызовами подпрограмм - такие процедуры могут располагаться и за индексом 1024).

Так же, в новой версии Collapse намного упростилась работа со стеком возвратов. Очевидно, что для мультипоточной рабочей среды требовалось создавать как минимум один П-стек возвратов для каждого потока. Если в пределах потока использовался один и тот же стек, то для того, чтобы он мог корректно использоваться при последовательном вызове из П-кода машинной подпрограммы, из которой, в свою очередь, опять вызывается П-кодированная процедура, и так далее - в любом порядке, то возникала необходимость в довольно сложном алгоритме переиспользования этого П-стека (его каждый раз приходилось находить, сопоставляя каждому потоку свой П-стек возвратов, более сложно оформлять кадр возврата, обеспечивать автоматическое увеличение размера и т.д.) Сам вызов и возврат становился довольно медленным и неуклюжим. В новой версии при вызове П-процедуры из машинной процедуры всегда выделяется порция памяти под П-стек (например, 1Кбайт - по умолчанию). И в начало (дно) этого стека укладывается сохраняемые регистры EBX, ESI, EBP, EDI, собственно адрес возврата в вызвавший машинный код, сам стек с этого момента адресуется регистром EDI, и оформляется специальный кадр возврата на адрес 0, который "скажет" процедуре возврата, что надо вернуть все сохраненные регистры и выполнить окончательный возврат в машинный код, освободив выделенную под П-стек память. Да, при постоянных вызовах П-кода из машинного кода и наоборот само выделение памяти - не лучшее с точки зрения скорости работы решение. Но, если П-процедуры не злоупотребляют вызовом машинных процедур, которые, в свою очередь, снова вызывают П-процедуры - и так далее, то на скорости это существенно не сказывается. (В частности, в случае, когда П-код используется прежде всего в МСК-проектах в автоматическом режиме, такая ситуация вообще невероятна). Зато появляется очень большой плюс: автоматическое решение для многопоточной среды проблемы нескольких стеков, причем без дополнительного, довольно сложного, как в прежней версии, программирования. Не говоря уже о тех плюсе, что существенно сокращается код эмулятора, и эмуляция вызовов процедур работает намного быстрее. На данном этапе, скорость работы эмулируемого кода по сравнению с машинным кодом, предполагается медленнее не более чем в 5-10 раз, а это уже слишком мизерная разница, тем более что (как я отмечал выше) основное время исполнения приходится на API-функции, а не на эмуляцию.

В пошаговый отладчик так же были внесены изменения в направлении его упрощения. Прежде всего, я избавился от необходимости передавать ему информацию о пути к модулю, номере исходной строки - прямо из П-кода. Теперь для компиляции проекта в режиме работы с отладчиком достаточно стало указать в опциях проекта символ COLLAPSE_DEBUG, и при запуске мы сразу попадаем в пошаговый отладчик, "остановленный" на первой строке П-кода. Работа П-отладчика стала базироваться исключительно на .debug-файлах, подготовленных П-компилятором, и мап-файле, изготовленном при линковке проекта (опция "detailed map" - должна быть включена в опции проекта обязательно, много она не тратит, так что ее проще включить раз и навсегда). Передавать информацию о местонахождении файлов проекта в отладчик программа стала через отдельную точку входа InitCollapseDebug в dll отладчика. На самом деле, передается туда результат функции GetStartDir, т.е. путь к исполнимому экзешнику (или dll) проекта. Т.е. требуется, чтобы выполнимый бинарник проекта строился там же, где располагаются его исходные тексты. Зато сам отладчик (dll) может располагаться где угодно. Надо лишь в файле PDebuger.cfg в папке проекта указать вместе с ключом /D полный (или относительный) путь к DLL отладчика.

Формат вывода отладочной информации в файл с дополнительным расширением .debug пришлось несколько изменить. По сравнению с предыдущей версией, в описание каждого П-оператора теперь через косую черту по возможности выводится длина его машинного кода. Иногда на конце строки длина не может быть измерена (оставил на усмотрение отладчика, в крайнем случае хотя бы первый байт кода пусть выделит, или - до конца строки). Итого, для каждого оператора формат отладочных данных <смещение в строке> : <смещение в коде от начала процедуры> / <длина кода оператора>. В отладчик пришлось вносить изменения с тем, чтобы он мог определить, какая процедура текущая, и соответственно, правильно использовать отладочные данные для отображения кода, и главное - для выделения текущего кода и текущего оператора в исходнике красным цветом. Без этого отладка становилась весьма затруднительной. Но самой серьезной проблемой оказалось связывание строк с исходным П-кодом со строками ассемблерного кода, в который компилировался П-код. Дело в том, что отладчик стал теперь получать информацию о соответствии исходных строк модуля с адресами исключительно по информации из мап-файла. А там идет указание на строки, в которых находится ассемблерный код, а не на П-код (который вообще оказывается как бы комментарием). Пришлось менять вывод отладочной информации еще раз, и выводить вместе с номером строки П-кода еще и номер строки ассемблерного кода. И обеспечивать в компиляторе построчное соответствие ассемблерного кода исходному П-коду.

Когда заработало ядро эмулятора П-машины для новой версии, я занялся генерацией кода MCK (который генерирует код, выполняемый в run-time). Для всех процедур типа SetupFirst, SetupParams, SetupLast, GenerateTransparentInits и прочих, создающих run-time код на основе design-time свойств зеркальных компонентов, надо было создать параллельный набор процедур P_SetupFirst, P_SetupParams и т.д., которые генерировали бы П-код вместо паскалевского кода. На самом деле, работа непростая, особенно на первых порах. Программирование в стиле Форта само по себе не очень привычное занятие (обратная польская запись, умение представлять себе состояние стека после каждой команды, умение думать "наоборот"), а тут еще приходилось писать не сам код, а его генератор, и решать множество возникающих мелких и не очень мелких проблем. Фактически в результате этой работы был создан "стандарт" на правила оформления исходного кода, достаточно удобный для решения моей задачи. Например, я "придумал" псевдо-макросы, и стало возможным (например) оформлять загрузку константы на вершину стека единообразно: L(число), независимо от величины числа. А дальше уже макрос определяет, какой способ должен использоваться для загрузки этой константы, т.е. будет использоваться однобайтовая команда (для -16..+15), двухбайтовая команда загрузки байта LoadByte, и т.д. Аналогичный псевдо-макрос был "придуман" для вызова паскаль-подпрограмм, передающих некоторое количество параметров через регистры EAX, EDX, ECX. Число передаваемых через регистры команд указывается вслед за наименованием процедуры в угловых скобках, и это указание является для П-компилятора указанием преобразовать данный вызов в последовательность двух команд: загрузки на вершину стека номера подпрограммы, и вызова одной из подпрограмм PASCAL1, PASCAL2 или PASCAL3. Для вызова подпрограмм, не имеющих параметров, или передающих параметры только через стек (соглашение stdcall) они вызываются непосредственно.

В конце концов, большая часть зеркального кода была приспособлена, я ускоренными темпами завершал эту работу. И по дороге решил начать составлять руководство по применению. Это описание истории так же будет приложено, для полноты описания. Может быть, оно поможет тем, кто будет изучать Collapse более тщательно, чем на уровне простого использования. Но в этот момент, глядя в код, который стал получаться в результате работы П-компилятора, я остро ощутил потребность переделать (опять!) систему команд, а именно, сделать вызовы всех подпрограмм, в том числе Паскалевских, двухбайтовыми. Примерно день ушел на эту работу, и - о, чудо, все заработало (т.е. ничего не сломалось, а вызовы стали действительно двухбайтовыми, а не 3трех-четырех байтовыми). Пришлось пересматривать и корректировать всю уже написанную документацию.

Первый релиз Collapse состоялся с версией KOL/MCK 2.25, но реально все было готово только к версии 2.27, т.е. уже в начале 2006 года. Применение Collapse к реальному проекту показало, что байт-код примерно в 2.2 раза компактнее аналогичного машинного. На 5 формах мне удалось сэкономить около 50 Кбайт. До того, как двигаться дальше переделывать весь проект под Collapse, я потратил некоторые дополнительные усилия на оптимизацию П-компиляции. Уже в версии 2.29 на втором проходе перекомпилировались только те модули, которые содержат П-код, вызывающий процедуры, для которых изменилось количество байтов, требуемых на их вызов (т.е. даже не просто изменившие свой номер). А модули, вообще не содержащие П-код, на втором проходе даже не просматриваются.

В районе версии 2.31 Collapse в основном был завершен. На своем приложении я сэкономил 100Кбайт (и 21Кбайт - на сжатом). Чтобы сэкономить больше, надо было превращать в П-код другие процедуры на Паскале, и 8.01.2006 я стартовал проект компилятора из паскаля в П-код (уже второго такого, первый был выполнен для standalone версии, вместе с Collapse-1). Но на этот раз мне нужен был компилятор, который превращал бы по отдельности каждую указанную Пскаль-процедуру.

В районе 10.01.06 выяснилась неприятность: Collapse не работает под NT4 (и вероятно, под 9х). Пришлось срочно переделывать SEH-обработчик для перехвата входа в П-эмулятор. Нельзя было, как оказалось, изменять указатель стека контекста. Под ХР и 2К хотя это работало.

Примерно 19.01.06 пользователи (EmuZWin 2.7 bld 2.5a) сообщили, что нет совместимости с windows9x. Как показала отладка, в Windows 9x команды in/out не являются привилегированными. Пришлось срочно доделывать такой вариант Collapse, в котором в качестве префикса для переключения в эмуляцию используется 5-байтный вызов подпрограммы (call RunPCodeN, N=0..3). Получилось чуть быстрее - так как не используются исключения, код, правда, на каждой отконвертированной процедуре больше на 4 байта. 21.01.06 совместимость новый вариант кода был готов.