| blob | 85a75ccbb8e39c7695dd0d72c006a0812ee8b912 |
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.)
70 expansion)))
72 ;;; If the lvar OBJECT definitely is or isn't of the specified
73 ;;; type, then return T or NIL as appropriate. Otherwise quietly
74 ;;; GIVE-UP-IR1-TRANSFORM.
80 ;; We don't transform alien type tests until here, because
81 ;; once we do that the rest of the type system can no longer
82 ;; reason about them properly -- so we'd miss out on type
83 ;; derivation, etc.
86 ;; If it's a lisp-rep-type, the CTYPE should be one already.
92 nil)
94 t)
96 nil)
107 ;;; Flush %TYPEP tests whose result is known at compile time.
112 object
114 node))
116 ;;; This is the IR1 transform for simple type predicates. It checks
117 ;;; whether the single argument is known to (not) be of the
118 ;;; appropriate type, expanding to T or NIL as appropriate.
128 ;;; If FIND-CLASSOID is called on a constant class, locate the
129 ;;; CLASSOID-CELL at load time.
135 \f
142 type
152 type
159 t)
161 nil)
165 \f
166 ;;;; standard type predicates, i.e. those defined in package COMMON-LISP,
167 ;;;; plus at least one oddball (%INSTANCEP)
168 ;;;;
169 ;;;; Various other type predicates (e.g. low-level representation
170 ;;;; stuff like SIMPLE-ARRAY-SINGLE-FLOAT-P) are defined elsewhere.
172 ;;; FIXME: This function is only called once, at top level. Why not
173 ;;; just expand all its operations into toplevel code?
176 ; (The ATOM predicate is handled separately as (NOT CONS).)
206 \f
207 ;;;; transforms for type predicates not implemented primitively
208 ;;;;
209 ;;;; See also VM dependent transforms.
213 #!+sb-unicode
216 ;; CONS is implemented as (and list (not (eql nil))) where the 'and' is
217 ;; built-in to the consp vop. Reduce to just LISTP if possible.
219 \f
220 ;;;; TYPEP source transform
222 ;;; Return a form that tests the variable N-OBJECT for being in the
223 ;;; binds specified by TYPE. BASE is the name of the base type, for
224 ;;; declaration. We make SAFETY locally 0 to inhibit any checking of
225 ;;; this assertion.
241 ;;; Do source transformation of a test of a known numeric type. We can
242 ;;; assume that the type doesn't have a corresponding predicate, since
243 ;;; those types have already been picked off. In particular, CLASS
244 ;;; must be specified, since it is unspecified only in NUMBER and
245 ;;; COMPLEX. Similarly, we assume that COMPLEXP is always specified.
246 ;;;
247 ;;; For non-complex types, we just test that the number belongs to the
248 ;;; base type, and then test that it is in bounds. When CLASS is
249 ;;; INTEGER, we check to see whether the range is no bigger than
250 ;;; FIXNUM. If so, we check for FIXNUM instead of INTEGER. This allows
251 ;;; us to use fixnum comparison to test the bounds.
252 ;;;
253 ;;; For complex types, we must test for complex, then do the above on
254 ;;; both the real and imaginary parts. When CLASS is float, we need
255 ;;; only check the type of the realpart, since the format of the
256 ;;; realpart and the imagpart must be the same.
264 type)))
270 (:real
272 nil
279 (:complex
290 base))))))))))
292 ;;; Do the source transformation for a test of a hairy type. AND,
293 ;;; SATISFIES and NOT are converted into the obvious code. We convert
294 ;;; unknown types to %TYPEP, emitting an efficiency note if
295 ;;; appropriate.
319 ;;; Do source transformation for TYPEP of a known union type. If a
320 ;;; union type contains LIST, then we pull that out and make it into a
321 ;;; single LISTP call. Note that if SYMBOL is in the union, then LIST
322 ;;; will be a subtype even without there being any (member NIL). We
323 ;;; currently just drop through to the general code in this case,
324 ;;; rather than trying to optimize it (but FIXME CSR 2004-04-05: it
325 ;;; wouldn't be hard to optimize it after all).
326 ;;; FIXME: if the CONSP|NIL -> LISTP optimization kicks in,
327 ;;; we forgo the array optimizations.
349 more-types)))))))
351 ;;; Do source transformation for TYPEP of a known intersection type.
358 ;;; If necessary recurse to check the cons type.
366 ;; CONSP can be safely weakened to LISTP if either of the CAR
367 ;; or CDR test (or both) can distinguish LIST from CONS
368 ;; by never returning T when given an input of NIL.
374 ;; can't weaken if the specifier is (CONS SYMBOL)
376 ;; these are disjoint from NIL
378 t)
380 ;; at least one of them must not spuriously return T
383 ;; require that none spuriously return T
386 ;; hack - (CONS KEYWORD) is weakenable
387 ;; because NIL is not a keyword.
398 ;; Being paranoid, perform the safely weakenable test first
399 ;; so that the other part doesn't execute on an object that
400 ;; it would not have gotten, were the CONSP test not weakened.
420 collect
423 #!+sb-simd-pack
437 ;;; Return the predicate and type from the most specific entry in
438 ;;; *TYPE-PREDICATES* that is a supertype of TYPE.
452 ;;; Return forms to test that OBJ has the rank and dimensions
453 ;;; specified by TYPE, where STYPE is the type we have checked against
454 ;;; (which is the same but for dimensions and element type).
455 ;;;
456 ;;; Secondary return value is true if passing the generated tests implies that
457 ;;; the array has a header.
469 for i from 0
472 t))
476 t))
481 nil)
486 nil)))
492 nil))))))
494 ;;; Return forms to test that OBJ has the element-type specified by type
495 ;;; specified by TYPE, where STYPE is the type we have checked against (which
496 ;;; is the same but for dimensions and element type). If HEADERP is true, OBJ
497 ;;; is guaranteed to be an array-header.
507 ;; If we know OBJ is an array header, and that the array is
508 ;; simple, we also know there is exactly one indirection to
509 ;; follow.
516 ;;; If we can find a type predicate that tests for the type without
517 ;;; dimensions, then use that predicate and test for dimensions.
518 ;;; Otherwise, just do %TYPEP.
520 ;; Intercept (SIMPLE-ARRAY * (*)) because otherwise it tests
521 ;; (AND SIMPLE-ARRAY (NOT ARRAY-HEADER)) to weed out rank 0 and >1.
522 ;; By design the simple arrays of of rank 1 occupy a contiguous
523 ;; range of widetags, and unlike the arbitrary-widetags code for unions,
524 ;; this nonstandard predicate can be generically defined for all backends.
532 ;; (If the element type hasn't been defined yet, it's
533 ;; not safe to assume here that it will eventually
534 ;; have (UPGRADED-ARRAY-ELEMENT-TYPE type)=T, so punt.)
545 ;; KLUDGE: this is a bit lame; if we get here,
546 ;; we already know that N-OBJ is an array, but
547 ;; (NOT SIMPLE-ARRAY) doesn't know that. On the
548 ;; other hand, this should get compiled down to
549 ;; two widetag tests, so it's only a bit lame.
551 ,@tests
555 ;;; Transform a type test against some instance type. The type test is
556 ;;; flushed if the result is known at compile time. If not properly
557 ;;; named, error. If sealed and has no subclasses, just test for
558 ;;; layout-EQ. If a structure then test for layout-EQ and then a
559 ;;; general test based on layout-inherits. If safety is important,
560 ;;; then we also check whether the layout for the object is invalid
561 ;;; and signal an error if so. Otherwise, look up the indirect
562 ;;; class-cell and call CLASS-CELL-TYPEP at runtime.
571 res
572 nil))))
574 ;; Flush tests whose result is known at compile time.
576 nil)
578 t)
579 ;; If not properly named, error.
582 class:~% ~S"
583 class))
585 ;; Delay the type transform to give type propagation a chance.
588 ;; Otherwise transform the type test.
598 ;; Test just one of %INSTANCEP or %FUNCALLABLE-INSTANCE-P
600 ;; But if we don't know which is will be, try both.
601 ;; This is less general than LAYOUT-OF,and therefore
602 ;; a little quicker to fail, because objects with
603 ;; {LIST|OTHER}-POINTER-LOWTAG can't possibly pass.
611 ;; It's possible to seal a STANDARD-CLASS, not just a STRUCTURE-CLASS,
612 ;; though probably extremely weird. Also the PRED should be set in
613 ;; that event, but it isn't.
616 ;; Sealed and has no subclasses.
617 ;; The crummy dual expressions for the same result are because
618 ;; (BLOCK (RETURN ...)) seems to emit a forward branch in the
619 ;; passing case, but AND emits a forward branch in the failing
620 ;; case which I believe is the better choice.
626 ;; structure type tests; hierarchical layout depths
628 ;; If a structure is apparently an abstract base type,
629 ;; having no constructor, then no instance layout should
630 ;; be EQ to the classoid's layout. It is a slight win
631 ;; to use the depth-based check first, then do the EQ check.
632 ;; There is no loss in the case where both fail, and there
633 ;; is a benefit in a passing case. Always try both though,
634 ;; because (MAKE-INSTANCE 'x) works on any structure class.
642 ;; Use DATA-VECTOR-REF directly, since that's what SVREF in
643 ;; a SAFETY 0 lexenv will eventually be transformed to.
644 ;; This can give a large compilation speedup, since
645 ;; %INSTANCE-TYPEPs are frequently created during
646 ;; GENERATE-TYPE-CHECKS, and the normal aref transformation
647 ;; path is pretty heavy.
656 ;; we used to check for invalid layouts here,
657 ;; but in fact that's both unnecessary and
658 ;; wrong; it's unnecessary because structure
659 ;; classes can't be redefined, and it's wrong
660 ;; because it is quite legitimate to pass an
661 ;; object with an invalid layout to a structure
662 ;; type test.
668 ;; hierarchical layout depths for other things (e.g.
669 ;; CONDITION, STREAM)
670 ;; The quasi-hierarchical types are abstract base types,
671 ;; so perform inheritance check first, and EQ second.
672 ;; Actually, since you can't make an abstract STREAM,
673 ;; maybe we should skip the EQ test? But you *can* make
674 ;; an instance of CONDITION for what it's worth.
675 ;; SEQUENCE is special-cased, but could be handled here.
686 ;; See above.
689 t
701 object)))))))))
703 ;;; If the specifier argument is a quoted constant, then we consider
704 ;;; converting into a simple predicate or other stuff. If the type is
705 ;;; constant, but we can't transform the call, then we convert to
706 ;;; %TYPEP. We only pass when the type is non-constant. This allows us
707 ;;; to recognize between calls that might later be transformed
708 ;;; successfully when a constant type is discovered. We don't give an
709 ;;; efficiency note when we pass, since the IR1 transform will give
710 ;;; one if necessary and appropriate.
711 ;;;
712 ;;; If the type is TYPE= to a type that has a predicate, then expand
713 ;;; to that predicate. Otherwise, we dispatch off of the type's type.
714 ;;; These transformations can increase space, but it is hard to tell
715 ;;; when, so we ignore policy and always do them.
753 #!+sb-simd-pack
769 ;; KLUDGE: It looks bad to only do this on explicitly quoted forms,
770 ;; since that would overlook other kinds of constants. But it turns
771 ;; out that the DEFTRANSFORM for TYPEP detects any constant
772 ;; lvar, transforms it into a quoted form, and gives this
773 ;; source transform another chance, so it all works out OK, in a
774 ;; weird roundabout way. -- WHN 2001-03-18
780 \f
781 ;;;; coercion
783 ;;; Constant-folding.
784 ;;;
785 #-sb-xc-host
791 t))))
793 ;;; Drops dimension information from vector types.
798 'simple-array
814 etype
815 complexp))))))))
823 'x
824 ;; Note: The THE forms we use to wrap the results make sure that
825 ;; specifiers like (SINGLE-FLOAT 0.0 1.0) can raise a TYPE-ERROR.
829 ;; FIXME: #!+long-float (t ,(error "LONG-FLOAT case needed"))
837 ;; unspecific FLOAT type
848 x)
853 ;; Special case STRING and SIMPLE-STRING as they are union types
854 ;; in SBCL.
858 x
862 ;; Special case VECTOR
866 x
868 ;; Handle specialized element types for 1D arrays.
870 ;; Can we avoid checking for dimension issues like (COERCE FOO
871 ;; '(SIMPLE-VECTOR 5)) returning a vector of length 6?
872 ;;
873 ;; CLHS actually allows this for all code with SAFETY < 3,
874 ;; but we're a conservative bunch.
878 ;; We can!
884 x
890 x))))
891 ;; No, duh. Dimension checking required.
893 "~@<~S specifies dimensions other than (*) in safe code.~:@>"
894 tval)))
903 "~@<open coding coercion to ~S not implemented.~:@>"
904 tval))))))