| blob | 6dae5357f9216a9a728fddd3213d855c145ccf2a |
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.
31 ;; Note that this IF mightn't be satisfied even if the runtime
32 ;; value is known to be a subtype of some specialized ARRAY, because
33 ;; we can have values declared e.g. (AND SIMPLE-VECTOR UNKNOWN-TYPE),
34 ;; which are represented in the compiler as INTERSECTION-TYPE, not
35 ;; array type.
38 ;; KLUDGE: there is no good answer here, but at least
39 ;; *wild-type* won't cause HAIRY-DATA-VECTOR-{REF,SET} to be
40 ;; erroneously optimized (see generic/vm-tran.lisp) -- CSR,
41 ;; 2002-08-21
50 ;;; The ``new-value'' for array setters must fit in the array, and the
51 ;;; return type is going to be the same as the new-value for SETF
52 ;;; functions.
57 new-value
64 array
68 nil)
70 ;;; Return true if ARG is NIL, or is a constant-lvar whose
71 ;;; value is NIL, false otherwise.
77 \f
78 ;;;; DERIVE-TYPE optimizers
80 ;;; Array operations that use a specific number of indices implicitly
81 ;;; assert that the array is of that rank.
84 array
110 ;;; Figure out the type of the data vector if we know the argument
111 ;;; element type.
118 (*))))))
132 adjustable fill-pointer displaced-index-offset displaced-to))
147 '*))
152 cdims
156 '(*))
158 '*))))
161 ;;; Complex array operations should assert that their array argument
162 ;;; is complex. In SBCL, vectors with fill-pointers are complex.
178 \f
179 ;;;; constructors
181 ;;; Convert VECTOR into a MAKE-ARRAY followed by SETFs of all the
182 ;;; elements.
193 elements)
196 ;;; Just convert it into a MAKE-ARRAY.
202 :element-type element-type
207 adjustable fill-pointer)
234 creation-form)
236 ;; error checking for target, disabled on the host because
237 ;; (CTYPE-OF #\Null) is not possible.
238 #-sb-xc-host
243 ;; this case will cause an error at runtime, so we'd
244 ;; better WARN about it now.
247 ~S of ~S).~@:>"
248 :format-arguments
250 value
252 'upgraded-array-element-type
253 eltype)))
255 ;; this case will not cause an error at runtime, but
256 ;; it's still worth STYLE-WARNing about.
258 value eltype)))))
263 array)))))
265 ;;; The integer type restriction on the length ensures that it will be
266 ;;; a vector. The lack of :ADJUSTABLE, :FILL-POINTER, and
267 ;;; :DISPLACED-TO keywords ensures that it will be simple; the lack of
268 ;;; :INITIAL-ELEMENT relies on another transform to deal with that
269 ;;; kind of initialization efficiently.
280 '*))
295 #-sb-xc-host
297 eltype-type)
298 ;; This situation arises e.g. in (MAKE-ARRAY 4 :ELEMENT-TYPE
299 ;; '(INTEGER 1 5)) ANSI's definition of MAKE-ARRAY says "If
300 ;; INITIAL-ELEMENT is not supplied, the consequences of later
301 ;; reading an uninitialized element of new-array are undefined,"
302 ;; so this could be legal code as long as the user plans to
303 ;; write before he reads, and if he doesn't we're free to do
304 ;; anything we like. But in case the user doesn't know to write
305 ;; elements before he reads elements (or to read manuals before
306 ;; he writes code:-), we'll signal a STYLE-WARNING in case he
307 ;; didn't realize this.
310 eltype))
315 'length
321 `(* ,padded-length-form
326 n-bits-per-element)))
334 ;;; The list type restriction does not ensure that the result will be a
335 ;;; multi-dimensional array. But the lack of adjustable, fill-pointer,
336 ;;; and displaced-to keywords ensures that it will be simple.
337 ;;;
338 ;;; FIXME: should we generalize this transform to non-simple (though
339 ;;; non-displaced-to) arrays, given that we have %WITH-ARRAY-DATA to
340 ;;; deal with those? Maybe when the DEFTRANSFORM
341 ;;; %DATA-VECTOR-AND-INDEX in the VECTOR case problem is solved? --
342 ;;; CSR, 2002-07-01
354 "The dimension list contains something other than an integer: ~S"
355 dims))
384 dims))
386 \f
387 ;;;; miscellaneous properties of arrays
389 ;;; Transforms for various array properties. If the property is know
390 ;;; at compile time because of a type spec, use that constant value.
392 ;;; Most of this logic may end up belonging in code/late-type.lisp;
393 ;;; however, here we also need the -OR-GIVE-UP for the transforms, and
394 ;;; maybe this is just too sloppy for actual type logic. -- CSR,
395 ;;; 2004-02-18
401 ;; there are at least two types, right?
407 ;; FIXME: intersection type [e.g. (and (array * (*)) (satisfies foo)) ]
420 ;; FIXME: intersection type
423 ;;; If we can tell the rank from the type info, use it instead.
429 "The array rank is not known at compile time: ~S"
430 dims)
433 ;;; If we know the dimensions at compile time, just use it. Otherwise,
434 ;;; if we can tell that the axis is in bounds, convert to
435 ;;; %ARRAY-DIMENSION (which just indirects the array header) or length
436 ;;; (if it's simple and a vector).
449 dims
450 axis))
453 dim)
466 ;;; If the length has been declared and it's simple, just return it.
476 ;;; All vectors can get their length by using VECTOR-LENGTH. If it's
477 ;;; simple, it will extract the length slot from the vector. It it's
478 ;;; complex, it will extract the fill pointer slot from the array
479 ;;; header.
483 ;;; If a simple array with known dimensions, then VECTOR-LENGTH is a
484 ;;; compile-time constant.
492 dim)))
494 ;;; Again, if we can tell the results from the type, just use it.
495 ;;; Otherwise, if we know the rank, convert into a computation based
496 ;;; on array-dimension. We can wrap a TRULY-THE INDEX around the
497 ;;; multiplications because we know that the total size must be an
498 ;;; INDEX.
512 ;;; Only complex vectors have fill pointers.
517 nil
520 t)
522 nil)
525 "The array type is ambiguous; must call ~
528 ;;; Primitive used to verify indices into arrays. If we can tell at
529 ;;; compile-time or we are generating unsafe code, don't bother with
530 ;;; the VOP.
539 \f
540 ;;;; WITH-ARRAY-DATA
542 ;;; This checks to see whether the array is simple and the start and
543 ;;; end are in bounds. If so, it proceeds with those values.
544 ;;; Otherwise, it calls %WITH-ARRAY-DATA. Note that %WITH-ARRAY-DATA
545 ;;; may be further optimized.
546 ;;;
547 ;;; Given any ARRAY, bind DATA-VAR to the array's data vector and
548 ;;; START-VAR and END-VAR to the start and end of the designated
549 ;;; portion of the data vector. SVALUE and EVALUE are any start and
550 ;;; end specified to the original operation, and are factored into the
551 ;;; bindings of START-VAR and END-VAR. OFFSET-VAR is the cumulative
552 ;;; offset of all displacements encountered, and does not include
553 ;;; SVALUE.
554 ;;;
555 ;;; When FORCE-INLINE is set, the underlying %WITH-ARRAY-DATA form is
556 ;;; forced to be inline, overriding the ordinary judgment of the
557 ;;; %WITH-ARRAY-DATA DEFTRANSFORMs. Ordinarily the DEFTRANSFORMs are
558 ;;; fairly picky about their arguments, figuring that if you haven't
559 ;;; bothered to get all your ducks in a row, you probably don't care
560 ;;; that much about speed anyway! But in some cases it makes sense to
561 ;;; do type testing inside %WITH-ARRAY-DATA instead of outside, and
562 ;;; the DEFTRANSFORM can't tell that that's going on, so it can make
563 ;;; sense to use FORCE-INLINE option in that case.
573 ,start-var
574 ,end-var
582 ;; success
585 ,n-svalue
591 ;;; This is the fundamental definition of %WITH-ARRAY-DATA, for use in
592 ;;; DEFTRANSFORMs and DEFUNs.
594 start
595 end
596 &key
598 unsafe?
599 fail-inline?)
602 (,defaulted-end
624 (+ ,cumulative-offset
634 ;; It might very well be reasonable to
635 ;; allow general ARRAY here, I just
636 ;; haven't tried to understand the
637 ;; performance issues involved. --
638 ;; WHN, and also CSR 2002-05-26
640 *
641 :node node
643 "inline non-SIMPLE-vector-handling logic"
645 `(%with-array-data-macro array start end
648 \f
649 ;;;; array accessors
651 ;;; We convert all typed array accessors into AREF and %ASET with type
652 ;;; assertions on the array.
657 bit
662 bit
678 ;; given a set of indices. We wrap each index with a call
679 ;; to %CHECK-BOUND to ensure that everything works out
680 ;; correctly. We can wrap all the interior arithmetic with
681 ;; TRULY-THE INDEX because we know the resultant
682 ;; row-major index must be an index.
696 ,',array
698 dims))
699 (,',index
701 0
709 index
711 (* ,form
713 (%check-bound
714 ,',array
720 ;; Just return the index after computing it.
723 index))
725 ;; Convert AREF and %ASET into a HAIRY-DATA-VECTOR-REF (or
726 ;; HAIRY-DATA-VECTOR-SET) with the set of indices replaced with the an
727 ;; expression for the row major index.
736 ;;; Just convert into a HAIRY-DATA-VECTOR-REF (or
737 ;;; HAIRY-DATA-VECTOR-SET) after checking that the index is inside the
738 ;;; array total size.
745 new-value))
746 \f
747 ;;;; bit-vector array operation canonicalization
748 ;;;;
749 ;;;; We convert all bit-vector operations to have the result array
750 ;;;; specified. This allows any result allocation to be open-coded,
751 ;;;; and eliminates the need for any VM-dependent transforms to handle
752 ;;;; these cases.
760 `(,',fun bit-array-1 bit-array-2
762 ;; If result is T, make it the first arg.
777 ;;; Similar for BIT-NOT, but there is only one arg...
786 \f
787 ;;; Pick off some constant cases.
791 ;; FIXME: use analogue of ARRAY-TYPE-DIMENSIONS-OR-GIVE-UP
792 nil)
796 ;; no array header
799 ;; multi-dimensional array, will have a header
802 nil)))))))