TYPEP failure when using displaced arrays.

[Mark Cox]

The following code uses TYPEP to check that a newly created displaced array is of type (ARRAY DOUBLE-FLOAT (* *)).

    (let* ((d (make-array (list 2 5 5) :element-type 'double-float))
           (v (make-array (list 5 5)
                          :element-type 'double-float
                          :displaced-to d
                          :displaced-index-offset 0)))
      (list (typep v '(array double-float (* *)))
            (subtypep (type-of v) '(array double-float (* *)))))

The expected result is (T T) but SBCL currently returns (NIL T).

sbcl --version => "SBCL 1.2.4"

Thanks
Mark

Darwin Kernel Version 13.4.0: Sun Aug 17 19:50:11 PDT 2014; root:xnu-2422.115.4~1/RELEASE_X86_64 x86_64

*FEATURES* =>
(cffi-features:flat-namespace cffi-features:x86-64 cffi-features:unix
 cffi-features:darwin :cffi cffi-sys::flat-namespace :cl-fad :bordeaux-threads
 :thread-support :quicklisp :asdf-package-system :asdf3.1 :asdf3 :asdf2 :asdf
 :os-macosx :os-unix :non-base-chars-exist-p :asdf-unicode :alien-callbacks
 :ansi-cl :ash-right-vops :bsd :c-stack-is-control-stack :common-lisp
 :compare-and-swap-vops :complex-float-vops :cycle-counter :darwin
 :darwin9-or-better :float-eql-vops :gencgc :ieee-floating-point
 :inline-constants :inode64 :linkage-table :little-endian
 :mach-exception-handler :mach-o :memory-barrier-vops :multiply-high-vops
 :os-provides-blksize-t :os-provides-dladdr :os-provides-dlopen
 :os-provides-putwc :os-provides-suseconds-t :package-local-nicknames
 :raw-instance-init-vops :sb-after-xc-core :sb-core-compression :sb-doc
 :sb-eval :sb-ldb :sb-package-locks :sb-simd-pack :sb-source-locations :sb-test
 :sb-thread :sb-unicode :sb-xref-for-internals :sbcl
 :stack-allocatable-closures :stack-allocatable-fixed-objects
 :stack-allocatable-lists :stack-allocatable-vectors
 :stack-grows-downward-not-upward :symbol-info-vops :ud2-breakpoints :unix
 :unwind-to-frame-and-call-vop :x86-64)

[Mark Cox (markcox80)]

I think the problem lies in SB-C:SOURCE-TRANSFORM-ARRAY-TYPEP in src/compiler/typetran.lisp.

The predicate ARRAY-TYPE-COMPLEXP returns :MAYBE when applied to both STYPE and TYPE for the test case. I'm not sure whether the /then/ clause of the IF expression should be changed to handle this case or the condition should be altered.

[Douglas Katzman (dougk)]

The transform looks right to me, but there is a bug in the DERIVE-TYPE optimization on ARRAY-HEADER-P.
A reduced example illustrates that bug.

(defvar *d* (make-array (list 2 5 5) :element-type 'double-float))
(defun baz ()
  (let ((a (make-array '(5 5)
                       :element-type 'double-float :displaced-to *d*)))
    (values (array-header-p (%array-data-vector a))
            (locally (declare (notinline array-header-p))
              (array-header-p (%array-data-vector a))))))

The optimization bug makes it appear that the transform misbehaves, which it doesn't really.

Additionally your example illustrates another shortcoming which is that the MAKE-ARRAY call was unable to derive the array type due to (LIST 5 5), whereas if it were given as '(5 5), then type derivation would have been precise, and then the whole TYPEP call would have been compile-time-folded, and in that case, been correct.

Except that, in my example, because I've "exploded" the code for the typep transform, the behavior is the same whether you give the dimensions as (LIST 5 5) or '(5 5) because in either case the DERIVE-TYPE bug exists.

[Douglas Katzman (dougk)]

actually, the bug is in the derive-type optimizer of %array-data-vector.
[Which, incidentally is poorly named because it's really the %array-data-whatever]

The code is identical for derivation of %array-data-vector and array-storage-vector despite that they return different things.
The %array-data-vector is whatever the array is backed by, which can be another (possibly non-simple) array,
but the array-storage-vector is the "really" underlying vector after chasing an arbitrary number of displacements.
As such, the %array-data-vector on a 2d array displaced to a 3d-array should NOT return that its data-vector is a simple-array.

This is [a piece of] the buggy code in 'vm-tran'. It should pass a parameter to maybe-array-data-vector-type-specifier saying which thing its trying to do.

(macrolet ((def (name)
             `(defoptimizer (,name derive-type) ((array-lvar))
                (let ((spec (maybe-array-data-vector-type-specifier array-lvar)))
                  (when spec
                    (specifier-type spec))))))
  (def %array-data-vector)
  (def array-storage-vector))

[Mark Cox (markcox80)]

The attached patches are an attempt at fixing this issue.

[Douglas Katzman (dougk)]

That looks right. But it appears I was making stuff up when I claimed what ARRAY-STORAGE-VECTOR is conceptually.

%ARRAY-DATA-VECTOR and ARRAY-STORAGE-VECTOR each chase exactly one pointer for inputs that are not already a vector, but it is illegal to call ARRAY-STORAGE-VECTOR where the backing array is not in fact a vector. So that's why it seems like the intent is to return the final vector in a chain of displacements.

The concern I would have is that since %ARRAY-DATA-VECTOR is the one used almost everywhere internally, weakening it as was done for correctness requires examining all of its uses.
Consider WITH-ARRAY stuff in 'array-tran'. Now that ARRAY-DATA-VECTOR isn't *known* to return a vector except when the loop over array headers terminates, do we now need to advise the compiler of that with (TRULY-THE (SIMPLE-blah)) in various places to assert (without checking) that the ultimate vector is really a vector?
I'm not sure that code inside the WITH-ARRAY will know that otherwise.

[Stas Boukarev (stassats)]

Got fixed by 19752b406b2c7e08f699bf247e6b38529bae5a42.