simplify types introduced during constraint propagation

[Nikodemus Siivola]

    (time (compile
           nil
           '(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: 1.0.14.36 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?

[Nikodemus Siivola (nikodemus)]

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)]

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)]

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 *))

whereas

 (not (integer 0 4))

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

...so 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)]

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.

[Nikodemus Siivola (nikodemus)]

The cases presented here were fixed in SBCL 1.0.44.28, 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.