X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fgeneric%2Fvm-tran.lisp;h=fa3bee30cc691e921069a21255faa9dea09d2bd5;hb=5dcf5905dc38232b3cc5ec6b309ea5c6424db957;hp=e28bc1328f9305dd2e76638f4fead1d5992c2d59;hpb=86210c4e406c1b2ff10cc3bac0e71435867db48b;p=sbcl.git diff --git a/src/compiler/generic/vm-tran.lisp b/src/compiler/generic/vm-tran.lisp index e28bc13..fa3bee3 100644 --- a/src/compiler/generic/vm-tran.lisp +++ b/src/compiler/generic/vm-tran.lisp @@ -41,9 +41,19 @@ ;;;; simplifying HAIRY-DATA-VECTOR-REF and HAIRY-DATA-VECTOR-SET +(deftransform hairy-data-vector-ref ((string index) (simple-string t)) + (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)) + ((simple-array nil (*)) (data-vector-ref string index)))))) + (deftransform hairy-data-vector-ref ((array index) (array t) * :important t) "avoid runtime dispatch on array element type" - (let ((element-ctype (extract-upgraded-element-type array))) + (let ((element-ctype (extract-upgraded-element-type array)) + (declared-element-ctype (extract-declared-element-type array))) (declare (type ctype element-ctype)) (when (eq *wild-type* element-ctype) (give-up-ir1-transform @@ -54,32 +64,23 @@ ;; to hand-expand it ourselves.) (let ((element-type-specifier (type-specifier element-ctype))) `(multiple-value-bind (array index) - ;; FIXME: All this noise should move into a - ;; %DATA-VECTOR-AND-INDEX function, and there should be - ;; DEFTRANSFORMs for %DATA-VECTOR-AND-INDEX to optimize the - ;; function call away when the array is known to be simple, - ;; and to specialize to - ;; %DATA-VECTOR-AND-INDEX-IN-VECTOR-CASE when the array is - ;; known to have only one dimension. - (if (array-header-p array) - (%with-array-data array index nil) - (let ((array array)) - (declare (type (simple-array ,element-type-specifier 1) - array)) - (%check-bound array 0 index) - (values array index))) + (%data-vector-and-index array index) (declare (type (simple-array ,element-type-specifier 1) array)) - (data-vector-ref array index))))) + ,(let ((bare-form '(data-vector-ref array index))) + (if (type= element-ctype declared-element-ctype) + bare-form + `(the ,(type-specifier declared-element-ctype) + ,bare-form))))))) (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))) (when (or (atom dims) (= (length dims) 1)) (give-up-ir1-transform)) - (let ((el-type (array-type-element-type array-type)) + (let ((el-type (array-type-specialized-element-type array-type)) (total-size (if (member '* dims) '* (reduce #'* dims)))) @@ -88,46 +89,50 @@ (%array-data-vector array)) index))))) +(deftransform hairy-data-vector-set ((string index new-value) + (simple-string t t)) + (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)) + ((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))) + (let ((element-ctype (extract-upgraded-element-type array)) + (declared-element-ctype (extract-declared-element-type array))) (declare (type ctype element-ctype)) (when (eq *wild-type* element-ctype) (give-up-ir1-transform "Upgraded element type of array is not known at compile time.")) (let ((element-type-specifier (type-specifier element-ctype))) `(multiple-value-bind (array index) - ;; FIXME: All this noise should move into a - ;; %DATA-VECTOR-AND-INDEX function, and there should be - ;; DEFTRANSFORMs for %DATA-VECTOR-AND-INDEX to optimize the - ;; function call away when the array is known to be simple, - ;; and to specialize to - ;; %DATA-VECTOR-AND-INDEX-IN-VECTOR-CASE when the array is - ;; known to have only one dimension. - (if (array-header-p array) - (%with-array-data array index nil) - (let ((array array)) - (declare (type (simple-array ,element-type-specifier 1) - array)) - (%check-bound array 0 index) - (values array index))) - (data-vector-set (truly-the (simple-array ,element-type-specifier 1) - array) - index - new-value))))) + (%data-vector-and-index array index) + (declare (type (simple-array ,element-type-specifier 1) array) + (type ,element-type-specifier new-value)) + ,(if (type= element-ctype declared-element-ctype) + '(data-vector-set array index new-value) + `(truly-the ,(type-specifier declared-element-ctype) + (data-vector-set array index + (the ,(type-specifier declared-element-ctype) + new-value)))))))) (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))) (when (or (atom dims) (= (length dims) 1)) (give-up-ir1-transform)) - (let ((el-type (array-type-element-type array-type)) + (let ((el-type (array-type-specialized-element-type array-type)) (total-size (if (member '* dims) '* (reduce #'* dims)))) @@ -137,6 +142,39 @@ index new-value))))) +(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) + * + :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 + ;; 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 @@ -196,18 +234,32 @@ bit-array-1 bit-array-2 result-bit-array)))) - (do ((index sb!vm:vector-data-offset (1+ index)) - (end (+ sb!vm:vector-data-offset - (truncate (the index - (+ (length bit-array-1) - sb!vm:n-word-bits -1)) - sb!vm:n-word-bits)))) - ((= index end) result-bit-array) - (declare (optimize (speed 3) (safety 0)) - (type index index end)) - (setf (%raw-bits result-bit-array index) - (,',wordfun (%raw-bits bit-array-1 index) - (%raw-bits bit-array-2 index)))))))) + (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 32bit-logical-and) (def bit-ior 32bit-logical-or) (def bit-xor 32bit-logical-xor) @@ -230,17 +282,113 @@ (error "Argument and result bit arrays are not the same length:~ ~% ~S~% ~S" bit-array result-bit-array)))) - (do ((index sb!vm:vector-data-offset (1+ index)) - (end (+ sb!vm:vector-data-offset - (truncate (the index - (+ (length bit-array) - (1- sb!vm:n-word-bits))) - sb!vm:n-word-bits)))) - ((= index end) result-bit-array) - (declare (optimize (speed 3) (safety 0)) - (type index index end)) - (setf (%raw-bits result-bit-array index) - (32bit-logical-not (%raw-bits bit-array index)))))) + (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) + (32bit-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)))))))) + +(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 (mod length sb!vm:n-word-bits)) + (mask (1- (ash 1 extra))) + (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 0 31) extra) + (type (unsigned-byte 32) 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)) + (unless (= numx numy) + (return nil)))))))) + +(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 32))) + `(if (= item 0) 0 #.(1- (ash 1 32)))))) + `(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-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 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))) + (logior code (ash code 8) (ash code 16) (ash code 24))) + `(let ((code (sb!xc:char-code item))) + (logior code (ash code 8) (ash code 16) (ash code 24)))))) + `(let ((length (length sequence)) + (value ,value)) + (multiple-value-bind (times rem) + (truncate length 4) + (do ((index sb!vm:vector-data-offset (1+ index)) + (end (+ times sb!vm:vector-data-offset))) + ((= index end) + (let ((place (* times 4))) + (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 @@ -279,7 +427,7 @@ (memmove (sap+ (sapify dst) dst-start) (sap+ (sapify src) src-start) (- dst-end dst-start))) - nil)) + (values))) ;;;; transforms for EQL of floating point values @@ -290,3 +438,81 @@ '(and (= (double-float-low-bits x) (double-float-low-bits y)) (= (double-float-high-bits x) (double-float-high-bits y)))) + +;;;; modular functions +(define-good-modular-fun logand) +(define-good-modular-fun logior) +;;; FIXME: XOR? ANDC1, ANDC2? -- CSR, 2003-09-16 + +#!-alpha +(progn + (defknown #1=sb!vm::ash-left-mod32 (integer (integer 0)) (unsigned-byte 32) + (foldable flushable movable)) + (define-modular-fun-optimizer ash ((integer count) :width width) + (when (and (<= width 32) + (constant-lvar-p count) ; ? + (plusp (lvar-value count))) + (cut-to-width integer width) + '#1#)) + (setf (gethash '#1# *modular-versions*) '(ash 32))) +#!+alpha +(progn + (defknown #1=sb!vm::ash-left-mod64 (integer (integer 0)) (unsigned-byte 64) + (foldable flushable movable)) + (define-modular-fun-optimizer ash ((integer count) :width width) + (when (and (<= width 64) + (constant-lvar-p count) ; ? + (plusp (lvar-value count))) + (cut-to-width integer width) + '#1#) + (setf (gethash '#1# *modular-versions*) '(ash 64)))) + + +;;; 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)))