There are other algorithms that may coalesce more phis, and can be done in linear time, but do not have such guarantee.
If your concern is dead phis, all dead phis (where dead is defined as unused, or only used by dead instructions) can be eliminated in linear time by performing a single linear time backwards-DCE pass on the graph.
This will get all phis and instructions that are dead, or only used by instructions that are themselves dead.
If your concern is useless phis and instructions (for lack of a better term, there are papers, and they use the word "dead" differently, so i'm defining a term here for you), where you define useless as "side-effects do not matter", such that in
*a = 5
c = a
*a = 5
c = a
the second store and assignment is useless,
This type of elimination is O(N^3) normally, and unproven bounds in SSA (AFAIK).
What exactly is "this type of elimination"? Within our compiler [0] your concrete example is optimized by an O(1) mechanism and then there is a more complex load-store-optimization which is O(n^2) I think.
Looking at your code, libfirm's DCE the standard SSA backwards DCE algorithm without control dependence computation to eliminate dead phis. It will be O(n).
The load store optimization looks like a modification of stuff i helped Thomas VanDrunen with. It is O(N^2), but will miss loads/stores depending entirely on the strength of your memory dependence calculation.
In fact, it will miss a lot, particularly around loop dependent store/load values that are equivalent.
It will catch my particular example, but GCC's testsuite has load/store examples (see gcc/testsuite/gcc.dg/tree-ssa) that it should fail at without help from other phase ordering/etc.
Thanks for the clarification. You are right, our load-store-opt cannot handle loops.
Dead code elimination technically [0] is O(n). However, it should be called "copying garbage collection" instead.
LibFirms SSA construction is minimal [1], it does not create dead phis. Or course, phis might die due to optimizations, in which case they become unreachable and get garbage collected at some point (see above). However, Firm does not model memory (global variables) as SSA, only registers (local variables).
Minor correction: LibFirm also generates pruned SSA, which is the property that guarantees lack of dead phis. Minimal SSA roughly means "no superfluous live phis".
Let me know if you still do this once you integrate a polyhedral code generator and try to do incremental SSA renaming on the nested loop outputs :)
Note that dead phis are actually useful in some contexts, particularly around loop updates
This is why things like loop-closed ssa (http://gcc.gnu.org/onlinedocs/gccint/LCSSA.html) exist, and phi nodes are generated even if the variable is never initially used outside the loop (makes sinking easier)
Thanks for that info; I have more reading to do. The actual work I get paid to do isn't on an SSA compiler, so keeping up-to-date on SSA is more of a hobby.
spill free phi elimination in polynomial time :)
There are other algorithms that may coalesce more phis, and can be done in linear time, but do not have such guarantee.
If your concern is dead phis, all dead phis (where dead is defined as unused, or only used by dead instructions) can be eliminated in linear time by performing a single linear time backwards-DCE pass on the graph. This will get all phis and instructions that are dead, or only used by instructions that are themselves dead.
If your concern is useless phis and instructions (for lack of a better term, there are papers, and they use the word "dead" differently, so i'm defining a term here for you), where you define useless as "side-effects do not matter", such that in
the second store and assignment is useless,This type of elimination is O(N^3) normally, and unproven bounds in SSA (AFAIK).