WARNINGs due to inability to derive rank of array union types

Bug #1310574 reported by 3b on 2014-04-21
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Medium
Paul Khuong

Bug Description

The DEFTRANSFORM for ARRAY-RANK gives up for many union types, so code like

;; simplified from opticl
(lambda (a)
  (typecase a
    ((or (array * (* * 3)) (array * (* * 4)))
     (case (array-rank a)
       (2 (aref a 1 2))))))

WARNs with

; caught WARNING:
; Derived type of A is
; (VALUES (OR (ARRAY * (* * 3)) (ARRAY * (* * 4))) &OPTIONAL),
; conflicting with its asserted type
; (ARRAY * (* *)).

(ARRAY-RANK A) could have been simplified to 3, in which case the AREF is dead code so wouldn't warn.

More generally, code like

(lambda (a)
  (typecase a
    ((or (array * ()) (array * (1)) (array * (1 2)))
     (case (array-rank a)
       (3 (aref a 1 2 3))))))

has the same problem but can't compile the ARRAY-RANK to a specific value. In that case, constraining the type of the returned value might be enough to avoid the warning.

Tested on 1.1.17.86, x8664 linux
1.1.16.83 compiles both forms, with a "deleting unreachable code" note for the first and no message for the second.

3b (00003b) wrote :

An attempt at fixing the problem, not sure if it handles all types correctly, or if expanding to (THE (MEMBER ...) ...) is the right way to specify the result type if it isn't a constant:

(defun array-type-rank-or-give-up (type)
  (labels ((maybe-array-type-ranks (type)
             (typecase type
               (array-type
                (list
                 (if (listp (array-type-dimensions type))
                     (length (array-type-dimensions type))
                     '*)))
               (union-type
                (remove-duplicates
                 (remove nil (mapcan #'maybe-array-type-ranks
                                     (union-type-types type)))))
               (intersection-type
                (let ((d (array-type-dimensions-or-give-up type)))
                  (list (if (consp d) (length d) d)))))))
    (or (maybe-array-type-ranks type)
        (give-up-ir1-transform
         (print "~@<don't know how to extract array dimensions from type ~S~:@>")
         (type-specifier type)))))

(deftransform array-rank ((array) (array) * :node node)
  (let ((array-type (lvar-type array)))
    (let ((dims (array-type-rank-or-give-up array-type)))
      (cond ((and (consp dims)
                  (every #'numberp dims))
             (if (every (lambda (a) (= a (car dims))) (cdr dims))
                 (car dims)
                 `(the (member ,@dims)
                       (%array-rank array))))
            ((eq t (and (array-type-p array-type)
                        (array-type-complexp array-type)))
             '(%array-rank array))
            (t
             (delay-ir1-transform node :constraint)
             `(if (array-header-p array)
                  (%array-rank array)
                  1))))))

Stas Boukarev (stassats) on 2014-04-22
Changed in sbcl:
status: New → Triaged
importance: Undecided → Medium

3b <email address hidden> writes:

> An attempt at fixing the problem, not sure if it handles all types
> correctly, or if expanding to (THE (MEMBER ...) ...) is the right way to
> specify the result type if it isn't a constant:

This looks like it's going on the right lines; I'd have thought it would
be better as a derive-type optimizer for array-rank rather than the
deftransform.

> (defun array-type-rank-or-give-up (type)

It's probably not ideal to have this name for a function applicable to
general types (rather than just to ARRAY-TYPEs -- it looks like a struct
accessor). TYPE-ARRAY-RANK-OR-GIVE-UP might be better?

Cheers,

Christophe

Paul Khuong (pvk) wrote :

Wrote some code, but I have to go. Pretty sure it's correct, if perhaps a bit slow. The comment about the pattern re iterating over union/intersection still stands, however.

Singleton types trigger constant propagation, so it's probably good enough to leave only strength reduction in the transform itself.

Cyrus Harmon (ch-launchpad) wrote :

git bisect says that the offending commit is 4e459f3ceb8acac03f99c5d17f8c13a2541b61eb

Paul Khuong (pvk) on 2014-06-09
Changed in sbcl:
assignee: nobody → Paul Khuong (pvk)
status: Triaged → In Progress
Paul Khuong (pvk) wrote :

commit 88429dc37df8b99a26eee4805e64a9ae1aa379b2
Author: Paul Khuong <email address hidden>
Date: Mon Jun 9 00:44:26 2014 -0400

    More aggressive ARRAY-RANK type derivation

    * Use list-abstract-type-function to derive possible values for
      ARRAY-RANK even in the face of union/intersection/negation types.

    * Fixes lp#1310574 (triggered by a prior fix to array type union).

    * Plus tests derived from opticl.

Changed in sbcl:
status: In Progress → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers