simplify types introduced during constraint propagation
Affects  Status  Importance  Assigned to  Milestone  

 SBCL 
Wishlist

Unassigned 
Bug Description
(time (compile
nil
'(lambda ()
(let ((start 4))
(let ((start 6))
(let ((start 10))
[ Update: 1.0.14.36 improved this quite a bit (2025%) by
eliminating useless work from PROPAGATEFROMSETS  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 :  #1 
Nikodemus Siivola (nikodemus) wrote :  #2 
Another from Alistair Gee:
(defun euler1 ()
(labels ((sumd (n)
(let ((m (truncate 999 n)))
(/ (* n m (1+ m)) 2))))
( (+ (sumd 3)
(sumd 5))
(sumd 15))))
Nikodemus Siivola (nikodemus) wrote :  #3 
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) wrote :  #4 
It seems to me the right place to do that is in DERIVENODETYPE (and, optionally, in ADDTEST
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 :  #5 
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 nonadjacent 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 typewidening 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 UNIONTYPE + simplify types introduced during constraint propagation 
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))))