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 ((check (type-check-template type
)))
53 (let ((found (cdr (assoc type
*backend-type-predicates
*
56 (+ (fun-guessed-cost found
) (fun-guessed-cost 'eq
))
60 (reduce #'+ (compound-type-types type
) :key
'type-test-cost
))
62 (* (member-type-size type
)
63 (fun-guessed-cost 'eq
)))
65 (* (if (numeric-type-complexp type
) 2 1)
67 (if (csubtypep type
(specifier-type 'fixnum
)) 'fixnump
'numberp
))
69 (if (numeric-type-low type
) 1 0)
70 (if (numeric-type-high type
) 1 0))))
72 (+ (type-test-cost (specifier-type 'cons
))
73 (fun-guessed-cost 'car
)
74 (type-test-cost (cons-type-car-type type
))
75 (fun-guessed-cost 'cdr
)
76 (type-test-cost (cons-type-cdr-type type
))))
78 (fun-guessed-cost 'typep
)))))
81 (weaken-type :hash-bits
8
82 :hash-function
(lambda (x)
83 (logand (type-hash-value x
) #xFF
)))
85 (declare (type ctype type
))
86 (let ((min-cost (type-test-cost type
))
89 (dolist (x *backend-type-predicates
*)
90 (let* ((stype (car x
))
91 (samep (type= stype type
)))
93 (and (csubtypep type stype
)
94 (not (union-type-p stype
))))
95 (let ((stype-cost (type-test-cost stype
)))
96 (when (or (< stype-cost min-cost
)
98 ;; If the supertype is equal in cost to the type, we
99 ;; prefer the supertype. This produces a closer
100 ;; approximation of the right thing in the presence of
104 min-cost stype-cost
))))))
105 ;; This used to return the *UNIVERSAL-TYPE* if no supertype was found,
106 ;; but that's too liberal: it's far too easy for the user to create
107 ;; a union type (which are excluded above), and then trick the compiler
108 ;; into trusting the union type... and finally ending up corrupting the
109 ;; heap once a bad object sneaks past the missing type check.
114 (defun weaken-values-type (type)
115 (declare (type ctype type
))
116 (cond ((eq type
*wild-type
*) type
)
117 ((not (values-type-p type
))
120 (make-values-type :required
(mapcar #'weaken-type
121 (values-type-required type
))
122 :optional
(mapcar #'weaken-type
123 (values-type-optional type
))
124 :rest
(acond ((values-type-rest type
)
125 (weaken-type it
)))))))
127 ;;;; checking strategy determination
129 ;;; Return the type we should test for when we really want to check
130 ;;; for TYPE. If type checking policy is "fast", then we return a
131 ;;; weaker type if it is easier to check. First we try the defined
132 ;;; type weakenings, then look for any predicate that is cheaper.
133 (defun maybe-weaken-check (type policy
)
134 (declare (type ctype type
))
135 (ecase (policy policy type-check
)
137 (2 (weaken-values-type type
))
140 ;;; This is like VALUES-TYPES, only we mash any complex function types
142 (defun no-fun-values-types (type)
143 (declare (type ctype type
))
144 (multiple-value-bind (res count
) (values-types type
)
145 (values (mapcar (lambda (type)
146 (if (fun-type-p type
)
147 (specifier-type 'function
)
152 ;;; Switch to disable check complementing, for evaluation.
153 (defvar *complement-type-checks
* t
)
155 ;;; LVAR is an lvar we are doing a type check on and TYPES is a list
156 ;;; of types that we are checking its values against. If we have
157 ;;; proven that LVAR generates a fixed number of values, then for each
158 ;;; value, we check whether it is cheaper to then difference between
159 ;;; the proven type and the corresponding type in TYPES. If so, we opt
160 ;;; for a :HAIRY check with that test negated. Otherwise, we try to do
161 ;;; a simple test, and if that is impossible, we do a hairy test with
162 ;;; non-negated types. If true, FORCE-HAIRY forces a hairy type check.
164 ;;; When doing a non-negated check, we call MAYBE-WEAKEN-CHECK to
165 ;;; weaken the test to a convenient supertype (conditional on policy.)
166 ;;; If SPEED is 3, or DEBUG-INFO is not particularly important (DEBUG
167 ;;; <= 1), then we allow weakened checks to be simple, resulting in
168 ;;; less informative error messages, but saving space and possibly
171 ;;; FIXME: I don't quite understand this, but it looks as though
172 ;;; that means type checks are weakened when SPEED=3 regardless of
173 ;;; the SAFETY level, which is not the right thing to do.
174 (defun maybe-negate-check (lvar types original-types force-hairy n-required
)
175 (declare (type lvar lvar
) (list types original-types
))
176 (let ((ptypes (values-type-out (lvar-derived-type lvar
) (length types
))))
177 (multiple-value-bind (hairy-res simple-res
)
178 (loop for p in ptypes
180 and a in original-types
182 for cc
= (if (>= i n-required
)
183 (type-union c
(specifier-type 'null
))
185 for diff
= (type-difference p cc
)
186 collect
(if (and diff
187 (< (type-test-cost diff
)
189 *complement-type-checks
*)
193 collect cc into simple-res
194 finally
(return (values hairy-res simple-res
)))
195 (cond ((or force-hairy
(find-if #'first hairy-res
))
196 (values :hairy hairy-res
))
197 ((every #'type-check-template simple-res
)
198 (values :simple simple-res
))
200 (values :hairy hairy-res
))))))
202 ;;; Determines whether CAST's assertion is:
203 ;;; -- checkable by the back end (:SIMPLE), or
204 ;;; -- not checkable by the back end, but checkable via an explicit
205 ;;; test in type check conversion (:HAIRY), or
206 ;;; -- not reasonably checkable at all (:TOO-HAIRY).
208 ;;; We may check only fixed number of values; in any case the number
209 ;;; of generated values is trusted. If we know the number of produced
210 ;;; values, all of them are checked; otherwise if we know the number
211 ;;; of consumed -- only they are checked; otherwise the check is not
214 ;;; A type is simply checkable if all the type assertions have a
215 ;;; TYPE-CHECK-TEMPLATE. In this :SIMPLE case, the second value is a
216 ;;; list of the type restrictions specified for the leading positional
221 ;;; We force a check to be hairy even when there are fixed values
222 ;;; if we are in a context where we may be forced to use the
223 ;;; unknown values convention anyway. This is because IR2tran can't
224 ;;; generate type checks for unknown values lvars but people could
225 ;;; still be depending on the check being done. We only care about
226 ;;; EXIT and RETURN (not MV-COMBINATION) since these are the only
227 ;;; contexts where the ultimate values receiver
229 ;;; In the :HAIRY case, the second value is a list of triples of
231 ;;; (NOT-P TYPE ORIGINAL-TYPE)
233 ;;; If true, the NOT-P flag indicates a test that the corresponding
234 ;;; value is *not* of the specified TYPE. ORIGINAL-TYPE is the type
235 ;;; asserted on this value in the lvar, for use in error
236 ;;; messages. When NOT-P is true, this will be different from TYPE.
238 ;;; This allows us to take what has been proven about CAST's argument
239 ;;; type into consideration. If it is cheaper to test for the
240 ;;; difference between the derived type and the asserted type, then we
241 ;;; check for the negation of this type instead.
242 (defun cast-check-types (cast force-hairy
)
243 (declare (type cast cast
))
244 (let* ((ctype (coerce-to-values (cast-type-to-check cast
)))
245 (atype (coerce-to-values (cast-asserted-type cast
)))
246 (dtype (node-derived-type cast
))
247 (value (cast-value cast
))
248 (lvar (node-lvar cast
))
249 (dest (and lvar
(lvar-dest lvar
)))
250 (n-consumed (cond ((not lvar
)
252 ((lvar-single-value-p lvar
)
254 ((and (mv-combination-p dest
)
255 (eq (mv-combination-kind dest
) :local
))
256 (let ((fun-ref (lvar-use (mv-combination-fun dest
))))
257 (length (lambda-vars (ref-leaf fun-ref
)))))))
258 (n-required (length (values-type-required dtype
))))
259 (aver (not (eq ctype
*wild-type
*)))
260 (cond ((and (null (values-type-optional dtype
))
261 (not (values-type-rest dtype
)))
262 ;; 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
)
266 ;; backend checks only consumed values
267 (not (eql n-required n-consumed
))
269 ((lvar-single-value-p lvar
)
270 ;; exactly one value is consumed
271 (principal-lvar-single-valuify lvar
)
272 (flet ((get-type (type)
273 (acond ((args-type-required type
)
275 ((args-type-optional type
)
277 (t (bug "type ~S is too hairy" type
)))))
278 (multiple-value-bind (ctype atype
)
279 (values (get-type ctype
) (get-type atype
))
280 (maybe-negate-check value
281 (list ctype
) (list atype
)
284 ((and (mv-combination-p dest
)
285 (eq (mv-combination-kind dest
) :local
))
286 ;; we know the number of consumed values
287 (maybe-negate-check value
288 (adjust-list (values-type-types ctype
)
291 (adjust-list (values-type-types atype
)
297 (values :too-hairy nil
)))))
299 ;;; Do we want to do a type check?
300 (defun cast-externally-checkable-p (cast)
301 (declare (type cast cast
))
302 (let* ((lvar (node-lvar cast
))
303 (dest (and lvar
(lvar-dest lvar
))))
304 (and (combination-p dest
)
305 ;; The theory is that the type assertion is from a
306 ;; declaration in (or on) the callee, so the callee should be
307 ;; able to do the check. We want to let the callee do the
308 ;; check, because it is possible that by the time of call
309 ;; that declaration will be changed and we do not want to
310 ;; make people recompile all calls to a function when they
311 ;; were originally compiled with a bad declaration. (See also
313 (or (immediately-used-p lvar cast
)
314 (binding* ((ctran (node-next cast
) :exit-if-null
)
315 (next (ctran-next ctran
)))
317 (eq (node-dest next
) dest
)
318 (eq (cast-type-check next
) :external
))))
319 (values-subtypep (lvar-externally-checkable-type lvar
)
320 (cast-type-to-check cast
)))))
322 ;;; Return true if CAST's value is an lvar whose type the back end is
323 ;;; likely to want to check. Since we don't know what template the
324 ;;; back end is going to choose to implement the continuation's DEST,
325 ;;; we use a heuristic. We always return T unless:
326 ;;; -- nobody uses the value, or
327 ;;; -- safety is totally unimportant, or
328 ;;; -- the lvar is an argument to an unknown function, or
329 ;;; -- the lvar is an argument to a known function that has
330 ;;; no IR2-CONVERT method or :FAST-SAFE templates that are
331 ;;; compatible with the call's type.
332 (defun probable-type-check-p (cast)
333 (declare (type cast cast
))
334 (let* ((lvar (node-lvar cast
))
335 (dest (and lvar
(lvar-dest lvar
))))
336 (cond ((not dest
) nil
)
339 (cond ((or (not dest
)
340 (policy dest
(zerop safety
)))
342 ((basic-combination-p dest
)
343 (let ((kind (basic-combination-kind dest
)))
345 ((eq cont
(basic-combination-fun dest
)) t
)
350 (and (combination-p dest
)
351 (not (values-subtypep ; explicit THE
352 (continuation-externally-checkable-type cont
)
353 (continuation-type-to-check cont
)))))
354 ;; :ERROR means that we have an invalid syntax of
355 ;; the call and the callee will detect it before
356 ;; thinking about types.
359 (let ((info (basic-combination-fun-info dest
)))
360 (if (fun-info-ir2-convert info
)
362 (dolist (template (fun-info-templates info
) nil
)
363 (when (eq (template-ltn-policy template
)
365 (multiple-value-bind (val win
)
366 (valid-fun-use dest
(template-type template
))
367 (when (or val
(not win
)) (return t
)))))))))))))
370 ;;; Return a lambda form that we can convert to do a hairy type check
371 ;;; of the specified TYPES. TYPES is a list of the format returned by
372 ;;; LVAR-CHECK-TYPES in the :HAIRY case.
374 ;;; Note that we don't attempt to check for required values being
375 ;;; unsupplied. Such checking is impossible to efficiently do at the
376 ;;; source level because our fixed-values conventions are optimized
377 ;;; for the common MV-BIND case.
378 (defun make-type-check-form (types)
379 (let ((temps (make-gensym-list (length types
))))
380 `(multiple-value-bind ,temps
382 ,@(mapcar (lambda (temp type
)
384 (let ((*unparse-fun-type-simplify
* t
))
385 (type-specifier (second type
))))
386 (test (if (first type
) `(not ,spec
) spec
)))
387 `(unless (typep ,temp
',test
)
390 ',(type-specifier (third type
))))))
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
)))
433 (let ((dtype (node-derived-type use
)))
434 (unless (values-types-equal-or-intersect dtype atype
)
435 (let* ((*compiler-error-context
* use
)
436 (atype-spec (type-specifier atype
))
437 (what (when (and (combination-p dest
)
438 (eq (combination-kind dest
) :local
))
439 (let ((lambda (combination-lambda dest
))
440 (pos (position-or-lose
441 lvar
(combination-args dest
))))
442 (format nil
"~:[A possible~;The~] binding of ~S"
443 (and (lvar-has-single-use-p lvar
)
444 (eq (functional-kind lambda
) :let
))
445 (leaf-source-name (elt (lambda-vars lambda
)
447 (cond ((and (ref-p use
) (constant-p (ref-leaf use
)))
450 "~:[This~;~:*~A~] is not a ~<~%~9T~:;~S:~>~% ~S"
452 (list what atype-spec
453 (constant-value (ref-leaf use
)))))
457 "~:[Result~;~:*~A~] is a ~S, ~<~%~9T~:;not a ~S.~>"
459 (list what
(type-specifier dtype
) atype-spec
)))))))))
462 ;;; Loop over all blocks in COMPONENT that have TYPE-CHECK set,
463 ;;; looking for CASTs with TYPE-CHECK T. We do two mostly unrelated
464 ;;; things: detect compile-time type errors and determine if and how
465 ;;; to do run-time type checks.
467 ;;; If there is a compile-time type error, then we mark the CAST and
468 ;;; emit a warning if appropriate. This part loops over all the uses
469 ;;; of the continuation, since after we convert the check, the
470 ;;; :DELETED kind will inhibit warnings about the types of other uses.
472 ;;; If the cast is too complex to be checked by the back end, or is
473 ;;; better checked with explicit code, then convert to an explicit
474 ;;; test. Assertions that can checked by the back end are passed
475 ;;; through. Assertions that can't be tested are flamed about and
476 ;;; marked as not needing to be checked.
478 ;;; If we determine that a type check won't be done, then we set
479 ;;; TYPE-CHECK to :NO-CHECK. In the non-hairy cases, this is just to
480 ;;; prevent us from wasting time coming to the same conclusion again
481 ;;; on a later iteration. In the hairy case, we must indicate to LTN
482 ;;; that it must choose a safe implementation, since IR2 conversion
483 ;;; will choke on the check.
485 ;;; The generation of the type checks is delayed until all the type
486 ;;; check decisions have been made because the generation of the type
487 ;;; checks creates new nodes whose derived types aren't always updated
488 ;;; which may lead to inappropriate template choices due to the
489 ;;; modification of argument types.
490 (defun generate-type-checks (component)
492 (do-blocks (block component
)
493 (when (block-type-check block
)
494 ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass
495 (do-nodes-backwards (node nil block
)
496 (when (and (cast-p node
)
497 (cast-type-check node
))
498 (cast-check-uses node
)
499 (cond ((cast-externally-checkable-p node
)
500 (setf (cast-%type-check node
) :external
))
502 ;; it is possible that NODE was marked :EXTERNAL by
504 (setf (cast-%type-check node
) t
)
505 (casts (cons node
(not (probable-type-check-p node
))))))))
506 (setf (block-type-check block
) nil
)))
507 (dolist (cast (casts))
508 (destructuring-bind (cast . force-hairy
) cast
509 (multiple-value-bind (check types
)
510 (cast-check-types cast force-hairy
)
514 (convert-type-check cast types
))
516 (let ((*compiler-error-context
* cast
))
517 (when (policy cast
(>= safety inhibit-warnings
))
519 "type assertion too complex to check:~% ~S."
520 (type-specifier (coerce-to-values (cast-asserted-type cast
))))))
521 (setf (cast-type-to-check cast
) *wild-type
*)
522 (setf (cast-%type-check cast
) nil
)))))))