| blob | 46b32e11cc9140e1729c6309e1f3fe792f99283d |
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
7 ;;;; more information.
8 ;;;;
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.
16 \f
17 ;;;; cost estimation
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.)
24 ;;;
25 ;;; We special-case NULL, since it does have a source tranform and is
26 ;;; interesting to us.
38 call-cost)))
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.
57 nil))))
100 type)))
109 type)
111 ;; KLUDGE: Simple range checks are not that expensive, and we *don't*
112 ;; want to accidentally lose eg. array bounds checks due to weakening,
113 ;; so for integer types we simply collapse all ranges into one.
127 samep)
128 ;; If the supertype is equal in cost to the type, we
129 ;; prefer the supertype. This produces a closer
130 ;; approximation of the right thing in the presence of
131 ;; poor cost info.
133 min-type stype
134 min-cost stype-cost))))))
135 ;; This used to return the *UNIVERSAL-TYPE* if no supertype was found,
136 ;; but that's too liberal: it's far too easy for the user to create
137 ;; a union type (which are excluded above), and then trick the compiler
138 ;; into trusting the union type... and finally ending up corrupting the
139 ;; heap once a bad object sneaks past the missing type check.
141 min-type
142 type)))))
156 \f
157 ;;;; checking strategy determination
159 ;;; Return the type we should test for when we really want to check
160 ;;; for TYPE. If type checking policy is "fast", then we return a
161 ;;; weaker type if it is easier to check. First we try the defined
162 ;;; type weakenings, then look for any predicate that is cheaper.
170 ;;; This is like VALUES-TYPES, only we mash any complex function types
171 ;;; to FUNCTION.
178 type))
179 res)
180 count)))
182 ;;; Switch to disable check complementing, for evaluation.
185 ;;; LVAR is an lvar we are doing a type check on and TYPES is a list
186 ;;; of types that we are checking its values against. If we have
187 ;;; proven that LVAR generates a fixed number of values, then for each
188 ;;; value, we check whether it is cheaper to then difference between
189 ;;; the proven type and the corresponding type in TYPES. If so, we opt
190 ;;; for a :HAIRY check with that test negated. Otherwise, we try to do
191 ;;; a simple test, and if that is impossible, we do a hairy test with
192 ;;; non-negated types. If true, FORCE-HAIRY forces a hairy type check.
198 and c in types
199 and a in original-types
200 and i from 0
203 c)
211 into hairy-res
212 collect cc into simple-res
221 ;;; Determines whether CAST's assertion is:
222 ;;; -- checkable by the back end (:SIMPLE), or
223 ;;; -- not checkable by the back end, but checkable via an explicit
224 ;;; test in type check conversion (:HAIRY), or
225 ;;; -- not reasonably checkable at all (:TOO-HAIRY).
226 ;;;
227 ;;; We may check only fixed number of values; in any case the number
228 ;;; of generated values is trusted. If we know the number of produced
229 ;;; values, all of them are checked; otherwise if we know the number
230 ;;; of consumed -- only they are checked; otherwise the check is not
231 ;;; performed.
232 ;;;
233 ;;; A type is simply checkable if all the type assertions have a
234 ;;; TYPE-CHECK-TEMPLATE. In this :SIMPLE case, the second value is a
235 ;;; list of the type restrictions specified for the leading positional
236 ;;; values.
237 ;;;
238 ;;; Old comment:
239 ;;;
240 ;;; We force a check to be hairy even when there are fixed values
241 ;;; if we are in a context where we may be forced to use the
242 ;;; unknown values convention anyway. This is because IR2tran can't
243 ;;; generate type checks for unknown values lvars but people could
244 ;;; still be depending on the check being done. We only care about
245 ;;; EXIT and RETURN (not MV-COMBINATION) since these are the only
246 ;;; contexts where the ultimate values receiver
247 ;;;
248 ;;; In the :HAIRY case, the second value is a list of triples of
249 ;;; the form:
250 ;;; (NOT-P TYPE ORIGINAL-TYPE)
251 ;;;
252 ;;; If true, the NOT-P flag indicates a test that the corresponding
253 ;;; value is *not* of the specified TYPE. ORIGINAL-TYPE is the type
254 ;;; asserted on this value in the lvar, for use in error
255 ;;; messages. When NOT-P is true, this will be different from TYPE.
256 ;;;
257 ;;; This allows us to take what has been proven about CAST's argument
258 ;;; type into consideration. If it is cheaper to test for the
259 ;;; difference between the derived type and the asserted type, then we
260 ;;; check for the negation of this type instead.
270 nil)
281 ;; we [almost] know how many values are produced
285 ;; backend checks only consumed values
287 n-required))
289 ;; exactly one value is consumed
301 force-hairy
302 n-required))))
305 ;; we know the number of consumed values
308 n-consumed
311 n-consumed
313 force-hairy
314 n-required))
318 ;;; Return T is the cast appears to be from the declaration of the callee,
319 ;;; and should be checked externally -- that is, by the callee and not the caller.
325 ;; The theory is that the type assertion is from a declaration on the
326 ;; callee, so the callee should be able to do the check. We want to
327 ;; let the callee do the check, because it is possible that by the
328 ;; time of call that declaration will be changed and we do not want
329 ;; to make people recompile all calls to a function when they were
330 ;; originally compiled with a bad declaration.
331 ;;
332 ;; ALMOST-IMMEDIATELY-USED-P ensures that we don't delegate casts
333 ;; that occur before nodes that can cause observable side effects --
334 ;; most commonly other non-external casts: so the order in which
335 ;; possible type errors are signalled matches with the evaluation
336 ;; order.
337 ;;
338 ;; FIXME: We should let more cases be handled by the callee then we
339 ;; currently do, see: https://bugs.launchpad.net/sbcl/+bug/309104
340 ;; This is not fixable quite here, though, because flow-analysis has
341 ;; deleted the LVAR of the cast by the time we get here, so there is
342 ;; no destination. Perhaps we should mark cases inserted by
343 ;; ASSERT-CALL-TYPE explicitly, and delete those whose destination is
344 ;; deemed unreachable?
349 ;;; Return true if CAST's value is an lvar whose type the back end is
350 ;;; likely to be able to check (see GENERATE-TYPE-CHECKS). Since we
351 ;;; don't know what template the back end is going to choose to
352 ;;; implement the continuation's DEST, we use a heuristic.
353 ;;;
354 ;;; We always return T unless nobody uses the value (the backend
355 ;;; cannot check unused LVAR chains).
356 ;;;
357 ;;; The logic used to be more complex, but most of the cases that used
358 ;;; to be checked here are now dealt with differently . FIXME: but
359 ;;; here's one we used to do, don't anymore, but could still benefit
360 ;;; from, if we reimplemented it (elsewhere):
361 ;;;
362 ;;; -- If the lvar is an argument to a known function that has
363 ;;; no IR2-CONVERT method or :FAST-SAFE templates that are
364 ;;; compatible with the call's type: return NIL.
365 ;;;
366 ;;; The code used to look like something like this:
367 ;;; ...
368 ;;; (:known
369 ;;; (let ((info (basic-combination-fun-info dest)))
370 ;;; (if (fun-info-ir2-convert info)
371 ;;; t
372 ;;; (dolist (template (fun-info-templates info) nil)
373 ;;; (when (eq (template-ltn-policy template)
374 ;;; :fast-safe)
375 ;;; (multiple-value-bind (val win)
376 ;;; (valid-fun-use dest (template-type template))
377 ;;; (when (or val (not win)) (return t)))))))))))))
378 ;;;
379 ;;; ADP says: It is still interesting. When we have a :SAFE template
380 ;;; and the type assertion is derived from the destination function
381 ;;; type, the check is unneccessary. We cannot return NIL here (the
382 ;;; whole function has changed its meaning, and here NIL *forces*
383 ;;; hairy check), but the functionality is interesting.
391 ;;; Return a lambda form that we can convert to do a hairy type check
392 ;;; of the specified TYPES. TYPES is a list of the format returned by
393 ;;; LVAR-CHECK-TYPES in the :HAIRY case.
394 ;;;
395 ;;; Note that we don't attempt to check for required values being
396 ;;; unsupplied. Such checking is impossible to efficiently do at the
397 ;;; source level because our fixed-values conventions are optimized
398 ;;; for the common MV-BIND case.
402 'dummy
409 (%type-check-error
410 ,temp
412 temps
413 types)
416 ;;; Splice in explicit type check code immediately before CAST. This
417 ;;; code receives the value(s) that were being passed to CAST-VALUE,
418 ;;; checks the type(s) of the value(s), then passes them further.
429 atype)
443 ;;; Check all possible arguments of CAST and emit type warnings for
444 ;;; those with type errors. If the value of USE is being used for a
445 ;;; variable binding, we figure out which one for source context. If
446 ;;; the value is a constant, we print it specially.
467 pos)))))))
470 :format-control
471 "~:[This~;~:*~A~] is not a ~<~%~9T~:;~S:~>~% ~S"
472 :format-arguments
477 :format-control
478 "~:[Result~;~:*~A~] is a ~S, ~<~%~9T~:;not a ~S.~>"
479 :format-arguments
483 ;;; Loop over all blocks in COMPONENT that have TYPE-CHECK set,
484 ;;; looking for CASTs with TYPE-CHECK T. We do two mostly unrelated
485 ;;; things: detect compile-time type errors and determine if and how
486 ;;; to do run-time type checks.
487 ;;;
488 ;;; If there is a compile-time type error, then we mark the CAST and
489 ;;; emit a warning if appropriate. This part loops over all the uses
490 ;;; of the continuation, since after we convert the check, the
491 ;;; :DELETED kind will inhibit warnings about the types of other uses.
492 ;;;
493 ;;; If the cast is too complex to be checked by the back end, or is
494 ;;; better checked with explicit code, then convert to an explicit
495 ;;; test. Assertions that can checked by the back end are passed
496 ;;; through. Assertions that can't be tested are flamed about and
497 ;;; marked as not needing to be checked.
498 ;;;
499 ;;; If we determine that a type check won't be done, then we set
500 ;;; TYPE-CHECK to :NO-CHECK. In the non-hairy cases, this is just to
501 ;;; prevent us from wasting time coming to the same conclusion again
502 ;;; on a later iteration. In the hairy case, we must indicate to LTN
503 ;;; that it must choose a safe implementation, since IR2 conversion
504 ;;; will choke on the check.
505 ;;;
506 ;;; The generation of the type checks is delayed until all the type
507 ;;; check decisions have been made because the generation of the type
508 ;;; checks creates new nodes whose derived types aren't always updated
509 ;;; which may lead to inappropriate template choices due to the
510 ;;; modification of argument types.
515 ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass
523 ;; it is possible that NODE was marked :EXTERNAL by
524 ;; the previous pass
534 (:hairy
536 (:too-hairy
540 "type assertion too complex to check:~% ~S."