(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)))
+ (values (type-singleton-p 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)
+ (if (and (ref-p use)
+ (constant-p (setf leaf (ref-leaf use))))
+ (constant-value leaf)
+ (multiple-value-bind (constantp value) (type-singleton-p type)
+ (unless constantp
+ (error "~S used on non-constant LVAR ~S" 'lvar-value lvar))
+ value))))
\f
;;;; interface for obtaining results of type inference
;;; 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))
(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.
(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))
(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)))
\f
;;;; IF optimization
-;;; If the test has multiple uses, replicate the node when possible.
-;;; Also check whether the predicate is known to be true or false,
+;;; Utility: return T if both argument cblocks are equivalent. For now,
+;;; detect only blocks that read the same leaf into the same lvar, and
+;;; continue to the same block.
+(defun cblocks-equivalent-p (x y)
+ (declare (type cblock x y))
+ (and (ref-p (block-start-node x))
+ (eq (block-last x) (block-start-node x))
+
+ (ref-p (block-start-node y))
+ (eq (block-last y) (block-start-node y))
+
+ (equal (block-succ x) (block-succ y))
+ (eql (ref-lvar (block-start-node x)) (ref-lvar (block-start-node y)))
+ (eql (ref-leaf (block-start-node x)) (ref-leaf (block-start-node y)))))
+
+;;; Check whether the predicate is known to be true or false,
;;; deleting the IF node in favor of the appropriate branch when this
;;; is the case.
+;;; Similarly, when both branches are equivalent, branch directly to either
+;;; of them.
+;;; Also, if the test has multiple uses, replicate the node when possible.
(defun ir1-optimize-if (node)
(declare (type cif node))
(let ((test (if-test node))
(block (node-block node)))
-
- (when (and (eq (block-start-node block) node)
- (listp (lvar-uses test)))
- (do-uses (use test)
- (when (immediately-used-p test use)
- (convert-if-if use node)
- (when (not (listp (lvar-uses test))) (return)))))
-
(let* ((type (lvar-type test))
+ (consequent (if-consequent node))
+ (alternative (if-alternative node))
(victim
(cond ((constant-lvar-p test)
- (if (lvar-value test)
- (if-alternative node)
- (if-consequent node)))
+ (if (lvar-value test) alternative consequent))
((not (types-equal-or-intersect type (specifier-type 'null)))
- (if-alternative node))
+ alternative)
((type= type (specifier-type 'null))
- (if-consequent node)))))
+ consequent)
+ ((cblocks-equivalent-p alternative consequent)
+ alternative))))
(when victim
(flush-dest test)
(when (rest (block-succ block))
(unlink-blocks block victim))
(setf (component-reanalyze (node-component node)) t)
- (unlink-node node))))
+ (unlink-node node)
+ (return-from ir1-optimize-if (values))))
+
+ (when (and (eq (block-start-node block) node)
+ (listp (lvar-uses test)))
+ (do-uses (use test)
+ (when (immediately-used-p test use)
+ (convert-if-if use node)
+ (when (not (listp (lvar-uses test))) (return))))))
(values))
;;; Create a new copy of an IF node that tests the value of the node
(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.
;;;
(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)
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))))
(let ((fun (defined-fun-functional leaf)))
(if (or (not fun)
(with-ir1-environment-from-node call
(frob)
(locall-analyze-component *current-component*)))
- ;; If we've already converted, change ref to the converted functional.
+ ;; If we've already converted, change ref to the converted
+ ;; functional.
(change-ref-leaf ref fun))))
(values (ref-leaf ref) nil))
(t
\f
;;;; 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)))
(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
;;; variable, we compute the union of the types across all calls and
;;; propagate this type information to the var's refs.
;;;
-;;; If the function has an XEP, then we don't do anything, since we
-;;; won't discover anything.
+;;; If the function has an entry-fun, then we don't do anything: since
+;;; it has a XEP we would not discover anything.
;;;
;;; We can clear the LVAR-REOPTIMIZE flags for arguments in all calls
;;; corresponding to changed arguments in CALL, since the only use in
;;; right here.
(defun propagate-local-call-args (call fun)
(declare (type combination call) (type clambda fun))
- (unless (or (functional-entry-fun fun)
- (lambda-optional-dispatch fun))
+ (unless (functional-entry-fun fun)
(let* ((vars (lambda-vars fun))
(union (mapcar (lambda (arg var)
(when (and arg