X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcompiler%2Fir1opt.lisp;h=d091f381e4353a5d08f0cd787f297184ccc502c0;hb=5745b5a5b2e3b967bf3876b4306f31b3c78495fa;hp=b8b00544c4cddf5b1c632beafdbe0a706ac3234e;hpb=5fb561a1daba0b6dbd76f7347d4b0fa4b02494a6;p=sbcl.git diff --git a/src/compiler/ir1opt.lisp b/src/compiler/ir1opt.lisp index b8b0054..d091f38 100644 --- a/src/compiler/ir1opt.lisp +++ b/src/compiler/ir1opt.lisp @@ -23,15 +23,28 @@ (defun constant-lvar-p (thing) (declare (type (or lvar null) thing)) (and (lvar-p thing) - (let ((use (principal-lvar-use thing))) - (and (ref-p use) (constant-p (ref-leaf use)))))) + (or (let ((use (principal-lvar-use thing))) + (and (ref-p use) (constant-p (ref-leaf use)))) + ;; check for EQL types (but not singleton numeric types) + (let ((type (lvar-type thing))) + (and (member-type-p type) + (eql 1 (member-type-size type))))))) ;;; Return the constant value for an LVAR whose only use is a constant ;;; node. (declaim (ftype (function (lvar) t) lvar-value)) (defun lvar-value (lvar) - (let ((use (principal-lvar-use lvar))) - (constant-value (ref-leaf use)))) + (let ((use (principal-lvar-use lvar)) + (type (lvar-type lvar)) + leaf) + (cond ((and (ref-p use) + (constant-p (setf leaf (ref-leaf use)))) + (constant-value leaf)) + ((and (member-type-p type) + (eql 1 (member-type-size type))) + (first (member-type-members type))) + (t + (error "~S used on non-constant LVAR ~S" 'lvar-value lvar))))) ;;;; interface for obtaining results of type inference @@ -42,6 +55,22 @@ ;;; The result value is cached in the LVAR-%DERIVED-TYPE slot. If the ;;; slot is true, just return that value, otherwise recompute and ;;; stash the value there. +(eval-when (:compile-toplevel :execute) + (#+sb-xc-host cl:defmacro + #-sb-xc-host sb!xc:defmacro + lvar-type-using (lvar accessor) + `(let ((uses (lvar-uses ,lvar))) + (cond ((null uses) *empty-type*) + ((listp uses) + (do ((res (,accessor (first uses)) + (values-type-union (,accessor (first current)) + res)) + (current (rest uses) (rest current))) + ((or (null current) (eq res *wild-type*)) + res))) + (t + (,accessor uses)))))) + #!-sb-fluid (declaim (inline lvar-derived-type)) (defun lvar-derived-type (lvar) (declare (type lvar lvar)) @@ -49,18 +78,7 @@ (setf (lvar-%derived-type lvar) (%lvar-derived-type lvar)))) (defun %lvar-derived-type (lvar) - (declare (type lvar lvar)) - (let ((uses (lvar-uses lvar))) - (cond ((null uses) *empty-type*) - ((listp uses) - (do ((res (node-derived-type (first uses)) - (values-type-union (node-derived-type (first current)) - res)) - (current (rest uses) (rest current))) - ((or (null current) (eq res *wild-type*)) - res))) - (t - (node-derived-type uses))))) + (lvar-type-using lvar node-derived-type)) ;;; Return the derived type for LVAR's first value. This is guaranteed ;;; not to be a VALUES or FUNCTION type. @@ -68,6 +86,112 @@ (defun lvar-type (lvar) (single-value-type (lvar-derived-type lvar))) +;;; LVAR-CONSERVATIVE-TYPE +;;; +;;; Certain types refer to the contents of an object, which can +;;; change without type derivation noticing: CONS types and ARRAY +;;; types suffer from this: +;;; +;;; (let ((x (the (cons fixnum fixnum) (cons a b)))) +;;; (setf (car x) c) +;;; (+ (car x) (cdr x))) +;;; +;;; Python doesn't realize that the SETF CAR can change the type of X -- so we +;;; cannot use LVAR-TYPE which gets the derived results. Worse, still, instead +;;; of (SETF CAR) we might have a call to a user-defined function FOO which +;;; does the same -- so there is no way to use the derived information in +;;; general. +;;; +;;; So, the conservative option is to use the derived type if the leaf has +;;; only a single ref -- in which case there cannot be a prior call that +;;; mutates it. Otherwise we use the declared type or punt to the most general +;;; type we know to be correct for sure. +(defun lvar-conservative-type (lvar) + (let ((derived-type (lvar-type lvar)) + (t-type *universal-type*)) + ;; Recompute using NODE-CONSERVATIVE-TYPE instead of derived type if + ;; necessary -- picking off some easy cases up front. + (cond ((or (eq derived-type t-type) + ;; Can't use CSUBTYPEP! + (type= derived-type (specifier-type 'list)) + (type= derived-type (specifier-type 'null))) + derived-type) + ((and (cons-type-p derived-type) + (eq t-type (cons-type-car-type derived-type)) + (eq t-type (cons-type-cdr-type derived-type))) + derived-type) + ((and (array-type-p derived-type) + (or (not (array-type-complexp derived-type)) + (let ((dimensions (array-type-dimensions derived-type))) + (or (eq '* dimensions) + (every (lambda (dim) (eq '* dim)) dimensions))))) + derived-type) + ((type-needs-conservation-p derived-type) + (single-value-type (lvar-type-using lvar node-conservative-type))) + (t + derived-type)))) + +(defun node-conservative-type (node) + (let* ((derived-values-type (node-derived-type node)) + (derived-type (single-value-type derived-values-type))) + (if (ref-p node) + (let ((leaf (ref-leaf node))) + (if (and (basic-var-p leaf) + (cdr (leaf-refs leaf))) + (coerce-to-values + (if (eq :declared (leaf-where-from leaf)) + (leaf-type leaf) + (conservative-type derived-type))) + derived-values-type)) + derived-values-type))) + +(defun conservative-type (type) + (cond ((or (eq type *universal-type*) + (eq type (specifier-type 'list)) + (eq type (specifier-type 'null))) + type) + ((cons-type-p type) + (specifier-type 'cons)) + ((array-type-p type) + (if (array-type-complexp type) + (make-array-type + ;; ADJUST-ARRAY may change dimensions, but rank stays same. + :dimensions + (let ((old (array-type-dimensions type))) + (if (eq '* old) + old + (mapcar (constantly '*) old))) + ;; Complexity cannot change. + :complexp (array-type-complexp type) + ;; Element type cannot change. + :element-type (array-type-element-type type) + :specialized-element-type (array-type-specialized-element-type type)) + ;; Simple arrays cannot change at all. + type)) + (t + ;; If the type contains some CONS types, the conservative type contains all + ;; of them. + (when (types-equal-or-intersect type (specifier-type 'cons)) + (setf type (type-union type (specifier-type 'cons)))) + ;; Similarly for non-simple arrays -- it should be possible to preserve + ;; more information here, but really... + (let ((non-simple-arrays (specifier-type '(and array (not simple-array))))) + (when (types-equal-or-intersect type non-simple-arrays) + (setf type (type-union type non-simple-arrays)))) + type))) + +(defun type-needs-conservation-p (type) + (cond ((eq type *universal-type*) + ;; Excluding T is necessary, because we do want type derivation to + ;; be able to narrow it down in case someone (most like a macro-expansion...) + ;; actually declares something as having type T. + nil) + ((or (cons-type-p type) (and (array-type-p type) (array-type-complexp type))) + ;; Covered by the next case as well, but this is a quick test. + t) + ((types-equal-or-intersect type (specifier-type '(or cons (and array (not simple-array))))) + t))) + ;;; If LVAR is an argument of a function, return a type which the ;;; function checks LVAR for. #!-sb-fluid (declaim (inline lvar-externally-checkable-type)) @@ -399,20 +523,8 @@ (delete-ref node) (unlink-node node)) (combination - (let ((kind (combination-kind node)) - (info (combination-fun-info node))) - (when (and (eq kind :known) (fun-info-p info)) - (let ((attr (fun-info-attributes info))) - (when (and (not (ir1-attributep attr call)) - ;; ### For now, don't delete potentially - ;; flushable calls when they have the CALL - ;; attribute. Someday we should look at the - ;; functional args to determine if they have - ;; any side effects. - (if (policy node (= safety 3)) - (ir1-attributep attr flushable) - (ir1-attributep attr unsafely-flushable))) - (flush-combination node)))))) + (when (flushable-combination-p node) + (flush-combination node))) (mv-combination (when (eq (basic-combination-kind node) :local) (let ((fun (combination-lambda node))) @@ -758,6 +870,14 @@ (values)) +(defun xep-tail-combination-p (node) + (and (combination-p node) + (let* ((lvar (combination-lvar node)) + (dest (when (lvar-p lvar) (lvar-dest lvar))) + (lambda (when (return-p dest) (return-lambda dest)))) + (and (lambda-p lambda) + (eq :external (lambda-kind lambda)))))) + ;;; If NODE doesn't return (i.e. return type is NIL), then terminate ;;; the block there, and link it to the component tail. ;;; @@ -783,7 +903,10 @@ (declare (ignore lvar)) (unless (or (and (eq node (block-last block)) (eq succ tail)) (block-delete-p block)) - (when (eq (node-derived-type node) *empty-type*) + ;; Even if the combination will never return, don't terminate if this + ;; is the tail call of a XEP: doing that would inhibit TCO. + (when (and (eq (node-derived-type node) *empty-type*) + (not (xep-tail-combination-p node))) (cond (ir1-converting-not-optimizing-p (cond ((block-last block) @@ -849,14 +972,18 @@ ((nil :maybe-inline) (policy call (zerop space)))) (defined-fun-p leaf) (defined-fun-inline-expansion leaf) - (let ((fun (defined-fun-functional leaf))) - (or (not fun) - (and (eq inlinep :inline) (functional-kind fun)))) (inline-expansion-ok call)) - (flet (;; FIXME: Is this what the old CMU CL internal documentation - ;; called semi-inlining? A more descriptive name would - ;; be nice. -- WHN 2002-01-07 - (frob () + ;; Inline: if the function has already been converted at another call + ;; site in this component, we point this REF to the functional. If not, + ;; we convert the expansion. + ;; + ;; For :INLINE case local call analysis will copy the expansion later, + ;; but for :MAYBE-INLINE and NIL cases we only get one copy of the + ;; expansion per component. + ;; + ;; FIXME: We also convert in :INLINE & FUNCTIONAL-KIND case below. What + ;; is it for? + (flet ((frob () (let* ((name (leaf-source-name leaf)) (res (ir1-convert-inline-expansion name @@ -864,18 +991,23 @@ leaf inlinep (info :function :info name)))) - ;; allow backward references to this function from - ;; following top level forms - (setf (defined-fun-functional leaf) res) + ;; Allow backward references to this function from following + ;; forms. (Reused only if policy matches.) + (push res (defined-fun-functionals leaf)) (change-ref-leaf ref res)))) - (if ir1-converting-not-optimizing-p - (frob) - (with-ir1-environment-from-node call - (frob) - (locall-analyze-component *current-component*)))) - - (values (ref-leaf (lvar-uses (basic-combination-fun call))) - nil)) + (let ((fun (defined-fun-functional leaf))) + (if (or (not fun) + (and (eq inlinep :inline) (functional-kind fun))) + ;; Convert. + (if ir1-converting-not-optimizing-p + (frob) + (with-ir1-environment-from-node call + (frob) + (locall-analyze-component *current-component*))) + ;; If we've already converted, change ref to the converted + ;; functional. + (change-ref-leaf ref fun)))) + (values (ref-leaf ref) nil)) (t (let ((info (info :function :info (leaf-source-name leaf)))) (if info @@ -1242,19 +1374,27 @@ ;;;; local call optimization -;;; Propagate TYPE to LEAF and its REFS, marking things changed. If -;;; the leaf type is a function type, then just leave it alone, since -;;; TYPE is never going to be more specific than that (and -;;; TYPE-INTERSECTION would choke.) +;;; Propagate TYPE to LEAF and its REFS, marking things changed. +;;; +;;; If the leaf type is a function type, then just leave it alone, since TYPE +;;; is never going to be more specific than that (and TYPE-INTERSECTION would +;;; choke.) +;;; +;;; Also, if the type is one requiring special care don't touch it if the leaf +;;; has multiple references -- otherwise LVAR-CONSERVATIVE-TYPE is screwed. (defun propagate-to-refs (leaf type) (declare (type leaf leaf) (type ctype type)) - (let ((var-type (leaf-type leaf))) - (unless (fun-type-p var-type) + (let ((var-type (leaf-type leaf)) + (refs (leaf-refs leaf))) + (unless (or (fun-type-p var-type) + (and (cdr refs) + (eq :declared (leaf-where-from leaf)) + (type-needs-conservation-p var-type))) (let ((int (type-approx-intersection2 var-type type))) (when (type/= int var-type) (setf (leaf-type leaf) int) (let ((s-int (make-single-value-type int))) - (dolist (ref (leaf-refs leaf)) + (dolist (ref refs) (derive-node-type ref s-int) ;; KLUDGE: LET var substitution (let* ((lvar (node-lvar ref))) @@ -1421,13 +1561,19 @@ (declare (type lvar arg) (type lambda-var var)) (binding* ((ref (first (leaf-refs var))) (lvar (node-lvar ref) :exit-if-null) - (dest (lvar-dest lvar))) + (dest (lvar-dest lvar)) + (dest-lvar (when (valued-node-p dest) (node-lvar dest)))) (when (and ;; Think about (LET ((A ...)) (IF ... A ...)): two ;; LVAR-USEs should not be met on one path. Another problem ;; is with dynamic-extent. (eq (lvar-uses lvar) ref) (not (block-delete-p (node-block ref))) + ;; If the destinatation is dynamic extent, don't substitute unless + ;; the source is as well. + (or (not dest-lvar) + (not (lvar-dynamic-extent dest-lvar)) + (lvar-dynamic-extent lvar)) (typecase dest ;; we should not change lifetime of unknown values lvars (cast