4 ms·

To add just a bit more: When assignments to variables happen in the context of a procedure call it's preferable to use registers for performance reasons since

To add just a bit more: When assignments to variables happen in the context of a procedure call it's preferable to use registers for performance reasons since memory access (even cache) is much slower by comparison. Unfortunately registers are a limited resource, so we would like to reuse them when a variable, though in scope, isn't "live" or in use. This whole area of optimization is called register allocation and the optimal solution reduces to the graph coloring problem which is NP-complete. As a result there are a myriad of approximation algorithms with knobs to turn to spend a bit more complexity for a bit more accuracy. This patch appears to be the turning of one such knob.

DannyBee 11y ago
Graph coloring is a small part of register allocation, and not the hard part. It's also not NP complete on interference graphs built from SSA form, which most modern compilers (though not GCC) use in the backend. In fact, it's linear time optimally solvable if you build ssi form, which can be done in linear time. The optimal spilling and rematerialization problems have not yet shown to be solvable in polynomial time on these forms, but folks are working on it.
- andrewflnr 11y ago
  The bit about SSI form is news to me. I have more research to do.
  - DannyBee 11y ago
    See http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf Look at page 10. (Fernando was once my intern, back in the day ;P)
- Someone 11y ago
  Also, something being NP complete does not say much about whether it is hard to do in the real world. Exponential is fine, as long as the constant, the value of n, or the exponent aren't too large. Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. It would be interesting (and quite an accomplishment, even if doesn't give significant performance gains) to combine this with whole-program optimization (imagine optimizing the calling conventions on a per-function basis, and considering generating code for a function twice, with different calling conventions) and/or with the code that decides what functions to inline, but AFAIK, nobody does that.
  - DannyBee 11y ago
    "Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. " You can do a good job with polynomial time heuristics (chaitin's heuristic) for coloring, however, you are wrong about the code. It is often very weird. At the same time, most of the performance issue is not coloring, or trying not to spill at all. The problem is deciding where to split live ranges (which introduces copies), where to merge existing live ranges (which removes copies at a cost of more interferences), where to spill, where to remat, are quite hard.
umanwizard 11y ago
I thought L1 cache access cost the same as register access on Intel machines. Is this not true? Just something I had heard somewhere; I don't have data to back it up.
- berkut 11y ago
  I think register access is technically faster than a L1 hit, but due to store forwarding from the write back cache, this extra latency is usually not visible, so in practice they're the same.
  - solarexplorer 11y ago
    You need two additional (micro)instructions, a store and a load. Store forwarding will save you from going to the cache and back, but it won't be as fast a register forwarding.
    - gpderetta 11y ago
      Yes. In particular store forwarding is slightly slower [1] than (or, in Skylake, as fast as) a plain L1 load. This still beats waiting for the dependent store to complete, but it is nowhere as fast as using a direct register reference. [1] i.e. higher latency.
- solarexplorer 11y ago
  No, it's not true. Even if L1 accesses were only 1 cycle, they would be slower. The CPU will try to execute instructions out-of-order and needs to detect dependencies and possible conflicts between instructions. This is easy with registers, if the registers are the same (have the same name), there may be conflicts or dependencies. This can be tested right after decoding the instruction. With memory it's much more complex, because the memory addresses have to be calculated before any comparisons can be made. Therefore it's much harder to reorder memory instructions. There are some exceptions, like push/pop pairs, but in general memory accesses will be significantly slower.
  - 11y ago

DannyBee 11y ago

Graph coloring is a small part of register allocation, and not the hard part. It's also not NP complete on interference graphs built from SSA form, which most modern compilers (though not GCC) use in the backend. In fact, it's linear time optimally solvable if you build ssi form, which can be done in linear time. The optimal spilling and rematerialization problems have not yet shown to be solvable in polynomial time on these forms, but folks are working on it.

andrewflnr 11y ago
The bit about SSI form is news to me. I have more research to do.
- DannyBee 11y ago
  See http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf Look at page 10. (Fernando was once my intern, back in the day ;P)
Someone 11y ago
Also, something being NP complete does not say much about whether it is hard to do in the real world. Exponential is fine, as long as the constant, the value of n, or the exponent aren't too large. Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. It would be interesting (and quite an accomplishment, even if doesn't give significant performance gains) to combine this with whole-program optimization (imagine optimizing the calling conventions on a per-function basis, and considering generating code for a function twice, with different calling conventions) and/or with the code that decides what functions to inline, but AFAIK, nobody does that.
- DannyBee 11y ago
  "Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. " You can do a good job with polynomial time heuristics (chaitin's heuristic) for coloring, however, you are wrong about the code. It is often very weird. At the same time, most of the performance issue is not coloring, or trying not to spill at all. The problem is deciding where to split live ranges (which introduces copies), where to merge existing live ranges (which removes copies at a cost of more interferences), where to spill, where to remat, are quite hard.

umanwizard 11y ago

I thought L1 cache access cost the same as register access on Intel machines. Is this not true? Just something I had heard somewhere; I don't have data to back it up.

berkut 11y ago
I think register access is technically faster than a L1 hit, but due to store forwarding from the write back cache, this extra latency is usually not visible, so in practice they're the same.
- solarexplorer 11y ago
  You need two additional (micro)instructions, a store and a load. Store forwarding will save you from going to the cache and back, but it won't be as fast a register forwarding.
  - gpderetta 11y ago
    Yes. In particular store forwarding is slightly slower [1] than (or, in Skylake, as fast as) a plain L1 load. This still beats waiting for the dependent store to complete, but it is nowhere as fast as using a direct register reference. [1] i.e. higher latency.
solarexplorer 11y ago
No, it's not true. Even if L1 accesses were only 1 cycle, they would be slower. The CPU will try to execute instructions out-of-order and needs to detect dependencies and possible conflicts between instructions. This is easy with registers, if the registers are the same (have the same name), there may be conflicts or dependencies. This can be tested right after decoding the instruction. With memory it's much more complex, because the memory addresses have to be calculated before any comparisons can be made. Therefore it's much harder to reorder memory instructions. There are some exceptions, like push/pop pairs, but in general memory accesses will be significantly slower.
- 11y ago