X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fgeneric%2Fvm-tran.lisp;h=7866594e0405dc96ed38c501903e0606a083b56b;hb=ca267caa3bdb897a93a1e69ae7300ba3ba5d391f;hp=bc21fbed3405c00315bfdb7fbc1f5ad287b7f4e0;hpb=f6f238261f95e8ffff2870ed3ac6fc00ddf09ef2;p=sbcl.git diff --git a/src/compiler/generic/vm-tran.lisp b/src/compiler/generic/vm-tran.lisp index bc21fbe..7866594 100644 --- a/src/compiler/generic/vm-tran.lisp +++ b/src/compiler/generic/vm-tran.lisp @@ -36,21 +36,24 @@ ;;;; character support ;;; In our implementation there are really only BASE-CHARs. +#+nil (define-source-transform characterp (obj) `(base-char-p ,obj)) ;;;; simplifying HAIRY-DATA-VECTOR-REF and HAIRY-DATA-VECTOR-SET (deftransform hairy-data-vector-ref ((string index) (simple-string t)) - (let ((ctype (continuation-type string))) + (let ((ctype (lvar-type string))) (if (array-type-p ctype) ;; the other transform will kick in, so that's OK (give-up-ir1-transform) `(etypecase string ((simple-array character (*)) (data-vector-ref string index)) + #!+sb-unicode + ((simple-array base-char (*)) (data-vector-ref string index)) ((simple-array nil (*)) (data-vector-ref string index)))))) -(deftransform hairy-data-vector-ref ((array index) (array t) * :important t) +(deftransform hairy-data-vector-ref ((array index) (array t) *) "avoid runtime dispatch on array element type" (let ((element-ctype (extract-upgraded-element-type array)) (declared-element-ctype (extract-declared-element-type array))) @@ -74,7 +77,7 @@ (deftransform data-vector-ref ((array index) (simple-array t)) - (let ((array-type (continuation-type array))) + (let ((array-type (lvar-type array))) (unless (array-type-p array-type) (give-up-ir1-transform)) (let ((dims (array-type-dimensions array-type))) @@ -91,20 +94,22 @@ (deftransform hairy-data-vector-set ((string index new-value) (simple-string t t)) - (let ((ctype (continuation-type string))) + (let ((ctype (lvar-type string))) (if (array-type-p ctype) ;; the other transform will kick in, so that's OK (give-up-ir1-transform) `(etypecase string ((simple-array character (*)) (data-vector-set string index new-value)) + #!+sb-unicode + ((simple-array base-char (*)) + (data-vector-set string index new-value)) ((simple-array nil (*)) (data-vector-set string index new-value)))))) (deftransform hairy-data-vector-set ((array index new-value) (array t t) - * - :important t) + *) "avoid runtime dispatch on array element type" (let ((element-ctype (extract-upgraded-element-type array)) (declared-element-ctype (extract-declared-element-type array))) @@ -126,7 +131,7 @@ (deftransform data-vector-set ((array index new-value) (simple-array t t)) - (let ((array-type (continuation-type array))) + (let ((array-type (lvar-type array))) (unless (array-type-p array-type) (give-up-ir1-transform)) (let ((dims (array-type-dimensions array-type))) @@ -143,7 +148,7 @@ new-value))))) (defoptimizer (%data-vector-and-index derive-type) ((array index)) - (let ((atype (continuation-type array))) + (let ((atype (lvar-type array))) (when (array-type-p atype) (values-specifier-type `(values (simple-array ,(type-specifier @@ -153,8 +158,7 @@ (deftransform %data-vector-and-index ((%array %index) (simple-array t) - * - :important 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 @@ -230,7 +234,7 @@ (length bit-array-2) (length result-bit-array)) (error "Argument and/or result bit arrays are not the same length:~ - ~% ~S~% ~S ~% ~S" + ~% ~S~% ~S ~% ~S" bit-array-1 bit-array-2 result-bit-array)))) @@ -260,16 +264,16 @@ (setf (%raw-bits result-bit-array index) (,',wordfun (%raw-bits bit-array-1 index) (%raw-bits bit-array-2 index)))))))))) - (def bit-and 32bit-logical-and) - (def bit-ior 32bit-logical-or) - (def bit-xor 32bit-logical-xor) - (def bit-eqv 32bit-logical-eqv) - (def bit-nand 32bit-logical-nand) - (def bit-nor 32bit-logical-nor) - (def bit-andc1 32bit-logical-andc1) - (def bit-andc2 32bit-logical-andc2) - (def bit-orc1 32bit-logical-orc1) - (def bit-orc2 32bit-logical-orc2)) + (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) @@ -280,30 +284,30 @@ '((unless (= (length bit-array) (length result-bit-array)) (error "Argument and result bit arrays are not the same length:~ - ~% ~S~% ~S" + ~% ~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-32 cases are handled by the (1- length), - ;; below. CSR, 2002-04-24 + ;; 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-32 need precisely - ;; one (SETF %RAW-BITS), done here in the - ;; epilogue. - CSR, 2002-04-24 + ;; 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) - (32bit-logical-not (%raw-bits 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) - (32bit-logical-not (%raw-bits 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)) @@ -313,7 +317,7 @@ (end-1 (+ sb!vm:vector-data-offset (floor (1- length) sb!vm:n-word-bits)))) ((= i end-1) - (let* ((extra (mod length sb!vm:n-word-bits)) + (let* ((extra (1+ (mod (1- length) sb!vm:n-word-bits))) (mask (1- (ash 1 extra))) (numx (logand @@ -331,15 +335,107 @@ (:big-endian '(- sb!vm:n-word-bits extra)))) (%raw-bits y i)))) - (declare (type (integer 0 31) extra) - (type (unsigned-byte 32) mask numx numy)) + (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 (unsigned-byte 32) numx numy)) + (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 (1- (ash 1 extra))) + (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)) + ;; could consider LOGNOT for the zero case instead of + ;; doing the subtraction... + (incf count ,(if (constant-lvar-p item) + (if (zerop (lvar-value item)) + '(- extra (logcount bits)) + '(logcount bits)) + '(if (zerop item) + (- extra (logcount bits)) + (logcount bits)))))) + (declare (type index index count end-1) + (optimize (speed 3) (safety 0))) + (incf count ,(if (constant-lvar-p item) + (if (zerop (lvar-value item)) + '(- sb!vm:n-word-bits (logcount (%raw-bits sequence index))) + '(logcount (%raw-bits sequence index))) + '(if (zerop item) + (- sb!vm:n-word-bits (logcount (%raw-bits sequence index))) + (logcount (%raw-bits sequence index))))))))) + +(deftransform fill ((sequence item) (simple-bit-vector bit) * + :policy (>= speed space)) + (let ((value (if (constant-lvar-p item) + (if (= (lvar-value item) 0) + 0 + #.(1- (ash 1 sb!vm:n-word-bits))) + `(if (= item 0) 0 #.(1- (ash 1 sb!vm:n-word-bits)))))) + `(let ((length (length sequence)) + (value ,value)) + (if (= length 0) + sequence + (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 sequence index) value) + sequence) + (declare (optimize (speed 3) (safety 0)) + (type index index end-1)) + (setf (%raw-bits sequence index) value)))))) + +(deftransform fill ((sequence item) (simple-base-string base-char) * + :policy (>= speed space)) + (let ((value (if (constant-lvar-p item) + (let* ((char (lvar-value item)) + (code (sb!xc:char-code char)) + (accum 0)) + (dotimes (i sb!vm:n-word-bytes accum) + (setf accum (logior accum (ash code (* 8 i)))))) + `(let ((code (sb!xc:char-code item))) + (logior ,@(loop for i from 0 below sb!vm:n-word-bytes + collect `(ash code ,(* 8 i)))))))) + `(let ((length (length sequence)) + (value ,value)) + (multiple-value-bind (times rem) + (truncate length sb!vm:n-word-bytes) + (do ((index sb!vm:vector-data-offset (1+ index)) + (end (+ times sb!vm:vector-data-offset))) + ((= index end) + (let ((place (* times sb!vm:n-word-bytes))) + (declare (fixnum place)) + (dotimes (j rem sequence) + (declare (index j)) + (setf (schar sequence (the index (+ place j))) item)))) + (declare (optimize (speed 3) (safety 0)) + (type index index)) + (setf (%raw-bits sequence index) value)))))) ;;;; %BYTE-BLT @@ -390,25 +486,126 @@ (= (double-float-high-bits x) (double-float-high-bits y)))) -;;;; 32-bit operations -#!-x86 ; on X86 it is a modular function -(deftransform lognot ((x) ((unsigned-byte 32)) * - :node node - :result result) - "32-bit implementation" - (let ((dest (continuation-dest result))) - (unless (and (combination-p dest) - (eq (continuation-fun-name (combination-fun dest)) - 'logand)) - (give-up-ir1-transform)) - (unless (some (lambda (arg) - (csubtypep (continuation-type arg) - (specifier-type '(unsigned-byte 32)))) - (combination-args dest)) - (give-up-ir1-transform)) - (setf (node-derived-type node) - (values-specifier-type '(values (unsigned-byte 32) &optional))) - '(32bit-logical-not x))) +;;;; modular functions +(define-good-modular-fun logand :unsigned) +(define-good-modular-fun logior :unsigned) +;;; FIXME: XOR? ANDC1, ANDC2? -- CSR, 2003-09-16 + +(macrolet + ((def (name class width) + (let ((type (ecase class + (:unsigned 'unsigned-byte) + (:signed 'signed-byte)))) + `(progn + (defknown ,name (integer (integer 0)) (,type ,width) + (foldable flushable movable)) + (define-modular-fun-optimizer ash ((integer count) ,class :width width) + (when (and (<= width ,width) + (or (and (constant-lvar-p count) + (plusp (lvar-value count))) + (csubtypep (lvar-type count) + (specifier-type '(and unsigned-byte fixnum))))) + (cut-to-width integer ,class width) + ',name)) + (setf (gethash ',name (modular-class-versions (find-modular-class ',class))) + `(ash ,',width)))))) + ;; This should really be dependent on SB!VM:N-WORD-BITS, but since we + ;; don't have a true Alpha64 port yet, we'll have to stick to + ;; SB!VM:N-MACHINE-WORD-BITS for the time being. --njf, 2004-08-14 + #!+#.(cl:if (cl:= 32 sb!vm:n-machine-word-bits) '(and) '(or)) + (progn + #!+x86 (def sb!vm::ash-left-smod30 :signed 30) + (def sb!vm::ash-left-mod32 :unsigned 32)) + #!+#.(cl:if (cl:= 64 sb!vm:n-machine-word-bits) '(and) '(or)) + (progn + #!+x86-64 (def sb!vm::ash-left-smod61 :signed 61) + (def sb!vm::ash-left-mod64 :unsigned 64))) + + +;;;; word-wise logical operations -(define-good-modular-fun logand) -(define-good-modular-fun logior) +;;; These transforms assume the presence of modular arithmetic to +;;; generate efficient code. + +(define-source-transform word-logical-not (x) + `(logand (lognot (the sb!vm:word ,x)) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-and ((x y)) + '(logand x y)) + +(deftransform word-logical-nand ((x y)) + '(logand (lognand x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-or ((x y)) + '(logior x y)) + +(deftransform word-logical-nor ((x y)) + '(logand (lognor x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-xor ((x y)) + '(logxor x y)) + +(deftransform word-logical-eqv ((x y)) + '(logand (logeqv x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-orc1 ((x y)) + '(logand (logorc1 x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-orc2 ((x y)) + '(logand (logorc2 x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-andc1 ((x y)) + '(logand (logandc1 x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + +(deftransform word-logical-andc2 ((x y)) + '(logand (logandc2 x y) #.(1- (ash 1 sb!vm:n-word-bits)))) + + +;;; There are two different ways the multiplier can be recoded. The +;;; more obvious is to shift X by the correct amount for each bit set +;;; in Y and to sum the results. But if there is a string of bits that +;;; are all set, you can add X shifted by one more then the bit +;;; position of the first set bit and subtract X shifted by the bit +;;; position of the last set bit. We can't use this second method when +;;; the high order bit is bit 31 because shifting by 32 doesn't work +;;; too well. +(defun ub32-strength-reduce-constant-multiply (arg num) + (declare (type (unsigned-byte 32) num)) + (let ((adds 0) (shifts 0) + (result nil) first-one) + (labels ((add (next-factor) + (setf result + (if result + (progn (incf adds) `(+ ,result ,next-factor)) + next-factor)))) + (declare (inline add)) + (dotimes (bitpos 32) + (if first-one + (when (not (logbitp bitpos num)) + (add (if (= (1+ first-one) bitpos) + ;; There is only a single bit in the string. + (progn (incf shifts) `(ash ,arg ,first-one)) + ;; There are at least two. + (progn + (incf adds) + (incf shifts 2) + `(- (ash ,arg ,bitpos) + (ash ,arg ,first-one))))) + (setf first-one nil)) + (when (logbitp bitpos num) + (setf first-one bitpos)))) + (when first-one + (cond ((= first-one 31)) + ((= first-one 30) (incf shifts) (add `(ash ,arg 30))) + (t + (incf shifts 2) + (incf adds) + (add `(- (ash ,arg 31) + (ash ,arg ,first-one))))) + (incf shifts) + (add `(ash ,arg 31)))) + (values (if (plusp adds) + `(logand ,result #.(1- (ash 1 32))) ; using modular arithmetic + result) + adds + shifts)))