(in-package "SB!C")
-;;; Convert into an IF so that IF optimizations will eliminate redundant
-;;; negations.
-(define-source-transform not (x) `(if ,x nil t))
-(define-source-transform null (x) `(if ,x nil t))
-
-;;; ENDP is just NULL with a LIST assertion. The assertion will be
-;;; optimized away when SAFETY optimization is low; hopefully that
-;;; is consistent with ANSI's "should return an error".
-(define-source-transform endp (x) `(null (the list ,x)))
-
;;; We turn IDENTITY into PROG1 so that it is obvious that it just
;;; returns the first value of its argument. Ditto for VALUES with one
;;; arg.
(define-source-transform identity (x) `(prog1 ,x))
(define-source-transform values (x) `(prog1 ,x))
-
;;; CONSTANTLY is pretty much never worth transforming, but it's good to get the type.
(defoptimizer (constantly derive-type) ((value))
(specifier-type
;;; whatever is right for them is right for us. FIFTH..TENTH turn into
;;; Nth, which can be expanded into a CAR/CDR later on if policy
;;; favors it.
-(define-source-transform first (x) `(car ,x))
(define-source-transform rest (x) `(cdr ,x))
(define-source-transform second (x) `(cadr ,x))
(define-source-transform third (x) `(caddr ,x))
(setf (cdr ,n-x) ,y)
,n-x)))
-(define-source-transform nth (n l) `(car (nthcdr ,n ,l)))
-
(deftransform last ((list &optional n) (t &optional t))
(let ((c (constant-lvar-p n)))
(cond ((or (not n)
(defun set-bound (x open-p)
(if (and x open-p) (list x) x))
-;;; Apply the function F to a bound X. If X is an open bound, then
-;;; the result will be open. IF X is NIL, the result is NIL.
-(defun bound-func (f x)
+;;; Apply the function F to a bound X. If X is an open bound and the
+;;; function is declared strictly monotonic, then the result will be
+;;; open. IF X is NIL, the result is NIL.
+(defun bound-func (f x strict)
(declare (type function f))
(and x
- (with-float-traps-masked (:underflow :overflow :inexact :divide-by-zero)
- ;; With these traps masked, we might get things like infinity
- ;; or negative infinity returned. Check for this and return
- ;; NIL to indicate unbounded.
- (let ((y (funcall f (type-bound-number x))))
- (if (and (floatp y)
- (float-infinity-p y))
- nil
- (set-bound y (consp x)))))))
+ (handler-case
+ (with-float-traps-masked (:underflow :overflow :inexact :divide-by-zero)
+ ;; With these traps masked, we might get things like infinity
+ ;; or negative infinity returned. Check for this and return
+ ;; NIL to indicate unbounded.
+ (let ((y (funcall f (type-bound-number x))))
+ (if (and (floatp y)
+ (float-infinity-p y))
+ nil
+ (set-bound y (and strict (consp x))))))
+ ;; Some numerical operations will signal SIMPLE-TYPE-ERROR, e.g.
+ ;; in the course of converting a bignum to a float. Default to
+ ;; NIL in that case.
+ (simple-type-error ()))))
(defun safe-double-coercion-p (x)
(or (typep x 'double-float)
(defun safe-single-coercion-p (x)
(or (typep x 'single-float)
- ;; Fix for bug 420, and related issues: during type derivation we often
- ;; end up deriving types for both
- ;;
- ;; (some-op <int> <single>)
- ;; and
- ;; (some-op (coerce <int> 'single-float) <single>)
- ;;
- ;; or other equivalent transformed forms. The problem with this is that
- ;; on some platforms like x86 (+ <int> <single>) is on the machine level
- ;; equivalent of
- ;;
- ;; (coerce (+ (coerce <int> 'double-float)
- ;; (coerce <single> 'double-float))
- ;; 'single-float)
- ;;
- ;; so if the result of (coerce <int> 'single-float) is not exact, the
- ;; derived types for the transformed forms will have an empty
- ;; intersection -- which in turn means that the compiler will conclude
- ;; that the call never returns, and all hell breaks lose when it *does*
- ;; return at runtime. (This affects not just +, but other operators are
- ;; well.)
- (and (not (typep x `(or (integer * (,most-negative-exactly-single-float-fixnum))
- (integer (,most-positive-exactly-single-float-fixnum) *))))
- (<= most-negative-single-float x most-positive-single-float))))
+ (and
+ ;; Fix for bug 420, and related issues: during type derivation we often
+ ;; end up deriving types for both
+ ;;
+ ;; (some-op <int> <single>)
+ ;; and
+ ;; (some-op (coerce <int> 'single-float) <single>)
+ ;;
+ ;; or other equivalent transformed forms. The problem with this
+ ;; is that on x86 (+ <int> <single>) is on the machine level
+ ;; equivalent of
+ ;;
+ ;; (coerce (+ (coerce <int> 'double-float)
+ ;; (coerce <single> 'double-float))
+ ;; 'single-float)
+ ;;
+ ;; so if the result of (coerce <int> 'single-float) is not exact, the
+ ;; derived types for the transformed forms will have an empty
+ ;; intersection -- which in turn means that the compiler will conclude
+ ;; that the call never returns, and all hell breaks lose when it *does*
+ ;; return at runtime. (This affects not just +, but other operators are
+ ;; well.)
+ ;;
+ ;; See also: SAFE-CTYPE-FOR-SINGLE-COERCION-P
+ ;;
+ ;; FIXME: If we ever add SSE-support for x86, this conditional needs to
+ ;; change.
+ #!+x86
+ (not (typep x `(or (integer * (,most-negative-exactly-single-float-fixnum))
+ (integer (,most-positive-exactly-single-float-fixnum) *))))
+ (<= most-negative-single-float x most-positive-single-float))))
;;; Apply a binary operator OP to two bounds X and Y. The result is
;;; NIL if either is NIL. Otherwise bound is computed and the result
`(and (not (fp-zero-p ,xb))
(not (fp-zero-p ,yb))))))))))))
+(defun coercion-loses-precision-p (val type)
+ (typecase val
+ (single-float)
+ (double-float (subtypep type 'single-float))
+ (rational (subtypep type 'float))
+ (t (bug "Unexpected arguments to bounds coercion: ~S ~S" val type))))
+
(defun coerce-for-bound (val type)
(if (consp val)
- (list (coerce-for-bound (car val) type))
+ (let ((xbound (coerce-for-bound (car val) type)))
+ (if (coercion-loses-precision-p (car val) type)
+ xbound
+ (list xbound)))
(cond
((subtypep type 'double-float)
(if (<= most-negative-double-float val most-positive-double-float)
(defun coerce-and-truncate-floats (val type)
(when val
(if (consp val)
- (list (coerce-and-truncate-floats (car val) type))
+ (let ((xbound (coerce-for-bound (car val) type)))
+ (if (coercion-loses-precision-p (car val) type)
+ xbound
+ (list xbound)))
(cond
((subtypep type 'double-float)
(if (<= most-negative-double-float val most-positive-double-float)
:high (copy-interval-limit (interval-high x))))
;;; Given a point P contained in the interval X, split X into two
-;;; interval at the point P. If CLOSE-LOWER is T, then the left
+;;; intervals at the point P. If CLOSE-LOWER is T, then the left
;;; interval contains P. If CLOSE-UPPER is T, the right interval
;;; contains P. You can specify both to be T or NIL.
(defun interval-split (p x &optional close-lower close-upper)
;;; the negative of an interval
(defun interval-neg (x)
(declare (type interval x))
- (make-interval :low (bound-func #'- (interval-high x))
- :high (bound-func #'- (interval-low x))))
+ (make-interval :low (bound-func #'- (interval-high x) t)
+ :high (bound-func #'- (interval-low x) t)))
;;; Add two intervals.
(defun interval-add (x y)
((zerop (type-bound-number y))
;; Divide by zero means result is infinity
nil)
- ((and (numberp x) (zerop x))
- ;; Zero divided by anything is zero.
- x)
(t
(bound-binop / x y)))))
(let ((top-range (interval-range-info top))
;;; Apply the function F to the interval X. If X = [a, b], then the
;;; result is [f(a), f(b)]. It is up to the user to make sure the
-;;; result makes sense. It will if F is monotonic increasing (or
-;;; non-decreasing).
-(defun interval-func (f x)
+;;; result makes sense. It will if F is monotonic increasing (or, if
+;;; the interval is closed, non-decreasing).
+;;;
+;;; (Actually most uses of INTERVAL-FUNC are coercions to float types,
+;;; which are not monotonic increasing, so default to calling
+;;; BOUND-FUNC with a non-strict argument).
+(defun interval-func (f x &optional increasing)
(declare (type function f)
(type interval x))
- (let ((lo (bound-func f (interval-low x)))
- (hi (bound-func f (interval-high x))))
+ (let ((lo (bound-func f (interval-low x) increasing))
+ (hi (bound-func f (interval-high x) increasing)))
(make-interval :low lo :high hi)))
;;; Return T if X < Y. That is every number in the interval X is
;;; Compute the square of an interval.
(defun interval-sqr (x)
(declare (type interval x))
- (interval-func (lambda (x) (* x x))
- (interval-abs x)))
+ (interval-func (lambda (x) (* x x)) (interval-abs x)))
\f
;;;; numeric DERIVE-TYPE methods
;;; a utility for defining derive-type methods of integer operations. If
;;; the types of both X and Y are integer types, then we compute a new
-;;; integer type with bounds determined Fun when applied to X and Y.
+;;; integer type with bounds determined by FUN when applied to X and Y.
;;; Otherwise, we use NUMERIC-CONTAGION.
(defun derive-integer-type-aux (x y fun)
(declare (type function fun))
(if (and divisor-low divisor-high)
;; We know the range of the divisor, and the remainder must be
;; smaller than the divisor. We can tell the sign of the
- ;; remainer if we know the sign of the number.
+ ;; remainder if we know the sign of the number.
(let ((divisor-max (1- (max (abs divisor-low) (abs divisor-high)))))
`(integer ,(if (or (null number-low)
(minusp number-low))
divisor-max
0)))
;; The divisor is potentially either very positive or very
- ;; negative. Therefore, the remainer is unbounded, but we might
+ ;; negative. Therefore, the remainder is unbounded, but we might
;; be able to tell something about the sign from the number.
`(integer ,(if (and number-low (not (minusp number-low)))
;; The number we are dividing is positive.
(reoptimize-component (node-component node) :maybe))
(cut-node (node &aux did-something)
(when (and (not (block-delete-p (node-block node)))
+ (ref-p node)
+ (constant-p (ref-leaf node)))
+ (let* ((constant-value (constant-value (ref-leaf node)))
+ (new-value (if signedp
+ (mask-signed-field width constant-value)
+ (ldb (byte width 0) constant-value))))
+ (unless (= constant-value new-value)
+ (change-ref-leaf node (make-constant new-value))
+ (setf (lvar-%derived-type (node-lvar node)) (make-values-type :required (list (ctype-of new-value))))
+ (setf (block-reoptimize (node-block node)) t)
+ (reoptimize-component (node-component node) :maybe)
+ (return-from cut-node t))))
+ (when (and (not (block-delete-p (node-block node)))
(combination-p node)
(eq (basic-combination-kind node) :known))
(let* ((fun-ref (lvar-use (combination-fun node)))
(best-modular-version width nil)
(when w
;; FIXME: This should be (CUT-TO-WIDTH NODE KIND WIDTH SIGNEDP).
- (cut-to-width x kind width signedp)
- (cut-to-width y kind width signedp)
- nil ; After fixing above, replace with T.
+ ;;
+ ;; FIXME: I think the FIXME (which is from APD) above
+ ;; implies that CUT-TO-WIDTH should do /everything/
+ ;; that's required, including reoptimizing things
+ ;; itself that it knows are necessary. At the moment,
+ ;; CUT-TO-WIDTH sets up some new calls with
+ ;; combination-type :FULL, which later get noticed as
+ ;; known functions and properly converted.
+ ;;
+ ;; We cut to W not WIDTH if SIGNEDP is true, because
+ ;; signed constant replacement needs to know which bit
+ ;; in the field is the signed bit.
+ (let ((xact (cut-to-width x kind (if signedp w width) signedp))
+ (yact (cut-to-width y kind (if signedp w width) signedp)))
+ (declare (ignore xact yact))
+ nil) ; After fixing above, replace with T, meaning
+ ; "don't reoptimize this (LOGAND) node any more".
))))))))
(defoptimizer (mask-signed-field optimizer) ((width x) node)
(when (and (numberp low) (numberp high))
(let ((width (max (integer-length high) (integer-length low))))
(multiple-value-bind (w kind)
- (best-modular-version width t)
+ (best-modular-version (1+ width) t)
(when w
- ;; FIXME: This should be (CUT-TO-WIDTH NODE KIND WIDTH T).
- (cut-to-width x kind width t)
+ ;; FIXME: This should be (CUT-TO-WIDTH NODE KIND W T).
+ ;; [ see comment above in LOGAND optimizer ]
+ (cut-to-width x kind w t)
nil ; After fixing above, replace with T.
))))))))
\f
(def round)
(def floor)
(def ceiling))
+
+(macrolet ((def (name &optional float)
+ (let ((x (if float '(float x) 'x)))
+ `(deftransform ,name ((x y) (integer (constant-arg (member 1 -1)))
+ *)
+ "fold division by 1"
+ `(values ,(if (minusp (lvar-value y))
+ '(%negate ,x)
+ ',x) 0)))))
+ (def truncate)
+ (def round)
+ (def floor)
+ (def ceiling)
+ (def ftruncate t)
+ (def fround t)
+ (def ffloor t)
+ (def fceiling t))
+
\f
;;;; character operations
(define-source-transform > (&rest args) (multi-compare '> args nil 'real))
;;; We cannot do the inversion for >= and <= here, since both
;;; (< NaN X) and (> NaN X)
-;;; are false, and we don't have type-inforation available yet. The
+;;; are false, and we don't have type-information available yet. The
;;; deftransforms for two-argument versions of >= and <= takes care of
;;; the inversion to > and < when possible.
(define-source-transform <= (&rest args) (multi-compare '<= args nil 'real))
,@(mapcar (lambda (x) `(values ,x)) (butlast args))
(values-list ,(car (last args))))))
-;;; When &REST argument are at play, we also have extra context and count
-;;; arguments -- convert to %VALUES-LIST-OR-CONTEXT when possible, so that the
-;;; deftransform can decide what to do after everything has been converted.
-(define-source-transform values-list (list)
- (if (symbolp list)
- (let* ((var (lexenv-find list vars))
- (info (when (lambda-var-p var)
- (lambda-var-arg-info var))))
- (if (and info
+;;;; transforming references to &REST argument
+
+;;; We add magical &MORE arguments to all functions with &REST. If ARG names
+;;; the &REST argument, this returns the lambda-vars for the context and
+;;; count.
+(defun possible-rest-arg-context (arg)
+ (when (symbolp arg)
+ (let* ((var (lexenv-find arg vars))
+ (info (when (lambda-var-p var)
+ (lambda-var-arg-info var))))
+ (when (and info
(eq :rest (arg-info-kind info))
(consp (arg-info-default info)))
- (destructuring-bind (context count &optional used) (arg-info-default info)
- (declare (ignore used))
- `(%values-list-or-context ,list ,context ,count))
- (values nil t)))
- (values nil t)))
-
-(deftransform %values-list-or-context ((list context count) * * :node node)
- (let* ((use (lvar-use list))
+ (values-list (arg-info-default info))))))
+
+(defun mark-more-context-used (rest-var)
+ (let ((info (lambda-var-arg-info rest-var)))
+ (aver (eq :rest (arg-info-kind info)))
+ (destructuring-bind (context count &optional used) (arg-info-default info)
+ (unless used
+ (setf (arg-info-default info) (list context count t))))))
+
+(defun mark-more-context-invalid (rest-var)
+ (let ((info (lambda-var-arg-info rest-var)))
+ (aver (eq :rest (arg-info-kind info)))
+ (setf (arg-info-default info) t)))
+
+;;; This determines of we the REF to a &REST variable is headed towards
+;;; parts unknown, or if we can really use the context.
+(defun rest-var-more-context-ok (lvar)
+ (let* ((use (lvar-use lvar))
(var (when (ref-p use) (ref-leaf use)))
(home (when (lambda-var-p var) (lambda-var-home var)))
- (info (when (lambda-var-p var) (lambda-var-arg-info var))))
+ (info (when (lambda-var-p var) (lambda-var-arg-info var)))
+ (restp (when info (eq :rest (arg-info-kind info)))))
(flet ((ref-good-for-more-context-p (ref)
(let ((dest (principal-lvar-end (node-lvar ref))))
(and (combination-p dest)
- ;; Uses outside VALUES-LIST will require a &REST list anyways,
- ;; to it's no use saving effort here -- plus they might modify
- ;; the list destructively.
- (eq '%values-list-or-context (lvar-fun-name (combination-fun dest)))
+ ;; If the destination is to anything but these, we're going to
+ ;; actually need the rest list -- and since other operations
+ ;; might modify the list destructively, the using the context
+ ;; isn't good anywhere else either.
+ (lvar-fun-is (combination-fun dest)
+ '(%rest-values %rest-ref %rest-length
+ %rest-null %rest-true))
;; If the home lambda is different and isn't DX, it might
;; escape -- in which case using the more context isn't safe.
(let ((clambda (node-home-lambda dest)))
(or (eq home clambda)
(leaf-dynamic-extent clambda)))))))
- (let ((context-ok
- (and info
- (consp (arg-info-default info))
- (not (lambda-var-specvar var))
- (not (lambda-var-sets var))
- (every #'ref-good-for-more-context-p (lambda-var-refs var))
- (policy node (= 3 rest-conversion)))))
- (cond (context-ok
- (destructuring-bind (context count &optional used) (arg-info-default info)
- (declare (ignore used))
- (setf (arg-info-default info) (list context count t)))
- `(%more-arg-values context 0 count))
- (t
- (when info
- (setf (arg-info-default info) t))
- `(values-list list)))))))
-
+ (let ((ok (and restp
+ (consp (arg-info-default info))
+ (not (lambda-var-specvar var))
+ (not (lambda-var-sets var))
+ (every #'ref-good-for-more-context-p (lambda-var-refs var)))))
+ (if ok
+ (mark-more-context-used var)
+ (when restp
+ (mark-more-context-invalid var)))
+ ok))))
+
+;;; VALUES-LIST -> %REST-VALUES
+(define-source-transform values-list (list)
+ (multiple-value-bind (context count) (possible-rest-arg-context list)
+ (if context
+ `(%rest-values ,list ,context ,count)
+ (values nil t))))
+
+;;; NTH -> %REST-REF
+(define-source-transform nth (n list)
+ (multiple-value-bind (context count) (possible-rest-arg-context list)
+ (if context
+ `(%rest-ref ,n ,list ,context ,count)
+ `(car (nthcdr ,n ,list)))))
+
+(define-source-transform elt (seq n)
+ (multiple-value-bind (context count) (possible-rest-arg-context seq)
+ (if context
+ `(%rest-ref ,n ,seq ,context ,count)
+ (values nil t))))
+
+;;; CAR/FIRST -> %REST-REF
+(defun source-transform-car (list)
+ (multiple-value-bind (context count) (possible-rest-arg-context list)
+ (if context
+ `(%rest-ref 0 ,list ,context ,count)
+ (values nil t))))
+(define-source-transform car (list)
+ (source-transform-car list))
+(define-source-transform first (list)
+ (or (source-transform-car list)
+ `(car ,list)))
+
+;;; LENGTH -> %REST-LENGTH
+(defun source-transform-length (list)
+ (multiple-value-bind (context count) (possible-rest-arg-context list)
+ (if context
+ `(%rest-length ,list ,context ,count)
+ (values nil t))))
+(define-source-transform length (list) (source-transform-length list))
+(define-source-transform list-length (list) (source-transform-length list))
+
+;;; ENDP, NULL and NOT -> %REST-NULL
+;;;
+;;; Outside &REST convert into an IF so that IF optimizations will eliminate
+;;; redundant negations.
+(defun source-transform-null (x op)
+ (multiple-value-bind (context count) (possible-rest-arg-context x)
+ (cond (context
+ `(%rest-null ',op ,x ,context ,count))
+ ((eq 'endp op)
+ `(if (the list ,x) nil t))
+ (t
+ `(if ,x nil t)))))
+(define-source-transform not (x) (source-transform-null x 'not))
+(define-source-transform null (x) (source-transform-null x 'null))
+(define-source-transform endp (x) (source-transform-null x 'endp))
+
+(deftransform %rest-values ((list context count))
+ (if (rest-var-more-context-ok list)
+ `(%more-arg-values context 0 count)
+ `(values-list list)))
+
+(deftransform %rest-ref ((n list context count))
+ (cond ((rest-var-more-context-ok list)
+ `(%more-arg context n))
+ ((and (constant-lvar-p n) (zerop (lvar-value n)))
+ `(car list))
+ (t
+ `(nth n list))))
+
+(deftransform %rest-length ((list context count))
+ (if (rest-var-more-context-ok list)
+ 'count
+ `(length list)))
+
+(deftransform %rest-null ((op list context count))
+ (aver (constant-lvar-p op))
+ (if (rest-var-more-context-ok list)
+ `(eql 0 count)
+ `(,(lvar-value op) list)))
+
+(deftransform %rest-true ((list context count))
+ (if (rest-var-more-context-ok list)
+ `(not (eql 0 count))
+ `list))
\f
;;;; transforming FORMAT
;;;;
projects / sbcl.git / blobdiff