5 ms·

You know way way more about compilers than I do, but the key is in this: Furthermore, there exists a path from h to a use of v which does not go through d. For

You know way way more about compilers than I do, but the key is in this: 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 ;)

DannyBee 11y ago
"someone like Walter Bright will have to jump in, he probably knows GCC inside-out" 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.
- bionsuba 11y ago
  "walter has not contributed a single patch to GCC i can find in the past 10 years (It may be longer, i stopped looking) :)" 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.
  - comex 11y ago
    (LLVM is under a BSD-style license and thus not copylefted, although it does require attribution.)
  - WalterBright 11y ago
    Haha, I once got sued by a company claiming I stole code from them, and their lawyer got sent packing when it turned out they had stolen the code from me. (I had a registered copyright on it.) 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.
- WalterBright 11y ago
  No, I've never contributed a patch to GCC. No need to look :-)
quietplatypus 11y ago
I've no idea about the specifics either, but I've done a little bit of compiler optimization in the JIT setting. What you say sounds right, and I'm filing it in the same mental bin as "when you're looking at which parts of the state + variables depend on others, you're most of the time better off reasoning from the initial state and input variables, instead of trying to do clever tricks of also reasoning backward from the output variables and combining them, resulting in worse approximations" Or maybe it's something else that has to do with loops the way they are written.
WalterBright 11y ago
Walter here. No, I don't know gcc at all. 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.

DannyBee 11y ago

"someone like Walter Bright will have to jump in, he probably knows GCC inside-out" 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.

bionsuba 11y ago
"walter has not contributed a single patch to GCC i can find in the past 10 years (It may be longer, i stopped looking) :)" 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.
- comex 11y ago
  (LLVM is under a BSD-style license and thus not copylefted, although it does require attribution.)
- WalterBright 11y ago
  Haha, I once got sued by a company claiming I stole code from them, and their lawyer got sent packing when it turned out they had stolen the code from me. (I had a registered copyright on it.) 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.
WalterBright 11y ago
No, I've never contributed a patch to GCC. No need to look :-)

quietplatypus 11y ago

I've no idea about the specifics either, but I've done a little bit of compiler optimization in the JIT setting. What you say sounds right, and I'm filing it in the same mental bin as "when you're looking at which parts of the state + variables depend on others, you're most of the time better off reasoning from the initial state and input variables, instead of trying to do clever tricks of also reasoning backward from the output variables and combining them, resulting in worse approximations" Or maybe it's something else that has to do with loops the way they are written.

WalterBright 11y ago

Walter here. No, I don't know gcc at all. 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.