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.
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.
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.
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.
(Fernando was once my intern, back in the day ;P)
Just something I had heard somewhere; I don't have data to back it up.
[1] i.e. higher latency.
He must have the most stable setup in the world if he has confidence in those results.
Furthermore, there exists a path from h to a use of v which does not go through d. For every node p in the loop, since the loop is strongly connected and node is a component of the CFG, there exists a path, consisting only of nodes of L from p to h. Concatenating these two paths proves that v is live-in and live-out of p.
I have no idea how to formally prove that assertion (it's logically sound, afaik, someone like Walter Bright will have to jump in, he probably knows GCC inside-out), but if correct, the code change is correct semantically. The computational gain can be trivially exhibited (again, no idea how to 'prove' it) by throwing code at it and seeing the RTL emitted. (I agree it lacks 'rigor' in the academic sense, but based on the list to which he submitted his code-change and the fact that he's at Xilinx and sent it to his colleagues makes me confident enough that the change is sound.)
Edit: Fair enough. You've convinced me. (Though the SPEC2000 resulting numbers still have me in the 'maybe' category - your argument below is more sound than my ignorance.) Anyone reading this should defer to Danny's posts rather than mine for the time being (after a day or two, read the resulting responses to see the expert analyses on the mailing list). Keeping this post intact solely for continuity for the reader. RE: Walter - I'd assume he'd keep up with the competition and know enough about the RTL as it hasn't changed extensively in the last decade to make a valid opinion w/r/t changes. Either way, gracefully upvoting Danny's two posts ;)
FWIW, walter has not contributed a single patch to GCC i can find in the past 10 years (It may be longer, i stopped looking) :)
Not that this makes him bad in any way, mind you, he's just not who i'd go to for gcc expertise. That would be someone like Richard Henderson, who is pretty much never talked about, but has touched pretty much all parts of the compiler and always does great work.
Also note that embedded developers in general do not have a good reputation among compiler people for doing "sound work". Again, not that this is a characterization of their engineering skills - They often have very tight deadlines, so the amount of time they can spend figuring out things instead of applying bandaids tends to be pretty limited. So they patch something, submit it, and move on.
It's worse than that. Because LLVM and GCC are copy-lefted and his compiler has a proprietary backend, he forces himself not to even look at their code in order to make the lawyers happy.
One thing I absolutely adore about Github is the audit trail about who contributed what and when. It's a solid gold defense, and a way to limit the damage if someone does check in bad code.
The frustrating thing about many optimizations is they'll improve some code generation and worsen others, because they all interact with each other. They're like a pharmaceutical - sometimes they cure, but have deleterious side effects. Most of the work in an optimizer is trying to make an optimization work better most of the time and limit the downsides.
Or maybe it's something else that has to do with loops the way they are written.
(Assuming you are accurately measuring the parts)
These benchmarks have a slight issue that they might not represent real world performance, but compilers and CPUs tend to be optimized against them - because their timing and measurement is generally more reliable than ad-hoc real world measurement. It might lead to slight "over-optimization" which doesn't reflect real performance but at least it's reliable and repeatable.
Did they repeat the benchmark? How many times? Is that information available? (Perhaps it's available for the master branch and not for the new commit).
Of course, but i was answering whether 0.5% matters, not whether it is valid.
This is explicitly why i said "assuming you are accurately measuring the parts".
It seems you are just making a side point for the heck of it, despite completely agreeing with what i said.
I'm asking if it is more likely that the 0.5% difference is due to the change in the implementation than normal variation in the original implementation.
I don't know how you can say that this is the case based only on the information that it's a geometric mean. You need to know the variation in the reference implementation, and you don't.
The facts that he measured an increase of performance of 0.5% and he used a geometric mean are not enough information to say that it's statistically significant.
I'm not sure why you want to be so pedantic, but it doesn't seem worthwhile to me since nobody was confused.
fwiw I was confused about what you meant by valid and matters