| blob | 3fd81d57a6fed065ece18b06d969fd7a26925e3f |
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))))
96 ;; If the supertype is equal in cost to the type, we
97 ;; prefer the supertype. This produces a closer
98 ;; approximation of the right thing in the presence of
99 ;; poor cost info.
101 min-type stype
102 min-cost stype-cost))))))
104 min-type
119 \f
120 ;;;; checking strategy determination
122 ;;; Return the type we should test for when we really want to check
123 ;;; for TYPE. If type checking policy is "fast", then we return a
124 ;;; weaker type if it is easier to check. First we try the defined
125 ;;; type weakenings, then look for any predicate that is cheaper.
133 ;;; This is like VALUES-TYPES, only we mash any complex function types
134 ;;; to FUNCTION.
141 type))
142 res)
143 count)))
145 ;;; Switch to disable check complementing, for evaluation.
148 ;;; LVAR is an lvar we are doing a type check on and TYPES is a list
149 ;;; of types that we are checking its values against. If we have
150 ;;; proven that LVAR generates a fixed number of values, then for each
151 ;;; value, we check whether it is cheaper to then difference between
152 ;;; the proven type and the corresponding type in TYPES. If so, we opt
153 ;;; for a :HAIRY check with that test negated. Otherwise, we try to do
154 ;;; a simple test, and if that is impossible, we do a hairy test with
155 ;;; non-negated types. If true, FORCE-HAIRY forces a hairy type check.
156 ;;;
157 ;;; When doing a non-negated check, we call MAYBE-WEAKEN-CHECK to
158 ;;; weaken the test to a convenient supertype (conditional on policy.)
159 ;;; If SPEED is 3, or DEBUG-INFO is not particularly important (DEBUG
160 ;;; <= 1), then we allow weakened checks to be simple, resulting in
161 ;;; less informative error messages, but saving space and possibly
162 ;;; time.
163 ;;;
164 ;;; FIXME: I don't quite understand this, but it looks as though
165 ;;; that means type checks are weakened when SPEED=3 regardless of
166 ;;; the SAFETY level, which is not the right thing to do.
172 and c in types
173 and a in original-types
174 and i from 0
177 c)
185 into hairy-res
186 collect cc into simple-res
195 ;;; Determines whether CAST's assertion is:
196 ;;; -- checkable by the back end (:SIMPLE), or
197 ;;; -- not checkable by the back end, but checkable via an explicit
198 ;;; test in type check conversion (:HAIRY), or
199 ;;; -- not reasonably checkable at all (:TOO-HAIRY).
200 ;;;
201 ;;; We may check only fixed number of values; in any case the number
202 ;;; of generated values is trusted. If we know the number of produced
203 ;;; values, all of them are checked; otherwise if we know the number
204 ;;; of consumed -- only they are checked; otherwise the check is not
205 ;;; performed.
206 ;;;
207 ;;; A type is simply checkable if all the type assertions have a
208 ;;; TYPE-CHECK-TEMPLATE. In this :SIMPLE case, the second value is a
209 ;;; list of the type restrictions specified for the leading positional
210 ;;; values.
211 ;;;
212 ;;; Old comment:
213 ;;;
214 ;;; We force a check to be hairy even when there are fixed values
215 ;;; if we are in a context where we may be forced to use the
216 ;;; unknown values convention anyway. This is because IR2tran can't
217 ;;; generate type checks for unknown values lvars but people could
218 ;;; still be depending on the check being done. We only care about
219 ;;; EXIT and RETURN (not MV-COMBINATION) since these are the only
220 ;;; contexts where the ultimate values receiver
221 ;;;
222 ;;; In the :HAIRY case, the second value is a list of triples of
223 ;;; the form:
224 ;;; (NOT-P TYPE ORIGINAL-TYPE)
225 ;;;
226 ;;; If true, the NOT-P flag indicates a test that the corresponding
227 ;;; value is *not* of the specified TYPE. ORIGINAL-TYPE is the type
228 ;;; asserted on this value in the lvar, for use in error
229 ;;; messages. When NOT-P is true, this will be different from TYPE.
230 ;;;
231 ;;; This allows us to take what has been proven about CAST's argument
232 ;;; type into consideration. If it is cheaper to test for the
233 ;;; difference between the derived type and the asserted type, then we
234 ;;; check for the negation of this type instead.
244 nil)
255 ;; we [almost] know how many values are produced
259 ;; backend checks only consumed values
261 n-required))
263 ;; exactly one value is consumed
273 force-hairy
274 n-required)))
277 ;; we know the number of consumed values
280 n-consumed
283 n-consumed
285 force-hairy
286 n-required))
290 ;;; Do we want to do a type check?
296 ;; The theory is that the type assertion is from a
297 ;; declaration in (or on) the callee, so the callee should be
298 ;; able to do the check. We want to let the callee do the
299 ;; check, because it is possible that by the time of call
300 ;; that declaration will be changed and we do not want to
301 ;; make people recompile all calls to a function when they
302 ;; were originally compiled with a bad declaration. (See also
303 ;; bug 35.)
313 ;;; Return true if CAST's value is an lvar whose type the back end is
314 ;;; likely to want to check. Since we don't know what template the
315 ;;; back end is going to choose to implement the continuation's DEST,
316 ;;; we use a heuristic. We always return T unless:
317 ;;; -- nobody uses the value, or
318 ;;; -- safety is totally unimportant, or
319 ;;; -- the lvar is an argument to an unknown function, or
320 ;;; -- the lvar is an argument to a known function that has
321 ;;; no IR2-CONVERT method or :FAST-SAFE templates that are
322 ;;; compatible with the call's type.
329 #+nil
332 nil)
340 (:full
345 ;; :ERROR means that we have an invalid syntax of
346 ;; the call and the callee will detect it before
347 ;; thinking about types.
349 (:known
352 t
361 ;;; Return a lambda form that we can convert to do a hairy type check
362 ;;; of the specified TYPES. TYPES is a list of the format returned by
363 ;;; LVAR-CHECK-TYPES in the :HAIRY case.
364 ;;;
365 ;;; Note that we don't attempt to check for required values being
366 ;;; unsupplied. Such checking is impossible to efficiently do at the
367 ;;; source level because our fixed-values conventions are optimized
368 ;;; for the common MV-BIND case.
372 'dummy
379 (%type-check-error
380 ,temp
382 temps
383 types)
386 ;;; Splice in explicit type check code immediately before CAST. This
387 ;;; code receives the value(s) that were being passed to CAST-VALUE,
388 ;;; checks the type(s) of the value(s), then passes them further.
399 atype)
413 ;;; Check all possible arguments of CAST and emit type warnings for
414 ;;; those with type errors. If the value of USE is being used for a
415 ;;; variable binding, we figure out which one for source context. If
416 ;;; the value is a constant, we print it specially.
437 pos)))))))
440 :format-control
441 "~:[This~;~:*~A~] is not a ~<~%~9T~:;~S:~>~% ~S"
442 :format-arguments
447 :format-control
448 "~:[Result~;~:*~A~] is a ~S, ~<~%~9T~:;not a ~S.~>"
449 :format-arguments
453 ;;; Loop over all blocks in COMPONENT that have TYPE-CHECK set,
454 ;;; looking for CASTs with TYPE-CHECK T. We do two mostly unrelated
455 ;;; things: detect compile-time type errors and determine if and how
456 ;;; to do run-time type checks.
457 ;;;
458 ;;; If there is a compile-time type error, then we mark the CAST and
459 ;;; emit a warning if appropriate. This part loops over all the uses
460 ;;; of the continuation, since after we convert the check, the
461 ;;; :DELETED kind will inhibit warnings about the types of other uses.
462 ;;;
463 ;;; If the cast is too complex to be checked by the back end, or is
464 ;;; better checked with explicit code, then convert to an explicit
465 ;;; test. Assertions that can checked by the back end are passed
466 ;;; through. Assertions that can't be tested are flamed about and
467 ;;; marked as not needing to be checked.
468 ;;;
469 ;;; If we determine that a type check won't be done, then we set
470 ;;; TYPE-CHECK to :NO-CHECK. In the non-hairy cases, this is just to
471 ;;; prevent us from wasting time coming to the same conclusion again
472 ;;; on a later iteration. In the hairy case, we must indicate to LTN
473 ;;; that it must choose a safe implementation, since IR2 conversion
474 ;;; will choke on the check.
475 ;;;
476 ;;; The generation of the type checks is delayed until all the type
477 ;;; check decisions have been made because the generation of the type
478 ;;; checks creates new nodes whose derived types aren't always updated
479 ;;; which may lead to inappropriate template choices due to the
480 ;;; modification of argument types.
485 ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass
493 ;; it is possible that NODE was marked :EXTERNAL by
494 ;; the previous pass
504 (:hairy
506 (:too-hairy
510 "type assertion too complex to check:~% ~S."