simplify types introduced during constraint propagation

Bug #309448 reported by Nikodemus Siivola on 2008-12-18
Affects Status Importance Assigned to Milestone

Bug Description

    (time (compile
           '(lambda ()
             (declare (optimize (safety 3)))
             (declare (optimize (compilation-speed 2)))
             (declare (optimize (speed 1) (debug 1) (space 1)))
             (let ((start 4))
               (declare (type (integer 0) start))
               (print (incf start 22))
               (print (incf start 26))
               (print (incf start 28)))
             (let ((start 6))
               (declare (type (integer 0) start))
               (print (incf start 22))
               (print (incf start 26)))
             (let ((start 10))
               (declare (type (integer 0) start))
               (print (incf start 22))
               (print (incf start 26))))))

  [ Update: improved this quite a bit (20-25%) by
    eliminating useless work from PROPAGATE-FROM-SETS -- but as alluded
    below, maybe we should be smarter about when to decide a derived
    type is "good enough". ]

  This example could be solved with clever enough constraint
  propagation or with SSA, but consider

    (let ((x 0))
      (loop (incf x 2)))

  The careful type of X is {2k} :-(. Is it really important to be
  able to work with unions of many intervals?

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

Another example:

(defun foo ()
  (labels ((bar (baz bim)
             (let ((n (+ baz bim)))
               (* n (+ n 1) bim))))
    (let ((a (bar 1 1))
          (b (bar 1 5))
          (c (bar 1 15)))
      (- (+ a b) c))))

Nikodemus Siivola (nikodemus) wrote :

Another from Alistair Gee:

(defun euler-1 ()
 (labels ((sum-d (n)
            (let ((m (truncate 999 n)))
              (/ (* n m (1+ m)) 2))))
   (- (+ (sum-d 3)
         (sum-d 5))
      (sum-d 15))))

Nikodemus Siivola (nikodemus) wrote :

It is worth noting that we cannot simplify

  (or (integer 0 0) (integer 2 2) (integer 4 4))

into eg.

 (integer 0 4)

in general, because

 (not (or (integer 0 0) (integer 2 2) (integer 4 4)))

 => (or (intger * -1) (integer 1 1) (integer 3 3) (integer 5 *))


 (not (integer 0 4))

 => (or (integer * -1) (integer 5 *)) the place to make these simplification decisions is in the compiler, which hopefully has enough contextual knowledge to figure out when it is safe -- and not the type system.

Paul Khuong (pvk) wrote :

It seems to me the right place to do that is in DERIVE-NODE-TYPE (and, optionally, in ADD-TEST-CONSTRAINT). The attached patch builds, tests (mostly), and manages to compile all the test cases above in decent time. The main question is how we want to widen/tighten types (see TYPE-ROUND-{UP,DOWN}); a specialised TYPE-APPROX-INTERSECTION2 for D-N-T would be useful, since we probably want to preserve the invariant that node types are always overwritten with subtypes.

Numeric, character set and member types are obvious candidates. Unions containing numeric types and array types are also interesting. What the patch implements is assuredly not on the Pareto front for complexity & effectiveness, but provides an idea of the possibilities.

Changed in sbcl:
assignee: nobody → Nikodemus Siivola (nikodemus)
status: Confirmed → In Progress
Nikodemus Siivola (nikodemus) wrote :

The cases presented here were fixed in SBCL, but I suspect other cases can still be developed that cause the same problem:

The approach taken in .28 was to simplify the types derived for arithmetic operators by allowed non-adjacent numeric ranges to be merged when the unions become overly complex -- preventing the complexity from being introduced in the first place.

However, I specifically suspect that cases still exist where the complexity isn't introduced until constraint propagation -- so something like Paul's generalized type-widening still seems like a good idea.

Changed in sbcl:
importance: Medium → Wishlist
status: In Progress → Triaged
assignee: Nikodemus Siivola (nikodemus) → nobody
summary: - compiler performance fiasco involving type inference and UNION-TYPE
+ simplify types introduced during constraint propagation
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Duplicates of this bug

Other bug subscribers