Steel Bank Common Lisp

compiler hang in ORDER-UVL-SETS

Reported by Nikodemus Siivola on 2008-12-17
2
Affects Status Importance Assigned to Milestone
SBCL
Low
Unassigned

Bug Description

BUGS #429

Compiling a file with this contents makes the compiler loop in ORDER-UVL-SETS:

  (declaim (inline storage))
  (defun storage (x)
    (the (simple-array flt (*)) (unknown x)))

  (defun test1 (lumps &key cg)
    (let ((nodes (map 'list (lambda (lump) (storage lump))
                      lumps)))
      (setf (aref nodes 0) 2)
      (assert (every #'~= (apply #'concatenate 'list nodes) '(2 3 6 9)))))

Changed in sbcl:
status: New → Confirmed
Changed in sbcl:
importance: Undecided → Medium
Nikodemus Siivola (nikodemus) wrote :

This is due to stack analysis being foiled by the unreachable code left in by control flow analysis, which in turn happens thanks to unconditional marking of NLX's as live in CONTROL-ANALYZE-1-FUN.

It seems to me that the correct fix would be to split CONTROL-ANALYZE into two stages: 1: walk the graph, marking nodes as live without giving NLX's special treatment. 2: walk the live parts of the graph in emit order, doing the emit order stuff.

Changed in sbcl:
assignee: nobody → Nikodemus Siivola (nikodemus)
tags: added: control-analysis stack-analysis
Nikodemus Siivola (nikodemus) wrote :

Workaround:

(defun order-uvl-sets (component)
  (clear-flags component)
  ;; KLUDGE: Workaround for lp#308914: we keep track of number of blocks
  ;; needing repeats, and bug out if we get stuck.
  (loop with head = (component-head component)
        with todo = 0
        with last-todo = 0
        do (psetq last-todo todo
                  todo 0)
        do (do-blocks (block component)
             (unless (block-flag block)
               (let ((pred (find-if #'block-flag (block-pred block))))
                 (when (and (eq pred head)
                            (not (bind-p (block-start-node block))))
                   (let ((entry (nle-block-entry-block block)))
                     (setq pred (if (block-flag entry) entry nil))))
                 (cond (pred
                        (setf (block-flag block) t)
                        (order-block-uvl-sets block pred))
                       (t
                        (incf todo))))))
        do (when (= last-todo todo)
             ;; If the todo count is the same as on last iteration, it means
             ;; we are stuck, which in turn means the unmarked blocks are
             ;; actually unreachable, so UVL set ordering for them doesn't
             ;; matter.
             (return-from order-uvl-sets))
        while (plusp todo)))

Nikodemus Siivola (nikodemus) wrote :

After another bout of wrestling with control-analysis, I'm inclined to believe the problem is not there after all.

The dead bits remain in the component because there is a XEP for the lambda from EVERY => (MAP NIL (LAMBDA ...) ...) -- this is quite correct as far as control analysis is concerned.

The existence of the XEP is not a great mystery either, since MAP doesn't get fully optimized there.

What is a mystery so far is why that XEP sticks around even though we should have by that point know that the (SETF AREF) will never return.

Changed in sbcl:
assignee: Nikodemus Siivola (nikodemus) → nobody
Nikodemus Siivola (nikodemus) wrote :

Downgrading to LOW as the workaround has been committed in SBCL 1.0.42.39.

IMPORTANT: Anyone wanting to investigate this bug needs to #+nil the (return-from order-uvl-sets) in the workaround.

Changed in sbcl:
importance: Medium → Low
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers