[Sbcl-help] Code generation questions

[Rupert S. <rsw...@gm...>]

Fresh in a new job where I'm writing a lot of assembly (for a strange
VLIW architecture), I decided to have a look at some of the code SBCL
was generating for a numerical GCD algorithm I was writing. The lisp
code is as follows:

  ;; CRECIP-FIXNUM
  ;;
  ;; The CRECIP algorithm that you'll find in CRECIP-GENERAL, but set up so that
  ;; it uses fixnum arithmetic. Note: There's no particular reason to target 32
  ;; bits except that trying to work out the right types on the fly looks
  ;; complicated and this lisp compiler, at least, uses 32 bit words. Since we
  ;; have to take a product, we constrain the types to 16 bit numbers.
  (defun crecip (n)
    ;; Punt on anything complicated
    (unless (and modulus (typep modulus '(unsigned-byte 15)))
      (return-from crecip (crecip-general n)))

    ;; And make sure that -MODULUS < N < MODULUS
    (unless (<= (- modulus) n modulus)
      (merror "N is out of range [-MODULUS, MODULUS] in crecip."))

    ;; N in [0, MODULUS]
    (when (minusp n) (setf n (+ n modulus)))

    ;; We have to rename modulus -> mod here to avoid binding the special variable
    ;; and breaking the cmod call below.
    (let ((mod modulus) (remainder n) (a 1) (b 0))
      ;; On SBCL in 2013 at least, the compiler doesn't spot that MOD and
      ;; REMAINDER are unsigned and bounded above by MODULUS, a 16-bit integer. So
      ;; we have to tell it. Also, the lisp implementation can't really be
      ;; expected to know that Bezout coefficients are bounded by the modulus and
      ;; remainder, so we have to tell it that too.
      (declare (type (unsigned-byte 15) mod)
               (type (unsigned-byte 15) remainder)
               (type (signed-byte 16) a b))

      (loop
         until (= remainder 1)

         when (zerop remainder) do
           (merror (intl:gettext "CRECIP: attempted inverse of zero (mod ~M)")
                   mod)
         doing
           (multiple-value-bind (quot rem)
               (truncate mod remainder)
             (setf mod remainder
                   remainder rem)
             (psetf a (- b (* a quot))
                    b a))

         finally
         ;; Is there any reason why this can't be (RETURN (CMOD Y2)) ? -cwh
           (return  (cmod a)))))

I have two questions. The first is about code generation. When I
disassemble the resulting code, it starts with the following:

  ; disassembly for CRECIP
  ; Size: 964 bytes
  ; 0E55607E:       8B0D1860550E     MOV ECX, [#xE556018]       ; 'MODULUS
                                                                ; no-arg-parsing entry point
  ;      084:       8B4111           MOV EAX, [ECX+17]
  ;      087:       648B00           MOV EAX, FS:[EAX]
  ;      08A:       83F85A           CMP EAX, 90
  ;      08D:       7503             JNE L0
  ;      08F:       8B41FD           MOV EAX, [ECX-3]
  ;      092: L0:   83F84A           CMP EAX, 74
  ;      095:       0F847C030000     JEQ L38
  ;      09B:       3D0B001001       CMP EAX, 17825803
  ;      0A0:       0F8458030000     JEQ L37
  ;      0A6:       8B0D1860550E     MOV ECX, [#xE556018]       ; 'MODULUS
  ;      0AC:       8B4111           MOV EAX, [ECX+17]
  ;      0AF:       648B00           MOV EAX, FS:[EAX]
  ;      0B2:       83F85A           CMP EAX, 90
  ;      0B5:       7503             JNE L1
  ;      0B7:       8B41FD           MOV EAX, [ECX-3]
  ;      0BA: L1:   83F84A           CMP EAX, 74
  ;      0BD:       0F8459030000     JEQ L39
  ;      0C3:       A90300FEFF       TEST EAX, 4294836227
  ;      0C8:       0F8530030000     JNE L37
  ;      0CE:       8B051860550E     MOV EAX, [#xE556018]       ; 'MODULUS
  ;      0D4:       8B5011           MOV EDX, [EAX+17]
  ;      0D7:       648B12           MOV EDX, FS:[EDX]
  ;      0DA:       83FA5A           CMP EDX, 90
  ;      0DD:       7503             JNE L2
  ;      0DF:       8B50FD           MOV EDX, [EAX-3]
  ;      0E2: L2:   83FA4A           CMP EDX, 74
  ;      0E5:       0F8436030000     JEQ L40

I'm a bit confused about why we seem to be doing the dance to load up
the special variable MODULUS twice. No following code jumps to L1 and,
unless I'm being truly dopey, there's no way that MODULUS can be unbound
the second time. Indeed, I think that it's still stored in EAX at 0CE,
so the reload is really crazy! Is my "analysis" right? And, if so, has
anyone written up more about SBCL's code generation stages so I can
delve further? I'm interested, but don't know much about the internals
of lisp compilers and where I should be looking.

The second question is alluded to in a comment in the code above. Why
doesn't type inference spot that MOD and REMAINDER are UNSIGNED-BYTE
16's? Is it that I'm adding and subtracting with them later on and the
compiler can't know that we don't overflow? Is there a neat way of
getting SBCL to tell me what it's managed to derive about a variable's
type?

If it's relevant, I'm using version 1.1.11 on Debian.

Many thanks for the help - I hope the questions aren't too stupid!

Rupert