1 ;;;; This file implements type check generation. This is a phase that
2 ;;;; runs at the very end of IR1. If a type check is too complex for
3 ;;;; the back end to directly emit in-line, then we transform the check
4 ;;;; into an explicit conditional using TYPEP.
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.
19 ;;; Return some sort of guess about the cost of a call to a function.
20 ;;; If the function has some templates, we return the cost of the
21 ;;; cheapest one, otherwise we return the cost of CALL-NAMED. Calling
22 ;;; this with functions that have transforms can result in relatively
23 ;;; meaningless results (exaggerated costs.)
25 ;;; We special-case NULL, since it does have a source tranform and is
26 ;;; interesting to us.
27 (defun fun-guessed-cost (name)
28 (declare (symbol name
))
29 (let ((info (info :function
:info name
))
30 (call-cost (template-cost (template-or-lose 'call-named
))))
32 (let ((templates (fun-info-templates info
)))
34 (template-cost (first templates
))
36 (null (template-cost (template-or-lose 'if-eq
)))
40 ;;; Return some sort of guess for the cost of doing a test against
41 ;;; TYPE. The result need not be precise as long as it isn't way out
42 ;;; in space. The units are based on the costs specified for various
43 ;;; templates in the VM definition.
44 (defun type-test-cost (type)
45 (declare (type ctype type
))
46 (or (when (eq type
*universal-type
*)
48 (when (eq type
*empty-type
*)
50 (let ((found (cdr (assoc type
*backend-type-predicates
*
53 (+ (fun-guessed-cost found
) (fun-guessed-cost 'eq
))
57 (reduce #'+ (compound-type-types type
) :key
'type-test-cost
))
59 (* (member-type-size type
)
60 (fun-guessed-cost 'eq
)))
62 (* (if (numeric-type-complexp type
) 2 1)
64 (if (csubtypep type
(specifier-type 'fixnum
)) 'fixnump
'numberp
))
66 (if (numeric-type-low type
) 1 0)
67 (if (numeric-type-high type
) 1 0))))
69 (+ (type-test-cost (specifier-type 'cons
))
70 (fun-guessed-cost 'car
)
71 (type-test-cost (cons-type-car-type type
))
72 (fun-guessed-cost 'cdr
)
73 (type-test-cost (cons-type-cdr-type type
))))
75 (fun-guessed-cost 'typep
)))))
77 (defun weaken-integer-type (type &key range-only
)
78 ;; FIXME: Our canonicalization isn't quite ideal for this. We get
81 ;; (OR (AND (SATISFIES FOO) (INTEGER -100 -50))
82 ;; (AND (SATISFIES FOO) (INTEGER 100 200)))
84 ;; here, and weakening that into
86 ;; (AND (SATISFIES FOO) (INTEGER -100 200))
88 ;; is too much work to do here ... but if we canonicalized things
89 ;; differently, we could get it for free with trivial changes here.
90 (labels ((weaken-integer-type-part (type base
)
91 (cond ((intersection-type-p type
)
92 (let ((new (specifier-type base
)))
93 (dolist (part (intersection-type-types type
))
96 (not (unknown-type-p part
)))
97 (setf new
(type-intersection
98 new
(weaken-integer-type-part part t
)))))
101 (let ((low t
) (high t
) (rest *empty-type
*))
102 (flet ((maximize (bound)
104 (setf high
(if (eq t high
)
110 (setf low
(if (eq t low
)
114 (dolist (part (union-type-types type
))
115 (let ((weak (weaken-integer-type-part part t
)))
116 (cond ((numeric-type-p weak
)
117 (minimize (numeric-type-low weak
))
118 (maximize (numeric-type-high weak
)))
120 (setf rest
(type-union rest weak
)))))))
125 `(integer ,(or low
'*) ,(or high
'*)))))))
128 (weaken-integer-type-part type
'integer
)))
131 (weaken-type :hash-bits
7 :hash-function
#'type-hash-value
)
133 (declare (type ctype type
))
134 (cond ((named-type-p type
)
136 ((csubtypep type
(specifier-type 'integer
))
137 ;; Simple range checks are not that expensive, and we *don't*
138 ;; want to accidentally lose eg. array bounds checks due to
139 ;; weakening, so for integer types we simply collapse all
141 (weaken-integer-type type
))
143 (let ((min-cost (type-test-cost type
))
146 (dolist (x *backend-type-predicates
*)
147 (let* ((stype (car x
))
148 (samep (type= stype type
)))
150 (and (csubtypep type stype
)
151 (not (union-type-p stype
))))
152 (let ((stype-cost (type-test-cost stype
)))
153 (when (or (< stype-cost min-cost
)
155 ;; If the supertype is equal in cost to the type, we
156 ;; prefer the supertype. This produces a closer
157 ;; approximation of the right thing in the presence of
161 min-cost stype-cost
))))))
162 ;; This used to return the *UNIVERSAL-TYPE* if no supertype was found,
163 ;; but that's too liberal: it's far too easy for the user to create
164 ;; a union type (which are excluded above), and then trick the compiler
165 ;; into trusting the union type... and finally ending up corrupting the
166 ;; heap once a bad object sneaks past the missing type check.
171 (defun weaken-values-type (type)
172 (declare (type ctype type
))
173 (cond ((eq type
*wild-type
*) type
)
174 ((not (values-type-p type
))
177 (make-values-type :required
(mapcar #'weaken-type
178 (values-type-required type
))
179 :optional
(mapcar #'weaken-type
180 (values-type-optional type
))
181 :rest
(acond ((values-type-rest type
)
182 (weaken-type it
)))))))
184 ;;;; checking strategy determination
186 ;;; Return the type we should test for when we really want to check
187 ;;; for TYPE. If type checking policy is "fast", then we return a
188 ;;; weaker type if it is easier to check. First we try the defined
189 ;;; type weakenings, then look for any predicate that is cheaper.
190 (defun maybe-weaken-check (type policy
)
191 (declare (type ctype type
))
192 (ecase (policy policy type-check
)
194 (2 (weaken-values-type type
))
197 ;;; LVAR is an lvar we are doing a type check on and TYPES is a list
198 ;;; of types that we are checking its values against. If we have
199 ;;; proven that LVAR generates a fixed number of values, then for each
200 ;;; value, we check whether it is cheaper to then difference between
201 ;;; the proven type and the corresponding type in TYPES.
202 (defun maybe-negate-check (lvar types original-types n-required
)
203 (declare (type lvar lvar
) (list types original-types
))
204 (let ((ptypes (values-type-out (lvar-derived-type lvar
) (length types
))))
205 (loop for p in ptypes
207 and a in original-types
209 for cc
= (if (>= i n-required
)
210 (type-union c
(specifier-type 'null
))
212 for diff
= (type-difference p cc
)
213 collect
(if (and diff
214 (< (type-test-cost diff
)
215 (type-test-cost cc
)))
219 ;;; Determine if CAST can be checked.
220 ;;; We may check only fixed number of values; in any case the number
221 ;;; of generated values is trusted. If we know the number of produced
222 ;;; values, all of them are checked; otherwise if we know the number
223 ;;; of consumed -- only they are checked; otherwise the check is not
226 ;;; In the types are checkable it returns :SIMPLE and the second value
228 ;;; (NOT-P TYPE ORIGINAL-TYPE)
230 ;;; If true, the NOT-P flag indicates a test that the corresponding
231 ;;; value is *not* of the specified TYPE. ORIGINAL-TYPE is the type
232 ;;; asserted on this value in the lvar, for use in error
233 ;;; messages. When NOT-P is true, this will be different from TYPE.
235 ;;; This allows us to take what has been proven about CAST's argument
236 ;;; type into consideration. If it is cheaper to test for the
237 ;;; difference between the derived type and the asserted type, then we
238 ;;; check for the negation of this type instead.
239 (defun cast-check-types (cast)
240 (declare (type cast cast
))
241 (let* ((ctype (coerce-to-values (cast-type-to-check cast
)))
242 (atype (coerce-to-values (cast-asserted-type cast
)))
243 (dtype (node-derived-type cast
))
244 (value (cast-value cast
))
245 (lvar (node-lvar cast
))
246 (dest (and lvar
(lvar-dest lvar
)))
247 (n-consumed (cond ((not lvar
)
249 ((lvar-single-value-p lvar
)
251 ((and (mv-combination-p dest
)
252 (eq (mv-combination-kind dest
) :local
)
253 (lvar-uses (mv-combination-fun dest
))
254 (singleton-p (mv-combination-args dest
)))
255 (let ((fun-ref (lvar-use (mv-combination-fun dest
))))
256 (length (lambda-vars (ref-leaf fun-ref
)))))))
257 (n-required (length (values-type-required dtype
))))
258 (aver (not (eq ctype
*wild-type
*)))
259 (cond ((and (null (values-type-optional dtype
))
260 (not (values-type-rest dtype
)))
261 ;; we [almost] know how many values are produced
263 (maybe-negate-check value
264 (values-type-out ctype n-required
)
265 (values-type-out atype n-required
)
267 ((lvar-single-value-p lvar
)
268 ;; exactly one value is consumed
269 (principal-lvar-single-valuify lvar
)
270 (flet ((get-type (type)
271 (acond ((args-type-required type
)
273 ((args-type-optional type
)
275 (t (bug "type ~S is too hairy" type
)))))
276 (values :simple
(maybe-negate-check value
277 (list (get-type ctype
))
278 (list (get-type atype
))
280 ((and (mv-combination-p dest
)
281 (eq (mv-combination-kind dest
) :local
)
282 (singleton-p (mv-combination-args dest
)))
283 ;; we know the number of consumed values
284 (values :simple
(maybe-negate-check value
285 (adjust-list (values-type-types ctype
)
288 (adjust-list (values-type-types atype
)
293 (values :too-hairy nil
)))))
295 ;;; Return T is the cast appears to be from the declaration of the callee,
296 ;;; and should be checked externally -- that is, by the callee and not the caller.
297 (defun cast-externally-checkable-p (cast)
298 (declare (type cast cast
))
299 (let* ((lvar (node-lvar cast
))
300 (dest (and lvar
(lvar-dest lvar
))))
301 (and (combination-p dest
)
302 ;; The theory is that the type assertion is from a declaration on the
303 ;; callee, so the callee should be able to do the check. We want to
304 ;; let the callee do the check, because it is possible that by the
305 ;; time of call that declaration will be changed and we do not want
306 ;; to make people recompile all calls to a function when they were
307 ;; originally compiled with a bad declaration.
309 ;; ALMOST-IMMEDIATELY-USED-P ensures that we don't delegate casts
310 ;; that occur before nodes that can cause observable side effects --
311 ;; most commonly other non-external casts: so the order in which
312 ;; possible type errors are signalled matches with the evaluation
315 ;; FIXME: We should let more cases be handled by the callee then we
316 ;; currently do, see: https://bugs.launchpad.net/sbcl/+bug/309104
317 ;; This is not fixable quite here, though, because flow-analysis has
318 ;; deleted the LVAR of the cast by the time we get here, so there is
319 ;; no destination. Perhaps we should mark cases inserted by
320 ;; ASSERT-CALL-TYPE explicitly, and delete those whose destination is
321 ;; deemed unreachable?
322 (almost-immediately-used-p lvar cast
)
323 (values (values-subtypep (lvar-externally-checkable-type lvar
)
324 (cast-type-to-check cast
))))))
326 ;; Type specifiers handled by the general-purpose MAKE-TYPE-CHECK-FORM are often
327 ;; trivial enough to have an internal error number assigned to them that can be
328 ;; used in lieu of OBJECT-NOT-TYPE-ERROR. On x86-64 this saves 16 bytes: 1 word
329 ;; for the symbol in the function's constant area, a MOV instruction to load it,
330 ;; and an sc-offset in the error trap.
331 (defglobal **type-spec-interr-symbols
**
333 ;; read-time-eval so that during cold-init we can recreate the
334 ;; table using the target's sxhash function, but without relying
335 ;; on readiness of the type system for parsing/unparsing specifiers.
338 (cons (type-specifier (specifier-type (car entry
)))
340 (remove-if #'stringp sb
!c
:+backend-internal-errors
+
342 ;; This is effectively a compact read-only binned hashtable.
343 (hashtable (make-array (logior (length entries
) 1)
344 :initial-element nil
)))
347 (let* ((canon-type (car entry
))
348 (bucket (mod (sxhash canon-type
) (length hashtable
))))
349 (push entry
(svref hashtable bucket
))))
352 (defun %interr-symbol-for-type-spec
(spec)
353 (let ((table **type-spec-interr-symbols
**))
354 (cadr (assoc spec
(svref table
(rem (sxhash spec
) (length table
)))
356 #+nil
; some meta-analysis to decide what types should be in "generic/interr"
358 (defvar *checkgen-used-types
* (make-hash-table :test
'equal
))
359 (defun interr-symbol-for-type-spec (spec)
360 (let ((answer (%interr-symbol-for-type-spec spec
))
361 (meta (gethash spec
*checkgen-used-types
*)))
362 ;; spec -> (count . primitive-p)
365 (setf (gethash spec
*checkgen-used-types
*) (cons 1 answer
)))
368 ;;; Return a lambda form that we can convert to do a type check
369 ;;; of the specified TYPES. TYPES is a list of the format returned by
370 ;;; CAST-CHECK-TYPES.
372 ;;; Note that we don't attempt to check for required values being
373 ;;; unsupplied. Such checking is impossible to efficiently do at the
374 ;;; source level because our fixed-values conventions are optimized
375 ;;; for the common MV-BIND case.
376 (defun make-type-check-form (types)
377 (let ((temps (make-gensym-list (length types
))))
378 `(multiple-value-bind ,temps
'dummy
379 ,@(mapcar (lambda (temp type
)
381 (let ((*unparse-fun-type-simplify
* t
))
382 (type-specifier (second type
))))
383 (test (if (first type
) `(not ,spec
) spec
))
384 (external-spec (type-specifier (third type
)))
386 (%interr-symbol-for-type-spec external-spec
)))
387 `(unless (typep ,temp
',test
)
389 `(%type-check-error
/c
,temp
',interr-symbol
)
390 `(%type-check-error
,temp
',external-spec
)))))
395 ;;; Splice in explicit type check code immediately before CAST. This
396 ;;; code receives the value(s) that were being passed to CAST-VALUE,
397 ;;; checks the type(s) of the value(s), then passes them further.
398 (defun convert-type-check (cast types
)
399 (declare (type cast cast
) (type list types
))
400 (let ((value (cast-value cast
))
401 (length (length types
)))
402 (filter-lvar value
(make-type-check-form types
))
403 (reoptimize-lvar (cast-value cast
))
404 (setf (cast-type-to-check cast
) *wild-type
*)
405 (setf (cast-%type-check cast
) nil
)
406 (let* ((atype (cast-asserted-type cast
))
407 (atype (cond ((not (values-type-p atype
))
410 (single-value-type atype
))
413 :required
(values-type-out atype length
)))))
414 (dtype (node-derived-type cast
))
415 (dtype (make-values-type
416 :required
(values-type-out dtype length
))))
417 (setf (cast-asserted-type cast
) atype
)
418 (setf (node-derived-type cast
) dtype
)))
422 ;;; Check all possible arguments of CAST and emit type warnings for
423 ;;; those with type errors. If the value of USE is being used for a
424 ;;; variable binding, we figure out which one for source context. If
425 ;;; the value is a constant, we print it specially.
426 (defun cast-check-uses (cast)
427 (declare (type cast cast
))
428 (let* ((lvar (node-lvar cast
))
429 (dest (and lvar
(lvar-dest lvar
)))
430 (value (cast-value cast
))
431 (atype (cast-asserted-type cast
))
432 (condition 'type-warning
)
435 (let ((dtype (node-derived-type use
)))
436 (if (values-types-equal-or-intersect dtype atype
)
437 (setf condition
'type-style-warning
)
438 (push use not-ok-uses
))))
439 (dolist (use (nreverse not-ok-uses
))
440 (let* ((*compiler-error-context
* use
)
441 (dtype (node-derived-type use
))
442 (what (when (and (combination-p dest
)
443 (eq (combination-kind dest
) :local
))
444 (let ((lambda (combination-lambda dest
))
445 (pos (position-or-lose
446 lvar
(combination-args dest
))))
447 (format nil
"~:[A possible~;The~] binding of ~S"
448 (and (lvar-has-single-use-p lvar
)
449 (eq (functional-kind lambda
) :let
))
450 (leaf-source-name (elt (lambda-vars lambda
)
452 (cond ((and (ref-p use
) (constant-p (ref-leaf use
)))
454 :format-control
"~:[This~;~:*~A~] is not a ~
455 ~<~%~9T~:;~/sb!impl:print-type/:~>~% ~S"
457 (list what atype
(constant-value (ref-leaf use
)))))
461 "~:[Result~;~:*~A~] is a ~/sb!impl:print-type/, ~
462 ~<~%~9T~:;not a ~/sb!impl:print-type/.~>"
463 :format-arguments
(list what dtype atype
)))))))
466 ;;; Loop over all blocks in COMPONENT that have TYPE-CHECK set,
467 ;;; looking for CASTs with TYPE-CHECK T. We do two mostly unrelated
468 ;;; things: detect compile-time type errors and determine if and how
469 ;;; to do run-time type checks.
471 ;;; If there is a compile-time type error, then we mark the CAST and
472 ;;; emit a warning if appropriate. This part loops over all the uses
473 ;;; of the continuation, since after we convert the check, the
474 ;;; :DELETED kind will inhibit warnings about the types of other uses.
476 ;;; If the cast is too complex to be checked by the back end, or is
477 ;;; better checked with explicit code, then convert to an explicit
478 ;;; test. Assertions that can checked by the back end are passed
479 ;;; through. Assertions that can't be tested are flamed about and
480 ;;; marked as not needing to be checked.
482 ;;; If we determine that a type check won't be done, then we set
483 ;;; TYPE-CHECK to :NO-CHECK. In the non-hairy cases, this is just to
484 ;;; prevent us from wasting time coming to the same conclusion again
485 ;;; on a later iteration. In the hairy case, we must indicate to LTN
486 ;;; that it must choose a safe implementation, since IR2 conversion
487 ;;; will choke on the check.
489 ;;; The generation of the type checks is delayed until all the type
490 ;;; check decisions have been made because the generation of the type
491 ;;; checks creates new nodes whose derived types aren't always updated
492 ;;; which may lead to inappropriate template choices due to the
493 ;;; modification of argument types.
494 (defun generate-type-checks (component)
496 (do-blocks (block component
)
497 (when (and (block-type-check block
)
498 (not (block-delete-p block
)))
499 ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass
500 (do-nodes-backwards (node nil block
)
501 (when (and (cast-p node
)
502 (cast-type-check node
))
503 (cast-check-uses node
)
504 (cond ((cast-externally-checkable-p node
)
505 (setf (cast-%type-check node
) :external
))
507 ;; it is possible that NODE was marked :EXTERNAL by
509 (setf (cast-%type-check node
) t
)
511 (setf (block-type-check block
) nil
)))
512 (dolist (cast (casts))
513 (unless (bound-cast-p cast
)
514 (multiple-value-bind (check types
) (cast-check-types cast
)
517 (convert-type-check cast types
))
519 (let ((*compiler-error-context
* cast
))
520 (when (policy cast
(>= safety inhibit-warnings
))
522 "type assertion too complex to check:~%~
523 ~/sb!impl:print-type/."
524 (coerce-to-values (cast-asserted-type cast
)))))
525 (setf (cast-type-to-check cast
) *wild-type
*)
526 (setf (cast-%type-check cast
) nil
)))))))