failed AVER: (SUBSETP END END-STACK)

[Douglas Katzman]

If a variable which is supposed to be a structure, but might be inferred to be nil (but not actually ever nil at runtime), is declared dynamic-extent, the compiler crashes. This hugely-stripped-down example shows something a little bit silly that our code does, which perhaps it ought not, but regardless should compile.

;; Minimal example:
(declaim (inline make-a-rec))
(defstruct (my-rec (:constructor make-a-rec (someslot))) someslot)

(defun hairyfun (rec1 rec2)
  (declare (ignore rec1 rec2))
  ;; complicated stuff elided
  nil)

(defmacro my-obj (x) `(when ,x (make-a-rec ,x)))

(defun mumble-p (cptr-a cptr-b)
  (let ((r8-a (my-obj cptr-a)) (r8-b (my-obj cptr-b)))
    (declare (dynamic-extent r8-a r8-b))
    (hairyfun r8-a r8-b)))
;; end of example

A few things can workaround the problem for us:
- remove the inline declamation, of course getting "cannot stack allocate", but no crash; or different compiler policy around this code achieves the same thing
- remove the "WHEN" around the object constructor and refactor MUMBLE-P to test whether it should make the objects at all (because in our case HAIRYFUN needs valid objects, so it would be a bug in our code if we ever got there without - however the rest of the scaffolding provided by MY-OBJ is fairly generic and generally useful, so we can't "just" do that)
- assert essentially the same around the invocation of MY-OBJ by writing (let ((r8-a (my-obj (the (not null)

Tested on 2 versions of sbcl:
Pristine sources:
- SBCL 1.0.54.0-185b926 (Darwin dhcp-172-23-194-151.cam.corp.google.com 10.8.0 Darwin Kernel Version 10.8.0: Tue Jun 7 16:33:36 PDT 2011; root:xnu-1504.15.3~1/RELEASE_I386 i386)
*features = (:ASDF2 :ASDF :ANSI-CL :COMMON-LISP :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE :SB-EVAL :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :X86 :UNIX :MACH-O :BSD :DARWIN :MACH-EXCEPTION-HANDLER :RESTORE-FS-SEGMENT-REGISTER-FROM-TLS :UD2-BREAKPOINTS :GENCGC :STACK-GROWS-DOWNWARD-NOT-UPWARD :C-STACK-IS-CONTROL-STACK :COMPARE-AND-SWAP-VOPS :UNWIND-TO-FRAME-AND-CALL-VOP :RAW-INSTANCE-INIT-VOPS :STACK-ALLOCATABLE-CLOSURES :STACK-ALLOCATABLE-VECTORS :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-FIXED-OBJECTS :ALIEN-CALLBACKS :CYCLE-COUNTER :INLINE-CONSTANTS :MEMORY-BARRIER-VOPS :MULTIPLY-HIGH-VOPS :LINKAGE-TABLE :OS-PROVIDES-DLOPEN :OS-PROVIDES-DLADDR :OS-PROVIDES-PUTWC :OS-PROVIDES-BLKSIZE-T :OS-PROVIDES-SUSECONDS-T)

Customized by cracauer@google
- 1.0.57.10.HEAD.82-e458da0 (Linux flarp.cam.corp.google.com 2.6.38.8-gg868 #2 SMP Fri May 18 03:37:30 PDT 2012 x86_64 GNU/Linux)
*features* = (:ITA :SB-THREAD :COMPILER-LOOPING-BUG-FIXED :ITA-USE-OS-EXIT :ANSI-CL :COMMON-LISP :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE :SB-EVAL :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :SB-CORE-COMPRESSION :OS-PROVIDES-POLL :OS-PROVIDES-GETPROTOBY-R :OS-PROVIDES-SUSECONDS-T :OS-PROVIDES-PUTWC :OS-PROVIDES-DLADDR :OS-PROVIDES-DLOPEN :LITTLE-ENDIAN :MULTIPLY-HIGH-VOPS :MEMORY-BARRIER-VOPS :INLINE-CONSTANTS :FLOAT-EQL-VOPS :COMPLEX-FLOAT-VOPS :CYCLE-COUNTER :ALIEN-CALLBACKS :STACK-ALLOCATABLE-FIXED-OBJECTS :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-VECTORS :STACK-ALLOCATABLE-CLOSURES :RAW-INSTANCE-INIT-VOPS :UNWIND-TO-FRAME-AND-CALL-VOP :COMPARE-AND-SWAP-VOPS :LINKAGE-TABLE :C-STACK-IS-CONTROL-STACK :STACK-GROWS-DOWNWARD-NOT-UPWARD :GENCGC :LARGEFILE :SB-FUTEX :SB-THREAD :LINUX :ELF :UNIX :X86-64)

[Stas Boukarev (stassats)]

Reduced:
(defun foo (x)
  (let ((a (if x
               (list (list x))
               (list (list x)))))
    (declare (dynamic-extent a))
    (prin1 a)
    1))
So, a problem is with IF and nested DXes.

[Alastair Bridgewater (alastair-bridgewater)]

It turns out that UPDATE-UVL-LIVE-SETS is a backwards flow-sensitive analysis, propagating :UNKNOWN LVARs (unknown-values and dynamic-extent stack packets) from where they are known to be consumed back to where they are created. In Stas' reduced test case, each branch of the IF creates two dynamic-extent LVARs, one of which is shared with the other branch. The analysis starts by looking for the start of all three LVARs, each branch kills two and leaves one, and when we get to the IF we end up with the UNION of the two branches and keep propagating the two LVARs that were only killed on one branch, all the way back to the beginning. Boom.

Nastier, control-flow wise:
(defun foo (x y)
  (dotimes (i 2)
    (block bar
      (let ((a (if x
                   (list (list x))
                   (list (list x))))
            (b (if y x (return-from bar x))))
        (declare (dynamic-extent a))
        (prin1 a)
        b))))

This example is worse because of the introduction of the RETURN-FROM to force an exit after allocating the DX values but BEFORE entering their environment (which would normally cause the DX values to simply be popped off) combined with a loop to cause the backwards flow analysis to propagate the LVAR lifetimes back around through the RETURN-FROM from the other side. On the upside, if a fixed STACK phase can handle this nastier case any further bugs would have to be VERY subtle.