Type propagation of MOD is insufficient

[Hugo Sansaqua]

(defconstant +mod+ 10007)

(defun test1 (a b)
  (declare (optimize (speed 3) (safety 0))
           (fixnum a)
           ((unsigned-byte 32) b))
  (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 (UNSIGNED-BYTE 64).
;

The value of (+ B (MOD A +MOD+)) is always a non-negative 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 derive-type 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) == (NTH-VALUE 1 (FLOOR X Y)):

(defun test2 (a b)
  (declare (optimize (speed 3) (safety 0))
           (fixnum a)
           ((unsigned-byte 32) b))
  (truncate (+ b (nth-value 1 (floor a +mod+))) +mod+))

This time Python follows the derive-type of FLOOR and successfully detects that the first argument of TRUNCATE is non-negative.

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))
  `(nth-value 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))
  `(nth-value 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.)

[Stas Boukarev (stassats)]

This only helps if the floor's derive-type 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 derive-type for MOD.

[Stas Boukarev (stassats)]

9a61b47cdc4555fb8a34457f45b3e382d5d28116

[Stas Boukarev (stassats)]

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.