| blob | 04584a614f3a49ba5e68b1f7da818dbd820f78f5 |
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.
54 nil))
78 ;; FIXME: Our canonicalization isn't quite ideal for this. We get
79 ;; types such as:
80 ;;
81 ;; (OR (AND (SATISFIES FOO) (INTEGER -100 -50))
82 ;; (AND (SATISFIES FOO) (INTEGER 100 200)))
83 ;;
84 ;; here, and weakening that into
85 ;;
86 ;; (AND (SATISFIES FOO) (INTEGER -100 200))
87 ;;
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.
99 new))
105 bound
111 bound
122 rest
127 type))))
135 type)
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
140 ;; ranges into one.
154 samep)
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
158 ;; poor cost info.
160 min-type stype
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.
168 min-type
169 type)))))
183 \f
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.
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.
206 and c in types
207 and a in original-types
208 and i from 0
211 c)
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
224 ;;; performed.
226 ;;; In the types are checkable it returns :SIMPLE and the second value
227 ;;; of the form:
228 ;;; (NOT-P TYPE ORIGINAL-TYPE)
229 ;;;
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.
234 ;;;
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.
248 nil)
261 ;; we [almost] know how many values are produced
266 n-required)))
268 ;; exactly one value is consumed
273 n-required)))
277 ;; we know the number of consumed values
280 n-consumed
283 n-consumed
285 n-required)))
289 ;;; Return T is the cast appears to be from the declaration of the callee,
290 ;;; and should be checked externally -- that is, by the callee and not the caller.
296 ;; The theory is that the type assertion is from a declaration on the
297 ;; callee, so the callee should be able to do the check. We want to
298 ;; let the callee do the check, because it is possible that by the
299 ;; time of call that declaration will be changed and we do not want
300 ;; to make people recompile all calls to a function when they were
301 ;; originally compiled with a bad declaration.
302 ;;
303 ;; ALMOST-IMMEDIATELY-USED-P ensures that we don't delegate casts
304 ;; that occur before nodes that can cause observable side effects --
305 ;; most commonly other non-external casts: so the order in which
306 ;; possible type errors are signalled matches with the evaluation
307 ;; order.
308 ;;
309 ;; FIXME: We should let more cases be handled by the callee then we
310 ;; currently do, see: https://bugs.launchpad.net/sbcl/+bug/309104
311 ;; This is not fixable quite here, though, because flow-analysis has
312 ;; deleted the LVAR of the cast by the time we get here, so there is
313 ;; no destination. Perhaps we should mark cases inserted by
314 ;; ASSERT-CALL-TYPE explicitly, and delete those whose destination is
315 ;; deemed unreachable?
320 ;; Type specifiers handled by the general-purpose MAKE-TYPE-CHECK-FORM are often
321 ;; trivial enough to have an internal error number assigned to them that can be
322 ;; used in lieu of OBJECT-NOT-TYPE-ERROR. On x86-64 this saves 16 bytes: 1 word
323 ;; for the symbol in the function's constant area, a MOV instruction to load it,
324 ;; and an sc-offset in the error trap.
327 ;; read-time-eval so that during cold-init we can recreate the
328 ;; table using the target's sxhash function, but without relying
329 ;; on readiness of the type system for parsing/unparsing specifiers.
336 ;; This is effectively a compact read-only binned hashtable.
344 entries)
345 hashtable))
356 ;; spec -> (count . primitive-p)
360 answer)))
365 type))
372 ;;; Return a lambda form that we can convert to do a type check
373 ;;; of the specified TYPES. TYPES is a list of the format returned by
374 ;;; CAST-CHECK-TYPES.
375 ;;;
376 ;;; Note that we don't attempt to check for required values being
377 ;;; unsupplied. Such checking is impossible to efficiently do at the
378 ;;; source level because our fixed-values conventions are optimized
379 ;;; for the common MV-BIND case.
390 temps
391 types)
394 ;;; Splice in explicit type check code immediately before CAST. This
395 ;;; code receives the value(s) that were being passed to CAST-VALUE,
396 ;;; checks the type(s) of the value(s), then passes them further.
408 atype)
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.
451 pos)))))))
455 ~<~%~9T~:;~/sb!impl:print-type/:~>~% ~S"
456 :format-arguments
460 :format-control
461 "~:[Result~;~:*~A~] is a ~/sb!impl:print-type/, ~
462 ~<~%~9T~:;not a ~/sb!impl:print-type/.~>"
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.
470 ;;;
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.
475 ;;;
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.
481 ;;;
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.
488 ;;;
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.
499 ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass
507 ;; it is possible that NODE was marked :EXTERNAL by
508 ;; the previous pass
516 (:simple
518 (:too-hairy
522 "type assertion too complex to check:~%~
523 ~/sb!impl:print-type/."