| blob | 0d47738a46502b66a9186a93b796680f2cb56e56 |
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 (*))))))
159 adjustable fill-pointer displaced-index-offset displaced-to))
174 '*))
179 cdims
183 '(*))
185 '*))))
188 ;;; Complex array operations should assert that their array argument
189 ;;; is complex. In SBCL, vectors with fill-pointers are complex.
205 \f
206 ;;;; constructors
208 ;;; Convert VECTOR into a MAKE-ARRAY followed by SETFs of all the
209 ;;; elements.
219 elements)
222 ;;; Just convert it into a MAKE-ARRAY.
228 :element-type element-type
233 adjustable fill-pointer)
260 creation-form)
262 ;; error checking for target, disabled on the host because
263 ;; (CTYPE-OF #\Null) is not possible.
264 #-sb-xc-host
269 ;; this case will cause an error at runtime, so we'd
270 ;; better WARN about it now.
273 ~S of ~S).~@:>"
274 :format-arguments
276 value
278 'upgraded-array-element-type
279 eltype)))
281 ;; this case will not cause an error at runtime, but
282 ;; it's still worth STYLE-WARNing about.
284 value eltype)))))
289 array)))))
291 ;;; The integer type restriction on the length ensures that it will be
292 ;;; a vector. The lack of :ADJUSTABLE, :FILL-POINTER, and
293 ;;; :DISPLACED-TO keywords ensures that it will be simple; the lack of
294 ;;; :INITIAL-ELEMENT relies on another transform to deal with that
295 ;;; kind of initialization efficiently.
306 '*))
321 #-sb-xc-host
323 ;; This situation arises e.g. in (MAKE-ARRAY 4 :ELEMENT-TYPE
324 ;; '(INTEGER 1 5)) ANSI's definition of MAKE-ARRAY says "If
325 ;; INITIAL-ELEMENT is not supplied, the consequences of later
326 ;; reading an uninitialized element of new-array are undefined,"
327 ;; so this could be legal code as long as the user plans to
328 ;; write before he reads, and if he doesn't we're free to do
329 ;; anything we like. But in case the user doesn't know to write
330 ;; elements before he reads elements (or to read manuals before
331 ;; he writes code:-), we'll signal a STYLE-WARNING in case he
332 ;; didn't realize this.
335 eltype))
340 'length
346 `(* ,padded-length-form
351 n-bits-per-element)))
359 ;;; The list type restriction does not ensure that the result will be a
360 ;;; multi-dimensional array. But the lack of adjustable, fill-pointer,
361 ;;; and displaced-to keywords ensures that it will be simple.
362 ;;;
363 ;;; FIXME: should we generalize this transform to non-simple (though
364 ;;; non-displaced-to) arrays, given that we have %WITH-ARRAY-DATA to
365 ;;; deal with those? Maybe when the DEFTRANSFORM
366 ;;; %DATA-VECTOR-AND-INDEX in the VECTOR case problem is solved? --
367 ;;; CSR, 2002-07-01
379 "The dimension list contains something other than an integer: ~S"
380 dims))
409 dims))
411 \f
412 ;;;; miscellaneous properties of arrays
414 ;;; Transforms for various array properties. If the property is know
415 ;;; at compile time because of a type spec, use that constant value.
417 ;;; Most of this logic may end up belonging in code/late-type.lisp;
418 ;;; however, here we also need the -OR-GIVE-UP for the transforms, and
419 ;;; maybe this is just too sloppy for actual type logic. -- CSR,
420 ;;; 2004-02-18
426 ;; there are at least two types, right?
432 ;; FIXME: intersection type [e.g. (and (array * (*)) (satisfies foo)) ]
445 ;; FIXME: intersection type
448 ;;; If we can tell the rank from the type info, use it instead.
454 "The array rank is not known at compile time: ~S"
455 dims)
458 ;;; If we know the dimensions at compile time, just use it. Otherwise,
459 ;;; if we can tell that the axis is in bounds, convert to
460 ;;; %ARRAY-DIMENSION (which just indirects the array header) or length
461 ;;; (if it's simple and a vector).
474 dims
475 axis))
478 dim)
491 ;;; If the length has been declared and it's simple, just return it.
501 ;;; All vectors can get their length by using VECTOR-LENGTH. If it's
502 ;;; simple, it will extract the length slot from the vector. It it's
503 ;;; complex, it will extract the fill pointer slot from the array
504 ;;; header.
508 ;;; If a simple array with known dimensions, then VECTOR-LENGTH is a
509 ;;; compile-time constant.
517 dim)))
519 ;;; Again, if we can tell the results from the type, just use it.
520 ;;; Otherwise, if we know the rank, convert into a computation based
521 ;;; on array-dimension. We can wrap a TRULY-THE INDEX around the
522 ;;; multiplications because we know that the total size must be an
523 ;;; INDEX.
537 ;;; Only complex vectors have fill pointers.
542 nil
545 t)
547 nil)
550 "The array type is ambiguous; must call ~
553 ;;; Primitive used to verify indices into arrays. If we can tell at
554 ;;; compile-time or we are generating unsafe code, don't bother with
555 ;;; the VOP.
564 \f
565 ;;;; WITH-ARRAY-DATA
567 ;;; This checks to see whether the array is simple and the start and
568 ;;; end are in bounds. If so, it proceeds with those values.
569 ;;; Otherwise, it calls %WITH-ARRAY-DATA. Note that %WITH-ARRAY-DATA
570 ;;; may be further optimized.
571 ;;;
572 ;;; Given any ARRAY, bind DATA-VAR to the array's data vector and
573 ;;; START-VAR and END-VAR to the start and end of the designated
574 ;;; portion of the data vector. SVALUE and EVALUE are any start and
575 ;;; end specified to the original operation, and are factored into the
576 ;;; bindings of START-VAR and END-VAR. OFFSET-VAR is the cumulative
577 ;;; offset of all displacements encountered, and does not include
578 ;;; SVALUE.
579 ;;;
580 ;;; When FORCE-INLINE is set, the underlying %WITH-ARRAY-DATA form is
581 ;;; forced to be inline, overriding the ordinary judgment of the
582 ;;; %WITH-ARRAY-DATA DEFTRANSFORMs. Ordinarily the DEFTRANSFORMs are
583 ;;; fairly picky about their arguments, figuring that if you haven't
584 ;;; bothered to get all your ducks in a row, you probably don't care
585 ;;; that much about speed anyway! But in some cases it makes sense to
586 ;;; do type testing inside %WITH-ARRAY-DATA instead of outside, and
587 ;;; the DEFTRANSFORM can't tell that that's going on, so it can make
588 ;;; sense to use FORCE-INLINE option in that case.
598 ,start-var
599 ,end-var
607 ;; success
610 ,n-svalue
616 ;;; This is the fundamental definition of %WITH-ARRAY-DATA, for use in
617 ;;; DEFTRANSFORMs and DEFUNs.
619 start
620 end
621 &key
623 unsafe?
624 fail-inline?)
627 (,defaulted-end
649 (+ ,cumulative-offset
659 ;; It might very well be reasonable to
660 ;; allow general ARRAY here, I just
661 ;; haven't tried to understand the
662 ;; performance issues involved. --
663 ;; WHN, and also CSR 2002-05-26
665 *
666 :node node
668 "inline non-SIMPLE-vector-handling logic"
670 `(%with-array-data-macro array start end
673 \f
674 ;;;; array accessors
676 ;;; We convert all typed array accessors into AREF and %ASET with type
677 ;;; assertions on the array.
682 bit
687 bit
703 ;; given a set of indices. We wrap each index with a call
704 ;; to %CHECK-BOUND to ensure that everything works out
705 ;; correctly. We can wrap all the interior arithmetic with
706 ;; TRULY-THE INDEX because we know the resultant
707 ;; row-major index must be an index.
721 ,',array
723 dims))
724 (,',index
726 0
734 index
736 (* ,form
738 (%check-bound
739 ,',array
745 ;; Just return the index after computing it.
748 index))
750 ;; Convert AREF and %ASET into a HAIRY-DATA-VECTOR-REF (or
751 ;; HAIRY-DATA-VECTOR-SET) with the set of indices replaced with the an
752 ;; expression for the row major index.
762 ;; For AREF of vectors we do the bounds checking in the callee. This
763 ;; lets us do a significantly more efficient check for simple-arrays
764 ;; without bloating the code.
775 ;;; But if we find out later that there's some useful type information
776 ;;; available, switch back to the normal one to give other transforms
777 ;;; a stab at it.
782 ;; If an element type has been declared, we want to
783 ;; use that information it for type checking (even
784 ;; if the access can't be optimized due to the array
785 ;; not being simple).
787 ;; This type logic corresponds to the special
788 ;; case for strings in HAIRY-DATA-VECTOR-REF
789 ;; (generic/vm-tran.lisp)
792 ;; If it's a simple array, we might be able
793 ;; to inline the access completely.
797 `(,',transform-to array
798 (%check-bound array
800 index)
803 hairy-data-vector-ref nil nil)
809 index))
812 ;; Not an exactly specified one-dimensional simple array -> punt
813 ;; to the complex version.
817 index)))
819 ;;; Just convert into a HAIRY-DATA-VECTOR-REF (or
820 ;;; HAIRY-DATA-VECTOR-SET) after checking that the index is inside the
821 ;;; array total size.
828 new-value))
829 \f
830 ;;;; bit-vector array operation canonicalization
831 ;;;;
832 ;;;; We convert all bit-vector operations to have the result array
833 ;;;; specified. This allows any result allocation to be open-coded,
834 ;;;; and eliminates the need for any VM-dependent transforms to handle
835 ;;;; these cases.
843 `(,',fun bit-array-1 bit-array-2
845 ;; If result is T, make it the first arg.
860 ;;; Similar for BIT-NOT, but there is only one arg...
869 \f
870 ;;; Pick off some constant cases.
874 ;; FIXME: use analogue of ARRAY-TYPE-DIMENSIONS-OR-GIVE-UP
875 nil)
879 ;; no array header
882 ;; multi-dimensional array, will have a header
887 nil)))))))