10 ms·

You can do dead code elimination before register allocation. Dead code elimination is doable in polynomial time. Alternatively, you can you use this relatively

• DannyBee 13y ago
  True. Let me expand a bit, I guess, to prevent confusion. Your time bounds and what you get depends on what you mean by "dead code", and how you perform it. The vast majority of DCE algorithms, in books, in compilers, etc, on SSA form, have the same properties: 1. The "bad" ones are forward DCE algorithms, and do not eliminate everything they could because they process in the wrong order. 2. The "good" ones, used in most compilers, are backwards DCE algorithms, and eliminate all dead scalar code in a straight line. Both are O(n). The standard backwards DCE algorithm has a number of deficiencies, that cannot be eliminated sanely in O(n) time. 1. These DCE algorithms do not consider memory affecting statements dead unless they can prove they are non-side effecting. Proving that is going to usually require at least some N^2 analysis somewhere. This means they miss all dead scalar code that results from a useless memory reload (second order effects), and generally will not eliminate any dead stores. Even though this is code, and it's dead, it is not eliminated. 2. These DCE algorithms that are O(n) don't deal with control altering statements. Jumps to empty blocks, as well as code contained in unreachable blocks, will be considered non-dead unless you include control dependence and some form of branch evaluation. You can compute control dependence in O(n) time. In practice, the constant sucks :) It is also not possible to statically evaluate all branches in O(1) time, so even in the absence of memory statements you cannot guarantee you eliminate all dead code in O(n), only some of it. 3. These DCE algorithms do not handle partially dead code (that is, code that is dead if moved to a different place in the program, but does not otherwise affect semantics). The canonical example is: y = a + b if (...) { y = c + d } else { ... } The first statement is partially dead (dead along some branches), and performing assignment sinking will make it fully dead (if you sink a copy into the else branch, the original is now fully dead). Performing this type of elimination is N^3 or worse, i haven't seen better time bounds on SSA. (It is not, AFAIK, completely subsumed by something like SSUPRE) GCC (and I think LLVM now) actually performs the most trivial case of this, which catches a very large number of cases once other passes are run. Well, actually, looking again, it looks like over the years it's grown. I guess nobody's noticed it's basically equivalent to Cliff Click's GCM algorithm at this point, without the nice guarantees. It looks like it could be trivially modified into the GCM algorithm now. Time to go file a bug.
  • qznc 13y ago
    In my opinion the "good" DCE is fine. Your deficiencies should be fixed elsewhere. It largely depends on the definition of dead, though. 1. I would never consider a store dead in the sense of DCE. Those side-effect analysis should be handled elsewhere. 2. DCE should not alter control-flow. 3. Partial dead code elimination is not about dead code or elimination anything. Click understood it correctly, it is about code motion. Effectively, I argue to push the problems somewhere else. This means that DCE is a very cheap optimization and can be run multiple times during compilation. This somewhat helps with the phase ordering problem. Partial dead code elimination (and partial redundant code elimination) is still an open research question. There are multiple overlapping approaches, but none subsumes everything.
    • DannyBee 13y ago
      Sure, these are all matters of opinion, though i'll point out GCC started out thinking the same way WRT to keeping things cheap and running them multiple times. This eventually led to horrendous compile times (that LLVM was much better at) because passes refused to clean up after themselves at all. After all, cheap DCE/cheap GVN/whatever would just get run later, who cared. Those passes became necessary, and even when cheap, if you run DCE 5 times, it starts to add up. Same with not touching control flow during DCE. Leave it to the CFG simplifier, which now gets run 5 or 6 times. These are all tradeoffs, and especially in a production compiler, you have to make these tradeoffs sometimes, and do more than is academic-wise ideal to do in a single pass. This is why LLVM's GVN prunes dead instructions, etc