Шитый код

Шитый код (англ. threaded code) — один из способов реализации промежуточной виртуальной машины при интерпретации языков программирования (наряду с байт-кодом). Иногда в литературе также встречается термин сшитый код.

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

Шитый код наиболее широко известен как техника, используемая при реализации Форта. Однако он также применялся при реализации языка программирования B (предшественника C). Он также иногда используется при реализации Бейсика, COBOLа и других языков программирования.

Особенности шитого кода

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

Виды шитого кода

Подпрограммный код

Эта разновидность шитого кода по сути ничем не отличается от машинного кода. Это последовательность вызовов уже скомпилированных подпрограмм.

Программа имеет следующий вид:

 call Sub1;
 call Sub2;
 call Sub3;

Прямой шитый код

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

 call Interpretator;
 AddrSub1;
 AddrSub2;
 ...
 AddrEXIT;
 ...
 ...
 Interpretator: машинный код, NEXT
 ...
 Sub...: машинный код, NEXT
 ...
 EXIT: машинный код, NEXT

В прямом шитом коде любое определение (например Sub) начинается машинным кодом. Интерпретатор должен запомнить в стеке возвратов прошлое значение счётчика инструкций (это не PC, или IP, а другой, который перемещается по коду Форта), а сделать текущим свой адрес возврата. Теперь он станет новым указателем на код Форта. В ряде версий для Intel x86 используется регистр SI. При чтении данных по косвенному адресу в этом регистре его значение меняется автоматически.

NEXT — это последовательность, используемая вместо return. Если мы завершаем Sub1, то NEXT обращается к счётчику инструкций Форта, изменяет его на размер кода и на следующем шаге уже исполняется первая машинная команда из Sub2. Скорость перехода получается не хуже, чем у пары команд return — call. Но переход NEXT в специализированном процессоре может быть выполнен как одна команда.

EXIT — восстанавливает предыдущее значение счётчика команд и переходит по соответствующему адресу.

Косвенный шитый код

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

 AddrInterpretator;
 AddrSub1;
 AddrSub2;
 ...
 AddrEXIT;
 ...
 ...
 Interpretator: Адрес машинного кода, машинный код, NEXT
 ...
 Sub...: Адрес машинного кода, машинный код, NEXT
 ...
 EXIT: Адрес машинного кода, машинный код, NEXT

Свёрнутый шитый код

Может, например, использоваться для сокращения размера кода, когда он имеет критическое значение. Он может быть как прямым, так и косвенным. Вместо прямых адресов подпрограмм и кодов в нём используются их свёртки, которые, вообще говоря, короче этих адресов. Используя 2-байтные коды, можно использовать адресное пространство, значительно превышающее 64 килобайт.

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

В ряде случаев для свёртки может использоваться адресная таблица. Шитый код представляет собой положение адреса в таблице. Интерпретатор читает из таблицы этот код и совершает переход по соответствующему адресу.

Байт-код можно рассматривать как специальный случай свёрнутого шитого кода с адресной таблицей.

Литература

• Баранов С. Н., Ноздрунов Н. Р. Язык Форт и его реализации. — Л.: Машиностроение, 1988. — 157 с. — ISBN 5-217-00324-3. — Раздел 2.1 — Шитый код и его разновидности.

Ссылки

• Threaded Code (англ.)
• Moving Forth (англ.)