[MIT-Scheme-devel] Re: Bug in x86-64 compiler?

[Taylor R Campbell]

   Date: Sat, 24 Apr 2010 12:17:15 -0700
   From: Chris Hanson <address@hidden>

   There's a reproducible bug in Edwin that appears to be a compiler bug
   in the x86-64 back end.  The problem is the following sequence (from
   edwin/bufwmc, procedure column->y, the second to last procedure in the
   file):

           ;; (assign (register #x3a) (fixnum-2-args fixnum-quotient (register
   #x29) (register #x2b) #f))
           (mov q (r 0) (r 1))
           (cse q (r 2) (r 0))
           (idiv q ((r 2) : (r 0)) (@ro 6 #x300))
           (sal q (r 0) (&u 6))

Here's the analogous i386 code:

        ;; (assign (register #x2a) (fixnum-2-args fixnum-quotient (register 
#x19) (register #x1b) #f))
        (mov w (r 0) (r 1))
        (mov w (r 2) (r 0))
        (sar w (r 2) (& #x1f))
        (idiv w (r 0) (@ro w 6 #x600))
        (sal w (r 0) (& 6))

So I don't think this is specific to the x86-64 back end.  (The LAP
generation methods for FIXNUM-QUOTIENT are nearly identical, except
for MOV/SAR vs CSE, which has to do with some fiddly details of sign
extension that I have thoroughly forgotten.)  What's a little puzzling
is that any pseudo-registers should be saved into their homes in the
x86-64 code -- there ought to be plenty machine registers to go
around.  I guess this just reflects the greediness of the register
allocation algorithm, which doesn't look ahead to see what machine
registers the following instructions may need.

   Basically, just before this code is run, r0 contains register #x2b
   (x-max), and r1 contains register #x29 (column).  The first
   instruction clobbers r0, losing x-max, then the idiv instruction
   refers to register #x2b's memory home; however that value was never
   saved to memory, so whatever is there is complete junk.  Usually the
   result of the idiv instruction is an exception that crashes Scheme.
   Sometimes it's just the wrong answer.

Just before lie the instructions

        (mov w (@ro w 6 #x600) (r 0))   ; i386
        ...
        (mov w (r 3) (@ro w 6 #x600))
        ...
        (mov w (r 0) (r 3))

        (mov q (@ro 6 #x300) (r 0))     ; x86-64
        ...
        (mov q (r 3) (@ro 6 #x300))
        ...
        (mov q (r 0) (r 3))

with no writes to r3 in the ellipsis.  These instructions are skipped,
though, if LINE-END? is false.  What I think happened is that, upon
seeing

(if line-end?
    (if (eq? (fix:remainder column x-max) 0)
        ...
        (fix:quotient column x-max))
    (fix:quotient column x-max)),

the RTL optimizer merged the common suffixes for the tail expression

(fix:quotient column x-max),

and the register allocator saved X-MAX (formerly in r0) into its home
#x300/#x600, for the evaluation of

(eq? (fix:remainder column x-max) 0),

but failed to reflect the save along both paths into the common suffix
block.  Consequently, the common suffix block thinks that X-MAX will
be in its home, but the path when LINE-END? is false fails to save
X-MAX into its home.