[MLton] Shortening dependency chains in the x86 codegen

[Matthew Fluet]

> IOW, the idea is to systematically, after a register-to-register copy,
> swap the roles of the registers, so that the target of the copy isn't the
> target (or source) of the subsequent op.
> 
> The previous code would be transformed to
> 
>                                  ;; cc W->R
>         movl %edx,%esi           ;; 1
>         andl $0xFFFF,%edx        ;; 1
>         movl %edx,%edi           ;; 2  edx
>         xorl %esi,%edx           ;; 2
>         shll $0x10,%edi          ;; 3  edi
>         shrl $0x10,%edx          ;; 3
>         xorl %edx,%edi           ;; 4  edx
>         movl %edi,%edx           ;; 5  edi
>         andl $0xFF00FF,%edi      ;; 5
>         xorl %edi,%edx           ;; 6  edi
>         shll $0x8,%edi           ;; 6
>         shrl $0x8,%edx           ;; 7  edx
>         xorl %edi,%edx           ;; 8  edx
> 
> The dependency chains of the transformed code are now shorter than of the
> original code, which means that it is easier for a CPU to execute the
> intructions in parallel.  The numbers in the comments indicate the clock
> cycle at which the instruction completes on an idealized processor where
> consecutive instructions without W->R dependencies can be executed in
> parallel and every instruction takes just one cycle.

Isn't that an overly idealized processor?  My architecture is a little 
rusty, but I seem to recall (at least at one point) that x86 ISA 
processors were doing fairly aggressive register renaming behind the 
scenes exactly to alleviate dependencies.

> Any estimate on how difficult something like this would be to implement?

It wouldn't be that hard to do; somewhere in toRegisterMemLoc in 
x86-allocate-registers.fun is where such a register-register move is 
generated.  You'd simply want to see which of the two temps is used 
first in the future and adjust the register mapping to make sure the 
next used temp is left in mapped to the src reg.