| blob | 522413454797ae6c3b572f1e39f3a96c88bdb015 |
1 ;;;; array-specific optimizers and transforms
3 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; more information.
5 ;;;;
6 ;;;; This software is derived from the CMU CL system, which was
7 ;;;; written at Carnegie Mellon University and released into the
8 ;;;; public domain. The software is in the public domain and is
9 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
10 ;;;; files for more information.
13 \f
14 ;;;; utilities for optimizing array operations
16 ;;; Return UPGRADED-ARRAY-ELEMENT-TYPE for LVAR, or do
17 ;;; GIVE-UP-IR1-TRANSFORM if the upgraded element type can't be
18 ;;; determined.
25 element-type-specifier)))
27 ;;; Array access functions return an object from the array, hence its
28 ;;; type is going to be the array upgraded element type.
32 ;; Note that this IF mightn't be satisfied even if the runtime
33 ;; value is known to be a subtype of some specialized ARRAY, because
34 ;; we can have values declared e.g. (AND SIMPLE-VECTOR UNKNOWN-TYPE),
35 ;; which are represented in the compiler as INTERSECTION-TYPE, not
36 ;; array type.
38 ;; fix for bug #396. This type logic corresponds to the special
39 ;; case for strings in HAIRY-DATA-VECTOR-REF
40 ;; (generic/vm-tran.lisp)
45 #!+sb-unicode
50 ;; see KLUDGE below.
53 ;; KLUDGE: there is no good answer here, but at least
54 ;; *wild-type* won't cause HAIRY-DATA-VECTOR-{REF,SET} to be
55 ;; erroneously optimized (see generic/vm-tran.lisp) -- CSR,
56 ;; 2002-08-21
65 ;;; The ``new-value'' for array setters must fit in the array, and the
66 ;;; return type is going to be the same as the new-value for SETF
67 ;;; functions.
72 new-value
79 array
83 nil)
85 ;;; Return true if ARG is NIL, or is a constant-lvar whose
86 ;;; value is NIL, false otherwise.
92 \f
93 ;;;; DERIVE-TYPE optimizers
95 ;;; Array operations that use a specific number of indices implicitly
96 ;;; assert that the array is of that rank.
99 array
137 ;;; Figure out the type of the data vector if we know the argument
138 ;;; element type.
145 (*))))))
163 adjustable fill-pointer displaced-index-offset displaced-to))
178 '*))
183 cdims
187 '(*))
189 '*))))
192 ;;; Complex array operations should assert that their array argument
193 ;;; is complex. In SBCL, vectors with fill-pointers are complex.
209 \f
210 ;;;; constructors
212 ;;; Convert VECTOR into a MAKE-ARRAY followed by SETFs of all the
213 ;;; elements.
223 elements)
226 ;;; Just convert it into a MAKE-ARRAY.
232 :element-type element-type
237 adjustable fill-pointer)
264 creation-form)
266 ;; error checking for target, disabled on the host because
267 ;; (CTYPE-OF #\Null) is not possible.
268 #-sb-xc-host
273 ;; this case will cause an error at runtime, so we'd
274 ;; better WARN about it now.
277 ~S of ~S).~@:>"
278 :format-arguments
280 value
282 'upgraded-array-element-type
283 eltype)))
285 ;; this case will not cause an error at runtime, but
286 ;; it's still worth STYLE-WARNing about.
288 value eltype)))))
293 array)))))
295 ;;; The integer type restriction on the length ensures that it will be
296 ;;; a vector. The lack of :ADJUSTABLE, :FILL-POINTER, and
297 ;;; :DISPLACED-TO keywords ensures that it will be simple; the lack of
298 ;;; :INITIAL-ELEMENT relies on another transform to deal with that
299 ;;; kind of initialization efficiently.
310 '*))
325 #-sb-xc-host
327 ;; This situation arises e.g. in (MAKE-ARRAY 4 :ELEMENT-TYPE
328 ;; '(INTEGER 1 5)) ANSI's definition of MAKE-ARRAY says "If
329 ;; INITIAL-ELEMENT is not supplied, the consequences of later
330 ;; reading an uninitialized element of new-array are undefined,"
331 ;; so this could be legal code as long as the user plans to
332 ;; write before he reads, and if he doesn't we're free to do
333 ;; anything we like. But in case the user doesn't know to write
334 ;; elements before he reads elements (or to read manuals before
335 ;; he writes code:-), we'll signal a STYLE-WARNING in case he
336 ;; didn't realize this.
339 eltype))
344 'length
350 `(* ,padded-length-form
355 n-bits-per-element)))
363 ;;; The list type restriction does not ensure that the result will be a
364 ;;; multi-dimensional array. But the lack of adjustable, fill-pointer,
365 ;;; and displaced-to keywords ensures that it will be simple.
366 ;;;
367 ;;; FIXME: should we generalize this transform to non-simple (though
368 ;;; non-displaced-to) arrays, given that we have %WITH-ARRAY-DATA to
369 ;;; deal with those? Maybe when the DEFTRANSFORM
370 ;;; %DATA-VECTOR-AND-INDEX in the VECTOR case problem is solved? --
371 ;;; CSR, 2002-07-01
383 "The dimension list contains something other than an integer: ~S"
384 dims))
413 dims))
415 \f
416 ;;;; miscellaneous properties of arrays
418 ;;; Transforms for various array properties. If the property is know
419 ;;; at compile time because of a type spec, use that constant value.
421 ;;; Most of this logic may end up belonging in code/late-type.lisp;
422 ;;; however, here we also need the -OR-GIVE-UP for the transforms, and
423 ;;; maybe this is just too sloppy for actual type logic. -- CSR,
424 ;;; 2004-02-18
430 ;; there are at least two types, right?
436 ;; FIXME: intersection type [e.g. (and (array * (*)) (satisfies foo)) ]
449 ;; FIXME: intersection type
452 ;;; If we can tell the rank from the type info, use it instead.
458 "The array rank is not known at compile time: ~S"
459 dims)
462 ;;; If we know the dimensions at compile time, just use it. Otherwise,
463 ;;; if we can tell that the axis is in bounds, convert to
464 ;;; %ARRAY-DIMENSION (which just indirects the array header) or length
465 ;;; (if it's simple and a vector).
478 dims
479 axis))
482 dim)
495 ;;; If the length has been declared and it's simple, just return it.
505 ;;; All vectors can get their length by using VECTOR-LENGTH. If it's
506 ;;; simple, it will extract the length slot from the vector. It it's
507 ;;; complex, it will extract the fill pointer slot from the array
508 ;;; header.
512 ;;; If a simple array with known dimensions, then VECTOR-LENGTH is a
513 ;;; compile-time constant.
521 dim)))
523 ;;; Again, if we can tell the results from the type, just use it.
524 ;;; Otherwise, if we know the rank, convert into a computation based
525 ;;; on array-dimension. We can wrap a TRULY-THE INDEX around the
526 ;;; multiplications because we know that the total size must be an
527 ;;; INDEX.
541 ;;; Only complex vectors have fill pointers.
546 nil
549 t)
551 nil)
554 "The array type is ambiguous; must call ~
557 ;;; Primitive used to verify indices into arrays. If we can tell at
558 ;;; compile-time or we are generating unsafe code, don't bother with
559 ;;; the VOP.
567 ;; FIXME: Can SPEED > SAFETY weaken this check to INTEGER?
569 \f
570 ;;;; WITH-ARRAY-DATA
572 ;;; This checks to see whether the array is simple and the start and
573 ;;; end are in bounds. If so, it proceeds with those values.
574 ;;; Otherwise, it calls %WITH-ARRAY-DATA. Note that %WITH-ARRAY-DATA
575 ;;; may be further optimized.
576 ;;;
577 ;;; Given any ARRAY, bind DATA-VAR to the array's data vector and
578 ;;; START-VAR and END-VAR to the start and end of the designated
579 ;;; portion of the data vector. SVALUE and EVALUE are any start and
580 ;;; end specified to the original operation, and are factored into the
581 ;;; bindings of START-VAR and END-VAR. OFFSET-VAR is the cumulative
582 ;;; offset of all displacements encountered, and does not include
583 ;;; SVALUE.
584 ;;;
585 ;;; When FORCE-INLINE is set, the underlying %WITH-ARRAY-DATA form is
586 ;;; forced to be inline, overriding the ordinary judgment of the
587 ;;; %WITH-ARRAY-DATA DEFTRANSFORMs. Ordinarily the DEFTRANSFORMs are
588 ;;; fairly picky about their arguments, figuring that if you haven't
589 ;;; bothered to get all your ducks in a row, you probably don't care
590 ;;; that much about speed anyway! But in some cases it makes sense to
591 ;;; do type testing inside %WITH-ARRAY-DATA instead of outside, and
592 ;;; the DEFTRANSFORM can't tell that that's going on, so it can make
593 ;;; sense to use FORCE-INLINE option in that case.
598 &body forms
605 ,start-var
606 ,end-var
631 ;;; This is the fundamental definition of %WITH-ARRAY-DATA, for use in
632 ;;; DEFTRANSFORMs and DEFUNs.
634 start
635 end
636 &key
638 check-bounds
639 check-fill-pointer)
652 (+ ,cumulative-offset
667 ;; If it's a simple multidimensional array, then just return
668 ;; its data vector directly rather than going through
669 ;; %WITH-ARRAY-DATA-MACRO. SBCL doesn't generally generate
670 ;; code that would use this currently, but we have encouraged
671 ;; users to use WITH-ARRAY-DATA and we may use it ourselves at
672 ;; some point in the future for optimized libraries or
673 ;; similar.
674 ;;
675 ;; FIXME: The return values here don't seem sane, and
676 ;; bounds-checks are elided!
680 `(%with-array-data-macro array start end
685 ;; It might very well be reasonable to allow general ARRAY here, I
686 ;; just haven't tried to understand the performance issues involved.
687 ;; -- WHN, and also CSR 2002-05-26
690 *
691 :node node
693 "inline non-SIMPLE-vector-handling logic"
697 *
698 :node node
700 "inline non-SIMPLE-vector-handling logic"
702 \f
703 ;;;; array accessors
705 ;;; We convert all typed array accessors into AREF and %ASET with type
706 ;;; assertions on the array.
711 bit
716 bit
732 ;; given a set of indices. We wrap each index with a call
733 ;; to %CHECK-BOUND to ensure that everything works out
734 ;; correctly. We can wrap all the interior arithmetic with
735 ;; TRULY-THE INDEX because we know the resultant
736 ;; row-major index must be an index.
750 ,',array
752 dims))
753 (,',index
755 0
763 index
765 (* ,form
767 (%check-bound
768 ,',array
774 ;; Just return the index after computing it.
777 index))
779 ;; Convert AREF and %ASET into a HAIRY-DATA-VECTOR-REF (or
780 ;; HAIRY-DATA-VECTOR-SET) with the set of indices replaced with the an
781 ;; expression for the row major index.
791 ;; For AREF of vectors we do the bounds checking in the callee. This
792 ;; lets us do a significantly more efficient check for simple-arrays
793 ;; without bloating the code. If we already know the type of the array
794 ;; with sufficient precision, skip directly to DATA-VECTOR-REF.
804 index)))
815 ;;; But if we find out later that there's some useful type information
816 ;;; available, switch back to the normal one to give other transforms
817 ;;; a stab at it.
822 ;; If an element type has been declared, we want to
823 ;; use that information it for type checking (even
824 ;; if the access can't be optimized due to the array
825 ;; not being simple).
827 ;; This type logic corresponds to the special
828 ;; case for strings in HAIRY-DATA-VECTOR-REF
829 ;; (generic/vm-tran.lisp)
832 ;; If it's a simple array, we might be able
833 ;; to inline the access completely.
837 `(,',transform-to array
838 (%check-bound array
840 index)
843 hairy-data-vector-ref nil nil)
847 ;;; Just convert into a HAIRY-DATA-VECTOR-REF (or
848 ;;; HAIRY-DATA-VECTOR-SET) after checking that the index is inside the
849 ;;; array total size.
856 new-value))
857 \f
858 ;;;; bit-vector array operation canonicalization
859 ;;;;
860 ;;;; We convert all bit-vector operations to have the result array
861 ;;;; specified. This allows any result allocation to be open-coded,
862 ;;;; and eliminates the need for any VM-dependent transforms to handle
863 ;;;; these cases.
871 `(,',fun bit-array-1 bit-array-2
873 ;; If result is T, make it the first arg.
888 ;;; Similar for BIT-NOT, but there is only one arg...
897 \f
898 ;;; Pick off some constant cases.
902 ;; FIXME: use analogue of ARRAY-TYPE-DIMENSIONS-OR-GIVE-UP
903 nil)
907 ;; no array header
910 ;; multi-dimensional array, will have a header
915 nil)))))))