3 ms·
Program dependency graphs 'work backwards' in that you have a node that performs a computation, and then you have a graph of edges backwards to information and
by chrisseaton 9y ago
Program dependency graphs 'work backwards' in that you have a node that performs a computation, and then you have a graph of edges backwards to information and effects in other nodes it needs in order to run. The 'first node' in a program dependency graph is the result that you want to achieve.
This doesn't really solve the problem that you are describing though. I think that's more to-do with the register allocator - there's where the moves come from.
Something interesting to note is that I think register to register moves are extremely cheap, because the processor is renaming all registers anyway. I think except for taking up instruction cache and a little work for decode and dispatch, these moves don't actually consume any execution slots so they're not a problem.
We are also finding in practice that simpler register allocation algorithms, such as linear scan, don't really seem much worse in practice very complicated algorithms that try to eliminate these moves. So that's more evidence that maybe they're not the problem you think they are.
When you read assembly it's frustrating to see redundant moves, but I'm not sure they actually cause as much slowdown as you think.
I'm not an expert in architecture though.