| blob | 8733eb43f5b486b27c17818fd33b5eb641d17c37 |
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.
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.
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 ATOM) are best tested by letting the
28 ;;;; 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.
37 ;;; Establish an association between the type predicate NAME and the
38 ;;; corresponding TYPE. This causes the type predicate to be
39 ;;; recognized for purposes of optimization.
50 name))
51 \f
52 ;;;; IR1 transforms
54 ;;; If we discover the type argument is constant during IR1
55 ;;; optimization, then give the source transform another chance. The
56 ;;; source transform can't pass, since we give it an explicit
57 ;;; constant. At worst, it will convert to %TYPEP, which will prevent
58 ;;; spurious attempts at transformation (and possible repeated
59 ;;; warnings.)
69 expansion)))
71 ;;; If the lvar OBJECT definitely is or isn't of the specified
72 ;;; type, then return T or NIL as appropriate. Otherwise quietly
73 ;;; GIVE-UP-IR1-TRANSFORM.
79 ;; We don't transform alien type tests until here, because
80 ;; once we do that the rest of the type system can no longer
81 ;; reason about them properly -- so we'd miss out on type
82 ;; derivation, etc.
85 ;; If it's a lisp-rep-type, the CTYPE should be one already.
91 nil)
93 t)
95 nil)
106 ;;; Flush %TYPEP tests whose result is known at compile time.
111 object
113 node))
115 ;;; This is the IR1 transform for simple type predicates. It checks
116 ;;; whether the single argument is known to (not) be of the
117 ;;; appropriate type, expanding to T or NIL as appropriate.
127 ;;; If FIND-CLASSOID is called on a constant class, locate the
128 ;;; CLASSOID-CELL at load time.
134 \f
135 ;;;; standard type predicates, i.e. those defined in package COMMON-LISP,
136 ;;;; plus at least one oddball (%INSTANCEP)
137 ;;;;
138 ;;;; Various other type predicates (e.g. low-level representation
139 ;;;; stuff like SIMPLE-ARRAY-SINGLE-FLOAT-P) are defined elsewhere.
141 ;;; FIXME: This function is only called once, at top level. Why not
142 ;;; just expand all its operations into toplevel code?
145 ; (The ATOM predicate is handled separately as (NOT CONS).)
173 \f
174 ;;;; transforms for type predicates not implemented primitively
175 ;;;;
176 ;;;; See also VM dependent transforms.
180 #!+sb-unicode
183 \f
184 ;;;; TYPEP source transform
186 ;;; Return a form that tests the variable N-OBJECT for being in the
187 ;;; binds specified by TYPE. BASE is the name of the base type, for
188 ;;; declaration. We make SAFETY locally 0 to inhibit any checking of
189 ;;; this assertion.
205 ;;; Do source transformation of a test of a known numeric type. We can
206 ;;; assume that the type doesn't have a corresponding predicate, since
207 ;;; those types have already been picked off. In particular, CLASS
208 ;;; must be specified, since it is unspecified only in NUMBER and
209 ;;; COMPLEX. Similarly, we assume that COMPLEXP is always specified.
210 ;;;
211 ;;; For non-complex types, we just test that the number belongs to the
212 ;;; base type, and then test that it is in bounds. When CLASS is
213 ;;; INTEGER, we check to see whether the range is no bigger than
214 ;;; FIXNUM. If so, we check for FIXNUM instead of INTEGER. This allows
215 ;;; us to use fixnum comparison to test the bounds.
216 ;;;
217 ;;; For complex types, we must test for complex, then do the above on
218 ;;; both the real and imaginary parts. When CLASS is float, we need
219 ;;; only check the type of the realpart, since the format of the
220 ;;; realpart and the imagpart must be the same.
228 type)))
234 (:real
236 nil
243 (:complex
254 base))))))))))
256 ;;; Do the source transformation for a test of a hairy type. AND,
257 ;;; SATISFIES and NOT are converted into the obvious code. We convert
258 ;;; unknown types to %TYPEP, emitting an efficiency note if
259 ;;; appropriate.
283 ;;; Do source transformation for TYPEP of a known union type. If a
284 ;;; union type contains LIST, then we pull that out and make it into a
285 ;;; single LISTP call. Note that if SYMBOL is in the union, then LIST
286 ;;; will be a subtype even without there being any (member NIL). We
287 ;;; currently just drop through to the general code in this case,
288 ;;; rather than trying to optimize it (but FIXME CSR 2004-04-05: it
289 ;;; wouldn't be hard to optimize it after all).
308 types))))))
310 ;;; Do source transformation for TYPEP of a known intersection type.
317 ;;; If necessary recurse to check the cons type.
346 collect
349 #!+sb-simd-pack
363 ;;; Return the predicate and type from the most specific entry in
364 ;;; *TYPE-PREDICATES* that is a supertype of TYPE.
378 ;;; Return forms to test that OBJ has the rank and dimensions
379 ;;; specified by TYPE, where STYPE is the type we have checked against
380 ;;; (which is the same but for dimensions and element type).
381 ;;;
382 ;;; Secondary return value is true if passing the generated tests implies that
383 ;;; the array has a header.
395 for i from 0
398 t))
402 t))
407 nil)
412 nil)))
418 nil))))))
420 ;;; Return forms to test that OBJ has the element-type specified by type
421 ;;; specified by TYPE, where STYPE is the type we have checked against (which
422 ;;; is the same but for dimensions and element type). If HEADERP is true, OBJ
423 ;;; is guaranteed to be an array-header.
433 ;; If we know OBJ is an array header, and that the array is
434 ;; simple, we also know there is exactly one indirection to
435 ;; follow.
442 ;;; If we can find a type predicate that tests for the type without
443 ;;; dimensions, then use that predicate and test for dimensions.
444 ;;; Otherwise, just do %TYPEP.
448 ;; (If the element type hasn't been defined yet, it's
449 ;; not safe to assume here that it will eventually
450 ;; have (UPGRADED-ARRAY-ELEMENT-TYPE type)=T, so punt.)
461 ;; KLUDGE: this is a bit lame; if we get here,
462 ;; we already know that N-OBJ is an array, but
463 ;; (NOT SIMPLE-ARRAY) doesn't know that. On the
464 ;; other hand, this should get compiled down to
465 ;; two widetag tests, so it's only a bit lame.
467 ,@tests
471 ;;; Transform a type test against some instance type. The type test is
472 ;;; flushed if the result is known at compile time. If not properly
473 ;;; named, error. If sealed and has no subclasses, just test for
474 ;;; layout-EQ. If a structure then test for layout-EQ and then a
475 ;;; general test based on layout-inherits. If safety is important,
476 ;;; then we also check whether the layout for the object is invalid
477 ;;; and signal an error if so. Otherwise, look up the indirect
478 ;;; class-cell and call CLASS-CELL-TYPEP at runtime.
487 res
488 nil))))
490 ;; Flush tests whose result is known at compile time.
492 nil)
494 t)
495 ;; If not properly named, error.
498 class:~% ~S"
499 class))
501 ;; Delay the type transform to give type propagation a chance.
504 ;; Otherwise transform the type test.
516 ;; Sealed and has no subclasses.
525 ;; structure type tests; hierarchical layout depths
530 ;; we used to check for invalid layouts here,
531 ;; but in fact that's both unnecessary and
532 ;; wrong; it's unnecessary because structure
533 ;; classes can't be redefined, and it's wrong
534 ;; because it is quite legitimate to pass an
535 ;; object with an invalid layout to a structure
536 ;; type test.
538 t
542 ;; Use DATA-VECTOR-REF directly,
543 ;; since that's what SVREF in a
544 ;; SAFETY 0 lexenv will eventually be
545 ;; transformed to. This can give a
546 ;; large compilation speedup, since
547 ;; %INSTANCE-TYPEPs are frequently
548 ;; created during GENERATE-TYPE-CHECKS,
549 ;; and the normal aref transformation path
550 ;; is pretty heavy.
555 ;; hierarchical layout depths for other things (e.g.
556 ;; CONDITION, STREAM)
566 t
570 ;; See above.
578 object)))))))))
580 ;;; If the specifier argument is a quoted constant, then we consider
581 ;;; converting into a simple predicate or other stuff. If the type is
582 ;;; constant, but we can't transform the call, then we convert to
583 ;;; %TYPEP. We only pass when the type is non-constant. This allows us
584 ;;; to recognize between calls that might later be transformed
585 ;;; successfully when a constant type is discovered. We don't give an
586 ;;; efficiency note when we pass, since the IR1 transform will give
587 ;;; one if necessary and appropriate.
588 ;;;
589 ;;; If the type is TYPE= to a type that has a predicate, then expand
590 ;;; to that predicate. Otherwise, we dispatch off of the type's type.
591 ;;; These transformations can increase space, but it is hard to tell
592 ;;; when, so we ignore policy and always do them.
630 #!+sb-simd-pack
637 ;; KLUDGE: It looks bad to only do this on explicitly quoted forms,
638 ;; since that would overlook other kinds of constants. But it turns
639 ;; out that the DEFTRANSFORM for TYPEP detects any constant
640 ;; lvar, transforms it into a quoted form, and gives this
641 ;; source transform another chance, so it all works out OK, in a
642 ;; weird roundabout way. -- WHN 2001-03-18
650 \f
651 ;;;; coercion
653 ;;; Constant-folding.
654 ;;;
655 #-sb-xc-host
661 t))))
663 ;;; Drops dimension information from vector types.
668 'simple-array
684 etype
685 complexp))))))))
693 'x
694 ;; Note: The THE forms we use to wrap the results make sure that
695 ;; specifiers like (SINGLE-FLOAT 0.0 1.0) can raise a TYPE-ERROR.
699 ;; FIXME: #!+long-float (t ,(error "LONG-FLOAT case needed"))
702 ;; Special case STRING and SIMPLE-STRING as they are union types
703 ;; in SBCL.
707 x
709 ;; Special case VECTOR
713 x
715 ;; Handle specialized element types for 1D arrays.
717 ;; Can we avoid checking for dimension issues like (COERCE FOO
718 ;; '(SIMPLE-VECTOR 5)) returning a vector of length 6?
719 ;;
720 ;; CLHS actually allows this for all code with SAFETY < 3,
721 ;; but we're a conservative bunch.
725 ;; We can!
731 x
737 x))))
738 ;; No, duh. Dimension checking required.
740 "~@<~S specifies dimensions other than (*) in safe code.~:@>"
741 tval)))
744 "~@<open coding coercion to ~S not implemented.~:@>"
745 tval))))))