Comment by userbinator | Hacker News Reader

Comment by userbinator | Hacker News Reader

Parent Full thread

It would be interesting to compare the statistics of compiler-generated code with that of human-written Asm, since I can easily tell the two apart; the latter tends to have a denser "texture" and less superfluous data movement.

Ideally, register-register MOV instructions on a 2-address architecture would be necessary only in the case of requiring two copies of some data, since the register/memory/immediate operands of other instructions can already be used to choose which registers should hold what data.

The fact that such a huge percentage of the instructions are simply moving data around suggests two possible explanations: these could be obligatory MOVs for making copies of data, meaning that a 2-address architecture is too limiting and a 3-address one would be more ideal, or they could be superfluous, meaning that 2-address is a sweet spot and compilers are generating lots more explicit data movement than they should. From my experience writing Asm and looking at typical data flow in applications, I'm tempted to lean toward the latter...

Calls and other instructions that use specific registers (variable shift and division on x86, for example) tend to ruin that ideal somewhat.

True, it's not always possible because there are certain constrained cases where the value in a fixed destination register immediately needs to go to a fixed source one, but from my experience a lot of cases have intervening operations that don't need a fixed source/dest, and yet the compiler didn't arrange things so that the results of preceding operations naturally went to the right place as the instruction came up, but instead had to generate a MOV. I suppose it's because there's a certain amount of "working backwards" (alternatively, "looking ahead") that's required, and traditional code generation techniques don't consider this case. A good human programmer would think "I'll need to divide, so I should compute the dividend in eax" or "there's a shift coming up, so the computation leading up to the shift amount should use ecx".

Calling conventions are similar (e.g. eax needs to be the return value), so you see things like this:

    mov ecx, [ebp+16]
    add ecx, edx
    mov eax, ecx  ; superfluous move
    ret

when this could've been done instead:

    mov eax, [ebp+16]
    add eax, edx
    ret

It's not true that traditional code generation approaches ignore this problem. Copy coalescing is a well-studied problem - the problem is that solving it optimally is expensive enough that compilers use heuristics[1]. Sometimes they don't do what you want. (Any reasonable allocator should catch the case that you mention, though.)

Higher quality compilers will also try things like commuting instructions, using lea as a three-address add, etc to avoid a move.

[1] Some recent progress on register allocation over SSA may improve this situation, but I don't think that work has made it into production compilers yet.

Reply on news.ycombinator.com