X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fcheckgen.lisp;h=2f9f9072a53a5f619f37b2a403b3485bd0dd9aeb;hb=61c18727668ff0c3263a3d363e609d4522d545cc;hp=53134417ef511711d0485911c7391ad6e52e1212;hpb=09cd508206ea4d5da08d3950f9cddb862e81dffd;p=sbcl.git diff --git a/src/compiler/checkgen.lisp b/src/compiler/checkgen.lisp index 5313441..2f9f907 100644 --- a/src/compiler/checkgen.lisp +++ b/src/compiler/checkgen.lisp @@ -43,7 +43,11 @@ ;;; templates in the VM definition. (defun type-test-cost (type) (declare (type ctype type)) - (or (let ((check (type-check-template type))) + (or (when (eq type *universal-type*) + 0) + (when (eq type *empty-type*) + 0) + (let ((check (type-check-template type))) (if check (template-cost check) (let ((found (cdr (assoc type *backend-type-predicates* @@ -141,9 +145,9 @@ ;;; Switch to disable check complementing, for evaluation. (defvar *complement-type-checks* t) -;;; CONT is a continuation we are doing a type check on and TYPES is a -;;; list of types that we are checking its values against. If we have -;;; proven that CONT generates a fixed number of values, then for each +;;; LVAR is an lvar we are doing a type check on and TYPES is a list +;;; of types that we are checking its values against. If we have +;;; proven that LVAR generates a fixed number of values, then for each ;;; value, we check whether it is cheaper to then difference between ;;; the proven type and the corresponding type in TYPES. If so, we opt ;;; for a :HAIRY check with that test negated. Otherwise, we try to do @@ -160,50 +164,60 @@ ;;; FIXME: I don't quite understand this, but it looks as though ;;; that means type checks are weakened when SPEED=3 regardless of ;;; the SAFETY level, which is not the right thing to do. -(defun maybe-negate-check (cont types original-types force-hairy) - (declare (type continuation cont) (list types)) - (multiple-value-bind (ptypes count) - (no-fun-values-types (continuation-derived-type cont)) - (if (eq count :unknown) - (if (and (every #'type-check-template types) (not force-hairy)) - (values :simple types) - (values :hairy (mapcar (lambda (x) (list nil x x)) types))) - (let ((res (mapcar (lambda (p c a) - (let ((diff (type-difference p c))) - (if (and diff - (< (type-test-cost diff) - (type-test-cost c)) - *complement-type-checks*) - (list t diff a) - (list nil c a)))) - ptypes types original-types))) - (cond ((or force-hairy (find-if #'first res)) - (values :hairy res)) - ((every #'type-check-template types) - (values :simple types)) - (t - (values :hairy res))))))) +(defun maybe-negate-check (lvar types original-types force-hairy n-required) + (declare (type lvar lvar) (list types original-types)) + (let ((ptypes (values-type-out (lvar-derived-type lvar) (length types)))) + (multiple-value-bind (hairy-res simple-res) + (loop for p in ptypes + and c in types + and a in original-types + and i from 0 + for cc = (if (>= i n-required) + (type-union c (specifier-type 'null)) + c) + for diff = (type-difference p cc) + collect (if (and diff + (< (type-test-cost diff) + (type-test-cost cc)) + *complement-type-checks*) + (list t diff a) + (list nil cc a)) + into hairy-res + collect cc into simple-res + finally (return (values hairy-res simple-res))) + (cond ((or force-hairy (find-if #'first hairy-res)) + (values :hairy hairy-res)) + ((every #'type-check-template simple-res) + (values :simple simple-res)) + (t + (values :hairy hairy-res)))))) -;;; Determines whether CONT's assertion is: +;;; Determines whether CAST's assertion is: ;;; -- checkable by the back end (:SIMPLE), or ;;; -- not checkable by the back end, but checkable via an explicit ;;; test in type check conversion (:HAIRY), or ;;; -- not reasonably checkable at all (:TOO-HAIRY). ;;; -;;; A type is checkable if it either represents a fixed number of -;;; values (as determined by VALUES-TYPES), or it is the assertion for -;;; an MV-BIND. A type is simply checkable if all the type assertions -;;; have a TYPE-CHECK-TEMPLATE. In this :SIMPLE case, the second value -;;; is a list of the type restrictions specified for the leading -;;; positional values. +;;; We may check only fixed number of values; in any case the number +;;; of generated values is trusted. If we know the number of produced +;;; values, all of them are checked; otherwise if we know the number +;;; of consumed -- only they are checked; otherwise the check is not +;;; performed. ;;; -;;; We force a check to be hairy even when there are fixed values if -;;; we are in a context where we may be forced to use the unknown -;;; values convention anyway. This is because IR2tran can't generate -;;; type checks for unknown values continuations but people could -;;; still be depending on the check being done. We only care about -;;; EXIT and RETURN (not MV-COMBINATION) since these are the only -;;; contexts where the ultimate values receiver +;;; A type is simply checkable if all the type assertions have a +;;; TYPE-CHECK-TEMPLATE. In this :SIMPLE case, the second value is a +;;; list of the type restrictions specified for the leading positional +;;; values. +;;; +;;; Old comment: +;;; +;;; We force a check to be hairy even when there are fixed values +;;; if we are in a context where we may be forced to use the +;;; unknown values convention anyway. This is because IR2tran can't +;;; generate type checks for unknown values lvars but people could +;;; still be depending on the check being done. We only care about +;;; EXIT and RETURN (not MV-COMBINATION) since these are the only +;;; contexts where the ultimate values receiver ;;; ;;; In the :HAIRY case, the second value is a list of triples of ;;; the form: @@ -211,111 +225,105 @@ ;;; ;;; If true, the NOT-P flag indicates a test that the corresponding ;;; value is *not* of the specified TYPE. ORIGINAL-TYPE is the type -;;; asserted on this value in the continuation, for use in error +;;; asserted on this value in the lvar, for use in error ;;; messages. When NOT-P is true, this will be different from TYPE. ;;; -;;; This allows us to take what has been proven about CONT's type into -;;; consideration. If it is cheaper to test for the difference between -;;; the derived type and the asserted type, then we check for the -;;; negation of this type instead. +;;; This allows us to take what has been proven about CAST's argument +;;; type into consideration. If it is cheaper to test for the +;;; difference between the derived type and the asserted type, then we +;;; check for the negation of this type instead. (defun cast-check-types (cast force-hairy) (declare (type cast cast)) - (let* ((cont (node-cont cast)) - (ctype (coerce-to-values (cast-type-to-check cast))) + (let* ((ctype (coerce-to-values (cast-type-to-check cast))) (atype (coerce-to-values (cast-asserted-type cast))) + (dtype (node-derived-type cast)) (value (cast-value cast)) - (vtype (continuation-derived-type value)) - (dest (continuation-dest cont))) + (lvar (node-lvar cast)) + (dest (and lvar (lvar-dest lvar))) + (n-consumed (cond ((not lvar) + nil) + ((lvar-single-value-p lvar) + 1) + ((and (mv-combination-p dest) + (eq (mv-combination-kind dest) :local)) + (let ((fun-ref (lvar-use (mv-combination-fun dest)))) + (length (lambda-vars (ref-leaf fun-ref))))))) + (n-required (length (values-type-required dtype)))) (aver (not (eq ctype *wild-type*))) - (multiple-value-bind (ctypes count) (no-fun-values-types ctype) - (multiple-value-bind (atypes acount) (no-fun-values-types atype) - (multiple-value-bind (vtypes vcount) (values-types vtype) - (declare (ignore vtypes)) - (aver (eq count acount)) - (cond ((not (eq count :unknown)) - (if (or (exit-p dest) - (and (return-p dest) - (multiple-value-bind (ignore count) - (values-types (return-result-type dest)) - (declare (ignore ignore)) - (eq count :unknown)))) - (maybe-negate-check value ctypes atypes t) - (maybe-negate-check value ctypes atypes force-hairy))) - ((and (continuation-single-value-p cont) - (or (not (args-type-rest ctype)) - (eq (args-type-rest ctype) *universal-type*))) - (principal-continuation-single-valuify cont) - (let ((creq (car (args-type-required ctype)))) - (multiple-value-setq (ctype atype) - (if creq - (values creq (car (args-type-required atype))) - (values (car (args-type-optional ctype)) - (car (args-type-optional atype))))) - (maybe-negate-check value - (list ctype) (list atype) - force-hairy))) - ((and (mv-combination-p dest) - (eq (mv-combination-kind dest) :local)) - (let* ((fun-ref (continuation-use (mv-combination-fun dest))) - (length (length (lambda-vars (ref-leaf fun-ref))))) - (maybe-negate-check value - ;; FIXME - (adjust-list (values-type-types ctype) - length - *universal-type*) - (adjust-list (values-type-types atype) - length - *universal-type*) - force-hairy))) - ((not (eq vcount :unknown)) - (maybe-negate-check value - (values-type-out ctype vcount) - (values-type-out atype vcount) - t)) - (t - (values :too-hairy nil)))))))) + (cond ((and (null (values-type-optional dtype)) + (not (values-type-rest dtype))) + ;; we [almost] know how many values are produced + (maybe-negate-check value + (values-type-out ctype n-required) + (values-type-out atype n-required) + ;; backend checks only consumed values + (not (eql n-required n-consumed)) + n-required)) + ((lvar-single-value-p lvar) + ;; exactly one value is consumed + (principal-lvar-single-valuify lvar) + (let ((creq (car (args-type-required ctype)))) + (multiple-value-setq (ctype atype) + (if creq + (values creq (car (args-type-required atype))) + (values (car (args-type-optional ctype)) + (car (args-type-optional atype))))) + (maybe-negate-check value + (list ctype) (list atype) + force-hairy + n-required))) + ((and (mv-combination-p dest) + (eq (mv-combination-kind dest) :local)) + ;; we know the number of consumed values + (maybe-negate-check value + (adjust-list (values-type-types ctype) + n-consumed + *universal-type*) + (adjust-list (values-type-types atype) + n-consumed + *universal-type*) + force-hairy + n-required)) + (t + (values :too-hairy nil))))) ;;; Do we want to do a type check? -(defun worth-type-check-p (cast) +(defun cast-externally-checkable-p (cast) (declare (type cast cast)) - (let* ((cont (node-cont cast)) - (dest (continuation-dest cont))) - (not (or (not (cast-type-check cast)) - (and (combination-p dest) - (let ((kind (combination-kind dest))) - (or (eq kind :full) - ;; The theory is that the type assertion is - ;; from a declaration in (or on) the callee, - ;; so the callee should be able to do the - ;; check. We want to let the callee do the - ;; check, because it is possible that by the - ;; time of call that declaration will be - ;; changed and we do not want to make people - ;; recompile all calls to a function when they - ;; were originally compiled with a bad - ;; declaration. (See also bug 35.) - (and (fun-info-p kind) - (null (fun-info-templates kind)) - (not (fun-info-ir2-convert kind))))) - (and - (immediately-used-p cont cast) - (values-subtypep (continuation-externally-checkable-type cont) - (cast-type-to-check cast)))))))) + (let* ((lvar (node-lvar cast)) + (dest (and lvar (lvar-dest lvar)))) + (and (combination-p dest) + ;; The theory is that the type assertion is from a + ;; declaration in (or on) the callee, so the callee should be + ;; able to do the check. We want to let the callee do the + ;; check, because it is possible that by the time of call + ;; that declaration will be changed and we do not want to + ;; make people recompile all calls to a function when they + ;; were originally compiled with a bad declaration. (See also + ;; bug 35.) + (or (immediately-used-p lvar cast) + (binding* ((ctran (node-next cast) :exit-if-null) + (next (ctran-next ctran))) + (and (cast-p next) + (eq (node-dest next) dest) + (eq (cast-type-check next) :external)))) + (values-subtypep (lvar-externally-checkable-type lvar) + (cast-type-to-check cast))))) -;;; Return true if CONT is a continuation whose type the back end is +;;; Return true if CAST's value is an lvar whose type the back end is ;;; likely to want to check. Since we don't know what template the ;;; back end is going to choose to implement the continuation's DEST, ;;; we use a heuristic. We always return T unless: ;;; -- nobody uses the value, or ;;; -- safety is totally unimportant, or -;;; -- the continuation is an argument to an unknown function, or -;;; -- the continuation is an argument to a known function that has +;;; -- the lvar is an argument to an unknown function, or +;;; -- the lvar is an argument to a known function that has ;;; no IR2-CONVERT method or :FAST-SAFE templates that are ;;; compatible with the call's type. (defun probable-type-check-p (cast) (declare (type cast cast)) - (let* ((cont (node-cont cast)) - (dest (continuation-dest cont))) + (let* ((lvar (node-lvar cast)) + (dest (and lvar (lvar-dest lvar)))) (cond ((not dest) nil) (t t)) #+nil @@ -348,7 +356,7 @@ ;;; Return a lambda form that we can convert to do a hairy type check ;;; of the specified TYPES. TYPES is a list of the format returned by -;;; CONTINUATION-CHECK-TYPES in the :HAIRY case. +;;; LVAR-CHECK-TYPES in the :HAIRY case. ;;; ;;; Note that we don't attempt to check for required values being ;;; unsupplied. Such checking is impossible to efficiently do at the @@ -371,16 +379,15 @@ types) (values ,@temps)))) -;;; Splice in explicit type check code immediately before the node -;;; which is CONT's DEST. This code receives the value(s) that were -;;; being passed to CONT, checks the type(s) of the value(s), then -;;; passes them on to CONT. +;;; Splice in explicit type check code immediately before CAST. This +;;; code receives the value(s) that were being passed to CAST-VALUE, +;;; checks the type(s) of the value(s), then passes them further. (defun convert-type-check (cast types) (declare (type cast cast) (type list types)) - (let ((cont (cast-value cast)) + (let ((value (cast-value cast)) (length (length types))) - (filter-continuation cont (make-type-check-form types)) - (reoptimize-continuation (cast-value cast)) + (filter-lvar value (make-type-check-form types)) + (reoptimize-lvar (cast-value cast)) (setf (cast-type-to-check cast) *wild-type*) (setf (cast-%type-check cast) nil) (let* ((atype (cast-asserted-type cast)) @@ -405,8 +412,8 @@ ;;; the value is a constant, we print it specially. (defun cast-check-uses (cast) (declare (type cast cast)) - (let* ((cont (node-cont cast)) - (dest (continuation-dest cont)) + (let* ((lvar (node-lvar cast)) + (dest (and lvar (lvar-dest lvar))) (value (cast-value cast)) (atype (cast-asserted-type cast))) (do-uses (use value) @@ -418,9 +425,9 @@ (eq (combination-kind dest) :local)) (let ((lambda (combination-lambda dest)) (pos (position-or-lose - cont (combination-args dest)))) + lvar (combination-args dest)))) (format nil "~:[A possible~;The~] binding of ~S" - (and (continuation-use cont) + (and (lvar-has-single-use-p lvar) (eq (functional-kind lambda) :let)) (leaf-source-name (elt (lambda-vars lambda) pos))))))) @@ -434,18 +441,17 @@ (values)) ;;; Loop over all blocks in COMPONENT that have TYPE-CHECK set, -;;; looking for continuations with TYPE-CHECK T. We do two mostly -;;; unrelated things: detect compile-time type errors and determine if -;;; and how to do run-time type checks. +;;; looking for CASTs with TYPE-CHECK T. We do two mostly unrelated +;;; things: detect compile-time type errors and determine if and how +;;; to do run-time type checks. ;;; -;;; If there is a compile-time type error, then we mark the -;;; continuation and emit a warning if appropriate. This part loops -;;; over all the uses of the continuation, since after we convert the -;;; check, the :DELETED kind will inhibit warnings about the types of -;;; other uses. +;;; If there is a compile-time type error, then we mark the CAST and +;;; emit a warning if appropriate. This part loops over all the uses +;;; of the continuation, since after we convert the check, the +;;; :DELETED kind will inhibit warnings about the types of other uses. ;;; -;;; If a continuation is too complex to be checked by the back end, or -;;; is better checked with explicit code, then convert to an explicit +;;; If the cast is too complex to be checked by the back end, or is +;;; better checked with explicit code, then convert to an explicit ;;; test. Assertions that can checked by the back end are passed ;;; through. Assertions that can't be tested are flamed about and ;;; marked as not needing to be checked. @@ -466,15 +472,18 @@ (collect ((casts)) (do-blocks (block component) (when (block-type-check block) - (do-nodes (node cont block) + ;; CAST-EXTERNALLY-CHECKABLE-P wants the backward pass + (do-nodes-backwards (node nil block) (when (and (cast-p node) (cast-type-check node)) (cast-check-uses node) - (cond ((worth-type-check-p node) - (casts (cons node (not (probable-type-check-p node))))) + (cond ((cast-externally-checkable-p node) + (setf (cast-%type-check node) :external)) (t - (setf (cast-%type-check node) nil) - (setf (cast-type-to-check node) *wild-type*))))) + ;; it is possible that NODE was marked :EXTERNAL by + ;; the previous pass + (setf (cast-%type-check node) t) + (casts (cons node (not (probable-type-check-p node)))))))) (setf (block-type-check block) nil))) (dolist (cast (casts)) (destructuring-bind (cast . force-hairy) cast