vm-tran.lisp

开源跨平台Lisp编译器

;;; Transform data vector access to a form that opens up optimization
;;; opportunities.
#!+(or x86 x86-64)
(define-source-transform data-vector-set (array index new-value)
  `(data-vector-set-with-offset ,array ,index 0 ,new-value))

#!+(or x86 x86-64)
(deftransform data-vector-set-with-offset ((array index offset new-value))
  (let ((array-type (lvar-type array)))
    (when (or (not (array-type-p array-type))
              (eql (array-type-specialized-element-type array-type)
                   *wild-type*))
      ;; We don't yet know the exact element type, but will get that
      ;; knowledge after some more type propagation.
      (give-up-ir1-transform))
    (aver (not (array-type-complexp array-type)))
    (let* ((element-type (type-specifier (array-type-specialized-element-type array-type)))
           (saetp (find-saetp element-type)))
      (when (< (sb!vm:saetp-n-bits saetp) sb!vm:n-byte-bits)
        (give-up-ir1-transform))
      (fold-index-addressing 'data-vector-set-with-offset
                             (sb!vm:saetp-n-bits saetp)
                             sb!vm:other-pointer-lowtag
                             sb!vm:vector-data-offset
                             index offset t))))

(defoptimizer (%data-vector-and-index derive-type) ((array index))
  (let ((atype (lvar-type array)))
    (when (array-type-p atype)
      (values-specifier-type
       `(values (simple-array ,(type-specifier
                                (array-type-specialized-element-type atype))
                              (*))
                index)))))

(deftransform %data-vector-and-index ((%array %index)
                                      (simple-array t)
                                      *)
  ;; KLUDGE: why the percent signs?  Well, ARRAY and INDEX are
  ;; respectively exported from the CL and SB!INT packages, which
  ;; means that they're visible to all sorts of things.  If the
  ;; compiler can prove that the call to ARRAY-HEADER-P, below, either
  ;; returns T or NIL, it will delete the irrelevant branch.  However,
  ;; user code might have got here with a variable named CL:ARRAY, and
  ;; quite often compiler code with a variable named SB!INT:INDEX, so
  ;; this can generate code deletion notes for innocuous user code:
  ;; (DEFUN F (ARRAY I) (DECLARE (SIMPLE-VECTOR ARRAY)) (AREF ARRAY I))
  ;; -- CSR, 2003-04-01

  ;; We do this solely for the -OR-GIVE-UP side effect, since we want
  ;; to know that the type can be figured out in the end before we
  ;; proceed, but we don't care yet what the type will turn out to be.
  (upgraded-element-type-specifier-or-give-up %array)

  '(if (array-header-p %array)
       (values (%array-data-vector %array) %index)
       (values %array %index)))

;;; transforms for getting at simple arrays of (UNSIGNED-BYTE N) when (< N 8)
;;;
;;; FIXME: In CMU CL, these were commented out with #+NIL. Why? Should
;;; we fix them or should we delete them? (Perhaps these definitions
;;; predate the various DATA-VECTOR-REF-FOO VOPs which have
;;; (:TRANSLATE DATA-VECTOR-REF), and are redundant now?)
#+nil
(macrolet
    ((frob (type bits)
       (let ((elements-per-word (truncate sb!vm:n-word-bits bits)))
         `(progn
            (deftransform data-vector-ref ((vector index)
                                           (,type *))
              `(multiple-value-bind (word bit)
                   (floor index ,',elements-per-word)
                 (ldb ,(ecase sb!vm:target-byte-order
                         (:little-endian '(byte ,bits (* bit ,bits)))
                         (:big-endian '(byte ,bits (- sb!vm:n-word-bits
                                                      (* (1+ bit) ,bits)))))
                      (%raw-bits vector (+ word sb!vm:vector-data-offset)))))
            (deftransform data-vector-set ((vector index new-value)
                                           (,type * *))
              `(multiple-value-bind (word bit)
                   (floor index ,',elements-per-word)
                 (setf (ldb ,(ecase sb!vm:target-byte-order
                               (:little-endian '(byte ,bits (* bit ,bits)))
                               (:big-endian
                                '(byte ,bits (- sb!vm:n-word-bits
                                                (* (1+ bit) ,bits)))))
                            (%raw-bits vector (+ word sb!vm:vector-data-offset)))
                       new-value)))))))
  (frob simple-bit-vector 1)
  (frob (simple-array (unsigned-byte 2) (*)) 2)
  (frob (simple-array (unsigned-byte 4) (*)) 4))

;;;; BIT-VECTOR hackery

;;; SIMPLE-BIT-VECTOR bit-array operations are transformed to a word
;;; loop that does 32 bits at a time.
;;;
;;; FIXME: This is a lot of repeatedly macroexpanded code. It should
;;; be a function call instead.
(macrolet ((def (bitfun wordfun)
             `(deftransform ,bitfun ((bit-array-1 bit-array-2 result-bit-array)
                                     (simple-bit-vector
                                      simple-bit-vector
                                      simple-bit-vector)
                                     *
                                     :node node :policy (>= speed space))
                `(progn
                   ,@(unless (policy node (zerop safety))
                             '((unless (= (length bit-array-1)
                                          (length bit-array-2)
                                          (length result-bit-array))
                                 (error "Argument and/or result bit arrays are not the same length:~
                         ~%  ~S~%  ~S  ~%  ~S"
                                        bit-array-1
                                        bit-array-2
                                        result-bit-array))))
                  (let ((length (length result-bit-array)))
                    (if (= length 0)
                        ;; We avoid doing anything to 0-length
                        ;; bit-vectors, or rather, the memory that
                        ;; follows them. Other divisible-by-32 cases
                        ;; are handled by the (1- length), below.
                        ;; CSR, 2002-04-24
                        result-bit-array
                        (do ((index sb!vm:vector-data-offset (1+ index))
                             (end-1 (+ sb!vm:vector-data-offset
                                       ;; bit-vectors of length 1-32
                                       ;; need precisely one (SETF
                                       ;; %RAW-BITS), done here in the
                                       ;; epilogue. - CSR, 2002-04-24
                                       (truncate (truly-the index (1- length))
                                                 sb!vm:n-word-bits))))
                            ((>= index end-1)
                             (setf (%raw-bits result-bit-array index)
                                   (,',wordfun (%raw-bits bit-array-1 index)
                                               (%raw-bits bit-array-2 index)))
                             result-bit-array)
                          (declare (optimize (speed 3) (safety 0))
                                   (type index index end-1))
                          (setf (%raw-bits result-bit-array index)
                                (,',wordfun (%raw-bits bit-array-1 index)
                                            (%raw-bits bit-array-2 index))))))))))
 (def bit-and word-logical-and)
 (def bit-ior word-logical-or)
 (def bit-xor word-logical-xor)
 (def bit-eqv word-logical-eqv)
 (def bit-nand word-logical-nand)
 (def bit-nor word-logical-nor)
 (def bit-andc1 word-logical-andc1)
 (def bit-andc2 word-logical-andc2)
 (def bit-orc1 word-logical-orc1)
 (def bit-orc2 word-logical-orc2))

(deftransform bit-not
              ((bit-array result-bit-array)
               (simple-bit-vector simple-bit-vector) *
               :node node :policy (>= speed space))
  `(progn
     ,@(unless (policy node (zerop safety))
         '((unless (= (length bit-array)
                      (length result-bit-array))
             (error "Argument and result bit arrays are not the same length:~
                     ~%  ~S~%  ~S"
                    bit-array result-bit-array))))
    (let ((length (length result-bit-array)))
      (if (= length 0)
          ;; We avoid doing anything to 0-length bit-vectors, or rather,
          ;; the memory that follows them. Other divisible-by
          ;; n-word-bits cases are handled by the (1- length), below.
          ;; CSR, 2002-04-24
          result-bit-array
          (do ((index sb!vm:vector-data-offset (1+ index))
               (end-1 (+ sb!vm:vector-data-offset
                         ;; bit-vectors of length 1 to n-word-bits need
                         ;; precisely one (SETF %RAW-BITS), done here in
                         ;; the epilogue. - CSR, 2002-04-24
                         (truncate (truly-the index (1- length))
                                   sb!vm:n-word-bits))))
              ((>= index end-1)
               (setf (%raw-bits result-bit-array index)
                     (word-logical-not (%raw-bits bit-array index)))
               result-bit-array)
            (declare (optimize (speed 3) (safety 0))
                     (type index index end-1))
            (setf (%raw-bits result-bit-array index)
                  (word-logical-not (%raw-bits bit-array index))))))))

(deftransform bit-vector-= ((x y) (simple-bit-vector simple-bit-vector))
  `(and (= (length x) (length y))
        (let ((length (length x)))
          (or (= length 0)
              (do* ((i sb!vm:vector-data-offset (+ i 1))
                    (end-1 (+ sb!vm:vector-data-offset
                              (floor (1- length) sb!vm:n-word-bits))))
                   ((>= i end-1)
                    (let* ((extra (1+ (mod (1- length) sb!vm:n-word-bits)))
                           (mask (ash #.(1- (ash 1 sb!vm:n-word-bits))
                                      (- extra sb!vm:n-word-bits)))
                           (numx
                            (logand
                             (ash mask
                                  ,(ecase sb!c:*backend-byte-order*
                                     (:little-endian 0)
                                     (:big-endian
                                      '(- sb!vm:n-word-bits extra))))
                             (%raw-bits x i)))
                           (numy
                            (logand
                             (ash mask
                                  ,(ecase sb!c:*backend-byte-order*
                                     (:little-endian 0)
                                     (:big-endian
                                      '(- sb!vm:n-word-bits extra))))
                             (%raw-bits y i))))
                      (declare (type (integer 1 #.sb!vm:n-word-bits) extra)
                               (type sb!vm:word mask numx numy))
                      (= numx numy)))
                (declare (type index i end-1))
                (let ((numx (%raw-bits x i))
                      (numy (%raw-bits y i)))
                  (declare (type sb!vm:word numx numy))
                  (unless (= numx numy)
                    (return nil))))))))

(deftransform count ((item sequence) (bit simple-bit-vector) *
                     :policy (>= speed space))
  `(let ((length (length sequence)))
    (if (zerop length)
        0
        (do ((index sb!vm:vector-data-offset (1+ index))
             (count 0)
             (end-1 (+ sb!vm:vector-data-offset
                       (truncate (truly-the index (1- length))
                                 sb!vm:n-word-bits))))
            ((>= index end-1)
             (let* ((extra (1+ (mod (1- length) sb!vm:n-word-bits)))
                    (mask (ash #.(1- (ash 1 sb!vm:n-word-bits))
                               (- extra sb!vm:n-word-bits)))
                    (bits (logand (ash mask
                                       ,(ecase sb!c:*backend-byte-order*
                                               (:little-endian 0)
                                               (:big-endian
                                                '(- sb!vm:n-word-bits extra))))
                                  (%raw-bits sequence index))))
               (declare (type (integer 1 #.sb!vm:n-word-bits) extra))
               (declare (type sb!vm:word mask bits))
               (incf count (logcount bits))
               ,(if (constant-lvar-p item)
                    (if (zerop (lvar-value item))
                        '(- length count)
                        'count)
                    '(if (zerop item)
                         (- length count)
                         count))))
          (declare (type index index count end-1)
                   (optimize (speed 3) (safety 0)))