1 ;;;; This file contains stuff for maintaining a database of special
2 ;;;; information about functions known to the compiler. This includes
3 ;;;; semantic information such as side effects and type inference
4 ;;;; functions as well as transforms and IR2 translators.
6 ;;;; This software is part of the SBCL system. See the README file for
9 ;;;; This software is derived from the CMU CL system, which was
10 ;;;; written at Carnegie Mellon University and released into the
11 ;;;; public domain. The software is in the public domain and is
12 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
13 ;;;; files for more information.
17 (/show0
"knownfun.lisp 17")
19 ;;;; interfaces to defining macros
22 (defstruct (transform (:copier nil
))
23 ;; the function type which enables this transform.
25 ;; (Note that declaring this :TYPE FUN-TYPE probably wouldn't
26 ;; work because some function types, like (SPECIFIER-TYPE 'FUNCTION0
27 ;; itself, are represented as BUILT-IN-TYPE, and at least as of
28 ;; sbcl-0.pre7.54 or so, that's inconsistent with being a
30 (type (missing-arg) :type ctype
)
31 ;; the transformation function. Takes the COMBINATION node and
32 ;; returns a lambda expression, or throws out.
33 (function (missing-arg) :type function
)
34 ;; string used in efficiency notes
35 (note (missing-arg) :type string
)
36 ;; T if we should emit a failure note even if SPEED=INHIBIT-WARNINGS.
37 (important nil
:type
(member nil
:slightly t
))
38 ;; A function with NODE as an argument that checks wheteher the
39 ;; transform applies in its policy.
40 ;; It used to be checked in the FUNCTION body but it would produce
41 ;; notes about failed transformation due to types even though it
42 ;; wouldn't have been applied with the right types anyway,
43 ;; or if another transform could be applied with the right policy.
44 (policy nil
:type
(or null function
)))
46 (defprinter (transform) type note important
)
48 ;;; Grab the FUN-INFO and enter the function, replacing any old
49 ;;; one with the same type and note.
50 (defun %deftransform
(name type fun
&optional note important policy
)
51 (let* ((ctype (specifier-type type
))
52 (note (or note
"optimize"))
53 (info (fun-info-or-lose name
))
54 (old (find-if (lambda (x)
55 (and (type= (transform-type x
) ctype
)
56 (string-equal (transform-note x
) note
)
57 (eq (transform-important x
) important
)))
58 (fun-info-transforms info
))))
60 (style-warn 'redefinition-with-deftransform
62 (setf (transform-function old
) fun
63 (transform-note old
) note
))
65 (push (make-transform :type ctype
:function fun
:note note
68 (fun-info-transforms info
))))
71 ;;; Make a FUN-INFO structure with the specified type, attributes
73 (defun %defknown
(names type attributes location
74 &key derive-type optimizer destroyed-constant-args result-arg
75 overwrite-fndb-silently
80 (let ((ctype (specifier-type type
)))
82 (unless overwrite-fndb-silently
83 (let ((old-fun-info (info :function
:info name
)))
85 ;; This is handled as an error because it's generally a bad
86 ;; thing to blow away all the old optimization stuff. It's
87 ;; also a potential source of sneaky bugs:
90 ;; DEFKNOWN FOO ; possibly hidden inside some macroexpansion
91 ;; ; Now the DEFTRANSFORM doesn't exist in the target Lisp.
92 ;; However, it's continuable because it might be useful to do
93 ;; it when testing new optimization stuff interactively.
94 (cerror "Go ahead, overwrite it."
95 "~@<overwriting old FUN-INFO ~2I~_~S ~I~_for ~S~:>"
97 (setf (info :function
:type name
) ctype
)
98 (setf (info :function
:where-from name
) :declared
)
99 (setf (info :function
:kind name
) :function
)
100 (setf (info :function
:info name
)
101 (make-fun-info :attributes attributes
102 :derive-type derive-type
104 :destroyed-constant-args destroyed-constant-args
105 :result-arg result-arg
106 :foldable-call-check foldable-call-check
107 :callable-check callable-check
108 :call-type-deriver call-type-deriver
109 :functional-args functional-args
))
111 (setf (getf (info :source-location
:declaration name
) 'defknown
)
113 (remf (info :source-location
:declaration name
) 'defknown
))))
116 ;;; Return the FUN-INFO for NAME or die trying.
117 (declaim (ftype (sfunction (t) fun-info
) fun-info-or-lose
))
118 (defun fun-info-or-lose (name)
119 (or (info :function
:info name
) (error "~S is not a known function." name
)))
121 ;;;; generic type inference methods
123 ;;; Derive the type to be the type of the xxx'th arg. This can normally
124 ;;; only be done when the result value is that argument.
125 (defun result-type-first-arg (call)
126 (declare (type combination call
))
127 (let ((lvar (first (combination-args call
))))
128 (when lvar
(lvar-type lvar
))))
129 (defun result-type-last-arg (call)
130 (declare (type combination call
))
131 (let ((lvar (car (last (combination-args call
)))))
132 (when lvar
(lvar-type lvar
))))
134 ;;; Derive the result type according to the float contagion rules, but
135 ;;; always return a float. This is used for irrational functions that
136 ;;; preserve realness of their arguments.
137 (defun result-type-float-contagion (call)
138 (declare (type combination call
))
139 (reduce #'numeric-contagion
(combination-args call
)
141 :initial-value
(specifier-type 'single-float
)))
143 (defun simplify-list-type (type &key preserve-dimensions
)
144 ;; Preserve all the list types without dragging
145 ;; (cons (eql 10)) stuff in.
146 (let ((cons-type (specifier-type 'cons
))
147 (list-type (specifier-type 'list
))
148 (null-type (specifier-type 'null
)))
149 (cond ((and preserve-dimensions
150 (csubtypep type cons-type
))
152 ((and preserve-dimensions
153 (csubtypep type null-type
))
155 ((csubtypep type list-type
)
158 ;;; Return a closure usable as a derive-type method for accessing the
159 ;;; N'th argument. If arg is a list, result is a list. If arg is a
160 ;;; vector, result is a vector with the same element type.
161 (defun sequence-result-nth-arg (n &key preserve-dimensions
162 preserve-vector-type
)
164 (declare (type combination call
))
165 (let ((lvar (nth (1- n
) (combination-args call
))))
167 (let ((type (lvar-type lvar
)))
168 (cond ((simplify-list-type type
169 :preserve-dimensions preserve-dimensions
))
170 ((not (csubtypep type
(specifier-type 'vector
)))
172 (preserve-vector-type
175 (let ((simplified (simplify-vector-type type
)))
176 (if (and preserve-dimensions
177 (csubtypep simplified
(specifier-type 'simple-array
)))
178 (type-intersection (specifier-type
179 `(simple-array * ,(ctype-array-dimensions type
)))
183 ;;; Derive the type to be the type specifier which is the Nth arg.
184 (defun result-type-specifier-nth-arg (n)
186 (declare (type combination call
))
187 (let ((lvar (nth (1- n
) (combination-args call
))))
188 (when (and lvar
(constant-lvar-p lvar
))
189 (careful-specifier-type (lvar-value lvar
))))))
191 ;;; Derive the type to be the type specifier which is the Nth arg,
192 ;;; with the additional restriptions noted in the CLHS for STRING and
193 ;;; SIMPLE-STRING, defined to specialize on CHARACTER, and for VECTOR
194 ;;; (under the page for MAKE-SEQUENCE).
195 ;;; At present this is used to derive the output type of CONCATENATE,
196 ;;; MAKE-SEQUENCE, and MERGE. Two things seem slightly amiss:
197 ;;; 1. The sequence type actually produced might not be exactly that specified.
198 ;;; (TYPE-OF (MAKE-SEQUENCE '(AND (NOT SIMPLE-ARRAY) (VECTOR BIT)) 9))
199 ;;; => (SIMPLE-BIT-VECTOR 9)
200 ;;; 2. Because we *know* that a hairy array won't be produced,
201 ;;; why does derivation preserve the non-simpleness, if so specified?
202 (defun creation-result-type-specifier-nth-arg (n)
204 (declare (type combination call
))
205 (let ((lvar (nth (1- n
) (combination-args call
))))
206 (when (and lvar
(constant-lvar-p lvar
))
207 (let* ((specifier (lvar-value lvar
))
208 (lspecifier (if (atom specifier
) (list specifier
) specifier
)))
210 ((eq (car lspecifier
) 'string
)
211 (destructuring-bind (string &rest size
)
213 (declare (ignore string
))
214 (careful-specifier-type
215 `(vector character
,@(when size size
)))))
216 ((eq (car lspecifier
) 'simple-string
)
217 (destructuring-bind (simple-string &rest size
)
219 (declare (ignore simple-string
))
220 (careful-specifier-type
221 `(simple-array character
,@(if size
(list size
) '((*)))))))
223 (let ((ctype (careful-specifier-type specifier
)))
224 (cond ((not (array-type-p ctype
))
226 ((unknown-type-p (array-type-element-type ctype
))
227 (make-array-type (array-type-dimensions ctype
)
228 :complexp
(array-type-complexp ctype
)
229 :element-type
*wild-type
*
230 :specialized-element-type
*wild-type
*))
231 ((eq (array-type-specialized-element-type ctype
)
233 (make-array-type (array-type-dimensions ctype
)
234 :complexp
(array-type-complexp ctype
)
235 :element-type
*universal-type
*
236 :specialized-element-type
*universal-type
*))
240 (defun remove-non-constants-and-nils (fun)
242 (remove-if-not #'lvar-value
243 (remove-if-not #'constant-lvar-p
(funcall fun list
)))))
245 ;;; FIXME: bad name (first because it uses 1-based indexing; second
246 ;;; because it doesn't get the nth constant arguments)
247 (defun nth-constant-args (&rest indices
)
251 (list list
(cdr list
))
253 ((null indices
) (nreverse result
))
254 (when (= i
(car indices
))
255 (when (constant-lvar-p (car list
))
256 (push (car list
) result
))
257 (setf indices
(cdr indices
)))))))
259 ;;; FIXME: a number of the sequence functions not only do not destroy
260 ;;; their argument if it is empty, but also leave it alone if :start
261 ;;; and :end bound a null sequence, or if :count is 0. This test is a
262 ;;; bit complicated to implement, verging on the impossible, but for
263 ;;; extra points (fill #\1 "abc" :start 0 :end 0) should not cause a
265 (defun nth-constant-nonempty-sequence-args (&rest indices
)
269 (list list
(cdr list
))
271 ((null indices
) (nreverse result
))
272 (when (= i
(car indices
))
273 (when (constant-lvar-p (car list
))
274 (let ((value (lvar-value (car list
))))
275 (unless (or (typep value
'null
)
276 (typep value
'(vector * 0)))
277 (push (car list
) result
))))
278 (setf indices
(cdr indices
)))))))
280 (defun read-elt-type-deriver (skip-arg-p element-type-spec no-hang
)
282 (let* ((element-type (specifier-type element-type-spec
))
283 (null-type (specifier-type 'null
))
284 (err-args (if skip-arg-p
; for PEEK-CHAR, skip 'peek-type' + 'stream'
285 (cddr (combination-args call
))
286 (cdr (combination-args call
)))) ; else just 'stream'
287 (eof-error-p (first err-args
))
288 (eof-value (second err-args
))
289 (unexceptional-type ; the normally returned thing
291 (types-equal-or-intersect (lvar-type eof-error-p
)
293 ;; (READ-elt stream nil <x>) returns (OR (EQL <x>) elt-type)
294 (type-union (if eof-value
(lvar-type eof-value
) null-type
)
296 ;; If eof-error is unsupplied, or was but couldn't be nil
299 (type-union unexceptional-type null-type
)
300 unexceptional-type
))))
303 (defun sequence-lvar-dimensions (lvar)
304 (if (not (constant-lvar-p lvar
))
305 (let ((max 0) (min array-total-size-limit
))
307 (labels ((max-dim (type)
308 ;; This can deal with just enough hair to handle type STRING,
309 ;; but might be made to use GENERIC-ABSTRACT-TYPE-FUNCTION
310 ;; if we really want to be more clever.
313 (mapc #'max-dim
(union-type-types type
)))
314 (array-type (if (array-type-complexp type
)
316 (process-dim (array-type-dimensions type
))))
319 (let ((length (car dim
)))
320 (if (and (singleton-p dim
)
322 (setf max
(max max length
)
323 min
(min min length
))
325 ;; If type derivation were able to notice that non-simple arrays can
326 ;; be mutated (changing the type), we could safely use LVAR-TYPE on
327 ;; any vector type. But it doesn't notice.
328 ;; We could use LVAR-CONSERVATIVE-TYPE to get a conservative answer.
329 ;; However that's probably not an important use, so the above
330 ;; logic restricts itself to simple arrays.
331 (max-dim (lvar-type lvar
))
333 (let ((value (lvar-value lvar
)))
334 (and (typep value
'sequence
)
335 (let ((length (length value
)))
336 (values length length
))))))
338 (defun position-derive-type (call)
339 (let ((dim (sequence-lvar-dimensions (second (combination-args call
)))))
341 (specifier-type `(or (integer 0 (,dim
)) null
)))))
343 (defun count-derive-type (call)
344 (let ((dim (sequence-lvar-dimensions (second (combination-args call
)))))
346 (specifier-type `(integer 0 ,dim
)))))
348 ;;; This used to be done in DEFOPTIMIZER DERIVE-TYPE, but
349 ;;; ASSERT-CALL-TYPE already asserts the ARRAY type, so it gets an extra
350 ;;; assertion that may not get eliminated and requires extra work.
351 (defun array-call-type-deriver (call trusted
)
352 (let ((type (lvar-type (combination-fun call
)))
353 (policy (lexenv-policy (node-lexenv call
)))
354 (args (combination-args call
)))
355 (flet ((assert-type (arg type
)
356 (when (assert-lvar-type arg type policy
)
357 (unless trusted
(reoptimize-lvar arg
)))))
358 (loop for
(type . next
) on
(fun-type-required type
)
360 do
(assert-type (pop args
) type
))
361 (assert-type (pop args
)
362 (specifier-type `(array * ,(make-list (length args
)
363 :initial-element
'*))))
364 (loop for subscript in args
365 do
(assert-type subscript
(fun-type-rest type
))))))
367 (/show0
"knownfun.lisp end of file")