Type propagation of MOD is insufficient
Affects  Status  Importance  Assigned to  Milestone  

 SBCL 
Undecided

Unassigned 
Bug Description
(defconstant +mod+ 10007)
(defun test1 (a b)
(declare (optimize (speed 3) (safety 0))
(fixnum a)
(truncate (+ b (mod a +mod+)) +mod+))
; (TRUNCATE (+ B (MOD A +MOD+)) +MOD+)
;
; note: unable to
; convert integer division to multiplication
; due to type uncertainty:
; The first argument is a (INTEGER 10006 4294987308), not a (UNSIGNEDBYTE 64).
;
The value of (+ B (MOD A +MOD+)) is always a nonnegative fixnum but Python can't detect it. This is due to the transforms of MOD: MOD is expanded into REM and REM is expanded into TRUNCATE. The returned value of (REM A +MOD+) is correctly inferred as (INTEGER 10006 10006), following the derivetype optimizer of TRUNCATE. In the transform of MOD, however, another +MOD+ is (conditionally) added to this value and Python regards the resultant type as (INTEGER 10006 20013).
Practically, I can avoid this problem by a trivial paraphrasing, (MOD X Y) == (NTHVALUE 1 (FLOOR X Y)):
(defun test2 (a b)
(declare (optimize (speed 3) (safety 0))
(fixnum a)
(truncate (+ b (nthvalue 1 (floor a +mod+))) +mod+))
This time Python follows the derivetype of FLOOR and successfully detects that the first argument of TRUNCATE is nonnegative.
Why is the current MOD transformed in this way, however? It seems to be pretty good when we define the transform of MOD in the same way as REM:
(deftransform rem ((number divisor))
`(nthvalue 1 (truncate number divisor)))
;; Current:
;; (deftransform mod ((number divisor))
;; `(let ((rem (rem number divisor)))
;; (if (and (not (zerop rem))
;; (if (minusp divisor)
;; (plusp number)
;; (minusp number)))
;; (+ rem divisor)
;; rem)))
;; New:
(deftransform mod ((number divisor))
`(nthvalue 1 (floor number divisor)))
This change appears to be no problem from both points, conformance to the ANSI and the efficiency. (No new failing tests on my environment, Windows 8.)
Hugo Ishimaru (privetkitty) wrote :  #1 
Stas Boukarev (stassats) wrote :  #3 
9a61b47cdc4555f
Stas Boukarev (stassats) wrote :  #4 
Also improved FLOOR's expansion so that it test the remainder, not the divisor. That way it's both faster and will aid constraint propagation even if the initial floor type derivation wasn't good.
This only helps if the floor's derivetype is reached when all the arguments are known. But after it transforms into the same code as MOD, it will produce the same problem.
> Why is the current MOD transformed in this way, however?
It's less work for the compiler.
But I'll apply the patch, because I don't want to write a derivetype for MOD.