Регистрация | Войти
Lisp — программируемый язык программирования

Добавление примитивов виртуальной машины SBCL

Автор: Дмитрий Кальянов

Источник: http://dmitry-vk.livejournal.com/32714.html

В SBCL (как и многих других компиляторах) существуют т.н. примитивы - языковые конструкции, не сводимые к другим. В SBCL такие примитивы реализуются посредством преобразования на уровнях IR1 (на котором код представлен в виде графа потока управления/данных) и на уровне IR2 (уровень виртуальной машины). На уровне IR1 реализуются такие конструкции, как let, lambda, а более простые вещи вроде "встроенных функций" (арифметика, выделение памяти и прочее) - в виде инструкций виртуальной машины, с которыми связаны процедуры генерации машинного кода.

Эти инструкции называются VOP'ами, и SBCL так устроен, что набор доступных инструкций (VOP'ов) не фиксирован, и их можно пополнять. Например, в проекте sb-cga (computer graphics algebra) путем добавления нескольких VOP'ов реализовано быстрое умножение матриц и векторов на SSE2.

Рассмотрим простейший пример - добавим ассемблерную вставку, которая делает XOR двух чисел.

Абстрактно, код ассемблерной вставки выглядит (в интеловском синтаксисе) так:

mov result, arg1
xor result, arg2

(здесь result - имя регистра, в который надо записать результат, arg1 и arg2 - регистры, в которых лежат аргументы).

Чтобы вставить этот код в код на лиспе, надо сделать две вещи:

  • Объявить новую примитивную функцию (назовем ее my-xor)
  • Добавить новую VOP, соответствующую этой примитивной функции
  • Определить функцию (на этот раз обычную функцию, а не примитив языка) my-xor

Проделав первые две операции, SBCL научится компилировать выражения вида (my-xor a b).

За определение примитива отвечает макрос SB-C:DEFKNOWN, в который передаются типы аргументов и возвращаемых значений функции. В нашем примере будем использовать только короткие числа - fixnum.

(sb-c:defknown my-xor (fixnum fixnum) fixnum)

Добавить новую VOP можно макросом SB-C:DEFINE-VOP. У этого макроса есть много параметров, касающихся кодогенерации (выбор регистров, типы аргументов, временные регистры, время жизни различных значений), оптимизации ("стоимость" операции), и других. Для заданного примера определение VOP выглядит следующим образом:

(sb-c:define-vop (my-xor)
  (:translate my-xor)
  (:args (a :scs (sb-vm::any-reg))
         (b :scs (sb-vm::any-reg))
)

  (:arg-types fixnum fixnum)
  (:results (c :scs (sb-vm::any-reg)))
  (:result-types fixnum)
  (:policy :fast-safe)
  (:generator
   0
   (sb-c::inst sb-vm::mov c a)
   (sb-c::inst sb-vm::xor c b)
)
)

Вкратце разберем различные части этого объявления

  • (sb-c:define-vop (my-xor) ...) задает имя VOP'а. В принципе, имя VOP'а может не совпадать с именем функции, и часто бывает так, что одной функции соответствуют несколько VOP'ов (например, различные варианты реализации функции +)
  • (:translate my-xor) указывает, что определяемый VOP реализует примитив my-xor. Эта часть определения указывает, что для компиляции выражения (my-xor a b) следует использовать этот VOP.
  • (:args ...) и (:results ...) описывает имена и то, как подаются аргументы и сохраняются результаты в VOP. :SCs задает список допустимых storage-class'ов (можно считать, что storage-class - это либо некоторое множестве регистров, либо стек, либо стек FPU). Класс sb-vm::any-reg сооветствует любому регистру общего назначения.
  • (:arg-types ..) и (:result-types ...) задает типы аргументов, к которым применим VOP и тип возвращаемого значения.
  • (:policy :fast-safe) определяет, когда следует вызывать этот VOP (если имеется выбор среди доступных VOP'ов): :small - когда нужен маленький код, :fast - когда нужен быстрый код, :safe - безопасный код, и :fast-safe - быстрый и безопасный.
  • (:generator 0 ...) задает собственно процедуру генерации машинного кода. Внутри этой процедуры доступен макрос SB-C::INST, реализующий интелоподобный синтаксис ассемблера. Аргументы для инструкций можно задавать:
  1. числовыми константами
  2. ссылками на аргументы, результат и временные переменные (используется в примере)
  3. ссылками на конкретные регистры (например, SB-VM::EAX-TN - ссылка на регистр EAX),
  4. ссылками на адрес памяти (например,
    (sb-vm::make-ea :dword :base sb-vm::eax-tn :index sb-vm::edi-tn :scale 2 :disp 3)
    - это ссылка 4хбайтное слово по адресу eax + edi * 2 + 3)
  5. ссылками на метки, которые явно создаются с помощью gen-label и emit-label:
    (let ((l (gen-label)) (inst jmp l) (emit-label l))
    - это полезно в макросах, используемых в теле VOP
  6. ссылками на метки, задаваемые символом в теле генератора:
    (:generator 0 (inst jmp label-1) label-1))
  7. ссылками на какие-то объекты (например, (sb-vm::make-fixup "strlen" :foreign) - ссылка на внешнюю функцию strlen). При этом, в качестве процедуры генерации может быть произвольный код на лиспе.

После этого, для полноты надо сделать еще одну маленькую вещь - объявить функцию-обертку над примитивом my-xor, чтобы можно было не только компилировать выражения вида (my-xor a b), но и иметь функцию #'MY-XOR, которую можно передать, например, в map:

(defun my-xor (a b)
  (my-xor a b)
)

На первый взгляд, определение функции my-xor - это бред: функция определена как рекурсивная функция, но без базы рекурсии и вообще без шага рекурсии. Но на самом деле тут определяется функция my-xor не через функцию my-xor, а через примитив my-xor, поэтому компилятор генерирует не вызов функции, а подставляет VOP, соответствующий примитиву.

Убедимся в этом:

(disassemble 'my-xor)
=>

; disassembly for MY-XOR
; 02DED843:       488BD1           MOV RDX, RCX               ; no-arg-parsing entry point
;       46:       4831FA           XOR RDX, RDI               ; <-- вот наш код
;       49:       488BE5           MOV RSP, RBP
;       4C:       F8               CLC
;       4D:       5D               POP RBP
;       4E:       C3               RET
;       4F:       CC0A             BREAK 10                   ; error trap
;       51:       02               BYTE #X02
;       52:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;       53:       54               BYTE #X54                  ; RCX
;       54:       CC0A             BREAK 10                   ; error trap
;       56:       02               BYTE #X02
;       57:       08               BYTE #X08                  ; OBJECT-NOT-FIXNUM-ERROR
;       58:       95               BYTE #X95                  ; RDX
;       59:       CC0A             BREAK 10                   ; error trap
;       5B:       04               BYTE #X04
;       5C:       08               BYTE #X08                  ; OBJECT-NOT-FIXNUM-ERROR
;       5D:       FED501           BYTE #XFE, #XD5, #X01      ; RDI

На данном листинге 2 инструкции по адресу 0x02DED843 - это созданный только что VOP, а остальное - стандартный эпилог функции и код по проверке корректности аргументов функции.

Теперь воспользуемся только что созданным примитивом для определения новой функции:

(defun foo (a b)
  (declare (type fixnum a b)
           (optimize (speed 3) (safety 0))
)

  (my-xor (1+ a) (1+ b))
)

И посмотрим на скомпилированный код этой функции:

(disassemble 'foo)
=>
; disassembly for FOO
; 0325A727:       48FFC2           INC RDX                    ; no-arg-parsing entry point
;       2A:       48FFC7           INC RDI
;       2D:       48C1E203         SHL RDX, 3
;       31:       48C1E703         SHL RDI, 3
;       35:       488BD2           MOV RDX, RDX               ; <--
;       38:       4831FA           XOR RDX, RDI               ; <-- код VOP'а my-xor
;       3B:       488BE5           MOV RSP, RBP
;       3E:       F8               CLC
;       3F:       5D               POP RBP
;       40:       C3               RET

Из дизассемблированного кода видно, что был подставлен именно тот код, который мы хотели.

Ссылка на полученный код: http://lisper.ru/apps/format/138.

Код получается многословным, в первую очередь, из-за того, что тут используется полная функциональность компилятора, а не просто вставка ассемблерного кода.

@2009-2013 lisper.ru