0.6.7.22: removed CVS dollar-Header-dollar tags from sources
[sbcl.git] / src / compiler / typetran.lisp
1 ;;;; This file contains stuff that implements the portable IR1
2 ;;;; semantics of type tests and coercion. The main thing we do is
3 ;;;; convert complex type operations into simpler code that can be
4 ;;;; compiled inline.
5
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.
14
15 (in-package "SB!C")
16 \f
17 ;;;; type predicate translation
18 ;;;;
19 ;;;; We maintain a bidirectional association between type predicates
20 ;;;; and the tested type. The presence of a predicate in this
21 ;;;; association implies that it is desirable to implement tests of
22 ;;;; this type using the predicate. These are either predicates that
23 ;;;; the back end is likely to have special knowledge about, or
24 ;;;; predicates so complex that the only reasonable implentation is
25 ;;;; via function call.
26 ;;;;
27 ;;;; Some standard types (such as SEQUENCE) are best tested by letting
28 ;;;; the TYPEP source transform do its thing with the expansion. These
29 ;;;; types (and corresponding predicates) are not maintained in this
30 ;;;; association. In this case, there need not be any predicate
31 ;;;; function unless it is required by the Common Lisp specification.
32 ;;;;
33 ;;;; The mapping between predicates and type structures is considered
34 ;;;; part of the backend; different backends can support different
35 ;;;; sets of predicates.
36
37 (defmacro define-type-predicate (name type)
38   #!+sb-doc
39   "Define-Type-Predicate Name Type
40   Establish an association between the type predicate Name and the
41   corresponding Type. This causes the type predicate to be recognized for
42   purposes of optimization."
43   `(%define-type-predicate ',name ',type))
44 (defun %define-type-predicate (name specifier)
45   (let ((type (specifier-type specifier)))
46     (setf (gethash name *backend-predicate-types*) type)
47     (setf *backend-type-predicates*
48           (cons (cons type name)
49                 (remove name *backend-type-predicates*
50                         :key #'cdr)))
51     (%deftransform name '(function (t) *) #'fold-type-predicate)
52     name))
53 \f
54 ;;;; IR1 transforms
55
56 ;;; If we discover the type argument is constant during IR1
57 ;;; optimization, then give the source transform another chance. The
58 ;;; source transform can't pass, since we give it an explicit
59 ;;; constant. At worst, it will convert to %TYPEP, which will prevent
60 ;;; spurious attempts at transformation (and possible repeated
61 ;;; warnings.)
62 (deftransform typep ((object type))
63   (unless (constant-continuation-p type)
64     (give-up-ir1-transform "can't open-code test of non-constant type"))
65   `(typep object ',(continuation-value type)))
66
67 ;;; If the continuation OBJECT definitely is or isn't of the specified
68 ;;; type, then return T or NIL as appropriate. Otherwise quietly
69 ;;; GIVE-UP-IR1-TRANSFORM.
70 (defun ir1-transform-type-predicate (object type)
71   (declare (type continuation object) (type ctype type))
72   (let ((otype (continuation-type object)))
73     (cond ((not (types-intersect otype type))
74            'nil)
75           ((csubtypep otype type)
76            't)
77           (t
78            (give-up-ir1-transform)))))
79
80 ;;; Flush %TYPEP tests whose result is known at compile time.
81 (deftransform %typep ((object type))
82   (unless (constant-continuation-p type) (give-up-ir1-transform))
83   (ir1-transform-type-predicate
84    object
85    (specifier-type (continuation-value type))))
86
87 ;;; This is the IR1 transform for simple type predicates. It checks
88 ;;; whether the single argument is known to (not) be of the
89 ;;; appropriate type, expanding to T or NIL as appropriate.
90 (deftransform fold-type-predicate ((object) * * :node node :defun-only t)
91   (let ((ctype (gethash (leaf-name
92                          (ref-leaf
93                           (continuation-use
94                            (basic-combination-fun node))))
95                         *backend-predicate-types*)))
96     (assert ctype)
97     (ir1-transform-type-predicate object ctype)))
98
99 ;;; If FIND-CLASS is called on a constant class, locate the CLASS-CELL
100 ;;; at load time.
101 (deftransform find-class ((name) ((constant-argument symbol)) *
102                           :when :both)
103   (let* ((name (continuation-value name))
104          (cell (find-class-cell name)))
105     `(or (class-cell-class ',cell)
106          (error "class not yet defined: ~S" name))))
107 \f
108 ;;;; standard type predicates
109
110 ;;; FIXME: needed only at cold load time, can be uninterned afterwards;
111 ;;; or perhaps could just be done at toplevel
112 (defun define-standard-type-predicates ()
113   (define-type-predicate arrayp array)
114   ; (The ATOM predicate is handled separately as (NOT CONS).)
115   (define-type-predicate bit-vector-p bit-vector)
116   (define-type-predicate characterp character)
117   (define-type-predicate compiled-function-p compiled-function)
118   (define-type-predicate complexp complex)
119   (define-type-predicate complex-rational-p (complex rational))
120   (define-type-predicate complex-float-p (complex float))
121   (define-type-predicate consp cons)
122   (define-type-predicate floatp float)
123   (define-type-predicate functionp function)
124   (define-type-predicate integerp integer)
125   (define-type-predicate keywordp keyword)
126   (define-type-predicate listp list)
127   (define-type-predicate null null)
128   (define-type-predicate numberp number)
129   (define-type-predicate rationalp rational)
130   (define-type-predicate realp real)
131   (define-type-predicate simple-bit-vector-p simple-bit-vector)
132   (define-type-predicate simple-string-p simple-string)
133   (define-type-predicate simple-vector-p simple-vector)
134   (define-type-predicate stringp string)
135   (define-type-predicate %instancep instance)
136   (define-type-predicate funcallable-instance-p funcallable-instance)
137   (define-type-predicate symbolp symbol)
138   (define-type-predicate vectorp vector))
139
140 (define-standard-type-predicates)
141 \f
142 ;;;; transforms for type predicates not implemented primitively
143 ;;;;
144 ;;;; See also VM dependent transforms.
145
146 (def-source-transform atom (x)
147   `(not (consp ,x)))
148 \f
149 ;;;; TYPEP source transform
150
151 ;;; Return a form that tests the variable N-Object for being in the binds
152 ;;; specified by Type. Base is the name of the base type, for declaration. We
153 ;;; make safety locally 0 to inhibit any checking of this assertion.
154 #!-negative-zero-is-not-zero
155 (defun transform-numeric-bound-test (n-object type base)
156   (declare (type numeric-type type))
157   (let ((low (numeric-type-low type))
158         (high (numeric-type-high type)))
159     `(locally
160        (declare (optimize (safety 0)))
161        (and ,@(when low
162                 (if (consp low)
163                     `((> (the ,base ,n-object) ,(car low)))
164                     `((>= (the ,base ,n-object) ,low))))
165             ,@(when high
166                 (if (consp high)
167                     `((< (the ,base ,n-object) ,(car high)))
168                     `((<= (the ,base ,n-object) ,high))))))))
169
170 #!+negative-zero-is-not-zero
171 (defun transform-numeric-bound-test (n-object type base)
172   (declare (type numeric-type type))
173   (let ((low (numeric-type-low type))
174         (high (numeric-type-high type))
175         (float-type-p (csubtypep type (specifier-type 'float)))
176         (x (gensym))
177         (y (gensym)))
178     `(locally
179        (declare (optimize (safety 0)))
180        (and ,@(when low
181                 (if (consp low)
182                     `((let ((,x (the ,base ,n-object))
183                             (,y ,(car low)))
184                         ,(if (not float-type-p)
185                             `(> ,x ,y)
186                             `(if (and (zerop ,x) (zerop ,y))
187                                  (> (float-sign ,x) (float-sign ,y))
188                                  (> ,x ,y)))))
189                     `((let ((,x (the ,base ,n-object))
190                             (,y ,low))
191                         ,(if (not float-type-p)
192                             `(>= ,x ,y)
193                             `(if (and (zerop ,x) (zerop ,y))
194                                  (>= (float-sign ,x) (float-sign ,y))
195                                  (>= ,x ,y)))))))
196             ,@(when high
197                 (if (consp high)
198                     `((let ((,x (the ,base ,n-object))
199                             (,y ,(car high)))
200                         ,(if (not float-type-p)
201                              `(< ,x ,y)
202                              `(if (and (zerop ,x) (zerop ,y))
203                                   (< (float-sign ,x) (float-sign ,y))
204                                   (< ,x ,y)))))
205                     `((let ((,x (the ,base ,n-object))
206                             (,y ,high))
207                         ,(if (not float-type-p)
208                              `(<= ,x ,y)
209                              `(if (and (zerop ,x) (zerop ,y))
210                                   (<= (float-sign ,x) (float-sign ,y))
211                                   (<= ,x ,y)))))))))))
212
213 ;;; Do source transformation of a test of a known numeric type. We can
214 ;;; assume that the type doesn't have a corresponding predicate, since
215 ;;; those types have already been picked off. In particular, CLASS
216 ;;; must be specified, since it is unspecified only in NUMBER and
217 ;;; COMPLEX. Similarly, we assume that COMPLEXP is always specified.
218 ;;;
219 ;;; For non-complex types, we just test that the number belongs to the
220 ;;; base type, and then test that it is in bounds. When CLASS is
221 ;;; INTEGER, we check to see whether the range is no bigger than
222 ;;; FIXNUM. If so, we check for FIXNUM instead of INTEGER. This allows
223 ;;; us to use fixnum comparison to test the bounds.
224 ;;;
225 ;;; For complex types, we must test for complex, then do the above on
226 ;;; both the real and imaginary parts. When CLASS is float, we need
227 ;;; only check the type of the realpart, since the format of the
228 ;;; realpart and the imagpart must be the same.
229 (defun source-transform-numeric-typep (object type)
230   (let* ((class (numeric-type-class type))
231          (base (ecase class
232                  (integer (containing-integer-type type))
233                  (rational 'rational)
234                  (float (or (numeric-type-format type) 'float))
235                  ((nil) 'real))))
236     (once-only ((n-object object))
237       (ecase (numeric-type-complexp type)
238         (:real
239          `(and (typep ,n-object ',base)
240                ,(transform-numeric-bound-test n-object type base)))
241         (:complex
242          `(and (complexp ,n-object)
243                ,(once-only ((n-real `(realpart (the complex ,n-object)))
244                             (n-imag `(imagpart (the complex ,n-object))))
245                   `(progn
246                      ,n-imag ; ignorable
247                      (and (typep ,n-real ',base)
248                           ,@(when (eq class 'integer)
249                               `((typep ,n-imag ',base)))
250                           ,(transform-numeric-bound-test n-real type base)
251                           ,(transform-numeric-bound-test n-imag type
252                                                          base))))))))))
253
254 ;;; Do the source transformation for a test of a hairy type. AND,
255 ;;; SATISFIES and NOT are converted into the obvious code. We convert
256 ;;; unknown types to %TYPEP, emitting an efficiency note if
257 ;;; appropriate.
258 (defun source-transform-hairy-typep (object type)
259   (declare (type hairy-type type))
260   (let ((spec (hairy-type-specifier type)))
261     (cond ((unknown-type-p type)
262            (when (policy nil (> speed brevity))
263              (compiler-note "can't open-code test of unknown type ~S"
264                             (type-specifier type)))
265            `(%typep ,object ',spec))
266           (t
267            (ecase (first spec)
268              (satisfies `(if (funcall #',(second spec) ,object) t nil))
269              ((not and)
270               (once-only ((n-obj object))
271                 `(,(first spec) ,@(mapcar #'(lambda (x)
272                                               `(typep ,n-obj ',x))
273                                           (rest spec))))))))))
274
275 ;;; Do source transformation for Typep of a known union type. If a
276 ;;; union type contains LIST, then we pull that out and make it into a
277 ;;; single LISTP call. Note that if SYMBOL is in the union, then LIST
278 ;;; will be a subtype even without there being any (member NIL). We
279 ;;; just drop through to the general code in this case, rather than
280 ;;; trying to optimize it.
281 (defun source-transform-union-typep (object type)
282   (let* ((types (union-type-types type))
283          (ltype (specifier-type 'list))
284          (mtype (find-if #'member-type-p types)))
285     (cond ((and mtype (csubtypep ltype type))
286            (let ((members (member-type-members mtype)))
287              (once-only ((n-obj object))
288                `(if (listp ,n-obj)
289                     t
290                     (typep ,n-obj
291                            '(or ,@(mapcar #'type-specifier
292                                           (remove (specifier-type 'cons)
293                                                   (remove mtype types)))
294                                 (member ,@(remove nil members))))))))
295           (t
296            (once-only ((n-obj object))
297              `(or ,@(mapcar #'(lambda (x)
298                                 `(typep ,n-obj ',(type-specifier x)))
299                             types)))))))
300
301 ;;; Return the predicate and type from the most specific entry in
302 ;;; *TYPE-PREDICATES* that is a supertype of TYPE.
303 (defun find-supertype-predicate (type)
304   (declare (type ctype type))
305   (let ((res nil)
306         (res-type nil))
307     (dolist (x *backend-type-predicates*)
308       (let ((stype (car x)))
309         (when (and (csubtypep type stype)
310                    (or (not res-type)
311                        (csubtypep stype res-type)))
312           (setq res-type stype)
313           (setq res (cdr x)))))
314     (values res res-type)))
315
316 ;;; Return forms to test that OBJ has the rank and dimensions
317 ;;; specified by TYPE, where STYPE is the type we have checked against
318 ;;; (which is the same but for dimensions.)
319 (defun test-array-dimensions (obj type stype)
320   (declare (type array-type type stype))
321   (let ((obj `(truly-the ,(type-specifier stype) ,obj))
322         (dims (array-type-dimensions type)))
323     (unless (eq dims '*)
324       (collect ((res))
325         (when (eq (array-type-dimensions stype) '*)
326           (res `(= (array-rank ,obj) ,(length dims))))
327         (do ((i 0 (1+ i))
328              (dim dims (cdr dim)))
329             ((null dim))
330           (let ((dim (car dim)))
331             (unless (eq dim '*)
332               (res `(= (array-dimension ,obj ,i) ,dim)))))
333         (res)))))
334
335 ;;; If we can find a type predicate that tests for the type w/o
336 ;;; dimensions, then use that predicate and test for dimensions.
337 ;;; Otherwise, just do %TYPEP.
338 (defun source-transform-array-typep (obj type)
339   (multiple-value-bind (pred stype) (find-supertype-predicate type)
340     (if (and (array-type-p stype)
341              ;; (If the element type hasn't been defined yet, it's
342              ;; not safe to assume here that it will eventually
343              ;; have (UPGRADED-ARRAY-ELEMENT-TYPE type)=T, so punt.)
344              (not (unknown-type-p (array-type-element-type type)))
345              (type= (array-type-specialized-element-type stype)
346                     (array-type-specialized-element-type type))
347              (eq (array-type-complexp stype) (array-type-complexp type)))
348         (once-only ((n-obj obj))
349           `(and (,pred ,n-obj)
350                 ,@(test-array-dimensions n-obj type stype)))
351         `(%typep ,obj ',(type-specifier type)))))
352
353 ;;; Transform a type test against some instance type. The type test is
354 ;;; flushed if the result is known at compile time. If not properly
355 ;;; named, error. If sealed and has no subclasses, just test for
356 ;;; layout-EQ. If a structure then test for layout-EQ and then a
357 ;;; general test based on layout-inherits. If safety is important,
358 ;;; then we also check whether the layout for the object is invalid
359 ;;; and signal an error if so. Otherwise, look up the indirect
360 ;;; class-cell and call CLASS-CELL-TYPEP at runtime.
361 ;;;
362 ;;; KLUDGE: The :WHEN :BOTH option here is probably a suboptimal
363 ;;; solution to the problem of %INSTANCE-TYPEP forms in byte compiled
364 ;;; code; it'd probably be better just to have %INSTANCE-TYPEP forms
365 ;;; never be generated in byte compiled code, or maybe to have a DEFUN
366 ;;; %INSTANCE-TYPEP somewhere to handle them if they are. But it's not
367 ;;; terribly important because mostly, %INSTANCE-TYPEP forms *aren't*
368 ;;; generated in byte compiled code. (As of sbcl-0.6.5, they could
369 ;;; sometimes be generated when byte compiling inline functions, but
370 ;;; it's quite uncommon.) -- WHN 20000523
371 (deftransform %instance-typep ((object spec) * * :when :both)
372   (assert (constant-continuation-p spec))
373   (let* ((spec (continuation-value spec))
374          (class (specifier-type spec))
375          (name (sb!xc:class-name class))
376          (otype (continuation-type object))
377          (layout (let ((res (info :type :compiler-layout name)))
378                    (if (and res (not (layout-invalid res)))
379                        res
380                        nil))))
381     (/noshow "entering DEFTRANSFORM %INSTANCE-TYPEP" otype spec class name layout)
382     (cond
383       ;; Flush tests whose result is known at compile time.
384       ((not (types-intersect otype class))
385        (/noshow "flushing constant NIL")
386        nil)
387       ((csubtypep otype class)
388        (/noshow "flushing constant T")
389        t)
390       ;; If not properly named, error.
391       ((not (and name (eq (sb!xc:find-class name) class)))
392        (compiler-error "can't compile TYPEP of anonymous or undefined ~
393                         class:~%  ~S"
394                        class))
395       (t
396        ;; Otherwise transform the type test.
397        (multiple-value-bind (pred get-layout)
398            (cond
399              ((csubtypep class (specifier-type 'funcallable-instance))
400               (values 'funcallable-instance-p '%funcallable-instance-layout))
401              ((csubtypep class (specifier-type 'instance))
402               (values '%instancep '%instance-layout))
403              (t
404               (values '(lambda (x) (declare (ignore x)) t) 'layout-of)))
405          (/noshow pred get-layout)
406          (cond
407            ((and (eq (class-state class) :sealed) layout
408                  (not (class-subclasses class)))
409             ;; Sealed and has no subclasses.
410             (/noshow "sealed and has no subclasses")
411             (let ((n-layout (gensym)))
412               `(and (,pred object)
413                     (let ((,n-layout (,get-layout object)))
414                       ,@(when (policy nil (>= safety speed))
415                               `((when (layout-invalid ,n-layout)
416                                   (%layout-invalid-error object ',layout))))
417                       (eq ,n-layout ',layout)))))
418            ((and (typep class 'basic-structure-class) layout)
419             (/noshow "structure type tests; hierarchical layout depths")
420             ;; structure type tests; hierarchical layout depths
421             (let ((depthoid (layout-depthoid layout))
422                   (n-layout (gensym)))
423               `(and (,pred object)
424                     (let ((,n-layout (,get-layout object)))
425                       ,@(when (policy nil (>= safety speed))
426                               `((when (layout-invalid ,n-layout)
427                                   (%layout-invalid-error object ',layout))))
428                       (if (eq ,n-layout ',layout)
429                           t
430                           (and (> (layout-depthoid ,n-layout)
431                                   ,depthoid)
432                                (locally (declare (optimize (safety 0)))
433                                  (eq (svref (layout-inherits ,n-layout)
434                                             ,depthoid)
435                                      ',layout))))))))
436            (t
437             (/noshow "default case -- ,PRED and CLASS-CELL-TYPEP")
438             `(and (,pred object)
439                   (class-cell-typep (,get-layout object)
440                                     ',(find-class-cell name)
441                                     object)))))))))
442
443 #|
444 ;;; Return (VALUES BEST-GUESS EXACT?), where BEST-GUESS is a CTYPE
445 ;;; which corresponds to the value returned by
446 ;;; CL:UPGRADED-ARRAY-ELEMENT-TYPE, and EXACT? tells whether that
447 ;;; result might change when we encounter a DEFTYPE.
448 (declaim (maybe-inline upgraded-array-element-ctype-2))
449 (defun upgraded-array-element-ctype-2 (spec)
450   (let ((ctype (specifier-type `(array ,spec))))
451     (values (array-type-specialized-element-type
452              (specifier-type `(array ,spec)))
453             (not (unknown-type-p (array-type-element-type ctype))))))
454 |#
455
456 ;;; If the specifier argument is a quoted constant, then we consider
457 ;;; converting into a simple predicate or other stuff. If the type is
458 ;;; constant, but we can't transform the call, then we convert to
459 ;;; %TYPEP. We only pass when the type is non-constant. This allows us
460 ;;; to recognize between calls that might later be transformed
461 ;;; successfully when a constant type is discovered. We don't give an
462 ;;; efficiency note when we pass, since the IR1 transform will give
463 ;;; one if necessary and appropriate.
464 ;;;
465 ;;; If the type is TYPE= to a type that has a predicate, then expand
466 ;;; to that predicate. Otherwise, we dispatch off of the type's type.
467 ;;; These transformations can increase space, but it is hard to tell
468 ;;; when, so we ignore policy and always do them. When byte-compiling,
469 ;;; we only do transforms that have potential for control
470 ;;; simplification. Instance type tests are converted to
471 ;;; %INSTANCE-TYPEP to allow type propagation.
472 (def-source-transform typep (object spec)
473   (if (and (consp spec) (eq (car spec) 'quote))
474       (let ((type (specifier-type (cadr spec))))
475         (or (let ((pred (cdr (assoc type *backend-type-predicates*
476                                     :test #'type=))))
477               (when pred `(,pred ,object)))
478             (typecase type
479               (hairy-type
480                (source-transform-hairy-typep object type))
481               (union-type
482                (source-transform-union-typep object type))
483               (member-type
484                `(member ,object ',(member-type-members type)))
485               (args-type
486                (compiler-warning "illegal type specifier for TYPEP: ~S"
487                                  (cadr spec))
488                `(%typep ,object ,spec))
489               (t nil))
490             (and (not (byte-compiling))
491                  (typecase type
492                    (numeric-type
493                     (source-transform-numeric-typep object type))
494                    (sb!xc:class
495                     `(%instance-typep ,object ,spec))
496                    (array-type
497                     (source-transform-array-typep object type))
498                    (t nil)))
499             `(%typep ,object ,spec)))
500       (values nil t)))
501 \f
502 ;;;; coercion
503
504 ;;; old working version
505 (deftransform coerce ((x type) (* *) * :when :both)
506   (unless (constant-continuation-p type)
507     (give-up-ir1-transform))
508   (let ((tspec (specifier-type (continuation-value type))))
509     (if (csubtypep (continuation-type x) tspec)
510         'x
511         `(the ,(continuation-value type)
512               ,(cond ((csubtypep tspec (specifier-type 'double-float))
513                       '(%double-float x))       
514                      ;; FIXME: If LONG-FLOAT is to be supported, we
515                      ;; need to pick it off here before falling through
516                      ;; to %SINGLE-FLOAT.
517                      ((csubtypep tspec (specifier-type 'float))
518                       '(%single-float x))
519                      (t
520                       (give-up-ir1-transform)))))))
521
522 ;;; KLUDGE: new broken version -- 20000504
523 #+nil
524 (deftransform coerce ((x type) (* *) * :when :both)
525   (unless (constant-continuation-p type)
526     (give-up-ir1-transform))
527   (let ((tspec (specifier-type (continuation-value type))))
528     (if (csubtypep (continuation-type x) tspec)
529         'x
530         `(if #+nil (typep x type) #-nil nil
531              x
532              (the ,(continuation-value type)
533                   ,(cond ((csubtypep tspec (specifier-type 'double-float))
534                           '(%double-float x))   
535                          ;; FIXME: If LONG-FLOAT is to be supported,
536                          ;; we need to pick it off here before falling
537                          ;; through to %SINGLE-FLOAT.
538                          ((csubtypep tspec (specifier-type 'float))
539                           '(%single-float x))
540                          #+nil
541                          ((csubtypep tspec (specifier-type 'list))
542                           '(coerce-to-list x))
543                          #+nil
544                          ((csubtypep tspec (specifier-type 'string))
545                           '(coerce-to-simple-string x))
546                          #+nil
547                          ((csubtypep tspec (specifier-type 'bit-vector))
548                           '(coerce-to-bit-vector x))
549                          #+nil
550                          ((csubtypep tspec (specifier-type 'vector))
551                           '(coerce-to-vector x type))
552                          (t
553                           (give-up-ir1-transform))))))))