(defun mapfoo-transform (fn arglists accumulate take-car)
(collect ((do-clauses)
- (args-to-fn)
- (tests))
+ (args-to-fn)
+ (tests))
(let ((n-first (gensym)))
(dolist (a (if accumulate
- arglists
- `(,n-first ,@(rest arglists))))
- (let ((v (gensym)))
- (do-clauses `(,v ,a (cdr ,v)))
- (tests `(endp ,v))
- (args-to-fn (if take-car `(car ,v) v))))
+ arglists
+ `(,n-first ,@(rest arglists))))
+ (let ((v (gensym)))
+ (do-clauses `(,v ,a (cdr ,v)))
+ (tests `(endp ,v))
+ (args-to-fn (if take-car `(car ,v) v))))
(let* ((fn-sym (gensym)) ; for ONCE-ONLY-ish purposes
- (call `(funcall ,fn-sym . ,(args-to-fn)))
- (endtest `(or ,@(tests))))
- (ecase accumulate
- (:nconc
- (let ((temp (gensym))
- (map-result (gensym)))
- `(let ((,fn-sym ,fn)
- (,map-result (list nil)))
- (do-anonymous ((,temp ,map-result) . ,(do-clauses))
- (,endtest (cdr ,map-result))
- (setq ,temp (last (nconc ,temp ,call)))))))
- (:list
- (let ((temp (gensym))
- (map-result (gensym)))
- `(let ((,fn-sym ,fn)
- (,map-result (list nil)))
- (do-anonymous ((,temp ,map-result) . ,(do-clauses))
- (,endtest (truly-the list (cdr ,map-result)))
- (rplacd ,temp (setq ,temp (list ,call)))))))
- ((nil)
- `(let ((,fn-sym ,fn)
- (,n-first ,(first arglists)))
- (do-anonymous ,(do-clauses)
- (,endtest (truly-the list ,n-first))
+ (call `(funcall ,fn-sym . ,(args-to-fn)))
+ (endtest `(or ,@(tests))))
+ (ecase accumulate
+ (:nconc
+ (let ((temp (gensym))
+ (map-result (gensym)))
+ `(let ((,fn-sym ,fn)
+ (,map-result (list nil)))
+ (do-anonymous ((,temp ,map-result) . ,(do-clauses))
+ (,endtest (cdr ,map-result))
+ (setq ,temp (last (nconc ,temp ,call)))))))
+ (:list
+ (let ((temp (gensym))
+ (map-result (gensym)))
+ `(let ((,fn-sym ,fn)
+ (,map-result (list nil)))
+ (do-anonymous ((,temp ,map-result) . ,(do-clauses))
+ (,endtest (truly-the list (cdr ,map-result)))
+ (rplacd ,temp (setq ,temp (list ,call)))))))
+ ((nil)
+ `(let ((,fn-sym ,fn)
+ (,n-first ,(first arglists)))
+ (do-anonymous ,(do-clauses)
+ (,endtest (truly-the list ,n-first))
,call))))))))
(define-source-transform mapc (function list &rest more-lists)
;;; TRULY-THE for the most specific type we can determine.
(deftransform map ((result-type-arg fun seq &rest seqs) * * :node node)
(let* ((seq-names (make-gensym-list (1+ (length seqs))))
- (bare `(%map result-type-arg fun ,@seq-names))
- (constant-result-type-arg-p (constant-lvar-p result-type-arg))
- ;; what we know about the type of the result. (Note that the
- ;; "result type" argument is not necessarily the type of the
- ;; result, since NIL means the result has NULL type.)
- (result-type (if (not constant-result-type-arg-p)
- 'consed-sequence
- (let ((result-type-arg-value
- (lvar-value result-type-arg)))
- (if (null result-type-arg-value)
- 'null
- result-type-arg-value)))))
+ (bare `(%map result-type-arg fun ,@seq-names))
+ (constant-result-type-arg-p (constant-lvar-p result-type-arg))
+ ;; what we know about the type of the result. (Note that the
+ ;; "result type" argument is not necessarily the type of the
+ ;; result, since NIL means the result has NULL type.)
+ (result-type (if (not constant-result-type-arg-p)
+ 'consed-sequence
+ (let ((result-type-arg-value
+ (lvar-value result-type-arg)))
+ (if (null result-type-arg-value)
+ 'null
+ result-type-arg-value)))))
`(lambda (result-type-arg fun ,@seq-names)
(truly-the ,result-type
- ,(cond ((policy node (< safety 3))
- ;; ANSI requires the length-related type check only
- ;; when the SAFETY quality is 3... in other cases, we
- ;; skip it, because it could be expensive.
- bare)
- ((not constant-result-type-arg-p)
- `(sequence-of-checked-length-given-type ,bare
- result-type-arg))
- (t
- (let ((result-ctype (ir1-transform-specifier-type
- result-type)))
- (if (array-type-p result-ctype)
- (let ((dims (array-type-dimensions result-ctype)))
- (unless (and (listp dims) (= (length dims) 1))
- (give-up-ir1-transform "invalid sequence type"))
- (let ((dim (first dims)))
- (if (eq dim '*)
- bare
- `(vector-of-checked-length-given-length ,bare
- ,dim))))
- ;; FIXME: this is wrong, as not all subtypes of
- ;; VECTOR are ARRAY-TYPEs [consider, for
- ;; example, (OR (VECTOR T 3) (VECTOR T
- ;; 4))]. However, it's difficult to see what we
- ;; should put here... maybe we should
- ;; GIVE-UP-IR1-TRANSFORM if the type is a
- ;; subtype of VECTOR but not an ARRAY-TYPE?
- bare))))))))
+ ,(cond ((policy node (< safety 3))
+ ;; ANSI requires the length-related type check only
+ ;; when the SAFETY quality is 3... in other cases, we
+ ;; skip it, because it could be expensive.
+ bare)
+ ((not constant-result-type-arg-p)
+ `(sequence-of-checked-length-given-type ,bare
+ result-type-arg))
+ (t
+ (let ((result-ctype (ir1-transform-specifier-type
+ result-type)))
+ (if (array-type-p result-ctype)
+ (let ((dims (array-type-dimensions result-ctype)))
+ (unless (and (listp dims) (= (length dims) 1))
+ (give-up-ir1-transform "invalid sequence type"))
+ (let ((dim (first dims)))
+ (if (eq dim '*)
+ bare
+ `(vector-of-checked-length-given-length ,bare
+ ,dim))))
+ ;; FIXME: this is wrong, as not all subtypes of
+ ;; VECTOR are ARRAY-TYPEs [consider, for
+ ;; example, (OR (VECTOR T 3) (VECTOR T
+ ;; 4))]. However, it's difficult to see what we
+ ;; should put here... maybe we should
+ ;; GIVE-UP-IR1-TRANSFORM if the type is a
+ ;; subtype of VECTOR but not an ARRAY-TYPE?
+ bare))))))))
;;; Return a DO loop, mapping a function FUN to elements of
;;; sequences. SEQS is a list of lvars, SEQ-NAMES - list of variables,
(declare (type list seqs seq-names)
(type symbol into))
(collect ((bindings)
- (declarations)
+ (declarations)
(vector-lengths)
(tests)
(places))
for seq-name in seq-names
for type = (lvar-type seq)
do (cond ((csubtypep type (specifier-type 'list))
- (with-unique-names (index)
+ (with-unique-names (index)
(bindings `(,index ,seq-name (cdr ,index)))
(declarations `(type list ,index))
(places `(car ,index))
(tests `(endp ,index))))
((csubtypep type (specifier-type 'vector))
(process-vector `(length ,seq-name))
- (places `(aref ,seq-name index)))
+ (places `(locally (declare (optimize (insert-array-bounds-checks 0)))
+ (aref ,seq-name index))))
(t
(give-up-ir1-transform
"can't determine sequence argument type"))))
(process-vector `(array-dimension ,into 0))))
(when found-vector-p
(bindings `(length (min ,@(vector-lengths))))
- (tests `(= index length)))
+ (tests `(>= index length)))
`(do (,@(bindings))
((or ,@(tests)) ,result)
(declare ,@(declarations))
;;; the reader, because the code is complicated enough already and I
;;; don't happen to need that functionality right now. -- WHN 20000410
(deftransform %map ((result-type fun seq &rest seqs) * *
- :policy (>= speed space))
+ :policy (>= speed space))
"open code"
(unless (constant-lvar-p result-type)
(give-up-ir1-transform "RESULT-TYPE argument not constant"))
(labels ( ;; 1-valued SUBTYPEP, fails unless second value of SUBTYPEP is true
- (fn-1subtypep (fn x y)
- (multiple-value-bind (subtype-p valid-p) (funcall fn x y)
- (if valid-p
- subtype-p
- (give-up-ir1-transform
- "can't analyze sequence type relationship"))))
- (1subtypep (x y) (fn-1subtypep #'sb!xc:subtypep x y)))
+ (fn-1subtypep (fn x y)
+ (multiple-value-bind (subtype-p valid-p) (funcall fn x y)
+ (if valid-p
+ subtype-p
+ (give-up-ir1-transform
+ "can't analyze sequence type relationship"))))
+ (1subtypep (x y) (fn-1subtypep #'sb!xc:subtypep x y)))
(let* ((result-type-value (lvar-value result-type))
- (result-supertype (cond ((null result-type-value) 'null)
- ((1subtypep result-type-value 'vector)
- 'vector)
- ((1subtypep result-type-value 'list)
- 'list)
- (t
- (give-up-ir1-transform
- "can't determine result type")))))
+ (result-supertype (cond ((null result-type-value) 'null)
+ ((1subtypep result-type-value 'vector)
+ 'vector)
+ ((1subtypep result-type-value 'list)
+ 'list)
+ (t
+ (give-up-ir1-transform
+ "result type unsuitable")))))
(cond ((and result-type-value (null seqs))
- ;; The consing arity-1 cases can be implemented
- ;; reasonably efficiently as function calls, and the cost
- ;; of consing should be significantly larger than
- ;; function call overhead, so we always compile these
- ;; cases as full calls regardless of speed-versus-space
- ;; optimization policy.
- (cond ((subtypep result-type-value 'list)
- '(%map-to-list-arity-1 fun seq))
- ( ;; (This one can be inefficient due to COERCE, but
- ;; the current open-coded implementation has the
- ;; same problem.)
- (subtypep result-type-value 'vector)
- `(coerce (%map-to-simple-vector-arity-1 fun seq)
- ',result-type-value))
- (t (bug "impossible (?) sequence type"))))
- (t
- (let* ((seqs (cons seq seqs))
- (seq-args (make-gensym-list (length seqs))))
- (multiple-value-bind (push-dacc result)
- (ecase result-supertype
- (null (values nil nil))
- (list (values `(push funcall-result acc)
+ ;; The consing arity-1 cases can be implemented
+ ;; reasonably efficiently as function calls, and the cost
+ ;; of consing should be significantly larger than
+ ;; function call overhead, so we always compile these
+ ;; cases as full calls regardless of speed-versus-space
+ ;; optimization policy.
+ (cond ((subtypep result-type-value 'list)
+ '(%map-to-list-arity-1 fun seq))
+ ( ;; (This one can be inefficient due to COERCE, but
+ ;; the current open-coded implementation has the
+ ;; same problem.)
+ (subtypep result-type-value 'vector)
+ `(coerce (%map-to-simple-vector-arity-1 fun seq)
+ ',result-type-value))
+ (t (bug "impossible (?) sequence type"))))
+ (t
+ (let* ((seqs (cons seq seqs))
+ (seq-args (make-gensym-list (length seqs))))
+ (multiple-value-bind (push-dacc result)
+ (ecase result-supertype
+ (null (values nil nil))
+ (list (values `(push funcall-result acc)
`(nreverse acc)))
- (vector (values `(push funcall-result acc)
- `(coerce (nreverse acc)
- ',result-type-value))))
- ;; (We use the same idiom, of returning a LAMBDA from
- ;; DEFTRANSFORM, as is used in the DEFTRANSFORMs for
- ;; FUNCALL and ALIEN-FUNCALL, and for the same
- ;; reason: we need to get the runtime values of each
- ;; of the &REST vars.)
- `(lambda (result-type fun ,@seq-args)
- (declare (ignore result-type))
+ (vector (values `(push funcall-result acc)
+ `(coerce (nreverse acc)
+ ',result-type-value))))
+ ;; (We use the same idiom, of returning a LAMBDA from
+ ;; DEFTRANSFORM, as is used in the DEFTRANSFORMs for
+ ;; FUNCALL and ALIEN-FUNCALL, and for the same
+ ;; reason: we need to get the runtime values of each
+ ;; of the &REST vars.)
+ `(lambda (result-type fun ,@seq-args)
+ (declare (ignore result-type))
(let ((fun (%coerce-callable-to-fun fun))
(acc nil))
(declare (type list acc))
:result '(when (array-has-fill-pointer-p result)
(setf (fill-pointer result) index))
:into 'result
- :body '(setf (aref result index) funcall-result))
+ :body '(locally (declare (optimize (insert-array-bounds-checks 0)))
+ (setf (aref result index) funcall-result)))
result)))
\f
'(setf (car (nthcdr i s)) v))
(deftransform %check-vector-sequence-bounds ((vector start end)
- (vector * *) *
- :node node)
+ (vector * *) *
+ :node node)
(if (policy node (< safety speed))
'(or end (length vector))
'(let ((length (length vector)))
- (if (<= 0 start (or end length) length)
- (or end length)
- (sb!impl::signal-bounding-indices-bad-error vector start end)))))
+ (if (<= 0 start (or end length) length)
+ (or end length)
+ (sb!impl::signal-bounding-indices-bad-error vector start end)))))
(macrolet ((def (name)
`(deftransform ,name ((e l &key (test #'eql)) * *
- :node node)
+ :node node)
(unless (constant-lvar-p l)
(give-up-ir1-transform))
(deftransform delete-if ((pred list) (t list))
"open code"
'(do ((x list (cdr x))
- (splice '()))
+ (splice '()))
((endp x) list)
(cond ((funcall pred (car x))
- (if (null splice)
- (setq list (cdr x))
- (rplacd splice (cdr x))))
- (t (setq splice x)))))
+ (if (null splice)
+ (setq list (cdr x))
+ (rplacd splice (cdr x))))
+ (t (setq splice x)))))
(deftransform fill ((seq item &key (start 0) (end (length seq)))
- (vector t &key (:start t) (:end index))
- *
- :policy (> speed space))
+ (vector t &key (:start t) (:end index))
+ *
+ :policy (> speed space))
"open code"
(let ((element-type (upgraded-element-type-specifier-or-give-up seq)))
- (values
+ (values
`(with-array-data ((data seq)
- (start start)
- (end end))
+ (start start)
+ (end end))
(declare (type (simple-array ,element-type 1) data))
(declare (type fixnum start end))
(do ((i start (1+ i)))
- ((= i end) seq)
- (declare (type index i))
- ;; WITH-ARRAY-DATA did our range checks once and for all, so
- ;; it'd be wasteful to check again on every AREF...
- (declare (optimize (safety 0)))
- (setf (aref data i) item)))
+ ((= i end) seq)
+ (declare (type index i))
+ ;; WITH-ARRAY-DATA did our range checks once and for all, so
+ ;; it'd be wasteful to check again on every AREF...
+ (declare (optimize (safety 0)))
+ (setf (aref data i) item)))
;; ... though we still need to check that the new element can fit
;; into the vector in safe code. -- CSR, 2002-07-05
`((declare (type ,element-type item))))))
(declare (type lvar lvar) (list names))
(let ((use (lvar-uses lvar)))
(and (ref-p use)
- (let ((leaf (ref-leaf use)))
- (and (global-var-p leaf)
- (eq (global-var-kind leaf) :global-function)
- (not (null (member (leaf-source-name leaf) names
- :test #'equal))))))))
+ (let ((leaf (ref-leaf use)))
+ (and (global-var-p leaf)
+ (eq (global-var-kind leaf) :global-function)
+ (not (null (member (leaf-source-name leaf) names
+ :test #'equal))))))))
;;; If LVAR is a constant lvar, the return the constant value. If it
;;; is null, then return default, otherwise quietly give up the IR1
(defun constant-value-or-lose (lvar &optional default)
(declare (type (or lvar null) lvar))
(cond ((not lvar) default)
- ((constant-lvar-p lvar)
- (lvar-value lvar))
- (t
- (give-up-ir1-transform))))
+ ((constant-lvar-p lvar)
+ (lvar-value lvar))
+ (t
+ (give-up-ir1-transform))))
;;; FIXME: Why is this code commented out? (Why *was* it commented
;;; out? We inherited this situation from cmucl-2.4.8, with no
;;; the argument (which should be referenced in any expansion), and
;;; the continuation for that argument (or NIL if unsupplied.)
(defstruct (arg (:constructor %make-arg (name cont))
- (:copier nil))
+ (:copier nil))
(name nil :type symbol)
(cont nil :type (or continuation null)))
(defmacro make-arg (name)
(declare (type (or arg null) arg))
(if (and arg (arg-cont arg))
(let ((cont (arg-cont arg)))
- (unless (constant-continuation-p cont)
- (give-up-ir1-transform "Argument is not constant: ~S."
- (arg-name arg)))
- (continuation-value from-end))
+ (unless (constant-continuation-p cont)
+ (give-up-ir1-transform "Argument is not constant: ~S."
+ (arg-name arg)))
+ (continuation-value from-end))
default))
;;; If Arg is a constant and is EQL to X, then return T, otherwise NIL. If
(declare (type (or arg null) x))
(if (and arg (arg-cont arg))
(let ((cont (arg-cont arg)))
- (and (constant-continuation-p cont)
- (eql (continuation-value cont) x)))
+ (and (constant-continuation-p cont)
+ (eql (continuation-value cont) x)))
(eql default x)))
(defstruct (iterator (:copier nil))
;;; the iteration is forward or backward, then GIVE-UP.
(defun make-sequence-iterator (sequence type &key start end from-end index)
(declare (symbol sequence) (type ctype type)
- (type (or arg null) start end from-end)
- (type (or symbol null) index))
+ (type (or arg null) start end from-end)
+ (type (or symbol null) index))
(let ((from-end (arg-constant-value from-end nil)))
(cond ((csubtypep type (specifier-type 'vector))
- (let* ((n-stop (gensym))
- (n-idx (or index (gensym)))
- (start (default-arg 0 start))
- (end (default-arg `(length ,sequence) end)))
- (make-iterator
- :kind :normal
- :binds `((,n-idx ,(if from-end `(1- ,end) ,start))
- (,n-stop ,(if from-end `(1- ,start) ,end)))
- :decls `((type neg-index ,n-idx ,n-stop))
- :current `(aref ,sequence ,n-idx)
- :done `(,(if from-end '<= '>=) ,n-idx ,n-stop)
- :next `(setq ,n-idx
- ,(if from-end `(1- ,n-idx) `(1+ ,n-idx)))
- :length (if from-end
- `(- ,n-idx ,n-stop)
- `(- ,n-stop ,n-idx)))))
- ((csubtypep type (specifier-type 'list))
- (let* ((n-stop (if (and end (not from-end)) (gensym) nil))
- (n-current (gensym))
- (start-p (not (arg-eql start 0 0)))
- (end-p (not (arg-eql end nil nil)))
- (start (default-arg start 0))
- (end (default-arg end nil)))
- (make-iterator
- :binds `((,n-current
- ,(if from-end
- (if (or start-p end-p)
- `(nreverse (subseq ,sequence ,start
- ,@(when end `(,end))))
- `(reverse ,sequence))
- (if start-p
- `(nthcdr ,start ,sequence)
- sequence)))
- ,@(when n-stop
- `((,n-stop (nthcdr (the index
- (- ,end ,start))
- ,n-current))))
- ,@(when index
- `((,index ,(if from-end `(1- ,end) start)))))
- :kind :normal
- :decls `((list ,n-current ,n-end)
- ,@(when index `((type neg-index ,index))))
- :current `(car ,n-current)
- :done `(eq ,n-current ,n-stop)
- :length `(- ,(or end `(length ,sequence)) ,start)
- :next `(progn
- (setq ,n-current (cdr ,n-current))
- ,@(when index
- `((setq ,n-idx
- ,(if from-end
- `(1- ,index)
- `(1+ ,index)))))))))
- (t
- (give-up-ir1-transform
- "can't tell whether sequence is a list or a vector")))))
+ (let* ((n-stop (gensym))
+ (n-idx (or index (gensym)))
+ (start (default-arg 0 start))
+ (end (default-arg `(length ,sequence) end)))
+ (make-iterator
+ :kind :normal
+ :binds `((,n-idx ,(if from-end `(1- ,end) ,start))
+ (,n-stop ,(if from-end `(1- ,start) ,end)))
+ :decls `((type neg-index ,n-idx ,n-stop))
+ :current `(aref ,sequence ,n-idx)
+ :done `(,(if from-end '<= '>=) ,n-idx ,n-stop)
+ :next `(setq ,n-idx
+ ,(if from-end `(1- ,n-idx) `(1+ ,n-idx)))
+ :length (if from-end
+ `(- ,n-idx ,n-stop)
+ `(- ,n-stop ,n-idx)))))
+ ((csubtypep type (specifier-type 'list))
+ (let* ((n-stop (if (and end (not from-end)) (gensym) nil))
+ (n-current (gensym))
+ (start-p (not (arg-eql start 0 0)))
+ (end-p (not (arg-eql end nil nil)))
+ (start (default-arg start 0))
+ (end (default-arg end nil)))
+ (make-iterator
+ :binds `((,n-current
+ ,(if from-end
+ (if (or start-p end-p)
+ `(nreverse (subseq ,sequence ,start
+ ,@(when end `(,end))))
+ `(reverse ,sequence))
+ (if start-p
+ `(nthcdr ,start ,sequence)
+ sequence)))
+ ,@(when n-stop
+ `((,n-stop (nthcdr (the index
+ (- ,end ,start))
+ ,n-current))))
+ ,@(when index
+ `((,index ,(if from-end `(1- ,end) start)))))
+ :kind :normal
+ :decls `((list ,n-current ,n-end)
+ ,@(when index `((type neg-index ,index))))
+ :current `(car ,n-current)
+ :done `(eq ,n-current ,n-stop)
+ :length `(- ,(or end `(length ,sequence)) ,start)
+ :next `(progn
+ (setq ,n-current (cdr ,n-current))
+ ,@(when index
+ `((setq ,n-idx
+ ,(if from-end
+ `(1- ,index)
+ `(1+ ,index)))))))))
+ (t
+ (give-up-ir1-transform
+ "can't tell whether sequence is a list or a vector")))))
;;; Make an iterator used for constructing result sequences. Name is a
;;; variable to be bound to the result sequence. Type is the type of result
#!+sb-doc
"COERCE-FUNCTIONS ({(Name Fun-Arg Default)}*) Form*"
(collect ((binds)
- (defs))
+ (defs))
(dolist (spec specs)
`(let ((body (progn ,@body))
- (n-fun (arg-name ,(second spec)))
- (fun-cont (arg-cont ,(second spec))))
- (cond ((not fun-cont)
- `(macrolet ((,',(first spec) (&rest args)
- `(,',',(third spec) ,@args)))
- ,body))
- ((not (csubtypep (continuation-type fun-cont)
- (specifier-type 'function)))
- (when (policy *compiler-error-context*
- (> speed inhibit-warnings))
- (compiler-notify
- "~S may not be a function, so must coerce at run-time."
- n-fun))
- (once-only ((n-fun `(if (functionp ,n-fun)
- ,n-fun
- (symbol-function ,n-fun))))
- `(macrolet ((,',(first spec) (&rest args)
- `(funcall ,',n-fun ,@args)))
- ,body)))
- (t
- `(macrolet ((,',(first spec) (&rest args)
- `(funcall ,',n-fun ,@args)))
- ,body)))))))
+ (n-fun (arg-name ,(second spec)))
+ (fun-cont (arg-cont ,(second spec))))
+ (cond ((not fun-cont)
+ `(macrolet ((,',(first spec) (&rest args)
+ `(,',',(third spec) ,@args)))
+ ,body))
+ ((not (csubtypep (continuation-type fun-cont)
+ (specifier-type 'function)))
+ (when (policy *compiler-error-context*
+ (> speed inhibit-warnings))
+ (compiler-notify
+ "~S may not be a function, so must coerce at run-time."
+ n-fun))
+ (once-only ((n-fun `(if (functionp ,n-fun)
+ ,n-fun
+ (symbol-function ,n-fun))))
+ `(macrolet ((,',(first spec) (&rest args)
+ `(funcall ,',n-fun ,@args)))
+ ,body)))
+ (t
+ `(macrolet ((,',(first spec) (&rest args)
+ `(funcall ,',n-fun ,@args)))
+ ,body)))))))
;;; Wrap code around the result of the body to define Name as a local macro
;;; that returns true when its arguments satisfy the test according to the Args
`(let ((not-p (arg-cont ,test-not)))
(when (and (arg-cont ,test) not-p)
(abort-ir1-transform "Both ~S and ~S were supplied."
- (arg-name ,test)
- (arg-name ,test-not)))
+ (arg-name ,test)
+ (arg-name ,test-not)))
(coerce-funs ((,name (if not-p ,test-not ,test) eql))
,@body)))
|#
(- start2
start1))))))
index)
- (t nil))
+ (t nil))
,(if ',equalp 'end1 nil))))))
(def string<* t nil)
(def string<=* t t)
(def string/=* identity))
\f
-;;;; string-only transforms for sequence functions
-;;;;
-;;;; Note: CMU CL had more of these, including transforms for
-;;;; functions which cons. In SBCL, we've gotten rid of most of the
-;;;; transforms for functions which cons, since our GC overhead is
-;;;; sufficiently large that it doesn't seem worth it to try to
-;;;; economize on function call overhead or on the overhead of runtime
-;;;; type dispatch in AREF. The exception is CONCATENATE, since
-;;;; a full call to CONCATENATE would have to look up the sequence
-;;;; type, which can be really slow.
-
-;;; Moved here from generic/vm-tran.lisp to satisfy clisp
-;;;
-;;; FIXME: Add a comment telling whether this holds for all vectors
-;;; or only for vectors based on simple arrays (non-adjustable, etc.).
+;;;; transforms for sequence functions
+
+;;; Moved here from generic/vm-tran.lisp to satisfy clisp. Only applies
+;;; to vectors based on simple arrays.
(def!constant vector-data-bit-offset
(* sb!vm:vector-data-offset sb!vm:n-word-bits))
(defun valid-bit-bash-saetp-p (saetp)
;; BIT-BASHing isn't allowed on simple vectors that contain pointers
(and (not (eq t (sb!vm:saetp-specifier saetp)))
+ ;; Disallowing (VECTOR NIL) also means that we won't transform
+ ;; sequence functions into bit-bashing code and we let the
+ ;; generic sequence functions signal errors if necessary.
+ (not (zerop (sb!vm:saetp-n-bits saetp)))
;; Due to limitations with the current BIT-BASHing code, we can't
;; BIT-BASH reliably on arrays whose element types are larger
;; than the word size.
(<= (sb!vm:saetp-n-bits saetp) sb!vm:n-word-bits)))
) ; EVAL-WHEN
-;; FIXME: It turns out that this transform (for SIMPLE-BASE-STRINGS)
-;; is critical for the performance of string streams. Make this
-;; more explicit.
+;;; FIXME: In the copy loops below, we code the loops in a strange
+;;; fashion:
+;;;
+;;; (do ((i (+ src-offset length) (1- i)))
+;;; ((<= i 0) ...)
+;;; (... (aref foo (1- i)) ...))
+;;;
+;;; rather than the more natural (and seemingly more efficient):
+;;;
+;;; (do ((i (1- (+ src-offset length)) (1- i)))
+;;; ((< i 0) ...)
+;;; (... (aref foo i) ...))
+;;;
+;;; (more efficient because we don't have to do the index adjusting on
+;;; every iteration of the loop)
+;;;
+;;; We do this to avoid a suboptimality in SBCL's backend. In the
+;;; latter case, the backend thinks I is a FIXNUM (which it is), but
+;;; when used as an array index, the backend thinks I is a
+;;; POSITIVE-FIXNUM (which it is). However, since the backend thinks of
+;;; these as distinct storage classes, it cannot coerce a move from a
+;;; FIXNUM TN to a POSITIVE-FIXNUM TN. The practical effect of this
+;;; deficiency is that we have two extra moves and increased register
+;;; pressure, which can lead to some spectacularly bad register
+;;; allocation. (sub-FIXME: the register allocation even with the
+;;; strangely written loops is not always excellent, either...). Doing
+;;; it the first way, above, means that I is always thought of as a
+;;; POSITIVE-FIXNUM and there are no issues.
+;;;
+;;; Besides, the *-WITH-OFFSET machinery will fold those index
+;;; adjustments in the first version into the array addressing at no
+;;; performance penalty!
+
+;;; This transform is critical to the performance of string streams. If
+;;; you tweak it, make sure that you compare the disassembly, if not the
+;;; performance of, the functions implementing string streams
+;;; (e.g. SB!IMPL::STRING-OUCH).
(macrolet
((define-replace-transforms ()
(loop for saetp across sb!vm:*specialized-array-element-type-properties*
- when (valid-bit-bash-saetp-p saetp)
+ for sequence-type = `(simple-array ,(sb!vm:saetp-specifier saetp) (*))
+ unless (= (sb!vm:saetp-typecode saetp) sb!vm::simple-array-nil-widetag)
collect
- (let* ((sequence-type `(simple-array ,(sb!vm:saetp-specifier saetp) (*)))
- (n-element-bits (sb!vm:saetp-n-bits saetp))
- (bash-function (intern (format nil "UB~A-BASH-COPY" n-element-bits)
- (find-package "SB!KERNEL"))))
- `(deftransform replace ((seq1 seq2 &key (start1 0) (start2 0) end1 end2)
- (,sequence-type ,sequence-type &rest t)
- ,sequence-type
- :node node)
- `(let* ((len1 (length seq1))
- (len2 (length seq2))
- (end1 (or end1 len1))
- (end2 (or end2 len2))
- (replace-len1 (- end1 start1))
- (replace-len2 (- end2 start2)))
- ,(unless (policy node (= safety 0))
- `(progn
- (unless (<= 0 start1 end1 len1)
- (sb!impl::signal-bounding-indices-bad-error seq1 start1 end1))
- (unless (<= 0 start2 end2 len2)
- (sb!impl::signal-bounding-indices-bad-error seq2 start2 end2))))
- (funcall (function ,',bash-function)
- seq2 start2
- seq1 start1
- (min replace-len1 replace-len2))
- seq1)))
+ `(deftransform replace ((seq1 seq2 &key (start1 0) (start2 0) end1 end2)
+ (,sequence-type ,sequence-type &rest t)
+ ,sequence-type
+ :node node)
+ ,(cond
+ ((valid-bit-bash-saetp-p saetp) nil)
+ ;; If we're not bit-bashing, only allow cases where we
+ ;; can determine the order of copying up front. (There
+ ;; are actually more cases we can handle if we know the
+ ;; amount that we're copying, but this handles the
+ ;; common cases.)
+ (t '(unless (= (constant-value-or-lose start1 0)
+ (constant-value-or-lose start2 0))
+ (give-up-ir1-transform))))
+ `(let* ((len1 (length seq1))
+ (len2 (length seq2))
+ (end1 (or end1 len1))
+ (end2 (or end2 len2))
+ (replace-len1 (- end1 start1))
+ (replace-len2 (- end2 start2)))
+ ,(unless (policy node (= safety 0))
+ `(progn
+ (unless (<= 0 start1 end1 len1)
+ (sb!impl::signal-bounding-indices-bad-error seq1 start1 end1))
+ (unless (<= 0 start2 end2 len2)
+ (sb!impl::signal-bounding-indices-bad-error seq2 start2 end2))))
+ ,',(cond
+ ((valid-bit-bash-saetp-p saetp)
+ (let* ((n-element-bits (sb!vm:saetp-n-bits saetp))
+ (bash-function (intern (format nil "UB~D-BASH-COPY" n-element-bits)
+ (find-package "SB!KERNEL"))))
+ `(funcall (function ,bash-function) seq2 start2
+ seq1 start1 (min replace-len1 replace-len2))))
+ (t
+ ;; We can expand the loop inline here because we
+ ;; would have given up the transform (see above)
+ ;; if we didn't have constant matching start
+ ;; indices.
+ '(do ((i start1 (1+ i))
+ (end (+ start1
+ (min replace-len1 replace-len2))))
+ ((>= i end))
+ (declare (optimize (insert-array-bounds-checks 0)))
+ (setf (aref seq1 i) (aref seq2 i)))))
+ seq1))
into forms
finally (return `(progn ,@forms)))))
(define-replace-transforms))
-(macrolet
- ((define-subseq-transforms ()
- (loop for saetp across sb!vm:*specialized-array-element-type-properties*
- when (valid-bit-bash-saetp-p saetp)
- collect
- (let* ((sequence-type `(simple-array ,(sb!vm:saetp-specifier saetp) (*)))
- (n-element-bits (sb!vm:saetp-n-bits saetp))
- (bash-function (intern (format nil "UB~A-BASH-COPY" n-element-bits)
- (find-package "SB!KERNEL"))))
- `(deftransform subseq ((seq start &optional end)
- (,sequence-type t &optional t)
- ,sequence-type :node node)
- `(let* ((length (length seq))
- (end (if end (min end length) length)))
- ,(unless (policy node (= safety 0))
- `(progn
- (unless (<= 0 start end length)
- (sb!impl::signal-bounding-indices-bad-error seq start end))))
- (let* ((size (- end start))
- (result (make-array size :element-type ',',(sb!vm:saetp-specifier saetp))))
- (funcall (function ,',bash-function)
- seq start result 0 size)
- result))))
- into forms
- finally (return `(progn ,@forms)))))
- (define-subseq-transforms))
-
-(macrolet
- ((define-copy-seq-transforms ()
- (loop for saetp across sb!vm:*specialized-array-element-type-properties*
- when (valid-bit-bash-saetp-p saetp)
- collect
- (let* ((sequence-type `(simple-array ,(sb!vm:saetp-specifier saetp) (*)))
- (n-element-bits (sb!vm:saetp-n-bits saetp))
- (bash-function (intern (format nil "UB~A-BASH-COPY" n-element-bits)
- (find-package "SB!KERNEL"))))
- `(deftransform copy-seq ((seq) (,sequence-type)
- ,sequence-type)
- `(let* ((length (length seq))
- (result (make-array length :element-type ',',(sb!vm:saetp-specifier saetp))))
- (funcall (function ,',bash-function)
- seq 0 result 0 length)
- result)))
- into forms
- finally (return `(progn ,@forms)))))
- (define-copy-seq-transforms))
-
-;;; FIXME: this would be a valid transform for certain excluded cases:
-;;; * :TEST 'CHAR= or :TEST #'CHAR=
-;;; * :TEST 'EQL or :TEST #'EQL
-;;; * :FROM-END NIL (or :FROM-END non-NIL, with a little ingenuity)
-(deftransform search ((pattern text &key (start1 0) (start2 0) end1 end2)
- (simple-string simple-string &rest t)
- *
- :policy (> speed (max space safety)))
- `(block search
- (let ((end1 (or end1 (length pattern)))
- (end2 (or end2 (length text))))
- (do ((index2 start2 (1+ index2)))
- ((>= index2 end2) nil)
- (when (do ((index1 start1 (1+ index1))
- (index2 index2 (1+ index2)))
- ((>= index1 end1) t)
- (when (= index2 end2)
- (return-from search nil))
- (when (char/= (char pattern index1) (char text index2))
- (return nil)))
- (return index2))))))
+;;; Expand simple cases of UB<SIZE>-BASH-COPY inline. "simple" is
+;;; defined as those cases where we are doing word-aligned copies from
+;;; both the source and the destination and we are copying from the same
+;;; offset from both the source and the destination. (The last
+;;; condition is there so we can determine the direction to copy at
+;;; compile time rather than runtime. Remember that UB<SIZE>-BASH-COPY
+;;; acts like memmove, not memcpy.) These conditions may seem rather
+;;; restrictive, but they do catch common cases, like allocating a (* 2
+;;; N)-size buffer and blitting in the old N-size buffer in.
+
+(defun frob-bash-transform (src src-offset
+ dst dst-offset
+ length n-elems-per-word)
+ (declare (ignore src dst length))
+ (let ((n-bits-per-elem (truncate sb!vm:n-word-bits n-elems-per-word)))
+ (multiple-value-bind (src-word src-elt)
+ (truncate (lvar-value src-offset) n-elems-per-word)
+ (multiple-value-bind (dst-word dst-elt)
+ (truncate (lvar-value dst-offset) n-elems-per-word)
+ ;; Avoid non-word aligned copies.
+ (unless (and (zerop src-elt) (zerop dst-elt))
+ (give-up-ir1-transform))
+ ;; Avoid copies where we would have to insert code for
+ ;; determining the direction of copying.
+ (unless (= src-word dst-word)
+ (give-up-ir1-transform))
+ ;; FIXME: The cross-compiler doesn't optimize TRUNCATE properly,
+ ;; so we have to do its work here.
+ `(let ((end (+ ,src-word ,(if (= n-elems-per-word 1)
+ 'length
+ `(truncate (the index length) ,n-elems-per-word)))))
+ (declare (type index end))
+ ;; Handle any bits at the end.
+ (when (logtest length (1- ,n-elems-per-word))
+ (let* ((extra (mod length ,n-elems-per-word))
+ ;; FIXME: The shift amount on this ASH is
+ ;; *always* negative, but the backend doesn't
+ ;; have a NEGATIVE-FIXNUM primitive type, so we
+ ;; wind up with a pile of code that tests the
+ ;; sign of the shift count prior to shifting when
+ ;; all we need is a simple negate and shift
+ ;; right. Yuck.
+ (mask (ash #.(1- (ash 1 sb!vm:n-word-bits))
+ (* (- extra ,n-elems-per-word)
+ ,n-bits-per-elem))))
+ (setf (sb!kernel:%vector-raw-bits dst end)
+ (logior
+ (logandc2 (sb!kernel:%vector-raw-bits dst end)
+ (ash mask
+ ,(ecase sb!c:*backend-byte-order*
+ (:little-endian 0)
+ (:big-endian `(* (- ,n-elems-per-word extra)
+ ,n-bits-per-elem)))))
+ (logand (sb!kernel:%vector-raw-bits src end)
+ (ash mask
+ ,(ecase sb!c:*backend-byte-order*
+ (:little-endian 0)
+ (:big-endian `(* (- ,n-elems-per-word extra)
+ ,n-bits-per-elem)))))))))
+ ;; Copy from the end to save a register.
+ (do ((i end (1- i)))
+ ((<= i ,src-word))
+ (setf (sb!kernel:%vector-raw-bits dst (1- i))
+ (sb!kernel:%vector-raw-bits src (1- i)))))))))
+
+#.(loop for i = 1 then (* i 2)
+ collect `(deftransform ,(intern (format nil "UB~D-BASH-COPY" i)
+ "SB!KERNEL")
+ ((src src-offset
+ dst dst-offset
+ length)
+ ((simple-unboxed-array (*))
+ (constant-arg index)
+ (simple-unboxed-array (*))
+ (constant-arg index)
+ index)
+ *)
+ (frob-bash-transform src src-offset
+ dst dst-offset length
+ ,(truncate sb!vm:n-word-bits i))) into forms
+ until (= i sb!vm:n-word-bits)
+ finally (return `(progn ,@forms)))
+
+;;; We expand copy loops inline in SUBSEQ and COPY-SEQ if we're copying
+;;; arrays with elements of size >= the word size. We do this because
+;;; we know the arrays cannot alias (one was just consed), therefore we
+;;; can determine at compile time the direction to copy, and for
+;;; word-sized elements, UB<WORD-SIZE>-BASH-COPY will do a bit of
+;;; needless checking to figure out what's going on. The same
+;;; considerations apply if we are copying elements larger than the word
+;;; size, with the additional twist that doing it inline is likely to
+;;; cons far less than calling REPLACE and letting generic code do the
+;;; work.
+;;;
+;;; However, we do not do this for elements whose size is < than the
+;;; word size because we don't want to deal with any alignment issues
+;;; inline. The UB*-BASH-COPY transforms might fix things up later
+;;; anyway.
+
+(defun maybe-expand-copy-loop-inline (src src-offset dst dst-offset length
+ element-type)
+ (let ((saetp (find-saetp element-type)))
+ (aver saetp)
+ (if (>= (sb!vm:saetp-n-bits saetp) sb!vm:n-word-bits)
+ (expand-aref-copy-loop src src-offset dst dst-offset length)
+ `(locally (declare (optimize (safety 0)))
+ (replace ,dst ,src :start1 ,dst-offset :start2 ,src-offset :end1 ,length)))))
+
+(defun expand-aref-copy-loop (src src-offset dst dst-offset length)
+ (if (eql src-offset dst-offset)
+ `(do ((i (+ ,src-offset ,length) (1- i)))
+ ((<= i ,src-offset))
+ (declare (optimize (insert-array-bounds-checks 0)))
+ (setf (aref ,dst (1- i)) (aref ,src (1- i))))
+ ;; KLUDGE: The compiler is not able to derive that (+ offset
+ ;; length) must be a fixnum, but arrives at (unsigned-byte 29).
+ ;; We, however, know it must be so, as by this point the bounds
+ ;; have already been checked.
+ `(do ((i (truly-the fixnum (+ ,src-offset ,length)) (1- i))
+ (j (+ ,dst-offset ,length) (1- j)))
+ ((<= i ,src-offset))
+ (declare (optimize (insert-array-bounds-checks 0))
+ (type (integer 0 #.sb!xc:array-dimension-limit) j i))
+ (setf (aref ,dst (1- j)) (aref ,src (1- i))))))
+
+(deftransform subseq ((seq start &optional end)
+ ((or (simple-unboxed-array (*)) simple-vector) t &optional t)
+ * :node node)
+ (let ((array-type (lvar-type seq)))
+ (unless (array-type-p array-type)
+ (give-up-ir1-transform))
+ (let ((element-type (type-specifier (array-type-specialized-element-type array-type))))
+ `(let* ((length (length seq))
+ (end (or end length)))
+ ,(unless (policy node (= safety 0))
+ '(progn
+ (unless (<= 0 start end length)
+ (sb!impl::signal-bounding-indices-bad-error seq start end))))
+ (let* ((size (- end start))
+ (result (make-array size :element-type ',element-type)))
+ ,(maybe-expand-copy-loop-inline 'seq 'start 'result 0 'size element-type)
+ result)))))
+
+(deftransform copy-seq ((seq) ((or (simple-unboxed-array (*)) simple-vector)) *)
+ (let ((array-type (lvar-type seq)))
+ (unless (array-type-p array-type)
+ (give-up-ir1-transform))
+ (let ((element-type (type-specifier (array-type-specialized-element-type array-type))))
+ `(let* ((length (length seq))
+ (result (make-array length :element-type ',element-type)))
+ ,(maybe-expand-copy-loop-inline 'seq 0 'result 0 'length element-type)
+ result))))
+
+;;; FIXME: it really should be possible to take advantage of the
+;;; macros used in code/seq.lisp here to avoid duplication of code,
+;;; and enable even funkier transformations.
+(deftransform search ((pattern text &key (start1 0) (start2 0) end1 end2
+ (test #'eql)
+ (key #'identity)
+ from-end)
+ (vector vector &rest t)
+ *
+ :policy (> speed (max space safety)))
+ "open code"
+ (let ((from-end (when (lvar-p from-end)
+ (unless (constant-lvar-p from-end)
+ (give-up-ir1-transform ":FROM-END is not constant."))
+ (lvar-value from-end)))
+ (keyp (lvar-p key))
+ (testp (lvar-p test)))
+ `(block search
+ (let ((end1 (or end1 (length pattern)))
+ (end2 (or end2 (length text)))
+ ,@(when keyp
+ '((key (coerce key 'function))))
+ ,@(when testp
+ '((test (coerce test 'function)))))
+ (declare (type index start1 start2 end1 end2))
+ (do (,(if from-end
+ '(index2 (- end2 (- end1 start1)) (1- index2))
+ '(index2 start2 (1+ index2))))
+ (,(if from-end
+ '(< index2 start2)
+ '(>= index2 end2))
+ nil)
+ ;; INDEX2 is FIXNUM, not an INDEX, as right before the loop
+ ;; terminates is hits -1 when :FROM-END is true and :START2
+ ;; is 0.
+ (declare (type fixnum index2))
+ (when (do ((index1 start1 (1+ index1))
+ (index2 index2 (1+ index2)))
+ ((>= index1 end1) t)
+ (declare (type index index1 index2))
+ ,@(unless from-end
+ '((when (= index2 end2)
+ (return-from search nil))))
+ (unless (,@(if testp
+ '(funcall test)
+ '(eql))
+ ,(if keyp
+ '(funcall key (aref pattern index1))
+ '(aref pattern index1))
+ ,(if keyp
+ '(funcall key (aref text index2))
+ '(aref text index2)))
+ (return nil)))
+ (return index2)))))))
;;; FIXME: It seems as though it should be possible to make a DEFUN
;;; %CONCATENATE (with a DEFTRANSFORM to translate constant RTYPE to
;;; FIXME: disabled for sb-unicode: probably want it back
#!-sb-unicode
(deftransform concatenate ((rtype &rest sequences)
- (t &rest (or simple-base-string
- (simple-array nil (*))))
- simple-base-string
- :policy (< safety 3))
+ (t &rest (or simple-base-string
+ (simple-array nil (*))))
+ simple-base-string
+ :policy (< safety 3))
(loop for rest-seqs on sequences
for n-seq = (gensym "N-SEQ")
for n-length = (gensym "N-LENGTH")
collect n-length into all-lengths
collect next-start into starts
collect `(if (and (typep ,n-seq '(simple-array nil (*)))
- (> ,n-length 0))
- (error 'nil-array-accessed-error)
+ (> ,n-length 0))
+ (error 'nil-array-accessed-error)
(#.(let* ((i (position 'character sb!kernel::*specialized-array-element-types*))
(saetp (aref sb!vm:*specialized-array-element-type-properties* i))
(n-bits (sb!vm:saetp-n-bits saetp)))
(defoptimizer (car derive-type) ((cons))
(let ((type (lvar-type cons))
- (null-type (specifier-type 'null)))
+ (null-type (specifier-type 'null)))
(cond ((eq type null-type)
- null-type)
- ((cons-type-p type)
- (cons-type-car-type type)))))
+ null-type)
+ ((cons-type-p type)
+ (cons-type-car-type type)))))
(defoptimizer (cdr derive-type) ((cons))
(let ((type (lvar-type cons))
- (null-type (specifier-type 'null)))
+ (null-type (specifier-type 'null)))
(cond ((eq type null-type)
- null-type)
- ((cons-type-p type)
- (cons-type-cdr-type type)))))
+ null-type)
+ ((cons-type-p type)
+ (cons-type-cdr-type type)))))
\f
;;;; FIND, POSITION, and their -IF and -IF-NOT variants
(defun check-inlineability-of-find-position-if (sequence from-end)
(let ((ctype (lvar-type sequence)))
(cond ((csubtypep ctype (specifier-type 'vector))
- ;; It's not worth trying to inline vector code unless we
- ;; know a fair amount about it at compile time.
- (upgraded-element-type-specifier-or-give-up sequence)
- (unless (constant-lvar-p from-end)
- (give-up-ir1-transform
- "FROM-END argument value not known at compile time")))
- ((csubtypep ctype (specifier-type 'list))
- ;; Inlining on lists is generally worthwhile.
- )
- (t
- (give-up-ir1-transform
- "sequence type not known at compile time")))))
+ ;; It's not worth trying to inline vector code unless we
+ ;; know a fair amount about it at compile time.
+ (upgraded-element-type-specifier-or-give-up sequence)
+ (unless (constant-lvar-p from-end)
+ (give-up-ir1-transform
+ "FROM-END argument value not known at compile time")))
+ ((csubtypep ctype (specifier-type 'list))
+ ;; Inlining on lists is generally worthwhile.
+ )
+ (t
+ (give-up-ir1-transform
+ "sequence type not known at compile time")))))
;;; %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for LIST data
(macrolet ((def (name condition)
- `(deftransform ,name ((predicate sequence from-end start end key)
- (function list t t t function)
- *
- :policy (> speed space))
- "expand inline"
- `(let ((index 0)
- (find nil)
- (position nil))
- (declare (type index index))
- (dolist (i sequence
- (if (and end (> end index))
- (sb!impl::signal-bounding-indices-bad-error
- sequence start end)
- (values find position)))
- (let ((key-i (funcall key i)))
- (when (and end (>= index end))
- (return (values find position)))
- (when (>= index start)
- (,',condition (funcall predicate key-i)
- ;; This hack of dealing with non-NIL
- ;; FROM-END for list data by iterating
- ;; forward through the list and keeping
- ;; track of the last time we found a match
- ;; might be more screwy than what the user
- ;; expects, but it seems to be allowed by
- ;; the ANSI standard. (And if the user is
- ;; screwy enough to ask for FROM-END
- ;; behavior on list data, turnabout is
- ;; fair play.)
- ;;
- ;; It's also not enormously efficient,
- ;; calling PREDICATE and KEY more often
- ;; than necessary; but all the
- ;; alternatives seem to have their own
- ;; efficiency problems.
- (if from-end
- (setf find i
- position index)
- (return (values i index))))))
- (incf index))))))
+ `(deftransform ,name ((predicate sequence from-end start end key)
+ (function list t t t function)
+ *
+ :policy (> speed space))
+ "expand inline"
+ `(let ((index 0)
+ (find nil)
+ (position nil))
+ (declare (type index index))
+ (dolist (i sequence
+ (if (and end (> end index))
+ (sb!impl::signal-bounding-indices-bad-error
+ sequence start end)
+ (values find position)))
+ (let ((key-i (funcall key i)))
+ (when (and end (>= index end))
+ (return (values find position)))
+ (when (>= index start)
+ (,',condition (funcall predicate key-i)
+ ;; This hack of dealing with non-NIL
+ ;; FROM-END for list data by iterating
+ ;; forward through the list and keeping
+ ;; track of the last time we found a match
+ ;; might be more screwy than what the user
+ ;; expects, but it seems to be allowed by
+ ;; the ANSI standard. (And if the user is
+ ;; screwy enough to ask for FROM-END
+ ;; behavior on list data, turnabout is
+ ;; fair play.)
+ ;;
+ ;; It's also not enormously efficient,
+ ;; calling PREDICATE and KEY more often
+ ;; than necessary; but all the
+ ;; alternatives seem to have their own
+ ;; efficiency problems.
+ (if from-end
+ (setf find i
+ position index)
+ (return (values i index))))))
+ (incf index))))))
(def %find-position-if when)
(def %find-position-if-not unless))
;;; without loss of efficiency. (I.e., the optimizer should be able
;;; to straighten everything out.)
(deftransform %find-position ((item sequence from-end start end key test)
- (t list t t t t t)
- *
- :policy (> speed space))
+ (t list t t t t t)
+ *
+ :policy (> speed space))
"expand inline"
'(%find-position-if (let ((test-fun (%coerce-callable-to-fun test)))
- ;; The order of arguments for asymmetric tests
- ;; (e.g. #'<, as opposed to order-independent
- ;; tests like #'=) is specified in the spec
- ;; section 17.2.1 -- the O/Zi stuff there.
- (lambda (i)
- (funcall test-fun item i)))
- sequence
- from-end
- start
- end
- (%coerce-callable-to-fun key)))
+ ;; The order of arguments for asymmetric tests
+ ;; (e.g. #'<, as opposed to order-independent
+ ;; tests like #'=) is specified in the spec
+ ;; section 17.2.1 -- the O/Zi stuff there.
+ (lambda (i)
+ (funcall test-fun item i)))
+ sequence
+ from-end
+ start
+ end
+ (%coerce-callable-to-fun key)))
;;; The inline expansions for the VECTOR case are saved as macros so
;;; that we can share them between the DEFTRANSFORMs and the default
;;; cases in the DEFUNs. (This isn't needed for the LIST case, because
;;; the DEFTRANSFORMs for LIST are less choosy about when to expand.)
(defun %find-position-or-find-position-if-vector-expansion (sequence-arg
- from-end
- start
- end-arg
- element
- done-p-expr)
+ from-end
+ start
+ end-arg
+ element
+ done-p-expr)
(with-unique-names (offset block index n-sequence sequence n-end end)
`(let ((,n-sequence ,sequence-arg)
- (,n-end ,end-arg))
+ (,n-end ,end-arg))
(with-array-data ((,sequence ,n-sequence :offset-var ,offset)
- (,start ,start)
- (,end (%check-vector-sequence-bounds
- ,n-sequence ,start ,n-end)))
+ (,start ,start)
+ (,end (%check-vector-sequence-bounds
+ ,n-sequence ,start ,n-end)))
(block ,block
- (macrolet ((maybe-return ()
- '(let ((,element (aref ,sequence ,index)))
- (when ,done-p-expr
- (return-from ,block
- (values ,element
- (- ,index ,offset)))))))
- (if ,from-end
- (loop for ,index
- ;; (If we aren't fastidious about declaring that
- ;; INDEX might be -1, then (FIND 1 #() :FROM-END T)
- ;; can send us off into never-never land, since
- ;; INDEX is initialized to -1.)
- of-type index-or-minus-1
- from (1- ,end) downto ,start do
- (maybe-return))
- (loop for ,index of-type index from ,start below ,end do
- (maybe-return))))
- (values nil nil))))))
+ (macrolet ((maybe-return ()
+ ;; WITH-ARRAY-DATA has already performed bounds
+ ;; checking, so we can safely elide the checks
+ ;; in the inner loop.
+ '(let ((,element (locally (declare (optimize (insert-array-bounds-checks 0)))
+ (aref ,sequence ,index))))
+ (when ,done-p-expr
+ (return-from ,block
+ (values ,element
+ (- ,index ,offset)))))))
+ (if ,from-end
+ (loop for ,index
+ ;; (If we aren't fastidious about declaring that
+ ;; INDEX might be -1, then (FIND 1 #() :FROM-END T)
+ ;; can send us off into never-never land, since
+ ;; INDEX is initialized to -1.)
+ of-type index-or-minus-1
+ from (1- ,end) downto ,start do
+ (maybe-return))
+ (loop for ,index of-type index from ,start below ,end do
+ (maybe-return))))
+ (values nil nil))))))
(def!macro %find-position-vector-macro (item sequence
- from-end start end key test)
+ from-end start end key test)
(with-unique-names (element)
(%find-position-or-find-position-if-vector-expansion
sequence
`(funcall ,test ,item (funcall ,key ,element)))))
(def!macro %find-position-if-vector-macro (predicate sequence
- from-end start end key)
+ from-end start end key)
(with-unique-names (element)
(%find-position-or-find-position-if-vector-expansion
sequence
`(funcall ,predicate (funcall ,key ,element)))))
(def!macro %find-position-if-not-vector-macro (predicate sequence
- from-end start end key)
+ from-end start end key)
(with-unique-names (element)
(%find-position-or-find-position-if-vector-expansion
sequence
;;; %FIND-POSITION, %FIND-POSITION-IF and %FIND-POSITION-IF-NOT for
;;; VECTOR data
(deftransform %find-position-if ((predicate sequence from-end start end key)
- (function vector t t t function)
- *
- :policy (> speed space))
+ (function vector t t t function)
+ *
+ :policy (> speed space))
"expand inline"
(check-inlineability-of-find-position-if sequence from-end)
'(%find-position-if-vector-macro predicate sequence
- from-end start end key))
+ from-end start end key))
(deftransform %find-position-if-not ((predicate sequence from-end start end key)
- (function vector t t t function)
- *
- :policy (> speed space))
+ (function vector t t t function)
+ *
+ :policy (> speed space))
"expand inline"
(check-inlineability-of-find-position-if sequence from-end)
'(%find-position-if-not-vector-macro predicate sequence
from-end start end key))
(deftransform %find-position ((item sequence from-end start end key test)
- (t vector t t t function function)
- *
- :policy (> speed space))
+ (t vector t t t function function)
+ *
+ :policy (> speed space))
"expand inline"
(check-inlineability-of-find-position-if sequence from-end)
'(%find-position-vector-macro item sequence
- from-end start end key test))
+ from-end start end key test))
;;; logic to unravel :TEST, :TEST-NOT, and :KEY options in FIND,
;;; POSITION-IF, etc.
(define-source-transform effective-find-position-test (test test-not)
(once-only ((test test)
- (test-not test-not))
+ (test-not test-not))
`(cond
((and ,test ,test-not)
(error "can't specify both :TEST and :TEST-NOT"))
(define-source-transform effective-find-position-key (key)
(once-only ((key key))
`(if ,key
- (%coerce-callable-to-fun ,key)
- #'identity)))
+ (%coerce-callable-to-fun ,key)
+ #'identity)))
(macrolet ((define-find-position (fun-name values-index)
- `(deftransform ,fun-name ((item sequence &key
- from-end (start 0) end
- key test test-not))
- '(nth-value ,values-index
- (%find-position item sequence
- from-end start
- end
- (effective-find-position-key key)
- (effective-find-position-test
- test test-not))))))
+ `(deftransform ,fun-name ((item sequence &key
+ from-end (start 0) end
+ key test test-not)
+ (t (or list vector) &rest t))
+ '(nth-value ,values-index
+ (%find-position item sequence
+ from-end start
+ end
+ (effective-find-position-key key)
+ (effective-find-position-test
+ test test-not))))))
(define-find-position find 0)
(define-find-position position 1))
(macrolet ((define-find-position-if (fun-name values-index)
- `(deftransform ,fun-name ((predicate sequence &key
- from-end (start 0)
- end key))
- '(nth-value
- ,values-index
- (%find-position-if (%coerce-callable-to-fun predicate)
- sequence from-end
- start end
- (effective-find-position-key key))))))
+ `(deftransform ,fun-name ((predicate sequence &key
+ from-end (start 0)
+ end key)
+ (t (or list vector) &rest t))
+ '(nth-value
+ ,values-index
+ (%find-position-if (%coerce-callable-to-fun predicate)
+ sequence from-end
+ start end
+ (effective-find-position-key key))))))
(define-find-position-if find-if 0)
(define-find-position-if position-if 1))
;;; FIXME: Maybe remove uses of these deprecated functions within the
;;; implementation of SBCL.
(macrolet ((define-find-position-if-not (fun-name values-index)
- `(deftransform ,fun-name ((predicate sequence &key
- from-end (start 0)
- end key))
- '(nth-value
- ,values-index
- (%find-position-if-not (%coerce-callable-to-fun predicate)
- sequence from-end
- start end
- (effective-find-position-key key))))))
+ `(deftransform ,fun-name ((predicate sequence &key
+ from-end (start 0)
+ end key)
+ (t (or list vector) &rest t))
+ '(nth-value
+ ,values-index
+ (%find-position-if-not (%coerce-callable-to-fun predicate)
+ sequence from-end
+ start end
+ (effective-find-position-key key))))))
(define-find-position-if-not find-if-not 0)
(define-find-position-if-not position-if-not 1))