That example in figure 1 really confused me for a moment, since it's a mix of GAS and Intel syntax - no $ or %, but with size suffices and the opposite operand order.

It's interesting to observe that "brute force" approaches to optimisation are yielding very good results, but I've always believed (and in this case, the "in some cases, expert handwritten assembly" phrase somewhat seems to support this) that making compilers more intelligent is the way to go -- make them "think" more like a human Asm programmer would.

For example, using their first sequence, 3 out of 11 instructions are moves that do nothing more than unproductive "register shuffling", which suggests to me that there's still room for improvement. As the saying goes, "the fastest way to do something is to not do it at all." That shuffling is only there because they constrained their register usage, and if I was implementing this, I'd arrange the code that came before such that the right operands are naturally in the right registers when instructions that require them e.g. mul are used. To my knowledge, this technique is not implemented in any compiler and none of the existing research on register allocation or optimisation mentions anything like that; instead they all seem to suggest "introduce extra moves and hope we can somehow remove them"... which doesn't work as well as planning ahead so you don't ever need them in the first place. Moves should only be used for making copies of values, since instructions that do other operations can implicitly "move" data as part of their operation anyway. Applying this principle to their first example eliminates two moves and yields this sequence:

    shlq 32, rcx
    movl edx, eax  <-- move + zero-extend
    xorq rcx, rax  <-- why xor? or probably works too
    mulq rsi
    addq r8, rdi
    adcq 0, rdx
    addq rax, rdi  <-- we want result in rdi anyway
    adcq 0, rdx
    movq rdx, r8   <-- this is still "room for improvement"

I think the same goes for optimisation as a separate pass - the idea of generating horribly inefficient code (gcc -O0 is a great example) and then trying to optimise it just doesn't make much sense to me; in my mind, if I tell a compiler to do max size or speed optimisation, it should be selecting and generating instructions that are pretty close to optimal already. I wonder if this is a result of that famous "premature optimisation" quote...

"Fastest" is also something that can be highly dependent on the processor model, so this is also important to keep in mind if you're compiling on one machine but executing on another. If anyone would like to, I'd be really interested in seeing the performance of my two-moves-less sequence above vs the one in the paper (don't have a 64-bit machine to test this on at the moment.)