Writing a VOP that is equivalent to mul/imul

Question

So, both mul and imul instructions multiply machine words and store both the result and overflow in some registers (see this for example https://c9x.me/x86/html/file_module_x86_id_210.html). I'm trying to write a vop that would use this information fully and return 2 values. Is this possible? I can't find any info on how to make vop return multiple values. If someone can just show the example of how the whole thing would look like, I would appreciate it as well.

EDIT: So I figured out something, but it's still not good enough. I'll post it here and then explain the problem.

(defpackage #:fixmul
  (:use #:CL)
  (:export #:fixmul))

(in-package #:fixmul)


(sb-c:defknown fixmul (fixnum fixnum) (values fixnum fixnum &optional)
    (sb-c:foldable sb-c:flushable sb-c:movable)
  :overwrite-fndb-silently t)

(in-package #:sb-vm)

(define-vop (fixmul:fixmul)
  (:policy :fast-safe)
  (:translate fixmul:fixmul)
  (:args (x :scs (signed-reg) :target eax)
         (y :scs (signed-reg signed-stack)))
  (:arg-types fixnum fixnum)
  (:args-var args)
  (:temporary (:sc signed-reg :offset eax-offset :target quo
               :from (:argument 0) :to (:result 0)) eax)
  (:temporary (:sc signed-reg :offset edx-offset :target rem
               :from (:argument 0) :to (:result 1)) edx)
  (:results (quo :scs (signed-reg))
            (rem :scs (signed-reg)))
  (:result-types fixnum fixnum)
  (:note "inline (unsigned-byte 64) arithmetic")
  (:vop-var vop)
  (:save-p :compute-only)
  (:generator 5
              (move eax x)
              (inst mul eax y)
              (move quo eax)
              (move rem edx)))

(in-package #:fixmul)

(defun fixmul (a b)
  (fixmul a b))

So, this disassembles to:

> (disassemble 'fixmul)
; disassembly for FIXMUL
; Size: 35 bytes. Origin: #x52C42F4F                          ; FIXMUL
; 4F:       48F7E7           MUL RAX, RDI
; 52:       488BFA           MOV RDI, RDX
; 55:       48D1E0           SHL RAX, 1
; 58:       48D1E7           SHL RDI, 1
; 5B:       488BD0           MOV RDX, RAX
; 5E:       488D5D10         LEA RBX, [RBP+16]
; 62:       B904000000       MOV ECX, 4
; 67:       BE17001050       MOV ESI, #x50100017              ; NIL
; 6C:       F9               STC
; 6D:       488BE5           MOV RSP, RBP
; 70:       5D               POP RBP
; 71:       C3               RET
NIL

This isn't bad, but I don't understand most of what I'm doing on sbcl side, in particular -- why am I getting this LEA RBX, [RBP+16] and MOV ESI, #x50100017
instructions ?

EDIT2: It seems those instructions are mostly about returning 2 values. However, the whole thing is problematic in a sense that it uses CL native fixnums etc, instead of just raw machine words. I'm not sure how to resolve this problem, which is why I don't put a self answer.

Silurid

The high half isn't "overflow", it's just the high half of the full result of N x N => 2N-bit multiplication. The fact that some languages don't give you easy access to full multiplication doesn't change what you should call it in asm terms. (I don't know the answer to your question, I don't know anything about SBCL, sorry). – Kamerman

Right okay. I didn't know the correct terminology, but I think that my mental picture of it is correct. – Silurid

Answer 1

Try:

(defpackage #:fixmul
  (:use #:CL)
  (:export #:fixmul))

(in-package #:fixmul)

(sb-c:defknown fixmul ((signed-byte 64) (signed-byte 64)) 
               (values (signed-byte 64) (signed-byte 64) &optional)
               (sb-c:foldable sb-c:flushable sb-c:movable))

(in-package #:sb-vm)

(define-vop (fixmul:fixmul)
  (:policy :fast-safe)
  (:translate fixmul:fixmul)
  (:args (x :scs (signed-reg) :target eax)
         (y :scs (signed-reg signed-stack)))
  (:arg-types signed-num signed-num)
  ; (:args-var args)
  (:temporary (:sc signed-reg :offset eax-offset :target quo
               :from (:argument 0) :to (:result 0)) eax)
  (:temporary (:sc signed-reg :offset edx-offset :target rem
               :from (:argument 0) :to (:result 1)) edx)
  (:results (quo :scs (signed-reg))
            (rem :scs (signed-reg)))
  (:result-types signed-num signed-num)
  (:note "inline (unsigned-byte 64) arithmetic")
  (:vop-var vop)
  (:save-p :compute-only)
  (:generator 5
              (move eax x)
              (inst mul eax y)
              (move quo eax)
              (move rem edx)))

(in-package #:fixmul)

(defun fixmul (a b)
  (fixmul a b))

Now: (disassemble 'fixmul)

Shows:

; disassembly for FIXMUL
; 02E2D561:       498BC0           MOV RAX, R8                ; no-arg-parsing entry point
;       64:       49F7E1           MUL RAX, R9
;       67:       488BCA           MOV RCX, RDX
;       6A:       486BD002         IMUL RDX, RAX, 2
;       6E:       710E             JNO L0
;       70:       488BD0           MOV RDX, RAX
;       73:       4C8D1C2540060020 LEA R11, [#x20000640]      ; ALLOC-SIGNED-BIGNUM-IN-RDX
;       7B:       41FFD3           CALL R11
;       7E: L0:   486BF902         IMUL RDI, RCX, 2
;       82:       710E             JNO L1
;       84:       488BF9           MOV RDI, RCX
;       87:       4C8D1C2518070020 LEA R11, [#x20000718]      ; ALLOC-SIGNED-BIGNUM-IN-RDI
;       8F:       41FFD3           CALL R11
;       92: L1:   488D5D10         LEA RBX, [RBP+16]
;       96:       B904000000       MOV ECX, 4
;       9B:       BE17001020       MOV ESI, 537919511
;       A0:       F9               STC
;       A1:       488BE5           MOV RSP, RBP
;       A4:       5D               POP RBP
;       A5:       C3               RET
;       A6:       0F0B0A           BREAK 10                   ; error trap
;       A9:       02               BYTE #X02
;       AA:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;       AB:       54               BYTE #X54                  ; RCX
NIL

As you can see from

; 73: 4C8D1C2540060020 LEA R11, [#x20000640] ; ALLOC-SIGNED-BIGNUM-IN-RDX

and

; 87: 4C8D1C2518070020 LEA R11, [#x20000718] ; ALLOC-SIGNED-BIGNUM-IN-RDI

that a bignum which is (and integer (not fixnum)) is allocated. Since I have a 64 bit system, a bignum fits in one machine word. The diassembly will be different on a 32 bit system. In that case you can specify (signed-byte 32) in sb-c:defknown fixmul.

Your result type and arg types can be different too (This way, if you know your input values are going to be small, then you can still get results for values near the max of (signed-byte 32).):

(sb-c:defknown fixmul ((signed-byte 32) (signed-byte 32)) 
               (values (signed-byte 64) (signed-byte 64) &optional)
               (sb-c:foldable sb-c:flushable sb-c:movable))

Some tests:

(fixmul 10000000000000000 100000000000000000)

> 4089650035136921600
  54210108624275


(fixmul 20 -200000)

> -4000000
  19

Note: I had to comment out (:args-var args) and do away with :overwrite-fndb-silently t for my code to work correctly. This is likely due to version difference with my sbcl from yours.

Copulative